结合聚类的改进HGS求解复杂车辆路径问题

作者：黄静; 王亚彬; 白梅娟; 闫聚兵; 侯帅; 王杨洋

来源：电脑知识与技术, 2023, 19(09): 5-8.

DOI：10.14004/j.cnki.ckt.2023.0437

• 车辆路径问题
• 多供应方
• 时间窗
• 聚类分解
• 改进饥饿游戏搜索算法

提出一种结合聚类分解策略的改进饥饿游戏搜索算法(Improved Hunger Games Search Algorithm Based on Cluster Decomposition, IHGS＿CD)来求解带时间窗的多供应方车辆路径问题(MDVRP＿TW)。首先，采用基于K-means的平衡约束聚类算法，将MDVRP＿TW合理分解为一系列带时间窗的单供应方车辆路径子问题(VRP＿TW)；其次，提出一种改进饥饿游戏搜索算法(Improved Hunger Games Search Algorithm, IHGS)求解分解后的各子问题(VRP＿TW)，从而获得原问题的解。IHGS引入个体精度约束参数来控制个体继续迭代，从而有效控制个体精度以提高算法的全局最优解。最后，通过实验验证了所提IHGS＿CD的有效性。

• 单位
  河北工程大学; 中国人民解放军陆军工程大学