(57)【要約】【課題】  移動能力が健常者とは異なる人に対して移動経路を提示する際に、健常者用の情報しかない場合でも、適切な移動経路を提示する。【解決手段】  本発明は、入力された現在地と目的地の双方の近くを通る該現在地の地点及び該目的地の地点を前記地点記憶手段から取得し、該地点に対応する教師経路候補を教師経路記憶手段から抽出し、該教師経路候補について信頼性の高い教師経路が占める割合が高いほどスコアの値が高いものと評価し、スコアの高いＮ個の教師経路候補を推薦経路候補として選出し、推薦経路候補に基づいて、道情報記憶手段から取得した移動コストに基づいて推薦経路を決定する。【選択図】  図１
2011232113.tif 000002
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を推薦する経路推薦装置であって、
地図上の点である地点を一意に特定する情報を格納した地点記憶手段と、
地図情報中の一部の経路（教師経路）毎に、該経路に沿った地点の順列を格納した教師経路記憶手段と、
道毎の地点間の移動コストを格納した道情報記憶手段と、
入力された現在地と目的地の双方の近くを通る該現在地の地点及び該目的地の地点を前記地点記憶手段から取得し、該地点に対応する教師経路候補を前記教師経路記憶手段から抽出し、該教師経路候補について信頼性の高い教師経路が占める割合が高いほどスコアの値が高いものと評価し、スコアの高いＮ個の教師経路候補を推薦経路候補として選出する経路候補選出手段と、
前記経路候補選出手段で選出された前記推薦経路候補に基づいて、前記道情報記憶手段から取得した移動コストに基づいて推薦経路を決定する推薦経路算出手段と、
を有することを特徴とする経路推薦装置。
【請求項２】
前記経路候補選出手段は、
前記教師経路候補に含まれる地点の中で出発地から直線距離が最も短い地点を出発点から教師経路に合流する地点、目的地から直線距離が最も短い地点を目的地から離脱する地点として選出する手段と、
前記教師経路候補の中で教師経路が占める割合が高ければ高いほどスコアの値が高くなる活用可能スコアを該教師経路候補に付与する手段と、
を含む請求項１記載の経路推薦装置。
【請求項３】
前記経路候補選出手段は、
前記教師経路候補に含まれる地点の中で出発地点を中心とした所定の半径Ｒの円内にあり、教師経路候補の経路の地点順列の中で最も後ろに位置する地点ａを抽出し、該教師経路候補に含まれる地点の中で目的地点を中心とした所定の半径Ｒの円内にあり、該教師経路候補の経路の地点順序の中で最も前に位置する地点ｂを抽出する手段と、
前記出発地点から前記地点ａまでの最短な経路Ａと、前記目的地点から前記地点ｂまでの最短な経路Ｂを決定し、該経路Ａと該地点ａから該地点ｂと該経路Ｂを順に結合した地点順列を推薦経路候補とする手段と、
を含む請求項１または２記載の経路推薦装置。
【請求項４】
前記推薦経路選出手段は、
前記推薦経路候補に基づいて前記道情報記憶手段を参照し、地点順列の移動コストを取得し、該移動コストの総和の逆数を活用可能性コストとし、該活用可能性コストの値が低いＮ個の推薦経路を出力する手段を
含む請求項１乃至３のいずれか１項に記載の経路推薦装置。
【請求項５】
出発地から目的地までの経路を推薦する経路推薦方法であって、
地図上の点である地点を一意に特定する情報を格納した地点記憶手段と、
地図情報中の一部の経路（教師経路）毎に、該経路に沿った地点の順列を格納した教師経路記憶手段と、
道毎の地点間の移動コストを格納した道情報記憶手段と、を有する装置が、
入力された現在地と目的地の双方の近くを通る該現在地の地点及び該目的地の地点を前記地点記憶手段から取得し、該地点に対応する教師経路候補を前記教師経路記憶手段から抽出し、該教師経路候補について信頼性の高い教師経路が占める割合が高いほどスコアの値が高いものと評価し、スコアの高いＮ個の教師経路候補を推薦経路候補として選出する経路候補選出ステップと、
前記経路候補選出ステップで選出された前記推薦経路候補に基づいて、前記道情報記憶手段から取得した移動コストに基づいて推薦経路を決定する推薦経路算出ステップと、
を行うことを特徴とする経路推薦方法。
【請求項６】
前記経路候補選出ステップにおいて、
前記教師経路候補に含まれる地点の中で出発地から直線距離が最も短い地点を出発点から教師経路に合流する地点、目的地から直線距離が最も短い地点を目的地から離脱する地点として選出し、
前記教師経路候補の中で教師経路が占める割合が高ければ高いほどスコアの値が高くなる活用可能スコアを該教師経路候補に付与する、
請求項５記載の経路推薦方法。
【請求項７】
前記経路候補選出ステップにおいて、
前記教師経路候補に含まれる地点の中で出発地点を中心とした所定の半径Ｒの円内にあり、教師経路候補の経路の地点順列の中で最も後ろに位置する地点ａを抽出し、該教師経路候補に含まれる地点の中で目的地点を中心とした所定の半径Ｒの円内にあり、該教師経路候補の経路の地点順序の中で最も前に位置する地点ｂを抽出し、
前記出発地点から前記地点ａまでの最短な経路Ａと、前記目的地点から前記地点ｂまでの最短な経路Ｂを決定し、該経路Ａと該地点ａから該地点ｂと該経路Ｂを順に結合した地点順列を推薦経路候補とする
請求項５または６記載の経路推薦方法。
【請求項８】
前記推薦経路選出ステップにおいて、
前記推薦経路候補に基づいて前記道情報記憶手段を参照し、地点順列の移動コストを取得し、該移動コストの総和の逆数を活用可能性コストとし、該活用可能性コストの値が低いＮ個の推薦経路を出力する
請求項５乃至７のいずれか１項に記載の経路推薦方法。
【請求項９】
請求項１乃至４のいずれか１項に記載の経路推薦装置を構成する各手段としてコンピュータを機能させるための経路推薦プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路推薦装置及び方法及びプログラムに係り、特に、有用な既知の教師経路を部分的に用いて、移動能力が健常者とは異なる人に移動経路を案内するための経路推薦装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
提示する経路を推薦する技術として以下のようなものがある。
【０００３】
１．グラフ理論における２頂点最短経路問題の解法：
経路推薦装置は一般に、入力手段を用い利用者によって入力された出発地と目的地に対して、最も負担の低い、出発地から目的地までの経路を推薦する装置である。
【０００４】
経路推薦は一般にグラフ理論における最短経路問題として解かれる。すなわち地図上の各地点をノード、各地点間(道)の移動コストをエッジの重みとするグラフを予め作成しておき、利用者によって入力された２ノード(出発地と目的地)間の２頂点対最短経路問題の解を推薦すべき経路とするものである。２頂点対最短経路問題を効率的に解くアルゴリズムにはダイクストラ法などがよく知られている（例えば、非特許文献１参照）。
【０００５】
道の移動コストとは、その移動体（ユーザ）が、その道を通過するのにかかる負担（肉体的負担、精神的負担、時間的負担などを総合化したもの）を任意の関数により定量化した値を指す。
【０００６】
２．精細な空間モデルを用いた移動者別経路案内システム
都市空間を精細に表現する空間情報システムにおける精細な空間情報を利用した，移動手段に応じた最短経路を検索・表示する装置が存在する（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269 〜 271.
【非特許文献２】蒔苗耕司，高木美紀. (2004). 3次元都市空間データモデルの構築と歩行者経路案内システムへの応用．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来のグラフ理論を利用した経路推薦装置では、出発地と目的地の近隣の、精度の高い、各地点間の移動コストが予め存在していることが前提である。一般的な健常者を想定した経路推薦装置においては、道の移動コストは道の距離などに応じて容易に出せるが、移動能力が健常者と大きく異なるような特殊な利用者においては、道の移動コストを適切に付与するのが難しい。例えば、段差や道幅、傾斜などが移動負担に大きく影響を与えるような車椅子利用者にとっては、健常者が移動する場合の移動コストは必ずしも参考にならず、健常者にとって快適な経路であっても、車椅子利用者にとっては快適に移動できなかったり、通過できなかったりする場合がある。結果として、車椅子利用者は一般的な経路推薦装置のみを利用するのではなく、信頼できる、限られた、高齢者・障害者用の経路を優先的に考慮し、経路を選択するという現状がある。
【０００９】
また従来は、非特許文献２のシステムのような、精細な空間モデルを利用した移動者別の経路案内を実現する装置が存在する。しかしながら、このような空間モデルを利用した装置は、空間モデルを作成するにあたり経路案内装置提供者の負担が大きく、全国の道などの空間で網羅的に利用することは難しい。したがって、空間モデルが作成されていない空間では一般に利用することができない。
【００１０】
すなわち、次のような限られた条件における経路推薦においては、従来の移動コストを利用した２頂点対最短経路問題を解くアルゴリズムを搭載した装置のみでは有効に経路を推薦できないという問題がある。
【００１１】
a. 利用者にとって精度の低い移動コスト付きの道集合が大量にある：
b. 利用者にとって精度の高い移動コスト付きの道集合が少数ある： 
上記ａ．の「利用者にとって精度の低い移動コスト付きの道集合」とは、各道の移動コスト値の大小が実際にその利用者が感じる度合いの大小との乖離が激しい（と推測される）集合とする。また、上記ｂ．の「利用者にとって精度の高い移動コスト付きの道集合」とは、各道の移動コスト値の大小が実際にその利用者が感じる度合いの大小との一致度が高い（と推測される）集合とする。
【００１２】
例として、さきほどの車椅子の利用者の場合においては、単純な道の距離のみなどから算出された移動コスト付きの道集合が、利用者にとって精度の低い移動コスト付きの道集合であり、車椅子利用者と同程度の移動能力を持つ車椅子利用者に移動履歴から算出された移動コスト付きの道集合などが、利用者にとって精度の高い移動コスト付きの道集合である。
【００１３】
本発明は、上記の点に鑑みなされたもので、移動能力が健常者とは異なる人に対して移動経路を提示する際に、健常者用の情報しかない場合でも、適切な移動経路を提示することが可能な経路推薦装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
図１は、本発明の原理構成図である。
【００１５】
本発明（請求項１）は、出発地から目的地までの経路を推薦する経路推薦装置であって、
地図上の点である地点を一意に特定する情報を格納した地点記憶手段４０と、
地図情報中の一部の経路（教師経路）毎に、該経路に沿った地点の順列を格納した教師経路記憶手段５０と、
道毎の地点間の移動コストを格納した道情報記憶手段６０と、
入力された現在地と目的地の双方の近くを通る該現在地の地点及び該目的地の地点を地点記憶手段４０から取得し、該地点に対応する教師経路候補を教師経路記憶手段５０から抽出し、該教師経路候補について信頼性の高い教師経路が占める割合が高いほどスコアの値が高いものと評価し、スコアの高いＮ個の教師経路候補を推薦経路候補として選出する経路候補選出手段２０と、
経路候補選出手段２０で選出された推薦経路候補に基づいて、道情報記憶手段６０から取得した移動コストに基づいて推薦経路を決定する推薦経路算出手段３０と、を有する。
【００１６】
また、本発明（請求項２）は、経路候補選出手段２０において、
教師経路候補に含まれる地点の中で出発地から直線距離が最も短い地点を出発点から教師経路に合流する地点、目的地から直線距離が最も短い地点を目的地から離脱する地点として選出する手段と、
教師経路候補の中で教師経路が占める割合が高ければ高いほどスコアの値が高くなる活用可能スコアを該教師経路候補に付与する手段と、を含む。
【００１７】
また、本発明（請求項３）は、経路候補選出手段２０において、
教師経路候補に含まれる地点の中で出発地点を中心とした所定の半径Ｒの円内にあり、教師経路候補の経路の地点順列の中で最も後ろに位置する地点ａを抽出し、該教師経路候補に含まれる地点の中で目的地点を中心とした所定の半径Ｒの円内にあり、該教師経路候補の経路の地点順序の中で最も前に位置する地点ｂを抽出する手段と、
出発地点から地点ａまでの最短な経路Ａと、目的地点から地点ｂまでの最短な経路Ｂを決定し、該経路Ａと該地点ａから該地点ｂと該経路Ｂを順に結合した地点順列を推薦経路候補とする手段と、を含む。
【００１８】
また、本発明（請求項４）は、推薦経路選出手段３０において、
推薦経路候補に基づいて道情報記憶手段４０を参照し、地点順列の移動コストを取得し、該移動コストの総和の逆数を活用可能性コストとし、該活用可能性コストの値が低いＮ個の推薦経路を出力する手段を含む。
【００１９】
図２は、本発明の原理を説明するための図である。
【００２０】
本発明（請求項５）は、出発地から目的地までの経路を推薦する経路推薦方法であって、
地図上の点である地点を一意に特定する情報を格納した地点記憶手段と、
地図情報中の一部の経路（教師経路）毎に、該経路に沿った地点の順列を格納した教師経路記憶手段と、
道毎の地点間の移動コストを格納した道情報記憶手段と、を有する装置が、
入力された現在地と目的地の双方の近くを通る該現在地の地点及び該目的地の地点を地点記憶手段から取得し、該地点に対応する教師経路候補を教師経路記憶手段から抽出し（ステップ１）、該教師経路候補について信頼性の高い教師経路が占める割合が高いほどスコアの値が高いものと評価し、スコアの高いＮ個の教師経路候補を推薦経路候補として選出する（ステップ２）経路候補選出ステップと、
経路候補選出ステップで選出された推薦経路候補に基づいて、道情報記憶手段から取得した移動コストに基づいて推薦経路を決定する推薦経路算出ステップ（ステップ３）と、を行う。
【００２１】
また、本発明（請求項６）は、経路候補選出ステップにおいて、
教師経路候補に含まれる地点の中で出発地から直線距離が最も短い地点を出発点から教師経路に合流する地点、目的地から直線距離が最も短い地点を目的地から離脱する地点として選出し、
教師経路候補の中で教師経路が占める割合が高ければ高いほどスコアの値が高くなる活用可能スコアを該教師経路候補に付与する。
【００２２】
また、本発明（請求項７）は、経路候補選出ステップにおいて、
教師経路候補に含まれる地点の中で出発地点を中心とした所定の半径Ｒの円内にあり、教師経路候補の経路の地点順列の中で最も後ろに位置する地点ａを抽出し、該教師経路候補に含まれる地点の中で目的地点を中心とした所定の半径Ｒの円内にあり、該教師経路候補の経路の地点順序の中で最も前に位置する地点ｂを抽出し、
出発地点から地点ａまでの最短な経路Ａと、目的地点から地点ｂまでの最短な経路Ｂを決定し、該経路Ａと該地点ａから該地点ｂと該経路Ｂを順に結合した地点順列を推薦経路候補とする。
【００２３】
また、本発明（請求項８）は、推薦経路選出ステップにおいて、
推薦経路候補に基づいて道情報記憶手段を参照し、地点順列の移動コストを取得し、該移動コストの総和の逆数を活用可能性コストとし、該活用可能性コストの値が低いＮ個の推薦経路を出力する。
【００２４】
本発明（請求項９）は、請求項１乃至４のいずれか１項に記載の経路推薦装置を構成する各手段としてコンピュータを機能させるための経路推薦プログラムである。
【発明の効果】
【００２５】
上記のように本発明によれば、以下のような効果を奏する。
【００２６】
Ａ：利用者の入力する出発地と目的地の一方もしくは両方が、教師経路集合のどの経路の出発地と目的地とも一致しないときにも、一部活用できる経路があるか判定し、ある場合については選出することができる。
【００２７】
Ｂ：利用者の入力する出発地と目的地の一方もしくは両方が、教師経路集合のどの経路の出発地と目的地とも一致しないときにも、一部活用できる教師経路がある場合に、ユーザの負担の低い経路を推薦することができる。
【００２８】
つまり、検索者にとって負担の低い既知の経路が少数存在する場合に、その経路を有効に利用できる。例として車椅子利用者においては、過去の同程度の移動能力を持つ車椅子利用者の移動履歴（教師経路）を有効に活用することができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の第１の実施の形態における経路推薦装置の構成図である。
【図４】本発明の第１の実施の形態における地点ＤＢの構成例である。
【図５】本発明の第１の実施の形態における教師経路ＤＢの構成例である。
【図６】本発明の第１の実施の形態における移動コスト付き道ＤＢの構成例である。
【図７】本発明の第１の実施の形態における経路推薦装置の詳細構成図である。
【図８】本発明の第１の実施の形態における教師経路選出部の動作を示すフローチャートである。
【図９】本発明の第１の実施の形態における教師経路候補抽出の例である。
【図１０】本発明の第１の実施の形態における教師経路候補の出発地と目的地の例である。
【図１１】本発明の第２の実施の形態における経路推薦装置の詳細構成図である。
【図１２】本発明の第２の実施の形態における教師経路選出部と推薦経路選出部の動作を示すフローチャートである。
【図１３】本発明の第２の実施の形態における教師経路の地点選出の例である。
【発明を実施するための形態】
【００３０】
以下図面と共に、本発明の実施の形態を説明する。
【００３１】
本発明は、最短経路問題を解くにあたり、
a. 利用者にとって精度の低い移動コスト付きの道集合が大量にある；
b. 利用者にとって精度の高い移動コスト付きの道集合が少数ある；
という限られた情報しか利用できないケースに着目し、本来活用しづらい教師経路を、最大限活用することを可能にするものである。
【００３２】
［第１の実施の形態］
図３は、本発明の第１の実施の形態における経路推薦装置の概要構成を示す。
【００３３】
同図に示す経路推薦装置１００は、入力部１０、教師経路選出部２０、推薦経路算出部３０、地点ＤＢ４０、教師経路ＤＢ５０、道ＤＢ６０から構成される。
【００３４】
地点ＤＢ４０は、図４に示すように、地点(地図上の点)を一意に特定するための地点IDと緯度、経度、その地点IDが含まれる教師経路ID(後述)から構成される。
【００３５】
教師経路ＤＢ５０は、図５に示すように、教師経路を一意に特定するための教師経路IDと、その教師経路上に存在する地点ＩＤを、経路に沿った順序で並べた地点ＩＤの順列である地点順列で構成される（つまり、地点順列とは地点IDの順番付きのリストである）。
【００３６】
教師経路は、地点順列で表現される、ある地点IDで表現される緯度経度上の位置からある地点IDで表現される緯度経度上の位置までに行く場合に、検索者にとって負担の低い（最適と考えられる）既知の経路を意味する。教師経路は通常、図５の｛教師経路ID-000001と教師経路ID-000002｝のペア、｛教師経路ID-000003と教師経路ID-000004｝のペアのように、逆順の地点順列で表現される教師経路が格納されているものとする（一方通行の道を表す連続する２地点IDを地点順列に含む教師経路のような、出発地と目的地を入れ替えた場合、教師経路といえなくなるような教師経路を除く）。また、このとき｛教師経路ID-000001と教師経路ID-000002｝のような教師経路IDのペアを教師経路のペア関係と呼ぶことにする。
【００３７】
移動コスト付き道ＤＢ６０は、図６に示すように、道(地点同士の接続線)ID、結ばれる2つの地点ID、道の移動コストで構成される。
【００３８】
以下では経路推薦装置の各部の詳細について記す。
【００３９】
図７は、本発明の第１の実施の形態における経路推薦装置の詳細構成を示す。
【００４０】
＜入力部＞
入力部１０は、利用者から、当該利用者が求める経路の出発地を表す緯度経度と目的地を表す緯度経度が入力として与えられると、地点ＤＢ４０を参照し、出発地の地点ID(S)と目的地の地点ID(G)を取得し、教師経路選出部２０に渡す。
【００４１】
＜教師経路選出部＞
次に、教師経路選出部２０は、教師経路存在判定部２１、教師経路候補選出部２２、活用可能性スコア算出部２３、有効性判定部２４を有し、入力部１０から渡された出発地の地点ＩＤ（Ｓ）と目的地の地点ＩＤ（Ｇ）から推薦候補となる教師経路候補を抽出し、推薦経路となるために有効なスコアを求め、当該スコアに応じて後段の推薦経路算出部３０に出力するものである。
【００４２】
図８は、本発明の第１の実施の形態における教師経路選出部の動作を示すフローチャートである。以下、図７に示す教師経路選出部２０の動作を図８に基づいて説明する。
【００４３】
ステップ１０１）  まず、教師経路存在判定部２１は、入力部１０から出発地の地点ＩＤと目的地の地点ＩＤを取得する。ここでは、出発地点Ｓ、目的地点Ｇとする。教師経路存在判定部２１は、ＳとＧに基づいて地点ＤＢ４０を参照し、Ｓ，Ｇの両方を含む教師経路ＩＤがあるかを判定し、ある場合はステップ１０２に移行し、ない場合は推薦経路表示部１１０に対して「推薦不能」を表すフラグを出力する。
【００４４】
ステップ１０２）  Ｓ、Ｇを両方含む教師経路がある場合はＳ、Ｇを両方含む教師経路ＩＤを地点ＤＢ４０から全ての教師経路を抽出する。なお、なお、ペア関係にある２つの教師経路が抽出されたときは、教師経路ＤＢ５０を参照し、ＧがＳより前側の項に位置している方は削除するものとする。抽出した各教師経路に対して、SからGまでの部分順列を推薦する教師経路とするので、該当するＳからＧまでの地点の順列を抽出し、抽出した各教師経路毎の地点順列（つまり、各教師経路の部分順列）を推薦経路表示部１１０に渡す。ここで、ある地点順列Teのある地点ID(e1)から別のある地点ID(e2)までの部分順列とは、Teに対して、e1より前の項、e2より後ろの項を除く処理を行った順列である。
（部分順列の例：
[000001, 000002, 000005, 000007, 000009]で表現される地点順列の000002から000007までの部分順列は[000002, 000005, 000007]である）
Ｓ，Ｇ両方を含む教師経路がない場合はＳとＧを次の教師経路候補選出部２２に渡す。
【００４５】
ステップ１０３）  教師経路候補選出部２２は、Ｓの緯度経度とＧの緯度経度に対して，近距離にある緯度経度を表す地点IDをそれぞれに対して含む教師経路を抽出する。具体的には、次の処理を行うことができる。
【００４６】
まず、地点ＤＢ４０を参照し、全ての地点IDと緯度経度と地点IDが含まれる教師経路IDを取得し、それらに対してＳの緯度経度との距離がＲ（Ｒは予め定められた閾値）以下の緯度経度を表す地点IDを全て抽出し、さらに抽出した地点IDが含まれる教師経路IDを全て抽出し、抽出した教師経路IDのリスト（重複する教師経度IDは一つにまとめる）を取得する（抽出したリストを、「Ｓ近傍教師経路リスト」と呼ぶこととする）。同様に，全ての地点IDと緯度経度と地点IDが含まれる教師経路IDに対して、Ｇの緯度経度との距離がＲ以下の緯度経度を表す地点IDを全て抽出し、さらに抽出した地点IDが含まれる教師経路IDを全て抽出し、抽出した教師経路IDのリスト（重複する教師経度IDは一つにまとめる）を取得する（抽出したリストを、「Ｇ近傍教師経路リスト」と呼ぶこととする）。
結果としてＳ， Ｇ それぞれに対して近距離にある教師経路IDのリストであるＳ近傍教師経路リストとＧ近傍教師経路リストが抽出される。
【００４７】
Ｓ近傍教師経路リストと、Ｇ近傍教師経路リストの両方に含まれる全ての教師経路IDを、教師経路候補として抽出する。
【００４８】
具体的には、図９に示すように、ＳとＧのそれぞれの緯度経度を中心とした予め与えられた半径Ｒの円内に教師経路中の地点IDが両方ともに含まれる教師経路IDを抽出することができる。図９の場合は、出発地点Ｓからの直線距離が最も短いｓ１を始点（教師経路に合流する地点）、目的地点Ｇからの直線距離が最も短いｇ１を終点（目的地点に向かうために教師経路から離脱する地点）とする教師経路候補Ｔ１と、同様に、ｓ２を始点、ｇ２を終点とする教師経路候補Ｔ２が選出される。
【００４９】
当該ステップではこのように教師経路候補選出部２２が教師経路候補を（全て）抽出し、抽出した教師経路候補を活用可能性スコア算出部２３に渡す（抽出された教師経路候補の数を仮にM個とする）。
【００５０】
なお、条件を満たす教師経路がない場合（つまり、抽出された教師経路候補が０個の場合）、推薦不能を表すフラグを推薦経路表示部１１０に渡す。
【００５１】
ステップ１０４）  活用可能性スコア算出部２３は、 教師経路候補選出部２２から取得した教師経路候補それぞれに対して、その教師経路が推薦する経路として活用できそうであればあるほど高い値を算出する評価関数を用いて、活用可能性スコアｐを算出する。
【００５２】
なお、教師経路候補を特定する識別子をＴi（ｉ＝１，２，…，Ｍ)とする。したがって、各教師経路候補Ｔi（i＝１，２，…，Ｍ）に対して活用可能性スコアｐを算出することとなる。
【００５３】
各教師経路候補Ｔiの活用可能性スコアｐを算出するための評価関数の例としては、Ｄtiの逆数がある。なお、Ｄtiの添え字tiはＴiを指し、Ｔiで特定される教師経路候補のスコアがＤtiである。ＤTiと記載する場合もある。このＤtiが低いほど活用可能性が高い教師経路候補とする。Ｄtiを求める式を以下に示す。
【００５４】
Dti = ||S-Sti|| + ||G-Gti||+|Sti-Gti| 
上記において、Sti, Gtiは，教師経路候補Ｔiの各地点IDで表される各緯度経度のうち、それぞれＳ、Ｇで表される緯度経度からの直線距離が最も小さい緯度経度によって表されるＴi上の地点であり、||X-Y||は地点ID- Xで表現される緯度経度と、地点ID-Yで表現される緯度経度の直線距離、|G-Gti|は教師経路候補Ｔiの地点順列のGからGtiまでの部分順列の各隣り合う地点IDの緯度経度の直線距離の総和を表す。
【００５５】
なお、上記のDtiの逆数を評価関数の値である活用可能性スコアＤtiは、出発地点Ｓから目的地点Ｇに至る全経路の長さが短ければ短いほど、その教師経路候補は推薦する経路として活用できそうである（つまり、活用可能性スコアｐは大きな値となる）と判定する例である。
【００５６】
図１０に、当該ステップで実施される処理のイメージを示す。同図中の太線の長さが活用可能性スコアＤtiに相当する（Si，Giが教師経路候補Tiの出発地と目的地を表す地点IDである）。
【００５７】
活用可能性スコア算出部２３は、上記で求められたＭ個の教師経路候補及び、当該候補の活用可能性スコアＤtiを有効性判定部２４に渡す。
【００５８】
ステップ１０５）  有効性判定部２４は、ステップ１０４で抽出した各教師経路候補Ｔiが活用可能か判定する。例として次の判定式を満たす場合に活用可能とする。
【００５９】
|Sti-Gti|/Dti  ≧  θ  (θは予め定めた閾値)
また、上記判定式の左辺の値を教師経路候補Ｔiの活用可能性スコアｑとする。なお、上記の活用可能性スコアｑは、出発地点Ｓから目的地点Ｇに至る全経路の中で、教師経路候補で特定される経路の長さが占める割合が高ければ高いほど、その教師経路候補は推薦する経路として活用できそうである（つまり、活用可能性スコアｑは大きな値となる）と判定する例である。
【００６０】
有効性判定部２４は、選出した教師経路候補のうち活用可能な教師経路候補が存在する場合に、活用可能な教師経路候補集合の各教師経路候補Ｔiについて、それぞれ活用する教師経路Ｔiとして、Ｔiの教師経路IDと地点Ｓti, Ｇtiの地点IDとその活用可能性スコアｐとその活用可能性スコアｑを、推薦経路算出部３０に渡す。なお、当該有効性判定部２４で活用可能と判定された教師経路候補の数をＮ個とし、活用可能性スコアｐ，ｑをＮ個出力するものとする。
【００６１】
一方、有効性判定部２４は、算出した全ての教師経路が活用可能でない場合に、推薦経路表示部１１０に推薦不能を表すフラグを渡す。
【００６２】
＜推薦経路算出部＞
次に、推薦経路算出部３０について説明する。
【００６３】
推薦経路算出部の概要を以下に示す。
【００６４】
推薦経路算出部３０は、地点ＤＢ４０を参照し，全ての地点IDとその緯度経度を取得しておく。また道ＤＢ６０を参照し、全ての道IDとその道で結ばれる地点ID、および移動コストを取得しておく。さらにそれらの地点IDをノード、地点間のコストをエッジとするネットワークグラフを作成しておく。
【００６５】
推薦経路算出部３０は教師経路選出部３０によって活用可能とされた教師経路集合の各教師経路ＴiとＳti，Ｇtiに対して移動コストを活用した推薦経路を算出する。教師経路選出部２０において活用可能とされた各教師経路Ｔi(とＳti， Ｇti)に対してＳ，Ｓti間、Ｇ，Ｇti間の移動コストの和が最も低い経路Ｓ→Ｓti，Ｇti→Ｇを算出する（Ｓ→ＳtiはＳからＳtiまでの移動コスト最適な経路を意味し、Ｓを初項、Ｇを末項とする地点順列で表される)。
【００６６】
なお、またＳ，Ｓti間及びＧ，Ｇti間のそれぞれの移動コストの総和の合計の逆数を活用可能性スコアｒとする。
【００６７】
なお、上記の活用可能性スコアｒは、出発地点Ｓから目的地点Ｇに至る経路において，教師経路の部分経路以外の経路中の道の移動コストの総和が低いほどその教師経路は推薦する経路として活用できそうである（つまり、活用可能性スコアｒは大きな値となる）と判定する例である。
【００６８】
さらに活用可能性スコアｐ、活用可能性スコアｑ、活用可能性スコアｒの線形和を活用可能性スコアｓとする。線形和をとるときの各項の係数は予め定めた値によって与えられるものとする。活用可能性スコアｓはこれまでに算出した活用可能性スコアｐ，活用可能性スコアｑ，活用可能性スコアｒの線形和が高ければ高いほど、その教師経路は推薦する経路として活用できそうである（つまり、活用可能性スコアｓは大きな値となる）と判定する例である。
【００６９】
算出される経路は、作成したネットワークグラフにおけるＳ−Ｓti間、 Ｇti−Ｇ間の２頂点対最短経路問題の解であり、ダイクストラ法などの既存手法によって抽出される。推薦経路算出部３０は、地点順列Ｓ→Ｓti，地点順列Ｓti〜Ｇti，地点順列Ｇti→Ｇをこの順に結合した地点を推薦経路として、活用可能性スコアｓと共に推薦経路表示部１１０に渡す。
【００７０】
(Sti~Gtiは教師経路Tiの地点順列のStiからGtiまでの部分順列)
地点順列Ａ，Ｂ，Ｃをこの順に結合した順列とは，地点順列Ａ，Ｂ，Ｃがあるとき、Ａの末項の次にBの初項を追加し、以下Ｂのx項(1>x)をＢのx-1項の次に追加し、Ｂの末項の次にCの初項を追加し、以下Ｃのy項(1>y)をＣのy-1項の次に追加した結果を表す順列である。但し、同じ値の項が隣り合う場合はどちらか一方の項を削除するものとする．
例として下記のような地点順列Ａ，Ｂ，Ｃがあるとき、それらをこの順に結合した順列とは下記のような順列Dである．
A = [a1, a2, ... , an]
B = [b1, b2, ... , bm] 
C = [c1, c2, ..., cl]
D = [a1, a2, ..., an, b1, b2, ..., bm, c1, c2, ..., cl]
＜推薦経路表示部＞
推薦経路表示部１１０は、経路推薦装置１００の教師経路選出部２０及び、推薦経路算出部３０に接続されている。推薦経路表示部１１０の概要を以下に示す。
【００７１】
推薦経路表示部１１０は、前の処理より推薦経路の地点順列（と活用可能性スコアｓ）の集合が渡された場合は、活用可能性スコアに高いものから順にそれらを表示インターフェイス上に利用者に表示する。なお、活用可能性スコアが与えられていない地点順列が与えられた時は、地点順列をランダムな順にそれらを表示インターフェイス上に表示するものとする．推薦不能を表すフラグが渡された場合は推薦する経路が存在しない旨を表示し終了する。
【００７２】
［第２の実施の形態］
図１１は、本発明の第２の実施の形態における経路推薦装置の構成を示す。
【００７３】
同図に示す経路推薦装置２００において、装置概要構成は図３と同様であるが、教師経路選出部７０と推薦経路選出部８０の構成が異なる。同図において、図７と同一構成部分には同一符号を付し、その説明を省略する。
【００７４】
教師経路選出部７０は、教師経路存在判定部７１と教師経路選出部７２を有する。教師経路存在判定部７１は、第１の実施の形態における教師経路存在判定部２１と同様である。
教師経路選出部７２も第１の実施の形態における教師経路選出部７２と同様である。
【００７５】
第１の実施の形態の推薦経路算出部３０に代わって、本実施の形態では、推薦経路選出部８０を有し、当該推薦経路選出部８０は合流経路抽出部８１と推薦経路ランキング８２を有する。
【００７６】
図１２は、本発明の第２の実施の形態における教師経路選出部と推薦経路選出部の動作のフローチャートである。
【００７７】
ステップ２０１〜ステップ２０２までは、第１の実施の形態における図８のステップ１０１〜ステップ１０２と同様である。
【００７８】
ステップ２０３）  推薦経路選出部８０の合流経路抽出部８１が教師経路選出部７２から教師経路候補を取得すると、図１３のように、地点ＤＢ４０を参照して各教師経路Ｔiに対して、Sを中心とした所定の半径Ｒの円内にあり、教師経路Ｔiの地点順列の中で最も後ろ側に位置する地点Miを選出する。同様にGを中心とした所定の半径Ｒの円内にあり、教師経路Ｔiの地点順列の中で最も前側に位置する地点Ｎiを選出する。
【００７９】
ステップ２０４）  合流経路抽出部８１ではＳからＭiおよびＮiからＧまでの最短な経路S→Ｍi，Ｎi→Gを抽出する。ただし、最短な経路を計算する上で、教師経路Ｔi上の道は信頼できる道として、Ｔi上の道のコストは、移動コスト付き道ＤＢ６０によって与えられる移動コストに対してパラメータαを乗算した値とする（α＜1）。なお、当該パラメータαは予め与えられメモリ（図示せず）に格納されている値とする。このとき各地点順列Ｓ→Ｍi，Ｍi〜Ｎi，Ｎi →Ｇをこの順に結合した地点順列が推薦経路であり、各教師経路Ti毎に抽出した推薦経路を推薦経路ランキング部８２に渡す。
【００８０】
ステップ２０５）  推薦経路ランキング部８２は、合流経路抽出部８１から取得した各推薦経路に、活用可能性スコアｓを付与する。当該活用可能性スコアｓは推薦経路の地点順列の移動コスト総和の逆数で表される（値が低いほど活用可能性が低い）。推薦経路ランキング部８２は、各教師経路毎の推薦経路の地点順列と活用可能性スコアｓを推薦経路表示部１１０に渡す。
【００８１】
以降の処理は第１の実施の形態と同様である。
【００８２】
上記の第１の実施の形態は、教師経路への合流箇所の決め方について、出発、目的地からの距離の近さを重要視した例であり、第２の実施の形態は、移動コストを柔軟に用いた例である。
【００８３】
なお、上記の図７、図１１に示す各構成要素の動作をプログラムとして構築し、経路推薦装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８４】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８６】
１０  入力部
２０  経路候補選出手段、教師経路選出部
２１  教師経路存在判定部
２２  教師経路選出部
２３  活用可能性スコア算出部
２４  有効性判定部
３０  推薦経路選出手段、推薦経路算出部
４０  地点記憶手段、地点ＤＢ
５０  教師経路記憶手段、教師経路ＤＢ
６０  道情報記憶手段、移動コスト付き道ＤＢ
７０  教師経路選出部
７１  教師経路存在判定部
７２  教師経路選出部
８０  推薦経路選出部
８１  合流経路抽出部
８２  推薦経路ランキング部
１００，２００  経路推薦装置
１１０  推薦経路表示部
【図１】
2011232113.tif 000003
【図２】
2011232113.tif 000004
【図３】
2011232113.tif 000005
【図４】
2011232113.tif 000006
【図５】
2011232113.tif 000007
【図６】
2011232113.tif 000008
【図７】
2011232113.tif 000009
【図８】
2011232113.tif 000010
【図９】
2011232113.tif 000011
【図１０】
2011232113.tif 000012
【図１１】
2011232113.tif 000013
【図１２】
2011232113.tif 000014
【図１３】
2011232113.tif 000015