全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2015 

求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析

DOI: 10.3969/j.issn.0372-2112.2015.04.006, PP. 658-664

Keywords: 伊藤算法,漂移算子,波动算子,收敛性分析,带软时间窗车辆路径问题

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对伊藤算法在求解离散组合优化问题时效率较低、收敛性较差等缺陷,本文提出的改进伊藤算法引入了协同扩散过程的漂移系数,采用局部搜索能力强的爬山法确定波动系数,将漂移和波动同步进行,当找到可行解之后再进行一定程度的波动.为了验证算法的有效性,将改进后的伊藤算法用于求解带软时间窗的车辆路径问题.仿真结果表明,改进后的算法效率更高,收敛速度更快,算法稳定性和健壮性也更好.此外,本文还根据马尔科夫链移向吸引元的性质及其各状态之间的转换关系,探讨了构造伊藤随机微分方程的马尔科夫链近似模拟算法及其收敛性证明.

References

[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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133