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

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

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

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.