摘要
双层次车辆路径NP组合优化问题的传统求解算法精度较低,针对该问题,提出一种基于最优切割算法和全路径匹配交叉Memetic算法的双层次车辆路径优化算法(OCFM-2E-VRP)。根据一二级配送耦合特点,采用最优切割算法一次性确定中转站配送容量次优解,以此作为客户配送优化的基础。为提高算法效率,设计全路径匹配交叉算子对Memetic算法交叉操作进行改进,利用爬山法进行局部搜索,并使最优切割算法和全路径匹配交叉Memetic算法顺序执行,实现对一级中转站容量和二级客户配送的同步优化。仿真结果表明,与Branch and Cut和Multi-start算法相比,该优化算法具有更高的收敛精度和更快的收敛速度。
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.
出处
《计算机工程》
CAS
CSCD
北大核心
2015年第8期279-285,共7页
Computer Engineering
基金
国家自然科学基金资助项目(61202453)
