基于实时信息的城市配送车辆动态路径优化

Optimization of Dynamic Vehicle Routing of Urban Distribution Based on the Real-time Information

针对城市物流配送的现状,研究了信息在配送过程中实时变化的动态车辆调度问题。分析了需求量在配送途中发生变化、需求点增减、道路交通中断、车辆在行驶过程中出现故障四种动态事件情形下的配送线路实时优化问题。通过引入虚拟顾客,将动态车辆路径问题转化为经典的静态单车型车辆路径问题,提出了动态车辆路径问题的模型构建方法。分构建初始线路和对线路进行实时优化两阶段完成对配送线路的规划,并运用混合遗传算法对其寻优。实验结果表明,本文模型和算法可以有效降低企业配送成本。

In view of the situation of urban distribution,this paper studies the dynamic vehicle routing problem in which the information keeps changing during the distribution process.It analyzes the four kinds of real-time factors including arrival of new customers,change of customer demand,cancellation of customer request,traffic jams and vehicle breakdowns.By introducing virtual customers,this paper converts the dynamic vehicle routing problem into the classic singletype static vehicle routing problem and proposes a model of dynamic vehicle routing problem based on natural description.A two-stage solving strategy is put forward,which involves making the initial plan and real-time optimization.Then a hybrid genetic algorithm is constructed.At last,the dynamic vehicle routing problem’s model and algorithm are tested and verified through data experiment.The results show that the model and algorithm can effectively reduce the distribution cost.