Revista UIS Ingenierías

Vol. 21 No. 3 (2022): Revista UIS Ingenierías
Articles

An ALNS algorithm for VRPD in last mile distribution

PDF (Español (España))
  • 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

Published 2022-10-02

Keywords

  • Vehicle Route Problem with Drones,
  • Adaptive Large Neighborhood Search,
  • UAV,
  • drones,
  • vehicles,
  • Random removal,
  • Worst Removal,
  • Cluster Removal,
  • Greedy Insertion with Noise Function,
  • Regret-N Insertion,
  • Closest Insertion
    • ...More
    Less

How to Cite

Tarazona-Jimenez, J. S., Jimenez-Romero , J. ., Aguilar-Imitola , K. ., & Lamos-Díaz , H. . (2022). An ALNS algorithm for VRPD in last mile distribution. Revista UIS Ingenierías, 21(3), 153–176. https://doi.org/10.18273/revuin.v21n3-2022012

Copyright (c) 2022 Revista UIS Ingenierías

Creative Commons License

This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Abstract

Unmanned aerial vehicles, better known as drones, have aroused great interest in recent years, having applications in military and civil operations. Research has recently been carried out on the advantages of their use in parcel distribution. This research addresses a Vehicle Routing Problem with Drones (VRPD) focused on last mile distribution, in which drones and trucks can work simultaneously, considering a capacity limit for the truck and the drone, as well as restrictions associated with the time of the route. Within the mathematical formulation, a drone flight speed equation is proposed, and the routes are restricted to a limit percentage of available battery to avoid malfunctions in the air. To solve this formulation, the Adaptive Large Neighborhood Search (ALNS) algorithm is used, which is validated using instances proposed in the literature. In addition, it is verified how the objective function of the initial solution varies by using the destruction and repair heuristics, finally a sensitivity analysis is performed for some parameters of the algorithm and characteristics of the drones; making conclusions from the results obtained and making recommendations for future research.

PDF (Español (España))

Downloads

Download data is not yet available.

References

  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