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

Contenido principal del artículo

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

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.

Citas

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.

M. Gendreau, Recent advances in stochastic vehicle routing, 2010.

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

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.

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

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

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

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.

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.

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

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

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.

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

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.

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

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,

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.

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

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

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.

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

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.

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.

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

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

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.

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.

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

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.

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

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

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.

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.

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

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.

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.

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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.

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.

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

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

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