| 発刊日 | 2005年12月26日 |
|---|---|
| 定価 | 本体2,200円＋税 |
| 頁数 | 208頁 |
| 造本 | A5 |
| ISBN | ISBN4-86043-099-9 |
| 発行 | （株)エヌ・ティー・エス |
| 問い合わせ |
(有)アイトップ TEL:0465-20-5467 E-mail:ktl@r4.dion.ne.jp フォームでのお問い合わせはこちら |
| 監修 |
著 鉄道総合技術研究所 運転システム研究室（執筆者全4名） |
| 編集委員 |
［著者―(財)鉄道総合技術研究所運転システム研究室］ 富井規雄（とみい・のりを） 1978年京都大学大学院工学研究科情報工学専攻修了。同年日本国有鉄道入社。本社運転局，東京システム開発工事局等を経て，1987年より(財)鉄道総合技術研究所。現在，同所輸送情報技術研究部長。鉄道のスケジューリング・アルゴリズムの研究に従事。京都大学博士（情報学）。電気通信大学大学院情報システム学研究科客員助教授。主な著書：『鉄道とコンピュータ』（共立出版），『鉄道システムへのいざない』（共立出版），『列車ダイヤのひみつ』（成山堂書店）など。 福村直登（ふくむら・なおと） 1988年早稲田大学大学院理工研究科工業経営学専門分野修了。同年(財)鉄道総合技術研究所。現在，輸送情報技術研究部運転システム研究室室長。鉄道輸送計画作成支援システム，および計画作成アルゴリズムの研究開発に従事。 坂口 隆（さかぐち・たかし） 1987年日本国有鉄道中央鉄道学園機械科卒業。同年(財)鉄道総合技術研究所。1999年電気通信大学大学院電気通信学研究科情報工学専攻修了。現在，同所輸送情報技術研究部運転システム研究室主任研究員。鉄道のスケジューリング・アルゴリズムの研究に従事。東洋大学情報工学科非常勤講師。 平井 力（ひらい・ちから 1996年東京工業大学大学院情報理工学研究科数理・計算科学専攻修士課程修了。同年(財)鉄道総合技術研究所。現在，同所輸送情報技術研究部運転システム研究室副主任研究員。鉄道に関するシミュレーションモデル，スケジューリング・アルゴリズムの研究に従事。 |
| 趣旨 |
【本書の特徴】 (財)鉄道総合技術研究所でつちかってきたノウハウをもとに、鉄道輸送において出現する問題に対して、その問題のとらえ方（モデル化）、そして、アルゴリズムの設計の仕方の両方に対する記述を行なう。 |
発刊にあたって
はじめに 「段取り」という言葉がある。「事の順序・方法を定めること」という意味である（広辞苑第五版）。身の回りにおいても，事の順序や方法を決めなければならないことは多い。朝起きてから出かけるまでにやるべきことの順序，料理を手際よく作る順序など。会社での仕事の順序もそうだし，工場でものを作る時も段取りが重要である。車の製造工場では，どの部品をどういう順序で取り付けるのかを決めることは基本であるし，あるいは，製鉄所などでも，入念に作業の段取りをしておくことが必要である。さらには，病院の看護婦さんの勤務割の段取りなどの人の勤務に関する段取りもある。 それらの中でも，鉄道の運行は，段取りそのものだと言っていいだろう。電車を運転するには，時刻や番線，どの駅に停まるかなどを決めておかなければならない。その他にも，車両をどういう順番で使うのかとか，運転士が出勤してからどの列車をどこまで運転するのかなどの段取りも，あらかじめきちんと作っておかなければならない。 本書は，鉄道を題材として，その中の段取りである各種の計画（運行計画）を作成するアルゴリズムについて解説する。広い意味で，スケジューリングアルゴリズムと呼ばれる範疇に属するアルゴリズムである。 3章で詳しく説明するが，実は，現時点では，鉄道の運行計画はほぼすべて人手で作られている。コンピュータも使われるようになってきているが，あくまでも人間を補助するだけの存在にすぎない。しかし，鉄道会社では，今後，より良質でより効率的な運行計画をよりタイムリーに提供していくことを目的として，その作成に要する労力と時間を軽減することが強く望まれている。要は，運行計画を自動的に作成するアルゴリズムがほしい，ということになる。本書では，運行計画を自動的に作成するアルゴリズムに関して，これまで（財）鉄道総合技術研究所で行なってきた研究成果を中心に解説を行なう。 鉄道に限ったことではないが，現実の問題は非常に複雑である。教科書に載っている手法そのままで解けることはめったにない。そもそも，条件や目的をどのように設定するか，問題をどのように捉えるか（モデル化）すら，決して当たり前のことではない。モデル化の後，アルゴリズムを考えることになるが，膨大な規模の組合せ問題を効率的に解くアルゴリズムが求められる。これも非常に難しい。本書では，鉄道の運行計画という非常に具体的な問題を題材にして，モデル化にあたっての考え方とアルゴリズム設計の考え方を述べている。また，それだけでなく，鉄道の運行にかかかる業務の仕組みについても，あえて詳しく述べている。それらの理解は，モデル化，アルゴリズムの設計に欠かせないと筆者らは信じるからである。 本書は，以下のように構成されている。 2章の「鉄道の輸送計画」と3章の「輸送計画作成・運行管理アルゴリズムの高度化」では，それぞれ，鉄道における輸送計画業務の概要と，それに対する自動作成アルゴリズム等を含む高度化への期待の背景とその難しさ等について解説する。この部分は，鉄道の業務の内容とその背景の説明である。 4章の「アルゴリズム概論－簡単に解ける問題，簡単に解けない問題」では，後段への導入として，いわゆる組合せ最適化問題の難しさについて述べる。「NP困難」についても，ごく平易に説明する。5章の「組合せ最適化問題に対するアルゴリズム」では，メタヒューリスティクス等の組合せ最適化問題に対するアルゴリズムの概要を述べている。4章，5章は，鉄道と直接の関係はなく，ごく一般的な話題となっている。この種の話題に始めて触れる人にもご理解いただけるように，非常にわかりやすく書いたつもりである。 6章から9章は，本書の中心となる部分で，2章，3章の鉄道業務に関する知識と，4章，5章のアルゴリズムに関する知識とを組み合わせた鉄道のスケジューリング問題に対するアルゴリズムの開発への取組みについて，具体的な研究事例の内容を詳しく紹介しながら解説を試みている。そして，その中では，単に結果を紹介するのではなく，モデル化を中心に，なぜそのようなアルゴリズムを考える必要があったかについて，その背景とともに，かなり丁寧に解説したつもりである。 10章では，残された課題に言及する。残念ながら，6章から9章のアルゴリズムですべての課題が解決したわけではない。まだまだ解決すべき課題が残されている。それらの課題と解決の方針について解説する。 筆者らが想定する本書の読者は，第一には，鉄道の輸送計画にかかわるシステム開発に興味を持っておられる方々である。しかし，鉄道以外の業種のスケジューリングアルゴリズム，最適化アルゴリズムに興味をお持ちの方にも参考にしていただけると考えている。さらに，匠たちのノウハウがどのようにコンピュータに組み込まれようとしているのかに興味をお持ちの方や，また，広く一般の鉄道ファンの方にも楽しんでいただけると考えている。 著者一同
書籍・DVDの内容
目次 はじめに 鉄道のスケジューリングアルゴリズム 1.1 鉄道のスケジューリング 1.2 本書で取り上げるアルゴリズム 車両運用計画の作成 乗務員運用計画の作成 駅構内作業計画の作成 運転整理案の作成 鉄道の輸送計画 2.1 輸送計画と運行管理 2.2 輸送計画 輸送計画とは 輸送計画の作成の手順 列車ダイヤ ダイヤ図 基準運転時分と時隔 車両運用計画 乗務員運用計画 構内作業計画 基本計画と実施計画 輸送計画の伝達 2.3 運行管理 運行管理とは？ 運行管理の歴史 運転整理とは？ 運転整理の難しさ 運転整理の支援 コラム「輸送計画と運行計画，輸送管理と運行管理」 輸送計画作成・運行管理アルゴリズムの高度化 3.1 輸送計画作成システムと運行管理システムの現状 列車ダイヤ作成システムの現状 システム化の効果 運行管理システムの現状 3.2 輸送計画作成・運行管理システムの機能高度化への要望 機能の高度化の背景 何を自動化するのか？ 輸送計画の自動作成アルゴリズムの研究状況 運行管理の自動作成アルゴリズムの研究状況 アルゴリズム概論――簡単に解ける問題，簡単に解けない問題 4.1 簡単に解ける問題と簡単に解けない問題の例 ケーニヒスベルクの7つの橋 グラフ理論 一筆描き 4.2 NP完全，NP困難――最も難しい問題 世の中の問題を難しさで分類したい：PとNP 未解決の問題 P＝NPか？ NP完全 NP困難 NP困難問題へのアプローチ コラム「巡回爆弾処理人問題」 組合せ最適化問題のアルゴリズム概論 5.1 メタヒューリスティクス 局所探索法 局所探索法の改善 5.2 遺伝的アルゴリズム 5.3 制約論理プログラミング 探索アルゴリズムとモデル化 制約充足問題 制約論理プログラミングとは 制約論理プログラミングの解探索アルゴリズム 5.4 整数計画法 数理計画問題における整数計画問題の位置づけ 線形計画問題と線形計画法 線形計画問題と整数計画問題 整数計画法 まとめ 車両運用計画の作成 6.1 車両運用計画とは 車両運用計画作成の必要性 列車ダイヤと車両運用計画 仕業・行路と交番 車両運用計画作成時の制約条件 車両運用計画の評価基準 車両運用計画のバリエーション 車両割当て計画 6.2 車両運用計画の自動作成 従来の研究例 車両運用計画のモデル化 車両運用計画作成問題と巡回セールスマン問題 車両運用計画作成問題に対するアルゴリズムの提案 乗務員運用計画作成 7.1 乗務員運用計画とは 基本計画と実施計画 行 路 乗務割交番 乗務員運用計画の作成条件 7.2 現状の乗務員運用計画作成の流れ 計画部門における作業 現業機関（区所等）における作業 7.3 乗務員運用計画のシステム化 現状の問題点と自動作成システムのメリット 乗務員運用計画作成システムの前提条件 乗務員運用計画作成システムの自動作成機能 7.4 行路計画作成問題 行路計画作成問題とは 行路計画の評価基準 行路計画作成問題の計算モデル 乗務行路作成問題を集合被覆問題として解く例 集合分割問題としてのモデル化 7.5 集合被覆問題，集合分割問題の解法 7.6 乗務割交番作成問題 乗務割交番作成問題とは 乗務割交番作成問題のモデル化 制約論理プログラミング 7.7 サイクル分割問題の制約論理プログラミングによる解法 定式化 解 法 駅構内入換計画のアルゴリズム 8.1 駅構内入換計画とは 駅構内入換計画 駅構内入換計画の意義 構内入換計画の制約 構内入換計画の評価基準 8.2 スケジューリング問題とそのアルゴリズム スケジューリング問題の例 ジョブショップスケジューリング問題 ジョブショップスケジューリング問題に対するアルゴリズム 選択グラフ（disjunctive graph） 8.3 有限資源プロジェクトスケジューリング問題としての駅構内入換計画 有限資源プロジェクトスケジューリング問題 有限資源プロジェクトスケジューリング問題としての駅構内入換計画作成問題 8.4 問題に対するアプローチ――基本的考え方とPERT 基本的考え方 PERT：Program Evaluation and Review Technique 8.5 確率的局所探索とPERTを組み合わせた駅構内入換計画作成アルゴリズム アルゴリズムの全体構成 初期解生成 近傍探索 評 価 選 択 8.6 実行結果 8.7 おわりに コラム「右手にコーヒー，左手にバター」 運転整理案作成アルゴリズム 9.1 運転整理とは ダイヤ変更の手段 運転整理の手順 運転整理の難しさ 運転整理支援システムの現状と問題点 解決すべき課題 9.2 運転整理案の評価 運転整理の評価に関する従来の研究 利用者の不満による運転整理案の評価 利用者の不満の定義 9.3 利用者の不満を最小にする運転整理案作成アルゴリズム 基本的考え方と全体構成 列車運行ネットワーク アルゴリズムの詳細 アルゴリズムの実行例 実線区への適用例 9.4 運転整理支援の高度化に向けて 今後の課題 作成範囲を明確に決めることが難しい 計画作成の粒度――どこまで細かい事情を考えるか？ 相互に関連し合う輸送計画 仕事を変える！ 評価の方法 おわりに 索引
