学习型蚁群算法求解一类复杂两级车辆路径问题

Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem

针对考虑同时取送货的绿色两级车辆路径问题,以最小化带碳排放成本的总运输成本为优化目标,提出一种结合聚类分解的学习型蚁群优化算法。针对两级问题相互耦合的特点,采用基于距离的聚类算法将原问题分解为一组子问题,提出一种学习型蚁群优化算法对各子问题进行求解,进而获得原问题的解。提出一种考虑问题结构特征的三维概率矩阵作为信息素矩阵,用于学习优质解的优良特征信息,以提高算法的全局搜索能力;提出一种考虑算法行为特征的局部搜索策略,用于学习所设计的六种邻域算子的搜索信息,以提高算法的局部搜索能力。通过仿真实验和算法比较,验证了所提算法的有效性。

Aiming at green 2-echelon vehicle routing problem with simultaneous pick-up and delivery,a learning-based ant colony optimization algorithm combined with clustering decomposition is proposed.The objective function to be minimized is total transportation cost wherein carbon emission cost is specially considered.Associated with the mutual coupling features of the 2-echelon vehicle routing problem,we propose a distance-based clustering method to decompose the original problem into a set of sub-problems.Then,a learning-based ant colony optimization algorithm is presented to find the solutions of the sub-problems based on which the solution of the original problem can be obtained.In the algorithm,we introduce a problem-dependent three-dimensional probability matrix to represent pheromone matrix,which is used to learn valuable information about high-quality solutions and improve global search ability.Thereafter,we propose a local search strategy based on the search behavior of the algorithm to learn information about excellent individuals for six dedicated neighborhood search operators,so as to enhance local search ability.Results of numerical experiments and algorithm comparisons demonstrate the effectiveness of the proposed algorithm.