基于改进差分进化的车辆路径优化算法  

Vehicle Routing Problem algorithm based on improved differential evolution

作　　者：邬开俊[1] 王铁君[2] 

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070 [2]西北民族大学数学与计算机科学学院,兰州730030

出　　处：《计算机工程与应用》2013年第13期17-20,共4页Computer Engineering and Applications

基　　金：国家社科基金(No.12CGL004);兰州交通大学青年科学研究基金(No.2011005)

摘　　要：差分进化算法是一种具有记忆个体最优解和种群内部信息共享的特点的新型进化算法,本质上可看做是一种基于实数编码的、具有保优思想的贪婪遗传算法。针对具有NP难的车辆路径优化问题,提出了一种改进的差分进化算法。利用贪心算法产生初始种群,定义合法化修复变异个体的方法,采用改进的顺序交叉,并在变异操作之后,加入新的选择机制。使用Matlab进行了算法的实现,实验结果表明了改进DE算法能够高效地解决VRP问题。As a new kind of evolutionary algorithm, Differential Evolution （DE） algorithm with the characteristics of remembering individual optimal solution and information sharing can be regarded as a real coded and excellent security greedy genetic algo-rithm. To solve the Vehicle Routing Problem（VRP）, which belongs to NP problems, the paper puts forward an improved differ- ential evolution algorithm. A greedy algorithm is used to generate the initial population, legalized method is used to repair muta-tion, improved order crossover is used, then, after the mutation operator, a new selection mechanism is added in. The new algo- rithm is implemented in Matlab, the experimental results show that the improved differential evolution algorithm can efficiently solve the VRP.

关 键 词：差分进化算法 车辆路径问题 贪心算法 NP问题 进化算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]