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