(57)【要約】      （修正有）【課題】観光客が複数の観光資源を巡回する場合に、該経路に関して、総巡回距離を最小にすることと、前記観光客の嗜好が反映されることに加え、各観光資源の営業時間や休日設定といった時間的な属性情報を反映することを可能にする。【解決手段】目的地をリストアップするためのリストアップ手段と、該目的地の巡回にかかる総巡回時間を最小にするための最適巡回経路探索手段と、前記目的地のそれぞれの巡回可能時刻をデータとして所持するデータベースの時間情報を時間属性情報と、前記リストアップ手段によってリストアップされた巡回経路群の中から前記時間属性情報に合致しない巡回経路を除外する巡回経路絞り込み手段と、を持ち、前記巡回経路絞り込み手段によって絞り込まれた巡回経路群に対して前記最適巡回経路探索手段を適用する。【選択図】図５
2011227827.tif 000002
【特許請求の範囲】
【請求項１】
目的地をリストアップするためのリストアップ手段と、該目的地の巡回にかかる総巡回時間を最小にするための最適巡回経路探索手段を持つ順路決定手段であって、
前記目的地のそれぞれの巡回可能時刻をデータとして所持するデータベースの時間情報を時間属性情報と呼ぶ場合に、
前記リストアップ手段によってリストアップされた巡回経路群の中から前記時間属性情報に合致しない巡回経路を除外する巡回経路絞り込み手段を持ち、
前記巡回経路絞り込み手段によって絞り込まれた巡回経路群に対して前記最適巡回経路探索手段を適用することを特徴とする順路決定手段。
【請求項２】
請求項１に記載の時間属性情報は、前記目的地に関して、巡回を許可された時刻、または巡回を推奨された時刻、または利用者の平均滞留時間から成るデータベースであることを特徴とする順路決定手段。
【請求項３】
請求項１あるいは請求項２のいずれか一項に記載の時間属性情報は、順路決定装置が予めデータベースとして所持するものであり、またはネットワークを介して必要に応じて取得するものであることを特徴とする順路決定手段。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の訪問先が存在する場合において、最適な順路を割り当てる装置及びその方法に関する。
【背景技術】
【０００２】
例えば特許文献１には、複数の場所で作業をするときに、移動所要時間を最短にする最も効率的な巡回順路を設定する技術について記載されている。具体的には、構造物の位置や、点検期限などを考慮して、最も効率的な巡回順路を選択する。
【０００３】
このような順路探索問題は古くから研究されており、例えばセールスマンが一度だけ訪問して巡回する距離を最小化する巡回路を発見する、いわゆる巡回セールスマン問題は、複雑な組み合わせ問題の代表例である。すべての組み合わせについて、しらみつぶしに距離計算を行い、最小距離の巡回路を決定していたのでは今日の計算機で実用的な時間内に答えを出すことはできない。
【０００４】
セールスマンの巡回問題の解法の一例としては、例えば特許文献２が提案されている。これはカオス理論を用いて最適ルートを求めるものであり、最適化問題の対処方法としてこのように人工知能を用いる例は多い。
【０００５】
最適な経路を得る要求としては、他にも、観光地における観光客の巡回ルートを最適化するものが考えられる。つまり、例えば京都観光において、観光客は複数の神社仏閣を巡回する。また、代官山観光において、観光客は複数のインディーズブランドショップを巡回する。
【０００６】
このような巡回問題においては、最適な順路は、利用者の嗜好も満たさなければならないという条件があるのが特徴である。つまり、セールスマンの巡回問題のように最短時間であれば良いというものではなく、利用者が観光したい観光地をリストアップしなければならない。
【０００７】
従来は、時間的な最適化では公共交通機関が提供する経路探索プログラムを用い、また、嗜好的な最適化では近似検索や協調フィルタリングといった手段が用いられていた。協調フィルタリングは、多くのユーザの嗜好情報を蓄積し、あるユーザと嗜好の類似した他のユーザの情報を用いて自動的に推論を行う方法論であり、趣味の似た人からの意見を参考にするという口コミの原理に例えられることが多い。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００２−００７６００号公報
【特許文献２】特開平１１−２１２９５９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかるに前記の手段によれば、嗜好を元に観光資源をリストアップすることや、観光資源の結びつきを距離で表現することや、あらかじめ順序が決められた観光資源あるいは経由ポイントのリストを元に順路を求めることしかできないといった課題があった。
【００１０】
このような条件のみで順路を決定した場合、訪れたものの該観光地が営業時間外である場合も多く、距離や嗜好のみで最適経路を決めても、観光地を観光するという本来の目的を達成できないことがあった。
【課題を解決するための手段】
【００１１】
前記課題を解決するために本発明は、
目的地をリストアップするためのリストアップ手段と、該目的地の巡回にかかる総巡回時間を最小にするための最適巡回経路探索手段を持つ順路決定手段であって、
前記目的地のそれぞれの巡回可能時刻をデータとして所持するデータベースの時間情報を時間属性情報と呼ぶ場合に、
前記リストアップ手段によってリストアップされた巡回経路群の中から前記時間属性情報に合致しない巡回経路を除外する巡回経路絞り込み手段を持ち、
前記巡回経路絞り込み手段によって絞り込まれた巡回経路群に対して前記最適巡回経路探索手段を適用することを特徴とする順路決定手段である。
【００１２】
また本発明は、前記時間属性情報は、前記目的地に関して、巡回を許可された時刻、または巡回を推奨された時刻、または利用者の平均滞留時間から成るデータベースであることを特徴とする順路決定手段である。
【００１３】
また本発明は、前記時間属性情報は、順路決定装置が予めデータベースとして所持するものであり、またはネットワークを介して必要に応じて取得するものであることを特徴とする順路決定手段である。
【発明の効果】
【００１４】
本発明によれば、例えば、観光客が複数の観光資源を巡回する場合に、該経路に関して、総巡回距離を最小にすることと、前記観光客の嗜好が反映されることに加え、各観光資源の営業時間や休日設定といった時間的な属性情報を反映することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】無規則な巡回路決定例を示した図である。
【図２】観光資源間の距離を踏まえた順路決定例を示した図である。
【図３】観光資源間の移動時間を示した表である。
【図４】４つの観光地に関する時間属性情報の一例を示した図である。
【図５】本発明にかかる最適巡回路決定の過程の一例を示した図の１である。
【図６】本発明にかかる最適巡回路決定の過程の一例を示した図の２である。
【図７】観光地のリストアップ手段の一例を示した図である。
【図８】時間属性情報による巡回経路の絞り込みの一例を示した図である。
【図９】絞り込まれた巡回経路から最適巡回経路を決定する手段の一例を示した図である。
【発明を実施するための形態】
【実施例】
【００１６】
本発明の好適な実施の形態について、図を参照して説明する。本実施例では、巡回先として、寺院や遊興施設などの観光資源を用いており、旅行者（ユーザ）が複数の観光資源を巡回する場合を想定している。
【００１７】
しかし本発明における巡回路決定の対象は、いわゆる観光資源に限定するものではなく、例えば食事どころ巡りや電器店巡りや、また、セールスマンの巡回問題のような場合にも適用できる。
【００１８】
図１は無規則な巡回路決定例を示した図である。つまり、ユーザによって観光資源のリストとして観光資源Ａ（１０１ａ）、観光資源Ｂ（１０１ｂ）、観光資源Ｃ（１０１ｃ）、観光資源Ｄ（１０１ｄ）がリストアップされた場合に、無規則にその巡回路を決定している。この場合はそれぞれの観光資源間の距離等は考慮に入れておらず、一般に最適巡回路決定手段を持たないユーザはこの手段によることが多い。
【００１９】
図２は観光資源間の移動時間を考慮した巡回路決定例を示した図であり、図３は各観光資源間について、具体的な移動時間の一例を示したものである。また、図２と図３においてユーザと記したのは、ユーザのホームポイントであり、それは自宅やホテルであったり、駅や空港であったりしてもよく、ユーザの出発点あるいは帰着点である。
【００２０】
この場合は、全巡回パターンに対するそれぞれの所要時間を調べることにより、「ユーザ→Ｂ→Ａ→Ｄ→Ｃ→ユーザ」あるいは逆のパターンであるところの「ユーザ→Ｃ→Ｄ→Ａ→Ｂ→ユーザ」が最適な巡回路であることがわかる。
【００２１】
なお、このような最適巡回路を計算によって求める手段あるいはプログラムとしては、様々な方法が考えられるが、本発明においてはこれをなんら限定するものではない。
【００２２】
本発明の要旨は、リストアップされた観光資源間の所要時間を元に最適巡回路を決める前記のような方法によると、各観光資源がそれぞれ持っている営業時間などの時間属性情報を反映させることができず、現地に到着したら営業時間外だったという事態を防ぐことを目的としている。
【００２３】
時間属性情報とは、こういった営業時間情報以外にも、例えば特定の時間帯のみ入館料が割引されるといった時間割引情報や、該観光地に関する平均閲覧時間なども含み、ユーザが安心して巡回路を観光する場合において、時間属性情報は非常に重要な決定要因である。
【００２４】
こういった時間属性情報を加味した巡回路決定手段によれば、巡回路における各地の順番のみではなく、各対象地への到着時間や出発時間も事前に決めることが可能になる。このように、本発明では、最適巡回路を得るにあたって、観光資源間の移動時間に加えて前記時間属性情報を用いることで、前記目的を達成するものである。
【００２５】
図４は時間属性情報の一例を示したものであり、前記４つの観光地に関し、それぞれ４０３ａ、４０３ｂ、４０３ｃ、４０３ｄとして閲覧可能時刻と平均閲覧時間が記されている。なお、出発時刻４０１は、最適巡回経路を決定する情報処理装置にユーザが直接入力してもよいし、あるいは、該情報処理装置が推奨出発時刻を表示するものであってもよい。
【００２６】
本発明は、図２に示した経路パターンに関して、図４に示した時間属性情報によってパターンの絞り込みを行い、その中から図３に示した移動時間の総和を最小にする経路を解とするものである。
【００２７】
つまり図５に示すように、嗜好により観光地をリストアップして（５０１）、時間属性情報によって経路パターンを絞り込んで（５０３）、移動時間によって最適巡回路を決定する（５０５）のである。
【００２８】
また逆に、図２に示した経路パターンに関して、図３に示した移動時間の総和を小さい方から順に並べ、図４に示した時間属性情報を満足する最小の巡回経路を解とする方法も考えられる。
【００２９】
つまり図６に示すように、嗜好により観光地をリストアップして（６０１）、移動時間によって巡回経路の候補を選んで（６０３）、時間属性情報によって該候補の中から最適巡回路を決定する（６０５）のである。
【００３０】
次に、好適な実施の例として、図５に示した処理手順について説明する。図５においては、時間属性情報によって経路パターンを絞り込むこと（５０３）が本発明の主旨であり、観光地のリストアップ（５０１）と最適巡回路の探索（５０５）は任意であり、その手段を限定するものではない。
【００３１】
まず、ユーザは自分の嗜好に基づいて観光地をリストアップする。このリストアップ手段として５種の例を図７に示す。図７はユーザの動作と情報処理装置の動作に分けて記載している。なお、情報処理装置は、人気の観光地や観光地の分類表といったデータベースを事前に持っている場合や、あるいは必要に応じて該データベースに関してネットワークを参照する機能を持っている。
【００３２】
７０１は情報処理装置の入力装置を用いてユーザが観光地名を直接入力する手段である。また、７０３は情報処理装置の表示装置に表示された地図上の観光地アイコンをユーザがクリックして選択する手段である。
【００３３】
また、７０５は例えば寺院やショッピングセンターといった観光分野をユーザが情報処理装置の入力装置を用いて入力し、情報処理装置が該入力に応じた観光地名を提示し、ユーザがそれを承認する手段である。
【００３４】
また、７０７は情報処理装置が人気の観光地名を保持し、それを情報処理装置の表示装置に提示し、ユーザがそれを承認する手段である。
【００３５】
また、７０９は決定したリストアップ内容を元に、情報処理装置が、さらにその内容に関連する観光地名を提示し、ユーザがそれを承認する手段である。なお、７０９の手段は、例えば最適巡回路を決定したものの、途中で空き時間がある場合に、さらに観光地を増やす場合において特に有効である。
【００３６】
次に、前記リストアップされた観光地に関して、時間属性情報によって、情報処理装置が経路パターンを絞り込む処理を行う。時間属性情報とは図４に示したような閲覧可能時刻や平均閲覧時間、あるいは閲覧料金の時間割引情報などを含むデータベースであり、情報処理装置が予めデータベースとして所持していてもよいし、適宜ネットワークを介してデータベースを参照して取得してもよい。
【００３７】
時間属性情報による巡回経路パターンの絞り込みの様子を図８に示す。一例としてユーザの出発時刻を８：００とする。なお、観光地間の所要移動時間は図３に、時間属性情報は図４に示すものとする。
【００３８】
図３によれば、スタート地点から観光地Ａ、Ｂ、Ｃ、Ｄに直行した場合のそれぞれの到達時刻は１１：３０、８：３０、１０：００、１２：００となる。観光地Ａに着目すると、閲覧可能時刻が１５：００から２０：００であり平均閲覧時間は３０分であるから、観光地Ａの閲覧時刻は１５：００から１５：３０となる。
【００３９】
次に観光地Ａから観光地Ｂ、Ｃ、Ｄに直行した場合のそれぞれの到達時刻は１６：３０、１８：３０、１７：００となる。この時点で観光地ＣとＤは閲覧可能時刻を過ぎているため、（スタート地点→Ａ→Ｃ）と（スタート地点→Ａ→Ｄ）の巡回経路は観光出来ないために実現不可能となる。
【００４０】
次に観光地Ｂから観光地Ｃ、Ｄに直行した場合のそれぞれの到達時刻は１９：００、２０：３０となる。同様にこの経路も観光地ＣおよびＤの閲覧可能時刻を過ぎているため実現不可能となる。従って、（スタート地点→Ａ）という経路は観光地Ｂ、Ｃ、Ｄを全て巡回することが不可能であり、採用することができない。
【００４１】
このように、時間属性情報を加味して巡回経路を探索すると、所要時間のみに着目して探索された巡回経路では為し得なかった、実際に閲覧が出来るのかどうかといった事象を満たすことが可能となる。図５の５０３ではこのような全ての閲覧を完遂できる巡回経路を絞り込む処理を行う。
【００４２】
前記のような処理を行うことにより、全観光地の閲覧が可能になるパターンは、パターン１（スタート地点→Ｃ→Ｄ→Ａ→Ｂ→スタート地点）、パターン２（スタート地点→Ｃ→Ｄ→Ｂ→Ａ→スタート地点）、パターン３（スタート地点→Ｄ→Ｃ→Ａ→Ｂ→スタート地点）、パターン４（スタート地点→Ｄ→Ｃ→Ｂ→Ａ→スタート地点）の４パターンに絞り込まれ、この絞り込み手段が本発明に掛かるものである。
【００４３】
次に図５の５０５では、これら絞り込まれたパターンの中から、最適巡回経路を探索する。なお、最適巡回経路の決定に至る指針は複数考えられる。つまり、帰着時刻が最も早いパターンや、総移動時間の短いパターンや、場合によっては移動を楽しむユーザなどは、総移動時間の最も長いパターンを欲することも考えられる。
【００４４】
従って最適巡回経路決定の指針をどうするかは、事前にユーザが情報処理装置に入力しておかねばならない。ただし、前記指針の入力が無い場合には、標準選択方法として帰着時刻が最も早いパターンを選択するといった決定方法も考えられる。
【００４５】
例えば帰着時刻の早さで最適巡回経路を決定するならば、図９に示すように、パターン１の帰着時刻が最も早いため、パターン１を最適巡回経路と決定する。同様に、総移動時間が最も短いパターンを最適とするなら、これもパターン１を最適巡回経路と決定する。さらに、総移動時間が最も長いパターンを最適経路と定義付けるならば、パターン４が最適巡回経路と決定付けられる。
【００４６】
以上は図５のような順序で最適巡回経路を決定する場合の実施例であるが、図６のような順序で最適巡回経路を決定する場合は、まず帰着時刻や総移動時間を探索し、この結果を順番に並べておき、時間属性情報を満たす最も上位の経路を最適巡回経路とすればよい。
【００４７】
本発明によれば、以上のように、従来手法であるところの総移動時間のみによる巡回経路の探索の欠点であるところの、立ち寄ったが営業時間外だったといったことを避けることが可能となり、実際に全ての閲覧を完結させるという条件を満たした上で最適巡回経路を決定することが可能になる。
【００４８】
なお、本発明は巡回の対象を観光地として説明したが、対象は観光地に限定するものではなく、セールスマンの巡回問題のような場合など、複数の訪問対象が存在する経路探索においてはいかなる場合にも適用できる。対象数に関しても本実施例では４カ所を例としたが、これをなんら制限するものではない。
【００４９】
また、最適巡回経路として複数の候補が同順位で見つかった場合の処理手段についてはこれを限定するものではなく、該当する全ての候補を提示してもよいし、ランダムに提示してもよいし、あるいはそれを１つに決定するための任意の設問を追加してもよい。
【００５０】
また、本発明で用いた情報処理装置は、これを何ら限定するものではなく、パーソナルコンピュータでもよいし、カーナビゲーションシステムや携帯端末でもよい。従って、最適巡回経路を決定する環境は、自宅などにおける固定端末でもよいし、車中などにおける移動端末でもよい。同様に情報処理装置へのユーザの入力手段に関しても、キーボードやタッチパネルによるものなど種々の方法が考えられ、これを何ら限定するものではない。
【符号の説明】
【００５１】
１０１ａ〜１０１ｄ…観光資源、
２０１…ユーザのホーム位置、
４０１…ユーザのホームポイントにおける時間属性情報、
４０３ａ〜４０３ｄ…観光地における時間属性情報、
５０１…観光地のリストアップ、
５０３…時間属性情報による絞り込み、
５０５…移動時間による最適巡回路決定、
６０３…移動時間による絞り込み、
６０５…時間属性情報による最適巡回路決定、
７０１…リストアップ手段の例１、
７０３…リストアップ手段の例２、
７０５…リストアップ手段の例３、
７０７…リストアップ手段の例４、
７０９…リストアップ手段の例５、
【図１】
2011227827.tif 000003
【図２】
2011227827.tif 000004
【図３】
2011227827.tif 000005
【図４】
2011227827.tif 000006
【図５】
2011227827.tif 000007
【図６】
2011227827.tif 000008
【図７】
2011227827.tif 000009
【図８】
2011227827.tif 000010
【図９】
2011227827.tif 000011