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

A Reoptimization Algorithm for Multiple Vehicles Routing Problem with Stochastic Demand

针对随机需求的多车辆路径问题(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.