 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| No.10 2008.5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| リサーチダイジェスト | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 鉄道の運行計画に対する最適化アルゴリズムの海外研究の動向調査 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 千葉工業大学 情報科学部 情報工学科 教授 富井 規雄 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| １．はじめに | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 列車ダイヤをはじめとする鉄道の運行計画は，長年にわたって，経験を積んだベテランの頭脳によって作られてきた。しかし，近年，コンピュータ・ハードウェアの高速化，最適化アルゴリズムの進展などによって，運行計画を自動的に作成するシステムに関する研究が注目されている。 特に，近年ヨーロッパでは，上下分離，すなわち，公的機関が保有するインフラの上で，各鉄道運営会社が商業ベースで列車を運行するという図式が定着しており，そのような環境においては，運行計画を効率的に作成することと，高品質の運行計画を作成することが重要課題として認識されるようになってきた。このような事情を背景に，EC(European Commission) では，ARRIVAL（Algorithms for Robust and online Railway optimization: Improving the Validity and reliAbility of Large scale systems）と称する特別プロジェクト1 を立ち上げ，大学等に対して，運行計画の自動作成・最適化アルゴリズムの研究に対する補助を盛んに行なっている。また，これらの研究では，従来一般的であった人工知能的手法ではなく，数理計画技法と呼ばれる厳密な数学的理論にもとづいた手法を用いていることが特徴である。 日本においても，上下分離こそ行なわれていないが，ベテラン社員の退職等を背景に，運行計画作成の効率化と高品質化が求められているという事情はヨーロッパと変わらない。そのため，これらの研究の動向の調査は，日本の事業者・研究者にとっても非常に有意義であると考えられる。 本調査では，上記ARRIVAL の成果として公表されている論文を中心として，ヨーロッパ等における運行計画の自動作成アルゴリズムに関する最新の研究動向の調査・分析を行なった。 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ２．コンピュータ支援の現状 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 鉄道のスケジューリング問題に対しては，コンピュータの黎明期から研究開発が行なわれてきた。しかし，その複雑さ・難しさから，近年になって，やっと支援システムが実用になってきた程度である。 しかし，鉄道会社においては，より高品質な運行計画をより効率よく作成することが求められている。 したがって，鉄道会社は，運行計画の自動作成などのアルゴリズムが今後どの程度実用になるのかについて，強い興味をいだいているのが現状である。 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ３．調査内容 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ４．調査結果のまとめ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ４．１ 設備計画・要員計画の作成 運行計画は，鉄道会社にとっての商品そのものであるがゆえに，その会社の経営方針を反映して作成される。中長期にわたる需要予測をもとにして，どの程度のサービスレベルを達成するのかを，投資計画を念頭において決定する。 また，経営方針を反映した運行計画を実現するための前提として，設備や要員に関する計画を作成する。設備計画としては，例えば，線路の建設・増設（複々線化等），線路の改良（通過速度の向上など），駅の番線の増設，車両基地・乗務員基地の新設・統廃合，車両の新製・改良，各基地での所属編成数や所属する車両の走行範囲の決定などがありうる。要員計画としては，要員（特に乗務員）の数，乗務員の乗務範囲の決定などがありうる。 設備計画や要員計画の作成も，本来，数理計画問題として扱うことができるはずである。しかし，これらを数理計画問題として扱う研究は，現状では，ほとんど行なわれていない。その理由としては，戦略的な判断が必要とされる難しい問題であること，実現に長い時間と莫大な額の投資が必要になることとあいまって，その効果を把握することが難しいことなど，定量化が難しい要素を多く含むこと等の理由によるものと考えられる。 ４．２ 運行計画基本方針の作成：LPP 運行計画の基本方針とは，列車の運行系統（どこからどこにどういう種類 の列車を運転するか），列車の運転本数，列車種別ごとの停車駅などのことを言う。列車ダイヤの骨格と言ってもよい。 運行計画の基本方針の決定問題も，設備計画・要員計画と同様，戦略的な要素を含む業務である。これについても同様の理由で，現状では研究開発事例はそれほど多くない。例としては，ヨーロッパのネットワーク状の路線を対象として，利用者のデマンド を入力とし，利用者全員に目的駅までの輸送サービスを提供できることを前提に，列車が通るルートとルートごとの列車の設定本数と停車駅等を決定する問題（LPP : Line Planning Problem）に対する研究が行なわれている。たとえば，Caprara らによる，コストを考慮した上で，乗換なしに目的駅まで行ける利用者の数を評価値とし，それを最大とする計画を整数計画問題を解くことによって求めるという研究例がある。 ４．３ 列車計画の作成：TTP，TPP 列車計画作成問題（TTP : Train Timetabling Problem）は，利用者のデマンドと列車運行に関する物理的制約 を入力とし，利用者の満足度にかかわる指標を最大とする列車計画（具体的には，列車設定本数，各駅の停車通過区分と着発時刻，場合によって，各列車の編成両数）を出力する問題である。評価指標を出力するためには，利用者の行動を推定することが必要となり，そのために，通常，利用者の行動様式や嗜好について，何らかの仮定がおかれる。例えば，目的駅にもっとも早く到着する列車を選択する，出発駅にランダムに出現する等である。 TTP に対しては，多くの研究事例が報告されている。ヨーロッパにおいては，TTP を混合整数計画問題（MILP）として定式化するアプローチをとる研究事例が多い。たとえば，Caprara らは，ある時刻の列車の着・発事象をノードとし（着発時刻としてとりうる時刻は，ある単位で離散化しておく），列車の走行・停車をアークとするmultigraph に対して，アークに付された列車のprofit を最大にするようなアークを選び出す問題をMILP として解くアプローチを提案している。MILP とする場合，現実の列車計画作成問題に応用するにあたっては，変数の数が膨大になるため，その問題にいかに対処するかが鍵となる。 日本では，駅における番線の使用方法は比較的単純である 。従って，ほとんどの駅においては，列車がどの番線を使用するかを決めることはさほど難しい問題ではない。そのため，列車の使用番線の決定は，列車計画の一部とされる。しかし，ヨーロッパ等においては，大規模駅における番線の使用方が複雑であることに起因して，駅における番線使用計画を，列車の時刻等を決定する問題とは別個に決定しようとする試みが行なわれている。この問題を，番線使用計画問題 (TPP: Train Platforming Problem) と呼ぶ。TPP は，ある駅に対する番線以外の列車計画と駅の配線データが与えられた時に，最小停車時分や番線・進路の競合等の制約を守った上で，各列車が列車計画で定められた通りの時刻に着発できるように適切な番線を割り当てる問題となる（あるいは，着発時刻の変更を許すとする場合もある）。 さらに，近年の傾向として，列車ダイヤの頑健性に関する研究事例が多数みられるということがあげられる。頑健なダイヤとは，予期せぬ外乱が生じた場合でも，列車に遅延を生じないようなダイヤのこととして定義されている。そのための余裕時分（走行時分に対する余裕，列車間隔に対する余裕）のつけ方等に関する研究が盛んである。これは，ヨーロッパにおいては，上下分離を原則に，列車の運行をつかさどる会社が定時運行に責任を持つ（約束の定時性を守れない場合，政府等からの補助金を受け取れないばかりか，場合によっては，罰金を支払う場合もある）ことが明確になっていたことが背景にあると考えられる。 ４．４ 車両運用計画の作成：RSCP 車両運用計画 (Rolling Stock Circulation Problem: RSCP) は，列車計画（各列車に必要な両数を含む）を入力とし，検査や清掃に関する制約が与えられた時に，使用する編成の数を最小にするような仕業と交番を出力する問題である。必要に応じて，車両の分割・併合もあわせて考慮する必要がある。 与えられた列車計画に対して，列車の始終着となる駅や車両基地でFIFO (First In First Out) で列車を接続して得られる車両運用計画は，使用編成数最小となることが知られている。しかし，実際には，検査・清掃のためにある一定の折り返し時間を確保しなければならないことや駅での番線の競合を避けるために入換が必要になることもあり，常にFIFO にできるわけではない。さらに，入力として与えられる列車計画は完全なものを想定することはできないという難しさもある。すなわち，車両運用の都合で設定する回送列車については，入力として与えられる列車計画には含まれないため，車両運用計画の中であわせて作成する必要がある。また，使用編成数以外にも，仕業検査の回数や回送列車の追加をなるべく少なくしたい等の要望もある。 仕業を作成する問題は，あらかじめ多数の仕業（検査の計画も含めておく）の候補を作成しておき，すべての列車がいずれか一つの仕業にのみ含まれるような仕業の組合せを選び出す問題とみなすことができる。すなわち，集合分割問題（Set Partitioning Problem : SPP）である。 一方，この方式では，場合によっては，仕業検査周期の制約を満たすことや，仕業検査の数を最小にすることが容易でないことがある。また，仕業は，出発地と終着駅が必ずしも一致しないため，交番を作る際には，回送列車を適切に挿入するなどのやや複雑な処理が必要となる。このような事情から，仕業と交番を同時に作成しようとするアプローチも提案されている。具体的には，列車をノードとし，車両運用として接続可能なノード間にアークを設定することによって作成したネットワークに対して，検査の条件を満たし，かつ，すべてのノードを経由する巡回路を見出そうとする，巡回セールスマン問題（TSP：Traveling Salesperson Problem）に似た問題として定式化される。 日本においては，仕業と交番は，必ずセットで作成することが求められる。しかし，諸外国においては，必ずしもそうではない。交番は，仕業検査や交番検査の施行予定をあらかじめ決定しておくという意味がある。逆に言えば，列車本数や対象編成数が多く，かつ，検査を周期ぎりぎりでなく実施してもよいなどの理由で，ad hoc にその日の検査対象編成を決定することが許される場合には，交番の作成は必ずしも必要ではない。その場合，仕業（のみ）を作成する問題は，Integer Multi Commodity Flow 問題として定式化される。 ４．５ 乗務員運用計画：CPP 乗務員運用計画作成問題 (Crew Planning Problem: CPP) は，入力として列車ダイヤと車両運用計画が与えられた時に，乗務員の勤務作成にかかわる制約 を守った上で，必要乗務員の数を最小とするような行路と交番を作成する問題である。 乗務員運用計画作成問題は，問題の構造としては，車両運用計画と類似している。しかし，乗務員の行路においては，出発地と終着地が必ず一致するという相違がある。従って，行路をまず作成し，その後，交番を作成する手順とするのが自然である。 行路の作成 (Crew Scheduling) は，あらかじめ作成した行路 (duty, pairing) の集合から，すべての列車がどれか1 つ以上の行路に含まれるような行路の組合せを見出す問題（Set Covering Problem :SCP）と見なすことができる。ここで，SPP ではなくSCP となるのは，乗務員運用計画作成問題においては，ある列車が複数の行路に含まれる解が生成された場合には，1 人以外の乗務員を便乗（列車を運転しない）とできるためである。 交番の作成 (Crew Rostering) は，多数の行路を，在宅休養時間等乗務員の労働時間と休養に関する制約を守りつつ，所与の数の交番（それぞれを交番組という）に分割する問題である。評価尺度としては，交番組間の労働時間の平均化などがある。 乗務員充当計画は，みかけは，Nurse Scheduling Problem (NSP) と類似しているが，前述のように，鉄道の乗務員は交番で指定された順序で充当されていくのが原則であるため，NSP のような難しい問題とはならない。逆に言えば，毎月NSP のような難しい問題を解く必要をなくすために，交番という考え方が採用されているとも考えられる。 ４．６ 構内作業計画：TUSP 構内作業計画（Train Unit Shunting Problem: TUSP）は，列車計画と車両運用計画が与えられた時に，番線や進路の競合などの物理的な制約を守ることを前提に，入換回数などの評価指標を最小にする入換計画を作成することを目的とする。 構内作業計画に対しては，番線・引上線を資源，番線の占有を作業とみなすことによって，Job Shop Scheduling 問題の拡張であるResource Constrained Project Scheduling Problem と考え，それに対するメタヒューリスティクスを用いたアルゴリズムが提案されている。また，車両基地の入換計画を対象として，ダイヤ乱れ時における計画の再作成にも適用できることを念頭において，制約プログラミングとヒューリスティクスを組み合わせたアルゴリズムが提案されている。さらに，Freling らは，駅構内のTUSP を，番線を決定する問題，入換のルートを決定する問題 等のいくつかのフェーズに分け，それぞれに対して，整数計画法等によるアルゴリズムを提案している。 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ５．調査対象論文一覧 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|