乗り継ぎ（乗り換え）検索のこんな使い方 2
本「列車乗り継ぎ検索（乗り換え検索）の基礎基本」で、列車の乗り継ぎ（乗り換え）検索アルゴリズムの基礎基本を紹介させていただきました。“乗り継ぎ（乗り換え）検索”は本来、“乗り換え案内”に用いるためのものですが、それ以外に“こんな使い方もあるよ”というようなものを３つほど不定期で紹介していこうと思います。これは、その第2回目です。
その2 最終列車案内
最終列車案内には２つのアプローチがあります。1つ目は単一到着駅アプローチです。駅Aがあって、各駅を出発して当日中にAに到着できる最も遅い列車を各駅毎に求めていきます。
2つ目は単一出発駅アプローチです。駅Aがあって、Aを出発して当日中に各駅に到着できる最も遅い列車を各駅毎に求めていきます。
ここでは、需要が高いと思われる単一出発駅のアプローチを取り上げてみたいと思います。これ以降、路線を西武鉄道池袋線、ダイヤを2025年3月15日改正の平日とし、出発駅を池袋駅として西武秩父駅までの各駅の最終列車を求めることを具体例として、最終列車を求める手法の一つを紹介していきます。
単一出発駅でのアプローチ
各駅毎に順番に最終列車を求めていくのがシンプルで確実ですが、乗り継ぎ（乗り換え）検索を行うアルゴリズムは単一始点最短経路問題を解いているので、これを利用する方法もありそうです。以降、この方法で最終列車を求めていくこととします。
1. 池袋駅から所沢・飯能・西武秩父方面への最終列車の発車時刻を発車希望時刻とし、出発起点で池袋駅出発西武秩父駅到着で乗り継ぎ探索する。
通常の検索では、西武秩父駅が基点駅となって確定した時点で計算を打ち切りますが、ここではすべての駅を確定させて単一始点最短経路問題を解ききるのがポイントです。当日中に西武秩父駅まで到達することができなかった場合は、そこで計算を打ち切ることになります。
池袋駅の最終列車は 0:18発保谷行き各駅停車です。これから他の列車への乗り継ぎはできないので、保谷駅までの駅の到着時刻が確定します。これらは椎名町～保谷間各駅への池袋駅発最終列車の到着時刻になります。
[各停 保谷行 0:18] 椎名町～保谷
2. 1.で探索した列車のひとつ前の池袋駅所沢・飯能・西武秩父方面の列車の発車時刻を発車希望時刻とし、出発起点で池袋駅出発西武秩父駅到着で乗り継ぎ探索する。
0:18発保谷行き各駅停車の一つ前は 0:14発小手指行き準急です。椎名町～保谷間の最終列車は既に確定しているので、新たに確定したひばりヶ丘～小手指間各駅の到着時刻が池袋駅発最終列車の到着時刻になります。
[準急 小手指行 0:14] ひばりヶ丘～小手指
3. 2.の手順を繰り返します。
次に新たな駅が確定するのは 0:00発飯能行き特急むさしで、入間市、飯能、の各駅の到着時刻が池袋駅発最終列車の到着時刻になります。
[特急むさし 飯能行 0:00] 入間市、飯能
この 0:00発飯能行き特急むさしは所沢駅で飯能行き各駅停車に乗り継ぎができます。新たに入間市を除く狭山ケ丘～元加治間の各駅が確定します。
[特急むさし 飯能行 0:00] （所沢駅 飯能行各停接続）狭山ケ丘～元加治（入間市を除く）
次に新たな駅が確定するのは 23:00発飯能行き特急むさしで、飯能駅で吾野行き各駅停車に乗り継ぎができて新たに東飯能～吾野間の各駅が確定します。
[特急むさし 飯能行 23:00] （飯能駅 吾野行各停接続）東飯能～吾野
次に新たな駅が確定するのは 22:30発飯能行き特急むさしで、飯能駅で西武秩父行き各駅停車に乗り継ぎができて新たに東飯能～西武秩父間の各駅が確定します。
[特急むさし 飯能行 22:30] （飯能駅 西武秩父行各停接続）西吾野～西武秩父
これで、西武秩父駅までのすべての駅への池袋駅発最終列車が確定しました。
4. 以上の結果をまとめます。
| 最終列車 | 対象降車駅 | 乗り換え |
|---|---|---|
| 特急むさし 飯能行 22:30 | 西吾野～西武秩父 | 飯能駅 西武秩父行各停接続 |
| 特急むさし 飯能行 23:00 | 東飯能～吾野 | 飯能駅 吾野行各停接続 |
| 特急むさし 飯能行 0:00 | 入間市、飯能 | |
| 狭山ケ丘～元加治 | 所沢駅 飯能行各停接続 | |
| 準急 小手指行 0:14 | ひばりヶ丘～小手指 | |
| 各停 保谷行 0:18 | 椎名町～保谷 |
単一到着駅でのアプローチ
最初に、池袋駅に所沢・飯能・西武秩父方面から到着する最終列車の到着時刻を到着希望時刻とし、到着起点で池袋駅到着西武秩父駅出発で乗り継ぎ探索します。これ以降の手順の構造は単一出発駅でのアプローチと同様です。
Discussion