connectedRoutes の経路探索 (stationapi/src/domain/route_search.rs) の
内部設計をまとめたドキュメントです。API の形、estimateArrivalTimes /
trainRoute との関係、stationsByName の到達判定については
アーキテクチャドキュメントの「乗換経路探索」
で説明しています。ここでは探索アルゴリズムそのものを扱います。
- 時刻表を持たないので、どの列車に乗るかまでは決めません。系統ごとの駅間
所要時間 (
arrival_estimationの推定値) と、種別ごとの平均待ち時間で経路を 評価します。 - 乗換案内アプリと同じく、「最速」「乗換最少」と、その中間の候補を返します。 乗換回数を自然に扱えるため、RAPTOR を採用しました。
- I/O を持たない純粋なロジックとして実装しています。網は一度構築したら
読み取り専用にし、リクエスト間で共有します (
Arc<RouteNetwork>をOnceLockに保持)。 - 探索結果では種別を 1 つに絞りません。停車駅が同じ並行種別 (快速と各停など)
は 1 つの経路にまとめ、区間ごとに乗車できる種別の一覧は、use case 層で
routeTypesと同じ関数を使って作ります。
RAPTOR (Round-bAsed Public Transit Optimized Router、Delling ら 2012) は、 公共交通向けの経路探索アルゴリズムです。
- ラウンド k では、「ちょうど k 本目の列車に乗った時点」での各駅の最良値を 求めます。
- 優先度付きキューは使わず、路線 (パターン) の停車駅の並びを端から順に 走査します。
- 1 ラウンドで走査するのは、前のラウンドで値が改善した駅 (marked) を通る パターンだけです。
- ラウンド k での目的地の値は「k 本以内の乗車で到達できる最良値」なので、 ラウンドを進めるだけで所要時間と乗換回数のパレート解が得られます。
| 元の RAPTOR | この実装 |
|---|---|
| ラベルは到着時刻 | ラベルは評価値 (秒)。出発地では 0 |
| 時刻表から、乗車できる最も早い便 (trip) を探す | 便は探さず、乗車駅で「基準値」を計算する (走査) |
| 待ち時間は時刻表から決まる | 乗車ごとに、種別の平均待ち時間を加える |
| 駅間の徒歩連絡がある | 同じ駅グループ内の乗換だけを扱い、徒歩 3 分を加える |
| 便ごとに進行方向がある | パターンは片方向の並びだけを持ち、逆方向は所要時間が上下で同じとみなして求める |
評価値は次の合計です。
| 項目 | 値 | 定義 |
|---|---|---|
| 乗車時間 | arrival_estimation の推定値 (停車時間・通過を含む) |
Pattern::arrival / departure |
| 乗車ごとの待ち時間 | 特急・新幹線 (kind 4) 15 分 / 急行・新快速 (kind 3, 5) 5 分 / その他 3 分 |
boarding_wait_seconds |
| 乗換の徒歩時間 | 3 分 (2 本目以降の乗車時のみ) | TRANSFER_WALK_SECONDS |
待ち時間は「運転間隔の半分」を見込んだ値です。これを加えないと、本数の 少ない特急が直通で速いと評価され、東京 → 渋谷で山手線より成田エクスプレスを 勧めてしまいます。
最初の列車の待ち時間も評価値には含めます (最初にどの列車に乗るかを比べる
ために必要なため)。Journey::total_seconds は、評価値から最初の待ち時間だけを
差し引いた値です。
RouteNetwork
├── patterns: Vec<Pattern> 系統 (line_group_cd) ごとに 1 つ
├── node_by_group: 駅グループ ID → ノード番号
├── node_groups: ノード番号 → 駅グループ ID
├── stop_patterns[ノード]: [(パターン, 1 周目の位置)] 乗降できる位置のみ
└── topology: RouteTopology 同じ系統から作った、所要時間を持たない網
- ノードは駅グループ (
station_g_cd) です。乗換はノードでだけ発生します。 駅 (station_cd) は路線ごとに異なるので、駅をノードにすると乗換を辺として 表す必要が出てきます。駅グループをノードにすれば、同じノードに停車する パターン同士がそのまま乗り換えられます。 - パターンは系統 (
line_group_cd) の停車駅の並びです。
Pattern
├── line_group_id
├── nodes[pos] 位置ごとのノード (環状線でも 1 周分)
├── station_cds[pos] 位置ごとの駅 (路線ごとの駅 ID)
├── line_cds[pos] 位置ごとの路線
├── stoppable[pos] 乗降できるか (通過駅は偽)
├── arrival[q] 展開位置 q の到着時刻 (始発からの累積秒数。環状線以外は nodes と同じ長さ)
├── departure[q] 展開位置 q の出発時刻 (到着時刻 + 停車時間)
├── circular 環状線か
└── boarding_wait 乗車時の平均待ち時間 (秒)
通過駅もパターンに残します。stoppable が偽の位置では乗降しませんが、
所要時間の推定と、区間の駅グループの並び (JourneyLeg.station_group_ids) に
必要だからです。
- 呼び出し側 (
src/repository.rsのbuild_route_network) が、鉄道の系統をline_group_cdの昇順に 1 つずつ、運行順 (sst.id順) に並べたStationの リストとして渡します。バスは含みません。sst_idとline_group_cdを 持たない駅は無視します。 trim_patternで整形します。- 先頭の駅が末尾にも重複して入っている、閉じた形の環状線データは、末尾の 駅を取り除きます。
- 乗降できる駅が 2 つ未満の系統は網に含めません。
- この関数は
RouteTopologyと共有しているので、2 つの網は必ず同じ系統から 同じ形で構築されます (実データのテストで一致を確認しています)。
estimate_arrival_minutes_with_profileで、順方向・逆方向の累積時分を 秒単位の浮動小数点で保持します。乗車区間の差を取ってから整数秒へ丸めます。- 「このノードでは、このパターンのこの位置で乗降できる」という対応を
stop_patternsに登録します。
構築は全系統に対して一度行います。そのため、最初に
connectedRoutes が呼ばれたときに OnceLock に構築し、isolate が生きている
間は使い回します。
環状線では、arrival / departure に2 周分 + 始点に戻る 1 駅
(2 * len + 1 要素) を並べます。展開位置 q の駅は nodes[q % len] です。
nodes: A B C D (len = 4)
展開位置 q: 0 1 2 3 4 5 6 7 8
駅: A B C D A B C D A
こうしておくと、継ぎ目をまたぐ乗車 (D → A → B) も配列の差
arrival[5] - departure[3] で計算できます。1 周以上乗り続けることは、
走査の中で禁止しています (走査)。
labels[0][出発地] = 0、それ以外は UNREACHED
best[出発地] = 0
best[目的地] = bound ← 目的地での枝刈りの上限
marked = {出発地}
for round in 1..=MAX_RIDES (6):
marked が空なら終了
1. marked の各ノードについて stop_patterns を引き、
パターンごとに、改善した位置の最小値 lo と最大値 hi を記録する (ranges)
2. 走査対象のパターンを番号順に並べ、それぞれを
前向きに lo から末尾まで
後ろ向きに hi (環状線は hi + len) から先頭まで
走査する
3. このラウンドで改善したノードを次の marked にする
labels[round] = このラウンドの値 (前ラウンドの値を複製してから更新したもの)
labels[round]は前ラウンドの値を複製してから更新するので、常にlabels[round][v] <= labels[round - 1][v]が成り立ちます。rangesとtouchedは探索ごとに 1 回だけ確保します。rangesは パターンを走査するときにその分だけ初期値に戻し、touchedはラウンドの 終わりに空にします。- 乗換の徒歩時間は、ラウンド 1 では 0、ラウンド 2 以降では 3 分です。
パターンを一方向にたどりながら、各位置で「降車」と「乗車」をこの順に 処理します。
乗車中の基準値。前向きの走査で位置 b から乗車したときの基準値を
base = labels[round-1][nodes[b]] + 徒歩 + 待ち時間 − departure[b]
と定義すると、位置 q で降車したときの値は
base + arrival[q]
= labels[round-1][nodes[b]] + 徒歩 + 待ち時間 + (arrival[q] − departure[b])
になります。arrival[q] − departure[b] がちょうど乗車時間なので、降車時の
計算は足し算 1 回で済みます。元の RAPTOR で「乗車できる最も早い便を探す」
処理を、この基準値で置き換えています。
乗車位置の更新。走査中に、前ラウンドで到達済みの位置に来たら、そこから
乗車した場合の基準値 candidate を計算します。今の base より小さければ、
そこから乗車したことにします。基準値が小さいほど、その先のどの駅でも降車時の
値が小さくなるので、比較は基準値だけで十分です。禁止集合 (banned) の照合は
ハッシュの参照を伴うので、乗車位置を更新すると得になる場合にだけ行います。
1 つの位置での処理順
-
環状線で、乗車位置から 1 周 (
len) 以上進んでいたら乗車中の状態を 解除します (1 周して同じ駅に戻るような乗車はしないため)。 -
通過駅 (
stoppableが偽) なら何もしません。 -
乗車中なら降車時の値
base + arrival[q]を求め、次の条件をすべて満たす 場合に記録します。- このノードの全ラウンドを通じた最良値
best[node]より小さい (local pruning) - 目的地の最良値
best[target]より小さい (target pruning) - 目的地で
viaLineIdが指定されている場合は、その路線の駅に到着している
記録するのは
current[node]、best[node]、親のLegRef { pattern, board, alight }、改善フラグです。 - このノードの全ラウンドを通じた最良値
-
前ラウンドでこのノードに到達していれば、ここから乗車し直すかどうかを 検討します。
降車を乗車より先に処理するので、ある位置で乗車して同じ位置で降車する
(乗車時間 0 の) 区間はできません。また、乗車は前ラウンドの値 (previous)
からしか行いません。同じラウンドで到達した値から乗車すると、乗車本数を
正しく数えられなくなるためです。そのため、このラウンドで降車した駅から、
同じラウンドのうちに別の列車へ乗り継ぐこともありません。
後ろ向きの走査。駅列を逆順にした推定値を別に構築し、その累積時分を 使います。上りと下りを対称と仮定して順方向の出発・到着を入れ替える処理は 行いません。区間の通過路線に応じた処理は「所要時間と運行条件」を参照してください。
走査範囲。前向きの走査は改善した位置の最小値 lo から、後ろ向きの走査は
最大値 hi から始めます。それより手前には前ラウンドで改善した駅がなく、
乗車できる位置がないためです。環状線の後ろ向きの走査は 2 周目の同じ駅
(hi + len) から始め、継ぎ目を逆方向にまたぐ乗車も拾えるようにしています。
best[target] を bound で初期化しておくと、bound 以上の値でしか目的地に
到達できない経路は、途中のノードでも記録されなくなります。初回の探索では
上限を設けず (UNREACHED)、代替経路の再探索では許容範囲 (score_limit + 1)
を渡して、どのみち提示しない遠回りを探索中に刈り込みます。
各ラウンドでの目的地の値を確認し、次の条件をすべて満たすラウンドだけを 結果に採用します。
- 前のラウンドより値が小さい (乗車を 1 本増やしたことで速くなった)
- 「値 + 乗換 1 回につき 5 分 (
TRANSFER_RANK_SECONDS)」が、それまでに 採用したどのラウンドよりも小さい - 下で説明する経路の復元に成功する
2 つ目は、1 分縮めるために乗換を増やし続けるような経路を除くための条件です。
採用したラウンドは、reconstruct で親をたどって区間のリストに戻します。
前のラウンドから引き継いだだけの値には親がないので、親が記録されている
ラウンドまで下がってから親をたどり、乗車駅のノードに移って 1 ラウンド
下がる、という処理をラウンド 0 まで繰り返します。最後に出発地まで戻れなかった
経路は捨てます。
パレート解には「最速」と「乗換最少」の系列の経路しか含まれません。それ以外の 経路は、区間を禁止して再探索することで集めます (Yen の k 最短経路 アルゴリズムの簡略版)。
pareto = raptor(禁止なし, 上限なし)
queue = pareto の各経路について、区間を乗車時間の長い順に 1 つずつ禁止した集合
while queue から禁止集合を取り出せる間:
探索回数が MAX_SEARCH_RUNS (8) 以上なら終了
for 経路 in raptor(禁止集合, 上限 = score_limit + 1):
許容範囲外・逆戻り・既出のいずれかなら捨てる
この経路の区間をさらに 1 つずつ禁止した集合を queue に追加する
alternatives に追加する
禁止集合は (パターン, ノード) の組の集合で、「このパターンに、このノード
から乗車してはならない」ことを表します。1 つの区間を禁止するときの対象は
次のとおりです。
- パターン: 区間の乗車駅と降車駅の両方に停車するパターン (並行する快速・ 各停などを含む)
- ノード: 区間の乗車駅から降車駅までの間で、元のパターンが停車するすべての駅
乗車駅だけを禁止すると、「別の列車で 1 駅進んでから同じ新幹線に乗る」 といった、実質的には同じで乗換だけが増えた経路が代替経路として出てきて しまいます。
| 条件 | 理由 |
|---|---|
| 順位の値が「最良値 × 1.15 + 15 分」を超える | 大きな遠回りは提示しない |
| 乗車回数が、パレート解の最多乗車回数 + 1 を超える | 乗換が多すぎる |
別々の区間で同じ駅グループに停車する (revisits_station_group) |
区間を禁止すると「1 駅戻って乗り直す」経路が出てくるため |
乗車駅・降車駅の駅グループと路線が、既出の経路と同じ (journey_key) |
種別が違うだけの同じ経路のため |
revisits_station_group は、乗換駅 (前の区間の降車駅 = 次の区間の乗車駅) と
通過駅を数えません。急行で通過した駅に先の駅から戻るのは実際にある乗り方
ですし、1 つの区間の中で同じ駅に 2 回停車するのも実在する運行 (大江戸線の
都庁前) だからです。初回探索のパレート解にはこの除外を適用しません。適用
すると、逆戻りでしか到達できない駅が、stationsByName では「行ける駅」と
して返るのに、経路が 0 件になってしまうためです。
パレート解は必ず残し、残りの枠を代替経路で埋めます。最後に「評価値 + 乗換
1 回につき 5 分」の小さい順、同点なら乗車回数の少ない順に並べ、最大 6 件を
返します。API はこの評価を保ち、各区間の recommendedGroupId と経路の
totalSeconds を返します。種別一覧の各停で再評価する処理はありません。
ArrivalTime は (totalSeconds, 乗換回数)、TransferCount は
(乗換回数, totalSeconds) で安定ソートします。候補の集合は変えません。
初回のパレート解は保持します。代替候補は最大 8 回の異なる禁止集合で探索し、
全候補を評価してから最大 6 件に絞ります。厳密な k 最短経路の列挙ではありません。
探索、枝刈り、順位付けには ETA と同じ線路距離と routing_estimation_params
を使います。trainRoute の Legacy と ETA の較正値は変更しません。
通過駅がない区間で各停速度を使う ETA の規則も維持します。
区間によらず速度が同じ系統は、順方向と逆方向の累積時分から乗車時間を引きます。 通過路線が一つの系統では、各停のラベル、通過前の候補、通過後のラベルを 単調キューで保持し、O(n) で正確に走査します。通過路線が複数の系統では、区間ごとの通過路線集合について 累積時分を一度ずつ構築し、区間時分表を作ります。探索時には表だけを参照します。 同じ系統の複数の乗車位置を保持し、全系統の累積時分だけで乗車位置を一つに 絞ってしまう処理を避けます。通常系統と通過路線が一つの系統は O(n)、通過路線が複数の系統は O(n²) の走査です。 区間時分表の容量は O(n²)、構築は O(n² + p × n) です。p は実際の区間に現れる 通過路線集合の数です。待ち時間は系統の先頭ではなく乗車位置で決めます。
data/route_service_rules.csv は種別または系統単位の運行制約を持ちます。
requires_timetable の系統は、時刻表を入力しない探索の前に除きます。
S-TRAINに限らず、既存の全国の種別・系統を確認し、公式資料で曜日・時間帯・
運転日が限定されると確認できた列車にも同じ基準を適用します。
対象と根拠は 運行制約の確認記録 に記載しています。
同じ快速でも池袋発着の188・620以外の系統にはその規則を適用しません。
「ライナー」412は複数社で共有するため、965・1018・1019を個別に登録します。
手動選択用の種別一覧には残します。これは検索日時のない探索に対する暫定制約で、
運行時間内の便を検索して推薦する機能ではありません。
東武のFライナーや各社の快速急行を名称だけで一律に除外する処理はありません。
各行に種別名・判断理由・確認日・出典を残し、検証時に種別IDと名前を照合します。
data/route_stop_rules.csv は格納順と逆順の乗車・降車許可を持ちます。
練馬の平日 S-TRAIN は下りの降車だけを許可します。根拠は CSV の source
に記載します。未登録の運行条件を推測して追加する処理はありません。
両 CSV は data_validator で参照 ID、重複、待ち時間を検査します。
同じ入力に対して常に同じ結果を返すよう、次の順序を固定しています。
- 網に載せる系統の順序: 呼び出し側が安定した順序 (系統番号順) で渡す
- 1 ラウンド内でのパターンの走査順: パターン番号順 (
touched.sort_unstable()) - 値が同じ場合は、先に記録したものを残す (
<のときだけ更新する) - 次ラウンドの
marked: ノード番号順 - 並べ替えは安定ソートで行い、同点の場合は乗車回数、次に発見順で並べる
connectedRoutesの並べ替えも安定ソートで、キーが同じ経路は探索時のおすすめ順を保つ
これは search_is_deterministic テストで確認しています。
| 定数 | 値 | 意味 |
|---|---|---|
TRANSFER_WALK_SECONDS |
180 | 乗換 1 回あたりの徒歩時間 |
MAX_RIDES |
6 | 1 つの経路で乗る列車の最大本数 (乗換 5 回まで)。ラウンド数の上限でもある |
MAX_JOURNEYS |
6 | 返す経路の最大数 |
MAX_SEARCH_RUNS |
8 | 代替経路を探すための探索回数の上限 (初回の探索を含む) |
ALTERNATIVE_SLACK_NUMERATOR / DENOMINATOR |
115 / 100 | 代替経路の許容倍率 |
ALTERNATIVE_SLACK_SECONDS |
900 | 代替経路の許容加算時間 |
TRANSFER_RANK_SECONDS |
300 | 順位付けで乗換 1 回ごとに加える重み (所要時間には含めない) |
ALTERNATIVE_EXTRA_TRANSFERS |
1 | 代替経路に許す乗車回数の上乗せ分 |
MAX_RIDES は、estimateArrivalTimes / trainRoute に渡す legs の上限にも
使っています。
- 時刻表がない: 実際の接続 (何分待つか)、終電、季節運行の臨時列車は 考慮しません。待ち時間は種別から見積もった値です。
- 駅グループをまたぐ徒歩連絡はない: 徒歩連絡のデータを持たないので、 別の駅グループへ歩いて乗り換える経路は扱いません。
- 乗換の徒歩時間は一律 3 分: 駅ごとの乗換時間の違いは反映しません。
- バスは対象外: 網に含めるのは鉄道の系統だけです。
- 代替経路は網羅的ではない: 探索回数に上限があるため、k 最短経路を 厳密には求めません。
単体テストは route_search.rs の tests モジュールにあり、小さな人工の網を
使って次の点を確認しています。
| テスト | 確認すること |
|---|---|
finds_direct_route_in_both_directions |
前向き・後ろ向きの走査 |
transfers_at_shared_station_group |
駅グループでの乗換 |
unknown_or_identical_endpoints_return_nothing |
網にない駅や、出発地と目的地が同じ場合は 0 件 |
cannot_board_or_alight_at_passed_station |
通過駅では乗降しない |
prefers_faster_route_and_keeps_fewest_transfers |
パレート解 |
collects_alternative_routes_through_other_stations |
代替経路 |
via_line_restricts_the_line_arriving_at_the_destination |
viaLineId |
rejects_routes_that_backtrack_through_a_visited_station |
逆戻りする経路の除外 |
collapses_parallel_train_types_into_one_route |
並行種別を 1 つの経路にまとめる |
rides_across_the_seam_of_a_circular_line |
環状線の継ぎ目をまたぐ乗車 |
search_is_deterministic |
決定性 |
sorts_journeys_by_arrival_time_or_transfer_count |
到着の早い順・乗換の少ない順 |
breaks_arrival_ties_by_transfers_and_transfer_ties_by_arrival |
並べ替えで同点になったときの扱い |
同じモジュールには、RouteTopology による到達判定 (stationsByName 用) の
テストもあります。
| テスト | 確認すること |
|---|---|
reachable_stations_follow_transfers_and_skip_passed_stations |
乗換でたどり、通過駅は含めない |
cannot_arrive_at_a_junction_on_the_branch_that_starts_there |
支線の分岐駅に、その支線で着いたことにしない |
cannot_arrive_at_the_origin_station_group |
出発地の駅グループは到達先として扱わない |
reachability_matches_search_on_a_ring_with_branches |
到達判定と探索の結果が一致する |
topology_built_from_route_stops_matches_the_one_inside_the_network |
2 つの網が同じになる |
reachable_stations_stop_after_the_ride_limit |
乗車本数の上限で打ち切る |
実データでの確認 (東京 → 渋谷が乗換なしで見つかる、三鷹 → 中目黒が乗換
ありで見つかる、2 つの網が一致する、など) は src/repository.rs のテストで
行っています。実データでの処理時間は
アーキテクチャドキュメントの「計算量」 を
参照してください。
同じ生成済み鉄道データで route_network_performance_report を実行しました。
ネイティブの debug ビルドで、5 経路を各 10 回検索した値です。
比較元は c06c728、共通処理変更後の測定対象は 4847a9 です。
Worker 上での時間を示す値ではありません。
| 実装 | 系統数 | 初回構築 | 検索の中央値 | 95 パーセンタイル |
|---|---|---|---|---|
| 比較元 | 1,342 | 987 ms | 44.2 ms | 66.3 ms |
| 共通時分・運行制約・区間走査 | 1,327 | 1,892 ms | 125.4 ms | 296.3 ms |
区間に応じた速度評価、逆方向の時分、最後まで実行する代替探索によって計算量が
増えています。単一の通過路線は単調キューで O(n) に保ち、複数の通過路線だけに
区間表を使います。構築は OnceLock で一度だけ実行します。