Comparison of the Cheapest Insertion Heuristic Algorithm, Christofides Algorithm, and Nearest Neighbor Algorithm for Determining Hospital Tours in Bandar Lampung City
DOI:
https://doi.org/10.23960/komputasi.v13i2.332Keywords:
Cheapest Insertion Heuristic Algorithm, Christofides Algorithm, Nearest Neighbor Algorithm, Travelling Salesman ProblemAbstract
Determining the optimal route is one of the important aspects in planning the distribution of health services, especially in emergency conditions in Bandar Lampung City. This study compares three algorithms for solving tour problems, namely Cheapest Insertion Heuristic, Nearest Neighbor (NN), and Christofides Algorithm, in determining the fastest tour to a number of hospitals. Calculations were performed manually and also implemented using the Python programming language. The results obtained show that manually and using Python programming, the Cheapest Insertion Heuristic algorithm produced 152 minutes, the Nearest Neighbour algorithm 142 minutes, and the Christofides Algorithm 147 minutes.
Downloads
References
S. Farlinda, R. Nurul, and S. A. Rahmadani. “Pembuatan Aplikasi Filling Rekam Medis Rumah Sakit ISSN : 2354-5852,” Kesehatan, vol. 5, no. 1, pp. 8–13, 2017.
A. Primadiamanti, G. A. R. Saputri, and D. L. Sari. “Evaluasi Penyimpanan Dan Pendistribusian Obat Di Instalasi Farmasi Rumah Sakit Mutiara Bunda Tulang Bawang,” J. Farm. Malahayati, Vol. 4(2), pp. 205–215, 2022, doi: 10.33024/jfm.v4i2.5315.
J. Jutriano and A. Abidin, “Integrasi Servqual, Kano Model, Dan Kansei Engineering Untuk Peningkatan Kualitas Layanan Distribusi Alat Kesehatan Urologi,” J. Compr. Sci., Vol. 2(12), pp. 1458–1466, 2023, doi: 10.59188/jcs.v2i12.561.
G. Reinelt., The Traveling Salesman: Computational Solutions for TSP Applications. Springer, 2003.
Ashish Gupta and Shipra Khurana, “Study of Traveling Salesman Problem Using Genetic Algorithm,” Int. J. Manag. IT& Engineering, Vol. 3(3), pp. 183–190, 2012.
D. B Essay, “An evolutionary approach to the traveling salesman problem,” Biol. Cybern., Vol. 3(3), pp. 139– 144, 1988.
A. W. Aranski, “Optimization of The Smallest Road Using The Traveling Salesman Problem (TSP) Method,”
Int. J. Inf. Syst. Technol. Akreditasi, Vol. 6 (158), pp. 159–166, 2022.
W. A. F. B and S. Rosnafi, “Product Distribution Route using Nearest Neighbor Algorithm Rute Pendistribusian Barang dengan Algoritma Nearest Neighbor,” Vol. 4, pp. 894–900, 2024.
I. Sutoyo, “Penerapan Algoritma Nearest Neighbour untuk Menyelesaikan Travelling Salesman Problem,” J. Paradig., Vol 20 (1), p. 101, 2018.
A. Lusiani, S. S. Purwaningsih, and E. Sartika, “TSP Method Using Nearest Neighbor Algorithm at PT. J&T Express in Bandung,” J. Lebesgue J. Ilm. Pendidik. Mat. Mat. dan Stat., Vol. 4(3), pp. 1560–1568, 2023, doi:
46306/lb.v4i3.449.
M. W. Stefan Hougardy, “On the nearest neighbor rule for the metric traveling salesman problem,” Discret. Appl. Math., pp. 101–103, 2015.
L. V. Hignasari and E. D. Mahira, “Optimization of Goods Distribution Route Assisted By Google Map With Cheapest Insertion Heuristic Algorithm (Cih),” Sinergi, Vol. 22(2), p. 132, 2018, doi: 10.22441/sinergi.2018.2.010.
K. Meliantari, D. Putra Githa, and N. K. Ayu Wirdiani, “Optimasi Distribusi Produk Menggunakan Metode Cheapest Insertion Heuristic Berbasis Web,” J. Ilm. Merpati (Menara Penelit. Akad. Teknol. Informasi), Vol. 6(3), p. 204, 2018, doi: 10.24843/jim.2018.v06.i03.p07.
R. G. Utomo, D. S. Maylawati, and C. N. Alam, “Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP),” J. Online Inform., Vol. 3(1), p. 61, 2018, doi: 10.15575/join.v3i1.218.
A. R. Dinata, Wamiliana, M. Ansori, Fitriani, and Notiragayu. Determining the Shortest Tour Location of Tourist Attractions in Bandar Lampung Using Cheapest Insertion Heuristic (CIH) and Modified Sollin Algorithm. Jurnal Pepadun, Vol. 6 (1), pp. 92-102, 2025.
N.W. Hadi, R. Nurfabella, Wamiliana, and M. Mustika. “Comparative Analysis of CIH and Christofides Algorithms for Optimal Tourist Route Planning in West Java”, Integra: Journal of Integrated Mathematics and Computer Science, Vol 2 (2):56 -62, 2024.
M. Y. Aswin and M. Ansori, “Perbandingan Cheapest Insertion Heuristic dan Algoritma Christofides untuk Menentukan Tour Pasar Tradisional di Kota Bandar Lampung” Jurnal Pepadun, Vol. 5(2), pp. 182–194, 2024.
F. J. Tjoea and S. Halim, “Evaluasi Rute Pelayaran Kapal dengan Pendekatan Modified Minimum Spanning Tree,” Jurnal Titra, Vol. 11 (2), pp. 265–272, 2023.
I. K. Omar Cheikhrouhou, “A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy, Computer Science Review,” Comput. Sci. Rev., Vol. 40, 2021.
D. R.A. Putri, N.A. Oktavia, S. L. Chasanah, R. Sawitri, and F. A. Paskalia. “Implementation of Christofides Algorithm to Determine the Shortest Tour of Some Hospitals in Palembang City” Integra : Journal of Integrated Mathematics and Computer Science, Vol. 2 (1), pp. 15–19.
Hadi N. W., R. Nurfabella, Wamiliana, and M. Mustika. Comparative Analysis of CIH and Christofides Algorithms for Optimal Tourist Route Planning in West Java. Integra: Journal of Integrated Mathematics and Computer Science, Vol 2 (2):56 -62, 2024.
M. Z. Rahman, S. R. Sheikh, A. Islam, and M. A. Rahman. Improvement of the Nearest Neighbor Heuristic Search Algorithm for Traveling Salesman Problem. Journal of Engineering Advancements, Vol 5(1), pp.19– 26, 2024.
S. Mutrofin, A. Mu'alif, R. V. H. Ginardi, and C. Fatichah. Solution of class imbalance of k-nearest neighbor for data of new student admission selection. International Journal of Artificial Intelligence Research, 3(2), pp. 47- 55, 2019.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Jurnal Komputasi
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
