Exact and approximate drone warehouse for a mixed landscape delivery system

We introduce a drone delivery system for the 'last-mile' logistics of small parcels. The system serves mixed delivery areas modeled as EMs. The shortest path between two destinations of an EM concatenates the Euclidean-and Manhattan-distance metrics. The drone's mission consists in one delivery for each destination of the grid, and, due to the strict payload constraint, the drone returns to the warehouse after each delivery. Our goal is to set the drone's warehouse in the delivery area so as the sum of the distances between the locations to be served and the warehouse is minimized. We exactly solve the problem proposing an algorithm that takes logarithmic time in the length of the Euclidean side of the EM. We also devise two approximate solutions that select the warehouse among a constant number of vertices of the EM. Such solutions are almost as good as the exact solution and we prove a √2-approximation bound in the worst case. Finally, we propose an exact solution for the two warehouse problem in a Manhattan grid, and an approximate solution for EMs.