On the Evaluation of a Drone-Based Delivery System on a Mixed Euclidean-Manhattan Grid

In this work, the authors investigate the use of drones in a delivery scenario formed by two contiguous areas. In one area the drones can freely fly on straight lines between any two locations (Euclidean metric), while in the other one the drones must follow the open space above the roads (Manhattan metric). They model this delivery scenario as a Euclidean-Manhattan-Grid (EM-grid). Given a set of customers to be served in an EM-grid, the objective is to find the distribution point (DP) for the drone that minimizes the overall traveled distance, considering that the drone has to do multiple round trips to/from the DP. In their view, the DP is optimized with respect to the set of customers and its computation must be light because it needs to be recomputed every time the set of customers varies. Accordingly, wthey define the Single Distribution Point Problem (SDPP) and devise sub-optimal time-efficient algorithms for solving it. The authors numerically compare the cost of their sub-optimal solutions with that of an optimal solution computed with a brute-force approach. Finally, using the BlueSky open air simulator, they compare the cost of their best solution with the cost of a solution that serves the costumers from a fixed DP, like the location of a delivery company’s depot. The fixed DP can perform very poorly for some customer instances, while their solution is highly adaptive and reduces the time and the distance covered by the drone.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01884167
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 31 2023 10:57AM