Mobile Factory Tech Blog

技術好きな方へ！モバイルファクトリーのエンジニアたちが楽しい技術話をお届けします！

Graphillionで東京メトロの最長経路問題を考える【追記あり】

こんにちは！ モバイルファクトリー Advent Calendar 2018 - Qiita 20日目担当の id:Ruby_on_JRs こと id:pikkaman です。この10月にモバイルファクトリーに新卒で入社し、エンジニアとして働いています。

はじめに

唐突ですが、私は入社直前の夏、全国のJR線で一筆書きをしたとき最も営業キロが長くなるルートで旅行する、いわゆる「JR線最長片道切符の旅」を自前のアルゴリズムで計算し、実際にそのルートで1ヶ月半かけて旅した後にそのまま入社していまして( Ruby on Japan Railways @最長片道切符(@Ruby_on_JRs) - Twilog )、全国4000の駅の思い出を集めながら日々全国の駅と路線の構造に想いをはせていました。

せっかくモバファクのアドベントカレンダーに参加することになりましたので、また別の路線図の最長経路問題について書くことに決めた次第です。

気付くと開いていた東京メトロのサイトの運送約款に関するページ 運送約款 | PASMO・定期・乗車券 | 東京メトロ に掲載されている、きっぷのルール等を定めた旅客営業規程を読んでみると以下の記述を見つけられます。

第45条 第43条の規定にかかわらず、次の区間内各駅発着の場合、又は同区間を通過する場合の片道普通旅客運賃は、最も短い経路のキロ程によって計算する。

第82条 第45条に掲げる区間内各駅間相互発着又は通過となる普通乗車券又は回数乗車券を所持する旅客は、その区間内においてはその乗車券の運賃計算経路にかかわらず、う回して乗車することができる。

つまり、特定の条件を満たすとき出発駅と到着駅から決まる運賃を払えば、途中どんな経路を通ってもよい ということです。世界有数の複雑な路線を持つ東京メトロであれば、きっと思いもよらない長い迂回路を取ることができるだろうと期待できます。この最長経路を考えてみることにしました。

この記事では以下の条件を満たすような経路をコンピュータを駆使して求めることを目標にします。

  1. 出発駅から到着駅までの経路の営業キロの和が最長となるような迂回経路を求める。
  2. 運賃は東京メトロの片道乗車券の上限である310円までとし、初乗り運賃にこだわることはしない。
  3. 出発駅の改札を通った後は、到着駅まで改札を出ることはない。
  4. 既に通過した駅にもう一度訪れてゴールとする経路は考えない。

条件2、3、4を変えることでさらに面白い問題にすることが可能ですが、今回は簡単のため単純な条件を採用しました。

注：読者から条件4が不足していることを指摘していただきました。ありがとうございます。

グラフ問題ライブラリGraphillionの導入

Graphillionとは

最長片道経路の探索にはPythonライブラリのGraphillion(Home · takemaru/graphillion Wiki · GitHub)を採用しました。GraphillionはPythonとC++を組み合わせて作られた高速にグラフ問題を解くためのライブラリです。具体的なアルゴリズムは割愛しますが（これも面白いのでまたの機会に！）、ライブラリの威力は次の動画でで実感できるでしょう。

youtu.be youtu.be

元々私はC#で実装した自前の最長経路探索アルゴリズムを使っていたのですが、この記事を書くに当たってそれより数十倍高速なGraphillionを知ってしまい、思わず乗り換えることになりました。これがあればJR線最長片道切符の旅の経路計算で度重なる領域分割に苦労することもなかったでしょう。 おまけに、早口で言うと「グラフ理論」に聞こえるところもおしゃれで好きです。

インストールとサンプルの実行

Grapillionのインストールはpipで簡単に行うことができます。また、Python2, Python3の両方に対応しています。（ただし日本語の情報はほとんどがPython 2であることに気をつけてください。英語ではwiki等もPython 3にアップデートされています）

公式GitHubリポジトリのwikiに記載されているJR山手線・中央線を単純にしたグラフ問題で (Example codes · takemaru/graphillion Wiki · GitHub)、実際のGraphillionの使い方を見ていきます。なお、説明のため問題と解答を一部改変しています。

ごく一部の例外を除いて、旅客営業を行う日本の鉄道路線では駅間を双方向に列車が行き来しています。そのため駅をノード、路線をエッジとする無向グラフとして路線図を見ることが可能になります。 さらに、最長片道経路問題を解くにあたっては各駅間の営業キロが必要になるので、営業キロを重みとする重み付き無向グラフを採用します。

   +--(11.3)------------------------- 上野
   |                                   |
   |                                 (3.6)
   |                                   |
  新宿 ---(3.7)--- 四ツ谷 ---(6.6)---- 東京
   |                                   |
   |                                 (6.8)
   |                                   |
   +--(10.6)------------------------- 品川

括弧内の数字が駅間距離を表しています。 この路線図に対して以下の問題を解きます。

  1. 東京から品川までの経路は何通りでしょう？
  2. 東京から品川までの最長経路はなんでしょう？
  3. 四ツ谷を経由して東京から品川まで至る経路には何があるでしょう？

これらの問題はGraphillionを利用することで簡単に解くことができます。 まず、エッジを (出発駅, 到着駅, 駅間距離（重み）) の形のタプルで表し、リストに格納します。 そのリストを用いてset_universe()でグラフを生成すれば準備完了です。

from graphillion import GraphSet as gs

universe = [('東京'   , '品川'     , 6.8),
            ('品川'   , '新宿'     , 10.6),
            ('新宿'   , '上野'     , 11.3),
            ('上野'   , '東京'     , 3.6),
            ('東京'   , '四ツ谷'   , 6.6),
            ('四ツ谷' , '新宿'     , 3.7)]
gs.set_universe(universe)

まずは東京から品川までの経路を列挙したグラフセット（条件を満たすグラフの集合）を生成します。

paths = gs.paths('東京', '品川')

これだけで東京から品川までのすべての経路が分かりました。第1問はpathsのlenを取れば求められます。

print(len(paths))

続いて、全経路pathsからmax_iter()を呼び出すことで重みの降順でソートされた経路を取り出すことが可能になります。よって第2問はその最初の経路を取ればよいことになります。

print(next(paths.max_iter()))

最後に、あるノードを通過するような経路をincluding()によって抽出することができます。第3問はこれを使って四ツ谷を通るようなグラフセットのみを得ることができます。

print(paths.including('四ツ谷'))

グラフセットの選択により複雑な条件を課すことで、グラフで表現できる様々な問題に対処できます。

Graphillionを使って最長片道経路を求める

前処理

ここからは本題の東京メトロの路線図で最長経路問題を解いていきます。

まずはGrapillionに路線データを読み込ませてグラフにします。 残念ながら駅間距離を取得するAPIを見つけることができなかったので、各種資料にあたって調べたものを手動でCSVにまとめます。

from to dist line
中目黒 恵比寿 10 日比谷線
恵比寿 広尾 15 日比谷線
広尾 六本木 17 日比谷線
六本木 神谷町 15 日比谷線
… … … …

これを2次元データの解析に便利なライブラリpandasを用いて読み込み（今回はCSVを読んでいるだけですが）、すべてのグラフの元になるユニバースを生成します。 なお、上のJR線の例とは違って、後に最長経路の距離を求めるために、タプルで表したエッジをキーとするディクショナリとして重みweightsを持っています。

import pandas as pd

df_list = pd.read_csv('./list.csv', sep=',')
univ = []
weights = {}

for i, v in df_list.iterrows():
    edge = (v['from'], v['to'])
    univ.append(edge)
    weights[edge] = v['dist']

gs.set_universe(univ)

例えば東京から池袋までの最長経路を求め、その距離を求めるには以下のように書けばよいです。

paths = gs.paths('東京', '池袋')
max_path = next(paths.max_iter(weights))
distance = 0
for edge in max_path:
    distance += weights[edge]
print(distance)

あとは出発駅と到着駅について考えられるすべてのパターンを試し、2駅の最長の経路が最も長かったものが求める最長片道経路です。

駅名が異なるが乗り換え可能な場合の扱い

ここからは単純に路線を読み込むだけでは処理できないケースについて見ていきます。 まず、東京メトロでは赤坂見附駅と永田町駅のように、駅名が異なる場合でも改札を出ることなく乗り換えが可能な駅が存在します。 Graphillionでユニバースを生成する際には駅名が同じであれば同一のノードとしてみなされますが、駅名が異なる場合は乗り換え可能であるにも関わらずエッジでつながらないことになります。

そこで、これらの駅は駅間営業キロ0kmの線路でつながっているとみなし、重み0のエッジとして実装しました。

from to dist line
赤坂見附 永田町 0 乗り換え
溜池山王 国会議事堂前 0 乗り換え
… … … …

ある組の駅の間に2路線存在する場合の扱い

さらに東京メトロでは2路線が並行している区間がいくつかあります。有楽町線と副都心線は小竹向原以北において線路を共有していますし、細かいところでは霞ヶ関-日比谷などが該当します。

Graphillionはあるノードの組に対しては1つのエッジでしかつなぐことができません。そこで、該当する駅はノード名を（路線名）駅名とし、別々のノードとした上で「駅名が異なるが乗り換え可能な駅の扱い」と同様に重み0のエッジでつなぎました。

from to dist line
（銀座）渋谷 （銀座）表参道 13 銀座線
（銀座）表参道 外苑前 7 銀座線
… … … …
（半蔵門）渋谷 （半蔵門）表参道 13 半蔵門線
（半蔵門）表参道 青山一丁目 14 半蔵門線
… … … …
（銀座）表参道 （半蔵門）表参道 0 乗り換え

注：当初渋谷にて銀座線と半蔵門線の改札内乗り換えが可能としていましたが、誤りのため訂正いたします。それに伴って上の例を表参道に変更しました。なお、副都心線と半蔵門線は改札内で乗り換えが可能です。

改札外乗り換えになる場合の扱い

東京メトロでの最長経路問題を複雑にしているのが改札外での乗り換えです。池袋駅や大手町駅には、乗り換えのために一度改札外に出るためのオレンジ色の改札があります。それに関して旅客営業規程では以下の条件を定めています。

第83条 前条第1項の規定にかかわらず、次に掲げる乗換駅においては、括弧内の路線相互について乗車する発着駅間の普通旅客運賃と比較して、発駅又は着駅から当該乗換駅までの運賃が高額となる場合は、別表第2号表に掲げる運賃による当該乗換駅での乗換えはできない

つまり、すぐ近くまでの切符を買って、オレンジ色の改札がある遠くの駅で改札を出てしまうことはできない ということです。この規定は特に初乗り運賃での最長経路を求めようとするタイプの問題において重要になります。

このような改札外での乗り換えが必要な駅は東京メトロのサイトで案内されている以下の13駅です。(https://ssl.tokyometro.jp/support/faq_answer?lang=ja&faqno=OpenFAQ-000204) ただし、旅客営業規程第83条 第3項にもあるように、実際は大手町と新宿三丁目は改札内で乗り換えが可能です。

  • 上野駅（銀座線と日比谷線）
  • 三越前駅（銀座線と半蔵門線）
  • 上野広小路駅‐仲御徒町駅（銀座線と日比谷線）
  • 大手町駅（丸ノ内線と東西線・千代田線・半蔵門線／東西線と丸ノ内線・千代田線・半蔵門線／千代田線と丸ノ内線・東西線・半蔵門線／半蔵門線と丸ノ内線・東西線・千代田線）
  • 池袋駅（丸ノ内線・副都心線と有楽町線）
  • 飯田橋駅（東西線と有楽町線・南北線）
  • 九段下駅（東西線と半蔵門線）
  • 日比谷駅‐有楽町駅（日比谷線・千代田線と有楽町線）
  • 淡路町駅‐新御茶ノ水駅（丸ノ内線と千代田線）
  • 渋谷駅（銀座線と副都心線）
  • 新宿三丁目駅（丸ノ内線と副都心線）
  • 人形町駅‐水天宮前駅（日比谷線と半蔵門線）
  • 築地駅‐新富町駅（日比谷線と有楽町線）

今回はオレンジ色の改札を通らなければならない乗り換え方法については認めないというルールにしたので、「ある組の駅の間に2路線存在する場合」「ある組の駅の間に2路線存在する場合」から、該当する乗り換え表現エッジを削除しました。

2回同じ駅を通る場合を除く

最後に2回同じ駅を通ってしまう場合を排除します。「ある駅の組の間に2路線存在する場合」においてノードの重複を避けるために路線名を頭につけた駅名を採用しましたが、このままでは同じ駅を別の路線で2回通ることが可能になってしまいます。 そこで、先に求めた経路から同じ駅を2回通る場合を引いて、残った経路の集合から最長片道経路を求めます。

例えば、有楽町線の千川と副都心線の千川をどちらも通る場合を考えます。それぞれはincludingを指定することで抽出できるため、それらの積を全体から引けばよいことが分かります。

senkawa = paths.including('（有楽町）千川').including('（副都心）千川')
paths -= senkawa

この操作を該当する他の駅に対しても実行することで、2回同じ駅を通過する経路を除くことができます。ただし、「ある組の駅の間に2路線存在する場合」のように（路線名）駅名の形でノードを作った駅で乗り換えられるように、(（路線名A）駅名, （路線名B）駅名)の形のエッジが経路に含まれる場合を除いておく必要があります。

注：当初記載されていた情報では方法の説明が不十分であったため、但し書きを追加しました。

これが東京メトロ改札内最長片道経路だ！

和光市から西船橋まで78.8kmの経路です。都内南西でトリッキーな動きをするのが面白いですね。

注：更新に伴って求めた経路を路線ごとに色分けしました。

まとめ

今回はグラフ検索ライブラリGraphillionを用いて、東京メトロの改札内乗り換え最長片道経路を計算してみました。ただし、旅客営業規定の解釈とアルゴリズムの正確性について100%の自信があるわけではございませんので、実際にこの経路で旅行される際は自己責任でお願いいたします。ちなみに、私なら自分が間違っているのが怖いので必ず1日乗車券を買って行きます。

もちろん、このような限界に挑むような経路の他にも、「旅行に行くけど目的地をどうやったら効率よく回れるかな」といったカジュアルな問題にもGraphillionは適用することができます。非力なラップトップでも数秒〜数分で経路を出せる素晴らしいライブラリですので、これからはGraphillionとも一緒に旅行するのはいかがでしょうか？

次は卒業生の @lycoris102 さんです。よろしくお願いします！