Two echelon vehicle routing problem with drones in last mile delivery
Two echelon vehicle routing problem with drones in last mile delivery
复制标题
DOI：
10.1016/j.ijpe.2019.107598
复制
发表时间：
2020-07-01
影响因子：
12
通讯作者：
Lee, Seokcheon
中科院分区：
文献类型：
--
作者：
Kitjacharoenchai, Patchara;Min, Byung-Cheol;Lee, Seokcheon
近年来，无人机路径选择与调度已成为一个非常活跃的研究领域。这项研究引入了一种新的路线模型，该模型考虑了同步的卡车-无人机操作，允许多架无人机从一辆卡车上起飞，为一个或多个客户服务，然后返回同一辆卡车进行电池更换和包裹取回。该模型解决了两个层次(梯队)的交付：从主仓库到服务指定客户的主要卡车路线，以及从卡车到辅助无人机路线，其行为像一个可移动的中间仓库，为其他客户组服务。该模型考虑了卡车和无人机的能力，目的是找到卡车和无人机的最佳静音，以最大限度地减少卡车和无人机在完成交付后到达仓库的总时间。该问题可以用公式化混合整数规划(MIP)来解决，并设计了两种有效的启发式算法来解决大尺寸问题：无人机卡车路径构建(DTRC)和大邻域搜索(LNS)。实验的数值结果比较了这两种启发式方法与文献中的MIP方法在中小型实例中的性能。通过敏感度分析表明，与以往的卡车-无人机路径模型相比，该模型的配送时间有所改善。
In recent years, drone routing and scheduling has become a highly active area of research. This research introduces a new routing model that considers a synchronized truck-drone operation by allowing multiple drones to fly from a truck, serve one or multiple customers, and return to the same truck for a battery swap and package retrieval. The model addresses two levels (echelons) of delivery: primary truck routing from the main depot to serve assigned customers and secondary drone routing from the truck, which behaves like a moveable intermediate depot to serve other sets of customers. The model takes into account both trucks' and drones' capacities with the objective of finding optimal mutes of both trucks and drones that minimizes the total arrival time of both trucks and drones at the depot after completing the deliveries. The problem can be solved by formulated mixed integer programming (MIP) for the small-size problem, and two efficient heuristic algorithms are designed to solve the large-size problems: Drone Truck Route Construction (DTRC) and Large Neighborhood Search (LNS). Numeric results from the experiment compare the performance of both heuristics against the MIP method in small/medium-size instances from the literature. A sensitivity analysis is conducted to show the delivery time improvement of the proposed model over the previous truck-drone routing models.