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

doi:10.3969/j.issn.0372-2112.2015.04.006

电子学报 ›› 2015, Vol. 43 ›› Issue (4): 658-664.DOI: 10.3969/j.issn.0372-2112.2015.04.006

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

易云飞^1,2,3, 董文永¹, 林晓东², 蔡永乐¹

1. 武汉大学计算机学院, 湖北武汉 430079;
2. 河池学院计算机与信息工程学院, 广西宜州 546300;
3. 广西混杂计算与集成电路设计分析重点实验室, 广西南宁 530006

收稿日期:2014-03-10 修回日期:2014-08-22 出版日期:2015-04-25 发布日期:2015-04-25
作者简介:易云飞 男,1981年出生于广西资源,武汉大学计算机学院博士生,副教授,研究方向为智能计算、机器学习等.E-mail:gxyiyf@163.com;董文永 男,1973年出生于河南南阳,武汉大学计算机学院教授,博士生导师,长期从事演化计算、机器学习、数据挖掘等方面的研究工作E-mail:hubei_001@163.com
基金资助:
国家自然科学基金(No.60873114,No.61170305);广西自然科学基金(No.2013GXNSFBA019282);广西混杂计算与集成电路设计分析重点实验室开放基金课题(No.HCI201411);国家级大学生创新创业训练计划(No.201310605017,No.201310605018)

The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis

YI Yun-fei^1,2,3, DONG Wen-yong¹, LIN Xiao-dong², CAI Yong-le¹

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

Received:2014-03-10 Revised:2014-08-22 Online:2015-04-25 Published:2015-04-25

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: Ito algorithms, drift operator, wave operator, convergence analysis, vehicle routing problem with soft time windows

中图分类号:

TP301

易云飞, 董文永, 林晓东, 蔡永乐. 求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[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[J]. Acta Electronica Sinica, 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.

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

The Improved ITO Algorithm to Solve the Vehicle Routing Problem with Soft Time Windows and Its Convergence Analysis

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	马梦瑶, 赖晓平, 孟海龙. 二维FIR滤波器约束最小二乘设计的最大分划松弛ADMM算法[J]. 电子学报, 2020, 48(3): 510-517.
[2]	易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
[3]	孟超, 孙知信. 中心引力优化CFO算法研究[J]. 电子学报, 2013, 41(4): 698-703.
[4]	张瑞华;欧阳缮;周德新;刘庆华. 实际AANC系统误差通道建模的分析[J]. 电子学报, 2004, 32(1): 55-58.