Solving the Asymmetric Capacitated Vehicle Routing Problem with Time Windows Using Sequential Insertion (SI) and Ant Colony Optimization (ACO) Algorithms
DOI:
https://doi.org/10.26593/jrsi.v12i2.6477.273-280Keywords:
vehicle routing problem, shipping cost, sequential insertion, ant colony optimizationAbstract
One of the main aspects that determines the successful of managing a supply chain system or supply chain management (SCM) is transportation planning. The problem of determining vehicle routes or commonly known as the vehicle routing problem (VRP) is one of the important studies in transportation planning at the operational level. Determining the right vehicle routes can increase the effectiveness and efficiency of a transportation system and related supply chain systems. This research focuses on the asymmetric capacitated vehicle routing problem with time windows (ACVRPTW), which is a vehicle routing problem that takes into account vehicle capacity, asymmetric return distances between customers, and delivery time constraints. A mathematical model is formulated based on the research objective to be achieved, i.e. minimizing the total shipping costs consisting of travel costs, overtime delivery costs, late delivery compensation costs, and re-delivery costs. Two alternative solution algorithms are developed, namely sequential insertion (SI) and ant colony optimization (ACO). A numerical example is provided to present the results of research on a clothing convection industry, where the ACO algorithm is proven to be able to produce better solutions than the SI algorithm.
References
Archetti, C., & Speranza, M. G. (2014). A survey on matheuristics for routing problems. EURO Journal on Computational Optimization, 2(4), 223–246.
Cordeau, J. F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle Routing. In C. Barnhart & G. Laporte (Eds.), Handbooks in Operations Research and Management Science: Transportation (1st ed., Vol. 14, pp. 195–224). Amsterdam: North-Holland.
CSCMP. (2023, February 6). Supply Chain Management Definitions and Glossary. https://cscmp.org/CSCMP/Educate/SCM_Definitions_and_Glossary_of_Terms.aspx.
Herrero, R., Rodriguez, A., Cruz, J. C., & Juan, A. A. (2014). Solving vehicle routing problems with asymmetric costs and heterogeneous fleets. International Journal of Advanced Operations Management, 6(1), 58–80.
Ilin, V., Matijevic, L., Davidovic, T., & Pardalos, P. M. (2018). Asymmetric Capacitated Vehicle Routing Problem with Time Window. Proceedings of XLV Symposium on Operational Research, 174–179.
Kumar, S. N., & Panneerselvam, R. (2012). A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 4(3), 66–74.
Leggieri, V., & Haouari, M. (2016). A matheuristic for the asymmetric capacitated vehicle routing problem. Discrete Applied Mathematics, 234, 139–150.
Li, J., Li, T., Yu, Y., Zhang, Z., Pardalos, P. M., Zhang, Y., & Ma, Y. (2019). Discrete firefly algorithm with compound neighborhoods for asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery. Applied Soft Computing, 81.
Liputra, D. T., Anna, I. D., & Kartika, W. (2015). Multi-vendor-Single-buyer Transportation Model with Heterogeneous Vehicles for Perishable Product. Proceedings of the 16th Asia Pacific Industrial Engineering and Management Systems, 1542–1546.
Liputra, D. T., Suhandi, V., & Ramdani, R. (2016). Balancing Vehicle Utilization on Capacitated Vehicle Routing Problem with Time Windows Using Simulated Annealing Algorithm. Proceedings of the 7th International Conference on Operations and Supply Chain Management, 344–351.
Marinakis, Y., & Migdalas, A. (2002). Heuristic Solutions of Vehicle Routing Problems in Supply Chain Management. In P. M. Pardalos, A. Migdalas, & R. E. Burkard (Eds.), Combinatorial and Global Optimization (Vol. 14, pp. 205–236). Singapore: World Scientific.
Pujawan, I. N., & Mahendrawathi, E. (2010). Supply Chain Management (2nd ed.). Surabaya: Guna Widya.
Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik: Implementasi dengan Matlab (1st ed.). Surabaya: ITS Tekno Sains.
Simchi-Levi, D., Kaminsky, P., & Simchi-Levi, E. (2009). Designing and Managing the Supply Chain: Concepts, Strategies, and Case Studies (3rd ed.). New York: McGraw-Hill.
Togatorop, R. E., Puspita, F. M., Yuliza, E., Dewi, N. R., & Octarina, S. (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.
