Maximum Coverage Facility Location Problem with Drones

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.
• Corporate Authors:

  Transportation Research Board

  ,    
• Authors:
  • Chauhan, Darshan
  • Unnikrishnan, Avinash
  • Figliozzi, Miguel
• Conference:
  • Transportation Research Board 98th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2019-1-13 to 2019-1-17
• Date: 2019

Language

• English

Media Info

• Media Type: Digital/other
• Features: Figures; Maps; References; Tables;
• Pagination: 26p

Subject/Index Terms

• TRT Terms: Drones; Energy consumption; Heuristic methods; Industrial location; Integer programming; Linear programming; Vehicle range
• Uncontrolled Terms: Greedy algorithms; Location problems
• Subject Areas: Aviation; Planning and Forecasting; Vehicles and Equipment;

Filing Info

• Accession Number: 01697560
• Record Type: Publication
• Report/Paper Numbers: 19-01068
• Files: TRIS, TRB, ATRI
• Created Date: Mar 1 2019 3:51PM