案内経路作成装置、案内経路作成方法、および、コンピュータプログラム
【課題】通過対象道路を全て通過する案内経路を効率良く作成する。
【解決手段】案内経路作成装置は、複数のノードとリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、処理対象ノードのうちの１つのノードである着目ノードについて、着目ノードに進入する進入リンクと着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する処理を、全ての処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、決定された進入リンクと脱出リンクの組み合わせに基づいて、通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、を備える。
【解決手段】案内経路作成装置は、複数のノードとリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、処理対象ノードのうちの１つのノードである着目ノードについて、着目ノードに進入する進入リンクと着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する処理を、全ての処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、決定された進入リンクと脱出リンクの組み合わせに基づいて、通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、案内経路作成装置、案内経路作成方法、および、コンピュータプログラムに関する。
【背景技術】
【０００２】
例えば、カーナビゲーション装置を始めとして、コンピュータで利用可能に電子化された地図データを利用して、車や歩行者に経路案内を行う技術は広く実用化されている。この際、営業における訪問経路の経路案内や道路調査のための経路案内など、通過すべき通過対象道路が予め決まっていて、通過対象道路をいかに効率良く通過する案内経路を作成できるかという技術の開発が行われている。（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−２４４６８９号公報
【特許文献２】特開平７−２４９０２５号公報
【特許文献３】特開平８−３２９０４１号公報
【特許文献４】特開平９−１６０９８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、通過対象道路を全て通過する案内経路を効率良く作成する技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態又は適用例として実現することが可能である。
【０００６】
［適用例１］案内経路作成装置であって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、
前記処理対象ノードのうちの１つのノードである着目ノードについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する進入脱出決定処理を、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、
を備える、案内経路作成装置。
こうすれば、処理対象ノードの全てについて、進入リンクと脱出リンクの一対一の組み合わせを決定したうえで、通過対象リンクを全て通過する案内経路を作成するので、案内経路を作成する作成速度を向上することができる。
【０００７】
［適用例２］適用例１に記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードに接続されている複数の前記通過対象リンクの数が奇数の場合には、当該複数の前記通過対象リンクのうちの一つを複製して仮想的な前記通過対象リンクとして追加することにより、あるいは、通過対象外である前記リンクのうち、通行可能なものを前記通過対象リンクとして追加することにより、前記着目ノードについて、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
こうすれば、進入リンクと脱出リンクの数を等しくして一対一の組み合わせを決定することにより、通過対象リンクを全て通過する案内経路を作成することができる。
【０００８】
［適用例３］適用例１または適用例２に記載の案内経路作成装置は、さらに、
通過対象リンクの全てについて、所定の条件に従って通過方向を定める有向化処理部を備え、
前記進入脱出決定部は、定められた通過対象リンクの通過方向に従って、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
通過対象リンクの全てを有向化してから、進入リンクと脱出リンクの一対一の組み合わせを決定するので、有向化されていないリンクを含む状態より、案内経路を作成する作成速度を向上することができる。
【０００９】
［適用例４］適用例３に記載の案内経路作成装置であって、
前記所定の条件は、交通規制を遵守することを含む、案内経路生成装置。
こうすれば、交通規制を遵守した案内経路を作成できる。
【００１０】
［適用例５］適用例３または適用例４に記載の案内経路作成装置であって、
前記有向化処理部における所定の条件は、前記着目ノードの前記進入リンクの数と前記脱出リンクの数の差を小さくすることを含む、案内経路生成装置。
こうすれば、後に進入リンクと脱出リンクの一対一の組み合わせを効率良く決定できる。
【００１１】
［適用例６］適用例３ないし適用例５のいずれかに記載の案内経路作成装置であって、
前記所定の条件は、前記着目ノードを通過する際の通過コストを小さくすることを含む、案内経路生成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１２】
［適用例７］適用例１ないし適用例６のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードを通過する際の通過コストを小さくするように、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１３】
［適用例８］適用例１ないし適用例７のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、
前記処理対象ノードのうち、前記脱出リンクの数が前記進入リンクの数より少ない脱出不足ノードを出発地ノードとし、前記処理対象ノードのうち、前記進入リンクの数が前記脱出リンクの数より少ない進入不足ノードを目的地ノードとする追加経路を探索し、
前記追加経路に対応するリンクを前記通過対象リンクに追加することにより、各処理対象ノードについて、前記進入リンクの数と前記脱出リンクの数を等しくし、
前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
こうすれば、進入リンクの数と前記脱出リンクの数を等しくしてから、進入リンクと脱出リンクの一対一の組み合わせを決定するので、確実に進入リンクと脱出リンクの一対一の組み合わせを決定して案内経路を作成できる。
【００１４】
［適用例９］適用例１ないし適用例８のいずれかに記載の案内経路作成装置であって、
前記案内経路作成部は、前記進入リンクと前記脱出リンクの組み合わせに従って一筆書き経路を作成し、
一筆書き経路が複数作成された場合には、前記進入リンクと前記脱出リンクの組み合わせのパターンが複数個許容される前記処理対象ノードについて、前記進入リンクと前記脱出リンクの組み合わせのパターンを変更することにより、複数の一筆書き経路を繋いで、最終的に一つの一筆書き経路からなる前記案内経路を作成する、案内経路作成装置。
こうすれば、１つの最終的な案内経路を効率よく作成できる。
【００１５】
［適用例１０］適用例９に記載の案内経路作成装置であって、
前記進入リンクと前記脱出リンクの組み合わせのパターンが３以上許容される場合には、通過コストの低下が最も少ないパターンに変更する、案内経路作成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１６】
なお、本発明は、種々の形態で実現することが可能であり、例えば、案内経路作成方法、コンピュータに案内経路を作成させるためのコンピュータプログラム、当該コンピュータプログラムを記録した記録媒体等の形態で実現することができる。
【図面の簡単な説明】
【００１７】
【図１】実施例としての案内経路作成装置の概略構成を示す説明図である。
【図２】地図データＤ１１の内容を説明する図である。
【図３】案内経路の作成の対象となる地域の道路の一例をノードとリンクのネットワークで表した図である。
【図４】実施例における案内経路作成処理の処理ステップを示すフローチャートである。
【図５】通過対象リンクＬＫＳの有向化について説明する第１の図である。
【図６】通過対象リンクＬＫＳの有向化について説明する第２の図である。
【図７】通過対象リンクＬＫＳの有向化について説明する第３の図である。
【図８】通過対象リンクＬＫＳの有向化について説明する第４の図である。
【図９】無向リンクについて脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する第１の図である。
【図１０】無向リンクについて脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する第２の図である。
【図１１】本実施例において脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。
【図１２】進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する第１の図である。
【図１３】進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する第２の図である。
【図１４】通過対処リンクを追加する処理について説明する第１の図である。
【図１５】通過対処リンクを追加する処理について説明する第２の図である。
【図１６】一筆書き経路の決定について説明する図である。
【図１７】進入リンクと脱出リンクの組み合わせの変更について説明する図である。
【図１８】第１変形例における案内経路作成処理の処理ステップを示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照しながら、実施例に基づき説明する。
【００１９】
Ａ．実施例：
・案内経路作成装置の構成：
図１は、実施例としての案内経路作成装置の概略構成を示す説明図である。案内経路作成装置２００は、大型計算機、パーソナルコンピュータなどの周知のコンピュータである。案内経路作成装置２００は、ＣＰＵ２０１と、ＲＡＭやＲＯＭなどの内部記憶装置２０３と、ハードディスクなどの外部記憶装置２０４と、外部機器（例えば、キーボード、マウスなど）とのインターフェースである入出力部２０２を備えている。
【００２０】
外部記憶装置２０４には、地図データＤ１１が格納されている。図２は、地図データＤ１１の内容を説明する図である。地図データＤ１１は、画像データベースＣＤ１と、経路データベースＣＤ２と、属性データベースＣＤ３とを含む。図２は、画像データベースＣＤ１と経路データベースＣＤ２と、属性データベースＣＤ３の内容が、それぞれ、概念的に示されている。
【００２１】
画像データベースＣＤ１には、地図画像を表すデータ（地図画像データ）がベクトルデータ形式で格納されている。なお、地図画像データは、ベクトルデータ形式に代えて、ビットマップ形式やＪＰＥＧデータ形式などのラスタデータ形式で格納されていても良い。この地図画像データには、地形や建物、道路等の形状を表すデータが含まれている。
【００２２】
経路データベースＣＤ２には、地図画像データが表す地図画像に対応した領域に存在する交通経路に関する経路データが格納されている。経路データは、交通経路の地表上における配置を示すネットワークを表すデータである。ネットワークデータは、交通経路における要素点ＮＤ（ノードと呼ぶ。）を表すノードデータと、ノード間を結ぶ線分ＬＫ（リンクと呼ぶ）を表すリンクデータとを含む。ノードＮＤは、例えば、交差点、分岐点、終点、始点、駅などの乗降位置などを表している。リンクＬＫは、例えば、車道、線路、歩行者道などの交通経路を表している。
【００２３】
属性データベースＣＤ３には、属性データが格納されている。属性データは、ノードＮＤあるいはリンクＬＫに関連付けられており、その属性を示す情報である。属性データは、ノードＮＤ、リンクＬＫに関する様々なデータを含む。例えば、リンクＬＫに関連付けられる属性データは、リンクＬＫの名称（例えば、道路の名称）、リンクＬＫの種類（例えば、高速道路であること）、リンクＬＫの規制情報（例えば、一方通行であること）、その他の情報（例えば、高速道路であれば、区間料金など）を含んでも良い。ノードＮＤに関連付けられる属性データは、ノードＮＤに対応する交差点の名称、ノードＮＤに対応する交差点の規制情報（例えば、ある方向から見て、左折可、右折不可、直進可など）、関連付けられたノードＮＤに関する画像を表す画像データ（例えば、ノードＮＤ（例えば、交差点、駅）の分岐状況を示す模式図や案内板を示す画像）を含んでも良い。１つのノードＮＤまたはリンクＬＫに関連付けられる属性データは、１つであっても良いし、複数であっても良い。また、属性データベースＣＤ３は、１つのデータベースである必要はなく、例えば、高速道路に関する属性データと、店舗や駅などの物件に関する属性データと、規制情報に関する属性データは、別々のデータベースとしても良い。
【００２４】
内部記憶装置２０３には、経路作成プログラムが格納されており、ＣＰＵ２０１が当該プログラムを実行することにより、図２の内部記憶装置２０３に図示した機能ブロックの機能を実現される。実現される機能ブロックは、通過対象リンク認識部Ｍ１１と、処理対象ノード認識部Ｍ１２と、リンク有向化処理部Ｍ１３と、進入脱出決定部Ｍ１４と、経路案内作成部Ｍ１５を含む。
【００２５】
通過対象リンク認識部Ｍ１１は、入出力部２０２を介して、例えば、操作者の入力を受け付けて、地図データＤ１１の経路データベースＣＤ２に含まれるリンクＬＫの中から、作成されるべき案内経路において通過すべき道に対応するリンク（通過対象リンク）ＬＫＳを認識する。処理対象ノード認識部Ｍ１２は、地図データＤ１１の経路データベースＣＤ２に含まれるノードＮＤの中から、認識された複数の通過対象リンクＬＫＳの両端に接続されている全てのノード（処理対象ノード）ＮＤＳを認識する。リンク有向化処理部Ｍ１３は、後述する所定の条件に従って通過対象リンクＬＫＳの全てについて通過方向を定める。進入脱出決定部Ｍ１４は、処理対象ノードＮＤＳのそれぞれについて、当該処理対象ノードに接続するリンクＬＫについて、当該処理対象ノードＮＤＳに進入するリンク（進入リンク）と当該処理対象ノードＮＤＳから脱出するリンクの一対一の組み合わせを決定する。ここで、進入リンクと脱出リンクの組み合わせは、少なくとも当該処理対象ノードＮＤＳに接続される通過対象リンクＬＫＳについては決定される。経路案内作成部Ｍ１５は、進入リンクと脱出リンクの組み合わせに基づいて、全ての通過対象リンクＬＫＳを通過する案内経路を作成する。
【００２６】
図３は、案内経路の作成の対象となる地域の道路の一例をノードとリンクのネットワークで表した図である。図３において、黒丸および２重丸はノードＮＤを表し、細線および太線はリンクＬＫを表している。なお、リンクＬＫのうち、矢印で表されているものは、矢印の方向への一方通行の道路に対応するリンクＬＫ、すなわち、属性情報として矢印の方向への一方通行を表す属性情報が対応付けられているリンクＬＫを表す。リンクＬＫのうち、矢印ではない単なる直線で表されているものは、両方向に通行可能な道路に対応するリンクＬＫを表す。リンクＬＫのうち、太線で示したリンクは、通過対象リンクＬＫＳを表す。ノードＮＤのうち、２重丸は、処理対象ノードＮＤＳを表す。以下では、図３のように指定された通過対象リンクＬＫＳを全て通過する案内経路を作成する案内経路作成処理について説明する。
【００２７】
・案内経路作成装置２００の動作：
図４は、実施例における案内経路作成処理の処理ステップを示すフローチャートである。案内経路作成処理は、ＣＰＵ２０１によって実行される処理である。案内経路作成処理が開始されると、ＣＰＵ２０１は、通過対象リンクＬＫＳを全て有向化する。有向化とは、通過対象リンクＬＫＳの通過方向を定めることである。
【００２８】
図５〜図８は、通過対象リンクＬＫＳの有向化について説明する図である。図５〜図８において、白丸はノードＮＤを表し、白丸の中にノードを識別するためのアルファベットを付した。以下では、白丸の中に付されたアルファベットを用いてノードＮＤを記述する場合がある。例えば、白丸の中に「Ａ」が付されたノードＮＤは、ノードＡと記述される。図５〜図８において、ノード間を結ぶ線は全てリンクを表す。図５〜図８において、一点破線の太線で表されたリンクは、有向化されていない通過対象リンクＬＫＳを表し、一点破線の太線の矢印で表されたリンクは、既に矢印の方向に有向化されている通過対象リンクＬＫＳを表す。細線で表されたリンクは、通過対象リンクＬＫＳではないリンクを表す。また、ノード付近に表された細い破線の矢印と×印は、当該ノードにおける交通規制を表す。例えば、図５（ａ）に示すノードＡは、ノードＤ側から進入する場合に右折禁止であり、ノードＢ側から進入する場合において左折禁止であることが示されている。また、図５〜図８において、白抜きの太い矢印の右側の図で、実線の太線の矢印で表されたリンクは、白抜きの太い矢印のステップにおいて有向化された通過対象リンクＬＫＳを表す。
【００２９】
有向化において、交通規制を遵守することが一つの条件とされ、ＣＰＵ２０１は、一方通行の道路に対応する通過対象リンクＬＫＳは、通過可能な方向に有向化する。例えば、図５（ａ）に示すように、交通規制により、ノードＡからノードＣへの方向の通過が規制されている場合は、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳは、ノードＣからノードＡへの方向に有向化される。また、図５（ｂ）に示すように、ノードＢからノードＡへ進入する方向に有向化された通過対象リンクＬＫＳが存在しているとき、当該通過対象リンクＬＫＳを通過した場合に交通規制によりノードＡからノードＣへの方向に脱出する他にないので、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳは、ノードＡからノードＣへの方向に有向化される。
【００３０】
既に有向化されている通過対象リンクＬＫＳと二差路接続している通過対象リンクＬＫＳは、道なりに走行するように有向化される。例えば、図６（ａ）に示す例では、ノードＡとノードＤとの間を接続する通過対象リンクＬＫＳがノードＡからノードＤへの方向に既に有向化されているので、ノードＢとノードＡとの間を接続する通過対象リンクＬＫＳがノードＢからノードＡへの方向に有向化される。また、通過対象リンクＬＫＳではないリンクを含めると四差接続しているノードについても、通過対象リンクＬＫＳだけを見れば、既に有向化されている通過対象リンクＬＫＳと二差路接続している通過対象リンクＬＫＳも道なりに走行するように有向化される。例えば、図６（ｂ）に示す例では、ノードＢとノードＡとの間を接続する通過対象リンクＬＫＳがノードＢからノードＡへの方向に既に有向化されているので、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳがノードＡからノードＣへの方向に有向化される。
【００３１】
また、ある処理対象ノード（着目ノード）から他の処理対象ノードへと脱出する方向へ有向化されたリンクである脱出リンクの数と他の処理対象ノードから着目ノードへと進入する方向へ有向化されたリンクである進入リンクとの数の差はゼロに近づくように、通過対象リンクＬＫＳは有向化される。例えば、図７（ａ）に示す例では、着目ノードＡからの脱出リンクが２本既に決まっているので、有向化されていない他の２本の通過対象リンクＬＫＳは、着目ノードＡへの進入リンクとなるように有向化される。また、図７（ｂ）に示す例では、着目ノードＡへの進入リンクが２本既に決まっているので、有向化されていない着目ノードＡとノードＣとの間の通過対象リンクＬＫＳは、着目ノードＡからの脱出リンクとなるように有向化される。
【００３２】
また、着目ノードと接続する通過対象リンクＬＫＳで既に有向化されているものがある場合、その有向化済みの通過対象リンクＬＫＳが着目ノードをなるべく低いコストで通過できるように、他の通過対象リンクＬＫＳが有向化される。通過コストは、通過に要する時間の長さを表し、通過に要する時間が長いほど通過コストは高いとされ、通過に要する時間が短いほど通過コストは低いとされる。例えば、右折や左折と比較すると直進は通過コストが低い。例えば、図８に示す例では、ノードＢから着目ノードＡへの進入リンクが既に決まっているので、当該進入リンクから通過コストの低い脱出リンクができるように、ノードＡとノードＤとの間を接続する通過対象リンクＬＫＳは、ノードＡからノードＢへの方向に有向化される。
【００３３】
以上説明した有向化のルールを適用しても有向化できなかった通過対象リンクＬＫＳについては、特に理由なく一の方向に有向化される。
【００３４】
通過対象リンクＬＫＳが有向化されると、ＣＰＵ２０１は、進入リンクの数と脱出リンクの数が等しい処理対象ノードＮＤＳを着目ノードとして、進入リンクと脱出リンクとの一対一の組み合わせを決定する（ステップＳ２０）。
【００３５】
ここで、先のステップＳ１０において、通過対象リンクＬＫＳを全て有向化した理由について説明しておく。図９および図１０は、有向化されていないリンク（無向リンク）について脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。図９では、着目ノードＡを中心とする四差路を表すネットワークが示されている。着目ノードＡと、着目ノードＡに接続するリンクと着目ノードＡとは異なる端部で接続しているノード（図９では、ノードＢ、Ｃ、Ｄ、Ｅの４つ）とを要素とした接続行列によって、リンクは表現できる。この接続行列において、例えば、ノードＡとノードＢ間のリンクがノードＡからノードＢへの有向リンクの場合は、行列（Ａ、Ｂ）の位置に値を持ち、行列（Ｂ、Ａ）の位置には値を持たない（０）。一方、ノードＡとノードＢ間の無向リンクである場合は、行列（Ａ、Ｂ）の位置と、行列（Ｂ、Ａ）の位置との両方に値を持つ。値を持つ場合、その値は、そのノード間に存在するリンクの本数である。ここで、図９（ｂ）着目ノードＡに接続するリンクについて、進入リンクと脱出リンクの組み合わせを決定するということは、進入元となるノードを行成分に、脱出先となるノードを列成分として接続行列において、行と列のいずれを見ても、要素の合計値が１にしかならないようにすることに等しい。これを無向リンクとして処理した場合、全てのリンクが進入リンクと脱出リンクの両方の候補となるため、組み合わせの数は、着目ノードに接続するリンクの数をｎとすると、ｎ×（ｎ−１）通りとなる（図１０）。
【００３６】
この組み合わせ問題に類似した有名な問題に「ｎクイーン問題」が知られている。ｎクイーン問題は、チェスのクイーンの可動範囲（縦・横・斜め方向に無限大）に、他のクイーンが配置されないようにｎ×ｎのチェス盤上にｎ個のクイーンを配置しようという問題である。本実施例における進入リンクと脱出リンクの組み合わせを決定する問題は、ｎクイーン問題において、クイーンの可動範囲から斜め方向を除いて、クイーンの可動範囲を縦・横方向に無限大とした問題と等しい。ｎクイーン問題は、ｎの数が８個を超えると計算量が膨大になることが知られている。本実施例において進入リンクと脱出リンクの組み合わせを決定する問題もまた、着目ノードに接続するリンクの数が８を超えると、現実的な計算量で組み合わせを決定することは困難になる。
【００３７】
図１１は、本実施例において脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。本実施例では、処理対象ノード（着目ノード）に接続するリンクを予め有向化しているので、考えなくてはならない組み合わせの数を大幅に減らすことができる。具体的には、上述したｎの数を半減した組み合わせの数を考えれば足りる。例えば、図１１に示すように、着目ノードに接続するリンクの数が４であるときは、無向リンクで考えなければならない組み合わせの数ｎ（ｎ―１）の式において、ｎ＝４／２＝２とした数、すなわち、２通りを考えるだけでよい。このように、着目ノードに接続するリンクを有向化した場合、ｎが８になるということは、着目ノードに接続するリンクの数が１６になるということになる。現実世界の交差点を考えた場合、後述するように、脱出リンクと進入リンクの数を一致させるためにリンクを追加しても、着目ノードに接続するリンクの数は１６未満になると考えられる。
【００３８】
図１２および図１３は、進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する図である。進入リンクと脱出リンクの組み合わせは、交通規制に従うように決定される。例えば、図１２に示すように、ノードＤ側から着目ノードＡを直進してノードＢへ通過することが禁止されている場合には、図１２において右側に示すように、ノードＥと着目ノードＡへの進入リンクと着目ノードＡからノードＢへの脱出リンクとを組み合わせると共に、ノードＤから着目ノードＡへの進入リンクと、着目ノードＡからノードＣへの脱出リンクとを組み合わせる。
【００３９】
交通規制に違反しない場合には、通過コストが低くなるように、進入リンクと脱出リンクの組み合わせを決定する。通過コストは、通常、直進＜左折＜右折＜Ｕターンと設定されることが多く、これに従うと、組み合わせとして優先される順番は、１．直進、２．左折、３．右折、４．Ｕターンとなる。例えば、図１３（ａ）に示すように、着目ノードＡに交通規制がない場合、進入リンクと脱出リンクの組み合わせのパターンは、図１２（ｂ）に示すパターンと、図１２（ｃ）に示すパターンの２とおりとなるが、この場合、着目ノードＡを直進する組み合わせである図１２（ｂ）に示すパターンに決定される。
【００４０】
以上説明した組み合わせの決定ルールを適用しても組み合わせが一義的に定まらない処理対象ノードＮＤＳについては、特に理由なく一つの組み合わせに決定される。また、全ての進入脱出リンクを用いる組み合わせが一つも求まらなかった場合は、進入と脱出のリンク数が等しい場合においても、ステップ３０を複数回行うことにより、最低一つの組み合わせを決定する。道路の規制や、リンクの構成上、どうしても組み合わせが求まらない場合は、そこで案内経路を切るようにしてもよい。
【００４１】
次に、ＣＰＵ２０１は、接続される進入リンクと脱出リンクの数が等しくない処理対象ノードＮＤＳについて、接続される進入リンクと脱出リンクの数が等しくなるように、通過対象リンクを追加する（ステップＳ３０）。図１４および図１５は、通過対象リンクを追加する処理について説明する図である。図１４および図１５において、一点破線で示す矢印が既に決まっている通過対象リンクＬＫＳを表す。図１４において、ノードＡは、接続される進入リンク（ノードＣからのリンクとノードＤからのリンク）の数より脱出リンク（ノードＤへのリンク）の数が少ない脱出不足ノードである。脱出不足ノードは、接続される進入リンクの数と脱出リンクの数を等しくするために、脱出リンクを追加する必要がある。一方、ノードＥは、接続される脱出リンク（ノードＦへのリンクとノードＧへのリンク）の数より進入リンク（ノードＨからのリンク）の数が少ない進入不足ノードである。進入不足ノードは、接続される進入リンクの数と脱出リンクの数を等しくするために、進入リンクを追加する必要がある。ここで、ＣＰＵ２０１は、処理対象ノードＮＤＳのうち、脱出不足ノードを出発地ノード候補とし、進入不足ノードを目的地ノード候補として、経路探索を実行する。その結果、接続経路が求められると、ＣＰＵ２０１は、求められた接続経路で出発地ノード候補と、目的地ノード候補との両方で、進入リンクと脱出リンクの組が確定するか否かを判断する。図１４に示す例では、ノードＡからノードＩとノードＪを介してノードＥに至る接続経路が探索されている。出発地ノード候補であるノードＡにおいては、新たに求められた経路の一部であるノードＡからノードＩへの脱出リンクが追加されることによって、進入リンクと脱出リンクの組み合わせを確定できる。しかしながら、図１４に示す例では、目的地ノード候補であるノードＥにおいて、新たに求められた経路の一部であるノードＪからノードＥへの進入リンクが追加されても、交通規制により、進入リンクと脱出リンクの組を確定できない。この場合、追加すべき通過対象経路は確定しない。
【００４２】
一方、図１５に示す例では、ノードＡが、進入不足ノードであり、ノードＦが脱出不足ノードである。この場合、ＣＰＵ２０１は、ノードＦを出発地ノード候補とし、ノードＡを目的地ノード候補として、経路探索を実行する。図１５に示す例では、ノードＦからノードＪとノードＤを介してノードＥに至る接続経路が探索されている。そして、図１５に示す例では、出発地ノード候補であるノードＦにおいて、新たに求められた経路の一部であるノードＦからノードＪへの脱出リンクが追加されることによって、進入リンクと脱出リンクの組み合わせを確定できる。しかも、図１５に示す例では、目的地ノード候補であるノードＡにおいて、新たに求められた経路の一部であるノードＤからノードＡへの進入リンクが追加されることによって、進入リンクと脱出リンクの組を確定できる。この場合、求められた接続経路を構成するリンクが追加すべき通過対象リンクＬＫＳとして確定する。なお、探索される接続経路は、既に通過対象リンクＬＫＳとされているリンクであっても、通過対象リンクＬＫＳではないリンクであっても良い。接続経路を構成するリンクが通過対象リンクＬＫＳとして追加される際、既に通過対象リンクＬＫＳとなっているリンクについては、仮想的なリンクが複製されて新たな通過対象リンクＬＫＳとして追加される。複製された通過対象リンクＬＫＳが存在するリンクに対応する道は、案内経路において複数回通過することになる。接続経路を構成するリンクが通過対象リンクＬＫＳとして追加される際、通過対象リンクＬＫＳではないリンクについては、当該リンクが通過対象リンクＬＫＳとして追加される。
【００４３】
このように、通過対象リンクを追加すると、ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されたか否かを判断する（ステップＳ４０）。
【００４４】
ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されていないと判断すると（ステップＳ４０：ＮＯ）、ステップＳ３０に戻って、通過対象リンクを追加しながら進入リンクと脱出リンクの組み合わせを決定していく上述の処理を繰り返す。
【００４５】
一方、ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されていると判断すると（ステップＳ４０：ＹＥＳ）、各処理対象ノードＮＤＳについて決定された進入リンクと脱出リンクの組み合わせに従って、一筆書き経路を決定する（ステップＳ５０）。図１６は、一筆書き経路の決定について説明する図である。図１６の上図では、全てのノードについて進入リンクと脱出リンクの組み合わせが決定されていることが示されている。この組み合わせに従って、全てのリンクを一度は通るように一筆書き経路を描いていくと、図１６の下図のように、実線の太線で示す第１の一筆書き経路と、破線の太線で示す第２の一筆書き経路が作成されることが解る。このように、全てのリンクを一度は通るように一筆書き経路を描いていくと必ずしも一つの一筆書き経路になるわけではなく、複数の一筆書き経路が作成されることがある。
【００４６】
ＣＰＵ２０１は、一筆書き経路が一つであるか否かを判断する（ステップＳ６０）。この結果、一筆書き経路が一つであると判断すると（ステップＳ６０：ＹＥＳ）、当該一筆書き経路を最終的な案内経路として、案内経路作成処理を終了する。
【００４７】
一方、ＣＰＵ２０１は、一筆書き経路が一つでない（複数ある）と判断すると（ステップＳ６０：ＮＯ）、一筆書き経路を減らすように、進入リンクと脱出リンクの組み合わせを変更可能な処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを変更する（ステップＳ７０）。
【００４８】
図１７は、進入リンクと脱出リンクの組み合わせの変更について説明する図である。図１７の例では、ノードＡについて、進入リンクと脱出リンクの組み合わせを変更している。すなわち、変更前のノードＡにおいては、ノードＥからノードＡへの進入リンクとノードＡからノードＣへの脱出リンクの組み合わせと、ノードＢからノードＡへの進入リンクとノードＡからノードＤへの脱出リンクの組み合わせであったところ（図１７：上図）、変更後のノードＡにおいては、ノードＥからノードＡへの進入リンクとノードＡからノードＤへの脱出リンクの組み合わせと、ノードＢからノードＡへの進入リンクとノードＡからノードＣへの脱出リンクの組み合わせとしている（図１７：下図）。この結果、２つあった一筆書き経路が一つになることが解る。ここで、ＣＰＵ２０１は、交通規制により進入リンクと脱出リンクの組み合わせのパターンが一つだけのノードに関しては、このような組み合わせの変更は行わない。ＣＰＵ２０１は、進入リンクと脱出リンクの組み合わせのパターンが複数あるノードを探索して、進入リンクと脱出リンクの組み合わせのパターンが複数あるノード関して、このような組み合わせの変更を行う。なお、進入リンクと脱出リンクの組み合わせのパターンが３つ以上存在し、組み合わせの変更が複数種類可能である場合には、ＣＰＵ２０１は、通過コストが低い方の組み合わせに変更する。この結果、最終的に作成される案内経路は、効率良く通過対象リンクに対応する道路を通過できる経路を案内するものとなる。
【００４９】
進入リンクと脱出リンクの組み合わせの変更を行うと、再び、一筆書き経路が一つであるか否かを判断する（ステップＳ６０）。この結果、一筆書き経路が一つであると判断すると（ステップＳ６０：ＹＥＳ）、当該一筆書き経路を最終的な案内経路として、案内経路作成処理を終了する。一方、ＣＰＵ２０１は、一筆書き経路が一つでない（複数ある）と判断するとステップＳ７０に戻って、再び、別の処理対象ノードＮＤＳに関して、進入リンクと脱出リンクの組み合わせの変更を行う処理を繰り返す。
【００５０】
ここで、オイラーグラフについて説明しておく。全てのリンクが有向リンクである場合、全てのノードにおいて、接続されている進入リンクの数と脱出リンクの数とが等しい場合、必ず一つのノードから同じノードに戻り全てのリンクを一度だけ通過する一つの一筆書き経路（オイラー閉路）が作成可能であることが知られている。本実施例では、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを決定している（例えば、図１６）ので、全ての処理対象ノードＮＤＳについて、当該ノードに接続されている進入リンクの数と脱出リンクの数とが等しいことが保証されている。したがって、ステップＳ７０における進入リンクと脱出リンクの組み合わせの変更を繰り返せば、一つの一筆書き経路を最終的な案内経路として作成することが可能である。
【００５１】
以上説明した上記実施例によれば、全ての通過対象リンクＬＫＳについて、通過するルートを通る案内経路を作成する計算時間を短縮できる。具体的には、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを決定してから一筆書きの案内ルートを作成するので、最終的には確実に一つの一筆書きの案内ルート（オイラー閉路）を作成することができる。さらには、全ての通過対象ルートを有向化してから進入リンクと脱出リンクの組み合わせを決定するので、計算時間を劇的に短縮できる。また、進入リンクと脱出リンクの組み合わせの決定、通過対象ルートの通過方向の決定（有向化）、複数の一筆書き経路を一つにするための進入リンクと脱出リンクの組み合わせの変更の際に、通過コストを考慮して通過コストが低くなるように決定または変更を行うので、生成される案内経路のトータルの通過コストを低減することができる。
【００５２】
Ｂ．変形例
・第１変形例：
上記実施例では、ステップＳ１０（図４）において、上述した有向化のルールを適用しても有向化できなかった通過対象リンクＬＫＳについては、特に理由なく一の方向に有向化しているが、これに代えて、有向化できなかった通過対象リンクＬＫＳについては、ステップＳ３０およびステップＳ４０（図４）を行った後に、改めて上述のルールを適用して有向化しても良い。その例を、第１変形例として図１８を参照して説明する。図１８は、第１変形例における案内経路作成処理の処理ステップを示すフローチャートである。本変形例では、ＣＰＵ２０１は、まず、通過対象リンクを、交通規制・２差路接続・進入リンクと脱出リンクの差・通過コスト等により、可能な限り有向化する（ステップＳ１１０）。次に、ＣＰＵ２０１は、接続する全てのリンクが有向化されており、かつ、侵入と脱出の数が等しいノードについて、進入と脱出の組を決定する（ステップＳ１２０）。続いて、ＣＰＵ２０１は、接続する全て有向化リンクについて、進入と脱出の数が等しくないノードについて、差が小さくなるような経路を求める（ステップＳ１３０）。ＣＰＵ２０１は、求まった経路に該当する、有向化されていないリンクがあれば、経路と同じ方向に有向化し、なければ新規にリンクを追加する（ステップＳ１４０）。この後、ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されたかを判定する（ステップＳ１５０）。ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されている場合には（ステップＳ１５０：ＹＥＳ）、ステップＳ１６０の処理に進む。ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されていない場合には（ステップＳ１５０：ＮＯ）、上述したステップＳ１１０に戻って、ステップＳ１１０〜Ｓ１４０までの処理を繰り返す。ステップＳ１６０では、実施例におけるステップＳ５０（図４）と同様に一筆書き経路を決定する（ステップＳ１６０）。次に、ＣＰＵ２０１は、実施例におけるステップＳ６０と同様に、一筆書き経路が一つであるか判定する（ステップＳ１７０）。ＣＰＵ２０１は、一筆書き経路が一つである場合には（ステップＳ１７０：ＹＥＳ）、判定する処理を終了する。ＣＰＵ２０１は、一筆書き経路が複数ある場合には（ステップＳ１７０：ＮＯ）、実施例におけるステップＳ７０（図４）と同様に、一筆書き経路を減らすように進入脱出の組を変更し（ステップＳ１８０）、一筆書き経路が一つになるまでステップＳ１７０およびステップＳ１８０の処理を繰り返す。以上説明した第１変形例においても、実施例と同様に、最終的に通過対象リンクを全て通過する案内経路を短い計算時間で作成することができる。
【００５３】
・第２変形例：
上記実施例では、全ての処理対象ノードＮＤＳについて、脱出リンクの数と進入リンクの数を等しくしているが、処理対象リンクに対して案内経路が複数回通過している箇所について、その重複経路部分を削除することにより、処理対象ノードＮＤＳのうちの一つについては脱出リンクを一本少なくすると共に、他の一つについて進入リンクを一本少なくしても良い。こうすれば、脱出リンクが一本多いノードから進入リンクが一本多いノードに至る一本の一筆書きの案内経路（オイラー経路）を作成することができる。
【００５４】
・第３変形例：
上記実施例において、案内経路作成処理の全ての処理をソフトウェアによって実現しているが、案内経路作成処理の一部または全部の処理をハードウェアによって実現しても良い。
【００５５】
以上、本発明の実施例および変形例について説明したが、本発明はこれらの実施例および変形例になんら限定されるものではなく、その要旨を逸脱しない範囲内において種々の態様での実施が可能である。
【符号の説明】
【００５６】
２００…案内経路作成装置
２０１…ＣＰＵ
２０２…入出力部
２０３…内部記憶装置
２０４…外部記憶装置
Ｄ１１…地図データ
Ｍ１１…通過対象リンク認識部
Ｍ１２…処理対象ノード認識部
Ｍ１３…リンク有向化処理部
Ｍ１４…進入脱出決定部
Ｍ１５…経路案内作成部
【技術分野】
【０００１】
本発明は、案内経路作成装置、案内経路作成方法、および、コンピュータプログラムに関する。
【背景技術】
【０００２】
例えば、カーナビゲーション装置を始めとして、コンピュータで利用可能に電子化された地図データを利用して、車や歩行者に経路案内を行う技術は広く実用化されている。この際、営業における訪問経路の経路案内や道路調査のための経路案内など、通過すべき通過対象道路が予め決まっていて、通過対象道路をいかに効率良く通過する案内経路を作成できるかという技術の開発が行われている。（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平７−２４４６８９号公報
【特許文献２】特開平７−２４９０２５号公報
【特許文献３】特開平８−３２９０４１号公報
【特許文献４】特開平９−１６０９８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、通過対象道路を全て通過する案内経路を効率良く作成する技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態又は適用例として実現することが可能である。
【０００６】
［適用例１］案内経路作成装置であって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、
前記処理対象ノードのうちの１つのノードである着目ノードについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する進入脱出決定処理を、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、
を備える、案内経路作成装置。
こうすれば、処理対象ノードの全てについて、進入リンクと脱出リンクの一対一の組み合わせを決定したうえで、通過対象リンクを全て通過する案内経路を作成するので、案内経路を作成する作成速度を向上することができる。
【０００７】
［適用例２］適用例１に記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードに接続されている複数の前記通過対象リンクの数が奇数の場合には、当該複数の前記通過対象リンクのうちの一つを複製して仮想的な前記通過対象リンクとして追加することにより、あるいは、通過対象外である前記リンクのうち、通行可能なものを前記通過対象リンクとして追加することにより、前記着目ノードについて、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
こうすれば、進入リンクと脱出リンクの数を等しくして一対一の組み合わせを決定することにより、通過対象リンクを全て通過する案内経路を作成することができる。
【０００８】
［適用例３］適用例１または適用例２に記載の案内経路作成装置は、さらに、
通過対象リンクの全てについて、所定の条件に従って通過方向を定める有向化処理部を備え、
前記進入脱出決定部は、定められた通過対象リンクの通過方向に従って、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
通過対象リンクの全てを有向化してから、進入リンクと脱出リンクの一対一の組み合わせを決定するので、有向化されていないリンクを含む状態より、案内経路を作成する作成速度を向上することができる。
【０００９】
［適用例４］適用例３に記載の案内経路作成装置であって、
前記所定の条件は、交通規制を遵守することを含む、案内経路生成装置。
こうすれば、交通規制を遵守した案内経路を作成できる。
【００１０】
［適用例５］適用例３または適用例４に記載の案内経路作成装置であって、
前記有向化処理部における所定の条件は、前記着目ノードの前記進入リンクの数と前記脱出リンクの数の差を小さくすることを含む、案内経路生成装置。
こうすれば、後に進入リンクと脱出リンクの一対一の組み合わせを効率良く決定できる。
【００１１】
［適用例６］適用例３ないし適用例５のいずれかに記載の案内経路作成装置であって、
前記所定の条件は、前記着目ノードを通過する際の通過コストを小さくすることを含む、案内経路生成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１２】
［適用例７］適用例１ないし適用例６のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードを通過する際の通過コストを小さくするように、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１３】
［適用例８］適用例１ないし適用例７のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、
前記処理対象ノードのうち、前記脱出リンクの数が前記進入リンクの数より少ない脱出不足ノードを出発地ノードとし、前記処理対象ノードのうち、前記進入リンクの数が前記脱出リンクの数より少ない進入不足ノードを目的地ノードとする追加経路を探索し、
前記追加経路に対応するリンクを前記通過対象リンクに追加することにより、各処理対象ノードについて、前記進入リンクの数と前記脱出リンクの数を等しくし、
前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
こうすれば、進入リンクの数と前記脱出リンクの数を等しくしてから、進入リンクと脱出リンクの一対一の組み合わせを決定するので、確実に進入リンクと脱出リンクの一対一の組み合わせを決定して案内経路を作成できる。
【００１４】
［適用例９］適用例１ないし適用例８のいずれかに記載の案内経路作成装置であって、
前記案内経路作成部は、前記進入リンクと前記脱出リンクの組み合わせに従って一筆書き経路を作成し、
一筆書き経路が複数作成された場合には、前記進入リンクと前記脱出リンクの組み合わせのパターンが複数個許容される前記処理対象ノードについて、前記進入リンクと前記脱出リンクの組み合わせのパターンを変更することにより、複数の一筆書き経路を繋いで、最終的に一つの一筆書き経路からなる前記案内経路を作成する、案内経路作成装置。
こうすれば、１つの最終的な案内経路を効率よく作成できる。
【００１５】
［適用例１０］適用例９に記載の案内経路作成装置であって、
前記進入リンクと前記脱出リンクの組み合わせのパターンが３以上許容される場合には、通過コストの低下が最も少ないパターンに変更する、案内経路作成装置。
こうすれば、効率良く通過対象リンクに対応する道を通過できる案内経路を作成できる。
【００１６】
なお、本発明は、種々の形態で実現することが可能であり、例えば、案内経路作成方法、コンピュータに案内経路を作成させるためのコンピュータプログラム、当該コンピュータプログラムを記録した記録媒体等の形態で実現することができる。
【図面の簡単な説明】
【００１７】
【図１】実施例としての案内経路作成装置の概略構成を示す説明図である。
【図２】地図データＤ１１の内容を説明する図である。
【図３】案内経路の作成の対象となる地域の道路の一例をノードとリンクのネットワークで表した図である。
【図４】実施例における案内経路作成処理の処理ステップを示すフローチャートである。
【図５】通過対象リンクＬＫＳの有向化について説明する第１の図である。
【図６】通過対象リンクＬＫＳの有向化について説明する第２の図である。
【図７】通過対象リンクＬＫＳの有向化について説明する第３の図である。
【図８】通過対象リンクＬＫＳの有向化について説明する第４の図である。
【図９】無向リンクについて脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する第１の図である。
【図１０】無向リンクについて脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する第２の図である。
【図１１】本実施例において脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。
【図１２】進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する第１の図である。
【図１３】進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する第２の図である。
【図１４】通過対処リンクを追加する処理について説明する第１の図である。
【図１５】通過対処リンクを追加する処理について説明する第２の図である。
【図１６】一筆書き経路の決定について説明する図である。
【図１７】進入リンクと脱出リンクの組み合わせの変更について説明する図である。
【図１８】第１変形例における案内経路作成処理の処理ステップを示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照しながら、実施例に基づき説明する。
【００１９】
Ａ．実施例：
・案内経路作成装置の構成：
図１は、実施例としての案内経路作成装置の概略構成を示す説明図である。案内経路作成装置２００は、大型計算機、パーソナルコンピュータなどの周知のコンピュータである。案内経路作成装置２００は、ＣＰＵ２０１と、ＲＡＭやＲＯＭなどの内部記憶装置２０３と、ハードディスクなどの外部記憶装置２０４と、外部機器（例えば、キーボード、マウスなど）とのインターフェースである入出力部２０２を備えている。
【００２０】
外部記憶装置２０４には、地図データＤ１１が格納されている。図２は、地図データＤ１１の内容を説明する図である。地図データＤ１１は、画像データベースＣＤ１と、経路データベースＣＤ２と、属性データベースＣＤ３とを含む。図２は、画像データベースＣＤ１と経路データベースＣＤ２と、属性データベースＣＤ３の内容が、それぞれ、概念的に示されている。
【００２１】
画像データベースＣＤ１には、地図画像を表すデータ（地図画像データ）がベクトルデータ形式で格納されている。なお、地図画像データは、ベクトルデータ形式に代えて、ビットマップ形式やＪＰＥＧデータ形式などのラスタデータ形式で格納されていても良い。この地図画像データには、地形や建物、道路等の形状を表すデータが含まれている。
【００２２】
経路データベースＣＤ２には、地図画像データが表す地図画像に対応した領域に存在する交通経路に関する経路データが格納されている。経路データは、交通経路の地表上における配置を示すネットワークを表すデータである。ネットワークデータは、交通経路における要素点ＮＤ（ノードと呼ぶ。）を表すノードデータと、ノード間を結ぶ線分ＬＫ（リンクと呼ぶ）を表すリンクデータとを含む。ノードＮＤは、例えば、交差点、分岐点、終点、始点、駅などの乗降位置などを表している。リンクＬＫは、例えば、車道、線路、歩行者道などの交通経路を表している。
【００２３】
属性データベースＣＤ３には、属性データが格納されている。属性データは、ノードＮＤあるいはリンクＬＫに関連付けられており、その属性を示す情報である。属性データは、ノードＮＤ、リンクＬＫに関する様々なデータを含む。例えば、リンクＬＫに関連付けられる属性データは、リンクＬＫの名称（例えば、道路の名称）、リンクＬＫの種類（例えば、高速道路であること）、リンクＬＫの規制情報（例えば、一方通行であること）、その他の情報（例えば、高速道路であれば、区間料金など）を含んでも良い。ノードＮＤに関連付けられる属性データは、ノードＮＤに対応する交差点の名称、ノードＮＤに対応する交差点の規制情報（例えば、ある方向から見て、左折可、右折不可、直進可など）、関連付けられたノードＮＤに関する画像を表す画像データ（例えば、ノードＮＤ（例えば、交差点、駅）の分岐状況を示す模式図や案内板を示す画像）を含んでも良い。１つのノードＮＤまたはリンクＬＫに関連付けられる属性データは、１つであっても良いし、複数であっても良い。また、属性データベースＣＤ３は、１つのデータベースである必要はなく、例えば、高速道路に関する属性データと、店舗や駅などの物件に関する属性データと、規制情報に関する属性データは、別々のデータベースとしても良い。
【００２４】
内部記憶装置２０３には、経路作成プログラムが格納されており、ＣＰＵ２０１が当該プログラムを実行することにより、図２の内部記憶装置２０３に図示した機能ブロックの機能を実現される。実現される機能ブロックは、通過対象リンク認識部Ｍ１１と、処理対象ノード認識部Ｍ１２と、リンク有向化処理部Ｍ１３と、進入脱出決定部Ｍ１４と、経路案内作成部Ｍ１５を含む。
【００２５】
通過対象リンク認識部Ｍ１１は、入出力部２０２を介して、例えば、操作者の入力を受け付けて、地図データＤ１１の経路データベースＣＤ２に含まれるリンクＬＫの中から、作成されるべき案内経路において通過すべき道に対応するリンク（通過対象リンク）ＬＫＳを認識する。処理対象ノード認識部Ｍ１２は、地図データＤ１１の経路データベースＣＤ２に含まれるノードＮＤの中から、認識された複数の通過対象リンクＬＫＳの両端に接続されている全てのノード（処理対象ノード）ＮＤＳを認識する。リンク有向化処理部Ｍ１３は、後述する所定の条件に従って通過対象リンクＬＫＳの全てについて通過方向を定める。進入脱出決定部Ｍ１４は、処理対象ノードＮＤＳのそれぞれについて、当該処理対象ノードに接続するリンクＬＫについて、当該処理対象ノードＮＤＳに進入するリンク（進入リンク）と当該処理対象ノードＮＤＳから脱出するリンクの一対一の組み合わせを決定する。ここで、進入リンクと脱出リンクの組み合わせは、少なくとも当該処理対象ノードＮＤＳに接続される通過対象リンクＬＫＳについては決定される。経路案内作成部Ｍ１５は、進入リンクと脱出リンクの組み合わせに基づいて、全ての通過対象リンクＬＫＳを通過する案内経路を作成する。
【００２６】
図３は、案内経路の作成の対象となる地域の道路の一例をノードとリンクのネットワークで表した図である。図３において、黒丸および２重丸はノードＮＤを表し、細線および太線はリンクＬＫを表している。なお、リンクＬＫのうち、矢印で表されているものは、矢印の方向への一方通行の道路に対応するリンクＬＫ、すなわち、属性情報として矢印の方向への一方通行を表す属性情報が対応付けられているリンクＬＫを表す。リンクＬＫのうち、矢印ではない単なる直線で表されているものは、両方向に通行可能な道路に対応するリンクＬＫを表す。リンクＬＫのうち、太線で示したリンクは、通過対象リンクＬＫＳを表す。ノードＮＤのうち、２重丸は、処理対象ノードＮＤＳを表す。以下では、図３のように指定された通過対象リンクＬＫＳを全て通過する案内経路を作成する案内経路作成処理について説明する。
【００２７】
・案内経路作成装置２００の動作：
図４は、実施例における案内経路作成処理の処理ステップを示すフローチャートである。案内経路作成処理は、ＣＰＵ２０１によって実行される処理である。案内経路作成処理が開始されると、ＣＰＵ２０１は、通過対象リンクＬＫＳを全て有向化する。有向化とは、通過対象リンクＬＫＳの通過方向を定めることである。
【００２８】
図５〜図８は、通過対象リンクＬＫＳの有向化について説明する図である。図５〜図８において、白丸はノードＮＤを表し、白丸の中にノードを識別するためのアルファベットを付した。以下では、白丸の中に付されたアルファベットを用いてノードＮＤを記述する場合がある。例えば、白丸の中に「Ａ」が付されたノードＮＤは、ノードＡと記述される。図５〜図８において、ノード間を結ぶ線は全てリンクを表す。図５〜図８において、一点破線の太線で表されたリンクは、有向化されていない通過対象リンクＬＫＳを表し、一点破線の太線の矢印で表されたリンクは、既に矢印の方向に有向化されている通過対象リンクＬＫＳを表す。細線で表されたリンクは、通過対象リンクＬＫＳではないリンクを表す。また、ノード付近に表された細い破線の矢印と×印は、当該ノードにおける交通規制を表す。例えば、図５（ａ）に示すノードＡは、ノードＤ側から進入する場合に右折禁止であり、ノードＢ側から進入する場合において左折禁止であることが示されている。また、図５〜図８において、白抜きの太い矢印の右側の図で、実線の太線の矢印で表されたリンクは、白抜きの太い矢印のステップにおいて有向化された通過対象リンクＬＫＳを表す。
【００２９】
有向化において、交通規制を遵守することが一つの条件とされ、ＣＰＵ２０１は、一方通行の道路に対応する通過対象リンクＬＫＳは、通過可能な方向に有向化する。例えば、図５（ａ）に示すように、交通規制により、ノードＡからノードＣへの方向の通過が規制されている場合は、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳは、ノードＣからノードＡへの方向に有向化される。また、図５（ｂ）に示すように、ノードＢからノードＡへ進入する方向に有向化された通過対象リンクＬＫＳが存在しているとき、当該通過対象リンクＬＫＳを通過した場合に交通規制によりノードＡからノードＣへの方向に脱出する他にないので、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳは、ノードＡからノードＣへの方向に有向化される。
【００３０】
既に有向化されている通過対象リンクＬＫＳと二差路接続している通過対象リンクＬＫＳは、道なりに走行するように有向化される。例えば、図６（ａ）に示す例では、ノードＡとノードＤとの間を接続する通過対象リンクＬＫＳがノードＡからノードＤへの方向に既に有向化されているので、ノードＢとノードＡとの間を接続する通過対象リンクＬＫＳがノードＢからノードＡへの方向に有向化される。また、通過対象リンクＬＫＳではないリンクを含めると四差接続しているノードについても、通過対象リンクＬＫＳだけを見れば、既に有向化されている通過対象リンクＬＫＳと二差路接続している通過対象リンクＬＫＳも道なりに走行するように有向化される。例えば、図６（ｂ）に示す例では、ノードＢとノードＡとの間を接続する通過対象リンクＬＫＳがノードＢからノードＡへの方向に既に有向化されているので、ノードＡとノードＣとの間を接続する通過対象リンクＬＫＳがノードＡからノードＣへの方向に有向化される。
【００３１】
また、ある処理対象ノード（着目ノード）から他の処理対象ノードへと脱出する方向へ有向化されたリンクである脱出リンクの数と他の処理対象ノードから着目ノードへと進入する方向へ有向化されたリンクである進入リンクとの数の差はゼロに近づくように、通過対象リンクＬＫＳは有向化される。例えば、図７（ａ）に示す例では、着目ノードＡからの脱出リンクが２本既に決まっているので、有向化されていない他の２本の通過対象リンクＬＫＳは、着目ノードＡへの進入リンクとなるように有向化される。また、図７（ｂ）に示す例では、着目ノードＡへの進入リンクが２本既に決まっているので、有向化されていない着目ノードＡとノードＣとの間の通過対象リンクＬＫＳは、着目ノードＡからの脱出リンクとなるように有向化される。
【００３２】
また、着目ノードと接続する通過対象リンクＬＫＳで既に有向化されているものがある場合、その有向化済みの通過対象リンクＬＫＳが着目ノードをなるべく低いコストで通過できるように、他の通過対象リンクＬＫＳが有向化される。通過コストは、通過に要する時間の長さを表し、通過に要する時間が長いほど通過コストは高いとされ、通過に要する時間が短いほど通過コストは低いとされる。例えば、右折や左折と比較すると直進は通過コストが低い。例えば、図８に示す例では、ノードＢから着目ノードＡへの進入リンクが既に決まっているので、当該進入リンクから通過コストの低い脱出リンクができるように、ノードＡとノードＤとの間を接続する通過対象リンクＬＫＳは、ノードＡからノードＢへの方向に有向化される。
【００３３】
以上説明した有向化のルールを適用しても有向化できなかった通過対象リンクＬＫＳについては、特に理由なく一の方向に有向化される。
【００３４】
通過対象リンクＬＫＳが有向化されると、ＣＰＵ２０１は、進入リンクの数と脱出リンクの数が等しい処理対象ノードＮＤＳを着目ノードとして、進入リンクと脱出リンクとの一対一の組み合わせを決定する（ステップＳ２０）。
【００３５】
ここで、先のステップＳ１０において、通過対象リンクＬＫＳを全て有向化した理由について説明しておく。図９および図１０は、有向化されていないリンク（無向リンク）について脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。図９では、着目ノードＡを中心とする四差路を表すネットワークが示されている。着目ノードＡと、着目ノードＡに接続するリンクと着目ノードＡとは異なる端部で接続しているノード（図９では、ノードＢ、Ｃ、Ｄ、Ｅの４つ）とを要素とした接続行列によって、リンクは表現できる。この接続行列において、例えば、ノードＡとノードＢ間のリンクがノードＡからノードＢへの有向リンクの場合は、行列（Ａ、Ｂ）の位置に値を持ち、行列（Ｂ、Ａ）の位置には値を持たない（０）。一方、ノードＡとノードＢ間の無向リンクである場合は、行列（Ａ、Ｂ）の位置と、行列（Ｂ、Ａ）の位置との両方に値を持つ。値を持つ場合、その値は、そのノード間に存在するリンクの本数である。ここで、図９（ｂ）着目ノードＡに接続するリンクについて、進入リンクと脱出リンクの組み合わせを決定するということは、進入元となるノードを行成分に、脱出先となるノードを列成分として接続行列において、行と列のいずれを見ても、要素の合計値が１にしかならないようにすることに等しい。これを無向リンクとして処理した場合、全てのリンクが進入リンクと脱出リンクの両方の候補となるため、組み合わせの数は、着目ノードに接続するリンクの数をｎとすると、ｎ×（ｎ−１）通りとなる（図１０）。
【００３６】
この組み合わせ問題に類似した有名な問題に「ｎクイーン問題」が知られている。ｎクイーン問題は、チェスのクイーンの可動範囲（縦・横・斜め方向に無限大）に、他のクイーンが配置されないようにｎ×ｎのチェス盤上にｎ個のクイーンを配置しようという問題である。本実施例における進入リンクと脱出リンクの組み合わせを決定する問題は、ｎクイーン問題において、クイーンの可動範囲から斜め方向を除いて、クイーンの可動範囲を縦・横方向に無限大とした問題と等しい。ｎクイーン問題は、ｎの数が８個を超えると計算量が膨大になることが知られている。本実施例において進入リンクと脱出リンクの組み合わせを決定する問題もまた、着目ノードに接続するリンクの数が８を超えると、現実的な計算量で組み合わせを決定することは困難になる。
【００３７】
図１１は、本実施例において脱出リンクと進入リンクとの一対一の組み合わせを決定する場合の計算について説明する図である。本実施例では、処理対象ノード（着目ノード）に接続するリンクを予め有向化しているので、考えなくてはならない組み合わせの数を大幅に減らすことができる。具体的には、上述したｎの数を半減した組み合わせの数を考えれば足りる。例えば、図１１に示すように、着目ノードに接続するリンクの数が４であるときは、無向リンクで考えなければならない組み合わせの数ｎ（ｎ―１）の式において、ｎ＝４／２＝２とした数、すなわち、２通りを考えるだけでよい。このように、着目ノードに接続するリンクを有向化した場合、ｎが８になるということは、着目ノードに接続するリンクの数が１６になるということになる。現実世界の交差点を考えた場合、後述するように、脱出リンクと進入リンクの数を一致させるためにリンクを追加しても、着目ノードに接続するリンクの数は１６未満になると考えられる。
【００３８】
図１２および図１３は、進入リンクと脱出リンクとの一対一の組み合わせの決定について説明する図である。進入リンクと脱出リンクの組み合わせは、交通規制に従うように決定される。例えば、図１２に示すように、ノードＤ側から着目ノードＡを直進してノードＢへ通過することが禁止されている場合には、図１２において右側に示すように、ノードＥと着目ノードＡへの進入リンクと着目ノードＡからノードＢへの脱出リンクとを組み合わせると共に、ノードＤから着目ノードＡへの進入リンクと、着目ノードＡからノードＣへの脱出リンクとを組み合わせる。
【００３９】
交通規制に違反しない場合には、通過コストが低くなるように、進入リンクと脱出リンクの組み合わせを決定する。通過コストは、通常、直進＜左折＜右折＜Ｕターンと設定されることが多く、これに従うと、組み合わせとして優先される順番は、１．直進、２．左折、３．右折、４．Ｕターンとなる。例えば、図１３（ａ）に示すように、着目ノードＡに交通規制がない場合、進入リンクと脱出リンクの組み合わせのパターンは、図１２（ｂ）に示すパターンと、図１２（ｃ）に示すパターンの２とおりとなるが、この場合、着目ノードＡを直進する組み合わせである図１２（ｂ）に示すパターンに決定される。
【００４０】
以上説明した組み合わせの決定ルールを適用しても組み合わせが一義的に定まらない処理対象ノードＮＤＳについては、特に理由なく一つの組み合わせに決定される。また、全ての進入脱出リンクを用いる組み合わせが一つも求まらなかった場合は、進入と脱出のリンク数が等しい場合においても、ステップ３０を複数回行うことにより、最低一つの組み合わせを決定する。道路の規制や、リンクの構成上、どうしても組み合わせが求まらない場合は、そこで案内経路を切るようにしてもよい。
【００４１】
次に、ＣＰＵ２０１は、接続される進入リンクと脱出リンクの数が等しくない処理対象ノードＮＤＳについて、接続される進入リンクと脱出リンクの数が等しくなるように、通過対象リンクを追加する（ステップＳ３０）。図１４および図１５は、通過対象リンクを追加する処理について説明する図である。図１４および図１５において、一点破線で示す矢印が既に決まっている通過対象リンクＬＫＳを表す。図１４において、ノードＡは、接続される進入リンク（ノードＣからのリンクとノードＤからのリンク）の数より脱出リンク（ノードＤへのリンク）の数が少ない脱出不足ノードである。脱出不足ノードは、接続される進入リンクの数と脱出リンクの数を等しくするために、脱出リンクを追加する必要がある。一方、ノードＥは、接続される脱出リンク（ノードＦへのリンクとノードＧへのリンク）の数より進入リンク（ノードＨからのリンク）の数が少ない進入不足ノードである。進入不足ノードは、接続される進入リンクの数と脱出リンクの数を等しくするために、進入リンクを追加する必要がある。ここで、ＣＰＵ２０１は、処理対象ノードＮＤＳのうち、脱出不足ノードを出発地ノード候補とし、進入不足ノードを目的地ノード候補として、経路探索を実行する。その結果、接続経路が求められると、ＣＰＵ２０１は、求められた接続経路で出発地ノード候補と、目的地ノード候補との両方で、進入リンクと脱出リンクの組が確定するか否かを判断する。図１４に示す例では、ノードＡからノードＩとノードＪを介してノードＥに至る接続経路が探索されている。出発地ノード候補であるノードＡにおいては、新たに求められた経路の一部であるノードＡからノードＩへの脱出リンクが追加されることによって、進入リンクと脱出リンクの組み合わせを確定できる。しかしながら、図１４に示す例では、目的地ノード候補であるノードＥにおいて、新たに求められた経路の一部であるノードＪからノードＥへの進入リンクが追加されても、交通規制により、進入リンクと脱出リンクの組を確定できない。この場合、追加すべき通過対象経路は確定しない。
【００４２】
一方、図１５に示す例では、ノードＡが、進入不足ノードであり、ノードＦが脱出不足ノードである。この場合、ＣＰＵ２０１は、ノードＦを出発地ノード候補とし、ノードＡを目的地ノード候補として、経路探索を実行する。図１５に示す例では、ノードＦからノードＪとノードＤを介してノードＥに至る接続経路が探索されている。そして、図１５に示す例では、出発地ノード候補であるノードＦにおいて、新たに求められた経路の一部であるノードＦからノードＪへの脱出リンクが追加されることによって、進入リンクと脱出リンクの組み合わせを確定できる。しかも、図１５に示す例では、目的地ノード候補であるノードＡにおいて、新たに求められた経路の一部であるノードＤからノードＡへの進入リンクが追加されることによって、進入リンクと脱出リンクの組を確定できる。この場合、求められた接続経路を構成するリンクが追加すべき通過対象リンクＬＫＳとして確定する。なお、探索される接続経路は、既に通過対象リンクＬＫＳとされているリンクであっても、通過対象リンクＬＫＳではないリンクであっても良い。接続経路を構成するリンクが通過対象リンクＬＫＳとして追加される際、既に通過対象リンクＬＫＳとなっているリンクについては、仮想的なリンクが複製されて新たな通過対象リンクＬＫＳとして追加される。複製された通過対象リンクＬＫＳが存在するリンクに対応する道は、案内経路において複数回通過することになる。接続経路を構成するリンクが通過対象リンクＬＫＳとして追加される際、通過対象リンクＬＫＳではないリンクについては、当該リンクが通過対象リンクＬＫＳとして追加される。
【００４３】
このように、通過対象リンクを追加すると、ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されたか否かを判断する（ステップＳ４０）。
【００４４】
ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されていないと判断すると（ステップＳ４０：ＮＯ）、ステップＳ３０に戻って、通過対象リンクを追加しながら進入リンクと脱出リンクの組み合わせを決定していく上述の処理を繰り返す。
【００４５】
一方、ＣＰＵ２０１は、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせが決定されていると判断すると（ステップＳ４０：ＹＥＳ）、各処理対象ノードＮＤＳについて決定された進入リンクと脱出リンクの組み合わせに従って、一筆書き経路を決定する（ステップＳ５０）。図１６は、一筆書き経路の決定について説明する図である。図１６の上図では、全てのノードについて進入リンクと脱出リンクの組み合わせが決定されていることが示されている。この組み合わせに従って、全てのリンクを一度は通るように一筆書き経路を描いていくと、図１６の下図のように、実線の太線で示す第１の一筆書き経路と、破線の太線で示す第２の一筆書き経路が作成されることが解る。このように、全てのリンクを一度は通るように一筆書き経路を描いていくと必ずしも一つの一筆書き経路になるわけではなく、複数の一筆書き経路が作成されることがある。
【００４６】
ＣＰＵ２０１は、一筆書き経路が一つであるか否かを判断する（ステップＳ６０）。この結果、一筆書き経路が一つであると判断すると（ステップＳ６０：ＹＥＳ）、当該一筆書き経路を最終的な案内経路として、案内経路作成処理を終了する。
【００４７】
一方、ＣＰＵ２０１は、一筆書き経路が一つでない（複数ある）と判断すると（ステップＳ６０：ＮＯ）、一筆書き経路を減らすように、進入リンクと脱出リンクの組み合わせを変更可能な処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを変更する（ステップＳ７０）。
【００４８】
図１７は、進入リンクと脱出リンクの組み合わせの変更について説明する図である。図１７の例では、ノードＡについて、進入リンクと脱出リンクの組み合わせを変更している。すなわち、変更前のノードＡにおいては、ノードＥからノードＡへの進入リンクとノードＡからノードＣへの脱出リンクの組み合わせと、ノードＢからノードＡへの進入リンクとノードＡからノードＤへの脱出リンクの組み合わせであったところ（図１７：上図）、変更後のノードＡにおいては、ノードＥからノードＡへの進入リンクとノードＡからノードＤへの脱出リンクの組み合わせと、ノードＢからノードＡへの進入リンクとノードＡからノードＣへの脱出リンクの組み合わせとしている（図１７：下図）。この結果、２つあった一筆書き経路が一つになることが解る。ここで、ＣＰＵ２０１は、交通規制により進入リンクと脱出リンクの組み合わせのパターンが一つだけのノードに関しては、このような組み合わせの変更は行わない。ＣＰＵ２０１は、進入リンクと脱出リンクの組み合わせのパターンが複数あるノードを探索して、進入リンクと脱出リンクの組み合わせのパターンが複数あるノード関して、このような組み合わせの変更を行う。なお、進入リンクと脱出リンクの組み合わせのパターンが３つ以上存在し、組み合わせの変更が複数種類可能である場合には、ＣＰＵ２０１は、通過コストが低い方の組み合わせに変更する。この結果、最終的に作成される案内経路は、効率良く通過対象リンクに対応する道路を通過できる経路を案内するものとなる。
【００４９】
進入リンクと脱出リンクの組み合わせの変更を行うと、再び、一筆書き経路が一つであるか否かを判断する（ステップＳ６０）。この結果、一筆書き経路が一つであると判断すると（ステップＳ６０：ＹＥＳ）、当該一筆書き経路を最終的な案内経路として、案内経路作成処理を終了する。一方、ＣＰＵ２０１は、一筆書き経路が一つでない（複数ある）と判断するとステップＳ７０に戻って、再び、別の処理対象ノードＮＤＳに関して、進入リンクと脱出リンクの組み合わせの変更を行う処理を繰り返す。
【００５０】
ここで、オイラーグラフについて説明しておく。全てのリンクが有向リンクである場合、全てのノードにおいて、接続されている進入リンクの数と脱出リンクの数とが等しい場合、必ず一つのノードから同じノードに戻り全てのリンクを一度だけ通過する一つの一筆書き経路（オイラー閉路）が作成可能であることが知られている。本実施例では、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを決定している（例えば、図１６）ので、全ての処理対象ノードＮＤＳについて、当該ノードに接続されている進入リンクの数と脱出リンクの数とが等しいことが保証されている。したがって、ステップＳ７０における進入リンクと脱出リンクの組み合わせの変更を繰り返せば、一つの一筆書き経路を最終的な案内経路として作成することが可能である。
【００５１】
以上説明した上記実施例によれば、全ての通過対象リンクＬＫＳについて、通過するルートを通る案内経路を作成する計算時間を短縮できる。具体的には、全ての処理対象ノードＮＤＳについて、進入リンクと脱出リンクの組み合わせを決定してから一筆書きの案内ルートを作成するので、最終的には確実に一つの一筆書きの案内ルート（オイラー閉路）を作成することができる。さらには、全ての通過対象ルートを有向化してから進入リンクと脱出リンクの組み合わせを決定するので、計算時間を劇的に短縮できる。また、進入リンクと脱出リンクの組み合わせの決定、通過対象ルートの通過方向の決定（有向化）、複数の一筆書き経路を一つにするための進入リンクと脱出リンクの組み合わせの変更の際に、通過コストを考慮して通過コストが低くなるように決定または変更を行うので、生成される案内経路のトータルの通過コストを低減することができる。
【００５２】
Ｂ．変形例
・第１変形例：
上記実施例では、ステップＳ１０（図４）において、上述した有向化のルールを適用しても有向化できなかった通過対象リンクＬＫＳについては、特に理由なく一の方向に有向化しているが、これに代えて、有向化できなかった通過対象リンクＬＫＳについては、ステップＳ３０およびステップＳ４０（図４）を行った後に、改めて上述のルールを適用して有向化しても良い。その例を、第１変形例として図１８を参照して説明する。図１８は、第１変形例における案内経路作成処理の処理ステップを示すフローチャートである。本変形例では、ＣＰＵ２０１は、まず、通過対象リンクを、交通規制・２差路接続・進入リンクと脱出リンクの差・通過コスト等により、可能な限り有向化する（ステップＳ１１０）。次に、ＣＰＵ２０１は、接続する全てのリンクが有向化されており、かつ、侵入と脱出の数が等しいノードについて、進入と脱出の組を決定する（ステップＳ１２０）。続いて、ＣＰＵ２０１は、接続する全て有向化リンクについて、進入と脱出の数が等しくないノードについて、差が小さくなるような経路を求める（ステップＳ１３０）。ＣＰＵ２０１は、求まった経路に該当する、有向化されていないリンクがあれば、経路と同じ方向に有向化し、なければ新規にリンクを追加する（ステップＳ１４０）。この後、ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されたかを判定する（ステップＳ１５０）。ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されている場合には（ステップＳ１５０：ＹＥＳ）、ステップＳ１６０の処理に進む。ＣＰＵ２０１は、全てのノードで進入と脱出の組が決定されていない場合には（ステップＳ１５０：ＮＯ）、上述したステップＳ１１０に戻って、ステップＳ１１０〜Ｓ１４０までの処理を繰り返す。ステップＳ１６０では、実施例におけるステップＳ５０（図４）と同様に一筆書き経路を決定する（ステップＳ１６０）。次に、ＣＰＵ２０１は、実施例におけるステップＳ６０と同様に、一筆書き経路が一つであるか判定する（ステップＳ１７０）。ＣＰＵ２０１は、一筆書き経路が一つである場合には（ステップＳ１７０：ＹＥＳ）、判定する処理を終了する。ＣＰＵ２０１は、一筆書き経路が複数ある場合には（ステップＳ１７０：ＮＯ）、実施例におけるステップＳ７０（図４）と同様に、一筆書き経路を減らすように進入脱出の組を変更し（ステップＳ１８０）、一筆書き経路が一つになるまでステップＳ１７０およびステップＳ１８０の処理を繰り返す。以上説明した第１変形例においても、実施例と同様に、最終的に通過対象リンクを全て通過する案内経路を短い計算時間で作成することができる。
【００５３】
・第２変形例：
上記実施例では、全ての処理対象ノードＮＤＳについて、脱出リンクの数と進入リンクの数を等しくしているが、処理対象リンクに対して案内経路が複数回通過している箇所について、その重複経路部分を削除することにより、処理対象ノードＮＤＳのうちの一つについては脱出リンクを一本少なくすると共に、他の一つについて進入リンクを一本少なくしても良い。こうすれば、脱出リンクが一本多いノードから進入リンクが一本多いノードに至る一本の一筆書きの案内経路（オイラー経路）を作成することができる。
【００５４】
・第３変形例：
上記実施例において、案内経路作成処理の全ての処理をソフトウェアによって実現しているが、案内経路作成処理の一部または全部の処理をハードウェアによって実現しても良い。
【００５５】
以上、本発明の実施例および変形例について説明したが、本発明はこれらの実施例および変形例になんら限定されるものではなく、その要旨を逸脱しない範囲内において種々の態様での実施が可能である。
【符号の説明】
【００５６】
２００…案内経路作成装置
２０１…ＣＰＵ
２０２…入出力部
２０３…内部記憶装置
２０４…外部記憶装置
Ｄ１１…地図データ
Ｍ１１…通過対象リンク認識部
Ｍ１２…処理対象ノード認識部
Ｍ１３…リンク有向化処理部
Ｍ１４…進入脱出決定部
Ｍ１５…経路案内作成部
【特許請求の範囲】
【請求項１】
案内経路作成装置であって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、
前記処理対象ノードのうちの１つのノードである着目ノードについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する進入脱出決定処理を、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、
を備える、案内経路作成装置。
【請求項２】
請求項１に記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードに接続されている複数の前記通過対象リンクの数が奇数の場合には、当該複数の前記通過対象リンクのうちの一つを複製して仮想的な前記通過対象リンクとして追加することにより、あるいは、通過対象外である前記リンクのうち通行可能なものを前記通過対象リンクとして追加することにより、前記着目ノードについて、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
【請求項３】
請求項１または請求項２に記載の案内経路作成装置は、さらに、
通過対象リンクの全てについて、所定の条件に従って通過方向を定める有向化処理部を備え、
前記進入脱出決定部は、定められた通過対象リンクの通過方向に従って、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
【請求項４】
請求項３に記載の案内経路作成装置であって、
前記所定の条件は、交通規制を遵守することを含む、案内経路生成装置。
【請求項５】
請求項３または請求項４に記載の案内経路作成装置であって、
前記有向化処理部における所定の条件は、前記着目ノードの前記進入リンクの数と前記脱出リンクの数の差を小さくすることを含む、案内経路生成装置。
【請求項６】
請求項３ないし請求項５のいずれかに記載の案内経路作成装置であって、
前記所定の条件は、前記着目ノードを通過する際の通過コストを小さくすることを含む、案内経路生成装置。
【請求項７】
請求項１ないし請求項６のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードを通過する際の通過コストを小さくするように、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
【請求項８】
請求項１ないし請求項７のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、
前記処理対象ノードのうち、前記脱出リンクの数が前記進入リンクの数より少ない脱出不足ノードを出発地ノードとし、前記処理対象ノードのうち、前記進入リンクの数が前記脱出リンクの数より少ない進入不足ノードを目的地ノードとする追加経路を探索し、
前記追加経路に対応するリンクを前記通過対象リンクに追加することにより、各処理対象ノードについて、前記進入リンクの数と前記脱出リンクの数を等しくし、
前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
【請求項９】
請求項１ないし請求項７のいずれかに記載の案内経路作成装置であって、
前記案内経路作成部は、前記進入リンクと前記脱出リンクの組み合わせに従って一筆書き経路を作成し、
一筆書き経路が複数作成された場合には、前記進入リンクと前記脱出リンクの組み合わせのパターンが複数個許容される前記処理対象ノードについて、前記進入リンクと前記脱出リンクの組み合わせのパターンを変更することにより、複数の一筆書き経路を繋いで、最終的に一つの一筆書き経路からなる前記案内経路を作成する、案内経路作成装置。
【請求項１０】
請求項９に記載の案内経路作成装置であって、
前記進入リンクと前記脱出リンクの組み合わせのパターンが３以上許容される場合には、通過コストの低下が最も少ないパターンに変更する、案内経路作成装置。
【請求項１１】
コンピュータを用いて、案内経路を作成する案内経路作成方法であって、
前記コンピュータは、複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部を備え、
前記案内経路作成方法は、
（ａ）前記コンピュータの演算手段が、前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する工程と、
（ｂ）前記コンピュータの演算手段が、前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する工程と、
（ｃ）前記コンピュータの演算手段が、前記処理対象ノードのうちの１つのノードである着目ノードに接続する少なくとも前記通過対象リンクを含む前記リンクについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定することを、全ての前記処理対象ノードを前記着目ノードとして実行する工程と、
（ｄ）決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する工程と、
を備える、案内経路作成方法。
【請求項１２】
コンピュータに案内経路を作成させるためのコンピュータプログラムであって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを取得するするネットワークデータ取得機能と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識機能と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識機能と、
前記処理対象ノードのうちの１つのノードである着目ノードに接続する少なくとも前記通過対象リンクを含む前記リンクについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定することを、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定機能と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成機能と、
を前記コンピュータに実現させる、コンピュータプログラム。
【請求項１】
案内経路作成装置であって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識部と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識部と、
前記処理対象ノードのうちの１つのノードである着目ノードについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定する進入脱出決定処理を、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定部と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成部と、
を備える、案内経路作成装置。
【請求項２】
請求項１に記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードに接続されている複数の前記通過対象リンクの数が奇数の場合には、当該複数の前記通過対象リンクのうちの一つを複製して仮想的な前記通過対象リンクとして追加することにより、あるいは、通過対象外である前記リンクのうち通行可能なものを前記通過対象リンクとして追加することにより、前記着目ノードについて、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
【請求項３】
請求項１または請求項２に記載の案内経路作成装置は、さらに、
通過対象リンクの全てについて、所定の条件に従って通過方向を定める有向化処理部を備え、
前記進入脱出決定部は、定められた通過対象リンクの通過方向に従って、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
【請求項４】
請求項３に記載の案内経路作成装置であって、
前記所定の条件は、交通規制を遵守することを含む、案内経路生成装置。
【請求項５】
請求項３または請求項４に記載の案内経路作成装置であって、
前記有向化処理部における所定の条件は、前記着目ノードの前記進入リンクの数と前記脱出リンクの数の差を小さくすることを含む、案内経路生成装置。
【請求項６】
請求項３ないし請求項５のいずれかに記載の案内経路作成装置であって、
前記所定の条件は、前記着目ノードを通過する際の通過コストを小さくすることを含む、案内経路生成装置。
【請求項７】
請求項１ないし請求項６のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、前記着目ノードを通過する際の通過コストを小さくするように、前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路生成装置。
【請求項８】
請求項１ないし請求項７のいずれかに記載の案内経路作成装置であって、
前記進入脱出決定部は、
前記処理対象ノードのうち、前記脱出リンクの数が前記進入リンクの数より少ない脱出不足ノードを出発地ノードとし、前記処理対象ノードのうち、前記進入リンクの数が前記脱出リンクの数より少ない進入不足ノードを目的地ノードとする追加経路を探索し、
前記追加経路に対応するリンクを前記通過対象リンクに追加することにより、各処理対象ノードについて、前記進入リンクの数と前記脱出リンクの数を等しくし、
前記進入リンクと前記脱出リンクの一対一の組み合わせを決定する、案内経路作成装置。
【請求項９】
請求項１ないし請求項７のいずれかに記載の案内経路作成装置であって、
前記案内経路作成部は、前記進入リンクと前記脱出リンクの組み合わせに従って一筆書き経路を作成し、
一筆書き経路が複数作成された場合には、前記進入リンクと前記脱出リンクの組み合わせのパターンが複数個許容される前記処理対象ノードについて、前記進入リンクと前記脱出リンクの組み合わせのパターンを変更することにより、複数の一筆書き経路を繋いで、最終的に一つの一筆書き経路からなる前記案内経路を作成する、案内経路作成装置。
【請求項１０】
請求項９に記載の案内経路作成装置であって、
前記進入リンクと前記脱出リンクの組み合わせのパターンが３以上許容される場合には、通過コストの低下が最も少ないパターンに変更する、案内経路作成装置。
【請求項１１】
コンピュータを用いて、案内経路を作成する案内経路作成方法であって、
前記コンピュータは、複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを記憶するネットワーク記憶部を備え、
前記案内経路作成方法は、
（ａ）前記コンピュータの演算手段が、前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する工程と、
（ｂ）前記コンピュータの演算手段が、前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する工程と、
（ｃ）前記コンピュータの演算手段が、前記処理対象ノードのうちの１つのノードである着目ノードに接続する少なくとも前記通過対象リンクを含む前記リンクについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定することを、全ての前記処理対象ノードを前記着目ノードとして実行する工程と、
（ｄ）決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する工程と、
を備える、案内経路作成方法。
【請求項１２】
コンピュータに案内経路を作成させるためのコンピュータプログラムであって、
複数のノードと前記ノード間を接続するリンクを含む道路ネットワークデータを取得するするネットワークデータ取得機能と、
前記道路ネットワークに含まれる前記リンクのうち、通過すべき道に対応するリンクを通過対象リンクとして認識する通過対象リンク認識機能と、
前記道路ネットワークに含まれる前記ノードのうち、複数の前記通過対象リンクに接続している全てのノードを処理対象ノードとして認識する処理対象ノード認識機能と、
前記処理対象ノードのうちの１つのノードである着目ノードに接続する少なくとも前記通過対象リンクを含む前記リンクについて、前記着目ノードに進入する進入リンクと前記着目ノードから脱出する脱出リンクの一対一の組み合わせを決定することを、全ての前記処理対象ノードを前記着目ノードとして実行する進入脱出決定機能と、
決定された前記進入リンクと前記脱出リンクの組み合わせに基づいて、前記通過対象リンクを全て通過する案内経路を作成する案内経路作成機能と、
を前記コンピュータに実現させる、コンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１０−２３０３６５（Ｐ２０１０−２３０３６５Ａ）
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願番号】特願２００９−７６０３２（Ｐ２００９−７６０３２）
【出願日】平成２１年３月２６日（２００９．３．２６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願日】平成２１年３月２６日（２００９．３．２６）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]