(57)【特許請求の範囲】
【請求項１】
コンピュータを、
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤを入力する入力手段と、
前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段と、
前記各アークについて、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいて、コストを設定するコスト設定手段と、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路を探索する巡回路探索手段と、
前記探索された巡回路を所定の評価基準に基づいて評価値を算出することにより評価を行う評価手段と、
前記巡回路探索手段が探索した巡回路の一部の巡回路を固定とし、残りの巡回路について再度探索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させる繰り返し手段と、
前記巡回路探索手段が、前記繰り返し手段による繰り返し実行により探索した巡回路の内、評価値が最良の巡回路を基に車両運用計画を作成する作成手段として機能させるための車両運用計画作成プログラム。
【請求項２】
請求項１において、
前記コスト設定手段が、所望のアークに対するコストの入力を受け付けて、当該アークのコストを設定するためのプログラムを含む車両運用計画作成プログラム。
【請求項３】
請求項１又は２において、
前記コスト設定手段が、元ノードに対応する列車の着駅と、先ノードに対応する列車の発駅との異同に応じて当該アークのコストを設定するためのプログラムを含む車両運用計画作成プログラム。
【請求項４】
請求項１〜３の何れかにおいて、
前記コスト設定手段が、元ノードに対応する列車と、先ノードに対応する列車との接続が同日に行えるか否かに応じて当該アークのコストを設定するためのプログラムを含む車両運用計画作成プログラム。
【請求項５】
請求項１〜４の何れかにおいて、
前記コスト設定手段が、前記各アークについて、当該アークの元ノードに対応する列車の着駅及び着時刻と、当該アークの先ノードに対応する列車の発駅及び発時刻と、に基づいて、交番検査用のコストを当該アークに設定するためのプログラムを含む車両運用計画作成プログラム。
【請求項６】
請求項１〜５の何れかにおいて、
前記巡回路探索手段によって探索された巡回路全体が仕業検査条件を満足するか否か、満足しない場合には満足する範囲を判別する判別手段として前記コンピュータを機能させるためのプログラムと、
前記繰り返し手段が、前記判別手段により、前記巡回路探索手段によって探索された巡回路全体が前記仕業検査条件を満足していないと判別された場合に、満足する範囲を固定とし、満足しない範囲について再度検索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させるためのプログラムと、
前記作成手段が、前記繰り返し手段により繰り返し実行されて探索された巡回路の内、前記判別手段によって巡回路全体が前記仕業検査条件を満足していると判別された巡回路であって、評価値が最良の巡回路を基に車両運用計画を作成するためのプログラムと、
を含む車両運用計画作成プログラム。
【請求項７】
請求項１〜５の何れかにおいて、
巡回路１つを記憶する巡回路記憶手段として前記コンピュータを機能させるためのプログラムと、
前記繰り返し手段が、繰り返し実行の際に、前記巡回路探索手段により探索された巡回路の評価値が、前記巡回路記憶手段に記憶されている巡回路の評価値よりも優良であった場合に、当該探索された巡回路を前記巡回路記憶手段に更新記憶させて前記繰り返し実行を行うためのプログラムと、
前記作成手段が、前記巡回路記憶手段に記憶された巡回路を基に車両運用計画を作成するためのプログラムと、
を含む車両運用計画作成プログラム。
【請求項８】
請求項１〜７の何れかにおいて、
前記評価手段が、(１)使用する車両の数、(２)検査の回数、(３)回送列車の本数、(４)回送列車の走行距離、(５)当該巡回路に含まれるアークのコスト総数、の内少なくとも１つの評価基準に基づいて、前記巡回路探索手段により探索された巡回路の評価値を算出するためのプログラムを含む車両運用計画作成プログラム。
【請求項９】
請求項１〜８の何れかにおいて、
前記巡回路探索手段が、前記コスト設定手段によって設定された各アークのコストに基づいて、アークを順次選択して巡回路を探索するためのプログラムを含む車両運用計画作成プログラム。
【請求項１０】
請求項１〜９の何れか記載の車両運用計画作成プログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項１１】
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤを入力する入力手段と、
前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段と、
前記各アークについて、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいて、コストを設定するコスト設定手段と、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路を探索する巡回路探索手段と、
前記探索された巡回路を所定の評価基準に基づいて評価値を算出することにより評価を行う評価手段と、
前記巡回路探索手段が探索した巡回路の一部の巡回路を固定とし、残りの巡回路について再度探索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させる繰り返し手段と、
前記巡回路探索手段が、前記繰り返し手段により繰り返し実行されて探索された巡回路の内、評価値が最良の巡回路を基に車両運用計画を作成する作成手段と、
を備える車両運用計画作成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、車両運用計画を作成するための車両運用計画作成プログラム、当該車両運用計画作成プログラムを記憶した記憶媒体、及び車両運用計画作成装置に関する。
【０００２】
【従来の技術】
従来、鉄道において、作成された運行スケジュール（列車ダイヤ）を実現するため、車両運用計画と呼ばれる車両の使用順序や車両に対する保守管理を含む車両の運用に関する計画を定めている。この計画においては、より車両の利用効率の高い計画が望ましく、作成者の知識や経験等に基づいて作成されるのが現状である。
【０００３】
【発明が解決しようとする課題】
ところで、車両運用計画は、作成段階において、その作成に係る様々な制約条件（例えば、交番検査や仕業検査の実施）を考慮する必要がある。このため、その規模の大きさ等によって、その作成は極めて複雑且つ困難な問題となり、作成者の負担が大きいという問題が生じていた。
【０００４】
また、車両の利用効率の良い車両運用計画を作成することは、列車運行のコストとの関連の点で極めて重要であるため、車両運用計画の作成工程は、鉄道会社の運用方針等とも密接な関係を持つ。このため、車両運用計画は、上述した制約条件を満足することに加えて、鉄道の運用方針等を考慮した作成者の意図を反映させて作成することが望まれる。
【０００５】
本発明は、上記の事情に鑑みてなされたものであり、車両を効率良く運用するための車両運用計画を、鉄道会社の運営方針等に基づいて自動的に作成することを目的とする。
【０００６】
【課題を解決するための手段】
以上の課題を解決するため、請求項１記載の車両運用計画作成プログラムは、コンピュータを、複数の列車及び各列車の着発時刻のデータを有する列車ダイヤを入力する入力手段（例えば、手入力であってもよいし、記憶媒体から読み込むこととしてもよい。）と、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段（例えば、図５に示す車両運用ネットワーク作成部１２０）と、前記各アークについて、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいて、コストを設定するコスト設定手段（例えば、図５に示す車両運用ネットワーク作成部１２０）と、前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路を探索する巡回路探索手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記探索された巡回路を所定の評価基準に基づいて評価する評価手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記巡回路探索手段が探索した巡回路の一部の巡回路を固定とし、残りの巡回路について再度探索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させる繰り返し手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記巡回路探索手段が、前記繰り返し手段による繰り返し実行により探索した巡回路の内、前記評価手段による評価結果が最良の巡回路を基に車両運用計画を作成する作成手段（例えば、図５に示す車両運用計画案作成部１４０）として機能させることを特徴とする。
【０００７】
また、請求項１１記載の車両運用計画装置は、複数の列車及び各列車の着発時刻のデータを有する列車ダイヤを入力する入力手段と、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段（例えば、図５に示す車両運用ネットワーク作成部１２０）と、前記各アークについて、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいて、コストを設定するコスト設定手段（例えば、図５に示す車両運用ネットワーク作成部１２０）と、前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路を探索する巡回路探索手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記探索された巡回路を所定の評価基準に基づいて評価する評価手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記巡回路探索手段が探索した巡回路の一部の巡回路を固定とし、残りの巡回路について再度探索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させる繰り返し手段（例えば、図５に示す車両運用計画案作成部１４０）と、前記巡回路探索手段が、前記繰り返し手段により繰り返し実行されて探索された巡回路の内、前記評価手段による評価結果が最良の巡回路を基に車両運用計画を作成する作成手段（例えば、図５に示す車両運用計画案作成部１４０）と、を備えることを特徴とする。
【０００８】
ここで、評価基準とは、例えば、作成された車両運用計画における使用編成数、車両に対して実施される仕業検査の数、回送列車の本数、回送列車の走行距離といった車両運用計画の作成に関する制約や要望に基づいて設定される評価項目のことである。
【０００９】
この請求項１又は１１記載の発明によれば、得られた巡回路を予め設定された評価基準に従って評価することが可能であり、さらに、巡回路の探索処理と、当該巡回路の評価との一連の処理を繰り返すことにより、評価が最良の巡回路を基に車両運用計画を作成するので、作成者の所望する車両運用計画を満足するような、理想的な巡回路を得ることができる。
【００１０】
また、請求項２記載の車両運用計画作成プログラムは、請求項１において、前記コスト設定手段が、所望のアークに対するコストの入力を受け付けて、当該アークのコストを設定するためのプログラムを含むことを特徴とする。
【００１１】
この請求項２記載の発明によれば、アークの元ノードに対応する列車の着時刻、及び当該アークの先ノードに対応する列車の発時刻に基づいて設定されるコストを手動で修正することができる。従って、例えば、接続の望ましさといった作成者の考えに基づいて設定されるコストの入力に応答し、列車の接続に関する作成者の意図を考慮した車両運用計画を作成することができる。
【００１２】
また、請求項３記載の車両運用計画作成プログラムのように、請求項１又は２において、前記コスト設定手段が、元ノードに対応する列車の着駅と、先ノードに対応する列車の発駅との異同に応じて当該アークのコストを設定するためのプログラムを含むこととしてもよい。
【００１３】
この請求項３記載の発明によれば、元ノードに対応する列車の着駅と先ノードに対応する列車の発駅とが異なる場合に、当該アークに設定するコストを増大させる。従って、着発駅が異なる接続（アーク）、即ち、回送列車の運転を加味した車両運用計画とすることができる。
【００１４】
また、請求項４記載の車両運用計画作成プログラムのように、請求項１〜３の何れかにおいて、前記コスト設定手段が、元ノードに対応する列車と、先ノードに対応する列車との接続が同日に行えるか否かに応じて当該アークのコストを設定するためのプログラムを含むこととしてもよい。
【００１５】
この請求項４記載の発明によれば、同日の接続が可能か否かが加味されるため、より車両数の少ない車両運用計画の作成を可能とすることができる。
【００１６】
さらに、請求項５記載の車両運用計画作成プログラムのように、請求項１〜４の何れかにおいて、前記コスト設定手段が、前記各アークについて、当該アークの元ノードに対応する列車の着駅及び着時刻と、当該アークの先ノードに対応する列車の発駅及び発時刻と、に基づいて、交番検査用のコストを当該アークに設定するためのプログラムを含むこととしてもよい。
【００１７】
この請求項５記載の発明によれば、元ノードに対応する列車の着駅及び着時刻と先ノードに対応する列車の発駅及び発時刻との間に、車両に対して実施される交番検査の所要時間を有するように列車同士を接続させることができる。これによれば、該当する列車同士の接続の際に、交番検査を実施することができる。
【００１８】
また、請求項６記載の車両運用計画作成プログラムは、請求項１〜５の何れかにおいて、前記巡回路探索手段によって探索された巡回路全体が仕業検査条件を満足するか否か、満足しない場合には満足する範囲を判別する判別手段（例えば、図５に示す車両運用計画案作成部１４０）として前記コンピュータを機能させるためのプログラムと、前記繰り返し手段が、前記判別手段により、前記巡回路探索手段によって探索された巡回路全体が前記仕業検査条件を満足していないと判別された場合に、満足する範囲を固定とし、満足しない範囲について再度検索するように、前記巡回路探索手段による探索、及び、前記評価手段による評価を繰り返し実行させるためのプログラムと、前記作成手段が、前記繰り返し手段により繰り返し実行されて探索された巡回路の内、前記判別手段によって巡回路全体が前記仕業検査条件を満足していると判別された巡回路であって、評価結果が最良の巡回路を基に車両運用計画を作成するためのプログラムと、を含むことを特徴とする。
【００１９】
この請求項６記載の発明によれば、巡回路に対応する車両運用計画が仕業検査条件を満足するように巡回路に対して一部経路を変更する処理を繰り返し、探索された仕業検査条件を満足する車両運用計画を表す巡回路に対する評価結果が最良の巡回路を車両運用計画とする。従って、仕業検査条件を満たした巡回路において、設定された評価基準に基づいた評価をすることができる。
【００２０】
また、請求項７記載の車両運用計画作成プログラムは、請求項１〜５の何れかにおいて、巡回路１つを記憶する巡回路記憶手段（例えば、図５に示す最良解格納領域６４０）として前記コンピュータを機能させるためのプログラムと、前記繰り返し手段が、繰り返し実行の際に、前記巡回路探索手段により探索された巡回路の評価結果が、前記巡回路記憶手段に記憶されている巡回路の評価結果よりも優良であった場合に、当該探索された巡回路を前記巡回路記憶手段に更新記憶させて前記繰り返し実行を行うためのプログラムと、前記作成手段が、前記巡回路記憶手段に記憶された巡回路を基に車両運用計画を作成するためのプログラムと、を含むことを特徴とする。
【００２１】
この請求項７記載の発明によれば、少なくとも得られた最良の巡回路を保持するだけでよい。
【００２２】
また、請求項８記載の車両運用計画作成プログラムは、請求項１〜７の何れかにおいて、前記評価手段が、(１)使用する車両の数、(２)検査の回数、(３)回送列車の本数、(４)回送列車の走行距離、(５)当該巡回路に含まれるアークのコスト総数、の内少なくとも１つの評価基準に基づいて、前記巡回路探索手段により探索された巡回路を評価するためのプログラムを含むことを特徴とする。
【００２３】
ここで、使用する車両の数とは、車両運用計画において計画される列車同士の接続に日またがりが生じている場合の数、回送列車の本数とは、計画された列車同士の接続において着発駅が異なる場合の数、回送列車の走行距離とは、着発駅が異なる列車同士の接続において各着発駅間の距離を累積したもののことである。
【００２４】
この請求項８記載の発明によれば、探索された巡回路を、設定された評価基準に基づいて評価することができる。また、各評価基準に対する重みを設定すれば、設定された重みに応じた評価基準の優先順位に従って巡回路を評価することができる。従って、作成者の所望する車両運用計画を満足するような、より最適な巡回路を得ることが可能となる。
【００２５】
また、請求項９記載の車両運用計画作成プログラムは、請求項１〜８の何れかにおいて、前記巡回路探索手段が、前記コスト設定手段によって設定された各アークのコストに基づいて、アークを順次選択して巡回路を探索するためのプログラムを含むことを特徴とする。
【００２６】
この請求項９記載の発明によれば、例えば、コストが小さいアークに対応する列車の接続が望ましい場合、コストの小さい値のアークを順次選択して巡回路を探索することにより、所望する車両運用計画を満足するような最適な巡回路を得ることができる。即ち、回送列車の運転回数が少ない、回送列車の走行距離が短い、車両の編成数の数が最小限であるといった、所望する車両運用計画を満足するような、より最適な巡回路を得ることができる。
【００２７】
さらに、請求項１０記載の発明は、請求項１〜９の何れか記載の車両運用計画作成プログラムを記憶したコンピュータ読み取り可能な記憶媒体である。
【００２８】
請求項１０記載の発明によれば、請求項１〜９のいずれかの発明と同様の効果を奏する記憶媒体を実現することができる。
【００２９】
【発明の実施の形態】
以下、図を参照して、本発明に係る車両運用計画作成装置の実施の形態について詳細に説明する。尚、以下、１台のパーソナル・コンピュータ（以下、パソコンという。）で車両運用計画作成装置を構成することとして説明するが、これに限定されるものではない。
【００３０】
車両運用計画は、上述したように、車両の使用順序や車両に対する保守管理を含む車両の運用に関する計画を定めたものであり、ダイヤ改正の際等において計画されて作成される列車ダイヤに基づいて作成される。
【００３１】
図１（ａ）に列車ダイヤの一例を示す。同図において、横軸を時刻、縦軸を駅ＡＡ、ＢＢ、ＣＣとして、１日分の列車ダイヤが、列車の運行を表す「列車スジ」により表現されている。また、各「列車スジ」には、対応する列車番号がそれぞれ表記されている。車両運用計画においては、この列車ダイヤを実現するために、当該列車ダイヤを構成する全ての列車に対して車両を割り当てて、車両の運用スケジュールを作成する。
【００３２】
ところで、車両に対しては、メンテナンスのため、その走行時間や距離に応じた検査を実施することが義務付けられている。具体的には、検査の周期と、当該周期に対応した検査の内容とが規定されている。特に、車両運用計画の作成時において考慮しなければならない検査は、仕業検査、及び交番検査と呼ばれる検査であり、それぞれの検査周期は、検査対象となる車両の種類等によって異なるが、例えば、仕業検査は３日毎、交番検査は３０日以内或いは走行距離３万キロ以内の内、先に達成する条件毎に１度実施しなければならない。各検査は在姿状態で実施される検査であり、仕業検査においては、目視による車両の点検が１時間程度で実施され、交番検査においては、例えば、ブレーキ装置や電気装置、走行装置といった車両の機能に関する検査が半日程度かけて実施される。また、各検査は、当該検査の際に必要な設備を備えて所定の駅等に設置された車両基地において、通常日中に実施される。
【００３３】
このため、車両運用計画は、車両に対して、仕業検査、及び交番検査が設定された検査周期（検査条件）を超過することなく実施されるように配慮して作成しなければならない。さらに、各検査の実施位置を設定する際には、当該検査の実施可能な場所、時間帯、所要時間等も考慮する必要がある。
【００３４】
図１（ｂ）に、図１（ａ）に示した列車ダイヤに基づいて作成された車両運用計画の一例を示す。同図において、横軸方向を時刻とした行路１、行路２、行路３で示す３本の行路が示されている。ここで、行路とは、ある車両の１日分の運用計画のことであり、ある１日における当該車両の運用が「横棒」により表現されている。例えば、行路１は、車両が、ＣＣ駅からＢＢ駅まで列車２として運転され、次いで、ＢＢ駅において仕業検査が実施された後、ＣＣ駅まで列車１として運転され、ＣＣ駅で折り返して列車７としてＢＢ駅まで運転されることを意味する。また、各行路を構成する「横棒」は、図１（ａ）に示す何れかの「列車スジ」に対応しており、図１（ｂ）に示す車両運用計画においては、３本の車両をそれぞれ行路１〜行路３に従って運転することにより、図１（ａ）に示す列車ダイヤを実現している。
【００３５】
さらに、図１（ｂ）に示す３本の行路は、ローテーションを組んで運用されるようになっている。即ち、行路１に割り当てられて上述したように運転された車両は、当該運転日の翌日には行路２、翌々日には行路３に従って運転され、行路１に戻るというように、３日サイクルで運用される。このことから、車両運用計画は、列車ダイヤを構成する全ての列車を同一の車両を用いてサイクリックに接続するための接続パターンを日毎に区切ることにより作成した行路の集合（交番）と考えることができる。
【００３６】
また、図１（ｂ）中に示す“仕”及び“交”は、それぞれ、上述した仕業検査及び交番検査を実施することを示す。
【００３７】
ここで、車両運用計画を作成するために列車同士を接続する際の制約について説明する。
（１）列車ダイヤに関する制約
１日分の列車ダイヤに定められた全ての列車に対して漏れや重複がないように車両を割り当てなければならない。そして、列車ダイヤに定められた各列車の始発駅、終発駅、各駅の着発時刻を守らなければならない。
（２）行路に関する制約
先ず、列車同士を接続する際に、接続する前後の列車において、前列車の終着駅と後列車の始発駅は同一駅でなければならない。例えば、Ｘ列車の終着駅とＹ列車の始発駅が同一駅でなければ、当該列車同士を接続することは不可能である。特に、ある駅に終着する列車の本数と当該駅から始発する列車の本数とが異なるといった矛盾が生じている不完全な列車ダイヤに対して車両運用計画を作成する場合には、この制約を満たすために、適宜回送列車を設定する必要がある。
【００３８】
次に、列車同士を接続する際に、翌日に運転される列車と接続する場合を除いて、前列車の着時刻と後列車の発時刻が逆転してはならない。例えば、Ｘ列車の終着駅着時刻よりＹ列車の始発駅発時刻が先行している場合、Ｘ列車とＹ列車を接続することは不可能である。
【００３９】
そして、列車同士を接続する際に、前列車の着時刻と後列車の発時刻との間に所定の時間間隔を設定しなければならない。即ち、接続する駅において、乗客・乗務員の乗り降りや清掃等を含む最小限の停止時間を確保する必要がある。
【００４０】
さらに、各駅において同時に滞留することが可能な車両の数や、該当する列車ダイヤにおいて使用可能な列車の最大数が予め設定されており、この最大数を超過しないように車両運用計画を作成しなければならない。
（３）交番に関する制約
交番において、連続する２つの行路の終了駅と開始駅は、同一でなければならない。これは、１番目の行路を走行した車両は、その翌日に２番目の行路を運転するためであり、同一でない場合は回送列車を設定する必要がある。また、交番において、上述した交番検査、及び仕業検査の実施位置を、その実施条件を満足するように設定しなければならない。
【００４１】
車両運用計画において列車の接続を計画する際には、以上説明した制約を守るとともに、さらに、作成された車両運用計画が以下に示すような事項を満足することがより望ましい。
【００４２】
即ち、鉄道会社の事業者の要望が反映されることである。
【００４３】
車両運用計画により計画された車両の運用は、鉄道運用に係るコストに影響するため、具体的には、例えば、１日の列車ダイヤを実現するために使用する車両の数（即ち、行路の数）、回送列車の本数や走行距離、或いは交番検査及び仕業検査の各検査の回数等を極力少なくしたいといった、コスト削減のための要望に沿うような車両運用計画が望まれる。
【００４４】
さらに、例えば、乱れに強いことを最優先に考えて車両運用計画を作成するといった、鉄道会社の事業者による車両運用計画の作成方針等を反映した車両運用計画が望まれる。例えば、図２に示す列車ダイヤにおいて、ＤＤ駅において予備車両を滞留させ、突発的なダイヤの乱れが発生した際に備えるために列車２と列車１７を接続したい、或いは、列車８と列車９は接続可能であるが、列車８に定常的な遅延が予想されるため、列車８の遅延を列車９の運行に影響を及ぼさないように列車８と列車９は接続したくない、といった要望に沿うような車両運用計画が望まれる。
【００４５】
本発明は、車両運用計画を、列車ダイヤを構成する全ての列車をサイクリックに接続するための１つの接続パターンとし、車両運用計画の作成を巡回セールスマン問題として捉え、上述した制約や要望に基づいて予め設定された評価基準に従った評価が最良の巡回路により表される車両運用計画案を採用することで、車両運用計画を自動的に作成するものである。
【００４６】
具体的には、列車のあらゆる接続パターンを、各列車を表すノードを列車同士の接続を表すアークにより結んだネットワーク（以下、車両運用ネットワークという。）により表現し、当該車両運用ネットワークにおいて、全てのノードを一度だけ通過して初期点に戻る巡回路を探索し、当該巡回路が示す列車の接続パターンを車両運用計画とする。また、各アークには、該当するアークに対応する列車の接続の望ましさに相当するコストが上述した制約や要望に従って設定され、このコストを当該アークにより結ばれるノード間の距離として、総距離が最短となるような巡回路を探索する。これにより、上述した車両運用計画の作成に係る制約を守り、且つ車両運用計画に対する要望をなるべく反映するような車両運用計画を作成する。
【００４７】
図３に車両運用ネットワークの一例を示す。同図に示すように、作成される車両運用ネットワークは、列車ａ〜ｊを表す各ノード間がそれぞれ双方向の有向アークにより結ばれた完全グラフのことである。例えば、列車ａを表すノードＮ１０と列車ｂを表すノードＮ１２とを結ぶアークの内、ノードＮ１２からノードＮ１０への有向アークＡ１０は、車両が列車ｂとして運転された後、列車ａとして運転されることを表す。この車両運用ネットワークにおいて、それぞれ一度だけ通過して初期点に戻るように各ノードからの有向アークを選択して巡回路を探索する。また、この際、各ノードから未到達のノードと結ばれるアークの内、コストの小さいアークを順次選択することにより巡回路を探索する。
【００４８】
具体的には、例えば、ノードＮ１２を初期点とした場合、当該ノードＮ１２から他のノードへの９本のアークＡ１０〜Ａ１８の中から、それぞれに設定されたコストの値が一番小さいアークを選択する。例えば、この９本のアークに設定されたコストの中で、アークＡ１４に設定されたコストの値が一番小さい場合には、当該アークＡ１４が選択されて、ノードＮ１２が列車ｇを表すノードＮ１４と結ばれる。そして、ノードＮ１４において、当該ノードＮ１４から未到達のノードへの有向アーク（即ち、ノードＮ１２へのアークＡ１９以外の有向アーク）からコストの一番小さいアークを選択する。以上のように、未到達のノードへのアークの内、設定されるコストの一番小さいアークを順次選択することにより、全てのノードを一度だけ通過して初期点に戻る巡回路を探索する。
【００４９】
また、本実施の形態においては、得られた巡回路（候補解）を用いて次の候補解を生成し、当該次候補解を評価してこれを最良の巡回路（最良解）とするか否かを判断する一連の処理を繰り返して巡回路を改良することにより、より良い巡回路を探索する。図４は、この巡回路探索のための処理の流れを示すフローチャートである。
【００５０】
即ち、先ず、車両運用ネットワークにおいて、任意に設定される初期点となるノードから、全てのノードを一度だけ通過して初期点に戻る巡回路を探索して初期解を生成する（ステップＳ１０）。また、この際、得られた初期解を、この段階での最良解として確定する。
【００５１】
次に、生成した初期解（最良解）の示す巡回路を、全てのノードを一度だけ通過するという条件を満たすように一部変更することにより候補解を生成する（ステップＳ１２）。続いて、生成した候補解を、最良解と比較することにより評価する（ステップＳ１４）。この際、得られた候補解が最良解よりも評価が低い（悪い）と判断した場合は、予め設定された確率に従って、当該候補解に対して次候補解の生成処理を行い、得られた次候補解を暫定解として確定する（ステップＳ１６）。これにより、最終的に得られる最良解を局所的な解にすることを防ぐとともに、より良い巡回路を探索させるための機会を提供する。
【００５２】
尚、候補解が最良解よりも評価が高い（良い）と判断した場合には、そのままステップＳ１８へ処理を移行する。そして、ステップＳ１２において生成した候補解、ステップＳ１６において生成した暫定解、既に設定されている最良解に基づいて、最良解を更新するか否かを判断して最良解を確定する（ステップＳ１８）。
【００５３】
そして、候補解の生成処理を指定回数繰り返したか否かを判定し（ステップＳ２０）、候補解を指定回数生成していないと判断した場合は、ステップＳ１２に戻って上述した処理を繰り返し、候補解を変形してより良い巡回路を探索する。また、ステップＳ２０において、候補解を指定回数生成したと判断した場合は、当該時点における最良解の示す巡回路で表される列車の接続を車両運用計画とする。
【００５４】
次に、本実施の形態における車両運用計画装置１０の機能構成について、図５を参照して説明する。同図に示すように、車両運用計画作成装置１０は、ＣＰＵ（Central Processing Unit）１００、ＲＯＭ（Read Only Memory）２００、入力装置３００、表示装置４００、通信装置５００、ＲＡＭ（Random Access Memory）６００、記憶装置７００、記憶媒体８００により構成され、記憶媒体８００以外の各部はバス９００により接続されている。
【００５５】
ＣＰＵ１００は、入力される指示に応じて所定のプログラムに基づいた処理を実行し、各機能部への指示やデータの転送等を行う。具体的には、ＣＰＵ１００は、入力装置３００を介して入力される操作信号等に応じて、ＲＯＭ２００や記憶装置７００が備える記憶媒体８００内に格納された各種プログラムを読み出してＲＡＭ６００に展開し、当該プログラムに従って処理を実行する。そして、この処理結果をＲＡＭ６００に格納するとともに、当該処理結果を表示するための表示信号を表示装置４００に出力する。さらに、ＲＡＭ６００内に格納した処理結果の一部或いは全てを、記憶媒体８００へ保存する。
【００５６】
また、ＣＰＵ１００は、本実施の形態において、記憶媒体８００に格納された車両運用計画作成プログラム８６０を読み出し、当該車両運用計画作成プログラム８６０に従って処理を実行する。このＣＰＵ１００により種々の機能が実現されるが、特に、（後述する）車両運用ネットワークを作成する機能部を車両運用ネットワーク作成部１２０、当該車両運用ネットワークに基づいて車両運用計画案を作成する機能部を車両運用計画案作成部１４０と呼び、以下説明する。また、車両運用ネットワーク作成部１２０と車両運用計画案作成部１４０とは、別個独立したＣＰＵ等によって実現してもよい。
【００５７】
ＲＯＭ２００には、ＣＰＵ１００により実行されるＩＰＬ（Initial Program Loader）プログラムや、当該ＩＰＬプログラムに係る各種初期設定値等が格納される。
【００５８】
入力装置３００は、カーソルキー、テンキー、各種ファンクションキー等を備えたキーボード、及びマウス等のポインティングデバイスを含み、キーボードにおいて押下されたキーの押下信号やマウスの位置信号等の操作信号をＣＰＵ１００に出力する。
【００５９】
表示装置４００は、ＣＲＴ（Cathode Ray Tube）やＬＣＤ（Liquid Crystal Display）等により構成され、ＣＰＵ１００から入力される表示信号に基づいて、当該表示信号に対応する表示情報を表示する。
【００６０】
通信装置５００は、装置内部で利用される情報を通信回線を介して外部とやりとりするための装置であり、他の装置と通信回線を介して接続されて所定の情報を送受すること等に利用される。
【００６１】
ＲＡＭ６００は、ＣＰＵ１００が実行する各種プログラムや、これらプログラムの実行に係るデータ等を一時的に格納するメモリ領域を備える。また、特に、後述する車両運用計画案の候補解とその評価値を保持するための格納領域６２０と、車両運用計画案の最良解とその評価値を保持するための最良解格納領域６４０と、車両運用計画案の暫定解とその評価値を保持するための暫定解格納領域６６０と、車両運用ネットワークの各アークに設定されるコストデータを保持するためのコストデータ格納領域６８０とを備える。
【００６２】
記憶装置７００は、プログラムやデータ等が予め記憶された記憶媒体８００を備え、この記憶媒体８００は磁気的、光学的記憶媒体、若しくは半導体メモリ等で構成されている。この記憶媒体８００は記憶装置７００に固定的に設けたもの、若しくは着脱自在に装着するものであり、上述した各種プログラムや、これらプログラムにおいて処理されたデータ等が記憶される。特に、記憶媒体８００には、列車ダイヤデータ８２０と、車両運用計画データ８４０と、車両運用計画作成プログラム８６０とが格納される。また、車両運用計画作成プログラム８６０は、車両運用ネットワーク作成部１２０において実行される車両運用ネットワーク作成プログラム８６２と、車両運用計画案作成部１４０において実行される車両運用計画案作成プログラム８６４とを含む。
【００６３】
次に、車両運用計画作成装置１０の動作について詳細に説明する。図６は、車両運用計画作成プログラム８６０を読み出して実行することによるＣＰＵ１００の処理動作を示すフローチャートである。
【００６４】
即ち、先ず、車両運用ネットワーク作成部１２０において、車両運用ネットワーク作成処理を実行する（ステップＳ３０）。図７に、車両運用ネットワーク作成プログラム８６２を読み出して実行することによる車両運用計画作成装置１０の動作フローを示す。
【００６５】
図７において、先ず、車両運用ネットワーク作成部１２０は、列車ダイヤデータ８２０を読み出して、該当する列車ダイヤを構成する各列車を表すノードを双方向の有向アークで結んだ車両運用ネットワークを作成する（ステップＳ５０）。
【００６６】
次いで、車両運用ネットワーク作成部１２０は、各アークに対して、当該アークにより結ばれるノード間の距離に相当するコストを、元ノードに対応する列車から先ノードに対応する列車への接続に係る所要時間に基づいて設定する（ステップＳ５２）。以下、コストの算出方法について、列車ｉを表すノードから列車ｊを表すノードへの有向アークに対するコストの算出を例にとって説明する。即ち、車両運用ネットワーク作成部１２０は、当該アークに設定するコストを以下の数式（１）に従って算出する。
【００６７】
0003989713.tif 000002
尚、ｗijを列車ｉを表すノードから列車ｊを表すノードへの有向アークに設定するコスト、ｔjdを列車ｊの始発駅からの発時刻、ｔiaを列車ｉの終着駅への着時刻、ｐ′ij及びｐ″ij（例えば、ｐ′ij＞ｐ″ij）を列車ｉと列車ｊの接続のために回送列車が運転された際のペナルティ値とする。
【００６８】
ここで、回送列車を運転した場合のペナルティ値（ｐ′ij、及びｐ″ij）について説明する。上述したように、車両運用ネットワークにおいては、全てのノード間に双方向のアークが存在する。即ち、例えば、列車ｉの終着駅と列車ｊの始発駅とが異なる等、列車ｉと列車ｊとを直接接続することが不可能な場合においても列車の接続を表すアークが存在する。この場合は、列車ｉと列車ｊを接続するため、列車ｉの終着駅から列車ｊの始発駅まで運転される回送列車を設定する必要がある。ところが、回送列車は直接旅客を輸送しないため、なるべく回送列車を利用しない車両運用計画の作成が望まれる。
【００６９】
ところで、巡回路は、よりコストの小さいアークを順次選択することにより探索されるので、ノード間を結ぶアークに対応する列車同士の接続が回送列車を利用する場合、当該アークに設定されるコストに大きい値を設定することで、なるべく該当するノード同士が接続されないように配慮することができる。即ち、ペナルティ値ｐ′ij、及びｐ″ijはなるべく回送列車を運転しない車両運用計画を作成するための値である。また、夜間の回送列車の運転は昼間の回送列車の運転より実現しやすいので、例えば、昼間に運転される回送列車の運転に係るペナルティ値をｐ′ij、夜間に運転される回送列車の運転に係るペナルティ値をｐ″ijとしてペナルティ値を使い分けてコストを算出する。
【００７０】
従って、数式（１）に示すように、各アークに設定されるコストは、列車ｉの終着駅と列車ｊの始発駅とが同一の場合には着発時刻の時間間隔に相当し、列車ｉの終着駅と列車ｊの始発駅とが異なる場合には、着発時刻の時間間隔と、列車ｉと列車ｊとを接続するために終着駅から始発駅へ回送列車を走行させることによるペナルティ値との和に相当する。
【００７１】
また、括弧内に、当該数式（１）によるコストの算出条件を示している。尚、αを回送列車の走行時間に関する定数、Ｔia→jdを列車ｉの終着駅から列車ｊの始発駅までの回送列車の走行時間、Ｔｓijを列車ｉの終着駅で列車ｊに接続するための車両の停止時間とする。また、この停止時間は、停車駅、列車種別等により予め定義されている時間であり、乗客・乗務員の乗り降りや清掃等に係る時間を含む。
【００７２】
即ち、数式（１）を用いてアークに設定されるコストを算出するための条件は、列車ｉの終着駅への着時刻と列車ｊの始発駅からの発時刻との時間間隔に関する条件であり、具体的には、列車ｉの終着駅と列車ｊの始発駅が同一の場合は着発時刻の時間間隔が停止時間以上であること、列車ｉの終着駅と列車ｊの始発駅とが異なる場合は着発時刻の時間間隔が運転される回送列車の走行時間と停車時間との和以上であることである。
【００７３】
また、上述した条件を満たしていない場合、即ち、列車ｉが、次の日に運転される列車ｊと接続される場合、車両運用ネットワーク作成部１２０は、以下の数式（２）に従ってコストを算出する。
【００７４】
0003989713.tif 000003
即ち、列車ｉの着時刻に対して列車ｊの発時刻が先行しているために列車ｉと列車ｊとを同日に接続することが不可能な場合のことであり、この場合は、数式（１）に示して説明したコストに１４４０（＝６０（分）×２４（時間））を加算した値をコストとして設定する。
【００７５】
次いで、車両運用ネットワーク作成部１２０は、上述したように各アークに設定されたコストの修正指示の入力を受け付ける（ステップＳ５３）。具体的には、例えば、なるべく接続したい列車同士の接続を表すアークのコストに十分小さい値を、また、接続したくない列車同士の接続を表すアークのコストに十分大きい値をそれぞれ設定することによりコストを修正する。これにより、車両運用計画を作成する際に、ある列車同士を接続したい、或いは接続したくないといった作成者の考えに基づいて、当該列車の接続を表すアークに設定するコストを修正することができる。従って、作成者の意図を車両運用計画になるべく反映させるように配慮することができる。
【００７６】
次いで、車両運用ネットワーク作成部１２０は、車両運用ネットワークに対して交番検査を割り当てる（ステップＳ５４）。
【００７７】
具体的には、車両運用ネットワーク作成部１２０は、先ず、列車ダイヤを構成する列車の走行距離の和と、交番検査の実施条件となる走行距離とから、当該列車ダイヤに基づいて作成される車両運用計画において実施しなければならない交番検査の回数Ｎを算出する。次いで、車両運用ネットワーク作成部１２０は、車両運用ネットワークにおいて、車両基地を備えた駅に終着する列車を表すノードを選出し、選出したノードからＮ個のノードを任意に選択してマークすることにより交番検査を割り当てる。車両は、マークされたノードに対応する列車として運転された後に交番検査が実施され、次いで、マークされたノードからの到達する先ノードに対応する列車として運転される。
【００７８】
図８に、図１（ａ）に示す列車ダイヤに基づいて作成した車両運用ネットワークの一例を示す。例えば、ＢＢ駅及びＣＣ駅において車両基地を備えるとすると、この列車ダイヤを構成する列車の総走行距離と交番検査の実施条件から例えば、作成される交番において実施すべき交番検査の回数が１回と判断された場合、ＢＢ駅及びＣＣ駅に終着する列車１、２、３、５、６、７を表す各ノードを選出する。そして、選出されたノードから任意にノードを１つ選択して（例えば、ノードＮ２０）マークする。
【００７９】
続いて、車両運用ネットワーク作成部１２０は、マークされたノードからの有向アークのコストを交番検査の所要時間に基づいて補正する（ステップＳ５６）。即ち、該当するアークに設定されたコストを、以下に示す数式（３）に従って算出したコストにより補正する。
【００８０】
0003989713.tif 000004
尚、Ｔkを交番検査の実施に係る所要時間とする。
【００８１】
即ち、マークされた元ノードと結ばれる先ノードとの遷移時間がＴk以上となるため、マークされたノード位置において交番検査に係る所要時間を確保することができる。尚、当日において交番検査に係る所要時間を確保することができない場合は、翌日に交番検査を実施することとして以下の数式（４）に従ってコストを修正する。
【００８２】
0003989713.tif 000005
以上説明したように、車両運用ネットワーク作成部１２０により車両運用ネットワークが作成されると、次いで、車両運用計画案作成部１４０が、車両運用計画案作成プログラム８６４を読み出すことにより車両運用計画案作成処理を実行する。先ず、車両運用計画案作成部１４０は、候補解作成処理を実行する（ステップＳ３２）。図９に、この候補解作成処理を実行することによる車両運用計画案作成部１４０の動作フローを示す。
【００８３】
図９において、先ず、車両運用計画案作成部１４０は、任意のノードを初期点とした巡回路を探索する（ステップＳ６０）。具体的には、車両運用ネットワークにおいて、例えば、選択可能なアークからコストの最も小さいアークを順次選択することにより全てのノードを１度だけ通過して初期点に戻る巡回路を探索する。
【００８４】
図１０に、図８に示して説明した車両運用ネットワークにおいて、列車２を表すノードＮ３０を初期点として探索された巡回路の一例を示す。尚、図１０において、設定されたコストに応じてアークの線の太さを変更して示している。即ち、列車７から列車４へ接続、及び列車６から列車５への接続を表すアークに設定されたコストにはその他の列車の接続を表すアークに設定されたコストより大きい値が設定される。これは、図１（ａ）に示すように列車４からの発時刻に対して列車７への着時刻が先行しているため、列車７は翌日に運転される列車４と接続されること、また、列車６の終着駅と列車５の始発駅が異なるために回送列車が設定されたことによりペナルティ値が設定されることによるものである。
【００８５】
次いで、車両運用計画案作成部１４０は、探索された巡回路に対して仕業検査の実施位置を割り当てる（ステップＳ６２）。具体的には、車両運用計画案作成部１４０は、先ず、車両基地を備えた駅に終着する列車、或いは車両基地を備えた駅から始発する列車のうち、次の列車（ノード）を全て選出する。即ち、当該着発時刻が仕業検査の可能な時間帯であるとともに、着発時刻の時間間隔が該当する駅における停止時間を除いて、仕業検査の実施のために必要な時間以上の時間間隔となるアーク（列車の接続）により結ばれる元ノードを全て選出する。次いで、車両運用計画案作成部１４０は、探索された巡回路において、初期点から順番に、選出したノードの中から仕業検査を割り当てるノードを選択する。
【００８６】
次いで、車両運用計画案作成部１４０は、巡回路が仕業検査の実施周期条件を満足するか否かを判定し（ステップＳ６４）、実施周期条件を満足すると判断した場合には、当該巡回路を候補解に確定する。例えば、図１０に示す巡回路において、ノードＮ３２に仕業検査が割り当てられる。
【００８７】
また、ステップＳ６４において、仕業検査の実施周期条件を満足しないと判断した場合には、ステップＳ６０に戻って処理を繰り返す。具体的には、車両運用計画案作成部１４０は、初期点から巡回路を辿って仕業検査の実施周期条件に従わない最初のノード位置から実施周期条件を満足するとともに、仕業検査の実施場所及び時間帯を満足するノードを選出し、当該ノードからのアークを変更し、到達する先ノードからの巡回路を再度探索する。
【００８８】
例えば、図１１（ａ）に示す巡回路が探索された場合を例に説明する。即ち、車両運用計画案作成部１４０は、当該巡回路を初期点Ｎ４０からノードを順番に辿ることにより、仕業検査の実施周期条件に従わない最初のノードを検出する。次いで、車両運用計画案作成部１４０は、当該ノードから実施周期条件を満足するノードを選出するとともに、選出したノード以降の巡回路を無効とする。例えば、図１１（ｂ）において、仕業検査の実施周期条件に従わない最初のノードがノードＮ４６であったとする（即ち、ノードＮ４２までの巡回路は仕業検査の実施条件を満足する。）。この場合に、ノードＮ４６から巡回路を逆に辿ることで実施周期条件を満足するノードとしてノードＮ４４が選出されると、ノードＮ４４以降の一点破線で示す接続を全て切断する。
【００８９】
そして、車両運用計画案作成部１４０は、この段階で未到達のノードの表す列車との着発時刻の時間間隔が上述した停止時間を除いて仕業検査のための所要時間以上の時間間隔を有するような列車を表すノードを検出し、当該ノードから任意に１つの先ノードを選択してアークにより結ぶとともに、当該先ノードからの新たな巡回路を探索する。即ち、図１１（ｃ）において、ノードＮ４４からのアークＡ４０が切断され、例えば、上述した条件を満足する未到達のノードからノードＮ４８が選出された場合に、当該ノード同士をアークＡ４２により結ぶとともに、ノードＮ４８からの巡回路を再度探索する。
【００９０】
次に、車両運用計画案作成部１４０は、候補解として確定された巡回路の評価値を以下の数式（５）に従って算出する（ステップＳ６６）。
【００９１】
【数１】
0003989713.tif 000006
尚、ｘiを車両運用計画を評価する基準となる種々の項目に対応するパラメータ値、ｐiをそれぞれの評価基準に対する重みとする。例えば、ｎ＝４とし、ｘ１を使用編成数、ｘ２を仕業検査回数、ｘ３を回送列車の本数、ｘ４を回送列車の走行距離、そしてｐ１〜ｐ４をｘ１〜ｘ４それぞれに対応する重みとする。
【００９２】
即ち、車両運用計画案作成部１４０は、例えば、候補解の表す車両運用計画において使用する車両の数（行路数）、巡回路に対して割り当てられた仕業検査の数、回送列車の本数、或いは走行距離といった評価項目となるパラメータに対応する重みにより、各評価基準の重要度を車両運用計画に反映させることができる。また、この際、算出された評価値とともに確定された巡回路を候補解格納領域６２０に格納する。
【００９３】
以上説明したように、候補解は、得られた巡回路に対応する車両運用計画において仕業検査の施行条件が満足されるように巡回路の修正を繰り返し、最終的に生成した検査条件を満足する巡回路に対して、車両運用計画に対する要望に基づいた評価を行うことにより作成される。
【００９４】
次いで、車両運用計画案作成部１４０は、最良解格納領域６４０に格納される巡回路の評価値と、候補解格納領域６２０に格納される巡回路の評価値とを比較判定して（ステップＳ３４）、最良解の評価値の方が大きいと判断した場合、即ち得られた候補解が最良解よりも評価が高い場合に、最良解格納領域６４０を候補解格納領域６２０で更新する（ステップＳ３６）。
【００９５】
また、ステップＳ３４において、候補解の評価値の方が大きいと判断した場合、車両運用計画案作成部１４０は、突然変異処理を実行するか否かを判定する（ステップＳ３８）。具体的には、予め設定された確率に従って突然変異処理を実行し、先ず、暫定解格納領域６６０の巡回路を候補解格納領域６２０の巡回路で更新する（ステップＳ４０）。
【００９６】
次いで、車両運用計画案作成部１４０は、候補解作成処理を実行する（ステップＳ４２）。具体的には、車両運用計画案作成部１４０は、暫定解格納領域６６０に保持される巡回路において任意にノードを１つ選択し、当該ノードからのアークを変更するとともに、当該アークにより結ばれた先ノード以降の経路を無効とし、この未完成の巡回路に対して候補解作成処理を実行する。
【００９７】
次いで、車両運用計画案作成部１４０は、得られた候補解の評価値と最良解の評価値とを比較判定して（ステップＳ４４）、最良解の評価値の方が大きいと判断した場合は、最良解格納領域６４０の巡回路を候補解格納領域６２０の巡回路で更新する（ステップＳ４６）。また、ステップＳ４４において、候補解の評価値の方が大きいと判断した場合、車両運用計画案作成部１４０は、候補解格納領域６２０の巡回路を暫定解格納領域６６０の巡回路で更新する。
【００９８】
そして、車両運用計画案作成部１４０は、ステップＳ３２〜Ｓ４８として説明した処理を繰り返して候補解を指定回数生成したか否かを判定し（ステップＳ５０）、指定回数生成していないと判断した場合は、ステップＳ３２に戻って上述した処理を繰り返す。具体的には、車両運用計画案作成部１４０は、候補解格納領域６２０に保持される巡回路において任意にノードを１つ選択し、当該ノードからのアークを変更するとともに、当該アークにより結ばれた先ノード以降の経路を無効とし、この未完成の巡回路に対して上述した処理を繰り返す。
【００９９】
また、ステップＳ５０において、候補解を指定回数生成したと判断した場合は、本処理を終了する。
【０１００】
以上説明した通り、本発明を適用した車両運用計画作成装置１０によれば、車両運用計画に対する制約に基づいて各アークに対するコストを設定し、コストのなるべく小さいアークを選択することにより巡回路を作成するとともに、作成した巡回路を車両運用計画に対する制約や要望に応じて評価する。さらに、得た巡回路を変更することにより、より良い巡回路の取得を試み、最終的に最良の巡回路を基に車両運用計画を作成する。これによれば、車両運用計画に対する制約を満足するとともに、作成者の要望を可及的に反映させた車両運用計画を生成し得る。
【０１０１】
尚、本発明の実施の形態においては、各駅の着発時刻は列車ダイヤに従うこととして説明したが、例えば、得られた候補解を使用する車両の数を重要視して評価する場合において、各駅の着発時刻を多少変更することにより使用する列車の数を減少させることが判明した場合、列車ダイヤを変更することとしてもよい。これによれば、より効率の良い車両の運用を提案することを可能とし、所望する車両運用計画を得ることができる。
【０１０２】
また、巡回路の探索の方法は、現ノードに接続されているアークの内、最もコストの小さいアークを選択することにより次ノードを選択していく方法としたが、この方法に限られるものではない。例えば、現ノードに接続されているアークと、その先のアークとのコストの総和から、アークを選択していくといった先読み的な方法により巡回路を探索してもよい。
【０１０３】
また、図６に示して説明した車両運用計画作成処理を、複数の異なる交番検査案に対して行うこととしてもよい。これによれば、より最良の巡回路を探索することができる。
【０１０４】
また、本実施の形態において、列車ダイヤは、記憶媒体８００内に保存されていることとして説明したが、例えば、通信装置５００及び通信回線を介して列車ダイヤデータが格納されるデータベースとデータ通信を行い、該当する列車ダイヤデータをダウンロードすることとしても勿論構わない。
【０１０５】
さらに、市販のパソコンを用いて、実際に運転されている列車ダイヤに対して本発明を適用して車両運用計画を作成し、実際の車両運用計画と比較する実験を行った結果、ほぼ一致する車両運用計画を得ることがわかった。また、要した処理時間は数十分であった。
【０１０６】
【発明の効果】
本発明によれば、作成者の所望する車両運用計画を満足するような、理想的な巡回路を得ることが可能となる。
【図面の簡単な説明】
【図１】（ａ）は列車ダイヤの一例、（ｂ）は（ａ）に示す列車ダイヤに基づく車両運用計画の一例を示す図である。
【図２】列車ダイヤの一例を示す図である。
【図３】本実施の形態における車両運用ネットワークの一例を示す図である。
【図４】巡回路探索のための処理の流れの一例を示すフローチャートである。
【図５】本実施の形態の機能ブロックの一例を示す図である。
【図６】車両運用計画作成処理の一例を示すフローチャートである。
【図７】車両運用ネットワーク作成処理の一例を示すフローチャートである。
【図８】候補解の作成を説明するための図である。
【図９】候補解作成処理の一例を示すフローチャートである。
【図１０】候補解の一例を示す図である。
【図１１】仕業検査の割り当てを説明するための図である。
【符号の説明】
１０            車両運用ネットワーク作成装置
１００        ＣＰＵ
１２０      車両運用ネットワーク作成部
１４０      車両運用計画案作成部
２００        ＲＯＭ
３００        入力装置
４００        表示装置
５００        通信装置
６００        ＲＡＭ
６２０      候補解格納領域
６４０      最良解格納領域
６６０      暫定解格納領域
６８０      コストデータ格納領域
７００        記憶装置
８００        記憶媒体
８２０      列車ダイヤデータ
８４０      車両運用計画データ
８６０      車両運用計画作成プログラム
８６２    車両運用ネットワーク作成プログラム
８６４    車両運用計画案作成プログラム
９００        バス
【図１】
0003989713.tif 000007
【図２】
0003989713.tif 000008
【図３】
0003989713.tif 000009
【図４】
0003989713.tif 000010
【図５】
0003989713.tif 000011
【図６】
0003989713.tif 000012
【図７】
0003989713.tif 000013
【図８】
0003989713.tif 000014
【図９】
0003989713.tif 000015
【図１０】
0003989713.tif 000016
【図１１】
0003989713.tif 000017