时变路网下同时配集货车辆-无人车协同配送路径问题

Van-unmanned Vehicle Routing Problem with Simultaneous Delivery and Pick-up Under Time-dependent Road Networks

摘要:

针对时变路网下同时配集货车辆?无人车协同配送路径问题，综合考虑配送区域路网交通信息、客户同时配集货需求、客户软时间窗、电池荷电状态等因素，以派遣成本、能耗成本以及时间窗惩罚成本之和最小为目标建立模型。设计了混合遗传变邻域搜索算法，采用轮盘赌选择策略，引入自适应邻域搜索次数策略，在算法不同时期设计不同的搜索次数以加快算法收敛速度、提高求解质量。通过多组算例求解验证了模型的正确性和算法的有效性，并对不同车辆?无人车协同配送方式、不同车辆行驶速度以及车辆和无人车电池的不同最低荷电状态组合等场景的变化进行了敏感性分析。结果表明，车辆在停靠点不等待无人车的协同配送方式能够有效降低配送成本；考虑车辆速度时变可以更好地适应不同路况，能够有效降低配送成本并提高配送效率；车辆和无人车的最低荷电状态越低，配送成本越小，这一结果对未来研发更高性能电池具有重要意义。

Abstract:

Aiming at the van-unmanned vehicle routing problem with simultaneous delivery and pick-up under time-dependent road network， a model is formulated to minimize the sum of dispatching costs， energy consumption cost and time windows penalty cost by comprehensively considering factors such as the delivery area road network traffic information， customer demand for simultaneous delivery and pick-up， customer soft time windows and battery state of charge. A hybrid genetic variable neighborhood search algorithm is designed. The algorithm uses a roulette selection strategy. The strategy of adaptive neighborhood search is introduced， and different search times are designed in different periods of the algorithm to accelerate the convergence speed of the algorithm and improve the solution quality. By solving multiple sets of instances， the correctness of the model and the effectiveness of the algorithm are verified. Sensitivity analysis is carried out on the changes of scenarios such as the cooperative distribution mode of different van-unmanned vehicles， the driving speed of different vans， and the combination of different minimum battery states of charge of vans and unmanned vehicles. The results show that the cooperative distribution mode of van not waiting for unmanned vehicles can effectively reduce the delivery cost； considering the time-varying speed of vans can better adapt to different road conditions， which can effectively reduce the delivery cost and improve the distribution efficiency； the lower the minimum state of charge of vans and unmanned vehicles， the smaller the delivery cost，which is of great significance for the future development of higher-performance batteries.