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