随机需求多车辆路径问题的重优化算法  

A Reoptimization Algorithm for Multiple Vehicles Routing Problem with Stochastic Demand

作　　者：樊建华[1] 王秀峰[1] 

机构地区：[1]南开大学信息技术科学学院

出　　处：《南开大学学报（自然科学版）》2008年第2期103-107,共5页Acta Scientiarum Naturalium Universitatis Nankaiensis

基　　金：国家自然科学基金(70572045);天津市自然科学基金(05YFJMJC01300);天津市科技发展计划基金(043185111-12)

摘　　要：针对随机需求的多车辆路径问题(MVRPSD),提出了一种简单有效的重优化新算法.该算法先用预优化策略给出一个预优化的单车辆路径,然后重复使用 rollout 算法对该路径进行进一步优化,将其划分为满足约束条件的多条子路径,不仅能满足实际需求,而且极大提高了优化性能.与现行方法对比实验结果表明,本算法可以对多车辆路径更为合理的优化,明显减少行驶费用,是求解随机需求的多车辆路径问题的一种有效算法.Put forward a simply effective reoptimization algorithm for multiple vehicles routing problem with stochastic demand （MVRPSD）. First, a priority single vehicle routing is initialized by a priority strategy, then improve the routing repeatedly using rollout algorithm, partitioning the single vehicle routing into subroutes satisfying constraints. This algorithm not only can satisfy actual requirement, but also enhance the optimization performance significantly. The experimentation results compared with existing method indicate that this algorithm can optimize the multiple vehicles routing rationally, reduce traveling cost evidently, and is an effective algorithm for multiple vehicles routing problem with stochastic demand.

关 键 词：多车辆路径 随机需求的车辆路径 启发式算法 重优化策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]