大回り乗車として知られている特殊な乗車方法があります。 例えば、東京→有楽町の乗車券で、逆回りに東京→上野→池袋→品川→有楽町と乗ったりすることです。 こういう乗車方法は、ある一定のルールを守れば鉄道会社との契約違反にはなりません。
概ね、大回り乗車を可能にしているルールは、次の3つがあります。
JRの大都市近郊区間については、大都市近郊区間であれば、券面の経路以外を乗車しても良い、という規則(選択乗車と言います)を利用しています。 ストアードフェアカード(ICカードも含む)については、一般的に、自動改札機による処理を前提としていることと、 乗車時には降車駅やそこに至る経路が決まっておらず乗車経路が特定不可能なため、 最安値で計算するという規則(最安運賃計算と言います)になっていることを利用しています。 私鉄については、会社によって違いますが、選択乗車か最安運賃計算のどちらかの規則があることが多いです。(ない場合もあります。)
ここでは、大回り乗車のうち、最も距離のかせげるルートは何かを計算しよう、ということを考えています。 できるだけ路線の形に左右されない、一般的な解法を考えて、いろんなタイプの大回り乗車に適用可能なように考えます。 こうして乗れる経路を、ここでは「最長大回り経路」と呼びます。
最長乗車経路を求める方法としては、整数計画法を用いると、 比較的短時間で、数学的に最長であることが保証できる経路を求められることが知られています。 インターネット上での初出は葛西隆也氏による最長片道きっぷの経路算出でしょう。
最長大回り経路については、近藤英明氏によって、EXCELによる最長片道ルート探索の一環として、 東京近郊区間の130円、150円ルートや東京メトロの160円での最長大回り経路が調べられています。 近藤英明氏はExcel付属のソルバーを用いて誰でもお手軽に、というところを目指した功績が大きいでしょう。
しかし、その後葛西隆也氏によって紹介されたGLPKというソルバーと、これを用いた葛西隆也氏作のLOP toolkitを使うことで、 整数計画法で最長経路の算出はさらに楽になりました。Excelのものよりかなり高速に解くことができます。 (その代わり、数式ファイルは自作しなくてはなりませんが。)
今回は、このGLPKを用いて最長大回り経路の求め方を考えてみようと思います。
葛西隆也氏による分類ですが、JRでは一枚の乗車券で乗車できる経路の形状は、L型、O型、P型をしています。 その他の私鉄でも、だいたい同じでしょう(O,P型が存在しないかもしれません)。 このうち、L型とO型が最長大回り経路に成り得ます。 P型の大回り、6の字大回りと言うほうが一般的ですが、この是非については、かなり意見が割れており、 一応「相当理論武装すれば可能であるが、やめておくのが無難」という扱いになっているようです。 なので、ここでは対象外とします。
また、O型経路ができる条件もかなり限られています。 JRの近郊区間の場合、駅Aから駅B,Cを経由して駅Aに戻ってくるX円の経路が存在すれば、X円でA→B→C→A以外の経路(A→D→E→F→...→A)に乗れます。 X円を初乗り運賃とした場合、秋葉原、御茶ノ水、神田しかこの駅A,B,Cに当てはまりません。 O型経路が最長になるとしたら、このX円の経路内にある駅ならどこを発着駅にしても構いません。 私鉄ではO型が可能な規則を持つところもあるようです。
一番ありがちなのは、L型経路でしょう。ただ、この経路はもう少し分類できます。 一般的には、大回り経路というと、Cのような形をしたルートをイメージするかもしれません。 しかし、それだけではありません。8の字を少し切った、Sのようなルートも大回り経路に成り得ます。 最短経路と大回り経路がクロスできるところがポイントです。
そこで、L型大回り経路と、最短経路をあわせた形がどうなるか分類しました。
黒線が最長大回り経路、ピンクの線が最短経路です。このぐらいの形状をとり得ると思います。
以下では、ピンクの線を「券面経路」、この経路を乗るのに必要なきっぷで乗れる最長距離を「券面距離」と言います。
(例えば、券面経路が東京→有楽町なら、運賃130円なので、券面距離は3kmです。)
あとは、8や呂を縦につなげた、
こんな経路もあるかと思います。(さすがに初乗りではないでしょうが、1000円以内でできる大回りとか考えるとこういうのが出てくる可能性はあります。)
さて、ここまで分類しましたが、目的としては、発着駅候補を絞り込みたいのです。 左上のOを1箇所切っただけのものをこれ以後C型と呼びますが、L型のうちC型以外は、発着駅以外に、分岐駅が必ず1つ以上あります。 そして、発着駅は最寄りの分岐駅から、券面距離以内に確実にあります。 さらに言うと、券面距離から、分岐駅からすべての隣駅への距離のうち最短のものを引いた距離以内にあります。 分岐駅から隣駅への距離がすべて券面距離の半分を超えている場合、その周辺駅は発着駅にはなり得ません。 こうして周辺駅を取り除いた後、隣の分岐駅まで券面距離以上離れている分岐駅も発着駅にはなり得ません。 例えば、東京近郊区間で130円(3km)大回りを考えるとき、 新宿の周辺で発着駅になりうる駅を探すため3km以内にある駅を集めてくるとこれぐらいです。
信濃町 | 2.4km |
千駄ヶ谷 | 1.7km |
原宿 | 2.2km |
代々木 | 0.7km |
新大久保 | 1.3km |
高田馬場 | 2.7km |
大久保 | 1.4km |
東中野 | 2.5km |
新宿から最寄りの駅は代々木の0.7kmです。つまり、ここであげた全駅が発着駅候補になるわけではなく、 3.0km-0.7km=2.3km以内の駅しか発着駅候補になりませんから、信濃町、高田馬場、東中野が候補から外れます。 (もっとも、信濃町は代々木を基準とした発着駅候補として復活します。)
これが、品川の周辺だとこうなります。
田町 | 2.2km |
大井町 | 2.4km |
大崎 | 2.0km |
五反田 | 2.9km |
西大井 | 3.6km |
最寄りは大崎の2.0kmですが、品川を挟むようにとるとあと1.0kmしかありません。1.0km以下のところはないので、 ここに挙げたすべての駅が発着駅候補からはずれます。 さらに、品川も3km以内に分岐駅はないため、品川も発着駅にはならず、分岐駅としてだけ残ります。
C型以外のL型は、こうして選んだ発着駅候補と分岐駅だけをグラフの頂点として最長経路を求めればよいことになります。 券面距離が分岐駅間の長さに比べて小さいことが多い場合は、発着候補駅のフィルタとしてはそこそこ有効なはずです。
では、最長大回り経路がC型である場合、どうすれば計算できるでしょうか?
たとえばこんな路線だった場合、C型が最長になってしまいます。しかも、前述の発着駅絞り込みから外れてしまいます(券面距離3kmの場合)。
最長はL型0.8+1.9+10.0+0.5=13.2kmでも、L型0.8+2.0+0.5+10.0=13.3kmでもなく、C型2.0+1.9+10.0=13.9kmです。
C型最長は、長いO型をいくつか求めて、それらの最短の区間を1つ切断すれば求まるはずです。 なので、O型がL型の長さを超えていて、O型乗車が不可能な場合、C型が最長になる可能性があるので考えねばなりません。 上記例の場合、L型最長13.3kmとO型最長14.4kmなので、O型が不可能な規則の場合はC型が最長になる可能性を検討する必要がある、ということです。
「長いO型をいくつか」と書きましたが、多少補足が必要です。 例えば求めたい路線ネットワークのうち、最短の駅間が0.5kmで、O型最長が110.0km、この経路に含まれる最短の駅間が0.8kmだったとします。 すると、このO型の最長のものから0.8kmを引いた、109.2kmがこのO型から得られるC型経路になります。 しかし、これだけでは109.2kmがC型最長であるとは断言できません。 次点の109.8kmのO型経路が0.5kmの区間を含んでいた場合、109.3kmというC型経路が求まって、最長になるでしょう。 つまり、この場合109.7kmまでのO型経路を探索すれば、最長のC型経路が出てくると言えます。 最長のC型はこのようにして求められます。
とは言っても、C型が最長大回り経路になることはあまりないでしょう。普通に考えて、L型>O型>C型になりそうなものです。 なので、L型とO型の最長経路を求めて、L型>O型になっていればL型が最長であることが確認できる、という手順になりそうです。 O型>C型は確実に言えますが、O型が乗車不可能であるときにC型が最長経路になる可能性はあります。がたぶん考えることはないでしょう。
ということで、L型、O型を整数計画法で表現する制約式を考えましょう。
ある駅からのびる枝を0本または2本用いるという式を葛西隆也氏が提示しています。駅から枝a,b,cがのびている場合、各枝を用いるとき1、 用いないとき0とする変数Ea, Eb, Ecを用意すると、
Ea + Eb + Ec ≦ 2
- Ea + Eb + Ec ≧ 0
Ea - Eb + Ec ≧ 0
Ea + Eb - Ec ≧ 0
これでEa, Eb, Ecのうち2つが1、1つが0であるという状態を表現できます。
O型の場合、制約式は基本的にこれだけで済みそうです。 L型はもう少し面倒です。発着駅に限り、枝は1本しか使ってほしくありません。 そこで、駅sが発駅であれば1、発駅でなければ0とする変数Fs、着駅であれば1、着駅でなければ0とする変数Tsを加えます。 あと、発着が同じ駅になっては困るのでそれも入れておきます。
Fs + Ts + Ea + Eb + Ec ≦ 2
- Fs + Ts + Ea + Eb + Ec ≧ 0
Fs - Ts + Ea + Eb + Ec ≧ 0
Fs + Ts - Ea + Eb + Ec ≧ 0
Fs + Ts + Ea - Eb + Ec ≧ 0
Fs + Ts + Ea + Eb - Ec ≧ 0
Fs + Ts ≦ 1
また、発着駅はそれぞれ1つずつなので、
Fs + Ft + Fu + Fv + ... = 1
Ts + Tt + Tu + Tv + ... = 1
という式が必要そうです。さらに発着駅の間が券面距離以下でなければなりません。 こうした発着駅の組合せは、あらかじめ用意しておくしかなさそうです。 そして書き方としては、駅sに対して、駅t, u, v, ...からでは発着駅の組合せになれない、と書くしか思いつきませんでした。
Fs + Tt + Tu + Tv + ... ≦ 1
あとは、最大化する目的関数です。これは簡単です。枝a,b,cの長さをDa, Db, Dcとすると、
Ea×Da + Eb×Db + Ec×Dc + ...
ですね。制約式は概ねこれでいいと思います。 ただし、整数計画法によるアプローチにはつきものですが、孤立したループが作られてしまう可能性が高いです。 孤立ループは、葛西隆也氏の方法と同様、出現してからそれを禁止する制約を増やせばよいと思います。 例えば、枝a,b,c,dによる孤立ループができてしまった場合は、
Ea + Eb + Ec + Ed ≦ 3
という制約式を追加して解き直すという手法をとります。
さて、ここまで乗換は無条件にできることを想定していたわけですが、実際には制約が加わったり、逆に特殊に可能になるようなものがあったりします。 そうした乗換パターンを分類してみました。
乗換パターン名 | 詳細 | 乗換条件 | 例 |
---|---|---|---|
無条件 | 特に条件なく、乗換可能である。 | なし。 | ほとんどの乗換駅 |
中間改札 | 路線Aと路線Bの間に中間改札がある。 | JR鶴見・加古川(有人窓口) | |
ラッチ外乗換 | 路線Aと路線Bを乗り継ぐには、一度改札外に出る必要がある。 | 特になし | JR浜川崎・折尾 |
発着駅が同じ会社であり、発駅からの距離が券面キロ以内にあること | メトロ上野・三越前・池袋・飯田橋・九段下・渋谷、都営蔵前 | ||
大回り中は利用できない(実乗経路計算)。 | 東急渋谷 | ||
全列車通過 | 分岐駅を全列車が通過するため、乗り換えられない。しかし、その救済のため、経路によっては区間外への折り返し乗車を認める特例が存在することがある。 | 特例規則の範囲で乗ること | JR鶴見・東神奈川・日暮里 |
乗り入れ列車 | 乗り入れ列車に乗車して通過するときのみ別線に移ることができる。 | 列車進行方向に移動すること | 西船橋(JR〜メトロ)、栗橋(JR〜東武) |
乗換可他駅 | ラッチ外で、他の駅に乗り換えられる。乗り換えなければ他駅として扱う。 | 発着駅が同じ会社であり、発駅から途中下車駅までの距離が券面距離以内にあること。2社に対しての合計金額以内で発駅から途中下車駅まで乗れる場合も含む。 | メトロ上野広小路〜仲御徒町・淡路町〜新御茶ノ水・日比谷〜有楽町、都営東日本橋〜馬喰横山、大阪市営梅田〜東梅田〜西梅田、メトロ/都営乗換可能な各駅。 |
ラッチ内乗換可他駅 | 改札なく乗換可能な他駅。乗り換えなければ他駅として扱う。 | 特になし | メトロ赤坂見附〜永田町・溜池山王〜国会議事堂前、大阪市営心斎橋〜四ツ橋 |
整数計画法のモデルにあらかじめ用意しておくのが良さそう制約は、一律に乗換を禁止する制約、 発駅からの距離が券面距離を超える場合に乗換を禁止する制約、でしょうか。 また、他駅への乗換は距離0の徒歩という路線を設定することで表現できそうです。 実乗経路計算については、乗換駅の隣から券面キロ以内にある駅を、乗換駅で接続可能な別路線として切り出せばいいでしょう。 その他の制約については、出現し次第に禁止するという扱いでいいと思います。
制約式は以下のように書けるでしょう。枝a,bと枝c,dの間の乗換禁止:
Ea + Ec ≦ 1
Ea + Ed ≦ 1
Eb + Ec ≦ 1
Eb + Ed ≦ 1
駅s,t,uを発駅とするとき枝a,bと枝c,dの間の乗換禁止:
Ea + Ec + Fs + Ft + Fu ≦ 2
Ea + Ed + Fs + Ft + Fu ≦ 2
Eb + Ec + Fs + Ft + Fu ≦ 2
Eb + Ed + Fs + Ft + Fu ≦ 2
ところで、よくわからないので今回無視しましたが、メトロの臨時列車で他線に乗り入れるものがあります(東京湾大華火祭臨時や臨時特急ベイリゾートなどの有楽町線直通が典型)。 普段は営業路線にならない連絡線を通過しますが、これの経由駅はどうなるのでしょうか?JRみたいに運賃計算用路線図にある線をむりやり通す、のでしょうか? ちょっと規則が気になります。
具体的な制約式ですが、まさか手で書くとか面倒すぎるしミスも混入しやすいので、 営業キロデータと乗換データを与えて制約式を出力するプログラムを書きました。 相変わらずRubyスクリプトです。葛西隆也氏によるLOP toolkitが非常に参考になりました。 名前もなんとなく似せて「最長大回り経路」=「Longest Detour Route」ということでLDR toolkitと呼んでいます。
ダウンロードはここから(18.9KB, Zip圧縮, 2010/2/11更新)。一切無保証・改造自由・再頒布自由のフリーソフトウェアとしてどうぞ。 Ruby, GLPKを別途インストールがすることが必須です。 自分は両方ともWindows向けバイナリ (Ruby 1.8.6、GLPK 4.34)を使っています。
┌─路線データテキスト │ ↓ │ [modmaker.rb] │ ↓ │ 整数計画法モデルファイル←─┐ │ ↓ │ │ [glpsol.exe] [手動(コピペ)で制約式追加] │ ↓ │ │ ソルバー出力ファイル │ ↓ ↓ │ [resultparser.rb] │ ↓ │ 結果表示─────────────┘
主にこんな感じの設計です。この他にedgeviewer.rb, sourcedata.rbがあります。 edgeviewer.rbはすべての枝のID(Exxx)とその路線・区間を表示するだけのツールです。 sourcedata.rbは路線データテキストのパーサで、modmaker.rb、resultparser.rb、edgeviewer.rbが内部的に用いています。 使用するコマンドはこのぐらいだと思います。
ruby modmaker.rb metro_data.txt 1 glpsol -m metro_data_ltype.mod -o metro_ltype_out.txt ruby resultparser.rb metro_data.txt metro_ltype_out.txt 1 ruby edgeviewer.rb metro_data.txt 1
なんとなくわかってください。ただし、1と3箇所あるところがよくわからないと思います。これは経路タイプ指定の数字で、
となっています。 発着駅指定最長経路モードは、主にSuica/PASMOで乗降車駅の会社以外を乗るときを想定して作成していますが、 他にも例えば自分の最寄り駅〜その隣駅までの最長大回り経路探索にも使えます。 路線データテキストのフォーマットはこんな感じです。
[路線ID] 駅名 営業キロ 駅ID(省略可) … [路線ID] 駅名 営業キロ 駅ID(省略可) … <ラッチ外> 接続ID 駅ID 駅ID … … <中間改札> 接続ID 駅ID 駅ID … … <ラッチ外接続他駅> 駅ID 駅ID … … <外部> 駅ID … {券面最長距離} キロ数
路線名、駅名、駅ID、接続IDにはタブ、改行、[]<>{}以外の任意の文字列が使えます。 注意点として、IDと名のつくものは同一文字列は同じものとして扱われます。 路線IDはすべて重複してはいけません(重複するとどっちかが無視されます)。 ラッチ外接続他駅の接続IDも内部的に路線IDと同一視されることがあるので、重複を避けてください。 駅IDについては、同一の駅IDを持つものは無条件に乗換可、 特殊条件で乗換可になるものは<ラッチ外>、<中間改札>、<ラッチ外接続他駅>に記述してください。 <外部>は発着駅指定最長経路モードでの発着駅になりうる駅IDを指定します。 ここに3つ以上指定した場合、発着駅の全組合せを網羅するnC2個のファイルを作成します。 {券面最長距離}はL型,O型最長経路モードでのみ利用します。利用するきっぷ等で乗車可能な最長距離の数字を書いてください。
サンプルデータも添付しているのでそれらしく作ってください。(2010/2/11追記:JR部のデータ誤りを修正しました) 乗換条件がこれじゃよくわからん!って人のために、厳密な定義を書いておきます。
(2009/9/5追記)当方の規則の誤認によるバグが発見されました。A駅とB駅がラッチ外乗換可であり、 C駅からの距離がA駅は券面距離を超えている、B駅は券面距離を超えていない、という場合に 今まではC→B→Aという経路は可、C→A→Bという経路は不可としていたのですが、 ラッチ外他駅乗換の存在する東京メトロ・都営・大阪市3社局ともにC→Aの運賃はC→Bと同一であり、C→A→Bを可能としているので修正しました。 これにより、ラッチ外乗換の絡む本稿の最長経路がかなり変化しています。
2009年3月13日までの130円での最長ルートはわらしべ長者町氏により提示され、 近藤英明氏により最長であることが証明されています。 3月14日から近郊区間が拡大し、松岸や安房鴨川までもが近郊区間に入りました。 今まで我孫子〜成田〜佐倉〜成東〜大網〜蘇我〜千葉と通っていた最長経路が、 我孫子〜成田〜松岸〜成東〜大網〜安房鴨川〜蘇我〜千葉と変化するだけと言われていましたが、どうでしょうか。
L型、O型両方についての最長は次の表の通りになりました。最長経路は予想通りにはなりませんでした。 (※コメント欄でより長いルートが報告され、JR部のデータ作成ミスが見つかったことで予想通りでなかったことが証明されました)
L型最長 北小金〜馬橋 1039.2km | |||
---|---|---|---|
常磐線 | 北小金 | 友部 | 76.8 |
水戸線 | 友部 | 小山 | 50.2 |
両毛線 | 小山 | 新前橋 | 84.4 |
上越線 | 新前橋 | 高崎 | 7.3 |
高崎線 | 高崎 | 大宮 | 74.7 |
川越線 | 大宮 | 高麗川 | 30.6 |
八高線 | 高麗川 | 八王子 | 31.1 |
横浜線 | 八王子 | 橋本 | 8.8 |
相模線 | 橋本 | 茅ヶ崎 | 33.3 |
東海道線 | 茅ヶ崎 | 大船 | 12.1 |
根岸線 | 大船 | 横浜 | 22.1 |
横須賀線 | 横浜 | 品川 | 24.9 |
京浜東北線 | 品川 | 川崎 | 11.4 |
南武線 | 川崎 | 立川 | 35.5 |
中央線 | 立川 | 西国分寺 | 4.7 |
武蔵野線 | 西国分寺 | 武蔵浦和 | 25.9 |
埼京線 | 武蔵浦和 | 赤羽 | 10.6 |
京浜東北線 | 赤羽 | 南浦和 | 9.3 |
武蔵野線 | 南浦和 | 西船橋 | 40.1 |
総武線 | 西船橋 | 佐倉 | 34.7 |
成田線 | 佐倉 | 松岸 | 75.4 |
総武線 | 松岸 | 成東 | 40.4 |
東金線 | 成東 | 大網 | 13.8 |
外房線 | 大網 | 安房鴨川 | 70.4 |
内房線 | 安房鴨川 | 蘇我 | 119.4 |
京葉線 | 蘇我 | 東京 | 43 |
総武線 | 東京 | 錦糸町 | 4.8 |
総武緩行線 | 錦糸町 | 秋葉原 | 3.4 |
京浜東北線 | 秋葉原 | 神田 | 0.7 |
中央線 | 神田 | 新宿 | 9 |
山手線 | 新宿 | 日暮里 | 11.3 |
常磐線 | 日暮里 | 馬橋 | 19.1 |
O型最長 秋葉原〜秋葉原 1014.6km | |||
---|---|---|---|
総武緩行線 | 秋葉原 | 錦糸町 | 3.4 |
総武線 | 錦糸町 | 佐倉 | 50.5 |
成田線 | 佐倉 | 松岸 | 75.4 |
総武線 | 松岸 | 成東 | 40.4 |
東金線 | 成東 | 大網 | 13.8 |
外房線 | 大網 | 安房鴨川 | 70.4 |
内房線 | 安房鴨川 | 蘇我 | 119.4 |
京葉線 | 蘇我 | 東京 | 43 |
京浜東北線 | 東京 | 神田 | 1.3 |
中央線 | 神田 | 代々木 | 8.3 |
山手線 | 代々木 | 品川 | 9.9 |
東海道線 | 品川 | 川崎 | 11.4 |
南武線 | 川崎 | 尻手 | 1.7 |
南武支線 | 尻手 | 浜川崎 | 4.1 |
鶴見線 | 浜川崎 | 鶴見 | 5.7 |
京浜東北線 | 鶴見 | 横浜 | 7.1 |
根岸線 | 横浜 | 大船 | 22.1 |
東海道線 | 大船 | 茅ヶ崎 | 12.1 |
相模線 | 茅ヶ崎 | 橋本 | 33.3 |
横浜線 | 橋本 | 八王子 | 8.8 |
中央線 | 八王子 | 立川 | 9.9 |
青梅線 | 立川 | 拝島 | 6.9 |
八高線 | 拝島 | 高麗川 | 21.2 |
川越線 | 高麗川 | 大宮 | 30.6 |
高崎線 | 大宮 | 高崎 | 74.7 |
上越線 | 高崎 | 新前橋 | 7.3 |
両毛線 | 新前橋 | 小山 | 84.4 |
水戸線 | 小山 | 友部 | 50.2 |
常磐線 | 友部 | 新松戸 | 78.1 |
武蔵野線 | 新松戸 | 南浦和 | 25.8 |
京浜東北線 | 南浦和 | 赤羽 | 9.3 |
埼京線 | 赤羽 | 武蔵浦和 | 10.6 |
武蔵野線 | 武蔵浦和 | 西国分寺 | 25.9 |
中央線 | 西国分寺 | 新宿 | 22.5 |
山手線 | 新宿 | 秋葉原 | 15.1 |
O型は神田〜神田でも構いません。
ちなみに、発着駅の制限がかなり効き、L型でも投入した駅数106、区間数133、変数数合計281におさえることができました。 GLPKで解く時間も、1回を解くのに概ね3分程度、孤立ループが出現し禁止すること5回、禁止制約計10個ぐらいでした。 当然O型はもっと楽です。
また、データ作成誤りが見つかったきっかけでもある、 よねざわいずみさんによるO型の最長解を読んで気づいたのですが、 特例による折り返し乗車分も乗車距離に含むという計算方法もあります。 何を基準にするかという考えの違いですので、この考え方によるL型も計算したいところです。 今はとりあえず次の課題というところで。
これも近藤英明氏により証明されていますが、副都心線開業前のものです。 副都心線開業でどう変化したか調べてみましょう。
前述のラッチ外乗換他駅のバグのおかげで最長を見逃していました。 この点を修正して、 結果は以下の通りです。L型が最長になりました。
L型最長 本郷三丁目→西ケ原 63.6km | |||
---|---|---|---|
丸ノ内線 | 本郷三丁目 | 淡路町 | 1.6 |
乗継 | 淡路町 | 新御茶ノ水 | 0 |
千代田線 | 新御茶ノ水 | 北千住 | 8.6 |
日比谷線 | 北千住 | 仲御徒町 | 5.8 |
乗継 | 仲御徒町 | 上野広小路 | 0 |
銀座線 | 上野広小路 | 日本橋 | 3 |
東西線 | 日本橋 | 茅場町 | 0.5 |
日比谷線 | 茅場町 | 銀座 | 2.5 |
銀座線 | 銀座 | 青山一丁目 | 4.5 |
半蔵門線 | 青山一丁目 | 大手町 | 6.1 |
千代田線 | 大手町 | 日比谷 | 1.4 |
日比谷線 | 日比谷 | 霞ケ関 | 1.2 |
千代田線 | 霞ケ関 | 表参道 | 4.1 |
半蔵門線 | 表参道 | 渋谷 | 1.3 |
副都心線 | 渋谷 | 新宿三丁目 | 3.6 |
丸ノ内線 | 新宿三丁目 | 四ツ谷 | 2.6 |
南北線 | 四ツ谷 | 市ケ谷 | 1 |
有楽町線 | 市ケ谷 | 池袋 | 6 |
丸ノ内線 | 池袋 | 後楽園 | 4.8 |
南北線 | 後楽園 | 西ケ原 | 5 |
O型最長 神保町〜神保町 59.4km | |||
---|---|---|---|
半蔵門線 | 神保町 | 青山一丁目 | 4.4 |
銀座線 | 青山一丁目 | 銀座 | 4.5 |
日比谷線 | 銀座 | 茅場町 | 2.5 |
東西線 | 茅場町 | 日本橋 | 0.5 |
銀座線 | 日本橋 | 上野 | 3.5 |
日比谷線 | 上野 | 北千住 | 5.3 |
千代田線 | 北千住 | 新御茶ノ水 | 8.6 |
乗継 | 新御茶ノ水 | 淡路町 | 0 |
丸ノ内線 | 淡路町 | 池袋 | 7.2 |
有楽町線 | 池袋 | 市ケ谷 | 6 |
南北線 | 市ケ谷 | 四ツ谷 | 1 |
丸ノ内線 | 四ツ谷 | 新宿三丁目 | 2.6 |
副都心線 | 新宿三丁目 | 渋谷 | 3.6 |
半蔵門線 | 渋谷 | 表参道 | 1.3 |
千代田線 | 表参道 | 霞ケ関 | 4.1 |
日比谷線 | 霞ケ関 | 日比谷 | 1.2 |
千代田線 | 日比谷 | 大手町 | 1.4 |
半蔵門線 | 大手町 | 神保町 | 1.7 |
L型の市ヶ谷〜飯田橋は有楽町線でも南北線でも構いません。O型も九段下発着でも同じです。
最長は、銀座→表参道→霞ヶ関→日比谷→大手町→永田町→市ヶ谷と辿っていたのが、 副都心線開業により、銀座→青山一丁目→大手町→日比谷→霞ヶ関→表参道→渋谷→新宿三丁目→四ツ谷→市ヶ谷となり、 皇居をコの字に行って戻るルートが皇居を2週するルートに変わりました。
ちなみに、O型ですが、どうやらメトロにはO型の乗車形式はないそうです。 ということであくまでもC型を否定するための参考資料ですね。この通り乗らないでください。
メトロは路線の形状的に、発着駅の絞り込みがあまりできない構造をしています。 おかげで、L型の場合、駅数119、区間数149、合計変数数387とJR近郊区間よりも手間そうな数字が出てきました。 ところが、意外と一発で1分ぐらいで解けてびっくりしました。
以前芝公園〜五反田/宝町→赤羽橋の36.1kmと書いていましたが、プログラムのバグ修正でさらに長いものが見つかりました。
L型最長 新橋→汐留 41.3km | |||
---|---|---|---|
浅草線 | 新橋 | 東日本橋 | 4 |
乗継 | 東日本橋 | 馬喰横山 | 0 |
新宿線 | 馬喰横山 | 神保町 | 2.5 |
三田線 | 神保町 | 三田 | 5.6 |
浅草線 | 三田 | 大門 | 1.5 |
大江戸線 | 大門 | 都庁前 | 8.6 |
大江戸線 | 都庁前 | 汐留 | 19.1 |
O型最長 森下〜森下 33.9km | |||
---|---|---|---|
大江戸線 | 森下 | 大門 | 7.3 |
浅草線 | 大門 | 東日本橋 | 5 |
乗継 | 東日本橋 | 馬喰横山 | 0 |
新宿線 | 馬喰横山 | 新宿 | 8.1 |
大江戸線 | 新宿 | 都庁前 | 0.8 |
大江戸線 | 都庁前 | 森下 | 12.7 |
O型は、森下を発着にしてみましたが、 それ以外でも東日本橋〜馬喰横山を170円で超えられるところならどこでもいいです(26駅もあります)。 下記コメント欄で情報提供いただきましたが、都営地下鉄はO型乗車可能なようです。
L型は、駅数64、区間数68、変数196と、あまり絞れた気がしませんでしたが、1回10秒程度で、十分早いと思います。
分量が多くなってきたので、別ページに分けました。こちらからどうぞ→Suica/PASMO初乗り最長大回り経路
以下、初稿時後に追加された、調子に乗っていろいろ調べてみた編です。
大阪の最長経路は、2ch大阪近郊区間大回りスレのテンプレに入っているものが最新ですが、実際その通りになりました。 券面距離の制限をなくしても最長距離にわかりやすい上限があるのが大阪近郊区間の特徴のようです。
ついでに、券面距離を長くしていくとどう変化するのかを見ることにしました。 なお、都合上加古川まで東海道本線扱いしています。
3km以内最長 天満〜福島 563.7km | |||
---|---|---|---|
大阪環状線 | 天満 | 京橋 | 2.6 |
JR東西線 | 京橋 | 尼崎 | 12.5 |
東海道本線 | 尼崎 | 山科 | 56 |
湖西線 | 山科 | 近江塩津 | 74.1 |
北陸本線 | 近江塩津 | 米原 | 31.4 |
東海道本線 | 米原 | 草津 | 45.5 |
草津線 | 草津 | 柘植 | 36.7 |
関西本線 | 柘植 | 木津 | 47 |
片町線 | 木津 | 放出 | 41.6 |
おおさか東線 | 放出 | 久宝寺 | 9.2 |
関西本線 | 久宝寺 | 奈良 | 30.4 |
桜井線 | 奈良 | 高田 | 29.4 |
和歌山線 | 高田 | 和歌山 | 76 |
阪和線 | 和歌山 | 天王寺 | 61.3 |
大阪環状線 | 天王寺 | 福島 | 10 |
6km以内最長 塚口〜加島 738.9km | |||
---|---|---|---|
福知山線 | 塚口 | 谷川 | 70.5 |
加古川線 | 谷川 | 加古川 | 48.5 |
東海道本線 | 加古川 | 山科 | 120.5 |
湖西線 | 山科 | 近江塩津 | 74.1 |
北陸本線 | 近江塩津 | 米原 | 31.4 |
東海道本線 | 米原 | 草津 | 45.5 |
草津線 | 草津 | 柘植 | 36.7 |
関西本線 | 柘植 | 木津 | 47 |
片町線 | 木津 | 放出 | 41.6 |
おおさか東線 | 放出 | 久宝寺 | 9.2 |
関西本線 | 久宝寺 | 奈良 | 30.4 |
桜井線 | 奈良 | 高田 | 29.4 |
和歌山線 | 高田 | 和歌山 | 76 |
阪和線 | 和歌山 | 天王寺 | 61.3 |
大阪環状線 | 天王寺 | 京橋 | 6.5 |
JR東西線 | 京橋 | 加島 | 10.3 |
15km以内最長 塚口〜福島 741.1km | |||
---|---|---|---|
福知山線 | 塚口 | 谷川 | 70.5 |
加古川線 | 谷川 | 加古川 | 48.5 |
東海道本線 | 加古川 | 尼崎 | 64.5 |
JR東西線 | 尼崎 | 京橋 | 12.5 |
大阪環状線 | 京橋 | 大阪 | 4.2 |
東海道本線 | 大阪 | 山科 | 48.3 |
湖西線 | 山科 | 近江塩津 | 74.1 |
北陸本線 | 近江塩津 | 米原 | 31.4 |
東海道本線 | 米原 | 草津 | 45.5 |
草津線 | 草津 | 柘植 | 36.7 |
関西本線 | 柘植 | 木津 | 47 |
片町線 | 木津 | 放出 | 41.6 |
おおさか東線 | 放出 | 久宝寺 | 9.2 |
関西本線 | 久宝寺 | 奈良 | 30.4 |
桜井線 | 奈良 | 高田 | 29.4 |
和歌山線 | 高田 | 和歌山 | 76 |
阪和線 | 和歌山 | 天王寺 | 61.3 |
大阪環状線 | 天王寺 | 福島 | 10 |
25km以内最長 塚口〜JR難波 743.5km | |||
---|---|---|---|
福知山線 | 塚口 | 谷川 | 70.5 |
加古川線 | 谷川 | 加古川 | 48.5 |
東海道本線 | 加古川 | 尼崎 | 64.5 |
JR東西線 | 尼崎 | 京橋 | 12.5 |
大阪環状線 | 京橋 | 天王寺 | 6.5 |
阪和線 | 天王寺 | 和歌山 | 61.3 |
和歌山線 | 和歌山 | 高田 | 76 |
桜井線 | 高田 | 奈良 | 29.4 |
関西本線 | 奈良 | 久宝寺 | 30.4 |
おおさか東線 | 久宝寺 | 放出 | 9.2 |
片町線 | 放出 | 木津 | 41.6 |
関西本線 | 木津 | 柘植 | 47 |
草津線 | 柘植 | 草津 | 36.7 |
東海道本線 | 草津 | 米原 | 45.5 |
北陸本線 | 米原 | 近江塩津 | 31.4 |
湖西線 | 近江塩津 | 山科 | 74.1 |
東海道本線 | 山科 | 大阪 | 48.3 |
大阪環状線 | 大阪 | 今宮 | 8.8 |
関西本線 | 今宮 | JR難波 | 1.3 |
大阪と同じように距離を変えて試してみたんですが、 よく考えたら福岡は概ね「目」の字+αという構造なので、「目」の外周のどこを切断して伸ばすと有利か、というだけの話でした。
3km以内最長 原町〜門松 169.9km | |||
---|---|---|---|
篠栗線 | 原町 | 博多 | 6.8 |
鹿児島本線 | 博多 | 原田 | 19.7 |
筑豊本線 | 原田 | 新飯塚 | 28.5 |
後藤寺線 | 新飯塚 | 田川後藤寺 | 13.3 |
日田彦山線 | 田川後藤寺 | 城野 | 30 |
日豊本線 | 城野 | 西小倉 | 5.3 |
鹿児島本線 | 西小倉 | 香椎 | 58 |
香椎線 | 香椎 | 長者原 | 6.3 |
篠栗線 | 長者原 | 門松 | 2 |
終点は6kmでは新原、10kmでは城戸南蔵院前、15kmでは九郎原、20kmでは筑前大分と伸びていくだけでした。 篠栗線はさすがにこれ以上になると無理で、25kmになると飯塚〜中間に移りました。
大阪市営地下鉄の距離には、営業キロと実キロの2種類があり、両方が公開されているので両方で計算してみました。 (実キロでの計算方法をちょっと考えましたが、制約式は営業キロのもの、目的関数は実キロのものを使って算出すればいいはずです。)
上記のプログラムの他駅乗り継ぎについてのバグ修正により、これも新たな最長が見つかりました。
営業キロ最長1・実キロ最長 東梅田〜西中島南方 営業キロ64.6km/実キロ65.1km | ||||
---|---|---|---|---|
谷町線 | 東梅田 | 太子橋今市 | 7.3 | 7.3 |
今里筋線 | 太子橋今市 | 今里 | 8.2 | 8.2 |
千日前線 | 今里 | 谷町九丁目 | 2.6 | 2.6 |
谷町線 | 谷町九丁目 | 天王寺 | 1.7 | 2.1 |
御堂筋線 | 天王寺 | 動物園前 | 1 | 1 |
堺筋線 | 動物園前 | 日本橋 | 1.7 | 2.1 |
千日前線 | 日本橋 | 難波 | 0.7 | 0.7 |
四つ橋線 | 難波 | 住之江公園 | 7.7 | 7.7 |
南港ポートタウン線 | 住之江公園 | コスモスクエア | 7.9 | 7.9 |
中央線 | コスモスクエア | 阿波座 | 8.3 | 8.3 |
千日前線 | 阿波座 | 西長堀 | 1 | 0.9 |
長堀鶴見緑地線 | 西長堀 | 森ノ宮 | 5.1 | 5.1 |
中央線 | 森ノ宮 | 谷町四丁目 | 1.3 | 1.3 |
谷町線 | 谷町四丁目 | 南森町 | 2.7 | 2.3 |
堺筋線 | 南森町 | 堺筋本町 | 1.7 | 1.9 |
中央線 | 堺筋本町 | 本町 | 0.7 | 0.7 |
御堂筋線 | 本町 | 西中島南方 | 5 | 5 |
営業キロ最長2 西中島南方〜西梅田 営業キロ64.6km | |||
---|---|---|---|
御堂筋線 | 西中島南方 | 梅田 | 2.8 |
徒歩 | 梅田 | 東梅田 | 0 |
谷町線 | 東梅田 | 太子橋今市 | 7.3 |
今里筋線 | 太子橋今市 | 今里 | 8.2 |
千日前線 | 今里 | 谷町九丁目 | 2.6 |
谷町線 | 谷町九丁目 | 天王寺 | 1.7 |
御堂筋線 | 天王寺 | 動物園前 | 1 |
堺筋線 | 動物園前 | 日本橋 | 1.7 |
千日前線 | 日本橋 | 難波 | 0.7 |
四つ橋線 | 難波 | 住之江公園 | 7.7 |
南港ポートタウン線 | 住之江公園 | コスモスクエア | 7.9 |
中央線 | コスモスクエア | 阿波座 | 8.3 |
千日前線 | 阿波座 | 西長堀 | 1 |
長堀鶴見緑地線 | 西長堀 | 森ノ宮 | 5.1 |
中央線 | 森ノ宮 | 谷町四丁目 | 1.3 |
谷町線 | 谷町四丁目 | 南森町 | 2.7 |
堺筋線 | 南森町 | 堺筋本町 | 1.7 |
中央線 | 堺筋本町 | 本町 | 0.7 |
四つ橋線 | 本町 | 西梅田 | 2.2 |
難波〜住之江公園 他候補(営業キロ/実キロ) | ||||
---|---|---|---|---|
御堂筋線 | 難波 | 大国町 | 1.2 | 1.2 |
四つ橋線 | 大国町 | 住之江公園 | 6.5 | 6.5 |