求解VRPSDP的变邻域混合遗传算法  

A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup

作　　者：马欢[1] 张建伟[1] 赵进超[2] 陈明[1] 

机构地区：[1]郑州轻工业学院软件学院,郑州河南450002 [2]郑州轻工业学院计算机与通信工程学院,郑州河南450002

出　　处：《郑州大学学报（工学版）》2015年第3期120-124,共5页Journal of Zhengzhou University（Engineering Science）

基　　金：国家自然科学基金资助项目(61403349);国家级大学生创新创业训练计划项目(201310462018)

摘　　要：针对卸装一体化车辆路径问题,提出一种结合变邻域下降搜索和遗传算法的混合启发式算法(GA_VND).利用随机生成的初始种群,通过遗传算法的交叉变异操作生成弱可行解种群,选择其中的最优值作为变邻域深度搜索的初始解.在变邻域深度搜索的过程中通过两种不同的局部搜索算子对解进行局部搜索和迭代优化.通过对54个算例的求解,仿真结果表明GA_VND更新了54个已知最好解中的8个,表明了该算法是解决卸装一体化车辆路径问题的一种有效方法.This paper proposes a hybrid heuristic algorithm combing variable neighborhood descent search with genetic algorithm （GA_VND） to solve vehicle routing problem with simultaneous delivery and pickup. By the use of the initial populations generated randomly, the weak feasible solutions are produced by the crossover and mutation operators of genetic algorithm. And then, the best of them was selected as initial solution of variable neighborhood descent algorithm. Finally, in the process of the variable neighborhood descent search, two different neighborhood structures are used to search the locally optimal solution. The simulation results show that GA_VND can update 8 better solutions in the 54 best known solutions, which illustrates that GA_VND is an effective method for vehicle routing problem with simultaneous delivery and pickup.

关 键 词：卸装一体化 车辆路径问题 变邻域下降搜索 遗传算法 组合优化 

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