Routing battery-constrained delivery drones in a depot network: A business model and its optimization–simulation assessment
Routing battery-constrained delivery drones in a depot network: A business model and its optimization–simulation assessment
复制标题
DOI：
10.1016/j.trc.2023.104147
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Yan-chun Liu
中科院分区：
文献类型：
--
作者：
Yan-chun Liu
本文提出了一种新的商业模式，按需使用无人机包裹运输服务，并评估不同的建模和解决方案的无人机路由问题，支持服务操作的方法。在拟议的服务中，客户的任意起点和目的地的货运订单，有效载荷重量和出价值每五分钟收集一次，然后从多个仓库派遣可用的无人机，以实现利润最大化的方式履行这些订单的子集。无人机路径从一个仓库开始，依次为一个或多个客户订单提供服务，并在一个仓库结束，以进行电池充电，这会产生固定成本。提出了两种混合整数规划（MIP）方法来模拟无人机调度和路由问题。为了提高求解效率，三种计算方法，包括两个列生成的算法和暴力路径枚举算法，开发和比较。计算实验表明，有点令人惊讶的是，蛮力的方法是最有效和最可扩展的一个，在计算时间和解决方案的质量大幅优于其他替代品。此外，提出了一个优化仿真框架来评估跨越多个调度周期的长时间范围内的系统性能，而不会使优化模型变得复杂。使用模拟框架，产生有用的管理见解，包括电池容量，风力条件和计算能力对车队调度操作的影响，这将指导新商业模式的实际实施。
This paper proposes a novel business model for on-demand package shipment services using drones, and evaluates different modeling and solution approaches for the drone routing problem that underpins the service operation. In the proposed service, customers’ shipment orders of arbitrary origins and destinations, payload weights and bid values are collected every five minutes, and available drones from multiple depots are then dispatched to fulfill a subset of these orders in a way to maximize profit. A drone path starts from a depot, serves one or more customer orders in sequence, and ends at a depot for battery recharging, which incurs a fixed cost. Two mixed integer programming (MIP) formulations are presented to model the drone dispatch and routing problem. To improve solution efficiency, three computational approaches, including two column generation based algorithms and a brute-force path enumeration algorithm, are developed and compared. Computational experiments suggest, somewhat surprisingly, that the brute-force approach is the most effective and most scalable one, outperforming other alternatives by a substantial margin in both computing time and solution quality. Furthermore, an optimization–simulation framework is proposed to assess the system performance over a long horizon that spans multiple dispatch periods without complicating the optimization model. Using the simulation framework, useful managerial insights including the effects of battery capacity, wind condition and computing capability on the fleet dispatch operation, are generated, which will guide real-world implementations of the new business model.