工場内フロー最適化 (QAP)

大学のプロジェクト

Carlos Requena Doña avatar

Carlos Requena Doña

AI・3Dグラフィックス・ゲーム開発

このプロジェクトは、工場の組立ラインの最適化問題(FORDのケーススタディに基づく)に取り組み、資材フローのコストを最小限に抑えるための部門の最適な配置を追求します。メタヒューリティクスコースの実習 1の一部として、Carlos Requena Doña と Yessin Mohamed によって開発されました。

構築的ヒューリスティクスから高度な局所探索メタヒューリスティクスまで、さまざまな最適化手法が実装され、比較されています。

🏭 問題の定義 (QAP)

目的は、nn 個の部門を nn 個の場所に割り当てて、以下の二次コスト関数を最小化することです:

C(S)=∑i,j=1n∑k,p=1nfij⋅dkp⋅xij⋅xkpC(S) = \sum_{i,j=1}^{n} \sum_{k,p=1}^{n} f_{ij} \cdot d_{kp} \cdot x_{ij} \cdot x_{kp}

ここで、部門間の資材のフロー (ff) と割り当てられた場所間の距離 (dd) の積を最小化することを目指します。

🧠 実装されたアルゴリズム

1. 貪欲法 (Greedy Algorithm)

高速な初期解を生成する構築的ヒューリスティクス。

  • 優先度付きキュー(ヒープ)を使用して、フロー(降順)と距離(昇順)をソートします。
  • 最もフローの多い部門を、利用可能な最も近い場所に繰り返し割り当てます。

2. 初回改善局所探索 (Local Search First-Improvement)

2つの部門の順列(スワップ)によって近傍を探索し、初期解を改善します。

  • 戦略: 現在のコストを改善する最初の近傍解を受け入れます。
  • DLB (Don’t Look Better): ビットベクトルを実装して探索を最適化し、最近改善を生み出していない部門をマークして無駄な再評価を回避します。

短期および長期のメモリによって導かれ、解を悪化させる動きを受け入れることで局所最適解からの脱出を可能にする高度なメタヒューリスティクス。

  • 短期メモリ: 「タブー期間」中に最近の動きを逆転させたり、訪問した解を繰り返したりすることを禁止するタブーリスト。
  • 長期メモリ: 多様化/集中化を導くための、場所への部門割り当ての頻度。
  • 戦略的振動: 頻度メモリに基づいて、集中化(有望なゾーンの活用)フェーズと多様化(新しいゾーンの探索)フェーズを交互に切り替えます。

4. マルチスタート (GRASP)

ランダム化された構築と局所探索を組み合わせて、解空間の複数の領域を探索します。

  • 構築フェーズ: 常に最良の選択肢を選ぶのではなく、上位「n」個の選択肢からランダムに選ぶランダム化された貪欲法(GRASP / RCL - 制限付き候補リスト)。
  • 改善フェーズ: 生成された各解にタブー探索を適用し、複数回の実行後に見つかった最良のグローバル解を保持します。

🛠️ アーキテクチャと設計

  • FileLoader (Singleton): フロー行列と距離行列をファイルから読み込み、再コンパイルなしで問題のインスタンスを変更できます。
  • 表現: 整数ベクトル v。ここで v[i] は部門 i の場所です。
  • ロギング: 各イテレーションにおけるアルゴリズムの収束と挙動を分析するための詳細なロギングシステム。

C++で実装された組合せ最適化プロジェクト。