ルート決定方法およびデバイス
【課題】 ユーザに提供する余分な詳細情報を減らしてルートを一層容易に理解できるように、従来技術の欠点を改善したルート計算方法およびデバイスを提供することにある。
【解決手段】 本発明は、計算機により地点αと地点βとの間の最適旅程を確立するためのルート計算方法に関し、第一ソースおよび第二ソースの両方に基準を有する少なくとも複数のαノード（Ｎα）のデジタル化されたデータを使用し、各ノードについての第一最適値を決定し、第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、各ノードについての第一最適値を決定し、全対のノードＮα、Ｎβについて、各対のノード（Ｎα、Ｎβ）の第二最適値を決定し、α−βルートの組について、地点αと地点βとの間の最適ノードを決定することからなる。本発明はまた、この方法を実施するデバイスに関する。
【解決手段】 本発明は、計算機により地点αと地点βとの間の最適旅程を確立するためのルート計算方法に関し、第一ソースおよび第二ソースの両方に基準を有する少なくとも複数のαノード（Ｎα）のデジタル化されたデータを使用し、各ノードについての第一最適値を決定し、第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、各ノードについての第一最適値を決定し、全対のノードＮα、Ｎβについて、各対のノード（Ｎα、Ｎβ）の第二最適値を決定し、α−βルートの組について、地点αと地点βとの間の最適ノードを決定することからなる。本発明はまた、この方法を実施するデバイスに関する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の基準ソースを用いて、命令の形態でのルート作成および／またはルート表示の最適化を可能にするルート計算方法に関する。
【背景技術】
【０００２】
近頃は、種々のルート計算方法および幾つかの形式の関連デバイスが良く知られている。２つの形式の補完技術が、これらのツールを大きく普及させることを可能にしている。第一に、ドライバが、その車両をスクリーン上に表示された方向に従って所与の場所に導くことができる搭載型デバイスがある。このようなデバイスは、しばしばＧＰＳ機器と組合されることにより、更に、車両のほぼ正確な場所およびこの場所からのルートの完成が可能である。パソコンで使用するための幾つかのバージョンも存在している。
一方、中央制御型デバイスは、多数の潜在的ユーザに、例えばインターネットのようなネットワークを介してアクセスできる非常に広範囲の可能性を提供する。集中デバイスは、（ユーザへの付加コストがない）規則的データ更新ができ、各ユーザの利用コストを最低にできるという長所がある。ルート計算以外に、プロバイダは、交通予報／推奨情報、ツーリスト情報等の関連サービスをもしばしば提供する。
【０００３】
これらの形式のサービスは現存しているので範囲の拡大は停止していないが、殆どの時間、改善は、ルート計算を可能にする技術に関するものではなく、関連アスペクトに関するものに費やされてきた。機器が着実にパワフルになるにつれて、演算時間の最適化にかなりの進歩がなされ、得られるプレゼンテーション等が改善されている。ルート計算の原理は殆ど進歩しておらず、従って、ときどき、作られるルートのクオリティに影響を与える危険がある幾つかの制限を有している。例えば、既知の形式の方法およびデバイスは、単一の地理的データソースを用いてルートを作成している。前記ソースにより与えられる情報の密度およびクオリティ、および更新される頻度に関係して、ルートは、信頼性の度合いは異なるがほぼ正確に作成される。
例えば、作成されるルートの大部分は、所与の都市領域に出発地点を有し、かつ前記領域内での都市旅程（urban journey）、都市間領域内でのルート部分および再度の都市領域内での目的地点を含んでいる。このようなルートが単一データソースに基いていると考えられる場合には、都市領域の必要精度を得るため、デフォルトにより「大縮尺」形式のソースが使用される。ルートが命令のリストの形態で与えられる場合には、都市旅程部分は、同じ道路等をどれ程の距離だけ続けるかについて、例えば、左折または右折の瞬間から出発して高度に詳細化される。
【０００４】
都市間領域内のルートでは、このような精度は不要でありかつ実際に望まれていない。実際に、例えばこのような主要道路すなわち自動車道のような高速道路に沿って走行するとき、ドライバは、走行すべき道路の形状、従うべき方向等に関する命令に一層よく応答できる。実際に、高速でおよび／または長距離旅程で、「左折し、１００ｍの間まっすぐに走行を続けて右折する」という形式の命令に応答することは困難である。しかしながら、このような命令は、大縮尺地図（large scale map）に一致（一般にあらゆる種類の詳細情報（detail）に富んだ都市領域に一致）するソースでは一般的である。
同様に、ルートが線（ライン）の形態で地図上に表示されるときは、無関係の詳細情報が多過ぎると、どこに居るのかを理解することが困難になってしまう。最終的には、得られるルートプランは長くて、使用が困難なものとなる。
これらの欠点を改善するため、ユーザに提供する余分な詳細情報を減らしてルートを一層容易に理解できるようにすることを目的として、ステップを連鎖(concatenating）させまたは簡単化させたルート計算方法がしばしば使用されている。しかしながら、このような方法も、未だ完全に満足できるものではない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、ユーザに提供する余分な詳細情報を減らしてルートを一層容易に理解できるように、従来技術の欠点を改善したルート計算方法およびデバイスを提供することにある。
【課題を解決するための手段】
【０００６】
従って本発明は、第一地点αと第二地点βとの間の最適ルートを、少なくとも１つの基準ＣＯの関数として計算機により作成できるルート計算方法であって、少なくとも１つの記憶媒体に記憶されかつ１組の共通ノードを有する少なくとも第一ソースおよび第二ソースからのデジタルデータ特に地理的データを使用する段階を有し、第二ソースは、少なくとも１つの特性Ｋが第一ソースとは異なっているルート計算方法において、
ａ）地点αおよび第一ソースに基いて、前記地点αに実質的に隣接しかつ第一ソースおよび第二ソースの両方に基準を有する複数のαノード（Ｎα）を決定し、かつ第一ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｂ）地点βおよび第三ソースに基いて、前記地点βに実質的に隣接しかつ第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、かつ第三ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｃ）全対のノードＮα、Ｎβについての第二ソースからのデータおよび所与の基準ＣＯに基いて、各対のノード（Ｎα、Ｎβ）の第二最適値を決定する段階と
ｄ）α−βルートの組について、地点αから地点βに至る全ルートの最適化を可能にする最適ノードを決定する段階とを有するルート計算方法を提供する。
これらの種々の段階が遂行される順序は、実施形態に基いて変えることができる。
ソースを区別する特性（characteristic）Ｋは、各ソース（例えば、第一ソースとは異なる縮尺、第一ソースのフォーマットとは異なるフォーマットのデータベース等）が保有する情報の関数であることが好ましい。かくして、例えば、第一ソースを都市形式とし、および／または第二ソースを都市間形式とし、および／または第三ソースを都市形式とすることができる。
【０００７】
このような構成は、ルート作成のリアルな最適化および結果の明瞭で正確かつ論理的表示の両方を可能にする。かくして、例えば都市旅程部分および都市間旅程部分を含むルートの場合には、本発明による方法は、基準を、各旅程部分について最適ソースにすることができる。かくして、都市旅程部分について、例えば基準を高密度ソース、すなわち多数の詳細情報を含むソースにすることができる。環境形式が例えば都市間旅程部分に変わるやいなや、基準が他のソースまたは最初のソースを補完するソースになる。例えば、基準は、長距離都市間旅程のルートを作成するための「小縮尺」形式のソースとなる。本質的な詳細情報のみが現われる。ユーザ（多くは車両のドライバ）に与えられる命令は簡単で、混乱を生じさせる虞れがあるあらゆる詳細情報がなくなる。記述命令またはコード化された命令の場合には、命令の形式を旅程の形式に適合させることは容易である。例えば市街地では、従うべき経路の表示は、例えば「左折し、３２０ｍ直進し、次に右折し、等」のように非常に詳細な情報である。自動車道路または高速道路では、表示は、「ＡＢＣの方向には２６０ａ号線の道路を選択せよ」となるであろう。かくして、得られるルートプランは、特に都市間旅程部分に関する限り、実質的に簡明になる。
【０００８】
一方、異なる起源および／または形式のソースを使用すると、個々の場合に最も適した各ソースからのデータ、例えば最も正確なデータ、最も新しいデータ、最も信頼できるデータ、最も品質の高いデータ等を用いて演算を行なうことができる。
また、例えば使用される種々のソースが互いに確実に補完されることを目的として、これらを自主的に処理または維持できることに留意されたい。かくして、例えば、交通の主要部を魅力的にする主要道路網に関するデータを保有するソースの維持および更新努力を集中させまたは最大化できる。
また、完全ルート、すなわち１つ以上の旅程部分を省略しないルートを提供することもできる。都市中心に関するデータを保有しているソースを、これらの中心同士をリンクさせることなく利用できる場合には、本発明により、中心間の連結を行なう第二ソースと呼ぶことができ、かくして、中心から中心までの全ルートを作成できる。
【０００９】
所与のルートの種々の各部分に良く適したソースを使用できるため、プロセスがかなり簡単化される。複雑で密度の高い単一ソースから複雑なルートが作成され、より実用的でユーザに優しいものとするため、得られる結果がプロセスの終時に簡単化される現在の或る技術とは異なり、本発明による方法は、アウトセットすなわち使用されるソースとの一体部分から簡単化できる。これは、例えば、所与の旅程部分に、過度に複雑であるか過度に詳細なソースの必要をなくする基準を回避する形態をとる。
前記方法において、段階ｃおよび段階ｄは、段階ａおよび段階ｂが完了すると連続して行なわれるのが好ましい。
第一ソースは都市形式であり、第二ソースは都市間形式であり、第三ソースは都市形式であるのが有利である。前記ノード（Ｎα、Ｎβ）の第一および第二最適値は、ＤＩＪＫＳＴＲＡから得られるアルゴリズムに基いて決定されることが好ましい。
１つの有利な実施形態の例によれば、地点αは例えばルートの出発地点であり、地点βは例えばルートの目的地点である。第三ソースは第一ソースに実質的に一致し、第三ソースは第一ソースの限定セクタに実質的に一致するのが有利である。
１つの有利な実施形態によれば、共通ノードの組は、１つ以上のソースで識別された或るノードが一緒にリンクされている、前のマッチング段階から得られる。
１つの有利な実施形態の例によればαノードは地点αに一致し、他の有利な実施形態の例によればβノードは地点βに一致する。
【００１０】
種々の変更形態によれば、ＧＯＮＤＲＡＮおよびＭＩＮＯＵＸにより開発された他の技術要素を導入することにより、ＤＩＪＫＳＴＲＡアルゴリズムが改良され、簡単化されまたは最適化される。
ノードまたはルートの最適値ＣＯは、少なくとも１つの基準ＣＲＩの関数として確立されるのが有利である。基準ＣＲＩは予確立されるか、予確立されたリストからユーザにより選択されるか、ユーザにより定められる。作成されたルートに関するデータ、コード化されたリストの形態、より詳しくは記述された命令の形態でユーザに与えられるのが有利である。１つの変更形態によれば、作成されたルートに関するデータは、地理的表示、より詳しくはルートが強調された道路地図の形態でユーザに提供される。
【００１１】
本発明はまた、上記方法を実施するデバイスを提供し、該デバイスは、
第一ソースおよび第二ソースからのデータにアクセスできる少なくとも１つの記憶ユニットと、
最適ルートを創成できる少なくとも１つの計算ユニットと、
ユーザに最適ルートを提示できる少なくとも１つのディスプレイ手段と、
前記方法を実施できる実行命令とを有している。
記憶ユニットは、ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭ等の着脱可能な記憶手段と協働できるのが有利である。
１つの有利な実施形態によれば、デバイスは自動車に搭載して使用することを意図している。
他の有利な実施形態によれば、記憶ユニットおよび計算ユニットは中央制御され、かつ分散制御される多数の周辺ステーションが、前記方法に従って作成された最適ルートにアクセスできるように構成される。例えば、分散制御されるステーションは、ネットワーク、特にグローバルネットワークを介して、中央制御されるユニットに接続できる。
【００１２】
本発明はまた、上記デバイスを有するコンピュータシステムを提供する。
本発明はまた、上記方法を実施するための、プログラムされたコード要素を有するソフトウェアにおいて、コンピュータシステムにローディングされかつかつ該コンピュータシステムにより実行されるソフトウェアを提供する。
本発明は更に、上記プログラムされたコード要素を有するコンピュータシステムにより読取り可能な媒体に記録された製品の形態をなすソフトウェアを提供する。
【発明を実施するための最良の形態】
【００１３】
以下、添付図面（図１〜図９）を参照して、本発明の実施形態を詳細に説明する。
種々の図面において、同類の要素は同じ参照番号を用いて示されている。
本願明細書において、下記用語は、特に下記の意味をもつものとして使用される。
用語「ノード」とは、第一地図要素すなわち道路網（または他の）要素と、このような道路網の第二要素との交差点、特に複数の道路の交差点である。ノードはまた、例えば２つのレーンから３つのレーンへの分岐部（changeover）、制限速度の変更、道路工事（一時的工事も含む）中のゾーン、国境等の遮断地点のような道路の一セクションの物理的または量的変更地点を意味する。
用語「セクション」は、２つのノード間の道路の部分である。
【００１４】
本発明の好ましい実施形態によれば、このルート計算方法は、少なくとも２つの異なるソースから、データ、特に地理的データまたは任意であるがツーリスト情報または交通情報、時刻表、推奨事項またはアドバイス等の他の形式のデータを用いて、地点αと地点βとの間の少なくとも１つの基準ＣＯの関数として最適ルートを作成できる。２つのソース間の区別（distinguishing）ファクタ「Ｋ」は、異なる形式の要素から得ることができる。第一例によれば、これは、包含される地理的データの形式から得られる。かくしてこれは、都市形式のソースで構成でき、この場合、該ソースは、道路網、地名等、町または広域都市圏の詳細地図に少し似たもの（これらは、このような地図の紙版の場合には大きい縮尺として類別される）に関する比較的詳細かつ正確なデータからなる。これは、一方では、都市間形式のソースとなることができ、この場合には、このソースは、特に、旅程が数十または数百キロメートルの１つである場合に、かなりの距離の旅程（例えば、町または町の一部を通る主要道路を通る旅程、主要道路または自動車道路での都市間領域等）を可能にする道路網に基いたデータを有する。この場合、これらのデータは、紙地図の場合での小縮尺として類別される領域、省、州または１つ以上の国の地図に似たものとなる。このような例の場合、文字Ｋは、「縮尺」の差、または情報の密度の差、または地図的範囲の差等に似ている。
区別するソースは、ソース形式例えば、地理的データのソース、または他の地質学的、気候学的または地球物理的的データからも得ることができる。この場合、文字Ｋは、ソースからの主データ形式に一致する。
【００１５】
図１および図２に示す特に有利な１つの例示実施形態によれば、主として道路上のルートであるが、可能であれば歩道セクション、レールセクションまたは海上セクション（例えばフェリーによるもの）をも含むルートを決定すなわち「作る」方法を最適化する目的で、２つ以上の補完地理的ソースが使用される。「統合（intermodal）」形式のルートも作成される。このようなルートには、例えば、バス、列車、航空機、船舶、自動車、歩行等の種々の交通モードを用いる種々の部分がある。
２つ以上のソースは、オーバーラップゾーン、共通ゾーンまたはインターフェースゾーンを有するのが好ましい。このようなゾーンは、ソース間の連続形態または連結形態にできるのが有利である。例えば、都市形式の第一ソースには地点αがあり、この地点αは、都市ゾーンに近い自動車道路の迂回路（motorway slip-road）に一致させることができる。都市間形式の第二ソースには、これも同じ自動車道路の迂回路に一致する同じ地点αが見られるようにするのが有利である。本発明の文脈では、同じ地点αとは、各ソースは、実世界での１つの同じ物理的または地理的事実を識別(identifying)するコードを有していることを意味する。
【００１６】
実際に、これと同じ地点αが、各ソースに１つの同じコードで表される。この場合には、１つのソースに基いて位置決めされる地点αは他のソースで容易に識別されかつ位置決めされるので簡単な管理が可能である。一方、地点αは異なるコードで表すことができる。この場合には、異なるソースからの「異なる」地点α同士の間をリンクさせ、一方から他方へと容易に通すことができるようにするのが望ましい。これらのリンクは、一方のソースに一体化されるか、独立したソースに一体化される。かくして、２つ以上のソースの間にリンクのベースを設け、これらのソース以外にこれを参照することができる。
また、他のソースにおいて必ずしも同じである必要がない所与の形態および所与の位置により、地点αを１つのソースで識別することができる。この場合、リンクまたはリンクソースは要素を対にすることを含むのが好ましく、これにより、１つのソースからの地点が、（１つの同じ地理的または物理的事実のための）他のソースの同様な地点に同化されること、および１つのソースから、干渉または不連続なく可能である他のソースへの切換えが可能である。この切換えは、しばしば、「マッチング」として示される。
【００１７】
本発明によれば、図１、図２および図８に例示するように、地点αおよび第一ソースを使用して１つ以上のαノード（Ｎα）を決定する。特定例によれば、地点αは実質的にノードに一致する。前述のように、選択されたノードは、２つのソースで参照されることにより、インターフェース可能なリンクにより、または２つのソース間にリンクを確立することにより、第一または第二ソースに基いて位置決めまたは識別される。
価値またはコストは、識別された各ノードについて、所与の基準ＣＯの関数として決定されるのが好ましい。この基準は、本発明の説明において後述する。
地点αの周囲領域またはセクタ内に位置するノードの数は、種々のアプローチに従って定めることができる。１つの有利な実施形態の例によれば、既に識別された第一ノードを通ることなく識別されたノードのみが採用すなわち維持される。このアプローチによれば、地点αの直ぐ近くに配置されるノードが最適化され、他のノードは自動的に配置される。
他の有利なアプローチによれば、例えば地点αのセクタ上に分布される１０、１５または３０個の所与のノード数が採用される。他の有利なアプローチによれば、例えば、地点αの周囲１０、２０または５０ｋｍの半径内に位置するノードのように、αセクタにリンクされた所与の地理的制限内に位置するノードが採用される。
これらのモードの１つまたは他のモードによれば、好ましくは所与の方向に位置するαセクタの地点を採用することもできる。
【００１８】
次に、図１、図２および図８に示すように、βセクタ（β）において複数のβノード（Ｎβ）を得るため、地点βについて同じプロセスが遂行される。βノードは、第三ソースおよび第二ソースの両方において基準となるのが好ましい。第三ソースは、例えば、地点βが位置するセクタと同じ都市ソースとすることができる。第三ソースは、前述のように、異なる形態にすることができる。次に、αノードの場合のようにして、βノードについての値が決定される。
一変更形態によれば、第三ソースは実質的に第一ソースに一致するか、或いは第一ソースの特定セクタに一致する。
次に、複数のαノードおよび複数のβノードが利用可能になる（図２参照）。図３、図４および下記表１には、都市形式すなわち大縮尺形式の第一ソースと、都市間形式すなわち小縮尺形式の第二ソース（図４）とに共通のαノードまたはβノードの例が示されている。
【００１９】
【表１】
【００２０】
この例では、ＴＥＬＥＡＴＬＡＳデータから大縮尺ソースが得られ、一方、ＭＩＣＨＥＬＩＮソース（ＭＩＣＨＥＬＩＮ Europeベース）から小縮尺ソースが得られる。表１には、出発地点（または目的地点）＊から決定される各ノード（例えばαまたはβノード）の詳細が示されている。この例では、各ノードに与えられる値は、問題とする出発地点からノードまでの旅程時間に一致する。同じ例において、表１に示すように、ノード１〜７が位置決めすなわち決定され、各ノードに１つの値が与えられる。
この例の出発地点は、ムードン（フランス）アヴェニュ ド ラ ペに位置し、「＊」により識別される。この地点の値はゼロが有利である。他の各ノードは、この例では、地点＊とノードとの間の実質的な平均旅程時間の関数としての異なる値を有している。他の値形式は、後述のように、他の単一または複数の基準の関数として与えられる。
αノードは地点αに対する値を有し、βノードは地点βに対する値を有する。
次に、好ましくは出発セクタとして識別されるセクタから出発しかつ徐々に他のセクタ（目的セクタ）に向かって走行することにより、各ノードについて第二値が有利に確立される。値は各ノードについて決定され、ここでは値Ｎ−Ｎ（ノード対ノード値）により表される。これは、前記値を確立する基準として機能する第二ソースに対して行なわれる。
【００２１】
このようにして続けると、出発地点に近いノードは「低い」値を有し、一方、目的セクタに近いノードは「高い」値を有する。ＤＩＪＫＳＴＲＡまたはアルゴリズムは、一方ではこれらの値を確立するのに使用され（ルート決定の分野または最短経路の決定分野で良く知られている）、他方では得られたルートを再び作成するのに有利に使用される。この方法によるノード決定は、図６および図７に示されかつこれに関連して更に説明する。
得られるルートは、目的セクタのノードについて可能な最良値の達成を可能にしたノードを通るルートに一致するのが好ましい。一般に、これは、最低値をもつノードである。値を決定する他の方法によれば、最高値をもつノードでもよい。このノードは「選択ノード」で示される。
【００２２】
本発明の好ましい実施形態によれば、各セクタについての最適値は、一方では、例えばこのプロセスのスタート時に確立されるαまたはβセクタの値を考察することにより、かつ他方では、例えば都市間セクタに一致するノード対ノードセクタ値を考察することにより確立される。かくして、目的βセクタでは、Ｎ−Ｎ値およびβセクタ値が各ノードに付加される。得られた全最適値をもつノードを使用するのが好ましい。αセクタの値とＮ−Ｎセクタの値とを組合せることにより、出発セクタについてこれと同じことが行なわれる。最適値をもつノードが選択される。
得られた全ルートは、出発セクタおよび目的セクタの選択ノード並びに値の最適化が許容されたＮ−Ｎセクタのノードを通る。
１つの変更形態によれば、出発地点は地点βであり、目的地点は地点αである。
他の変更形態によれば、αセクタおよび／またはβセクタから選択された少なくとも１つのノードの値は、全ルートの作成の考慮には入れられない。このような場合には、ノード対ノード部分に優先権が与えられる。
他の変更形態によれば、αルートは、地点αからαノード（最適化されているか否かは問わない）まで作成され、これと同じことが、βルートについて地点βからβノードまで行なわれ、かつノード対ノードルートがセクタＮ−Ｎセクタについて作成される。
【００２３】
かくして、１つの最適ルートが、旅程の１セクションに亘ってのみ得られる。しかしながら、この方法は、少なくとも２つの異なるソースについて参照がなされる種々のステップを有している。実際には、或る形式のルートについての最適化の必要性は二次的なものとするか、ユーザが、最適化されていない複数のルート間の選択を残しておくことが可能である。
本発明の好ましい実施形態によれば、ルート作成に関する情報は、下記表２に示すようなコード化された、より詳しくは記述された命令のリストの形態でユーザに与えられる。
【００２４】
【表２】
【００２５】
命令の第一部分（トップ部分）は、実質的にルートの都市部に相当する。与えられる詳細情報は非常に正確であり、非常に混雑した道路網であっても車両を容易に導くことができる。
この表１は、ユーザに命令を与えるすなわち伝達する一例を示している。多数の他の方法を使用することもできる。かくして、例えば、１つのセクションまたは表示された２つの道路の変化部を走行する旅程時間を特定できる。また、矢印のような記号または絵文字を使用することもできる。他の変更形態によれば、音声合成デバイスにより、途中でドライバに方向を伝達できる。
表１の下部には、都市間すなわち「小縮尺」形式の旅程部分が示されている。与えられる命令は、簡潔で、例えば従うべき方向、道路番号（または道路名）、出口番号（または出口名）等の形態にするのが有利である。与えられる命令は、ドライバが観察しかつ車両で適当な地点に到達したときに従う道路符号に関する表示を考慮に入れるのが有利である。
【００２６】
図８の例は、目的地点として、図３および図４におけるのと同じ出発地点から作成され、目的地点はヴェリズィ−ヴィラクレイである。出発セクタ（αセクタ）内でノード１が選択される。選択されたルートが、図５において実線および矢印で表示される。
一変更形態によれば、作成されるルートに関する情報は、地理的表示（より詳しくは、ルートが強調されている道路地図）の形態でユーザに提供される。
最適化基準ＣＯは、或る選択に従って値の割当てモードを定めることすなわち割当てることができる。ノードまたはルートのこの最適値ＣＯは、少なくとも１つの基準ＣＲＩの関数として確立される。一実施形態によれば、基準ＣＲＩが予確立され、例えばユーザによりリストから選択される。ルートを決定するときにユーザが考察する幾つかの特に有利な基準ＣＲＩの下記例がある。
・αとβとの間の実質的な最短ルートの決定
・αとβとの間の実質的な最高速ルートの決定
・距離と時間との妥協が得られるルートの決定
・αとβとの間の自動車道路の優先使用を本質的に与えるルートの決定
・αとβとの間の使用を本質的に回避するルートの決定
・通行料金が実質的に最も安いルートの決定
・最も快適なルートの決定
・本質的に最も混雑しないルートの決定
・例えば所与の国境を超えないルートの決定
・少なくとも１つの所望地点（例えば、ホテル、レストラン、ガソリンステーションまたはサービスステーション、観光地等）を通るルートの決定
かくして、基準ＣＯは複数の要素を考慮に入れる（任意であるが、これらの各要素の重要性を勘案する）のが有利である。
他の実施形態によれば、基準ＣＲＩはユーザにより定められる。基準は、既にリストで例示されたものと似たものでもよいし、個々に一層適応した他の基準形式でもよい。
【００２７】
図６および図７には、ＤＩＪＫＳＴＲＡアルゴリズム（好ましくは改訂版）を用いたツールに基いたルート（都市間形式のソースに基いた、都市間旅程部分のルート）の実施形態が例示されている。図６では、ParisからToulouseへのルートについて、ノードは、Parisの領域内の出発地点から可能性ある全ての方向に決定される。目的地セクタ（Toulouse）内に位置するノードが決定されかつ各ノードに値が割当てられたときには、最適出発ノードおよび目的地ノードを選択できる。得られたルートは、図示のように、最適ノードが得られるようにするノードを通る。
図７には変更形態が示されており、この変更形態によれば、ノードは、目的地セクタに向かう方向への優先性を与えることにより決定される。決定されたノードは、次に、目的地点に向かって配向された一種の「水滴」を形成する。新しいノードが、このノードと目的地点との間の値を、既知の他のノードに対して最適化できない場合には、ぉれを採用しないことが好ましい。
【００２８】
図９には、本発明の目的で使用するのに適した装置の一例が示されている。１つ以上のデータベースＤＢは、種々のソースからの地図的データを保有している。１つ以上の計算手段は、ルートを作成するのに要する演算の遂行を可能にする。ドライバは、演算を同期させるのに使用するのが有利である。
本発明の有利な変更形態によれば、本発明の方法は、ノードのみでなく他の出発データにも使用でき、例えば、ノードおよび／または配向されたセクションを使用することができる。
【図面の簡単な説明】
【００２９】
【図１】ルートの出発地点および目的地点を示す概略図であり、本発明による全ルートの最適化計算を行なうため、第一ソースから第二ソースに切換えることができるノードを示すものである。
【図２】ルートの出発地点および目的地点を示す概略図であり、本発明による全ルートの最適化計算を行なうため、第一ソースから第二ソースに切換えることができるノードを示すものである。
【図３】所与の出発地点に基いて決定された一連のノードを示す概略図であり、ノードは、都市形式の典型的表示で示されている。
【図４】所与の出発地点に基いて決定された一連のノードを示す概略図であり、ノードは、都市間形式の典型的表示で示されており、従って、ルートの作成に使用される２つのソース間の一致ゾーンまたは立体交差ゾーンを示している。
【図５】本図中の７つの潜在ノードの１つまたは他から出発する、ムードンからヴェリズィへのルートを見出す方法を示すものである。
【図６】ルートを作成すべく機能するノードをもつルートの都市間部分の一例を示し、（パリの）所与の半径内の全てのノードを示すものである。
【図７】ルートを作成すべく機能するノードをもつルートの都市間部分の一例を示し、目的地点（トゥールーズ）の方向に与えられる優先度をもつ或る半径内のノードを示すものである。
【図８】本発明の方法を用いて、地点αと地点βとの間の最適ルートの用意を可能にする主要段階を示すものである。
【図９】公共ネットワークによりアクセスできる、中央制御型ルート計算システムに使用される装置の例示構成を示すものである。
【符号の説明】
【００３０】
Ｎα αノード
Ｎβ βノード
【技術分野】
【０００１】
本発明は、複数の基準ソースを用いて、命令の形態でのルート作成および／またはルート表示の最適化を可能にするルート計算方法に関する。
【背景技術】
【０００２】
近頃は、種々のルート計算方法および幾つかの形式の関連デバイスが良く知られている。２つの形式の補完技術が、これらのツールを大きく普及させることを可能にしている。第一に、ドライバが、その車両をスクリーン上に表示された方向に従って所与の場所に導くことができる搭載型デバイスがある。このようなデバイスは、しばしばＧＰＳ機器と組合されることにより、更に、車両のほぼ正確な場所およびこの場所からのルートの完成が可能である。パソコンで使用するための幾つかのバージョンも存在している。
一方、中央制御型デバイスは、多数の潜在的ユーザに、例えばインターネットのようなネットワークを介してアクセスできる非常に広範囲の可能性を提供する。集中デバイスは、（ユーザへの付加コストがない）規則的データ更新ができ、各ユーザの利用コストを最低にできるという長所がある。ルート計算以外に、プロバイダは、交通予報／推奨情報、ツーリスト情報等の関連サービスをもしばしば提供する。
【０００３】
これらの形式のサービスは現存しているので範囲の拡大は停止していないが、殆どの時間、改善は、ルート計算を可能にする技術に関するものではなく、関連アスペクトに関するものに費やされてきた。機器が着実にパワフルになるにつれて、演算時間の最適化にかなりの進歩がなされ、得られるプレゼンテーション等が改善されている。ルート計算の原理は殆ど進歩しておらず、従って、ときどき、作られるルートのクオリティに影響を与える危険がある幾つかの制限を有している。例えば、既知の形式の方法およびデバイスは、単一の地理的データソースを用いてルートを作成している。前記ソースにより与えられる情報の密度およびクオリティ、および更新される頻度に関係して、ルートは、信頼性の度合いは異なるがほぼ正確に作成される。
例えば、作成されるルートの大部分は、所与の都市領域に出発地点を有し、かつ前記領域内での都市旅程（urban journey）、都市間領域内でのルート部分および再度の都市領域内での目的地点を含んでいる。このようなルートが単一データソースに基いていると考えられる場合には、都市領域の必要精度を得るため、デフォルトにより「大縮尺」形式のソースが使用される。ルートが命令のリストの形態で与えられる場合には、都市旅程部分は、同じ道路等をどれ程の距離だけ続けるかについて、例えば、左折または右折の瞬間から出発して高度に詳細化される。
【０００４】
都市間領域内のルートでは、このような精度は不要でありかつ実際に望まれていない。実際に、例えばこのような主要道路すなわち自動車道のような高速道路に沿って走行するとき、ドライバは、走行すべき道路の形状、従うべき方向等に関する命令に一層よく応答できる。実際に、高速でおよび／または長距離旅程で、「左折し、１００ｍの間まっすぐに走行を続けて右折する」という形式の命令に応答することは困難である。しかしながら、このような命令は、大縮尺地図（large scale map）に一致（一般にあらゆる種類の詳細情報（detail）に富んだ都市領域に一致）するソースでは一般的である。
同様に、ルートが線（ライン）の形態で地図上に表示されるときは、無関係の詳細情報が多過ぎると、どこに居るのかを理解することが困難になってしまう。最終的には、得られるルートプランは長くて、使用が困難なものとなる。
これらの欠点を改善するため、ユーザに提供する余分な詳細情報を減らしてルートを一層容易に理解できるようにすることを目的として、ステップを連鎖(concatenating）させまたは簡単化させたルート計算方法がしばしば使用されている。しかしながら、このような方法も、未だ完全に満足できるものではない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、ユーザに提供する余分な詳細情報を減らしてルートを一層容易に理解できるように、従来技術の欠点を改善したルート計算方法およびデバイスを提供することにある。
【課題を解決するための手段】
【０００６】
従って本発明は、第一地点αと第二地点βとの間の最適ルートを、少なくとも１つの基準ＣＯの関数として計算機により作成できるルート計算方法であって、少なくとも１つの記憶媒体に記憶されかつ１組の共通ノードを有する少なくとも第一ソースおよび第二ソースからのデジタルデータ特に地理的データを使用する段階を有し、第二ソースは、少なくとも１つの特性Ｋが第一ソースとは異なっているルート計算方法において、
ａ）地点αおよび第一ソースに基いて、前記地点αに実質的に隣接しかつ第一ソースおよび第二ソースの両方に基準を有する複数のαノード（Ｎα）を決定し、かつ第一ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｂ）地点βおよび第三ソースに基いて、前記地点βに実質的に隣接しかつ第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、かつ第三ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｃ）全対のノードＮα、Ｎβについての第二ソースからのデータおよび所与の基準ＣＯに基いて、各対のノード（Ｎα、Ｎβ）の第二最適値を決定する段階と
ｄ）α−βルートの組について、地点αから地点βに至る全ルートの最適化を可能にする最適ノードを決定する段階とを有するルート計算方法を提供する。
これらの種々の段階が遂行される順序は、実施形態に基いて変えることができる。
ソースを区別する特性（characteristic）Ｋは、各ソース（例えば、第一ソースとは異なる縮尺、第一ソースのフォーマットとは異なるフォーマットのデータベース等）が保有する情報の関数であることが好ましい。かくして、例えば、第一ソースを都市形式とし、および／または第二ソースを都市間形式とし、および／または第三ソースを都市形式とすることができる。
【０００７】
このような構成は、ルート作成のリアルな最適化および結果の明瞭で正確かつ論理的表示の両方を可能にする。かくして、例えば都市旅程部分および都市間旅程部分を含むルートの場合には、本発明による方法は、基準を、各旅程部分について最適ソースにすることができる。かくして、都市旅程部分について、例えば基準を高密度ソース、すなわち多数の詳細情報を含むソースにすることができる。環境形式が例えば都市間旅程部分に変わるやいなや、基準が他のソースまたは最初のソースを補完するソースになる。例えば、基準は、長距離都市間旅程のルートを作成するための「小縮尺」形式のソースとなる。本質的な詳細情報のみが現われる。ユーザ（多くは車両のドライバ）に与えられる命令は簡単で、混乱を生じさせる虞れがあるあらゆる詳細情報がなくなる。記述命令またはコード化された命令の場合には、命令の形式を旅程の形式に適合させることは容易である。例えば市街地では、従うべき経路の表示は、例えば「左折し、３２０ｍ直進し、次に右折し、等」のように非常に詳細な情報である。自動車道路または高速道路では、表示は、「ＡＢＣの方向には２６０ａ号線の道路を選択せよ」となるであろう。かくして、得られるルートプランは、特に都市間旅程部分に関する限り、実質的に簡明になる。
【０００８】
一方、異なる起源および／または形式のソースを使用すると、個々の場合に最も適した各ソースからのデータ、例えば最も正確なデータ、最も新しいデータ、最も信頼できるデータ、最も品質の高いデータ等を用いて演算を行なうことができる。
また、例えば使用される種々のソースが互いに確実に補完されることを目的として、これらを自主的に処理または維持できることに留意されたい。かくして、例えば、交通の主要部を魅力的にする主要道路網に関するデータを保有するソースの維持および更新努力を集中させまたは最大化できる。
また、完全ルート、すなわち１つ以上の旅程部分を省略しないルートを提供することもできる。都市中心に関するデータを保有しているソースを、これらの中心同士をリンクさせることなく利用できる場合には、本発明により、中心間の連結を行なう第二ソースと呼ぶことができ、かくして、中心から中心までの全ルートを作成できる。
【０００９】
所与のルートの種々の各部分に良く適したソースを使用できるため、プロセスがかなり簡単化される。複雑で密度の高い単一ソースから複雑なルートが作成され、より実用的でユーザに優しいものとするため、得られる結果がプロセスの終時に簡単化される現在の或る技術とは異なり、本発明による方法は、アウトセットすなわち使用されるソースとの一体部分から簡単化できる。これは、例えば、所与の旅程部分に、過度に複雑であるか過度に詳細なソースの必要をなくする基準を回避する形態をとる。
前記方法において、段階ｃおよび段階ｄは、段階ａおよび段階ｂが完了すると連続して行なわれるのが好ましい。
第一ソースは都市形式であり、第二ソースは都市間形式であり、第三ソースは都市形式であるのが有利である。前記ノード（Ｎα、Ｎβ）の第一および第二最適値は、ＤＩＪＫＳＴＲＡから得られるアルゴリズムに基いて決定されることが好ましい。
１つの有利な実施形態の例によれば、地点αは例えばルートの出発地点であり、地点βは例えばルートの目的地点である。第三ソースは第一ソースに実質的に一致し、第三ソースは第一ソースの限定セクタに実質的に一致するのが有利である。
１つの有利な実施形態によれば、共通ノードの組は、１つ以上のソースで識別された或るノードが一緒にリンクされている、前のマッチング段階から得られる。
１つの有利な実施形態の例によればαノードは地点αに一致し、他の有利な実施形態の例によればβノードは地点βに一致する。
【００１０】
種々の変更形態によれば、ＧＯＮＤＲＡＮおよびＭＩＮＯＵＸにより開発された他の技術要素を導入することにより、ＤＩＪＫＳＴＲＡアルゴリズムが改良され、簡単化されまたは最適化される。
ノードまたはルートの最適値ＣＯは、少なくとも１つの基準ＣＲＩの関数として確立されるのが有利である。基準ＣＲＩは予確立されるか、予確立されたリストからユーザにより選択されるか、ユーザにより定められる。作成されたルートに関するデータ、コード化されたリストの形態、より詳しくは記述された命令の形態でユーザに与えられるのが有利である。１つの変更形態によれば、作成されたルートに関するデータは、地理的表示、より詳しくはルートが強調された道路地図の形態でユーザに提供される。
【００１１】
本発明はまた、上記方法を実施するデバイスを提供し、該デバイスは、
第一ソースおよび第二ソースからのデータにアクセスできる少なくとも１つの記憶ユニットと、
最適ルートを創成できる少なくとも１つの計算ユニットと、
ユーザに最適ルートを提示できる少なくとも１つのディスプレイ手段と、
前記方法を実施できる実行命令とを有している。
記憶ユニットは、ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭ等の着脱可能な記憶手段と協働できるのが有利である。
１つの有利な実施形態によれば、デバイスは自動車に搭載して使用することを意図している。
他の有利な実施形態によれば、記憶ユニットおよび計算ユニットは中央制御され、かつ分散制御される多数の周辺ステーションが、前記方法に従って作成された最適ルートにアクセスできるように構成される。例えば、分散制御されるステーションは、ネットワーク、特にグローバルネットワークを介して、中央制御されるユニットに接続できる。
【００１２】
本発明はまた、上記デバイスを有するコンピュータシステムを提供する。
本発明はまた、上記方法を実施するための、プログラムされたコード要素を有するソフトウェアにおいて、コンピュータシステムにローディングされかつかつ該コンピュータシステムにより実行されるソフトウェアを提供する。
本発明は更に、上記プログラムされたコード要素を有するコンピュータシステムにより読取り可能な媒体に記録された製品の形態をなすソフトウェアを提供する。
【発明を実施するための最良の形態】
【００１３】
以下、添付図面（図１〜図９）を参照して、本発明の実施形態を詳細に説明する。
種々の図面において、同類の要素は同じ参照番号を用いて示されている。
本願明細書において、下記用語は、特に下記の意味をもつものとして使用される。
用語「ノード」とは、第一地図要素すなわち道路網（または他の）要素と、このような道路網の第二要素との交差点、特に複数の道路の交差点である。ノードはまた、例えば２つのレーンから３つのレーンへの分岐部（changeover）、制限速度の変更、道路工事（一時的工事も含む）中のゾーン、国境等の遮断地点のような道路の一セクションの物理的または量的変更地点を意味する。
用語「セクション」は、２つのノード間の道路の部分である。
【００１４】
本発明の好ましい実施形態によれば、このルート計算方法は、少なくとも２つの異なるソースから、データ、特に地理的データまたは任意であるがツーリスト情報または交通情報、時刻表、推奨事項またはアドバイス等の他の形式のデータを用いて、地点αと地点βとの間の少なくとも１つの基準ＣＯの関数として最適ルートを作成できる。２つのソース間の区別（distinguishing）ファクタ「Ｋ」は、異なる形式の要素から得ることができる。第一例によれば、これは、包含される地理的データの形式から得られる。かくしてこれは、都市形式のソースで構成でき、この場合、該ソースは、道路網、地名等、町または広域都市圏の詳細地図に少し似たもの（これらは、このような地図の紙版の場合には大きい縮尺として類別される）に関する比較的詳細かつ正確なデータからなる。これは、一方では、都市間形式のソースとなることができ、この場合には、このソースは、特に、旅程が数十または数百キロメートルの１つである場合に、かなりの距離の旅程（例えば、町または町の一部を通る主要道路を通る旅程、主要道路または自動車道路での都市間領域等）を可能にする道路網に基いたデータを有する。この場合、これらのデータは、紙地図の場合での小縮尺として類別される領域、省、州または１つ以上の国の地図に似たものとなる。このような例の場合、文字Ｋは、「縮尺」の差、または情報の密度の差、または地図的範囲の差等に似ている。
区別するソースは、ソース形式例えば、地理的データのソース、または他の地質学的、気候学的または地球物理的的データからも得ることができる。この場合、文字Ｋは、ソースからの主データ形式に一致する。
【００１５】
図１および図２に示す特に有利な１つの例示実施形態によれば、主として道路上のルートであるが、可能であれば歩道セクション、レールセクションまたは海上セクション（例えばフェリーによるもの）をも含むルートを決定すなわち「作る」方法を最適化する目的で、２つ以上の補完地理的ソースが使用される。「統合（intermodal）」形式のルートも作成される。このようなルートには、例えば、バス、列車、航空機、船舶、自動車、歩行等の種々の交通モードを用いる種々の部分がある。
２つ以上のソースは、オーバーラップゾーン、共通ゾーンまたはインターフェースゾーンを有するのが好ましい。このようなゾーンは、ソース間の連続形態または連結形態にできるのが有利である。例えば、都市形式の第一ソースには地点αがあり、この地点αは、都市ゾーンに近い自動車道路の迂回路（motorway slip-road）に一致させることができる。都市間形式の第二ソースには、これも同じ自動車道路の迂回路に一致する同じ地点αが見られるようにするのが有利である。本発明の文脈では、同じ地点αとは、各ソースは、実世界での１つの同じ物理的または地理的事実を識別(identifying)するコードを有していることを意味する。
【００１６】
実際に、これと同じ地点αが、各ソースに１つの同じコードで表される。この場合には、１つのソースに基いて位置決めされる地点αは他のソースで容易に識別されかつ位置決めされるので簡単な管理が可能である。一方、地点αは異なるコードで表すことができる。この場合には、異なるソースからの「異なる」地点α同士の間をリンクさせ、一方から他方へと容易に通すことができるようにするのが望ましい。これらのリンクは、一方のソースに一体化されるか、独立したソースに一体化される。かくして、２つ以上のソースの間にリンクのベースを設け、これらのソース以外にこれを参照することができる。
また、他のソースにおいて必ずしも同じである必要がない所与の形態および所与の位置により、地点αを１つのソースで識別することができる。この場合、リンクまたはリンクソースは要素を対にすることを含むのが好ましく、これにより、１つのソースからの地点が、（１つの同じ地理的または物理的事実のための）他のソースの同様な地点に同化されること、および１つのソースから、干渉または不連続なく可能である他のソースへの切換えが可能である。この切換えは、しばしば、「マッチング」として示される。
【００１７】
本発明によれば、図１、図２および図８に例示するように、地点αおよび第一ソースを使用して１つ以上のαノード（Ｎα）を決定する。特定例によれば、地点αは実質的にノードに一致する。前述のように、選択されたノードは、２つのソースで参照されることにより、インターフェース可能なリンクにより、または２つのソース間にリンクを確立することにより、第一または第二ソースに基いて位置決めまたは識別される。
価値またはコストは、識別された各ノードについて、所与の基準ＣＯの関数として決定されるのが好ましい。この基準は、本発明の説明において後述する。
地点αの周囲領域またはセクタ内に位置するノードの数は、種々のアプローチに従って定めることができる。１つの有利な実施形態の例によれば、既に識別された第一ノードを通ることなく識別されたノードのみが採用すなわち維持される。このアプローチによれば、地点αの直ぐ近くに配置されるノードが最適化され、他のノードは自動的に配置される。
他の有利なアプローチによれば、例えば地点αのセクタ上に分布される１０、１５または３０個の所与のノード数が採用される。他の有利なアプローチによれば、例えば、地点αの周囲１０、２０または５０ｋｍの半径内に位置するノードのように、αセクタにリンクされた所与の地理的制限内に位置するノードが採用される。
これらのモードの１つまたは他のモードによれば、好ましくは所与の方向に位置するαセクタの地点を採用することもできる。
【００１８】
次に、図１、図２および図８に示すように、βセクタ（β）において複数のβノード（Ｎβ）を得るため、地点βについて同じプロセスが遂行される。βノードは、第三ソースおよび第二ソースの両方において基準となるのが好ましい。第三ソースは、例えば、地点βが位置するセクタと同じ都市ソースとすることができる。第三ソースは、前述のように、異なる形態にすることができる。次に、αノードの場合のようにして、βノードについての値が決定される。
一変更形態によれば、第三ソースは実質的に第一ソースに一致するか、或いは第一ソースの特定セクタに一致する。
次に、複数のαノードおよび複数のβノードが利用可能になる（図２参照）。図３、図４および下記表１には、都市形式すなわち大縮尺形式の第一ソースと、都市間形式すなわち小縮尺形式の第二ソース（図４）とに共通のαノードまたはβノードの例が示されている。
【００１９】
【表１】
【００２０】
この例では、ＴＥＬＥＡＴＬＡＳデータから大縮尺ソースが得られ、一方、ＭＩＣＨＥＬＩＮソース（ＭＩＣＨＥＬＩＮ Europeベース）から小縮尺ソースが得られる。表１には、出発地点（または目的地点）＊から決定される各ノード（例えばαまたはβノード）の詳細が示されている。この例では、各ノードに与えられる値は、問題とする出発地点からノードまでの旅程時間に一致する。同じ例において、表１に示すように、ノード１〜７が位置決めすなわち決定され、各ノードに１つの値が与えられる。
この例の出発地点は、ムードン（フランス）アヴェニュ ド ラ ペに位置し、「＊」により識別される。この地点の値はゼロが有利である。他の各ノードは、この例では、地点＊とノードとの間の実質的な平均旅程時間の関数としての異なる値を有している。他の値形式は、後述のように、他の単一または複数の基準の関数として与えられる。
αノードは地点αに対する値を有し、βノードは地点βに対する値を有する。
次に、好ましくは出発セクタとして識別されるセクタから出発しかつ徐々に他のセクタ（目的セクタ）に向かって走行することにより、各ノードについて第二値が有利に確立される。値は各ノードについて決定され、ここでは値Ｎ−Ｎ（ノード対ノード値）により表される。これは、前記値を確立する基準として機能する第二ソースに対して行なわれる。
【００２１】
このようにして続けると、出発地点に近いノードは「低い」値を有し、一方、目的セクタに近いノードは「高い」値を有する。ＤＩＪＫＳＴＲＡまたはアルゴリズムは、一方ではこれらの値を確立するのに使用され（ルート決定の分野または最短経路の決定分野で良く知られている）、他方では得られたルートを再び作成するのに有利に使用される。この方法によるノード決定は、図６および図７に示されかつこれに関連して更に説明する。
得られるルートは、目的セクタのノードについて可能な最良値の達成を可能にしたノードを通るルートに一致するのが好ましい。一般に、これは、最低値をもつノードである。値を決定する他の方法によれば、最高値をもつノードでもよい。このノードは「選択ノード」で示される。
【００２２】
本発明の好ましい実施形態によれば、各セクタについての最適値は、一方では、例えばこのプロセスのスタート時に確立されるαまたはβセクタの値を考察することにより、かつ他方では、例えば都市間セクタに一致するノード対ノードセクタ値を考察することにより確立される。かくして、目的βセクタでは、Ｎ−Ｎ値およびβセクタ値が各ノードに付加される。得られた全最適値をもつノードを使用するのが好ましい。αセクタの値とＮ−Ｎセクタの値とを組合せることにより、出発セクタについてこれと同じことが行なわれる。最適値をもつノードが選択される。
得られた全ルートは、出発セクタおよび目的セクタの選択ノード並びに値の最適化が許容されたＮ−Ｎセクタのノードを通る。
１つの変更形態によれば、出発地点は地点βであり、目的地点は地点αである。
他の変更形態によれば、αセクタおよび／またはβセクタから選択された少なくとも１つのノードの値は、全ルートの作成の考慮には入れられない。このような場合には、ノード対ノード部分に優先権が与えられる。
他の変更形態によれば、αルートは、地点αからαノード（最適化されているか否かは問わない）まで作成され、これと同じことが、βルートについて地点βからβノードまで行なわれ、かつノード対ノードルートがセクタＮ−Ｎセクタについて作成される。
【００２３】
かくして、１つの最適ルートが、旅程の１セクションに亘ってのみ得られる。しかしながら、この方法は、少なくとも２つの異なるソースについて参照がなされる種々のステップを有している。実際には、或る形式のルートについての最適化の必要性は二次的なものとするか、ユーザが、最適化されていない複数のルート間の選択を残しておくことが可能である。
本発明の好ましい実施形態によれば、ルート作成に関する情報は、下記表２に示すようなコード化された、より詳しくは記述された命令のリストの形態でユーザに与えられる。
【００２４】
【表２】
【００２５】
命令の第一部分（トップ部分）は、実質的にルートの都市部に相当する。与えられる詳細情報は非常に正確であり、非常に混雑した道路網であっても車両を容易に導くことができる。
この表１は、ユーザに命令を与えるすなわち伝達する一例を示している。多数の他の方法を使用することもできる。かくして、例えば、１つのセクションまたは表示された２つの道路の変化部を走行する旅程時間を特定できる。また、矢印のような記号または絵文字を使用することもできる。他の変更形態によれば、音声合成デバイスにより、途中でドライバに方向を伝達できる。
表１の下部には、都市間すなわち「小縮尺」形式の旅程部分が示されている。与えられる命令は、簡潔で、例えば従うべき方向、道路番号（または道路名）、出口番号（または出口名）等の形態にするのが有利である。与えられる命令は、ドライバが観察しかつ車両で適当な地点に到達したときに従う道路符号に関する表示を考慮に入れるのが有利である。
【００２６】
図８の例は、目的地点として、図３および図４におけるのと同じ出発地点から作成され、目的地点はヴェリズィ−ヴィラクレイである。出発セクタ（αセクタ）内でノード１が選択される。選択されたルートが、図５において実線および矢印で表示される。
一変更形態によれば、作成されるルートに関する情報は、地理的表示（より詳しくは、ルートが強調されている道路地図）の形態でユーザに提供される。
最適化基準ＣＯは、或る選択に従って値の割当てモードを定めることすなわち割当てることができる。ノードまたはルートのこの最適値ＣＯは、少なくとも１つの基準ＣＲＩの関数として確立される。一実施形態によれば、基準ＣＲＩが予確立され、例えばユーザによりリストから選択される。ルートを決定するときにユーザが考察する幾つかの特に有利な基準ＣＲＩの下記例がある。
・αとβとの間の実質的な最短ルートの決定
・αとβとの間の実質的な最高速ルートの決定
・距離と時間との妥協が得られるルートの決定
・αとβとの間の自動車道路の優先使用を本質的に与えるルートの決定
・αとβとの間の使用を本質的に回避するルートの決定
・通行料金が実質的に最も安いルートの決定
・最も快適なルートの決定
・本質的に最も混雑しないルートの決定
・例えば所与の国境を超えないルートの決定
・少なくとも１つの所望地点（例えば、ホテル、レストラン、ガソリンステーションまたはサービスステーション、観光地等）を通るルートの決定
かくして、基準ＣＯは複数の要素を考慮に入れる（任意であるが、これらの各要素の重要性を勘案する）のが有利である。
他の実施形態によれば、基準ＣＲＩはユーザにより定められる。基準は、既にリストで例示されたものと似たものでもよいし、個々に一層適応した他の基準形式でもよい。
【００２７】
図６および図７には、ＤＩＪＫＳＴＲＡアルゴリズム（好ましくは改訂版）を用いたツールに基いたルート（都市間形式のソースに基いた、都市間旅程部分のルート）の実施形態が例示されている。図６では、ParisからToulouseへのルートについて、ノードは、Parisの領域内の出発地点から可能性ある全ての方向に決定される。目的地セクタ（Toulouse）内に位置するノードが決定されかつ各ノードに値が割当てられたときには、最適出発ノードおよび目的地ノードを選択できる。得られたルートは、図示のように、最適ノードが得られるようにするノードを通る。
図７には変更形態が示されており、この変更形態によれば、ノードは、目的地セクタに向かう方向への優先性を与えることにより決定される。決定されたノードは、次に、目的地点に向かって配向された一種の「水滴」を形成する。新しいノードが、このノードと目的地点との間の値を、既知の他のノードに対して最適化できない場合には、ぉれを採用しないことが好ましい。
【００２８】
図９には、本発明の目的で使用するのに適した装置の一例が示されている。１つ以上のデータベースＤＢは、種々のソースからの地図的データを保有している。１つ以上の計算手段は、ルートを作成するのに要する演算の遂行を可能にする。ドライバは、演算を同期させるのに使用するのが有利である。
本発明の有利な変更形態によれば、本発明の方法は、ノードのみでなく他の出発データにも使用でき、例えば、ノードおよび／または配向されたセクションを使用することができる。
【図面の簡単な説明】
【００２９】
【図１】ルートの出発地点および目的地点を示す概略図であり、本発明による全ルートの最適化計算を行なうため、第一ソースから第二ソースに切換えることができるノードを示すものである。
【図２】ルートの出発地点および目的地点を示す概略図であり、本発明による全ルートの最適化計算を行なうため、第一ソースから第二ソースに切換えることができるノードを示すものである。
【図３】所与の出発地点に基いて決定された一連のノードを示す概略図であり、ノードは、都市形式の典型的表示で示されている。
【図４】所与の出発地点に基いて決定された一連のノードを示す概略図であり、ノードは、都市間形式の典型的表示で示されており、従って、ルートの作成に使用される２つのソース間の一致ゾーンまたは立体交差ゾーンを示している。
【図５】本図中の７つの潜在ノードの１つまたは他から出発する、ムードンからヴェリズィへのルートを見出す方法を示すものである。
【図６】ルートを作成すべく機能するノードをもつルートの都市間部分の一例を示し、（パリの）所与の半径内の全てのノードを示すものである。
【図７】ルートを作成すべく機能するノードをもつルートの都市間部分の一例を示し、目的地点（トゥールーズ）の方向に与えられる優先度をもつ或る半径内のノードを示すものである。
【図８】本発明の方法を用いて、地点αと地点βとの間の最適ルートの用意を可能にする主要段階を示すものである。
【図９】公共ネットワークによりアクセスできる、中央制御型ルート計算システムに使用される装置の例示構成を示すものである。
【符号の説明】
【００３０】
Ｎα αノード
Ｎβ βノード
【特許請求の範囲】
【請求項１】
第一地点αと第二地点βとの間の最適ルートを、少なくとも１つの基準ＣＯの関数として計算機により作成できるルート計算方法であって、少なくとも１つの記憶媒体に記憶されかつ１組の共通ノードを有する少なくとも第一ソースおよび第二ソースからのデジタルデータ特に地理的データを使用する段階を有し、第二ソースは、少なくとも１つの特性Ｋが第一ソースとは異なっているルート計算方法において、
ａ）地点αおよび第一ソースから、前記地点αに実質的に隣接しかつ第一ソースおよび第二ソースの両方に基準を有する複数のαノード（Ｎα）を決定し、かつ第一ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｂ）地点βおよび第三ソースから、前記地点βに実質的に隣接しかつ第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、かつ第三ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｃ）全対のノードＮα、Ｎβについての第二ソースからのデータおよび所与の基準ＣＯから、各対のノード（Ｎα、Ｎβ）の第二最適値を決定する段階と
ｃ）全対のノードＮα、Ｎβについての第二ソースおよび所与の基準ＣＯから、各対のノード（Ｎα、Ｎβ）についての第二最適値を決定する段階と
ｄ）α−βルートの組について、地点αから地点βに至る全ルートの最適化を可能にする最適ノードを決定する段階とを有することを特徴とするルート計算方法。
【請求項２】
前記ソースを区別する特性Ｋは、各ソースが保有する情報の関数であることを特徴とする請求項１記載のルート計算方法。
【請求項３】
前記段階ｃおよび段階ｄは、段階ａおよび段階ｂが完了すると、連続して遂行されることを特徴とする請求項１または２記載のルート計算方法。
【請求項４】
前記第一ソースは都市形式であり、第二ソースは都市間形式であることを特徴とする請求項１〜３のいずれか１項記載のルート計算方法。
【請求項５】
前記第三ソースは都市形式であることを特徴とする請求項１〜４のいずれか１項記載のルート計算方法。
【請求項６】
前記共通ノードの組は、１つ以上のソースで識別された或るノードが一緒にリンクされている、前のマッチング段階から得られることを特徴とする請求項１〜５のいずれか１項記載のルート計算方法。
【請求項７】
前記地点αは例えばルートの出発地点であり、地点βはルートの目的地点であることを特徴とする請求項１〜６のいずれか１項記載のルート計算方法。
【請求項８】
前記第三ソースは、第一ソースに実質的に一致することを特徴とする請求項１〜７のいずれか１項記載のルート計算方法。
【請求項９】
前記第三ソースは、第一ソースの限定セクタに実質的に一致することを特徴とする請求項１〜８のいずれか１項記載のルート計算方法。
【請求項１０】
前記αノードは地点αに一致することを特徴とする請求項１〜９のいずれか１項記載のルート計算方法。
【請求項１１】
前記βノードは地点βに一致することを特徴とする請求項１〜１０のいずれか１項記載のルート計算方法。
【請求項１２】
前記ノード（Ｎα、Ｎβ）の第一および第二最適値は、ＤＩＪＫＳＴＲＡから得られるアルゴリズムに基いて決定されることを特徴とする請求項１〜１１のいずれか１項記載のルート計算方法。
【請求項１３】
前記ノードまたはルートの最適値は、少なくとも１つの基準ＣＲＩの関数として確立されることを特徴とする請求項１〜１２のいずれか１項記載のルート計算方法。
【請求項１４】
前記基準ＣＲＩは予確立されたリストからユーザにより選択され、前記リストは、
・αとβとの間の実質的な最短ルートを決定することを目的とするＣＲ１１と、
・αとβとの間の実質的な最高速ルートを決定することを目的とするＣＲ１２と、
・αとβとの間の自動車道路の使用優先性を実質的に与えるルートを決定することを目的とするＣＲ１３と、
・αとβとの間の自動車道路の使用を本質的に回避するルートを決定することを目的とするＣＲ１４と、
・通行料金に関して実質的に最も安いルートを決定することを目的とするＣＲ１５と、
・最も快適なルートを決定することを目的とするＣＲ１６と、
・本質的に最も混雑していないルートを決定することを目的とするＣＲ１７と、
・少なくとも１つの所望地点を通るルートを決定することを目的とするＣＲ１８とを有することを特徴とする請求項１〜１３のいずれか１項記載のルート計算方法。
【請求項１５】
請求項１〜１４のいずれか１項記載の方法を実施するデバイスにおいて、
第一ソースおよび第二ソースからのデータにアクセスできる少なくとも１つの記憶ユニットと、
最適ルートを創成できる少なくとも１つの計算ユニットと、
ユーザに最適ルートを提示できる少なくとも１つのディスプレイ手段と、
前記方法を実施できる実行命令とを有することを特徴とするデバイス。
【請求項１６】
自動車に搭載して使用することを意図したことを特徴とする請求項１５記載のデバイス。
【請求項１７】
前記記憶ユニットおよび計算ユニットは中央制御され、かつ分散制御される多数の周辺ステーションが、前記方法に従って作成された最適ルートにアクセスできるようにすることを特徴とする請求項１５記載のデバイス。
【請求項１８】
前記分散制御されるステーションは、ネットワーク特にグローバルネットワークを介して、中央制御されるユニットに接続できることを特徴とする請求項１７記載のデバイス。
【請求項１９】
請求項１５に記載のデバイスを有することを特徴とするコンピュータシステム。
【請求項２０】
請求項１〜１４のいずれか１項記載の方法を実施するための、プログラムされたコード要素を有するソフトウェアにおいて、コンピュータシステムにローディングされかつかつ該コンピュータシステムにより実行されることを特徴とするソフトウェア。
【請求項２１】
請求項２０に記載のプログラムされたコード要素を有することを特徴とする、コンピュータシステムにより読取り可能な媒体に記録された製品の形態をなすソフトウェア。
【請求項１】
第一地点αと第二地点βとの間の最適ルートを、少なくとも１つの基準ＣＯの関数として計算機により作成できるルート計算方法であって、少なくとも１つの記憶媒体に記憶されかつ１組の共通ノードを有する少なくとも第一ソースおよび第二ソースからのデジタルデータ特に地理的データを使用する段階を有し、第二ソースは、少なくとも１つの特性Ｋが第一ソースとは異なっているルート計算方法において、
ａ）地点αおよび第一ソースから、前記地点αに実質的に隣接しかつ第一ソースおよび第二ソースの両方に基準を有する複数のαノード（Ｎα）を決定し、かつ第一ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｂ）地点βおよび第三ソースから、前記地点βに実質的に隣接しかつ第三ソースおよび第二ソースの両方に基準を有する複数のβノード（Ｎβ）を決定し、かつ第三ソースおよび所与の基準ＣＯからのデータの関数として、各ノードについての第一最適値を決定する段階と、
ｃ）全対のノードＮα、Ｎβについての第二ソースからのデータおよび所与の基準ＣＯから、各対のノード（Ｎα、Ｎβ）の第二最適値を決定する段階と
ｃ）全対のノードＮα、Ｎβについての第二ソースおよび所与の基準ＣＯから、各対のノード（Ｎα、Ｎβ）についての第二最適値を決定する段階と
ｄ）α−βルートの組について、地点αから地点βに至る全ルートの最適化を可能にする最適ノードを決定する段階とを有することを特徴とするルート計算方法。
【請求項２】
前記ソースを区別する特性Ｋは、各ソースが保有する情報の関数であることを特徴とする請求項１記載のルート計算方法。
【請求項３】
前記段階ｃおよび段階ｄは、段階ａおよび段階ｂが完了すると、連続して遂行されることを特徴とする請求項１または２記載のルート計算方法。
【請求項４】
前記第一ソースは都市形式であり、第二ソースは都市間形式であることを特徴とする請求項１〜３のいずれか１項記載のルート計算方法。
【請求項５】
前記第三ソースは都市形式であることを特徴とする請求項１〜４のいずれか１項記載のルート計算方法。
【請求項６】
前記共通ノードの組は、１つ以上のソースで識別された或るノードが一緒にリンクされている、前のマッチング段階から得られることを特徴とする請求項１〜５のいずれか１項記載のルート計算方法。
【請求項７】
前記地点αは例えばルートの出発地点であり、地点βはルートの目的地点であることを特徴とする請求項１〜６のいずれか１項記載のルート計算方法。
【請求項８】
前記第三ソースは、第一ソースに実質的に一致することを特徴とする請求項１〜７のいずれか１項記載のルート計算方法。
【請求項９】
前記第三ソースは、第一ソースの限定セクタに実質的に一致することを特徴とする請求項１〜８のいずれか１項記載のルート計算方法。
【請求項１０】
前記αノードは地点αに一致することを特徴とする請求項１〜９のいずれか１項記載のルート計算方法。
【請求項１１】
前記βノードは地点βに一致することを特徴とする請求項１〜１０のいずれか１項記載のルート計算方法。
【請求項１２】
前記ノード（Ｎα、Ｎβ）の第一および第二最適値は、ＤＩＪＫＳＴＲＡから得られるアルゴリズムに基いて決定されることを特徴とする請求項１〜１１のいずれか１項記載のルート計算方法。
【請求項１３】
前記ノードまたはルートの最適値は、少なくとも１つの基準ＣＲＩの関数として確立されることを特徴とする請求項１〜１２のいずれか１項記載のルート計算方法。
【請求項１４】
前記基準ＣＲＩは予確立されたリストからユーザにより選択され、前記リストは、
・αとβとの間の実質的な最短ルートを決定することを目的とするＣＲ１１と、
・αとβとの間の実質的な最高速ルートを決定することを目的とするＣＲ１２と、
・αとβとの間の自動車道路の使用優先性を実質的に与えるルートを決定することを目的とするＣＲ１３と、
・αとβとの間の自動車道路の使用を本質的に回避するルートを決定することを目的とするＣＲ１４と、
・通行料金に関して実質的に最も安いルートを決定することを目的とするＣＲ１５と、
・最も快適なルートを決定することを目的とするＣＲ１６と、
・本質的に最も混雑していないルートを決定することを目的とするＣＲ１７と、
・少なくとも１つの所望地点を通るルートを決定することを目的とするＣＲ１８とを有することを特徴とする請求項１〜１３のいずれか１項記載のルート計算方法。
【請求項１５】
請求項１〜１４のいずれか１項記載の方法を実施するデバイスにおいて、
第一ソースおよび第二ソースからのデータにアクセスできる少なくとも１つの記憶ユニットと、
最適ルートを創成できる少なくとも１つの計算ユニットと、
ユーザに最適ルートを提示できる少なくとも１つのディスプレイ手段と、
前記方法を実施できる実行命令とを有することを特徴とするデバイス。
【請求項１６】
自動車に搭載して使用することを意図したことを特徴とする請求項１５記載のデバイス。
【請求項１７】
前記記憶ユニットおよび計算ユニットは中央制御され、かつ分散制御される多数の周辺ステーションが、前記方法に従って作成された最適ルートにアクセスできるようにすることを特徴とする請求項１５記載のデバイス。
【請求項１８】
前記分散制御されるステーションは、ネットワーク特にグローバルネットワークを介して、中央制御されるユニットに接続できることを特徴とする請求項１７記載のデバイス。
【請求項１９】
請求項１５に記載のデバイスを有することを特徴とするコンピュータシステム。
【請求項２０】
請求項１〜１４のいずれか１項記載の方法を実施するための、プログラムされたコード要素を有するソフトウェアにおいて、コンピュータシステムにローディングされかつかつ該コンピュータシステムにより実行されることを特徴とするソフトウェア。
【請求項２１】
請求項２０に記載のプログラムされたコード要素を有することを特徴とする、コンピュータシステムにより読取り可能な媒体に記録された製品の形態をなすソフトウェア。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２００６−５０２３７７（Ｐ２００６−５０２３７７Ａ）
【公表日】平成１８年１月１９日（２００６．１．１９）
【国際特許分類】
【出願番号】特願２００３−５５３１９６（Ｐ２００３−５５３１９６）
【出願日】平成１４年１２月１７日（２００２．１２．１７）
【国際出願番号】ＰＣＴ／ＥＰ２００２／０１４３９６
【国際公開番号】ＷＯ２００３／０５２３５１
【国際公開日】平成１５年６月２６日（２００３．６．２６）
【出願人】（５９９０９３５６８）ソシエテ ド テクノロジー ミシュラン (552)
【Ｆターム（参考）】
【公表日】平成１８年１月１９日（２００６．１．１９）
【国際特許分類】
【出願日】平成１４年１２月１７日（２００２．１２．１７）
【国際出願番号】ＰＣＴ／ＥＰ２００２／０１４３９６
【国際公開番号】ＷＯ２００３／０５２３５１
【国際公開日】平成１５年６月２６日（２００３．６．２６）
【出願人】（５９９０９３５６８）ソシエテ ド テクノロジー ミシュラン (552)
【Ｆターム（参考）】
[ Back to top ]