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
How to Cite
Copyright (c) 2022 Revista UIS Ingenierías
![Creative Commons License](http://i.creativecommons.org/l/by-nd/4.0/88x31.png)
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.
Downloads
References
- 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
- “Ecommerce: Evolución y perspectivas 2020 | COMUNICAWEB”. [En línea]. Disponible en: https://comunica-web.com/blog/marketing-digital/ecommerce-datos-evolucion/
- 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
- 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
- “El nuevo mapa de rescates con drones de DJI - ITSitio”. https://www.itsitio.com/co/nuevo-mapa-rescates-drones-dji/
- 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
- Bonn, “DHL Press Release English”, 2014. https://www.reutersevents.com/supplychain/3pl/dhl-parcelcopter-launches-initial-operations-research-purposes
- “Google tests drone deliveries in Project Wing trials - BBC News”. https://www.bbc.com/news/technology-28964260
- 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
- I. or its affiliates Amazon.com, “Amazon.com: Prime Air”, 2016. https://www.aboutamazon.com/news/transportation/amazon-prime-air-prepares-for-drone-deliveries
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- “Existencias: Vehicle Routing Problem with Drones Instances”. https://zenodo.ups.edu.ec/Record/zen-1568853
- “Uso y cuidado de baterías para drones”. https://elvuelodeldrone.com/blog-de-drones/uso-cuidado-baterias-para-drones/
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- R. Lutz, “Adaptive Large Neighborhood Search”, 2014, [En línea]. Disponible en: http://dx.doi.org/10.18725/OPARU-3237
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- D. Sacramento, “Vehicle Routing Problem with Drones Instances”, Transportation Research Part C: Emerging Technologies, ago. 2018, doi: https://doi.org/10.5281/zenodo.2572764