求解车辆路径问题的改进伊藤算法

针对车辆路径问题中选取客户节点易陷入局部最优的缺点,引入节约法并结合路径权重和距离启发因子来改进选取 客户节点的决策规则。根据粒子实际运动过程的特点和伊藤算法在迭代过程中逐步收敛的特性,结合算法的波动算子和漂移算子设计了对路径权重的更新规则,提升了算法的收敛速度。通过增大波动系数和提高环境温度来应对伊藤算法迭代过程中出现的搜索停滞、局部最优现象。引入2-opt局部优化算法来优化当前迭代取得的最优解。实验结果表明,改进后的伊藤算法有效地加快了收敛速度,提高了搜索全局最优解的能力。

Improved ITO Algorithm for Solving VRP

In order to avoid local optimum for selecting client node in VRP,this paper introduced saving method combined with the path weight value and the distance heuristic factor to improve the decision rule of selecting client node.According to the characteristics of the actual process of particle motion and the gradual convergence characteristics of ITO algorithm in the iterative procedure,combining drifting operator and fluctuation operator,this paper proposed the path weight value update rule to enhance the convergence rate of the algorithm.By increasing fluctuation coefficient and raising the ambient temperature,local optimum is skipped and search stagnating is avoided.The local optimization algorithm named 2-opt was introduced to further optimize the current generating best solution.Experimental result shows that the improved ITO algorithm effectively promotes the convergence rate and the ability of searching the global optimal solution.