Article Details

KOMPARASI DAN IMPLEMENTASI ALGORITMA PARTIALLY MATCHED CROSSOVER DAN GRAPH THEORY DIJKSTRA UNTUK TRAVELLING SALESMAN PROBLEM

Oleh   Faras Banas Lubis [18217046]
Kontributor / Dosen Pembimbing : Dr. Tutun Juhana, S.T., M.T.;Luqman Muhammad Zagi, S.T., M.T.;
Jenis Koleksi : S1-Tugas Akhir
Penerbit : Sistem dan Teknologi Informasi
Fakultas : Sekolah Teknik Elektro dan Informatika
Subjek :
Kata Kunci : demand chain, Travelling Salesman Problem, Capacitated Vehicle Routing Problem, logistik 4.0, algoritma genetika, algoritma dari algoritma rule based, Partially Matched Crossover, One Order Crossover, Graph Theory, Dijkstra, integer linear, Heroku
Sumber :
Staf Input/Edit : Dessy Rondang Monaomi  
File : 0 file
Tanggal Input : 21 Sep 2022

Tidak ada file


Salah satu masalah dalam logistik adalah Capacitated Vehicle Routing Problem (CVRP) yang merupakan sub-masalah dari Travelling Salesman Problem. Masalah ini berbentuk penentuan rute minimal serta ‘biaya’ minimal dari pengiriman barang oleh kendaraan dan dapat diselesaikan dengan analisis algoritma. Metodologi yang digunakan dalam analisis algoritma pada penelitian ini adalah Engineering Design Process (EDP). Dalam pelaksanaan EDP akan ada dua algoritma yang dibandingkan yaitu algoritma genetika dan algoritma dari algoritma rule based. Algoritma genetika adalah algoritma yang mencari solusi terbaik berdasarkan teori evolusi biologis yang diaplikasikan ke algoritma komputer. Algoritma genetika yang akan dianalisis adalah Partially Matched Crossover dan One Order Crossover. Sedangkan algoritma dari algoritma rule based adalah algoritma yang mengaplikasikan aturan atau rule ke algoritma komputer. Terdapat dua algoritma dari algoritma rule based yang akan dianalisis, yaitu: Graph Theory Dijkstra dan Integer Linear. Dari algoritma tersebut akan diuji dengan mengukur kompleksitas waktu, ruang, keefektifan, dan kelengkapan. Kriteria-kriteria ini penting dalam komparasi algoritma. Berdasarkan skor hasil, algoritma PartiallyMatched Crossover mendapatkan nilai 50,91% dan algoritma Dijkstra mendapatkan nilai 83,27%. Dari algoritma yang diuji, algoritma Graph Theory Dijkstra yang mendapatkan skor yang lebih tinggi. Hal ini dijadikan fondasi untuk aplikasi pemilihan rute yang dapat digunakan oleh perusahaan logistik demand chain. Situs menggunakan Heroku sebagai platform.