💻 computer science

A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

本論文では、反復局所探索法（Iterated Local Search）と集合分割（Set Partitioning）による後最適化を組み合わせたハイブリッド・メタヒューリスティックであるILS+SPを紹介しており、これは大規模なベンチマーク・インスタンスにおいて準最適解を達成することで、ファミリー容量制約付き車両配送問題（Family Capacitated Vehicle Routing Problem）を解く既存の最先端手法を大幅に上回る性能を示す。

原著者： Bruno Oliveira, Diogo Lima, Marcos Roboredo

公開日 2026-07-02

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Bruno Oliveira, Diogo Lima, Marcos Roboredo

原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは配送会社のマネージャーだと想像してください。あなたは中央倉庫から出発する、すべて同一モデルのトラックのフリート（車両群）を管理しています。あなたの仕事は、さまざまな顧客に荷物を届けることです。

しかし、ここにはひねりがあります。あなたの顧客は単なる「個人」ではありません。彼らは**「家族」ごとにまとめられています。例えば、「スミス家」には異なる通りに5軒の家がありますが、契約ではそのうちの2軒だけに配達することになっています。「ガルシア家」は3軒の家がありますが、あなたは1軒**だけを訪問する必要があります。

これが**「ファミリー容量制車両配送問題（F-CVRP）」**です。これには主に2つのルールがあります：

ファミリー・ルール： 各家族に対して要求された正確な数の家を訪問しなければなりませんが、具体的にどの家を訪問するかは選ぶことができます。
トラック・ルール： 各トラックには重量制限（容量）があります。積みすぎてはいけません。

目標はシンプルです。これらのルールを満たしながら、ガソリン切れや時間の不足に陥ることなく、すべてのトラックを走らせる最も安価な方法を見つけることです。

問題点：完璧に解くのはあまりに困難

家族や家の数が増えるにつれ、可能なルートの数は膨大になり、世界最速のスーパーコンピュータであっても、完璧な答えを見つけるのに何年もかかるようになります。だからこそ、著者であるブルーノ、ディオゴ、マルコスは、非常に優れた答えを素早く見つけ出すための「賢い推測器（メタヒューリスティック）」を作り出したのです。

彼らはその解決策を ILS+SP と呼んでいます。これを料理の比喩を使って分解してみましょう。

レシピ：ILS+SP

1. 「反復局所探索（ILS）」 – 味見をするシェフ

シェフがスープのレシピを完成させようとしている場面を想像してください。

スタート： シェフは基本的なスープを作ります（初期解）。
味見（局所探索）： シェフは味見をし、小さな調整を加えます。「塩をひとつまみ足してみようか？」とか「人参をジャガイモに替えてみようか？」といった具合です。彼らは改善のために、こうした小さな変更を繰り返します。
「焼きなまし法（Simulated Annealing）」のひねり： 時には、変更によってスープの味が一時的に「悪く」なることがあります。普通のシェフならすぐに拒否するところですが、このシェフは特別なルール（焼きなまし法）を使います。もしスープがわずかに悪くなった程度であれば、あえてそれを受け入れます。なぜなら、後で全く新しい、素晴らしい風味のプロファイルを発見するためには、時にはスープの味を少し「崩す」必要があるからです。これは、彼らが平凡なレシピに固執してしまう「悪い領域」から脱出するのを助けます。
揺さぶり（摂動/Perturbation）： もしシェフが、改善につながらない小さな調整のループに陥ってしまったら、彼らは思い切った行動に出ます。スープの半分を捨ててしまい、全く新しい材料の組み合わせでやり直すのです。これは「摂動」と呼ばれます。これにより、全く新しいキッチンの領域を探求することが強制されます。

著者たちは、このシェフの道具箱に特別な材料を追加しました。それが MemberRelocate です。これは「ファミリー」の問題なので、シェフは単に材料を入れ替えるだけでなく、「家族のメンバー」を入れ替えます。もしスミス家の家番号1を訪問しているなら、「待てよ、家番号2の方が近いぞ。家番号1を家番号2に入れ替えて、時間を節約できるか見てみよう」と考えるのです。

2. 「集合分割（SP）」 – マスター・エディター（熟練の編集者）

シェフが試行錯誤し、揺さぶり、味見を繰り返した後、手元には、試してきた様々なスープのバリエーション（ルート）が記された膨大なノートがあります。

**集合分割（Set Partitioning）**のステップは、そのノート全体を見渡すマスター・エディターのようなものです。エディターは料理を作ることはしません。ただ、選び、組み合わせるだけです。彼は、シェフが一日の中で作った最高の「塊（チャンク）」を眺め、「午前10時の特定のルートと、午後2時のあのルートを組み合わせれば、完璧な食事を作れるのではないか？」と問いかけます。

この最終ステップにより、たとえシェフが調理プロセス中に完璧な組み合わせを見逃していたとしても、エディターがその日の成果から最高のパーツを数学的に組み立てることで、解決を図ります。

結果：うまくいったのか？

著者たちは、自分たちの「ILS+SP」レシピを、世界における現時点での最高の手法と比較テストを行いました。

テスト： 彼らは、他の研究者がすでに解こうとしてきた144個の大型で困難なパズル（顧客数が50人以上）を使用しました。
スコア： 彼らの手法は、すべてのインスタンスにおいて、優勝するか、あるいは同率1位となりました。
改善度： この論文が出る前、最高の手法は平均して、完璧な解から約**1.84%の誤差がありました。著者たちの手法は、その差を0.01%**まで縮めました。物流の世界において、これは「的を外している状態」から「ほぼ毎回、的の真ん中を射抜いている状態」へと進化したことを意味します。
スピード： さらに大きなパズル（最大142顧客）に対してもテストを行いました。彼らの手法は、平均して約37秒で素晴らしい解を見つけ出しました。

まとめ

この論文は、どの家族のメンバーを訪問するかを選択しなければならない、複雑な配送ルート問題を解決するための、新しいハイブリッドな手法を提示しています。「賢い小さな変化を加え、時にはリスクを取る『味見をするシェフ』」と、「その日の成果から最高のパーツを組み立てる『マスター・エディター』」を組み合わせることで、彼らはこの特定の課題に対して、これまで発表されたどの手法よりも速く、より正確なツールを作り上げました。

技術要約：ファミリー容量制車両配送問題のためのハイブリッド・メタヒューリスティック

問題定義

本論文は、ファミリー・トラベリング・セールスマン問題（FTSP）および古典的な容量制車両配送問題（CVRP）を一般化した、**ファミリー容量制車両配送問題（F-CVRP）**を扱う。F-CVRPでは、 $K$ 台の同種車両による均質なフリートが、単一のデポから出発し、ファミリーに分割された顧客セットをサービスする。すべての顧客を訪問しなければならない標準的なCVRPとは異なり、F-CVRPでは、各ファミリー $l$ から特定の人数（ $v_l$ ）を訪問する必要があり、そのファミリーの残りのメンバーは未訪問のままにされる可能性がある。目的は、車両容量制約を遵守し、各ファミリーの正確な訪問要件を満たしながら、総ルートコストを最小化することである。

問題の規模が拡大するにつれ、厳密解法は計算量的に困難となる。したがって、本論文は、タイトな時間予算内で高品質な解を提供できる、高速かつ高品質なヒューリスティックの開発に焦点を当てている。これは、スタンドアロンのソルバーとしてだけでなく、厳密なフレームワークへのプライマル・バウンド（primal bounds）の提供源としても機能する。

手法：ILS+SP ハイブリッド・メタヒューリスティック

著者らは、反復局所探索（ILS）フレームワークと集合分割（SP）ポスト最適化フェーズを組み合わせたハイブリッド・メタヒューリスティックであるILS+SPを提案している。アルゴリズムは以下のように動作する。

1. 反復局所探索（ILS）コア

探索は、ルートのプール（ $P$ ）を保持し、発見された最良の実行可能解（ $s^*$ ）を追跡するILSフレームワークによって駆動される。

初期解: 最良並列挿入（BPI）ヒューリスティックを用いて生成される。これは、コスト増加を最小限に抑えるように顧客を反復的に挿入することで $K$ 個のルートを構築し、ファミリーの訪問数が満たされることを保証する。
局所探索（RVND）: 局所探索は、**ランダム変数近傍降下法（RVND）**戦略を採用している。これは、9つの近傍ポートフォリオを探索する：
- ルート間（5つ）: Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0)。
- ルート内（3つ）: Exchange, Reinsertion, Or-opt2。
- 特化型（1つ）: MemberRelocate。これは問題固有のオペレータであり、訪問済みの顧客を取り除き、同じファミリーの未訪問メンバーを全ルートの中で最適な位置に挿入する。
- すべての近傍は、ファミリー訪問数および有効なルート数（ $K$ ）の構造的制約を維持する。
受理基準: 標準的な局所探索とは異なり、アルゴリズムは時間駆動型の冷却スケジュールを用いた**焼きなまし法（SA）**の基準に基づき、悪化する動きを受け入れる。これにより、探索が局所解から脱出することを可能にする。
摂動（Perturbation）: 探索を多様化するために、局所探索に再入る前に、現在の解に対して3つのランダムな摂動（RandomSwap, RandomShift, または RandomMemberRelocate）を適用する。
ペナルティ処理: 容量違反は、探索を実行可能領域へと導くために、現在の解の実行可能性に基づいて調整される、目的関数内の動的なペナルティ係数（ $\theta$ ）を介して処理される。

2. 集合分割（SP）ポスト最適化

時間予算を使い果たした後、アルゴリズムは最終的な最適化ステップを実行する。探索プロセス全体で収集された容量実行可能なルートのプール（ $P$ ）に対して、集合分割問題を定式化する。

SPモデルは、ファミリーの訪問要件を満たし、かつ正確に $K$ 個のルートを使用しながら、総コストを最小化するようにルートのサブセットを選択する。
プール $P$ には、これまでの探索で見つかった最良の解（ $s^*$ ）を構成するルートが含まれているため、SPの最適解は必ず $s^*$ と同等かそれ以上に優れたものになる。

主な貢献

本論文は、既存の最先端技術（具体的には Bernardino and Paias, 2024 による ILS）と区別される4つの主要な貢献を強調している：

集合分割によるハイブリッド化: ルートプールを再最適化するためのSPポスト最適化フェーズの導入。これは、従来の近似手法には存在しないマテューリスティック（matheuristic）成分である。
強化された局所探索: 単にその場で入れ替えるのではなく、未訪問のファミリーメンバーを全ルートの中で最適な位置に最適に挿入するMemberRelocate近傍の実装。
ランダム化された近傍探索: 近傍探索の順序をランダム化するRVNDの使用。これは、先行文献で使用されている固定順序とは対照的である。
焼きなまし法による受理: 以前の手法における厳格な改善のみを受け入れる方式に代わり、SA基準を採用して、悪化する解を受け入れることで、集約（intensification）と多様化（diversification）のバランスを向上させた。

計算結果

著者らは、2つのベンチマークセットを用いてILS+SPを評価した：

標準ベンチマーク（144インスタンス）: 50人以上の顧客を含む Augerat et al. (1995) のセットから派生。
- 性能: 最先端のヒューリスティックである Bernardino and Paias (2024) に対し、すべてのインスタンスにおいて勝利またはタイとなった。
- ギャップの減少: 最良既知解（BKS）への平均ギャップは、従来の最良値の 1.84% から 0.01% に減少した。
スケーラビリティ・ベンチマーク（120インスタンス）: CVRP Set X (Uchoa et al., 2017) から派生した、より大規模なインスタンス（最大142顧客）の新しいセット。
- 性能: アルゴリズムは平均実行時間 37秒 で平均ギャップ 0.47% を達成し、より大きな問題サイズへのスケーラビリティを示した。

重要性と主張

本論文は、ILS+SPをF-CVRPに対する堅牢かつスケーラブルなソリューションとして位置づけている。著者らは、問題固有の近傍とSA受理を備えた洗練されたILSフレームワークと、マテューリスティックなポスト最適化（SP）を統合することで、本手法が既存のヒューリスティックを大幅に上回ることを主張している。結果は、このアプローチが確立されたベンチマークにおける最良既知解に一致または改善する能力を持つだけでなく、より大きく複雑なインスタンスにも効果的にスケールアップできることを示唆しており、スタンドアロンの適用および厳密な解法フレームワークへの統合の両方において価値のあるツールであることを示している。