アークルーティング

アークルーティング問題 ( ARP ) は、ノードルーティング問題 (NRP) も含む一般ルーティング問題 (GRP) のカテゴリです。ARP と NRP の目的は、それぞれグラフのエッジとノードをたどることです。^{[ 1 ]}アークルーティング問題の目的は、総距離と時間を最小化することであり、多くの場合、目的地に到達するのにかかる時間である空車時間を最小化します。アークルーティング問題は、ゴミ収集、スクールバスのルート計画、小包や新聞の配達、道路に塩を撒く冬季サービス車両による除氷と除雪、 ^{[ 2 ]}郵便配達、ネットワーク保守、道路清掃、警察や警備員の巡回、^{[ 1 ]}および除雪に適用できます。^{[ 3 ] [ 4 ]}アークルーティング問題は、多項式時間で解けるルート検査問題とは対照的に、NP 困難です。

アークルーティング問題の解決の実際の例として、Cristina R. Delgado Serna と Joaquín Pacheco Bonrostro は、スペインのブルゴス県の中等学校システムで最適なスクールバスのルートを見つけるために近似アルゴリズムを適用しました。研究者らは、まず 60 分以上かかるルートの数を最小化しました。また、固定された最大車両数で最長のルートの所要時間を最小化しました。^{[ 5 ]}

アークルーティング問題には、複数の郵便配達員を導入する一般化があり、例えばk中国郵便配達員問題（KCPP）などがある。

車両の効率的なスケジュールとルーティングにより、産業界と政府は毎年数百万ドルを節約できます。^{[ 2 ] [ 6 ]}アークルーティング問題は、スクールバスの計画、都市のごみや廃棄物の収集、郵便配達員や郵便サービスによる郵便物や小包の配達、冬季の道路の安全確保のための融雪剤散布、除雪、遠隔無線周波数識別メーター読み取り技術を含むメーター読み取り、道路の維持管理と清掃、警察パトカーのルート計画など、さまざまな用途に使用されています。

基本的なルーティング問題は、車両群によってサービスされるノードおよび/またはアークのセットが与えられたとき、各車両がデポを出発し、デポに戻るルートを見つけることです。車両ルートは、車両がデポを出発し、デポに戻る順番に通過しなければならないポイントまたはノードのシーケンスです。^{[ 2 ]}

中国郵便配達員問題（CPP）は、1人の郵便配達員にとって最短の長さのサイクルを見つけることを目的としている。CPPではすべてのエッジを一度通過する必要があるが、農村郵便配達員問題（RPP）では、最短の長さのサイクルでエッジのサブセットを通過する必要がある。^{[ 1 ]}

アークルーティング問題は、戦略的、戦術的、および運用上の計画決定に影響を与えます。デポの配置場所の戦略的役割は、利用可能な最も効率的なアークルートに依存します。さまざまな仕様の車両フリートのサイズと車両タイプの決定は、オペレーションズリサーチにおけるアークルーティング問題の戦術的側面に関連しています。ルーティングとスケジューリングの決定は、アークルーティング問題における運用上の計画決定です。運用上の計画決定には、スタッフの決定とともに、作業員が車両を使用する時間も含まれます。^{[ 2 ]}デポの場所に関する車両ルーティングの決定は、地理的な地域を横断して資材を輸送するコストに依存します。Bodin らは、車両ルーティングをダイヤルアライド問題に適用しました。^{[ 7 ]}

状況によっては、必要なエッジの集合がグラフ内のエッジと異なる場合があります。これは、必要なエッジがエッジシステムのサブセットである農村郵便配達員問題 (RPP) ^{[ 1 ]}によってモデル化されています。

大量のデータを用いて、中国郵便配達問題 (CPP)、風の強い郵便配達問題 (WPP)、農村郵便配達問題 (RPP)、k-中国郵便配達問題 (KCPP)、混合中国郵便配達問題(MCPP)、指向性中国郵便配達問題 (DCPP)、^{[ 8 ]}下り坂耕作問題 (DPP)、優先順位付き耕作問題 (PPP)、風の強い農村郵便配達問題 (WRPP)、風の強い一般経路問題 (WGRP) に対して効率的な解を見つけるには、ヒューリスティック最適化手法、分岐限定法、整数線形計画法、巡回セールスマン問題アルゴリズムの応用など、思慮深い数学的概念を用いる必要があり、 Held–Karp アルゴリズムは改善をもたらす。${\displaystyle O(n!)}$に${\displaystyle O(2^{n}n^{2})}$[ ^{9 ]}これらのアルゴリズムに加えて、これらのクラスの問題は、切断平面アルゴリズム、凸最適化^、凸包、ラグランジュ乗数法、その他の動的計画法でも解決できます。計算複雑度が高いため、Held–Karp アルゴリズムを実行することが現実的でない場合、このようなアルゴリズムを使用して、妥当な時間で解を近似することができます。^{[ 10 ]}

アークルーティング問題の領域に関する最も古い記録は、オイラーが不可能であることを証明したケーニヒスベルクの橋の古典的な挑戦である。 ^{[ 4 ]}ケーニヒスベルク（現在のカリーニングラードの一部）の住民は、プレゲル川にかかる7つの橋を、後戻りや引き返すことなく、つまり各橋を1回だけ渡る方法を見つけようとした。1736年、オイラーはこの問題をノードとエッジの問題に還元し、問題が不可能であることを示した。1873年、ヒアホルツァーは閉回路の問題についてさらに研究を行った。^{[ 4 ]}

オイラー回路に関する研究は、1953年7月1日にサイエンティフィック・アメリカン誌で広く知られるようになった。 ^{[ 11 ]}この研究は、上屯師範大学のクワン・メイコーとしても知られるメイグ・グアンによって拡張された。メイグ・グアンは、閉回路を決定するのではなく、別の問題に興味を持っていた。グアンは、グラフのすべての辺を少なくとも1回通過する最小長の歩行経路を見つけようとした。グアンは1962年にその目標を次のように説明した。「郵便配達員は、郵便局に戻る前に割り当てられた区間をカバーしなければならない。問題は、郵便配達員の最短歩行距離を見つけることである。」^{[ 4 ]}

アークルーティング問題（ARP）は、その目的やヒューリスティックにおいて違いがある。しかし、それらはすべてNP困難であることが知られている。

URPPは1974年に初めて導入され、 LenstraとKanによってNP困難問題であることが証明されました。UCARPはURPPから導出できるため、同様にNP困難です。1981年には、別のコンピュータ科学者であるGoldenとWongが、URPPの0.5近似を導出することさえNP困難であることを証明しました。2000年には、Drorがさまざまなアークルーティング問題を解説した書籍を出版しました。

ミニエカが提案した風の強い郵便配達員問題は、入力が無向グラフであるものの、各エッジを一方の方向に通過する場合と他方の方向に通過する場合でコストが異なる可能性があるという経路検査問題の変種である。^{[ 13 ]}有向グラフと無向グラフの解とは対照的に、これはNP完全である。^{[ 14 ] [ 15 ]}風が顔に当たっているときの移動コストは、風が背後から吹いているときよりも大きいため、これが風の強い郵便配達員問題という名前の由来となっている。風の強い日に、道路を一方の方向に横断するのに必要な作業は、別の方向に横断するのに必要な作業とは異なる。^{[ 8 ]}

風の強い郵便配達員問題は、混合中国郵便配達員問題 MCPP を特殊なケースとして含むアークルーティング問題 (ARP) です。^{[ 16 ]}

この問題は次のように定義できます。「2つの非負のコストを持つ無向連結グラフG=(V,E)が与えられた場合${\displaystyle c_{i,j}}$そして${\displaystyle c_{j,i}}$各エッジに関連付けられている${\displaystyle \{i,j\}\in E}$それぞれ i から j および j から i への移動コストに対応して、WPP は、各エッジを少なくとも 1 回通過する最小コストのツアーを G 上で見つけることです。」^{[ 16 ]}この問題は Minieka によって導入されました。WPP は一般に NP 完全であり、G がオイラーグラフである場合、G のすべてのサイクルの 2 つの反対方向のコストが同じである場合、または G が直並列グラフである場合は、多項式時間で解くことができます。Windy Rural Postman Problem (WRPP) は WPP の一般化であり、グラフ内のすべてのエッジを通過する必要はありませんが、必要なエッジの指定されたサブセット内のエッジのみを通過する必要があります。たとえば、一部の田舎道は郵便配達員が通過する必要がなく、急な丘の道は上る方が下るよりも時間がかかります。^{[ 10 ]}

風の強い田舎の郵便配達員問題 (WRPP) は、WPP の一般化であり、グラフ内のすべてのエッジを通行する必要はなく、必要なエッジの特定のサブセット内のエッジのみを通行すればよい。たとえば、田舎道の中には郵便配達員が通行する必要のない道路もあり、急な坂道の中には上り坂の方が下り坂よりも時間がかかるものもある。^{[ 10 ]}無向グラフを考える${\displaystyle G=\{E,V\}}$2つの費用${\displaystyle c_{ij}}$そして${\displaystyle c_{ji}}$端を通過するコストに関連する${\displaystyle (i,j)}$それぞれ i と j から始まる。G は風の強いグラフであり、我々はエッジのサブセット、つまり数学記号で表すと次のものに興味がある。${\displaystyle E_{R}\subseteq E}$。

WRPPに、特定の頂点群を訪問しなければならないという追加制約が含まれる場合—${\displaystyle V_{R}\subseteq V}$この問題が風の強い一般ルーティング問題（WGRP）に変わる。ベナベントは、WRPP に対して整数線形計画法による定式化とさまざまなヒューリスティックおよび下限を提案した。^{[ 9 ]}

Benavent らは、中規模グラフの下限から 1% 以内の偏差で WRPP を数秒で解くために使用されるいくつかのヒューリスティック手法の評価を発表しました。彼らはこれを Scatter Search アルゴリズムで改善し、差を 0.5% にまで減らしました。Scatter Search は、数百のノードと数千のエッジを持つネットワークに適用した場合、2% 未満の偏差で解を見つけました。^{[ 9 ]}

現実世界のアプリケーションでは、移動可能な車両が複数存在するため、Min-Max K-vehicles Windy Rural Postman Problem (MM K-WRPP) と呼ばれる一般化が行われます。Min-Max K-vehicles Windy Rural Postman Problem (MM K-WRPP) は次のように定義されます。Windy グラフが与えられた場合${\displaystyle G=\{V,E\}}$、際立った頂点、${\displaystyle 1\in V}$倉庫を表す、必要なエッジのサブセット ${\displaystyle E_{R}\subseteq E}$MM K-WRPP は、車両数が固定されている K の場合、各ツアーが車庫で開始および終了し、必要な各エッジがちょうど 1 台の車両によってサービスされるように、車両の K 個のツアーのセットを見つけることから成ります。目的は、車両のバランスの取れたルートのセットを見つけるために、最長ツアーの長さを最小化することです。最小最大目的のルーティング問題の実際の応用例としては、スクールバスのルーティング (Delgado および Pacheco 2001)、顧客への新聞の配達 (Applegate ら 2002)、廃棄物の収集 (Lacomme ら 2004) などがあります。^{[ 10 ]}

最適なMM K_WRPPアルゴリズムは、車両数が2台と3台の場合、最小解に非常に近く、平均で0.4%未満でした。車両数が4台と5台の場合、その差は約1.00%と1.60%に拡大します。

Dussault らおよび Benavent らによると、メタヒューリスティクス多目的シミュレーティングアニーリングアルゴリズム (MOSA) は、WRPP に課せられたさまざまな制約を解くことができる。WRPP は、多くの単一車両アークルーティング問題を一般化した重要なアークルーティング問題である。実際の数学の応用では、すべての車両のルートの総コストと最長ツアーの長さを最小化するソリューションが望ましい。荷物がいつも何時間も遅れる場所にいるのは難しい。^{[ 8 ]} 測定不可能な無限の容量を持つ 1 台の車両よりも、顧客にサービスを提供する特定の測定可能な容量を持つ複数の車両の方が現実的であるという仮定から始めるべきである。Rabbani らは、Yang らによって開発されたカッコウ探索の多目的開発を使用して MOSA アルゴリズムとモデルのパフォーマンスを測定した。^{[ 17 ]}これは、多目的カッコウ探索とも呼ばれ、MOCS と略される。^{[ 8 ]}彼らはMOSA法がMOCS法よりも効率的であると結論付けた。将来的には、非劣解ソート遺伝的アルゴリズム（NSGA-）、多目的粒子群最適化アルゴリズム（MOPSO）、多目的帝国主義競争アルゴリズムなど、他のメタヒューリスティック法との比較を研究することができる。

風の強い郵便配達員問題 (WPP) モデルでは、一方の方向に進むコストと反対方向に進むコストが異なります。たとえば、風が道路に沿って吹いている場合、風に逆らって進む方が、風に乗って進むよりも時間とエネルギーが多くかかります。WPP のもう 1 つの例は、上り坂を耕すコストが下り坂を耕すコストよりも大きいことです。^{[ 3 ]}これは、Dussault らが研究した、下り坂耕作問題 (DPP) という変種によってモデル化されています。^{[ 3 ]}

風の強い郵便配達人問題に対して、アンヘル・コルベランによって分岐限定法が発表された。このアルゴリズムは、奇数カット不等式違反を操作するためのヒューリスティック法と厳密法に基づいている。^{[ 16 ]}

平面グラフにおける最大カットの探索や無向グラフにおける最小平均長回路の探索など、さまざまな組み合わせ問題が中国郵便配達員問題に帰着されている。 ^{[ 18 ]}

k-中国郵便配達員問題は次のように定義できます。「連結した辺重み付きグラフGと整数pおよびkが与えられたとき、Gのすべての辺が少なくとも1つの閉路に含まれ、かつ閉路内の辺の総重みがp以下であるような閉路が少なくともk個存在するかどうかを判定せよ。」 k -CPPの解を求めるプロセスはNP完全です。Gutin、Muciaccia、およびYeoは2013年にk -CPPが固定パラメータ扱い可能であることを証明しました。^{[ 19 ]}著者らは、 k -CPPがカーネルを持つことを証明しています。${\displaystyle O(k^{2}\log(k))}$頂点数と、 k -CPPの有向バージョンはNP完全である。

農村郵便配達員問題 (RPP) では、いくつかの経路が必須かつ絶対的なものとなりますが、グラフをたどる人は特定の方向に進む必要はありません。RPP は、kCPP、DPP、PPP と同様に NP 困難かつ完全です。ベネヴァントは、この問題の一般化である、方向指定農村郵便配達員問題 (DRPP-TP) を研究しました。^{[ 20 ]}ベネヴァントのアルゴリズムは、DRPP-TP を非対称巡回セールスマン問題 (ATSP) に変換することで解を近似しました。

ほとんどのアルゴリズムでは、グラフの前処理が必要です。前処理では、2つの必須エッジ間の最短経路に含まれないすべてのエッジを削除することで、初期グラフを単純化します。前処理によってさらに単純化される点として、経路に必須エッジが存在しない場合、経路内のエッジの数に関係なく、2つの必須エッジ間の最短経路を1つの非必須エッジに変換します。

前処理が完了すると、問題は凸包問題に一般化でき、その辺は凸包の点となります。凸包問題は線形計画法または凸包アルゴリズムによって解くことができますが、凸包を求めるプロセスは指数関数的な問題です。

前処理後にURPPを解く方法は、カッティングプレーンアルゴリズムと分岐＆カット法から構成される。 ^{[ 21 ]}

これは、さまざまなアークルーティング問題における計算複雑度の一覧です。

• ランカスター大学のアークルーティング問題検索ページ
• アークルーティングのトレンド

• 中国の郵便配達人問題– グラフのすべてのエッジを通る最短経路を見つけるリダイレクト先の簡単な説明を表示するページ 
• 車両経路問題– 最適化問題 
• 巡回セールスマン問題― 組み合わせ最適化におけるNP困難問題 
• オイラー経路– グラフにおいて、各辺を一度ずつ通過する経路 
• 容量制約付きアークルーティング問題
• グラフ理論の問題一覧– 離散数学の分野 リダイレクト先の簡単な説明を表示するページ 
• 除雪車の経路問題– アーク経路問題と車両経路問題の除雪への応用 
• 中国郵便配達人問題の複雑性リスト– 総距離と時間を最小化するルーティング問題のカテゴリリダイレクト先の簡単な説明を表示するページ