Document Type

Pre-Print

Publication Date

12-2020

Subjects

Drone aircraft -- Industrial applications, Delivery of goods -- Technological innovations

Abstract

Given a set of spatially distributed demand for a specific commodity, potential facility locations, and drones, an agency is tasked with locating a prespecified number of facilities and assigning drones to them to serve the demand while respecting drone range constraints. The agency seeks to maximize the demand served while considering uncertainties in initial battery availability and battery consumption. The facilities have a limited supply of the commodity being distributed and also act as a launching site for drones. Drones undertake one-to-one trips (from located facility to demand location and back) until their available battery energy is exhausted. This paper extends the work done by Chauhan et al. (1) and presents an integer linear programming formulation to maximize coverage using robust optimization framework. The uncertainty in initial battery availability and battery consumption is modeled using a penalty-based approach and gamma robustness, respectively. A novel robust three stage heuristic (R3SH) is developed which provides objective values which are within 7%of the average solution reported by MIP solver with a median reduction in computational time of 97% on average. A Monte Carlo Simulation based testing is performed to evaluate the value of adding robustness to the deterministic problem. The robust model provides higher and more reliable estimates of actual coverage under uncertainty. The average maximum coverage difference between the robust optimization solution and deterministic solution is 8.1% across all scenarios.

Rights

This is the author’s version of a work. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. A definitive version was subsequently published in Transportation Research Record and can be found online at: https://doi.org/10.1177/0361198120968094

DOI

10.1177/0361198120968094

Persistent Identifier

https://archives.pdx.edu/ds/psu/34391

Download

Share

COinS