(57)【要約】【課題】効率的に優良な運行経路を得ることができる運行経路決定装置及び運行経路決定方法を提供する。【解決手段】本発明の実施形態に係る運行経路決定装置は、各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、乗降場所情報を含む利用要求情報に応じて、各移動体の運行経路を決定する。運行経路決定装置は、列挙手段と、生成手段と、算出手段と、除外手段と、決定手段とを備える。列挙手段は、運行経路を生成する対象となる利用要求情報の集合の部分集合を列挙する。生成手段は、各部分集合に含まれる利用要求情報に応じて各移動体の運行経路を生成する。算出手段は、運行経路のそれぞれに対して評価値を算出する。特定手段は、生成手段が生成した運行経路の中から評価値に基づいて運行経路の候補を特定する。決定手段は、運行経路の候補の中から各移動体の運行経路を決定する。【選択図】図１
2015040780.tif 000002
【特許請求の範囲】
【請求項１】
各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、移動体の利用を要求するための乗降場所情報を含む利用要求情報に応じて、各移動体の運行経路を決定する運行経路決定装置であって、
運行経路を生成する対象となる前記利用要求情報の集合の部分集合を列挙する列挙手段と、
各部分集合に含まれる利用要求情報に応じて各移動体が運行する運行経路を生成する生成手段と、
前記生成手段が生成した運行経路のそれぞれに対して、移動体の運行情報に基づいて評価値を算出する算出手段と、
前記生成手段が生成した運行経路の中から前記評価値に基づいて運行経路の候補を特定する特定手段と、
前記運行経路の候補の中から各移動体の運行経路を決定する決定手段と、
を備える運行経路決定装置。
【請求項２】
前記決定手段は、各移動体の運行経路を決定するためのモデルを生成するモデル生成部と、
前記モデルに基づいて各移動体の運行経路を決定する運行経路決定部と、
を備え、
前記モデルは、運行経路を生成する対象となる全ての利用要求情報に応じるように各移動体の運行経路を選択した場合に、運行経路の評価値の合計が最も良い各移動体の運行経路を解とする集合被覆問題又は集合分割問題として定式化される請求項１に記載の運行経路決定装置。
【請求項３】
前記特定手段は、同一の移動体に対して生成された運行経路の中から複数の運行経路を選択し、
前記複数の運行経路の評価値の合計値と、前記複数の運行経路のそれぞれに対応する前記部分集合の和集合に対して生成された同一の移動体の運行経路の評価値と、を比較することにより、選択された複数の運行経路を運行経路の候補から除外するか否か判定するように構成された請求項１又は請求項２に記載の運行経路決定装置。
【請求項４】
前記特定手段は、前記移動体が運行する過程で同時に対応する利用要求情報数の最大値が所定値以上になる運行経路を運行経路の候補から除外するように構成された請求項１〜請求項３のいずれか１項に記載の運行路決定装置。
【請求項５】
前記特定手段は、前記移動体が運行する過程で乗降場所に停車する回数が所定の範囲を超える運行経路を運行経路の候補から除外するように構成された請求項１〜請求項４のいずれか１項に記載の運行経路決定装置。
【請求項６】
前記特定手段は、移動体が運行するのに要する時間が所定の範囲を超える運行経路を運行経路の候補から除外するように構成された請求項１〜請求項５のいずれか１項に記載の運行経路決定装置。
【請求項７】
前記特定手段は、同一の部分集合に含まれる利用要求情報に応じた同一の移動体の運行経路が複数生成された場合、複数生成された運行経路のうち少なくとも一部の運行経路を運行経路の候補から除外するように構成された請求項１〜請求項６のいずれか１項に記載の運行経路決定装置。
【請求項８】
前記利用要求情報には、移動体が利用されることを予測して予め入力された利用要求情報が含まれる請求項１〜請求項７のいずれか１項に記載の運行経路決定装置。
【請求項９】
前記決定手段により決定された運行経路において、複数の移動体が同一の利用要求情報に対応している場合、
前記決定手段は、当該利用要求情報に対応する移動体を１つ選択し、その他の移動体には当該利用要求情報に対応しない運行経路に改めて決定するよう構成された請求項１〜請求項８のいずれか１項に記載の運行経路決定装置。
【請求項１０】
前記列挙手段は、前記部分集合に含まれる利用要求情報の数が所定値以下の部分集合のみ列挙するように構成された請求項１〜請求項９のいずれか１項に記載の運行経路決定装置。
【請求項１１】
前記列挙手段は、利用要求情報が入力された時刻が所定の範囲に含まれる乗降場所が同一の複数の利用要求情報を、１つの利用要求情報として扱い、部分集合を列挙するように構成された請求項１〜請求項１０のいずれか１項に記載の運行経路決定装置。
【請求項１２】
前記利用要求情報には、移動体の利用要求が登録された時刻の情報が含まれる請求項１〜請求項１１のいずれか１項に記載の運行経路決定装置。
【請求項１３】
各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、移動体の利用を要求するための乗降場所情報を含む利用要求情報に応じて、各移動体の運行経路を決定する運行経路決定方法であって、
運行経路を生成する対象となる前記利用要求情報の集合の部分集合を列挙し、
各部分集合に含まれる利用要求情報に応じて各移動体が運行する運行経路を生成し、
前記生成手段が生成した運行経路のそれぞれに対して、移動体の運行情報に基づいて評価値を算出し、
前記生成手段が生成した運行経路の中から前記評価値に基づいて運行経路の候補を特定し、
前記運行経路の候補の中から各移動体の運行経路を決定する運行経路決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、運行経路決定装置及び運行経路決定方法に関する。
【背景技術】
【０００２】
従来、各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、移動体の利用を要求する利用要求情報に応じて各移動体の運行経路を決定するために、運行経路決定装置が利用されている。運行経路決定装置は、各移動体が運行可能な複数の運行経路に対してサービス時間などの評価値を算出し、評価値の良い運行経路を探索し、各移動体の運行経路として決定していた。
【０００３】
運行経路決定装置による運行経路の探索は、一般に運行経路の評価値をコスト（重み）とした集合被覆問題又は集合分割問題（以下、「集合被覆問題等」という）に帰着することができる。運行経路の探索を上述の集合被覆問題等に帰着した場合、運行経路は集合被覆問題等の解として求めることができ、利用者にとって最適な運行経路（評価値が最も良い運行経路）は、集合被覆問題等の厳密解として求めることができる。
【０００４】
しかし、各移動体の運行可能な経路数は組み合わせ的に増加するため、移動体の数や乗降場所の数によっては膨大な数となり、集合被覆問題等の厳密解を求めることは困難である。そこで、運行経路決定装置においては、利用者にとってできるだけ優良な運行経路（できるだけ評価値が良い運行経路）を探索するために、集合被覆問題等のより良い解（近似解）を求めることが重要となる。
【０００５】
このような集合被覆問題等の解法として、様々な方法が知られている。しかし、いずれの解法でも、効率的に質の良い解を得ることは困難であった。例えば、ルールベースの解構築法（貪欲法、近傍探索法）の場合、移動体が運行可能な運行経路の数が増加するほど、質の良い解が望めなくなった。
【０００６】
また、遺伝的アルゴリズム（GA, Genetic Algorithm）、焼きなまし法（SA, Simulated Annealing）及び列挙ベースの探索では、解の探索中に評価値を繰り返し計算しなければならないため、効率的に質の良い解を求めることができなかった。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００１−５１９３０７号公報
【特許文献２】特開２００６−１４３３６０号公報
【特許文献３】特開２００３−００６７８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
効率的に優良な運行経路を得ることができる運行経路決定装置及び運行経路決定方法を提供する。
【課題を解決するための手段】
【０００９】
本発明の実施形態に係る運行経路決定装置は、各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、移動体の利用を要求するための乗降場所情報を含む利用要求情報に応じて、各移動体の運行経路を決定する。運行経路決定装置は、列挙手段と、生成手段と、算出手段と、特定手段と、決定手段とを備える。列挙手段は、運行経路を生成する対象となる利用要求情報の集合の部分集合を列挙する。生成手段は、各部分集合に含まれる利用要求情報に応じて各移動体が運行する運行経路を生成する。算出手段は、生成手段が生成した運行経路のそれぞれに対して、移動体の運行情報に基づいて評価値を算出する。特定手段は、生成手段が生成した運行経路の中から評価値に基づいて運行経路の候補を特定する。決定手段は、運行経路の候補の中から各移動体の運行経路を決定する。
【００１０】
また、本発明の実施形態に係る運行経路決定方法は、各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体に対して、移動体の利用を要求するための乗降場所情報を含む利用要求情報に応じて、各移動体の運行経路を決定する。運行経路決定方法は、運行経路を生成する対象となる利用要求情報の集合の部分集合を列挙し、各部分集合に含まれる利用要求情報に応じて各移動体が運行する運行経路を生成し、生成手段が生成した運行経路のそれぞれに対して、移動体の運行情報に基づいて評価値を算出し、生成手段が生成した運行経路の中から評価値に基づいて運行経路の候補を特定し、運行経路の候補の中から各移動体の運行経路を決定する。
【図面の簡単な説明】
【００１１】
【図１】図１は、本発明の実施形態に係る運行経路決定装置及び移動体を示すブロック図である。
【図２】図２は、運行情報記憶部に記憶された運行情報の一例である。
【図３】図３は、運行ルール記憶部に記憶された運行ルールの一例である。
【図４】図４は、図１の運行経路決定装置が各移動体の運行経路を決定するまでの処理の概観を示すフローチャートである。
【図５】図５は、全呼びリスト作成部が作成する全呼びリストの一例である。
【図６】図６は、図５の全呼びリストに基づいて列挙された呼び集合の一例である。
【図７】図７は、全呼びリスト作成部が作成する全呼びリストの他の例である。
【図８】図９は、図７の全呼びリストに基づいて列挙された呼び集合の一例である。
【図９】図９は、評価値算出部が算出する運行経路の評価値の一例である。
【図１０】図１０は、運行経路生成部により生成された運行経路の中から運行経路特定手段により運行経路の候補として特定された運行経路の一例である。
【図１１】図１１は、モデル生成部が生成する運行経路を決定するためのモデルの一例である。
【図１２】図１２は、運行経路決定部が求める集合被覆問題等の解の一例である。
【図１３】図１３は、運行経路決定部が求める集合被覆問題等の解の一例である。
【図１４】図１４は、運行経路生成部が運行経路を生成する処理の一例を示すフローチャートである。
【図１５】図１５は、呼び集合ｋに含まれる各呼び情報の乗車階、降車階、進行方向を説明する説明図である。
【図１６】図１６は、運行経路生成部により作成された呼びリストＱの一例である。
【図１７】図１７は、運行経路除外部が運行経路を除外する処理の一例を示すフローチャートである。
【図１８】図１８は、運行経路除外部により選択された運行経路ｒ，ｔを示す一例である。
【図１９】図１９は、運行経路除外部が運行経路を除外する処理の他の例を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態について図面を参照して説明する。ここで、図１は、本発明の実施形態に係る運行経路決定装置及び移動体を示すブロック図である。
【００１３】
まず、運行経路決定装置が運行経路を決定する移動体１について説明する。移動体１は、利用者や貨物を乗車場所から降車場所まで移送する移送手段であり、所定の軌道上を運行する。所定の軌道上には、移動体１が利用者を乗降させる複数の乗降場所が設けられている。軌道上の複数の乗降場所は、各乗降場所間の経路、すなわち、軌道上の任意の乗車場所と降車場所との間の経路が移動体ごとに定められている。このような移動体１として、エレベータ、デマンドバス、乗り合いタクシーなどが含まれるが、これに限られない。移動体１が運行する運行経路の全体は、複数の移動体１が同時に運行可能な１つの軌道（複数台のデマンドバスが運行する道路など）により構成されてもよいし、１つの移動体１が運行する軌道（エレベータのかごの昇降路など）が複数設けられることにより構成されてもよい。
【００１４】
利用者は、移動体１を利用する際、移動体１の利用を要求する呼び（利用要求）を登録する。利用者により呼びが登録されると、運行経路決定装置には、移動体１の利用を要求する呼び情報（利用要求情報）が入力される。運行経路決定装置は、この呼び情報に応じて各移動体１の運行経路を決定する。
【００１５】
利用者が登録する呼びには乗車呼びと降車呼びの２種類がある。乗車呼びとは、利用者が移動体１へ乗車する乗車場所を指定する呼びであり、乗車呼び情報には乗車場所を示す乗車場所情報が含まれる。一方、降車呼びとは、利用者が移動体１から降車する降車場所を指定する呼びであり、降車呼び情報には降車場所を示す降車場所情報が含まれる。利用者は乗車呼びと降車呼びを同時に、あるいは別々に登録することができる。
【００１６】
利用者が乗車呼びと降車呼びを同時に登録する例として、移動体１が行き先階ボタン方式の（エレベータホールに行き先階ボタンが設置された）エレベータの場合が挙げられる。この場合、利用者は、乗車階で行き先階ボタンを押すことにより、乗車呼びと降車呼びの両方を同時に登録することができる。この呼び登録により入力される呼び情報には乗車階情報と降車階情報の両方が含まれる。
【００１７】
これに対して、利用者が乗車呼びと降車呼びを別々に登録する例として、移動体１が上下ボタン方式の（エレベータホールに上下ボタンが設置された）エレベータの場合が挙げられる。この場合、利用者は、乗車階で上下ボタンを押すことにより乗車呼びを登録することができ、この呼び登録により入力される呼び情報には乗車階情報は含まれる。しかし、上下ボタンでは降車階を指定できないため、利用者は、乗車呼びと同時に降車呼びを登録することができず、乗車したエレベータのかご内に設けられた行き先階ボタンを押すことで降車呼びを登録することとなる。
【００１８】
なお、上述した呼び情報には、乗降場所情報だけでなく、その呼びが登録された時刻である呼び登録時刻や、それぞれの呼びを識別する呼び番号などの情報が含まれる。
【００１９】
以上説明した移動体１は、利用者が呼びを登録すると、乗車呼びにより指定された乗車場所へ移動し、利用者を乗車させ、降車呼びにより指定された降車場所へ軌道上の所定の経路に従って移動し、利用者を降車させる。
【００２０】
次に、運行経路決定装置について説明する。運行経路決定装置は、軌道上を運行する複数の移動体１に対して呼びが登録された場合、登録された呼びに対応する移動体１と、移動体１が呼びに対応する順番と、を決定することにより各移動体１の運行経路を決定する。
【００２１】
運行経路決定装置は、図１に示すように、利用者が呼びを登録する呼び登録部２と、呼び情報を収集する呼び情報収集部３と、移動体の情報を収集する移動体情報収集部４と、運行情報を記憶する運行情報記憶部５と、運行経路を生成する運行経路生成手段６と、運行経路の評価値を算出する評価値算出部７と、運行経路の候補を特定する運行経路特定手段８と、運行経路を決定する運行経路決定手段９と、を備える。
【００２２】
呼び登録部２は、利用者が呼びを登録するための手段であり、乗車呼び又は降車呼びの少なくとも一方を登録できるように構成されている。利用者が呼びを登録すると、呼び登録部２は呼び情報を呼び情報収集部３へ送信する。呼び登録部２は、例えば、有線又は無線で呼び情報収集部３と接続された携帯端末であってもよい。この呼び登録部２は、表示部２１を備える。
【００２３】
表示部２１は、移動体１の運行情報などを表示するための手段であり、例えば、現在の移動体１の位置や、次に乗降場所に到着する移動体１はどれかなどの運行情報を表示する。これにより、利用者に移動体１の運行情報を提供することが可能になり、移動体１の利便性を向上させることができる。
【００２４】
呼び情報収集部３は、１つ又は複数の呼び登録部２が送信した呼び情報を収集するための手段であり、呼び登録部２から呼び情報を受信すると、受信した呼び情報を運行情報記憶部５に送信する。また、呼び情報収集部３は、外部（運行情報記憶部５や運行経路決定部９２など）から受信した情報を１つ又は複数の呼び登録部２に送信できるよう構成されてもよい。これにより、呼び情報収集部３は、運行情報記憶部５から受信した運行情報や、運行経路決定手段９から受信した運行経路の情報を、呼び登録部２に送信し、表示部２１に表示させることができる。呼び情報収集部３は、携帯端末とされ、外部（運行情報記憶部５や運行経路決定部９２など）と無線又は有線で通信できるよう構成されてもよい。
【００２５】
移動体情報収集部４は、移動体１から移動体情報を収集する手段であって、移動体１と無線又は有線で、あるいは携帯端末を介して接続されている。ここで、移動体情報とは、移動体１に関する情報であって、例えば、移動体１の現在位置などの情報が含まれる。移動体情報収集部４は、移動体１から収集した移動体情報を運行情報記憶部５に送信する。移動体情報収集部４が運行情報記憶部５に移動体情報を送信するタイミングは任意であり、例えば、移動体１が各乗降場所に到着したタイミングとすることができる。移動体情報収集部４は、携帯端末とされ、外部（運行経路決定部９２など）と無線又は有線で通信できるよう構成されてもよい。
【００２６】
また、移動体情報収集部４は、外部から受信した情報を表示できるように構成されてもよい。例えば、移動体１がデマンドバスのようにドライバーによって手動で運行される場合、移動体情報収集部４は、運行経路決定手段９から受信した運行経路情報を表示することで、運行経路決定装置が決定した運行経路をドライバーに提供することができる。
【００２７】
さらに、移動体情報収集部４は、外部から受信した情報に基づいて、移動体１を制御できるように構成されてもよい。例えば、移動体１がエレベータのように自動で運行される場合、移動体情報収集部４は、運行経路決定手段９から受信した運行経路情報に基づいて各移動体１の運行を制御することができる。
【００２８】
運行情報記憶部５は、移動体１の運行情報と、呼び情報収集部３から受信した呼び情報とを記憶した記憶部であり、記憶した運行情報を運行経路生成手段６に送信する。運行情報記憶部５が記憶する運行情報には、移動体情報収集部４から受信した移動体情報が含まれ、さらに、各乗降場所間の移動時間や各乗降場所での停車時間等の情報が含まれる。移動体１がエレベータである場合、図２に示すように、運行情報には階床間を昇降するためにかかる時間（traveling time）、ドアを閉めるためにかかる時間（door close time）、ドアを開けるためにかかる時間（door open time）、利用者がかごへ乗るのにかかる一人あたりの時間（load time per passenger）、利用者がかごから降りるのにかかる一人あたりの時間（unload time per passenger）、及び各かごの初期階床（car initial floor）が含まれる。図２において、階床間を昇降するためにかかる時間（traveling time）は、エレベータが現在位置から昇降する階床数に応じて要する時間として示されている。すなわち、このエレベータは、１階床昇降するために約４．４７秒かかり、２階床昇降するために約６．３秒かかる。また、図２の各かごの初期階床（car initial floor）は、エレベータが４つのかごを備え、各かごの初期階床が１階であることを示している。
【００２９】
また、運行情報記憶部５には、利用者が移動体１を利用することを予測して予め入力された呼び情報が記憶されてもよい。このような予測は、運行経路決定装置と他の装置（入退出管理システムやカメラ等のセンサ）とを連携させることにより可能となる。例えば、移動体１がエレベータであり、運行経路決定装置とカメラ等のセンサとが連携している場合、呼び情報は、センサが移動体１の乗降場所に接近する利用者を感知した時点で運行情報記憶部５に記憶されてもよい。当該呼び情報は、運行経路決定装置により生成されてもよいし、運行経路決定装置と連携した他の装置から入力されてもよい。これにより、移動体１が乗車場所に到着するまでの、利用者の待ち時間を短縮することができる。
【００３０】
運行経路生成手段６は、運行情報記憶部５から受信した運行情報及び呼び情報に応じた各移動体１の運行経路を生成する。運行経路生成手段６は、全呼びリストを作成する全呼びリスト作成部６１と、呼び集合を列挙する呼び集合列挙部６２と、運行経路を生成する運行経路生成部６３と、運行ルールが記憶された運行ルール記憶部６４とを備える。
【００３１】
全呼びリスト作成部６１は、運行情報記憶部５から運行情報及び呼び情報を受信し、これから運行経路を生成する対象となる呼び情報の一覧である全呼びリストを作成する。全呼びリストには、新たに追加された呼び情報だけでなく、すでに運行経路が決定されている呼び情報も含まれる。全呼びリストは、呼び情報を元（要素）とした集合であり、後述する呼び集合に対する全体集合となる。全呼びリスト作成部６１は、作成した全呼びリストを呼び集合列挙部６２に送信する。
【００３２】
呼び集合列挙部６２は、全呼びリストの部分集合である呼び集合を列挙する列挙手段である。すなわち、列挙された個々の呼び集合は、全呼びリストに含まれる呼び情報の少なくとも一部を元（要素）とする呼び情報の集合、または空集合である。全呼びリストにｎ個の元（呼び情報）が含まれている場合、呼び集合列挙部６２は、最大で２ｎ個の呼び集合を列挙することができる。呼び集合列挙部６２は、列挙した呼び集合を運行経路生成部６３に送信する。
【００３３】
運行経路生成部６３は、呼び集合列挙部６２が列挙した各呼び集合に対して、当該呼び集合に含まれる呼び情報に応じた各移動体１の運行経路を生成する生成手段である。運行経路生成部６３は、運行ルール記憶部６４に記憶された移動体１の運行ルールに従って運行経路を生成し、生成した運行経路を評価値算出部７に送信する。
【００３４】
運行ルール記憶部６４は、移動体１の運行に関するルールである運行ルールを記憶している。図３は、運行ルール記憶部６４に記憶された運行ルールの一例であり、運行ルールには、移動体の逆走のような利用者にとって不自然な運行や不快な運行を禁止するルールが含まれている。運行経路生成部６３は、このような運行ルールに従って運行経路を生成するため、移動体１が利用者にとって不自然な運行や不快な運行をする運行経路が生成されない。運行経路決定装置は、このような運行経路の中から移動体１の運行経路を決定するため、乗客に不満や不快感を与えない運行経路を決定することができる。
【００３５】
評価値算出部７は、運行経路生成部６３から受信した運行経路のそれぞれに対して評価値を算出する算出手段である。評価値算出部７は、運行情報記憶部５に記憶された運行情報と運行ルール記憶部６４に記憶された運行ルールとに基づいて運行経路の評価値を算出し、算出した評価値と、その評価値が算出された運行経路とを運行経路特定手段８に送信する。
【００３６】
評価値算出部７が算出する評価値として、サービス時間の合計値を用いることができる。サービス時間とは、利用者が呼びを登録してから降車場所で降車するまでに要する時間である。また、評価値として、未応答時間（利用者が呼びを登録してから移動体１が乗車場所に到着するまでに要する時間）、最大未応答時間、運行経路を運行する過程で移動体１が停車する回数、移動体１の輸送能力、及び移動体１を運行させるために消費する消費エネルギーなどを用いることもできる。運行経路の良否は評価値に基づいて判定されるが、判定方法は使用される評価値によって異なる。例えば、評価値がサービス時間である場合には、評価値が小さい、すなわちサービス時間が短い運行経路が優良な運行経路となり、評価値が移動体１の輸送能力の場合には、評価値が大きい、すなわち、移動体１の輸送能力が大きい運行経路が優良な運行経路となる。
【００３７】
運行経路特定手段８は、運行経路生成手段６が生成した運行経路の中から評価値算部７で算出された評価値に基づいて運行経路の候補を特定する特定手段である。運行経路特定手段８は、運行経路を記憶する運行経路記憶部８１と、運行経路を除外する運行経路除外部８２とを備える。
【００３８】
運行経路記憶部８１は、運行経路生成手段６が生成した運行経路を評価値算出部７から受信し、受信した運行経路とその評価値とを記憶する記憶部である。運行経路記憶部８１は、記憶した運行経路の一部を運行経路除外部８２により運行経路の候補から除外（削除）された後、残った運行経路、すなわち運行経路の候補として特定された運行経路を運行経路決定手段９に送信する。
【００３９】
運行経路除外部８２は、運行経路記憶部８１に記憶された運行経路の一部を評価値に基づいて運行経路の候補から除外する。運行経路除外部８２は、運行経路記憶部８１に記憶された運行経路の中から同一の移動体１の異なる呼び集合の運行経路を複数選択し、評価値に基づいて当該運行経路を運行経路の候補から除外するか否か判定し、除外する場合には運行経路記憶部８１から当該運行経路の情報を削除する。これにより、運行経路記憶部８１から評価値の悪い運行経路を削除する。
【００４０】
運行経路決定手段９は、運行経路生成手段６により生成された運行経路のうち運行経路特定手段８により運行経路の候補として特定された運行経路の中から各移動体１の運行経路を決定する決定手段である。運行経路決定手段９は、運行経路を決定するためのモデルを生成するモデル生成部９１と、モデルに基づいて各移動体１の運行経路を決定する運行経路決定部９２とを備える。
【００４１】
モデル生成部９１は、各移動体１の運行経路を決定するためのモデルを生成する。このモデルは、運行経路特定手段８から受信した運行経路とその評価値に基づく集合被覆問題又は集合分割問題として定式化することができる。モデル生成部９１は、生成したモデルを運行経路決定部９２に送信する。
【００４２】
運行経路決定部９２は、モデル生成部９１から受信したモデルに基づいて、各移動体１の運行経路を決定する。運行経路決定部９２は、上述の集合被覆問題等を解くことにより、各移動体１の運行経路を得る。運行経路決定部９２は、決定した各移動体１の運行経路を呼び情報収集部３及び移動体情報収集部４に送信する。
【００４３】
次に、本実施形態の運行経路決定装置の動作について説明する。まず、運行経路決定装置が各移動体１の運行経路を決定するまでの処理の概観を図４〜図１３を参照して説明する。ここで、図４は、本実施形態に係る運行経路決定装置が各移動体１の運行経路を決定するまでの処理の概観を示すフローチャートである。
【００４４】
（ステップＳ１０１）
全呼びリスト作成部６は、新たな運行経路を決定するタイミングか否かを判定する。新たな運行経路を決定するタイミングは、例えば、１つ以上の新たな呼び情報を運行情報記憶部５から受信したタイミングや、交通事情の変化（渋滞など）によって移動体１の運行に要する時間が変化したタイミングである。また、移動体１の利用を予約していた利用者が来なかった場合、あるいは利用予約がキャンセルされた場合に、新たな運行経路を決定することとしてもよい。
【００４５】
（ステップＳ１０２）
全呼びリスト作成部６１は、新たな運行経路を決定するタイミングと判定すると、運行情報記憶部５から受信した呼び情報に基づいて、これから新たな運行経路を決定する全呼びリストを作成する。図５に示すように、全呼びリストには、登録された各呼びの呼び情報が一覧されており、それぞれの呼び情報を識別する呼び番号、呼びが登録された時刻である呼び登録時刻、乗車場所情報及び降車場所情報が含まれる。移動体１の利用が予約されていた場合には、呼び登録時刻の代わりに利用者が移動体１の利用を予約している予約時刻を利用することができる。以下、呼び番号Xの呼び情報を呼び情報Xとして説明する。
【００４６】
図５において、全呼びリストには乗降場所情報が全て記入されているが、利用者が乗車呼び又は降車呼びの一方しか登録しなかった場合、乗車場所情報又は降車場所情報が空欄になることがある。例えば、移動体１が上下ボタン方式のエレベータの場合、上下ボタンが押された際には降車場所がわからない（呼び情報には降車階情報が含まれない）ため、当該呼びの降車場所情報が空欄になる。このような場合には、空欄となった乗降場所情報に、仮の乗降場所情報を追加して全呼びリストを作成することができる。
【００４７】
ここでいう仮の乗降場所情報とは、空欄となった乗降場所情報に追加することで全呼びリストを作成するために、仮に設定された乗降場所情報である。仮の乗降場所情報として、利用者が実際に乗車又は降車する可能性のある乗降場所情報が使用されるのが好ましい。全呼びリスト作成部６１は、運行情報記憶部５から受信した運行情報に基づいて仮の乗降場所情報を生成したり、予め複数の仮の乗降場所情報のパターンを運行記憶情報５に記憶させておき、その中から選択して使用したりすることができる。
【００４８】
（ステップＳ１０３）
呼び集合列挙部６２は、全呼びリスト作成部６１から受信した全呼びリストの部分集合である呼び集合を列挙する。呼び集合列挙部６２は、図５に示すような呼び情報が５個含まれる全呼びリストを受信した場合、図６に示すように３２個（＝２５個）の呼び集合を列挙することができる。図６において、各呼び集合の１の位から順に呼び情報１、呼び情報２と対応しており、各位の値が１の場合はその位に対応する呼び情報が含まれ、０の場合にはその位に対応する呼び情報が含まれない。したがって、例えば、図６において01001と表わされる呼び集合は、呼び情報１と呼び情報４だけを含む呼び集合である。以下、図６において、５桁の数値YYYYYで表される呼び集合を、呼び集合YYYYYという。
【００４９】
呼び集合列挙部６２は、図６に示すように、全呼びリストの部分集合の全てを呼び集合として列挙してもよいし、全呼びリストの部分集合の一部を呼び集合として列挙してもよい。例えば、呼び集合列挙部６２は、全呼びリストの部分集合のうち、そこ含まれる呼び情報の数が所定値以下の部分集合のみを呼び集合として列挙するよう構成されてもよい。この場合、上記の所定値は、（呼び情報の数／移動体の数）＋α（α＞０）として算出することができる。呼び情報が５個、移動体が３台、αが１／３の場合、上記の所定値は２となり、呼び集合列挙部６２は、呼び情報の数が２つ以下の部分集合のみを呼び集合として列挙する。すなわち、呼び集合00001や呼び集合00011は列挙されるが、呼び集合00111や呼び集合01111は列挙されない。これにより、呼び集合の列挙数を減らし、生成される運行経路数を減少させることができる。また、一部の移動体１が多くの呼びに対応する非効率な可能性の高い運行経路の生成を防ぎ、生成される運行経路における優良な運行経路の割合を増加させることができる。
【００５０】
また、呼び集合列挙部６２は、全呼びリストに含まれる呼び情報のうち、呼び情報が入力された呼び登録時刻が所定の範囲に含まれる乗降場所が同一の複数の呼び情報を、１つの呼び情報として扱い、呼び集合を列挙するように構成されてもよい。例えば、図７に示す全呼びリストにおいて、呼び情報２と呼び情報３とは、呼び登録時刻も乗降場所も同一である。このような全呼びリストを受信した場合、呼び集合列挙部６２は、呼び情報２と呼び情報３とをまとめて１つの呼び情報として扱い、呼び集合を列挙することができる。この場合、図８に示すように、１６個（＝２４個）の呼び集合が列挙される。これにより、呼び集合の列挙数を減少させることができる。
【００５１】
（ステップＳ１０４）
運行経路生成部６３は、各移動体１に対してステップＳ１０５〜ステップＳ１０７の処理を行う。ステップＳ１０４はループ処理であり、全ての移動体１に対してステップＳ１０５〜ステップＳ１０７の処理が行われるまで繰り返される。以下、ステップＳ１０４のループ処理中の移動体１を移動体ｉという。
【００５２】
（ステップＳ１０５）
運行経路生成部６３は、各呼び集合に対してステップＳ１０６及びステップＳ１０７の処理を行う。ステップＳ１０５はループ処理であり、全ての呼び集合に対してステップＳ１０６及びステップＳ１０７の処理が行われるまで繰り返される。以下、ステップＳ１０５のループ処理中の呼び集合を呼び集合ｋという。なお、ステップＳ１０４とステップＳ１０５は順番が逆であってもよい。
【００５３】
（ステップＳ１０６）
運行経路生成部６３は、呼び集合ｋに含まれる呼び情報に応じて移動体ｉが運行する運行経路を生成する。運行経路生成部６３による運行経路生成処理については後述する。
【００５４】
（ステップＳ１０７）
評価値算出部７は、ステップＳ１０６で作成された移動体ｉの呼び集合ｋに対する運行経路の評価値を算出する。図９は、評価値算出部７が算出する評価値の一例であり、評価値としてサービス時間の合計値が用いられている。以下、図９において、５桁の数値YYYYYで表される運行経路を、運行経路YYYYYという。運行経路YYYYYは、呼び集合YYYYYに含まれる呼び情報に応じて移動体１が運行する運行経路である。例えば、図９によれば、この移動体１の呼び集合00001に対する運行経路00001の評価値は41.13である。
【００５５】
評価値算出部７は、移動体ｉの呼び集合ｋに対する運行経路の評価値を算出すると、当該評価値と運行経路とを運行経路記憶部８１に送信し、評価値と運行経路とは運行経路記憶部８１に記憶される。このように、本実施形態において、一度算出された評価値は、運行経路とともに運行経路記憶部８１に記憶され、以下のステップにおいて改めて算出する必要がないため効率的である。
【００５６】
（ステップＳ１０８）
ステップＳ１０４のループ処理が終了すると、運行経路除外部８２は、運行経路記憶部８１に記憶された運行経路のそれぞれについて運行経路の候補から除外するか否か判定する。運行経路除外部８２による運行経路除外処理については後述する。運行経路除外部８２による除外処理が終了すると、運行経路記憶部８１に記憶された運行経路、すなわち、運行経路生成部６３により生成された運行経路のうち運行経路除外部８２により除外されずに残った運行経路（図１０参照）は、モデル生成部９１に送信される。
【００５７】
（ステップＳ１０９）
モデル生成部９１は、受信した運行経路に基づいて運行経路を決定するためのモデルを生成する。このモデルは、図１１に示すように、全呼び情報に応じるように各移動体１の運行経路を選択した場合に、運行経路の評価値の合計が最も良い各移動体１の運行経路を解とする集合被覆問題又は集合分割問題として定式化することができる。本実施形態において、評価値はサービス時間の合計値であるため、評価値がよい（優良な）運行経路とは評価値が小さい運行経路である。したがって、目的関数は評価値の合計の最小値（min）を求める式となる。これに対して、評価値がよい（優良な）運行経路が評価値の大きい運行経路である場合、目的関数は評価値の最大値（max）を求める式となる。
【００５８】
（ステップ１１０）
運行経路決定部９２は、モデル生成部９１から受信した集合被覆問題等を解き、解（近似解）を求め、得られた解により各移動体１の運行経路を決定する。ここで求められる解は、少なくとも１つの運行経路を含む運行経路の集合である。図１２は、集合被覆問題等を解いて得られる解の一例である。この解によれば、運行経路決定部９２は、移動体１ａが運行経路00110を運行し、移動体１ｂが運行経路01000を運行し、移動体１ｃが運行経路10001を運行するよう、各移動体１の運行経路を決定する。最適化問題等を解く際には、決定変数Ｚjrを、目的関数が良くなる方向に最適化すればよい。
【００５９】
このように決定された運行経路において、複数の移動体１が同一の呼び情報に対応している場合、運行経路決定部９２は、当該呼び情報に対応する移動体１を１つ選択し、その他の移動体１は当該呼び情報に対応しない運行経路に改めて決定する。例えば、運行経路決定部９２により、図１３に示す運行経路が決定された場合、呼び情報３には、移動体１ａと移動体１ｂとが対応している。このような場合には、運行経路決定部９２は、呼び情報３に対応する移動体１として、最も評価値のよい移動体１、すなわち移動体１ａを選択する。そして、運行経路決定部９２は、移動体１ｂに対して、呼び情報３に対応しない運行経路を改めて決定する。すなわち、移動体１ｂの現在決定されている運行経路01100から、呼び情報３を除外した運行経路である運行経路01000を移動体１ｂの運行経路として決定する。これにより、各移動体１の実行可能な運行経路を決定することができる。
【００６０】
次に、運行経路生成部６３が運行経路を生成する処理について図１４〜図１６を参照して説明する。ここで、図１４は、運行経路生成部６３が各移動体ｉの呼び集合ｋに対する運行経路生成処理の一例を示すフローチャートである。
【００６１】
（ステップＳ２０１）
運行経路生成部６３は、移動体ｉの呼び集合ｋに対する運行経路を生成するために、呼びリストＱを作成する。呼びリストＱとは、呼び集合ｋに含まれる呼び情報を、乗降場所情報に基づき所定の順番に並べたリストである。運行経路生成部６３は、呼び集合ｋに含まれる呼び情報を、移動体ｉが軌道上を進行方向に一巡する間に、各呼び情報の進行方向と逆行せずに対応できる順番に並べることにより、呼びリストＱを作成する。
【００６２】
以下、呼び集合ｋが図５の全呼びリストの呼び情報を全て含む呼び集合11111である場合について具体的に説明する。移動体１はエレベータであり、図５の乗車場所はエレベータの乗車階を示し、降車場所は降車階を示すものとする。図１５は、この呼び集合ｋに含まれる各呼び情報の乗車階、降車階、進行方向を説明する説明図である。移動体ｉは８階を上昇中であるものとする。
【００６３】
運行経路生成部６３は、まず、移動体ｉが８階から１４階まで上昇する間に呼び情報の進行方向と逆行せずに対応できる呼び情報を順番に呼びリストＱに追加する。これにより、呼び情報２及び呼び情報３が順番に呼びリストＱに追加される。次に、運行経路生成部６３は、移動体ｉが１４階から２階まで下降する間に呼び情報の進行方向と逆行せずに対応できる呼び情報を順番に呼びリストＱに追加する。これにより、呼び情報４が呼びリストＱに追加される。さらに、運行経路生成部６３は、移動体ｉが２階から８階まで上昇する間に呼び情報の進行方向と逆行せずに対応できる呼び情報を呼びリストＱに追加する。これにより、呼び情報５及び呼び情報１が、順番に呼びリストＱに追加される。以上により、移動体ｉは軌道上を進行方向に一巡する。図１６は、このようにして作成された呼びリストＱを示す。呼びリストＱには、上述の通り、呼び情報が呼び情報２，３，４，５，１の順番で並べられている。
【００６４】
同様に、運行経路生成部６３は、移動体ｉが８階で下降中の場合には、呼び情報が呼び番号４，５，１，２，３の順番で並べられた呼びリストＱを作成する。また、運行経路生成部６３は、移動体ｉが停車中の場合には、移動体ｉの進行方向が上昇方向の場合と下降方向の場合の２通りの呼びリストＱを作成することができ、運行経路生成部６３は両方の呼びリストＱを作成してもよいし、いずれか一方を作成してもよい。
【００６５】
（ステップＳ２０２）
次に、運行経路生成部６３は、移動体ｉの運行経路を示す呼びリストＰを作成する。呼びリストＰは上述の呼びリストＱの呼び情報を所定の順番に並び替えたものである。運行経路生成部６３は、呼びリストＰを作成するために、まず、呼びリストＱのうち呼び登録時刻が最も早い呼び情報ｐを選択し、呼びリストＰの先頭に追加する。図１６の呼びリストＱの場合、呼び情報５が呼び情報ｐとして選択され、呼びリストＰの先頭に追加される。
【００６６】
（ステップＳ２０３）
運行経路生成部６３は、呼びリストＱにおける呼び情報ｐの位置（呼びリストＱの４番目）を検索し、その次の位置（呼びリストＱの５番目）を記憶し、呼びリストＱから呼び情報ｐ（呼び情報５）を削除する。これにより、呼びリストＱの４番目は空欄となる。
【００６７】
（ステップＳ２０４）
運行経路生成部６３は、ステップＳ２０３で記憶した次の位置（呼びリストＱの５番目）の呼び情報ｑ（呼び情報１）を選択し、呼び情報ｑに対してステップＳ２０５〜ステップＳ２０７の処理を行う。ステップＳ２０４はループ処理であり、呼びリストＱに含まれる全ての呼び情報に対して処理が行われるまで繰り返される。呼び情報ｑ（呼び情報１）に対してステップＳ２０５〜ステップＳ２０７の処理が行われると、呼び情報ｑ（呼び情報１）の次に並んだ呼び情報（呼び情報２）が、次の呼び情報ｑとして選択される。呼び情報ｑが呼びリストＱの最後尾まで選択された場合には、次の呼び情報ｑは呼びリストＱの先頭から選択される。
【００６８】
（ステップＳ２０５）
運行経路生成部６３は、移動体ｉが現在位置（８階）から呼び情報ｐ（呼び情報５）に対応する過程で、呼び情報ｑ（呼び情報１）に対応できるか否か判定する。この判定は、運行ルール記憶部６４に記憶された運行ルールに従って行われる。運行経路生成部６３は、呼び情報ｑに対応できると判定した場合（yes）、ステップＳ２０６へ進み、対応できないと判定した場合（no）、ステップＳ２０２へ戻り、次の呼び情報ｐを選択し、呼びリストＰに追加する。
【００６９】
（ステップＳ２０６）
運行経路生成部６３は、呼び情報ｑを呼びリストＰに追加する。
【００７０】
（ステップＳ２０７）
運行経路生成部６３は、呼び情報ｑを呼びリストＱから削除する。
【００７１】
（ステップＳ２０８）
呼びリストＱに含まれる全ての呼び情報（最初に選択される呼び情報ｐは除く）に対してステップＳ２０４のループ処理が行われると、運行経路生成部６３は、呼びリストＱが空か否か判定する。呼びリストＱが空とは、呼びリストＱに記憶された全ての呼び情報が削除された状態をいう。運行経路生成部６３は、呼びリストＱが空と判定した場合（yes）、移動体ｉの呼び集合ｋに対する運行経路生成処理を終了し、生成された運行経路を評価値算出部７へ送信する。運行経路生成部６３は、呼びリストＱが空ではないと判定した場合（no）、ステップＳ２０２へ戻り、次の呼び情報ｐを選択し、呼びリストＰに追加する。
【００７２】
なお、運行経路生成部６３が生成する移動体ｉの呼び集合ｋに対する運行経路の数は、移動体ｉの運行状態や、運行経路生成方法（アルゴリズム）、運行ルールに応じて変化する。例えば、運行経路生成部６３は、移動体ｉが停車中の場合、すなわち、移動体ｉが複数の方向に進行可能な場合や、運行経路生成方法（アルゴリズム）が複数ある場合には、複数の運行経路を生成してもよいし、運行ルールに従った運行経路を生成できない場合には、当該移動体ｉの呼び集合ｋに対する運行経路を生成しなくてもよい。
【００７３】
さらに、運行経路除外部８２が運行経路を除外する処理について図１７，図１８を参照して説明する。ここで、図１７は、運行経路除外部８２が運行経路記憶部８１に記憶された運行経路を除外する運行経路除外処理の一例を示すフローチャートである。
【００７４】
（ステップＳ３０１）
運行経路除外部８２は、運行経路記憶部８１に記憶された複数の運行経路の中から、同一の移動体１に対して生成された、異なる呼び集合に対する運行経路を２つ選択する。ここで選択された運行経路を、以下では運行経路ｒ及び運行経路ｔという。運行経路ｒ，ｔは、一方の運行経路の呼び集合が、他方の運行経路の呼び集合の部分集合とならないように選択される。運行経路ｒ，ｔの選択方法は、運行経路ｒ，ｔの同一の組み合わせが複数回選択されない選択方法が好ましい。このステップＳ３０１はループ処理であり、運行経路ｒ，ｔの可能な全ての組み合わせに対してステップＳ３０２〜ステップＳ３０４の処理が行われるまで繰り返される。
【００７５】
（ステップＳ３０２）
運行経路除外部８２は、選択された２つの運行経路ｒ及び運行経路ｔを運行経路の候補から除外するか否か判定する。この判定は、運行経路ｒの評価値と運行経路ｔの評価値の合計値と、運行経路ｓの評価値とを比較することにより行われる。運行経路ｓとは、運行経路ｒの呼び集合と運行経路ｔの呼び集合と和集合に対して生成された同一の移動体１の運行経路をいう。図１８に示すように、運行経路ｒの呼び集合が呼び集合00001であり、運行経路ｔの呼び集合が呼び集合00110である場合、運行経路ｓは呼び集合00001と呼び集合00110の和集合である呼び集合00111に対して生成された運行経路00111である。運行経路除外部８２は、運行経路ｒと運行経路ｔとの評価値の合計値（41.13+106.85=147.98）と、運行経路ｓの評価値（172.79）とを比較し、運行経路ｓの評価値の方が悪い場合にはステップＳ３０１に戻って他の運行経路ｒ，ｔを選択し、運行経路ｓの評価値の方が良い場合にはステップＳ３０３へ進む。
【００７６】
（ステップＳ３０３）
運行経路除外部８２は、運行経路ｒ及び運行経路ｔを運行経路記憶部８１から削除する。すなわち、運行経路除外部８２は、評価値の悪い運行経路を運行経路の候補から除外し、評価値の良い運行経路を運行経路の候補として特定する。これにより、運行経路記憶部８１に記憶される運行経路の数が減少するとともに、運行経路記憶部８１には評価値の良い優良な運行経路が記憶されることとなる。
【００７７】
（ステップＳ３０４）
運行経路除外部８２は、運行経路ｒの呼び集合00001の補集合である呼び集合11110に対して生成された運行経路11110と、運行経路ｔの呼び集合00110の補集合である呼び集合11001に対して生成された運行経路11001とを運行経路記憶部８１から削除する。これにより、運行経路除外部８２は、運行経路ｒ，ｔと同様に評価値の悪い運行経路を運行経路の候補から除外する。
【００７８】
なお、運行経路除外部８２による運行経路除外処理は、運行経路ｒ，ｔの全ての組み合わせについて実施してもよいし、所定回数あるいは所定の組み合わせに対して実施されてもよい。また、運行経路除外部８２は、運行経路を３つ以上選択し、ステップＳ３０２〜ステップＳ３０４の処理を実施することもできる。さらに、運行経路除外処理は、呼び集合６２による呼び集合の列挙、運行経路生成部６３による運行経路の生成、及び評価値算出部７による評価値の算出などの処理と並列して実施することもできる。
【００７９】
以上説明したとおり、本発明の実施形態に係る運行経路決定装置は、各乗降場所間の経路が移動体ごとに定められた複数の乗降場所を有する軌道上を運行する複数の移動体１に対して、移動体１の利用を要求するための呼び情報（利用要求情報）に応じて各移動体１の運行経路を決定する。この運行経路決定装置は、全呼びリストの部分集合（呼び集合）を列挙する呼び集合列挙部６２（列挙手段）と、呼び集合に含まれる呼び情報に応じた各移動体１の運行経路を生成する運行経路生成部６３（生成手段）と、運行経路生成手段６が生成した運行経路のそれぞれに対して、移動体１の運行情報に基づいて評価値を算出する評価値算出部７（算出手段）と、運行経路生成部６３が生成した運行経路の中から評価値に基づいて運行経路の候補を特定する運行経路特定手段８（特定手段）と、運行経路特定手段９が特定した運行経路の候補の中から各移動体１の運行経路を決定する運行経路決定手段９（決定手段）と、を備える。
【００８０】
このような構成により、本実施形態に係る運行経路決定装置は、運行経路決定手段９が優良な運行経路を得るために探索する運行経路の数が減少する。したがって、効率的に優良な運行経路を得ることができる。また、移動体が優良な運行経路を運行することにより、利用者へのサービスの向上や、移動体によるエネルギー消費の削減が可能となる。
【００８１】
さらに、運行経路除外部８２が運行経路を除外する処理の他の例について図１９を参照して説明する。ここで、図１９は、運行経路除外部８２が運行経路記憶部８１に記憶された運行経路を除外する運行経路除外処理の他の例を示すフローチャートである。
【００８２】
（ステップＳ４０１）
運行経路除外部８２は、運行経路記憶部８１に記憶された複数の運行経路の中から、任意の運行経路ｒを１つ選択する。
【００８３】
（ステップＳ４０２）
運行経路除外部８２は、選択された運行経路ｒを運行経路の候補から除外するか否か判定する。運行経路除外部８２は、運行経路ｒを除外すると判定した場合には、ステップＳ４０３へ進み、除外しないと判定した場合には、ステップＳ４０１へ戻り、他の運行経路ｒを選択する。
【００８４】
運行経路除外部８２は、移動体１が運行する過程で同時に対応する呼び情報数の最大値が所定値以上になる運行経路ｒを運行経路の候補から除外するように判定してもよい。移動体１が同時に対応する呼び情報数は、移動体に１に同時に乗車する利用者の人数を示す。これにより、運行経路除外部８２は、移動体１の乗車人数を制限し、移動体１に積載人数制限がある場合には、制限を超過する運行経路を除外することができる。
【００８５】
また、運行経路除外部８２は、移動体１が運行する過程で乗降場所に停車する回数が所定の範囲を超える運行経路ｒを運行経路の候補から除外するように判定してもよい。一部の移動体１が他の移動体１に比べて極端に停車回数が多い又は少ない運行経路は、移動体１の仕事量が不均一なため、優良な運行経路ではない可能性が高い。そこで、このような運行経路を除外することにより、運行経路の数を減少させつつ、優良な可能性の高い運行経路を運行経路の候補として残すことができる。なお、運行経路除外部８２は、選択された運行経路ｒを除外すると、運行経路ｒが対応する呼び情報のうち少なくとも１つに対応する運行経路が、運行経路記憶部８１から全て削除されてしまう場合には、運行経路ｒを除外しないように判定する。例えば、選択された運行経路ｒが運行経路00001であり、運行経路記憶部８１に記憶された他の運行経路が全て運行経路YYYY0で表される場合、運行経路ｒを除外すると、呼び情報１に対応する運行経路が運行経路記憶部８１から全て削除され、運行経路の候補の中に１つも存在しなくなる。このような場合には、運行経路除外部８２は運行経路ｒを除外しないように判定する。これにより、上述のステップ１１０において、運行経路が決定できなくなる（集合被覆問題等が解なしとなる）ことを防ぐことができる。
【００８６】
また、運行経路除外部８２は、移動体１が運行するのに要する時間が所定の範囲を超える運行経路を運行経路の候補から除外するように判定してもよい。一部の移動体１が他の移動体１に比べて極端に運行に要する時間が長い又は短い運行経路は、移動体１の仕事量が不均一なため、優良な運行経路ではない可能性が高い。そこで、このような運行経路を除外することにより、運行経路の数を減少させつつ、優良な可能性の高い運行経路を候補として残すことができる。なお、運行経路除外部８２は、選択された運行経路ｒを除外すると、運行経路ｒが対応する呼び情報のうち少なくとも１つに対応する運行経路が、運行経路記憶部８１から全て削除されてしまう場合には、運行経路ｒを除外しないように判定する。
【００８７】
また、運行経路除外部８２は、同一の呼び集合に対する同一の移動体の運行経路が複数生成された場合、複数生成された運行経路のうち少なくとも一部の運行経路を運行経路の候補から除外するように判定してもよい。上述の通り、運行経路を生成する際に移動体１が停車中の場合や、運行経路生成方法（アルゴリズム）が複数ある場合には、運行経路生成部６３により、同一の移動体１の同一の呼び集合に対する運行経路が複数生成されることがある。このような場合には、複数の運行経路の中で最も評価値が良い運行経路を残し、他の運行経路を除外するよう判定することにより、運行経路の数を減少させつつ、優良な運行経路を候補として残すことができる。なお、運行経路除外部８２は、選択された運行経路ｒを除外すると、運行経路ｒが対応する呼び情報のうち少なくとも１つに対応する運行経路が、運行経路記憶部８１から全て削除されてしまう場合には、運行経路ｒを除外しないように判定する。
【００８８】
（ステップＳ４０３）
運行経路除外部８２は、運行経路ｒを運行経路記憶部８１から削除する。すなわち、運行経路除外部８２は、評価値の悪い運行経路を運行経路の候補から除外し、評価値の良い運行経路を候補として残す。これにより、運行経路記憶部８１に記憶される運行経路の数が減少するとともに、運行経路記憶部８１には評価値の良い優良な運行経路が記憶されることとなる。
【００８９】
（ステップＳ４０４）
運行経路除外部８２は、運行経路ｒの呼び集合の補集合となる呼び集合に対して生成された運行経路を運行経路記憶部８１から削除する。
【００９０】
尚、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また上記各実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の発明を形成できる。また例えば、各実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。さらに、異なる実施形態に記載した構成要素を適宜組み合わせてもよい。
【符号の説明】
【００９１】
１：移動体
２：呼び登録部
２１：表示部
３：呼び情報収集部
４：移動体情報収集部
５：運行情報記憶部
６：運行経路生成手段
６１：全呼びリスト作成部
６２：呼び集合列挙部
６３：運行経路生成部
６４：運行ルール記憶部
７：評価値算出部
８：除外運行経路特定手段運行経路特定手段
８１：運行経路記憶部
８２：運行経路除外部
９：運行経路決定手段
９１：モデル生成部
９２：運行経路決定部
【図１】
2015040780.tif 000003
【図２】
2015040780.tif 000004
【図３】
2015040780.tif 000005
【図４】
2015040780.tif 000006
【図５】
2015040780.tif 000007
【図６】
2015040780.tif 000008
【図７】
2015040780.tif 000009
【図８】
2015040780.tif 000010
【図９】
2015040780.tif 000011
【図１０】
2015040780.tif 000012
【図１１】
2015040780.tif 000013
【図１２】
2015040780.tif 000014
【図１３】
2015040780.tif 000015
【図１４】
2015040780.tif 000016
【図１５】
2015040780.tif 000017
【図１６】
2015040780.tif 000018
【図１７】
2015040780.tif 000019
【図１８】
2015040780.tif 000020
【図１９】
2015040780.tif 000021