基于需求划分的带软时间窗的路径优化方法

The Optimal Approach of Vehicle Route with Time Window Based on Genetic Algorithm:Dynamic Partition of Demand

针对带有时间窗约束的车辆路径问题(Vehicle Routing Problem With Time Windows,VRPTW)的NP特征,以非完全连通配送网络为研究对象,用带有软时间窗约束的整体配送费用最小为目标,提出了一种基于需求的城市动态划分方法,有效的减少了路径的组合规模,并且用遗传算法将其实现,通过改进的Dijkstra算法求取其基于动态划分的最优配送路径集,最后计算示例验证了本文方法的有效性。

Aiming at the NP characteristic of VRPTW （Vehicle Routing Problem with Time Windows）, with un-entire connection network as the study object, and minimal total cost with time windows as the optimal target, this paper presented an approach of cities dynamic partition based on demands, which reduced the combination scale of vehicle routes. Furthermore, the genetic algorithm of this approach was structured. The optimal route set based on demand partition was obtained through improved Dijkstra algorithm. The simulating result indicates that the dynamic partition method of demand is effective.