JP4339714B2

JP4339714B2 - 経路算出装置、経路算出方法、及びプログラム

Info

Publication number: JP4339714B2
Application number: JP2004035786A
Authority: JP
Inventors: 達也本丸; 重昭中田
Original assignee: ジクー・データシステムズ株式会社
Priority date: 2004-02-12
Filing date: 2004-02-12
Publication date: 2009-10-07
Anticipated expiration: 2024-02-12
Also published as: JP2005228011A

Description

本発明は、経路算出装置、経路算出方法、及びプログラムに関する。特に本発明は、最も移動コストが小さくなる出入口の経路を求める経路算出装置に関する。

従来、経路算出装置においては、例えばダイクストラ法を用いて経路計算を行う手法が知られているが、経路計算の対象となる領域が広い場合には、経路計算に長い時間がかかるという課題がある。係る課題を解決するために、地図を一定の大きさのメッシュに分割し、任意の２つのメッシュを結ぶメッシュの組み合わせを予め登録することにより経路計算の対象となる領域を狭く取り、これにより計算時間を短縮する構成が開示されている（例えば、特許文献１参照）。
特開平６−３２３８６１号公報

しかしながら上記の構成を用いて経路計算を行った場合においても、予め登録されたメッシュを通過する経路は多数あるので、これらの経路のいずれが最も移動時間が短いかをダイクストラ法によって求める必要がある。この為、計算の対象となる領域が広い場合には、経路計算に長い時間がかかるという課題がある。

そこで本発明は、上記の課題を解決することのできる経路算出装置、経路算出方法、及びプログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。

上記課題を解決するために、本発明の第１の形態において経路算出装置は、地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、複数のメッシュのそれぞれへの道路の出入口および当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部と、複数のメッシュに含まれるいずれか２つのメッシュの、各々１つの出入口が指定された場合に、２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択手段と、選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択手段と、選択された出入口間の移動コストをメッシュ内移動コスト記憶部から読み出すことにより、選択された出入口の中で、各々１つの出入口を結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出手段とを備える。これにより、選択された２つのメッシュ間の移動コストを、ダイクストラ法を用いて計算する場合に比べより高速に、経路を算出することができる。

上記の経路算出装置は、一のメッシュ内部の始点、および他のメッシュ内部の終点が指定された場合に、始点および終点が含まれるメッシュに隣接するメッシュへの選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出手段を更に備え、端部出入口間の移動コストを経路算出手段によって求め、端部移動コストを加算することにより、始点から終点までの移動コストを算出してもよい。これにより、始点及び終点がいずれの位置であっても適切に、経路を求めることができる。

上記の経路算出装置は、メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、当該細メッシュへの道路の出入口、および当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部と、を備え、端部移動コスト算出手段は、始点および終点から始点および終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、メッシュ選択手段、出入口選択手段、および経路算出手段はそれぞれ、各々１つの細メッシュの出入口から当該細メッシュの各々１つの出入口近傍のメッシュの出入口の、細メッシュの組み合わせ、細メッシュへの出入口、および細メッシュの各々１つの出入口から、近傍のメッシュの出入口までの経路を算出する手段を有し、端部移動コスト算出手段は、ダイクストラ法によって算出された移動コストに、細メッシュの各々１つの出入口から近傍のメッシュの出入口までの移動コストを加えることにより、端部移動コストを算出してよい。これにより、始点及び終点から、始点及び終点が含まれる各メッシュの端部出入口までの経路を全てダイクストラ法を用いて求めた場合に比べ、より高速に経路を求めることができる。

上記の経路算出装置において、交通量がより大きい都市部におけるメッシュの大きさは、他の地域におけるメッシュの大きさよりも小さくてもよい。又、上記の経路算出装置において、道路の密度が高い都市部におけるメッシュの大きさは、他の地域におけるメッシュの大きさよりも小さくてもよい。

メッシュの大きさが一定である場合、交通量が多い都市部や道路密度が高い都市部におけるメッシュの出入口の個数は、他の地域におけるメッシュの出入口の個数よりも相対的に多くなる。しかしながら、始点及び終点から端部出入口までの部移動コストを求める場合、移動コストの算出時間を短縮する為には、出入口の数が少ないことが望ましい。本発明における経路算出装置においては、交通量や道路の密度が大きい地域のメッシュを、他の地域のメッシュよりも小さくすることにより、メッシュへの出入口の個数を相対的に少なくするので、高速に経路を求めることができる。また小さいメッシュには、より細かい道路の出入口を対応づけてもよく、これにより経路検索の精度を上げることができる。

本発明の第２の形態においては、地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、複数のメッシュのそれぞれへの道路の出入口および当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部とを備える経路算出装置を制御することにより経路を算出する経路算出方法であって、複数のメッシュに含まれるいずれか２つのメッシュの、各々１つの出入口が指定された場合に、２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択ステップと、選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択ステップと、選択された出入口間の移動コストをメッシュ内移動コスト記憶部から読み出すことにより、選択された出入口の中で、各々１つの出入口を結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出ステップとを備える。これにより第１の実施形態と同様の効果を得ることができる。

上記の経路算出方法は、一のメッシュ内部の始点、および他のメッシュ内部の終点が指定された場合に、始点および終点が含まれるメッシュに隣接するメッシュへの選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出ステップを更に備え、端部出入口間の移動コストを経路算出ステップによって求め、端部移動コストを加算することにより、始点から終点までの移動コストを算出してもよい。これにより第１の実施形態と同様の効果を得ることができる。

上記の経路算出装置は、メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、当該細メッシュへの道路の出入口、および当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部とを更に備えており、端部移動コスト算出ステップは、始点および終点から始点および終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、メッシュ選択ステップ、出入口選択ステップ、および経路算出ステップはそれぞれ、各々１つの細メッシュの出入口から当該細メッシュの各々１つの出入口近傍のメッシュの出入口の、細メッシュの組み合わせ、細メッシュへの出入口、および細メッシュの各々１つの出入口から、近傍のメッシュの出入口までの経路を算出するステップを有し、端部移動コスト算出ステップは、ダイクストラ法によって算出された移動コストに、細メッシュの各々１つの出入口から近傍のメッシュの出入口までの移動コストを加えることにより端部移動コストを算出してもよい。これにより第１の実施形態と同様の効果を得ることができる。

本発明の第３の形態においては、地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、複数のメッシュのそれぞれへの道路の出入口および当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部とを備える経路算出装置を機能させるプログラムであって、複数のメッシュに含まれるいずれか２つのメッシュの、各々１つの出入口が指定された場合に、２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択手段と、選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択手段と、選択された出入口間の移動コストをメッシュ内移動コスト記憶部から読み出すことにより、選択された出入口の中で、各々１つの出入口を結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出手段とを備える。これにより第１の実施形態と同様の効果を得ることができる。

上記のプログラムは、一のメッシュ内部の始点、および他のメッシュ内部の終点が指定された場合に、始点および終点が含まれるメッシュに隣接するメッシュへの選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出手段を更に備え、端部出入口間の移動コストを経路算出手段によって求め、端部移動コストを加算することにより、始点から終点までの移動コストを算出してもよい。これにより第１の実施形態と同様の効果を得ることができる。

上記の経路算出装置は、メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、当該細メッシュへの道路の出入口、および当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部とを更に備えており、端部移動コスト算出手段は、始点および終点から始点および終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、メッシュ選択手段、出入口選択手段、および経路算出手段はそれぞれ、各々１つの細メッシュの出入口から当該細メッシュの各々１つの出入口近傍のメッシュの出入口の、細メッシュの組み合わせ、細メッシュへの出入口、および細メッシュの各々１つの出入口から、近傍のメッシュの出入口までの経路を算出する手段を有し、端部移動コスト算出手段は、ダイクストラ法によって算出された移動コストに、細メッシュの各々１つの出入口から近傍のメッシュの出入口までの移動コストを加えることにより、端部移動コストを算出してもよい。これにより第１の実施形態と同様の効果を得ることができる。

なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。

以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１は、本発明の実施形態に係る経路算出装置１００の構成の一例を示す。本例における経路算出装置１００は、例えばカーナビケーション装置であり、経路算出装置１００のユーザーにより設定された始点及び終点間の経路を高速に求めることを目的とする。経路算出装置１００は、メッシュ記憶部１０、メッシュ選択手段３０、メッシュ内移動コスト記憶部４０、出入口選択手段５０、端部移動コスト算出手段６０、経路算出手段７０、及び記録媒体１１０を備える。

メッシュ記憶部１０は、地図上の各領域を、複数のメッシュのいずれかに対応付けて格納する。本例におけるメッシュ記憶部１０は、地図上の各領域を、対応するメッシュのメッシュ番号に対応づけて格納する。またメッシュ記憶部１０は、地図上の各領域における絶対位置を示す情報をメッシュ番号に対応づけて格納する。

メッシュ内移動コスト記憶部４０は、複数のメッシュのそれぞれへの道路の出入口、及びこれらの出入口間の移動に要する移動コストを、それぞれのメッシュのメッシュ番号に対応付けて格納する。本例におけるメッシュ内移動コスト記憶部４０は、出入口間を示す出入口番号の組に、移動コストを対応づけて格納する。本例における移動コストとは、出入口間の移動に要する最小の時間であり、予め計算されてメッシュ内移動コスト記憶部４０に格納される。この場合、移動コストは、例えばダイクストラ法等の手法を用いて予め計算されてよい。尚、他の例において、移動コストとは、出入口間の距離、料金、曲がり角の数、信号数、及び道路幅、又はメッシュに対応する領域の天候を示す指標等であってよい。

メッシュ選択手段３０は、経路算出装置１００のユーザーから、地図上の各領域における始点及び終点の位置を示す情報を受け取ると、メッシュ記憶部１０を参照して、始点及び終点が含まれるメッシュを特定する。一のメッシュ内部の始点、および他のメッシュ内部の終点が指定された場合に、メッシュ選択手段３０は、始点が含まれるメッシュと、終点が含まれるメッシュとを結ぶメッシュの組み合わせを選択する。本例におけるメッシュ選択手段３０は、例えば、始点と終点を異なる焦点とする、予め形状の定められた楕円領域を生成し、この楕円領域の範囲内において、メッシュの組み合わせを選択する。メッシュ選択手段３０は、選択したメッシュの組み合わせを示すメッシュ番号を出入口選択手段５０へ通知する。

メッシュ選択手段３０よりメッシュ番号を受け取ると、出入口選択手段５０は、始点および終点が含まれる２つのメッシュに隣接するメッシュへの出入口である端部出入口を選択する。また出入口選択手段５０は、メッシュ内移動コスト記憶部４０を参照し、選択されたメッシュ中の隣接したメッシュ間の出入口を選択する。ここで、本例における出入口選択手段５０は、メッシュ選択手段３０が生成した楕円領域内における出入口を全て選択する。出入口選択手段５０は、選択した出入口の出入口番号を、端部移動コスト算出手段６０及び経路算出手段７０へ通知する。

端部移動コスト算出手段６０は、始点および終点からそれぞれの端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する。

経路算出手段７０は、出入口選択手段５０より出入口番号を受け取ると、出入口の組に対応する移動コストのそれぞれをメッシュ内移動コスト記憶部４０から読み出し、読み出した出入口の組に対応する移動コストのそれぞれを加算することにより、端部出入口間の移動コストを算出する。そして経路算出手段７０は、端部出入口間移動コストに、端部移動コストを加算することにより、始点から終点を結ぶ経路の移動コストを算出する。ここで経路算出手段７０は、各々１つの端部出入口間を結ぶ、選択された出入口により中継された経路の移動コストを算出する。この場合、経路算出手段７０は、始点側の端部出入口、及び終点側の端部出入口の全ての組み合わせについて、この端部出入口どうしを結ぶ全ての経路の移動コストを算出する。そして経路算出手段７０は、始点から終点を結ぶ経路の移動コストが最小となる経路を選択して、選択した経路をユーザーへ通知する。本例における経路算出手段７０は、移動コストが最小となる経路を中継する出入口の組み合わせを、ユーザーへ通知する。

このように、選択されたメッシュ内において、一のメッシュから他のメッシュへの移動コストが最小となる経路を求める場合、本発明における経路算出装置１００は、出入口間の移動に要する最小のコストを予め計算して格納しておき、これらの移動コストを加算することにより、メッシュ間の経路の移動コストを算出するので、同じく選択されたメッシュ内においてダイクストラ法を用いて移動コストが最小となる経路を求める場合に比べてより高速に、移動コストが最小となる経路を求めることができる。

ここで、本例における経路算出装置１００は、更に、細メッシュ記憶部１５、細メッシュ内移動コスト記憶部４５、及びノード間移動コスト記憶部６５を備える。細メッシュ記憶部１５は、メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する。ここで細メッシュ記憶部１５は、地図上の各領域を、対応する細メッシュのメッシュ番号に対応づけて格納すると共に、各領域における絶対位置を示す情報を、細メッシュのメッシュ番号に対応づけて格納する。また細メッシュ内移動コスト記憶部４５は、細メッシュへの道路の出入口、および当該出入口間の移動コストを、当該細メッシュの細メッシュ番号に対応付けて格納する。

ノード間移動コスト記憶部６５は、細メッシュを通る道路内での移動に必要な移動コストを格納する。本例におけるノード間移動コスト記憶部６５は、道路におけるノード間の移動コストを各ノードを示すノード番号に対応づけて格納している。本例におけるノードとは、道路の交差点、道路のメッシュへの出入口、道路の行き止まり等である。

メッシュ選択手段３０、出入口選択手段５０、および経路算出手段７０はそれぞれ、各々１つの細メッシュの出入口から当該細メッシュの各々１つの出入口近傍のメッシュの出入口の、細メッシュの組み合わせ、細メッシュへの出入口、および細メッシュの各々１つの出入口から端部出入口までの経路を算出する手段を有する。即ち、メッシュ選択手段３０は、始点及び終点が含まれる細メッシュと、端部出入口を含む細メッシュとを結ぶ細メッシュの組み合わせを選択する。出入口選択手段５０は、選択された細メッシュ中の隣接した細メッシュ間の出入口を全て選択する。経路算出手段７０は、出入口番号が示す出入口の全ての組に対応する移動コストを細メッシュ内移動コスト記憶部４５から読み出し、それぞれを加算する。これにより経路算出手段７０は、始点又は終点が含まれる細メッシュの出入口から端部出入口までの移動コスト及び経路を求める。

端部移動コスト算出手段６０は、始点および終点から始点および終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する。端部移動コスト算出手段６０は、ダイクストラ法によって算出された移動コストに、細メッシュの各々１つの出入口から端部出入口までの移動コストを加えることにより、端部移動コストを算出する。ここで本例における経路算出手段７０は、端部移動コストと端部出入口間移動コストとの和が最小となるような、始点及び終点から各端部出入口までの経路、及び細メッシュの出入口から端部出入口までの経路を選択する。

このように本発明における経路算出装置１００は、端部移動コストを求める場合、始点及び終点から細メッシュの出入口までの経路はダイクストラ法を用いることにより算出し、始点及び終点が含まれる細メッシュの出入口から、各端部出入口までの移動コストは、予め計算された出入口間の移動コストを用いる。従って、始点及び終点がいずれの位置であっても適切に、経路を求めることができる。また、始点及び終点から、始点及び終点が含まれる各メッシュの端部出入口までの経路を全てダイクストラ法を用いて求めた場合に比べ、より高速に経路を求めることができる。

記録媒体１１０は、経路算出装置１００に、メッシュ選択手段３０、出入口選択手段５０、端部移動コスト算出手段６０、及び経路算出手段７０として機能させるプログラムを格納する。記録媒体１１０は、例えばＤＶＤ、ＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、磁気記録媒体、または半導体記録装置等であってよい。経路算出装置１００は、これらのプログラムを、記録媒体１１０から読み取って実行する。また、経路算出装置１００は、外部と通信を行う通信回線を更に備えてもよく、この通信回線を介してこれらのプログラムを取得してよい。

図２は、メッシュ及び細メッシュの一例を示す。図２（ａ）は、メッシュを説明する図である。図２（ｂ）は、細メッシュを説明する図である。本例におけるメッシュ記憶部１０は、地図３００上の各領域を、例えば複数の長方形状のメッシュ３０２〜３１８に対応づけて格納し、細メッシュ記憶部１５は、メッシュ３０４に含まれる各領域を、このメッシュを分割した長方形状の細メッシュ４００〜４１６に対応づけて格納する。

図２（ａ）のＸ１〜Ｘ１２によって示された各点のそれぞれ、及び、図２（ｂ）のＸ３、Ｘ４、Ｙ１〜Ｙ１４によって示された各点のぞれぞれは、メッシュ及び細メッシュにおける出入口を示しており、各出入口を結ぶ直線は、この出入口間で経路がつながっていることを示す。点線で示された領域は、メッシュ選択手段３０により生成された、始点５００及び終点５０２を焦点とする楕円領域５１０を示す。

また本例におけるメッシュ内移動コスト記憶部４０は、メッシュに対応する領域を通る大きな道路の出入口のみを格納し、細メッシュ内移動コスト記憶部４５は、細メッシュに対応する領域を通る大きな道路の出入口に加えて、この領域を通る小さな道路の出入口を更に格納する。ここで大きな道路とは、高速自動車道路、一般国道、県道、４車線以上の市町村道等の主要幹線道路であり、小さい道路とは、主要幹線道路以外の道路であってよい。この様子は、例えば図２（ａ）におけるメッシュ３０４、及び図２（ｂ）における細メッシュ４００〜４１６に示されている。例えばメッシュ３０４には、Ｘ３及びＸ４を結ぶ１つの経路しか示されていないのに対し、同じ領域に対応する細メッシュ４００〜４１６には、Ｘ３及びＸ４を結ぶ経路に加えて更に、Ｙ１〜Ｙ１４のそれぞれを出入口とする複数の経路が示されている。

図３は、メッシュ内移動コスト記憶部４０に格納されるデータ構成の一例を示す。図４は、細メッシュ内移動コスト記憶部４５に格納されるデータ構成の一例を示す。図３及び図４に示すように、メッシュ内移動コスト記憶部４０及び細メッシュ内移動コスト記憶部４５は、各メッシュにおける出入口間の全ての組み合わせについて、対応する移動コストを予め格納する。

図５は、経路算出装置１００の動作の一例を示すフローチャートである。経路算出装置１００のユーザーが、始点５００及び終点５０２を設定する（Ｓ１００）と、メッシュ選択手段３０は、始点５００が含まれるメッシュ３０４、及び終点５０２が含まれるメッシュ３１４を特定し、メッシュ３０４とメッシュ３１４を結ぶメッシュの組み合わせを選択する（Ｓ１０５）。

本例におけるメッシュ選択手段３０は、例えば始点５００及び終点５０２を焦点とする予め形状の定められた楕円領域５１０を求め、この楕円領域５１０内において、始点を含むメッシュ３０４、及び終点を含むメッシュ３１８を結ぶ全てのメッシュの組み合わせを選択する。そして、メッシュ選択手段３０は、選択したメッシュのメッシュ番号を出入口選択手段５０へ通知する。

メッシュ番号を受け取ると、出入口選択手段５０はメッシュ内移動コスト記憶部４０を参照し、選択されたメッシュ中の隣接したメッシュ間の出入口を全て選択する（Ｓ１１０）。そして出入口選択手段５０は、選択した出入口の出入口番号を、端部移動コスト算出手段６０及び経路算出手段７０へ通知する。

すると端部移動コスト算出手段６０は、端部移動コストを算出する（Ｓ１１５）。本例における端部移動コストは、始点５００からＸ３又はＸ４、終点５０２からＸ６、Ｘ１０、又はＸ１１までの移動コストである。

経路算出手段７０は、出入口選択手段５０により通知された出入口の組に対応する移動コストを、メッシュ内移動コスト記憶部４０から読み出し、読み出した移動コストのそれぞれを加算することにより、端部出入口間の移動コストを算出する（Ｓ１２０）。

例えば出入口選択手段５０は、始点が含まれるメッシュにおける端部出入口として、メッシュ３０４におけるＸ３及びＸ４を選択し、終点が含まれるメッシュにおける端部出入口として、Ｘ６及びＸ１０を選択する。ここで出入口選択手段５０は、始点側の端部出入口であるＸ３及びＸ４と、終点側の端部出入口であるＸ６及びＸ１０とを中継する出入口として、Ｘ５及びＸ８を選択する。そして経路算出手段７０は、始点側の端部出入口Ｘ３及びＸ４から、出入口Ｘ５及びＸ８を中継して、終点側の端部出入口であるＸ６及びＸ１０を結ぶ全ての経路の移動コストを算出する。本例では、経路算出手段７０は、Ｘ３からＸ４及びＸ５を経てＸ６へ至る経路、Ｘ３からＸ４及びＸ８を経てＸ１０へ至る経路、Ｘ４からＸ５を経てＸ６へ至る経路、Ｘ４からＸ８を経てＸ１０へ至る経路の移動コストを算出する。

経路算出手段７０は、端部移動コストと端部出入口間の移動コストとを加算することにより、始点から終点までの移動コストを算出する（Ｓ１２５）。そして経路算出手段７０は、選択された出入口の中で、各々１つの出入口を結ぶ、最も移動コストが小さくなる出入口の経路を求める（Ｓ１３０）。これにより経路算出手段７０は、移動コストが最小となる経路をユーザーへ通知する。

図６は、細メッシュにおける道路及びノードを説明する図である。例えばＹ６、Ｙ１１、及びＺ１〜Ｚ６で示された各点は、細メッシュ４１０に対応する領域を通る道路上におけるノードを示している。尚、本例におけるノード間移動コスト記憶部６５は、ノードの絶対位置を示す情報を格納してよい。これにより、始点及び終点を示す情報が設定された場合、本例における端部移動コスト算出手段６０は、細メッシュに含まれる始点及び終点が、どの道路上のノードの近傍であるかを特定する。

図７は、ノード間移動コスト記憶部６５に格納されるデータ構成の一例を示す。ノード間移動コスト記憶部６５は、ノード間の移動コストを、ノードを示すノード番号に対応づけて予め格納する。

図８は、図５におけるＳ１１５の詳細な動作の一例を示すフローチャートである。ユーザにより始点及び終点が設定されると、メッシュ選択手段３０は、細メッシュ記憶部１５を参照して、始点及び終点が含まれる細メッシュを特定する。例えば始点５００が設定された場合、メッシュ選択手段３０は、始点５００を含む細メッシュ４１０を特定する。更にメッシュ選択手段３０は、ノード間移動コスト記憶部６５を参照し、始点５００に近いノードであるＺ１及びＺ５を選択する。そして端部移動コスト算出手段６０は、ダイクストラ法を用いて、Ｚ１及びＺ５から、細メッシュ４１０の出入口Ｙ６及びＹ１１までの経路、及びその経路の移動コストを求める。これにより、端部移動コスト算出手段６０は、始点及び終点が含まれる細メッシュの出入口までの移動コストを算出する（Ｓ２００）。

そしてメッシュ選択手段３０は、始点及び終点を含むメッシュ内において、始点又は終点が含まれる細メッシュと、始点側又は終点側の端部出入口を含む細メッシュとを結ぶ細メッシュの組み合わせを選択する（Ｓ２０５）。本例におけるメッシュ選択手段３０は、例えば始点５００が含まれるメッシュ３０４内において、細メッシュ４１０から端部出入口Ｘ３を含む細メッシュ４０４を結ぶ細メッシュの組み合わせ、及び、細メッシュ４１０から別の端部出入口Ｘ４を含む細メッシュ４１４を結ぶ細メッシュの組み合わせを全て選択する。メッシュ選択手段３０は、選択した細メッシュのメッシュ番号を出入口選択手段５０へ通知する。ここで出入口選択手段５０は、細メッシュ番号を受け取ると、細メッシュ内移動コスト記憶部４５を参照し、選択された細メッシュ中の隣接した細メッシュ間の出入口を選択する（Ｓ２１０）。この場合、例えば始点５００において出入口選択手段５０は、Ｙ１１からＸ３またはＸ４、或いはＹ６からＸ３またはＸ４を結ぶ全ての経路における出入口を選択する。そして出入口選択手段５０は、選択した出入口の出入口番号を経路算出手段７０へ通知する。

経路算出手段７０は、出入口番号を受け取ると、出入口番号が示す出入口に対応する移動コストを細メッシュ内移動コスト記憶部４５から読み出し、読み出した移動コストを加算する。これにより経路算出手段７０は、始点又は終点が含まれる細メッシュの出入口から端部出入口までの移動コストを算出する。そして経路算出手段７０は、端部移動コストと端部出入口間移動コストとの和が最小となるような、始点及び終点から各細メッシュの出入口までの経路、各細メッシュの出入口から各端部出入口までの経路、及び各端部出入口間の経路、のそれぞれを選択する。これにより経路算出手段７０は細メッシュ間の出入口間の経路を算出する（Ｓ２１５）。例えば経路算出手段７０は、始点５００からＺ１、Ｚ４を経てＹ１１へ至る経路を、始点から細メッシュの出入口までの経路として選択し、Ｙ１１からＹ１２を経てＸ４へ至る経路を、始点側の細メッシュの出入口から端部出入口までの経路として選択し、更にＸ４からＸ５を経てＸ６に至る経路を端部出入口間の経路として選択する。同様にして経路算出手段７０は、Ｘ６から終点５０２までの経路を求める。以上で本フローチャートの処理は終了する。

図９は、メッシュ内移動コスト記憶部４０が更に格納する、出入口間の移動コストの一例を示す図である。本例においてメッシュ内移動コスト記憶部４０は、予め計算された出入口間の移動コストを格納したが、経路算出手段７０が算出した移動コストの計算結果を、更に格納してもよい。ここでメッシュ内移動コスト記憶部４０は、端部出入口の番号と、端部出入口を中継した複数の出入口の番号とを、算出された移動コストに対応づけて格納する。この場合、経路算出装置１００は、計算結果の移動コストを、新たな経路の移動コストを求める場合に利用してもよい。これにより本発明の経路算出装置１００は、過去に計算したメッシュ間の移動コストについては、再び計算する必要がないので、より高速に経路を求めることができる。

また、本例におけるメッシュの大きさは、全て同じ長方形状であったが、他の例においては、交通量がより大きい都市部におけるメッシュの大きさは、他の地域におけるメッシュの大きさよりも小さくてもよく、或いは、道路の密度が高い都市部におけるメッシュの大きさは、他の地域におけるメッシュの大きさよりも小さくてもよい。

メッシュの大きさが一定である場合、交通量が多い都市部や道路密度が高い都市部におけるメッシュの出入口の個数は、他の地域におけるメッシュの出入口の個数よりも相対的に多くなる。しかしながら、始点及び終点から端部出入口までの部移動コストを求める場合、移動コストの算出時間を短縮する為には、出入口の数が少ないことが望ましい。本発明における経路算出装置１００においては、交通量や道路の密度が大きい地域のメッシュを小さくするので、メッシュへの出入口の個数を相対的に少なくすることができるので、高速に経路を求めることができる。また、小さいメッシュには、より細かい道路の出入口を対応づけてもよく、これにより経路検索の精度を上げることができる。

以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

本発明の実施形態に係る経路算出装置１００の構成の一例を示す図である。メッシュ及び細メッシュの一例を示す図である。（ａ）は、メッシュを説明する図であり、（ｂ）細メッシュを説明する図である。メッシュ内移動コスト記憶部４０に格納されるデータ構成の一例を示す図である。細メッシュ内移動コスト記憶部４５に格納されるデータ構成の一例を示す図である。経路算出装置１００の動作の一例を示すフローチャートである。細メッシュにおける道路及びノードを説明する図である。ノード間移動コスト記憶部６５に格納されるデータ構成の一例を示す図である。図５におけるＳ１１５の詳細な動作の一例を示すフローチャートである。メッシュ内移動コスト記憶部４０に更に格納される、出入口間の移動コストの一例を示す図である。

符号の説明

１０・・・メッシュ記憶部、１５・・・細メッシュ記憶部、３０・・・メッシュ選択手段、４０・・・メッシュ内移動コスト記憶部、４５・・・細メッシュ内移動コスト記憶部、５０・・・出入口選択手段、６０・・・端部移動コスト算出手段、６５・・・ノード間移動コスト記憶部、７０・・・経路算出手段、１００・・・経路算出装置、１１０・・・記録媒体、３００・・・地図、３０２〜３１８・・・メッシュ、４００〜４１６・・・細メッシュ、５００・・・始点、５０２・・・終点、５１０・・・楕円領域、Ｘ１〜Ｘ１２、Ｙ１〜Ｙ１４・・・出入口、Ｚ１〜Ｚ６・・・ノード

Claims

地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、
前記複数のメッシュのそれぞれへの道路の出入口及び当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部と、
前記複数のメッシュに含まれるいずれか２つのメッシュの、一のメッシュ内部の始点、及び他のメッシュ内部の終点が指定された場合に、前記２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択手段と、
前記選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択手段と、
前記選択された出入口間の移動コストを前記メッシュ内移動コスト記憶部から読み出すことにより、前記選択された出入口の中で、前記２つのメッシュを結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出手段と
を備えた経路算出装置。
前記始点、及び前記終点が指定された場合に、前記始点及び前記終点が含まれるメッシュに隣接するメッシュへの前記選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出手段を更に備え、
前記端部出入口間の移動コストを前記経路算出手段によって求め、前記端部移動コストを加算することにより、前記始点から前記終点までの移動コストを算出する請求項１に記載の経路算出装置。
前記メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、
当該細メッシュへの道路の出入口、及び当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部と、
を備え、
前記端部移動コスト算出手段は、前記始点及び前記終点から前記始点及び前記終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、
前記メッシュ選択手段、前記出入口選択手段、及び前記経路算出手段はそれぞれ、前記各々１つの細メッシュの出入口から当該細メッシュの前記各々１つの出入口近傍のメッシュの出入口の、前記細メッシュの組み合わせ、前記細メッシュへの出入口、及び前記細メッシュの前記各々１つの出入口から、前記近傍のメッシュの出入口までの経路を算出する手段を有し、
前記端部移動コスト算出手段は、前記ダイクストラ法によって算出された移動コストに、前記細メッシュの前記各々１つの出入口から前記近傍のメッシュの出入口までの移動コストを加えることにより、前記端部移動コストを算出する請求項２に記載の経路算出装置。
交通量がより大きい都市部における前記メッシュの大きさは、他の地域における前記メッシュの大きさよりも小さい請求項１に記載の経路算出装置。
道路の密度が高い都市部における前記メッシュの大きさは、他の地域における前記メッシュの大きさよりも小さい請求項１に記載の経路算出装置。
地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、前記複数のメッシュのそれぞれへの道路の出入口及び当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部とを備える経路算出装置を制御することにより経路を算出する経路算出方法であって、
前記複数のメッシュに含まれるいずれか２つのメッシュの、一のメッシュ内部の始点、及び他のメッシュ内部の終点が指定された場合に、前記２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択ステップと、
前記選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択ステップと、
前記選択された出入口間の移動コストを前記メッシュ内移動コスト記憶部から読み出すことにより、前記選択された出入口の中で、前記２つのメッシュを結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出ステップと
を備えた経路算出方法。
前記始点、及び前記終点が指定された場合に、前記始点及び前記終点が含まれるメッシュに隣接するメッシュへの前記選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出ステップを更に備え、
前記端部出入口間の移動コストを前記経路算出ステップによって求め、前記端部移動コストを加算することにより、前記始点から前記終点までの移動コストを算出する請求項６に記載の経路算出方法。
前記経路算出装置は前記メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、当該細メッシュへの道路の出入口、及び当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部とを更に備えており、
前記端部移動コスト算出ステップは、前記始点及び前記終点から前記始点及び前記終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、
前記メッシュ選択ステップ、前記出入口選択ステップ、及び前記経路算出ステップはそれぞれ、前記各々１つの細メッシュの出入口から当該細メッシュの前記各々１つの出入口近傍のメッシュの出入口の、前記細メッシュの組み合わせ、前記細メッシュへの出入口、及び前記細メッシュの前記各々１つの出入口から、前記近傍のメッシュの出入口までの経路を算出するステップを有し、
前記端部移動コスト算出ステップは、前記ダイクストラ法によって算出された移動コストに、前記細メッシュの前記各々１つの出入口から前記近傍のメッシュの出入口までの移動コストを加えることにより、前記端部移動コストを算出する請求項７に記載の経路算出方法。
地図上の各領域を、複数のメッシュのいずれかに対応付けて格納するメッシュ記憶部と、前記複数のメッシュのそれぞれへの道路の出入口及び当該出入口間の移動コストを、当該メッシュに対応付けて格納するメッシュ内移動コスト記憶部とを備える経路算出装置を機能させるプログラムであって、
前記複数のメッシュに含まれるいずれか２つのメッシュの、一のメッシュ内部の始点、及び他のメッシュ内部の終点が指定された場合に、前記２つのメッシュを結ぶメッシュの組み合わせを選択するメッシュ選択手段と、
前記選択されたメッシュ中の隣接したメッシュ間の出入口を選択する出入口選択手段と、
前記選択された出入口間の移動コストを前記メッシュ内移動コスト記憶部から読み出すことにより、前記選択された出入口の中で、前記２つのメッシュを結ぶ、最も移動コストが小さくなる出入口の経路を求める経路算出手段と
を備えるプログラム。
前記始点、及び前記終点が指定された場合に、前記始点及び前記終点が含まれるメッシュに隣接するメッシュへの前記選択された出入口である端部出入口までの端部移動コストを、少なくともダイクストラ法を用いて算出する端部移動コスト算出手段を更に備え、
前記端部出入口間の移動コストを前記経路算出手段によって求め、前記端部移動コストを加算することにより、前記始点から前記終点までの移動コストを算出する請求項９に記載のプログラム。
前記経路算出装置は前記メッシュに含まれる各領域を、当該メッシュを分割した細メッシュのいずれかに対応付けて格納する細メッシュ記憶部と、当該細メッシュへの道路の出入口、及び当該出入口間の移動コストを格納する細メッシュ内移動コスト記憶部とを更に備えており、
前記端部移動コスト算出手段は、前記始点及び前記終点から前記始点及び前記終点が含まれる細メッシュの各々１つの出入口までの移動コストをダイクストラ法を用いて算出する手段を有し、
前記メッシュ選択手段、前記出入口選択手段、及び前記経路算出手段はそれぞれ、前記各々１つの細メッシュの出入口から当該細メッシュの前記各々１つの出入口近傍のメッシュの出入口の、前記細メッシュの組み合わせ、前記細メッシュへの出入口、及び前記細メッシュの前記各々１つの出入口から、前記近傍のメッシュの出入口までの経路を算出する手段を有し、
前記端部移動コスト算出手段は、前記ダイクストラ法によって算出された移動コストに、前記細メッシュの前記各々１つの出入口から前記近傍のメッシュの出入口までの移動コストを加えることにより、前記端部移動コストを算出する請求項１０に記載のプログラム。