A-VRPD: Automating Drone-Based Last-Mile Delivery Using Self-Driving Cars
A-VRPD: Automating Drone-Based Last-Mile Delivery Using Self-Driving Cars
复制标题
DOI：
10.1109/tits.2023.3266460
复制
发表时间：
2023-09
影响因子：
8.5
通讯作者：
N. Imran;Sabyasachee Mishra;M. Won
中科院分区：
文献类型：
--
作者：
N. Imran;Sabyasachee Mishra;M. Won
基于无人机的最后一英里交付是一项新兴技术，它使用装载到卡车上的无人机将包裹交付给客户。在本文中，我们介绍了一种通过结合自动驾驶汽车（AV）实现基于无人机的最后一英里交付的全自动化系统。提出了一种新的无人机自主车辆路径问题（A-VRPD）。A-VRPD是基于众包从可用的AV池中选择AV，将选定的AV分配给客户组，并为选定的AV安排路线以优化总运营成本。我们制定A-VRPD作为一个混合线性规划（MILP），并提出了一个优化框架来解决这个问题。贪婪算法也被开发，以显着提高大规模交付场景的运行时间。进行了大量的模拟，考虑到不同类型的自动驾驶汽车的现实世界的运营成本，行驶距离计算考虑到实时交通条件使用谷歌地图API，和不同的负载能力的自动驾驶汽车。我们通过与两种不同的最先进解决方案进行比较来评估性能：一种算法，旨在解决传统的无人机车辆路径问题（VRP-D），其中涉及人工操作的卡车与无人机协同工作以交付包裹，以及两级车辆路径问题（2 E-VRP）的算法，其中包裹首先被运输到卫星位置，随后从那些卫星递送到客户。结果表明，与最先进的算法相比，送货公司和车主的利润都大幅增加。
Drone-based last-mile delivery is an emerging technology that uses drones loaded onto a truck to deliver parcels to customers. In this paper, we introduce a fully automated system for drone-based last-mile delivery through incorporation of autonomous vehicles (AVs). A novel problem called the autonomous vehicle routing problem with drones (A-VRPD) is defined. A-VRPD is to select AVs from a pool of available AVs based on crowd sourcing, assign selected AVs to customer groups, and schedule routes for selected AVs to optimize the total operational cost. We formulate A-VRPD as a Mixed Integer Linear Program (MILP) and propose an optimization framework to solve the problem. A greedy algorithm is also developed to significantly improve the running time for large-scale delivery scenarios. Extensive simulations were conducted taking into account real-world operational costs for different types of AVs, traveled distances calculated considering the real-time traffic conditions using Google Map API, and varying load capacities of AVs. We evaluated the performance in comparison with two different state-of-the-art solutions: an algorithm designed to address the traditional vehicle routing problem with drones (VRP-D), which involves human-operated trucks working in tandem with drones to deliver parcels, and an algorithm for the two echelon vehicle routing problem (2E-VRP), wherein parcels are first transported to satellite locations and subsequently delivered from those satellites to the customers. The results indicate a substantial increase in profits for both the delivery company and vehicle owners compared with the state-of-the-art algorithms.