Parcel Delivery Using Drones in the Presence of Obstacles

To tackle the challenges of last-mile logistics, drone delivery of parcels has emerged as an efficient and fast solution. However, deploying drone delivery systems in urban environments requires robust obstacle-avoidance capabilities to ensure safe and reliable operations. This study focuses on two critical aspects of parcel delivery via drones: first, how to plan the drone’s trajectory while avoiding obstacles, and second, how to find the optimal position of the source (distribution point) that minimizes the drone’s total movement while delivering parcels. We consider two versions of the problem. In one, the drone can carry only one parcel at a time, and in the other, it can carry up to k parcels. For the first version, our strategy finds the shortest paths from the source position to the customer locations or targets while avoiding obstacles. For the second version, we construct a graph representing all targets, and the edge weights are the shortest path distances considering obstacles. We divide the targets into clusters of size at most k and find a TSP tour for each cluster using Christofide’s algorithm. Experiments have been conducted on problem sets in a simulated urban environment to analyze the proposed solution and determine the effect of k on the cost of solutions.