Skip to main content
Article
Dispatching Point Selection For A Drone-based Delivery System Operating In A Mixed Euclidean–Manhattan Grid
Annals of Operations Research
  • Francesco Betti Sorbelli
  • Federico Corò
  • Sajal K. Das, Missouri University of Science and Technology
  • Cristina M. Pinotti
  • Anil Shende
Abstract

In this paper, we present a drone-based delivery system that assumes to deal with a mixed-area, i.e., two areas, one rural and one urban, placed side-by-side. In the mixed-areas, called EM-grids, the distances are measured with two different metrics, and the shortest path between two destinations concatenates the Euclidean and Manhattan metrics. Due to payload constraints, the drone serves a single customer at a time returning back to the dispatching point (DP) after each delivery to load a new parcel for the next customer. In this paper, we present the 1 -Median Euclidean–Manhattan grid Problem (MEMP) for EM-grids, whose goal is to determine the drone's DP position that minimizes the sum of the distances between all the locations to be served and the point itself. We study the MEMP on two different scenarios, i.e., one in which all the customers in the area need to be served (full-grid) and another one where only a subset of these must be served (partial-grid). For the full-grid scenario we devise optimal and approximation algorithms, while for the partial-grid scenario we devise an optimal algorithm.

Department(s)
Computer Science
Publication Status
Open Access
Comments

National Science Foundation, Grant 1952045

Keywords and Phrases
  • Delivery system,
  • Drone,
  • Euclidean and Manhattan metrics,
  • Facility location,
  • Logistics
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Springer, All rights reserved.
Publication Date
1-1-2023
Publication Date
01 Jan 2023
Disciplines
Citation Information
Francesco Betti Sorbelli, Federico Corò, Sajal K. Das, Cristina M. Pinotti, et al.. "Dispatching Point Selection For A Drone-based Delivery System Operating In A Mixed Euclidean–Manhattan Grid" Annals of Operations Research (2023) ISSN: 1572-9338; 0254-5330
Available at: http://works.bepress.com/sajal-das/314/