JP2012167942A - 最適経路検索システム及び最適経路検索方法 - Google Patents

Abstract

【課題】移動手段の特徴を考慮して、複数の移動手段を組み合わせて、所定の業務を効率よく行うための最適経路を検索する。
【解決手段】一以上の計算機を備え、移動体の移動経路を最適化する最適経路検索システムであって、計算機は、ノード及びノード間を接続するリンクから構成される経路ネットワークを管理する経路ネットワーク管理情報を含む経路情報データベースと、移動体の移動コストが最小となる最適経路を検索する経路検索部とを備え、経路検索部は、目的地点を決定し、目的地点毎に最近傍ノードを検索し、移動体が全ての目的地点及び少なくとも一以上の最近傍ノードを移動する移動経路を検索して、移動体が検索された移動経路を移動するために必要な移動コストを算出し、算出された移動コストが最小となる移動経路を前記最適経路に決定し、移動体が最適経路上を移動するための各移動手段を用いた移動経路を検索とする。
【選択図】図１

Description

本発明は、所定の業務を遂行するために複数の移動体の移動経路を最適化する技術に関する。

圃場に作付けされる作物の品目の調査業務は、一般的な方法として、調査員が主に紙の地図に頼って対象圃場を探して行われている。

当該調査業務においてカーナビゲーションシステムを補助的に利用することは可能であるが、カーナビゲーションシステム用の地図には、一部の農道は及び圃場間のあぜ道等は通常登録されていない。これは、一定の幅以下の道路は運転の難易度が高いため、一般利用者向けのカーナビゲーションシステムでは、前述したようなあぜ道等を経路として提示することが不適切であるからである。

したがって、調査対象圃場の付近を目的地として設定してカーナビゲーションシステムを利用することは可能であるが、目的地点に到着した後は、調査員が紙の地図に頼って圃場を探す必要がある。

前述の調査業務では、調査対象圃場まで車での通行が困難な細い農道、及び車で通行できないあぜ道を移動する必要がある。したがって、調査経路の最適化は、自動車による移動と、徒歩による移動との組み合わせを考慮した最適化問題となる。

前述した課題に対する解決策として、例えば、徒歩及び交通公共機関を用いた移動を組み合わせた最適経路を提示する技術が知られている（例えば、特許文献１参照）。また、タクシー及びレンタカーが利用可能な駅と、タクシー及びレンタカーが利用できない駅とを考慮した最適経路を検索する方法が知られている（例えば、特許文献２参照）。これによって、最寄りの駅で降りて長時間歩くルートよりも、目的地への距離は長くてもタクシーが使えるため結果として早く目的地に到着するルートを提示し、また、最寄りの駅ではないが終電が遅くタクシーが利用できる駅を降車地として提示できる。

その他にも、徒歩及び自動車などの複数の移動体が異なる出発点から同一の目的地まで向かう場合に、自動車に乗車して移動する人が、徒歩で移動する人を途中で乗車させることを考慮して、それぞれの移動体の最適経路を検索する技術が知られている（例えば、特許文献３参照）。また、医師又は看護士の代わりに薬品等の医療資材を病室まで運搬する機材運搬ロボットの移動経路を検索する技術が知られている（例えば、特許文献４参照）。

特開２００３−１０６８５８号公報 特開２００６−２９２４４７号公報 特開２００５−１４０６６４号公報 特開２００５−２８８６２８号公報

しかし、特許文献１に記載の技術では、交通公共機関及びタクシーの移動スケジュールは、利用者の都合に合わせて最適化される訳ではない。また、利用者の都合に合わせて経路を変更可能なタクシーを利用する場合であっても、出発地点にタクシーを呼ぶ場合と駅においてタクシーに乗車する場合とについてのみ記載されており、徒歩による移動と自動車を利用した移動とを最適化する経路を検索するものではない。また、特許文献２に記載の技術も、特許文献１に記載の技術と同様に、タクシーの移動スケジュールを最適化することについては記載されていない。

また、特許文献３に記載の技術では、目的地点が同一かつ一つであるため、複数の目的地点を移動する圃場における調査業務には適用できない。また、調査員が、車を用いて所定の地点まで移動し、その後、車では通行不可能な地点で調査を行うために車を降りるような最適経路を検索することができない。

また、特許文献４に記載の技術では、医師又は看護士の目的地点、及び機材運搬ロボットの目的地点は、複数ではあるが、いずれも同一の目的地点を通過する経路であるため、異なる経路を移動する移動体の移動経路の最適化をすることができない。

すなわち、本発明で解決しようとする課題は、圃場調査又は収穫作業など、複数種類の移動手段を考慮し、複数の移動手段を組み合わせて、所定の業務を効率よく行うための最適経路を検索可能な方法及びシステムを提供することである。

本発明の代表的な一例を示せば以下の通りである。すなわち、一以上の計算機を備え、移動体の移動経路を最適化する最適経路検索システムであって、前記計算機は、前記移動体が移動可能な地点を表す複数のノード及び前記ノード間を接続する複数のリンクから構成される経路ネットワークを管理する経路ネットワーク管理情報、並びに、前記リンクの移動時に用いられる移動手段毎に、当該移動手段を用いて前記リンクを移動するために必要な移動コストを管理する移動コスト管理情報を含む経路情報データベースと、前記移動体の移動経路のうち、当該移動体の移動コストが最小となる最適経路を検索する経路検索部と、前記検索された最適経路に関する情報を出力する出力部と、を備え、前記経路検索部は、前記経路ネットワーク上の目的地点を決定し、前記経路情報データベースを参照して、前記目的地点から、前記複数の移動手段を用いて移動可能な前記ノードである交点ノードへの第１の移動経路を検索して、前記移動体が前記検索された第１の移動経路を移動するために必要な第１の移動コストを算出し、前記目的地点毎に、前記算出された第１の移動コストが最小となる前記交点ノードである最近傍ノードを検索し、前記経路情報データベースを参照して、前記移動体が前記全ての目的地点及び少なくとも一以上の前記最近傍ノードを移動する第２の移動経路を検索して、前記移動体が前記検索された第２の移動経路を移動するために必要な第２の移動コストを算出し、前記算出された第２の移動コストが最小となる前記第２の移動経路を前記最適経路として決定し、前記経路情報データベースを参照して、前記移動体が前記最適経路上を移動するための前記各移動手段を用いた移動経路を検索し、前記出力部は、前記最適経路及び前記各移動手段の移動経路に関する情報を表示するためのデータを出力することを特徴とする。

検索される移動経路の最適性を満たすとともに計算量を削減し、移動体の移動経路が最適になるように各移動手段の移動経路を決定することできる。

本発明の第１の実施形態の最適経路検索システムの構成の一例を説明するブロック図である。 本発明の第１の実施形態における経路ネットワークの一例を示す説明図である。 本発明の第１の実施形態における経路ネットワークの別形態を示す説明図である。 本発明の第１の実施形態における経路ネットワークの別形態を示す説明図である。 本発明の第１の実施形態の経路ネットワークＤＢに格納されるノード情報テーブルの一例を示す説明図である。 本発明の第１の実施形態の経路ネットワークＤＢに格納される移動コスト情報テーブルの一例を示す説明図である。 本発明の第１の実施形態のサーバが実行する最適経路の検索処理を説明するフローチャートである。 本発明の第１の実施形態における経路ネットワークの一例を示す説明図である。 本発明の第１の実施形態におけるグループ間を接続する最適経路の一例を示す説明図である。 本発明の第１の実施形態のサーバが実行する最近傍ノードの検索処理を説明するフローチャートである。 本発明の第１の実施形態におけるリストの一例を示す説明図である。 本発明の第１の実施形態における目的地点と最近傍ノードとのペアの一例を示す説明図である。 本発明の第１の実施形態におけるペアのグループ化処理を説明するフローチャートである。 本発明の第１の実施形態において運転手がいる場合の最適経路の一例を示す説明図である。 本発明の第１の実施形態において運転手がいない場合の最適経路の一例を示す説明図である。 本発明の第１の実施形態におけるグループの分割の一例を示す説明図である。 本発明の第１の実施形態におけるペアのグループ化処理を説明するフローチャートである。 本発明の第１の実施形態におけるグループの結合例を示す説明図である。 本発明の第２の実施形態における最適経路検索システムの構成例を示すブロック図である。 本発明の第２の実施形態のサーバが実行する最適経路検索処理を説明するフローチャートである。 本発明の第２の実施形態における経路ネットワークの一例を示す説明図である。 本発明の第２の実施形態における経路ネットワークの一例を示す説明図である。 本発明の第２の実施形態における経路ネットワークの一例を示す説明図である。

［第１の実施形態］
第１の実施形態では、調査員が水田、畑などの圃場を調査する場合に、自動車による移動と、徒歩による移動とを組み合わせた最適経路を検索する最適経路検索システムについて説明する。以下、自動車による移動を自動車移動と呼び、徒歩による移動を徒歩移動と呼ぶ。

図１は、本発明の第１の実施形態の最適経路検索システムの構成の一例を説明するブロック図である。

第１の実施形態における最適経路検索システムは、調査員が携行する端末１００と、最適経路の検索処理を実行するサーバ１０１と、端末１００及びサーバ１０１を接続するネットワーク１０２とから構成される。なお、図１では、端末１００及びサーバ１０１はそれぞれ一つであるが複数あってもよい。

端末１００は、制御部１０４、入力部１０５、表示部１０６、位置検出部１０７及び通信部１０８を備え、各構成はデータ通信バス１０３によって互いに接続される。なお、端末１００は、他の構成を含んでいてもよい。

制御部１０４は、端末１００の備える機能を実現するための処理を実行する。制御部１０４は、例えば、プロセッサ等によって実現できる。

入力部１０５は、調査員からの情報の提示要求及び経路検索条件の設定要求などを受付ける。入力部１０５は、ボタン、タッチパネルなどによって実現できる。

表示部１０６は、調査員に地図画像及び経路情報等の情報を表示する。表示部１０６は、例えば、液晶ディスプレイ等によって実現できる。

位置検出部１０７は、端末１００の現在位置を検出する。位置検出部１０７は、例えば、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）、又は自立航法ユニット等によって実現できる。

通信部１０８は、ネットワーク１０２を介してサーバ１０１と通信する。具体的には、通信部１０８は、端末１００の現在位置に関する情報、情報の提示要求、及び経路検索条件の設定要求等をサーバ１０１に送信し、また、端末１００の現在位置周辺の地図画像、及び最適経路情報等をサーバ１０１から受信する。通信部１０８は、携帯電話通信カード又はＷｉＭＡＸ通信カードなどによって実現できる。

なお、端末１００が備える各構成はソフトウェアを用いて実現してもよい。例えば、携帯電話、スマートフォン、携帯ゲーム機、カーナビゲーションシステム、ＰＮＤ（Ｐｅｒｓｏｎａｌ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ）等の既存の機器に、各構成を実現するソフトウェアを導入することによって、端末１００として利用することもできる。

また、端末１００の形態はどのようなものであってもよく、調査員が徒歩での移動中に携帯できる端末１００、又は自動車に設置可能な端末１００でもよい。

サーバ１０１は、自動車移動と徒歩移動とを組み合わせた最適な圃場調査経路（最適経路）を検索し、検索された最適経路に関する情報を端末１００に送信する。

サーバ１０１は、制御部１１０、入力部１１１、表示部１１２、通信部１１３、経路ネットワークＤＢ１１４、地図ＤＢ１１５及び経路検索部１１６を備え、各構成はデータ通信バス１０９によって互いに接続される。

制御部１１０は、サーバ１０１が備える機能を実現するための処理を実行する。制御部１１０は、例えば、プロセッサによって実現できる。また、制御部１１０は、処理に必要な情報を格納する記憶部（図示省略）を備える。

入力部１１１は、サーバ１０１を操作するオペレータがサーバ１０１の操作を行うためのインタフェースである。入力部１１１は、例えば、キーボード、マウス、ボタン、及びタッチパネル等によって実現できる。オペレータは、入力部１１１を用いて緯度及び経度情報、又は、経路ネットワークのノード番号を入力し、調査員が調査のために移動する場所を指定する。以下、調査員が調査のために移動する場所を目的地点と呼ぶ。

表示部１１２は、オペレータに対して各種情報を表示する。表示部１１２は、例えば、液晶ディスプレイ等によって実現される。

通信部１１３は、ネットワーク１０２を介して一以上の端末１００と通信する。通信部１１３は、端末１００に最適経路に関する情報を送信し、また、端末１００の現在位置に対応する周辺地図画像を当該端末１００に送信する。通信部１１３は、例えば、ネットワークカード等によって実現できる。

経路ネットワークＤＢ１１４は、経路ネットワークに関する情報を格納する。ここで、経路ネットワークは、地点を表すノードと、当該ノード間を接続するリンクとから構成される。経路ネットワークには、自動車移動が可能な道路、自動車移動が可能な農道、及び徒歩移動のみが可能なあぜ道等の情報が含まれる。経路ネットワークについては、図２、図３Ａ及び図３Ｂを用いて後述する。

地図ＤＢ１１５は、ラスター形式又はベクター形式で表現された地図画像を格納する。地図ＤＢ１１５には、例えば、国土地理院等によって作成された５０ｍメッシュ標高データ等が格納される。なお、地図画像には、ＪＰＥＧ、ＰＮＧ及びＴＩＦＦなどの形式を用いることができる。

また、地図ＤＢ１１５は、解像度ごとに地図画像を格納し、さらに区域ごとに分割して当該地図画像を格納する。これによって、端末１００の現在位置が変化した場合、サーバ１０１は端末１００に適切な区域かつ適切な解像度の地図画像を送信することができる。したがって、端末１００には現在位置に応じた地図が表示される。なお、ベクター形式の地図画像としてはＳＶＧ（Ｓｃａｌａｂｌｅ Ｖｅｃｔｏｒ Ｇｒａｐｈｉｃｓ）などが利用できる。

経路検索部１１６は、調査員が全ての目的地点を最も効率よく移動するための最適経路を検索し、検索された最適経路に関する情報をオペレータ又は調査員に対して出力する。本実施形態では、自動車移動と徒歩移動とを組み合わせた最適経路が検索される。

ここで、二つの移動手段を組み合わせた最適な経路とは、自動車を利用して移動する経路、自動車を降りる地点、徒歩で移動する経路、及び再び自動車に乗り込む地点がそれぞれ最適に決定された経路を表す。以下では、最適経路における自動車を乗り降りする地点を離合点と呼ぶ。

図２は、本発明の第１の実施形態における経路ネットワークの一例を示す説明図である。

図１で述べたように、経路ネットワークは、複数のノード２０１と、複数のリンク２０２とから構成される。ノード２０１は、調査員が移動可能な地点を表す。ノード２０１には、経路ネットワーク上で一意に識別可能な識別子が付与される。なお、以下の説明では、ノード２０１には、自動車移動が可能か否かを示す属性情報が付与される。また、リンク２０２には、自動車移動及び徒歩移動の移動時間に関する情報（移動コスト情報２０３）が付与される。

以下、自動車移動及び徒歩移動の移動時間を移動コストと呼ぶ。また、自動車移動が可能か否かを表す属性情報を属性情報と呼び、自動車移動及び徒歩移動の移動時間に関する情報を移動コスト情報２０３と呼ぶ。

図２に示す例では、ノードＫ２０１及びノードＬ２０１は、自動車移動が不可能なノード２０１を表す。本実施形態では、自動車移動が可能なノード２０１を実線の円を用いて表現し、また、自動車移動が不可能なノード２０１を点線の円を用いて表現する。

また、以下では、経路ネットワークを構成するノード２０１のうち、自動車移動及び徒歩移動の両方で到達又は通過可能なノード２０１を交点ノード２０１とも呼ぶ。図２に示す例では。ノードＡ２０１〜ノードＪ２０１が交点ノード２０１となる。

リンク２０２は有向リンクであり、一方通行を表現することもできる。ただし、本実施形態では説明を簡単にするため、リンク２０２における移動コストが移動方向に依存せずかつ同一である場合、すなわち、無向リンクの場合を例に説明する。

移動コスト情報２０３は、リンク２０２における各移動手段の移動コストを格納する。

図２に示す例では、移動コスト情報２０３には自動車移動及び徒歩移動それぞれの移動コストが格納される。具体的には、移動コスト情報２０３のうち、上段は徒歩移動の移動コストを表し、下段は自動車移動の移動コストを表す。

なお、移動コスト情報に設定される「−」は、対応する移動手段による移動が不可能なことを表す。「−」を計算機上で表す方法としては、最大整数値等の大きな値を移動コストとして与えることで可能となる。

また、リンク２０２には、道路、農道又はあぜ道等の道路の種別を表す道路種別情報が付与されてもよい。リンク２０２に道路種別情報が付与される場合、自動車移動の移動コストが「−」となっているリンクは「あぜ道」の道路種別情報が付与されていることを表す。

なお、経路ネットワークに属性情報が含まれない場合、以下のような方法を用いて自動車移動が可能なノード２０１を特定することができる。

サーバ１０１が、リンク２０２が保持する自動車移動の移動コスト情報を用いて、所定のスタート地点からノード２０１を深さ優先探索法で順次たどる。このとき、サーバ１０１は、一度たどったノード２０１には自動車移動が可能であることを示すマークを付与し、マークが付与された時点で深さ方向の探索を打ち切る。これによって、スタート地点から自動車移動が可能な全てのノード２０１を特定することができる。したがって、経路ネットワークには、ノード２０１の属性情報が含まれていなくてもよい。

図２は、典型的な圃場周辺の道路を表現した経路ネットワークであり、あぜ道によって６つの圃場に分割される。図２に示すように、自動車移動が可能なリンク２０２（道路又は農道）を徒歩で移動する場合の移動コストは、あぜ道を移動する場合と比較して少ない。

図２に示す例では、自動車移動が可能な経路、及び徒歩移動が可能な経路を一つの経路ネットワークとして表現している。しかし、経路ネットワークはこれに限定されず、例えば、移動手段毎に保持されてもよい。

図３Ａ及び図３Ｂは、本発明の第１の実施形態における経路ネットワークの別形態を示す説明図である。

図３Ａは自動車移動に関する経路ネットワークを表し、図３Ｂは徒歩移動に関する経路ネットワークを表す。なお、それぞれの経路ネットワークにおいて同一の識別子のノード２０１は同一地点を表す。

次に、経路ネットワークＤＢ１１４に格納される具体的な情報の一例を説明する。

図４Ａは、本発明の第１の実施形態の経路ネットワークＤＢ１１４に格納されるノード情報テーブル４００の一例を示す説明図である。図４Ｂは、本発明の第１の実施形態の経路ネットワークＤＢ１１４に格納される移動コスト情報テーブル４１０の一例を示す説明図である。

ノード情報テーブル４００は、ノード２０１の管理情報を格納する。ノード情報テーブル４００は、ノード識別子４０１、車両移動４０２、経度４０３及び緯度４０４を含む。

ノード識別子４０１は、ノード２０１を一意に識別するための識別子を格納する。

車両移動４０２は、ノード識別子４０１に対応するノード２０１が自動車移動による移動が可能か否かを示す情報を格納する。本実施形態では、自動車移動による移動が可能な場合には「Ｔｒｕｅ」が格納され、自動車移動による移動が不可能な場合には「Ｆａｌｅｓ」が格納される。

経度４０３及び緯度４０４は、ノード識別子４０１に対応するノード２０１の位置を表す経度及び緯度を格納する。

移動コスト情報テーブル４１０は、一つのリンク２０２に対する各移動手段の移動コストの管理情報を格納する。移動コスト情報テーブル４１０は、リンク識別子４１１、ノード識別子４１２、ノード識別子４１３、移動コスト（自動車）４１４、移動コスト（徒歩）４１５及び道路種別４１６を含む。

リンク識別子４１１は、リンク２０２を一意に識別するための識別子を格納する。

ノード識別子４１２及びノード識別子４１３は、リンク識別子４１１に対応するリンク２０２が接続するノード２０１を一意に識別するための識別子を格納する。

移動コスト（自動車）４１４は、リンク識別子４１１に対応するリンク２０２を、自動車を用いて移動した場合の移動コストを格納する。

移動コスト（徒歩）４１５は、リンク識別子４１１に対応するリンク２０２を、徒歩で移動した場合の移動コストを格納する。

道路種別４１６は、リンク２０２に対応する道路の道路種別情報を格納する。道路種別４１６には、「あぜ道」及び「道路」等の情報が格納される。

なお、ノード識別子４１２及びノード識別子４１３を用いてリンク２０２を特定できるためリンク識別子４１１は必ずしも必要ではない。

以下、最適経路を検索するための具体的な処理について説明する。

図５は、本発明の第１の実施形態のサーバ１０１が実行する最適経路の検索処理を説明するフローチャートである。図６は、本発明の第１の実施形態における経路ネットワークの一例を示す説明図である。

以下の説明では、図６に示すような経路ネットワークを例に説明する。

まず、サーバ１０１は、目的地点を決定する（ステップ５０１）。ここで、目的地点は、作付け判別調査において、調査員が圃場内における作物の品目を確認するために訪れる場所に相当し、また、坪刈り調査において、調査員が坪刈りを行うために圃場に立ち入るための場所に相当する。なお、調査にかかる時間は圃場の大きさ及び調査内容の種類によって異なるが、調査経路とは独立であると仮定し、本実施形態の検索処理では考慮しない。

以下では、図６に示すように、ノードＬ２０１及びノードＫ２０１が目的地点として決定された場合を例に説明する。以下、目的地点として決定されたノードＬ２０１及びノードＫ２０１を目的地点Ｌ及び目的地点Ｋと呼ぶ。

なお、目的地点はノード２０１に限定されず、リンク２０２上に目的地点を決定することも可能できる。この場合、リンク２０２上の目的地点に新たなノード２０１を追加し、さらに、リンク２０２を分割して新たに追加されたノード２０１を目的地点として決定することと同等である。したがって、以下ではノード２０１が目的地点として決定された場合について説明する。

サーバ１０１は、オペレータが作業内容を考慮して指定して情報に基づいて目的地点を決定してもよいし、経路ネットワークＤＢ１１４及び地図ＤＢ１１５を参照して、自動的に目的地点を決定してもよい。サーバ１０１が自動的に目的地点を決定する方法としては以下のようなものが考えられる。

作付け判別調査の場合、サーバ１０１は、例えば、経路ネットワークにおける部分的なループのうち、１つでも農道又はあぜ道に面しているループを圃場とし、当該ループを構成するノードのうち、他の圃場も構成するノード２０１を優先的に目的地点として決定する。さらに、サーバ１０１は、少なくとも圃場を表すループを構成するノード２０１のうち少なくとも１つのノード２０１が目的地点として指定されるまで目的地点を追加する。以上の処理によって、自動的に目的地点が決定される。ここで、経路ネットワークから部分的なループを抽出する方法としては次のようなものが考えられる。

すなわち、任意のノード２０１からリンク２０２をたどって次のノード２０１に移動する場合に、最も右方向に出ているリンクを選択して次のノードへ移動するという処理を繰り返すことによってサーバ１０１はループを抽出できる。

一般的な経路ネットワークでは「最も右方向」なリンクを特定することはできないが、本実施形態の経路ネットワークＤＢ１１４のノード情報テーブル４００には緯度及び経度の情報が含まれるため、サーバ１０１は当該情報からノード２０１を接続するリンクの地図上での向きを把握することができる。サーバ１０１は、一度たどったリンク２０２にはマークを付与し、次のループの抽出処理ではたどっていないリンク２０２を選択して同様の処理を実行する。

なお、第１のノード及び第２のノードを接続するリンク２０２において、サーバ１０１は、第１のノードから第２のノードの方向へ移動と、第２のノードから第１のノードの方向へ移動とは区別してマークを付与する。

また、サーバ１０１が自動的に目的地点を決定する方法としては、次のような方法も考えられる。圃場まで行かなくとも離れた場所から作付けの判別が可能な場合、サーバ１０１が、地図ＤＢ１１５に格納される国土地理院等によって作成された５０ｍメッシュ標高データ等を参照して、見晴らしのよい場所を目的地点として決定し、決定された目的地点から見通せる圃場以外に対して、前述した決定方法を用いて他の目的地点を決定する。

以上が、サーバ１０１が自動的に目的地点を決定する方法の説明である。図５の説明に戻る。

次に、サーバ１０１は、決定された目的地点毎に所定の条件を満たすノード２０１である最近傍ノード２０１を検索し、目的地点と最近傍ノード２０１とのペアを生成する（ステップ５０２）。ここで、最近傍ノード２０１とは、目的地点から移動可能な交点ノード２０１であって、かつ、目的地点からの移動コストが最小となる交点ノード２０１を表す。

なお、最近傍ノード２０１の検索処理及びペアの生成処理の詳細については、図８を用いて後述する。

次に、サーバ１０１は、生成されたペアに基づいて、１以上のグループを生成する（ステップ５０３）。ここで、グループとは、少なくとも１つ以上のペアを含む経路ネットワークの部分集合を表す。

グループの生成方法としては、（方法１）全体を１つのグループとして分割する方法、（方法２）ペア同士及びグループ同士を組み合わせてグループを生成する方法、（方法３）最初に適当なグループを生成して調整する方法の３つの方法が考えられる。詳細は後述する。

次に、サーバ１０１は、生成されたグループ内における最適経路を検索する（ステップ５０４）。複数のグループが生成された場合、各グループについて最適経路が検索される。サーバ１０１は、グループ毎に最適経路を検索することによって、計算量を減らすことが可能となる。

グループ内の最適経路の検索処理では、サーバ１０１は、グループ内の全ての目的地点と少なくとも１つ以上の最近傍ノード２０１とを移動し、かつ、移動コストが最小となる最適経路を検索する。このとき、最近傍ノード２０１の中から離合点が決定されることとなる。

なお、離合点が２つ以上含まれる場合、以下のようにして最適経路が検索される。

自動車移動については、離合点間の移動コストが最小となる経路が検索される。徒歩移動については、離合点から移動を開始して、一以上の目的地点を経由して離合点へ至る移動コストが最小になる経路が検索される。なお、到着地点となる離合点は、移動開始点とした離合点と同一であってもよい。

より具体的には、目的地点を経由しない離合点間の移動では、自動車移動による移動コストが最小となる経路が検索される。また、少なくとも一以上の目的地点を経由する離合点間の移動については、徒歩移動による移動コストが最小となる経路が検索される。すなわち、自動車移動による経路と徒歩移動による経路とが最適化される。

ステップ５０４では、少なくとも１つ以上の最近傍ノード２０１を含むという条件の下、グループ内の目的地点を最小の移動コストで全て移動する経路が検索される。これによって、経路の最適性を保ち、かつ、検索処理の計算量を削減することができる。

なお、ステップ５０３の処理において、各グループにおける最適経路及び当該最適経路の移動コストが算出されている場合、ステップ５０４と同様の処理がすでに実行されているためステップ５０４の処理は省略できる。

次に、サーバ１０１は、全てのグループ間を１回ずつ移動する最適経路を検索する（ステップ５０５）。すなわち、グループ間の移動経路の最適化が実行される。

本実施形態におけるグループ間の最適経路は、ステップ５０４において検索された一つのグループにおける最適経路の終了地点と、他のグループにおける最適経路の開始地点とを結ぶ経路の中から検索される。なお、無向リンクを仮定する場合、開始地点と終了地点とを入れ替えることができる。

ステップ５０５の処理が終了した後に、サーバ１０１は、検索された最適経路に関する情報を表示するための出力情報を生成して、当該出力情報を端末１００に送信する。

ステップ５０５の検索処理は、巡回セールスマン問題として取り扱うことができる。巡回セールスマン問題はＮＰ困難な問題であるが、グループ数が所定数以下であれば、サーバ１０１は分枝限定法などの既存の方法を用いて実用的な時間で最適経路を検索できる。また、あらかじめ最適経路検索の対象となる地域ごとに本実施形態におけるサーバ１０１を用いることによって、膨大な計算量の発生を回避することができる。

図７は、本発明の第１の実施形態におけるグループ間を接続する最適経路の一例を示す説明図である。

図７では、グループ７０１とグループ７０２とを接続する最適経路を示す。各グループ内の目的地点は黒丸で表し、グループ内の最適経路は太線で表している。

図７に示すように、本実施形態では、ノードＡとノードＢとの間を接続する経路がグループ７０１とグループ７０２との間を接続する最適経路となる。

なお、ノードＣとノードＤとの間を結ぶ経路が最適経路となるように各グループ内の経路を変更した方が、全体としての移動コストが最小となる可能性も考えられる。しかし、グループ内及びグループ間の移動コストを考慮して、全ての開始地点及び終了地点の組み合わせに対して検索処理を実行すると、計算量が著しく増大してしまう。

本実施形態では、目的地点を全て通過する最適経路を検索する処理において、目的地点及び最近傍ノード２０１を含むグループ内の最適経路を検索し、さらに、グループ間を接続する最適経路を検索することによって計算量を削減する。より具体的には、グループ内の開始地点及び終了地点を固定し、グループ間の移動では自動車移動を用い、徒歩移動を含むグループ内の最適化を優先的に行うように検索処理を実行することによって、計算量を大幅に削減する効果がある。

以上で述べた処理によって、サーバ１０１は、自動車移動と徒歩移動とを組み合わせた最適経路を検索できる。

次に、ステップ５０２における最近傍ノード２０１の検索処理について説明する。

図８は、本発明の第１の実施形態のサーバ１０１が実行する最近傍ノード２０１の検索処理を説明するフローチャートである。

まず、サーバ１０１は、目的地点を一つ選択する（ステップ８０１）。ステップ８０２以下の処理は選択された目的地点毎に実行される。すなわち、各目的地点についてステップ８０２〜ステップ８０８の処理が実行される。

サーバ１０１は、経路ネットワークＤＢ１１４を参照して、選択された目的地点に自動車移動による移動が可能であるか否かを判定する（ステップ８０２）。すなわち、目的地点が交点ノード２０１であるか否かが判定される。

具体的には、サーバ１０１は、選択された目的地点のノード識別子に基づいてノード情報テーブル４００を参照し、対応するエントリの車両移動４０２が「Ｔｒｕｅ」であるか否かを判定する。対応するエントリの車両移動４０２が「Ｔｒｕｅ」である場合には、目的地点が交点ノード２０１であると判定される。

ステップ８０３以下の処理では、最近傍ノード２０１の候補となるノード２０１を検索し、ステップ８０３〜ステップ８０８のループ処理によって当該ノード２０１を更新して真の最近傍ノード２０１が検索される。以下では、最近傍ノード２０１の候補となるノード２０１を候補ノード２０１とも呼ぶ。

目的地点が交点ノード２０１であると判定された場合、サーバ１０１は、目的地点そのものが最近傍ノード２０１となるため処理を終了する。

目的地点が交点ノード２０１でないと判定された場合、サーバ１０１は、初期化処理を実行する（ステップ８０３）。

具体的には、サーバ１０１は以下の処理を実行する。

サーバ１０１は、候補ノード２０１にダミーのノード（以下、ダミーノード２０１と呼ぶ）を設定する。また、サーバ１０１は、ダミーノード２０１へ移動するためのリンク２０２の移動コストに大きな値を設定する。初期化処理は、候補ノード２０１が再度候補ノード２０１として検索されることを防止するための処理である。なお、初めて処理が実行される場合には、ダミーノード２０１の設定処理を省略してもよい。

また、サーバ１０１は、最近傍ノード２０１を検索するためのリスト９００を生成する。

図９は、本発明の第１の実施形態におけるリスト９００の一例を示す説明図である。

リスト９００は、ノード識別子９０１、累積移動コスト９０２及び経路９０３を含む。

ノード識別子９０１は、候補ノード２０１を識別するための識別子を格納する。累積移動コスト９０２は、目的地点からノード識別子９０１に対応するノード２０１までの移動コストを格納する。経路９０３は、目的地点からノード識別子９０１に対応するノード２０１までの移動経路に関する情報を格納する。経路９０３には、例えば、目的地点から移動する順にノード２０１の識別子を並べたものが格納される。ただし、移動経路が分かる情報であればどのような形式の情報であってもよい。

初めて、初期化処理が実行される場合、ノード識別子９０１には選択された目的地点の識別子が格納され、累積移動コスト９０２には「０」が格納され、経路９０３には移動経路がない旨の情報が格納される。ステップ８０３以降の処理では、リスト９００を用いて処理が実行される。

初期化処理を実行した後に、サーバ１０１は、経路ネットワークＤＢ１１４及びリスト９００を参照して、隣接ノード２０１を検索する（ステップ８０４）。

具体的には、サーバ１０１は、リスト９００から最も累積移動コスト９０２の値が最も小さいノード２０１を選択して、選択されたノード２０１に隣接する隣接ノード２０１を検索する。

ここで、隣接ノード２０１とは、ノード識別子９０１に対応するノード２０１と直接リンク２０２によって接続されるノード２０１を表す。すなわち、ノード識別子９０１に対応するノード２０１から１ステップで移動可能なノードを表す。

次に、サーバ１０１は、隣接ノード２０１に関する情報をリスト９００に追加する（ステップ８０５）。

具体的には、サーバ１０１は、対応するエントリのノード識別子９０１に隣接ノード２０１の識別子を格納する。また、サーバ１０１は、隣接ノード２０１までの移動経路を検索し、当該移動経路を経路９０３に格納する。また、サーバ１０１は、目的地点から隣接ノード２０１までの移動コストを算出し、累積移動コスト９０２に算出された移動コストを格納する。

次に、サーバ１０１は、経路ネットワークＤＢ１１４及びリスト９００を参照して、候補ノード２０１を選択する（ステップ８０６）。

具体的には、以下のような処理が実行される。

サーバ１０１は、経路ネットワークＤＢ１１４のノード情報テーブル４００を参照して、リスト９００から交点ノード２０１に対応するエントリを一以上抽出する。

サーバ１０１は、抽出されたエントリの中から、累積移動コスト９０２が最小かつ現在の候補ノード２０１への累積移動コスト９０２より小さい交点ノード２０１のエントリをすべて選択する。サーバ１０１は、選択されたエントリに対応する交点ノード２０１を候補ノード２０１として選択する。すなわち、現在の候補ノード２０１が選択された交点ノード２０１に置き換えられる。

前述の条件を満たすエントリがない場合、サーバ１０１は、累積移動コスト９０２が最小かつ現在の候補ノード２０１への累積移動コスト９０２と等しいエントリをすべて選択する。サーバ１０１は、選択されたエントリを候補ノード２０１として追加する。

さらに、サーバ１０１は、リスト９００から交点ノード２０１に対応するエントリを削除する。なお、この時点でリスト９００にエントリが無い場合、当該候補ノード２０１が真の最近傍ノード２０１となるため、サーバ１０１は処理を終了してもよい。また、交点ノード２０１以外のノード２０１に対応するエントリは、リスト９００から削除されない。

次に、サーバ１０１は、リスト９００を更新する（ステップ８０７）。

具体的には、サーバ１０１は、経路ネットワークＤＢ１１４を参照して、累積移動コスト９０２が候補ノード２０１の累積移動コスト９０２以上となるノード２０１をリスト９００から削除する。

次に、サーバ１０１は、リスト９００にエントリが存在するか否かを判定する（ステップ８０８）。

リスト９００にエントリが存在すると判定された場合、サーバ１０１は、ステップ８０３に戻り同様の処理を実行する。なお、ステップ８０３における初期化処理において、候補ノード２０１の移動コストに大きな値を設定するのは、当該最近傍ノード２０１が重複して選択されるのを防止するためである。

リスト９００にエントリが存在しないと判定された場合、サーバ１０１は、現在の候補ノード２０１を最近傍ノード２０１と決定し、処理を終了する。

以上に処理によって、最近傍ノード２０１、目的地点から最近傍ノード２０１までの移動コスト、及び目的地点から最近傍ノード２０１までの移動経路（最適経路）を検索することができる。

目的地点と最近傍ノード２０１とを結ぶ最適経路は、自動車を降りて最初の目的地点まで徒歩で移動する経路の候補であり、かつ、目的地点から徒歩移動で自動車に乗車可能な場所まで移動する経路の候補でもある。つまり、最近傍ノード２０１は、離合点の候補となるノード２０１である。

本実施形態では、離合点の候補を最近傍ノード２０１に限定することによって、全てのノード２０１を離合点として最適経路を検索する場合に比べて検索範囲を限定することができる。したがって、計算量の削減及び最適経路を検索処理の時間短縮という効果が得られる。

一方、検索範囲を限定することによって、真の最適経路と乖離した経路が検索される懸念がある。しかし、自動車移動と徒歩移動との移動コストは大きく異なるため、徒歩移動の移動コストが最小となるように経路の最適化を優先的に行い、最近傍ノード２０１のいずれかを離合点とすることによって、解の最適性を損なうことが極めて小さくなる。

前述の方法では、移動コストが最小となる候補ノード２０１が複数ある場合でもいずれか一つの候補ノード２０１が選択されるが、本発明はこれに限定されない。すなわち、複数の最近傍ノード２０１を抽出してもよい。この場合、それぞれの最近傍ノード２０１に対して、最適経路検索処理を実行して、最終的な離合点を決定する方法であってもよい。

なお、図６に示す例では、図１０に示すようなペアが生成される。すなわち、目的地点Ｌと最近傍ノードＧ２０１とのペアと、目的地点Ｋと最近傍ノードＢ２０１とのペアが生成される。

次に、ステップ３０３におけるペアのグループ化の方法について説明する。

図１１は、本発明の第１の実施形態におけるペアのグループ化処理を説明するフローチャートである。

図１１では、（方法１）に対応するグループ化処理、すなわち、全体を１つのグループとして分割するグループ化処理について説明する。なお、以下では、図６を例に説明する。

最初に、サーバ１０１は、全体を１つのグループとして未処理グループリストに追加する（ステップ１１０１）。図６の場合、図６に示す経路ネットワークが一つのグループとして未処理グループリストに追加される。

次に、サーバ１０１は、未処理グループリストから処理対象となるグループを１つ選択し、選択されたグループにおける最適経路を検索し、さらに、検索された最適経路の移動コストを算出する（ステップ１１０２）。なお、最適経路は、交点ノード２０１を開始点として、全ての目的地点を通過して、交点ノードを終了点とする経路の中から検索される。

ここで、グループ内の最適経路の検索方法について説明する。

グループ内の全ての目的地点を通過する最適経路を検索する問題も、巡回セールスマン問題として取り扱うことができ、目的地点の数が多くなければ、分枝限定法などの既存の手法を用いて実用的な時間で最適経路を検索できる。一方、目的地点の数が多い場合は、（方法１）よりも（方法２）及び（方法３）を用いることが好ましい。

なお、グループ内の最適経路の検索処理では、自動車を運転する運転手がいるか否かを考慮する必要がある。運転手がいる場合には、目的地点における調査及び徒歩移動中に自動車を別の地点に移動させることができるためである。したがって、運転手がいる場合にはグループ内での開始地点のノード２０１と終了地点のノード２０１とは異なってもよい。

例えば、図６の場合、ノードＡ２０１〜ノードＪ２０１の全てのノード２０１を開始地点とすることができ、さらに開始地点に依存することなく独立にノードＡ２０１〜ノードＪ２０１のいずれを終了地点とすることができる。

なお、ノード間の移動コストが移動方向に依存しない無向リンクの経路ネットワークでは、ノードＡ２０１を開始地点とし、ノードＨ２０１を終了地点とした経路と、逆方向に移動する経路とでは移動コストが同一となるため、いずれか片方の経路を検索すればよい。一方、有効リンクの経路ネットワークでは、最適経路を検索する場合は、同一経路であっても移動方向を考慮して両方の移動方向についての移動コストを算出する必要がある。

また、本実施形態では徒歩の移動中及び調査中に、自動車が交点ノード２０１まで移動を完了していると仮定しているが、当該仮定が成立しない場合は、降車地点から乗車地点までの自動車移動の移動コストと、徒歩移動での移動コスト及び調査コストとの合計を比較し、大きい方の移動コストを経路の移動コストとして考えればよい。

運転手がいない場合は、サーバ１０１は、開始地点と終了地点とが同一となるという条件の下、最適経路の検索処理を実行すればよい。

なお、運転手がいるか否かを示す情報は、オペレータ又は調査員が指定する。当該指定によって経路開始地点と経路終了地点とが同一であるか否かが決定される。

また、オペレータ又は調査員は、運転手がいるという条件と、運転手がいないという条件の両方の条件について最適経路の検索処理を実行するようにサーバ１０１に指示してもよい。この場合、サーバ１０１が、オペレータ又は調査員にそれぞれの条件における最適経路を表示することによって、調査時に運転手を同行させるか否かの判断を支援することができる。

さらに、サーバ１０１は、異なる条件における最適経路ごとの、調査時間の違い、必要とする燃料の違い、運転手を同行させた場合の人件費（又はタクシー代）等のコストを表示することもできる。また、サーバ１０１は、調査時間の違い及び燃料の違い等に対応する係数に基づいて調査に係る金額に換算し、いずれの条件のもと調査した方が金銭的に有利であるかを表示することもできる。

図６を例に運転手がいる場合、運転手がいない場合のそれぞれの最適経路は、図１２Ａ及び図１２Ｂに示すようになる。

図１２Ａは、本発明の第１の実施形態において運転手がいる場合の最適経路の一例を示す説明図である。図１２Ｂは、本発明の第１の実施形態において運転手がいない場合の最適経路の一例を示す説明図である。

図１２Ａ及び図１２Ｂは、調査員が移動する経路を示す。

図１２Ａに示すように、運転手がいる場合の調査員の最適経路は、経路（Ｂ、Ｋ、Ｌ、Ｇ）又は経路（Ｇ、Ｌ、Ｋ、Ｂ）となる。なお、自動車の運転手の移動経路は、経路（Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ）又は経路（Ｂ、Ａ、Ｊ、Ｉ、Ｈ、Ｇ）のいずれかが最適経路となる。

図１２Ｂに示すように、運転手がいない場合の最適経路は、経路（Ｂ、Ｋ、Ｌ、Ｃ、Ｂ）、経路（Ｂ、Ｃ、Ｌ、Ｋ、Ｂ）、経路（Ｃ、Ｌ、Ｋ、Ｂ、Ｃ）又は経路（Ｃ、Ｂ、Ｋ、Ｌ、Ｃ）となる。なお、経路（Ｂ、Ｋ、Ｌ、Ｃ、Ｂ）においてノードＣ２０１からノードＢ２０１へは徒歩移動による移動となる。他の経路についても同様である。

図１２Ａ及び図１２Ｂに示す最適経路では、自動車の乗降回数はそれぞれ１回ずつであるが、目的地点を全て通過する経路の中には、自動車の乗降回数がそれぞれ複数回になる経路も存在する。例えば、ノードＢ２０１を開始地点とし、徒歩でノードＫ２０１まで移動し、ノードＢ２０１に戻り、ノードＢ２０１で再び乗車し、自動車でノードＣ２０１まで移動し、ノードＣ２０１で自動車を降りて徒歩でノードＬ２０１まで移動し、さらに、ノード２０１Ｃに戻って乗車するという経路が考えられる。このような場合、最適経路の移動コストとして、乗降時のコストを考慮することもできる。

例えば、計測機器を車のトランクに積んで移動する場合、降車後の計測機器の準備、又は調査後の計測機器の収納にかかる時間が乗降時コストに相当する。この場合、サーバ１０１は、徒歩移動から自動車移動に交点ノード２０１において、所定の乗降時コストを加算して最適経路を検索すればよい。

図１１の説明に戻る。

次に、サーバ１０１は、グループを２つに分割する（ステップ１１０３）。

分割方法は様々考えられるが、例えば、目的地点間の地図上での位置（緯度及び経度）を用いて、距離尺度としてユークリッド距離を用いたＫ−ｍｅａｎｓ法等によって分割できる。

図１３は、本発明の第１の実施形態におけるグループの分割の一例を示す説明図である。

次に、サーバ１０１は、分割された各グループにおいて、交点ノード２０１を経路の開始地点として、全ての目的地点を通過し、交点ノード２０１を経路の終了地点とする最適経路を検索し、２つのグループそれぞれの移動コストＬ１、Ｌ２を算出する（ステップ１１０４）。最適経路の検索方法は、ステップ１１０２と同一であるため説明を省略する。

図１３のように分割された場合、上のグループでは経路（Ｇ、Ｌ、Ｇ）が最適経路となり、下のグループでは経路（Ｂ、Ｋ、Ｂ）が最適経路となる。

次に、サーバ１０１は、分割後の各グループにおける最適経路の移動コストが、分割前のグループにおける最適経路の移動コストより大きいか否かを判定する（ステップ１１０５）。

具体的には、分割前のグループにおける最適経路の移動コストをＬとし、分割後の各グループにおける最適経路の移動コストＬ１、Ｌ２とし、グループ間の移動に必要な移動コストＬＧとした場合、「Ｌ＞Ｌ１＋Ｌ２＋ＬＧ」を満たすか否かが判定される。

図１３に示す例では、グループ間の移動は、経路（Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ）又は経路（Ｂ、Ａ、Ｊ、Ｉ、Ｈ、Ｇ）の移動コストが最小となるため最適経路となる。

分割後の最適経路の移動コストが分割前の最適経路の移動コストより大きいと判定された場合、サーバ１０１は、分割後の方が全体としての移動コストが削減できるため、分割したグループを未処理グループリストに追加し（ステップ１１０６）、ステップ１１０２に戻り同様の処理を実行する。

分割後の最適経路の移動コストが分割前の最適経路の移動コスト以下と判定された場合、サーバ１０１は、分割前の方が全体として移動コストを削減できるため、分割前のグループを未処理グループリストから削除し、さらに、処理済グループリストに追加する（ステップ１１０７）。

次に、サーバ１０１は、未処理グループリストに未処理のグループがあるか否かを判定する（ステップ１１０８）。

未処理グループリストに未処理のグループがあると判定された場合、サーバ１０１は、ステップ１１０２に戻り同様の処理を実行する。

未処理グループリストに未処理のグループがないと判定された場合、サーバ１０１は、処理を終了する。

以上の処理によって、処理済グループリストには分割されたグループが格納される。

図１２Ａの場合、調査員の移動コストは「８＋１０＋９＝２７」となる。図１２Ｂの場合、調査員の移動コストは「８＋１０＋１１＋６＝３５」となる。

一方、図１３に示すように分割された場合、目的地点Ｌを含むグループの移動コストは運転手の有無にかかわらず「９＋９＝１８」となり、また、目的地点Ｋを含むグループの移動コストは運転手の有無にかかわらず「８＋８＝１６」となる。また、グループ間の移動コストは経路（Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ）又は経路（Ｂ、Ａ、Ｊ、Ｉ、Ｈ、Ｇ）が最適経路となり、当該最適経路の移動コストは「５」となる。なお、グループ間移動コストは、単純な最適経路の検索問題であり、ダイクストラ法等の既存の方法で検索できる。

したがって、分割前の移動コストは分割後の移動コストより小さいため、運転手の有無にかかわらず、グループは分割されない。

前述の分割処理では、分割方法によって、ステップ１１０５の判定結果が異なる可能性がある。例えば、Ｋ−ｍｅａｎｓ法を用いて分割した場合、分割前の移動コストが分割後の移動コストより小さいと判定された場合でも、他の分割法を用いて分割した場合、分割後の移動コストが分割前の移動コストより小さいと判定される可能性もある。

したがって、ステップ１１０３及びステップ１１０４において、複数の分割法を用いてグループを分割し、分割方法毎の移動コストを比較して、分割後の移動コストが最も小さくなる分割方法について、ステップ１１０５の判定処理を実行するようにしてもよい。

図１４は、本発明の第１の実施形態におけるペアのグループ化処理を説明するフローチャートである。

図１４では、（方法２）に対応するグループ化処理、すなわち、ペア又はグループ同士を組み合わせてグループを生成するグループ化方法を説明する。なお、以下では、図６を例に説明する。

まず、サーバ１０１は、目的地点と最近傍ノード２０１とのペアを一つのグループとして未処理グループリストに追加する（ステップ１４０１）。なお、以下の処理では複数のペアが結合されることによってグループが生成される。したがって、当該グループ化処理では一つのペアも一つのグループとして扱われる。以下、ペアをペアグループとも記載する。

次に、サーバ１０１は、未処理グループリストから隣接する２つのペアグループを取り出し、各ペアグループにおける最適経路を検索し、また検索された各最適経路の移動コストを算出する（ステップ１４０２）。

ここで、隣接する２つのペアグループの選択方法としては、ペアグループ間の移動コストが最小のものを選択する方法、ペアグループ内の目的地点と最近傍ノードとの全体の重心間距離が最小のものを選択する方法など様々な方法が考えられる。本実施形態では、ペアグループ間の移動コストが最小となるペアグループを隣接するペアグループとして選択するものとする。

次に、サーバ１０１は、取り出された２つのペアグループを結合する（ステップ１４０３）。ここで、ペアグループの結合とは、２つのペアグループに含まれる全ての目的地点と最近傍ノードとのペアの集合の和集合を生成することを意味する。

次に、サーバ１０１は、結合されたペアグループ内の最適経路を検索し、当該最適経路の移動コストを算出する（ステップ１４０４）。

次に、サーバ１０１は、結合されたペアグループにおける最適経路の移動コストが、結合前の各ペアグループにおける最適経路の移動コストより小さいか否かを判定する（ステップ１４０５）。

具体的には、結合前の各ペアグループにおける最適経路の移動コストをＬ１、Ｌ２とし、ペアグループ間の移動コストをＬＧとし、また、結合後のペアグループにおける最適経路の移動コストをＬとした場合、「Ｌ＜Ｌ１＋Ｌ２＋ＬＧ」を満たすか否かが判定される。

結合後のペアグループにおける最適経路の移動コストが結合前の各ペアグループにおける最適経路の移動コストより小さいと判定された場合、サーバ１０１は、結合されたペアグループを未処理グループリストに追加し（ステップ１４０６）、ステップ１４０８に進む。これは、２つのペアグループを結合した方が全体としての移動コストが削減できるためである。

結合後のペアグループにおける最適経路の移動コストが結合前の各ペアグループにおける最適経路の移動コスト以上であると判定された場合、サーバ１０１は、結合前の各ペアグループを処理済グループリストに追加し（ステップ１４０７）、ステップ１４０８に進む。これは、２つのペアグループを結合しない方が全体として移動コストが削減できるためである。

次に、サーバ１０１は、未処理グループリストに未処理のペアグループが２つ以上あるか否かを判定する（ステップ１４０８）。

未処理グループリストに未処理のペアグループが２つ以上あると判定された場合、サーバ１０１は、ステップ１４０２に戻り、同様の処理を実行する。

未処理グループリストに未処理のペアグループが１つ以下であると判定された場合、サーバ１０１は、未処理のペアグループを処理済グループリストに追加し処理を終了する。

以上の処理によって、処理済グループリストには結合されたペアグループが残る。

なお、ステップ１４０７において、選択された２つのペアグループを処理済グループリストに追加しているが、これは隣接する２つのペアグループと結合しても移動コストが削減されない場合、他のペアグループと結合しても移動コストが削減される可能性は低いという考え方に基づくものである。

前述の仮定は、隣接グループの定義、ペアグループ内の目的地点の分布、経路ネットワークの性質等によって該当しない場合も考えられる。したがって、隣接する２つのペアグループを選択するのではなく、結合候補を複数選択し、それぞれ結合させた場合の移動コストの削減量を算出し、最も移動コストの削減量が多いものを実際に結合させる方法を用いてもよい。

以下、図１４の示す方法を図６に示す経路ネットワークに適用した場合について説明する。

ステップ１４０１において、サーバ１０１は、図１０に示す、目的地点Ｋ及び最近傍ノードＢ２０１のペア、並びに、目的地点Ｌ及び最近傍ノードＧ２０１のペアの２つのグループをそれぞれグループリストに追加する。

ステップ１４０２において、サーバ１０１は、グループリストから２つのグループを取り出し、それぞれグループの最適経路を検索し、さらに各最適経路の移動コストＬ１、Ｌ２を算出する。ここでは、グループリストには２つのグループしか含まれないため当該グループが自動的に選択される。

具体的には、目的地点Ｋ及び最近傍ノードＢ２０１のペアからなるグループにおける移動コストは「１８」と算出され、また、目的地点Ｌ及び最近傍ノードＧ２０１のペアからなるグループにおける移動コストは「１６」と算出される。

また、結合前のグループでは交点ノードＢ２０１から交点ノードＧ２０１までの自動車移動が最適経路となるため、結合前のグループ間の移動コストは、交点ノード２０１における移動コストを「０」とした場合、「５」と算出される。

したがって、結合前の移動コストは「３９」と算出される。

ステップ１４０３において、２つのグループが図１５に示すように結合される。このとき、ステップ１４０４において、結合後の移動コストは「２７」と算出される。

ステップ１４０５において、サーバ１０１は、結合後の移動コストが結合前の移動コストより小さいと判定し、さらにステップ１４０６において、結合されたグループをグループリストに追加する。

この時点でグループリストにはグループが１つしか存在しないため、当該グループが処理済グループに残ることになる。したがって、グループにおける最適経路の移動コストが「２７」であるグループが１つ得られる。なお、図６に示す例では、運転手がいる否にかかわらず同一の結論となる。

（方法３）は、隣接する目的地点は結果的に同一のグループになる可能性が高いという仮定に基づくグループ化方法である。

例えば、サーバ１０１は、Ｋ−ｍｅａｎｓクラスタリング等を用いて、目的地点の位置情報に基づいて初期のグループから適当な数のグループを生成する。さらに、サーバ１０１は、生成されたグループに対して、（方法１）及び（方法２）のグループ化方法をランダムに実行して、移動コストの削減が一定回数「０」となった場合に処理を終了させるアルゴリズムを適用することが考えられる。

（方法３）の利点は、計算量の少ないＫ−ｍｅａｎｓ法等のクラスタリング手法を用いて、おおまかにグループ化することによって、計算量の多いセールスマン巡回問題を解く回数を削減することができる点である。

また、オペレータ又は調査員が初期のグループを指定してもよい。なお、当該グループは集落及び地域などの任意の基準で指定されるものであり、必ずしも調査時のグループとして最適なものではないため、前述した各グループ化方法を組み合わせて最適なグループを生成することが望ましい。

第１の実施形態における最適経路検索システムの構成は以上で説明したものに限定されない。例えば、端末１００が経路ネットワークＤＢ１１４又は地図ＤＢ１１５を備え、当該端末１００が最適経路の検索処理を実行してもよい。この場合、サーバ１０１が端末１００を携行する調査員が担当する目的地点の情報を端末１００に送信し、端末１００が指定された目的地点に対してのみ最適経路の検索処理を実行すればよい。

第１の実施形態によれば、移動コストの異なる徒歩移動及び自動車移動を組み合わせた最適経路の検索処理において、目的地点と離合点とを移動する最適経路を検索することによって、経路の最適性を保ち、かつ、検索処理に必要な計算処理を低減することが可能となる。

また、各目的地点の最近傍ノード２０１を離合点の候補として検索処理を実行することによって、経路の最適性を損なわずに、経路検索の範囲を大幅に削減することができる。したがって、計算量を削減し、迅速な最適経路を提示することが可能となる。

また、目的地点を含む複数のグループに経路ネットワークを分割することによって、グループの中での徒歩移動による移動経路の最適化、及び、グループ間の自動車移動による移動経路の最適化に問題を分割できる。これによって、経路の最適性を損なわずに、経路検索の範囲を大幅に削減することができる。

また、運転者がいる場合、運転手がいない場合のそれぞれの条件に対して、自動車移動及び徒歩移動を組み合わせた最適経路を調査員に提示することができる。すなわち、自動車移動による移動経路、徒歩移動による移動経路、及び動車を乗り降りする地点（離合点）をそれぞれ表示することができる。

［第２の実施形態］
第２の実施形態では、コンバイン、輸送トラック及び運搬機のそれぞれの移動経路、並びに、作物の積み替え地点を最適化する最適経路検索システムについて説明する。

コンバインは、圃場内の作物の刈り取り、刈り取った作物の脱穀作業等を行って作物を収穫する。コンバインは、収穫した作物を一定量貯めておくことができるが、圃場全体の作物を貯めるほどの積載量は有さない。したがって、コンバインに積載された作物を、適宜運搬車に積み替える必要がある。

輸送トラックは、大量の作物を積載し、カントリーエレベータ等の施設へ輸送する。輸送トラックは、圃場内を移動できず、圃場の外周のみを移動できるという特性を持つ。

運搬機は、コンバインに積載された作物を輸送トラックまで運搬し、輸送トラックに収穫された作物を積み替える。運搬機は、圃場内を自由に移動でき、かつ、輸送トラックへ積み替え可能な地点まで移動できる。

コンバインの積載量が所定値以上になると、刈り取り作業が中断されるため作業効率が低下する。すなわち、収穫の作業効率は、コンバインの稼動状況に依存するため、コンバインの運行計画が最優先となる。したがって、第２の実施形態における最適経路検索システムの課題は、コンバインの刈り取り作業を中断することなく、運搬機及び輸送用トラックの移動経路、並びに、作物の積み替え地点を最適化することである。

図１６は、本発明の第２の実施形態における最適経路検索システムの構成例を示すブロック図である。

第２の実施形態における最適経路検索システムは、コンバイン、輸送トラック及び運搬機のそれぞれに搭載される端末１６００と、サーバ１６０１と、端末１６００及びサーバ１６０１を接続するネットワーク１６０２とから構成される。

端末１６００は、制御部１６０４、入力部１６０５、表示部１６０６、位置検出部１６０７、及び通信部１６０８を備え、各構成はデータ通信バス１６０３によって互いに接続される。なお、端末１６００は、他の構成を含んでいてもよい。

制御部１６０４は、端末１６００が備える機能を実現するための処理を実行する。制御部１６０４は、例えば、プロセッサ等によって実現できる。

入力部１６０５は、作業者から情報の提示要求、及び経路検索条件の設定要求などを受付ける。入力部１６０５は、例えば、ボタン、タッチパネルなどによって実現できる。

表示部１６０６は、作業者に地図画像及び経路情報等の情報を表示する。表示部１６０６は、例えば、液晶ディスプレイ等によって実現できる。

位置検出部１６０７は、端末１６００の現在位置を検出する。位置検出部１６０７は、例えば、ＧＰＳ、又は自立航法ユニット等によって実現できる。

通信部１６０８は、ネットワーク１６０２を介してサーバ１６０１と通信する。具体的には、通信部１６０８は、端末１６００の現在位置に関する情報、情報の提示要求、及び経路検索条件の設定要求等をサーバ１６０１に送信し、また、端末１６００の現在位置周辺の地図画像及び最適経路情報等をサーバ１６０１から受信する。通信部１６０８は、携帯電話通信カードやＷｉＭＡＸ通信カードなどによって実現できる。

なお、端末は１００が備える各構成はソフトウェアを用いて実現してもよい。例えば、携帯電話、スマートフォン、携帯ゲーム機、カーナビゲーションシステム、ＰＮＤ（Ｐｅｒｓｏｎａｌ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ）等の既存の機器に、各構成を実現するソフトウェアを導入することによって、調査員が携帯できる端末１６００として利用することもできる。

サーバ１６０１は、本発明の中核をなす部分であり、コンバイン、運搬機及び輸送トラックを組み合わせた最適な収穫経路（最適経路）を検索し、検索された最適経路に関する情報を端末１６００に送信する。

サーバ１６０１は、制御部１６１０、入力部１６１１、表示部１６１２、通信部１６１３、経路ネットワークＤＢ１６１４、地図ＤＢ１６１５、経路検索部１６１６、及び刈り取り順決定部１６１７を備え、各構成はデータ通信バス１６０９によって接続される。

制御部１６１０は、サーバ１６０１が備える機能を実現するための処理を実行する。制御部１６１０は、例えば、プロセッサ等によって実現できる。

入力部１６１１は、オペレータがサーバ１０１の操作を行うためのインタフェースである。入力部１６１１は、例えば、キーボード、マウス、ボタン、及びタッチパネル等によって実現できる。

表示部１６１２は、オペレータに対して各種情報を表示する。表示部１６１２は、例えば、液晶ディスプレイ等によって実現される。

通信部１６１３は、ネットワーク１６０２を介して一以上の端末１６００と通信する。通信部１６１３は、端末１６００に対して最適経路に関する情報を送信し、また、端末１６００の現在位置に対応する周辺地図画像を当該端末１６００に送信する。通信部１６１３は、例えば、ネットワークカード等によって実現できる。

経路ネットワークＤＢ１６１４は、経路ネットワークに関する情報を格納する。本実施形態の経路ネットワークは、輸送トラックが通行可能な道路、地点を表すノードと、当該ノード間を接続するリンクとから構成される。なお、ノードは、積み替え可能か否かを示す属性情報を保持する。また、輸送トラックが通行可能な道路は、コンバイン及び運搬機も通行可能である。

地図ＤＢ１６１５は、ラスター形式又はベクター形式で表現された地図画像を格納する。地図画像には、ＪＰＥＧ、ＰＮＧ及びＴＩＦＦなどの形式が利用できる。地図ＤＢ１６１５は、解像度ごとに地図画像を格納し、さらに区域ごとに分割されて当該地図画像を格納する。これによって、端末１６００の現在位置が変化した場合、サーバ１６０１は端末１６００に適切な区域かつ適切な解像度の地図画像を送信することができる。したがって、端末１６００には現在位置に応じた地図が表示される。なお、ベクター形式の地図画像としてはＳＶＧ（Ｓｃａｌａｂｌｅ Ｖｅｃｔｏｒ Ｇｒａｐｈｉｃｓ）などが利用できる。

経路検索部１６１６は、コンバイン、運搬機及び輸送トラックが連携して収穫作業を行うための最適経路を検索し、検索された最適経路に関する情報をオペレータ又は作業者に対して出力する。

ここで、コンバイン、運搬機及び輸送トラックが連携して収穫作業を行うための最適経路の検索とは、コンバインの移動経路、運搬機の移動経路、コンバインから運搬機に積み替える地点、輸送トラックに積み替える地点、及び輸送トラックの移動経路のそれぞれ最適に決定することを意味する。

刈り取り順決定部１６１７は、圃場の刈り取り順を決定する。なお、刈り取り順は、移動コストとは異なる基準に基づいて決定される。

以下、第２の実施形態における最適経路の検索処理について説明する。

図１７は、本発明の第２の実施形態のサーバ１６０１が実行する最適経路検索処理を説明するフローチャートである。

経路検索部１６１６は、最初にコンバインの圃場内での移動経路を決定する。コンバインの移動経路は、圃場間の移動経路と、圃場内の移動経路に分けて検索される。これは、第１の実施形態におけるグループ間の最適経路と、グループ内の最適経路とを検索する処理に対応する。

まず、サーバ１６０１は、各圃場内のコンバインの最適経路を検索する（ステップ１７０２）。

圃場内におけるコンバインの最適経路の検索方法は、例えば、特開２００４−３５４１１７号公報に開示されているような方法を用いて通常方式（近）、通常方式（遠）、枕無し方式、片側枕無し方式のような既存の走行パターンの中から、ユーザのパターンを選択させることによって検索することができる。なお、前述の公報に記載の方法では、圃場への入り口と出口との組み合わせを考慮した圃場内の移動経路をオペレータが選択することができる。オペレータの選択が無かった場合、入り口と出口との組み合わせに対してデフォルトの移動経路タイプが選択されるようにしてもよい。

次に、サーバ１６０１は、経路ネットワークＤＢ１６１４を参照して、輸送トラックが通行可能な道路のみを表現した経路ネットワークに対して、圃場内におけるコンバインの移動経路を追加する（ステップ１７０３）。

ステップ１７０３では、以下のような処理が実行される。

まず、サーバ１６０１は、コンバインの最適経路上に目的地点を決定する。具体的には、コンバインは一定時間ごとに運搬機への積み替え作業を必要とするため、サーバ１６０１は、一定の時間間隔ごとのコンバインの移動地点を目的地点として決定する。目的地点を経路ネットワーク上に表現するためには、目的地点にノードを生成し、当該ノードを目的地点として決定すればよい。当該処理は、第１の実施形態におけるステップ５０１に対応する処理である。

サーバ１６０１は、決定された目的地点周辺の経路ネットワーク上において、運搬機が収穫した作物を輸送トラックに積み替えることが可能な地点（ノード）を検索する。これは、第１の実施形態における交点ノード２０１に対応するノードである。以下では、輸送トラックに積み替えが可能な地点を積み替え地点と呼ぶ。

サーバ１６０１は、目的地点と積み替え地点との間にリンクを生成する。ここで、リンクの移動コストは、地点間の地理的な距離及び運搬機の平均移動速度から算出できる。

また、サーバ１６０２は、それぞれの目的地点に対して最も移動コストの少ない積み替え地点に対してリンクを生成する。生成されたリンクは、第１の実施形態における自動車移動ができないリンクに対応する。また、目的地点に対してはそれぞれ唯一つの積み替え地点に対するリンクが生成されるため、この積み替え地点は第１の実施形態における最近傍ノードに相当する。すなわち、当該処理は第１の実施形態におけるステップ５０２に相当する処理である。

一方、コンバインの進行順に目的地点を目的地点ｋ（ｋ＝１、２、３、・・・）と表した場合、サーバ１６０１は、目的地点ｋから、目的地点ｋ−１及び目的地点ｋ＋１における最近傍ノードに対しても同様にリンクを生成する。

ただし、目的地点１に対しては、目的地点２における最近傍ノードとのリンクのみが生成され、また、最後の目的地点に対しては１つ前の目的地点における最近傍ノードとのリンクのみが生成される。これは、最初の目的地点の前に相当する目的点がなく、また最後の目的地点の次に相当する目的地点が存在しないためである。

また、すでに目的地点と最近傍ノードとの間にリンクが存在する場合、サーバ１６０１は、重複してリンクを生成する必要はない。当該処理によって、第１の実施形態における図２と同等の経路ネットワークが生成される。

次に、サーバ１６０１は、運搬機の最適経路を検索する（ステップ１７０４）。このステップは第１の実施形態における、ステップ５０３とステップ５０４に相当する処理である。

まず目的地点と最近傍ノードのペアのグループ化処理では、圃場内のペアを全てグループとすればよい。

次にサーバ１６０１は、グループ内での最短経路を検索する（ステップ５０４相当）。第１の実施形態では目的地点の移動順番は任意であったが、第２の実施形態ではコンバインの進行に合わせて目的地点を移動する必要がある。また、運搬機は目的地点に移動した後に、必ず積み替え地点に移動する必要がある。

例えば、コンバインが目的地点１、目的地点２、目的地点３の順に進行する場合、移動経路は（目的地点１の最近傍ノード、目的地地点１、目的地点１の最近傍ノード又は目的地点２の最近傍ノード、目的地点２、目的地点２の最近傍ノード又は目的地点３の最近傍ノード、目的地点３、目的地点３の最近傍ノード）の順番となる。

したがって、運搬機の最短経路は、（目的地点ｋ、目的地点ｋの最近傍ノード、目的地点ｋ＋１）と（目的地点ｋ、目的地点ｋ＋１の最近傍ノード、目的地点ｋ＋１）のうち、移動コストの小さい経路が選択される。選択された経路に含まれる最近傍ノードが第１の実施形態における離合点に相当する。

以上の処理によって、運搬機の最適な移動経路が算出される。

次に、サーバ１６０１は、輸送トラックの移動経路を検索する（ステップ１７０５）。

輸送トラックの移動経路は、離合点の間を最小コストで移動する経路となる。すなわち、輸送トラックの移動経路については、所定の積み替え地点において運搬機が積み替えを行った後、次の積み替え地点が異なれば当該積み替え地点に移動するという単純な経路が最適経路となる。ここでは、運搬機の移動コスト、及び、コンバインが収穫した作物の積み替えにかかるコストに対して、輸送トラックが異なる積み替え地点に移動するコストが必ず小さいことを仮定しているが、通常この仮定は満たされる。

最後に、サーバ１６０１は、圃場間のコンバイン、輸送機及び輸送トラックの最適経路を検索する（ステップ１７０６）。

圃場間の移動は通常舗装された広い道路を利用するため、それぞれの機械に対する最適な経路は等しくなる場合が多いが、それぞれの機械に対して異なる経路ネットワークを設定することによって、最適経路が異なる場合もある。

圃場間を移動する順番に制約がない場合における最適経路の検索処理では、サーバ１６０１が、各圃場間の最適経路をダイクストラ法で算出し、セールスマン巡回問題として分枝限定法などの既存の手法で実用的な時間で最適経路を検索可能である。

一方、圃場ごとの刈り取り順があらかじめ決められている場合がある。例えば、とうもろこしや水稲においては、ほぼ植え付け順に刈り取るのが通常であり、小麦に関しては人工衛星写真から植生指標ＮＤＶＩ＝（近赤外域強度−赤色域強度）／（近赤外域強度＋赤色域強度）を求め、算出された値から含有水分量を推定することによって収穫順を決定する方法が実用化されている。

刈り取り順決定部１６１７は、前述した既存の刈り取り順の決定方法を用いて、圃場間の刈り取り順を決定する。経路検索部１６１６は、刈り取り順決定部１６１７によって決定された刈り取り順に基づいて、各圃場間のコンバイン・輸送機・輸送トラックの最適経路を検索する。検索方法は、例えば、ダイクストラ法を用いることが考えられるが、他の方法を用いてもよい。

以上で説明したように、第２の実施形態では、コンバインの移動経路（最適経路）上に目的地点が決定され、当該目的地点と積み替え地点とのペアが生成され、当該ペアから運搬機の最適経路が検索される。すなわち、積み替え地点のいずれかから離合点が決定され、目的地点及び離合点を通過する運搬機の最適経路が検索される。さらに、当該決定された離合点を最適に移動するための輸送トラックの経路も検索される。

図１８Ａ、図１８Ｂ及び図１８Ｃは、本発明の第２の実施形態における経路ネットワークの一例を示す説明図である。

図１８Ａは、ステップ１７０２の処理が実行され、さらに、コンバインの最適経路上に目的地点が決定された後の経路ネットワークを表す。

図１８Ａにおいて、ノードＡ１８０１〜ノードＤ１８０１は、コンバイン及び運搬機のみが移動可能な地点を表す。ノードＥ１８０１〜ノードＧ１８０１は、積み替え地点を表す。

ノード１８０１とリンク１８０２とに囲まれた部分が圃場を表す。リンク１８０２は、輸送トラックが移動可能な経路を表す。

経路１８０３は、コンバインの最適経路を表す。図１８Ａに示す例では、ノードＡ１８０１からコンバインが作業を開始し、ノードＤ１８０１まで移動する経路を表す。

地点１８０４は、コンバインが収穫した作物を積み替える地点、すなわち、目的地点を表す。図１８Ａに示す例では、地点１８０４の数字順にコンバインが移動することを表す。

図１８Ｂは、目的地点と積み替え地点との間のリンクが生成された後の経路ネットワークを表す。

リンク１８０５は、目的地点と積み替え地点とのリンクを表す。

図１８Ｃは、ステップ１７０４の処理が実行された後の経路ネットワークを表す。

目的地点と積み替え地点とを結ぶ実線１８０５は、運搬機の最適経路を表す。図１８Ｃに示す例では、実線１８０５に付された数字は、運搬機の移動順を表す。

第２の実施形態では、コンバイン、運搬機及び輸送トラックを組み合わせた収穫経路を最適化することができる。

１００ 端末
１０１ サーバ
１０２ ネットワーク
１０３ データ通信バス
１０４ 制御部
１０５ 入力部
１０６ 表示部
１０７ 位置検出部
１０８ 通信部
１０９ データ通信バス
１１０ 制御部
１１１ 入力部
１１２ 表示部
１１３ 通信部
１１４ 経路ネットワークＤＢ
１１５ 地図ＤＢ
１１６ 経路検索部
２０１ ノード
２０２ リンク
２０３ 移動コスト情報
４００ ノード情報テーブル
４１０ 移動コスト情報テーブル
７０１、７０２ グループ
９００ リスト
１６００ 端末
１６０１ サーバ
１６０２ ネットワーク
１６０３ データ通信バス
１６０４ 制御部
１６０５ 入力部
１６０６ 表示部
１６０７ 位置検出部
１６０８ 通信部
１６０９ データ通信バス
１６１０ 制御部
１６１１ 入力部
１６１２ 表示部
１６１３ 通信部
１６１４ 経路ネットワークＤＢ
１６１５ 地図ＤＢ
１６１６ 経路検索部
１６１７ 刈り取り順決定部
１８０１ ノード
１８０２、１８０５ リンク
１８０３ 経路
１８０４ 地点

Claims (20)

1. 一以上の計算機を備え、移動体の移動経路を最適化する最適経路検索システムであって、
   前記計算機は、
   前記移動体が移動可能な地点を表す複数のノード及び前記ノード間を接続する複数のリンクから構成される経路ネットワークを管理する経路ネットワーク管理情報、並びに、前記リンクの移動時に用いられる移動手段毎に、当該移動手段を用いて前記リンクを移動するために必要な移動コストを管理する移動コスト管理情報を含む経路情報データベースと、
   前記移動体の移動経路のうち、当該移動体の移動コストが最小となる最適経路を検索する経路検索部と、
   前記検索された最適経路に関する情報を出力する出力部と、
   を備え、
   前記ノードは、前記複数の移動手段を用いて前記リンクを移動して到達可能な交点ノードを含み、
   前記経路検索部は、
   前記経路ネットワーク上の目的地点を決定し、
   前記経路情報データベースを参照して、前記目的地点から前記交点ノードまで移動する第１の移動経路を検索して、前記移動体が前記検索された第１の移動経路を移動するために必要な第１の移動コストを算出し、
   前記目的地点毎に、前記算出された第１の移動コストが最小となる前記交点ノードである最近傍ノードを検索し、
   前記経路情報データベースを参照して、前記移動体が前記全ての目的地点及び少なくとも一以上の前記最近傍ノードを通過して移動する第２の移動経路を検索して、前記移動体が前記検索された第２の移動経路を移動するために必要な第２の移動コストを算出し、
   前記算出された第２の移動コストが最小となる前記第２の移動経路を前記最適経路に決定し、
   前記経路情報データベースを参照して、前記移動体が前記最適経路上を移動するための前記各移動手段を用いた移動経路を検索し、
   前記出力部は、前記最適経路及び前記各移動手段の移動経路に関する情報を表示するためのデータを出力することを特徴とする最適経路検索システム。
2. 前記移動コストは、移動時間であり、
   前記移動コスト管理情報は、前記各リンクを移動可能な前記移動手段毎の移動時間を含むことを特徴とする請求項１に記載の最適経路検索システム。
3. 前記最適経路を検索する場合に、前記目的地点と前記最近傍ノードとを対応づけたペアを生成し、
   前記一以上のノード及び前記生成されたペアを少なくとも一つ含み、前記経路ネットワークの部分集合となるグループを生成し、
   前記経路情報データベースを参照して、前記移動体が、前記グループ内に含まれる全ての前記目的地点、及び、前記グループに含まれる前記最近傍ノードの少なくとも一つを移動するグループ内の第３の移動経路を検索して、前記移動体が前記検索されたグループ内の第３の移動経路を移動するために必要な第３の移動コストを算出し、
   前記算出された第３の移動コストが最小となる前記グループ内の第３の移動経路をグループ内最適経路に決定し、
   前記経路情報データベースを参照して、前記移動体が前記各グループ間を移動するグループ間の第４の移動経路を検索して、前記移動体が前記検索されたグループ間の第４の移動経路を移動するために必要な第４の移動コストを算出し、
   前記算出された第４の移動コストが最小となる前記グループ間の第４の移動経路をグループ間最適経路に決定し、
   前記グループ内最適経路及び前記グループ間最適経路に基づいて前記最適経路を決定することを特徴とする請求項１に記載の最適経路検索システム。
4. 前記グループ内の第３の移動経路を検索する場合に、前記グループに含まれる前記最近傍ノードを開始点として、前記グループに含まれる前記全ての目的地点を移動し、かつ、前記グループに含まれる前記最近傍ノードを終了点とする移動経路の中から前記グループ内の第３の移動経路を検索することを特徴とする請求項３に記載の最適経路検索システム。
5. 同一の前記最近傍ノードを前記開始点及び前記終了点とすることを特徴とする請求項４に記載の最適経路検索システム。
6. 前記最適経路検索部は、
   前記グループを生成する場合に第１のグループを定義し、
   前記経路情報データベースを参照して、前記第１のグループの前記グループ内最適経路を検索して、前記移動体が前記第１のグループのグループ内最適経路を移動するために必要な第５の移動コストを算出し、
   前記第１のグループを第２のグループ及び第３のグループに分割したと仮定した場合に、前記経路情報データベースを参照して、前記第２のグループ及び前記第３のグループのそれぞれの前記グループ内最適経路を検索して、前記移動体が前記第２のグループのグループ内最適経路を移動するために必要な第６の移動コスト、及び、前記移動体が前記第３のグループのグループ内最適経路を移動するために必要な第７の移動コストを算出し、
   前記経路情報データベースを参照して、前記第２のグループと前記第３のグループとの間の前記グループ間最適経路を検索して、前記移動体が当該グループ間最適経路を移動するための第８の移動コストを算出し、
   前記第６の移動コスト、前記第７の移動コスト及び前記第８の移動コストの合計値と、前記第５の移動コストとを比較し、
   前記第６の移動コスト、前記第７の移動コスト及び前記第８の移動コストの合計値が、前記第５の移動コストより小さいと判定された場合に、前記第１のグループを前記第２のグループと前記第３のグループとに分割することを特徴とする請求項４に記載の最適経路検索システム。
7. 前記最適経路検索部は、
   前記グループを生成する場合に第１のグループ及び第２のグループを定義し、
   前記経路情報データベースを参照して、前記第１のグループの前記グループ内最適経路を検索して、前記移動体が前記第１のグループのグループ内最適経路を移動するために必要な第９の移動コストを算出し、
   前記経路情報データベースを参照して、前記第２のグループの前記グループ内最適経路を検索して、前記移動体が前記第２のグループのグループ内最適経路を移動するために必要な第１０の移動コストを算出し、
   前記経路情報データベースを参照して、前記第１のグループと前記第２のグループとの間の前記グループ間最適経路を検索して、前記移動体が前記検索されたグループ間最適経路を移動するために必要な第１１の移動コストを算出し、
   前記第１のグループと前記第２のグループとを結合した第３のグループを生成したと仮定した場合に、前記経路情報データベースを参照して、前記第３のグループの前記グループ内最適経路を検索して、前記移動体が前記第３グループのグループ内最適経路を移動するために必要な第１２の移動コストを算出し、
   前記第１２の移動コストと、前記第９の移動コスト、前記第１０の移動コスト及び前記１１の移動コストの合計値とを比較し、
   前記第１２の移動コストが、前記第９の移動コスト、前記第１０の移動コスト及び前記１１の移動コストの合計値より小さいと判定された場合に、前記第１のグループと前記第２のグループとを結合して前記第３のグループを生成することを特徴とする請求項４に記載の最適経路検索システム。
8. 前記目的地点を決定する場合に、前記経路情報データベースを参照して、前記経路ネットワークから一以上のループを抽出し、
   前記抽出されたループに対して、当該ループを構成する前記ノードのうち、少なくとも一以上の前記交点ノードを目的地点に決定することを特徴とする請求項１に記載の最適経路検索システム。
9. 前記移動手段は、第１の移動手段、第２の移動手段及び第３の移動手段を含み、
   前記最適経路検索部は、
   前記目的地点を決定する場合に、前記第１の移動手段を用いた移動経路を決定し、
   前記第１の移動手段を用いた移動経路上に前記目的地点を決定し、
   前記最適経路を検索する場合に、前記目的地点と、前記第２移動手段及び前記第３移動手段が移動可能な前記交点ノードとを交互に移動する前記第２の移動経路を検索して、前記移動体が前記検索された第２の移動経路を移動するために必要な第１３の移動コストを算出し、
   前記算出された第１３の移動コストが最小となる前記第２の移動経路を前記最適経路に決定し、
   前記移動体が前記最適経路上を移動するための前記第３の移動手段の移動経路を検索することを特徴とする請求項１に記載の最適経路検索システム。
10. 前記第１の手段を用いた移動経路は、予め決定された移動条件に基づいて決定されることを特徴とする請求項９に記載の最適経路検索システム。
11. 一以上の計算機を備え、移動体の移動経路を最適化する最適経路検索システムにおける最適経路検索方法であって、
    前記計算機は、
    前記移動体が移動可能な地点を表す複数のノード及び前記ノード間を接続する複数のリンクから構成される経路ネットワークを管理する経路ネットワーク管理情報、並びに、前記リンクの移動時に用いられる移動手段毎に、当該移動手段を用いて前記リンクを移動するために必要な移動コストを管理する移動コスト管理情報を含む経路情報データベースと、
    前記移動体の移動経路のうち、当該移動体の移動コストが最小となる最適経路を検索する経路検索部と、
    前記検索された最適経路に関する情報を出力する出力部と、
    を備え、
    前記ノードは、前記複数の移動手段を用いて前記リンクを移動して到達可能な交点ノードを含み、
    前記方法は、
    前記経路検索部が、前記経路ネットワーク上の目的地点を決定する第１のステップと、
    前記経路検索部が、前記経路情報データベースを参照して、前記目的地点から前記交点ノードまでを移動する第１の移動経路を検索して、前記移動体が前記検索された第１の移動経路を移動するために必要な第１の移動コストを算出する第２のステップと、
    前記経路検索部が、前記目的地点毎に、前記算出された第１の移動コストが最小となる前記交点ノードである最近傍ノードを検索する第３のステップと、
    前記経路検索部が、前記経路情報データベースを参照して、前記移動体が前記全ての目的地点及び少なくとも一以上の前記最近傍ノードを通過して移動する第２の移動経路を検索して、前記移動体が前記検索された第２の移動経路を移動するために必要な第２の移動コストを算出する第４のステップと、
    前記経路検索部が、前記算出された第２の移動コストが最小となる前記第２の移動経路を前記最適経路に決定する第５のステップと、
    前記経路検索部が、前記経路情報データベースを参照して、前記移動体が前記最適経路上を移動するための前記各移動手段を用いて移動経路を検索する第６のステップと、
    前記出力部が、前記最適経路及び前記各移動手段の移動経路に関する情報を表示するためのデータを出力する第７のステップと、
    を含むことを特徴とする最適経路検索方法。
12. 前記移動コストは、移動時間であり、
    前記移動コスト管理情報は、前記各リンクを移動可能な前記移動手段毎の移動時間を含むことを特徴とする請求項１１に記載の最適経路検索方法。
13. 前記第４のステップは、
    前記目的地点と前記最近傍ノードとを対応づけたペアを生成する第８のステップと、
    前記一以上のノード及び前記生成されたペアを少なくとも一つ含み、前記経路ネットワークの部分集合となるグループを生成する第９のステップと、
    前記経路情報データベースを参照して、前記移動体が、前記グループ内に含まれる全ての前記目的地点、及び、前記グループに含まれる前記最近傍ノードの少なくとも一つを移動するグループ内の第３の移動経路を検索して、前記移動体が前記検索されたグループ内の第３の移動経路を移動するために必要な第３の移動コストを算出する第１０のステップと、
    前記算出された第３の移動コストが最小となる前記グループ内の第３の移動経路をグループ内最適経路に決定する第１１のステップと、
    前記経路情報データベースを参照して、前記移動体が前記各グループ間を移動するグループ間の第４の移動経路を検索して、前記移動体が前記検索されたグループ間の第４の移動経路を移動するために必要な第４の移動コストを算出する第１２のステップと、
    前記算出された第４の移動コストが最小となる前記グループ間の第４の移動経路をグループ間最適経路に決定する第１３のステップと、を含み、
    前記第５のステップは、前記グループ内最適経路及び前記グループ間最適経路に基づいて前記最適経路を決定するステップを含むことを特徴とする請求項１１に記載の最適経路検索方法。
14. 前記第１０のステップでは、前記グループに含まれる前記最近傍ノードを開始点として、前記グループに含まれる前記全ての目的地点を移動し、かつ、前記グループに含まれる前記最近傍ノードを終了点とする移動経路の中から前記グループ内の第３の移動経路を検索することを特徴とする請求項１３に記載の最適経路検索方法。
15. 同一の前記最近傍ノードを前記開始点及び前記終了点とすることを特徴とする請求項１４に記載の最適経路検索方法。
16. 前記第９のステップは、
    第１のグループを定義するステップと、
    前記経路情報データベースを参照して、前記第１のグループの前記グループ内最適経路を検索して、前記移動体が前記第１のグループのグループ内最適経路を移動するために必要な第５の移動コストを算出するステップと、
    前記第１のグループを第２のグループ及び第３のグループに分割したと仮定した場合に、前記経路情報データベースを参照して、前記第２のグループ及び前記第３のグループのそれぞれの前記グループ内最適経路を検索して、前記移動体が前記第２のグループのグループ内最適経路を移動するために必要な第６の移動コスト、及び、前記移動体が前記第３のグループのグループ内最適経路を移動するために必要な第７の移動コストを算出するステップと、
    前記経路情報データベースを参照して、前記第２のグループと前記第３のグループとの間の前記グループ間最適経路を検索して、前記移動体が当該グループ間最適経路を移動するための第８の移動コストを算出するステップと、
    前記第６の移動コスト、前記第７の移動コスト及び前記第８の移動コストの合計値と、前記第５の移動コストとを比較するステップと、
    前記第６の移動コスト、前記第７の移動コスト及び前記第８の移動コストの合計値が、前記第５の移動コストより小さいと判定された場合に、前記第１のグループを前記第２のグループと前記第３のグループとに分割するステップと、
    を含むことを特徴とする請求項１４に記載の最適経路検索方法。
17. 前記第９のステップは、
    第１のグループ及び第２のグループを定義し、
    前記経路情報データベースを参照して、前記第１のグループの前記グループ内最適経路を検索して、前記移動体が前記第１のグループのグループ内最適経路を移動するために必要な第９の移動コストを算出するステップと、
    前記経路情報データベースを参照して、前記第２のグループの前記グループ内最適経路を検索して、前記移動体が前記第２のグループのグループ内最適経路を移動するために必要な第１０の移動コストを算出するステップと、
    前記経路情報データベースを参照して、前記第１のグループと前記第２のグループとの間の前記グループ間最適経路を検索して、前記移動体が前記検索されたグループ間最適経路を移動するために必要な第１１の移動コストを算出するステップと、
    前記第１のグループと前記第２のグループとを結合した第３のグループを生成したと仮定した場合に、前記経路情報データベースを参照して、前記第３のグループの前記グループ内最適経路を検索して、前記移動体が前記第３グループのグループ内最適経路を移動するために必要な第１２の移動コストを算出するステップと、
    前記第１２の移動コストと、前記第９の移動コスト、前記第１０の移動コスト及び前記１１の移動コストの合計値とを比較するステップと、
    前記第１２の移動コストが、前記第９の移動コスト、前記第１０の移動コスト及び前記１１の移動コストの合計値より小さいと判定された場合に、前記第１のグループと前記第２のグループとを結合して前記第３のグループを生成するステップと、
    を含むことを特徴とする請求項１４に記載の最適経路検索方法。
18. 前記第１のステップは、
    前記経路情報データベースを参照して、前記経路ネットワークから一以上のループを抽出するステップと、
    前記抽出されたループに対して、当該ループを構成する前記ノードのうち、少なくとも一以上の前記交点ノードを目的地点に決定するステップと、
    を含むことを特徴とする請求項１１に記載の最適経路検索方法。
19. 前記移動手段は、第１の移動手段、第２の移動手段及び第３の移動手段を含み、
    前記第１のステップは、
    前記第１の移動手段を用いた移動経路を決定するステップと、
    前記第１の移動手段を用いた移動経路上に前記目的地点を決定するステップと、を含み、
    前記第４のステップは、
    前記目的地点と、前記第２移動手段及び前記第３移動手段が移動可能な前記交点ノードとを交互に移動する前記第２の移動経路を検索して、前記移動体が前記検索された第２の移動経路を移動するために必要な第１３の移動コストを算出するステップと、を含み、
    前記第５のステップは、前記算出された第１３の移動コストが最小となる前記第２の移動経路を前記最適経路に決定するステップを含み、
    前記第６のステップは、前記移動体が前記最適経路上を移動するための前記第３の移動手段の移動経路を検索するステップを含むことを特徴とする請求項１１に記載の最適経路検索方法。
20. 前記第１の手段を用いた移動経路は、予め決定された移動条件に基づいて決定されることを特徴とする請求項１９に記載の最適経路検索方法。

Images