Algoritma Tabu Search untuk Graf Optimasi Rute Pengiriman Barang

Rowina Windiyani Heryana; Didi Suhaedi

doi:10.29313/jrm.v4i2.5063

Authors

Rowina Windiyani Heryana Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Islam Bandung
Didi Suhaedi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Islam Bandung

DOI:

https://doi.org/10.29313/jrm.v4i2.5063

Keywords:

Algoritma Tabu Search, Optimisasi, Rute Pengiriman Barang

Abstract

Abstrak. Dalam industri jasa ekspedisi, efisiensi rute pengiriman barang sangat penting untuk menekan biaya operasional dan meningkatkan kepuasan pelanggan. Dengan meningkatnya volume pengiriman akibat tren belanja online, optimasi rute pengiriman menjadi masalah yang krusial. Penelitian ini menggunakan data lokasi pengiriman barang pada satu hari pengiriman dengan lima titik pengiriman yang diolah dengan algoritma Tabu Search untuk mengatasi masalah optimasi rute pengiriman barang. Algoritma ini dipilih karena menggunakan memori tabu yang menyimpan solusi sebelumnya dan mencegah perulangan. Selain itu, algoritma Tabu Search dapat menghasilkan solusi yang optimal dengan adanya pertukaran dua vertex secara berurutan pada tiap iterasinya. Masalah rute pengiriman barang direpresentasikan dalam bentuk graf, dengan setiap simpul (vertex) mewakili lokasi pengiriman dan setiap sisi (edge) mewakili rute dengan bobot tertentu yang mewakili total jarak tempuh. Hasil penelitian ini menunjukkan bahwa algoritma Tabu Search dapat mengoptimalkan total jarak tempuh sebanyak 1,71%. Hal ini dapat memberikan rekomendasi rute pengiriman dengan total jarak tempuh minimum untuk jasa ekspedisi.

Abstract. In the shipping industry, the efficiency of shipping routes is very important to reduce operational costs and increase customer satisfaction. With the increasing volume of shipments due to the trend of online shopping, optimization of shipping routes becomes a crucial problem. This study uses data on shipping locations on one shipping day with five shipping points processed by the Tabu Search algorithm to solve the problem of shipping route optimization. This algorithm was chosen because it uses tabu memory that stores previous solutions and prevents repetition. In addition, the Tabu Search algorithm can produce optimal solutions by exchanging two vertices sequentially in each iteration. The problem of shipping routes is represented in the form of a graph, with each vertex representing a shipping location and each edge representing a route with a certain weight representing the total distance traveled. The results of this study indicate that the Tabu Search algorithm can optimize the total distance traveled by 1.71%. This can provide recommendations for shipping routes with a minimum total distance traveled for shipping services.

References

I. Berlianty and M. Arifin, Teknik-Teknik Optimasi Heuristik, 1st ed. Yogyakarta: Penerbit Graha Ilmu, 2010.

F. E. Pradhana, E. Sugiharti, and M. Kharis, “Penerapan Algoritma Tabu Search untuk Menyelesaikan Vehicle Routing Problem,” UNNES Journal of Mathematics, vol. 1, no. 1, 2012.

A. Yulmasari, “Minimasi Biaya Distribusi Dengan Menggunakan Metode Traveling Salesman Problem (TSP),” Prosiding Seminar Nasional Sains dan Teknologi, 2017.

D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study, vol. 17. Princeton University Press, 2007.

L. Ariyanti, “Implementasi Ant Colony Optimization untuk Optimasi Rute Terpendek pada Pengiriman Barang di Kantor J&T Kota Jambi,” Universitas Jambi, Jambi, 2023.

A. Segev, “A Global Heuristic For Distributed Join Operations,” INFOR: Information Systems and Operational Research, vol. 28, no. 3, pp. 154–165, Aug. 1990, doi: 10.1080/03155986.1990.11732132.

R. Veerapaneni, M. S. Saleem, and M. Likhachev, “Learning Local Heuristics for Search-Based Navigation Planning,” Mar. 2023.

D. D. Arizal, “Rekomendasi Penentuan Harga Bahan dan Jasa Pembangunan Rumah Menggunakan Algoritma Tabu Search,” Universitas Islam Negeri Sultan Syarif Kasim Riau, Pekanbaru, 2021.

H. Hardiansyah, “Aplikasi Pembuatan Penentuan Lokal Untuk Penjadwalan Pengajaran Guru Dengan Menggunakan Algoritma Tabu Search Studi Kasus: Pondok Pesantren Nasriyatul Ulum Cisauk,” Universitas Islam Negeri Syarif Hidayatullah, Jakarta, 2012.

A. S. Wardana, “Penerapan algoritma Tabu Search untuk pencarian jalur terpendek dalam pengiriman barang,” Universitas Widyatama, Bandung, 2015.

M. A. Uwaisy, Z. K. A. Baizal, and M. Y. Reditya, “Recommendation of Scheduling Tourism Routes using Tabu Search Method (Case Study Bandung),” Procedia Comput Sci, vol. 157, pp. 150–159, 2019, doi: 10.1016/j.procs.2019.08.152.

R. W. Dewantoro, P. Sihombing, and Sutarman, “The Combination of Ant Colony Optimization (ACO) and Tabu Search (TS) Algorithm to Solve the Traveling Salesman Problem (TSP),” in 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering (ELTICOM), IEEE, Sep. 2019, pp. 160–164. doi: 10.1109/ELTICOM47379.2019.8943832.

R. Y. Indriani, D. Suhaedi, and F. H. Badruzzaman, “Penggunaan Metode Nadir Compromise Programming dalam Menyelesaikan Permasalahan Multi Objektif,” J. Ris. Mat., vol. 1, no. 2, pp. 82–90, Dec. 2021, doi: 10.29313/jrm.v1i2.364.

F. R. Fargiana, “Implementasi Algoritma Cheapest Insertion Heuristic dalam Menentukan Rute Pengiriman Barang,” J. Ris. Mat., vol. 1, no. 2, pp. 129–136, Feb. 2022, doi: 10.29313/jrm.v1i2.483.

H. Chaerunnissa, D. Suhaedi, and Respitawulan, “Penyelesaian Travelling Salesman Problem dengan Menggunakan Algoritma Artificial Bee Colony,” J. Ris. Mat., vol. 1, no. 1, pp. 37–45, Oct. 2021, doi: 10.29313/jrm.v1i1.160.

G. Achyar and O. Rohaeni, “Penggunaan Hybrid K-Means dan General Regression Neural Network untuk Prediksi Harga Saham Indeks LQ45,” J. Ris. Mat., pp. 111–120, Dec. 2022, doi: 10.29313/jrm.v2i2.1193.

S. D. Qirani and I. Sukarsih, “Penerapan Metode K-Nearest Neighbor untuk Prediksi Harga Gas Alam Menggunakan Python,” J. Ris. Mat., vol. 4, no. 1, pp. 57–64, Jun. 2024, doi: 10.29313/jrm.v4i1.3602.

E. Siti Nurmala and Y. Permanasari, “Penerapan Pewarnaan Graf untuk Menentukan Tujuan Wisata Kuliner Kota Bandung,” J. Ris. Mat., pp. 149–156, Dec. 2023, doi: 10.29313/jrm.v3i2.2834.

M. Y. Fakhri, E. Harahap, and F. H. Badruzzaman, “Implementasi Algoritma Welch-Powell pada Pengaturan Lampu Lalu Lintas Pasteur Bandung,” J. Ris. Mat., vol. 1, no. 2, pp. 91–98, Dec. 2021, doi: 10.29313/jrm.v1i2.365.

S. Zein and G. Gunawan, “Prediksi Hasil FIFA World Cup Qatar 2022 Menggunakan Machine Learning dengan Python,” J. Ris. Mat., pp. 153–162, Dec. 2022, doi: 10.29313/jrm.v2i2.1382.