(57)【要約】【課題】既存の乗務員区所の配置箇所を白紙状態に戻し、乗務員区所の配置箇所をすべて新規とした上で、輸送量（列車ダイヤ）に基づいて、乗務員区所の最適な配置、及び乗務員の最適な行路を決定する配置決定装置及び配置決定プログラムを提供する。【解決手段】配置決定装置１００が、少なくとも起点及び終点により定まるデータを取得するデータ取得部１１１と、起点及び終点から候補を取得する候補取得部１１２と、コストの評価値を算出するための各変数に乗じる係数を取得する係数取得部１１３と、データを組み合わせた行路から起点及び終点が一致する行路を候補ごとに列挙する行路列挙部１１４と、係数を乗じた変数を含む評価関数を生成する評価関数生成部１１５と、評価関数に基づいて評価値が最小となる変数を算出する算出部１１７とを備える。【選択図】図１
2011034499.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも起点及び終点により定まるデータを取得するデータ取得部と、
該データ取得部により取得された前記起点及び前記終点の中から候補を取得する候補取得部と、
コストの評価値を算出するための各変数に乗じる係数を取得する係数取得部と、
前記データを組み合わせた行路の中から前記起点及び前記終点が一致する前記行路を前記候補ごとに列挙する行路列挙部と、
該行路列挙部により列挙された前記行路のそれぞれについて前記係数を乗じた前記変数を含む評価関数を生成する評価関数生成部と、
該評価関数生成部により生成された前記評価関数に基づいて前記評価値が最小となる前記変数を算出する算出部と、
を備えることを特徴とする配置決定装置。
【請求項２】
前記評価関数生成部は、前記候補を採用するか否かを示す前記変数に前記係数を乗じた値と、前記列挙された行路を選択するか否かを示す前記変数に前記係数を乗じた値との総和を前記評価関数として生成することを特徴とする請求項１に記載の配置決定装置。
【請求項３】
前記候補及び前記列挙された行路に基づいて制約条件を生成する制約条件生成部をさらに備え、
前記算出部は、前記評価関数生成部により生成された前記評価関数及び前記制約条件生成部により生成された前記制約条件に基づいて、前記評価値が最小となる前記変数を算出することを特徴とする請求項１から請求項２のいずれか１つに記載の配置決定装置。
【請求項４】
配置決定装置のコンピュータに、
少なくとも起点及び終点により定まるデータを取得する手順と、
該データ取得部により取得された前記起点及び前記終点の中から候補を取得する手順と、
コストの評価値を算出するための各変数に乗じる係数を取得する手順と、
前記データを組み合わせた行路の中から前記起点及び前記終点が一致する前記行路を前記候補ごとに列挙する手順と、
該行路列挙部により列挙された前記行路のそれぞれについて前記係数を乗じた前記変数を含む評価関数を生成する手順と、
該評価関数生成部により生成された前記評価関数に基づいて前記評価値が最小となる前記変数を算出する手順と、
を実行させることを特徴とする配置決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鉄道事業者などの乗務員区所の配置及び乗務員の行路を決定する配置決定装置及び配置決定プログラムに関する。
【背景技術】
【０００２】
鉄道事業において、乗務員区所の配置箇所を決定することは、乗務員の運用効率に直結する事項であり、コスト削減の観点から重要な問題である。このため、運用計画の作成者は、乗務員区所の配置箇所を決定する際、新規に乗務員区所を置くことはできないか、既存の乗務員区所を別の場所に移転することはできないか、既存の乗務員区所の一部を廃止することができないか等について手作業で検討し、乗務員区所の配置箇所を決定していた。あるいは、既存の乗務員区所の配置箇所を変更せずに、乗務員の運用効率化を図るに留まるのみであった。
【０００３】
そこで、乗務員区所の最適な配置の決定、及び乗務員の最適な行路の決定を、手作業でなく配置決定装置を用いて行うことが試みられている。
【０００４】
まず、乗務員区所の最適な配置箇所を決定するという観点からは、特許文献１に開示された方法及び装置が知られている（特許文献１参照）。特許文献１に開示された方法は、公共施設、防災設備、店舗などの施設を対象とし、利用者の利便性を踏まえ、既存施設の移設あるいは規模拡大により利便性の向上を図るためのものである。ここで、特許文献１における「施設」を「乗務員区所」と、「利用者（需要のある地点）」を「乗務」と読み替えるものとする。
【０００５】
また、乗務員の最適な行路を決定するという観点からは、特許文献２に開示されたプログラム及び装置が知られている（特許文献２参照）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平８−１１０９１６号公報
【特許文献２】特開２００７−１８８２２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
乗務員の運用効率を向上させるためには、既存の乗務員区所の配置箇所を白紙状態に戻し、配置箇所をすべて新規とした上で、輸送量（列車ダイヤ）に基づいて、乗務員区所の最適な配置、及び乗務員の行路を決定することが望ましい。
【０００８】
しかしながら、乗務員区所の配置箇所、各乗務員区所に配置される乗務員数、各乗務員の行路など、組み合わせは膨大であり、その作業量が急激に増大してしまうため、運用計画の作成者が手作業で行うには限界があった。
【０００９】
また、鉄道事業では、乗務員が複数の乗務を担当するのに対し、特許文献１に開示された方法は、乗務員区所（乗務員）に対して乗務を割り当てる方法であり、乗務と乗務員の関係が逆であった。また、特許文献１に開示された装置は、乗務を考慮して乗務員区所の配置箇所を決定することはできても、乗務員の行路を決定することまではできなかった。さらに当該装置は、既存施設の移転や新設と、既存施設の現在の配置を前提としており、乗務員区所の配置箇所がすべて新規である場合に、乗務員区所の配置箇所を決定することができなかった。
【００１０】
一方、特許文献２に開示された装置は、既存の乗務員区所のみに基づいて乗務員の行路を決定することはできても、新規の乗務員区所を考慮した場合に、その行路が乗務員の最適な行路であるとは必ずしもいえないという問題があった。
【００１１】
本発明は、前記の諸点に鑑みてなされたものであり、既存の乗務員区所の配置箇所を白紙状態に戻し、乗務員区所の配置箇所をすべて新規とした上で、輸送量（列車ダイヤ）に基づいて、乗務員区所の最適な配置、及び乗務員の最適な行路を決定する配置決定装置及び配置決定プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するためになされたものであり、少なくとも起点及び終点により定まるデータを取得するデータ取得部と、該データ取得部により取得された前記起点及び前記終点の中から候補を取得する候補取得部と、コストの評価値を算出するための各変数に乗じる係数を取得する係数取得部と、前記データを組み合わせた行路の中から前記起点及び前記終点が一致する前記行路を前記候補ごとに列挙する行路列挙部と、該行路列挙部により列挙された前記行路のそれぞれについて前記係数を乗じた前記変数を含む評価関数を生成する評価関数生成部と、該評価関数生成部により生成された前記評価関数に基づいて前記評価値が最小となる前記変数を算出する算出部と、を備えることを特徴とする配置決定装置である。
【００１３】
また本発明は、前記評価関数生成部は、前記候補を採用するか否かを示す前記変数に前記係数を乗じた値と、前記列挙された行路を選択するか否かを示す前記変数に前記係数を乗じた値との総和を前記評価関数として生成することを特徴とする配置決定装置である。
【００１４】
また本発明は、前記候補及び前記列挙された行路に基づいて制約条件を生成する制約条件生成部をさらに備え、前記算出部は、前記評価関数生成部により生成された前記評価関数及び前記制約条件生成部により生成された前記制約条件に基づいて、前記評価値が最小となる前記変数を算出することを特徴とする配置決定装置である。
【００１５】
また本発明は、配置決定装置のコンピュータに、少なくとも起点及び終点により定まるデータを取得する手順と、該データ取得部により取得された前記起点及び前記終点の中から候補を取得する手順と、コストの評価値を算出するための各変数に乗じる係数を取得する手順と、前記データを組み合わせた行路の中から前記起点及び前記終点が一致する前記行路を前記候補ごとに列挙する手順と、該行路列挙部により列挙された前記行路のそれぞれについて前記係数を乗じた前記変数を含む評価関数を生成する手順と、該評価関数生成部により生成された前記評価関数に基づいて前記評価値が最小となる前記変数を算出する手順と、を実行させることを特徴とする配置決定プログラムである。
【発明の効果】
【００１６】
本発明によれば、配置決定装置が、評価関数に基づいてコストの評価値が最小となる変数を算出する。これにより、配置決定装置は、既存の乗務員区所の配置箇所を白紙状態に戻し、乗務員区所の配置箇所をすべて新規とした上で、輸送量（列車ダイヤ）に基づいて、乗務員区所の最適な配置、及び乗務員の最適な行路を決定することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態における配置決定装置１００の構成を示すブロック図である。
【図２】本発明の一実施形態における列車ダイヤの一例を示す図である。
【図３】本発明の一実施形態における図２の列車ダイヤのデータを示す図である。
【図４】本発明の一実施形態における３つの乗務員区所配置案を比較する表である。
【図５】本発明の一実施形態におけるＡ区所のネットワークを示す図である。
【図６】本発明の一実施形態におけるＡ区所のネットワークにおいて、終点ノードに達するまでを示す図である。
【図７】本発明の一実施形態におけるＡ区所のネットワークにおいて、乗務８ノードに達するまでを示す図である。
【図８】本発明の一実施形態におけるＡ区所のネットワークにおいて、乗務９ノードに達するまでを示す図である。
【図９】本発明の一実施形態における行路列挙手順を示すフローチャートである。
【図１０】本発明の一実施形態におけるＡ区所の行路を示す図である。
【図１１】本発明の一実施形態におけるＢ区所のネットワークを示す図である。
【図１２】本発明の一実施形態におけるＢ区所の最初の行路ができるまでを示す図である。
【図１３】本発明の一実施形態におけるＢ区所の行路を示す図である。
【図１４】本発明の一実施形態におけるＣ区所のネットワークを示す図である。
【図１５】本発明の一実施形態におけるＣ区所の行路を示す図である。
【図１６】本発明の一実施形態における乗務と行路の関係を示す表である。
【図１７】本発明の一実施形態における算出された最適な乗務員区所配置案を示す図である。
【図１８】本発明の一実施形態における配置決定装置１００の動作を説明するフローチャートである。
【図１９】本発明の一実施形態において、乗務員区所配置コストを変更した場合における算出された最適な乗務員区所配置案を示す図である。
【図２０】本発明の一実施形態において、乗務員の勤務条件を変更した場合におけるＡ区所の行路を示す図である。
【図２１】本発明の一実施形態において、乗務員の勤務条件を変更した場合におけるＣ区所の行路を示す図である。
【図２２】本発明の一実施形態において、乗務員の勤務条件を変更した場合における最適な乗務員区所配置案を示す図である。
【発明を実施するための形態】
【００１８】
本発明の一実施形態について図面を参照して詳細に説明する。図１は、本発明の一実施形態における配置決定装置１００の構成を示すブロック図である。配置決定装置１００は、データベース２００と、入力装置３００と、表示装置４００に接続される。
【００１９】
データベース２００は、列車ダイヤのデータ（図３）を記憶し、配置決定装置１００の要求に応じてデータを出力する。
【００２０】
入力装置３００は、運用計画の作成者の操作に応じて、乗務員区所を配置する駅の候補を示すデータと、候補としない駅を示すデータと、勤務条件データ（乗務員勤務条件パラメータ）を配置決定装置１００に出力する。
【００２１】
入力装置３００は、乗務員区所を配置する駅の候補（以下、「候補駅」と称する）を配置決定装置１００に出力する。ここで、乗務員区所とは、乗務員が勤務を開始及び終了する駅である。乗務員区所に配置された乗務員は、勤務において乗務を担当する。以下、乗務を開始する駅を「起点」と、乗務を終了する駅を「終点」と称する。
【００２２】
運用計画の作成者は、すべての駅を候補駅として、乗務員区所の最適な配置箇所を配置決定装置１００に算出させてもよいが、例えば駅の大きさを考慮して、候補としない駅（以下、「非候補駅」と称する）を入力装置３００から配置決定装置１００に入力することができる。この処理により、候補駅の数を少なくすることができるが、以下ではすべての駅を候補駅として説明する。
【００２３】
また、運用計画の作成者は、勤務条件として、例えば乗務員の拘束時間を入力装置３００から入力することができる。ここで拘束時間とは、乗務員の勤務の開始から終了までの時間である。運用計画の作成者は、例えば「拘束時間が１２時間を越えないようにする」という勤務条件を入力装置３００から配置決定装置１００に入力することができる。なお、拘束時間に乗務員が担当する各乗務の間には、休憩時間が設けられてもよい。
【００２４】
さらに入力装置３００は、運用計画の作成者の操作に応じて、コストの評価値を算出するための各変数に乗じる係数（評価値パラメータ）を配置決定装置１００に出力する。
【００２５】
表示装置４００は、配置決定装置１００が算出した乗務員区所の最適な配置、及び乗務員の最適な行路を表示画面（不図示）に表示する。なお、乗務員が勤務を開始した駅で勤務を終了させるものとするため、行路は２つ以上の乗務の組み合わせとなる。
【００２６】
配置決定装置１００は、列車ダイヤのデータ、候補駅、コストの評価値を算出するための各変数に乗じる係数（評価値パラメータ）、勤務条件（乗務員勤務条件パラメータ）等を取得し、そのデータの処理結果を表示装置４００に表示させる。配置決定装置１００は演算部１１０に、データ取得部１１１と、候補取得部１１２と、係数取得部１１３と、行路列挙部１１４と、評価関数生成部１１５と、制約条件生成部１１６と、算出部１１７を備える。
【００２７】
データ取得部１１１は、データベース２００に列車ダイヤを要求し、データベース２００から取得した列車ダイヤのデータを行路列挙部１１４及び制約条件生成部１１６に出力する。
【００２８】
図２は、本発明の一実施形態における列車ダイヤの一例を示す図である。一例として、本実施形態では、Ａ駅、Ｂ駅、及びＣ駅があり、１０個の乗務があるものとする。また、各乗務は、いずれかの乗務員（運転士）が担当しなければならないものとする。
【００２９】
図３は、本発明の一実施形態における図２の列車ダイヤのデータを示す図である。例えば、乗務１は、起点を「Ａ駅」と、終点を「Ｂ駅」とする乗務であり、起点の出発時刻を「６：００」と、終点の到着時刻を「７：００」とする乗務であることが示されている。乗務２〜１０についても同様のデータが示されている。このほか、列車ダイヤのデータには、その他のデータ、例えば乗務に使用される列車の列車番号が含まれていてもよい。
【００３０】
次に、候補取得部１１２（図１）について説明する。候補取得部１１２は、運用計画の作成者の操作により入力装置３００から入力された候補駅データを取得し、取得した候補駅データを行路列挙部１１４と評価関数生成部１１５と制約条件生成部１１６に出力する。
【００３１】
係数取得部１１３は、運用計画の作成者の操作により入力装置３００から入力された、コストの評価値を算出するための各変数の係数データ（評価値パラメータ）を取得する。係数取得部１１３は、コストの評価値を算出するための評価関数の各変数に乗じる係数として、取得した係数データ（評価値パラメータ）を評価関数生成部１１５に出力する。
【００３２】
コストについて説明する。図４は、本発明の一実施形態における３つの乗務員区所配置案を比較する表である。乗務員区所の最適な配置は、コストによって評価される。ここで、一例として、Ａ駅に乗務員区所を配置した場合のコスト（乗務員区所配置コスト）を値「２」と、Ｂ駅に乗務員区所を配置した場合のコストを値「３」と、Ｃ駅に乗務員区所を配置した場合のコストを値「２」とする。また、乗務員１人あたりのコスト（乗務員コスト）は値「１」であるものとする。以下、Ａ駅に配置された乗務員区所を「Ａ区所」と、Ｂ駅に配置された乗務員区所を「Ｂ区所」と、Ｃ駅に配置された乗務員区所を「Ｃ区所」と称する。
【００３３】
図４に示す乗務員区所配置案の場合、図４（Ａ）の配置を採用した場合の総コストは、乗務員区所のコスト「３」と乗務員のコスト「７」の合計である「１０」となる。同様に、図４（Ｂ）の配置を採用した場合の総コストは「８」と、図４（Ｃ）の配置を採用した場合の総コストは「９」となることが示されている。したがって、図４に示す乗務員区所配置案では、乗務員区所の最適な配置は、総コスト（評価値）が最小となる図４（Ｂ）の配置であることが判る。
【００３４】
次に、行路列挙部１１４（図１）について説明する。行路列挙部１１４には、データ取得部１１１から列車ダイヤのデータと、候補取得部１１２から候補駅データと、運用計画の作成者の操作により入力装置３００から勤務条件（乗務員勤務条件パラメータ）とが入力される。行路列挙部１１４は、これらのデータに基づき、起点及び終点が一致する行路を候補駅ごとに列挙し、列挙した行路データを評価関数生成部１１５及び制約条件生成部１１６に出力する。
【００３５】
行路の列挙手順について説明する。行路の列挙手順には、次のようにバックトラック法を用いてもよい。図５は、本発明の一実施形態におけるＡ区所のネットワークを示す図である。行路列挙部１１４は、ノード及びアークで構成されるネットワークを各区所について作成する。以下、図において、ノードを丸印、アークを矢印で示す。
【００３６】
ノードには、始点ノード「ｓ」、終点ノード「ｔ」、乗務ノード「数字（番号）」の３種類がある。ここで、始点ノードは勤務を開始する駅を示す。また、終点ノードは勤務を終了する駅を示す。さらに、各乗務ノードの数字は、それぞれ乗務１〜１０の番号を表す。
【００３７】
アークはノード間のつなぎを表す。例えば、図５において乗務ノード１から乗務ノード２につながっているアークは、乗務員が乗務１の次に乗務２を担当することができることを示す。また例えば、始点ノードｓからは、乗務ノード１及び７につながっているが、これは、Ａ区所において、勤務を乗務１又は乗務７から開始することができることを示す。同様に、終点ノードｔには、乗務ノード４及び１０からつながっているが、これは、乗務４又は乗務１０を終了すれば、勤務が終了することを示す。
【００３８】
ここで、行路列挙部１１４は、明らかに無駄なアークをつなげなくてもよいものとする。例えば、乗務ノード１から１０にアークを直接つなげることは可能ではあるが、「拘束時間が１２時間を越えない」という勤務条件を考慮すれば、乗務ノード１から１０にアークを直接つなげることは明らかに無駄である。このため、行路列挙部１１４は、図５の乗務ノード１から１０にはアークをつなげていない。
【００３９】
また図２によれば、例えば乗務１を終了後に乗務５を担当した場合、乗務員がＣ駅からＡ駅に戻る時刻は「２４：００」となるため、拘束時間が１２時間を超えてしまう。しかし、行路列挙部１１４が行路を列挙する際にそのことを判明させるためには、乗務ノード１から５にアークをつなげておき、勤務時間を検討することが必要である。このため、明らかに無駄なアーク以外は、アークをつなげておくものとする。
【００４０】
行路列挙のための探索について説明する。原則は、始点ノードから探索を開始し、終了ノードにたどり着けば、その過程（経路）が行路となる。ただし、その探索の途中で、勤務条件（拘束時間が１２時間を超えない等）を満たさないことが判明した場合、行路列挙部１１４は、１つ前のノードに戻る。行路列挙部１１４は、この手順を繰り返し、すべての探索を終了すると、Ａ区所の行路をすべて列挙することができる。
【００４１】
図６は、本発明の一実施形態におけるＡ区所のネットワークにおいて、終点ノードに達するまでを示す図である。行路列挙部１１４は、まず始点ノードｓから探索を始める。以下では、終点ノードｔを最優先とし、後続ノードに未選択（未探索）の乗務ノード（以下、「未選択ノード」と称する）が複数ある場合、小さい番号の乗務ノードを優先して選択し、その乗務ノードを探索するものとする。
【００４２】
始点ノードｓからは、乗務ノード１又は７につながるアークがある。このため行路列挙部１１４は、乗務ノード１に進む。次に行路列挙部１１４は、勤務条件を満たすか否かを確認する。この場合、拘束時間は１２時間を超えてないので、行路列挙部１１４は、乗務ノード２に進む。以下、同様の手順（探索）を繰り返すことで、行路列挙部１１４は、終点ノードｔに達する。このようにして探索された過程（経路）「乗務１→乗務２→乗務３→乗務４」が１本の行路である。
【００４３】
終点ノードｔに達した場合、行路列挙部１１４は、１つ前の乗務ノードに戻って、探索を続ける。図７は、本発明の一実施形態におけるＡ区所のネットワークにおいて、乗務８ノードに達するまでを示す図である。終点ノードｔに達したため、行路列挙部１１４は、乗務ノード４に戻り、乗務ノード７に進む。ここで、勤務条件を満たすか否かを確認する。乗務ノード７に進んだ段階で勤務条件を満たしているため、行路列挙部１１４は乗務ノード８に進む。さらに、乗務ノード８に進んだ段階で勤務条件を満たすか否かを確認した結果、拘束時間が１２時間を超えることが判明する。このため行路列挙部１１４は、この過程（経路）における以降の探索を終了し、１つ前の乗務ノードに戻って、探索を続ける。
【００４４】
図８は、本発明の一実施形態におけるＡ区所のネットワークにおいて、乗務ノード９に達するまでを示す図である。次に、行路列挙部１１４は乗務ノード７に戻り、乗務ノード１０に進む。ここで、勤務条件を満たすか否かを確認した結果、拘束時間が１２時間を超えることが判明したため、行路列挙部１１４は、この過程（経路）における以降の探索を終了する。
【００４５】
次に、行路列挙部１１４は再び乗務ノード７に戻る。ここで行路列挙部１１４は、乗務ノード７から進むことのできる乗務ノードをすべて探索しているので、さらに乗務ノード４に戻る。同様の理由で、行路列挙部１１４は、さらに乗務ノード３に戻る。
【００４６】
次に、行路列挙部１１４は乗務ノード５に進み、勤務条件を満たすか否かを確認する。さらに、行路列挙部１１４は乗務ノード９に進む。ここで、勤務条件を満たすか否かを確認した結果、拘束時間が１２時間を超えることが判明したため、行路列挙部１１４は、この過程（経路）における以降の探索を終了する。このようにして、行路列挙部１１４はＡ区所の行路を列挙する。
【００４７】
上記の行路列挙手順をまとめると、図９に示すフローチャートとなる。まず、行路列挙部１１４は、未探索の乗務員区所から乗務員区所を１つ選択する。未探索のＡ区所、Ｂ区所、Ｃ区所がある場合、例えば、Ａ区所を選択する（ステップＳａ１）。行路列挙部１１４は、選択した乗務員区所のネットワークを作成する（ステップＳａ２）。また行路列挙部１１４は、作成したネットワークの始点ノード（初期ノード）を選択する（ステップＳａ３）。
【００４８】
次に、行路列挙部１１４は、後続ノードに未選択ノードがあるか否かを判定する（ステップＳa４）。未選択ノードがある場合（Ｓａ４：Ｙｅｓ）、後続ノードの未選択ノードから乗務ノードを選択する（ステップＳａ５）。
【００４９】
次に、行路列挙部１１４は、その乗務ノードを選択したことで、勤務条件を満たすか否かを判定する（ステップＳａ６）。勤務条件を満たす場合（Ｓａ６：Ｙｅｓ）、行路列挙部１１４は、そのノードが終点ノードであるか否かを判定する（ステップＳａ７）。終点ノードである場合（Ｓａ７：Ｙｅｓ）、行路列挙部１１４は、探索過程（経路）を新たな行路として追加（記憶）し（ステップＳａ８）、１つ前のノードに戻る（ステップＳａ９）。さらに、行路列挙部１１４はステップＳａ４に戻る（ステップＳａ９）。
【００５０】
ステップＳａ４において未選択ノードがない場合（Ｓａ４：Ｎｏ）、行路列挙部１１４は、探索中のノードが始点ノードであるか否かを判定する（ステップＳａ１０）。始点ノードである場合（Ｓａ１０：Ｙｅｓ）、行路列挙部１１４は、探索を終了する（ステップＳａ１１）。
【００５１】
次に、行路列挙部１１４は、未探索の乗務員区所があるか否かを判定する（ステップＳａ１２）。未探索の乗務員区所がある場合（Ｓａ１２：Ｙｅｓ）、行路列挙部１１４は、ステップＳａ１に戻る。一方、未探索の乗務員区所がない場合（Ｓａ１２：Ｎｏ）、行路列挙部１１４は探索を終了する。探索が終了すれば、すべての乗務員区所の行路が列挙される。
【００５２】
ステップＳａ６において勤務条件を満たさない場合（Ｓａ６：Ｎｏ）、行路列挙部１１４は、ステップＳａ９に進む。また、ステップＳａ７において終点ノードでない場合（Ｓａ７：Ｎｏ）、行路列挙部１１４は、ステップＳａ４に戻る。また、ステップＳａ１０において始点ノードでない場合（Ｓａ１０：Ｎｏ）、行路列挙部１１４は、ステップＳａ９に進む。
【００５３】
図１０は、本発明の一実施形態におけるＡ区所の行路を示す図である。ここで、丸印から始まり三角印で終わる１本の経路は、１本の行路を表す。ここで、丸印及び三角印のアルファベットは区所を表し、数字は行路の番号を表す。したがって、Ａ区所にはＡ１〜Ａ４の４本の行路があることが判る。また例えば、行路Ａ１を担当する乗務員は、Ａ駅から勤務を開始し、「乗務１→乗務２→乗務３→乗務４」の順に乗務を担当して、Ａ駅で勤務を終了することが判る。
【００５４】
同様に、行路列挙部１１４は、Ｂ区所の行路を列挙する。図１１は、本発明の一実施形態におけるＢ区所のネットワークを示す図である。ここで、乗務を開始する駅がＢ駅である各乗務ノードには、始点ノードｓからアークがつながっている。また、乗務を終了する駅がＢ駅である各乗務ノードには、終点ノードｔからアークがつながっている。さらに、乗務ノード間のアークは、Ａ区所の場合（図５）と同じである。
【００５５】
図１２は、本発明の一実施形態におけるＢ区所の最初の行路ができるまでを示す図である。その探索方法（行路の列挙手順）は、Ａ区所の場合と同様である。
【００５６】
図１３は、本発明の一実施形態におけるＢ区所の行路を示す図である。Ｂ区所にはＢ１〜Ｂ５の５本の行路があることが判る。また例えば、行路Ｂ１を担当する乗務員は、Ｂ駅から勤務を開始し、「乗務２→乗務３」の順に乗務を担当して、Ｂ駅で勤務を終了することが判る。
【００５７】
同様に、行路列挙部１１４は、Ｃ区所の行路を列挙する。図１４は、本発明の一実施形態におけるＣ区所のネットワークを示す図である。ここで、乗務を開始する駅がＣ駅である各乗務ノードには、始点ノードｓからアークがつながっている。また、乗務を終了する駅がＣ駅である各乗務ノードには、終点ノードｔからアークがつながっている。さらに、乗務ノード間のアークは、Ａ区所及びＢ区所の場合（図５、図１１）と同じである。
【００５８】
図１５は、本発明の一実施形態におけるＣ区所の行路を示す図である。Ｃ区所にはＣ１〜Ｃ４の４本の行路があることが判る。また例えば、行路Ｃ１を担当する乗務員は、Ｃ駅から勤務を開始し、「乗務３→乗務５」の順に乗務を担当して、Ｃ駅で勤務を終了することが判る。このようにして、行路列挙部１１４はＡ〜Ｃ区所（候補駅）の行路を列挙する。
【００５９】
次に、評価関数生成部１１５（図１）について説明する。評価関数生成部１１５には、候補取得部１１２から候補駅データ、及び係数データ（評価値パラメータ）と、行路列挙部１１４から行路データとが入力される。評価関数生成部１１５は、行路データ、候補駅データ、及び係数データに基づいて評価関数を生成し、生成した評価関数を算出部１１７に出力する。ここで、２種類の変数を次のように定義する。
【００６０】
候補駅に乗務員区所を配置する（候補を採用する）か否かを示す変数
「ＹＡ：Ａ区所を  配置する＝１，配置しない＝０」
「ＹＢ：Ｂ区所を  配置する＝１，配置しない＝０」
「ＹＣ：Ｃ区所を  配置する＝１，配置しない＝０」
【００６１】
行路を選択するか否かを示す変数
「ＸＡ１：行路Ａ１を  選択する＝１，選択しない＝０」
「ＸＡ２：行路Ａ２を  選択する＝１，選択しない＝０」
…
「ＸＣ４：行路Ｃ４を  選択する＝１，選択しない＝０」
【００６２】
評価関数生成部１１５は、これらの変数を用い、評価関数の値（評価値）が「乗務員区所配置コスト及び乗務員コスト」の総和となるよう、評価関数を「２ＹＡ＋３ＹＢ＋２ＹＣ＋ＸＡ１＋ＸＡ２＋ＸＡ３＋ＸＡ４＋ＸＢ１＋ＸＢ２＋ＸＢ３＋ＸＢ４＋ＸＢ５＋ＸＣ１＋ＸＣ２＋ＸＣ３＋ＸＣ４」と生成する。ここで、各変数には入力装置３００から取得した係数データがそれぞれ乗算されている。例えば、「ＹＡ」には、Ａ区所の乗務員区所配置コスト「２」が乗算されている。また例えば、「ＸＡ１」には、Ａ区所に配置された乗務員の乗務員コスト「１」が乗算されている。したがって、評価関数の値（評価値）が最小であれば、総コストが最小となる。
【００６３】
次に、制約条件生成部１１６について説明する。制約条件生成部１１６には、データ取得部１１１から列車ダイヤのデータと、候補取得部１１２から候補駅データと、行路列挙部１１４から行路データが入力される。制約条件生成部１１６は、これらのデータに基づいて制約条件を生成し、制約条件を算出部１１７に出力する。
【００６４】
ここで、次の制約条件があるものとする。
第１の制約条件：すべての乗務について、１人以上の乗務員が担当する。
第２の制約条件：乗務員区所を配置した駅にのみ、乗務員を配置する。
第３の制約条件：各変数は、値「１」又は「０」のいずれかの値をとる。
【００６５】
図１６は、本発明の一実施形態における乗務と行路の関係を示す表である。図１６において、丸印のある箇所は、その乗務が含まれる行路を示す。例えば、乗務１〜４は行路Ａ１に含まれることが示されている。制約条件生成部１１６は、乗務と行路の関係（図１６）に基づいて、第１の制約条件を次のように生成する。
【００６６】
「ＸＡ１＋ＸＡ２＞＝１」        ←  乗務１を含む行路は、行路Ａ１、Ａ２のみ
「ＸＡ１＋ＸＢ１＋ＸＢ２＞＝１」←  乗務２を含む行路は、行路Ａ１、Ｂ１、Ｂ２のみ
…
「ＸＡ３＋ＸＡ４＞＝１」        ←  乗務１０を含む行路は、行路Ａ３、Ａ４のみ
制約条件生成部１１６は、全１０乗務について同様に生成し、合計１０個（乗務の数）の式を生成する。
【００６７】
また、制約条件生成部１１６は、乗務と行路の関係（図１６）に基づいて、第２の制約条件を次のように生成する。
【００６８】
「ＹＡ−ＸＡ１＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ１を選択しない
「ＹＡ−ＸＡ２＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ２を選択しない
「ＹＡ−ＸＡ３＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ３を選択しない
「ＹＡ−ＸＡ４＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ４を選択しない
制約条件生成部１１６は、Ｂ区所及びＣ区所について同様に生成し、合計１３個（行路の本数）の式を生成する。
【００６９】
また、制約条件生成部１１６は、第３の制約条件を次のように生成する。
「ＹＡ＝１又は０」，「ＹＢ＝１又は０」，「ＹＣ＝１又は０」，「ＸＡ１＝１又は０」，「ＸＡ２＝１又は０」，…，「ＸＣ４＝１又は０」
【００７０】
次に、制約条件生成部１１６は、各変数の組み合わせを少なくするため、制約条件を抽出する。上記の評価関数は、１６個の項からなることが判る。したがって、評価関数の各変数が値「１」又は「０」の２値をとる場合、その組み合わせは、２の１６乗＝６５５３６通りにもなる。
【００７１】
そこで、制約条件生成部１１６は、乗務と行路の関係（図１６）に基づいて、制約条件を抽出し、これを生成する。上記の例では、次のように生成することができる。
【００７２】
「ＹＡ＝１」  ←  乗務１を含む行路は、Ａ区所の行路のみ（Ａ区所は必要である）。
「ＹＢ＋ＹＣ＞＝１」  ←  乗務５を含む行路は、Ｂ区所及びＣ区所のみ。
…
「ＹＡ＝１」  ←  乗務１０を含む行路は、Ａ区所の行路のみ（Ａ区所は必要である）。
制約条件生成部１１６は、この例では１０個（乗務の数）の制約条件を新たに生成することができる。
【００７３】
なお、乗務員区所を必ず配置したい駅がある場合、及び必ず採用したい行路がある場合など、運用計画の作成者は、入力装置３００を用いて各変数を値「１」又は「０」に設定することができるとしてもよい。
【００７４】
算出部１１７には、評価関数生成部１１５により生成された評価関数と、制約条件生成部１１６により生成された制約条件が入力される。算出部１１７は、これらに基づいて評価関数の値（評価値）を算出し、表示装置４００に出力する。算出部１１７の演算処理は、第１〜３の制約条件と、抽出された制約条件を用いることで、各変数をすべて単純に組合せて演算処理した場合と比べ、大幅に高速化することができる。
【００７５】
上記の例において、評価値が最小となる場合の各変数の値「ＹＡ＝１，ＹＢ＝０，ＹＣ＝１，ＸＡ１＝１，ＸＡ２＝０，ＸＡ３＝１，ＸＡ４＝０，ＸＢ１＝０，ＸＢ２＝０，ＸＢ３＝０，ＸＢ４＝０，ＸＢ５＝０，ＸＣ１＝１，ＸＣ２＝０，ＸＣ３＝０，ＸＣ４＝１」が算出部１１７によって算出される。
【００７６】
図１７は、本発明の一実施形態における算出された最適な乗務員区所配置案を示す図である。算出結果から、この乗務員区所配置案では、評価関数の値（評価値）は「９」となる。また、候補駅であったＡ〜Ｃ駅のうちＡ駅及びＣ駅が乗務員区所として採用され、それぞれにＡ区所及びＣ区所が配置されたことが判る。さらに、行路Ａ１、Ａ３、Ｃ１、Ｃ４が選択されたことも判る。
【００７７】
算出部１１７は、これらの算出結果を表示装置４００に出力する。なお、乗務３には２人の乗務員が割り当てられているが（行路Ａ１及びＣ１の重複部分）、いずれかの乗務員が乗務を担当し、残りの乗務員はその列車に同乗するとしてもよい。
【００７８】
図１８は、本発明の一実施形態における配置決定装置１００の動作を説明するフローチャートである。まず、データ取得部１１１は、列車ダイヤのデータを取得する（ステップＳ１）。次に候補取得部１１２は、乗務員区所の配置候補駅を取得する（ステップＳ２）。さらに、係数取得部１１３は、コストの評価値を算出するための評価関数の各変数に乗じる係数（評価値パラメータ）を取得する（ステップＳ３）。
【００７９】
行路列挙部１１４は、列車ダイヤのデータと勤務条件（乗務員勤務条件パラメータ）を取得し（ステップＳ４）、区所の候補ごとに行路を列挙する（ステップＳ５）。次に、評価関数生成部１１５は、評価関数を生成する（ステップＳ６）。さらに、制約条件生成部１１６は、制約条件を生成する（前処理）（ステップＳ７）。
【００８０】
算出部１１７は、評価値が最小となる変数を算出する（ステップＳ８）。表示装置４００は、配置決定装置１００が算出した乗務員区所の最適な配置（区所配置案）、及び乗務員の最適な行路を表示画面（不図示）に表示する（ステップＳ９）。
【００８１】
以上が配置決定装置１００の一連の動作であるが、運用計画の作成者は、評価関数の各種パラメータを変更し、複数の区所配置案を算出させた上で、乗務員区所の配置箇所を決定してもよい。
【００８２】
例えば、運用計画の作成者は、乗務員区所配置コストを変更してもよい。一例として、Ａ駅に乗務員区所を配置した場合のコスト（乗務員区所配置コスト）を値「２」と、Ｂ駅に乗務員区所を配置した場合のコストを値「１」と、Ｃ駅に乗務員区所を配置した場合のコストを値「３」と変更したものとする。
【００８３】
これにより、評価関数は「２ＹＡ＋ＹＢ＋３ＹＣ＋ＸＡ１＋ＸＡ２＋ＸＡ３＋ＸＡ４＋ＸＢ１＋ＸＢ２＋ＸＢ３＋ＸＢ４＋ＸＢ５＋ＸＣ１＋ＸＣ２＋ＸＣ３＋ＸＣ４」と生成される。ここで、制約条件は上記と同じであるものとする。
【００８４】
したがって、評価値が最小となる場合の各変数の値「ＹＡ＝１，ＹＢ＝１，ＹＣ＝０，ＸＡ１＝１，ＸＡ２＝０，ＸＡ３＝１，ＸＡ４＝０，ＸＢ１＝０，ＸＢ２＝１，ＸＢ３＝０，ＸＢ４＝１，ＸＢ５＝０，ＸＣ１＝０，ＸＣ２＝０，ＸＣ３＝０，ＸＣ４＝０」が算出部１１７によって算出される。
【００８５】
図１９は、本発明の一実施形態において、乗務員区所配置コストを変更した場合における算出された最適な乗務員区所配置案を示す図である。算出結果から、この乗務員区所配置案では、評価関数の値（評価値）は「７」となる。また、候補駅であったＡ〜Ｃ駅のうちＡ駅及びＢ駅が採用され、それぞれにＡ区所及びＢ区所が配置されたことが判る。さらに、行路Ａ１、Ａ３、Ｂ２、Ｂ４が選択されたことも判る。
【００８６】
また例えば、運用計画の作成者は、乗務員の勤務条件を変更してもよい。一例として、乗務員に休憩時間を取らせるために、「Ａ駅からＣ駅」及び「Ｃ駅からＡ駅」にはそれぞれ連続して乗務できないものとする。
【００８７】
したがって、行路列挙部１１４は、行路Ａ１、Ａ３、及びＣ２を列挙することができなくなる。このためＡ区所及びＣ区所の行路は、図２０及び２１に示す行路のみとなる。ここで、図２０は、本発明の一実施形態において、乗務員の勤務条件を変更した場合におけるＡ区所の行路を示す図である。また、図２１は、本発明の一実施形態において、乗務員の勤務条件を変更した場合におけるＣ区所の行路を示す図である。
【００８８】
これにより、評価関数は「２ＹＡ＋３ＹＢ＋２ＹＣ＋ＸＡ２＋ＸＡ４＋ＸＢ１＋ＸＢ２＋ＸＢ３＋ＸＢ４＋ＸＢ５＋ＸＣ１＋ＸＣ３＋ＸＣ４」と生成される。
【００８９】
また第１の制約条件は、ＸＡ１、ＸＡ３、ＸＣ２をすべて消すことで、次のようになる。
「ＸＡ２＞＝１」        ←  乗務１を含む行路は、行路Ａ２のみ
「ＸＢ１＋ＸＢ２＞＝１」←  乗務２を含む行路は、行路Ｂ１、Ｂ２のみ
…
「ＸＡ４＞＝１」        ←  乗務１０を含む行路は、行路Ａ４のみ
【００９０】
さらに第２の制約条件は、ＸＡ１、ＸＡ３、ＸＣ２をすべて消すことで、次のようになる。
「ＹＡ−ＸＡ２＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ２を選択しない
「ＹＡ−ＸＡ４＞＝０」  ←  Ａ区所を配置しない場合、行路Ａ４を選択しない
制約条件生成部１１６は、Ｂ区所及びＣ区所について同様に生成し、合計１０個（行路の本数）の式を生成する。ここで、その他の制約条件は上記と同じであるものとする。
【００９１】
したがって、評価値が最小となる場合の各変数の値「ＹＡ＝１，ＹＢ＝１，ＹＣ＝０，ＸＡ２＝１，ＸＡ４＝１，ＸＢ１＝１，ＸＢ２＝１，ＸＢ３＝０，ＸＢ４＝１，ＸＢ５＝１，ＸＣ１＝０，ＸＣ３＝０，ＸＣ４＝０」が算出部１１７によって算出される。
【００９２】
図２２は、本発明の一実施形態において、乗務員の勤務条件を変更した場合における最適な乗務員区所配置案を示す図である。算出結果から、この乗務員区所配置案では、評価関数の値（評価値）は「１１」となる。また、この乗務員区所配置案では、候補駅であったＡ〜Ｃ駅のうちＡ駅及びＢ駅が乗務員区所として採用され、それぞれにＡ区所及びＢ区所が配置されたことが判る。さらに、行路Ａ２、Ａ４、Ｂ１、Ｂ２、Ｂ４、Ｂ５が選択されたことも判る。
【００９３】
以上のように、配置決定装置が、評価関数に基づいてコストの評価値が最小となるパラメータを算出する。これにより、配置決定装置は、既存の乗務員区所の配置箇所を白紙状態に戻し、乗務員区所の配置箇所をすべて新規とした上で、輸送量（列車ダイヤ）に基づいて、乗務員区所の最適な配置、及び乗務員の最適な行路を決定することができる。
【００９４】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００９５】
例えば、配置決定装置１００は、記録媒体の読取部をさらに備え、データベース２００の代わりに記録媒体から列車ダイヤのデータを取得し、上述の処理を実行してもよい。
【００９６】
また、図９、図１８に示す各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、実行処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）や周辺機器等のハードウェアを含むものであってもよい。
【００９７】
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【００９８】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。
さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【符号の説明】
【００９９】
１〜１０…乗務  １００…配置決定装置  １１０…演算部  １１１…データ取得部  １１２…候補取得部  １１３…係数取得部  １１４…行路列挙部  １１５…評価関数生成部  １１６…制約条件生成部  １１７…算出部  ２００…データベース  ３００…入力装置  ４００…表示装置
【図１】
2011034499.tif 000003
【図２】
2011034499.tif 000004
【図３】
2011034499.tif 000005
【図４】
2011034499.tif 000006
【図５】
2011034499.tif 000007
【図６】
2011034499.tif 000008
【図７】
2011034499.tif 000009
【図８】
2011034499.tif 000010
【図９】
2011034499.tif 000011
【図１０】
2011034499.tif 000012
【図１１】
2011034499.tif 000013
【図１２】
2011034499.tif 000014
【図１３】
2011034499.tif 000015
【図１４】
2011034499.tif 000016
【図１５】
2011034499.tif 000017
【図１６】
2011034499.tif 000018
【図１７】
2011034499.tif 000019
【図１８】
2011034499.tif 000020
【図１９】
2011034499.tif 000021
【図２０】
2011034499.tif 000022
【図２１】
2011034499.tif 000023
【図２２】
2011034499.tif 000024