Flying Drone Sidekick Travelling Salesman Problem with Integrating Pickup and Delivery

Abstract

With the current growth of e-commerce, the complexity of last-mile logistics has become an essential field of study to improve customer satisfaction. Existing research has primarily focused on integrating drones for delivery services largely neglecting pickup services, thus leaving a critical gap in service needs related to parcel returns or combined pickup and delivery. To fill this gap, this dissertation aims to integrate drones to assist traditional last-mile logistics vehicles to form a truck-drone tandem with pickup/return and delivery services. We develop mathematical models and employ tailored heuristic/meta-heuristic methods to solve these complex problems. Furthermore, we conduct numerical experiments to validate that our approaches concerning their capabilities to enhance service efficiency in terms of total service time.

The first part of this dissertation focuses on introducing a drone to last-mile logistics with delivery and return functions. In this model, a truck is responsible for delivering parcels and collecting return parcels along its route while simultaneously deploying a drone with a single payload for similar tasks. We formulate a mathematical model using mixed-integer linear programming (MILP) along with a randomized greedy heuristic to solve large instances. The results show that by introducing drones for both delivery and return services, the system could save up to 24.4% in total service time, compared to the traditional method with one truck only.

The second part of this dissertation extends the previous concept by incorporating multiple payloads to a single drone. We formulate a mathematical model using MILP and validate our approach with small-size instances. We also introduce a tailored heuristic, a variant of Variable Neighborhood Search (VNS), to solve realistic-size instances within a reasonable runtime. The results show that, when compared to a model where a drone can carry only one payload at a time, increasing the drone capacity from one to multiple payloads can reduce the total service time up to 18.3%.

The third part of this dissertation expands into medical last-mile logistics with pickup and delivery services for distributing medications. The model consists of multiple drones, each capable of handling multiple payloads, as sidekicks to a single truck. Unlike our two previous problems where parcels are centralized at a single depot for delivery to customers or returned after being picked up from customers, this approach allows for parcels to be picked up from different locations and delivered to customers. Note that return parcels are not allowed in this model, unlike in the first two parts of this dissertation. We formulate a MILP model and conduct numerical experiments on realistically-sized instances using a variant of the meta-heuristic Simulated Annealing (SA). The results show that by introducing multiple drones with multiple payloads, we could save up to 30.2% of total service time compared to the standard pickup and delivery problem with only one truck.

In conclusion, the integration of drones as sidekicks in delivery and pickup/return services can significantly reduce the total service time, illustrating a significant improvement compared to traditional methods. The results reveal opportunities for further exploration, such as the economic implications of these models and their scalability in larger logistics networks.