(57)【要約】【課題】コンピュータを用いたユニット割当計画の作成を実現するための手法を提案すること。【解決手段】列車ダイヤに従って着ノード及び発ノードを抽出する処理と、車両運用計画に従って初期留置ノード及び最終留置ノードを設定する処理と、駅属性に従って滞留ノードを列挙する処理とが行われて、列車運行にかかるユニットの事象を表すノードが作成される。また、列車ダイヤ及び駅属性に基づいて、作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークが作成される。そして、作成されたアークそれぞれに、所定の制約条件を満たし、且つ、各走行アークのペナルティ値の総和が最小となるように０以上のユニットの割当数が充当されて、列車ダイヤを実現するユニットの割当計画が作成される。【選択図】図２
2010064557.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、所与の列車ダイヤの各列車の各駅間それぞれに、列車を構成する単位であるユニットを割り当てる数を決定して、前記列車ダイヤに対する前記ユニットの割当計画を作成させるためのプログラムであって、
前記列車ダイヤに基づいて各列車の各駅の着発それぞれを表す着ノード及び発ノードを抽出する処理と、所与のユニット初期配置条件に基づいて各ユニットの初期留置駅での留置を表す初期留置ノードと各ユニットの最終留置駅を表す最終留置ノードとを設定する処理と、留置可能な駅への着ノードそれぞれの後に当該列車の一部又は全部のユニットを当該駅に留置することを表す滞留ノードを列挙する処理とを行って、列車運行にかかるユニットの事象を表すノードを作成するノード作成手段、
前記列車ダイヤに基づいて、前記ノード作成手段により作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークを作成するアーク作成手段、
前記アーク作成手段により作成されたアークそれぞれに所定のユニット運用条件を満たすように０以上のユニットの割当数を充当して、前記列車ダイヤを実現するユニットの割当計画を作成する割当計画作成手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
前記列車ダイヤの各列車の各駅間の予想利用者人数が予め与えられており、
前記ユニットには座席数及び／又は乗車定員が予め定められており、
前記割当計画作成手段が、
前記アーク作成手段により作成されたアークそれぞれに０以上のユニットの割当数を充当することで暫定割当計画を作成する暫定割当計画作成手段と、
前記暫定割当計画に含まれる発ノードと着ノード間のアークによって表される駅間走行アークに充当されたユニット数分の座席数及び／又は乗車定員と、当該駅間の予想利用者人数との差異を総ての駅間走行アークについて評価することで当該暫定割当計画を評価する評価手段と、
を有し、前記評価手段による評価結果が最高評価の暫定割当計画を割当計画とするように前記コンピュータを機能させるための請求項１に記載のプログラム。
【請求項３】
前記評価手段が、座席数及び／又は乗車定員に対する予想利用者人数の過不足が大きくなるに従ってより低く評価するとともに、不足になる場合の評価低減率よりも過剰になる場合の評価低減率の方を大きくして前記駅間走行アークの評価を行うように前記コンピュータを機能させるための請求項２に記載のプログラム。
【請求項４】
各駅それぞれについて列車の分割併合の可否と上り／下りの折返し可否とが予め駅条件として定められており、
前記ノード作成手段が、各駅それぞれの前記駅条件に従って滞留ノードを列挙し、
前記アーク作成手段が、各駅それぞれの前記駅条件に従って折返しアークを作成する、
ように前記コンピュータを機能させるための請求項１〜３の何れか一項に記載のプログラム。
【請求項５】
前記割当計画作成手段が、列車の分割併合が不可で、且つ、上り及び下りの少なくとも一方の折返しが可能な駅条件が定められた駅に対応付けて作成された着ノード及び発ノードについて、当該着ノードを元ノードとするアークのうち多くとも１つのアークのみに１以上の割当数を充当して残余のアークに０を充当し、当該発ノードを先ノードとするアークのうち多くとも１つのアークのみに１以上の割当数を充当して残余のアークに０を充当する、ように前記コンピュータを機能させるための請求項４に記載のプログラム。
【請求項６】
所与の列車ダイヤの各列車の各駅間それぞれに、列車を構成する単位であるユニットを割り当てる数を決定して、前記列車ダイヤに対する前記ユニットの割当計画を作成するユニット割当計画作成装置であって、
前記列車ダイヤに基づいて各列車の各駅の着発それぞれを表す着ノード及び発ノードを抽出する処理と、所与のユニット初期配置条件に基づいて各ユニットの初期留置駅での留置を表す初期留置ノードと各ユニットの最終留置駅を表す最終留置ノードとを設定する処理と、留置可能な駅への着ノードそれぞれの後に当該列車の一部又は全部のユニットを当該駅に留置することを表す滞留ノードを列挙する処理とを行って、列車運行にかかるユニットの事象を表すノードを作成するノード作成手段と、
前記列車ダイヤに基づいて、前記ノード作成手段により作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークを作成するアーク作成手段と、
前記アーク作成手段により作成されたアークそれぞれに所定のユニット運用条件を満たすように０以上のユニットの割当数を充当して、前記列車ダイヤを実現するユニットの割当計画を作成する割当計画作成手段と、
を備えたユニット割当計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータに、所与の列車ダイヤの各列車の各駅間それぞれに、列車を構成する単位であるユニットを割り当てる数を決定して、前記列車ダイヤに対する前記ユニットの割当計画を作成させるためのプログラム等に関する。
【背景技術】
【０００２】
計画ダイヤの作成において、利用者デマンドに応じて、臨時列車の増発方法を変更するきめ細かい輸送サービスを行っている鉄道会社がある。利用者デマンドは、ＩＣカードの普及による自動改札機データ（いわゆるＯＤ（Origin Destination）データ）や、大都市交通センサス等の交通統計から予測する手法も提案されている。
【０００３】
このような背景のもと、現有する車両や鉄道設備等の既存のリソースを制約として考慮し、利用者デマンドになるべく合致する列車ダイヤの作成を行いたいという要請があり、列車ダイヤの作成に関する技術が、例えば特許文献１に開示されている。
【特許文献１】特開２００７−２３７９４８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、列車は、１以上の車両が編成された自走可能な列車構成単位であるユニットが１又は複数連結されて構成される。新幹線が分かりやすい例である。複数のユニットで列車を構成する場合、駅においてユニットを分割或いは併合（以下、「分割併合」という。）することで、乗客に提供する座席数を増減調整する。
【０００５】
このような車両運用を、利用者デマンドに合致するように計画するためには、利用者のデマンドが多い駅間については、多くのユニットを列車に割り当て、逆に、利用者のデマンドが少ない駅間については、列車に割り当てるユニットの数を少なくすることが適切であると考えられる。しかしながら、車両運用計画を作成するに当たっては、計画ダイヤの実現と、車両検査周期を考慮した交番の実現とが優先されるため、列車に充当するユニット数を決定する計画（以下、「ユニット割当計画」という。）については、ほとんど研究されていないのが実状である。
【０００６】
本発明は上述した課題に鑑みて為されたものであり、その目的とするところは、コンピュータを用いたユニット割当計画の作成を実現するための手法を提案することである。
【課題を解決するための手段】
【０００７】
以上の課題を解決するための第１の発明は、
コンピュータに、所与の列車ダイヤの各列車の各駅間それぞれに、列車を構成する単位であるユニットを割り当てる数を決定して、前記列車ダイヤに対する前記ユニットの割当計画を作成させるためのプログラムであって、
前記列車ダイヤ（例えば、図１６の列車ダイヤデータ５０３、図１）に基づいて各列車の各駅の着発それぞれを表す着ノード（例えば、図３の着ノード）及び発ノード（例えば、図３の発ノード）を抽出する処理と、所与のユニット初期配置条件（例えば、図１５の車両運用計画データ５０９）に基づいて各ユニットの初期留置駅での留置を表す初期留置ノード（例えば、図３の初期留置ノード）と各ユニットの最終留置駅を表す最終留置ノード（例えば、図３の最終留置ノード）とを設定する処理と、留置可能な駅への着ノードそれぞれの後に当該列車の一部又は全部のユニットを当該駅に留置することを表す滞留ノード（例えば、図３の滞留ノード）を列挙する処理とを行って、列車運行にかかるユニットの事象を表すノードを作成するノード作成手段（例えば、図２０のステップＡ５）、
前記列車ダイヤに基づいて、前記ノード作成手段により作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアーク（例えば、図３の各種アーク）を作成するアーク作成手段（例えば、図２０のステップＡ５）、
前記アーク作成手段により作成されたアークそれぞれに所定のユニット運用条件を満たすように０以上のユニットの割当数を充当して、前記列車ダイヤを実現するユニットの割当計画（例えば、図１５のユニット割当計画データ６０５、図２）を作成する割当計画作成手段（例えば、図２０のステップＡ７）、
として前記コンピュータを機能させるためのプログラム（例えば、図１５のユニット割当計画作成プログラム５０１）である。
【０００８】
また、他の発明として、
所与の列車ダイヤの各列車の各駅間それぞれに、列車を構成する単位であるユニットを割り当てる数を決定して、前記列車ダイヤに対する前記ユニットの割当計画を作成するユニット割当計画作成装置であって、
前記列車ダイヤに基づいて各列車の各駅の着発それぞれを表す着ノード及び発ノードを抽出する処理と、所与のユニット初期配置条件に基づいて各ユニットの初期留置駅での留置を表す初期留置ノードと各ユニットの最終留置駅を表す最終留置ノードとを設定する処理と、留置可能な駅への着ノードそれぞれの後に当該列車の一部又は全部のユニットを当該駅に留置することを表す滞留ノードを列挙する処理とを行って、列車運行にかかるユニットの事象を表すノードを作成するノード作成手段（例えば、図１５のＣＰＵ１０；図２０のステップＡ５）と、
前記列車ダイヤに基づいて、前記ノード作成手段により作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークを作成するアーク作成手段（例えば、図１５のＣＰＵ１０；図２０のステップＡ５）と、
前記アーク作成手段により作成されたアークそれぞれに所定のユニット運用条件を満たすように０以上のユニットの割当数を充当して、前記列車ダイヤを実現するユニットの割当計画を作成する割当計画作成手段（例えば、図１５のＣＰＵ１０；図２０のステップＡ７）と、
を備えたユニット割当計画作成装置（例えば、図１５のユニット割当計画作成装置１）を構成してもよい。
【０００９】
この第１の発明等によれば、着ノード及び発ノードを抽出する処理と、初期留置ノード及び最終留置ノードを設定する処理と、滞留ノードを列挙する処理とが行われて、列車運行にかかるユニットの事象を表すノードが作成される。また、作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークが、列車ダイヤに基づいて作成される。そして、作成されたアークそれぞれに所定のユニット運用条件を満たすように０以上のユニットの割当数が充当されて、列車ダイヤを実現するユニットの割当計画が作成される。
【００１０】
列車運行にかかるユニットの事象を表すノードを作成し、遷移可能性のあるノード間を結ぶアークを作成することで、ユニットの遷移を表現するネットワークを生成することができる。そして、生成したネットワークを基に、所定のユニット運用条件を満たすように各アークそれぞれに０以上のユニットを割り当てることで、列車ダイヤを実現するユニットの割当計画を作成することができる。また、列車の一部又は全部のユニットを駅に留置することを表す滞留ノードを導入したことで、駅における列車の分割併合を考慮した割当計画の作成を実現し得る。
【００１１】
また、第２の発明として、第１の発明のプログラムであって、
前記列車ダイヤの各列車の各駅間の予想利用者人数（例えば、図１７の予想利用者人数５０５５、図１）が予め与えられており、
前記ユニットには座席数及び／又は乗車定員が予め定められており、
前記割当計画作成手段が、
前記アーク作成手段により作成されたアークそれぞれに０以上のユニットの割当数を充当することで暫定割当計画を作成する暫定割当計画作成手段（例えば、図２０のステップＡ７）と、
前記暫定割当計画に含まれる発ノードと着ノード間のアークによって表される駅間走行アークに充当されたユニット数分の座席数及び／又は乗車定員と、当該駅間の予想利用者人数との差異を総ての駅間走行アークについて評価することで当該暫定割当計画を評価する評価手段（例えば、図２０のステップＡ９）と、
を有し、前記評価手段による評価結果が最高評価の暫定割当計画を割当計画とする（例えば、図２０のステップＡ１１〜Ａ１９）ように前記コンピュータを機能させるためのプログラムを構成してもよい。
【００１２】
この第２の発明によれば、作成されたアークそれぞれに０以上のユニットの割当数を充当することで暫定割当計画が作成される。そして、暫定割当計画に含まれる発ノードと着ノード間のアークによって表される駅間走行アークに充当されたユニット数分の座席数及び／又は乗車定員と、当該駅間の予想利用者人数との差異を総ての駅間走行アークについて評価することで、当該暫定割当計画が評価される。そして、評価結果が最高評価の暫定割当計画が割当計画とされる。
【００１３】
暫定的なユニットの割当計画として作成した暫定割当計画を、座席数や乗車定員と予想利用者人数との差異に基づいてそれぞれ評価し、評価結果が最高評価の暫定割当計画を最終的なユニットの割当計画とすることで、利用者デマンドに最も適合する割当計画を作成することが可能となる。
【００１４】
また、第３の発明として、第２の発明のプログラムであって、
前記評価手段が、座席数及び／又は乗車定員に対する予想利用者人数の過不足が大きくなるに従ってより低く評価するとともに、不足になる場合の評価低減率よりも過剰になる場合の評価低減率の方を大きくして前記駅間走行アークの評価を行う（例えば、図１３のペナルティ関数）ように前記コンピュータを機能させるためのプログラムを構成してもよい。
【００１５】
この第３の発明によれば、座席数及び／又は乗車定員に対する予想利用者人数の過不足が大きくなるに従ってより低く評価するとともに、不足になる場合の評価低減率よりも過剰になる場合の評価低減率の方を大きくして駅間走行アークの評価を行う。座席数や乗車定員が過剰となる場合の方が、予想利用者人数が過剰となる場合よりも好ましいと考えられるため、前者の場合の評価低減率が、後者の場合の評価低減率よりも小さくなるようにしたものである。
【００１６】
また、第４の発明として、第１〜第３の何れかの発明のプログラムであって、
各駅それぞれについて列車の分割併合の可否と上り／下りの折返し可否とが予め駅条件（例えば、図１８の駅属性データ５０７）として定められており、
前記ノード作成手段が、各駅それぞれの前記駅条件に従って滞留ノードを列挙し、
前記アーク作成手段が、各駅それぞれの前記駅条件に従って折返しアーク（例えば、図３の折返しアーク）を作成する、
ように前記コンピュータを機能させるためのプログラムを構成してもよい。
【００１７】
この第４の発明によれば、各駅それぞれの駅条件に従って滞留ノードを列挙し、各駅それぞれの駅条件に従って折返しアークを作成する。折返しアークを作成することで、ユニットの駅での折返しを考慮した割当計画を作成することが可能となる。
【００１８】
また、第５の発明として、第４の発明のプログラムであって、
前記割当計画作成手段が、列車の分割併合が不可で、且つ、上り及び下りの少なくとも一方の折返しが可能な駅条件が定められた駅に対応付けて作成された着ノード（例えば、図１４の制着ノードＮ１）及び発ノード（例えば、図１４の制発ノードＮ２，Ｎ３）について、当該着ノードを元ノードとするアークのうち多くとも１つのアークのみに１以上の割当数を充当して残余のアークに０を充当し、当該発ノードを先ノードとするアークのうち多くとも１つのアークのみに１以上の割当数を充当して残余のアークに０を充当する（例えば、図１４のＳＯＳ１制約）、ように前記コンピュータを機能させるためのプログラムを構成してもよい。
【００１９】
この第５の発明によれば、列車の分割併合が不可で、且つ、上り及び下りの少なくとも一方の折返しが可能な駅条件が定められた駅に対応付けて作成された着ノード及び発ノードについて、当該着ノードを元ノードとするアークのうち多くとも１つのアークのみに１以上の割当数が充当されて残余のアークに０が充当され、当該発ノードを先ノードとするアークのうち多くとも１つのアークのみに１以上の割当数が充当されて残余のアークに０が充当される。
【００２０】
列車の分割併合が不可である駅においては、ユニットを列車に増結したり、列車からユニットを減車することができない。そのため、着ノードから出力するアークの集合及び発ノードに入力するアークの集合それぞれについて、多くとも１つのアークのみに１以上のユニット数が割り当てられ、残余のアークに割り当てられるユニット数は０となるようにしなければならない。これにより、いわゆるＳＯＳ１（Special Ordered Sets of Type1）制約に従ったユニットの割当を実現する。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照して、本発明に好適な実施形態の一例を説明する。但し、本発明を適用可能な実施形態がこれらに限定されるわけではない。
【００２２】
１．概説
本実施形態では、所与の列車ダイヤに従って運行する各列車に対して、単独で双方向に自走可能な列車構成単位（以下、「ユニット」という。）を割り当てる数を決定する計画（以下、「ユニット割当計画」という。）を作成する。
【００２３】
図１は、列車ダイヤの一例を示す図である。図１では、横軸を時間、縦軸を駅として、点線で示される臨時列車の列車スジと、実線で示される定期列車の列車スジとを示している。縦軸上方向に向かう列車が上りの列車であり、縦軸下方向に向かう列車が下りの列車である。Ａ駅からＤ駅に向かう下りの臨時列車と、Ｄ駅からＡ駅に向かう上りの臨時列車と、Ａ駅からＤ駅に向かう下りの定期列車と、Ｄ駅からＡ駅に向かう上りの定期列車との４本の列車の列車スジが示されている。
【００２４】
また、各列車の各駅間には、当該列車を利用することが予想される乗客の人数（以下、「予想利用者人数」という。）が定められている。この予想利用者人数は、ＯＤデータや大都市交通センサス等の交通統計から予測される。本実施形態は、この予測に特徴があるものではなく、予め予想利用者人数が与えられているものである。図１に示すような各列車の各駅間の予想利用者人数が与えられた場合に、各列車それぞれについて、当該列車に各駅間でユニットをいくつ割り当てれば効率良く乗客を運送することができるかを決定することが、本願実施形態の目的である。
【００２５】
図２は、図１の列車ダイヤに対して実際にユニット割当計画を作成した場合の結果の一例を示す図である。図２では、図１の４本の列車それぞれについて、当該列車の各駅間に割り当てるユニット１つ１つを太実線で示している。１ユニット当たりの座席数は１０席とした。座席数とは、着席可能な人数の意味である。また、使用可能なユニットの総数（以下、「ユニット総数」という。）は１０ユニット、１列車に連結可能な最大のユニット数（以下、「最大充当可能ユニット数」という。）は４ユニットとした。
【００２６】
この結果を見ると、各駅間の予想利用者人数に応じた適切な数のユニットが割り当てられていることがわかる。しかし、上りの定期列車のＢ駅→Ａ駅間では、予想利用者人数が５０人であるのに対し、割り当てられたユニットの数は４ユニット（４０席）となっており、座席が１０席不足している。これは、最大充当可能ユニット数が４ユニットに制限されているためである。
【００２７】
また、下りの定期列車のＣ駅→Ｄ駅間では、予想利用者人数が３０人であるのに対し、割り当てられたユニットの数は２ユニット（２０席）となっており、この場合も座席が１０席不足している。これは、ユニット総数が１０ユニットに限られているため、他の列車に割り当てられるユニット数との関係で、１ユニット不足することによるものである。
【００２８】
２．原理
次に、ユニット割当計画作成の原理について説明する。本実施形態では、最初に、列車運行にかかるユニットの事象を表す「ノード」を列挙し、ユニットの遷移可能性のあるノード間を有向辺である「アーク」によって結合することでネットワークを生成する。
【００２９】
図３は、ネットワークを構成するノードとアークの説明図である。本実施形態では、５種類のノードと６種類のアークとを用いて、ネットワークを生成する。具体的には、ノードとして、各列車が駅に到着した事象を表す「着ノード」、各列車が駅から発車した事象を表す「発ノード」、各ユニットの初期留置駅での留置を表す「初期留置ノード」、各ユニットの最終留置駅での留置を表す「最終留置ノード」、各ユニットの駅での留置を表す「滞留ノード」を作成する。
【００３０】
また、アークとして、列車が走行していることを表す「走行アーク」、列車が駅に停車していることを表す「停車アーク」、ユニットが駅に留置されたままであることを表す「駅留置アーク」、列車にユニットを充当することを表す「増結アーク」、列車からユニットを分離することを表す「減車アーク」、ユニットが駅で折返すことを表す「折返しアーク」を作成する。
【００３１】
図中では、着ノードを「着」、発ノードを「発」、初期留置ノードを「初」、最終留置ノードを「終」、滞留ノードを「滞」としてそれぞれ示している。また、走行アーク及び停車アークを細実線、駅留置アークを太実線、増結アークを破線、減車アークを点線、折返しアークを一点鎖線でそれぞれ示している。
【００３２】
ノード及びアークの作成方法は、各駅における列車の分割併合の可否、及び、折返しの可否によって異なる。詳細には、各駅における分割併合の可否、及び、上り／下りの折返しの可否の組合せとして与えられる８通りのパターンそれぞれについて、ノード及びアークを作成する。
【００３３】
図４〜図１１を参照して、ノード及びアークの作成方法について具体的に説明する、ここでは、Ａ駅〜Ｃ駅の３駅のうち、Ｂ駅に着目した場合のノード及びアークの作成方法を例に挙げて説明する。図４〜図１１において、横軸は時間、縦軸は駅をそれぞれ示している。
【００３４】
（Ａ）分割併合が可能で、折返しが可能な場合
図４は、Ｂ駅が、列車の分割併合が可能で、折返しも可能な場合におけるノード及びアークの作成方法の説明図である。先ず、所与の車両運用計画（ユニットの初期配置計画）に従い、Ｂ駅でユニットの初期留置がなされる場合は、Ｂ駅の先端部分に初期留置ノードを配置する。そして、初期留置ノードの直後に滞留ノード（以下、このノードを「初期滞留ノード」という。）を１つ配置し、初期留置ノードから初期滞留ノードに対して駅留置アークを引く。
【００３５】
同様に、所与の車両運用計画に従い、Ｂ駅でユニットが最終留置されなければならない場合は、Ｂ駅の末端部分に最終留置ノードを配置する。そして、最終留置ノードの直前に滞留ノード（以下、このノードを「最終滞留ノード」という。）を１つ配置し、最終滞留ノードから最終留置ノードに対して駅留置アークを引く。
【００３６】
次に、着ノード及び発ノードを、所与の列車ダイヤに基づいて抽出して配置する。具体的には、列車ダイヤとして定められた各列車の各駅の着発事象それぞれに対応する着ノード及び発ノードを配置する。そして、当該列車の運行に従って、対応する発ノードから着ノードに対して走行アークを引き、着ノードから同じ駅の直後の発ノードに対して停車アークを引く。駅間の走行アークは、列車スジを表していると言え、停車アークは、その駅で列車が停車することを表していると言える。
【００３７】
また、１つの着ノードに対して、その着ノード以降で最も早い同じ駅の異なる列車の発ノードとの間に、滞留ノードを１つ配置する。そして、同じ駅の滞留ノードを、駅留置アークで順番に結んでいく。また、同じ駅の滞留ノードから次の発ノードへと増結アークを引き、同じ駅の着ノードから次の滞留ノードへと減車アークを引く。
【００３８】
尚、Ｂ駅では列車の折返しが可能であるが、「（Ａ）分割併合が可能で、折返しが可能な場合」については、例外的に折返しアークを引かない。
【００３９】
（Ｂ）分割併合が可能で、上りから下りの折返しが可能な場合
図５は、Ｂ駅が、列車の分割併合が可能で、上りから下りの折返しが可能な場合におけるノード及びアークの作成方法の説明図である。この場合は、上りと下りを区別するため、滞留ノードを上りと下りに分ける。
【００４０】
具体的には、上り用の滞留ノードとして「上滞留ノード」、下り用の滞留ノードとして「下滞留ノード」を、初期留置ノードの直後と最終留置ノードの直前にそれぞれ配置する。また、１つの着ノードに対して、当該着ノードが下りの列車の着ノードである場合は、その着ノード以降で最も早い同じ駅の異なる列車の発ノードとの間に、下滞留ノードを１つ配置する。同様に、当該着ノードが上りの列車の着ノードである場合は、その着ノード以降で最も早い同じ駅の異なる列車の発ノードとの間に、上滞留ノードを１つ配置する。
【００４１】
そして、上滞留ノードは上滞留ノード同士を、下滞留ノードは下滞留ノード同士を、駅留置アークで順番に結んでいく。また、上滞留ノードから上りの列車の発ノードに対して増結アークを引き、下滞留ノードから下りの列車の発ノードに対して増結アークを引く。同様に、上りの列車の着ノードから上滞留ノードに対して減車アークを引き、下りの列車の着ノードから下滞留アークに対して減車アークを引く。また、上りから下りの折返しのみが可能であるため、上りの列車の着ノードから下りの列車の発ノードに対してのみ折返しアークを引く。
【００４２】
（Ｃ）分割併合が可能で、下りから上りの折返しが可能な場合
図６は、Ｂ駅が、列車の分割併合が可能で、下りから上りの折返しが可能な場合におけるノード及びアークの作成方法の説明図である。この場合は、「（Ｂ）分割併合が可能で、上りから下りの折返しが可能な場合」とほぼ同様である。異なるのは、下りから上りの折返しのみが可能であるため、下りの列車の着ノードから上りの列車の発ノードに対してのみ折返しアークを引くことである。
【００４３】
（Ｄ）分割併合が可能で、折返しが不可な場合
図７は、Ｂ駅が、列車の分割併合が可能で、折返しが不可な場合におけるノード及びアークの作成方法の説明図である。この場合は、「（Ｂ）分割併合が可能で、上りから下りの折返しが可能な場合」とほぼ同様である。異なるのは、折返しが不可であるため、折返しアークを引かないことである。
【００４４】
（Ｅ）分割併合が不可で、折返しが可能な場合
図８は、Ｂ駅が、列車の分割併合が不可で、折返しが可能な場合におけるノード及びアークの作成方法の説明図である。この場合は、滞留アークの上りと下りは区別しない。また、列車の分割併合が不可であるため、初期滞留ノードと最終滞留ノード以外は、滞留ノードを列挙しない。
【００４５】
初期滞留ノードから最終滞留ノードに対して駅留置アークを引く。また、初期滞留ノードから全ての発ノードに対して増結アークを引き、全ての着ノードから最終滞留ノードに対して減車アークを引く。また、上りから下りの折返し、下りから上りの折返しが共に可能であるため、上りの列車の着ノードから下りの列車の発ノードに対して折返しアークを引き、下りの列車の着ノードから上りの列車の発ノードに対して折返しアークを引く。
【００４６】
（Ｆ）分割併合が不可で、上りから下りの折返しが可能な場合
図９は、Ｂ駅が、列車の分割併合が不可で、上りから下りの折返しが可能な場合におけるノード及びアークの作成方法の説明図である。この場合は、「（Ｅ）分割併合が不可で、折返しが可能な場合」とほぼ同様である。異なるのは、上りから下りの折返しのみが可能であるため、上りの列車の着ノードから下りの列車の発ノードに対してのみ折返しアークを引くことである。
【００４７】
（Ｇ）分割併合が不可で、下りから上りの折返しが可能である場合
図１０は、Ｂ駅が、列車の分割併合が不可で、下りから上りの折返しが可能である場合におけるノード及びアークの作成方法の説明図である。この場合は、「（Ｅ）分割併合が不可で、折返しが可能な場合」とほぼ同様である。異なるのは、下りから上りの折返しのみが可能であるため、下りの列車の着ノードから上りの列車の発ノードに対してのみ折返しアークを引くことである。
【００４８】
（Ｈ）分割併合が不可で、折返しが不可な場合
図１１は、Ｂ駅が、列車の分割併合が不可で、折返しも不可な場合におけるノード及びアークの作成方法の説明図である。Ｂ駅では、分割併合も折返しも不可であることから、初期滞留ノードと最終滞留ノード以外は、滞留ノードを列挙しない。また、ユニット数の変化が起こらないため、増結アーク、減車アーク及び折返しアークを引かない。
【００４９】
以上の手順に従って、全ての駅についてノード及びアークを列挙することで、例えば図１２に示すようなネットワークが出来上がる。ネットワークが生成できたら、当該ネットワークに含まれる各アークそれぞれの重みを決定する。アークの重みは、列車に割り当てるユニットの数を表している。すなわち、各アークそれぞれの重みを決定することは、各駅間において各列車に割り当てるユニットの数を決定することと等価である。
【００５０】
各走行アークは、列車が各駅間を走行することを表しており、列車スジと同義である。前述したように、各列車スジには予想利用者人数が対応付けられている。本実施形態では、各走行アーク（列車スジ）について「ペナルティ値」と呼ばれる評価値を算出し、全ての走行アークのペナルティ値の総和（以下、「総ペナルティ値」という。）が最小となるように、各アークそれぞれの重みを決定する。ペナルティ値は、ペナルティ関数と呼ばれる関数を用いて算出し、ペナルティ値が小さいほど、当該走行アークの評価が高いことを意味する。
【００５１】
図１３は、ペナルティ関数の一例を示す図である。図１３において、横軸正方向は不足座席数、横軸負方向は過剰座席数、縦軸はペナルティ値をそれぞれ示している。ペナルティ関数は、走行アークに対応付けられた予想利用者人数と、当該走行アークの重み（ユニット数）で乗客に提供可能な座席数との差分を変数とする関数であり、例えば図１３に示すような１次関数で表される。
【００５２】
特徴的であることの１つは、予想利用者人数が座席数を上回る場合（座席が不足する場合）におけるペナルティ関数の傾きが、座席数が予想利用者人数を上回る場合（座席が過剰となる場合）におけるペナルティ関数の傾きよりも大きくなっている点である。言い換えると、予想利用者人数が過剰である場合の方が、予想利用者人数が不足する場合よりもペナルティ値が高くなるように（走行アークの評価が低くなるように）、ペナルティ関数が定められている。
【００５３】
このようなペナルティ関数を用いることで、車両の走行にかかるペナルティ（過剰座席数に対するペナルティ）よりも、利用者の需要を満たさないことに対するペナルティ（不足座席数に対するペナルティ）を重視した、利用者のデマンドに見合った評価ができる。また、利用者の需要を満たさないことに対するペナルティのみでなく、鉄道会社側のコスト（車両の走行にかかるペナルティ）をも考慮した評価を実現できる点も、本実施形態のペナルティ関数の特徴である。
【００５４】
また、本実施形態では、以下の（１）〜（７）の制約条件を満たすように、各アークの重みを決定する。
【００５５】
（１）ユニット総数
ユニット総数は予め定められているため、最初に駅に留置されているユニットの総数と、最後に駅に留置されるユニットの総数とは一致しなければならない。具体的には、次式（１）を満たす必要がある。
【数１】
2010064557.tif 000003
但し、「ｙtotal」はユニット総数であり、「ｗt」はアークｔの重み、「Ａstart」は初期留置ノードと初期滞留ノードとを結ぶアークの集合、「Ａend」は最終滞留ノードと最終留置ノードとを結ぶアークの集合をそれぞれ示している。
【００５６】
（２）流量保存則
各ノードそれぞれについて、当該ノードに入力するアークの重みの総和と、当該ノードから出力するアークの重みの総和とは一致しなければならない。具体的には、次式（２）を満たす必要がある。
【数２】
2010064557.tif 000004
但し、「Ａin」はノードに入力するアークの集合、「Ａout」はノードから出力するアークの集合をそれぞれ示している。
【００５７】
（３）１列車当たりの最大ユニット数
各列車の各駅間について、列車に最大限割り当て可能なユニット数（最大充当可能ユニット数）が定められており、この最大充当可能ユニット数を超えるユニット数を列車に割り当てることはできない。具体的には、次式（３）を満たす必要がある。
【数３】
2010064557.tif 000005
但し、「Ｕmax」は１列車当たりの最大充当可能ユニット数、「Ａrun」は走行アークの集合、「Ａstop」は停車アークの集合をそれぞれ示している。
【００５８】
（４）１列車当たりの最低ユニット数
各列車の各駅間について、列車に最低限割り当てなければならないユニット数（最小充当ユニット数）が予め定められており、この最小充当ユニット数に満たないユニット数を列車に割り当てることはできない。具体的には、次式（４）を満たす必要がある。
【数４】
2010064557.tif 000006
但し、「ｕt」は走行アークｔの最小充当ユニット数を示している。
【００５９】
（５）各駅に留置可能なユニット数の上限
各駅において、留置されているユニットの数が、当該駅に留置可能なユニット数の上限（以下、「最大留置可能ユニット数」という。）を超えないことが必要である。具体的には、各滞留ノードそれぞれについて、次式（５）を満たす必要がある。
【数５】
2010064557.tif 000007
但し、「ｙmax」は最大留置可能ユニット数である。
【００６０】
（６）整数制約
ユニット数は整数であるため、各アークの重みは整数でなければならない。具体的には、次式（６）を満たす必要がある。
【数６】
2010064557.tif 000008
但し、「Ｚ+」は整数、「Ａall」は全てのアークの集合をそれぞれ示している。
【００６１】
（７）ＳＯＳ１（Special Ordered Sets of Type1）制約
ＳＯＳ１制約とは、ある集合に含まれるアークのうち、多くとも１つのアークのみが正の値を取る（全てのアークの重みが０となるか、１つのアーク以外のアークの重みは全て０となる）という制約である。このＳＯＳ１制約は、列車の分割併合が不可で、且つ、上り及び下りの少なくとも一方の折返しが可能な駅に対応付けて作成された着ノード及び発ノードについて、当該着ノードから出力するアークの集合及び当該発ノードに入力するアークの集合に適用される。以下の説明では、ＳＯＳ１制約の対象とする着ノード及び発ノードを、それぞれ「制着ノード」及び「制発ノード」と呼ぶ。
【００６２】
図１４は、ＳＯＳ１制約を説明するための図である。ここでは、Ｂ駅が、列車の分割併合が不可であり、折返しが可能な駅であるものとして説明する。例えば、制着ノードＮ１に着目した場合、制着ノードＮ１からは、１本の停車アークと、２本の折返しアークと、１本の減車アークとの計４本のアークが出力している。これにより、例えばＣ駅からＢ駅に到着した列車が４ユニットで構成されている場合、これら４本のアークに、それぞれ１ユニットずつユニットを割り当てることが可能であることになる。
【００６３】
しかし、Ｂ駅は列車の分割併合が不可な駅であるため、ユニットを分離させることはできない。従って、４本のアークのうち、何れか１本のアークにのみ４ユニットを割り当て、他のアークに割り当てるユニット数は０としなければならない。
【００６４】
同様に、例えば制発ノードＮ２及びＮ３についても、これらのノードに入力する１本の停車アークと、１本の増結アークと、１本の折返しアークとの計３本のアークのうち、何れか１本のアークに割り当てられるユニット数のみが正の値となり、他のアークに割り当てられるユニット数は０としなければならない。
【００６５】
以上の（１）〜（７）の制約条件を満たし、且つ、全ての走行アークのペナルティ値の総和（総ペナルティ値）が最小となるように決定された各アークの重みが、最終的に求めるユニット割当計画となる。
【００６６】
３．実施例
次に、上述した原理に従ってユニット割当船計画を作成する装置であるユニット割当計画作成装置１について説明する。
【００６７】
３−１．構成
図１５は、ユニット割当計画作成装置１の機能構成を示すブロック図である。ユニット割当計画作成装置１は、ＣＰＵ（Central Processing Unit）１０と、操作部２０と、表示部３０と、通信部４０と、ハードディスク５０と、ＲＡＭ（Random Access Memory）６０とを備え、各部はバス７０で相互にデータ通信可能に接続されて構成されるコンピュータシステムである。
【００６８】
ＣＰＵ１０は、ハードディスク５０に記憶されているシステムプログラム等に従ってユニット割当計画作成装置１の各部を統括的に制御するプロセッサである。特に、ＣＰＵ１０は、ハードディスク５０に記憶されているユニット割当計画作成プログラム５０１に従ってユニット割当計画作成処理を行ってユニット割当計画を作成し、作成したユニット割当計画を表示部３０に表示させる。
【００６９】
操作部２０は、例えばキーボードやタッチパネル等により構成される入力装置であり、押下されたキーやアイコンの信号をＣＰＵ１０に出力する。この操作部２０の操作により、各種データの入力等がなされる。
【００７０】
表示部３０は、ＬＣＤ（Liquid Crystal Display）等により構成され、ＣＰＵ１０から入力される表示信号に基づいた各種表示を行う表示装置である。表示部３０には、ＣＰＵ１０により作成されたユニット割当計画等が表示される。
【００７１】
通信部４０は、ＣＰＵ１０の制御に基づいて、装置内部で利用される情報をインターネット等の通信ネットワークを介して外部とやりとりするための通信装置である。
【００７２】
ハードディスク５０は、磁気ヘッド等を用いてデータの読み書きを行う記憶装置であり、ユニット割当計画作成装置１が備える各種機能を実現するためのプログラムやデータ等を記憶している。ハードディスク５０には、例えば、ＣＰＵ１０により読み出され、ユニット割当計画作成処理（図２０参照）として実行されるユニット割当計画作成プログラム５０１と、列車ダイヤデータ５０３と、列車駅間データ５０５と、駅属性データ５０７と、車両運用計画データ５０９とが記憶されている。
【００７３】
ユニット割当計画作成処理とは、ＣＰＵ１０が、暫定的なユニット割当計画である暫定ユニット割当計画を作成して、各アークについて設定されたペナルティ値の総和である総ペナルティ値を算出する処理を所定回数（例えば「１００回」）繰り返し実行し、最も総ペナルティ値が小さい暫定ユニット割当計画を、最終的なユニット割当計画として出力する処理である。ユニット割当計画作成処理については、フローチャートを用いて詳細に後述する。
【００７４】
図１６は、列車ダイヤデータ５０３のデータ構成の一例を示す図である。列車ダイヤデータ５０３には、列車番号５０３１と、列車種別５０３２と、上下識別５０３３と、駅５０３４と、着時刻５０３５と、発時刻５０３６とが対応付けて記憶されている。
【００７５】
列車番号５０３１は、各列車をユニークに識別するための番号である。列車種別５０３２は、当該列車が臨時列車と定期列車の何れの種類の列車であるかを示しており、「臨時」又は「定期」が記憶される。上下識別５０３３は、当該列車が上りと下りの何れの列車であるかを示しており、「上り」又は「下り」が記憶される。
【００７６】
駅５０３４は、列車が着発する駅を示しており、駅名が記憶される。着時刻５０３５は、当該列車が当該駅に到着する時刻である。当該列車が当該駅からの始発列車である場合は、「始発」が記憶される。また、発時刻５０３６は、当該列車が当該駅から発車する時刻である。当該列車が当該駅への終着列車である場合は、「終着」が記憶される。
【００７７】
図１６において、例えば、列車Ｔ１は、Ａ駅を始発駅とし、Ｄ駅を終着駅とする下りの臨時列車である。列車Ｔ１は、Ａ駅を「７時３０分」に発車して、Ｂ駅に「７時４５分」に到着する。そして、Ｂ駅を「７時４７分」に発車して、Ｃ駅に「８時０５分」に到着する。そして、Ｃ駅を「８時０８分」に発車して、Ｄ駅に「８時２０分」に到着する。
【００７８】
ユニット割当計画作成処理において、ＣＰＵ１０は、列車ダイヤデータ５０３のデータ内容に基づいて、各列車の各駅の着ノード及び発ノードを抽出する処理を行う。そして、これらのデータ内容に基づいて、着発ノード間を結ぶ走行アーク及び停車アークを作成することで、ネットワークを生成する。
【００７９】
図１７は、列車駅間データ５０５のデータ構成の一例を示す図である。列車駅間データ５０５には、列車番号５０５１と、駅間５０５２と、最小充当ユニット数５０５３と、最大充当可能ユニット数５０５４と、予想利用者人数５０５５とが対応付けて記憶されている。
【００８０】
列車番号５０５１は、図１６の列車ダイヤデータ５０３の列車番号５０３１に対応している。駅間５０５２は、当該列車が走行する駅間を示している。最小充当ユニット数５０５３は、当該列車の当該駅間に充当しなければならない最低限のユニット数である。尚、当該列車が臨時列車である場合は、最小充当ユニット数５０５３は設定されない。
【００８１】
最大充当可能ユニット数５０５４は、当該列車の当該駅間に充当することができる最大限のユニット数である。最大充当可能ユニット数５０５４は、当該列車が停車する各駅のプラットホームの長さ（ホーム長）等に従って設定される。予想利用者人数５０５５は、当該駅間において当該列車を利用することが予想される乗客の人数である。予想利用者人数５０５５は、例えばＯＤデータ等から予め算出されたデータである。
【００８２】
図１７において、例えば、定期列車Ｔ３のＡ駅→Ｂ駅の駅間における最小充当ユニット数は「２」であり、当該駅間における最大充当可能ユニット数は「４」である。また、当該駅間における予想利用者人数は「３０人」である。
【００８３】
ユニット割当計画作成処理において、ＣＰＵ１０は、列車ダイヤデータ５０３及び列車駅間データ５０５のデータ内容に基づいて、図１９に示すペナルティ値設定データ６０１を生成して、ＲＡＭ６０に記憶させる。
【００８４】
図１８は、駅属性データ５０７のデータ構成の一例を示す図である。駅属性データ５０７には、各駅５０７１それぞれについて、当該駅での列車の分割併合の可否５０７２と、上下の折返しの可否５０７３とが対応付けて記憶されている。例えば、Ｃ駅は、列車の分割併合が可能な駅であり、上りから下りの折返しは可能であるが、下りから上りの折返しは不可である。
【００８５】
車両運用計画データ５０９は、車両の運用計画についてのデータであり、例えば、各駅それぞれについて、最初に留置させる列車や最後に留置させる列車についてのデータが記憶されている。
【００８６】
ユニット割当計画作成処理において、ＣＰＵ１０は、駅属性データ５０７及び車両運用計画データ５０９のデータ内容に基づいて、初期留置ノード及び最終留置ノードを設定する処理と、滞留ノードを列挙する処理とを行う。そして、これらのデータ内容に基づいて、ノード間を結ぶ駅留置アーク、増結アーク、減車アーク及び折返しアークを作成することで、ネットワークを生成する。
【００８７】
ＲＡＭ６０は、読み書き可能な揮発性の記憶装置であり、ＣＰＵ１０により実行されるシステムプログラム、各種処理プログラム、各種処理の処理中データ、処理結果などを一時的に記憶するワークエリアを形成している。ＲＡＭ６０には、例えば、ペナルティ値設定データ６０１と、ネットワークデータ６０３と、ユニット割当計画データ６０５と、総ペナルティ値データ６０７とが記憶される。
【００８８】
図１９は、ペナルティ値設定データ６０１のデータ構成の一例を示す図である。ペナルティ値設定データ６０１には、列車番号６０１１と、駅間６０１２と、予想利用者人数６０１３と、候補ユニット数６０１４と、ペナルティ値６０１５とが対応付けて記憶されている。
【００８９】
列車番号６０１１、駅間６０１２及び予想利用者人数６０１３は、図１７の列車駅間データ５０５の列車番号５０５１、駅間５０５２及び予想利用者人数５０５５にそれぞれ対応している。候補ユニット数６０１４は、当該列車に当該駅間で割り当てるユニット数の候補である。列車駅間データ５０５において、最小充当ユニット数５０５３から最大充当可能ユニット数５０５４までの数値範囲に含まれるユニット数が、候補ユニット数６０１４となる。候補ユニット数６０１４は、各走行アークに割り当てる重みの候補であるとも言える。
【００９０】
ペナルティ値６０１５は、当該候補ユニット数６０１４で乗客に提供可能な座席数と、予想利用者人数６０１３とを用いて、図１３のペナルティ関数に従って算出される評価値である。ペナルティ値６０１５は、走行アークに当該候補ユニット数が重みとして割り当てられた場合におけるその割当の妥当性を判断するための指標値となるものである。
【００９１】
例えば、定期列車Ｔ４のＣ駅→Ｂ駅の駅間では、図１７の列車駅間データ５０５において最小充当ユニット数５０５３が「１」、最大充当可能ユニット数５０５４が「４」と設定されているため、候補ユニット数６０１４は、「１〜４」の数値範囲に含まれる値とされる。
【００９２】
また、当該駅間における予想利用者人数は３０人であり、候補ユニット数を「１」、「２」とした場合は、それぞれ座席が２０席、１０席不足するため、図１３のペナルティ関数に従って、ペナルティ値としてそれぞれ「２０」、「１０」が設定されている。但し、１ユニットの座席数は１０席である。
【００９３】
また、候補ユニット数を「３」とした場合は、座席が過不足なく乗客に割り当てられるため、ペナルティ値として最小の「０」が設定されており、候補ユニット数を「４」とした場合は、座席が１０席余るため、ペナルティ値として小さな値である「０．１」が設定されている。
【００９４】
ネットワークデータ６０３は、例えば図１２に示したようなネットワークに関するデータである。ユニット割当計画作成処理において、ＣＰＵ１０は、前述した原理に従ってノード及びアークで構成されるネットワークを生成して、ネットワークデータ６０３に記憶させる。
【００９５】
ユニット割当計画データ６０５は、総ペナルティ値が最も小さいユニット割当計画であって、最終的に出力するユニット割当計画のデータであり、ユニット割当計画作成処理においてＣＰＵ１０により更新される。
【００９６】
総ペナルティ値データ６０７は、ユニット割当計画データ６０５に記憶されたユニット割当計画の全ての走行アークに設定されたペナルティ値の総和であり、ユニット割当計画作成処理においてＣＰＵ１０により更新される。
【００９７】
３−２．処理の流れ
図２０は、ＣＰＵ１０によりハードディスク５０に記憶されているユニット割当計画作成プログラム５０１が読み出されて実行されることで、ユニット割当計画作成装置１において実行されるユニット割当計画作成処理の流れを示すフローチャートである。
【００９８】
先ず、ＣＰＵ１０は、初期設定を行う（ステップＡ１）。具体的には、操作部２０を介してユーザにより入力された列車ダイヤデータ５０３、列車駅間データ５０５、駅属性データ５０７及び車両運用計画データ５０９を、ハードディスク５０にそれぞれ記憶させる。
【００９９】
次いで、ＣＰＵ１０は、ハードディスク５０に記憶されている列車ダイヤデータ５０３及び列車駅間データ５０５を用いてペナルティ値設定データ６０１を生成し、ＲＡＭ６０に記憶させる（ステップＡ３）。
【０１００】
その後、ＣＰＵ１０は、前述した原理に従ってネットワークを生成するネットワーク生成処理を行い、生成したネットワークのデータをＲＡＭ６０にネットワークデータ６０３として記憶させる（ステップＡ５）。そして、ＣＰＵ１０は、暫定ユニット割当計画作成処理を行う（ステップＡ７）。
【０１０１】
図２１は、暫定ユニット割当計画作成処理の流れを示すフローチャートである。
先ず、ＣＰＵ１０は、ＲＡＭ６０のネットワークデータ６０３に記憶されているネットワークにおいて、全てのアークの重みを初期化する（ステップＢ１）。そして、ＣＰＵ１０は、ネットワークに含まれる各ノードそれぞれについて、ループＡの処理を実行する（ステップＢ３〜Ｂ２３）。
【０１０２】
ループＡの処理では、ＣＰＵ１０は、当該ノードが制着ノードであるか否かを判定し（ステップＢ５）、制着ノードであると判定した場合は（ステップＢ５；Ｙｅｓ）、当該ノード以外の他のノードに入出力するアークの重みを考慮しつつ、当該ノードから出力するアークの中からアークを１つ選択する（ステップＢ７）。
【０１０３】
その後、ＣＰＵ１０は、ステップＢ７で選択したアークに、当該ノードに入力する全てのアークの重みの合算値を設定するとともに（ステップＢ９）、選択したアーク以外の当該ノードから出力する全てのアークの重みを「０」に設定する（ステップＢ１１）。これらは、ＳＯＳ１制約に基づく処理である。そして、ＣＰＵ１０は、次のノードへと処理を移行する。
【０１０４】
一方、ステップＢ５において当該ノードが制着ノードではないと判定した場合は（ステップＢ５；Ｎｏ）、ＣＰＵ１０は、当該ノードが制発ノードであるか否かを判定する（ステップＢ１３）。そして、制発ノードであると判定した場合は（ステップＢ１３；Ｙｅｓ）、ＣＰＵ１０は、当該ノード以外の他のノードに入出力するアークの重みを考慮しつつ、当該ノードに入力するアークの中からアークを１つ選択する（ステップＢ１５）。
【０１０５】
その後、ＣＰＵ１０は、ステップＢ１５で選択したアークに、当該ノードから出力するアークの重みの合算値を設定するとともに（ステップＢ１７）、選択したアーク以外の当該ノードに入力する全てのアークの重みを「０」に設定する（ステップＢ１９）。これらも、ＳＯＳ１制約に基づく処理である。そして、ＣＰＵ１０は、次のノードへと処理を移行する。
【０１０６】
また、ステップＢ１３において当該ノードが制発ノードではないと判定した場合は（ステップＢ１３；Ｎｏ）、ＣＰＵ１０は、他のノードに入出力するアークの重みを考慮しつつ、流量保存則を満たすように、当該ノードから出力するアーク及び当該ノードに入力するアークの重みを設定する（ステップＢ２１）。そして、ＣＰＵ１０は、次のノードへと処理を移行する。
【０１０７】
全てのノードについてステップＢ５〜Ｂ２１の処理を行った後、ＣＰＵ１０は、ループＡの処理を終了する（ステップＢ２３）。その後、ＣＰＵ１０は、ＳＯＳ１制約及び流量保存則以外の他の制約条件が満たされているか否かを判定し（ステップＢ２５）、満たされていない制約条件があると判定した場合は（ステップＢ２５；Ｎｏ）、ステップＢ１に戻る。
【０１０８】
また、ステップＢ２５において全ての制約条件が満たされていると判定した場合は（ステップＢ２５；Ｙｅｓ）、設定した各アークの重みを暫定ユニット割当計画とする（ステップＢ２７）。そして、ＣＰＵ１０は、暫定ユニット割当計画作成処理を終了する。
【０１０９】
図２０のユニット割当計画作成処理に戻って、暫定ユニット割当計画作成処理を行った後、ＣＰＵ１０は、ＲＡＭ６０のペナルティ値設定データ６０１に記憶されているペナルティ値６０１５を用いて、暫定ユニット割当計画の総ペナルティ値を算出する（ステップＡ９）。すなわち、暫定ユニット割当計画に含まれる全ての走行アークのペナルティ値を合算することで、総ペナルティ値を求める。
【０１１０】
その後、ＣＰＵ１０は、算出した総ペナルティ値が、ＲＡＭ６０の総ペナルティ値データ６０７に記憶されている総ペナルティ値よりも小さいか否かを判定し（ステップＡ１１）、記憶されている総ペナルティ値以上であると判定した場合は（ステップＡ１１；Ｎｏ）、ステップＡ１７へと処理を移行する。
【０１１１】
また、ステップＡ１１において、記憶されている総ペナルティ値よりも小さいと判定した場合は（ステップＡ１１；Ｙｅｓ）、ＣＰＵ１０は、暫定ユニット割当計画作成処理で作成した暫定ユニット割当計画をユニット割当計画として、ユニット割当計画データ６０５を更新する（ステップＡ１３）。また、ステップＡ９で算出した総ペナルティ値で、総ペナルティ値データ６０７を更新する（ステップＡ１５）。
【０１１２】
次いで、ＣＰＵ１０は、暫定ユニット割当計画の作成を所定回数（例えば「１００回」）実行したか否かを判定し（ステップＡ１７）、まだ実行していないと判定した場合は（ステップＡ１７；Ｎｏ）、ステップＡ７に戻る。また、所定回数実行したと判定した場合は（ステップＡ１７；Ｙｅｓ）、ＲＡＭ６０のユニット割当計画データ６０５に記憶されているユニット割当計画を表示部３０に表示させた後（ステップＡ１９）、ユニット割当計画作成処理を終了する。
【０１１３】
４．作用効果
本実施形態によれば、列車ダイヤに従って着ノード及び発ノードを抽出する処理と、車両運用計画に従って初期留置ノード及び最終留置ノードを設定する処理と、駅属性に従って滞留ノードを列挙する処理とが行われて、列車運行にかかるユニットの事象を表すノードが作成される。また、列車ダイヤ及び駅属性に基づいて、作成されたノードのうち、ユニットの遷移可能性のあるノード間を結ぶアークが作成される。そして、作成されたアークそれぞれに、所定の制約条件を満たし、且つ、各走行アークのペナルティ値の総和が最小となるように０以上のユニットの割当数が充当されて、列車ダイヤを実現するユニットの割当計画が作成される。
【０１１４】
列車運行にかかるユニットの事象を表すノードを作成し、遷移可能性のあるノード間を結ぶアークを作成することで、ユニットの遷移を表現するネットワークを作成することができる。そして、作成したネットワークを基に、所定の制約条件を満たし、且つ、各走行アークのペナルティ値の総和が最小となるように０以上のユニットを割り当てることで、列車ダイヤを実現するユニットの割当計画を作成することが可能となる。また、本実施形態では、列車の一部又は全部のユニットを駅に留置することを表す滞留ノードを導入したことで、駅における列車の分割併合を考慮した適切な割当計画の作成を実現し得る。
【０１１５】
ペナルティ値は、ユニットの座席数と予想利用者人数との差を変数とするペナルティ関数に基づいて算出される。ペナルティ関数は、予想利用者人数が過剰である場合の方が、予想利用者人数が不足する場合よりもペナルティ値が大きくなるように（評価が低くなるように）予め定められている。これは、座席数が過剰となる場合の方が、予想利用者人数が過剰となる場合よりも好ましいと考えられるため、前者の場合の方が後者の場合よりも評価が高くなるようにしたものである。
【０１１６】
また、本実施形態では、列車の分割併合が不可で、且つ、上り及び下りの少なくとも一方の折返しが可能な駅条件が定められた駅に対応付けて作成された着ノード及び発ノードについて、当該着ノードを元ノードとするアークのうち多くとも１つのアークのみに１以上の割当数が充当されて残余のアークに０が充当され、当該発ノードを先ノードとするアークのうち多くとも１つのアークのみに１以上の割当数が充当されて残余のアークに０が充当される。
【０１１７】
列車の分割併合が不可な駅においては、ユニットを列車に充当したり、列車からユニットを分離することができない。そのため、ある着ノードから出力するアークの集合及びある発ノードに入力するアークの集合それぞれについて、多くとも１つのアークのみに１以上のユニット数が割り当てられ、残余のアークに割り当てられるユニット数は０となるようにしなければならない。これにより、いわゆるＳＯＳ１制約に従ったユニットの割当を実現する。
【０１１８】
５．変形例
５−１．ユニット割当計画作成装置
上述した実施形態では、ユニット割当計画作成装置を、作成したユニット割当計画を最終的なユニット割当計画として出力する装置として説明した。しかし、使用用途によっては、ユニット割当計画作成装置により作成されたユニット割当計画をもとに、さらに人手によって微調整を行って、最終的なユニット割当計画とする場合もあり得る。その場合には、ユニット割当計画作成装置は、ユニット割当計画の作成を支援する装置（ユニット割当計画作成支援装置）となるが、支援する装置と言えどもユニット割当計画作成装置の一種であり、本願発明の一実施形態と言える。
【０１１９】
５−２．乗車定員
上述した実施形態では、各ユニットには座席数が予め定められているものとして説明したが、座席数に加えて、或いは、座席数に代えて、乗車定員を予め定めておくこととしてもよい。座席数及び乗車定員の両方を予め定めておく場合は、例えば、座席数と予想利用者人数との差を第１の変数とし、乗車定員と予想利用者人数との差を第２の変数とするペナルティ関数を定義し、このペナルティ関数から算出される各走行アークのペナルティ値の総和を最小とするようにユニット割当計画を決定すればよい。
【０１２０】
また、乗車定員のみを予め定めておく場合は、乗車定員と予想利用者人数との差を変数とするペナルティ関数を定義し、このペナルティ関数から算出される各走行アークのペナルティ値の総和を最小とするようにユニット割当計画を決定する。尚、何れの場合も、予想利用者人数の過不足が大きくなるに従ってペナルティ値が大きくなり（評価が低くなり）、予想利用者人数が過剰になる場合のペナルティ値の増分が、予想利用者人数が不足になる場合のペナルティ値の増分よりも大きくなるようにペナルティ関数を設定しておくことにすれば好適である。
【０１２１】
５−３．ペナルティ関数
また、上述した実施形態では、図１３に示すような１次関数で表されるペナルティ関数を用いてペナルティ値を算出するものとして説明したが、この１次関数の傾きは適宜設定変更可能である。また、１次関数ではなく、２次以上の関数でペナルティ関数を表現することとしてもよい。
【図面の簡単な説明】
【０１２２】
【図１】列車ダイヤと予想利用者人数の一例を示す図。
【図２】ユニット割当計画の一例を示す図。
【図３】ノードとアークの説明図。
【図４】ノード及びアークの作成方法の説明図。
【図５】ノード及びアークの作成方法の説明図。
【図６】ノード及びアークの作成方法の説明図。
【図７】ノード及びアークの作成方法の説明図。
【図８】ノード及びアークの作成方法の説明図。
【図９】ノード及びアークの作成方法の説明図。
【図１０】ノード及びアークの作成方法の説明図。
【図１１】ノード及びアークの作成方法の説明図。
【図１２】ネットワークの一例を示す図。
【図１３】ペナルティ関数の一例を示す図。
【図１４】ＳＯＳ１制約の説明図。
【図１５】ユニット割当計画作成装置の機能構成を示すブロック図。
【図１６】列車ダイヤデータのデータ構成の一例を示す図。
【図１７】列車駅間データのデータ構成の一例を示す図。
【図１８】駅属性データのデータ構成の一例を示す図。
【図１９】ペナルティ値設定データのデータ構成の一例を示す図。
【図２０】ユニット割当計画作成処理の流れを示すフローチャート。
【図２１】暫定ユニット割当計画作成処理の流れを示すフローチャート。
【符号の説明】
【０１２３】
１              ユニット割当計画作成装置
１０            ＣＰＵ
２０            操作部
３０            表示部
４０            通信部
５０            ハードディスク
５０１          ユニット割当計画作成プログラム
５０３          列車ダイヤデータ
５０５          列車駅間データ
５０７          駅属性データ
５０９          車両運用計画データ
６０            ＲＡＭ
６０１          ペナルティ値設定データ
６０３          ネットワークデータ
６０５          ユニット割当計画データ
６０７          総ペナルティ値データ
７０            バス
【図１】
2010064557.tif 000009
【図２】
2010064557.tif 000010
【図３】
2010064557.tif 000011
【図４】
2010064557.tif 000012
【図５】
2010064557.tif 000013
【図６】
2010064557.tif 000014
【図７】
2010064557.tif 000015
【図８】
2010064557.tif 000016
【図９】
2010064557.tif 000017
【図１０】
2010064557.tif 000018
【図１１】
2010064557.tif 000019
【図１２】
2010064557.tif 000020
【図１３】
2010064557.tif 000021
【図１４】
2010064557.tif 000022
【図１５】
2010064557.tif 000023
【図１６】
2010064557.tif 000024
【図１７】
2010064557.tif 000025
【図１８】
2010064557.tif 000026
【図１９】
2010064557.tif 000027
【図２０】
2010064557.tif 000028
【図２１】
2010064557.tif 000029