OPTIMALISASI PENCARIAN LINTASAN TRAVELING SALESMAN PROBLEM  MENGGUNAKAN ALGORITMA BACKTRACKING

Hari Murti; Edy Supriyanto; Sugiyamta Sugiyamta

doi:10.35315/dinamik.v23i1.7175

Hari Murti Universitas Stikubank
Edy Supriyanto Universitas Stikubank
Sugiyamta Sugiyamta Universitas Stikubank

DOI: https://doi.org/10.35315/dinamik.v23i1.7175

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.

References

Aristi, G., 2014, Perbandingan Algoritma Greedy, Algoritma Cheapest Insertion Heuristics dan Dynamic Programming Dalam Penyelesaian Travelling Salesman Problem, Jurnal Paradigma, Vol. XVI, No. 2, Hal. 52 - 58, September 2014.
Desiani, A. dan Arhami, M., 2006, Konsep Kecerdasan Buatan, Penerbit Andi, Yogyakarta.
Erdiwansyah, Gani, T. A., 2016, Analisis Perbandingan Metode Local Search dan Population Based Dalam Algoritma Berevolusi untuk Penyelesaian Travelling Salesman Problem (TSP), Jurnal Serambi Engineering, Volume I, Nomor 1, Hal. 111, Agustus 2016.
Fatmawati, Prihandono, B., Noviani, E., 2015, Penyelesaian Travelling Salesman Problem Dengan Metode Tabu Search, Buletin Ilmiah Mat. Stat. Dan Terapannya (Bimaster), Vol. 04, No.1, hal 17 – 24, (2015).
Kusumadewi, S., 2003, Artificial Intelligence (Teknik dan Aplikasinya), Graha Ilmu, Yogyakarta.
Kusumadewi, S. dan Purnomo, H., 2005, Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik, Graha Ilmu, Y ogyakarta.
Murti, H., Soelistijadi, R., Sugiyamto, 2017, Analisa Kebutuhan Waktu pada Proses Penyelesaian Traveling Salesman Problem, Prosiding SINTAK 2017 Hal. 74 - 78, Universitas Stikubank Semarang.
Paliyus, R., Muhammad Danial, M., Udjulawa, D.,, 2015, Implementasi Backtracking Dalam Permainan Cari Kata untuk Mengenalkan Nama dan Fungsi Anggota Tubuh, http://eprints.mdp.ac.id/1681/, STMIK MDP GI Palembang.
Russell, S., Norvig, P., 2010, Artificial Intelligence A Modern Approach Third Edition, Pearson, USA.
Widodo, A.W., Mahmudy, W.F., 2010, Penerapan Algoritma Genetika pada Sistem Rekomendasi Wisata Kuliner, Jurnal Ilmiah KURSOR Vol. 5, No. 4, hlm. 205-211, Juli 2010.
Yunus, H., Helmi, Martha, S., 2015, Metode Program Dinamis pada Penyelesaian Traveling Salesman Problem, Buletin Ilmiah Mat. Stat. dan Terapannya, Volume 04, No. 3 (2015), hal 329 – 336.