Online Delivery Problem for Hybrid Truck–Drone System with Independent and Truck-Carried Drones
Open Access
- 13 January 2023
- journal article
- research article
- Published by MDPI AG in Sustainability
- Vol. 15 (2) , 1584
Abstract
Considering real-time requests and multiple truck–drone delivery modes, we propose an online delivery problem using a truck and some drones, which form a hybrid truck–drone delivery collaboration system comprising independent and truck-carried drones. Considering this problem, we focus on how to schedule the vehicles to serve real-time requests, with the objective of minimizing the time of the latest vehicle’s return to the delivery station. First, we proved the lower bound of this problem to be 1.5. Second, we designed an online re-planning algorithm and proved its competitive ratio to be 2.5. As the online re-planning algorithm invokes an offline algorithm, an offline model was established, and an offline drone priority algorithm was designed. Then, we verified the effectiveness of the offline algorithm by comparing it with the CPLEX solution, and the stability of the online re-planning algorithm with different input parameters was studied through MATLAB simulation. Finally, the minimal latest time saving was calculated by comparing the hybrid truck–drone collaboration system with a truck-only delivery system. This research provides theoretical support for addressing the hybrid truck–drone delivery problem.Keywords
Funding Information
- The National Natural Science Foundation of China (71702016, 21YJC630159, 21YJC630138, 22SKJD092)
- Humanities and Social Science Research Project of Education Commission (71702016, 21YJC630159, 21YJC630138, 22SKJD092)
- Humanities and Social Science research project of Chongqing Education Commission (71702016, 21YJC630159, 21YJC630138, 22SKJD092)
This publication has 18 references indexed in Scilit:
- The Drone-Assisted Traveling Salesman Problem with Robot Stations2020
- An Expressway Based TSP Model for Vehicle Delivery Service Coordinated with Truck + UAV2019
- Routing and Scheduling for Hybrid Truck-Drone Collaborative Parcel Delivery With Independent and Truck-Carried DronesIEEE Internet of Things Journal, 2019
- Vehicle routing problem with dronesTransportation Research Part B: Methodological, 2019
- Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup timesComputers & Operations Research, 2019
- Sizing of the Drone Delivery Fleet Considering Energy AutonomySustainability, 2018
- Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman ProblemEuropean Journal of Operational Research, 2014
- Online traveling salesman problem with deadlines and service flexibilityJournal of Combinatorial Optimization, 2013
- Online Routing Problems: Value of Advanced Information as Improved Competitive RatiosTransportation Science, 2006
- Algorithms for the On-Line Travelling Salesman1Algorithmica, 2001