(57)【特許請求の範囲】
【請求項１】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成する作成手段と、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定する設定手段と、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換する交換手段と、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力する出力手段と、を具備し、
前記設定手段は、各日ごとに、運用未割当の車両がある場合には、運用未割当の車両に前日の到着場所に滞在するヨビノードを割当てることを特徴とする車両運用計画作成装置。
【請求項２】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成する作成手段と、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定する設定手段と、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換する交換手段と、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力する出力手段と、を具備し、
前記交換手段は、各経路での交換するアーク数を示す交換回数を１から順に設定し、全ての経路に対応する全ての車両が目標日に目標日場所にいるように、交換回数閾値までの複数回のアークの交換により得られる１個以上の候補を生成することを特徴とする車両運用計画作成装置。
【請求項３】
前記交換手段は、各経路での交換するアーク数を示す交換回数を１から順に設定し、目標日に目標日場所にいない車両には前記交換回数閾値から交換回数を引いた数を新閾値として、該新閾値までアークを交換することを特徴とする請求項２に記載の車両運用計画作成装置。
【請求項４】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成する作成手段と、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定する設定手段と、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換する交換手段と、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力する出力手段と、を具備し、
前記交換手段は、目標日に目標日場所にいない車両があり、かつ、車両の運用を限定する運用限定制約がある車両がある場合に、アークの交換を行うことを特徴とする車両運用計画作成装置。
【請求項５】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成し、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定し、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換し、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力することを具備し、
前記経路を設定することは、各日ごとに、運用未割当の車両がある場合には、運用未割当の車両に前日の到着場所に滞在するヨビノードを割当てることを特徴とする車両運用計画作成方法。
【請求項６】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成し、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定し、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換し、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力することを具備し、
前記他のアークと交換することは、各経路での交換するアーク数を示す交換回数を１から順に設定し、全ての経路に対応する全ての車両が目標日に目標日場所にいるように、交換回数閾値までの複数回のアークの交換により得られる１個以上の候補を生成することを特徴とする車両運用計画作成方法。
【請求項７】
前記他のアークと交換すること手段は、各経路での交換するアーク数を示す交換回数を１から順に設定し、目標日に目標日場所にいない車両には前記交換回数閾値から交換回数を引いた数を新閾値として、該新閾値までアークを交換することを特徴とする請求項６に記載の車両運用計画作成方法。
【請求項８】
初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成し、
初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定し、
目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換し、
全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力することを具備し、
前記他のアークと交換することは、目標日に目標日場所にいない車両があり、かつ、車両の運用を限定する運用限定制約がある車両がある場合に、アークの交換を行うことを特徴とする車両運用計画作成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発時刻・出発場所・到着時刻・到着場所が定まった複数の運用全てを、運用限定制約を考慮しながら、使用可能な複数の車両への割当を行う車両運用計画作成装置および方法に関する。
【０００２】
特に車両運用計画の制約を満たす初期案の作成に係わる
【背景技術】
【０００３】
鉄道事業者の多くでは、列車運用計画により、全ての列車スジについて、始発駅から終着駅までの間の発着時刻を定めているが、実際に運用列車を運用するためには、それらの列車に割当てる鉄道車両編成（以下、「車両」と呼ぶ）を決定する必要がある。この車両の割当を決めることを車両運用と呼ぶ。
【０００４】
車両運用を考える場合、列車スジごとに車両の割当を考える場合もあるが、スジを何本か繋いだひと続きのスジ群を単位として、車両の割当を考える場合もある。そこで、車両を割当てられる最小単位を「運用」と呼ぶこととし、これら運用を、いずれかの車両にもれなく割当てる作業をおこなうものとする。
【０００５】
各運用には、出発時刻・出発場所・到着時刻・到着場所が定まっており、この複数の運用全てを、運用限定制約を考慮しながら、使用可能な複数の車両にもれなく割当てる。ただし、同一日同一車両に両立可能な複数の運用を割当てることもありうるとする。
【０００６】
この車両運用には、「鉄道のスケジューリングアルゴリズム」（鉄道総合技術研究所  運転システム研究室著）によると、一般的な制約としては、以下のようなものがある。  
（１）各車両は、前日の最終到着地からしか翌日は出発できない、また１日当たり複数の運用を同一車両に割当てる場合には、２番目以降に割当てる運用は、直前の到着地から出発する運用に限定される（以下、「つなぎ制約」と呼ぶ）。  
（２）各路線の設備条件の違いにより、運用可能な車両形式が限定される。  
（３）車両ごとの、全般検査、交番検査、仕業検査などの検査については、法令により定期的に実施することが義務付けられている。  
（４）車体や客室内の清掃、補給等のメンテナンス作業の時間を定期的に確保する必要がある。
【０００７】
一般にはこれらの制約を満たすような計画案を一定の期間ごとに作成することが多いが、この作業を「白紙計画作成」と呼ぶ。なおこの場合は、直前の期間との接続を考える必要があるため、計画初日に関する制約が新たに課される。
【０００８】
一方、ダイヤ乱れ等により運用が乱れた際や、緊急で車両の作業予定が入った際等には、元の計画を変更する必要があるが、その場合には、緊急の状況を勘案しながら、かつできるだけ早い日数で元の計画に戻すような計画変更を行うことが多い。この作業を「修正計画作成」と呼ぶ。この修正計画作成の場合は、目標日以降は元の計画予定が実施できなければならないため、計画初日に関する制約だけでなく、車両ごとに目標日に到達すべき場所に関する制約が別途課される。この「白紙計画作成」と「修正計画作成」の作業をまとめて、車両運用計画作成と呼ぶ。
【０００９】
この複雑な制約を有する車両運用計画作成の問題に対し、従来多くの鉄道事業者では計画作成担当者をおき、担当者自身の経験と知識に基づき、手作業で作成することが多かった。一般には、一定の期間ごとに図６のような車両運用表を作成する白紙計画作成を行い、またこの計画を適宜変更しながら修正計画作成をおこなってきた。
【００１０】
この車両運用計画作成を自動作成する技術はいくつか開示されている。例えば、車両運用計画作成問題を、列車スジをノード、列車スジの接続可能性をアークとするグラフ（かつ異なる日の同一の列車スジを同一ノードとみなす）によりモデル化し、このグラフ上の巡回路を得ることにより、周期的な車両運用計画案を自動作成する技術がある。また、車両運用計画作成問題を、運用をノード、運用の接続可能性をアークとするグラフによりモデル化し、このグラフ上で遺伝的アルゴリズムを用いることにより、より評価値を高めるような計画案を自動作成する技術がある。さらに、車両運用計画作成問題を、周期的なローテーションパターンを最初に作成し、そのパターンを必要に応じて適宜変更することにより、計画案を自動作成する技術について開示されている（例えば、特許文献１参照）。
【特許文献１】特開２０００−７１９８８公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
計画作成担当者が白紙計画作成または修正計画作成をおこなう場合、その作成手順は試行錯誤ベースであるため、膨大な時間を要し、また計画の品質が担当者個人の能力に依存する、といった問題点がある。また、修正計画作成をおこなう場合には、人間の作業は必ずしも完全ではないため、必要以上に予定を変更してしまい変更作業のオーバーヘッドが大きくなる場合や、解があるにも関わらず解を発見できないためにやむを得ず回送や運用振り替え、あるいは車両交換といった緊急的な手法に頼らざるを得ない場合等がある。
【００１２】
一方、従来技術では、周期的な車両運用計画案、あるいはほとんど周期的な車両運用計画案を作ることはできるものの、これは一般的によく出現する状況に対応できない。なぜなら、実際のダイヤには平日ダイヤと土休日ダイヤ等が混在しており、かつ祭日が非周期的に現れることから、そもそも周期的ではない。また、車両に課される検査計画や清掃計画等の制約には作業員や作業場所の予定等が絡むため、周期的にはなりにくい。
【００１３】
次に、グラフ上で遺伝的アルゴリズムを用いる手法では、初期解を発見した後に、その初期解からより評価値の高い解を順次生成するが、初期解を発見すること自体が困難な場合があり、求解できるのは制約が緩い単純な問題に限られる。特に本発明が対象とするような、目標日に到達すべき場所に関する制約がある場合、運用限定制約の制約が厳しい場合、同一日同一車両に複数の運用の割当がある場合、といった現実によく現れる制約を有する問題においては、初期解を得ること自体が大変困難な問題となる。
【００１４】
さらに、特許文献1の周期的なローテーションパターンを作成する技術では、初期解の探索段階、もしくはより良い計画を作成するための計画変更段階において制約を満たさない計画となった場合に、バックトラック探索により制約を満たす解を探索する。ただしこの方法は、制約を満たさない車両とその他の車両との間の、交換１回の解を探索しているに過ぎず、このような単純な方法で制約を満たす解を得られるのは、制約が緩い単純な場合に限られる。実際にこの手法では、本発明の以下の実施形態で述べるいずれの問題に対しても解を得ることはできない。また、この発明に述べられたような、制約条件が増えるたびに、バックトラックの検索条件を増やすようなやり方は好ましくない。なぜなら、実際の問題のような制約が日々変化するような状況においては、バックトラック探索部のメンテナンスコストが大きくなり運用が困難となるからである。
【００１５】
以上の従来技術によっては、厳しい制約を有する車両運用計画に対し、制約を満たす解を得ることは困難であると予想される。
【００１６】
この発明は、上述した事情を考慮してなされたものであり、与えられた制約を満たす車両運用表をより短時間で自動作成する車両運用計画作成装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
上述の課題を解決するため、本発明の車両運用計画作成装置は、初日から目標日までの間で車両ごとに、初日場所と、出発時刻、出発場所、到着時刻、および、到着場所で定まる運用と、目標日場所とをそれぞれノードで表し、場所と時刻とより接続可能なノードをすべてアークで接続した運用接続グラフを作成する作成手段と、初日から順に目標日までの各日に車両ごとに、前記アークで接続された前記運用を割当て、接続された前記運用を結ぶ１本の経路を設定する設定手段と、目標日に目標日場所にいない車両がある場合には、全ての車両が目標日に目標日場所にいるように、複数の車両に対応する複数の経路において前記アーク単位で他のアークと交換する交換手段と、全ての車両が目標日に目標日場所にいる複数の経路が見つけ出された場合には、この経路に対応する運用の割当を車両運用計画として出力する出力手段と、を具備することを特徴とする。
【発明の効果】
【００１８】
本発明の車両運用計画作成装置および方法によれば、与えられた制約を満たす車両運用表をより短時間で自動作成する。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照しながら本発明の実施形態に係る車両運用計画作成装置および方法について詳細に説明する。なお、以下の実施形態中では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。  
本実施形態では、車両運用計画作成の問題を、ノードとアークで示した運用接続グラフでモデル化する。ノードは運用を示し、アークは運用間の接続可能性を示す。各車両の一連の割当をこの運用接続グラフ上の１本の経路として表す。
【００２０】
この運用接続グラフ上で、後述するグリーディー割当部と、計画作成の途中段階でグリーディー割当が行き詰まった場合に行き詰まりを打開する候補を列挙する後述するバックトラック探索部とを、繰り返し実行することにより、車両運用計画自動作成をおこなう。  
特に、本実施形態では、バックトラック探索部が行き詰まりを解消する際に、運用接続グラフ上の計画済アークを基準として、交換回数の少ない、より単純な変更案から網羅的に解を列挙することが特徴的である。
【００２１】
（システムの基本構成）  
車両運用計画作成装置の基本構成について図１を参照して説明する。  
実施形態の車両運用計画作成装置は、車両運用計画自動作成部１０１，入力処理装置１０２，出力処理装置１０３からなる。
【００２２】
入力処理装置１０２は、各種データ入力を受けつけ、初日情報１２１，目標日情報１２２，車両情報１２３，運用パターン情報１２４，運用限定制約情報１２５からなる入力データに変換する。
【００２３】
車両運用計画自動作成部１０１は、初日情報１２１，目標日情報１２２，車両情報１２３，運用パターン情報１２４，運用限定制約情報１２５を入力し、所定の演算を行い、計画候補案１１２，または失敗シグナル１１５を出力する。
【００２４】
出力処理装置１０３は、計画候補案１１２，または失敗シグナル１１５を入力とし、これらに簡単な加工を施し、車両運用表１１４を出力する。
【００２５】
このうち、入力処理装置１０２および出力処理装置１０３の詳細に関しては、本発明では特に限定しないため、以下では、主に車両運用計画自動作成部１０１の詳細に関して述べる。
【００２６】
＜初日情報１２１および目標日情報１２２＞  
次に、車両運用計画自動作成部１０１の入力となる、初日情報１２１および目標日情報１２２に関して図２を参照して説明する。  
初日情報１２１は、図２のように、白紙計画作成または修正計画作成のそれぞれに関して、計画予定を作成する期間のうちの初日の日付を表す。目標日情報１２２は、図２のように、白紙計画作成または修正計画作成のそれぞれに関して、計画予定を作成する期間の目標日の日付を表す。
【００２７】
＜車両情報１２３＞  
次に、車両運用計画自動作成部１０１の入力となる、車両情報１２３に関して図３を参照して説明する。  
この車両情報１２３は、図３のように、車両ごとの計画初日の場所、および修正計画作成の際の目標到着場所の情報を有する。
【００２８】
＜運用パターン情報１２４＞  
次に、車両運用計画自動作成部１０１の入力となる、運用パターン情報１２４に関して図４を参照して説明する。  
運用パターン情報１２４は、図４のように、日ごとのダイヤパターンに応じて定まる当該日に割当てるべき運用のパターンを定義したものである。例えば、平日ダイヤと休日ダイヤが異なる場合、一般にはこの運用パターンも異なる。この運用パターン情報１２４は、パターンごとに複数の運用から構成される。
【００２９】
＜運用データ＞  
次に、運用パターン情報１２４を構成する運用データの詳細に関して説明する。  
運用データには、図４に示すように、出発場所、出発時刻、到着場所、到着時刻の４個の属性がある。以下ではこのことを模式的に表すために、図１８の上図のように運用をブロックで表し、このブロックを、縦を車両、横を日付および時刻とするテーブルに順次配置することで、運用の車両への割当を表現することにする。
【００３０】
この図１８のように、同一車両への割当は、横１列に並ぶため、運用間のつなぎ制約は、初日に割当てた運用から順に横に見ることにより、確認することができる。すなわち、同一車両に割当てる前後の運用は、前運用の到着地と次運用の出発値が一致し、かつ前運用の到着時間が次運用の出発時間前となる必要がある。
【００３１】
また、修正計画作成の場合は、車両情報１２３で目標日に定められた場所に到達する必要がある。これを「目標日制約」と呼ぶ。
【００３２】
＜運用限定制約情報１２５＞  
次に、車両運用計画自動作成部１０１の入力となる、運用限定制約情報１２５に関して図５を参照して説明する。  
運用限定制約情報１２５は、図５のように、ある日ある車両について、割当可能な運用を限定する情報である。例えば、法定検査や清掃などが、１日目に車両１で実施される場合等に、その作業実施と両立しない運用がある場合には、「車両１の１日目に運用５７を割当てられない」、といった制約が有りうる。  
また、運用の特殊事情（車両の台数や保安装置の制約など）により、運用に割当てられる車両が限定される場合は、「車両４は常に運用２３しか割当てられない」、といった制約が有りうる。  
さらに、ある車両が一定期間工場に入る場合などは、一定の期間、運用を割当てられない状況となり、「車両６は、２日目から１０日目までは、運用を割当られない」、といった制約が有りうる。
【００３３】
＜車両運用計画自動作成部１０１の出力＞  
次に、車両運用計画自動作成部１０１の出力に関して図６を参照して説明する。  
車両運用計画自動作成部１０１は、車両運用計画作成に成功した場合は、計画候補案１１２を出力する。これは図６の車両運用表１１４の元となるデータである。一方、車両運用計画自動作成部１０１は、車両運用計画作成に失敗した場合は、失敗シグナル１１５を出力する。
【００３４】
＜運用接続グラフ１１３＞  
次に、以下の実施形態で用いる運用接続グラフ１１３に関して図７を参照して説明する。  
運用接続グラフ１１３は、図７のように、各日の運用パターンを構成する各運用をノードとし、その運用間の接続可能性を有向アークで接続したグラフである。なお、実際に存在する運用のみをノードとすると、例えば、１日目に場所Ａに到着する運用ノードは、２日目以降に場所Ａを出発する全ての運用ノードと接続可能であるため、煩雑となる。そこで各日ごとに、「ヨビノード」と呼ばれる１日同じ場所に留まることを表現するノードを用意することし、１日１個も運用を割当てないノードについては、このヨビノードを割当てることとした。ここで、Ａに滞在するヨビノードでは、終日同一の場所Ａに滞在するヨビ車両を表現するため、属性を以下のように定める。  
・出発場所：Ａ  
・到着場所：Ａ  
・出発時刻：十分早い時刻  
・到着時刻：十分遅い時刻
このようにヨビノードの属性を定めることにより、以下では、このヨビノードとその他の元からある運用ノードを区別なく扱い、かつヨビノードが割当てられた車両については、他の運用を割当てられないという制約を実現できる。また、このヨビノードを導入することにより、次ノードとの間の接続可能性は、当日および翌日のみを考えれば十分となる効果がある。
【００３５】
さらに運用接続グラフにおいては、説明の簡単のため図７のように、車両ごとに初日出発場所に相当するノード（以下、「０日目ノード」という）を追加し、初日の各運用に相当するノードのうち出発場所が０日目ノードの場所と一致するノードがある場合については、０日目ノードとこのノードを有向アークにより接続するものとする。
【００３６】
＜車両運用計画作成の問題設定＞  
この運用接続グラフによりモデル化した場合、各車両について、０日目ノードからつなぎ制約を満たす経路があり、かつ各車両の経路に含まれるノードに重なりがなく、かつヨビノード以外のノード全てが必ずいずれかの車両の経路に含まれる場合には、これらの経路に相当する計画は、例えば図８のような、つなぎ制約を満たす計画候補案１１１となる。
【００３７】
図８は２日目までの割当の例であり、図８のグラフでは、各車両に割当てた運用ノードをつなぐ経路を実線で表している。以下では、運用接続グラフ上の接続可能アークのうち、この実線上のアークを「計画済みアーク」と呼び、割当済の運用のつなぎをこの計画済みアークにより表現した運用接続グラフを「割当グラフ」と呼ぶ。以下のグリーディー割当やバックトラック探索は、この割当グラフを更新しながらおこなう。
【００３８】
図８の場合は、確かに各車両の０日目ノードから始まる経路は、つなぎ制約を満たし、かつ、１日目と２日目のヨビノード以外のノード全てが、いずれかの車両に割当てられているため、つなぎ制約を満たす計画候補案１１１となる。このつなぎ制約を満たす計画候補案１１１は、出力処理装置１０３により図６のような車両運用表１１４に変換される。
【００３９】
（第１の実施形態）  
本実施形態では、運用限定制約情報１２５を考慮しない場合の修正計画作成の場合について説明する。なお、白紙計画作成の場合には、以下の処理において、目標日制約がないとみなせばよい。
【００４０】
本実施形態の車両運用計画作成装置について図９を参照して説明する。  
本実施形態の車両運用計画作成装置は、入力処理装置１０２、初日情報記憶部９０１、目標日情報記憶部９０２、車両情報記憶部９０３、運用パターン情報（運用データ）記憶部９０４、運用接続グラフ作成部９０５、運用接続グラフ記憶部９０６、グリーディー割当部９０７、バックトラック探索部９０８、つなぎ制約を満たす計画候補案（割当グラフ）記憶部９０９、計画候補案（割当グラフ）記憶部９１０、失敗シグナル記憶部９１１、出力処理装置１０３、車両運用表記憶部９１２を含む。車両運用計画自動作成部１０１は、運用接続グラフ作成部９０５、運用接続グラフ記憶部９０６、グリーディー割当部９０７、バックトラック探索部９０８、つなぎ制約を満たす計画候補案記憶部９０９、計画候補案記憶部９１０を含む。
【００４１】
車両運用計画自動作成部１０１は、初日情報記憶部９０１に記憶されている初日情報１２１，目標日情報記憶部９０２に記憶されている目標日情報１２２，車両情報記憶部９０３に記憶されている車両情報１２３，運用パターン情報記憶部９０４に記憶されている運用パターン情報１２４を入力とし、計画に失敗した場合に失敗シグナル１１５を、計画に成功した場合に計画候補案１１２を出力する。
【００４２】
運用接続グラフ作成部９０５は運用接続グラフ１１３を作成する。その詳細については後に図１１を参照して説明する。
【００４３】
グリーディー割当部９０７は、つなぎ制約を満たすように、ｍ（ｍ：自然数）日目パターンに含まれる各運用ノード全てをいずれかの車両に割当てる。その詳細については後に図１３を参照して説明する。グリーディー割当部９０７は、ｍ日目に１個も運用ノードが割当てられない車両に、この車両の前日の到着場所に滞在するヨビノードを割当てる。その詳細については後に図１５を参照して説明する。
【００４４】
バックトラック探索部９０８は、目標日制約を満たさない車両ｈがある場合、車両ｈに関して、バックトラック探索をおこなう。このバックトラック探索については、交換閾値ｋを１からｍａｘまで順次増やしながら、バックトラック成功となるまで、繰り返し実行する。バックトラック探索の詳細については後に図１７を参照して説明する。
【００４５】
なお、修正計画作成の場合に、目標日情報１２２を入力とせず目標日情報１２２を１から順次大きくしながら、できるだけ早く元の計画に復帰するような拡張も可能である。この場合、車両情報１２３の各車両の目標到達場所の情報は、目標日の候補日全てに対して有する必要がある。
【００４６】
＜第１の実施形態の制御フロー＞  
次に、第１の実施形態に係る車両運用計画作成装置の動作の一例について図１０を参照して説明する。ここでは修正計画作成の目標日がｎ（ｎ：自然数）日目である場合を考える。なお、この図１０のフローは、以下の第２の実施形態および第３の実施形態においても共通のフローとなる。ただし、第３の実施形態においては、分岐ステップＳ１００５において目標日制約のみではなく、運用限定制約もチェックする点が異なる。
【００４７】
まず、Ｓｔｅｐ１では、運用接続グラフ１１３の作成をおこなう（ステップＳ１００１）。次に、ｍ＝１として（ステップＳ１００２）、ｍ＝＝ｎとなるまでステップＳ１００３〜ステップＳ１０１０のループ１を繰り返す。Ｓｔｅｐ２、Ｓｔｅｐ３、およびＳｔｅｐ４では、初日から目標日までの各日（ｍ日目）に、グリーディー割当部９０７およびバックトラック探索部９０８により、割当グラフを更新しながら制約を満たす計画作成をおこなう。
【００４８】
Ｓｔｅｐ２では、グリーディー割当部９０７が、つなぎ制約を満たすように、ｍ日目パターンに含まれる各運用ノード全てをいずれかの車両に割当てる（ステップＳ１００３）。次にＳｔｅｐ３では、グリーディー割当部９０７が、ｍ日目に１個も運用ノードが割当てられない車両に、この車両の前日の到着場所に滞在するヨビノードを割当てる（ステップＳ１００４）。
【００４９】
この時点で、目標日制約を満たさない車両ｈがない場合（ステップＳ１００５のＮＯ）は、ｍが目標日（ｍ＝＝ｎ）である場合にはループ１を抜けて終了し、ｍが目標日でない場合にはｍを１増やし翌日に進む。なお、グリーディー割当および、バックトラック探索が完了した状態である、ステップＳ１００５の時点では、必ずつなぎ制約を満たす割当となるため、全ての車両が目標日制約を満たす割当は、全ての制約を満たす割当となる。また、目標日制約は、目標日前日（ｍ＝＝ｎ−１）以外はチェックを行わないため、実際にはステップＳ１００５においてＹｅｓとなるのは、ｍ＝＝ｎ−１の場合に限られる。
【００５０】
一方、目標日制約を満たさない車両ｈがある場合（ステップＳ１００５のＹＥＳ）、車両ｈに関して、ｋ＝１として（ステップＳ１００６）、ｋ＝＝ｍａｘとなるまでステップＳ１００７〜ステップＳ１００９のループ２を繰り返す。Ｓｔｅｐ４では、バックトラック探索部９０８によりバックトラック探索をおこなう。このバックトラック探索については、交換閾値ｋを１からｍａｘまで順次増やしながら、バックトラック成功となるまで、繰り返し実行する。バックトラック成功（ステップＳ１００８のＹＥＳ）となった場合は、再びステップＳ１００５に進み、ｋ＝ｍａｘとしても、バックトラック成功とならない場合には、失敗シグナルを出力して終了する。
【００５１】
以上の処理により、目標日までの全ての運用の割当に成功した場合は、車両運用計画表を出力して終了する。なお、図１０のフローについては、次に掲げるいくつかの変更があった場合においても同様の効果が得られる。  
まず、図１０のＳｔｅｐ２では、１日分の運用全てをまずグリーディー割当により割当てた後にバックトラック探索をするフローとしたが、運用１個ごとにグリーディー割当とバックトラック探索を繰り返すようなフローとしてもよい。また、図１０のＳｔｅｐ３では、当該日に１個も運用ノードが割当てられない車両に、ヨビノードを割当てるフローとしたが、ある場所への終日滞在をヨビノードにより表現せず、運用接続グラフの有向アークで結ばれる条件を変更することにより表現することも可能である。さらに、図１０のＳｔｅｐ４のバックトラック探索では、予め最大交換閾値ｍａｘを決めておき、閾値ｋを順次増やしながらおこなうこととしたが、最初から最大交換閾値ｍａｘを閾値としてバックトラック探索をおこなうフローとしてもよい。
【００５２】
＜運用接続グラフ作成部９０５＞  
次に、運用接続グラフ作成部９０５が運用接続グラフ１１３を作成する動作の一例について図１１を参照して説明する。  
まず、各車両に０日目ノードを割当てる（ステップＳ１１０１）。０日目ノードの割当の例について図１２を用いて説明する。車両情報１２３が図３であるとすると、車両１の初日場所がＡであるため、０日目ノードとしては、Ａノードを割当てる。このノードは、１日目に場所Ａを出発場所とする運用と接続可能である。同様に、車両２にはＢノード，車両３にはＢノードを割当てる（図７を参照）。
【００５３】
次に、１日ごとにＳｔｅｐ１およびＳｔｅｐ２を順次実行することでノードを作成する。すなわち、ｍを１に設定し、ｍ＝＝ｎとなるまでステップＳ１１０３〜ステップＳ１１０５のループ１を繰り返し、その次にステップＳ１１０６のループ２を繰り返す。Ｓｔｅｐ１ではｍ日目パターンに含まれる運用に相当するノードを追加し、Ｓｔｅｐ２ではｍ日目に必要なヨビノードを追加する。また、このヨビノードは、場所ごとに可能性がある最大数以上の数作成しておく。
【００５４】
１日目および、２日目の運用パターンとして、図４を仮定すると、図７のように、１日目ノードとして、８９，４１，７９，８３，４３，および５７の各運用ノードが追加され、２日目ノードとしては、３９および５３の運用ノードが追加される。また、各日について場所ごとのヨビノード（この場合１個ずつ）を追加する。
【００５５】
次に、前記作成した各ノードｐを順に辿り、接続可能なノードｑに対し、有向アークで結ぶ（ステップＳ１１０６）。ここでノードｐと接続可能な条件は、ノードｑがノードｐと同日もしくは翌日のノードであり、ノードｐの到着場所とノードｑの出発場所が一致、かつノードｐの到着時刻がノードｑの出発時刻よりも前であることである。図７の例では、各ノードに相当する運用の出発時刻、出発場所、到着時刻、到着場所に基づき、接続可能なノード間がアークで結ばれている。
【００５６】
＜グリーディー割当部９０７＞  
次に、グリーディー割当部９０７の動作の一例について図１３を参照して説明する。  
グリーディー割当は、ｍ日目の運用パターンに含まれる各運用を出発時刻が早い順につなぎ制約を満たす割当可能な車両に割当てる。例えば、図１４の例では、出発時刻が早い順に８９→４１→７９といった順序で割当をおこなう。なお、図１３のフローでは、ｍ日目の未割当運用があるかどうか判定し（ステップＳ１３０１）、未割当運用がある場合には、ｍ日目の運用パターンに含まれる各運用を出発時刻が早い順に割当可能な車両に割当てる（ステップＳ１３０２）こととしたが、これは、全ての運用を確実に割当てるための方法の１つである。よって、全ての運用を割当てられる方法であれば、特にこの順序には限定しない。
【００５７】
＜最大限ヨビ車両を確保するグリーディー割当部の工夫の例＞  
ここで割当て可能な車両が複数あり、かつその中に、当該日の運用が既に割当てられた車両と、当該日の運用が未だ割当てられていない車両がある場合には、前者の既に割当てられた車両に優先的に割当てるという基準を設けてもよい。
【００５８】
例えば、図１４の例で７９運用を割当てた次に、７９運用の次に出発時刻が早い８３運用の割当先を考える。この８３運用の割当先としては、つなぎ制約を満たすものとして、車両１、車両３および車両４の３通りの可能性がある（車両２は、４１運用の到着時刻が８３運用の出発時刻より遅いため割当不可である）。ここで、上記の基準を採用することとすると、既に運用が割当たった車両１、車両３、および未だ運用が割当っていない車両４と３通りの可能性のうち、既に運用が割当たった車両１、車両３のいずれかに割当てることになる。
【００５９】
このような基準を設けると、グリーディー割当終了後に得られる割当ては、ヨビ車両を最大限に確保する割当てとなる。実際の車両運用計画においては、不測の事態に備えて、ヨビ車両をできるだけ確保することは重要であるため、このような基準は有用となる場合が多い。
【００６０】
＜ヨビノード割当＞  
次に、グリーディー割当部９０７が行う、ヨビノード割当について図１５を参照して説明する。  
ヨビノードの割当は、ｍ日目の運用の割当終了後に運用未割当の車両があるかどうか判定し（ステップＳ１５０１）、１個も運用が割当てられていない車両それぞれに、前日の最終到着場所に滞在する、ヨビノードを割当てる（ステップＳ１５０２）。図１６の例では、２日目の運用全て（３９、５３）をグリーディー割当で割当てた後に車両２には、１個も運用が割当てられていないため、車両２にヨビノードを割当てる。この場合に、車両２の１日目の最終到着場所はＡであるため、場所Ａのヨビノードを割当てる。
【００６１】
＜バックトラック探索＞  
次に、バックトラック探索部９０８が行う、車両ｈが制約を満たさない場合の交換閾値がｋ回の場合のｍ日目までのバックトラック探索の詳細について図１７を参照して説明する。  
（ループ１全経路の列挙）  
まず図１７のバックトラック探索では、最初のループ１により、車両ｈの０日目ノードを起点とする、つなぎ制約を満たす経路全てのうち、交換回数ｋ回以下のものを順に調べる（ただし、この経路は、計画済みでないヨビノードを含まない経路とする）。ここで交換回数とは、割当グラフ上で、当該経路が計画済アークでないアーク（以下、「交換アーク」と呼ぶ）を通った回数とする。
【００６２】
運用接続グラフ上で車両の０日目からｍ日目までの、つなぎ制約および目標日制約を満たす交換回数ｋ回以下の経路ｐを全て求め、全ての経路を調べるまで、ステップＳ１７０１〜ステップＳ１７０３のループ１を繰り返す。まず、経路ｐに対応する交換を全て行い（ステップＳ１７０１）、経路ｐ上にある車両の全てがつなぎ制約および目標日制約を満たすかどうかを判定する（ステップＳ１７０２）。これらの制約を満たす場合にはバックトラックは成功したとして処理を終了する（ステップＳ１７０５）。ステップＳ１７０２でこれらの制約を満たさない場合にはステップＳ１７０１での交換を元に戻し（ステップＳ１７０３）、新たな交換回数でステップＳ１７０１を行う。
【００６３】
具体的には、例えば、図８の割当グラフで、車両１を起点としたつなぎ制約および目標日制約を満たす経路には、ｐ１＝Ａ→８９→４３→Ａヨや，ｐ２＝Ａ→８９→５７→Ａヨなどがある。経路ｐ１では、アーク８９→４３が交換アークであるためｐ１は交換回数１。経路ｐ２では、アーク８９→５７および５７→Ａヨが交換アークであるためｐ２は交換回数２の経路となる。
【００６４】
ここで交換回数ｋ回以内の経路を全列挙する問題は、割当済みアークに重み０、それ以外の交換アークに重み１を与えた、割当グラフ上で、距離ｋ以内の経路全てを列挙する問題となる。距離ｋ以内の経路全てを列挙する手法としては、深さ優先法、幅優先法、最良優先法など様々な手法が知られており、これらのうちいずれかを用いればよい。
【００６５】
（Ｓｔｅｐ１交換の実行）  
前記の処理により、車両ｈの０日目ノードを起点とする、交換閾値ｋ回以下のつなぎ制約を満たす経路ｐが得られた場合は、経路ｐの交換アークと対応する交換を全て実行する（ステップＳ１７０１）。ここで交換とは、車両ｈと、交換アークの行先ノードが割当てられていた車両ｈ２との、当該交換アークノード以降の経路を全て取り換えることを意味するものとする。例えば、図８の経路ｐ１＝Ａ→８９→４３→Ａヨの場合は、交換アーク８９→４３に基づく車両１の交換後の経路は、Ａ→８９→４３→Ａヨとなり、一方、交換アークの行先ノード４３が割当てられていた車両２の交換後の経路は、（元の車両２の経路上の運用４３の直前のノードである４１と、元の車両１の経路上の運用８９の直後の運用である運用８３を利用し）Ｂ→４１→８３→５３となる。この割当グラフは実はつなぎ制約を満たさないが、この時点ではチェックを行わない。なお、経路ｐ２のように交換アークを複数含む場合は、経路上０日目ノードに近い交換アークに相当する交換から順に交換を実行する。
【００６６】
（制約ｃｈｅｃｋ）  
このＳｔｅｐ１の交換の後に、交換された全ての車両のつなぎ制約および目標日制約のチェックを行い、もしいずれの制約も満たした場合（ステップＳ１７０２のＹＥＳ）は、車両ｈおよび関係する全ての車両の制約を満たす割当グラフを作成できたこととなるため、バックトラック成功となり終了する。一方いずれかの制約を満たさなかった場合（ステップＳ１７０２のＮＯ）は、当該経路ｐと対応する交換を元に戻し（ステップＳ１７０３）、次の経路候補へと進む。
【００６７】
＜第１の実施形態の具体例＞  
以上説明した第１の実施形態の適用例を、初日＝１、目標日ｎ＝２、交換閾値ｍａｘ＝２としたバックトラック探索を中心に、具体例により説明する。なお図１８以降の図では、上に運用ブロック割当の図を、下に割当グラフを図示する。  
まず、図１０のフローに従い、２日目のグリーディー割当までを行い、図１８のような割当グラフが得られたものとする（１日目は、より単純な処理であるため説明を省略する）。この場合、車両１が目標日制約を満たさない（ステップＳ１００５のＹＥＳ）ため、ｈ＝１としてバックトラック探索のフロー（図１７）に進む。
【００６８】
最初にｋ＝１の場合は、まず車両１の０日目ノードであるＡノードを起点とする距離１の経路を探索し、例えば、経路ｐ１＝Ａ→８９→４３→Ａヨが得られる（図１９）。ここで、経路ｐ１はつなぎ制約も車両１の目標日制約も満たすため図１７のＳｔｅｐ１に進み、この経路ｐ１に基づく交換を実行し、図２０のような割当グラフが得られる。
【００６９】
次に、この割当グラフをチェックすると、車両２の運用４１と運用８３は接続可能でない（接続可能アークがないため）ため、つなぎ制約を満たさない（ステップＳ１７０２のＮＯ）。よって経路ｐ１に基づく交換を元に戻し（図１７のＳｔｅｐ２）、次の経路に進む。この後、交換回数１の経路で、つなぎ制約および目標日制約を満たすものは存在しないため、ｋ＝２とする。
【００７０】
ｋ＝２の場合は、車両１の０日目ノードであるＡノードを起点とする距離２の経路を探索し、例えば、経路ｐ２＝Ａ→８９→５７→Ａヨが得られる（図２１）。ここで、経路ｐ２はつなぎ制約も車両１の目標日制約も満たすためステップＳ１７０１に進み、この経路ｐ２に基づく交換を実行すると、図２２のような割当グラフが得られる。
【００７１】
次に、この割当グラフをチェックすると、車両２、車両３共に、つなぎ制約および目標日制約を満たすため（ステップＳ１７０２のＹＥＳ）バックトラック成功となる。
【００７２】
よって、バックトラック探索のフロー（図１７）を抜け、再び図１０のフローの図１０のステップＳ１００５に進むが、今度は、全ての車両が目標日制約を満たすため（ステップＳ１００５のＮｏ）バックトラック探索を行わない。ここで目標日までの計画作成が終了した（ｍ＝＝ｎ(＝２)である）ことからループを抜けて、計画作成終了となる。
【００７３】
以上に説明した第１の実施形態によれば、つなぎ制約を満たすように、日にちごとにその日にちに含まれる各運用ノード全てをいずれかの車両に割当て、目標日制約を満たさない車両には運用ノードの組み合わせを網羅的に探索することにより、つなぎ制約および目標日を満たす修正計画作成問題の制約を満たす車両運用表を短時間で自動作成することができる。
【００７４】
（第２の実施形態）  
本実施形態は、バックトラック探索時に起点となる車両以外の交換も行う修正計画を作成する場合である。本実施形態の車両運用計画作成装置は、第１の実施形態と同様であるが、動作が少し異なる。
【００７５】
＜第２の実施形態の制御フロー＞  
まず第２の実施形態に係る車両運用計画作成装置の動作の一例について図２３を参照して説明する。この第２の実施形態の制御フローは、バックトラック探索のフローが図１７から、図２３に変わる点を除くと、第１の実施形態のフローチャート（図１０）と全く同じである。よって以下では第２の実施形態のバックトラック探索の詳細について、図２３のフローチャートを用いて説明する。
【００７６】
図２３のフローチャートは、第１の実施形態の図１７のフローチャートと比べると、ステップＳ１７０１とステップＳ１７０３との間に、ステップＳ２３０１、ステップＳ２３０２、ステップＳ２３０３が挿入されている点のみが異なる。すなわち第２の実施形態では、制約を満たす経路ｐ（交換回数ｋ’）に基づく交換を実行後、つなぎ制約もしくは目標日制約を満たさない車両ｈ２があり、かつｋ＞ｋ’（ステップＳ２３０１のＹＥＳ）である場合に、この車両ｈ２を起点として、再びこの手続きＴ２そのものを交換閾値をｋ”（＝ｋ−ｋ’）として実行（再帰呼出し）し（ステップＳ２３０２）、バックトラックが成功するかどうかの判定をおこなう（ステップＳ２３０３）。
【００７７】
ここで車両ｈは制約を満たさない車両であることから、制約を満たす経路ｐは少なくとも１回以上交換が必要なため必ずｋ’＞０となる。よって必ずｋ＞ｋ”（＝ｋ−ｋ’）が成り立つことから、再帰呼出しごとに交換閾値（ｋ→ｋ”．．．）が減少する。したがって、再帰呼び出しの深さは手続きＴ２が最初に呼び出された際の交換閾値ｋ回以下であり、この手続きＴ２が必ず停止することが保証される。
【００７８】
＜第２の実施形態の具体例＞  
この第２の実施形態のバックトラック探索に関して、具体例（図２４）を用いて説明する。なお、初日＝１、目標日ｎ＝２、交換閾値ｍａｘ＝２とする。
【００７９】
まず、図１０のフローに従い、２日目のグリーディー割当までを行い、図２４のような割当グラフが得られたものとする。この割当グラフでは、車両１の目標日制約を満たさないため、ｈ＝１として、バックトラック探索のフロー（図２３）に進む。なお以下では、バックトラック探索Ｔ２が最初に呼び出された際の交換閾値がｋ＝１の場合にバックトラック失敗となった後の、バックトラック探索Ｔ２の交換閾値がｋ＝２となった状況であるものとする。
【００８０】
バックトラック探索では、まず車両１の０日目ノードであるＡノードを起点とする距離２の経路を探索し、例えば、経路ｐ３＝Ａ→８９→Ａヨ（交換回数ｋ’＝１）が得られる（図２５）。ここで、経路ｐ３はつなぎ制約も車両１の目標日制約も満たすため、図２３のＳｔｅｐ１に進みこの経路ｐ３に基づく交換を実行すると、図２６のような割当グラフが得られる。
【００８１】
次に、この割当グラフをチェックすると、車両２の目標日制約を満たさず（図２３のステップＳ１７０２のＮＯ）かつｋ＞ｋ’（２＞１）（図２３のステップＳ２３０１のＹＥＳ）であるため、図２３のＳｔｅｐ３に進み、今度は、車両ｈ’（＝２）の交換閾値ｋ”（＝２−１）であるバックトラック探索Ｔ２（ｈ’，ｋ”）を再帰的に呼び出す。
【００８２】
よって今度は車両ｈ＝２を起点とする交換閾値１のバックトラック探索をおこなう。この場合に、例えば図２７のような経路ｐ４＝Ａ→５１→Ｂヨ（交換１回）が得られる。ここで、経路ｐ４はつなぎ制約も車両１の目標日制約も満たすため、図２３のＳｔｅｐ１に進み経路ｐ４に基づく交換を実行すると、図２８のような割当グラフが得られる。
【００８３】
次にこの割当グラフをチェックすると、車両２、車両３共に、つなぎ制約および目標日制約を満たすためバックトラック成功となる。よって、再帰呼び出し後のバックトラック探索のフロー（図２３）を抜け、再帰呼び出し前のバックトラック探索のフローも抜け、再びステップＳ１００５に進むが、今度は、全ての車両が目標日制約を満たすため（ステップＳ１００５のＮＯ）バックトラックは行わない。ここで目標日までの計画作成が終了した（ｍ＝＝ｎ(＝２)である）ことからループを抜けて、作成終了となる。
【００８４】
以上に説明した第２の実施形態によれば、交換回数がｋ回以内の解を網羅的に調べることができるため、第１の実施形態よりも高い可能性で、車両運用表を短時間で自動作成することができる。
【００８５】
（第３の実施形態）  
本実施形態は、車両運用計画自動作成部１０１に入力する情報として、運用限定制約情報１２５を加えた場合である。  
本実施形態の車両運用計画作成装置は、第１の実施形態の車両運用計画作成装置の装置部分に加えて、運用限定制約情報記憶部２９０１を設けている。他は、第１の実施形態と同様である。
【００８６】
運用限定制約情報記憶部２９０１は、運用限定制約情報１２５を記憶していて、グリーディー割当部９０７およびバックトラック探索部９０８にこの情報を提供する。運用限定制約情報１２５の情報は、運用限定制約のチェックの際に用いる。
【００８７】
＜第３の実施形態の制御フロー＞  
まず第３の実施形態に係る車両運用計画作成装置の動作の一例について図３０を参照して説明する。この第３の実施形態の制御フローは、図１０のフローチャートのステップＳ１００５において、目標日制約のみではなく運用限定制約もチェックする点、およびバックトラック探索のフローが図２３から、図３０に変わる点を除くと、第２の実施形態のフローチャートと全く同じである。よって以下では第３の実施形態のバックトラック探索の詳細について、図３０のフローチャートを用いて説明する。
【００８８】
図３０のフローチャートにおける、図２３のフローチャートとの相異点は、ループ１およびステップＳ３００１において満足すべき制約として、つなぎ制約、目標日制約に加えて、運用限定制約が加わった点のみである。
【００８９】
＜第３の実施形態の具体例＞  
この第３の実施形態のバックトラック探索に関して、具体例（図３１）を用いて説明する。なお、初日＝１、目標日ｎ＝２、交換閾値ｍａｘ＝２とする。また運用限定制約として、車両１の１日目に５７運用を割当てはならないという制約があるものとする。
【００９０】
まず、図１０のフローに従い、２日目のグリーディー割当までを行い、図３１のような割当グラフが得られたものとする。この割当グラフでは、車両１の１日目に５７運用が割当てられており運用限定制約を満たさないため、ｈ＝１として、バックトラック探索のフロー（図３０）に進む。なお以下では、ｋ＝１の探索後の状況を考え、ｋ＝２とする。バックトラック探索では、まず車両１の０日目ノードであるＡノードを起点とする距離２の経路を探索し、例えば、経路ｐ５＝Ａ→８９→４３→Ａヨ（交換回数ｋ’＝２）が得られる（図３２）。ここで、経路ｐ５はつなぎ制約も車両１の目標日制約も満たすため、図３０のＳｔｅｐ１に進み、この経路ｐ５に基づく交換を実行すると、図３３のような計画が得られる。
【００９１】
次にこの割当グラフをチェックすると、車両１、車両２共に、つなぎ制約、目標日制約、運用限定制約を満たすためバックトラック成功となる。よって、バックトラック探索のフロー（図２３）を抜け、再びステップＳ１００５に進むが、今度は、全ての車両が目標日制約を満たすため（ステップＳ１００５のＮＯ）バックトラックは行わない。ここで目標日までの計画作成が終了した（ｍ＝＝ｎ(＝２)である）ことからループを抜けて、作成終了となる。
【００９２】
以上に説明した第３の実施形態によれば、運用限定制約を満たす修正計画作成問題の制約を満たす車両運用表を短時間で自動作成することができる。
【００９３】
＜ヨビノードに関する工夫＞  
なお前記の第１の実施形態から第３の実施形態のバックトラック探索においては、ヨビノードを通常の運用と同一視しているため、仮に上記のグリーディー割当において、ヨビ車両を最大限確保する割当計画を作成した場合には、以降のバックトラック探索においても、ヨビ車両を最大限確保した割当計画しか得られないこととなる。この結果、例えば、図３４の右上図のような、ヨビ車両の数が１台少ない割当は実現できなくなる。
【００９４】
一般には、前記のように、ヨビ車両を最大限確保することが重要とされることが多いが、他の制約との兼ね合いで、ヨビ車両を最大限確保しない割当計画を作成したい可能性も有りうる。このような場合には、場所Ｂに関するヨビノードの各属性の定義を予め以下のようにしておく。（上記の定義とは、到着時刻の定義が異なる）  
・出発場所：Ｂ  
・到着場所：Ｂ  
・出発時刻：十分早い時刻  
・到着時刻：十分早い時刻
このようにしておくと、ヨビノードの後に、当該日に場所Ｂを出発場所とする全ての運用ノードと接続可能となるため、図３４の下図のような交換が可能となり、ヨビ車両の数が最大数でない（この場合最大数より１台少ない）割当計画を得ることができる。
【００９５】
以上に示した実施形態によれば、つなぎ制約を満たすように、日にちごとにその日にちに含まれる各運用ノード全てをいずれかの車両に割当て、目標日制約（および運用限定制約）を満たさない車両には運用ノードの組み合わせを網羅的に探索することにより、与えられた制約を満たす車両運用表を短時間で自動作成することができる。
【００９６】
なお本発明では、運用可能な車両の限定制約、車両ごとの検査・清掃制約、工場入場等による車両の使用不可制約などの種々雑多な制約を、一般化された運用限定制約の表現で統一的に処理できる特長がある。よって実際の運用において、制約が追加されたり、変更された場合においても、制約処理エンジン自体を変更する必要はなく、運用限定制約の作成手法を変更すればよい。このためメンテナンスコストを低減できる効果がある。
【００９７】
また、以上の実施形態では基本的に、しらみ潰しベースの探索方法を取っていることもあり、探索方法自体を制御するためのパラメータが存在せず、適用対象路線あるいは運用状況が変化するごとにパラメータチューニングするコストを低減できる効果がある。
【００９８】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００９９】
【図１】実施形態の車両運用計画作成装置の基本構成を示す図。
【図２】図１の車両運用計画自動作成部の入力となる初日情報および目標日情報の一例を示す図。
【図３】図１の車両運用計画自動作成部の入力となる車両情報の一例を示す図。
【図４】図１の車両運用計画自動作成部の入力となる運用パターン情報の一例を示す図。
【図５】図１の車両運用計画自動作成部の入力となる運用限定制約情報の一例を示す図。
【図６】図１の車両運用計画自動作成部の出力となる計画候補案からなる車両運用表の一例を示す図。
【図７】運用接続グラフの一例を示す図。
【図８】割当グラフの一例を示す図。
【図９】第１および第２の実施形態の車両運用計画作成装置のブロック図。
【図１０】図９の車両運用計画作成装置の動作の一例を示すフローチャート。
【図１１】図９の運用接続グラフ作成部の動作の一例を示すフローチャート。
【図１２】各車両に０日目ノードを割当てる一例を示す図。
【図１３】図９のグリーディー割当部の動作の一例を示すフローチャート。
【図１４】１日目のグリーディー割当の一例を示す図。
【図１５】図９のグリーディー割当部によるヨビノード割当の一例を示すフローチャート。
【図１６】２日目の車両２へのヨビノード割当の一例を示す図。
【図１７】図９のバックトラック探索部の動作の一例を示すフローチャート。
【図１８】第１の実施形態の適用例を示す図。
【図１９】図１８の車両１を起点とする経路Ｐ１を発見した場合を示す図。
【図２０】図１９の経路Ｐ１に基づいて交換を行った場合を示す図。
【図２１】図１８の車両１を起点とする経路Ｐ２を発見した場合を示す図。
【図２２】図２１の経路Ｐ２に基づいて交換を行った場合を示す図。
【図２３】第２の実施形態での図９のバックトラック探索部の動作の一例を示すフローチャート。
【図２４】第２の実施形態の適用例を示す図。
【図２５】図２４の車両１を起点とする経路Ｐ３を発見した場合を示す図。
【図２６】図２５の経路Ｐ３に基づいて交換を行った場合を示す図。
【図２７】図２４の車両１を起点としてバックトラック探索を再帰実行した場合を示す図。
【図２８】図２７の経路Ｐ４に基づいて交換を行った場合を示す図。
【図２９】第３の実施形態の車両運用計画作成装置のブロック図。
【図３０】第３の実施形態での図９のバックトラック探索部の動作の一例を示すフローチャート。
【図３１】第３の実施形態の適用例を示す図。
【図３２】図３１の車両１を起点とする経路Ｐ５を発見した場合を示す図。
【図３３】図３２の経路Ｐ５に基づいて交換を行った場合を示す図。
【図３４】ヨビ車両が１台少ない割当の実現を説明するための図。
【符号の説明】
【０１００】
１０１・・・車両運用計画自動作成部、１０２・・・入力処理装置、１０３・・・出力処理装置、１１１・・・つなぎ制約を満たす計画候補案、１１２・・・計画候補案、１１３・・・運用接続グラフ、１１４・・・車両運用表、１１５・・・失敗シグナル、１２１・・・初日情報、１２２・・・目標日情報、１２３・・・車両情報、１２４・・・運用パターン情報、１２５・・・運用限定制約情報、９０１・・・初日情報記憶部、９０２・・・目標日情報記憶部、９０３・・・車両情報記憶部、９０４・・・運用パターン情報記憶部、９０５・・・運用接続グラフ作成部、９０６・・・運用接続グラフ記憶部、９０７・・・グリーディー割当部、９０８・・・バックトラック探索部、９０９・・・計画候補案記憶部、９１０・・・計画候補案記憶部、９１１・・・失敗シグナル記憶部、９１２・・・車両運用表記憶部、２９０１・・・運用限定制約情報記憶部。
【図１】
0005075577.tif 000002
【図２】
0005075577.tif 000003
【図３】
0005075577.tif 000004
【図４】
0005075577.tif 000005
【図５】
0005075577.tif 000006
【図６】
0005075577.tif 000007
【図７】
0005075577.tif 000008
【図８】
0005075577.tif 000009
【図９】
0005075577.tif 000010
【図１０】
0005075577.tif 000011
【図１１】
0005075577.tif 000012
【図１２】
0005075577.tif 000013
【図１３】
0005075577.tif 000014
【図１４】
0005075577.tif 000015
【図１５】
0005075577.tif 000016
【図１６】
0005075577.tif 000017
【図１７】
0005075577.tif 000018
【図１８】
0005075577.tif 000019
【図１９】
0005075577.tif 000020
【図２０】
0005075577.tif 000021
【図２１】
0005075577.tif 000022
【図２２】
0005075577.tif 000023
【図２３】
0005075577.tif 000024
【図２４】
0005075577.tif 000025
【図２５】
0005075577.tif 000026
【図２６】
0005075577.tif 000027
【図２７】
0005075577.tif 000028
【図２８】
0005075577.tif 000029
【図２９】
0005075577.tif 000030
【図３０】
0005075577.tif 000031
【図３１】
0005075577.tif 000032
【図３２】
0005075577.tif 000033
【図３３】
0005075577.tif 000034
【図３４】
0005075577.tif 000035