基于改进分支定价法的车辆路径优化研究

Research on Vehicle Routing Optimization Based on Improved Branch Pricing Method

为克服分支定价算法中基于{0,1}的分支策略在求解车辆路径问题时效率和稳定性方面的缺陷,提出了一种双重禁用的分支策略。该分支策略在分支阶段首先通过筛选一组出弧数量最多的集合,然后按照一定的规则将其分为两组,左右分支分别对包含这两组弧的路线进行禁用,禁用的范围不仅局限于分支阶段,在之后的定价阶段同样需要禁止该弧的使用。双重禁用的分支策略不仅实现了分支定界树所需的分支功能,而且达到了求解效率和质量的平衡。通过采用包含强时间窗约束、载重约束、里程约束的车辆路径问题相关的算例,验证了相对于基于{0,1}的分支策略具有较强的寻优和稳定性能。

Vehicle routing optimization has always been the focus of logistics industry research.In order to further reduce the cost of vehicle routing,branch pricing algorithms have been widely used in the optimization research of vehicle routing problems.In order to overcome the problem that the branch pricing strategy based on{0,1}in the branch pricing algorithm leads to the inefficiency of the branch pricing algorithm,a new branching strategy with double disabling is proposed.The strategy generates an out-of-arc collection for each node’s out-of-arc and sorts the arc-out traffic from large to small,and then divides the arc-collection into two subsets according to certain rules,and the node's left and right branches respectively disable the two subsets.The route containing the set of arcs is implemented to implement the branch.The new double-disabled branching strategy can improve the processing efficiency of vehicle routing problems under various constraints such as strong time window constraints,load constraints,and mileage constraints encountered by the branch pricing algorithm in dealing with vehicle routing problems.The example shows that the branching strategy based on{0,1}has strong optimization and stability.