求解带容量约束的车辆路径问题的改进伊藤算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (5): 213-216.

求解带容量约束的车辆路径问题的改进伊藤算法

易云飞,蔡永乐,董文永,林郭隆

武汉大学计算机学院武汉430079;河池学院计算机与信息科学系宜州546300;武汉大学计算机学院武汉430079;河池学院计算机与信息科学系宜州546300

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(61170305),广西自然科学基金项目(2011GXNSFB018074),广西教育厅科研项目(200911lx406,3YB136),河池学院自然科学基金项目(2008B-N005),广西新世纪教改工程立项项目(2012JGA198)资助

Improved ITO Algorithm for Solving the CVRP

YI Yun-fei,CAI Yong-le,DONG Wen-yong and LIN Guo-long

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 针对车辆路径问题中路径选择未能确定的缺陷,引入蚁群算法对客户点选取规则进行决策。此外,采用冷却进度表作为控制温度变化的参数,将漂移和波动过程同步进行来改进根据伊藤随机过程而设计的伊藤算法,并将改进后的算法应用于CVRP的求解。实验结果表明,改进后的算法能有效求解带容量约束的车辆路径问题,取得了理想的结果。

关键词: 车辆路径问题,伊藤算法,漂移算子,波动算子

Abstract: In order to overcome the shortcoming of the path selection for the vehicle routing problem,the method of the Ant Colony Algorithm was used to select the customer point．In addition,cooling schedule was used to control the parameters of temperature changes,and the process of drifting operator and fluctuation operator simultaneously to improve the Ito algorithm which is based on the hypothesis testing and Ito stochastic process．When it comes to solve the capacitated vehicle routing problems,the improved ITO algorithm is effective,and the numerical results show that the improved algorithm is feasible．

Key words: Vehicle routing problem,ITO algorithm,Drifting operator,Fluctuation operator

易云飞,蔡永乐,董文永,林郭隆. 求解带容量约束的车辆路径问题的改进伊藤算法[J]. 计算机科学, 2013, 40(5): 213-216. https://doi.org/

YI Yun-fei,CAI Yong-le,DONG Wen-yong and LIN Guo-long. Improved ITO Algorithm for Solving the CVRP[J]. Computer Science, 2013, 40(5): 213-216. https://doi.org/

参考文献

[1] Dantzig G,Ramser J．The truck dispatching Problem [J].Mana-gement Science,1959(6):80-91
[2] 王科峰,叶春明,唐国春.一类新的车辆路径问题及其两阶段算法[J].运筹学学报,2010,4(3):55-63
[3] 李娅,王东.基于混沌扰动和邻域交换的蚁群算法求解车辆路径问题[J].计算机应用,2012,2(2):444-447
[4] 骆剑平,李霞,陈泯融.基于改进混合蛙跳算法的CVRP求解[J].电子与信息学报,2011,3(2):429-434
[5] 王君,李波.带时间窗车辆路径问题的文化基因算法[J].计算机工程与应用,2012,8(7):26-29
[6] 易云飞,阮忠,王国兴,等.求解车辆路径问题的改进粒子群算法[J].计算机科学,2009,1A(36):149-152
[7] 魏明,靳文舟.求解车辆路径问题的离散粒子群算法[J].计算机科学,2010,7(4):187-191
[8] 寇明顺,叶春明,陈子皓.应用蜜蜂繁殖进化型粒子群算法求解车辆路径问题[J].工业工程,2012,5(1):23-27
[9] 董文永,张文生,于瑞国．求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J]．计算机学报,2011,34(4):636-646
[10] Dong Wen-yong．The Simulation Optimization Algorithm Based on the Ito Process[C]∥The 2^nd International Conference on Intelligent Computing．2007:563-573
[11] Dong Wen-yong．The Multi-Objective ITO Algorithms[C]∥The 2^ndInternational Symposium on Intelligence Computation and Applications.2007:21-23
[12] Dong Wen-yong．Simulation Optimization Based on the Hypothe-sis Testing and ITO Process[C]∥Third International Conf-erence on Natural Computation．2007:1210-1221
[13] Dong Wen-yong．Time Series Modeling Based on ITO Algorithm[C]∥Third International Conference on Natural Computation.2007:398-402
[14] Dong Wen-yong,et al.BBOB-benchmarking:A new evolutiona-ry algorithms inspired by ITO process for noiseless function testbed[J]．Journal of Computational Information Systems,2011,7(6):2195-2203
[15] Dong Wen-yong,Yu Rui-guo,Lei Ming．Merging the Ranking and Selection into ITO Algorithm for Simulation Optimization[C]∥5th International Symposium on Intelligence Computation and Applications.2010:87-96
[16] Dong Wen-yong,et al.A New Evolutionary Algorithms forGlobal Numerical Optimization Based on Ito Process[C]∥5th International Symposium on Intelligence Computation and Applications.2010:57-67

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed