系统仿真学报 ›› 2023, Vol. 35 ›› Issue (11): 2476-2495.doi: 10.16182/j.issn1004731x.joss.22-0682

• 论文 • 上一篇    

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

陈雪1(), 胡蓉1(), 王辉2, 李作成1, 钱斌1, 李熠胥1   

  1. 1.昆明理工大学 信息工程与自动化学院,云南 昆明 650500
    2.红塔烟草(集团)有限公司昭通卷烟厂,云南 昭通 657000
  • 收稿日期:2022-06-21 修回日期:2022-09-26 出版日期:2023-11-25 发布日期:2023-11-24
  • 通讯作者: 胡蓉 E-mail:1182442949@qq.com;ronghu@vip.163.com
  • 第一作者简介:陈雪(1998-),女,硕士生,研究方向为复杂系统智能优化。E-mail: 1182442949@qq.com
  • 基金资助:
    国家自然科学基金(61963022);云南省基础研究计划重点项目(202201AS070030)

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

Chen Xue1(), Hu Rong1(), Wang Hui2, Li Zuocheng1, Qian Bin1, Li Yixu1   

  1. 1.School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
    2.Zhaotong Cigarette Factory, Hongta Tobacco Co. , Ltd, Zhaotong 657000, China
  • Received:2022-06-21 Revised:2022-09-26 Online:2023-11-25 Published:2023-11-24
  • Contact: Hu Rong E-mail:1182442949@qq.com;ronghu@vip.163.com

摘要:

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

关键词: 绿色两级车辆路径问题, 蚁群优化, 聚类分解, 学习, 三维概率矩阵, 同时取送货

Abstract:

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.

Key words: green 2-echelon vehicle routing problem, ant colony optimization algorithm, clustering decomposition, machine learning, Three-dimensional probabilistic model, simultaneous pick-up and delivery

中图分类号: