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

A Memetic algorithm for solving two-echelon vehicle routing problem

作　　者：许维胜[1] 曾正洋[1] 徐志宇[1] 

机构地区：[1]同济大学电子与信息工程学院,上海201804

出　　处：《控制与决策》2013年第10期1587-1590,1595,共5页Control and Decision

基　　金：国家自然科学基金重大项目(71090404;71090400);上海市基础研究重点项目(10JC1415300)

摘　　要：两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第1级),再由中转站配送至客户(第2级)的一种车辆路径问题.针对该NP难问题提出一种Memetic算法通过自底向上的方式进行求解.首先利用改进的最优切割算法MDVRP-Split将客户合理分配至中转站;然后采用局部搜索解决第1级问题,交叉产生的精英个体通过局部搜索改进.标准算例的测试结果表明,所提出算法更注重求解质量与求解效率的平衡,性能优于其他现有的两种算法.Two-echelon vehicle routing problem（2E-VRP） is a kind of vehicle routing problem in which freight from depot is compulsorily delivered through intermediate depots（satellites）. The first echelon is from depot to satellites, while the second is 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. Then the 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 balance between solution quality and efficiency, and outperforms two existing algorithms for 2E-VRP.

关 键 词：两级车辆路径问题 MEMETIC算法 最优切割 局部搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]