Solución del problema de ruteo de vehículos con demandas estocásticas mediante la optimización por espiral
Resumen
El artículo presenta los resultados del estudio de un problema de ruteo de vehículos con demandas estocásticas (Vehicle Routing Problem with Stochastic Demands, VRPSD), en el cual la única variable estocástica es la demanda de los clientes, esta variable sigue una distribución discreta, y su valor solo es conocido cuando el vehículo llega a la ubicación del cliente. Para su solución, se implementó la metaheurística denominada Optimización por Espiral, con el enfoque a priori y la estrategia de reabastecimiento preventivo para un solo vehículo. Para mejorar el método se inicializaron las rutas mediante la heurística del vecino más cercano, y posteriormente se utilizó la mutación, un operador evolutivo, para ampliar la zona de exploración de los puntos de búsqueda. Adicionalmente, se utilizó el intercambio 2-Opt, una heurística de búsqueda local, con el fin de intensificar la búsqueda en la vecindad de soluciones óptimas encontradas. Por otra parte, se realizó un diseño de experimentos 23, con el fin de determinar la influencia de cada factor en la función objetivo. Este análisis se llevó a cabo en 8 instancias diferentes que fueron diseñadas y desarrolladas por Galván et al. [1]. Finalmente, se compararon los resultados obtenidos con los arrojados por el algoritmo híbrido EPSO, con el objetivo de probar la eficiencia y eficacia del algoritmo desarrollado. Esta comparación evidenció que el método propuesto obtiene mejores resultados en todas las instancias, con mejoras de hasta el 5,71 %.Palabras clave
demandas estocásticas, metaheurísticas, optimización por espiral, ruteo de vehículos
Citas
- S. Galván, J. Arias and H. Lamos, “Optimización por simulación basado en un sistema evolutivo de optimización de enjambre de partículas para el problema de ruteo de vehículos con demandas estocásticas”. Tesis de Maestría. Universidad Industrial de Santander, Bucaramanga, Colombia. 2013.
- R. H. Ballou, Logística. Administración de la cadena de suministro. México: Prentice Hall, 2004.
- J. Sourabh and K. Sarabjit, “Comparative analysis of two different heuristics for model of VRP”, Advances in Computing and Communication Engineering (ICACCE), Dehradun (India), pp. 124-127, May. 2015. DOI: http://dx.doi.org/10.1109/ICACCE.2015.87. DOI: https://doi.org/10.1109/ICACCE.2015.87
- J. M. Daza, J. R. Montoya and F. Narducci, “Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases”, Revista EIA, n° 12, pp. 23-38. Dec. 2009.
- N. Secomandi, “A rollout policy for the vehicle routing problem with stochastic demands”, Operations Research, vol. 49 (5), pp. 796-802, Oct. 2001. DOI: http://dx.doi.org/10.1287/opre.49.5.796.10608. DOI: https://doi.org/10.1287/opre.49.5.796.10608
- M. Dror, G. Laporte and P. Trudeau, “Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks”, Transportation Science, vol. 23 (3), Aug. 1989. DOI: http://dx.doi.org/10.1287/trsc.23.3.166. DOI: https://doi.org/10.1287/trsc.23.3.166
- K. Tamura and K. Yasuda, “Spiral Optimization. A new multipoint search method”, Systems, Man, and Cybernetics (SMC), Anchorage (Alaska), pp. 1759-1764, Oct. 2011. DOI: http://dx.doi.org/ 10.1109/ICSMC.2011.6083926. DOI: https://doi.org/10.1109/ICSMC.2011.6083926
- S. Geetha, G. Poonthalir and P. T. Vanathi, “A Hybrid Particle Swarm Optimization with Genetic Operators for Vehicle Routing Problem”, Journal of Advances in Information Technology, vol. 1 (4), pp. 181–188, Nov. 2010. DOI: http://dx.doi.org/10.4304/jait.1.4.181- DOI: https://doi.org/10.4304/jait.1.4.181-188
- B. Liu, L. Wang and Y. Jin, “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers”, Computers & Operations Research, vol. 35 (9), pp. 2791-2806, Sep. 2008. DOI: http://dx.doi.org/10.1016/j.cor.2006.12.013. DOI: https://doi.org/10.1016/j.cor.2006.12.013
Descargas
Los datos de descargas todavía no están disponibles.