OPTIMIZATION MODELS AND ANALYSIS OF TRUCK-DRONE HYBRID ROUTING FOR LAST MILE DELIVERY

E-commerce and retail companies are seeking ways to cut delivery time and cost by exploring opportunities to use drones for making last-mile deliveries. In recent years, drone routing and scheduling have become a highly active area of research. This research addresses the concept of a truck-drone combined delivery by allowing autonomous drones to fly from delivery trucks, make deliveries, and fly to delivery trucks nearby. The first part of the research considers the synchronized truck drone routing model by allowing multiple drones to fly from any truck, serve customers and immediately return to any available truck or depot in the system. The goal is to find the optimal routes of both trucks and drones which minimize the arrival time of both trucks and drones at the depot after completing the deliveries. The problem can be solved by the formulated Mixed Integer Programming (MIP) for the small-size problems and our proposed heuristic called Adaptive Insertion Heuristics (ADI) which is based on the insertion technique for the medium/large-size problems. The second part of the research extends the first studied problem by allowing drones to serve multiple customers before merging with trucks as well as considering the capacity requirement for both vehicles. The problem is mathematically formulated and two efficient heuristic algorithms are designed to solve the large-size problems: Drone Truck Route Construction (DTRC) and Large Neighborhood Search (LNS). In the third study, the goal is to study the potential benefits of combining different types of fleet vehicles to deliver packages to the customers. Three types of vehicles are considered in this study including large drones, traditional trucks and hybrid trucks. The problem can be optimally solved by a mathematical formulation on a small scale. Two efficient metaheuristics based on Variable Neighborhood Search (VNS) and Large Neighborhood Search (LNS) are proposed to solve for approximate solutions of the large-size problems. A case study and numerical analysis demonstrate the better delivery time of the proposed model when compared with the delivery time of other delivery models with a single fleet type.