JPH09315308A

JPH09315308A - 運行機材の運用計画作成方法

Info

Publication number: JPH09315308A
Application number: JP13187096A
Authority: JP
Inventors: Tatsuhiro Sato; 達広佐藤; Toshihiro Eguchi; 俊宏江口; Tomohiro Murata; 智洋村田; Kazuo Kurihara; 和男栗原
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1996-05-27
Filing date: 1996-05-27
Publication date: 1997-12-09

Abstract

(57)【要約】【課題】単一の運行ダイヤから成るか又は所定の接続
条件の下で複数の運行ダイヤを接続する運用パターンの
構成と、所定の制約条件の下で複数の運用パターンを順
次連結する車両運用計画の組立とを統合的に行い、計画
作成者の負担を軽減する。【解決手段】接続制約行列の生成１は、運行ダイヤテ
ーブル１１を入力して運行ダイヤｉに運行ダイヤｊの接
続可否を示す接続制約行列１２を作成する。遺伝子コー
ド行列の生成３は、接続制約行列１２の接続可を示す行
列要素について接続又は非接続を確率的に決定し、遺伝
子コード行列１４を作成する。運用計画の解探索４は、
制約条件１５の下に遺伝子コード行列１４から運用シー
ケンスに追加する運用パターンを探索し、運用計画の解
候補１７を作成する。作成した解候補を制約条件１５の
下に評価し、評価値に基づいて遺伝子コード行列１４に
遺伝子操作を加える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、鉄道、バス、航空
機など運行機材の運用計画作成方法に係わり、特に電子
計算機を利用して解の探索を行う運用計画作成方法に関
するものである。

【０００２】

【従来の技術】鉄道、バス、航空機などの運行機材が出
発点を出発して運行し到着点に到着するまでのスケジュ
ールは運行ダイヤと呼ばれる。単一の運行ダイヤによっ
て又は所定の接続条件の下で複数の運行ダイヤを接続し
て一定期間、例えば１日の運用パターンが構成される。
電子計算機を利用して運行ダイヤから運用パターンを作
成する方法が実用化されている。例えば「岩崎他：車両
運用自動作成システムの開発，ｐｐ３６４−３６８，日
本鉄道サイバネティクス協議会第２６回論文集，１９９
１年１１月」は、グラフィカルユーザーインターフェー
スを用いて運用パターンの作成を支援するシステムにつ
いて開示する。

【０００３】

【発明が解決しようとする課題】上記従来技術は、電子
計算機を利用して運行パターンの作成を行うが、さらに
所定の制約条件の下で複数の運用パターンを連結して運
用パターンのシーケンス、すなわち運用計画の全体を作
成するまでには至っていない。このため運用計画の作成
と評価は、計画作成者の手作業に依存しているのが現状
である。計画作成者が運用計画を作成し評価した結果、
それが計画作成者の意図を満足する解ではないと判断さ
れる場合、運用パターンの作成をやり直す必要があり、
電子計算機を利用して運行パターンを再作成すれば再び
手作業による運用計画の作成を繰り返すことになり、計
画作成者の負担が大きいという問題があった。

【０００４】本発明の目的は、運行パターンの解探索と
運用計画の解探索とを電子計算機によって統合して行
い、もって計画作成者の負担を軽減することにある。

【０００５】本発明の他の目的は、計画作成者によって
運行ダイヤの接続条件や運行パターンを連結するときの
制約条件を変更したり追加できるようにし、計画作成者
の意図を充分反映することにある。

【０００６】

【課題を解決するための手段】本発明は、まず運行ダイ
ヤｉに運行ダイヤｊが接続可能か否かを示す接続制約行
列を作成し、この接続制約行列の接続可を示す行列要素
について所定の接続条件を充足するように運行ダイヤｉ
に運行ダイヤｊを接続するか非接続とするかを確率的に
決定して接続行列を作成する。この接続行列は実現可能
な運用パターンの種類を表現している。接続可能な行列
要素の値を確率的に決めるため、複数個の接続行列を作
成することが可能である。次に各接続行列が表現する運
用パターンの中から所定の制約条件を充足する運用パタ
ーンを探索して作成中の運用パターンのシーケンスに追
加する。制約条件を充足する運用パターンが見当らなけ
れば、いくつかの制約条件のうち優先順位の低いものか
ら順に制約条件を解除して運用パターンの探索を再試行
する。このようにして各接続行列に対応して運用計画の
解候補を組み立てた後、制約条件の違反の程度に応じて
各解候補の評価値を算出する運行機材の運用計画作成方
法を特徴とする。

【０００７】また本発明は、計画作成者によって接続制
約行列の接続可能を示す行列要素のうち特定の行列要素
の値が接続又は非接続に固定されたとき、このように固
定された接続条件に従って解の探索を進める。また計画
作成者によって特定の運用パターンへの特定の運用パタ
ーンの連結を指定されたとき、この条件を制約条件に追
加し、この制約条件に従って解の探索を進める。

【０００８】

【発明の実施の形態】以下、本発明の一実施形態につい
て図面を用いて詳細に説明する。

【０００９】図２は、ある鉄道路線における運行ダイヤ
の例を示す図である。運行ダイヤは、車両が出庫場所
（出発点）を出発して運行し、入庫場所（到着点）に到
着するまでのスケジュールを示しており、各運行ダイヤ
には運行番号が付されている。丸記号は出庫場所を示す
記号、三角記号は入庫場所を示す記号である。丸記号及
び三角記号の下の場所名は、それぞれ出庫場所の名称及
び入庫場所の名称を示している。例えば運行番号０１の
運行ダイヤに割り当てられた車両は、前日に駅Ａに留置
されており(留置入庫)、当日は午前５時２９分に駅Ａを
出発し、午前８時５８分に車両基地に入庫する。図２の
例によれば、２５種類の運行ダイヤがあり、これらの運
行ダイヤが車両運用計画を作成するときの基本的な構成
要素となる。

【００１０】図３は、車両運用計画の例を示す図であ
る。各運用パターンは、１日の車両運用スケジュールを
示しており、１個の運行ダイヤを適用するか又は２個の
運行ダイヤを組合わせることによって構成される。運用
番号は各運用パターンに付された番号であり、運行番号
は適用する運行ダイヤの運行番号、出庫は車両の出庫場
所、入庫は車両の入庫場所を示す。例えば運用番号１の
運用パターンは、運行番号０１及び０２の運行ダイヤを
適用する。すなわちこの運用パターンを割り当てられた
車両は、運行番号０１の運行ダイヤによる運行を行った
後に運行番号０２の運行ダイヤによる運行を行い、両運
行の間に定期点検と中清掃を受ける。ある運用パターン
に次の運用パターンを連結するとき、前者の入庫場所と
後者の出庫場所とは一致している。各運用パターンに付
された運用番号は、運用ローテーションの順序を示して
いる。また運用パターンの数は、予備車両を除いて運用
に必要な車両の数を示している。

【００１１】図４は、１ケ月間の運用ローテーションの
例を示す図である。運用ローテーションは、運用パター
ンをその運用番号の順に並べることによって構成され
る。図４は車両０１に対して運用番号１から始まる運用
計画を割り当てることを示している。各車両に対して運
用番号の順に運用割当を行うことにより、法律で義務付
けられている定期点検間隔（通常は３日以内）を遵守し
た車両の運用を実現できる。また各車両の走行距離を均
一にすることができる。毎日の車両配車を行う車両割当
計画は、月次検査や重要部検査等の車両検査計画を満足
した上でなるべくこの運用ローテーションを崩さないよ
うにして作成される。

【００１２】以下車両運用計画の作成処理について順を
追って説明するが、本実施形態の車両運用計画の作成と
は、（ａ）運行ダイヤ間に存在する接続条件の下で運行ダイ
ヤから運用パターンを作成する。（ｂ）運用パターン間に存在する制約条件の下で運用パ
ターンのシーケンスを作り、運用計画を組み立てる。の
２種類の組合わせ問題を解くことである。組合わせ問題
（ａ）の解が組合わせ問題（ｂ）の入力となり、組合わ
せ問題（ｂ）の解を評価してその結果が組合わせ問題
（ａ）の組合わせの仕方に影響を与える。従って両者の
解を相互に関連づけて解探索をする必要がある。

【００１３】図１は、車両運用計画の作成処理を行う情
報処理装置の処理手順の概略を示す図である。運行ダイ
ヤテーブル１１は、図２に示すような運行ダイヤをテー
ブルの形式で格納するファイルである。接続制約行列１
２は、運行番号ｉの運行ダイヤに運行番号ｊの運行ダイ
ヤを接続できるか否かを示す行列を格納するファイルで
ある。接続制約行列の生成１の処理は、運行ダイヤテー
ブル１１を参照して各運行ダイヤの出庫場所、入庫場
所、出庫時刻及び入庫時刻に基づいて接続制約行列を生
成し、接続制約行列１２に格納する。入力装置１８は、
以下に説明する解探索のパラメータを入力するキーボー
ド等の装置である。解探索パラメータ１３は、入力され
た解探索パラメータを格納するファイルである。解探索
パラメータの入力２の処理は、入力装置１８から入力さ
れたパラメータを解探索パラメータ１３に格納する。遺
伝子コード行列１４は、接続制約行列１２に基づいて運
行番号ｉの運行ダイヤに運行番号ｊの運行ダイヤを接続
するかしないかを示す行列を格納するファイルである。
遺伝子コード行列の生成３の処理は、接続制約行列１２
を入力し、運行ダイヤの接続が可能な行列要素に対して
接続するか接続しないかを確率的に決定し、その結果の
行列を複数種類生成して遺伝子コード行列１４に格納す
る。各遺伝子コード行列は、運用パターンの解候補を表
現するものである。生成する行列の数は、解探索パラメ
ータ１３から入力される。

【００１４】制約条件１５は、運用パターンに運用パタ
ーンを連結するときの制約条件を設定するファイルであ
る。選択条件１６は、運用計画を組み立てる途中で次の
運用パターンを選択するときの条件を設定する作業用フ
ァイルである。選択条件は制約条件１５から決定され
る。解候補１７は、解探索の結果として求められた運用
計画の解候補を格納するファイルである。運用計画の解
探索４の処理は、遺伝子コード行列１４から１つの遺伝
子コード行列を取り出し、制約条件１５から次に連結す
る運用パターンを選択する条件を決定して選択条件１６
に格納し、この選択条件に基づいて次に接続する運用パ
ターンを探索する。このようにして運用パターンを次々
に連結して運用計画の解候補を組み立てて解候補１７に
格納する。運用計画の解探索４は、１つの運用計画の解
候補を生成すると、遺伝子コード行列１４から次の遺伝
子コード行列を取り出して上記処理を繰り返す。このよ
うにして遺伝子コード行列が尽きたとき、解候補１７中
の解候補の評価を行いこの評価値に基づいて遺伝子コー
ド行列１４中の遺伝子コード行列に対して遺伝子操作を
行って次の世代の遺伝子コード行列を生成し、再び上記
の解候補の生成処理を行う。このようにして運用計画の
解探索４は、解探索パラメータ１３によって指定された
世代数について解探索を行った後、処理を終了する。

【００１５】解候補の表示とオペレータ評価８の処理
は、解候補１７を参照して最も評価値の高い解候補を表
示装置１９上に表示する。マウス，キーボード等の入力
装置１８を介して解承認、解修正、代案要求又は制約編
集が指示されたとき、解候補の表示とオペレータ評価８
は、指示された処理を行う。解承認が指示されたとき、
承認された解候補をプリンタ２０上に出力して処理を終
了する。解修正が指示されたとき、表示装置１９に表示
された解候補について入力装置１８を介して行われる変
更に従って解候補１７を修正する。代案要求が指示され
たとき、解候補１７中の他の代案を表示装置１９上に表
示する。制約編集が指示されたとき、入力装置１８を介
するオペレータの操作に従って接続制約行列１２の運用
ダイヤの接続を固定したり、制約条件１５に運用パター
ンの接続についての制約条件を加えるような編集処理を
行う。

【００１６】上記の車両運用計画の作成処理は、パソコ
ン、ワークステーションを含む通常の情報処理装置によ
って実現可能である。運行ダイヤテーブル１１、接続制
約行列１２、解探索パラメータ１３、遺伝子コード行列
１４、制約条件１５、選択条件１６及び解候補１７は、
この情報処理装置の記憶装置に格納されるファイルであ
る。入力装置１８、表示装置１９及びプリンタ２０は、
この情報処理装置に接続される入出力装置である。接続
制約行列の生成１、解探索パラメータの入力２、遺伝子
コード行列の生成３、運用計画の解探索４及び解候補の
表示とオペレータ評価８は、この情報処理装置の記憶装
置に格納されるプログラムを実行することによって実現
される。

【００１７】図５は、接続制約行列１２のデータ形式を
示す図である。接続制約行列１２は、運行ダイヤの数×
運行ダイヤの数の行列要素を持つ正方行列であり、行列
要素（ｉ，ｊ）のｉ及びｊは運行番号である。行列要素
（ｉ，ｊ）は、０，１又は＊の符号をもつ。符号０は運
行番号ｉの運行ダイヤに運行番号ｊの運行ダイヤを接続
しないことを示し、符号１は運行番号ｉの運行ダイヤに
運行番号ｊの運行ダイヤを接続することを示す。符号＊
は運行番号ｉの運行ダイヤに運行番号ｊの運行ダイヤを
接続可能なことを示す。最初に作成される接続制約行列
１２は、符号０及び符号＊から成り、符号１を含まな
い。

【００１８】運行ダイヤテーブル１１は、図２に示す運
行ダイヤをテーブルの形式で表現したもので、各運行ダ
イヤごとに運行番号、出庫場所、出庫時刻、入庫場所及
び入庫時刻のデータを有する。接続制約行列の生成１
は、運行ダイヤテーブル１１を読み込んで接続制約行列
１２を生成する。運行番号ｉの運行ダイヤの入庫時刻が
運行番号ｊの運行ダイヤの出庫時刻の前であり、かつ前
者の入庫場所と後者の出庫場所が等しい場合には、１つ
の車両が運行ｉに続いて運行ｊを行うことが可能であ
り、行列要素（ｉ，ｊ）に符号＊を格納する。また運行
番号ｉの運行ダイヤと運行番号ｊの運行ダイヤとがこの
接続条件を満足しないときには、１つの車両が運行ｉに
続いて運行ｊを行うことが不可能であり、行列要素
（ｉ，ｊ）に符号０を格納する。

【００１９】解探索パラメータの入力２は、表示装置１
９上に解探索パラメータを入力するための画面を表示
し、入力装置１８から入力された解探索パラメータを解
探索パラメータ１３に格納する。解探索パラメータは、
次のようなデータ項目から構成される。（ａ）遺伝子コード行列の数（１〜１００）（ｂ）世代数（１〜１０００）（ｃ）自然淘汰率（１〜１００％）（ｄ）突然変異率（０要素，１〜１００％）（ｅ）突然変異率（１要素，１〜１００％）遺伝子コード行列の数は、遺伝子コード行列の生成３が
生成する遺伝子コード行列の数を設定する。世代数は運
用計画の解探索４が行う遺伝子操作について何世代の遺
伝子操作を行うかその数を設定する。（ｃ）（ｄ）
（ｅ）は、遺伝子操作のパラメータであり、自然淘汰率
は自然淘汰操作で消滅させる遺伝子コードの割合を指定
する。突然変異率（０要素）は突然変異操作で遺伝子コ
ードの符号０を符号１に変化させる確率を指定し、突然
変異率（１要素）は遺伝子コードの符号１を符号０に変
化させる確率を指定する。

【００２０】図６は、遺伝子コード行列１４のデータ形
式を示す図である。遺伝子コード行列１４は、運行ダイ
ヤの数×運行ダイヤの数の行列要素を持つ正方行列であ
り、行列要素（ｉ，ｊ）のｉ及びｊは運行番号である。
行列要素（ｉ，ｊ）は、遺伝子コードと呼ばれ、０又は
１の符号をもつ。符号０は運行番号ｉの運行ダイヤに運
行番号ｊの運行ダイヤを接続しないことを示し、符号１
は運行番号ｉの運行ダイヤに運行番号ｊの運行ダイヤを
接続することを示す。行列要素（０３，０２）のように
遺伝子コードが１である行列要素に着目したとき、同じ
行０３の他の遺伝子コードはすべて符号０であり、同じ
列０２の他の遺伝子コードはすべて符号０である。すな
わち運行ｉに運行ｊを接続するとき、運行ｉに他の運行
が接続することはなく、また運行ｊが他の運行に接続す
ることはない。また行列要素（ｉ，ｊ）の遺伝子コード
が１であるとき、運行ｊに運行ｉが接続することは不可
能であるから、行列要素（ｊ，ｉ）の遺伝子コードは０
である。一般に１個の運行ダイヤに接続できる運行ダイ
ヤは高々１個に限られる。遺伝子コード行列は、実行可
能な運用パターンの解候補を表現するものである。本実
施形態では遺伝子コード行列に遺伝子操作を施すために
遺伝子コード行列と呼ぶが、遺伝子操作に関係しないな
ら単に接続行列と呼んでもよい。

【００２１】遺伝子コード行列の生成３は、接続制約行
列１２を入力し、初期の遺伝子コード行列を生成して遺
伝子コード行列１４に格納する。遺伝子コード行列１４
の各行列要素（ｉ，ｊ）に遺伝子コードを設定するとき
の規則は次の通りである。（ａ）接続制約行列１２の行列要素（ｉ，ｊ）が符号０
であるとき、遺伝子コード行列１４の対応する行列要素
（ｉ，ｊ）の遺伝子コードを符号０にする。（ｂ）接続制約行列１２の行列要素（ｉ，ｊ）が符号１
であるとき、遺伝子コード行列１４の対応する行列要素
（ｉ，ｊ）の遺伝子コードを符号１にする。（ｃ）接続制約行列１２の行列要素（ｉ，ｊ）が符号＊
であるとき、遺伝子コード行列１４の行ｉ又は列ｊにす
でに１がある場合には遺伝子コード行列１４の対応する
行列要素（ｉ，ｊ）の遺伝子コードを符号０にする。（ｄ）接続制約行列１２の行列要素（ｉ，ｊ）が符号＊
であるとき、遺伝子コード行列１４の行ｉ又は列ｊにま
だ１がない場合には遺伝子コード行列１４の対応する行
列要素（ｉ，ｊ）の遺伝子コードを確率的に符号０又は
符号１にする。規則（ｄ）を適用するとき、遺伝子コー
ド行列の生成３は乱数を発生させて遺伝子コードを決定
する。符号０又は符号１にする確率は５０％である。こ
のようにして１つの遺伝子コード行列を生成して遺伝子
コード行列１４に格納し、生成した遺伝子コード行列の
数が解探索パラメータ１３から入力された遺伝子コード
行列の数に達しないときは、次の遺伝子コード行列を生
成して遺伝子コード行列１４に格納する。遺伝子コード
行列の生成３は、解探索パラメータ１３に設定した数の
遺伝子コード行列を生成して遺伝子コード行列１４に格
納したとき処理を終了する。このようにして生成された
遺伝子コード行列は、それぞれ実行可能な運用パターン
の解候補を表現するものである。各遺伝子コード行列が
表現する運用パターンの総数は、（運行ダイヤの総数）
−（遺伝子コードが１である行列要素の数）によって得
られる。

【００２２】制約条件１５は、運用パターンに運用パタ
ーンを連結して運用計画を組み立てるときの必須制約と
目標制約を設定する。必須制約は必ず充足しなければな
らない制約であり、目標制約はなるべく充足したい制約
である。以下に制約条件の例を挙げる。（ａ）必須制約（i）運用パターンｉの入庫場所とこれに連結する運用
パターンｉ＋１の出庫場所は同じでなければならない。（ii）３日以内に車両の定期点検を行わねばならない。（iii）オペレータの指示による制約条件：特定の解候
補について特定の運用パターンに連結する運用パターン
を固定するときに、解候補の識別子及び運用番号の並び
を設定する。（ｂ）目標制約（i）少なくとも８日に１度車両の中清掃を行い、少な
くとも１２日に１度車両の大清掃を行う。（ii）前日駅に留置した車両は当日なるべく車両基地に
入庫する。

【００２３】選択条件１６は、解探索の途中で運用パタ
ーンのシーケンス（以下運用シーケンスという）に追加
する運用パターンを選択するときの条件を設定する作業
用ファイルである。選択条件は次の５つの項目から構成
される。（ａ）運用パターン識別子必須制約（iii）により次に連結する運用パターンが固
定されているとき、解候補の識別子と運用パターンの運
用番号を設定する。（ｂ）出庫場所必須制約（i）により、運用シーケンスの最後にある運
用パターンの入庫場所を設定する。（ｃ）定期点検必須制約（ii）により、次の運用パターンに定期点検が
必要なときに「要」を設定する。（ｄ）清掃目標制約（i）により、次の運用パターンが清掃日に当
っているとき「要」を設定する。（ｅ）基地入庫目標制約（ii）により、次の運用パターンの入庫場所と
して基地入庫としたいとき「要」を設定する。これらの
項目の優先順位は、（ａ）が最も高く（ｂ）（ｃ）
（ｄ）（ｅ）の順に低くなる。

【００２４】解候補１７は、図３に示すような運用計画
をテーブル形式でもつ運用計画の解候補である。各解候
補は識別子をもち、対応する遺伝子コード行列の識別子
及び運用計画の解探索４によって与えられた評価値をも
つ。また必須制約違反をしている運用パターン及び目標
制約違反をしている運用パターンにはそれぞれフラグを
セットする。

【００２５】図７は、運用計画の解探索４の処理の流れ
を示すフローチャートである。運用計画の解探索４は、
実行世代数を示すカウンタｍを０クリアし（ステップ４
１）、実行行列数を示すカウンタｎを０クリアする（ス
テップ４２）。実行世代数ｍが解探索パラメータ１３か
ら入力した世代数に達しなければ（ステップ４３＜）、
実行行列数ｎが解探索パラメータ１３から入力した遺伝
子コード行列数に達しないとき（ステップ４４＜）、運
行ダイヤテーブル１１、制約条件１５及び選択条件１６
を参照し、遺伝子コード行列１４中の１つの遺伝子コー
ド行列について解候補の探索を行い、作成した運用計画
の解候補を解候補１７に格納する（ステップ４５）。こ
のとき解候補に使用した遺伝子コード行列の識別子を付
加する。次に運用計画の解探索４は、制約条件１５を参
照して作成した解候補について設定した制約条件の充足
度をチェックして評価値を算出する（ステップ４６）。
解候補を構成する運用パターンのうち必須制約違反又は
目標制約違反をしている運用パターンにそれぞれのフラ
グをセットし、解候補に評価値を付加する。次に実行行
列数ｎに１を加えて（ステップ４７）、ステップ４４の
処理に戻る。すなわち遺伝子コード行列１４に残りの遺
伝子コード行列があれば、次の遺伝子コード行列につい
て上記処理を繰り返す。実行行列数ｎがパラメータの遺
伝子コード行列数に達したとき（ステップ４４＝）、遺
伝子コード行列１４中の遺伝子コード行列について自然
淘汰、交叉及び突然変異の遺伝子操作を行う（ステップ
４８）。新しく生成した遺伝子コード行列には新しい識
別子を付与する。次に実行世代数ｍに１を加えて（ステ
ップ４９）、ステップ４２の処理に戻る。実行世代数ｍ
がパラメータの世代数に達したとき（ステップ４３
＝）、運用計画の解探索４の処理を終了する。

【００２６】図８は、ステップ４５の運用計画の組立の
処理をさらに展開して示すフローチャートである。運用
計画の解探索４は、現在の遺伝子コード行列から運用パ
ターンの総数を求めてカウンタｉにセットする（ステッ
プ５１）。カウンタｉの値が０より大きいとき（ステッ
プ５２＞）、選択条件１６を決定する。制約条件１５を
参照し、運用シーケンスに追加する運用パターンの選択
条件を選択条件１６に設定する（ステップ５３）。運用
シーケンスの最後にある運用パターンに接続する運用パ
ターンを固定する制約条件が設定されていれば、固定す
る運用パターンの識別子を選択条件１６に設定する。出
庫場所は、運用シーケンスの最後にある運用パターンの
入庫場所を設定する。運用シーケンスの最初の運用パタ
ーンについては、制約条件１５に設定してなければ任意
であり、遺伝子コード行列１４の運用パターンの中から
ランダムに選択する。定期点検、清掃及び基地入庫につ
いては、すでに組み立てた運用シーケンスを参照して必
要であれば「要」を設定する。次に現在の遺伝子コード
行列を参照してまだ採用されない運用パターンの中から
選択条件１６を満足する運用パターンの探索を行う（ス
テップ５４）。運用パターン識別子が選択条件になって
いれば、解候補１７を参照して該当する運用パターンを
抽出する。該当する運用パターンが見つかれば（ステッ
プ５５有）、点検及び清掃を決定する（ステップ５
６）。選択条件１６の定期点検又は清掃が「要」であれ
ば、定期点検又は清掃を設定する。運用シーケンスにお
いて清掃を行わない運用が続いた回数によって中清掃か
大清掃を設定する。定期点検又は清掃が「要」でなく、
かつ定期点検又は清掃が可能である運用パターンについ
ては、定期点検又は清掃は任意である。その場合定期点
検又は清掃を行わない運用が続いた回数によって行うか
否かを決定してよい。運用パターンがオペレータ指示に
よって固定されていれば、定期点検又は清掃は元の運用
パターンの通りである。次に完成した運用パターンにシ
ーケンス順に運用番号を付与して解候補１７の運用シー
ケンスに追加する（ステップ５７）。次にカウンタｉか
ら１を引き（ステップ５８）、ステップ５２に戻って上
記処理を繰り返す。該当する運用パターンが存在しなけ
れば（ステップ５５なし）、選択条件１６を緩和する
（ステップ５９）。すなわち選択条件が設定されている
項目の中で最も優先順位の低い項目の選択条件を解除す
る。そして再びステップ５４の運用パターンの探索を行
う。すべての選択条件が解除されたとき、ステップ５４
は残っている任意の運用パターンをランダムに選択す
る。カウンタｉの値が０になったとき（ステップ５２
＝）、処理を終了する。

【００２７】ステップ４６の解候補の評価では、解候補
１７中の各解候補について制約条件１５を参照して評価
値を計算する。必須制約違反及び目標制約違反の各々に
ついてペナルティ値を設け、各制約違反するごとに減点
する。例えば初期値を１０００点とし、各必須制約違反
のペナルティ値を３００点、目標制約違反のペナルティ
値を５０点に設定するなどである。運用計画の解探索４
は、解候補を構成する運用パターンのうち必須制約違反
又は目標制約違反をしている運用パターンにそれぞれフ
ラグをセットし、解候補に算出した評価値を付加する。
なお解候補を構成する運用パターンの総数は、運用計画
に必要な車両数を示しているので、上記制約違反に加え
て車両数を最小にするための運用パターン数を評価の対
象としてもよい。

【００２８】ステップ４８の遺伝子操作では、遺伝子コ
ード行列１４に対して自然淘汰、交叉及び突然変異の順
で遺伝子操作を行う。まず自然淘汰操作では、解候補１
７を参照して遺伝子コード行列１４の各遺伝子コード行
列の識別子を評価値の順に並べ、評価値の低いものから
順に遺伝子コード行列を遺伝子コード行列１４から削除
する。また対応する解候補を解候補１７から削除する。
削除する遺伝子コード行列の数は、遺伝子コード行列１
４中の行列数×解探索パラメータ１３から入力された自
然淘汰率である。

【００２９】自然淘汰操作によって減少した遺伝子コー
ド行列の数だけ交叉操作によって新たな遺伝子コード行
列を生成して補充する。交叉操作は、親の遺伝子コード
行列Ａと親の遺伝子コード行列Ｂから新しい子の遺伝子
コード行列Ｃを生成する処理である。行列Ａ及び行列Ｂ
は評価値の高いものから順に選択する。交叉オペレーシ
ョンは、親の行列要素Ａ_ijのコードと親の行列要素Ｂ_ij
のコードに基づいて子の行列要素Ｃ_ijのコードを生成す
る操作である。図９は、交叉操作の処理の流れを示すフ
ローチャートである。子のすべての行列要素Ｃ_ijの生成
を終えていなければ（ステップ６１ＮＯ）、行列要素Ｃ
_ijをランダムに選択する（ステップ６２）。Ｃ_ijに対応
する行列Ａの要素Ａ_ijと行列Ｂの要素Ｂ_ijの値が等しけ
れば（ステップ６３ＹＥＳ）、行列要素Ａ_ijの値をＣ_ij
に設定する（ステップ６４）。Ａ_ijの値とＢ_ijの値が等
しくなければ（ステップ６３ＮＯ）、遺伝子コードを設
定するときの規則に従って行ｉ又は列ｊにすでに１があ
る場合（ステップ６５ＮＯ）、Ｃ_ijを０に設定する（ス
テップ６６）。行ｉ及び列ｊに１がない場合（ステップ
６５ＹＥＳ）には、確率Ｐ_cで行列要素Ａ_ijの値をＣ_ij
に設定し、確率１−Ｐ_cで行列要素Ｂ_ijの値をＣ_ijに設
定する（ステップ６７）。ここにＰ_c＝行列Ａの評価値
／（行列Ａの評価値＋行列Ｂの評価値）である。ステッ
プ６４，６６及び６７からステップ６１に戻り、子のす
べての行列要素Ｃ_ijの生成を終えたとき（ステップ６１
ＹＥＳ）、行列Ｃの生成処理を終了する。この交叉オペ
レーションの結果として得られる新しい遺伝子コード行
列Ｃは、運行ダイヤの接続条件を充足し、かつ評価値の
高い親の遺伝子コード行列の形質をより強く受け継いだ
ものとなる。

【００３０】次に自然淘汰操作によって残った遺伝子コ
ード行列の中から評価値の低い遺伝子コード行列を選ん
で突然変異操作を行う。この突然変異操作の役割は、解
探索が局所解に陥ることを防ぐことである。本実施形態
の突然変異操作は、親の遺伝子コード行列の遺伝子コー
ドを確率的に反転させることによって突然変異を実現す
る。図１０は、突然変異操作の処理の流れを示すフロー
チャートである。親の遺伝子コード行列を行列Ａとし、
生成される子の遺伝子コード行列を行列Ａ’とする。接
続制約行列１２中の符号＊をもった行列要素（ｉ，ｊ）
に対応する行列Ａ’の行列要素をＡ’_ij（＊）とすると
き、まずＡ’_ij（＊）以外の行列要素Ａ’_ij（¬＊）の
値として対応する親の行列要素Ａ_ij（¬＊）を設定する
（ステップ７１）。すべてのＡ’_ij（＊）の生成を終え
ていなければ（ステップ７２ＮＯ）、行列要素Ａ’
_ij（＊）を選択する（ステップ７３）。選択したＡ’_ij
（＊）に対応する親の行列要素Ａ_ij（＊）が１であれば
（ステップ７４ＮＯ）、解探索パラメータ１３に設定さ
れた突然変異率（１要素）による確率Ｐ₁でＡ’
_ij（＊）を０に反転したものとし、確率１−Ｐ₁でＡ’
_ij（＊）を反転しない（ステップ７５）。親の行列要素
Ａ_ij（＊）が０であれば（ステップ７４ＹＥＳ）、遺伝
子コードを設定するときの規則に従って行ｉ又は列ｊに
すでに１がある場合（ステップ７６ＮＯ）、Ａ’
_ij（＊）を０に設定する（ステップ７７）。行ｉ及び列
ｊに１がない場合（ステップ７６ＹＥＳ）には、解探索
パラメータ１３に設定された突然変異率（０要素）によ
る確率Ｐ₀でＡ’_ij（＊）を１に反転したものとし、確
率１−Ｐ₀でＡ’_ij（＊）を反転しない（ステップ７
８）。ステップ７５，７７及び７８からステップ７２に
戻り、行列Ａ’のすべてＡ’_ij（＊）の生成を終えたと
き（ステップ７２ＹＥＳ）、行列Ａ’の生成処理を終了
する。突然変異操作によって親の行列Ａを子の行列Ａ’
に代える。

【００３１】解候補の表示とオペレータ評価８は、解候
補１７の中から最も評価値の高い解候補を選択し、表示
装置１９上に表示する。このとき解候補を構成する運用
パターンの中で必須制約違反又は目標制約違反のフラグ
がセットされている運用パターンがあれば、その運用パ
ターンを強調表示する。図１１は、表示装置１９に表示
された解候補である運用計画の例を示す図である。図の
運用計画の解候補は、運用番号４の運用パターンの出庫
場所が運用番号３の運用パターンの入庫場所に一致しな
い必須制約違反をしている。

【００３２】入力装置１８を介して解承認が指示された
とき、解候補の表示とオペレータ評価８は承認された解
候補をプリンタ２０上に出力して処理を終了する。解修
正が指示されたとき、解候補の表示とオペレータ評価８
は表示装置１９に表示された解候補に対して入力装置１
８を介してオペレータの自由な修正を許す。例えば図１
２は、運用パターンに定期点検と中清掃を追加する例を
示す図である。入力装置１８を介して図１２（ａ）に示
す運用パターンが指定され、作業指示が指定されると、
解候補の表示とオペレータ評価８は図１２（ｂ）のよう
な作業指定ウィンドウを開く。入力装置１８から点検の
有無及び清掃の有無と種類が指定されると、解候補の表
示とオペレータ評価８は２つの運用ダイヤの間に点検と
清掃を追加し、解候補１７及び表示装置１９上の表示を
更新する。また図１３は、運用パターンの順序を変更す
る例を示す図である。入力装置１８を介して図１３
（ａ）に示すように運用番号７の運用パターンと運用番
号１０の運用パターンとが選択され、図１３（ｃ）に示
す解修正ウィンドウ中の「ＥＸＣＨＡＮＧＥ」ボタンが
選択されると、図１３（ｂ）に示すように指定された運
用パターンを交換し、解候補１７及び表示装置１９上の
表示を更新する。なお解候補の表示とオペレータ評価８
は修正が行われるたびに制約違反をチェックし、解候補
１７中のフラグを更新するとともに制約違反の強調表示
を更新する。

【００３３】入力装置１８を介して代案要求が指示され
たとき、解候補の表示とオペレータ評価８は解候補１７
を参照して解候補の識別子、その評価値及び対応する遺
伝子コード行列の識別子を評価値の高いものから順に表
示装置１９上に一覧表の形式で表示する。入力装置１８
を介して特定の解候補の識別子が指定されたとき、解候
補の表示とオペレータ評価８は指定された運用計画の解
候補を表示装置１９上に表示する。

【００３４】入力装置１８を介して制約編集が指示され
たとき、解候補の表示とオペレータ評価８は制約指示ウ
ィンドウを開いてオペレータによる制約指示を受け入れ
る。図１４は、制約編集の例を示す図である。図１４
（ａ）のように表示装置１９に表示される運用計画中の
特定の運用パターンが指定され、図１４（ｂ）に示す制
約指示ウィンドウ中の「ＧＲＯＵＰ」ボタンが選択され
ると、解候補の表示とオペレータ評価８は指定された運
用パターンを構成する２つの運行ダイヤの接続を固定す
るために、接続制約行列１２の対応する行列要素の符号
＊を符号１に変更する。この操作によって以後２つの運
行ダイヤの接続は固定され、作成される解候補はこの運
用パターンを含むことになる。また制約指示ウィンドウ
中の「ＵＮＧＲＯＵＰ」ボタンが選択されると、解候補
の表示とオペレータ評価８は指定された運用パターンを
構成する２つの運行ダイヤを切り離すために、接続制約
行列１２の対応する行列要素の符号＊を符号０に変更す
る。この操作によって以後この２つの運行ダイヤは切り
離され、作成される解候補がこの運用パターンを含むこ
とはなくなる。また図１４（ｃ）のように２つの運用パ
ターンが指定され、図１４（ｄ）に示す制約指示ウィン
ドウ中の「ＣＯＮＮＥＣＴ」ボタンが選択されると、解
候補の表示とオペレータ評価８は指定された２つの運用
パターンの並びを固定するために、制約条件１５の必須
制約条件として解候補の識別子と運用番号の並びを設定
する。この操作によって以後作成される解候補は、これ
らの運用パターンの並びが固定されたまま出現する。た
だし運用パターンに付与される運用番号は、新しい解候
補の運用シーケンスに従って付け換えられる。以上のよ
うにして制約編集をした後、遺伝子コード行列の生成３
から又は運用計画の解探索４から上記処理を繰り返せ
ば、解候補１７に新しい解候補が得られ、入力装置１８
の指示に従って新しい解候補を表示装置１９上に表示す
ることができる。

【００３５】なお上記実施形態は鉄道車両を例にして説
明したが、本発明は鉄道車両に限定されるものではな
く、バス、航空機等他の運行機材の運用計画にも適用で
きることが理解される。

【００３６】

【発明の効果】本発明によれば、運用パターンの解探索
と運用計画の解探索とを相互に関連づけて行い、運用計
画の解候補の評価結果に応じて運用パターンの作成を軌
道修正でき、最終的な運用計画の作成に当って計画作成
者の負担を軽減することができる。

【００３７】また計画作成者によって運用パターンを構
成する運行ダイヤの接続条件や運用パターンを連結する
ときの制約条件を固定したり追加したりできるので、計
画作成者の意図を充分に反映する運用計画作成が可能で
ある。

【図面の簡単な説明】

【図１】本発明の実施形態の車両運用計画作成の処理の
概略を示す図である。

【図２】運行ダイヤの例を示す図である。

【図３】車両運用計画の例を示す図である。

【図４】運用ローテーションの例を示す図である。

【図５】実施形態の接続制約行列１２のデータ形式を示
す図である。

【図６】実施形態の遺伝子コード行列１４のデータ形式
を示す図である。

【図７】実施形態の運用計画の解探索４の処理の流れを
示すフローチャートである。

【図８】実施形態の運用計画の組立処理（ステップ４
５）の処理の流れを示すフローチャートである。

【図９】実施形態の交叉操作の処理の流れを示すフロー
チャートである。

【図１０】実施形態の突然変異操作の処理の流れを示す
フローチャートである。

【図１１】解候補である運用計画の表示例を示す図であ
る。

【図１２】解修正の例を示す図である。

【図１３】他の解修正の例を示す図である。

【図１４】制約編集の例を示す図である。

【符号の説明】

１：接続制約行列の生成、３：遺伝子コード行列の生
成、４：運用計画の解探索、８：解候補の表示とオペレ
ータ評価、１１：運行ダイヤテーブル、１２：接続制約
行列、１４：遺伝子コード行列、１５：制約条件、１
７：解候補

───────────────────────────────────────────────────── フロントページの続き (72)発明者栗原和男茨城県ひたちなか市市毛1070番地株式会社日立製作所水戸工場内

Claims

【特許請求の範囲】

【請求項１】運行機材が出発点を出発して運行し到着点
に到着するまでのスケジュールを示す複数種類の運行ダ
イヤが与えられ、単一の運行ダイヤによって又は所定の
接続条件の下で複数の運行ダイヤを接続して一定期間の
運用パターンを構成し、所定の制約条件の下で複数の運
用パターンを順次連結して運行機材の運用計画を組み立
てる情報処理装置を利用する運用計画作成方法であっ
て、運行ダイヤｉに運行ダイヤｊが接続可能か否かを示す接
続制約行列を作成して記憶装置に格納し、該接続制約行列の接続可を示す行列要素について該接続
条件を充足するように運行ダイヤｉに運行ダイヤｊを接
続するか非接続とするかを確率的に決定し可能な運用パ
ターンの種類を表現する接続行列を作成して記憶装置に
格納し、接続可を示す行列要素の値の確率的変化に依存
して複数個の接続行列を作成し、該接続行列が表現する運用パターンの中から該制約条件
を充足する運用パターンを探索して作成途中の運用パタ
ーンのシーケンスに連結し、該制約条件を充足する運用
パターンが見当らなければ該制約条件のうち優先順位の
最も低いものから順に制約条件を解除して運用パターン
の探索を行い、各接続行列に対応して運用計画の解候補
を組み立てて記憶装置に格納し、該制約条件の違反の程
度に応じて該解候補の各々の評価値を算出することを特
徴とする運行機材の運用計画作成方法。
【請求項２】該解候補のうち最も評価値の高い解候補を
表示装置上に表示することを特徴とする請求項１記載の
運行機材の運用計画作成方法。
【請求項３】該評価値に基づいて該接続行列に遺伝子操
作を施して上記運用パターンの探索を繰り返し、新たな
解候補を作成することを特徴とする請求項１記載の運行
機材の運用計画作成方法。
【請求項４】該接続制約行列の接続可能を示す行列要素
のうち特定の行列要素の値を接続又は非接続に固定した
上で上記接続行列の作成及び運用パターンの探索を行う
ことを特徴とする請求項１記載の運行機材の運用計画作
成方法。
【請求項５】該制約条件の１つとして特定の運用パター
ンへの特定の運用パターンの連結を固定することを特徴
とする請求項１記載の運行機材の運用計画作成方法。