空間充填曲線のある組合せ論的応用
Some combinatorial applications of spacefilling curves (www2.isye.gatech.edu)
要約
空間充填曲線、特にSierpinski曲線は、巡回セールスマン問題(TSP)に対する高速なヒューリスティック解法として応用されています。この手法は距離計算が不要で並列化可能ですが、最適解より約25%長い経路を生成します。このアルゴリズムは、ルーティングシステムや戦略防衛構想のレーザー照準など、様々な実用的なアプリケーションで利用されてきました。
全文翻訳
空間充填曲線による組み合わせ論的応用
[画像: 空間充填曲線は、点の集合に対するヒューリスティックな巡回経路を示唆しています]
図1: 巡回セールスマン問題に対するヒューリスティックな解法は、Sierpinski空間充填曲線と同じ順序で点を巡回することです。
空間充填曲線とは、低次元空間から高次元空間への連続写像のことです。有名な空間充填曲線としてSierpinskiによるものがあり、これは単純なパターンを繰り返しコピーして縮小することによって形成されます(図1の複雑な巡回経路)。
空間充填曲線の有用な特性は、ある領域に入ると、その領域内のすべての点を一度は訪れる傾向があることです。したがって、平面上で近い位置にある点は、曲線に沿った見た目でも近い位置にある傾向があります。
これが、L. Platzmanと私が考案した、n個の与えられた場所(いわゆる巡回セールスマン問題)に対して、比較的短い巡回経路を生成するためのヒューリスティックの基礎となります。単純に、空間充填曲線が登場するのと同じ順序でそれらを訪れます。例えば、赤で示された点に対する短い巡回経路は、緑の線で示されており、空間充填曲線上の出現順に点を結んでいます。
空間充填曲線ヒューリスティック(SFC)には多くの利点があります。ただし、最適解より約25%長い解を受け入れる用意がある場合(ランダムな点の集合に対する期待値)です。これらの利点には以下が含まれます:
- SFCアルゴリズムは高速です。n個の点の経路を構築するのにO(n log n)の労力しかかからず、点の追加や削除による解の更新にはO(log n)の労力しかかかりません。
- SFCヒューリスティックは、点間の明示的な距離を必要としません。そのため、他のほとんどのヒューリスティックが計算または測定する必要があるような距離を計算したり測定したりする必要がありません。
- アルゴリズムは並列化可能です。(比較として、同等のアルゴリズムである最近傍法は、明らかに並列化できません。)
- ランダムな点に対するSFC経路のリンク長は、小さく、分散も小さいと期待されるため、(1/k)番目の停止地点が、移動時間の約(1/k)を占めます。これは、SFC経路をk個の車両用の経路に、SFCルートをk個のセグメントに分割するだけで簡単に変換できることを意味します。
空間充填曲線ヒューリスティックは、多くのアプリケーションで使用されてきました。それには以下が含まれます:
- フルトン郡(ジョージア州アトランタ)のMeals-on-Wheels(配食サービス)のルーティングシステム構築。これは、自分で買い物をするのが困難なほど病気または高齢の人々に毎日数百食を配達しています。私たちはこれを2つのローロデックスカードファイル上に構築しました。
- アメリカ赤十字によるアトランタ都市圏の病院への血液配送のルーティング。
- 戦略防衛構想(一般に「スター・ウォーズ」プログラムとして知られる)の宇宙ベースレーザーのターゲティング。このアプリケーションは、TRW Systemsの科学者(SDIの契約業者)から伝えられました。彼らは、SFCヒューリスティックが、よく分析されており、並列化可能で、軌道に打ち上げ可能なコンピュータで実行できるため、代替手段よりもSFCヒューリスティックを選択しました。
- 地図描画のためのペンプロッターの制御。(東京大学のIri氏と共同研究者たちは、ペンを効率的にルーティングすることで大規模な道路地図の描画時間を短縮する方法を示しました。彼らは、描画時間が10時間から1時間半に短縮された例を挙げました。)
空間充填曲線によるルーティングのアイデアは、その後、ARC/Info地理情報システム、Baan SystemsのCAPS Logistics Toolkit、およびその他の2次元データを管理する商用システムに組み込まれました。
技術的な詳細を省き、技術文献へのポインタを含めたアイデアの概要は、私のクラスノート「空間充填曲線に基づくルーティングシステム」[PDF形式、22ページ]で見つけることができます。これに加えて、100 x 100グリッドの点のSierpinskiインデックスのテーブル(PDF形式、22ページ)があり、これを使えば午後に独自のルーティングシステムを構築できます。アルゴリズムのパフォーマンスに関する技術的な詳細と、関連研究への引用は、「Spacefilling curves and the planar travelling salesman problem」L. K. Platzmanとの共著、Journal of the Association for Computing Machinery 36(4):719-737 (1989)で見つけることができます。
[画像: ドイツの15,112都市を巡回する空間充填曲線ソリューション]
図2: ドイツの15,112都市のTSP巡回。この巡回は、Sierpinski空間充填曲線によって1秒未満で生成され、最短可能な経路よりも約1/3長くなっています。
この軽量なヒューリスティックを、D. Applegate、R. Bixby、V. Chvatal、およびW. Cookによって開発されたような、ヘビーデューティーな最適化パッケージと比較するのは興味深いです。彼らのTSPパッケージは、数学的最適化技術の偉業であり、ドイツの15,112都市の巡回セールスマン問題を解決するために使用されました。これは、証明可能な最適解が生成された最大の非自明な問題です。Applegateらは計算リソースについて説明しています:「計算は、ライス大学とプリンストン大学にある110プロセッサのネットワーク上で行われました。計算に使用された総コンピュータ時間は、500 MHzで動作するCompaq EV6 Alphaプロセッサにスケールすると22.6年でした。最適巡回長は、TSPLIBで使用される単位で1,573,084であり、これはドイツを約66,000キロメートル移動することに相当します。」
比較として、Paul Goldsmanは同じインスタンスを空間充填曲線ヒューリスティックを使用して解決しました。私たちの解は(図2で)約34%長くなりました。1日あたり600 kmの移動とすると、総運転時間は110日 versus 147日になります。しかし、私たちの計算は安価なラップトップで1秒未満で完了しました。したがって、トレードオフは次のようになります。私たちのヒューリスティックを使用すると、すぐにルートが得られますが、1ヶ月余分に移動する必要があります。あるいは、110プロセッサのネットワークを構成し、2ヶ月かけて最短ルートを計算して、1ヶ月の運転時間を節約します。
[画像: 三角形がパスを形成するようにシーケンス化された三角形分割不規則ネットワーク]
図3: 三角形分割不規則ネットワークのすべての点を、三角形のハミルトンパスまたは回路を見つけ、それぞれに適切に方向付けられた空間充填曲線で満たすことによって連続的にインデックス付けできます。
Bill Nulty、Paul Goldsman、および私は、これらのアイデアをいくつかの方向に拡張しました:
- 「Robust Multidimensional Searching with Spacefilling Curves」J. BartholdiおよびW. Nulty著、Proceedings of the Sixth International Symposium on Spatial Data Handling、エディンバラ、スコットランド、1994年9月。
- 地球の階層的分割の連続インデックス付け J. BartholdiおよびP. Goldsman著(2000年)。これは、Int. J. Geographical Information Science 15(6):489-522 (2001)にわずかに改訂された形で掲載されました。
- Hilbert空間充填曲線の頂点ラベリングアルゴリズム J. BartholdiおよびP. Goldsman著(2000年)。これは、Software -- Practice and Experience 31:395-408 (2000)にわずかに改訂された形で掲載されました。
- 三角形分割不規則ネットワークの頂点隣接双対はハミルトンサイクルを持つ J. BartholdiおよびP. Goldsman著、Operations Research Letters 32 (2004)。Perouz Taslakianは、アイデアとアルゴリズムの非常に優れたイラストを作成しました。