求解VRPSDP的多邻域导向局部搜索算法  

Multiple Neighborhood Guided Local Search Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup

作　　者：赵进超[1] 李红婵[1] 朱颢东[1] 

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

出　　处：《微电子学与计算机》2015年第9期109-113,共5页Microelectronics & Computer

基　　金：国家自然科学基金项目(61201447);河南省高等学校青年骨干教师资助计划项目(2014GGJS-084);河南省教育厅科学技术研究重点项目(13A520367);郑州轻工业学院校级青年骨干教师培养对象资助计划项目(XGGJS02);郑州轻工业学院博士科研基金资助项目(2010BSJJ038)

摘　　要：针对有运输容量约束的车辆路径问题,提出一种基于多邻域的导向局部搜索算法.该算法首先利用最近邻法构造初始可行解,然后再从该可行解出发同时在多个邻域内进行局部搜索,当陷入局部最优解时找出解中惩罚效用最大的弧并修改惩罚特征系数和目标函数,在选择当前的最优解后从新的目标函数出发重新进行局部优化.通过对54个算例的求解,仿真结果表明了该算法在解决卸装一体化车辆路径优化问题上是一种可行有效的方法.This Paper proposed a Multiple Neighborhood Guided Local Search Algorithm （MN_GLS）to solve vehicle routing problem with simultaneous delivery and pickup.Firstly,it used the nearest neighbor method to build the initial solution.Secondly,it did the local search in multi-operator from the initial solution,and found the bow which had the biggest utility of punishment value when the solution fail into the local optimal solution,then changed the punishment of features value and objective function value.Thirdly,it selected the current optimal solution from the local optimal solutions,and then did the local optimization in multi-operator again from the current optimal solution which has the new objective function value.By means of 54 examples,the simulation results illustrate that MN_GLS is an effective and stabilize method for Vehicle Routing Problem with Simultaneous Delivery and Pickup.

关 键 词：车辆路径问题 多邻域 导向局部搜索 惩罚策略 

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