（書評）鉄道のスケジューリングアルゴリズム　～コンピュータで運行計画をつくる～

はじめに

　「段取り」という言葉がある。「事の順序・方法を定めること」という意味である（広辞苑第五版）。身の回りにおいても，事の順序や方法を決めなければならないことは多い。朝起きてから出かけるまでにやるべきことの順序，料理を手際よく作る順序など。会社での仕事の順序もそうだし，工場でものを作る時も段取りが重要である。車の製造工場では，どの部品をどういう順序で取り付けるのかを決めることは基本であるし，あるいは，製鉄所などでも，入念に作業の段取りをしておくことが必要である。さらには，病院の看護婦さんの勤務割の段取りなどの人の勤務に関する段取りもある。
　それらの中でも，鉄道の運行は，段取りそのものだと言っていいだろう。電車を運転するには，時刻や番線，どの駅に停まるかなどを決めておかなければならない。その他にも，車両をどういう順番で使うのかとか，運転士が出勤してからどの列車をどこまで運転するのかなどの段取りも，あらかじめきちんと作っておかなければならない。
　本書は，鉄道を題材として，その中の段取りである各種の計画（運行計画）を作成するアルゴリズムについて解説する。広い意味で，スケジューリングアルゴリズムと呼ばれる範疇に属するアルゴリズムである。
　3章で詳しく説明するが，実は，現時点では，鉄道の運行計画はほぼすべて人手で作られている。コンピュータも使われるようになってきているが，あくまでも人間を補助するだけの存在にすぎない。しかし，鉄道会社では，今後，より良質でより効率的な運行計画をよりタイムリーに提供していくことを目的として，その作成に要する労力と時間を軽減することが強く望まれている。要は，運行計画を自動的に作成するアルゴリズムがほしい，ということになる。本書では，運行計画を自動的に作成するアルゴリズムに関して，これまで（財）鉄道総合技術研究所で行なってきた研究成果を中心に解説を行なう。
　鉄道に限ったことではないが，現実の問題は非常に複雑である。教科書に載っている手法そのままで解けることはめったにない。そもそも，条件や目的をどのように設定するか，問題をどのように捉えるか（モデル化）すら，決して当たり前のことではない。モデル化の後，アルゴリズムを考えることになるが，膨大な規模の組合せ問題を効率的に解くアルゴリズムが求められる。これも非常に難しい。本書では，鉄道の運行計画という非常に具体的な問題を題材にして，モデル化にあたっての考え方とアルゴリズム設計の考え方を述べている。また，それだけでなく，鉄道の運行にかかかる業務の仕組みについても，あえて詳しく述べている。それらの理解は，モデル化，アルゴリズムの設計に欠かせないと筆者らは信じるからである。
　本書は，以下のように構成されている。
　2章の「鉄道の輸送計画」と3章の「輸送計画作成・運行管理アルゴリズムの高度化」では，それぞれ，鉄道における輸送計画業務の概要と，それに対する自動作成アルゴリズム等を含む高度化への期待の背景とその難しさ等について解説する。この部分は，鉄道の業務の内容とその背景の説明である。
　4章の「アルゴリズム概論－簡単に解ける問題，簡単に解けない問題」では，後段への導入として，いわゆる組合せ最適化問題の難しさについて述べる。「NP困難」についても，ごく平易に説明する。5章の「組合せ最適化問題に対するアルゴリズム」では，メタヒューリスティクス等の組合せ最適化問題に対するアルゴリズムの概要を述べている。4章，5章は，鉄道と直接の関係はなく，ごく一般的な話題となっている。この種の話題に始めて触れる人にもご理解いただけるように，非常にわかりやすく書いたつもりである。
　6章から9章は，本書の中心となる部分で，2章，3章の鉄道業務に関する知識と，4章，5章のアルゴリズムに関する知識とを組み合わせた鉄道のスケジューリング問題に対するアルゴリズムの開発への取組みについて，具体的な研究事例の内容を詳しく紹介しながら解説を試みている。そして，その中では，単に結果を紹介するのではなく，モデル化を中心に，なぜそのようなアルゴリズムを考える必要があったかについて，その背景とともに，かなり丁寧に解説したつもりである。
　10章では，残された課題に言及する。残念ながら，6章から9章のアルゴリズムですべての課題が解決したわけではない。まだまだ解決すべき課題が残されている。それらの課題と解決の方針について解説する。
　筆者らが想定する本書の読者は，第一には，鉄道の輸送計画にかかわるシステム開発に興味を持っておられる方々である。しかし，鉄道以外の業種のスケジューリングアルゴリズム，最適化アルゴリズムに興味をお持ちの方にも参考にしていただけると考えている。さらに，匠たちのノウハウがどのようにコンピュータに組み込まれようとしているのかに興味をお持ちの方や，また，広く一般の鉄道ファンの方にも楽しんでいただけると考えている。

著者一同