最適経路探索システム並びにこれを用いた運行計画作成システム及び運行管理支援システム
【課題】 運転整理の局面でも乗客の移動経路推定を短時間で行うことができる最適経路探索システムを得る。
【解決手段】 探索条件入力装置３により、乗客の出発駅と目的駅と出発駅における出発時刻とを入力し、グラフ構造作成装置２により、乗客の出発駅から目的駅に至る各途中駅での到着時刻及び出発時刻をノードとし、乗客の各途中駅間の移動をノード間のリンクとして表現し、このリンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置１に記憶された運行計画に基き作成し、この作成されたグラフ構造を利用して、探索装置４により乗客の出発駅から目的駅への最適経路を探索し、探索結果を探索結果出力装置７に出力する。
【解決手段】 探索条件入力装置３により、乗客の出発駅と目的駅と出発駅における出発時刻とを入力し、グラフ構造作成装置２により、乗客の出発駅から目的駅に至る各途中駅での到着時刻及び出発時刻をノードとし、乗客の各途中駅間の移動をノード間のリンクとして表現し、このリンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置１に記憶された運行計画に基き作成し、この作成されたグラフ構造を利用して、探索装置４により乗客の出発駅から目的駅への最適経路を探索し、探索結果を探索結果出力装置７に出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、鉄道に代表される、予め定められた運行計画に従って運行される交通機関において、乗客（積載物）の移動経路を求める最適経路探索システム並びにこれを用いた運行計画システム及び運行管理システムに関するものである。
【背景技術】
【０００２】
鉄道に代表される、予め定められた運行計画に従って運行される交通機関においては、利用客にとってよりよい運行計画を策定するために、運行計画を乗客の立場から評価するということが考えられている。乗客の立場から見た運行計画に対する評価指標としては、各乗客の旅行所要時間や乗換の回数、移動途中の混雑状況などが挙げられる。
こうした評価値を計算するためには、各乗客がシステム内をどのように移動し、どこで乗り換えるかの情報が必要である。ところで、乗客行動を実際に測定して、こうした情報を得るということは、様々な装置を各所に配置して測定分析を行わなければならず、困難である上に、実際に実行された運行計画に対してのみしか用いることができない。運行計画や運行管理に役立てるために、計画案に対して、こうした評価値を計算するためには、乗客のシステム内での行動を何らかの方法で推定して求める必要がある。
これに対して、自動改札機やＩＣカード式乗車券などから得ることのできる情報（例えば、出発駅に入った時刻と目的駅を出た時刻）のこれまでの統計と、その交通機関の運行計画の情報から推定する方法が考えられる。
従来の技術としては、ロジットモデルを利用した方法（例えば特許文献１）と、グラフ構造でモデルを表現してダイクストラ法を適用した方法（例えば非特許文献１）があった。
特許文献１には、乗車券としてのＩＣカードにより旅客流動を把握し、ロジットモデルに基いた旅客行動モデルを構築し、このモデルにより、列車ダイヤに乱れが生じたときの各列車の乗客数を推定するものが記載されている。
非特許文献１には、各列車の到着と出発イベントをノードで表し、列車運行・停車・乗換などで乗客が移動する可能性のあるノード同士を重み付き有向リンクで接続したグラフにより乗客行動を表現し、乗客の出発駅の任意の出発ノードを起点として、最も経路長が短くなる目的駅の到着ノードを終点とする経路を選択するダイクストラ法最短経路探索を行うものが記載されている。
【０００３】
【特許文献１】特開２００１−５５１４５号公報（第３〜６頁、図１）
【非特許文献１】平成１５年電気学会全国大会講演論文集、２００３、ｐｐ３４３−３４４、「都市近郊鉄道における運転整理時の乗客行動経路再決定の高速化手法」
【発明の開示】
【発明が解決しようとする課題】
【０００４】
予め定められた運行計画に従って運行される交通機関においては、計画立案に関して、事前に運行計画を立案するという段階と、事故や災害などの影響を受けて運行が乱れた際に、適切な処置を行って元の運行計画に復帰させる（これを運転整理と呼ぶ）という段階の２つが存在している。
このうち前者については、十分に時間を掛けて計画を練ることができるが、後者については、実際に進行する事態に合わせて、その場その場で短時間に新しい計画を立案しなければならないという強い制約が存在する。こうした場面でも乗客の行動を推定して、その情報を利用して計画立案に生かしていくためには、乗客の移動経路の推定を極めて短時間に終わらせなければならない。
特許文献１のロジットモデルを利用した方法では、推定精度は高いものの、推定に相当程度の時間が掛かり、運転整理の局面に利用することは困難である。
また、非特許文献１のダイクストラ法を利用した方法についても、実用規模の問題に対して、乗客の移動経路推定に掛かる時間が長く、運転整理の局面に利用することは困難であった。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、運転整理の局面でも乗客の移動経路推定を短時間で行うことができる最適経路探索システム及びこれを用いて、より利用客にとって利便性の高い運行計画を立案及び運行管理を支援できる運行計画作成システム及び運行管理支援システムを得ることを目的としている。
【課題を解決するための手段】
【０００６】
この発明に係わる最適経路探索システムにおいては、時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの移動体の積載物の移動経路を探索する最適経路探索システムにおいて、積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、運行計画を記憶する運行計画記憶装置、移動体の出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、ノード間の経過をリンクとして表現し、リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成されたグラフ構造を利用して、積載物の出発点から到着点への最適経路を探索する探索装置、及び探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
探索装置は、探索条件入力装置により入力された積載物の到着点から出発点に向う逆方向に、各経由点のノードから到着点までの最短経路のリンクの重みを合計し、各ノードに評価値として割当てた後、積載物の出発点及び出発点での出発時刻に基き、出発点から到着点までの順方向に、各ノードに割当てられた評価値及びリンクの重み付けの値により各経由点を選択することにより、積載物の出発点から到着点までの最適経路を探索するものである。
【発明の効果】
【０００７】
この発明は、以上説明したように、時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの移動体の積載物の移動経路を探索する最適経路探索システムにおいて、積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、運行計画を記憶する運行計画記憶装置、移動体の出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、ノード間の経過をリンクとして表現し、リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成されたグラフ構造を利用して、積載物の出発点から到着点への最適経路を探索する探索装置、及び探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
探索装置は、探索条件入力装置により入力された積載物の到着点から出発点に向う逆方向に、各経由点のノードから到着点までの最短経路のリンクの重みを合計し、各ノードに評価値として割当てた後、積載物の出発点及び出発点での出発時刻に基き、出発点から到着点までの順方向に、各ノードに割当てられた評価値及びリンクの重み付けの値により各経由点を選択することにより、積載物の出発点から到着点までの最適経路を探索するので、乗客の行動経路を探索するときに、各探索箇所から目的地または出発地までの最良の評価値が予め逆方向の予備的な探索によって計算して与えてあることによって、それに基づいて効率よく順方向の探索の枝刈りをすることができ、それによって従来のダイクストラ法に基づく探索と同じ結果を、ダイクストラ法に基づく探索に比べて著しく短い探索時間で得ることができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
図１は、この発明の実施の形態１による最適経路探索システムを示す全体構成図である。
図１において、運行計画記憶装置１は、予め対象とする鉄道の計画ダイヤを格納している。グラフ構造作成装置２は、乗客流動を表現したグラフ構造を作成する。探索条件入力装置３は、乗客の出発駅、目的駅、出発駅での出発時刻を、乗客の移動経路探索の条件として入力する。探索装置４は、運行計画入力装置１からの情報を基に探索を実行して、その結果を探索結果記憶装置６に出力する。グラフ構造記憶装置５は、グラフ構造作成装置２によって作成された、乗客流動を表現したグラフ構造を格納する。探索結果表示装置７は、探索装置４による探索結果を表示する。
【０００９】
図２は、この発明の実施の形態１による最適経路探索システムの乗客流動をグラフ構造で示す概念図である。
図２において、列車の各駅への到着と出発をそれぞれグラフ理論におけるノードとして表現し、列車の駅への停車、駅間の走行をそれらのノード間を結ぶ有向リンクとして表現する。各リンクには重みと呼ばれる数値を持たせる。図２では、リンクの脇に重みの値を付記してある。重みは、そのリンクの利用しやすさを表現した値であり、小さいほど利用しやすいことを示す。
なお、図２では、白い丸が、出発ノードであり、ハッチングされた丸が、到着ノードである。各ノード間の経過がリンクであり、実線が停車リンク、点線が走行リンク、一点鎖線が乗換リンクを示している。駅Ａが出発駅（出発点）、駅Ｂと駅Ｃが途中駅（経由点）、駅Ｄが目的駅（到着点）である。
【００１０】
図３は、この発明の実施の形態１による最適経路探索システムの乗客流動の簡略化したグラフ構造を示す図である。
図３において、ノード１〜ノード３と、各ノードを結ぶリンクの重みが示されている。
図４は、図３に対応するデータ構造を示す図である。
図４において、図３のグラフ構造に対応する汎用コンピュータメモリ上のデータ構造が示されている。各ノードに対して一意に識別できるノードＩＤを割り当てている。
【００１１】
図５は、この発明の実施の形態１による最適経路探索システムの予め計算した各ノードの最短経路評価値を示す図である。
図５において、各ノートには、目的駅側からの逆方向の探索によって、目的駅ノードへの最短経路評価値を割付けている。
図６は、この発明の実施の形態１による最適経路探索システムの探索装置によって実行される目的駅側からの逆方向の探索を示すフローチャートである。
図７は、この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索での再帰処理を示すフローチャートである。
【００１２】
図８は、この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索を行うときの途中経過を示す図である。
図８において、駅Ａから駅Ｄまで４つの駅がある路線で、実線により表された急行と、点線により表された各停が交互に運転している場合を示している。
図９は、この発明の実施の形態１による最適経路探索システムの追い抜き関係にある場合の評価値の更新を示す図である。
図９において、出発ノードから到着ノードまでのリンクの重みが、９の列車と３の列車が存在している。後からリンク重み３の列車が出発して先行の列車を追い抜く様子を示している。
図１０は、この発明の実施の形態１による最適経路探索システムの逆方向探索終了後のノードの状態を示す図である。
図１０において、逆方向の探索終了後の各ノードは、最短距離にある目的駅到着ノードによって、Ａ、Ｂ、Ｃ、Ｄ、Ｅのように分類されている。
【００１３】
図１１は、この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索を示すフローチャートである。
図１２は、この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索での再帰処理を示すフローチャートである。
図１３は、この発明の実施の形態１による最適経路探索システムのスタック構造を示す図である。
図１３には、順方向の経路探索されたノードが探索された順序でスタックに格納されている。
【００１４】
次に、動作について説明する。
実施の形態１の最適経路探索システムでは、まず、乗客の移動経路の探索条件として、探索条件入力装置３から乗客の出発駅、目的駅、出発時刻を入力する。また、予め対象とする鉄道の計画ダイヤを格納した運行計画記憶装置１からの情報を基にして、グラフ構造作成装置２が乗客流動を表現した、図２のようなグラフ構造を作成し、グラフ構造記憶装置５に格納する。
探索装置４が、運行計画入力装置１からの探索条件の情報を基に、探索を実行して、その結果を探索結果記憶装置６に出力し、それを探索結果表示装置７が表示する。探索結果表示装置７により表示される結果は、探索条件入力装置３に入力された探索条件の下で、最適な利用列車、乗換駅などの情報を含む経路情報である。
【００１５】
次いで、さらに詳しく説明する。
グラフ構造作成装置２が作成するグラフ構造は、非特許文献１に記載された手法による。具体的には、図２に示すように、列車の各駅への到着と出発をそれぞれグラフ理論におけるノードとして表現し、列車の駅への停車、駅間の走行をそれらのノード間を結ぶ有向リンクとして表現する。各リンクには重みと呼ばれる数値を持たせ、図２では、リンクの脇に重みの値を付記してある。この重みは、そのリンクの利用しやすさを表現した値であり、小さいほど利用しやすいことを示す。乗客は所要時間が長いことや乗換があることなどを嫌がるので、そうした乗客が嫌がる事象に対しては、大きな値を与え、そうでないことに対しては、小さな値を与えることで、乗客の経路選択を表現する。
なお、図２の例では、重みは、そのリンクが表している停車や走行の所要時間を表しているが、それ以外の値を与えてもよい。さらに、乗換が可能な駅では、乗換元の列車のその駅への到着ノードから乗換先の列車のその駅での出発ノードへ、乗換を表現する有向リンクを張る。図２の例では、乗換リンクの重みは、その乗換の所要時間である。
【００１６】
グラフ構造は、グラフ構造記憶装置５に記憶されるが、このグラフ構造は、汎用コンピュータのメモリ上のデータ構造として実現してもよい。図３のような簡単なグラフ構造をメモリ上のデータ構造として表現した例を図４に示す。
図４では、各ノードに対して、一意に識別できるノードＩＤを割り当てる。さらに、そのイベントが発生した時刻（到着ノードならば到着時刻、出発ノードならば出発時刻）を後のために記録しておき、また、後で経路探索に必要となる評価値を格納する領域を用意する。
リンクの情報は、１つのノードに関係するリンクの数が可変であるので、別に配列を用意する。グラフは、有向グラフであるので、リンクの向きを区別できるような構造にするが、後で述べるように逆方向からの探索を行う必要があるので、リンクの到着側のノードからも、そのリンクを容易に参照できるようにしておく。
【００１７】
乗客は、ある時刻に出発駅にやってきて、目的駅までの列車を選択して乗車したり、乗り換えたりして目的駅まで移動する。この乗客の行動モデルを考えると、多くの乗客は、所要時間が短いとか乗換が少ないなどの条件で、乗車する列車を選択していると考えられる。
これは、グラフ構造の上では、リンクの重みが少ない経路を選択するということであり、図２のグラフ構造で考えると、乗客は、出発駅のある１つの出発ノードから目的駅へ向かってリンクに沿って移動していくが、移動経路上のリンクの重みの合計が、最も少なくなるような経路を選択することになる。
【００１８】
本発明は、探索装置４によって、まず目的駅の側から出発駅に向かって逆方向に予備的な探索を行って、予め各ノードに経路選択に必要な情報（評価値）を割り当てておき、その情報を元に出発駅の側からの探索を行って、移動経路を確定させる。
目的とする駅が１つに定まれば、各ノードから目的駅への最短経路は、例え、複数の経路が同一の評価値で共に最短であったとしても、必ずある１つの評価値を持っていることになる。
【００１９】
図５に示すように、予め各ノードから目的駅へのこのただ１つの最短経路評価値を求めておくと、出発駅側から探索を実行したときに、現に探索を実行しているリンクが最短経路となるかならないか、両端のノードの最短経路評価値の差とそのリンクの重みの比較から容易に判断できるため、的確に探索の枝刈りを実行して探索時間を縮減することができる。
例えば、図５に示されるように、左側の経路では、出発駅ノードと途中駅ノードとの間のリンクの重みは５であり、出発駅ノードが評価値１０、途中駅ノードが評価値５であるから、両評価値の差とリンクの重みが等しくなり、このリンクが最短経路上のリンクであることがわかる。一方、右側の経路では、出発駅ノードと途中駅ノードとの間のリンクの重みは８であり、出発駅ノードが評価値１０、途中駅ノードが評価値５であるから、両評価値の差とリンクの重みが等しくなく、このリンクは最短経路上のリンクではないことがわかる。
つまり、最初に目的駅側からの逆方向の予備的な探索によって、各ノードに目的駅への最短経路の評価値を割り当てておき、それを元に出発駅側からの探索を行えばよいのである。
【００２０】
各ノードに予め与えておく目的駅までの最短経路評価値を求めるための、探索装置４によって実行される目的駅側からの逆方向の探索のフローチャートを図６に、その一部である再帰処理の部分のフローチャートを図７に示す。
次に、図６に基き、探索装置４によって実行される目的駅側からの逆方向の探索について、説明する。
例として、図８のように駅Ａから駅Ｄまで４つの駅がある路線で、急行と各停が交互に運転している場合を考える。
図６において、処理開始（ステップＳ１）後、最初に全てのノードに初期の評価値として十分大きな値を設定しておく（ステップＳ２）。このノードの評価値は、そのノードから目的とする駅までの現在の最短経路の評価値（所要時間の合計）を記憶しておくためのものである。駅Ｄに到着する経路を探索する場合には、まず図６のフローチャートのステップＳ３、Ｓ４に従い、駅Ｄに最初に到着する列車の到着ノードを選択して（ステップＳ３）評価値を０にセット（ステップＳ４）し、ステップＳ５の再帰処理を開始する。
【００２１】
次いで、図７の再帰処理について説明する。
図７の再帰処理が開始される（ステップＳ１０１）と、まず現在選択されている到着ノードからリンクを逆にたどって、１つ前の駅の出発ノードを選択する（ステップＳ１０２）。そしてこのノードの評価値を改善可能であるかどうか調べる（ステップＳ１０３）。評価値を改善可能であるというのは、現在そのノードに設定されている評価値よりよい（小さな）評価値を設定可能であるということである。最初に全てのノードに十分大きな値を初期の評価値として設定してあるので、初めてそのノードを探索した時には、必ず評価値を改善可能であり、２回目以降に探索した時には、ノードの記憶領域に保存してある前回までの探索の中で最良の評価値と今回の評価値を比較してよい方を採用して、ノードに記憶されている評価値を更新する（ステップＳ１０５）。今回の評価値は、１つ前の到着ノードの評価値に、その間のリンクの重みを合計して求める。１つ前の到着ノードの評価値は、目的駅への最短経路の長さ（リンク重みの合計）を表しているので、更新される評価値は、この出発ノードから目的駅への現在の最短経路の長さを表すことになる。ここで評価値を更新できなければ、再帰を脱出する（ステップＳ１０４）。
【００２２】
評価値が更新できた場合は、この出発ノードより先にこの駅を出発する他の列車の各出発ノードを時間的に後のものから順に評価値を更新していくループを実行する（ステップＳ１０６〜Ｓ１０８）。このループは、そのノードから出発するより後の列車の出発ノードから出発した方が、目的駅に早く到着するようなノードを探索するために実行される。
これは、図９に示すように途中で追い抜きが行われるような場合に、正しく探索が行えるようにするためのものである。図９の例のように、出発ノードから到着ノードまでのリンクの重みが、９の列車と３の列車が存在していて、後からリンク重み３の列車が出発して先行の列車を追い抜くとき、先行のリンク重み９の列車に乗車するよりも、この列車を見送って、後のリンク重み３の列車に乗った方が経路全体の評価値が良い、という場合がある。
このため、同一駅の出発ノード間での評価値の更新をステップＳ１０６〜Ｓ１０８で行う。評価値は、ステップＳ１０５で、更新した評価値に、出発ノードの時間差を加えて求める。出発ノードを１つずつ前にたどりながら更新を行い、評価値の改善ができなくなった時点でこのループを脱出する。
【００２３】
出発ノード間の評価値更新が完了した後、ステップＳ１０５で、評価値を更新した出発ノード（今まさに注目している列車の注目している駅の出発ノード）から、停車リンクを逆にたどって、その駅の到着ノードを選択し（ステップＳ１０９）、到着ノードの評価値の更新が可能であるならば（ステップＳ１１０）、更新して（ステップＳ１１１）、ステップＳ１０１から再帰的に処理を行う（ステップＳ１１２）。
ステップＳ１１２の再帰から復帰した後と、ステップＳ１１０で更新ができなかった時の次の処理として、乗換の探索を行う。乗換が行えるのは、乗換先の列車が出発する時刻より前にその駅に到着する列車であるのは当然なので、乗換先列車出発時刻から時間的に前にその駅の到着ノードを順番に探索を行う（ステップＳ１１３〜ステップＳ１１６）。
評価値の更新が行えた（乗換元到着ノードの評価値が乗換先出発ノードの評価値に乗換リンクの重みを合計したより大きい）場合は、その乗換元到着ノードから前にたどってステップＳ１０１から再帰的に探索を行う。評価値の更新が行えなかった場合、それ以上前の時間に到着する列車を探索しても評価値改善の見込みがないので、そこで乗換探索を打ち切って、図７で示したフローチャート全体の再帰探索を脱出する（ステップＳ１１７）。
【００２４】
図７の再帰処理を脱出すると、図６のステップＳ６に戻ってくる。再帰処理を始めるときに選択していた到着ノードの次に目的駅に到着するノードを選択して（ステップＳ７）、ステップＳ４で、選択ノードの評価値を０にセットした後、再びステップＳ５の再帰処理を開始する。目的駅の到着ノード全てに対して再帰処理が完了すると、目的駅側からの逆方向探索が完了する（ステップＳ８）。
逆方向探索が完了した時点で、各ノードには目的駅の到着ノードの中で最短距離にあるノードまでの距離（最短経路の評価値）が与えられている。図５の方式で、最短経路上にあるノード・リンクは識別できるので、この時点で図１０のように、最短距離にある目的駅到着ノードによって、全てのノードがＡ、Ｂ、Ｃ、Ｄ、Ｅのように分類されたといえる。
【００２５】
図６のフローチャートで示したとおり、逆方向探索を始める目的駅到着ノードは、時刻順に選択することになっている。これにより、最初の探索では始発列車が選択されるため、それ以上前を走っている列車がなく、探索空間は狭い範囲に制約される。
２回目以降の探索では、前回までの探索により、すでに評価値が計算されたノードが前方に存在していて、これにより探索空間は狭い範囲に制約される。評価値がすでに計算されているノードであっても、後の探索により評価値が更新される可能性はあるが、後の探索は、目的駅に、より後に到着する所要時間の長い経路であるため、評価値が更新されるのは、リンクコストの設定が単純ではない例外的な場合のみである。
したがって、全体のグラフ構造をたかだか１回程度探索することで、全ての目的駅到達可能ノードに対して評価値を計算することができる。これは、単純にダイクストラ法を目的駅到着ノード側から逆向きに適用して評価値を計算した場合に比べると、計算量を縮減できるということである。
【００２６】
逆方向探索が完了した後、さらに探索装置４が続けて順方向探索を行って経路を確定させる。
図１１に順方向探索による経路確定のフローチャートを、図１２にその一部である再帰処理の部分のフローチャートを示す。
図１１では、出発駅の各出発ノードから目的駅の到着ノードへ向かって探索を行うので、処理を開始する（ステップＳ２０１）と、まず、出発駅の出発ノードのうち、最初のものを選択する（ステップＳ２０２）。後で確定した経路を取り出すために、どのようなノードを経由して探索したかを、図１３に示すようなスタック構造に保存しておく。スタック構造の一番下（最初に入れたデータ）が出発駅の出発ノードのＩＤとなり、以後、順に経由したノードのＩＤを保存していき、最後に目的駅に着いた時に、目的駅到着ノードのＩＤが一番上に入っているようにする。このために、まず出発駅出発ノードのＩＤをスタック構造に保存する（ステップＳ２０３）。
ここで、図１２の再帰処理を開始する（ステップＳ２０４）。
【００２７】
ここで、図１２の再帰処理について説明する。
図１２で、再帰処理を開始した時点で出発ノードが選択されているので、ここから走行リンクをたどって、次の駅の到着ノードを選択する（ステップＳ３０２）。この到着ノードと前の出発ノードとの評価値の差が、その間の走行リンクの重みに等しいかどうかチェックし（ステップＳ３０３）、等しくなければ、このリンクは、最短経路上にはないので、再帰処理を中断して戻る（ステップＳ３０４）。等しければ、このリンクが最短経路上にあるので、選択されている到着ノードのＩＤをスタックに積む（ステップＳ３０５）。
ここで、目的駅に到着したかどうかを調べ（ステップＳ３０６）、到着していれば、スタックの情報を元に経路情報を作成して探索結果記憶装置６に出力する（ステップＳ３０７）。経路情報は、どこの駅からどこの駅まで、どの列車を利用して移動したかを記録しているもので、後で列車の混雑情報などを計算するのに用いる。経路情報の出力が行われた後、スタックから１つノードＩＤを取り出してから（ステップＳ３０８）、再帰処理を脱出する（ステップＳ３０９）。
【００２８】
目的駅に到着していなければ、その到着ノードから停車リンクをたどって、次の出発ノードを選択する（ステップＳ３１０）。この出発ノードと到着ノードとの評価値の差が停車リンクの重みに等しければ（ステップＳ３１１）、出発ノードＩＤをスタックに積み（ステップＳ３１２）、再帰処理を行う（ステップＳ３１３）。再帰処理から復帰すると、出発ノードＩＤをスタックから取り除く（ステップＳ３１４）。
ステップＳ３１１で、評価値の差が停車リンクの重みと等しくなかった場合と、ステップＳ３１４を終えた後に、さらにこの駅で可能な乗換先列車全てに対して乗換の探索を行う（ステップＳ３１５〜Ｓ３２１）。ただし探索順序は、乗換先列車の出発時刻が早いものからとする。
この乗換の探索では、乗換先の列車の出発ノードを選択し（ステップＳ３１６）、この出発ノードと乗換元の到着ノードとの評価値の差が乗換リンクの重みに等しければ（ステップＳ３１７）、出発ノードのＩＤをスタックに積んでから（ステップＳ３１８）、出発ノードから再帰処理を実施する（ステップＳ３１９）。
再帰処理から戻ると、スタックからＩＤを１つ取り出し（ステップＳ３２０）、次のループ（ステップＳ３１５〜Ｓ３２１）を実行する。
ステップＳ３１７で、評価値の差がリンクの重みと等しくなければ、ループを脱出し、ステップＳ３０５で積んだ到着ノードのＩＤをスタックから取り出した上で（ステップＳ３２２）、再帰処理を終了する（ステップＳ３２３）。
【００２９】
図１１に戻って、スタックから出発ノードのＩＤを取り出して（ステップＳ２０５）、次の出発ノードからの探索を開始する。次の出発ノードがなければ（ステップＳ２０６）、処理を終了し（ステップＳ２０８）、あれば、次の出発ノードを選択して（ステップＳ２０７）、ステップ２０３に行く。
その出発駅の出発ノード全てに対して探索を繰り返すと、この出発駅−目的駅の間の移動経路全てが出力されることになる。
【００３０】
順方向探索は、逆方向探索によって、各ノードに割り当てられた評価値によって、分岐の探索を進めるかどうかを決定するため、最短経路となる可能性がない分岐を全く探索することがなく、単純なダイクストラ法による探索に比べて、ずっと高速に探索を行うことができる。
逆方向探索による最適評価値割り当ても、順方向探索による経路の作成も、探索装置４によって行われ、その結果の最適経路は、探索結果記憶装置６に記憶される。
【００３１】
出発駅における出発時刻が与えられると、乗車することができる列車は、その時刻以降にその駅を出発する列車であるから、探索結果記憶装置６に記憶されている出発駅−目的駅の間の全ての移動経路の中で最適な経路は、与えられた出発時刻以降で最初に出発する経路となる。
このようにして、探索条件入力装置３から与えられた探索条件に最適な経路を探索結果出力装置７から得ることが可能となる。
また、この実施の形態１では、鉄道を例に説明したが、バスや船舶、航空機など、決まった地点で積載物の積み込み、積み下ろしをして運行計画が時間に基づいて定められているような交通機関や物流システム等においても適用可能であり、これらを本発明の範囲から排除するものではない。
【００３２】
実施の形態１によれば、乗客の行動経路を探索する時に、各探索箇所から目的地または出発地までの最良の評価値が、予め、目的駅側から行われる予備的な探索によって計算して与えてあることによって、それに基づいて効率よく出発駅側からの探索の枝刈りをすることができ、それによって従来のダイクストラ法に基づく探索と同じ結果を、ダイクストラ法に基づく探索に比べて著しく短い探索時間で得ることができる。
【００３３】
実施の形態２．
実施の形態１では、出発駅にある時刻に現れて目的駅へ移動する最適経路を考える乗客について述べたが、逆に目的駅へ到着したい時刻を定めて、そこから逆算して出発駅に現れる乗客も存在する。実施の形態２は、この乗客のような場合についてのものである。
【００３４】
目的駅に到着する時刻を定めて、それに間に合う最適な経路を探索する方法は、実施の形態１で、説明した方法を逆に適用することで全く同様に行える。
実施の形態２では、図１の最適経路探索システムのうち、探索条件入力装置３が出発駅、目的駅、目的駅での到着時刻を入力するものとなり、グラフ構造作成装置２が図２のグラフ構造のリンクを逆向きに張るものとなり、探索装置４が出発駅から各ノードまでの最短距離のリンクの重みの合計である評価値を、予め各ノードに割り当てて、この後に目的駅側からの探索を行うようにする。
これにより、目的駅での時刻を定めた最適経路探索が可能となる。これは特に、目的駅付近で大規模なイベントがあるような場合などに有効である。
【００３５】
実施の形態２によれば、最初に出発駅側からの探索により、各ノードに評価値を与えておき、その後、目的駅側から探索することにより、目的地到着時刻を定めて出発地に現れる利用者の出発地から目的地までの最適経路探索を行うときに最短経路とならない分岐を見分けることができるため、探索を枝刈りして効率よく探索することができる。
【００３６】
実施の形態３．
図１４は、この発明の実施の形態３による最適経路探索システムの乗換障壁の影響を説明する図である。
図１４において、最適経路の評価値を各ノードに割当てる探索を行うときに、乗換障壁のために、乗換元列車１では評価値更新ができると共に、乗換元列車２では評価値更新ができない。
図１５は、この発明の実施の形態３による最適経路探索システムの評価値格納領域を二つずつ用意する理由を説明する図である。
図１５において、Ａ列車とＢ列車の目的駅到着ノードまでの各ノードの評価値が示されている。Ａ列車は出発駅から出発し、Ｂ列車は途中駅１から出発するが、出発ノード間の評価値更新を行うと、Ａ列車の途中駅１出発ノードでは、乗換障壁が考慮されない評価値が設定されるので、正しく探索を行うことができなくなる。このため、各ノードに対して出発時用と途中用の二つの評価値が必要になる。
【００３７】
実施の形態３では、実施の形態１または実施の形態２に示した最適経路探索システムに、さらに乗換障壁のような情報を付け加えて探索を行う時に、正確に最適経路を求める方法についてのものである。
ここで、乗換障壁とは、乗換を乗客がどの程度嫌がるかを表した値であり、この例では、乗換障壁を時間に換算して表し、１回の乗換は、その乗換障壁の時間だけ所要時間が長くなるのと同等であるとみなして取り扱う。各乗換がどの程度の乗換障壁に相当するかは、各駅の条件などによって予め定められているものとする。
【００３８】
乗換障壁を反映して最適経路探索を行うためには、図２の乗換リンクに対して、所要時間にさらに乗換障壁の値を加えなければならない。乗換リンクのコストが正しく設定されると、実施の形態１または実施の形態２の最適経路探索システムにより、乗換障壁を反映した最適経路が求められる。
ただし、図７及び図１２における乗換列車を探すループの脱出条件を変更する必要がある。
図７においては、乗換元列車のノードの評価値を更新できなくなった時にループを脱出し、図１２においては、乗換先列車のノードと乗換元列車のノードとの評価値の差が、乗換リンクの重みと等しくなくなった時にループを脱出している。これは、出発時間や到着時間の差と評価する順番の関係から、それより先を探索しても乗換ができる可能性はないということを利用したものである。
【００３９】
しかし、実施の形態３では、乗換障壁が設定されていることによって、乗換可能な列車の順番が入れ替わることがある。これについて、図１４を用いて説明する。
図７の最適経路の評価値を各ノードに割り当てる探索を行っているとき、ある乗換先列車のノードの評価値が１０で、乗換元列車１（先着）と乗換元列車２（後着）のノードの評価値が共に２２であるとする。図７のフローチャートに従えば、後着列車から順番に探索するから、乗換元列車２と乗換先列車の間の乗換リンクの重みとの比較により評価値が更新できない。しかし、乗換元列車１と乗換元列車２では、乗換先列車に対する乗換障壁が大きく異なるため、到着時刻の差が乗換障壁の差より小さければ、図１４のように先着列車へは評価値更新可能となることがある。
このことを考慮して、実施の形態３での乗換を探索するループは、図７及び図１２におけるループ脱出条件を満たしてから、さらに最大乗換障壁時間だけ余計に探索をしなければ完全ではない。
【００４０】
また、乗換障壁を導入する場合には、各ノードの評価値を１つのノードにつき２つずつ記憶できるようにして使い分ける必要がある。この理由を図１５により説明する。
図１５では、Ａ列車とＢ列車の２本の列車が運行されていて、各駅間の走行リンクの重みが共に４、駅の停車リンクの重みを２とし、列車間の時間間隔を８、乗換障壁をすべて１とすると、図７のフローチャートのステップＳ１０６〜Ｓ１０８の出発ノード間の評価値更新を考慮しなければ、各ノードの評価値は、図１５のようになる。
ところが、出発ノード間の評価値更新を考慮すると、Ｂ列車の途中駅１出発ノードからＡ列車の途中駅１出発ノードの評価値が更新されて、Ａ列車の途中駅１出発ノードの評価値は１７から１６になる。
この１の差は、出発ノード間の評価値更新では、乗換障壁が考慮されないためである。出発ノード間の評価値更新で乗換障壁を考慮しないことは、途中駅１が本来の出発駅であった場合は、Ａ列車に乗らずＢ列車に乗るということは、乗換ではないため正しい。しかし、図１５のように、さらに手前の駅が出発駅であった場合、Ａ列車の途中駅１出発ノードの評価値が更新されてしまうことによって、Ａ列車の最短経路上のノード間の評価値の差がその間のリンクの重みと等しくなくなり、後で経路探索を行うことができなくなってしまう。
【００４１】
出発ノード間の評価値更新をした時に、さらに再帰的にＡ列車の途中駅１到着ノードの評価値更新を行うようにすると、Ａ列車の途中駅１到着ノードにＡ列車からＢ列車へ乗換障壁なしで乗り換えたときの評価値が設定されてしまうため、これも問題となる。
出発ノード間の評価値更新をした値が必要になるのは、その駅が出発駅であった場合だけであるので、ノード毎に途中用の評価値と出発時用の評価値の２つを持たせておき、通常は両方の評価値を全く同じに更新していくが、出発ノード間の評価値更新についてだけは、出発時用の評価値に対してのみ行うようにすると、この問題を解決できる。後で、経路探索を行うときには、出発駅でのみ出発時用の評価値を参照し、後は通常用の評価値を参照してたどると、正しく探索が行える。
【００４２】
この問題が発生するのは、乗換障壁があるためであるので、乗換障壁を全く考慮しないという場合には、評価値領域を２つずつ用意する必要は無い。また、評価値が更新された場合、通常はそのノードからさらに再帰的に探索するが、乗換障壁が考慮されない評価値が伝播することを防ぐために、出発ノード間の評価値更新の場合は、さらにその先まで再帰的に探索を行うことはしない。
このようにすることで、乗換障壁を考慮したより、実態に即した探索を行うことが可能となる。この例では鉄道旅客の乗換に余計なコストを加算する例を示したが、物流網においてトラック間での荷物の積み替えのような場合も、同様にして積み替えの少なくなる経路を探索することが可能となる。
【００４３】
実施の形態３によれば、この構成により、リンクの重み付けに乗換障壁を含めて考えている場合に、同一経由点の別のノードを経由して出発する場合を考慮した探索をすると、その経由点が途中経由点であった場合に正しく探索されなくなる問題を回避して、正しく探索を行うことができる。
【００４４】
実施の形態４．
実施の形態４は、実施の形態１〜実施の形態３に示した最適経路探索システムを利用した運行計画作成システムについてのものである。
図１６は、この発明の実施の形態４による運行計画作成システムを示す全体構成図である。
図１６において、１、２、４〜６は図１におけるものと同一のものである。運行計画入力装置８は、運行計画を入力する。運行計画編集装置９は、運行計画入力装置８からの入力を受けて、運行計画記憶装置１に記憶されている現状の運行計画に対する変更・追加などの処理を行う。運行計画表示装置１０は、現在の運行計画をダイヤ図・グラフ・表その他の形式で表示する。輸送需要記憶装置１１は、乗客需要のデータを記憶する。運行計画評価装置１２は、探索結果記憶装置６の記憶内容に基き、各乗客の所要時間や乗換回数、各列車の混雑度などにより運行計画を評価する。評価結果表示装置１３は、運行計画評価装置１２によって評価された運行計画の評価結果を表示する。
【００４５】
次に、動作について説明する。
運行計画作成システムでは、通常、運行計画入力装置８からの入力を受けて、運行計画記憶装置１に記憶されている現状の運行計画に対する変更・追加などの処理を運行計画編集装置９で行って、運行計画記憶装置１に書き込み、現在の運行計画を、運行計画表示装置１０でダイヤ図・グラフ・表その他の形式で表示して、それを参考にさらに入力を行う、という形で運行計画の作成が進められる。
これに対して、現在計画中の運行計画を実行した時の乗客の所要時間や乗換回数などの評価を行うためには、乗客の行動経路を推定する必要があり、これに最適経路探索システムを利用することができる。
【００４６】
実施の形態１〜実施の形態３では、ある目的駅または出発駅に対しての最適経路を求めるが、これを任意の駅間について全て求めた上で、各駅間の乗客需要のデータを合わせることで、各経路の乗客数を推定することができる。
例えば、自動改札から収集される入場時刻と出発駅、目的駅の情報の組み合わせがあれば、出発駅と目的駅の間の最短経路の中から、入場時刻以降に最初に出発駅を出発する経路を選択すると考えることができるので、目的駅までの利用列車・乗換駅と目的駅到着時刻を推定することができる。
また、ＯＤ表と呼ばれる出発駅と目的駅のマトリクス上に各駅間の移動乗客数を記載した表があれば、その対象とする時間の長さで割ることで、単位時間当たりの駅間乗客需要を求めることができる。
【００４７】
都市鉄道における大半の乗客のように、時刻表を気にせず出発駅に均一に乗客が現れるという仮定の元では、前にその駅を出発した経路と次にその駅を出発する経路の時間間隔に比例して、次の経路の利用乗客が決まると考えられるので、単位時間当たり駅間乗客需要の値に経路間の時間間隔を掛けることで、各経路の乗客数を推定することができる。
自動改札の入場情報を利用する方法でも、ＯＤ表を利用する方法でも、仮に同時刻に出発して途中の利用列車や乗換駅が異なる複数の経路が、同一の評価値で存在していた場合には、計画の評価をする目的では、個別の乗客の移動経路を推定する必要はなく、全体の傾向を推定できれば十分であるため、それらを按分して乗客配分をすればよい。
【００４８】
各経路を何人の乗客が利用したかが推定できれば、利用列車ごとに乗客数を積算することによって、各列車の区間ごとの乗客数や各駅での乗降客数など様々な統計情報を推定することができる。こうした統計情報は、従来実際に実行したダイヤにおける結果を実測することができるだけであったが、本発明に基づく最適経路探索システムを使うことによって、まだ実行していないダイヤに対して、このような統計情報を推定して求めることができるようになる。
図１６のように、グラフ構造作成装置２の入力として、現在の運行計画を運行計画記憶装置１から取得して、グラフ構造記憶装置５にグラフ構造を作成し、乗客需要のデータを輸送需要記憶装置１１から取得して、探索装置４により探索を実行することで、全体の最適経路を探索結果記憶装置６に得ることができ、乗客流動を推定することができる。
この情報を各乗客の所要時間や乗換回数、各列車の混雑度などを評価する運行計画評価装置１２に与えることで、運行計画の評価が求まり、評価結果表示装置１３に出力される。この出力結果を参考にしながら、これを改善するように、運行計画の変更を繰り返すことにより、運行計画を利用客にとって、よりよいものにすることが可能となる。
【００４９】
実施の形態４によれば、最適経路探索システムを運行計画作成システムに適用することにより、運行計画の立案を行う担当者は、利用者の立場からの評価を考慮しながら作業を行うことができ、利用者にとって利便性の高い運行計画作成を行うことができる。
【００５０】
実施の形態５．
実施の形態５は、実施の形態１〜実施の形態３に示した最適経路探索システムを利用した運行管理支援システムについてのものである。
図１７は、この発明の実施の形態５による運行管理支援システムを示す全体構成図である。
図１７において、１、２、４〜６、８、１１〜１３は図１６におけるものと同一のものである。運行状況把握装置１５は、管理対象である輸送システム１４から、各列車等の位置や速度などの現在の運行の状況を取得する。運行計画変更装置１６は、運行計画を変更し、輸送システムに変更された運行計画を実行させる。運行状況予測装置１７は、現在の運行状況及び運行計画入力装置により入力された運行計画の変更に基き、将来の運行状況を予測する。運行計画記憶装置１には、現状の運行状況及び将来の運行状況予測の情報が記憶される。運行状況表示装置１８は、運行計画記憶装置１に記憶された将来の運行状況を表示する。
【００５１】
次に、動作について説明する。
運行管理支援システムでは、管理対象としている輸送システム１４から運行状況把握装置１５により各列車等の位置や速度などの現在の運行状況が取得され、運行計画記憶装置１に格納される。運行計画入力装置８から入力された運行計画の変更と、運行計画記憶装置１に格納されている輸送システムの現在の運行状況とから、運行状況予測装置１７により将来の運行状況を予測した上で、運行状況表示装置１８に出力する。
そして、出力結果が望みのものであれば、運行計画の変更の指示を実際の輸送システム１４に運行計画変更装置１６を通して送り出し、実行され、望みのものでなければ、さらに繰り返し入力を行って運行計画の変更を続けるという方法で運行管理が行われる。
【００５２】
この中で、本発明の最適経路探索システムを利用した運行計画の評価を行うために、運行計画記憶装置１に記憶されている現在の運行状況及び将来の運行状況の予測情報から、グラフ構造作成装置２によりグラフ構造記憶装置５にグラフ構造を作成し、輸送需要記憶装置１１に格納されている輸送需要の各乗客の情報とから、探索装置４により、各乗客の最適経路を求めて探索結果記憶装置６に記憶し、運行計画評価装置１２で評価を行って、その結果を評価結果表示装置１３に出力する。
この出力された結果を見ながら、運行計画の変更を考えることにより、より利用客の利便性に配慮した運行管理を行うことが可能になる。
【００５３】
実施の形態５によれば、最適経路探索システムを利用した運行管理支援システムとすることにより、運行管理の際に利用者の立場からの評価を考慮しながら作業を行うことができ、利用者にとって利便性の高い運行管理を行うことができる。
【００５４】
実施の形態６．
実施の形態６では、実施の形態５に示した運行管理支援システムに、さらに最適経路探索の入力として、実際の利用状況を与えるようにしたものである。
図１８は、この発明の実施の形態６による運行管理支援システムを示す全体構成図である。
図１８において、１、２、４〜６、８、１１〜１８は図１７におけるものと同一のものである。図１８では、輸送需要を随時把握できる輸送需要把握装置１９が設けられている。
【００５５】
実施の形態６でも、運行計画変更を行う仕組みは、実施の形態５と同じであるが、実施の形態６では、輸送需要の把握に関する部分が追加されている。
最近の輸送システムでは、例えば鉄道では、自動改札機などの乗客の数を自動的に数えることのできる装置が多く用いられており、こうした輸送需要を随時把握できる装置を利用すると、事前の輸送需要の予測や過去の統計に頼るよりも正確に把握することが可能である。
このため、輸送需要把握装置１９を置いて、これにより把握された情報と過去の統計情報などを合わせて考慮した上で、探索装置４を実行することで、より正確な運行計画の評価を行なうことが可能となる。
【００５６】
実施の形態６によれば、輸送需要把握装置により輸送需要を把握するようにしたので、運行管理の際に利用者の流動情報をより正確に把握して作業を行うことができる。
【００５７】
なお、上記実施の形態１〜実施の形態６の説明では、列車に搭乗する乗客の最適経路探索として説明したが、一般に、移動体に積載される積載物の最適経路探索としても同じである。
【図面の簡単な説明】
【００５８】
【図１】この発明の実施の形態１による最適経路探索システムを示す全体構成図である。
【図２】この発明の実施の形態１による最適経路探索システムの乗客流動をグラフ構造で示す概念図である。
【図３】この発明の実施の形態１による最適経路探索システムの乗客流動の簡略化したグラフ構造を示す図である。
【図４】図３に対応するデータ構造を示す図である。
【図５】この発明の実施の形態１による最適経路探索システムの予め計算した各ノードの最短経路評価値を示す図である。
【図６】この発明の実施の形態１による最適経路探索システムの探索装置によって実行される目的駅側からの逆方向の探索を示すフローチャートである。
【図７】この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索での再帰処理を示すフローチャートである。
【図８】この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索を行うときの途中経過を示す図である。
【図９】この発明の実施の形態１による最適経路探索システムの追い抜き関係にある場合の評価値の更新を示す図である。
【図１０】この発明の実施の形態１による最適経路探索システムの逆方向探索終了後のノードの状態を示す図である。
【図１１】この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索を示すフローチャートである。
【図１２】この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索での再帰処理を示すフローチャートである。
【図１３】この発明の実施の形態１による最適経路探索システムのスタック構造を示す図である。
【図１４】この発明の実施の形態３による最適経路探索システムの乗換障壁の影響を説明する図である。
【図１５】この発明の実施の形態３による最適経路探索システムの評価値格納領域を二つずつ用意する理由を説明する図である。
【図１６】この発明の実施の形態４による運行計画作成システムを示す全体構成図である。
【図１７】この発明の実施の形態５による運行管理支援システムを示す全体構成図である。
【図１８】この発明の実施の形態６による運行管理支援システムを示す全体構成図である。
【符号の説明】
【００５９】
１ 運行計画記憶装置
２ グラフ構造作成装置
３ 探索条件入力装置
４ 探索装置
５ グラフ構造記憶装置
６ 探索結果記憶装置
７ 探索結果出力装置
８ 運行計画入力装置
９ 運行計画編集装置
１０ 運行計画表示装置
１１ 輸送需要記憶装置
１２ 運行計画評価装置
１３ 評価結果表示装置
１４ 輸送システム
１５ 運行状況把握装置
１６ 運行計画変更装置
１７ 運行状況予測装置
１８ 運行状況表示装置
１９ 輸送需要把握装置
【技術分野】
【０００１】
この発明は、鉄道に代表される、予め定められた運行計画に従って運行される交通機関において、乗客（積載物）の移動経路を求める最適経路探索システム並びにこれを用いた運行計画システム及び運行管理システムに関するものである。
【背景技術】
【０００２】
鉄道に代表される、予め定められた運行計画に従って運行される交通機関においては、利用客にとってよりよい運行計画を策定するために、運行計画を乗客の立場から評価するということが考えられている。乗客の立場から見た運行計画に対する評価指標としては、各乗客の旅行所要時間や乗換の回数、移動途中の混雑状況などが挙げられる。
こうした評価値を計算するためには、各乗客がシステム内をどのように移動し、どこで乗り換えるかの情報が必要である。ところで、乗客行動を実際に測定して、こうした情報を得るということは、様々な装置を各所に配置して測定分析を行わなければならず、困難である上に、実際に実行された運行計画に対してのみしか用いることができない。運行計画や運行管理に役立てるために、計画案に対して、こうした評価値を計算するためには、乗客のシステム内での行動を何らかの方法で推定して求める必要がある。
これに対して、自動改札機やＩＣカード式乗車券などから得ることのできる情報（例えば、出発駅に入った時刻と目的駅を出た時刻）のこれまでの統計と、その交通機関の運行計画の情報から推定する方法が考えられる。
従来の技術としては、ロジットモデルを利用した方法（例えば特許文献１）と、グラフ構造でモデルを表現してダイクストラ法を適用した方法（例えば非特許文献１）があった。
特許文献１には、乗車券としてのＩＣカードにより旅客流動を把握し、ロジットモデルに基いた旅客行動モデルを構築し、このモデルにより、列車ダイヤに乱れが生じたときの各列車の乗客数を推定するものが記載されている。
非特許文献１には、各列車の到着と出発イベントをノードで表し、列車運行・停車・乗換などで乗客が移動する可能性のあるノード同士を重み付き有向リンクで接続したグラフにより乗客行動を表現し、乗客の出発駅の任意の出発ノードを起点として、最も経路長が短くなる目的駅の到着ノードを終点とする経路を選択するダイクストラ法最短経路探索を行うものが記載されている。
【０００３】
【特許文献１】特開２００１−５５１４５号公報（第３〜６頁、図１）
【非特許文献１】平成１５年電気学会全国大会講演論文集、２００３、ｐｐ３４３−３４４、「都市近郊鉄道における運転整理時の乗客行動経路再決定の高速化手法」
【発明の開示】
【発明が解決しようとする課題】
【０００４】
予め定められた運行計画に従って運行される交通機関においては、計画立案に関して、事前に運行計画を立案するという段階と、事故や災害などの影響を受けて運行が乱れた際に、適切な処置を行って元の運行計画に復帰させる（これを運転整理と呼ぶ）という段階の２つが存在している。
このうち前者については、十分に時間を掛けて計画を練ることができるが、後者については、実際に進行する事態に合わせて、その場その場で短時間に新しい計画を立案しなければならないという強い制約が存在する。こうした場面でも乗客の行動を推定して、その情報を利用して計画立案に生かしていくためには、乗客の移動経路の推定を極めて短時間に終わらせなければならない。
特許文献１のロジットモデルを利用した方法では、推定精度は高いものの、推定に相当程度の時間が掛かり、運転整理の局面に利用することは困難である。
また、非特許文献１のダイクストラ法を利用した方法についても、実用規模の問題に対して、乗客の移動経路推定に掛かる時間が長く、運転整理の局面に利用することは困難であった。
【０００５】
この発明は、上述のような課題を解決するためになされたものであり、運転整理の局面でも乗客の移動経路推定を短時間で行うことができる最適経路探索システム及びこれを用いて、より利用客にとって利便性の高い運行計画を立案及び運行管理を支援できる運行計画作成システム及び運行管理支援システムを得ることを目的としている。
【課題を解決するための手段】
【０００６】
この発明に係わる最適経路探索システムにおいては、時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの移動体の積載物の移動経路を探索する最適経路探索システムにおいて、積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、運行計画を記憶する運行計画記憶装置、移動体の出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、ノード間の経過をリンクとして表現し、リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成されたグラフ構造を利用して、積載物の出発点から到着点への最適経路を探索する探索装置、及び探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
探索装置は、探索条件入力装置により入力された積載物の到着点から出発点に向う逆方向に、各経由点のノードから到着点までの最短経路のリンクの重みを合計し、各ノードに評価値として割当てた後、積載物の出発点及び出発点での出発時刻に基き、出発点から到着点までの順方向に、各ノードに割当てられた評価値及びリンクの重み付けの値により各経由点を選択することにより、積載物の出発点から到着点までの最適経路を探索するものである。
【発明の効果】
【０００７】
この発明は、以上説明したように、時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの移動体の積載物の移動経路を探索する最適経路探索システムにおいて、積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、運行計画を記憶する運行計画記憶装置、移動体の出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、ノード間の経過をリンクとして表現し、リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成されたグラフ構造を利用して、積載物の出発点から到着点への最適経路を探索する探索装置、及び探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
探索装置は、探索条件入力装置により入力された積載物の到着点から出発点に向う逆方向に、各経由点のノードから到着点までの最短経路のリンクの重みを合計し、各ノードに評価値として割当てた後、積載物の出発点及び出発点での出発時刻に基き、出発点から到着点までの順方向に、各ノードに割当てられた評価値及びリンクの重み付けの値により各経由点を選択することにより、積載物の出発点から到着点までの最適経路を探索するので、乗客の行動経路を探索するときに、各探索箇所から目的地または出発地までの最良の評価値が予め逆方向の予備的な探索によって計算して与えてあることによって、それに基づいて効率よく順方向の探索の枝刈りをすることができ、それによって従来のダイクストラ法に基づく探索と同じ結果を、ダイクストラ法に基づく探索に比べて著しく短い探索時間で得ることができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
図１は、この発明の実施の形態１による最適経路探索システムを示す全体構成図である。
図１において、運行計画記憶装置１は、予め対象とする鉄道の計画ダイヤを格納している。グラフ構造作成装置２は、乗客流動を表現したグラフ構造を作成する。探索条件入力装置３は、乗客の出発駅、目的駅、出発駅での出発時刻を、乗客の移動経路探索の条件として入力する。探索装置４は、運行計画入力装置１からの情報を基に探索を実行して、その結果を探索結果記憶装置６に出力する。グラフ構造記憶装置５は、グラフ構造作成装置２によって作成された、乗客流動を表現したグラフ構造を格納する。探索結果表示装置７は、探索装置４による探索結果を表示する。
【０００９】
図２は、この発明の実施の形態１による最適経路探索システムの乗客流動をグラフ構造で示す概念図である。
図２において、列車の各駅への到着と出発をそれぞれグラフ理論におけるノードとして表現し、列車の駅への停車、駅間の走行をそれらのノード間を結ぶ有向リンクとして表現する。各リンクには重みと呼ばれる数値を持たせる。図２では、リンクの脇に重みの値を付記してある。重みは、そのリンクの利用しやすさを表現した値であり、小さいほど利用しやすいことを示す。
なお、図２では、白い丸が、出発ノードであり、ハッチングされた丸が、到着ノードである。各ノード間の経過がリンクであり、実線が停車リンク、点線が走行リンク、一点鎖線が乗換リンクを示している。駅Ａが出発駅（出発点）、駅Ｂと駅Ｃが途中駅（経由点）、駅Ｄが目的駅（到着点）である。
【００１０】
図３は、この発明の実施の形態１による最適経路探索システムの乗客流動の簡略化したグラフ構造を示す図である。
図３において、ノード１〜ノード３と、各ノードを結ぶリンクの重みが示されている。
図４は、図３に対応するデータ構造を示す図である。
図４において、図３のグラフ構造に対応する汎用コンピュータメモリ上のデータ構造が示されている。各ノードに対して一意に識別できるノードＩＤを割り当てている。
【００１１】
図５は、この発明の実施の形態１による最適経路探索システムの予め計算した各ノードの最短経路評価値を示す図である。
図５において、各ノートには、目的駅側からの逆方向の探索によって、目的駅ノードへの最短経路評価値を割付けている。
図６は、この発明の実施の形態１による最適経路探索システムの探索装置によって実行される目的駅側からの逆方向の探索を示すフローチャートである。
図７は、この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索での再帰処理を示すフローチャートである。
【００１２】
図８は、この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索を行うときの途中経過を示す図である。
図８において、駅Ａから駅Ｄまで４つの駅がある路線で、実線により表された急行と、点線により表された各停が交互に運転している場合を示している。
図９は、この発明の実施の形態１による最適経路探索システムの追い抜き関係にある場合の評価値の更新を示す図である。
図９において、出発ノードから到着ノードまでのリンクの重みが、９の列車と３の列車が存在している。後からリンク重み３の列車が出発して先行の列車を追い抜く様子を示している。
図１０は、この発明の実施の形態１による最適経路探索システムの逆方向探索終了後のノードの状態を示す図である。
図１０において、逆方向の探索終了後の各ノードは、最短距離にある目的駅到着ノードによって、Ａ、Ｂ、Ｃ、Ｄ、Ｅのように分類されている。
【００１３】
図１１は、この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索を示すフローチャートである。
図１２は、この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索での再帰処理を示すフローチャートである。
図１３は、この発明の実施の形態１による最適経路探索システムのスタック構造を示す図である。
図１３には、順方向の経路探索されたノードが探索された順序でスタックに格納されている。
【００１４】
次に、動作について説明する。
実施の形態１の最適経路探索システムでは、まず、乗客の移動経路の探索条件として、探索条件入力装置３から乗客の出発駅、目的駅、出発時刻を入力する。また、予め対象とする鉄道の計画ダイヤを格納した運行計画記憶装置１からの情報を基にして、グラフ構造作成装置２が乗客流動を表現した、図２のようなグラフ構造を作成し、グラフ構造記憶装置５に格納する。
探索装置４が、運行計画入力装置１からの探索条件の情報を基に、探索を実行して、その結果を探索結果記憶装置６に出力し、それを探索結果表示装置７が表示する。探索結果表示装置７により表示される結果は、探索条件入力装置３に入力された探索条件の下で、最適な利用列車、乗換駅などの情報を含む経路情報である。
【００１５】
次いで、さらに詳しく説明する。
グラフ構造作成装置２が作成するグラフ構造は、非特許文献１に記載された手法による。具体的には、図２に示すように、列車の各駅への到着と出発をそれぞれグラフ理論におけるノードとして表現し、列車の駅への停車、駅間の走行をそれらのノード間を結ぶ有向リンクとして表現する。各リンクには重みと呼ばれる数値を持たせ、図２では、リンクの脇に重みの値を付記してある。この重みは、そのリンクの利用しやすさを表現した値であり、小さいほど利用しやすいことを示す。乗客は所要時間が長いことや乗換があることなどを嫌がるので、そうした乗客が嫌がる事象に対しては、大きな値を与え、そうでないことに対しては、小さな値を与えることで、乗客の経路選択を表現する。
なお、図２の例では、重みは、そのリンクが表している停車や走行の所要時間を表しているが、それ以外の値を与えてもよい。さらに、乗換が可能な駅では、乗換元の列車のその駅への到着ノードから乗換先の列車のその駅での出発ノードへ、乗換を表現する有向リンクを張る。図２の例では、乗換リンクの重みは、その乗換の所要時間である。
【００１６】
グラフ構造は、グラフ構造記憶装置５に記憶されるが、このグラフ構造は、汎用コンピュータのメモリ上のデータ構造として実現してもよい。図３のような簡単なグラフ構造をメモリ上のデータ構造として表現した例を図４に示す。
図４では、各ノードに対して、一意に識別できるノードＩＤを割り当てる。さらに、そのイベントが発生した時刻（到着ノードならば到着時刻、出発ノードならば出発時刻）を後のために記録しておき、また、後で経路探索に必要となる評価値を格納する領域を用意する。
リンクの情報は、１つのノードに関係するリンクの数が可変であるので、別に配列を用意する。グラフは、有向グラフであるので、リンクの向きを区別できるような構造にするが、後で述べるように逆方向からの探索を行う必要があるので、リンクの到着側のノードからも、そのリンクを容易に参照できるようにしておく。
【００１７】
乗客は、ある時刻に出発駅にやってきて、目的駅までの列車を選択して乗車したり、乗り換えたりして目的駅まで移動する。この乗客の行動モデルを考えると、多くの乗客は、所要時間が短いとか乗換が少ないなどの条件で、乗車する列車を選択していると考えられる。
これは、グラフ構造の上では、リンクの重みが少ない経路を選択するということであり、図２のグラフ構造で考えると、乗客は、出発駅のある１つの出発ノードから目的駅へ向かってリンクに沿って移動していくが、移動経路上のリンクの重みの合計が、最も少なくなるような経路を選択することになる。
【００１８】
本発明は、探索装置４によって、まず目的駅の側から出発駅に向かって逆方向に予備的な探索を行って、予め各ノードに経路選択に必要な情報（評価値）を割り当てておき、その情報を元に出発駅の側からの探索を行って、移動経路を確定させる。
目的とする駅が１つに定まれば、各ノードから目的駅への最短経路は、例え、複数の経路が同一の評価値で共に最短であったとしても、必ずある１つの評価値を持っていることになる。
【００１９】
図５に示すように、予め各ノードから目的駅へのこのただ１つの最短経路評価値を求めておくと、出発駅側から探索を実行したときに、現に探索を実行しているリンクが最短経路となるかならないか、両端のノードの最短経路評価値の差とそのリンクの重みの比較から容易に判断できるため、的確に探索の枝刈りを実行して探索時間を縮減することができる。
例えば、図５に示されるように、左側の経路では、出発駅ノードと途中駅ノードとの間のリンクの重みは５であり、出発駅ノードが評価値１０、途中駅ノードが評価値５であるから、両評価値の差とリンクの重みが等しくなり、このリンクが最短経路上のリンクであることがわかる。一方、右側の経路では、出発駅ノードと途中駅ノードとの間のリンクの重みは８であり、出発駅ノードが評価値１０、途中駅ノードが評価値５であるから、両評価値の差とリンクの重みが等しくなく、このリンクは最短経路上のリンクではないことがわかる。
つまり、最初に目的駅側からの逆方向の予備的な探索によって、各ノードに目的駅への最短経路の評価値を割り当てておき、それを元に出発駅側からの探索を行えばよいのである。
【００２０】
各ノードに予め与えておく目的駅までの最短経路評価値を求めるための、探索装置４によって実行される目的駅側からの逆方向の探索のフローチャートを図６に、その一部である再帰処理の部分のフローチャートを図７に示す。
次に、図６に基き、探索装置４によって実行される目的駅側からの逆方向の探索について、説明する。
例として、図８のように駅Ａから駅Ｄまで４つの駅がある路線で、急行と各停が交互に運転している場合を考える。
図６において、処理開始（ステップＳ１）後、最初に全てのノードに初期の評価値として十分大きな値を設定しておく（ステップＳ２）。このノードの評価値は、そのノードから目的とする駅までの現在の最短経路の評価値（所要時間の合計）を記憶しておくためのものである。駅Ｄに到着する経路を探索する場合には、まず図６のフローチャートのステップＳ３、Ｓ４に従い、駅Ｄに最初に到着する列車の到着ノードを選択して（ステップＳ３）評価値を０にセット（ステップＳ４）し、ステップＳ５の再帰処理を開始する。
【００２１】
次いで、図７の再帰処理について説明する。
図７の再帰処理が開始される（ステップＳ１０１）と、まず現在選択されている到着ノードからリンクを逆にたどって、１つ前の駅の出発ノードを選択する（ステップＳ１０２）。そしてこのノードの評価値を改善可能であるかどうか調べる（ステップＳ１０３）。評価値を改善可能であるというのは、現在そのノードに設定されている評価値よりよい（小さな）評価値を設定可能であるということである。最初に全てのノードに十分大きな値を初期の評価値として設定してあるので、初めてそのノードを探索した時には、必ず評価値を改善可能であり、２回目以降に探索した時には、ノードの記憶領域に保存してある前回までの探索の中で最良の評価値と今回の評価値を比較してよい方を採用して、ノードに記憶されている評価値を更新する（ステップＳ１０５）。今回の評価値は、１つ前の到着ノードの評価値に、その間のリンクの重みを合計して求める。１つ前の到着ノードの評価値は、目的駅への最短経路の長さ（リンク重みの合計）を表しているので、更新される評価値は、この出発ノードから目的駅への現在の最短経路の長さを表すことになる。ここで評価値を更新できなければ、再帰を脱出する（ステップＳ１０４）。
【００２２】
評価値が更新できた場合は、この出発ノードより先にこの駅を出発する他の列車の各出発ノードを時間的に後のものから順に評価値を更新していくループを実行する（ステップＳ１０６〜Ｓ１０８）。このループは、そのノードから出発するより後の列車の出発ノードから出発した方が、目的駅に早く到着するようなノードを探索するために実行される。
これは、図９に示すように途中で追い抜きが行われるような場合に、正しく探索が行えるようにするためのものである。図９の例のように、出発ノードから到着ノードまでのリンクの重みが、９の列車と３の列車が存在していて、後からリンク重み３の列車が出発して先行の列車を追い抜くとき、先行のリンク重み９の列車に乗車するよりも、この列車を見送って、後のリンク重み３の列車に乗った方が経路全体の評価値が良い、という場合がある。
このため、同一駅の出発ノード間での評価値の更新をステップＳ１０６〜Ｓ１０８で行う。評価値は、ステップＳ１０５で、更新した評価値に、出発ノードの時間差を加えて求める。出発ノードを１つずつ前にたどりながら更新を行い、評価値の改善ができなくなった時点でこのループを脱出する。
【００２３】
出発ノード間の評価値更新が完了した後、ステップＳ１０５で、評価値を更新した出発ノード（今まさに注目している列車の注目している駅の出発ノード）から、停車リンクを逆にたどって、その駅の到着ノードを選択し（ステップＳ１０９）、到着ノードの評価値の更新が可能であるならば（ステップＳ１１０）、更新して（ステップＳ１１１）、ステップＳ１０１から再帰的に処理を行う（ステップＳ１１２）。
ステップＳ１１２の再帰から復帰した後と、ステップＳ１１０で更新ができなかった時の次の処理として、乗換の探索を行う。乗換が行えるのは、乗換先の列車が出発する時刻より前にその駅に到着する列車であるのは当然なので、乗換先列車出発時刻から時間的に前にその駅の到着ノードを順番に探索を行う（ステップＳ１１３〜ステップＳ１１６）。
評価値の更新が行えた（乗換元到着ノードの評価値が乗換先出発ノードの評価値に乗換リンクの重みを合計したより大きい）場合は、その乗換元到着ノードから前にたどってステップＳ１０１から再帰的に探索を行う。評価値の更新が行えなかった場合、それ以上前の時間に到着する列車を探索しても評価値改善の見込みがないので、そこで乗換探索を打ち切って、図７で示したフローチャート全体の再帰探索を脱出する（ステップＳ１１７）。
【００２４】
図７の再帰処理を脱出すると、図６のステップＳ６に戻ってくる。再帰処理を始めるときに選択していた到着ノードの次に目的駅に到着するノードを選択して（ステップＳ７）、ステップＳ４で、選択ノードの評価値を０にセットした後、再びステップＳ５の再帰処理を開始する。目的駅の到着ノード全てに対して再帰処理が完了すると、目的駅側からの逆方向探索が完了する（ステップＳ８）。
逆方向探索が完了した時点で、各ノードには目的駅の到着ノードの中で最短距離にあるノードまでの距離（最短経路の評価値）が与えられている。図５の方式で、最短経路上にあるノード・リンクは識別できるので、この時点で図１０のように、最短距離にある目的駅到着ノードによって、全てのノードがＡ、Ｂ、Ｃ、Ｄ、Ｅのように分類されたといえる。
【００２５】
図６のフローチャートで示したとおり、逆方向探索を始める目的駅到着ノードは、時刻順に選択することになっている。これにより、最初の探索では始発列車が選択されるため、それ以上前を走っている列車がなく、探索空間は狭い範囲に制約される。
２回目以降の探索では、前回までの探索により、すでに評価値が計算されたノードが前方に存在していて、これにより探索空間は狭い範囲に制約される。評価値がすでに計算されているノードであっても、後の探索により評価値が更新される可能性はあるが、後の探索は、目的駅に、より後に到着する所要時間の長い経路であるため、評価値が更新されるのは、リンクコストの設定が単純ではない例外的な場合のみである。
したがって、全体のグラフ構造をたかだか１回程度探索することで、全ての目的駅到達可能ノードに対して評価値を計算することができる。これは、単純にダイクストラ法を目的駅到着ノード側から逆向きに適用して評価値を計算した場合に比べると、計算量を縮減できるということである。
【００２６】
逆方向探索が完了した後、さらに探索装置４が続けて順方向探索を行って経路を確定させる。
図１１に順方向探索による経路確定のフローチャートを、図１２にその一部である再帰処理の部分のフローチャートを示す。
図１１では、出発駅の各出発ノードから目的駅の到着ノードへ向かって探索を行うので、処理を開始する（ステップＳ２０１）と、まず、出発駅の出発ノードのうち、最初のものを選択する（ステップＳ２０２）。後で確定した経路を取り出すために、どのようなノードを経由して探索したかを、図１３に示すようなスタック構造に保存しておく。スタック構造の一番下（最初に入れたデータ）が出発駅の出発ノードのＩＤとなり、以後、順に経由したノードのＩＤを保存していき、最後に目的駅に着いた時に、目的駅到着ノードのＩＤが一番上に入っているようにする。このために、まず出発駅出発ノードのＩＤをスタック構造に保存する（ステップＳ２０３）。
ここで、図１２の再帰処理を開始する（ステップＳ２０４）。
【００２７】
ここで、図１２の再帰処理について説明する。
図１２で、再帰処理を開始した時点で出発ノードが選択されているので、ここから走行リンクをたどって、次の駅の到着ノードを選択する（ステップＳ３０２）。この到着ノードと前の出発ノードとの評価値の差が、その間の走行リンクの重みに等しいかどうかチェックし（ステップＳ３０３）、等しくなければ、このリンクは、最短経路上にはないので、再帰処理を中断して戻る（ステップＳ３０４）。等しければ、このリンクが最短経路上にあるので、選択されている到着ノードのＩＤをスタックに積む（ステップＳ３０５）。
ここで、目的駅に到着したかどうかを調べ（ステップＳ３０６）、到着していれば、スタックの情報を元に経路情報を作成して探索結果記憶装置６に出力する（ステップＳ３０７）。経路情報は、どこの駅からどこの駅まで、どの列車を利用して移動したかを記録しているもので、後で列車の混雑情報などを計算するのに用いる。経路情報の出力が行われた後、スタックから１つノードＩＤを取り出してから（ステップＳ３０８）、再帰処理を脱出する（ステップＳ３０９）。
【００２８】
目的駅に到着していなければ、その到着ノードから停車リンクをたどって、次の出発ノードを選択する（ステップＳ３１０）。この出発ノードと到着ノードとの評価値の差が停車リンクの重みに等しければ（ステップＳ３１１）、出発ノードＩＤをスタックに積み（ステップＳ３１２）、再帰処理を行う（ステップＳ３１３）。再帰処理から復帰すると、出発ノードＩＤをスタックから取り除く（ステップＳ３１４）。
ステップＳ３１１で、評価値の差が停車リンクの重みと等しくなかった場合と、ステップＳ３１４を終えた後に、さらにこの駅で可能な乗換先列車全てに対して乗換の探索を行う（ステップＳ３１５〜Ｓ３２１）。ただし探索順序は、乗換先列車の出発時刻が早いものからとする。
この乗換の探索では、乗換先の列車の出発ノードを選択し（ステップＳ３１６）、この出発ノードと乗換元の到着ノードとの評価値の差が乗換リンクの重みに等しければ（ステップＳ３１７）、出発ノードのＩＤをスタックに積んでから（ステップＳ３１８）、出発ノードから再帰処理を実施する（ステップＳ３１９）。
再帰処理から戻ると、スタックからＩＤを１つ取り出し（ステップＳ３２０）、次のループ（ステップＳ３１５〜Ｓ３２１）を実行する。
ステップＳ３１７で、評価値の差がリンクの重みと等しくなければ、ループを脱出し、ステップＳ３０５で積んだ到着ノードのＩＤをスタックから取り出した上で（ステップＳ３２２）、再帰処理を終了する（ステップＳ３２３）。
【００２９】
図１１に戻って、スタックから出発ノードのＩＤを取り出して（ステップＳ２０５）、次の出発ノードからの探索を開始する。次の出発ノードがなければ（ステップＳ２０６）、処理を終了し（ステップＳ２０８）、あれば、次の出発ノードを選択して（ステップＳ２０７）、ステップ２０３に行く。
その出発駅の出発ノード全てに対して探索を繰り返すと、この出発駅−目的駅の間の移動経路全てが出力されることになる。
【００３０】
順方向探索は、逆方向探索によって、各ノードに割り当てられた評価値によって、分岐の探索を進めるかどうかを決定するため、最短経路となる可能性がない分岐を全く探索することがなく、単純なダイクストラ法による探索に比べて、ずっと高速に探索を行うことができる。
逆方向探索による最適評価値割り当ても、順方向探索による経路の作成も、探索装置４によって行われ、その結果の最適経路は、探索結果記憶装置６に記憶される。
【００３１】
出発駅における出発時刻が与えられると、乗車することができる列車は、その時刻以降にその駅を出発する列車であるから、探索結果記憶装置６に記憶されている出発駅−目的駅の間の全ての移動経路の中で最適な経路は、与えられた出発時刻以降で最初に出発する経路となる。
このようにして、探索条件入力装置３から与えられた探索条件に最適な経路を探索結果出力装置７から得ることが可能となる。
また、この実施の形態１では、鉄道を例に説明したが、バスや船舶、航空機など、決まった地点で積載物の積み込み、積み下ろしをして運行計画が時間に基づいて定められているような交通機関や物流システム等においても適用可能であり、これらを本発明の範囲から排除するものではない。
【００３２】
実施の形態１によれば、乗客の行動経路を探索する時に、各探索箇所から目的地または出発地までの最良の評価値が、予め、目的駅側から行われる予備的な探索によって計算して与えてあることによって、それに基づいて効率よく出発駅側からの探索の枝刈りをすることができ、それによって従来のダイクストラ法に基づく探索と同じ結果を、ダイクストラ法に基づく探索に比べて著しく短い探索時間で得ることができる。
【００３３】
実施の形態２．
実施の形態１では、出発駅にある時刻に現れて目的駅へ移動する最適経路を考える乗客について述べたが、逆に目的駅へ到着したい時刻を定めて、そこから逆算して出発駅に現れる乗客も存在する。実施の形態２は、この乗客のような場合についてのものである。
【００３４】
目的駅に到着する時刻を定めて、それに間に合う最適な経路を探索する方法は、実施の形態１で、説明した方法を逆に適用することで全く同様に行える。
実施の形態２では、図１の最適経路探索システムのうち、探索条件入力装置３が出発駅、目的駅、目的駅での到着時刻を入力するものとなり、グラフ構造作成装置２が図２のグラフ構造のリンクを逆向きに張るものとなり、探索装置４が出発駅から各ノードまでの最短距離のリンクの重みの合計である評価値を、予め各ノードに割り当てて、この後に目的駅側からの探索を行うようにする。
これにより、目的駅での時刻を定めた最適経路探索が可能となる。これは特に、目的駅付近で大規模なイベントがあるような場合などに有効である。
【００３５】
実施の形態２によれば、最初に出発駅側からの探索により、各ノードに評価値を与えておき、その後、目的駅側から探索することにより、目的地到着時刻を定めて出発地に現れる利用者の出発地から目的地までの最適経路探索を行うときに最短経路とならない分岐を見分けることができるため、探索を枝刈りして効率よく探索することができる。
【００３６】
実施の形態３．
図１４は、この発明の実施の形態３による最適経路探索システムの乗換障壁の影響を説明する図である。
図１４において、最適経路の評価値を各ノードに割当てる探索を行うときに、乗換障壁のために、乗換元列車１では評価値更新ができると共に、乗換元列車２では評価値更新ができない。
図１５は、この発明の実施の形態３による最適経路探索システムの評価値格納領域を二つずつ用意する理由を説明する図である。
図１５において、Ａ列車とＢ列車の目的駅到着ノードまでの各ノードの評価値が示されている。Ａ列車は出発駅から出発し、Ｂ列車は途中駅１から出発するが、出発ノード間の評価値更新を行うと、Ａ列車の途中駅１出発ノードでは、乗換障壁が考慮されない評価値が設定されるので、正しく探索を行うことができなくなる。このため、各ノードに対して出発時用と途中用の二つの評価値が必要になる。
【００３７】
実施の形態３では、実施の形態１または実施の形態２に示した最適経路探索システムに、さらに乗換障壁のような情報を付け加えて探索を行う時に、正確に最適経路を求める方法についてのものである。
ここで、乗換障壁とは、乗換を乗客がどの程度嫌がるかを表した値であり、この例では、乗換障壁を時間に換算して表し、１回の乗換は、その乗換障壁の時間だけ所要時間が長くなるのと同等であるとみなして取り扱う。各乗換がどの程度の乗換障壁に相当するかは、各駅の条件などによって予め定められているものとする。
【００３８】
乗換障壁を反映して最適経路探索を行うためには、図２の乗換リンクに対して、所要時間にさらに乗換障壁の値を加えなければならない。乗換リンクのコストが正しく設定されると、実施の形態１または実施の形態２の最適経路探索システムにより、乗換障壁を反映した最適経路が求められる。
ただし、図７及び図１２における乗換列車を探すループの脱出条件を変更する必要がある。
図７においては、乗換元列車のノードの評価値を更新できなくなった時にループを脱出し、図１２においては、乗換先列車のノードと乗換元列車のノードとの評価値の差が、乗換リンクの重みと等しくなくなった時にループを脱出している。これは、出発時間や到着時間の差と評価する順番の関係から、それより先を探索しても乗換ができる可能性はないということを利用したものである。
【００３９】
しかし、実施の形態３では、乗換障壁が設定されていることによって、乗換可能な列車の順番が入れ替わることがある。これについて、図１４を用いて説明する。
図７の最適経路の評価値を各ノードに割り当てる探索を行っているとき、ある乗換先列車のノードの評価値が１０で、乗換元列車１（先着）と乗換元列車２（後着）のノードの評価値が共に２２であるとする。図７のフローチャートに従えば、後着列車から順番に探索するから、乗換元列車２と乗換先列車の間の乗換リンクの重みとの比較により評価値が更新できない。しかし、乗換元列車１と乗換元列車２では、乗換先列車に対する乗換障壁が大きく異なるため、到着時刻の差が乗換障壁の差より小さければ、図１４のように先着列車へは評価値更新可能となることがある。
このことを考慮して、実施の形態３での乗換を探索するループは、図７及び図１２におけるループ脱出条件を満たしてから、さらに最大乗換障壁時間だけ余計に探索をしなければ完全ではない。
【００４０】
また、乗換障壁を導入する場合には、各ノードの評価値を１つのノードにつき２つずつ記憶できるようにして使い分ける必要がある。この理由を図１５により説明する。
図１５では、Ａ列車とＢ列車の２本の列車が運行されていて、各駅間の走行リンクの重みが共に４、駅の停車リンクの重みを２とし、列車間の時間間隔を８、乗換障壁をすべて１とすると、図７のフローチャートのステップＳ１０６〜Ｓ１０８の出発ノード間の評価値更新を考慮しなければ、各ノードの評価値は、図１５のようになる。
ところが、出発ノード間の評価値更新を考慮すると、Ｂ列車の途中駅１出発ノードからＡ列車の途中駅１出発ノードの評価値が更新されて、Ａ列車の途中駅１出発ノードの評価値は１７から１６になる。
この１の差は、出発ノード間の評価値更新では、乗換障壁が考慮されないためである。出発ノード間の評価値更新で乗換障壁を考慮しないことは、途中駅１が本来の出発駅であった場合は、Ａ列車に乗らずＢ列車に乗るということは、乗換ではないため正しい。しかし、図１５のように、さらに手前の駅が出発駅であった場合、Ａ列車の途中駅１出発ノードの評価値が更新されてしまうことによって、Ａ列車の最短経路上のノード間の評価値の差がその間のリンクの重みと等しくなくなり、後で経路探索を行うことができなくなってしまう。
【００４１】
出発ノード間の評価値更新をした時に、さらに再帰的にＡ列車の途中駅１到着ノードの評価値更新を行うようにすると、Ａ列車の途中駅１到着ノードにＡ列車からＢ列車へ乗換障壁なしで乗り換えたときの評価値が設定されてしまうため、これも問題となる。
出発ノード間の評価値更新をした値が必要になるのは、その駅が出発駅であった場合だけであるので、ノード毎に途中用の評価値と出発時用の評価値の２つを持たせておき、通常は両方の評価値を全く同じに更新していくが、出発ノード間の評価値更新についてだけは、出発時用の評価値に対してのみ行うようにすると、この問題を解決できる。後で、経路探索を行うときには、出発駅でのみ出発時用の評価値を参照し、後は通常用の評価値を参照してたどると、正しく探索が行える。
【００４２】
この問題が発生するのは、乗換障壁があるためであるので、乗換障壁を全く考慮しないという場合には、評価値領域を２つずつ用意する必要は無い。また、評価値が更新された場合、通常はそのノードからさらに再帰的に探索するが、乗換障壁が考慮されない評価値が伝播することを防ぐために、出発ノード間の評価値更新の場合は、さらにその先まで再帰的に探索を行うことはしない。
このようにすることで、乗換障壁を考慮したより、実態に即した探索を行うことが可能となる。この例では鉄道旅客の乗換に余計なコストを加算する例を示したが、物流網においてトラック間での荷物の積み替えのような場合も、同様にして積み替えの少なくなる経路を探索することが可能となる。
【００４３】
実施の形態３によれば、この構成により、リンクの重み付けに乗換障壁を含めて考えている場合に、同一経由点の別のノードを経由して出発する場合を考慮した探索をすると、その経由点が途中経由点であった場合に正しく探索されなくなる問題を回避して、正しく探索を行うことができる。
【００４４】
実施の形態４．
実施の形態４は、実施の形態１〜実施の形態３に示した最適経路探索システムを利用した運行計画作成システムについてのものである。
図１６は、この発明の実施の形態４による運行計画作成システムを示す全体構成図である。
図１６において、１、２、４〜６は図１におけるものと同一のものである。運行計画入力装置８は、運行計画を入力する。運行計画編集装置９は、運行計画入力装置８からの入力を受けて、運行計画記憶装置１に記憶されている現状の運行計画に対する変更・追加などの処理を行う。運行計画表示装置１０は、現在の運行計画をダイヤ図・グラフ・表その他の形式で表示する。輸送需要記憶装置１１は、乗客需要のデータを記憶する。運行計画評価装置１２は、探索結果記憶装置６の記憶内容に基き、各乗客の所要時間や乗換回数、各列車の混雑度などにより運行計画を評価する。評価結果表示装置１３は、運行計画評価装置１２によって評価された運行計画の評価結果を表示する。
【００４５】
次に、動作について説明する。
運行計画作成システムでは、通常、運行計画入力装置８からの入力を受けて、運行計画記憶装置１に記憶されている現状の運行計画に対する変更・追加などの処理を運行計画編集装置９で行って、運行計画記憶装置１に書き込み、現在の運行計画を、運行計画表示装置１０でダイヤ図・グラフ・表その他の形式で表示して、それを参考にさらに入力を行う、という形で運行計画の作成が進められる。
これに対して、現在計画中の運行計画を実行した時の乗客の所要時間や乗換回数などの評価を行うためには、乗客の行動経路を推定する必要があり、これに最適経路探索システムを利用することができる。
【００４６】
実施の形態１〜実施の形態３では、ある目的駅または出発駅に対しての最適経路を求めるが、これを任意の駅間について全て求めた上で、各駅間の乗客需要のデータを合わせることで、各経路の乗客数を推定することができる。
例えば、自動改札から収集される入場時刻と出発駅、目的駅の情報の組み合わせがあれば、出発駅と目的駅の間の最短経路の中から、入場時刻以降に最初に出発駅を出発する経路を選択すると考えることができるので、目的駅までの利用列車・乗換駅と目的駅到着時刻を推定することができる。
また、ＯＤ表と呼ばれる出発駅と目的駅のマトリクス上に各駅間の移動乗客数を記載した表があれば、その対象とする時間の長さで割ることで、単位時間当たりの駅間乗客需要を求めることができる。
【００４７】
都市鉄道における大半の乗客のように、時刻表を気にせず出発駅に均一に乗客が現れるという仮定の元では、前にその駅を出発した経路と次にその駅を出発する経路の時間間隔に比例して、次の経路の利用乗客が決まると考えられるので、単位時間当たり駅間乗客需要の値に経路間の時間間隔を掛けることで、各経路の乗客数を推定することができる。
自動改札の入場情報を利用する方法でも、ＯＤ表を利用する方法でも、仮に同時刻に出発して途中の利用列車や乗換駅が異なる複数の経路が、同一の評価値で存在していた場合には、計画の評価をする目的では、個別の乗客の移動経路を推定する必要はなく、全体の傾向を推定できれば十分であるため、それらを按分して乗客配分をすればよい。
【００４８】
各経路を何人の乗客が利用したかが推定できれば、利用列車ごとに乗客数を積算することによって、各列車の区間ごとの乗客数や各駅での乗降客数など様々な統計情報を推定することができる。こうした統計情報は、従来実際に実行したダイヤにおける結果を実測することができるだけであったが、本発明に基づく最適経路探索システムを使うことによって、まだ実行していないダイヤに対して、このような統計情報を推定して求めることができるようになる。
図１６のように、グラフ構造作成装置２の入力として、現在の運行計画を運行計画記憶装置１から取得して、グラフ構造記憶装置５にグラフ構造を作成し、乗客需要のデータを輸送需要記憶装置１１から取得して、探索装置４により探索を実行することで、全体の最適経路を探索結果記憶装置６に得ることができ、乗客流動を推定することができる。
この情報を各乗客の所要時間や乗換回数、各列車の混雑度などを評価する運行計画評価装置１２に与えることで、運行計画の評価が求まり、評価結果表示装置１３に出力される。この出力結果を参考にしながら、これを改善するように、運行計画の変更を繰り返すことにより、運行計画を利用客にとって、よりよいものにすることが可能となる。
【００４９】
実施の形態４によれば、最適経路探索システムを運行計画作成システムに適用することにより、運行計画の立案を行う担当者は、利用者の立場からの評価を考慮しながら作業を行うことができ、利用者にとって利便性の高い運行計画作成を行うことができる。
【００５０】
実施の形態５．
実施の形態５は、実施の形態１〜実施の形態３に示した最適経路探索システムを利用した運行管理支援システムについてのものである。
図１７は、この発明の実施の形態５による運行管理支援システムを示す全体構成図である。
図１７において、１、２、４〜６、８、１１〜１３は図１６におけるものと同一のものである。運行状況把握装置１５は、管理対象である輸送システム１４から、各列車等の位置や速度などの現在の運行の状況を取得する。運行計画変更装置１６は、運行計画を変更し、輸送システムに変更された運行計画を実行させる。運行状況予測装置１７は、現在の運行状況及び運行計画入力装置により入力された運行計画の変更に基き、将来の運行状況を予測する。運行計画記憶装置１には、現状の運行状況及び将来の運行状況予測の情報が記憶される。運行状況表示装置１８は、運行計画記憶装置１に記憶された将来の運行状況を表示する。
【００５１】
次に、動作について説明する。
運行管理支援システムでは、管理対象としている輸送システム１４から運行状況把握装置１５により各列車等の位置や速度などの現在の運行状況が取得され、運行計画記憶装置１に格納される。運行計画入力装置８から入力された運行計画の変更と、運行計画記憶装置１に格納されている輸送システムの現在の運行状況とから、運行状況予測装置１７により将来の運行状況を予測した上で、運行状況表示装置１８に出力する。
そして、出力結果が望みのものであれば、運行計画の変更の指示を実際の輸送システム１４に運行計画変更装置１６を通して送り出し、実行され、望みのものでなければ、さらに繰り返し入力を行って運行計画の変更を続けるという方法で運行管理が行われる。
【００５２】
この中で、本発明の最適経路探索システムを利用した運行計画の評価を行うために、運行計画記憶装置１に記憶されている現在の運行状況及び将来の運行状況の予測情報から、グラフ構造作成装置２によりグラフ構造記憶装置５にグラフ構造を作成し、輸送需要記憶装置１１に格納されている輸送需要の各乗客の情報とから、探索装置４により、各乗客の最適経路を求めて探索結果記憶装置６に記憶し、運行計画評価装置１２で評価を行って、その結果を評価結果表示装置１３に出力する。
この出力された結果を見ながら、運行計画の変更を考えることにより、より利用客の利便性に配慮した運行管理を行うことが可能になる。
【００５３】
実施の形態５によれば、最適経路探索システムを利用した運行管理支援システムとすることにより、運行管理の際に利用者の立場からの評価を考慮しながら作業を行うことができ、利用者にとって利便性の高い運行管理を行うことができる。
【００５４】
実施の形態６．
実施の形態６では、実施の形態５に示した運行管理支援システムに、さらに最適経路探索の入力として、実際の利用状況を与えるようにしたものである。
図１８は、この発明の実施の形態６による運行管理支援システムを示す全体構成図である。
図１８において、１、２、４〜６、８、１１〜１８は図１７におけるものと同一のものである。図１８では、輸送需要を随時把握できる輸送需要把握装置１９が設けられている。
【００５５】
実施の形態６でも、運行計画変更を行う仕組みは、実施の形態５と同じであるが、実施の形態６では、輸送需要の把握に関する部分が追加されている。
最近の輸送システムでは、例えば鉄道では、自動改札機などの乗客の数を自動的に数えることのできる装置が多く用いられており、こうした輸送需要を随時把握できる装置を利用すると、事前の輸送需要の予測や過去の統計に頼るよりも正確に把握することが可能である。
このため、輸送需要把握装置１９を置いて、これにより把握された情報と過去の統計情報などを合わせて考慮した上で、探索装置４を実行することで、より正確な運行計画の評価を行なうことが可能となる。
【００５６】
実施の形態６によれば、輸送需要把握装置により輸送需要を把握するようにしたので、運行管理の際に利用者の流動情報をより正確に把握して作業を行うことができる。
【００５７】
なお、上記実施の形態１〜実施の形態６の説明では、列車に搭乗する乗客の最適経路探索として説明したが、一般に、移動体に積載される積載物の最適経路探索としても同じである。
【図面の簡単な説明】
【００５８】
【図１】この発明の実施の形態１による最適経路探索システムを示す全体構成図である。
【図２】この発明の実施の形態１による最適経路探索システムの乗客流動をグラフ構造で示す概念図である。
【図３】この発明の実施の形態１による最適経路探索システムの乗客流動の簡略化したグラフ構造を示す図である。
【図４】図３に対応するデータ構造を示す図である。
【図５】この発明の実施の形態１による最適経路探索システムの予め計算した各ノードの最短経路評価値を示す図である。
【図６】この発明の実施の形態１による最適経路探索システムの探索装置によって実行される目的駅側からの逆方向の探索を示すフローチャートである。
【図７】この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索での再帰処理を示すフローチャートである。
【図８】この発明の実施の形態１による最適経路探索システムの目的駅側からの逆方向の探索を行うときの途中経過を示す図である。
【図９】この発明の実施の形態１による最適経路探索システムの追い抜き関係にある場合の評価値の更新を示す図である。
【図１０】この発明の実施の形態１による最適経路探索システムの逆方向探索終了後のノードの状態を示す図である。
【図１１】この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索を示すフローチャートである。
【図１２】この発明の実施の形態１による最適経路探索システムの出発駅側からの経路探索での再帰処理を示すフローチャートである。
【図１３】この発明の実施の形態１による最適経路探索システムのスタック構造を示す図である。
【図１４】この発明の実施の形態３による最適経路探索システムの乗換障壁の影響を説明する図である。
【図１５】この発明の実施の形態３による最適経路探索システムの評価値格納領域を二つずつ用意する理由を説明する図である。
【図１６】この発明の実施の形態４による運行計画作成システムを示す全体構成図である。
【図１７】この発明の実施の形態５による運行管理支援システムを示す全体構成図である。
【図１８】この発明の実施の形態６による運行管理支援システムを示す全体構成図である。
【符号の説明】
【００５９】
１ 運行計画記憶装置
２ グラフ構造作成装置
３ 探索条件入力装置
４ 探索装置
５ グラフ構造記憶装置
６ 探索結果記憶装置
７ 探索結果出力装置
８ 運行計画入力装置
９ 運行計画編集装置
１０ 運行計画表示装置
１１ 輸送需要記憶装置
１２ 運行計画評価装置
１３ 評価結果表示装置
１４ 輸送システム
１５ 運行状況把握装置
１６ 運行計画変更装置
１７ 運行状況予測装置
１８ 運行状況表示装置
１９ 輸送需要把握装置
【特許請求の範囲】
【請求項１】
時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの上記移動体の積載物の移動経路を探索する最適経路探索システムにおいて、上記積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、上記運行計画を記憶する運行計画記憶装置、上記移動体の上記出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、上記ノード間の経過をリンクとして表現し、上記リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、上記運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成された上記グラフ構造を利用して、上記積載物の出発点から到着点への最適経路を探索する探索装置、及び上記探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
上記探索装置は、上記探索条件入力装置により入力された上記積載物の到着点から出発点に向う逆方向に、各経由点のノードから上記到着点までの最短経路の上記リンクの重みを合計し、上記各ノードに評価値として割当てた後、上記積載物の出発点及び出発点での出発時刻に基き、上記出発点から到着点までの順方向に、上記各ノードに割当てられた評価値及び上記リンクの重み付けの値により上記各経由点を選択することにより、上記積載物の出発点から到着点までの最適経路を探索することを特徴とする最適経路探索システム。
【請求項２】
時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの上記移動体の積載物の移動経路を探索する最適経路探索システムにおいて、上記積載物の出発点と到着点と上記到着点における到着時刻とを入力する探索条件入力装置、上記運行計画を記憶する運行計画記憶装置、上記移動体の上記出発点での出発時刻及び上記到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、上記ノード間の経過をリンクとして表現し、上記リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、上記運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成された上記グラフ構造を利用して、上記積載物の出発点から到着点への最適経路を探索する探索装置、及び上記探索装置により探索された最適経路を出力する探索結果出力装置を備え、
上記探索装置は、上記探索条件入力装置により入力された上記積載物の出発点から到着点に向う順方向に、上記出発点から各経由点のノードまでの最短経路の上記リンクの重みを合計し、上記各ノードに評価値として割当てた後、上記積載物の到着点及び到着点での到着時刻に基き、上記到着点から出発点までの逆方向に、上記各ノードに割当てられた評価値及び上記リンクの重み付けの値により上記各経由点を選択することにより、上記積載物の出発点から到着点までの最適経路を探索することを特徴とする最適経路探索システム。
【請求項３】
上記経由点で乗換が行われる場合には、上記リンクの重み付けの値に乗換障壁が加算され、上記経由点のノードには、上記乗換障壁が加算されない上記評価値と、上記乗換障壁が加算された上記評価値の二つの評価値が割り当てられ、上記二つの評価値は、使い分けられることを特徴とする請求項１または請求項２記載の最適経路探索システム。
【請求項４】
請求項１〜請求項３のいずれかに記載の最適経路探索システム、運行計画または運行計画の変更を入力する運行計画入力装置、この運行計画入力装置により入力された運行計画または運行計画の変更と上記運行計画記憶装置に記憶された運行計画とに基き、新たな運行計画を作成し、上記運行計画記憶装置に記憶させる運行計画編集装置、上記輸送システムの輸送需要情報を格納する輸送需要記憶装置、上記最適経路探索システムによって求められた各積載物の最適経路を基に、上記運行計画記憶装置に記憶されている運行計画を評価する運行計画評価装置、及びこの運行計画評価装置による運行計画の評価を表示する評価結果表示装置を備え、
上記最適経路探索システムは、上記輸送需要記憶装置に記憶された輸送需要情報の各積載物情報及び上記運行計画記憶装置に記憶されている運行計画に基き、上記各積載物の最適経路を探索することを特徴とする運行計画作成システム。
【請求項５】
請求項１〜請求項３のいずれかに記載の最適経路探索システム、運行計画の変更を入力する運行計画入力装置、上記輸送システムにおける現在の運行状況を取得する運行状況把握装置、この運行状況把握装置により取得された上記現在の運行状況及び上記運行計画入力装置により入力された運行計画の変更に基き、将来の運行状況を予測し、上記運行計画記憶装置に記憶する運行状況予測装置、上記輸送システムの輸送需要情報を格納する輸送需要記憶装置、上記最適経路探索システムによって求められた各積載物の最適経路を基に、上記運行計画記憶装置に記憶された上記将来の運行状況を評価する運行計画評価装置、この運行計画評価装置による上記将来の運行状況の評価を表示する評価結果表示装置、及びこの評価結果表示装置により表示された上記将来の運行状況の評価が確認されたとき、上記運行計画入力装置により入力された運行計画の変更を上記輸送システムに伝達して実行させる運行計画変更装置を備え、
上記最適経路探索システムは、上記輸送需要記憶装置に記憶された輸送需要情報の各積載物情報及び上記運行計画記憶装置に記憶されている上記将来の運行状況に基き、上記各積載物の最適経路を探索することを特徴とする運行管理支援システム。
【請求項６】
上記輸送システムにおける上記各積載物情報を含む輸送需要を取得する輸送需要把握装置を備え、
上記最適経路探索システムは、上記輸送需要把握装置により取得された輸送需要の各積載物情報を用いて、上記各積載物の最適経路を探索することを特徴とする請求項５記載の運行管理支援システム。
【請求項１】
時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの上記移動体の積載物の移動経路を探索する最適経路探索システムにおいて、上記積載物の出発点と到着点と出発点における出発時刻とを入力する探索条件入力装置、上記運行計画を記憶する運行計画記憶装置、上記移動体の上記出発点での出発時刻及び到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、上記ノード間の経過をリンクとして表現し、上記リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、上記運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成された上記グラフ構造を利用して、上記積載物の出発点から到着点への最適経路を探索する探索装置、及び上記探索装置による探索の結果である最適経路を出力する探索結果出力装置を備え、
上記探索装置は、上記探索条件入力装置により入力された上記積載物の到着点から出発点に向う逆方向に、各経由点のノードから上記到着点までの最短経路の上記リンクの重みを合計し、上記各ノードに評価値として割当てた後、上記積載物の出発点及び出発点での出発時刻に基き、上記出発点から到着点までの順方向に、上記各ノードに割当てられた評価値及び上記リンクの重み付けの値により上記各経由点を選択することにより、上記積載物の出発点から到着点までの最適経路を探索することを特徴とする最適経路探索システム。
【請求項２】
時刻に基き移動体を運行させる運行計画が予め定められている輸送システムでの上記移動体の積載物の移動経路を探索する最適経路探索システムにおいて、上記積載物の出発点と到着点と上記到着点における到着時刻とを入力する探索条件入力装置、上記運行計画を記憶する運行計画記憶装置、上記移動体の上記出発点での出発時刻及び上記到着点での到着時刻並びに各経由点での到着時刻及び出発時刻をノードとし、上記ノード間の経過をリンクとして表現し、上記リンクにはそのリンクの利用のしやすさを示す重み付けの値を与えたグラフ構造を、上記運行計画記憶装置に記憶された運行計画に基き、作成するグラフ構造作成装置、このグラフ構造作成装置により作成された上記グラフ構造を利用して、上記積載物の出発点から到着点への最適経路を探索する探索装置、及び上記探索装置により探索された最適経路を出力する探索結果出力装置を備え、
上記探索装置は、上記探索条件入力装置により入力された上記積載物の出発点から到着点に向う順方向に、上記出発点から各経由点のノードまでの最短経路の上記リンクの重みを合計し、上記各ノードに評価値として割当てた後、上記積載物の到着点及び到着点での到着時刻に基き、上記到着点から出発点までの逆方向に、上記各ノードに割当てられた評価値及び上記リンクの重み付けの値により上記各経由点を選択することにより、上記積載物の出発点から到着点までの最適経路を探索することを特徴とする最適経路探索システム。
【請求項３】
上記経由点で乗換が行われる場合には、上記リンクの重み付けの値に乗換障壁が加算され、上記経由点のノードには、上記乗換障壁が加算されない上記評価値と、上記乗換障壁が加算された上記評価値の二つの評価値が割り当てられ、上記二つの評価値は、使い分けられることを特徴とする請求項１または請求項２記載の最適経路探索システム。
【請求項４】
請求項１〜請求項３のいずれかに記載の最適経路探索システム、運行計画または運行計画の変更を入力する運行計画入力装置、この運行計画入力装置により入力された運行計画または運行計画の変更と上記運行計画記憶装置に記憶された運行計画とに基き、新たな運行計画を作成し、上記運行計画記憶装置に記憶させる運行計画編集装置、上記輸送システムの輸送需要情報を格納する輸送需要記憶装置、上記最適経路探索システムによって求められた各積載物の最適経路を基に、上記運行計画記憶装置に記憶されている運行計画を評価する運行計画評価装置、及びこの運行計画評価装置による運行計画の評価を表示する評価結果表示装置を備え、
上記最適経路探索システムは、上記輸送需要記憶装置に記憶された輸送需要情報の各積載物情報及び上記運行計画記憶装置に記憶されている運行計画に基き、上記各積載物の最適経路を探索することを特徴とする運行計画作成システム。
【請求項５】
請求項１〜請求項３のいずれかに記載の最適経路探索システム、運行計画の変更を入力する運行計画入力装置、上記輸送システムにおける現在の運行状況を取得する運行状況把握装置、この運行状況把握装置により取得された上記現在の運行状況及び上記運行計画入力装置により入力された運行計画の変更に基き、将来の運行状況を予測し、上記運行計画記憶装置に記憶する運行状況予測装置、上記輸送システムの輸送需要情報を格納する輸送需要記憶装置、上記最適経路探索システムによって求められた各積載物の最適経路を基に、上記運行計画記憶装置に記憶された上記将来の運行状況を評価する運行計画評価装置、この運行計画評価装置による上記将来の運行状況の評価を表示する評価結果表示装置、及びこの評価結果表示装置により表示された上記将来の運行状況の評価が確認されたとき、上記運行計画入力装置により入力された運行計画の変更を上記輸送システムに伝達して実行させる運行計画変更装置を備え、
上記最適経路探索システムは、上記輸送需要記憶装置に記憶された輸送需要情報の各積載物情報及び上記運行計画記憶装置に記憶されている上記将来の運行状況に基き、上記各積載物の最適経路を探索することを特徴とする運行管理支援システム。
【請求項６】
上記輸送システムにおける上記各積載物情報を含む輸送需要を取得する輸送需要把握装置を備え、
上記最適経路探索システムは、上記輸送需要把握装置により取得された輸送需要の各積載物情報を用いて、上記各積載物の最適経路を探索することを特徴とする請求項５記載の運行管理支援システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００７−２２４３０（Ｐ２００７−２２４３０Ａ）
【公開日】平成１９年２月１日（２００７．２．１）
【国際特許分類】
【出願番号】特願２００５−２１００１６（Ｐ２００５−２１００１６）
【出願日】平成１７年７月２０日（２００５．７．２０）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成１９年２月１日（２００７．２．１）
【国際特許分類】
【出願日】平成１７年７月２０日（２００５．７．２０）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]