国际群体智能与进化计算杂志

抽象的

组合优化的免疫算法：以燃料分配问题为例

Pavone M*、Costanza J 和 Cutello V

摘要 路线问题是经典的组合优化任务，在众多工业和现实场景中具有广泛的适用性。路线问题的一个具有挑战性的变体是燃料分配问题 (FDP)，运输公司在日常运营中必须面对这个问题。运输燃料公司的主要活动是沿着地理地图向其所有商店（即加油站）补货，目标是最大限度地降低其总体成本。在这项研究工作中，我们提出了一种基于免疫系统隐喻的混合启发式方法来解决 FDP，该方法基本上要求为固定数量的公司车辆找到一组尽可能短的路线，以满足收到的客户的多种需求。特别是，所提出的免疫算法受到克隆选择原理的启发，其主要特征是克隆、超突变和老化运算符。这种算法还具有以下特点：(i) 基于深度优先搜索 (DFS) 算法的确定性方法（用于将顶点分配给车辆的方案）和 (ii) 基于邻域探索的局部搜索算子。该算法已在一个真实数据实例上进行了测试，该实例具有 82 个顶点，以及从 DIMACS 图着色基准中获取的 25 个其他人工不同实例。本文给出的实验结果不仅证明了所开发算法的稳健性和效率，而且还展示了局部搜索和基于 DFS 算法的方法的优点。这两种方法都有助于算法更好地探索复杂的搜索空间。