JP2012168169A - 乗り物のナビゲーションデバイスおよび方法 - Google Patents

Abstract

【課題】ルートサーチおよびルートガイダンスにおいて、追い越し車線を考慮に入れ得る乗り物のナビゲーションデバイスおよび方法を提供すること。
【解決手段】乗り物のナビゲーションデバイス（１）は、マップデータを格納するマップデータベース（３）と処理ユニット（２）とを含む。マップデータベース（３）は、追い越し車線の存在を示す第一の属性と、車線に割り当てられることによって道路セグメントのどの車線が追い越し車線かを示す第二の属性とを含む。処理ユニット（２）は、マップデータベース（３）に結合され、ルートサーチを少なくとくとも第一の属性に基づいて行うことと、ルートガイダンス情報の出力をユーザーインターフェース（４）を介して少なくとも第二の属性に基づいて制御することとを行うように構成されている。
【選択図】図１

Description

（技術分野）
本発明は、マップデータを格納するマップデータベースを含む乗り物のナビゲーションデバイス、マップデータベースを生成する方法、およびマップデータベースに格納されたデータを処理する方法に関する。本発明は、特に、マップデータベースが属性を含み得るこのようなデバイスおよび方法に関する。

（背景）
ナビゲーションデバイスは、マップデータを用いて開始ポイントから目的地までのルートを決定するように既知である。概して、これらのナビゲーションデバイスは、コスト関数を最小化するルートに対するサーチを行い得る。コスト関数は、移動時間、ルートに関連付けられた距離または燃料コスト、または最小化されるべき任意の他の適切な量を表し得る。最適化であるルートは、好みのオプションまたは回避のオプションの起動に依存し得る。高速道路、フェリーまたはトンネルに対する好みのオプションおよび回避のオプションが提供され得る。

ルート決定に加えて、ナビゲーションデバイスはまた、ユーザーインターフェースを介してルートガイダンス機能を提供し得る。ガイダンス情報の提供は、光学またはオーディオ指示と組み合わせ可能である、乗り物の周囲の道路ネットワークの一部分についての情報をドライバーに提供する光学またはオーディオ出力の生成を含み得る。

データがルートサーチおよびルートガイダンスに対して有効に使用されることを可能にするマップデータベースの提供および使用は、相当な挑戦を表し得る。例示として、ルートサーチのために、道路ネットワークの微細構造に関する情報は、通常、開始ポイントと目的地との両方から離れた場所に対して要求されない。しかし、開始ポイントと目的地との両方から離れた場所における少なくともあるタイプの道路（例えば、高速道路）に関する情報は、ルートサーチのために要求される。対照的に、ガイダンス機能は、乗り物の周囲の範囲のみにおける情報を要求し得、より大きなレベルの詳細では要求しない。

多くの道路ネットワークは、いわゆる追い越し車線を含む。そのような追い越し車線は、しばしば都市部とその近郊において見られ得る。一般的に、追い越し車線は、本明細書において、設備への入口および出口ポイントの数を限定することによって管理されている車線へのアクセスを有する車線として理解される。つまり、通常の車線の全てのアクセスまたは出口ポイントが追い越し車線のアクセスまたは出口ポイントになるわけではない。追い越し車線は、主要な車道通路内に提供された汎用受け入れ能力から物理的に分離され得るか、または柵で囲まれ得る。もしくは、追い越し車線は、道路マーキングによって汎用受け入れ能力から分離され得る。追い越し車線は、両流設備または双方向設備として動作され得る。

そのため、ルートサーチおよびルートガイダンスにおいて、追い越し車線を考慮に入れ得る乗り物のナビゲーションデバイスおよび方法を提供する必要性がある。

（概要）
この必要性は、独立請求項に記述されるデバイスおよび方法によって対処される。従属請求項は、実施形態を規定する。

局面に従って、マップデータベースおよび処理ユニットを含む乗り物のナビゲーションデバイスが提供される。マップデータベースは、リンクおよび属性を含むマップデータを格納する。リンクは、道路セグメントを表す。第一の属性は、それぞれリンクのサブセットに割り当てられ、サブセットに含まれるリンクが少なくなくとも１つの追い越し車線を有することを示す。第二の属性は、それぞれサブセットに含まれるリンクの少なくとも一部の車線に割り当てられ、それぞれの道路セグメントのどの車線が追い越し車線かを示す。処理ユニットは、マップデータベースに結合され、ルートサーチを少なくとも第一の属性に基づいて行うことと、ルートガイダンス情報の出力をユーザーインターフェースを介して少なくとも第二の属性に基づいて制御することとを行うように構成されている。

ナビゲーションデバイスにおいて、追い越し車線を示す第一および第二の属性が用いられる。このことは、追い越し車線がルートサーチとルートガイダンスとの両方において考慮に入れられることを可能にする。第一および第二の属性は、マップデータベースの別個の部分に格納され得る。これは、処理ユニットが第一の属性が格納されている部分にアクセスすることによって、追い越し車線を考慮に入れたルートサーチを行い、第二の属性が格納されている部分にアクセスすることによって、追い越し車線を考慮に入れたルートガイダンスを行うことを可能にする。

マップデータベースは、各リンクに対するデータ構造を含み得る。データ構造は、固定された数のデータフィールドを有する。値は、それぞれ、各データフィールドに対して設定される。第一の属性および第二の属性は、リンクに対するデータ構造から分離して格納され得る。次いで、マップデータベースは、少なくとも１つの追い越し車線を含むリンクのみに対して、第一および第二の属性を含むことを要求される。それによって、格納スペース要件が減少され得る。

第一の属性は、ブーリアンパラメータを有し得る。処理ユニットは、ルートサーチをリンクに対して第一の属性とブーリアンパラメータとの両方に基づいて行うように構成され得る。ブーリアンパラメータは、回避および好みのオプションが追い越し車線に対して実装されることを可能にする。

マップデータベースにおいて、ブーリアンパラメータが第一の値に設定された第一の属性は、それぞれ、追い越し車線から全体が構成されるリンクに割り当てられ得る。ブーリアンパラメータが第一の値とは異なる第二の値に設定された第一の属性は、それぞれ、少なくとも１つの非追い越し車線を含むリンクに割り当てられ得る。これは、回避および好みのオプションが追い越し車線に対して実装されることを可能にする。

第一の属性は、パラメータを有し得、特に、整数パラメータタイプのパラメータを有し得る。パラメータは、車線の数を示し得る。処理ユニットは、ルートサーチをリンクに対して第一の属性とパラメータとの両方に基づいて行うように構成され得る。

マップデータベースは、第一の部分および第二の部分を含み得る。第一の属性は、第一の部分に格納され、第二の属性は、第二の部分に格納される。処理ユニットは、ルートガイダンス情報の出力を第二の部分から検索されたデータに基づき、第一の部分に格納されたデータから独立して制御するように構成され得る。あるいは、またはさらに、処理ユニットは、ルートサーチを第一の部分から検索されたデータに基づき、第二の部分に格納されたデータから独立して行うように構成され得る。そのようなマップデータベースによって、情報は、マップデータベースからルートサーチまたはルートガイダンスのために効率的に検索され得る。ルートサーチを行うとき、回避または好みのオプションが追い越し車線に対して選択された場合、処理ユニットは、コストモデルにおけるリンクのコストを第一の属性に基づいて調節するように構成され得る。

第一の部分および第二の部分は、別個のテーブルであり得る。第一の部分は、マップデータベースのルート層を表し得る。第二の部分は、マップデータベースのガイダンス層を表し得る。第一の部分および第二の部分は、別個のテーブルに格納される必要はないが、論理的に異なるファイルの部分に格納され得る。

乗り物のナビゲーションデバイスは、マップデータベースにおけるデータを組織化または処理するためにタイリングを用い得る。そのようなタイリングおよびマップデータベースにおけるデータの対応する組織化の規定は、局所更新を容易にする。道路ネットワークにおける局所変更の結果から生じるマップデータにおける変更は、全部のマップデータベースの交換を要求せずに収容され得る。マップデータベースは、リンクのうちの少なくとも１つが少なくとも１つの追い越し車線を有する場合のみ、タイリングのタイルに配置されたリンクに対して第一の属性を含み得る。少なくとも１つの追い越し車線を有するリンクがないタイルに対する第一の属性を省略することによって、格納スペース要件が減少され得る。

乗り物のナビゲーションデバイスは、さらなるタイリングをガイダンス機能に対して用い得る。さらなるタイリングは、ルート機能に対して用いられるタイリングと同一であり得るか、または異なり得る。マップデータベースは、タイルに配置された道路セグメントのうちの少なくとも１つが少なくとも１つの追い越し車線を有する場合のみ、さらなるタイリングのタイルに配置された道路セグメントの車線に対して第二の属性を含み得る。少なくとも１つの追い越し車線を有するリンクがないタイルに対する第二の属性を省略することによって、格納スペース要件が減少され得る。

マップデータベースは、ナビゲーションデータ規格（ＮＤＳ）に従うマップデータベースであり得る。

別の局面に従って、マップデータベースを生成する方法が提供される。道路セグメントに関する情報および各道路セグメントの車線に関する情報を含むデータが検索される。複数の道路セグメントに対して、道路セグメントが少なくとも１つの追い越し車線を有するか否かが決定される。第一の属性は、道路セグメントの少なくとも１つの車線が追い越し車線である場合、道路セグメントを表すリンクに選択的に割り当てられる。第二の属性は、道路セグメントを表すリンクの車線に選択的に割り当てられる。第二の属性は、道路セグメントのどの車線が追い越し車線かに基づいて選択的に割り当てられる。第一の属性および第二の属性は、マップデータベースに格納される。

そのような方法は、マップデータベースが乗り物のナビゲーションデバイスにおける利用のために生成されることを可能にする。マップデータベースは、それぞれ追い越し車線を示す第一および第二の属性を含む。第一および第二の属性は、マップデータベースが乗り物のナビゲーションデバイスに配備された場合、それぞれ、ルートサーチおよびルートガイダンスのために用いられ得る。

第一の属性を選択的に割り当てることは、第一の属性のパラメータを道路セグメントの全ての車線が追い越し車線か否かに基づいて設定することを含み得る。パラメータは、マップデータベースに格納され得る。パラメータは、回避および好みのプションが追い越し車線に対して実装されることを可能にする。

第一の属性は、マップデータベースの第一の部分に格納され得、第二の属性は、マップデータベースの第二の部分に格納され得る。第一の部分は、ルートサーチのためのデータを表し得、第二の部分は、ルートガイダンス情報を出力するためのデータを表し得る。そのようなマップデータベースによって、情報は、ルートサーチまたはルートガイダンスのためにマップデータベースから効率的に検索され得る。

第一の部分は、第一のテーブルであり得、第二の部分は、第一のテーブルから分離した第二のテーブルとして形成され得る。第一および第二のテーブルは、例えば、ＳＱＬデータベースのテーブルであり得る。

複数のタイルを含み、道路セグメントを含むタイリングが規定され得る。マップデータベースは、タイリングのいずれか所与のタイルに配置された道路セグメントに関連付けられたデータがマップデータベースにおいて識別され得るように、データをマップデータベースに格納することによって生成され得る。

タイリングの各タイルに対して、第一の属性は、タイリングのそれぞれのタイルに含まれる少なくとも１つの道路セグメントが少なくとも１つの追い越し車線を含む場合のみ、マップデータベースに格納され得る。少なくとも１つの追い越し車線を有するリンクがないタイルに対して第一の属性を省略することによって、格納スペース要件が減少され得る。

同様に、さらなるタイリングは、ルートガイダンスに関連付けられたデータを組織化するために規定され得る。さらなるタイリングは、タイリングと同一であり得る。さらなるタイリングの各タイルに対して、第二の属性は、さらなるタイリングのそれぞれのタイルに含まれる少なくとも１つの道路セグメントが少なくとも１つの追い越し車線を含む場合のみ、マップデータベースに格納され得る。少なくとも１つの追い越し車線を有するリンクがないタイルに対して第二の属性を省略することによって、格納スペース要件が減少され得る。

別の局面に従って、マップデータベースに格納されたデータを処理する方法が提供される。マップデータベースは、道路セグメントを表すリンクと、第一および第二の属性とを含む。第一の属性は、リンクのサブセットに割り当てられ、第二の属性は、リンクのサブセットの少なくとも一部の車線に割り当てられる。方法において、ルートサーチが行われる。追い越し車線に対する好みまたは回避のオプションの起動が監視される。ルートのコストは、好みまたは回避のオプションが起動された場合、リンクに割り当てられた第一の属性に基づいて、選択的に調節される。方法において、ルートガイダンス情報が出力される。ルートガイダンス情報は、第二の属性に基づいて、出力される。

ルートサーチを行うことは、好みまたは回避のオプションが起動された場合、第一の属性が割り当てられるリンクを識別することと、リンクに対するコストモデルにおけるコストを選択的に増やす、または減らすこととを含み得る。

ルートガイダンス情報を出力することは、追い越し車線である乗り物の周囲状況における車線を第二の属性に基づいて、識別することと、オーディオまたは光学出力を識別された車線に基づいて改変することと含み得る。

ルートサーチは、第二の属性から独立して行われ得る。あるいは、またはさらに、ルートガイダンス情報を出力することが、第一の属性から独立して行われ得る。

マップデータベースは、いずれか一局面または実施形態に従うマップデータを生成する方法によって生成されたマップデータベースであり得る。

別の局面に従って、リンクおよび属性を含むマップデータベースを格納するデータキャリアーが提供される。リンクは、道路セグメントを表し、第一の属性は、それぞれ、リンクのサブセットに割り当てられ、サブセットに含まれるリンクが少なくとも１つの追い越し車線を有することを示す。第二の属性は、それぞれ、サブセットに含まれるリンクの少なくとも一部の車線に割り当てられ、それぞれの道路セグメントのどの車線が追い越し車線かを示す。第二の属性は、第一の属性とは異なる。

さらに別の局面に従って、ナビゲーションデータ規格（ＮＤＳ）に従って構成されているマップデータベースを格納し、追い越し車線を示す少なくとも１つの属性を含むデータキャリアーが提供される。

上で言及し、下で説明する特徴は、それぞれの示された組み合わせだけで用いられ得るだけでなく、他の組み合わせまたは単独で用いられ得ることが理解されるべきである。

例えば、本発明は、以下の項目を提供する。
（項目１）
乗り物のナビゲーションデバイスであって、
該乗り物のナビゲーションデバイスは、
マップデータベース（１０）であって、該マップデータベース（１０）は、マップデータを格納し、該マップデータは、リンクおよび属性（６３、６４、８３、８６、９３、９８）を含み、該リンクは、道路セグメント（５１〜５９）を表し、第一の属性（６３、６４、８３、８６）は、それぞれ該リンクのサブセットに割り当てられることによって、該サブセットに含まれる該リンクが少なくとも１つの追い越し車線を有することを示し、第二の属性（９３、９８）は、それぞれ該サブセットに含まれる該リンクの少なくとも一部の車線に割り当てられることによって、該それぞれの道路セグメント（５１〜５３）のどの車線が追い越し車線かを示し、該第二の属性（９３、９８）は、該第一の属性（６３、６４、８３、８６）とは異なる、マップデータベース（１０）と、
処理ユニット（２）であって、該処理ユニット（２）は、該マップデータベース（１０）に結合され、該第一の属性（６３、６４、８３、８６）に少なくとも基づいてルートサーチを行うことと、ルートガイダンス情報の出力を、ユーザーインターフェース（４）を介して少なくとも該第二の属性（９３、９８）に基づいて制御することとを行うように構成されている、処理ユニット（２）と
を含む、乗り物のナビゲーションデバイス。
（項目２）
上記マップデータベース（１０）は、各リンクに対してデータ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）を含み、該データ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）は、リンクに対して固定された数のデータフィールドを有し、値は、それぞれ各データフィールドに対して設定されており、
上記第一の属性（６３、６４、８３、８６）および上記第二の属性（９３、９８）は、該データ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）から分離して格納される、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目３）
上記第一の属性（６３、６４、８３、８６）は、ブーリアンパラメータを有し、
上記処理ユニット（２）は、リンクに対するルートサーチを、該第一の属性（６３、６４、８３、８６）と該ブーリアンパラメータとの両方に基づいて行うように構成されている、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目４）
上記マップデータベース（１０）において、上記ブーリアンパラメータが第一の値に設定された上記第一の属性（６３、８３）は、それぞれ、リンク（５１、５２）へ割り当てられ、該リンク（５１、５２）は、追い越し車線で全体が構成され、該ブーリアンパラメータが該第一の値とは異なる第二の値に設定された該第一の属性（６４、８６）は、それぞれ、リンク（５３）へ割り当てられ、該リンク（５３）は、少なくとも１つの追い越し車線と少なくとも１つの非追い越し車線とを含む、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目５）
上記マップデータベース（１０）は、第一の部分（１１）および第二の部分（１４）を含み、上記第一の属性（６３、６４、８３、８６）は、該第一の部分（１１）に格納され、上記第二の属性（９３、９８）は、該第二の部分（１４）に格納され、
上記処理ユニット（２）は、該第二の部分（１４）から検索され、該第一の部分（１１）に格納されたデータから独立しているデータに基づいて、上記ルートガイダンス情報の出力を制御するように構成されている、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目６）
上記第一の部分（１１）は、第一のテーブルであり、上記第二の部分（１４）は、該第一のテーブル（１１）とは異なる第二のテーブルである、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目７）
各道路セグメント（５１〜５９）は、タイリングの少なくとも１つのタイル（５０、７１〜７４）に配置され、
上記マップデータベース（１０）は、リンクによって表された該道路セグメント（５１〜５３）の少なくとも１つが少なくとも１つの追い越し車線を有する場合ののみ、該タイリングのタイル（５０、７１〜７４）に配置された該リンク（５１〜５３）に対する上記第一の属性（６３、６４、８３、８６）を含む、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目８）
各リンクは、さらなるタイリングの少なくとも１つのタイル（７１〜７４）に配置され、
上記マップデータベース（１０）は、該さらなるタイリングのタイル（７１〜７４）に配置された道路セグメント（５１〜５９）の少なくとも１つが少なくとも１つの追い越し車線を有する場合にのみ、該さらなるタイリングの該タイル（７１〜７４）に配置された該道路セグメント（５１〜５９）の車線に対する上記第二の属性（９３、９８）を含む、上記項目のいずれかに記載の乗り物のナビゲーションデバイス。
（項目９）
マップデータベース（１０）を生成する方法であって、
該方法は、
道路セグメント（５１〜５９）に関する情報と各道路セグメントの車線に関する情報とを含むデータを検索することと、
複数の道路セグメント（５１〜５９）に対して、
該道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を有するか否かを決定することと、
該道路セグメント（５１〜５９）の少なくとも１つの車線が追い越し車線である場合、第一の属性（６３、６４、８３、８６）を該道路セグメント（５１〜５９）を表すリンクに選択的に割り当てることと、
第二の属性（９３、９８）を該道路セグメント（５１〜５９）の車線に選択的に割り当てることであって、該第二の属性は（９３、９８）は、該道路セグメント（５１〜５９）のどの車線が追い越し車線かに基づいて選択的に割り当てられる、ことと
を行うことと、
該第一の属性（６３、６４、８３、８６）および第二の属性（９３、９８）を該マップデータベース（１０）に格納することと
を含む、方法。
（項目１０）
上記第一の属性（６３、６４、８３、８６）を選択的に割り当てることは、該第一の属性（６３、６４、８３、８６）のパラメータを上記道路セグメント（５１〜５９）の全ての車線が追い越し車線であるか否かに基づいて設定することを含み、該パラメータは、上記マップデータベース（１０）に格納される、上記項目のいずれかに記載の方法。
（項目１１）
上記第一の属性（６３、６４、８３、８６）は、上記マップデータベース（１０）の第一の部分（１１）に格納され、上記第二の属性（９３、９８）は、該マップデータベース（１０）の第二の部分（１４）に格納され、該第一の部分（１１）は、ルートサーチのためのデータを表し、該第二の部分（１４）は、ルートガイダンス情報を出力するためのデータを表す、上記項目のいずれかに記載の方法。
（項目１２）
複数のタイル（５０、７１〜７４）を含み、上記道路セグメント（５１〜５９）をカバーするタイリングが規定され、
該タイリングの各タイル（５０、７１〜７４）に対して、第一の属性（６３、６４、８３、８６）は、該タイリングの上記それぞれのタイル（５０、７１〜７４）に含まれる少なくとも１つの道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を含む場合にのみ、上記マップデータベース（１０）に格納される、上記項目のいずれかに記載の方法。
（項目１３）
複数のタイル（７１〜７４）を含み、上記道路セグメント（５１〜５９）をカバーするさらなるタイリングが規定され、
該さらなるタイリングの各タイル（７１〜７４）に対して、第二の属性（９３、９８）は、該さらなるタイリング（７１〜７４）の上記それぞれのタイルに含まれる少なくとも１つの道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を含む場合にのみ、上記マップデータベース（１０）に格納される、上記項目のいずれかに記載の方法。
（項目１４）
マップデータベース（１０）に格納されたデータを処理する方法であって、該マップデータベース（１０）は、道路セグメント（５１〜５９）を表すリンクと、第一の属性（６３、６４、８３、８６）と、第二の属性（９３、９８）とを格納し、該第一の属性（６３、６４、８３、８６）は、リンク（５１〜５３）のサブセットに割り当てられ、該第二の属性（９３、９８）は、該リンク（５１〜５３）のサブセットの少なくとも一部の車線に割り当てられ、該方法は、
ルートサーチを行うことであって、該ルートサーチを行うことは、
追い越し車線に対する好みまたは回避のオプションの起動を監視することと、該好みまたは回避のオプションが起動された場合、リンクに割り当てられた該第一の属性（６３、６４、８３、８６）に基づいて、ルートのコストを選択的に調節することと
を含む、ことと、
ルートガイダンス情報を該第二の属性（９３、９８）に基づいて出力することと
を含む、方法。
（項目１５）
上記ルートサーチは、上記第二の属性（９３、９８）から独立して行われ、該ルートガイダンス情報の出力は、上記第一の属性（６３、６４、８３、８６）から独立して行われる、上記項目のいずれかに記載の方法。

（摘要）
乗り物のナビゲーションデバイス（１）は、マップデータを格納するマップデータベース（３）と処理ユニット（２）とを含む。マップデータベース（３）は、追い越し車線の存在を示す第一の属性と、車線に割り当てられることによって道路セグメントのどの車線が追い越し車線かを示す第二の属性とを含む。処理ユニット（２）は、マップデータベース（３）に結合され、ルートサーチを少なくとくとも第一の属性に基づいて行うことと、ルートガイダンス情報の出力をユーザーインターフェース（４）を介して少なくとも第二の属性に基づいて制御することとを行うように構成されている。

添付の図面に関連して読んだ場合、実施形態の先述および他の特徴が以下の実施形態の詳細な説明からより明らかになる。図面において、類似の参照数字は、類似の要素を指す。

図１は、実施形態に従うナビゲーションデバイスの概略ブロック図である。 図２は、マップデータベースの概略表示である。 図３は、ルートサーチを実施形態に従う方法において行う手続きのフローチャートである。 図４は、ルートサーチにおける追い越し車線属性の利用を例示するフローチャートである。 図５は、ルートガイダンス情報を実施形態に従う方法において出力する手続きのフローチャートである。 図６は、道路ネットワークの一部を例示する。 図７は、マップデータベースのルート層の構造を説明する概略図である。 図８は、図６の道路ネットワークの一部を別のレベルにおいて例示する。 図９は、マップデータベースのルート層の構造を図７のレベルとは異なるレベルにおいて説明する概略図である。 図１０は、マップデータベースのガイダンス層の構造を説明する概略図である。 図１１は、マップデータベースを生成する方法のフローチャートである。

（詳細な説明）
図１は、実施形態に従う乗り物のナビゲーションデバイス１を概略的に例示する。ナビゲーションデバイス１は、（例えば、メモリに格納された制御指令に従う）ナビゲーションデバイス１の動作を制御する処理ユニット２を含む。処理ユニット２は、例えば、１つ以上のマイクロプロセッサ、デジタルシグナルプロセッサまたは特定用途向け集積回路の形態である中央処理装置を含み得る。ナビゲーションデバイス１は、メモリ３に格納されたマップデータベースをさらに含む。メモリ３は、ランダムアクセスメモリ、フラッシュメモリまたはハードドライブのようなさまざまなタイプのメモリのうちのいずれか１つ、またはいずれかの組み合わせを含み得るが、コンパクトディスク（ＣＤ）、ＤＶＤ、メモリカードなどのようなリムーバブルメモリも含み得る。ナビゲーションデバイス１は、また、ガイダンス情報をユーザーへ出力する出力インターフェース４を含む。出力インターフェース４は、光学出力デバイス、オーディオ出力デバイスまたはそれらの組み合わせを含み得る。ナビゲーションデバイス１は、また、ユーザーがオプションを設定することを可能にする入力インターフェース５を含む。特に、入力インターフェース５は、ユーザーがルートサーチに対する好みのオプションまたは回避のオプションを設定することを可能にし得る。

ナビゲーションデバイスは、位置センサーおよび／またはワイヤレス受信器および／または乗り物インターフェースのようなさらなる構成要素を含み得る。位置センサーは、ナビゲーションデバイス１がインストールされた乗り物の現在の位置を決定するように適合され得る。位置センサーは、ＧＰＳ（全地球測位システム）センサー、ガリレオセンサー、モバイル通信網に基づいた位置センサーなどを含み得る。ワイヤレス受信器は、メモリ３に格納されたマップデータベースを更新する情報を受信するように構成され得る。車インターフェースは、処理ユニット２が他の乗り物システムからの情報または乗り物状態情報を乗り物インターフェースを介して得ることを可能にし得る。乗り物インターフェースは、例えば、ＣＡＮ（コントローラーエリアネットワーク）またはＭＯＳＴ（メディアオリエンテッドデバイストランスポート）インターフェースを含み得る。

メモリ３は、マップデータを含むマップデータベースを格納する。マップデータベースは、道路セグメントを表すリンクおよび属性に関する情報を含む。マップデータベースは、特に、リンクによって表された道路セグメントが追い越し車線を含むか否かを示す属性を含む。異なる第一の属性および第二の属性は、プロセッサにリンクが少なくとも１つの追い越し車線を含むことを通知するか、および／または道路セグメントのどの車線が追い越し車線かに関する情報を提供するために提供され得る。

プロセッサ２は、ユーザーが追い越し車線に対して好みのオプションまたは回避のオプションを入力インターフェース５を介して設定した場合、ルートサーチを行うために第一の属性を用い得る。プロセッサ２は、車線に割り当てられた第二の属性から独立してルートサーチを行い得る。プロセッサ２は、出力インターフェース５を介したルートガイダンス情報の出力の制御のために第二の属性を用い得る。プロセッサ２は、ルートガイダンス情報の出力を第一の属性から独立して制御し得る。マップデータベースは、そのため、それぞれ追い越し車線に関連付けられた異なる第一の属性および第二の属性を含み得る。第一の属性は、ルートサーチのために用いられ、第二の属性は、ルートガイダンスのために用いられる。

一般的に、さまざまな属性がリンクに割り当てられ得、マップデータベースに格納され得る。属性は、リンクの開始および終了ポイントに関する情報またはマップトポロジーに関する他の情報を含み得る。そのような属性は、予め規定された数のデータフィールドを有するデータ構造に格納され得る。予め規定された数のデータフィールドは、マップデータベースに格納された各リンクまたは他のマップ特徴のために、それぞれ提供される。さらに、属性は、それぞれのリンク上に存在する場合のみ、リンクまたは他の特徴に選択的に割り当てられ得る。メモリ３に格納されたマップデータベースは、追い越し車線を示す属性を柔軟な属性として含む。柔軟な属性は、少なくとも１つの追い越し車線を含むリンクのみに対して選択的に格納される。追い越し車線を示す属性は、各リンクに対してマップデータベースに格納された固定フォーマットデータ構造から分離して格納され得る。

メモリ３に格納されたマップデータベースは、異なる論理層を含み得る。さらに、マップデータベースは、タイリングの異なる更新領域またはタイルに関連付けられた異なるブロックに分割され得る。そのような構造は、更新の実行を容易にする。これは、マップデータベースを道路ネットワークの局所変更に調節するマップデータベースの更新を行うために特に望ましい。次いで、そのような更新は、道路ネットワークにおける変更によって影響された更新領域またはタイルのみを更新することによって行われ得る。これは、更新がより時間効率な態様または無線更新としてより容易に行われることを可能にする。

図２は、マップデータベース１０の概略表示である。以下で説明する構造を有するマップデータベース１０は、乗り物のナビゲーションデバイス１のメモリ３に格納され得る。

マップデータベース１０は、複数の層１１および１４を含む。複数の層１１および１４は、ルート層１１およびガイダンス層１４を含む。ルート層１１は、ルートサーチを行うために要求される情報を含む。この情報は、リンクの開始ポイントおよび終了ポイントのような道路ネットワークのトポロジーに関する情報を含み得る。ルート層１１における情報は、さまざまなコストモデルに対するリンクに関連付けられたコストをさらに含み得る。ルート層１１における情報は、リンクのコストがルートサーチにおいて好みのオプションまたは回避のオプションに基づいて調節されることを可能にする属性をさらに含み得る。

ルート層１１において、異なるレベル１２、１３があり得る。異なるレベル１２、１３は、異なるレベルの詳細で道路ネットワークを表すデータを含む。例示として、道路ネットワークの全ての道路セグメントがレベル１３において存在し得るが、道路セグメントの一部は、より高いレベル１２において省略され得る。

ガイダンス層１４は、ルートガイダンスのために要求されるデータを含む。ガイダンス層１４は、ガイダンス情報の光学および／またはオーディオ出力のために要求されるデータを特に含み得る。ガイダンス層は、また、レベル構造を含み得る。異なるレベルにおけるデータは、異なるレベルの詳細で道路ネットワークを表す。

ルート層１１およびガイダンス層１４は、メモリに格納された別個のテーブルとして構成され得る。限定よりも例示として、ルート層１１は、ＳＱＬデータベースにおいてテーブルであり得、ガイダンス層１４は、ＳＱＬデータベースにおいて別のテーブルであり得る。ルート層１１およびガイダンス層１４は、別個のファイルに格納され得る。ルート層１１およびガイダンス層１４は、１つのファイルの論理的に異なった部分であり得る。

マップデータベース１０は、さらなる層１５〜１７を含み得る。ネーム層１５は、道路名、家屋番号などへの参照を含む。トラック層１６は、トラックまたはローリーのための特定の属性を含み得る。高度運転者支援システム（ＡＤＡＳ）層１７は、高度運転者支援のためのデータを含み得る。さらなるまたは代替の層が提供され得、例えば、興味のポイントのための層、音声表示のための層または基本マップ表示のための層である。

マップデータベース１０は、ナビゲーションデータ規格（ＮＤＳ）によって規定される構造を有し得る。ＮＤＳは、柔軟な属性が用いられることを可能にする。これは、追い越し車線を示す属性が、マップデータベース１０がＮＤＳに従って設定された場合に規定され、格納されることを可能にする。

追い越し車線を示す属性は、マップデータベースに格納される。第一の属性は、それぞれ、ルート層１１に格納されるデータのために用いられ得る。第一の属性は、各リンクに割り当てられ得、各リンクは、少なくとも１つの追い越し車線を含む。これは、好みのオプションが少なくとも１つの追い越し車線を含む道路セグメントに対して実装されることを可能にする。マップデータベース１０は、第一の属性を指向性リンクと非指向性リンクとの両方のために格納し得る。異なるタイプのリンクが区別されるようにマップデータベース１０が構造化された場合、マップデータベース１０は、第一の属性を全てのタイプのリンクのために格納し得る。例示として、マップデータベース１０がタイル境界にわたり延在するタイリングのタイルおよびルートリンク全体に配置されたベースリンクを含む場合、マップデータベース１０は、ベースリンクとルートリンクとの両方に振り当てられた第一の属性を格納し得る。

第一の属性は、ブーリアンパラメータであり得るパラメータを有し得る。いずれかのリンク（このリンクのために、第一の属性は、マップデータベース１０に格納される）に対して、道路セグメントの全ての車線が追い越し車線である場合、パラメータは、１つの値（例えば、ＴＲＵＥ）を有し得る。

追い越し車線でない少なくとも１つの車線がある場合、パラメータは、別の値（例えば、ＦＡＬＳＥ）を有し得る。第一の属性およびそのパラメータに基づいて、プロセッサ２は、いずれかの道路セグメントが追い越し車線から全体が構成されているか否かを決定し得る。その場合、追い越し車線に対する回避のオプションが選択された場合、コストは、ルートサーチにおいて増える。プロセッサ２は、また、いずれかの道路セグメントが少なくとも１つ（ｏｎ）の追い越し車線を有するか否かを決定し得、その場合、追い越し車線に対する好みのオプションが選択された場合、コストは、ルートサーチにおいて増える。

第一の属性は、固定フォーマットデータ構造から分離して格納され得る。固定フォーマットデータ構造は、マップデータベース１０に全てのリンクまたは他のマップ特徴のために格納される。そのため、各道路セグメントに対して、道路セグメントが追い越し車線を含むか否かを示すために設定されなければならないフラッグのための格納スペースを保存することは要求されない。各道路セグメントに対して、道路セグメントが追い越し車線から全体が構成されているか否かを示すために設定されなければならないフラッグのための格納スペースを保存することも要求されない。むしろ、そのような情報は、柔軟な属性として含まれる。第一の属性は、少なくとも１つの追い越し車線を含むリンクがない更新領域またはタイルに対して省略され得る。追い越し車線に関する情報を格納する格納スペース要件は、これによって、減少され得る。

ルートサーチを行う場合、プロセッサ２は、追い越し車線に対する回避のオプションまたは好みのオプションをルート層１１に格納された第一の属性およびそのパラメータに基づいて考慮に入れ得る。そのような手続きは、下で図３および図４を参照してより詳細に説明される。

追い越し車線を示す第二の属性は、ガイダンス層１４に格納され得る。第二の属性は、少なくとも１つの追い越し車線を含むそれらの道路セグメントのみのために選択的に格納され得る。いくつかの実装において、第二の属性は、道路セグメントが、追い越し車線である少なくとも１つの車線と、追い越し車線でない別の車線を有する場合のみ、道路セグメントの車線に選択的に割り当てられ得る。第二の属性は、ガイダンス層１４に格納され得ることによってプロセッサ２に各道路セグメントが少なくとも１つの追い越し車線を含むことを示し、道路セグメントのどの車線が追い越し車線かに関する情報をさらに提供し得る。第二の属性を車線に割り当てるために、さらなる情報がマップデータベース１０にリンクに対して選択的に格納され得る。リンクは、少なくとも１つの追い越し車線を含み、それぞれの道路セグメントのどの車線が追い越し車線かを示す。このさらなる情報は、車線マスクの形態で格納され得る。車線マスクは、追い越し車線である車線に対して１つの値（例えば、「１」）および追い越し車線でない車線に対して別の値（例えば、「０」）を有する。そのようなさらなる情報は、第二の属性を個々の車線に割り当てるために用いられ得る。

ナビゲーションデバイス１がルートガイダンスを行う場合、プロセッサ２は、ガイダンス層１４にアクセスし、ルートガイダンスのためのデータを検索する。一般的に、乗り物の周囲の範囲に関するデータのみがルートガイダンスのために検索されなければならない。道路セグメントのためのデータをガイダンス層１４から検索する場合、プロセッサ２は、第二の属性がそれぞれの道路セグメントの１つの車線または複数の車線に割り当てられているか否かを決定する。プロセッサ２は、第二の属性をどの車線が追い越し車線かを（例えば、車線マスクの形態で）示すさらなる情報にまとめ得、道路セグメントのどの車線が追い越し車線かを決定する。あるいは、第二の属性は、個々の車線に対して別個に格納され得る。

プロセッサ２は、ルートガイダンスを道路セグメントのどの車線が追い越し車線かに基づいて制御し得る。例えば、運転指示を有するオーディオ出力は、道路セグメントのどの車線が追い越し車線かに基づいて制御され得る。さらに、またはあるいは、運転指示を有する光学出力は、道路セグメントのどの車線が追い越し車線かに基づいて制御され得る。

第二の属性は、固定フォーマットデータ構造から分離して格納され得る。固定フォーマットデータ構造は、マップデータベース１０に全てのリンクまたは他のマップ特徴のために格納される。そのため、道路セグメントのどの車線が追い越し車線かを示す各道路セグメントに対して設定されなければならないフラッグのための格納スペースを保存することは要求されない。第二の属性は、少なくとも１つの追い越し車線を含む道路セグメントがない更新領域またはタイルに対して省略され得る。追い越し車線に関する情報を格納する格納スペース要件は、これによって、減少され得る。

ルートガイダンスを行う場合、プロセッサ２は、道路セグメントのどの車線が追い越し車線かをガイダンス層１４に格納された第二の属性に基づいて考慮に入れ得る。そのような手続きは、図５を参照して下でより詳細に説明される。

第一および第二の属性は、マップデータベース１０の異なる層に別個に格納されるが、追い越し車線情報に関連付けられたこの情報を格納するために要求されるオーバーヘッド格納スペースは、適度に保たれ得る。マップデータベース１０は、第一および第二の属性を少なくとも１つの追い越し車線を含むそれらの道路セグメントのみのために選択的に含む。さらに、異なる層１１および１４における別個の第一および第二の属性を用いることによって、マップデータベース１０へのアクセスがルートサーチとルートガイダンスとの両方において効率的に行われ得る。

図３〜５を参照して、乗り物のナビゲーションデバイス１のプロセッサ２によって行われ得る方法がより詳細に説明される。プロセッサ２は、図３および図４において例示されるルートサーチと、図５において例示されるルートガイダンスとを行い得る。

方法は、道路セグメントと、追い越し車線を示す属性とを表すリンクに関する情報を格納するマップデータベースを用いて行われ得る。マップデータベースは、図２または図６〜図１０を参照して説明する構成を有し得る。例示として、第一の属性は、図３〜図５において「ＥＸＰＲＥＳＳ＿ＲＯＡＤ」と呼ばれる。第一の属性のパラメータは、「ＡｌｌＬａｎｅｓ」と呼ばれ、第二の属性は、「ＥＸＰＲＥＳＳ＿ＬＡＮＥ」と呼ばれる。

図３は、ルートサーチを行う手続き２０のフローチャートである。２１において、ルートサーチが開始される。ルートサーチは、ユーザー入力に基づいて開始され得る。あるいは、またはさらに、ルートサーチは、また、所定の事象が検知された場合（例えば、ユーザーが以前にルートサーチにおいて見つけたルートを離れた場合）、自動的に開始され得る。

２２において、追い越し車線を有する道路に対する回避のオプションまたは好みのオプションが選択されたか否かが決定される。道路に対するそのような回避のオプションまたは好みのオプションの選択は、入力インターフェースを介してなされ得、乗り物のナビゲーションデバイスに格納され得る。

追い越し車線を有する道路に対して回避のオプションまたは好みのオプションが選ばれていないことが決定された場合、２３において、ルートサーチは、従来の方法でマップデータベースにおけるデータに基づいて行われる。第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤは、このルートサーチにおいて無視される。

追い越し車線を有する道路に対して回避のオプションまたは好みのオプションが選ばれたことが決定された場合、２４において、ルートサーチは、リンクのうちの一部に割り当てられた第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤを考慮に入れて行われる。第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤは、さまざまな方法で考慮に入れられ得る。例示として、追い越し車線を有する道路に対する全回避のオプションが設定された場合、追い越し車線の全てを構成する道路を表す全てのリンクは無視され得る。あるいは、またはさらに、リンクのコストは、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤが割り当てられたリンクに対して回避または好みのオプションに基づいて調節され得る。コストのそのような調節は、最速ルート（移動時間を最小化させる）、最短ルート（移動距離を最小化させる）または最少燃料消費ルート（燃料消費を最小化する）のようなさまざまなコストモデルのうちのいずれか１つに対してなされ得る。

図４は、ルートサーチにおけるリンクコストを第一の属性に基づいて調節する手続き３０のフローチャートである。手続き３０は、図３の手続き２０における２４において行われるルートサーチにおけるコスト調節を実装するために用いられ得る。

３１において、リンクはルートサーチにおいて識別される。リンクは、例えば、サーチアルゴリズムの拡張工程において識別され得る。リンクは、例えば、ダイクストラのアルゴリズムまたはＡ^＊アルゴリズムの拡張工程において識別され得る。あるいは、コストの調節は、例えば、ダイクストラのアルゴリズムまたはＡ^＊アルゴリズムを行う前に行われ得る。後者の場合、ＥＸＰＲＥＳＳ＿ＲＯＡＤ属性を有する全てのリンクは、これらのリンクのコストを調節するために、まず識別され得る。

３２において、識別されたリンクが識別されたリンクに割り当てられた第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤを有するか否かが決定される。この決定は、マップデータベースから検索されたデータに基づいてなされる。層になった構造を有するマップデータベースに対して、決定はルート層１１に格納された第一の属性に基づいてなされ得る。

識別されたリンクが識別されたリンクに割り当てられた第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤを有さないことが決定された場合、３３において、リンクのコストは、調節されないままになる。ルートサーチは、それぞれのコストモデルのコストを表すコストによって続き得る。

識別されたリンクが識別されたリンクに割り当てられた第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤを有することが決定された場合、３４において、追い越し車線に対する回避のオプションが設定されたか否かが決定される。

回避のオプションが設定されていないことが決定された場合、３５において、リンクのコストが減少される。それによって、追い越し車線を有する道路に対する好みのオプションが、リンクに対するコストを減少させることによって考慮に入れられる。リンクへは、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤが割り当てられる。リンクのコストを３５において減少させることは、さまざまな方法で行われ得る。例示として、それぞれのコストモデルのコストが１より小さい係数によって掛けられ得る。あるいは、値がそれぞれのコストモデルのコストから引かれ得る。リンクのコストを３５において減少させることは、数学的操作またはテーブルルックアップを用いて行われ得る。ルートサーチは、リンクに対する減少されたコストによって続き得る。

回避のオプションが設定されたことが決定された場合、３６において、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤのパラメータＡｌｌＬａｎｅｓがＴＲＵＥであるか否かが決定される。

第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤのパラメータＡｌｌＬａｎｅｓがＴＲＵＥでない場合、３８において、リンクのコストは調節されないままである。手続きは、それぞれのコストモデルのコストを表すコストによって続き得る。これは、回避のオプションが、追い越し車線でない少なくとも１つの車線を有する道路が避けられることを要求しないことを反映している。

第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤのパラメータＡｌｌＬａｎｅｓがＴＲＵＥでないことが決定された場合、３７において、リンクのコストが増やされる。リンクのコストを３７において増やすことは、さまざまな方法で行われ得る。例示として、それぞれのコストモデルのコストは、１より大きい係数によって掛けられ得る。あるいは、値がそれぞれのコストモデルのコストに加えられ得る。リンクのコストを３７において増やすことは、数学的操作またはテーブルルックアップを用いて行われ得る。ルートサーチは、リンクに対して増やされたコストによって続き得る。

追い越し車線に対する回避および好みのオプションを考慮に入れるルートサーチが図３および図４において例示されるが、ルートサーチは、追い越し車線の利用が完全に禁止されているオプションの変種も含み得る。そのような場合、それぞれのリンクは、ルートサーチにおける考慮から、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤおよびそのパラメータＡｌｌＬａｎｅｓに基づいて離され得る。

図５は、ルートガイダンス情報の出力を制御する手続き４０のフローチャートである。４１において、乗り物の現地の周囲環境における道路セグメントが識別される。道路セグメントは、現在の乗り物の位置に基づいて識別され得る。道路セグメントは、ルートサーチの結果に基づいてさらに識別され得る。４１において識別された道路セグメントは、全ての道路セグメントを含み得る。全ての道路セグメントに関する情報がガイダンス情報を出力するために要求される。

４２において、識別された道路セグメントのいずれか１つの車線が、その車線に割り当てられた第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥを有するか否かが決定される。この決定は、マップデータベースから検索されたデータに基づいてなされる。層になった構造を有するマップデータベースに対して、決定がガイダンス層１４に格納された第二の属性に基づいてなされ得る。

道路セグメントの車線が、その車線に割り当てられた第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥを有さないことが決定された場合、４５において、ガイダンス情報が出力される。この場合、ガイダンス情報は、第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥに基づいて改変されない。

道路セグメントの車線が、その車線に割り当てられた第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥを有することが決定された場合、４３において、それぞれの道路セグメントに対する車線の数およびタイプに関する情報が検索される。情報は、マップデータベースから検索され得る。マップデータベース１０のようなマップデータベースが層になった構造を有する場合、情報は、ガイダンス層１４から検索され得る。検索された情報は、道路セグメントの車線の数に関する情報を含み得る。検索された情報は、車線のうちのどれが追い越し車線かに関する情報を含み得る。

４４において、出力情報は、４３において検索された情報に基づいて調節される。出力情報を調節することは、道路セグメントのどの車線が追い越し車線かに基づいてスピーチ出力を調節することを含み得る。出力情報を調節することは、あるいは、またはさらに、道路セグメントのどの車線が追い越し車線かに基づいて光学出力を調節することを含み得る。光学出力情報は、例えば、追い越し車線を示す色彩マーキングまたは追い越し車線を示すグラフィックアイコンを用いて調節され得る。

次いで、４５において、ガイダンス情報が出力される。ガイダンス情報出力に４５において影響する道路セグメントが追い越し車線を含む場合、ガイダンス情報は、第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥによって提供される追い越し車線に関する情報に基づいて生成される。

図６〜図１０を参照して、追い越し車線を示す第一の属性および第二の属性の定義ならびにマップデータベースの構造がより詳細に説明される。

図６は、道路セグメント５１〜５５を含む道路ネットワークの概略図である。道路ネットワークを含むタイリングが規定される。タイリングは、タイル５０を含む。

複数の道路セグメント５１〜５５がラベル「ＲＳ１」、「ＲＳ５」によって、マップデータベースにおいて参照される。道路セグメントの一部は、少なくとも１つの追い越し車線を含み得る。例示として、マップデータベースにおいて、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメント５１および５２は、追い越し車線から全体が構成され得る。マップデータベースにおいて「ＲＳ３」とラベル付けされた道路セグメント５３は、少なくとも１つの追い越し車線と、追い越し車線でない少なくとも１つの車線とを有し得る。道路セグメント５４および５５は、いずれの追い越し車線も含まなくなり得る。

道路セグメント５１〜５５は、リンクによってマップデータベースにおいて示される。ルート層におけるデータとガイダンス層におけるデータとの両方は、それぞれタイルに従って組織化され得る。タイルにおいて、それぞれの道路セグメントが配置される。これは、局所更新がより容易に行われることを可能にする。

図７は、ルート層のセクション１２の概略表示である。セクション１２は、重要性がより低い道路セグメントを省略して、粗い解像度を有するレベルを表す。まだ、レベルにおいて存在している道路セグメントのセットは、例えば、機能的道路分類または他の道路セグメント特性に基づいて選択され得る。

ルート層のセクション１２は、タイル５０に関連付けられたデータ６１を含む。データ６１は、道路セグメント５１〜５５を表す各リンクに対してデータ構造を含む。このデータ構造は、６２おいて、道路セグメント５１〜５５を表すリンクに対して概略的に示される。データ構造は、各リンクに対して固定された数のデータフィールドを含む。データ構造は、予め規定された構造を有し得る。値は、各フィールドにおいて設定されなければならない。

マップデータベースは、リンクに割り当てられた第一の属性をさらに含み、それぞれのリンクが少なくとも１つの追い越し車線を含むことを示す。第一の属性は、また、データ６１にタイル５０のために格納され得る。タイル５０において、それぞれの道路セグメント５１〜５５が配置される。

タイル５０に対するデータ６１は、第一の属性６３を含み、ブーリアンパラメータは、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントに対して１つの値に設定される。これは、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントが追い越し車線から全体が構成されていることを示す。「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントには、ブーリアンパラメータが１つの値に設定された第一の属性６３が割り当てられる。

タイル５０に対するデータ６１は、第一の属性６４を含み、ブーリアンパラメータは、「ＲＳ３」とラベル付けされた道路セグメントに対して別の値に設定される。これは、「ＲＳ３」とラベル付けされた道路セグメントが少なくとも１つの追い越し車線を有するが、追い越し車線から全体は構成されていないことを示す。「ＲＳ３」とラベル付けされた道路セグメントには、ブーリアンパラメータが別の値に設定された第一の属性６４が割り当てられる。

第一の属性６３および６４は、リンクに対して予め規定されたデータ構造６２に含まれない。第一の属性６３および６４は、柔軟な属性である。第一の属性は、それぞれのタイルにおける少なくとも１つの道路セグメントが少なくとも１つの追い越し車線を有する場合のみ、タイルを表すルート層のデータ６１に含まれ得る。

図７において、第一の属性は、属性ＥＸＰＲＥＳＳ＿ＲＯＡＤとして示され、第一の属性のパラメータは、ＡｌｌＬａｎｅｓとして示される。

図８は、図６の道路ネットワークの概略図である。図８において、道路ネットワークは、より大きなレベルの詳細で例示される。図８および図６は、異なるレベルにおける同じ道路ネットワークを表すが、図８に例示されるレベルにおいて存在する道路ネットワークの道路セグメント５６〜５９は、図６に例示されるより粗いレベルにおいて省略される。

道路ネットワークは、道路セグメント５１〜５５および道路セグメント５６〜５９を含む。道路ネットワークを含むタイリング７０が規定される。タイリングは、タイル７１〜７４を含む。図８に例示される解像度のレベルにおいて、タイル７１〜７４のタイルサイズは、図６に例示されるより粗い解像度のレベルにおけるよりも小さくなるように選択される。

道路ネットワークは、タイルと、タイル境界にわたり延在する道路セグメントとの全体内に配置された道路セグメントを含み得る。道路セグメント５９は、タイル７３とタイル７４との間の境界にわたり延在する。マップデータベースにおけるデータを組織化するために、道路セグメント５９は、道路セグメント５９のトポロジーを反映する１つのリンクに関連付けられ得る。さらに、道路セグメント５９のジオメトリを反映する構造７５、７６が規定され得、それぞれ１つのタイルにのみ配置される。構造７５、７６は、ジオメトリラインと呼ばれ得る。

省略される道路セグメントがより少ないか、または全く道路セグメントが省略されない図８に示される解像度のレベルにおいて、ルート層およびガイダンス層におけるデータも、それぞれタイルごとの態様で組織化され得る。

図９は、ルート層のセクション１３の概略表示である。セクション１３は、道路ネットワークを図７のセクション１２より大きなレベルの詳細で表すレベルを表す。例示として、ルート層のセクション１３によって表される詳細のレベルは、全ての道路セグメントを含み得る。

ルート層のセクション１３は、タイル７１に関連付けられたデータ８１を含む。データ８１は、タイル７１内に配置された道路セグメント５１および５２を表す各リンクに対してデータ構造を含む。このデータ構造は、８２において、道路セグメント５１および５２を表すリンクのために概略的に示される。データ構造は、各リンクに対して固定された数のデータフィールドを含み、予め規定された構造を有する。値は、各フィールドにおいて設定されなければならない。

マップデータベースは、リンクに割り当てられた第一の属性をさらに含み、それぞれのリンクが少なくとも１つの追い越し車線を含むことを示す。第一の属性も、それぞれの道路セグメント５１および５２が配置されるタイル７１に対するデータ８１に格納され得る。

タイル７１に対するデータ８１は、第一の属性８３を含み、ブーリアンパラメータは、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントに対して１つの値（例えば、「ＴＲＵＥ」）に設定される。上で説明したように、これは、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントが追い越し車線から全体が構成されることを示す。「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントには、ブーリアンパラメータが１つの値に設定された第一の属性８３が割り当てられる。

ルート層のセクション１３は、タイル７２に関連付けられたデータ８４を含む。データ８４は、タイル７２内に配置された道路セグメント５３〜５５を表す各リンクに対してデータ構造を含む。このデータ構造は、８５において、道路セグメント５３〜５５を表すリンクのために概略的に示される。データ構造は、各リンクに対して固定された数のデータフィールドを含み、予め規定された構造を有する。値は、各フィールドにおいて設定されなければならない。

マップデータベースは、リンクに割り当てられた第一の属性をさらに含み、それぞれのリンクが少なくとも１つの追い越し車線を含むことを示す。第一の属性も、それぞれの道路セグメント５３〜５５が配置されるタイル７２に対するデータ８４に格納され得る。タイル７２に対するデータ８４は、第一の属性８６を含み、ブーリアンパラメータは、「ＲＳ３」とラベル付けされた道路セグメントに対して別の値（例えば、「ＦＡＬＳＥ」）に設定される。これは、「ＲＳ３」とラベル付けされた道路セグメントが少なくとも１つの追い越し車線を有するが、追い越し車線から全体は構成されないことを示す。「ＲＳ３」とラベル付けされた道路セグメントには、ブーリアンパラメータが別の値に設定された第一の属性８６が割り当てられる。

ルート層のセクション１３は、タイル７３に関連付けられたデータ８７と、タイル７４に関連付けられたデータ８９とを含む。データ８７は、タイル７３内に配置される道路セグメント５７、５８を表す各リンクと、道路セグメント５９の一部を表すジオメトリライン７６とに対するデータ構造を含む。この８８において概略的に示されるデータ構造は、予め規定された数およびタイプのフィールドを有する固定された属性から構成される。データ８９は、タイル７３内に配置される道路セグメント５６を表すリンクと、道路セグメント５９の一部を表すジオメトリライン７５とに対するデータ構造を含む。この９０において概略的に示されるデータ構造は、予め規定されたデータフィールドを有する固定された属性から構成される。

タイル７３および７４における道路セグメントのうち、追い越し車線を有するものがないとすると、第一の属性は、タイル７３および７４を表すデータ８７および８９に格納されない。第一の属性を追い越し車線を有する道路セグメントがないタイルに関連付けられたデータに格納することは要求されない。それによって、過剰な車線属性を実装するための格納スペース要件は、適度なままであり得る。

図９において、第一の属性は、属性ＥＸＰＲＥＳＳ＿ＲＯＡＤとして示され、第一の属性のパラメータは、ＡｌｌＬａｎｅｓとして示される。

図７および図９から見て取れるように、実施形態に従って、道路セグメント５１〜５３に対する第一の属性は、より高いレベルの道路セグメントを表すセクション１２と、より低いレベルで表し、より多くの道路セグメントを含むセクション１３との両方において格納され得る。

図１０は、再び図８の道路ネットワークに対するガイダンス層１４のセクションの概略表示である。ガイダンス層１４は、また、異なる正確度で道路ネットワークを表す複数のレベルを含み得るが、追い越し車線を示すために車線に割り当てられた第二の属性は、各レベルに含まれる必要はない。異なるレベルがある場合、第二の属性は、特に、省略される道路セグメントの数が最も少ないレベル（つまり、道路ネットワークが最も大きな詳細において表される基本レベル）において格納され得る。そのようなレベルのみが図１０において概略的に例示される。

ルート層における第一の属性は、ルート層の各異なるレベルにおいて存在し得るが、ガイダンス層が複数のレベルを有する場合、ガイダンス層のレベルのうちの１つにおいてのみ、第二の属性が含まれれば十分である。

ガイダンス層１４は、タイル７１に関連付けられたデータ９１を含む。データ９１は、タイル７１内に配置された道路セグメント５１および５２を表す各リンクに対してデータ構造を含む。このデータ構造は、９２において、道路セグメント５１および５２を表すリンクのために概略的に示される。データ構造は、各リンクに対して固定された数のデータフィールドを含み、予め規定された構造を有する。値は、各フィールドにおいて設定されなければならい。

マップデータベースは、リンクの車線に割り当てられた第二の属性をさらに含み、それぞれの車線が追い越し車線であることを示す。第二の属性も、それぞれの道路セグメント５１および５２が配置されるタイル７１に対するデータ９１に格納され得る。

タイル７１に対するデータ９１は、「ＲＳ１」および「ＲＳ２」とラベル付けされた道路セグメントに対して第二の属性９３を含む。さらなるデータ構造９４および９５は、第二の属性９３を道路セグメント５１および５２のうちの個々の車線に割り当てるために提供され得る。データ構造９４および９５は、道路セグメントのそれぞれの車線が追い越し車線の場合、「１」のような１つの値を有する車線マスクを表し得、道路セグメントのそれぞれの車線が追い越し車線でない場合、「０」のような別の値を表し得る。プロセッサは、第二の属性９３を道路セグメント５１の車線マスクを表すデータ構造９４にまとめ得、追い越し車線である道路セグメント５１のうちの車線を識別する。プロセッサは、第二の属性９３を道路セグメント５２の車線マスクを表すデータ構造９５にまとめ得、追い越し車線である道路セグメント５２のうちの車線を識別する。

ガイダンス層は、タイル７２に関連付けられたデータ９６を含む。データ９６は、タイル７２内に配置された道路セグメント５３〜５５を表す各リンクに対してデータ構造を含む。このデータ構造は、９７において、道路セグメント５３〜５５を表すリンクのために概略的に示される。データ構造は、各リンクに対して固定された数のデータフィールドを含み、予め規定された構造を有する。値は、各フィールドにおいて設定されなければならない。

タイル９８に対するデータ９６は、「ＲＳ３」とラベル付けされた道路セグメントに対して第二の属性９８を含む。さらなるデータ構造９９は、第二の属性９８を道路セグメント５３のうちの個々の車線に割り当てるために提供され得る。データ構造９９は、車線マスクを表し得る。プロセッサは、第二の属性９８を道路セグメント５３の車線マスクを表すデータ構造９９にまとめ得、追い越し車線である道路セグメント５３のうちの車線を識別する。

ガイダンス層１４は、タイル７３に関連付けられたデータ１００と、タイル７４に関連付けられたデータ１０２とを含む。データ１００は、タイル７３における道路セグメントに対して少なくとも固定された属性１０１を含む。データ１０２は、タイル７４における道路セグメントに対して少なくとも固定された属性１０３を含む。タイル７３および７４における道路セグメントのうち、追い越し車線を有するものがないとすると、第二の属性は、タイル７３および７４を表すデータ１００および１０２に格納されない。第二の属性を、追い越し車線を有する道路セグメントがないタイルに関連付けられたデータに格納することは要求されない。これによって、過剰な車線属性を実装する格納スペース要件は、適度なままであり得る。

図１０において、第二の属性は、属性ＥＸＰＲＥＳＳ＿ＬＡＮＥとして示される。

第一および第二の属性を用いて、他のマップデータベース構造が使用され得ることが認識される。例示として、第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥは、図１０の９４、９５および９９において例示されるさらなるデータ構造によって個々の車線に割り当てられるよりも、むしろ、個々の車線に直接割り当てられ得る。第二の属性を個々の車線に直接割り当てることは、個々の車線がマップデータベースにおいて、個々のマップ特徴として表される場合、特に有用であり得る。

図１１は、マップデータベースを生成する方法１１０のフローチャートであり、マップデータベースは、追い越し車線を示す属性を含む。方法は、電子コンピュータシステムによって行われ得る。方法は、道路ネットワークの道路セグメントに関する情報および道路セグメントの車線に関する情報を含む生データを用いる。そのようなデータは、さまざまな納入業者によって提供され、ＮａｖｔｅｑまたはＴｅｌｅａｔｌａｓのようなさまざまなフォーマットを有し得る。方法を用いて、生データは処理され、追い越し車線を示す属性を含むデータベースを形成する。

１１１において、生データが検索される。生データは、道路セグメントに関する情報および道路セグメントのどの車線が追い越し車線かに関する情報を含み得る。そのような生データは、例えば、格納スペース限度に起因するか、または効率の悪いアクセスに起因して、乗り物のナビゲーションデバイスにおける直接使用には不適切であるフォーマットを有し得る。

１１２において、道路セグメントのトポロジーおよびジオメトリ情報が決定される。トポロジーは、道路セグメントの開始ポイントおよび終了ポイントに関する情報、他のマップ特徴への接続に関する情報などを含み得る。ジオメトリ情報は、道路セグメントまたはタイリングのうちの１つのタイルに配置された道路セグメントの一部のジオメトリに関する情報を含み得る。トポロジー情報は、道路セグメントを表すマップデータにおいてリンクを生成するために用いられ得る。

１１３において、道路セグメントは、少なくとも１つの追い越し車線を有するか否かが決定される。道路セグメントが追い越し車線を有さないと決定された場合、追い越し車線を示す属性は、道路セグメントに対して格納される必要はない。方法は、１１１に戻り得る。

道路セグメントが少なくとも１つの追い越し車線を有すると決定された場合、１１４において、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤがリンクに割り当てられる。第一の属性は、マップデータにおける続く格納のために登録され得る。第一の属性は、格納され得るが、すぐに格納される必要はない。むしろ、タイルに配置された異なる道路セグメントに割り当てられた第一の属性は、続く格納のために集められ得る。

１１５において、道路セグメントの全ての車線が追い越し車線か否かが決定される。道路セグメントが、追い越し車線でない少なくとも１つの車線を有すると決定された場合、１１６において、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤのブーリアンパラメータＡｌｌＬａｎｅｓがＦＡＬＳＥに設定される。道路セグメントの全ての車線が追い越し車線であると決定された場合、１１７において、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤのブーリアンパラメータＡｌｌＬａｎｅｓがＴＲＵＥに設定される。パラメータは、マップデータにおける続く格納のために登録され得る。パラメータは、格納され得るが、すぐに格納される必要はない。むしろ、タイルに配置された異なる道路セグメントに割り当てられたそれぞれ設定されたパラメータと共に、第一の属性は、続く格納のために集められ得る。

１１８において、第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥが道路セグメントの車線に割り当てられる。第二の属性は、車線のうちのどの車線が追い越し車線かに基づいて、選択的に割り当てられる。いくつかの実施形態において、属性ＥＸＰＲＥＳＳ＿ＬＡＮＥは、追い越し車線である車線のみに割り当てられ得る。第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥを道路セグメントの車線に割り当てることは、図１０の９４、９５および９９において示される第二の属性を個々の車線に関連付けるデータ構造を生成することを含み得る。このデータ構造は、バイナリ列の数字が道路セグメントの個々の車線を表す車線マスクフォーマットを有し得る。あるいは、第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥは、車線マスクを要求せずに、道路セグメントの個々の車線と直接関連付けられるように格納され得る。

１１９において、第一の属性ＥＸＰＲＥＳＳ＿ＲＯＡＤは、マップデータベースのルート層に格納され得る。第二の属性ＥＸＰＲＥＳＳ＿ＬＡＮＥは、マップデータベースのガイダンス層に格納され得る。

各道路セグメントに対して、個々に第一および第二の属性をマップデータベースに格納することは要求されない。むしろ、タイリングが規定され得、工程１１１〜１１８が、まず、タイルに含まれる全ての道路セグメントに対して繰り返され得る。第一の属性が割り当てられるリンクに関する情報および第二属性が割り当てられる車線に関する情報は、工程１１１〜１１８がタイルの全ての道路セグメントに対して行われた後、続いて集められ得、格納され得る。この処理は、異なるタイルに対して反復して繰り返され得る。

方法において、タイルが少なくとも１つの追い越し車線を有する道路セグメントを有さない場合、第一の属性または第二の属性をマップデータベースにおけるタイルを表すデータに格納することは要求されない。

さらに、いくつかの実施形態において、道路セグメントの全ての車線が追い越し車線の場合、第二の属性を道路セグメントの車線に対して格納することが要求されない場合がある。つまり、方法は、工程１１７から直接工程１１９に進み得る。したがって、いくつかの実施形態において、マップデータベースは、第二の属性を少なくとも１つの追い越し車線を有するが、追い越し車線から全体は構成されない道路セグメントの車線のみに対して含み得る。

図１１の方法を用いて生成されたマップデータベースは、さまざまなフォーマットを有し得る。限定としてよりは、むしろ例示として、マップデータベースは、ＮＤＳに従って設定されたマップデータベースであり得る。第一の属性および第二の属性は、ＮＤＳによって規定された柔軟な属性であり得る。

図１１の方法を用いて生成されたマップデータベースは、実施形態に従う乗り物のナビゲーションデバイスにおいて用いられ得る。

実施形態に従うデバイスおよび方法が詳細に説明されたが、改変が他の実施形態において実装され得る。例示として、実施形態のデバイスおよび方法によって用いられるマップデータベースがタイリングに従って組織化されたデータを格納することは要求されない。タイリングがマップデータベースを組織化するために用いられた場合、タイリングは、スクエアタイリングである必要はなく、道路ネットワークを含むいずれか他のタイリングであり得る。異なるタイリングは、ルートおよびガイダンス機能のために用いられ得る。ルート層に対して規定されたタイリングは、タイルを含み得、これらのタイルは、サイズおよび／または形状がガイダンス層に対して規定された別のタイリングの他のタイルと異なり得る。

さらなる例示として、第一の属性は、ブーリアンパラメータを有し得るが、第一の属性は、別のパラメータタイプのパラメータを有し得る。例示として、第一の属性は、整数パラメータタイプのパラメータを有し得る。パラメータは、それぞれの道路セグメントの車線の数を示し得る。

さらなる例示として、実施形態のマップデータベースは、少なくとも１つの追い越し車線を含むいずれかの道路セグメントに対して第二の属性を含み得るが、他の実施形態において、マップデータベースは、追い越し車線から全体が構成される道路セグメントの車線に対して第二の属性を有さない場合がある。この場合、追い越し車線である車線に関する情報は、第一の属性およびそのパラメータから派生され得る。

発明の実施形態は、乗り物のナビゲーションデバイスとして用いられ得る。

Claims (15)

1. 乗り物のナビゲーションデバイスであって、
   該乗り物のナビゲーションデバイスは、
   マップデータベース（１０）であって、該マップデータベース（１０）は、マップデータを格納し、該マップデータは、リンクおよび属性（６３、６４、８３、８６、９３、９８）を含み、該リンクは、道路セグメント（５１〜５９）を表し、第一の属性（６３、６４、８３、８６）は、それぞれ該リンクのサブセットに割り当てられることによって、該サブセットに含まれる該リンクが少なくとも１つの追い越し車線を有することを示し、第二の属性（９３、９８）は、それぞれ該サブセットに含まれる該リンクの少なくとも一部の車線に割り当てられることによって、該それぞれの道路セグメント（５１〜５３）のどの車線が追い越し車線かを示し、該第二の属性（９３、９８）は、該第一の属性（６３、６４、８３、８６）とは異なる、マップデータベース（１０）と、
   処理ユニット（２）であって、該処理ユニット（２）は、該マップデータベース（１０）に結合され、該第一の属性（６３、６４、８３、８６）に少なくとも基づいてルートサーチを行うことと、ルートガイダンス情報の出力を、ユーザーインターフェース（４）を介して少なくとも該第二の属性（９３、９８）に基づいて制御することとを行うように構成されている、処理ユニット（２）と
   を含む、乗り物のナビゲーションデバイス。
2. 前記マップデータベース（１０）は、各リンクに対してデータ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）を含み、該データ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）は、リンクに対して固定された数のデータフィールドを有し、値は、それぞれ各データフィールドに対して設定されており、
   前記第一の属性（６３、６４、８３、８６）および前記第二の属性（９３、９８）は、該データ構造（６２、８２、８５、８８、９０、９２、９７、１０１、１０３）から分離して格納される、請求項１に記載の乗り物のナビゲーションデバイス。
3. 前記第一の属性（６３、６４、８３、８６）は、ブーリアンパラメータを有し、
   前記処理ユニット（２）は、リンクに対するルートサーチを、該第一の属性（６３、６４、８３、８６）と該ブーリアンパラメータとの両方に基づいて行うように構成されている、請求項１に記載の乗り物のナビゲーションデバイス。
4. 前記マップデータベース（１０）において、前記ブーリアンパラメータが第一の値に設定された前記第一の属性（６３、８３）は、それぞれ、リンク（５１、５２）へ割り当てられ、該リンク（５１、５２）は、追い越し車線で全体が構成され、該ブーリアンパラメータが該第一の値とは異なる第二の値に設定された該第一の属性（６４、８６）は、それぞれ、リンク（５３）へ割り当てられ、該リンク（５３）は、少なくとも１つの追い越し車線と少なくとも１つの非追い越し車線とを含む、請求項３に記載の乗り物のナビゲーションデバイス。
5. 前記マップデータベース（１０）は、第一の部分（１１）および第二の部分（１４）を含み、前記第一の属性（６３、６４、８３、８６）は、該第一の部分（１１）に格納され、前記第二の属性（９３、９８）は、該第二の部分（１４）に格納され、
   前記処理ユニット（２）は、該第二の部分（１４）から検索され、該第一の部分（１１）に格納されたデータから独立しているデータに基づいて、前記ルートガイダンス情報の出力を制御するように構成されている、請求項１に記載の乗り物のナビゲーションデバイス。
6. 前記第一の部分（１１）は、第一のテーブルであり、前記第二の部分（１４）は、該第一のテーブル（１１）とは異なる第二のテーブルである、請求項５に記載の乗り物のナビゲーションデバイス。
7. 各道路セグメント（５１〜５９）は、タイリングの少なくとも１つのタイル（５０、７１〜７４）に配置され、
   前記マップデータベース（１０）は、リンクによって表された該道路セグメント（５１〜５３）の少なくとも１つが少なくとも１つの追い越し車線を有する場合ののみ、該タイリングのタイル（５０、７１〜７４）に配置された該リンク（５１〜５３）に対する前記第一の属性（６３、６４、８３、８６）を含む、請求項１〜６のうちのいずれか一項に記載の乗り物のナビゲーションデバイス。
8. 各リンクは、さらなるタイリングの少なくとも１つのタイル（７１〜７４）に配置され、
   前記マップデータベース（１０）は、該さらなるタイリングのタイル（７１〜７４）に配置された道路セグメント（５１〜５９）の少なくとも１つが少なくとも１つの追い越し車線を有する場合にのみ、該さらなるタイリングの該タイル（７１〜７４）に配置された該道路セグメント（５１〜５９）の車線に対する前記第二の属性（９３、９８）を含む、請求項７に記載の乗り物のナビゲーションデバイス。
9. マップデータベース（１０）を生成する方法であって、
   該方法は、
   道路セグメント（５１〜５９）に関する情報と各道路セグメントの車線に関する情報とを含むデータを検索することと、
   複数の道路セグメント（５１〜５９）に対して、
   該道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を有するか否かを決定することと、
   該道路セグメント（５１〜５９）の少なくとも１つの車線が追い越し車線である場合、第一の属性（６３、６４、８３、８６）を該道路セグメント（５１〜５９）を表すリンクに選択的に割り当てることと、
   第二の属性（９３、９８）を該道路セグメント（５１〜５９）の車線に選択的に割り当てることであって、該第二の属性は（９３、９８）は、該道路セグメント（５１〜５９）のどの車線が追い越し車線かに基づいて選択的に割り当てられる、ことと
   を行うことと、
   該第一の属性（６３、６４、８３、８６）および第二の属性（９３、９８）を該マップデータベース（１０）に格納することと
   を含む、方法。
10. 前記第一の属性（６３、６４、８３、８６）を選択的に割り当てることは、該第一の属性（６３、６４、８３、８６）のパラメータを前記道路セグメント（５１〜５９）の全ての車線が追い越し車線であるか否かに基づいて設定することを含み、該パラメータは、前記マップデータベース（１０）に格納される、請求項９に記載の方法。
11. 前記第一の属性（６３、６４、８３、８６）は、前記マップデータベース（１０）の第一の部分（１１）に格納され、前記第二の属性（９３、９８）は、該マップデータベース（１０）の第二の部分（１４）に格納され、該第一の部分（１１）は、ルートサーチのためのデータを表し、該第二の部分（１４）は、ルートガイダンス情報を出力するためのデータを表す、請求項９に記載の方法。
12. 複数のタイル（５０、７１〜７４）を含み、前記道路セグメント（５１〜５９）をカバーするタイリングが規定され、
    該タイリングの各タイル（５０、７１〜７４）に対して、第一の属性（６３、６４、８３、８６）は、該タイリングの前記それぞれのタイル（５０、７１〜７４）に含まれる少なくとも１つの道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を含む場合にのみ、前記マップデータベース（１０）に格納される、請求項９〜１１のうちのいずれか一項に記載の方法。
13. 複数のタイル（７１〜７４）を含み、前記道路セグメント（５１〜５９）をカバーするさらなるタイリングが規定され、
    該さらなるタイリングの各タイル（７１〜７４）に対して、第二の属性（９３、９８）は、該さらなるタイリング（７１〜７４）の前記それぞれのタイルに含まれる少なくとも１つの道路セグメント（５１〜５９）が少なくとも１つの追い越し車線を含む場合にのみ、前記マップデータベース（１０）に格納される、請求項１２に記載の方法。
14. マップデータベース（１０）に格納されたデータを処理する方法であって、該マップデータベース（１０）は、道路セグメント（５１〜５９）を表すリンクと、第一の属性（６３、６４、８３、８６）と、第二の属性（９３、９８）とを格納し、該第一の属性（６３、６４、８３、８６）は、リンク（５１〜５３）のサブセットに割り当てられ、該第二の属性（９３、９８）は、該リンク（５１〜５３）のサブセットの少なくとも一部の車線に割り当てられ、該方法は、
    ルートサーチを行うことであって、該ルートサーチを行うことは、
    追い越し車線に対する好みまたは回避のオプションの起動を監視することと、該好みまたは回避のオプションが起動された場合、リンクに割り当てられた該第一の属性（６３、６４、８３、８６）に基づいて、ルートのコストを選択的に調節することと
    を含む、ことと、
    ルートガイダンス情報を該第二の属性（９３、９８）に基づいて出力することと
    を含む、方法。
15. 前記ルートサーチは、前記第二の属性（９３、９８）から独立して行われ、該ルートガイダンス情報の出力は、前記第一の属性（６３、６４、８３、８６）から独立して行われる、請求項１４に記載の方法。

Images