JPH0969122A - 運行機材の運用計画作成方法およびシステム - Google Patents

Abstract

(57)【要約】 【目的】 ユーザの意図を容易に解探索に反映可能な運
行機材の運用計画作成方法およびシステムを提供するこ
と。 【構成】 運行機材の運用番号と日付とから成る２次元
マトリクスの格納領域と、この２次元マトリクスと同一
マトリクス構造の複数の遺伝子の格納領域とを設けた上
で、運行機材を複数の運用番号のいずれかに割り当てる
際に考慮すべき制約条件を前記２次元マトリクスの対応
するメッシュに設定して記憶させると共に、複数の遺伝
子の格納領域にそれぞれ異なる遺伝子コードをランダム
に設定して遺伝子コードが異なる複数の遺伝子を生成し
た後、この複数の遺伝子の各遺伝子コードと対応するメ
ッシュの制約条件とに基づき運行機材をいずれかの運用
番号に割り当てる割当て処理を行い、この割当て処理後
に得られた各遺伝子対応の複数の運用計画を前記制約条
件に対する充足度合いで評価し、評価値の高い運用計画
を出力する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、列車、バス、航空機な
どの運行機材の運用計画の立案問題を計算機で解く運用
計画作成方法に係り、詳しくは、計算機を利用した計画
の立案、立案結果の表示、立案結果の修正、立案結果の
検証の各過程を含む運用計画作成方法およびシステムに
関するものである。

【０００２】

【従来の技術】車両の運用計画を計算機によって作成す
るシステムとして、ＡＩの技法を応用したシステムがあ
る。

【０００３】例えば、「高橋、他：車両基地におけるコ
ンピュータ利用，pp47-50，三菱電機技報vol.61,No.2,1
987」に記載されているように、パソコンを利用して車
両の運用管理を支援するシステムがある。このシステム
では、専門家の知識を利用して、全列車の走行キロ数が
均一となるように、数日先の運用を考慮して、一日ずつ
計画を作成している。

【０００４】また、「車両運用計画エキスパートシステ
ム，pp224，東芝レビューvol.49,No.3,1993」に記載さ
れているように、車両運用計画を作成するだけでなく、
留置計画の自動作成ならびに故障時等に代替可能な車両
を自動検索する機能をサポートしているシステムがあ
る。

【０００５】

【発明が解決しようとする課題】しかしながら、エキス
パートシステム等、ＡＩの技法を応用した従来の車両運
用計画システムにあっては、解の探索論理が問題固有の
解法知識（ヒューリスティクス）にかなり依存してい
る。このため、計画作成条件等がいったん変化してしま
うと、システムがこれに追従できず、満足な解が得られ
ないということが頻繁に発生していた。このような場合
には、探索ルールの変更や制約の緩和など、人間による
介入が必要になるが、ヒューリスティクスへの依存度の
高い従来のシステムでは、探索ルールや制約の効率的な
修正が困難であるため、試行錯誤的に探索論理を調整し
なければならないという問題があった。

【０００６】本発明の目的は、計画作成条件等の変更に
対して、探索ルールや制約条件を効率的に修正し、探索
解にユーザの意図を容易に反映させることができる運行
機材の運用計画作成方法およびシステムを提供すること
にある。

【０００７】

【課題を解決するための手段】上記の目的を達成するた
めに、本発明は、基本的には、運行機材の運用番号と日
付とから成る２次元マトリクスの格納領域と、この２次
元マトリクスと同一マトリクス構造の複数の遺伝子の格
納領域とを設けた上で、運行機材を複数の運用番号のい
ずれかに割り当てる際に考慮すべき制約条件を前記２次
元マトリクスの対応するメッシュに設定して記憶させる
と共に、前記複数の遺伝子の格納領域にそれぞれ異なる
遺伝子コードをランダムに設定して遺伝子コードが異な
る複数の遺伝子を生成した後、この複数の遺伝子の各遺
伝子コードと対応するメッシュの前記制約条件とに基づ
き運行機材をいずれかの運用番号に割り当てる割当て処
理を行い、この割当て処理後に得られた各遺伝子対応の
複数の運用計画を前記制約条件に対する充足度合いで評
価し、評価値の高い運用計画を出力することを特徴とす
る。

【０００８】

【作用】上記手段によれば、運行ダイヤや検査計画など
の制約条件を、制約の種類毎に例えば横軸を日付、縦軸
を運用番号とした２次元マトリクスの各要素に記憶する
一方で、その２次元マトリクスに対応した構造の複数の
遺伝子を生成し、この複数の遺伝子の各遺伝子コードと
対応するメッシュの制約条件とに基づき運行機材をいず
れかの運用番号に割り当てる。そして、その割当て処理
後に得られた各遺伝子対応の複数の運用計画を制約条件
に対する充足度合いで評価し、評価値の高い運用計画を
出力する。

【０００９】従って、制約条件を操作することにより、
その制約条件に柔軟に追従した解（運用計画）を効率良
く探索し、出力することができる。

【００１０】この場合、運行機材の運用計画を、運用接
続行列における各隣接ノード間の接続グラフを用いて表
示し、接続グラフのノードやアークをマウス等によるポ
インティングデバイスを用いて指定することにより、グ
ラフィックを修正する感覚で制約や計画の修正を行うこ
とができる。

【００１１】さらに、運用計画を修正毎にチェックし、
運用接続グラフ上の制約違反箇所のノードやアークを点
滅・着色することにより、制約のチェック結果を分かり
易くユーザに提示することができる。

【００１２】さらに、制約の追加や変更に対して、制約
条件を充足している部分については、その部分に対する
割当てを凍結することにより、現時点の解をなるべく崩
さないように制約に対する充足解を効率良く求めること
ができる。

【００１３】

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

【００１４】まず、本実施例で取り扱う車両運用計画作
成問題の概要を説明する。

【００１５】鉄道の車両は、定期的に検査を受けること
が義務付けられている。検査の種類は、長期検査と短期
検査の２つに分類される。長期検査は、車両を一旦分解
し、再度組立てるために作業に数ヵ月を要する。一方、
短期検査は予め定められたチェック項目を検査器で自動
検査するため、数日で検査を完了する。

【００１６】一般的には、全ての車両は１〜２年に１回
のペースで長期検査を受け、それとは別に２〜３ヵ月に
１回のペースで短期検査を受けなければならない。ま
た、全ての車両には、車両ＩＤが定められており、これ
を用いて予め１年分の全車両の検査計画が人手により作
成される。検査計画の立案は、全ての車両がバランス良
く短期検査を受けられるように十分に配慮されている。

【００１７】一方、列車の運行ダイヤに毎日割り当てら
れる車両は日々変更され、毎日同じ車両を同じ時間に運
行させることはしない。一般的な車両の運用形態は、運
用「１」に割り当てられた車両は、翌日は運用「２」、
翌々日は運用「３」といったように車両の配車係の作業
ができるだけサイクリックパタン（ローテーション運
用）となり、かつ全ての車両が定期的に基地に戻って点
検や清掃を受けられるように配慮されている。

【００１８】車両運用計画作成問題は、予め人手により
作成された検査計画と車両運行計画（列車ダイヤ）を必
須の制約条件とし、ローテーション運用をなるべく崩さ
ないように１ヵ月分の運行計画に車両を過不足なく割り
当てる問題である。

【００１９】図１は、本発明による鉄道車両の運用計画
作成手順の一実施例を示すフローチャートである。

【００２０】ステップ１０１０では、問題の規模を決定
するための基本情報を入力する。図２に基本情報の入力
画面２０１０を示している。

【００２１】ユーザはＸ軸、Ｙ軸の名称およびレンジ、
割付けるリソース名称、リソースのレンジ（個数）を入
力する。

【００２２】本実施例の車両割付け問題では、Ｘ軸が１
ヵ月の日付２０２０、Ｙ軸が例えば２２種類の運用番号
２０３０、リソースは各運用番号に割り当てられる２２
本の車両２０４０に相当する。

【００２３】２０５０は、上記の基本情報により作成さ
れたＸ軸を日付、Ｙ軸を運用番号とする２次元マトリク
スに配置されたノードの集合であり、これが解表現の基
本型となる。なお、ノードの集合２０５０における丸印
が１つのノードに該当する。

【００２４】例えば、１日目の運用番号「３」に車両Ａ
が割り当てられ、翌２日目に車両Ａが運用番号「１」に
割り当てられたとすると、その部分計画はノード２０６
１，２０６２間の接続アーク２０６０で表現される。

【００２５】本実施例は、車両運用割付け問題を、解表
現の基本型（運用番号を表現するノード集合）上を車両
ＩＤに相当する複数のアークで配線する配線パスの組合
せ最適化問題として取り扱うものである。

【００２６】ステップ１０２０では、遺伝子オペレーシ
ョンの実行世代数等の解探索パラメータの入力を行う。
解の探索は、確率的探索手法である遺伝的アルゴリズム
を利用する。

【００２７】遺伝的アルゴリズムは、世代サイクルの中
で、（１）自然淘汰（２）増殖（３）突然変異等の遺伝
オペレーションを繰り返し行うことにより、より適応度
（評価値）の高い、遺伝子の組合せを探索する最適化手
法の一つの枠組みである。本実施例では、遺伝子は各ノ
ード与えられた０／１コードの集合に相当する。

【００２８】一般に、遺伝的アルゴリズムにおける遺伝
子オペレーションは、 （１）自然淘汰：適応度（評価値）の劣る遺伝子を消滅
させる。

【００２９】（２）増殖：複数の遺伝子組を交叉させ、
新しい遺伝子を生成する。

【００３０】（３）突然変異：確率的に遺伝子の一部の
遺伝子コードを人為的に反転させる。

【００３１】等が代表的である。

【００３２】本実施例における具体的な最適化の手法お
よび遺伝オペレーションはステップ１０６０で詳しく説
明するが、基本的な処理の流れは （Ｓ１）各ノード毎に遺伝子コード（０または１）をラ
ンダムに与える （Ｓ２）初期解候補として遺伝子コードの集合（遺伝
子）を複数作成する （Ｓ３）遺伝子を変換アルゴリズムにより解表現へ変換
する （Ｓ４）変換された解表現を評価アルゴリズムにより評
価する （Ｓ５）評価値の低い遺伝子から順に自然淘汰率に応じ
て消滅させる （Ｓ６）生き残った遺伝子を交叉させて、新しい遺伝子
を生成する （Ｓ７）生成された遺伝子の遺伝子コードを突然変異率
に応じて反転させる （Ｓ８）生成された遺伝子に対して、処理（Ｓ３）と処
理（Ｓ４）を実施する （Ｓ９）上記の（Ｓ３）から（Ｓ８）の処理を実行世代
数繰り返す である。

【００３３】ステップ１０２０において入力される各種
パラメータは、図３のパラメータ入力画面を用いて入力
され、次の通りである。

【００３４】（１）実行世代数３０１０ 上記処理（Ｓ３）から（Ｓ８）の繰返し回数を指定する
パラメータ （２）集団個体数３０２０ 上記処理（Ｓ２）で作成する遺伝子の個数を指定するパ
ラメータ （３）自然淘汰率３０３０ 上記処理（Ｓ５）で消滅させる遺伝子の割合を指定する
パラメータ （４）突然変異率３０４０ 上記処理（Ｓ７）で遺伝子コードを反転させる確率を指
定するパラメータ （５）非０要素率３０５０ 上記処理（Ｓ２）で生成される遺伝子のうち、非０要素
が占める割合を指定するパラメータ。

【００３５】図３の例では、実行世代数３０１０＝１０
００（回）、集団個体数（遺伝子個数）３０２０＝３０
（個）、自然淘汰率３０３０＝２５（％）、突然変異率
３０４０＝５（％）、非０要素率３０５０＝５０（％）
が入力されたことを示している。

【００３６】次に、ステップ１０３０では、遺伝子情報
の初期化を行う。図４は遺伝子の初期化処理の概略説明
図であり、先のステップ１０１０で定義された各ノード
の集合２０５０に対応するｎ個の遺伝子４０１０ｊ（ｊ
＝１〜ｎ）に対して、０／１をランダムに割り当てるこ
とによりｎ個の遺伝子の初期化を行う。

【００３７】０／１の出現確率は、ステップ１０２０に
おいて入力された非０要素比率により決定される。例え
ば、非０要素比率がＮ％の時は、「１」から「１００」
までの一様乱数値ＲＡＮＤと非０要素比率の大小関係テ
ーブル４０２０とにより、０／１が決定される。

【００３８】ステップ１０４０では、制約条件の入力を
行う。

【００３９】制約条件とは、鉄道やバス，航空機等の運
行計画や検査計画に対し、日々の運行機材（バス，列
車，航空機等の機材）を割り当てる際に考慮すべき条件
のことである。

【００４０】本実施例においては、制約条件として接続
制約と割当て制約とを入力する。

【００４１】接続制約とは、前日の特定の運用番号と当
日の運用番号との接続に関する制約のことであり、割当
て制約とは特定のリソース（運行機材）を当日のいずれ
かの運用番号に割当てる際の制約のことである。

【００４２】接続制約および割当て制約は、「割り当て
なければならない」、あるいは「割り当ててはならな
い」という意味の「優先度＝必須」の制約と、「割り当
てた方が良い」という意味の「優先度＝目標」の制約に
区分されている。なお、制約条件に関する優先度として
は、「必須」および「目標」の他に、「制約なし」があ
る。

【００４３】本実施例では、計画作成条件等の変更に対
し、制約条件を効率良く修正するために、制約条件の入
力インタフェイスとして図５のようなグラフ画面を用い
る。すなわち、図２の２次元マトリクスにおける各ノー
ド間のアークの接続／切断操作や、特定ノードへのリソ
ースの割当操作をポインティング等を用いたグラフ編集
操作によって行い、接続制約や割当制約を効率良く入力
することが可能なように構成している。

【００４４】５０１０は接続制約の表示例である。制約
の強さは優先度で決定され、優先度が「必須」の場合に
は、この制約は「１０Ｂの運用を行った車両は、翌日は
運用１１Ｂに割り当てなければならない。」と解釈され
る。一方、優先度が「目標」の場合には、「１０Ｂの運
用を行った車両は、翌日は運用１１Ｂに割り当てた方が
よい。」と解釈される。

【００４５】なお、接続制約の強さ（すなわち必須か、
目標か）は、アークの太さや色を変えることにより容易
に識別可能に構成され、例えば優先度が「必須」の接続
制約については、表示例５０３０内に示すように、ノー
ド間を太実線で表示し、優先度が「目標」の接続制約に
ついては表示例５０１０に示すようにノード間を細実線
で表示するようになっている。

【００４６】一方、図５の５０２０は割当制約の表示例
である。これも接続制約と同様に、その制約の強さは優
先度で決定される。制約の優先度が「必須」の場合に
は、「２９から３１日の３日間は、「車両ＩＤ＝５」の
車両は短期検査を受けなければならない。」と解釈され
る。また、優先度が「目標」の場合には、「２９から３
１日の３日間は、車両ＩＤが５の車両は短期検査を受け
た方が良い。」と解釈される。なお、割当制約の強さ
は、接続制約の場合と同様に、ノードの大きさや色を変
えることにより容易に識別することが可能になってい
る。

【００４７】図６は、接続制約のデータ構造を示したも
のであり、「優先度」６０１０、「タイプ」６０１１、
「適応対象」６０１２などをユーザーが指定することに
より、制約条件の新規登録／無効化／変更が可能であ
る。図６の例では、優先度６０１０として「目標」、タ
イプ６０１１として「肯定」、適応対象６０１２として
「ノードＡ］と「ノードＢ」が指定されているため、こ
の接続制約は「ノードＡとノードＢは接続すべきであ
る」という意味に解釈される。

【００４８】なお、タイプ６０１１として「否定」が指
定されていた場合は、「ノードＡとノードＢは接続すべ
きでない」という意味に解釈される。

【００４９】また、タイプ６０１１の「なし」はデフォ
ルト値であり、「肯定」と同義である。

【００５０】図７は、割当制約のデータ構造を示したも
のであり、これも接続制約と同様に、「優先度」７０１
０、「タイプ」７０１１、「適応対象」７０１２などを
ユーザーが指定することにより制約の新規登録／無効化
／変更が可能である。図７の例では、優先度７０１０と
して「必須」、タイプ７０１１として「否定」、適応対
象７０１２として「ノードＡ］と「リソースＢ」が指定
されているため、この割当制約は「ノードＡにはリソー
スＢを割り当ててはいけない。」という意味に解釈され
る。

【００５１】図８は、接続制約および割当制約の格納場
所に関する説明図である。

【００５２】本実施例では、接続制約と割当制約を具体
例として扱っているが、各制約ごとに解表現のノードと
１対１に対応したメッシュを有する制約格納用マトリク
ス８００１，８００２の各メッシュに制約条件を格納す
る。

【００５３】例えば、図８に示すアーク８０１０は、
「１９日」に運用６Ｂに割り当てられた車両は、翌「２
０日」には運用７Ｂに割り当てられなければならないと
いう「必須」の接続制約を意味するが、これはノード８
０２０に記述された接続制約Ａとして接続制約格納用マ
トリクス８００１のメッシュ８０３０に格納される。

【００５４】同様に、アーク８０４０は、「２１日」に
運用７Ｂに割り当てられた車両は、翌「２２日」には運
用８Ｂに割り当てた方が良いという「目標」の接続制約
を意味するが、これはノード８０５０に記述された接続
制約Ｂとしてメッシュ８０６０に格納される。

【００５５】一方、ノード８０７０は、「２１日」の運
用１０Ｂには「車両ＩＤ＝５」の車両を割り当てなけれ
ばならないという「必須」の割当制約を意味するが、こ
れはノード８０７０に記述された割当制約Ｃとして割当
制約格納用マトリクス８００２のメッシュ８０８０に格
納される。同様に、ノード８０９０は、「２２日」の運
用１０Ｂには「車両ＩＤ＝９」の車両を割り当てた方が
良いという「目標」の割当制約を意味するが、これはノ
ード８０９０に記述された割当制約Ｄとしてメッシュ８
１００に格納される。

【００５６】次に、ステップ１０５０の解の部分凍結処
理について説明する。

【００５７】システムが提案した制約充足解に対してユ
ーザが新たな制約を加えたり、解の一部を修正すること
によって他のスケジュールに影響が波及し、制約に違反
する箇所が出現する。このような場合、解を一旦「白
紙」に戻して新たな制約を全て満足する解を探索するこ
とは可能であるが、本実施例では、現状の解をなるべく
壊さないで新たな制約を適宜に吸収しながら実行可能な
解を効率良く探索する機能を備えている。

【００５８】図９は、解の部分凍結処理のメイン処理フ
ローである。まず、ステップ９０１０において日付の初
期化を行って日付を「１」に設定し、続くステップ９０
２０において「月末」かどうかの処理終了判定を行い、
日付が月末の場合には処理を終了する。

【００５９】ステップ９０３０においては運用番号の初
期化を行って運用番号を「１」に設定する。ステップ９
０４０においては、運用番号による終了判定を行い運用
番号が最終の場合にはステップ９０５０において日付を
更新し、ステップ９０２０に戻る。

【００６０】次に、ステップ９０６０において該当する
ノードに登録されている制約が充足されているかを判定
する。修正前の接続制約や割当て制約によってシステム
が以前に作成した制約充足解の各ノードと、修正された
接続制約や割当て制約とを照合し、以前に作成した制約
充足解の各ノードが修正された接続制約や割当て制約を
充足しているか否かを判定する。この判定においては、
以前に作成した制約充足解の各ノードが修正された接続
制約や割当て制約に適合している場合は、充足とする。

【００６１】制約が充足されているか、または何も制約
が記述されていない場合にはステップ９０７０において
指定ノードに登録されている制約の優先度を最大にして
解を凍結する。すなわち、「必須」の制約に設定して解
を凍結する。

【００６２】また、制約が充足されていない場合には、
制約はそのままの状態でステップ９０８０で運用番号を
更新し、ステップ９０４０に戻る。

【００６３】なお、解の部分凍結は、制約を充足したメ
ッシュに対応する遺伝子コードを凍結することによって
も等価に実現することができる。

【００６４】図１０は、解の部分凍結処理の概略説明図
であり、１００１０は制約条件の追加等によって現状の
解に制約違反箇所が出現した例である。網かけのノード
が接続制約の違反箇所であることを示し、太線ノードが
割当制約の違反箇所であることを示している。この場
合、接続制約を格納するマトリクスの制約違反エリアは
１００２０であり、制約充足エリアは１００３０であ
る。この時、制約充足エリアに登録されている接続制約
の優先度を確率的に最大に変更する、すなわち「必須」
の接続制約に変更することにより、このエリアの解を確
率的に凍結する。

【００６５】同様に、割当制約の格納マトリクスの制約
違反エリアは１００４０であり、制約充足エリアは１０
０５０である。この時、制約充足エリア１００５０に登
録されている割当制約の優先度を確率的に最大に変更す
る、すなわち「必須」の割当制約に変更することによ
り、このエリアの解を確率的に凍結する。

【００６６】この解の凍結処理によって、凍結しなかっ
たノードについてのみ新たな解の探索が実行される。

【００６７】次に、ステップ１０６０の最適化処理につ
いて説明する。

【００６８】図１１は、最適化のメイン処理フローであ
る。

【００６９】ステップ１１０１０において世代数ｉの初
期化を行って「世代数＝１」に設定し、続くステップ１
１０２０において遺伝子ポインタｊの初期化を行って
「ｊ＝１」に設定する。

【００７０】ステップ１１０３０では終了判定を行い、
世代数ｉが予め設定された実行世代数に達した場合には
処理を終了する。ステップ１１０４０では、遺伝子の解
表現への変換処理（デコード）を行う。

【００７１】デコード処理は、ある遺伝子を変換して１
月分の車両運用計画を生成する処理であり、月の初めか
ら順に１日毎に各ノードを前日のノードと接続する。

【００７２】図１２は、デコードの詳細処理フローであ
る。

【００７３】ステップ１２０１０で日付の初期化を行っ
て「日付＝１」とした後、ステップ１２０２０で月末に
よる処理終了判定を行い、日付が月末の場合には処理を
終了する。

【００７４】次に、ステップ１２０３０において、優先
度に「最大優先度」（本実施例では必須制約）を設定す
る。ステップ１２０４０では、優先度による１日分の終
了判定が行われ、１日分の全ての優先度のデコードが終
了している場合には、ステップ１２０５０で日付の更新
を行ない、ステップ１２０２０に戻る。

【００７５】ステップ１２０６０では、運用番号の初期
化を行って「運用番号＝１」とする。次に、ステップ１
２０７０において運用番号による終了判定を行い、運用
番号が最終の場合にはステップ１２０８０において優先
度を更新してステップ１２０４０に戻る。

【００７６】次に、ステップ１２０９０において、制約
格納用マトリクス８００１，８００２の該当するメッシ
ュにステップ１２０３０で設定した優先度またはステッ
プ１２０８０で行使した優先度と同じ優先度の制約が登
録されているかを判定し、登録されている場合にはステ
ップ１２１００においてデコードルールを実行する。

【００７７】なお、デコード処理は、制約格納用マトリ
クス８００１，８００２に格納された制約をワークエリ
アに複写して行う。その理由は、制約格納用マトリクス
８００１，８００２に格納された制約は、全ての遺伝子
で共通に使用するからでる。従って、遺伝子ポインタｊ
が更新される度に制約格納用マトリクス８００１，８０
０２に格納された制約がワークエリアに複写され、この
複写された制約を用いてデコード処理が実施される。

【００７８】図１３は、デコードルールの定義画面を示
す説明図である。

【００７９】デコードルールは、ｉｆ−ｔｈｅｎ形式で
記述され、ｉｆ部は制約の優先度、タイプ、遺伝子の０
／１コードを用いて記述され、ｔｈｅｎ部は制約の適応
対象と図１３に示す処理コードを用いて記述される。

【００８０】このｉｆ−ｔｈｅｎ形式のデコードルール
により、制約の適用対象に対して処理コードで示される
優先度の更新、未接続ノードのランダム割付け処理等を
行う。

【００８１】本実施例においては、 （１）制約の優先度が「必須制約」の場合 制約が登録されている制約マトリクス８００１，８００
２のメッシュ位置に該当する遺伝子コードに無関係に処
理コードはＡであり、遺伝子コードの０／１に関係なく
無条件に制約を充足させる。

【００８２】（２）制約の優先度が「目標制約」の場合 制約が登録されている制約マトリクス８００１，８００
２のメッシュ位置に該当する遺伝子コードが「０」の場
合には処理コードがＡであり目標制約を充足させるが、
該当する遺伝子コードが「１」の場合には処理コードは
Ｄであり、制約の優先度を１ランク落とし、制約の充足
を保留する。

【００８３】（３）制約の優先度が「無し」あるいは制
約が登録されていない場合 制約が登録されている制約マップのメッシュ位置に該当
する遺伝子コードに無関係に処理コードはＺであり、未
接続なノードを探索して前日のノードにランダムに接続
する。

【００８４】また、該当する優先度を持つ制約が存在し
ない場合には、ステップ１２１１０において運用番号の
更新を行い、ステップ１２０７０に戻る。

【００８５】図１１の最適化メインフローに戻り、次の
ステップ１１０５０では、デコード結果として得られた
解の評価を行う。

【００８６】図１４は、評価の詳細処理フローである。
評価は制約違反に応じた減点法により行う。

【００８７】まず、ステップ１４０１０においてペナル
ティと日付の初期化を行い、「ペナルティ＝０」、「日
付＝１」とした後、ステップ１４０２０において月末に
よる処理終了判定を行い、日付が月末の場合には、世代
数ｉの遺伝子ポインタｊで指定される遺伝子に起案する
評価処理を終了する。

【００８８】ステップ１４０３０において、優先度に
「最大優先度」（本実施例では必須制約）を設定し、さ
らにステップ１４０４０では優先度による１日分の終了
判定を行い、全ての優先度に対するペナルティ集計が終
了している場合には、ステップ１４０５０で日付の更新
を行ない、ステップ１４０２０に戻る。

【００８９】ステップ１４０６０では、運用番号の初期
化を行って「運用番号＝１」とする。ステップ１４０７
０において運用番号による終了判定を行い、運用番号が
最終の場合にはステップ１４０８０において優先度を更
新し、ステップ１４０４０に戻る。

【００９０】次に、ステップ１４０９０において制約マ
ップの該当するメッシュにステップ１４０３０で設定し
た優先度またはステップ１４０８０で更新した優先度と
同じ優先度の制約が登録されているかを判定し、登録さ
れている場合にはステップ１４１００において制約が充
足されているかをチェックする。

【００９１】制約が充足されているか否かは、図１２の
デコード処理によってデコードした制約充足解と接続制
約格納用マトリクス８００１および割当て制約格納用マ
トリクス８００２に格納されている接続制約および割当
て制約とを照合し、図１２のデコード処理によってデコ
ードした制約充足解が接続制約格納用マトリクス８００
１および割当て制約格納用マトリクス８００２に格納さ
れている接続制約および割当て制約を充足するか否かに
よって判定する。

【００９２】制約が充足されていない場合には、ステッ
プ１４１１０で当該遺伝子のペナルティを減点法によっ
て更新し、ステップ１４１２０で運用番号を更新し、ス
テップ１４０７０に戻る。

【００９３】一方、制約を充足している場合には、その
ままステップ１４１２０で運用番号を更新し、ステップ
１４０７０に戻る。

【００９４】図１１の最適化メインフローに戻り、ステ
ップ１１０６０ではデコードすべき遺伝子が残っている
かを判定し、残っている場合にはステップ１１０７０で
遺伝子ポインタｊを１つ更新し、ステップ１１０４０に
戻り、次の遺伝子のデコード処理および評価処理を行
う。

【００９５】デコードすべき遺伝子が残っていない場合
には、ステップ１１０８０において遺伝子オペレーショ
ンの１つである自然淘汰処理を行う。

【００９６】図１５は、自然淘汰処理の概略説明図であ
る。自然淘汰処理は、全ての遺伝子の中から評価値が低
いものから順に自然淘汰率に応じた個数の遺伝子を淘汰
（抹消）する。

【００９７】例えば、遺伝子はＡからＺまであり、自然
淘汰により２個の遺伝子が淘汰される場合で説明する。
１５０１０は、先のステップで新たに生成された遺伝子
Ｙ、Ｚのデコードと評価の終了状態であり、１５０２０
は全ての遺伝子を評価値の高い順に並び変えた状態であ
る。この時、評価値の最も低い遺伝子から順に２つの遺
伝子の評価値に「−１」が設定され、遺伝子が淘汰され
た状態が１５０３０である。

【００９８】この処理によって評価値の低い遺伝子Ｗ，
Ｘが淘汰される。

【００９９】続いて、図１１のステップ１１０９０で
は、遺伝子の交叉オペレーションを行い、先の自然淘汰
において減少した遺伝子数の分だけ新たな遺伝子を生成
して補充する。

【０１００】図１６は交叉処理の概略説明図である。

【０１０１】図１６（ａ）に示す親Ａの遺伝子１６０１
０と同図（ｂ）に示す親Ｂの遺伝子１６０２０とを交叉
して同図（ｃ）に示す子の遺伝子１６０３０を生成する
場合を例に交叉処理を説明する。

【０１０２】一般的には交叉処理は、遺伝子をあるとこ
ろで切断して双方の親の遺伝子を組み合わせるが、本実
施例では、遺伝子コードの合成という手法により新たな
遺伝子を生成させる。

【０１０３】具体的には、２つの親の同一メッシュにあ
る遺伝子コードを合成規則にもとづいて合成し、合成さ
れたコードを子の遺伝子の同一メッシュに設定する。合
成規則としては、２つのコードのＡＮＤ、ＯＲ、ＥＯＲ
をとるなど様々な方法が存在するが、本実施例において
は遺伝子コードの非０要素比率が最適値に収束するため
の仕掛けとして図１６（ｄ）に示すような合成規則１６
０４０を適応する。

【０１０４】これは、合成する２つの親の遺伝子コード
が同一の場合には、子にも同一の遺伝子コードが継承さ
れ、相異なる遺伝子コードの場合には確率Ｐに応じて０
／１を決定する。ここで確率Ｐは、子の遺伝子コードの
非０要素比率の期待値が評価値の高い親の非０要素比率
と同一になるように動的に定められたものである。

【０１０５】次に、図１１のステップ１１１００では、
遺伝子の突然変異オペレーションを行う。一般に遺伝的
アルゴリズムにおける突然変異オペレーションの目的は
解探索が局所解に陥るのを防ぐことであるが、本実施例
においても同様の目的で生成された新たな遺伝子に対し
て突然変異を施す。

【０１０６】図１７は突然変異オペレーションの概略説
明図である。例えば、図１７（ａ）に示す変異前の遺伝
子１７０１０が同図（ｂ）の遺伝子１７０２０に変異す
る場合、遺伝子１７０１０のメッシュＡに格納される遺
伝子コードは突然変異オペレーション１７０３０により
コード変換されて遺伝子１７０２０のメッシュＢに格納
される。

【０１０７】突然変異オペレーションは、あらかじめ定
められた突然変異率Ｐにより遺伝子コードを反転する処
理である。

【０１０８】続いて、図１１のステップ１１１１０では
世代数ｉを更新し、ステップ１１０２０に戻る。上記の
ステップ１１０２０から１１１１０を実行世代数分繰り
返すことにより最適解の探索が進められる。

【０１０９】図１のメインフローに戻り、ステップ１０
７０の立案内容の表示／ユーザ介入処理について説明す
る。

【０１１０】最適化処理が終了した時点での最も評価値
の高い遺伝子を解表現にデコードし、その結果を図１８
のような車両運用グラフで表示する。

【０１１１】この場合のデコードルールは、図１３で説
明したのと同じルールを用いる。

【０１１２】計画立案者は、表示された車両運用グラフ
を判断して、制約修正１８０１０、代案要求１８０２
０、承認１８０３０、破棄１８０４０、制約チェック１
８０５０などの介入を行う。

【０１１３】制約の修正は、ステップ１０４０での説明
と同様である。制約の変更操作が入力されると、それに
応じて各制約格納用マトリクス８００１，８００２が更
新される。

【０１１４】図１９は、接続制約が新たに３箇所入力さ
れた例である。「制約１」は太線アークで必須の接続制
約であり、「制約２」は太い×印で必須の接続制約であ
り、「制約３」は細実線アークで「目標」の接続制約で
ある。「制約１」を例に取ると、接続制約を入力したノ
ードとのマッピングを行い、制約格納用マトリクス８０
０１の対応するメッシュに制約１９０１０が新たに格納
される。

【０１１５】一方、図２０は割当制約が新たに３箇所入
力された例である。「制約６」は薄色ノードで目標の割
当制約であり、「制約４」、「制約５」は濃色ノードで
必須の割当制約である。「制約６」を例に取ると、割当
制約を入力したノードとのマッピングを行い、制約格納
用マトリクス８００２の対応するメッシュに制約２００
１０が新たに格納される。

【０１１６】代替案を要求した場合には、ステップ１０
８０で代替案生成処理を行った後、ステップ１０７０に
戻る。

【０１１７】図２１は代替案生成処理の概略説明図であ
る。代替案の生成は、評価値が次に高い遺伝子Ｂをデコ
ードすることにより生成する。

【０１１８】図２１においては、評価値が最も高い遺伝
子Ａに対し、評価値が次に高い遺伝子Ｂをデコードし、
「代案１」２１０１０を生成することを示している。

【０１１９】立案者が制約のチェックを要求した場合に
は、ステップ１０９０で接続制約、割当制約の各々につ
いて制約のチェックを行い結果を表示する。

【０１２０】制約のチェックは、接続制約格納用マトリ
クス８００１および割当て制約格納用マトリクス８００
２に格納された接続制約と割当て制約に違反していない
か否かを調べることによって行う。

【０１２１】図２２は、接続制約の違反箇所の表示例を
示す説明図であり、違反箇所のアーク２２０１１をブリ
ンク表示すると共に、違反内容をウインド２２０１０に
表示する。ウインド２２０１０では、図１９で示した
「接続制約２」が違反し、ノードＢには接続不可である
ことが表示されている。

【０１２２】図２３は、割当制約の違反箇所の表示例を
示す説明図であり、違反箇所のノード２３０１１をブリ
ンク表示（点滅表示）すると共に、違反内容をウインド
２３０１０に表示する。なお、ブリンク表示に代えて、
該当するアークあるいはノードの線の太さあるいは色を
変えてもよい。

【０１２３】計画の破棄を選んだ場合には、解探索パラ
メータを修正した後に解の探索を最初からやり直すた
め、メイン処理フローのステップ１０２０に戻る。

【０１２４】計画の承認を選んだ場合には、ステップ１
１００で書式変換および印字を行う。

【０１２５】承認された計画は、正式な計画として登録
され、１月分の全車両の運用計画表が実務フォーマット
に書式が変換された上でプリンタから出力される。

【０１２６】図２４は、上述した運用計画作成方法を実
施するシステムのブロック構成図であり、基本情報等を
入力するキーボード２４０１、接続制約等をグラフ画面
で入力する時に使用するポインティングデバイス２４０
２、制約充足解等を表示するディスプレイ２４０３、制
約充足解を印刷出力するプリンタ２４０５、図１のフロ
ーチャートで示した処理を行う処理装置２４６、接続制
約等の各種情報を記憶する記憶装置２４０７とから構成
されている。

【０１２７】処理装置２４０６は、図１のフローチャー
トの各ステップに対応した処理機能を備えている。すな
わち、基本情報入力処理２４１１、解探索パラメータ入
力処理２４１２、遺伝子情報初期化処理２４１３、制約
条件入力処理２４１４、解の部分凍結処理２４１５、最
適化処理２４１６、代案生成処理２４１７、制約チェッ
ク処理２４１８、書式変換・印字処理２４１９を備えて
いる。

【０１２８】記憶装置２４０７は、接続制約格納用マト
リクス８００１および割当て制約格納用マトリクス８０
０２を記憶する記憶領域２４２０および２４２１と、遺
伝子格納領域２４２２、各遺伝子の評価値を格納する評
価値格納領域２４２３とを備えている。

【０１２９】このシステム構成にあっては、処理装置２
４０６は図１〜図２３で説明したのと同じ処理を行い、
接続制約および割当て制約に充足する解を探索し、ディ
スプレイ２４０３の画面に表示したり、プリンタ２４０
５から印刷出力する。詳しい説明は、図１〜図２３の説
明と重複するため、省略する。

【０１３０】なお、図２４では、図１の各ステップで示
した処理を１つの処理装置で実行するように構成してい
るが、複数の処理装置で分散して実行させるように構成
してもよい。

【０１３１】以上のように、本実施例の運用計画作成方
法およびシステムによれば、 （１）車両を列車ダイヤや検査計画に沿って運行する上
での制約条件を解表現である２次元マトリクス上にマッ
ピングすることにより、計画の修正操作と制約条件の調
整操作を連動させることが可能になり、運用計画作成条
件等の変更に対し、探索ルールや制約条件を効率良く修
正し、ユーザの意図を車両運用計画に容易に反映するこ
とが可能となる。

【０１３２】（２）車両運用計画の表示／修正をグラフ
編集操作で行えるため、運用計画の評価や制約チェック
が容易になり、運用計画作成作業の効率が向上する。

【０１３３】（３）新たな制約が追加された場合や制約
違反を解消する際に、現時点での解をなるべく崩さない
ように部分凍結処理を行っているため、例えば行楽シー
ズン等において臨時列車を運行させる場合の制約充足解
を効率的に探索することが可能となる。

【０１３４】（４）ポインティングデバイスを用いてグ
ラフ作成操作や修正操作を行う場合に、２つのノード間
を接続するアークの太さまたは色によって接続制約、割
当て制約の強さを表現するようにしているため、制約条
件が必須の条件か、目標の条件かを直感的に識別するこ
とができ、操作性が向上する。

【０１３５】（５）接続制約や割当て制約に違反してい
る個所に対しては、該当するアークあるいはノードの線
の太さあるいは色を変えたり、点滅させているため、制
約違反個所を直感的に把握させることができる。

【０１３６】（６）遺伝子アルゴリズムによって最適解
を探索しているため、制約条件の多次元の組合せ、ある
いは計画作成条件の変更に対し、探索ルールを変更する
ことなく、最適解を得ることができ、計画作成条件の変
更等に対する柔軟な対応が可能になる。

【０１３７】なお、上記実施例においては、列車の運用
計画を作成する場合について説明したが、バス、航空
機、タクシー、船舶などの運行機材の運用計画の作成に
ついても同様に適用することができることは言うまでも
ない。

【０１３８】

【発明の効果】本発明によれば、以下の効果がある。

【０１３９】（１）車両を列車ダイヤや検査計画に沿っ
て運行する上での制約条件を解表現である２次元マトリ
クス上にマッピングすることにより、計画の修正操作と
制約条件の調整操作を連動させることが可能になり、運
用計画作成条件等の変更に対し、探索ルールや制約条件
を効率良く修正し、ユーザの意図を車両運用計画に容易
に反映することが可能となる。

【０１４０】（２）車両運用計画の表示／修正をグラフ
編集操作で行えるため、運用計画の評価や制約チェック
が容易になり、運用計画作成作業の効率が向上する。

【０１４１】（３）新たな制約が追加された場合や制約
違反を解消する際に、現時点での解をなるべく崩さない
ように部分凍結処理を行っているため、例えば行楽シー
ズン等において臨時列車を運行させる場合の制約充足解
を効率的に探索することが可能となる。

【０１４２】（４）遺伝子アルゴリズムによって最適解
を探索しているため、制約条件の多次元の組合せ、ある
いは計画作成条件の変更に対し、探索ルールを変更する
ことなく、最適解を得ることができ、計画作成条件の変
更等に対する柔軟な対応が可能になる。

【図面の簡単な説明】

【図１】本発明の車両運用計画作成方法の一実施例を示
すメイン処理フロー図である。

【図２】基本情報の入力画面を示す説明図である。

【図３】解探索パラメータの入力画面を示す説明図であ
る。

【図４】遺伝子情報の初期化方法の説明図である。

【図５】制約条件の入力画面を示す説明図である。

【図６】接続制約の定義の一例を示す説明図である。

【図７】割当制約の定義の一例を示す説明図である。

【図８】制約条件の格納場所の説明図である。

【図９】解の部分凍結処理のフロー図である。

【図１０】解の部分凍結処理の説明図である。

【図１１】最適化処理のフロー図である。

【図１２】デコード処理のフロー図である。

【図１３】デコード方法の説明図である。

【図１４】評価処理のフロー図である。

【図１５】自然淘汰処理の概要説明図である。

【図１６】交叉処理の概要説明図である。

【図１７】突然変異処理の概要説明図である。

【図１８】車両運用グラフの例を示す説明図である。

【図１９】接続制約の変更入力例を示す説明図である。

【図２０】割当制約の変更入力例を示す説明図である。

【図２１】代替案の生成処理の説明図である。

【図２２】接続制約の違反箇所のチェック機能の説明図
である。

【図２３】割当制約の違反箇所のチェック機能の説明図
である。

【図２４】運用計画作成システムの実施例を示すブロッ
ク構成図である。

【符号の説明】

２４０１…キーボード、２４０２…ポインティングデバ
イス、２４０３…ディスプレイ、２４０５…プリンタ、
２４０６…処理装置、２４０７…記憶装置、２４１１…
基本情報入力処理、２４１２…解探索パラメータ入力処
理、２４１３…遺伝子情報初期化処理、２４１４…制約
条件入力処理、２４１５…解の部分凍結処理、２４１６
…最適化処理、２４１７…代案生成処理、２４１８…制
約チェック処理、２４１９…書式変換・印字処理、２４
２２…遺伝子格納領域、２４２３…評価値格納領域、４
０１０ｊ…遺伝子、８００１…接続制約格納用マトリク
ス、８００２…割当て制約格納用マトリクス。

Claims (12)

【特許請求の範囲】
1. 【請求項１】 運行機材の運用番号と日付とから成る２
   次元マトリクスの格納領域と、この２次元マトリクスと
   同一マトリクス構造の複数の遺伝子の格納領域とを設け
   た上で、運行機材を複数の運用番号のいずれかに割り当
   てる際に考慮すべき制約条件を前記２次元マトリクスの
   対応するメッシュに設定して記憶させると共に、前記複
   数の遺伝子の格納領域にそれぞれ異なる遺伝子コードを
   ランダムに設定して遺伝子コードが異なる複数の遺伝子
   を生成した後、この複数の遺伝子の各遺伝子コードと対
   応するメッシュの前記制約条件とに基づき運行機材をい
   ずれかの運用番号に割り当てる割当て処理を行い、この
   割当て処理後に得られた各遺伝子対応の複数の運用計画
   を前記制約条件に対する充足度合いで評価し、評価値の
   高い運用計画を出力することを特徴とする運行機材の運
   用計画作成方法。
2. 【請求項２】 前記割当て処理後に得られた各遺伝子対
   応の複数の運用計画を前記制約条件に対する充足度合い
   で評価した後、その評価値に基づいて複数の遺伝子の遺
   伝子コードを組替えた後、その組替え後の複数の遺伝子
   の各遺伝子コードと対応するメッシュの前記制約条件と
   に基づき運行機材をいずれかの運用番号に割り当てる割
   当て処理を行い、この割当て処理後に得られた各遺伝子
   対応の複数の運用計画を前記制約条件に対する充足度合
   いで評価する処理を予め指定された世代交代数分繰返し
   行い、この繰返し処理終了後に得られた各遺伝子対応の
   複数の運用計画のうち前記制約条件に対する評価値の高
   い運用計画を出力することを特徴とする請求項１記載の
   運行機材の運用計画作成方法。
3. 【請求項３】 出力した運用計画の基礎となった制約条
   件の変更に対し、変更後の制約条件を充足する運行機材
   の割当てを凍結し、充足しない制約条件についてのみ前
   記割当て処理を行うことを特徴とする請求項１または２
   記載のいずれかの運行機材の運用計画作成方法。
4. 【請求項４】 前記運用計画を、運用番号と日付とから
   成る２次元マトリクス上の各メッシュに配したノード間
   の接続グラフとして編集し、出力することを特徴とする
   請求項１〜３記載のいずれかの運行機材の運用計画作成
   方法。
5. 【請求項５】 前記制約条件の変更を、前記接続グラフ
   を変更することによって行うことを特徴とする請求項４
   記載の運行機材の運用計画作成方法。
6. 【請求項６】 前記制約条件は、運行機材を当日の運用
   番号のいずれかに割り当てる際の割当て制約と前日の特
   定の運用番号と当日の運用番号とを接続する際の接続制
   約とから成るものである請求項１〜５記載のいずれかの
   運行機材の運用計画作成方法。
7. 【請求項７】 運行機材の運用番号と日付とから成る２
   次元マトリクスの格納領域と、 この２次元マトリクスと同一マトリクス構造の複数の遺
   伝子の格納領域と、 運行機材を複数の運用番号のいずれかに割り当てる際に
   考慮すべき制約条件を前記２次元マトリクスの対応する
   メッシュに設定して記憶させる手段と、 前記複数の遺伝子の格納領域にそれぞれ異なる遺伝子コ
   ードをランダムに設定して遺伝子コードが異なる複数の
   遺伝子を生成する手段と、 前記複数の遺伝子の各遺伝子コードと対応するメッシュ
   の前記制約条件とに基づき運行機材をいずれかの運用番
   号に割り当てる割当て処理を行う手段と、 割当て処理後に得られた各遺伝子対応の複数の運用計画
   を前記制約条件に対する充足度合いで評価する手段と、 評価値の高い運用計画を出力する手段とを備えることを
   特徴とする運行機材の運用計画作成システム。
8. 【請求項８】 前記評価する手段の評価値に基づいて複
   数の遺伝子の遺伝子コードを組替える手段と、 組替え後の複数の遺伝子の各遺伝子コードと対応するメ
   ッシュの前記制約条件とに基づき運行機材をいずれかの
   運用番号に割り当てる割当て処理と前記制約条件に対す
   る充足度合いで評価する処理を予め指定された世代交代
   数分繰返し実行させる手段とをさらに備え、 その繰返し処理終了後に得られた各遺伝子対応の複数の
   運用計画のうち前記制約条件に対する評価値の高い運用
   計画を出力することを特徴とする請求項７記載の運行機
   材の運用計画作成システム。
9. 【請求項９】 出力した運用計画の基礎となった制約条
   件の変更に対し、変更後の制約条件を充足する運行機材
   の割当てを凍結する手段をさらに備え、制約条件を充足
   しない制約条件についてのみ前記割当て処理を行うこと
   を特徴とする請求項７または９記載のいずれかの運行機
   材の運用計画作成システム。
10. 【請求項１０】 前記運用計画を、運用番号と日付とか
    ら成る２次元マトリクス上の各メッシュに配したノード
    間の接続グラフとして編集し、出力する手段をさらに備
    えることを特徴とする請求項７〜９記載のいずれかの運
    行機材の運用計画作成システム。
11. 【請求項１１】 前記制約条件を、前記接続グラフの変
    更操作に従って変更する手段をさらに備えることを特徴
    とする請求項１０記載の運行機材の運用計画作成システ
    ム。
12. 【請求項１２】 前記制約条件は、運行機材を当日の運
    用番号のいずれかに割り当てる際の割当て制約と前日の
    特定の運用番号と当日の運用番号とを接続する際の接続
    制約とから成るものである請求項７〜１１記載のいずれ
    かの運行機材の運用計画作成システム。