(57)【特許請求の範囲】
【請求項１】
所定の区域に出入りする複数の移動体の当該区域内の留置計画を作成する留置計画作成装置において、
前記区域内の留置場所を示す場所情報及び前記各移動体の前記区域の出入り時刻を示す時刻情報から、前記留置計画の対象期間を区分した各時間帯で、前記区域内の各留置場所に留置される前記各移動体を表す場所・時間帯別情報を生成する場所・時間帯別情報生成手段と、
前記移動体が留置されることにより他の前記移動体の移動に支障を与える前記区域内の留置場所の関係を規定する移動支障情報を入力し、前記場所・時間帯別情報生成手段に生成された場所・時間帯別情報に基づいて、前記各移動体を前記各時間帯で留置する留置場所が、前記移動支障情報に規定された前記区域内の留置場所の関係に該当しないように、前記各時間帯における前記区域内での前記各移動体の移動を制約する制約式を生成する移動制約生成手段と、
前記区域内から前記制約式を充足する前記移動体の留置場所を探索して前記留置計画を作成する留置場所探索手段と、
前記場所・時間帯別情報生成手段に生成された場所・時間帯別情報における前記各時間帯で移動する前記移動体の数が均等になるように、前記留置計画の対象期間を区分する数及び前記時間帯の幅を調整する時間帯区分調整手段とを備えた
ことを特徴とする留置計画作成装置。
【請求項２】
所定の区域に出入りする複数の移動体の当該区域内の留置計画を作成する留置計画作成装置において、
前記区域内の留置場所を示す場所情報及び前記各移動体の前記区域の出入り時刻を示す時刻情報から、前記留置計画の対象期間を区分した各時間帯で、前記区域内の各留置場所に留置される前記各移動体を表す場所・時間帯別情報を生成する場所・時間帯別情報生成手段と、
前記移動体が留置されることにより他の前記移動体の移動に支障を与える前記区域内の留置場所の関係を規定する移動支障情報を入力し、前記場所・時間帯別情報生成手段に生成された場所・時間帯別情報に基づいて、前記各移動体を前記各時間帯で留置する留置場所が、前記移動支障情報に規定された前記区域内の留置場所の関係に該当しないように、前記各時間帯における前記区域内での前記各移動体の移動を制約する制約式を生成する移動制約生成手段と、
前記区域内から前記制約式を充足する前記移動体の留置場所を探索して前記留置計画を作成する留置場所探索手段と、
前記場所・時間帯別情報生成手段に生成された場所・時間帯別情報における前記各時間帯の区分が前記移動体の出区時刻と入区時刻との間になるように、前記留置計画の対象期間を区分する数及び前記時間帯の幅を調整する時間帯区分調整手段とを備えた
ことを特徴とする留置計画作成装置。
【請求項３】
前記時間帯区分調整手段は、前記留置計画の対象期間に前記区域を出入りする前記移動体の数に応じて、当該対象期間において前記移動体の出区時刻と入区時刻との間に時間帯の区分を入れる箇所を決定することを特徴とする請求項２記載の留置計画作成装置。
【請求項４】
前記時間帯区分調整手段は、前記留置場所探索手段が前記移動制約を充足する留置計画を作成できなかった場合、前記留置計画の対象期間を区分する数を増やし、
前記場所・時間帯別情報生成手段は、前記時間帯区分調整手段によって増加された前記各時間帯で前記区域内の各留置場所に留置する前記各移動体を表す場所・時間帯別情報を生成し、
前記移動制約生成手段は、前記場所・時間帯別情報生成手段に生成された前記場所・時間帯別情報に基づいて、前記各移動体を前記各時間帯で留置する留置場所が、前記移動支障情報に規定された前記区域内の留置場所の関係に該当しないように、前記各時間帯における前記区域内での前記各移動体の移動を制約する制約式を生成し、
前記留置場所探索手段は、前記区域内から前記制約式を充足する前記移動体の留置場所を再び探索する
ことを特徴とする請求項１から請求項３のうちのいずれか１項記載の留置計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、鉄道等の交通機関や工場での物資の搬送、輸送機関等で使用する車両等の移動体の留置計画を作成する装置に関する。
【背景技術】
【０００２】
ある車両を車両基地から移動させる際にその進路上に他の車両が留置されていて移動に支障を来す場合、この支障となる車両（以下、支障車両と呼ぶ）を他へ移動させる必要がある。また、運行計画に従ってある車両を車両基地へ移動させる際にその進路上に支障車両が留置されている場合も同様に支障車両を他へ移動させる必要がある。このような支障車両の移動は、運行上、本質的に必要とされる移動ではないので、こうした移動が発生しないように、すなわち支障車両がなくなるように配慮された留置場所の決定を行うことが望ましい。
【０００３】
例えば、特許文献１には、鉄道の車両基地構内における車両の編成の入れ換えや構内作業の計画を作成する装置の一環として、制約論理プログラミングを用いて鉄道車両の各編成の留置場所の計画を作成する装置が記載されている。この装置は、鉄道車両の編成の車両基地への到着時刻及び出発時刻と当該車両基地の構造とを考慮して支障車両のない留置計画を作成している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１７８７４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に代表される従来の技術は、制約論理プログラミングを用いて、車両基地における鉄道車両の留置場所の支障関係を制約式で表現することにより、この制約式で探索した制約充足解から、鉄道車両間で支障のない留置場所が決定された留置計画を作成することができる。
【０００６】
しかしながら、従来の技術では、ある運行計画に従って移動する移動体Ａの基地からの出発や基地への到着に際し、同様に運行計画に従って移動する他の移動体Ｂが留置されている場所を通過しない、という条件を表現するには「移動体Ａが到着時又は出発時に通過する場所に移動体Ｂが留置されるならば、移動体Ａと移動体Ｂとの到着時刻及び出発時刻が、互いに支障とならない関係を満たす」という制約式を、任意の移動体Ａと移動体Ｂとの組み合わせに対して設定する必要がある。
【０００７】
このように、任意の２つの移動体の組み合わせに対して制約式を設定する必要があると、対象の移動体の数が増えた場合、移動体数の２乗に比例して制約式が増加する。
例えば、鉄道車両の編成について留置計画を作成する場合、留置計画作成対象の編成群における編成の数の２乗に比例して制約式が増加することになる。
このため、留置計画の作成で消費される計算機の記憶領域と計算時間が増大して実用的な速度で留置計画を作成することが困難になるという課題があった。
【０００８】
この発明は、上記のような課題を解決するためになされたもので、所定の区域を出入りする移動体の当該区域内での留置計画を迅速かつ確実に作成することができる留置計画作成装置を得ることを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係る留置計画作成装置は、所定の区域に出入りする複数の移動体の当該区域内の留置計画を作成する留置計画作成装置において、区域内の留置場所を示す場所情報及び各移動体の区域の出入り時刻を示す時刻情報から、留置計画の対象期間を区分した各時間帯で、区域内の各留置場所に留置される各移動体を表す場所・時間帯別情報を生成する場所・時間帯別情報生成手段と、移動体が留置されることにより他の移動体の移動に支障を与える区域内の留置場所の関係を規定する移動支障情報を入力し、場所・時間帯別情報生成手段に生成された場所・時間帯別情報に基づいて、各移動体を各時間帯で留置する留置場所が、移動支障情報に規定された区域内の留置場所の関係に該当しないように、各時間帯における区域内での各移動体の移動を制約する制約式を生成する移動制約生成手段と、区域内から制約式を充足する移動体の留置場所を探索して留置計画を作成する留置場所探索手段と、場所・時間帯別情報生成手段に生成された場所・時間帯別情報における各時間帯で移動する移動体の数が均等になるように、留置計画の対象期間を区分する数及び時間帯の幅を調整する時間帯区分調整手段とを備えたことを特徴とする。
【発明の効果】
【００１０】
この発明によれば、所定の区域を出入りする移動体の当該区域内の留置計画を、対象となる移動体の数が増えても実用的な速度で確実に作成することができるという従来にない顕著な効果が得られる。
【図面の簡単な説明】
【００１１】
【図１】この発明の実施の形態１が適用される鉄道の車両基地の構成例を示す図である。
【図２】図１の車両基地における車両の編成の留置例を示す図である。
【図３】この発明の実施の形態１による留置計画作成装置の構成を示すブロック図である。
【図４】場所・時間帯別機材情報の一例を示す図である。
【図５】機材間の出発と到着の関係の一例を説明するための図である。
【図６】機材間の出発と到着の関係の他の例を説明するための図である。
【図７】実施の形態１が適用される鉄道の車両基地の他の構成例を示す図である。
【図８】この発明の実施の形態２による留置計画作成装置の構成を示すブロック図である。
【発明を実施するための形態】
【００１２】
実施の形態１．
以降では、この発明の留置計画作成装置を、鉄道の車両基地内に車両の編成を留置する留置計画の作成装置に適用した場合を例に挙げる。
図１は、留置計画の対象となる鉄道の車両基地の構成例を示す図である。図１中の実線が線路を示しており、この線路を介して基地出入口１１１に各番線１０１〜１１０が接続されている。また、これら番線１０１〜１１０に車両の編成が留置される。
【００１３】
図２は、図１の車両基地における車両の編成の留置例を示す図であり、車両の編成を矩形ブロックで記載している。図２においては、同一の線路上で縦列に２本の編成を留置することができる。例えば、編成２０３は編成２０２よりも奥に止まっている。この場合、編成２０３を車両基地から出発するに際して、編成２０２を先に移動させておかなければならない。このような移動作業を入換と呼び、これを実施するためには多大なエネルギーを消費し、編成２０１〜２０５の構内移動を担当する運転士をそれぞれ割り当てなければならず、少なからず手間がかかる。従って、なるべく余計な入換が発生しないような編成の留置場所を選択することが望ましい。
【００１４】
大抵の鉄道では、昼間に多くの列車が運行しており、夜間は列車の運行があまりない。また、夜間になると、その日の運行を終えた車両の編成が、車両基地へ引き揚げてきて、車両基地構内に多くの編成が留置される。そして、翌日に車両基地を再び出発してその日の運行に就く。従って、車両の編成が車両基地へ到着する順序や車両基地を出発する順序は、その編成がその日にどのような運行を担当するかに依存しており、車両基地の留置計画を作成する段階では既に決定されている。
【００１５】
本発明は、既に与えられている基地の構造に関する情報及び車両の編成の運行に関する情報に基づいて、入換作業のない車両基地構内の留置計画を作成する。
なお、以下の説明では、鉄道の車両基地のような所定の区域を出入りする鉄道車両等の移動体を機材と呼び、当該移動体と同一の意味で適宜記載している。
つまり、「機材の運行」という記載は、移動体の運行を意味し、「機材の基地への到着及び出発」という記載は、当移動体の基地への到着及び出発を意味している。
また、「機材Ａと機材Ｂが同じ」とは、移動体Ａ，Ｂが同じ場合を示し、「機材Ａと機材Ｂが異なる」とは、移動体Ａと移動体Ｂがそれぞれ別個に移動する場合を示している。
【００１６】
図３は、この発明の実施の形態１による留置計画作成装置の構成を示すブロック図である。基地の構造に関する情報は、留置場所に関する情報と移動支障に関する情報から構成される。図３において、留置計画作成装置３００の入力として与えられる情報は、留置場所情報３０１、機材の到着／出発時刻情報３０２、移動支障情報３０３である。
【００１７】
留置場所情報３０１は、留置場所に関する情報であり、留置計画作成対象となる基地内の全ての留置場所を示す情報である。
機材の到着／出発時刻情報３０２は、機材の運行に関する情報であり、留置計画作成対象の各機材が基地へ到着する到着時刻と各機材が基地から出発する出発時刻を示している。
移動支障情報３０３は、移動支障に関する情報であり、留置計画作成対象となる基地において、機材が留置されると、互いの移動に支障を来す関係（以下、支障関係と呼ぶ）にある留置場所を示す情報である。
【００１８】
位置情報３０９は、留置計画作成対象となる基地内の留置場所のうち、機材を留置する場所を示す情報であり、留置場所に関する情報に相当する。
場所・時間帯別機材情報３１０は、留置計画作成対象の基地内の各留置場所を各時間帯に使用する機材を示す情報であり、機材の運行に関する情報に相当する。
【００１９】
位置情報初期化手段３０４は、留置場所情報３０１に基づいて留置計画作成対象となる基地の位置情報３０９を初期化する構成部である。なお、位置情報３０９の初期化とは、留置場所情報３０１で与えられる留置場所を、留置計画作成対象の基地内で各機材が留置され得る位置として保持する位置情報３０９を生成する処理に相当する。つまり、初期化の際は、留置場所情報３０１で与えられる留置場所を示す変数とこれに留置される機材を示す変数とが関連付けられた情報として位置情報３０９が生成され、どの機材がどの場所に留置されるかは決定されていない。
【００２０】
場所・時間帯別機材情報初期化手段（場所・時間帯別情報生成手段）３０５は、留置場所情報（場所情報）３０１と機材の到着／出発時刻情報（時刻情報）３０２に基づいて、場所・時間帯別機材情報（場所・時間帯別情報）３１０を初期化する構成部である。
なお、場所・時間帯別機材情報３１０の初期化とは、留置場所情報３０１及び機材の到着／出発時刻情報３０２から、留置計画の対象期間を区分した各時間帯で、基地内の各留置場所に留置される各機材を変数で表した場所・時間帯別機材情報３１０を生成する処理に相当する。
また、場所・時間帯別機材情報初期化手段３０５は、場所・時間帯別機材情報３１０に設定した各機材の到着時刻及び出発時刻における時間帯での留置場所を、初期化後の位置情報３０９と関連付ける。
【００２１】
移動制約生成手段３０６は、機材の到着／出発時刻情報３０２、移動支障情報３０３、及び場所・時間帯別機材情報３１０に基づいて、各機材の各時間帯での留置場所への到着時の移動及び当該留置場所からの出発時の移動が、別の機材との間で支障関係にならないような移動支障制約を生成する構成部である。移動支障制約の詳細については後述する。
【００２２】
留置場所探索手段３０７は、移動制約生成手段３０６で生成された移動支障制約に基づいて、位置情報３０９で与えられる留置場所のうちから、移動支障制約を満たす留置場所を解として探索する構成部である。また、留置場所探索手段３０７は、位置情報３０９に対して探索結果３０８の機材の留置場所を設定する。
【００２３】
なお、位置情報初期化手段３０４、場所・時間帯別機材情報初期化手段３０５、移動制約手段３０６及び留置場所探索手段３０７は、例えば、この発明の趣旨に従う留置計画作成プログラムを計算機に実行させることにより、ハードウェアとソフトウェアが協働した具体的な手段として実現される。つまり、上記の手段３０４〜３０７の機能は、上記留置計画作成プログラムの各プログラムモジュールに規定される。
【００２４】
また、留置場所情報３０１、機材の到着／出発時刻情報３０２、移動支障情報３０３、位置情報３０９及び場所・時間帯別機材情報３１０は、例えば、上記計算機に搭載された記憶装置に記憶される。記憶装置としては、ハードディスク装置、半導体メモリ、ＣＤやＤＶＤ等の記憶メディアのドライブ装置等が挙げられる。
【００２５】
次に動作について説明する。
先ず、位置情報初期化手段３０４が、留置場所情報３０１を入力すると、当該留置場所情報３０１に基づいて、留置計画作成対象の基地で各機材が留置され得る留置場所が規定された情報を、位置情報３０９として生成する。具体的には、位置情報初期化手段３０４は、留置場所情報３０１で与えられる留置場所を元とした基地内の全ての留置場所の集合をＴとし、機材数をｎ、各機材をＦ１〜Ｆｎ、添字ｋを１からｎまでの任意の値として、Ｔ（Ｆｋ）∈Ｔで定義される位置情報３０９を生成する。なお、Ｔ（Ｆｋ）は、機材Ｆｋを留置する場所を表しており、集合Ｔに含まれる任意の留置場所となり得て、後述する移動支障制約の解の探索によって具体的な留置場所が決定される。また、特定の機材については特定の留置場所を使用できないといった制限がある場合に、例えば、機材Ｆｋが留置場所Ｔ’を使用できないときは、Ｔ（Ｆｋ）≠Ｔ’のような制約式を設定しておくこともできる。
【００２６】
次に、場所・時間帯別機材情報初期化手段３０５が、留置場所情報３０１及び機材の到着／出発時刻情報３０２を入力し、留置場所情報３０１で与えられる基地内の各留置場所を、機材の到着／出発時刻情報３０２で与えられる到着時刻及び出発時刻における各時間帯に使用する機材を表す中間変数として場所・時間帯別機材情報３１０を生成する。
また、場所・時間帯別機材情報初期化手段３０５は、場所・時間帯別機材情報３１０に設定した留置場所と位置情報初期化手段３０４で生成された位置情報３０９の留置場所とを関連付ける。
【００２７】
なお、場所・時間帯別機材情報３１０が初期化された時点では、上記の変数に値が設定されておらず、不定値である。初期化の後に、留置場所探索手段３０７が探索を行う度に留置場所が順次決定され、当該留置場所に相当する値が上記変数に代入される。
場所・時間帯別機材情報３１０は、場所・時間帯別機材情報初期化手段３０５及び移動制約生成手段３０６による一連の処理で位置情報３０９との間に制約式を設定することにより、上記制約式が示す制約を遵守した留置場所を決定する媒介として機能する。
【００２８】
図４は、場所・時間帯別機材情報の一例を示す図であり、留置計画の対象の日を４つの時間帯に区分して、各時間帯１〜４の各場所１〜１０に所在する機材を示している。図４に示すテーブルデータのうち、場所と時間帯とで特定される１〜７の数値は、機材に割り当てた固有の番号である。すなわち、時間帯２の場所１には、番号“５”の機材が留置される。場所・時間帯別機材情報３１０を示すテーブルデータは、実際は計算機のメモリ上のデータとして表現される。
【００２９】
また、図４の＊印は、機材が所在していない、あるいは未定であることを示している。従って、時間帯１の場所１には機材が所在しておらず、時間帯２から時間帯４までの場所１には番号“５”の機材が所在している。
なお、時間帯２から時間帯４までの場所１に番号“５”の機材が所在していると述べたが、これらの時間帯全体にわたって所在しているとは限らず、例えば、時間帯２の途中で場所１に到着した場合や時間帯４の途中で場所１から出発した場合も含まれる。
【００３０】
場所・時間帯別機材情報初期化手段３０５は、時間帯ｌの留置場所ｐに所在する機材をＰ（ｐ，ｌ）と表現した情報を、場所・時間帯別機材情報３１０として生成する。
機材の到着／出発時刻情報３０２により各機材の到着時刻及び出発時刻は所与であるので、場所・時間帯別機材情報初期化手段３０５は、機材Ｆｋの到着時刻をＡｋとし、機材Ｆｋを留置する場所をＴ（Ｆｋ）とし、出発時刻をＤｋとし、添字ｋを１からｎまでの任意の値とし、ｌを時刻Ａｋから時刻Ｄｋまでの時間帯とすると、場所・時間帯別機材情報３１０に対して、下記の制約式（１）を設定する。
Ｐ（Ｔ（Ｆｋ），ｌ）＝Ｆｋ      ・・・（１）
【００３１】
後述するように留置場所探索手段３０７によって、位置情報３０９の値が具体的に決定されていくと、上記の制約式を通じて、図４に示すように場所・時間帯別機材情報３１０のテーブルデータに値が代入されていくことになる。
なお、ある時間帯のある留置場所に存在する機材を表す変数は１つしかない。従って、上記の制約式を設定することによって、間接的に同じ時間帯の同じ留置場所に複数の機材が存在しないという制約を実現することができる。
ある時間帯及び場所にどの機材も存在していない場合は、この制約式が働かないので、場所・時間帯別機材情報３１０の値は不定となる。
【００３２】
続いて、移動制約生成手段３０６は、機材の到着／出発時刻情報３０２、移動支障情報３０３及び場所・時間帯別機材情報３１０を入力して、機材の到着／出発時刻情報３０２及び場所・時間帯別機材情報３１０で与えられる、各機材の各時間帯での留置場所への到着時及び当該留置場所からの出発時の移動が、移動支障情報３０３に示した支障関係にならないように移動支障制約を生成する。
例えば、移動支障情報３０３において、ある機材が留置場所ｐに到着する際に、留置場所ｑに機材が存在すると、留置場所ｐへの移動に支障を来すことが規定されている場合、移動制約生成手段３０６は、機材Ｆｋが留置場所ｐに到着する到着時刻をＡＴ（Ｆｋ）として、時間帯ｌについて下記式（２）で表現される制約を生成する。
ＡＴ（Ｐ（ｐ，ｌ））＜ＡＴ（Ｐ（ｑ，ｌ））      ・・・（２）
【００３３】
上記制約式（２）の制約が成り立てば、ある機材の留置場所ｑへの到着時刻が機材Ｆｋの留置場所ｐへの到着時刻よりも後になる。このため、機材Ｆｋが留置場所ｐへ到着する際に留置場所ｑに機材は存在せず、支障にならない。また、留置場所ｐ又は留置場所ｑに留置される機材が存在しない場合、Ｐ（ｐ，ｌ）又はＰ（ｑ，ｌ）が不定値となるため、制約式（２）の制約はなくなる。
【００３４】
一方、移動支障情報３０３において、ある機材が留置場所ｐから出発する際に、留置場所ｑに機材が存在すると留置場所ｐからの移動に支障を来すことが規定されている場合、移動制約生成手段３０６は、機材Ｆｋの出発時刻をＤＴ（Ｆｋ）として、時間帯ｌについて下記式（３）で表現される制約を生成する。
ＤＴ（Ｐ（ｑ，ｌ））＜ＤＴ（Ｐ（ｐ，ｌ））      ・・・（３）
【００３５】
上記制約式（３）の制約が成り立てば、ある機材の留置場所ｑからの出発時刻が、機材Ｆｋの留置場所ｐからの出発時刻よりも先になる。このため、機材Ｆｋが留置場所ｐから出発する際に留置場所ｑに機材は存在せず、支障にならない。
【００３６】
図５は、機材間の出発と到着の関係の一例を説明するための図である。図５の上側の図は、ある機材Ａが留置場所ｑに到着してから出発するまでの期間５０４を時間軸５０１上に記載したものである。ここで、時刻５０２が留置場所ｑへの到着時刻であり、時刻５０２が留置場所ｑからの出発時刻である。同様に、図５の下側の図は、機材Ａとは異なる、機材Ｂが留置場所ｐに到着してから出発するまでの期間５０８を時間軸５０５上に記載したものである。ここで、時刻５０６が留置場所ｐへの到着時刻であり、時刻５０７が留置場所ｐからの出発時刻である。
【００３７】
図５に示す時間軸５０１，５０５は同一期間を示しているので、機材Ａが留置場所ｑに到着する時刻５０２は、機材Ｂが留置場所ｐに到着する時刻５０６よりも遅く、機材Ａが留置場所ｑから出発する時刻５０３は、機材Ｂが留置場所ｐから出発する時刻５０８よりも早い。このため、留置場所ｑに留置される機材Ａは、留置場所ｐに留置される機材Ｂの出入りに対する支障とはならない。この関係は、制約式（２）と制約式（３）との論理積を算出することにより表現できる。
【００３８】
図６は、機材間の出発と到着の関係の他の例を説明するための図である。図６の上側の図は、図５と同様に、ある機材Ｃが留置場所ｑに到着してから出発するまでの期間６０４と次に機材Ｃが留置場所ｑに到着してから出発するまでの期間６０５とを時間軸６０１上に記載したものである。ここで、時刻６０２は、期間６０４だけ留置していた機材Ｃが留置場所ｑから出発した時刻であり、時刻６０３は、機材Ｃが留置場所ｑに戻ってきた到着時刻である。同様に、図６の下側の図は、機材Ｃとは異なる機材Ｄが留置場所ｐに到着してから出発するまでの期間６０９と次に機材Ｄが留置場所ｐに到着してから出発するまでの期間６１０とを時間軸６０６上に記載したものである。時刻６０７は、期間６０９だけ留置していた機材Ｄが留置場所ｐから出発した時刻であり、時刻６０８は、機材Ｄが留置場所ｐに戻ってきた到着時刻である。
【００３９】
図６に示す機材間の出発と到着の関係は、例えば機材が留置場所を朝方出発して夕方に同じ留置場所へ帰ってくる場合に相当する。この場合においても、上述の２つの制約式の条件を適用することができる。また、朝方に出発する機材と夕方に到着する機材とが別のものであっても、場所・時間帯別機材情報３１０は、時間帯を区切って機材の情報を保持しているので、出発時と到着時との時間帯が異なっていれば、制約式（２）及び制約式（３）の条件をそのまま適用できる。
【００４０】
留置計画の対象期間が１日単位である場合、対象日の前日や翌日との接続条件を考える必要がある。この場合においても、例えば、前日から同じ場所に留置されている機材について、到着時刻ＡＴ（Ｆｋ）に前日の時刻を与えることにより、同様の制約式で支障条件を表現できる。出発時刻ＤＴ（Ｆｋ）についても同様である。
【００４１】
留置場所ｐと留置場所ｑとが支障関係にあるかどうかは、所与の基地の構造から定まる固定的な関係であり、移動支障情報３０３を参照すればよい。そのような留置場所ｐ，ｑの全ての組み合わせについて、全ての時間帯ｌに対して、制約式（２）と制約式（３）との論理積を制約条件として設定すれば、到着時及び出発時に支障機材がないという条件を設定することができる。また、３箇所以上の留置場所が支障関係にある場合であっても、その全ての組み合わせについて、これらの制約式を設定すればよい。
【００４２】
従来の移動支障制約は、基地内で各機材が留置され得る留置場所を直接参照した制約式で表現されていた。この場合に、実際に各機材をどの留置場所に留置するかは、移動支障制約に基づいた留置場所の探索により決定されるので、従来は、留置計画作成対象の全ての機材の組み合わせに対して「支障関係にある場所に機材が留置されているならば、出発時刻及び到着時刻の関係が支障とならない条件を満たす」という制約を設定する必要があった。このため、機材数の２乗に比例する数の制約式を設定しなければならなかった。
例えば、図２において、編成２０１と編成２０２が支障関係にならない制約を示す制約式、編成２０１と編成２０３が支障関係にならない制約を示す制約式、・・・というように全ての編成の組み合わせに対する制約式を生成する必要がある。図２の例では、全部で５本の編成２０１〜２０５について、合計１０個の制約式を設定しなければならない。
【００４３】
これに対して、本発明は、各時間帯に各場所に留置されている機材を表す変数として、場所・時間帯別機材情報３１０を用意し、この場所・時間帯別機材情報３１０に基づいて実際に支障関係にある場所の組み合わせに対してのみ「出発時刻及び到着時刻の関係が支障とならない条件を満たす」という制約を設定する。
例えば、図２に対応する図１では、番線１０１に留置する編成と番線１０２に留置する編成とが支障関係にないという制約式、番線１０３に留置する編成と番線１０４に留置する編成とが支障関係にないという制約式、番線１０５に留置する編成と番線１０６に留置する編成とが支障関係にないという制約式、・・・というように、全ての支障関係にある番線の組み合わせに対して制約式が設定される。つまり、支障関係にある番線の組み合わせ（番線１０１，１０２、番線１０３，１０４、番線１０５，１０６、番線１０７，１０８、番線１０９，１１０）が５つあるので、５つの制約式を設定すればよい。
【００４４】
このように、本発明では、移動支障情報３０３を参照して互いに支障関係にある場所の組み合わせに対してのみ制約式を設定するので、機材数が留置場所の数と比べてとても少ないような事例を除けば、従来の技術に比べて制約式の数を大幅に減らすことができる。また、機材数が留置場所の数と比べてとても少ない場合であっても、移動支障のない留置計画の作成は、とても簡単であり、特段の工夫を必要としない。
【００４５】
留置場所探索手段３０７は、移動制約生成手段３０６によって生成された移動支障制約の制約充足解を探索する。この探索には、制約論理プログラミング等の既知の手法を利用することができる。制約論理プログラミングでは、変数間の制約関係を数式（制約式）で表現するとともに変数の値の選択肢をツリー構造で表す。このツリー構造の選択肢を順次辿り、制約条件を満たさない選択肢があるならばその枝の先の探索に見込みがないとして枝刈りを行い、見込みがある他の選択肢を辿れるところまでバックトラックを実施することにより、制約充足解が求まる。この制約論理プログラミングの過程において、制約式で表現された変数間の制約関係を他の変数にも伝播させる制約伝播を行うことで、探索範囲を狭めて制約充足解を高速に求めることができる。
【００４６】
なお、留置場所探索手段３０７に対して、制約論理プログラミングの手法に基づくバックトラックをそのまま実装しても、あるいは市販の汎用ライブラリを用いて実装してもよい。制約充足解が存在するならば、各機材の留置場所として適切な解の探索結果３０８が得られる。
【００４７】
以上のように、この実施の形態１によれば、基地内の留置場所を示す留置場所情報３０１及び各機材の基地への到着時刻及び出発時刻を示す機材の到着／出発時刻情報３０２から、留置計画の対象期間を区分した各時間帯で、基地内の各留置場所に留置される各機材を表す場所・時間帯別機材情報３１０を生成する場所・時間帯別情報初期化手段３０５と、機材が留置されることにより他の機材の移動に支障を与える基地内の留置場所の関係を規定する移動支障情報３０３を入力し、場所・時間帯別情報初期化手段３０５に生成された場所・時間帯別機材情報３１０に基づいて、各機材を各時間帯で留置する留置場所が、移動支障情報３０３に規定された基地内の留置場所の関係に該当しないように、各時間帯における基地内での各機材の移動を制約する制約式の移動支障制約を生成する移動制約生成手段３０６と、基地内から移動支障制約の制約式を充足する機材の留置場所を探索して留置計画を作成する留置場所探索手段３０７とを備える。
このように場所・時間帯別機材情報３１０に基づいて、留置計画の対象期間を区分した各時間帯で機材の基地での移動に制約を設定することで、制約式の数が機材数の２乗に比例して増加することを回避できる。これにより、問題規模の増加に伴って制約充足解を求めるために必要な計算能力と記憶能力とが２乗で増大することが避けられ、実用性を向上できる。
【００４８】
また、上記実施の形態１において、基地の構造に応じた移動支障制約を設定する必要がある。図７は、実施の形態１が適用される鉄道の車両基地の他の構成例を示す図である。図７に示す例では、基地出入口７１１が番線７０１，７０３，７０５，７０７，７０９に接続し、これらの番線に続く番線７０２，７０４，７０６，７０８，７１０にも基地出入口７１２が接続している。実施の鉄道の車両基地においては、図１に示したように、基地出入口が１つの場合だけでなく、図７のように複数の基地出入口が存在する場合がある。この場合、到着時と出発時の方向、すなわちどの基地出入口を使用するかによって、車両の編成の移動に支障となるか否かが変化する。
【００４９】
また、移動制約生成手段３０６は、各機材を各時間帯で留置する留置場所が、移動支障情報３０３が規定する基地内の留置場所の関係に該当しないように、各時間帯における基地内での各機材の所定方向（基地出入口の方向）の移動を制約する制約式である移動支障制約を生成する。
先ず、ｋを１からｎまでの任意の値とし、編成Ｆｋの出発の向きをＤＤ（Ｆｋ）とし、到着の向きをＤＡ（Ｆｋ）とする。また、ＤＤ（Ｆｋ）及びＤＡ（Ｆｋ）の値は、図７に示す基地の左側、つまり基地出入口７１１を使用して編成Ｆｋが出入りするとき“−１”となり、図７に示す基地の右側、つまり、基地出入口７１２を使用して編成Ｆｋが出入りするとき“１”となるものとする。
【００５０】
ここで、編成Ｆｉ，Ｆｊ（ｉ，ｊは１からｎまでの互いに異なる任意の値）について、編成Ｆｉが番線７０１に留置され、編成Ｆｊが番線７０２に留置される場合に、編成Ｆｉと編成Ｆｊの到着の向きがＤＡ（Ｆｉ）＝−１かつＤＡ（Ｆｊ）＝１であり、編成Ｆｉと編成Ｆｊの出発の向きがＤＤ（Ｆｉ）＝−１かつＤＤ（Ｆｊ）＝１である場合のみ、移動支障がなくなり、それ以外の到着及び出発の向きでは移動支障が発生する。
【００５１】
上述の条件を一般的に表現すると、制約式は、下記式（４）及び下記式（５）のようになる。ただし、番線を留置場所ｐ，ｑで表し、図７において場所ｐが場所ｑよりも左側にあるものとする。例えば、番線７０１，７０３，７０５，７０７，７０９が場所ｐに相当し、番線７０２，７０４，７０６，７０８，７１０が場所ｑに相当する。また、∧は論理積を表す記号であり、∨は論理和を表す記号である。
（１）到着時（時間帯ｌ）
（ＤＡ（Ｆ（ｐ，ｌ））
＝−１∧ＤＡ（Ｆ（ｑ，ｌ））＝１）∨ＡＴ（Ｆ（ｐ，ｌ））＜ＡＴ（Ｆ（ｑ，ｌ））
・・・（４）
（２）出発時（時間帯ｌ）
（ＤＤ（Ｆ（ｐ，ｌ））
＝−１∧ＤＤ（Ｆ（ｑ，ｌ））＝１）∨ＤＴ（Ｆ（ｑ，ｌ））＜ＤＴ（Ｆ（ｐ，ｌ））
・・・（５）
【００５２】
制約式（４）及び制約式（５）によって、場所ｐと場所ｑに留置される編成の到着及び出発方向が、互いに支障とならない向きであるか、もしくは、支障となる向きであっても時刻が重ならない、という条件を表現することができる。この後、留置場所探索手段３０７が、上記実施の形態１と同様にして、上記制約式（４）及び制約式（５）の制約充足解を探索することで、制約充足解が存在するならば、出発及び到着の方向を考慮した適切な解が得られる。これにより、基地に出入口が複数ある場合でも留置計画を作成することができる。
【００５３】
実施の形態２．
上記実施の形態１では、場所・時間帯別機材情報を用いて、各機材を、留置される場所に加え、留置される時間帯ごとに区別していた。これにより、留置の時間帯区分が異なる場合であれば、異なる機材が同じ場所に留置される状態も表現することが可能である。
一方、留置される時刻の時間帯区分が同じ場合には、たとえ実際には留置時刻がずれて支障とならずに留置可能であっても、複数の機材が同じ場所を続けて利用する状態を表現することはできない。
【００５４】
例えば、１０時から１４時までが１つの時間帯であるとき、機材Ａが１１時に出発し、機材Ｂが１３時に到着するならば、機材Ａが使っていた留置場所に機材Ｂを留置することは実際には可能である。しかしながら、上記実施の形態１では、機材Ａ，Ｂの留置場所の利用が同じ時間帯になるため、いわゆる“留置時間の量子化”により、留置不可能と判定される。
【００５５】
また、時間帯区分の数を増やして時間帯を細かく分割すれば、上述の問題を回避できるが、時間帯区分の増加に伴って制約式の数も増えてしまう。つまり、場所・時間帯別機材情報３１０によって機材数の２乗に比例した制約式の増加を回避した意味がなくなる。
このように、時間帯区分の設定は、実行可能な解を見逃さず、かつ制約式の数の増大を抑えて計算時間を適切な範囲に収めるために重要な意味がある。
すなわち、時間帯区分の設定を変更可能として、問題の性質又は試行した計算の状況に応じて調整すれば、制約充足解の見逃しの回避と計算時間の縮減との両立を図ることができる。
【００５６】
また、各時間帯の長さを等しく区分しなくてもよい。例えば、機材の到着と出発の数が多い時間帯を細かく区分し、機材の到着と出発の数が少ない時間帯は粗く区分すれば、複数の機材が続けて同じ場所を利用するような事例において、機材が互いに異なる時間帯に区分されるように分解能を調整することができる。
【００５７】
図８は、この発明の実施の形態２による留置計画作成装置の構成を示すブロック図である。なお、図８において、図３と同一の構成要素には同一符号を付して重複する説明を省略する。留置計画作成装置３００Ａには、実施の形態２に特有な構成として、時間帯区分調整手段３１１が設けられる。時間帯区分における時間帯幅の分解能の調整は、対象基地内の留置場所に対する機材の到着と出発の数を参照して、各機材の到着と出発の数が多い時間帯を細かく区分し、機材の到着と出発の数が少ない時間帯を粗く区分する。
【００５８】
時間帯区分調整手段３１１は、上述のような時間帯区分の分解能の調整を行うために、機材の到着／出発時刻情報３０２を参照して留置計画作成期間全体での機材の出発と到着の数を数え上げ、それを時間帯区分の数で除算することにより、各時間帯に同じ数の出発及び到着が含まれるように時間帯幅を調整する。時間帯幅を調整した時間帯区分に関する情報は、時間帯区分情報３１２として留置計画作成装置３００Ａのメモリに保持される。
【００５９】
場所・時間帯別機材情報初期化手段３０５ａは、留置場所情報３０１と機材の到着／出発時刻情報３０２に加え、時間帯区分調整手段３１１が生成した時間帯区分情報３１２を入力して、留置場所情報３０１で特定される基地内の留置場所を、機材の到着／出発時刻情報３０２及び時間帯区分情報３１２にそれぞれ規定された各時間帯に使用する機材を表す中間変数として、場所・時間帯別機材情報３１０ａを生成する。
【００６０】
移動制約生成手段３０６ａは、機材の到着／出発時刻情報３０２、移動支障情報３０３及び場所・時間帯別機材情報３１０ａに基づいて、各機材の各時間帯での留置場所への到着時の移動及び当該留置場所からの出発時の移動が、別の機材との間で支障関係にならないような移動支障制約を生成する。
留置場所探索手段３０７ａは、移動制約生成手段３０６ａで生成された移動支障制約に基づいて、位置情報３０９で与えられる留置場所のうちから、移動支障制約を満たす留置場所を解として探索する。
上述のように機材の到着と出発の数が多い時間帯で時間帯幅の分解能を上げることで、時間帯区分の数の増加が抑えられ、移動制約生成手段３０６ａが設定すべき制約式の数の増大を抑えることができる。
【００６１】
機材の基地からの出発は、基地内の留置場所の使用終了に相当し、機材の基地への到着は、基地内の留置場所の使用開始に相当する。上述の留置時間の量子化では、機材が出発して留置場所の使用が既に終了しているにもかかわらず、その後に到着した機材をその留置場所に留置できないことに問題がある。従って、機材の出発時刻と到着時刻の間に時間帯の区切りがあれば、出発する機材の留置時間と到着した機材の留置時間が重なって支障関係にあると判断されることはない。
【００６２】
一方で、同一時刻にある機材が留置場所へ到着し別の機材が同じ留置場所へ到着する場合、あるいは同一時刻にある機材が留置場所から出発し別の機材が同じ留置場所から出発する場合は元々留置時間が重なっており、移動支障が発生する場合に相当する。この場合には、機材の出発時刻と到着時刻の間に時間帯の区切りを入れても意味がない。
また、同一時刻に、ある機材が留置場所へ到着し別の機材が同じ留置場所から出発する場合においても元々留置時間が重なっており、移動支障が発生する場合に相当する。この場合には、機材の出発時刻と到着時刻の間に時間帯の区切りを入れても意味がない。
さらに、同じ機材が留置場所へ到着する場合と出発する場合は、到着時刻と出発時刻との間に時間帯の区切りを入れても入れなくても移動支障と判定されることはない。
そこで、この実施の形態２では、時間帯区分調整手段３１１が、機材の到着／出発時刻情報３０２に基づいて時間帯区分情報３１２を生成する際に、機材の基地への到着時刻と当該基地からの出発時刻との間に時間帯の区切りを入れる。これにより、上述の留置時間の量子化による問題を完全に回避できる。
【００６３】
なお、留置計画の対象期間に機材の到着及び出発の数が十分少なければ、全ての機材の到着時刻と出発時刻との間に時間帯の区切りを入れる。
一方、所定数以上の数がある場合には、各時間帯に含まれる機材の出発及び到着の数ができるだけ均等になるように機材の到着時刻と出発時刻との間に時間帯の区切りを入れる方法や、基地に所在する機材の数が多い時間帯で機材の到着時刻と出発時刻との間に時間帯の区切りを入れる方法が考えられる。
【００６４】
機材の到着時刻及び出発時刻は、機材の到着／出発時刻情報３０２により全て所与であるので、時間帯ごとに基地内に存在している機材の数は簡単に求められる。また、基地内に所在する機材の数が多いほど留置場所の需要が高いと考えられる。
そこで、時間帯区分調整手段３１１が、基地内に所在する機材の数が所定値以上の時間帯から優先的に時間帯を区分してもよい。これにより、制約充足解を発見し易くなることが期待できる。
【００６５】
また、留置計画作成期間の時間帯区分の数が少なすぎると、複数の機材の留置場所の利用が同じ時間帯となり、留置時間の量子化から実際には支障となっていない場合でも支障と判定されて、制約充足解を発見できない可能性がある。この場合は、時間帯区分の数を増やして再度探索を行えば、制約充足解を発見できる可能性がある。
そこで、この実施の形態２では、制約充足解を発見できずに探索終了した場合、留置計画作成期間の時間帯区分の数を増加させてから再度探索を行う。すなわち、留置場所探索手段３０７ａが、制約充足解を発見できずに探索を終了すると、その旨を時間帯区分調整手段３１１に通知する。時間帯区分調整手段３１１は、当該通知を受けると、留置計画作成期間の時間帯区分の数を所定数だけ増加させた時間帯区分情報３１２を生成する。この時間帯区分情報３１２に基づいて、移動支障制約を設定し、その制約式で留置場所を再度探索する。これにより、制約充足解を発見できる可能性を高めることができる。
【００６６】
以上のように、この実施の形態２によれば、場所・時間帯別機材情報初期化手段３０５ａに生成された場所・時間帯別機材情報３１０ａにおける各時間帯で移動する機材の数が均等になるように、留置計画の対象期間を区分する数及び時間帯の幅を調整する時間帯区分調整手段３１１を備える。このように、問題条件に応じて制約充足解が得られるように、留置計画の対象期間の区分を自動的に調整することで、計算時間を縮減することができる。
【００６７】
さらに、この実施の形態２によれば、場所・時間帯別機材情報初期化手段３０５ａに生成された場所・時間帯別機材情報３１０ａにおける各時間帯の区分が機材の出発時刻（出区時刻）と到着時刻（入区時刻）との間になるように、留置計画の対象期間を区分する数及び時間帯の幅を調整する時間帯区分調整手段３１１を備える。これにより、いわゆる留置時間の量子化が問題となる場合に留置計画の対象期間の時間帯区分を設定できる。
【００６８】
さらに、この実施の形態２によれば、時間帯区分調整手段３１１が、留置計画の対象期間に基地に到着及び出発する機材の数に応じて、当該対象期間において機材の出発時刻と到着時刻との間に時間帯の区分を入れる箇所を決定する。これにより、時間帯区分を設定するにあたり、基地内の機材の数を参考にしてより的確に区分の設定箇所を判断することができる。
【００６９】
さらに、この実施の形態２によれば、時間帯区分調整手段３１１が、留置場所探索手段３０７ａが移動支障制約を充足する留置計画を作成できなかった場合、留置計画の対象期間を区分する数を増やし、場所・時間帯別機材情報初期化手段３０５ａが、時間帯区分調整手段３１１によって増加された各時間帯で基地内の各留置場所に留置する各機材を表す場所・時間帯別機材情報３１０ａを生成し、移動制約生成手段３０６ａが、場所・時間帯別機材情報初期化手段３０５ａに生成された場所・時間帯別機材情報３１０ａに基づいて、各機材を各時間帯で留置する留置場所が、移動支障情報３０３に規定された基地内の留置場所の関係に該当しないように、各時間帯における基地内での各機材の移動を制約する制約式の移動支障制約を生成し、留置場所探索手段３０７ａが、基地内から、移動支障制約の制約式を充足する機材の留置場所を再び探索する。このように、移動支障制約を充足する留置計画を作成できなかった場合は、時間帯の数を増やして再度留置計画作成を試みる。これにより、制約充足解を発見できない場合に再試行できるようになる。
【００７０】
上記実施の形態１，２では、留置計画作成対象が鉄道車両の編成である場合を例に挙げて説明したが、本発明は、これに限定されるものではない。つまり、所与の到着時刻及び出発時刻で基地を出入りする移動体であれば、本発明を適用できる。また、移動体には、人、車両、鉄道、船舶又は航空機等が含まれる。例えば、駐車場での駐車車両の配置や、空港での航空機の配置にも応用可能である。
【００７１】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００７２】
１０１〜１１０，７０１〜７１０  番線（留置場所）、１１１，７１１，７１２  基地出入口、２０１〜２０５  車両の編成（移動体）、３００，３００Ａ  留置計画作成装置、３０１  留置場所情報（場所情報）、３０２  機材の到着／出発時刻情報（時刻情報）、３０３  移動支障情報、３０４  位置情報初期化手段、３０５，３０５ａ  場所・時間帯別機材情報初期化手段（場所・時間帯別情報生成手段）、３０６，３０６ａ  移動制約生成手段、３０７，３０７ａ  留置場所探索手段、３０８，３０８ａ  探索結果、３０９  位置情報、３１０，３１０ａ  場所・時間帯別機材情報（場所・時間帯別情報）、３１１  時間帯区分調整手段、３１２  時間帯区分情報。
【図１】
0005449107.tif 000002
【図２】
0005449107.tif 000003
【図３】
0005449107.tif 000004
【図４】
0005449107.tif 000005
【図５】
0005449107.tif 000006
【図６】
0005449107.tif 000007
【図７】
0005449107.tif 000008
【図８】
0005449107.tif 000009