The stochastics vehicle routing problem: state of the art
Article Sidebar
Downloads
Article Details
Altmetrics
Se solicita a los autores que diligencien el documento de cesión de derechos de autor sobre el artículo, para que sea posible su edición, publicación y distribución en cualquier medio y modalidad: medios electrónicos, CD ROM, impresos o cualquier otra forma, con fines exclusivamente científicos, educativos y culturales
- La obra pertenece a UNIMINUTO.
- Dada la naturaleza de UNIMINUTO como Institución de Educación Superior, con un modelo universitario innovador para ofrecer Educación de alta calidad, de fácil acceso, integral y flexible; para formar profesionales altamente competentes, éticamente responsables y líderes de procesos de transformación social, EL CEDENTE ha decidido ceder los derechos patrimoniales de su OBRA, que adelante se detalla para que sea explotado por ésta
- El querer de EL CEDENTE es ceder a título gratuito los derechos patrimoniales de la OBRA a UNIMINUTO con fines académicos.
Main Article Content
Abstract
This article presents a literature review of the Stochastic Vehicle Routing Problem SVRP. Despite the recent attention to the problems of routing and the existing variety of studies in this regard, in this research we emphasize a special typology, which account for one or multiple parameters of a probabilistic or stochastic nature. The rigorous revision of the state of the art was conducted using science direct, ebsco and google scholar databases. Considering a time window of the last 10 years, and classifying
the results, allowed us to establish a particular conceptualization for this types of routing problems, their classifications and solution methods. This constitutes a tool of great help for those researching on the subject, as it facilitates the understanding of the modelling approaches and solution methods. As a main conclusion, due to the complexity of svrp solutions, there are less results and applications that contemplate this type of formulations, as opposed to those contemplating deterministic parameters. Offering a wide field for future research in the field.
References
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.