đ
17 June 2019
DOI: 10.35315/dinamik.v23i1.7175
OPTIMALISASI PENCARIAN LINTASAN TRAVELING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA BACKTRACKING
Dinamik
Universitas Stikubank
đ Abstract
Tujuan pemecahan masalah penjual atau wira niaga keliling (traveling salesman problem, TSP) adalah menentukan lintasan atau rute dengan total jarak atau biaya yang paling minimum. Penelitian ini berkenaan dengan proses optimalisasi pencarian alternatif lintasan atau rute pada masalah TSP. Penjual mencari rute atau lintasan untuk mengunjungi semua kota yang ada sebanyak satu kali kunjungan. Proses optimalisasi pencarian alternatif menggunakan algoritma backtracking.
Terdapat lima buah kasus TSP yang akan digunakan yaitu TSP1 memiliki 4 buah kota dengan 6 lintasan (jalur), TSP2 memiliki 5 buah kota dengan 10 lintasan, TSP3 memiliki 6 buah kota dengan 15 lintasan, TSP4 memiliki 7 buah kota dengan 21 lintasan, dan TSP5 memiliki 8 buah kota dengan 28 lintasan. Dari hasil pengujian diperoleh algoritma runut-balik (backtracking) dapat digunakan untuk menghasilkan jumlah alternatif lintasan yang lebih sedikit jika dibandingkan dengan total kombinasi alternatif lintasan. Semakin besar jumlah node (kota) dan jumlah lintasan (jalur) maka prosentase pengurangan variasi (alternatif) akan lintasan semakin besar.
Terdapat lima buah kasus TSP yang akan digunakan yaitu TSP1 memiliki 4 buah kota dengan 6 lintasan (jalur), TSP2 memiliki 5 buah kota dengan 10 lintasan, TSP3 memiliki 6 buah kota dengan 15 lintasan, TSP4 memiliki 7 buah kota dengan 21 lintasan, dan TSP5 memiliki 8 buah kota dengan 28 lintasan. Dari hasil pengujian diperoleh algoritma runut-balik (backtracking) dapat digunakan untuk menghasilkan jumlah alternatif lintasan yang lebih sedikit jika dibandingkan dengan total kombinasi alternatif lintasan. Semakin besar jumlah node (kota) dan jumlah lintasan (jalur) maka prosentase pengurangan variasi (alternatif) akan lintasan semakin besar.
âšī¸ Informasi Publikasi
Tanggal Publikasi
17 June 2019
Volume / Nomor / Tahun
Volume 23, Nomor 1, Tahun 2019
đ HOW TO CITE
Murti, Hari; Supriyanto, Edy; Sugiyamta, Sugiyamta, "OPTIMALISASI PENCARIAN LINTASAN TRAVELING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA BACKTRACKING," Dinamik, vol. 23, no. 1, Jun. 2019.
ACM
ACS
APA
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
0
Sitasi
Cek Google Scholar