(57)【要約】【課題】道路ネットワークデータにおける単位交差点について、交差点内リンクおよび交差点外リンクに、１の前記交差点ノードを出入りする２つのリンクにまたがる通行を不可とする規制情報を効率的に付与する技術を提供する。【解決手段】交差点内ネットワークデータ整備装置１０において、補助リンク生成部１６は、通行不可リンク列を構成する交差点内リンクが１つのみである第２の場合に、その交差点内リンクの両端の交差点ノードを結ぶダミーリンク列を新たに生成し、通行不可リンク列を構成する交差点内リンク列であって、通行可能リンク列と重複しており、かつ、代替の経路が存在しない交差点内リンク列が存在する第３の場合に、その交差点内リンク列の両端の交差点ノードを結ぶダミーリンクを新たに生成する。【選択図】図１
2013210496.tif 000002
【特許請求の範囲】
【請求項１】
地図上の道路を表すとともに進行方向が定められているリンクと前記道路の端点を表すノードとを有する道路ネットワークデータであって、１つの交差点とみなした単位交差点について、前記単位交差点内の通路を表すとともに進行方向が定められている交差点内リンクと前記通路の端点を表す交差点ノードとを含む道路ネットワークデータにおいて、前記交差点内リンクおよび前記交差点内リンクに前記交差点ノードを介して接続されているリンクである交差点外リンクに、１の前記交差点ノードを出入りする２つのリンクにまたがる通行を不可とする規制情報を付与する交差点内ネットワークデータ整備装置であって、
前記単位交差点について、前記道路ネットワークデータに基づいて、交差点への進入から退出まで回帰せずに接続可能な前記交差点外リンクおよび前記交差点内リンクの列である接続可能リンク列であって、前記規制情報が付与されていない接続可能リンク列をすべて特定するとともに、前記単位交差点に対応する交差点についての現実の交通規制情報に基づいて、前記接続可能リンク列を、通行が不可とされていない接続可能リンク列である通行可能リンク列と、通行を不可とすべき接続可能リンク列である通行不可リンク列と、に分類するリンク列分類部と、
前記通行可能リンク列および前記通行不可リンク列を比較して、前記通行不可リンク列を構成する前記２つのリンクであって、前記通行可能リンク列と重複していない前記２つのリンク、または、前記通行可能リンク列と重複しているが代替の経路が存在する前記２つのリンクが存在する第１の場合に、該２つのリンクに前記規制情報を付与して、前記リンク列分類部に処理を戻す規制情報付与部と、を備え、
前記規制情報付与部は、前記通行可能リンク列および前記通行不可リンク列を比較して、前記第１の場合以外の場合に、前記交差点内リンクまたは前記交差点内リンクの列である交差点内リンク列を新たに生成することができる補助リンク生成部を備え、
前記補助リンク生成部は、
前記通行不可リンク列を構成する前記交差点内リンクが１つのみである第２の場合に、該交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列を新たに生成して、前記リンク列分類部に処理を戻し、
前記通行不可リンク列を構成する前記交差点内リンク列であって、前記通行可能リンク列と重複しており、かつ、代替の経路が存在しない前記交差点内リンク列が存在する第３の場合に、該交差点内リンク列の両端の交差点ノードを結ぶ交差点内リンクを新たに生成して、前記リンク列分類部に処理を戻す、
交差点内ネットワークデータ整備装置。
【請求項２】
請求項１記載の交差点内ネットワークデータ整備装置であって、
前記補助リンク生成部は、前記第３の場合であって、前記通行不可リンク列を構成し前記通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合には、該交差点内リンク列を構成する交差点内リンクの数が最大となる交差点内リンク列である最大交差点内リンク列を特定して、該最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する、
交差点内ネットワークデータ整備装置。
【請求項３】
請求項２記載の交差点内ネットワークデータ整備装置であって、
前記補助リンク生成部は、前記第３の場合であって、前記通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合において、前記最大交差点内リンク列が複数存在する場合には、前記通行可能リンク列および前記通行不可リンク列との重複数の合計が最も多い最大交差点内リンク列を特定して、該最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する、
交差点内ネットワークデータ整備装置。
【請求項４】
地図上の道路を表すとともに進行方向が定められているリンクと前記道路の端点を表すノードとを有する道路ネットワークデータであって、１つの交差点とみなした単位交差点について、前記単位交差点内の通路を表すとともに進行方向が定められている交差点内リンクと前記通路の端点を表す交差点ノードとを含む道路ネットワークデータにおいて、前記交差点内リンクおよび前記交差点内リンクに前記交差点ノードを介して接続されているリンクである交差点外リンクに、１の前記交差点ノードを出入りする２つのリンクにまたがる通行を不可とする規制情報を付与する交差点内ネットワークの整備方法であって、
前記単位交差点について、前記道路ネットワークデータに基づいて、交差点への進入から退出まで回帰せずに接続可能な前記交差点外リンクおよび前記交差点内リンクの列である接続可能リンク列であって、前記規制情報が付与されていない接続可能リンク列をすべて特定するとともに、前記単位交差点に対応する交差点についての現実の交通規制情報に基づいて、前記接続可能リンク列を、通行が不可とされていない接続可能リンク列である通行可能リンク列と、通行を不可とすべき接続可能リンク列である通行不可リンク列と、に分類するリンク列分類工程と、
前記通行可能リンク列および前記通行不可リンク列を比較して、前記通行不可リンク列を構成する前記２つのリンクであって、前記通行可能リンク列と重複していない前記２つのリンク、または、前記通行可能リンク列と重複しているが代替の経路が存在する前記２つのリンクが存在する第１の場合に、該２つのリンクに前記規制情報を付与して、前記リンク列分類工程に処理を戻す規制情報付与工程と、を備え、
前記規制情報付与工程は、前記通行可能リンク列および前記通行不可リンク列を比較して、前記第１の場合以外の場合に、前記交差点内リンクまたは前記交差点内リンクの列である交差点内リンク列を新たに生成することができる補助リンク生成工程を備え、
前記補助リンク生成工程は、
前記通行不可リンク列を構成する前記交差点内リンクが１つのみである第２の場合に、該交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列を新たに生成して、前記リンク列分類工程に処理を戻す交差点内リンク列生成工程と、
前記通行不可リンク列を構成する前記交差点内リンク列であって、前記通行可能リンク列と重複しており、かつ、代替の経路が存在しない前記交差点内リンク列が存在する第３の場合に、該交差点内リンク列の両端の交差点ノードを結ぶ交差点内リンクを新たに生成して、前記リンク列分類工程に処理を戻す交差点内リンク生成工程と、
を含む、
交差点内ネットワークデータの整備方法。
【請求項５】
地図上の道路を表すとともに進行方向が定められているリンクと前記道路の端点を表すノードとを有する道路ネットワークデータであって、１つの交差点とみなした単位交差点について、前記単位交差点内の通路を表すとともに進行方向が定められている交差点内リンクと前記通路の端点を表す交差点ノードとを含む道路ネットワークデータにおいて、前記交差点内リンクおよび前記交差点内リンクに前記交差点ノードを介して接続されているリンクである交差点外リンクに、１の前記交差点ノードを出入りする２つのリンクにまたがる通行を不可とする規制情報を付与するためのコンピュータプログラムであって、
前記単位交差点について、前記道路ネットワークデータに基づいて、交差点への進入から退出まで回帰せずに接続可能な前記交差点外リンクおよび前記交差点内リンクの列である接続可能リンク列であって、前記規制情報が付与されていない接続可能リンク列をすべて特定するとともに、前記単位交差点に対応する交差点についての現実の交通規制情報に基づいて、前記接続可能リンク列を、通行が不可とされていない接続可能リンク列である通行可能リンク列と、通行を不可とすべき接続可能リンク列である通行不可リンク列と、に分類するリンク列分類機能と、
前記通行可能リンク列および前記通行不可リンク列を比較して、前記通行不可リンク列を構成する前記２つのリンクであって、前記通行可能リンク列と重複していない前記２つのリンク、または、前記通行可能リンク列と重複しているが代替の経路が存在する前記２つのリンクが存在する第１の場合に、該２つのリンクに前記規制情報を付与して、前記リンク列分類機能に処理を戻す規制情報付与機能と、
をコンピュータに実現させるためのコンピュータプログラムであり、
前記規制情報付与機能は、前記通行可能リンク列および前記通行不可リンク列を比較して、前記第１の場合以外の場合に、前記交差点内リンクまたは前記交差点内リンクの列である交差点内リンク列を新たに生成することができる補助リンク生成機能を備え、
前記補助リンク生成機能は、
前記通行不可リンク列を構成する前記交差点内リンクが１つのみである第２の場合に、該交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列を新たに生成して、前記リンク列分類機能に処理を戻す交差点内リンク列生成機能と、
前記通行不可リンク列を構成する前記交差点内リンク列であって、前記通行可能リンク列と重複しており、かつ、代替の経路が存在しない前記交差点内リンク列が存在する第３の場合に、該交差点内リンク列の両端の交差点ノードを結ぶ交差点内リンクを新たに生成して、前記リンク列分類機能に処理を戻す交差点内リンク生成機能と、
を含む、
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、交差点内ネットワークデータを整備する技術に関し、詳しくは、道路ネットワークデータにおいて、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報を付与する技術に関するものである。
【背景技術】
【０００２】
電子地図データは、例えば、ユーザーによって指定された出発地から目的地までの経路探索や、経路案内に利用される。このような電子地図データには、地図上の道路を表すリンク（リンクデータ）と道路の端点を表すノード（ノードデータ）とを有する道路ネットワークデータが含まれる。そして、この道路ネットワークデータには、交差点における規制情報（例えば、転回禁止、右折禁止、左折禁止、進入禁止等）も含まれる。規制情報は、交差点における現実の交通規制情報に基づいて付与される。
【０００３】
近年では、経路探索および経路案内を精度よく行うために、道路ネットワークデータにおいて、上り車線と下り車線とが別個の道路として扱われる道路（二条化道路）は、進行方向が一方向に定められた２つのリンクを用いて表される。この場合、２つのリンクが接続されている交差点も、複数のノード（交差点ノード）を用いて表される。このため、このような道路ネットワークデータでは、１つの交差点について、複数の交差点ノードを接続する通路を表す交差点内リンクが仮想的に設けられる。さらに、このような交差点には、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報が付与される。さらに、通行可能な経路と通行不可能な経路とが重なる交差点内リンクが存在する場合には、これらの経路に対する規制を個別に付与するために、仮想的なリンクであるダミーリンクや、仮想的なノードであるダミーノードが設けられる（下記特許文献１参照）。
【０００４】
そして、例えば、下記特許文献１に記載された技術では、任意の交差点に対応する交差点ノードおよびダミーノード数と、これらに接続する交差点内リンクおよびダミーリンクの数とに基づいて、この交差点が基本規制情報対象交差点であるか否かを判定し、この交差点が基本規制情報対象交差点である場合に、基本規制情報を付与する。さらに、この交差点を構成する交差点ノードと道路リンクとの接続関係から、この交差点が個別規制情報対象交差点であるか否かを判定し、この交差点が個別規制情報対象交差点である場合に、個別規制情報の入力を受け付けて、追加の規制情報を付与する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−２３７４８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上記特許文献１に記載された技術では、道路ネットワークデータにおいて、交差点に、ダミーリンクやダミーノードが画一的に設けられていた。つまり、上記特許文献１に記載された技術では、現実の交通規制情報の内容によっては不必要となる可能性があるダミーリンクやダミーノードも設けられていた。そして、不必要なダミーリンクやダミーノードが設けられた場合には、不必要な規制情報も付与されていた。また、上記特許文献１に記載された技術では、基本規制情報対象交差点ではない交差点については、オペレータの判断によって個別に規制情報を付与する必要があり、効率よく、かつ、正確に、規制情報を付与することができなかった。
【０００７】
本発明は、上述の課題を解決するためになされたものであり、道路ネットワークデータにおける単位交差点について、交差点内リンクおよび交差点外リンクに、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報を、効率的に付与する技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態又は適用例として実現することが可能である。
【０００９】
［適用例１］地図上の道路を表すとともに進行方向が定められているリンクと前記道路の端点を表すノードとを有する道路ネットワークデータであって、１つの交差点とみなした単位交差点について、前記単位交差点内の通路を表すとともに進行方向が定められている交差点内リンクと前記通路の端点を表す交差点ノードとを含む道路ネットワークデータにおいて、前記交差点内リンクおよび前記交差点内リンクに前記交差点ノードを介して接続されているリンクである交差点外リンクに、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報を付与する交差点内ネットワークデータ整備装置であって、前記単位交差点について、前記道路ネットワークデータに基づいて、交差点への進入から退出まで回帰せずに接続可能な前記交差点外リンクおよび前記交差点内リンクの列である接続可能リンク列であって、前記規制情報が付与されていない接続可能リンク列をすべて特定するとともに、前記単位交差点に対応する交差点についての現実の交通規制情報に基づいて、前記接続可能リンク列を、通行が不可とされていない接続可能リンク列である通行可能リンク列と、通行を不可とすべき接続可能リンク列である通行不可リンク列と、に分類するリンク列分類部と、前記通行可能リンク列および前記通行不可リンク列を比較して、前記通行不可リンク列を構成する前記２つのリンクであって、前記通行可能リンク列と重複していない前記２つのリンク、または、前記通行可能リンク列と重複しているが代替の経路が存在する前記２つのリンクが存在する第１の場合に、該２つのリンクに前記規制情報を付与して、前記リンク列分類部に処理を戻す規制情報付与部と、を備え、前記規制情報付与部は、前記通行可能リンク列および前記通行不可リンク列を比較して、前記第１の場合以外の場合に、前記交差点内リンクまたは前記交差点内リンクの列である交差点内リンク列を新たに生成することができる補助リンク生成部を備え、前記補助リンク生成部は、前記通行不可リンク列を構成する前記交差点内リンクが１つのみである第２の場合に、該交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列を新たに生成して、前記リンク列分類部に処理を戻し、前記通行不可リンク列を構成する前記交差点内リンク列であって、前記通行可能リンク列と重複しており、かつ、代替の経路が存在しない前記交差点内リンク列が存在する第３の場合に、該交差点内リンク列の両端の交差点ノードを結ぶ交差点内リンクを新たに生成して、前記リンク列分類部に処理を戻す、交差点内ネットワークデータ整備装置。
ここで、「代替の経路が存在する」とは、同じ始終点ノードを持つ通行可能リンク列が複数存在しており、そのうち通行不可リンク列と重複していない通行可能リンク列が存在している場合のことをいう。
【００１０】
ここで、「代替の経路が存在する」とは、同じ始終点ノードを持つ通行可能リンク列が複数存在しており、そのうち通行不可リンク列と重複していない通行可能リンク列が存在している場合のことをいう。補助リンク生成部が生成する新たな交差点内リンクは、道路ネットワークデータが予め有している交差点内リンクに追加される交差点内リンクであり、上記特許文献１におけるダミーリンクに相当する。また、補助リンク生成部が生成する新たな交差点内リンク列は、道路ネットワークデータが予め有している交差点内リンク列に追加される交差点内リンク列であり、上記特許文献１におけるダミーリンクおよびダミーノードに相当する。
【００１１】
適用例１の交差点内ネットワークデータ整備装置では、整備前、すなわち、上記規制情報を付与する前の道路ネットワークデータにおいて、交差点（単位交差点）に、ダミーリンクやダミーノードは設けられていない。そして、適用例１の交差点内ネットワークデータ整備装置では、規制情報付与部が上記規制情報を付与するに際し、補助リンク生成部は、順次、通行可能リンク列および通行不可リンク列の構成に基づいて、交差点内リンク列（ダミーリンクおよびダミーノード）を新たに生成したり、交差点内リンク（ダミーリンク）を新たに生成したり、交差点内リンク列も交差点内リンクも新たに生成しなかったりする。このため、必要最小限の交差点内リンク列および交差点リンクだけが新たに生成され、不必要となる可能性がある交差点内リンク列（ダミーリンクおよびダミーノード）および交差点リンク（ダミーリンク）が新たに生成されることはない。そして、不必要な規制情報が付与されることもない。また、規制情報付与部は、通行可能リンク列および通行不可リンク列を比較して、上記第１の場合には、オペレータの判断によらずに、上記規制情報を付与することができる。したがって、適用例１の交差点内ネットワークデータ整備装置によって、道路ネットワークデータにおける単位交差点について、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報を、交差点内リンクまたは交差点外リンクに効率的に付与することができる。
【００１２】
また、適用例１の交差点内ネットワークデータ整備装置によれば、不必要な交差点内リンク列および交差点リンクが新たに生成されることがなく、不必要な規制情報が付与されることもないので、規制情報を記憶するための記憶容量を低減することもできる。
【００１３】
［適用例２］適用例１記載の交差点内ネットワークデータ整備装置であって、前記補助リンク生成部は、前記第３の場合であって、前記通行不可リンク列を構成し前記通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合には、該交差点内リンク列を構成する交差点内リンクの数が最大となる交差点内リンク列である最大交差点内リンク列を特定して、該最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する、交差点内ネットワークデータ整備装置。
【００１４】
［適用例３］適用例２記載の交差点内ネットワークデータ整備装置であって、前記補助リンク生成部は、前記第３の場合であって、前記通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合において、前記最大交差点内リンク列が複数存在する場合には、前記通行可能リンク列および前記通行不可リンク列との重複数の合計が最も多い最大交差点内リンク列を特定して、該最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する、交差点内ネットワークデータ整備装置。
【００１５】
適用例２，３の交差点内ネットワークデータ整備装置では、単位交差点に接続される道路（交差点外リンク）の数が多く、現実の交通規制情報や、道路の接続状態が複雑な交差点についても、上記規制情報を効率的に付与することができる。
【００１６】
本発明は、上述の交差点内ネットワークデータ整備装置としての構成の他、交差点内ネットワークデータの整備方法の発明として構成することもできる。また、これらを実現するコンピュータプログラム、およびそのプログラムを記録した記録媒体、そのプログラムを含み搬送波内に具現化されたデータ信号など種々の態様で実現することが可能である。なお、それぞれの態様において、先に示した種々の付加的要素を適用することが可能である。
【００１７】
本発明をコンピュータプログラムまたはそのプログラムを記録した記録媒体等として構成する場合には、交差点内ネットワークデータ整備装置の動作を制御するプログラム全体として構成するものとしてもよいし、本発明の機能を果たす部分のみを構成するものとしてもよい。また、記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置などコンピュータが読み取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施例としての交差点内ネットワークデータ整備装置１０の概略構成を示す説明図である。
【図２】規制情報付与処理の流れを示すフローチャートである。
【図３】規制情報付与処理の流れを示すフローチャートである。
【図４】具体例１の単位交差点を示す説明図である。
【図５】通行可能リンク列および通行不可リンク列を模式的に示す説明図である。
【図６】単位交差点について、ダミーリンクＤＬａｃ、および、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とリンク列［Ｎｃ→Ｎｄ→Ｎａ］とに、２リンク規制情報２４が付与された様子を模式的に示す説明図である。
【図７】通行可能リンク列および通行不可リンク列を模式的に示す説明図である。
【図８】リンク列［Ｎａ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｂ→Ｎｃ→Ｎａ］と、リンク列［Ｎｃ→Ｎａ→Ｎｂ］と、リンク列［Ｎｄ→Ｎａ→Ｎｃ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。
【図９】具体例２の単位交差点を示す説明図である。
【図１０】通行可能リンク列および通行不可リンク列を模式的に示す説明図である。
【図１１】ダミーノードＤＮｃおよびダミーリンクＤＬａｃ，ＤＬｂｃが生成された単位交差点を示す説明図である。
【図１２】通行可能リンク列および通行不可リンク列を模式的に示す説明図である。
【図１３】単位交差点について、段階的に２リンク規制情報２４が付与されていく様子を模式的に示す説明図である。
【図１４】具体例３の単位交差点を示す説明図である。
【図１５】通行可能リンク列を模式的に示す説明図である。
【図１６】通行不可リンク列を模式的に示す説明図である。
【図１７】リンク列［Ｎ５→Ｎｄ→Ｎｅ］と、リンク列［Ｎｅ→Ｎｆ→Ｎｇ］と、リンク列［Ｎ１１→Ｎｈ→Ｎａ］と、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。
【図１８】ダミーリンクを生成する重複交差点リンク列を決定する方法を説明するための説明図である。
【図１９】ダミーリンクＤＬｄａ，ＤＬｈｅが生成された単位交差点を模式的に示す説明図である。
【図２０】通行可能リンク列を模式的に示す説明図である。
【図２１】通行不可リンク列を模式的に示す説明図である。
【図２２】リンク列［Ｎｃ→Ｎｄ→Ｎａ］と、リンク列［Ｎｄ→Ｎａ→Ｎｂ］と、リンク列［Ｎｇ→Ｎｈ→Ｎｅ］と、リンク列［Ｎｈ→Ｎｅ→Ｎｆ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。
【図２３】リンク列［Ｎｄ→Ｎｇ→Ｎｈ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、実施例に基づき説明する。
Ａ．交差点内ネットワークデータ整備装置の構成：
図１は、本発明の一実施例としての交差点内ネットワークデータ整備装置１０の概略構成を示す説明図である。この交差点内ネットワークデータ整備装置１０は、後述する交差点内リンクおよび交差点外リンクに、１の交差点ノードに出入りする２つのリンクにまたがる通行を不可とする規制情報（以下、２リンク規制情報とも言う）を付与する装置である。交差点内ネットワークデータ整備装置１０は、ＣＰＵや、図示しない記憶部を備えている。ＣＰＵは、記憶部に記憶されたコンピュータプログラムを実行することによって、リンク列分類部１２、規制情報付与部１４として機能する。規制情報付与部１４は、補助リンク生成部１６を備えている。
【００２０】
交差点内ネットワークデータ整備装置１０には、電子地図データ記憶装置２０が接続されている。そして、電子地図データ記憶装置２０には、道路ネットワークデータ２２と、交通規制情報２６とが対応付けて記憶されている。道路ネットワークデータ２２は、リンクデータや、ノードデータや、２リンク規制情報２４等を含んでいる。リンクデータは、地図上における道路（リンク）を表すデータである。各リンクには、進行方向が定められている。また、リンクデータは、１つの交差点とみなした単位交差点について、単位交差点内の通路（交差点内リンク）を表すデータも含んでいる。ノードデータは、地図上における道路の端点（例えば、交差点や、行き止まり等）を表すデータである。また、ノードデータは、１つの交差点とみなした単位交差点について、単位交差点内の通路の端点（交差点ノード）を表すデータも含んでいる。２リンク規制情報２４は、交差点内ネットワークデータ整備装置１０による後述する規制情報付与処理によって付与されて記憶される。交通規制情報２６は、交差点における現実の交通規制情報（例えば、転回禁止、右折禁止、左折禁止、進入禁止等）である。
【００２１】
リンク列分類部１２は、単位交差点について、道路ネットワークデータ２２に基づいて、交差点への進入から退出まで回帰せずに接続可能な交差点外リンクおよび交差点内リンクの列である接続可能リンク列であって、２リンク規制情報２４が付与されていない接続可能リンク列をすべて特定する。交差点内リンクは、単位交差点内の通路を表すリンクである。また、交差点外リンクは、交差点内リンクに前記交差点ノードを介して接続されているリンクである。そして、リンク列分類部１２は、単位交差点に対応する交差点についての現実の交通規制情報２６に基づいて、接続可能リンク列を、通行が不可とされていない接続可能リンク列である通行可能リンク列と、通行を不可とすべき接続可能リンク列である通行不可リンク列と、に分類する。通行不可リンク列および通行可能リンク列は、規制情報付与部１４によって参照される。リンク列分類部１２が実行する処理については、後から具体例を挙げて、詳しく説明する。
【００２２】
規制情報付与部１４は、通行可能リンク列および通行不可リンク列を比較して、通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複していない２つのリンク、または、通行可能リンク列と重複しているが代替の経路が存在する２つのリンクが存在する第１の場合に、この２つのリンクに２リンク規制情報２４を付与して、リンク列分類部１２に処理を戻す。「代替の経路が存在する」とは、同じ始終点ノードを持つ通行可能リンク列が複数存在しており、そのうち通行不可リンク列と重複していない通行可能リンク列が存在している場合のことをいう。こうすることによって、規制情報付与部１４は、通行不可リンク列に含まれる２つのリンクに、過不足なく、２リンク規制情報２４を付与することができる。規制情報付与部１４が実行する処理については、後から具体例を挙げて、詳しく説明する。
【００２３】
補助リンク生成部１６は、通行可能リンク列および通行不可リンク列を比較して、上記第１の場合以外の場合に、交差点内リンク（後述するダミーリンク）または交差点内リンクの列である交差点内リンク列（後述するダミーリンク列）を新たに生成することができる。具体的には、補助リンク生成部１６は、通行不可リンク列を構成する交差点内リンクが１つのみである第２の場合に、この交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列（ダミーリンク列）を新たに生成して、リンク列分類部１２に処理を戻す。また、補助リンク生成部１６は、通行不可リンク列を構成する交差点内リンク列であって、通行可能リンク列と重複しており、かつ、代替の経路が存在しない交差点内リンク列が存在する第３の場合に、この交差点内リンク列の両端の交差点ノードを結ぶ交差点内リンク（ダミーリンク）を新たに生成して、リンク列分類部１２に処理を戻す。交差点内ネットワークデータ整備装置１０は、リンク列分類部１２の処理において、通行不可リンク列に分類される接続可能リンク列が存在しない場合に、交差点内リンク（ダミーリンク）および交差点内リンク列（ダミーリンク列）を新たに生成せずに、単位交差点についての２リンク規制情報２４の付与を終了する。こうすることによって、補助リンク生成部１６は、不必要となる可能性がある交差点内リンク列（ダミーリンク列）および交差点リンク（ダミーリンク）を生成しないようにすることができる。補助リンク生成部１６が実行する処理については、後から具体例を挙げて、詳しく説明する。
【００２４】
Ｂ．規制情報付与処理：
図２および図３は、規制情報付与処理の流れを示すフローチャートである。この処理は、例えば、道路地図の整備時、電子地図データ記憶装置２０に記憶された道路ネットワークデータ２２または現実の交通規制情報２６が変更されて、２リンク規制情報２４の付与指示が入力されたときに、交差点内ネットワークデータ整備装置１０のＣＰＵが実行する処理である。なお、交差点内ネットワークデータ整備装置１０がこの規制情報付与処理を開始する際には、道路ネットワークデータ２２において、後述するダミーリンク、ダミーノード、および、２リンク規制情報２４はすべて削除されているか、未生成もしくは未付与の状態とする。
【００２５】
まず、リンク列分類部１２は、処理対象の単位交差点について、道路ネットワークデータ２２を取得し（ステップＳ１０）、２リンク規制情報２４が付与されていない接続可能リンク列をすべて特定する。また、リンク列分類部１２は、処理対象となる単位交差点に対応する交差点の現実の交通規制情報２６を検索する（ステップＳ１２）。そして、リンク列分類部１２は、その交差点に対応する交通規制情報２６があるか否かを判断する（ステップＳ１４）。交通規制情報２６がない場合には（ステップＳ１４：ＮＯ）、リンク列分類部１２は、規制情報付与処理を終了する。
【００２６】
交通規制情報２６がある場合には（ステップＳ１４：ＹＥＳ）、リンク列分類部１２は、交通規制情報２６に基づいて、接続可能リンク列を、通行可能リンク列と通行不可リンク列とに分類する。具体的には、以下の処理を行う。まず、リンク列分類部１２は、接続可能リンク列の中から、通行可能リンク列を特定する（ステップＳ２０）。そして、リンク列分類部１２は、経路が作れない始終点の組があるか否かを判断する（ステップＳ２２）。経路が作れない始終点の組がある場合には（ステップＳ２２：ＹＥＳ）、リンク列分類部１２は、規制情報付与処理を終了する。道路ネットワークデータ２２および交通規制情報２６に誤りがなければ、経路が作れない始終点の組はない。経路が作れない始終点の組がない場合には（ステップＳ２２：ＮＯ）、リンク列分類部１２は、接続可能リンク列の中から、通行不可リンク列を特定する（ステップＳ２６）。そして、規制情報付与部１４は、通行不可リンク列があるか否かを判断する（ステップＳ２８）。通行不可リンク列がない場合には（ステップＳ２８：ＮＯ）、２リンク規制情報２４を付与するリンク列がないので、規制情報付与部１４は、規制情報付与処理を終了する。
【００２７】
通行不可リンク列がある場合には（ステップＳ２８：ＹＥＳ）、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（ステップＳ３０）。換言すれば、規制情報付与部１４は、通行可能リンク列および通行不可リンク列を比較して、通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複していない２つのリンクが存在するか否かを判断する。そして、通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複していない２つのリンクが存在する場合（第１の場合Ａ）には（ステップＳ３０：ＹＥＳ）、その２つのリンクに２リンク規制情報２４を付与し（ステップＳ３２）、処理をステップＳ２０に戻す。
【００２８】
通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複していない２つのリンクが存在しない場合には（ステップＳ３０：ＮＯ）、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（ステップＳ４０）。換言すれば、規制情報付与部１４は、通行可能リンク列および通行不可リンク列を比較して、通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複しているが代替の経路が存在する２つのリンクが存在するか否かを判断する。そして、通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複しているが代替の経路が存在する２つのリンクが存在する場合（第１の場合Ｂ）には（ステップＳ４０：ＹＥＳ）、規制情報付与部１４は、その２つのリンクに２リンク規制情報２４を付与し（ステップＳ４２）、処理をステップＳ２０に戻す。
【００２９】
通行不可リンク列を構成する１の交差点ノードに出入りする２つのリンクであって、通行可能リンク列と重複しているが代替の経路が存在する２つのリンクが存在しない場合には（ステップＳ４０：ＮＯ）、規制情報付与部１４は、ノード４点のみで構成される通行不可リンク列が存在するか否かを判断する（ステップＳ５０）。換言すれば、規制情報付与部１４は、通行不可リンク列を構成する交差点内リンクが１つのみであるか否かを判断する。そして、通行不可リンク列を構成する交差点内リンクが１つのみである場合（第２の場合）には（ステップＳ５０：ＹＥＳ）、補助リンク生成部１６は、その交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列、すなわち、ダミーリンク（交差点内リンク）およびダミーノード（交差点ノード）を新たに生成し（ステップＳ５２）、処理をステップＳ２０に戻す。なお、交差点内リンクの両端の交差点ノードを１本の交差点内リンクではなく、交差点内リンク列で結ぶのは、道路ネットワークデータ２２において、両端の２つのノードの組み合わせが同一となる複数のリンクの存在が認められていないからである。
【００３０】
規制情報付与部１４は、通行不可リンク列を構成する交差点内リンクが１つのみではない場合（第３の場合）には（ステップＳ５０：ＮＯ）、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複する交差点内リンク列を特定する（ステップＳ６０）。そして、補助リンク生成部１６は、その交差点内リンク列の両端の交差点ノードを結ぶダミーリンク（交差点内リンク）を新たに生成し（ステップＳ６２）、処理をステップＳ２０に戻す。
【００３１】
なお、ステップＳ６０において、上記第３の場合であって、通行不可リンク列を構成し通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合には、その交差点内リンク列を構成する交差点内リンクの数が最大となる交差点内リンク列である最大交差点内リンク列を特定して、その最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する（ステップＳ６２）。このように、最大交差点内リンク列の両端の交差点ノードを結ぶことにより、１つの交差点について新たに生成する交差点内リンクの数を少なくすることができる。また、これに伴い、１つの交差点について付与する規制情報を少なくすることもできる。さらに、ステップＳ６０において、上記第３の場合であって、通行可能リンク列と重複する交差点内リンク列を構成する交差点内リンクの数が３つ以上である場合において、最大交差点内リンク列が複数存在する場合には、通行可能リンク列および通行不可リンク列との重複数の合計が最も多い最大交差点内リンク列を特定して、その最大交差点内リンク列の両端の交差点ノードを結ぶ交差点リンクを新たに生成する（ステップＳ６２）。
【００３２】
以下、具体的な単位交差点を例示して、上述した規制情報付与処理の流れについて、詳しく説明する。
【００３３】
Ｃ．具体例１：
図４は、具体例１の単位交差点を示す説明図である。この単位交差点は、上り車線と下り車線とを有する二条化道路同士が交差する交差点である。図示するように、具体例１の単位交差点は、交差点外リンクＬ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５，Ｌ６，Ｌ７，Ｌ８と、交差点内リンクＬａｂ，Ｌｂｃ，Ｌｃｄ，Ｌｄａと、を含んでいる。そして、この単位交差点内では、交通規制情報２６によって、転回（いわゆるＵターン）が禁止されているものとする。
【００３４】
交差点外リンクＬ１は、交差点外ノードＮ１を始点ノードとし、交差点ノードＮａを終点ノードとする交差点外リンクである。交差点外リンクＬ２は、交差点ノードＮａを始点ノードとし、交差点外ノードＮ２を終点ノードとする交差点外リンクである。交差点外リンクＬ３は、交差点外ノードＮ３を始点ノードとし、交差点ノードＮｂを終点ノードとする交差点外リンクである。交差点外リンクＬ４は、交差点ノードＮｂを始点ノードとし、交差点外ノードＮ４を終点ノードとする交差点外リンクである。交差点外リンクＬ５は、交差点外ノードＮ５を始点ノードとし、交差点ノードＮｃを終点ノードとする交差点外リンクである。交差点外リンクＬ６は、交差点ノードＮｃを始点ノードとし、交差点外ノードＮ６を終点ノードとする交差点外リンクである。交差点外リンクＬ７は、交差点外ノードＮ７を始点ノードとし、交差点ノードＮｄを終点ノードとする交差点外リンクである。交差点外リンクＬ８は、交差点ノードＮｄを始点ノードとし、交差点外ノードＮ８を終点ノードとする交差点外リンクである。
【００３５】
また、交差点内リンクＬａｂは、交差点ノードＮａを始点ノードとし、交差点ノードＮｂを終点ノードとする交差点内リンクである。交差点内リンクＬｂｃは、交差点ノードＮｂを始点ノードとし、交差点ノードＮｃを終点ノードとする交差点内リンクである。交差点内リンクＬｃｄは、交差点ノードＮｃを始点ノードとし、交差点ノードＮｄを終点ノードとする交差点内リンクである。交差点内リンクＬｄａは、交差点ノードＮｄを始点ノードとし、交差点ノードＮａを終点ノードとする交差点内リンクである。
【００３６】
以下、リンクを、始点ノードと終点ノードとを、始点ノードから終点ノードに向かう矢印記号「→」でつなぐことによって表すものとする。例えば、交差点外リンクＬ１は、［Ｎ１→Ｎａ］と表される。また、リンク列は、始点ノードと終点ノードとを含む３つ以上のノードを、矢印記号「→」で連続的につなぐことによって表すものとする。例えば、交差点外リンクＬ１と、交差点内リンクＬａｂと、交差点外リンクＬ４とからなるリンク列は、［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］と表される。なお、以下すべての図内において、リンクは矢印記号を用いて表されているが、これは矢印の方向へ進行方向が一方向に定められていることを表している。図４には存在しないが、双方向へ進行可能なリンクの場合は、やじりが両端にある矢印記号を用いて表すこととする。
【００３７】
規制情報付与処理において、リンク列分類部１２は、上述した単位交差点について、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図５は、通行可能リンク列および通行不可リンク列を模式的に示す説明図である。図５（ａ）に通行可能リンク列を模式的に示した。また、図５（ｂ）に、通行不可リンク列を模式的に示した。なお、図５において、シンボル「●」は、リンク列の始点ノードを表している。また、図５（ａ）において、シンボル「●」から伸びる実線は、始点ノードからの通行が不可とされていないリンク列を表しており、終端の矢印は、そのリンク列の終点ノードを表している。また、図５（ｂ）において、シンボル「●」から伸びる実線は、始点ノードからの通行が不可とされているリンク列を表しており、終端のシンボル「◆」は、そのリンク列の終点ノードを表している。
【００３８】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ５→Ｎｃ→Ｎ６］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ１→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｂ→Ｎｃ→Ｎ６］
【００３９】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００４０】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、該当する連続３点は存在しない（図３のステップＳ４０：ＮＯ）。
【００４１】
次に、規制情報付与部１４は、ノード４点のみで構成される通行不可リンク列が存在するか否かを判断する（図３のステップＳ５０）。ここでは、該当する通行不可リンク列は存在しない（図３のステップＳ５０：ＮＯ）。
【００４２】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複する交差点内リンク列（以下、重複交差点内リンク列とも言う）を特定する（図３のステップＳ６０）。ここでは、重複交差点内リンク列として、リンク列［Ｎａ→Ｎｂ→Ｎｃ］と、リンク列［Ｎｃ→Ｎｄ→Ｎａ］と、リンク列［Ｎｂ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｄ→Ｎａ→Ｎｂ］とが抽出される。ここで、各重複交差点内リンク列を構成する交差点内リンクの数は、同じ（それぞれ２つ）である。また、各重複交差点内リンク列と通行可能リンク列との重複数も、同じ（それぞれ１つ）である。また、各重複交差点内リンク列と通行不可リンク列との重複数も、同じ（それぞれ２つ）である。そこで、補助リンク生成部１６は、通行不可リンク列を網羅する重複交差点内リンク列の組み合わせとして、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とリンク列［Ｎｃ→Ｎｄ→Ｎａ］とを選択し、これらの両端の交差点ノードを結ぶダミーリンク（交差点内リンク）を新たに生成する（ステップＳ６２）。すなわち、補助リンク生成部１６は、ダミーリンク［Ｎａ→Ｎｃ］と、ダミーリンク［Ｎｃ→Ｎａ］とを生成する。ダミーリンク［Ｎａ→Ｎｃ］と、ダミーリンク［Ｎｃ→Ｎａ］とをまとめて、ダミーリンクＤＬａｃとも言う（図６参照）。そして、補助リンク生成部１６は、処理を図２のステップＳ２０に戻す。
【００４３】
なお、ステップＳ６２において、補助リンク生成部１６は、通行不可リンク列を網羅する重複交差点内リンク列の組み合わせとして、リンク列［Ｎｂ→Ｎｃ→Ｎｄ］とリンク列［Ｎｄ→Ｎａ→Ｎｂ］とを選択し、これらの両端の交差点ノードを結ぶダミーリンクを新たに生成するものとしてもよい。また、ステップＳ６２において、補助リンク生成部１６は、４つの重複交差点内リンク列のうち、１つのリンク列、例えば、リンク列［Ｎａ→Ｎｂ→Ｎｃ］を選択し、この両端の交差点ノードを結ぶダミーリンクを新たに生成するものとしてもよい。この場合、詳細な説明は省略するが、後から再度、ステップＳ６２によって、リンク列［Ｎｃ→Ｎｄ→Ｎａ］に対して、ダミーリンクが生成される。
【００４４】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、ダミーリンクＤＬａｃを考慮して、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。
【００４５】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。なお、星印「★」が付されたリンク列は、ダミーリンクＤＬａｃを生成したことによって新たに発生したリンク列である。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ１→Ｎａ→Ｎｃ→Ｎ６］★
［Ｎ５→Ｎｃ→Ｎ６］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ５→Ｎｃ→Ｎａ→Ｎ２］★
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ１→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｄ→Ｎ８］★
［Ｎ５→Ｎｃ→Ｎｄ→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ５→Ｎｃ→Ｎａ→Ｎｂ→Ｎ４］★
［Ｎ３→Ｎｂ→Ｎｃ→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］★
［Ｎ７→Ｎｄ→Ｎａ→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｃ→Ｎ６］★
【００４６】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００４７】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とリンク列［Ｎｃ→Ｎｄ→Ｎａ］とが該当する（図３のステップＳ４０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とリンク列［Ｎｃ→Ｎｄ→Ｎａ］とに、２リンク規制情報２４を付与する（図３のステップＳ４２）。図６は、単位交差点について、ダミーリンクＤＬａｃ、および、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とリンク列［Ｎｃ→Ｎｄ→Ｎａ］とに２リンク規制情報２４が付与された様子を模式的に示す説明図である。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００４８】
処理がステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図７は、通行可能リンク列および通行不可リンク列を模式的に示す説明図である。図７（ａ）に、通行可能リンク列を模式的に示した。また、図７（ｂ）に、通行不可リンク列を模式的に示した。
【００４９】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｃ→Ｎ６］
［Ｎ５→Ｎｃ→Ｎ６］
［Ｎ５→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ５→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎ６］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎ８］
［Ｎ７→Ｎｄ→Ｎａ→Ｎ２］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ１→Ｎａ→Ｎｃ→Ｎｄ→Ｎ８］
［Ｎ５→Ｎｃ→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ７→Ｎｄ→Ｎａ→Ｎｃ→Ｎ６］
【００５０】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、リンク列［Ｎａ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｂ→Ｎｃ→Ｎａ］と、リンク列［Ｎｃ→Ｎａ→Ｎｂ］と、リンク列［Ｎｄ→Ｎａ→Ｎｃ］とが該当する（図３のステップＳ３０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎａ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｂ→Ｎｃ→Ｎａ］と、リンク列［Ｎｃ→Ｎａ→Ｎｂ］と、リンク列［Ｎｄ→Ｎａ→Ｎｃ］とに、２リンク規制情報２４を追加して付与する（ステップＳ３２）。図８は、リンク列［Ｎａ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｂ→Ｎｃ→Ｎａ］と、リンク列［Ｎｃ→Ｎａ→Ｎｂ］と、リンク列［Ｎｄ→Ｎａ→Ｎｃ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００５１】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。ここで特定される通行可能リンク列は、前回特定された通行可能リンク列と同じである。また、通行不可リンク列は存在しない（図２のステップＳ２８：ＮＯ）。したがって、規制情報付与部１４は、規制情報付与処理を終了する。
【００５２】
Ｄ．具体例２：
図９は、具体例２の単位交差点を示す説明図である。この単位交差点は、上り車線と下り車線とを有する二条化道路と双方向に通行が可能な一条道路とが交差する交差点である。図示するように、具体例２の単位交差点は、交差点外リンクＬ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５，Ｌ６と、交差点内リンクＬａｂと、を含んでいる。そして、この単位交差点内では、交通規制情報２６によって、転回（いわゆるＵターン）が禁止されているものとする。
【００５３】
交差点外リンクＬ１は、交差点外ノードＮ１および交差点ノードＮａを両端のノードとする双方向に通行が可能な交差点外リンクである。交差点外リンクＬ２は、交差点ノードＮａを始点ノードとし、交差点外ノードＮ２を終点ノードとする交差点外リンクである。交差点外リンクＬ３は、交差点外ノードＮ３を始点ノードとし、交差点ノードＮｂを終点ノードとする交差点外リンクである。交差点外リンクＬ４は、交差点外ノードＮ４および交差点ノードＮｂを両端のノードとする双方向に通行が可能な交差点外リンクである。交差点外リンクＬ５は、交差点ノードＮｂを始点ノードとし、交差点外ノードＮ５を終点ノードとする交差点外リンクである。交差点外リンクＬ６は、交差点外ノードＮ６を始点ノードとし、交差点ノードＮａを終点ノードとする交差点外リンクである。また、交差点内リンクＬａｂは、交差点ノードＮａおよび交差点ノードＮｂを両端のノードとする双方向に通行が可能な交差点内リンクである。
【００５４】
規制情報付与処理において、リンク列分類部１２は、上述した単位交差点について、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図１０は、通行可能リンク列および通行不可リンク列を模式的に示す説明図である。図１０（ａ）に、通行可能リンク列を模式的に示した。また、図１０（ｂ）に、通行不可リンク列を模式的に示した。
【００５５】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ３→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｂ→Ｎ５］
【００５６】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００５７】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、該当する連続３点存在しない（図３のステップＳ４０：ＮＯ）。
【００５８】
次に、規制情報付与部１４は、ノード４点のみで構成される通行不可リンク列が存在するか否かを判断する（図３のステップＳ５０）。ここでは、リンク列［Ｎ３→Ｎｂ→Ｎａ→Ｎ２］と、リンク列［Ｎ６→Ｎａ→Ｎｂ→Ｎ５］とが該当する（図３のステップＳ５０：ＹＥＳ）。そこで、補助リンク生成部１６は、リンク列［Ｎ３→Ｎｂ→Ｎａ→Ｎ２］およびリンク列［Ｎ６→Ｎａ→Ｎｂ→Ｎ５］に対して、これらのリンク列に含まれる交差点内リンクの両端の交差点ノードを結ぶ交差点内リンク列（ダミーリンク列）、すなわち、ダミーリンク（交差点内リンク）およびダミーノード（交差点ノード）を新たに生成する（ステップＳ５２）。すなわち、補助リンク生成部１６は、ダミーノードＤＮｃおよびダミーリンク［Ｎａ→Ｎｃ］，［Ｎｃ→Ｎａ］，［Ｎｃ→Ｎｂ］，［Ｎｂ→Ｎｃ］を生成する。双方向に通行可能なダミーリンク［Ｎａ→Ｎｃ］，［Ｎｃ→Ｎａ］をまとめて、ダミーリンクＤＬａｃとも言う（図１１参照）。また、双方向に通行可能なダミーリンク［Ｎｃ→Ｎｂ］，［Ｎｂ→Ｎｃ］をまとめて、ダミーリンクＤＬｂｃとも言う（図１１参照）。図１１は、ダミーノードＤＮｃおよびダミーリンクＤＬａｃ，ＤＬｂｃが生成された単位交差点を示す説明図である。そして、補助リンク生成部１６は、処理を図２のステップＳ２０に戻す。
【００５９】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、ダミーリンクＤＬａｃ，ＤＬｂｃを考慮して、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図１２は、通行可能リンク列および通行不可リンク列を模式的に示す説明図である。図１２（ａ）に、通行不可リンク列を模式的に示した。なお、図１２（ａ）では、見易さを考慮して、通行不可リンク列を、図１２（ａ−１）と図１２（ａ−２）とに分割して示した。また、図１２（ｂ）に、通行不可リンク列を模式的に示した。
【００６０】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。なお、星印「★」が付されたリンク列は、ダミーリンクＤＬａｃ，ＤＬｂｃを生成したことによって新たに発生したリンク列である。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］★
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］★
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］★
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］★
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］★
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］★
＜通行不可リンク列＞
［Ｎ３→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］★
［Ｎ６→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］★
【００６１】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００６２】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎ３→Ｎｂ→Ｎａ］と、リンク列［Ｎｂ→Ｎａ→Ｎ２］と、リンク列［Ｎ６→Ｎａ→Ｎｂ］と、リンク列［Ｎａ→Ｎｂ→Ｎ５］と、リンク列［Ｎ３→Ｎｂ→Ｎｃ］と、リンク列［Ｎｃ→Ｎａ→Ｎ２］と、リンク列［Ｎ６→Ｎａ→Ｎｃ］と、リンク列［Ｎｃ→Ｎｂ→Ｎ５］とが該当する（図３のステップＳ４０：ＹＥＳ）。そこで、規制情報付与部１４は、リンク列［Ｎ３→Ｎｂ→Ｎａ］に、２リンク規制情報２４を付与する（図３のステップＳ４２）（図１３（ａ）参照）。図１３は、単位交差点について、段階的に２リンク規制情報２４が付与されていく様子を模式的に示す説明図である。なお、今回は、この第１段階の２リンク規制情報２４の付与において、規制情報付与部１４は、リンク列［Ｎ３→Ｎｂ→Ｎａ］に、２リンク規制情報２４を付与するものとしたが、上述したリンク列［Ｎｂ→Ｎａ→Ｎ２］，［Ｎ６→Ｎａ→Ｎｂ］，［Ｎａ→Ｎｂ→Ｎ５］，［Ｎ３→Ｎｂ→Ｎｃ］，［Ｎｃ→Ｎａ→Ｎ２］，［Ｎ６→Ｎａ→Ｎｃ］，［Ｎｃ→Ｎｂ→Ｎ５］のいずれかに、２リンク規制情報２４を付与するものとしてもよい。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００６３】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。
【００６４】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
【００６５】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００６６】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎ６→Ｎａ→Ｎｂ］と、リンク列［Ｎａ→Ｎｂ→Ｎ５］と、リンク列［Ｎｃ→Ｎａ→Ｎ２］と、リンク列［Ｎ６→Ｎａ→Ｎｃ］と、リンク列［Ｎｃ→Ｎｂ→Ｎ５］とが該当する（図３のステップＳ４０：ＹＥＳ）。そこで、規制情報付与部１４は、リンク列［Ｎ６→Ｎａ→Ｎｂ］に、２リンク規制情報２４を追加して付与する（図３のステップＳ４２）（図１３（ｂ）参照）。なお、今回は、この第２段階の２リンク規制情報２４の付与において、規制情報付与部１４は、リンク列［Ｎ６→Ｎａ→Ｎｂ］に、２リンク規制情報２４を付与するものとしたが、上述したリンク列［Ｎａ→Ｎｂ→Ｎ５］に、２リンク規制情報２４を付与するものとしてもよい。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００６７】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。
【００６８】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
【００６９】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００７０】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎｃ→Ｎａ→Ｎ２］と、リンク列［Ｎｃ→Ｎｂ→Ｎ５］とが該当する（図３のステップＳ４０：ＹＥＳ）。そこで、規制情報付与部１４は、リンク列［Ｎｃ→Ｎａ→Ｎ２］に、２リンク規制情報２４を追加して付与する（図３のステップＳ４２）（図１３（ｃ）参照）。なお、今回は、この第３段階の２リンク規制情報２４の付与において、規制情報付与部１４は、リンク列［Ｎｃ→Ｎａ→Ｎ２］に、２リンク規制情報２４を付与するものとしたが、リンク列［Ｎｃ→Ｎｂ→Ｎ５］に、２リンク規制情報２４を付与するものとしてもよい。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００７１】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ１→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
＜通行不可リンク列＞
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ５］
【００７２】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００７３】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎｃ→Ｎｂ→Ｎ５］が該当する（図３のステップＳ４０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎｃ→Ｎｂ→Ｎ５］に、２リンク規制情報２４を追加して付与する（図３のステップＳ４２）（図１３（ｄ）参照）。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００７４】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。ここで特定される通行可能リンク列は、以下に示すとおりである。
＜通行可能リンク列＞
［Ｎ１→Ｎａ→Ｎ２］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ４］
［Ｎ１→Ｎａ→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎ５］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ１］
［Ｎ４→Ｎｂ→Ｎａ→Ｎ２］
［Ｎ３→Ｎｂ→Ｎ４］
［Ｎ３→Ｎｂ→Ｎ５］
［Ｎ３→Ｎｂ→Ｎｃ→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ１］
［Ｎ６→Ｎａ→Ｎ２］
［Ｎ６→Ｎａ→Ｎｃ→Ｎｂ→Ｎ４］
【００７５】
一方、通行不可リンク列は存在しない（図２のステップＳ２８：ＮＯ）。したがって、規制情報付与部１４は、規制情報付与処理を終了する。
【００７６】
Ｅ．具体例３：
図１４は、具体例３の単位交差点を示す説明図である。この単位交差点は、上り車線と下り車線とがそれぞれ側道を有する二条化道路と、上り車線と下り車線とがともに側道を有していない二条化道路が交差する交差点である。図示するように、具体例３の単位交差点は、交差点外リンクＬ１，Ｌ２，Ｌ３，Ｌ４，Ｌ５，Ｌ６，Ｌ７，Ｌ８，Ｌ９，Ｌ１０，Ｌ１１，Ｌ１２と、交差点内リンクＬａｂ，Ｌｂｃ，Ｌｃｄ，Ｌｄｅ，Ｌｅｆ，Ｌｆｇ，Ｌｇｈ，Ｌｈａ，Ｌｈｃ，Ｌｄｇと、を含んでいる。
【００７７】
交差点外リンクＬ１は、交差点ノードＮａを始点ノードとし、交差点外ノードＮ１を終点ノードとする交差点外リンクである。交差点外リンクＬ２は、交差点外ノードＮ２を始点ノードとし、交差点ノードＮｂを終点ノードとする交差点外リンクである。交差点外リンクＬ３は、交差点ノードＮｂを始点ノードとし、交差点外ノードＮ３を終点ノードとする交差点外リンクである。交差点外リンクＬ４は、交差点ノードＮｃを始点ノードとし、交差点外ノードＮ４を終点ノードとする交差点外リンクである。交差点外リンクＬ５は、交差点外ノードＮ５を始点ノードとし、交差点ノードＮｄを終点ノードとする交差点外リンクである。交差点外リンクＬ６は、交差点外ノードＮ６を始点ノードとし、交差点ノードＮｅを終点ノードとする交差点外リンクである。交差点外リンクＬ７は、交差点ノードＮｅを始点ノードとし、交差点外ノードＮ７を終点ノードとする交差点外リンクである。交差点外リンクＬ８は、交差点外ノードＮ８を始点ノードとし、交差点ノードＮｆを終点ノードとする交差点外リンクである。交差点外リンクＬ９は、交差点ノードＮｆを始点ノードとし、交差点外ノードＮ９を終点ノードとする交差点外リンクである。交差点外リンクＬ１０は、交差点ノードＮｇを始点ノードとし、交差点外ノードＮ１０を終点ノードとする交差点外リンクである。交差点外リンクＬ１１は、交差点外ノードＮ１１を始点ノードとし、交差点ノードＮｈを終点ノードとする交差点外リンクである。交差点外リンクＬ１２は、交差点外ノードＮ１２を始点ノードとし、交差点ノードＮａを終点ノードとする交差点外リンクである。
【００７８】
また、交差点内リンクＬａｂは、交差点ノードＮａを始点ノードとし、交差点ノードＮｂを終点ノードとする交差点内リンクである。交差点内リンクＬｂｃは、交差点ノードＮｂを始点ノードとし、交差点ノードＮｃを終点ノードとする交差点内リンクである。交差点内リンクＬｃｄは、交差点ノードＮｃを始点ノードとし、交差点ノードＮｄを終点ノードとする交差点内リンクである。交差点内リンクＬｄｅは、交差点ノードＮｄを始点ノードとし、交差点ノードＮｅを終点ノードとする交差点内リンクである。交差点内リンクＬｅｆは、交差点ノードＮｅを始点ノードとし、交差点ノードＮｆを終点ノードとする交差点内リンクである。交差点内リンクＬｆｇは、交差点ノードＮｆを始点ノードとし、交差点ノードＮｇを終点ノードとする交差点内リンクである。交差点内リンクＬｇｈは、交差点ノードＮｇを始点ノードとし、交差点ノードＮｈを終点ノードとする交差点内リンクである。交差点内リンクＬｈａは、交差点ノードＮｈを始点ノードとし、交差点ノードＮａを終点ノードとする交差点内リンクである。交差点内リンクＬｈｃは、交差点ノードＮｈを始点ノードとし、交差点ノードＮｃを終点ノードとする交差点内リンクである。交差点内リンクＬｄｇは、交差点ノードＮｄを始点ノードとし、交差点ノードＮｇを終点ノードとする交差点内リンクである。
【００７９】
そして、この単位交差点内では、以下に示す複雑な交通規制情報が定められているものとする。
＜交通規制情報＞
・交差点外ノードＮ２から交差点外ノードＮ３，Ｎ４，Ｎ７，Ｎ９，Ｎ１０への通行は可能である。
・交差点外ノードＮ２から交差点外ノードＮ１への通行は不可である。
・交差点外ノードＮ５から交差点外ノードＮ１，Ｎ１０への通行は可能である。
・交差点外ノードＮ５から交差点外ノードＮ３，Ｎ４，Ｎ７，Ｎ９への通行は不可である。
・交差点外ノードＮ６から交差点外ノードＮ７，Ｎ９への通行は可能である。
・交差点外ノードＮ６から交差点外ノードＮ１，Ｎ３，Ｎ４，Ｎ１０への通行は不可である。
・交差点外ノードＮ８から交差点外ノードＮ１，Ｎ３，Ｎ４，Ｎ９，Ｎ１０への通行は可能である。
・交差点外ノードＮ８から交差点外ノードＮ７への通行は不可である。
・交差点外ノードＮ１１から交差点外ノードＮ４，Ｎ７への通行は可能である。
・交差点外ノードＮ１１から交差点外ノードＮ１，Ｎ３，Ｎ９，Ｎ１０への通行は不可である。
・交差点外ノードＮ１２から交差点外ノードＮ１，Ｎ３への通行は可能である。
・交差点外ノードＮ１２から交差点外ノードＮ４，Ｎ７，Ｎ９，Ｎ１０への通行は不可である。
【００８０】
規制情報付与処理において、リンク列分類部１２は、上述した単位交差点について、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図１５は、通行可能リンク列を模式的に示す説明図である。また、図１６は、通行不可リンク列を模式的に示す説明図である。なお、図１６では、見易さを考慮して、通行不可リンク列を、図１６（ａ）と図１６（ｂ）とに分割して示した。
【００８１】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
Ｎ２→Ｎｂ→Ｎ３
Ｎ２→Ｎｂ→Ｎｃ→Ｎ４
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎ７
Ｎ６→Ｎｅ→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎ４
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１２→Ｎａ→Ｎ１
Ｎ１２→Ｎａ→Ｎｂ→Ｎ３
＜通行不可リンク列＞
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｅ→Ｎ７
Ｎ５→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ６→Ｎｅ→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ６→Ｎｅ→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ６→Ｎｅ→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎａ→Ｎ１
Ｎ１１→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ１２→Ｎａ→Ｎｂ→Ｎｃ→Ｎ４
Ｎ１２→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１２→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ１２→Ｎａ→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
【００８２】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、リンク列［Ｎ５→Ｎｄ→Ｎｅ］と、リンク列［Ｎｅ→Ｎｆ→Ｎｇ］と、リンク列［Ｎ１１→Ｎｈ→Ｎａ］と、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とが該当する（図３のステップＳ３０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎ５→Ｎｄ→Ｎｅ］と、リンク列［Ｎｅ→Ｎｆ→Ｎｇ］と、リンク列［Ｎ１１→Ｎｈ→Ｎａ］と、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とに、２リンク規制情報２４を追加して付与する（ステップＳ３２）。図１７は、リンク列［Ｎ５→Ｎｄ→Ｎｅ］と、リンク列［Ｎｅ→Ｎｆ→Ｎｇ］と、リンク列［Ｎ１１→Ｎｈ→Ｎａ］と、リンク列［Ｎａ→Ｎｂ→Ｎｃ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００８３】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。
【００８４】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
Ｎ２→Ｎｂ→Ｎ３
Ｎ２→Ｎｂ→Ｎｃ→Ｎ４
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎ７
Ｎ６→Ｎｅ→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎ４
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１２→Ｎａ→Ｎ１
Ｎ１２→Ｎａ→Ｎｂ→Ｎ３
＜通行不可リンク列＞
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
【００８５】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００８６】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、該当する連続３点存在しない（図３のステップＳ４０：ＮＯ）。
【００８７】
次に、規制情報付与部１４は、ノード４点のみで構成される通行不可リンク列が存在するか否かを判断する（図３のステップＳ５０）。ここでは、該当する通行不可リンク列は存在しない（図３のステップＳ５０：ＮＯ）。
【００８８】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複する重複交差点内リンク列を特定する（図３のステップＳ６０）。ここでは、重複交差点内リンク列として、リンク列［Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ］と、リンク列［Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ］と、リンク列［Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ］と、リンク列［Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ］と、リンク列［Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ］と、リンク列［Ｎｄ→Ｎｇ→Ｎｈ］と、リンク列［Ｎｇ→Ｎｈ→Ｎｃ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ］と、リンク列［Ｎｃ→Ｎｄ→Ｎｇ］とが抽出される。そして、補助リンク生成部１６は、以下に説明するように、上述した重複交差点内リンク列の中から、ダミーリンクを生成する重複交差点内リンク列を決定して、その重複交差点内リンク列について、ダミーリンクを新たに生成する（ステップＳ６２）。
【００８９】
図１８は、ダミーリンクを生成する重複交差点リンク列を決定する方法を説明するための説明図である。図１８では、各重複交差点内リンク列について、通行可能リンク列との重複数と、通行不可リンク列との重複数と、通行可能リンク列および通行不可リンク列との重複数の合計（合計重複数）と、重複交差点内リンク列を構成する交差点内リンクの数（交差点内リンク数）とを示した。
【００９０】
まず、補助リンク生成部１６は、経路に対する影響が大きい重複交差点内リンク列、すなわち、重複交差点内リンク列を構成する交差点内リンクの数（交差点内リンク数）が最大となる最大交差点内リンク列を特定する。ここでは、最大交差点内リンク列として、交差点内リンク数が３である６つの重複交差点内リンク列［Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ］，［Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ］，［Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ］，［Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ］，［Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ］，［Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ］が抽出される。
【００９１】
そして、補助リンク生成部１６は、これら６つの最大重複交差点内リンク列の中から、経路に対する影響が大きい最大交差点内リンク列、すなわち、通行可能リンク列および通行不可リンク列との重複数の合計（合計重複数）が最も多い最大交差点内リンク列を特定する。ここでは、合計重複数が３である２つの最大交差点内リンク列［Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ］，［Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ］が抽出される。
【００９２】
そして、補助リンク生成部１６は、これらの最大交差点内リンク列を、ダミーリンクを生成する重複交差点リンク列として決定し、これらの最大交差点内リンク列について、それぞれ、ダミーリンクを生成する。すなわち、補助リンク生成部１６は、最大交差点内リンク列［Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ］の両端の交差点ノードＮｄ，Ｎａを結ぶダミーリンク［Ｎｄ→Ｎａ］と、最大交差点内リンク列［Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ］の両端の交差点ノードＮｈ，Ｎｅを結ぶダミーリンク［Ｎｈ→Ｎｅ］とを新たに生成する。ダミーリンク［Ｎｄ→Ｎａ］を、ダミーリンクＤＬｄａとも言う（図１９参照）。また、ダミーリンク［Ｎｈ→Ｎｅ］を、ダミーリンクＤＬｈｅとも言う（図１９参照）。図１９は、ダミーリンクＤＬｄａ，ＤＬｈｅが生成された単位交差点を模式的に示す説明図である。そして、補助リンク生成部１６は、処理を図２のステップＳ２０に戻す。
【００９３】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、ダミーリンクＤＬｄａ，ＤＬｈｅを考慮して、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。図２０は、通行可能リンク列を模式的に示す説明図である。図２０では、見易さを考慮して、通行可能リンク列を、図２０（ａ）と図２０（ｂ）とに分割して示した。また、図２１は、通行不可リンク列を模式的に示す説明図である。図２１では、見易さを考慮して、通行不可リンク列を、図２１（ａ）と図２１（ｂ）とに分割して示した。
【００９４】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。なお、星印「★」が付されたリンク列は、ダミーリンクＤＬｄａ，ＤＬｈｅを生成したことによって新たに発生したリンク列である。
＜通行可能リンク列＞
Ｎ２→Ｎｂ→Ｎ３
Ｎ２→Ｎｂ→Ｎｃ→Ｎ４
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎａ→Ｎ１★
Ｎ５→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎ７
Ｎ６→Ｎｅ→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎ４
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎｅ→Ｎ７★
Ｎ１２→Ｎａ→Ｎ１
Ｎ１２→Ｎａ→Ｎｂ→Ｎ３
＜通行不可リンク列＞
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎａ→Ｎ１★
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎａ→Ｎｂ→Ｎ３★
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｅ→Ｎ７★
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎｅ→Ｎｆ→Ｎ９★
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
【００９５】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、リンク列［Ｎｃ→Ｎｄ→Ｎａ］と、リンク列［Ｎｄ→Ｎａ→Ｎｂ］と、リンク列［Ｎｇ→Ｎｈ→Ｎｅ］と、リンク列［Ｎｈ→Ｎｅ→Ｎｆ］とが該当する（図３のステップＳ３０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎｃ→Ｎｄ→Ｎａ］と、リンク列［Ｎｄ→Ｎａ→Ｎｂ］と、リンク列［Ｎｇ→Ｎｈ→Ｎｅ］と、リンク列［Ｎｈ→Ｎｅ→Ｎｆ］とに、２リンク規制情報２４を追加して付与する（ステップＳ３２）。図２２は、リンク列［Ｎｃ→Ｎｄ→Ｎａ］と、リンク列［Ｎｄ→Ｎａ→Ｎｂ］と、リンク列［Ｎｇ→Ｎｈ→Ｎｅ］と、リンク列［Ｎｈ→Ｎｅ→Ｎｆ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【００９６】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。
【００９７】
ここで特定される通行可能リンク列および通行不可リンク列は、それぞれ、以下に示す通りである。
＜通行可能リンク列＞
Ｎ２→Ｎｂ→Ｎ３
Ｎ２→Ｎｂ→Ｎｃ→Ｎ４
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎ７
Ｎ６→Ｎｅ→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎ４
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎｅ→Ｎ７
Ｎ１２→Ｎａ→Ｎ１
Ｎ１２→Ｎａ→Ｎｂ→Ｎ３
＜通行不可リンク列＞
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ５→Ｎｄ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ１１→Ｎｈ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
【００９８】
そして、規制情報付与部１４は、通行不可リンク列にあって、通行可能リンク列にないノードの連続３点が存在するか否かを判断する（図３のステップＳ３０）。ここでは、該当する連続３点は存在しない（図３のステップＳ３０：ＮＯ）。
【００９９】
次に、規制情報付与部１４は、通行不可リンク列と通行可能リンク列とに重複するが、代替の経路があるノードの連続３点が存在するか否かを判断する（図３のステップＳ４０）。ここでは、リンク列［Ｎｄ→Ｎｇ→Ｎｈ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ］とが該当する（図３のステップＳ４０：ＹＥＳ）。したがって、規制情報付与部１４は、リンク列［Ｎｄ→Ｎｇ→Ｎｈ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ］とに、２リンク規制情報２４を追加して付与する（図３のステップＳ４２）。図２３は、リンク列［Ｎｄ→Ｎｇ→Ｎｈ］と、リンク列［Ｎｈ→Ｎｃ→Ｎｄ］とに、２リンク規制情報２４が追加して付与された様子を模式的に示す説明図である。そして、規制情報付与部１４は、処理を図２のステップＳ２０に戻す。
【０１００】
処理が図２のステップＳ２０に戻ると、リンク列分類部１２は、上述した単位交差点について、再度、通行可能リンク列および通行不可リンク列を特定する（図２のステップＳ２０、および、ステップＳ２６）。ここで特定される通行可能リンク列は、以下に示すとおりである。
＜通行可能リンク列＞
Ｎ２→Ｎｂ→Ｎ３
Ｎ２→Ｎｂ→Ｎｃ→Ｎ４
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎ７
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｅ→Ｎｆ→Ｎ９
Ｎ２→Ｎｂ→Ｎｃ→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ５→Ｎｄ→Ｎａ→Ｎ１
Ｎ５→Ｎｄ→Ｎｇ→Ｎ１０
Ｎ６→Ｎｅ→Ｎ７
Ｎ６→Ｎｅ→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎ１
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎａ→Ｎｂ→Ｎ３
Ｎ８→Ｎｆ→Ｎｇ→Ｎｈ→Ｎｃ→Ｎ４
Ｎ８→Ｎｆ→Ｎ９
Ｎ８→Ｎｆ→Ｎｇ→Ｎ１０
Ｎ１１→Ｎｈ→Ｎｃ→Ｎ４
Ｎ１１→Ｎｈ→Ｎｅ→Ｎ７
Ｎ１２→Ｎａ→Ｎ１
Ｎ１２→Ｎａ→Ｎｂ→Ｎ３
【０１０１】
一方、通行不可リンク列は存在しない（図２のステップＳ２８：ＮＯ）。したがって、規制情報付与部１４は、規制情報付与処理を終了する。
【０１０２】
以上説明した本実施例の交差点内ネットワークデータ整備装置１０では、整備前、すなわち、２リンク規制情報２４を付与する前の道路ネットワークデータ２２において、単位交差点に、ダミーリンクやダミーノードは設けられていない。そして、本実施例の交差点内ネットワークデータ整備装置１０では、規制情報付与部１４が２リンク規制情報２４を付与するに際し、補助リンク生成部１６は、順次、通行可能リンク列および通行不可リンク列の構成に基づいて、交差点内リンク列（ダミーリンク列）を新たに生成したり、交差点内リンク（ダミーリンク）を新たに生成したり、交差点内リンク列も交差点内リンクも新たに生成しなかったりする。このため、必要最小限の交差点内リンク列および交差点リンクだけが新たに生成され、不必要となる可能性がある交差点内リンク列および交差点リンクが新たに生成されることはない。そして、不必要な２リンク規制情報２４が付与されることもない。また、規制情報付与部１４は、通行可能リンク列および通行不可リンク列を比較して、上記第１の場合に、オペレータの判断によらずに、２リンク規制情報２４を付与することができる。したがって、本実施例の交差点内ネットワークデータ整備装置１０によって、道路ネットワークデータ２２における単位交差点について、交差点内リンクおよび交差点外リンクに、２リンク規制情報２４を、効率的に付与することができる。
【０１０３】
また、本実施例の交差点内ネットワークデータ整備装置１０によれば、不必要な交差点内リンク列（ダミーリンク列）および交差点リンク（ダミーリンク）が新たに生成されることがなく、不必要な２リンク規制情報２４が付与されることもないので、電子地図データ記憶装置２０において、２リンク規制情報２４を記憶するための記憶容量を低減することもできる。
【０１０４】
Ｆ．変形例：
以上、本発明のいくつかの実施の形態について説明したが、本発明はこのような実施の形態になんら限定されるものではなく、その要旨を逸脱しない範囲内において種々なる態様での実施が可能である。例えば、以下のような変形が可能である。
【０１０５】
Ｆ１．変形例１：
上記実施例では、電子地図データ記憶装置２０は、交差点内ネットワークデータ整備装置１０の外部に接続されるものとしたが、本発明は、これに限られない。電子地図データ記憶装置２０は、交差点内ネットワークデータ整備装置１０の内部に備えられるものとしてもよい。
【０１０６】
Ｆ２．変形例２：
図２に示した規制情報付与処理において、道路ネットワークデータ２２および交通規制情報２６に誤りがないことが確定している場合には、ステップＳ２２，２４を省略するようにしてもよい。上記実施例では、規制情報付与処理中に、ステップＳ２２，２４を行うことによって、道路ネットワークデータ２２およびまたは交通規制情報２６にの誤りをチェックすることができる。
【０１０７】
Ｆ３．変形例３：
上記実施例の交差点内ネットワークデータ整備装置１０において、ソフトウェアによって実現した機能の一部を、ハードウェアによって実現するようにしてもよい。また、上記実施例の交差点内ネットワークデータ整備装置１０において、ハードウェアによって実現した機能の一部を、ソフトウェアによって実現するようにしてもよい。
【符号の説明】
【０１０８】
１０…交差点内ネットワークデータ整備装置
１２…リンク列分類部
１４…規制情報付与部
１６…補助リンク生成部
２０…電子地図データ記憶装置
２２…道路ネットワークデータ
２４…２リンク規制情報
２６…交通規制情報
Ｎａ，Ｎｂ，Ｎｃ，Ｎｄ，Ｎｅ，Ｎｆ，Ｎｇ，Ｎｈ…交差点ノード
Ｎ１〜Ｎ１２…交差点外ノード
Ｌａｂ，Ｌｂｃ，Ｌｃｄ，Ｌｄａ，Ｌｄｅ，Ｌｅｆ，Ｌｆｇ，Ｌｇｈ，Ｌｈａ，Ｌｈｃ，Ｌｄｇ…交差点内リンク
Ｌ１〜Ｌ１２…交差点外リンク
ＤＬａｃ，ＤＬｂｃ，ＤＬｄａ，ＤＬｈｅ…ダミーリンク
ＤＮｃ…ダミーノード
【図１】
2013210496.tif 000003
【図２】
2013210496.tif 000004
【図３】
2013210496.tif 000005
【図４】
2013210496.tif 000006
【図５】
2013210496.tif 000007
【図６】
2013210496.tif 000008
【図７】
2013210496.tif 000009
【図８】
2013210496.tif 000010
【図９】
2013210496.tif 000011
【図１０】
2013210496.tif 000012
【図１１】
2013210496.tif 000013
【図１２】
2013210496.tif 000014
【図１３】
2013210496.tif 000015
【図１４】
2013210496.tif 000016
【図１５】
2013210496.tif 000017
【図１６】
2013210496.tif 000018
【図１７】
2013210496.tif 000019
【図１８】
2013210496.tif 000020
【図１９】
2013210496.tif 000021
【図２０】
2013210496.tif 000022
【図２１】
2013210496.tif 000023
【図２２】
2013210496.tif 000024
【図２３】
2013210496.tif 000025