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

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.

Key words:two echelon vehicle routing problem; multi start methods; variable neighborhood descent algorithm; Split algorithm