Robust Maximum Coverage Facility Location Problem with Drones Considering Uncertainties in Battery Availability and Consumption
Robust Maximum Coverage Facility Location Problem with Drones Considering Uncertainties in Battery Availability and Consumption
复制标题
DOI：
10.1177/0361198120968094
复制
发表时间：
2021-02-01
影响因子：
1.7
通讯作者：
Boyles, Stephen D.
中科院分区：
文献类型：
--
作者：
Chauhan, Darshan R.;Unnikrishnan, Avinash;Boyles, Stephen D.
给定一组对特定商品、潜在设施位置和无人机的空间分布需求，机构的任务是定位预先指定数量的设施，并向它们分配无人机以满足需求，同时遵守无人机射程限制。该机构寻求最大限度地满足需求，同时考虑初始电池可用性和电池消耗的不确定性。这些设施对正在分发的商品供应有限，也是无人机的发射场。无人机进行一对一的旅行(从所在的设施到需求地点并返回)，直到其可用电池能量耗尽。本文推广了Chauhan等人的工作。并提出了一种整数线性规划公式，以使用稳健的优化框架来最大化覆盖。初始电池可用性的不确定性和电池消耗的不确定性分别使用基于惩罚的方法和伽马稳健性进行建模。提出了一种新的稳健三阶段启发式算法(R3SH)，其目标值与MIP求解器所报道的平均解相比在7%以内，平均计算时间减少了97%。基于蒙特卡罗模拟的测试被用来评估增加确定性问题的稳健性的价值。稳健模型对不确定情况下的实际覆盖率提供了更高和更可靠的估计。在所有场景中，稳健优化解决方案和确定性解决方案之间的平均最大覆盖差异为8.1%。
Given a set of a spatially distributed demand for a specific commodity, potential facility locations, and drones, an agency is tasked with locating a pre-specified 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. and presents an integer linear programming formulation to maximize coverage using a 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. Monte Carlo simulation based testing is performed to assess 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 the deterministic solution is 8.1% across all scenarios.