Scholarlink

<p>The capacitated vehicle routing problem (CVRP) is a well-known optimization issue in transportation logistics. As a typical representative of swarm intelligence algorithm, ant colony optimization (ACO) has shown encouraging outcomes in CVRP. In contrast, ACO has limitations such as undesirable solutions and susceptibility to getting stuck in local optima. To address these challenges, a multi-strategy adaptive ant colony optimization with the k-means clustering algorithm (KMACO) is proposed for solving CVRP in this study. In the initial stage of KMACO, k-means clustering algorithm is introduced to enhance the quality of the initial solution. Simultaneously, a path-saving factor is added to the state transition rules to improve the success rate of planning. Moreover, the algorithm’s global search capability is further enhanced by dynamically adjusting the pheromone volatilization coefficient. Then, a problem-specific crossover operator and three-stage local operators are designed to strike a balance between the global optimization and local search of KMACO. Finally, to confirm the effectiveness of KMACO, simulation experiments are conducted on three types of datasets. Compared with ACO and six other intelligent algorithms, the KMACO achieves the best-known solution in 17, 12, and 10 instances in benchmark sets A, B, and P, respectively.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Multi-strategy ant colony optimization with k-means clustering algorithm for capacitated vehicle routing problem

  • 期刊论文

  • 发表日期：

    2025年1月21日

查看全文
  • Zhaojun Zhang,
  • Simeng Tan,
  • Jiale Qin,
  • Kuansheng Zou,
  • Shengwu Zhou

摘要

The capacitated vehicle routing problem (CVRP) is a well-known optimization issue in transportation logistics. As a typical representative of swarm intelligence algorithm, ant colony optimization (ACO) has shown encouraging outcomes in CVRP. In contrast, ACO has limitations such as undesirable solutions and susceptibility to getting stuck in local optima. To address these challenges, a multi-strategy adaptive ant colony optimization with the k-means clustering algorithm (KMACO) is proposed for solving CVRP in this study. In the initial stage of KMACO, k-means clustering algorithm is introduced to enhance the quality of the initial solution. Simultaneously, a path-saving factor is added to the state transition rules to improve the success rate of planning. Moreover, the algorithm’s global search capability is further enhanced by dynamically adjusting the pheromone volatilization coefficient. Then, a problem-specific crossover operator and three-stage local operators are designed to strike a balance between the global optimization and local search of KMACO. Finally, to confirm the effectiveness of KMACO, simulation experiments are conducted on three types of datasets. Compared with ACO and six other intelligent algorithms, the KMACO achieves the best-known solution in 17, 12, and 10 instances in benchmark sets A, B, and P, respectively.