PENENTUAN JALUR DISTRIBUSI PADA TRAVELING SALESMAN PROBLEM (TSP) DENGAN ALGORITMA BRANCH AND BOUND DAN NEAREST NEIGHBOUR UNTUK MENGOPTIMALKAN BIAYA TRANSPORTASI DI UMKM BOLEN CRISPY MAK TIN
DOI:
https://doi.org/10.59024/jisi.v3i2.1171Keywords:
Traveling Salesman Problem (TSP), Distribution, Branch and Bound Algorithm, Nearest Neighbor, Transportation CostsAbstract
Optimizing distribution routes is an important step for MSMEs in increasing operational efficiency and customer satisfaction. This research was conducted on Bolen Crispy Mak Tin MSMEs which face distribution challenges with routes that are not yet optimal, causing increased transportation costs and the risk of decreasing product quality. This research uses the Branch and Bound and Nearest Neighbor algorithms to solve the Traveling Salesman Problem (TSP) problem in determining efficient distribution routes. The results of data processing are optimal routes that have the minimum distance with a total distance of 282.5 KM with route P-1-2-7-4-5-6-3-0 for the branch and Bound algorithm and 239 km with route P- 2-3-4-5-6-7-1-P for Nearest Neighbor This result is more optimal when compared to the previous route, namely P-1-2-3-4-5-6-7-P with a distance of 291 km analysis shows that Method Nearest Neighbor is able to provide an optimal solution by minimizing travel distance and distribution costs, while the Branch and Bound algorithm also provides an optimal solution but is less efficient. and distribution cost efficiency from Rp. 570,320.9 to 565,511.36 or 0.84% more savings for the Branch and Bound Algorithm and 540,795.45 or 5.18% more savings for Nearest Neighbor
References
Ardiansyah, M. V., Darajatun, R. A., & Rinaldi, D. N. (2021). Optimalisasi Pendistribusian Dengan Metode Travelling Salesman Problem Untuk Menentukan Rute Terpendek Di Pt Xyz. Tekmapro: Journal of Industrial Engineering and Management, 16(2), 84-95.Journal of Industrial Engineering and Management.
Anjani, A. (2021). Apa yang Dimaksud Distribusi? Ini Pengertian dan Tujuannya. detikedu, diakses, 15. for the Dubins Travelling Salesman Problem’. Journal of Heuristic, 503-530.
Chandra, Novilia Eka. (2020). ‘Penerapan Metode Branch and Bound Pada Penyelesaian Masalah Traveling Salesman Problem (TSP)’. Skripsi Sarjana Univeritas Negeri Jakarta.
Christata, B.R., & Primadasa, R. (2023). ‘Penentuan Rute Pengiriman Es Batu Menggunakan Nearest Neighbor Dan Excel Solver’. Journal Of Industrial Engineering And Technology (Jointech) Universitas Muria Kudus (Vol. 3, No. 2).
Ekawati, R., & Arkeman, Y. (2020). ‘Traveling Salesman Problem in The Case of Refined Sugar Shipment From Distribution Centers For the beverage Industries’. Journal Industrial Servicess (Vol. 6, No. 1).
S., Syafilin, I.A.S., & Fauzi, M. (2021). ‘Traveling Salesman Problem Analysis With Enumeration Method, Branch & Bound and Greedy Heuristic’. Journal of Universal Studies (Vol. 1, No. 8).
Harianja, Salamah Fitriani. (2021). ‘Nilai Total Ketakteraturan Titik Dari Graf Seri Paralel (m, 1, 5)’. Tugas Akhir Sarjana, Universitas Islam Negeri Sultan Syarif Kasim Riau.
Hidayat, A., & Irvanda, M. (2022). ‘Optimalisasi Penyusunan dan Pembuatan Laporan Untuk Mewujudkan Good Covernance’. Jurnal Hospitality (Vol. 11, No.1).
Juliani, & Hamrul, H. (2022). ‘Optimasi Distribusi Buku menggunakan Algoritma Branch and Bound untuk Efisiensi Rute Terpendek’. Journal of Computer and Informasi System (J-CIS) (Vol. 5, No. 2).
Amelia, K., Reza, R., & Ellyawati, N. (2022). Pengaruh Biaya Promosi dan Biaya Distribusi Terhadap Volume Penjualan PT. Martina Berto Periode 2011-2020. Jurnal Promosi Program Studi Pendidikan Ekonomi, 10(2).
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). In Seminar dan Konferensi Nasional IDEC 2018 Surakarta 7-8 Mei.
Ahmad, M., Aspriyani, R., & Ma’rifah, U. (2023, December). Shortest Route For Distribusion of Election Logistic in Cilacap Regency Using The Branch and Bound Algorithm. In Proceeding Al Ghazali International Conference (Vol. 1, pp. 229-241).
Sitanggang, F. A. A., & Napitupulu, N. (2023). Implementation of Branch and Bound Algorithm to Solve the Travelling Salesman Problem at PT Jasa Harapan Barat. JMEA: Journal of Mathematics Education and Application, 2(3), 152-158.
Moriza, D., Adianto, H., & Nurdiansyah, Y. (2016). Rute Pendistribusian Air Mineral Dalam Kemasan Menggunakan Metode Nearest neighbour dan Branch and bound Di PT. Agronesia Bmc. Reka Integra, 4(2).
Wulandari, C. B. K. (2020). Penentuan Rute Distribusi Menggunakan Metode Nearest Neighbors dan Metode Branch and Bound untuk Meminimumkan Biaya Distribusi di PT. X. Jurnal Optimasi Teknik Industri (JOTI), 2(1), 7-12.
Wisudawati, N., Valentine, A., & Patradhiani, R. (2022). Usulan Perbaikan Rute Pengangkutan Sampah Menggunakan Metode Branch And Bound Dan Nearest Neighbour Untuk Meminimalkan Biaya Transportasi. Jurnal Teknik Industri: Jurnal Hasil Penelitian dan Karya Ilmiah dalam Bidang Teknik Industri, 8(2), 288-294.
Widiarti, Winda. (2023). ‘Optimasi Rute Distribusi Kurir Paket JNT Di Kecamatan Batang Cenaku Menggunakan Kombinasi Algoritma Branch And Bound Dan Cheapest Insertion Heuristic’. Skripsi Sarjana Universitas Islam Negeri Sultan Syarif Kasim Riau Pekanbaru
Wulansari, T., Aditya, A. M., & Fauzi, M. (2020). ‘Penentuan Rute Optimal Distribusi Paving Block dengan Metode Branch and Bound’. Jurnal Hasil Penelitian dan Karya Ilmiah dalam Bidang Teknik Industri(Vol. 6, No. 2).
Zupemungkas, H.O., & Handayani, W. (2021). ‘Optimalisasi Rute Distribusi Menggunakan Metode Traveling Salesman Problem (TSP) Untuk Meminimasi Biaya Distribusi’. Jurnal Ekonomi dan Bisnis (Vol. 8, No. 2).
Downloads
Published
Issue
Section
License
Copyright (c) 2025 JURNAL ILMIAH TEKNIK INDUSTRI DAN INOVASI

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.