(57)【特許請求の範囲】
【請求項１】
入力された経路探索条件に基づいて出発地から目的地までの交通手段を用いた経路を探索して案内する空席経路探索システムにおいて、
前記空席経路探索システムは、各交通手段の運行データを記憶した運行データデータベースと、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件とし、該座席条件を含む経路探索条件を入力する条件入力手段と、予約情報収集手段で収集した座席情報と予約情報と前記座席条件を含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備え、
前記経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行うことを特徴とする空席経路探索システム。
【請求項２】
前記条件入力手段は、交通手段がすべて予約可能でかつ空席であることを座席条件として入力する手段を有することを特徴とする請求項１に記載の空席経路探索システム。
【請求項３】
前記条件入力手段は、交通手段が予約可能な場合は空席であることを座席条件として入力する手段を有することを特徴とする請求項１に記載の空席経路探索システム。
【請求項４】
前記条件入力手段は、交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を入力する手段を有することを特徴とする請求項１に記載の空席経路探索システム。
【請求項５】
前記条件入力手段は、交通手段が予約なしで利用できることを座席条件として入力する手段を有することを特徴とする請求項１に記載の空席経路探索システム。
【請求項６】
前記条件入力手段は、交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を入力する手段を有することを特徴とする請求項１に記載の空席経路探索システム。
【請求項７】
探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として入力された前記座席条件を含む経路探索条件に基づいて各交通手段の運行データを記憶した運行データデータベースから運行データを参照して出発地から目的地までの交通手段を用いた経路を探索して案内する空席経路探索装置であって、
前記空席経路探索装置は、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、予約情報収集手段で収集した座席情報と予約情報と前記座席条件を含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備え、
前記経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行うことを特徴とする空席経路探索装置。
【請求項８】
交通手段がすべて予約可能でかつ空席であることを座席条件として含む探索条件が入力されることを特徴とする請求項７に記載の空席経路探索装置。
【請求項９】
交通手段が予約可能な場合は空席であることを座席条件として含む探索条件が入力されることを特徴とする請求項７に記載の空席経路探索装置。
【請求項１０】
交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を含む探索条件が入力されることを特徴とする請求項７に記載の空席経路探索装置。
【請求項１１】
交通手段が予約なしで利用できることを座席条件として含む探索条件が入力されることを特徴とする請求項７に記載の空席経路探索装置。
【請求項１２】
交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を含む探索条件が入力されることを特徴とする請求項７に記載の空席経路探索装置。
【請求項１３】
探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、予約情報収集手段で収集した座席情報と予約情報と経路探索条件に基づいて前記探索用運行データデータベースを参照して経路となる交通手段を探索する経路探索手段と、を備え、
前記経路探索手段は、経路探索に先立ち、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として含む経路探索条件に合致する座席情報と予約情報を持つ交通手段を前記運行データデータベースから抽出して探索用運行データデータベースを形成して経路探索を行う空席経路探索装置に探索条件を送信する端末装置であって、
前記端末装置は、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件とし、該座席条件を含む経路探索条件を入力する入力手段を備えたことを特徴とする端末装置。
【請求項１４】
前記条件入力手段は、交通手段がすべて予約可能でかつ空席であることを座席条件として入力する手段を有することを特徴とする請求項１３に記載の端末装置。
【請求項１５】
前記条件入力手段は、交通手段が予約可能な場合は空席であることを座席条件として入力する手段を有することを特徴とする請求項１３に記載の端末装置。
【請求項１６】
前記条件入力手段は、交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を入力する手段を有することを特徴とする請求項１３に記載の端末装置。
【請求項１７】
前記条件入力手段は、交通手段が予約なしで利用できることを座席条件として入力する手段を有することを特徴とする請求項１３に記載の端末装置。
【請求項１８】
前記条件入力手段は、交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を入力する手段を有することを特徴とする請求項１３に記載の端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーションシステムの一種である交通手段を用いた経路探索システム、すなわち、航空機、列車、電車、バスなどの交通手段を用いて出発地から目的地までの経路を探索して案内する経路探索システムに関するものであり、特に、交通手段を用いて出発地から目的地までの経路を探索する際に、使用する交通手段における空席の有無に基づいて効率よく目的地までの経路（使用する交通手段）を探索して案内できるようにした空席経路探索システム、空席経路探索装置および端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データ、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに列車時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。
【０００４】
また、航空機、列車、電車、バスなどの交通手段を用いて出発地から目的地までの経路を探索して案内する経路探索システムも知られている。このような経路探索システムは一般的には、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行データをデータベース化した運行データＤＢ（データベース）を参照して、乗り継ぎを含めて出発地と目的地を結ぶ、利用可能な各交通手段を経路として順次たどり、経路探索条件に合致する案内経路（列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００５】
歩行者ナビゲーションシステムやカーナビゲーションシステムにおける経路探索のための道路ネットワークは、例えば、図８に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで道路ネットワークデータを構成している。すなわち、図８において、○印、◎印がノードを示し、◎印は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図８では図示を簡略化するため矢印の向きのリンクのみを図示している。
【０００６】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図８において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。図８ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクスラ法と呼ばれる周知の手法によって行われる。
【０００７】
このような道路ネットワークは、図８に模式的に示すようにリンクコストが固定であり、経路が定まればその累積リンクコストは一意に定まる静的なネットワークデータであってデータの量も道路ネットワークの量に比例したものになる。
【０００８】
これに対して、交通機関の運行ネットワークデータは、例えば、図９に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図９において、○印、◎印がノードを示し、◎印は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図９では図示を簡略化するため矢印の向きのリンクのみを図示している。
【０００９】
しかしながら、交通機関の運行ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通機関の運行ネットワークでは、図９に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数あり、各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００１０】
図９に例示する交通機関の運行ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になり、道路ネットワークのデータ量に比べて膨大なデータ量のネットワークデータとなる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００１１】
このような交通機関の運行ネットワークデータを用いてある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。例えば、図９において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択し、交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃを運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００１２】
前述のような経路探索は単純な道路ネットワークにおけるダイクストラ法による経路探索と異なり、交通手段（個々の列車や航空機などの経路）の組み合わせが膨大なものになり、先に述べたように経路探索時間が増大することになる。このような交通機関の運行ネットワークのデータを用いて経路探索を行う手法は、例えば、下記の非特許文献1（菊池，「動的ネットワーク表現に基づく列車・航空便の最適乗り継ぎ系列探索の手法とその実際への応用」，情報処理学会，平成９年４月，第３８巻，第４号，Ｐ．９１５−９２６）に開示された手法を用いることができる。ここで動的ネットワークとは、時間とともに関連するノードおよびリンクを逐次付加することにより形成されるネットワークをいう。
【００１３】
ところで、交通機関を用いた経路探索においては、経路として案内する探索条件に合致した交通手段（個々の航空機や列車、電車、バス）が特定されたとしても、当該特定された航空機や列車、電車、バスが指定席で運行される交通手段であって、全ての指定席が予約されており空席がない場合には、その航空機や列車、電車、バス（交通手段）は実質的には案内経路にはなり得ないことになる。この場合、指定席の空席の有無を探索条件に加えて経路探索を行う予約システムも以下に述べるようにサービスされている。本発明では、以下、空席の有無を探索の条件とする場合を座席条件ということとし、特に明示しない限り探索条件と記述した場合には座席条件を探索条件に含むものとする。
【００１４】
一般に、交通手段を用いて出発地から目的地まで移動する場合に、空席の有無を条件として利用可能な交通手段（航空機や列車）を探索するシステムとしては、航空機予約システム、列車予約システムなどが知られている。このような予約システムは、各交通機関が運営する予約センターに設置した予約情報データベースを有するコンピュータ装置にアクセスして空席のある交通手段を検索して予約する構成のシステムが一般的である。端末装置は各駅の予約窓口や旅行会社の予約窓口に設置されるが、最近では、ユーザが所有するコンピュータ装置や携帯電話からインターネット網を介して前記コンピュータ装置にアクセスして予約ができるようになってきている。
【００１５】
このような予約システムは、候補となる交通手段を複数探索して案内するナビゲーションシステムとは異なり、探索条件に合致する列車に空席がなく座席条件が満たされず予約不能な場合に、探索条件を変更して次の候補の予約状況を提示するようにオペレータが介在してインタラクティブに探索が行われるのが一般的である。また、予約システムは交通機関毎に個別、独立の形態で運用されるシステムが多く、ユーザが個別に必要な予約システムで予約を行うか、旅行代理店の窓口において、オペレータに各交通機関の予約システムを利用して探索、予約を依頼する必要があった。
【００１６】
このような不都合を解消する交通予約システムとしては、例えば、下記の特許文献１（特開平４−７０９６３号公報）に開示されたシステムが知られている。この交通予約システムは、あらゆる交通機関の情報を管理する交通情報管理手段と、この交通情報管理手段を用いて各種交通機関の様々な組み合わせによるスケジューリングを行い目的地までの交通手段を決定するスケジューリング手段と、スケジューリング手段で決定した交通手段の予約を実行する予約手段とから構成されたものである。
【００１７】
この交通予約システムにおいては、公報３頁、左下欄に「空席が無く予約不可能となれば（ステップ１０７否定）、再び最短経路スケジューラ１１によって次に最短経路となる交通機関が検索され、スケジューリングが行われる（ステップ１０３）」とあるように、ある探索条件で探索される交通機関（経路）に空席がなく予約不可能であったら、次の交通機関（経路）を再度探索する必要がある。
【００１８】
また、下記の特許文献２（特開２００３−４４５５３号公報）には、旅行プランの提供方法および旅行プラン提供装置が開示されている。この装置は、ネットワークを利用した場合でも、きめ細かい旅行案内サービスを行えるようにしたものである。すなわち、ブラウズ端末のユーザは、メニュー画面の条件設定ボタン群を使って旅行プラン策定に必要な諸条件を入力・選択し、検索ボタンを押すと、旅行プラン策定依頼が旅行プランサービスセンターに送信され、当該センターで策定された旅行プランが表示エリアに表示される。修正ボタン群やスライドボタン群を使って表示中のプランの変更を行うと、当該プランの変更依頼が前記センターに送信され、当該センターで策定し直された旅行プランが表示エリアに表示されるようにしたものである。
【００１９】
そしてこの装置においては、決定した運行便を利用するのに指定席の予約あるいはチケット手配が必要であれば、前記運行便（交通手段）の空席状況の確認指示を、指示送受信部を介して交通機関ダイヤ検索・予約依頼部に通知する。そして、交通機関ダイヤ検索・予約依頼部に、交通機関予約センターにアクセスさせて、前記運行便の空席状況を確認させる。その結果、空席がないことが確認されたならば、交通機関ダイヤ検索・予約依頼部に、前記路線区間を運行する運行便であって前記到着予定時刻よりも先に到着する運行便のうち、空席が確認できなかった運行便の次に、前記到着予定時刻に近い到着予定時刻の運行便を検索させ、この運行便を前記路線区間で搭乗する運行便に決定して、上記と同じ要領で空席状況を確認させる。この処理を、空席のある運行便が見つかるまで続けるように構成されている。
【００２０】
更に、下記の特許文献３（特開２００４−２０６４８２号公報）にはナビゲーションシステムおよび経路探索方法のプログラムが開示されている。このナビゲーションシステムは、経路探索区間を探索条件として設定する探索条件設定処理手段と、設定された探索条件に基づいて経路を探索する経路探索処理手段と、探索経路に少なくとも一つ以上の指定席路線が含まれるかどうかを判断する指定席路線判定処理手段と、探索経路に少なくとも一つ以上の指定席路線が含まれる場合に、指定席路線が含まれる探索経路を操作者に通知する通知処理手段とを有する。そして、探索経路に少なくとも一つ以上の指定席路線が含まれる場合に、指定席路線が含まれる探索経路が操作者に通知される。このナビゲーションシステムによれば探索経路上において公共の交通機関を利用するに当たり、座席を確保することが可能になる。
【００２１】
【非特許文献１】菊地，「動的ネットワーク表現に基づく列車・航空便の最適乗り継ぎ系列探索の手法とその実際への応用」，情報処理学会，平成９年４月，第３８巻，第４号，Ｐ．９１５−９２６
【特許文献１】特開平４−７０９６３号公報（第１図）
【特許文献２】特開２００３−４４５５３号公報（図１、段落［０１３３］）
【特許文献３】特開２００４−２０６４８２号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
航空機、列車、電車、バスなどの交通手段を用いて出発地から目的地までの経路を探索して案内する経路探索システム、特に、交通手段を用いて出発地から目的地までの経路を探索する際に、使用する交通手段における空席の有無に基づいて目的地までの経路（使用交通機関）を探索して案内するシステムにおいては、単に予約が必要な交通手段（探索条件に合致する個々の列車や航空機の指定席）に空席があるか否かによって案内経路を探索するだけではユーザにとって満足のゆく経路案内を行うことはできない。
【００２３】
例えば、探索条件に合致する出発地から目的地までの交通手段（列車、航空機など）において、全区間その交通手段に空席がない場合であっても、一定の区間を自由席を使用すれば、途中から指定席に空席ができる場合があり、また、指定席に空席がない場合であっても、出発地から目的地までの区間であれば空席がある場合もある。また、他の乗り継ぎ可能な路線を運行する交通手段、あるいは、同じ路線の別の交通手段（出発時間が探索条件より後の交通手段）には空席がある場合もある。このような予約状況は詳細な予約情報を収集することによってきめ細かく知ることができる。経路探索においては、例えば、探索条件に合致する交通手段に空席があるかないかだけでなく、可能な組み合わせを逐一探索して案内経路をユーザに提供できるようにシステムを構成する必要がある。
【００２４】
特に、交通手段が航空機の場合、特定の出発地を所定の日時に出発して特定の目的地に所定の日時までに到着したいという探索条件であると、交通手段の候補となる便が限られ、その便に空席がない場合には、出発日時や到着日時を変更せざるを得ず、ユーザが旅行スケジュールの変更を強いられるケースが頻繁に生じていた。ところが、航空機の場合、高速で長距離を移動するものであるから、あらゆる運行ネットワークデータを網羅した経路探索が可能であれば、思いもよらぬ経由地で便を乗り継ぐと探索条件に合致した経路が存在することもままある。
【００２５】
上記のように、探索条件に合致する経路に空席があるかないかだけでなく、可能な組み合わせを逐一探索して案内経路をユーザに提供できるようにシステムを構成し、あるいは、航空機のように高速で長距離を移動する交通機関を利用する場合にあらゆる運行ネットワークデータを網羅した経路探索を可能とするにはネットワークデータが膨大であり、経路の組み合わせも膨大であることから、効率的に目的とする経路を探索できるようにシステムを構成する必要がある。
【００２６】
しかしながら、上記特許文献１ないし特許文献３に開示されたシステムは何れも、先ず、通常の経路探索を行ってから、探索した交通手段（案内経路となる列車、航空機など）の指定席に空席がない場合には、探索をやり直す（特許文献１）か、あるいは、同一の路線で他の交通手段を探索する（特許文献２）か、または、経路探索結果から空席のない交通機関を除外する（特許文献３）ものであり、空席のない区間を代替する他の交通手段をきめ細かく探索することができず、ユーザの要求を満足させる経路探索を行うことができないという問題点があった。
また、経路探索に要する時間を短縮し効率的に経路探索を行うことができないという問題点も存在していた。
【００２７】
すなわち、特許文献１ないし特許文献３のようなシステムでは、最適に探索された交通手段（経路）の指定席が満席の場合に再度経路探索を行うことになり、経路探索を最初からやり直して順次２番目、３番目・・・・の経路を求めることになるので、空席が見つからないと経路探索の処理が加速度的に増えてしまう。特に、最短経路や運賃の条件で優先順位を付けて探索するのが一般的であるから、類似の交通手段（経路）が続けて出力される傾向にあり、その交通路線に含まれたある共通の交通手段（列車や飛行機）が満席であると、なかなか案内すべき交通手段（経路）が見つからないことがある。
また、乗り継ぎが必要なケースではその中の１便が満席なだけで案内経路にはならない。最初に経路探索を行う方法では、結局無駄な探索を行うことになり、経路探索サーバの負荷を大きくしてしまうことになる。また、従来の技術は指定席だけに注目しており、自由席があればそれを案内経路の一部とするというような詳細な設定ができなかった。
【００２８】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、各交通機関の予約情報を収集し、この予約情報とユーザが指定する経路探索条件とに基づいて経路探索に使用する運行ネットワークデータを動的に形成する。すなわち、経路探索の都度、予約情報と座席条件を含む経路探索の条件に合致しない交通手段（経路）に関連する運行データを除き、座席条件を含む経路探索の条件に合致する交通手段に関連する運行データのみを取得して経路探索用の運行ネットワークデータを動的に形成した上で経路探索を行うようにすることで、経路探索に要する時間を短縮可能であることを見いだし、本発明を完成するに至ったものである。
【００２９】
すなわち、本発明は前記の問題点を解消することを課題とし、交通手段を用いて出発地から目的地までの経路を探索する際に、使用する交通手段における空席の有無に基づいて効率よく目的地までの経路（使用交通手段）を探索して案内できるようにした空席経路探索システム、空席経路探索装置および端末装置を提供することを目的とするものである。
【課題を解決するための手段】
【００３０】
前記課題を解決するために、本願の請求項１にかかる発明は、入力された経路探索条件に基づいて出発地から目的地までの交通手段を用いた経路を探索して案内する空席経路探索システムにおいて、
前記空席経路探索システムは、各交通手段の運行データを記憶した運行データデータベースと、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件とし、該座席条件を含む経路探索条件を入力する条件入力手段と、予約情報収集手段で収集した座席情報と予約情報と前記座席条件を含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備え、
前記経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行うことを特徴とする。
【００３１】
また、本願の請求項２にかかる発明は、請求項１にかかる空席経路探索システムにおいて、前記条件入力手段は、交通手段がすべて予約可能でかつ空席であることを座席条件として入力する手段を有することを特徴とする。
【００３２】
また、本願の請求項３にかかる発明は、請求項１にかかる空席経路探索システムにおいて、前記条件入力手段は、交通手段が予約可能な場合は空席であることを座席条件として入力する手段を有することを特徴とする。
【００３３】
また、本願の請求項４にかかる発明は、請求項１にかかる空席経路探索システムにおいて、前記条件入力手段は、交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を入力する手段を有することを特徴とする。
【００３４】
また、本願の請求項５にかかる発明は、請求項１にかかる空席経路探索システムにおいて、前記条件入力手段は、交通手段が予約なしで利用できることを座席条件として入力する手段を有することを特徴とする。
【００３５】
また、本願の請求項６にかかる発明は、請求項１にかかる空席経路探索システムにおいて、前記条件入力手段は、交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を入力する手段を有することを特徴とする。
【００３６】
また、本願の請求項７にかかる発明は、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として入力された前記座席条件を含む経路探索条件に基づいて各交通手段の運行データを記憶した運行データデータベースから運行データを参照して出発地から目的地までの交通手段を用いた経路を探索して案内する空席経路探索装置であって、
前記空席経路探索装置は、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、予約情報収集手段で収集した座席情報と予約情報と前記座席条件を含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備え、
前記経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行うことを特徴とする。
【００３７】
また、本願の請求項８にかかる発明は、請求項７にかかる空席経路探索装置において、交通手段がすべて予約可能でかつ空席であることを座席条件として含む探索条件が入力されることを特徴とする。
【００３８】
また、本願の請求項９にかかる発明は、請求項７にかかる空席経路探索装置において、交通手段が予約可能な場合は空席であることを座席条件として含む探索条件が入力されることを特徴とする。
【００３９】
また、本願の請求項１０にかかる発明は、請求項７にかかる空席経路探索装置において、交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を含む探索条件が入力されることを特徴とする。
【００４０】
また、本願の請求項１１にかかる発明は、請求項７にかかる空席経路探索装置において、交通手段が予約なしで利用できることを座席条件として含む探索条件が入力されることを特徴とする。
【００４１】
また、本願の請求項１２にかかる発明は、請求項７にかかる空席経路探索装置において、交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を含む探索条件が入力されることを特徴とする。
【００４２】
また、本願の請求項１３にかかる発明は、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、予約情報収集手段で収集した座席情報と予約情報と経路探索条件に基づいて前記探索用運行データデータベースを参照して経路となる交通手段を探索する経路探索手段と、を備え、
前記経路探索手段は、経路探索に先立ち、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として含む経路探索条件に合致する座席情報と予約情報を持つ交通手段を前記運行データデータベースから抽出して探索用運行データデータベースを形成して経路探索を行う空席経路探索装置に探索条件を送信する端末装置であって、
前記端末装置は、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件とし、該座席条件を含む経路探索条件を入力する入力手段を備えたことを特徴とする。
【００４３】
また、本願の請求項１４にかかる発明は、請求項１３にかかる端末装置において、前記条件入力手段は、交通手段がすべて予約可能でかつ空席であることを座席条件として入力する手段を有することを特徴とする。
【００４４】
また、本願の請求項１５にかかる発明は、請求項１３にかかる端末装置において、前記条件入力手段は、交通手段が予約可能な場合は空席であることを座席条件として入力する手段を有することを特徴とする。
【００４５】
また、本願の請求項１６にかかる発明は、請求項１３にかかる端末装置において、前記条件入力手段は、交通手段が予約不能な満席状態であっても当該交通手段に自由席がある場合は経路とする座席条件を入力する手段を有することを特徴とする。
【００４６】
また、本願の請求項１７にかかる発明は、請求項１３にかかる端末装置において、前記条件入力手段は、交通手段が予約なしで利用できることを座席条件として入力する手段を有することを特徴とする。
【００４７】
また、本願の請求項１８にかかる発明は、請求項１３にかかる端末装置において、前記条件入力手段は、交通手段が予約可能でかつ空席があっても当該交通手段に自由席がある場合には該自由席を経路とする座席条件を入力する手段を有することを特徴とする。
【発明の効果】
【００４８】
請求項１にかかる発明は、予約情報収集手段で収集した各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報と、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件を含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備えた空席経路探索システムである。そして、経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行う。従って、運行ネットワークのネットワークデータ全てを対象として経路探索する必要がなく、効率的に経路を探索することができるようになる。
【００４９】
請求項２ないし請求項６にかかる発明は、請求項１にかかる空席経路探索システムにおいて、条件入力手段は交通手段の座席の予約情報を加味した経路探索条件を入力するための種々の座席条件を入力する手段を有する。従って、ユーザは、条件入力手段を用いてきめ細かな座席条件を入力し、経路探索手段は入力条件に合致した経路（交通手段）を探索することができるようになる。
【００５０】
請求項７にかかる発明は、予約情報収集手段で収集した各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報と、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として含む経路探索条件に基づいて前記探索用運行データデータベースを参照して出発地から目的地までの交通手段を用いた経路となる交通手段を探索する経路探索手段と、経路探索の結果を出力する出力手段と、を備えた空席経路探索装置である。そして、経路探索手段は、経路探索に先立ち、前記運行データデータベースから経路探索条件として指定された前記座席条件に合致する座席情報と予約情報を持つ交通手段を抽出して探索用運行データデータベースを形成して経路探索を行う。従って、運行ネットワークのネットワークデータ全てを対象として経路探索する必要がなく、効率的に経路を探索することができるようになる。
【００５１】
請求項８ないし請求項１２にかかる発明は、請求項７にかかる空席経路探索装置において、条件入力手段は交通手段の座席の予約情報を加味した経路探索条件を入力するための種々の座席条件を入力する手段を有する。従って、ユーザは、条件入力手段を用いてきめ細かな座席条件を入力し、経路探索手段は入力条件に合致した経路（交通手段）を探索することができるようになる。
【００５２】
請求項１３にかかる発明は、探索用の運行データを記憶する探索用運行データデータベースと、前記各交通手段の指定席の有無および自由席の有無を含む座席情報と、指定席の予約情報を収集する予約情報収集手段と、予約情報収集手段で収集した座席情報と予約情報と経路探索条件に基づいて前記探索用運行データデータベースを参照して経路となる交通手段を探索する経路探索手段と、を備え、経路探索に先立ち、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件として含む経路探索条件に合致する座席情報と予約情報を持つ交通手段を前記運行データデータベースから抽出して探索用運行データデータベースを形成して経路探索を行う空席経路探索装置に探索条件を送信する端末装置であって、該端末装置は、探索すべき交通手段における指定席の有無および自由席の有無および指定席の空席の有無の組み合わせの何れか１つを座席条件とし、該座席条件を含む経路探索条件を入力する入力手段を備えたものである。従って、ユーザは座席条件を含む経路探索の条件を空席経路探索装置に送り、効率的に経路探索結果を得ることができるようになる。
【００５３】
請求項１４ないし請求項１８にかかる発明は、請求項１３にかかる端末装置において、条件入力手段は交通手段の座席の予約情報を加味した経路探索条件を入力するための種々の座席条件を入力する手段を有する。従って、ユーザは、条件入力手段を用いてきめ細かな座席条件を入力し、経路探索手段は入力条件に合致した経路（交通手段）を探索することができるようになる。
【発明を実施するための最良の形態】
【００５４】
以下、本発明の具体例を実施例および図面を用いて詳細に説明する。図１は、本発明の実施例１にかかる空席経路探索システムの構成を示すブロック図である。図２は、経路探索条件の１つである座席条件のパターンを説明するための模式図である。図３は、条件入力手段における入力画面の構成を示す画面構成図である。図４は、経路探索条件の１つである座席条件を説明するための模式図である。図５は、予約情報ＤＢにおけるデータ構造を説明するための模式図である。図６は、予約情報ＤＢに蓄積された予約情報を用いて座席条件に合致した交通手段を抽出する処理を説明するための模式図である。図７は、本発明の実施例２にかかる空席経路探索システムの構成を示すブロック図である。
【実施例１】
【００５５】
本発明の実施例１にかかる空席経路探索システム１０は、インターネットなどのネットワーク１１、１２を介して通信する端末装置２０と空席経路探索装置３０と各種の交通機関６０〜６Ｎが運行する交通手段の運行データを蓄積した運行データＤＢ（データベース）５２および予約情報ＤＢ（データベース）５１とから構成される。
【００５６】
端末装置２０は、制御手段２１、条件入力手段２２、出力手段２３、通信手段２４などから構成されている。制御手段２１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。条件入力手段２２は、数字やアルファベットキーやその他の機能キー、選択キーなどからなる入力手段であり、出力手段２３である表示手段に表示されるメニュー画面から所望のメニューを選択し、あるいは、数字やアルファベットキーを操作して経路探索の条件を入力するものである。通信手段２４は、ネットワーク１１を介して空席経路探索装置３０と通信するためのインターフェースである。
【００５７】
経路探索の条件は、出発地、目的地、出発日時、到着日時などの一般的な経路探索の条件の他、本実施例においては、経路となる交通手段（個々の列車や航空機）における指定席の有無とその空席の状況のバリエーションを経路探索の条件として入力できるように構成されている。以下これを「座席条件」と称する。この座席条件の詳細については後述する。
【００５８】
一方、空席経路探索装置３０は、制御手段３１、経路案内手段３２、表示手段３３、通信手段３４、予約情報収集手段３５、経路探索手段３６、探索用運行データＤＢ３７から構成されている。制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。表示手段３３は空席経路探索装置３０のモニタ表示手段であり、通信手段３４は、ネットワーク１１、１２を介して端末装置２０や予約情報ＤＢ５１、運行データＤＢ５２と通信するためのインターフェースである。経路案内手段３２は、経路探索手段３６が探索した案内経路手段（個々の列車や航空機などの交通手段）を端末装置２０に配信するためのデータに編集するためのものである。
【００５９】
なお、予約情報ＤＢ５１は各交通機関６０〜６Ｎが運行する各々の交通手段（列車や航空機）の毎に予約情報、すなわち指定席が予約で満席であるか空席があるかという情報を随時更新して蓄積しており、予約情報ＤＢ５１を有するコンピュータ装置（図示せず）から旅行会社の予約センターや各交通機関の予約窓口端末あるいは本実施例にかかる空席経路探索装置３０やエンドユーザである個人などが保有するＰＣ、携帯電話などにインターネットを経由して予約情報を配信することができる。
【００６０】
同様に、運行データＤＢ５２は各交通機関６０〜６Ｎが運行する各々の交通手段（列車や航空機）の運行ネットワークデータを蓄積したデータベースであって、各交通機関６０〜６Ｎが運行する各々の交通手段の時刻表から作成された運行ネットワークデータを蓄積している。運行データＤＢ５２は、また、各交通機関６０〜６Ｎが運行する各々の交通手段（列車や航空機）の指定席の有無や自由席の有無、普通車やグリーン車、個室や寝台などのグレード、禁煙席、喫煙席の有無に関する座席データなどの静的なデータも蓄積されている。そして、運行データＤＢ５２を有するコンピュータ装置（図示せず）から旅行会社の予約センターや各交通機関の予約窓口端末あるいは本実施例にかかる空席経路探索装置３０に経路探索のための運行データ、座席データを提供することができる。
【００６１】
経路探索手段３６は、マルチモーダルな経路探索エンジンであって徒歩と交通機関を併用した経路探索機能を有するものであって、このような経路探索エンジンは例えば特開２０００−２５８１８４号公報（米国特許第６３４９２６１）に開示されている。端末装置２０から入力された座席条件を含む経路探索条件に基づいて予約情報収集手段３５を介して予約情報ＤＢ５１を収集するとともに、運行データＤＢ５２から後述するように座席条件を含む経路探索条件に合致する運行データのみを抽出して探索用運行データＤＢ３７に探索用運行データ（運行ネットワーク）を動的に形成し、この探索用の運行データベースを用いて前述した座席条件を含む経路探索条件に合致する交通手段を探索する。
【００６２】
本実施例においては、単に探索した交通手段が満席であった場合にこれを除外して経路探索を行うのではなくて、「探索すべき交通手段に自由席があるか否か」、「指定席があるか否か」、「指定席がある場合にその予約情報（満席か空席があるか）」の３つの要素を座席条件として経路探索を可能とし、ユーザの細かな要望に応じて経路探索を行うことにしている。上記３条件を機械的に組み合わせた８通りの条件は、図２のようなパターンに分類され、以下の意味を持つ。すなわち、図２において、各欄の「０」は、「無し」を意味し、「１」は、「有り」を示す。
Ｐ０：自由席、指定席共に無く、運休日などの場合が該当する。
Ｐ１：指定席が無いのに空席がある、ということはないので経路探索の条件外である。
Ｐ２：全車指定席で予約満席。
Ｐ３：全車指定席で空席あり。
Ｐ４：全車自由席。
Ｐ５：指定席が無いのに空席がある、ということはないので経路探索の条件外である。
Ｐ６：指定席が予約満席。自由席がある。
Ｐ７：指定席に空席あり。自由席もある。
【００６３】
端末装置２０の条件入力手段２２はＰ１とＰ５の条件を除く６通りの座席条件を入力することができる。図３は、端末装置２０における条件入力手段２２を構成する条件入力画面７０の構成を示す画面構成図である。ユーザは端末装置２０から図３の入力画面を用いて経路探索の条件を入力する。例えば、出発地、経由地、目的地の入力ボックス７１〜７３への入力に際して、住所、郵便（郵便番号）、電話（電話番号）、駅・空港、スポットの各入力カテゴリのチェックボックスをチェックして該当する入力ボックス７１〜７３に入力する。入力カテゴリがチェックされた際に各入力ボックス７１〜７３にプルダウンメニューを用意しておき、予め用意した出発地や経由地、目的地の一覧選択画面を表示して所望の場所を選択入力するように構成することもできる。出発日時、到着日時の入力も同様であり、出発または到着の入力カテゴリのチェックボックスをチェックして入力ボックス７４に数字入力する。
【００６４】
使用する移動手段や座席条件は図示されている該当チェックボックス７５をチェックして探索条件を入力することができる。例えば、自動車で移動する場合でかつ渋滞状況を加味した経路探索を指定する場合は該当するチェックボックスにチェックを入れ、経路探索ボタン７６をクリックすればよい。渋滞状況を加味しない場合には自動車のチェックボックスのみをチェックして経路探索ボタン７６をクリックする。本実施例にかかる交通機関を使用して移動する場合は乗物＋徒歩のチェックボタンをチェックし、グレードオプション、喫煙オプションの各チェックボックスから所望のオプションのチェックボックスをチェックする。そして、経路となる交通手段（航空機や列車）における空席予約を含む座席条件を経路探索条件とする場合には、「予約選択する」のチェックボックスをチェックし、その下に展開されている５つのチェックボックスの何れかをチェックして探索条件を指定して経路探索ボタン７６をクリックすることにより座席条件を含む経路探索条件を入力することができる。
【００６５】
端末装置２０において上記のようにして入力された経路探索条件は、通信手段２４、通信手段３４を介して経路探索装置３０で受信され、経路探索手段３６が経路探索を行う。条件入力手段２２により指定された移動手段のうち徒歩による経路探索、自動車による経路探索は、一般のナビゲーションシステムと同様であるので説明を省略し、本実施例においては、移動手段として交通機関を使用する区間の経路探索について以下に説明する。
【００６６】
図３において、「予約選択する」の下には、次の５つの座席条件が選択できるチェックボックスが配置されている。上から順に、「全て指定席を利用」、「指定席は全て利用」「指定席満席なら自由席」、「自由席のみ利用」、「混んでいない自由席（予測）」である。
「全て指定席を利用」は、指定席がありかつ空席があることが座席条件となり図２のＰ３、Ｐ７のパターンが該当する（完全予約と略称する）。
「指定席は全て利用」は、指定席がありかつ空席がある場合には指定席を利用し、自由席しかない場合は自由席を利用することを座席条件とするものであり、図２のＰ３、Ｐ４、Ｐ７のパターンが該当する（予約優先と略称する）。
「指定席満席なら自由席」は、指定席が満席なら自由席でも良いという現実的な座席条件である。図２のＰ３、Ｐ４、Ｐ６、Ｐ７のパターンが該当する（自由席許容と略称する）。この座席条件は最も許容範囲が広い座席条件であるが、図２のＰ２のパターン（交通手段の全席か指定席でかつ空席がない場合）は経路とすることができない。
【００６７】
「自由席のみ利用」は、一見、空席経路探索（予約）とは矛盾するように思えるが、予約無しでもとにかく目的地に行くことができるルートを見つけることができる座席条件である。目的地に行く必要があるかどうかが決まらなくて、予約ができないときに、万が一予約がとれなくても、いつまでに出発したら良いかといった判断に用いることができる。この座席条件は図２のＰ４、Ｐ６、Ｐ７のパターンが該当する（完全自由と略称する）。
「混んでいない自由席（予測）」は、指定席が満席となっていない列車の自由席および自由席のみの列車を座席条件とするものである。指定席が満席であると、自由席も混雑が予想されるため、逆に発想して指定席が満席でない列車の自由席は混雑していないと推測して座席条件とするものである。また、自由席のみの列車は予約状況から混雑度を予測することができないが、そもそも自由席のみの列車は、指定席が必要でない利用状況から自由席のみで運行される傾向があることから、自由席のみの列車も座席条件に含めることにしている。この座席条件は、図２のＰ４、Ｐ７が該当する（空席予測と略称する）。
【００６８】
これを整理して図示したものが図４である。図４のＲ〜Ｖの各欄が前述の説明で示した５つの座席条件を示している。欄Ｒは完全予約、欄Ｓは予約優先、欄Ｔは自由席許容、欄Ｕは完全自由、欄Ｖは空席予測の座席条件を示している。各欄にチェック（レ点）が入ったパターンに合致する交通手段が経路として探索すべきものである。例えば、完全予約の場合は、図２のパターンＰ３、Ｐ７を満足する予約状況の交通手段、すなわち、指定席が有りかつ空席がある交通手段であって座席条件以外の経路探索条件をも満足する交通手段を抽出すべきことを示している。
【００６９】
端末装置２０において、上記５つの座席条件のうちの１つを含む経路探索条件が入力されると、入力された経路探索条件は空席経路探索装置３０に送られる。空席経路探索装置３０が経路探索条件を受け取ると、経路探索手段３６は予約情報ＤＢ５１、運行データＤＢ５２を参照し、前記座席条件を含む経路探索条件を満足しない交通手段を除外して、すなわち、前記座席条件を含む経路探索条件を満足する交通手段の運行データを運行データＤＢ５２から抽出してその運行データに基づいた運行ネットワークデータを探索用運行データＤＢ３７に形成した上で経路探索を行う。
【００７０】
例えば、「全て指定席を利用」（完全予約と略称する）が座席条件として指定された場合は、経路とする交通手段が指定席を持ち、かつ指定席に空席がありこの空席を予約することが条件となり、経路探索手段３６はこれに合致しない交通手段を経路として抽出しないように予約情報ＤＢ５１、運行データＤＢ５２を参照し、指定席のない交通手段、指定席があっても空席のない交通手段を除外して経路探索条件に合致する交通手段のみを抽出して探索用運行データＤＢ３７に運行ネットワークデータを形成して経路探索を行う。従って、ローカル線など指定席の無いものは除外される。指定席がある交通機関までのルートは徒歩、あるいは自動車（タクシー）で充当する。または、出発地、目的地を空港とした場合の航空路線では、空席があれば経路として選択される座席条件である。
【００７１】
以上の説明を要約すると、経路探索手段３６による経路探索は以下のように行われる。すなわち、出発地や目的地が駅や空港などのターミナルでなく任意の地点である場合には、一般の歩行者ナビゲーションシステムと同様にして、出発地から交通機関に乗車できるいくつかの出発候補の駅、目的地近傍のいくつかの目的候補の駅が探索され、出発地から各候補駅までの最短の経路、目的候補の駅から目的地までの最短の経路がそれぞれの案内経路として探索される。そして、経路探索手段３６は予約情報ＤＢ５１、運行データＤＢ５２を参照して経路探索条件に合致する交通手段の運行データを抽出し、抽出した運行データに基づいて探索用運行データＤＢ３７に各出発候補駅から目的候補駅までの動的な運行ネットワークデータを形成して複数の候補経路（候補となる交通手段）を探索する。
【００７２】
動的な運行ネットワークデータを形成する段階で、経路探索の対象となる交通手段の運行データ（一般的には運行ダイヤと称することもある）が先ず運行データＤＢ５２から抽出される。本実施例ではこの抽出段階において、座席条件を含む経路探索条件に合致する交通手段のみを抽出する。例えば、前述した「完全予約」の座席条件である場合、図２、図４のパターンＰ３、Ｐ７の交通手段のみを抽出する。運行データＤＢ５２には各交通手段の自由席、指定席の有無などの情報しか蓄積されていないので、空席の有無は予約情報ＤＢ５１から取得する。この探索用運行データＤＢへの運行ネットワークデータの形成およびこれを用いた経路探索には前述した非特許文献１の手法を用いる。
【００７３】
次に、予約情報ＤＢ５１について具体的に説明する。予約情報ＤＢ５１は先に述べたように、各交通機関６０〜６Ｎが運行する各交通手段（列車、航空機など）の予約状況を常に更新している。予約情報ＤＢ５１のデータ構造は列車を例にとると、図５に示すような構造であり、先ず、列車のＩＤがあり、このＩＤに続いて当日（Ｔｏｄａｙ）から予約可能な期間全ての期間の予約状況データを逐次更新して蓄積する。予約状況データは、各列車毎に座席の種別に分けて「種別  Ａ−ＮＳ」、「種別  Ａ−Ｓ」、「種別  Ｇ−ＮＳ」、「種別  Ｇ−Ｓ」の４組の予約状況データが記憶される。「種別  Ａ−ＮＳ」は普通車指定席の禁煙席、「種別  Ａ−Ｓ」は普通車指定席の喫煙席、「種別  Ｇ−ＮＳ」はグリーン車指定席の禁煙席、「種別  Ｇ−Ｓ」はグリーン車指定席の喫煙席の予約状況データを記憶する。
【００７４】
各座席の種別「種別  Ａ−ＮＳ」、「種別  Ａ−Ｓ」、「種別  Ｇ−ＮＳ」、「種別  Ｇ−Ｓ」の予約状況データＢ１〜Ｂ３２までの３２ビットに記憶される。ビットＢ１は始発駅における予約の有無を記憶し、ビットＢ２〜Ｂ３２まで順次各停車駅における予約の有無を記憶する。予約状況は各ビットに「１」「０」で記憶される。「１」は満席で空席がない状態を、「０」は満席でなく空席がある状態を示している。
【００７５】
すなわち、１つの座席の種別の予約状況データは、上記のように３２ビットのデータで構成されており、最初のビット（ＬＳＢ）が始発駅における予約状況、すなわち、満席か否かを表している。満席が「１」である。次のビットには次の停車駅での予約状態が蓄積されている。データ長が３２ビットであるので、始発駅を含めて３２駅分の予約状態が蓄積できる。日本ではまず十分な長さである。もし停車駅がもっと多い場合にはデータ長を６４ビット、１２８ビットなど適宜の長さで構成すればよい。停車駅が少ない場合には、不要な上位ビットは「０」を蓄積しておけばよい。航空機の場合には経由地がそれほど多くないので１６ビットあるいは８ビットのデータ長であっても十分である。
【００７６】
このようなデータ構造で予約情報ＤＢ５１に蓄積された予約情報を用いて座席条件に合致した交通手段を抽出する場合の処理を図６に示す模式図を用いて説明する。経路探索条件である乗車日の該当する列車の予約状況データ（Ａ）に対して、乗車区間データ（Ｂ）を作成し両方のデータのアンドをとる。この時、経路探索条件の座席条件が「種別  Ａ−Ｓ」の普通車指定席の喫煙席であれば、予約状況データ（Ａ）は該当する種別の予約状況データ（図５参照）が選択される。
【００７７】
乗車区間データ（Ｂ）における乗車区間とは、乗車駅から下車駅の１つ手前（下車駅からで先は満席であってもかまわない）に相当する区間に「１」を記録したデータであり、経路探索条件（乗車駅と下車駅）に基づいて作成される。このデータとアンドをとった結果のデータ（Ｃ）が「０」になれば、乗車区間において満席でないことになる。もしも結果が「０」でなければ、どこかのビットに「１」が記録されており、乗車区間に満席の区間が存在することを意味する。
【００７８】
運行データＤＢ５２および予約情報ＤＢ５１を参照して経路探索手段３６は以上のような処理を行って座席条件を含む経路探索条件に合致する交通手段（個々の列車、航空機など）のみを抽出して探索用運行データＤＢ３７に探索用の運行ネットワークデータを動的に形成して乗り継ぎを含めた経路探索を行うため、運行ネットワーク全体を対象とした経路探索を行う場合に比較して、短時間で効率的に目的の経路を探索することができるようになる。
【００７９】
予約情報ＤＢ５１は、リアルタイムに各交通機関６０〜６Ｎの予約状況を反映することが望ましいが、予約はチケットの売り出し日、乗車当日とその前２日間程度の期間に変動することが多いので、その期間に該当する予約状況を特に短い間隔で収集してデータベースに反映することが好ましい。また、運行データＤＢ５２および予約情報ＤＢ５１は、空席経路探索装置３０と同じサーバあるいは隣接したサーバに配置する構成としてもよい。
【実施例２】
【００８０】
図７は、本発明の実施例２にかかる空席経路探索システムの構成を示すブロック図である。図７において図１の実施例１と同一の構成要素は同一の参照符号を付している。実施例１と異なる点は、実施例１における端末装置２０と空席経路探索装置３０が一体のコンポーネントである空席経路探索装置８０で構成されている点である。実施例２における空席経路探索装置８０は、制御手段８１、条件入力手段８９、表示手段８３、通信手段８４、予約情報収集手段８５、経路探索手段８６、探索用運行データＤＢ８７から構成されている。制御部８１、表示手段８３、通信手段８４、予約情報収集手段８５、経路探索手段８６、探索用運行データＤＢ８７は実施例１における制御手段３１、表示手段３３、通信手段３４、予約情報収集手段３５、経路探索手段３６、探索用運行データＤＢ３７とそれぞれ同一の機能である。また、実施例２における条件入力手段８９は実施例１における端末装置２０の条件入力手段２２と同一の機能である。
【００８１】
また、実施例２においても実施例１の場合と同様に、運行データＤＢ５２および予約情報ＤＢ５１は、空席経路探索装置８０と同じサーバあるいは隣接したサーバに配置する構成としてもよい。
【産業上の利用可能性】
【００８２】
このシステムは、端末をインターネット経由で接続した個人のパソコンや、通信回線で結ばれた携帯電話として、ユーザが自ら経路探索を行っても良いし、また旅行代理店の端末として顧客の希望を聞いてオペレータが処理を行うものとしても良い。
いずれの場合も、従来のように経路探索→空席確認→詳細条件の確認といった手動のステップを踏まずに、希望の経路を見つけることができるようになる。
特に携帯電話を端末にして実施した場合は、課金手段も確立しているので、探索結果から即座に予約に移行することも可能である。携帯電話の限られた表示画面でも、無駄な経路を表示することなく、所望の経路が最初から表示されるので、最適な探索システムとなる。
【００８３】
交通機関の立場では、このシステムに対応して空席情報を提供することによって、より予約客を獲得しやすくなると共に、今まで指定席が満席のために自由席に流れていた乗客を、迂回ルートの指定席に誘導することができて単価アップも期待できる。
【図面の簡単な説明】
【００８４】
【図１】本発明の実施例１にかかる空席経路探索システムの構成を示すブロック図である。
【図２】経路探索条件の１つである座席条件のパターンを説明するための模式図である。
【図３】条件入力手段における入力画面の構成を示す画面構成図である。
【図４】経路探索条件の１つである座席条件を説明するための模式図である。
【図５】予約情報ＤＢにおけるデータ構造を説明するための模式図である。
【図６】予約情報ＤＢに蓄積された予約情報を用いて座席条件に合致した交通手段を抽出する処理を説明するための模式図である。
【図７】本発明の実施例２にかかる空席経路探索システムの構成を示すブロック図である。
【図８】一般的な経路探索のための道路ネットワークを説明するための模式図である。
【図９】交通機関を使用した経路探索のための道路ネットワークを説明するための模式図である。
【符号の説明】
【００８５】
１０・・・空席経路探索システム
１１、１２・・・ネットワーク
２０・・・端末装置
２１・・・制御手段
２２・・・条件入力手段
２３・・・出力手段（表示手段）
２４・・・通信手段
３０・・・空席経路探索装置
３１・・・制御手段
３２・・・経路案内手段
３３・・・表示手段
３４・・・通信手段
３５・・・予約情報収集手段
３６・・・経路探索手段
３７・・・探索用運行データＤＢ（データベース）
５１・・・予約情報ＤＢ（データベース）
５２・・・運行データＤＢ（データベース）
６０〜６Ｎ・・・交通機関１〜Ｎ
【図１】
0004056076.tif 000002
【図２】
0004056076.tif 000003
【図３】
0004056076.tif 000004
【図４】
0004056076.tif 000005
【図５】
0004056076.tif 000006
【図６】
0004056076.tif 000007
【図７】
0004056076.tif 000008
【図８】
0004056076.tif 000009
【図９】
0004056076.tif 000010