巡回経路探索機能を有するナビゲーションシステムおよび経路探索サーバならびに巡回経路探索方法
【課題】巡回すべき複数の地点に順序および／または時間的な制約がある場合に、当該制約を満足し得る巡回経路を探索できるようにする。
【解決手段】巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する操作・入力手段１７０と、２地点間の経路を探索する２点間経路探索手段１５３と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段１５０と、を備え、２地点間経路探索手段１５３は、巡回対象の２地点間全ての最短経路を探索して記憶し、巡回経路探索手段は１５０、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【解決手段】巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する操作・入力手段１７０と、２地点間の経路を探索する２点間経路探索手段１５３と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段１５０と、を備え、２地点間経路探索手段１５３は、巡回対象の２地点間全ての最短経路を探索して記憶し、巡回経路探索手段は１５０、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望の地点から所望の地点までの最適経路を探索して案内するナビゲーションシステムにし、予め定められた複数の地点を経由して巡回するための効率的な経路を探索する巡回経路探索機能を有するナビゲーションシステムおよび経路探索サーバに関するものであり、特に、巡回する地点に順序的あるいは時間的な制約条件がある場合に、当該制約条件を加味した効率的な巡回経路を探索するナビゲーションシステムおよび経路探索サーバならびに巡回経路探索方法に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られている。
このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置（以下、カーナビという）、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
上記カーナビは、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ：全地球測位システム）を利用したものであり、地球上を周回している複数のＧＰＳ衛星から送信されるＧＰＳ信号をＧＰＳアンテナで受信し、該ＧＰＳ信号に含まれる衛星位置や時計情報等を解析して位置の特定化を行うものである。該複数のＧＰＳ衛星の個数は少なくとも４個以上必要である。ＧＰＳの単独測位精度は一般的に１０ｍ強であるが、ＤＧＰＳ（Ｄｉｆｆｅｒｅｎｔｉａｌ ＧＰＳ：ディファレンシャルＧＰＳ）を採用することにより５ｍ以下に向上する。特に、従来は一部の携帯電話にしか搭載されていない測位ユニット、例えば、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信して測位するＧＰＳ受信機などが、第三世代と称される携帯電話では全ての機種に搭載されるような趨勢にある。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を経路探索サーバに送り、経路探索サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
経路探索サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、経路探索サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
ところで、経路探索において所望の２地点間の最適経路を探索する場合の他、所望の出発地から目的地までの間に所定の複数の地点を経由地として巡回する経路を探索する巡回経路探索が必要になる場合がある。このような経路探索は、例えば、物品の配送作業やセールスマンが複数の顧客場所を巡回する作業において必要になる。このような経路探索を巡回経路探索という。
【０００７】
巡回経路探索は、ｎ個の頂点を持つ完全グラフＧ（Ｖ、Ｅ）が与えられたとき、du,vを辺 (u, v) ∈Eのコストとすると、ある頂点s ∈Vから出発し、他の頂点を全て一度ずつ訪問して、最後に目的地eへ到達する経路を求めることを目的としている。ここで、一般的な配送などの業務の効率を考えた場合、なるべく巡回する経路の総コストが小さくなることが望まれる。この巡回経路を探索する課題は、ＮＰ困難な問題として知られている。
【０００８】
ＮＰ困難な問題とは、アルゴリズムの時間複雑度が指数時間となる問題、つまり、その問題を解くためのアルゴリズムにおいて必要なステップ数に関する漸近的な限界がO(cn)（ただし、cは1より大きい実数、nは問題の規模）となるものをいう。
たとえば、出発地と目的地を含まない巡回地点数がnの場合、最適な巡回経路を求めるための巡回経路探索回数は、n！となる。つまり、１０地点を巡回する場合の探索回数は、（１０×９×８×７×６×５×４×３×２×１）＝３６２８８０回となる。
ちなみに出発地を巡回地数に含め、かつ出発地に戻ってくる場合の巡回経路探索回数は（ｎ−１）！／２となる。
【０００９】
図１５は、１０ＴＦｌｏｐｓ（１秒間に１０13回浮動小数点演算が可能）のスーパーコンピュータを用いて上記のような巡回経路探索を、巡回数を代えて行った場合の各巡回数に対する巡回経路総数と計算時間を示す。１０ＴＦｌｏｐｓのスーパーコンピュータは、例えば、Pentium4（登録商標名）-1.8ＧＨｚのパソコン５０００台分程度の演算能力を持つものである。
【００１０】
図１５に示したように、巡回経路探索は、巡回地点が多くなると現在の一般的な演算処理装置で総当り演算を行うと膨大な演算が必要となり現実的には困難であるという問題点があるため、一般的には「遺伝アルゴリズム」と言われるアルゴリズムなどを用いて近似解を求めることが行われる。
【００１１】
例えば、下記の特許文献２（特開２０００−１７２６６４号公報）、特許文献３（特開平８−２０２６７５号公報）に、遺伝アルゴリズムを用いた巡回経路探索の技術が開示されている。
【００１２】
遺伝アルゴリズムは、生物の進化過程（交叉、突然変異等）をモデルとして、確率的に解を探索しようとする手法である。まずここで遺伝アルゴリズムについて説明する。遺伝アルゴリズムについて、例えば、下記の非特許文献１（ David E. Goldの「Genetic Algorithms in Search, Optimization and Machine Learning」(Addison Wesley社）に詳細が開示されている。
【００１３】
遺伝アルゴリズムでは、入力値として、ｘ個のビット列Ｂ＝(Ｂ1,Ｂ2,…,ＢＸ)、（あるいは省略して単に、Ｂ1Ｂ2…ＢＸとも記す）の集合Ｐが与えられる。集合Ｐの元（ｘ個のビット列）の個数をｎとし、各元を遺伝子、集合Ｐを個体群と呼ぶ。集合Ｐの各元は、与えられた問題の解をそれぞれ表現しており、遺伝アルゴリズムでは、生物の進化過程に倣った繰り返し処理を集合Ｐに加え、最適解を得ようとする。
【００１４】
遺伝アルゴリズムにおける処理の概要は次のようである。まず、ランダムに生成した遺伝子の集合として個体群を構成する。これを初期個体群と呼ぶ。次に、問題に応じて与えられた評価尺度（評価関数）にしたがって、個体群中の各遺伝子において解としての良さを評価し、その結果を遺伝子ごとに評価値として表す。そして、求めた評価値にしたがって、評価の低い遺伝子を減らし、その分、評価の良い遺伝子を増やす。その結果、評価の良い遺伝子ほど個体群Ｐに占める割合が高くなる。このような現象を「淘汰」と呼ぶ。この遺伝子の淘汰の処理は下記のようにして行われる。
【００１５】
まず、ランダムに生成された個体群から２つの遺伝子を、例えばランク方式やルーレット方式などの方法により選択し、それらの遺伝子を成すビット列の一部を交換する。この操作を「交叉」と呼ぶ。この交叉は、予め設定された交叉率により繰り返す回数が決定される。交叉によって新しく生成される遺伝子の数は、この交叉率に遺伝子数ｎを乗じた数となる。続いて、通常低い確率で設定される突然変異率にしたがい交叉によって得られた遺伝子を少し変更する。この操作を「突然変異」と呼ぶ。突然変異の方法としては、例えば遺伝子のビット列の一部をビット反転するなどの方法が知られている。
【００１６】
交叉・突然変異などの操作が完了したら、個体群中の各遺伝子において解としての良さを評価し、その評価結果にしたがい次の個体群を生成する。新たな個体群は、上述の操作によって作られた個体群と以前の個体群において、良い評価値を持つ遺伝子を遺伝子数ｎ分だけ抽出することによって生成される。この１回の淘汰、すなわち交叉・突然変異及び新たな個体群の生成の１回のサイクルが「世代」に相当する。このような上述の処理を繰り返すことで個体群の世代が進み、個体群の各遺伝子が淘汰されることで、個体群内の各遺伝子は、与えられた問題の最適解あるいは準最適解に達する。
【００１７】
上記の遺伝アルゴリズムを複数の地点を巡回する経路探索に用いる場合、１つの遺伝子は出発地、目的地を含んだ１つの巡回経路となる。例えば、出発地から全ての巡回地点を１度だけ通り目的地に至る巡回経路を探索する場合、まず出発地から各巡回地点を通り目的地に至る経路をランダムに複数作成する。これらの複数の遺伝子は個体群として保存され、集合Ｐ０が形成される。集合Ｐ０における各遺伝子の評価値は、設定した各地点間の経路コスト（時間および／または距離）の総和になる。
【００１８】
次に、集合Ｐ０から選択した２つの遺伝子から新しい遺伝子を生成し、その遺伝子の評価値を求める。例えば、ルーレット方式で新しい集合Ｐ１を作成する場合は、良い評価値を持つ遺伝子ほど高い確率で集合Ｐ０から選択される。つまり、良い評価値を持つ遺伝子ほど新しい遺伝子を生成するための種となりやすいということである。ここで選択された２つの遺伝子（巡回経路）において巡回順の一部を入れ換えて新たな遺伝子を作成し、かつ低い確率で突然変異を行い、その評価値を求める。この新しい遺伝子の評価値が、集合Ｐ０における最も評価値が悪い遺伝子より良い評価値を持っていれば、この遺伝子を入れ換える。集合Ｐ１は、このような操作を１世代分行うことによって得られる。この処理を繰り返して世代交代を行い、世代交代が予め設定した所定の回数に達するか、評価値が収束すれば処理を終了し、最後に得られた集合ＰＮにおける最良の評価値を持つ遺伝子（巡回経路）が最適解または準最適解となる。
【００１９】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−１７２６６４公報
【特許文献３】特開平８−２０２６７５号公報
【非特許文献１】David E. Gold著、「Genetic Algorithms in Search, Optimization and Machine Learning」(Addison Wesley社 １９８９年発行)
【発明の開示】
【発明が解決しようとする課題】
【００２０】
一般的に巡回経路探索は、物品の配送や送迎の業務を効率化することを目的としているため、必ずしも最適解が必要というわけでない。つまり、準最適解でも十分有用であるということである。一般的な業務においては、最適な巡回経路を求めなくとも人間が考える経路よりも良い結果を導き出すことができれば良い。あるいは、巡回経路探索装置を使用することによって人間が経路を考えるという労力を少なくするができるため、これだけでも業務の効率化を行うことが可能である。これらのことも、巡回経路探索に近似解法が適用される1つの要因となっている。
【００２１】
巡回経路を求める演算は非常に計算量が多く困難を極めるため、人間の勘に頼るか、あるいは現在地を中心に周回するだけの経路を求めることで妥協する例も見られる。また、単純な巡回経路探索は、なるべく短い巡回経路を求めることが目的となっており実際の利用状況にそぐわない場合がある。
たとえば、
１）巡回地点に順番の優先条件がある場合
２）巡回地点に立ち寄る時刻条件がある場合
３）巡回地点に順番の優先条件と立ち寄る時刻条件がある場合
である。
【００２２】
物品の集荷や配送における経路決定においては巡回する地点の間に順序の制約（優先条件）がある。つまり物品を配送する場合、集荷と配達があるので、巡回経路を探索する場合には集荷と配達の順番を満たさなければならない。そのため上記遺伝アルゴリズムを適用した単純な巡回経路探索では満足できる結果が得られないという問題点があった。このような問題点は特開２００５−２６３４４７号公報においても課題として開示されている。
【００２３】
別の例を挙げると、過疎地において１台の車両で複数の住民の移動の希望を同時に満たすために乗り合いバスを運行する場合が該当する。それぞれの住民の乗車希望位置と下車希望位置が巡回地点になるが、乗車→下車の順番が条件となるので、純粋な巡回経路探索では解が求められない。（乗車と下車の順番が逆になるとその住民は利用できない）。
このようなケースにおいては、巡回する必要のある地点が１０地点とすると、巡回地 Ｒ∈｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｉ，ｊ}のとき、地点ｃはａより後、あるいは地点ｄ，ｃは地点ｈ，ｉ，ｊより後に巡回するというような条件を同時に満足する巡回経路を導き出すことが求められる。
【００２４】
巡回地点に時間的制約（優先条件）があるケースとは、例えば、巡回地点がある決まった時間にしか立ち入ることができないビル内にあるようなケースである。物品の配送の例でいえば、立ち入りの時間が限られるビル内に設置された自動販売機に商品を配送するようなケースである。
つまり、このような経路探索においては、出発地の出発時刻あるいは到着地の到着時刻を基準とする巡回地点の到着希望時刻などの条件を満たす巡回経路を導き出すことが求められるのである。
【００２５】
また、上記のような順序の制約と時間の制約が同時に存在する場合もある。このようなケースは、例えば、上記の過疎地における乗合バス運行の巡回経路探索において、過疎地の住民が乗車希望位置と下車希望位置と、乗車または下車の希望時刻まで条件設定できる巡回経路探索というテーマにも発展するものである。
【００２６】
本願の発明者は上記のような問題点を解消すべく種々検討を重ねた結果、巡回対象の地点の制約条件を入力する手段を設け、巡回対象の全ての２地点間の最短経路を探索し記憶しておき、順序探索手段は遺伝的アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和だけでなく、巡回対象の地点の制約条件に対する評価値を加味して算出して、この評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めるようになせば上記問題点を解消し得ることに想到し本発明を完成するに至ったものである。
【００２７】
すなわち、本発明は上記の問題点を解消することを目的とし、巡回すべき複数の地点に順序および／または時間的な制約がある場合に、当該制約を満足し得る巡回経路を探索できるようにしたナビゲーションシステム、経路探索サーバを提供することを目的とするものである。
【課題を解決するための手段】
【００２８】
前記課題を解決するために、本願の請求項１にかかる発明は、
複数の地点を巡回する巡回経路探索機能を有するナビゲーションシステムであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする。
【００２９】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする。
【００３０】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする。
【００３１】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする。
【００３２】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする。
【００３３】
また、請求項６にかかる発明は、
複数の地点を巡回する巡回経路探索機能を有する経路探索サーバであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする。
【００３４】
本願の請求項７にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする。
【００３５】
本願の請求項８にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする。
【００３６】
本願の請求項９にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする。
【００３７】
本願の請求項１０にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする。
【００３８】
また、本願の請求項１１にかかる発明は、
複数の地点を巡回する巡回経路探索方法であって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段が、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶するステップと、
前記巡回経路探索手段が、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出するステップと、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えるステップと、を含み巡回経路探索を進めることを特徴とする。
【００３９】
また、本願の請求項１２にかかる発明は、請求項１１にかかる巡回経路探索方法において、
前記２地点間経路探索手段が最短経路を探索してその最適経路および経路コストを記憶するステップは、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する処理を含むことを特徴とする。
【発明の効果】
【００４０】
請求項１にかかる発明においては、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【００４１】
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４２】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回対象の地点の制約条件は、当該地点の巡回順序の優先度である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に順序的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４３】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点に時間的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４４】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足し、かつ、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮した効率的な巡回経路を探索して提供できるようになる。
【００４５】
また、請求項５にかかる発明においてはき、請求項１にかかるナビゲーションシステムにおいて、記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する。
このような構成によれば、都市部のように一方通行路が多い場合、あるいは方向によって著しくコストが異なる経路が存在する場合においても効率のよい巡回経路を探索することができるようになる。
【００４６】
本願の請求項６〜請求項１０にかかる発明においては、それぞれ請求項１〜請求項５にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項１１、請求項１２にかかる発明においては、それぞれ請求項６、請求項１０にかかる経路探索サーバにおける巡回経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００４８】
本発明の実施例にかかるナビゲーションシステムは、図１に示すように経路探索サーバ１０を備えて構成されている。経路探索サーバ１０は図示しない端末装置から経路探索要求を受信し、出発地から目的地までの最適経路を探索し、要求元の端末装置に配信する。
【００４９】
経路探索サーバ１０は、制御手段１１０、通信手段１２０、出力・配信手段１３０、経路探索手段１４０、巡回経路探索手段１５０、前処理手段１５１、２点間経路探索手段１５３、ＧＡ処理手段１５５、表示手段１６０、操作・入力手段１７０、地図データ１８０、道路ネットワークデータベース１９０、ガイダンスデータベース２００などを備えて構成されている。
【００５０】
制御手段１１０は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段１２０はネットワークを介して端末装置や他のサーバと通信するためのものである。出力・配信手段１３０は、経路探索結果を出力し、あるいは、端末装置に配信するためのものであり、経路データ、ガイダンスデータを端末装置に配信するためのデータに編集する。操作・入力手段１７０は経路探索サーバ１０に所望の入力、操作を行うためのものであり、表示手段１６０は液晶表示ユニットなどから構成され、所定の入力画面を表示する。
【００５１】
地図データ１８０には端末装置に提供する地図情報が蓄積されており、道路ネットワークデータベース１９０には地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）などがデータベースとして蓄積されている。ガイダンスデータベース２００には、交差点などにおける進行方向案内のための音声データや案内表示画像データが蓄積されている。
【００５２】
経路探索手段１４０は道路ネットワークデータベース１９０を参照して通常の経路探索を行う。巡回経路探索手段１５０は本実施例における巡回経路の探索を行うものである。巡回経路探索手段１５０は、前処理手段１５１、２点間経路探索手段１５３、ＧＡ処理手段１５５を備えて構成されている。これらの詳細については後述する。
【００５３】
本実施例においては、巡回経路探索のモデルを、例えば、僻地における荷物の集配の例で説明する。僻地では単位面積あたりの配送数が少ないので、１台の車両で集荷と配達を行うと効率が良い。また単位面積あたりの配送数が少ないということは、１配送あたりの走行距離も長くなるので、収益面でも出来るだけ効率の良い配送をしないと事業として成り立たない。
【００５４】
図２は、経路探索サーバ１０において巡回経路探索を実施する際の端末装置における巡回地点の入力画面である。実施に当たってはそれぞれの業態により最適なユーザインタフェース（ＵＩ）にカスタマイズされるべきであるが、機能のみを簡潔に説明する。この実施例では、出発地はこの配送業者の営業所、また最終目的地は出発地に戻るものとして登録済みである。また、経路探索サーバ１０を本実施例の経路探索エンジンをインストールしたパーソナルコンピュータに置き換えることもできる。
【００５５】
ある日の集配計画を立てるために、図２に示す入力画面からまず巡回地点の入力を行う。巡回地点は、住所、店舗／施設名、電話番号などを選択してフリーワードで入力可能である（選択しなくても検索機能により検索して入力することも可能である）。その巡回地点に立ち寄る時刻条件があれば、時刻指定から選択する。デフォルトは、「なし」であるが、プルダウンメニューによって、
11：00〜13：00
13：00〜15：00
15：00〜17：00
...
など時間の制約条件を指定することが可能である。
荷物の集荷から配達をまで行う場合には、左側の欄に集荷地点、右側の欄に配達先を入力することで、順序条件を指定する。
【００５６】
地点を確認する場合は、地図ボタンを押すことで地図上の位置を確認できる。また地図上で修正も可能である。誤入力した場合は、削除ボタンで、その行をクリアすることもできる。さらに巡回地点がある場合は、次の行に順次入力する。行が足りなくなったら、追加ボタンを押して、さらに入力行を増やせるようになっている。なお、巡回経路を求めるので、オペレータは地点を順次入力して行くだけでよい（入力の順番を意識する必要は無い）。
【００５７】
入力が終わったところで、検索ボタンを押すと、巡回経路探索の処理に移る。巡回経路探索の処理は大きく分けて図３のフローチャートに示す手順で進行する。すなわち、ステップＳ１１の処理において前処理を行った後、ステップＳ１２の処理において巡回地点の各２地点間の全ての組み合わせの最適経路探索を行う。（なお、２地点間の経路に一方通行路などが含まれない場合は２地点間の順序による経路コストは考慮しなくても良いが、都市部のように一方通行路が多い場合、あるいは方向によって著しくコストが異なる経路が存在する場合は双方向の経路を探索するのが良い）一度最適経路探索を行って経路コストを記憶しておけば、巡回経路の探索では経路コストのみを扱えばよい。
【００５８】
このため、ステップＳ１３の処理において探索した全ての経路のコストを保存する。次いでステップＳ１４の処理において巡回経路探索を行い、ステップＳ１５の処理において結果を出力する。以下に各処理を更に詳細に説明する。
【００５９】
［前処理］
まず、前処理手段１５１は、前処理として、入力されたデータの整理とエラーのチェックを行う。前処理は、図４Ａに示すように、たとえば、同一地点（Ａ）から複数の地点（Ｂ，Ｃ，Ｄ）への順番が入力された場合に、同一地点（Ａ）に複数の時刻指定が無ければ同一地点（Ａ）への巡回は１回のみとして、内部表現ではＡ，Ｂ，Ｃ，Ｄを１つのグループとみなし、図４Ｂに示すように
Ａ（１），Ｂ（２），Ｃ（２），Ｄ（２）・・・（括弧内はグループ内優先度）
というグループを作っておく。
また、逆に図４Ｃに示すように配達先が地点（Ａ）１箇所となるような場合もグループ化しておく。さらに、時刻指定が集荷と配達で時間的に逆になっているような場合は、配達の時刻指定を集荷後になるように変更する、あるいはエラーを表示して再入力を促す、という処理も行う。
【００６０】
［２地点間経路探索］
次に、２点間経路探索手段１５３は、前処理を経て登録された巡回地点の各２点間の全ての組み合わせにおける２地点間の最適経路探索を行う。一度最適経路探索を行って経路コストを記憶しておけば、巡回経路の探索では経路コストのみを扱えばよい。この探索は通常の経路探索を行う経路探索手段１４０を使用して行ってもよい。
【００６１】
［巡回経路探索］
次いで、本発明の中心となる巡回経路探索を行う。この処理はＧＡ処理手段１５５によって行われる。ＧＡ処理手段１５５は遺伝アルゴリズム（Genetic Algorithms）を用いて経路を探索する。遺伝アルゴリズムは先に述べたように進化論にヒントを得た探索手法の1つである。遺伝子に見立てた解が効率的かつ系統的に解空間を探索し最適解を求めるために、自然の進化過程を模倣している。
【００６２】
ある有利な特徴を持つ遺伝子、すなわち最適解に近い解は、より長く生き延び、かつ多くの子孫を残すことができる。つまり、自然淘汰の理論を用いている。この過程は、解をビット列の遺伝子として表現し、遺伝子の選択や交叉・突然変異などの操作によって行う。
この中で、さらに特徴的な部分が、遺伝子の評価方法である。遺伝子の評価は、良い解を導くための重要な指標となる。なぜならば、この関数によって求められた評価値を基準にして、その遺伝子を次世代に残すかどうかを決定するからである。
【００６３】
ここでの処理は先に概念を説明したように、出発地、目的地を含んだ１つの巡回経路が１つの遺伝子であり、複数の遺伝子により個体群、集合Ｐ０が形成される。例えば、出発地から全ての巡回地点を１度だけとおり目的地に至る巡回経路を探索する場合、出発地から各巡回地点をとおり目的地に至る経路をランダムに複数作成する。これらの複数の遺伝子は個体群として保存され、集合Ｐ０が形成される。集合Ｐ０における各遺伝子の評価値は、設定した各地点間の経路コスト（時間および／または距離）の総和になる。
【００６４】
次に、集合Ｐ０から選択した２つの遺伝子から新しい遺伝子を生成し、その遺伝子の評価値を求める。例えば、ルーレット方式で新しい集合Ｐ１を作成する場合は、良い評価値を持つ遺伝子ほど高い確率で集合Ｐ０から選択される。つまり、良い評価値を持つ遺伝子ほど新しい遺伝子を生成するための種となりやすいということである。ここで選択された２つの遺伝子（巡回経路）において巡回順の一部を入れ換えて新たな遺伝子を作成し、かつ低い確率で突然変異を行い、その評価値を求める。この新しい遺伝子の評価値が、集合Ｐ０における最も評価値が悪い遺伝子より良い評価値を持っていれば、この遺伝子を入れ換える。集合Ｐ１は、このような操作を１世代分行うことによって得られる。この処理を繰り返して世代交代を行い、世代交代が予め設定した所定の回数に達するか、評価値が収束すれば処理を終了し、最後に得られた集合ＰＮにおける最良の評価値を持つ遺伝子（巡回経路）が最適解または準最適解となる。
【００６５】
本発明においては、各巡回地点において順序的制約および時間的制約の条件を入力し、遺伝アルゴリズムを用いて評価値を算出する際に経路コストに加えて、各巡回地点に設定された順序的制約、時間的制約条件に基づく制約コストを付加して算出することに特徴がある。この制約に基づくコストは、順序制約や時間制約を違反した巡回地の数によって変化する。これにより、巡回地点に制約が付されている場合の巡回経路を算出することができるようになる。
【００６６】
図５、図６は、この処理の概念を説明するための模式図である。図５、図６において、出発地ＳＴから巡回地点Ｘ１〜Ｘ６を巡回して目的地ＧＬに至る巡回経路を探索する例を示し、巡回地点Ｘ３とＸ６には順序の条件（Ｘ６の巡回順の優先度がＸ３より高い：Ｘ６はＸ３より先に巡回するという条件）が付加されている。
【００６７】
図５に示すランダムに生成された初期個体群における１つの遺伝子Ｇ０が表す巡回経路の評価値として、まず経路コストの総和が加算される。評価値は経路コストの総和である。全ての２地点間の最適経路の経路コストは、２点間経路探索において探索し、その結果は保存されている。ここで、巡回地点Ｘ３とＸ６は順序制約があり、Ｘ６の巡回順の優先度がＸ３より高いので、順序制約を違反している巡回地点数がカウントアップされる。後述する式１にしたがうと、この制約違反の総数を予め設定した順序制約の重みで割り、それに経路コストを乗じることによって制約コストが求まる。ここで順序制約の重みは通常１とするが、順序に関する制約を強めたい場合は０．１〜０．９程度の値を、弱めたい場合は１．１〜１．９程度の値を設定する。この制約コストと予め求めた経路コストを加算することによって、この遺伝子の評価値が決定する。巡回地点に時間的制約が存在する場合も同様である。
【００６８】
次いで、初期個体群から２つの遺伝子を選択し、新たに生成した遺伝子Ｇ１が表す巡回経路を図６に示す。この遺伝子では、上述の遺伝子が表す巡回経路における巡回地点Ｘ２とＸ５が交換された形となっている。この遺伝子の評価値を先と同様にして算出する。ここで得た評価値が、初期個体群における遺伝子より良い評価値であれば遺伝子集団に加え新たな遺伝子を保存し、悪い評価値であれば遺伝子集団に加えず破棄する。
【００６９】
このような処理を繰り返し、全ての遺伝子の評価値が同じになるか、最も良い遺伝子の評価値が集団の平均評価値とほぼ同じである状態に収束したならば、最も良い評価値を持つ遺伝子が巡回地点Ｘ１〜Ｘ６を巡回する最適解、または、準最適解になる。
【００７０】
図７は、ＧＡ処理部１５３における処理手順を示す概念図である。ＧＡ処理手段１５３への入力情報は前処理を完了した巡回地点数、巡回地情報、各２地点間経路の経路コストである。ステップＳ２１の処理において、初期遺伝子の生成処理を行う。ここで指定された数の遺伝子をランダムに生成することにより、初期個体群Ｐ０が作成される。初期遺伝子は、ランダムに各巡回地点を通るルートを引き、既に保存してある２地点間経路のコスト総和を求める処理である。このとき、前処理で付加された各巡回地点の制約条件による制約コストが加味され各遺伝子の評価値が算出される。
【００７１】
続いて、ステップＳ２２の処理において初期遺伝子として生成された初期個体群Ｐ０から２つの遺伝子を親遺伝子として選択し、ステップＳ２３の処理において２つの遺伝子の任意の巡回地点を選択して入れ換える操作である交叉、および１つの遺伝子において巡回地点を変更する操作である突然変異を行い、ステップＳ２４にて新たな遺伝子すなわち子遺伝子を生成する。ことのき、全ての巡回地点を必ず１度だけ通るよう、つまり同じ地点を複数回巡回せず、かつ１度も巡回しない地点が存在しないような遺伝子操作を行う。
【００７２】
次いで、ステップＳ２５の処理において新たに生成された子遺伝子の評価値を算出し、個体群Ｐ０における各遺伝子の評価値と比較する。ここで生成された子遺伝子が個体群Ｐ０における遺伝子の評価値より良い値であればこの子遺伝子を採用し、その評価値と巡回順（ルート）を表現する遺伝子とを保存し、子遺伝子が個体群Ｐ０の遺伝子の評価値より悪い値であればこの子遺伝子は採用されず、結果は保存しない。
【００７３】
その後、ステップＳ２６の処理において処理の終了判定を行い、処理が終了していなければステップＳ２２の処理に戻り、上記の遺伝的操作を繰り返し行う。
【００７４】
［処理の終了判定］
ＧＡ処理手段１５３による探索処理は、試行回数が指定回数を満たした場合、あるいは遺伝子の集団における評価値が収束した場合に終了する。例えば、2つの遺伝子を選択して子遺伝子を生成する過程を1試行とすると、巡回数がnの場合、このケースにおいては最大試行回数を５０ｎ2程度とするのが良い。また、評価値が収束した状態というのは、全ての遺伝子の評価値が同じになるか、最も良い遺伝子の評価値が集団の平均評価値とほぼ同じである状態のことをいう。このような状態になったら処理が終了したものと判定し、巡回地点数、巡回順が出力される。巡回順がわかれば、保存してあった２地点間の最適経路を当該巡回順にならべて巡回経路を提供することができる。
【００７５】
巡回経路探索手段１５０における目的関数Ｆは次式のようになる。
Ｆ＝ｍｉｎ（ｅｖａｌ（ｎ））
ここで、遺伝子の評価値を求める評価関数ｅｖａｌ（ｎ）は次式のように定義する。
【数１】
ここで、ｎ： 巡回地点数
ｄｉｓｔ（ｉ）： ｉ番目の巡回地点間の経路コスト
Ｄｄｉｓｔ： 経路コストに対する重み
Ｄｔｉｍｅ： 時間制約に対する重み
Ｄｏｒｄｅｒ： 順序制約に対する重み
Ｐｔｉｍｅ： 時間制約に違反した巡回地点の総数
Ｐｏｒｄｅｒ： 順序制約に違反した巡回地点の総数
である。
【００７６】
この評価によって得られた評価値が、既存集団における遺伝子より良い評価値であれば遺伝子集団に加える（図７のステップＳ２２〜ステップＳ２５の処理参照）。このとき、既存遺伝子集団において評価値が最下位の遺伝子が集団から排除される。
【００７７】
以上のような構成の巡回経路探索手段１５０を用いて、図８に示す巡回地点１〜巡回地点５を巡回する巡回経路を求めた結果について以下に説明する。図９は、図８の具体例の配送業務の対象となるエリアの地図、配送地点を示す図である。このエリアの配送業務においては、出発地、目的地、地点１〜地点２８の配送地点が存在する。図８の具体例は出発地から地点１〜地点２８を巡回して目的地に至る巡回経路を探索する場合を示している
【００７８】
図８において、具体例１は各巡回地点のうち巡回地点１〜巡回地点５に到着時間や優先順序に関する制約が何もない巡回経路を求める場合を示す。具体例２は各巡回地点のうち巡回地点１と巡回地点３に図示のような到着時間の制約がある場合を示す。到着時間は出発時間からの経過時間（秒）で示されている。
【００７９】
具体例３は各巡回地点のうち巡回地点１と巡回地点２に順序の優先度がある第１のグループ（グループ１）と、巡回地点３〜巡回地点５の間に順序の優先度がある第２のグループ（グループ２）とが存在する場合を示す。順序の優先度は優先度の後に記述された数値（１〜３・・）が小さい程、順序の優先度が高いものとしている。具体例４は、具体例３と具体例４の制約条件を合わせ持つ場合を示している。
【００８０】
図８の具体例１の条件で巡回経路を探索した結果により得られた巡回経路が図１０に示されている。図１０においては図９に示す巡回地点を巡回順序に従った経由地+数値（巡回順）で示している。例えば巡回地点１（図９参照）は経由地８（図１０参照）で示されており、巡回順序が８番目になることを示している。具体例１の場合、ＧＡ処理手段１５５の処理において算出される遺伝子は、巡回地点の各２地点間を結ぶ経路コストの総和であり、図１０に示すように巡回経路として、経路コストの総和が最も小さくなるほぼ最適解が得られた。
【００８１】
図１１は具体例２の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、時間制約のある巡回地点１が経由地２に、巡回地点３が経由地６になり、巡回地点１の巡回順序が２番目に、巡回地点３の巡回順序が６番目になる巡回経路が求められている。
【００８２】
図１２は、具体例３の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、順序制約のあるグループ１の巡回地点１が経由地６に、巡回地点２が経由地７になり、巡回地点１の巡回順序が６番目に、巡回地点２の巡回順序が７番目になっている。順序制約のあるグループ２の巡回地点３が経由地９に、巡回地点４が経由地１１に、巡回地点５が経由地２２なり、巡回地点３の巡回順序が９番目に、巡回地点４の巡回順序が１１番目に、巡回地点５の巡回順序が２２番目になる巡回経路が求められている。
【００８３】
図１３は、具体例４の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、順序制約のあるグループ１の巡回地点１が経由地２に、巡回地点２が経由地１５になり、巡回地点１の巡回順序が２番目に、巡回地点２の巡回順序が１５番目になっている。順序制約のあるグループ２の巡回地点３が経由地４に、巡回地点４が経由地６に、巡回地点５が経由地１０になり、巡回地点３の巡回順序が４番目に、巡回地点４の巡回順序が６番目に、巡回地点５の巡回順序が１０番目になる。また、時間制約のある巡回地点１と巡回地点３に関しては、巡回地点１の巡回順序が２番目、巡回地点３の巡回順序が４番目であり、時間制約をも満たす巡回経路が求められている。
【００８４】
以上のように、具体例１〜具体例４の全ての条件に対して、それぞれ異なる巡回経路を得ることができ、またこの巡回経路はそれぞれの条件（時間制約、順序制約）を満たす巡回経路になっている。この処理に要した演算処理の実行時間は、いずれの場合でも１０秒程度であり、その殆ど（９９％）は２点間経路探索までの処理時間であった。
【００８５】
図１４は、以上のような巡回経路探索に要する演算時間を示すグラフである。図１４において横軸は巡回地点の数、縦軸はプロサッサの演算時間（秒）であり、各グラフはそれぞれプロセッサとして Pentium １．８Ｇ（５１２Ｍ）、 Pentium ２．４Ｇ（１．０Ｇ）、 Pentium ３．０Ｇ（１．０Ｇ）を使用した場合の巡回地点数に対する演算時間を示している。
【００８６】
図１４からわかるように、巡回地点が３０地点程度の場合の巡回経路探索に要する処理時間は非常に僅かであり、また、上記具体例１〜具体例４に示すように、十分な結果が得られており、実用に適しているのがわかる。
【００８７】
なお、上記実施例において、２点間経路探索手段１５３が２地点間の最適な経路コストを探索する際に、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量などを考慮したネットワークデータを利用すれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足し、かつ、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量を加味した効率的な巡回経路を探索することができる。これら日時、渋滞情報、道路種別、巡航速度、混雑度、積載量のデータは経路探索サーバ１０が道路交通情報サーバなどの他の情報配信サーバからデータを収集し道路ネットワークデータベース１９０のデータを入れ換えることによって実施することができる。
【産業上の利用可能性】
【００８８】
以上説明したように本発明は、実際に即した各種の制約条件を有する巡回地点を効率的に巡回する巡回経路探索が行えるので、物流やセールスおよび巡回調査などの分野に幅広く応用することが可能である。
【図面の簡単な説明】
【００８９】
【図１】本発明の実施例にかかるナビゲーションシステムにおける経路探索サーバの構成を示すブロック図である。
【図２】巡回経路探索における巡回地点を入力する際の入力画面の構成を示す図である。
【図３】本発明の実施例にかかる巡回経路探索の処理手順を示すフローチャートである。
【図４】本発明の実施例にかかる巡回経路探索の前処理の概念を示す図であり、図４Ａは出発地から複数地点への順番が入力された状態を示す模式図、図４Ｂは出発地をＡとする巡回地点のグループを作成した状態を示す模式図、図４Ｂは目的地をＡとする巡回地点のグループを作成した状態を示す模式図である。
【図５】本発明の実施例にかかる巡回経路探索処理の概念を説明するための模式図である。
【図６】本発明の実施例にかかる巡回経路探索処理の概念を説明するための模式図である。
【図７】遺伝アルゴリズムを使用したＧＡ処理部における処理手順を示す概念図である。
【図８】本発明による巡回経路探索を適用して巡回経路探索を実施した具体例を示す図であり、巡回地点の諸制約条件を示す図である。
【図９】図８に示す具体例の配送業務の対象となるエリアの地図、配送地点を示す図である。
【図１０】図８に示す具体例１の条件で求めた巡回経路を示す図である。
【図１１】図８に示す具体例２の条件で求めた巡回経路を示す図である。
【図１２】図８に示す具体例３の条件で求めた巡回経路を示す図である。
【図１３】図８に示す具体例４の条件で求めた巡回経路を示す図である。
【図１４】本発明の実施例にかかる巡回経路探索に要する演算時間を示すグラフである。
【図１５】１０ＴＦｌｏｐｓ（１秒間に１０13回浮動小数点演算が可能）のスーパーコンピュータを用いて巡回経路探索を、巡回数を代えて行った場合の各巡回数に対する巡回経路総数と計算時間を示す図である。
【符号の説明】
【００９０】
１０・・・・経路探索サーバ
１１０・・・制御手段
１２０・・・通信手段
１３０・・・出力・配信手段
１４０・・・経路探索手段
１５０・・・巡回経路探索手段
１５１・・・前処理手段
１５３・・・２点間経路探索手段
１５５・・・ＧＡ処理手段
１６０・・・表示手段
１７０・・・操作・入力手段
１８０・・・地図データ
１９０・・・道路ネットワークデータベース
２００・・・ガイダンスデータベース
【技術分野】
【０００１】
本発明は、所望の地点から所望の地点までの最適経路を探索して案内するナビゲーションシステムにし、予め定められた複数の地点を経由して巡回するための効率的な経路を探索する巡回経路探索機能を有するナビゲーションシステムおよび経路探索サーバに関するものであり、特に、巡回する地点に順序的あるいは時間的な制約条件がある場合に、当該制約条件を加味した効率的な巡回経路を探索するナビゲーションシステムおよび経路探索サーバならびに巡回経路探索方法に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られている。
このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置（以下、カーナビという）、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
上記カーナビは、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ：全地球測位システム）を利用したものであり、地球上を周回している複数のＧＰＳ衛星から送信されるＧＰＳ信号をＧＰＳアンテナで受信し、該ＧＰＳ信号に含まれる衛星位置や時計情報等を解析して位置の特定化を行うものである。該複数のＧＰＳ衛星の個数は少なくとも４個以上必要である。ＧＰＳの単独測位精度は一般的に１０ｍ強であるが、ＤＧＰＳ（Ｄｉｆｆｅｒｅｎｔｉａｌ ＧＰＳ：ディファレンシャルＧＰＳ）を採用することにより５ｍ以下に向上する。特に、従来は一部の携帯電話にしか搭載されていない測位ユニット、例えば、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）衛星からの信号を受信して測位するＧＰＳ受信機などが、第三世代と称される携帯電話では全ての機種に搭載されるような趨勢にある。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を経路探索サーバに送り、経路探索サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
経路探索サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、経路探索サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
ところで、経路探索において所望の２地点間の最適経路を探索する場合の他、所望の出発地から目的地までの間に所定の複数の地点を経由地として巡回する経路を探索する巡回経路探索が必要になる場合がある。このような経路探索は、例えば、物品の配送作業やセールスマンが複数の顧客場所を巡回する作業において必要になる。このような経路探索を巡回経路探索という。
【０００７】
巡回経路探索は、ｎ個の頂点を持つ完全グラフＧ（Ｖ、Ｅ）が与えられたとき、du,vを辺 (u, v) ∈Eのコストとすると、ある頂点s ∈Vから出発し、他の頂点を全て一度ずつ訪問して、最後に目的地eへ到達する経路を求めることを目的としている。ここで、一般的な配送などの業務の効率を考えた場合、なるべく巡回する経路の総コストが小さくなることが望まれる。この巡回経路を探索する課題は、ＮＰ困難な問題として知られている。
【０００８】
ＮＰ困難な問題とは、アルゴリズムの時間複雑度が指数時間となる問題、つまり、その問題を解くためのアルゴリズムにおいて必要なステップ数に関する漸近的な限界がO(cn)（ただし、cは1より大きい実数、nは問題の規模）となるものをいう。
たとえば、出発地と目的地を含まない巡回地点数がnの場合、最適な巡回経路を求めるための巡回経路探索回数は、n！となる。つまり、１０地点を巡回する場合の探索回数は、（１０×９×８×７×６×５×４×３×２×１）＝３６２８８０回となる。
ちなみに出発地を巡回地数に含め、かつ出発地に戻ってくる場合の巡回経路探索回数は（ｎ−１）！／２となる。
【０００９】
図１５は、１０ＴＦｌｏｐｓ（１秒間に１０13回浮動小数点演算が可能）のスーパーコンピュータを用いて上記のような巡回経路探索を、巡回数を代えて行った場合の各巡回数に対する巡回経路総数と計算時間を示す。１０ＴＦｌｏｐｓのスーパーコンピュータは、例えば、Pentium4（登録商標名）-1.8ＧＨｚのパソコン５０００台分程度の演算能力を持つものである。
【００１０】
図１５に示したように、巡回経路探索は、巡回地点が多くなると現在の一般的な演算処理装置で総当り演算を行うと膨大な演算が必要となり現実的には困難であるという問題点があるため、一般的には「遺伝アルゴリズム」と言われるアルゴリズムなどを用いて近似解を求めることが行われる。
【００１１】
例えば、下記の特許文献２（特開２０００−１７２６６４号公報）、特許文献３（特開平８−２０２６７５号公報）に、遺伝アルゴリズムを用いた巡回経路探索の技術が開示されている。
【００１２】
遺伝アルゴリズムは、生物の進化過程（交叉、突然変異等）をモデルとして、確率的に解を探索しようとする手法である。まずここで遺伝アルゴリズムについて説明する。遺伝アルゴリズムについて、例えば、下記の非特許文献１（ David E. Goldの「Genetic Algorithms in Search, Optimization and Machine Learning」(Addison Wesley社）に詳細が開示されている。
【００１３】
遺伝アルゴリズムでは、入力値として、ｘ個のビット列Ｂ＝(Ｂ1,Ｂ2,…,ＢＸ)、（あるいは省略して単に、Ｂ1Ｂ2…ＢＸとも記す）の集合Ｐが与えられる。集合Ｐの元（ｘ個のビット列）の個数をｎとし、各元を遺伝子、集合Ｐを個体群と呼ぶ。集合Ｐの各元は、与えられた問題の解をそれぞれ表現しており、遺伝アルゴリズムでは、生物の進化過程に倣った繰り返し処理を集合Ｐに加え、最適解を得ようとする。
【００１４】
遺伝アルゴリズムにおける処理の概要は次のようである。まず、ランダムに生成した遺伝子の集合として個体群を構成する。これを初期個体群と呼ぶ。次に、問題に応じて与えられた評価尺度（評価関数）にしたがって、個体群中の各遺伝子において解としての良さを評価し、その結果を遺伝子ごとに評価値として表す。そして、求めた評価値にしたがって、評価の低い遺伝子を減らし、その分、評価の良い遺伝子を増やす。その結果、評価の良い遺伝子ほど個体群Ｐに占める割合が高くなる。このような現象を「淘汰」と呼ぶ。この遺伝子の淘汰の処理は下記のようにして行われる。
【００１５】
まず、ランダムに生成された個体群から２つの遺伝子を、例えばランク方式やルーレット方式などの方法により選択し、それらの遺伝子を成すビット列の一部を交換する。この操作を「交叉」と呼ぶ。この交叉は、予め設定された交叉率により繰り返す回数が決定される。交叉によって新しく生成される遺伝子の数は、この交叉率に遺伝子数ｎを乗じた数となる。続いて、通常低い確率で設定される突然変異率にしたがい交叉によって得られた遺伝子を少し変更する。この操作を「突然変異」と呼ぶ。突然変異の方法としては、例えば遺伝子のビット列の一部をビット反転するなどの方法が知られている。
【００１６】
交叉・突然変異などの操作が完了したら、個体群中の各遺伝子において解としての良さを評価し、その評価結果にしたがい次の個体群を生成する。新たな個体群は、上述の操作によって作られた個体群と以前の個体群において、良い評価値を持つ遺伝子を遺伝子数ｎ分だけ抽出することによって生成される。この１回の淘汰、すなわち交叉・突然変異及び新たな個体群の生成の１回のサイクルが「世代」に相当する。このような上述の処理を繰り返すことで個体群の世代が進み、個体群の各遺伝子が淘汰されることで、個体群内の各遺伝子は、与えられた問題の最適解あるいは準最適解に達する。
【００１７】
上記の遺伝アルゴリズムを複数の地点を巡回する経路探索に用いる場合、１つの遺伝子は出発地、目的地を含んだ１つの巡回経路となる。例えば、出発地から全ての巡回地点を１度だけ通り目的地に至る巡回経路を探索する場合、まず出発地から各巡回地点を通り目的地に至る経路をランダムに複数作成する。これらの複数の遺伝子は個体群として保存され、集合Ｐ０が形成される。集合Ｐ０における各遺伝子の評価値は、設定した各地点間の経路コスト（時間および／または距離）の総和になる。
【００１８】
次に、集合Ｐ０から選択した２つの遺伝子から新しい遺伝子を生成し、その遺伝子の評価値を求める。例えば、ルーレット方式で新しい集合Ｐ１を作成する場合は、良い評価値を持つ遺伝子ほど高い確率で集合Ｐ０から選択される。つまり、良い評価値を持つ遺伝子ほど新しい遺伝子を生成するための種となりやすいということである。ここで選択された２つの遺伝子（巡回経路）において巡回順の一部を入れ換えて新たな遺伝子を作成し、かつ低い確率で突然変異を行い、その評価値を求める。この新しい遺伝子の評価値が、集合Ｐ０における最も評価値が悪い遺伝子より良い評価値を持っていれば、この遺伝子を入れ換える。集合Ｐ１は、このような操作を１世代分行うことによって得られる。この処理を繰り返して世代交代を行い、世代交代が予め設定した所定の回数に達するか、評価値が収束すれば処理を終了し、最後に得られた集合ＰＮにおける最良の評価値を持つ遺伝子（巡回経路）が最適解または準最適解となる。
【００１９】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２０００−１７２６６４公報
【特許文献３】特開平８−２０２６７５号公報
【非特許文献１】David E. Gold著、「Genetic Algorithms in Search, Optimization and Machine Learning」(Addison Wesley社 １９８９年発行)
【発明の開示】
【発明が解決しようとする課題】
【００２０】
一般的に巡回経路探索は、物品の配送や送迎の業務を効率化することを目的としているため、必ずしも最適解が必要というわけでない。つまり、準最適解でも十分有用であるということである。一般的な業務においては、最適な巡回経路を求めなくとも人間が考える経路よりも良い結果を導き出すことができれば良い。あるいは、巡回経路探索装置を使用することによって人間が経路を考えるという労力を少なくするができるため、これだけでも業務の効率化を行うことが可能である。これらのことも、巡回経路探索に近似解法が適用される1つの要因となっている。
【００２１】
巡回経路を求める演算は非常に計算量が多く困難を極めるため、人間の勘に頼るか、あるいは現在地を中心に周回するだけの経路を求めることで妥協する例も見られる。また、単純な巡回経路探索は、なるべく短い巡回経路を求めることが目的となっており実際の利用状況にそぐわない場合がある。
たとえば、
１）巡回地点に順番の優先条件がある場合
２）巡回地点に立ち寄る時刻条件がある場合
３）巡回地点に順番の優先条件と立ち寄る時刻条件がある場合
である。
【００２２】
物品の集荷や配送における経路決定においては巡回する地点の間に順序の制約（優先条件）がある。つまり物品を配送する場合、集荷と配達があるので、巡回経路を探索する場合には集荷と配達の順番を満たさなければならない。そのため上記遺伝アルゴリズムを適用した単純な巡回経路探索では満足できる結果が得られないという問題点があった。このような問題点は特開２００５−２６３４４７号公報においても課題として開示されている。
【００２３】
別の例を挙げると、過疎地において１台の車両で複数の住民の移動の希望を同時に満たすために乗り合いバスを運行する場合が該当する。それぞれの住民の乗車希望位置と下車希望位置が巡回地点になるが、乗車→下車の順番が条件となるので、純粋な巡回経路探索では解が求められない。（乗車と下車の順番が逆になるとその住民は利用できない）。
このようなケースにおいては、巡回する必要のある地点が１０地点とすると、巡回地 Ｒ∈｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｉ，ｊ}のとき、地点ｃはａより後、あるいは地点ｄ，ｃは地点ｈ，ｉ，ｊより後に巡回するというような条件を同時に満足する巡回経路を導き出すことが求められる。
【００２４】
巡回地点に時間的制約（優先条件）があるケースとは、例えば、巡回地点がある決まった時間にしか立ち入ることができないビル内にあるようなケースである。物品の配送の例でいえば、立ち入りの時間が限られるビル内に設置された自動販売機に商品を配送するようなケースである。
つまり、このような経路探索においては、出発地の出発時刻あるいは到着地の到着時刻を基準とする巡回地点の到着希望時刻などの条件を満たす巡回経路を導き出すことが求められるのである。
【００２５】
また、上記のような順序の制約と時間の制約が同時に存在する場合もある。このようなケースは、例えば、上記の過疎地における乗合バス運行の巡回経路探索において、過疎地の住民が乗車希望位置と下車希望位置と、乗車または下車の希望時刻まで条件設定できる巡回経路探索というテーマにも発展するものである。
【００２６】
本願の発明者は上記のような問題点を解消すべく種々検討を重ねた結果、巡回対象の地点の制約条件を入力する手段を設け、巡回対象の全ての２地点間の最短経路を探索し記憶しておき、順序探索手段は遺伝的アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和だけでなく、巡回対象の地点の制約条件に対する評価値を加味して算出して、この評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めるようになせば上記問題点を解消し得ることに想到し本発明を完成するに至ったものである。
【００２７】
すなわち、本発明は上記の問題点を解消することを目的とし、巡回すべき複数の地点に順序および／または時間的な制約がある場合に、当該制約を満足し得る巡回経路を探索できるようにしたナビゲーションシステム、経路探索サーバを提供することを目的とするものである。
【課題を解決するための手段】
【００２８】
前記課題を解決するために、本願の請求項１にかかる発明は、
複数の地点を巡回する巡回経路探索機能を有するナビゲーションシステムであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする。
【００２９】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする。
【００３０】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする。
【００３１】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする。
【００３２】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする。
【００３３】
また、請求項６にかかる発明は、
複数の地点を巡回する巡回経路探索機能を有する経路探索サーバであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする。
【００３４】
本願の請求項７にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする。
【００３５】
本願の請求項８にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする。
【００３６】
本願の請求項９にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする。
【００３７】
本願の請求項１０にかかる発明は、請求項６にかかるナビゲーションサーバにおいて、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする。
【００３８】
また、本願の請求項１１にかかる発明は、
複数の地点を巡回する巡回経路探索方法であって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段が、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶するステップと、
前記巡回経路探索手段が、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出するステップと、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えるステップと、を含み巡回経路探索を進めることを特徴とする。
【００３９】
また、本願の請求項１２にかかる発明は、請求項１１にかかる巡回経路探索方法において、
前記２地点間経路探索手段が最短経路を探索してその最適経路および経路コストを記憶するステップは、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する処理を含むことを特徴とする。
【発明の効果】
【００４０】
請求項１にかかる発明においては、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【００４１】
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４２】
また、請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回対象の地点の制約条件は、当該地点の巡回順序の優先度である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に順序的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４３】
また、請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点に時間的な制約条件がある場合であっても、制約条件を満足する効率的な巡回経路を探索して提供できるようになる。
【００４４】
また、請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間である。
このような構成によれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足し、かつ、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮した効率的な巡回経路を探索して提供できるようになる。
【００４５】
また、請求項５にかかる発明においてはき、請求項１にかかるナビゲーションシステムにおいて、記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する。
このような構成によれば、都市部のように一方通行路が多い場合、あるいは方向によって著しくコストが異なる経路が存在する場合においても効率のよい巡回経路を探索することができるようになる。
【００４６】
本願の請求項６〜請求項１０にかかる発明においては、それぞれ請求項１〜請求項５にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項１１、請求項１２にかかる発明においては、それぞれ請求項６、請求項１０にかかる経路探索サーバにおける巡回経路探索方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００４８】
本発明の実施例にかかるナビゲーションシステムは、図１に示すように経路探索サーバ１０を備えて構成されている。経路探索サーバ１０は図示しない端末装置から経路探索要求を受信し、出発地から目的地までの最適経路を探索し、要求元の端末装置に配信する。
【００４９】
経路探索サーバ１０は、制御手段１１０、通信手段１２０、出力・配信手段１３０、経路探索手段１４０、巡回経路探索手段１５０、前処理手段１５１、２点間経路探索手段１５３、ＧＡ処理手段１５５、表示手段１６０、操作・入力手段１７０、地図データ１８０、道路ネットワークデータベース１９０、ガイダンスデータベース２００などを備えて構成されている。
【００５０】
制御手段１１０は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段１２０はネットワークを介して端末装置や他のサーバと通信するためのものである。出力・配信手段１３０は、経路探索結果を出力し、あるいは、端末装置に配信するためのものであり、経路データ、ガイダンスデータを端末装置に配信するためのデータに編集する。操作・入力手段１７０は経路探索サーバ１０に所望の入力、操作を行うためのものであり、表示手段１６０は液晶表示ユニットなどから構成され、所定の入力画面を表示する。
【００５１】
地図データ１８０には端末装置に提供する地図情報が蓄積されており、道路ネットワークデータベース１９０には地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）などがデータベースとして蓄積されている。ガイダンスデータベース２００には、交差点などにおける進行方向案内のための音声データや案内表示画像データが蓄積されている。
【００５２】
経路探索手段１４０は道路ネットワークデータベース１９０を参照して通常の経路探索を行う。巡回経路探索手段１５０は本実施例における巡回経路の探索を行うものである。巡回経路探索手段１５０は、前処理手段１５１、２点間経路探索手段１５３、ＧＡ処理手段１５５を備えて構成されている。これらの詳細については後述する。
【００５３】
本実施例においては、巡回経路探索のモデルを、例えば、僻地における荷物の集配の例で説明する。僻地では単位面積あたりの配送数が少ないので、１台の車両で集荷と配達を行うと効率が良い。また単位面積あたりの配送数が少ないということは、１配送あたりの走行距離も長くなるので、収益面でも出来るだけ効率の良い配送をしないと事業として成り立たない。
【００５４】
図２は、経路探索サーバ１０において巡回経路探索を実施する際の端末装置における巡回地点の入力画面である。実施に当たってはそれぞれの業態により最適なユーザインタフェース（ＵＩ）にカスタマイズされるべきであるが、機能のみを簡潔に説明する。この実施例では、出発地はこの配送業者の営業所、また最終目的地は出発地に戻るものとして登録済みである。また、経路探索サーバ１０を本実施例の経路探索エンジンをインストールしたパーソナルコンピュータに置き換えることもできる。
【００５５】
ある日の集配計画を立てるために、図２に示す入力画面からまず巡回地点の入力を行う。巡回地点は、住所、店舗／施設名、電話番号などを選択してフリーワードで入力可能である（選択しなくても検索機能により検索して入力することも可能である）。その巡回地点に立ち寄る時刻条件があれば、時刻指定から選択する。デフォルトは、「なし」であるが、プルダウンメニューによって、
11：00〜13：00
13：00〜15：00
15：00〜17：00
...
など時間の制約条件を指定することが可能である。
荷物の集荷から配達をまで行う場合には、左側の欄に集荷地点、右側の欄に配達先を入力することで、順序条件を指定する。
【００５６】
地点を確認する場合は、地図ボタンを押すことで地図上の位置を確認できる。また地図上で修正も可能である。誤入力した場合は、削除ボタンで、その行をクリアすることもできる。さらに巡回地点がある場合は、次の行に順次入力する。行が足りなくなったら、追加ボタンを押して、さらに入力行を増やせるようになっている。なお、巡回経路を求めるので、オペレータは地点を順次入力して行くだけでよい（入力の順番を意識する必要は無い）。
【００５７】
入力が終わったところで、検索ボタンを押すと、巡回経路探索の処理に移る。巡回経路探索の処理は大きく分けて図３のフローチャートに示す手順で進行する。すなわち、ステップＳ１１の処理において前処理を行った後、ステップＳ１２の処理において巡回地点の各２地点間の全ての組み合わせの最適経路探索を行う。（なお、２地点間の経路に一方通行路などが含まれない場合は２地点間の順序による経路コストは考慮しなくても良いが、都市部のように一方通行路が多い場合、あるいは方向によって著しくコストが異なる経路が存在する場合は双方向の経路を探索するのが良い）一度最適経路探索を行って経路コストを記憶しておけば、巡回経路の探索では経路コストのみを扱えばよい。
【００５８】
このため、ステップＳ１３の処理において探索した全ての経路のコストを保存する。次いでステップＳ１４の処理において巡回経路探索を行い、ステップＳ１５の処理において結果を出力する。以下に各処理を更に詳細に説明する。
【００５９】
［前処理］
まず、前処理手段１５１は、前処理として、入力されたデータの整理とエラーのチェックを行う。前処理は、図４Ａに示すように、たとえば、同一地点（Ａ）から複数の地点（Ｂ，Ｃ，Ｄ）への順番が入力された場合に、同一地点（Ａ）に複数の時刻指定が無ければ同一地点（Ａ）への巡回は１回のみとして、内部表現ではＡ，Ｂ，Ｃ，Ｄを１つのグループとみなし、図４Ｂに示すように
Ａ（１），Ｂ（２），Ｃ（２），Ｄ（２）・・・（括弧内はグループ内優先度）
というグループを作っておく。
また、逆に図４Ｃに示すように配達先が地点（Ａ）１箇所となるような場合もグループ化しておく。さらに、時刻指定が集荷と配達で時間的に逆になっているような場合は、配達の時刻指定を集荷後になるように変更する、あるいはエラーを表示して再入力を促す、という処理も行う。
【００６０】
［２地点間経路探索］
次に、２点間経路探索手段１５３は、前処理を経て登録された巡回地点の各２点間の全ての組み合わせにおける２地点間の最適経路探索を行う。一度最適経路探索を行って経路コストを記憶しておけば、巡回経路の探索では経路コストのみを扱えばよい。この探索は通常の経路探索を行う経路探索手段１４０を使用して行ってもよい。
【００６１】
［巡回経路探索］
次いで、本発明の中心となる巡回経路探索を行う。この処理はＧＡ処理手段１５５によって行われる。ＧＡ処理手段１５５は遺伝アルゴリズム（Genetic Algorithms）を用いて経路を探索する。遺伝アルゴリズムは先に述べたように進化論にヒントを得た探索手法の1つである。遺伝子に見立てた解が効率的かつ系統的に解空間を探索し最適解を求めるために、自然の進化過程を模倣している。
【００６２】
ある有利な特徴を持つ遺伝子、すなわち最適解に近い解は、より長く生き延び、かつ多くの子孫を残すことができる。つまり、自然淘汰の理論を用いている。この過程は、解をビット列の遺伝子として表現し、遺伝子の選択や交叉・突然変異などの操作によって行う。
この中で、さらに特徴的な部分が、遺伝子の評価方法である。遺伝子の評価は、良い解を導くための重要な指標となる。なぜならば、この関数によって求められた評価値を基準にして、その遺伝子を次世代に残すかどうかを決定するからである。
【００６３】
ここでの処理は先に概念を説明したように、出発地、目的地を含んだ１つの巡回経路が１つの遺伝子であり、複数の遺伝子により個体群、集合Ｐ０が形成される。例えば、出発地から全ての巡回地点を１度だけとおり目的地に至る巡回経路を探索する場合、出発地から各巡回地点をとおり目的地に至る経路をランダムに複数作成する。これらの複数の遺伝子は個体群として保存され、集合Ｐ０が形成される。集合Ｐ０における各遺伝子の評価値は、設定した各地点間の経路コスト（時間および／または距離）の総和になる。
【００６４】
次に、集合Ｐ０から選択した２つの遺伝子から新しい遺伝子を生成し、その遺伝子の評価値を求める。例えば、ルーレット方式で新しい集合Ｐ１を作成する場合は、良い評価値を持つ遺伝子ほど高い確率で集合Ｐ０から選択される。つまり、良い評価値を持つ遺伝子ほど新しい遺伝子を生成するための種となりやすいということである。ここで選択された２つの遺伝子（巡回経路）において巡回順の一部を入れ換えて新たな遺伝子を作成し、かつ低い確率で突然変異を行い、その評価値を求める。この新しい遺伝子の評価値が、集合Ｐ０における最も評価値が悪い遺伝子より良い評価値を持っていれば、この遺伝子を入れ換える。集合Ｐ１は、このような操作を１世代分行うことによって得られる。この処理を繰り返して世代交代を行い、世代交代が予め設定した所定の回数に達するか、評価値が収束すれば処理を終了し、最後に得られた集合ＰＮにおける最良の評価値を持つ遺伝子（巡回経路）が最適解または準最適解となる。
【００６５】
本発明においては、各巡回地点において順序的制約および時間的制約の条件を入力し、遺伝アルゴリズムを用いて評価値を算出する際に経路コストに加えて、各巡回地点に設定された順序的制約、時間的制約条件に基づく制約コストを付加して算出することに特徴がある。この制約に基づくコストは、順序制約や時間制約を違反した巡回地の数によって変化する。これにより、巡回地点に制約が付されている場合の巡回経路を算出することができるようになる。
【００６６】
図５、図６は、この処理の概念を説明するための模式図である。図５、図６において、出発地ＳＴから巡回地点Ｘ１〜Ｘ６を巡回して目的地ＧＬに至る巡回経路を探索する例を示し、巡回地点Ｘ３とＸ６には順序の条件（Ｘ６の巡回順の優先度がＸ３より高い：Ｘ６はＸ３より先に巡回するという条件）が付加されている。
【００６７】
図５に示すランダムに生成された初期個体群における１つの遺伝子Ｇ０が表す巡回経路の評価値として、まず経路コストの総和が加算される。評価値は経路コストの総和である。全ての２地点間の最適経路の経路コストは、２点間経路探索において探索し、その結果は保存されている。ここで、巡回地点Ｘ３とＸ６は順序制約があり、Ｘ６の巡回順の優先度がＸ３より高いので、順序制約を違反している巡回地点数がカウントアップされる。後述する式１にしたがうと、この制約違反の総数を予め設定した順序制約の重みで割り、それに経路コストを乗じることによって制約コストが求まる。ここで順序制約の重みは通常１とするが、順序に関する制約を強めたい場合は０．１〜０．９程度の値を、弱めたい場合は１．１〜１．９程度の値を設定する。この制約コストと予め求めた経路コストを加算することによって、この遺伝子の評価値が決定する。巡回地点に時間的制約が存在する場合も同様である。
【００６８】
次いで、初期個体群から２つの遺伝子を選択し、新たに生成した遺伝子Ｇ１が表す巡回経路を図６に示す。この遺伝子では、上述の遺伝子が表す巡回経路における巡回地点Ｘ２とＸ５が交換された形となっている。この遺伝子の評価値を先と同様にして算出する。ここで得た評価値が、初期個体群における遺伝子より良い評価値であれば遺伝子集団に加え新たな遺伝子を保存し、悪い評価値であれば遺伝子集団に加えず破棄する。
【００６９】
このような処理を繰り返し、全ての遺伝子の評価値が同じになるか、最も良い遺伝子の評価値が集団の平均評価値とほぼ同じである状態に収束したならば、最も良い評価値を持つ遺伝子が巡回地点Ｘ１〜Ｘ６を巡回する最適解、または、準最適解になる。
【００７０】
図７は、ＧＡ処理部１５３における処理手順を示す概念図である。ＧＡ処理手段１５３への入力情報は前処理を完了した巡回地点数、巡回地情報、各２地点間経路の経路コストである。ステップＳ２１の処理において、初期遺伝子の生成処理を行う。ここで指定された数の遺伝子をランダムに生成することにより、初期個体群Ｐ０が作成される。初期遺伝子は、ランダムに各巡回地点を通るルートを引き、既に保存してある２地点間経路のコスト総和を求める処理である。このとき、前処理で付加された各巡回地点の制約条件による制約コストが加味され各遺伝子の評価値が算出される。
【００７１】
続いて、ステップＳ２２の処理において初期遺伝子として生成された初期個体群Ｐ０から２つの遺伝子を親遺伝子として選択し、ステップＳ２３の処理において２つの遺伝子の任意の巡回地点を選択して入れ換える操作である交叉、および１つの遺伝子において巡回地点を変更する操作である突然変異を行い、ステップＳ２４にて新たな遺伝子すなわち子遺伝子を生成する。ことのき、全ての巡回地点を必ず１度だけ通るよう、つまり同じ地点を複数回巡回せず、かつ１度も巡回しない地点が存在しないような遺伝子操作を行う。
【００７２】
次いで、ステップＳ２５の処理において新たに生成された子遺伝子の評価値を算出し、個体群Ｐ０における各遺伝子の評価値と比較する。ここで生成された子遺伝子が個体群Ｐ０における遺伝子の評価値より良い値であればこの子遺伝子を採用し、その評価値と巡回順（ルート）を表現する遺伝子とを保存し、子遺伝子が個体群Ｐ０の遺伝子の評価値より悪い値であればこの子遺伝子は採用されず、結果は保存しない。
【００７３】
その後、ステップＳ２６の処理において処理の終了判定を行い、処理が終了していなければステップＳ２２の処理に戻り、上記の遺伝的操作を繰り返し行う。
【００７４】
［処理の終了判定］
ＧＡ処理手段１５３による探索処理は、試行回数が指定回数を満たした場合、あるいは遺伝子の集団における評価値が収束した場合に終了する。例えば、2つの遺伝子を選択して子遺伝子を生成する過程を1試行とすると、巡回数がnの場合、このケースにおいては最大試行回数を５０ｎ2程度とするのが良い。また、評価値が収束した状態というのは、全ての遺伝子の評価値が同じになるか、最も良い遺伝子の評価値が集団の平均評価値とほぼ同じである状態のことをいう。このような状態になったら処理が終了したものと判定し、巡回地点数、巡回順が出力される。巡回順がわかれば、保存してあった２地点間の最適経路を当該巡回順にならべて巡回経路を提供することができる。
【００７５】
巡回経路探索手段１５０における目的関数Ｆは次式のようになる。
Ｆ＝ｍｉｎ（ｅｖａｌ（ｎ））
ここで、遺伝子の評価値を求める評価関数ｅｖａｌ（ｎ）は次式のように定義する。
【数１】
ここで、ｎ： 巡回地点数
ｄｉｓｔ（ｉ）： ｉ番目の巡回地点間の経路コスト
Ｄｄｉｓｔ： 経路コストに対する重み
Ｄｔｉｍｅ： 時間制約に対する重み
Ｄｏｒｄｅｒ： 順序制約に対する重み
Ｐｔｉｍｅ： 時間制約に違反した巡回地点の総数
Ｐｏｒｄｅｒ： 順序制約に違反した巡回地点の総数
である。
【００７６】
この評価によって得られた評価値が、既存集団における遺伝子より良い評価値であれば遺伝子集団に加える（図７のステップＳ２２〜ステップＳ２５の処理参照）。このとき、既存遺伝子集団において評価値が最下位の遺伝子が集団から排除される。
【００７７】
以上のような構成の巡回経路探索手段１５０を用いて、図８に示す巡回地点１〜巡回地点５を巡回する巡回経路を求めた結果について以下に説明する。図９は、図８の具体例の配送業務の対象となるエリアの地図、配送地点を示す図である。このエリアの配送業務においては、出発地、目的地、地点１〜地点２８の配送地点が存在する。図８の具体例は出発地から地点１〜地点２８を巡回して目的地に至る巡回経路を探索する場合を示している
【００７８】
図８において、具体例１は各巡回地点のうち巡回地点１〜巡回地点５に到着時間や優先順序に関する制約が何もない巡回経路を求める場合を示す。具体例２は各巡回地点のうち巡回地点１と巡回地点３に図示のような到着時間の制約がある場合を示す。到着時間は出発時間からの経過時間（秒）で示されている。
【００７９】
具体例３は各巡回地点のうち巡回地点１と巡回地点２に順序の優先度がある第１のグループ（グループ１）と、巡回地点３〜巡回地点５の間に順序の優先度がある第２のグループ（グループ２）とが存在する場合を示す。順序の優先度は優先度の後に記述された数値（１〜３・・）が小さい程、順序の優先度が高いものとしている。具体例４は、具体例３と具体例４の制約条件を合わせ持つ場合を示している。
【００８０】
図８の具体例１の条件で巡回経路を探索した結果により得られた巡回経路が図１０に示されている。図１０においては図９に示す巡回地点を巡回順序に従った経由地+数値（巡回順）で示している。例えば巡回地点１（図９参照）は経由地８（図１０参照）で示されており、巡回順序が８番目になることを示している。具体例１の場合、ＧＡ処理手段１５５の処理において算出される遺伝子は、巡回地点の各２地点間を結ぶ経路コストの総和であり、図１０に示すように巡回経路として、経路コストの総和が最も小さくなるほぼ最適解が得られた。
【００８１】
図１１は具体例２の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、時間制約のある巡回地点１が経由地２に、巡回地点３が経由地６になり、巡回地点１の巡回順序が２番目に、巡回地点３の巡回順序が６番目になる巡回経路が求められている。
【００８２】
図１２は、具体例３の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、順序制約のあるグループ１の巡回地点１が経由地６に、巡回地点２が経由地７になり、巡回地点１の巡回順序が６番目に、巡回地点２の巡回順序が７番目になっている。順序制約のあるグループ２の巡回地点３が経由地９に、巡回地点４が経由地１１に、巡回地点５が経由地２２なり、巡回地点３の巡回順序が９番目に、巡回地点４の巡回順序が１１番目に、巡回地点５の巡回順序が２２番目になる巡回経路が求められている。
【００８３】
図１３は、具体例４の条件で巡回経路を探索した結果得られた巡回経路を示す図である。この巡回経路においては、順序制約のあるグループ１の巡回地点１が経由地２に、巡回地点２が経由地１５になり、巡回地点１の巡回順序が２番目に、巡回地点２の巡回順序が１５番目になっている。順序制約のあるグループ２の巡回地点３が経由地４に、巡回地点４が経由地６に、巡回地点５が経由地１０になり、巡回地点３の巡回順序が４番目に、巡回地点４の巡回順序が６番目に、巡回地点５の巡回順序が１０番目になる。また、時間制約のある巡回地点１と巡回地点３に関しては、巡回地点１の巡回順序が２番目、巡回地点３の巡回順序が４番目であり、時間制約をも満たす巡回経路が求められている。
【００８４】
以上のように、具体例１〜具体例４の全ての条件に対して、それぞれ異なる巡回経路を得ることができ、またこの巡回経路はそれぞれの条件（時間制約、順序制約）を満たす巡回経路になっている。この処理に要した演算処理の実行時間は、いずれの場合でも１０秒程度であり、その殆ど（９９％）は２点間経路探索までの処理時間であった。
【００８５】
図１４は、以上のような巡回経路探索に要する演算時間を示すグラフである。図１４において横軸は巡回地点の数、縦軸はプロサッサの演算時間（秒）であり、各グラフはそれぞれプロセッサとして Pentium １．８Ｇ（５１２Ｍ）、 Pentium ２．４Ｇ（１．０Ｇ）、 Pentium ３．０Ｇ（１．０Ｇ）を使用した場合の巡回地点数に対する演算時間を示している。
【００８６】
図１４からわかるように、巡回地点が３０地点程度の場合の巡回経路探索に要する処理時間は非常に僅かであり、また、上記具体例１〜具体例４に示すように、十分な結果が得られており、実用に適しているのがわかる。
【００８７】
なお、上記実施例において、２点間経路探索手段１５３が２地点間の最適な経路コストを探索する際に、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量などを考慮したネットワークデータを利用すれば、遺伝アルゴリズムを用いて複数の巡回地点を巡回する巡回経路を探索する際、巡回地点の間に時間的な制約条件や順序的な制約条件がある場合であっても、制約条件を満足し、かつ、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量を加味した効率的な巡回経路を探索することができる。これら日時、渋滞情報、道路種別、巡航速度、混雑度、積載量のデータは経路探索サーバ１０が道路交通情報サーバなどの他の情報配信サーバからデータを収集し道路ネットワークデータベース１９０のデータを入れ換えることによって実施することができる。
【産業上の利用可能性】
【００８８】
以上説明したように本発明は、実際に即した各種の制約条件を有する巡回地点を効率的に巡回する巡回経路探索が行えるので、物流やセールスおよび巡回調査などの分野に幅広く応用することが可能である。
【図面の簡単な説明】
【００８９】
【図１】本発明の実施例にかかるナビゲーションシステムにおける経路探索サーバの構成を示すブロック図である。
【図２】巡回経路探索における巡回地点を入力する際の入力画面の構成を示す図である。
【図３】本発明の実施例にかかる巡回経路探索の処理手順を示すフローチャートである。
【図４】本発明の実施例にかかる巡回経路探索の前処理の概念を示す図であり、図４Ａは出発地から複数地点への順番が入力された状態を示す模式図、図４Ｂは出発地をＡとする巡回地点のグループを作成した状態を示す模式図、図４Ｂは目的地をＡとする巡回地点のグループを作成した状態を示す模式図である。
【図５】本発明の実施例にかかる巡回経路探索処理の概念を説明するための模式図である。
【図６】本発明の実施例にかかる巡回経路探索処理の概念を説明するための模式図である。
【図７】遺伝アルゴリズムを使用したＧＡ処理部における処理手順を示す概念図である。
【図８】本発明による巡回経路探索を適用して巡回経路探索を実施した具体例を示す図であり、巡回地点の諸制約条件を示す図である。
【図９】図８に示す具体例の配送業務の対象となるエリアの地図、配送地点を示す図である。
【図１０】図８に示す具体例１の条件で求めた巡回経路を示す図である。
【図１１】図８に示す具体例２の条件で求めた巡回経路を示す図である。
【図１２】図８に示す具体例３の条件で求めた巡回経路を示す図である。
【図１３】図８に示す具体例４の条件で求めた巡回経路を示す図である。
【図１４】本発明の実施例にかかる巡回経路探索に要する演算時間を示すグラフである。
【図１５】１０ＴＦｌｏｐｓ（１秒間に１０13回浮動小数点演算が可能）のスーパーコンピュータを用いて巡回経路探索を、巡回数を代えて行った場合の各巡回数に対する巡回経路総数と計算時間を示す図である。
【符号の説明】
【００９０】
１０・・・・経路探索サーバ
１１０・・・制御手段
１２０・・・通信手段
１３０・・・出力・配信手段
１４０・・・経路探索手段
１５０・・・巡回経路探索手段
１５１・・・前処理手段
１５３・・・２点間経路探索手段
１５５・・・ＧＡ処理手段
１６０・・・表示手段
１７０・・・操作・入力手段
１８０・・・地図データ
１９０・・・道路ネットワークデータベース
２００・・・ガイダンスデータベース
【特許請求の範囲】
【請求項１】
複数の地点を巡回する巡回経路探索機能を有するナビゲーションシステムであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする巡回経路探索機能を有するナビゲーションシステム。
【請求項２】
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項３】
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項４】
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項５】
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項６】
複数の地点を巡回する巡回経路探索機能を有する経路探索サーバであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする巡回経路探索機能を有する経路探索サーバ。
【請求項７】
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項８】
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項９】
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項１０】
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする請求項６に記載の巡回経路探索機能を有す経路探索サーバ。
【請求項１１】
複数の地点を巡回する巡回経路探索方法であって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段が、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶するステップと、
前記巡回経路探索手段が、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出するステップと、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えるステップと、を含み巡回経路探索を進めることを特徴とする巡回経路探索方法。
【請求項１２】
前記２地点間経路探索手段が最短経路を探索してその最適経路および経路コストを記憶するステップは、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する処理を含むことを特徴とする請求項１１に記載の巡回経路探索方法。
【請求項１】
複数の地点を巡回する巡回経路探索機能を有するナビゲーションシステムであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする巡回経路探索機能を有するナビゲーションシステム。
【請求項２】
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項３】
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項４】
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項５】
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする請求項１に記載の巡回経路探索機能を有するナビゲーションシステム。
【請求項６】
複数の地点を巡回する巡回経路探索機能を有する経路探索サーバであって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進めることを特徴とする巡回経路探索機能を有する経路探索サーバ。
【請求項７】
前記巡回対象の地点の制約条件は、当該地点の巡回順序の優先度であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項８】
前記巡回対象の地点の制約条件は、当該地点の巡回時刻または巡回時間帯であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項９】
前記巡回順序に応じた経路コストは、少なくとも、日時、渋滞情報、道路種別、巡航速度、混雑度、積載量の１つを考慮して算出した距離または時間であることを特徴とする請求項６に記載の巡回経路探索機能を有する経路探索サーバ。
【請求項１０】
前記２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索する際、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶することを特徴とする請求項６に記載の巡回経路探索機能を有す経路探索サーバ。
【請求項１１】
複数の地点を巡回する巡回経路探索方法であって、
巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する入力手段と、２地点間の経路を探索する２地点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、とを備え、
前記２地点間経路探索手段が、巡回対象の２地点間全ての最短経路を探索してその最適経路および経路コストを記憶するステップと、
前記巡回経路探索手段が、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出するステップと、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えるステップと、を含み巡回経路探索を進めることを特徴とする巡回経路探索方法。
【請求項１２】
前記２地点間経路探索手段が最短経路を探索してその最適経路および経路コストを記憶するステップは、２地点間の経路を有向リンクとして取り扱い、両方向の経路コストを算出して記憶する処理を含むことを特徴とする請求項１１に記載の巡回経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１４】
【図１５】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１４】
【図１５】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００７−１８７５８４（Ｐ２００７−１８７５８４Ａ）
【公開日】平成１９年７月２６日（２００７．７．２６）
【国際特許分類】
【出願番号】特願２００６−６７０３（Ｐ２００６−６７０３）
【出願日】平成１８年１月１３日（２００６．１．１３）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成１９年７月２６日（２００７．７．２６）
【国際特許分類】
【出願日】平成１８年１月１３日（２００６．１．１３）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]