Optimasi Rute Pendistribusian Barang Menggunakan Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic
DOI:
https://doi.org/10.21580/square.2024.6.2.22992Abstract
The problem that often occurs in the process of distributing goods is that the distribution route is not optimal which results in higher costs and longer travel times. This can be solved by finding the shortest path that can be passed or widely recognized as the Traveling Salesman Problem (TSP). This study aims to determine the optimal distribution route for goods using a combination of the Branch and Bound and Cheapest Insertion Heuristic algorithms. The data used are in the form of location names and distances between locations that have been collected by Putra BJ Bangun in his research entitled Solving the Traveling Salesman Problem (TSP) with the Branch and Bound Method (Application of the Palembang Post Office Goods Transportation Problem). The results of the research indicate that the optimal route for the distribution of goods at the Palembang City Post Office, using a combination of both algorithms, is: KPRK Palembang → KPC Kapt A. Rivai → KPC Pakjo → KPC Talang Ratu → KPC Sukarami → KPC Alang Lebar → KPC Sekip → KPC Cinde → KPRK Palembang, spanning a total of 24.3 km. This route can be an alternative for salesmen to visit several KPCs and return to KPRK, with more efficient costs and time because it is the shortest route. In addition, this combination of algorithms is more efficient and simpler in terms of processing steps and computing time compared to using the Branch and Bound algorithm.
Keywords: Traveling Salesman Problem (TSP), Branch and Bound, Cheapest Insertion Heuristic, Algorithm Combination, Optimal.
Downloads
References
Anassuka, B., Cholissodin, I., & Rahayudi, B. (2022). Optimasi Rute Multiple Travelling Salesman Problem Distribusi Produk PT Indomarco Adi Prima (Stock Point Nganjuk) menggunakan Algoritme Ant Colony Optimization dan Algoritme Genetika. Jurnal Pengembangan Teknologi Informasi Dan Ilmu Komputer, 6(3), 1290–1297.
Aristi, G. (2014). Perbandingan Algoritma Greedy, Algoritma Cheapest Insertion Heuristics dan Dynamic Programming dalam Penyelesaian Travelling Salesman Problem. Paradigma, 16(2), 52–58.
Auliasari, K., Kertaningtyas, M., & Basuki, D. W. L. (2018). Optimalisasi Rute Distribusi Produk Menggunakan Metode Traveling Salesman Problem. Optimalisasi Rute Distribusi Produk Menggunakan Metode Traveling Salesman Problem, 16(1), 15–23.
Azzahrha, F. K., Sari, R. P., & Fauzi, M. D. R. (2021). Optimalisasi Produksi Tahu Menggunakan Metode Branch and Bound dan Cutting Plane. STRING (Satuan Tulisan Riset Dan Inovasi Teknologi), 6(2), 175–184.
Bangun, P. B. J., Octarina, S., & Purba, B. V. (2015). Penyelesaian Travelling Salesman Problem (TSP) dengan Metode Branch and Bound (Aplikasi Permasalahan Pengangkutan Barang Kantor Pos Palembang). SEMIRATA 2015, 1(1), 399–408.
Hignasari, L. V. (2019). Komparasi Algoritma Cheapest Insertion Heuristic (CIH) dan Greedy dalam Optimasi Rute Pendistribusian Barang. Jurnal Ilmiah Vastuwidya, 2(2), 31–39.
Lakutu, N. F., Mahmud, S. L., Katili, M. R., & Yahya, N. I. (2023). Algoritma Dijkstra dan Algoritma Greedy Untuk Optimasi Rute Pengiriman Barang Pada Kantor Pos Gorontalo. Euler: Jurnal Ilmiah Matematika, Sains Dan Teknologi, 11(1), 55–65.
Lattan, B. W., Tupan, J. M., & Paillin, D. B. (2021). Pemecahan Traveling Salesmen Problem Menggunakan Teknik Branch and Bound dan Cheapest Insertion Heuristic. I Tabaos, 1(1), 13–22.
Mas’ ud, S. (2024). Route Determination for Distribution by Using a Combination of Branch and Bound Algorithm and Cheapest Insertion Heuristic. ARRUS Journal of Mathematics and Applied Science, 4(1), 20–27.
Ningrum, E. R., Sanwidi, A., Akbarita, R., & Qomaruddin, M. N. H. (2023). Optimasi Rute Pendistribusian Gas Elpiji Menggunakan Algoritma Floyd Warshall dan Algoritma Greedy. Jurnal Ilmiah Matematika Dan Terapan, 20(1), 1–14.
Nur, M. A. S., & Rahadjeng, B. (2021). Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic dalam Menyelesaikan Asymmetric Travelling Salesman Problem. MATHunesa: Jurnal Ilmiah Matematika, 9(2), 351–358.
Paillin, D. B., & Sosebeko, F. (2017). Penentuan Rute Optimal Distribusi Produk Nestle Dengan Metode Traveling Salesman Problem (TSP)(Studi Kasus: PT. Paris Jaya Mandiri). Arika, 11(1), 35–44.
Paillin, D. B., & Tupan, J. M. (2018). Pemecahan Travelling Salesman Problem Menggunakan Teknik Branch and Bound dan Cheapest Insertion Heuristic (Studi Kasus: PT. Paris Jaya Mandiri-Ambon). Seminar Dan Konferensi Nasional IDEC 2018 Surakarta 7-8 Mei.
Rahmadi, D., & Sandariria, H. (2023). Penerapan Minimum Spanning Tree dalam Menentukan Rute Terpendek Distribusi Naskah Soal USBN di SMA Negeri se-Sleman. Basis: Jurnal Ilmiah Matematika, 2(1), 66–71.
Rozi, S., & Multahadah, C. (2021). Rute Terpendek untuk Pengangkutan Sampah dengan Pendekatan Lintasan Hamilton. E-Jurnal Matematika, 10(2), 115–121.
Safitri, E., Basriati, S., Widiarti, W., & Sukmawati, S. (2024). Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic dalam Mengoptimalkan Rute Distribusi Kurir Paket JNT di Kecamatan Batang Cenaku. Jurnal Lebesgue: Jurnal Ilmiah Pendidikan Matematika, Matematika Dan Statistika, 5(1), 561–572.
Saleh, K., & Helmi, B. P. (2015). Penentuan Rute Terpendek Dengan Menggunakan Algoritma Cheapest Insertion Heuristic (Studi Kasus: Pt. Wicaksana Overseas International Tbk. Cabang Pontianak). Bimaster: Buletin Ilmiah Matematika, Statistika Dan Terapannya, 4(03), 295–304.
Saputra, D. W. (2022). Optimalisasi Rute Distribusi Kurir Menggunakan Metode Traveling Salesman Problem (Studi Kasus: Jne Balige). G-Tech: Jurnal Teknologi Terapan, 6(2), 159–165.
Sari, M., & Asmendri, A. (2020). Penelitian Kepustakaan (Library Research) dalam Penelitian Pendidikan IPA. Natural Science, 6(1), 41–53.
Sihombing, D. E., & Ahyaningsih, F. (2023). Optimalisasi Rute Distribusi Air Minum Dalam Kemasan Menggunakan Algoritma Genetika Pada PT. Mual Natio Maju Bersama. JURNAL RISET RUMPUN ILMU PENDIDIKAN, 2(1), 70–83.
Sulistiyorini, R., & Mahmudy, W. F. (2015). Penerapan Algoritma genetika untuk Permasalahan Optimasi Distribusi Barang Dua Tahap. DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, 5(12), 1–12.
Usman, M. Z., & Oktiarso, T. (2018). Implementasi Algoritma Greedy Untuk Menyelesaikan Travelling Salesman Problem di Distributor PT. Z. Journal of Integrated System, 1(2), 216–229.
Yuliantari, R., & Musabbikhah, L. (2022). Review Artikel: Analisis Penggunaan Algoritma Dijkstra untuk Mencari Rute Terpendek di Rumah Sakit. Edu Elektrika Journal, 11(1), 1–5.
Downloads
Published
Issue
Section
License
The Authors submitting a manuscript do so on the understanding that if accepted for publication, copyright of the article shall be assigned to Square: Journal of Mathematics and Mathematics Education as the publisher of the journal. The copyright form should be signed originally and send to the Editorial Office in the form of original mail, scanned document to [email protected]
Square : Journal of Mathematics and Mathematics Education by Mathematics Department UIN Walisongo Semarang is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
