Revista UIS Ingenierías

Vol. 21 Núm. 3 (2022): Revista UIS Ingenierías
Artículos

Un algoritmo ALNS para el VRPD en la distribución de última milla

PDF
  • Jeamy Sebastian Tarazona-Jimenez,
  • Jhon Jimenez-Romero ,
  • Karin Aguilar-Imitola ,
  • Henry Lamos-Díaz
Jeamy Sebastian Tarazona-Jimenez
Universidad Industrial de Santander
Jhon Jimenez-Romero
Universidad Industrial de Santander
Karin Aguilar-Imitola
Universidad Industrial de Santander
Henry Lamos-Díaz
Universidad Industrial de Santander
DOI: https://doi.org/10.18273/revuin.v21n3-2022012

Publicado 2022-10-02

Palabras clave

  • Problema de Ruteo de Vehículos con Drones,
  • Adaptive Large Neighborhood Search,
  • UAV,
  • drones,
  • vehículos,
  • Remoción Aleatoria,
  • Peor Remoción,
  • Cluster Removal,
  • Inserción Codiciosa con Función de Ruido,
  • Regret-n Insertion,
  • Closest Insertion
    • ...Más
    Menos

Cómo citar

Tarazona-Jimenez, J. S., Jimenez-Romero , J. ., Aguilar-Imitola , K. ., & Lamos-Díaz , H. . (2022). Un algoritmo ALNS para el VRPD en la distribución de última milla . Revista UIS Ingenierías, 21(3), 153–176. https://doi.org/10.18273/revuin.v21n3-2022012

Derechos de autor 2022 Revista UIS Ingenierías

Creative Commons License

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

Resumen

Los vehículos aéreos no tripulados más conocidos como drones han despertado gran interés en los últimos años, teniendo aplicaciones en operaciones militares y civiles, recientemente se ha investigado acerca de las ventajas de su uso en la distribución de paquetes. En esta investigación se aborda un Problema de Ruteo de Vehículos con Drones (VRPD) enfocado a la distribución de última milla, en el cual los drones y camiones pueden trabajan de manera simultánea, considerando un límite de capacidad para el camión y el dron, así como restricciones asociadas al tiempo de la ruta. Dentro de la formulación matemática se propone una ecuación de velocidad de vuelo del dron y se restringen las rutas a un porcentaje límite de batería disponible para evitar mal funcionamiento en el aire. Para resolver esta formulación se usa el algoritmo Adaptive Large Neighborhood Search (ALNS), que es validado usando instancias propuestas en la literatura. Además, se verifica cómo varía la función objetivo de la solución inicial mediante la utilización de las heurísticas de destrucción y reparación, finalmente se realiza un análisis de sensibilidad para algunos parámetros del algoritmo y características de los drones; realizando conclusiones de los resultados arrojados y efectuando recomendaciones para futuras investigaciones.

PDF

Descargas

Los datos de descargas todavía no están disponibles.

Referencias

  1. Brown Eric, “E-commerce spurs innovation in last- mile logistics”, MIT News, 2019, Consultado: jul. 07, 2022. [En línea]. Disponible en: https://news.mit.edu/2018/mit-e-commerce-spurs-innovations-last-mile-logistics-0904
  2. “Ecommerce: Evolución y perspectivas 2020 | COMUNICAWEB”. [En línea]. Disponible en: https://comunica-web.com/blog/marketing-digital/ecommerce-datos-evolucion/
  3. B. Balcik, B. M. Beamon, K. Smilowitz, “Last mile distribution in humanitarian relief”, J. Intell. Transp. Syst. Technol. Planning, Oper., vol. 12, núm. 2, pp. 51–63, abr. 2008, doi: https://doi.org/10.1080/15472450802023329
  4. B. Minten, B. Koru, D. Stifel, “The last mile(s) in modern input distribution: Pricing, profitability, and adoption”, Agric. Econ., vol. 44, núm. 6, pp. 629–646, nov. 2013, doi: https://doi.org/10.1111/AGEC.12078
  5. “El nuevo mapa de rescates con drones de DJI - ITSitio”. https://www.itsitio.com/co/nuevo-mapa-rescates-drones-dji/
  6. C. Rose, “Jeff Bezos de Amazon mira hacia el futuro - CBS News”, 2013. https://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future
  7. Bonn, “DHL Press Release English”, 2014. https://www.reutersevents.com/supplychain/3pl/dhl-parcelcopter-launches-initial-operations-research-purposes
  8. “Google tests drone deliveries in Project Wing trials - BBC News”. https://www.bbc.com/news/technology-28964260
  9. C. C. Murray, A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transp. Res. Part C Emerg. Technol., vol. 54, pp. 86–109, 2015, doi: https://doi.org/10.1016/J.TRC.2015.03.005
  10. I. or its affiliates Amazon.com, “Amazon.com: Prime Air”, 2016. https://www.aboutamazon.com/news/transportation/amazon-prime-air-prepares-for-drone-deliveries
  11. G. B. Dantzig, J. H. Ramser, “The Truck Dispatching Problem”, Source Manag. Sci., vol. 6, núm. 1, pp. 80–91, 1959, doi: https://doi.org/10.1287/mnsc.6.1.80
  12. S. Erdoĝan, E. Miller-Hooks, “A Green Vehicle Routing Problem”, Transp. Res. Part E Logist. Transp. Rev., vol. 48, núm. 1, pp. 100–114, 2012, doi: https://doi.org/10.1016/J.TRE.2011.08.001
  13. B. Golden, A. Assad, L. Levy, F. Gheysens, “The fleet size and mix vehicle routing problem”, Comput. Oper. Res., vol. 11, núm. 1, pp. 49–66, 1984, doi: https://doi.org/10.1016/0305-0548(84)90007-8
  14. S. Erdoĝan, E. Miller-Hooks, “A Green Vehicle Routing Problem”, Transp. Res. Part E Logist. Transp. Rev., vol. 48(1), pp. 100–114, 2012, doi: https://doi.org/10.1016/J.TRE.2011.08.001
  15. J. Lin, W. Zhou, O. Wolfson, “Electric Vehicle Routing Problem”, Transp. Res. Procedia, vol. 12, pp. 508–521, ene. 2016, doi: https://doi.org/10.1016/J.TRPRO.2016.02.007
  16. B. N. Coelho et al., “A multi-objective green UAV routing problem”, Comput. Oper. Res., vol. 88, pp. 306–315, dic. 2017, doi: https://doi.org/10.1016/J.COR.2017.04.011
  17. N. Boysen, D. Briskorn, S. Fedtke, S. Schwerdfeger, “Drone delivery from trucks: Drone scheduling for given truck routes”, Networks, 2018, doi: https://doi.org/10.1002/net.21847
  18. D. Sacramento, D. Pisinger, S. Ropke, “An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones”, Transp. Res. Part C Emerg. Technol., vol. 102, pp. 289–315, 2019, doi: https://doi.org/10.1016/J.TRC.2019.02.018
  19. “Existencias: Vehicle Routing Problem with Drones Instances”. https://zenodo.ups.edu.ec/Record/zen-1568853
  20. “Uso y cuidado de baterías para drones”. https://elvuelodeldrone.com/blog-de-drones/uso-cuidado-baterias-para-drones/
  21. P. Shaw, “Using constraint programming and local search methods to solve vehicle routing problems”, Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 1520, pp. 417–431, 1998, doi: https://doi.org/10.1007/3-540-49481-2_30
  22. W. Li, Y. Wu, P. N. R. Kumar, y K. Li, “Engineering Optimization Multi-trip vehicle routing problem with order release time Multi-trip vehicle routing problem with order release time”, Optim. Ing., 2019, doi: https://doi.org/10.1080/0305215X.2019.1642880
  23. H. Paessens, “The savings algorithm for the vehicle routing problem”, Eur. J. Oper. Res., vol. 34, núm. 3, pp. 336–344, 1988, doi: https://doi.org/10.1016/0377-2217(88)90154-3
  24. T. Pichpibul, R. Kawtummachai, “A heuristic approach based on Clarke-Wright algorithm for open vehicle routing problem”, Sci. World J., vol. 2013, 2013, doi: https://doi.org/10.1155/2013/874349
  25. T. J. Gaskell, “Bases for Vehicle Fleet Scheduling”, J. Oper. Res. Soc., vol. 18, núm. 3, pp. 281–295, sep. 1967, doi: https://doi.org/10.1057/jors.1967.44
  26. P. C. Yellow, “A Computational Modification to the Savings Method of Vehicle Scheduling”, J. Oper. Res. Soc., vol. 21, núm. 2, pp. 281–283, 1970, doi: https://doi.org/10.1057/JORS.1970.52
  27. D. Pisinger, S. Ropke, “A general heuristic for vehicle routing problems”, Comput. Oper. Res., vol. 34, núm. 8, pp. 2403–2435, 2007, doi: https://doi.org/10.1016/J.COR.2005.09.012
  28. S. Ropke, D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”, Transp. Sci., vol. 40, núm. 4, pp. 455–472, 2006, doi: https://doi.org/10.1287/trsc.1050.0135
  29. R. Lutz, “Adaptive Large Neighborhood Search”, 2014, [En línea]. Disponible en: http://dx.doi.org/10.18725/OPARU-3237
  30. S. Ropke, “Heuristic and exact algorithms for vehicle routing problems”, 2006. [En línea]. Disponible en: https://backend.orbit.dtu.dk/ws/portalfiles/portal/3155278/Heuristic+and+exact+algorithms+for+vehicle+routing+problems_Ropke.pdf
  31. S. Ropke, D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”, Transp. Sci., vol. 40, núm. 4, pp. 455–472, 2006, doi: https://doi.org/10.1287/TRSC.1050.0135
  32. A. T. Phan, T. D. Nguyen, Q. D. Pham, “Traveling salesman problem with multiple drones”, ACM Int. Conf. Proceeding Ser., pp. 46–53, 2018, doi: https://doi.org/10.1145/3287921.3287932
  33. M. Keskin, B. Catay, “Partial recharge strategies for the electric vehicle routing problem with time windows”, Transp. Res. Part C Emerg. Technol., vol. 65, pp. 111–127, abr. 2016, doi: https://doi.org/10.1016/j.trc.2016.01.013
  34. D. Pisinger, S. Ropke, “A general heuristic for vehicle routing problems”, Comput. Oper. Res., vol. 34, núm. 8, pp. 2403–2435, 2007, doi: https://doi.org/10.1016/j.cor.2005.09.012
  35. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, núm. 4598, pp. 671–680, may 1983, doi: https://doi.org/10.1126/science.220.4598.671
  36. V. Černý, “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”, J. Optim. Theory Appl., vol. 45, núm. 1, pp. 41–51, 1985, doi: https://doi.org/10.1007/BF00940812
  37. D. Sacramento, “Vehicle Routing Problem with Drones Instances”, Transportation Research Part C: Emerging Technologies, ago. 2018, doi: https://doi.org/10.5281/zenodo.2572764