时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。

Time-dependent Single Vehicle Routing Problem and Dynamic Programming Algorithm with Greed Dispatching Restriction

Vehicle routing problems have been extensively studied due to its extensive application and great value on economy. However, two constraints receive less attention, i.e., vehicle speed will be changed with time, and vehicle can service more than one trip. This paper discusses single vehicle routing problem with these two constraints. A mathematic model the optimal object of which is to find the route schedule which has the earliest task completion time is established. It's hard to achieve exact solutions of the problem. So the paper proposes a greed dispatching strategy for the model to compress solution space, and provides a dynamic programming algorithm with FIFO rule. The numerical examples demonstrate that for our model, the solution provided by dynamic programming algorithm is only a satisfactory solution. The numerical examples also indicate the optimal dispatching time decreases while the vehicle load capacity increases, and it gets the minimum when the vehicle load capacity is larger than customers total demand. That is, using larger capacity vehicle will save more dispatching time than using smaller capacity vehicle.