El problema de enrutamiento de vehículos con ventanas de tiempo suave y tiempos de viaje estocásticos
Resumen
Un enfoque totalmente multiobjetivo es usado en este artículo para estudiar un problema de enrutamiento de vehículos capacitado (CVRP), estocástico y multiobjetivo. En esta versión del problema, la demanda se considera determinística, pero los tiempos de viaje son asumidos como estocásticos. Una ventana de tiempo suave es asociada con cada cliente y hay una penalización por iniciar el servicio por fuera de esta. Dos objetivos son minimizados, la distancia total recorrida y la penalización por no cumplir con la ventana de tiempo. El método de solución propuesto incluye un algoritmo genético con ordenamiento no dominado (NSGA) y una heurística de búsqueda de vecindad variable (VNS). Se probó en problemas de la literatura y se comparó con un enfoque previo de solución. El método propuesto es capaz de encontrar soluciones que dominan algunas de las mejores soluciones conocidas para el CVRP multiobjetivo.
Palabras clave
algoritmos genéticos, algoritmos heurísticos, optimización multiobjetivo, proceso aleatorio, ruteo de vehículos
Referencias
[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.