×

A memetic algorithm for the multiperiod vehicle routing problem with profit. (English) Zbl 1317.90340

Summary: In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archetti, C.; Hertz, A.; Speranza, M., Metaheuristics for the team orienteering problem, Journal of Heuristics, 13, 49-76 (2007)
[2] Beasley, J., Route-first cluster-second methods for vehicle routing, Omega, 11, 403-408 (1983)
[3] Bellman, R., Dynamic programming treatment of the travelling salesman problem, Journal of ACM, 9, 61-63 (1962) · Zbl 0106.14102
[4] Bostel, N.; Dejax, P.; Guez, P.; Tricoire, F., Multiperiod planning and routing on a rolling horizon for field force optimization logistics, (Golden, B.; Raghavan, S.; Wasil, E., The Vehicle Routing Problem: Latest Advances and New Challenges, vol. 43 (2008), Springer: Springer US), 503-525 · Zbl 1187.90040
[5] Bouly, H.; Dang, D.-C.; Moukrim, A., A memetic algorithm for the team orienteering problem, 4OR: A Quarterly Journal of Operations Research, 8, 49-70 (2010) · Zbl 1186.90012
[6] Campbell, A. M.; Savelsbergh, M., Efficient insertion heuristics for vehicle routing and scheduling problems, Transportation Science, 38, 369-378 (2004)
[8] Chao, I.-M.; Golden, B. L.; Wasil, E. A., The team orienteering problem, European Journal of Operational Research, 88, 464-474 (1996) · Zbl 0911.90145
[9] Christofides, N.; Beasley, J. E., The period routing problem, Networks, 14, 237-256 (1984) · Zbl 0541.90073
[10] Chu, F.; Labadi, N.; Prins, C., A scatter search for the periodic capacitated arc routing problem, European Journal of Operational Research, 169, 586-605 (2006) · Zbl 1079.90028
[11] Cordeau, J.-F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 105-119 (1997) · Zbl 0885.90037
[12] Goel, A., Vehicle scheduling and routing with drivers’ working hours, Transportation Science, 43, 17-26 (2009)
[13] Goel, A., Truck driver scheduling in the European Union, Transportation Science, 44, 429-441 (2010)
[14] (Golden, B.; Raghavan, S.; Wasil, E., The Vehicle Routing Problem: Latest Advances and New Challenges (2008), Springer: Springer US) · Zbl 1142.90004
[15] Golden, B.; Wasil, E.; Kelly, J.; Chao, I.-M., The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results, (Crainic, T.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Boston), 33-56 · Zbl 0997.90021
[17] Hancock, W.; Bayha, F., The learning curve, (Salvendy, G., Handbook of Industrial Engineering (1992), John Wiley: John Wiley New York)
[18] Ke, L.; Archetti, C.; Feng, Z., Ants can solve the team orienteering problem, Computers and Industrial Engineering, 54, 648-665 (2008)
[19] Kok, A. L.; Meyer, C. M.; Kopfer, H.; Schutten, J. M.J., A dynamic programming heuristic for the vehicle routing problem with time windows and european community social legislation, Transportation Science, 44, 442-454 (2010)
[20] Laporte, G., What you should know about the vehicle routing problem, Naval Research Logistics (NRL), 54, 811-819 (2007) · Zbl 1135.90308
[21] Mendoza, J.; Medaglia, A.; Velasco, N., An evolutionary-based decision support system for vehicle routing: the case of a public utility, Decision Support Systems, 46, 730-742 (2009)
[22] Moscato, P., Memetic algorithms: a short introduction, (Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw Hill), 219-234
[23] Nagata, Y.; Bräysy, O., Edge assembly-based memetic algorithm for the capacitated vehicle routing problem, Networks, 54, 205-215 (2009) · Zbl 1206.90025
[24] Oliver, I.; Smith, D.; Holland, J., A study of permutation crossover operators on the traveling salesman problem, (JJ, G., Proceedings of the Second International Conference on Genetic Algorithms (1987), Lawrence Erlbaum: Lawrence Erlbaum Hillsdale, NJ), 224-230
[25] Powell, W. B.; Snow, W.; Cheung, R. K., Adaptive labeling algorithms for the dynamic assignment problem, Transportation Science, 34, 50-66 (2000) · Zbl 1002.90035
[26] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers and Operations Research, 31, 1985-2002 (2004) · Zbl 1100.90504
[27] Prins, C., Two memetic algorithms for heterogeneous fleet vehicle routing problems, Engineering Applications of Artificial Intelligence, 22, 916-928 (2009)
[28] Qin, H.; Lim, A.; Xu, D., The selective traveling salesman problem with regular working time windows, (Chien, B.-C.; Hong, T.-P., Opportunities and Challenges for Next-Generation Applied Intelligence. Opportunities and Challenges for Next-Generation Applied Intelligence, Studies in Computational Intelligence, vol. 214 (2009), Springer: Springer Berlin/Heidelberg), 291-296
[29] Savelsbergh, M.; Sol, M., Drive: dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511
[30] Souffriau, W.; Vansteenwegen, P.; Berghe, G. V.; Oudheusden, D. V., A path relinking approach for the team orienteering problem, Computers and Operations Research, 37, 1853-1859 (2010) · Zbl 1188.90221
[31] Tan, K.; Cheong, C.; Goh, C., Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation, European Journal of Operational Research, 177, 813-839 (2007) · Zbl 1110.90015
[32] Tang, H.; Miller-Hooks, E., A tabu search heuristic for the team orienteering problem, Computers and Operations Research, 32, 1379-1407 (2005) · Zbl 1122.90434
[33] Toth, P.; Vigo, D., The vehicle routing problem, SIAM. SIAM, Monographs on Discrete Mathematics and Applications (2002), SIAM: SIAM Philadelphia · Zbl 0979.00026
[34] Vansteenwegen, P.; Souffriau, W.; Oudheusden, D. V., The orienteering problem: a survey, European Journal of Operational Research, 209, 1-10 (2011) · Zbl 1205.90253
[35] Velasco, N.; Castagliola, P.; Dejax, P.; Guéret, C.; Prins, C., A memetic algorithm for a pick-up and delivery problem by helicopter, (Pereira, F.; Tavares, J., Bio-inspired Algorithms for the Vehicle Routing Problem. Bio-inspired Algorithms for the Vehicle Routing Problem, Studies in Computational Intelligence, vol. 161 (2009), Springer: Springer Berlin/Heidelberg), 173-190
[36] Villegas, J.; Prins, C.; Prodhon, C.; Medaglia, A.; Velasco, N., GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots, Engineering Applications of Artificial Intelligence, 23, 780-794 (2010)
[37] Xu, H.; Chen, Z.-L.; Rajagopal, S.; Arunapuram, S., Solving a practical pickup and delivery problem, Transportation Science, 37, 347-364 (2003)
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.