(57)【要約】【課題】精度とレスポンスというお互いに矛盾する要件を満たす最適ルートが算出でき、事前準備インデックスデータを無効にする回避・規制情報等の雑音データに対しても柔軟に対応でき、且つ、用途、目的に応じて多様な特徴を持った最適ルートが算出可能である最適ルート探索方法及び装置を提供する。【解決手段】上記課題を解決するために、最適ルート探索方法においては、出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定工程と、目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定工程と、起点と終点との間に回避又は規制がある場合に回避又は規制を考慮しながら起点から終点までの最適ルートを道路情報を用いて探索する探索工程とを含む。【選択図】　　　図１５
2004101447.tif 000002
【特許請求の範囲】
【請求項１】
最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段により出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定工程と、設定手段により目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定工程と、起点と終点との間に回避又は規制がある場合に回避又は規制を考慮しながら起点から終点までの最適ルートを道路情報を用いて探索する探索工程とを含むことを特徴とする最適ルート探索方法。
【請求項２】
請求項１に記載の最適ルート探索方法において、リンク上制御点は操作者により入力された指示制御点から求められることを特徴とする最適ルート探索方法。
【請求項３】
請求項１に記載の最適ルート探索方法において、回避とは使用者により任意に指定された通行禁止設定であり、規制とは道路に対して課せられた種々の規制であることを特徴とする最適ルート探索方法。
【請求項４】
請求項１に記載の最適ルート探索方法において、出発地設定工程及び目的地設定工程のそれぞれにおいて複数のリンク上制御点が設定され、探索工程において設定された複数のリンク上制御点から複数のルートが探索され、更に探索された複数のルートから１つの最適なルートを抽出する抽出工程を含むことを特徴とする最適ルート探索方法。
【請求項５】
請求項１に記載の最適ルート探索方法の迂回路探索工程において、リンク上制御点を起点または終点として所定の方向を向いた道路リンクを設定する道路リンク設定工程を含み、所定の方向を向いた道路リンクの左又は右の一定の側に目的物があることを特徴とする最適ルート探索方法。
【請求項６】
最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段によりルート探索における出発地点を設定する出発地設定工程と、設定手段によりルート探索における目的地点を設定する目的地設定工程と、出発地点又は目的地点を含む所定サイズの領域を中心として当該所定サイズ単位で全方位方向に領域を広げながら探索した道路ノードの数と道路ノード数閾値とを比較することにより全体道路で探索する範囲を自動的に設定する全体道路探索範囲設定工程と、全体道路探索範囲設定工程により設定された全体道路探索範囲における複数の道路ノードを抽出する抽出工程と、抽出された道路ノードを起点又は終点として出発地点及び目的地点の間にある全体道路探索範囲外の中間部ルートを幹線道路の道路情報を用いて探索する中間部ルート探索工程とを含むことを特徴とする最適ルート探索方法。
【請求項７】
請求項６に記載の最適ルート探索方法において、全体道路とは分断された道路線形状であるリンクとそのリンクの両端にあるノードとからなり、当該リンクは分断された幹線道路を示す幹線リンクと分断された非幹線道路を示す非幹線リンクを含み、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードと非幹線リンクの両端にある非幹線ノードを含み、当該道路ノードは幹線ノードまたは幹線上ノードであることを特徴とする最適ルート探索方法。
【請求項８】
最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段により出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定工程と、設定手段により目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定工程と、回避又は規制を考慮せずに起点から終点までの基本ルートを道路情報を用いて探索する基本ルート探索工程と、回避及び規制が設定されている幹線リンクに対する迂回路探索範囲を自動的に設定する迂回路探索範囲設定工程と、迂回路探索範囲設定工程で設定された迂回路探索範囲内の迂回路ルート探索の起点から終点までの迂回路を道路情報を用いて探索する迂回路探索工程と、前記基本ルートに迂回路探索工程で得られた迂回路を統合して出力する統合工程とを含むことを特徴とする最適ルート探索方法。
【請求項９】
請求項８に記載の最適ルート探索方法において、基本ルート探索工程において基本ルートを求めた後に迂回路を適用する迂回路探索仮定を用いることを特徴とする最適ルート探索方法。
【請求項１０】
請求項８に記載の最適ルート探索方法において、迂回路探索範囲設定工程は回避、規制のグループ化をすることを特徴とする最適ルート探索方法。
【請求項１１】
請求項８に記載の最適ルート探索方法の迂回路探索工程において、分断された道路線形状であるリンクとそのリンクの両端にあるノードとからなる道路において、当該リンクが分断された幹線道路を示す幹線リンクと分断された非幹線道路を示す非幹線リンクを含み、且つ、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードと非幹線リンクの両端にある非幹線ノードを含む全体道路で回避又は規制を考慮しながら迂回路を探索する全体道路迂回路走行モードと、当該リンクが分断された幹線道路を示す幹線リンクであり、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードを含む細分化幹線道路で回避又は規制を考慮しながら迂回路を探索する細分化幹線迂回路走行モード、及び中間部ルート探索を最初から細分化幹線で行なう細分化幹線長距離走行モードとを自動的に選択することを特徴とする最適ルート探索方法。
【請求項１２】
出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定手段と、目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定手段と、起点と終点との間に回避又は規制がある場合に回避又は規制を考慮しながら起点から終点までの最適ルートを道路情報を用いて探索する探索手段とを含むことを特徴とする最適ルート探索装置。
【請求項１３】
出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、ルート探索における出発地点を設定する出発地設定手段と、ルート探索における目的地点を設定する目的地設定手段と、出発地点又は目的地点を含む所定サイズの領域を中心として当該所定サイズ単位で全方位方向に領域を広げながら探索した道路ノードの数と道路ノード数閾値とを比較することにより全体道路で探索する範囲を自動的に設定する全体道路探索範囲設定手段と、全体道路探索範囲設定手段により設定された全体道路探索範囲における複数の道路ノードを抽出する抽出手段と、抽出された道路ノードを起点又は終点として出発地点及び目的地点の間にある全体道路探索範囲外の中間部ルートを幹線道路の道路情報を用いて探索する中間部ルート探索手段とを含むことを特徴とする最適ルート探索装置。
【請求項１４】
出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定手段と、目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定手段と、回避又は規制を考慮せずに起点から終点までの基本ルートを道路情報を用いて探索する基本ルート探索手段と、回避及び規制が設定されている幹線リンクに対する迂回路探索範囲を自動的に設定する迂回路探索範囲設定手段と、迂回路探索範囲設定手段で設定された迂回路探索範囲内の迂回路ルート探索の起点から終点までの迂回路を探索する迂回路探索手段と、前記基本ルートに迂回路探索手段で得られた迂回路を統合して出力する統合手段とを含むことを特徴とする最適ルート探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、道路のルート探索に係わり、特に、使用者個々の価値観に応じた多様な探索結果を提供すると共に、精度とレスポンスの双方を満足する最適ルート探索方法及び装置に関するものである。
【０００２】
【従来の技術】
従来のシステムでは、ルート探索を高速化するために事前にデータの絞り込みに利用するインデックスを作成していた。このインデックスは、事前に作成される静的なデータである。従って、リアルタイムに与えられた回避・規制に対応できないため、この事前に作成されたインデックスが役に立たないという事態が発生する。ここでインデックスとしては色々な形態が有り得るが、一つにはあるゾーンからあるゾーンに行く場合に通り得るゾーンの最大集合を事前に計算しておく方法がある。例えば、東京から大阪に行く場合は、せいぜい東海から中部ゾーンしか通らないという知識である。もう一つは、幹線道路のような地域を結ぶ主要な本線の交差点等の情報と、主要な道路の線形状等の情報からなる幹線道路ネットワークのような、より上位の道路ネットワークを事前に作成するものである。このような上位の道路ネットワークを考えることで交差点等の情報量を減らすことができるため、それだけ検索が高速になる。
【０００３】
【発明が解決しようとする課題】
しかし、従来のシステムでは、次のような問題があった。
１．自由度：最適ルート探索には色々な価値観（兎に角精度を良くしたい：精度が悪くても良いから高速に検索したい：迂回路としては幹線だけを走りたい等）が存在するにも拘わらず、従来の最適ルート探索ではインデックスとして事前に作成される静的なデータを用いるため、ロジックに自由度がなかった。従って、使用者個々の価値観に応じた多様な探索結果を提供することが出来なかった。
【０００４】
２．精度とレスポンス：また、従来は精度とレスポンスの双方を満足する探索は実現されていなかったという問題があった。
【０００５】
３．出発地と目的地を反転させた場合に求められるルートが必ずしも対称にならないことがあった。
【０００６】
４．出発地、経由地、目的地付近における道路リンクの走行方向に対して、制約を課すことが出来なかった。
【０００７】
【課題を解決するための手段】
（１）上記目的を解決するために、最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段により出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定工程と、設定手段により目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定工程と、起点と終点との間に回避又は規制がある場合に回避又は規制を考慮しながら起点から終点までの最適ルートを道路情報を用いて探索する探索工程とを含むことを特徴とする。
【０００８】
（２）また、（１）に記載の最適ルート探索方法において、リンク上制御点は操作者により入力された指示制御点から求められることを特徴とする。
【０００９】
（３）更に、（１）に記載の最適ルート探索方法において、回避とは使用者により任意に指定された通行禁止設定であり、規制とは道路に対して課せられた種々の規制であることを特徴とする。
【００１０】
（４）また、（１）に記載の最適ルート探索方法において、出発地設定工程及び目的地設定工程のそれぞれにおいて複数のリンク上制御点が設定され、探索工程において設定された複数のリンク上制御点から複数のルートが探索され、更に探索された複数のルートから１つの最適なルートを抽出する抽出工程を含むことを特徴とする。
【００１１】
（５）加えて、（１）に記載の最適ルート探索方法の迂回路探索工程において、リンク上制御点を起点または終点として所定の方向を向いた道路リンクを設定する道路リンク設定工程を含み、所定の方向を向いた道路リンクの左又は右の一定の側に目的物があることを特徴とする。
【００１２】
（６）また、最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段によりルート探索における出発地点を設定する出発地設定工程と、設定手段によりルート探索における目的地点を設定する目的地設定工程と、出発地点又は目的地点を含む所定サイズの領域を中心として当該所定サイズ単位で全方位方向に領域を広げながら探索した道路ノードの数と道路ノード数閾値とを比較することにより全体道路で探索する範囲を自動的に設定する全体道路探索範囲設定工程と、全体道路探索範囲設定工程により設定された全体道路探索範囲における複数の道路ノードを抽出する抽出工程と、抽出された道路ノードを起点又は終点として出発地点及び目的地点の間にある全体道路探索範囲外の中間部ルートを幹線道路の道路情報を用いて探索する中間部ルート探索工程とを含むことを特徴とする。
【００１３】
（７）この他、（６）に記載の最適ルート探索方法において、全体道路とは分断された道路線形状であるリンクとそのリンクの両端にあるノードとからなり、当該リンクは分断された幹線道路を示す幹線リンクと分断された非幹線道路を示す非幹線リンクを含み、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードと非幹線リンクの両端にある非幹線ノードを含み、当該道路ノードは幹線ノードまたは幹線上ノードであることを特徴とする。
【００１４】
（８）また、最適ルート探索装置の不揮発性記憶媒体に格納されている道路情報を使用して走行ルートを探索する最適ルート探索方法において、設定手段により出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定工程と、設定手段により目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定工程と、回避又は規制を考慮せずに起点から終点までの基本ルートを道路情報を用いて探索する基本ルート探索工程と、回避及び規制が設定されている幹線リンクに対する迂回路探索範囲を自動的に設定する迂回路探索範囲設定工程と、迂回路探索範囲設定工程で設定された迂回路探索範囲内の迂回路ルート探索の起点から終点までの迂回路を道路情報を用いて探索する迂回路探索工程と、前記基本ルートに迂回路探索工程で得られた迂回路を統合して出力する統合工程とを含むことを特徴とする。
【００１５】
（９）更に、（８）に記載の最適ルート探索方法において、基本ルート探索工程において基本ルートを求めた後に迂回路を適用する迂回路探索仮定を用いることを特徴とする。
【００１６】
（１０）また、（８）に記載の最適ルート探索方法において、迂回路探索範囲設定工程は回避、規制のグループ化をすることを特徴とする。
【００１７】
（１１）加えて、（８）に記載の最適ルート探索方法の迂回路探索工程において、分断された道路線形状であるリンクとそのリンクの両端にあるノードとからなる道路において、当該リンクが分断された幹線道路を示す幹線リンクと分断された非幹線道路を示す非幹線リンクを含み、且つ、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードと非幹線リンクの両端にある非幹線ノードを含む全体道路で回避又は規制を考慮しながら迂回路を探索する全体道路迂回路走行モードと、当該リンクが分断された幹線道路を示す幹線リンクであり、当該ノードは幹線リンクの両端にある幹線ノードと幹線リンク上にある幹線上ノードを含む細分化幹線道路で回避又は規制を考慮しながら迂回路を探索する細分化幹線迂回路走行モード、及び中間部ルート探索を最初から細分化幹線で行なう細分化幹線長距離走行モードとを自動的に選択することを特徴とする。
【００１８】
（１２）一方、出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定手段と、目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定手段と、起点と終点との間に回避又は規制がある場合に回避又は規制を考慮しながら起点から終点までの最適ルートを道路情報を用いて探索する探索手段とを含むことを特徴とする。
【００１９】
（１３）また、出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、ルート探索における出発地点を設定する出発地設定手段と、ルート探索における目的地点を設定する目的地設定手段と、出発地点又は目的地点を含む所定サイズの領域を中心として当該所定サイズ単位で全方位方向に領域を広げながら探索した道路ノードの数と道路ノード数閾値とを比較することにより全体道路で探索する範囲を自動的に設定する全体道路探索範囲設定手段と、全体道路探索範囲設定手段により設定された全体道路探索範囲における複数の道路ノードを抽出する抽出手段と、抽出された道路ノードを起点又は終点として出発地点及び目的地点の間にある全体道路探索範囲外の中間部ルートを幹線道路の道路情報を用いて探索する中間部ルート探索手段とを含むことを特徴とする。
【００２０】
（１４）更に、出発地点から目的地点までの走行ルートを探索する最適ルート探索装置において、道路情報を格納した不揮発性記憶媒体、出発地側のルート探索の起点となるリンク上制御点を設定する出発地設定手段と、目的地側のルート探索の終点となるリンク上制御点を設定する目的地設定手段と、回避又は規制を考慮せずに起点から終点までの基本ルートを道路情報を用いて探索する基本ルート探索手段と、回避及び規制が設定されている幹線リンクに対する迂回路探索範囲を自動的に設定する迂回路探索範囲設定手段と、迂回路探索範囲設定手段で設定された迂回路探索範囲内の迂回路ルート探索の起点から終点までの迂回路を探索する迂回路探索手段と、前記基本ルートに迂回路探索手段で得られた迂回路を統合して出力する統合手段とを含むことを特徴とする。
【００２１】
以上のような工程を経て最適ルート探索を行なうことにより、▲１▼精度とレスポンスというお互いに矛盾する要件を満たす最適ルートが算出できること（高品質）、▲２▼事前準備インデックスデータを無効にする回避・規制情報等の雑音データに対しても柔軟に対応出来ること（柔軟性）、▲３▼用途、目的に応じて多様な特徴を持った最適ルートが算出可能であること（多様性）、を実現した最適ルート探索方法及び装置を提供することを目的とするものである。
【００２２】
【発明の実施の形態】
〔第１の実施形態〕
図１は、本発明の全体構成を示す図である。各モジュールの構成は、図１の通りである。四角で囲まれた内部が、１つのモジュールに該当する。最適ルート探索と規制情報ＩＯとを用いて、最適ルート探索は実行される。その探索結果は、例えば有料道路を利用した場合の料金計算やＴＳＰ（Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ）の解決のために利用される。各モジュールの機能を、表１に示す。
【００２３】
【表１】
2004101447.tif 000003
【００２４】
次に、本実施形態の最適ルート探索の基本概念について説明をする。
【００２５】
＜ノードとリンクと補間点＞
ノードとリンクは、道路ネットワークを定義する時に用いられる図形要素である。リンクは、道路の線形状そのものである。そして、リンクの両端が、ノードである。言い換えると、リンクは、ノードによって分断されている道路線形状である。ここで、ノードは、▲１▼行き止まり点、▲２▼属性変化点、▲３▼交差点の３種類に分かれる。つまり、ノードが出来る場合は、▲１▼そこで行き止まりになっているか、▲２▼そこで属性（図２の例では、道路幅員や道路管理者等）が変化しているか、▲３▼そこで道路が交差しているか、のいずれかである。最適ルート探索においては、このリンクを辿って最適なルートを探し出す。
【００２６】
尚、図２に示されるように、線分列であるリンクがある。即ち、リンクは複数の線分の集合であり（つまり１本の線分ではない場合がある。）、よってノード以外に別途、補間点と呼ばれる座標記述点を持つ。
【００２７】
＜３種類の道路ネットワーク＞
本発明における道路ネットワークは、全体道路、細分化幹線道路及び集約化幹線道路の３つに分類される（図３参照）。ここで、ネットワークとは、単に道路の線形状のみを意味するのではなく、ノードやリンクの切れ方、つながり方も含めた、いわゆるネットワーク構造を意味する。これ以降、場合によっては「道路ネットワーク」を、単に「道路」と便宜上言う場合がある。
【００２８】
まず、図３を用いて道路ネットワークを説明する。全体道路とは、全ての道路を含む概念である。次に、幹線道路は、その全体道路の中から重要な道路、即ち長距離走行に使われると想定される道路のみを抽出した結果である。幹線道路には、更に「集約化幹線道路」と「細分化幹線道路」の２種類が存在する。
【００２９】
次に、図４を用いて道路ネットワークを説明する。まず、道路リンクは、幹線リンクと非幹線リンクに分かれる。両者の違いは、前述の通り、幹線は重要な道路、即ち長距離走行に使われると想定される道路であるという点である。また、幹線リンク同士の交差点や行き止まり点、また属性変化点を幹線ノードと呼ぶ。ここで注意しなければいけないのは、幹線リンク上にもノードが存在する点である。この幹線ノードでない幹線リンク上のノードを、幹線上ノードと呼ぶ。更に、幹線ノードでも幹線上ノードでも無いノードを、非幹線ノードと呼ぶ。ここで、全体道路は、全てのノードとリンクを含んだ、言わば細かく切れ切れになった全てを包含する道路ネットワークである。次に、細分化幹線道路は、幹線リンクと幹線ノード及び幹線上ノードから構成される道路ネットワークであり、言わば細分化された切れ切れの幹線のネットワークである。最後に、集約化幹線道路は、幹線リンクと幹線ノードしか含んでおらず、言わば最もコンパクトにつながった幹線のネットワークである。各々の道路ネットワークの長所及び短所を、表２に示す。
【００３０】
【表２】
2004101447.tif 000004
【００３１】
ここまでの３種類の道路ネットワークの説明を要約すると、表３になる。
【００３２】
【表３】
2004101447.tif 000005
【００３３】
＜出発地、目的地、経由地＞
出発地（スタート）は、最適ルート探索を行なう際の我々の常識通りの起点となる出発地である。目的地（ゴール）は、最適ルート探索を行なう際の我々の常識通りの終点となる目的地である。経由地は、出発地から目的地に向う途中で、経由して欲しい地点を意味する。経由地には、順番が指定される。もし、順番が指定されないとＴＳＰ、つまり巡回セールスマン問題（複数地点を回る時、どのような順番でどの道路を通れば良いかが不明確となる問題）になる。
【００３４】
経由地が無い場合とある場合の最適ルート探索の様子を、各々図５、図６に示す。
【００３５】
＜指示制御点とリンク上制御点＞
プログラムの内部的な処理の流れを言うと、経由地がある場合は、経由地が無い場合の出発地〜目的地の探索が複数回繰り返されているだけである。例えば、表４の各々の探索は、何れも経由地が無い場合の出発地〜目的地の探索が、各々別個に独立して行なわれているに過ぎない。
【００３６】
【表４】
2004101447.tif 000006
【００３７】
このように、出発地、目的地、経由地は、お互いに非常に似ている。そこで、出発地、目的地、経由地を総称して指示制御点（最適ルート探索を制御し、かつそれは操作者が指示して決めると言う意味で）と呼ぶ（図７）。この指示制御点は、多くの場合、操作者が、例えばマウスクリックにより地図上で指定するので、必ずしも道路上にあるとは限らない。そこで、道路上に移動した、実際に探索が始まる又は終わる点をリンク上制御点と呼ぶ（図７）。また、指示制御点は、観光・レジャーに係わる施設又は会社等の名称、電話番号又はマップコード等を入力することにより指定しても良い。
【００３８】
リンク上制御点を求める時は、指示制御点を中心として周囲に仮想の矩形を発生させ、この矩形を段々膨張させることで、探索範囲を広げて行く。この時、この矩形のサイズの開始値、終了値、増分値を、表５のように命名する。また、この探索のための矩形の膨張の様子を、図８に示す。
【００３９】
【表５】
2004101447.tif 000007
【００４０】
＜回避、規制、迂回路＞
回避とは、経由地の逆であり、この道路リンクは通行しないで欲しいという指定である。
【００４１】
規制は、我々の常識通り、道路に対して課せられる種々の規制を意味する。規制に対しては、色々なパラメータが指定可能である。規制に対して指定可能なパラメータを、表６に示す。
【００４２】
【表６】
2004101447.tif 000008
【００４３】
さて、上記の説明より、「回避＝時間的に常時有効である通行禁止」とも解釈出来る。即ち、回避と規制は似たような概念にも見える。しかし、本質的にこの両者は、似て非なる概念である。その違いを、表７に示す。
【００４４】
【表７】
2004101447.tif 000009
【００４５】
最後に、迂回路とは、回避、規制に出会った時に考える逃げ道を意味する。
【００４６】
＜長距離と短（近）距離＞
最適ルート探索においては、出発地と目的地の間の距離が長いと長距離、短いと短距離（場合によっては近距離と呼ぶこともある）と呼んでいる。ただし、長距離と短距離の間には、例えば５０ｋｍ以上は長距離と言うような、明確な切り分け基準が存在するわけではない。また、長距離探索の場合は、ルートが通過するノード数が多くなるので、何の工夫もしない場合は探索が非常に遅くなる。従って、本実施形態における長距離探索の場合は、中間部では幹線しか走行しない等の仮定、工夫をしている（中間部ルート探索）。
【００４７】
＜２次メッシュ、図郭＞
最適ルート探索の際に用いられる道路データは、オリジナル（初期）の状態では、２次メッシュと呼ばれる区画単位にファイル分けされている。ここで２次メッシュとは、緯度経度平面上における区画である。本実施形態において、図９に示すように、２次メッシュは経度７．５分、緯度５分の区画で表される。また、図郭（辺）とは、２次メッシュの境界を構成する４つの辺である。
【００４８】
＜ノード数ＤＢ＞
本実施形態においては、Ｇメッシュ毎のノード数のデータベース（以下、ＤＢと呼ぶ。）が存在する。Ｇメッシュとは、上述の２次メッシュ１つを１つ又は複数の区画に更に分割したメッシュであり、ノード数ＤＢには、Ｇメッシュ内のノード数がＧメッシュ毎に記録されている（図１０）。このノード数ＤＢは、主に探索範囲を決める際に用いられる。
【００４９】
＜探索モード＞
＜基本定義＞
次に、本実施形態における探索モードの基本定義について説明をする。
【００５０】
最適ルート探索においては、いくつかの探索手法が存在し、これらの探索手法は選択が可能である。この選択は手動（操作者が明示して指定する）の場合もあれば、自動（計算機が自動的に判断する）の場合も存在する。通常、探索手法毎に得られる最適ルートは、微妙に異なる。しかし、結果として、違いが無いケースも有り得る。この種々の探索手法及びそれに応じた探索の流れを、探索モードと呼んでいる。まず、基本的な探索モードについて説明する。
【００５１】
▲１▼　完全最適解モード：細分化幹線道路ネットワーク、集約化幹線道路ネットワークは一切使わずに、全体道路ネットワークのみを用いて、真に最適なルートを求めるモードである。探索精度は最高であるが、探索速度は、特に長距離の場合非常に遅くなる。
【００５２】
▲２▼　細分化幹線長距離走行モード：出発地と目的地の周辺では全体道路ネットワークを走行し、両者の間では細分化幹線道路ネットワークを走行する前提の元で、最適なルートを求めるモードである（図１１参照）。細分化幹線道路ネットワークについては、同時に回避、規制も考慮出来る。
【００５３】
▲３▼　集約化幹線長距離走行モード：細分化幹線長距離走行モードと基本的に類似している。出発地と目的地の周辺では全体道路ネットワークを走行し、両者の間では集約化幹線道路ネットワークを走行する前提の元で、最適なルートを求めるモードである（図１１参照）。回避、規制は分断された個々の道路リンクに対して定義されるので、集約化幹線道路ネットワークについては、同時に回避、規制をデータ構造上（互いにつながっているので）考慮出来ない。
【００５４】
＜集約化幹線長距離走行モードにおける回避、規制への対処法＞
次に、集約化幹線長距離走行モードにおける回避、規制への対処法に関するモードを説明する。上述した通り、集約化幹線道路ネットワークについては、同時に回避、規制はデータ構造上考慮出来ないので、別途、迂回路の探索処理が必要である。この迂回路の探索については、以下の２つのモードが存在する。
【００５５】
▲１▼　全体道路迂回走行モード：一旦、回避、規制を考慮せずに集約化幹線長距離走行モードを実行する。次に、回避、規制を迂回路探索仮定を適用して解決する。この時、迂回路は、全体道路ネットワークレベルで探索する。
【００５６】
▲２▼　細分化幹線迂回走行モード：基本的に、全体道路迂回走行モードと類似しているが、迂回路を探索する道路レベルが細分化幹線道路ネットワークである点が異なる。両者の違いを、図１２に示す。
【００５７】
また、上述の探索モードを要約すると、表８になる。
【００５８】
【表８】
2004101447.tif 000010
【００５９】
＜非完全最適解モードに導入されている仮定＞
非完全最適解モードの解法は、多かれ少なかれ何らかの仮定に基づいている。これらの仮定によって初めて非完全最適解モードの諸法は、理論的根拠を与えられる。ここでは、その仮定についてまとめる。
【００６０】
▲１▼　長距離走行仮定：出発地或いは目的地の周辺の範囲（以後、全体道路探索範囲と呼ぶ）から外に出る場合は、そこから先は幹線道路だけを走行する。集約化幹線長距離走行モードと細分化幹線長距離走行モードの根底には、この仮定が存在する。尚、全体道路探索範囲の決め方であるが、これを決めるのが後述するＮｏｄｅＳＧＭｉｎであり、具体的なその手法については、後述する「プライオリティ」を参考にされたい。また、集約化幹線長距離走行モードと細分化幹線長距離走行モードにおいて、同一のＮｏｄｅＳＧＭｉｎが与えられた時、即ち同一の全体道路探索範囲が与えられた時に、どのノードまで探索されるかを具体的に示すと、図１３を得る。ここで、集約化幹線長距離走行モードにおいて、Ｎ３Ｎ５（非幹線リンク）がＮＧとなっている。Ｎ３Ｎ５は、全体道路探索では探索されているが、集約化幹線道路を走る場合には幹線上ノードＮ５が見えないので、結果として無視されることを表している。図１３において、Ｎ５が幹線ノードであるならば、Ｎ３Ｎ５（非幹線リンク）はＯＫとなる。
【００６１】
▲２▼　迂回路探索仮定：集約化幹線道路に対しては、データ構造上の理由より、直接的には回避、規制を考慮出来ない。そこで、一旦、回避、規制を考慮せずに（無いものと考えて）最適ルートを求め、次に回避、規制の周辺において迂回路を探索し、発見された迂回路と元の最適ルートを統合する。このようにして求めたルート（それは必ずしも真の最適ルートでは無いかもしれないが）を最適ルートと考えて良いという仮定が、迂回路探索仮定である。図示すると、図１４の通りである。
【００６２】
＜使い分けフロー＞
上記の探索モードが実際にどう使い分けられているかというフロー図を、図１５に示す。
【００６３】
＜プライオリティ＞
最適ルート探索においては、相反する２つの価値観が求められる。それは、探索精度と探索速度（パフォーマンス）である。探索精度を上げる、つまりより厳密な最適性を求めようとすると、当然探索速度は落ち、レスポンスが悪くなる。今日の多くの既存の最適ルート探索エンジンは、多かれ少なかれ何らかの仮定、デフォルメを行なうことで、探索の高速性を維持している。探索速度が遅いと製品として成立し得ないからである。このことは、当然本実施形態の最適ルート探索モジュールについても当てはまり、即ち何らかの情報を元に探索をある程度の範囲内で切っている。さて、この探索精度と探索速度という相反する２つの価値観のどちらをどの程度優先するかという選択、設定パラメータを、プライオリティ（パラメータ）と呼んでいる。
【００６４】
このプライオリティは、本実施形態の最適ルート探索モジュールにおいてはノード個数を用いている。プライオリティとしてのノード個数には、表９の４種類が存在する。
【００６５】
【表９】
2004101447.tif 000011
【００６６】
以下では、ＮｏｄｅＳＧＭｉｎを例に説明する。非完全最適解モード（表８参照）では、出発地周辺において、幹線（上）ノード（これ以降、幹線（上）ノードは、幹線ノード又は幹線上ノードを意味する）を探索する。幹線（上）ノードを探し出せば、そこからは幹線を走行するので、高速に探索が可能であると言う発想である。ここから先は、集約化幹線長距離走行モードを例として説明する。集約化幹線長距離走行モードの場合は、幹線ノードのみを探索するのに対して、細分化幹線長距離走行モードでは、幹線上ノードも併せて探すと言う点が違うだけで、ＮｏｄｅＳＧＭｉｎの意味は、両者とも基本的には一緒である。さて、幹線ノードとは、幹線道路のレベルでノードとして認識されるノードであり（上述の「３種類の道路ネットワーク」参照）、図１６を例にすると、Ｎ１〜Ｎ８がこれに該当する。そして、探索速度を優先する余り、リンク上制御点Ｐ１から出発して一番近いＮ１を幹線ノードとして発見し、そこから幹線道路のみを走行すると、結果として、Ｐ１→Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５→Ｎ８というルートを辿る。しかし、このルートは明らかに遠回りであり、実際には、Ｐ１→Ｍ１→Ｎ６→Ｎ７→Ｎ８の方が近道である。更に、明らかに近いのは、Ｐ１からＮ１を経てから北に向かい、△そしてＮ４、Ｎ５、Ｎ８と辿るルートである。このルートならば、無駄が発生しない。このことより、最適解を求めようとすると、それなりに広い範囲に渡って幹線ノードを探索しなければならないことが分かる。そして、この「それなりに広い範囲」を定義するのに、ノード数を使用するのである。具体的には、このＮｏｄｅＳＧＭｉｎは、「出発地のリンク上制御点からスタートして、ＮｏｄｅＳＧＭｉｎ個の全体道路のノードを探索し終えるまでは、幹線（上）ノードを探す。」と言うロジックの中で使用される。これにより、ＮｏｄｅＳＧＭｉｎを多くとればとるほど、発見される幹線ノードが、Ｎ１、Ｎ６、そしてＮ４（△を経て）というように増加し、それだけ解の精度が向上する。
【００６７】
出発地付近での全体道路の探索範囲を例にとって、その範囲の決め方を図示すると、図１７を得る。
【００６８】
ＮｏｄｅＤｅｔｏｕｒＭｉｎは、ＮｏｄｅＳＧＭｉｎと同様のパラメータであり、回避、規制に対して迂回路を探索する際に、探索する範囲を規定するノード数である。
【００６９】
一方、ＮｏｄｅＡｃｃｕＭａｘとＮｏｄｅＤｅｔｏｕｒＭａｘは、末尾がＭａｘと共通していることからも推察される通り、似た意味を持っている。ＮｏｄｅＤｅｔｏｕｒＭｉｎとＮｏｄｅＳＧＭｉｎの末尾がＭｉｎであるコンビが、「最低限これだけは探索してくれ」と言う、言わば下限を規定するノード数であったのに対し、「これ以上は探索しなくて良い」と言うノード数である。具体的には、ＮｏｄｅＡｃｃｕＭａｘは完全最適解の自動判断１（図１５参照）において、これ以上探すならば、完全最適解は諦めてくれと言う上限を規定する。ＮｏｄｅＤｅｔｏｕｒＭａｘは、回避、規制に対して迂回路を探索する際に、これ以上探すならば、迂回路探しは諦めてくれと言う上限を規定する。
【００７０】
＜回避、規制の統合＞
集約化幹線長距離走行モードにおいて、互いに近接する回避、規制は統合されてから迂回路探索が行なわれる。これは、個別に迂回路を探すと効率の悪いルートになる可能性があるからである。感覚的な言い方をすると、回避、規制がお互いに近い場合に、この統合を行なっている（図１８参照）。実際には、単なる空間距離で統合の可否を判断しているのではなく、ノード数ＤＢを用いて周囲のノード数を見ながら判断している。
【００７１】
＜データファイル＞
利用されているデータファイルの内容と構成を、図１９に示す。
【００７２】
＜３種類の道路ネットワークの使い分け＞
各々異なる長短所を持つ３種類の道路ネットワーク（全体道路、細分化幹線、集約化幹線）を提案し、その各々を状況により適宜使い分ける。この使い分け方を、表１０に示す。
【００７３】
【表１０】
2004101447.tif 000012
【００７４】
＜ノード数の利用＞
探索精度とレスポンスのバランスを取るため、ノード数を調整のための基準変量として利用する。これにより、ノード数を増やすことで探索の精度を上げ、減らすことで探索の精度を落として、探索を高速化出来る等の制御が可能である。
【００７５】
＜図郭ノード＞
本実施形態において、図郭ノードの記述方法として、互い違い法を採用した（図２０）。その理由は、以下の通りである。
【００７６】
完全一致法は、一見理想的な方法に見えるが、実はリンクの座標を記述する時にこれまでの規則（２次メッシュ毎に独立したデータとして扱う）と矛盾を引き起こす。長さ０リンク法は、リンクの本数が増えるので、データ量をそれだけ増やし、パフォーマンスを低下させる危険性が存在する。よって、互い違い法を採用する。
【００７７】
ただし、互い違い法の場合、２つの図郭ノードが物理的に一致していることを記述する必要性が生じる。よって、図郭ノード対応テーブルを導入する。
【００７８】
＜回避・規制の統合＞
互いに近接する回避・規制を、柔軟に判断しながら必要に応じて統合して行く。この統合の際に、ノード数を利用する。これにより、効率的なルートを発見することが出来る。
【００７９】
＜基本探索モード別処理フロー＞
プログラムの内部的な処理の流れを言うと、経由地がある場合は、経由地が無い場合の出発地〜目的地の探索が複数回繰り返されているだけである（表４参照）。そこで、本実施形態では、経由地が無い場合に対して、基本の探索モード別に処理フローを以下に記す。
【００８０】
▲１▼　完全最適解モード
完全最適解モードの探索フローを、図２１に示す。まず、出発地側の入力された指示制御点よりリンク上制御点を求める（ステップＳ２１０１）。次に、目的地側の入力された指示制御点よりリンク上制御点を求める（ステップＳ２１０２）。また、指示制御点を入力せずに、直接リンク上制御点を入力するようにしても良い。このようにして、出発地側及び目的地側のリンク上制御点を設定する。
【００８１】
次に、回避、規制を同時に考慮しながら全体道路で探索を行ない（ステップＳ２１０３）、最終結果を得る（ステップＳ２１０４）。
【００８２】
▲２▼　細分化幹線長距離走行モード
細分化幹線長距離走行モードにおいて、図２２に示す探索フローに従った処理を実行する。
【００８３】
出発地／目的地側の入力された指示制御点よりリンク上制御点を求める（ステップＳ２２０１、Ｓ２２０５）。また、指示制御点を入力せずに直接リンク上制御点を入力するようにしても良い。このようにして、出発地側及び目的地側のリンク上制御点を設定する。
【００８４】
次に、出発地／目的地側の全体道路探索範囲の設定を行なう（ステップＳ２２０２、Ｓ２２０６：図１７及び後述するアルゴリズムの補足を参照）。
【００８５】
リンク上制御点からスタートし、全体道路探索範囲内で全体道路を探索し、範囲内で到達出来る限りの幹線上ノード及び幹線ノードを抽出する（ステップＳ２２０３、Ｓ２２０７）。同時に、そこに至るまでのコスト（時間と距離を総称して以後コストと呼ぶ）を計算する。また、図２３に示す通り、便宜上これらの探索を各々Ｆｒｏｎｔ探索（出発地側探索）、Ｂａｃｋ探索（目的地側探索）と呼ぶ。尚、ステップＳ２２０７においては、回避、規制は考慮しなくて良い。それは、本探索の目的があくまで目的地周辺の幹線（上）ノードを探すことにあるからであり、また同時に逆方向の探索中に正確な回避、規制の適用は不可能だからである。
【００８６】
前ステップで抽出された幹線（上）ノードの集合を、各々「出発地側幹線（上）ノードリスト」、「目的地側幹線（上）ノードリスト」と呼ぶ（ステップＳ２２０４、Ｓ２２０８）。これらは、各々図２３のＳ１〜Ｓ４及びＧ１〜Ｇ４が該当する。図２３に示すのはあくまでも一例であり、Ｓ１が必ずＧ１に対応するものではない。例えば、Ｍｉｄ探索において、Ｓ２のみがＧ１〜Ｇ４に対応する可能性もある。
【００８７】
「出発地側幹線（上）ノードリスト」を出発地とし、そこに至るまでのコストを考慮しつつ、「目的地側幹線（上）ノードリスト」に至るまでを細分化幹線道路ネットワークを用いて探索する（ステップＳ２２０９）。この時、回避、規制を同時に考慮する。便宜上、この探索をＭｉｄ探索（中間部ルート探索）と呼ぶ．Ｍｉｄ探索により、「目的地側幹線（上）ノードリスト」までは到達できる。
【００８８】
再度、「目的地側幹線（上）ノードリスト」から目的地側のリンク上制御点まで、全体道路で探索を行なう（ステップＳ２２１０）。この時、回避、規制は考慮する。そして、細分化幹線長距離走行モードにおける探索結果を得る（ステップＳ２２１１）。
【００８９】
ここでは、Ｆｒｏｎｔ探索及びＢａｃｋ探索の両方を行なう例を示したが、必ずしもＦｒｏｎｔ探索及びＢａｃｋ探索の両探索を行なう必要はない。例えば、探索を開始したいとき、既に高速道路のような幹線リンク上にいる場合は、Ｆｒｏｎｔ探索及びＢａｃｋ探索を行なう必要はない。状況に応じて、Ｆｒｏｎｔ探索又はＢａｃｋ探索のいずれかの探索のみを行なうこともある。
【００９０】
この場合、Ｍｉｄ探索（中間部ルート探索）は、出発地側リンク上制御点から目的地側幹線（上）ノードまでの探索、または出発地側幹線（上）ノードから目的地側リンク上制御点までの探索となる。
【００９１】
従って、使用者の意図に応じて、全体道路探索範囲の設定をするかどうかを選択できるので、自由度が増す。
【００９２】
▲３▼　集約化幹線長距離走行モード
集約化幹線長距離走行モードの探索フローは、以下の２ステップに分かれる。この探索フローの根底には、「非完全最適解モードに導入されている仮定」で述べた「迂回路探索仮定」が存在する。
【００９３】
ステップ１（基本ルートの探索）：回避、規制を全く考慮せず、兎に角、出発地から目的地までの最適ルートを探索する。
【００９４】
ステップ２（迂回路の統合）：上記で求めた基本ルートに対して回避、規制を適用し、迂回路を求め、求めた迂回路を基本ルートに統合する。
【００９５】
以下、このステップ別に解説する。
【００９６】
＜ステップ１：基本ルートの探索＞
ステップ１については、基本的には細分化幹線長距離走行モードの探索フローに酷似している。以下では、図２２及び図２３において異なる点のみ述べる。
【００９７】
▲１▼　「出発地側幹線（上）ノードリスト」は、「出発地側幹線ノードリスト」である。
【００９８】
▲２▼　「目的地側幹線（上）ノードリスト」は、「目的地側幹線ノードリスト」である。
【００９９】
▲３▼　ステップＳ２２０３、Ｓ２２０７で抽出するのは、「幹線上ノード及び幹線ノード」でなく「幹線ノード」のみである。
【０１００】
▲４▼　ステップＳ２２０９で探索するのは、細分化幹線でなく集約化幹線道路である。
【０１０１】
▲５▼　回避、規制：どの工程においても一切考慮しない。
【０１０２】
▲６▼　行き戻り：Ｆｒｏｎｔ探索とＭｉｄ探索結果の統合及びＭｉｄ探索結果とＢａｃｋ探索結果の統合の際に、行き戻りが発生する可能性があるので、消去する。例えば、図２４で、Ｒ１がＦｒｏｎｔ探索の成果のルート、Ｒ２がＭｉｄ探索の成果のルートとすると、図に示す行き戻り部分（重複部分）が発生する可能性があるので、これを消去する。このとき同時に、コストの再計算を行なわなければいけない。
【０１０３】
＜ステップ２：迂回路の統合＞
次に、回避、規制が無いという理想状態に対して求めた最適ルートに対して、回避、規制を適用して迂回路を求め、その迂回路を元の理想のルートに統合する。処理フローを、図２５に示す。
【０１０４】
まず、出発地側から順に回避、規制を取り出しつつ、逐次行なう（ステップＳ２５０１）。
【０１０５】
全体道路によって回避、規制のグループ化を行なう（ステップＳ２５０２）。グループ化は、図２６に示すように、回避、規制が設定されているリンクに対する迂回路探索範囲が交わるか否かで判断する。交わる場合は、統合して１グループとみなす。ここで迂回路探索範囲の計算方法は、後述する迂回路探索範囲の設定（図２８）を参照されたい。
【０１０６】
迂回路探索範囲に基づいて、図２７に示す通り、迂回路探索の出発地、目的地ノードを決める（ステップＳ２５０３）。
【０１０７】
前ステップで求めた迂回路探索の出発地、目的地ノードを元に、全体道路で最適ルート探索を行なう（ステップＳ２５０４）。この時、回避、規制も考慮する。
【０１０８】
探索が成功したか否かを判定する。成功していたらステップＳ２５０６へ、失敗していたらステップＳ２５０７へ進む（ステップＳ２５０５）。
【０１０９】
Ｓ２５０５で探索が成功していたら、求めた迂回路を元のルートに統合する（ステップＳ２５０６）。この時、行き戻り処理を行なう。
【０１１０】
ステップＳ２５０５で探索が失敗していたら、細分化幹線道路を用いて、ステップＳ２５０２〜Ｓ２５０４と同様の処理を行なう（ステップＳ２５０７）。全体道路でなく、細分化幹線を用いるためノード数が減少し、より広い範囲を探索することが可能になり、探索が成功する可能性が高まる。
【０１１１】
そして、細分化幹線道路を用いた探索が成功したか否かを判定する（ステップＳ２５０８）。成功していたらステップＳ２５０６へ、失敗していたらステップＳ２５０９へ進む。
【０１１２】
つまり、迂回路探索仮定を用いている限り、最適ルートが求められない（裏を返すと、回避、規制が夥しくあるので、ステップ１で求めた基本ルートに合理性が最早ない）、と考えて細分化幹線長距離走行モードへ遷移する（ステップＳ２５０９）。
【０１１３】
全体道路又は細分化幹線道路を用いた迂回路の探索が成功していた場合は、ステップＳ２５０６を経てステップＳ２５０１に戻る。すべての回避、規制を処理した場合は、最終結果が得られる（ステップＳ２５１０）。
【０１１４】
＜アルゴリズムの補足＞
＜全体道路探索範囲の設定＞
全体道路探索範囲設定の処理フローの概念を示すと、図１７になる。具体的な処理フローは、以下の通りである。
【０１１５】
▲１▼　出発地（リンク上制御点）を中心として、幅（両側合計で）Ｇメッシュ１個分の領域内に中心が含まれるＧメッシュ（以後、初期値Ｇメッシュと呼ぶ）を求める。
【０１１６】
▲２▼　初期値Ｇメッシュを、「全体道路探索範囲（Ｇメッシュ群）」の初期値として登録する。
【０１１７】
▲３▼　「全体道路探索範囲」に含まれるノード数の合計がＮｏｄｅＳＧＭｉｎを超えた場合は、その時点（超えた直後）での「全体道路探索範囲」が求める結果であるので本処理を終了する。
【０１１８】
▲４▼　そうでないならば、周囲にＧメッシュ１個分だけ「全体道路探索範囲」の拡張を行なう。
【０１１９】
▲５▼　「全体道路探索範囲」に該当するＧメッシュ群に含まれるノード数の合計がＮｏｄｅＳＧＭａｘを超えたならば、探索不能として全処理を終了する。
【０１２０】
▲６▼　▲３▼に戻る。
【０１２１】
＜迂回路探索範囲の設定＞
迂回路探索範囲設定の処理フローは、「全体道路探索範囲の設定」と共通である。違いは、以下の４点である。
【０１２２】
▲１▼　核となる線分群は、回避、規制リンクをノードの座標のみ採用して折れ線近似して求める。
【０１２３】
▲２▼　初期値Ｇメッシュが核となる線分群の周囲に、Ｇメッシュ１個分だけ拡幅した領域を含むＧメッシュ群であること。
【０１２４】
▲３▼　「迂回路探索範囲（Ｇメッシュ群）」の形状が不規則であるため、Ｇメッシュ１個分だけ範囲を拡張する際に注意を要すること（図２８参照）。
【０１２５】
▲４▼　ＮｏｄｅＳＧＭｉｎ、ＮｏｄｅＳＧＭａｘの代わりに、ＮｏｄｅＤｅｔｏｕｒＭｉｎ、ＮｏｄｅＤｅｔｏｕｒＭａｘが用いられること。
【０１２６】
以上の述べたように、本発明によると、▲１▼精度とレスポンスというお互いに矛盾する要件を満たす最適ルートが算出できること（高品質）、▲２▼事前準備インデックスデータを無効にする回避・規制情報等の雑音データに対しても柔軟に対応出来ること（柔軟性）、▲３▼用途、目的に応じて多様な特徴を持った最適ルートが算出可能であること（多様性）、等の効果が得られる。
【０１２７】
＜指定可能パラメータ＞
次に、本実施形態で設定可能なパラメータを列挙する。
（）内は関連するプロパティ名又はその一部を意味する。
【０１２８】
＜指示制御点＞
出発地（Ｓｔａｒｔ）：出発地の座標
目的地（Ｇｏａｌ）：目的地の座標
経由地（Ｖｉａ）：経由地の座標（任意点数設定可、順番指定の必要有り）
【０１２９】
＜モードの制御＞
厳密性の選択（Ａｃｃｕｒａｃｙ）：完全最適解モードか、非完全最適解モードか、或いはその両者を自動判断で切り分けるかと言う選択。「探索モード」参照。
【０１３０】
長距離走行手法の選択（ＬｏｎｇＤｒｉｖｅ）：細分化幹線長距離走行モードか、或いは集約化幹線長距離走行モードかと言う選択。「探索モード」参照。
【０１３１】
＜プライオリティ＞
上述の４つのノード数である（表９参照）。
【０１３２】
＜回避、規制＞
回避（Ｄｅｔｏｕｒ）：回避を設定する道路リンク
規制（Ｒｅｇｕ）：規制を設定する道路リンク及び「回避、規制、迂回路」で説明した規制に付随するパラメータ
【０１３３】
＜その他一般＞
（１）出発日付（ＤａｔｅＳｔａｒｔ）：出発する日時、規制に対して開始、終了時間が設定可能なので、結果としてこのパラメータが必要である。
（２）最適化目的（Ｏｐｔｉｍｉｚｅ）：最短時間を目指すか、最短距離を目指すかの何れであるかの選択
以下の（３）から（６）までは、リンク上制御点を求める工程（ＳｅａｒｃｈＣＰｏｉｎｔ）と最適ルート探索を行なう工程（ＳｅａｒｃｈＲｏｕｔｅ）毎に２つ存在する。
（３）走行可不可−有料道路（ＥｎａｂｌｅＴｏｌｌ）：有料道路を走行して良いか否かの選択
（４）走行可不可−自動車専用道路（ＥｎａｂｌｅＣａｒＯｎｌｙ）：自動車専用道路を走行して良いか否かの選択
（５）走行可不可−高速自動車国道（ＥｎａｂｌｅＨｉｇｈｗａｙ）：高速自動車国道を走行して良いか否かの選択
（６）走行可不可−道路幅員（ＥｎａｂｌｅＷｉｄｔｈ）：道路幅員ランク別の走行して良いか否かの選択。ここで道路幅員ランクとは、幅員１３．０ｍ以上、幅員５．５ｍ以上１３．０ｍ未満、幅員３．０ｍ以上５．５ｍ未満、幅員３．０ｍ未満の４ランクである。
（７）有効無効−規制（ＥｎａｂｌｅＲｅｇｕ）：定義された規制情報を考慮するか否かの選択
（８）有効無効−一方通行定義（ＥｎａｂｌｅＯｎｅＷａｙ）：道路の一方通行定義を考慮するか否かの選択。人や緊急車両（救急車、消防自動車等）は、道路の一方通行定義を無視するであろうから、このような切り替え設定が存在する。
（９）走行主体（Ｔｒａｖｅｌｅｒ）：走行するのは人か車かの選択。規制対象に人か車かの２つのタイプが存在するので、どちらのタイプの規制が適用されるかをここで指定する。また、自動車通行不可のリンクに対しても、走行主体が人の場合は通行して良いと言う違いもある。
（１０）速度定義タイプ（ＶｅｌｏｃｉｔｙＴｙｐｅ）：速度ランク（道路を走行可能速度別に分類したときのランク、表１１参照）別に道路の走行可能速度を指定するか、それとも全道路共通の一定速度を指定するかの選択。最適化目的が最短距離である場合は、無効なパラメータである。
【０１３４】
【表１１】
2004101447.tif 000013
【０１３５】
（１１）速度ランク別の速度（ＶｅｌｏｃｉｔｙＴａｂｌｅ）：道路の速度ランク（表１１参照）別の走行可能速度。速度定義タイプが全道路共通の一定速度である場合は、無効なパラメータである。
（１２）全道路共通の一定速度（ＶｅｌｏｃｉｔｙＵｓｅｒ）：速度定義タイプが全道路共通の一定速度である場合に有効で、その全道路に共通な一定の走行速度である。
（１３）リンク上制御点探索半径開始値：表５参照。
（１４）リンク上制御点探索半径終了値：表５参照。
（１５）リンク上制御点探索半径増分値：表５参照。
（１６）イベント発生間隔（Ｉｎｔｅｒｖａｌ）：イベントを発生させる間隔である。処理全体に対する割合で表現する。
【０１３６】
〔第２の実施形態〕
次に、本実施形態における最適ルート探索装置の構成及び動作について説明する。最適ルート探索装置は以下の表１２及び図２９に示すように、地図表示装置２９０１、パラメータ入力装置２９０２、中央演算装置２９０３、最適ルート表示装置２９０４、ネットワークデータ記憶装置２９０５、形状データ記憶装置２９０６とから構成される。
【０１３７】
【表１２】
2004101447.tif 000014
【０１３８】
図２９において、矢印の向きはデータの流れを示す。ここで、地図表示装置２９０１と最適ルート表示装置２９０４は別体で示してあるが、同一の表示装置でも良い。
【０１３９】
始めに、地図表示装置２９０１上で、操作者により地図を確認しながら指示制御点（出発地、目的地）が入力される。そして、この指示制御点に関する情報が中央演算装置２９０３に入力される。また、上述の各種パラメータの変更等がある場合にはパラメータ入力装置２９０２で各種パラメータの選択及び入力ができる。また、パラメータ入力装置２９０２により探索モードの設定をする。
【０１４０】
このようにして、入力及び設定された情報は中央演算装置２９０３により各種の演算処理が行なわれる。指示制御点設定部２９１０は、地図表示装置２９０１を通して指示制御点を操作者に入力させる流れを制御する。
【０１４１】
次に、指示制御点から実際に探索を開始または終了するリンク上制御点を求める。まず、ネットワークデータ記憶装置２９０５からネットワークデータ読み込み部２９１１を介して道路のネットワーク構造を示すネットワークデータを読み込む。そして、形状データ記憶装置２９０６から形状データ読み込み部２９１２を介して道路の形状データを読み込む。読み込まれたネットワークデータと形状データ及び設定された指示制御点を用いてリンク上制御点探索部２９１３によりリンク上制御点を求める。具体的には既に述べたように、指示制御点を中心として周囲に仮想の矩形を発生させ、この矩形を段々膨張させることで、探索範囲を広げて行くことにより求める（図８）。
【０１４２】
この様にしてリンク上制御点が求められた後に、最適ルート探索パラメータ指定部２９１４により管理された各種パラメータとリンク上制御点とを用いて最適ルート探索部２９１５で最適ルートを探索する。そして、探索された最適ルートを最適ルート表示装置２９０４で表示するために、最適ルート表示用データ作成部２９１６でルートの座標が構築される。中央演算処理装置２９０３における各部の説明を表１３に示す。
【０１４３】
【表１３】
2004101447.tif 000015
【０１４４】
〔第３の実施形態〕
最適ルート探索におけるリンク上制御点の指定を最近隣の１つとしたとき、図３０（ａ）に示すように、最近隣の道路が一方通行である場合は、求められるルートが一旦先のＵターン路、またはインターチェンジまで行ってから逆走するルートとになる。また、この結果、図３１（ａ）及び図３１（ｂ）に示す通り、出発地と目的地を反転させた場合に求められるルートが必ずしも対称にならないことがある。これらの事象の原因は、リンク上制御点として最近隣の１点のみを用いてルート探索を行なっている場合に起こることにある。そこで、本実施形態においては、この辺が出発地または目的地と言う漠然とした意識を支援する機能を提供する。
【０１４５】
これにより、図３０（ｂ）に示すように、Ｕターンしない経路を探索することができる。これにより、図３１（ａ）及び図３１（ｃ）に示すように対称な最適ルートを探索することができる。
【０１４６】
次に、余分な迂回をせず、対称性を保った最適ルートを求めるための処理手順及びパラメータについて説明する。
【０１４７】
▲１▼　最初に人間により指示された点（以後、指示制御点と命名する）を元にして、距離的に近い順に、複数のリンク上制御点（図３２のＱ１、Ｑ２、Ｑ３）を求める。
【０１４８】
▲２▼　どの位まで離れたリンク上制御点を求めるかはＲａｎｋＤｉｓｔａｎｃｅパラメータにより制御する（図　３２参照）。
【０１４９】
▲３▼　この様にして、複数個のリンク上制御点を出発地側と目的地側とで求める。
【０１５０】
▲４▼　出発地側のリンク上制御点と目的地側のリンク上制御点の組み合わせに対して、最適ルート探索を行なう。この最適ルート探索の処理内容は、今まで説明して来た通りである。
【０１５１】
▲５▼　探索の結果、最大で目的地側のリンク上制御点の個数に等しい本数の最適ルートが求められる。このうち、最小コストのルート（１本のみ）を抽出する。例えば、図３３ではＳ１〜Ｓ３とＧ１〜Ｇ４の組み合わせで合計３×４＝１２本の最適ルートから、一番最適なルート１本を抽出して答えとする（図３３の例ではルートＳ１〜Ｇ１が選択される）。
【０１５２】
このようにして、余分な迂回をせず、対称性を保った最適ルートを求めることができる。
【０１５３】
〔第４の実施形態〕
本実施例における最適ルート探索において、出発地や目的地（の指示制御点）に隣接している（リンク上制御点がのっている）道路リンクに、道路リンクの走行方向を制御すると言う視点を与える。例えば、図３４において、ルートＡは距離的には短いものの、出発地や目的地（の指示制御点）をルートの右側に見ることになる。一方ルートＢは距離的には遠いものの、指示制御点をルートの左側に見ることが出来る。よって、指示制御点を常に左側に見なければいけないと言う制約条件の元ではルートＢが求める答えである。そこで、本実施例において、道路リンクの走行方向にこの様な制約を課して、ルートＡでなくルートＢを求めることを可能にする。
【０１５４】
この制約を与えるために、当該道路リンクに対して一方通行の設定を行なうと言う対処法が存在する。しかし、この一方通行の指定には図３５に示す問題が存在する。図３５において、道路リンクＬは出発地Ｐ〜目的地Ａの組み合わせでは、右から左にしか行けない一方通行であるが、出発地Ｐ〜目的地Ｂの組み合わせでは、左から右へ行っても構わない。つまり、今必要な走行可能方向の制約条件は、道路リンクＬがリンク上制御点を含む場合にのみ有効にすべきであり、恒常的な交通規制とは異なる概念である。よって、一方通行と言う交通規制の概念を本問題に適用するのには無理があり、それゆえ前記の制約を課すことは出来ない。
【０１５５】
そこで、本実施形態では出発地や目的地に隣接している（リンク上制御点がのっている）道路リンクにおいて、その走行する方向に対して制約を与えた。この制約機能により、図３６に示す様に配置されたゴミ収集ステーションのゴミを収集する際に、常にステーションを左側に臨むような最適ルートを求めることが可能になる。
【０１５６】
これを可能とするため、探索の起点、終点となるリンク上制御点の処理に特徴を持たせる。リンク上制御点がのっている道路リンクの走行方向を意識するとは、単にあるリンク上制御点から出発すれば良い、或いはあるリンク上制御点に到着すれば良いと言う考え方を捨てることである。その替わりに、リンク上制御点を起点または終点として持つ仮想の方向付き道路リンクを導入し、この仮想リンクを探索の起点、終点として処理を行なう。具体的な処理フローは以下の通りである。ここで、仮想と言う用語は、元の道路リンクをリンク上制御点で仮想的に切断しているため、実際のＲｅａｌな道路リンクと区別すると言う理由より用いた。
【０１５７】
▲１▼　出発地側のリンク上制御点を起点として含み、かつ所定の方向条件を満たす走行可能な仮想の方向付き道路リンクを設定する。これ以降、このリンクを出発地側仮想リンク（図３７のＬｓが該当する）と命名する。
【０１５８】
▲２▼　目的地側のリンク上制御点を終点として含み、かつ所定の方向条件を満たす走行可能な仮想の方向付き道路リンクを設定する。これ以降、このリンクを目的地側仮想リンク（図３７のＬｇが該当する）と命名する。
【０１５９】
▲３▼　出発地側仮想リンクを最初の走行可能候補リンクとしてダイクストラ探索を開始する。この後の処理は通常の探索処理である。
【０１６０】
▲４▼　目的地側仮想リンクが走行リンクとして取り出された時点で探索は終了する。この時希望する最適ルートが図３８の様に求められる。
【０１６１】
このような制約を与えることにより、図３６に示す様に配置されたゴミ収集ステーションのゴミを収集する際に、常にステーションを左側に臨むような最適ルートを求めることが可能となった。
【０１６２】
【発明の効果】
以上説明したように、本発明によれば、▲１▼精度とレスポンスというお互いに矛盾する要件を満たす最適ルートが算出できること（高品質）、▲２▼事前準備インデックスデータを無効にする回避・規制情報等の雑音データに対しても柔軟に対応出来ること（柔軟性）、▲３▼用途、目的に応じて多様な特徴を持った最適ルートが算出可能であること（多様性）、を実現した最適ルート探索方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】本発明に係る一実施形態に係わる全体構成を示す図である。
【図２】本発明に係る一実施形態に係わるノードとリンクを示す図である。
【図３】本発明に係る一実施形態に係わる３種類の道路ネットワークを示す図である。
【図４】本発明に係る一実施形態に係わる３種類の道路ネットワークの定義を示す図である。
【図５】本発明に係る一実施形態に係わる経由地無しの最適ルート探索を示す図である。
【図６】本発明に係る一実施形態に係わる経由地有りの最適ルート探索を示す図である。
【図７】本発明に係る一実施形態に係わる指示制御点とリンク上制御点を示す図である。
【図８】本発明に係る一実施形態に係わるリンク上制御点の探索矩形の拡張を示す図である。
【図９】本発明に係る一実施形態に係わる２次メッシュと図郭を示す図である。
【図１０】本発明に係る一実施形態に係わるノード数ＤＢを示す図である。
【図１１】本発明に係る一実施形態に係わる細分化幹線長距離走行モードと集約化幹線長距離走行モードのイメージを示す図である。
【図１２】本発明に係る一実施形態に係わる対象道路レベルによる迂回路の違いを示す図である。
【図１３】本発明に係る一実施形態に係わる探索されるノードを示す図である。
【図１４】本発明に係る一実施形態に係わる迂回路探索仮定を示す図である。
【図１５】本発明に係る一実施形態に係わる探索モード分岐部を示す図である。
【図１６】本発明に係る一実施形態に係わる出発地周辺での幹線ノードの探索を示す図である。
【図１７】本発明に係る一実施形態に係わる出発地付近での全体道路探索範囲の決め方を示す図である。
【図１８】本発明に係る一実施形態に係わる回避、規制の統合を示す図である。
【図１９】本発明に係る一実施形態に係わるデータファイルを示す図である。
【図２０】本発明に係る一実施形態に係わる図郭ノードの扱い（全体道路、細分化幹線道路）を示す図である。
【図２１】本発明に係る一実施形態に係わる完全最適解モードの探索フローを示すフローチャートである。
【図２２】本発明に係る一実施形態に係わる細分化幹線長距離走行モードの探索フローを示すフローチャートである。
【図２３】本発明に係る一実施形態に係わる細分化幹線長距離走行モードの模式図である。
【図２４】本発明に係る一実施形態に係わる行き戻りの削除を示す図である。
【図２５】本発明に係る一実施形態に係わる集約化幹線長距離走行モードにおける迂回路の探索フローを示すフローチャートである。
【図２６】本発明に係る一実施形態に係わる回避、規制のグループ化を示す図である。
【図２７】本発明に係る一実施形態に係わる迂回路探索の出発地、目的地ノードの決定に関する図である。
【図２８】本発明に係る一実施形態に係わるＧメッシュ１個ずつの拡張を示す図である。
【図２９】本発明に係る最適ルート探索装置の構成を示す図である。
【図３０】本発明に係る最適ルートの探索例を示す図である。
【図３１】本発明に係る最適ルートの非対称及び対称な探索例を示す図である。
【図３２】本発明に係る一実施形態に係わるＲａｎｋＤｉｓｔａｎｃｅを示す図である。
【図３３】本発明に係る一実施形態に係わる最小コストの最適ルートの選択を示す図である。
【図３４】本発明に係る一実施形態に係わる走行方向の制御を示す図である。
【図３５】本発明に係る一実施形態に係わる任意に一方通行の設定をした場合の限界を示す図である。
【図３６】本発明に係る一実施形態に係わる常に左側にゴミ収集ステーションがある場合のゴミの収集経路を示す図である。
【図３７】本発明に係る一実施形態に係わる出発地側仮想リンクと目的地側仮想リンクを示す図である。
【図３８】本発明に係る一実施形態に係わるゴミ収集ステーションを左側に臨む最適ルートを示す図である。
【符号の説明】
２９０１…地図表示装置
２９０２…パラメータ入力装置
２９０３…中央演算装置
２９０４…最適ルート表示装置
２９０５…ネットワークデータ記憶装置
２９０６…形状データ記憶装置
２９１０…指示制御点設定部
２９１１…ネットワークデータ読み込み部
２９１２…形状データ読み込み部
２９１３…リンク上制御点探索部
２９１４…最適ルート探索パラメータ指定部
２９１５…最適ルート探索部
２９１６…最適ルート表示用データ作成部
【図１】
2004101447.tif 000016
【図２】
2004101447.tif 000017
【図３】
2004101447.tif 000018
【図４】
2004101447.tif 000019
【図５】
2004101447.tif 000020
【図６】
2004101447.tif 000021
【図７】
2004101447.tif 000022
【図８】
2004101447.tif 000023
【図９】
2004101447.tif 000024
【図１０】
2004101447.tif 000025
【図１１】
2004101447.tif 000026
【図１２】
2004101447.tif 000027
【図１３】
2004101447.tif 000028
【図１４】
2004101447.tif 000029
【図１５】
2004101447.tif 000030
【図１６】
2004101447.tif 000031
【図１７】
2004101447.tif 000032
【図１８】
2004101447.tif 000033
【図１９】
2004101447.tif 000034
【図２０】
2004101447.tif 000035
【図２１】
2004101447.tif 000036
【図２２】
2004101447.tif 000037
【図２３】
2004101447.tif 000038
【図２４】
2004101447.tif 000039
【図２５】
2004101447.tif 000040
【図２６】
2004101447.tif 000041
【図２７】
2004101447.tif 000042
【図２８】
2004101447.tif 000043
【図２９】
2004101447.tif 000044
【図３０】
2004101447.tif 000045
【図３１】
2004101447.tif 000046
【図３２】
2004101447.tif 000047
【図３３】
2004101447.tif 000048
【図３４】
2004101447.tif 000049
【図３５】
2004101447.tif 000050
【図３６】
2004101447.tif 000051
【図３７】
2004101447.tif 000052
【図３８】
2004101447.tif 000053