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

发布时间：2018-03-22 10:42

本文选题：管理科学与工程　切入点：路径计划　出处：《运筹与管理》2014年02期 　论文类型：期刊论文

【摘要】：车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。
[Abstract]:Vehicle routing problem has become a hot topic of academic research because of its wide application field and economic value. However, in the existing research literature, The characteristics of time-varying vehicle speed and multitasking service are seldom concerned. In this paper, the optimization problem of bicycle routing with these two characteristics is discussed, and a time-varying vehicle routing optimization with the earliest delivery completion time as the target is established. Because it is difficult to obtain the exact solution of the model, In this paper, a greedy replenishment strategy is proposed to compress the solution space of the original problem. A dynamic programming algorithm is designed to give the approximate optimal solution of the delivery order in which the vehicle travel time satisfies the FIFO rule. The numerical example verifies that the solution obtained by the algorithm is only the approximate optimal solution of the original problem. The example also shows that the solution obtained by the algorithm is only the approximate optimal solution of the original problem. The optimal delivery time is shortened with the increase of vehicle loading capacity. The shortest delivery time can be achieved when the vehicle loading capacity exceeds the total demand of all customers, that is, the use of larger loading capacity vehicle can save more distribution time.
【作者单位】：重庆交通大学交通运输学院;永川供电局;
【基金】：国家自然科学基金资助项目(60974132) 重庆市教育委员会科学技术研究项目(KJ090415)
【分类号】：U492.22

【参考文献】