摘要： 双层次车辆路径NP组合优化问题的传统求解算法精度较低,针对该问题,提出一种基于最优切割算法和全路径匹配交叉Memetic算法的双层次车辆路径优化算法(OCFM-2E-VRP)。根据一二级配送耦合特点,采用最优切割算法一次性确定中转站配送容量次优解,以此作为客户配 送优化的基础。为提高算法效率,设计全路径匹配交叉算子对Memetic算法交叉操作进行改进,利用爬山法进行局部搜索,并使最优切割算法和全路径匹配交叉Memetic算法顺序执行,实现对一级中转站容量和二级客户配送的同步优化。仿真结果表明,与Branch and Cut和 Multi-start算法相比,该优化算法具有更高的收敛精度和更快的收敛速度。

关键词: 最优切割, 路径匹配交叉, Memetic算法, 双层次, 车辆路径优化问题

Abstract: According to the low accuracy in solving the traditional two-echelon vehicle routing problem,an Optimal Cutting Algorithm(OCA) and a full path matching cross Memetic algorithm are proposed and combined.Firstly,according to the distribution coupling characteristics of the one and two stage,OCA is used to determine the suboptimal solutions of capacity for transfer station,which is used as the basis for the optimization of the distribution of customers;Secondly,in order to improve the efficiency of the algorithm,the full path matching crossover Memetic algorithm is proposed,and then the hill climbing method is used for local search.OCA and improved Memetic algorithm are executed in order,which realizes the synchronization optimization for the capacity of transfer station and customer distribution of two-echelon.The experimental results show that,compared with Branch and Cut and Multi-start algorithm,the proposed optimization algorithm can achieve better performance in terms of both convergence precision and convergence speed.

Key words: optimal cutting, path matching cross, Memetic algorithm, two-echelon, Vehicle Routing optimization Problem(VRP)

中图分类号: 

• TP18