The capacitated vehicle routing problem with soft time windows and stochastic travel times

El problema de enrutamiento de vehículos con ventanas de tiempo suave y tiempos de viaje estocásticos

Main Article Content

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:

Downloads

Download data is not yet available.

Article Details

References (SEE)

[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.

Citado por: