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

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

针对有运输容量约束的车辆路径问题,提出一种基于多邻域的导向局部搜索算法.该算法首先利用最近邻法构造初始可行解,然后再从该可行解出发同时在多个邻域内进行局部搜索,当陷入局部最优解时找出解中惩罚效用最大的弧并修改惩罚特征系数和目标函数,在选择当前的最优解后从新的目标函数出发重新进行局部优化.通过对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.