摘要
两级车辆路径问题是指物资必须先由中心仓库配送至中转站(第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.
出处
《控制与决策》
EI
CSCD
北大核心
2013年第10期1587-1590,1595,共5页
Control and Decision
基金
国家自然科学基金重大项目(71090404
71090400)
上海市基础研究重点项目(10JC1415300)
