はじめに
名古屋市営地下鉄の定期券について、複数の駅を選ぶと「それらを一筆書きで通るルート」と定期代の候補を出してくれるWebアプリを作りました。
2026/10 追記：UIを刷新し、条件の入力と結果を1ページにまとめました（PCは左右、スマホは縦並び）。あわせて「寄り道駅の比較」機能を追加しています。スクリーンショットは新しいUIのものです。
定期券に通したい駅を選ぶと、
一筆書きで通れるルートと定期代の候補が出てきます。
大学生になって、家から大学までの定期券を作ることになりました。名古屋市営地下鉄の定期代は距離で決まりますが、一定の距離を超えるとそれ以上は値段が上がりません。それなら、最短経路ではなく、よく使う駅を通る経路にしたほうが得なのでは？と考えました。
ちなみに、学生定期券でも経路は自由に選べます。交通局の学生定期券についてにこう書かれています。
市バス・地下鉄の学生定期券は、通学経路に限らずにお客様の希望される区間・経路でご購入いただける定期券です。通学に限らず、塾やアルバイトにも、お客さまの希望される区間・経路が選べます。
ただ、どの駅を通せるのか、いくらになるのかを路線図を見ながら手で調べるのは大変です。そこで、通りたい駅を選ぶとルートを考えてくれるアプリを作りました。
この記事では主に次の3つを書きます。
- 路線図をグラフにして「一筆書きルート」を列挙する方法
- 最初の全列挙が遅かったので、ビットマスク付きの最良優先探索に変えた話
- Next.js と FastAPI を Vercel の1プロジェクトにまとめた話
定期券のルールをざっくり
名古屋市交通局の定期券の購入方法には、地下鉄定期券の経路について次のように書かれています。
地下鉄の定期券は「一筆書き」で描ける経路で乗換が3回以内なら、お客さまの便利な経路を選んで購入できます。
経路が交差したり、駅が重複する場合は発売できません。
経路・接続号線を判別する駅（大曽根、金山、西高蔵、国際センター、吹上）と乗換駅の総数が5駅を超える場合は、3回以内の乗換でも発売できないことがあります。
定期券の料金は「一筆書き」の経路の長さで決まります。
料金は距離で1区（3kmまで）から5区（15km超）の5段階です（料金表）。
つまり「通りたい駅を全部含む一筆書きルートのうち、できるだけ短いもの」を探す問題になります。
たとえば大学生の通学定期（1ヶ月）だと、アプリの計算結果はこうなります。
| 選んだ駅 | ルート | 距離 | 区 | 1ヶ月 |
|---|---|---|---|---|
| 名古屋・八事 | 名古屋 → 伏見（乗換） → 八事 | 9.4km | 3区 | 5,880円 |
| 名古屋・金山・八事 | 名古屋 → 伏見（乗換） → 上前津（乗換） → 金山 → 八事 | 14.0km | 4区 | 6,200円 |
| 名古屋・金山・八事（遠回り） | 名古屋 → 栄（乗換） → 金山 → 新瑞橋（乗換） → 御器所（乗換） → 八事 | 17.6km | 5区 | 6,440円 |
名古屋〜八事の定期に月320円足すと、金山も通れるようになります。また、5区（15km超）が上限なので、そこから先はどれだけ遠回りしても6,440円のままです。
各候補には、始点・終点・選んだ駅・乗換駅だけを並べた簡易ルート図が表示されます。「全N駅を表示」を押すと、途中で通る駅をすべて確認できます。
寄り道駅の比較
「遠回りしたほうが得なのでは？」を確かめやすくするために、駅を「必須駅（家・大学）」と「寄り道駅（バイト先や店が多い駅など）」に分けて選べるようにしました。寄り道駅を入れて検索すると、各候補に次の2つが表示されます。
- 必須駅だけを通る遠回りしないルートと比べて、定期代がいくら増えるか
- 遠回りしない定期で寄り道駅まで乗り越す場合と比べて、寄り道駅で月に何回以上降りれば遠回りの定期のほうが得になるか
乗り越し運賃は、遠回りしないルート上でいちばん安く乗り越せる駅から寄り道駅までの普通運賃を、往復分で計算しています。
たとえば必須駅を名古屋・八事、寄り道駅を金山にすると、金山を通す定期は遠回りしない定期より月320円高くなります。一方、遠回りしない定期で金山に行くと上前津から乗り越して往復420円かかるので、金山で月1回以上降りるなら遠回りの定期のほうが得です。
構成
frontend/
├── app/page.tsx # Next.js (App Router) のUI
├── api/
│ ├── main.py # FastAPI: 路線データ・探索・料金計算
│ └── index.py # Vercel Serverless Function の入口
├── next.config.ts
├── vercel.json
└── requirements.txt
- フロントエンド: Next.js (TypeScript, Tailwind CSS)
- バックエンド: FastAPI
- ホスティング: Vercel
路線をグラフにする
駅をノード、駅間を辺、営業キロを重みにした無向グラフです。隣接リストを辞書で持っています。
class SubwayNetwork:
def __init__(self):
self.graph = {}
def add_edge(self, station1, station2, dist):
if station1 not in self.graph: self.graph[station1] = {}
if station2 not in self.graph: self.graph[station2] = {}
self.graph[station1][station2] = dist
self.graph[station2][station1] = dist
def build_nagoya_subway(self):
# 東山線
self.add_edge("高畑", "八田", 0.9)
self.add_edge("八田", "岩塚", 1.1)
# ...
全6路線で87駅・95辺です。乗換駅は駅名が同じなので、add_edge するだけで自然に路線同士がつながります。
入力ミスがないか、駅間の距離を路線ごとに合計して確かめました。東山線20.6km、名城線26.4km、名港線6.0km、鶴舞線20.4km、桜通線19.1km、上飯田線0.8kmで、合計93.3kmです。公表されている各線の営業キロと一致します。
路線の判定用に、路線ごとの駅リストも別に持っています。
LINE_STATIONS = {
"東山線": ["高畑", "八田", ...],
"名城線": ["金山", "東別院", ...],
# ...
}
def get_connecting_line(station1, station2):
for line, stations in LINE_STATIONS.items():
if station1 in stations and station2 in stations:
return line
return None
経路上で「隣り合う2駅がどの路線か」を順に見ていき、路線が変わった回数を乗換回数として数えます。
料金計算と浮動小数点の罠
料金は距離で区を引くだけです。
def get_fare(self, distance_km: float, fare_type: str):
dist_rounded = round(distance_km, 1)
for rule in self.fare_rules:
if dist_rounded <= rule.max_km:
...
round を入れているのは、0.1km単位の距離を足していくと誤差が出るからです。たとえば上社から本山経由で茶屋ヶ坂までは、駅間距離を足すとちょうど7.0kmで2区のはずです。
>>> 1.1 + 1.3 + 1.1 + 0.9 + 1.4 + 1.2
7.000000000000001
>>> 1.1 + 1.3 + 1.1 + 0.9 + 1.4 + 1.2 <= 7.0
False
このままだと3区になってしまいます。区の境界ちょうどの経路で金額が変わるので、ここは地味に大事でした。
料金表は公式の金額をそのまま辞書にしています。対応しているのは通勤、学生（大学生／高校・中学生／小学生以下）、割引通勤、割引学生の6種類で、1ヶ月と6ヶ月を出します。
最初の実装：順列 × 単純経路の全列挙
最初は素直に書きました。
- 選んだ駅の並び順を
itertools.permutationsで全部試す - 隣り合う2駅の間の単純経路（同じ駅を通らない経路）を列挙する
- すでに通った駅は次の区間で通行禁止にして、再帰的につなぐ
2駅間の経路列挙はこうです（抜粋）。ヒープで距離の短い順に取り出します。
def find_all_simple_paths(self, start, goal, exclude_stations, max_paths=1000):
queue = [(0.0, start, [start])]
found_paths = []
while queue:
dist, curr, path = heapq.heappop(queue)
if curr == goal:
found_paths.append((dist, path))
if len(found_paths) >= max_paths:
break
continue
for neighbor, weight in self.graph[curr].items():
if neighbor in path: continue
if neighbor in exclude_stations: continue
heapq.heappush(queue, (dist + weight, neighbor, path + [neighbor]))
return found_paths
見た目はダイクストラ法に似ていますが、「確定済みノードを再訪しない」処理がありません。最短経路だけでなく全経路が欲しいので、ヒープに入れるのは「駅」ではなく「そこまでの経路」です。
公式ルールの「経路が交差」については、個別の判定は入れていません。このグラフでは路線が交わる点がすべて乗換駅、つまり同じノードなので、同じ駅を2回通らない経路だけを探せば交差も起きない、という扱いにしています。
同じルートを逆向きにたどったものは同一視して捨てます。
route_tuple = tuple(res["full_path"])
rev_route_tuple = tuple(res["full_path"][::-1])
if route_tuple in seen_routes_set or rev_route_tuple in seen_routes_set:
continue
問題：駅を増やすと急に遅い
順列は n! 通りあり、区間ごとに経路列挙が走るので、駅数が増えると一気に重くなります。手元のPCでも5駅選ぶと4〜5秒かかり、実行時間に上限がある Serverless Function では不安な数字です。
改善：ビットマスク付きの最良優先探索
「順番を決めてから区間ごとにつなぐ」のをやめて、1本の経路を伸ばしながら「どの目的駅をもう通ったか」をビットマスクで持つようにしました。距離の短い経路から順にヒープから取り出すので、探索の種類としては均一コスト探索（ダイクストラ法と同じ取り出し順）です。
# 抜粋
def find_routes_by_distance(target_stops, fare_type, max_results=100):
target_index = {station: i for i, station in enumerate(target_stops)}
all_targets_mask = (1 << len(target_stops)) - 1
queue = []
# 選んだ駅すべてを出発点候補としてヒープに入れる
for station in target_stops:
mask = 1 << target_index[station]
heapq.heappush(queue, (0.0, station, [station], mask))
results = []
seen_routes_set = set()
expansions = 0
max_expansions = 200000
while queue and len(results) < max_results and expansions < max_expansions:
distance, station, path, mask = heapq.heappop(queue)
expansions += 1
# 全部の目的駅を通ったらゴール
if mask == all_targets_mask:
route_tuple = tuple(path)
rev_route_tuple = tuple(path[::-1])
if route_tuple not in seen_routes_set and rev_route_tuple not in seen_routes_set:
result = build_route_result(path, target_stops, distance, fare_type)
if result:
seen_routes_set.add(route_tuple)
results.append(result)
continue
for neighbor, weight in nw.graph[station].items():
if neighbor in path:
continue
next_mask = mask
if neighbor in target_index:
next_mask |= 1 << target_index[neighbor]
heapq.heappush(queue, (distance + weight, neighbor, path + [neighbor], next_mask))
return results
ポイントは3つです。
- 順列を回さない。 経路を伸ばす途中で目的駅を踏んだらビットを立てるだけなので、訪問順は探索が勝手に決めてくれます。
- 距離の短い順に出てくる。 ヒープから取り出す順がそのまま安い順なので、100件集まったら打ち切れます。
- 展開回数に上限を付ける。 最悪ケースでも20万回で止まります。
正直に書くと、計算量のオーダーが良くなったわけではありません。どちらの方式も単純経路を列挙していることは同じです。速くなったのは、全列挙が順列ごとに同じ区間の経路を何度も探し直していた無駄がなくなったからです。
また、100件または20万回で打ち切るので、理屈の上では取りこぼしがありえます。ただ、下の計測で試したケースでは展開回数は最大でも約4.7万回で、上限には当たりませんでした。
測ってみた
手元のPC（Python 3.13）で、各5回実行した中央値です。定期の種類は大学生です。
| 選んだ駅 | 件数 | 全列挙 | 最良優先 | 倍率 |
|---|---|---|---|---|
| 塩釜口・栄 | 24 | 27ms | 25ms | 1.1倍 |
| 塩釜口・栄・名古屋 | 24 | 230ms | 107ms | 2.1倍 |
| 塩釜口・栄・名古屋・金山 | 6 | 825ms | 187ms | 4.4倍 |
| 塩釜口・栄・名古屋・金山・大曽根 | 0 | 3,794ms | 222ms | 17倍 |
| 藤が丘・名古屋港・上小田井・徳重・赤池 | 0 | 4,793ms | 214ms | 22倍 |
2駅ではほぼ同じですが、駅が増えるほど差が開き、5駅では約20倍になりました。全列挙は駅数とともに急に重くなるのに対して、最良優先は3駅以上でも100〜200ms台に収まっています。この5ケースでは、両方式が返すルートは完全に一致しています。
最後のケースは終点を5つ選んだもので、一筆書きの端は2つしかないので0件が正解です。全列挙は「ない」と分かるまでに5秒近くかかっています。
全列挙も「網羅」モードとして残していて、8秒の制限時間を付けました。時間切れになったら、見つかった分だけ返して警告を出します。
if deadline is not None and time.monotonic() > deadline:
raise SearchLimitReached()
「窓口確認推奨」の判定
先ほどの「判別する駅と乗換駅の総数が5駅を超える場合」のルールです。公式の表現が「発売できないことがあります」なので、候補から外さずに注意書きを出すだけにしています。
DISCRIMINATOR_STATIONS = {"大曽根", "金山", "西高蔵", "国際センター", "吹上"}
def calculate_complexity(path):
...
return len(transfer_stations.union(found_discriminators))
この画像の5番と6番の候補は、どちらも乗換3回ですが、「乗換駅・特定駅の合計が5駅を超えるため、購入前に窓口で確認してください。」という注意書きが出るのは5番だけです。
| 候補 | 乗換駅 | 判別する駅 | 合計 | 注意書き |
|---|---|---|---|---|
| 5: 八事 → 御器所 → 名古屋 → 栄 → 金山 | 御器所・名古屋・栄 | 吹上・国際センター・金山 | 6 | 出る |
| 6: 名古屋 → 栄 → 金山 → 新瑞橋 → 御器所 → 八事 | 栄・新瑞橋・御器所 | 金山・西高蔵 | 5 | 出ない |
5番は御器所から名古屋まで桜通線に乗るので、途中の吹上と国際センターを通ります。表示上は出てこない通過駅が効いてくるので、手で数えると間違えやすいところです。
乗換駅と判別駅は集合の和を取っているので、金山で乗り換えた場合も1駅として数えます。
一方、乗換については公式に「3回以内なら」とあるので、3回を超えるルートは候補から外しています。
Next.js と FastAPI を Vercel の1プロジェクトに載せる
最初はバックエンドを Render に置いていました。無料プランはしばらくアクセスがないとスリープするので、初回アクセスで1分近く待たされます。そのため、3秒以上応答がなければ「サーバーを起動しています」と出す画面をわざわざ作っていました（コードにはいまも残っています）。
これをやめて、FastAPI を Vercel の Python Serverless Function として同じプロジェクトに入れました。必要だったのは次の3つです。
1. api/index.py を入口にする
from .main import app as fastapi_app
app = fastapi_app
2. vercel.json で /api/* をすべてそこに流す
{
"rewrites": [
{ "source": "/api/(.*)", "destination": "/api/index.py" }
]
}
FastAPI 側のルートは /api/stations のように /api 付きで定義しておきます。
3. ローカル開発では Next.js の rewrites で uvicorn に転送する
const nextConfig: NextConfig = {
async rewrites() {
if (process.env.NODE_ENV === "development") {
return [
{ source: "/api/:path*", destination: "http://127.0.0.1:8000/api/:path*" },
];
}
return [];
},
};
フロントからは本番でもローカルでも fetch("/api/calculate?...") と書くだけで済み、CORSも気にしなくてよくなりました。requirements.txt は fastapi と uvicorn の2行だけです。
移行していちばん良かったのは起動の速さです。Render のときと比べて圧倒的に早く、開いてすぐ駅を選べるようになりました。
課題
- 乗換回数は「路線名が変わった回数」で数えている。公式ページには数え方の細かい定義までは書かれていないので、ここは自分の解釈。たとえば名城線と名港線は別路線として扱っているので、金山をまたいで直通する場合も乗換1回と数えている
- 探索中に経路をリストでコピーしているので、もっと大きな路線網だとメモリが厳しい
- 対応しているのは地下鉄だけで、市バスや他社線との連絡定期は未対応
- 金額は1ヶ月と6ヶ月だけで、3ヶ月は未対応
今後は、駅の選び方をもっと分かりやすくしたいです。いまは路線ごとに並んだ駅名のボタンを押すか、駅名で絞り込んで選ぶ形ですが、路線図を表示して、図の上の駅を直接押して選べるようにしたいと考えています。
おわりに
初めての個人開発でした。かなりAI頼りで、いわゆるバイブコーディングになりましたが、満足のいくものができました。自分が「ほしい」と思ったものをすぐ作れる環境は、すごく楽しいです。
コーディング面の勉強も頑張ります……。
本アプリは個人が作った非公式ツールです。実際に定期券を買うときは、必ず交通局の窓口で確認してください。