運行機材又は乗務員の運用計画作成装置
【課題】計画作成者の置かれた状況（基本計画作成時はある程度時間をかけても評価値の良い計画を作成したい、ダイヤが乱れた時は評価値が少し悪くても短時間で計画を作成したいなどの状況）に応じた最適な計画を立案することができる運行機材又は乗務員の運用計画作成装置を提供する。
【解決手段】運行機材又は乗務員の運用計画作成装置において、計画作成のための許容時間を格納する許容時間格納部と、計画作成手段毎の特徴情報（乗務数と計算時間、計画の質の関係など）を格納する作成手段特徴格納部とを備えることにより、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができるようにした。
【解決手段】運行機材又は乗務員の運用計画作成装置において、計画作成のための許容時間を格納する許容時間格納部と、計画作成手段毎の特徴情報（乗務数と計算時間、計画の質の関係など）を格納する作成手段特徴格納部とを備えることにより、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができるようにした。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、交通分野において、運行機材や乗務員の運用計画を自動作成する装置に関するものである。
【背景技術】
【０００２】
従来より、交通分野において、乗物の運行ダイヤに基づいて運行機材や乗務員の運用計画を作成する作業は熟練者の手作業に委ねられており、その負荷は極めて高い。最近では、熟練者の負荷軽減を目的として、計画の自動作成に関する研究開発が進んでいる。
【０００３】
スケジュールを作成する従来の方法としては、例えば特許文献１に記載されているように、分枝限定法を用いて解を求める方法が知られている。
【０００４】
また、一般的に解をできるだけ速く得る方法としては、例えば特許文献２に記載されているように、複数の最適解探索手段を持ち、予め定められた条件が満たされたときに現在使用している探索手段から他の探索手段に切り替える方法が知られている。この方法は、ある最適解探索手段における解の改善度がある閾値以下になったとき、予め定められた順番にしたがって、次の最適解探索手段に切り替えるものであり、探索の行き詰まりを防ぎ、高速に解を得られる効果がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平９−１８８２５５号公報
【特許文献２】特開平７−２２５７５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一方、計画作成者の置かれた状況（基本計画作成時はある程度時間をかけても評価値（質）の良い計画を作成したい、運行ダイヤが乱れた時は評価値（質）が少し悪くても短時間で計画を作成したいなどの状況）によって、計画作成の許容時間や求められる計画の質は異なる。しかしながら、上記特許文献１に記載されているような従来の方法では、計画を作成する際、分枝限定法しか用いないため、計画が作成できるまでに一定の時間がかかってしまい、許容時間を考慮することができない。また、上記特許文献２に記載されているような従来の方法では、複数の解法を用いることができるが、計画作成の高速化しか考慮しておらず、計画の質を考慮していない。そのため、従来では、計画作成者の置かれた状況に応じた最適な計画を立案できないことがあるという問題点があった。
【０００７】
この発明は、上記のような課題を解決するためになされたものであり、許容される計画作成時間を最大限に活用して計画を作成することで、計画作成者の置かれた状況に応じた最適な計画を立案することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、この発明に係る運行機材又は乗務員の運用計画作成装置は、計画の作成手段を複数有する作成手段格納部と、前記各作成手段に対する特徴情報を格納する作成手段特徴格納部と、計画作成にかかる許容時間を格納する許容時間格納部と、計画作成開始からの経過時間を取得する経過時間取得部と、前記運行機材又は乗務員の割り当て状況、前記特徴情報、前記許容時間、及び、計画作成途中における前記経過時間に基づいて、前記複数の作成手段の中から前記許容時間内に作成できる最適な作成手段を計画作成途中で逐次選択する作成手段選択部とを備えることを特徴とする。
【発明の効果】
【０００９】
この発明によれば、特に作成手段特徴格納部と許容時間格納部を備えたことにより、設定された許容時間を考慮して、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができる。そのため、許容される計画作成時間を最大限に活用でき、計画作成者の置かれた状況（時間をかけても評価値（質）の良い計画を作成したい、評価値（質）が少し悪くても短時間で計画を作成したいなど）に応じて最適な計画を立案することができる。
【図面の簡単な説明】
【００１０】
【図１】列車の運行ダイヤと行路の例を示す図である。
【図２】この発明の実施の形態１に係る運行機材又は乗務員の運用計画作成装置の構成図である。
【図３】許容時間設定部として実現される許容時間設定画面の例である。
【図４】計画作成部における処理のフローチャートである。
【図５】作成手段選択部における処理のフローチャートである。
【図６】作成手段特徴格納部に格納された特徴情報の例である。
【図７】図６に示す特徴情報に計画作成結果の履歴を加えた特徴情報の例である。
【発明を実施するための形態】
【００１１】
実施の形態１．
以下では、鉄道乗務員運用計画の作成を対象として説明する。「鉄道乗務員運用計画」とは、列車の運行ダイヤ上のすべての乗務に対して、一人以上の乗務員を割り当てた乗務員の運用スケジュールのことである。ここで、「乗務」とは、開始時刻、開始場所、終了時刻、終了場所の組み合わせからなる作業の単位である。乗務員運用計画で用いる評価指標としては、行路数や便乗数、あるいはそれらの重み付き和などが考えられる。また、「行路」とは、乗務員の勤務を構成する一連の乗務の集合のことであり、「便乗」とは、一つの乗務を二人以上の乗務員が担当したとき、運転を行わない乗務員の乗務のことである。各行路を担当する乗務員は勤務時間の上限や乗務時間の上限などの制約条件を満たす必要がある。
【００１２】
図１は、列車の運行ダイヤと行路の例を示す図である。図１において、斜めの線は乗務を表しており、太い実線と一点鎖線は行路を表している。図１に示されたような一連の乗務で構成される行路を多数生成し、すべての乗務が被覆されるように行路を選択する。ここで、乗務が行路に「被覆される」とは、その乗務に行路（あるいはそれに対応する乗務員）が割り当たっていることを意味する。また、図１では、ある一つの乗務が二つの行路で被覆されており、便乗が存在する。
【００１３】
乗務員運用計画の自動作成方法は二段階に分かれており、まず、第一段階として、制約条件を満たす行路候補を多数列挙する。次に、第二段階として、列挙した行路候補の中から、評価値を最適化し、すべての乗務が選択した行路候補のいずれかに割り当たるように、行路候補の組み合わせを選択して運用計画を作成する。制約条件を満たす行路候補を列挙する方法として、バックトラック法や列生成法などの公知の方法が知られている。また、行路候補の組み合わせを選択する方法についても、分枝限定法、貪欲法、ラグランジュ緩和法などの公知の方法が知られている。
【００１４】
上で述べた公知の方法は、計算時間は長いが良い評価値（質）を持つ解が得られる方法、計算時間は短いが程々の質の解しか得られない方法など、方法に応じて様々な特徴を持つ。例えば、分枝限定法はすべての組み合わせの中から最適な組み合わせを選ぶ方法であり、規模が大きくなると指数的に計算時間が増加するため、最適解を得ることができるが、そのための計算時間は長い。また、貪欲法は行路候補に順位を付け、順位の高い行路候補から採用していく方法であり、計算時間は短いが、程々の評価値（質）を持つ解しか得られない。さらに、ラグランジュ緩和法は評価指標と制約条件（すべての乗務が選択した行路候補のいずれかに割り当たる）の違反度との重み付き和を最小化する解を得る方法であり、計算時間は非常に短いが、制約を違反した解が得られることがある。
【００１５】
乗務員運用計画を自動作成する際、基本計画作成時はある程度時間をかけても評価値（質）の良い計画を作成したい、運行ダイヤが乱れた時は評価値（質）が少し悪くても短時間で計画を作成したいなど、状況に応じて計画作成者が求める計画作成の許容時間や計画の質は異なる。そこで、この発明は、計画作成者によって設定された許容時間を最大限に活用し、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることで、最適な計画を立案することを目的とする。
【００１６】
図２は、この発明に係る運行機材又は乗務員の運用計画作成装置の構成図である。ダイヤ格納部１に格納された列車の運行ダイヤを基に、計画作成部２が運用計画を作成する。作成した計画は作成結果格納部３に格納される。計画作成の際に用いる計画作成手段は作成手段格納部４に複数格納される。各作成手段に対する乗務数と計画作成にかかる計算時間、及び、計画の評価値（質）の関係に関する特徴情報は作成手段特徴格納部５に格納される。計画作成に許容される時間は許容時間設定部６で設定され、許容時間格納部７に格納される。また、計画作成開始からの経過時間が経過時間取得部９によって取得される。そして、作成手段選択部８は、計画作成の途中で、運行機材又は乗務員の割り当て状況、作成手段毎の特徴情報、計画作成の許容時間、及び、計画作成開始からの経過時間を基に、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段を逐次選択して切り替える。
【００１７】
本実施例では、許容時間設定部６を、図３に示した許容時間設定画面１１として提供し、この許容時間設定画面１１を介して許容時間の設定が行われる。図３における許容時間設定画面では、テキストボックス１２に許容時間が入力され、設定ボタン１３が押されることにより、入力された許容時間が許容時間格納部７に格納される。
【００１８】
次に、計画作成部２における計画作成の流れを説明する。以下では、行路候補選択の流れを例に説明する。図４は、計画作成部２の処理手順を示したフローチャートである。計画作成部２は、まず、運行ダイヤをダイヤ格納部１から受け取り（ステップＳ１）、複数の作成手段を作成手段格納部４から受け取る（ステップＳ２）。その後、計画作成開始からの経過時間を経過時間取得部９から受け取る（ステップＳ３）。そして、探索状況として、受け取った経過時間と採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）を作成手段選択部８に送る（ステップＳ４）。この際、最初は、経過時間は０であり、採用した行路によって被覆された乗務（乗務員が割り当てられた乗務）はないので、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）は、運行ダイヤの乗務数である。次に、作成手段選択部８による作成手段選択情報として、どの作成手段が、許容時間を満たす中で作成できる計画の質が最も高いと期待されるかという情報を、作成手段選択部８から受け取る（ステップＳ５）。作成手段選択部８による選択の処理手順については後述する。受け取った作成手段選択情報を基に、計画作成部２は、作成手段格納部４から受け取った作成手段を用いて、行路候補を選択する（ステップＳ６）。そして、採用した行路候補によって、運行ダイヤ上の乗務がすべて被覆されていれば（ステップＳ７）、作成結果格納部３に作成結果を格納し（ステップＳ８）、計画作成を終了する。一方、上記ステップＳ７において、運行ダイヤ上の乗務がすべて被覆されていなければ、ステップＳ１にて受け取った運行ダイヤの乗務数と、採用した行路によって被覆された乗務数（乗務員が割り当てられた乗務数）との差をとることにより、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）を算出して（ステップＳ９）、ステップＳ３の処理に戻る。
【００１９】
次に、作成手段選択部８における計画作成手段選択の流れを説明する。図５は、作成手段選択部８の処理手順を示したフローチャートである。作成手段選択部８は、まず、計画作成部２から、探索状況として、処理開始からの経過時間と採用した行路候補に被覆されていない乗務数を受け取る（ステップＳ１１）。次に、許容時間格納部７から許容時間を取得する（ステップＳ１２）。そして、計画作成手段を選択するタイミングかどうかを判断する（ステップＳ１３）。本実施例では、計画作成手段を選択するタイミングは、採用した行路候補に被覆されていない乗務数が作成手段特徴格納部５に格納された特徴情報が持つ乗務数以下となったとき、あるいは行路候補の組合せ選択開始時点とする。計画作成手段を選択するタイミングでなければ、作成手段選択部８は、現在用いている作成手段を選択する（ステップＳ１４）。一方、計画作成手段を選択するタイミングであれば、作成手段選択部８は、作成手段特徴格納部５から、各作成手段の特徴情報、あるいは推定値を取得する（ステップＳ１５）。本実施例では、採用した行路候補に被覆されていない乗務数（Ｎ１とする）に対応した各手段毎の特徴情報が格納されていなければ、格納されている中で一番近い乗務数（Ｎ２とする）の特徴情報から推定値を算出する。推定値は「Ｎ２における特徴情報の値」÷「Ｎ２」×「Ｎ１」で与える。ここでは、各作成手段の特徴情報が乗務数に比例するとみなして推定値を算出しているが、一般には各作成手段の特徴情報は乗務数に比例するとは限らないため、推定値の精度が悪いと実際の値と大きく異なる可能性があることに注意する。得られた各手段毎の特徴情報、あるいは推定値を基に、作成手段選択部８は、許容時間を満たす中で作成できる計画の質が最も高いと期待される作成手段を選択する（ステップＳ１６）。そして、どの作成手段を選択したかという情報を計画作成部２へ送り（ステップＳ１７）、作成手段選択処理を終了する。
【００２０】
以下、作成手段選択部８における計画作成手段の選択例を説明する。本選択例では、「行路数(の最小化)」を計画作成で用いる評価指標とする。
【００２１】
ダイヤ格納部１に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が格納されているとする。また、許容時間設定部６により許容時間として「９時間」が設定され、許容時間格納部７に許容時間「９時間」が格納されているとする。
【００２２】
図６は、作成手段特徴格納部５に格納された、分枝限定法と貪欲法に対する特徴情報、すなわち、乗務数と計画作成にかかる計算時間、及び、得られる解の行路数の関係を示す図である。これらの関係は、各乗務数を持つサンプルダイヤに対してそれぞれの作成手段を適用することで事前に取得することができる。本実施例では、２００乗務での分枝限定法の作成手段特徴は与えられていない状況を考え、図６において、２００乗務での分枝限定法の作成手段特徴を「−」と表記している。図６で与えられた作成手段特徴の場合、作成手段選択部８が作成手段特徴や計画作成状況から計画作成手段を選択するタイミングは、行路候補の組合せ選択開始時点、及び、採用した行路候補に被覆されていない乗務数が４００乗務以下となったとき、２００乗務以下となったとき、の合計３回与えられる。
【００２３】
行路候補の組み合わせ選択開始時点において、図６には５００乗務に対する各作成手段の特徴がないため、４００乗務に対する各作成手段の特徴情報から推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、５００乗務に対する分枝限定法では行路数２５の計画を１５時間で作成できると推定される。次に、４００乗務に対する貪欲法では行路数２４の計画を４時間で作成できることが期待されるため、５００乗務に対する貪欲法では行路数３０の計画を５時間で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００２４】
貪欲法では、行路候補を一つずつ採用していくため、行路候補が採用されるたびに、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）は減っていく。貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され（乗務員が割り当てられ）、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）が４００乗務となり、４００乗務以下となったとする。この時点での経過時間は１時間であったとする。このとき、計画作成に許容される時間の残りは８時間である。図６より、分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるのに対して、貪欲法では行路数２４の計画を４時間で作成できることが期待される。したがって、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００２５】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が１９０乗務となり、２００乗務以下となったとする。ここでは、１９０乗務となった時点で初めて２００乗務以下となったとする。つまり、一つ前の行路候補を採用した時点では、採用した行路候補に含まれていない乗務数が２００乗務より大きい（例えば、２０５乗務だった）とする。計画作成開始時点からの経過時間は３時間とする。このとき、計画作成に許容される時間の残りは６時間である。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。次に、２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。分枝限定法を用いると、貪欲法よりも計算時間は３時間４８分長くなると推定されるが、許容時間内に計画を作成でき、貪欲法よりも行路数は１．９行路少なくなると推定されるため、作成手段選択部８は分枝限定法を選択する。
【００２６】
以降は、乗務数１９０より小さい乗務数を持つ作成手段特徴が格納されていないため、作成手段選択部８は分枝限定法を選択し続けて、計画を作成する。
【００２７】
本実施例では、最初に貪欲法を用い、採用した行路候補に被覆されていない乗務数が１９０乗務となったとき、貪欲法から分枝限定法に切り替え、以降は分枝限定法を用いて計画を作成した。本装置を用いて計画を作成した場合と、貪欲法のみを用いて計画を作成した場合を比較すると、計画作成にかかる時間は３時間４８分長くなるが、許容時間内に行路数が１．９行路少ない計画を作成できると推定される。行路数は必要な乗務員数に対応しているため、行路数を減らすことにより人件費の大幅な削減が期待できる。また、本装置を用いて計画を作成した場合と、分枝限定法のみを用いて計画を作成した場合を比較すると、分枝限定法では許容時間内に計画を作成することができないと推定されるが、本装置では許容時間内に計画を作成できると推定される。
【００２８】
このように、計画作成途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段を選択することにより、許容される計画作成時間を最大限に活用し、時間をかけても評価値（質）の良い計画を作成したい、又は、評価値（質）が多少悪くても短時間で計画を作成したいなどといった、計画作成者の置かれた状況に応じた最適な計画を立案することができる。
【００２９】
なお、本実施の形態では、作成手段格納部４に異なる作成手段を格納したが、同じ作成手段に対して異なるパラメータを与えたもの（例えば、分枝限定法の場合は解を探索する順番を変えたものなど）を格納してもよい。
【００３０】
また、本実施の形態では、作成手段選択部８が計画作成手段を選択するタイミングとして、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）が作成手段特徴格納部５に格納された特徴情報が持つ乗務数以下となったときとしたが、採用した行路候補に含まれていない乗務数（乗務員が割り当てられていない乗務数）が変化したときや一定時間経過したとき（例えば、５分おき）としてもよい。
【００３１】
さらに、本実施の形態では、特徴情報の推定値として「Ｎ２における特徴情報の値」÷「Ｎ２」×「Ｎ１」を用いたが、採用した行路候補に被覆されていない乗務数Ｎ１が特徴情報として格納されている乗務数Ｎ３とＮ４の間にあるとき、すなわち、「Ｎ３ < Ｎ１ < Ｎ４」が成立するとき、推定値を「Ｖ３」＋（「Ｖ４」−「Ｖ３」）×（「Ｎ１」−「Ｎ３」）÷（「Ｎ４」−「Ｎ３」）と与えてもよい。ここで、Ｖ３とＶ４はＮ３における特徴情報の値とＮ４における特徴情報の値である。
【００３２】
実施の形態２．
実施の形態１において、乗務数が１９０乗務のときに分枝限定法に切り替えることで、切り替えた時点から計画を作成し終えるまで３時間かかったとする。また、分枝限定法に切り替えた時点から計画を作成し終えるまでに採用した行路数を９とする。計画作成において、切り替えた計画作成手段の作成履歴を基に、作成手段の特徴情報（この場合、分枝限定法は１９０乗務の問題に対して行路数９の計画を３時間で作成できるという情報）を作成手段特徴格納部５に追加することで、特徴情報の充実化が可能となる。
【００３３】
図７は、上記の分枝限定法の特徴情報を作成手段特徴格納部５に追加したものである。以下、上記の作成手段特徴情報を追加した場合（図７）と追加しなかった場合（図６）に対する、作成手段選択部８における計画作成手段の選択例を比較する。
【００３４】
新たな問題として、ダイヤ格納部1に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が格納されているとする。また、許容時間設定部６により許容時間として「７時間」が設定され、許容時間格納部７に許容時間「７時間」が格納されているとする。計画作成手段を選択するタイミングや作成手段特徴情報の推定値の算出方法については、実施の形態１と同様に行う。
【００３５】
行路候補の組み合わせ選択開始時点において、図７には５００乗務に対する各作成手段の特徴がないため、４００乗務に対する各作成手段の特徴情報から推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、５００乗務に対する分枝限定法では行路数２５の計画を１５時間で作成できると推定される。次に、４００乗務に対する貪欲法では行路数２４の計画を４時間で作成できることが期待されるため、５００乗務に対する貪欲法では行路数３０の計画を５時間で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。図７を作成手段特徴情報として用いた場合も図７を用いたときと同様の処理が行われる。
【００３６】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が４００乗務となり、４００乗務以下となったとする。経過時間は１時間とする。このとき、計画作成に許容される時間の残りは６時間であり、採用した行路候補に被覆されていない乗務は４００乗務である。図７より、分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるのに対して、貪欲法では行路数２４の計画を４時間で作成できることが期待される。したがって、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。図６を作成手段特徴情報として用いた場合も図７を用いたときと同様の処理が行われる。
【００３７】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が１９０乗務となり、１９０乗務以下となったとする。実施の形態１と同様に、ここでも、１９０乗務となった時点で初めて２００乗務以下となったとする。計画作成開始時点からの経過時間は３時間とする。このとき、計画作成に許容される時間の残りは４時間であり、まだ行路が割り当てられていない乗務は１９０乗務である。図７より、分枝限定法では行路数９の計画を３時間で作成できることが期待される。一方、図７には１９０乗務に対する貪欲法の特徴がないため、２００乗務に対する特徴情報から推定値を算出する。２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。どちらも許容時間内に計画を作成できるが、行路数は分枝限定法の方が少なくなるため、作成手段選択部８は分枝限定法を選択する。
【００３８】
次に、図６を作成手段特徴情報として用いた場合を考える。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。一方、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあると作成手段選択部８は判断し、貪欲法を選択する。つまり、残り１９０乗務となったとき、図６を用いたときは貪欲法を選択して行路数１１．４の計画が得られると推定するのに対して、図７を用いたときは分枝限定法を選択して行路数９の計画が得られると推定する。したがって、作成手段特徴格納部５に図７の特徴情報を用いた方が、図６の特徴情報を用いるよりも、作成手段選択部８は許容時間内でより行路の少ない計画を作成できるようになる。
【００３９】
以上のように、計画作成において、最後に切り替えた計画作成手段の作成履歴を基に、作成手段の特徴情報を作成手段特徴格納部５に追加することで、特徴情報が充実化する。すなわち、計画作成を繰り返すことにより、特徴情報が充実化する。そして、特徴情報が充実化することにより、特徴情報の推定値を算出する精度が上がり、また、作成手段選択部８が作成手段を選択する機会が増える。そのため、より質の高い計画を立案することができるようになる。
【００４０】
実施の形態３．
実施の形態１及び２においては、計画作成の許容時間は、最初に予め設定されており、作成途中に再設定される場合を考えていなかったが、計画作成途中で許容時間が変更可能であるようにしてもよい。
【００４１】
以下、許容時間が計画作成途中に変更された場合における計画作成手段の選択例を説明する。実施の形態１と同様に、計画作成開始時点においては、ダイヤ格納部１に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が設定されているとする。また、許容時間設定部６により許容時間として「９時間」が設定され、許容時間格納部７に許容時間「９時間」が格納されているとし、作成手段特徴格納部５には、図６で示した作成手段特徴が格納されているとする。
【００４２】
行路候補の組み合わせ選択開始時点においては、実施の形態１と同様にして、作成手段選択部は貪欲法を選択する。
【００４３】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が４００乗務となり、４００乗務以下となったとする。経過時間は１時間とする。このとき、実施の形態１と同様にして、作成手段選択部は貪欲法を選択する。
【００４４】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が２００乗務以下となったとする。計画作成開始時点からの経過時間は３時間とする。このときに、計画作成終了までに許容される残り時間として、「２時間」が再設定されたとする。採用した行路候補に被覆されていない乗務は１９０乗務である。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。次に、２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００４５】
このように、計画作成途中で許容時間が再設定された場合においても、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができる。
【００４６】
実施の形態４．
許容時間を問わずに最適な計画を作成したい場合、許容時間設定部６で許容時間として「∞時間」あるいはそれに相当する十分大きな時間を設定する。このようにすることで、作成手段選択部８は計画作成途中で逐次、計画作成手段の中から、許容時間を問わずに一番良い評価値（質）を持つ計画を作成できる計画作成手段を選択するため、できるだけ評価値（質）の良い計画を作成できる。
【００４７】
実施の形態５．
作成手段選択部８が作成手段を選択する際、作成手段特徴格納部５に格納された特徴情報、あるいはその推定値から、作成手段格納部４に格納されたいずれの計画作成手段を用いても許容時間内で計画作成することができる作成手段を選択することができない場合には、許容時間内に計画を作成できないと判断して、計画作成部２が許容時間内に計画を作成できる見込みがないという情報を作成結果格納部３に格納し、計画作成を打ち切る。
【００４８】
このように、許容時間内に計画を作成できないと判断した時点ですぐに計画作成を打ち切るため、無駄な計算を短縮することができ、計画作成者はすぐに別の許容時間を設定して計画作成を行うことができるようになる。
【００４９】
実施の形態６．
計画の評価値（質）を問わずにできるだけ速く計画を作成したい場合、許容時間設定部６で許容時間として「０時間」を格納したとき、計画作成手段の中から評価値（質）を問わずに一番速く計画を作成できる計画作成手段を逐次選択させる。このようにすることで、計画の評価値（質）を問わない場合には、できるだけ速く計画を作成することができる。
【００５０】
なお、以上の実施の形態においては、乗務員の運用計画作成について説明したが、本願発明の運用計画作成装置は、乗務員ではなく運行機材について適用することもでき、また、運行機材及び乗務員の運用計画作成について適用することもできるものである。また、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００５１】
１ ダイヤ格納部、２ 計画作成部、３ 作成結果格納部、４ 作成手段格納部、５ 作成手段特徴格納部、６ 許容時間設定部、７ 許容時間格納部、８ 作成手段選択部、９ 経過時間取得部、１１ 許容時間設定画面、１２ テキストボックス、１３ 設定ボタン。
【技術分野】
【０００１】
この発明は、交通分野において、運行機材や乗務員の運用計画を自動作成する装置に関するものである。
【背景技術】
【０００２】
従来より、交通分野において、乗物の運行ダイヤに基づいて運行機材や乗務員の運用計画を作成する作業は熟練者の手作業に委ねられており、その負荷は極めて高い。最近では、熟練者の負荷軽減を目的として、計画の自動作成に関する研究開発が進んでいる。
【０００３】
スケジュールを作成する従来の方法としては、例えば特許文献１に記載されているように、分枝限定法を用いて解を求める方法が知られている。
【０００４】
また、一般的に解をできるだけ速く得る方法としては、例えば特許文献２に記載されているように、複数の最適解探索手段を持ち、予め定められた条件が満たされたときに現在使用している探索手段から他の探索手段に切り替える方法が知られている。この方法は、ある最適解探索手段における解の改善度がある閾値以下になったとき、予め定められた順番にしたがって、次の最適解探索手段に切り替えるものであり、探索の行き詰まりを防ぎ、高速に解を得られる効果がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平９−１８８２５５号公報
【特許文献２】特開平７−２２５７５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
一方、計画作成者の置かれた状況（基本計画作成時はある程度時間をかけても評価値（質）の良い計画を作成したい、運行ダイヤが乱れた時は評価値（質）が少し悪くても短時間で計画を作成したいなどの状況）によって、計画作成の許容時間や求められる計画の質は異なる。しかしながら、上記特許文献１に記載されているような従来の方法では、計画を作成する際、分枝限定法しか用いないため、計画が作成できるまでに一定の時間がかかってしまい、許容時間を考慮することができない。また、上記特許文献２に記載されているような従来の方法では、複数の解法を用いることができるが、計画作成の高速化しか考慮しておらず、計画の質を考慮していない。そのため、従来では、計画作成者の置かれた状況に応じた最適な計画を立案できないことがあるという問題点があった。
【０００７】
この発明は、上記のような課題を解決するためになされたものであり、許容される計画作成時間を最大限に活用して計画を作成することで、計画作成者の置かれた状況に応じた最適な計画を立案することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、この発明に係る運行機材又は乗務員の運用計画作成装置は、計画の作成手段を複数有する作成手段格納部と、前記各作成手段に対する特徴情報を格納する作成手段特徴格納部と、計画作成にかかる許容時間を格納する許容時間格納部と、計画作成開始からの経過時間を取得する経過時間取得部と、前記運行機材又は乗務員の割り当て状況、前記特徴情報、前記許容時間、及び、計画作成途中における前記経過時間に基づいて、前記複数の作成手段の中から前記許容時間内に作成できる最適な作成手段を計画作成途中で逐次選択する作成手段選択部とを備えることを特徴とする。
【発明の効果】
【０００９】
この発明によれば、特に作成手段特徴格納部と許容時間格納部を備えたことにより、設定された許容時間を考慮して、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができる。そのため、許容される計画作成時間を最大限に活用でき、計画作成者の置かれた状況（時間をかけても評価値（質）の良い計画を作成したい、評価値（質）が少し悪くても短時間で計画を作成したいなど）に応じて最適な計画を立案することができる。
【図面の簡単な説明】
【００１０】
【図１】列車の運行ダイヤと行路の例を示す図である。
【図２】この発明の実施の形態１に係る運行機材又は乗務員の運用計画作成装置の構成図である。
【図３】許容時間設定部として実現される許容時間設定画面の例である。
【図４】計画作成部における処理のフローチャートである。
【図５】作成手段選択部における処理のフローチャートである。
【図６】作成手段特徴格納部に格納された特徴情報の例である。
【図７】図６に示す特徴情報に計画作成結果の履歴を加えた特徴情報の例である。
【発明を実施するための形態】
【００１１】
実施の形態１．
以下では、鉄道乗務員運用計画の作成を対象として説明する。「鉄道乗務員運用計画」とは、列車の運行ダイヤ上のすべての乗務に対して、一人以上の乗務員を割り当てた乗務員の運用スケジュールのことである。ここで、「乗務」とは、開始時刻、開始場所、終了時刻、終了場所の組み合わせからなる作業の単位である。乗務員運用計画で用いる評価指標としては、行路数や便乗数、あるいはそれらの重み付き和などが考えられる。また、「行路」とは、乗務員の勤務を構成する一連の乗務の集合のことであり、「便乗」とは、一つの乗務を二人以上の乗務員が担当したとき、運転を行わない乗務員の乗務のことである。各行路を担当する乗務員は勤務時間の上限や乗務時間の上限などの制約条件を満たす必要がある。
【００１２】
図１は、列車の運行ダイヤと行路の例を示す図である。図１において、斜めの線は乗務を表しており、太い実線と一点鎖線は行路を表している。図１に示されたような一連の乗務で構成される行路を多数生成し、すべての乗務が被覆されるように行路を選択する。ここで、乗務が行路に「被覆される」とは、その乗務に行路（あるいはそれに対応する乗務員）が割り当たっていることを意味する。また、図１では、ある一つの乗務が二つの行路で被覆されており、便乗が存在する。
【００１３】
乗務員運用計画の自動作成方法は二段階に分かれており、まず、第一段階として、制約条件を満たす行路候補を多数列挙する。次に、第二段階として、列挙した行路候補の中から、評価値を最適化し、すべての乗務が選択した行路候補のいずれかに割り当たるように、行路候補の組み合わせを選択して運用計画を作成する。制約条件を満たす行路候補を列挙する方法として、バックトラック法や列生成法などの公知の方法が知られている。また、行路候補の組み合わせを選択する方法についても、分枝限定法、貪欲法、ラグランジュ緩和法などの公知の方法が知られている。
【００１４】
上で述べた公知の方法は、計算時間は長いが良い評価値（質）を持つ解が得られる方法、計算時間は短いが程々の質の解しか得られない方法など、方法に応じて様々な特徴を持つ。例えば、分枝限定法はすべての組み合わせの中から最適な組み合わせを選ぶ方法であり、規模が大きくなると指数的に計算時間が増加するため、最適解を得ることができるが、そのための計算時間は長い。また、貪欲法は行路候補に順位を付け、順位の高い行路候補から採用していく方法であり、計算時間は短いが、程々の評価値（質）を持つ解しか得られない。さらに、ラグランジュ緩和法は評価指標と制約条件（すべての乗務が選択した行路候補のいずれかに割り当たる）の違反度との重み付き和を最小化する解を得る方法であり、計算時間は非常に短いが、制約を違反した解が得られることがある。
【００１５】
乗務員運用計画を自動作成する際、基本計画作成時はある程度時間をかけても評価値（質）の良い計画を作成したい、運行ダイヤが乱れた時は評価値（質）が少し悪くても短時間で計画を作成したいなど、状況に応じて計画作成者が求める計画作成の許容時間や計画の質は異なる。そこで、この発明は、計画作成者によって設定された許容時間を最大限に活用し、計画作成の途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることで、最適な計画を立案することを目的とする。
【００１６】
図２は、この発明に係る運行機材又は乗務員の運用計画作成装置の構成図である。ダイヤ格納部１に格納された列車の運行ダイヤを基に、計画作成部２が運用計画を作成する。作成した計画は作成結果格納部３に格納される。計画作成の際に用いる計画作成手段は作成手段格納部４に複数格納される。各作成手段に対する乗務数と計画作成にかかる計算時間、及び、計画の評価値（質）の関係に関する特徴情報は作成手段特徴格納部５に格納される。計画作成に許容される時間は許容時間設定部６で設定され、許容時間格納部７に格納される。また、計画作成開始からの経過時間が経過時間取得部９によって取得される。そして、作成手段選択部８は、計画作成の途中で、運行機材又は乗務員の割り当て状況、作成手段毎の特徴情報、計画作成の許容時間、及び、計画作成開始からの経過時間を基に、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段を逐次選択して切り替える。
【００１７】
本実施例では、許容時間設定部６を、図３に示した許容時間設定画面１１として提供し、この許容時間設定画面１１を介して許容時間の設定が行われる。図３における許容時間設定画面では、テキストボックス１２に許容時間が入力され、設定ボタン１３が押されることにより、入力された許容時間が許容時間格納部７に格納される。
【００１８】
次に、計画作成部２における計画作成の流れを説明する。以下では、行路候補選択の流れを例に説明する。図４は、計画作成部２の処理手順を示したフローチャートである。計画作成部２は、まず、運行ダイヤをダイヤ格納部１から受け取り（ステップＳ１）、複数の作成手段を作成手段格納部４から受け取る（ステップＳ２）。その後、計画作成開始からの経過時間を経過時間取得部９から受け取る（ステップＳ３）。そして、探索状況として、受け取った経過時間と採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）を作成手段選択部８に送る（ステップＳ４）。この際、最初は、経過時間は０であり、採用した行路によって被覆された乗務（乗務員が割り当てられた乗務）はないので、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）は、運行ダイヤの乗務数である。次に、作成手段選択部８による作成手段選択情報として、どの作成手段が、許容時間を満たす中で作成できる計画の質が最も高いと期待されるかという情報を、作成手段選択部８から受け取る（ステップＳ５）。作成手段選択部８による選択の処理手順については後述する。受け取った作成手段選択情報を基に、計画作成部２は、作成手段格納部４から受け取った作成手段を用いて、行路候補を選択する（ステップＳ６）。そして、採用した行路候補によって、運行ダイヤ上の乗務がすべて被覆されていれば（ステップＳ７）、作成結果格納部３に作成結果を格納し（ステップＳ８）、計画作成を終了する。一方、上記ステップＳ７において、運行ダイヤ上の乗務がすべて被覆されていなければ、ステップＳ１にて受け取った運行ダイヤの乗務数と、採用した行路によって被覆された乗務数（乗務員が割り当てられた乗務数）との差をとることにより、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）を算出して（ステップＳ９）、ステップＳ３の処理に戻る。
【００１９】
次に、作成手段選択部８における計画作成手段選択の流れを説明する。図５は、作成手段選択部８の処理手順を示したフローチャートである。作成手段選択部８は、まず、計画作成部２から、探索状況として、処理開始からの経過時間と採用した行路候補に被覆されていない乗務数を受け取る（ステップＳ１１）。次に、許容時間格納部７から許容時間を取得する（ステップＳ１２）。そして、計画作成手段を選択するタイミングかどうかを判断する（ステップＳ１３）。本実施例では、計画作成手段を選択するタイミングは、採用した行路候補に被覆されていない乗務数が作成手段特徴格納部５に格納された特徴情報が持つ乗務数以下となったとき、あるいは行路候補の組合せ選択開始時点とする。計画作成手段を選択するタイミングでなければ、作成手段選択部８は、現在用いている作成手段を選択する（ステップＳ１４）。一方、計画作成手段を選択するタイミングであれば、作成手段選択部８は、作成手段特徴格納部５から、各作成手段の特徴情報、あるいは推定値を取得する（ステップＳ１５）。本実施例では、採用した行路候補に被覆されていない乗務数（Ｎ１とする）に対応した各手段毎の特徴情報が格納されていなければ、格納されている中で一番近い乗務数（Ｎ２とする）の特徴情報から推定値を算出する。推定値は「Ｎ２における特徴情報の値」÷「Ｎ２」×「Ｎ１」で与える。ここでは、各作成手段の特徴情報が乗務数に比例するとみなして推定値を算出しているが、一般には各作成手段の特徴情報は乗務数に比例するとは限らないため、推定値の精度が悪いと実際の値と大きく異なる可能性があることに注意する。得られた各手段毎の特徴情報、あるいは推定値を基に、作成手段選択部８は、許容時間を満たす中で作成できる計画の質が最も高いと期待される作成手段を選択する（ステップＳ１６）。そして、どの作成手段を選択したかという情報を計画作成部２へ送り（ステップＳ１７）、作成手段選択処理を終了する。
【００２０】
以下、作成手段選択部８における計画作成手段の選択例を説明する。本選択例では、「行路数(の最小化)」を計画作成で用いる評価指標とする。
【００２１】
ダイヤ格納部１に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が格納されているとする。また、許容時間設定部６により許容時間として「９時間」が設定され、許容時間格納部７に許容時間「９時間」が格納されているとする。
【００２２】
図６は、作成手段特徴格納部５に格納された、分枝限定法と貪欲法に対する特徴情報、すなわち、乗務数と計画作成にかかる計算時間、及び、得られる解の行路数の関係を示す図である。これらの関係は、各乗務数を持つサンプルダイヤに対してそれぞれの作成手段を適用することで事前に取得することができる。本実施例では、２００乗務での分枝限定法の作成手段特徴は与えられていない状況を考え、図６において、２００乗務での分枝限定法の作成手段特徴を「−」と表記している。図６で与えられた作成手段特徴の場合、作成手段選択部８が作成手段特徴や計画作成状況から計画作成手段を選択するタイミングは、行路候補の組合せ選択開始時点、及び、採用した行路候補に被覆されていない乗務数が４００乗務以下となったとき、２００乗務以下となったとき、の合計３回与えられる。
【００２３】
行路候補の組み合わせ選択開始時点において、図６には５００乗務に対する各作成手段の特徴がないため、４００乗務に対する各作成手段の特徴情報から推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、５００乗務に対する分枝限定法では行路数２５の計画を１５時間で作成できると推定される。次に、４００乗務に対する貪欲法では行路数２４の計画を４時間で作成できることが期待されるため、５００乗務に対する貪欲法では行路数３０の計画を５時間で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００２４】
貪欲法では、行路候補を一つずつ採用していくため、行路候補が採用されるたびに、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）は減っていく。貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され（乗務員が割り当てられ）、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）が４００乗務となり、４００乗務以下となったとする。この時点での経過時間は１時間であったとする。このとき、計画作成に許容される時間の残りは８時間である。図６より、分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるのに対して、貪欲法では行路数２４の計画を４時間で作成できることが期待される。したがって、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００２５】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が１９０乗務となり、２００乗務以下となったとする。ここでは、１９０乗務となった時点で初めて２００乗務以下となったとする。つまり、一つ前の行路候補を採用した時点では、採用した行路候補に含まれていない乗務数が２００乗務より大きい（例えば、２０５乗務だった）とする。計画作成開始時点からの経過時間は３時間とする。このとき、計画作成に許容される時間の残りは６時間である。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。次に、２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。分枝限定法を用いると、貪欲法よりも計算時間は３時間４８分長くなると推定されるが、許容時間内に計画を作成でき、貪欲法よりも行路数は１．９行路少なくなると推定されるため、作成手段選択部８は分枝限定法を選択する。
【００２６】
以降は、乗務数１９０より小さい乗務数を持つ作成手段特徴が格納されていないため、作成手段選択部８は分枝限定法を選択し続けて、計画を作成する。
【００２７】
本実施例では、最初に貪欲法を用い、採用した行路候補に被覆されていない乗務数が１９０乗務となったとき、貪欲法から分枝限定法に切り替え、以降は分枝限定法を用いて計画を作成した。本装置を用いて計画を作成した場合と、貪欲法のみを用いて計画を作成した場合を比較すると、計画作成にかかる時間は３時間４８分長くなるが、許容時間内に行路数が１．９行路少ない計画を作成できると推定される。行路数は必要な乗務員数に対応しているため、行路数を減らすことにより人件費の大幅な削減が期待できる。また、本装置を用いて計画を作成した場合と、分枝限定法のみを用いて計画を作成した場合を比較すると、分枝限定法では許容時間内に計画を作成することができないと推定されるが、本装置では許容時間内に計画を作成できると推定される。
【００２８】
このように、計画作成途中で逐次、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段を選択することにより、許容される計画作成時間を最大限に活用し、時間をかけても評価値（質）の良い計画を作成したい、又は、評価値（質）が多少悪くても短時間で計画を作成したいなどといった、計画作成者の置かれた状況に応じた最適な計画を立案することができる。
【００２９】
なお、本実施の形態では、作成手段格納部４に異なる作成手段を格納したが、同じ作成手段に対して異なるパラメータを与えたもの（例えば、分枝限定法の場合は解を探索する順番を変えたものなど）を格納してもよい。
【００３０】
また、本実施の形態では、作成手段選択部８が計画作成手段を選択するタイミングとして、採用した行路候補に被覆されていない乗務数（乗務員が割り当てられていない乗務数）が作成手段特徴格納部５に格納された特徴情報が持つ乗務数以下となったときとしたが、採用した行路候補に含まれていない乗務数（乗務員が割り当てられていない乗務数）が変化したときや一定時間経過したとき（例えば、５分おき）としてもよい。
【００３１】
さらに、本実施の形態では、特徴情報の推定値として「Ｎ２における特徴情報の値」÷「Ｎ２」×「Ｎ１」を用いたが、採用した行路候補に被覆されていない乗務数Ｎ１が特徴情報として格納されている乗務数Ｎ３とＮ４の間にあるとき、すなわち、「Ｎ３ < Ｎ１ < Ｎ４」が成立するとき、推定値を「Ｖ３」＋（「Ｖ４」−「Ｖ３」）×（「Ｎ１」−「Ｎ３」）÷（「Ｎ４」−「Ｎ３」）と与えてもよい。ここで、Ｖ３とＶ４はＮ３における特徴情報の値とＮ４における特徴情報の値である。
【００３２】
実施の形態２．
実施の形態１において、乗務数が１９０乗務のときに分枝限定法に切り替えることで、切り替えた時点から計画を作成し終えるまで３時間かかったとする。また、分枝限定法に切り替えた時点から計画を作成し終えるまでに採用した行路数を９とする。計画作成において、切り替えた計画作成手段の作成履歴を基に、作成手段の特徴情報（この場合、分枝限定法は１９０乗務の問題に対して行路数９の計画を３時間で作成できるという情報）を作成手段特徴格納部５に追加することで、特徴情報の充実化が可能となる。
【００３３】
図７は、上記の分枝限定法の特徴情報を作成手段特徴格納部５に追加したものである。以下、上記の作成手段特徴情報を追加した場合（図７）と追加しなかった場合（図６）に対する、作成手段選択部８における計画作成手段の選択例を比較する。
【００３４】
新たな問題として、ダイヤ格納部1に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が格納されているとする。また、許容時間設定部６により許容時間として「７時間」が設定され、許容時間格納部７に許容時間「７時間」が格納されているとする。計画作成手段を選択するタイミングや作成手段特徴情報の推定値の算出方法については、実施の形態１と同様に行う。
【００３５】
行路候補の組み合わせ選択開始時点において、図７には５００乗務に対する各作成手段の特徴がないため、４００乗務に対する各作成手段の特徴情報から推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、５００乗務に対する分枝限定法では行路数２５の計画を１５時間で作成できると推定される。次に、４００乗務に対する貪欲法では行路数２４の計画を４時間で作成できることが期待されるため、５００乗務に対する貪欲法では行路数３０の計画を５時間で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。図７を作成手段特徴情報として用いた場合も図７を用いたときと同様の処理が行われる。
【００３６】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が４００乗務となり、４００乗務以下となったとする。経過時間は１時間とする。このとき、計画作成に許容される時間の残りは６時間であり、採用した行路候補に被覆されていない乗務は４００乗務である。図７より、分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるのに対して、貪欲法では行路数２４の計画を４時間で作成できることが期待される。したがって、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。図６を作成手段特徴情報として用いた場合も図７を用いたときと同様の処理が行われる。
【００３７】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が１９０乗務となり、１９０乗務以下となったとする。実施の形態１と同様に、ここでも、１９０乗務となった時点で初めて２００乗務以下となったとする。計画作成開始時点からの経過時間は３時間とする。このとき、計画作成に許容される時間の残りは４時間であり、まだ行路が割り当てられていない乗務は１９０乗務である。図７より、分枝限定法では行路数９の計画を３時間で作成できることが期待される。一方、図７には１９０乗務に対する貪欲法の特徴がないため、２００乗務に対する特徴情報から推定値を算出する。２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。どちらも許容時間内に計画を作成できるが、行路数は分枝限定法の方が少なくなるため、作成手段選択部８は分枝限定法を選択する。
【００３８】
次に、図６を作成手段特徴情報として用いた場合を考える。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。一方、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。このとき、分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあると作成手段選択部８は判断し、貪欲法を選択する。つまり、残り１９０乗務となったとき、図６を用いたときは貪欲法を選択して行路数１１．４の計画が得られると推定するのに対して、図７を用いたときは分枝限定法を選択して行路数９の計画が得られると推定する。したがって、作成手段特徴格納部５に図７の特徴情報を用いた方が、図６の特徴情報を用いるよりも、作成手段選択部８は許容時間内でより行路の少ない計画を作成できるようになる。
【００３９】
以上のように、計画作成において、最後に切り替えた計画作成手段の作成履歴を基に、作成手段の特徴情報を作成手段特徴格納部５に追加することで、特徴情報が充実化する。すなわち、計画作成を繰り返すことにより、特徴情報が充実化する。そして、特徴情報が充実化することにより、特徴情報の推定値を算出する精度が上がり、また、作成手段選択部８が作成手段を選択する機会が増える。そのため、より質の高い計画を立案することができるようになる。
【００４０】
実施の形態３．
実施の形態１及び２においては、計画作成の許容時間は、最初に予め設定されており、作成途中に再設定される場合を考えていなかったが、計画作成途中で許容時間が変更可能であるようにしてもよい。
【００４１】
以下、許容時間が計画作成途中に変更された場合における計画作成手段の選択例を説明する。実施の形態１と同様に、計画作成開始時点においては、ダイヤ格納部１に「５００乗務」の運行ダイヤ、作成手段格納部４に「分枝限定法」と「貪欲法」が設定されているとする。また、許容時間設定部６により許容時間として「９時間」が設定され、許容時間格納部７に許容時間「９時間」が格納されているとし、作成手段特徴格納部５には、図６で示した作成手段特徴が格納されているとする。
【００４２】
行路候補の組み合わせ選択開始時点においては、実施の形態１と同様にして、作成手段選択部は貪欲法を選択する。
【００４３】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち１００乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が４００乗務となり、４００乗務以下となったとする。経過時間は１時間とする。このとき、実施の形態１と同様にして、作成手段選択部は貪欲法を選択する。
【００４４】
貪欲法によっていくつかの行路候補が採用され、運行ダイヤ内の５００乗務のうち３１０乗務が採用した行路候補に被覆され、採用した行路候補に被覆されていない乗務数が２００乗務以下となったとする。計画作成開始時点からの経過時間は３時間とする。このときに、計画作成終了までに許容される残り時間として、「２時間」が再設定されたとする。採用した行路候補に被覆されていない乗務は１９０乗務である。図６には１９０乗務に対する各作成手段の特徴がないため、分枝限定法は４００乗務に対する特徴情報から、貪欲法は２００乗務に対する特徴情報からそれぞれ推定値を算出する。まず、４００乗務に対する分枝限定法では行路数２０の計画を１２時間で作成できることが期待されるため、１９０乗務に対する分枝限定法では行路数９．５の計画を５時間４２分で作成できると推定される。次に、２００乗務に対する貪欲法では行路数１２の計画を２時間で作成できることが期待されるため、１９０乗務に対する貪欲法では行路数１１．４の計画を１時間５４分で作成できると推定される。分枝限定法では許容時間内に計画を作成できる見込みがないのに対して、貪欲法では許容時間内で計画を作成できる見込みがあるため、作成手段選択部８は貪欲法を選択する。
【００４５】
このように、計画作成途中で許容時間が再設定された場合においても、許容時間を満たす中で作成できる計画の質が最も高いと期待される計画作成手段に切り替えることができる。
【００４６】
実施の形態４．
許容時間を問わずに最適な計画を作成したい場合、許容時間設定部６で許容時間として「∞時間」あるいはそれに相当する十分大きな時間を設定する。このようにすることで、作成手段選択部８は計画作成途中で逐次、計画作成手段の中から、許容時間を問わずに一番良い評価値（質）を持つ計画を作成できる計画作成手段を選択するため、できるだけ評価値（質）の良い計画を作成できる。
【００４７】
実施の形態５．
作成手段選択部８が作成手段を選択する際、作成手段特徴格納部５に格納された特徴情報、あるいはその推定値から、作成手段格納部４に格納されたいずれの計画作成手段を用いても許容時間内で計画作成することができる作成手段を選択することができない場合には、許容時間内に計画を作成できないと判断して、計画作成部２が許容時間内に計画を作成できる見込みがないという情報を作成結果格納部３に格納し、計画作成を打ち切る。
【００４８】
このように、許容時間内に計画を作成できないと判断した時点ですぐに計画作成を打ち切るため、無駄な計算を短縮することができ、計画作成者はすぐに別の許容時間を設定して計画作成を行うことができるようになる。
【００４９】
実施の形態６．
計画の評価値（質）を問わずにできるだけ速く計画を作成したい場合、許容時間設定部６で許容時間として「０時間」を格納したとき、計画作成手段の中から評価値（質）を問わずに一番速く計画を作成できる計画作成手段を逐次選択させる。このようにすることで、計画の評価値（質）を問わない場合には、できるだけ速く計画を作成することができる。
【００５０】
なお、以上の実施の形態においては、乗務員の運用計画作成について説明したが、本願発明の運用計画作成装置は、乗務員ではなく運行機材について適用することもでき、また、運行機材及び乗務員の運用計画作成について適用することもできるものである。また、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００５１】
１ ダイヤ格納部、２ 計画作成部、３ 作成結果格納部、４ 作成手段格納部、５ 作成手段特徴格納部、６ 許容時間設定部、７ 許容時間格納部、８ 作成手段選択部、９ 経過時間取得部、１１ 許容時間設定画面、１２ テキストボックス、１３ 設定ボタン。
【特許請求の範囲】
【請求項１】
乗物の運行ダイヤに基づいて運行機材又は乗務員の運用計画を作成する運用計画作成装置において、
計画の作成手段を複数有する作成手段格納部と、
前記各作成手段に対する特徴情報を格納する作成手段特徴格納部と、
計画作成にかかる許容時間を格納する許容時間格納部と、
計画作成開始からの経過時間を取得する経過時間取得部と、
前記運行機材又は乗務員の割り当て状況、前記特徴情報、前記許容時間、及び、計画作成途中における前記経過時間に基づいて、前記複数の作成手段の中から前記許容時間内に計画作成できる最適な作成手段を計画作成途中で逐次選択する作成手段選択部と
を備えたことを特徴とする運行機材又は乗務員の運用計画作成装置。
【請求項２】
前記作成手段特徴格納部に格納された特徴情報は、前記各作成手段に対する、運行機材又は乗務員を割り当てる必要のある乗務数、計画作成にかかる計算時間、及び、計画の評価値の関係で与えられることを特徴とする請求項１記載の運行機材又は乗務員の運用計画作成装置。
【請求項３】
前記作成手段選択部が前記作成手段を選択するタイミングは、“一定周期ごと、運行機材や乗務員が割り当てられていない乗務数が変化したとき、又は、運行機材や乗務員が割り当てられていない乗務数が前記特徴情報に格納されている乗務数以下となったとき、のいずれか１つ以上”及び“計画作成開始時点”であることを特徴とする請求項２記載の運行機材又は乗務員の運用計画作成装置。
【請求項４】
前記作成手段特徴格納部は、過去に作成した計画の作成履歴を基にして、前記特徴情報を追加格納することを特徴とする請求項１から請求項３のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項５】
前記作成手段特徴格納部は、前記過去に作成した計画の作成履歴を基にして前記特徴情報を追加格納する際、前記作成手段選択部が計画作成において最後に切り替えた作成手段の特徴情報を格納することを特徴とする請求項４記載の運行機材又は乗務員の運用計画作成装置。
【請求項６】
前記許容時間格納部に格納される許容時間は、計画作成途中において変更可能であることを特徴とする請求項１から請求項５のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項７】
前記作成手段選択部が前記許容時間内に計画作成できる前記作成手段を選択することができない場合には、許容時間内に計画を作成できないと判断し、計画作成を打ち切ることを特徴とする請求項１から請求項６のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項８】
前記許容時間として０が設定されている場合には、
前記作成手段選択部が前記作成手段の中から評価値を問わずに一番早く計画を作成できる作成手段を逐次選択することを特徴とする請求項１から請求項６のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項１】
乗物の運行ダイヤに基づいて運行機材又は乗務員の運用計画を作成する運用計画作成装置において、
計画の作成手段を複数有する作成手段格納部と、
前記各作成手段に対する特徴情報を格納する作成手段特徴格納部と、
計画作成にかかる許容時間を格納する許容時間格納部と、
計画作成開始からの経過時間を取得する経過時間取得部と、
前記運行機材又は乗務員の割り当て状況、前記特徴情報、前記許容時間、及び、計画作成途中における前記経過時間に基づいて、前記複数の作成手段の中から前記許容時間内に計画作成できる最適な作成手段を計画作成途中で逐次選択する作成手段選択部と
を備えたことを特徴とする運行機材又は乗務員の運用計画作成装置。
【請求項２】
前記作成手段特徴格納部に格納された特徴情報は、前記各作成手段に対する、運行機材又は乗務員を割り当てる必要のある乗務数、計画作成にかかる計算時間、及び、計画の評価値の関係で与えられることを特徴とする請求項１記載の運行機材又は乗務員の運用計画作成装置。
【請求項３】
前記作成手段選択部が前記作成手段を選択するタイミングは、“一定周期ごと、運行機材や乗務員が割り当てられていない乗務数が変化したとき、又は、運行機材や乗務員が割り当てられていない乗務数が前記特徴情報に格納されている乗務数以下となったとき、のいずれか１つ以上”及び“計画作成開始時点”であることを特徴とする請求項２記載の運行機材又は乗務員の運用計画作成装置。
【請求項４】
前記作成手段特徴格納部は、過去に作成した計画の作成履歴を基にして、前記特徴情報を追加格納することを特徴とする請求項１から請求項３のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項５】
前記作成手段特徴格納部は、前記過去に作成した計画の作成履歴を基にして前記特徴情報を追加格納する際、前記作成手段選択部が計画作成において最後に切り替えた作成手段の特徴情報を格納することを特徴とする請求項４記載の運行機材又は乗務員の運用計画作成装置。
【請求項６】
前記許容時間格納部に格納される許容時間は、計画作成途中において変更可能であることを特徴とする請求項１から請求項５のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項７】
前記作成手段選択部が前記許容時間内に計画作成できる前記作成手段を選択することができない場合には、許容時間内に計画を作成できないと判断し、計画作成を打ち切ることを特徴とする請求項１から請求項６のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【請求項８】
前記許容時間として０が設定されている場合には、
前記作成手段選択部が前記作成手段の中から評価値を問わずに一番早く計画を作成できる作成手段を逐次選択することを特徴とする請求項１から請求項６のうちのいずれか１項記載の運行機材又は乗務員の運用計画作成装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−１４８７４２（Ｐ２０１２−１４８７４２Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１１−１０８００（Ｐ２０１１−１０８００）
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２３年１月２１日（２０１１．１．２１）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]