JP5020199B2 - プログラム及び車両運用整理案作成装置 - Google Patents

Description

本発明は、車両運用整理案作成装置等に関する。

鉄道では、作成された計画ダイヤ（列車ダイヤ）を実現するため、車両の使用順序や車両に対する保守管理を含む車両の運用の計画である車両運用計画が定められる。この車両運用計画は、仕業検査等の車両に対する検査を定期的に実施するといった様々な制約を考慮して作成される。一方で、例えば定期検査の回数を極力少なくするといったように、車両運用にかかるコストを削減した効率の良い車両運用計画の作成が望まれていた。

そこで、車両検査を考慮し、且つ効率の良い車両運用計画を自動的に作成する装置として、例えば特許文献１に開示されている装置が知られている。かかる車両運用計画作成装置では、列車の接続間合いに車両検査を実施することが可能な検査可能アークを選定し、計画ダイヤを表現した車両運用ネットワークにおいて、全てのノードを一度だけ通過する巡回路であって、選定された全ての検査可能アークを含む巡回路が探索される。これは、複数日の運用行路がローテーションを組んで運用されており、車両運用計画が、列車ダイヤを構成する全ての列車をサイクリックに接続した接続パターンを日毎に区切ることにより作成した行路の集合として表現されているためである。
特開２００５−２５９５２号公報

ところで、ダイヤ乱れ時には、乱れたダイヤを正常なダイヤ（計画ダイヤ）に復帰させるために運転整理を行うが、この運転整理に伴って、車両運用計画を修正・変更する車両運用整理を行う必要がある。運転整理は、ダイヤ乱れの状況に応じて計画ダイヤの一部又は全部を対象期間として行われ、車両運用整理の対象期間は、この運転整理の対象期間に合わせたものになる。つまり、車両運用整理の対象期間は、ダイヤ乱れの状況に応じて異なる。このため、上述の特許文献１に開示されている、車両運用ネットワークにおいて列車ダイヤを構成する全ての列車をサイクリックに接続した接続パターン（巡回路）を探索するといった車両運用計画の作成手法を、そのまま車両運用計画に適用することができない。また、車両運用整理においても、車両運用計画の作成と同様に、定期検査を考慮しつつ、且つ効率の良い車両運用整理案の作成が望まれている。本発明は、上記事情に鑑みてなされたものであり、車両の定期検査を考慮し、且つ効率の良い車両運用整理案の作成の実現を目的としている。

上記課題を解決するための第１の発明は、
コンピュータに、所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成させるためのプログラムであって、
前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段、
前記運用整理基本ネットワークに含まれる所定ノードの総数Ｎに基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段、
前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数だけ生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段、
前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードの検査により検査期限条件を満たす前記所定ノードの数ｎ（≦Ｎ）に対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段、
前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段、
として前記コンピュータを機能させるためのプログラムである。

また、他の発明として、
所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成する車両運用整理案作成装置であって、
前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段と、
前記運用整理基本ネットワークに含まれる所定ノードの総数Ｎに基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段と、
前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数だけ生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段と、
前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードの検査により検査期限条件を満たす前記所定ノードの数ｎ（≦Ｎ）に対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段と、
前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段と、
を備える車両運用整理案作成装置を構成しても良い。

この第１の発明等によれば、対象ダイヤに基づく運用整理基本ネットワークが生成されるとともに、この運用整理基本ネットワークを複製した複製ネットワークが、運用整理基本ネットワークに含まれる所定ノードの総数Ｎに基づく数だけ複製され、運用整理基本ネットワークと合わせた拡張ネットワークが生成される。次いで、この拡張ネットワークにおいて、検査ノードそれぞれについて、該検査ノードを元ノードとするアークの先ノードが、検査期限条件を満たす所定ノードの数ｎに対応する複製ネットワーク中の対応する先ノードに変更される。そして、運用整理基本ネットワークの発ノードから拡張ネットワークの何れかの着ノードに至る経路が車両運用行路候補として探索され、探索された車両運用行路候補を組み合わせて運用整理案が作成される。

つまり、列車ノードと検査ノードとを含む車両運用ネットワークを生成することで、検査期限条件を満たす車両運用行路候補の探索が可能となる。また、検査期限条件を満たす車両運用行路候補の探索方法として、運用整理基本ネットワークを複製して拡張ネットワークを生成し、各検査ノードのアークの先ノードを当該検査ノードの検査により検査期限条件を満たす所定ノード数に対応する複製ネットワーク中の対応する先ノードに変更した後、拡張ネットワークにおいて経路探索を行う。かかる方法では、複製ネットワークそれぞれは、検査期限条件を満たす所定ノードの数ｎに対応している。また、各検査ノードのアークが、当該検査ノードにより検査期限条件を満たす所定ノード数に対応する複製ネットワーク中の対応する先ノード、すなわち、該検査ノードの検査期限条件に応じた複製ネットワーク中の先ノードに変更されている。つまり、仕業検査ノードのアークの変更によって検査期限の変更が表現されているとともに、変更した先ノードを含む複製ネットワークによって、変更した検査期限が表現されている。

ところで、車両運用行路の探索は、車両検査による検査期限を考慮して行わなければならない。具体的には、運用整理基本ネットワークにおいて、検査期限に達する前に次の検査ノードを選択するとともに、検査ノードを選択する毎に検査期限条件を更新しながら経路探索を行う必要がある。しかし、本発明のように、仕業検査ノードのアークの変更によって検査期限の変更が表現されていることから、各複製ネットワークにおいて、列車ノードと検査ノードとを区別することなく経路探索を行うことができ、検査期限条件を満たす車両運用行路候補の探索を簡単化できる。

また、第２の発明として、第１の発明のプログラムであって、
前記拡張ネットワーク生成手段が、前記整理対象期間が車両検査の検査周期より長い場合に、前記運用整理基本ネットワークに含まれる列車ノード及び着ノードを前記所定ノードとして前記拡張ネットワークを生成し、
前記アーク変更手段が、検査ノードの検査により前記検査期限条件を満たす列車ノード及び着ノードを前記所定ノードとして当該所定ノードの数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。

この第２の発明によれば、整理対象期間が車両検査の検査周期よりも長い場合には、列車ノード及び着ノードを所定ノードとし、運用整理基本ネットワークに含まれる列車ノード及び着ノードの総数Ｎだけの複製ネットワークが複製されて拡張ネットワークが生成される。そして、各検査ノードを元ノードとするアークの先ノードが、該検査ノードの検査により検査期限条件を満たす列車ノード及び着ノードの数ｎに対応する複製ネットワーク中の対応する先ノードに変更される。

また、第３の発明として、第１又は第２の発明のプログラムであって、
前記拡張ネットワーク生成手段が、前記整理対象期間が車両検査の検査周期以下の場合に、前記運用整理基本ネットワークに含まれる着ノードを前記所定ノードとして前記拡張ネットワークを生成し、
前記アーク変更手段が、検査ノードの検査により前記検査期限条件を満たす着ノードを前記所定ノードとして当該所定ノードの数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。

この第３の発明によれば、整理対象期間が車両検査の検査周期以下の場合には、着ノードを所定ノードとし、運用整理基本ネットワークに含まれる着ノードの総数Ｎだけの複製ネットワークが複製されて拡張ネットワークが生成される。そして、各検査ノードを元ノードとするアークの先ノードが、該検査ノードの検査により検査期限条件を満たす着ノードの数ｎに対応する複製ネットワーク中の対応する先ノードに変更される。

運用整理の対象期間が検査周期以下の場合、整理対象期間において少なくとも１回の検査が実施されることで、運用整理対象期間内の全ての列車ノードが検査期限条件を満たすこととなる。このため、アークの変更先の複製ネットワークとして、検査期限を満たす列車ノードの数に対応する複製ネットワークを考えなくとも良く、検査期限条件を満たす着ノードの数に対応する複製ネットワークのみを考えれば良い。これにより、複製ネットワークの数Ｎを減少させ、車両運用行路候補の探索にかかる演算量を低減させることができる。

第４の発明は、
コンピュータに、所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成させるためのプログラムであって、
前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段、
前記運用整理基本ネットワークを複製した複製ネットワークを、前記運用整理基本ネットワークに含まれる前記検査ノードの総数Ｎだけ生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段、
前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段、
前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段、
として前記コンピュータを機能させるためのプログラムである。

また、他の発明として、
所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成する車両運用整理案作成装置であって、
前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段と、
前記運用整理基本ネットワークを複製した複製ネットワークを、前記運用整理基本ネットワークに含まれる前記検査ノードの総数Ｎだけ生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段と、
前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段と、
前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段と、
前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段と、
を備える車両運用整理案作成装置を構成しても良い。

この第４の発明等によれば、対象ダイヤに基づく運用整理基本ネットワークが生成されるとともに、この運用整理基本ネットワークを複製した複製ネットワークが、運用整理基本ネットワークに含まれる検査ノードの総数Ｎだけ生成され、運用整理基本ネットワークと合わせた拡張ネットワークが生成される。次いで、この拡張ネットワークにおいて、検査ノードそれぞれについて、該検査ノードを元ノードとするアークの先ノードが、該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更される。そして、運用整理基本ネットワークの発ノードから拡張ネットワークの何れかの着ノードに至る経路が車両運用行路候補として探索され、探索された車両運用行路候補を組み合わせて運用整理案が作成される。

つまり、列車ノードと検査ノードとを含む車両運用ネットワークを生成することで、検査期限条件を満たす車両運用行路候補の探索が可能となる。また、検査期限条件を満たす車両運用行路候補の探索方法として、運用整理基本ネットワークを複製して拡張ネットワークを生成し、各検査ノードのアークの先ノードを当該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更した後、拡張ネットワークにおいて経路探索を行う。かかる方法では、Ｎ個の複製ネットワークそれぞれは検査ノードそれぞれに対応しており、各検査ノードのアークが、該検査ノードに対応する複製ネットワーク中の先ノードに変更されている。つまり、仕業検査ノードのアークの変更によって検査期限の変更が表現されている。

ところで、車両運用行路の探索は、車両検査による検査期限を考慮して行わなければならない。具体的には、運用整理基本ネットワークにおいて、検査期限に達する前に次の検査ノードを選択するとともに、検査ノードを選択する毎に検査期限条件を更新しながら経路探索を行う必要がある。しかし、本発明のように、仕業検査ノードのアークの変更によって検査期限の変更が表現されていることから、各複製ネットワークにおいて、列車ノードと検査ノードとを区別することなく経路探索を行うことができ、検査期限条件を満たす車両運用行路候補の探索を簡単化できる。

また、第５の発明として、第１〜第４の何れかの発明のプログラムであって、
各複製ネットワークにおいて、他のネットワークの検査ノードからのアークが変更・接続されることによる該検査ノードの検査によっても前記検査期限条件を満たすことのないノードに接続されたアークを切断するアーク切断手段として前記コンピュータを機能させるためのプログラムを構成しても良い。

この第５の発明によれば、各複製ネットワークにおいて、他のネットワークの検査ノードからのアークが変更・接続されることによる該検査ノードの検査によっても検査期限条件を満たすことのないノードに接続されたアークが切断される。つまり、検査期限条件を満たすノードにのみアークが接続されていることになる。これにより、検査ノードによる検査期限条件を考慮することなく、容易に、検査期限条件を満たすノードのみを選択して経路探索を行うことができる。

また、第６の発明として、第１〜第５の何れかの発明のプログラムであって、
前記列車ダイヤは前記整理対象期間を運転整理した運転整理ダイヤであり、
前記運用整理案作成手段が、
前記経路探索手段により探索された車両運用行路候補を組み合わせることによる暫定運用整理案を作成する暫定運用整理案作成手段と、
前記暫定運用整理案に含まれる車両運用行路候補と運転整理前の車両運用行路との差異に基づいて前記暫定運用整理案を評価する評価手段と、
を有し、前記暫定運用整理案作成手段及び前記評価手段を繰り返し実行させて最高評価の暫定運用整理案を前記運用整理案とする、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。

この第６の発明によれば、探索された車両運用行路候補を組み合わせることによる暫定運用整理案の作成と、暫定運用整理案に含まれる車両運用行路候補と、運転整理前の車両運用行路との差異に基づく暫定運用整理案の評価とが繰り返し実行されて、最高評価の暫定運用整理案が運用整理案とされる。これにより、逐次、その時点で最良とされる運用整理案が作成される。

また、第７の発明として、第６の発明のプログラムであって、
前記評価手段が、少なくとも、仕業切替に関する評価指標と、臨時検査の実施に関する評価指標とを含む複数の評価指標を用いて、前記暫定運用整理案に含まれる車両運用行路候補と運転整理前の車両運用行路との差異に基づく評価を行うように前記コンピュータを機能させるためのプログラムを構成しても良い。

この第７の発明によれば、仕業切替に関する評価指標と、臨時検査の実施に関する評価指標とを含む複数の評価指標を用いて、暫定運用整理案に含まれる車両運用行路候補と、運転整理前の車両運用行路との差異に基づく評価が行われる。

また、第８の発明として、第７の発明のプログラムであって、
前記評価指標それぞれについての評価値をユーザの操作入力に従って可変する評価値可変手段として前記コンピュータを機能させ、
前記評価手段が、前記可変された評価値に従って評価を行う、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。

この第８の発明によれば、評価指標それぞれについての評価値がユーザの操作入力に従って可変され、可変された評価値に従って暫定運用整理案の評価が行われる。つまり、各評価指標の評価値を可変すると、運用行路それぞれの評価が変化し、その結果、作成される暫定運用整理案の評価が変化する。ユーザにとってみれば、評価指標それぞれの評価値を任意に設定することが可能であるため、例えば所望の評価指標の評価値を他の評価指標の評価値よりも大きく設定することで、該所望の評価指標を重視した場合に最良とされる運用整理案を得ることができる。また、暫定運用整理案の作成が繰り返し実行されるため、重要視する評価指標を異ならせた複数の暫定運用整理案を得ることもできる。

本発明によれば、列車ノードと検査ノードとを含む車両運用ネットワークを生成することで、検査期限条件を満たす車両運用行路候補の探索が可能となる。また、検査期限条件を満たす車両運用行路候補の探索方法として、運用整理基本ネットワークを複製して拡張ネットワークを生成し、各検査ノードのアークの先ノードを当該検査ノードの検査により検査期限条件を満たす所定ノード数に対応する複製ネットワーク中の対応する先ノードに変更した後、拡張ネットワークにおいて経路探索を行う。かかる方法では、複製ネットワークそれぞれは、検査期限条件を満たす所定ノードの数ｎに対応している。また、各検査ノードのアークが、当該検査ノードにより検査期限条件を満たす所定ノード数に対応する複製ネットワーク中の対応する先ノード、すなわち、該検査ノードの検査期限条件に応じた複製ネットワーク中の先ノードに変更されている。つまり、仕業検査ノードのアークの変更によって検査期限の変更が表現されているとともに、変更した先ノードを含む複製ネットワークによって、変更した検査期限が表現されている。これにより、各複製ネットワークにおいて、列車ノードと検査ノードとを区別することなく経路探索を行うことができ、検査期限条件を満たす車両運用行路候補の探索を簡単化できる。

以下、図面を参照して、本発明の好適な実施形態を説明する。

［原理］
車両運用整理案作成装置は、列車のダイヤ乱れが発生した際に作成される運転整理ダイヤ（運転整理案）に合わせて、車両運用計画を変更した車両運用変更計画（車両運用整理案）を自動的に作成する装置である。車両運用計画とは、列車ダイヤを構成する全ての列車に対して車両を割り当てた車両の運用スケジュールのことである。そして、車両運用整理案とは、ダイヤ乱れ時の運転整理ダイヤに対する車両運用計画のことである。本実施形態の車両運用整理案作成装置では、暫定的な車両運用整理案（暫定運用整理案）を作成する暫定整理案作成処理が繰り返し実行され、最終的に評価が最良となった暫定運用整理案が出力される。

本実施形態において、車両運用整理案の作成は、この車両運用整理案の作成問題を「追加制約付き集合分割問題」にモデル化することで行われる。この追加制約付き集合分割問題を用いた車両運用計画の作成について、簡単な例を挙げて説明する。

図１は、運転整理ダイヤの一例を示す図である。列車ダイヤは、横軸を時刻ｔ、縦軸を駅Ａ，Ｂ，Ｃとして、列車の運行を表す「列車スジ」によって表現されている。各列車スジには、対応する列車番号が表記されている。また、この運転整理ダイヤに対する車両運用には、３台の車両ａ，ｂ，ｃが割り当てられている。

先ず、運転整理ダイヤに対して割り当てられる車両それぞれについて、運用行路の候補（行路候補）が設定される。ここで、運用行路は、１車両に割り当て可能な１又は複数の列車の組合せである。運用行路候補は、対象期間の開始時点において、対象車両が存在する駅を起点とした運用行路とされる。なお、ここで設定される行路候補は、考えられる全ての行路を含まなくとも良い。

図１の場合、各車両の行路候補は、図２に示すように設定される。すなわち、車両ａについては、Ａ駅を起点とする４つの行路候補が設定され、車両ｂについては、Ｂ駅を起点とする３つの行路候補が設定され、車両ｃについては、Ｃ駅を起点とする４つの行路候補が設定される。

続いて、行路候補それぞれが、所定の評価基準に従って評価され、評価値（行路評価値）が算出される。すなわち、行路候補それぞれが、予め定められた複数の評価指標それぞれを満たすかが判定され、満たすと判定された評価指標の指標値の和が、当該行路候補の行路評価値として算出される。この評価指標は、運用計画で定められた車両運用行路（計画行路）からの変更についてであり、具体的には、行路候補の一部又は全部が該当する車両とは異なる車両の仕業に変更されている「次仕業切替」や、仕業の途中で他の車両の仕業に変更されている「仕業中切替」、変更された仕業が該当する車両とは異なる形式の車両の仕業である「他区形式切替」、運用計画では実施されない臨時仕業検査が実施される「臨時仕業検査」がある。ここで、「仕業中切替」及び「他区形式切替」は、「次仕業切替」に行われる場合に更に判定される評価指標である。また、指標値は正の整数とする。つまり、行路評価値が小さいほど、「良い」行路候補であることを示す。

次いで、これらの行路候補それぞれに「変数Ｘ」を割り当て、追加制約付き集合分割問題にモデル化したモデル式が生成される。変数Ｘは、対応する行路候補を選択するか否か（選択是非）を示す変数であり、「１」は当該行路候補を選択することを示し、「０」は選択しないことを示す。そして、これらの行路候補を部分集合とし、運転整理ダイヤの対象期間の全ての列車を要素とした追加制約付き集合分割問題のモデル式を算出する。

「集合分割」とは、「全ての列車が、１つの車両の運用行路によって被覆される」ことである。このモデル式は、例えば図２の場合には、次式（１）となる。

また、「追加制約」とは、「１つの車両が選択できる運用行路は１つのみである」ということである。このモデル式は、例えば図２の場合には、次式（２）となる。

そして、この集合分割問題及び追加制約のそれぞれのモデル式の解であって、行路評価値の総和が最小となる解が算出される。このとき、変数Ｘの範囲を「０．０≦Ｘ≦１．０」として解を算出する。また、このモデル式の解法としては、例えばＳｉｍｐｌｅｘ法といった公知の手法を用いることができる。

算出された解が所定の運用整理条件を満たすならば、対応する変数Ｘの値が「１」である行路候補の組合せが運用整理案とされる。ここで、運用整理条件は、「変数Ｘの値がそれぞれ「０」或いは「１」である」ことである。そして、この運用整理案を構成する各行路候補の行路評価値の総和が、該運用整理案の総合評価値とされる。なお、算出された解が運用整理条件を満たさない（すなわち、算出した変数Ｘの値に「０」或いは「１」以外が１つでも含まれる）ならば、運用整理案は作成されない。追加制約付き集合分割問題にモデル化することによる運用整理案の作成は、このように行われる。

また、上述の運用整理案の作成において、各車両の行路候補の設定は、仕業検査（車両の定期検査の一つ）を考慮しなければならない。すなわち、各車両の運用行路は、該車両に対する仕業検査が、予め定められた検査周期（例えば、７２時間）を超過することなく実施されるように設定される。この仕業検査の制約を満たす行路候補の設定について説明する。

図３は、運転整理案（列車ダイヤ）の一例を示す図である。そして、図４は、この運転整理案のうち、運用整理対象期間のダイヤ部分を表現した列車ダイヤネットワークである。列車ダイヤネットワークは、横方向を時刻ｔとして、列車ダイヤを構成する各列車を表す列車ノードＲＮを配置し、接続可能な列車ノードＲＮ同士をアークで連結することで構成される。また、列車ダイヤネットワークには、スタートノードとして、対象の車両の発駅（すなわち、運用整理対象期間の開始時点での在線駅）を表す発ノードＳＮが設定されるとともに、エンドノードとして、該車両の着駅（すなわち、運用整理対象期間の終了時点において到着すべき駅）を表す着ノードＥＮが設定される。

着ノードＥＮは、運用整理対象期間以降の列車ダイヤに対する車両運用に応じて決められる。つまり、運用整理対象期間の車両運用は、運用整理対象期間以降の車両運用に接続されなければならないからである。そして、着ノードＥＮの数は、運用整理対象期間のダイヤ部分に割り当てられる車両の数に等しい。同図では、対象車両の発駅であるＢ駅を表す発ノードＳＮと、この車両の着駅となり得るＡ駅〜Ｃ駅それぞれを表す３つの着ノードＥＮ１〜ＥＮ３とが設定されている。

次いで、この列車ダイヤネットワークに、実施可能な仕業検査を表す仕業検査ノードを追加した運用整理基本ネットワークが生成される。図５は、図４の列車ダイヤネットワークに基づく運用整理基本ネットワークを示す図である。

仕業検査の実施には所定時間（例えば、１時間）を要する。このため、仕業検査ノードＴＮは、仕業検査が実施可能であると定められた駅において、接続される列車同士の時間間隔（先列車の着時刻と後列車の発時刻までの時間）が仕業検査の実施所要時間以上である列車ノードＲＮ間に追加される。

例えば、図３に示す列車ダイヤでは、Ａ，Ｃ駅において仕業検査が可能である。そして、図５に示す運用整理基本ネットワークでは、Ａ駅において接続される１列車を表す列車ノードＲＮ１と５列車を表す列車ノードＲＮ５との間に仕業検査ノードＴＮ１が追加され、３列車を表す列車ノードＲＮ３とＡ駅を表す着ノードＥＮ１との間に仕業検査ノードＴＮ２が追加されている。なお、３列車と５列車との間は、接続時間間隔が短いため、仕業検査は実施不可能である。また、Ｃ駅において接続される２列車を表す列車ノードＲＮ２とＣ駅を表す着ノードＥＮ３との間に仕業検査ノードＴＮ３が追加されている。

このように、列車ダイヤネットワークに仕業検査ノードＴＮを追加して生成された運用整理基本ネットワークにおいて、発ノードＳＮから何れかの着ノードＥＮに至る経路が探索され、該車両の運用行路の候補とされる。このとき、経路探索は、予め定められた仕業検査の検査周期を満たすように行われる。

本実施形態では、仕業検査の検査周期を考慮した経路探索を次のように行う。先ず、図６に示すように、運用整理基本ネットワークＢＭを複製した複数の複製ネットワークＣＭが生成され、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとされる。生成される複製ネットワークＣＭの数は、運用整理基本ネットワークに含まれる列車ノードＲＮ及び着ノードＥＮによって決まる。具体的には、運用整理基本ネットワークＢＭに含まれる列車ノードＲＮ及び着ノードＥＭの総数Ｎと、発ノードＳＮの「到達可能ノード数ｎ」との差である（Ｎ−ｎ）個の複製ネットワークＣＭが生成される。そして、拡張ネットワークＥＭを構成する各ネットワークに「ｎ」〜「Ｎ」のラベルが付けられる。詳細には、運用整理基本ネットワークＢＭには発ノードＳＮの到達可能ノード数ｎに等しい「ｎ」のラベルが付けられ、複製ネットワークＣＭそれぞれには「ｎ＋１」〜「Ｎ」のラベルが付けられる。

ここで、到達可能ノード数ｎとは、該当する仕業検査の実施によって「検査期限条件」を満たす列車ノードＲＮ及び着ノードＥＮの数である。検査期限条件とは、仕業検査の検査周期を満たすための条件であり、具体的には、次の仕業検査が実施されなければならない期限（検査期限）の条件である。つまり、到達可能ノード数ｎとは、仕業検査の実施によって、次の仕業検査を実施しなくとも発ノードＳＮから到達可能となる列車ノードＲＮ及び着ノードＥＮの数を意味する。

発ノードＳＮの到達可能ノード数ｎは、運用整理対象期間以前の列車運用において該発ノードＳＮの直前に実施される仕業検査によって検査期限条件を満たす列車ノードＲＮ及び着ノードＥＮの数として定められる。

図７は、発ノードＳＮの到達可能ノード数ｎを説明する図である。同図において、発ノードＳＮの直前の仕業検査ノードＴＮａで表現される仕業検査ａによる検査期限は、運用整理対象期間内であって、列車ノードＲＮ２と列車ノードＲＮ３との間に定められる。つまり、２つの列車ノードＲＮ１，ＲＮ２が期限条件を満たし、発ノードＳＮの到達可能ノード数ｎは「２」である。

図６では、運用整理基本ネットワークＢＭに含まれる列車ノードＲＮ及び着ノードＥＭの総数Ｎは「９」であり、発ノードＳＮの到達可能ノード数ｎは「２」である。従って、７（＝９−２）個の複製ネットワークＣＭが生成される。そして、運用整理基本ネットワークＢＭには「２」のラベルが付けられ、各複製ネットワークＣＭには「３」〜「９」のラベルが付けられている。

続いて、この拡張ネットワークＥＭにおいて、各仕業検査ノードＴＮを元ノードとするアークの付け替えが行われる。図８は、図６の拡張ネットワークＥＭにおける各仕業検査ノードＴＮのアークの付け替えを説明する図である。図８に示すように、各仕業検査ノードＴＮを元ノードとするアークの先ノードが、該仕業検査ノードＴＮに基づく到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭにおける先ノードに変更される。

仕業検査ノードＴＮに基づく到達可能ノード数ｎは、該仕業検査ノードＴＮに該当する仕業検査の実施によって検査期限条件を満たす列車ノードＲＮ及び着ノードＥＮの数として定められる。

ここで、検査期限条件を満たすか否かの判定は、列車ノードＲＮであるか着ノードＥＮであるかによって異なる。すなわち、列車ノードＲＮについては、検査期限以前であるならば該列車ノードＲＮは検査期限条件を満たすと判定され、検査期限を越えるならば該列車ノードＲＮは検査期限条件を満たさないと判定される。

図９は、検査期限条件を満たす列車ノードＲＮの判定を説明する図である。同図において、仕業検査ノードＴＮに該当する仕業検査の実施によって決まる検査期限は、運用整理対象期間内であって、列車ノードＲＮ４と列車ノードＲＮ５との間に定められている。つまり、運用整理対象期間の開始時点からこの検査期限までの間に含まれる４つの列車ノードＲＮ１〜ＲＮ４は検査期限条件を満たし、これ以外の列車ノードＲＮ５，ＲＮ６は検査期限条件を満たさないと判定される。

また、着ノードＥＮについては、運用整理対象期間以降の車両運用において該着ノードＥＮの直後に実施される仕業検査が検査期限以前であるならば、該着ノードＥＮは検査期限条件を満たすと判定され、検査期限を越えるならば該着ノードＥＮは検査期限条件を満たさないと判定される。これは、運用整理対象期間以降は列車ダイヤ及び車両運用が決まっており、運用整理対象期間の車両運用は、この決まっている車両運用に接続しなくてはならないためである。

図１０は、検査期限条件を満たす着ノードＥＮの判定を説明する図である。同図において、仕業検査ノードＴＮａによって決まる検査期限は、運用整理対象期間以降であって、着ノードＥＮ１の直後の仕業検査ノードＴＮｘで表現される仕業検査ｘと、着ノードＥＮ２の直後の仕業検査ノードＴＮｙで表現される仕業検査ｙ及び着ノードＥＮ３の直後の仕業検査ノードＴＮｚで表現される仕業検査ｚとの間に定められる。つまり、仕業検査ｘは検査期限以前に実施され、仕業検査ｙ，ｚは検査期限以降に実施される。従って、着ノードＥＮ１は検査期限条件を満たし、着ノードＥＮ２，ＥＮ３は検査期限条件を満たさないと判定される。

そして、図８に示した運用整理基本ネットワークＢＭにおける各仕業検査ノードＴＮに基づく到達可能ノード数ｎは、図１１〜図１３のようになる。図１１は、仕業検査ノードＴＮ１に基づく到達可能ノード数ｎを説明する図である。同図において、仕業検査ノードＴＮ１に該当する仕業検査の実施による検査期限は、運用整理対象期間内であって、列車ノードＲＮ６の以降に定められる。つまり、６つの列車ノードＲＮ１〜ＲＮ６が検査期限条件を満たし、仕業検査ノードＴＮ１に基づく到達可能ノード数ｎは「６」である。

また、図１２は、仕業検査ノードＴＮ２に基づく到達可能ノード数ｎを説明する図である。同図において、仕業検査ノードＴＮ２に該当する仕業検査の実施による検査期限は、運用整理対象期間以降であって、着ノードＥＮ２の直後の仕業検査ノードＴＮｘで表現される仕業検査ｘと、着ノードＥＮ２の直後の仕業検査ノードＴＮｙで表現される仕業検査ｙとの間に定められる。つまり、６つの列車ノードＲＮ１〜ＲＮ６と１つの着ノードＥＮ１が検査期限条件を満たし、仕業検査ノードＴＮ２に基づく到達可能ノード数ｎは「７」である。

また、図１３は、仕業検査ノードＴＮ３に基づく到達可能ノード数ｎを説明する図である。同図において、仕業検査ノードＴＮ３に該当する仕業検査の実施による検査期限は、運用整理対象期間以降であって、着ノードＥＮ３の直後の仕業検査ノードＴＮｚで表現される仕業検査ｚ以降に定められる。つまり、６つの列車ノードＲＮ１〜ＲＮ６と３つの着ノードＥＮとが検査期限条件を満たし、仕業検査ノードＴＮ３に基づく到達可能ノード数ｎは「９」である。

なお、後述のように、拡張ネットワークＥＭにおける経路探索は、運用整理基本ネットワークＢＭの発ノードＳＮを始点として行われる。このため、各複製ネットワークＣＭの全ての仕業検査ノードＴＮについてアークの付け替えを行う必要が無い。すなわち、運用整理基本ネットワークＢＭにおいて、各仕業検査ノードＴＮのアークの付け替えを行うとともに、このアークが付け替えられた先の複製ネットワークＣＭそれぞれにおいて、付け替えられたアークの先ノード以降の各仕業検査ノードＴＮについてアークの付け替えを行えばよい。

つまり、図８において、発ノードＳＮの到達可能ノード数ｎは「２」である。また、仕業検査ノードＴＮ１〜ＴＮ３の到達可能ノード数ｎは、それぞれ、「６」，「７」，「９」である。従って、同図に示す拡張ネットワークＥＭでは、運用整理基本ネットワークＢＭ（ラベル「２」）において、仕業検査ノードＴＮ１を元ノードとするアークの先ノードが、ラベル「６」の複製ネットワークＣＭの列車ノードＲＮ３に付け替えられている。また、仕業検査ノードＴＮ２を元ノードとするアークの先ノードが、ラベル「７」の複製ネットワークＣＭの列車ノードＲＮ４に付け替えられている。また、仕業検査ノードＴＮ３を元ノードとするアークの先ノードが、ラベル「９」の複製ネットワークＣＭの着ノードＥＮ２に付け替えられている。更に、ラベル「６」，「７」の複製ネットワークＣＭそれぞれにおいて、仕業検査ノードＴＮ３のアークがラベル「９」の複製ネットワークＣＭの着ノードＥＮに付け替えられている。

このように、仕業検査ノードＴＮのアークが付け替えられた拡張ネットワークＥＭにおいて、運用整理基本ネットワークＢＭの発ノードＳＮから、何れかの着ノードＥＮに到達する経路が探索される。

また、この経路探索では、仕業検査の検査期間を考慮するため、仕業検査ノードＴＮを選択する毎に、該当する仕業検査によって決まる検査期限以降のノードに向かうアークが切断される。図１４は、経路探索の際のアークの切断を説明する図である。同図に示すように、仕業検査ノードＴＮを選択する毎に、該仕業検査ノードＴＮのアークの付け替え先の複製ネットワークＣＭ（すなわち、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭ）において、該仕業検査ノードＴＮに該当する仕業検査の実施によっても検査期限条件を満たさないノードに向かうアークが切断される。

すなわち、列車ノードＲＮについては、検査期限以降の列車ノードＲＮに向かうアークが切断される。一方、着ノードＥＮについては、図１５に示すように、その直後に実施される仕業検査が検査期限以降である着ノードＥＮに向かうアークが切断される。同図では、仕業検査ノードＴＮ１に該当する仕業検査の実施による検査期限は、運用整理対象期間以降に定められる。そして、着ノードＥＮ１の直後の仕業検査ノードＴＮｘで表現される仕業検査ｘは検査期限以前に実施されるため、該着ノードＥＮ１は検査期限条件を満たす。また、着ノードＥＮ２．ＥＮ３それぞれの直後の仕業検査ノードＴＮｙ，Ｔｎｚで表現される仕業検査ｙ、ｚは検査期限より後に実施されるため、該着ノードＥＮ２，ＥＮ３は検査期限条件を満たさない。従って、この場合、着ノードＥＮ２，ＥＮ３それぞれに向かうアークが切断される。

図１４では、先ず、運用整理基本ネットワークＢＭ（ラベル「２」）において、発ノードＳＮの直前に実施される仕業検査による検査期限条件を満たさない（検査期限を越える）列車ノードＲＮ３〜ＲＮ６、仕業検査ノードＴＮ２，ＴＮ３、及び、着ノードＥＮ１〜ＥＮ３それぞれに向かうアークが切断される。

次いで、仕業検査ノードＴＮ１を選択してラベル「６」の複製ネットワークＣＭに遷移すると、このラベル「６」の複製ネットワークＣＭにおいて、仕業検査ノードＴＮ１による検査期限条件を満たさない着ノードＥＮ１〜ＥＮ３それぞれに向かうアークが切断される。

更に、このラベル「６」の複製ネットワークＣＭにおいて、仕業検査ノードＴＮ２を選択してラベル「７」の複製ネットワークＣＭに遷移した場合も、同様に、このラベル「７」の複製ネットワークＣＭにおいて、仕業検査ノードＴＮ２による検査期限条件を満たさない（検査期限を越える）各ノードに向かうアークが切断される。また、仕業検査ノードＴＮ３を選択した場合も同様である。

ところで、仕業検査の検査周期が運用整理の対象期間より長い場合、より少ない数の複製ネットワークＣＭによって拡張ネットワークＥＭを構成することができる。すなわち、運用整理対象期間内において、少なくとも１回の仕業検査が実施されることで、該仕業検査による仕業検査期限は、運用整理対象期間以降に定められることになる。つまり、運用整理対象期間内の全ての仕業検査ノードＴＮの検査期限条件を全ての列車ノードＲＮが満たし、その到達可能ノード数ｎは、運用整理対象期間内の列車ノードＲＮの総数以上となる。

図１６は、仕業検査周期が運用整理対象期間より長い場合の、拡張ネットワークＥＭにおけるアークの付け替えを説明する図である。同図では、発ノードＳＮの到達可能ノード数ｎは「２」であり、運用整理基本ネットワークＢＭのラベルは「２」である。また、運用整理対象期間内の列車ノードＲＮの総数は「６」である。つまり、運用整理対象期間内の各仕業検査ノードＴＮの到達可能ノード数ｎは、必ず「６」以上となる。すなわち、仕業検査ノードＴＮ１〜ＴＮ３それぞれに該当する仕業検査による検査期限は、何れも運用整理対象期間以降に定められ、その到達可能ノード数ｎは、それぞれ、「７」，「８」，「９」である。

つまり、これらの仕業検査ノードＴＮ１〜ＴＮ３それぞれのアークの付け替え先は、ラベル「７」〜「９」の何れかの複製ネットワークＣＭとなり、ラベル「３」〜「５」の複製ネットワークＣＭに付け替えられることはない。このため、「仕業検査期間が運用整理対象期間よりも長い」場合、仕業検査ノードＴＮの到達可能ノード数ｎを、「該仕業検査ノードＴＮによる検査期限条件を満たす列車ノードＲＮ及び着ノードＥＮの数」ではなく、「該仕業検査ノードＴＮによる検査期限条件を満たす着ノードＥＮの数」とする。

また、生成する複製ネットワークＣＭの数を、着ノードＥＮの総数Ｍと、運用整理基本ネットワークＢＭの到達可能ノード数ｎとの差である（Ｍ−ｎ）個とする。そして、運用整理基本ネットワークＢＭ及び（Ｍ−ｎ）個の複製ネットワークＣＭからなる拡張ネットワークＥＭにおいて、運用整理基本ネットワークＢＭのラベルを発ノードＳＮの到達可能ノード数ｎとし、複製ネットワークＣＭそれぞれのラベルを「ｎ＋１」〜「Ｍ」とする。

図１７は、図１６に示した拡張ネットワークＥＭにおいて、到達可能ノード数ｎを「検査期限条件を満たす着ノードＥＮの数」とした場合を示す図である。図１７において、着ノードＥＮの数は「３」である。また、発ノードＳＮの直前に実施される仕業検査による検査期限は運用整理対象期間内に定められ、該発ノードＳＮの到達可能ノード数ｎは「０」である。従って、３（＝３−０）個の複製ネットワークＣＭが生成され、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとされる。そして、運用整理基本ネットワークＢＭに「０」のラベルが付けられ、３個の複製ネットワークＣＭそれぞれに「１」〜「３」が付けられている。

更に、仕業検査ノードＴＮ１〜ＴＮ３の到達可能ノード数ｎは、それぞれ、「１」，「２」，「３」である。従って、運用整理基本ネットワークＢＭにおいて、仕業検査ノードＴＮ１〜ＴＮ３それぞれのアークが、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベル「１」，「２」，「３」の複製ネットワークＣＭに付け替えられている。

また、本実施形態では、車両運用整理案の作成に用いられる評価基準を、ユーザが任意に設定・変更することが可能となっている。このユーザ操作を、表示画面を参照して説明する。

先ず、評価基準を設定するための「評価基準設定画面」が表示される。図１８に、評価基準設定画面の一例を示す。同図によれば、評価基準設定画面には、複数の評価指標それぞれについて、その指標値を変更・設定するためのスライダＳが設けられているとともに、このスライダＳによって指示されている現在の指標値Ｖが表示されている。ユーザは、この評価基準設定画面において、例えばマウス操作等によってスライダＳを移動（スライド）させ、該当する評価指標の指標値Ｖを変更する。そして、開始アイコンＩＣ１を選択すると、各評価指標の指標値が変更した値に設定される。その後、暫定整理案作成処理が開始され、当該処理を実行中であることを示す「実行中画面」が表示される。なお、運用整理案の作成そのものを終了する場合には、キャンセルアイコンＩＣ２を選択する。

図１９に、実行中画面の一例を示す。同図によれば、実行中画面には、車両運用整理案を作成中であることを示すメッセージＭが表示されるとともに、作成された暫定運用整理案それぞれの名称及び総合評価値が次々と一覧表示される。同図では、３つの暫定運用整理案１〜３が作成されていることを示している。なお、この暫定運用整理案の総合評価値は、上述の評価基準設定画面において設定された各評価指標の指標値に基づくものである。この実行中画面において中断アイコンＩＣ３を選択すると、実行中の暫定整理案作成処理が一時中断され、評価基準を再設定するための「評価基準再設定画面」が表示される。なお、暫定整理案作成処理を終了する場合には、終了アイコンＩＣ４を選択する。

図２０に、評価基準再設定画面の一例を示す。同図によれば、評価基準再設定画面には、評価基準設定画面と同様に、複数の評価指標それぞれについて、指標値を設定するためのスライダＳが設けられているとともに、現在の指標値が表示されている。ユーザは、評価基準設定画面と同様に、スライダＳを移動させて、各評価指標の指標値Ｖを変更する。そして、再開アイコンＩＣ５を選択すると、各評価指標の指標値が変更した値に再設定され、一時中断している暫定整理案作成処理が再開され、図１９に一例を示した実行中画面が、再度表示される。この再開以降の運用整理案作成処理は、再設定した評価基準値に基づいて実行される。

［構成］
図２１は、車両運用整理案作成装置１の構成を示すブロック図である。同図によれば、車両運用整理案作成装置１は、例えばコンピュータで実現され、ＣＰＵ１０と、入力部２０と、表示部３０と、通信部４０と、記憶部５０とを備えて構成される。

ＣＰＵ１０は、記憶部５０に記憶されたプログラムやデータ、入力部２０から入力されたデータ等に基づいて、車両運用整理案作成装置１を構成する各部への指示やデータ転送を行い、車両運用整理案作成装置１の全体制御を行う。また、ＣＰＵ１０は、車両運用整理プログラム５１０に従った運用整理案作成処理を行って、運転整理ダイヤ（運転整理案）に対する車両運用整理案を作成する。なお、運転整理ダイヤは、運転整理案データ５２３に格納されている。

具体的には、先ず、評価基準値の設定を行う。すなわち、図１８に一例を示した評価基準設定画面を表示部３０に表示させ、入力部２０から入力されるユーザの操作指示に従って、各評価指標の指標値を設定する。設定された評価基準値は、評価基準データ５２４に格納される。また、入力部２０から入力されるユーザの操作指示に従って、車両運用整理の対象となる区間や期間、車両等を設定する。

図２２に、評価基準データ５２４のデータ構成の一例を示す。同図によれば、評価基準データ５２４は、予め定められた複数の評価指標５２４ａそれぞれについて、現在の指標値５２４ｂを対応付けて格納している。

その後、ＣＰＵ１０は、例えば図１９に一例を示した実行中画面を表示部３０に表示させ、暫定整理案作成処理を開始する。先ず、対象の車両それぞれについて、所定数の運用行路の候補（行路候補）を設定する。すなわち、運転整理ダイヤの運用整理対象期間のダイヤ部分に基づく列車ダイヤネットワークを生成する。このとき、発ノードＳＮを、対象の車両の運用整理対象期間の開始時点での在線駅とし、着ノードＥＮを、運用整理対象期間の終了時点において該車両が到着すべき駅とする。次いで、この列車ダイヤネットワークに、実施可能な仕業検査ノードＴＮを追加した運用整理基本ネットワークＢＭを生成する。そして、この運用整理基本ネットワークＢＭを複製した複製ネットワークＣＭを生成し、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとする。

すなわち、運用整理対象期間が仕業検査周期より長い場合には、運用整理基本ネットワークＢＭの発ノードＳＮ及び仕業検査ノードＴＮそれぞれについて、到達可能ノード数ｎを、該当する仕業検査による検査期限条件を満たす列車ノードＲＮ及び着ノードＥＮの総数として設定する。そして、運用整理対象期間内の列車ノードＲＮ及び着ノードＥＮの総数Ｎと、発ノードの到達可能ノード数ｎとの差に等しい（Ｎ−ｎ）個の複製ネットワークＣＭを生成し、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとする。また、運用整理基本ネットワークＢＭに、該運用整理基本ネットワークＢＭの到達可能ノード数ｎに等しい「ｎ」のラベルを付け、各複製ネットワークＣＭに「ｎ＋１」〜「Ｎ」のラベルを付ける。

一方、運用整理対象期間が仕業検査周期以下の場合には、運用整理基本ネットワークＢＭの発ノードＳＮ及び仕業検査ノードＴＮそれぞれについて、到達可能ノード数ｎを、該当する仕業検査による検査期限条件を満たす着ノードＥＮの総数として設定する。
そして、着ノードＥＮの数Ｍと、発ノードＳＮの到達可能ノード数ｎとの差に等しい（Ｍ−ｎ）個の複製ネットワークＣＭを生成し、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとする。また、運用整理基本ネットワークＢＭに、該運用整理基本ネットワークＢＭの到達可能ノード数ｎに等しい「ｎ」のラベルを付け、各複製ネットワークＣＭに「ｎ＋１」〜「Ｍ」のラベルを付ける。

拡張ネットワークＥＭを生成すると、続いて、仕業検査ノードＴＮそれぞれについて、該仕業検査ノードＴＮを元ノードとするアークの先ノードを、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭに付け替える。

その後、仕業検査ノードＴＮのアークが付け替えられた拡張ネットワークＥＭにおいて、運用整理基本ネットワークＢＭの発ノードＳＮから、何れかの着ノードＥＮに至る経路探索を行う。また、仕業検査ノードＴＮを選択したときは、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭ（すなわち、該仕業検査ノードＴＮのアークの付け替え先の複製ネットワークＣＭ）において、該仕業検査ノードＴＮに該当する仕業検査による検査期限を満たさない各ノードに向かうアークを切断する。

各車両の運用行路候補を設定すると、次いで、設定した行路候補それぞれの行路評価値を算出する。すなわち、行路候補それぞれについて、該当する車両の計画行路を比較して、評価指標それぞれを満たすかを判定し、満たすと判定した評価指標の指標値の和を、当該行路候補の行路評価値とする。ここで、車両の計画行路は、車両運用計画を構成する各車両の運行行路であり、車両運用計画データ５２２に格納されている。この車両運用計画は、計画ダイヤデータ５２１に格納されている計画ダイヤに対応するものである。

設定した行路候補についてのデータは、行路候補データ５２５に格納される。図２３に、行路候補データ５２５のデータ構成の一例を示す。同図によれば、行路候補データ５２５は、運用整理の対象の車両５２５ａ毎に、設定した行路候補５２５ｂと、行路評価値５２５ｃと、変数５２５ｄとを対応付けて格納している。変数５２５ｄは、追加制約付き集合分割問題としてモデル化する際に割り当てられる変数Ｘである。

そして、これらの行路候補のうちから、運転整理ダイヤのうち、対象範囲の全ての列車に１台の車両が割り当てられる組合せであって、行路評価値の和が最小となる組合せを選択する。すなわち、上述のように、各車両に設定した行路候補それぞれに変数Ｘを割り当て、追加制約付き集合分割問題にモデル化したモデル式を算出し、このモデル式の解を算出する。次いで、算出した解が運用整理条件を満たすかを判断する。すなわち、算出した全ての変数Ｘの値が「１」或いは「０」ならば、運用整理条件を満たすと判定し、それ以外の値ならば、運用整理条件を満たさないと判断する。運用整理条件を満たすと判断したならば、変数Ｘの値が「１」である行路候補の組合せを暫定運用整理案とし、この暫定運用整理案を構成する各行路候補の行路評価値の和を、当該暫定運用整理案の総合評価とする。そして、作成した暫定運用整理案を、現在の評価基準と対応付けて暫定整理案データ５２７とし、車両運用整理案データ５２６に追加する。

図２４に、暫定整理案データ５２７のデータ構成の一例を示す。同図によれば、暫定整理案データ５２７は、作成された暫定運用整理案毎に作成され、運用整理案５２８と、総合評価値５２８ｄと、評価基準５２９とを含んでいる。運用整理案５２８は、当該運用整理案を構成する運用行路の組合せであり、運用整理の対象となっている車両５２８ａそれぞれについて、運用行路５２８ｂと、行路評価値５２８ｃとを対応付けて格納している。総合評価値５２８ｄは、当該運用整理案の総合評価値であり、当該運用整理案を構成する運用行路それぞれの行路評価値の和である。評価基準５２９は、当該運用整理案が作成されたときの評価基準であり、評価指標５２９ａそれぞれについて、指標値５２９ｂを対応付けて格納している。

ＣＰＵ１０は、以上の暫定整理案作成処理を繰り返し実行する。この暫定整理案作成処理の繰り返し毎に、各列車に設定する行路候補を変更する。すなわち、初回（１回目）の暫定整理案作成処理では、各車両について所定数の行路候補を設定するが、２回目以降の暫定整理案作成処理では、各車両について所定数の行路候補を追加し、繰り返し毎に行路候補の数を増加させてゆく。このとき、追加する行路候補は、当該車両に既に設定されている行路候補とは異なる行路とする。これにより、より最良な暫定運用整理案の作成が期待される。

また、ＣＰＵ１０は、２回目以降の暫定整理案作成処理では、今回作成した暫定運用整理案が、直近に作成した暫定運用整理案と比較して「改善」されているかを判断する。具体的には、今回の暫定運用整理案の総合評価値が、直近の暫定運用整理案の総合評価値よりも小さいならば「改善された」と判断し、そうでないならば「改善されていない」と判断して所定のカウンタを「１」加算（カウントアップ）する。つまり、このカウンタは、作成した暫定運用整理案が、直近に作成した暫定運用整理案と比較して改善されなかった回数をカウントしている。そして、このカウンタ値が所定値に達すると、暫定整理案作成処理の繰り返しを終了する。

また、ＣＰＵ１０は、暫定整理案作成処理の実行中、入力部２０から、ユーザによる処理の一時中断指示が入力されると、実行中の暫定整理案作成処理を一時中断する。次いで、例えば図２０に一例を示した評価基準再設定画面を表示部３０に表示させ、入力部２０から入力されるユーザの操作指示に従って、各評価指標の指標値を変更する。そして、入力部２０から、ユーザによる暫定整理案作成処理の「再開」指示が入力されると、各評価指標の指標値を変更後の値に再設定し、一時中断している暫定整理案作成処理を再開する。このときは、一時中断前の進行状況に関わらず、車両に設定した行路候補それぞれの行路評価値の算出から再開する。また、ＣＰＵ１０は、入力部２０から、ユーザによる暫定整理案作成処理の「終了」指示が入力されると、暫定整理案作成処理の繰り返しを終了する。

図２１に戻り、入力部２０は、例えばキーボードやマウス、タッチパネル、各種スイッチ等で実現される入力装置であり、操作入力に応じた入力信号をＣＰＵ１０に出力する。
表示部３０は、例えばＬＣＤ（Liquid Crystal Display）やＥＬＤ（Electronic Luminescent Display）等で実現される表示装置であり、ＣＰＵ１０から入力される表示信号に基づく各種画面を表示する。通信部４０は、例えば無線通信モジュールやルータ、モデム、ＴＡ、有線用の通信ケーブルのジャックや制御回路等で実現される通信装置であり、外部機器との間でデータ通信を行う。

記憶部５０は、ＣＰＵ１０が車両運用整理案作成装置１を統合的に制御するための諸機能を実現するためのシステムプログラムや、本実施形態の車両運用整理案の作成処理を実行するためのプログラムやデータ等を記憶しているとともに、ＣＰＵ１０の作業領域として用いられ、ＣＰＵ１０が各種プログラムに従って実行した演算結果や、入力部２０からの入力信号が一時的に格納される。本実施形態では、記憶部５０には、プログラムとして車両運用整理プログラム５１０が記憶されるとともに、データとして、計画ダイヤデータ５２１と、車両運用計画データ５２２と、運転整理案データ５２３と、評価基準データ５２４と、行路候補データ５２５と、車両運用整理案データ５２６とが記憶される。

［処理の流れ］
図２５は、車両運用整理案作成処理の流れを説明するためのフローチャートである。同図によれば、ＣＰＵ１０は、先ず、評価基準の入力・設定を行う。すなわち、ユーザが評価基準の設定を行うための評価基準設定画面を表示部３０に表示させ、入力部２０から入力されるユーザの操作指示に従って、各評価指標の評価値を設定する（ステップＡ１）。次いで、運用行路候補算出処理（図２６参照）を行って、車両それぞれについて所定数ａの行路候補を設定し（ステップＡ３）、設定した行路候補それぞれについて行路評価値を算出する（ステップＡ５）。

その後、暫定整理案作成処理の繰り返しを開始する。すなわち、各車両に設定した行路候補それぞれに変数Ｘを割り当て追加制約付き集合分割問題にモデル化したモデル式を算出する（ステップＡ７）。次いで、行路候補それぞれの行路評価値に当該行路候補に対応する変数Ｘの値を乗じた値の総和が最小となるモデル式の解を算出する（ステップＡ９）。そして、算出した解が運用整理条件を満たすかを判断し、満たすならば（ステップＡ１１：ＹＥＳ）、変数Ｘの値が「１」の行路候補の集合を、暫定運用整理案とする。また、変数Ｘの値が「１」の行路候補それぞれの行路評価値の和を算出し、作成した暫定運用整理案の総合評価値とする（ステップＡ１３）。そして、作成した暫定運用整理案を、算出した総合評価値と対応付けて記憶する（ステップＡ１５）。ここまでが、暫定整理案作成処理である。

暫定整理案作成処理が終了すると、続いて、行路候補算出処理（図２６参照）を行って、車両それぞれについて所定数ｂの新たな行路候補を追加設定し（ステップＡ１７）、各行路候補の行路評価値を算出する（ステップＡ１９）。その後、上述の暫定整理案作成処理（ステップＡ７〜Ａ１５）と同様の処理を行う（ステップＡ２１）。

そして、この暫定整理案作成処理において暫定運用整理案が作成されたならば（ステップＡ２３：ＹＥＳ）、今回作成された暫定運用整理案が、直近に作成された暫定運用整理案と比較して改善されたかを判定する。すなわち、今回の暫定運用整理案の総合評価値が直近の暫定運用整理案の総合評価値より大きいならば「改善された」と判断し、そうでないならば「改善されていない」と判断する。

改善されたと判断したならば（ステップＡ２５：ＹＥＳ）、続いて、処理の打ち切り時間に達したかを判断する。処理の打ち切り時間に達していないならば（ステップＡ３１：ＮＯ）、ステップＡ１７に戻り、打ち切り時間に達しているならば（ステップＡ３１：ＹＥＳ）、暫定整理案作成処理の繰り返しを終了する。

一方、作成された暫定運用整理案が改善されていないと判断したならば（ステップＡ２５：ＮＯ）、所定のカウンタをカウントアップする（ステップＡ２７）。次いで、このカウンタ値と所定の閾値とを比較し、カウンタ値が閾値に達していないならば（ステップＡ２９：ＮＯ）、続いて、処理の打ち切り時間に達したかを判断する。処理の打ち切り時間に達していないならば（ステップＡ３１：ＮＯ）、ステップＡ１７に戻り、打ち切り時間に達しているならば（ステップＡ３１：ＹＥＳ）、暫定整理案作成処理の繰り返しを終了する。一方、カウンタ値が所定の閾値に達しているならば（ステップＡ２９：ＹＥＳ）、暫定整理案作成処理の繰り返しを終了する。

暫定整理案作成処理の繰り返しを終了した後は、蓄積記憶した暫定運用整理案を総合評価値とともに一覧表示し（ステップＡ３３）、これらのうちの何れかがユーザにより選択されたならば（ステップＡ３５：ＹＥＳ）、当該選択された暫定運用整理案の詳細表示を行う（ステップＡ３７）。以上の処理を行うと、運用整理案作成処理を終了する。

図２６は、行路候補設定処理の流れを説明するためのフローチャートである。同図によれば、ＣＰＵ１０は、運用整理の対象の車両毎に、ループＡの処理を繰り返す。

ループＡでは、先ず、運転整理案の運用整理対象期間のダイヤ部分に基づく列車ダイヤネットワークを生成する。このとき、対象車両に該当する発ノードＳＮ及び着ノードＥＮを設定する（ステップＢ１）。次いで、この列車ダイヤネットワークに実施可能な仕業検査ノードＴＮを追加して、運用整理基本ネットワークＢＭを生成する（ステップＢ３）。また、対象車両についての行路候補の検査数を「０」に初期設定する（ステップＢ５）。

続いて、仕業検査の検査周期と運用整理対象期間とを比較し、仕業検査周期が運用整理対象期間よりも短いならば（ステップＢ７：ＹＥＳ）、発ノードＳＮ及び仕業検査ノードＴＮそれぞれについて、到達可能ノード数ｎを、該当する仕業検査による検査期限条件を満たさない列車ノードＲＮ及び着ノードＥＮの数として設定する（ステップＢ９）。次いで、運用整理基本ネットワークＢＭに含まれる列車ノードＲＮ及び着ノードＥＮの総数Ｎを算出する（ステップＢ１１）。そして、この総数Ｎと発ノードＳＮの到達可能ノード数ｎとの差である（Ｎ−ｎ）個の複製ネットワークＣＭを生成し、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭするとともに、運用整理基本ネットワークＢＭに、発ノードＳＮの到達可能ノード数ｎに等しい「ｎ」のラベルを付け、複製ネットワークＣＭそれぞれに「ｎ＋１」〜「Ｎ」のラベルを付ける（ステップＢ１３）。

一方、仕業検査周期が運用整理対象期間以上ならば（ステップＢ７：ＮＯ）、発ノードＳＮ及び仕業検査ノードＴＮそれぞれについて、到達可能ノード数ｎを、該当する仕業検査による検査期限条件を満たす着ノードＥＮの数として設定する（ステップＢ１５）。次いで、運用整理基本ネットワークＢＭに含まれる着ノードＥＮの数Ｍを算出する（ステップＢ１７）。そして、この総数Ｍと発ノードの到達可能ノード数ｎとの差である（Ｍ−ｎ）個の複製ネットワークＣＭを生成し、運用整理基本ネットワークＢＭと合わせて拡張ネットワークＥＭとするとともに、運用整理基本ネットワークＢＭに、発ノードＳＮの到達可能ノード数ｎに等しい「ｎ」のラベルを付け、複製ネットワークＣＭそれぞれに「ｎ＋１」〜「Ｍ」のラベルを付ける（ステップＢ１９）。

拡張ネットワークを生成すると、ＣＰＵ１０は、続いて、この拡張ネットワークにおいて、各仕業検査ノードＴＮを元ノードとするアークを、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭの対応する先ノードに付け替える（ステップＢ２１）。

そして、この拡張ネットワークにおいて、運用整理基本ネットワークＢＭの発ノードＳＮから、何れかの着ノードＥＮに到達する経路を探索する経路探索処理を行う（ステップＢ２３）。このとき、仕業検査ノードＴＮを選択する毎に、該仕業検査ノードＴＮを元ノードとするアークの先ノードの複製ネットワークＣＭ（すなわち、該仕業検査ノードＴＮの到達可能ノード数ｎに等しいラベルの複製ネットワークＣＭ）において、該仕業検査ノードＴＮに該当する仕業検査による検査期限を満たさないノードに向かうアークを切断して、経路探索を行う。

この経路探索によって、新たな経路が探索されたならば（ステップＢ２５：ＹＥＳ）、検索された経路を、対象車両の行路候補に追加するとともに（ステップＢ２７）、検索数を「１」加算した値に更新する（ステップＢ２９）。続いて、探索数が所定数に達したかを判断し、所定数に達していないならば（ステップＢ３１：ＮＯ）、ステップＢ２３に戻り、再度、経路探索を行う。

一方、新たな経路が探索されない（ステップＢ２５：ＮＯ）、或いは、探索数が所定数に達したならば（ステップＢ３１：ＹＥＳ）、対象車両に対するループＡの処理を終了する。そして、運用整理の対象車両の全てについて、ループＡの処理を行って所定数の行路候補を算出すると、運用行路候補算出処理を終了する。

図２７は、運用整理案作成処理と並行して実行される割込み処理の流れを説明するためのフローチャートである。同図によれば、ＣＰＵ１０は、入力部２０から、ユーザによる実行中断指示が入力されたならば（ステップＣ１：ＹＥＳ）、実行中の運用整理案作成処理を一時中断する（ステップＣ３）。次いで、ユーザが評価基準を再設定するための評価基準再設定画面を表示部３０に表示させ、入力部２０から入力されるユーザの変更指示に従って、各評価指標の評価値を変更する（ステップＣ５）。そして、入力部２０から、ユーザによる再開指示が入力されたならば（ステップＣ７：ＹＥＳ）、各評価指標の評価値を変更された値に再設定する（ステップＣ９）。以上の処理を行うと、一時中断させている運用整理案作成処理を、ステップＡ１或いはＡ１９から再開させる。

［作用・効果］
このように、本実施形態によれば、暫定運用整理案の作成処理が繰り返し実行されるとともに、繰り返し毎に、各車両の運用行路候補が変更（追加）されてゆく。つまり、複数の暫定運用整理案が、逐次、作成・蓄積記憶され、これにより、限られた時間内で最適な車両運用整理案を得ることが可能となる。

また、暫定運用整理案が作成される毎に、直近に作成された暫定運用整理案と比較して改善されたか判定され、「改善されていない」と判定された回数が所定回数に達すると、暫定運用整理案の作成の繰り返しが終了する。これにより、暫定運用整理案の作成を繰り返しても、これ以上の改善が見込めないと判断される時点で、車両運用整理案の作成を終了することができる。

また、暫定運用整理案の作成処理においては、運転整理案に基づく列車ダイヤネットワークに仕業検査を表す仕業検査ノードＴＮを追加した運用整理基本ネットワークＢＭが生成され、この運用整理基本ネットワークＢＭに基づいて、各車両の行路候補が算出される。これにより、仕業検査を考慮した行路候補の算出が可能となる。

更に、運用整理基本ネットワークＢＭを用いた経路探索では、この運用整理基本ネットワークＢＭを複製した複数の複製ネットワークＣＭを生成し、各仕業検査ノードＴＮのアークの先ノードを、該仕業検査ノードＴＮの到達可能ノード数（該当する仕業検査の実施によって、検査期限条件が満たされるノードの数ｎ）に対応する複製ネットワークＣＭの対応する先ノードに変更している。つまり、仕業検査ノードＴＮのアークの変更によって検査期限の変更が表現されているとともに、変更した先ノードを含む複製ネットワークＣＭによって、変更した検査期限が表現されている。これにより、各複製ネットワークＣＭにおいて、列車ノードＲＮと仕業検査ノードＴＮとを区別することなく経路探索を行うことができ、従って、仕業検査を考慮した車両運用行路候補の探索が容易となる。

更に、評価基準をユーザが任意に設定することができるとともに、暫定運用整理案の作成中であっても、この作成処理を一時中断させて評価基準を再設定することができる。
これにより、ユーザが所望する評価指標を重要視した車両運用整理案の作成が可能となるとともに、重要視する評価指標を異ならせた複数の暫定運用整理案を作成し、これをユーザが見比べて所望の運用整理案を選択するといったことが可能となる。

［変形例］
なお、本発明の適用可能な実施形態は上述の実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で適宜変更可能なのは勿論である。

（Ａ）指標値
例えば、上述の実施形態では、指標値を「正の整数」としたが、これを「小数値」としても良いし、「負値」としても良い。負値とした場合、行路評価値が大きいほど、「良い」行路となる。従って、追加制約付き集合分割問題にモデル化したモデル式の解を算出する際には、行路評価値の総和Ｃが最大となる解を算出する。

（Ｂ）指標値を正規化
また、各評価指標の指標値を、他の指標値との相対的な値を表すように正規化して用いても良い。具体的には、各評価指標の指標値を、全ての評価指標の指標値の総和に対する比率に基づいて正規化し、この正規化した指標値をもとに、各行路候補の行路評価値を算出する。

（Ｃ）複製ネットワークＣＭの生成
また、上述の実施形態では、運用整理基本ネットワークＢＭを複製した複製ネットワークＣＭを、運用整理基本ネットワークＢＭに含まれる列車ノードＲＮ及び着ノードＥＮの数Ｎに応じた数だけ生成することとしたが、これを、運用整理基本ネットワークＢＭに含まれる仕業検査ノードＴＮの数の複製ネットワークＣＭを生成することとしても良い。

具体的には、図２８に示すように、仕業検査ノードＴＮの数Ｎに等しい数の複製ネットワークＣＭを生成し、生成した複製ネットワークＣＭそれぞれに、運用整理基本ネットワークＢＭに含まれる１つの仕業検査ノードＴＮを対応付ける。次いで、図２９に示すように、運用整理基本ネットワークＢＭの各仕業検査ノードＴＮのアークを、該当する複製ネットワークＣＭの対応する先ノードに付け替える。そして、各複製ネットワークＣＭにおいて、対応する仕業検査ノードＴＮに該当する仕業検査による検査期限条件を満たさないノードに至るアークを切断する。その後、運用整理基本ネットワークの発ノードＳＮから、何れかの着ノードＥＮに至る経路を探索する。つまり、１つの仕業検査ノードＴＮにつき１つの複製ネットワークＣＭが対応付けられているため、経路の探索中にアークを切断する必要がない。これにより、各ネットワークにおいて列車ノードＲＮと仕業検査ノードＴＮとを区別することなく経路探索を行うことができ、発ノードＳＮから着ノードＥＮに至る経路を容易に探索することが可能となる。

列車ダイヤの一例。 図１の列車ダイヤに対する行路候補の一例。 運転整理案の一例。 図３の運転整理案に対する列車ダイヤネットワークを示す図。 図３の運転整理案に対する運用整理基本ネットワークを示す図。 複製ネットワークの生成の説明図。 発ノードの到達可能ノード数の一例。 仕業検査ノードのアークの変更の説明図。 検査期限条件を満たす列車ノードの判定の説明図。 検査期限条件を満たす着ノードの判定の説明図。 仕業検査ノードの到達可能ノード数の一例。 仕業検査ノードの到達可能ノード数の一例。 仕業検査ノードの到達可能ノード数の一例。 アークの切断の説明図。 着ノードに向かうアークの切断の説明図。 仕業検査周期が運用整理対象期間より長い場合のアークの変更の説明図。 検査周期が運用整理対象期間より長い場合の拡張ネットワークの説明図。 評価基準設定画面の一例。 実行中画面の一例。 評価基準再設定画面の一例。 車両運用整理案作成装置の内部構成図。 評価基準データのデータ構成例。 行路候補データのデータ構成例。 暫定整理案データのデータ構成例。 運用整理案作成処理のフローチャート。 運用整理案作成処理中に実行される行路候補算出処理のフローチャート。 運用整理案作成処理と並行して実行される割込み処理のフローチャート。 複製ネットワークの生成にかかる別の実施例の説明図。 複製ネットワークの生成にかかる別の実施例の説明図。

符号の説明

１ 車両運用整理案作成装置
１０ ＣＰＵ、２０ 入力部、３０ 表示部、４０ 通信部
５０ 記憶部
５１０ 車両運用整理プログラム
５２１ 計画ダイヤデータ、５２２ 車両運用計画データ
５２３ 運転整理案データ
５２４ 評価基準データ、５２５ 行路候補データ
５２６ 車両運用整理案データ、５２７ 暫定整理案データ
ＳＮ 発ノード、ＥＮ 着ノード、ＲＮ 列車ノード、ＴＮ 仕業検査ノード
ＢＭ 運用整理基本ネットワーク、ＣＭ 複製ネットワーク、ＥＭ 拡張ネットワーク

Claims (11)

1. コンピュータに、所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成させるためのプログラムであって、
   前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段、
   前記運用整理基本ネットワークに含まれる所定ノードの総数に基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段、
   前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する手段であって、前記整理対象期間が車両検査の検査周期より長い場合に、前記運用整理基本ネットワークに含まれる列車ノード及び着ノードを前記所定ノードとして前記拡張ネットワークを生成する第１の拡張ネットワーク生成手段、
   前記第１の拡張ネットワーク生成手段により生成された拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードの検査により検査期限条件を満たす列車ノード及び着ノードのノード数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する第１のアーク変更手段、
   前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
   前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段、
   として前記コンピュータを機能させるためのプログラム。
2. コンピュータに、所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成させるためのプログラムであって、
   前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段、
   前記運用整理基本ネットワークに含まれる所定ノードの総数に基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段、
   前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する手段であって、前記整理対象期間が車両検査の検査周期以下の場合に、前記運用整理基本ネットワークに含まれる着ノードを前記所定ノードとして前記拡張ネットワークを生成する第２の拡張ネットワーク生成手段、
   前記第２の拡張ネットワーク生成手段により生成された拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードの検査により検査期限条件を満たす着ノードのノード数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する第２のアーク変更手段、
   前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
   前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段、
   として前記コンピュータを機能させるためのプログラム。
3. 前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する手段であって、前記整理対象期間が車両検査の検査周期以下の場合に、前記運用整理基本ネットワークに含まれる着ノードを前記所定ノードとして前記拡張ネットワークを生成する第２の拡張ネットワーク生成手段、
   前記第２の拡張ネットワーク生成手段により生成された拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードの検査により前記検査期限条件を満たす着ノードのノード数ｍを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｍに対応する複製ネットワーク中の対応する先ノードに変更する第２のアーク変更手段、
   として前記コンピュータを更に機能させるための請求項１に記載のプログラム。
4. コンピュータに、所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成させるためのプログラムであって、
   前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段、
   前記運用整理基本ネットワークを複製した複製ネットワークを、前記運用整理基本ネットワークに含まれる前記検査ノードの総数分生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段、
   前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段、
   前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
   前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段、
   として前記コンピュータを機能させるためのプログラム。
5. 各複製ネットワークにおいて、他のネットワークの検査ノードからのアークが変更・接続されることによる該検査ノードの検査によっても前記検査期限条件を満たすことのないノードに接続されたアークを切断するアーク切断手段として前記コンピュータを機能させるための請求項１〜４の何れか一項に記載のプログラム。
6. 前記列車ダイヤは前記整理対象期間を運転整理した運転整理ダイヤであり、
   前記運用整理案作成手段が、
   前記経路探索手段により探索された車両運用行路候補を組み合わせることによる暫定運用整理案を作成する暫定運用整理案作成手段と、
   前記暫定運用整理案に含まれる車両運用行路候補と運転整理前の車両運用行路との差異に基づいて前記暫定運用整理案を評価する評価手段と、
   を有し、前記暫定運用整理案作成手段及び前記評価手段を繰り返し実行させて最高評価の暫定運用整理案を前記運用整理案とする、
   ように前記コンピュータを機能させるための請求項１〜５の何れか一項に記載のプログラム。
7. 前記評価手段が、少なくとも、仕業切替に関する評価指標と、臨時検査の実施に関する評価指標とを含む複数の評価指標を用いて、前記暫定運用整理案に含まれる車両運用行路候補と運転整理前の車両運用行路との差異に基づく評価を行うように前記コンピュータを機能させるための請求項６に記載のプログラム。
8. 前記評価指標それぞれについての評価値をユーザの操作入力に従って可変する評価値可変手段として前記コンピュータを機能させ、
   前記評価手段が、前記可変された評価値に従って評価を行う、
   ように前記コンピュータを機能させるための請求項７に記載のプログラム。
9. 所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成する車両運用整理案作成装置であって、
   前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段と、
   前記運用整理基本ネットワークに含まれる所定ノードの総数Ｎに基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段と、
   前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する手段であって、前記整理対象期間が車両検査の検査周期より長い場合に、前記運用整理基本ネットワークに含まれる列車ノード及び着ノードを前記所定ノードとして前記拡張ネットワークを生成する第１の拡張ネットワーク生成手段と、
   前記第１の拡張ネットワーク生成手段により生成された拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードの検査により検査期限条件を満たす列車ノード及び着ノードのノード数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する第１のアーク変更手段と、
   前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
   前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段と、
   を備える車両運用整理案作成装置。
10. 所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成する車両運用整理案作成装置であって、
    前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段と、
    前記運用整理基本ネットワークに含まれる所定ノードの総数に基づいて、前記運用整理基本ネットワークを複製する複製数を決定する複製数決定手段と、
    前記運用整理基本ネットワークを複製した複製ネットワークを前記複製数生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する手段であって、前記整理対象期間が車両検査の検査周期以下の場合に、前記運用整理基本ネットワークに含まれる着ノードを前記所定ノードとして前記拡張ネットワークを生成する第２の拡張ネットワーク生成手段と、
    前記第２の拡張ネットワーク生成手段により生成された拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードの検査により検査期限条件を満たす着ノードのノード数ｎを算出し、当該検査ノードを元ノードとするアークの先ノードを、算出した数ｎに対応する複製ネットワーク中の対応する先ノードに変更する第２のアーク変更手段と、
    前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段、
    前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段と、
    を備える車両運用整理案作成装置。
11. 所定の列車ダイヤのうちの所与の整理対象期間の対象ダイヤに対する車両運用整理案を作成する車両運用整理案作成装置であって、
    前記対象ダイヤに基づいて、前記整理対象期間における各車両の発駅を表す発ノード、前記整理対象期間において何れかの車両が終着すべき駅の着ノード、前記整理対象期間の各列車を表す列車ノード、及び、車両検査可能な駅を着駅とする列車の当該着駅での車両検査を表す検査ノードを算出し、前記算出されたノードのち、前記対象ダイヤに基づいて接続可能なノード同士をアークにより結んで運用整理基本ネットワークを生成する基本ネットワーク生成手段と、
    前記運用整理基本ネットワークを複製した複製ネットワークを、前記運用整理基本ネットワークに含まれる前記検査ノードの総数分生成し、前記運用整理基本ネットワークと合わせた拡張ネットワークを生成する拡張ネットワーク生成手段と、
    前記拡張ネットワークに含まれる検査ノードそれぞれについて、当該検査ノードを元ノードとするアークの先ノードを、当該検査ノードに対応する複製ネットワーク中の対応する先ノードに変更するアーク変更手段と、
    前記運用整理基本ネットワークの発ノードから、前記拡張ネットワークの何れかの着ノードに至るアークの経路を車両運用行路候補として探索する経路探索手段と、
    前記経路探索手段により探索された車両運用行路候補を組み合わせて運用整理案を作成する運用整理案作成手段と、
    を備える車両運用整理案作成装置。

Images