求解客户需求动态变化的车辆路径规划方法

Method of solving vehicle routing problem with customers' dynamic requests

对于集货过程中客户需求随时间变化的动态车辆路径规划问题,按时间段划分为一系列车辆已驶离中心车场的静态车辆路径问题,引入虚拟任务点与相关约束方法,将其进一步等价转化为普通的静态车辆路径问题,使用适用于静态问题的算法对其进行求解。应用此车辆路径规划方法,以改进的节约法为静态算法,对于客户数为20的动态路径规划问题进行求解,得到重新优化路径所用的时间为0.49s,说明这种规划方法可行。

A real-time vehicle routing problem （VRP） with customers＇ dynamic requests in Logistics collection was decomposed into a set of static VRPs, in which vehicles were not at depot. Static VRPs were equally converted into general static VRPs by adding virtual customers and relative restrictions, and they were solved by static problem algorithm. With the solving VRP method, a dynamic VRP with 20 customers was solved by using improved saving algorithm. The result shows that the method is feasible, it takes 0.49 s to get the reoptimized route. 3 tabs, 2 figs, 11 refs.