主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2023, Vol. 31 ›› Issue (3): 48-57.doi: 10.16381/j.cnki.issn1003-207x.2022.0367

• 论文 • 上一篇    

多卡车多机器人联合配送系统路径问题研究

高佳静, 镇璐   

  1. 上海大学管理学院，上海200444
  • 收稿日期:2022-02-26 修回日期:2022-09-05 发布日期:2023-04-03
  • 通讯作者: 镇璐(1981-)，男(汉族)，湖北宜都人，上海大学管理学院，院长，教授，博士生导师，研究方向：生产与服务运作管理优化、运筹调度、物流与供应链管理优化，Email:lzhen@shu.edu.cn. E-mail:lzhen@shu.edu.cn
  • 基金资助:
    国家杰出青年科学基金资助项目(72025103);国家自然科学基金重点资助项目(71831008)

Research on Routing Problem for Joint Delivery System Based on Multiple Trucks and Robots

GAO Jia-jing, ZHEN Lu   

  1. School of Management, Shanghai University, Shanghai 200444, China
  • Received:2022-02-26 Revised:2022-09-05 Published:2023-04-03
  • Contact: 镇璐 E-mail:lzhen@shu.edu.cn

PDF (PC)

652

摘要： 近年来，卡车与送货机器人联合配送系统为物流配送提供了新方向，在推广应用中存在卡车与送货机器人的时间衔接要求高和卡车与送货机器人的配送路径规划复杂问题，传统调度方式难以充分发挥系统潜力。为进一步研究该系统的应用价值，更好地规划该系统的卡车与机器人的平行独立运动路线及互相之间的关联路线，并拓展传统车辆路径规划问题，本文以系统总成本最小化为目标，建立了混合整数规划模型对该系统的联合配送路径问题进行研究。此外，本文设计了变邻域搜索算法求解模型，并通过数值实验验证了模型和算法的有效性。最后，本文通过敏感性分析实验，为物流公司卡车数量配置和卡车停靠位置等宏观规划决策提供了科学的参考依据。

关键词: 送货机器人；联合配送系统；无人配送；变邻域搜索算法；混合整数规划

Abstract: The business model of unmanned delivery has received attention, and unmanned delivery has provided a new direction for logistics distribution. As a new mode of unmanned delivery, the joint delivery mode of trucks and robots raises some scheduling problems in its application, such as complex path planning and strict time connection requirements of trucks and robots. The traditional scheduling mode is difficult to support the operation of the system. In the joint delivery system based on multiple trucks and robots, trucks serve as mobile depots for delivery robots and goods. Trucks do not serve customers, but all customers are served by delivery robots. To study the routing problem for joint delivery system based on multiple trucks and robots, a mixed integer programming (MIP) model with the objective of minimizing total cost including the traveling cost of truck, robot, and the cost of late delivery penalty is established. The MIP model makes the complex problem mathematical, considers customer time window, truck capacity and other factors, and studies the distribution decisions among different truck groups, the robot task allocation decisions, and the distribution path planning decisions of trucks and delivery robots in the joint delivery system based on multiple trucks and robots. A variable neighborhood search (VNS) algorithm is designed to solve the model, which provides an effective tool for solving practical problems. And the effectiveness of the model and algorithm is verified by numerical experiments. The experiment results show that the difference between the results of VNS algorithm and the optimal solution is 0.98% in small-scale experiments, and the calculation time is significantly shortened. In the case of large scale, the algorithm can optimize the rules up to 30.99%. Finally, through sensitivity analysis experiments, a scientific reference is provided for logistics companies to make macro-planning decisions such as the quantity allocation of trucks and the location of trucks.

Key words: delivery robot; joint delivery system; unmanned delivery; variable neighborhood search algorithm; mixed integer programming

中图分类号: