求解环境车辆路径问题的多种群伊藤算法

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

摘要/Abstract

摘要： 针对传统伊藤算法收敛速度慢、易陷入局部最优解的缺陷,重新设计了环境温度调节函数,并改进了粒子漂移和波动时的路径权重更新规则,使粒子更符合布朗运动的特性。把多种群概念引入到算法中,利用种群信息加快算法的收敛速度和寻优能力。利用2-opt局部优化和反转优化进一步改进前5个最优解。最后,考虑车辆载重量对燃料消耗率的影响,对最少碳排放的环境车辆路径问题模型进行改进,利用改进后的算法进行仿真求解。实验结果表明,改进后的算法提高了搜寻最优解的能力并加快了收敛速度,有效防止了停滞现象。

关键词: 伊藤算法,多种群,碳排放,漂移,波动

Abstract: In view of the defects that traditional ITO algorithm,due to low convergence speed,is prone to run into local optimal solution,the environmental temperature adjustment function was redesigned and the path weight renewal rule of particles in drifting and fluctuating was improved so as to make the particles better meet the characteristics of Brownian motion particles.Meanwhile,multi-group concept is introduced into the algorithm to acclerate the convergence speed and improve the capacity of finding an optimal solutions with fully taking advantage of the population information.The first five optimal solutions are further improved by using 2-opt local optimization and reverse optimization.Finally,The vehicle load is considered into the calculation of the fuel efficiency rate,the environment vehicle routing problem(EVRP) model based on least carbon emission is improved,and the improved algorithm is used to solve the problem.Experimental result shows that the improved ITO algorithm can effectively promote the ability of searching the global optimal solution and the convergence rate,and it can effectively prevent the stagnation phenomenon.

Key words: ITO algorithm,Multigroup,Carbon emission,Drift,Fluctuation

尹志扬,余世明. 求解环境车辆路径问题的多种群伊藤算法[J]. 计算机科学, 2016, 43(12): 260-263. https://doi.org/10.11896/j.issn.1002-137X.2016.12.047

YIN Zhi-yang and YU Shi-ming. Multigroup ITO Algorithm for Solving EVRP[J]. Computer Science, 2016, 43(12): 260-263. https://doi.org/10.11896/j.issn.1002-137X.2016.12.047

参考文献

[1] Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91
[2] Kuo Y.Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J].Computers &Industrial Engineering,2010,59(1):157-165
[3] Xiao Yi-yong,Zhao Qiu-hong,Kaku Ikou,et al.Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J].Computers & Operations Research,2012,39(7):1419-1431
[4] 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 & Environment,2014,31(8):85-99
[5] Li Jin,Zhang Jiang-hua.Vehicle routing problem with time windows based on carbon emissions and speed optimization[J].Systems Engineering-Theory & Practice,2014,34(12):3063-3072(in Chinese)李进,张江华.基于碳排放与速度优化的带时间窗车辆路径问题[J].系统工程理论与实践,2014,34(12):3063-3072
[6] Dong Wen-yong,Zhang Deng-yi,Zhong Wei-cheng.The Simulation Optimization Algorithm Based on the Ito Process[M]∥Advanced Intelligent Computing Theories and Applications.With Aspects of Contemporary Intelligent Computing Techniques,2007:115-124
[7] Dong Wen-yong,Lei Ming,Yu Rui-guo.A New EvolutionaryAlgorithms for Global Numerical Optimization Based on Ito Process[M]∥Computational Intelligence and Intelligent Systems.Springer Berlin Heidelberg,2010:57-67
[8] Dong Wen-yong,Yu Rui-guo,Lei Ming.Merging the Ranking and Selection into ITO Algorithm for Simulation Optimization[M]∥Computeational Intelligence and Intelligent Systems.Springer Berlin Heidelberg,2010:87-96
[9] Dong Wen-yong,Zhang Deng-yi,Li Yuan-xiang.The multi-objective ITO algorithms[C]∥Proceedings of the 2nd Internatio-nal Conference on Advances in Computation and Intelligence.Springer-Verlag,2007:53-61
[10] 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,34(4):636-646(in Chinese) 董文永,张文生,于瑞国.求解组合优化问题伊藤算法的收敛性和期望收敛速度分析[J].计算机学报,2011,34(4):636-646
[11] Yi Yun-fei,Cai Yong-le,Dong Wen-yong,et al.Improved ITOAlgorithm for Solving the CVRP[J].Computer Science,2013,40(5):213-216(in Chinese) 易云飞,蔡永乐,董文永,等.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,40(5):213-216
[12] Ubeda S,Arcelus F J,Faulin J.Green logistics at Eroski:A case study[J].International Journal of Production Economics,2011,131(1):44-51

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed