Solución “Wait and See” para el problema de ruteo abierto de vehículos con demandas estocásticas bajo un esquema de estimación por puntos

Alejandro Ospina Castaño; Eliana Mirledy Toro Ocampo; Ramón Alfonso Gallego Rendón

doi:10.24054/rcta.v3iEspecial.851

Authors

Alejandro Ospina Castaño Universidad Tecnológica de Pereira
Eliana Mirledy Toro Ocampo Universidad Tecnológica de Pereira
Ramón Alfonso Gallego Rendón Universidad Tecnológica de Pereira

DOI:

https://doi.org/10.24054/rcta.v3iEspecial.851

Keywords:

Demanda estocástica, estabilidad, método de estimación por 2 puntos, ruteo abierto, ruteo de vehículos, solución wait and see

Abstract

En este artículo se propone una técnica de solución estocástica bajo un esquema “wait and see” para abordar los siguientes problemas de ruteo con demandas estocásticas: CVRPSD y OVRPSD. La técnica de solución ha venido siendo aplicada en los últimos diez años al problema de flujo de carga estocástico en redes de distribución de energía eléctrica. El objetivo de la técnica es encontrar un valor esperado de costos operativos con su respectiva desviación estándar a partir de 2J escenarios probabilísticos desacoplados, siendo J el número de clientes en un escenario estocástico. Para su verificación se usan instancias propuestas en la literatura del VRP, observándose la influencia que ejerce en los costos operativos la estocasticidad de la demanda.

Downloads

Download data is not yet available.

References

Arias Hernández, A., Hincapié Isaza, R., & Gallego Rendón, R. (2014). Comparación de flujos de carga probabilísticos empleados en sistemas de distribución levemente enmallados. Scientia et Technica, 19(2), 153–162. https://doi.org/10.22517/23447214.9025

Bertsimas, D. J. (1992). A Vehicle Routing Problem with Stochastic Demand. Operations Research, 40(3), 574–585. https://doi.org/10.1287/opre.40.3.574

Birge, J., & Louveaux, F. (2011). Introduction to stochastic programming (second edi; S. S. in O. R. and F. Engineering, ed.).

Christiansen, C. H., & Lysgaard, J. (2007). A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research Letters. https://doi.org/10.1016/j.orl.2006.12.009

Fourer, R., Gay, D. M., & Kernighan, B. W. (1993). AMPL. A modeling language for mathematical programming.

Gauvin, C., Desaulniers, G., & Gendreau, M. (2014). A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Computers and Operations Research, 50, 141–153. https://doi.org/10.1016/j.cor.2014.03.028

Gendreau, M., & Laporte, G. (1996). EUROPEAN JOURNAL OF OPERATIONAL RESEARCH Stochastic vehicle routing. In European Journal of Operational Research (Vol. 88).

Hjorring, C., & Holt, J. (1999). New optimality cuts for a single-vehicle stochastic routing problem. Annals of Operations Research, 86, 569–584. https://doi.org/10.1023/A:1018995927636

Hong, H. (1998). An efficient point estimate method for probabilistic analysis. Reliability Engineering and System Safety, 59(3), 261– 267. https://doi.org/10.1016/S0951-8320(97)00071-9

Laporte, G., Louveaux, F., & Mercure, H. (1989). Models and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research, 39(1), 71–78. https://doi.org/10.1016/0377-2217(89)90354-8

Laporte, G., & Louveaux, F. V. (1998). Solving Stochastic Routing Problems with the Integer L-Shaped Method. In Fleet Management and Logistics (pp. 159–167). https://doi.org/10.1007/978-1-4615-5755-5_7

Laporte, G., Louveaux, F. V, & van Hamme, L. (2002). An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands. Operations Research, 50(3), 415–423. https://doi.org/10.1287/opre.50.3.415.7751

Lavorato, M., Franco, J. F., Rider, M. J., & Romero, R. (2012). Imposing radiality constraints in distribution system optimization problems. IEEE Transactions on Power Systems, 27(1), 172–180. https://doi.org/10.1109/TPWRS.2011.2161349

Ospina-Toro, D, Toro-Ocampo, E. M., & Gallego- Rendón, R. A. (2018). Solución Del MDVRP Usando El Algoritmo De Búsqueda Local Iterada. Revista Colombiana de Tecnologías de Avanzada, 1(31), 120–127. https://doi.org/https://doi.org/10.24054/16927257.v31.n31.2018.2774

Ospina Castaño, A., Toro-Ocampo, E. M., & Gallego-Rendón, R. A. (2019). Sensibility Analysis for the MULTI-Objective MDVRPPC that Considering Cost and Environmental Impact. Revista Colombiana de Tecnologias de Avanzada, 2(34), 8.

Perboli, G., Rosano, M., Saint-Guillain, M., & Rizzo, P. (2018). Simulation-optimisation framework for City Logistics: An application on multimodal last-mile delivery. IET Intelligent Transport Systems, 12(4), 262– 269. https://doi.org/10.1049/iet-its.2017.0357

Rei, W., Gendreau, M., & Soriano, P. (2010). A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands. Transportation Science, 44(1), 136–146. https://doi.org/10.1287/trsc.1090.0295

Rosenblueth, E. (1981). Two-point estimates in probabilities. Applied Mathematical Modelling, 5(5), 329–335. https://doi.org/10.1016/S0307-904X(81)80054-6

Secomandi, N., & Margot, F. (2008). Reoptimization Approaches for the Vehicle- Routing Problem with Stochastic Demands. Operations Research, 57(1), 214–230. https://doi.org/10.1287/opre.1080.0520

Stewart, W. R., & Golden, B. L. (1983). Stochastic vehicle routing: A comprehensive approach. European Journal of Operational Research, 14(4), 371–385. https://doi.org/10.1016/0377-2217(83)90237-0

Su, C. L. (2005). Probabilistic load-flow computation using point estimate method. IEEE Transactions on Power Systems, 20(4), 1843–1851. https://doi.org/10.1109/TPWRS.2005.857921

Toro-ocampo, E. M. (2016). Solución del problema de localización y ruteo usando un modelo matemático flexible y considerando efectos ambientales (Universidad Tecnológica de Pereira).