A Collaborative Drone-Truck Delivery System With Memetic Computing Optimization
- 21 March 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Vol. 54 (6) , 3618-3630
Abstract
With technological breakthroughs, drone deliveries have become increasingly popular, especially during the COVID-19 pandemic. Driven by both economical benefit and efficiency, drone-truck combined deliveries are in demand. However, it is very challenging to handle the collaboration between trucks and drones. Existing methods for truck-only routing cannot be directly applied, since their solution representations and search operators cannot consider the drone-truck collaborations effectively. In this article, we model the system as traveling salesman problem with drones (TSP-Ds), and propose a new Memetic algorithm named MATSP-D for solving it. Specifically, we design a new drone-truck solution representation and develop new crossover and local search operators under the new representation, which can modify the drone services effectively. MATSP-D conducts exploration by crossover, and exploitation by a variable neighborhood search process. The experimental results show that the proposed MATSP-D significantly outperforms the state-of-the-art algorithms for most test instances, especially the large instances with more complex collaborations between the truck and drone. Further analysis verifies the effectiveness of the newly developed local search operators in searching for better-drone-truck collaborations.Keywords
All Related Versions
Funding Information
- National Key Research and Development Program of China (2023YFC3341100)
- National Natural Science Foundation of China (52302398)
- Marsden Fund of New Zealand Government (VUW1614)
This publication has 56 references indexed in Scilit:
- A novel multi-objective optimization model for the vehicle routing problem with drone delivery and dynamic flight enduranceComputers & Industrial Engineering, 2022
- Delivery path planning of heterogeneous robot system under road network constraintsComputers and Electrical Engineering, 2021
- The traveling salesman problem with release dates and drone resupplyComputers & Operations Research, 2021
- Optimization for drone and drone-truck combined operations: A review of the state of the art and future directionsComputers & Operations Research, 2020
- A hybrid genetic algorithm for the traveling salesman problem with droneJournal of Heuristics, 2019
- Dynamic programming approaches for the traveling salesman problem with droneNetworks, 2018
- Drone delivery from trucks: Drone scheduling for given truck routesNetworks, 2018
- Persistent UAV delivery logistics: MILP formulation and efficient heuristicComputers & Industrial Engineering, 2018
- Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspectionAutomation in Construction, 2017
- Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plansComputers & Operations Research, 2012