TRB Pubsindex
Text Size:
x

« Prev Next »

Return to Results | New Search

Bookmark and Share

Title:

Maximum Coverage Facility Location Problem with Drones

Accession Number:

01697560

Record Type:

Component

Abstract:

This paper presents a novel integer linear programming formulation for locating facilities which serve spatially distributed demand locations utilizing drones. Unlike other drone problems formulated in the past, the new formulation explicitly incorporates drone energy consumption and range constraints to a maximum coverage location problem. The new formulation is called the Maximum Coverage Facility Location Problem with Drones or simply MCFLPD. The objective of the MCFLPD is to maximize the total demand served while respecting facility capacity and drone range constraints. The MCFLPD is a complex problem and even for relatively small problem sizes a state of the art MIP solver may require unacceptably long running times to find feasible solutions. Computational efficiency of MCFLPD solutions is a key factor since conditions associated to customer demands or weather conditions (e.g., wind direction and speed) may change suddenly and require a fast global reoptimization. To better balance solution quality and running times novel greedy and a three-stage heuristics are developed. The three-stage heuristics (3SH) is based on decomposition and local exchange principles and involves a facility location and allocation problem, multiple knapsack subproblems, and a final exchange based random search stage. On average the 3SH solutions are within 5% of the best Gurobi solutions but at a small fraction of the running time. Multiple scenarios are run to highlight the importance of changes in drone battery capabilities on coverage.

Supplemental Notes:

This paper was sponsored by TRB committee AT015 Standing Committee on Freight Transportation Planning and Logistics.

Report/Paper Numbers:

19-01068

Language:

English

Corporate Authors:

Transportation Research Board

Authors:

Chauhan, Darshan
Unnikrishnan, Avinash
Figliozzi, Miguel

Pagination:

26p

Publication Date:

2019

Conference:

Transportation Research Board 98th Annual Meeting

Location: Washington DC, United States
Date: 2019-1-13 to 2019-1-17
Sponsors: Transportation Research Board

Media Type:

Digital/other

Features:

Figures; Maps; References; Tables

Uncontrolled Terms:

Greedy algorithms; Location problems

Subject Areas:

Aviation; Planning and Forecasting; Vehicles and Equipment

Source Data:

Transportation Research Board Annual Meeting 2019 Paper #19-01068

Files:

TRIS, TRB, ATRI

Created Date:

Dec 7 2018 9:31AM