The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis
YI Yun-fei1,2,3, DONG Wen-yong1, LIN Xiao-dong2, CAI Yong-le1
1. Computer School, Wuhan University, Wuhan, Hubei 430079, China;
2. College of Computer and Information Engineering, Hechi University, Yizhou, Guangxi 546300, China;
3. Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Nanning, Guangxi 530006, China
In order to overcome the shortcoming of the efficiency of the Ito algorithm for the discrete combinatorial optimization problems,an improved Ito algorithm based on collaborative diffusion coefficient and Hill climbing was proposed in this paper.To be consistent with the principle of Brownian motion,the drift and wave should be moved simultaneously,when it found a feasible solution,which continued to be a degree of renewed volatility.Experimental results show that the improved Ito algorithm for solving vehicle routing problem with a soft time window is valid,with the convergence speed,robustness and stability,especially Ito algorithm combines the ability of local search algorithms after climbing method performance has been greatly improved.Finally,according the nature of Markov chain to move to its attractive element and the transformation of the relationship between each state,the Markov chain approximation simulation algorithm which structures the Ito stochastic differential equation and its convergence was proved in this paper.
易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J]. 电子学报, 2015, 43(4): 658-664.
YI Yun-fei, DONG Wen-yong, LIN Xiao-dong, CAI Yong-le. The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis. Chinese Journal of Electronics, 2015, 43(4): 658-664.
[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Sc ience,1959,6(1):80-91.
[2] Szeto W Y,Wu Y,et al.An artificial bee colony algorithm for the capacit ated vehicle routing problem[J].European Journal of Operational Research,201 1,215(1):126-135.
[3] Gong Y J,Zhang J,et al.Optimizing the vehicle routing problem with time windows:a discrete particle swarm optimization approach[J].IEEE Trans Syst, 2012,42(2):254-267.
[4] KONG Ji-li,JIA Guo-zhu,et al. A new mathematical model of vehicle rout ing problem based on milk-run[A].International Conference on Management Scien ce & Engineering[C].Harbin:IEEE press,2013.385-392.
[5] Wang Y,Ma X L,et al.A two-stage heuristic method for vehicle routing pro blem with split deliveries and pickups[J].Journal of Zhejiang University-Sci ence C,2014,15(3):200-210.
[6] Chiang W C,Russell R A.Simulated annealing metah-euristics for the vehic le routing problem with time windows[J].Ann Oper Res,1996,63(1):3-27.
[7] Taillard E,Badeau P,et al.A tabu search heuristic for the vehicle routin g problem with soft time windows[J].Transp Sci,1997,31(2):170-186.
[8] Ghoseiri K,Ghannadpour S F.Hybrid genetic algorithm for vehicle routing a nd scheduling problem[J].Appl Sci,2009,9(1):79-87.
[9] 吴兆福,董文永.求解动态车辆路径问题的演化蚁群算法[J].武汉大学学报(理学版 ),2007,53(5):571-575. Wu Zhaofu,Dong Wenyong.A mixed evolutionary ant algorithm for the dynamic vehi cle routing problem[J].Wuhan Univ,2007,53(5):571-575.(in Chinese)
[10] Lin C J,Chen C H,et al.A hybrid of cooperative particle swarm optimizat ion and cultural algorithm for neural fuzzy networks and its prediction applicat ions[J].IEEE Trans Syst Man,Cybern C,Appl Rev,2009,39(1):55-68.
[11] 喻飞,李元香,等.透镜成像反学习策略在粒子群算法中的应用[J].电子学报,2 014,42(2):230-235. YU Fei,LI Yuan-xiang,et al.The application of a novel OBLbased on lens imagin g principle in PSO[J].Acta Electronica Sinica,2014,42(2):230-235.(in Chine se)
[12] Dong Wenyong,Zhang Dengyi.Simulation optimization based on the hypothesi s testing and ITO process[A].Third International Conference on Natural Computa tion[C].Haikou:IEEE Press,2007.660-665.
[13] Dong Wenyong,Yu Ruiguo,et al.Merging the ranking and selection into ITO algorithm for simulation optimization[A].International Conference on Intelli gence Computation and Applications[C].Wuhan:Springer-Verlag Berlin Heidelbe rg,2010.87-96.
[14] Dong Wenyong,Lei Ming,et al.A new evolutionary algorithms for global nu merical optimization based on ITO process[A].International Conference on Inte lligence Computation and Applications[C].Wuhan:Springer-Verlag Berlin Heide lberg,2010.57-67.
[15] 董文永,张文生,等.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J] .计算机学报,2011,34(4):636-646. DONG Wen-yong,ZHANG Wen-Sheng,et al.Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization[J].Chinese Journal of Computers,2011,34 (4):636-646.(in Chinese)
[16] Wenyong DONG,Ming LEI,et al.BBOB-benchmarking:a new evolutionary algor ithms inspired by ITO process for noiseless function testbed[J].Journal of Com putational Information Systems,2011,7 (6):2195-2203.
2015, Vol. 43 
