鉄道のスケジューリングアルゴリズム
ー現状と今後の課題一
冨井 規雄
鉄道においては，列車ダイヤに代表されるように，列車の時刻，車両・乗務員の運用計画等がすべて事前に定められ，それに従って列車が運車云される．最近では，これらのスケジュールは，コンピュータによる支援システムを用いて作成されるようになってきているが，作業効率のさらなる向上等を目指して，自動作成アルゴリズムが望まれるようになっている．本稿では，鉄道におけるスケジュールの作成について，現状の実態，自動作成アルゴリズムに関する研究動向，
アルゴリズム開発にあたっての難しさ，今後さらに検討を必要とする課題等について述べる．

キーワード：鉄道，列車ダイヤ，車両運用計画，乗務員運用計画，構内作業計画，スケジューリン
グアルゴリズム，メタヒューリステイクス…l州‖…ll‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝＝‖‖‖＝‖‖‖＝‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖＝‖川‖l仙‖川＝l川‖ll川Illl…llll………‖l川‖州‖……………ll‖＝‖‖＝＝‖‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖＝‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖州‖

イヤ図）から釆ているのだが，今では，交通機関の運

1．鉄道のスケジュール

行スケジュールの意味で使われている．事実，広辞苑

鉄道は，あらかじめ定められたスケジュールに従って動く．事実，国土交通省令にも，「列車の運転は，（第5版）にも，「ダイヤが乱れる」という用例が掲載されている．

…出発時刻，通過時刻，到着時刻等を定めて行わなけ

鉄道部内では，列車ダイヤは，列車計画のことをさればならない」とある1．よって，あらかじめ定めらす．ここで，列車計画とは，列車21本1本に対して，れたダイヤに従って動かないものは，鉄道ではないと各駅の者時刻・発時刻，番線などを定めたものを言う．

いうことになる．すなわち，「スケジュールは，鉄道

JRの多くク）線区では，列車ダイヤは，15秒単位で作そのものである」と言い切ってしまっても過言ではなられる．大都市近郊の線区では，10秒や5秒単位といだろう．

なる．列車ダイヤを図表の形式で表したものが，列車では，そのスケジュールの具体的な中身はなんだろ

ダイヤ図（単にダイヤ図と呼ぶことも多い）である．

うか，あるいは，そのスケジュールは，誰がどうやっその一部を図1に示しておこう（1枚のダイヤ図には，て作っているのだろうか，自動化はされているのだろうか，されているとしたら，どのようなアルゴリズムが使われているのだろうか．そして，残された問題はないのだろうか．本稿では，次々と沸き起こるこのような■疑問に対して解説を試みてみたい．

2．鉄道のスケジュールとは
2．1スケジュールの内容一四つのスケジュール【列車ダイヤ】「ダイヤ」，あるいは，「列車ダイヤ」という言葉をお聞きになった方は多いだろう．ダイヤ改正などという言葉も広く使われる．ダイヤは，ダイアグラム（ダ
図1列車ダイヤ図（一部）とみい のりお㈱鉄道総合技術研究所〒185−8540国分寺市光町2−8−38
1鉄道に関する技術上の基準を定める省令，第99条．
2004年1月号

2列車は「停車場外の線路を運転させる目的で組成された車両をいう」と定義されるが，駅と駅の間の線路を走っている普通の電車のことだと思っていただいて差し支えない．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（33）33

24時間分の列車ダイヤが含まれるが，図1では，そ上線に入れた後，3番線に移動させる．このような作のうちの約1．5時間分を示している）．横軸が時間，業を「人換」という．構内作業計画とは，このような縦軸が駅で，時間の経過にそって動く列車の軌跡を1

車両の人換，ならびに，分割・併合，車内点検，合図，本の直線で表している．鉄道における最重要な図表で清掃など，駅で行われる作業に関するスケジュールのある．ちなみに，列車ダイヤを作る専門家をスジ屋とことをいう．これは，駅ごとに作られることになる．

呼ぶが，これは，列車ダイヤ図の列車の線を「スジ」

構内作業計画は，車両基地に対しても作る必要があ
る．これは，基地での，車両の人換，検査，清掃等のと呼ぶことに起因している．

スケジュールを定める．

【車両運用計画と乗務員運月指†一画】

さて，鉄道のスケジュールというと，列車ダイヤがまず思い浮かぶのだが，列車ダイヤ（列車計画）だけ

2．2 毎日違う列車ダイヤ一基本計画と実施計画
列車ダイヤは毎［l異なる，というと驚かれるだろう

で列車が動くわけではない．列車が動くためには，そか．今述べた匹Ⅰつの計画は，ダイヤ改正時に作られる．

こにリソースを割当てる必要がある．リソースとは，これを「基本計画」という．ダイヤ改正時に作った計車両と乗務員（運転士と車掌）を指す．列車ダイヤは，画に基づいて，毎日毎日，列車が運行されるのが原則

列車の運転区間と運転時刻を決めただけの，いわば論であるが，必ずしもそういう訳でもない．それは，臨理的なものだから，それを具現化するためには，物理

時列車の存在による．需要が多い季節には，臨時列車的な存在，すなわち，車両と乗務員の運用計画を決めを運転することがある3．あるいは，高校野球応援団

る必要がある．例えば，ある運転士がある駅に列車のような個別の団体のためにその都度仕立てられる臨Aを運転して着いたとして，では，次にその運転士

時列車もある．これらの列車を遵車云するために，基本は，どの列車を運転するのかなどを決めてやらねばな

計画の一部を変更せざるをえなくなるときがある．例らない．車両についても事情は同じである．このようえば，列車の時刻や番線を変更することがある．場合に，車両や乗務員の使用計画を定めたスケジュールのによっては，車両運用計画や乗務員運用計画についてことを，それぞれ，車両運用計画，乗務員運用計画とも，基本計画を変更することになる．もちろん，構内

いっ．

作業計画も同様である．
臨時列車の遵車云のパターンは，日々異なる．だから，【構内作業計画】

もう一つの計画が構内作業計画である．駅の中での少し大げさにいうと，列車ダイヤは，毎日異なるとい編成の移動スケジュールのことをいう．例えば，図2

うことになる．この日々の鉄道の運行計画のことを，のような配線の駅で，ある列車が1番線に到着したと「実施計画」という．

して，その折返しの列車が3番線から発車するようなさて，ある日の列車は，その日の実施計画に従って計画だったとする．利用者の便を考えて，列車の発車運転されるのだが，時として事故や災害などによってホームを方面別に統一したいというときには，このよ

列車ダイヤが乱されることがある．そのような場合にうに到着番線と発車番線が異なることが多い（復習しは，一時的に列車ダイヤ（車両運用計画等を含む）のておくと，列車の番線は列車計画で定められるわけだ
し，どの列車で折り返すかは車両運用計画で決められ

基本計画

実施計画

運転整理

臨時列車

ダイヤ乱れ

ている）．この駅では，列車は1番線から直接3番線に行くことはできない．1番線から，いったん下り引

ダイヤ改正

図3 鉄道のスケジュールの構造

図2 駅の配線の例
34（34）

3厳脅‖こいうと，こういう列車は「季節列車」と呼ぶ．
オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

変更を行って，乱れた列車ダイヤをもとに戻す．この変えた場合の輸送計画の検討など）という事情がある．

業務を運転整理という．

4．車両運用計画作成アルゴリズム

基本計画と実施計画，運転整理の関連を図3に示す．

4．1車両運用計画とは3．鉄道のスケジュールはどのように作られるか？

本稿では，鉄道の輸送計画の一つである車両運用計
画，特に，ダイヤ改正時に作られる車両運用計画（基3．1コンピュータは使われているか？

本車両道庁ほ十画）の自動作成アルゴリズムを例にとっ今説明した四つの計画だが，現時点では，これらは，て，その構造，定式化の方法，考慮すべき点などにつすべて人手で作られている．そんな馬鹿な！ とお思いて述べてみようと思う．以下では，車両運用計画といの方もおられるかもしれないが，残念ながら事実でいったときには，基本車両運用計画を指す．

ある．ただし，コンピュータが使われていない訳では

図4をご覧いただきたい．これは，列車ダイヤであない．最近では，コンピュータを使って，これらのスる．これが車両運用計画作成問題の入力となる．図5

ケジュールを作ることが主流になりつつある．しかし，が出力，すなわち，図4から作られた車両運用封・画でコンピュータはあくまでも人間を支援するにすぎない．

ある．図4の列車ダイヤを実現可能とするための編成

意思決定を行うのは人間である．どの線区のどことどの便月引憤序を定めた計画ということになる．図5の1

この間に，何本くらいの列車を運転しようとか，始発行が，ある編成の1日の動きを示している（「行路」

駅の発車時刻を何時にしようとか，そういったことは，と呼ぶ）．例えば，列車2で駅Bに到着した編成が列

すべて人間が決めて人力する．ディスプレイの上にダ

車1で折り返すことを示している．図5は，行路そのイヤ図を表示し，それを見ながら人間がダイヤを作っものの順序をも示している．これを「交番」と呼ぶ．

ていく．コンピュータはある程度の自動作成機能（例

図5の計画では，列車8で駅Bに到着した編成は，

えば，始発駅と終着駅の時刻を決めれば，あるルール

翌日は行路2の列車4に充当される．また，列車7でに従って中間の駅の時刻を自動的に決めるなど）は，駅Cに到着した編成は，翌日は交番の最初にもどっ持っているが，それはとても「自動作成」といえるよて，行路1の列車2に充当されることになる．

うなものではない．コンピュータは，その他，矛盾の図5は，二i行，すなわち，三つの行路から成り立っ

チェック（例えば，列車が駅間で他の列車を追い越すている．このことは，図5の車両運用計画を実現する

ような計画になっていないかなど）や，ダイヤ図などためには，：i本の編成が必要になることをも示していの帳票の出力を分担．している．これは，列車ダイヤのる．

例であったが，車両運用計画や乗務員運用計画，構内図5については，以上のことの他に，次の二つのことを説明しなければならない．一つは，検査の計画で作業計画についそも事情は変わらない．
その背景には，これらの計画の作成にあたっては，ある．鉄道の車両は，一定の周期で検査を実施しなけ

コンピュータにはまかせられない高度な判断業務が必要であるため，「意思決定は人間，単純作業はコンピ
ュータ」という役割分担にしようという，インタラク
ティブシステムの思想がある．

3．2 インテリジェントなスケジューリングシステ
ムヘの期待

ロ ノ＼畠

ノ＼ご 其・＼

近年になって，高度な自動作成機能を持ったスケジ
図4 列車ダイヤ（人力）ューリングシステムへの期待が高まっている．その背景には，輸送計画の作成にかかる手間をなるべく少なくして，作業を効率化したいという事情（さらに，この背景には，ベテランの減少と経費の節減の要望がある），それに，様々な条件のもとでの輸送計画を迅速に作ることができれば，経営施策の策定に資することができる（例えば，車両の配置箇所や所属乗務員数を2004年1月号

行路1 c＿ヱ＿

行路2 B 行路3

図5 図4から作成した車両運用計画（出力）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）35

ればならないと定められている．車両運用計画において考慮しなければならない検査には，交番検査と仕業検査がある．交番検査は，編成の走行距離が30，000
kmに達する前ごとなどに実施しなければならない．
仕業検査は，主に外観を検査するもので，3日ごとなどに実施しなければならない4．交番検査や仕業検査は，どこででも実施できる訳ではない．たいていの場
合，車両基地で実施することになる．また，それらの検査には，ある時間を要する（車種や両数によって異なるが，正味の時間は，前者で数時間，後者で数十分

図6 実際の車両運用計画（一部）である）．このことは，すなわち，車両運用計画においては，検査の周期に達する前に，検査ができる場所に行く計画になっていなければならないこと，そして，／一フ⑳

そこでは，検査に要する時間が確保されていなければならないことを意味している（図5では，仕業検査だ
けを書いている．仕に○の字が仕業検査を表してい訝郡

る）．
もう一つは，回送列車の存在である．図5を注意深く見ていただくと，図4には含まれていない列車が現れていることがわかる．それは，「回送」と書いてあ

図7 車両運用計画ネットワーク

る列車だ．実は，図4の列車ダイヤそのままでは，車両運用計画は作れない．C駅に到着する列車の数（2クを考える．アークには，アークの始点側の列車の終本）とC駅から発車する列車の数（3本）が一致して着時刻と終点側列車の始発時刻の間の時間差（間隔）いないからだ．事情は，B駅についても同様である．

を重みとして付す（マイナスになるときには，24時

このような場合，B駅とC駅の間に回送列車を設定

間を加える．これは，翌日の列車と接続することを意して，到着列車の数と出発列車の数をあわせてやらな

味する）．このようにして作成したネットワークを車ければならない．このような回送列車を設定すること

両運用計画ネットワークと呼ぶことにしよう（図4かも，車両運用計画作成の一部である．

ら作成した車両運用計画ネットワークを図7に示す．

車両はきわめて高価なものである．種類にもよるが，1両1億円規模だと考えていただいてよい．10両編成

ただし，煩雑になるので，すべてのアークを書いてはいないし，アークの重みも省略している）．

なら，1編成10イ意円ということになる．よって，車さて，使用編成数がもっとも少ない車両運用計画は，両運用計画を作るときには，使う車両がなるべく少な入力として与えられた列車ダイヤから作成した車両運

くてすむような計画が求められる．

用計画ネットワーク上で，「すべてのノードを通り，

なお，図5は，説明のためにきわめて単純な例をあかつ，アークの重みの和が最小であるような巡回路」

げた．実際の車両運用計画は，数百本規模の列車を含（図7の太線）を見出すことによって得られる．言う

むきわめて大規模な問題となる．実際の車両運用計画までもなく，これは，巡回セールスマン問題の一部を図6にあげる（図6は，図5とは異なって，（TSP）である．すなわち，基本的には，車両運用計

ダイヤ図一車両運用ダイヤ図−の形式で描かれてい画作成問題は，巡回セールスマン問題と等価であるとる）．

いうことになる．

4．2 TSPとしての車両運用計画作成問題

4．3 TSPよりも難しい！

図4の列車ダイヤに対して，列車をノードとし，任TSPは組合せ最適化問題の中でも難しい問題とさ意の二つのノードの間にアークを設定したネットワー

れている．しかし，車両運用計画作成問題はさらに難4 これは一つの例である．実際には，交番検査，仕業検査の周期は車種によって異なる．

しい．その主な理由を次にあげよう．

36（36）

・検査の考慮：「重み最小の巡回路」だけでは，交オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

番検査・仕業検査の周期に関する制約を満たしてまず見つけ，それを変形していくということにある．

いない．また，周期のほかにも，交番検査や仕業

やはり，車両運用計画については，検査の制約が非常検査ができる時間帯が限られているという制約もにきびしい．

ある．例えば，通常，交番検査は夜間に実施するアルゴリズムの枠組みとしては，メタヒューリステ

ことはできない．これは，検査を実施する要員のイクスの一種である確率的局所探索を用いている．筆

勤務時間に起因している．検査に関するこれらの者らがメタヒューリステイクスに注目している理由は，制約を満たしながら，使用編成数最小の巡回路をその処理速度にある．ここで対象としているのは，計作っていくことは簡単ではない．

画段階（すなわち，ダイヤ改正時）であるから，ある・評価尺度：必要編成数が最小になることは最重要程度処理時間がかかっても差し支えないともいえる．

な評価尺度であるが，それだけではない．例えば，

完璧な結果が得られるのなら，一晩くらいかかっても回送列車は，車両運用の都合で，いわば仕方なく実用上問題ないかもしれない．しかし，先ほどのよう設定したものであるから，その本数・走行距離はな多様な評価尺度，それに，節6で述べるような残さなるべく少ない方がよい．また，検査の回数につれた問題を考慮すると，現時点では，ある程度人間がいても，制約を満たしている限り，少ない方がよ介入する必要が残されているのではないかと考えていいだろう．すなわち，車両運用計画作成問題は，る．そのためには処理時間は短いにこしたことはない．

いわゆる多目的最適化問題になる．

つまり，コンピュータの作成結果を見て人間がある程5．鉄道のスケジューリングアルゴリズムの現状度の条件を入力し，それをもとにコンピュータが計画の再作成を行うという枠組みが実用的ではないかという意味である．

5．1鉄道のスケジューリング問題の難しさ

5．3 鉄道のスケジューリングアルゴリズムの現状

節4での議論から，ある程度ご理解いただけたと思節3で述べたように，現時点では，鉄道の輸送計画

うのだが，車両運用計画をはじめとする鉄道のスケジ

は人間主導で作られているが，研究としては，スケジューリング問題の難しさを要約すると次のようになる

ュール作成の自動化に関する成果が数多く報告されてと思う．

いるようになってきている．そのいくつかをご紹介し（1）大規模な組合せ最適化問題になる．
（2）考慮しなければならない制約が多数存在し，かつ，複雑である．

よう．
【列車ダイヤ】

列車ダイヤの自動作成は容易ではない［2］．一つの（3）ある程度迅速に解を生成することが求められる．

理由は，経営方針に直結するからである．どの区間に（4）評佃尺度が多数存在する．

どの程度の本数の列車を運転し，どの駅に快速列車を（5）評価尺度の間の優先度，優先順位等を明確にす止めるのかなどを決めることは，競合路線との関係とることが難しく，しかも場合によって変わる．

もあいまって，高度な経営判断となる．評価尺度もあ

もちろん，このうちのいくつかは，現実の問題を対いまいである．何がよいダイヤかを明確に定義するの象としているがゆえに発生する難しさであって，他のは難しい．また，対象範囲を限定しにくい問長引こなり業種にも共通する問題であろう．

がちだという問題もある．その主な理由は，接続にあ5，2 メタヒューリステイクスによる車両運用計画

る．他線区との列車の接続を考えなければならない．

場合によっては，他会社やバスなどの他交通機関との作成アルゴリズム

筆者らは，車両運用計画作成問題に対して，メタヒ接続が問題になる場合もある．

ューリステイクスを用いたアルゴリズムを開発してい【乗務員運用計画】

る［1］．そして，現実のダイヤデータを用いた実験の列車ダイヤにくらべれば，車両運用計画や乗務員運結果，人間の専門家が長い時間をかけて作成した車両

用計画は，まだ見込みがある．乗務員運用計画は，車運用計画と比較して，ほぼ遜色ない結果が得られるこ

両運用計画と類似の構造を持っている．ただし，一つとを確認している．

の行路（2日またがりの場合もある）の開始駅と終了

アルゴリズムの詳細は，文献［1］を参照していただ

駅が一致しなければならない（つまり，乗務員が出勤

きたいが，その骨子は，検査の制約を満たす巡回路をする場所と勤務終了後に帰ってくる場所が同じでなけ2004年1月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）37

ればならない）という制約がある．したがって，乗務・多様な評佃尺度への対応

員運用計画については，行路と交番を別々に作ること

節5．1でも述べたように，鉄道のスケジューリンが多い．行路の案をまず作った後，在宅休養時間や休グ問題は多目的最適化問題になる．これに対する日等の制約を考慮して，行路の並び（交番）を作ろう

一つのアプローチは，各々の評価尺度に重みを乗という考え方になる．

じて加算したものをその解に対する評価値とする

行路の自動作成問題は，集合被覆問題（Set Cover−というものである．しかし，このアプローチでは，

ing Problem）として定式化することができる．すな

重みのつけ方をどうするのかなどの問題が残る．

わち，行路の案をあらかじめ多数生成しておき，その・制約，前提条件，評佃尺度のあいまいさ

中からすべての列車を被覆できる行路の組合せを見出鉄道に限らず，実世界の問題にはよくあることでそうとする考え方である．複数の行路で被覆された列あると思われるが，制約や前提条件を明確にする

車については，乗務員が複数乗務することになりそうことが必ずしも容易ではない．評価尺度についてだが，そのうちの1名以外は，便乗（運車云しないで移も同様である．「できれば00であってほしいの動するだけ）ということにすればよい．

だが…まあ，だめなら仕方がないけど」といった乗務員運用計画は，生身の人間の勤務のスケジュー

ものが続出する．そして，これらの条件を割り切ルであるだけに，勤務時間（出勤から退勤までの時間，ってしまうと，例えば，乗務員運用計画の場合

連続して運転する時間等）や休憩時間に関して，様々「血も涙もない運用計画」が作成されてしまうこな制約がある．また，人間の勤務であるがゆえの配慮とになる［2］．

が求められる．例えば，深夜遅く到着した乗務員は，・制約を満たさない場合の扱い

可能なら翌日は遅めに発車する列車に充当するなど，

例えば，乗務員の昼食のための休憩は，12時〜2

例によって，明確には記述しがたい条件に関する配慮

時ごろまでが望ましい．これは，制約であると考が求められる．乗務員運用の作成にあたっては，このえることができる．すべての行路についてそれが点が難しい．

満足できればよいが，そうもいかない場合がある．

乗務員運用計画については，文献［3〜6］等の研究が制約を満足できない行路を含む場合，その解にはなされている．海外においても多くの研究事例（文献

ペナルティをつけることになるだろう．では，そ［7］など）がある．なお，文献［6］は，交番の作成に関のペナルティはどのようにつければよいのだろうするものである．

か？

【構内作業計画】

しかも，このような制約は昼食時間だけではない．

構内作業計画については，基本的には，ある一つの考慮すべき制約が数十もあるとしたら，それら相駅や車両基地の内部だけに議論を絞ることができる．

互の関係を考慮してペナルティの付け方を決める

よって，列車ダイヤや車両・乗務員運用計画にくらべことはできるだろうか［2］．

ると，比較的取り扱いやすい．これは，ある種の有限・わかりやすさへの配慮

資源プロジェクトスケジュー1）ング問題（Resource

作成された計画に沿って作業を行うのは人間であConstrained Project Scheduling Problem）［8］である．となると，人間にとってわかりやすい計画にると考えることができる．これについては，例えば，

なっていることが求められる．例えば，ダイヤ改文献［9〜12］などの研究が報告されている．

正とはいっても，小規模な変更であれば，乗務員運用計画などは，ダイヤ改正前となるべく同じも

6．今後の課題は？

のにしたいという要望がある．慣れ親しんだ計画

節5で紹介したように，鉄道の輸送計画作成アルゴに沿って作業した方が，取り扱いの誤りなどが防リズムの高度化については，近年多くの研究がなされ止できると考えられるからというのがその理由でてきている．しかし，より高度なアルゴリズムを開発ある．

するためには，まだ，取り組まなければならない課題

・問題の範囲を限定することが難しいがあることも事実だろう．そのうちのいくつかについ

先ほど車両運用計画の入力としては，図4のようて述べてみようと思う．

な列車ダイヤ（列車計画）が与えられると述べた．
しかし，厳密にいうと，これは必ずしも正しくな

38（38）

オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

い．車両運用計画は，車種ごとに作られる．とな覧いただきたい．

ると，その車種の編成を充当するはずの列車だけ

参考文献を選び出したものを，入力となる列車ダイヤとすることになる．しかし，列車によっては，A車
種でもB車種でもよいという場合も存在する（例えば，以前の東海道新幹線のダイヤで，一部の「ひかり」に「のぞみ」の編成が使われていたように）．このような場合，A車種とB車種の車両運用計画をまとめて作るという方策もあるが，それでは問題の規模が大きくなりすぎるし，また，
A車種とB車種を完全に混ぜて作ってよいわけでもないという難しさもある（「ひかり」に「の［1］過鵬，冨井規雄，福村直登，坂口隆：「確率的局所探索に基づく鉄道車両運用計画アルゴリズム」，電気学会交通・

電気鉄道研究会，TER−0ト54，2001．
［2］冨井規雄編：「鉄道システムへのいざない」，共立出版，
2001．
［3］松田雅軋小川健一，森戸晋，新井裕明：「乗務員基地を考慮した乗務員スケジューリング問題への列生成アプローチ」，統計数理研究所共同研究レポート161最適化：
モデリングとアルゴリズム16，2003．

［4］今泉淳，鷺見亮，斉藤秀和他：「鉄道乗務員運用計画へぞみ」の編成を使ってもよいが，その道は不可でのバックトラック法による行路候補列挙と集合被覆問題

ある）．

の近似解法」，統計数理研究所共同研究レポート（2004発

これらの課題の中には，純粋なアルゴリズムの研究の範囲を超えるものが存在することも事実だと思う．
また，研究者サイドだけでは解決できないものもあろう．アルゴリズムの研究成果を真に有月≡はものにする
ためには，ユーザとも連携して，これらの課題に粘り

強く取り組んでいくことが必要であると考える．

行予定）［5］竹田真也，一階良知，片岡健司，薦田憲久：「状態選択法と条件緩和探索法による知識型乗務員運用計画方式」，電学論C，Vol．119，No．11，1999．
［6］坂口隆：「制約論理プログラミングの探索手法と対話型スケジューリング」，オペレーションズ・リサーチ，
Vol．47，No．1，2002．

［7］Caprar．a，A．，M．Fischettiet al∴

7．おわりにSolution of

Large−Scale railway Crew Planning Problems‥the
本稿では，鉄道におけるスケジューリング問題につItalian Experience，in N．H．M．Wilson ed．，Com−

いて，現状の作業の実態，研究の動向，残された課題

PuterLAided 7領znsit Scheduling，Lecture Notesin等について述べた．本稿を読んで，鉄道のスケジュー

Economics and MathematicalSystems，Springer，

リング問題に関心を持っていただける読者が増えれば，

1999．
［8］鍋島一郎：「スケジューリング理論」，森北出版，1974．

筆者にとって望外の幸である．
ただし，鉄道業務に関わる人間の全員が輸送計画の自動作成にもろ手を挙げて賛成しているわけではない

ことも付記しておかなければならないだろう．自動化機能を導入することには異論もある．「自動化が進めば，専門家としての知識が乏しくなり，コンピュータの出力を無批判に受け入れてしまうことになるのではないか」「開発コストやデータの準備等にかかるコストを考慮するとペイするのか」等が主な反論である．
いずれも，あながち的を射ていないこともない．自動［9］冨井規雄，周利剣，福村直登：「確率的局所探索と
PERTを組み合わせた駅構内入換計画作成アルゴ））ズ

ム」，電学論，Vol．119−C，No．3，1999．
［10］冨井規雄，周利剣：「事例ベース推論を応用した鉄道
駅構内入換作業スケジューリングアルゴリズム」，電学論，Vol．12Z2−C，No．6，2002．
［11］冨井規雄，周利剣：「要員割当を考慮した鉄道駅構内
作業計画スケジューリングアルゴリズム」，スケジューリ
ングシンポジウム2001，2001．
［12］佐藤達広，江口俊宏，村田智洋：「GA・ヒューリステ

化機能を考えるにあたっても，このような意見がある

ィック融合スケジューリング方式一車両転線計画の作ことを意識しておく必要があろう．

成」，情報処理学会人工生命とその応用シンポジウム，

なお，紙面の都合により，本稿では，計画作成段階に焦点をあてた．もう一つの重要なトピックとして，計画の実行段階の業務，すなわち，ダイヤ乱れに対応して行われる再スケジューリング（運転整理）がある．

これについては，例えば，文献［2，13，14］などをご2004年1月号

1997．
［13］冨井規維：「ダイヤの乱れを克服する一鉄道の運行管

理システムの現状と今後」，情報処理，Vol．44，No．8，
2003．
［14］冨井規維：「定時運行の科学」，成山堂書店，近刊．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）39