Comparative Analysis of New Solutions for the Capacitated Vehicle Routing Problem Against CVRPLIB Benchmark
DOI:
https://doi.org/10.22399/ijcesen.626Keywords:
NP-hard problems, Capacitated vehicle routing problem, Ant colony systemAbstract
The capacitated vehicle routing (CVRP) is a combinatorial optimization problem (COP) which is belong to NP-hard problem category. This problem includes determining the best option for low-cargo vehicles to serve a number of clients. Every client is required to make a single journey, and the overall demand on each route cannot be greater than the vehicle's capacity. Numerous precise and heuristic approaches have been put out in the literature to address this problem. Specific methods such as branch-binding and branch-pruning assure the search for optimal solutions but are often impractical for large data sets due to their computational complexity heuristic and metaheuristic approaches like genetic algorithms (GAs), ant colony optimization (ACO), simulated annealing (SA), and tabu search (TS), provide optimal solutions in real time, making them more appropriate for bigger instances. Despite these advancements, most studies have not achieved new results compared to those in the standard CVRPLIB benchmark instances. Therefore, this study focused on exploring new results obtained by state-of-the-art approaches in the literature that have solved CVRP. In particular, our aim is to explore new algorithmic improvements designed to improve CVRP regarding to computational efficiency and quality of the solution.
References
V. Praveen, (2022). Vehicle Routing Optimization Problem: A Study on Capacitated Vehicle Routing Problem’, Materialstoday Proceeding, 64(1);670–674. https://doi.org/10.1016/j.matpr.2022.05.185
E. Febriana Aqidawati, M. Ichwan Anshory, A. Dityarini, W. Sutopo, and B. Artanto, (2021). Application of Vehicle Routing Problem to Determine Optimal Route in Fuel Distribution: A Case Study. Proceedings of the 11th Annual International Conference on Industrial Engineering and Operations Management Singapore, March 7-11, 2021
Kim, H., Kang, J., & Kim, W. (2014). AN Application of capacitated vehicle routing problem to reverse logistics of disposed food waste. International Journal of Industrial Engineering-theory Applications and Practice, 21.
N. Christofides, A. Mingozzi, and P. Toth, (1979). Loading problems’, N. Christofides and al., editors, Combinatorial Optimization, pp. 339–369.
M. L. Mutar, B. M. Aboobaider, A. S. Hameed, and N. Yusof, ‘Enhancing solutions of capacity vehicle routing problem based on an improvement ant colony system algorithm’, vol, vol. 11, pp. 1362–1374, 2019.
S. F. M. Ayop, M. S. Othman, and L. M. Yusuf, (2020). Ant Colony Optimization Using Different Heuristic Strategies for Capacitated Vehicle Routing Problem, IOP Conference Series: Materials Science and Engineering, IOP Publishing, p. 012082.
Y. Kao and M. Chen, (2013). Solving the CVRP problem using a hybrid PSO approach, in Computational Intelligence: Revised and Selected Papers of the International Joint Conference, IJCCI 2011, Paris, France, October 24-26, 2011, Springer,pp. 59–67.
T. Iswari and A. M. S. Asih, (2018). Comparing genetic algorithm and particle swarm optimization for solving capacitated vehicle routing problem, in IOP Conference Series: Materials Science and Engineering, Institute of Physics Publishing, Apr. 2018. doi: 10.1088/1757-899X/337/1/012004.
P. Augerat, D. Naddef, J. M. Belenguer, E. Benavent, A. Corberan, and G. Rinaldi, (1995). Computational results with a branch and cut code for the capacitated vehicle routing problem. Istituto di analisi dei sistemi ed informatica consiglio nazionale delle ricerche
N. Christofides and S. Eilon, (1969). An algorithm for the vehicle-dispatching problem, Journal of the Operational Research Society, 20(3);309–318. https://www.jstor.org/stable/3008733
M. L. Fisher, (1994). Optimal solution of vehicle routing problems using minimum k-trees, Oper Res, 42(4);626–642. https://www.jstor.org/stable/171617
N. Christofides, (1979). The vehicle routing problem’, Combinatorial optimization. 10;55-70 DOI:10.1051/ro/197610v100551
Y. Rochat and É. D. Taillard, (1995). Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1(1);147–167. https://doi.org/10.1007/BF02430370
B. Golden, E. Wasil, J. Kelly, and I. Chao, (1998). The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, Fleet Management and Logistics, Springer, pp. 33–56.
F. Li, B. Golden, and E. Wasil, (2005). Very large-scale vehicle routing: new test problems, algorithms, and results, Computers & Operations Research, 32(5);1165–1179. https://doi.org/10.1016/j.cor.2003.10.002
D. Pecin, A. Pessoa, M. Poggi, and E. Uchoa, (2014). Improved branch-cut-and-price for capacitated vehicle routing, in Integer Programming and Combinatorial Optimization, Springer, pp. 393–403.
F. Arnold, M. Gendreau, and K. Sörensen, (2019) Efficiently solving very large-scale routing problems, Comput Oper Res,107;32–42. https://doi.org/10.1016/j.cor.2019.03.006
Y. Xiao, Q. Zhao, I. Kaku, and Y. Xu, (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Comput Oper Res, 39(7);1419–1431. https://doi.org/10.1016/j.cor.2011.08.013
W. Y. Szeto, Y. Wu, and S. C. Ho, (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem, Eur J Oper Res, 215(1);126–135 https://doi.org/10.1016/j.ejor.2011.06.006
R. Baldacci, A. Mingozzi, and R. Roberti, (2011) New route relaxation and pricing strategies for the vehicle routing problem, Oper Res, 59(5);1269–1283. DOI:10.1287/opre.1110.0975
G. Perboli, R. Tadei, and D. Vigo, (2011). The two-echelon capacitated vehicle routing problem: Models and math-based heuristics, Transportation Science, 45(3);364–380. https://www.jstor.org/stable/23018533
P. Toth and D. Vigo, (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Appl Math, 123(1–3);487–512. https://doi.org/10.1016/S0166-218X(01)00351-1
Z. Wang and J.-B. Sheu, (2019). Vehicle routing problem with drones, Transportation research part B: methodological, 122;350–364. https://doi.org/10.1016/j.trb.2019.03.005
E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, (2017). New benchmark instances for the capacitated vehicle routing problem, Eur J Oper Res, 257(3);845–858. https://doi.org/10.1016/j.ejor.2016.08.012
I. Kara, B. Y. Kara, and M. K. Yetis, (2007). Energy minimizing vehicle routing problem, in Combinatorial Optimization and Applications: First International Conference, COCOA 2007, Xi’an, China, August 14-16, 2007. Proceedings 1, Springer, 2007, pp. 62–71.
C. Archetti, M. Savelsbergh, and M. G. Speranza, (2016). The vehicle routing problem with occasional drivers, Eur J Oper Res, 254(2);472–480. DOI:10.1016/j.ejor.2016.03.049
M. Reed, A. Yiannakou, and R. Evering, (2014). An ant colony algorithm for the multi-compartment vehicle routing problem, Appl Soft Comput, 15;169–176. https://doi.org/10.1016/j.asoc.2013.10.017
M. L. Mutar, B. M. Aboobaider, A.S. Hameed, N. Yusof, M. F. Alrifaie, and A. A. Mohammed, (2020). Multi-objectives ant colony system for solving multi-objectives capacitated vehicle routing problem, J Theor Appl Inf Technol, 98(24);14.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 International Journal of Computational and Experimental Science and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
