Route Optimization in Asymmetric Capacitated Vehicle Routing Problem (ACVRP) Model using Tabu Search Algorithm (Case Study: Car Oil Distribution of PT. Kencana Central Mobil)
Keywords: Distance, Asymmetric, Heuristic Methods
Abstract
PT. Kencana Central Mobil is an automotive workshop that distributes oil to nine regular customers spread across Pontianak and its surroundings. The route from the depot to the customer and between customers has a different length, because when making a round trip using different roads. From this information, the author conducted observations in the field to measure the distance between customers with the help of the Avanza application. Thus, the problem in this company is included in the Asymmetric Capacitated Vehicle Routing Problem. The ACVRP model is a problem where the route from location to is not the same as the route from location to . Based on the problems that have been explained, this study uses the Tabu Search algorithm to solve it. The Tabu Search algorithm works by moving from one route to another, so that when related to a problem the company can find a trip by choosing the shortest route. There are six steps in solving this problem, namely determining the initial route, finding alternative routes by swapping two node positions so that the routes that can be formed each iteration are routes (nine is the number of customers), choosing the best route among alternative routes, determining the new best route, updating the tabu list and checking the stopping criteria. From the calculation results, there is a difference in the distance traveled from the initial route which is 63.16 km long, while when calculated using the Tabu Search Algorithm, it can be seen that the tabu search criteria stops at the 7th iteration with a route length of 50.26 km so that it differs by 12.9 km from the initial route. The length of the route is optimal because it has the shortest route length of all the literature that has been traced.
Downloads
References
Addini’s, S. S. F., & Fauzan, M. (2018). Penyelesaian Masalah Rute Terpendek Distribusi Kertas di CV. Margotama Fancindo Yogyakarta Menggunakan Metode Nearest Neighbour dan Metode Saving Matrix. Jurnal Kajian dan Terapan Matematika, 7(3), 96–106.
Alesiani, F., Ermis, G., & Gkiotsalitis, K. (2022) Constrained Clustering For The Capacitated Vehilce Routing Problem (CC-CVRP). Appliend Artifical Intelligence. 36(1), 1995658.
Candra, L. (2016). Penerapan Algoritma Tabu Search untuk Penjadwalan Mata Pelajaran di SMK Swasta Pelita-2 Aekkanopan. JURIKOM (Jurnal Riset Komputer), 3(6), 74–79.
Chou, X., Gambardella L. M. & Montemanni, R. (2021). A Tabu search algorithm for the probabilistic orienteering problem. Computers & Operations Research, 126, 105107
Falih, M. H. N. (2021). Implementasi Algoritma Tabu Search dalam Penjadwalan Produksi PT Arkha Jayanti Persada untuk Meminimasi Nilai Makespan. Scientific Journal of Industrial Engineering, 2(2), 41–46.
Fatimah, S. (2019). Pengantar Transportasi. Myria Publisher.
Fatmawati, Prihandono, B., & Noviani, E. (2015). Penyelesaian Travelling Salesman Problem dengan Metode Tabu Search. Bimaster, 04(1), 17–24.
Firdaus, A. N., & Rahayu, P. P. (2018). Aplikasi Algoritma Tabu Search dan Safety Stock pada Penentuan Rute Distribusi Air Mineral di Daerah Istimewa Yogyakarta. Jurnal Fourier, 7(1), 45–56.
Hakim, Lidia A., Ardiansyah, Muhammad N., & Yulianti, Femi. (2023). Usulan Perancangan Rute Transportasi di PT. XYZ Menggunakan Algoritma Tabu Search Pada Heterogeneous Fleet Vehicle Routing Problem dengan Time Window untuk Meminimasi Biaya Transportasi. e-Proceeding of Engineering. 10(3), 3055-3062.
Kusumawardana, A. S. & Irhamah. (2013). Vehicle Routing Problem With Stochastic Demands dengan Metode Hybrid Simulated Annealing-Algoritma Genetika. Jurnal Statistika Universitas Muhammadiyah Semarang, 1(2), 1–8.
Leggieri, V., & Haouari, M. (2018). A Matheuristic for the Asymmetric Capacitated Vehicle Routing Problem. Discrete Applied Mathematics, 234, 139–150.
Lu, Z., Martinez-Gavara, A., Hoa, J. K., & Lai, X. (2023). Solution-based tabu search for the capacitated dispersion problem. Expert Systems with Applications, 233, 119856.
Moghdani, R., Salimifard, K., Demir, E., & Benyettou, A. (2021). The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production, 279, 123691.
Purba, R., & Tarigan, K. (2020). Pengaruh Jenis Oli Terhadap Daya dan Konsumsi Bahan Bakar Motor Kapasitas 150 CC. Jurnal Ilmiah Teknik Sipil, 9(1), 47–58.
Riswan, Sahari, A., & Lusiyanti, D. (2020). Penentuan Rute Terpendek Pendistribusian Tabung Gas Lpg 3 Kg PT. Fega Gas Palu Pratama Menggunakan Algoritma Tabu Search. Jurnal Ilmiah Matematika dan Terapan, 16(2), 221–229.
Ritonga, R. P., Zakaria, M., & Syukriah, S. (2021). Penugasan Rute Distribusi Menggunakan Algoritma Tabu Search pada PT. Yakult Indonesia Persada Cabang Lhokseumawe. Industrial Engineering Journal, 10(1).
Sari, R. F., Rakhmawati, F., & Nur Lela. (2023). Implementasi Pewarnaan Graf Menggunakan Metode Algoritma Tabu Search Pada Penjadwalan Kerja Perawat. G-Tech: Jurnal Teknologi Terapan, 7(1), 298–304.
Siswanto, B. N., Ariffien, A., & Jayakusuma, I. (2019). Sistem Routing Proses Delivery Menggunakan Simulated Annealing (Studi Kasus: PT. X). Jurnal Teknologia, 2(1), 87–105.
Sulistiono, S., & Mussafi, N. S. M. (2015). Rancang Bangun Vehicle Routing Problem Menggunakan Algoritma Tabu Search. Jurnal Fourier, 4(2), 113–122..
Togatorop, R. E., Puspita, F. M., Octarina, S., Yuliza, E., & Dewi, N. R. (2022). Penerapan Algoritma Tabu Search pada Model ACVRP untuk Menentukan Rute Pengangkutan Sampah yang Optimal di Kecamatan Kalidoni. Teorema: Teori dan Riset Matematika, 7(2), 303–310.
Uman, M. S., Mustafis, M., & Suryono, S. (2022). A hybrid genetic algorithm and tabu search for minimizing makespan in flow shot scheduling problem. Journal of king saud University-Computer and Information Sciences, 34(9), 7459-7467.
Copyright (c) 2024 Jurnal Matematika Sains dan Teknologi
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.