一种求解两级车辆路径问题的Memetic 算法

两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级)，再由中转站配送至客户(第2级)的一种车辆路径问题。针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解。首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站；然后采用局部搜索解决第1级问题，交叉产生的精英个体通过局部搜索改进。标准算例的测试结果表明，所提出算法更注重求解质量与求解效率的平衡，性能优于其他现有的两种算法。

A Memetic algorithm for solving two-echelon vehicle routing problem

Two-echelon vehicle routing problem(2E-VRP) is a kind of vehicle routing problem in which freight from depot iscompulsorily delivered through intermediate depots(satellites). The first echelon is from depot to satellites, while the secondis from satellites to customers. This paper proposes a Memetic algorithm to solve the NP-hard problem in a bottom-up way.The customers are assigned to the satellites reasonably by an improved optimal splitting algorithm MDVRP-Split. Thenthe first-echelon problem is solved by using local search. The elitist produced by crossover is improved by local search.Computational tests on some benchmark instances show that the proposed algorithm pays more attention on the balancebetween solution quality and efficiency, and outperforms two existing algorithms for 2E-VRP.