An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

技術的サマリー：顧客非互換性を伴う容量制約付き施設配置問題に対する拡張された大規模近傍探索アプローチ

問題定義
本論文は、顧客非互換性を伴うマルチソース容量制約付き施設配置問題（MS-CFLP-CI）を取り扱います。この変種は、同じ施設によって供給されることができない非互換な顧客ペアの集合（$I$）を導入することで、古典的な MS-CFLP を拡張したものです。この問題は、どの施設を開くか（開設コスト $f_j$ を発生させる）と、開いた施設間で顧客需要（$d_i$）をどのように配分するか（輸送コスト $c_{ij}$ を発生させる）を決定し、総コストを最小化することを目的とします。解は、施設容量制約（$s_j$）を満たし、顧客需要を完全に満たし、かつ2人の非互換な顧客が同じ施設を共有しないことを保証しなければなりません。非互換性制約の存在により、開いた施設の集合が固定されている場合であっても、開いた施設からの最適供給を見つける部分問題は NP 困難となります。

手法
著者は、MS-CFLP-CI を解くための大規模近傍探索（LNS）フレームワークを提案します。このアプローチの中核は、現在の解の一部を反復的に破壊し、厳密な混合整数計画法（MIP）ソルバー（Gurobi）を用いて修復することです。

• 解の表現: 解は、出荷量の行列として表現され、開いている/閉じている施設と割り当てられた顧客を追跡する補助データ構造によってサポートされます。
• 初期解: ヒューリスティックが、開設コストで施設をソートし、総需要を満たすのに十分な数の施設を選択し、非互換性制約を処理するために特定の数の追加施設（$k=5$）を加えることで、開始解を構築します。顧客は均一な戦略に基づいて割り当てられます。
• 破壊オペレーター: 本論文は、非互換性制約に特化して設計された 3 つの新しい破壊オペレーターを導入します。
  1. 最安値施設（CF）: 無作為に 1 つの施設とその顧客を選択し、その特定の顧客グループに対して平均輸送コストが最も低い他の開いている施設を特定します。
  2. ハイブリッド顧客（HC）: 2 つの戦略の再結合です。無作為に 1 つの施設とその顧客を選択し、「最安値顧客」（施設への輸送コストが低い顧客）と「高価な顧客」（輸送コストが高い顧客）を特定します。その後、これらの特定の顧客部分集合に対して最善のサービスを提供する追加の施設を選択します。
  3. 閉鎖された施設: 無作為に選ばれた閉鎖された施設と、最小コスト尺度（$Q_g$）を持つ施設の両方が、新しい施設を開くことを探求するために部分問題に含まれます。
• 修復オペレーター: 破壊された要素によって定義される部分問題は、Gurobi を用いて厳密に解かれます。計算時間を管理するために、修復フェーズには、現在部分問題に関与している施設の数から最大 2 つまでしか新しい施設を開かないように制限する制約が含まれます。収束を加速させるため、現在の部分問題のコストをカットオフ値としてソルバーに提供します。
• 構成とチューニング: 著者は、インスタンスの規模に基づいて（具体的には施設数が 700 以下と 700 超を区別して）、部分問題のサイズ（$\nu$）などのパラメータを調整するための機能ベースのパラメータチューニングに irace ツールを採用しています。最終的なアルゴリズム $LNS_{init,accept}$ は、提案された破壊オペレーター、改良された初期解ヒューリスティック、および局所最適解からの脱出を容易にするために等しいコストの解も受け入れる受入基準を組み合わせたものです。

主要な貢献

• 新規アルゴリズムフレームワーク: MS-CFLP-CI 問題に対する大規模近傍探索の最初の適用です。
• 特化されたオペレーター: 標準的な施設配置ヒューリスティックを超えて、非互換性制約を明示的に考慮する破壊オペレーター（CF および HC）の設計。
• ハイブリッドな厳密/ヒューリスティック修復: 解の質と実行時間のバランスを取るために特定の制約で最適化された、修復フェーズ内への厳密な MIP ソルバーの統合。
• 厳密な分析: 個々の構成要素（初期化、受入基準、適応的重み）の影響を評価するための包括的なアブレーション研究と統計分析（Friedman テストおよび Nemenyi テストの使用）。
• 広範なベンチマーク: 最大 3,000 の施設と 8,000 の顧客を含む 2 つの大規模データセット（wlp および cflp-ci）での評価。

実験結果
提案された $LNS_{init,accept}$ 法は、MineReduce ベースのマルチスタート反復局所探索（MR-MS-ILS）、GRASP、順列符号化進化アルゴリズム（PcEA）、マルチスタート貪欲法（MG）、およびシミュレーテッドアニーリング（SA）を含む最先端のメタヒューリスティックに対してテストされました。

• 性能: 提案された方法は、2 つの異なる時間制限（$10\sqrt{m}$ 秒および $m$ 秒）の下で、両方のデータセットにおいて既存のすべての方法を大幅に上回りました。
• 新たな最良解: このアプローチは、両方のデータセットにわたる 80 件のインスタンスすべてにおいて、新たな最良解を見つけました。
• 統計的有意性: 統計的テストにより、以前の最良手法（SA）に対する改善が統計的に有意であることが確認されました。
• スケーラビリティ: 厳密ソルバー（Gurobi/CPLEX）は合理的な時間内で最適解を求められるのは最大 150 施設までのインスタンスに限られていたのに対し、LNS アプローチは最大 3,000 施設までのインスタンスを効果的に処理しました。
• ギャップの縮小: wlp データセットにおいて、本手法は既知の最良解に対して -0.68% から -1.84% のギャップ改善を達成しました。cflp-ci データセットでは、改善は -0.46% から -2.09% の範囲でした。

意義と主張
著者は、自らの手法が MS-CFLP-CI 問題における現在の最先端を表すと主張しています。この研究の意義は、顧客非互換性によって導入された計算の複雑さを処理する能力にあり、特に大規模なインスタンスにおいて、以前のメタヒューリスティックが完全に最適化することに苦労していた点を克服したことです。本論文は、新規の破壊オペレーター、厳密な修復フェーズ、および特定のアルゴリズム的チューニングの組み合わせにより、中規模の近傍を効果的に探索し、SA や他の手法が停滞する場所で優れた解を見出すことができると主張しています。著者は、現在のところ自らの手法が最良であるが、将来の研究にはインスタンスの難しさをよりよく理解するためのインスタンス空間分析や、他の施設配置変種へのアプローチの拡張が含まれ得ると控えめに述べています。