Aplikasi Android Untuk Mencari Jalur Tercepat Pada Pengiriman Barang Dengan Algoritma Held-Karp

  • Alfin H Politeknik Caltex Riau
  • Kartina Diah Kesuma Wardhani Politeknik Caltex Riau
Keywords: Pengiriman Barang, Traveling Salesman Problem, Algoritma Held-Karp


The total number of shipments to be sent from 2017 with an average total of 18 million shipments per month until 2018 reaches 24 million per month, while the process the shipping path is still as described and guessing, so couriers often wrong in estimating the fastest route or forgetting to order delivery based on previous couriers which cause the courier to have to turn around and every time the courier turns back then the shipping process becomes ineffective in terms of time, distance and cost. Based on the results of a 2018 study, Held-Karp produced a better route than Iterative Deepening Search in finding a shipping route. Therefore an Android-based application is created and uses the Google Maps API to determine the time, distance, and cost required at each point of delivery, as well as using the Held-Karp algorithm to search for the fastest path based on time, distance and cost. Based on functionality testing the application is estimated to run correctly and per the expected function, then in cyclometric complexity testing, the Held-karp algorithm is categorized in well-written and structured code and high testability because there is no v (G) above 10.


Download data is not yet available.


A. A. N. Hidayat, "2019, JNE Targetkan Pengiriman 1 Juta Paket Tiap Hari," 9 Desember 2018. [Online]. Available: https://bisnis.tempo.co/read/1153712/2019-jne-targetkan-pengiriman-1-juta-paket-tiap-hari/full&view=ok.

W. Alfarisi, "PENCARIAN JALUR TERPENDEK PENGIRIMA N BARANG," Jurnal Riset Komputer (JURIKOM), pp. 90-95, 2016.

I. G. S. Rahayuda and N. P. Linda Santiari, "Penerapan Pemrograman Dinamis Pada Manajemen Pengiriman Produk Menggunakan Metode Held-Karp," E-Proceedings KNS&I STIKOM Bali, pp. 513-518, 2017.

A. R. Amin, M. Ikhsan and L. Wibisono, Traveling Salesman Problem, Bandung: Institut Teknologi Bandung, 2012.

C. Chekuri, "Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time," 58th Annual IEEE Symposium on Foundations of Computer Science, pp. 789-800, 2017.

I. G. S. Rahayuda and N. P. Linda Santiari, "Implementasi dan Perbandingan Metode Iterative Deepening Search dan Held-Karp pada Manajemen Pengiriman Produk," Open Access Journal Of Information System (OAJIS), pp. 131-149, 2018.

Megariza, "Penentuan Rute Belanja dengan TSP dan Algoritma Greedy," Makalah IF3051 Strategi Algoritma, 2011.

R. Munir, Matematika Diskrit, Revisi Kelima., Bandung: Informatika., 2012.

I. ECMA, "“The JSON Data Interchange Format.”," ECMA International 2st Edition(December):16., 2017.

"softwaretestingfundamentals," 2019. [Online]. Available: http://softwaretestingfundamentals.com/black-box-testing/.

R. M. Patelia and S. Vyas, "A Review and Analysis on Cyclomatic Complexity," ORIENTAL JOURNAL OF COMPUTER SCIENCE & TECHNOLOGY, pp. 382-384, 2014.

How to Cite
A. H and K. Wardhani, “Aplikasi Android Untuk Mencari Jalur Tercepat Pada Pengiriman Barang Dengan Algoritma Held-Karp”, JAIC, vol. 4, no. 2, pp. 101-106, Sep. 2020.