群知能と進化的計算の国際ジャーナル

概要

組み合わせ最適化のための免疫学的アルゴリズム：燃料配分問題をケーススタディとして

パヴォーネ M*、コスタンツァ J、クテロ V

要約 ルーティング問題は、数多くの産業および現実世界のシナリオで広く適用できる古典的な組み合わせ最適化タスクです。ルーティング問題の困難なバリエーションの 1 つに、輸送会社が日常業務で直面しなければならない燃料分配問題 (FDP) があります。輸送燃料会社の主な活動は、全体的なコストを最小限に抑えることを目的として、地理的なマップに沿ってすべての店舗 (ガソリン スタンド) に商品を補充することです。この研究では、FDP を解決するための免疫システムのメタファーに基づくハイブリッド ヒューリスティックを提示します。これは基本的に、顧客から受け取ったさまざまな要求を満たすために、会社の車両を一定数使用して、可能な限り短いルートのセットを見つけることを求めます。特に、提示された免疫アルゴリズムは、クローン選択原理にヒントを得ており、その主要な特徴は、クローニング、超突然変異、および老化演算子です。このようなアルゴリズムは、(i) 頂点を車両に割り当てるスキームで使用される深さ優先探索 (DFS) アルゴリズムに基づく決定論的アプローチと、(ii) 近傍の探索に基づくローカル検索演算子を備えているという特徴もあります。アルゴリズムは、DIMACS グラフ カラーリング ベンチマークから取得した 82 個の頂点を持つ 1 つの実際のデータ インスタンスと 25 個の他の人工的な異なるインスタンスでテストされています。この研究で提示された実験結果は、開発されたアルゴリズムの堅牢性と効率性を証明するだけでなく、ローカル検索と DFS アルゴリズムに基づくアプローチの優秀さも示しています。両方の方法論は、アルゴリズムが複雑な検索空間をより適切に探索するのに役立ちます。