(57)【要約】【課題】  検索された複数のＰＯＩを巡回的に訪れる場合に最適な経路探索と案内をすることができるようにしたナビゲーションシステムを提供する。【解決手段】  情報配信サーバ３０は、ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベース３７と、ＰＯＩ検索手段３８と、ＰＯＩソート手段３９とを備えて構成され、ネットワークを介して携帯端末２０に接続される。ＰＯＩソート手段３９は、第１の検索モードが設定された時は、ＰＯＩ検索手段３８によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、第２の検索モードが設定された時は、ＰＯＩ検索手段３８によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートし、ソートされた結果を携帯端末２０に配信する。【選択図】      図１
2007024624.tif 000002
【特許請求の範囲】
【請求項１】
第１の検索モードと第２の検索モードを有し、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートし、
前記ソートされた結果を携帯端末に配信するように構成したことを特徴とするナビゲーションシステム。
【請求項２】
前記ＰＯＩデータベースは、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶するとともに、各カテゴリにそれぞれ前記第１の検索モードまたは第２の検索モードの何れかを示す検索モードの情報を記憶したことを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、前記抽出された各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートすることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記ナビゲーションシステムは、更に、前記ソートモード選択手段を備え、前記第１のソートモードまたは第２のソートモードを任意に選択するようになしたことを特徴とする請求項３または請求項４に記載のナビゲーションシステム。
【請求項６】
検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備えた携帯端末とネットワークを介して接続される情報配信サーバであって、
前記情報配信サーバは第１の検索モードと第２の検索モードを有し、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートし、
前記ソートされた結果を前記携帯端末に配信するように構成したことを特徴とする情報配信サーバ。
【請求項７】
前記ＰＯＩデータベースは、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶するとともに、各カテゴリにそれぞれ前記第１の検索モードまたは第２の検索モードの何れかを示す検索モードの情報を記憶したことを特徴とする請求項６に記載の情報配信サーバ。
【請求項８】
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートすることを特徴とする請求項６に記載の情報配信サーバ。
【請求項９】
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートすることを特徴とする請求項６に記載の情報配信サーバ。
【請求項１０】
第１の検索モードと第２の検索モードを有し、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする情報配信サーバとネットワークを介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする携帯端末。
【請求項１１】
前記ＰＯＩソート手段は更に、第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、前記抽出された各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする情報配信サーバにネットワークを介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする請求項１０に記載の携帯端末。
【請求項１２】
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートする情報配信サーバにネットワークを介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする請求項１０に記載の携帯端末。
【請求項１３】
前記携帯端末は、更に、前記ソートモード選択手段を備え、前記第１のソートモードまたは第２のソートモードを任意に選択するようになしたことを特徴とする請求項１１または請求項１２に記載の携帯端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、携帯電話などの携帯端末と情報配信サーバからなる通信型のナビゲーションシステムに関するものであり、特に、ユーザが所望する位置周辺における興味対象場所（ＰＯＩ）の情報を検索し、検索されたＰＯＩへの経路を案内することができるナビゲーションシステム、情報配信サーバ、携帯端末に関するものである。
本発明は上記のようなナビゲーションシステムにおいて、検索された複数のＰＯＩを巡回的に訪れる場合の最適な経路探索と案内をすることができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末に関するものである。
【背景技術】
【０００２】
近年、携帯電話など携帯端末がブラウザを搭載し、インターネットにアクセスして所望の情報の提供を受けることができるようになっている。このようなシステムにおいては、ユーザは携帯端末を操作して、サーバに備えられた検索エンジン等を利用して所望のサイトを見出し、当該サイトのコンテンツをダウンロードして、ブラウザにより当該コンテンツを閲覧している。上記コンテンツには種々のカテゴリに属する情報があり、店舗やイベントの情報提供、鉄道路線の時刻表の提供や、鉄道の乗り換え案内なども含まれる。
【０００３】
店舗やイベントの情報提供にあっては、ユーザが携帯端末を操作して店舗やイベントのカテゴリ、検索したい地域を入力して指定したカテゴリに該当し、かつ当該地域にある店舗やイベントが検索されその情報が携帯端末装置に配信される。時刻表の提供においては、ユーザが携帯端末を操作して、路線を指定すると、当該路線の時刻表が携帯端末の表示装置の画面上に提示される。また、乗り換え案内においては、ユーザが、出発地や目的地を指定することにより、推奨する経路が提示される。
【０００４】
情報配信サーバも機能が充実され、上記のような鉄道路線やバス路線の時刻表の提供や乗り換え案内にとどまらず、従来の車載用ナビゲーションシステムの機能を携帯電話などの携帯端末に提供する情報配信サーバも実現されている。このようなシステムによれば、自動車の運転者のみならず、歩行者に対するナビゲーションサービスを提供することができる。
【０００５】
携帯電話のユーザは上記のようなサービスを利用して種々の所望の情報を得ることができる。例えば、ユーザが興味を持っている興味対象場所（Point  of  Interest：以下単にＰＯＩという）に関する地図や営業内容、価格、営業時間などの情報を得ることができる。ＰＯＩとは、例えば、ホテル、レストラン、デパート、テーマパーク、コンビニ、ガソリンスタンド、運動施設、公園などのあらゆる店舗、施設が対象となり得る。このためＰＯＩは種類（カテゴリ）が膨大であり、当該カテゴリに属する店舗、場所も無数に存在する。情報配信サーバがカバーする範囲が広ければ広い程その数も増加する。
【０００６】
従って、これら無数のＰＯＩに関する情報をユーザに提供するため、情報配信サーバはＰＯＩデータベースを備えている。このＰＯＩデータベースにおいては、ＰＯＩはカテゴリ分けされており、また、このＰＯＩカテゴリはその数の多さから大分類、中分類、小分類などと階層化されている。ユーザは携帯端末に表示されたメニュー画面から所望のＰＯＩカテゴリを選択して情報配信サーバにデータを要求することになるが、特定の所望のＰＯＩカテゴリを選択するために、大分類、中分類、小分類とカテゴリの階層をたどり、情報配信を希望するＰＯＩカテゴリを選択することになる。
【０００７】
また、ユーザが特定のＰＯＩに関する情報の配信を希望する場合は、当該ＰＯＩを利用する意図を持っているのが普通であるから、ユーザが希望する地域や現在地周辺のＰＯＩに関する情報を得ることが目的であることが一般的である。従ってＰＯＩカテゴリを選択するとともに、ＰＯＩの存在する地域や自身の現在位置情報を指定する操作を伴う。
【０００８】
ユーザが利用する携帯端末が携帯電話である場合、最近の携帯電話はＧＰＳ受信機を備え、ＧＰＳ衛星からの信号を受信して自身の現在位置を算出する測位機能を有しておりこの機能を利用して現在位置を情報配信サーバに送信することができる。また、ナビゲーションサービスを受けることのできる携帯端末であれば、所望の特定のＰＯＩ情報を得た後、現在位置または自宅、勤務先など所望の出発地として当該特定のＰＯＩまでの経路探索を受けることもできる。
【０００９】
このようなＰＯＩ情報提供システムは種々提案されている。例えば、下記の特許文献１（特開２００３−１３２４８３号公報）に「情報配信方法」として開示されたシステムが知られている。
【００１０】
この特許文献１に開示された情報配信方法は、情報配信コンピュータシステムと端末装置である携帯電話とからなるシステムである。この情報配信コンピュータシステムは、外部の携帯電話から或るＰＯＩの案内情報が要求されると、所望ＰＯＩの案内情報に、ＰＯＩの位置情報と最適経路情報の情報配信コンピュータシステムに対する経路探索要求用のＵＲＬをリンク情報とするリンクを付随させて要求元に返信する。該携帯電話でＰＯＩの案内情報と一緒に表示されたリンクを選択すると、ＧＰＳ受信部で検出された現在位置を出発地、ＰＯＩの位置情報を目的地、計時部で計時された日時を出発予定日時とした経路探索条件が自動設定され、情報配信コンピュータシステムに対し、経路探索条件の情報を付随した経路探索要求をするように構成されている。
【００１１】
すなわち、この情報配信コンピュータシステムは、携帯電話からＰＯＩの検索要求があり、特定のＰＯＩを検索しそのＰＯＩ案内情報（地図、営業案内など）を携帯電話に配信する際に、経路探索機能へのリンク情報を付加して配信し、携帯電話がそのリンクを選択すると現在位置から当該ＰＯＩへの最適経路を探索して配信するようにしたものである。
【００１２】
また、下記の特許文献２（特開２００３−１５０４７５公報）に「情報提供システムおよび方法」として開示されたシステムも知られている。この特許文献２に開示された情報提供システムは、携帯端末とＷｅｂアプリケーションサーバからなるシステムである。
【００１３】
この情報提供システムにおいて、携帯端末を利用するユーザは、表示された提供サービスメニューから要求するサービスを選択する。選択されたサービスの情報はＷｅｂアプリケーションサーバに送信される。ＧＰＳ衛星は位置情報を出力する。携帯端末は、位置情報を受信し、受信した位置情報に基づいて現在位置を算出し、その現在位置の情報を、インターネットを介してＷｅｂアプリケーションサーバに送信する。Ｗｅｂアプリケーションサーバは、携帯端末から送信された現在位置の情報を受信し、携帯端末を利用するユーザによって選択されたサービスに関する情報であって、その現在位置に関連する情報を携帯端末に送信する。
【００１４】
一般的に、目的とするＰＯＩカテゴリに属する特定のＰＯＩが現在位置や所望の位置周辺（例えば、半径２ｋｍの範囲）に複数存在する場合、上記のようなＰＯＩ検索システムや経路案内システムにおいて検索された複数のＰＯＩに関する位置情報や関連情報は、現在位置や所望の位置から近い順に並べられて携帯端末に配信される。近い順とは現在位置や所望の位置からの各ＰＯＩまでの直線距離、または、各ＰＯＩまでの案内経路の距離が短い順である。案内経路の距離とは、徒歩移動の場合はＰＯＩまでの徒歩距離、自動車による移動にあっては案内道路の距離である。
【００１５】
現在位置周辺のＰＯＩを検索し、複数のＰＯＩが存在する場合に、現在位置から近い順に当該複数のＰＯＩの位置や関連情報を案内するシステムは、例えば、下記の特許文献３（特開平１０−２８１７９７号公報）に開示されている。特許文献３に開示された車載用ナビゲーション装置及び周辺施設検索方法は、複数のカテゴリから目的に応じた施設を簡単に探索することができて操作性が優れた車載用ナビーション装置及び周辺施設探索方法を提供するものである。
【００１６】
この車載用ナビゲーション装置及び周辺施設検索方法は、テーブル記憶部に、用途別にグループ化されるカテゴリが記憶されており、ユーザが操作部を介して用途（カテゴリ）を選択して入力すると、制御部は入力された用途に対応するグループのカテゴリに属する施設について、車両の現在位置の周辺（所定の距離範囲）に存在する施設を検索するように構成されている。検索結果は、現在位置から近い順に、該当する複数の施設が表示される。
【００１７】
【特許文献１】特開２００３−１３２４８３号公報（図１、段落［０００６］）
【特許文献２】特開２００３−１５０４７５号公報（図１、図２、段落［００１３］）
【特許文献３】特開平１０−２８１７９７号公報（図１、段落［００２８］）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
先に述べたように、一般的なナビゲーションシステムなどにおける興味対象場所（ＰＯＩ）の検索サービスでは、検索結果であるＰＯＩの情報は、現在位置や所望の位置から近い順に並べられて携帯端末に配信される。例えば、上記特許文献３に開示されたナビゲーションシステムの説明に記載されているように、ユーザが手洗所を探すような場合は現在位置から近い順に複数のＰＯＩをＰＯＩリストとして携帯端末に配信する方法であっても、最も近いＰＯＩで目的が果たせるので問題はない。
【００１９】
しかしながら、このような検索結果の配信方法ではユーザの目的に添わないケースが生じる。例えば、薬局で薬を買いたい場合である。慣れている鎮痛剤があるので、その銘柄を買いたいとする。携帯電話を端末としたナビゲーションシステムのロケーションサービスを使用して図８のサービスメニューから所望のＰＯＩカテゴリの「薬局」を選択して周辺検索を行うと、図９Ａのように現在位置から近い順に薬局のＰＯＩリストが表示される。
【００２０】
図９Ａの表示画面において、所望のＰＯＩ、例えば、Ａ薬局を選択すると図９Ｂに示すようにＡ薬局の所在地、電話番号などＰＯＩ関連情報が表示され、この画面で地図表示の項目である「地図を表示する」を選択すると現在位置、ＰＯＩ位置を含む地図を表示することができ、経路案内の項目である「ここに行く！」を選択すると現在位置からＡ薬局までの案内経路を表示することができる。
【００２１】
表示されたＰＯＩの店舗電話番号を利用して携帯電話から発呼することもできるが、在庫の確認をしている間に店舗に着いてしまうこともある。また商品の名称を明確に覚えていないと問い合わせもできないことがある。また携帯電話の通話料はデータ通信料金に比べて高い。従って近所なら直接行ってみるのが良い。
【００２２】
最も近いＡ薬局に行ってみたところ、所望の鎮痛剤の在庫が無いということがあり得る。すると、先程の図９ＡのＰＯＩリストのページに戻って、次に近いＢ薬局に行ってみる。ところが、ここも在庫が無いとすると、更に、ドラッグＣ、Ｄ薬品、Ｅ堂、ドラッグＦと立ち寄ったとすると、実は大変無駄な移動をしていることになってしまう。
【００２３】
この場合における個々のＰＯＩ店舗の位置関係を携帯端末の地図表示で見ると図１０のような位置関係にあり、この場合の移動経路は図１１のようになっている。鎮痛剤がすぐに欲しいのに、これではユーザの目的に添わず利便性に優れた検索サービスとは言えない。
【００２４】
この原因は、特許文献３などに開示された従来のナビゲーションシステムにおけるＰＯＩ検索の結果が、現在位置からの距離（あるいは道のり）でソートしてあるので、必ずしもそのままでは最適な巡回経路になり得ないという点に問題があった。このように従来のＰＯＩ検索では、順次ＰＯＩを回らないと目的を果たすことができないようなケースに適した検索結果の提供が考慮されていなかった。すなわち、従来は複数のＰＯＩを最適経路で巡回できるようなユーザの目的行動に適した検索結果を提供できなかったという問題点があった。
【００２５】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、ＰＯＩカテゴリ検索の結果に複数のＰＯＩが含まれる場合、現在位置（または所望の位置）から最も近いＰＯＩを起点に各ＰＯＩまでの距離を総あたりで探索し、起点であるＰＯＩから最も近いＰＯＩを求め、次にそのＰＯＩを起点に最も近いＰＯＩを求める。この処理を順次繰り返して起点であるＰＯＩから次々に巡回すべきＰＯＩをソートして携帯端末に配信するようになせば、ユーザが効率よく複数のＰＯＩを巡回できるようになり、上記問題点を解消し得ることを想到して本発明を完成するに至ったものである。
【００２６】
すなわち、本発明は前述の問題点を解消することを課題とし、ＰＯＩカテゴリ検索の結果、検索された複数のＰＯＩを巡回的に訪れる場合に最適な経路探索と案内をすることができるようにしたナビゲーションシステム、情報配信サーバ、携帯端末を提供することを目的とするものである。
【課題を解決するための手段】
【００２７】
前記課題を解決するために、本願の請求項１にかかる発明は、
第１の検索モードと第２の検索モードを有し、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートし、
前記ソートされた結果を携帯端末に配信するように構成したことを特徴とする。
【００２８】
また、本願の請求項２にかかる発明は、請求項１にかかる発明において、
前記ＰＯＩデータベースは、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶するとともに、各カテゴリにそれぞれ前記第１の検索モードまたは第２の検索モードの何れかを示す検索モードの情報を記憶したことを特徴とする。
【００２９】
また、本願の請求項３にかかる発明は、請求項１にかかる発明において、
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、前記抽出された各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートすることを特徴とする。
【００３０】
また、本願の請求項４にかかる発明は、請求項１にかかる発明において、
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートすることを特徴とする。
【００３１】
また、本願の請求項５にかかる発明は、請求項３または請求項４にかかる発明において、
前記ナビゲーションシステムは、更に、前記ソートモード選択手段を備え、前記第１のソートモードまたは第２のソートモードを任意に選択するようになしたことを特徴とする。
【００３２】
本願の請求項６にかかる発明は、
検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備えた携帯端末とネットワークを介して接続される情報配信サーバであって、
前記情報配信サーバは第１の検索モードと第２の検索モードを有し、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートし、
前記ソートされた結果を前記携帯端末に配信するように構成したことを特徴とする。
【００３３】
また、本願の請求項７にかかる発明は、請求項６にかかる発明において、
前記ＰＯＩデータベースは、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶するとともに、各カテゴリにそれぞれ前記第１の検索モードまたは第２の検索モードの何れかを示す検索モードの情報を記憶したことを特徴とする。
【００３４】
また、本願の請求項８にかかる発明は、請求項６にかかる発明において、
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートすることを特徴とする。
【００３５】
また、本願の請求項９にかかる発明は、請求項６にかかる発明において、
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートすることを特徴とする。
【００３６】
本願の請求項１０にかかる発明は、
第１の検索モードと第２の検索モードを有し、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶したＰＯＩデータベースと、前記ＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、
前記ＰＯＩソート手段は、前記第１の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、前記第２の検索モードが設定された時は、前記ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする情報配信サーバとネットワークを介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする携帯端末。
【００３７】
また、本願の請求項１１にかかる発明は、請求項１０にかかる発明において、
前記ＰＯＩソート手段は更に、第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、前記抽出された各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする情報配信サーバにネットワークに介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする。
【００３８】
また、本願の請求項１２にかかる発明は、請求項１０にかかる発明において、
前記ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予め設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートする情報配信サーバにネットワークに介して接続される携帯端末であって、
前記携帯端末は、検索モードを決定する検索モード選択手段と、ＰＯＩのカテゴリを選択して所望のＰＯＩ検索要求を行うための操作・入力手段と、を備え、前記情報配信サーバから配信されたＰＯＩ検索結果を受信することを特徴とする。
【００３９】
また、本願の請求項１３にかかる発明は、請求項１１または請求項１２にかかる発明において、
前記携帯端末は、更に、前記ソートモード選択手段を備え、前記第１のソートモードまたは第２のソートモードを任意に選択するようになしたことを特徴とする。
【発明の効果】
【００４０】
請求項１にかかる発明においては、ナビゲーションシステムがＰＯＩデータベースを参照して、現在位置または所定の位置を含む所定の範囲内の該当ＰＯＩを検索する検索手段と、検索された複数のＰＯＩを第１の検索モードと第２の検索モードの何れかに基づいてソートするＰＯＩソート手段と、を備え、ＰＯＩソート手段は、第１の検索モードが設定された時は、ＰＯＩ検索手段によって検索された複数のＰＯＩを、現在位置または所定の位置に近い順にソートし、第２の検索モードが設定された時は、ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする。
従って、ユーザは任意に第１の検索モードまたは、第２の検索モードを選択して、所定位置から近い順にソートされた各ＰＯＩの情報、または、現在位置または所定の位置から最短経路で順次複数のＰＯＩ巡回する経路の順にソートされたＰＯＩの情報を得ることができるようになる。
【００４１】
請求項２にかかる発明においては、請求項１にかかる発明のナビゲーションシステムにおいて、ＰＯＩデータベースは、各ＰＯＩ毎にＰＯＩの位置情報を含むＰＯＩ情報をカテゴリ別に記憶するとともに、各カテゴリにそれぞれ前記第１の検索モードまたは第２の検索モードの何れかを示す検索モードの情報を記憶したものである。
従って、ユーザは、ＰＯＩを検索するためにＰＯＩのカテゴリを設定するだけで、第１の検索モードまたは第２の検索モードを設定できるようになり、操作が容易になる。
【００４２】
請求項３にかかる発明においては、請求項１にかかる発明のナビゲーションシステムにおいて、ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第１のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩのうち、現在位置または所定の位置を中心に所定の距離範囲に存在するＰＯＩを抽出し、前記抽出された各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする。
従って、ユーザは第１のソートモードを選択することによって、従来の経路と比較して無駄な移動がない最適経路でＰＯＩを巡回することができるようになり、かつ、現在位置または所定の位置を中心に一定の距離範囲を逸脱することなく、目的とするＰＯＩを巡回することができるようになる。
【００４３】
請求項４にかかる発明においては、請求項１にかかる発明のナビゲーションシステムにおいて、ＰＯＩソート手段は第１のソートモードと第２のソートモードを有し、前記第２の検索モードが選択され、かつ、第２のソートモードが選択された場合、前記ＰＯＩソート手段は、前記ＰＯＩ検索手段が検索した複数のＰＯＩの全てを対象に、予めが設定された巡回ＰＯＩ数だけ、現在位置または所定の位置に最も近いＰＯＩを起点として、最短経路で移動できる次のＰＯＩを順次選択してソートする。
従って、ユーザは第２のソートモードを選択することによって、従来の経路と比較して無駄な移動がない最適経路でＰＯＩを巡回することができるようになり、かつ、現在位置または所定の位置から遠ざかる方向に最短経路で巡回すべきＰＯＩが存在する場合、経路は現在位置または所定の位置から遠ざかる経路になるものの、目的のＰＯＩを最短経路で巡回することができるようになる。
【００４４】
請求項５にかかる発明においては、請求項３または請求項４にかかる発明のナビゲーションシステムにおいて、前記ナビゲーションシステムは、更に、前記ソートモード選択手段を備え、前記第１のソートモードまたは第２のソートモードを任意に選択するように構成される。従って、ユーザは任意に第１のソートモードまたは第２のソートモードを設定できるようになり、検索するＰＯＩの利用目的に応じて、在位置または所定の位置を中心に一定の距離範囲を逸脱することなく、目的とするＰＯＩを巡回する最適経路、または、現在位置または所定の位置から遠ざかる経路になる可能性はあるものの、目的のＰＯＩを最短経路で巡回する最適経路の何れかを検索要求することができるようになる。
【００４５】
請求項６〜請求項９にかかる発明においては、それぞれ請求項１〜請求項４にかかる発明のナビゲーションシステムを構成する情報配信サーバを提供することができるようになる。
【００４６】
請求項１０〜請求項１３にかかる発明においては、それぞれ請求項１、請求項３、請求項４、請求項５にかかる発明のナビゲーションシステムを構成する携帯端末を提供することができるようになる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。以下の実施例においては、携帯電話機を端末装置とし、経路探索および経路案内を行うナビゲーションシステムにＰＯＩ情報提供機能を備えたナビゲーションシステムを具体例として説明するが、本発明はこのような実施例に限ることなく、ＰＯＩ情報を提供する機能を単独に有するシステムであってもよく、端末装置は携帯電話機のような携帯型の端末装置でもよく、また、車載型の端末装置のような移動端末であってもよい。本明細書においては、移動端末を含めて携帯端末と総称する。
【実施例】
【００４８】
図１は、本発明の実施例にかかるナビゲーションシステムの構成を示す図である。ナビゲーションシステム１０は、図１に示すように、インターネットなどのネットワーク１１を介して接続される携帯端末２０と情報配信サーバ３０を備えて構成されている。情報配信サーバ３０は、端末装置２０にＰＯＩ情報を提供するため、ＰＯＩカテゴリ別に区分し、当該カテゴリに属する各ＰＯＩとその位置情報（緯度・経度）などＰＯＩに関連する情報を蓄積したデータベースであるＰＯＩＤＢ３７と、ＰＯＩ検索手段３８と、ＰＯＩソート手段３９と、を備えている。
【００４９】
ＰＯＩＤＢ３７には、後述するようにＰＯＩのカテゴリ毎に、そのカテゴリに属する個々のＰＯＩの位置情報（緯度・経度）や案内地図、営業案内などのＰＯＩ関連情報が蓄積されており、携帯端末２０から現在位置と所望のＰＯＩカテゴリを指定した検索要求が送信されると、ＰＯＩＤＢ３７を参照して、携帯端末の現在位置から所定の範囲内、例えば、半径２ｋｍ以内に存在するＰＯＩを検索してそのＰＯＩ関連情報を携帯端末２０に配信する。なお、ＰＯＩの検索は必ずしも現在位置を基準として検索要求する必要はなく、所望の目的地を基準として検索要求することもできる。このように特定の場所を基準とした周辺のＰＯＩなどについての検索を一般には周辺検索という。
【００５０】
携帯端末２０は例えばＧＰＳ測位手段を搭載した携帯電話機であり、現在地や目的地周辺の周辺検索、すなわち、所望のＰＯＩ検索が行える。現在位置や目的地の位置情報を付けて周辺検索要求を情報配信サーバ３０に送ると、情報配信サーバ３０は、携帯端末２０の現在位置または目的地の位置を考慮して、その位置から所定の範囲、例えば半径２ｋｍ以内に存在するＰＯＩを検索できるように構成する。ＰＯＩ検索にあたって携帯端末２０はＰＯＩカテゴリの選択画面が表示され、ユーザは所望のＰＯＩカテゴリを選択して情報配信サーバ３０に当該ＰＯＩカテゴリに属するＰＯＩを検索させる。以下の説明においては、現在位置を基準とした周辺検索を例にとり具体例を説明することとする。
【００５１】
図２は、ＰＯＩＤＢ３７に蓄積されたＰＯＩ関連情報の構成の一例を示す図である。Ａレストラン、Ｂレストランなどの個々のＰＯＩはそれぞれカテゴリ分けされ、カテゴリのコード（４桁の数値）、カテゴリ名、検索モード（第１の検索モードまたは第２の検索モード）が記憶され、それぞれのカテゴリに属する個々のＰＯＩについてその位置情報（緯度・経度）や番地、地図番号、営業案内、その他などＰＯＩ関連情報か記憶されている。
【００５２】
本実施例にかかる情報配信サーバ３０は、携帯端末２０から要求されたＰＯＩを検索して携帯端末２０に検索結果を配信する場合に、ＰＯＩソート手段３９において、従来のように現在位置から近い順に複数のＰＯＩを並べて配信する第１の検索モードと、現在位置から最短経路で各ＰＯＩを巡回できる順にＰＯＩを並べて配信する第２の検索モードを有する。第２の検索モードにおいては、ＰＯＩ検索手段によって検索された複数のＰＯＩについて、各ＰＯＩ間の距離を検索して現在位置または所定の位置に最も近いＰＯＩを起点として最短経路で各ＰＯＩを巡回できる順に各ＰＯＩをソートする。
【００５３】
最短経路で各ＰＯＩを巡回する順序（ソート順）は、現在位置（または所望の位置）から最も近いＰＯＩを起点に各ＰＯＩまでの距離を総あたりで検索し、起点であるＰＯＩから最も近いＰＯＩを求め、次にそのＰＯＩを起点に最も近いＰＯＩを求める。更にこのＰＯＩを起点に同様の処理を順次繰り返して、起点であるＰＯＩから次々に巡回すべきＰＯＩをソートすることで処理することができる。また、総あたりでＰＯＩ間の距離を検索する方法によらず、例えば、特開平８−２０２６７５号公報に開示された手法を適用して求めることもできる。
【００５４】
例えば、図２において、「グルメ（コード０００１）」のカテゴリは、検索モードが第１のモードであり、このカテゴリに属するＡレストラン〜Ｘレストランなどについてそれぞれ個々のＰＯＩのＰＯＩ関連情報が蓄積されている。「薬局（コード０００４）」のカテゴリは、検索モードが第２のモードであり、このカテゴリに属するＡ薬局〜Ｄ薬品などについてそれぞれ個々のＰＯＩの関連情報が蓄積されている。
【００５５】
従って、携帯端末２０が「グルメ」のカテゴリを選択して情報配信サーバ３０にＰＯＩ検索要求すると、情報配信サーバ３０からの検索結果は第１の検索モード、すなわち、現在位置から近い順にソートされ、該当するＰＯＩの情報が並べられて配信される。これに対して携帯端末２０が「薬局」のカテゴリを選択して情報配信サーバ３０にＰＯＩ検索要求すると、情報配信サーバ３０からの検索結果は第２検索モード、すなわち、現在位置から最も近いＰＯＩを起点に各ＰＯＩを最短の経路で巡回できる順序にソートされて該当するＰＯＩの情報が配信される。このため、情報配信サーバ３０は検索モード検出手段３６を備えており、携帯端末２０において選択されたＰＯＩのカテゴリに基づいて検索モードを検出する。
【００５６】
携帯端末２０はＰＯＩの検索要求にあたって、第１、第２の検索モードのいずれでＰＯＩ検索要求するかを選択する。本実施例においては、前述のように、ＰＯＩＤＢ３７に蓄積したＰＯＩデータのカテゴリ別に第１の検索モードか第２の検索モードかの設定がなされており、携帯端末２０がＰＯＩ検索のカテゴリを選択することにより自動的に検索モードが指定される。
【００５７】
現在位置周辺の複数の所望ＰＯＩを最短経路で巡回するＰＯＩ順序は、ユーザの検索目的の態様によって、次の２通りが考えられる。第１の態様は、現在位置を中心にある一定の範囲、例えば、半径２ｋｍ以内に設定された周辺検索で得られた複数のＰＯＩのうち、半径５００ｍ以内のＰＯＩを最短経路で巡回したいという場合である。これは、昼休みに現在位置から離れることなく目的の商品を購入したいというケースが該当する。
【００５８】
第２の態様は、最短経路でＰＯＩ巡回した結果、現在位置から離れてしまう経路になるＰＯＩ順であっても、とにかく早く各ＰＯＩを巡回して目的の商品を購入したいというという場合である。例えば、薬局で特定の薬を早く購入したい場合、半径２ｋｍ以内に設定された周辺検索で得られた複数のＰＯＩについて最短経路で順に結ばれるＰＯＩ順序を無条件でソートしてユーザに提示するものである。この場合、次々に最短経路で結ばれるＰＯＩを巡回した結果、現在位置からどんどん遠くに離れていく経路が最適経路になることがある。
【００５９】
第１の態様、第２の態様のいずれを選択するかは、携帯端末２０における周辺探索のサービスメニュー画面からユーザが選択する。これについては後に図面を参照して詳細に説明する。そして、情報配信サーバ３０おいては、ＰＯＩソート手段３９が第１のソートモードと第２のソートモードを有しており、第１の態様には第１のソートモード、第２の態様には第２のソートモードが対応する。
【００６０】
また、情報配信サーバ３０は、制御手段３１、配信データ編集手段３２、経路探索手段３３、通信手段３４、経路探索用ネットワークデータ３５を備えている。探索用ネットワークデータ３５には、徒歩および自動車用の経路探索のための道路ネットワークデータと、交通機関を用いた経路探索のための交通ネットワークデータとを蓄積している。ネットワークデータの構成については後述する。
【００６１】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４は、ネットワーク１１、１２を介して携帯端末２０や、各種のＰＯＩ情報を提供するＰＯＩ情報提供サーバ５０と通信するためのインターフェースである。配信データ編集手段３２は、経路探索やＰＯＩ検索の結果を携帯端末２０に配信するためのデータに編集するためのものである。情報配信サーバ３０は、ネットワーク１２を介して各種のＰＯＩ情報提供サーバ５０からＰＯＩの情報を収集してＰＯＩＤＢ３７にデータベース登録し、ユーザに提供できるＰＯＩ情報を充実してゆくことができる。
【００６２】
経路探索手段３３はマルチモーダルな経路探索エンジンであって徒歩と交通機関を併用した経路探索機能を有するものである。このような経路探索エンジンは例えば特開２０００−２５８１８４号公報などに開示されている。経路の探索方法としては周知のダイクストラ法と呼ばれる手法が適用され、経路探索条件やＰＯＩ検索の条件は携帯端末２０から送信される。
【００６３】
一方、携帯端末２０は、図１に示されるように、制御手段２１、通信手段２２、ＧＰＳ受信機などからなる測位手段２３、液晶表示ユニットなどからなる表示手段２４、情報配信サーバ３０から配信されたデータなど記憶する配信データ記憶手段２５、情報配信サーバ３０に対する各種要求を編集する配信要求編集手段２６、操作・入力手段２７を備えている。
【００６４】
制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２７は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力手段ためのものであり、出力手段である表示手段２４に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２４は操作・入力手段２７の一部としても機能する。通信手段２２は、ネットワーク１１を介して情報配信サーバ３０と通信するためのインターフェースである。
【００６５】
ユーザが情報配信サーバ３０にＰＯＩの検索を依頼しようとする場合、携帯端末２０において操作・入力手段２７を操作し、図３に示すサービスメニュー画面を表示手段２４に表示して所望の選択入力を行う。図３において、図３Ａは周辺検索のサービスメニュー画面の構成、図３Ｂは図３Ａから遷移したメニュー画面の構成を示す図である。
【００６６】
例えば、ユーザが現在位置周辺の薬局で特定の薬を購入したい場合、図３Ａのサービスメニュー画面において「薬局」のカテゴリを選択する。カテゴリが選択されるとサービスメニュー画面は図３Ｂの画面に遷移する。図３Ｂのサービスメニュー画面において「現在地周辺で探す」の選択項目は、前述した第１の態様を選択する項目であり、この項目が選択されると、ＰＯＩソート手段３９は第１のソートモードに設定される。「とにかく早く探す」は前述した第２の態様を選択する項目であり、この項目が選択されると、ＰＯＩソート手段３９は第２のソートモードに設定される。
【００６７】
第１のソートモードの場合、ＰＯＩソート手段３９は、所定の範囲、例えば、半径５００ｍの範囲内のＰＯＩを抽出し、現在位置から最も近いＰＯＩを起点に最短経路で各ＰＯＩを巡回する順にＰＯＩをソートする。従って、ユーザは現在位置から半径５００ｍ以上離れることはなく、容易に現在位置に戻ることができる。
【００６８】
第２のソートモードの場合、ＰＯＩソート手段３９は、ＰＯＩ検索手段３８により検索された（例えば、現在位置から半径２ｋｍ以内）の全てのＰＯＩを対象に、現在位置から最も近いＰＯＩを起点に最短経路で各ＰＯＩを巡回する順にＰＯＩをソートする。ユーザはＰＯＩの位置関係によっては現在位置から遠ざかる方向に移動する必要があるが、距離的に近いＰＯＩを巡回して、素早く目的を達成できる可能性がある。
【００６９】
例えば、第１の態様の「現在地周辺で探す」を選択すると、測位手段２３が測位した現在位置と、ＰＯＩカテゴリを「薬局」としたＰＯＩ検索要求（周辺検索要求）が情報配信サーバ３０に送信される。この周辺検索要求を受信すると情報配信サーバ３０は先ず、ＰＯＩ検索手段３８はＰＯＩＤＢ３７を参照して、現在位置を中心にある一定の範囲、例えば、半径２ｋｍ以内に存在する個々のＰＯＩである薬局を検索する。
【００７０】
このＰＯＩ検索により抽出された薬局が、例えば、図１０のようにＡ〜Ｆの６ケ所であり、これら薬局Ａ〜Ｆの地図上の位置関係が図１１のような位置関係であったとする。図１１における☆印が携帯端末２０の現在位置であり、Ａ〜Ｅを結ぶ各矢印は従来の方法により巡回する場合の経路を示す。
【００７１】
ここで、ＰＯＩソート手段３９は、この周辺検索で得られた複数の薬局のうち、例えば、半径５００ｍ以内の薬局、例えば、図１０のＡ〜Ｅの５ケ所を抽出する、そして、現在位置に最も近い薬局（最初に巡回すべき薬局）を起点として各薬局までのルートを総当たりで検索して最も短い経路になるＰＯＩの順を決定する。現在位置に最も近い薬局Ａを起点にすると、残りのＰＯＩはＢ〜Ｅの４箇所であるので、合計２４通り（４！）の経路を求め、最短の経路を巡回経路として決定すればよい。現在位置を起点としても薬局Ａ〜Ｅの５箇所について合計１２０通り（５！）の経路を求め、最短の経路を巡回経路として決定すればよい。経路の探索と距離の演算は経路探索用ネットワークデータ３５を参照して行う。ＰＯＩ間の距離は経路の徒歩移動距離であることが好ましい。
【００７２】
このような処理の結果、巡回すべき薬局の順序は「Ａ→Ｃ→Ｂ→Ｄ→Ｅ」となり、図１１に示した従来の経路と比較して無駄な移動がなくなる最適経路となる。ＦはＣから最短の経路で巡回できるが半径５００ｍの範囲内から外れているので、第１の態様（第１のソートモード）においては巡回経路から除かれる。このような最適経路順でＰＯＩを案内すると、ユーザは現在位置を中心に一定の距離範囲を逸脱することなく、最短経路で目的とするＰＯＩを巡回することができるようになる。
【００７３】
上記第１のソートモードで処理されたＰＯＩ検索結果は情報配信サーバ３０から携帯端末２０に配信され、表示手段２４に図４Ａの表示画面として表示される。ユーザがルート案内の項目を選択すると、現在位置付近の地図が表示され、各薬局Ａ〜Ｅの位置マークとそれらを最短経路で巡回する経路を表示することができる。
【００７４】
第２の態様の「とにかく早く探す」の項目が選択されると、ＰＯＩソート手段３９は、半径２ｋｍ以内に存在する個々のＰＯＩである薬局Ａ〜Ｆ無条件に対象とし、予め設定された巡回ＰＯＩ数に達するまで、現在位置に最も近い薬局（最初に巡回すべき薬局）を起点として各薬局までのルートを総当たりで検索し、起点の薬局に距離が最も近い薬局（２番目に巡回すべき薬局）を特定する。次に、特定された２番目に巡回すべき薬局を起点として残りの薬局について同様の処理を行い、３番目に巡回すべき薬局、４番目に巡回すべき薬局、５番目に巡回すべき薬局・・・と予め設定された巡回ＰＯＩ数に達するまで順次特定していきソート結果とする。
【００７５】
ただし、この第１のソートモードを選択する場合、ユーザは巡回を所望するＰＯＩの数を指定する。例えば、この場合ユーザが巡回を所望するＰＯＩの数を「５」と指定したものとする。なお、巡回を所望するＰＯＩの数は、必ずしもユーザが指定する構成とする必要はなく、第２のソートモードが選択された場合、経路探索サーバ３０側に予め設定された巡回ＰＯＩ数に基づいて処理するように構成することもできる。
【００７６】
この第２のソートモードの場合、範囲を指定する第１のソートモードと異なり、ＰＯＩ間の距離が近ければどの方向に行ってもかまわない、いわば成り行きまかせの巡回順の決定になる。従って、現在位置からは距離の遠くないＰＯＩがあっても、巡回を所望するＰＯＩ数に従った上記最短経路の検索の結果、最短経路に上記のＰＯＩが含まれない場合もあり、その場合当該ＰＯＩは巡回経路から外れることになる。
【００７７】
このようにして特定された薬局の最短距離での巡回の順は「Ａ→Ｃ→Ｆ・・・」となる。この場合、Ｆに近い次に巡回すべき薬局はＢまたはＥであるが、Ｆの近くに現在位置から遠ざかる方向に近い薬局が存在する場合、巡回経路は現在位置から遠ざかる経路になり、ユーザは現在位置からは離れていくが、所望の数のＰＯＩを最短経路で巡回することができるようになる。
【００７８】
上記第２のソートモードで処理されたＰＯＩ検索結果は情報配信サーバ３０から携帯端末２０に配信され、表示手段２４に図４Ｂの表示画面として表示される。ユーザがルート案内の項目を選択すると、現在位置付近の地図が表示され、各薬局Ａ〜Ｆ・・・の位置マークとそれらを最短経路で巡回する経路を表示することができる。
【００７９】
次に、上記ＰＯＩ検索における情報配信サーバ３０の処理手順について図５のフローチャートを参照して説明する。携帯端末２０において、測位手段２３で現在位置が測位され、前述のごとくしてサービスメニュー画面において所望のＰＯＩカテゴリが選択されて周辺検索の要求がなされる。情報配信サーバ３０がこの周辺検索要求を受信すると、ステップＳ１０の処理において選択されたカテゴリに基づいて検索モードが第１モード、第２モードのいずれであるかが判定される。
【００８０】
検索モードはＰＯＩＤＢ３７に記憶されたカテゴリ毎のモードを参照して判断される。第１の検索モードは従来のＰＯＩ検索、結果配信（現在位置からの距離が近い順に該当するＰＯＩを順にソートして配信するモードである。第２の検索モードが現在位置から最短経路でＰＯＩを順次巡回する順にＰＯＩをソートして配信するモードである。
【００８１】
ステップＳ１０の処理において、第１の検索モードであると判別されると、ＰＯＩ検索手段３８はステップＳ１１の処理において、ＰＯＩＤＢ３７を参照して従来と同様に現在位置を中心に予め設定された距離範囲内において選択されたＰＯＩのカテゴリに属する個々のＰＯＩを検索する。そしてステップＳ１２の処理において、ＰＯＩソート手段３９は検索結果として得られたＰＯＩが複数存在する場合は、現在位置から距離の近い順にソートする。ステップＳ１８の処理において配信データ編集手段３２はソートされたＰＯＩの情報を携帯端末２０に配信するデータとして編集し、ステップＳ１９の処理において編集されたＰＯＩの情報を携帯端末２０に配信する（図９Ａ参照）。
【００８２】
ステップＳ１０の処理において、第２の検索モードであると判別されると、ステップＳ１４の処理において、ユーザが選択した態様が第１のソートモードか、第２のソートモードかが判定される。
【００８３】
図３Ｂにおいて「現在地周辺で探す」の項目が選択された場合が第１のソートモードであり、「とにかく早く探す」の項目が選択された場合が第２のソートモードである。第１のソートモードはユーザが現在位置を中心にそこから遠ざかることなく周辺のＰＯＩを最短経路で巡回できるように検索結果である複数のＰＯＩをソートする処理、すなわち、ユーザが現在位置に戻る場合の態様である。また、第２のソートモードは、現在位置から遠ざかるか否かとは無関係に、現在位置から最も近いＰＯＩを起点に複数のＰＯＩ間を最短経路で結ぶ経路で巡回できるようにソートする処理、すなわち、ユーザが無条件で最短の経路をたどりＰＯＩを巡回して目的を果せるようにする態様である。
【００８４】
ステップＳ１４の処理において、第１のソートモードであると判別されると、ＰＯＩ検索手段３８はステップＳ１５の処理において、検索結果として得られた複数のＰＯＩのうち、所定の距離範囲内、例えば半径５００mの範囲内のＰＯＩを抽出する。そしてステップＳ１７の処理において、ＰＯＩソート手段３９は、現在位置に最も近いＰＯＩ（最初に巡回すべき薬局）を起点として各ＰＯＩまでの経路（距離）を総当たりで検索し、起点のＰＯＩに距離が最も近いＰＯＩ（２番目に巡回すべきＰＯＩ薬局）を特定する。次に、特定された２番目に巡回すべきＰＯＩを起点として残りのＰＯＩについて同様の処理を行い、３番目に巡回すべきＰＯＩ、・・・と同様の処理を繰り返し巡回するＰＯＩ順を順次特定しソートする。
【００８５】
この処理が終了すると、ステップＳ１８の処理において配信データ編集手段３２はソートされたＰＯＩの情報を携帯端末２０に配信するデータとして編集し、ステップＳ１９の処理において編集されたＰＯＩの情報を携帯端末２０に配信する（図４Ａ参照）。
【００８６】
このような処理の結果、巡回すべきＰＯＩが最短の経路で結ばれ、図１１に示した従来の経路と比較して無駄な移動がなくなる最適経路となる。ユーザは現在位置を中心に一定の距離範囲を逸脱することなく、最短経路で目的とするＰＯＩを巡回することができるようになる。
【００８７】
ステップＳ１４の処理において、第２のソートモードであると判別されると、ＰＯＩソート手段３９はＰＯＩ検索手段３８が検索した検索結果として得られた複数のＰＯＩの全てをソート対象とする（ステップＳ１６）。そしてステップＳ１７の処理において、ＰＯＩソート手段３９は、現在位置に最も近いＰＯＩ（最初に巡回すべき薬局）を起点として各ＰＯＩまでの経路を総当たりで検索し、起点のＰＯＩに距離が最も近いＰＯＩ（２番目に巡回すべきＰＯＩ薬局）を特定する。次に、特定された２番目に巡回すべきＰＯＩを起点として残りのＰＯＩについて同様の処理を行い、３番目に巡回すべきＰＯＩ、・・・と同様の処理を繰り返し巡回するＰＯＩ順を順次特定しソートする。
【００８８】
この処理が終了すると、ステップＳ１８の処理において配信データ編集手段３２はソートされたＰＯＩの情報を携帯端末２０に配信するデータとして編集し、ステップＳ１９の処理において編集されたＰＯＩの情報を携帯端末２０に配信する（図４Ｂ参照）。
【００８９】
このようにして特定されたＰＯＩの最短距離での巡回の順によれば、現在位置から遠ざかる方向に最短経路で巡回すべきＰＯＩが存在する場合、経路は現在位置から遠ざかる経路になるものの目的のＰＯＩを最短経路で巡回することができるようになる。
【００９０】
図１のナビゲーションにおいて、経路探索手段３３は現在位置から周辺検索において検索されたＰＯＩまでの経路を探索して案内することができる。例えば、図４Ａ、図４ＢのＰＯＩ検索結果の表示画面において、「ルート案内開始」の項目が選択されること経路探索を行い、現在位置から表示画面で選択されたＰＯＩまでの経路案内ができる。また、通常のナビゲーションシステムと同様に携帯端末２０から送信された経路探索条件（現在位置または出発地、目的地、移動手段など）に基づいて経路を探索して携帯端末２０に案内することができる。
経路探索に用いられる経路探索用ネットワークデータ３５は、自動車、歩行者用の経路を探索するための道路ネットワークデータと、交通機関を用いる場合いの経路探索用の交通ネットワークデータを含んでいる。
【００９１】
経路探索のための道路ネットワークは以下のように構成されている。例えば、道路が図６に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータと構成される。
【００９２】
すなわち、図６において、○印、◎印がノードを示し、◎印は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図６では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９３】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図６において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００９４】
図６ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクトスラ法と呼ばれる周知の手法によって行われる。
【００９５】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図７に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図７において、○印、◎印がノードを示し、◎印は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９６】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図７に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００９７】
図７に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００９８】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図７において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００９９】
ＰＯＩへの経路探索機能を提供する場合は、経路探索のためのネットワークデータに、各ＰＯＩ位置（緯度・経度）をノードとして追加したデータとし、所望の出発地から所定の位置からそのＰＯＩのノードまでの経路を探索して案内するように構成すればよい。例えば、特定のホテルを指定したＰＯＩ検索要求し、空港からそのＰＯＩまでの経路探索要求をして最適な経路案内を受けることができる。
【０１００】
上記実施例においては、第１の検索モードと第２の検索モードはＰＯＩのカテゴリ毎に設定されＰＯＩＤＢ３７に蓄積したＰＯＩのデータ中に記録され、携帯端末２０において検索したいＰＯＩのカテゴリが選択されると、情報配信サーバ３０側で自動的に第１または第２の検索モードが自動的に選択される態様を説明した。しかしながら、あるＰＯＩのカテゴリが一様に何れかの検索モードに設定した場合、あるユーザにとって利便性が損なわれるケースがあり得る。例えば、「グルメ」カテゴリは上記実施例では第１の検索モードに設定されているが、第２の検索モードで検索を希望するユーザもあり得る。検索されたＰＯＩで所望のメニューが提供されておらず、他のＰＯＩを巡回するようなケースも起こり得るからである。
【０１０１】
このような不具合に対応するためには、ユーザに２つ詮索モードの相違を理解してもらい、操作・入力手段２７を操作して所望の検索モードを選択させる態様とすると好都合である。ユーザはＰＯＩのカテゴリによらず、自身の希望により第１または第２の検索モードを選択することができるからである。この場合、操作・入力手段２７が検索モードの選択手段として機能するが、上記実施例においては、ＰＯＩＤＢ３７が検索モードの選択手段として機能しているということができる。
【０１０２】
また、ＰＯＩの種類が多岐にわたるため、周辺検索のサービスメニュー画面にカテゴリを表示しきれない場合には、カテゴリをキーワード検索により検索して回答されたカテゴリから選択する構成をとることもできる。
【産業上の利用可能性】
【０１０３】
本発明は、現在地から所望のＰＯＩを検索する場合に適するので、携帯電話などを端末装置として用いたナビゲーションシステムに適用するのに好適である。また、本発明は、明確な目的が無い散策のような利用方法に適している。例えば、古本屋めぐりをしたい場合、神田神保町駅を出たところで、古本屋カテゴリで検索を行うと、ちょうどその近辺の巡回経路が作成される。古本を買う場合は、同じ本があったとしてもその本の傷みの程度や価格を勘案して購入先を決めるので、効率よく各ＰＯＩを結ぶ巡回経路を回ってから決めることも出来る。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施例にかかるＰＯＩ情報提供システムの構成を示す図である。
【図２】ＰＯＩカテゴリデータベース（ＤＢ）に蓄積されるＰＯＩ情報のデータ構成を示す説明図である。
【図３】本発明の携帯端末における周辺検索のサービスメニュー画面の構成を示す図であり、図３Ａは周辺検索のサービスメニュー画面の構成、図３Ｂは図３Ａから遷移したメニュー画面の構成を示す図である。
【図４】情報配信サーバから配信されたＰＯＩ検索結果の表示画面の構成を示す図であり、図４Ａは第１のソートモードにかかるソート結果を、図４Ｂは第２のソートモードにかかるソート結果を示す表示画面の構成を示す図である。
【図５】本発明の実施例にかかるＰＯＩ検索、検索結果の配信の手順を示すフローチャートである。
【図６】道路ネットワークのデータの概念を示す模式図である。
【図７】交通ネットワークのデータの概念を示す模式図である。
【図８】従来のＰＯＩ検索メニュー画面の構成を示す図である。
【図９】従来のＰＯＩ検索結果を示す表示画面の構成を示す図であり、図９ＡはＰＯＩリスト画面の構成を示す図、図９ＢはＰＯＩリスト画面で選択されたＰＯＩのＰＯＩ情報表示する表示画面の構成を示す図である。
【図１０】検索されたＰＯＩが地図上に現在位置とともにマークされた表示画面の構成を示す図である。
【図１１】従来のＰＯＩ検索の結果に基づいて現在位置から近い順にＰＯＩを巡回する場合の経路を示す模式図である。
【符号の説明】
【０１０５】
１０・・・・ナビゲーションシステム
１１、１２・・ネットワーク
２０・・・・携帯端末
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段
２４・・・・表示手段
２５・・・・配信データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・情報配信サーバ
３１・・・・制御手段
３２・・・・配信データ編集手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・探索用ネットワークデータ
３６・・・・検索モード検出手段
３７・・・・ＰＯＩＤＢ（データベース）
３８・・・・ＰＯＩ検索手段
３９・・・・ＰＯＩソート手段
５０・・・・ＰＯＩ情報提供サーバ
【図１】
2007024624.tif 000003
【図２】
2007024624.tif 000004
【図３】
2007024624.tif 000005
【図４】
2007024624.tif 000006
【図５】
2007024624.tif 000007
【図６】
2007024624.tif 000008
【図７】
2007024624.tif 000009
【図８】
2007024624.tif 000010
【図９】
2007024624.tif 000011
【図１０】
2007024624.tif 000012
【図１１】
2007024624.tif 000013