(57)【特許請求の範囲】
【請求項１】
コンピュータに、所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求めさせるためのプログラムであって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、当該行路に含まれるアークに対する前記既約コストの総和が相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
コンピュータに、所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求めさせるためのプログラムであって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路において、同一の行路に含まれ得ないノードの集合を、クリークとして抽出するクリーク抽出手段、
前記抽出されたクリークに属するノードを含まない行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する前記抽出されたクリークに属するノードを含まない行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第１の相対コスト算出手段、
前記抽出されたクリークに属する各ノードについて、該ノードを含む行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する該ノードを含む行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第２の相対コスト算出手段、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、前記相対コストが相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段、
として前記コンピュータを機能させるためのプログラム。
【請求項３】
前記クリーク抽出手段が、単位乗務が密集している一の時刻にかかる単位乗務を表すノードの集合を前記クリークとして抽出するように前記コンピュータを機能させるための請求項２に記載のプログラム。
【請求項４】
前記行路案抽出手段が、前記各ノードそれぞれが所定回数以上出現することを条件に、行路案を篩い分けて抽出するように前記コンピュータを機能させるための請求項１〜３の何れか一項に記載のプログラム。
【請求項５】
前記完全マッチング算出手段が、求められた完全マッチングで表される行路の一部に、所定の違反条件を満たすノード間接続の組み合わせが含まれるか否かを判定する判定手段を有し、前記判定手段により含まれると判定された場合に、当該ノード間接続の組み合わせを構成する一のアークを削除して、完全マッチングと既約コストとを再度算出するように前記コンピュータを機能させるための請求項１〜４の何れか一項に記載のプログラム。
【請求項６】
所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求める乗務行路計画装置であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段と、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段と、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段と、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、当該行路に含まれるアークに対する前記既約コストの総和が相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段と、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段と、
を備えた乗務行路計画装置。
【請求項７】
所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求める乗務行路計画装置であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段と、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段と、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段と、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路において、同一の行路に含まれ得ないノードの集合を、クリークとして抽出するクリーク抽出手段と、
前記抽出されたクリークに属するノードを含まない行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する前記抽出されたクリークに属するノードを含まない行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第１の相対コスト算出手段と、
前記抽出されたクリークに属する各ノードについて、該ノードを含む行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する該ノードを含む行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第２の相対コスト算出手段と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、前記相対コストが相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段と、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段と、
を備えた乗務行路計画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータに、列車ダイヤに基づき、乗務可能な乗務区間の単位である単位乗務の遷移で構成される乗務員の行路を組み合わせて乗務行路計画を求めさせるためのプログラム等に関する。
【背景技術】
【０００２】
鉄道において、列車ダイヤの改正が行われた場合には、運転士や車掌等の乗務員の乗務の割り当てを計画しなければならない。この計画は、乗務行路計画と呼ばれ、乗務員がどのような順序で、どの駅からどの駅まで乗務するかを示す乗務行路（以下、単に「行路」と呼ぶ。）を決定する必要がある。
【０００３】
図５７は、列車ダイヤの一例を示す図であり、図５８は、図５７の列車ダイヤに対する乗務行路計画の一例を示す図である。図５７及び図５８は、横軸が時刻、縦軸が駅及び区所を示している。図５７では、列車の運行を表す「列車スジ」を傾斜線で示し、各列車スジには、対応する列車番号を表記している。また、図５８では、太実線で「行路」、太破線で「便乗」をそれぞれ示している。但し、「便乗」とは、乗務員が、他の乗務員が乗務する列車に乗って移動することを言う。
【０００４】
図５８の乗務行路計画は、３つの行路によって構成され、例えば第１の行路は、Ｂ駅で１列車に乗務することから始まり、最後に１３列車で再びＢ駅に戻って終了する行路である。尚、この計画では、１日に４人の乗務員が乗務に就くことになる。第１、第２、第３の行路に就く乗務員と、前日に第３の行路について同行路の２日目に就く乗務員との４人である。
【０００５】
この乗務行路計画は、列車ダイヤ改正の度に、長い日数と労力とをかけて手作業で行われているのが実状であり、昨今、コンピュータで乗務行路計画を求めることへの要請が強くなってきている。
【０００６】
乗務行路計画とは別に行われる計画として、列車ダイヤに基づいて各列車の車両の割り当てを決定する車両運用計画が存在し、この車両運用計画を求める手法が、例えば特許文献１に開示されている。
【特許文献１】特開２００５−２５９０５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、特許文献１に開示されているように、車両運用計画では、車両の交番検査や仕業検査等の制約条件を考慮する必要があるが、乗務行路計画では、この制約条件がより厳しいものとなる。
【０００８】
というのは、乗務行路計画は乗務員を対象とするため、（１）労働時間が基準値に近いか、（２）無駄な待ち時間が少ないか、（３）食事時間や睡眠時間が適切に確保されているか、（４）勤務開始・終了時刻が適切であるか、等の車両には無い特有の問題があるからである。このような制約条件の厳しさは、コンピュータで乗務行路計画を求めることを困難にしている一因であった。
【０００９】
また、１つの列車ダイヤについて考えられる行路の数は膨大であり、その膨大な数の行路の組み合わせは天文学的な数となるため、乗務行路計画に採用する行路の組み合わせを１つ１つ検討することは極めて困難であり、コンピュータ化の大きな障壁となっていた。
【００１０】
本発明はこのような課題に鑑みて為されたものであり、その目的とするところは、適切な乗務行路計画を求めることのできる装置等を実現することにある。
【課題を解決するための手段】
【００１１】
以上の課題を解決するための第１の発明は、
コンピュータに、所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求めさせるためのプログラム（例えば、図３７の第１の乗務行路計画プログラム５０１）であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段（例えば、図３８のステップＡ３）、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段（例えば、図３８のステップＡ５）、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段（例えば、図３７の乗務行路ネットワークデータ６０１）、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段（例えば、図３８のステップＡ７）、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、当該行路に含まれるアークに対する前記既約コストの総和が相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段（例えば、図３８のステップＡ９）、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段（例えば、図３８のステップＡ１１）、
として前記コンピュータを機能させるためのプログラムである。
【００１２】
また、第６の発明は、
所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求める乗務行路計画装置（例えば、図３７の乗務行路計画装置１０）であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段（例えば、図３７のＣＰＵ１００；図３８のステップＡ３）と、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段（例えば、図３７のＣＰＵ１００；図３８のステップＡ５）と、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段（例えば、図３７の乗務行路ネットワークデータ６０１）と、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段（例えば、図３７のＣＰＵ１００；図３８のステップＡ７）と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、当該行路に含まれるアークに対する前記既約コストの総和が相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段（例えば、図３７のＣＰＵ１００；図３８のステップＡ９）と、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段（例えば、図３７のＣＰＵ１００；図３８のステップＡ１１）と、
を備えた乗務行路計画装置である。
【００１３】
この第１又は第６の発明によれば、遷移可能な単位乗務同士のノード間をアークにより結んだ乗務行路ネットワークが生成され、乗務行路ネットワークの各アークに、所定の評価基準に基づいたコストが設定される。また、設定されたコストに基づいて、乗務行路ネットワーク全体における各アークそれぞれの価値が既約コストとして算出され、ノードの完全マッチングが算出される。そして、アークに従ったノード間接続の組み合わせで表される乗務員の行路のうち、その行路に含まれるアークの既約コストの総和が相対的に小さい所定数の行路が行路案として抽出され、この抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせが最適な乗務行路計画とされる。
【００１４】
既約コストは、個々のノード間接続で見た場合の各アークの評価値（言わば、局所的な評価値）ではなく、乗務行路ネットワーク全体で見た場合の各アークの評価値（言わば、大域的な評価値）であるため、既約コストの総和が小さい行路案は乗務行路計画に必要な行路案である可能性が高い。従って、上記抽出された行路案の中から行路案の組み合わせが探索されることで、適切な乗務行路計画が求められるようになる。
【００１５】
また、第２の発明は、
コンピュータに、所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求めさせるためのプログラム（例えば、図５１の第２の乗務行路計画プログラム５２１）であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段（例えば、図５３のステップＤ３）、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段（例えば、図５３のステップＤ５）、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段（例えば、図５２の乗務行路ネットワークデータ６０１）、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段（例えば、図５３のステップＤ７）、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路において、同一の行路に含まれ得ないノードの集合を、クリークとして抽出するクリーク抽出手段（例えば、図５３のステップＤ９）、
前記抽出されたクリークに属するノードを含まない行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する前記抽出されたクリークに属するノードを含まない行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第１の相対コスト算出手段（例えば、図５３のステップＤ１１、図５５のステップＦ３）、
前記抽出されたクリークに属する各ノードについて、該ノードを含む行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する該ノードを含む行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第２の相対コスト算出手段（例えば、図５３のステップＤ１１、図５５のステップＦ１１）、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、前記相対コストが相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段（例えば、図５３のステップＤ１３）、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段（例えば、図５３のステップＤ１５）、
として前記コンピュータを機能させるためのプログラムである。
【００１６】
また、第７の発明は、
所与の列車ダイヤに含まれる全ての列車スジを乗務員が乗務可能な乗務区間の単位である単位乗務に分割し、当該単位乗務間の遷移を組み合わせることにより乗務員の行路を構成し、当該構成された乗務員の行路を組み合わせることで、乗務行路計画を求める乗務行路計画装置（例えば、乗務行路計画装置２０）であって、
前記単位乗務を各々ノードによって表し、遷移可能な当該ノード間をアークにより結んだ乗務行路ネットワークを生成するネットワーク生成手段（例えば、ＣＰＵ１２０；図５３のステップＤ３）と、
前記生成された乗務行路ネットワークの各アークに対し、前記単位乗務間の遷移に関する所定の評価基準に基づいてコストを設定するコスト設定手段（例えば、ＣＰＵ１２０；図５３のステップＤ５）と、
前記生成された乗務行路ネットワークと、前記設定されたコストとを記憶する乗務行路ネットワークデータ記憶手段（例えば、図５２の乗務行路ネットワークデータ６０１）と、
前記記憶された乗務行路ネットワークの各ノードを遷移元及び遷移先とし、前記記憶された乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノードへ前記アークを結んだグラフを生成して、前記乗務行路ネットワークデータ記憶手段に記憶された前記アークに対する前記コストに基づいて、前記グラフにおける前記遷移元ノードから前記遷移先ノードへの前記コストの総和を最小にする最小コスト完全マッチングを算出すると共に、前記最小コスト完全マッチングによって算出される最小コストの行路における最終到達点から各ノードへの距離を表す前記ノードのポテンシャルと、前記アークで結ばれる２つのノードに係る前記ポテンシャル差に基づいて前記アークのコストを更新した値である既約コストとを算出する完全マッチング算出手段（例えば、ＣＰＵ１２０；図５３のステップＤ７）と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路において、同一の行路に含まれ得ないノードの集合を、クリークとして抽出するクリーク抽出手段（例えば、ＣＰＵ１２０；図５３のステップＤ９）と、
前記抽出されたクリークに属するノードを含まない行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する前記抽出されたクリークに属するノードを含まない行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第１の相対コスト算出手段（例えば、ＣＰＵ１２０；図５３のステップＤ１１、図５５のステップＦ３）と、
前記抽出されたクリークに属する各ノードについて、該ノードを含む行路のうち、当該行路に含まれるアークに対する既約コストの総和が最小の行路の該既約コストの総和に対する該ノードを含む行路それぞれに含まれるアークに対する既約コストの総和の相対コストを算出する第２の相対コスト算出手段（例えば、ＣＰＵ１２０；図５３のステップＤ１１、図５５のステップＦ１１）と、
前記アークに従った前記ノード間接続の組み合わせで表される乗務員の行路のうち、前記相対コストが相対的に小さい所定数の行路を行路案として抽出する行路案抽出手段（例えば、ＣＰＵ１２０；図５３のステップＤ１３）と、
前記抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせを最適な乗務行路計画とする乗務行路計画算出手段（例えば、ＣＰＵ１２０；図５３のステップＤ１５）と、
を備えた乗務行路計画装置である。
【００１７】
この第２又は第７の発明によれば、遷移可能な単位乗務同士のノード間をアークにより結んだ乗務行路ネットワークが生成され、乗務行路ネットワークの各アークに、所定の評価基準に基づいたコストが設定される。また、設定されたコストに基づいて、乗務行路ネットワーク全体における各アークそれぞれの価値が既約コストとして算出され、ノードの完全マッチングが算出される。そして、アークに従ったノード間接続の組み合わせで表される乗務員の行路の中からクリークとなるノードが抽出され、クリークに属するノードを含まない行路と、クリークに属するノードを含む行路とのそれぞれについて、既約コストに基づいて相対コストが算出される。そして、アークに従ったノード間接続の組み合わせで表される乗務員の行路のうち、相対コストが相対的に小さい所定数の行路が行路案として抽出され、この抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせを探索し、探索された当該行路案の組み合わせのうち、使用するアークに対する前記コストの総和が最小となる行路案の組み合わせが最適な乗務行路計画とされる。
【００１８】
クリークに属するノードは互いに同一の行路に含まれ得ないため、当該各ノードを含む行路案は必ず行路案の組み合わせに含まれなければならないが、相対コストは、行路全体から見た各行路の評価値（言わば、絶対的な評価値）ではなく、クリークに属するノード別に各行路を見た評価値（言わば、相対的な評価値）であるため、相対コストに基づいて行路案が抽出されることで、クリークに属するノードを含む行路が集中的に削除されることがない。また、相対コストは、既約コストに基づいて算出される評価値であるため、相対コストの小さい行路案は乗務行路計画に必要な行路案である可能性が高い。従って、上記抽出された行路案の中から行路案の組み合わせが探索されることで、適切な乗務行路計画が求められるようになる。
【００１９】
また、第３の発明は、第２の発明のプログラムであって、
前記クリーク抽出手段が、単位乗務が密集している一の時刻にかかる単位乗務を表すノードの集合を前記クリークとして抽出するように前記コンピュータを機能させるためのプログラムである。
【００２０】
この第３の発明によれば、単位乗務が密集している一の時刻にかかる単位乗務を表すノードの集合がクリークとして抽出されるようになる。
【００２１】
また、第４の発明は、第１〜第３の何れか一の発明のプログラムであって、
前記行路案抽出手段が、前記各ノードそれぞれが所定回数以上出現することを条件に、行路案を篩い分けて抽出するように前記コンピュータを機能させるためのプログラムである。
【００２２】
この第４の発明によれば、各ノードそれぞれが所定回数以上出現するように、行路案の篩い分けが行われる。各ノードそれぞれが所定回数以上出現すれば、特定のノードを含む行路案の数だけが極端に少なくなるといった事態の発生が防止されるため、乗務行路計画として成立し得る行路案の組み合わせが存在し易くなる。
【００２３】
また、第５の発明は、第１〜第４の何れか一の発明のプログラムであって、
前記完全マッチング算出手段が、求められた完全マッチングで表される行路の一部に、所定の違反条件を満たすノード間接続の組み合わせが含まれるか否かを判定する判定手段（例えば、図３８のステップＡ７、図３９のステップＢ７）を有し、前記判定手段により含まれると判定された場合に、当該ノード間接続の組み合わせを構成する一のアークを削除して、完全マッチングと既約コストとを再度算出する（例えば、図３９のステップＢ７；Ｙｅｓ→ステップＢ９→ステップＢ３）ように前記コンピュータを機能させるためのプログラムである。
【００２４】
この第５の発明によれば、完全マッチングで表される行路の一部に、所定の違反条件を満たすノード間接続の組み合わせが含まれる場合に、当該ノード間接続の組み合わせを構成する一のアークが削除されて、完全マッチングと既約コストとが再度算出されるようになる。
【発明の効果】
【００２５】
本発明によれば、乗務行路ネットワークに含まれる各アークの既約コストが算出され、アークに従ったノード間接続の組み合わせで表される乗務員の行路のうち、アークの既約コストの総和が相対的に小さい所定数の行路が行路案として抽出される。そして、使用するアークのコストの総和が最小となるように、抽出された行路案の中から乗務行路計画として成立し得る行路案の組み合わせが探索されて、乗務行路計画とされる。
【００２６】
既約コストは、個々のノード間接続で見た場合の各アークの評価値（言わば、局所的な評価値）ではなく、乗務行路ネットワーク全体で見た場合の各アークの評価値（言わば、大域的な評価値）であるため、既約コストの総和が小さい行路案は乗務行路計画に必要な行路案である可能性が高い。従って、上記抽出された行路案の中から行路案の組み合わせが探索されることで、適切な乗務行路計画が求められるようになる。
【発明を実施するための最良の形態】
【００２７】
１．第１実施形態
１−１．原理
先ず、第１実施形態における乗務行路計画の原理について説明する。
図１は、第１の乗務行路計画の流れを示すフローチャートである。
第１の乗務行路計画は、乗務行路ネットワーク生成（ステップＳ１）と、各アークの基礎コスト設定（ステップＳ３）と、最小コスト完全マッチング算出処理（ステップＳ５）と、第１の行路案抽出処理（ステップＳ７）と、集合分割解探索（ステップＳ９）との５つのステップにより実現される。以下、これら５つのステップについて、詳細に説明する。
【００２８】
１−１−１．乗務行路ネットワーク生成
先ず、与えられた列車ダイヤの全ての列車スジを乗務員が交代可能な駅間で区切り、その１つ１つの区間を「単位乗務」とする。例えば、図５７に示した列車ダイヤにおいて、Ａ駅〜Ｃ駅に向かう１列車を考えた場合、乗務員はＡ駅、Ｂ駅及びＣ駅で交代可能であるため、Ａ駅〜Ｂ駅までの区間と、Ｂ駅〜Ｃ駅までの区間とが、それぞれ単位乗務となる。但し、ここでは、乗務員は区所から１列車に乗務することはできないものとしている。
【００２９】
次いで、各単位乗務を「ノード」と呼ばれる点で表し、遷移可能な単位乗務同士のノード間を「アーク」と呼ばれる線で結んだ「乗務行路ネットワーク」を生成する。ここで、単位乗務同士が遷移可能であるとは、遷移元の単位乗務の到達駅と、遷移先の単位乗務の出発駅とが同一であることを言う。例えば、Ａ駅〜Ｂ駅を表す単位乗務から、Ｂ駅〜Ｃ駅を表す単位乗務への遷移は可能であるが、Ａ駅〜Ｂ駅を表す単位乗務から、Ｃ駅〜Ａ駅を表す単位乗務への遷移は不可能である。尚、乗務行路ネットワークでは、各アークを矢印で表し、矢印の方向にのみ単位乗務が遷移可能であることを示している。
【００３０】
１−１−２．各アークの基礎コスト設定
乗務行路ネットワークを生成したら、乗務行路ネットワークに含まれる各アークについて、予め定められた評価基準に基づいて基礎コストと呼ばれる評価値を設定する。基礎コストは、評価が高いほど値が小さくなるように設定する。例えば、ある単位乗務から別の単位乗務への遷移に要する時間（即ち、乗務員の待ち時間）を評価基準とした場合、業務効率の観点から見ると、遷移に要する時間は短い方が良いと言える。そこで、遷移に要する時間が短いアークほど、基礎コストを小さく設定する。尚、基礎コストを設定するための評価基準は上述したものに限られず、例えば、食事時間や睡眠時間の確保等にしても良く、適宜変更可能である。また、複数の評価基準に基づいて基礎コストを設定するようにしても良い。
【００３１】
図２は、各アークに基礎コストが設定された乗務行路ネットワークの一例を示す図である。同図において、「ａ」〜「ｆ」で表されるノードが、それぞれ単位乗務を表している。また、「Ｘ」及び「Ｙ」で表されるノードは、それぞれ乗務の開始及び終了を表しており、便宜的に使用する特殊なノード（以下、「ダミーノード」と呼ぶ。）である。以下、乗務は、必ずダミーノード「Ｘ」から開始してダミーノード「Ｙ」で終了するものとして説明する。また、ダミーノード「Ｘ」からダミーノード「Ｙ」に至るノード間の接続の組み合わせ（道筋）を「行路」と呼ぶことにし、例えば「Ｘ」→「ａ」→「ｆ」→「Ｙ」の道筋を、行路「ＸａｆＹ」で表す。
【００３２】
また、図２において、各アークに付された数値は、設定された基礎コストを示している。例えば、ノード「ａ」とノード「ｆ」とを結んだアークの基礎コストは「３０」であり、他のアークと比べて非常に大きな値となっていることから、ノード「ａ」を表す単位乗務から、ノード「ｆ」を表す単位乗務への遷移は、評価の低い遷移であると言える。
【００３３】
乗務行路計画は、上述した行路の組み合わせのうち、ダミーノードを除いた各ノードが１回ずつ出現するような組み合わせ（以下、この組み合わせを「集合分割解」と呼ぶ。）を探索することで実現される。なぜなら、全てのノードが１回ずつ出現していれば、全ての単位乗務に対して乗務員が割り当てられたことになるからである。
【００３４】
しかしながら、一般に、考えられる行路の数は膨大であるため、全ての行路についてその組み合わせを探索するのは極めて困難であり、コンピュータの処理能力を超える場合もある。そこで、乗務行路計画における必要性の高い行路のみが残存するように、行路の篩い分けを行うことを考えた。
【００３５】
この場合、何らかの評価基準に基づいて、各行路の乗務行路計画における必要性を判断する必要がある。そこで、各アークに設定された基礎コストに着目すると、基礎コストは、個々のノード間の接続にのみ着目した評価値であるが、各行路の乗務行路計画における必要性を評価するために好適な評価値であるとは一概に言えない。というのは、例えばアークの基礎コストの総和が小さくなるような行路のみが残存するように行路の篩い分けを行うと、どうしても特定のノードを含んだ行路ばかりが残存するようになり、集合分割解が存在しなくなる恐れがあるからである。
【００３６】
そこで、各行路の乗務行路計画における必要性を評価するために、乗務行路ネットワーク全体で見たときの各アークの価値を表す「既約コスト」と呼ぶ概念を導入することにした。既約コストは、基礎コストと同様に値が小さいほど評価が高いことを表す評価値である。この既約コストは、ダミーノードを除いた各ノードについて、他の何れかのノードに向かって必ず１本のアークが出ており、また、他の何れかのノードから必ず１本のアークが入ってくるようなノードの組み合わせ（以下、この組み合わせのことを「完全マッチング」と呼ぶ。）であって、基礎コストの総和を最小にする完全マッチングである「最小コスト完全マッチング」を算出することで求めることができる。
【００３７】
１−１−３．最小コスト完全マッチング算出処理
次に、図３〜図２９を参照して、最小コスト完全マッチングを算出する方法について詳細に説明する。ここでは、図２の乗務行路ネットワークに対する最小コスト完全マッチングを算出する場合を例に挙げて説明する。
【００３８】
最初に、図２の乗務行路ネットワークを書き換えた「遷移正規化図」を生成する。具体的には、遷移元の単位乗務を表すノードとしてノード「ａ」〜「ｆ」を一列に配置し、その対極に遷移先の単位乗務を表すノードとしてノード「ａ」〜「ｆ」を一列に配置する。即ち、ノード「ａ」〜「ｆ」については、遷移元と遷移先とを区別して、２つずつノードが配置されることになる。以下、遷移元の単位乗務を表すノードを「遷移元ノード」、遷移先の単位乗務を表すノードを「遷移先ノード」とそれぞれ呼ぶことにする。
【００３９】
また、遷移元ノードと遷移先ノードとの中間位置に、ダミーノード「Ｘ」及び「Ｙ」を配置する。そして、図２の乗務行路ネットワークと等価になるように、遷移元ノードから遷移先ノード又はダミーノードに対し、また、ダミーノードから遷移先ノードに対して、基礎コストが設定されたアークを結ぶ。生成された遷移正規化図を、図３に示す。
【００４０】
但し、図３では、遷移元ノードと遷移先ノードとを区別するため、遷移元ノードは「ａ1」〜「ｆ1」で表し、遷移先ノードは「ａ2」〜「ｆ2」で表している。また、図を見易くするために、ダミーノード「Ｘ」及び「Ｙ」をまとめてダミーノード「Ｘ／Ｙ」で表し、遷移元ノード「ａ1」〜「ｆ1」の並び順と、遷移先ノード「ａ2」〜「ｆ2」の並び順とを逆にしている。
【００４１】
各アークに設定された基礎コストは、最小コスト完全マッチング算出の過程において、「既約コスト」として随時更新されていく。即ち、基礎コストは、既約コストの初期値となる。
【００４２】
また、全てのノードについて、「距離ラベル」と「ノードポテンシャル」とを設定する。距離ラベルは、あるノードを出発点とした場合に（以下、「出発ノード」と呼ぶ。）、出発ノードから当該ノードまでを結ぶアークの、現在把握している既約コストの総和である。距離ラベルは、初期値として「∞（無限大）」が設定され、新たに算出された値が既に設定されている値よりも小さい場合に、この新たに算出された値で更新される。以下、ノード「ｉ」の距離ラベルを、ｄ（ｉ）で表すことにする。
【００４３】
ノードポテンシャルは、各ノードが持つ内在的なエネルギーであって、既約コストを算出するための作業用の変数として機能する。ノードポテンシャルは、初期値として「０」が設定され、距離ラベルが確定したノードについてのみ、その値が更新される。
【００４４】
具体的には、ノード「ｉ」におけるノードポテンシャルを「π（ｉ）」で表すことにすると、π（ｉ）は式（１）に従って更新される。
π（ｉ）←π（ｉ）−ｄ（ｉ）＋ｄ（Ｒ）    ・・・（１）
但し、ｄ（Ｒ）は、出発ノードから最終的に到達したノード（以下、「最終到達ノード」と呼ぶ。）までを結ぶアークの既約コストの総和である。即ち、最終到達ノードの距離ラベルがｄ（Ｒ）となる。
【００４５】
式（１）によると、ノードポテンシャルは、対象となるノードの距離ラベルと、最終到達ノードの距離ラベルとの相対的な関係によって決まり、２つの距離ラベルの差が大きいほど、更新される量は大きくなる。
【００４６】
各アークの既約コストは、当該アークで結ばれる２つのノードのうちの一方又は両方のノードポテンシャルが更新されることで、その値が更新される。具体的には、ノード「ｉ」からノード「ｊ」に向かって結ばれたアークの既約コストを「ｗ（ｉｊ）」で表すことにすると、ｗ（ｉｊ）は式（２）に従って更新される。
ｗ（ｉｊ）←ｗ（ｉｊ）−π（ｉ）＋π（ｊ）    ・・・（２）
【００４７】
式（２）によると、既約コストは、対象となるアークで結ばれる２つのノードのノードポテンシャルの相対的な関係によって決まり、２つのノードポテンシャルの差が大きいほど、更新される量は大きくなる。
【００４８】
距離ラベルとノードポテンシャルとの設定を行ったら、各遷移元ノードを出発ノードとして、最小の既約コストで到達可能な遷移先ノードの探索を行う。そして、探索された遷移先ノードを最終到達ノードに確定し、ノードポテンシャル及び既約コストを、式（１）及び式（２）に従って更新する。
【００４９】
以下、最終到達ノードの探索方法について説明するが、各出発ノード１つ１つに関する処理を順次行い、出発ノード１つに関する処理を「ターン」と呼び、この１つのターンにおいて値が確定した距離ラベル、ノードポテンシャル及び既約コストを、図中ではグレーの塗り潰しで表現する。また、距離ラベルが現在確定しているノードまでのアークを太矢印で表現する。
【００５０】
（Ａ）遷移元ノード「ａ1」を出発ノードとした場合
先ず、遷移元ノード「ａ1」を出発ノードとすると、遷移元ノード「ａ1」が自身に到達するまでの既約コストは「０」であるため、遷移元ノード「ａ1」の距離ラベルを「∞」から「０」に更新する。遷移元ノード「ａ1」の距離ラベルがこれよりも小さくなることはないため、遷移元ノード「ａ1」の距離ラベルは「０」に確定する（図４参照）。
【００５１】
次いで、遷移元ノード「ａ1」から到達可能な遷移先ノードは、遷移先ノード「ｆ2」又は遷移先ノード「ｃ2」であるが、遷移先ノード「ｆ2」に到達するまでの既約コストは「３０」であり、遷移先ノード「ｃ2」に到達するまでの既約コストは「１」である。
【００５２】
この場合、遷移先ノード「ｆ2」の距離ラベルは「３０」、遷移先ノード「ｃ2」の距離ラベルは「１」にそれぞれ更新されるが、遷移先ノード「ｃ2」には、遷移先ノード「ｆ2」よりも小さい既約コストで到達することが可能である。従って、遷移先ノード「ｃ2」の距離ラベルを「１」に確定する。また、遷移先ノード「ｃ2」から他に到達できるノードは存在しないため、遷移先ノード「ｃ2」を最終到達ノードに確定する（図５参照）。
【００５３】
ここまでの手順により、遷移元ノード「ａ1」及び遷移先ノード「ｃ2」の距離ラベルが確定したことになる。従って、遷移元ノード「ａ1」のノードポテンシャル「π（ａ1）」と、遷移先ノード「ｃ2」のノードポテンシャル「π（ｃ2）」とを、式（１）に従って更新する。
【００５４】
具体的には、ノードポテンシャル「π（ａ1）」は、現在の値が「π（ａ1）＝０」、遷移元ノード「ａ1」の距離ラベルが「ｄ（ａ1）＝０」、最終到達ノードの距離ラベルが「ｄ（Ｒ）＝ｄ（ｃ2）＝１」であるため、「π（ａ1）−ｄ（ａ1）＋ｄ（Ｒ）＝１」に更新する。同様に、ノードポテンシャル「π（ｃ2）」は、現在の値が「π（ｃ2）＝０」、遷移先ノード「ｃ2」の距離ラベルが「ｄ（ｃ2）＝１」、最終到達ノードの距離ラベルが「ｄ（Ｒ）＝ｄ（ｃ2）＝１」であるため、「π（ｃ2）−ｄ（ｃ2）＋ｄ（Ｒ）＝０」に更新する。
【００５５】
また、ノードポテンシャル「π（ａ1）」及び「π（ｃ2）」を更新したため、遷移元ノード「ａ1」から遷移先ノード「ｆ2」に向かうアークの既約コストｗ（ａ1ｆ2）と、遷移元ノード「ａ1」から遷移先ノード「ｃ2」に向かうアークの既約コストｗ（ａ1ｃ2）とを、式（２）に従って更新する。
【００５６】
具体的には、既約コスト「ｗ（ａ1ｆ2）」は、現在の値が「ｗ（ａ1ｆ2）＝３０」、遷移元ノード「ａ1」のノードポテンシャルが「π（ａ1）＝１」、遷移先ノード「ｆ2」のノードポテンシャルが「π（ｆ2）＝０」であるため、「ｗ（ａ1ｆ2）−π（ａ1）＋π（ｆ2）＝２９」に更新する。同様に、既約コスト「ｗ（ａ1ｃ2）」は、現在の値が「ｗ（ａ1ｃ2）＝１」、遷移元ノード「ａ1」のノードポテンシャルが「π（ａ1）＝１」、遷移先ノード「ｃ2」のノードポテンシャルが「π（ｃ2）＝０」であるため、「ｗ（ａ1ｃ2）−π（ａ1）＋π（ｃ2）＝０」に更新する。
【００５７】
ここまでで、遷移元ノード「ａ1」を出発ノードとした場合のターンは終了となるが、遷移先ノード「ｃ2」を最終到達ノードに確定したという意味で、遷移元ノード「ａ1」から遷移先ノード「ｃ2」に向かうアークの向きを反転させる（図６参照）。尚、遷移元ノード「ａ1」から遷移先ノード「ｃ2」に向かうアークの既約コストが「０」であるため分かりづらいが、アークの向きを反転させることで既約コストの符号も反転する。
【００５８】
（Ｂ）遷移元ノード「ｂ1」を出発ノードとした場合
次に、遷移元ノード「ｂ1」を出発ノードとする。先ず、全てのノードの距離ラベルを「∞」に初期化する。
その後、遷移元ノード「ｂ1」が自身に到達するまでの既約コストは「０」であるため、遷移元ノード「ｂ1」の距離ラベルを「∞」から「０」に更新して確定する（図７参照）。
【００５９】
次いで、遷移元ノード「ｂ1」から到達可能な遷移先ノードは、遷移先ノード「ｅ2」又は遷移先ノード「ｃ2」であるが、遷移先ノード「ｅ2」に到達するまでの既約コストは「１０」であり、遷移先ノード「ｃ2」に到達するまでの既約コストは「５」である。
【００６０】
この場合、遷移先ノード「ｅ2」の距離ラベルは「１０」、遷移先ノード「ｃ2」の距離ラベルは「５」にそれぞれ更新されるが、遷移先ノード「ｃ2」には、遷移先ノード「ｅ2」よりも小さい既約コストで到達することが可能である。従って、遷移先ノード「ｃ2」の距離ラベルを「５」に確定する（図８参照）。
【００６１】
遷移先ノード「ｃ2」は、遷移元ノード「ａ1」の最終到達ノードとして確定しているため、遷移先ノード「ｃ2」を遷移元ノード「ｂ1」の最終到達ノードに確定することはできない。しかし、アークの反転により、遷移先ノード「ｃ2」から遷移元ノード「ａ1」への遷移が可能となったため、遷移元ノード「ｂ1」から、遷移先ノード「ｃ2」及び遷移元ノード「ａ1」を介して遷移先ノード「ｆ2」に到達することは可能である。
【００６２】
今、遷移元ノード「ｂ1」から遷移元ノード「ａ1」に到達するまでの既約コストは「５＋０＝５」であり、遷移元ノード「ｂ1」から遷移先ノード「ｅ2」に到達するまでの既約コスト「１０」よりも小さいため、遷移元ノード「ａ1」の距離ラベルを「５」に確定する（図９参照）。
【００６３】
次いで、遷移元ノード「ｂ1」から遷移先ノード「ｆ2」に到達するまでの既約コストを考えると「５＋０＋２９＝３４」であるが、遷移元ノード「ｂ1」から遷移先ノード「ｅ2」に到達するまでの既約コストは「１０」であるため、遷移先ノード「ｅ2」には、遷移先ノード「ｆ2」よりも小さい既約コストで到達することが可能である。従って、遷移先ノード「ｅ2」の距離ラベルを「１０」に確定する。また、遷移先ノード「ｅ2」から他に到達できるノードは存在しないため、遷移先ノード「ｅ2」を最終到達ノードに確定する（図１０参照）。
【００６４】
ここまでの手順により、遷移元ノード「ａ1」、遷移元ノード「ｂ1」、遷移先ノード「ｃ2」及び遷移先ノード「ｅ2」の距離ラベルが確定したことになるため、それぞれのノードポテンシャルを、式（１）に従って更新する。
【００６５】
具体的には、ノードポテンシャル「π（ａ1）」は、「π（ａ1）−ｄ（ａ1）＋ｄ（Ｒ）＝６」に更新し、ノードポテンシャル「π（ｂ1）」は、「π（ｂ1）−ｄ（ｂ1）＋ｄ（Ｒ）＝１０」に更新する。また、ノードポテンシャル「π（ｃ2）」は、「π（ｃ2）−ｄ（ｃ2）＋ｄ（Ｒ）＝５」に更新し、ノードポテンシャル「π（ｅ2）」は、「π（ｅ2）−ｄ（ｅ2）＋ｄ（Ｒ）＝０」に更新する。但し、ｄ（Ｒ）＝ｄ（ｅ2）＝１０である。
【００６６】
また、関係する既約コストを更新すると、既約コスト「ｗ（ｂ1ｅ2）」は、「ｗ（ｂ1ｅ2）−π（ｂ1）＋π（ｅ2）＝０」に更新され、既約コスト「ｗ（ｂ1ｃ2）」は、「ｗ（ｂ1ｃ2）−π（ｂ1）＋π（ｃ2）＝０」に更新される。また、既約コスト「ｗ（ａ1ｆ2）」は、「ｗ（ａ1ｆ2）−π（ａ1）＋π（ｆ2）＝２４」に更新され、既約コスト「ｗ（Ｘ／Ｙｃ2）」は、「ｗ（Ｘ／Ｙｃ2）−π（Ｘ／Ｙ）＋π（ｃ2）＝６」に更新される。
【００６７】
ここまでで、遷移元ノード「ｂ1」を出発ノードとした場合のターンは終了となるため、遷移元ノード「ｂ1」から遷移先ノード「ｅ2」に向かうアークを反転させる（図１１参照）。
【００６８】
（Ｃ）遷移元ノード「ｃ1」を出発ノードとした場合
遷移元ノード「ｃ1」を出発ノードとした場合も同様であり、先ず全てのノードの距離ラベルを「∞」に初期化した後、遷移元ノード「ｃ1」の距離ラベルを「０」に確定する（図１２参照）。
【００６９】
次いで、遷移先ノード「ｄ2」に到達するまでの既約コストが「１」で最も小さいため、遷移先ノード「ｄ2」の距離ラベルを「１」に確定して、遷移先ノード「ｄ2」を最終到達ノードに確定する（図１３参照）。尚、既約コスト「ｗ（ｃ1ｄ2）＝ｗ（ｃ1ｆ2）＝１」であるため、遷移先ノード「ｆ2」を最終到達ノードに確定しても良いが、ここでは遷移先ノード「ｄ2」の方を選択したものとして説明する。
【００７０】
そして、距離ラベルが確定した遷移元ノード「ｃ1」及び遷移先ノード「ｄ2」についてノードポテンシャルを更新し、関係する既約コストを更新する。また、ここまでで遷移元ノード「ｃ1」を出発ノードとした場合のターンは終了となるため、遷移元ノード「ｃ1」から遷移先ノード「ｄ2」に向かうアークを反転させる（図１４参照）。
【００７１】
（Ｄ）遷移元ノード「ｄ1」を出発ノードとした場合
遷移元ノード「ｄ1」を出発ノードとした場合も同様であり、先ず全てのノードの距離ラベルを「∞」に初期化した後、遷移元ノード「ｄ1」の距離ラベルを「０」に確定する（図１５参照）。
【００７２】
次いで、ダミーノード「Ｘ／Ｙ」の距離ラベルを「１」に確定する（図１６参照）。そして、遷移先ノード「ｂ2」に到達するまでの既約コストが「１＋５＝６」で最も小さいため、遷移先ノード「ｂ2」の距離ラベルを「６」に確定して、遷移先ノード「ｂ2」を最終到達ノードに確定する（図１７参照）。尚、既約コスト「ｗ（Ｘ／Ｙｂ2）＝ｗ（Ｘ／Ｙａ2）＝５」であるため、遷移先ノード「ａ2」を最終到達ノードに確定しても良いが、ここでは遷移先ノード「ｂ2」の方を選択したものとして説明する。
【００７３】
そして、距離ラベルが確定した遷移元ノード「ｄ1」、ダミーノード「Ｘ／Ｙ」及び遷移先ノード「ｂ2」についてノードポテンシャルを更新し、関係する既約コストを更新する。また、ここまでで遷移元ノード「ｄ1」を出発ノードとした場合のターンは終了となるため、遷移元ノード「ｄ1」からダミーノード「Ｘ／Ｙ」に向かうアークと、ダミーノード「Ｘ／Ｙ」から遷移先ノード「ｂ2」に向かうアークとをそれぞれ反転させる（図１８参照）。
【００７４】
（Ｅ）遷移元ノード「ｅ1」を出発ノードとした場合
遷移元ノード「ｅ1」を出発ノードとした場合も同様であり、先ず全てのノードの距離ラベルを「∞」に初期化した後、遷移元ノード「ｅ1」の距離ラベルを「０」に確定する（図１９参照）。
【００７５】
次いで、遷移先ノード「ｄ2」に到達するまでの既約コスト「５」の方が、ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１５」よりも小さいので、遷移先ノード「ｄ2」の距離ラベルを「５」に確定する（図２０参照）。
【００７６】
また、遷移先ノード「ｄ2」を介して遷移元ノード「ｃ1」に到達するまでの既約コスト「５＋０＝５」の方が、ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１５」よりも小さいので、遷移元ノード「ｃ1」の距離ラベルを「５」に確定する（図２１参照）。
【００７７】
そして、遷移先ノード「ｄ2」及び遷移元ノード「ｃ1」を介して遷移先ノード「ｆ2」に到達するまでの既約コスト「５＋０＋０＝５」の方が、ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１５」よりも小さいので、遷移先ノード「ｆ2」の距離ラベルを「５」に確定し、遷移先ノード「ｆ2」を最終到達ノードに確定する（図２２参照）。
【００７８】
そして、距離ラベルが確定した遷移元ノード「ｅ1」、遷移元ノード「ｃ1」、遷移先ノード「ｄ2」及び遷移先ノード「ｆ2」についてノードポテンシャルを更新し、関係する既約コストを更新する。また、ここまでで遷移元ノード「ｅ1」を出発ノードとした場合のターンは終了となるため、遷移元ノード「ｅ1」から遷移先ノード「ｄ2」に向かうアークと、遷移先ノード「ｄ2」から遷移元ノード「ｃ1」に向かうアークと、遷移元ノード「ｃ1」から遷移先ノード「ｆ2」に向かうアークとをそれぞれ反転させる（図２３参照）。
【００７９】
（Ｆ）遷移元ノード「ｆ1」を出発ノードとした場合
遷移元ノード「ｆ1」を出発ノードとした場合も同様であり、先ず全てのノードの距離ラベルを「∞」に初期化した後、遷移元ノード「ｆ1」の距離ラベルを「０」に確定する（図２４参照）。
【００８０】
次いで、遷移先ノード「ｄ2」に到達するまでの既約コスト「１」の方が、ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１０」よりも小さいので、遷移先ノード「ｄ2」の距離ラベルを「１」に確定する（図２５参照）。
【００８１】
また、遷移先ノード「ｄ2」を介して遷移元ノード「ｅ1」に到達するまでの既約コスト「１＋０＝１」の方が、ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１０」よりも小さいので、遷移元ノード「ｅ1」の距離ラベルを「１」に確定する（図２６参照）。
【００８２】
そして、遷移先ノード「ｄ2」及び遷移元ノード「ｅ1」を介してダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１＋０＋１０＝１１」と、遷移元ノード「ｆ1」から直接ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１０」とを比較すると、直接ダミーノード「Ｘ／Ｙ」に到達するまでの既約コスト「１０」の方が小さいので、ダミーノード「Ｘ／Ｙ」の距離ラベルを「１０」に確定する（図２７参照）。
【００８３】
次いで、ダミーノード「Ｘ／Ｙ」を介して遷移先ノード「ａ2」に到達するまでの既約コストが「１０＋０＝１０」で最も小さいため、遷移先ノード「ａ2」の距離ラベルを「１０」に確定して、遷移先ノード「ａ2」を最終到達ノードに確定する（図２８参照）。
【００８４】
そして、距離ラベルが確定した遷移元ノード「ｆ1」、遷移元ノード「ｅ1」、遷移先ノード「ｄ2」、遷移先ノード「ａ2」及びダミーノード「Ｘ／Ｙ」についてノードポテンシャルを更新し、関係する既約コストを更新する。また、ここまでで遷移元ノード「ｆ1」を出発ノードとした場合のターンは終了となるため、遷移元ノード「ｆ1」からダミーノード「Ｘ／Ｙ」に向かうアークと、ダミーノード「Ｘ／Ｙ」から遷移先ノード「ａ2」に向かうアークとをそれぞれ反転させる（図２９参照）。
【００８５】
以上、全ての遷移元ノードを出発ノードとした場合について、最小の既約コストで到達可能な遷移先ノードの探索を行った。この探索により得られた出発ノードと最終到達ノードとの対応関係は、最小コスト完全マッチングになっている。
【００８６】
今、最小コスト完全マッチングが算出された遷移正規化図をネットワーク形式に書き換えた図を「マッチング後ネットワーク」と呼ぶことにする。図２９の遷移正規化図に対するマッチング後ネットワークを、図３０に示す。
【００８７】
図３０では、最小コスト完全マッチングを太矢印で示している。これを見ると、確かにダミーノードを除いた全てのノードについて、他の何れかのノードに向かって必ず１本のアークが出ており、また、他の何れかのノードから必ず１本のアークが入ってくるようなノードの組み合わせが得られている。
【００８８】
尚、最小コスト完全マッチングに属する行路（即ち、矢印を辿ることで得られる行路）には、１継続乗務時間を違反する経路（以下、「１継続乗務時間違反経路」と呼ぶ。）が含まれている場合がある。ここで、１継続乗務時間とは、予め定められた乗務員が継続して乗務を行っても良い時間のことを指し、例えば「３時間」と決められている。また、経路とは、行路中のあるノードから別のノードまでの道筋のことを指す。この１継続乗務時間違反経路を含む行路に、乗務員を割り当てることはできない。
【００８９】
そこで、最小コスト完全マッチングに属する行路に１継続乗務時間違反経路が含まれる場合は、当該経路上のアークを１つ削除する。アークを１つ削除すれば、当該アークで結ばれるノードを表す単位乗務間の遷移が不可能となり、当該経路の１継続乗務時間違反が解消されるからである。そして、最小コスト完全マッチングの算出を再度行うようにする。
【００９０】
１−１−４．第１の行路案抽出処理
最小コスト完全マッチング算出処理により、各アークについて既約コストが求められたことになる。既約コストは、乗務行路ネットワーク全体における各アークの価値を表しているため、この既約コストに基づいて行路の篩い分けを行えば、乗務行路計画における必要性の高い行路のみを残存させることができるようになる。
【００９１】
そこで、第１の行路案抽出処理では、以下の手順で行路の篩い分けを行う。
先ず、マッチング後ネットワークから行路を１つずつ選択していき、ダミーノードを除いた各ノードについて、その出現した回数（以下、「出現回数」と呼ぶ。）をカウントする。そして、出現回数のうち最小のもの（以下、「最小出現回数」と呼ぶ。）が所定の閾値θを超えるまで（最小出現回数＞閾値θとなるまで）、行路を選択していく。尚、行路を選択する順序は、予め設定された順序としても良いし、ランダムとしても良い。
【００９２】
そして、最小出現回数が閾値θを超えた段階で、既に選択済みの行路のうち、行路に含まれるアークの既約コストの総和（以下、「合計既約コスト」と呼ぶ。）が最大の行路を１つ削除し、マッチング後ネットワークから他の行路を新しく選択する。そして、選択可能な行路が無くなるまで、この手順を繰り返し実行する。
【００９３】
マッチング後ネットワークから選択可能な行路が無くなったら、出現回数＞閾値θの条件を満たすノードのみを含んだ行路があるか否かを判定し、有ると判定した場合は、当該行路のうち合計既約コストが最大の行路を１つ削除する。そして、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が無くなるまでこの手順を繰り返し実行し、無くなった時点で、行路の篩い分けを終了する。
【００９４】
この第１の行路案抽出処理による行路の篩い分けを、図３０のマッチング後ネットワークに含まれる行路について行った場合を例に挙げて説明する。但し、ここでは、閾値θを「３」として行路の篩い分けを行った場合について説明する。
【００９５】
図３１〜図３４は、第１の行路案抽出処理において行路の篩い分けを行う際に用いるデータである第１の行路案データ６０７を示す図である。
第１の行路案データ６０７には、行路６０７１と、合計既約コスト６０７３と、ノード６０７５とが対応付けて記憶され、ノード６０７５を構成する各ノードについて、出現回数６０７７が記憶される。
【００９６】
行路６０７１は、マッチング後ネットワークから選択された行路であり、合計既約コスト６０７３は、当該行路の合計既約コストである。ノード６０７５は、マッチング後ネットワークに含まれるダミーノードを除いた各ノードで構成され、選択された行路に当該ノードが含まれる場合に、「マル」が設定される。出現回数６０７７は、ノード６０７５を構成する各ノードの出現回数を示しており、各ノードに設定された「マル」の数の合計が記憶される。
【００９７】
図３１は、図３０のマッチング後ネットワークに含まれる行路をランダムに選択していき、ノード６０７５の最小出現回数が閾値θを越えた場合の第１の行路案データ６０７を示す図である。行路「ＸｂｅｄＹ」が選択されたことで、ノード「ｂ」、「ｄ」及び「ｅ」の出現回数が更新されてノードの最小出現回数が「４」となり、閾値である「θ＝３」を超えた状態が示されている。
【００９８】
図３２は、図３１の状態の後、合計既約コストが最大の行路が１つ削除され、新たに別の行路が選択された場合の第１の行路案データ６０７を示す図である。図３１においてノードの最小出現回数が「４」となり、閾値である「θ＝３」を超えたことで、合計既約コストが最大の行路である行路「ＸｃｄＹ」が削除され、マッチング後ネットワークから新たに行路「ＸａｃｅＹ」が選択されている。また、これに伴って、出現回数６０７７が更新されている。
【００９９】
図３３は、図３２の手順が繰り返し実行され、マッチング後ネットワークから選択できる行路が無くなった場合の第１の行路案データ６０７を示す図である。また、図３４は、図３３の状態の後、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が１つ削除された場合の第１の行路案データ６０７を示す図である。
【０１００】
マッチング後ネットワークから選択できる行路が無くなったことで、出現回数＞閾値θの条件を満たすノードのみを含んだ行路のうち、合計既約コストが最大の行路が１つ削除される。図３３において、出現回数＞閾値θの条件を満たすノードは「ａ」以外のノードであり、ノード「ａ」を含まない行路のうち、合計既約コストが最大の行路である行路「ＸｃｅｄＹ」が削除された状態が、図３４に示されている。尚、ここでは、行路「ＸｃｅｄＹ」が削除されることとしたが、合計既約コストが同様に最大の行路である行路「ＸｂｃｅＹ」が削除されることとしても勿論良い。
【０１０１】
図３５は、図３４の手順が繰り返され、行路の篩い分けが終了した状態における第１の行路案データ６０７を示す図である。出現回数＞閾値θの条件を満たすノードのみを含んだ行路のうち、合計既約コストが最大の行路を削除する手順が繰り返し実行され、最終的に６つの行路が残存した状態が示されている。
【０１０２】
１−１−５．集合分割解探索
第１の行路案抽出処理により、既約コストに基づいた行路の篩い分けが行われたことになる。後は、残存した行路の中から集合分割解を探索し、探索した集合分割解を乗務行路計画とすれば良い。ここで、乗務行路計画の最適解となるのは、アークに設定された基礎コストの総和が最小となるような行路の組み合わせである。基礎コストは、ノード間の接続に着目したアークの評価値であるため、基礎コストの小さいアークが含まれる行路ほど、評価の高い行路であると言えるからである。
【０１０３】
図３６は、図３５の第１の行路案データ６０７に含まれる行路の中から集合分割解を探索することで得られた乗務行路計画のデータである乗務行路計画データ６０９を示す図である。
図３５の第１の行路案データ６０７に含まれる６つの行路の中から集合分割解を探索すると、「ＸｂｅｄＹ＋ＸａｃｆＹ」と、「ＸａｃｆｄＹ＋ＸｂｅＹ」とが探索され、この２つが乗務行路計画となる。また、乗務行路計画「ＸｂｅｄＹ＋ＸａｃｆＹ」を構成する行路に含まれるアークの基礎コストの総和は「２１＋１２＝３３」であり、乗務行路計画「ＸａｃｆｄＹ＋ＸｂｅＹ」を構成する行路に含まれるアークの基礎コストの総和は「９＋２５＝３４」であることから、値の小さい乗務行路計画「ＸｂｅｄＹ＋ＸａｃｆＹ」が最適解であり、乗務行路計画「ＸａｃｆｄＹ＋ＸｂｅＹ」は準最適解となる。
【０１０４】
１−２．実施例
次に、図３７〜図４０を参照して、１−１．原理で説明した乗務行路計画を行う装置である乗務行路計画装置１０について説明する。
【０１０５】
１−２−１．構成
先ず、構成について説明する。
図３７は、乗務行路計画装置１０の機能構成を示すブロック図である。
乗務行路計画装置１０は、ＣＰＵ（Central Processing Unit）１００と、入力部２００と、表示部３００と、通信部４００と、ＲＯＭ（Read Only Memory）５００と、ＲＡＭ（Random Access Memory）６００とを備え、各部はバス７００で相互にデータ通信可能に接続されて構成されるコンピュータシステムである。
【０１０６】
ＣＰＵ１００は、ＲＯＭ５００に記憶されているシステムプログラム等に従って各部を統括的に制御する。また、ＣＰＵ１００は、ＲＯＭ５００に記憶されている第１の乗務行路計画プログラム５０１に従って第１の乗務行路計画処理を行い、乗務行路計画を表示部３００に表示させる。
【０１０７】
入力部２００は、例えばキーボード等により実現され、押下されたキーの信号をＣＰＵ１００に出力する。この入力部２００によるキー操作により、各種データの入力等がなされる。
【０１０８】
表示部３００は、ＬＣＤ（Liquid Crystal Display）等により構成され、ＣＰＵ１００から入力される表示信号に基づいた各種表示を行う表示装置である。
【０１０９】
通信部４００は、ＣＰＵ１００の制御に基づいて、装置内部で利用される情報をインターネット等の通信ネットワークを介して外部とやりとりするための通信装置である。
【０１１０】
ＲＯＭ５００は、乗務行路計画装置１０の備える各種機能を実現するためのプログラム等を記憶している。ＲＯＭ５００は、ＣＰＵ１００により読み出され、第１の乗務行路計画処理（図３８参照）として実行される第１の乗務行路計画プログラム５０１と、列車ダイヤデータ５０５と、乗務員拠点データ５０７と、乗務遷移条件データ５０９とを備えている。また、第１の乗務行路計画プログラム５０１は、最小コスト完全マッチング算出処理（図３９参照）として実行される最小コスト完全マッチング算出プログラム５０２と、第１の行路案抽出処理（図４０参照）として実行される第１の行路案抽出プログラム５０３とをサブルーチンとして備えている。
【０１１１】
第１の乗務行路計画処理とは、ＣＰＵ１００が、列車ダイヤデータ５０５及び乗務員拠点データ５０７に基づいて生成した乗務行路ネットワークに対する最小コスト完全マッチングを、最小コスト完全マッチング算出処理により算出し、第１の行路案抽出処理により、行路の篩い分けを行う処理である。そして、ＣＰＵ１００は、行路の篩い分けによって残存した行路の中から集合分割解を探索し、探索した集合分割解を乗務行路計画として表示部３００に表示させる。この第１の乗務行路計画処理については、詳細に後述する。
【０１１２】
最小コスト完全マッチング算出処理とは、ＣＰＵ１００が、乗務行路ネットワークに基づいて遷移正規化図を生成し、生成した遷移正規化図を用いて最小コスト完全マッチングを算出する処理である。そして、ＣＰＵ１００は、算出した最小コスト完全マッチングに基づいて、マッチング後ネットワークを生成する。この最小コスト完全マッチング算出処理は、その原理について上述したが、フローチャートを用いて再度詳細に後述する。
【０１１３】
第１の行路案抽出処理とは、ＣＰＵ１００が、マッチング後ネットワークに含まれる行路を選択しながら、合計既約コストに基づいた行路の削除を行うことで、行路の篩い分けを行う処理である。この第１の行路案抽出処理は、その原理について上述したが、フローチャートを用いて再度詳細に後述する。
【０１１４】
列車ダイヤデータ５０５は、例えば図５７に示したような通常運行時の列車ダイヤについてのデータであり、列車ダイヤを構成する列車の列車情報が記憶されている。具体的には、各列車の列車番号、各駅における着発時刻、列車種別等の情報である。
【０１１５】
乗務員拠点データ５０７は、乗務員の拠点となる駅が定められたデータである。この列車ダイヤデータ５０５及び乗務員拠点データ５０７は、第１の乗務行路計画処理において、ＣＰＵ１００が乗務行路ネットワークを生成する際に用いるデータである。
【０１１６】
乗務遷移条件データ５０９は、単位乗務間の遷移に関する条件や遷移に関する評価基準が定められたデータである。この乗務遷移条件データ５０９は、第１の乗務行路計画処理において、ＣＰＵ１００が乗務行路ネットワークの各アークの基礎コストを設定する際に用いるデータである。
【０１１７】
ＲＡＭ６００は、ＣＰＵ１００により実行されるシステムプログラム、各種処理プログラム、各種処理の処理中データ、処理結果などを一時的に記憶するワークエリアを形成している。ＲＡＭ６００は、乗務行路ネットワークデータ６０１と、遷移正規化図データ６０３と、マッチング後ネットワークデータ６０５と、第１の行路案データ６０７と、乗務行路計画データ６０９とを備えている。
【０１１８】
乗務行路ネットワークデータ６０１は、例えば図２に示したような乗務行路ネットワークについてのデータであり、第１の乗務行路計画処理においてＣＰＵ１００により生成される乗務行路ネットワークが記憶される。この乗務行路ネットワークデータ６０１には、各アークに設定された基礎コストも一緒に記憶される。
【０１１９】
遷移正規化図データ６０３は、例えば図３〜図２９に示したような遷移正規化図についてのデータであり、最小コスト完全マッチング算出処理においてＣＰＵ１００により生成される遷移正規化図が記憶される。この遷移正規化図データ６０３には、各ノードの距離ラベルや、ノードポテンシャルや、既約コストも一緒に記憶される。
【０１２０】
マッチング後ネットワークデータ６０５は、例えば図３０に示したようなマッチング後ネットワークについてのデータであり、最小コスト完全マッチング算出処理においてＣＰＵ１００により生成されるマッチング後ネットワークが記憶される。このマッチング後ネットワークデータ６０５には、各アークについて求められた既約コストも一緒に記憶される。
【０１２１】
第１の行路案データ６０７は、行路６０７１と、合計既約コスト６０７３と、ノード６０７５とが対応付けて記憶され、各ノードの出現回数６０７７が記憶されたデータであり、そのデータ構成例は、図３１〜図３５に示した通りである。この第１の行路案データ６０７は、第１の行路案抽出処理において、ＣＰＵ１００により生成される。
【０１２２】
乗務行路計画データ６０９は、第１の乗務行路計画処理において、ＣＰＵ１００により探索された集合分割解が乗務行路計画として記憶されるデータであり、そのデータ構成例は、図３６に示した通りである。
【０１２３】
１−２−２．処理の流れ
次に、処理の流れについて説明する。
図３８は、ＣＰＵ１００により第１の乗務行路計画プログラム５０１が読み出されて実行されることにより乗務行路計画装置１０において実行される第１の乗務行路計画処理の流れを示すフローチャートである。
【０１２４】
先ず、ＣＰＵ１００は、第１の行路案抽出処理において行路の篩い分けを行う際に用いる閾値θの設定等の初期設定を行う（ステップＡ１）。
【０１２５】
次いで、ＣＰＵ１００は、列車ダイヤデータ５０５及び乗務員拠点データ５０７に基づいて、乗務行路ネットワークを生成する（ステップＡ３）。具体的には、ＣＰＵ１００は、列車ダイヤの全ての列車スジを乗務員が交代可能な駅で区切ることで単位乗務を取得する。そして、ＣＰＵ１００は、各単位乗務をノードとし、遷移可能な単位乗務同士のノード間をアークで結ぶことで乗務行路ネットワークを生成する。その後、ＣＰＵ１００は、生成した乗務行路ネットワークを、乗務行路ネットワークデータ６０１として記憶させる。
【０１２６】
その後、ＣＰＵ１００は、乗務遷移条件データ５０９に基づいて、ステップＡ３で生成した乗務行路ネットワークに含まれる各アークの基礎コストを設定する（ステップＡ５）。具体的には、ＣＰＵ１００は、評価の低い単位乗務間の遷移を表すアークほど値が大きくなるように、基礎コストを設定する。そして、ＣＰＵ１００は、設定した基礎コストを、乗務行路ネットワークデータ６０１に記憶させる。
【０１２７】
次いで、ＣＰＵ１００は、最小コスト完全マッチング算出プログラム５０２を読み出して実行することで、最小コスト完全マッチング算出処理を行う（ステップＡ７）。
【０１２８】
図３９は、最小コスト完全マッチング算出処理の流れを示すフローチャートである。
先ず、ＣＰＵ１００は、第１の乗務行路計画処理において生成した乗務行路ネットワーク及び設定した各アークの基礎コストに基づいて、遷移正規化図を生成する（ステップＢ１）。
【０１２９】
具体的には、ＣＰＵ１００は、遷移元ノードと、遷移先ノードと、ダミーノードとを配置し、乗務行路ネットワークと等価になるようにアークを結ぶことで、遷移正規化図を生成する。また、各ノードの距離ラベルを「∞」、ノードポテンシャルを「０」にそれぞれ初期化し、各アークの既約コストの初期値として、基礎コストを設定する。そして、ＣＰＵ１００は、生成した遷移正規化図を、遷移正規化図データ６０３として記憶させる。
【０１３０】
次いで、ＣＰＵ１００は、遷移正規化図の各遷移元ノードを出発ノードとして、最小の既約コストで到達可能な遷移先ノードを探索することで、最小コスト完全マッチングを算出する（ステップＢ３）。この最小コスト完全マッチングを算出する方法については、図３〜図２９を用いて説明した通りである。
【０１３１】
その後、ＣＰＵ１００は、ステップＢ３において最小コスト完全マッチングが算出された遷移正規化図をネットワーク形式に書き換えることで、マッチング後ネットワークを生成する（ステップＢ５）。そして、ＣＰＵ１００は、生成したマッチング後ネットワークを、マッチング後ネットワークデータ６０５として記憶させる。
【０１３２】
次いで、ＣＰＵ１００は、算出した最小コスト完全マッチングに属する行路に、１継続乗務時間違反経路が含まれるか否かを判定する（ステップＢ７）。具体的には、ＣＰＵ１００は、列車ダイヤデータ５０５及び乗務行路ネットワークデータ６０１を参照して、最小コスト完全マッチングに属する行路の中から、遷移に要する時間が「０」であるアークを全て抽出し、抽出したアークを含まない経路を列挙する。そして、列挙した各経路それぞれの乗務時間を算出し、算出した乗務時間が予め定められた１継続乗務時間を超えているか否かを判定する。
【０１３３】
ステップＢ７において、１継続乗務時間違反経路が含まれると判定した場合は（ステップＢ７；Ｙｅｓ）、ＣＰＵ１００は、当該１継続乗務時間違反経路上のアークを１つ削除して（ステップＢ９）、ステップＢ３に戻る。
【０１３４】
一方、ステップＢ７において、１継続乗務時間違反経路が含まれないと判定した場合は（ステップＢ７；Ｎｏ）、ＣＰＵ１００は、最小コスト完全マッチング算出処理を終了する。
【０１３５】
図３８の第１の乗務行路計画処理に戻って、最小コスト完全マッチング算出処理を終了すると、ＣＰＵ１００は、第１の行路案抽出プログラム５０３を読み出して実行することで、第１の行路案抽出処理を行う（ステップＡ９）。
【０１３６】
図４０は、第１の行路案抽出処理の流れを示すフローチャートである。
先ず、ＣＰＵ１００は、最小コスト完全マッチング算出処理において生成したマッチング後ネットワークに含まれる行路を１つ選択する（ステップＣ１）。
【０１３７】
次いで、ＣＰＵ１００は、選択した行路に含まれるアークの既約コストの総和を算出することで合計既約コストを算出し、当該行路と共に第１の行路案データ６０７として記憶させる（ステップＣ３）。そして、ＣＰＵ１００は、当該行路に含まれるノードを特定することで、ノードの出現回数を更新する（ステップＣ５）。
【０１３８】
その後、ＣＰＵ１００は、ノードの最小出現回数が閾値θを超えたか否かを判定し（ステップＣ７）、超えなかったと判定した場合は（ステップＣ７；Ｎｏ）、ステップＣ１３へと処理を移行する。
【０１３９】
一方、ステップＣ７において、ノードの最小出現回数が閾値θを超えたと判定した場合は（ステップＣ７；Ｙｅｓ）、ＣＰＵ１００は、第１の行路案データ６０７に含まれる行路のうち、合計既約コストが最大の行路を１つ削除する（ステップＣ９）。そして、ＣＰＵ１００は、削除した行路に含まれるノードを特定することで、ノードの出現回数を更新する（ステップＣ１１）。
【０１４０】
次いで、ＣＰＵ１００は、マッチング後ネットワークから他に選択できる行路が無くなったか否かを判定し（ステップＣ１３）、まだ他に選択できる行路が有ると判定した場合は（ステップＣ１３；Ｎｏ）、ステップＣ１へと戻る。
【０１４１】
一方、ステップＣ１３において、他に選択できる行路が無くなったと判定した場合は（ステップＣ１３；Ｙｅｓ）、ＣＰＵ１００は、第１の行路案データ６０７を参照して、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が有るか否かを判定する（ステップＣ１５）。
【０１４２】
ステップＣ１５において、行路が有ると判定した場合は（ステップＣ１５；Ｙｅｓ）、ＣＰＵ１００は、当該行路のうち、合計既約コストが最大の行路を１つ削除する（ステップＣ１７）。そして、ＣＰＵ１００は、削除した行路に含まれるノードを特定することで、ノードの出現回数を更新して（ステップＣ１９）、ステップＣ１５へと戻る。
【０１４３】
一方、ステップＣ１５において、行路が無いと判定した場合は（ステップＣ１５；Ｎｏ）、ＣＰＵ１００は、第１の行路案抽出処理を終了する。
【０１４４】
図３８の第１の乗務行路計画処理に戻って、第１の行路案抽出処理を終了すると、ＣＰＵ１００は、篩い分けにより残存した行路の中から集合分割解を探索し（ステップＡ１１）、探索した集合分割解を乗務行路計画データ６０９に記憶させる。そして、ＣＰＵ１００は、探索した集合分割解を乗務行路計画として表示部３００に表示させて（ステップＡ１３）、第１の乗務行路計画処理を終了する。
【０１４５】
１−３．作用効果
本実施形態によれば、単位乗務を表すノードの最小コスト完全マッチングが算出され、その過程で求められる既約コストに基づいて行路の篩い分けが行われる。そして、篩い分けにより残存した行路の中から集合分割解が探索されて、乗務行路計画とされる。
【０１４６】
既約コストは、個々のノード間の接続で見た場合の各アークの評価値（言わば、局所的な評価値）ではなく、乗務行路ネットワーク全体で見た場合の各アークの評価値（言わば、大域的な評価値）であるため、既約コストに基づいた行路の篩い分けにより、乗務行路計画における必要性の高い行路のみが残存するようになる。
【０１４７】
また、各ノードの出現回数が必ず所定の閾値以上となるように行路の篩い分けが行われるため、特定のノードを含む行路案の数だけが極端に少なくなるといった事態の発生が防止され、乗務行路計画として成立し得る行路案の組み合わせが存在し易くなる。
【０１４８】
２．第２実施形態
２−１．原理
次に、第２実施形態における乗務行路計画の原理について説明する。
図４１は、第２の乗務行路計画の流れを示すフローチャートである。
第２の乗務行路計画は、乗務行路ネットワーク生成（ステップＴ１）と、各アークの基礎コスト設定（ステップＴ３）と、最小コスト完全マッチング算出処理（ステップＴ５）と、クリーク抽出処理（ステップＴ７）と、閾値処理（ステップＴ９）と、第２の行路案抽出処理（ステップＴ１１）と、集合分割解探索（ステップＴ１３）との７つのステップにより実現される。
【０１４９】
尚、乗務行路ネットワーク生成（ステップＴ１）、各アークの基礎コスト設定（ステップＴ３）、最小コスト完全マッチング算出処理（ステップＴ５）及び集合分割解探索（ステップＴ１３）については、１−１．原理で説明した第１の乗務行路計画における処理と同一であるため、説明を省略する。
【０１５０】
２−１−１．クリーク抽出処理
先ず、クリーク抽出処理について説明する。
ステップＴ５において最小コスト完全マッチング算出処理を行ったら、マッチング後ネットワークの中から、同一の行路に含まれ得ないノードの集合を「クリーク」として抽出する。
【０１５１】
具体的には、最もノード（単位乗務）が密集していると考えられる時間帯（例えば、ラッシュ時間帯）の一の時刻を選択し、選択した時刻にかかる全てのノード（選択した時刻に乗務している単位乗務）を抽出して、その集合をクリークとする。しかし、これではクリークが不十分であるため、クリークに属するノードの何れからも到達できず、また何れのノードへも到達できないノードが存在するか否かを判定し、存在する場合は、当該ノードをクリークに含める処理を行う。
【０１５２】
図４２は、図３０のマッチング後ネットワークから、クリークとなるノードを抽出した結果を示す図である。ここでは、同一の行路に含まれ得ないノードとして、ノード「ｅ」及び「ｆ」がクリークとして抽出されている。尚、ノード「ａ」及び「ｂ」も同一の行路に含まれ得ないため、ノード「ａ」及び「ｂ」をクリークとして抽出することにしても良い。
【０１５３】
２−１−２．閾値処理
次に、閾値処理について説明する。
閾値処理では、クリーク抽出処理により抽出されたクリークに属するノードを含まない行路と、クリークに属するノードを含む行路とのそれぞれについて相対コストと呼ばれる評価値を算出する。
【０１５４】
具体的には、先ずクリークに属するノードを含まない行路の中から合計既約コストを最小にする行路を特定し、特定した行路の合計既約コストを最小合計既約コストＲＣ0とする。そして、クリークに属するノードを含まない各行路について、当該行路の合計既約コストと、最小合計既約コストＲＣ0との差を算出し、算出した値を相対コストとする。そして、算出した相対コストが予め定められた閾値αを超えている場合は、当該行路の閾値超過フラグをＯＮに、超えていない場合にはＯＦＦに設定する。
【０１５５】
また、クリークに属する各ノードについて、以下の処理を行う。即ち、当該ノード「ｎ」を含む行路の中から合計既約コストを最小にする行路を特定し、特定した行路の合計既約コストを最小合計既約コストＲＣnとする。そして、当該ノード「ｎ」を含む各行路について、当該行路の合計既約コストと、最小合計既約コストＲＣnとの差を算出し、算出した値を相対コストとする。そして、算出した相対コストが予め定められた閾値αを超えている場合は、当該行路の閾値超過フラグをＯＮに、超えていない場合にはＯＦＦに設定する。
【０１５６】
この閾値処理を、図４２に示したノード「ｅ」及び「ｆ」がクリークとして抽出されたマッチング後ネットワークについて行った場合について、以下説明する。但し、ここでは、閾値αを「４」として閾値処理を行った場合について説明する。
【０１５７】
先ず、クリークに属するノード「ｅ」及び「ｆ」を含まないマッチング後ネットワークを、図４３に示す。
図４３のマッチング後ネットワークにおいて、合計既約コストを最小にする行路は行路「ＸａｃｄＹ」又は「ＸｂｃｄＹ」であり、その合計既約コストは「９」であることから、最小合計既約コストＲＣ0は「９」となる。
【０１５８】
この時、図４３のマッチング後ネットワークに含まれる各行路について相対コストを算出すると、行路「ＸａｃｄＹ」及び「ＸｂｃｄＹ」については「９−９＝０」であり、行路「ＸｃｄＹ」については「１０−９＝１」である。そして、何れの行路も相対コストが閾値「α＝４」よりも小さいため、各行路の閾値超過フラグはＯＦＦとなる。この場合の行路６２３１と、合計既約コスト６２３３と、相対コスト６２３５と、閾値超過フラグ６２３７との関係を示すデータである閾値処理用データ６２３を、図４４に示す。
【０１５９】
次に、クリークに属するノード「ｅ」を含むマッチング後ネットワークを、図４５に示す。
図４５のマッチング後ネットワークにおいて、合計既約コストを最小にする行路は行路「ＸｂｅｄＹ」であり、その合計既約コストは「０」であることから、最小合計既約コストＲＣeは「０」となる。
【０１６０】
この時、図４５のマッチング後ネットワークに含まれる各行路について相対コストを算出すると、行路「ＸａｃｅｄＹ」及び「ＸｂｃｅｄＹ」については「４−０＝４」であり、行路「ＸａｃｅＹ」、「ＸｃｅｄＹ」及び「ＸｂｃｅＹ」については「５−０＝５」である。また、行路「ＸｃｅＹ」については「６−０＝６」であり、行路「ＸｂｅｄＹ」については「０−０＝０」であり、行路「ＸｂｅＹ」については「１−０＝１」である。そして、行路「ＸａｃｅＹ」、「ＸｃｅｄＹ」、「ＸｃｅＹ」及び「ＸｂｃｅＹ」については、相対コストが閾値「α＝４」を超えたため、閾値超過フラグがＯＮに設定される。この場合の閾値処理用データ６２３を、図４６に示す。
【０１６１】
同様に、クリークに属するノード「ｆ」を含むマッチング後ネットワークを、図４７に示す。
図４７のマッチング後ネットワークにおいて、合計既約コストを最小にする行路は行路「ＸａｃｆＹ」、「ＸａｃｆｄＹ」、「ＸｂｃｆＹ」又は「ＸｂｃｆｄＹ」であり、その合計既約コストは「０」であることから、最小合計既約コストＲＣfは「０」となる。
【０１６２】
この時、図４７のマッチング後ネットワークに含まれる各行路について相対コストを算出すると、行路「ＸａｆＹ」及び「ＸａｆｄＹ」については「２４−０＝２４」であり、行路「ＸａｃｆＹ」、「ＸａｃｆｄＹ」、「ＸｂｃｆＹ」及び「ＸｂｃｆｄＹ」については「０−０＝０」である。また、行路「ＸｃｆＹ」及び「ＸｃｆｄＹ」については「１−０＝１」である。そして、行路「ＸａｆＹ」、及び「ＸａｆｄＹ」については、相対コストが閾値「α＝４」を超えたため、閾値超過フラグがＯＮに設定される。この場合の閾値処理用データ６２３を、図４８に示す。
【０１６３】
２−１−３．第２の行路案抽出処理
第２の行路案抽出処理は、１−１−４．第１の行路案抽出処理で説明した処理とほぼ同様であるが、閾値処理により閾値設定フラグがＯＮに設定された行路については篩い分けの対象とせず、また、合計既約コストではなく、閾値処理において算出された相対コストの大きさに基づいて行路の削除を行う点が、第１の行路案抽出処理とは異なる。
【０１６４】
この第２の行路案抽出処理により、図３０に示したマッチング後ネットワークに含まれる行路の篩い分けを行った結果を、図４９に示す。但し、ここでは、閾値θを「３」として行路の篩い分けを行った場合について説明する。
【０１６５】
図４９は、第２の行路案抽出処理において行路の篩い分けを行うためのデータである第２の行路案データ６２５を示す図である。第２の行路案データ６２５には、行路６２５１と、相対コスト６２５３と、ノード６２５５とが対応付けて記憶されており、ノード６２５５を構成する各ノードについて出現回数６２５７が記憶されている。ここでは、行路の篩い分けの結果、相対コストが比較的小さい７つの行路が残存した状態が示されている。
【０１６６】
第２の行路案抽出処理が終了したら、１−１−５．最適解探索と同様に、篩い分けにより残存した行路の中から集合分割解を探索し、探索した集合分割解を乗務行路計画とする。乗務行路計画の最適解となるのは、アークに設定された基礎コストの総和が最小となるような行路の組み合わせである。
【０１６７】
図５０は、図４９の第２の行路案データ６２５に含まれる行路の中から集合分割解を探索することで得られた乗務行路計画データ６０９を示す図である。
図４９の第２行路案データ６２５に含まれる７つの行路の中から集合分割解を探索すると、「ＸｂｅｄＹ＋ＸａｃｆＹ」と、「ＸａｃｆｄＹ＋ＸｂｅＹ」とが探索され、この２つが乗務行路計画となる。また、乗務行路計画「ＸｂｅｄＹ＋ＸａｃｆＹ」を構成する行路に含まれるアークの基礎コストの総和は「２１＋１２＝３３」であり、乗務行路計画「ＸａｃｆｄＹ＋ＸｂｅＹ」を構成する行路に含まれるアークの基礎コストの総和は「９＋２５＝３４」であることから、値の小さい乗務行路計画「ＸｂｅｄＹ＋ＸａｃｆＹ」が最適解であり、乗務行路計画「ＸａｃｆｄＹ＋ＸｂｅＹ」は準最適解となる。
【０１６８】
第２の行路案抽出処理において、相対コストに基づいて行路の篩い分けを行うのは、クリークに属するノードを含んだ行路が集中的に削除されることを防止するためである。例えば、クリークに属する一のノードを含む行路が、合計既約コストの大きい行路ばかりであったとする。これは、当該ノードと、当該ノードに隣接するノードとを結ぶアークの既約コストが極端に大きい場合等に起こり得る現象である。
【０１６９】
この場合、合計既約コストに基づいて行路の篩い分けを行うと、合計既約コストの大きい行路から順に削除していくため、当該ノードを含む行路が集中的に削除されることになる。クリークに属するノードは互いに同一の行路に含まれ得ないため、当該ノードを含む行路が集中的に削除されると、どうしてもノードに偏りが生じてしまう。これは、集合分割解を探索する上での障害となる。
【０１７０】
しかし、相対コストは、全ての行路から見た各行路の絶対的な評価値ではなく、クリークに属するノード別に見た各行路の相対的な評価値であるため、相対コストに基づいた行路の篩い分けが行われると、当該ノードを含む行路が集中的に削除されることがない。
【０１７１】
また、相対コストが所定の閾値を超えていない行路についてのみ篩い分けを行うことにしているため、全ての行路について篩い分けを行う場合と比べて、処理時間が短時間で済むことになる。
【０１７２】
２−２．実施例
次に、図５１〜図５６を参照して、２−１．原理で説明した乗務行路計画を行う装置である乗務行路計画装置２０について説明する。
【０１７３】
２−２−１．構成
先ず、構成について説明する。
乗務行路計画装置２０の構成は、１−２．実施例で説明した乗務行路計画装置１０の構成とほぼ同一であるが、ＲＯＭ及びＲＡＭの構成が乗務行路計画装置１０とは異なる。そこで、ＲＯＭ及びＲＡＭ以外の構成については説明を省略し、各機能部を、ＣＰＵ１２０、入力部２２０、表示部３２０、通信部４２０、ＲＯＭ５２０、ＲＡＭ６２０及びバス７２０でそれぞれ表すことにする。また、乗務行路計画装置１０と同一の構成要素については同一の符号を付し、その説明を省略する。
【０１７４】
図５１は、乗務行路計画装置２０が備えるＲＯＭ５２０の構成を示す図である。
ＲＯＭ５２０は、ＣＰＵ１２０により読み出され、第２の乗務行路計画処理（図５３参照）として実行される第２の乗務行路計画プログラム５２１と、列車ダイヤデータ５０５と、乗務員拠点データ５０７と、乗務遷移条件データ５０９とを備えている。また、第２の乗務行路計画プログラム５２１は、最小コスト完全マッチング算出処理（図３９参照）として実行される最小コスト完全マッチング算出プログラム５０２と、クリーク抽出処理（図５４参照）として実行されるクリーク抽出プログラム５２２と、閾値処理（図５５参照）として実行される閾値処理プログラム５２３と、第２の行路案抽出処理（図５６参照）として実行される第２の行路案抽出プログラム５２４とをサブルーチンとして備えている。
【０１７５】
第２の乗務行路計画処理とは、ＣＰＵ１２０が、列車ダイヤデータ５０５及び乗務員拠点データ５０７に基づいて生成した乗務行路ネットワークに対する最小コスト完全マッチングを、最小コスト完全マッチング算出処理により算出し、クリーク抽出処理により抽出したクリークに基づいた閾値処理を行う処理である。そして、ＣＰＵ１２０は、第２の行路案抽出処理により行路の篩い分けを行い、残存した行路の中から集合分割解を探索し、探索した集合分割解を乗務行路計画として表示部３２０に表示させる。この第２の乗務行路計画処理については、詳細に後述する。
【０１７６】
クリーク抽出処理とは、ＣＰＵ１２０が、マッチング後ネットワークから、最もノードが密集していると考えられる時刻にかかる全てのノードを抽出することで、クリークを抽出する処理である。このクリーク抽出処理は、その原理について上述したが、フローチャートを用いて再度詳細に後述する。
【０１７７】
閾値処理とは、ＣＰＵ１２０が、クリークに属するノードを含まない行路と、クリークに属する各ノードを含む行路とのそれぞれについて、相対コストに基づいた閾値判定を行い、相対コストが閾値αを超えた行路については閾値超過フラグをＯＮに設定し、超えていない行路についてはＯＦＦに設定する処理である。この閾値処理は、その原理について上述したが、フローチャートを用いて再度詳細に後述する。
【０１７８】
第２の行路案抽出処理とは、ＣＰＵ１２０が、マッチング後ネットワークに含まれる行路を選択しながら、相対コストに基づいた行路の削除を行うことで、行路の篩い分けを行う処理である。この第２の行路案抽出処理は、その原理について上述したが、フローチャートを用いて再度詳細に後述する。
【０１７９】
図５２は、乗務行路計画装置２０が備えるＲＡＭ６２０の構成を示す図である。
ＲＡＭ６２０は、乗務行路ネットワークデータ６０１と、遷移正規化図データ６０３と、マッチング後ネットワークデータ６０５と、クリークデータ６２１と、閾値処理用データ６２３と、第２の行路案データ６２５と、乗務行路計画データ６０９とを備えている。
【０１８０】
クリークデータ６２１は、クリークについてのデータであり、クリーク抽出処理おいて、ＣＰＵ１２０によりマッチング後ネットワークからクリークとして抽出されたノードが記憶される。
【０１８１】
閾値処理用データ６２３は、行路６２３１と、合計既約コスト６２３３と、相対コスト６２３５と、閾値超過フラグ６２３７とが対応付けて記憶されたデータであり、そのデータ構成例は、図４４、図４６及び図４８に示した通りである、この閾値処理用データ６２３は、閾値処理において、ＣＰＵ１２０により生成される。
【０１８２】
第２の行路案データ６２５は、行路６２５１と、相対コスト６２５３と、ノード６２５５とが対応付けて記憶され、各ノードの出現回数６２５７が記憶されたデータであり、そのデータ構成例は、図４９に示した通りである。この第２の行路案データ６２５は、第２の行路案抽出処理において、ＣＰＵ１２０により生成される。
【０１８３】
２−２−２．処理の流れ
次に、処理の流れについて説明する。
図５３は、ＣＰＵ１２０により第２の乗務行路計画プログラム５２１が読み出されて実行されることにより乗務行路計画装置２０において実行される第２の乗務行路計画処理の流れを示すフローチャートである。
【０１８４】
先ず、ＣＰＵ１２０は、初期設定を行う（ステップＤ１）。具体的には、ＣＰＵ１２０は、閾値処理において行路の閾値判定を行う際に用いる閾値αや、第２の行路案抽出処理において行路の篩い分けを行う際に用いる閾値θの設定等を行う。
【０１８５】
次いで、ＣＰＵ１２０は、列車ダイヤデータ５０５及び乗務員拠点データ５０７に基づいて、乗務行路ネットワークを生成する（ステップＤ３）。具体的には、ＣＰＵ１２０は、列車ダイヤの全ての列車スジを乗務員が交代可能な駅で区切ることで単位乗務を取得する。そして、ＣＰＵ１２０は、各単位乗務をノードとし、遷移可能な単位乗務同士のノード間をアークで結ぶことで乗務行路ネットワークを生成する。その後、ＣＰＵ１２０は、生成した乗務行路ネットワークを、乗務行路ネットワークデータ６０１として記憶させる。
【０１８６】
その後、ＣＰＵ１２０は、乗務遷移条件データ５０９に基づいて、ステップＤ３で生成した乗務行路ネットワークに含まれる各アークの基礎コストを設定する（ステップＤ５）。具体的には、ＣＰＵ１２０は、評価の低い単位乗務間の遷移を表すアークほど値が大きくなるように、基礎コストを設定する。そして、ＣＰＵ１２０は、設定した基礎コストを、乗務行路ネットワークデータ６０１に記憶させる。
【０１８７】
次いで、ＣＰＵ１２０は、最小コスト完全マッチング算出プログラム５０２を読み出して実行することで、最小コスト完全マッチング算出処理を行う（ステップＤ７）。その後、ＣＰＵ１２０は、クリーク抽出プログラム５２２を読み出して実行することで、クリーク抽出処理を行う（ステップＤ９）。
【０１８８】
図５４は、クリーク抽出処理の流れを示すフローチャートである。
先ず、ＣＰＵ１２０は、列車ダイヤデータ５０５及びマッチング後ネットワークデータ６０５を参照して、最もノードが密集していると考えられる一の時刻を選択する（ステップＥ１）。
【０１８９】
そして、ＣＰＵ１２０は、選択した時刻にかかる全てのノードを抽出して、その集合をクリークとし（ステップＥ３）、クリークとして抽出したノードをクリークデータ６２１として記憶させる。
【０１９０】
次いで、ＣＰＵ１２０は、クリークに属する何れのノードからも到達できず、また何れのノードへも到達できないノードが存在するか否かを判定し（ステップＥ５）、存在すると判定した場合は（ステップＥ５；Ｙｅｓ）、当該ノードをクリークに含めて（ステップＥ７）、ステップＥ５に戻る。一方、ステップＥ５において、ノードが存在しないと判定した場合は（ステップＥ５；Ｎｏ）、ＣＰＵ１２０は、クリーク抽出処理を終了する。
【０１９１】
図５３の第２の乗務行路計画処理に戻って、クリーク抽出処理を終了すると、ＣＰＵ１２０は、閾値処理プログラム５２３を読み出して実行することで、閾値処理を行う（ステップＤ１１）。
【０１９２】
図５５は、閾値処理の流れを示すフローチャートである。
先ず、ＣＰＵ１２０は、マッチング後ネットワークデータ６０５及びクリークデータ６２１を参照し、クリークに属するノードを含まない行路の最小合計既約コストＲＣ0を算出する（ステップＦ１）。
【０１９３】
そして、ＣＰＵ１２０は、クリークに属するノードを含まない各行路について、ループＡの処理を繰り返し実行する。
ループＡでは、ＣＰＵ１２０は、当該行路の相対コストを算出する（ステップＦ３）。具体的には、ＣＰＵ１２０は、当該行路の合計既約コストを算出し、合計既約コストと、ステップＦ１で算出した最小合計既約コストＲＣ0との差を算出して、相対コストとする。
【０１９４】
次いで、ＣＰＵ１２０は、ステップＦ３で算出した相対コストが閾値αを超えているか否かを判定し（ステップＦ５）、超えていると判定した場合は（ステップＦ５；Ｙｅｓ）、当該行路の閾値超過フラグをＯＮに設定して（ステップＦ７）、次の行路へと処理を移行する。
【０１９５】
一方、ステップＦ５において、相対コストが閾値αを超えていないと判定した場合は（ステップＦ５；Ｎｏ）、ＣＰＵ１２０は、当該行路の閾値超過フラグをＯＦＦに設定して（ステップＦ８）、次の行路へと処理を移行する。そして、ＣＰＵ１２０は、クリークに属するノードを含まない全ての行路について処理を行った後、ループＡの処理を終了する。
【０１９６】
次いで、ＣＰＵ１２０は、クリークに属する各ノードについて、ループＢの処理を繰り返し実行する。
ループＢでは、ＣＰＵ１２０は、マッチング後ネットワークデータ６０５及びクリークデータ６２１を参照し、当該ノードを含む行路の最小合計既約コストＲＣnを算出する（ステップＦ９）。
【０１９７】
そして、ＣＰＵ１２０は、当該ノードを含む各行路について、ループＣの処理を繰り返し実行する。
ループＣでは、ＣＰＵ１２０は、当該行路の相対コストを算出する（ステップＦ１１）。具体的には、ＣＰＵ１２０は、当該行路の合計既約コストを算出し、合計既約コストと、ステップＦ９で算出した最小合計既約コストＲＣnとの差を算出して、相対コストとする。
【０１９８】
次いで、ＣＰＵ１２０は、ステップＦ１１で算出した相対コストが閾値αを超えているか否かを判定し（ステップＦ１３）、超えていると判定した場合は（ステップＦ１３；Ｙｅｓ）、当該行路の閾値超過フラグをＯＮに設定して（ステップＦ１５）、次の行路へと処理を移行する。
【０１９９】
一方、ステップＦ１３において、相対コストが閾値αを超えていないと判定した場合は（ステップＦ１３；Ｎｏ）、ＣＰＵ１２０は、当該行路の閾値超過フラグをＯＦＦに設定して（ステップＦ１６）、次の行路へと処理を移行する。そして、ＣＰＵ１２０は、当該ノードを含む全ての行路について処理を行った後、ループＣの処理を終了する。また、ＣＰＵ１２０は、クリークに属する全てのノードについて処理を行った後、ループＢの処理を終了して、閾値処理を終了する。
【０２００】
図５３の第２の乗務行路計画処理に戻って、閾値処理を終了すると、ＣＰＵ１２０は、第２の行路案抽出プログラム５２４を読み出して実行することで、第２の行路案抽出処理を行う（ステップＤ１３）。
【０２０１】
図５６は、第２の行路案抽出処理の流れを示すフローチャートである。
先ず、ＣＰＵ１２０は、最小コスト完全マッチング算出処理において生成したマッチング後ネットワークに含まれる行路を１つ選択する（ステップＧ１）。
【０２０２】
次いで、ＣＰＵ１２０は、ステップＧ１で選択した行路の閾値超過フラグがＯＮに設定されているか否かを判定し（ステップＧ３）、ＯＮに設定されていると判定した場合は（ステップＧ３；Ｙｅｓ）、ステップＧ１５へと処理を移行する。
【０２０３】
一方、ステップＧ３において、閾値超過フラグがＯＮに設定されていない、即ちＯＦＦに設定されていると判定した場合は（ステップＧ３；Ｎｏ）、ＣＰＵ１２０は、選択した行路の相対コストを、行路と共に第２の行路案データ６２５として記憶させる（ステップＧ５）。そして、ＣＰＵ１２０は、選択した行路に含まれるノードを特定することで、ノードの出現回数を更新する（ステップＧ７）。
【０２０４】
次いで、ＣＰＵ１２０は、ノードの最小出現回数が閾値θを超えたか否かを判定し（ステップＧ９）、超えなかったと判定した場合は（ステップＧ９；Ｎｏ）、ステップＧ１５へと処理を移行する。
【０２０５】
一方、ステップＧ９において、ノードの最小出現回数が閾値θを超えたと判定した場合は（ステップＧ９；Ｙｅｓ）、ＣＰＵ１２０は、第２の行路案データ６２５に含まれる行路のうち、相対コストが最大の行路を１つ削除する（ステップＧ１１）。そして、ＣＰＵ１２０は、削除した行路に含まれるノードを特定することで、ノードの出現回数を更新する（ステップＧ１３）。
【０２０６】
その後、ＣＰＵ１２０は、マッチング後ネットワークから他に選択できる行路が無くなったか否かを判定し（ステップＧ１５）、まだ他に選択できる行路が有ると判定した場合は（ステップＧ１５；Ｎｏ）、ステップＧ１へと戻る。
【０２０７】
一方、ステップＧ１５において、他に選択できる行路が無くなったと判定した場合は（ステップＧ１５；Ｙｅｓ）、ＣＰＵ１２０は、第２の行路案データ６２５を参照して、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が有るか否かを判定する（ステップＧ１７）。
【０２０８】
ステップＧ１７において、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が有ると判定した場合は（ステップＧ１７；Ｙｅｓ）、ＣＰＵ１２０は、当該行路のうち、相対コストが最大の行路を１つ削除する（ステップＧ１９）。そして、ＣＰＵ１２０は、削除した行路に含まれるノードを特定することで、ノードの出現回数を更新し（ステップＧ２１）、ステップＧ１７へと戻る。
【０２０９】
一方、ステップＧ１７において、出現回数＞閾値θの条件を満たすノードのみを含んだ行路が無いと判定した場合は（ステップＧ１７；Ｎｏ）、ＣＰＵ１２０は、第２の行路案抽出処理を終了する。
【０２１０】
図５３の第２の乗務行路計画処理に戻って、第２の行路案抽出処理を終了すると、ＣＰＵ１２０は、篩い分けにより残存した行路の中から集合分割解を探索し（ステップＤ１５）、探索した集合分割解を乗務行路計画データ６０９に記憶させる。そして、ＣＰＵ１２０は、探索した集合分割解を乗務行路計画として表示部３２０に表示させて（ステップＤ１７）、第２の乗務行路計画処理を終了する。
【０２１１】
２−３．作用効果
本実施形態によれば、マッチング後ネットワークからクリークが抽出され、抽出されたクリークに基づいた行路の閾値判定が行われる。そして、閾値を超えなかったと判定された行路についてのみ、合計既約コストから算出される相対コストに基づいた行路の篩い分けが行われ、篩い分けによって残存した行路の中から集合分割解が探索されて、乗務行路計画とされる。
【０２１２】
相対コストは、全ての行路から見た各行路の絶対的な評価値ではなく、クリークに属するノード別に見た各行路の相対的な評価値であるため、相対コストに基づいた行路の篩い分けが行われることで、クリークに属するノードを含む行路が集中的に削除されることがない。
【０２１３】
また、相対コストが所定の閾値を超えていない行路についてのみ篩い分けが行われるため、全ての行路について篩い分けが行われる場合と比べて、処理時間が短時間で済むことになる。
【０２１４】
３．変形例
３−１．集合被覆解探索
上述した実施形態では、篩い分けによって残存した行路の中から集合分割解を探索して乗務行路計画とすることとしたが、集合被覆解を探索して乗務行路計画とすることにしても良い。集合被覆解とは、同一のノードが複数回出現することを許し、全てのノードが少なくとも１回は出現するような行路の組み合わせのことを言う。この場合、ノードが重複した部分については、一の乗務員は乗務とし、別の乗務員は便乗とすれば良い。
【０２１５】
３−２．行路の篩い分け
第１実施形態で説明した行路の篩い分けは、例えば次のように行っても良い。
即ち、マッチング後ネットワークから全ての行路を選択した後に、出現回数＞閾値θの条件を満たすノードのみを含んだ行路の有無を判定する。そして、条件を満たす行路が無くなるまで、合計既約コストが最大の行路を１つ削除する処理を繰り返し実行する。
【０２１６】
或いは、マッチング後ネットワークから行路を１つずつ選択していき、最小出現回数が閾値θを超えた時点で、出現回数＞閾値θの条件を満たすノードのみを含んだ行路の有無を判定する。そして、条件を満たす行路が無くなるまで、合計既約コストが最大の行路を１つ削除する処理を繰り返し実行し、無くなった時点で、マッチング後ネットワークから他の行路を選択してくるようにする。尚、第２実施形態で説明した行路の篩い分けについても、同様にして行うことができる。
【０２１７】
３−３．閾値判定
第２実施形態では、閾値処理による行路の閾値判定を行った後に、第２の行路案抽出処理による行路の篩い分けを行うこととして説明したが、閾値判定を行いながら行路の篩い分けを行うようにしても良い。
【０２１８】
具体的には、マッチング後ネットワークから行路を１つ選択し、当該行路の相対コストを算出する。そして、算出した相対コストが閾値αを超えている場合は、当該行路は篩い分けの対象とせず、マッチング後ネットワークから次の行路を選択してくるようにする。一方、算出した相対コストが閾値αを超えていない場合は、当該行路は篩い分けの対象とし、ノードの出現回数を更新して、出現回数＞閾値θの条件を満たすノードのみを含んだ行路を１つ削除した後に、マッチング後ネットワークから次の行路を選択してくるようにする。
【０２１９】
更には、第２の行路案抽出処理に閾値処理を含めてしまっても良い。具体的には、第２の行路案抽出処理において、最初に全ての行路について閾値判定を行う。そして、相対コストが閾値αを超えないと判定した行路だけを抽出するようにする。
【図面の簡単な説明】
【０２２０】
【図１】第１の乗務行路計画の流れを示すフローチャート。
【図２】乗務行路ネットワークの一例を示す図。
【図３】遷移正規化図の一例を示す図。
【図４】遷移正規化図の一例を示す図。
【図５】遷移正規化図の一例を示す図。
【図６】遷移正規化図の一例を示す図。
【図７】遷移正規化図の一例を示す図。
【図８】遷移正規化図の一例を示す図。
【図９】遷移正規化図の一例を示す図。
【図１０】遷移正規化図の一例を示す図。
【図１１】遷移正規化図の一例を示す図。
【図１２】遷移正規化図の一例を示す図。
【図１３】遷移正規化図の一例を示す図。
【図１４】遷移正規化図の一例を示す図。
【図１５】遷移正規化図の一例を示す図。
【図１６】遷移正規化図の一例を示す図。
【図１７】遷移正規化図の一例を示す図。
【図１８】遷移正規化図の一例を示す図。
【図１９】遷移正規化図の一例を示す図。
【図２０】遷移正規化図の一例を示す図。
【図２１】遷移正規化図の一例を示す図。
【図２２】遷移正規化図の一例を示す図。
【図２３】遷移正規化図の一例を示す図。
【図２４】遷移正規化図の一例を示す図。
【図２５】遷移正規化図の一例を示す図。
【図２６】遷移正規化図の一例を示す図。
【図２７】遷移正規化図の一例を示す図。
【図２８】遷移正規化図の一例を示す図。
【図２９】遷移正規化図の一例を示す図。
【図３０】マッチング後ネットワークの一例を示す図。
【図３１】第１の行路案データの一例を示す図。
【図３２】第１の行路案データの一例を示す図。
【図３３】第１の行路案データの一例を示す図。
【図３４】第１の行路案データの一例を示す図。
【図３５】第１の行路案データの一例を示す図。
【図３６】乗務行路計画データの一例を示す図。
【図３７】第１実施形態における乗務行路計画装置の機能構成を示すブロック図。
【図３８】第１の乗務行路計画処理の流れを示すフローチャート。
【図３９】最小コスト完全マッチング算出処理の流れを示すフローチャート。
【図４０】第１の行路案抽出処理の流れを示すフローチャート。
【図４１】第２の乗務行路計画の流れを示すフローチャート。
【図４２】クリークに属するノードの一例を示す図。
【図４３】クリークに属するノードを含まない行路を示す図。
【図４４】閾値処理用データの一例を示す図。
【図４５】クリークに属するノードを含む行路を示す図。
【図４６】閾値処理用データの一例を示す図。
【図４７】クリークに属するノードを含む行路を示す図。
【図４８】閾値処理用データの一例を示す図。
【図４９】第２の行路案データの一例を示す図。
【図５０】乗務行路計画データの一例を示す図。
【図５１】第２実施形態における乗務行路計画装置のＲＯＭの構成を示す図。
【図５２】第２実施形態における乗務行路計画装置のＲＡＭの構成を示す図。
【図５３】第２の乗務行路計画処理の流れを示すフローチャート。
【図５４】クリーク抽出処理の流れを示すフローチャート。
【図５５】閾値処理の流れを示すフローチャート。
【図５６】第２の行路案抽出処理の流れを示すフローチャート。
【図５７】列車ダイヤの一例を示す図。
【図５８】乗務行路計画の一例を示す図。
【符号の説明】
【０２２１】
１０            乗務行路計画装置
１００          ＣＰＵ
２００          入力部
３００          表示部
４００          通信部
５００          ＲＯＭ
５０１          第１の乗務行路計画プログラム
５０２          最小コスト完全マッチング算出プログラム
５０３          第１の行路案抽出プログラム
５０５          列車ダイヤデータ
５０７          乗務員拠点データ
５０９          乗務遷移条件データ
６００          ＲＡＭ
６０１          乗務行路ネットワークデータ
６０３          遷移正規化図データ
６０５          マッチング後ネットワークデータ
６０７          第１の行路案データ
６０９          乗務行路計画データ
７００          バス
【図１】
0004701090.tif 000002
【図２】
0004701090.tif 000003
【図３】
0004701090.tif 000004
【図４】
0004701090.tif 000005
【図５】
0004701090.tif 000006
【図６】
0004701090.tif 000007
【図７】
0004701090.tif 000008
【図８】
0004701090.tif 000009
【図９】
0004701090.tif 000010
【図１０】
0004701090.tif 000011
【図１１】
0004701090.tif 000012
【図１２】
0004701090.tif 000013
【図１３】
0004701090.tif 000014
【図１４】
0004701090.tif 000015
【図１５】
0004701090.tif 000016
【図１６】
0004701090.tif 000017
【図１７】
0004701090.tif 000018
【図１８】
0004701090.tif 000019
【図１９】
0004701090.tif 000020
【図２０】
0004701090.tif 000021
【図２１】
0004701090.tif 000022
【図２２】
0004701090.tif 000023
【図２３】
0004701090.tif 000024
【図２４】
0004701090.tif 000025
【図２５】
0004701090.tif 000026
【図２６】
0004701090.tif 000027
【図２７】
0004701090.tif 000028
【図２８】
0004701090.tif 000029
【図２９】
0004701090.tif 000030
【図３０】
0004701090.tif 000031
【図３１】
0004701090.tif 000032
【図３２】
0004701090.tif 000033
【図３３】
0004701090.tif 000034
【図３４】
0004701090.tif 000035
【図３５】
0004701090.tif 000036
【図３６】
0004701090.tif 000037
【図３７】
0004701090.tif 000038
【図３８】
0004701090.tif 000039
【図３９】
0004701090.tif 000040
【図４０】
0004701090.tif 000041
【図４１】
0004701090.tif 000042
【図４２】
0004701090.tif 000043
【図４３】
0004701090.tif 000044
【図４４】
0004701090.tif 000045
【図４５】
0004701090.tif 000046
【図４６】
0004701090.tif 000047
【図４７】
0004701090.tif 000048
【図４８】
0004701090.tif 000049
【図４９】
0004701090.tif 000050
【図５０】
0004701090.tif 000051
【図５１】
0004701090.tif 000052
【図５２】
0004701090.tif 000053
【図５３】
0004701090.tif 000054
【図５４】
0004701090.tif 000055
【図５５】
0004701090.tif 000056
【図５６】
0004701090.tif 000057
【図５７】
0004701090.tif 000058
【図５８】
0004701090.tif 000059