Perbandingan Cheapest Insertion Heuristic dan Algoritma Christofides untuk Menentukan Tour Pasar Tradisional di Kota Bandar Lampung
Article Sidebar
Main Article Content
Abstract
The Traveling Salesman Problem is a problem to determine the cheapest cost for a salesman staring from original location to all destination on his objective and return to the original location. In this study, a comparison of the Cheapest Insertion Heuristic and the Christofides Algorithm will be carried out to determine the traditional market tour in Bandar Lampung. The results obtained show that the solution obtained manually using the Cheapest Insertion Heuristic and the Christofides Algorithm produce the same solution, which is 216 minutes, while using Python programming, the Cheapest Insertion Heuristic provides a solution in 217 minutes and using the Christofides Algorithm in 226 minutes. However, because the solution obtained manually or by programming still produces intersections in the tour, to get better solution, the tour may be revised/repaired by removing the intersections. After repairing the tour, the same solution is obtained, whether using the Cheapest Insertion Heuristic or the Christofides Algorithm, which is 216 minutes.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
References
K. Saleh, Helmi & B. Prihandono, Penentuan Rute Terpendek Dengan Menggunakan Algoritma Cheapest Insertion Heuristic (Studi Kasus: PT. Wicaksana Overseas International Tbk. Cabang Pontianak). Bimaster: Buletin Ilmiah Math. Stat. dan Terapannya, vol. 4, no. 3, pp. 295–304, 2015, https://doi.org/10.26418/bbimst.v4i03.11888.
E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, & D. B. Shmyos, The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, 1991.
K. Kusrini & J. E. Istiyanto, Penyelesain Travelling Salesman Problem dengan Algoritma Cheapest Insertion Heuristic dan Basis Data. Jurnal Informatika, vol. 8, no. 2, pp. 109-114, 2008, https://doi.org/10.9744/informatika.8.2.pp.%20109-114.
F. Fargiana, R. Respitawulan, Y. Fajar, D. Suhaedi, & E. Harahap, Implementation of Cheapest Insertion Heuristic Algorithm in Determining Shortest Delivery Route, International Journal of Global Operations Research, vol. 3, no. 2, pp. 37–45, 2022, https://doi.org/10.47194/ijgor.v3i2.137.
M. Hilman & Y. Y. Sidik, Penentuan Rute Distribusi Menggunakan Metode Cheapest Insertion Heuristic (CIH) Guna Meminimalkan Pengeluaran Biaya Pada Ukm Aren Creativity di Kabupaten Ciamis, Jurnal Industrial Galuh, vol. 4, no. 2, pp. 51–61, 2022, https://doi.org/10.25157/jig.v4i2.3017.
D. T. Wiyanti, Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem, Jurnal Transformatika, vol. 11, no. 1, pp. 1-6, 2013, https://doi.org/10.26623/transformatika.v11i1.76.
E. Yulianto E & A. Setiawan, Optimasi Rute Sales Coverage Menggunakan Algoritma Cheapest Insertion Heuristic dan Layanan Google Maps API, INTERNAL (Information System Journal), vol. 1, no. 1, pp. 39–54, 2018, https://doi.org/10.32627/internal.v1i1.326.
M. Amelia, I. I. Sholeha, Y. R. Revangga, & Wamiliana, The Comparison of Brute Force, Cheapest-Insertion, and Nearest-Neighbor Heuristics for Determining the Shortest Tour for Visiting Malls in Bandar Lampung. EXPERT: Jurnal Manajemen Sistem Informasi dan Teknologi, vol. 14, no. 1 , pp. 51-54 , 2024. http://dx.doi.org/10.36448/expert.v14i1.3715.
L. V. Hignasari & E. D. Mahira, Optimization of Goods Distribution Route assisted by Google Maps with Cheapest Insertion Heuristic Algorithm (CIH). SINERGI, vol. 22, no. 2, pp. 132-138, 2018, https://dx.doi.org/10.22441/sinergi.2018.2.010.
M. Kurniawan, F. Farida, & S. Agustini, Rute Terpendek Algoritma Particle Swarm Optimization dan Brute Force untuk Optimasi Travelling Salesman Problem, Jurnal Teknik Informatika, vol. 14, no. 2, pp. 191-200, 2021, https://doi.org/10.15408/jti.v14i2.19094.
S. Violina, Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP), TURCOMAT, vol. 12, no. 8, pp. 1226–1229, 2021.
A. Wilson, Y. Sibaroni, & I. Ummah, Analisis Penyelesaian Traveling Salesman Problem Dengan Metode Brute Force Menggunakan Graphic Processing Unit, e-Proceeding of Engineering, vol. 2, no. 1, pp. 1874-1883, 2015.
S. A. Nene & S. K. Nayar, A simple algorithm for nearest neighbor search in high dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 9, pp. 989-1003, 1997, https://doi.org/10.1109/34.615448.
I. Sutoyo, Penerapan Algoritma Nearest Neighbour untuk Menyelesaikan Travelling Salesman Problem, Paradigma - Jurnal Komputer dan Informatika, vol. 20, no. 1, pp. 101–106, 2018, https://doi.org/10.31294/p.v20i1.3155.
F. J. Tjoea & S. Halim, Evaluasi Rute Pelayaran Kapal dengan Pendekatan Modified Minimum Spanning Tree, Jurnal Titra, vol. 11, no. 2, pp. 265-272, 2023.