(57)【要約】【課題】  車両に対して実施される検査がその検査周期及び実施条件を満足するように確実に割り当てられた車両運用計画であって、且つ車両を効率良く運用することができる車両運用計画を自動的に作成すること。【解決手段】  車両運用計画作成部１２０は、検査周期を満足するために最低限必要な仕業検査の検査回数を想定する。そして、車両運用計画作成部１２０は、列車運用ネットワークを構成するアークのうち、当該アークにより表される列車の接続の間合いに車両検査を実施することが可能なアークを選定することにより、車両運用ネットワークに各車両検査を割り当てる。そして、巡回路探索部１２４が、全てのノードを一度だけ通過する巡回路であって、選定された全ての検査可能アークを含む巡回路を探索して、車両運用計画として出力する。【選択図】図３
2005259052.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤをもとに、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段、
前記各アークについて、少なくとも、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいてコストを設定するコスト設定手段、
前記各アークのうち、当該アークの元ノード及び先ノードの列車同士の接続の間合いに車両検査を行うアークを選定する検査アーク選定手段、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路であって前記検査アーク選定手段により選定されたアークを含む巡回路を探索する巡回路探索手段、
前記巡回路探索手段により探索された巡回路を基に車両運用計画を作成する作成手段、
として機能させるためのプログラム。
【請求項２】
前記巡回路探索手段が、
前記選定されたアークのうち、第ｉアーク（ｉは整数）の先ノードから第ｉ＋１アークの元ノードまでをつなぐアークのパスを決定する選定アーク間パス決定手段を有し、
前記ｉの値を０から順次変更して前記選定アーク間パス決定手段にパスを決定させていくことにより、前記選定されたアーク全てを含む巡回路を探索するように前記コンピュータを機能させるための請求項１に記載のプログラム。
【請求項３】
前記巡回路探索手段が、前記選定アーク間パス決定手段により決定されたパスで車両運用する場合の運用所要時間に基づいて、前記決定されたパスに含まれるアークの一つを切断し、切断したアークの元ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを再探索して、前記第ｉアークの先ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを更新するパス更新手段を有するように前記コンピュータを機能させるための請求項２に記載のプログラム。
【請求項４】
前記パス更新手段が、切断するアークとして、元ノードの列車と先ノードの列車とを日またぎで接続するアークを選択する切断アーク選択手段を有するように前記コンピュータを機能させるための請求項３に記載のプログラム。
【請求項５】
前記パス更新手段が、切断したアークの元ノードが表す列車と同日に運行可能なノードをつなぐパスであって、同日中での着時刻が所定の時刻条件となるノードをつなぐパスを含むように、前記切断したアークの元ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを再探索するように前記コンピュータを機能させるための請求項３又は４に記載のプログラム。
【請求項６】
前記巡回路探索手段による巡回路の探索が失敗した場合に、前記検査アーク選定手段に、車両検査を行うアークの選定数を増加させて再度選定させ、前記巡回路探索手段に巡回路の探索を再度実行させる制御を行う制御手段として前記コンピュータを更に機能させるための請求項１〜５の何れか一項に記載のプログラム。
【請求項７】
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤをもとに、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段と、
前記各アークについて、少なくとも、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいてコストを設定するコスト設定手段と、
前記各アークのうち、当該アークの元ノード及び先ノードの列車同士の接続の間合いに車両検査を行うアークを選定する検査アーク選定手段と、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路であって前記検査アーク選定手段により選定されたアークを含む巡回路を探索する巡回路探索手段と、
前記巡回路探索手段により探索された巡回路を基に車両運用計画を作成する作成手段と、
を備える車両運用計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両運用計画を作成するためのプログラム及び車両運用計画作成装置に関する。
【背景技術】
【０００２】
鉄道において、作成された運行スケジュール（列車ダイヤ）を実現するため、車両運用計画と呼ばれる計画を定めている。この車両運用計画は、車両の使用順序（列車の接続順序）や車両に対する保守管理を含む車両の運用に関する計画であり、様々な制約を考慮して作成される。
【０００３】
例えば、車両に対しては、メンテナンスのため、その走行時間や距離に応じた検査を実施することが義務付けられているが、特に、車両運用計画の作成時において、仕業検査、及び交番検査と呼ばれる車両検査を考慮しなければならない。各検査には、検査の周期（検査周期）及び検査の内容がそれぞれ規定されている。具体的には、仕業検査においては、目視による車両の点検が１時間程度で実施され、交番検査においては、例えば、ブレーキ装置や電気装置、走行装置といった車両の機能に関する検査が半日程度かけて実施される。また、各検査は、当該検査の際に必要な設備を備えて所定の駅等に設置された車両基地において、通常日中に実施される。尚、交番検査の検査内容は仕業検査の検査内容を満たしており、交番検査を実施すると同時に仕業検査も実施されたことになる。
【０００４】
このため、車両運用計画は、車両に対して仕業検査及び交番検査が、設定された検査周期を超過することなく実施されるように配慮して作成しなければならない。さらにこの際、検査の実施可能な場所、時間帯、所要時間等（以下、「実施条件」という。）を考慮して、各検査の実施位置を設定する必要がある。
【０００５】
また、この他にも、列車を接続する際の所定の接続条件や、旅客の輸送量の確保といった様々な制約を考慮する必要がある。
【０００６】
一方で、車両の運用は、鉄道運用に係るコストに影響するため、作成される車両運用計に対しては、コスト削減に関する要望があった。具体的には、例えば、交番検査及び仕業検査の回数が極力少なくなるように車両運用計画を作成し、車両を効率良く利用することが望ましい。
【０００７】
ところで、これらの制約を満足する車両運用計画を自動的に作成する技術が開発されており、本願出願人も、車両運用計画を、列車ダイヤを構成する全ての列車をサイクリックに接続するための１つの接続パターンとし、車両運用計画の作成を巡回セールスマン問題と捉え、上記した制約等に基づいて予め設定された評価基準に従った評価が最良である巡回路により表される車両運用計画案を採用することで、車両運用計画を自動的に作成する技術を開示している（特許文献１参照。）。
【特許文献１】特開２００３−１５４９３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記した特許文献１の技術を用いて車両運用計画を作成した場合、以下のような問題があった。すなわち、特許文献１では、交番検査の実施位置を予め割り当てておき、探索した巡回路を、仕業検査の検査周期及び実施条件を満足するように変更することで、各検査を割り当てた車両運用計画を作成しているが、もととなる列車ダイヤによっては、巡回路に対して仕業検査を上手く割り当てられない場合があり、適切な車両運用計画を得難いという問題があった。
【０００９】
そこで本発明は、車両に対して実施される検査がその検査周期及び実施条件を満足するように確実に割り当てられた車両運用計画であって、且つ車両を効率良く運用することができる車両運用計画を自動的に作成することを目的とする。
【課題を解決するための手段】
【００１０】
以上の課題を解決するための第１の発明は、コンピュータを、
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤをもとに、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段（例えば、図３に示す車両運用ネットワーク生成部１２２）、
前記各アークについて、少なくとも、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいてコストを設定するコスト設定手段（例えば、図３に示す車両運用ネットワーク生成部１２２）、
前記各アークのうち、当該アークの元ノード及び先ノードの列車同士の接続の間合いに車両検査を行うアークを選定する検査アーク選定手段（例えば、図３に示す車両運用計画作成部１２０）、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路であって前記検査アーク選定手段により選定されたアークを含む巡回路を探索する巡回路探索手段（例えば、図３に示す巡回路探索部１２４）、
前記巡回路探索手段により探索された巡回路をもとに車両運用計画を作成する作成手段（例えば、図３に示す車両運用計画作成部１２０）、
として機能させるためのプログラムである。
【００１１】
また、第７の発明の車両運用計画作成装置は、
複数の列車及び各列車の着発時刻のデータを有する列車ダイヤをもとに、前記列車ダイヤを構成する各列車を表すノード同士を、列車同士を接続することを表すアークにより結んだ車両運用ネットワークを生成する生成手段と、
前記各アークについて、少なくとも、当該アークの元ノードに対応する列車の着時刻、及び、当該アークの先ノードに対応する列車の発時刻に基づいてコストを設定するコスト設定手段と、
前記各アークのうち、当該アークの元ノード及び先ノードの列車同士の接続の間合いに車両検査を行うアークを選定する検査アーク選定手段と、
前記車両運用ネットワークのノードの内、所与のノードを初期点とし、アークを順次選択することによって全てのノードを１度だけ通過して初期点に戻る巡回路であって前記検査アーク選定手段により選定されたアークを含む巡回路を探索する巡回路探索手段と、
前記巡回路探索手段により探索された巡回路をもとに車両運用計画を作成する作成手段と、
を備えることを特徴としている。
【００１２】
この第１又は第７の発明によれば、列車ダイヤをもとに生成した車両運用ネットワークを構成するアークの中から、元ノード及び先ノードの列車同士の接続の間合いに車両検査を実施することが可能なアークを選定し、当該選定したアークを含む巡回路を探索して車両運用計画を作成することができる。これにより、車両に対して実施されなければならない車両検査を確実に割り当てた車両運用計画を作成することができる。また、車両検査の回数が極力少なくなるように列車同士の接続の間合いに車両検査が可能なアークを選定すれば、探索した巡回路をもとに作成される車両運用計画により、車両を効率良く運用することができる。
【００１３】
第２の発明は、第１の発明のプログラムであって、
前記巡回路探索手段が、
前記選定されたアークのうち、第ｉアーク（ｉは整数）の先ノードから第ｉ＋１アークの元ノードまでをつなぐアークのパスを決定する選定アーク間パス決定手段を有し、
前記ｉの値を０から順次変更して前記選定アーク間パス決定手段にパスを決定させていくことにより、前記選定されたアーク全てを含む巡回路を探索するように前記コンピュータを機能させるためのプログラムである。
【００１４】
この第２の発明によれば、選定されたアークの何れかである第ｉアークの先ノードから第ｉ＋１アークの元ノードまでをつなぐアークのパスを決定するとともに、ｉの値を０から順次変更して第ｉアークの先ノードから第ｉ＋１アークの元ノードまでをつなぐパスを決定していくことで、選定されたアークを全て含む巡回路を探索することができる。
【００１５】
第３の発明は、第２の発明のプログラムであって、
前記巡回路探索手段が、前記選定アーク間パス決定手段により決定されたパスで車両運用する場合の運用所要時間に基づいて、前記決定されたパスに含まれるアークの一つを切断し、切断したアークの元ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを再探索して、前記第ｉアークの先ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを更新するパス更新手段を有するように前記コンピュータを機能させるためのプログラムである。
【００１６】
この第３の発明によれば、決定されたパスで車両運用する場合の運用所要時間（例えば、日数であってもよい）に基づいて、当該パスに含まれるアークの一つを切断し、切断したアークの元ノードから第ｉ＋１アークの元ノードまでをつなぐアークのパスを再探索して、第ｉアークの先ノードから第ｉ＋１アークの元ノードまでをつなぐパスを更新することができる。これによれば、第ｉアークの先ノードから第ｉ＋１アークの元ノードまでのパスで車両運用する場合の運用所要時間が車両検査の検査周期を満たすように、当該パスを更新することができる。
【００１７】
第４の発明は、第３の発明のプログラムであって、
前記パス更新手段が、切断するアークとして、元ノードの列車と先ノードの列車とを日またぎで接続するアークを選択する切断アーク選択手段を有するように前記コンピュータを機能させるためのプログラムである。
【００１８】
この第４の発明によれば、第ｉアークの先ノードから第ｉ＋１アークの元ノードまでをつなぐパスを構成するアークの中に、列車同士の接続に日またがりが生じているアークが含まれる場合に、当該アークを切断することにより、第ｉアークの先ノードから第ｉ＋１アークの元ノードまでのパスで車両運用する場合の運用所要時間が車両検査の検査周期を満たすように、当該パスを更新することができる。
【００１９】
第５の発明は、第３又は第４の発明のプログラムであって、
前記パス更新手段が、切断したアークの元ノードが表す列車と同日に運行可能なノードをつなぐパスであって、同日中での着時刻が所定の時刻条件となるノードをつなぐパスを含むように、前記切断したアークの元ノードから前記第ｉ＋１アークの元ノードまでをつなぐパスを再探索するように前記コンピュータを機能させるためのプログラムである。
【００２０】
この第５の発明によれば、切断したアークの元ノードから第ｉ＋１アークの元ノードまでをつなぐアークのパスを再探索する際に、切断したアークの元ノードが表す列車と同日に運行可能なノードをつなぐパスであって、同日中での着時刻が所定の時刻条件となるノードをつなぐパスを含むようなパスを再探索することができる。これによれば、第ｉアークの先ノードから第ｉ＋１アークの元ノードまでのパスで車両運用することにより、当該車両により同日中に運用される列車が極力多くなるように車両運用計画を作成することができる。したがって、車両を効率良く利用することが可能な車両運用計画を作成することができる。
【００２１】
第６の発明は、第１〜第５の何れかの発明のプログラムであって、
前記巡回路探索手段による巡回路の探索が失敗した場合に、前記検査アーク選定手段に、車両検査を行うアークの選定数を増加させて再度選定させ、前記巡回路探索手段に巡回路の探索を再度実行させる制御を行う制御手段（例えば、図３に示す車両運用計画作成部１２０）として前記コンピュータを更に機能させるためのプログラムである。
【００２２】
この第６の発明によれば、巡回路の探索が失敗した場合には、車両検査を行うアークの選定数を増加させて再度選定し、巡回路の探索を再度実行させる制御を実施することができる。これにより、車両運用ネットワークのノードの内、所与のノードを初期点として全てのノードを１度だけ通過して初期点に戻る巡回路であって、選定されたアークを含む巡回路を確実に探索することができる。
【発明の効果】
【００２３】
本発明によれば、列車ダイヤをもとに生成した車両運用ネットワークを構成するアークの中から、元ノード及び先ノードの列車同士の接続の間合いに車両検査を実施することが可能なアークを選定し、当該選定したアークを含む巡回路を探索して車両運用計画を作成することができる。これにより、車両に対して実施されなければならない車両検査を確実に割り当てた車両運用計画を自動的に作成することができる。また、車両検査の回数が極力少なくなるように列車同士の接続の間合いに車両検査が可能なアークを選定すれば、探索した巡回路をもとに作成される車両運用計画により、車両を効率良く運用することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図を参照して、本発明に係る車両運用計画作成装置の実施の形態について詳細に説明する。尚、以下では、１台のパーソナル・コンピュータ（以下、パソコンという。）で車両運用計画作成装置を構成することとして説明するが、これに限定されるものではない。また、「ノードをつなぐ」「ノードを連結する」「マークを付す」といった平易な表現を用いて説明するが、これらの表現は、情報処理の内容を比喩した表現であり、コンピュータの演算処理がその実態である。
【００２５】
［概要］
車両運用計画は、上記したように、車両の使用順序や車両に対する保守管理を含む車両の運用に関する計画を定めたものであり、ダイヤ改正の際等において計画される列車ダイヤに基づいて作成される。
【００２６】
図１（ａ）に、列車ダイヤの一例を示す。図１（ａ）において、横軸を時刻、縦軸を駅ＡＡ、ＢＢ、ＣＣとして、列車の運行を表す「列車スジ」により列車ダイヤが表現されている。また、各「列車スジ」には、対応する列車番号がそれぞれ表記されている。車両運用計画においては、この列車ダイヤを実現するために、当該列車ダイヤを構成する全ての列車に対して車両を割り当てて、車両の運用スケジュールを作成する。
【００２７】
図１（ｂ）に、図１（ａ）に示した列車ダイヤに基づいて作成された車両運用計画の一例を示す。図１（ｂ）において、横軸方向を時刻とした行路１、行路２、行路３で示す３本の行路が示されている。ここで、行路とは、ある車両の１日分の運用計画のことであり、ある１日における当該車両の運用が「横棒」により表現されている。尚、図１（ｂ）中に示す“仕”は、上記した仕業検査を実施することを示す。
【００２８】
例えば、行路１は、車両が、ＣＣ駅からＢＢ駅まで列車２として運転され、次いで、ＢＢ駅において仕業検査が実施された後、ＣＣ駅まで列車１として運転され、ＣＣ駅で折り返して列車７としてＢＢ駅まで運転されることを意味する。また、各行路を構成する「横棒」は、図１（ａ）に示す何れかの「列車スジ」に対応しており、図１（ｂ）に示す車両運用計画においては、３本の車両をそれぞれ行路１〜行路３に従って運転することにより、図１（ａ）に示す列車ダイヤを実現している。
【００２９】
さらに、図１（ｂ）に示す３本の行路は、ローテーションを組んで運用されるようになっている。すなわち、行路１に割り当てられて上記したように運転された車両は、当該運転日の翌日には行路２、翌々日には行路３に従って運転され、行路１に戻るというように、３日サイクルで運用される。すなわち、車両運用計画は、列車ダイヤを構成する全ての列車をサイクリックに接続した接続パターンを、日毎に区切ることにより作成した行路の集合（交番）である。
【００３０】
この車両運用計画は、上記したように、交番検査及び仕業検査（車両検査）に関する制約や列車を接続する際の制約を満足するよう、また、コスト削減に関する要望に沿うように作成される。例えば、以下のような制約・要望がある。
【００３１】
（１）検査の実施条件に関する制約
交番において、上記したように、交番検査及び仕業検査の実施位置を、その検査周期や実施条件を満たすように設定しなければならない。
【００３２】
（２）列車を接続する際の制約
先ず、接続する前後の列車において、前列車の終着駅と後列車の始発駅は同一駅である必要がある。例えば、Ｘ列車の終着駅とＹ列車の始発駅が同一駅でなければ、当該列車同士を接続することは不可能である。車両運用計画を作成する際には、この制約を満たすために、適宜回送列車を設定する。また、この際、接続する駅において、乗客・乗務員の乗り降りや清掃等を含む最小限の停止時間を確保するため、前列車の着時刻と後列車の発時刻との間に所定の時間間隔をあける必要がある。
【００３３】
また、翌日に運転される列車と接続する場合を除いて、前列車の着時刻と後列車の発時刻が逆転してはならない。例えば、Ｘ列車の終着駅着時刻よりＹ列車の始発駅発時刻が先行している場合、Ｘ列車とＹ列車を接続することは不可能である。
【００３４】
そして、交番において、連続する２つの行路の終了駅と開始駅は、同一でなければならない。これは、１番目の行路を終了駅で終了した車両は、その翌日に２番目の行路の開始駅から運転を開始するためであり、車両運用計画を作成する際には、この制約を満たすために、適宜回送列車を設定する。
【００３５】
（３）コスト削減に関する要望
車両を効率良く利用することが可能な車両運用計画が望ましい。このため、例えば、交番検査及び仕業検査の回数を極力少なくしたいという要望、各車両により１日に運用される列車ができるだけ多くなるようにして、１日の列車ダイヤを実現するために使用される車両の数（すなわち、行路の数）を極力少なくしたいという要望、回送列車の本数や回数列車の走行距離を極力少なくしたいという要望がある。
【００３６】
本実施形態は、車両運用計画を、列車ダイヤを構成する全ての列車をサイクリックに接続するための１つの接続パターン（巡回路）とし、上記した制約や要望を満足する最良の巡回路により表される車両運用計画案を採用することで、車両運用計画を自動的に作成するものである。
【００３７】
具体的には、列車ダイヤを構成する列車同士の接続パターンを、各列車を表すノードを列車同士の接続を表すアークにより連結したネットワーク（以下、「車両運用ネットワーク」という。）により表現し、この車両運用ネットワークにおいて、全てのノードを一度だけ通過して初期点に戻る巡回路を探索して候補解を生成する。そして、巡回路を探索する処理を繰り返してより良い巡回路（最良解）を探索し、候補解の生成処理を指定回数繰り返して行った時点での最良解の示す巡回路で表される列車の接続を車両運用計画とする。
【００３８】
図２（ａ）に、車両運用ネットワークの一例を示す。図２（ａ）に示すように、車両運用ネットワークは、列車ダイヤを構成する各列車（図２（ａ）では列車１〜列車７）を表す各ノードと、接続可能な列車同士の接続を表す有向アークとから構成されている。例えば、列車７を表すノードＮ１０と、列車６を表すノードＮ１２とを連結するアークの内、ノードＮ１０からノードＮ１２へのアークＡ１０は、車両が列車７として運転された後、列車６として運転されることを表している。尚、列車同士が接続可能であるか否かは以下のように判断される。例えば、接続する駅において最小限確保しなければならない停止時間といった、列車の接続に必要な時間が不足している場合には、当該列車同士は接続不可能と判断される。また、番線数等による制約によって、当該駅において同時に滞留することが可能な車両の数が予め決まっており、当該駅において可能な列車間の接続候補が限定されている場合には、当該駅における接続候補以外の列車の接続は不可能と判断される。
【００３９】
詳細には、各ノード間は、車両運用計画を作成する際の制約として説明した列車を接続する際の制約（２）に基づいて、以下の（ａ）〜（ｄ）に示す４種類のアークのうちの何れかにより連結される。
【００４０】
（ａ）当日接続アーク
当日中に接続可能な列車を表すノード間は、当日接続アークにより連結される。図２（ａ）では、この当日接続アークを太線の実線矢印により示している。例えば、図２（ａ）において、ノードＮ１４からノードＮ１６への当日接続アークＡ１２は、車両が列車２として運転された後、当日中に列車１として運転されることを表している。
【００４１】
（ｂ）翌日接続アーク
翌日に接続可能な列車を表すノード間は、翌日接続アークにより連結される。図２（ａ）では、この翌日接続アークを細線の実線矢印により示している。例えば、図２（ａ）において、ノードＮ１６からノードＮ１４への翌日接続アークＡ１４は、車両が列車１として運転された後、翌日に列車２として運転されることを表している。
【００４２】
（ｃ）回送付当日接続アーク
列車間の着発駅が異なる場合であって、回送列車として運転されることで当日中に接続可能な列車を表すノード間は、回送付当日接続アークにより接続される。図２（ａ）では、この回送付当日接続アークを太線の点線矢印により示している。例えば、図２（ａ）において、ノードＮ１８からノードＮ１２への回送付当日接続アークＡ１６は、車両が列車４として運転された後、当日中に列車４の終着駅から列車６の始発駅まで回送列車として運転されて列車６として運転されることを表している。
【００４３】
（ｄ）回送付翌日接続アーク
列車間の着発駅が異なる場合であって、回送列車として運転されることで翌日に接続可能な列車を表すノード間は、この回送付翌日接続アークにより接続される。図２（ａ）では、この回送付翌日接続アークを細線の点線矢印により示している。例えば、図２（ａ）において、ノードＮ１２からノードＮ１９への回送付翌日接続アークＡ１８は、車両が列車６として運転された後、当日中或いは翌日に列車６の終着駅から列車４の始発駅まで回送列車として運転され、翌日に列車４として運転されることを表している。
【００４４】
また、各ノードには、該当する列車が始発駅を出発してから終着駅に到着するまでの時間（総運転時分）がコストとしてそれぞれ設定され、各アークには、元ノードにより表される列車の終着時刻と、先ノードにより表される列車の始発時刻との時間間隔（以下、「着発時間間隔」という。）がコストとしてそれぞれ設定される。
【００４５】
さらに、この車両運用ネットワークを構成するアークのうち、車両検査の実施条件を満足するアークに対して、各検査が実施可能なことを表すマークが付される。詳細には、当該アークが、先ノードにより表される列車の始発駅が車両基地を備えた駅であるアーク、或いは元ノードにより表される列車の終着駅が車両基地を備えた駅であるアークであること、先ノードにより表される列車の始発時刻或いは元ノードにより表される列車の終着時刻とをもとに、車両検査が実施可能な時間帯に関する実施条件を満足すると判断されたアークであること、さらには、設定されるコスト（着発時間間隔）が車両検査の所要時間に関する実施条件を満足するアークであることを条件に、各検査が実施可能であることを表すマークが付される。
【００４６】
例えば、図２（ａ）において、回送付翌日接続アークＡ１８には交番検査可能マークＭ１０が付されており、車両に対して列車６と列車５との接続の間合いに交番検査及び仕業検査が実施可能であることを示している。また、図２（ａ）において、当日接続アークＡ１２には仕業検査可能マークＭ１２が付されており、車両に対して列車２と列車１との接続の間合いに仕業検査が実施可能であることを示している。以下、交番検査可能マークが付されたアークを「交番検査可能アーク」、仕業検査可能マークが付されたアークを「仕業検査可能アーク」といい、これらを包括して適宜「検査可能アーク」という。
【００４７】
図２（ｂ）は、（ａ）に示す車両運用ネットワークをもとに探索された巡回路の一例を示す図である。詳細は後述するが、本実施形態では、検査周期を満足するために最低限必要な検査回数が想定され、この検査回数に基づく数の検査可能アークが最初に選定される。そして、全てのノードを一度だけ通過する巡回路であって、選定された全ての検査可能アークを含む巡回路が探索されて、車両運用計画として出力される。
【００４８】
また、巡回路の探索に失敗した場合には、前述の検査回数を増加させて検査可能アークを選定し、巡回路を再度探索する。図２（ｂ）では、検査周期を満足するために必要な仕業検査の回数を１回と想定した場合の巡回路の一例を示しており、同図において、選定された検査可能アーク（交番検査可能アーク）である回送付翌日接続アークＡ１８を含む巡回路を示している。尚、この巡回路は、図１（ｂ）に示す車両運用計画に相当するものである。
【００４９】
［機能構成］
次に、車両運用計画作成装置１０の機能構成について説明する。図３は、車両運用計画作成装置１０の機能構成の一例を示すブロック図である。図３に示すように、車両運用計画作成装置１０は、ＣＰＵ１００、ＲＯＭ２００、入力装置３００、表示装置４００、通信装置５００、ＲＡＭ６００、記憶装置７００、記憶媒体８００により構成され、記憶媒体８００以外の各部はバス９００により接続されている。
【００５０】
ＣＰＵ１００は、入力される指示に応じて所定のプログラムに基づいた処理を実行して各機能部への指示やデータの転送等を行い、車両運用計画作成装置１０を統括的に制御する。具体的には、ＣＰＵ１００は、入力装置３００を介して入力される操作信号等に応じて、ＲＯＭ２００や記憶装置７００が備える記憶媒体８００内に格納された各種プログラムを読み出してＲＡＭ６００に展開し、当該プログラムに従って処理を実行する。そして、この処理結果をＲＡＭ６００に格納するとともに、当該処理結果を表示するための表示信号を表示装置４００に出力する。さらに、ＲＡＭ６００内に格納した処理結果の一部或いは全てを、記憶媒体８００へ保存する。
【００５１】
このＣＰＵ１００により種々の機能が実現されるが、特に、車両運用計画を作成する機能部を車両運用計画作成部１２０と呼び、この車両運用計画作成部１２０において、車両運用ネットワークを生成する機能部を車両運用ネットワーク生成部１２２、巡回路を探索する機能部を巡回路探索部１２４と呼び、以下説明する。
【００５２】
車両運用計画作成部１２０は、後述する車両運用ネットワーク生成部１２２に車両運用ネットワーク生成処理を実行させ、生成した車両運用ネットワークを構成する検査可能アークに対して、その検査周期に従って車両検査を割り当てる。尚、本実施形態では、仕業検査の検査周期の上限を３日とし、交番検査を１回実施することによりその検査周期が満足されることとする。そして、車両運用計画作成部１２０は、巡回路探索部１２４に巡回路探索処理を所定回数繰り返し実行させる制御を行い、巡回路探索部１２４により探索された巡回路の内、評価値が最良となる巡回路を車両運用計画として出力する。
【００５３】
車両運用ネットワーク生成部１２２は、記憶媒体８００に格納される列車ダイヤデータ８２０に基づいて、図２に示して説明した車両運用ネットワークを生成する。
【００５４】
具体的には、車両運用ネットワーク生成部１２２は、先ず、列車ダイヤを構成する各列車を表す各ノードのコストとして総運転時分をそれぞれ設定する。また、車両運用ネットワーク生成部１２２は、接続可能な列車を表すノード間を連結するアークの種類（アーク種別）を設定するとともに、各アークのコストとして発着時間間隔をそれぞれ設定する。
【００５５】
次に、車両運用ネットワーク生成部１２２は、先ノードにより表される列車の始発駅が車両基地を備えた駅であるアーク、或いは元ノードにより表される列車の終着駅が車両基地を備えた駅であるアークであって、前述のようにコストとして設定される着発時間間隔により元ノード及び先ノードの列車同士の接続の間合いに車両検査が可能と判断されたアークのリスト（検査可能アークリスト）を作成する。詳細には、車両運用ネットワーク生成部１２２は、交番検査が実施可能なアークのリストと、仕業検査が実施可能なアークのリストをそれぞれ作成する。
【００５６】
そして、車両運用ネットワーク生成部１２２は、各ノードを設定されたアーク種別のアークにより連結するとともに、検査可能アークリストに従って、該当するアークに車両検査が実施可能であることを示すマーク（交番検査可能マーク或いは仕業検査可能マーク）を付して、車両運用ネットワークを生成する。
【００５７】
巡回路探索部１２４は、車両運用ネットワーク生成部１２２により生成された車両運用ネットワークの巡回路を探索する。具体的には、巡回路探索部１２４は、車両運用ネットワークを構成する全てのノードを一度だけ通過する巡回路であって、車両検査をするとして割り当てられた全ての検査可能アークを含む巡回路を探索する。
【００５８】
ＲＯＭ２００には、各種初期設定、ハードウェアの構成、又は必要なプログラムのロード等を行うための初期プログラムが格納される。
【００５９】
入力装置３００は、カーソルキー、テンキー、各種ファンクションキー等を備えたキーボード、及びマウス等のポインティングデバイス等により実現されるものであり、これらが操作された場合には、その操作に応じた操作信号をＣＰＵ１００に出力する。
【００６０】
表示装置４００は、例えば、ＬＣＤ（Liquid Crystal Display）やＥＬＤ（Electronic Luminescent Display）等の表示装置であり、ＣＰＵ１００から入力される表示信号に基づく各種画面を表示する。
【００６１】
通信装置５００は、装置内部で利用される情報を通信回線を介して外部とやりとりするための装置であり、他の装置との通信を行うための制御を行う。
【００６２】
ＲＡＭ６００は、ＣＰＵ１００の作業用メモリとして用いられる半導体メモリであり、ＣＰＵ１００が実行するプログラムや、これらプログラムの実行に係るデータ等を一時的に保持するメモリ領域を備える。特に、本実施形態を実現するため、巡回路の候補解とその評価値を保持する候補解格納領域６２０と、巡回路の最良解とその評価値を保持する最良解格納領域６４０と、車両運用ネットワークのデータを保持する車両運用ネットワークデータ格納領域６６０とを備え、車両運用ネットワークデータ格納領域６６０には、特に、コストデータ６６２及び検査可能アークリスト６６４が格納される。
【００６３】
コストデータ６６２には、上記したように車両運用ネットワーク生成部１２２により各アーク及び各ノードにそれぞれ設定されるコストが格納される。図４は、コストデータ６６２の一例を示す図である。図４に示すように、コストデータ６６２には、ノードコストデータ６６２ａ及びアークコストデータ６６２ｂが格納される。ノードコストデータ６６２ａには、各列車を表すノードを示すノード番号と対応付けて、それぞれコストが設定される。そして、アークコストデータ６６２ｂには、接続可能な列車同士の接続を表すアークを示すアーク番号と対応付けて、アーク種別と、コストとがそれぞれ設定される。
【００６４】
検査可能アークリスト６６４には、上記したように車両運用ネットワーク生成部１２２により生成される検査可能アークリストが格納される。図５は、検査可能アークリスト６６４の一例を示す図である。図５に示すように、検査可能アークリスト６６４には、交番検査可能アークリスト６６４ａ及び仕業検査可能アークリスト６６４ｂが格納される。交番検査可能アークリスト６６４ａには、接続の間合いに交番検査が実施可能な列車同士の接続を表すアークのアーク番号の一覧が格納される。そして、仕業検査可能アークリスト６６４ｂには、接続の間合いに仕業検査が実施可能な列車同士の接続を表すアークのアーク番号の一覧が格納される。
【００６５】
記憶装置７００は、磁気的、光学的記憶媒体、或いは半導体メモリ等で構成される記憶媒体８００を備える。この記憶媒体８００は、記憶装置７００に固定的に設けたもの、或いは着脱自在に装着するものであり、各種処理プログラムや、これらの処理プログラムにより処理されたデータ等が記憶される。特に、本実施形態を実現するため、列車ダイヤデータ８２０と、車両運用計画データ８４０と、車両運用計画作成プログラム８６０とが格納される。
【００６６】
列車ダイヤデータ８２０には、列車ダイヤを構成する各列車の列車情報が蓄積される。この列車情報には、例えば、当該列車の列車番号や列車種別、当該列車が着発する各駅における着発時刻といった情報が含まれる。また、車両運用計画データ８４０には、本車両運用計画作成装置１０により作成・確定された巡回路の最良解が車両運用計画データとして格納される。
【００６７】
車両運用計画作成プログラム８６０は、ＣＰＵ１００を車両運用計画作成部１２０として機能させるためのプログラムであり、この車両運用計画作成プログラム８６０は、車両運用計画作成部１２０を車両運用ネットワーク生成部１２２として機能させるためのプログラムである車両運用ネットワーク生成プログラム８６２と、車両運用計画作成部１２０を巡回路探索部１２４として機能させるためのプログラムである巡回路探索プログラム８６４とを含む。
【００６８】
［処理の流れ］
次に、本実施形態における車両運用計画作成処理の流れについて説明する。図６は、車両運用計画作成処理の実行に係る車両運用計画作成部１２０の処理フローの一例を示す図である。この車両運用計画作成処理は、車両運用計画作成部１２０が車両運用計画作成プログラム８６０を読み出して実行することにより実現される。
【００６９】
先ず、車両運用計画作成部１２０は、例えば、候補解の生成回数（後述するループＡのループ回数）や最良解及びその評価値が格納される最良解格納領域６４０の初期化といった、初期設定処理を実行する（ステップＳ１０）。
【００７０】
続いて、車両運用ネットワーク生成部１２２が、車両運用ネットワーク生成処理を実行する（ステップＳ１５）。図７は、車両運用ネットワーク生成処理の実行に係る車両運用ネットワーク生成部１２２の処理フローの一例を示す図である。この車両運用ネットワーク生成処理は、車両運用ネットワーク生成部１２２が車両運用ネットワーク生成プログラム８６２を読み出して実行することにより実現される。
【００７１】
車両運用ネットワーク生成部１２２は、先ず、列車ダイヤを構成する各列車同士が接続可能であるか否かを判断し、当該列車ダイヤを構成する全てのノードと、接続可能な列車を表すノード間を連結するアークについて、コストデータ６６２を作成する（ステップＳ１５２）。
【００７２】
具体的には、車両運用ネットワーク生成部１２２は、列車ダイヤデータ８２０をもとに、各列車を表すノードのコストとして総運転時分をそれぞれ設定して、ノードコストデータ６６２ａとしてコストデータ６６２に格納する。
【００７３】
また、車両運用ネットワーク生成部１２２は、各アークの種類（アーク種別）を設定する。具体的には、車両運用ネットワーク生成部１２２は、当日中に接続可能な列車を表すノード間のアーク種別に当日接続アークを設定し、翌日に接続可能な列車を表すノード間のアーク種別に翌日接続アークを設定する。また、車両運用ネットワーク生成部１２２は、列車間の着発駅が異なる場合、回送列車として運転されることで当日中に接続可能な列車を表すノード間のアーク種別に回送付当日接続アークを設定し、回送列車として運転されることで翌日に接続可能な列車を表すノード間のアーク種別に回送付翌日接続アークを設定する。そして、車両運用ネットワーク生成部１２２は、以上のように設定された各アークのコストとして発着時間間隔をそれぞれ設定して、設定したアーク種別とともにアークコストデータ６６２ｂとしてコストデータ６６２に格納する。
【００７４】
次に、車両運用ネットワーク生成部１２２は、車両検査の実施条件を満足する検査可能アークリスト６６４を作成する（ステップＳ１５４）。
【００７５】
具体的には、車両運用ネットワーク生成部１２２は、列車ダイヤデータ８２０をもとに、先ノードにより表される列車の始発駅が車両基地を備えた駅であるアーク、或いは元ノードにより表される列車の終着駅が車両基地を備えた駅であるアークを抽出する。
【００７６】
そして、車両運用ネットワーク生成部１２２は、抽出したアークの中から、先ノードにより表される列車の始発時刻或いは元ノードにより表される列車の終着時刻とをもとに、交番検査が実施可能な時間帯に関する実施条件を満足すると判断されたアークであって、前述のようにコストとして設定される着発時間間隔により元ノード及び先ノードの列車同士の接続の間合いに交番検査が可能なアークを抽出し、交番検査可能アークリスト６６４ａとして検査可能アークリスト６６４に格納するとともに、同様にして、仕業検査が可能なアークを抽出し、仕業検査可能アークリスト６６４ｂとして検査可能アークリスト６６４に格納する。
【００７７】
そして、車両運用ネットワーク生成部１２２は、車両運用ネットワークデータ格納領域６６０を参照して、車両運用ネットワークを生成する（ステップＳ１５６）。この際、車両運用ネットワーク生成部１２２は、コストデータ６６２に格納されるアークコストデータをもとに、接続可能なノード間を該当するアーク種別のアークにより連結する。さらにこの際、車両運用ネットワーク生成部１２２は、検査可能アークリスト６６４に格納される交番検査可能アークリスト６６４ａをもとに、該当するアークに交番検査可能マークを付すとともに、仕業検査可能アークリスト６６４ｂをもとに、該当するアークに仕業検査可能マークを付す。
【００７８】
図６に戻り、車両運用ネットワーク生成部１２２により実行される車両運用ネットワーク生成処理を終了すると、車両運用計画作成部１２０は、列車ダイヤデータ８２０を参照して、列車ダイヤを実現するために最低限必要な車両数（必要最低車両数）を取得し、この必要最低車両数に基づいて検査周期を満足するために最低限必要な仕業検査の回数を想定し、この回数から１を減算した値を仕業検査想定回数として仮決めする（ステップＳ２０）。尚、必要最低車両数として、列車ダイヤにおいて同一の時間帯に運用される列車の最大数を取得する。
【００７９】
次に、車両運用計画作成部１２０は、生成した車両運用ネットワークに対して、実施順序に“０”を割り振って交番検査を割り当てる（ステップＳ２５）。具体的には、車両運用計画作成部１２０は、検査可能アークリスト６６４を参照し、交番検査可能アークリスト６６４ａから、アーク番号を例えば乱数を発生させてランダムに一つ選定し、該当するアークにより表される列車同士の接続の間合いに交番検査を実施することとして、実施順序に“０”を割り振る。
【００８０】
続いて、車両運用計画作成部１２０は、ループＡの処理を所定回数実行する（ステップＳ３０〜ステップＳ５５）。
【００８１】
ループＡでは、車両運用計画作成部１２０は、先ず、生成した車両運用ネットワークに対して、実施順序として“１”以降の番号を割り振って仕業検査を割り当てる（ステップＳ３５）。具体的には、車両運用計画作成部１２０は、検査可能アークリスト６６４を参照し、仕業検査可能アークリスト６６４ｂから、仕業検査想定回数個のアーク番号を例えばランダムに選定し、該当するアークにより表される列車同士の接続の間合いに仕業検査を実施することとして、選定した順に“１”以降の番号を割り振る。尚、仕業検査を割り当てる際に選定されるアーク番号は、交番検査の実施位置として選定されたアーク番号と重複しないように選定する必要があり、車両運用計画作成部１２０は、ステップＳ２５で選定されたアーク番号と重複するアーク番号が選定された場合には、再度アーク番号を選定する。また、最終的に全てのノードを一度だけ通過して初期点に戻る巡回路を探索するため、ステップＳ２５及びステップＳ３５で選定される各検査可能アークの元ノード及び先ノードがそれぞれ重複しないように各アーク番号を選定する必要がある。したがって、車両運用計画作成部１２０は、選定された検査可能アークの元ノード或いは先ノードが、既に選定された検査可能アークの元ノード或いは先ノードの何れかと重複する場合にも、再度アーク番号を選定する。
【００８２】
続いて、巡回路探索部１２４は、巡回路探索処理を実行する（ステップＳ４０）。図８は、巡回路探索処理の実行に係る巡回路探索部１２４の処理フローの一例を示す図である。この巡回路探索処理は、巡回路探索部１２４が巡回路探索プログラム８６４を読み出して実行することにより実現される。
【００８３】
巡回路探索部１２４は、先ず、対象実施番号ｋに“０”を代入して初期化する（ステップＳ４００）。また、この際、巡回路を探索する際の作業用に用いられる確定パスＰ０が初期化される。
【００８４】
続いて、巡回路探索部１２４は、対象実施番号ｋをもとに起点ノードＳ及び終点ノードＥを設定して、選定アーク間を決定する（ステップＳ４１０）。具体的には、巡回路探索部１２４は、対象実施番号ｋの値が実施番号として割り振られた検査可能アークの先ノードを起点ノードＳとし、ｋ＋１の値が実施番号として割り振られた検査可能アークの元ノードを終点ノードＥとして、起点ノードＳと終点ノードＥ間を選定アーク間に決定する。
【００８５】
例えば、対象実施番号ｋに初期値“０”が設定されている場合には、選定アーク間は、実施番号に“０”が割り振られた検査可能アーク（交番検査可能アーク）の先ノードである起点ノードＳと、実施番号に“１”が割り振られた検査可能アーク（仕業検査可能アーク）の元ノードである終点ノードＥとの間に設定される。尚、対象実施番号ｋが仕業検査想定回数と一致する場合には、選定アーク間は、実施番号に“ｋ”が割り振られた検査可能アークの先ノードである起点ノードＳと、“０”が割り振られた検査可能アーク（交番検査可能アーク）の元ノードである終点ノードＥとの間に設定される。
【００８６】
続いて、巡回路探索部１２４は、コストデータ６６２を参照して、起点ノードＳから終点ノードＥへの最短路（アークでつないだパス全体のコストが最低となるパス）を探索する（ステップＳ４２０）。本実施形態では、この最短路は、例えば、最短経路問題を解く公知のアルゴリズムであるダイクストラ法と呼ばれる技術を用いて探索される。尚、この起点ノードＳから終点ノードＥへのパスの探索方法は、ダイクストラ法に限定されるものではない。例えば、貪欲法と呼ばれる技術を用いて、元ノードと連結されるアークの内、最もコストの小さいアークを選択することにより先ノードを順次選択していき、起点ノードＳから終点ノードＥへのパスを探索することとしてもよい。また、この際、確定パスＰ０に探索された最短路が追加されてできたパスが、候補解として候補解格納領域６２０に保持される。
【００８７】
図９は、このステップＳ４２０の処理により探索された最短路の一例を示す図である。尚、図９において、生成された車両運用ネットワークを構成するノードの一部を示している。この図９に示す最短路は、例えば、車両運用ネットワークを構成する検査可能アークから任意に選定されて車両検査が割り当てられた交番検査可能アークＡ１００の先ノードである起点ノードＮ１００、及び仕業検査可能アークＡ１１０の元ノードである終点ノードＮ１１０との間を対象選定アーク間とした場合に探索された、起点ノードＳから終点ノードＥまでの最短路を示している。
【００８８】
続いて、巡回路探索部１２４は、対象選定アーク間のパスに含まれるアークのうち、日またぎが生じているアーク、すなわち翌日接続アーク或いは回送付翌日接続アークの数を計数する（ステップＳ４３０）。そして、巡回路探索部１２４は、計数されたアーク数が仕業検査周期（３日）と一致するか否かを判定し、一致しない場合には（ステップＳ４４０：ＮＯ）、パス追加処理に移行する（ステップＳ４５０）。
【００８９】
図１０は、パス追加処理の一例を示すフローチャートである。図１０に示すように、巡回路探索部１２４は、先ず、日またぎが生じているアークのうち、起点ノードＳに最も近いアークを切断する（ステップＳ４５２）。続いて、巡回路探索部１２４は、未到達のノード（パスとして選択されていないノード）の中から、切断されたアークの元ノードの表す列車と当日に接続することが可能で、且つ着時刻が最も遅い時刻であるノードに到達するアークを順次選択して追加パスを生成する（ステップＳ４５４）。また、この際、追加パスが確定パスに追加されて、確定パスＰ０が更新される。尚、巡回路探索部１２４は、切断されたアークの元ノードの表す列車と当日に接続することが可能で、且つ着時刻が最も遅い時刻である未到達のノードが終点ノードＥの場合には、二番目に着時刻が遅いノードに到達するアークを順次選択して追加パスを生成する。そして、巡回路探索部１２４は、起点ノードＳを、追加パスが到達する最先のノードに更新する（ステップＳ４５６）。
【００９０】
尚、パス追加処理では、ステップＳ４５２において、日またぎが生じているアークのうちの起点ノードＳに最も近いアークを切断することとしたが、他の方法を用いてもよい。すなわち、例えば、対象選定アーク間のパスに日またぎのアークが複数含まれる場合に、切断する日またぎのアークを乱数を用いてランダムに決定することとしてもよい。また、対象選定アーク間のパスに含まれる日またぎのアーク毎に、それぞれ当該日またぎのアークを切断したと仮定して追加パスを生成し、追加パスに含まれるアーク数やノード数に基づいて切断する日またぎのアークを決定することとしてもよい。例えば、切断することでアーク数或いはノード数が最も多く含まれる追加パスが生成されると判断された日またぎのアークを切断するアークに決定することとしてもよい。
【００９１】
図１１は、対象選定アーク間のパスの生成過程を説明するための図であり、図９に示す対象選定アーク間のパスを修正する様子を示している。図１１（ａ）において、対象選定アーク間のパスを構成するアークの中から、日またぎが生じているアークであって、起点ノードＳに最も近いアーク（細線の実線で示す翌日接続アークＡ２００）が切断されている。この切断された翌日接続アークＡ２００の元ノードＮ２００と連結される未到達のノードのうち、同日中に運転される列車であって着時刻が最も遅くなるノードに到達するためのアークが順次選択されて追加パスが生成される。
【００９２】
例えば、図１１（ｂ）では、ノードＮ２００からノードＮ３００へのパスが追加パスとして生成されており、ノードＮ３００が起点ノードＳに変更されている。
【００９３】
図８に戻り、巡回路探索部１２４は、ステップＳ４５０のパス追加処理を終了すると、ステップＳ４２０に移行して、ステップＳ４４０において日またぎが生じているアーク数が仕業検査周期と一致すると判断されるまで、上記した処理を繰り返す。
【００９４】
図１１（ｃ）は、（ｂ）に示して説明したように変更された起点ノードＳから、終点ノードＥへの最短路が探索されることにより修正された対象選定アーク間のパスの一例を示す図である。尚、このパスに含まれる、日またぎが生じているアークは二本（翌日接続アークＡ４００及びＡ４１０）であり、仕業検査の検査周期（３日）と一致しないため、起点ノードＳから最も近い日またぎのアーク（翌日接続アークＡ４００）を切断して、上記した処理が再度実行される。また、対象選定アーク間のパスを構成する日またぎのアーク数が仕業検査の検査周期と一致すると、当該対象選定アーク間のパスが確定される。そして、車両検査が割り当てられた検査可能アークの実施順序に従って対象選定アーク間が変更されて、順次対象選定アーク間のパスが決定されていく。すなわち、これにより、予め車両検査を割り当てた検査可能アーク間である対象選定アーク間のパスを、車両がその検査周期内でできるだけ多くの列車を運行するように修正することができる。
【００９５】
そして、図８に示すステップＳ４４０において、日またぎが生じているアーク数が仕業検査周期と一致すると判断された場合には、続いて、巡回路探索部１２４は、対象実施番号ｋが仕業検査想定回数と一致するか否かを判定して、一致しない場合には（ステップＳ４６０：ＮＯ）、対象実施番号ｋをインクリメントした後（ステップＳ４７０）、ステップＳ４１０に移行して上記した処理を繰り返し実行する。これにより、上記したように順次選定アーク間が変更されて、順次選定アーク間パスが生成されて、巡回路が完成される。
【００９６】
そして、ステップＳ４６０において、仕業検査想定回数を満足していると判定した場合には、巡回路探索部１２４は、候補解の評価値を以下の数式（１）に従って算出する（ステップＳ４８０）。
【数１】
2005259052.tif 000003
尚、ｘiを車両運用計画を評価する基準となる種々の項目に対応するパラメータ値、ｐiをそれぞれの評価基準に対する重みとする。例えば、ｎ＝３とし、ｘ１を使用車両数、ｘ２を回送列車の本数、ｘ３を回送列車の走行距離、そしてｐ１〜ｐ３をｘ１〜ｘ３それぞれに対応する重みとする。
【００９７】
これにより、巡回路探索部１２４は、例えば、候補解の表す車両運用計画において使用する車両の数（行路数）、回送列車の本数や走行距離といった項目を評価基準として、候補解の評価値を算出することができる。
【００９８】
図６に戻り、巡回路探索部１２４により実行される巡回路探索処理を終了すると、車両運用計画作成部１２０は、最良解格納領域６４０に格納される最良解の評価値と、候補解格納領域６２０に格納される候補解の評価値とを比較し（ステップＳ４５）、新たに探索された候補解が最良解よりも評価が高い場合に、最良解格納領域６４０を候補解格納領域６２０で更新する（ステップＳ５０）。
【００９９】
以上説明したように、候補解は、選定された交番検査可能アークの先ノードを初期点とした巡回路であり、得られた巡回路により表される車両運用計画において仕業検査の検査周期を満たすとともに、この検査周期内で車両により運用される列車ができるだけ多くなるように巡回路の修正を繰り返し、最終的に生成した巡回路に対して、車両運用計画に対する要望に基づいた評価を行うことにより作成される。
【０１００】
さて、ループＡを終了すると、車両運用計画作成部１２０は、最良解の巡回路が、全てのノードを一度だけ通過して初期点に戻る巡回路であるか否かを判定することで、当該最良解が完全であるか、不完全であるかを判断する（ステップＳ６０）。そして、車両運用計画作成部１２０は、得られた最良解が不完全であると判断した場合には、仕業検査想定回数をインクリメントして１増加させ（ステップＳ６５）、ステップＳ２５に戻って上記した処理を繰り返す。
【０１０１】
これにより、得られた最良解が不完全の場合には、行路数がステップＳ２０で取得した必要最低車両数となる車両運用計画は作成できないと判断し、必要最低車両数、すなわち仕業検査想定回数を増加させて、最良解の作成処理をやり直すことができる。
【０１０２】
また、ステップＳ６０において、得られた最良解が完全であると判断した場合には、最良解により表される車両運用計画を車両運用計画データ８４０として記憶媒体８００に格納し、例えば表示装置４００に出力して（ステップＳ７０）、本処理を終了する。
【０１０３】
以上説明したように、本実施形態によれば、候補解は、車両検査を割り当てた選定アーク間の最短路（アークでつないだパス全体のコストが最低となるパス）を探索するとともに、各検査の検査周期内で車両ができるだけ多くの列車を運行するように最短路の修正を繰り返す処理を、各選定アーク間について行うことで、車両検査の実施条件を満足する巡回路を生成し、車両運用計画に対する要望に基づいた評価を行うことにより作成される。したがって、上記した車両運用計画の作成に係る制約を守り、且つ車両運用計画に対する要望をなるべく反映するような車両運用計画を作成することができる。
【０１０４】
尚、上記した実施形態では、各アークに対して、元ノードにより表される列車の終着時刻と、先ノードにより表される列車の始発時刻との時間間隔（着発時間間隔）をコストとして設定することとしたが、以下のようにしてもよい。
【０１０５】
すなわち、翌日に接続可能な列車を表すノード間を連結するアークに対して設定するコストを調整することとしてもよい。具体的には、これらのアークには、元ノードにより表される列車の終着時刻から、例えば午前３時までの時間間隔をコストとして設定することとしてもよい。午前３時から始発時刻までの時間帯と、日中の時間帯とではそのコストを同一に扱えないからである。
【０１０６】
また、車両が回送列車として運転されることで接続可能な列車同士の接続を表す回送付当日接続アークや回送付翌日接続アークに対して、着発時間間隔に所定の値を加算した値をコストとして設定することとしてもよい。また、この際、当該回送列車の走行時間等を加味して前記加算する所定の値を変更することとしてもよい。アークでつないだパス全体のコストが最低となるパスが最短路として探索される（図８のステップＳ４２０）ので、ノード間を連結するアークに対応する列車同士の接続が回送列車を利用する場合に、当該アークに設定されるコストに大きい値を設定することで、なるべく該当するノード同士が接続されないように配慮することができるからである。これにより、なるべく回送列車を運転しない車両運用計画を作成することができる。
【０１０７】
また、図６に示して説明した車両運用計画作成処理を、複数の異なる交番検査案に対して行うこととしてもよい。これによれば、より最良の巡回路を探索することができる。
【０１０８】
また、列車ダイヤは、記憶媒体８００内に保存されていることとして説明したが、例えば、通信装置５００及び通信回線を介して列車ダイヤデータが格納されるデータベースとデータ通信を行い、該当する列車ダイヤデータをダウンロードすることとしても勿論構わない。
【図面の簡単な説明】
【０１０９】
【図１】（ａ）は列車ダイヤの一例、（ｂ）は（ａ）に示す列車ダイヤに基づく車両運用計画の一例を示す。
【図２】（ａ）は車両運用ネットワークの一例、（ｂ）は（ａ）に示す車両運用ネットワークの巡回路の一例を示す図。
【図３】車両運用計画作成装置の機能構成の一例を示すブロック図。
【図４】コストデータの一例を示す図。
【図５】検査可能アークリストの一例を示す図。
【図６】車両運用計画作成処理の一例を示すフローチャート。
【図７】車両運用ネットワーク生成処理の一例を示すフローチャート。
【図８】巡回路探索処理の一例を示すフローチャート。
【図９】対象選定アーク間の最短路の一例を示す図。
【図１０】パス追加処理の一例を示すフローチャート。
【図１１】対象選定アーク間のパスの生成過程を説明するための図。
【符号の説明】
【０１１０】
１０            車両運用計画作成装置
１００        ＣＰＵ
１１０      車両運用計画作成部
１１２    車両運用ネットワーク生成部
１１４    巡回路探索部
２００        ＲＯＭ
３００        入力装置
４００        表示装置
５００        通信装置
６００        ＲＡＭ
６２０      候補解格納領域
６４０      最良解格納領域
６６０      車両運用ネットワークデータ格納領域
６６２    検査可能アークリスト
６６４    コストデータ
７００        記憶装置
８００        記憶媒体
８２０      列車ダイヤデータ
８４０      車両運用計画データ
８６０      車両運用計画作成プログラム
８６２    車両運用ネットワーク生成プログラム
８６４    巡回路探索プログラム
【図１】
2005259052.tif 000004
【図２】
2005259052.tif 000005
【図３】
2005259052.tif 000006
【図４】
2005259052.tif 000007
【図５】
2005259052.tif 000008
【図６】
2005259052.tif 000009
【図７】
2005259052.tif 000010
【図８】
2005259052.tif 000011
【図９】
2005259052.tif 000012
【図１０】
2005259052.tif 000013
【図１１】
2005259052.tif 000014