A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems

In vehicle routing problems, the initial solutions of the routes are important for improving thequality and solution time of the algorithm. For a better route construction algorithm, theobtained initial solutions must be basic, fast, and flexible with reasonable accuracy. In thisstudy, initial solutions are introduced to improve the final solution of the Capacitated VehicleRouting Problem based on a method from the literature. Using a different formula foraddressing the gravitational forces, a new method is introduced and compared with the previousphysics inspired algorithm. By using the initial solutions of the proposed method and usingthem as the initial routes of the Record-to-Record and Simulated Annealing algorithms, it isseen that better results are obtained when compared with various algorithms from the literature.Also, in order to fairly compare the algorithms executed on different machines, a newcomparison scale for the solution quality of vehicle routing problems is proposed that dependson the solution time and the deviation from the best known solution. The obtained initialsolutions are then input to Record-to-Record and Simulated Annealing algorithms to obtainfinal solutions. Various test instances and CVRP solutions from the literature are used forcomparison. The comparisons with the proposed method have shown promising results.

PDF

___

Toth, P., Vigo, D., An Overview of Vehicle Routing Problem, in The Vehicle Routing Problem, Philadelphia, SIAM, 1–23, (2002).
Li, F., Golden, B., Wasil, E., “Very large-scale vehicle routing: new test problems, algorithms, and results,” Computers & Operations Research, 32(5): 1165–1179, (2005).
Cordeau, J.F., Gendreau M.,Laporte, G.,Potvin, J.Y., Semet F., “A guide to vehicle routing heuristics,” Journal of the Operational Research Society, 53(5): 512–522, (2002).
Baker, B.M., Ayechew, M., “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, 30(5): 787–800, (2003).
Battarra, M., Benedettini, S., Roli, A., “Leveraging saving-based algorithms by master–slave genetic algorithms,” Engineering Applications of Artificial Intelligence, 24(4): 555–566, (2011).
Laporte, G., Semet, F., Classical Heuristics for the Capacitated VRP, in The Vehicle Routing Problem, Philadelphia, SIAM, 109-126, (2002).
Prins, C., “A simple and effective evolutionary algorithm for the vehicle routing problems,” Computers & Operations Research, 31(12): 1985-2002, (2004).
Spall, J.C., Stochastic Optimization, in Handbook of Computational Statistics: Concepts and Methods (2nd ed.) (Gentle, J., Härdle, W., Mori, Y. eds.), Springer−Verlag, Heidelberg, Chapter 7, 173–201, (2012).
Rashedi, E., Nezamabadi-pour, H., Saryazdi, S., Farsangi, M.M., “Allocation of static var compensator using gravitational search algorithm,” in First Joint Congress on Fuzzy and Intelligent Systems, Mashhad, Iran, (2007).
Xie, L., Tan, Y., Zeng, J., “Artificial physics optimisation: a brief survey,” International Journal of Bio-Inspired Computation, 2(5): 291-302, (2010).
Rashedi, E., Nezamabadi-pour, H., Saryazdi, S., “GSA: A gravitational search algorithm,” Information Sciences, 179(13): 2232-2248, (2009).
Formato, R.A., “Central Force Optimization: A new metaheuristic with applications in applied electromagnetism,” Progress In Electromagnetics Research, 77: 425-491, (2007).
Zheng, M., Liu, G.-X., Zhou, C.-G., Liang, Y.-C., Wang, Y., “Gravitation field algorithm and its application in gene cluster,” Algorithms for Molecular Biology, 6: 1-11, (2010).
Xie, L., Tan, Y., Zeng, J., Artificial Physics Optimization Algorithm for Global Optimization, in Physicomimetics (Spears, M., Spears, D., eds.), London, New York, Springer Heidelberg Dordrecht, 565-589, (2011).
Xie, L., Zeng, J., Formato, R.A., “Convergence analysis and performance of the extended artificial physics optimization algorithm,” Applied Mathematics and Computation, 218: 4000–4011, (2011).
Kripka, M., Kripka, R.M.L., “Big crunch optimization method,” in EngOpt 2008 - International Conference on Engineering Optimization, Rio de Janeiro, Brazil, (2008).
Ding, D., Qi, D., Luo, X., Chen, J., Wang, X., Du, P., “Convergence analysis and performance of an extended central force optimization algorithm,” Applied Mathematics and Computation, 219(4): 2246–2259, (2012).
Sarafrazi, S., Nezamabadi-pour, H., Saryazdi, S., “Disruption: A new operator in gravitational search algorithm," Scientia Iranica D, 18(3): 539–548, (2011).
Hassanzadeh, H.R., Rouhani, M., “A multi-objective gravitational search algorithm,” in Second International Conference on Computational Intelligence, Communication Systems and Networks, Liverpool, UK, (2010).
Chatterjee, A., Mahanti, G.K., Pathak, N., “Comparative performance of gravitational search algorithm and modified particle swarm optimization algorithm for synthesis of thinned scanned concentric ring array antenna,” Progress In Electromagnetics Research B, 25(25): 331–348, (2010).
Duman, S., Güvenç, U., Yörükeren, N., “Gravitational search algorithm for economic dispatch with valve-point effects,” International Review of Electrical Engineering, 5(6): 2890-2895, (2010).
Shin,K., Han, S., “A centroid-based heuristic algorithm for the capacitated vehicle routing problem,” Computing and Informatics, 30(4): 721-732, (2011).
Karagül, K., Tokat, S., Aydemir, E., “Physics-inspired optimization algorithm for obtaining initial routes of capacitated vehicle routing problem,” in EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog), Oslo, Norway, (2014).
Karagül, K., Tokat, S., Aydemir, E., "A new algorithm to the construction of the initial routes for the capacitated vehicle routing problem", Journal of Engineering Sciences and Design, 4(3): 215-226, (2016).
Vidal, T., Battarra, M., Subramanian, A., Erdoǧan, G., “Hybrid metaheuristics for the clustered vehicle routing problem,” Computers & Operations Research, 58: 87–99, (2015).
Guimarans, D., Herrero, R., Ramos, J. J., Padrón, S., “Solving vehicle routing problems using constraint programming and Lagrangean relaxation in a metaheuristics framework,” International Journal of Information Systems and Supply Chain Management, 4(2): 61-81, (2011).
Guimarans, D., Herrero, R., Riera, D., Juan, A.A., Ramos, J.J., “Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem,” Annals of Mathematics and Artificial Intelligence, 62(3-4): 299-315, (2011).
The Physics Classroom, “The Physics Classroom,” (10.07.2015)-[Online]. Available: http://www.physicsclassroom.com/class/circles/Lesson-3/Newton-s-Law-of-Universal-Gravitation.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., Subramanian, A., “New benchmark instances for the capacitated vehicle routing problem,” European Journal of Operational Research, 257(3): 845-858, (2017).
Kay, M. G., “Matlog: Logistics Engineering Matlab Toolbox,” (05.05.2015)-[Online]. Available: http://www.ise.ncsu.edu/kay/matlog/index.htm.
Kay, M.G., “Matlog: Logistics Engineering Matlab”, Journal of Engineering Sciences and Design, 4(1): 15-20, (2016).
Groer, C., Golden, B., Wasil, E., “A library of local search heuristics for the vehicle routing problem,” Mathematical Programming Computation, 2(2): 79-101, (2010).
Groer, C., Parallel and Serial Algorithms for Vehicle Routing Problems,” PhD Thesis, (Golden, B., supervisor), Robert H. Smith School of Business, (2008).
Groer, C., "VRPH," (5.5.2015)-[Online]. Available: http://www.coin-or.org/projects/VRPH.xml.
Battarra, M., Benedettini, S., Roli, A., “Additional material for “Leveraging saving-based algorithms by master-slave genetic algorithms,” Engineering Applications of Artificial Intelligence, Appendix A: supplementary data, (2011).
Yurtkuran, A., Emel, E., “A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems,” Expert Systems with Applications, 37(4):3427–3433, (2010).
Xie, L., Zeng, J., “The performance analysis of artificial physics optimization algorithm driven by different virtual forces,” ICIC Express Letters (ICIC-EL), 4(1): 239-244, (2010).