基于共生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.

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

双层车辆路径规划问题(2E-VRP)是现代多层城市物流系统的基本问题,也是运筹学和组合优化领域的研究热点及NP难问题。针对问题的双层次复杂性,课题在Memetic框架下研究两种全局优化算法的共生计算模式，对目标问题进行先分后合再优的求解。2E-VRP它可以看成是两阶段的SDVRP和MDVRP，其中SDVRP是由一定数量的大型货车从中心仓库将客户的货物运送至各个卫星并返回，该类型的VRP允许客户的需求被分割，从而充分利用车辆的运载力；MDVRP 是由一定数量的小型货车将卫星的货物运送至各个客户并返回,该类型的VRP不允许客户需求被分割。因此，MDVRP要求同一客户的需求必须由同一卫星同一车辆进行配送。课题将设计并行蚁群优化算法进行求解；两种算法基于实时信息交流通过解的整合、优化与重构等共生行为完成最终求解。课题将研究两个全局优化算法的共生计算来完善Memetic算法理论，并在双层次目标平衡和计算时间两个技术瓶颈实现质的突破，为城市物流多层次运输调度需求提供高效可行的计算方法。