「３・３・SUNデジタルフリーきっぷ」は近鉄・南海・名鉄（一部区間を除く）が連続2日間または3日間乗り放題のデジタルフリーきっぷです。
2006年まで、近鉄・南海・名鉄が連続３日間乗り放題となる「３・３・SUNフリーきっぷ」が発売されていました。「３・３・SUNデジタルフリーきっぷ」は「３・３・SUNフリーきっぷ」がデジタルきっぷとなり、2025年に復活したものです。
「３・３・SUNデジタルフリーきっぷ」のフリーエリアは、
- 近鉄・南海の全線
- 名鉄の名古屋本線（東岡崎～名鉄岐阜）・犬山線・各務原線・常滑線・空港線・河和線（太田川～知多半田）・西尾線（新安城～西尾）
で、名鉄のエリア内での乗降可能駅はタッチ決済対応の改札機が設置されている
中部国際空港/名鉄名古屋/金山/東岡崎/神宮前/国府宮/名鉄一宮/新木曽川/笠松/名鉄岐阜/犬山/知多半田/西尾
の計13駅に限られます。
以前私は、近鉄や南海など関西の私鉄各社が乗り放題となる「スルッとKANSAI」のエリア内における最長片道経路をGraphillionで求めてみた、という記事を書いたことがあります。今回、「３・３・SUNデジタルフリーきっぷ」でも最長片道経路を求めてみました。なお、ここでいう「最長片道経路」とは、同じ駅を二度通らず、途中で経路が分断されない一本の経路のうち、鉄道営業キロの合計が最も長くなるものを指すものとします。
結果はこちらです↓
区間：国府宮→京都（逆向き可）
経路：国府宮→ 名鉄岐阜→ 新鵜沼→ 名鉄名古屋→〔徒歩〕近鉄名古屋→ 伊勢中川→ 大和八木→ 橿原神宮前→ 古市→ 河内長野→ 難波→〔徒歩〕大阪難波→ 生駒→ 王寺→〔徒歩〕新王寺→ 西田原本→〔徒歩〕田原本→ 大和西大寺→ 京都
総距離：376.9 km
通過駅数：234駅
条件：「名鉄名古屋⇔近鉄名古屋」「大阪難波⇔難波」「王寺⇔新王寺」「田原本⇔西田原本」は徒歩乗換を可とする
大和八木駅で４方向の路線が集まってしまうこと、南海⇔近鉄間の乗換駅が難波と河内長野に限られてしまうことから、南海の和歌山方面には向かわないルートとなり、それほど距離が延びませんでした。
とはいえ、直感的には加太～国府宮のようなルートが最長に思えるのに対し、京都が出発/終着駅となるルートになるのは面白いですね。なお、加太駅を始発駅としたルートは、「加太 → 紀ノ川 → 岸里玉出 → 河内長野 → 古市 → 橿原神宮前 → 大和八木 → 伊勢中川 → 近鉄名古屋 →〔徒歩〕名鉄名古屋 → 東枇杷島 → 新鵜沼 → 名鉄岐阜 → 国府宮」となり総距離は346.8kmとなります。
（以下、技術的な話）
今回、最長片道経路探索に使ったデータとスクリプトです。
https://github.com/hamanasu12/3_3_SUN_Free_longest-one-way-route
今回の最長片道経路探索はChatGPT Proに依頼し、近鉄・南海の駅間距離情報はスルっとKANSAI最長経路探索時に作成した資料を活用、名鉄の駅間距離情報はCodexの手で作成し、最長経路探索は混合整数線形計画（MILP）のソルバーを用いて実施しました。
駅・駅間区間のグラフ化から、最長経路特定までに使用したツールや計算方法は以下の通りです。（コードは記事最後に掲載します。）
| 処理 | 使用したもの |
|---|---|
| 駅・駅間区間のグラフ化 | NetworkX |
| 接続関係や連結性の確認 | NetworkX |
| 最長単純経路の探索 | 混合整数線形計画（MILP） |
| 最適化ソルバー | HiGHS |
| 結果の駅順への復元・検証 | NetworkX＋独自処理 |
最長片道経路の探索方法としては、「深さ優先探索（DFS：Depth-First Search）」や「ゼロ抑制二分決定図（ZDD）（Graphillionで使用される探索方法）」などが挙げられます。
今回は、「３・３・SUNデジタルフリーきっぷ」のフリーエリアはグラフとしては中規模になることや、名鉄のフリーエリア内で乗降可能駅/不可駅があることなどから、探索方法として「混合整数線形計画（MILP）」を採用しています。
MILPでは、「駅を使用するか」「始点・終点にできるか」「同じ駅を二度通らないか」といった条件をそれぞれ変数と数式として明示的に設定することができるので、今回のように複数の条件を同時に扱う問題に向いています。
なお、同じ問題をCodexに解かせたところCodexでは「深さ優先探索（DFS）」が採用されました。「３・３・SUNデジタルフリーきっぷ」のフリー区間程度であれば、単純な「深さ優先探索（DFS）」でも最長片道経路問題を解くことができるようです。
1. MILPとは何か
「MILP」とは、Mixed-Integer Linear Programming のことです。それぞれの単語の意味は、
| 言葉 | 意味 |
|---|---|
| Mixed | 複数種類の変数を混ぜられる |
| Integer | 整数しか取れない変数がある |
| Linear | 式が一次式で表される |
| Programming | ここでは「計画・最適化」という意味 |
ですので、日本語では一般に「混合整数線形計画法」と呼ばれます。
以下で、今回「３・３・SUNデジタルフリーきっぷ」の最長片道経路問題をどのように定式化したかを記述します。
2. 「３・３・SUNデジタルフリーきっぷ」フリーエリアのグラフ化
「３・３・SUNデジタルフリーきっぷ」のフリーエリアを、無向多重グラフ
$$G = (V,E)$$
として表します。
- $V$：駅の集合
- $E$：隣接駅間の区間の集合
ここで、$E$ に含まれる一つ一つの区間を $e$ と表します。各区間 $e$ には、その区間の営業キロを表す $d_{e}$ を設定します。
$$d_{e} = \begin{cases}
\text{その区間の営業キロ } & {e\text{が鉄道区間の場合}} \
0 & {e\text{が徒歩連絡の場合}}
\end{cases}$$
したがって、
- 鉄道区間では $d_{e} > 0$
- 徒歩連絡では $d_{e} = 0$
となります。
このグラフは多重グラフなので、同じ2駅間に複数路線が存在する場合も、それぞれ別の物理区間として保持できます。
3. グラフの辺について、無向辺から有向アークに変換する
鉄道の区間そのものには、通常、向きがありません。
そのため、例えば「名鉄名古屋―山王」という区間は、
$$e = {\text{名鉄名古屋},\text{山王}}$$
という1本の無向辺として表せます。これは、「名鉄名古屋と山王がつながっている」という意味です。
しかし、今回求めるのは単なる区間の集まりではなく、実際に駅を順番に進んでいく経路です。そのため、その区間をどちら向きに通るのかも区別する必要があります。
そこで、1本の無向区間から、次の2通りの進み方を用意します。
$$\text{名鉄名古屋}\rightarrow\text{山王}$$
$$\text{山王}\rightarrow\text{名鉄名古屋}$$
一般に、両端が駅 $i$ と駅 $j$ である無向区間は
$$e = { i,j}$$
と表しますが、この区間から次の2本の「向きのある移動候補」を作ります。
$$(i,j,e),\qquad(j,i,e)$$
- $(i,j,e)$：物理区間 $e$ を使って、駅 $i$ から駅 $j$ へ進む
- $(j,i,e)$：同じ物理区間 $e$ を使って、駅 $j$ から駅 $i$ へ進む
このような向きのある移動候補を「有向アーク」と呼び、すべての有向アークを集めた集合を $A$ とします。
なお、ここでは、実際の鉄道区間は2本に増えていません。物理的な区間 $e$ は1本のままであり、その区間を通る方向を2通り用意しただけです。
方向を区別することで、後ほど、
- どの駅から出発したか
- どの駅へ到着したか
- 各駅に何本のアークが入るか
- 各駅から何本のアークが出るか
- 駅をどの順番で通るか
を数式で表せるようになります。
グラフを上記の通り定義した上で、ここから「混合整数線形計画（MILP）」の定式化のために使用する変数を定義していきます。
4. 使用する変数
駅数を
$$N = \lvert V \rvert$$
とします。
4.1 区間使用変数
各有向アーク $(i,j,e) \in A$ について、
$$x_{ije} = \begin{cases}
1 & {i\text{から}j\text{へ物理区間}e\text{を使う}} \
0 & \text{使わない}
\end{cases}$$
とします。これは0–1変数です。
4.2 駅使用変数
各駅 $v \in V$ について、
$$y_{v} = \begin{cases}
1 & {\text{駅}v\text{を経路に含める}} \
0 & \text{含めない}
\end{cases}$$
とします。
4.3 始点変数
$$s_{v} = \begin{cases}
1 & {\text{駅}v\text{を始点にする}} \
0 & \text{始点にしない}
\end{cases}$$
とします。
4.4 終点変数
$$t_{v} = \begin{cases}
1 & {\text{駅}v\text{を終点にする}} \
0 & \text{終点にしない}
\end{cases}$$
とします。
4.5 順序変数
各駅 v について、その駅を経路のどの段階で通るかを表す補助変数 $q_{v}$ を用意します。駅を使用しない場合は $q_{v}$=0、使用する場合は1以上の値を取るようにします。
5. 目的関数
求めたいのは、使用した鉄道区間の営業キロの合計が最大になる経路です。
したがって目的関数は、
$$\max\sum\limits_{(i,j,e) \in A}d_{e}x_{ije}$$
となります。
$d_{e}$は区間の距離、$x_{ije}$は、その方向のアークを選べば1、選ばなければ0となる区間使用変数です。したがって、上式は、選択したアークに対応する区間の距離を加算し、その合計距離を最大にするという意味になります。
徒歩連絡辺は
$$d_{e} = 0$$
なので、経路を接続するためには利用できますが、目的関数の距離には加算されません。
なお、SciPyのMILPは最小化問題を解く関数であるため、コードでは符号を反転して、
$$\min - \sum\limits_{(i,j,e) \in A}d_{e}x_{ije}$$
としてソルバーであるHiGHSへ渡します。
6. 各駅の入次数・出次数制約
ここでは、選択されたアークが各駅へ何本入り、各駅から何本出るかを制約します。
ある駅に入ってくるアークの本数を「入次数」、ある駅から出ていくアークの本数を「出次数」と呼びます。 ただし、ここで数えるのは鉄道網にもともと存在するすべてのアークではありません。 区間使用変数 $x_{ije}$ が1となり、今回の経路として選択されたアークだけを数えます。
6.1 各駅の出次数制約
駅 v から出る有向アークの集合を
$$\delta^{+}(v)$$
とします。例えば、駅 v から駅 j へ物理区間 e を使って進むアークは、 (v, j, e) と表されます。
駅 v から出る選択アークの本数は、
$$\sum\limits_{(v,j,e) \in \delta^{+}(v)}x_{vje}$$
で表すことができます。この本数について、次の制約を設定します。
$$\sum\limits_{(v,j,e) \in \delta^{+}(v)}x_{vje} = y_{v} - t_{v}$$
この式が表す内容を、駅の状態ごとに確認します。
駅を使用しない場合
$y_{v}$=0、$t_{v}$=0 なので、右辺は0となり、駅 v から出る選択アークは0本になります。
始点の場合
$y_{v}$=1、$t_{v}$=0 なので、右辺は1となり、始点から出る選択アークは1本になります。
中間駅の場合
$y_{v}$=1、$t_{v}$=0 なので、右辺は1となり、中間駅から出る選択アークは1本になります。
終点の場合
$y_{v}$=1、$t_{v}$=1 なので、右辺は0となり、終点から出る選択アークは0本になります。
以上をまとめると、出次数制約によって、
- 使用しない駅：出るアークは0本
- 始点：出るアークは1本
- 中間駅：出るアークは1本
- 終点：出るアークは0本
となります。
6.2 各駅の入次数制約
次に、駅 v へ入る有向アークの集合を
$$\delta^{-}(v)$$
とします。例えば、駅 i から駅 v へ物理区間 e を使って進むアークは、 (i, v, e) と表されます。
駅 v へ入る選択アークの本数は、
$$\sum\limits_{(i,v,e) \in \delta^{-}(v)}x_{ive}$$
で表すことができます。この本数について、次の制約を設定します。
$$\sum\limits_{(i,v,e) \in \delta^{-}(v)}x_{ive} = y_{v} - s_{v}$$
ここで、$s_{v}$ は、駅 v を始点にする場合に1となる始点変数です。この式についても、駅の状態ごとに確認します。
駅を使用しない場合
$y_{v}$=0、$s_{v}$=0 なので、右辺は0となり、駅 v へ入る選択アークは0本になります。
始点の場合
$y_{v}$=1、$s_{v}$=1 なので、右辺は0となり、始点へ入る選択アークは0本になります。
中間駅の場合
$y_{v}$=1、$s_{v}$=0 なので、右辺は1となり、中間駅へ入る選択アークは1本になります。
終点の場合
$y_{v}$=1、$s_{v}$=0 なので、右辺は1となり、終点へ入る選択アークは1本になります。
以上をまとめると、入次数制約によって、
- 使用しない駅：入るアークは0本
- 始点：入るアークは0本
- 中間駅：入るアークは1本
- 終点：入るアークは1本
となります。
6.3 入次数制約と出次数制約を組み合わせた結果
入次数制約と出次数制約を合わせると、各駅の状態は次のようになります。
| 駅の状態 | $y_{v}$ | $s_{v}$ | $t_{v}$ | 入る本数 | 出る本数 |
|---|---|---|---|---|---|
| 使用しない駅 | 0 | 0 | 0 | 0 | 0 |
| 始点 | 1 | 1 | 0 | 0 | 1 |
| 中間駅 | 1 | 0 | 0 | 1 | 1 |
| 終点 | 1 | 0 | 1 | 1 | 0 |
つまり、始点では経路が始まり、中間駅では入ってきた経路が次の駅へ続き、終点では経路がそこで終了します。
また、各駅へ入る選択アークと、各駅から出る選択アークは、それぞれ最大1本に制限されます。 そのため、一つの経路の中で同じ駅へ二度入ったり、同じ駅から二度出たりすることはできません。 これにより、同じ駅を繰り返し通る経路は除外されます。
ただし、この二つの次数制約だけでは、始点から終点までの経路とは別の場所に、独立した閉路が選択される可能性が残っています。
例えば、
- 始点から終点までの一本の経路
- それとは離れた場所にある環状の経路
が同時に選ばれる可能性があります。このような閉路は、後ほど説明するMTZ制約によって除去します。
7. 始点と終点を一つずつ選ぶ
始点は全体で1駅だけです。
$$\sum\limits_{v \in V}s_{v} = 1$$
終点も全体で1駅だけです。
$$\sum\limits_{v \in V}t_{v} = 1$$
さらに、同じ駅を始点と終点の両方にはできないように、
$$s_{v} + t_{v} \leq 1\qquad(\forall v \in V)$$
としています。
この条件により、空の経路や、始点と終点が同じ閉路も候補から除外することができます。
8. 始点・終点にできる駅の制限
今回、すべての駅を自由に始点・終点にできるわけではありません。
許可された端点集合を
$$V_{end} \subseteq V$$
とすると、許可されていない駅では、
$$s_{v} = 0,\qquad t_{v} = 0\qquad(v \notin V_{end})$$
としています。
実際の集合は、おおむね次の構成です。
- 近鉄・南海の対象区間に含まれる全駅
- 名鉄側は、公式エリア図で指定された13駅
したがって、名鉄の対象区間内にある駅でも、指定13駅以外は経路の中間駅にはなれますが、始点または終点にはなれません。
9. 同じ物理区間を両方向に使うことの禁止
無向の物理区間 $e = { i,j}$について、2方向の変数があります。
$$x_{ije},\quad x_{jie}$$
両方向を同時に選ばないように、
$$x_{ije} + x_{jie} \leq 1\qquad(\forall e \in E)$$
としています。
例えば、
$$A\rightarrow B$$
と
$$B\rightarrow A$$
を同じ経路で同時に選ぶことはできません。
10. 順序変数と駅使用変数の関係
順序変数には、
$$q_{v} \leq Ny_{v}$$
$$q_{v} \geq y_{v}$$
という制約をつけます。この制約により、駅使用変数
$y_{v}$ と順序変数 $q_{v}$ が連動します。
駅を使わない場合
$y_{v} = 0$なら、
$$q_{v} \leq 0$$
$$q_{v} \geq 0$$
なので、
$$q_{v} = 0$$
となります。
駅を使う場合
$y_{v} = 1$なら、
$$1 \leq q_{v} \leq N$$
となります。つまり、
経路に含まれる駅には、1以上 $N$ 以下の、通過順序を表す値が割り当てられる
という意味です。
11. MTZ制約による閉路除去
各有向アーク $(i,j,e) \in A$について、次の制約を設定しています。
$$q_{j} \geq q_{i} + 1 - N(1 - x_{ije})$$
これを展開すると、
$$q_{j} - q_{i} - Nx_{ije} \geq 1 - N$$
となり、コード上の式と一致します。
アークを使用する場合
アークを使用する場合は、$x_{ije}$=1です。
選択したアークで駅 i から駅 j へ進む場合、駅 j の順序は駅 i より後でなければなりません。そのため、
$$q_{j} \geq q_{i} + 1$$
となります。
つまり、選択されたアークを進むたびに順序が必ず増加します。
例えば、
$$A\rightarrow B\rightarrow C$$
を選んだ場合、
$$q_{B} \geq q_{A} + 1$$
$$q_{C} \geq q_{B} + 1$$
となります。
ただし、この条件はアークを選択した場合だけ働かせる必要があります。
アークを使用しない場合
アーク $(i,j,e)$を使用しない場合は、
$$x_{ije} = 0$$
です。これをMTZ制約に代入すると、
$$q_{j} \geq q_{i} + 1 - N$$
となります。
ここで $N$ は鉄道網に含まれる駅の総数です。また、順序変数には、
$$0 \leq q_{i} \leq N,\qquad 0 \leq q_{j} \leq N$$
という範囲が設定されています。
例えば、駅数が $N = 300$ で、$q_{i} = 200$だった場合、制約は、
$$q_{j} \geq 200 + 1 - 300 = - 99$$
となります。
しかし、$q_{j}$にはもともと、
$$q_{j} \geq 0$$
という条件があります。そのため、新たに得られた「$q_{j} \geq - 99$」という条件は、$q_{j}$の値を実際には何も制限しません。
これは、アークを使用しない場合には、
駅 $i$ と駅 $j$ の通過順序に関係を求めない
ことを意味します。
したがって、この式は、アークの使用状況に応じて次のように働きます。
| アークの状態 | $x_{ije}$ | 順序に関する条件 |
|---|---|---|
| 使用する | 1 | $q_{j}$ ≥ $q_{i}$ + 1 を要求する |
| 使用しない | 0 | $q_{i}$と$q_{j}$の順序関係を実質的に要求しない |
このように、0–1変数の値に応じて、制約を「働かせる」または「実質的に働かせない」ために十分大きな数を引く方法を、一般に「Big-M法」と呼びます。
今回の式では、新しい記号 $M$ を用意するのではなく、駅数 $N$をその十分大きな数として利用しています。
12. なぜMTZ制約で閉路が消えるのか
仮に、次の閉路が選ばれたとします。
$$A\rightarrow B\rightarrow C\rightarrow A$$
するとMTZ制約から、
$$q_{B} \geq q_{A} + 1$$
$$q_{C} \geq q_{B} + 1$$
$$q_{A} \geq q_{C} + 1$$
が必要です。
3式を足すと、
$$q_{A} + q_{B} + q_{C} \geq q_{A} + q_{B} + q_{C} + 3$$
すなわち、
$$0 \geq 3$$
となります。
これは成立しません。したがって、選択されたアークの中に有向閉路は存在できません。
なお、MTZは、Miller–Tucker–Zemlinの頭文字です。
13. なぜ選択区間が一本につながるのか
次数制約だけなら、選択された区間は一般に、
- 始点から終点までの一本の経路
- それとは別に存在する一つ以上の閉路
へ分解される可能性があります。
しかし今回のモデルでは、
- 始点が正確に1駅
- 終点が正確に1駅
- 始点以外の使用駅には1本入る
- 終点以外の使用駅からは1本出る
- MTZ制約により閉路は禁止
となっています。
したがって、始点から選択アークをたどると、必ず終点に到達します。
もしその経路とは離れた場所に別の選択区間があれば、そこには始点も終点もないため、各駅の入次数と出次数がともに1になります。有限グラフでは、それは必ず閉路を形成します。しかし閉路はMTZ制約に反します。
よって、選択されたすべてのアークは、始点から終点までの一本の経路に含まれます。
14. 完全な数理モデル
以上をまとめると、実際のMILPは次のように書けます。
目的関数
$$\max\sum\limits_{(i,j,e) \in A}d_{e}x_{ije}$$
制約条件
$$\sum\limits_{(v,j,e) \in \delta^{+}(v)}x_{vje} = y_{v} - t_{v}\qquad(\forall v \in V)$$
$$\sum\limits_{(i,v,e) \in \delta^{-}(v)}x_{ive} = y_{v} - s_{v}\qquad(\forall v \in V)$$
$$\sum\limits_{v \in V}s_{v} = 1$$
$$\sum\limits_{v \in V}t_{v} = 1$$
$$s_{v} + t_{v} \leq 1\qquad(\forall v \in V)$$
$$x_{ije} + x_{jie} \leq 1\qquad(\forall e = { i,j} \in E)$$
$$q_{v} \leq Ny_{v}\qquad(\forall v \in V)$$
$$q_{v} \geq y_{v}\qquad(\forall v \in V)$$
$$q_{j} \geq q_{i} + 1 - N(1 - x_{ije})\qquad(\forall(i,j,e) \in A)$$
許可されていない端点について、
$$s_{v} = t_{v} = 0\qquad(\forall v \notin V_{end})$$
変数領域
$$x_{ije} \in { 0,1}$$
$$y_{v},s_{v},t_{v} \in { 0,1}$$
$$0 \leq q_{v} \leq N$$
です。
15. この定式化が解いている問題
以上により、実際に解いている問題は厳密には、
許可された駅から始点と終点を1駅ずつ選び、同じ駅を二度使用せず、選択した全区間が始点から終点まで一本につながり、徒歩連絡区間の距離を0 kmとして、鉄道営業キロの合計が最大になる有向単純経路を求める。
という問題となります。
最後に、使用したコードを掲載します。
import json
from pathlib import Path
import networkx as nx
import numpy as np
import pandas as pd
from scipy.optimize import Bounds, LinearConstraint, milp
from scipy.sparse import lil_matrix
ROOT = Path(__file__).resolve().parent
KINKI_OPERATORS = {"KINTETSU", "NANKAI"}
MEITETSU_GATE_NAMES = {
"中部国際空港", "名鉄名古屋", "金山", "東岡崎", "神宮前", "国府宮",
"名鉄一宮", "新木曽川", "笠松", "名鉄岐阜", "犬山", "知多半田", "西尾",
}
# 公式エリア図に線として描かれた区間。指定13駅間のすべての迂回路ではなく、
# 下記の路線・端点間だけを対象にする。
MEITETSU_AREA_SEGMENTS = [
("ME_NAGOYA_MAIN", "東岡崎", "名鉄岐阜"),
("ME_INUYAMA", "東枇杷島", "新鵜沼"),
("ME_KAKAMIGAHARA", "新鵜沼", "名鉄岐阜"),
("ME_NISHIO", "新安城", "西尾"),
("ME_TOKONAME", "神宮前", "常滑"),
("ME_AIRPORT", "常滑", "中部国際空港"),
("ME_KOWA", "太田川", "知多半田"),
]
# 徒歩距離は鉄道営業キロに加算しないため 0 km とする。
WALK_TRANSFERS = [
("近鉄", "王寺", "近鉄", "新王寺", "王寺―新王寺"),
("近鉄", "田原本", "近鉄", "西田原本", "田原本―西田原本"),
("近鉄", "生駒", "近鉄", "鳥居前", "生駒―鳥居前"),
("近鉄", "大阪難波", "近鉄", "難波", "大阪難波―南海難波"),
("近鉄", "近鉄名古屋", "名鉄", "名鉄名古屋", "近鉄名古屋―名鉄名古屋"),
]
def read_sources():
ke = pd.read_excel(ROOT / "kinki.xlsx", sheet_name="路線データ")
ks = pd.read_excel(ROOT / "kinki.xlsx", sheet_name="駅マスター")
kl = pd.read_excel(ROOT / "kinki.xlsx", sheet_name="路線マスター")
me = pd.read_excel(ROOT / "meitetsu.xlsx", sheet_name="路線データ")
ms = pd.read_excel(ROOT / "meitetsu.xlsx", sheet_name="駅マスター")
ml = pd.read_excel(ROOT / "meitetsu.xlsx", sheet_name="路線マスター")
return ke, ks, kl, me, ms, ml
def build_graph():
ke, ks, kl, me, ms, ml = read_sources()
station_name = dict(zip(ks.station_id, ks.official_name))
station_name.update(dict(zip(ms.station_id, ms.official_name)))
line_name = dict(zip(kl.line_id, kl.route_name))
line_name.update(dict(zip(ml.line_id, ml.route_name)))
g = nx.MultiGraph()
k_edges = ke[ke.operator_id.isin(KINKI_OPERATORS)].copy()
for row in k_edges.itertuples(index=False):
g.add_edge(
row.from_station_id, row.to_station_id, key=row.edge_id,
weight=float(row.distance_km), line_id=row.line_id,
line=line_name[row.line_id], kind="rail", edge_id=row.edge_id,
)
# 名鉄は公式エリア図に描かれた指定区間だけを対象とする。
mg_all = nx.MultiGraph()
for row in me.itertuples(index=False):
mg_all.add_edge(
row.from_station_id, row.to_station_id, key=row.edge_id,
weight=float(row.distance_km), line_id=row.line_id,
line=line_name[row.line_id], kind="rail", edge_id=row.edge_id,
)
name_to_mid = {name: sid for sid, name in zip(ms.station_id, ms.official_name)}
gates = {name_to_mid[n] for n in MEITETSU_GATE_NAMES}
mg = nx.MultiGraph()
for line_id, start_name, end_name in MEITETSU_AREA_SEGMENTS:
line_edges = [
(u, v, k, d) for u, v, k, d in mg_all.edges(keys=True, data=True)
if d["line_id"] == line_id
]
line_graph = nx.MultiGraph()
for u, v, k, d in line_edges:
line_graph.add_edge(u, v, key=k, **d)
start, end = name_to_mid[start_name], name_to_mid[end_name]
node_path = nx.shortest_path(line_graph, start, end)
for u, v in zip(node_path, node_path[1:]):
key, data = next(iter(line_graph[u][v].items()))
mg.add_edge(u, v, key=key, **data)
for u, v, key, data in mg.edges(keys=True, data=True):
g.add_edge(u, v, key=key, **data)
k_name_to_id = {name: sid for sid, name in zip(ks.station_id, ks.official_name)}
m_name_to_id = {name: sid for sid, name in zip(ms.station_id, ms.official_name)}
transfer_records = []
for op1, n1, op2, n2, label in WALK_TRANSFERS:
a = k_name_to_id[n1] if op1 == "近鉄" else m_name_to_id[n1]
b = k_name_to_id[n2] if op2 == "近鉄" else m_name_to_id[n2]
key = f"WALK_{len(transfer_records)+1}"
g.add_edge(a, b, key=key, weight=0.0, line_id=key, line="徒歩連絡",
kind="walk", edge_id=key, label=label)
transfer_records.append((a, b, label))
allowed_endpoints = set(k_edges.from_station_id) | set(k_edges.to_station_id) | gates
return g, station_name, gates, allowed_endpoints, transfer_records, mg
def solve_milp(g, allowed_endpoints):
nodes = list(g.nodes)
node_ix = {n: i for i, n in enumerate(nodes)}
undirected_edges = list(g.edges(keys=True, data=True))
arcs = []
for ei, (u, v, key, data) in enumerate(undirected_edges):
arcs.append((u, v, ei, data))
arcs.append((v, u, ei, data))
n, m = len(nodes), len(arcs)
# variables: arc x[m], node y[n], start s[n], end t[n], order q[n]
x0, y0, s0, t0, q0 = 0, m, m+n, m+2*n, m+3*n
nv = m + 4*n
c = np.zeros(nv)
c[x0:x0+m] = [-a[3]["weight"] for a in arcs]
integrality = np.zeros(nv, dtype=int)
integrality[:m+3*n] = 1
lb = np.zeros(nv)
ub = np.ones(nv)
ub[q0:q0+n] = n
for i, node in enumerate(nodes):
if node not in allowed_endpoints:
ub[s0+i] = 0
ub[t0+i] = 0
bounds = Bounds(lb, ub)
rows = []
lo = []
hi = []
def add(coeff, lower, upper):
rows.append(coeff)
lo.append(lower)
hi.append(upper)
out_arcs = {v: [] for v in nodes}
in_arcs = {v: [] for v in nodes}
edge_arcs = {}
for ai, (u, v, ei, data) in enumerate(arcs):
out_arcs[u].append(ai)
in_arcs[v].append(ai)
edge_arcs.setdefault(ei, []).append(ai)
for i, v in enumerate(nodes):
# out = y - t; in = y - s
r = {x0+a: 1 for a in out_arcs[v]}
r[y0+i] = -1
r[t0+i] = 1
add(r, 0, 0)
r = {x0+a: 1 for a in in_arcs[v]}
r[y0+i] = -1
r[s0+i] = 1
add(r, 0, 0)
# q <= n*y and q >= y
add({q0+i: 1, y0+i: -n}, -np.inf, 0)
add({q0+i: 1, y0+i: -1}, 0, np.inf)
# a node cannot be both endpoints
add({s0+i: 1, t0+i: 1}, -np.inf, 1)
add({s0+i: 1 for i in range(n)}, 1, 1)
add({t0+i: 1 for i in range(n)}, 1, 1)
# At most one direction/version of each physical edge.
for ais in edge_arcs.values():
add({x0+a: 1 for a in ais}, -np.inf, 1)
# MTZ ordering eliminates disconnected directed cycles.
for ai, (u, v, ei, data) in enumerate(arcs):
iu, iv = node_ix[u], node_ix[v]
# q[v] >= q[u] + 1 - n*(1-x)
add({q0+iv: 1, q0+iu: -1, x0+ai: -n}, 1-n, np.inf)
A = lil_matrix((len(rows), nv), dtype=float)
for ri, coeff in enumerate(rows):
for ci, val in coeff.items():
A[ri, ci] = val
result = milp(
c=c, integrality=integrality, bounds=bounds,
constraints=LinearConstraint(A.tocsr(), np.array(lo), np.array(hi)),
options={"time_limit": 600, "mip_rel_gap": 0.0, "presolve": True},
)
if result.x is None:
raise RuntimeError(result.message)
chosen = {}
for ai, (u, v, ei, data) in enumerate(arcs):
if result.x[x0+ai] > 0.5:
chosen[u] = (v, ei, data)
start = nodes[int(np.argmax(result.x[s0:s0+n]))]
end = nodes[int(np.argmax(result.x[t0:t0+n]))]
path_nodes = [start]
path_edges = []
cur = start
while cur != end:
nxt, ei, data = chosen[cur]
path_edges.append((cur, nxt, undirected_edges[ei][2], data))
path_nodes.append(nxt)
cur = nxt
if len(path_nodes) > n + 1:
raise RuntimeError("Path reconstruction loop")
return result, path_nodes, path_edges
def main():
g, names, gates, allowed, transfers, mg = build_graph()
print("combined", g.number_of_nodes(), g.number_of_edges())
print("meitetsu_core", mg.number_of_nodes(), mg.number_of_edges(),
"km", sum(d["weight"] for *_, d in mg.edges(data=True)))
simple = nx.Graph(g)
print("components", [len(c) for c in nx.connected_components(simple)])
print("biconnected max", max(map(len, nx.biconnected_components(simple))))
result, path_nodes, path_edges = solve_milp(g, allowed)
rail_km = sum(e[3]["weight"] for e in path_edges)
output = {
"solver_status": int(result.status),
"solver_message": result.message,
"objective_km": rail_km,
"start": names[path_nodes[0]],
"end": names[path_nodes[-1]],
"station_count": len(path_nodes),
"rail_edge_count": sum(e[3]["kind"] == "rail" for e in path_edges),
"walk_count": sum(e[3]["kind"] == "walk" for e in path_edges),
"path": [
{
"seq": i + 1,
"from": names[u],
"to": names[v],
"distance_km": data["weight"],
"line": data["line"],
"kind": data["kind"],
"edge_id": data["edge_id"],
}
for i, (u, v, key, data) in enumerate(path_edges)
],
}
(ROOT / "longest_path_result.json").write_text(
json.dumps(output, ensure_ascii=False, indent=2), encoding="utf-8"
)
pd.DataFrame(output["path"]).to_csv(
ROOT / "longest_path_result.csv", index=False, encoding="utf-8-sig"
)
print(json.dumps({k: v for k, v in output.items() if k != "path"},
ensure_ascii=False, indent=2))
if __name__ == "__main__":
main()
本当に、最近のAIの賢さには驚かされるばかりです。
（この記事は、私のブログ「線路のあるとこ一人旅」の記事からの転載です。）