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

doi:10.11896/j.issn.1002-137X.2015.09.049

摘要/Abstract

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

关键词: 路径权重,收敛速度,局部最优,2-opt

Abstract: 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.

Key words: Path weight value,Convergence rate,Local optimum,2-opt

王浩光,余世明. 求解车辆路径问题的改进伊藤算法[J]. 计算机科学, 2015, 42(9): 253-256. https://doi.org/10.11896/j.issn.1002-137X.2015.09.049

WANG Hao-guang and YU Shi-ming. Improved ITO Algorithm for Solving VRP[J]. Computer Science, 2015, 42(9): 253-256. https://doi.org/10.11896/j.issn.1002-137X.2015.09.049

参考文献

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management science,1959,6(1):80-91
[2] 陈森,姜江,陈英武,等.一类非确定性车辆路径问题模型及其算法设计[J].计算机工程,2011,37(14):186-188 Chen Sen,Jiang Jiang,Chen Ying-wu,et al.A Class of Non-deterministic Vehicle Routing Problem Model and Its Algorithm Design[J].Computer Engineering,2011,37(14):186-188
[3] Stanojevi M,Stanojevi B,Vujoevi M.Enhanced savings calculation and its applications for solving capacitated vehicle routing problem[J].Applied Mathematics and Computation,2013,219(20):10302-10312
[4] 柳毅,沈勤.带时间窗可回程取货车辆路径问题的元胞鱼群算法[J].系统管理学报,2011,20(6):739-743 Liu Yi,Shen Qin.The CA-AFSA Algorithm for Vehicle Routing Problem with Backhauls and Time Windows[J].Journal of Systems & Management,2011,20(6):739-743
[5] 王君,李波.带时间窗车辆路径问题的文化基因算法[J].计算机工程与应用,2012,48(7):26-29 Wang Jun,Li Bo.Memetic algorithm for vehicle routing problem with time windows[J].Computer Engineering and Applications,2012,48(7):26-29
[6] 王沛栋,唐功友,李扬.带容量约束车辆路由问题的改进蚁群算法[J].控制与决策,2012,27(11):1633-1638 Wang Pei-dong,Tang Gong-you,Li Yang.Improved ant colony algorithm for capacitated vehicle routing problems[J].Control and Decision,2012,27(11):1633-1638
[7] Dong Wen-yong,Zhang Deng-yi,Zhong Wei-cheng.The Simulation Optimization Algorithm Based on the Ito Process[C]∥Proceedings of the 2007 International Conference on Intelligent Computing.Qingdao,China,Berlin Heidelberg:Springer,2007:115-124
[8] Dong Wen-yong,Lei Ming,Yu Rui-guo.A New EvolutionaryAlgorithms for Global Numerical Optimization Based on I TO Process[C]∥Proceedings of the 5th International Symposium on Intelligence Computation and Application.Wuhan,China,Berlin Heidelberg:Springer,2010:57-67
[9] Dong Wen-yong,Yu Rui-guo,Lei Ming.Merging the Rankingand Selection into ITO Algorithm for Simulation Optimization[C]∥Proceedings of the 5th International Symposium on Intelligence Computation and Application.Wuhan,China,Berlin Heidelberg:Springer,2010:87-96
[10] Dong Wen-yong,Zhang Deng-yi,Li Yuan-xiang.The Multi-Objective ITO Algorithms[C]∥Proceedings of the 2nd International Symposium on Intelligence Computation and Application.Wuhan,China,Berlin Heidelberg:Springer,2007:53-61
[11] 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011,34(4):636-646 Dong Wen-yong,Zhang Wen-sheng,Yu Rui-guo.Convergence and Runtime Analysis of ITO Algorithm for One Class of Combinatorial Optimization[J].Chinese Journal of Computers,2011,34(4):636-646
[12] 易云飞,蔡永乐,董文永,等.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,40(5):213-216 Yi Yun-fei,Cai Yong-le,Dong Wen-yong,et al.Improved ITO Algorithm for Solving the CVRP[J].Computer Science,2013,40(5):213-216
[13] 吴斌.车辆路径问题的粒子群算法研究与应用[D].杭州:浙江工业大学,2007 Wu Bin.Particle Swarm Optimization for Vehicle Routing Problem and its Application[D].Hangzhou:Zhejiang University of Technology,2007

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed