【事件の表示】
　特許第３０２７８９９号「推奨経路案内装置」の請求項１ないし８に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結　論】
　訂正を認める。
　特許第３０２７８９９号の請求項１ないし８に係る特許を維持する。
【理　由】
１．手続の経緯
　特許第３０２７８９９号の請求項１ないし８に係る発明は、平成５年５月１２日に特許出願され、平成１２年２月４日にその特許権の設定登録がなされ、その後、大西蓉子により特許異議の申立てがなされ、取消しの理由が通知され、その指定期間内である平成１３年５月１日に訂正請求がなされたものである。
２．訂正の適否についての判断
（１）訂正の内容
１．訂正事項ａ
　特許請求の範囲の請求項１における「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段と、」とあるのを、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、」と訂正する。
２．訂正事項ｂ
　特許明細書の段落番号【０００８】を、
「【課題を解決するための手段】
　上記の問題を解決するために本発明は、第１の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段とを備えたことを特徴とする。」と訂正する。
３．訂正事項ｃ
　特許明細書の段落番号【００４８】を、
「【００４８】
　　第３の実施例における地点設定処理と第１および第２の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第１および第２の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第３の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図１２のフローチャートを用いて詳細に説明する。図１２のステップ１２０１においてユーザーは出発地（目的地）の位置を例えばＣＲＴに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ１２０２ では、設定した出発地の座標を中心に半径limit_distの円の範囲（図２の点線の円：例えば５０ｍの範囲）の地図情報を読み込むが、この場合は簡単のため１枚の地図内としている。ステップ１２０３ では、各リンク（Ｌ１〜Ｌ１２）への距離（各差分データ成分への一番近い距離）を図１１（ｂ）の経度・緯度情報および図１１（ｃ）のリンク形状差分データとステップ１２０１で得た出発地（目的地）の位置情報から順次算出し、距離の小さい順にＮ本（例えば２本）を選択して垂線とリンクの交点の位置および距離を記録する。図１１（ａ）のような場合、出発地側ではリンクＬ１上の点Ｐ１の位置座標と距離ＤＰ１、およびリンクＬ３上の点Ｐ２の位置座標と距離ＤＰ２が記録され、目的地側ではリンクＬ８上の点Ｐ３の位置座標と距離ＤＰ３、およびリンクＬ１１上の点Ｐ４の位置座標と距離 ＤＰ４が記録される。次にスデップ１２０４ にて出発地側かどうか判定される。出発地側であればステップ１２０５ に進み、選択されたリンクＬ１上の点Ｐ１から一方通行規制に従って到達できるノードＮ１、Ｎ３および選択されたリンクＬ３上の点Ｐ２から一方通行規制に従って到達できるノードＮ３ を探索開始点とする。ノードＮ１には交点Ｐ１からノードＮ１までの距離を、ノードＮ３には交点Ｐ１からノードＮ３までの距離または交点Ｐ２からノードＮ３までの距離の短い方を記憶する。さらにステップ１２０６において選択したノードＮ１、Ｎ３に探索開始点フラグをたてる。ステップ１２０４ において目的地側であればステップ１２０８に進み、選択されたリンクＬ８上の点Ｐ３に一方通行規制に従って進入できるノードＮ７および選択されたリンクＬ１１上の点Ｐ４に一方通行規制に従って進入できるノードＮ１１を探索開始点とする。ノードＮ７ には交点 Ｐ３ からノードＮ７までの距離を、ノードＮ１１には交点Ｐ４からノードＮ１１までの距離を記録する。さらにステップ１２０９ において選択したノードＮ７、Ｎ１１に探索終了点フラグをたてる。最後にステップ１２０７ において、探索開始点（ノードＮ１、Ｎ３）および探索終了点（ノードＮ７、Ｎ１１）に初期コストとして一定値（例えば０）を付与する。以上で地点設定処理を終了する。」と訂正する。
（２）訂正の目的の適否、新規事項の有無及び拡張・変更の存否
　　上記訂正事項ａは、発明を特定する事項である「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段」を、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段」という発明特定事項に減縮するものであり、しかも、これについては願書に添付された明細書の段落【００２３】〜【００２９】に記載されているから、特許請求の範囲の減縮を目的とした明細書の訂正に該当する。
　　上記訂正事項ｂは、訂正事項ａとの整合をとるための訂正であり、明りょうでない記載の釈明に該当する。
　　上記訂正事項ｃは、訂正前の「図１２（ａ）」という記載は明らかに「図１１（ａ）」の誤記であるので、誤記の訂正に該当する。
（３）むすび
　　したがって、上記訂正は、特許法の一部を改正する法律（平成６年法律第１１６号）附則第６条第１項の規定によりなお従前の例によるとされる、特許法第１２０条の４第３項で準用する平成６年法律第１１６号による改正前の特許法第１２６条第１項ただし書き及び第２項の規定に適合するので、当該訂正を認める。
３．特許異議の申立てについての判断
（１）申立ての理由の概要
　　申立人大西蓉子は、証拠として甲第１号証（特開平４−３５９１１２号公報）、甲第２号証（特開平４−３２８７８９号公報）、甲第３号証（特開昭６２−８２３１６号公報）、甲第４号証（特開昭６２−２７６６９７号公報）、甲第５号証（特開平４−３７２９８５号公報）、甲第６号証（特開平４−３１９９８６号公報）を提出し、請求項１ないし８に係る発明は、特許法第２９条第２項の規定に違反してなされたものであるから、取り消すべき旨主張している。
（２）本件の請求項１に係る発明
　　上記２．で示したように上記訂正が認められるから、本件の請求項１に係る発明（「本件発明」という。）は、上記訂正請求に係る訂正明細書の特許請求の範囲の請求項１に記載された事項により特定される、以下のとおりのものと認める。
「交差点および道路の位置および接続関係を記録した道路ネットワーク記録手段と、出発地と目的地を設定する地点設定手段と、前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、前記探索手段で得られた経路を出力する出力手段とを備えたことを特徴とする推奨経路案内装置。」
（３）刊行物等
　　特許異議申立人が証拠として提出した刊行物には、以下のように記載されている。
１．甲第１号証
　　「車両を出発地点から目的地点まで案内するために出発地点から目的地点までの経路を設定する車両用経路案内装置であって、各交差点の位置情報、各交差点の隣接交差点までの区間道程、各交差点および各道路に関する属性情報を含む交差点情報を記憶する交差点情報記憶手段と、該交差点情報記憶手段に記憶された交差点情報に基づいて前記出発地点および目的地点からそれぞれ所定範囲内の交差点を候補交差点として選択し、この選択された交差点の中から所定のパラメータに基づいて出発交差点および最終交差点を設定する経路端交差点設定手段と、該経路端交差点設定手段で設定された出発交差点および最終交差点との間の最適誘導経路を前記交差点情報記憶手段に記憶された交差点情報にに基づいて設定する誘導経路設定手段とを有することを特徴とする車両用経路案内装置。」（特許請求の範囲）
　　「【００２６】なお、出発地点および目的地点は、通常はこのように交差点に設定されていない場合が多く、交差点と交差点との間のリンク、すなわち道路上であったり、またはリンク上でない例えば自車の駐車場であったりする。」（公報第６欄）
　　「【００２８】ここで、出発候補交差点の中から最も適した交差点を出発交差点として選定する場合と、最終候補交差点の中から最も適した交差点を最終交差点として選定する場合とはほぼ同じ考えで選定するので、以下、出発候補交差点の中から出発交差点を選定する場合で説明する。抽出した出発候補交差点の中から最も適した交差点を出発交差点として選定する場合、この問題を単純な２次平面上の問題として捕らえる場合には、出発地点から最も近い交差点を出発交差点として選定すればよいことになるけれども、現実には最も近い交差点が出発交差点に適さない場合も多々ある。」（公報第６欄）
　　「【００３０】従って、本実施例では、出発地点から所定距離範囲内にある交差点を出発候補交差点として抽出し（ステップ２２０）、この抽出した交差点をそれぞれ後述する１つ以上のパラメータによって重み付けを行い、この重みによって最適な交差点をひとつ選定しようとするものである。」（公報第６欄）
　　「【００４７】そして、このように計算された重み合計値Ｋｎが最も大きいものを選択することにより出発交差点が選定され、処理を終了する（ステップ２６０）。」（公報第７，８欄）
２．甲第２ないし４号証
　　甲第２号証ないし第４号証には、出発地から目的地までの経路を探索する際に、一方通行や通行禁止等の通行規制のある道路・交差点を考慮することにより、到達不可能な経路を探索しないことについて記載されている。
３．甲第５及び６号証
　　甲第５及び６号証には、出発地や目的地が道路上にない場合において、出発地や目的地から道路に垂線をを下ろして最も近い点を求め、この交点からリンク両端までの距離を算出して経路探索のコスト（重み）として用いることが記載されている。
（４）対比・判断
　　本件発明と、甲各号証に記載された発明とを対比すると、本件発明の　　「前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段」については、いずれの号証にも記載がなく、また、これを示唆する記載もない。
　　本件発明は、上記手段を備えることにより、探索開始点または探索終了点をひとつに限定することなく出発地から目的地までの最適な経路を探索することができるものであり、
「このように本発明の第１の手段によると地点設定した位置近傍の複数の地点に固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた探索開始点または探索終了点を設定することによって、新たな入力作業を伴うことなく、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、行き過ぎ等の不適切な経路を選出することを防ぐことができる。」という、明細書記載の格別の効果を奏するものと認められる。
（５）申立人の主張について
　　申立人は、本件発明の上記手段に関し、異議申立書において本件発明の 構成Ｃと分説し、甲第１号証の第４頁右欄第７行〜第５頁第４２行の記載を引用の上、甲第１号証にはＣ要件における「地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段」について記載されていると主張しているが、探索開始点または探索終了点を複数個設定することに関しては、前述のとおり、いずれの証拠にも記載がないから、各号証記載のものをいかに組み合わせても本件発明の構成を得ることはできず、申立人の主張は採用できない。
（６）むすび
　　以上のとおりであるから、特許異議の申立ての理由及び証拠によっては、本件請求項１ないし８に係る特許を取り消すことができない。また、他に本件請求項１ないし８に係る特許を取り消すべき理由を発見しない。
　　よって、結論のとおり決定する。
【異議決定日】
平成１４年９月３日（２００２．９．３）
【訂正の要旨】
訂正の内容
１．訂正事項ａ
　特許請求の範囲の請求項１における「前記探索開始終了点設定手段で設定した探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索する探索手段と、」とあるのを、「前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と、」と訂正する。
２．訂正事項ｂ
　特許明細書の段落番号【０００８】を、
「【課題を解決するための手段】
　上記の問題を解決するために本発明は、第１の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段とを備えたことを特徴とする。」と訂正する。
３．訂正事項ｃ
　特許明細書の段落番号【００４８】を、
「【００４８】
　第３の実施例における地点設定処理と第１および第２の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第１および第２の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第３の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図１２のフローチャートを用いて詳細に説明する。図１２のステップ１２０１においてユーザーは出発地（目的地）の位置を例えばＣＲＴに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ１２０２では、設定した出発地の座標を中心に半径ｌｉｍｉｔ＿ｄｉｓｔの円の範囲（図２の点線の円：例えば５０ｍの範囲）の地図情報を読み込むが、この場合は簡単のため１枚の地図内としている。ステップ１２０３では、各リンク（Ｌ１〜Ｌ１２）への距離（各差分データ成分への一番近い距離）を図１１（ｂ）の経度・緯度情報および図１１（ｃ）のリンク形状差分データとステップ１２０１で得た出発地（目的地）の位置情報から順次算出し、距離の小さい順にＮ本（例えば２本）を選択して垂線とリンクの交点の位置および距離を記録する。図１１（ａ）のような場合、出発地側ではリンクＬ１上の点Ｐ１の位置座標と距離ＤＰ１、およびリンクＬ３上の点Ｐ２の位置座標と距離ＤＰ２が記録され、目的地側ではリンクＬ８上の点Ｐ３の位置座標と距離ＤＰ３、およびリンクＬ１１上の点Ｐ４の位置座標と距離ＤＰ４が記録される。次にスデップ１２０４にて出発地側かどうか判定される。出発地側であればステップ１２０５に進み、選択されたリンクＬ１上の点Ｐ１から一方通行規制に従って到達できるノードＮ１、Ｎ３および選択されたリンクＬ３上の点Ｐ２から一方通行規制に従って到達できるノードＮ３を探索開始点とする。ノードＮ１には交点Ｐ１からノードＮ１までの距離を、ノードＮ３には交点Ｐ１からノードＮ３までの距離または交点Ｐ２からノードＮ３までの距離の短い方を記憶する。さらにステップ１２０６において選択したノードＮ１、Ｎ３に探索開始点フラグをたてる。ステップ１２０４において目的地側であればステップ１２０８に進み、選択されたリンクＬ８上の点Ｐ３に一方通行規制に従って進入できるノードＮ７および選択されたリンクＬ１１上の点Ｐ４に一方通行規制に従って進入できるノードＮ１１を探索開始点とする。ノードＮ７には交点Ｐ３からノードＮ７までの距離を、ノードＮ１１には交点Ｐ４からノードＮ１１までの距離を記録する。さらにステップ１２０９において選択したノードＮ７、Ｎ１１に探索終了点フラグをたてる。最後にステップ１２０７において、探索開始点（ノードＮ１、Ｎ３）および探索終了点（ノードＮ７、Ｎ１１）に初期コストとして一定値（例えば０）を付与する。以上で地点設定処理を終了する。」と訂正する。
（５４）【発明の名称】
推奨経路案内装置
（５７）【特許請求の範囲】
　【請求項１】交差点および道路の位置および接続関係を記録した道路ネットワーク記録手段と、出発地と目的地を設定する地点設定手段と、前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段と、前記探索開始終了点設定手段で
初期コストが与えられた各
加算コストが与えられた各
、前記出発地から前記目的地まで最小コストで到達できる経路を求める
　【請求項２】探索開始終了点設定手段は、選択された各交差点と出発地または目的地との距離に関する関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項１記載の推奨経路案内装置。
　【請求項３】探索開始終了点設定手段は、出発地と目的地の位置情報から近傍の道路リンクを各々１本以上選出し、そのリンクの両端の交差点を選択することを特徴とする請求項１記載の推奨経路案内装置。
　【請求項４】探索開始終了点設定手段は、各道路リンクの両端の交差点のうち通行規制を遵守して到達可能な交差点のみを選択することを特徴とする請求項３記載の推奨経路案内装置。
　【請求項５】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点とその点までの距離を求め、この距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項４記載の推奨経路案内装置。
　【請求項６】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点を求め、その点から道路リンクの両端の交差点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項４記載の推奨経路案内装置。
　【請求項７】探索開始終了点設定手段は、出発地または目的地から各道路リンク上の最も近い点とその点までの距離を求め、この距離の関数で与えられるコストとその点から道路リンクの両端の交差点までの距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項４記載の推奨経路案内装置。
　【請求項８】探索開始終了点設定手段は、出発地および目的地から各探索開始点および探索終了点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることを特徴とする請求項４記載の推奨経路案内装置。
　【請求項９】探索開始終了点設定手段は、車両の位置と向きから出発地側の探索開始点または出発地側の探索終了点を決定することを特徴とする請求項４記載の推奨経路案内装置。
　【請求項１０】探索開始終了点設定手段は、車両の向きと道路リンクのなす角度によるペナルティコストを出発地側の探索開始時の初期コストまたは出発地側の探索終了点到達時の加算コストに加えることを特徴とする請求項４記載の推奨経路案内装置。
　【請求項１１】探索開始終了点設定手段は、目的地と道路リンクの位置関係により右左折のペナルティコストを目的地側の探索開始時の初期コストまたは目的地側の探索終了点到達時の加算コストに加えることを特徴とする請求項４記載の推奨経路案内装置。
【発明の詳細な説明】
　【０００１】
　【産業上の利用分野】
　本発明は、車両がある地点から別の地点へ効率的に移動するために、その地点までの経路を自動的に選定して案内をする推奨経路案内装置に関する。
　【０００２】
　【従来の技術】
　従来の経路探索装置の地点設定手段としては、例えばユーザーが設定した地点に一番距離的に近い主要交差点を出発地または目的地としたり、特公平５ー６２３８で開示されているように複数の候補交差点の中からユーザーに選択させる方法があった。
　【０００３】
　【発明が解決しようとする課題】
　しかしながら、探索開始点および探索終了点を単純に出発地あるいは目的地に距離的に一番近い交差点に設定すると、ユーザーの意図しない地点から（あるいはユーザーの意図しない地点まで）経路を導出する可能性がある。ここで、その例を示す。図１５（ａ）は従来の地点設定法では希望する経路が求められない場合の道路網の例（目的地側）を示す図、図１５（ｂ）は従来の地点設定法を用いて求めた選択経路の例を示す図である。図１５（ａ）において、出発地はＰ（Ｓ）の方向にあり、ユーザーは網掛けの地点に行きたくて地点Ｐ（Ｕ）に目的地設定したとする。また、このとき地点Ｐ（Ｕ）から交差点Ｎ０、Ｎ１、Ｎ２への距離はそれぞれ次の関係があるとする。
　【０００４】
　　Ｐ（Ｕ）・Ｎ０間の距離　＜　Ｐ（Ｕ）・Ｎ２間の距離　＜　Ｐ（Ｕ）・Ｎ１間の距離
　これらの条件において、探索終了点を地点Ｐ（Ｕ）に一番近い交差点とすると、交差点Ｎ０が探索終了点として選択され図１５（ｂ）の点線で示したような経路が選出される。このように目的地の前を通り過ぎて裏に誘導してしまうような経路を選出する可能性がある。また、地点設定とは別に複数の候補交差点から一つの交差点をユーザーに選択させることは、ユーザーが必ずしも入力地点付近の状況に詳しいとは限らないし、実際の入力手順として非常に煩わしいものとなる。そこで、新たな入力作業を伴うことなく、行き過ぎ等の不適切な経路を選出しないことを第１の目的とする。
　【０００５】
　また、第１の目的を満たした上で、地点設定した位置に近い交差点が選択されることを第２の目的とする。
　【０００６】
　また、ユーザーが設定した位置の近傍の道路上から離れた交差点に探索開始点または探索終了点が設定されることを防ぐことを第３の目的とする。
　【０００７】
　また、第３の目的を満たした上で、目的地に到達するために最も効率的な方向へ誘導する経路を選出することを第４の目的とする。
　【０００８】
　【課題を解決するための手段】
　上記の問題を解決するために本発明は、第１の手段として前記地点設定手段で設定した出発地または目的地の情報から複数個の探索開始点または探索終了点を設定し、それぞれに固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与える探索開始終了点設定手段
と、前記探索開始終了点設定手段で初期コストが与えられた各探索開始点から、加算コストが与えられた各探索終了点までの経路を前記道路ネットワーク記録手段の情報から探索し、前記出発地から前記目的地まで最小コストで到達できる経路を求める探索手段と
　【０００９】
　また、第２の手段は前記地点設定手段において設定された出発地または目的地から前記探索開始終了点設定手段において設定された探索開始点または探索終了点までの距離の関数で探索開始時の初期コストまたは探索終了点到達時の加算コストを設定する処理を第１の手段における探索開始終了点設定手段に加えたことを特徴とする。
　【００１０】
　また、第３の手段は前記地点設定手段で設定された出発地・目的地の位置情報から１本以上の道路を選択し、その両端の交差点のうち交通規制情報に従って到達できる交差点を選択する前記探索開始終了点設定手段を備えたことを特徴とする。
　【００１１】
　また、第４の手段は前記地点設定手段であげられた出発地または目的地から各道路上の最も近い点を求め、出発地または目的地から最も近い点までの距離の関数で与えられるコストとその点から道路の両端の交差点に対する距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与える処理を第３の手段における前記探索開始終了点設定手段に加えたことを特徴とする。
　【００１２】
　【作用】
　本発明は、第１の手段によると、探索開始終了点設定手段において地点設定手段で設定した出発地または目的地の情報から、固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた複数個の探索開始点または探索終了点を設定して、出発地近傍の目的地方向側に探索開始点を、目的地近傍の出発地方向に探索終了点を作成することにより、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、出発地後方を経路の開始点にしたり目的地を行き過ぎるような経路を選出することを防ぐことができる。
　【００１３】
　また第２の手段によると、第１の手段により実現された機能を満たした上で、出発地または目的地からの距離の関数で探索開始時の初期コストおよび探索終了点到達時の加算コストを与えることにより、遠く離れた探索開始点および探索終了点は大きなコストを持つことになるので、経路の開始点または終了点がそれぞれ出発地または目的地の位置から遠く離れることを防ぐことができる。
　【００１４】
　また第３の手段によると、探索開始終了点設定手段において地点設定手段で入力された出発地または目的地の位置情報から近傍の１本以上の道路を選出し、その両端の交差点のうち交通規制情報に従って到達できる全ての交差点を探索開始点または探索終了点に設定することにより、ユーザーが設定した出発地または目的地に最も近い道路が長いリンクで近くに交差点がない場合でも他の道路上の交差点に探索開始点または探索終了点が設定されることを防ぐことができる。
　【００１５】
　また第４の手段によると、第３の手段により実現された機能を満たした上で、出発地または目的地から最も近い各道路上の点を求め、出発地または目的地から最も近い点までの距離の関数で与えられるコストとその点から道路の両端の交差点に対する距離の関数で与えられるコストの和で探索開始時の初期コストまたは探索終了点到達時の加算コストを与えることにより、出発地から目的地へ到達するために不適切な探索開始点および探索終了点は大きなコストを持つことになるので、出発地から目的地へ向かうために適切な経路を選出することができる。
　【００１６】
　【実施例】
　以下、本発明の実施例を図面を用いて詳細に説明する。
　【００１７】
　（実施例１）
　図１は本発明の第１の実施例を示す推奨経路案内装置のブロック図である。図１において、１０１は交差点や道路の接続状況や座標・形状・属性など道路ネットワークに関する情報を地図データとして記録しておく道路ネットワーク記録手段、１０２は出発地および目的地の位置を入力する地点設定手段、１０３は前記地点設定手段１０２で入力された出発地および目的地の位置から地図データ上の探索開始点および探索終了点を設定する探索開始終了点設定手段、１０４は前記探索開始終了点設定手段１０３で設定された探索開始点から探索終了点までの経路を前記道路ネットワーク記録手段１０１に記憶された地図データを利用して選出する探索手段、１０５は前記探索手段１０４で求められた経路を画像や音声で出力する出力手段である。
　【００１８】
　以上のように構成された第１の実施例の推奨経路案内装置について以下にその動作を説明する。図２（ａ）は第１の実施例における道路網の例を示す図、図２（ｂ）は本道路網においてノード情報の例を示す図、図２（ｃ）は本道路網においてリンク情報の例を示す図である。また、図３は本発明の第１の実施例における推奨経路案内装置の全体動作を示すフローチャート、図４は本発明の第１の実施例における地点設定処理のフローチャートである。
　【００１９】
　図２（ａ）に示されるようにＮ１〜Ｎ１０までの１０個のノードとＬ１〜Ｌ９までの９本のリンクで表される道路網において、道路ネットワーク記録手段１０１には図２（ｂ）に示されるように少なくともノードの位置情報「経度・緯度」とそのノードが接続するリンクの情報「接続リンク」を持ったノード情報と、図２（ｃ）に示されるように少なくともリンクの両端のノードの情報「接続ノード１・接続ノード２」とリンクの形状情報「リンク形状差分データ」を持ったリンク情報が記憶されている。ここで、図２（ａ）において、△（Ｓ）は出発地、▽（Ｄ）は目的地、○はノード、実線はリンク（太さは重要度を表す）を示すものとする。また、（？？ｋｍ／ｈ）の速度表記はその道路における平均走行速度である。ここでもう少し詳しく図２（ｂ）のノード情報と図２（ｃ）のリンク情報について説明しておく。まず、図２（ｂ）のノード情報について述べる。「経度・緯度」情報は各ノードが実際に位置する座標の情報である。「隣接ノード」情報は地図を分割して持つ場合、道路が地図の境界上を横切るところに双方の地図内においてノードを作成するが、実際には同一のノードである隣の地図内のノードの情報を記録する。ただし、図２（ａ）の道路網の場合、簡単のため１地図としているので「隣接ノード」の情報は使用しない。「接続リンク」情報はそのノードがどのリンクにつながっているかを示す情報である。次に、図２（ｃ）のリンク情報について述べる。「距離」情報は実際の道路上の距離を記録し、ここでは例えばメートル単位で示している。この情報は後述するリンク形状データから計算することもできるが計算時間の関係からデータとして持っておくことが望ましい。「コスト」情報は経路を選出する際の評価基準により異なる。ここでは、例えば旅行時間を最小にする経路を求めるものとして、そのリンクにおける旅行時間を０．１秒単位で持つものとする。（？？ｋｍ／ｈ）はそのリンクにおける平均走行速度（時速）を示している。距離と時速からこのコストは計算できるが計算時間の関係から記録しておくことが望ましい。「接続ノード１、接続ノード２」はリンクの両端がどのノードにつながっているかを示している。「一方通行」情報は一方通行規制があればその規制を示す。図中、「Ｎ３→Ｎ２」という表記はノードＮ３からノードＮ２方向のみ通行可ということである。「リンク形状差分データ」情報は該当リンクが「接続ノード１」から「接続ノード２」の間でどのような形状をしているのかを「接続ノード１」の位置からの差分データで記録する。ここで、ユーザーは図２（ａ）の出発地△から目的地▽へ到達する経路を知りたいものと仮定する。このときの処理の詳細を図３、図４のフローチャートに従って以下に説明する。
　【００２０】
　まず、図３のステップ３０１においてユーザーが出発地側地点設定処理を行う。この処理の詳細を図４に示してある。図４のステップ４０１においてユーザーは出発地の位置を例えばＣＲＴに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定し、所望の座標系に変換し位置情報を取得する。ステップ４０２では、設定した出発地の座標を中心に半径ｌｉｍｉｔ＿ｄｉｓｔの円の範囲（図２の点線の円：例えば５０ｍの範囲）の地図情報を読み込むが、この場合は簡単のため１枚の地図内としている。ステップ４０３では、各ノード（Ｎ１〜Ｎ１２）への距離を図２（ｂ）の経度・緯度情報とステップ４０１で得た出発地の位置情報から順次算出し、距離の小さい順にＮ個（例えば４個）を選択して記録する。図２（ａ）のような場合、円の範囲内にノードＮ３しか存在しないので、ノードＮ３とそこまでの距離ＤＮ３を記憶する。次にステップ４０４にて出発地側かどうか判定し、出発地側であればステップ４０５に進み、ノードＮ３に探索開始点フラグを立てる。さらにステップ４０６において探索開始時の初期コストを一定値（例えば０）とする。以上でステップ３０１の処理を終了する。
　【００２１】
　次に、ステップ３０２においてステップ３０１の処理と同様に目的地側地点設定処理を行う。出発地側と違う点は、ステップ４０４において目的地側であると判定されると、ステップ４０７に進み選択したノードに探索終了点フラグを立てる処理を行うことのみである。ステップ３０２の処理により、図２（ａ）の例では探索終了点としてノードＮ５、Ｎ７、Ｎ８の３点が選択される。
　【００２２】
　次にステップ３０３において経路探索処理を実行する。図５に本発明の第１の実施例における経路探索処理のフローチャート、図６に本発明の第１の実施例における出発地側探索処理のフローチャート、図７に本発明の第１の実施例における目的地側探索処理のフローチャートを示す。以下、これらを用いて詳述する。ステップ５０１では、探索開始点フラグが立っているノードＮ３を出発地側探索候補状態とし、探索終了点フラグが立っているノードＮ５、Ｎ７、Ｎ８を目的地側探索候補状態とする。次にステップ５０２で、出発地側と目的地側探索候補状態以外のノードを未探索状態にして初期コストを無限大とし、初期化を行う。さらにステップ５０３において最大探索範囲制限を探索コストの値で設定する。この最大探索範囲制限は探索範囲に比べて十分大きいもの（例えば２００００ｍ）とする。ステップ５０４では、出発地側探索処理を実行する。この処理の詳細は図６に示してあるので、本フローチャートに従って説明する。
　【００２３】
　まず、ステップ６０１では出発地側探索候補状態となっているノードで出発地側探索コストが一番小さいノードを基準交差点とする。ここでは、出発地側探索候補状態となっているノードはノードＮ３しかないので、ノードＮ３が基準交差点となる。ステップ６０２では目的地側の探索に移行すべきかどうか判定する。すなわち出発地側と目的地側探索範囲が接していない状態で、探索範囲がステップ５０３で設定した値を越えた場合目的地側探索に移行するため出発地側探索を終了する。また、基準交差点がなかった場合も、探索続行不能として出発地側探索処理を終了する。しかし、ここでは基準交差点が存在し、かつ最大探索範囲制限は十分大きいとしているのでステップ６０３に進む。ステップ６０３では、出発地側探索コストが出発地側経路確定コスト（初期値：無限大）を越えたかどうかで経路が確定したか判定する。最終的には目的地側探索処理を行って経路を決定する。いま、出発地側経路確定コストは無限大（初期値）のままなのでステップ６０４の処理に進む。ステップ６０４では基準交差点が隣の地図に接続したノード（隣接ノード）であるかどうか判定し、そうであればステップ６１４、６１５、６１６の処理を行い隣の地図の隣接ノードに基準交差点を移す処理を行うが、ここでは図２（ａ）の道路網は簡単のため１地図内を対象にしているので隣接ノードは考慮しないものとする。次にステップ６０５では、基準交差点に接続するリンクを順に調査対象リンクとする。ノードＮ３に接続するリンクは、図２（ｂ）のノード情報よりＬ１、Ｌ２、Ｌ３、Ｌ４の４本である。まず、リンクＬ１を調査対象リンクとする。ステップ６０６でノードＮ３からノードＮ１ヘリンクＬ１を使って進むことができるかどうか調べる。もし、一方通行規制のためノードＮ３からノードＮ１へ進むことができなかった場合にはステップ６１１に進む。しかし、図２（ｃ）のリンク情報よりリンクＬ１は双方向通行可のリンクであるので、ステップ６０７の処理に進む。ステップ６０７では、調査対象リンクの先のノードが目的地側探索候補状態か判定する。調査対象リンクの先のノードが目的地側探索候補状態であれば、ステップ６１７に進み出発地側と目的地側が接続したものとしてこの経路を記録するかどうか判定する。現在、調査対象リンクの先のノードＮ１は未探索状態であるので、ステップ６０８に進む。ステップ６０８では、ノードＮ１への到達コストを計算する。ノードＮ３は出発地であり初期コストが０であるので、
　　ノードＮ１への到達コスト←基準交差点への到達コスト［初期コスト：０］＋調査対象リンクＬ１のコスト［４３］
より、ノードＮ１への到達コストは「４３」となる。次に、ステップ６０９ではノードＮ３に今までの最小コストで到達したか判定する。過去にもっと小さいコストで到達したことがあれば、ステップ６１１に進みノードＮ１に今回の探索結果を記憶しない。しかし、ノードＮ３は初期状態なので今回到達するのが初めてである。故に、ステップ６１０に進み、探索結果をノードＮ１に記憶する。記憶する内容は、
　　前ノード　←　ノードＮ３
　　前リンク　←　リンクＬ１
　　出発地側探索コスト　←　「４３」
である。さらにノードＮ１を出発地側探索候補状態とする。次に、ステップ６１１において、ノードＮ３に接続する全てのリンクを調査対象リンクに選択したか判定する。まだ、リンクＬ２、Ｌ３、Ｌ４が残っているのでステップ６０５の処理に戻る。ステップ６０５では次に調査対象リンクとしてリンクＬ２を選択する。ステップ６０６において、リンクＬ２上をノードＮ３からノードＮ２に進めるかどうかチェックされるが、図２（ｃ）のリンク情報よりこの方向への進行は可能な一方通行規制であるのでステップ６０７の処理に進む。ステップ６０７〜ステップ６１１までの処理を上記と同様に繰り返し、ノードＮ２に次の探索結果を記憶する。
　【００２４】
　　前ノード　←　ノードＮ３
　　前リンク　←　リンクＬ２
　　出発地側探索コスト　←　「１８０」
　さらに、ノードＮ２を出発地側探索候補状態とする。ステップ６１１において、ノードＮ３に接続するリンクはリンクＬ３、Ｌ４が残っているので、ステップ６０５に戻り調査対象リンクをＬ３にする。しかし、ステップ６０６でリンクＬ３上はノードＮ３からノードＮ４へは一方通行規制により進めないのでステップ６１１の処理に進む。ゆえに、ノードＮ４には探索結果を記憶しない。ステップ６１１において、ノードＮ３に接続するリンクはリンクＬ４が残っているので、ステップ６０５に戻り調査対象リンクをＬ４にする。ステップ６０６までは従来通りであるが、ステップ６０７で調査対象リンクの先のノードＮ７は目的地側探索候補状態なので経路選出判定を行うためステップ６１７に進む。ここでは、経路の総コストを算出する。
　【００２５】
　経路総コスト←基準交差点Ｎ３への到達コスト［初期コスト：０］＋調査対象リンクのコスト［１７３］＋目的地側探索候補状態の交差点Ｎ７のコスト［初期コスト：０］
故に、経路総コストは「１７３」と算出される。次に、ステップ６１８において、算出した経路総コストは過去に求められた経路の内、最小のコストであるかどうか判定される。もし最小コストでなければ、もっと小さいコストで出発地から目的地まで到達できる経路が求められていたものとしてステップ６１１に進み、今回の探索結果を記憶しない。しかし、今の場合、初めて出発地側と目的地側が接続したのでステップ６１９に進み、経路接続地点情報として次の情報を記憶する。
　【００２６】
　　出発地側接続交差点　　　←　ノードＮ３
　　目的地側接続交差点　　　←　ノードＮ７
　　出発地側経路確定コスト　←　「１７３」
　　目的地側経路確定コスト　←　「０」
　　経路接続総コスト　　　　←　「１７３」
　　接続リンク　　　　　　　←　リンクＬ４
　次にステップ６１１に進み、基準交差点Ｎ３に接続するリンクを全て調査対象リンクとしたか判定する。ここでは、全て調査済みであるのでステップ６１２に進む。ステップ６１２では基準交差点Ｎ３を出発地側探索済み状態にして、ノードＮ３を基準とした探索処理を終了する。再びステップ６０１に戻り全てのノードを調査して、出発地側探索候補状態で出発地側探索コストが最小のノードを捜す。現在、ノードＮ３に接続している２つのノードＮ１、Ｎ２がそれぞれ出発地側探索コスト「４３」、「１８０」を持ち出発地側探索候補状態となっている。現時点で最小な出発地側探索コストを持つ出発地側探索候補状態ノードはノードＮ１となる。故に基準交差点としてノードＮ１が選択される。次にステップ６０２〜ステップ６０８までは上記と同様に処理され（簡単のため探索対象地図は１地図のみと考えて隣接ノードは考慮しない）、リンクＬ１が調査対象リンクとなりノードＮ３への到達コストとして「４３」＋「４３」が求められるが、ステップ６１０においてノードＮ３は探索開始点として初期コスト「０」が与えられているので今までの最小コストで到達していないと判定され、ステップ６１１へ進む。ステップ６１１ではノードＮ１につながった全ての接続リンクが調査されたとしてステップ６１２に進み、ノードＮ１を出発地側探索済み状態にする。また、ステップ６０１に戻り同様に次の基準交差点をノードＮ２とする。ここで、ステップ６０３においてノードＮ２の出発地側探索コスト「１８０」は出発地側経路確定コスト「１７３」よりも大きいので、ステップ６１３に進み出発地側経路探索処理で目的地側に接したことを示すフラグを立てる。以上でステップ５０４の出発地側探索処理を終了する。
　【００２７】
　次にステップ５０５に進み、目的地側探索処理を実行する。この処理の詳細は図７に示してある。基本的に出発地側探索処理と異なる点が２点ある。１点は、ステップ７０６において基準交差点に接続する調査対象リンクが走行できるかどうかチェックする時、目的地側探索の場合は実際に車両が走行する向きとは逆の方向に探索を広げているので一方通行規制を逆に考える点である。もう１点は、ステップ７０７において目的地側探索範囲と出発地側探索範囲が接した状態の判定を調査対象リンクの先のノードが出発地側探索済み状態であることにより行う点である。これ以外は出発地側と同様の探索処理を行う。この場合、ノードＮ６、Ｎ９、Ｎ１０がそれぞれ目的地側探索コスト［９０」、「９０」、「５８」を持つ目的地側探索候補状態になり次の基準交差点としてノードＮ１０が選択されたところで、目的地側経路確定コストが「０」であり目的地側探索コストが「５８」となるのでステップ７０３の判定でステップ７１３の処理に進む。ここで、目的地側経路確定判定がなされ全経路が確定したことを示すフラグを立てる。以上でステップ５０５の目的地側探索処理を終了する。
　【００２８】
　ステップ５０６では経路が確定したことを確認し、もし経路が確定されていなければ、ステップ５０７で探索失敗フラグを立てる。しかし、この場合ステップ７１３において全経路が確定したフラグが立っているのでステップ５０６で全経路確定したと判断されてステップ３０３の経路探索処理を終了する。
　【００２９】
　ステップ３０４では探索失敗フラグが立っているかどうかチェックする。探索成功と判定されればステップ３０５に進み、例えば求められた経路を走行順に地図番号とリンク番号（方向性を含む）の列に直し経路構成を行う。さらにステップ３０６で求められた経路をＣＲＴに写し出された地図に合わせて表示することにより経路をユーザーに示す。ステップ３０４において、探索失敗フラグが立っていると探索失敗と判定して、ステップ３０７で例えば経路が求められなかったことをユーザーに告知するなどの探索失敗時の処理を行う。この場合、経路地点接続情報から経路構成を行うとノードＮ３からノードＮ７へリンクＬ４を使って到達する経路が得られる。故に次の経路構成結果が残される。
　【００３０】
　　地図番号１　　←　＊（１地図なので不要）
　　リンク番号１　←　リンクＬ４
　　方向性　　　　←　「接続ノード１」から「接続ノード２」へ
　以上のように、第１の実施例によれば複数の地点を出発地または目的地として選択することにより、例えば図２（ａ）の道路網の例でノードＮ３−リンクＬ４−ノードＮ７−リンクＬ７−ノードＮ８−リンクＬ５−ノードＮ５に至るような目的地の前を行き過ぎるような経路を出さないようにすることができる。
　【００３１】
　（実施例２）
　次に本発明の第２の実施例について説明する。本発明の第２の実施例を示す推奨経路案内装置のブロック図は第１の実施例と同様である。
　【００３２】
　以上のように構成された第２の実施例の推奨経路案内装置について以下にその動作を説明する。図８（ａ）は第２の実施例における道路網の例を示す図、図８（ｂ）は本道路網においてノード情報の例を示す図、図８（ｃ）は本道路網においてリンク情報の例を示す図である。また、図９は本発明の第２の実施例における地点設定処理のフローチャートである。
　【００３３】
　それでは、図８の道路網の例と図９の地点設定処理のフローチャートを用いて第１の実施例との差異を説明する。まず、図８（ａ）に示されるようにＮ１〜Ｎ１２までの１２個のノードとＬ１〜Ｌ１１までの１１本のリンクで表される道路網において、道路ネットワーク記録手段１０１には図８（ｂ）に示されるようなノード情報と図８（ｃ）に示されるようなリンク情報が記憶されている。ここで、各種記号は図２の場合と同様である。
　【００３４】
　このようなネットワークの場合、図４のステップ４０３で選択される交差点数Ｎを４として第１の実施例と同様に経路を求めると、図８におけるノードＮ６が探索終了点の１つに含まれてしまうので、最終的に選択される経路は探索開始点群（ノードＮ３）と探索終了点群（ノードＮ６、Ｎ７、Ｎ９、Ｎ１０）を結ぶ組合せのうち一番コストの小さい組合せの経路ノードＮ３−リンクＬ４−ノードＮ６が選択されてしまう。ゆえに、ノードＮ６までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。そこで、第２の実施例として地点設定処理を図９のような処理に変更することによりこの問題を解決する。
　【００３５】
　第２の実施例における地点設定処理と第１の実施例における地点設定処理の差異はステップ９０６の初期コストの設定にある。第１の実施例ではステップ４０６に示すように一律同じ値（０）としていたが、第２の実施例ではステップ９０６のように距離に比例した値を与える。ここで、ステップ９０６における比例係数ｍは正の実数である。なお、これは出発地ＳとノードＮ３間へ仮想リンクＶＬ１を、また目的地ＤとノードＮ６、Ｎ７、Ｎ９、Ｎ１０間へそれぞれ仮想リンクＶＬ２、ＶＬ３、ＶＬ４、ＶＬ５を想定し、それぞれの仮想リンクに初期コスト相当の仮想リンクコストを割り付け、出発地Ｓから目的地Ｄまで仮想リンクを含んだ道路ネットワーク上で最小コスト経路を求めたときと同じ結果が地図データに処理を加えないで得られる特徴を持つ。
　【００３６】
　例えば図８（ａ）中のリンクの中で平均走行速度が一番小さいものは時速１０ｋｍ／ｈであるが、初期コストとして直線距離を時速５ｋｍ／ｈで走行した事に等しい値を与える。ゆえに、ノードＮ３には次の初期コストが与えられる。
　【００３７】
　　５（ｍ）／５（ｋｍ／ｈ）×３６＝３６（１０−１秒）
　同様に、各探索開始点・探索終了点とも以下の表１のような初期コストを持つ。
　【００３８】
　【表１】
　【００３９】
　探索開始点の探索終了点の組合せは計４通りある。以上の初期コストの基で全ての経路の組合せについて、これらの経路の総コストを比較すると表２のようになる。
　【００４０】
　【表２】
　【００４１】
　この場合、最小コスト経路はノードＮ３〜ノードＮ９までの経路となり、総コストは３５３となる。
　【００４２】
　このように第２の実施例の特徴である地点設定手法を用いて、第１の実施例と同様に経路探索処理を行うことで探索開始点と探索終了点を結ぶ最短コスト経路であるノードＮ３−リンクＬ４−リンクＬ６−ノードＮ９を求めることができる。故に、第１の実施例の地点設定手法を使用した場合のように、目的地のかなり手前までしか経路が求められないという現象がなくなり、目的地に対してなるべく近くまでの経路を求めることができる。
　【００４３】
　なお、図９のステップ９０６では距離に対して比例して初期コストを与えたが、比例でなければならない必要はない。図１０に別の初期コストの付与例を示す。図１０（ａ）に示すように非連続的でもよいし、図１０（ｂ）に示すように距離により比例乗数ｍを変更してもよい。
　【００４４】
　（実施例３）
　次に本発明の第３の実施例について説明する。本発明の第３の実施例を示す推奨経路案内装置のブロック図は第１の実施例と同様である。
　【００４５】
　以上のように構成された第３の実施例の推奨経路案内装置について以下にその動作を説明する。図１１（ａ）は第３の実施例における道路網の例を示す図、図１１（ｂ）は本道路網においてノード情報の例を示す図、図１１（ｃ）は本道路網においてリンク情報の例を示す図である。また、図１２は本発明の第３の実施例における地点設定処理のフローチャートである。
　【００４６】
　それでは、図１１の道路網の例と図１２の地点設定処理のフローチャートを用いて第１の実施例との差異を説明する。まず、図１１（ａ）に示されるようにＮ１〜Ｎ１３までの１３個のノードとＬ１〜Ｌ１２までの１２本のリンクで表される道路網において、道路ネットワーク記録手段１０１には図１１（ｂ）に示され
るようなノー
ド情報と図１１（ｃ）に示されるようなリンク情報が記憶されている。ここで、各種記号は図２の場合と同様である。
　【００４７】
　このようなネットワークの場合、第１および第２の実施例と同様に経路を求めると、図８におけるノードＮ５のみが探索終了点に選ばれてしまうので、最終的に選択される経路はノードＮ３−リンクＬ４−ノードＮ５が選択されてしまう。ゆえに、ノードＮ５までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。そこで、第３の実施例として地点設定処理を図１２のような処理に変更することによりこの問題を解決する。
　【００４８】
　第３の実施例における地点設定処理と第１および第２の実施例における地点設定処理の差異は、探索開始点および探索終了点の設定基準をリンク上に置くかノード上に置くかにある。第１および第２の実施例では出発地または目的地の位置から近いノードを探索開始点または探索終了点として選択していたが、第３の実施例では出発地または目的地の位置から近いリンクを選択してそのリンク上の端のノードを探索開始点または探索終了点とする。以降に図１２のフローチャートを用いて詳細に説明する。図１２のステップ１２０１においてユーザーは出発地（目的地）の位置を例えばＣＲＴに映し出された地図上にカーソルを表示し、カーソルを移動させることにより位置を決定して、所望の座標系に変換し位置情報を取得する。ステップ１２０２では、設定した出発地の座標を中心に半径ｌｉｍｉｔ＿ｄｉｓｔの円の範囲（図２の点線の円：例えば５０ｍの範囲）の地図情報を読み込むが、この場合は簡単のため１枚の地図内としている。ステップ１２０３では、各リンク（Ｌ１〜Ｌ１２）への距離（各差分データ成分への一番近い距離）を図１１（ｂ）の経度・緯度情報および図１１（ｃ）のリンク形状差分データとステップ１２０１で得た出発地（目的地）の位置情報から順次算出し、距離の小さい順にＮ本（例えば２本）を選択して垂線とリンクの交点の位置および距離を記録する。
図１１（ａ）
　【００４９】
　ここで、探索開始点の探索終了点の組合せは計４通りある。全ての経路の組合せについて、これらの経路の総コストを比較すると表３のようになる。
　【００５０】
　【表３】
　【００５１】
　この場合、最小コスト経路はノードＮ３〜ノードＮ７までの経路となり、総コストは２６６となる。
　【００５２】
　このように、第３の実施例の特徴である地点設定手法を用いて、第１および第２の実施例と同様に経路探索処理を行う事により、最小コスト経路としてノードＮ３−リンクＬ４−リンクＬ６−ノードＮ７を求めることができる。故に、第１および第２の実施例の地点設定手法を使用した場合のように、目的地付近の道路とは離れた道路上の交差点までの経路を求めてしまう現象がなくなり、目的地へ到達するために適した経路を求めることができる。
　【００５３】
　なお、図１２のステップ１２０５ではノードＮ３には交点Ｐ１からノードＮ３までの距離または交点Ｐ２からノードＮ３までの距離の短い方を記録したが、出発地からの総距離の短い方を記録しても良いし、リンクに出るまでの距離の短い方を記録してもよい。また、予め出発地からリンク上に下ろした垂線との交点と探索開始点との間の形状データおよび目的地からリンク上に下ろした垂線との交点と探索終了点との間の形状データを保持して置くことによりリンク途中までの経路表示や誘導を行ってもよい。また、リンク形状に垂線が下ろせない場合、各形状データの曲折点への距離中、一番距離が小さい点をリンクとの交点として採用してもよい。
　【００５４】
　（実施例４）
　次に本発明の第４の実施例について説明する。本発明の第４の実施例を示す推奨経路案内装置のブロック図は第１の実施例と同様である。
　【００５５】
　以上のように構成された第４の実施例の推奨経路案内装置について以下にその動作を説明する。図１３（ａ）は第４の実施例における道路網の例を示す図、図１３（ｂ）は本道路網においてノード情報の例を示す図、図１３（ｃ）は本道路網においてリンク情報の例を示す図である。また、図１４は本発明の第４の実施例における地点設定処理のフローチャートである。
　【００５６】
　それでは、図１３の道路網の例と図１４の地点設定処理のフローチャートを用いて第３の実施例との差異を説明する。まず、図１３（ａ）に示されるようにＮ１〜Ｎ１２までの１２個のノードとＬ１〜Ｌ１１までの１１本のリンクで表される道路網において、道路ネットワーク記録手段１０１には図１３（ｂ）に示されるようなノード情報と図１３（ｃ）に示されるようなリンク情報が記憶されている。ここで、各種記号は図２の場合と同様である。
　【００５７】
　このようなネットワークの場合、第１および第２の実施例と同様に経路を求めると、探索開始点としてノードＮ３が、探索終了点としてノードＮ６がそれぞれ選択されるので、最終的に選択される経路はノードＮ３とノードＮ６を結ぶ経路ノードＮ３−リンクＬ４−リンクＬ６−ノードＮ６が選択されてしまう。ゆえに、ノードＮ６までの経路しか求められないので目的地▽に到達するかなり手前までしか経路がわからない。また、第３の実施例と同様に経路を求めると、探索開始点としてノードＮ３が、探索終了点としてノードＮ５，Ｎ８，Ｎ９，Ｎ１２が選択されるので、最終的に選択される経路は探索開始点群（ノードＮ３）と探索終了点群（ノードＮ５，Ｎ８，Ｎ９，Ｎ１２）を結ぶ最小コスト経路である経路ノードＮ３−リンクＬ４−ノードＮ５が選択されてしまう。ゆえに、ノードＮ５を通り地点Ｐ３に到達する経路しか求められないので目的地▽に至るにふさわしい経路が求められない。そこで、第４の実施例として地点設定処理を図１４のような処理に変更することによりこの問題を解決する。
　【００５８】
　第４の実施例における地点設定処理と第３の実施例における地点設定処理の差異はステップ１４０７の初期コストの設定にある。第３の実施例ではステップ１２０７に示すように一律同じ値（０）としていたが、第４の実施例ではステップ１４０７のようにリンクに下ろした垂線の距離に比例したコストとリンク上を走行するためのコストの和で初期コストを与える。ここで、ステップ１４０７における比例係数ｍ１、ｍ２は正の実数である。なお、これは出発地ＳからリンクＬ１へ下ろした垂線を仮想リンクＶＬ１（リンクＬ１との交点をＰ１）、リンクＬ３に下ろした垂線を仮想リンクＶＬ２（リンクＬ３との交点をＰ２）、また目的地ＤからリンクＬ５に下ろした垂線を仮想リンクＶＬ３（リンクＬ５との交点をＰ３）、リンクＬ１０に下ろした垂線を仮想リンクＶＬ４（リンクＬ１０との交点をＰ４）として、それぞれの仮想リンクに初期コスト相当の仮想リンクコストを割り付け、出発地Ｓから目的地Ｄまで仮想リンクを含んだ道路ネットワーク上で最小コスト経路を求めた場合と同じ結果が地図データに処理を加えなくても得られる特徴を持つ。
　【００５９】
　例えば図１３（ａ）中のリンクの中で平均走行速度が一番小さいものは時速１０ｋｍ／ｈであるが、仮想リンクコストとして仮想リンク上を時速５ｋｍ／ｈで走行した事に等しい値を与える。また、仮想リンクから通常リンク上へ出た地点から次の交差点まで進むコストとして、通常リンク全体のコストを走行した距離の比で分配した値を与える。ゆえに、ノードＮ３には次の初期コストが与えられる。
［１］　　５（ｍ）／５（ｋｍ／ｈ）×３６　　　　　　…仮想リンコスト　
　　　＋　４３　（リンクＬ１のコスト）／６０（ｍ）×５（ｍ）　…リンクＬ１上の分配コスト
　　　≒　４０　（１０−１秒）　　　　　　　　［リンクＬ１経由の初期コスト］
［２］　　５（ｍ）／５（ｋｍ／ｈ）×３６　　　　　　　…仮想リンクコスト
　　　＋　２５２（リンクＬ３のコスト）／１４０（ｍ）×５（ｍ）…リンクＬ３上の分配コスト
　　　≒　４５　（１０−１秒）　　　　　　　　　［リンクＬ３経由の初期コスト］
　リンクＬ１経由の方がリンクＬ３経由よりも初期コストが小さいのでノードＮ３にはリンクＬ１経由の情報が残される。故に初期コストは４０となる。
　【００６０】
　同様に、各探索開始点・探索終了点とも以下の表４のような初期コストを持つ。
　【００６１】
　【表４】
　【００６２】
　探索開始点の探索終了点の組合せは計８通りある。以上の初期コストの元で全ての経路の組合せについて、これらの経路の総コストを比較すると表５のようになる。
　【００６３】
　【表５】
　【００６４】
　この場合、最小コスト経路はノードＮ３〜ノードＮ８までの経路となり、総コストは４３６となる。
　【００６５】
　このように第４の実施例の特徴である地点設定手法を用いて、第１の実施例と同様に経路探索処理を行うことで探索開始点と探索終了点を結ぶ最短コスト経路であるノードＮ３−リンクＬ４−リンクＬ６−リンクＬ８−ノードＮ８を求めることができる。故に、第１、第２、第３の実施例の地点設定手法を使用した場合のように、目的地へ到達するには不適切な経路を選択する現象がなくなり、目的地に対して適切な経路を求めることができる。
　【００６６】
　なお、図１４のステップ１４０７ではリンクまでの距離に対して比例して仮想リンクコストコストを与えたが、図１０（ａ）に示すように非連続的でもよいし、図１０（ｂ）に示すように距離により比例乗数ｍを変更してもよい。また、リンクへの垂線との交点からリンクの端ノードまでのコストとして、リンク全体のコストを距離で分配したが、特別な仮想走行速度を想定してリンクコストを付与し直してもよい。また、ノードまでの直線距離に比例して初期コストを与えてもよい。さらにこの場合、ノードまでの直線距離に対して図１０（ａ）に示すように非連続的でもよいし、図１０（ｂ）に示すように直線距離により比例乗数を変更してもよい。また、目的地から垂線をおろしたリンクを基準にした位置関係、すなわち経路上を走行してそのリンクから目的地へ向かう場合左右どちらに曲がるかによって決定する右左折のペナルティコストを目的地側の初期コストに加えてもよい。
　【００６７】
　さらに、第１から第４の実施例共に、車両の現在位置と向きを取得して出発地側の探索開始点の設定を行なってもよい。例えば、車両がリンク上に存在しなければ取得した位置情報を基に上記実施例に従って出発地側の探索開始点を設定してもよいし、車両がリンク上に存在すれば車両の前方方向のリンクの行き先ノードを出発地側の探索開始点に設定してもよい。また、探索開始点にリンク走行分に相当する初期コストを持たせてもよい。また、車両がリンク上に存在した場合で一方通行規制に従って車両の前方方向と反対向きに進むことが可能な場合は、そのリンクの行き先ノードとは反対側のノードを出発地側の探索開始点に加えてもよい。その場合、リンク走行分に相当するリンクコストとＵターンペナルティコストを加えたコストを初期コストとして与えてもよい。さらに、リンク上に現在位置が存在しない場合、車両の向きとリンクの向きがなす角度により初期コストにペナルティコストを加えてもよい。
　【００６８】
　最後に、探索時に交差点で曲がる角度や道なりから外れることなどによりコストを加算してもよいし、探索する評価基準（コストの対象）は例えば料金や走り易さ等の概念を含んでもよい。また、探索法は出発地と目的地双方から探索する双方向探索を用いたが、出発地または目的地のいずれか一方から探索する一方向探索でもよい。その場合、探索の終了点側の初期コストはその点が探索候補状態になったとき到達コストに加算コストとして加えられる。その結果、加算コストを含んだ総コストが最小となる経路が選出される。さらに一方向探索の場合、目的地側を探索開始点として出発地側へ向かって探索を広げてもよい。また、探索法については階層化された地図を用いて探索を行なってもよいし、ダイクストラ法でなくても最小コスト経路を求められる方法であればよい。また、出力手段は経路を表示するだけでなく、車両の現在位置を取得し曲がるべき交差点の手前で音声により誘導案内を行ってもよい。また、出発地側と目的地側の地点設定法は同一でなくてもよい。
　【００６９】
　【発明の効果】
　このように本発明の第１の手段によると地点設定した位置近傍の複数の地点に固有の探索開始時の初期コストまたは探索終了点到達時の加算コストを与えた探索開始点または探索終了点を設定することによって、新たな入力作業を伴うことなく、順序づけられた複数の探索開始点および探索終了点の中から合理的な探索開始点および探索終了点を選択でき、かつ、行き過ぎ等の不適切な経路を選出することを防ぐことができる。
　【００７０】
　また、第２の手段によると第１の手段で選択した複数の交差点に地点設定した位置からの距離の関数で初期コストを与えてやることにより、地点設定した位置から遠くの交差点が経路の開始点や終了点となることを防ぐことができる。
　【００７１】
　さらに、第３の手段によると地点設定した位置近傍の１本以上の道路上の両端交差点のなかで通行規制を遵守して通ることができる交差点を探索開始点・探索終了点として設定することにより、地点設定位置の近傍道路に接続していない交差点が経路の開始点や終了点となることを防ぐことができる。
　【００７２】
　最後に、第４の手段によると第３の手段で選択した複数の交差点に、地点設定位置の近傍道路までの距離の関数で与えられたコストと前記近傍道路上の走行距離の関数で与えられたコストの和で初期コストを与えることにより、出発地から目的地まで到達するために最も適切な経路を選択することができる。
【図面の簡単な説明】
　【図１】
　本発明の第１から第４の実施例を示す推奨経路案内装置のブロック図
　【図２】
　（ａ）は本発明の第１の実施例における道路網の例を示す図
　（ｂ）は本発明の第１の実施例における道路網においてノード情報データの例を示す図
　（ｃ）は本発明の第１の実施例における道路網においてリンク情報データの例を示す図
　【図３】
　本発明の第１から第４の実施例における推奨経路案内装置の全体動作を示すフローチャート
　【図４】
　本発明の第１の実施例における地点設定処理のフローチャート
　【図５】
　本発明の第１から第４の実施例における経路探索処理のフローチャート
　【図６】
　本発明の第１から第４の実施例における出発地側探索処理のフローチャート
　【図７】
　本発明の第１から第４の実施例における目的地側探索処理のフローチャート
　【図８】
　（ａ）は本発明の第２の実施例における道路網の例を示す図
　（ｂ）は本発明の第２の実施例における道路網においてノード情報データの例を示す図
　（ｃ）は本発明の第２の実施例における道路網においてリンク情報データの例を示す図
　【図９】
　本発明の第２の実施例における地点設定処理のフローチャート
　【図１０】
　（ａ）は本発明の第２、第４の実施例とは別の初期コストの付与例を示す図（１）
　（ｂ）は本発明の第２、第４の実施例とは別の初期コストの付与例を示す図（２）
　【図１１】
　（ａ）は本発明の第３の実施例における道路網の例を示す図
　（ｂ）は本発明の第３の実施例における道路網においてノード情報データの例を示す図
　（ｃ）は本発明の第３の実施例における道路網においてリンク情報データの例を示す図
　【図１２】
　本発明の第３の実施例における地点設定処理のフローチャート
　【図１３】
　（ａ）は本発明の第４の実施例における道路網の例を示す図
　（ｂ）は本発明の第４の実施例における道路網においてノード情報データの例を示す図
　（ｃ）は本発明の第４の実施例における道路網においてリンク情報データの例を示す図
　【図１４】
　本発明の第４の実施例における地点設定処理のフローチャート
　【図１５】
　（ａ）は従来の地点設定法では希望する経路が求められない場合の道路網の例（目的地側）を示す図
　（ｂ）は従来の地点設定法を用いて求めた選択経路の例を示す図
　【符号の説明】
　１０１　道路ネットワーク記憶手段
　１０２　地点設定手段
　１０３　探索開始終了点設定手段
　１０４　探索手段
　１０５　出力手段