Optimasi Traveling Salesman Problem (TSP) Menggunakan Algoritma Genetika dan Google Maps API untuk Kurir Ekspedisi pada J&T Paris 2 Berbasis Web GIS

Gusti Muhamad Adzaky Gusti; Rachmat Wahid Saleh Insani; Sucipto

doi:10.23887/insert.v4i2.68223

Authors

Gusti Muhamad Adzaky Gusti Universitas Muhammadiyah Pontianak
Rachmat Wahid Saleh Insani Universitas Muhammadiyah Pontianak
Sucipto Universitas Muhammadiyah Pontianak

DOI:

https://doi.org/10.23887/insert.v4i2.68223

Keywords:

Traveling Salesman Problem, Algoritma Genetika, Optimasi Rute, Maps Api, Matriks Jarak

Abstract

Kurir, sebagai elemen vital dalam proses pengiriman, memiliki tanggung jawab penting dalam menjaga kelancaran operasi ekspedisi dengan mengirim barang secara cepat dan efisien. Mereka sering dihadapkan pada tantangan menentukan rute optimal, terutama saat mengirim barang ke berbagai alamat di area luas. Kondisi ini dapat menyebabkan pemborosan waktu dan bahan bakar. Oleh karena itu, peneliti menghubungkan permasalahan ini dengan Traveling Salesman Problem (TSP) dan mendapati bahwa algoritma genetika merupakan solusi efektif. Penelitian ini berfokus pada studi kasus konkret, J&T Paris 2, dan bertujuan mengimplementasikan solusi berbasis web untuk membantu kurir menentukan rute pengiriman yang efisien dengan memanfaatkan teknologi informasi. Metodologi penelitian mencakup identifikasi masalah, pengumpulan data lokasi tujuan, pengolahan data dengan algoritma genetika, dan desain sistem Web GIS. Hasilnya mencakup berbagai fitur dalam pengoptimalan rute, seperti dashboard, estimasi biaya, CRUD data kelompok, titik pengantaran, pembobotan, dan hasil rute terbaik dengan algoritma genetika. Untuk mengoptimasi rute perjalanan kurir, dan menghasilkan runing time(waktu eksekusi) yang optimal. Peneliti melakukan 6 kali percobaan, dengan estimasi biaya 1 kilometernya sebesar Rp. 1200 menggunakan data Kelompok Antar Area Pontianak Tenggara (Kurir Dimas) dengan Parameter Algoritma Genetika. Eksperimen menunjukkan bahwa sistem ini mencapai kinerja optimal pada eksperimen nomor 3, menghasilkan total jarak perjalanan sekitar 10.524 kilometer dengan estimasi biaya sebesar Rp. 12.031. Pengujian juga memvalidasi fungsi-fungsi sistem, termasuk login, pengubahan data estimasi biaya pengguna, CRUD kelompok, CRUD titik pengantaran, pembobotan, perhitungan, dan penghapusan data. Kesimpulannya, implementasi Web GIS berhasil memenuhi kebutuhan dalam penyimpanan data dan penentuan lintasan terpendek, mengoptimasi TSP dengan algoritma genetika dan Google Maps API. Sistem ini efisien dan efektif dalam mengatasi permasalahan pengantaran oleh kurir.

References

Auliasari, K., Kertaningtyas, M., & Basuki, D. W. L. (2018). Optimalisasi Rute Distribusi Produk Menggunakan Metode Traveling Salesman Problem. Jurnal Sains, Teknologi Dan Industri, 16(1), 15. https://doi.org/10.24014/sitekin.v16i1.6109

C, A. P., Pramono, B., & Aksara, L. . B. (2017). Travelling Salesman Problem (TSP) Untuk Menentukan Rute Terpendek Bagi Kurir Kota Kendari Menggunakan Algoritma Greedy Berbasis Android. SemanTIK, 3(1), 95–106.

Hijriana, N. (2015). Penerapan Metode Algoritma Genetika Untuk Permasalahan Penjadwalan Perawat (Nurse Schedulling Problem). Info Teknik, 16(1), 61–74.

Jinggo Pratama, A. S., Abdul Khamid, & Yesy Diah Rosita. (2023). Pencarian Rute Optimal Wisata Mojokerto Dalam Kasus Traveling Salesman Problem Menggunakan Algoritma Genetika. Jurnal Informatika Teknologi Dan Sains (Jinteks), 5(2), 283–288. https://doi.org/10.51401/jinteks.v5i2.2447

Kamelia, R. (2023). Profil Kota Pontianak: Sejarah, Geografi, Peta, dan Iklim. https://tirto.id/profil-kota-pontianak-sejarah-geografi-peta-dan-iklim-gAzw

Nadzir, M., Cholissodin, I., & Rahayudi, B. (2019). Penerapan Multi Travelling Salesman Problem Pada Optimasi Pendistribusian Bantuan Sosial Beras Sejahtera Studi Kasus: Perum Bulog Subdivre Malang. Jurnal Pengembangan Teknologi Informasi Dan Ilmu Komputer, 3(3), 2894–2902.

Nugroho, I. S., Bhagya, T. G., & Rosinawati, D. (2020). Genetic Algorithm Untuk Memperbaiki Rute Travelling Salesman Problem Yang Dihasilkan Dari Savings Algorithm. Jurnal Sain Dan Teknik, 2(2), 58–71.

Pitaloka, D. K., & Koesdijarto, R. (2022). IMPLEMENTASI TRAVELLING SALESMAN PROBLEM ( TSP ) DENGAN ALGORITMA GENETIKA MENGGUNAKAN PETA LEAFLET ( Studi Kasus PT . AMZ Geoinfo Solution Surabaya ). 1(September), 767–776.

Rizki, Pratama, R., Rintho, Rerung, R., & Erfina, A. (2020). PENYELESAIAN TRAVELLING SALESMAN PROBLEM MENGGUNAKAN ALGORITMA GENETIKA. Jurnal Sistem Informasi Dan Teknologi Informasi, 2(1), 10–18.

Rohman, S., Zakaria, L., Asmiati, A., & Nuryaman, A. (2020). Optimisasi Travelling Salesman Problem dengan Algoritma Genetika pada Kasus Pendistribusian Barang PT. Pos Indonesia di Kota Bandar Lampung. Jurnal Matematika Integratif, 16(1), 61. https://doi.org/10.24198/jmi.v16.n1.27804.61-73

Santoso, H., & Sanuri, R. (2019). Implementasi Algoritma Genetika dan Google Maps API Dalam Penyelesaian Traveling Salesman Problem with Time Window (TSP-TW) Pada Penjadwalan Rute Perjalanan Divisi Pemasaran STMIK El Rahma. Teknika, 8(2), 110–118. https://doi.org/10.34148/teknika.v8i2.187

Yusron Mubarok, A., & Chotijah, U. (2021). Penerapan Algoritma Genetika Untuk Mencari Optimasi Kombinasi Jalur Terpendek Dalam Kasus Travelling Salesman Problem. Jurnal Teknologi Terpadu, 7(2), 77–82. https://doi.org/10.54914/jtt.v7i2.424