两级车辆路径问题的多起始点变邻域下降算法

A Multi start Variable Neighborhood Descent Algorithm for Two echelon Vehicle Routing Problem

摘要:

两级车辆路径问题是指货物必须首先由中心仓库配送至中转站(第一级)，再转运至需求点(第二级)的一种新型车辆路径问题.针对该问题特性，提出一种多起始点变邻域下降求解算法.首先由改进的Split算法循环分割由所有需求点组成的随机排列，直至出现可行的第二级配送方案，然后求解第一级问题，获得完整的初始可行解，再通过变邻域下降算法进一步改进.当变邻域下降算法无法改进时，采用多起始点技术重复上述过程，直至算法终止.实验结果表明，所提出的算法易于实现，且性能优于已有最好的两种启发式算法.

Abstract:

Two echelon vehicle routing problem(2E VRP) is a novel kind of vehicle routing problem in which freight from depot to customers is compulsorily delivered through intermediate depots (named satellites). The first echelon is from depot to satellites, while the second from satellites to customers. This paper proposes a multi start variable neighborhood descent algorithm to solve 2E VRP according to the characteristics of this problem. First, an improved Split algorithm continuously splits random permutations of all customers until a feasible second echelon distribution scheme appears. Then, a complete initial feasible solution is obtained by solving the first echelon problem and then further improved by a variable neighborhood descent (VND). When no improvements can be found by VND, the preceding process is repeated by multi start skills until the algorithm is terminated. Computational results show that the proposed algorithm is easy to implement and it outperforms the best two existing heuristics for 2E VRP.