基于共生Memetic算法的双层次车辆路径问题求解研究

城市物流业的迅猛发展催生了对多层次运输调度技术的迫切需求。双层次车辆路径问题就是其中最前沿、最核心的复杂规划难题之一，但至今求解该问题的算法研究仍属于起步阶段。针对问题的双层次复杂性,课题在Memetic框架下研究两种全局优化算法的共生计算模式，对目标问题进行先分后合再优的求解。第一层中转站的选取问题可等价抽象为一个多背包问题，课题将设计个体差异进化规划算法进行快速求解；第二层发货点到中转站再到客户的双层配送问题等价于多个单层次车辆路径问题，课题将设计复合信息素矩阵并行蚁群优化算法进行求解；两种算法基于实时信息交流通过解的整合、优化与重构等共生行为完成最终求解。课题将研究两个全局优化算法的共生计算来完善Memetic算法理论，并在双层次目标平衡和计算时间两个技术瓶颈实现质的突破，为城市物流多层次运输调度需求提供高效可行的计算方法。

Mutil-level transportation management has become more and more necessary owing to the quick development of city logistics. Two-Echelon vehicle routing problem (2E-VRP) is one of the most important difficult problems，yet in infancy. This proposal will put forward a symbion memetic algorithm to solve 2E-VRP at two levels. At the first level, the problem of satellite selection will be abstracted to a multiple knapsack problem solved by an evolutionary programming based on individual differences. At the second,the problem of satellite-to-customer assignment will be considered as several 1-E vehicle routing problems tackled by ant colony optimization of compound pheromone matrix. Symbion behaviors will be designed to complete the solution of 2E-VRP based on the real-time information communication of the algorithms, like reconstructing solutions based on threshold, optimizing computational time and so on. The contributions of this project include designing a symbion computational framework of two global optimization algorithms,keeping the balance between two-level targets and computational time and providing an efficient approach for mutil-level transportation management.