混合中国語郵便配達員問題

混合中国郵便配達問題 (MCPP または MCP)は、頂点の集合 V、正の有理数重みを持つ無向辺の集合 E、および正の有理数重みを持つ有向弧の集合 A を持つグラフの最短走査で、各辺または弧を少なくとも 1 回は最小コストでカバーする経路を探す問題です。^{[1]この問題は、} PapadimitriouによってNP 完全であることが証明されています。^[2]混合中国郵便配達問題は、一部の道路は両方向に通過するには狭すぎる一方で、他の道路は双方向で両方向に除雪できるような、雪かきなどの弧ルーティング問題でよく発生します。グラフが強く接続されているかどうかを確認することで、混合グラフに任意のサイズの郵便配達ツアーがあるかどうかを簡単に確認できます。郵便配達ツアーを各弧を 1 回だけ通過するように制限するか、各辺を 1 回だけ通過するように制限すると、Zaragoza Martinez によって証明されたように、この問題は NP 困難です。^{[3] [4]}

数学的な定義は次のとおりです。

入力:すべてのエッジにコストがあり、最大コストが指定された、強く接続された混合グラフ。 ${\displaystyle G=(V,E,A)}$${\displaystyle c(e)\geq 0}$${\displaystyle e\subset E\cup A}$${\displaystyle c_{max}}$

質問: 内のすべての辺と内のすべての弧を少なくとも1回通過し、コストが最大で である(有向)ツアーは存在するか? ^[5]${\displaystyle E}$${\displaystyle A}$${\displaystyle c_{max}}$

混合中国郵便配達問題を解決する際の主な難しさは、ツアーの予算が厳しく、各辺を 1 回しか通過できないときに、(無向) 辺の方向を選択することです。次に、辺の方向を決め、さらにアークを追加して、有向オイラーグラフを取得する必要があります。つまり、すべての頂点のバランスをとる必要があります。1 つの頂点に複数の辺が接続している場合、各辺の正しい方向を決定するのは簡単な作業ではありません。^[6]数学者の Papadimitriou は、この問題をさらに制限して分析しました。「入力グラフが平面で、各頂点の次数が最大 3 で、各辺とアークのコストが 1 であっても、混合中国郵便配達は NP 完全です。」^[7]

混合グラフがオイラーグラフであるかどうかを確認するプロセスは、混合中国郵便配達員問題を解くアルゴリズムを作成する上で重要です。混合グラフGの次数はオイラー閉路を持つためには偶数でなければなりませんが、これだけでは十分ではありません。^[8]

混合中国郵便配達員がNP困難であるという事実は、最適解に合理的な閾値で近づく多項式時間アルゴリズムの探索につながった。フレデリックソンは、平面グラフに適用できる係数3/2の方法を開発し、^[9]ラガヴァチャリとヴェラサミーは平面である必要のない方法を発見した。^[10]しかし、多項式時間では、デッドヘッディングのコスト、つまり除雪車が除雪する道路に到達するのにかかる時間や、道路清掃車が清掃する道路に到達するのにかかる時間を見つけることはできない。^{[11] [12]}

頂点集合、辺集合 、弧集合、および各 の非負のコストを持つ強く連結された混合グラフが与えられた場合、MCPP は、各リンクを少なくとも 1 回 通過する最小コスト ツアーを見つけることから構成されます。${\displaystyle G=(V,E,A)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle A}$${\displaystyle c_{e}}$${\displaystyle e\in E\cup A}$${\displaystyle e\in E\cup A}$

、、が与えられた場合、は 、およびにちょうど 1 つの端点を持つ辺の集合を表します。頂点 が与えられた場合 、(入次数) は に入る弧の数、(出次数) は を出る弧の数、(次数) は に接続するリンクの数を表します。^[13]であることに注意してください。混合グラフは、そのすべての頂点の次数が偶数である場合に偶数と呼ばれ、各頂点に対して である場合に対称的であると呼ばれ、頂点の任意の部分集合が与えられた場合に、 から、へ向かう 弧の数と から、へ向かう弧の数の差が、と、 を結ぶ無向辺の数よりも大きくない場合にバランスが取れていると言われます。${\displaystyle S\subset V}$${\displaystyle \delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}}$${\displaystyle \delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}}$${\displaystyle \delta (S)}$${\displaystyle S}$${\displaystyle \delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}}$${\textstyle i}$${\displaystyle d_{i}^{-}}$${\displaystyle i}$${\displaystyle d_{i}^{+}}$${\textstyle i}$${\displaystyle d_{i}}$${\displaystyle i}$${\displaystyle d_{i}=|\delta ^{\star }(\{{i}\})|}$${\displaystyle G=(V,E,A)}$${\displaystyle d_{i}^{-}=d_{i}^{+}}$${\textstyle i}$${\displaystyle S}$${\displaystyle S}$${\displaystyle V\backslash S}$${\displaystyle |\delta ^{+}(S)|}$${\displaystyle V\backslash S}$${\displaystyle S}$${\displaystyle |\delta ^{-}(S)|}$${\displaystyle S}$${\displaystyle V\backslash S}$${\displaystyle |\delta (S)|}$

混合グラフがオイラーグラフであるためには、が偶数かつバランスが取れている必要があることはよく知られている事実です。^[14]が偶数かつ対称である場合、G もバランスが取れている（かつオイラーである）ことに注意してください。さらに、が偶数である場合、は多項式時間で正確に解くことができます。^[15]${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle MCPP}$

1. 偶数で強く連結された混合グラフ が与えられている場合、は、 と の辺に同じコストで方向をランダムに割り当てることによって得られる弧の集合であるとします。有向グラフ の各頂点 i について を計算します。 を持つ頂点は、供給 需要 を持つソース (シンク) と見なされます。 は偶数グラフであるため、すべての供給と需要は偶数であることに注意してください(ゼロは偶数と見なされます)。${\displaystyle G=(V,E,A)}$${\displaystyle A_{1}}$${\displaystyle E}$${\displaystyle s_{i}=d_{i}^{-}-d_{i}^{+}}$${\displaystyle (V,A\cup A_{1})}$${\textstyle i}$${\displaystyle s_{i}>0(s_{i}}}$${\displaystyle s_{i}(-s_{i})}$${\displaystyle G}$
2. を、それらの対応する辺のコストを持つ、 の反対方向の弧の集合とし、を、コストがゼロでに平行な弧の集合とします。${\displaystyle A_{2}}$${\displaystyle A_{1}}$${\displaystyle A_{3}}$${\displaystyle A_{2}}$
3. すべての頂点の需要を満たすには、グラフ 内の各弧の容量が無限大で、 内の各弧の容量が 2 である、グラフ 内の最小コスト フロー問題を解きます。 を最適フローとします。${\displaystyle s_{i}}$${\displaystyle (V,A\cup A_{1}\cup A_{2}\cup A_{3})}$${\displaystyle A\cup A_{1}\cup A_{2}}$${\displaystyle A_{3}}$${\displaystyle x_{ij}}$
4. 内の各アークに対して、次の操作を実行します。 の場合、 内の対応するエッジを から に向けます(手順1 で関連付けられたエッジに割り当てられたから への方向は「間違っています」)。 の場合、 内の対応するエッジを から に向けます(この場合、手順 1 の方向は「正しい」です)。内のアークを通るフロー値はすべて偶数であるため、このケースは不可能であることに注意してください。${\displaystyle (i,j)}$${\displaystyle A_{3}}$${\displaystyle x_{ij}=2}$${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle x_{ij}=0}$${\displaystyle G}$${\displaystyle j}$${\displaystyle i}$${\displaystyle x_{ij}=1}$${\displaystyle A_{3}}$
5. の各弧のコピーを追加してを増やします。結果のグラフは偶数かつ対称です。${\displaystyle G}$${\displaystyle x_{ij}}$${\displaystyle A\cup A_{1}\cup A_{2}}$

混合グラフが偶数でなく、ノードがすべて偶数次数ではない場合、グラフを偶数グラフに変換できます。

• が強く連結された混合グラフであるとします。弧の方向を無視して奇数次ノードを見つけ、最小コストのマッチングを取得します。最小コストのマッチングからのエッジでグラフを拡張して、偶数グラフを生成します。${\displaystyle \mathrm {G=\{V,E,A\}} }$${\displaystyle \mathrm {G'=\{V',E',A'\}} }$
• グラフは偶数ですが対称ではありません。オイラー混合グラフは偶数かつ対称です。 の最小コストフロー問題を解くと、偶数ではない可能性のある対称グラフが得られます。${\displaystyle G'}$${\displaystyle G''}$
• 最後のステップでは、対称グラフを均等にします。奇数次のノードにラベルを付けます。内のポイントで開始および終了する、アーク セット内の線とエッジ セット内の線の間で交互に発生するサイクルを見つけます。 内のアークは、有向アークではなく、無向エッジとして考える必要があります。${\displaystyle G''}$${\displaystyle V_{O}}$${\displaystyle A''\backslash A}$${\displaystyle E''}$${\displaystyle V_{O}}$${\displaystyle A''\backslash A}$

Hua Jiangらが発表した論文では、集団を操作することで混合中国郵便配達員問題を解く遺伝的アルゴリズムが提示された。このアルゴリズムは、MCPPの他の近似アルゴリズムと比較して優れたパフォーマンスを示した。^[16]

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