(57)【特許請求の範囲】
【請求項１】
情報を格納する記憶部と、情報を出力する出力部と、情報を入力する入力部と、プログラムを実行する処理装置とを有するコンピュータにより実現される資源運用計画作成装置であって、
該記憶部は輸送サービスの運行スケジュール情報を格納しており、
該処理装置は、プログラムを実行することにより；
該記憶部に予め格納された輸送サービスの運行スケジュール情報を読込む運行スケジュール読込部と、
該運行スケジュール情報に基づいて運行スケジュールに含まれる複数の各輸送行程について、輸送行程の始発場所、始発時間、終着場所、および終着時間を少なくとも属性として有するノードを作成し、各ノードの属性に基づいて同じ資源を用いて連続した運行が可能な輸送行程を表すノード間を接続したパスを作成して、輸送行程のネットワークモデルを作成し、
更に、各資源の運用開始場所と各資源を利用可能な時間帯と該資源を識別する情報を少なくとも属性として有する運用開始ノードと、運用終了場所と該資源を識別する情報を少なくとも属性として有する運用終了ノードを作成し、運用開始ノードの属性値とネットワークモデルを構成する他のノードの属性値とに基づいて、時刻と場所の接続が成り立つように、輸送行程を表すノードと運用開始ノードとを接続するパスを作成し、運用終了ノードの運用終了場所の属性値とネットワークモデルを構成する他のノードの終着場所の属性値が一致するように、輸送行程を表すノードと運用終了ノードとを接続するパスを作成し、同じ資源識別情報を属性とする運用開始ノードと運用終了ノードとを接続するパスを作成し、作成したネットワークモデルに追加するネットワーク作成部と、
該運行スケジュール情報に基づいて、資源の運用終了場所を元の計画から変更しないという条件を達成するために複数の資源を割り当てる候補となる輸送行程を抽出する併合候補判定部と、
複数の資源を割り当て可能な輸送行程を表すノードを複製して併合ノードを作成し、併合ノードの属性とネットワークモデルを構成する他のノードの属性とに基づいて、併合ノードと複製元のノードが接続しているノードとを接続するパスをネットワークモデルに追加する併合候補反映部と、
ネットワークモデルを構成する併合ノード以外の各ノードに、一つの資源が割り当てられるような複数のパスから構成されるパスの組合せをネットワークモデルから抽出し、更に抽出された組合せについて、該組合せを構成する複数のパスの各々に資源を割り当てることで、運用終了場所を元の計画から変更しないという条件を満たす資源の運用計画を作成して該運用計画を、該出力部に出力する計画作成部とを有する、ことを特徴とする資源運用計画作成装置。
【請求項２】
前記併合候補判定部は、
運用終了可能場所ごとに、その場所を運用終了とする資源の数を算出する手段と、
各資源の運用終了場所を元の計画から変更しないという条件の代わりに、前記算出した値を元の計画から変更しないという条件を満たすように複数の資源を割り当てる候補となる輸送行程を抽出する手段を有する請求項１に記載の資源運用計画作成装置。
【請求項３】
前記併合候補判定部は、各資源の運用終了場所、または各運用終了可能場所を運用終了とする資源の数を、元の計画から変更しないという条件を満たすように回送行程を追加する、請求項１又は２記載の資源運用計画作成装置。
【請求項４】
前記併合候補判定部は、複数の資源を割り当て可能な輸送行程の指定を、該入力部から受け付けた指定を基に複数の資源を割り当てる候補となる輸送行程を生成する、請求項１乃至３の何れかの項記載の資源運用計画作成装置。
【請求項５】
前記計画作成部は、資源を併合した際の各資源の併合位置を、各資源が併合場所に到着する順序に従って算出し、併合駅への到着順序を考慮したうえで、前記算出した併合位置を各資源に設定する、請求項１乃至４の何れかの項記載の資源運用計画作成装置。
【請求項６】
前記記憶部は、運行を開始する前に計画されている行路に関する元の行路情報と、輸送サービスの最小単位ごとにその行程を定義した運行情報と、輸送サービスに用いる列車に関する資源情報と、１つの資源が輸送サービスの最小単位をどのような順序で実行していくかを定義する行路情報と、複数の資源を併合する作業または分離する作業を実施可能な場所を定義する併合可能場所情報と、併合候補として判定した行路又は予め併合候補が決まっている場合はその併合候補に関する併合候補情報に関する輸送サービスの運行スケジュール情報を格納する請求項１乃至５の何れかの項記載の資源運用計画作成装置。
【請求項７】
輸送サービスの運行スケジュール情報を格納する記憶部と、情報を出力する出力部と、情報を入力する入力部と、プログラムを実行する処理装置とを有するコンピュータにより実現される資源運用計画作成方法であって、
該処理装置でプログラムを実行することにより；
該記憶部に格納された該運行スケジュール情報を読込み、
該運行スケジュール情報に基づいて運行スケジュールに含まれる複数の各輸送行程について、該輸送行程の始発場所、始発時間、終着場所、および終着時間を少なくとも属性として有するノードを作成し、各ノードの属性に基づいて同じ資源を用いて連続した運行が可能な輸送行程を表すノード間を接続したパスを作成して、輸送行程のネットワークモデルを作成し、
各資源の運用開始場所と各資源を利用可能な時間帯と該資源を識別する情報を少なくとも属性として有する運用開始ノードと、運用終了場所と該資源を識別する情報を少なくとも属性として有する運用終了ノードを作成し、運用開始ノードの属性値とネットワークモデルを構成する他のノードの属性値とに基づいて、時刻と場所の接続が成り立つように、輸送行程を表すノードと運用開始ノードとを接続するパスを作成し、運用終了ノードの運用終了場所の属性値とネットワークモデルを構成する他のノードの終着場所の属性値が一致するように、輸送行程を表すノードと運用終了ノードとを接続するパスを作成し、同じ資源識別情報を属性とする運用開始ノードと運用終了ノードとを接続するパスを作成し、作成したネットワークモデルに追加し、
該運行スケジュール情報に基づいて、資源の運用終了場所を元の計画から変更しないという条件を達成するために複数の資源を割り当てる候補となる輸送行程を抽出し、
複数の資源を割り当て可能な輸送行程を表すノードを複製して併合ノードを作成し、併合ノードの属性とネットワークモデルを構成する他のノードの属性とに基づいて、併合ノードと複製元のノードが接続しているノードとを接続するパスをネットワークモデルに追加し、
ネットワークモデルを構成する併合ノード以外の各ノードに、一つの資源が割り当てられるような複数のパスから構成されるパスの組合せをネットワークモデルから抽出し、
抽出された組合せについて、該組合せを構成する複数のパスの各々に資源を割り当てることで、運用終了場所を元の計画から変更しないという条件を満たす資源の運用計画を作成して該運用計画を該出力部に出力することを特徴とする資源運用計画作成方法。
【請求項８】
運用終了可能場所ごとに、その場所を運用終了とする資源の数を算出し、
各資源の運用終了場所を元の計画から変更しないという条件の代わりに、前記算出した値を元の計画から変更しないという条件を満たすように複数の資源を割り当てる候補となる輸送行程を抽出する請求項７に記載の資源運用計画作成方法。
【請求項９】
各資源の運用終了場所、または各運用終了可能場所を運用終了とする資源の数を、元の計画から変更しないという条件を満たすように回送行程を追加する請求項７又は８記載の資源運用計画作成方法。
【請求項１０】
複数の資源を割り当て可能な輸送行程の指定を、該入力部から受け付けた指定を基に複数の資源を割り当てる候補となる輸送行程を生成する、請求項７乃至９の何れかの項記載の資源運用計画作成方法。
【請求項１１】
資源を併合した際の各資源の併合位置を、各資源が併合場所に到着する順序に従って算出し、併合駅への到着順序を考慮したうえで、前記算出した併合位置を各資源に設定する、請求項７乃至１０の何れかの項記載の資源運用計画作成方法。
【請求項１２】
輸送サービスの運行スケジュール情報を格納する記憶部と、情報を出力する出力部と、情報を入力する入力部と、プログラムを実行する処理装置とを有するコンピュータで実行される資源運用計画作成のためのプログラムであって、該処理装置でプログラムを実行することにより；
該記憶部に予め格納された輸送サービスの運行スケジュール情報を読込む運行スケジュール読込部と、
該運行スケジュール情報に基づいて運行スケジュールに含まれる複数の各輸送行程について、輸送行程の始発場所、始発時間、終着場所、および終着時間を少なくとも属性として有するノードを作成し、各ノードの属性に基づいて同じ資源を用いて連続した運行が可能な輸送行程を表すノード間を接続したパスを作成して、輸送行程のネットワークモデルを作成し、
更に、各資源の運用開始場所と各資源を利用可能な時間帯と該資源を識別する情報を少なくとも属性として有する運用開始ノードと、運用終了場所と該資源を識別する情報を少なくとも属性として有する運用終了ノードを作成し、運用開始ノードの属性値とネットワークモデルを構成する他のノードの属性値とに基づいて、時刻と場所の接続が成り立つように、輸送行程を表すノードと運用開始ノードとを接続するパスを作成し、運用終了ノードの運用終了場所の属性値とネットワークモデルを構成する他のノードの終着場所の属性値が一致するように、輸送行程を表すノードと運用終了ノードとを接続するパスを作成し、同じ資源識別情報を属性とする運用開始ノードと運用終了ノードとを接続するパスを作成し、作成したネットワークモデルに追加するネットワーク作成部と、
該運行スケジュール情報に基づいて、資源の運用終了場所を元の計画から変更しないという条件を達成するために複数の資源を割り当てる候補となる輸送行程を抽出する併合候補判定部と、
複数の資源を割り当て可能な輸送行程を表すノードを複製して併合ノードを作成し、併合ノードの属性とネットワークモデルを構成する他のノードの属性とに基づいて、併合ノードと複製元のノードが接続しているノードとを接続するパスをネットワークモデルに追加する併合候補反映部と、
ネットワークモデルを構成する併合ノード以外の各ノードに、一つの資源が割り当てられるような複数のパスから構成されるパスの組合せをネットワークモデルから抽出し、更に抽出された組合せについて、該組合せを構成する複数のパスの各々に資源を割り当てることで、運用終了場所を元の計画から変更しないという条件を満たす資源の運用計画を作成して該運用計画を、該出力部に出力する計画作成部とを有する、
ことを特徴とする資源運用計画作成のためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、資源運用計画作成装置及びその方法、及びそのプログラムに係り、特に、鉄道や航空などの輸送サービスにおける移動媒体（車両や機体など）や乗務員といった資源の資源運用計画を、資源の運用終了場所を考慮して作成することを可能とする技術に関する。
【背景技術】
【０００２】
鉄道や航空などの輸送サービスでは、運行スケジュールの管理と並行して、運行に用いる資源（移動媒体等）の保守作業計画や乗務員の乗務計画も考慮する。例えば、鉄道では、車両検査の周期が法的に定められているので、列車への効率的な車両割り当てを行いつつ、検査周期を守るように検査作業を定期的に実施しなければならない。また、乗務員の連続乗務時間や勤務時間が法的に定められているので、法的な取組めを守りつつ乗務員を列車乗務に割り当てていかねばならない。このような資源の運用を考える計画のことを「資源運用計画」ということにする。
【０００３】
鉄道における資源運用計画は、車両の形式や性能などの個々の車両の特性や、駅での折返しのタイミング、検査のために車両基地へ戻す時刻などを考慮しながら、膨大な組合せの中から列車に割り当てる車両を選択しなければならず、人手作業では困難である。乗務員の運用計画も同様に、乗務員の勤務条件や乗務履歴などの個々の乗務員の特性や、駅での乗り継ぎ時間やタイミング、休憩時間などを考慮しながら、膨大な組合せの中から列車に乗務する乗務員を選択しなければならない。しかし、鉄道における資源運用計画の作成については車両と乗務員共にシステム化がまだ十分に進んでおらず、熟練者の経験を頼りに人手作業によって行われている。
【０００４】
そこで、資源運用計画を自動的に作成するアイデアがいろいろと提案されている。例えば、特許文献１および非特許文献１には、列車の運行乱れ時に乱れ回復のために変更された列車ダイヤを対象に、検査周期も考慮した資源運用計画を再作成する手段を有する旨開示されている。また、特許文献２には、予定外の検査作業を実施可能な箇所を、列車の接続間合いを基に見つけ、臨時の検査作業を挿入した資源運用計画を作成する手段を有する旨開示されている。また、特許文献３には、列車の折返しや列車に割り当てる車両に関して利用者から望ましいパターンを受付け、列車の接続に関する利用者の意図を考慮した資源運用計画を作成する手段を有する旨開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−５８７７１号公報
【特許文献２】特開２００５−２５９０５２号公報
【特許文献３】特開２００３−１５４９３９号公報
【非特許文献】
【０００６】
【非特許文献１】佐藤 圭介、福村 直登著  ダイヤ乱れ時の貨物機関車運用整理問題  IPSJ SIG Notes 2009(19), 141-144, 2009-02-26
【発明の概要】
【発明が解決しようとする課題】
【０００７】
資源運用計画の作成では、上記のような車両と乗務員の特性および運行スケジュールを満たすだけでなく、運用の規則性（運用パターンという）の確保も重要となってくる。例えば鉄道の場合では、大きな検査を控えている車両は検査の前に予備車として車両基地に一日留置しておいたり、複数の車両間で走行距離や走行日数を平準化するために予備車として留置しておく期間をあえて計画に入れ込んでいる。このような規則性は、保守作業を周期通り実施するためだけでなく、保守作業や車両保管作業を行う上で現場が普段通りに作業を行えるようにするためにも重要な要素である。また、乗務員の場合も同様に、定期的な休日を入れることや乗務時間を平準化することなどを目的とした運用パターンが存在する。
【０００８】
運行が乱れた際に計画を変更する場合には、翌日以降の運用パターンを崩さないために、一日内で資源の運用終了場所（滞泊場所という）を元の計画から変えない、または、少なくとも同じ場所で運用終了する資源の数を元の計画から変えないことが重要である。例えば鉄道では、一日の運用が終了した車両は運用終了駅構内または最寄りの車両基地に格納され、翌日もその場所から運用を開始する。運行が乱れた場合、車両が運用を終了する駅（運用終了駅という）が変わってしまうと、翌日は元の計画とは異なる列車を充当することになるため、運用パターンの崩れや検査作業の実施漏れなどが生じる。これらを防ぐため、鉄道事業者では、運用終了駅が変わった列車を必要に応じて回送として元の計画通りの駅に戻す作業を行うなどの対応を行っており、資源の運用効率の低下の原因となっている。
上記文献に開示された技術はいずれも、計画対象となっている時間範囲内において効率的な運用となるよう運用計画を作成することを目的としており、滞泊場所の条件を考慮していない。
【０００９】
本発明の目的は、運用終了場所を元の計画から変えない運用計画を作成する資源運用計画作成装置及びその方法、及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１０】
本発明に係る資源運用計画作成装置は、好ましくは、情報を格納する記憶部と、情報を出力する出力部と、情報を入力する入力部と、プログラムを実行する処理装置とを有するコンピュータにより実現される資源運用計画作成装置であって、
該記憶部は輸送サービスの運行スケジュール情報を格納しており、
該処理装置は、プログラムを実行することにより；
該記憶部に予め格納された輸送サービスの運行スケジュール情報を読込む運行スケジュール読込部と、
該運行スケジュール情報に基づいて運行スケジュールに含まれる複数の各輸送行程について、輸送行程の始発場所、始発時間、終着場所、および終着時間を少なくとも属性として有するノードを作成し、各ノードの属性に基づいて同じ資源を用いて連続した運行が可能な輸送行程を表すノード間を接続したパスを作成して、輸送行程のネットワークモデルを作成し、
更に、各資源の運用開始場所と各資源を利用可能な時間帯と該資源を識別する情報を少なくとも属性として有する運用開始ノードと、運用終了場所と該資源を識別する情報を少なくとも属性として有する運用終了ノードを作成し、運用開始ノードの属性値とネットワークモデルを構成する他のノードの属性値とに基づいて、時刻と場所の接続が成り立つように、輸送行程を表すノードと運用開始ノードとを接続するパスを作成し、運用終了ノードの運用終了場所の属性値とネットワークモデルを構成する他のノードの終着場所の属性値が一致するように、輸送行程を表すノードと運用終了ノードとを接続するパスを作成し、同じ資源識別情報を属性とする運用開始ノードと運用終了ノードとを接続するパスを作成し、作成したネットワークモデルに追加するネットワーク作成部と、
該運行スケジュール情報に基づいて、資源の運用終了場所を元の計画から変更しないという条件を達成するために複数の資源を割り当てる候補となる輸送行程を抽出する併合候補判定部と、
複数の資源を割り当て可能な輸送行程を表すノードを複製して併合ノードを作成し、併合ノードの属性とネットワークモデルを構成する他のノードの属性とに基づいて、併合ノードと複製元のノードが接続しているノードとを接続するパスをネットワークモデルに追加する併合候補反映部と、
ネットワークモデルを構成する併合ノード以外の各ノードに、一つの資源が割り当てられるような複数のパスから構成されるパスの組合せをネットワークモデルから抽出し、更に抽出された組合せについて、該組合せを構成する複数のパスの各々に資源を割り当てることで、運用終了場所を元の計画から変更しないという条件を満たす資源の運用計画を作成して該運用計画を、該出力部に出力する計画作成部とを有する、ことを特徴とする資源運用計画作成装置として構成される。
【００１１】
本発明に係る資源運用計画作成方法は、好ましくは、輸送サービスの運行スケジュール情報を格納する記憶部と、情報を出力する出力部と、情報を入力する入力部と、プログラムを実行する処理装置とを有するコンピュータにより実現される資源運用計画作成方法であって、該処理装置でプログラムを実行することにより；
該記憶部に格納された該運行スケジュール情報を読込み、
該運行スケジュール情報に基づいて運行スケジュールに含まれる複数の各輸送行程について、該輸送行程の始発場所、始発時間、終着場所、および終着時間を少なくとも属性として有するノードを作成し、各ノードの属性に基づいて同じ資源を用いて連続した運行が可能な輸送行程を表すノード間を接続したパスを作成して、輸送行程のネットワークモデルを作成し、
各資源の運用開始場所と各資源を利用可能な時間帯と該資源を識別する情報を少なくとも属性として有する運用開始ノードと、運用終了場所と該資源を識別する情報を少なくとも属性として有する運用終了ノードを作成し、運用開始ノードの属性値とネットワークモデルを構成する他のノードの属性値とに基づいて、時刻と場所の接続が成り立つように、輸送行程を表すノードと運用開始ノードとを接続するパスを作成し、運用終了ノードの運用終了場所の属性値とネットワークモデルを構成する他のノードの終着場所の属性値が一致するように、輸送行程を表すノードと運用終了ノードとを接続するパスを作成し、同じ資源識別情報を属性とする運用開始ノードと運用終了ノードとを接続するパスを作成し、作成したネットワークモデルに追加し、
該運行スケジュール情報に基づいて、資源の運用終了場所を元の計画から変更しないという条件を達成するために複数の資源を割り当てる候補となる輸送行程を抽出し、
複数の資源を割り当て可能な輸送行程を表すノードを複製して併合ノードを作成し、併合ノードの属性とネットワークモデルを構成する他のノードの属性とに基づいて、併合ノードと複製元のノードが接続しているノードとを接続するパスをネットワークモデルに追加し、
ネットワークモデルを構成する併合ノード以外の各ノードに、一つの資源が割り当てられるような複数のパスから構成されるパスの組合せをネットワークモデルから抽出し、
抽出された組合せについて、該組合せを構成する複数のパスの各々に資源を割り当てることで、運用終了場所を元の計画から変更しないという条件を満たす資源の運用計画を作成して該運用計画を該出力部に出力することを特徴とする資源運用計画作成方法として構成される。
【００１２】
更に、本発明に係る資源運用計画作成のためのプログラムは、上記資源運用計画作成を、コンピュータ上で実行可能なプログラムとして構成される。
【発明の効果】
【００１３】
本発明によれば、資源の運用終了場所または運用終了場所に留置する資源の数を元の計画から変えない運用計画を作成することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施例による資源運用計画作成装置の構成図である。
【図２】資源運用計画作成装置の基本的な処理順を示すフローチャートである。
【図３Ａ】列車の運行スケジュールの例を示す図である。
【図３Ｂ】列車の運行スケジュールにおける各編成への列車の割り当ての例を示す図である。
【図４】併合可能場所情報レコードの構成とそのレコードに属するデータ例を示す図である。
【図５】併合候補情報レコードの構成とそのレコードに属するデータ例を示す図である。
【図６】運用計画を表すネットワークモデルの例を示す図である。
【図７】併合列車を追加した運用計画を表すネットワークモデルの例を示す図である。
【図８】運用計画の解の一例をネットワークモデルで表す図である。
【図９】資源運用計画作成装置の出力画面の例を示す図である。
【図１０】ネットワークモデルの作成手順を示すフローチャートである。
【図１１】併合候補の判定手順を示すフローチャートである。
【図１２Ａ】運休の例を示す図である。
【図１２Ｂ】運休の例を示す図である。
【図１３】運用計画の作成手順を示すフローチャートである。
【図１４】併合候補の判定手順を示すフローチャートである。
【図１５Ａ】列車の運行スケジュールの例を示す図である。
【図１５Ｂ】列車の運行スケジュールにおける各編成への列車の割り当ての例を示す図である。
【図１６】併合候補の判定手順を示すフローチャートである。
【図１７】運用計画の作成手順を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、鉄道における車両運用を例にあげて本発明の実施例を説明する。
【実施例１】
【００１６】
図１は、資源運用計画作成装置の構成例を示すブロック図である。
資源運用計画作成装置１０００は、メモリ１００１、記憶部１１００、表示部１２００、入力部１２０１、処理装置（ＣＰＵ）１２０２、通信部１２０３、およびこれらを接続するデータバス１２０４を有するコンピュータにおいて実現される。この資源運用計画作成装置１０００は通信網を介して外部の端末装置等と接続される。
【００１７】
表示部１２００は液晶表示器などの情報の可視的な出力部であり、資源運用計画作成装置１０００によって処理される実行状況や実行結果などを表示して利用者に知らせる。入力部１２０１はキーボードやマウスなどのコンピュータに指示を入力するためのデバイスであり、利用者からの入力を受付ける。処理装置１２０２は、メモリ１００１に格納される各種プログラムを実行する。通信部１２０３は、ＬＡＮ（Local Area Network）などを介して、他の装置と各種データやコマンドを交換する。記憶部１１００は、資源運用計画作成装置１０００が処理を実行するための各種データを保存する。メモリ１００１は、資源運用計画作成装置１０００が処理を実行する各種のプログラム１００２および一時的なデータを保持する。
【００１８】
記憶部１１００には、元の行路情報１、運行情報２、資源情報３、行路情報４、併合可能場所情報５、および併合候補情報６が格納される。
メモリ１００１には、プログラム１００２が格納され、処理装置１２０２でプログラム１００２が実行されることで、運行スケジュール読込部 １００３、ネットワーク作成部 １００４、併合候補判定部１００５、併合候補反映部１００６、計画作成部１００７の各機能部が実現される。
運行スケジュール読込部１００３は、記憶部１１００に格納された運行情報２を読込む。
ネットワーク作成部１００４は、運行スケジュール読込部１００３で読込んだ運行情報を基に資源運用計画を表すネットワークモデルを作成する。このネットワークモデルに関しての詳細は図６において説明する。
【００１９】
併合候補判定部１００５は、運行スケジュール読込部１００３で読込んだ運行情報を基に、各資源の運用終了駅を算出し、それを基に複数の資源を割り当てる候補となる行路を判定する。
併合候補反映部１００６は、併合候補判定部１００５で複数の資源を割り当てる候補であると判定した行路を基に、ネットワーク作成部１００４で作成したネットワークモデルを変更する。この変更後のネットワークモデルの詳細は図７において説明する。
計画作成部１００７は、ネットワーク作成部１００４で作成し、併合候補反映部１００６で変更を加えたネットワークモデルを基に制約条件を作成し、作成した制約条件を満たすように資源運用計画を作成し、作成した資源運用計画を、表示部１２００を介して利用者に提示する。
【００２０】
図２は、資源運用計画作成装置１０００の基本的な処理手順を示すフローチャートである。
まず、動作手順の概要について説明する。
運行スケジュール読込部１００３は、記憶部１１００に格納された運行情報２を読込む（Ｓ２０１）。そして、ネットワーク作成部１００４は、運行スケジュール読込部１００３が読込んだ運行スケジュールを基に、車両などの資源の運用計画を表すネットワークモデルを作成する（Ｓ２０２）。なお、作成するネットワークモデルについては図６を参照して、またネットワークモデルの作成方法については、図１０を参照して、それぞれ詳述する。
【００２１】
併合候補判定部１００５は、Ｓ２０１で読込まれた運行スケジュールと記憶部１１００に格納された併合可能場所情報５を基に、複数の資源を割り当てる候補となる行路（併合候補という）を判定する（Ｓ２０３）。例えば鉄道では、併合列車の候補となる列車を判定する。ここで、併合列車とは複数の編成を結合して一つの列車として走行する列車である。また、編成とは、列車へ割り当てる複数の車両のまとまりを意味する。併合候補の判定方法については、図１１を参照して詳述する。
併合候補判定部１００５は、Ｓ２０３で併合候補として判定された列車があるかどうかを判定し、候補が１つ以上あれば、併合候補をＳ２０２で作成したネットワークモデルに反映する処理Ｓ２０５を実行し、併合候補がない場合は資源運用計画を作成する処理Ｓ２０６を実行する（Ｓ２０４）。
【００２２】
併合候補反映部１００６は、Ｓ２０２で作成したネットワークモデルに、Ｓ２０３で判定した併合候補の列車を表すノードおよびリンクを追加する（Ｓ２０５）。併合候補を追加したネットワークモデルについては、図７を参照して詳述する。
計画作成部１００７は、Ｓ２０１〜Ｓ２０５の一連の手順で作成したネットワークモデルを基に輸送計画問題として定式化した数理モデルを生成し、数理モデルによって表された条件を満たす資源運用計画を作成する（Ｓ２０６）。ここで、作成する数理モデルおよび計画作成手順に関しては、図１３を参照して詳述する。計画作成部１００７は、Ｓ２０６で作成した資源運用計画結果を表示部１２００に表示して（Ｓ２０７）利用者に知らせる。このとき、Ｓ２０６で複数の計画結果を作成した場合はその全てを表示する。
【００２３】
次に、本実施例において取扱われる各種の情報１〜６について説明し、その後、資源運用計画作成装置１０００の各処理部１００３〜１００７の詳細を説明する。
元の行路情報１は、運行を開始する前に計画されている行路に関する情報であり、項目は以降の行路情報４の項目に、各列車の始発駅と終着駅を追加した項目で構成される。
運行情報２は、輸送サービスの最小単位ごとにその行程を定義したものである。例えば、鉄道における輸送サービスの最小単位は列車であり、始発駅から終着駅までに電車が停車または通過する駅、各駅の到着時刻・出発時刻または通過時刻により定義される。
【００２４】
資源情報３は、輸送サービスに用いる資源を定義する。例えば、鉄道における資源情報には車両や乗務員である。例えば、車両を定義する情報は、車両を一意に識別するための車両名称または識別番号、運行当日に実施予定の保守作業（検査や清掃など）の有無、保守作業の実施可能時刻、保守作業の実施場所、車両に割り当てられている輸送サービス（鉄道では列車に相当）を一意に識別するための行路識別番号によって表される。
【００２５】
行路情報４は、１つの資源が、輸送サービスの最小単位をどのような順序で実行していくかを定義する。例えば鉄道では、編成の折り返し運転や車両基地への格納・引き出しを考慮して、一つの編成に割り当てる列車情報を列挙したものが行路情報である（図３Ａ）。ここで、列車情報とは列車を一意に識別する列車名称または列車ＩＤである。例えば図３Ｂでは、３つの編成各々にどのように列車が割り当てられているかが表されている。即ち列車１、列車４および列車８に一つの編成が割り当てられる。同様にして、列車２、列車５、列車７および列車９に別の一つの編成が割り当てられ、列車３、列車６および列車１０に別の一つの編成が各々割り当てられている。
【００２６】
併合可能場所情報５は、複数の資源を併合する作業、または分離する作業を実施可能な場所を定義する。例えば鉄道では、複数の編成を併合または分離することが可能な駅または車両基地につながっている駅を定義したものが併合可能場所情報である。鉄道を例に、併合可能場所情報５の一例を図４に示す。対象線区５１は、定義対象となる線区を一意に識別するＩＤまたは線区名称を格納する。併合可能場所５２は、対象線区５１で識別された線区に属する駅であり、かつ併合作業を実施可能な駅を一意に識別するＩＤまたは駅名称を格納する。分離可能場所５３は、対象線区５１で識別された線区に属する駅であり、かつ分離作業を実施可能な駅を一意に識別するＩＤまたは駅名称を格納する。例えば、レコード５４は、線区Ａに属する駅のうち、Ａ駅とＣ駅において併合作業が実行可能であり、Ｃ駅において分離作業が実行可能であることを表す。
【００２７】
併合候補情報６は、併合候補判定部１００５が併合候補として判定した行路を格納する、あるいは予め併合候補が決まっている場合はその併合候補を格納する。例えば鉄道では併合候補となる列車を定義する情報である。図５に、併合候補情報の一例を示す。併合区間６１は、併合列車として走行する駅間を格納する。併合候補６２は、併合候補となる列車を格納する。併合可能数６３は、併合列車として併合可能な編成の最大数を格納する。例えば、レコード６４は、併合区間Ａ駅からＣ駅の間で、元の編成に最大２編成まで追加で併合し、列車５として走行させることが可能であることを示す。
【００２８】
次に、図３Ａ、図３Ｂを用いて、本実施例で対象とする業務について説明し、図６を用いて資源運用計画のモデルについて説明する。その後に、図７〜図１３を用いて、資源運用計画作成装置１０００の各処理部の機能乃至作用の詳細について説明する。本実施例では、鉄道の運行が乱れた際に行われる車両運用整理という業務を想定する。車両運用整理とは、事故や車両故障などにより列車の運行スケジュールが急遽変更となった際に、変更された運行スケジュールに合わせて列車への車両の割り当てを変更する業務である。車両の割り当ての変更手段は、折返し駅で割り当てる列車を変更する手段と、車両基地に留置してある予備列車を臨時に引き出す手段と、臨時に車両基地へ車両を格納する手段などがある。また、車両には、走行キロと走行日数に応じて定期的な検査の実施が法で義務付けられている。車両運用整理では、検査周期を超えないように決められた検査を実施することも考慮に入れて、上記のような手段を組合せて車両の割り当てを変更する。
【００２９】
＜業務の説明＞
図３は、鉄道の輸送サービスで用いる図表の説明及び本実施例で例として用いられるデータを示す。
図３Ａは、列車の運行スケジュールの例を示す。列車の運行スケジュールは運行情報２を基に作成される。図３Ａの縦軸３１は駅を表し、横軸３２は時刻を表す。列車の始発駅から終着駅までを時刻に従って線を引くことで一つの列車を表す（列車スジという）。例えば、太線３３は、６時に駅Ｃを始発し、６時３０分ごろに駅Ａに終着する一つの列車を表す。
【００３０】
線分３４のように２本の列車スジをつなぐ線分は、一つの編成に割り当てる列車群を表す。例えば、図３Ｂの例では、列車１と列車４と列車８が一連の列車群としてつながれており、これらの順に一つの編成が走行することを意味する。
記号３５のように「○」で表された記号は、編成を車両基地から引き出すタイミングを表す。例えば、記号３５は、列車１の出発に合わせて駅Ｃに隣接する車両基地から編成を引き出すことを表す。記号３６のように「△」で表された記号は、編成を車両基地へ格納するタイミングを表す。例えば、記号３６は、列車６が到着した後に、列車６に割り当てていた編成を駅Ａに隣接する車両基地へ格納することを表す。
【００３１】
図３Ｂは、各編成への列車の割り当てを示す。この列車の割り当ては資源情報３と行路情報４を基に作成される。図３Ｂは、横軸４１、編成名称４２、割り当て情報４３で表される。
軸４１は時刻を表す。編成名称４２は、編成を一意に識別するための名称を表す。割り当て情報４３は、編成４２に示された編成に対する列車の割り当てを表す。割り当てる各列車を一つの横棒で表し（例えば横棒４４）、横棒の近くに列車名称（例えば列車名称４５）を表示する。また、清掃や検査などの保守作業が予定されている編成の場合は、予定されている作業を表す記号を表示する。例えば、記号４６は、編成Ｃが列車６として走行した後、検査Ａという保守作業を実施予定であることを表している。
【００３２】
レコード４７を例にして一連の行路情報を説明する。レコード４７は、編成Ｃに割り当てられた行路を表しており、編成Ｃは、列車３として走行後に、列車６として走行し、検査Ａという作業を実施された後、列車１０として走行することを表している。なお、図３Ａを見ると、列車６は、走行後に、駅Ａに隣接する車両基地に格納され、列車１０は、車両基地Ａに隣接する車両基地から引き出されることになっている。よって、編成Ｃは、列車３と列車６を走行後に車両基地に一旦格納された後、再び車両基地から引き出されて列車１０として走行すると読み取ることができる。  
【００３３】
＜ネットワークモデル＞
図６は、資源運用計画のネットワークモデルを示す。なお、図６に示した例は、見易くするためにいくつかのリンクを省略している。図６は、行路として作成し得る候補を表すネットワークモデルであり、編成ノード、列車ノード、終端ノード、接続リンク、終端リンクで構成される。
【００３４】
（１）編成ノード
編成ノードは、行路が割り当てられている編成を表すノードである。一つの編成につき一つの編成ノードを設定する。編成ノードは、編成を利用可能な時間帯の開始時刻、編成を利用可能な時間帯の終了時刻、運用開始時に留置されている位置（留置されている車両基地の隣接駅または留置駅）、元の計画の行路の開始駅、および元の計画の行路の終着駅を属性として持つ。
【００３５】
（２）列車ノード
列車ノードは、運行スケジュールに含まれる列車を表す。一つの列車につき一つの列車ノードを設定する。列車ノードは列車の始発駅、終着駅、始発時刻、および終了時刻を属性として持つ。
【００３６】
（３）終端ノード
終端ノードは行路の終端を表す。一つの編成につき一つの終端ノードを設定する。終端ノードは、編成を一意に識別する編成名称または編成ＩＤと、元の計画で計画されていた行路の終着駅を属性として持つ。例えば、終端ノード６１は、編成Ａの行路の終端を表すものとする。図３Ｂに示した例では、編成Ａの元の計画の行路の終端は列車８であり、図３Ａに示した例では、列車８は駅Ａで終着する。よって、終端ノード６１の終着駅の属性の値は「駅Ａ」である。
【００３７】
（４）接続リンク
接続リンクは、列車ノード間、編成ノードと列車ノードの間、列車ノードと終端ノードの間を結ぶ有向リンクであり、それぞれ以下のように作成する。
【００３８】
（列車ノード間の接続リンクの張り方）
列車ノード間の接続リンクは、列車ノードが表す列車の始発駅と始発時刻と終着駅と終着時刻を基に、時刻と駅の接続が成り立つように作成する。例えば、列車ノード６３は列車１を表しており、始発駅は駅Ｃ、終着駅は駅Ａ、始発時刻は６時、終着時刻は６時半となる。また、ノード６４は列車４を表しており、始発駅は駅Ａ、終着駅は駅Ｃ、始発時刻は６時４０分、終着時刻は７時５分となる。これら２つの列車ノードを比較すると、ノード６３の終着駅はノード６４の始発駅と等しいため場所の接続が成り立つ。かつ、ノード６３の終着時刻はノード６４の始発時刻よりも早いため、時刻の接続が成り立つ。よって、ノード６３からノード６４への接続リンクを作成することができる。同様に、ノード６３から、列車５を表すノード、列車３を表すノード、列車１０を表すノードそれぞれに向かって接続リンクを作成することができる。
【００３９】
元の資源運用計画で同一編成に連続して割り当てられている列車間の接続リンクには、それ以外の接続リンクよりも解として選ばれやすい重みを設定する。例えば、後述するが、本実施例では、図６に示したネットワーク上のリンクの重みが小さくなるような巡回路を探索することで行路を作成する。よって、元の資源運用計画で同一編成に連続して割り当てられている列車間の接続リンクには小さい値の重みを設定する。これにより元の計画からの変更ができるだけ少ない計画を得ることができる。尚、以降、接続リンクとして選ばれやすい重みと言う場合は、同様の意味である。
【００４０】
（列車ノードと編成ノードの間の接続リンクの張り方）
列車ノードと編成ノードの間の接続リンクは、列車ノードが表す列車の始発駅と始発時刻と終着駅と終着時刻と、編成ノードが表す編成の利用可能な時間帯の開始時刻と終了時刻と運用開始時の編成の位置を基に、時刻と場所の接続が成り立つように作成する。例えば、編成ノード６２の表す編成（編成Ａ）の利用可能時間帯は６時であり、開始位置は駅Ｃであるため、編成ノード６２から、６時以降に駅Ｃを始発する列車を表す列車ノードへ向かって接続リンクを作成する。つまり、列車１、列車２、列車６、列車８をそれぞれ表す列車ノードへ向かって接続リンクを作成する。
元の資源運用計画と同じ割り当てを示す接続リンクに対しては、それ以外のリンクよりも解として選ばれやすい重みを設定する。
【００４１】
（列車ノードと終端ノードの間の接続リンクの張り方）
列車ノードと終端ノードの間の接続リンクは、行路の最終列車として設定可能な列車ノードから終端ノードへ向かって作成する。行路の最終列車として設定可能な列車は、基本的には車両基地に隣接する駅または駅構内に翌日まで留置できる駅を終着駅とする列車である。そうでない場合は、車両基地へ車両を格納するために回送を走らせることになるため望ましくない。
元の計画で行路の終端となっている列車を表す列車ノードと終端ノードを接続する接続リンクに対しては、それ以外のリンクよりも解として選ばれやすい重みを設定する。
【００４２】
（５）終端リンク
終端リンクは、編成が元の資源運用計画で予定されていた地点で行路を終了するように制約をかけるためのリンクである。終端リンクは、一つの終端ノードから全ての編成ノードに向かってリンクを作成し、行路終了地点の制約を基に重みを設定する。つまり、終端ノードが保持している元の資源運用計画上の終着駅の値と、編成ノードが保持している当該資源運用計画上の終端駅の値を比較し、同じであれば、該当する終端ノードと該当する編成ノードとを結ぶ終端リンクには、該当する終端ノードから他の編成ノードへのびる終端リンクより選択されやすくなるよう、重み値を設定する。
【００４３】
例えば、より小さな重みのリンクが選ばれやすい場合を想定する。このとき、終端ノード６１は編成Ａの行路の終端を表しており、元の計画の終着駅は駅Ａである。編成Ａを表すノードは編成ノード６２であり、元の計画の終着駅は駅Ａである。終端ノード６１の終着駅と編成ノード６２の終着駅が同じなので、終端ノード６１と編成ノード６２を結ぶ終端リンクには、終端ノード６１から他の編成ノードへ延びるリンクよりも小さい値を設定する。また、終端ノード６５は、編成Ｂの行路の終端を表しており、図３Ｂより、編成Ｂの行路の終端は列車９なので、終着駅は駅Ｃとなる。編成Ｃの行路の終端も駅Ｃなので、終端ノード６５は、編成Ｂを表す編成ノード６７との終端リンクと、編成Ｃを表す編成ノード６８との終端リンクの両方のリンクに対して同じ値の重みを設定する。この終端リンクの重みの設定により、行路の最後に割り当てられた列車が元の資源運行計画と異なる場合でも、終着駅は同じとなる列車が割り当てられる可能性を高めることができる。
【００４４】
本実施形態では、以上のようなネットワークモデルを基本とし、併合候補がある場合は併合候補に合わせてネットワークモデルを変更する。そして、ネットワークモデルを基に資源運用計画を作成する。次に、図２を用いて、資源運用計画作成装置１０００の処理手順の詳細を説明する。
Ｓ２０１において、運行スケジュール読込部１００３は、記憶部１１００に格納された運行情報２を読込む。
Ｓ２０２において、ネットワーク作成部１００４は、Ｓ２０１で読込んだ運行情報を基に、図６に示したネットワークモデルを作成する。ネットワークモデルの作成手順の詳細は、以降で図１０を用いて説明する。
【００４５】
Ｓ２０３において、併合候補判定部１００５は、記憶部１１００に格納された併合可能場所情報５を読込み、併合候補となる列車を判定し、記憶部１１００の併合候補情報６に格納する。併合候補となる列車の判定は、以降で図１１を用いて説明する。
Ｓ２０４において、併合候補判定部１００５は、併合候補がある場合は併合候補の反映（Ｓ２０５）に進み、併合候補がない場合は資源運用計画の作成（Ｓ２０６）に進む。
Ｓ２０５において、併合候補反映部１００６は、Ｓ２０２において作成したネットワークモデルに、記憶部１１００の併合候補情報６に格納された併合候補を表すノードとリンクを追加する。
【００４６】
ここで、図７を用いて、ネットワークモデルへの併合候補の反映方法を示す。以降、Ｓ２０１にて読込んだ運行スケジュールにおいて列車３と列車４が運休となっていた場合で、かつ併合候補判定部１００５が図４に示すような判定結果を作成した場合を例にとり、説明する。
列車３と列車４は運休となっているため、Ｓ２０２において、図６に示したネットワークから列車３と列車４を表すノードが削除され、これらと接続するリンクも全て削除された状態のネットワークが作成される。Ｓ２０５では、このネットワークから、併合候補である列車５（図４参照）を表すノード９１を検出し、このノードを併合可能な数だけ複製し、ネットワークモデルに追加する。このとき、ノードを複製するとは、新しくノードを作成し、複製元となるノードの属性と同じ属性値を新しく作成したノードに付与することである。ここで、図４の例では、列車５は最大２編成まで併合可能であるので、図７に示すように、列車５を表すノードを２つ複製し、ネットワークモデルに追加する（ノード９２とノード９３）。
ノードを追加した後、複製したノードとその他のノードを接続するリンクを作成する。リンクの作成方法は、以下の２通りがある。
【００４７】
（１）併合候補の列車が一つのみの場合
リンクは、複製元のノードが接続しているノードと同じノードに接続するように作成する。例えば、図７の例では、ノード９１は、列車ノード「列車１」、列車ノード「列車２」、編成ノード「編成Ｃ」をそれぞれ接続元とするリンク、および列車ノード「列車８」、列車ノード「列車７」、列車ノード「列車６」、終端ノード「終了Ｃ」をそれぞれ接続先とするリンクと接続されている。よって、ノード９１の複製であるノード９２とノード９３も同じように、列車ノード「列車１」、列車ノード「列車２」、編成ノード「編成Ｃ」をそれぞれ接続元とするリンク、および列車ノード「列車８」、列車ノード「列車７」、列車ノード「列車６」、終端ノード「終了Ｃ」をそれぞれ接続先とするリンクで接続する。
【００４８】
（２）併合候補の列車が複数ある場合
併合候補の開始列車を接続先とするリンクは、複製元のノードと同じように作成し、併合候補の終了列車を接続元とするリンクは複製元のノードと同じように作成する。併合候補の開始列車と終了列車の間にある列車に関しては、併合候補同士を結ぶリンクしか存在しないようにリンクを作成する。例えば、併合候補が「列車５→列車８→列車１０」となっていた場合は、列車５の複製ノードを接続先とするリンクは、列車５を接続先とするリンクと同じように作成し、列車１０の複製ノードを接続元とするリンクは、列車１０を接続元とするリンクと同じように作成する。そして、列車５の複製ノードを接続元とするリンクは列車８の複製ノードに向かってのみ作成し、列車８の複製ノードを接続元とするリンクは列車１０の複製ノードに向かってのみ作成する。
【００４９】
このネットワークモデルを用いて表した資源運用計画の解の一例を図８に示す。図８では、編成Ａが列車１として走行した後、併合列車５の一部として走行し、列車８として走行した後、運用を終了することを表す。同じく編成Ｃが、併合列車５の一部として走行した後、列車６として走行し、列車１０として走行した後、運用を終了することを表す。
Ｓ２０６において、計画作成部１００７は、Ｓ２０１〜Ｓ０２０５を実行して作成されたネットワークモデルを基に資源運用計画を作成する。なお、詳細な手順については、図１３を参照して説明する。
【００５０】
Ｓ２０７において、計画作成部１００７は、Ｓ２０６で作成した計画を利用者に提示する。図９に出力の画面例を示す。出力画面１１１には、運行スケジュール図１１２、割り当て図１１３が表示される。尚、この画面は、計画作成部１００７によって作成され表示部１２００に表示される。
運行スケジュール図１１２と割り当て図１１３の見方については、それぞれ図３Ａと図３Ｂの説明で示した通りである。図８に示したネットワークモデルの例では、列車５は、元の列車５に対して編成Ａと編成Ｃを併合して走行することになっている。このため、このネットワークモデルによって表される運用計画を示した運行スケジュール図１１２では、元々の列車５にあたる列車スジ１１４と並行して、併合することを表す列車スジ１１５と列車スジ１１６を描く。また、割り当て図１１３においては、編成Ａ、編成Ｂ、編成Ｃそれぞれに対する列車の割り当てを表す行に、列車５を表す線分１１７、線分１１８、線分１１９をそれぞれ表記する。更に、列車を表す線分の近くに、該当する編成が何両目に位置するかを表記する。例えば、ラベル１２０は、編成Ａが列車５として走行する時には、６両編成のうち１両目から２両目に位置して走行することを示す。
【００５１】
次に、Ｓ２０２のネットワークモデルの作成とＳ２０３の併合候補の判定およびＳ２０６の資源運用計画の作成の詳細について説明する。
図１０は、Ｓ２０２のネットワークモデルの作成手順を示す。
Ｓ１２１において、ネットワーク作成部１００４は、記憶部１１００に格納された行路情報４を読込む。
Ｓ１２２において、ネットワーク作成部１００４は、記憶部１１００に格納された資源情報３を読込む。
Ｓ１２３において、ネットワーク作成部１００４は、Ｓ１２１で読込んだ行路情報を列車に分離して各列車を表す列車ノードを作成し、各列車が持つ属性を行路情報から抽出してこれを当該列車の列車ノードに割り当てる。列車ノードの詳細および列車ノードに割り当てられる属性については、図６のネットワークモデルに示した通りである。なお更にＳ１２３では、行路情報上で列車の列車名として用いられている識別情報が、当該列車の列車ノードの識別情報として付与される。
【００５２】
Ｓ１２４において、ネットワーク作成部１００４は、Ｓ１２２で読込んだ資源情報を基に、編成ノードと終端ノードを作成し、各ノードに当該ノードの識別情報と属性を付与する。これらのノードの詳細（ノードが持つ属性等）については、図６のネットワークモデルに示した通りである。
Ｓ１２５において、ネットワーク作成部１００４は、Ｓ１２３およびＳ１２４で作成したノードからノードを一つ選択する。
Ｓ１２６において、ネットワーク作成部１００４は、Ｓ１２５で選択したノードが終端ノードかどうかを判定し、終端ノードであればＳ１２７の終端リンクの作成に進み、終端ノードでなければＳ１２９の接続リンクの作成に進む。
【００５３】
Ｓ１２７とＳ１２８において、ネットワーク作成部１００４は、以下のように終端リンクを作成する。
Ｓ１２７において、Ｓ１２５で選択したノードから、そのノードの属性の一つである「元の計画における終着駅」と同じ終着駅を持つ編成ノードへ向かう終端リンクを作成する（終端リンク１）。更に、残りの編成ノードへ向かってＳ１２５で選択したノードから終端リンクを作成する（終端リンク２）。
Ｓ１２８において、Ｓ１２７で作成した終端リンク１と終端リンク２に対して重みを設定する。ここで、終端リンク１に対しては、資源運用計画の作成において終端リンク２よりも選択されやすいように重み値を設定する。
【００５４】
Ｓ１２９において、ネットワーク作成部１００４は、Ｓ１２５で選択したノードから、始発駅と始発時刻と終着駅と終着時刻の比較に基づいて接続が可能なノードへ向かう接続リンクを作成する。詳細は、図６のネットワークモデルに示した通りである。
Ｓ１２１０において、ネットワーク作成部１００４は、Ｓ１２９で作成した接続リンクに対して重みを設定する。ここで、リンクで結ばれた２つのノードが元の計画で同じ編成に連続して割り当てられていた場合は、当該リンクに対しては、当該２つのノードの少なくとも一方に接続されている他のリンクよりも資源運用計画の作成において選択されやすいよう、重み値を設定する。
Ｓ１２１１において、ネットワーク作成部１００４は、Ｓ１２３とＳ１２４で作成した全てのノードに対してＳ１２７〜Ｓ１２８またはＳ１２９〜Ｓ１２１０の処理を行ったかどうかを判定し、行った場合は一連の処理を終了し、行っていない場合はＳ１２５へ進む。
【００５５】
次に、図１１を用いて、Ｓ２０３の併合候補判定の手順について説明する。
Ｓ１３０１において、併合候補判定部１００５は、記憶部１１００から運行情報２、資源情報３、行路情報４を読込み、各駅に対して、その駅を運用終了駅としている編成の数（滞泊数という）Ｘを算出する。ここで、車両の形式によって走行可能な線区や割り当て可能な列車が異なる場合は、車両の形式ごとに分けて算出し、以降の処理も車両の形式ごとに分けて実施するものとする。
Ｓ１３０２において、併合候補判定部１００５は、元の計画における各駅の滞泊数Ｙを算出する。具体的には、記憶部１１００から元の行路情報１を読込み、各駅に対して滞泊数を算出する。
【００５６】
各編成の運用終了駅を判定する際に、割り当てられた行路に運用がつながらない、つまり同じ編成に続けて割り当てられた列車同士において先に割り当てられた列車の終着駅と後に割り当てられた列車の開始駅が異なる場合または先に割り当てられた列車の終着時刻よりも後に割り当ててられた列車が早く出発してしまう場合には、運用が正しくつながる列車までをその編成に対する運用として扱う。よって、運用終了駅は、その編成に割り当てられた列車のうち、運用が正しくつながる列車群の最後の終着駅とする。
【００５７】
Ｓ１３０３において、併合候補判定部１００５は、Ｓ１３０１で算出した滞泊数ＸとＳ１３０２で算出した滞泊数Ｙが異なるか否か判定する。判定の結果、双方の値が異なる場合はＳ１３０４を実行し、等しい場合はそのまま処理を終了する。
Ｓ１３０４において、併合候補判定部１００５は、資源を併合する区間の候補を作成する。例えば鉄道では、併合列車を走行させる駅間の開始駅と終了駅の組合せを作成する。この併合区間の候補の作成は、各編成の運用終了駅を元の計画にあわせるか、各運用終了駅における滞泊数を元の計画とあわせるかによって異なる。以降、図３に示した計画を元の計画とし、図１２に示したように、列車３（列車スジ６１、横棒６３）と列車４（列車スジ６２、横棒６４）を運休とした場合を例に、それぞれの場合について示す。
【００５８】
（１）個々の編成の運用終了駅を元の計画とあわせる場合
各編成に対して、Ｓ１３０１で記憶部から読み込んだ運行情報２における運用終了駅（Ｓ１）と元の計画における運用終了駅（Ｓ２）とを比較し、異なる編成を検出する。
検出した個々の編成について、Ｓ１を併合区間の開始駅とし、Ｓ２を併合区間の終了駅として併合区間の開始駅・終了駅の組合せを作成する。
加えて、運用終了駅が変わらない場合でも、運休を行路に含んでいる場合は、運休の開始駅を併合区間の開始駅とし、運休の終了駅を併合区間の終了駅とすることで併合区間の開始駅・終了駅の組合せを追加する。
【００５９】
図１２Ａ、図１２Ｂを参照して、運休の例について説明する。列車３と列車４を運休としたことで、編成Ａの運用終了は列車８から列車１となっているが、列車８と列車１の終着駅は共にＡ駅であるため運用終了駅は変わらない。一方、編成Ｃは、運用開始の列車が運休となったため車両基地から出られず、運用終了駅は列車１０の終着駅であるＣ駅からＡ駅に変わっている。よって、Ａ駅を併合区間の開始駅、Ｃ駅を併合区間の終了駅とする組合せを併合区間の候補の１つとして作成する。これに加えて、編成Ａは、運用終了駅は変わらないが行路に運休を含んでいるため、運休区間の開始駅であるＡ駅を併合区間の開始駅、運休区間の終了駅であるＣ駅を併合区間の終了区間とする組合せを併合区間の候補の１つとして追加する。
【００６０】
（２）滞泊数を元の計画と合わせる場合
Ｓ１３０１で算出した滞泊数とＳ１３０２で算出した滞泊数が異なる駅を用いて、滞泊数が０となる駅の集合を作成する。集合に属する駅のうち、滞泊数が元の計画よりも多い駅を併合区間の開始駅とし、滞泊数が元の計画よりも少ない駅を併合区間の終了駅として併合区間の開始駅・終了駅の組合せを作成する。加えて、Ｓ１３０３にて、運用終了駅が変わらないと判定された編成のうち、運休を行路に含んでいる編成がある場合は、運休の開始駅を併合区間の開始駅とし、運休の終了駅を併合区間の終了駅として併合区間の開始駅・終了駅の組合せを追加する。
【００６１】
図１２を参照するに、上記（１）で説明したように、編成Ｃの運用終了駅がＣ駅からＡ駅に変わっており、Ａ駅の滞泊数が元の計画よりも１つ増え、Ｃ駅の滞泊駅が元の計画よりも１つ減っている。よって、Ａ駅を併合区間の開始駅、Ｃ駅を併合区間の終了駅とする組合せを併合区間の候補の１つとして作成する。これに加えて、編成Ａは、運用終了駅は変わらないが行路に運休を含んでいるため、運休区間の開始駅であるＡ駅を併合区間の開始駅、運休区間の終了駅であるＣ駅を併合区間の終了区間とする組合せを併合区間の候補の１つとして追加する。
【００６２】
Ｓ１３０５において、併合候補判定部１００５は、Ｓ１３０４にて生成した併合区間の開始駅・終了駅の組合せから、まだ処理をしていない組合せを１つ選択する。
Ｓ１３０６において、併合候補判定部１００５は、記憶部１１００に格納された併合可能場所情報５を読込み、Ｓ１３０５にて選択した開始駅であり、かつ併合作業が可能な駅でもある駅を出発点として、Ｓ１３０５にて選択した終了駅であり、かつ分離作業可能な駅でもある駅を到着点して走行する行路を作成する。ここで、併合作業が可能な駅かどうかは、併合可能場所情報５を用いて、現在処理中の線区を対象線区５１の検索キーとして併合可能場所５２を取得し、取得結果に処理中の駅が含まれているかどうかによって判定する。同様に、分離可能な駅であるかどうかは、現在処理中の線区を対象線区５１の検索キーとして分離可能場所５３を取得し、取得結果に処理中の駅が含まれているかどうかによって判定する。
なお、同じ列車を含む行路が複数あり、かつ一方が他方を包含するような場合は、併合列車を挿入する際に考慮したい条件に応じて、例えば以下のように、行路を取捨選択してもよい。
【００６３】
（１）併合列車をなるべく少なく抑える場合
行路に含まれる列車数が最も少ない行路を選択して、その行路のみを作成する。
（２）列車を一旦併合したらなるべく運用終了近くまで併合したままで運用する場合
行路に含まれる列車数が最も多い行路を選択して、その行路のみを作成する。
【００６４】
また、車両の形式によって割り当て可能な列車が異なる場合は、割り当て可能な形式が同じ列車のみを同一の行路に含むように行路を作成する。
作成した行路を記憶部１１００の併合候補情報６（図５）に格納する。具体的には、Ｓ１３０５にて選択した併合区間の開始駅・終了駅の組合せを併合候補情報６の併合区間６１に格納し、作成した行路に含まれる全ての列車の列車ＩＤまたは列車名称を併合候補６２に格納する。また、併合可能数６３には、Ｓ１３０４で作成した組合せの集合の中で同じ組合せが重複して表れた回数を格納する。
【００６５】
上記Ｓ１３０４で示したように、図１２に示した例では、併合区間の開始駅・終了駅の組合せは、開始駅を「Ａ駅」とし、終了駅を「Ｃ駅」とする組合せが２組ある。また、Ａ駅からＣ駅の区間を走行する行路としては図１２Ａの運行情報より、行路Ｉ：列車５、行路ＩＩ：列車５→列車６→列車１０、行路ＩＩＩ：列車５→列車８→列車１０の３通りがある。しかし、行路ＩＩと行路ＩＩＩは行路Ｉを包含しており、行路Ｉの列車数が最も少ない。よって、本実施例では、行路として「列車５」を作成する。以上より、併合候補情報６には、併合区間６１には「Ａ駅→Ｃ駅」、併合候補６２には「列車５」、併合可能数６３には「２」を格納する。
【００６６】
次に、図１３を用いて、Ｓ２０６の資源運用計画の作成の手順について説明する。
Ｓ１４０１において、計画作成部１００７は、Ｓ２０１〜Ｓ２０５の一連の処理によって作成されたネットワークモデルから、重みが一定値よりも大きい終端リンクを一時的に除外する。これは、各編成の行路の終了駅が元の計画と同じとなるように計画を作成する可能性を上げるためである。
【００６７】
Ｓ１４０２において、計画作成部１００７は、Ｓ１４０１の処理結果のネットワークモデルを基に巡回路（つまり、出発ノード以外のいずれのノードも２回以上は通らず、出発ノードへ戻ってくる経路）を探索する。ここで作成する巡回路はネットワークモデルの形状から、編成ノードで始まり終端ノード通って編成ノードへ戻る閉路となる。
【００６８】
Ｓ１４０３において、計画作成部１００７は、記憶部１１００に格納されている併合可能場所情報５と併合候補情報６を基に、以降のＳ１４０４で解を探索する際の制約条件を生成する。
Ｓ１４０４において、作成した複数の巡回路から、全列車ノードを各々一度だけカバーし、全併合列車ノードを各々多くても一度だけカバーする巡回路の組合せ（巡回路集合と呼ぶ）を探索する。ここで、併合列車ノードは、「多くても一度だけ」カバーするという条件であり、必ずしもカバーする必要はない。
すなわち、以下の集合分割問題の解を探索する。
【００６９】
＜定数＞
【数１】
0005869276.tif 000002
【００７０】
＜決定変数＞
【数２】
0005869276.tif 000003
【００７１】
＜目的関数＞
【数３】
0005869276.tif 000004
【００７２】
＜制約条件＞
【数４】
0005869276.tif 000005
【００７３】
目的関数は、重みの総和を最小となるような巡回路集合を求めることを意味し、条件（１）は、解となる巡回路集合において、各ノードは多くても一つの巡回路にのみ含まれることを意味し、条件（２）は、解となる巡回路集合において、併合列車以外のノードが出現する回数は併合列車以外のノードの数に等しいことを意味する。条件（１）と条件（２）を合わせることで、解となる巡回路集合において、併合列車以外のノードは一つの巡回路にのみ一度だけ含まれ、併合列車のノードは巡回路に含まれないか含まれても一度だけ含まれることを表す。
【００７４】
条件（３）は、解となる巡回路集合に含まれる巡回路は編成の数だけ存在することを意味する。なお、Ｓ１４０４で作成する巡回路には、編成ノードを２つ以上含むような巡回路が生成される場合もあるため、そうした巡回路を選択しないように条件（３）を設定する必要がある。
【００７５】
条件（４）は、資源の併合作業と分離作業をそれぞれの作業が可能な場所で行うための条件（分併条件）である。この分併条件は、前述のＳ１３０６において、併合候補の行路を作成する際に、併合可能な場所を開始点とし、分離可能な場所を終了点とする行路を併合候補として作成することで考慮した。しかしこの処理は、併合列車ノードを同じ行路に連続して割り当てることで望ましくない分離や併合を制限するための処理であり、併合相手となる元の列車ノードを割り当てる行路によっては望ましくない分離や併合が発生する可能性がある。例えば、併合候補が「列車５→列車６→列車１０」であった場合、列車５と列車６と列車１０をそれぞれ表すノードを複製して併合列車ノードを作成し、併合列車ノード５→併合列車ノード６→併合列車ノード１０と連続してつながるようにリンクを作成する。しかし、このままでは、列車ノード５→列車ノード６→列車ノード１０の間には制限はない。このため、併合列車ノード５→併合列車ノード６→併合列車ノード１０は同一行路（行路Ｉ）、つまり途中に分離も併合もなく同じ編成を割り当てられるが、元の列車の方は、「列車ノード５→列車ノード７→列車９」という行路となることもあり得る。そうすると、行路Ｉは、列車５を併合列車として走行した後、列車５の終着駅で、併合相手は列車６として走行するため分離され、別の編成と併合した後、列車６を併合列車として走行することとなる。このような事態を避けるため、条件（４）によって、併合相手となる元の列車ノードに関しても制限を加える。
【００７６】
併合列車ノードは連続して同じ行路に割り当てなければならないのに対して、併合相手となる列車ノードは、併合列車ノードを併合される場合のみ、併合候補に含まれる列車の列車ノードを全て同じ行路に割り当てる。例えば、上述の例では、「併合列車ノード５→併合列車ノード６→併合列車ノード１０」が解の巡回路に含まれる場合のみ、「列車ノード５→列車ノード６→列車ノード１０」も解の巡回路に含む必要がある。以降、この条件を、条件（４）はどのように表しているかを説明する。
【００７７】
条件（４）の減算の左項は、k 番目の併合候補に含まれる列車を表すノードのうち併合列車以外を表すノードであり、かつ巡回路 jに含まれるノードの数を表す。条件（４）の減算の右項は、k 番目の併合候補に含まれる列車を表すノードのうち併合列車を表すノードであり、かつ巡回路１に含まれるノードの数を表す。なお、併合候補に含まれる列車を表すノードとは、併合候補情報６の併合候補６２に基づいて併合候補反映部１００６が作成した併合列車ノードおよび元となる列車ノードである。ここで、併合列車ノードに接続するリンクは、併合候補となる列車のつながりを崩さないように作成されること（Ｓ２０５の説明を参照）に注意すると、減算の右項は０または N pk のいずれかの値をとる。また、併合候補に含まれるノードのうち、併合列車ノードとその元となる列車ノードの間にはリンクは作成されないため、巡回路に含まれるノード数は実際には最大でもN pk までである。このため、左項の値は０以上 N pk 以下である。よって、巡回路１が併合列車を含まない場合、つまり減算の右項が０の場合は、条件（４）は減算の左項の値にかかわらず成立し、巡回路１が併合列車を含む場合、つまり減算の右項が N pk の場合は、条件（４）は、減算の左項の値が N pk  の場合、つまり巡回路 j が併合候補の列車ノードを全て含む場合のみ成立する。なお、 N pk  は、k 番目の併合候補に含まれる「列車」の数であり、例えば、図５のレコード６４の併合候補は「列車５」のみなので、N pk は「１」であり、併合候補が「列車５→列車６→列車１０」であれば「３」である。
【００７８】
なお、集合分割問題による定式化を行う場合、一つの編成は一つの行路のみに割り当てるという条件を追加する場合もあるが、本発明のネットワークモデルでは編成もノードとして表しているため、この条件は上記の条件に含まれている。
ここで得られる巡回路集合に含まれる各巡回路が、その巡回路に含まれる編成ノードが表す編成に割り当てられる行路となる。
【００７９】
Ｓ１４０５において、計画作成部１００７は、Ｓ１４０４の探索で解が得られたかどうかを判定し、得られた場合はＳ１４０６に進み、得られなかった場合はＳ１４０７の判定に進む。
Ｓ１４０６において、計画作成部１００７は、Ｓ１４０４で得られた解を資源運用計画の候補として記憶部１１００に格納する。このとき、計画作成部１００７は、Ｓ１４０４で得られた解に含まれる各パスを、そのパスに含まれる編成ノードに対応する編成に割当ることで資源運用計画の候補を作成する。また、併合列車ノードを解に含む場合は、計画作成部１００７は、併合列車ノードの併合相手となる列車ノードおよび併合列車ノードを抽出し、抽出した列車と併合列車が併合する駅に到着する時刻を比較し、各列車（抽出した列車と併合列車）が併合される位置（何両目〜何両目までか）を算出する。このとき、併合後の走行向きが併合前の走行向きと変わらない場合は到着順序が早い順に前方車両となるように位置を算出し、走行向きが変わる場合は到着順序が遅い順に前方車両となるように位置を算出する。
【００８０】
Ｓ１４０７において、計画作成部１００７は、Ｓ１４０４で得られた解に、重みが一定値よりも大きい終端リンクが含まれるかどうかを判定し、含まれる場合はＳ１４０８に進み、含まれない場合は処理を終了する。ここでの重みの一定値はＳ１４０１で用いた一定値と同じ値とする。これは、行路の終了駅が元の計画の終了駅と異なるような編成が解に含まれるかどうかを判定することを目的とした処理である。
Ｓ１４０８において、計画作成部１００７は、Ｓ１４０１で除外したリンクをネットワークモデルに戻し、Ｓ１４０２に進む。
【実施例２】
【００８１】
実施例１では、運用終了場所または滞泊数を元の計画と合わせるために併合列車を含む資源運用計画を作成した。実施例２では、回送列車を設定することで、運用終了場所または滞泊数を元の計画から変えないような資源運用計画を作成する例を示す。なお、以下の説明では、実施例１との相違する部分について述べる。
【００８２】
図１６は、実施例１のＳ２０３「併合候補の判定」の詳細フローである。
Ｓ１３０１〜Ｓ１３０５は実施例１で示した通りである。
Ｓ１５０６において、併合候補判定部１００５は、Ｓ１３０５で選択した併合区間の候補の開始場所を始発駅とし、終了場所を終着駅とし、途中駅は全て通過する回送列車を新たに生成し、記憶部１１００の併合候補情報６に格納する。Ｓ１３０７は実施例１で示した通りである。
【００８３】
本実施例では、実施例１のＳ２０３を上記のようなフローに置き換え、Ｓ２０５において併合候補をネットワークモデルに反映する際に、併合候補が回送列車であった場合は回送列車ノードとしてネットワークモデルに追加し、列車の始発駅と終着駅のつながりを考慮して他のノードとのリンクを生成する。
【００８４】
また、Ｓ１４０４の探索において考慮する条件は、実施例１の条件（２）に代えて、以下を考慮する。
【００８５】
【数５】
0005869276.tif 000006
【実施例３】
【００８６】
実施例１では、運用終了場所を基に併合候補を作成した。実施例３では、ユーザから併合区間の開始場所と終了場所の指定を受付け、受付けた併合区間を実現する併合候補を作成する例を示す。なお、以下、実施例１と相違する部分について述べる。
【００８７】
図１４は、実施例１のＳ２０３「併合候補の判定」の詳細フローである。
Ｓ１７０１において、併合候補判定部１００５は、併合区間の開始場所と終了場所の入力を、入力部１２０１を介してユーザから受付ける。このとき、Ｓ２０１で読み込んだ運行スケジュールとＳ１２１およびＳ１２２で読み込んだ行路情報と資源情報を基に、図１５に示すような運行スケジュール図と列車の割り当て図を表示する。図１５の構成は実施例１の図９に示した通りである。実施例１の図９に加えて、図１５では、各駅における滞泊数（図１５Ａの６５、６６）および各編成の運用終了場所（図１５Ｂの６７、６８，６９）を表示する。
【００８８】
Ｓ１７０２において、併合候補判定部１００５は、Ｓ１７０１で受付けた併合区間の開始場所と終了場所を基に併合候補となる行路を作成する。この処理は、実施例１のＳ１３０６の処理と同様である。
本実施例によれば、実施例１のＳ２０３を上記のようなフローに置き換え、それ以外は実施例１と同じように実施することで資源運用計画を作成することができる。
【実施例４】
【００８９】
実施例１では、複数の資源を併合する際に併合順序を考慮せずに資源運用計画を作成した。実施例４では、列車の到着順序から割り出される併合順序を考慮することでより実用に近い資源運用計画を作成する例を示す。
【００９０】
図１７は、実施例１のＳ２０６「資源運用計画の作成」の詳細フローである。
Ｓ１４０１〜Ｓ１４０４は実施例１で示した通りである。
Ｓ１６０５において計画作成部１００７は、Ｓ１４０４で作成した解に含まれる併合列車に対して以下の処理を行う。
【００９１】
（１）新しく追加した併合列車である場合
実施例１のＳ２０５「併合候補の反映」で追加した併合列車に対して、併合する相手同士の編成それぞれが到着する時刻を比較し、到着が早い順に編成位置の早い番号または遅い番号を割り振る。早い番号から割り当てるか、遅い番号から割り当てるかは事前の設定で変更可能とする。ここで、編成位置とは、列車を構成する全両数のうち何両目から何両目として走行するかを表す数値である。
【００９２】
（２）元の計画に含まれる併合列車である場合
元の計画から設定されている併合列車に対しては、併合する相手同士の編成でそれぞれが到着する時刻を比較し、到着が早い順に編成位置の早い番号または遅い番号を仮に割り振る。仮に割り振った編成位置と元の計画で設定されている編成位置を比較し、異なっている場合は、該当列車を併合する駅で入換が可能であるかどうかを記憶部１１００に格納した入換可否情報７を基に判定し、入換不可能であれば、仮に割り振った編成位置を該当列車の編成位置として設定する。
Ｓ１４０６〜Ｓ１４０９は、実施例１に示した通りである。
本実施例によれば、実施例１のＳ２０６を上記のようなフローに置き換え、それ以外は実施例１と同じように実施することで、資源運用計画を作成することができる。
【符号の説明】
【００９３】
１０００：資源運用計画作成装置、１００１：メモリ、１００２：プログラム、１００３：運行スケジュール読込部、１００４：ネットワーク作成部、１００５：併合候補判定部、１００６：併合候補反映部、１００７：計画作成部、１１００：記憶部、１２００：表示部、１２０１：入力部、１２０２：処理装置、１２０３：通信部、１２０４：データパス
【図１】
0005869276.tif 000007
【図２】
0005869276.tif 000008
【図３Ａ】
0005869276.tif 000009
【図３Ｂ】
0005869276.tif 000010
【図４】
0005869276.tif 000011
【図５】
0005869276.tif 000012
【図６】
0005869276.tif 000013
【図７】
0005869276.tif 000014
【図８】
0005869276.tif 000015
【図９】
0005869276.tif 000016
【図１０】
0005869276.tif 000017
【図１１】
0005869276.tif 000018
【図１２Ａ】
0005869276.tif 000019
【図１２Ｂ】
0005869276.tif 000020
【図１３】
0005869276.tif 000021
【図１４】
0005869276.tif 000022
【図１５Ａ】
0005869276.tif 000023
【図１５Ｂ】
0005869276.tif 000024
【図１６】
0005869276.tif 000025
【図１７】
0005869276.tif 000026