【手続補正書】
【提出日】平成25年11月11日(2013.11.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
或る出発地点から或る目的地点へのジャーニーの公共的通行ルートを決定するために、コンピュータで実施される方法であって、前記公共的通行ルートには公共交通車両を持つ少なくとも１つの公共交通システムを使用し、前記方法はコンピュータにより実行され、且つ、
前記少なくとも１つの公共交通システムにおける複数の乗換パターンを第１のデータベース内に記憶するステップと、該記憶された乗換パターンの各々は、前記少なくとも１つの公共交通システムに関連する一対の通行駅間のルートを記述し、かつ、前記一対の通行駅間にある通行駅において公共交通車両を少なくとも１回乗り換えることを含み、
複数の公共通行駅を記述する情報であって各公共通行駅毎の場所を含む該情報を第２のデータベース内に記憶するステップと、
出発地点から目的地点への公共的通行ルートのリクエストをクライアント装置から受信するステップと、該公共的通行ルートは、少なくとも１つの公共交通システムを使用する前記出発地点から前記目的地点への道順を含み、
前記出発地点の或る半径距離内にある前記少なくとも１つの公共交通システムの通行駅を前記第２のデータベースを使用して決定し、それにより前記出発地点の前記半径距離内の通行駅を含む起点駅リストを生成するステップと、
前記目的地点の前記半径距離内にある前記少なくとも１つの公共交通システムの通行駅を前記第２のデータベースを使用して決定し、それにより前記目的地点の前記半径距離内の通行駅を含む目的駅リストを生成するステップと、
前記起点駅リスト中の１つの起点駅と前記目的駅リスト中の１つの目的駅とを含む通行駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための該賢明な組み合わせの１ペアにおける前記起点駅及び前記目的駅の間の中間通行駅での前記少なくとも１つの公共交通システムの公共交通車両の乗換を示す１つの記憶された乗換パターンを、前記複数の乗換パターンを記憶した前記第１のデータベースから検索するステップと、
前記検索された乗換パターン毎に、或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定するステップと、
前記少なくとも１つの最適な公共的通行ルートを記述する情報を前記クライアント装置に送信するステップと
を備えることを特徴とする方法。
【請求項２】
前記出発地点は前記クライアント装置のユーザの現在の地理的位置であることを特徴とする請求項１に記載の方法。
【請求項３】
前記目的地点は前記クライアント装置のユーザが望む行き先の地理的位置であることを特徴とする請求項１に記載の方法。
【請求項４】
前記出発地点又は前記目的地点は或る通行駅の地理的地位であることを特徴とする請求項１に記載の方法。
【請求項５】
前記リクエストは、更に、前記出発地点からの出発時刻又は前記目的地点への到達時刻を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記１つの記憶された乗換パターンを前記複数の乗換パターンを記憶した前記第１のデータベースから検索する前記ステップは、
その乗換パターンサフィックスに関連付けられた１つの駅に先行する連続する一対の駅を示す１以上の乗換パターンサフィックスを検索するステップと、
前記１つの記憶された乗換パターンを生成するために、前記１以上の乗換パターンサフィックスを連結するステップ
を備えることを特徴とする請求項１に記載の方法。
【請求項７】
前記少なくとも１つの公共交通システムの前記通行駅の賢明な組み合わせのペア毎の前記１つの記憶された乗換パターンを、該１つの記憶された乗換パターンにより表された順番で、弧によって連結されたノードのシークエンスとして表すクエリグラフを生成するステップを更に備えることを特徴とする請求項１に記載の方法。
【請求項８】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、
前記クエリグラフ内の各ノードを、そのノードに関連付けられた或る通行駅で乗車することになる前記少なくとも１つの公共交通システムの公共交通車両を表す駅ノード、及び、そのノードに関連付けられた或る通行駅に公共交通車両が到着している間乗車したままとする前記少なくとも１つの公共交通システムの公共交通車両を表す乗車ノードとして表すことにより、前記クエリグラフを拡張するステップと、
前記起点駅から各後続駅への１以上の直通接続ルートを決定するステップであって、直通接続ルートは、前記起点駅から１つの後続駅へのルートと、前記１つの記憶された乗換パターンに関連付けられた前記起点駅と前記後続駅の間の中間通行駅での停車スケジュールとを表すものと、
前記１以上の直通接続ルート毎に、前記拡張されたクエリグラフ内のノードの連なりを、前記直通接続ルートを表す弧により連結するステップであり、前記ノードの連なりにおける各ノードはそれぞれ、前記１つの記憶された乗換パターンに関連付けられた駅を表すものと
を備えることを特徴とする請求項７に記載の方法。
【請求項９】
前記起点駅から少なくとも１つの後続駅への１以上の直通接続を決定するステップと、
前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続を決定するステップと、
前記起点駅から前記目的駅へのルートを形成するために、前記起点駅から少なくとも１つの後続駅への１以上の直通接続を、前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続に連結するステップと、
前記拡張されたクエリグラフ内のノードの連なりを、前記形成されたルートを表す弧により連結するステップと
を備えることを特徴とする請求項８に記載の方法。
【請求項１０】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、
多次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適な公共的通行ルートを決定するために、前記拡張されたクエリグラフにパレート‐ダイクストラ計算を適用することにより、前記少なくとも１つの最適な公共的通行ルートを計算するステップであって、前記多次元のコストは駅ペアの間の時間長とペナルティを含むもの、を備えることを特徴とする請求項８に記載の方法。
【請求項１１】
前記ペナルティは、金銭的コスト、前記起点駅から前記目的駅に到達するために必要な公共交通車両の乗換数、及び、徒歩コストの少なくとも一部に基づくものであることを特徴とする請求項１０に記載の方法。
【請求項１２】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、
１次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適な公共的通行ルートを決定するために、前記拡張されたクエリグラフにダイクストラ計算を適用することにより、前記少なくとも１つの最適な公共的通行ルートを計算するステップであって、前記１次元のコストは、前記起点駅から前記目的駅へのトリップを完遂するために要する総時間、前記起点駅から前記目的駅に到達するために要する乗換数、又は、金銭的コストのいずれか１つを含むものである
ことを特徴とする請求項８に記載の方法。
【請求項１３】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、前記少なくとも１つの最適な公共的通行ルートを決定するために目標指向検索を適用することを含み、前記目標指向検索はＡ＊探索アルゴリズムであることを特徴とする請求項８に記載の方法。
【請求項１４】
或る出発地点から或る目的地点へのジャーニーの公共的通行ルートを決定するためにコンピュータにより実行可能なコードからなるコンピュータプログラムであって、前記公共的通行ルートには公共交通車両を持つ少なくとも１つの公共交通システムを使用し、コンピュータプロセッサに、
前記少なくとも１つの公共交通システムにおける複数の乗換パターンを第１のデータベース内に記憶するステップと、該記憶された乗換パターンの各々は、前記少なくとも１つの公共交通システムに関連する一対の通行駅間のルートを記述し、かつ、前記一対の通行駅間にある通行駅において公共交通車両を少なくとも１回乗り換えることを含み、
複数の公共通行駅を記述する情報であって各公共通行駅毎の場所を含む該情報を第２のデータベース内に記憶するステップと、
出発地点から目的地点への公共的通行ルートのリクエストをクライアント装置から受信するステップと、該公共的通行ルートは、少なくとも１つの公共交通システムを使用する前記出発地点から前記目的地点への道順を含み、
前記出発地点の或る半径距離内にある前記少なくとも１つの公共交通システムの通行駅を前記第２のデータベースを使用して決定し、それにより前記出発地点の前記半径距離内の通行駅を含む起点駅リストを生成するステップと、
前記目的地点の前記半径距離内にある前記少なくとも１つの公共交通システムの通行駅を決定し、それにより前記目的地点の前記半径距離内の通行駅を含む目的駅リストを生成するステップと、
前記起点駅リスト中の１つの起点駅と前記目的駅リスト中の１つの目的駅とを含む通行駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための該賢明な組み合わせの１ペアにおける前記起点駅及び前記目的駅の間の中間通行駅での前記少なくとも１つの公共交通システムの公共交通車両の乗換を示す１つの記憶された乗換パターンを、前記複数の乗換パターンを記憶した前記第１のデータベースから検索するステップと、
前記検索された乗換パターン毎に、或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定するステップと、
前記少なくとも１つの最適な公共的通行ルートを記述する情報を前記クライアント装置に送信するステップと
を実行させることを特徴とするプログラム。
【請求項１５】
前記１つの記憶された乗換パターンを前記複数の乗換パターンを記憶した前記第１のデータベースから検索する前記ステップは、前記コンピュータプロセッサに、
その乗換パターンサフィックスに関連付けられた１つの駅に先行する連続する一対の駅を示す１以上の乗換パターンサフィックスを検索するステップと、
前記１つの記憶された乗換パターンを生成するために、前記１以上の乗換パターンサフィックスを連結するステップ
を実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１６】
前記コンピュータプロセッサに、更に、前記少なくとも１つの公共交通システムの前記通行駅の賢明な組み合わせのペア毎の前記１つの記憶された乗換パターンを、該１つの記憶された乗換パターンにより表された順番で、弧によって連結されたノードのシークエンスとして表すクエリグラフを生成するステップを実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１７】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、前記コンピュータプロセッサに、
前記クエリグラフ内の各ノードを、そのノードに関連付けられた或る通行駅で乗車することになる前記少なくとも１つの公共交通システムの公共交通車両を表す駅ノード、及び、そのノードに関連付けられた或る通行駅に公共交通車両が到着している間乗車したままとする前記少なくとも１つの公共交通システムの公共交通車両を表す乗車ノードとして表すことにより、前記クエリグラフを拡張するステップと、
前記起点駅から各後続駅への１以上の直通接続ルートを決定するステップであって、直通接続ルートは、前記起点駅から１つの後続駅へのルートと、前記１つの記憶された乗換パターンに関連付けられた前記起点駅と前記後続駅の間の中間通行駅での停車スケジュールとを表すものと、
前記１以上の直通接続ルート毎に、前記拡張されたクエリグラフ内のノードの連なりを、前記直通接続ルートを表す弧により連結するステップであり、前記ノードの連なりにおける各ノードはそれぞれ、前記１つの記憶された乗換パターンに関連付けられた駅を表すものと
を実行させることを特徴とする請求項１６に記載のプログラム。
【請求項１８】
前記コンピュータプロセッサに、
前記起点駅から少なくとも１つの後続駅への１以上の直通接続を決定するステップと、
前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続を決定するステップと、
前記起点駅から前記目的駅へのルートを形成するために、前記起点駅から少なくとも１つの後続駅への１以上の直通接続を、前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続に連結するステップと、
前記拡張されたクエリグラフ内のノードの連なりを、前記形成されたルートを表す弧により連結するステップと
を実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１９】
或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定する前記ステップは、前記コンピュータプロセッサに、
多次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適な公共的通行ルートを決定するために、前記拡張されたクエリグラフにパレート‐ダイクストラ計算を適用することにより、前記少なくとも１つの最適な公共的通行ルートを計算するステップであって、前記多次元のコストは駅ペアの間の時間長とペナルティを含むもの、を実行させることを特徴とする請求項１４に記載のプログラム。
【請求項２０】
或る出発地点から或る目的地点へのジャーニーの公共的通行ルートを決定するためのコンピュータシステムであって、前記公共的通行ルートには公共交通車両を持つ少なくとも１つの公共交通システムを使用し、前記システムは、
コンピュータプロセッサと、
前記コンピュータプロセッサに実行されるよう構成されたコンピュータ実行可能なコードを記憶するコンピュータ読み取り可能な記憶媒体とを備え、
前記コードが実行されるときに、
前記少なくとも１つの公共交通システムにおける複数の乗換パターンを第１のデータベース内に記憶することと、ここで、該記憶された乗換パターンの各々は、前記少なくとも１つの公共交通システムに関連する一対の通行駅間のルートを記述し、かつ、前記一対の通行駅間にある通行駅において公共交通車両を少なくとも１回乗り換えることを含み、
複数の公共通行駅を記述する情報であって各公共通行駅毎の場所を含む該情報を第２のデータベース内に記憶することと、
出発地点から目的地点への公共的通行ルートのリクエストをクライアント装置から受信することと、ここで、該公共的通行ルートは、少なくとも１つの公共交通システムを使用する前記出発地点から前記目的地点への道順を含み、
前記出発地点の或る半径距離内にある前記少なくとも１つの公共交通システム通行駅を前記第２のデータベースを使用して決定し、それにより前記出発地点の前記半径距離内の通行駅を含む起点駅リストを生成することと、
前記目的地点の前記半径距離内にある前記少なくとも１つの公共交通システム通行駅を前記第２のデータベースを使用して決定し、それにより前記目的地点の前記半径距離内の通行駅を含む目的駅リストを生成することと、
前記起点駅リスト中の１つの起点駅と前記目的駅リスト中の１つの目的駅とを含む通行駅の賢明な組み合わせのペア毎に、前記起点駅から前記目的駅へ移動するための該賢明な組み合わせの１ペアにおける前記起点駅及び前記目的駅の間の中間通行駅での前記少なくとも１つの公共交通システムの公共交通車両の乗換を示す１つの記憶された乗換パターンを、前記複数の乗換パターンを記憶した前記第１のデータベースから検索することと、
前記検索された乗換パターン毎に、或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定することと、
前記少なくとも１つの最適な公共的通行ルートを示す情報を前記クライアント装置に伝送することと、
前記少なくとも１つの最適な公共的通行ルートを記述する情報を前記クライアント装置に送信すること、
を実行するように構成されたシステム。
【請求項２１】
前記出発地点は前記クライアント装置のユーザの現在の地理的位置であることを特徴とする請求項２０に記載のシステム。
【請求項２２】
前記目的地点は前記クライアント装置のユーザが望む行き先の地理的位置であることを特徴とする請求項２０に記載のシステム。
【請求項２３】
前記出発地点又は前記目的地点は或る通行駅の地理的地位であることを特徴とする請求項２０に記載のシステム。
【請求項２４】
前記リクエストは、更に、前記出発地点からの出発時刻又は前記目的地点への到達時刻を含むことを特徴とする請求項２０に記載のシステム。
【請求項２５】
前記１つの記憶された乗換パターンを前記複数の乗換パターンを記憶した前記第１のデータベースから検索することは、
その乗換パターンサフィックスに関連付けられた１つの駅に先行する連続する一対の駅を示す１以上の乗換パターンサフィックスを検索することと、
前記１つの記憶された乗換パターンを生成するために、前記１以上の乗換パターンサフィックスを連結すること
からなることを特徴とする請求項２０に記載のシステム。
【請求項２６】
前記コードが実行されるときに、
前記少なくとも１つの公共交通システムの前記通行駅の賢明な組み合わせのペア毎の前記１つの記憶された乗換パターンを、該１つの記憶された乗換パターンにより表された順番で、弧によって連結されたノードのシークエンスとして表すクエリグラフを生成すること、
を更に実行するように構成された請求項２０に記載のシステム。
【請求項２７】
前記或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定することは、
前記クエリグラフ内の各ノードを、そのノードに関連付けられた或る通行駅で乗車することになる前記少なくとも１つの公共交通システムの公共交通車両を表す駅ノード、及び、そのノードに関連付けられた或る通行駅に公共交通車両が到着している間乗車したままとする前記少なくとも１つの公共交通システムの公共交通車両を表す乗車ノードとして表すことにより、前記クエリグラフを拡張することと、
前記起点駅から各後続駅への１以上の直通接続ルートを決定することと、ここで、直通接続ルートは、前記起点駅から１つの後続駅へのルートと、前記１つの記憶された乗換パターンに関連付けられた前記起点駅と前記後続駅の間の中間通行駅での停車スケジュールとを表し、
前記１以上の直通接続ルート毎に、前記拡張されたクエリグラフ内のノードの連なりを、前記直通接続ルートを表す弧により連結すること、
からなり、ここで、前記ノードの連なりにおける各ノードはそれぞれ、前記１つの記憶された乗換パターンに関連付けられた駅を表すものである、請求項２６に記載のシステム。
【請求項２８】
前記コードが実行されるときに、
前記起点駅から少なくとも１つの後続駅への１以上の直通接続を決定することと、
前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続を決定することと、
前記起点駅から前記目的駅へのルートを形成するために、前記起点駅から少なくとも１つの後続駅への１以上の直通接続を、前記少なくとも１つの後続駅から前記目的駅への１以上の直通接続に連結することと、
前記拡張されたクエリグラフ内のノードの連なりを、前記形成されたルートを表す弧により連結すること、
を更に実行するように構成された請求項２７に記載のシステム。
【請求項２９】
前記或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定することは、
多次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適な公共的通行ルートを決定するために、前記拡張されたクエリグラフにパレート‐ダイクストラ計算を適用することにより、前記少なくとも１つの最適な公共的通行ルートを計算することからなり、前記多次元のコストは駅ペアの間の時間長とペナルティを含む、
ことを特徴とする請求項２７に記載のシステム。
【請求項３０】
前記ペナルティは、金銭的コスト、前記起点駅から前記目的駅に到達するために必要な公共交通車両の乗換数、及び、徒歩コストの少なくとも一部に基づくものであることを特徴とする請求項２９に記載のシステム。
【請求項３１】
前記或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定することは、
１次元のコストに基づいて前記起点駅から前記目的駅への前記少なくとも１つの最適な公共的通行ルートを決定するために、前記拡張されたクエリグラフにダイクストラ計算を適用することにより、前記少なくとも１つの最適な公共的通行ルートを計算することからなり、前記１次元のコストは、前記起点駅から前記目的駅へのトリップを完遂するために要する総時間、前記起点駅から前記目的駅に到達するために要する乗換数、又は、金銭的コストのいずれか１つを含む、
ことを特徴とする請求項２７に記載のシステム。
【請求項３２】
前記或る特定時刻での前記乗換パターンの具体例である前記起点駅から前記目的駅への少なくとも１つの最適な公共的通行ルートを決定することは、前記少なくとも１つの最適な公共的通行ルートを決定するために目標指向検索を適用することを含み、前記目標指向検索はＡ＊探索アルゴリズムであることを特徴とする請求項２７に記載のシステム。