[HOME] [都市比較]

路線図と、平行四辺形の詰め込み問題

かなり昔にこの同じ問題を考えていたと思うのですが、その時に具体的には何の問題を抽象化した結果としてその問題を考えていたのか思い出せません。ということで、次回同じことを考え始めたときのために、今回のきっかけをメモしておきます。

モスクワの都市軸はどういう傾きなのだろうと思ってモスクワの地図を探していたら、モスクワの地下鉄の路線図が出てきて、中心は、東京の地下鉄の様にぐちゃぐちゃもつれ合っている様な路線図で、それを1重の環状線が囲み、環状線の内側の路線から郊外へ延びる放射状の線路が続いているというものでした。地下鉄の路線図の構成要素として考えられるのは、あとは、格子状の地下鉄くらいでしょうから、3つの要素が綺麗に組み合わさっていることにちょっと感動しました。

環状の路線  vs 放射状の路線

道路にしろ鉄道にしろ、最初は、放射状に発達し、次に周辺の都市を結ぶ環状の路線ができるというパターンがありますが、たとえば、中心から伸びる放射状の線路が何本になれば、環状の路線ができるのが普通なのか? という疑問があります。それを考えるための平均的な人口分布や、移動人口の分布のモデルはあるかなあとか思って、そのまま止まっています。郊外から郊外への移動の際に、環状の路線があれば、乗車距離は短くなるわけですが、道路なら問題なくても、電車の場合には、2度の乗り換えが必要になって、時間当たりの電車の本数によっては、待ち時間を含めた所要時間はあまり短縮されない可能性があります。

放射状の路線の問題

バス路線の場合は、地下鉄の場合と違って、かなりの路線数になっても、放射状の路線図を維持します。バスの場合、住宅地から鉄道の駅までを結ぶのが主な移動の目的ということもあるでしょう。しかし、市内での移動を目的とする人の場合は、用事が無くても乗り換えのために、いったん中心部のバスターミナルまで出てこなければならないということになります。例えば、タクシーや自転車で移動した場合と比べると、無駄な動きをしている様に感じてしまいます。これに対して、バス路線が格子状に走っていたとすればどうだろうかなどと思うわけですが、中心部を経由しない路線に乗る人の数はきわめて少ないでしょうから、実際的ではありません。

しかし、例えば、通勤時間帯なら、主要駅を中心とした放射状のバス路線が最適でも、時間帯によっては、商店街などの別の場所を中心とした放射状の路線なり、文化施設などを結ぶ環状の路線が最適になる可能性もあると思います。放射状のバス路線以外の可能性が常にあると思います。

放射状から網状の発展

あるいは、放射状の路線の発展系として、南からの路線がバスターミナルで終点になるのではなく、バスターミナルを経由して北に伸びる様な路線は容易に考えられます。それであれば、特定の経路に限った場合ですが、乗り換えなしで、目的地に到着することができます。

また、バスターミナルを途中駅にした場合には、乗り換えが集中するよりも、分散した方が良いので、乗り換える路線によって、乗換駅を変えるということになってきます。

こう考えると、モスクワの地下鉄路線図は、放射状の路線と、環状線が組み合わさったものの中心部が網状に変化したものとして理解できます。

図1

図1のように、N本の路線にそれぞれN-1の乗換駅があるという様な路線図をイメージしています。                             

図1を、阿弥陀くじに書き直すと図2になります。

図2

横線が駅に相当し、阿弥陀くじのルールに従ってたどったコースが路線に相当しています。ただし、スタートとゴールに2分する方法が複数になるので、1対1対応というわけには行きません。

あるいは、駅を人、路線をグループと見なして、N*(N-1)/2人の集団を、(N-1)人ずつのN種類のグループに配置する方法は何通りあるか? という問題にも置き換えることができます。ただし、それぞれの人はかならず2つのグループに属するものとします。

この路線図トポロジーを数え上げる問題が、何かもっと役に立つ場面があったと思うのですが、それにしては、この問題をあまり追求していないまま放置しているのが少し謎です。

思い出しました。

関連ページ

雑誌の記事

すごく、昔のことでした。1991年3月の、科学朝日のパズルの正解者欄とか書いてある様に昔、ピーター・フランクル氏が、出していた問題にプログラムで解いて応募したのでした。もともとの問題は、正2N角形を、N*(N-1)/2の平行四辺形に分割する問題で、12角形の場合をプログラムで解いたのでした。しかし、特に考えずに、実際に平行四辺形を詰め込んでみる様な解き方でした。

 
図3

図3の様に、1つの平行四辺形が、1つの乗換駅に対応しています。同じ傾きの線分のグループが路線に対応することになります。メモによれば、平行四辺形の問題が、こういう風に置き換えられることに気づいたのは2000年4月頃ですが、でも、それを思いついたのは別の関連した問題があったからかも知れません。

2000年2月20日ごろに自分の掲示板に書き込んでいました。やはり結局バス路線のことを考えていたみたいです。

関連ページ

bbs_log1

2003/6/19追記

 

地下鉄最適化問題

名前がわからないので、こう呼ぶことにします。TSP(巡回セールスマン問題)や最短木(最小木)の仲間として教科書に載っていても良いような気がするのですが、見たことがありません。googleで「TSP 最短木」を検索してヒットしたのは1件でした。

駅の位置が与えられた時にそれらを結ぶ総延長が最小になる地下鉄の路線図を描く問題です。乗り換えは1回以内で任意の2駅間を移動でき、どの駅も1つまたは、2つの路線が 通っているという条件です。

駅の配置によっては、すべての駅を1つの路線で結ぶというのが最適解になる場合もあります。

すべての路線が、2n多角形の相対する頂点を結ぶ様になっている場合、もともとの平行四辺形の詰め込み問題と双対になります。平行四辺形詰め込み問題と双対の路線図の場合では、2つの路線が乗換駅で必ず交差することになりますが、交差せずに、また離れるというのでも、地下鉄最適化問題にとっては同じ結論になると思います。n*(n−1)/2個の乗換駅と2n個の外周部の駅という関係が、地下鉄最適化問題にとって、なんらかの特別な位置を占めるのかどうかはわかりません。駅が均等に分布している場合には、その場合が最適なことが多いとかなれば、それは美しい結論なのですが。

交差すべきところで、近づいてまた離れる場合には、乗り換え回数を1回以内に収めることができなくなるので、間違っていました。

2003/6/22追記

すべての2つの駅の組み合わせについての移動距離の平均を最小化する様に路線図を描く という別の問題も考えられます。平均移動距離を最小化する場合には、それぞれの路線が環状線になった方が有利になります。8の字状の路線 を1路線と考えるのか? とか、8の字の交点の駅にさらにもう1つの路線が通る と、中央駅からの放射状の路線図になってしまうとか、違う問題になるので、ここでは考えません。実際には、周辺部の駅の人気の低さの重み付けをすることによって、最初の条件と似た結論になりそうな気もするのですが。

2003/6/22追記

そもそも名前がわからない

TSP、最短木、格子、スター、ループ

これらでないことは明らかですよね。

ニューサイエンス関連の自殺した作家(名前度忘れ)が、ヒエラルキー構造に対して、ヘテラルキー構造と言っていたのですが、単に双峰性とか訳してあった様な記憶があるので、かならずしも、こういう構造ではありませんよね。ヘテラルキーの用語を作った人の本は読んでいませんし。

類義語を探すと、クロスバというのが出てきました。あと、ループではなくリングでした。完全結合、ライン?リニア?、トーラス

{ドロネー図、ガブリエルグラフ、相対近傍グラフ、最近傍グラフ、最小木}みたいに何かのシリーズの中に地下鉄路線図が入らないかなあ

2003/6/23追記

2003/6/22追記

国際会議の同時通訳ブースの例

問題を変えると、別の要因が関係してきたりして、最適な場合が変化しますが、国際会議の場面を想定すると、同時通訳の人は、乗換駅、会議の参加者は、途中駅、言語は路線という風な対応関係が見つかります。そして、この例で特異なのは、スター型の接続方法では、いったん開催地の言語なり英語なりに翻訳して、それぞれの参加者の言語に翻訳するという最大2度の乗り換えが前提になっているということです。

翻訳回数 構造
1度以下 完全結合
2度以下 放射状と環状
2度以下 放射状
限定なし 木構造

2003/7/5追記

ソフトウェア開発プロジェクトの例

例えば、デジカメとプリンタだけで完結して、パソコンは不要になるという様な流れがあります。対応すべき標準が増えて開発の手間が余計にかかるだけとも思えますが、1対1のインタフェイスには、簡潔で無駄が無いという魅力があり、 ユーザーにとっても、余分な機能が無い分、操作が簡単になります。

構造 メリット 問題
地下鉄      
スター クローズド 計画的で効率的な開発 細分化されすぎて、重複コードが増える
オープンソース 問題があっても一部分の手直しでOK 全体を管理できないので、瑣末な違いでバージョンが増える

2003/7/5追記

関連ページ

CPUの接続方法

菱形42面体、菱形56面体、菱形72面体

格子状でない十字路網

外部リンク

UrbanRail.Net Europe Russia Moskva (Moscow) Metro
metroPlanet Europe Russia Moskva (Moscow) Metro

 

作成 2003/6/18 - 更新 2007/04/12

都市比較ディレクトリ

Google
Web www.PAG1U.net

関連ディレクトリ

姫路

発明 

家系図

通信

古代史

関連サイト

 
 
 
 
 
 
 
 
 

 

seo

[HOME]  [都市比較] (C)MATSUOKA , Hajime