求解VRPBTW的变邻域搜索算法

以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.

Variable Neighborhood Search for Solving Vehicle Routing Problems with Backhauls and Time Windows

Based on the background of goods distribution in e-business environment,a model for solving the problems VRPBTW,i.e.,the vehicle routing problems with backhauls and time windows,is developed,and it is analyzed to improve the VNS(variable neighborhood search) algorithm so as to solve the problems.Applying the modified sequential cheapest insertion heuristic proposed originally by Braysy to generating an initial solution for improvement,the algorithm introduces four different local search operators in accordance to VNS mechanism.The results of computational tests including 15 examples were compared with that by conventional VNS and showed that the modified VNS algorithm is effective for solving the problems and greatly outperforms the conventional one.