Implementation of Cheapest Insertion Heuristic Algorithm  in Determining Shortest Delivery Route

Farid Fargiana; Respitawulan Respitawulan; Yusuf Fajar; Didi Suhaedi; Erwin Harahap

doi:10.47194/ijgor.v3i2.137

Authors

Farid Fargiana
farid.risqullah22@gmail.com
Department of Mathematics, Universitas Islam Bandung, Bandung, Indonesia
Respitawulan Respitawulan Department of Mathematics, Universitas Islam Bandung, Bandung, Indonesia
Yusuf Fajar Department of Mathematics, Universitas Islam Bandung, Bandung, Indonesia
Didi Suhaedi Department of Mathematics, Universitas Islam Bandung, Bandung, Indonesia
Erwin Harahap Department of Mathematics, Universitas Islam Bandung, Bandung, Indonesia

Keywords:

Goods Delivery Route, Travelling Salesman Problem, Cheapest Insertion Heuristic, Algorithm, Shortest Path

Abstract

The buying and selling transaction system that many people use today is the online buying and selling system. In this system, there is a process of goods delivery by one branch of a freight forwarder in Indonesia, namely SiCepat Express Baleendah. In the process of shipping goods, a delivery route with the shortest path is needed in order to minimize of the goods delivery process. The problem of the route of goods delivery can be solved by one of the algorithms in the Traveling Salesman Problem (TSP), namely the Cheapest Insertion Heuristic (CIH) Algorithm. This study aims to determine the shortest route and distance for goods delivery using the CIH Algorithm by the Asymmetric TSP CIH application, as well as knowing its efficiency compared to the route that used by SiCepat Express Baleendah. The result shows that the use of the CIH Algorithm is proven to produce a more efficient delivery route than the route created by SiCepat Express Baleendah. Based on the goods delivery route from SiCepat Express Baleendah, the result of the total distance is 18.55 km. On the other hand, based on the CIH Algorithm, the delivery route obtained result is 13.45 km. The efficiency of using the CIH Algorithm is 27.48% better than the result from SiCepat Express Baleendah route.

References

Cantona, A., Fauziah, F., & Winarsih, W. (2020). Implementasi Algoritma Dijkstra pada Pencarian Rute Terpendek ke Museum di Jakarta. Jurnal Teknologi dan Manajemen Informatika, 6(1), 27-34.

Fadhillah, I., Permanasari, Y., & Harahap, E. (2017). Representasi Matriks untuk Proses Crossover Pada Algoritma Genetika untuk Optimasi Travelling Salesman Problem. Matematika: Jurnal Teori dan Terapan Matematika, 16(1).

Fitria, T. N. (2017). Bisnis Jual Beli Online (Online Shop) dalam Hukum Islam dan Hukum Negara. Jurnal Ilmiah Ekonomi Islam, 3(01), 52-62.

Harahap, E. (2003). Graph Bipartite Pada Penguatan Kerangka Baja Persegi. Prosiding Integratif, Seminar Nasional Matematika UNPAD, 46-49.

Hayu, W., Yuliani, Y., & Sam, M. (2017). Pembentukan Pohon Merentang Minimum Dengan Algoritma Kruskal. Indonesian Journal of Fundamental Sciences, 3(2), 108-115.

Merdeka.com. (2021). Belanja Online Meningkat Saat Pandemi, Ini Daftar EÂ¬Commerce Paling Banyak Dikunjungi. Online: https://www.merdeka.com/ (accessed on 12 December 2021)

Munir, R. (2012). Matematika Diskrit. Penerbit Informatika. Bandung.

Sayekti, Hangga Aji. (2015). CIH (Cheapest Insertion Heuristic). https://github.com/hangga/CIH (accessed on 15 December 2021)

SiCepat Express. (2021). https://www.sicepat.com/ (accessed on 12 December 2021)

Sunaryono, A. H., Permanasari, P., & Harahap, E. (2016). Pemilihan Rute Perjalanan Terpendek Menggunakan Algoritma Dijkstra dan Google Maps.

Wattimena, A. Z., & Lawalatta, S. (2013). Aplikasi Algoritma Kruskal dalam Pengotimalan Panjang Pipa. BAREKENG: Jurnal Ilmu Matematika dan Terapan, 7(2), 13-18.

Wiyanti, D. T. (2013). Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem. Jurnal Transformatika, 11(1), 1-6.

Yulianto, E., & Setiawan, A. (2018). Optimasi Rute Sales Coverage Menggunakan Algoritma Cheapest Insertion Heuristic Dan Layanan Google Maps API. INTERNAL (Information System Journal), 1(1), 39-54.

Zulfa, I. (2021). Pengefisiensian Penyaluran Barang dan Rute Pengiriman Ekspedisi JNE dengan Aplikasi Graf. J-SAKTI (Jurnal Sains Komputer dan Informatika), 5(1), 99-109.