経路探索装置、経路探索方法、経路探索プログラムおよび地図データ
【課題】歩行者のために好適な経路を探索することが可能な経路探索装置、経路探索方法、経路探索プログラムおよび地図データを提供する。
【解決手段】経路案内サーバ３０は、歩行路を表すリンクデータと、リンクの端点を示すノードデータと、リンクの種別を示すリンク種別データと、リンクコストデータとを含む地図データが格納される地図情報記憶部３７と、出発地から目的地までの経路に含まれるリンクコストデータから合計コストを演算して最適経路を探索する最適経路探索部３４０と、最適経路探索部３４０が探索した最適経路にリンク種別データとしてリンクを通行するための所要時間が不確定な横断リンクが含まれる場合に、横断リンクのリンクコストを、待ち時間なしコストデータから待ち時間ありコストデータに変更して、一以上の他の経路を最適経路探索部３４０に探索させ、最適経路と共に一以上の他の経路を経路候補とする再探索部３４１とを備えている。
【解決手段】経路案内サーバ３０は、歩行路を表すリンクデータと、リンクの端点を示すノードデータと、リンクの種別を示すリンク種別データと、リンクコストデータとを含む地図データが格納される地図情報記憶部３７と、出発地から目的地までの経路に含まれるリンクコストデータから合計コストを演算して最適経路を探索する最適経路探索部３４０と、最適経路探索部３４０が探索した最適経路にリンク種別データとしてリンクを通行するための所要時間が不確定な横断リンクが含まれる場合に、横断リンクのリンクコストを、待ち時間なしコストデータから待ち時間ありコストデータに変更して、一以上の他の経路を最適経路探索部３４０に探索させ、最適経路と共に一以上の他の経路を経路候補とする再探索部３４１とを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、歩行者が出発地から目的地までを歩く際に、好適な経路を探索することが可能な経路探索装置、経路探索方法、経路探索プログラムおよび地図データに関する。
【背景技術】
【０００２】
地図上の経路を探索することで、出発地から目的地までを短時間で到達することが可能な経路探索装置が知られている。
例えば、特許文献１には、地図データや公共交通機関に関するデータに基づいて、距離コストを道路種別に応じて設定された車速で除算することで車両経路のコストを時間単位とすると共に、駅間の所要時間や待ち時間を加算することで公共交通機関経路のコストも時間単位とし、車両経路と公共交通機関経路との比較を可能とする経路案内装置が記載されている。
【０００３】
特許文献１の経路案内装置では、公共交通機関経路のコストを時間単位で算出するためのデータとして、時刻表データや周辺データなどを用いている。周辺データとは、公共交通機関が鉄道の場合では、各駅の構内施設に関するデータであり、乗り換えに必要な階段の有無やエスカレータ、エレベータの有無、駅の出入口からプラットホームまでの所要時間を示すデータである。これらは、鉄道を利用するときの容易度を評価する際の基準となるもので、例えば、乗り換えに必要な階段数が増大すればするほどコストとしては増大するように設定されている。また、エレベータやエスカレータの数が多ければ多いほど、利用の容易度は大きくなりコストとしては低下するように設定されている。
【０００４】
【特許文献１】特開２００１−１６５６８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の経路案内装置では、出発地から目的地までの移動が車両だけでなく公共交通機関を利用する場合が考慮されている。公共交通機関を利用する場合に考慮されるコストは、時刻表データや駅の構内施設に関する周辺データなどから、駅での待ち時間や乗り換え時間などの待ち時間を演算することで決定されるので、現在時刻がわかれば固定的に目的地までのコストを演算することができる。
しかし、出発地から目的地までを徒歩で移動する場合には、車両や公共交通機関とは異なる考慮が必要である。
【０００６】
例えば、横断歩道が設置された道幅の広い通りを横切ることが、案内された目的地までの最適経路である場合には、歩行者用信号機の赤信号に遭遇してしまえば、すぐには横断できないことがある。通りが交通量の多い大通りであれば赤信号が長く、多大な時間の損失が発生する。そうなると、その横断歩道を渡ることが最適経路であったとしても、迂回した方が早く目的地まで到着できることがあり、歩行者にとっては案内された経路が満足のいかない結果となってしまう。つまり、出発地から目的地までを徒歩で移動する際のコストは、予告無く状況が変化するために不確実な面があるので、コストデータとして準備することが困難である、従って、公共交通機関を利用する場合と異なる特異性がある。
【０００７】
そこで本発明は、歩行者のために好適な経路を探索することが可能な経路探索装置、経路探索方法、経路探索プログラムおよび地図データを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の経路案内装置は、歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納される記憶手段と、出発地から目的地までの各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索手段と、前記最適経路探索手段に最適経路を探索させ、当該最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、最適経路探索手段の探索条件を変更して、一以上の他の経路を前記最適経路探索手段に探索させ、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段とを備えたことを特徴とする。
【０００９】
本発明は、最適経路探索手段が出発地から目的地までに含まれるリンクのリンクコストデータから合計コストを演算して最適経路を探索したときに、この最適経路に不確定リンクが含まれているときには、最適経路に所要時間が不確定な要素が含まれているため、再探索手段が、最適経路探索手段の探索条件を変更して、一以上の他の経路を探索することで、最適経路と同等またはより以上の最適な経路を経路候補とすることができる。本発明は、経路探索方法としても、経路探索プログラムとしても、実施することが可能である。
【００１０】
前記再探索手段は、最適経路探索手段の探索条件を変更して、前記一以上の他の経路を探索するときに、前記最適経路に含まれる不確定リンクのリンクコストデータを変更して探索することができる。再探索手段が最適経路に含まれる不確定リンクのリンクコストデータを変更すると、最適経路として探索された経路の合計コストが変更されるので、再探索手段が出発地から目的地までの経路を、再度、最適探索手段に探索させることで、一以上の他の経路を探索することができる。
【００１１】
前記記憶手段には、前記リンク種別が不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータと、待ち時間が発生しない場合の待ち時間なしコストデータとが格納され、前記再探索手段は、前記最適経路探索手段に不確定リンクのリンクコストデータを変更して探索させるときに、前記待ち時間なしコストデータから前記待ち時間ありコストデータへ変更して合計コストを演算させるのが望ましい。再探索手段が、不確定リンクのリンクコストデータを、記憶手段に格納されている待ち時間なしコストと待ち時間ありコストデータとに設定することで、不確定リンクに応じたリンクコストを設定することができる。
【００１２】
前記再検索手段は、前記一以上の他の経路について探索するときに、（Ａ）前記最適経路探索手段により最初に探索された最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して新たな最適経路を前記最適経路探索手段に探索させ、（Ｂ）前記最適経路探索手段により新たな最適経路が探索されると、当該新たな最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して、再度、前記最適経路探索手段により最適経路を探索させ、（Ｃ）前記最適経路探索手段により探索された経路が、以前に探索されていない新たな経路であれば、更に（Ｂ）を処理し、（Ｄ）前記最適経路探索手段により探索された経路が、探索された経路に含まれている場合には、探索を終了するのが望ましい。
再探索手段は、最適経路に不確定リンクが含まれている場合には、当該最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータにして新たな最適経路の探索をする。そうすることで、新たな最適経路として好適な経路が存在するか否かが確かめられる。従って、再探索手段は、新たな最適経路が以前に探索された最適経路に一致するまで探索を繰り返すことで、不確定リンクを渡っても目的地まで早く到達できるかもしれない経路を探索することができる。
【００１３】
前記再探索手段は、探索された新たな最適経路に不確定リンクが含まれていない場合に、探索を終了するのが望ましい。そうすることで、再探索手段は、他の経路より合計コストが高いかもしれないが、不確定リンクを通行する必要のない経路を探索することができる。
【００１４】
前記再探索手段は、前記経路候補に含まれるそれぞれの不確定リンクの出発地側のノードを始点として設定し、前記最適経路探索手段にそれぞれの始点から目的地までの最適経路について局所経路として探索する局所経路探索処理を実行して、それぞれの始点ごとの局所経路グループを探索するのが望ましい。再探索手段が、不確定リンクの出発地側のノードを最適経路を探索する始点とすることで、出発地を始点した場合と始点が異なるので、新たな経路を探索することができる。
【００１５】
また、前記再探索手段は、前記局所経路探索処理を実行するときに、前記最適経路探索手段により前記（Ａ）から（Ｄ）までの処理を実行して前記局所経路を探索することができる。
【００１６】
前記記憶手段には、前記不確定リンクごとに待ち時間の発生の有無の確率を示す待ち発生確率値が格納され、前記再探索手段は、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択し、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算し、前記待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループの合計コストを演算し、前記局所経路グループごとの合計コストに基づいて推奨経路を決定するのが望ましい。
再探索手段は、まず、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択する。次に、再探索手段は、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算する。次に、再探索手段は、待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループの合計コストを演算する。そして、再探索手段は、局所経路グループごとの合計コストに基づいて推奨経路を決定することで、最良の局所経路グループを選択することができる。つまり、最初に探索された最適経路では、不確定リンクによる遅れが発生すると回避できない可能性があるが、最良の局所経路グループの始点まで進行しておけば、不確定リンクに到達した時点で待ちの状態となったとしても、他の経路へ分岐することが可能であるので、少し遠回りとなってしまうかもしればないが、なるべく待ちが発生しないような経路を選択することで、結果として目的地まで早く到達できる経路を探索することができる。
【００１７】
また、本発明の地図データは、コンピュータによる経路探索に利用される地図データ であって、歩行路であるリンクを表すリンクデータおよび該リンクの端点であるノードデータと、前記リンクの種別を示すためのリンク種別データと、前記リンクごとに設定されたリンクコストデータと、前記リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータ、および待ち時間が発生しない場合の待ち時間なしコストデータとを備え、コンピュータが、出発地から目的地までの各経路に含まれるリンクデータに設定されたリンクコストデータを読み込み、読み込まれたリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索し、当該最適経路に含まれるリンク種別データを読み込み、読み込まれたリンク種別データがリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、該不確定リンクに対応するコストデータを待ち時間なしコストデータから待ち時間ありコストデータへ変更して合計コストを演算して一以上の他の経路を探索し、前記最適経路と共に前記一以上の他の経路を経路候補とすることを特徴とする。
このような構成の地図データとすることで、経路中に不確定リンクを示すリンク種別が含まれているときに、待ち時間ありコストまたは待ち時間なしコストに基づいて合計コストを演算することができるので、より実際に即した最適経路の探索を行うことができる。
【発明の効果】
【００１８】
本発明は、最適経路に所要時間が不確定な要素が含まれているため、一以上の他の経路を探索することで、最適経路と同等またはより以上の最適な経路を経路候補とすることができるので、歩行者のために好適な経路を探索することが可能である。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態に係る経路案内システムを図面に基づいて説明する。
図１に示すように、経路案内システム１０は、ユーザである歩行者が携行する携帯電話２０と、経路探索装置として機能し、探索された経路を案内する経路案内サーバ３０と、電子地図データ生成装置として機能する電子地図データ生成サーバ４０とが、それぞれ電気通信回線の一例であるインターネットＷを介して通信可能に接続されている。ユーザは、携帯電話２０を携行して、経路案内サーバ３０から送信された地図画像を参照することで、目的地までを歩行する。
【００２０】
携帯電話２０は、図２に示すように、携帯端末として機能するものであり、通信部２１と、通話部２２と、インターネット制御部２３と、ＧＰＳ（Global Positioning System）部２４と、時計部２５と、操作部２６と、表示部２７と、主制御部２８とを備えている。
【００２１】
通信部２１は、無線信号により基地局または中継局と通信する無線手段として機能するものであり、送信パケットを変調したり、受信パケットに復調したりする機能を備えている。
通話部２２は、電話機能を実現するもので、図示しないマイクからの音声信号を送信パケットに変換したり、受信パケットから音声データを抽出してスピーカーから出力したりする機能を備えている。
インターネット制御部２３は、インターネットＷへのアクセス機能を実現するもので、ＵＲＬ（Uniform Resource Locator）に基づいてウェブサイトへアクセスして、表示部２７に表示されたブラウザにウェブサイトからの情報を表示する機能を備えている。
ＧＰＳ部２４は、現在位置を現在位置情報として出力する機能を備えている。現在位置情報としては、経度情報と緯度情報とすることができる。ＧＰＳ部２４は、ＧＰＳ（全地球測位システム）とする以外に、衛星測位システム（ガリレオ）なども採用できる。
時計部２５は、現在時刻を現在時刻情報として出力する機能を備えている。
操作部２６は、数字キー、記号キー、機能キー、十字キー（カーソルキーまたは選択キー）などを備え、入力手段として機能するものである。表示部２７は、表示データを表示する機能を備えている。表示部２７としては、ＬＣＤ（Liquid Crystal Display）や有機ＥＬ（Organic Electro-Luminescence）などが使用できる。主制御部２８は、携帯電話２０全体を統括制御する機能を備えている。主制御部２８は、ＧＰＳ部２４からの現在位置情報と、時計部２５からの現在時刻情報と、送信した携帯電話２０を特定する歩行者識別情報とを歩行者情報として、電子地図データ生成サーバ４０へ通信部２１を介して、所定時間間隔ごとに送信する機能を備えている。この所定時間間隔は、本実施の形態では例えば３秒とすることができる。
【００２２】
次に、経路案内サーバ３０の構成について、図３に基づいて説明する。コンピュータである経路案内サーバ３０は、経路探索プログラムを動作させることで、地図画像上に経路を重畳させたウェブページを送信する機能を備えている。
【００２３】
経路案内サーバ３０は、上述した機能を実現するために、通信部３１と、地図要求受付部３２と、地図送信部３３と、経路探索部３４と、経路提供部３５と、地図送信部３３と、情報報知部３６と、地図情報記憶部３７と、地図データ更新部３８とを備えている。
通信部３１は、インターネットＷを介して携帯電話２０と通信する機能を備えており、例えば、ＡＤＳＬ（Asymmetric Digital Subscriber Line）や、ＦＴＴＰ（Fiber To The Premises）と接続するＬＡＮ（Local Area Network）とすることができる。
地図要求受付部３２は、インターネットＷを介して送信された地図画像の表示要求コマンドを受け付け、所定地域周辺の地図画像の要求であれば、表示要求コマンドと共に受信した位置情報を地図送信部３３へ地図画像の送信を指示する。また、地図要求受付部３２は、経路探索であれば、表示要求コマンドと共に受信した出発地情報および目的地情報に基づいて経路探索部３４へ経路探索を指示する。
地図送信部３３は、地図情報記憶部３７から読み込んだ地図画像を通信部３１を介してインターネットＷに送信する機能を備えている。
【００２４】
経路探索部３４は、ユーザから指定されたコマンドに基づき経路探索を行う機能を備えている。経路探索には、例えば、ダイクストラ法などの周知の方法が利用可能である。この経路探索部３４は、最適経路探索部３４０と、再探索部３４１とを備えている。
最適経路探索部３４０は、出発地から目的地までの経路のうち、合計コストが最も小さい経路を最適経路として探索する最適経路探索手段として機能するものである。
再探索部３４１は、最適経路探索部３４０により最初に探索された最適経路に、通行するときの所要時間が不確定な不確定リンクが含まれるか否かを判定し、不確定リンクが含まれていれば、一以上の他の経路を最適経路探索部３４０に探索させる再探索手段として機能するものである。再探索部３４１は、初期経路探索部３４１ａと、局所経路探索部３４１ｂと、コスト演算部３４１ｃを備えている。
【００２５】
初期経路探索部３４１ａは、初期経路探索処理を実行することで、最適経路探索部３４０に探索させた最適経路以外の一以上の他の経路を探索する機能を備えている。
局所経路探索部３４１ｂは、局所経路探索処理を実行することで、初期経路探索部３４１ａにより探索された一以上の他の経路について、更に局所的な経路探索を行う機能を備えている。
コスト演算部３４１ｃは、局所経路探索部３４１ｂにより探索された局所経路グループに基づいて、不確定リンクの待ち発生確率を考慮した合計コストを演算する機能を備えている。
経路提供部３５は、経路探索部３４が探索した経路を地図画像に重畳させる機能を備えている。情報報知部３６は、文字や音声などのメッセージを通信部３１を介してインターネットＷへ送信する機能を備えている。
【００２６】
地図情報記憶部３７は、経路探索や地図表示に使用される電子地図データベースである。この地図情報記憶部３７は、大容量で高速アクセスが可能なハードディスクドライブを採用することができる。地図情報記憶部３７には、車路や歩行路を表すリンクデータと、このリンクの端点であるノードデータと、リンクの種別を示すリンク種別データと、リンクごとに設定されたリンクコストデータとを含む地図データが、それぞれ関連付けられて格納されている。リンクコストデータは、リンク種別データが不確定リンクを示す場合には、待ち時間が発生する場合のコストである待ち時間ありコストデータと、待ち時間が発生しない場合のコストである待ち時間なしコストデータとが設けられている。
また、地図情報記憶部３７には、リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクである場合には、このリンクに、待ち時間が発生する確率を示す待ち時間あり発生確率値と、待ち時間が発生しない確率を示す待ち時間なし発生確率値とが関連付けられている。この待ち時間あり発生確率と待ち時間なし発生確率は、後述するように、実際に横断歩道を歩行している歩行者の移動軌跡情報を用いて作成されても良い。また、横断歩道にある信号機は一般的に、待ち時間がある場合とない場合の２つの場合に大別されるため、例えば待ち時間ありの場合の確率を０．５、待ち時間のない場合の確率を０．５と予め設定しておいても良い。また、予め設定する基準は、例えば横断歩道が、渡ろうとする道路に交わる他の道路と平行な場合と単純に道路を横断する場合で差を設けても良い、さらに、横断しようとする道路に交わる他の道路と平行な横断歩道の場合には交わる道路の道路種別や幅と横断する道路の種別や幅に応じて差異を設けても良い。また、３差路以上の交差点の場合には交差点にかかる各信号の待ちなし確率を１／３、待ちあり確率を２／３とする等、交差点の形状によって均等に待ちありと待ちなしの確率を設定しても良い。こうすることによって、予めデータを作成することなく、現実の状況により近い，待ちありおよび待ちなしの確率を用いた経路案内を行うことが可能となる。
【００２７】
地図データ更新部３８は、通信部３１を介して電子地図データ生成サーバ４０と通信して、地図情報記憶部３７に格納されている待ち時間あり発生確率値と、時間なし発生確率値を更新する機能を備えている。
【００２８】
次に、電子地図データ生成サーバ４０の構成について、図４に基づいて説明する。コンピュータである電子地図データ生成サーバ４０は、電子地図データ生成プログラムを動作させることで、実際の状況に応じた不確定リンクの待ち時間あり発生確率値を算出して、経路案内サーバ３０の経路探索を行う際の精度を向上させる機能を備えている。
【００２９】
電子地図データ生成サーバ４０は、上述した機能を実現するために、通信部４１と、位置情報収集部４２と、軌跡補間部４３と、軌跡抽出部４４と、ノイズ除去部４５と、確率演算部４６と、地図データ送信部４７と、地図情報記憶部４８とを備えている。
通信部４１は、インターネットＷを介して携帯電話２０と通信する機能を備えており、経路案内サーバ３０と同様に、ＬＡＮとすることができる。
位置情報収集部４２は、携帯電話２０からの歩行者位置情報、または図示しない車両に搭載されたナビゲーション装置やプローブ車両からの車両位置情報を、通信部４１を介して収集し、記憶手段である地図情報記憶部４８へ収集した歩行者位置情報および車両位置情報を格納する機能を備えている。
軌跡補間部４３は、順次受信した歩行者位置情報または車両位置情報に含まれる現在位置情報により得られた移動軌跡に対して、現在位置情報の送信時間間隔が大きい場合、現在位置情報が示すそれぞれの位置の間を補間して、移動軌跡の構成点を密にする機能を備えている。
軌跡抽出部４４は、現在位置情報が描く軌跡が不確定リンクを通過したものか否かを判定し、不確定リンクを通過した軌跡を抽出する機能を備えている。
ノイズ除去部４５は、軌跡抽出部４４により抽出された軌跡から、不確定リンクの待ち発生確率値の精度を向上させるのに阻害となる軌跡（以下、この軌跡をノイズと称すことがある。）を除外する機能を備えている。
確率演算部４６は、ノイズ除去部４５によりノイズが除去され、残った軌跡から不確定リンクの待ち発生確率値を演算する機能を備えている。
地図データ送信部４７は、地図情報記憶部４８に格納された不確定リンクの待ち発生確率値を経路案内サーバ３０へ通信部４１を介して送信する機能を備えている。
地図情報記憶部４８には、車路や歩行路を表すリンクデータと、このリンクの端点であるノードデータと、リンクの種別を示すリンク種別データとを含む電子地図データが、それぞれ関連付けられて格納されている。また、地図情報記憶部４８には、位置情報収集部４２により収集された歩行者位置情報や車両位置情報などの位置情報と、軌跡抽出部４４により生成された移動軌跡情報テーブルと、確率演算部４６により演算された待ち時間あり発生確率値および待ち時間なし発生確率値とが格納されている。この地図情報記憶部４８は、大容量で高速アクセスが可能なハードディスクドライブを採用することができる。
【００３０】
以上のように構成された本発明の実施の形態に係る経路案内システム１０の動作および使用状態について、図面に基づいて説明する。
【００３１】
まず、図５に基づいて、経路案内サーバ３０の動作について、全体の流れを説明した後に、経路探索の方法について詳細に説明する。
携帯電話２０を携行する歩行者は、携帯電話２０の操作部２６を操作してブラウザを起動し、現在位置の周辺地域の地図画像を経路案内サーバ３０へ表示要求する。この操作によりインターネット制御部２３は、ＧＰＳ部２４からの現在位置情報と共に表示要求コマンドを経路案内サーバ３０へ通信部２１を介して送信する（ステップＳ１１０）。
【００３２】
表示要求コマンドを受け付けた経路案内サーバ３０の地図要求受付部３２は、地図送信部３３へ周辺地域の地図画像を、現在地情報に基づいて地図情報記憶部３７から取得する（ステップＳ１２０）。地図送信部３３は、地図情報記憶部３７から取得した周辺地域の地図画像を通信部３１を介して携帯電話２０へ送信する（ステップＳ１３０）。
地図画像を受信した携帯電話２０のインターネット制御部２３は、地図画像をブラウザに表示する（ステップＳ１４０）。
【００３３】
次に、歩行者は、表示部２７に表示された地図画像を見ながら操作部２６を操作して目的地を指定し、現在地である出発地から目的地までの経路探索を経路案内サーバ３０へ依頼する。この操作によりインターネット制御部２３は、経路探索を依頼するコマンドである経路探索要求コマンドと共に、ＧＰＳ部２４からの取得した現在位置情報を出発地情報とし、指定された目的地の位置情報を目的地情報として経路案内サーバ３０へ送信する（ステップＳ１５０）。
【００３４】
経路探索要求コマンドを受け付けた経路案内サーバ３０の地図要求受付部３２は、経路探索部３４へ出発地から目的地までの推奨経路の探索を指示する（ステップＳ１６０）。
経路提供部３５は、経路探索部３４が探索した推奨経路を周辺地域の地図画像に重畳させる（ステップＳ１７０）。そして、推奨経路が重畳された周辺地域の地図画像を地図送信部３３が通信部３１を介して携帯電話２０へ送信する（ステップＳ１８０）。
地図画像を受信した携帯電話２０のインターネット制御部２３は、地図画像をブラウザに表示する（ステップＳ１９０）。
このような手順で、ユーザである歩行者は現在地である出発地から目的地までの経路を探索することができる。
【００３５】
次に、ステップＳ１６０での推奨経路の探索方法について詳細に説明する。本実施の形態では、図６に示す経路図１についての経路探索処理例（１）と、図２２に示す経路図２についての経路探索処理例（２）とに基づいて説明する。なお、経路探索処理例（１）と経路探索処理例（２）とについて、不確定リンクとして、信号機付きの横断歩道を示す横断リンクを例に説明する。また、リンクコストデータ、待ち時間ありコストデータ、待ち時間なしコストデータを、コスト演算の説明においては、単にリンクコスト、待ち時間ありコスト、待ち時間なしコストと称する。
【００３６】
経路探索処理例（１）
図６に示す経路図１は、地図情報記憶部３７に格納された地図データの一部を模式的に表したものである。経路図１には、出発地ＳＴ１から目的地ＧＬ１までの歩行路を表すリンクＬ１〜リンクＬ２３と、このリンクＬ１〜リンクＬ２３の端点であるノードＡ〜ノードＯと、リンクＬ１〜リンクＬ２３のそれぞれに割り付けられたリンクコストとが示されている。リンクＬ１〜リンクＬ６およびリンクＬ２３は、道幅の狭い道路であり、ノードＤ〜ノードＩとノードＪ〜ノードＯのそれぞれに接続されるリンクＬ７〜リンクＬ２２は大通りである。
【００３７】
つまり、リンクＬ７〜リンクＬ１１とリンクＬ１８〜リンクＬ２２は大通りの両側に敷設された歩道を示し、リンクＬ１２〜リンクＬ１７はこの大通りを横断する信号付きの横断歩道である。従って、リンクＬ１２〜リンク１７には、横断歩道であることを示すリンク種別データが割り付けられている。以下、このリンクＬ１２〜リンクＬ１７を横断リンクＬ１２〜横断リンクＬ１７と称する。また、横断リンクＬ１２〜横断リンクＬ１７のリンクコストには、信号待ちが発生しない場合の待ち時間なしコスト「２０」と、信号待ちが発生したことによる時間の損失を考慮した待ち時間ありコスト「４０」との２つのコストが割り付けられている。
【００３８】
このような経路図１において、携帯電話２０から送信された出発地情報および目的地情報に基づいて、まず経路探索部３４が初期経路探索処理（一次経路探索処理）を行う。
【００３９】
図７に示すように、初期経路探索処理は、最初に最適経路探索部３４０に最適経路を探索させる（ステップＳ２１０）。この最適経路の探索は、横断リンクＬ１２〜横断リンクＬ１７の全てのリンクコストを待ち時間なし「２０」とし、出発地ＳＴ１から目的地ＧＬ１まで各経路に含まれるそれぞれのリンクのリンクコストから合計コストを演算することで、合計コストが最小の経路を探索して最適経路とする。この探索は、信号待ちによる時間の損失を考慮しない従来の方法と同じである。
【００４０】
この経路図１の場合では、図８に示す出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＨ→ノードＮ→目的地ＧＬ１の順に歩行する経路（Ａ）が、コスト「８８」であるので最小のコストである。
【００４１】
次に、再探索部３４１の初期経路探索部３４１ａは、最適経路として探索された経路（Ａ）について、リンクを通行するための所要時間が不確定な不確定リンク、つまり横断リンクが含まれるか否かを判定する（ステップＳ２２０）。経路（Ａ）には、ノードＨ，Ｎにて接続された横断リンクＬ１６が含まれているので、横断リンク有りの判定となる。
【００４２】
初期経路探索部３４１ａは、経路（Ａ）に横断リンクが含まれていると判定することにより、横断リンクＬ１６のリンクコストを待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する（ステップＳ２３０）。つまり、横断歩道で待ち時間が発生していない場合から、待ち時間が発生した場合へと変更する。そして、初期経路探索部３４１ａは、再度、最適経路探索部３４０に出発地ＳＴ１から目的地ＧＬ１までの最適経路を探索させる（ステップＳ２４０）。
【００４３】
横断リンクＬ１６のリンクコストを待ち時間なしコスト「２０」として演算した場合には、経路（Ａ）の合計コストが「８８」であったが、待ち時間ありコスト「４０」へ変更することで、経路（Ａ）の合計コストは「１０８」となる。従って、最適経路探索部３４０による結果は、出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＧ→ノードＭ→ノードＮ→目的地ＧＬ１の順に歩行する図９に示す経路（Ｂ）がコスト「９０」であるので、最小のコストとなる。従って、２回目の経路探索では、経路（Ｂ）が最適経路として探索される。
【００４４】
初期経路探索部３４１ａは、経路（Ｂ）について、横断リンクが含まれるか否かを判定する（ステップＳ２５０）。経路（Ｂ）には、ノードＧ，Ｍにて接続された横断リンクＬ１５が含まれているので、横断リンク有りとの判定となる。
【００４５】
次に、初期経路探索部３４１ａは、探索された経路が新たな経路か否かを判定する（ステップＳ２６０）。この場合には、探索された経路（Ｂ）は、経路（Ａ）と異なり新たな経路なので、ステップＳ２３０へ移行する。
このようにして、初期経路探索部３４１ａは、順次、ステップＳ２３０からステップＳ２６０を繰り返して、最適経路探索部３４０に最適経路を探索させることで、図１０に示すように、最初に経路（Ａ）が探索された後、経路（Ｂ）から経路（Ｆ）が順番に探索される。ここで、経路（Ａ）から経路（Ｆ）について図１１に合計コストを示す。図１１では、それぞれの経路に含まれる横断リンクのリンクコストを待ち時間なしコストとした場合と、待ち時間ありコストとした場合との合計コストを示している。
図１１から待ち時間なしコストから待ち時間ありコストへ変更して、合計コストを算出し、最小のコストとなる経路を最適経路とすると、経路（Ａ）から経路（Ｆ）までが順次、探索されることがわかる。
【００４６】
そして、経路（Ｆ）の横断リンクＬ１３について、リンクコストを待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して（ステップＳ２３０）、最適経路を探索すると（ステップＳ２４０）、経路（Ｆ）の合計コストは「１２０」なので、合計コスト「１０８」の経路（Ａ）が最適経路として、再度探索される。つまり、初期経路探索部３４１ａは、横断リンク有りの判定をした後に（ステップＳ２５０）、以前に探索された経路と同じ経路であるとの判定をして（ステップＳ２６０）、初期経路探索処理を終了する。これらの経路（Ａ）〜経路（Ｆ）は、初期経路探索部３４１ａにより、地図情報記憶部３７に初期探索経路情報として格納される。
【００４７】
本実施の形態では、経路（Ａ）〜経路（Ｆ）の全てに横断リンクが含まれているが、最適経路として探索された経路に、横断リンクが含まれていなければ、初期経路探索部３４１ａは、初期経路探索処理を終了するように判定する（ステップＳ２２０，ステップＳ２５０）。それは、横断リンクが含まれていないために、待ち時間なしコストから待ち時間ありコストへと変更できないため、再度、ステップＳ２４０にて最適経路探索を行っても同じ結果となるためである。
【００４８】
このようにして探索された経路（Ａ）〜経路（Ｆ）について、局所経路探索処理（二次経路探索処理）を行う。局所経路探索処理は、各経路を局所的にコスト演算して、より最適な経路を探索する処理である。
【００４９】
図１２に示すように、局所経路探索処理では、まず、局所経路探索部３４１ｂが、経路（Ａ）〜経路（Ｆ）のそれぞれに含まれる横断リンクの出発地ＳＴ１側の端点であるノードを探索する（ステップＳ３１０）。これにより、図１３に示すノードＥ〜ノードＨが探索される。
【００５０】
次に、探索されたノードＥ〜ノードＨの各ノードのうち、一のノードを始点（出発地）として設定する（ステップＳ３２０）。そして、始点として設定されたノード（ノードＥ〜ノードＦ）から目的地ＧＬ１までの最適経路を探索する（ステップＳ３３０）。本実施の形態では、まず、目的地ＧＬ１に近いノードＨから局所経路探索するものとする。
【００５１】
ここで、ステップＳ３３０にて行われる局所経路探索での経路探索について、図１４に基づいて詳細に説明する。
全部の横断リンク（横断リンクＬ１２〜横断リンクＬ１７）のリンクコストを待ち時間なしコスト「２０」とする（ステップＳ４１０）。次に、ノードＨを始点とした経路の合計コストが最小の経路を最適経路として探索する（ステップＳ４２０）。以下、局所経路探索における合計コストを局所コストと称する。
【００５２】
最適経路の探索は、ノードＨを始点として設定しているので、図１５（Ａ）に示すような、ノードＨから横断リンクＬ１６を介してノードＮへ向かう経路（ａ）が探索される。そして、以前に探索された経路と同じ経路か否かを判定する（ステップＳ４３０）。まだ、最初の経路（ａ）を探索したばかりなので、次の経路を探索するために横断リンクのリンクコストを待ち時間なしコストから待ち時間ありコストへ変更する（ステップＳ４４０）。つまり、横断リンクＬ１６のリンクコストを「２０」から「４０」へ変更する。
【００５３】
横断リンクＬ１６のリンクコストを「２０」から「４０」へ変更して最適経路の探索をした結果、経路（ａ）の局所コストが「５０」であるのに対し、最小となる他の経路の局所コストも「５０」であるため、最適経路としてはやはり経路（ａ）が最適経路として探索される（ステップＳ４２０）。従って、１回目と２回目とで同じ最適経路が探索されるので、局所経路探索での最適経路の探索を終了する（ステップＳ４３０）。
【００５４】
図１２に戻って、経路探索が終了すると、全ての出発地（ノードＥ〜ノードＨ）について経路探索したか否かを判定する（ステップＳ３４０）。全ての経路探索が終わっていれば処理を終了する。終わっていなければ、次のノード、例えば、ノードＨについて終了していればノードＧを出発地として設定する（ステップＳ３２０）。
【００５５】
このようにして、ノードＨからノードＥまで順番に行うことで、図１５（Ａ）から同図（Ｄ）までに示すように、ノードＨを始点した局所経路グループには経路（ａ）が探索され、ノードＧを始点とした局所経路グループには経路（ｂ），（ｃ）が探索され、ノードＦを始点とした局所経路グループには経路（ｄ）〜経路（ｆ）が探索され、ノードＥを始点とした局所経路グループには経路（ｇ）〜経路（ｊ）が探索される。これらの局所経路グループに属するそれぞれの経路（ａ）〜経路（ｊ）は、局所経路探索部３４１ｂにより、地図情報記憶部３７に局所探索経路情報として格納される。
【００５６】
経路（ａ）〜経路（ｊ）が探索されたことで、コスト演算部３４１ｃは、次に、経路（ａ）〜経路（ｊ）と、この経路（ａ）〜経路（ｊ）へ至るまでの最適経路との合計コストを演算する。ノードＥ〜ノードＨを経由する経路は、例えば、経路（ａ）であれば、図１０に示す経路（Ａ）の出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＨの経路が最も小さいコストとなるため、合計コストは、横断リンクＬ１６のコストを待ち時間なしコストとした場合で「８８」、待ち時間ありコストとした場合で「１０８」となる。このようにして演算された経路（ａ）〜経路（ｊ）の局所コストと合計コストとを局所経路グループごとに図１６（Ａ）〜同図（Ｄ）に示す。
【００５７】
このように局所経路探索処理を行うことで、初期経路探索処理では探索されなかった経路が探索される。例えば、初期経路探索処理ではノードＦを通過する経路は、図１０に示すように横断リンクＬ１４を通る経路（Ｄ）と、横断リンクＬ１５を通る経路（Ｅ）とが探索されたが、ノードＦを始点とした局所経路探索処理では、図１５（Ｃ）に示すように、更に横断リンクＬ１６を通る経路（ｆ）が探索される。
【００５８】
局所経路探索処理による経路の探索が終了すると、次に、コスト演算部３４１ｃは、横断リンクの待ち時間の発生確率を考慮した合計コストの演算を行う。本実施の形態では、待ち時間あり発生確率値を１／２、待ち時間なし確率値を１／２とする。
【００５９】
まず、最初にノードＨを始点として局所経路探索された経路（ａ）を経由点とした経路について合計コストの演算を行う。経路（ａ）を経由点とした経路の合計コストは、横断リンクとして横断リンクＬ１６が一つのみなので、横断リンクＬ１６が待ち時間が発生する場合としない場合との２通りとなる。すなわち、図１７に示すように、待ち時間が発生する場合の合計コストは「８８」であり、待ち時間が発生しない場合の合計コストは「１０８」である。従って、横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ１は、式（１）によって演算することができる。
合計コストＣ１＝88×1/2＋108×1/2＝９８ …（１）
【００６０】
次に、ノードＧを経由点とする経路（経路（ｂ），（ｃ）を含む経路）について合計コストの演算を行う。経路（ｂ），（ｃ）を含む経路の合計コストは、横断リンクとして２つの横断リンクＬ１５，Ｌ１６が含まれるので、図１８に示すように４通りとなる。従って、それぞれの組み合わせ事象が発生する確率は１／２×１／２となり１／４となる。
【００６１】
例えば、横断リンクＬ１５，Ｌ１６の両方で待ち時間が発生しない場合には、まずノードＧを端点とする横断可能な横断リンクL１５（待ち時間の発生しない横断リンクＬ１５）を渡る経路（ｃ）が選択されるので、合計コストが「９０」となる。
次に、横断リンクＬ１５で待ち時間が発生せず、横断リンクＬ１６で待ち時間が発生する場合には、ノードＧにいる歩行者は、横断リンクＬ１６より手前にある横断リンクＬ１５を横断リンクＬ１６より先に渡った方が、目的地に到達するまでに所要時間が不確定な要因を排除できる。結果、横断リンクＬ１５で待ち時間が発生せず、横断リンクＬ１６で待ち時間が発生する場合には、経路（ｃ）が選択されるので、合計コストは「９０」となる。
【００６２】
次に、横断リンクＬ１５で待ち時間が発生し、横断リンクＬ１６で待ち時間が発生しない場合には、ノードＧにて横断リンクＬ１５が横断可能な状態となるまで待つよりも、ノードＨに向かう方が効率がよい。結果、経路（ｂ）が選択されるので、合計コストは「９０」となる。
【００６３】
横断リンクＬ１５，Ｌ１６の両方で待ち時間が発生する場合には、横断リンクＬ１５の端点であるノードＧで待たずに歩行者は先へ進み、ノードＨに到達するまでに横断可能となることが期待できるので、横断リンクＬ１６を通過する経路（ｂ）を選択した方がよい。従って、経路（ｂ）が選択されるので、合計コストは「１１０」となる。
このようにして経路が選択されるので、横断リンクＬ１５，Ｌ１６の待ち時間の発生確率を考慮した合計コストＣ２は、式（２）によって演算することができる。
合計コストＣ２＝90×1/4＋90×1/4＋90×1/4＋110×1/4＝９５ …（２）
【００６４】
次に、ノードＦを経由点とする経路（経路（ｄ）〜経路（ｆ）を含む経路）について合計コストの演算を行う。経路（ｄ）〜経路（ｆ）を含む経路の合計コストは、横断リンクとして３つの横断リンクＬ１４〜横断リンクＬ１６が含まれるので、図１９に示すように４通りとなる。従って、それぞれの組み合わせ事象が発生する確率は１／２×１／２×１／２となり１／８となるので、横断リンクＬ１４〜横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ３は、式（３）によって演算することができる。
合計コストＣ３＝90×1/8＋90×1/8＋90×1/8＋90×1/8＋95×1/8＋95×1/8＋95×1/8＋115×1/8＝９５ …（３）
【００６５】
次に、ノードＥを経由点とする経路（経路（ｇ）〜経路（ｊ）を含む経路）について合計コストの演算を行う。経路（ｇ）〜経路（ｊ）を含む経路の合計コストは、横断リンクとして４つの横断リンクＬ１３〜横断リンクＬ１６が含まれるので、図２０に示すように１６通りとなる。従って、それぞれの事象が発生する確率は１／２×１／２×１／２×１／２となり１／１６となるので、横断リンクＬ１３〜横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ４は、式（４）によって演算することができる。
合計コストＣ４＝100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋90×1/16＋90×1/16＋90×1/16＋90×1/16＋95×1/16＋95×1/16＋95×1/16＋115×1/16＝９７．５ …（４）
このようにして、コスト演算部３４１ｃは、各経路での合計コストＣ１〜Ｃ４を演算する。
【００６６】
初期経路探索処理では、図１１に示すように、経路（Ａ）が最小コストであった。この経路（Ａ）について、横断リンクの待ち時間の発生確率を考慮した合計コストを演算すると、合計コストＣ５は、横断リンクとして横断リンクＬ１６のみ含んでいるので、式（５）によって演算することができる。
合計コストＣ５＝88×1/2＋108×1/2＝９８ …（５）
【００６７】
つまり、初期経路探索処理によって探索された経路（Ａ）では合計コストが９８となるが、局所経路探索処理により経路を探索し、合計コストを演算すると、ノードＦを始点した局所経路グループが合計コストが９５となって、ノードＥを始点した局所経路グループの合計コストと同じ値で、最も小さい値であるが、この場合、ノードＦとノードＥとで出発地ＳＴ１に近い方が選択される。
つまり、出発地ＳＴ１からノードＡおよびノードＥを経由してノードＦへ至り、ノードＦを通過した後に、横断リンクＬ１４〜横断リンクＬ１６の状態に応じて経路（ｄ）〜経路（ｆ）のいずれかの経路を歩行する方が最適な経路を選択できることを示している。これは、歩行者がノードＦまで到達した時点で、横断リンクが赤信号であれば青信号の横断リンクを選択しながら歩行することができるからである。
更に、ノードＦから経路（ｄ）〜経路（ｆ）のうち、横断リンクＬ１４が青信号であれば、経路（ｄ）を選択することが最もよいことを示している。
【００６８】
経路提供部３５は、このように経路が探索されると、推奨経路を周辺地域の地図画像に重畳させる。例えば、図２１に示すように出発地ＳＴ１からノードＦまでに至るまでの一つの経路と、ノードＦから目的地ＧＬ１へ至る複数の経路（経路（ｄ）〜経路（ｆ））とにより歩行者に案内する。このとき、最も良い経路である経路（ｄ）について目立つようにして案内するようにしてもよい。更に、情報報知部３６により、まずノードＦまで歩行し、更に横断リンクＬ１４〜横断リンクＬ１６を順に青であれば渡ってよい旨のメッセージまたは音声を、地図画像と共に携帯電話２０へ送信することで更に利便性を向上させることができる。また、最も良い経路である経路（ｄ）についても文字や音声で案内するようにしてもよい。
【００６９】
経路探索処理例（２）
図２２に示す経路図２は、出発地ＳＴ２から目的地ＧＬ２までのいずれの経路中にも複数の横断リンクが含まれている例を示すものである。
経路図２には、出発地ＳＴ２から目的地ＧＬ２までの歩行路を表すリンクＬ２４〜リンクＬ３５と、このリンクＬ２４〜リンクＬ３５の端点であるノードＰ〜ノードＷと、リンクＬ２４〜リンクＬ３５のそれぞれに割り付けられたリンクコストとが示されている。
【００７０】
リンクＬ２５とリンクＬ２６とは大通りの両側に敷設された歩道を示し、リンクＬ３１とリンクＬ３２とはこの大通りを横断する信号付きの横断歩道である。また、リンクＬ２９とリンクＬ３０も同様に大通りの両側に敷設された歩道を示し、リンクＬ３３とリンクＬ３４はこの大通りを横断する信号付きの横断歩道である。従って、経路図１と同様に、リンクＬ３１〜リンク３４には、横断歩道であることを示すリンク種別データが割り付けられている。以下、このリンクＬ３１〜リンク３４を横断リンクと称する。また、横断リンクＬ３１〜横断リンクＬ３４のリンクコストには、信号待ちが発生しない場合の待ち時間なしコスト「２０」と、信号待ちが発生したことによる時間の損失を考慮した待ち時間ありコスト「４０」との２つのコストが割り付けられている。
【００７１】
このような経路図２において、携帯電話２０から送信された出発地情報および目的地情報に基づいて、経路図１を用いて説明したように、まず経路探索部３４が初期経路探索処理（一次経路探索処理）を行う。
【００７２】
図２３に示すように、初期経路探索処理は、最初に最適経路探索部３４０が最適経路を探索する（ステップＳ５１０）。この最適経路の探索は、横断リンクＬ３１〜横断リンク３４の全てのリンクコストを待ち時間なし「２０」とし、出発地ＳＴ２から目的地ＧＬ２まで各経路に含まれるそれぞれのリンクのリンクコストから合計コストを演算することで、合計コストが最小の経路を探索して最適経路とする。この探索は、信号待ちによる時間の損失を考慮しない従来の方法と同じである。
【００７３】
この経路図２の場合では、図２４に示す出発地ＳＴ２→ノードＰ→ノードＱ→ノードＳ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路（Ｇ）が、コスト「９０」で最小のコストである。しかし、最小コストいう点では、例えば、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＳ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路でもコスト「９０」であり、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＴ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路でもコスト「９０」である。この場合、最適経路探索部３４０は、いずれの経路を選択して最適経路としてもよいが、本実施の形態では、最初に探索された経路（Ｇ）を最適経路として設定したものとする。このようにして、経路としては一つであるが、まず経路（Ｇ）が最適経路グループ（ア）として、図２５に示すように探索される。
【００７４】
次に、再探索部３４１の初期経路探索部３４１ａは、最適経路として探索された経路（Ｇ）について、リンクを通行するための所要時間が不確定な不確定リンク、つまり横断リンクが含まれるか否かを判定する（ステップＳ５２０）。経路（Ｇ）には、ノードＱ，Ｓにて接続された横断リンクＬ３２と、ノードＵ，Ｗにて接続された横断リンクＬ３４とが含まれているので、横断リンク有りの判定となる。
【００７５】
初期経路探索部３４１ａは、経路（Ｇ）に横断リンクが含まれていると判定することにより、次の最適経路グループを探索する。
経路（Ｇ）には、横断リンクＬ３２，Ｌ３４が含まれているので、この横断リンクＬ３２，Ｌ３４について、いずれか一方、または両方のリンクコストを、順次、待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して、それぞれ変更したときの最適経路の探索を行う。
この場合、まず横断リンクＬ３２のリンクコストを変更する（ステップＳ５３０）。そして、初期経路探索部３４１ａは、再度、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。
【００７６】
横断リンクＬ３２のリンクコストを待ち時間なしコスト「２０」として演算した場合には、経路（Ｇ）の合計コストが「９０」であったが、待ち時間ありコスト「４０」へ変更することで、経路（Ｇ）の合計コストは「１１０」となる。従って、最適経路探索部３４０による結果は、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＴ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する図２４に示す経路（Ｈ）がコスト「９０」であるので、経路（Ｇ）より小さいコストとなる。従って、図２５に示すように２回目の経路探索では、経路（Ｈ）が、最適経路グループ（イ−１）として探索される。
【００７７】
初期経路探索部３４１ａは、経路（Ｈ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｈ）には、横断リンクＬ３１，Ｌ３４が含まれているので、横断リンク有りとの判定となる。
【００７８】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。この時点では、まだ横断リンクＬ３２のみ変更しただけなので、残りの経路を探索するためにステップＳ５３０へ移行する。
【００７９】
次に、横断リンクＬ３４を待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する。このとき、横断リンクＬ３２のコストは待ち時間なしコスト「２０」とする（ステップＳ５３０）。そして、初期経路探索部３４１ａは、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。そうすることで、最適経路として合計リンクコストが「９０」の経路（Ｉ）（図２５に示す最適経路グループ（イ−２）参照）が探索される。
【００８０】
初期経路探索部３４１ａは、経路（Ｉ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｉ）には、横断リンクＬ３１，Ｌ３３が含まれているので、横断リンク有りとの判定となる。
【００８１】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。この場合、横断リンクＬ３２，Ｌ３４の両方のリンクコストを待ち時間ありコストとするケースが残っているため、ステップＳ５３０へ移行する。
次に、横断リンクＬ３２を待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する。つまり、横断リンクＬ３２，Ｌ３４のコストを待ち時間ありコスト「４０」とする（ステップＳ５３０）。そして、初期経路探索部３４１ａは、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。そうすることで、最適経路として合計リンクコストが「９０」の経路（Ｉ）（図２５に示す最適経路グループ（イ−３）参照）が探索される。
【００８２】
初期経路探索部３４１ａは、経路（Ｉ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｉ）には、横断リンクＬ３１，Ｌ３３が含まれているので、横断リンク有りとの判定となる。
【００８３】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。横断リンクＬ３２，Ｌ３４のリンクコストを変更して、全てのケースについて最適経路を探索したので、最適経路グループ（イ）については終了する。
次に、最適経路グループに以前に探索されていない新たな経路が含まれているか否かを判定する（ステップＳ５７０）。
最適経路グループ（イ）には、最適経路グループ（ア）には含まれていない経路（Ｈ）や経路（Ｉ）が探索されたため、ステップＳ５３０へ移行する。
【００８４】
経路（Ｈ）および経路（Ｉ）について、経路（Ｈ）には横断リンクＬ３１，Ｌ３４が含まれ、経路（Ｉ）には横断リンクＬ３１，Ｌ３３が含まれている。従って、ステップＳ５３０からステップＳ５６０を繰り返して、これらの横断リンクについて、いずれか一方、または両方のリンクコストを、順次、待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して、それぞれ変更したときの最適経路の探索を行う。その際、経路探索グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、経路探索グループ（イ）を探索したときと同様に、全てのケースについて行う。
【００８５】
初期経路探索部３４１ａは、横断リンクのリンクコストを変更し最適経路を探索することで、図２５に示す最適経路グループ（ウ）として（ウ−１）〜（ウ−９）を抽出する。なお、図２５の最適経路グループ（ウ）については、他の経路と重複するケースは省略している。初期経路探索部３４１ａは、最適経路を最適経路探索部３４０に探索させる際に、横断リンクＬ３１〜横断リンクＬ３４の状態の組み合わせが以前にあったか否かを予め判断してから最適経路の探索をさせるようにしてもよいし、最適経路探索部３４０に探索させてから重複した組み合わせについて削除するようにしてもよい。これら図２５に示す抽出された経路は、初期経路探索部３４１ａにより、地図情報記憶部３７に初期探索経路情報として格納される。
【００８６】
このようにして探索された経路（Ｇ）〜経路（Ｉ）について、局所経路探索処理（二次経路探索処理）を行う。
局所経路探索処理は、局所経路探索部３４１ｂが、まず横断リンクの出発地側のノードを始点として横断リンクのリンクコストを変更しながら順次、最適経路を探索し、次にこのノードを経由点とした経路の合計リンクを算出する。この方法については、経路図１における経路探索処理例（１）と同じである。
【００８７】
経路図２における局所経路探索処理を行った結果を、図２６から図２９に示す。図２６は、局所経路探索部３４１ｂによりノードＰを始点（経由点）とした局所経路探索処理を行い、コスト演算部３４１ｃにより算出したその経路の合計コストを示したものである。
【００８８】
ノードＰを始点とした場合、まず、横断リンクＬ３１が待ち時間ありの場合には、リンクＬ２５を経由してノードＱまで到達し、横断リンクＬ３２を渡る経路を選択する。これは、ノードＰにて横断リンクＬ３１が横断可能な状態となるまで待つよりも、ノードＱに向かう方が効率がよいためである。従って、横断リンクＬ３２が待ち時間ありの場合には、全て経路（Ｇ）が選択され、経路（Ｇ）に含まれる横断リンクＬ３２および横断リンクＬ３４の状態に応じて合計コストが算出される。
【００８９】
横断リンクＬ３１が待ち時間なしの場合には、まず横断リンクＬ３１を渡る経路が選択される。これは、横断可能な横断リンクＬ３１を先に渡った方が、早く目的地ＧＬ２の近い位置へ行けるためである。従って、横断リンクＬ３１を渡り、リンクＬ２７を通過してノードＴへ到達する。そして、ノードＴから横断リンクＬ３３が待ち時間なしの状態であれば、横断リンクＬ３３を渡る経路（Ｉ）が選択され、横断リンクＬ３３が待ち時間ありであれば経路（Ｈ）が選択される。このようにして経路（Ｉ）または経路（Ｈ）が選択されると、経路（Ｉ）または経路（Ｈ）に含まれる横断リンクＬ３１，Ｌ３３，Ｌ３４の状態に応じて合計コストが算出される。
【００９０】
次に、コスト演算部３４１ｃは、横断リンクの待ち時間の発生確率を考慮した合計コストの演算を行う。本実施の形態では、待ち時間あり発生確率値を１／２、待ち時間なし確率値を１／２とする。
【００９１】
ノードＰを始点（経由点）とした経路は、横断リンクＬ３１〜横断リンクＬ３４がそれぞれ待ち時間の発生ありと待ち時間発生なしとの組み合わせとなるため、それぞれの組み合わせ事象が発生する確率は１／１６となる。従って、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ６は、式（６）によって演算することができる。
合計コストＣ６＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＝１０２．５ …（６）
【００９２】
ノードＱを始点（経由点）とした局所経路探索処理は、図２７に示すように、横断リンクＬ３２が待ち時間あり、または待ち時間なしに関わらず、全て経路（Ｇ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ７は、式（７）によって演算することができる。
合計コストＣ７＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＝１１０ …（７）
【００９３】
ノードＴを始点（経由点）とした局所経路探索処理は、図２８に示すように、横断リンクＬ３３が待ち時間ありとなった場合には、横断リンクＬ３４へ向かう経路（Ｈ）、横断リンクＬ３３が待ち時間なしとなった場合には、そのまま横断リンクＬ３３を渡る経路（Ｉ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ８は、式（８）によって演算することができる。
合計コストＣ８＝130×1/16＋110×1/16＋110×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋110×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＝１０５ …（８）
【００９４】
ノードＵを始点（経由点）とした局所経路探索処理は、図２９に示すように、横断リンクＬ３１が待ち時間ありとなった場合には、横断リンクＬ３２へ向かう経路（Ｇ）、横断リンクＬ３１が待ち時間なしとなった場合には、そのまま横断リンクＬ３１を渡り、ノードＵへ向かう経路（Ｈ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ９は、式（９）によって演算することができる。
合計コストＣ９＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＝１０５ …（９）
【００９５】
局所経路探索処理により式（６）から式（９）から得られた待ち時間の発生確率を考慮した合計コストでは、ノードＰを始点（経由点）とした場合が最も小さい値である。従って、出発地ＳＴ２からノードＰへ至り、横断リンクＬ３１の状態に応じて横断リンクＬ３１を渡るか、またはノードＱへ向かうか選択して歩行する方が最適な経路であることを示している。
【００９６】
経路提供部３５は、このように経路が探索されると、推奨経路を周辺地域の地図画像に重畳させる。例えば、図３０に示すように出発地ＳＴ２からノードＰまでに至るまでの一つの経路と、ノードＰにて２つに分岐する経路と、更にノードＴにて２つに分岐する経路とを重畳させた地図画像（図２４に示す経路（Ｇ）〜経路（Ｉ）参照）を、通信部３１を介して携帯電話２０へ送信する。経路（Ｇ）〜経路（Ｉ）は、横断リンクのリンクコストが同じ条件であれば、経路の合計コストは同じである。この場合、経路提供部３５は、特に経路（Ｇ）〜経路（Ｉ）のいずれの経路も強調せずに地図画像に重畳させて提供する。
【００９７】
また、情報報知部３６が音声またはメッセージにより、まずノードＰまで歩行し、更に横断リンクＬ３１の状態に応じて青であれば渡ってよいことを、歩行者に報知することで、更に利便性を向上させることができる。
【００９８】
このように、初期経路探索処理により最初に探索された経路に、横断リンクが含まれているときに、探索条件として、横断リンクのリンクコストを、待ち時間なしコストから待ち時間なしコストへ変更して他の経路を探索して歩行者へ提供することで、歩行者のために好適な経路を探索することが可能である。
また、再探索部３４１の局所経路探索部３４１ｂは、局所経路探索処理において横断リンクの出発地側のノードを、最適経路を探索する始点として最適経路を探索することで、出発地を始点した場合と始点が異なるので、初期経路探索処理では探索できなかった新たな経路を探索することができる。
【００９９】
更に、地図情報記憶部３７に、リンク種別がリンクを通行するための所要時間が不確定な横断リンクのリンクコストとして、待ち時間ありコストと、待ち時間なしコストとを備えた地図データが格納されているので、経路中に横断リンクを示すリンク種別が含まれているときに、待ち時間ありコストまたは待ち時間なしコストに基づいて合計コストを演算することができるので、より実際に即した最適経路の探索を行うことができる。
【０１００】
なお、本実施の形態では、初期経路探索処理により最初に探索された経路に、横断リンクが含まれているときに、変更する探索条件として横断リンクのリンクコストを変更したが、横断リンクを回避することを条件として再探索することも可能である。
また、本実施の形態では、不確定リンクとして横断歩道を示す横断リンクを例に説明したが、通行する際にリンクコストが不確定なリンクであれば、他のリンクでも本発明を適用することが可能である。例えば、列車が通過する時間が一定ではない踏切や、信号機無しの横断歩道、横断歩道はないが横断可能な場所なども不確定リンクとする待ち時間ありコストと待ち時間なしコストして整備することができる。
【０１０１】
次に、電子地図データ生成サーバ４０の動作について、図３１から図４３に基づいて説明する。
図３１に示すように、まず、電子地図データ生成サーバ４０の位置情報収集部４２は、携帯電話２０から送信される歩行者位置情報を地図情報記憶部４８に蓄積する（ステップＳ６１０）。
【０１０２】
次に、蓄積された歩行者位置情報の歩行者識別情報から特定された携帯電話２０が同じ現在位置情報を抽出して、順次受信した現在位置情報により得られた移動軌跡に対して、補間処理を行う（ステップＳ６２０）。この補間処理は、図３２（Ａ）に示すように、３秒間隔に送信される現在位置情報では、現在位置情報が示すそれぞれの構成点Ｐ１が疎となる場合には、図３２（Ｂ）に示すように、軌跡補間部４３が移動軌跡の構成点を密にするために、１秒間隔と想定される位置に補間構成点Ｐ２を生成する。そして軌跡補間部４３は、補間構成点Ｐ２により補間された移動軌跡を地図情報記憶部４８に格納する。この補間方法としては、線形補間法が使用できる。
【０１０３】
次に、横断リンク選定処理により横断待ち確率を整備する横断リンクを選定する（ステップＳ６２１）、更に軌跡抽出部４４により軌跡抽出処理が行われる（ステップＳ６３０）。軌跡抽出処理は、まず、収集された歩行者の移動軌跡のうち横断リンク付近を通過する移動軌跡を抽出する。例えば、横断リンクを中心とした１ｋｍ四方の領域を通過する移動軌跡を抽出する。
【０１０４】
次に、抽出された移動軌跡の中から横断リンクに沿って通過した移動軌跡を抽出する。例えば、図３３（Ａ）に示すように道路Ｒ１にノードａとノードｂとを端点に有する横断リンクＬＫ１が設けられていたとすると、軌跡抽出部４４はまず横断リンクＬＫ１の中間位置を中点ｃに設定する。次に、図３３（Ｂ）に示すように軌跡抽出部４４は、中点ｃを中心した所定半径（例えば、半径２ｍ。）の円内を通過した移動軌跡を選択することで、横断リンクＬＫ１を通過した移動軌跡を抽出することができる。
【０１０５】
しかし、図３３（Ｃ）に示すようにノードａを通過し、中点ｃを中心とした円内を通過した移動軌跡Ｔ２も抽出されてしまう。この場合には、中点ｃを中心とした円内を通過することを条件とするだけでなく、ノードａおよびノードｂのいずれか一方または両方を中心とした円内を通過することを条件とすることで移動軌跡の抽出精度を向上させる。
【０１０６】
このようにして軌跡抽出部４４により抽出された移動軌跡は、移動軌跡情報テーブルとして地図情報記憶部４８に格納される。ここで、移動軌跡情報テーブルについて図３４に基づいて詳細に説明する。
【０１０７】
図３４に示すように、移動軌跡情報テーブルは、軌跡ＩＤと、日付と、到着時刻と、進入時刻と、優先度ポイントとが関連付けられたテーブルである。
軌跡ＩＤは、それぞれの移動軌跡を識別するために付与された識別情報である。日付は収集された日にちを示すもので、現在時間情報に含まれる日付情報である。到着時刻は、歩行者が横断リンクの進入側のノードに到着した時刻を示す情報で、進入側のノードを中心とした円内にいた時刻のうち最も早い時刻である。この到着時刻は、現在時間情報に含まれる時間情報である。進入時刻は、横断リンクに進入した時刻を示す情報で、進入側のノードを中心とした円内にいた時刻のうち最も遅い時刻である。優先度ポイントは、ノイズを除去するために計数されるポイント情報である。初期値は０である。
【０１０８】
この移動軌跡情報テーブルに基づいて、ノイズ除去部４５はノイズ除去処理を行う（ステップＳ６４０）。
このノイズ除去処理は、まず、横断リンクを同時に通行しようとする歩行者を検出して優先度ポイントを増加させる加算処理を行うことで、横断リンクに到着したが、すぐに横断リンクを通行しない移動軌跡に対する優先度ポイントを相対的に下げる処理を行う。これは、歩行者が横断リンクに到着したが、携帯電話２０による通話のために一旦停止した場合や、横断リンク付近に位置する自動販売機を利用するために停止した場合などを排除するためである。
【０１０９】
図３５に示すように、ノイズ除去部４５は、まず軌跡の選択を行う（ステップＳ７１０）。例えば軌跡ＩＤが「００１０１」である移動軌跡（図３４参照）を対象移動軌跡として着目する。次に、軌跡ＩＤが「００１０１」の移動軌跡が横断リンクの進入前に停止したか否かを判定する（ステップＳ７２０）。この判定は、進入時刻と到着時刻との差分が所定値より大きい場合に停止していたとすることができる。
【０１１０】
例えば、「００１０１」の移動軌跡は、到着時刻が１５：３０：００で、進入時刻が１５：３０：４０であるので、４０秒間ほど横断リンクの進入側のノードを中心とした円内にいたことになる。従って、「００１０１」の移動軌跡は、４０秒停止していたことになる。例えば、停止を５秒以上であるとしたときには、「００１０１」の移動軌跡は４０秒間停止していたことになるので、横断リンクの進入側のノードで停止していたと判定することができる。
【０１１１】
次に、進入時刻が同じ他の移動軌跡があるか否かを判定する（ステップＳ７３０）。進入時刻が同じ移動軌跡が他にある場合には、その移動軌跡の優先度ポイントも増加させる加算処理を行う。これは、複数の歩行者が同時に横断リンクに進入したということは、横断リンクが待ちの状態から待ちなしの状態へ遷移して一斉に移動し始めたことを示す確度が高いためである。
【０１１２】
図３４に示す移動軌跡情報テーブルでは、「００１０１」の移動軌跡は、軌跡ＩＤが「００１０２」，「００１０４」，「００１０５」の移動軌跡と進入時刻が同時刻なので、図３６（Ａ）に示すように、進入前の停止が「あり」で、同時進入する軌跡が「あり」なので、「００１０１」の移動軌跡の優先度＋５０ポイント加算される。他の軌跡「００１０２」，「００１０４」，「００１０５」についても同様な処理が行なわれ、これらの移動軌跡の優先度も＋５０ポイント加算される（ステップＳ７４０）。
また、「００１０６」の移動軌跡は、「００１０７」の移動軌跡と進入時刻が同時刻なので、「００１０６」の移動軌跡が選択された処理のときに、＋５０ポイント加算される。
【０１１３】
次に、対象軌跡として全ての移動軌跡を処理したか否かが判定される（ステップＳ７５０）。全ての移動軌跡について処理していれば終了する。処理していなければステップＳ７１０へ移行する。
【０１１４】
例えば、軌跡ＩＤが「００１０５」の移動軌跡であれば、到着時刻と進入時刻とが同時刻であるので、横断リンクの進入側のノードでは一旦停止していないため優先度ポイントが＋５０加算される（ステップＳ７６０）。
【０１１５】
また、軌跡ＩＤが「００１０３」の移動軌跡は、進入時刻と到着時刻との差分が１５秒なので、一旦停止したものと判定されるが、進入時刻が他の移動軌跡と異なるので、進入側のノードでの停止は、赤信号による待ちではなく、他の目的によるものと推定できるため、優先度ポイントを増加する加算処理は行わず、ステップＳ７５０へ移行する。このため赤信号待ち以外の理由で待っている場合には、他の場合と比べて相対的に優先度ポイントが加算されないままとなる。このようにして、図３６（Ｂ）の移動軌跡情報テーブルに示すように優先度ポイントが加算される。
【０１１６】
次に、ノイズ除去部４５は、ノイズ除去処理として車両の移動軌跡を利用して優先度ポイントを増加させる加算処理を行う。この加算処理は、図３７に示すように、車両Ｃが横断歩道を通過する際に、信号機ＳＧ１が赤信号であれば、逆に歩行者側の信号機ＳＧ２が青信号の状態であることを利用するものである。
まず、図３８に示すように、予め位置情報収集部４２が、車両に搭載されたナビゲーション装置やプローブ車両からの車両位置情報を、通信部４１を介して収集し、地図情報記憶部４８へ格納する（ステップＳ８１０）。次に、必要に応じて軌跡補間部４３が、蓄積された車両位置情報のうち、車両識別情報から特定された車両が同じ現在位置情報を抽出して、車両位置情報に含まれる現在位置情報により得られる軌跡に対して補間処理を行う（ステップＳ８２０）。
【０１１７】
次に、軌跡抽出部４４が軌跡抽出処理を行う（ステップＳ８３０）。軌跡抽出処理は、まず歩行者の場合と同様に、収集された車両の移動軌跡のうち横断リンク付近を通過する移動軌跡を抽出する。例えば、横断リンクを中心とする１ｋｍ四方の領域を通過する移動軌跡を抽出する。次に、抽出された移動軌跡の中から横断リンクを横切る移動軌跡を抽出する（図３７（Ｂ）参照）。
【０１１８】
軌跡抽出部４４は、抽出した横断リンクを横切る車両の移動軌跡のうち、横断リンクの手前で停止した移動軌跡の抽出を行う（ステップＳ８４０）。ここで停止とは、時間経過による車両位置の変化が小さいことをいう。軌跡抽出部４４は、抽出された移動軌跡に基づき、対象となる横断リンクに対して車両ごとに停止時間帯を記録したテーブル（図３９（Ａ）参照）を作成し、このテーブルに基づいて対象の横断リンクの車両停止時間テーブル（図３９（Ｂ）参照）を作成する（ステップＳ８５０）。
図３９（Ａ）に示す例では、車両Ａが、車両Ａ〜車両Ｃの中で最も早く横断リンクに到着し、そして最も早く移動を開始して横断リンクを横切っていることから、車両の停止時間、つまり横断リンクで歩行者が通行可能である状態が１５：３０：３５〜１５：３１：００であることがわかる（停止時間Ａ）。
ここまでの処理（ステップＳ８１０からステップＳ８５０）は、図３１に示す位置情報収集部４２による位置情報の収集処理（ステップＳ６１０）から軌跡抽出部４４による軌跡抽出処理（ステップＳ６３０）と並行して行われる。
【０１１９】
ノイズ除去部４５は、車両停止時間テーブルに基づいて移動軌跡情報テーブルの優先度ポイントを増加させる加算処理を行う（ステップＳ８６０）。この加算処理は、図４０に示す移動軌跡情報テーブルの進入時刻が、図３９（Ｂ）に示す車両停止時間テーブルの停止時間に含まれていれば、車両が停止した後に、歩行者が横断リンク内に進入したことを示しているので、優先度ポイントを＋２０ポイント加算する。
このようにして、車両の移動軌跡を利用した優先度ポイントを増加させる加算処理を行う。
【０１２０】
次に、ノイズ除去部４５は、ノイズ除去処理として横断リンクへ進入する前に通過したリンク（以下、進入前リンクと称す。）と、横断リンクから退出した後に通過したリンク（以下、退出後リンクと称す。）とに応じて、優先度ポイントを増加させる加算処理を行う。
【０１２１】
この加算処理は、図４１（Ａ）に示すように対象となる横断リンクＬＫ１に、曲がりながら進入したり退出したりした移動軌跡Ｔ４よりも、直線的に通過した移動軌跡Ｔ５の優先度を上げるために行う処理である。これは、移動軌跡Ｔ４が示すように、歩行者が、まず横断リンクＬＫ２を横断しようとしたが赤信号であったため道路Ｒ２に沿って歩き、横断リンクＬＫ１へ通行可能な状態となるまでタイミングを図りながら向かった可能性があるためである。また、歩行者が、横断リンクＬＫ１を横断した後に道路Ｒ２に沿って歩行する場合には、次の横断リンクを探しながら渡ろうとする可能性があるためである。
【０１２２】
従って、図４１（Ｂ）に示すように、移動軌跡が通過する、横断リンクＬＫ２と、横断リンクＬＫ１へ進入する進入前リンクＬＫ３とのなす角αが、１８０°に近い所定角度以上であれば、その移動軌跡の優先度ポイントに＋１５ポイント加算する。また、図４１（Ｃ）に示すように、移動軌跡が通過した、横断リンクＬＫ１と、横断リンクＬＫ１から退出する退出後リンクＬＫ４とのなす角βが、１８０°に近い所定角度以上であれば、その移動軌跡の優先度ポイントに＋１５ポイント加算する。
【０１２３】
例えば、それぞれの移動軌跡が図４１（Ｄ）に示すような軌跡である場合には、軌跡ＩＤが「００１０２」，「００１０４」，「００１０５」は、横断リンクＬＫ１に対して進入時のなす角と退出時のなす角が両方とも１８０°であるので、優先度ポイントとして進入時と退出時とで合計＋３０ポイントが加算される。また軌跡ＩＤが「００１０１」，「００１０７」は進入時と退出時とでほぼ直角なので加算されない。軌跡ＩＤが「００１０３」は進入時が、「００１０６」は退出時が横断リンクＬＫ１に対してなす角が１８０°であるので、＋１５ポイントのみ加算される。このようにノイズ除去部４５によって優先度ポイントを増加させる加算処理が行われた結果を、図４２に示す。
【０１２４】
図４１（Ａ）に示す横断リンクＬＫ１，ＬＫ２は、一本の道路Ｒ２に沿って敷設された一方の歩道から他方の歩道に並行して設けられている。ここで、図４３に示すような道幅の広い道路Ｒ２１，Ｒ２２同士が交差する交差点では、横断リンクＬＫ３〜ＬＫ６を連結するリンク（以下、このリンクを交差点内リンクＬＫＣと称す。）が存在する。このような場合には、移動軌跡が通過する横断リンクＬＫ３〜ＬＫ６と交差点リンクＬＫＣとのなす角だけでは判断できない。従って、移動軌跡が次に通過するリンクまでを考慮する。つまり、横断リンクＬＫ３〜ＬＫ６のいずれかを渡った後に交差点内リンクＬＫＣを通過し、更に次のどのリンクを移動軌跡が通過したかによって、優先度ポイントの加算を行う。例えば、交差点内リンクＬＫＣを通過した後に、横断リンクＬＫ３〜ＬＫ６を通過したのであれば、加算せず、通常のリンクへ向かったのであれば＋１５ポイント加算するなどである。
【０１２５】
次に、ノイズ除去部４５は、加算された移動軌跡情報テーブルの優先度ポイントに基づいてノイズの除去を行う。例えば、優先度ポイントが高い移動軌跡のみを採用し、他の移動軌跡は削除することでノイズ除去を行うことができる。優先度ポイントが高い移動軌跡とは、優先度ポイント上位７０％以内に含まれる移動軌跡とすることができる。
また、優先度ポイントが高い移動軌跡に対して重み付けを行ってもよい。重み付けは、優先度ポイント上位４０％の移動軌跡の重みを２倍とするなどで、確率演算処理を行う際に優先度ポイント上位４０％の移動軌跡を２重にカウントすることができる。優先度ポイントが高い移動軌跡に対して重み付けを行う場合には、ノイズ除去部４５は重み付けを行う旨のフラグを立てることで、確率演算部４６に指示する。
この上位７０％や、上位４０％などの範囲は適宜決定することが可能である。
【０１２６】
ノイズ除去部４５によるノイズ除去処理が終了すると、確率演算部４６による確率演算処理を行う（ステップＳ６５０）。
確率演算部４６による確率演算処理は、まず、横断リンクに到着してから横断リンクへ進入するまでの横断待ち時間として、移動軌跡情報テーブルの各移動軌跡の進入時刻から到着時刻を引いた差分値を演算する。次に、確率演算部４６は、横断待ち時間を所定値ごとに区分した範囲に含まれる移動軌跡のカウントを行う。本実施の形態では、横断待ち時間が０〜１０秒、１０〜２０秒と、１０秒ごとの範囲で集計を行っている。このように集計された移動軌跡を図４４（Ａ）に示す。また、図４４（Ｂ）に同図（Ａ）の表に基づいて作成されたヒストグラムを示す。図４４（Ａ）では、一つの移動軌跡を一人として示している。このとき、重み付けを行う旨のフラグが立っていた場合には、確率演算部４６は優先度ポイント上位４０％に含まれる移動軌跡のカウントを２重にカウントする。
【０１２７】
次に、確率演算部４６は、待ち時間あり発生確率値を演算する。この待ち時間あり発生確率値は、以下の式から算出することができる。
待ち時間あり発生確率値＝１−（待ちなし移動軌跡の総数）÷（移動軌跡の総数）
ここで、待ちなし移動軌跡とは、横断待ち時間が閾値以下である移動軌跡である。本実施の形態では閾値を１０秒としている。つまり、横断待ち時間が１０秒以下であれば、横断リンクによる待ちが発生しなかった移動軌跡である。
【０１２８】
図４４（Ａ）の例では、待ち時間あり発生確率値＝１−（１０５÷２６０）から、待ち時間あり発生確率値が約０．６０であることが算出される。従って、待ち時間なし発生確率値は、約０．４となり、横断リンクの実際の待ち時間あり発生確率値および待ち時間なし発生確率は、１／２ではないことがわかる。
【０１２９】
このように順次、歩行者からの歩行者位置情報と車両からの車両位置情報とを収集し、対象となる横断リンクを変更しながら地図情報記憶部４８の待ち時間あり発生確率値および待ち時間なし発生確率値を設定または変更する。
【０１３０】
地図データ送信部４７は、経路案内サーバ３０の地図データ更新部３８と通信して、設定または変更された横断リンクの待ち時間あり発生確率値および待ち時間なし発生確率値を経路案内サーバ３０へ、対象となる横断リンクを識別する情報と共に送信する。地図データ更新部３８は、受信した待ち時間あり発生確率値および待ち時間なし発生確率値を地図情報記憶部３７を参照して更新する。
【０１３１】
このように、電子地図データ生成サーバ４０は、実際の状況に応じた不確定リンクである横断リンクの待ち時間あり発生確率値を算出して、経路案内サーバ３０の経路探索を行う際の精度を向上させることができると共に、出発地から目的地までの到達予測時間の精度を向上させることができる。
【０１３２】
また、優先度ポイントを、横断リンクを同時に通行しようとする歩行者を検出して増加したり、車両の移動軌跡を利用して増加したり、進入前リンクや退出後リンクに応じて増加したりすることで、精度として信頼性の低い移動軌跡の優先度ポイントを相対的に下げることができる。
【０１３３】
本実施の形態では、優先度ポイントを増加させる加算を行うことで、ノイズとなる移動軌跡の優先度ポイントを相対的に低下させているが、収集された歩行者の移動軌跡に予め所定ポイントを付与しておき、加算処理の代わりに減算処理を行うようにして、最終的に優先度ポイントが低いものを上位とすることも可能である。
また、本実施の形態では、経路案内サーバ３０と電子地図データ生成サーバ４０とは別体としているが、同じサーバ内に構築してもよい。
【産業上の利用可能性】
【０１３４】
本発明は、歩行者が携行する携帯電話やＰＤＡ（Personal Digital Assistant）が通信回線を介して経路探索結果を送信するサーバや、携帯型ナビゲーション装置などに好適である。
【図面の簡単な説明】
【０１３５】
【図１】経路案内システムを示す図である。
【図２】携帯電話の構成を示すブロック部である。
【図３】経路案内サーバの構成を示すブロック図である。
【図４】地図データ生成サーバを示すブロック図である。
【図５】経路案内サーバの動作全体を説明するためのフローチャートである。
【図６】経路探索処理例（１）における経路例を示す図である。
【図７】初期経路探索処理の動作を説明するためのフローチャートである。
【図８】探索された経路（Ａ）を示す図である。
【図９】探索された経路（Ｂ）を示す図である。
【図１０】初期経路探索処理により探索された経路を示す図である。
【図１１】初期経路探索処理により探索された経路の合計コストを示す表である。
【図１２】局所経路探索処理の動作を説明するためのフローチャートである。
【図１３】始点となるノードを示す図である。
【図１４】局所経路探索処理における経路探索を説明するためのフローチャートである。
【図１５】（Ａ）〜（Ｄ）は局所経路グループごとの経路を示す図である。
【図１６】（Ａ）〜（Ｄ）は局所経路グループごとの局所コストと合計コストとを示す表である。
【図１７】ノードＨを始点としたときの合計コストを示す表である。
【図１８】ノードＧを始点としたときの合計コストを示す表である。
【図１９】ノードＦを始点としたときの合計コストを示す表である。
【図２０】ノードＥを始点としたときの合計コストを示す表である。
【図２１】経路図１における推奨経路の案内例を示す図である。
【図２２】経路探索処理例（２）における経路例を示す図である。
【図２３】初期経路探索処理の動作を説明するためのフローチャートである。
【図２４】探索された経路（Ｇ）〜経路（Ｉ）を示す図である。
【図２５】初期経路探索処理により探索された経路の合計コストを示す表である。
【図２６】ノードＰを始点としたときの合計コストを示す表である。
【図２７】ノードＱを始点としたときの合計コストを示す表である。
【図２８】ノードＴを始点としたときの合計コストを示す表である。
【図２９】ノードＵを始点としたときの合計コストを示す表である。
【図３０】経路図２における推奨経路の案内例を示す図である。
【図３１】電子地図データ生成サーバの動作を説明するためのフローチャートである。
【図３２】（Ａ）は補間処理を行う前の移動軌跡を示す図、（Ｂ）は補間処理を行った後の移動軌跡を示す図である。
【図３３】（Ａ）は道路に設けられた横断リンクを示す図、（Ｂ）は横断リンクを通過した移動軌跡の一例を示す図、（Ｃ）は横断リンクを通過していない移動軌跡の一例を示す図である。
【図３４】移動軌跡情報テーブルを示す図である。
【図３５】ノイズ除去処理を動作を説明するためのフローチャートである。
【図３６】（Ａ）は優先度ポイントの加算方法を説明するための図、（Ｂ）は進入時刻が同じ移動軌跡に対して加算された移動軌跡情報テーブルを示す図である。
【図３７】（Ａ）および（Ｂ）は車両を利用したノイズ除去処理を説明するための図である。
【図３８】車両の移動軌跡を利用したノイズ除去処理の動作を説明するためのフローチャートである。
【図３９】（Ａ）は車両ごとに停止時間帯を記録したテーブルを示す図、（Ｂ）は横断リンクの車両停止時間テーブルを示す図である。
【図４０】車両停止時間テーブルに基づいて優先度ポイントを増加する加算処理を行った移動軌跡情報テーブルを示す図である。
【図４１】（Ａ）は曲がりながら進入したり退出したりした移動軌跡と、直線的に通過した移動軌跡とを示す図、（Ｂ）は進入前リンクと横断リンクとのなす角を示す図、（Ｃ）は退出後リンクと横断リンクとのなす角を示す図、（Ｄ）は移動軌跡ごとの加算処理を説明するための図である。
【図４２】進入前リンクおよび退出後リンクに基づいて優先度ポイントを増加する加算処理を行った移動軌跡情報テーブルを示す図である。
【図４３】交差点内リンクがある交差点を示す図である。
【図４４】（Ａ）は横断待ち時間を所定値ごとに区分した範囲に含まれる移動軌跡のカウントを行った表であり、（Ｂ）は（Ａ）に示す表に基づいて作成されたヒストグラムである。
【符号の説明】
【０１３６】
３０…経路案内サーバ、３４０…最適経路探索部、３４１…再探索部、３７…地図情報記憶部
【技術分野】
【０００１】
本発明は、歩行者が出発地から目的地までを歩く際に、好適な経路を探索することが可能な経路探索装置、経路探索方法、経路探索プログラムおよび地図データに関する。
【背景技術】
【０００２】
地図上の経路を探索することで、出発地から目的地までを短時間で到達することが可能な経路探索装置が知られている。
例えば、特許文献１には、地図データや公共交通機関に関するデータに基づいて、距離コストを道路種別に応じて設定された車速で除算することで車両経路のコストを時間単位とすると共に、駅間の所要時間や待ち時間を加算することで公共交通機関経路のコストも時間単位とし、車両経路と公共交通機関経路との比較を可能とする経路案内装置が記載されている。
【０００３】
特許文献１の経路案内装置では、公共交通機関経路のコストを時間単位で算出するためのデータとして、時刻表データや周辺データなどを用いている。周辺データとは、公共交通機関が鉄道の場合では、各駅の構内施設に関するデータであり、乗り換えに必要な階段の有無やエスカレータ、エレベータの有無、駅の出入口からプラットホームまでの所要時間を示すデータである。これらは、鉄道を利用するときの容易度を評価する際の基準となるもので、例えば、乗り換えに必要な階段数が増大すればするほどコストとしては増大するように設定されている。また、エレベータやエスカレータの数が多ければ多いほど、利用の容易度は大きくなりコストとしては低下するように設定されている。
【０００４】
【特許文献１】特開２００１−１６５６８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１に記載の経路案内装置では、出発地から目的地までの移動が車両だけでなく公共交通機関を利用する場合が考慮されている。公共交通機関を利用する場合に考慮されるコストは、時刻表データや駅の構内施設に関する周辺データなどから、駅での待ち時間や乗り換え時間などの待ち時間を演算することで決定されるので、現在時刻がわかれば固定的に目的地までのコストを演算することができる。
しかし、出発地から目的地までを徒歩で移動する場合には、車両や公共交通機関とは異なる考慮が必要である。
【０００６】
例えば、横断歩道が設置された道幅の広い通りを横切ることが、案内された目的地までの最適経路である場合には、歩行者用信号機の赤信号に遭遇してしまえば、すぐには横断できないことがある。通りが交通量の多い大通りであれば赤信号が長く、多大な時間の損失が発生する。そうなると、その横断歩道を渡ることが最適経路であったとしても、迂回した方が早く目的地まで到着できることがあり、歩行者にとっては案内された経路が満足のいかない結果となってしまう。つまり、出発地から目的地までを徒歩で移動する際のコストは、予告無く状況が変化するために不確実な面があるので、コストデータとして準備することが困難である、従って、公共交通機関を利用する場合と異なる特異性がある。
【０００７】
そこで本発明は、歩行者のために好適な経路を探索することが可能な経路探索装置、経路探索方法、経路探索プログラムおよび地図データを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の経路案内装置は、歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納される記憶手段と、出発地から目的地までの各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索手段と、前記最適経路探索手段に最適経路を探索させ、当該最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、最適経路探索手段の探索条件を変更して、一以上の他の経路を前記最適経路探索手段に探索させ、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段とを備えたことを特徴とする。
【０００９】
本発明は、最適経路探索手段が出発地から目的地までに含まれるリンクのリンクコストデータから合計コストを演算して最適経路を探索したときに、この最適経路に不確定リンクが含まれているときには、最適経路に所要時間が不確定な要素が含まれているため、再探索手段が、最適経路探索手段の探索条件を変更して、一以上の他の経路を探索することで、最適経路と同等またはより以上の最適な経路を経路候補とすることができる。本発明は、経路探索方法としても、経路探索プログラムとしても、実施することが可能である。
【００１０】
前記再探索手段は、最適経路探索手段の探索条件を変更して、前記一以上の他の経路を探索するときに、前記最適経路に含まれる不確定リンクのリンクコストデータを変更して探索することができる。再探索手段が最適経路に含まれる不確定リンクのリンクコストデータを変更すると、最適経路として探索された経路の合計コストが変更されるので、再探索手段が出発地から目的地までの経路を、再度、最適探索手段に探索させることで、一以上の他の経路を探索することができる。
【００１１】
前記記憶手段には、前記リンク種別が不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータと、待ち時間が発生しない場合の待ち時間なしコストデータとが格納され、前記再探索手段は、前記最適経路探索手段に不確定リンクのリンクコストデータを変更して探索させるときに、前記待ち時間なしコストデータから前記待ち時間ありコストデータへ変更して合計コストを演算させるのが望ましい。再探索手段が、不確定リンクのリンクコストデータを、記憶手段に格納されている待ち時間なしコストと待ち時間ありコストデータとに設定することで、不確定リンクに応じたリンクコストを設定することができる。
【００１２】
前記再検索手段は、前記一以上の他の経路について探索するときに、（Ａ）前記最適経路探索手段により最初に探索された最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して新たな最適経路を前記最適経路探索手段に探索させ、（Ｂ）前記最適経路探索手段により新たな最適経路が探索されると、当該新たな最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して、再度、前記最適経路探索手段により最適経路を探索させ、（Ｃ）前記最適経路探索手段により探索された経路が、以前に探索されていない新たな経路であれば、更に（Ｂ）を処理し、（Ｄ）前記最適経路探索手段により探索された経路が、探索された経路に含まれている場合には、探索を終了するのが望ましい。
再探索手段は、最適経路に不確定リンクが含まれている場合には、当該最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータにして新たな最適経路の探索をする。そうすることで、新たな最適経路として好適な経路が存在するか否かが確かめられる。従って、再探索手段は、新たな最適経路が以前に探索された最適経路に一致するまで探索を繰り返すことで、不確定リンクを渡っても目的地まで早く到達できるかもしれない経路を探索することができる。
【００１３】
前記再探索手段は、探索された新たな最適経路に不確定リンクが含まれていない場合に、探索を終了するのが望ましい。そうすることで、再探索手段は、他の経路より合計コストが高いかもしれないが、不確定リンクを通行する必要のない経路を探索することができる。
【００１４】
前記再探索手段は、前記経路候補に含まれるそれぞれの不確定リンクの出発地側のノードを始点として設定し、前記最適経路探索手段にそれぞれの始点から目的地までの最適経路について局所経路として探索する局所経路探索処理を実行して、それぞれの始点ごとの局所経路グループを探索するのが望ましい。再探索手段が、不確定リンクの出発地側のノードを最適経路を探索する始点とすることで、出発地を始点した場合と始点が異なるので、新たな経路を探索することができる。
【００１５】
また、前記再探索手段は、前記局所経路探索処理を実行するときに、前記最適経路探索手段により前記（Ａ）から（Ｄ）までの処理を実行して前記局所経路を探索することができる。
【００１６】
前記記憶手段には、前記不確定リンクごとに待ち時間の発生の有無の確率を示す待ち発生確率値が格納され、前記再探索手段は、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択し、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算し、前記待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループの合計コストを演算し、前記局所経路グループごとの合計コストに基づいて推奨経路を決定するのが望ましい。
再探索手段は、まず、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択する。次に、再探索手段は、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算する。次に、再探索手段は、待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループの合計コストを演算する。そして、再探索手段は、局所経路グループごとの合計コストに基づいて推奨経路を決定することで、最良の局所経路グループを選択することができる。つまり、最初に探索された最適経路では、不確定リンクによる遅れが発生すると回避できない可能性があるが、最良の局所経路グループの始点まで進行しておけば、不確定リンクに到達した時点で待ちの状態となったとしても、他の経路へ分岐することが可能であるので、少し遠回りとなってしまうかもしればないが、なるべく待ちが発生しないような経路を選択することで、結果として目的地まで早く到達できる経路を探索することができる。
【００１７】
また、本発明の地図データは、コンピュータによる経路探索に利用される地図データ であって、歩行路であるリンクを表すリンクデータおよび該リンクの端点であるノードデータと、前記リンクの種別を示すためのリンク種別データと、前記リンクごとに設定されたリンクコストデータと、前記リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータ、および待ち時間が発生しない場合の待ち時間なしコストデータとを備え、コンピュータが、出発地から目的地までの各経路に含まれるリンクデータに設定されたリンクコストデータを読み込み、読み込まれたリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索し、当該最適経路に含まれるリンク種別データを読み込み、読み込まれたリンク種別データがリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、該不確定リンクに対応するコストデータを待ち時間なしコストデータから待ち時間ありコストデータへ変更して合計コストを演算して一以上の他の経路を探索し、前記最適経路と共に前記一以上の他の経路を経路候補とすることを特徴とする。
このような構成の地図データとすることで、経路中に不確定リンクを示すリンク種別が含まれているときに、待ち時間ありコストまたは待ち時間なしコストに基づいて合計コストを演算することができるので、より実際に即した最適経路の探索を行うことができる。
【発明の効果】
【００１８】
本発明は、最適経路に所要時間が不確定な要素が含まれているため、一以上の他の経路を探索することで、最適経路と同等またはより以上の最適な経路を経路候補とすることができるので、歩行者のために好適な経路を探索することが可能である。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態に係る経路案内システムを図面に基づいて説明する。
図１に示すように、経路案内システム１０は、ユーザである歩行者が携行する携帯電話２０と、経路探索装置として機能し、探索された経路を案内する経路案内サーバ３０と、電子地図データ生成装置として機能する電子地図データ生成サーバ４０とが、それぞれ電気通信回線の一例であるインターネットＷを介して通信可能に接続されている。ユーザは、携帯電話２０を携行して、経路案内サーバ３０から送信された地図画像を参照することで、目的地までを歩行する。
【００２０】
携帯電話２０は、図２に示すように、携帯端末として機能するものであり、通信部２１と、通話部２２と、インターネット制御部２３と、ＧＰＳ（Global Positioning System）部２４と、時計部２５と、操作部２６と、表示部２７と、主制御部２８とを備えている。
【００２１】
通信部２１は、無線信号により基地局または中継局と通信する無線手段として機能するものであり、送信パケットを変調したり、受信パケットに復調したりする機能を備えている。
通話部２２は、電話機能を実現するもので、図示しないマイクからの音声信号を送信パケットに変換したり、受信パケットから音声データを抽出してスピーカーから出力したりする機能を備えている。
インターネット制御部２３は、インターネットＷへのアクセス機能を実現するもので、ＵＲＬ（Uniform Resource Locator）に基づいてウェブサイトへアクセスして、表示部２７に表示されたブラウザにウェブサイトからの情報を表示する機能を備えている。
ＧＰＳ部２４は、現在位置を現在位置情報として出力する機能を備えている。現在位置情報としては、経度情報と緯度情報とすることができる。ＧＰＳ部２４は、ＧＰＳ（全地球測位システム）とする以外に、衛星測位システム（ガリレオ）なども採用できる。
時計部２５は、現在時刻を現在時刻情報として出力する機能を備えている。
操作部２６は、数字キー、記号キー、機能キー、十字キー（カーソルキーまたは選択キー）などを備え、入力手段として機能するものである。表示部２７は、表示データを表示する機能を備えている。表示部２７としては、ＬＣＤ（Liquid Crystal Display）や有機ＥＬ（Organic Electro-Luminescence）などが使用できる。主制御部２８は、携帯電話２０全体を統括制御する機能を備えている。主制御部２８は、ＧＰＳ部２４からの現在位置情報と、時計部２５からの現在時刻情報と、送信した携帯電話２０を特定する歩行者識別情報とを歩行者情報として、電子地図データ生成サーバ４０へ通信部２１を介して、所定時間間隔ごとに送信する機能を備えている。この所定時間間隔は、本実施の形態では例えば３秒とすることができる。
【００２２】
次に、経路案内サーバ３０の構成について、図３に基づいて説明する。コンピュータである経路案内サーバ３０は、経路探索プログラムを動作させることで、地図画像上に経路を重畳させたウェブページを送信する機能を備えている。
【００２３】
経路案内サーバ３０は、上述した機能を実現するために、通信部３１と、地図要求受付部３２と、地図送信部３３と、経路探索部３４と、経路提供部３５と、地図送信部３３と、情報報知部３６と、地図情報記憶部３７と、地図データ更新部３８とを備えている。
通信部３１は、インターネットＷを介して携帯電話２０と通信する機能を備えており、例えば、ＡＤＳＬ（Asymmetric Digital Subscriber Line）や、ＦＴＴＰ（Fiber To The Premises）と接続するＬＡＮ（Local Area Network）とすることができる。
地図要求受付部３２は、インターネットＷを介して送信された地図画像の表示要求コマンドを受け付け、所定地域周辺の地図画像の要求であれば、表示要求コマンドと共に受信した位置情報を地図送信部３３へ地図画像の送信を指示する。また、地図要求受付部３２は、経路探索であれば、表示要求コマンドと共に受信した出発地情報および目的地情報に基づいて経路探索部３４へ経路探索を指示する。
地図送信部３３は、地図情報記憶部３７から読み込んだ地図画像を通信部３１を介してインターネットＷに送信する機能を備えている。
【００２４】
経路探索部３４は、ユーザから指定されたコマンドに基づき経路探索を行う機能を備えている。経路探索には、例えば、ダイクストラ法などの周知の方法が利用可能である。この経路探索部３４は、最適経路探索部３４０と、再探索部３４１とを備えている。
最適経路探索部３４０は、出発地から目的地までの経路のうち、合計コストが最も小さい経路を最適経路として探索する最適経路探索手段として機能するものである。
再探索部３４１は、最適経路探索部３４０により最初に探索された最適経路に、通行するときの所要時間が不確定な不確定リンクが含まれるか否かを判定し、不確定リンクが含まれていれば、一以上の他の経路を最適経路探索部３４０に探索させる再探索手段として機能するものである。再探索部３４１は、初期経路探索部３４１ａと、局所経路探索部３４１ｂと、コスト演算部３４１ｃを備えている。
【００２５】
初期経路探索部３４１ａは、初期経路探索処理を実行することで、最適経路探索部３４０に探索させた最適経路以外の一以上の他の経路を探索する機能を備えている。
局所経路探索部３４１ｂは、局所経路探索処理を実行することで、初期経路探索部３４１ａにより探索された一以上の他の経路について、更に局所的な経路探索を行う機能を備えている。
コスト演算部３４１ｃは、局所経路探索部３４１ｂにより探索された局所経路グループに基づいて、不確定リンクの待ち発生確率を考慮した合計コストを演算する機能を備えている。
経路提供部３５は、経路探索部３４が探索した経路を地図画像に重畳させる機能を備えている。情報報知部３６は、文字や音声などのメッセージを通信部３１を介してインターネットＷへ送信する機能を備えている。
【００２６】
地図情報記憶部３７は、経路探索や地図表示に使用される電子地図データベースである。この地図情報記憶部３７は、大容量で高速アクセスが可能なハードディスクドライブを採用することができる。地図情報記憶部３７には、車路や歩行路を表すリンクデータと、このリンクの端点であるノードデータと、リンクの種別を示すリンク種別データと、リンクごとに設定されたリンクコストデータとを含む地図データが、それぞれ関連付けられて格納されている。リンクコストデータは、リンク種別データが不確定リンクを示す場合には、待ち時間が発生する場合のコストである待ち時間ありコストデータと、待ち時間が発生しない場合のコストである待ち時間なしコストデータとが設けられている。
また、地図情報記憶部３７には、リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクである場合には、このリンクに、待ち時間が発生する確率を示す待ち時間あり発生確率値と、待ち時間が発生しない確率を示す待ち時間なし発生確率値とが関連付けられている。この待ち時間あり発生確率と待ち時間なし発生確率は、後述するように、実際に横断歩道を歩行している歩行者の移動軌跡情報を用いて作成されても良い。また、横断歩道にある信号機は一般的に、待ち時間がある場合とない場合の２つの場合に大別されるため、例えば待ち時間ありの場合の確率を０．５、待ち時間のない場合の確率を０．５と予め設定しておいても良い。また、予め設定する基準は、例えば横断歩道が、渡ろうとする道路に交わる他の道路と平行な場合と単純に道路を横断する場合で差を設けても良い、さらに、横断しようとする道路に交わる他の道路と平行な横断歩道の場合には交わる道路の道路種別や幅と横断する道路の種別や幅に応じて差異を設けても良い。また、３差路以上の交差点の場合には交差点にかかる各信号の待ちなし確率を１／３、待ちあり確率を２／３とする等、交差点の形状によって均等に待ちありと待ちなしの確率を設定しても良い。こうすることによって、予めデータを作成することなく、現実の状況により近い，待ちありおよび待ちなしの確率を用いた経路案内を行うことが可能となる。
【００２７】
地図データ更新部３８は、通信部３１を介して電子地図データ生成サーバ４０と通信して、地図情報記憶部３７に格納されている待ち時間あり発生確率値と、時間なし発生確率値を更新する機能を備えている。
【００２８】
次に、電子地図データ生成サーバ４０の構成について、図４に基づいて説明する。コンピュータである電子地図データ生成サーバ４０は、電子地図データ生成プログラムを動作させることで、実際の状況に応じた不確定リンクの待ち時間あり発生確率値を算出して、経路案内サーバ３０の経路探索を行う際の精度を向上させる機能を備えている。
【００２９】
電子地図データ生成サーバ４０は、上述した機能を実現するために、通信部４１と、位置情報収集部４２と、軌跡補間部４３と、軌跡抽出部４４と、ノイズ除去部４５と、確率演算部４６と、地図データ送信部４７と、地図情報記憶部４８とを備えている。
通信部４１は、インターネットＷを介して携帯電話２０と通信する機能を備えており、経路案内サーバ３０と同様に、ＬＡＮとすることができる。
位置情報収集部４２は、携帯電話２０からの歩行者位置情報、または図示しない車両に搭載されたナビゲーション装置やプローブ車両からの車両位置情報を、通信部４１を介して収集し、記憶手段である地図情報記憶部４８へ収集した歩行者位置情報および車両位置情報を格納する機能を備えている。
軌跡補間部４３は、順次受信した歩行者位置情報または車両位置情報に含まれる現在位置情報により得られた移動軌跡に対して、現在位置情報の送信時間間隔が大きい場合、現在位置情報が示すそれぞれの位置の間を補間して、移動軌跡の構成点を密にする機能を備えている。
軌跡抽出部４４は、現在位置情報が描く軌跡が不確定リンクを通過したものか否かを判定し、不確定リンクを通過した軌跡を抽出する機能を備えている。
ノイズ除去部４５は、軌跡抽出部４４により抽出された軌跡から、不確定リンクの待ち発生確率値の精度を向上させるのに阻害となる軌跡（以下、この軌跡をノイズと称すことがある。）を除外する機能を備えている。
確率演算部４６は、ノイズ除去部４５によりノイズが除去され、残った軌跡から不確定リンクの待ち発生確率値を演算する機能を備えている。
地図データ送信部４７は、地図情報記憶部４８に格納された不確定リンクの待ち発生確率値を経路案内サーバ３０へ通信部４１を介して送信する機能を備えている。
地図情報記憶部４８には、車路や歩行路を表すリンクデータと、このリンクの端点であるノードデータと、リンクの種別を示すリンク種別データとを含む電子地図データが、それぞれ関連付けられて格納されている。また、地図情報記憶部４８には、位置情報収集部４２により収集された歩行者位置情報や車両位置情報などの位置情報と、軌跡抽出部４４により生成された移動軌跡情報テーブルと、確率演算部４６により演算された待ち時間あり発生確率値および待ち時間なし発生確率値とが格納されている。この地図情報記憶部４８は、大容量で高速アクセスが可能なハードディスクドライブを採用することができる。
【００３０】
以上のように構成された本発明の実施の形態に係る経路案内システム１０の動作および使用状態について、図面に基づいて説明する。
【００３１】
まず、図５に基づいて、経路案内サーバ３０の動作について、全体の流れを説明した後に、経路探索の方法について詳細に説明する。
携帯電話２０を携行する歩行者は、携帯電話２０の操作部２６を操作してブラウザを起動し、現在位置の周辺地域の地図画像を経路案内サーバ３０へ表示要求する。この操作によりインターネット制御部２３は、ＧＰＳ部２４からの現在位置情報と共に表示要求コマンドを経路案内サーバ３０へ通信部２１を介して送信する（ステップＳ１１０）。
【００３２】
表示要求コマンドを受け付けた経路案内サーバ３０の地図要求受付部３２は、地図送信部３３へ周辺地域の地図画像を、現在地情報に基づいて地図情報記憶部３７から取得する（ステップＳ１２０）。地図送信部３３は、地図情報記憶部３７から取得した周辺地域の地図画像を通信部３１を介して携帯電話２０へ送信する（ステップＳ１３０）。
地図画像を受信した携帯電話２０のインターネット制御部２３は、地図画像をブラウザに表示する（ステップＳ１４０）。
【００３３】
次に、歩行者は、表示部２７に表示された地図画像を見ながら操作部２６を操作して目的地を指定し、現在地である出発地から目的地までの経路探索を経路案内サーバ３０へ依頼する。この操作によりインターネット制御部２３は、経路探索を依頼するコマンドである経路探索要求コマンドと共に、ＧＰＳ部２４からの取得した現在位置情報を出発地情報とし、指定された目的地の位置情報を目的地情報として経路案内サーバ３０へ送信する（ステップＳ１５０）。
【００３４】
経路探索要求コマンドを受け付けた経路案内サーバ３０の地図要求受付部３２は、経路探索部３４へ出発地から目的地までの推奨経路の探索を指示する（ステップＳ１６０）。
経路提供部３５は、経路探索部３４が探索した推奨経路を周辺地域の地図画像に重畳させる（ステップＳ１７０）。そして、推奨経路が重畳された周辺地域の地図画像を地図送信部３３が通信部３１を介して携帯電話２０へ送信する（ステップＳ１８０）。
地図画像を受信した携帯電話２０のインターネット制御部２３は、地図画像をブラウザに表示する（ステップＳ１９０）。
このような手順で、ユーザである歩行者は現在地である出発地から目的地までの経路を探索することができる。
【００３５】
次に、ステップＳ１６０での推奨経路の探索方法について詳細に説明する。本実施の形態では、図６に示す経路図１についての経路探索処理例（１）と、図２２に示す経路図２についての経路探索処理例（２）とに基づいて説明する。なお、経路探索処理例（１）と経路探索処理例（２）とについて、不確定リンクとして、信号機付きの横断歩道を示す横断リンクを例に説明する。また、リンクコストデータ、待ち時間ありコストデータ、待ち時間なしコストデータを、コスト演算の説明においては、単にリンクコスト、待ち時間ありコスト、待ち時間なしコストと称する。
【００３６】
経路探索処理例（１）
図６に示す経路図１は、地図情報記憶部３７に格納された地図データの一部を模式的に表したものである。経路図１には、出発地ＳＴ１から目的地ＧＬ１までの歩行路を表すリンクＬ１〜リンクＬ２３と、このリンクＬ１〜リンクＬ２３の端点であるノードＡ〜ノードＯと、リンクＬ１〜リンクＬ２３のそれぞれに割り付けられたリンクコストとが示されている。リンクＬ１〜リンクＬ６およびリンクＬ２３は、道幅の狭い道路であり、ノードＤ〜ノードＩとノードＪ〜ノードＯのそれぞれに接続されるリンクＬ７〜リンクＬ２２は大通りである。
【００３７】
つまり、リンクＬ７〜リンクＬ１１とリンクＬ１８〜リンクＬ２２は大通りの両側に敷設された歩道を示し、リンクＬ１２〜リンクＬ１７はこの大通りを横断する信号付きの横断歩道である。従って、リンクＬ１２〜リンク１７には、横断歩道であることを示すリンク種別データが割り付けられている。以下、このリンクＬ１２〜リンクＬ１７を横断リンクＬ１２〜横断リンクＬ１７と称する。また、横断リンクＬ１２〜横断リンクＬ１７のリンクコストには、信号待ちが発生しない場合の待ち時間なしコスト「２０」と、信号待ちが発生したことによる時間の損失を考慮した待ち時間ありコスト「４０」との２つのコストが割り付けられている。
【００３８】
このような経路図１において、携帯電話２０から送信された出発地情報および目的地情報に基づいて、まず経路探索部３４が初期経路探索処理（一次経路探索処理）を行う。
【００３９】
図７に示すように、初期経路探索処理は、最初に最適経路探索部３４０に最適経路を探索させる（ステップＳ２１０）。この最適経路の探索は、横断リンクＬ１２〜横断リンクＬ１７の全てのリンクコストを待ち時間なし「２０」とし、出発地ＳＴ１から目的地ＧＬ１まで各経路に含まれるそれぞれのリンクのリンクコストから合計コストを演算することで、合計コストが最小の経路を探索して最適経路とする。この探索は、信号待ちによる時間の損失を考慮しない従来の方法と同じである。
【００４０】
この経路図１の場合では、図８に示す出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＨ→ノードＮ→目的地ＧＬ１の順に歩行する経路（Ａ）が、コスト「８８」であるので最小のコストである。
【００４１】
次に、再探索部３４１の初期経路探索部３４１ａは、最適経路として探索された経路（Ａ）について、リンクを通行するための所要時間が不確定な不確定リンク、つまり横断リンクが含まれるか否かを判定する（ステップＳ２２０）。経路（Ａ）には、ノードＨ，Ｎにて接続された横断リンクＬ１６が含まれているので、横断リンク有りの判定となる。
【００４２】
初期経路探索部３４１ａは、経路（Ａ）に横断リンクが含まれていると判定することにより、横断リンクＬ１６のリンクコストを待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する（ステップＳ２３０）。つまり、横断歩道で待ち時間が発生していない場合から、待ち時間が発生した場合へと変更する。そして、初期経路探索部３４１ａは、再度、最適経路探索部３４０に出発地ＳＴ１から目的地ＧＬ１までの最適経路を探索させる（ステップＳ２４０）。
【００４３】
横断リンクＬ１６のリンクコストを待ち時間なしコスト「２０」として演算した場合には、経路（Ａ）の合計コストが「８８」であったが、待ち時間ありコスト「４０」へ変更することで、経路（Ａ）の合計コストは「１０８」となる。従って、最適経路探索部３４０による結果は、出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＧ→ノードＭ→ノードＮ→目的地ＧＬ１の順に歩行する図９に示す経路（Ｂ）がコスト「９０」であるので、最小のコストとなる。従って、２回目の経路探索では、経路（Ｂ）が最適経路として探索される。
【００４４】
初期経路探索部３４１ａは、経路（Ｂ）について、横断リンクが含まれるか否かを判定する（ステップＳ２５０）。経路（Ｂ）には、ノードＧ，Ｍにて接続された横断リンクＬ１５が含まれているので、横断リンク有りとの判定となる。
【００４５】
次に、初期経路探索部３４１ａは、探索された経路が新たな経路か否かを判定する（ステップＳ２６０）。この場合には、探索された経路（Ｂ）は、経路（Ａ）と異なり新たな経路なので、ステップＳ２３０へ移行する。
このようにして、初期経路探索部３４１ａは、順次、ステップＳ２３０からステップＳ２６０を繰り返して、最適経路探索部３４０に最適経路を探索させることで、図１０に示すように、最初に経路（Ａ）が探索された後、経路（Ｂ）から経路（Ｆ）が順番に探索される。ここで、経路（Ａ）から経路（Ｆ）について図１１に合計コストを示す。図１１では、それぞれの経路に含まれる横断リンクのリンクコストを待ち時間なしコストとした場合と、待ち時間ありコストとした場合との合計コストを示している。
図１１から待ち時間なしコストから待ち時間ありコストへ変更して、合計コストを算出し、最小のコストとなる経路を最適経路とすると、経路（Ａ）から経路（Ｆ）までが順次、探索されることがわかる。
【００４６】
そして、経路（Ｆ）の横断リンクＬ１３について、リンクコストを待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して（ステップＳ２３０）、最適経路を探索すると（ステップＳ２４０）、経路（Ｆ）の合計コストは「１２０」なので、合計コスト「１０８」の経路（Ａ）が最適経路として、再度探索される。つまり、初期経路探索部３４１ａは、横断リンク有りの判定をした後に（ステップＳ２５０）、以前に探索された経路と同じ経路であるとの判定をして（ステップＳ２６０）、初期経路探索処理を終了する。これらの経路（Ａ）〜経路（Ｆ）は、初期経路探索部３４１ａにより、地図情報記憶部３７に初期探索経路情報として格納される。
【００４７】
本実施の形態では、経路（Ａ）〜経路（Ｆ）の全てに横断リンクが含まれているが、最適経路として探索された経路に、横断リンクが含まれていなければ、初期経路探索部３４１ａは、初期経路探索処理を終了するように判定する（ステップＳ２２０，ステップＳ２５０）。それは、横断リンクが含まれていないために、待ち時間なしコストから待ち時間ありコストへと変更できないため、再度、ステップＳ２４０にて最適経路探索を行っても同じ結果となるためである。
【００４８】
このようにして探索された経路（Ａ）〜経路（Ｆ）について、局所経路探索処理（二次経路探索処理）を行う。局所経路探索処理は、各経路を局所的にコスト演算して、より最適な経路を探索する処理である。
【００４９】
図１２に示すように、局所経路探索処理では、まず、局所経路探索部３４１ｂが、経路（Ａ）〜経路（Ｆ）のそれぞれに含まれる横断リンクの出発地ＳＴ１側の端点であるノードを探索する（ステップＳ３１０）。これにより、図１３に示すノードＥ〜ノードＨが探索される。
【００５０】
次に、探索されたノードＥ〜ノードＨの各ノードのうち、一のノードを始点（出発地）として設定する（ステップＳ３２０）。そして、始点として設定されたノード（ノードＥ〜ノードＦ）から目的地ＧＬ１までの最適経路を探索する（ステップＳ３３０）。本実施の形態では、まず、目的地ＧＬ１に近いノードＨから局所経路探索するものとする。
【００５１】
ここで、ステップＳ３３０にて行われる局所経路探索での経路探索について、図１４に基づいて詳細に説明する。
全部の横断リンク（横断リンクＬ１２〜横断リンクＬ１７）のリンクコストを待ち時間なしコスト「２０」とする（ステップＳ４１０）。次に、ノードＨを始点とした経路の合計コストが最小の経路を最適経路として探索する（ステップＳ４２０）。以下、局所経路探索における合計コストを局所コストと称する。
【００５２】
最適経路の探索は、ノードＨを始点として設定しているので、図１５（Ａ）に示すような、ノードＨから横断リンクＬ１６を介してノードＮへ向かう経路（ａ）が探索される。そして、以前に探索された経路と同じ経路か否かを判定する（ステップＳ４３０）。まだ、最初の経路（ａ）を探索したばかりなので、次の経路を探索するために横断リンクのリンクコストを待ち時間なしコストから待ち時間ありコストへ変更する（ステップＳ４４０）。つまり、横断リンクＬ１６のリンクコストを「２０」から「４０」へ変更する。
【００５３】
横断リンクＬ１６のリンクコストを「２０」から「４０」へ変更して最適経路の探索をした結果、経路（ａ）の局所コストが「５０」であるのに対し、最小となる他の経路の局所コストも「５０」であるため、最適経路としてはやはり経路（ａ）が最適経路として探索される（ステップＳ４２０）。従って、１回目と２回目とで同じ最適経路が探索されるので、局所経路探索での最適経路の探索を終了する（ステップＳ４３０）。
【００５４】
図１２に戻って、経路探索が終了すると、全ての出発地（ノードＥ〜ノードＨ）について経路探索したか否かを判定する（ステップＳ３４０）。全ての経路探索が終わっていれば処理を終了する。終わっていなければ、次のノード、例えば、ノードＨについて終了していればノードＧを出発地として設定する（ステップＳ３２０）。
【００５５】
このようにして、ノードＨからノードＥまで順番に行うことで、図１５（Ａ）から同図（Ｄ）までに示すように、ノードＨを始点した局所経路グループには経路（ａ）が探索され、ノードＧを始点とした局所経路グループには経路（ｂ），（ｃ）が探索され、ノードＦを始点とした局所経路グループには経路（ｄ）〜経路（ｆ）が探索され、ノードＥを始点とした局所経路グループには経路（ｇ）〜経路（ｊ）が探索される。これらの局所経路グループに属するそれぞれの経路（ａ）〜経路（ｊ）は、局所経路探索部３４１ｂにより、地図情報記憶部３７に局所探索経路情報として格納される。
【００５６】
経路（ａ）〜経路（ｊ）が探索されたことで、コスト演算部３４１ｃは、次に、経路（ａ）〜経路（ｊ）と、この経路（ａ）〜経路（ｊ）へ至るまでの最適経路との合計コストを演算する。ノードＥ〜ノードＨを経由する経路は、例えば、経路（ａ）であれば、図１０に示す経路（Ａ）の出発地ＳＴ１→ノードＡ→ノードＢ→ノードＣ→ノードＨの経路が最も小さいコストとなるため、合計コストは、横断リンクＬ１６のコストを待ち時間なしコストとした場合で「８８」、待ち時間ありコストとした場合で「１０８」となる。このようにして演算された経路（ａ）〜経路（ｊ）の局所コストと合計コストとを局所経路グループごとに図１６（Ａ）〜同図（Ｄ）に示す。
【００５７】
このように局所経路探索処理を行うことで、初期経路探索処理では探索されなかった経路が探索される。例えば、初期経路探索処理ではノードＦを通過する経路は、図１０に示すように横断リンクＬ１４を通る経路（Ｄ）と、横断リンクＬ１５を通る経路（Ｅ）とが探索されたが、ノードＦを始点とした局所経路探索処理では、図１５（Ｃ）に示すように、更に横断リンクＬ１６を通る経路（ｆ）が探索される。
【００５８】
局所経路探索処理による経路の探索が終了すると、次に、コスト演算部３４１ｃは、横断リンクの待ち時間の発生確率を考慮した合計コストの演算を行う。本実施の形態では、待ち時間あり発生確率値を１／２、待ち時間なし確率値を１／２とする。
【００５９】
まず、最初にノードＨを始点として局所経路探索された経路（ａ）を経由点とした経路について合計コストの演算を行う。経路（ａ）を経由点とした経路の合計コストは、横断リンクとして横断リンクＬ１６が一つのみなので、横断リンクＬ１６が待ち時間が発生する場合としない場合との２通りとなる。すなわち、図１７に示すように、待ち時間が発生する場合の合計コストは「８８」であり、待ち時間が発生しない場合の合計コストは「１０８」である。従って、横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ１は、式（１）によって演算することができる。
合計コストＣ１＝88×1/2＋108×1/2＝９８ …（１）
【００６０】
次に、ノードＧを経由点とする経路（経路（ｂ），（ｃ）を含む経路）について合計コストの演算を行う。経路（ｂ），（ｃ）を含む経路の合計コストは、横断リンクとして２つの横断リンクＬ１５，Ｌ１６が含まれるので、図１８に示すように４通りとなる。従って、それぞれの組み合わせ事象が発生する確率は１／２×１／２となり１／４となる。
【００６１】
例えば、横断リンクＬ１５，Ｌ１６の両方で待ち時間が発生しない場合には、まずノードＧを端点とする横断可能な横断リンクL１５（待ち時間の発生しない横断リンクＬ１５）を渡る経路（ｃ）が選択されるので、合計コストが「９０」となる。
次に、横断リンクＬ１５で待ち時間が発生せず、横断リンクＬ１６で待ち時間が発生する場合には、ノードＧにいる歩行者は、横断リンクＬ１６より手前にある横断リンクＬ１５を横断リンクＬ１６より先に渡った方が、目的地に到達するまでに所要時間が不確定な要因を排除できる。結果、横断リンクＬ１５で待ち時間が発生せず、横断リンクＬ１６で待ち時間が発生する場合には、経路（ｃ）が選択されるので、合計コストは「９０」となる。
【００６２】
次に、横断リンクＬ１５で待ち時間が発生し、横断リンクＬ１６で待ち時間が発生しない場合には、ノードＧにて横断リンクＬ１５が横断可能な状態となるまで待つよりも、ノードＨに向かう方が効率がよい。結果、経路（ｂ）が選択されるので、合計コストは「９０」となる。
【００６３】
横断リンクＬ１５，Ｌ１６の両方で待ち時間が発生する場合には、横断リンクＬ１５の端点であるノードＧで待たずに歩行者は先へ進み、ノードＨに到達するまでに横断可能となることが期待できるので、横断リンクＬ１６を通過する経路（ｂ）を選択した方がよい。従って、経路（ｂ）が選択されるので、合計コストは「１１０」となる。
このようにして経路が選択されるので、横断リンクＬ１５，Ｌ１６の待ち時間の発生確率を考慮した合計コストＣ２は、式（２）によって演算することができる。
合計コストＣ２＝90×1/4＋90×1/4＋90×1/4＋110×1/4＝９５ …（２）
【００６４】
次に、ノードＦを経由点とする経路（経路（ｄ）〜経路（ｆ）を含む経路）について合計コストの演算を行う。経路（ｄ）〜経路（ｆ）を含む経路の合計コストは、横断リンクとして３つの横断リンクＬ１４〜横断リンクＬ１６が含まれるので、図１９に示すように４通りとなる。従って、それぞれの組み合わせ事象が発生する確率は１／２×１／２×１／２となり１／８となるので、横断リンクＬ１４〜横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ３は、式（３）によって演算することができる。
合計コストＣ３＝90×1/8＋90×1/8＋90×1/8＋90×1/8＋95×1/8＋95×1/8＋95×1/8＋115×1/8＝９５ …（３）
【００６５】
次に、ノードＥを経由点とする経路（経路（ｇ）〜経路（ｊ）を含む経路）について合計コストの演算を行う。経路（ｇ）〜経路（ｊ）を含む経路の合計コストは、横断リンクとして４つの横断リンクＬ１３〜横断リンクＬ１６が含まれるので、図２０に示すように１６通りとなる。従って、それぞれの事象が発生する確率は１／２×１／２×１／２×１／２となり１／１６となるので、横断リンクＬ１３〜横断リンクＬ１６の待ち時間の発生確率を考慮した合計コストＣ４は、式（４）によって演算することができる。
合計コストＣ４＝100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋100×1/16＋90×1/16＋90×1/16＋90×1/16＋90×1/16＋95×1/16＋95×1/16＋95×1/16＋115×1/16＝９７．５ …（４）
このようにして、コスト演算部３４１ｃは、各経路での合計コストＣ１〜Ｃ４を演算する。
【００６６】
初期経路探索処理では、図１１に示すように、経路（Ａ）が最小コストであった。この経路（Ａ）について、横断リンクの待ち時間の発生確率を考慮した合計コストを演算すると、合計コストＣ５は、横断リンクとして横断リンクＬ１６のみ含んでいるので、式（５）によって演算することができる。
合計コストＣ５＝88×1/2＋108×1/2＝９８ …（５）
【００６７】
つまり、初期経路探索処理によって探索された経路（Ａ）では合計コストが９８となるが、局所経路探索処理により経路を探索し、合計コストを演算すると、ノードＦを始点した局所経路グループが合計コストが９５となって、ノードＥを始点した局所経路グループの合計コストと同じ値で、最も小さい値であるが、この場合、ノードＦとノードＥとで出発地ＳＴ１に近い方が選択される。
つまり、出発地ＳＴ１からノードＡおよびノードＥを経由してノードＦへ至り、ノードＦを通過した後に、横断リンクＬ１４〜横断リンクＬ１６の状態に応じて経路（ｄ）〜経路（ｆ）のいずれかの経路を歩行する方が最適な経路を選択できることを示している。これは、歩行者がノードＦまで到達した時点で、横断リンクが赤信号であれば青信号の横断リンクを選択しながら歩行することができるからである。
更に、ノードＦから経路（ｄ）〜経路（ｆ）のうち、横断リンクＬ１４が青信号であれば、経路（ｄ）を選択することが最もよいことを示している。
【００６８】
経路提供部３５は、このように経路が探索されると、推奨経路を周辺地域の地図画像に重畳させる。例えば、図２１に示すように出発地ＳＴ１からノードＦまでに至るまでの一つの経路と、ノードＦから目的地ＧＬ１へ至る複数の経路（経路（ｄ）〜経路（ｆ））とにより歩行者に案内する。このとき、最も良い経路である経路（ｄ）について目立つようにして案内するようにしてもよい。更に、情報報知部３６により、まずノードＦまで歩行し、更に横断リンクＬ１４〜横断リンクＬ１６を順に青であれば渡ってよい旨のメッセージまたは音声を、地図画像と共に携帯電話２０へ送信することで更に利便性を向上させることができる。また、最も良い経路である経路（ｄ）についても文字や音声で案内するようにしてもよい。
【００６９】
経路探索処理例（２）
図２２に示す経路図２は、出発地ＳＴ２から目的地ＧＬ２までのいずれの経路中にも複数の横断リンクが含まれている例を示すものである。
経路図２には、出発地ＳＴ２から目的地ＧＬ２までの歩行路を表すリンクＬ２４〜リンクＬ３５と、このリンクＬ２４〜リンクＬ３５の端点であるノードＰ〜ノードＷと、リンクＬ２４〜リンクＬ３５のそれぞれに割り付けられたリンクコストとが示されている。
【００７０】
リンクＬ２５とリンクＬ２６とは大通りの両側に敷設された歩道を示し、リンクＬ３１とリンクＬ３２とはこの大通りを横断する信号付きの横断歩道である。また、リンクＬ２９とリンクＬ３０も同様に大通りの両側に敷設された歩道を示し、リンクＬ３３とリンクＬ３４はこの大通りを横断する信号付きの横断歩道である。従って、経路図１と同様に、リンクＬ３１〜リンク３４には、横断歩道であることを示すリンク種別データが割り付けられている。以下、このリンクＬ３１〜リンク３４を横断リンクと称する。また、横断リンクＬ３１〜横断リンクＬ３４のリンクコストには、信号待ちが発生しない場合の待ち時間なしコスト「２０」と、信号待ちが発生したことによる時間の損失を考慮した待ち時間ありコスト「４０」との２つのコストが割り付けられている。
【００７１】
このような経路図２において、携帯電話２０から送信された出発地情報および目的地情報に基づいて、経路図１を用いて説明したように、まず経路探索部３４が初期経路探索処理（一次経路探索処理）を行う。
【００７２】
図２３に示すように、初期経路探索処理は、最初に最適経路探索部３４０が最適経路を探索する（ステップＳ５１０）。この最適経路の探索は、横断リンクＬ３１〜横断リンク３４の全てのリンクコストを待ち時間なし「２０」とし、出発地ＳＴ２から目的地ＧＬ２まで各経路に含まれるそれぞれのリンクのリンクコストから合計コストを演算することで、合計コストが最小の経路を探索して最適経路とする。この探索は、信号待ちによる時間の損失を考慮しない従来の方法と同じである。
【００７３】
この経路図２の場合では、図２４に示す出発地ＳＴ２→ノードＰ→ノードＱ→ノードＳ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路（Ｇ）が、コスト「９０」で最小のコストである。しかし、最小コストいう点では、例えば、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＳ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路でもコスト「９０」であり、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＴ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する経路でもコスト「９０」である。この場合、最適経路探索部３４０は、いずれの経路を選択して最適経路としてもよいが、本実施の形態では、最初に探索された経路（Ｇ）を最適経路として設定したものとする。このようにして、経路としては一つであるが、まず経路（Ｇ）が最適経路グループ（ア）として、図２５に示すように探索される。
【００７４】
次に、再探索部３４１の初期経路探索部３４１ａは、最適経路として探索された経路（Ｇ）について、リンクを通行するための所要時間が不確定な不確定リンク、つまり横断リンクが含まれるか否かを判定する（ステップＳ５２０）。経路（Ｇ）には、ノードＱ，Ｓにて接続された横断リンクＬ３２と、ノードＵ，Ｗにて接続された横断リンクＬ３４とが含まれているので、横断リンク有りの判定となる。
【００７５】
初期経路探索部３４１ａは、経路（Ｇ）に横断リンクが含まれていると判定することにより、次の最適経路グループを探索する。
経路（Ｇ）には、横断リンクＬ３２，Ｌ３４が含まれているので、この横断リンクＬ３２，Ｌ３４について、いずれか一方、または両方のリンクコストを、順次、待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して、それぞれ変更したときの最適経路の探索を行う。
この場合、まず横断リンクＬ３２のリンクコストを変更する（ステップＳ５３０）。そして、初期経路探索部３４１ａは、再度、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。
【００７６】
横断リンクＬ３２のリンクコストを待ち時間なしコスト「２０」として演算した場合には、経路（Ｇ）の合計コストが「９０」であったが、待ち時間ありコスト「４０」へ変更することで、経路（Ｇ）の合計コストは「１１０」となる。従って、最適経路探索部３４０による結果は、出発地ＳＴ２→ノードＰ→ノードＲ→ノードＴ→ノードＵ→ノードＷ→目的地ＧＬ２の順に歩行する図２４に示す経路（Ｈ）がコスト「９０」であるので、経路（Ｇ）より小さいコストとなる。従って、図２５に示すように２回目の経路探索では、経路（Ｈ）が、最適経路グループ（イ−１）として探索される。
【００７７】
初期経路探索部３４１ａは、経路（Ｈ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｈ）には、横断リンクＬ３１，Ｌ３４が含まれているので、横断リンク有りとの判定となる。
【００７８】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。この時点では、まだ横断リンクＬ３２のみ変更しただけなので、残りの経路を探索するためにステップＳ５３０へ移行する。
【００７９】
次に、横断リンクＬ３４を待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する。このとき、横断リンクＬ３２のコストは待ち時間なしコスト「２０」とする（ステップＳ５３０）。そして、初期経路探索部３４１ａは、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。そうすることで、最適経路として合計リンクコストが「９０」の経路（Ｉ）（図２５に示す最適経路グループ（イ−２）参照）が探索される。
【００８０】
初期経路探索部３４１ａは、経路（Ｉ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｉ）には、横断リンクＬ３１，Ｌ３３が含まれているので、横断リンク有りとの判定となる。
【００８１】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。この場合、横断リンクＬ３２，Ｌ３４の両方のリンクコストを待ち時間ありコストとするケースが残っているため、ステップＳ５３０へ移行する。
次に、横断リンクＬ３２を待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更する。つまり、横断リンクＬ３２，Ｌ３４のコストを待ち時間ありコスト「４０」とする（ステップＳ５３０）。そして、初期経路探索部３４１ａは、最適経路探索部３４０に出発地ＳＴ２から目的地ＧＬ２までの最適経路を探索させる（ステップＳ５４０）。そうすることで、最適経路として合計リンクコストが「９０」の経路（Ｉ）（図２５に示す最適経路グループ（イ−３）参照）が探索される。
【００８２】
初期経路探索部３４１ａは、経路（Ｉ）について、横断リンクが含まれるか否かを判定する（ステップＳ５５０）。経路（Ｉ）には、横断リンクＬ３１，Ｌ３３が含まれているので、横断リンク有りとの判定となる。
【００８３】
次に、初期経路探索部３４１ａは、最適経路グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、リンクコストを変更したか否かを判定する（ステップＳ５６０）。横断リンクＬ３２，Ｌ３４のリンクコストを変更して、全てのケースについて最適経路を探索したので、最適経路グループ（イ）については終了する。
次に、最適経路グループに以前に探索されていない新たな経路が含まれているか否かを判定する（ステップＳ５７０）。
最適経路グループ（イ）には、最適経路グループ（ア）には含まれていない経路（Ｈ）や経路（Ｉ）が探索されたため、ステップＳ５３０へ移行する。
【００８４】
経路（Ｈ）および経路（Ｉ）について、経路（Ｈ）には横断リンクＬ３１，Ｌ３４が含まれ、経路（Ｉ）には横断リンクＬ３１，Ｌ３３が含まれている。従って、ステップＳ５３０からステップＳ５６０を繰り返して、これらの横断リンクについて、いずれか一方、または両方のリンクコストを、順次、待ち時間なしコスト「２０」から待ち時間ありコスト「４０」へ変更して、それぞれ変更したときの最適経路の探索を行う。その際、経路探索グループ（ア）の経路（Ｇ）に含まれる横断リンクＬ３２，Ｌ３４について、経路探索グループ（イ）を探索したときと同様に、全てのケースについて行う。
【００８５】
初期経路探索部３４１ａは、横断リンクのリンクコストを変更し最適経路を探索することで、図２５に示す最適経路グループ（ウ）として（ウ−１）〜（ウ−９）を抽出する。なお、図２５の最適経路グループ（ウ）については、他の経路と重複するケースは省略している。初期経路探索部３４１ａは、最適経路を最適経路探索部３４０に探索させる際に、横断リンクＬ３１〜横断リンクＬ３４の状態の組み合わせが以前にあったか否かを予め判断してから最適経路の探索をさせるようにしてもよいし、最適経路探索部３４０に探索させてから重複した組み合わせについて削除するようにしてもよい。これら図２５に示す抽出された経路は、初期経路探索部３４１ａにより、地図情報記憶部３７に初期探索経路情報として格納される。
【００８６】
このようにして探索された経路（Ｇ）〜経路（Ｉ）について、局所経路探索処理（二次経路探索処理）を行う。
局所経路探索処理は、局所経路探索部３４１ｂが、まず横断リンクの出発地側のノードを始点として横断リンクのリンクコストを変更しながら順次、最適経路を探索し、次にこのノードを経由点とした経路の合計リンクを算出する。この方法については、経路図１における経路探索処理例（１）と同じである。
【００８７】
経路図２における局所経路探索処理を行った結果を、図２６から図２９に示す。図２６は、局所経路探索部３４１ｂによりノードＰを始点（経由点）とした局所経路探索処理を行い、コスト演算部３４１ｃにより算出したその経路の合計コストを示したものである。
【００８８】
ノードＰを始点とした場合、まず、横断リンクＬ３１が待ち時間ありの場合には、リンクＬ２５を経由してノードＱまで到達し、横断リンクＬ３２を渡る経路を選択する。これは、ノードＰにて横断リンクＬ３１が横断可能な状態となるまで待つよりも、ノードＱに向かう方が効率がよいためである。従って、横断リンクＬ３２が待ち時間ありの場合には、全て経路（Ｇ）が選択され、経路（Ｇ）に含まれる横断リンクＬ３２および横断リンクＬ３４の状態に応じて合計コストが算出される。
【００８９】
横断リンクＬ３１が待ち時間なしの場合には、まず横断リンクＬ３１を渡る経路が選択される。これは、横断可能な横断リンクＬ３１を先に渡った方が、早く目的地ＧＬ２の近い位置へ行けるためである。従って、横断リンクＬ３１を渡り、リンクＬ２７を通過してノードＴへ到達する。そして、ノードＴから横断リンクＬ３３が待ち時間なしの状態であれば、横断リンクＬ３３を渡る経路（Ｉ）が選択され、横断リンクＬ３３が待ち時間ありであれば経路（Ｈ）が選択される。このようにして経路（Ｉ）または経路（Ｈ）が選択されると、経路（Ｉ）または経路（Ｈ）に含まれる横断リンクＬ３１，Ｌ３３，Ｌ３４の状態に応じて合計コストが算出される。
【００９０】
次に、コスト演算部３４１ｃは、横断リンクの待ち時間の発生確率を考慮した合計コストの演算を行う。本実施の形態では、待ち時間あり発生確率値を１／２、待ち時間なし確率値を１／２とする。
【００９１】
ノードＰを始点（経由点）とした経路は、横断リンクＬ３１〜横断リンクＬ３４がそれぞれ待ち時間の発生ありと待ち時間発生なしとの組み合わせとなるため、それぞれの組み合わせ事象が発生する確率は１／１６となる。従って、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ６は、式（６）によって演算することができる。
合計コストＣ６＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＝１０２．５ …（６）
【００９２】
ノードＱを始点（経由点）とした局所経路探索処理は、図２７に示すように、横断リンクＬ３２が待ち時間あり、または待ち時間なしに関わらず、全て経路（Ｇ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ７は、式（７）によって演算することができる。
合計コストＣ７＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＝１１０ …（７）
【００９３】
ノードＴを始点（経由点）とした局所経路探索処理は、図２８に示すように、横断リンクＬ３３が待ち時間ありとなった場合には、横断リンクＬ３４へ向かう経路（Ｈ）、横断リンクＬ３３が待ち時間なしとなった場合には、そのまま横断リンクＬ３３を渡る経路（Ｉ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ８は、式（８）によって演算することができる。
合計コストＣ８＝130×1/16＋110×1/16＋110×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋110×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＋110×1/16＋90×1/16＋90×1/16＋90×1/16＝１０５ …（８）
【００９４】
ノードＵを始点（経由点）とした局所経路探索処理は、図２９に示すように、横断リンクＬ３１が待ち時間ありとなった場合には、横断リンクＬ３２へ向かう経路（Ｇ）、横断リンクＬ３１が待ち時間なしとなった場合には、そのまま横断リンクＬ３１を渡り、ノードＵへ向かう経路（Ｈ）を選択することになるため、横断リンクＬ３１〜横断リンクＬ３４の待ち時間の発生確率を考慮した合計コストＣ９は、式（９）によって演算することができる。
合計コストＣ９＝130×1/16＋110×1/16＋130×1/16＋110×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＋110×1/16＋90×1/16＝１０５ …（９）
【００９５】
局所経路探索処理により式（６）から式（９）から得られた待ち時間の発生確率を考慮した合計コストでは、ノードＰを始点（経由点）とした場合が最も小さい値である。従って、出発地ＳＴ２からノードＰへ至り、横断リンクＬ３１の状態に応じて横断リンクＬ３１を渡るか、またはノードＱへ向かうか選択して歩行する方が最適な経路であることを示している。
【００９６】
経路提供部３５は、このように経路が探索されると、推奨経路を周辺地域の地図画像に重畳させる。例えば、図３０に示すように出発地ＳＴ２からノードＰまでに至るまでの一つの経路と、ノードＰにて２つに分岐する経路と、更にノードＴにて２つに分岐する経路とを重畳させた地図画像（図２４に示す経路（Ｇ）〜経路（Ｉ）参照）を、通信部３１を介して携帯電話２０へ送信する。経路（Ｇ）〜経路（Ｉ）は、横断リンクのリンクコストが同じ条件であれば、経路の合計コストは同じである。この場合、経路提供部３５は、特に経路（Ｇ）〜経路（Ｉ）のいずれの経路も強調せずに地図画像に重畳させて提供する。
【００９７】
また、情報報知部３６が音声またはメッセージにより、まずノードＰまで歩行し、更に横断リンクＬ３１の状態に応じて青であれば渡ってよいことを、歩行者に報知することで、更に利便性を向上させることができる。
【００９８】
このように、初期経路探索処理により最初に探索された経路に、横断リンクが含まれているときに、探索条件として、横断リンクのリンクコストを、待ち時間なしコストから待ち時間なしコストへ変更して他の経路を探索して歩行者へ提供することで、歩行者のために好適な経路を探索することが可能である。
また、再探索部３４１の局所経路探索部３４１ｂは、局所経路探索処理において横断リンクの出発地側のノードを、最適経路を探索する始点として最適経路を探索することで、出発地を始点した場合と始点が異なるので、初期経路探索処理では探索できなかった新たな経路を探索することができる。
【００９９】
更に、地図情報記憶部３７に、リンク種別がリンクを通行するための所要時間が不確定な横断リンクのリンクコストとして、待ち時間ありコストと、待ち時間なしコストとを備えた地図データが格納されているので、経路中に横断リンクを示すリンク種別が含まれているときに、待ち時間ありコストまたは待ち時間なしコストに基づいて合計コストを演算することができるので、より実際に即した最適経路の探索を行うことができる。
【０１００】
なお、本実施の形態では、初期経路探索処理により最初に探索された経路に、横断リンクが含まれているときに、変更する探索条件として横断リンクのリンクコストを変更したが、横断リンクを回避することを条件として再探索することも可能である。
また、本実施の形態では、不確定リンクとして横断歩道を示す横断リンクを例に説明したが、通行する際にリンクコストが不確定なリンクであれば、他のリンクでも本発明を適用することが可能である。例えば、列車が通過する時間が一定ではない踏切や、信号機無しの横断歩道、横断歩道はないが横断可能な場所なども不確定リンクとする待ち時間ありコストと待ち時間なしコストして整備することができる。
【０１０１】
次に、電子地図データ生成サーバ４０の動作について、図３１から図４３に基づいて説明する。
図３１に示すように、まず、電子地図データ生成サーバ４０の位置情報収集部４２は、携帯電話２０から送信される歩行者位置情報を地図情報記憶部４８に蓄積する（ステップＳ６１０）。
【０１０２】
次に、蓄積された歩行者位置情報の歩行者識別情報から特定された携帯電話２０が同じ現在位置情報を抽出して、順次受信した現在位置情報により得られた移動軌跡に対して、補間処理を行う（ステップＳ６２０）。この補間処理は、図３２（Ａ）に示すように、３秒間隔に送信される現在位置情報では、現在位置情報が示すそれぞれの構成点Ｐ１が疎となる場合には、図３２（Ｂ）に示すように、軌跡補間部４３が移動軌跡の構成点を密にするために、１秒間隔と想定される位置に補間構成点Ｐ２を生成する。そして軌跡補間部４３は、補間構成点Ｐ２により補間された移動軌跡を地図情報記憶部４８に格納する。この補間方法としては、線形補間法が使用できる。
【０１０３】
次に、横断リンク選定処理により横断待ち確率を整備する横断リンクを選定する（ステップＳ６２１）、更に軌跡抽出部４４により軌跡抽出処理が行われる（ステップＳ６３０）。軌跡抽出処理は、まず、収集された歩行者の移動軌跡のうち横断リンク付近を通過する移動軌跡を抽出する。例えば、横断リンクを中心とした１ｋｍ四方の領域を通過する移動軌跡を抽出する。
【０１０４】
次に、抽出された移動軌跡の中から横断リンクに沿って通過した移動軌跡を抽出する。例えば、図３３（Ａ）に示すように道路Ｒ１にノードａとノードｂとを端点に有する横断リンクＬＫ１が設けられていたとすると、軌跡抽出部４４はまず横断リンクＬＫ１の中間位置を中点ｃに設定する。次に、図３３（Ｂ）に示すように軌跡抽出部４４は、中点ｃを中心した所定半径（例えば、半径２ｍ。）の円内を通過した移動軌跡を選択することで、横断リンクＬＫ１を通過した移動軌跡を抽出することができる。
【０１０５】
しかし、図３３（Ｃ）に示すようにノードａを通過し、中点ｃを中心とした円内を通過した移動軌跡Ｔ２も抽出されてしまう。この場合には、中点ｃを中心とした円内を通過することを条件とするだけでなく、ノードａおよびノードｂのいずれか一方または両方を中心とした円内を通過することを条件とすることで移動軌跡の抽出精度を向上させる。
【０１０６】
このようにして軌跡抽出部４４により抽出された移動軌跡は、移動軌跡情報テーブルとして地図情報記憶部４８に格納される。ここで、移動軌跡情報テーブルについて図３４に基づいて詳細に説明する。
【０１０７】
図３４に示すように、移動軌跡情報テーブルは、軌跡ＩＤと、日付と、到着時刻と、進入時刻と、優先度ポイントとが関連付けられたテーブルである。
軌跡ＩＤは、それぞれの移動軌跡を識別するために付与された識別情報である。日付は収集された日にちを示すもので、現在時間情報に含まれる日付情報である。到着時刻は、歩行者が横断リンクの進入側のノードに到着した時刻を示す情報で、進入側のノードを中心とした円内にいた時刻のうち最も早い時刻である。この到着時刻は、現在時間情報に含まれる時間情報である。進入時刻は、横断リンクに進入した時刻を示す情報で、進入側のノードを中心とした円内にいた時刻のうち最も遅い時刻である。優先度ポイントは、ノイズを除去するために計数されるポイント情報である。初期値は０である。
【０１０８】
この移動軌跡情報テーブルに基づいて、ノイズ除去部４５はノイズ除去処理を行う（ステップＳ６４０）。
このノイズ除去処理は、まず、横断リンクを同時に通行しようとする歩行者を検出して優先度ポイントを増加させる加算処理を行うことで、横断リンクに到着したが、すぐに横断リンクを通行しない移動軌跡に対する優先度ポイントを相対的に下げる処理を行う。これは、歩行者が横断リンクに到着したが、携帯電話２０による通話のために一旦停止した場合や、横断リンク付近に位置する自動販売機を利用するために停止した場合などを排除するためである。
【０１０９】
図３５に示すように、ノイズ除去部４５は、まず軌跡の選択を行う（ステップＳ７１０）。例えば軌跡ＩＤが「００１０１」である移動軌跡（図３４参照）を対象移動軌跡として着目する。次に、軌跡ＩＤが「００１０１」の移動軌跡が横断リンクの進入前に停止したか否かを判定する（ステップＳ７２０）。この判定は、進入時刻と到着時刻との差分が所定値より大きい場合に停止していたとすることができる。
【０１１０】
例えば、「００１０１」の移動軌跡は、到着時刻が１５：３０：００で、進入時刻が１５：３０：４０であるので、４０秒間ほど横断リンクの進入側のノードを中心とした円内にいたことになる。従って、「００１０１」の移動軌跡は、４０秒停止していたことになる。例えば、停止を５秒以上であるとしたときには、「００１０１」の移動軌跡は４０秒間停止していたことになるので、横断リンクの進入側のノードで停止していたと判定することができる。
【０１１１】
次に、進入時刻が同じ他の移動軌跡があるか否かを判定する（ステップＳ７３０）。進入時刻が同じ移動軌跡が他にある場合には、その移動軌跡の優先度ポイントも増加させる加算処理を行う。これは、複数の歩行者が同時に横断リンクに進入したということは、横断リンクが待ちの状態から待ちなしの状態へ遷移して一斉に移動し始めたことを示す確度が高いためである。
【０１１２】
図３４に示す移動軌跡情報テーブルでは、「００１０１」の移動軌跡は、軌跡ＩＤが「００１０２」，「００１０４」，「００１０５」の移動軌跡と進入時刻が同時刻なので、図３６（Ａ）に示すように、進入前の停止が「あり」で、同時進入する軌跡が「あり」なので、「００１０１」の移動軌跡の優先度＋５０ポイント加算される。他の軌跡「００１０２」，「００１０４」，「００１０５」についても同様な処理が行なわれ、これらの移動軌跡の優先度も＋５０ポイント加算される（ステップＳ７４０）。
また、「００１０６」の移動軌跡は、「００１０７」の移動軌跡と進入時刻が同時刻なので、「００１０６」の移動軌跡が選択された処理のときに、＋５０ポイント加算される。
【０１１３】
次に、対象軌跡として全ての移動軌跡を処理したか否かが判定される（ステップＳ７５０）。全ての移動軌跡について処理していれば終了する。処理していなければステップＳ７１０へ移行する。
【０１１４】
例えば、軌跡ＩＤが「００１０５」の移動軌跡であれば、到着時刻と進入時刻とが同時刻であるので、横断リンクの進入側のノードでは一旦停止していないため優先度ポイントが＋５０加算される（ステップＳ７６０）。
【０１１５】
また、軌跡ＩＤが「００１０３」の移動軌跡は、進入時刻と到着時刻との差分が１５秒なので、一旦停止したものと判定されるが、進入時刻が他の移動軌跡と異なるので、進入側のノードでの停止は、赤信号による待ちではなく、他の目的によるものと推定できるため、優先度ポイントを増加する加算処理は行わず、ステップＳ７５０へ移行する。このため赤信号待ち以外の理由で待っている場合には、他の場合と比べて相対的に優先度ポイントが加算されないままとなる。このようにして、図３６（Ｂ）の移動軌跡情報テーブルに示すように優先度ポイントが加算される。
【０１１６】
次に、ノイズ除去部４５は、ノイズ除去処理として車両の移動軌跡を利用して優先度ポイントを増加させる加算処理を行う。この加算処理は、図３７に示すように、車両Ｃが横断歩道を通過する際に、信号機ＳＧ１が赤信号であれば、逆に歩行者側の信号機ＳＧ２が青信号の状態であることを利用するものである。
まず、図３８に示すように、予め位置情報収集部４２が、車両に搭載されたナビゲーション装置やプローブ車両からの車両位置情報を、通信部４１を介して収集し、地図情報記憶部４８へ格納する（ステップＳ８１０）。次に、必要に応じて軌跡補間部４３が、蓄積された車両位置情報のうち、車両識別情報から特定された車両が同じ現在位置情報を抽出して、車両位置情報に含まれる現在位置情報により得られる軌跡に対して補間処理を行う（ステップＳ８２０）。
【０１１７】
次に、軌跡抽出部４４が軌跡抽出処理を行う（ステップＳ８３０）。軌跡抽出処理は、まず歩行者の場合と同様に、収集された車両の移動軌跡のうち横断リンク付近を通過する移動軌跡を抽出する。例えば、横断リンクを中心とする１ｋｍ四方の領域を通過する移動軌跡を抽出する。次に、抽出された移動軌跡の中から横断リンクを横切る移動軌跡を抽出する（図３７（Ｂ）参照）。
【０１１８】
軌跡抽出部４４は、抽出した横断リンクを横切る車両の移動軌跡のうち、横断リンクの手前で停止した移動軌跡の抽出を行う（ステップＳ８４０）。ここで停止とは、時間経過による車両位置の変化が小さいことをいう。軌跡抽出部４４は、抽出された移動軌跡に基づき、対象となる横断リンクに対して車両ごとに停止時間帯を記録したテーブル（図３９（Ａ）参照）を作成し、このテーブルに基づいて対象の横断リンクの車両停止時間テーブル（図３９（Ｂ）参照）を作成する（ステップＳ８５０）。
図３９（Ａ）に示す例では、車両Ａが、車両Ａ〜車両Ｃの中で最も早く横断リンクに到着し、そして最も早く移動を開始して横断リンクを横切っていることから、車両の停止時間、つまり横断リンクで歩行者が通行可能である状態が１５：３０：３５〜１５：３１：００であることがわかる（停止時間Ａ）。
ここまでの処理（ステップＳ８１０からステップＳ８５０）は、図３１に示す位置情報収集部４２による位置情報の収集処理（ステップＳ６１０）から軌跡抽出部４４による軌跡抽出処理（ステップＳ６３０）と並行して行われる。
【０１１９】
ノイズ除去部４５は、車両停止時間テーブルに基づいて移動軌跡情報テーブルの優先度ポイントを増加させる加算処理を行う（ステップＳ８６０）。この加算処理は、図４０に示す移動軌跡情報テーブルの進入時刻が、図３９（Ｂ）に示す車両停止時間テーブルの停止時間に含まれていれば、車両が停止した後に、歩行者が横断リンク内に進入したことを示しているので、優先度ポイントを＋２０ポイント加算する。
このようにして、車両の移動軌跡を利用した優先度ポイントを増加させる加算処理を行う。
【０１２０】
次に、ノイズ除去部４５は、ノイズ除去処理として横断リンクへ進入する前に通過したリンク（以下、進入前リンクと称す。）と、横断リンクから退出した後に通過したリンク（以下、退出後リンクと称す。）とに応じて、優先度ポイントを増加させる加算処理を行う。
【０１２１】
この加算処理は、図４１（Ａ）に示すように対象となる横断リンクＬＫ１に、曲がりながら進入したり退出したりした移動軌跡Ｔ４よりも、直線的に通過した移動軌跡Ｔ５の優先度を上げるために行う処理である。これは、移動軌跡Ｔ４が示すように、歩行者が、まず横断リンクＬＫ２を横断しようとしたが赤信号であったため道路Ｒ２に沿って歩き、横断リンクＬＫ１へ通行可能な状態となるまでタイミングを図りながら向かった可能性があるためである。また、歩行者が、横断リンクＬＫ１を横断した後に道路Ｒ２に沿って歩行する場合には、次の横断リンクを探しながら渡ろうとする可能性があるためである。
【０１２２】
従って、図４１（Ｂ）に示すように、移動軌跡が通過する、横断リンクＬＫ２と、横断リンクＬＫ１へ進入する進入前リンクＬＫ３とのなす角αが、１８０°に近い所定角度以上であれば、その移動軌跡の優先度ポイントに＋１５ポイント加算する。また、図４１（Ｃ）に示すように、移動軌跡が通過した、横断リンクＬＫ１と、横断リンクＬＫ１から退出する退出後リンクＬＫ４とのなす角βが、１８０°に近い所定角度以上であれば、その移動軌跡の優先度ポイントに＋１５ポイント加算する。
【０１２３】
例えば、それぞれの移動軌跡が図４１（Ｄ）に示すような軌跡である場合には、軌跡ＩＤが「００１０２」，「００１０４」，「００１０５」は、横断リンクＬＫ１に対して進入時のなす角と退出時のなす角が両方とも１８０°であるので、優先度ポイントとして進入時と退出時とで合計＋３０ポイントが加算される。また軌跡ＩＤが「００１０１」，「００１０７」は進入時と退出時とでほぼ直角なので加算されない。軌跡ＩＤが「００１０３」は進入時が、「００１０６」は退出時が横断リンクＬＫ１に対してなす角が１８０°であるので、＋１５ポイントのみ加算される。このようにノイズ除去部４５によって優先度ポイントを増加させる加算処理が行われた結果を、図４２に示す。
【０１２４】
図４１（Ａ）に示す横断リンクＬＫ１，ＬＫ２は、一本の道路Ｒ２に沿って敷設された一方の歩道から他方の歩道に並行して設けられている。ここで、図４３に示すような道幅の広い道路Ｒ２１，Ｒ２２同士が交差する交差点では、横断リンクＬＫ３〜ＬＫ６を連結するリンク（以下、このリンクを交差点内リンクＬＫＣと称す。）が存在する。このような場合には、移動軌跡が通過する横断リンクＬＫ３〜ＬＫ６と交差点リンクＬＫＣとのなす角だけでは判断できない。従って、移動軌跡が次に通過するリンクまでを考慮する。つまり、横断リンクＬＫ３〜ＬＫ６のいずれかを渡った後に交差点内リンクＬＫＣを通過し、更に次のどのリンクを移動軌跡が通過したかによって、優先度ポイントの加算を行う。例えば、交差点内リンクＬＫＣを通過した後に、横断リンクＬＫ３〜ＬＫ６を通過したのであれば、加算せず、通常のリンクへ向かったのであれば＋１５ポイント加算するなどである。
【０１２５】
次に、ノイズ除去部４５は、加算された移動軌跡情報テーブルの優先度ポイントに基づいてノイズの除去を行う。例えば、優先度ポイントが高い移動軌跡のみを採用し、他の移動軌跡は削除することでノイズ除去を行うことができる。優先度ポイントが高い移動軌跡とは、優先度ポイント上位７０％以内に含まれる移動軌跡とすることができる。
また、優先度ポイントが高い移動軌跡に対して重み付けを行ってもよい。重み付けは、優先度ポイント上位４０％の移動軌跡の重みを２倍とするなどで、確率演算処理を行う際に優先度ポイント上位４０％の移動軌跡を２重にカウントすることができる。優先度ポイントが高い移動軌跡に対して重み付けを行う場合には、ノイズ除去部４５は重み付けを行う旨のフラグを立てることで、確率演算部４６に指示する。
この上位７０％や、上位４０％などの範囲は適宜決定することが可能である。
【０１２６】
ノイズ除去部４５によるノイズ除去処理が終了すると、確率演算部４６による確率演算処理を行う（ステップＳ６５０）。
確率演算部４６による確率演算処理は、まず、横断リンクに到着してから横断リンクへ進入するまでの横断待ち時間として、移動軌跡情報テーブルの各移動軌跡の進入時刻から到着時刻を引いた差分値を演算する。次に、確率演算部４６は、横断待ち時間を所定値ごとに区分した範囲に含まれる移動軌跡のカウントを行う。本実施の形態では、横断待ち時間が０〜１０秒、１０〜２０秒と、１０秒ごとの範囲で集計を行っている。このように集計された移動軌跡を図４４（Ａ）に示す。また、図４４（Ｂ）に同図（Ａ）の表に基づいて作成されたヒストグラムを示す。図４４（Ａ）では、一つの移動軌跡を一人として示している。このとき、重み付けを行う旨のフラグが立っていた場合には、確率演算部４６は優先度ポイント上位４０％に含まれる移動軌跡のカウントを２重にカウントする。
【０１２７】
次に、確率演算部４６は、待ち時間あり発生確率値を演算する。この待ち時間あり発生確率値は、以下の式から算出することができる。
待ち時間あり発生確率値＝１−（待ちなし移動軌跡の総数）÷（移動軌跡の総数）
ここで、待ちなし移動軌跡とは、横断待ち時間が閾値以下である移動軌跡である。本実施の形態では閾値を１０秒としている。つまり、横断待ち時間が１０秒以下であれば、横断リンクによる待ちが発生しなかった移動軌跡である。
【０１２８】
図４４（Ａ）の例では、待ち時間あり発生確率値＝１−（１０５÷２６０）から、待ち時間あり発生確率値が約０．６０であることが算出される。従って、待ち時間なし発生確率値は、約０．４となり、横断リンクの実際の待ち時間あり発生確率値および待ち時間なし発生確率は、１／２ではないことがわかる。
【０１２９】
このように順次、歩行者からの歩行者位置情報と車両からの車両位置情報とを収集し、対象となる横断リンクを変更しながら地図情報記憶部４８の待ち時間あり発生確率値および待ち時間なし発生確率値を設定または変更する。
【０１３０】
地図データ送信部４７は、経路案内サーバ３０の地図データ更新部３８と通信して、設定または変更された横断リンクの待ち時間あり発生確率値および待ち時間なし発生確率値を経路案内サーバ３０へ、対象となる横断リンクを識別する情報と共に送信する。地図データ更新部３８は、受信した待ち時間あり発生確率値および待ち時間なし発生確率値を地図情報記憶部３７を参照して更新する。
【０１３１】
このように、電子地図データ生成サーバ４０は、実際の状況に応じた不確定リンクである横断リンクの待ち時間あり発生確率値を算出して、経路案内サーバ３０の経路探索を行う際の精度を向上させることができると共に、出発地から目的地までの到達予測時間の精度を向上させることができる。
【０１３２】
また、優先度ポイントを、横断リンクを同時に通行しようとする歩行者を検出して増加したり、車両の移動軌跡を利用して増加したり、進入前リンクや退出後リンクに応じて増加したりすることで、精度として信頼性の低い移動軌跡の優先度ポイントを相対的に下げることができる。
【０１３３】
本実施の形態では、優先度ポイントを増加させる加算を行うことで、ノイズとなる移動軌跡の優先度ポイントを相対的に低下させているが、収集された歩行者の移動軌跡に予め所定ポイントを付与しておき、加算処理の代わりに減算処理を行うようにして、最終的に優先度ポイントが低いものを上位とすることも可能である。
また、本実施の形態では、経路案内サーバ３０と電子地図データ生成サーバ４０とは別体としているが、同じサーバ内に構築してもよい。
【産業上の利用可能性】
【０１３４】
本発明は、歩行者が携行する携帯電話やＰＤＡ（Personal Digital Assistant）が通信回線を介して経路探索結果を送信するサーバや、携帯型ナビゲーション装置などに好適である。
【図面の簡単な説明】
【０１３５】
【図１】経路案内システムを示す図である。
【図２】携帯電話の構成を示すブロック部である。
【図３】経路案内サーバの構成を示すブロック図である。
【図４】地図データ生成サーバを示すブロック図である。
【図５】経路案内サーバの動作全体を説明するためのフローチャートである。
【図６】経路探索処理例（１）における経路例を示す図である。
【図７】初期経路探索処理の動作を説明するためのフローチャートである。
【図８】探索された経路（Ａ）を示す図である。
【図９】探索された経路（Ｂ）を示す図である。
【図１０】初期経路探索処理により探索された経路を示す図である。
【図１１】初期経路探索処理により探索された経路の合計コストを示す表である。
【図１２】局所経路探索処理の動作を説明するためのフローチャートである。
【図１３】始点となるノードを示す図である。
【図１４】局所経路探索処理における経路探索を説明するためのフローチャートである。
【図１５】（Ａ）〜（Ｄ）は局所経路グループごとの経路を示す図である。
【図１６】（Ａ）〜（Ｄ）は局所経路グループごとの局所コストと合計コストとを示す表である。
【図１７】ノードＨを始点としたときの合計コストを示す表である。
【図１８】ノードＧを始点としたときの合計コストを示す表である。
【図１９】ノードＦを始点としたときの合計コストを示す表である。
【図２０】ノードＥを始点としたときの合計コストを示す表である。
【図２１】経路図１における推奨経路の案内例を示す図である。
【図２２】経路探索処理例（２）における経路例を示す図である。
【図２３】初期経路探索処理の動作を説明するためのフローチャートである。
【図２４】探索された経路（Ｇ）〜経路（Ｉ）を示す図である。
【図２５】初期経路探索処理により探索された経路の合計コストを示す表である。
【図２６】ノードＰを始点としたときの合計コストを示す表である。
【図２７】ノードＱを始点としたときの合計コストを示す表である。
【図２８】ノードＴを始点としたときの合計コストを示す表である。
【図２９】ノードＵを始点としたときの合計コストを示す表である。
【図３０】経路図２における推奨経路の案内例を示す図である。
【図３１】電子地図データ生成サーバの動作を説明するためのフローチャートである。
【図３２】（Ａ）は補間処理を行う前の移動軌跡を示す図、（Ｂ）は補間処理を行った後の移動軌跡を示す図である。
【図３３】（Ａ）は道路に設けられた横断リンクを示す図、（Ｂ）は横断リンクを通過した移動軌跡の一例を示す図、（Ｃ）は横断リンクを通過していない移動軌跡の一例を示す図である。
【図３４】移動軌跡情報テーブルを示す図である。
【図３５】ノイズ除去処理を動作を説明するためのフローチャートである。
【図３６】（Ａ）は優先度ポイントの加算方法を説明するための図、（Ｂ）は進入時刻が同じ移動軌跡に対して加算された移動軌跡情報テーブルを示す図である。
【図３７】（Ａ）および（Ｂ）は車両を利用したノイズ除去処理を説明するための図である。
【図３８】車両の移動軌跡を利用したノイズ除去処理の動作を説明するためのフローチャートである。
【図３９】（Ａ）は車両ごとに停止時間帯を記録したテーブルを示す図、（Ｂ）は横断リンクの車両停止時間テーブルを示す図である。
【図４０】車両停止時間テーブルに基づいて優先度ポイントを増加する加算処理を行った移動軌跡情報テーブルを示す図である。
【図４１】（Ａ）は曲がりながら進入したり退出したりした移動軌跡と、直線的に通過した移動軌跡とを示す図、（Ｂ）は進入前リンクと横断リンクとのなす角を示す図、（Ｃ）は退出後リンクと横断リンクとのなす角を示す図、（Ｄ）は移動軌跡ごとの加算処理を説明するための図である。
【図４２】進入前リンクおよび退出後リンクに基づいて優先度ポイントを増加する加算処理を行った移動軌跡情報テーブルを示す図である。
【図４３】交差点内リンクがある交差点を示す図である。
【図４４】（Ａ）は横断待ち時間を所定値ごとに区分した範囲に含まれる移動軌跡のカウントを行った表であり、（Ｂ）は（Ａ）に示す表に基づいて作成されたヒストグラムである。
【符号の説明】
【０１３６】
３０…経路案内サーバ、３４０…最適経路探索部、３４１…再探索部、３７…地図情報記憶部
【特許請求の範囲】
【請求項１】
歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納される記憶手段と、
出発地から目的地までの各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索手段と、
前記最適経路探索手段に最適経路を探索させ、当該最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、前記最適経路探索手段の探索条件を変更して、一以上の他の経路を前記最適経路探索手段に探索させ、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段とを備えたことを特徴とする経路探索装置。
【請求項２】
前記最適経路探索手段の探索条件の変更は、前記最適経路に含まれる不確定リンクのリンクコストデータの変更である請求項１記載の経路探索装置。
【請求項３】
前記記憶手段には、前記リンク種別が不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータと、待ち時間が発生しない場合の待ち時間なしコストデータとが格納され、
前記再探索手段は、前記最適経路探索手段に不確定リンクのリンクコストデータを変更して探索させるときに、前記待ち時間なしコストデータから前記待ち時間ありコストデータへ変更して合計コストを演算させる請求項２記載の経路探索装置。
【請求項４】
前記再探索手段は、前記一以上の他の経路について探索するときに、
（Ａ）前記最適経路探索手段により最初に探索された最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して新たな最適経路を前記最適経路探索手段に探索させ、
（Ｂ）前記最適経路探索手段により新たな最適経路が探索されると、当該新たな最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して、再度、前記最適経路探索手段により最適経路を探索させ、
（Ｃ）前記最適経路探索手段により探索された経路が、以前に探索されていない新たな経路であれば、更に（Ｂ）を処理し、
（Ｄ）前記最適経路探索手段により探索された経路が、以前に探索された経路に含まれている場合には、探索を終了する請求項３記載の経路探索装置。
【請求項５】
前記再探索手段は、探索された新たな最適経路に不確定リンクが含まれていない場合に、探索を終了する請求項３記載の経路探索装置。
【請求項６】
前記再探索手段は、前記経路候補に含まれるそれぞれの不確定リンクの出発地側のノードを始点として設定し、前記最適経路探索手段にそれぞれの始点から目的地までの最適経路について局所経路として探索する局所経路探索処理を実行して、それぞれの始点ごとの局所経路をグループとした局所経路グループを探索する請求項４または５記載の経路探索装置。
【請求項７】
前記再探索手段は、前記局所経路探索処理を実行するときに、前記最適経路探索手段により前記（Ａ）から（Ｄ）までの処理を実行して前記局所経路を探索する請求項６記載の経路探索装置。
【請求項８】
前記記憶手段には、前記不確定リンクごとに待ち時間の発生の有無の確率を示す待ち発生確率値が格納され、
前記再探索手段は、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択し、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算し、前記待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループごとの合計コストを演算し、前記局所経路グループごとの合計コストに基づいて推奨経路を決定する請求項６または７記載の経路探索装置。
【請求項９】
最適経路探索手段が、歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納された記憶手段を参照して、出発地から目的地まで各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索ステップと、
再探索手段が、前記最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、一以上の他の経路を前記最適経路探索ステップを実行して、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索ステップとを備えたことを特徴とする経路探索方法。
【請求項１０】
コンピュータを、
歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納された記憶手段を参照して、出発地から目的地まで各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、前記合計コストに基づいて最適経路を探索する最適経路探索手段、
前記最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、一以上の他の経路を前記最適経路探索ステップを実行して、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段
として機能させるための経路探索プログラム。
【請求項１１】
コンピュータによる経路探索に利用される地図データであって、
歩行路であるリンクを表すリンクデータおよび該リンクの端点であるノードデータと、
前記リンクの種別を示すためのリンク種別データと、
前記リンクごとに設定されたリンクコストデータと、
前記リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータ、および待ち時間が発生しない場合の待ち時間なしコストデータと
を備え、
コンピュータが、出発地から目的地までの各経路に含まれるリンクデータに設定されたリンクコストデータを読み込み、読み込まれたリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索し、当該最適経路に含まれるリンク種別データを読み込み、読み込まれたリンク種別データがリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれると判定した場合に、該不確定リンクに対応するコストデータを待ち時間なしコストデータから待ち時間ありコストデータへ変更して合計コストを演算して一以上の他の経路を探索し、前記最適経路と共に前記一以上の他の経路を経路候補とすることを特徴とする地図データ。
【請求項１２】
前記リンクコストデータに前記不確定リンクの待ち時間ありまたはなしの発生の確率を示す確率情報データを備えたことを特徴とする請求項１１記載の地図データ。
【請求項１】
歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納される記憶手段と、
出発地から目的地までの各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索手段と、
前記最適経路探索手段に最適経路を探索させ、当該最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、前記最適経路探索手段の探索条件を変更して、一以上の他の経路を前記最適経路探索手段に探索させ、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段とを備えたことを特徴とする経路探索装置。
【請求項２】
前記最適経路探索手段の探索条件の変更は、前記最適経路に含まれる不確定リンクのリンクコストデータの変更である請求項１記載の経路探索装置。
【請求項３】
前記記憶手段には、前記リンク種別が不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータと、待ち時間が発生しない場合の待ち時間なしコストデータとが格納され、
前記再探索手段は、前記最適経路探索手段に不確定リンクのリンクコストデータを変更して探索させるときに、前記待ち時間なしコストデータから前記待ち時間ありコストデータへ変更して合計コストを演算させる請求項２記載の経路探索装置。
【請求項４】
前記再探索手段は、前記一以上の他の経路について探索するときに、
（Ａ）前記最適経路探索手段により最初に探索された最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して新たな最適経路を前記最適経路探索手段に探索させ、
（Ｂ）前記最適経路探索手段により新たな最適経路が探索されると、当該新たな最適経路に含まれる不確定リンクのリンクコストデータを待ち時間ありコストデータに設定して、再度、前記最適経路探索手段により最適経路を探索させ、
（Ｃ）前記最適経路探索手段により探索された経路が、以前に探索されていない新たな経路であれば、更に（Ｂ）を処理し、
（Ｄ）前記最適経路探索手段により探索された経路が、以前に探索された経路に含まれている場合には、探索を終了する請求項３記載の経路探索装置。
【請求項５】
前記再探索手段は、探索された新たな最適経路に不確定リンクが含まれていない場合に、探索を終了する請求項３記載の経路探索装置。
【請求項６】
前記再探索手段は、前記経路候補に含まれるそれぞれの不確定リンクの出発地側のノードを始点として設定し、前記最適経路探索手段にそれぞれの始点から目的地までの最適経路について局所経路として探索する局所経路探索処理を実行して、それぞれの始点ごとの局所経路をグループとした局所経路グループを探索する請求項４または５記載の経路探索装置。
【請求項７】
前記再探索手段は、前記局所経路探索処理を実行するときに、前記最適経路探索手段により前記（Ａ）から（Ｄ）までの処理を実行して前記局所経路を探索する請求項６記載の経路探索装置。
【請求項８】
前記記憶手段には、前記不確定リンクごとに待ち時間の発生の有無の確率を示す待ち発生確率値が格納され、
前記再探索手段は、前記局所経路グループに含まれる全ての不確定リンクの待ち時間の発生有無の組み合わせ事象ごとに最適な局所経路を選択し、選択された局所経路の合計コストおよび始点としたノードに至るまでの最適経路の合計コストを合算して組み合わせ事象ごとの合計コストを演算し、前記待ち発生確率値に基づいて組み合わせ事象が発生する事象発生確率値を演算し、この事象発生確率値と組み合わせ事象ごとの合計コストとを乗算して全体を合算することで局所経路グループごとの合計コストを演算し、前記局所経路グループごとの合計コストに基づいて推奨経路を決定する請求項６または７記載の経路探索装置。
【請求項９】
最適経路探索手段が、歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納された記憶手段を参照して、出発地から目的地まで各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索する最適経路探索ステップと、
再探索手段が、前記最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、一以上の他の経路を前記最適経路探索ステップを実行して、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索ステップとを備えたことを特徴とする経路探索方法。
【請求項１０】
コンピュータを、
歩行路を表すリンクデータと、該リンクの端点を示すノードデータと、前記リンクの種別を示すリンク種別データと、前記リンクごとに設定されたリンクコストデータとを含む地図データが格納された記憶手段を参照して、出発地から目的地まで各経路に含まれるそれぞれのリンクのリンクコストデータから合計コストを演算し、前記合計コストに基づいて最適経路を探索する最適経路探索手段、
前記最適経路に、前記リンク種別データとしてリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれる場合に、一以上の他の経路を前記最適経路探索ステップを実行して、前記最適経路と共に前記一以上の他の経路を経路候補とする再探索手段
として機能させるための経路探索プログラム。
【請求項１１】
コンピュータによる経路探索に利用される地図データであって、
歩行路であるリンクを表すリンクデータおよび該リンクの端点であるノードデータと、
前記リンクの種別を示すためのリンク種別データと、
前記リンクごとに設定されたリンクコストデータと、
前記リンク種別データがリンクを通行するための所要時間が不確定な不確定リンクであるリンクのリンクコストデータとして、待ち時間が発生した場合の待ち時間ありコストデータ、および待ち時間が発生しない場合の待ち時間なしコストデータと
を備え、
コンピュータが、出発地から目的地までの各経路に含まれるリンクデータに設定されたリンクコストデータを読み込み、読み込まれたリンクコストデータから合計コストを演算し、該合計コストに基づいて最適経路を探索し、当該最適経路に含まれるリンク種別データを読み込み、読み込まれたリンク種別データがリンクを通行するための所要時間が不確定な不確定リンクが含まれるか否かを判定し、当該最適経路中に不確定リンクが含まれると判定した場合に、該不確定リンクに対応するコストデータを待ち時間なしコストデータから待ち時間ありコストデータへ変更して合計コストを演算して一以上の他の経路を探索し、前記最適経路と共に前記一以上の他の経路を経路候補とすることを特徴とする地図データ。
【請求項１２】
前記リンクコストデータに前記不確定リンクの待ち時間ありまたはなしの発生の確率を示す確率情報データを備えたことを特徴とする請求項１１記載の地図データ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３】
【図４４】
【公開番号】特開２００９−２９４１５３（Ｐ２００９−２９４１５３Ａ）
【公開日】平成２１年１２月１７日（２００９．１２．１７）
【国際特許分類】
【出願番号】特願２００８−１４９７７３（Ｐ２００８−１４９７７３）
【出願日】平成２０年６月６日（２００８．６．６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２１年１２月１７日（２００９．１２．１７）
【国際特許分類】
【出願日】平成２０年６月６日（２００８．６．６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]