ナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラム
【課題】全てのユーザにとって効率の良い合流地点を設定することができるナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラムを提供する。
【解決手段】ナビゲーション装置１は、各ユーザの出発地を取得して、各出発地から目的地までの初期経路をそれぞれ探索し、出発地が異なる複数の初期経路の重複区間があるか否かを判断し、重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、重複区間を含まない初期経路の出発地に対して、合流候補地点を経由する候補経路を探索し、候補経路の初期経路に対する増加コストを算出し、増加コストの大きさに応じて前記合流候補地点を合流地点として特定する。
【解決手段】ナビゲーション装置１は、各ユーザの出発地を取得して、各出発地から目的地までの初期経路をそれぞれ探索し、出発地が異なる複数の初期経路の重複区間があるか否かを判断し、重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、重複区間を含まない初期経路の出発地に対して、合流候補地点を経由する候補経路を探索し、候補経路の初期経路に対する増加コストを算出し、増加コストの大きさに応じて前記合流候補地点を合流地点として特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラム
に関する。
【背景技術】
【０００２】
複数のユーザが、異なる地点から出発し、途中で合流する場合、ユーザは、各車両の経路を選び、地図上で適当な施設等を選んでいた。しかし、このように合流地点を選ぶ場合には、各ユーザが合流しやすいか否かを判断するのは困難であり、一方のユーザにとっては合流しやすい地点であっても、他方のユーザにとっては合流しにくい地点である可能性がある。
【０００３】
これに対し、特許文献１には、各ユーザに対して待ち合わせ場所に関する情報を提供するシステムが記載されている。このシステムでは、各車両の出発地から目的地までの経路を単独でそれぞれ探索し、さらに任意の車両２台からなる組を形成して、各組の中で最も早い時刻に合流する組を検出する。そして、その組の合流地点を、全体の合流地点とする。
【特許文献１】特開２００４−４５３３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところが、上記したように合流地点を決定すると、最も早い時刻に合流する組以外の車両にとって効率の悪い合流地点が設定される場合が想定される。例えば、合流地点を経由するために、目的地と全く異なる方面に向かって長距離を走行する必要が生じてしまう場合がある。
【０００５】
本発明は、上記問題点に鑑みてなされたものであり、その目的は、各ユーザにとって合流しやすい合流地点を設定することができるナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記問題点を解決するために、請求項１に記載の発明は、各ユーザの出発地を取得する取得手段と、前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段とを備えたことを要旨とする。
【０００７】
請求項２に記載の発明は、請求項１に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記初期経路のコストに対する増加コストの割合であるコスト増加率を算出し、算出した割合が所定率以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを要旨とする。
【０００８】
請求項３に記載の発明は、請求項２に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記コスト増加率が最小となる前記合流候補地点を合流地点として特定することを要旨とする。
【０００９】
請求項４に記載の発明は、請求項１に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記初期経路のコストに対する増加コストが所定量以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを要旨とする。
【００１０】
請求項５に記載の発明は、請求項４に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記増加コストが最小となる前記合流候補地点を合流地点として特定することを要旨とする。
【００１１】
請求項６に記載の発明は、経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出方法において、前記制御手段が、各ユーザの出発地を取得し、前記各出発地からの初期経路をそれぞれ探索するとともに、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断し、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出し、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定することを要旨とする。
【００１２】
請求項７に記載の発明は、経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出プログラムにおいて、前記制御手段を、各ユーザの出発地を取得する取得手段と、前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段として機能させることを要旨とする。
【発明の効果】
【００１３】
請求項１に記載の発明によれば、ナビゲーションシステムは、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１４】
請求項２に記載の発明によれば、初期経路のコストに対する増加コストの割合が、所定率以下である合流候補地点を抽出し、その合流候補地点から合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１５】
請求項３に記載の発明によれば、コスト増加率が最小となる合流候補地点を合流地点として特定する。このため、各ユーザにとって最も合流しやすい合流地点を設定することができる。
【００１６】
請求項４に記載の発明によれば、初期経路のコストに対する増加コストが、所定量以下である合流候補地点を抽出し、抽出した合流候補地点から合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１７】
請求項５に記載の発明によれば、増加コストが最小となる合流候補地点を合流地点として特定する。このため、各ユーザにとって最も合流しやすい合流地点を設定することがで
きる。
【００１８】
請求項６に記載の発明によれば、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１９】
請求項７に記載の発明によれば、合流地点抽出プログラムに従って、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【発明を実施するための最良の形態】
【００２０】
（第１実施形態）
以下、本発明を具体化した一実施形態を図１〜図８に従って説明する。本実施形態では、ナビゲーションシステムを１台の車両に搭載されたナビゲーション装置１に具体化し、該ナビゲーション装置１が、車両３台以上の合流地点を特定する場合について説明する。
【００２１】
図１は、車両に搭載されたナビゲーション装置１の説明図である。ナビゲーション装置１は、合流地点を特定する制御部３を備え、制御部３は、ＣＰＵ１０、ＲＡＭ１１、ＲＯＭ１２、車両側Ｉ／Ｆ１３、通信Ｉ／Ｆ１４、画像プロセッサ１５、入力Ｉ／Ｆ１６を備えている。この制御部３は、取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段を構成する。ＲＯＭ１２又は図示しない記憶部には、合流地点抽出プログラムが格納されている。
【００２２】
ＣＰＵ１０は、車両側Ｉ／Ｆ１３を介して、ＧＰＳ（Global Positioning System）受
信部３０、ジャイロセンサ３１及び車速センサ３２から取得した検出信号に基づき、電波航法及び自律航法によって自車位置を特定する。
【００２３】
通信Ｉ／Ｆ１４は、専用回線又はインターネット等の公衆回線網に接続するためのインターフェースであって、ＣＰＵ１０は、この通信Ｉ／Ｆ１４を介して、各車両に特定した合流地点を通知する。
【００２４】
また、ナビゲーション装置１は、内蔵ハードディスク、又は光ディスク等の外部記憶媒体からなる地理情報記憶部１８及びＰＯＩ（Point Of Interest）情報記憶部１９から、
各種データを読み出す。
【００２５】
地理情報記憶部１８には、目的地までの経路を探索するための各経路ネットワークデータ（以下、経路データ２０という）と、タッチパネルディスプレイ２に地図画面２Ａを出力するための地図描画データ２１とが格納されている。
【００２６】
図２に示すように、経路データ２０は、各メッシュの識別子であるメッシュＩＤ２０Ｉ、リンクＩＤ２０Ａ、接続ノード２０Ｂ、道路種別２０Ｃ、リンクコスト２０Ｄを有している。ノードは、交差点、インターチェンジ、道路の端点等を示すデータ要素であって、リンクは各ノードを接続するデータ要素である。
【００２７】
メッシュＩＤ２０Ｉは、全国を分割した各区域を示し、メッシュＩＤ２０Ｉには、そのメッシュ内に含まれるリンクデータが関連付けられている。リンクデータのリンクＩＤ２
０Ａは、リンクの識別子を示している。接続ノード２０Ｂは、そのリンクに接続したノードの番号等を示す。道路種別２０Ｃは、そのリンクが対応する道路の種別であって、国道、高速道路、一般道等を示す。リンクコスト２０Ｄは、そのリンク自身に割り当てられたコストである。本実施形態では、リンクコスト２０Ｄは、リンク長、道幅、車線数、道路種別等の道路の固有情報に基づくコスト、そのリンクを走行する際にかかる所要時間、渋滞の有無等の時間情報に基づくコストを有している。例えば、リンク長が長い場合、コストは大きく設定され、道幅が大きい場合、コストは小さく設定される。所要時間が長い場合や、渋滞が発生している場合にはコストは大きく設定される。また、リンクコスト２０Ｄは、一つのリンクに対して、「距離優先」、「一般道路優先」等の探索条件や、道路種別に応じて予め設定されたコストをそれぞれ有していてもよい。
【００２８】
また、地図描画データ２１は、全国の地図を分割したメッシュ毎に格納され、道路、市街地、施設等を描画するための背景データ、道路の形状を示す道路データ等を有している。
【００２９】
ＣＰＵ１０は、例えば出発地の座標と目的地の座標とを取得し、経路探索要求を入力すると、複数の探索条件下で、出発地から目的地までのリンクコスト２０Ｄの合計が最小となる推奨経路をそれぞれ探索する。
【００３０】
ＣＰＵ１０は、必要な場合にはリンクコスト２０Ｄに道路種別や渋滞情報等に応じた係数を乗算又は加算し、係数を乗算又は加算したリンクコスト２０Ｄの合計が最小となる経路を探索する。「一般道路優先」の探索条件の下で探索を行う場合には、有料道路のリンクコスト２０Ｄを高く設定して、有料道路を通行しづらくするようにしてもよい。また、探索条件に応じて異なるコスト値がリンクコスト２０Ｄに設定されている場合には、その探索条件に応じたコスト値を用いる。
【００３１】
ＰＯＩ情報記憶部１９には、ＰＯＩデータ２２が記憶されている。図３に示すように、ＰＯＩデータ２２は、エリアコード２２Ａ及びジャンル２２Ｂを管理データとして有している。エリアコード２２Ａは、上記メッシュＩＤでもよいし、都道府県等の行政区分でもよい。ジャンル２２Ｂは、例えば「見る」、「遊ぶ」、「食べる」という目的別の階層と、「ガソリンスタンド」、「ゴルフ場」等の施設種別の階層とを有している。尚、図ではエリアコード２２Ａの下位にジャンル２２Ｂが設定されているが、上位でもよい。
【００３２】
名称２２Ｉは、その施設の名称であって、座標２２Ｊは、その施設の座標を示す。リンクＩＤ２２Ｋは、その施設が属するリンクのＩＤ又はその施設に最も近いリンクのＩＤである。住所２２Ｌは、その施設の住所である。この他にも、ＰＯＩデータ２２は、施設の電話番号、郵便番号等を有している。
【００３３】
また、ナビゲーション装置１の図示しない記憶部には、合流地点として設定可能な施設のジャンル２２Ｂのリスト等が予め記憶されている。或いは、ＰＯＩデータ２２に、その施設が合流地点として設定可能な施設であるか否かを示すフラグを設定してもよい。
【００３４】
次に、本実施形態の処理手順について、図４及び図５に従って説明する。まず、ＣＰＵ１０は、上記合流地点抽出プログラムを用いて、合流モードが指定されたか否かを判断する。タッチパネルディスプレイ２又は操作スイッチ２Ｂ（図１参照）で合流モードを指定する操作が行われると、タッチパネルディスプレイ２のコントローラから合流モード要求が出力される。ＣＰＵ１０は、この合流モード要求を、合流地点の判定処理の開始トリガとする。
【００３５】
ＣＰＵ１０は、合流モード要求を入力すると、各車両の出発地を取得する（ステップＳ
１）。ここでは、ユーザはタッチパネル操作により、各車両の出発地をそれぞれ入力する。ＣＰＵ１０は、タッチパネルコントローラから入力Ｉ／Ｆ１６を介して出発地の位置を取得すると、その位置に対応する座標又はリンクＩＤを取得して、ＲＡＭ１１等に一時記憶する。
【００３６】
次に、ＣＰＵ１０は、目的地を取得する（ステップＳ２）。このときもステップＳ１と同様に、ユーザはタッチパネル操作により目的地の位置を指定し、ＣＰＵ１０は、タッチパネルコントローラから入力Ｉ／Ｆ１６を介して目的地の位置を取得する。尚、目的地は、同一地点でもよいし、異なる地点でもよい。
【００３７】
出発地と目的地とを取得すると、ＣＰＵ１０は、合流地点を特定する（ステップＳ３）。この合流地点の特定処理について、図５に従って説明する。
ＣＰＵ１０は、各車両の出発地と、目的地とを用いて重複区間沿いの合流可能地点の検出処理を行う（ステップＳ３−１）。この処理では、公知の方法を用いることができる。例えば、各車両の出発地毎に、予め決められた探索条件下で、目的地までの経路を単独で探索する。このときの探索条件は特に限定されない。以下、このときの探索により得られた経路を、初期経路という。尚、このとき用いる探索条件は、単数でもよく複数でもよい。
【００３８】
そして、ＣＰＵ１０は、グループを構成する全ての車両５の初期経路が重複する重複区間があるか否かを判断する。例えば、目的地が同一である場合には、初期経路が交差する交差地点があるか否かに基づき、重複区間があるか否かを判断してもよい。図６に示すように、初期経路ＲＰ，ＲＱ上に各経路が交差する交差地点ＰＣがある場合、その交差地点ＰＣから目的地Ｇまでの各経路は重複する。全ての車両５の経路が重複した重複区間が存在する場合には、その重複区間沿いに合流可能な地点があるか否かをＰＯＩデータ２２を用いて検索する。さらに、合流地点として設定可能な施設のリスト又はＰＯＩデータ２２の上記フラグを参照して、その重複区間沿いの施設の中から、合流可能な施設があるか否かを検索する。
【００３９】
次に、ＣＰＵ１０は、ステップＳ３−１の検出結果に基づき、上記重複区間沿いに全員が合流することができる合流可能地点があるか否かを判断する（ステップＳ３−２）。ステップＳ３−１において、全ての車両５の経路が全く重複しない場合、及び一部の車両５の経路のみ重複する場合は、全ての車両の重複区間沿いに合流可能な地点が無いと判断して（ステップＳ３−２においてＮＯ）、ステップＳ３−４に進む。また、全ての車両５の経路が重複する重複区間があるが、合流可能な施設がない場合にもステップＳ３−４に進む。
【００４０】
全ての車両の重複区間沿いに合流可能な地点があると判断すると（ステップＳ３−２においてＹＥＳ）、ＣＰＵ１０は、その候補地点を合流地点として特定する（ステップＳ３−３）。全員が合流可能な候補地点が複数存在する場合には、予め定めた条件で一つの地点を合流地点として特定する。例えば、各車両の目的地が同一である場合、その目的地から最も遠い地点を合流地点として特定する。或いは、各候補地点をタッチパネルディスプレイ２に表示して、ユーザの選択操作により合流地点を特定するようにしてもよい。
【００４１】
一方、全ての初期経路が重複する重複区間が無い場合、及びその重複区間はあっても合流可能な地点が無い場合（ステップＳ３−２においてＮＯ）、２台以上が合流可能な候補地点があるか否かを判断する（ステップＳ３−４）。例えば、図６に示すように、合流予定の３台の車両５Ｐ〜５Ｒのうち、車両５Ｐ，５Ｑの初期経路ＲＰ，ＲＱのみに重複区間が検出され、重複区間沿いに合流可能な候補地点Ｐ１〜Ｐ４が検出されている場合、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステ
ップＳ３−５に進む。
【００４２】
また、図７に示すように、合流予定の４台の車両５Ｐ〜５Ｓのうち、車両５Ｐ及び車両５Ｑのみの重複区間に候補地点Ｐ１〜Ｐ３が検出されている場合、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステップＳ３−５に進む。
【００４３】
さらに、図８に示すように、車両５Ｐ及び車両５Ｑの初期経路ＲＰ，ＲＱの重複区間沿いに候補地点Ｐ１〜Ｐ３があり、車両５Ｒ及び車両５Ｓの経路の重複区間沿いにも異なる候補地点Ｐ４，Ｐ５がある場合にも、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステップＳ３−５に進む。
【００４４】
また、異なる車両５の経路に重複区間が全くない場合、２台以上が合流可能な候補地点がないと判断して（ステップＳ３−４においてＮＯ）、目的地を合流地点として特定し（ステップＳ３−９）、合流地点の特定処理を終了する。
【００４５】
ステップＳ３−５では、ＣＰＵ１０は、候補地点に合流した場合のコスト増加率を算出する。コスト増加率の算出の対象となる車両５は、その初期経路上に交差地点ＰＣがない車両である。例えば、図６に示すように、車両５Ｒに対して探索された初期経路ＲＲが、他の車両５Ｐ，５Ｑの候補地点Ｐ１〜Ｐ４と重複しない場合、車両５Ｒを対象としてコスト増加率を算出する。
【００４６】
具体的には、ＣＰＵ１０は、車両５Ｒに対して探索された一つの初期経路ＲＲのコストを取得する。このとき、ステップＳ３−１の初期経路の探索の際に用いたコストをそのまま用いてもよいが、必要に応じて、合流地点抽出のためのコスト計算条件で、初期経路ＲＲのコスト合計を算出する。また、渋滞情報、天候情報等の時間の経過とともに変化する情報をデータ要素として加味している場合には、外部から最新の渋滞情報等を取得してもよい。
【００４７】
また、ＣＰＵ１０は、車両５Ｒの出発地Ｓから各候補地点Ｐ１〜Ｐ４を経由して目的地Ｇに到達する候補経路ＲＴ１〜ＲＴ４をそれぞれ探索する。このときの探索条件は初期経路の探索条件と同じ条件である。また、ＣＰＵ１０は、候補経路ＲＴ１〜ＲＴ４のコスト合計をそれぞれ取得する。このコスト合計は、初期経路ＲＲのコスト合計に用いられた上記コスト計算条件で算出された合計値である。
【００４８】
そして、ＣＰＵ１０は、候補経路ＲＴ１〜ＲＴ４のコスト合計から、初期経路ＲＲのコスト合計を減算して、増加コストΔＣを算出する。さらに、増加コストΔＣを、初期経路ＲＲのコスト合計で除算して、コスト増加率（％）を算出する。
【００４９】
例えば、初期経路のコスト合計が「１０００」であって、候補地点Ｐ１を経由する候補経路ＲＴ１のコスト合計が「１５００」である場合、増加コストΔＣは「５００」であって、コスト増加率は「５０％」である。また、候補地点Ｐ２を経由する候補経路ＲＴ２のコスト合計が「１２１０」である場合、コスト増加率は「２１％」である。また、候補地点Ｐ３を経由する候補経路ＲＴ３のコスト合計が「１２００」である場合、コスト増加率は「２０％」である。さらに、候補地点Ｐ４を経由する候補経路ＲＴ４のコスト合計が「１１００」である場合、コスト増加率は「１０％」である。
【００５０】
次に、ＣＰＵ１０は、コスト増加率が所定率（Ｘ％）以下の候補地点があるか否かを判断する（ステップＳ３−６）。本実施形態では、所定率は２０％に設定されている。候補経路ＲＴ１〜ＲＴ４のうち、コスト増加率がＸ％以下である経路は、候補経路ＲＴ３及び
候補経路ＲＴ４であるため、ステップＳ３−６においてコスト増加率がＸ％以下の候補地点があると判断して（ステップＳ３−６においてＹＥＳ）、該当する候補地点を抽出し、ＲＡＭ１１等に一時記憶する（ステップＳ３−７）。
【００５１】
さらに、ＣＰＵ１０は、一時記憶された候補地点の中から、合流地点を特定する（ステップＳ３−８）。候補地点が一つしか抽出されていない場合には、その候補地点を合流地点として特定する。抽出した候補地点が複数である場合、ＣＰＵ１０は、各車両５のコスト増加率の平均が最も小さい候補地点を合流地点とする。１台の車両５に対してコスト増加率を算出している場合には、コスト増加率が最小となる候補地点を合流地点とする。例えば、ステップＳ３−７において、候補地点Ｐ３，Ｐ４が一時記憶されている場合、候補地点Ｐ３，Ｐ４をそれぞれ経由する候補経路ＲＴ３，ＲＴ４のコスト増加率を比較する。候補経路ＲＴ３のコスト増加率は「２０％」であり、候補経路ＲＴ４のコスト増加率は「１０％」であるため、ＣＰＵ１０は、候補経路ＲＴ４の候補地点Ｐ４を合流地点として特定する。合流地点を特定すると、合流地点の特定処理を終了し、図４に示すステップＳ５に進む。
【００５２】
尚、ここでは３台が同じ目的地に対して合流する場合について説明したが、４台以上が同じ目的地に対して合流する場合も、上記した手順と同様に合流地点を特定する。図７に示すように２台の車両５Ｒ，５Ｓの初期経路ＲＲ，ＲＳ上に重複区間がなく、他２台の車両５Ｐ，５Ｑの初期経路ＲＰ，ＲＱ上に候補地点Ｐ１〜Ｐ３がある場合、車両５Ｒ，５Ｓが候補地点Ｐ１〜Ｐ３を経由した候補経路ＲＴ１〜ＲＴ６をそれぞれ探索する。さらに、候補経路ＲＴ１〜ＲＴ６のコスト増加率を算出する。そして、車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以内となる候補地点がある場合には、候補地点を抽出し、抽出した候補地点の一つを合流地点とする。車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以内となる候補地点がない場合には、目的地を合流地点とする。
【００５３】
また、図８に示すように、全ての車両５Ｐ〜５Ｓの経路が重複する区間はないものの、車両５Ｐ，５Ｑの候補地点Ｐ１〜Ｐ３と、車両５Ｒ，５Ｓの候補地点Ｐ４，Ｐ５がそれぞれ存在する場合がある。この場合、候補地点Ｐ１〜Ｐ３を経由する場合の車両５Ｒ，５Ｓのコスト増加率を算出するとともに、候補地点Ｐ４，Ｐ５を経由する場合の車両５Ｐ，５Ｑのコスト増加率を算出する。そして、車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以下となる候補地点、車両５Ｐ，５Ｑ両方のコスト増加率がＸ％以下となる候補地点を抽出し、抽出した候補地点の中から、上記したように合流地点を特定する。
【００５４】
合流地点を特定すると、図４に示すように、ＣＰＵ１０は、合流地点を経由する経路を各出発地毎に探索し、探索した経路の経路案内を行う（ステップＳ４）。このとき、ＣＰＵ１０は、通信Ｉ／Ｆ１４を介して、同じ目的地に向かう車両５のナビゲーション装置、或いはユーザが所持する携帯端末に、合流地点の座標をそれぞれ送信してもよい。他のユーザの各端末は、選択された合流地点の座標を取得し、その合流地点までの経路を端末のディスプレイ等に表示する。
【００５５】
第１実施形態によれば、以下のような効果を得ることができる。
（１）第１実施形態では、ナビゲーション装置１は、各車両５の出発地を取得して、出発地からの初期経路を経路データ２０を用いてそれぞれ探索し、出発地が異なる複数の初期経路の交差地点を検索することにより、重複区間の有無を判断する。重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、交差地点が初期経路上にない、即ち重複区間を含まない初期経路の車両５の出発地に対して、該候補地点を経由した候補経路を探索する。さらに、候補経路の初期経路に対する増加コストΔＣを経路データ２０を用いて算出し、増加コストΔＣの大きさに応じて候補地点を合流地点として特定する。このため、例えば全ての車両５の初期経路が重複する区間が無い場合にも、全ての車両５に
とって、合流のために長距離又は長時間走行する必要が無い、合流しやすい合流地点を設定することができる。
【００５６】
（２）第１実施形態では、ナビゲーション装置１は、初期経路のコストに対する候補経路のコスト増加率を算出し、算出したコスト増加率がＸ％以下となる候補地点の中から、合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００５７】
（３）第１実施形態では、コスト増加率がＸ％以下となる候補地点が複数存在する場合に、コスト増加率が最小となる候補地点を合流地点として特定する。このため、全ての車両５にとって最も合流しやすい合流地点を設定することができる。
【００５８】
（第２実施形態）
次に、本発明を具体化した第２実施形態を図９〜図１０に従って説明する。尚、第２実施形態は、第１実施形態のシステム構成を変更しており、同様の部分についてはその詳細な説明を省略する。
【００５９】
本実施形態では、ナビゲーションシステムを、図９に示す経路案内サーバ５１に具体化している。経路案内サーバ５１は、専用線又はインターネット等の公衆回線網からなるネットワークＮと、基地局５２と介して、車両５に搭載されたナビゲーション装置１及びユーザ端末５３と接続されている。ナビゲーション装置１は、第１実施形態と同じ構成とする。ユーザ端末５３は、図９では携帯電話としたが、パーソナルコンピュータ、その他の端末に具体化してもよい。
【００６０】
図１０は、経路案内サーバ５１のハードウェア構成を示すブロック図である。経路案内サーバ５１は、ＣＰＵ５５、ＲＡＭ５６、ＲＯＭ５７、通信Ｉ／Ｆ５８からなる制御コンピュータ５４と、地理情報記憶部５９、ユーザ情報記憶部６０とを備えている。制御コンピュータ５４は、取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段を構成する。制御コンピュータ５４には、合流地点抽出プログラムが格納されている。
【００６１】
地理情報記憶部５９には、経路データ２０が格納されている。このデータは、上記したナビゲーション装置１に格納された経路データ２０と同じ構成となっている。
また、ユーザ情報記憶部６０には、ユーザデータ６１が格納されている。ユーザデータ６１は、予め登録されたユーザに関するデータであって、各ユーザが所持するナビゲーション装置１又はユーザ端末５３の固有アドレス、ユーザＩＤ、パスワード等が格納されている。経路案内サーバ５１は、ナビゲーション装置１又はユーザ端末５３からログイン要求を受け付けた際に、このユーザデータ６１を用いてユーザ認証を行う。
【００６２】
本実施形態の処理手順について、図４に従って説明する。経路案内サーバ５１は、ナビゲーション装置１又はユーザ端末５３から、全ての車両５の出発地を取得するとともに（ステップＳ１）、目的地を取得する（ステップＳ２）。尚、目的地は、代表ユーザのみから取得するようにしてもよい。また、目的地に向かう車両の台数を、代表ユーザのナビゲーション装置１又はユーザ端末５３から取得する。
【００６３】
目的地、及び全ての車両５の出発地の収集が完了すると、ＣＰＵ５５は、上記した手順で合流地点の特定処理を行う（ステップＳ３）。合流地点を特定すると、ＣＰＵ５５は、その合流地点を経由した経路を各出発地毎に探索し、ナビゲーション装置１又はユーザ端末５３に対して経路案内を行う（ステップＳ４）。このとき、ＣＰＵ５５は、通信Ｉ／Ｆ５８を介して、ユーザ情報記憶部６０に登録されたナビゲーション装置１又はユーザ端末
５３に、特定した合流地点の座標と、探索した経路を示す経路データとをそれぞれ送信する。ナビゲーション装置１又はユーザ端末５３は、受信した合流地点の座標及び経路データを用いて、合流地点の位置と目的地までの経路をディスプレイにそれぞれ表示する。
【００６４】
第２実施形態によれば、以下のような効果を得ることができる。
（４）第２実施形態では、経路案内サーバ５１が、出発地及び目的地を取得し、各ユーザの合流地点を特定する。このため、ナビゲーション装置１やユーザ端末５３の処理を軽減することができる。また、ユーザ端末５３は、経路データ２０を格納していなくても、自車位置を経路案内サーバ５１に送信するのみで、合流地点を取得することができる。
【００６５】
（第３実施形態）
次に、本発明を具体化した第３実施形態を図１１に従って説明する。尚、第３実施形態は、第１実施形態の経路データの構成を変更したのみの構成であり、同様の部分についてはその詳細な説明を省略する。
【００６６】
本実施形態では、リンクコスト２０Ｄには、料金データ７０が含まれている。料金データ７０は、有料道路を通過する際や、フェリーを使用する際の料金を示すデータであって、例えば高速道路のＩＣ間の料金を示している。尚、料金データ７０の構成は、図１１に示す構成に限定されず、他の構成でもよい。
【００６７】
ステップＳ３では、ナビゲーション装置１は、候補地点に合流した際のコスト増加率を、この料金データ７０を用いて算出する。この場合、増加コストΔＣは、料金である。この増加コストΔＣには、初期経路に対する候補経路の走行距離の増加分に基づく燃料費を含めてもよい。コスト増加率は、増加コストΔＣを初期経路を走行する際にかかる料金で除算して算出する。そして、コスト増加率が、Ｘ％以下となる候補地点を抽出し、それらの候補地点から合流地点を特定する。
【００６８】
第３実施形態によれば、以下のような効果を得ることができる。
（５）第３実施形態では、コスト増加率を算出する際に、料金データ７０を用いる。このため、全ての車両５の初期経路が重複する区間が無い場合にも、全ての車両５にとって、料金が過度に高くならない、合流しやすい合流地点を設定することができる。
【００６９】
尚、上記各実施形態は以下のように変更してもよい。
・上記各実施形態では、初期経路に対する候補経路のコスト増加率を算出し、そのコスト増加率がＸ％以下の候補地点を抽出したが、初期経路に対する候補経路の増加コストΔＣが所定量以下の候補地点を抽出するようにしてもよい。
【００７０】
・上記実施形態では、３台以上の車両５が目的地に向かう際の合流地点の特定について説明したが、３人以上のユーザが徒歩や電車等の車両以外の交通手段によって目的地に向かう場合に合流地点を特定しても良い。この場合、ユーザのうち少なくともひとりが、経路案内サーバ５１に接続可能なユーザ端末５３を所持するものとする。
【図面の簡単な説明】
【００７１】
【図１】ナビゲーション装置のハードウェア構成を示すブロック図。
【図２】経路データのデータ構成を示す概念図。
【図３】ＰＯＩデータのデータ構成を示す概念図。
【図４】全体の処理手順を示すフローチャート。
【図５】合流地点の特定の処理手順を示すフローチャート。
【図６】３台の車両に対する合流地点の特定の手順を示す概念図。
【図７】４台の車両に対する合流地点の特定の手順を示す概念図。
【図８】４台の車両に対する合流地点の特定の手順を示す概念図。
【図９】第２実施形態の経路案内システムのネットワーク図。
【図１０】経路案内サーバのハードウェア構成を示すブロック図。
【図１１】料金データのデータ構成を示す概念図。
【符号の説明】
【００７２】
１…ナビゲーションシステムを構成するナビゲーション装置、３…取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段としての制御部、５１…ナビゲーションシステムとしての経路案内サーバ、５４…出発地取得手段、経路探索手段、初期経路手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段としての制御コンピュータ、Ｇ…目的地、ＲＴ１〜ＲＴ６…候補経路、ＲＰ〜ＲＳ…初期経路、Ｐ１〜Ｐ４…合流候補地点としての候補地点、ＰＣ…交差地点、Ｓ…出発地、ΔＣ…増加コスト。
【技術分野】
【０００１】
本発明は、ナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラム
に関する。
【背景技術】
【０００２】
複数のユーザが、異なる地点から出発し、途中で合流する場合、ユーザは、各車両の経路を選び、地図上で適当な施設等を選んでいた。しかし、このように合流地点を選ぶ場合には、各ユーザが合流しやすいか否かを判断するのは困難であり、一方のユーザにとっては合流しやすい地点であっても、他方のユーザにとっては合流しにくい地点である可能性がある。
【０００３】
これに対し、特許文献１には、各ユーザに対して待ち合わせ場所に関する情報を提供するシステムが記載されている。このシステムでは、各車両の出発地から目的地までの経路を単独でそれぞれ探索し、さらに任意の車両２台からなる組を形成して、各組の中で最も早い時刻に合流する組を検出する。そして、その組の合流地点を、全体の合流地点とする。
【特許文献１】特開２００４−４５３３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところが、上記したように合流地点を決定すると、最も早い時刻に合流する組以外の車両にとって効率の悪い合流地点が設定される場合が想定される。例えば、合流地点を経由するために、目的地と全く異なる方面に向かって長距離を走行する必要が生じてしまう場合がある。
【０００５】
本発明は、上記問題点に鑑みてなされたものであり、その目的は、各ユーザにとって合流しやすい合流地点を設定することができるナビゲーションシステム、合流地点抽出方法及び合流地点抽出プログラムを提供することにある。
【課題を解決するための手段】
【０００６】
上記問題点を解決するために、請求項１に記載の発明は、各ユーザの出発地を取得する取得手段と、前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段とを備えたことを要旨とする。
【０００７】
請求項２に記載の発明は、請求項１に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記初期経路のコストに対する増加コストの割合であるコスト増加率を算出し、算出した割合が所定率以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを要旨とする。
【０００８】
請求項３に記載の発明は、請求項２に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記コスト増加率が最小となる前記合流候補地点を合流地点として特定することを要旨とする。
【０００９】
請求項４に記載の発明は、請求項１に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記初期経路のコストに対する増加コストが所定量以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを要旨とする。
【００１０】
請求項５に記載の発明は、請求項４に記載のナビゲーションシステムにおいて、前記合流地点特定手段は、前記増加コストが最小となる前記合流候補地点を合流地点として特定することを要旨とする。
【００１１】
請求項６に記載の発明は、経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出方法において、前記制御手段が、各ユーザの出発地を取得し、前記各出発地からの初期経路をそれぞれ探索するとともに、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断し、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出し、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定することを要旨とする。
【００１２】
請求項７に記載の発明は、経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出プログラムにおいて、前記制御手段を、各ユーザの出発地を取得する取得手段と、前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段として機能させることを要旨とする。
【発明の効果】
【００１３】
請求項１に記載の発明によれば、ナビゲーションシステムは、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１４】
請求項２に記載の発明によれば、初期経路のコストに対する増加コストの割合が、所定率以下である合流候補地点を抽出し、その合流候補地点から合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１５】
請求項３に記載の発明によれば、コスト増加率が最小となる合流候補地点を合流地点として特定する。このため、各ユーザにとって最も合流しやすい合流地点を設定することができる。
【００１６】
請求項４に記載の発明によれば、初期経路のコストに対する増加コストが、所定量以下である合流候補地点を抽出し、抽出した合流候補地点から合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１７】
請求項５に記載の発明によれば、増加コストが最小となる合流候補地点を合流地点として特定する。このため、各ユーザにとって最も合流しやすい合流地点を設定することがで
きる。
【００１８】
請求項６に記載の発明によれば、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００１９】
請求項７に記載の発明によれば、合流地点抽出プログラムに従って、出発地が異なる複数の初期経路に重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する。さらに、当該重複区間を含まない初期経路の出発地に対して、合流候補地点を経由した場合の増加コストを算出し、その増加コストに応じて合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【発明を実施するための最良の形態】
【００２０】
（第１実施形態）
以下、本発明を具体化した一実施形態を図１〜図８に従って説明する。本実施形態では、ナビゲーションシステムを１台の車両に搭載されたナビゲーション装置１に具体化し、該ナビゲーション装置１が、車両３台以上の合流地点を特定する場合について説明する。
【００２１】
図１は、車両に搭載されたナビゲーション装置１の説明図である。ナビゲーション装置１は、合流地点を特定する制御部３を備え、制御部３は、ＣＰＵ１０、ＲＡＭ１１、ＲＯＭ１２、車両側Ｉ／Ｆ１３、通信Ｉ／Ｆ１４、画像プロセッサ１５、入力Ｉ／Ｆ１６を備えている。この制御部３は、取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段を構成する。ＲＯＭ１２又は図示しない記憶部には、合流地点抽出プログラムが格納されている。
【００２２】
ＣＰＵ１０は、車両側Ｉ／Ｆ１３を介して、ＧＰＳ（Global Positioning System）受
信部３０、ジャイロセンサ３１及び車速センサ３２から取得した検出信号に基づき、電波航法及び自律航法によって自車位置を特定する。
【００２３】
通信Ｉ／Ｆ１４は、専用回線又はインターネット等の公衆回線網に接続するためのインターフェースであって、ＣＰＵ１０は、この通信Ｉ／Ｆ１４を介して、各車両に特定した合流地点を通知する。
【００２４】
また、ナビゲーション装置１は、内蔵ハードディスク、又は光ディスク等の外部記憶媒体からなる地理情報記憶部１８及びＰＯＩ（Point Of Interest）情報記憶部１９から、
各種データを読み出す。
【００２５】
地理情報記憶部１８には、目的地までの経路を探索するための各経路ネットワークデータ（以下、経路データ２０という）と、タッチパネルディスプレイ２に地図画面２Ａを出力するための地図描画データ２１とが格納されている。
【００２６】
図２に示すように、経路データ２０は、各メッシュの識別子であるメッシュＩＤ２０Ｉ、リンクＩＤ２０Ａ、接続ノード２０Ｂ、道路種別２０Ｃ、リンクコスト２０Ｄを有している。ノードは、交差点、インターチェンジ、道路の端点等を示すデータ要素であって、リンクは各ノードを接続するデータ要素である。
【００２７】
メッシュＩＤ２０Ｉは、全国を分割した各区域を示し、メッシュＩＤ２０Ｉには、そのメッシュ内に含まれるリンクデータが関連付けられている。リンクデータのリンクＩＤ２
０Ａは、リンクの識別子を示している。接続ノード２０Ｂは、そのリンクに接続したノードの番号等を示す。道路種別２０Ｃは、そのリンクが対応する道路の種別であって、国道、高速道路、一般道等を示す。リンクコスト２０Ｄは、そのリンク自身に割り当てられたコストである。本実施形態では、リンクコスト２０Ｄは、リンク長、道幅、車線数、道路種別等の道路の固有情報に基づくコスト、そのリンクを走行する際にかかる所要時間、渋滞の有無等の時間情報に基づくコストを有している。例えば、リンク長が長い場合、コストは大きく設定され、道幅が大きい場合、コストは小さく設定される。所要時間が長い場合や、渋滞が発生している場合にはコストは大きく設定される。また、リンクコスト２０Ｄは、一つのリンクに対して、「距離優先」、「一般道路優先」等の探索条件や、道路種別に応じて予め設定されたコストをそれぞれ有していてもよい。
【００２８】
また、地図描画データ２１は、全国の地図を分割したメッシュ毎に格納され、道路、市街地、施設等を描画するための背景データ、道路の形状を示す道路データ等を有している。
【００２９】
ＣＰＵ１０は、例えば出発地の座標と目的地の座標とを取得し、経路探索要求を入力すると、複数の探索条件下で、出発地から目的地までのリンクコスト２０Ｄの合計が最小となる推奨経路をそれぞれ探索する。
【００３０】
ＣＰＵ１０は、必要な場合にはリンクコスト２０Ｄに道路種別や渋滞情報等に応じた係数を乗算又は加算し、係数を乗算又は加算したリンクコスト２０Ｄの合計が最小となる経路を探索する。「一般道路優先」の探索条件の下で探索を行う場合には、有料道路のリンクコスト２０Ｄを高く設定して、有料道路を通行しづらくするようにしてもよい。また、探索条件に応じて異なるコスト値がリンクコスト２０Ｄに設定されている場合には、その探索条件に応じたコスト値を用いる。
【００３１】
ＰＯＩ情報記憶部１９には、ＰＯＩデータ２２が記憶されている。図３に示すように、ＰＯＩデータ２２は、エリアコード２２Ａ及びジャンル２２Ｂを管理データとして有している。エリアコード２２Ａは、上記メッシュＩＤでもよいし、都道府県等の行政区分でもよい。ジャンル２２Ｂは、例えば「見る」、「遊ぶ」、「食べる」という目的別の階層と、「ガソリンスタンド」、「ゴルフ場」等の施設種別の階層とを有している。尚、図ではエリアコード２２Ａの下位にジャンル２２Ｂが設定されているが、上位でもよい。
【００３２】
名称２２Ｉは、その施設の名称であって、座標２２Ｊは、その施設の座標を示す。リンクＩＤ２２Ｋは、その施設が属するリンクのＩＤ又はその施設に最も近いリンクのＩＤである。住所２２Ｌは、その施設の住所である。この他にも、ＰＯＩデータ２２は、施設の電話番号、郵便番号等を有している。
【００３３】
また、ナビゲーション装置１の図示しない記憶部には、合流地点として設定可能な施設のジャンル２２Ｂのリスト等が予め記憶されている。或いは、ＰＯＩデータ２２に、その施設が合流地点として設定可能な施設であるか否かを示すフラグを設定してもよい。
【００３４】
次に、本実施形態の処理手順について、図４及び図５に従って説明する。まず、ＣＰＵ１０は、上記合流地点抽出プログラムを用いて、合流モードが指定されたか否かを判断する。タッチパネルディスプレイ２又は操作スイッチ２Ｂ（図１参照）で合流モードを指定する操作が行われると、タッチパネルディスプレイ２のコントローラから合流モード要求が出力される。ＣＰＵ１０は、この合流モード要求を、合流地点の判定処理の開始トリガとする。
【００３５】
ＣＰＵ１０は、合流モード要求を入力すると、各車両の出発地を取得する（ステップＳ
１）。ここでは、ユーザはタッチパネル操作により、各車両の出発地をそれぞれ入力する。ＣＰＵ１０は、タッチパネルコントローラから入力Ｉ／Ｆ１６を介して出発地の位置を取得すると、その位置に対応する座標又はリンクＩＤを取得して、ＲＡＭ１１等に一時記憶する。
【００３６】
次に、ＣＰＵ１０は、目的地を取得する（ステップＳ２）。このときもステップＳ１と同様に、ユーザはタッチパネル操作により目的地の位置を指定し、ＣＰＵ１０は、タッチパネルコントローラから入力Ｉ／Ｆ１６を介して目的地の位置を取得する。尚、目的地は、同一地点でもよいし、異なる地点でもよい。
【００３７】
出発地と目的地とを取得すると、ＣＰＵ１０は、合流地点を特定する（ステップＳ３）。この合流地点の特定処理について、図５に従って説明する。
ＣＰＵ１０は、各車両の出発地と、目的地とを用いて重複区間沿いの合流可能地点の検出処理を行う（ステップＳ３−１）。この処理では、公知の方法を用いることができる。例えば、各車両の出発地毎に、予め決められた探索条件下で、目的地までの経路を単独で探索する。このときの探索条件は特に限定されない。以下、このときの探索により得られた経路を、初期経路という。尚、このとき用いる探索条件は、単数でもよく複数でもよい。
【００３８】
そして、ＣＰＵ１０は、グループを構成する全ての車両５の初期経路が重複する重複区間があるか否かを判断する。例えば、目的地が同一である場合には、初期経路が交差する交差地点があるか否かに基づき、重複区間があるか否かを判断してもよい。図６に示すように、初期経路ＲＰ，ＲＱ上に各経路が交差する交差地点ＰＣがある場合、その交差地点ＰＣから目的地Ｇまでの各経路は重複する。全ての車両５の経路が重複した重複区間が存在する場合には、その重複区間沿いに合流可能な地点があるか否かをＰＯＩデータ２２を用いて検索する。さらに、合流地点として設定可能な施設のリスト又はＰＯＩデータ２２の上記フラグを参照して、その重複区間沿いの施設の中から、合流可能な施設があるか否かを検索する。
【００３９】
次に、ＣＰＵ１０は、ステップＳ３−１の検出結果に基づき、上記重複区間沿いに全員が合流することができる合流可能地点があるか否かを判断する（ステップＳ３−２）。ステップＳ３−１において、全ての車両５の経路が全く重複しない場合、及び一部の車両５の経路のみ重複する場合は、全ての車両の重複区間沿いに合流可能な地点が無いと判断して（ステップＳ３−２においてＮＯ）、ステップＳ３−４に進む。また、全ての車両５の経路が重複する重複区間があるが、合流可能な施設がない場合にもステップＳ３−４に進む。
【００４０】
全ての車両の重複区間沿いに合流可能な地点があると判断すると（ステップＳ３−２においてＹＥＳ）、ＣＰＵ１０は、その候補地点を合流地点として特定する（ステップＳ３−３）。全員が合流可能な候補地点が複数存在する場合には、予め定めた条件で一つの地点を合流地点として特定する。例えば、各車両の目的地が同一である場合、その目的地から最も遠い地点を合流地点として特定する。或いは、各候補地点をタッチパネルディスプレイ２に表示して、ユーザの選択操作により合流地点を特定するようにしてもよい。
【００４１】
一方、全ての初期経路が重複する重複区間が無い場合、及びその重複区間はあっても合流可能な地点が無い場合（ステップＳ３−２においてＮＯ）、２台以上が合流可能な候補地点があるか否かを判断する（ステップＳ３−４）。例えば、図６に示すように、合流予定の３台の車両５Ｐ〜５Ｒのうち、車両５Ｐ，５Ｑの初期経路ＲＰ，ＲＱのみに重複区間が検出され、重複区間沿いに合流可能な候補地点Ｐ１〜Ｐ４が検出されている場合、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステ
ップＳ３−５に進む。
【００４２】
また、図７に示すように、合流予定の４台の車両５Ｐ〜５Ｓのうち、車両５Ｐ及び車両５Ｑのみの重複区間に候補地点Ｐ１〜Ｐ３が検出されている場合、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステップＳ３−５に進む。
【００４３】
さらに、図８に示すように、車両５Ｐ及び車両５Ｑの初期経路ＲＰ，ＲＱの重複区間沿いに候補地点Ｐ１〜Ｐ３があり、車両５Ｒ及び車両５Ｓの経路の重複区間沿いにも異なる候補地点Ｐ４，Ｐ５がある場合にも、２台以上が合流可能な候補地点があると判断して（ステップＳ３−４においてＹＥＳ）、ステップＳ３−５に進む。
【００４４】
また、異なる車両５の経路に重複区間が全くない場合、２台以上が合流可能な候補地点がないと判断して（ステップＳ３−４においてＮＯ）、目的地を合流地点として特定し（ステップＳ３−９）、合流地点の特定処理を終了する。
【００４５】
ステップＳ３−５では、ＣＰＵ１０は、候補地点に合流した場合のコスト増加率を算出する。コスト増加率の算出の対象となる車両５は、その初期経路上に交差地点ＰＣがない車両である。例えば、図６に示すように、車両５Ｒに対して探索された初期経路ＲＲが、他の車両５Ｐ，５Ｑの候補地点Ｐ１〜Ｐ４と重複しない場合、車両５Ｒを対象としてコスト増加率を算出する。
【００４６】
具体的には、ＣＰＵ１０は、車両５Ｒに対して探索された一つの初期経路ＲＲのコストを取得する。このとき、ステップＳ３−１の初期経路の探索の際に用いたコストをそのまま用いてもよいが、必要に応じて、合流地点抽出のためのコスト計算条件で、初期経路ＲＲのコスト合計を算出する。また、渋滞情報、天候情報等の時間の経過とともに変化する情報をデータ要素として加味している場合には、外部から最新の渋滞情報等を取得してもよい。
【００４７】
また、ＣＰＵ１０は、車両５Ｒの出発地Ｓから各候補地点Ｐ１〜Ｐ４を経由して目的地Ｇに到達する候補経路ＲＴ１〜ＲＴ４をそれぞれ探索する。このときの探索条件は初期経路の探索条件と同じ条件である。また、ＣＰＵ１０は、候補経路ＲＴ１〜ＲＴ４のコスト合計をそれぞれ取得する。このコスト合計は、初期経路ＲＲのコスト合計に用いられた上記コスト計算条件で算出された合計値である。
【００４８】
そして、ＣＰＵ１０は、候補経路ＲＴ１〜ＲＴ４のコスト合計から、初期経路ＲＲのコスト合計を減算して、増加コストΔＣを算出する。さらに、増加コストΔＣを、初期経路ＲＲのコスト合計で除算して、コスト増加率（％）を算出する。
【００４９】
例えば、初期経路のコスト合計が「１０００」であって、候補地点Ｐ１を経由する候補経路ＲＴ１のコスト合計が「１５００」である場合、増加コストΔＣは「５００」であって、コスト増加率は「５０％」である。また、候補地点Ｐ２を経由する候補経路ＲＴ２のコスト合計が「１２１０」である場合、コスト増加率は「２１％」である。また、候補地点Ｐ３を経由する候補経路ＲＴ３のコスト合計が「１２００」である場合、コスト増加率は「２０％」である。さらに、候補地点Ｐ４を経由する候補経路ＲＴ４のコスト合計が「１１００」である場合、コスト増加率は「１０％」である。
【００５０】
次に、ＣＰＵ１０は、コスト増加率が所定率（Ｘ％）以下の候補地点があるか否かを判断する（ステップＳ３−６）。本実施形態では、所定率は２０％に設定されている。候補経路ＲＴ１〜ＲＴ４のうち、コスト増加率がＸ％以下である経路は、候補経路ＲＴ３及び
候補経路ＲＴ４であるため、ステップＳ３−６においてコスト増加率がＸ％以下の候補地点があると判断して（ステップＳ３−６においてＹＥＳ）、該当する候補地点を抽出し、ＲＡＭ１１等に一時記憶する（ステップＳ３−７）。
【００５１】
さらに、ＣＰＵ１０は、一時記憶された候補地点の中から、合流地点を特定する（ステップＳ３−８）。候補地点が一つしか抽出されていない場合には、その候補地点を合流地点として特定する。抽出した候補地点が複数である場合、ＣＰＵ１０は、各車両５のコスト増加率の平均が最も小さい候補地点を合流地点とする。１台の車両５に対してコスト増加率を算出している場合には、コスト増加率が最小となる候補地点を合流地点とする。例えば、ステップＳ３−７において、候補地点Ｐ３，Ｐ４が一時記憶されている場合、候補地点Ｐ３，Ｐ４をそれぞれ経由する候補経路ＲＴ３，ＲＴ４のコスト増加率を比較する。候補経路ＲＴ３のコスト増加率は「２０％」であり、候補経路ＲＴ４のコスト増加率は「１０％」であるため、ＣＰＵ１０は、候補経路ＲＴ４の候補地点Ｐ４を合流地点として特定する。合流地点を特定すると、合流地点の特定処理を終了し、図４に示すステップＳ５に進む。
【００５２】
尚、ここでは３台が同じ目的地に対して合流する場合について説明したが、４台以上が同じ目的地に対して合流する場合も、上記した手順と同様に合流地点を特定する。図７に示すように２台の車両５Ｒ，５Ｓの初期経路ＲＲ，ＲＳ上に重複区間がなく、他２台の車両５Ｐ，５Ｑの初期経路ＲＰ，ＲＱ上に候補地点Ｐ１〜Ｐ３がある場合、車両５Ｒ，５Ｓが候補地点Ｐ１〜Ｐ３を経由した候補経路ＲＴ１〜ＲＴ６をそれぞれ探索する。さらに、候補経路ＲＴ１〜ＲＴ６のコスト増加率を算出する。そして、車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以内となる候補地点がある場合には、候補地点を抽出し、抽出した候補地点の一つを合流地点とする。車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以内となる候補地点がない場合には、目的地を合流地点とする。
【００５３】
また、図８に示すように、全ての車両５Ｐ〜５Ｓの経路が重複する区間はないものの、車両５Ｐ，５Ｑの候補地点Ｐ１〜Ｐ３と、車両５Ｒ，５Ｓの候補地点Ｐ４，Ｐ５がそれぞれ存在する場合がある。この場合、候補地点Ｐ１〜Ｐ３を経由する場合の車両５Ｒ，５Ｓのコスト増加率を算出するとともに、候補地点Ｐ４，Ｐ５を経由する場合の車両５Ｐ，５Ｑのコスト増加率を算出する。そして、車両５Ｒ，５Ｓ両方のコスト増加率がＸ％以下となる候補地点、車両５Ｐ，５Ｑ両方のコスト増加率がＸ％以下となる候補地点を抽出し、抽出した候補地点の中から、上記したように合流地点を特定する。
【００５４】
合流地点を特定すると、図４に示すように、ＣＰＵ１０は、合流地点を経由する経路を各出発地毎に探索し、探索した経路の経路案内を行う（ステップＳ４）。このとき、ＣＰＵ１０は、通信Ｉ／Ｆ１４を介して、同じ目的地に向かう車両５のナビゲーション装置、或いはユーザが所持する携帯端末に、合流地点の座標をそれぞれ送信してもよい。他のユーザの各端末は、選択された合流地点の座標を取得し、その合流地点までの経路を端末のディスプレイ等に表示する。
【００５５】
第１実施形態によれば、以下のような効果を得ることができる。
（１）第１実施形態では、ナビゲーション装置１は、各車両５の出発地を取得して、出発地からの初期経路を経路データ２０を用いてそれぞれ探索し、出発地が異なる複数の初期経路の交差地点を検索することにより、重複区間の有無を判断する。重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、交差地点が初期経路上にない、即ち重複区間を含まない初期経路の車両５の出発地に対して、該候補地点を経由した候補経路を探索する。さらに、候補経路の初期経路に対する増加コストΔＣを経路データ２０を用いて算出し、増加コストΔＣの大きさに応じて候補地点を合流地点として特定する。このため、例えば全ての車両５の初期経路が重複する区間が無い場合にも、全ての車両５に
とって、合流のために長距離又は長時間走行する必要が無い、合流しやすい合流地点を設定することができる。
【００５６】
（２）第１実施形態では、ナビゲーション装置１は、初期経路のコストに対する候補経路のコスト増加率を算出し、算出したコスト増加率がＸ％以下となる候補地点の中から、合流地点を特定する。このため、各ユーザにとって合流しやすい合流地点を設定することができる。
【００５７】
（３）第１実施形態では、コスト増加率がＸ％以下となる候補地点が複数存在する場合に、コスト増加率が最小となる候補地点を合流地点として特定する。このため、全ての車両５にとって最も合流しやすい合流地点を設定することができる。
【００５８】
（第２実施形態）
次に、本発明を具体化した第２実施形態を図９〜図１０に従って説明する。尚、第２実施形態は、第１実施形態のシステム構成を変更しており、同様の部分についてはその詳細な説明を省略する。
【００５９】
本実施形態では、ナビゲーションシステムを、図９に示す経路案内サーバ５１に具体化している。経路案内サーバ５１は、専用線又はインターネット等の公衆回線網からなるネットワークＮと、基地局５２と介して、車両５に搭載されたナビゲーション装置１及びユーザ端末５３と接続されている。ナビゲーション装置１は、第１実施形態と同じ構成とする。ユーザ端末５３は、図９では携帯電話としたが、パーソナルコンピュータ、その他の端末に具体化してもよい。
【００６０】
図１０は、経路案内サーバ５１のハードウェア構成を示すブロック図である。経路案内サーバ５１は、ＣＰＵ５５、ＲＡＭ５６、ＲＯＭ５７、通信Ｉ／Ｆ５８からなる制御コンピュータ５４と、地理情報記憶部５９、ユーザ情報記憶部６０とを備えている。制御コンピュータ５４は、取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段を構成する。制御コンピュータ５４には、合流地点抽出プログラムが格納されている。
【００６１】
地理情報記憶部５９には、経路データ２０が格納されている。このデータは、上記したナビゲーション装置１に格納された経路データ２０と同じ構成となっている。
また、ユーザ情報記憶部６０には、ユーザデータ６１が格納されている。ユーザデータ６１は、予め登録されたユーザに関するデータであって、各ユーザが所持するナビゲーション装置１又はユーザ端末５３の固有アドレス、ユーザＩＤ、パスワード等が格納されている。経路案内サーバ５１は、ナビゲーション装置１又はユーザ端末５３からログイン要求を受け付けた際に、このユーザデータ６１を用いてユーザ認証を行う。
【００６２】
本実施形態の処理手順について、図４に従って説明する。経路案内サーバ５１は、ナビゲーション装置１又はユーザ端末５３から、全ての車両５の出発地を取得するとともに（ステップＳ１）、目的地を取得する（ステップＳ２）。尚、目的地は、代表ユーザのみから取得するようにしてもよい。また、目的地に向かう車両の台数を、代表ユーザのナビゲーション装置１又はユーザ端末５３から取得する。
【００６３】
目的地、及び全ての車両５の出発地の収集が完了すると、ＣＰＵ５５は、上記した手順で合流地点の特定処理を行う（ステップＳ３）。合流地点を特定すると、ＣＰＵ５５は、その合流地点を経由した経路を各出発地毎に探索し、ナビゲーション装置１又はユーザ端末５３に対して経路案内を行う（ステップＳ４）。このとき、ＣＰＵ５５は、通信Ｉ／Ｆ５８を介して、ユーザ情報記憶部６０に登録されたナビゲーション装置１又はユーザ端末
５３に、特定した合流地点の座標と、探索した経路を示す経路データとをそれぞれ送信する。ナビゲーション装置１又はユーザ端末５３は、受信した合流地点の座標及び経路データを用いて、合流地点の位置と目的地までの経路をディスプレイにそれぞれ表示する。
【００６４】
第２実施形態によれば、以下のような効果を得ることができる。
（４）第２実施形態では、経路案内サーバ５１が、出発地及び目的地を取得し、各ユーザの合流地点を特定する。このため、ナビゲーション装置１やユーザ端末５３の処理を軽減することができる。また、ユーザ端末５３は、経路データ２０を格納していなくても、自車位置を経路案内サーバ５１に送信するのみで、合流地点を取得することができる。
【００６５】
（第３実施形態）
次に、本発明を具体化した第３実施形態を図１１に従って説明する。尚、第３実施形態は、第１実施形態の経路データの構成を変更したのみの構成であり、同様の部分についてはその詳細な説明を省略する。
【００６６】
本実施形態では、リンクコスト２０Ｄには、料金データ７０が含まれている。料金データ７０は、有料道路を通過する際や、フェリーを使用する際の料金を示すデータであって、例えば高速道路のＩＣ間の料金を示している。尚、料金データ７０の構成は、図１１に示す構成に限定されず、他の構成でもよい。
【００６７】
ステップＳ３では、ナビゲーション装置１は、候補地点に合流した際のコスト増加率を、この料金データ７０を用いて算出する。この場合、増加コストΔＣは、料金である。この増加コストΔＣには、初期経路に対する候補経路の走行距離の増加分に基づく燃料費を含めてもよい。コスト増加率は、増加コストΔＣを初期経路を走行する際にかかる料金で除算して算出する。そして、コスト増加率が、Ｘ％以下となる候補地点を抽出し、それらの候補地点から合流地点を特定する。
【００６８】
第３実施形態によれば、以下のような効果を得ることができる。
（５）第３実施形態では、コスト増加率を算出する際に、料金データ７０を用いる。このため、全ての車両５の初期経路が重複する区間が無い場合にも、全ての車両５にとって、料金が過度に高くならない、合流しやすい合流地点を設定することができる。
【００６９】
尚、上記各実施形態は以下のように変更してもよい。
・上記各実施形態では、初期経路に対する候補経路のコスト増加率を算出し、そのコスト増加率がＸ％以下の候補地点を抽出したが、初期経路に対する候補経路の増加コストΔＣが所定量以下の候補地点を抽出するようにしてもよい。
【００７０】
・上記実施形態では、３台以上の車両５が目的地に向かう際の合流地点の特定について説明したが、３人以上のユーザが徒歩や電車等の車両以外の交通手段によって目的地に向かう場合に合流地点を特定しても良い。この場合、ユーザのうち少なくともひとりが、経路案内サーバ５１に接続可能なユーザ端末５３を所持するものとする。
【図面の簡単な説明】
【００７１】
【図１】ナビゲーション装置のハードウェア構成を示すブロック図。
【図２】経路データのデータ構成を示す概念図。
【図３】ＰＯＩデータのデータ構成を示す概念図。
【図４】全体の処理手順を示すフローチャート。
【図５】合流地点の特定の処理手順を示すフローチャート。
【図６】３台の車両に対する合流地点の特定の手順を示す概念図。
【図７】４台の車両に対する合流地点の特定の手順を示す概念図。
【図８】４台の車両に対する合流地点の特定の手順を示す概念図。
【図９】第２実施形態の経路案内システムのネットワーク図。
【図１０】経路案内サーバのハードウェア構成を示すブロック図。
【図１１】料金データのデータ構成を示す概念図。
【符号の説明】
【００７２】
１…ナビゲーションシステムを構成するナビゲーション装置、３…取得手段、経路探索手段、重複判断手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段としての制御部、５１…ナビゲーションシステムとしての経路案内サーバ、５４…出発地取得手段、経路探索手段、初期経路手段、候補地点設定手段、コスト算出手段、合流地点特定手段、制御手段としての制御コンピュータ、Ｇ…目的地、ＲＴ１〜ＲＴ６…候補経路、ＲＰ〜ＲＳ…初期経路、Ｐ１〜Ｐ４…合流候補地点としての候補地点、ＰＣ…交差地点、Ｓ…出発地、ΔＣ…増加コスト。
【特許請求の範囲】
【請求項１】
各ユーザの出発地を取得する取得手段と、
前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、
前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、
前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、
前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、
前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段と
を備えたことを特徴とするナビゲーションシステム。
【請求項２】
請求項１に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記初期経路のコストに対する増加コストの割合であるコスト増加率を算出し、算出した割合が所定率以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを特徴とするナビゲーションシステム。
【請求項３】
請求項２に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記コスト増加率が最小となる前記合流候補地点を合流地点として特定することを特徴とするナビゲーションシステム。
【請求項４】
請求項１に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記初期経路のコストに対する増加コストが所定量以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを特徴とするナビゲーションシステム。
【請求項５】
請求項４に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記増加コストが最小となる前記合流候補地点を合流地点として特定することを特徴とするナビゲーションシステム。
【請求項６】
経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出方法において、
前記制御手段が、
各ユーザの出発地を取得し、前記各出発地からの初期経路をそれぞれ探索するとともに、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断し、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出し、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定することを特徴とする合流地点抽出方法。
【請求項７】
経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出プログラムにおいて、
前記制御手段を、
各ユーザの出発地を取得する取得手段と、
前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、
前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、
前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、
前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、
前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段として機能させることを特徴とする合流地点抽出プログラム。
【請求項１】
各ユーザの出発地を取得する取得手段と、
前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、
前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、
前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、
前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、
前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段と
を備えたことを特徴とするナビゲーションシステム。
【請求項２】
請求項１に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記初期経路のコストに対する増加コストの割合であるコスト増加率を算出し、算出した割合が所定率以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを特徴とするナビゲーションシステム。
【請求項３】
請求項２に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記コスト増加率が最小となる前記合流候補地点を合流地点として特定することを特徴とするナビゲーションシステム。
【請求項４】
請求項１に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記初期経路のコストに対する増加コストが所定量以下である前記合流候補地点を抽出し、抽出した前記合流候補地点から前記合流地点を特定することを特徴とするナビゲーションシステム。
【請求項５】
請求項４に記載のナビゲーションシステムにおいて、
前記合流地点特定手段は、
前記増加コストが最小となる前記合流候補地点を合流地点として特定することを特徴とするナビゲーションシステム。
【請求項６】
経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出方法において、
前記制御手段が、
各ユーザの出発地を取得し、前記各出発地からの初期経路をそれぞれ探索するとともに、前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断し、前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定し、前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出し、前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定することを特徴とする合流地点抽出方法。
【請求項７】
経路を探索する制御手段を用いて、各ユーザの合流地点を特定する合流地点抽出プログラムにおいて、
前記制御手段を、
各ユーザの出発地を取得する取得手段と、
前記各出発地からの初期経路をそれぞれ探索する経路探索手段と、
前記出発地が異なる複数の前記初期経路の重複区間があるか否かを判断する重複判断手段と、
前記重複区間が存在する場合に、当該重複区間沿いに合流候補地点を設定する候補地点設定手段と、
前記重複区間を含まない前記初期経路の出発地に対して、前記合流候補地点を経由する候補経路を探索し、当該候補経路の前記初期経路に対する増加コストを算出するコスト算出手段と、
前記増加コストの大きさに応じて前記合流候補地点を前記各ユーザの合流地点として特定する合流地点特定手段として機能させることを特徴とする合流地点抽出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００９−２０４４１６（Ｐ２００９−２０４４１６Ａ）
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願番号】特願２００８−４６３０２（Ｐ２００８−４６３０２）
【出願日】平成２０年２月２７日（２００８．２．２７）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願日】平成２０年２月２７日（２００８．２．２７）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]