Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing
Source abstract
Abstract
Many exact algorithms, heuristics, and metaheuristics have been proposed to solve the Vehicle Routing Problem with Drones, which involves using a fleet of trucks and drones to fulfil customer orders in last-mile delivery. In this study, the problem is formulated using the Markov Decision Process, and a Reinforcement Learning (RL) based solution is proposed. The proposed RL model is based on an attention-encoder and a recurrent neural network-decoder architecture. This approach enhances coordination by determining which vehicles should visit specific customers and where vehicles can rendezvous, effectively leveraging drones and reducing the overall completion time. The RL model has demonstrated competitive performance compared to benchmark algorithms through extensive experiments.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: UAV Applications and Optimization · Distributed Control Multi-Agent Systems · Transportation and Mobility Innovations
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Science, SDU University, Kaskelen 040900, Kazakhstan
Funding
Ministry of Science and Higher Education of the Republic of Kazakhstan
References (31)
Show source-provided references
1. Deloison, T., Hannon, E., Huber, A., Heid, B., Klink, C., Sahay, R., and Wolff, C. (2020, January 21–24). The future of the last-mile ecosystem. Proceedings of the World Economic Forum, Davos, Switzerland.
2. Mahadevan, P. (2010). The military utility of drones. CSS Anal. Secur. Policy, 78.
3. Drone applications for supporting disaster management10.4236/wjet.2015.33C047 ↗
4. Drone-aided routing: A literature review10.1016/j.trc.2020.102762 ↗
5. Borghetti, F., Caballini, C., Carboni, A., Grossato, G., Maja, R., and Barabino, B. (2022). The use of drones for last-mile delivery: A numerical case study in Milan, Italy. Sustainability, 14.10.3390/su14031766 ↗
6. The vehicle routing problem with drones: Several worst-case results10.1007/s11590-016-1035-3 ↗
7. Vehicle routing problem with drones10.1016/j.trb.2019.03.005 ↗
8. The vehicle routing problem with drones: Extended models and connections10.1002/net.21746 ↗
9. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations10.1016/j.cor.2019.04.021 ↗
10. Kool, W., van Hoof, H., and Welling, M. (2019). Attention, Learn to Solve Routing Problems!. arXiv.
11. Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M. (2018, January 3–5). Reinforcement learning for solving the vehicle routing problem. Proceedings of the Advances in Neural Information Processing Systems 31 (NeurIPS 2018), Montréal, QC, Canada.
12. Machine Learning to Solve Vehicle Routing Problems: A Survey10.1109/TITS.2023.3334976 ↗
13. A deep reinforcement learning approach for solving the traveling salesman problem with drone10.1016/j.trc.2022.103981 ↗
14. Schermer, D., Moeini, M., and Wendt, O. (2018, January 19–21). Algorithms for solving the vehicle routing problem with drones. Proceedings of the Intelligent Information and Database Systems: 10th Asian Conference, ACIIDS 2018, Dong Hoi City, Vietnam. Proceedings, Part I 10.10.1007/978-3-319-75417-8_33 ↗
15. A matheuristic for the vehicle routing problem with drones and its variants10.1016/j.trc.2019.06.016 ↗
16. Reinforcement learning based truck-and-drone coordinated delivery10.1109/TAI.2021.3087666 ↗
17. Joint optimization of area throughput and grid-connected microgeneration in UAV-based mobile networks10.1109/ACCESS.2019.2920065 ↗
18. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey10.1002/net.21818 ↗
19. A bi-objective optimization model for the medical supplies’ simultaneous pickup and delivery with drones10.1016/j.cie.2022.108389 ↗
20. Trotta, A., Andreagiovanni, F.D., Di Felice, M., Natalizio, E., and Chowdhury, K.R. (2018, January 16–19). When UAVs ride a bus: Towards energy-efficient city-scale video surveillance. Proceedings of the IEEE Infocom 2018-IEEE Conference on Computer Communications, Honolulu, HI, USA.10.1109/INFOCOM.2018.8485863 ↗
21. Reinforcement learning for combinatorial optimization: A survey10.1016/j.cor.2021.105400 ↗
22. Bello, I., Pham, H., Le, Q.V., Norouzi, M., and Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv.
23. Vinyals, O., Fortunato, M., and Jaitly, N. (2015, January 7–12). Pointer networks. Proceedings of the Advances in Neural Information Processing Systems 28 (NIPS 2015), Montreal, QC, Canada.
24. Khalil, E., Dai, H., Zhang, Y., Dilkina, B., and Song, L. (2017, January 4–9). Learning combinatorial optimization algorithms over graphs. Proceedings of the Advances in Neural Information Processing Systems 30 (NIPS 2017), Long Beach, CA, USA.
25. Pomo: Policy optimization with multiple optima for reinforcement learning
26. Kim, M., and Park, J. (2021, January 6–14). Learning Collaborative Policies to Solve NP-hard Routing Problems. Proceedings of the Advances in Neural Information Processing Systems 34 (NIPS 2021), Online.
27. Ma, Y., Li, J., Cao, Z., Song, W., Zhang, L., Chen, Z., and Tang, J. (2021, January 6–14). Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer. Proceedings of the Advances in Neural Information Processing Systems 34 (NIPS 2021), Online.
28. Optimization approaches for the traveling salesman problem with drone10.1287/trsc.2017.0791 ↗
29. Schermer, D., Moeini, M., and Wendt, O. (2018). A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones, Technische Universität Kaiserslautern. Technacal Report.10.1016/j.cor.2019.04.021 ↗
30. A reinforcement learning approach for rebalancing electric vehicle sharing systems10.1109/TITS.2021.3085217 ↗
31. Simple statistical gradient-following algorithms for connectionist reinforcement learning10.1007/BF00992696 ↗