Web Metaheuristic Algorithm for Capacitated Vehicle Routing Problem

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University

Abstract

In the business world, a high percentage of prime costs is related to transportation. Any actions to improve transport ways and eliminate unnecessary trips or create alternative shorter routes leads to significant savings in total costs. One of the well-known optimization issues in this regard is capacitated vehicle routing problem (CVRP) that includes arranging vehicle routes while considering its capacity. This problem is among the NP-Hard problems and many different metaheuristic algorithms have been applied for finding its solution, especially in large dimensions. The purpose of this paper is to design a new metaheuristic algorithm, inspired by spiders routing and hunting in cobweb, based on the problem structure which can be used to obtain optimum and near optimum results. Solving three standard problems of CVRP with different dimensions, called P-n19-k2, E-n33-k14, and B-n78-k10 demonstrates that the error values of the proposed algorithm from the optimum answers are less than one percent. Therefore, web metaheuristic algorithm is capable of achieving proper answers in a reasonable time.

Keywords

References

Altabeeb, A. M., Mohsen, A. M., Abualigah, L., & Ghallab, A. (2021). Solving capacitated vehicle routing problem using cooperative firefly algorithm. Applied Soft Computing, 108, 107403. https://doi.org/10.1016/j.asoc.2021.107403
Amberg, A., Domschke, W., & Voß, S. (2000). Multiple Center Capacitated Arc Routing Problems: A Tabu Search Algorithm using Capacitated Trees. European Journal of Operational Research, 124(2), 360–376. https://doi.org/10.1016/S0377-2217(99)00170-8
Arbelaitz, O., Rodriguez, C., & Zamakola, I. (2001). Low Cost Parallel Solutions for the VRPTW Optimization Problem. Proceedings of the International Conference on Parallel Processing Workshops, 2001-Janua, 176–181. https://doi.org/10.1109/ICPPW.2001.951932
Arifuddin, A., Utamima, A., Mahananto, F., Vinarti, R. A., & Fernanda, N. (2024). Optimizing the Capacitated Vehicle Routing Problem at PQR Company: A Genetic Algorithm and Grey Wolf Optimizer Approach. Procedia Computer Science, 234, 420–427. https://doi.org/10.1016/j.procs.2024.03.023
Aydınalp, Z., & Özgen, D. (2023). Solving vehicle routing problem with time windows using metaheuristic approaches. International Journal of Intelligent Computing and Cybernetics, 16(1), 121–138. https://doi.org/10.1108/IJICC-01-2022-0021
Berger, J., & Barkaoui, M. (2003). A New Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem. Journal of the Operational Research Society, 54(12), 1254–1262. https://doi.org/10.1057/palgrave.jors.2601635
Bullnheimer, B., Hartl, R. F., & Strauss, C. (1997). Applying the ANT System to the Vehicle Routing Problem. 2nd International Conference on Metaheuristics, November. https://doi.org/10.1007/978-1-4615-5775-3
Caccetta, L., & Abdul-niby, M. (2013). [8] An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem [2013]. 3, 413–415.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80–91. https://doi.org/10.1007/978-1-4419-1153-7_200874
Dorigo, M. (1992). Optimization, Learning and Natural Algorithms.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.
Jiang, H., Lu, M., Tian, Y., Qiu, J., & Zhang, X. (2022). An evolutionary algorithm for solving Capacitated Vehicle Routing Problems by using local information. Applied Soft Computing, 117, 108431. https://doi.org/10.1016/j.asoc.2022.108431
Ke, L., & Feng, Z. (2013). A two-Phase Metaheuristic for the Cumulative Capacitated Vehicle Routing Problem. Computers and Operations Research, 40(2), 633–638. https://doi.org/10.1016/j.cor.2012.08.020
Kumari, M., De, P. K., Chaudhuri, K., & Narang, P. (2023). Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem. Results in Control and Optimization, 13(September), 100292. https://doi.org/10.1016/j.rico.2023.100292
Li, F., Golden, B., & Wasil, E. (2005). Very Large-Scale Vehicle Routing: New Test Problems, Algorithms, and Results. Computers and Operations Research, 32(5), 1165–1179. https://doi.org/10.1016/j.cor.2003.10.002
Lin, S. W., Lee, Z. J., Ying, K. C., & Lee, C. Y. (2009). Applying Hybrid Meta-Heuristics for Capacitated Vehicle Routing Problem. Expert Systems with Applications, 36(2 PART 1), 1505–1512. https://doi.org/10.1016/j.eswa.2007.11.060
Mahmudy, W. F., Widodo, A. W., & Haikal, A. H. (2024). Challenges and Opportunities for Applying Meta-Heuristic Methods in Vehicle Routing Problems: A Review †. Engineering Proceedings, 63(1). https://doi.org/10.3390/engproc2024063012
Miao, L., Ruan, Q., Woghiren, K., & Ruo, Q. (2012). A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints. RAIRO - Operations Research, 46(1), 63–82. https://doi.org/10.1051/ro/2012008
Muriyatmoko, D., Djunaidy, A., & Muklason, A. (2024). Heuristics and Metaheuristics for Solving Capacitated Vehicle Routing Problem: An Algorithm Comparison. Procedia Computer Science, 234, 494–501. https://doi.org/10.1016/j.procs.2024.03.032
Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the Capacitated Vehicle Routing Problem. Mathematical Programming, 94, 343–359.
Reimann, M., Doerner, K., & Hartl, R. F. (2004). D-ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem. Computers and Operations Research, 31(4), 563–591. https://doi.org/10.1016/S0305-0548(03)00014-5
Sbai, I., Krichen, S., & Limam, O. (2022). Two Meta-Heuristics for Solving the Capacitated Vehicle Routing Problem: The Case of the Tunisian Post Office. In Operational Research (Vol. 22, Issue 1). Springer Berlin Heidelberg. https://doi.org/10.1007/s12351-019-00543-8
Simsir, F., & Ekmekci, D. (2019). A Metaheuristic Solution Approach to Capacitied Vehicle Routing and Network Optimization. Engineering Science and Technology, an International Journal, 22(3), 727–735. https://doi.org/10.1016/j.jestch.2019.01.002
Tlili, T., Faiz, S., & Krichen, S. (2014). A Hybrid Metaheuristic for the Distance-constrained Capacitated Vehicle Routing Problem. Procedia - Social and Behavioral Sciences, 109, 779–783. https://doi.org/10.1016/j.sbspro.2013.12.543
Wang, C. H., & Lu, J. Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert Systems with Applications, 36(2 PART 2), 2921–2936. https://doi.org/10.1016/j.eswa.2008.01.072
Xu, J., & Kelly, J. P. (1996). A Network Flow-based Tabu Search Heuristic for the Vehicle Routing Problem. Transportation Science, 30(4), 379–393. https://doi.org/10.1287/trsc.30.4.379
Journal of Optimization and Supply Chain Management
Volume 1, Issue 1
September 2024
Pages 63-72

Files

Share

How to cite

Statistics