容量制約付きアークルーティング問題

数学において、容量制約付きアークルーティング問題（CARP）とは、除雪車、道路清掃車、冬季用散布車、あるいはその他の容量制約を持つ実世界の物体など、グラフ上を移動する物体に容量制約が課せられた、無向辺と有向弧からなる混合グラフにおいて、グラフ距離／移動距離が最小となる最短経路を求める問題である。この制約は、車両が中央デポから離れている時間、総移動距離、あるいはその両方を異なる重み付け係数で組み合わせたものに対して課される。

CARPにはさまざまなバリエーションがあり、Ángel CorberánとGilbert Laporteによる書籍「Arc Routing: Problems, Methods, and Applications 」で説明されています。 ^{[ 1 ]}

CARPを解決するには、グラフ理論、アークルーティング、オペレーションズリサーチ、地理的ルーティングアルゴリズムを研究し、最短経路を効率的に見つける必要がある。

CARPはNP困難なアークルーティング問題である。

大規模容量制約付きアークルーティング問題（LSCARP）は、CARPの変種であり、300以上のエッジを対象として、大規模な複雑なアークルーティング問題をモデル化するものです。

Yi Mei らは、協調共進化アルゴリズムを用いて大規模な容量制約付きアークルーティング問題を解決するアルゴリズムを発表した。^{[ 2 ]}

LSCARPは、経路切断分解に分割統治アルゴリズムを適用することで解決できます。^{[ 3 ]}

LSCARPは、他の方法の上限と下限を改善する反復的な局所探索によっても解くことができる。^{[ 4 ]}

LSCARPアルゴリズムは、FAST-CARPと呼ばれる高速ヒューリスティックを用いてデンマークの廃棄物収集に適用されている。^{[ 5 ]}

このアルゴリズムは、時間制約付きアークルーティング問題（TCARP）とも呼ばれます。TCARPは、メタヒューリスティックを使用して妥当な時間内に解くことができます。TCARPは、例えばメーター読み取り^{[ 6 ]のように、ボリューム制約が適用されない場合によく発生します。}

Zhangらは、大規模マルチデポCARP（LSMDCARP）と呼ばれる一般化を解決するためのメタヒューリスティックであるルートクラスタリングと探索ヒューリスティックを作成した。^{[ 7 ]}

LSCARP 用のアルゴリズムである拡張ステップと大規模 CARP 用の統計フィルタリング (ESMAENS) が 2017 年に開発されました。^{[ 8 ]}

LSCARP は、階層的分解アルゴリズムを使用して、大規模な容量制約付き車両経路問題に拡張できます。^{[ 9 ]} LSCVRP は、局所探索に基づく進化的手法で解くことができます。^{[ 10 ]} LSCVRP の解決は、統合サポートベクターマシンとランダムフォレスト法で行うことができます。^{[ 11 ]}

LSCARP をシミュレーテッドアニーリングに基づいて解くアルゴリズムである FILO は、Accorsi らによって開発されました^{[ 12 ] 。}