Artículo de Artículos de Investigación Científica y Tecnológica

Estado del arte del problema del ruteo de vehículos con componentes estocásticos

Artículo principal

Elsa Cristina González La Rotta
https://orcid.org/0000-0002-7054-5386
Oswaldo González Yazo
Mauricio Becerra Fernández
https://orcid.org/0000-0003-1060-2198
Enviado enero 11, 2018      Aceptado febrero 18, 2018      Publicado abril 2, 2018

Resumen

Este artículo presenta una revisión a la literatura del problema de ruteo de vehículos con componentes aleatorios: SVRP (Stochastics Vehicle Routing Problem). A pesar de la atención reciente hacia los problemas de ruteo y la variedad de estudios al respecto, con este trabajo se pretende enfatizar en una tipología especial, la cual presenta uno o múltiples parámetros de carácter probabilístico o estocástico. Después de una búsqueda rigurosa en las bases de datos Science Direct, EBSCO y Google Scholar, utilizando una ventana de tiempo de los últimos diez años y clasificando dichas investigaciones, se logra establecer un concepto particular para este tipo de problemas
de ruteo, sus clasificaciones y métodos de solución, lo cual resulta de gran ayuda para quienes desean investigar el tema, pues facilita la indagación acerca de enfoques de modelamiento y métodos de solución. Como conclusión principal, se determina que, debido a la complejidad de su solución, son menos los resultados y aplicaciones que contemplen este tipo de formulaciones, con respecto a las que presentan parámetros deterministas; ofreciendo un amplio campo de trabajo para trabajos posteriores.

[1] L. Bianchi et al., “Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands”, Journal of Mathematical Modelling and Algorithms, vol. 5, no. 1, pp. 91–110, 2005.

[2] M. Gendreau, Recent advances in stochastic vehicle routing, 2010.

[3] B. Golden & A. Assad, “Perspectives on vehicle routing: exciting new developments”, Operations Research, vol. 34, no. 5, pp. 803 – 810, 1986.

[4] K. Tan, C. Cheong & C. Goh, “Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation”, European Journal of Operational Research, vol. 177, no. 2, pp. 813 – 839, 2007.

[5] P. Toth & D. Vigo, The vehicle routing problem. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics, 2002.

[6] B. Golden et al., The Vehicle Routing Problem: Latest Advances and New Challenges, 2008.

[7] F. Merrill, “The traveling-salesman problem”, Operations Research, no. 1, pp. 61 – 75, 1996.

[8] V. Yepes, Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW, tesis doctoral, Universidad Politécnica de Valencia, 2002.

[9] E. Gonzalez-L, W. Adarme-J & J. Orjuela-C, “Modelo matemático estocástico para el problema de ruteo de vehículos en la recolección de productos perecederos”, DYNA, vol. 82, no. 189, pp. 199 – 206, 2015.

[10] M. Córdova et al., La integración de las tecnologías de la información y la comunicación (TIC) como estrategias de innovación pedagógica en el proceso de enseñanza aprendizaje en las asignaturas básicas impartidas en los centros de educación formal Fe y Alegría San Jose Pla. San Salvador, 2013. Disponible: http://ri.ues.edu.sv/4578/1/La integracióndelastecnologías.pdf

[11] P. Jaillet, Probabilistic traveling salesman problems, tesis doctoral, Massachusetts Institute of Technology, 1985.

[12] M. Gendreau, “A tabu search heuristic for the vehicle routing problem with stochastic demands and customers”, Operations Research, vol. 44, no. 3, pp. 469 – 477, 1996.

[13] F. Tillman, “The multiple terminal delivery problem with probabilistic demands”, Transportation Science, no. 3, pp. 192–204, 1969.

[14] W. R. Stewart JR & B. Golden, “Stochastic vehicle routing: A comprehensive approach”, European Journal of Operational Research, vol. 14, no. 4, pp. 371 – 385, 1983.

[15] V. Lambert, “Designing collection routes through bank branches”, Computer & Operations Research, no. 20, pp. 783 – 791, 1993.

[16] H. Lei et al., “The capacitated vehicle routing problem with stochastic demands and time windows”, Computers & Operations Research, vol. 38, no. 12, pp. 1775 – 1783,
2011.

[17] D. Bertsimas & G. Ryzin, “Stochastic and dynamic vehicle routing with general demand and interarrival time distributions”, Applied Probability Trust, vol. 25, no. 25, pp. 947 – 978, 1993.

[18] M. Gendreau, Recent Advances in Stochastic Vehicle Routing, 2010b.

[19] M. Gendreau, An Adaptive Large Neighborhood Search for a Vehicle Routing Problem with Multiple Trips, 2010a.

[20] N. Azi et al., “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles”, European Journal of Operational Research, vol. 202, no. 3, pp. 756 – 763, 2010.

[21] L. C. Coelho, “The exact solution of several classes of inventory-routing problems”, Computers & Operations Research, vol. 40, no. 2, pp. 558–565, 2013.

[22] L. B. Rocha et al., “Una revisión al estado del arte del problema de ruteo de vehículos: evolución histórica y métodos de solución”, Ingeniería, vol. 16, no. 2, pp. 35–55, 2011.

[23] B. Golden & W. Stewart, “Vehicle routing with probabilistic demands”, Computer Science and Statistics Tenth Annual Symposium on the Interface, D. Hoyben and D. Fife, Eds. NBS Special Publication 503, National Bureau of Standards: Washington, D.C., pp. 252 – 259, 1978.

[24] B. Golden & J. Yee, “A framework for probabilistic vehicle routing”, AIEE Transact, vol. 11, no. 2, pp. 109 – 112, 1979.

[25] J. Yee & B. Golden, “A note on determining operating strategies for probabilistic vehicle routing”, Naval Research Logistics, no. 27, pp. 159 – 163, 1980.

[26] W. Stewart & B. Golden, “A chance-constrained approach to the stochastic vehicle routing problem”, In G. Boseman, J. Vora. Proceedings of 1980 Northeast aids Conference: Philadelphia, pp. 33 – 35, 1980.

[27] W. Stewart, New algorithm for deterministic and stochastic vehicle routing problem, Tesis Post Doctoral Report No. 81 - 009, University of Maryland at College Park, MD, 1981.

[28] W. Stewart et al., “A survey of stochastic vehicle routing”, ieee, pp. 229 – 232, 1982.

[29] L. Bodin et al., “Routing and schedulling of vehicles and crews. The state of the art”, Computers & Operations Research, vol. 10, no. 2, pp. 63 – 211, 1983.

[30] A. Jezequel, Probabilistic vehicle routing problems, Tesis de maestría, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1985.

[31] M. Dror & P. Trudeau, “Stochastic vehicle routing with modified savings algorithm”.,European Journal of Operational Research, vol. 23, no. 2, pp. 228 – 235, 1986.

[32] F. Rossi & I. Gavioli, “Aspects of heuristic method in the probabilistic traveling salesman problem”, In Advanced School on Stochastics in Combinatorial Optimization, G. Andreatta, F. Mason and P. Serafini, Eds. World Scientific Publisher: Singapore, pp. 214-227, 1987.

[33] P. Jaillet, “A priori solution of a traveling salesman problem in which a random subset of the customers are visited”, Operations Research, vol. 36, no. 6, pp. 929 – 936, 1987.

[34] D. Bertsimas, Probabilistic combinatorial optimization problems, Tesis doctoral, Massachusetts Institute of Technology, 1988.

[35] P. Jaillet & A. Odoni, “The probabilistic vehicle routing problem”, In Vehicle Routing; Methods and Studies, B.L. Golden and A. A. Assad, Eds. North Holland: Amsterdam, 1988.

[36] G. Laporte et al., “Models and exact solutions for a class of stochastic location-routing problems”, European Journal of Operational Research, vol. 39, no. 1, pp. 71 – 78, 1989.

[37] M. Dror et al., “Vehicle routing with stochastic Demands: properties and solution frameworks”, Transportation Science, vol. 23, no. 3, pp. 166 – 177, 1989.

[38] C. Waters, “Vehicle-scheduling problems with uncertainty and omitted customers”, Operational Research Society, vol. 40, no. 12, pp. 1099 – 1100, 1989.

[39] G. Laporte & F. Louveaux, “Formulations and bounds for the stochatsic capacitated vehicle routing problem with uncertain supplies”. Economic Decision-Making Games, Economics and Optimisation, Ch, Elsevier Science Publ. B. V., pp. 443 – 455, 1990.

[40] D. Bertsimas et al., “A priori optimization”, Operations Research, vol. 38, no.6, pp. 1019 – 1033, 1990.

[41] D. Bertsimas et al., “Computational approaches to stochastic vehicle routing problems”, WP# 3285-91-MSA, pp. 1 – 35, 1991.

[42] P. Trudeau & M. Dror, “Stochastic inventory routing: route desing with stockouts and route failures”, Transportation Science, vol. 26, no. 3, pp. 171 – 184, 1992.

[43] C. Bastian & A. Rinnooy, “The stochastic vehicle routing problem revisited”, European Journal of Operational Research, vol. 56, no. 3, pp. 407 – 412, 1992.

[44] D. Bertsimas, “A vehicle routing problem with stochastic demand”, Operations Research, vol. 40, no. 3, pp. 574 – 585, 1992.

[45] W. Benton & M. Rossetti, “The vehicle scheduling problem with intermittent customer demands”, Computers & Operations Research, vol. 19, no. 6, pp. 521 – 531, 1992.

[46] G. Laporte et al., “The vehicle routing problem with stochastic travel times”, Transportation Science, vol. 26, no. 3, pp. 161 – 170, 1992.

[47] B. Bouzaiene, “Vehicle routing with stochastic demands and split deliveries”, Foundations of Conputing and Decision Sciences, vol. 18, no. 1, 1993.

[48] M. Dror et al., “Vehicle routing with stochastic demands and restricted failures”, Methods and Models Od Operations Research, no. 37, pp. 273–283, 1993.

[49] G. Laporte et al. “A priori optimization of the probabilistic traveling salesman roblem”, Operations Research, vol. 42, no. 3, pp. 543 – 549, 1994.

[50] R. Séguin, Problémes stochastiques de tournées de véhicules, Tesis doctoral, Université de Montréal, 1994.

[51] M. Gendreau et al., “An exact algorithm for the vehicle routing problem with stochastic customers and demands”, Transportation Science, vol. 29, no. 2, pp. 143 – 155, 1995.

[52] M. Gendreau, “Stochastic vehicle routing”, European Journal of Operational Research, vol. 88, no. 6, pp. 13 - 22, January, 1996.

[53] G. Laporte & F. Louveaux, “Solving stochastic routing problems with the integer L-Shaped method”, Fleet Management and Logistics, pp. 159–167, 1998.

[54] W. Yang et al., “Stochastic vehicle routing problem with restocking”, Transportation Science informs, vol. 34, no. 1, pp. 99 – 112, 2000.

[55] N. Secomandi, “A rollout policy for the vehicle routing problem with stochastic demands”, Operations Research informs, vol. 49, no. 5, pp. 796 – 802, 2001.

[56] C. Christiansen & J. Lysgaard, “A branch-andprice algorithm for the capacitated vehicle routing problem with stochastic demands”, Operations Research Letters, no. 35, pp. 773 – 781, 2007.

[57] W. Rei et al., “A hybrid Monte Carlo local branching algorithm for the single vehicle routing problem with stochastic demands”, Transportation Science, vol. 44, no. 1, pp. 136 – 146, 2010.

[58] A. Erera et al., “The vehicle routing problem with stochastic demand and duration constraints”, Transportation Science, vol. 44, no. 4, pp. 474 – 492, 2010.

[59] V. Pillac et al., “A review of dynamic vehicle routing problems”, European Journal of Operational Research, vol. 225, no. 1, 1 – 11, 2013.

[60] M. Wen et al., The dynamic multi-period vehicle routing problem, Computers & Operations Research, vol. 37, no. 9, pp. 1615 – 1623, 2010.

Detalles de artículos

Cómo citar
González La Rotta, E., González Yazo, O., & Becerra Fernández, M. (2018). Estado del arte del problema del ruteo de vehículos con componentes estocásticos. INVENTUM, 13(24), 2-14. https://doi.org/10.26620/uniminuto.inventum.13.24.2018.2-14
Sección
Artículos de Investigación Científica y Tecnológica