交通运输系统工程与信息

交通运输系统工程与信息 ›› 2025, Vol. 25 ›› Issue (6): 305-316.DOI: 10.16097/j.cnki.1009-6744.2025.06.028

• 系统工程理论与方法 • 上一篇    下一篇

多移动中转站下货车-多机器人协同配送路径优化

陈俊熙，卫振林*   

  1. 北京交通大学，交通运输学院，北京100044
  • 收稿日期:2025-07-25 修回日期:2025-09-08 接受日期:2025-09-18 出版日期:2025-12-25 发布日期:2025-12-24
  • 作者简介:陈俊熙(1998— )，男，广东东莞人，博士生。
  • 基金资助:
    中央高校基本科研业务经费专项资金(2024YJS107)；国家重点研发计划 (2023YFB4301900)。

Collaborative Routing Optimization for Multiple Trucks and Robots with Multiple Mobile Satellites

CHEN Junxi, WEI Zhenlin*   

  1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China
  • Received:2025-07-25 Revised:2025-09-08 Accepted:2025-09-18 Online:2025-12-25 Published:2025-12-24
  • Supported by:
    Fundamental Research Funds for the Central Universities (2024YJS107)；The National Key Research and Development Program of China (2023YFB4301900)。

PDF

摘要： 针对货车禁行区的实际可达性及机器人的灵活投放与回收问题，构建一种多移动中转站下的货车多机器人协同配送路径优化模型(MMS-MTRCRP)，以最小化货车与机器人的路径成本及货车固定成本为目标，综合考虑货车路径约束、机器人行驶与续航约束、动态资源约束、客户的硬时间窗约束，以及货车与机器人在时间、空间和容量方面的耦合约束。针对耦合约束带来的复杂决策难题，提出基于投放与回收操作的贪婪路径初始化算法(DRGPIA)，并设计一种融合优化操作的改进自适应大规模邻域搜索算法(IALNS)。基于12个Solomon算例与GUROBI12.0.1的对比实验表明，所提算法在求解质量与效率方面均优于精确求解器。在小规模算例中，IALNS在结果与时间上均优于GUROBI；在中大规模算例中，也表现出良好的性能。此外，通过消融实验与多模式对比分析发现：优化算子对算法性能均产生积极影响，尤其在3个大规模算例中，优化模块使求解成本平均降低8.9%；在单中转站及多中转站原地回收模式无法获得可行解的场景下，多中转站协同优化策略仍可求得满足硬时间窗的可行解，且平均成本分别降低20.6%与17.1%。

关键词: 物流工程, 协同路径优化, 改进的自适应大规模邻域搜索, 多货车-多机器人, 多移动中转站

Abstract: This paper focuses on the challenges of actual accessibility in truck-prohibited areas and the flexible deployment and retrieval of robots by proposing a collaborative routing optimization model for multiple trucks and robots with multiple mobile satellites (MMS-MTRCRP). The model aims to minimize the total cost comprising routing costs of trucks and robots and the fixed cost of trucks, incorporating constraints such as truck routing, robot travel and endurance, dynamic resource allocation, and coupled temporal, spatial, and capacity constraints between trucks and robots. For the complex decision-making resulting from these coupling constraints, the study proposes a greedy path initialization algorithm based on deployment and retrieval operations (DRGPIA), along with an improved adaptive large neighborhood search algorithm (IALNS) integrated with optimization operators. Comparative experiments on 12 Solomon instances with solver GUROBI 12.0.1 were conducted to validate the effectiveness of the proposed algorithm. The IALNS outperforms GUROBI in both solution quality and computation time for small-scale instances and demonstrates competitive performance in medium-and large-scale instances. Furthermore, ablation studies and comparative analysis with other modes reveal that the optimization operators positively contribute to the algorithm's performance. The optimization module reduces the solving cost of IALNS by an average of 8.9% in three large-scale instances. In cases where neither the single-satellite mode nor the multi-satellite same-station retrieval mode can achieve a feasible solution, the multi-satellite collaborative optimization strategy successfully obtains feasible solutions that satisfy all hard time window constraints, yielding average cost reductions of 20.6% and 17.1%, respectively.

Key words: logistics engineering, collaborative route optimization, improved adaptive large-scale neighborhood search, multiple trucks and robots, multiple mobile satellites

中图分类号: