Penyelesaian TSP Distribusi LPG dengan Algoritma Nearest Neighbor dan Insertion
DOI:
https://doi.org/10.55826/jtmit.v4i3.790Keywords:
Traveling Salesman Problem (TSP), Distribusi, Nearest Neighbour, Insertion, Penentuan RuteAbstract
PT XYZ merupakan perusahaan penyedia energi gas, khususnya Liquified Petroleum Gas (LPG), yang mendistribusikan produknya ke berbagai wilayah di Kalimantan Timur, termasuk Samarinda. Namun, proses distribusi masih belum efisien karena penentuan rute pengiriman bergantung pada pengalaman supir tanpa perencanaan sistematis, sehingga mengakibatkan jarak tempuh dan biaya operasional yang tinggi. Penelitian ini bertujuan mengoptimalkan rute distribusi LPG dengan menerapkan algoritma Nearest Neighbor dan Insertion untuk meminimalkan jarak tempuh dan biaya bahan bakar. Data jarak antarlokasi diperoleh melalui Google Maps dan diolah dalam bentuk matriks jarak sebelum dihitung menggunakan kedua algoritma. Hasil menunjukkan bahwa algoritma Nearest Neighbor menghasilkan total jarak tempuh 574,61 km, memotong jarak sebesar 40,98 km (6,657%) dari jarak awal 615,59 km, dengan biaya bahan bakar Rp1.869.193,01 dan penghematan Rp133.306,99. Sementara itu, algoritma Insertion memberikan hasil lebih optimal dengan jarak 524,05 km, pengurangan 91,54 km (14,870%), serta biaya bahan bakar Rp1.704.722,50 dan penghematan sebesar Rp297.777,50. Dengan demikian, algoritma Insertion terbukti lebih efektif dalam menyelesaikan permasalahan Traveling Salesman Problem (TSP) pada distribusi LPG, serta berkontribusi dalam meningkatkan efisiensi operasional dan keandalan distribusi LPG di PT XYZ.
References
R. Sayyida dan S. Akhmaddhian, “Penegakan Hukum terhadap Pelaku Tindak Pidana Pengoplos Tabung Gas LPG Bersubsidi,” Log. J. Multidiscip. Stud., vol. 13, no. 01, hal. 1–7, 2022, doi: 10.25134/logika.v13i01.2558.
M. A. Prasetyo dan N. Paramytha, “Pengembangan Sistem Pendeteksi Kebocoran Gas LPG dengan Teknologi IoT dan Sensor MQ5,” J. Ampere, vol. 8, no. 2, hal. 103–115, 2023, doi: 10.31851/ampere.v8i2.9240.
M. Z. Arifin, B. T. Meitasari, A. D. Akmal, dan Y. Amrozi, “Konfigurasi Jaringan Supply Chain Pada Distribusi Gas Lpg 3 Kg Di Indonesia,” JITMI, vol. 4, no. 1, hal. 1–9, 2021, [Daring]. Tersedia pada: www.edm.go.id
A. Rozalina, S. Uslianti, dan P. Anggela, “Optimasi Rute Distribusi Dengan Penyelesaian Vehicle Routing Problem Menggunakan Algoritmasweep Pada Pd.Xyz Di Pontianak,” J. Tek. Ind. Univ. Tanjungpura, vol. 4, no. 1, hal. 45–50, 2020.
M. A. Aulia, L. S. Fajhriana, F. Aziz, dan M. Fauzi, “Perencanaan Distribusi Produk Gas Pt.Rebbak Trolih Lestari Menggunakan Metode Distribution Requirement Planning (Drp),” J. Bayesian J. Ilm. Stat. dan Ekon., vol. 2, no. 1, hal. 1–14, 2022, doi: 10.46306/bay.v2i1.12.
T. Juniarto, F. Mawasandi, dan hmad N. Faiz, “PERMASALAHAN TRAVELLING SALESMAN PROBLEM PENGIRIMAN PAKET PADA PERUSAHAAN EKSPEDISI XYZ DI KOTA PALEMBANG,” J. Transform. Hum., vol. 7, no. 7, hal. 39–52, 2024.
S. Kristina, R. D. Sianturi, dan R. Husnadi, “Penerapan Model Capacitated Vehicle Routing Problem (CVRP) Menggunakan Google OR-Tools untuk Penentuan Rute Pengantaran Obat pada Perusahaan Pedagang Besar Farmasi (PBF),” J. Telemat., vol. 15, no. 2, hal. 101–106, 2021, doi: 10.61769/telematika.v15i2.359.
I. A. Setiani dan Lukmandono, “Optimasi Rute Distribusi Obat Untuk Meminimalkan Biaya Transportasi Dengan Menggunakan Metode Saving Matrix,” Semin. Nas. Sains dan Teknol. Terap., hal. 87–94, 2021.
B. R. Christata dan R. Primadasa, “PENENTUAN RUTE PENGIRIMAN ES BATU MENGGUNAKAN NEAREST NEIGHBOR DAN EXCEL SOLVER,” Jointech Umk, vol. 1, no. 1, hal. 11–17, 2020.
R. P. Sinaga dan F. Marpaung, “Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem,” J. Ris. Rumpun Mat. Dan Ilmu Pengetah. Alam, vol. 2, no. 2, hal. 238–247, 2023, doi: 10.55606/jurrimipa.v2i2.1614.
W. A. F. B dan S. Rosnafi, “Product Distribution Route using Nearest Neighbor Algorithm Rute Pendistribusian Barang dengan Algoritma Nearest Neighbor,” vol. 4, no. July, hal. 894–900, 2024.
R. S. Utami, R. Arifin, R. D. Lufika, R. Dio, dan H. Vicarlo, “Penerapan Algoritma Evolutionary dan Nearest Neighbor untuk Optimasi Rute Distribusi,” vol. 05, no. 02, hal. 84–93, 2024.
S. Rohman, L. Zakaria, A. Asmiati, dan A. Nuryaman, “Optimisasi Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT. Pos Indonesia di Kota Bandar Lampung,” J. Mat. Integr., vol. 16, no. 1, hal. 61, 2020, doi: 10.24198/jmi.v16.n1.27804.61-73.
S. Martono dan H. L. H. S. Warnars, “Penentuan Rute Pengiriman Barang Dengan Metode Nearest Neighbor,” Petir, vol. 13, no. 1, hal. 44–57, 2020, doi: 10.33322/petir.v13i1.869.
D. S. Oetomo, R. F. Ramdhani, dan A. P. Abdi, “Penentuan Rute Pengiriman Produk Dengan Meminimalkan Biaya Transportasi Menggunakan Metode Saving Matrik Dan Nearest Neighbour Di Pt. Aisyah Berkah Utama,” J. Sains dan Teknol. J. Keilmuan dan Apl. Teknol. Ind., vol. 22, no. 1, hal. 130–145, 2022, doi: 10.36275/stsp.v22i1.477.
V. A. Perdana, Z. F. Hunusalela, dan A. T. Prasasty, “Penerapan Metode Saving Matrix Dan Algoritma Nearest Neighbor Dalam Menentukan Rute Distribusi Untuk Meminimalkan Biaya Transportasi Pada PT. XYZ,” J. Ilm. Tek. dan Manaj. Ind. Univ. Kadiri (JATI UNIK), vol. 4, no. 2, hal. 91–105, 2021.
Suparmi, H. Suyitno, dan I. Rosyida, “Pengoptimalan Rute Distribusi Produk Menggunakan Metode Saving Matrix Dan Nearest Insertion,” UNNES J. Math., vol. 9, no. 2, hal. 49–57, 2020, [Daring]. Tersedia pada: http://journal.unnes.ac.id/sju/index.php/ujmUJM9
P. Lestari, A. Hasibuan, dan B. Harahap, “Analisis Penentuan Rute Distribusi menggunakan Metode Nearest Neighbor di PT Medan Juta Rasa Tanjung Morawa,” Fact. J. Ind. Manaj. dan Rekayasa Sist. Ind., vol. 1, no. 1, hal. 26–32, 2022, doi: 10.56211/factory.v1i1.110.
N. Nurjanah, H. Setiadi, dan M. Azizah, “Penentuan Rute Distribusi Produk Pangan Komersial Pada Perusahaan Xyz Menggunakan Metode Saving Matrix,” J. Logistik Bisnis, vol. 12, no. 02, hal. 38–41, 2022, [Daring]. Tersedia pada: https://ejurnal.poltekpos.ac.id/index.php/logistik/index
W. A. F. B, S. Rosnafi, N. N. Sari, dan J. E. Simarmata, “Product Distribution Route using Nearest Neighbor Algorithm Rute Pendistribusian Barang dengan Algoritma Nearest Neighbor,” MALCOM Indones. J. od Mach. Learn. Comput. Sci., vol. 4, no. 3, hal. 894–900, 2024.
B. H. Purnomo, N. N. Novijanto, dan C. W. Ramadhan, “Analisis rute distribusi dengan jarak tempuh terpendek pada produk air mineral dalam kemasan (AMDK) (studi kasus CV. XYZ),” Agrointek J. Teknol. Ind. Pertan., vol. 17, no. 3, hal. 674–683, 2023, doi: 10.21107/agrointek.v17i3.15862.
M. V. Andriansyah, R. A. Darajatun, dan D. N. Rinaldi, “Optimalisasi Pendistribusian Dengan Metode Travelling Salesman Problem Untuk Menentukan Rute Terpendek Di Pt Xyz,” Tekmapro J. Ind. Eng. Manag., vol. 16, no. 2, hal. 84–95, 2021, doi: 10.33005/tekmapro.v16i2.264.
M. A. S. Nur dan B. Rahadjeng, “Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic dalam Menyelesaikan Asymmetric Travelling Salesman Problem,” MATHunesa J. Ilm. Mat., vol. 9, no. 2, hal. 351–358, 2021, doi: 10.26740/mathunesa.v9n2.p351-358.
A. Yustavia, L. L. Salomon, dan H. J. Kristina, “Analisis Penentuan Rute Distribusi Optimal Dengan Pendekatan Manajemen Transportasi Dan Distribusi Di Cv. Expedisi Mitra Mandiri,” J. Mitra Tek. Ind., vol. 1, no. 2, hal. 126–134, 2022, doi: 10.24912/jmti.v1i2.21248.
L. E. Marpaung, J. Arifin, dan W. Winarno, “Optimalisasi Rute Distribusi Menggunakan Algoritma Clarke and Wright Savings,” J. Media Tek. dan Sist. Ind., vol. 6, no. 2, hal. 76, 2022, doi: 10.35194/jmtsi.v6i2.1784.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Jasmine Najwa Raihana, Wahyuda, Ridzky Zul Asdi
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
