遺伝的アルゴリズムを用いた経路探索装置及び方法
【課題】あるノードが共通ノードでない場合でも、そのノード以降にて親経路の一部を組み換えて子経路を生成可能である遺伝的アルゴリズムを用いた経路探索装置及び方法を提供する。
【解決手段】本発明の経路探索装置は、交叉処理にて、第１経路及び第２経路が共有する共通ノードを交叉可能ノードとして抽出し、共通ノードではない一方の経路上のノードから他方の経路に繋がる連結経路が探索された場合に、そのノードを、抽出された交叉可能ノード群に加える。そして、本発明の経路探索装置は、交叉可能ノード群から選択された交叉可能ノードが、一方の経路上のみに存在する場合、この交叉可能ノード以降にて、この交叉可能ノードを始端とする連結経路と、他方の経路の一部であって、この連結経路の終端である他方の経路上のノードから目的地に至る経路とで、一方の経路を部分的に組み換えて１本の子経路を生成する。
【解決手段】本発明の経路探索装置は、交叉処理にて、第１経路及び第２経路が共有する共通ノードを交叉可能ノードとして抽出し、共通ノードではない一方の経路上のノードから他方の経路に繋がる連結経路が探索された場合に、そのノードを、抽出された交叉可能ノード群に加える。そして、本発明の経路探索装置は、交叉可能ノード群から選択された交叉可能ノードが、一方の経路上のみに存在する場合、この交叉可能ノード以降にて、この交叉可能ノードを始端とする連結経路と、他方の経路の一部であって、この連結経路の終端である他方の経路上のノードから目的地に至る経路とで、一方の経路を部分的に組み換えて１本の子経路を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車載用ナビゲーション装置に代表される経路探索装置と、出発地から目的地に至る経路を探索する経路探索方法とに関する。
【背景技術】
【０００２】
経路探索装置は、多数のノードとリンクで構成された経路網上において、出発地から目的地に至る最適な経路を求める装置である。周知のように、車載用ナビゲーション装置は、社会において最も広く普及している経路探索装置であり、ノード及びリンク情報を含む地図データを記録した記録媒体と、ＧＰＳ等を用いた車両情報取得手段と、ＬＣＤ等を用いた表示手段と、車両情報取得手段等から送られたデータの処理や経路探索等を行う制御手段とを具えている。車載用ナビゲーション装置では、ノードは、交差点や交差点等の経路網上の基準点に相当している。リンクは、ノード間の接続(つまり、ノード間を繋ぐ道路)を表しており、向きを有する場合が一般的である。
【０００３】
車載用ナビゲーション装置では、出発地(出発地ノード)及び目的地(目的地ノード)が入力又は決定されると、これらの地点を結ぶ最適経路(又は複数の経路からなる最適経路候補)が制御手段にて求められてユーザに提示される。また、車載用ナビゲーション装置では、車両情報取得手段によって逐次得られる位置情報に基づいて、車両付近の地図データが記録媒体から読み出される。そして、車両の現在位置と選択すべき道路とが明示された状態で、現在位置付近の地図が表示手段にて随時表示されることによって、最適経路に沿ってユーザが誘導される。
【０００４】
一般的な車載用ナビゲーション装置では、ダイクストラ法によって、最適経路が求められている。ダイクストラ法は、基本的なアルゴリズムが比較的単純であるために、制御手段として実装されるマイクロコンピュータ(以下、「マイコン」と称する)に過度の負担を掛けることがなく、経路探索が短時間で済む利点がある。しかしながら、その一方で、信頼性が低く、真に又は十分に適切な経路が求められない事態がかなりの頻度で生じてしまう。この問題を解決するために、近年、遺伝的アルゴリズムを用いて最適経路を探索する車載用ナビゲーション装置が幾つか提案されている(特許文献１乃至３参照)。
【０００５】
車載用ナビゲーション装置において、遺伝的アルゴリズムを用いた経路探索は、例えば以下のように行われる。まず、出発地から目的地に至る経路を染色体とする初期集団が準備される。遺伝的アルゴリズムでは、各染色体は、遺伝子の集団で構成される。車載用ナビゲーション装置では、通常、遺伝子としてリンク又はノードが用いられて、各経路は、リンク列又はノード列で表現される。
【０００６】
次に、各経路について算出された評価コスト(適応度)に基づいて選択処理が行われて、初期集団から２本の親経路が選択される。２本の親経路がランダムに選択されてもよいが、通常、評価コストが高い経路がより高い確率で選択されるように選択処理が行われる。評価コストとは、移動時間、移動費用、又は経路長さ等である。
【０００７】
次に、選択された親経路に対して遺伝子操作処理が、一般的には、交叉処理、さらには突然変異処理が行われて新たな経路が作成される。交叉処理は、染色体の一部、即ちリンク列又はノード列の一部を、選択された経路間で組み換えて新たな経路(子経路)を生成するものであり、突然変異処理は、生成された子経路のリンク列又はノード列の一部を適当なリンク列又はノード列に入れ換えるものである。このように生成された子経路は、初期集団に加えられる。そして、評価コストが低い２本の経路を初期集団から取り除く淘汰処理が行われる。以後、経路集団に対して、選択処理、遺伝子操作処理、及び淘汰処理が所定の回数だけ繰り返された後、評価コストが最も優れた経路が最適経路として特定される。
【特許文献１】特開平９−１７８５００号公報
【特許文献２】特開平１１−１１８５０１号公報
【特許文献３】特開２０００−１７２６６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記のような遺伝的アルゴリズムを用いた経路探索では、以下に述べる問題が生じる。図７は、高速道路のインターチェンジ(ＩＣ)付近のノード及びリンクを示している。図においてノードは白丸で、リンクは矢印で示されている(以下同様)。なお、黒の矢印は高速道路、白の矢印は一般道路、灰色の矢印は連結路に対応している。
【０００９】
上記に述べた選択処理にて、経路Ｅ及びＦの２本の経路が選択されたケースを考える。経路Ｅは、高速道路を用いて目的地に向かう経路であって、このＩＣを通り過ぎる。経路Ｅは、リンク列｛Ｌe(1),・・・，Ｌe(i)，Ｌe(i+1)，Ｌe(i+2)，・・・，Ｌe(n)｝で表現される。経路Ｆは、（少なくともこのＩＣ付近では）一般道路を通って目的地に向かう経路であって、リンク列｛Ｌf(1),・・・，Ｌf(j)，Ｌf(j+1)，Ｌf(j+2)，・・・，Ｌf(m)｝で表現される。経路Ｅ及びＦに交叉処理を施して、新たな経路が生成されるためには、このＩＣにてこれら経路が交わっていること、言い換えると、このＩＣにてこれら経路に共通ノードがあることが必要とされる。
【００１０】
しかしながら、図７に示すような経路Ｅ及びＦが選択された場合、このＩＣにて経路Ｅ及びＦの共通ノードは存在しないことから、交叉処理の結果として、このＩＣにて高速道路を降りて一般道路に移行する経路｛Ｌe(1),・・・，Ｌe(i)，Ｌr(1)，Ｌf(j+2)，・・・，Ｌf(m)｝(Ｌr(1)は連結路を表すリンク)が生成されることはない。また、同様な理由から、このＩＣにて一般道路から高速道路に移行する経路｛Ｌf(1),・・・，Ｌf(j)，Ｌr(2)，Ｌe(j+2)，・・・，Ｌe(n)｝(Ｌr(2)は連結路を表すリンク)も生成されることはない。従って、このＩＣにて高速道路から一般道路に、又は一般道路から高速道路に移行することが最適経路に求められる場合に、従来の遺伝的アルゴリズムを用いた経路探索では、交叉処理が有効に機能し得えなかった。その結果、遺伝的アルゴリズムを用いても、最適経路として適切な経路が必ずしも求められない事態が生じていた。
【００１１】
同様な問題は、高架橋を含んだ交差路についても生じる。図８Ａは、このような交差路付近のノード及びリンクを示している。選択処理にて、例えば、経路Ｇ及び経路Ｈの２本の経路が選択されており、経路Ｇは高架橋上の基幹道路(黒色の矢印(リンク)で示す)を通って目的地に向かう経路であって、リンク列｛Ｌg(1),・・・，Ｌg(i)，Ｌg(i+1)，Ｌg(i+2)，・・・，Ｌg(n)｝で表現される。経路Ｈは、高架橋下の道路(白色の矢印で示す)を通って目的地に向かう経路であって、リンク列｛Ｌh(1),・・・，Ｌh(j)，Ｌh(j+1)，Ｌh(j+2)，・・・，Ｌh(m)｝で表現される。交差路付近にて経路Ｇ及びＨには共通のノード(白丸で示す)が存在しないことから、交叉処理の結果として、高架橋下の道路から連結路(灰色の矢印で示す)を通って基幹道路に移行する経路｛Ｌh(1),・・・，Ｌh(j)，Ｌr(3)，Ｌg(j+2)，・・・，Ｌg(n)｝(Ｌr(3)は連結路を表すリンク)が生成されることはない。
【００１２】
また、同様な問題は、本道と側道から構成される平行道路についても生じる。図８Ｂは、このような平行道路のノード及びリンクを示している。選択処理において、図示したノード付近にて本道(黒色の矢印(リンク)で示す)を通る経路Ｉと、側道(白色の矢印で示す)を通る経路Ｊとが選択された場合、交叉処理にて、連結路(灰色の矢印で示す)を通って本道から側道に移行する経路、又は側道から本道に移行する経路が生成されることはない。
【００１３】
本発明は、以上の問題を解決するものであり、あるノードが共通ノードでない場合でも、そのノード以降にて親経路の一部を組み換えて子経路を生成可能である遺伝的アルゴリズムを用いた経路探索装置及び方法を提供する。
【課題を解決するための手段】
【００１４】
本発明の経路探索装置は、出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索装置である。
【００１５】
本発明の経路探索装置は、前記交叉処理にて、前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、このノードを抽出された交叉可能ノード群に加え、共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、このノードを前記交叉可能ノード群に加える。
【００１６】
さらに、本発明の経路探索装置は、前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成し、前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成し、前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する。
【００１７】
本発明の経路探索方法は、出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索方法である。
【００１８】
本発明の経路探索方法は、前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、このノードを抽出された交叉可能ノード群に加える工程と、共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、このノードを前記交叉可能ノード群に加える工程とを含んでいる。
【００１９】
さらに、本発明の経路探索方法は、前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程と、前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程と、前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含んでいる。
【発明の効果】
【００２０】
本発明によれば、あるノードが共通ノードでなくとも、所定の条件を満たす場合には、そのノード以降にて、一方の親経路が、連結経路と、連結経路の終端から目的地に至る他方の親経路の一部分と組み換えられて子経路が生成される。従って、選択された親経路が、例えば、ＩＣにて交差しない場合であっても、交叉処理にて、ＩＣから一般道路に移行する子経路又は一般道路からＩＣに移行する子経路が生成されて、遺伝的アルゴリズムによる経路探索がより効率的に機能すする。
【００２１】
所定の条件は、共通ノードではない第１又は第２経路上のノードと、このノードを始端ノードとする第１又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含むのが好ましい。また、所定の条件は、第１又は第２連結経路の長さが所定の長さ以下であることを含むことが好ましい。これらによって、適切な第１及び第２連結経路が探索される。
【００２２】
また、経路集団は、ダイクストラ法を用いて準備するのが好ましく、第１連結経路及び前記第２連結経路は、ダイクストラ法を用いて探索されるのが好ましい。ダイクストラ法を、このように、遺伝的アルゴリズムと組み合わせることによって、遺伝的アルゴリズムを用いた経路探索を迅速化することが可能となる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を車載用ナビゲーション装置に適用した実施例について説明する。図１は、本発明の実施例である車載用ナビゲーション装置(以下、「ナビゲーション装置」と称する)の概要を示すブロック図である。本実施例のナビゲーション装置は、車両の現在位置等を取得する車両情報取得手段と、記録媒体に記録された地図データを読み出す記録手段と、ナビゲーション画面や各種情報等を表示する表示手段と、ドライバーを誘導する音声を出力する音声出力手段と、各種キー等を含む操作手段と、これら手段に接続されて動作上必要な各種処理及び制御等を行う制御手段とを含んでいる。
【００２４】
車両情報取得手段は、ＧＰＳ受信部(1)と、ジャイロスコープ(3)と、ジャイロマイコン(5)等で構成される。ＧＰＳ受信部(1)は、ＧＰＳアンテナ(7)を介してＧＰＳ衛星から送られる電波を受信し、受信信号に基づいて車両の絶対位置を算出する。算出された車両の絶対位置(例えば、この位置は、緯度及び経度で与えられる)は、制御手段たる制御マイコン(9)に送られる。制御マイコン(9)は、図示を省略したＣＰＵ、ＲＡＭ及びＲＯＭ等で構成されている。ジャイロスコープ(3)は、車両の方位を得るために用いられており、ジャイロマイコン(5)は、ジャイロスコープ(3)から送られた信号に基づいて車両の方位を決定し、その情報を制御マイコン(9)に送る。また、ジャイロマイコン(5)には、車両に設けられた車速センサ(図示せず)から車速パルス信号が送られる。ジャイロマイコン(5)は、車速パルス信号に基づいて車両の速度や走行距離を決定し、それらを制御マイコン(9)に送る。制御マイコン(9)は、ジャイロマイコン(5)から送られる車両の方位及び走行距離情報から車両の相対位置を決定し、相対位置情報とＧＰＳ受信部(1)から送られる絶対位置情報とから走行軌跡を求めて、地図データ上の道路(リンク)と整合させる。
【００２５】
記録手段は、記録媒体(11)と、記録媒体(11)から情報を読み出して制御マイコン(9)に送るドライバ(13)等とで構成される。記録媒体(11)には、例えばＤＶＤ、ＣＤ−ＲＯＭやハードディスクが用いられており、地図データが記録されている。地図データには、形状情報(背景データ及び道路データ)、接続情報(道路ネットワークデータ)、及び属性情報(場所検索データ及びサービス検索データ)等が含まれている。接続情報は、地図上のノードとリンクに関する情報を含んでおり、経路探索に用いられる。各ノードに関する情報は、例えば、ノードＩＤ番号、座標、道路種別情報、及び隣接リンク情報で構成される。各リンクに関する情報は、例えば、リンクＩＤ番号、道路種別情報、規制情報、リンク長、隣接ノード情報、及び展開可能リンク番号等で構成される。
【００２６】
制御マイコン(9)は、処理に必要な情報を、ドライバ(13)を介して記録媒体(11)から適宜取得する。例えば、表示手段にナビゲーション画像を表示するナビゲーション動作を行っている際、ナビゲーション装置は、車両情報取得手段から得られた位置情報等に基づいて、その付近のノード、リンク及びその他の情報を取得する。制御マイコン(9)は、車両情報取得手段及び記録手段から得られた情報を処理して、ナビゲーション画像を作成するのに必要な指示を表示手段に送る。表示手段は、描画ＩＣ(15)、ＬＣＤＩ/Ｆ(17)及びＬＣＤ(19)等で構成されている。描画ＩＣ(15)は、車両の現在位置及び進行方向や各種道路及び施設等を表現するキャラクタデータと、住所や道路の名称等を表示するための文字データとを記憶したメモリを有しており、制御マイコン(9)からの指示に基づいてナビゲーション画像の画像データを作成する。描画ＩＣ(15)で作成された画像データはＬＣＤＩ/Ｆ(17)を介してＬＣＤ(19)に送られて、該ＬＣＤ(19)にナビゲーション画像が表示される。また、制御マイコン(9)は、ナビゲーション動作の際に、車両情報取得手段及び記録手段から得られた情報を処理して、音声でドライバーを誘導するための音声データを作成する。音声データは、デジタル形式で作成されて、音声出力手段に送られる。音声出力手段は、デジタル−アナログコンバータ(21)と、アンプ(23)と、スピーカ(25)等とで構成されており、制御マイコン(9)から送られた音声データは、デジタル−アナログコンバータ(21)でアナログ化されて、アンプ(23)で増幅された後に、スピーカ(25)から出力される。
【００２７】
操作手段は、ナビゲーション装置の筐体に設けられた各種操作キー(27)と、ＬＣＤ(19)上に配置されるタッチパネル(29)と、付属のリモートコントローラ(図示せず)と、このリモートコントローラから送られた赤外線信号を受光するリモコン受光部(31)と、これらからの入力を処理するキーマイコン(33)等とで構成される。ある操作キー(27)が押されると、キーマイコン(33)は、押された操作キー(27)を判別して、それに応じた動作コマンドを制御マイコン(9)に送る。また、キーマイコン(33)は、ＬＣＤ(19)に設定用画面が表示されている状態にて、タッチパネル(29)が押された領域を判別して、操作に対応した動作コマンドを制御マイコン(9)に送る。リモコン受光部(31)は、受光した赤外線信号を電気信号に変換し、さらには変換した電気信号を復調してキーマイコン(33)に送り、キーマイコン(33)は、送られた信号に基づいて特定した動作コマンドを制御マイコン(9)に送る。
【００２８】
上述した車両情報取得手段や記憶手段等に加えて、ナビゲーション装置には、道路交通情報を提供する情報システムや高速道路の自動料金徴収システム等のインフラストラクチャを利用する手段が設けられている。ナビゲーション装置は、ＶＩＣＳ(Vehicle Information Communication System)を利用して、渋滞情報、事故・工事情報及び速度規制情報等の道路交通情報を取得可能である。ＶＩＣＳチューナ(35)は、ＦＭ用アンテナ(37)を介して、道路交通情報が重畳されたＦＭ多重放送を受信し、ＲＦアンテナ(39)を介して、道路上に設けられた電波ビーコンから送られた、道路交通情報に関する２.５ＧＨｚのＲＦ信号を受信して復調する。また、ＶＩＣＳマイコン(41)には、道路上に設けられた光ビーコンから送られた、道路交通情報に関する赤外線信号を受光する光ビーコン受光部(43)が接続されており、光ビーコン受光部(43)は、受光した赤外線信号を電気信号に変換、さらには電気信号を復調する。ＶＩＣＳマイコン(41)は、ＶＩＣＳチューナ(35)や光ビーコン受光部(43)から送られる復調信号を処理して道路交通情報を得る。得られた道路交通情報は、制御マイコン(9)で処理されて、ＬＣＤ(19)に表示される。また、ナビゲーション動作中では、車両情報や地図データに加えて、ＶＩＣＳマイコン(41)から送られる道路交通情報にも基づいて、ナビゲーション画面が作成される。例えば、渋滞情報に基づいて、渋滞した道路がナビゲーション画面にて明示される。
【００２９】
さらに、ナビゲーション装置には、ＥＴＣ(Electronic Toll Collection System)を利用するためのＥＴＣ装置(45)が接続されている。ＥＴＣ装置(45)は、５.８ＧＨｚのＲＦ信号を送受信するためのＲＦアンテナと、変復調処理を行う送受信部と、ＥＴＣカードを読み書きするリーダライタと等で構成されている(何れも図示せず)。制御マイコン(9)は、例えば、ＥＴＣ装置(45)から送られた情報に基づいて、ＥＴＣゲートのレーンをスピーカ(25)の音声で案内したり、ＥＴＣゲートの拡大図をＬＣＤ(19)に表示する。
【００３０】
以下、本実施例のナビゲーション装置が行う経路探索動作について説明する。図２は、この経路探索動作の概要を示すフローチャートであって、この動作を記述したプロクラムは、制御マイコン(9)内のＲＯＭに格納されており、制御マイコン(9)内のＣＰＵにて実行される。操作手段を介して経路探索動作モードが選択されると、制御マイコン(9)からの指示により、出発地及び目的地の入力をドライバーに促す設定画面がＬＣＤ(19)に表示されて、それらの設定が行われる(Ｓ１)。なお、設定される出発地は、車両情報取得手段から得られた車両の現在位置でもよい。そして、制御マイコン(9)は、出発地及び目的地を含む所定の領域内のノード及びリンク情報を記録媒体(11)から読み出して、内蔵するＲＡＭに記憶する(Ｓ２)。以後の処理において、ＲＡＭに記憶されたノード及びリンク情報は適宜参照される。
【００３１】
ステップＳ２の後、制御マイコン(9)は、ダイクストラ法を用いて初期集団を生成する処理を行う(Ｓ３)。初期集団は、複数の経路からなる経路集団(遺伝子プール)であって、出発地のノード(又は出発地に最も近いノード。以下「出発地ノード」と称す)と、目的地のノード(又は目的地に最も近いノード。以下「目的地ノード」と称す)とを結ぶ複数の経路(例えば、２０本の経路)で構成されている。生成された経路集団は、ＲＡＭに記憶される。なお、ＤＦＳ法又はダイクストラ法以外のＢＦＳ法を用いて、初期集団が生成されてもよい。
【００３２】
ステップＳ３の後、経路集団から親経路を２本選択する処理が行われる(Ｓ４)。ステップＳ４では、任意の２本の親経路が選択されてもよいが、後述する評価コストが高い経路がより高い確率で親経路として選択されるのが好ましい。本実施例では、リンクを遺伝子としており、経路はリンク列で表現される。以後、選択された２本の親経路を経路Ａ｛Ｌa(1),・・・，Ｌa(n)｝と、経路Ｂ｛Ｌb(1),・・・，Ｌb(m)｝表記する。経路Ａは、出発地側から順番に、Ｌa(1)からＬa(n)までのｎ個のリンクで構成されている。経路Ｂは、出発地側から順番に、Ｌb(1)からＬb(m)までのｍ個のリンクで構成されている。また、以後、経路Ａ上のｎ＋１個のノードを、出発地側から順番に、Ｎa(0),・・・，Ｎa(n)(Ｎa(0)は出発地ノード、Ｎa(n)は目的地ノード)と表記する。また、経路Ｂ上のｍ＋１個のノードを、出発地側から順番に、Ｎb(0),・・・，Ｎb(m)(Ｎb(0)＝Ｎa(0) 、Ｎb(m)＝Ｎa(n))と表記する。リンクＬa(i)の始端ノードは、ノードＮa(i-1)となり、リンクＬa(i)の終端ノードは、ノードＮa(i)となる。
【００３３】
ステップＳ４の後、遺伝子操作処理、具体的には、選択された親経路に対して交叉処理が施されて、１又は２本の子経路が生成される(Ｓ５)。生成された経路は経路集団に加えられて、淘汰処理が行われる(Ｓ６)。淘汰処理では、経路集団を構成する経路について評価コストが比較されて、評価コストが最も低い１又は２本の経路が経路集団から取り除かれる。子経路が１本である場合１本の経路が、子経路が２本である場合２本の経路が取り除かれる。なお、経路集団に同一の経路が複数存在するケースがあり得るので、同一経路があるか否かの判定を行って、同一経路がない場合には、上述のように淘汰処理を行い、同一経路がある場合には、経路の重複分を経路集団から取り除くようにステップＳ６を構成してもよい。また、本実施例では、ステップＳ５において、交叉処理のみが行われるが、生成された子経路の一部のリンク列を入れ換える突然変異処理のような子経路を対象とする処理がさらに行われてもよい。本発明は、遺伝的アルゴリズムにおける交叉処理に関するものであって、本発明の効果が失われない限り、経路探索動作はどのように変更されてもよい。
【００３４】
本実施例では、ステップＳ６(必要に応じてステップＳ４も)において、経路の評価コストは、評価コスト＝Σ(所用時間×ドライバ時間単価)＋燃料単価×Σ消費燃料＋有料道路料金、として求められる。この式で、所用時間、ドライバ時間単価及び消費燃料は、リンクに応じて定められる値であり、Σは、経路を構成する全リンクについて和をとることを意味する。各リンクの所用時間は、所要時間＝(平均移動時間×道路種別係数×道幅係数×規制速度係数)＋１０秒×右折左折回数＋３０秒×信号数＋５秒×交差点数)×地域係数×バイパス係数、として算出される。平均移動時間、道路種別係数、規制速度係数、信号数等は各リンクについて地図データに含まれているか、地図レーダの情報に基づいて定められる。平均移動時間は、リンクを移動するのに要する平均時間であり、道路種別係数、道幅係数、規制速度係数、地域係数及びバイパス係数は、そのリンクの種々の特長に応じて設定される係数である。例えば、地域係数は、リンクが都会にある場合は０.９とされ、その他は１とされる。また、バイパス係数は、リンクがバイパスである又はバイパスの一部であるならば１.１とされ、その他は１とされる。ドライバ時間単価は、所用時間をコスト(価格)に換算するための値であり、出発地付近では高く、目的地付近では低く、中間では中程度に設定される。
【００３５】
各リンクに関する消費燃料は、消費燃料＝リンク長÷燃費×道路種別消費燃料係数＋５０ｍｌ×右折左折回数＋５０ｍｌ×信号数、として算出される。また、評価コストに関する上述の式にて、ドライバ時間単価とは、移動時間をコストに換算する値であり、有料道路料金とは、経路における高速道路等の通行料金である。
【００３６】
ステップＳ６の後、制御マイコン(9)は、終了条件が満たされているか否かを判断する(Ｓ７)。例えば、終了条件は、ステップＳ４乃至６の繰り返し回数が、所定回数(例えば、５０回)に至ったというものである。ステップＳ７にて、終了条件が満たされていないと判断された場合には、再度、制御マイコン(9)は、ステップＳ４乃至６の処理を行う。満たされていると判断された場合には、制御マイコン(9)は、経路探索結果をＬＣＤ(19)に表示する(Ｓ８)。ＬＣＤ(19)には、例えば、評価コストの最も高い経路、又は、評価コストが上位である複数の経路が表示される。
【００３７】
本発明は、一方の親経路のあるノードが共通ノードでなくとも、交叉処理(Ｓ５)にて、所定の条件を満たすならば、そのノード以降についてリンク列を部分的に組み換えて子経路を生成できることを特徴とする。以下、図３乃至５のフローチャートを参照して、本実施例の交叉処理を具体的に説明する。図３を参照すると、まず最初に変数ｇ及びフラグの初期化が行われる(Ｓ１１)。変数ｇは１に、フラグはオフにされる。なお、以下に言及する変数の値、フラグ及び処理結果等は、制御マイコン(9)内のＲＡＭに適宜記憶され、読み出される。次に、経路Ａ及びＢの両方に存在する共通ノードを抽出する処理が行われる(Ｓ１２)。抽出された共通ノードは、交叉可能ノードとして制御マイコン(9)内に記憶される。以後、抽出されたｋ個の交叉可能ノードを、Ｎ(1),・・・，Ｎ(k)と表記する。なお、この際、出発地及び目的地ノードは交叉可能ノードから除外される。さらに、経路Ａ及びＢにおいて最初の幾つかのリンクが共通する場合には、及び/又は、経路Ａ及びＢにおいて最後の幾つかのリンクが共通する場合には、このようなリンク上の共通ノードも交叉可能ノードから除外されるのが好ましい。ステップＳ１２にて抽出された交叉可能ノードが０個である場合もあり得るが、この場合でも図３乃至５に示す経路探索動作は、問題なく実行される。
【００３８】
ステップＳ１２の後、以後の処理にて経路Ａ上のノードを特定する変数ｉの値を設定する処理が行われる(Ｓ１３)。最初にステップＳ１３が行われる場合、ｉは１に設定される。ステップＳ１３は、後述するステップＳ１４からＳ２６までの処理を繰り返すループの始端となっており、後述するステップＳ１５は、このループの終端となっている。ステップＳ１３の後、ノードＮa(i)が共通ノードであるか否かが判断される(Ｓ１４)。ステップＳ１４にて、ノードＮa(i)が共通ノードであると判断された場合、ステップＳ１５にて、ノードＮa(i)が目的地ノードの１つ手前のノードであるか否か、即ち、ｉの値がｎ−１に等しいか否かが判断される(Ｓ１５)。ステップＳ１５にて、ｉの値はｎ−１と異なると判断された場合、処理はステップＳ１３に戻って、ｉの値がインクリメントされる。その後、ステップＳ１４以降の処理が再度行われる。
【００３９】
ステップＳ１４にて、ノードＮa(i)は共通ノードではないと判断された場合、以後の処理にて経路Ｂのノードを特定する変数ｊの値を設定する処理が行われる(Ｓ１６)。最初にステップＳ１６が行われる場合、ｊは１に初期化される。ステップＳ１６は、後述するステップＳ１７からＳ２４までの処理を繰り返すループの始端となっており、後述するステップＳ１８は、このループの終端となっている。ステップＳ１６の後、ノードＮb(j)が共通ノードであるか否かが判断される(Ｓ１７)。ステップＳ１７にて、ノードＮb(j)が共通ノードであると判断された場合、ステップＳ１８にて、ノードＮb(j)が目的地ノードの１つ手前のノードであるか否か、即ち、ｊの値がｍ−１に等しいか否かが判断される(Ｓ１８)。ステップＳ１８にて、ｊの値がｍ−１と異なると判断された場合、処理はステップＳ１６に戻って、ｊの値がインクリメントされる。その後、ステップＳ１７以降の処理が再度行われる。
【００４０】
ステップＳ１７にて、ノードＮb(j)は共通ノードではないと判断された場合、ノードＮa(i)とノードＮb(j)間の直線距離が、所定の距離Ｘ以下であるか否かが判断される(Ｓ１９)。ステップＳ１９にて、この直線距離が、所定の距離Ｘを超えていると判断された場合、ステップＳ１８以降の処理が行われる。ステップＳ１９にて、直線距離が所定の距離Ｘ以下であると判断された場合、ノードＮa(i)からノードＮb(j)への経路(以下、「連結経路」と称する)の探索が、タイクストラ法を用いて行われる(Ｓ２０)。なお、ＤＦＳ法又はダイクストラ法以外のＢＦＳ法が用いられてもよい。ステップＳ２０の後、経路探索が成功したか否かが判断される(Ｓ２１)。例えば、所定の時間、経路探索が行われても連結経路が得られない場合に、ステップＳ２１にて経路探索に失敗したと判断される。経路探索に失敗したと判断された場合、つまりノードＮa(i)からノードＮb(j)への連結経路が得られなかった場合、ステップＳ１８以降の処理が行われる。ステップＳ２０にて、ノードＮa(i)からノードＮb(j)への連結経路が得られた場合(ステップＳ２１にて経路探索に成功したと判断された場合)、この連結経路の長さがＸ＋α(αは所定の定数)以下であるか否かが判断される(Ｓ２２)。
【００４１】
ステップＳ２２にて、得られた連結経路の長さがＸ＋αを超えていると判断された場合、ステップＳ１８以降の処理が行われる。ステップＳ２０で求められた経路の長さがＸ＋α以下であると判断された場合、ノードＮa(i)は、交叉可能ノードＮ(k+g)として記憶されて、交叉可能ノード群に加えられる(Ｓ２３)。その後、探索された連結経路は、Ｒ(g) :｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝(ｏは正の整数。ｏ＝１ならば、Ｒ(g)は１つのリンクＬr(g)(1))として記憶されて、フラグがオンにされる(Ｓ２４)。
【００４２】
ステップＳ２４の後、ステップＳ１８が行われる。ノードＮb(1)からノードＮb(j-1)について、ステップＳ１７、Ｓ１９乃至２４が繰り返し行われると、ステップＳ１８にて、ｊの値はｍ−１と等しいと判断される。その場合、ステップＳ１８の後に、フラグがオンであるか否かが判断されて(Ｓ２５)、フラグがオンである場合には、変数ｇの値がインクリメントされて、フラグがオフに戻される(Ｓ２６)。ステップＳ２６の後、又は、ステップＳ２５にてフラグがオフである場合には、ステップＳ１５が行われる。
【００４３】
なお、ノードＮb(1)からノードＮb(j-1)について、ステップＳ１７、Ｓ１９乃至２４が繰り返し行われるので、経路Ａ上のあるノードＮa(i)について、連結される経路Ｂ上のノードが異なる複数の連結経路が探索されることが起こり得る。本実施例では、このような場合にステップＳ２４が繰り返して行われると、記録された連結経路Ｒ(g)が上書きされて、最終的により目的地に近い連結経路(連結される経路Ｂ上のノードが最も目的値に近い連結経路)が記録されるようになっている。なお、ステップＳ２４にて、既に記憶されている連結経路Ｒ(g)の長さと、新たに得られた連結経路の長さを比較して、後者の長さが前者の長さよりも短い場合に、上書きして後者を連結経路Ｒ(g)として記憶してもよい。
【００４４】
ノードＮa(1)からノードＮa(i-1)について、ステップＳ１４、Ｓ１６乃至Ｓ２６が繰り返し行われると、ステップＳ１５にて、ｉの値はｎ−１と等しいと判断される。そして、その後、図４に示す一連の処理が行われる。図４に示すステップＳ３１乃至４４の処理は、経路Ａと経路Ｂの立場が変わった点を除いて、図３に示したステップＳ１３以降の処理と基本的に同じものである。故に、図４に示すステップＳ３１乃至４４の処理に関する詳細な説明は省略する。例えば、ステップＳ３１はステップＳ１３に、ステップＳ３２はステップＳ１４に、ステップＳ３５はステップＳ１７に相当しており、ステップＳ３７はステップＳ１９に相当している。
【００４５】
ノードＮb(1)からノードＮb(j-1)について、ステップＳ３２、Ｓ３４乃至４４が行われると、ステップＳ３３にて、ｊの値はｍ−１と等しいと判断される。そして、その後、図５に示す一連の処理が行われる。まず、記憶されている交叉可能ノード群から、任意の交叉可能ノードＮ(w)が選択される(Ｓ６１)。ここで、ｗ＝１〜ｋ+ｇfであり、ｇfは、最終的なｇの値、つまり、上記の説明と、図３及び図４とから理解されるように、ステップＳ１２で抽出された交叉可能ノード群に対して、後に加えられた交叉可能ノードの全数に等しい。次に、選択した交叉可能ノードＮ(w)が経路Ａ上のノードであるか否かが判断される(Ｓ６２)。ステップＳ６２にて、交叉可能ノードＮ(w)が経路Ａ上にあると判断された場合、交叉可能ノードＮ(w)が経路Ｂ上のノードであるか否かが判断される(Ｓ６３)。ステップＳ６３にて、交叉可能ノードＮ(w)が経路Ｂ上にあると判断された場合、つまり、交叉可能ノードＮ(w)が経路Ａ及びＢの共通ノードである場合、この交叉可能ノードＮ(w)以降にて、経路Ａ及びＢのリンク列を部分的に相互に組み換える交叉処理が行われて、子経路Ｃ及びＤが生成される(Ｓ６４)。交叉可能ノードＮ(w)が経路Ａ上で出発地ノードから数えてｐ＋１番目に位置するノードＮa(p)であり、さらに、経路Ｂ上で出発地ノードから数えてｑ＋１番目に位置するノードＮb(q)であるとすると、ステップＳ６４で生成される子経路Ｃは、リンク列｛Ｌa(1),・・・，Ｌa(p),Ｌb(q+1),・・・，Ｌb(m)｝となり、子経路Ｄは、リンク列｛Ｌb(1),・・・，Ｌb(q),Ｌb(p+1),・・・，Ｌa(n)｝となる。ステップＳ６４の後、これら子経路Ｃ及びＤが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４６】
ステップＳ６１にて選択した交叉可能ノードＮ(w)が経路Ａ上のノードではないと、即ち、経路Ｂ上にのみ存在するノードであると、ステップＳ６２にて判断された場合、この交叉可能ノードＮ(w)以降にて、経路Ｂのリンク列を部分的に組み換える交叉処理が行われて、１本の子経路Ｄが生成される(Ｓ６６)。ステップＳ６６では、交叉可能ノードＮ(w)以降のリンク列は、ステップＳ４２で記憶された、この交叉可能ノードＮ(w)と経路Ａ上のノードを結ぶ連結経路Ｒ(g)のリンク列｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝と、経路Ａの一部であって、リンクＬr(g)(o)の終端ノードである経路Ａ上のノードから目的地ノードに至る経路のリンク列とを合成したものとなる。例えば、交叉可能ノードＮ(w)が、出発地ノードから数えて、経路Ｂにてｑ＋１番目に位置するノードであり、リンクＬr(g)(o)の終端ノードである経路Ａ上のノードが、出発地ノードから数えてｐ＋１番目に位置するノードであるとすると、子経路Ｄは、リンク列｛Ｌb(1),・・・，Ｌb(q),Ｌr(g)(1),・・・，Ｌr(g)(o),Ｌa(p+1),・・・，Ｌa(n)｝となる。ステップＳ６６の後、この子経路Ｄが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４７】
ステップＳ６１にて選択した交叉可能ノードＮ(w)が経路Ｂ上のノードではないと、即ち、経路Ａ上にのみ存在するノードであると、ステップＳ６３にて判断された場合、この交叉可能ノードＮ(w)以降にて、経路Ａのリンク列を部分的に組み換える交叉処理が行われて、１本の子経路Ｃが生成される(Ｓ６７)。ステップＳ６７では、交叉可能ノードＮ(w)以降のリンク列は、ステップＳ２４で記憶された、この交叉可能ノードＮ(w)と経路Ｂ上のノードとを繋ぐ連結経路Ｒ(g)のリンク列｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝と、経路Ｂの一部であって、リンクＬr(g)(o)の終端ノードである経路Ｂ上のノードから目的地ノードに至る経路のリンク列とを合成したものとなる。交叉可能ノードＮ(w)が、経路Ａにて出発地ノードから数えてｐ＋１番目に位置するノードであり、リンクＬr(g)(o)の終端ノードである経路Ｂ上のノードが、出発地ノードから数えてｑ＋１番目に位置するノードであるとすると、子経路Ｃは、リンク列｛Ｌa(1),・・・，Ｌa(p),Ｌr(g)(1),・・・，Ｌr(g)(o),Ｌb(q+1),・・・，Ｌb(m)｝となる。ステップＳ６７の後、この子経路Ｃが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４８】
図６は、本実施例の交叉処理を説明する概念図であり、図２に示すステップＳ４にて選択された親経路Ａ及びＢの一例を示している。本図では、これら経路は部分的に省略されて示されており、経路Ａを構成する各リンクは黒色の矢印で、 経路Ｂを構成する各リンクは白色の矢印で、ノードは白丸で示されている。図３に示すステップＳ１２では、共通ノードが抽出されて交叉可能ノードとして記憶される。図６に示す例では、ステップＳ１２が行われると、リンクＬa(2)とＬb(2)の終端ノードが交叉可能ノードＮ(1)として、リンクＬa(n-1)とＬb(m-1)の始端ノードが交叉可能ノードＮ(k)として記憶される(なお、交叉可能ノードＮ(1)とＮ(k)の間に位置するその他の共通ノードも記憶される)。
【００４９】
図３に示すステップＳ１３以降の処理は、共通ノードではない経路Ａ上のノードの各々について、所定の条件を満たした、該ノードから経路Ｂに接続する連結経路を探索して記憶するものである。また、そのような連結経路が探索されたノードは、交叉可能ノード群に加えられる。ステップＳ１６を始端とし、ステップＳ１８を終端とするループでは、ステップＳ１３で指定された共通ノードではない、経路Ａ上のある１つのノードについて、出発地及び目的地ノードを除く経路Ｂ上のノードの各々について、所定の条件を満たす連結経路を求める試みが行われる。例えば、ステップＳ１３にて、図６に示す経路Ａ上のノードＮa(p)が指定された場合、第１の条件は、連結経路の両端のノード間の直線距離が所定の距離Ｘ以下であることなので、ステップＳ１９にて、ステップＳ１７で指定された経路Ｂ上のノードがノードＮa(p)を中心とする半径Ｘの円内にあるか否かが判断される。図６に示す例では、経路Ｂ上のノードＮb(q)がこの円内に入っており、ステップＳ１７にてノードＮb(q)が指定された場合、ステップＳ１９の後に、ノードＮa(p)からノードＮb(q)への連結経路が探索される(Ｓ２０)。
【００５０】
第２の条件は、連結経路の長さが所定の長さ以下であることである。ステップＳ２０で得られた連結経路は、例えば、図６に示す円から大きくはみ出た経路である可能性があり、このような実質的に無意味な経路がこの条件を課すことで排除される。この条件は、ステップＳ２２にて判断される。所定の長さＸ＋αは、当然にＸよりも長く、例えば、αは、Ｘと同程度の大きさに設定される。連結経路が、この第２の条件を満たす場合、ノードＮa(p)は、交叉可能ノードとして記憶され(Ｓ２３)、連結経路はＲ(g)として記憶される(Ｓ２４)。図６では、記憶された連結経路Ｒ(g)を、灰色の矢印のリンクで示してある。
【００５１】
図４に示すステップＳ３１以降の処理は、ステップＳ１２で抽出された共通ノードではない経路Ｂ上のノードの各々について、上記と同様にして、上述の第１及び第２の条件を満たした、該ノードから経路Ａに接続する連結経路を求めて記憶するものである。また、そのような連結経路の始端となる経路Ｂ上のノードは、交叉可能ノード群に加えられる。
【００５２】
図６に示す例では、例えば、ステップＳ６１にて、図中に示すノードＮ(1)やノードＮ(k)のような共通ノードである交叉可能ノードが選択されると、ステップＳ６４にて、従来の交叉処理のようにリンク列の組換えが行われて２本の子経路が作成される。一方で、例えば、ステップＳ６１にて、図６中に示すノードＮa(p)が選択されると、上述したように、経路Ａのように出発地ノードからノードＮa(p)に至り、その後、連結経路Ｒ(g)を通って、経路ＢのようにノードＮb(q)から目的地ノードに至る１本の子経路Ｃが生成される。
【００５３】
本実施例では、各経路は、先に示したようにリンクを遺伝子としたリンク列で表現されているが、ノードを遺伝子としてノード列で表現されていてもよい。また、本発明を車載用ナビゲーション装置に適用した実施例を取り上げて本発明を説明したが、本発明は、それ以外の経路探索装置、例えば、荷物等の輸送経路を探索する装置や巡回経路を探索する装置に用いることができる。
【００５４】
上記実施例の説明は、本発明を説明するためのものであって、特許請求の範囲に記載の発明を限定し、或は範囲を減縮する様に解すべきではない。本発明の各部構成は上記実施例に限らず、特許請求の範囲に記載の技術的範囲内で種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施例である車載用ナビゲーション装置の概要を示すブロック図である。
【図２】本発明の本実施例のナビゲーション装置が行う経路探索動作の概要を示すフローチャートである。
【図３】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図４】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図５】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図６】本発明の実施例のナビゲーション装置が行う交叉処理を説明する概念図である。
【図７】高速道路のインターチェンジ付近のノード及びリンクを示す説明図である。
【図８】図８Ａは、交差路付近のノード及びリンクを示す説明図、図８Ｂは、平行道路のノード及びリンクを示す説明図である。
【符号の説明】
【００５６】
(1) ＧＰＳ受信部
(3) ジャイロスコープ
(5) ジャイロマイコン
(9) 制御マイコン
(11) 記録媒体
(19) ＬＣＤ
(25) スピーカ
(27) キー
【技術分野】
【０００１】
本発明は、車載用ナビゲーション装置に代表される経路探索装置と、出発地から目的地に至る経路を探索する経路探索方法とに関する。
【背景技術】
【０００２】
経路探索装置は、多数のノードとリンクで構成された経路網上において、出発地から目的地に至る最適な経路を求める装置である。周知のように、車載用ナビゲーション装置は、社会において最も広く普及している経路探索装置であり、ノード及びリンク情報を含む地図データを記録した記録媒体と、ＧＰＳ等を用いた車両情報取得手段と、ＬＣＤ等を用いた表示手段と、車両情報取得手段等から送られたデータの処理や経路探索等を行う制御手段とを具えている。車載用ナビゲーション装置では、ノードは、交差点や交差点等の経路網上の基準点に相当している。リンクは、ノード間の接続(つまり、ノード間を繋ぐ道路)を表しており、向きを有する場合が一般的である。
【０００３】
車載用ナビゲーション装置では、出発地(出発地ノード)及び目的地(目的地ノード)が入力又は決定されると、これらの地点を結ぶ最適経路(又は複数の経路からなる最適経路候補)が制御手段にて求められてユーザに提示される。また、車載用ナビゲーション装置では、車両情報取得手段によって逐次得られる位置情報に基づいて、車両付近の地図データが記録媒体から読み出される。そして、車両の現在位置と選択すべき道路とが明示された状態で、現在位置付近の地図が表示手段にて随時表示されることによって、最適経路に沿ってユーザが誘導される。
【０００４】
一般的な車載用ナビゲーション装置では、ダイクストラ法によって、最適経路が求められている。ダイクストラ法は、基本的なアルゴリズムが比較的単純であるために、制御手段として実装されるマイクロコンピュータ(以下、「マイコン」と称する)に過度の負担を掛けることがなく、経路探索が短時間で済む利点がある。しかしながら、その一方で、信頼性が低く、真に又は十分に適切な経路が求められない事態がかなりの頻度で生じてしまう。この問題を解決するために、近年、遺伝的アルゴリズムを用いて最適経路を探索する車載用ナビゲーション装置が幾つか提案されている(特許文献１乃至３参照)。
【０００５】
車載用ナビゲーション装置において、遺伝的アルゴリズムを用いた経路探索は、例えば以下のように行われる。まず、出発地から目的地に至る経路を染色体とする初期集団が準備される。遺伝的アルゴリズムでは、各染色体は、遺伝子の集団で構成される。車載用ナビゲーション装置では、通常、遺伝子としてリンク又はノードが用いられて、各経路は、リンク列又はノード列で表現される。
【０００６】
次に、各経路について算出された評価コスト(適応度)に基づいて選択処理が行われて、初期集団から２本の親経路が選択される。２本の親経路がランダムに選択されてもよいが、通常、評価コストが高い経路がより高い確率で選択されるように選択処理が行われる。評価コストとは、移動時間、移動費用、又は経路長さ等である。
【０００７】
次に、選択された親経路に対して遺伝子操作処理が、一般的には、交叉処理、さらには突然変異処理が行われて新たな経路が作成される。交叉処理は、染色体の一部、即ちリンク列又はノード列の一部を、選択された経路間で組み換えて新たな経路(子経路)を生成するものであり、突然変異処理は、生成された子経路のリンク列又はノード列の一部を適当なリンク列又はノード列に入れ換えるものである。このように生成された子経路は、初期集団に加えられる。そして、評価コストが低い２本の経路を初期集団から取り除く淘汰処理が行われる。以後、経路集団に対して、選択処理、遺伝子操作処理、及び淘汰処理が所定の回数だけ繰り返された後、評価コストが最も優れた経路が最適経路として特定される。
【特許文献１】特開平９−１７８５００号公報
【特許文献２】特開平１１−１１８５０１号公報
【特許文献３】特開２０００−１７２６６４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記のような遺伝的アルゴリズムを用いた経路探索では、以下に述べる問題が生じる。図７は、高速道路のインターチェンジ(ＩＣ)付近のノード及びリンクを示している。図においてノードは白丸で、リンクは矢印で示されている(以下同様)。なお、黒の矢印は高速道路、白の矢印は一般道路、灰色の矢印は連結路に対応している。
【０００９】
上記に述べた選択処理にて、経路Ｅ及びＦの２本の経路が選択されたケースを考える。経路Ｅは、高速道路を用いて目的地に向かう経路であって、このＩＣを通り過ぎる。経路Ｅは、リンク列｛Ｌe(1),・・・，Ｌe(i)，Ｌe(i+1)，Ｌe(i+2)，・・・，Ｌe(n)｝で表現される。経路Ｆは、（少なくともこのＩＣ付近では）一般道路を通って目的地に向かう経路であって、リンク列｛Ｌf(1),・・・，Ｌf(j)，Ｌf(j+1)，Ｌf(j+2)，・・・，Ｌf(m)｝で表現される。経路Ｅ及びＦに交叉処理を施して、新たな経路が生成されるためには、このＩＣにてこれら経路が交わっていること、言い換えると、このＩＣにてこれら経路に共通ノードがあることが必要とされる。
【００１０】
しかしながら、図７に示すような経路Ｅ及びＦが選択された場合、このＩＣにて経路Ｅ及びＦの共通ノードは存在しないことから、交叉処理の結果として、このＩＣにて高速道路を降りて一般道路に移行する経路｛Ｌe(1),・・・，Ｌe(i)，Ｌr(1)，Ｌf(j+2)，・・・，Ｌf(m)｝(Ｌr(1)は連結路を表すリンク)が生成されることはない。また、同様な理由から、このＩＣにて一般道路から高速道路に移行する経路｛Ｌf(1),・・・，Ｌf(j)，Ｌr(2)，Ｌe(j+2)，・・・，Ｌe(n)｝(Ｌr(2)は連結路を表すリンク)も生成されることはない。従って、このＩＣにて高速道路から一般道路に、又は一般道路から高速道路に移行することが最適経路に求められる場合に、従来の遺伝的アルゴリズムを用いた経路探索では、交叉処理が有効に機能し得えなかった。その結果、遺伝的アルゴリズムを用いても、最適経路として適切な経路が必ずしも求められない事態が生じていた。
【００１１】
同様な問題は、高架橋を含んだ交差路についても生じる。図８Ａは、このような交差路付近のノード及びリンクを示している。選択処理にて、例えば、経路Ｇ及び経路Ｈの２本の経路が選択されており、経路Ｇは高架橋上の基幹道路(黒色の矢印(リンク)で示す)を通って目的地に向かう経路であって、リンク列｛Ｌg(1),・・・，Ｌg(i)，Ｌg(i+1)，Ｌg(i+2)，・・・，Ｌg(n)｝で表現される。経路Ｈは、高架橋下の道路(白色の矢印で示す)を通って目的地に向かう経路であって、リンク列｛Ｌh(1),・・・，Ｌh(j)，Ｌh(j+1)，Ｌh(j+2)，・・・，Ｌh(m)｝で表現される。交差路付近にて経路Ｇ及びＨには共通のノード(白丸で示す)が存在しないことから、交叉処理の結果として、高架橋下の道路から連結路(灰色の矢印で示す)を通って基幹道路に移行する経路｛Ｌh(1),・・・，Ｌh(j)，Ｌr(3)，Ｌg(j+2)，・・・，Ｌg(n)｝(Ｌr(3)は連結路を表すリンク)が生成されることはない。
【００１２】
また、同様な問題は、本道と側道から構成される平行道路についても生じる。図８Ｂは、このような平行道路のノード及びリンクを示している。選択処理において、図示したノード付近にて本道(黒色の矢印(リンク)で示す)を通る経路Ｉと、側道(白色の矢印で示す)を通る経路Ｊとが選択された場合、交叉処理にて、連結路(灰色の矢印で示す)を通って本道から側道に移行する経路、又は側道から本道に移行する経路が生成されることはない。
【００１３】
本発明は、以上の問題を解決するものであり、あるノードが共通ノードでない場合でも、そのノード以降にて親経路の一部を組み換えて子経路を生成可能である遺伝的アルゴリズムを用いた経路探索装置及び方法を提供する。
【課題を解決するための手段】
【００１４】
本発明の経路探索装置は、出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索装置である。
【００１５】
本発明の経路探索装置は、前記交叉処理にて、前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、このノードを抽出された交叉可能ノード群に加え、共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、このノードを前記交叉可能ノード群に加える。
【００１６】
さらに、本発明の経路探索装置は、前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成し、前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成し、前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する。
【００１７】
本発明の経路探索方法は、出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索方法である。
【００１８】
本発明の経路探索方法は、前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、このノードを抽出された交叉可能ノード群に加える工程と、共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、このノードを前記交叉可能ノード群に加える工程とを含んでいる。
【００１９】
さらに、本発明の経路探索方法は、前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程と、前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程と、前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含んでいる。
【発明の効果】
【００２０】
本発明によれば、あるノードが共通ノードでなくとも、所定の条件を満たす場合には、そのノード以降にて、一方の親経路が、連結経路と、連結経路の終端から目的地に至る他方の親経路の一部分と組み換えられて子経路が生成される。従って、選択された親経路が、例えば、ＩＣにて交差しない場合であっても、交叉処理にて、ＩＣから一般道路に移行する子経路又は一般道路からＩＣに移行する子経路が生成されて、遺伝的アルゴリズムによる経路探索がより効率的に機能すする。
【００２１】
所定の条件は、共通ノードではない第１又は第２経路上のノードと、このノードを始端ノードとする第１又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含むのが好ましい。また、所定の条件は、第１又は第２連結経路の長さが所定の長さ以下であることを含むことが好ましい。これらによって、適切な第１及び第２連結経路が探索される。
【００２２】
また、経路集団は、ダイクストラ法を用いて準備するのが好ましく、第１連結経路及び前記第２連結経路は、ダイクストラ法を用いて探索されるのが好ましい。ダイクストラ法を、このように、遺伝的アルゴリズムと組み合わせることによって、遺伝的アルゴリズムを用いた経路探索を迅速化することが可能となる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明を車載用ナビゲーション装置に適用した実施例について説明する。図１は、本発明の実施例である車載用ナビゲーション装置(以下、「ナビゲーション装置」と称する)の概要を示すブロック図である。本実施例のナビゲーション装置は、車両の現在位置等を取得する車両情報取得手段と、記録媒体に記録された地図データを読み出す記録手段と、ナビゲーション画面や各種情報等を表示する表示手段と、ドライバーを誘導する音声を出力する音声出力手段と、各種キー等を含む操作手段と、これら手段に接続されて動作上必要な各種処理及び制御等を行う制御手段とを含んでいる。
【００２４】
車両情報取得手段は、ＧＰＳ受信部(1)と、ジャイロスコープ(3)と、ジャイロマイコン(5)等で構成される。ＧＰＳ受信部(1)は、ＧＰＳアンテナ(7)を介してＧＰＳ衛星から送られる電波を受信し、受信信号に基づいて車両の絶対位置を算出する。算出された車両の絶対位置(例えば、この位置は、緯度及び経度で与えられる)は、制御手段たる制御マイコン(9)に送られる。制御マイコン(9)は、図示を省略したＣＰＵ、ＲＡＭ及びＲＯＭ等で構成されている。ジャイロスコープ(3)は、車両の方位を得るために用いられており、ジャイロマイコン(5)は、ジャイロスコープ(3)から送られた信号に基づいて車両の方位を決定し、その情報を制御マイコン(9)に送る。また、ジャイロマイコン(5)には、車両に設けられた車速センサ(図示せず)から車速パルス信号が送られる。ジャイロマイコン(5)は、車速パルス信号に基づいて車両の速度や走行距離を決定し、それらを制御マイコン(9)に送る。制御マイコン(9)は、ジャイロマイコン(5)から送られる車両の方位及び走行距離情報から車両の相対位置を決定し、相対位置情報とＧＰＳ受信部(1)から送られる絶対位置情報とから走行軌跡を求めて、地図データ上の道路(リンク)と整合させる。
【００２５】
記録手段は、記録媒体(11)と、記録媒体(11)から情報を読み出して制御マイコン(9)に送るドライバ(13)等とで構成される。記録媒体(11)には、例えばＤＶＤ、ＣＤ−ＲＯＭやハードディスクが用いられており、地図データが記録されている。地図データには、形状情報(背景データ及び道路データ)、接続情報(道路ネットワークデータ)、及び属性情報(場所検索データ及びサービス検索データ)等が含まれている。接続情報は、地図上のノードとリンクに関する情報を含んでおり、経路探索に用いられる。各ノードに関する情報は、例えば、ノードＩＤ番号、座標、道路種別情報、及び隣接リンク情報で構成される。各リンクに関する情報は、例えば、リンクＩＤ番号、道路種別情報、規制情報、リンク長、隣接ノード情報、及び展開可能リンク番号等で構成される。
【００２６】
制御マイコン(9)は、処理に必要な情報を、ドライバ(13)を介して記録媒体(11)から適宜取得する。例えば、表示手段にナビゲーション画像を表示するナビゲーション動作を行っている際、ナビゲーション装置は、車両情報取得手段から得られた位置情報等に基づいて、その付近のノード、リンク及びその他の情報を取得する。制御マイコン(9)は、車両情報取得手段及び記録手段から得られた情報を処理して、ナビゲーション画像を作成するのに必要な指示を表示手段に送る。表示手段は、描画ＩＣ(15)、ＬＣＤＩ/Ｆ(17)及びＬＣＤ(19)等で構成されている。描画ＩＣ(15)は、車両の現在位置及び進行方向や各種道路及び施設等を表現するキャラクタデータと、住所や道路の名称等を表示するための文字データとを記憶したメモリを有しており、制御マイコン(9)からの指示に基づいてナビゲーション画像の画像データを作成する。描画ＩＣ(15)で作成された画像データはＬＣＤＩ/Ｆ(17)を介してＬＣＤ(19)に送られて、該ＬＣＤ(19)にナビゲーション画像が表示される。また、制御マイコン(9)は、ナビゲーション動作の際に、車両情報取得手段及び記録手段から得られた情報を処理して、音声でドライバーを誘導するための音声データを作成する。音声データは、デジタル形式で作成されて、音声出力手段に送られる。音声出力手段は、デジタル−アナログコンバータ(21)と、アンプ(23)と、スピーカ(25)等とで構成されており、制御マイコン(9)から送られた音声データは、デジタル−アナログコンバータ(21)でアナログ化されて、アンプ(23)で増幅された後に、スピーカ(25)から出力される。
【００２７】
操作手段は、ナビゲーション装置の筐体に設けられた各種操作キー(27)と、ＬＣＤ(19)上に配置されるタッチパネル(29)と、付属のリモートコントローラ(図示せず)と、このリモートコントローラから送られた赤外線信号を受光するリモコン受光部(31)と、これらからの入力を処理するキーマイコン(33)等とで構成される。ある操作キー(27)が押されると、キーマイコン(33)は、押された操作キー(27)を判別して、それに応じた動作コマンドを制御マイコン(9)に送る。また、キーマイコン(33)は、ＬＣＤ(19)に設定用画面が表示されている状態にて、タッチパネル(29)が押された領域を判別して、操作に対応した動作コマンドを制御マイコン(9)に送る。リモコン受光部(31)は、受光した赤外線信号を電気信号に変換し、さらには変換した電気信号を復調してキーマイコン(33)に送り、キーマイコン(33)は、送られた信号に基づいて特定した動作コマンドを制御マイコン(9)に送る。
【００２８】
上述した車両情報取得手段や記憶手段等に加えて、ナビゲーション装置には、道路交通情報を提供する情報システムや高速道路の自動料金徴収システム等のインフラストラクチャを利用する手段が設けられている。ナビゲーション装置は、ＶＩＣＳ(Vehicle Information Communication System)を利用して、渋滞情報、事故・工事情報及び速度規制情報等の道路交通情報を取得可能である。ＶＩＣＳチューナ(35)は、ＦＭ用アンテナ(37)を介して、道路交通情報が重畳されたＦＭ多重放送を受信し、ＲＦアンテナ(39)を介して、道路上に設けられた電波ビーコンから送られた、道路交通情報に関する２.５ＧＨｚのＲＦ信号を受信して復調する。また、ＶＩＣＳマイコン(41)には、道路上に設けられた光ビーコンから送られた、道路交通情報に関する赤外線信号を受光する光ビーコン受光部(43)が接続されており、光ビーコン受光部(43)は、受光した赤外線信号を電気信号に変換、さらには電気信号を復調する。ＶＩＣＳマイコン(41)は、ＶＩＣＳチューナ(35)や光ビーコン受光部(43)から送られる復調信号を処理して道路交通情報を得る。得られた道路交通情報は、制御マイコン(9)で処理されて、ＬＣＤ(19)に表示される。また、ナビゲーション動作中では、車両情報や地図データに加えて、ＶＩＣＳマイコン(41)から送られる道路交通情報にも基づいて、ナビゲーション画面が作成される。例えば、渋滞情報に基づいて、渋滞した道路がナビゲーション画面にて明示される。
【００２９】
さらに、ナビゲーション装置には、ＥＴＣ(Electronic Toll Collection System)を利用するためのＥＴＣ装置(45)が接続されている。ＥＴＣ装置(45)は、５.８ＧＨｚのＲＦ信号を送受信するためのＲＦアンテナと、変復調処理を行う送受信部と、ＥＴＣカードを読み書きするリーダライタと等で構成されている(何れも図示せず)。制御マイコン(9)は、例えば、ＥＴＣ装置(45)から送られた情報に基づいて、ＥＴＣゲートのレーンをスピーカ(25)の音声で案内したり、ＥＴＣゲートの拡大図をＬＣＤ(19)に表示する。
【００３０】
以下、本実施例のナビゲーション装置が行う経路探索動作について説明する。図２は、この経路探索動作の概要を示すフローチャートであって、この動作を記述したプロクラムは、制御マイコン(9)内のＲＯＭに格納されており、制御マイコン(9)内のＣＰＵにて実行される。操作手段を介して経路探索動作モードが選択されると、制御マイコン(9)からの指示により、出発地及び目的地の入力をドライバーに促す設定画面がＬＣＤ(19)に表示されて、それらの設定が行われる(Ｓ１)。なお、設定される出発地は、車両情報取得手段から得られた車両の現在位置でもよい。そして、制御マイコン(9)は、出発地及び目的地を含む所定の領域内のノード及びリンク情報を記録媒体(11)から読み出して、内蔵するＲＡＭに記憶する(Ｓ２)。以後の処理において、ＲＡＭに記憶されたノード及びリンク情報は適宜参照される。
【００３１】
ステップＳ２の後、制御マイコン(9)は、ダイクストラ法を用いて初期集団を生成する処理を行う(Ｓ３)。初期集団は、複数の経路からなる経路集団(遺伝子プール)であって、出発地のノード(又は出発地に最も近いノード。以下「出発地ノード」と称す)と、目的地のノード(又は目的地に最も近いノード。以下「目的地ノード」と称す)とを結ぶ複数の経路(例えば、２０本の経路)で構成されている。生成された経路集団は、ＲＡＭに記憶される。なお、ＤＦＳ法又はダイクストラ法以外のＢＦＳ法を用いて、初期集団が生成されてもよい。
【００３２】
ステップＳ３の後、経路集団から親経路を２本選択する処理が行われる(Ｓ４)。ステップＳ４では、任意の２本の親経路が選択されてもよいが、後述する評価コストが高い経路がより高い確率で親経路として選択されるのが好ましい。本実施例では、リンクを遺伝子としており、経路はリンク列で表現される。以後、選択された２本の親経路を経路Ａ｛Ｌa(1),・・・，Ｌa(n)｝と、経路Ｂ｛Ｌb(1),・・・，Ｌb(m)｝表記する。経路Ａは、出発地側から順番に、Ｌa(1)からＬa(n)までのｎ個のリンクで構成されている。経路Ｂは、出発地側から順番に、Ｌb(1)からＬb(m)までのｍ個のリンクで構成されている。また、以後、経路Ａ上のｎ＋１個のノードを、出発地側から順番に、Ｎa(0),・・・，Ｎa(n)(Ｎa(0)は出発地ノード、Ｎa(n)は目的地ノード)と表記する。また、経路Ｂ上のｍ＋１個のノードを、出発地側から順番に、Ｎb(0),・・・，Ｎb(m)(Ｎb(0)＝Ｎa(0) 、Ｎb(m)＝Ｎa(n))と表記する。リンクＬa(i)の始端ノードは、ノードＮa(i-1)となり、リンクＬa(i)の終端ノードは、ノードＮa(i)となる。
【００３３】
ステップＳ４の後、遺伝子操作処理、具体的には、選択された親経路に対して交叉処理が施されて、１又は２本の子経路が生成される(Ｓ５)。生成された経路は経路集団に加えられて、淘汰処理が行われる(Ｓ６)。淘汰処理では、経路集団を構成する経路について評価コストが比較されて、評価コストが最も低い１又は２本の経路が経路集団から取り除かれる。子経路が１本である場合１本の経路が、子経路が２本である場合２本の経路が取り除かれる。なお、経路集団に同一の経路が複数存在するケースがあり得るので、同一経路があるか否かの判定を行って、同一経路がない場合には、上述のように淘汰処理を行い、同一経路がある場合には、経路の重複分を経路集団から取り除くようにステップＳ６を構成してもよい。また、本実施例では、ステップＳ５において、交叉処理のみが行われるが、生成された子経路の一部のリンク列を入れ換える突然変異処理のような子経路を対象とする処理がさらに行われてもよい。本発明は、遺伝的アルゴリズムにおける交叉処理に関するものであって、本発明の効果が失われない限り、経路探索動作はどのように変更されてもよい。
【００３４】
本実施例では、ステップＳ６(必要に応じてステップＳ４も)において、経路の評価コストは、評価コスト＝Σ(所用時間×ドライバ時間単価)＋燃料単価×Σ消費燃料＋有料道路料金、として求められる。この式で、所用時間、ドライバ時間単価及び消費燃料は、リンクに応じて定められる値であり、Σは、経路を構成する全リンクについて和をとることを意味する。各リンクの所用時間は、所要時間＝(平均移動時間×道路種別係数×道幅係数×規制速度係数)＋１０秒×右折左折回数＋３０秒×信号数＋５秒×交差点数)×地域係数×バイパス係数、として算出される。平均移動時間、道路種別係数、規制速度係数、信号数等は各リンクについて地図データに含まれているか、地図レーダの情報に基づいて定められる。平均移動時間は、リンクを移動するのに要する平均時間であり、道路種別係数、道幅係数、規制速度係数、地域係数及びバイパス係数は、そのリンクの種々の特長に応じて設定される係数である。例えば、地域係数は、リンクが都会にある場合は０.９とされ、その他は１とされる。また、バイパス係数は、リンクがバイパスである又はバイパスの一部であるならば１.１とされ、その他は１とされる。ドライバ時間単価は、所用時間をコスト(価格)に換算するための値であり、出発地付近では高く、目的地付近では低く、中間では中程度に設定される。
【００３５】
各リンクに関する消費燃料は、消費燃料＝リンク長÷燃費×道路種別消費燃料係数＋５０ｍｌ×右折左折回数＋５０ｍｌ×信号数、として算出される。また、評価コストに関する上述の式にて、ドライバ時間単価とは、移動時間をコストに換算する値であり、有料道路料金とは、経路における高速道路等の通行料金である。
【００３６】
ステップＳ６の後、制御マイコン(9)は、終了条件が満たされているか否かを判断する(Ｓ７)。例えば、終了条件は、ステップＳ４乃至６の繰り返し回数が、所定回数(例えば、５０回)に至ったというものである。ステップＳ７にて、終了条件が満たされていないと判断された場合には、再度、制御マイコン(9)は、ステップＳ４乃至６の処理を行う。満たされていると判断された場合には、制御マイコン(9)は、経路探索結果をＬＣＤ(19)に表示する(Ｓ８)。ＬＣＤ(19)には、例えば、評価コストの最も高い経路、又は、評価コストが上位である複数の経路が表示される。
【００３７】
本発明は、一方の親経路のあるノードが共通ノードでなくとも、交叉処理(Ｓ５)にて、所定の条件を満たすならば、そのノード以降についてリンク列を部分的に組み換えて子経路を生成できることを特徴とする。以下、図３乃至５のフローチャートを参照して、本実施例の交叉処理を具体的に説明する。図３を参照すると、まず最初に変数ｇ及びフラグの初期化が行われる(Ｓ１１)。変数ｇは１に、フラグはオフにされる。なお、以下に言及する変数の値、フラグ及び処理結果等は、制御マイコン(9)内のＲＡＭに適宜記憶され、読み出される。次に、経路Ａ及びＢの両方に存在する共通ノードを抽出する処理が行われる(Ｓ１２)。抽出された共通ノードは、交叉可能ノードとして制御マイコン(9)内に記憶される。以後、抽出されたｋ個の交叉可能ノードを、Ｎ(1),・・・，Ｎ(k)と表記する。なお、この際、出発地及び目的地ノードは交叉可能ノードから除外される。さらに、経路Ａ及びＢにおいて最初の幾つかのリンクが共通する場合には、及び/又は、経路Ａ及びＢにおいて最後の幾つかのリンクが共通する場合には、このようなリンク上の共通ノードも交叉可能ノードから除外されるのが好ましい。ステップＳ１２にて抽出された交叉可能ノードが０個である場合もあり得るが、この場合でも図３乃至５に示す経路探索動作は、問題なく実行される。
【００３８】
ステップＳ１２の後、以後の処理にて経路Ａ上のノードを特定する変数ｉの値を設定する処理が行われる(Ｓ１３)。最初にステップＳ１３が行われる場合、ｉは１に設定される。ステップＳ１３は、後述するステップＳ１４からＳ２６までの処理を繰り返すループの始端となっており、後述するステップＳ１５は、このループの終端となっている。ステップＳ１３の後、ノードＮa(i)が共通ノードであるか否かが判断される(Ｓ１４)。ステップＳ１４にて、ノードＮa(i)が共通ノードであると判断された場合、ステップＳ１５にて、ノードＮa(i)が目的地ノードの１つ手前のノードであるか否か、即ち、ｉの値がｎ−１に等しいか否かが判断される(Ｓ１５)。ステップＳ１５にて、ｉの値はｎ−１と異なると判断された場合、処理はステップＳ１３に戻って、ｉの値がインクリメントされる。その後、ステップＳ１４以降の処理が再度行われる。
【００３９】
ステップＳ１４にて、ノードＮa(i)は共通ノードではないと判断された場合、以後の処理にて経路Ｂのノードを特定する変数ｊの値を設定する処理が行われる(Ｓ１６)。最初にステップＳ１６が行われる場合、ｊは１に初期化される。ステップＳ１６は、後述するステップＳ１７からＳ２４までの処理を繰り返すループの始端となっており、後述するステップＳ１８は、このループの終端となっている。ステップＳ１６の後、ノードＮb(j)が共通ノードであるか否かが判断される(Ｓ１７)。ステップＳ１７にて、ノードＮb(j)が共通ノードであると判断された場合、ステップＳ１８にて、ノードＮb(j)が目的地ノードの１つ手前のノードであるか否か、即ち、ｊの値がｍ−１に等しいか否かが判断される(Ｓ１８)。ステップＳ１８にて、ｊの値がｍ−１と異なると判断された場合、処理はステップＳ１６に戻って、ｊの値がインクリメントされる。その後、ステップＳ１７以降の処理が再度行われる。
【００４０】
ステップＳ１７にて、ノードＮb(j)は共通ノードではないと判断された場合、ノードＮa(i)とノードＮb(j)間の直線距離が、所定の距離Ｘ以下であるか否かが判断される(Ｓ１９)。ステップＳ１９にて、この直線距離が、所定の距離Ｘを超えていると判断された場合、ステップＳ１８以降の処理が行われる。ステップＳ１９にて、直線距離が所定の距離Ｘ以下であると判断された場合、ノードＮa(i)からノードＮb(j)への経路(以下、「連結経路」と称する)の探索が、タイクストラ法を用いて行われる(Ｓ２０)。なお、ＤＦＳ法又はダイクストラ法以外のＢＦＳ法が用いられてもよい。ステップＳ２０の後、経路探索が成功したか否かが判断される(Ｓ２１)。例えば、所定の時間、経路探索が行われても連結経路が得られない場合に、ステップＳ２１にて経路探索に失敗したと判断される。経路探索に失敗したと判断された場合、つまりノードＮa(i)からノードＮb(j)への連結経路が得られなかった場合、ステップＳ１８以降の処理が行われる。ステップＳ２０にて、ノードＮa(i)からノードＮb(j)への連結経路が得られた場合(ステップＳ２１にて経路探索に成功したと判断された場合)、この連結経路の長さがＸ＋α(αは所定の定数)以下であるか否かが判断される(Ｓ２２)。
【００４１】
ステップＳ２２にて、得られた連結経路の長さがＸ＋αを超えていると判断された場合、ステップＳ１８以降の処理が行われる。ステップＳ２０で求められた経路の長さがＸ＋α以下であると判断された場合、ノードＮa(i)は、交叉可能ノードＮ(k+g)として記憶されて、交叉可能ノード群に加えられる(Ｓ２３)。その後、探索された連結経路は、Ｒ(g) :｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝(ｏは正の整数。ｏ＝１ならば、Ｒ(g)は１つのリンクＬr(g)(1))として記憶されて、フラグがオンにされる(Ｓ２４)。
【００４２】
ステップＳ２４の後、ステップＳ１８が行われる。ノードＮb(1)からノードＮb(j-1)について、ステップＳ１７、Ｓ１９乃至２４が繰り返し行われると、ステップＳ１８にて、ｊの値はｍ−１と等しいと判断される。その場合、ステップＳ１８の後に、フラグがオンであるか否かが判断されて(Ｓ２５)、フラグがオンである場合には、変数ｇの値がインクリメントされて、フラグがオフに戻される(Ｓ２６)。ステップＳ２６の後、又は、ステップＳ２５にてフラグがオフである場合には、ステップＳ１５が行われる。
【００４３】
なお、ノードＮb(1)からノードＮb(j-1)について、ステップＳ１７、Ｓ１９乃至２４が繰り返し行われるので、経路Ａ上のあるノードＮa(i)について、連結される経路Ｂ上のノードが異なる複数の連結経路が探索されることが起こり得る。本実施例では、このような場合にステップＳ２４が繰り返して行われると、記録された連結経路Ｒ(g)が上書きされて、最終的により目的地に近い連結経路(連結される経路Ｂ上のノードが最も目的値に近い連結経路)が記録されるようになっている。なお、ステップＳ２４にて、既に記憶されている連結経路Ｒ(g)の長さと、新たに得られた連結経路の長さを比較して、後者の長さが前者の長さよりも短い場合に、上書きして後者を連結経路Ｒ(g)として記憶してもよい。
【００４４】
ノードＮa(1)からノードＮa(i-1)について、ステップＳ１４、Ｓ１６乃至Ｓ２６が繰り返し行われると、ステップＳ１５にて、ｉの値はｎ−１と等しいと判断される。そして、その後、図４に示す一連の処理が行われる。図４に示すステップＳ３１乃至４４の処理は、経路Ａと経路Ｂの立場が変わった点を除いて、図３に示したステップＳ１３以降の処理と基本的に同じものである。故に、図４に示すステップＳ３１乃至４４の処理に関する詳細な説明は省略する。例えば、ステップＳ３１はステップＳ１３に、ステップＳ３２はステップＳ１４に、ステップＳ３５はステップＳ１７に相当しており、ステップＳ３７はステップＳ１９に相当している。
【００４５】
ノードＮb(1)からノードＮb(j-1)について、ステップＳ３２、Ｓ３４乃至４４が行われると、ステップＳ３３にて、ｊの値はｍ−１と等しいと判断される。そして、その後、図５に示す一連の処理が行われる。まず、記憶されている交叉可能ノード群から、任意の交叉可能ノードＮ(w)が選択される(Ｓ６１)。ここで、ｗ＝１〜ｋ+ｇfであり、ｇfは、最終的なｇの値、つまり、上記の説明と、図３及び図４とから理解されるように、ステップＳ１２で抽出された交叉可能ノード群に対して、後に加えられた交叉可能ノードの全数に等しい。次に、選択した交叉可能ノードＮ(w)が経路Ａ上のノードであるか否かが判断される(Ｓ６２)。ステップＳ６２にて、交叉可能ノードＮ(w)が経路Ａ上にあると判断された場合、交叉可能ノードＮ(w)が経路Ｂ上のノードであるか否かが判断される(Ｓ６３)。ステップＳ６３にて、交叉可能ノードＮ(w)が経路Ｂ上にあると判断された場合、つまり、交叉可能ノードＮ(w)が経路Ａ及びＢの共通ノードである場合、この交叉可能ノードＮ(w)以降にて、経路Ａ及びＢのリンク列を部分的に相互に組み換える交叉処理が行われて、子経路Ｃ及びＤが生成される(Ｓ６４)。交叉可能ノードＮ(w)が経路Ａ上で出発地ノードから数えてｐ＋１番目に位置するノードＮa(p)であり、さらに、経路Ｂ上で出発地ノードから数えてｑ＋１番目に位置するノードＮb(q)であるとすると、ステップＳ６４で生成される子経路Ｃは、リンク列｛Ｌa(1),・・・，Ｌa(p),Ｌb(q+1),・・・，Ｌb(m)｝となり、子経路Ｄは、リンク列｛Ｌb(1),・・・，Ｌb(q),Ｌb(p+1),・・・，Ｌa(n)｝となる。ステップＳ６４の後、これら子経路Ｃ及びＤが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４６】
ステップＳ６１にて選択した交叉可能ノードＮ(w)が経路Ａ上のノードではないと、即ち、経路Ｂ上にのみ存在するノードであると、ステップＳ６２にて判断された場合、この交叉可能ノードＮ(w)以降にて、経路Ｂのリンク列を部分的に組み換える交叉処理が行われて、１本の子経路Ｄが生成される(Ｓ６６)。ステップＳ６６では、交叉可能ノードＮ(w)以降のリンク列は、ステップＳ４２で記憶された、この交叉可能ノードＮ(w)と経路Ａ上のノードを結ぶ連結経路Ｒ(g)のリンク列｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝と、経路Ａの一部であって、リンクＬr(g)(o)の終端ノードである経路Ａ上のノードから目的地ノードに至る経路のリンク列とを合成したものとなる。例えば、交叉可能ノードＮ(w)が、出発地ノードから数えて、経路Ｂにてｑ＋１番目に位置するノードであり、リンクＬr(g)(o)の終端ノードである経路Ａ上のノードが、出発地ノードから数えてｐ＋１番目に位置するノードであるとすると、子経路Ｄは、リンク列｛Ｌb(1),・・・，Ｌb(q),Ｌr(g)(1),・・・，Ｌr(g)(o),Ｌa(p+1),・・・，Ｌa(n)｝となる。ステップＳ６６の後、この子経路Ｄが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４７】
ステップＳ６１にて選択した交叉可能ノードＮ(w)が経路Ｂ上のノードではないと、即ち、経路Ａ上にのみ存在するノードであると、ステップＳ６３にて判断された場合、この交叉可能ノードＮ(w)以降にて、経路Ａのリンク列を部分的に組み換える交叉処理が行われて、１本の子経路Ｃが生成される(Ｓ６７)。ステップＳ６７では、交叉可能ノードＮ(w)以降のリンク列は、ステップＳ２４で記憶された、この交叉可能ノードＮ(w)と経路Ｂ上のノードとを繋ぐ連結経路Ｒ(g)のリンク列｛Ｌr(g)(1),・・・，Ｌr(g)(o)｝と、経路Ｂの一部であって、リンクＬr(g)(o)の終端ノードである経路Ｂ上のノードから目的地ノードに至る経路のリンク列とを合成したものとなる。交叉可能ノードＮ(w)が、経路Ａにて出発地ノードから数えてｐ＋１番目に位置するノードであり、リンクＬr(g)(o)の終端ノードである経路Ｂ上のノードが、出発地ノードから数えてｑ＋１番目に位置するノードであるとすると、子経路Ｃは、リンク列｛Ｌa(1),・・・，Ｌa(p),Ｌr(g)(1),・・・，Ｌr(g)(o),Ｌb(q+1),・・・，Ｌb(m)｝となる。ステップＳ６７の後、この子経路Ｃが経路集団に加えられて(Ｓ６５)、交叉処理は終了する。
【００４８】
図６は、本実施例の交叉処理を説明する概念図であり、図２に示すステップＳ４にて選択された親経路Ａ及びＢの一例を示している。本図では、これら経路は部分的に省略されて示されており、経路Ａを構成する各リンクは黒色の矢印で、 経路Ｂを構成する各リンクは白色の矢印で、ノードは白丸で示されている。図３に示すステップＳ１２では、共通ノードが抽出されて交叉可能ノードとして記憶される。図６に示す例では、ステップＳ１２が行われると、リンクＬa(2)とＬb(2)の終端ノードが交叉可能ノードＮ(1)として、リンクＬa(n-1)とＬb(m-1)の始端ノードが交叉可能ノードＮ(k)として記憶される(なお、交叉可能ノードＮ(1)とＮ(k)の間に位置するその他の共通ノードも記憶される)。
【００４９】
図３に示すステップＳ１３以降の処理は、共通ノードではない経路Ａ上のノードの各々について、所定の条件を満たした、該ノードから経路Ｂに接続する連結経路を探索して記憶するものである。また、そのような連結経路が探索されたノードは、交叉可能ノード群に加えられる。ステップＳ１６を始端とし、ステップＳ１８を終端とするループでは、ステップＳ１３で指定された共通ノードではない、経路Ａ上のある１つのノードについて、出発地及び目的地ノードを除く経路Ｂ上のノードの各々について、所定の条件を満たす連結経路を求める試みが行われる。例えば、ステップＳ１３にて、図６に示す経路Ａ上のノードＮa(p)が指定された場合、第１の条件は、連結経路の両端のノード間の直線距離が所定の距離Ｘ以下であることなので、ステップＳ１９にて、ステップＳ１７で指定された経路Ｂ上のノードがノードＮa(p)を中心とする半径Ｘの円内にあるか否かが判断される。図６に示す例では、経路Ｂ上のノードＮb(q)がこの円内に入っており、ステップＳ１７にてノードＮb(q)が指定された場合、ステップＳ１９の後に、ノードＮa(p)からノードＮb(q)への連結経路が探索される(Ｓ２０)。
【００５０】
第２の条件は、連結経路の長さが所定の長さ以下であることである。ステップＳ２０で得られた連結経路は、例えば、図６に示す円から大きくはみ出た経路である可能性があり、このような実質的に無意味な経路がこの条件を課すことで排除される。この条件は、ステップＳ２２にて判断される。所定の長さＸ＋αは、当然にＸよりも長く、例えば、αは、Ｘと同程度の大きさに設定される。連結経路が、この第２の条件を満たす場合、ノードＮa(p)は、交叉可能ノードとして記憶され(Ｓ２３)、連結経路はＲ(g)として記憶される(Ｓ２４)。図６では、記憶された連結経路Ｒ(g)を、灰色の矢印のリンクで示してある。
【００５１】
図４に示すステップＳ３１以降の処理は、ステップＳ１２で抽出された共通ノードではない経路Ｂ上のノードの各々について、上記と同様にして、上述の第１及び第２の条件を満たした、該ノードから経路Ａに接続する連結経路を求めて記憶するものである。また、そのような連結経路の始端となる経路Ｂ上のノードは、交叉可能ノード群に加えられる。
【００５２】
図６に示す例では、例えば、ステップＳ６１にて、図中に示すノードＮ(1)やノードＮ(k)のような共通ノードである交叉可能ノードが選択されると、ステップＳ６４にて、従来の交叉処理のようにリンク列の組換えが行われて２本の子経路が作成される。一方で、例えば、ステップＳ６１にて、図６中に示すノードＮa(p)が選択されると、上述したように、経路Ａのように出発地ノードからノードＮa(p)に至り、その後、連結経路Ｒ(g)を通って、経路ＢのようにノードＮb(q)から目的地ノードに至る１本の子経路Ｃが生成される。
【００５３】
本実施例では、各経路は、先に示したようにリンクを遺伝子としたリンク列で表現されているが、ノードを遺伝子としてノード列で表現されていてもよい。また、本発明を車載用ナビゲーション装置に適用した実施例を取り上げて本発明を説明したが、本発明は、それ以外の経路探索装置、例えば、荷物等の輸送経路を探索する装置や巡回経路を探索する装置に用いることができる。
【００５４】
上記実施例の説明は、本発明を説明するためのものであって、特許請求の範囲に記載の発明を限定し、或は範囲を減縮する様に解すべきではない。本発明の各部構成は上記実施例に限らず、特許請求の範囲に記載の技術的範囲内で種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施例である車載用ナビゲーション装置の概要を示すブロック図である。
【図２】本発明の本実施例のナビゲーション装置が行う経路探索動作の概要を示すフローチャートである。
【図３】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図４】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図５】本発明の実施例のナビゲーション装置が行う交叉処理を示すフローチャートである。
【図６】本発明の実施例のナビゲーション装置が行う交叉処理を説明する概念図である。
【図７】高速道路のインターチェンジ付近のノード及びリンクを示す説明図である。
【図８】図８Ａは、交差路付近のノード及びリンクを示す説明図、図８Ｂは、平行道路のノード及びリンクを示す説明図である。
【符号の説明】
【００５６】
(1) ＧＰＳ受信部
(3) ジャイロスコープ
(5) ジャイロマイコン
(9) 制御マイコン
(11) 記録媒体
(19) ＬＣＤ
(25) スピーカ
(27) キー
【特許請求の範囲】
【請求項１】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索装置であって、
前記交叉処理にて、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加え、
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成し、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成し、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する経路探索装置。
【請求項２】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１に記載の経路探索装置。
【請求項３】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項１又は請求項２に記載の経路探索装置。
【請求項４】
前記経路集団の初期集団は、ダイクストラ法を用いて準備される、請求項１乃至３の何れかに記載の経路探索装置。
【請求項５】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項１乃至４の何れかに記載の経路探索装置。
【請求項６】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路方法であって、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加える工程と、
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含む経路探索方法。
【請求項７】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項６に記載の経路探索方法。
【請求項８】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項６又は請求項７に記載の経路探索方法。
【請求項９】
前記経路集団の初期集団を、ダイクストラ法を用いて準備する工程を含む、請求項６乃至８の何れかに記載の経路探索方法。
【請求項１０】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項６乃至９の何れかに記載の経路探索方法。
【特許請求の範囲】
【請求項１】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施すことを繰り返す遺伝的アルゴリズムを用いた経路探索装置であって、
前記交叉処理にて、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する経路探索装置。
【請求項２】
前記所定の条件は、共通ノードではない前記第１経路上のノードと、このノードを始端ノードとする第１連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１に記載の経路探索装置。
【請求項３】
第１連結経路は、ダイクストラ法を用いて探索される、請求項１又は請求項２に記載の経路探索装置。
【請求項４】
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する、請求項１に記載の経路探索装置。
【請求項５】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項４に記載の経路探索装置。
【請求項６】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項４又は請求項５に記載の経路探索装置。
【請求項７】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項４乃至６の何れかに記載の経路探索装置。
【請求項８】
前記経路集団の初期集団は、ダイクストラ法を用いて準備される、請求項１乃至７の何れかに記載の経路探索装置。
【請求項９】
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記第１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する、請求項１乃至８の何れかに記載の経路探索装置。
【請求項１０】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施すことを繰り返す遺伝的アルゴリズムを用いた経路方法であって、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程とを含む経路探索方法。
【請求項１１】
前記所定の条件は、共通ノードではない前記第１経路と、このノードを始端ノードとする第１連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１０に記載の経路探索方法。
【請求項１２】
前記所定の条件は、第１連結経路の長さが所定の長さ以下であることを含む、請求項１１又は請求項１２に記載の経路探索方法。
【請求項１３】
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含む、請求項１０に記載の経路探索方法。
【請求項１４】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１３に記載の経路探索方法。
【請求項１５】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項１３又は請求項１４に記載の経路探索方法。
【請求項１６】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項１３乃至１５の何れかに記載の経路探索方法。
【請求項１７】
前記経路集団の初期集団を、ダイクストラ法を用いて準備する工程を含む、請求項１０乃至１６の何れかに記載の経路探索方法。
【請求項１８】
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記第１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程を含む、請求項１０乃至１７の何れかに記載の経路探索方法。
【請求項１】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路探索装置であって、
前記交叉処理にて、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加え、
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成し、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成し、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する経路探索装置。
【請求項２】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１に記載の経路探索装置。
【請求項３】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項１又は請求項２に記載の経路探索装置。
【請求項４】
前記経路集団の初期集団は、ダイクストラ法を用いて準備される、請求項１乃至３の何れかに記載の経路探索装置。
【請求項５】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項１乃至４の何れかに記載の経路探索装置。
【請求項６】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施して、１又は２本の子経路を生成することを繰り返す遺伝的アルゴリズムを用いた経路方法であって、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加える工程と、
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含む経路探索方法。
【請求項７】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項６に記載の経路探索方法。
【請求項８】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項６又は請求項７に記載の経路探索方法。
【請求項９】
前記経路集団の初期集団を、ダイクストラ法を用いて準備する工程を含む、請求項６乃至８の何れかに記載の経路探索方法。
【請求項１０】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項６乃至９の何れかに記載の経路探索方法。
【特許請求の範囲】
【請求項１】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施すことを繰り返す遺伝的アルゴリズムを用いた経路探索装置であって、
前記交叉処理にて、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出し、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する経路探索装置。
【請求項２】
前記所定の条件は、共通ノードではない前記第１経路上のノードと、このノードを始端ノードとする第１連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１に記載の経路探索装置。
【請求項３】
第１連結経路は、ダイクストラ法を用いて探索される、請求項１又は請求項２に記載の経路探索装置。
【請求項４】
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加え、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する、請求項１に記載の経路探索装置。
【請求項５】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項４に記載の経路探索装置。
【請求項６】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項４又は請求項５に記載の経路探索装置。
【請求項７】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項４乃至６の何れかに記載の経路探索装置。
【請求項８】
前記経路集団の初期集団は、ダイクストラ法を用いて準備される、請求項１乃至７の何れかに記載の経路探索装置。
【請求項９】
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記第１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する、請求項１乃至８の何れかに記載の経路探索装置。
【請求項１０】
出発地から目的地に至る複数の経路で構成される経路集団から第１経路及び第２経路を選択し、前記第１経路及び前記第２経路に対して交叉処理を施すことを繰り返す遺伝的アルゴリズムを用いた経路方法であって、
前記第１経路及び前記第２経路が共有する共通ノードを交叉可能ノードとして抽出する工程と、
共通ノードではない前記第１経路上のノードから前記第２経路に繋がる所定の条件を満たす第１連結経路が探索された場合に、この第１経路上のノードを、抽出された交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第１経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第１連結経路と、前記第２経路の一部であって、この第１連結経路の終端ノードである前記第２経路上のノードから前記目的地に至る経路とで、前記第１経路を部分的に組み換えて１本の子経路を生成する工程とを含む経路探索方法。
【請求項１１】
前記所定の条件は、共通ノードではない前記第１経路と、このノードを始端ノードとする第１連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１０に記載の経路探索方法。
【請求項１２】
前記所定の条件は、第１連結経路の長さが所定の長さ以下であることを含む、請求項１１又は請求項１２に記載の経路探索方法。
【請求項１３】
共通ノードではない前記第２経路上のノードから前記第１経路に繋がる前記所定の条件を満たす第２連結経路が探索された場合に、この第２経路上のノードを前記交叉可能ノード群に加える工程と、
前記交叉可能ノード群から選択された交叉可能ノードが、前記第２経路上のみに存在する場合、選択された交叉可能ノード以降にて、この交叉可能ノードを始端ノードとする第２連結経路と、前記第１経路の一部であって、この第２連結経路の終端ノードである前記第１経路上のノードから前記目的地に至る経路とで、前記第２経路を部分的に組み換えて１本の子経路を生成する工程とを含む、請求項１０に記載の経路探索方法。
【請求項１４】
前記所定の条件は、共通ノードではない前記第１経路又は前記第２経路上のノードと、このノードを始端ノードとする第１連結経路又は第２連結経路の終端ノードとの間の距離が、所定の距離以下であることを含む、請求項１３に記載の経路探索方法。
【請求項１５】
前記所定の条件は、第１連結経路又は第２連結経路の長さが所定の長さ以下であることを含む、請求項１３又は請求項１４に記載の経路探索方法。
【請求項１６】
第１連結経路及び第２連結経路は、ダイクストラ法を用いて探索される、請求項１３乃至１５の何れかに記載の経路探索方法。
【請求項１７】
前記経路集団の初期集団を、ダイクストラ法を用いて準備する工程を含む、請求項１０乃至１６の何れかに記載の経路探索方法。
【請求項１８】
前記交叉可能ノード群から選択された交叉可能ノードが、共通ノードである場合、選択された交叉可能ノード以降にて前記第１経路及び前記第２経路を部分的に相互に組み換えて２本の子経路を生成する工程を含む、請求項１０乃至１７の何れかに記載の経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００６−１９４６０３（Ｐ２００６−１９４６０３Ａ）
【公開日】平成１８年７月２７日（２００６．７．２７）
【国際特許分類】
【出願番号】特願２００５−３６９７（Ｐ２００５−３６９７）
【出願日】平成１７年１月１１日（２００５．１．１１）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
【公開日】平成１８年７月２７日（２００６．７．２７）
【国際特許分類】
【出願日】平成１７年１月１１日（２００５．１．１１）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
[ Back to top ]