Implementasi Algoritma Lin Kernighan Helsgaun Untuk Menentukan Jarak Terpendek Dalam Sistem Pengantaran Pos Di Kecamatan Mariso
DOI:
https://doi.org/10.57250/ajst.v3i2.1785Kata Kunci:
Algoritma, Lin-Kernighan-Helsgaun, optimasi rute, pengiriman pos, Travelling Salesman Problem, efisiensi logistikAbstrak
Dalam industri jasa pengiriman, efisiensi rute pengantaran merupakan faktor utama dalam meningkatkan kecepatan dan menekan biaya operasional. PT Pos Indonesia sebagai penyedia layanan pengiriman menghadapi tantangan dalam menentukan rute optimal bagi kurirnya, terutama di wilayah perkotaan yang memiliki jaringan jalan kompleks seperti Kecamatan Mariso. Penelitian ini bertujuan untuk mengimplementasikan Algoritma Lin-Kernighan-Helsgaun (LKH) dalam optimasi rute pengiriman pos guna memperoleh rute terpendek yang lebih efisien dibandingkan metode konvensional.Penelitian ini menggunakan data geografis dan pemetaan wilayah Kecamatan Mariso untuk membangun model graf berbobot. Jarak antar titik dihitung menggunakan Rumus Haversine, kemudian diterapkan Algoritma LKH untuk menemukan rute optimal. Hasil simulasi menunjukkan bahwa algoritma ini mampu mengurangi total jarak tempuh pengiriman dibandingkan dengan metode manual yang biasa digunakan kurir. Implementasi Algoritma LKH menghasilkan efisiensi dalam distribusi paket, mengurangi waktu perjalanan, serta menekan biaya operasional yang berhubungan dengan bahan bakar dan tenaga kerja. Dengan hasil yang diperoleh, penelitian ini diharapkan dapat memberikan kontribusi dalam pengembangan sistem logistik PT Pos Indonesia, serta menjadi referensi dalam optimasi rute pada bidang transportasi dan distribusi.
Referensi
Buhaerah, Busrah, Z., & Sanjaya, H. (2019). Teori Graf dan Aplikasinya. In Living Spiritual Quotient.
Dendi, M., Santoso, A., Daru Kusuma, P., & Ningsih, C. S. (2021). Pemilihan Rute Terpendek Pasien Untuk Penanganan Covid-19 Di Jakarta Menggunakan Algoritma Steepest Ascent Hill Climbing Shortest Route Selection of Patients for Handling Covid-19 in Jakarta Using Steepest Ascent Hill Climbing Algorithm. Jurnal Teknik Informatika, 8(5), 6402–6410.
Informatika, J., & Informasi, S. (2023). INFORMASI (Jurnal Informatika dan Sistem Informasi) Volume 15 No.1 / Mei / 2023. 15(1), 70–80.
Khaedar, M., Supardi, R., & Alam, S. (2020). DIKDAS MATAPPA : Jurnal Ilmu Pendidikan Dasar. Jurnal Ilmu Pendidikan Dasar, 3(April), 794–800.
Melladia. (2020). Algoritma Genetika Menentukan Jalur Jalan dengan Lintasan Terpendek (Shortest Path). Prosiding Seminar Nasional Sistem Informasi Dan Teknologi (SISFOTEK), 4(1), 112–117.
Nur Sabila, S., Subarno, A., & Susantiningrum, S. (2023). Penerapan i-pos dalam meningkatkan pelayanan pelanggan di PT Pos Indonesia Wilayah Surakarta. JIKAP (Jurnal Informasi Dan Komunikasi Administrasi Perkantoran), 7(6), 487. https://doi.org/10.20961/jikap.v7i6.65910
Pipit Muliyah, Dyah Aminatun, Sukma Septian Nasution, Tommy Hastomo, Setiana Sri Wahyuni Sitepu, T. (2020). 済無No Title No Title No Title. Journal GEEJ, 7(2), 4–8.
Prasetyo, Y. D. (2017). Penyelesaian Travelling Salesman Problem Dengan Algoritma Branch and Bound. Jurnal MATEMATICS PAEDAGOGIC, I(2), 162–168. www.jurnal.una.ac.id/indeks/jmp
Rahayu, C. S., Gata, W., Rahayu, S., Salim, A., & Budiarto, A. (2021). Penerapan Algoritma Dijkstra Dalam Penentuan Lintasan Terpendek Menuju Upt. Puskesmas Cilodong Kota Depok. Jurnal Teknik Informatika, 14(1), 81–92. https://doi.org/10.15408/jti.v14i1.18721
Simarmata, J. E. (2020). Penerapan Algoritma Branch and Bound Pada Persoalan Pedagang Keliling (Travelling Salesman Problem). RANGE: Jurnal Pendidikan Matematika, 1(2), 111–121. https://doi.org/10.32938/jpm.v1i2.366
Sisi, D. U. A., Pada, O., Es, P. T., & Boyolali, M. (2019). MENYELESAIKAN TRAVELLING SALESMAN PROBLEM DENGAN METODE. 8(1).
Sudaryana, Y. (2020). Pengaruh Kualitas Pelayanan, Kepercayaan Dan Harga Terhadap Kepuasan Konsumen Pada Kantor Pos Indonesia (Persero) Kota Tangerang. Journal of Management Review, 4(1), 447–455.
Syihabuddin, R. F., Jauhari, M. N., Khudzaifah, M., & Fahmi, H. (2022). Implementasi Algoritma A-Star dalam Menentukan Rute Terpendek Destinasi Wisata Kota MalSyihabuddin, R. F., Jauhari, M. N., Khudzaifah, M., & Fahmi, H. (2022). Implementasi Algoritma A-Star dalam Menentukan Rute Terpendek Destinasi Wisata Kota Malang. Jurn. Jurnal Riset Mahasiswa Matematika, 1(5), 236–245.
Tani, F., Warsito, A., & Lapono, L. A. S. (2022). Kajian Optimasi Rute Terpendek Menggunakan Metode Simulated Annealing untuk Distribusi Obat pada Jaringan Apotek Kimia Farma di Kota Kupang. Magnetic: Research Journal Of Physics and It’s Application, 2(2), 179–187.
Winarta, L. M. A., Daru Kusuma, P., & Setianingsih, C. (2021). Analisa Sistem Pencarian Jalur Pada Aplikasi Panggilan Darurat Menggunakan Algoritma A* (A STAR) dan PRIM Routing. 8(6), 11901–11908.
Zahra, A., Herawaty, T., & Muttaqin, Z. (2024). Pengembangan Kualitas Pelayanan Jasa Pengiriman Barang pada PT Pos Indonesia (Persero) KCU Bandung. Jurnal Administrasi Bisnis (JAB), 14(1), 95–103.
Zheng, J., He, K., Zhou, J., Jin, Y., & Li, C. M. (2021). Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem. 35th AAAI Conference on Artificial Intelligence, AAAI 2021, 14A, 12445–12452. https://doi.org/10.1609/aaai.v35i14.17476
