一种改进的混沌伊藤算法求解车辆配送问题

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

摘要/Abstract

摘要： 为了提高基本伊藤算法搜索最优解的效率,在状态转移策略中引入C-W节约法,并根据伊藤算法迭代的特性改进了距离启发因子和路径权重的更新规则,同时在寻优过程中对各个因子的权值系数作线性调整,保证了初期种群的多样性和后期遍历寻优的能力。根据种群中粒子的适应度设计了针对波动算子和漂移算子的自适应扰动策略,以避免算法在迭代过程中出现搜索停滞的现象。构造了4个邻域搜索算子,并在此基础上提出了基于幂函数载波的混沌局部优化方法,该方法提高了局部搜索的充分性和遍历性。仿真结果证明了所提算法的有效性。

关键词: 伊藤算法,状态转移策略,自适应扰动,混沌局部优化

Abstract: In order to improve the efficiency of ITO algorithm searching optimal solution,the C-W saving method was introduced to the strategy of state transition,meanwhile,the distance heuristic factor and the update rule of path weight were modified on the basis of the characteristic of ITO algorithm.For the purpose of enhancing the diversity of initial population and the final optimization capability,the weight coefficient of each factor was adjusted linearly in the process of optimization.According to the fitness of particles,the adaptive disturbance was designed for fluctuation operator and drifting operator to overcome the ITO easy-to-stagnation phenomenon.Based on the four local search operators,a chaoticlocal optimization method using power function carrier was proposed,which greatly improves the ergodicity and the sufficiency of the local search.The simulation results show the effectiveness of the proposed algorithm.

Key words: ITO algorithm,Strategy of state transition,Adaptive disturbance,Chaotic local optimization

华茂,余世明. 一种改进的混沌伊藤算法求解车辆配送问题[J]. 计算机科学, 2016, 43(3): 266-270. https://doi.org/10.11896/j.issn.1002-137X.2016.03.049

HUA Mao and YU Shi-ming. Modified Chaotic ITO Algorithm to Vehicle Routing Problem[J]. Computer Science, 2016, 43(3): 266-270. https://doi.org/10.11896/j.issn.1002-137X.2016.03.049

参考文献

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91
[2] He Xiao-feng,Ma Liang.Quantum-inspired ant colony algorithmfor vehicle routing problem with time windows[J].Systems Engineering-Theory&Practice,2013(5):1255-1261
[3] 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(in Chinese) 王沛栋,唐功友,李扬.带容量约束车辆路由问题的改进蚁群算法[J].控制与决策,2012,27(11):1633-1638
[4] Qi M Y,Zhang J J,Ren L.Vehicle Routing Algorithm Based on Spatiotemporal Clustering[J].Computer Science,2014,41(3):218-222(in Chinese) 戚铭尧,张金金,任丽.基于时空聚类的带时间窗车辆路径规划算法[J].计算机科学,2014,41(3):218-222
[5] Jia H,Li Y,Dong B,et al.An Improved Tabu Search Approach to Vehicle Routing Problem [J].Procedia-Social and Behavioral Sciences,2013,96:1208-1217
[6] Zhang S,Lee C K M,Choy K L,et al.Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem[J].Transportation Research Part D:Transport and Environment,2014,31(8):85-99
[7] Dong Wen-yong,Zhang Wen-sheng,Yu Rui-guo.Convergenceand Runtime Analysis of ITO Algorithm for One Class of Combinatorial Optimization[J].Chinese Journal of Computers,2011(4):636-646(in Chinese) 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011(4):636-646
[8] Dong W,Zhang D,Zhang W,et al.The Simulation Optimization Algorithm Based on the Ito Process[J].Communications in Computer & Informmation Science,2007,2:115-124
[9] Dong W,Yu R,Lei M.Merging the Ranking and Selection into ITO Algorithm for Simulation Optimization[C]∥ 5th International Symposium Computational Intelligence and Intelligent Systems(ISICA 2010).Wuhan,China,2010:87-96
[10] 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(in Chinese) 易云飞,蔡永乐,董文永,等.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,40(5):213-216
[11] Dong W,Lei M,Yu R.A New Evolutionary Algorithms forGlobal Numerical Optimization Based on Ito Process[J].Communcations in Computer & Information Science,2010,107:57-67
[12] Clarke G,Wright J.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J].Operations Research,1964,12(4):568-581
[13] Wan Bo,Lu Yu,Chen Li-yun,et al.Study of modified shuffled frog leaping algorithm for solving CVRP[J].Application Research of Computers,2011,28(12):4503-4506(in Chinese) 万博,卢昱,陈立云,等.求解CVRP的改进混合蛙跳算法研究[J].计算机应用研究,2011,28(12):4503-4506
[14] Tang Wei.Chaotic Optimization Method Based on Power Function Carrier and Its Application[J].Control and Decision,2005,20(9):1043-1046(in Chinese) 唐巍.基于幂函数载波的混沌优化方法及其应用[J].控制与决策,2005,20(9):1043-1046
[15] Xiu Chun-bo,Zhang Yu-hong,Gu Sheng-na.Chaos annealing sear-ching algorithm based on power function carrier[J].Control Theory & Applications,2007,24(6):1021-1024(in Chinese) 修春波,张雨虹,顾盛娜.基于幂函数载波的混沌退火搜索算法[J].控制理论与应用,2007,24(6):1021-1024
[16] Ning Ai-bing,Ma Liang.Competitive decision algorithm and its application to vehicle routing problem[J].Journal of Management Sciences in China,2005,8(6):10-18(in Chinese) 宁爱兵,马良.竞争决策算法及其在车辆路径问题中的应用[J].管理科学学报,2005,8(6):10-18

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed