中国郵便配達問題（経路検査問題）

主要な概念と性質

オイラー閉路とは、すべての辺をちょうど1回ずつ使う閉じた道であり、存在するなら理想的な解である。連結な無向グラフがオイラー閉路をもつのは、各頂点の次数がすべて偶数のときに限られる。グラフがすでにオイラー的であれば、中国郵便配達問題の解は単に任意のオイラー巡回路でよい。奇数次数の頂点がある場合には、すべての次数を偶数にするために一部の辺を重複して通る必要があり、そのぶん全体の長さが増える。

無向グラフに対するアルゴリズムの概略

重み付き無向グラフに対する標準的な多項式時間手法は、おおむね次の通りである。

• 次数が奇数の頂点をすべて特定する。
• 奇数頂点同士の各組について最短経路距離を計算する（ダイクストラ法、または全点対最短経路法を用いる）。
• その距離を辺重みとして、奇数頂点の間で最小重み完全マッチングを求め、対応する元の辺を最短経路に沿って重複させる。
• これで全頂点の次数が偶数になるので、オイラー多重グラフを作り、各元の辺を少なくとも1回含む最短閉路としてオイラー閉路を取り出す。

この還元では最小重み完全マッチングの部分手続きが必要であり、Edmonds のブロッサム・アルゴリズムはその代表的な解法として知られている。そのため、無向グラフでは全体として多項式時間で解くことができる。

有向・混合・その他の変種

有向グラフでは、しばしば最小費用流やサーキュレーションの手法で入次数と出次数を釣り合わせ、その後、平衡化された有向多重グラフのオイラー巡回路を求める。変種の中にははるかに難しいものもある。ウィンディ郵便配達問題（辺の費用が通る向きに依存する）やルーラル郵便配達問題（指定された一部の辺だけをカバーすればよい）は、一般には NP 困難である。無向辺と有向辺の両方を含む混合グラフも、無向の場合より計算上難しい定式化になる。

歴史・用語・応用

この問題は、1960年代初頭の論文に由来するとされ、しばしば中国人研究者（一般には Mei-Ku Kwan あるいはそれに近いローマ字表記）に帰される。英語名の "Chinese postman problem" は後に広まり、初期の採用例として米国標準局の Alan Goldman の名が挙げられることがある。route inspection という用語も広く使われている。

実際の利用と注目点

応用は郵便配達に限られない。街路清掃、除雪、ゴミ収集、検針、保守の巡回計画などで典型的に用いられる。奇数頂点を最短経路で対にする方法は、辺をすべて覆う目的を、より少数の頂点上のマッチング問題へと変換する重要な着想である。関連するグラフ理論の背景としては、オイラー路や経路検査の入門を参照するとよい。応用寄りの解説としては、郵便ルーティングや物流最適化に関する資料がある。

無向の中国郵便配達問題には効率的で厳密なアルゴリズムがある一方、時間窓、車両容量、非対称コスト、部分的なカバー要件など、現実の制約が加わるとより難しい問題になるため、ヒューリスティックや整数計画法が必要になることが多い。研究では、大規模ネットワーク向けの特化した定式化や高速実装も継続して検討されている。