Abstract
The rapid growth of e-commerce and the increasing demand for timely, cost-effective last-mile delivery have increased interest in collaborative logistics. This research introduces a novel collaborative synchronized multi-platform vehicle routing problem with drones and robots (VRP-DR), where a fleet of $\mathcal{M}$ trucks, $\mathcal{N}$ drones and $\mathcal{K}$ robots, cooperatively delivers parcels. Trucks serve as mobile platforms, enabling the launching, retrieving, and en-route charging of drones and robots, thereby addressing critical limitations such as restricted payload capacities, limited range, and battery constraints. The VRP-DR incorporates five realistic features: (1) multi-visit service per trip, (2) multi-trip operations, (3) flexible docking, allowing returns to the same or different trucks (4) cyclic and acyclic operations, enabling return to the same or different nodes; and (5) en-route charging, enabling drones and robots to recharge while being transported on the truck, maximizing operational efficiency by utilizing idle transit time. The VRP-DR is formulated as a mixed-integer linear program (MILP) to minimize both operational costs and makespan. To overcome the computational challenges of solving large-scale instances, a scalable heuristic algorithm, FINDER (Flexible INtegrated Delivery with Energy Recharge), is developed, to provide efficient, near-optimal solutions. Numerical experiments across various instance sizes evaluate the performance of the MILP and heuristic approaches in terms of solution quality and computation time. The results demonstrate significant time savings of the combined delivery mode over the truck-only mode and substantial cost reductions from enabling multi-visits. The study also provides insights into the effects of en-route charging, docking flexibility, drone count, speed, and payload capacity on system performance.
Abstract (translated)
电子商务的快速增长和对及时、经济高效的最后一公里配送需求的增加,引发了人们对于协同物流的兴趣。这项研究提出了一种新颖的合作同步多平台车辆路径问题(VRP-DR),其中由$\mathcal{M}$辆卡车、$\mathcal{N}$架无人机以及$\mathcal{K}$个机器人组成的车队共同完成包裹递送任务。卡车作为移动平台,能够支持无人机和机器人的启动、回收及途中充电,从而解决载重有限、航程受限和电池约束等关键限制问题。VRP-DR涵盖了五个现实特征:(1)单次旅程中的多次服务;(2)多趟作业操作;(3)灵活对接,允许返回同一或不同卡车;(4)循环与非循环操作,支持回到相同或不同的节点;以及(5)途中充电,在运输过程中为无人机和机器人提供充电能力,最大化利用闲置的运输时间以提高运营效率。VRP-DR被建模成一个混合整数线性规划问题(MILP),旨在最小化运营成本与总耗时。为了克服解决大规模实例计算挑战的问题,研究开发了一种可扩展的启发式算法FINDER(灵活集成配送及能量充电),以提供高效且接近最优的解决方案。通过不同规模实例的数值实验评估了MILP和启发式方法在解的质量和计算时间方面的性能。结果表明,综合递送模式相比仅使用卡车模式显著节约了时间和成本,并从支持多次服务中实现了可观的成本削减。该研究还提供了有关途中充电、对接灵活性、无人机数量、速度及载重能力对系统表现影响的洞见。
URL
https://arxiv.org/abs/2505.23584