Adjusting the order crossover operator for capacitated vehicle routing problems. (English) Zbl 1520.90037
Summary: The capacitated vehicle routing problem is a much studied combinatorial optimization problem, reflecting its practical importance within areas such as logistics. The problem is computationally intractable, and heuristics are commonly applied for solving large instances. Among the best heuristics available is a hybrid genetic search that consists of mechanisms from evolutionary algorithms and a range of local search operators. This heuristic applies an order crossover operator that takes as input two existing solutions and produces as output a new solution for the search to explore. An open-source implementation of the heuristic is available, in which the order crossover operator represents 1.4% of the code. This work discusses potential short-comings of the traditional order crossover operator and proposes an adjusted operator. The new operator is evaluated on standard benchmark test instances, and is shown to reduce the gaps to best-known solutions by 4.2%.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Accorsi, L.; Vigo, D., A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems, Transp. Sci., 55, 832-856 (2021) |
| [2] | Arnold, F.; Gendreau, M.; Sörensen, K., Efficiently solving very large-scale routing problems, Comput. Oper. Res., 107, 32-42 (2019) · Zbl 1458.90055 |
| [3] | Arnold, F.; Sörensen, K., Knowledge-guided local search for the vehicle routing problem, Comput. Oper. Res., 105, 32-46 (2019) · Zbl 1458.90056 |
| [4] | Berthold, T., Measuring the impact of primal heuristics, Oper. Res. Lett., 41, 611-614 (2013) · Zbl 1287.90037 |
| [5] | Christiaens, J.; Vanden Berghe, G., Slack induction by string removals for vehicle routing problems, Transp. Sci., 54, 417-433 (2020) |
| [6] | Dantzig, G. B.; Ramser, J. H., The truck dispatching problem, Manage. Sci., 6, 80-91 (1959) · Zbl 0995.90560 |
| [7] | David, L., Applying adaptive algorithms to epistatic domains, (IJCAI’85: Proceedings of the 9th International Joint Conference on Artificial Intelligence, Vol. 1 (1985)), 162-164 |
| [8] | Derrac, J.; García, S.; Molina, D.; Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol. Comput., 1, 3-18 (2011) |
| [9] | Gendreau, M.; Laporte, G.; Potvin, J.-Y., Metaheuristics for the capacitated VRP, (Toth, P.; Vigo, D., The Vehicle Routing Problem. The Vehicle Routing Problem, Discrete Mathematics and Applications (2002), SIAM: SIAM Philadelphia, USA), 129-154 · Zbl 1076.90545 |
| [10] | Laporte, G., Fifty years of vehicle routing, Transp. Sci., 43, 4, 408-416 (2009) |
| [11] | Lenstra, J. K.; Kan, A. R., Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981) |
| [12] | Oliver, I. M.; Smith, D. J.; Holland, J. R.C., A study of permutation crossover operators on the traveling salesman problem, (Grefenstette, J., Genetic Algorithms and their Applications: Proceedings of the Second International Conference (1987), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ, USA), 224-230 |
| [13] | Pecin, D.; Pessoa, A.; Poggi, M.; Uchoa, E., Improved branch-cut-and-price for capacitated vehicle routing, Math. Program. Comput., 9, 61-100 (2017) · Zbl 1368.90111 |
| [14] | Pessoa, A.; Sadykov, R.; Uchoa, E.; Vanderbeck, F., A generic exact solver for vehicle routing and related problems, Math. Program., 183, 483-523 (2020) · Zbl 1450.90017 |
| [15] | Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Comput. Oper. Res., 31, 12, 1985-2002 (2004) · Zbl 1100.90504 |
| [16] | Reeves, C. R., Genetic algorithms, (Gendreau, M.; Potvin, J.-Y., Handbook of Metaheuristics. Handbook of Metaheuristics, International Series in Operations Research & Management Science, vol. 146 (2010), Springer: Springer New York, NY, USA), 109-140 · Zbl 1198.90002 |
| [17] | Simensen, M.; Hasle, G.; Stålhane, M., Combining hybrid genetic search with ruin-and-recreate for solving the capacitated vehicle routing problem, J. Heuristics (2022) |
| [18] | Subramanian, A.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for a class of vehicle routing problems, Comput. Oper. Res., 40, 2519-2531 (2013) · Zbl 1348.90132 |
| [19] | Uchoa, E.; Pecin, D.; Poessoa, A.; Poggi, M.; Vidal, T.; Subramanian, A., New benchmark instances for the capacitated vehicle routing problem, European J. Oper. Res., 257, 845-858 (2017) · Zbl 1394.90130 |
| [20] | Vidal, T., Tehcnical note: Split algorithm in O(n) for the capacitated vehicle routing problem, Comput. Oper. Res., 69, 40-47 (2016) · Zbl 1349.90136 |
| [21] | Vidal, T., Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood, Comput. Oper. Res., 140, Article 105643 pp. (2022) · Zbl 1512.90004 |
| [22] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Lahrichi, N.; Rei, W., A hybrid genetic algorithm for multidepot and periodic vehicle routing problems, Oper. Res., 60, 3, 611-624 (2012) · Zbl 1260.90058 |
| [23] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Comput. Oper. Res., 40, 475-489 (2013) · Zbl 1349.90137 |
| [24] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, European J. Oper. Res., 234, 658-673 (2014) · Zbl 1304.90004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
