The capacitated vehicle routing problem with soft time windows and stochastic travel times
Abstract
A full multiobjective approach is employed in this paper to deal with a stochastic multiobjective capacitated vehicle routing problem (CVRP). In this version of the problem, the demand is considered to be deterministic, but the travel times are assumed to be stochastic. A soft time window is tied to every customer and there is a penalty for starting the service outside the time window. Two objectives are minimized, the total length and the time window penalty. The suggested solution method includes a non-dominated sorting genetic algorithm (NSGA) together with a variable neighborhood search (VNS) heuristic. It was tested on instances from the literature and compared to a previous solution approach. The suggested method is able to find solutions that dominate some of the previously best known stochastic multiobjective CVRP solutions.
Keywords
genetic algorithms, heuristic algorithms, multiobjective programming, random processes, vehicle routing
References
[1] G. B. Dantzig, and J. H. Ramser, "The truck dispatching problem," Management Science, vol. 6 (1), pp. 80-91, 1959. DOI: https://doi.org/10.1287/mnsc.6.1.80.
[2] P. Toth, and D. Vigo, "Models, relaxations and exact approaches for the capacitated vehicle routing problem," Discrete Applied Mathematics, vol. 123 (1-3), pp. 487–512, 2002. DOI: https://doi.org/10.1016/S0166-218X(01)00351-1.
[3] M. Gendreau, G. Laporte, and R. Seguin, "Stochastic vehicle routing," European Journal of Operational Research, vol. 88 (1), pp. 3-12, Jan. 1996. DOI: https://doi.org/10.1016/0377-2217(95)00050-X.
[4] J. Oyola, H. Arntzen, and D. L. Woodruff, "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, vol. 7 (3), p. 193–221, Sep. 2018. DOI: https://doi.org/10.1007/s13676-016-0100-5.
[5] R. A. Russell, and T. L. Urban, "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, vol. 59 (9), pp. 1220-1228, Sep. 2008. DOI: https://doi.org/10.1057/palgrave.jors.2602465.
[6] J. Current, and H. Min, "Multiobjective design of transportation networks: Taxonomy and annotation," European Journal of Operational Research, vol. 26 (2), pp. 187-201, Aug. 1986. DOI: https://doi.org/10.1016/0377-2217(86)90180-3.
[7] Y. Collette, and P. Siarry, Multiobjective optimization: principles and case studies, Berlin: Springer, 2003.
[8] N. Jozefowiez, F. Semet, and E. Talbi, "Target aiming pareto search and its application to the vehicle routing problem with route balancing," Journal of Heuristics, vol. 13 (5), pp. 455-469, Sep. 2007. DOI: https://doi.org/10.1007/s10732-007-9022-6.
[9] R. Caballero, E. Cerdá, M. D. M. Muñoz, and L. Rey, "Stochastic approach versus multiobjective approach for obtaining efficient solutions in stochastic multiobjective programming problems," European Journal of Operational Research, vol. 158 (3), pp. 633-648, Nov. 2004. DOI: https://doi.org/10.1016/S0377-2217(03)00371-0.
[10] X. Li, P. Tian, and S. C. Leung, "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, vol. 125 (1), pp. 137-145, May. 2010. DOI: https://doi.org/10.1016/j.ijpe.2010.01.013.
[11] H. Lei, G. Laporte, and B. Guo, "A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times," TOP, vol. 20 (1), pp. 99 - 118, Apr. 2012. DOI: https://doi.org/10.1007/s11750-011-0188-6.
[12] T. Zhang, W. Chaovalitwongse, and Y. Zhang, "Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries," Computers & Operations Research, vol. 39 (10), pp. 2277-2290, Oct. 2012. DOI: https://doi.org/10.1016/j.cor.2011.11.021.
[13] D. Taş, N. Dellaert, T. Van Woensel, and T. de Kok, "Vehicle routing problem with stochastic travel times including soft time windows and service costs," Computers & Operations Research, vol. 40 (1), pp. 214-224, Jan. 2013. DOI: https://doi.org/10.1016/j.cor.2012.06.008.
[14] D. Taş, M. Gendreau, N. Dellaert, T. Van Woensel, and A. de Kok, "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, vol. 236 (3), pp. 789-799, Aug. 2014. DOI: https://doi.org/10.1016/j.ejor.2013.05.024.
[15] A. S. Kenyon, and D. P. Morton, "Stochastic vehicle routing with random travel times," Transportation Science, vol. 37 (1), pp. 69-82, Feb. 2003. DOI: https://doi.org/10.1287/trsc.37.1.69.12820.
[16] C. Lee, K. Lee, and S. Park, "Robust vehicle routing problem with deadlines and travel time/demand uncertainty," Journal of the Operational Research Society, vol. 63 (9), pp. 1294-1306, Sep. 2012. DOI: https://doi.org/10.1057/jors.2011.136.
[17] M. Gendreau, O. Jabali, and W. Rei, "Stochastic vehicle routing problems.," in Vehicle Routing: Problems, Methods, and Applications, Philadelphia, Society for Industrial and Applied Mathematics, Nov. 2014, pp. 213-239. DOI: https://doi.org/10.1137/1.9781611973594.ch8.
[18] J. Oyola, H. Arntzen, and D. L. Woodruff, "The stochastic vehicle routing problem, a literature review, part II: solution methods," EURO Journal on Transportation and Logistics, vol. 6 (4), p. 349–388, Dec. 2017. DOI: https://doi.org/10.1007/s13676-016-0099-7.
[19] A. Ahmadi-Javid, and A. H. Seddighi, "A location-routing problem with disruption risk," Transportation Research Part E Logistics and Transportation Review, vol. 53, pp. 63-82, Jul. 2013. DOI: https://doi.org/10.1016/j.tre.2013.02.002.
[20] A. Juan, J. Faulin, S. Grasman, D. Riera, J. Marull, and C. Mendez, "Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands," Transportation Research Part C Emerging Technologies, vol. 19 (5), pp. 751-765, Aug. 2011. DOI: https://doi.org/10.1016/j.trc.2010.09.007.
[21] K. Tan, C. Cheong, and C. Goh, "Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation," European Journal of Operational Research, vol. 177 (2), pp. 813-839, Mar. 2007. DOI: https://doi.org/10.1016/j.ejor.2005.12.029.
[22] N. Jozefowiez, F. Semet, and E. Talbi, "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, vol. 195 (3), pp. 761-769, Jun. 2009. DOI: https://doi.org/10.1016/j.ejor.2007.06.065.
[23] J. E. Mendoza, B. Castanier, C. Gueret, A. L. Medaglia, and N. Velasco, "A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands," Computers & Operations Research, vol. 37 (11), pp. 1886-1898, Nov. 2010. DOI: https://doi.org/10.1016/j.cor.2009.06.015.
[24] K. Sörensen, and M. Sevaux, "A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling," Journal of Mathematical Modelling and Algorithms, vol. 8 (4), pp. 387-407, Dec. 2009. DOI: https://doi.org/10.1007/s10852-009-9113-5.
[25] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. Evol. Comp, vol. 6 (2), pp. 182-197, Apr. 2002. DOI: https://doi.org/10.1109/4235.996017.
[26] C. Prins, "A simple and effective evolutionary algorithm for the vehicle routing problem," Computers & Operations Research, vol. 31 (12), pp. 1985-2002, Oct. 2004. DOI: https://doi.org/10.1016/S0305-0548(03)00158-8.
[27] W.-C. Chiang, and R. A. Russell, "A metaheuristic for the vehicle-routeing problem with soft time windows," Journal of the Operational Research Society, vol. 55 (12), pp. 1298-1310, Dec. 2004. DOI: https://doi.org/10.1057/palgrave.jors.2601791.
[28] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, vol. 35 (2), pp. 254-265, 1987. DOI: https://doi.org/10.1287/opre.35.2.254.
[29] J.-Y. Potvin, and S. Bengio, "The vehicle routing problem with time windows part II: Genetic search," INFORMS Journal on Computing, vol. 8 (2), pp. 165-172, May. 1996. DOI: https://doi.org/10.1287/ijoc.8.2.165.
[30] P. Venkataraman, Applied Optimization with MATLAB Programming, Hoboken: John Wiley & Sons Inc., 2009.
[31] J. Mendoza, L.-M. Rousseau, and J. Villegas, "A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints," Journal of Heuristics, vol. 22 (4), p. 539–566, Aug. 2016. DOI: https://doi.org/10.1007/s10732-015-9281-6.
[32] M. Kaut, and S. W. Wallace, "Evaluation of scenario-generation methods for stochastic programming," Pacific Journal of Optimization, vol. 3 (2), pp. 257-271, 2007.
[33] J. D. Knowles, "Local-search and hybrid evolutionary algorithms for Pareto optimization," Ph. D. Dissertation, University of Reading, Reading, 2002.
[34] P. Mateo, and I. Alberto, "A mutation operator based on a pareto ranking for multi-objective evolutionary algorithms," Journal of Heuristics, vol. 18 (1), pp. 53-89, Feb. 2012. DOI: https://doi.org/10.1007/s10732-011-9156-4.