计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

最优切割与全路径匹配交叉的2E-VRP优化算法

马震远1,梁钰彬1,李俊2   

  1. (1.广东技术师范学院计算机科学学院,广州 510665; 2.悉尼科技大学量子计算与智能系统研究中心,澳大利亚 悉尼 2007)
  • 收稿日期:2014-12-29 出版日期:2015-08-15 发布日期:2015-08-15
  • 作者简介:马震远(1980-),男,讲师、博士,主研方向:路由算法;梁钰彬,硕士研究生;李俊,博士后。
  • 基金项目:
    国家自然科学基金资助项目(61202453)。

2E-VRP Optimization Algorithm with Optimal Cutting and Full Path Matching Cross

MA Zhenyuan  1,LIANG Yubin  1,LI Jun  2   

  1. (1.School of Computer Science,Guangdong Polytechnic Normal University,Guangzhou 510665,China; 2.Centre for Quantum Computation and Intelligent Systems,University of Technology Sydney,Sydney 2007,Austialia)
  • Received:2014-12-29 Online:2015-08-15 Published:2015-08-15

摘要: 双层次车辆路径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)

中图分类号: