Design of Vehicle Routes for Rice Distribution System in Bandung Using Simulated Annealing Algorithm
DOI:
https://doi.org/10.26593/jrsi.v11i2.5842.211-220Kata Kunci:
heuristic method, rice distribution system, simulated annealing, vehicle routing problemAbstrak
VRP (vehicle routing problem) belongs to the problem of NP-hard. It makes the computation time becoming longer as the number of data increases. This statement is in accordance with previous research which solved the VRP for the rice distribution system in Bandung which consisted of 40 demand points in the form of traditional markets using the optimal method. The computational time required is 167 hours 52 minutes 38 seconds. Therefore, a heuristic method is needed to solve VRP with a more efficient computation time and an acceptable solution. The purpose of this paper is to complete the VRP by using an annealing simulation to design a rice distribution system in Bandung. Simulated annealing (SA) is a local search algorithm (meta-heuristic) that is able to get out of the local optimum. Its ease of implementation, the use of hill-climbing motions to avoid local optimal, and the convergent nature, have made SA a popular technique over the past two decades. After comparing the results to the ILP model, the computational experiments show what the SA algorithm developed in this paper is able to produce a relatively small gap in terms of total transportation cost, which is 1.26%. This paper has also succeeded in improving the previous paper by reducing the computation time to 19 seconds using the developed SA algorithm.
Referensi
Fitria, L., Susanty, S., & Suprayogi, S. (2009). Penentuan Rute Truk Pengumpulan Dan Pengangkutan Sampah Di Bandung. Jurnal Teknik Industri, 11(1), 51–60. https://doi.org/10.9744/jti.11.1.pp
Henderson, D., Jacobson, S. H., & Johnson, A. W. (2003). The Theory and Practice of Simulated Annealing. In F. Glover & G. A. Kochenberger (Eds.), Handbook of Metaheuristics (pp. 287–319). Springer US. https://doi.org/10.1007/0-306-48056-5_10
Lubis, H. A. R., Maulana, A., & Frazila, R. B. (2016). Penerapan Konsep Vehicle Routing Problem dalam Kasus Pengangkutan Sampah di Perkotaan. Jurnal Teknik Sipil, 23(3), 213–222. https://doi.org/10.5614/jts.2016.23.3.6
Ramadhan, F., & Imran, A. (2018). Penentuan Rute Dan Jumlah Kendaraan Pada Kasus School Bus Routing Problem: Penerapan Algoritma Record-to-record Travel. Jurnal Rekayasa Sistem & Industri (JRSI), 5(01), 15–22. https://doi.org/10.25124/jrsi.v5i01.307
Saragih, N. I., Bahagia, S. N., Suprayogi, & Syabri, I. (2019). A heuristic method for location-inventory-routing problem in a three-echelon supply chain system. Computers & Industrial Engineering, 127, 875–886. https://doi.org/10.1016/j.cie.2018.11.026
Saragih, N. I., & Rachman, R. S. (2020). The Application of Vehicle Routing Problem for Rice Distribution System in City of Bandung. 334–338. https://doi.org/10.2991/aebmr.k.201222.048
Sopandi, D. B., Ardiansyah, D., Pangestu, D., Hasanah, T. U., & Saragih, N. I. (2020). The Application of Improved Nearest Neighbor Heuristic to Solve Vehicle Routing Problem for Rice Distribution System in Bandung. Solid State Technology, 63(4), 4449–4461.
Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718515
Wulandari, S., Kusrini, K., & Arief, M. R. (2019). Penerapan Algoritma Palgunadi Pada Split Delivery Vehicle Routing Problem Untuk Pendistribusian Multi Produk. Informasi Interaktif, 4(1), 23–30.
