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

Autores/as

  • 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

Palabras clave:

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

Resumen

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.

Citas

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).

Descargas

Publicado

2021-04-13 — Actualizado el 2020-08-14

Versiones

Cómo citar

Ospina Castaño, A., Toro Ocampo, E. M., & Gallego Rendón , R. A. (2020). 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. REVISTA COLOMBIANA DE TECNOLOGIAS DE AVANZADA (RCTA), 3(2), 25–32. https://doi.org/10.24054/rcta.v3iEspecial.851 (Original work published 13 de abril de 2021)

Número

Vol. 3 (2020): Edición Especial

Sección

Artículos

Licencia

Derechos de autor 2020 REVISTA COLOMBIANA DE TECNOLOGIAS DE AVANZADA

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.

Los autores que publiquen en esta revista aceptan las siguientes condiciones:

  1. Los autores conservan los derechos morales de autor y otorgan a la revista el derecho de la primera publicación del trabajo. Este trabajo se licencia bajo la Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0 DEED), que permite a terceros utilizar el trabajo siempre que se dé crédito adecuado a los autores y a la primera publicación en esta revista. No se permite el uso comercial de la obra y no se pueden crear obras derivadas.

  2. Los autores pueden celebrar acuerdos contractuales adicionales e independientes para la distribución no exclusiva de la versión del artículo publicado en esta revista (por ejemplo, incluirlo en un repositorio institucional o publicarlo en un libro), siempre que se indique claramente que el trabajo se publicó por primera vez en esta revista.

  3. Se permite y se recomienda a los autores publicar su trabajo en Internet (por ejemplo, en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado.