(57)【要約】本発明は、最良旅行料金を見出すために旅行料金問合せを処理する方法、装置およびシステムを提供する。本発明の１実施形態において、問合せサーバは、最良旅行料金ソリューションに到達する可能なソリューションを非明示的に列挙する技術に基づいたブランチングおよびバウンディングを使用する。【選択図】図７
2005505025.tif 000002
【特許請求の範囲】
【請求項１】
トリップに対する部分的旅行料金ソリューションのセットを決定し、
トリップに対する完成旅行料金ソリューションのセットを規定するためにこの部分的旅行料金ソリューションにトリップ情報を追加し、
トリップ情報が部分的旅行料金ソリューションに追加されたときに、最適でない部分的ソリューションである部分的旅行料金ソリューションを除去し、
前記完成旅行料金ソリューションのサブセットをそのトリップに対する最良の旅行料金として戻すステップを含んでいるトリップに対する１以上の最良の旅行料金を発見する方法。
【請求項２】
トリップ情報を追加するステップは、
旅行料金問合せをソリューションツリー中のルートノードに提供し、
前記ルートノードに対応した旅行料金コンポーネントを複数の第１のノードに割当て、
前記第１のノードに対応した１以上の輸送業者を複数の第２のノードに割当て、
前記第２のノードに対応した１以上のフライトを複数の第３のノードに割当て、
前記第３のノードに対応した１以上の価格付け可能なユニットを複数の第４のノードに割当て、
前記第４のノードに対応した１以上の旅行料金を複数のリーフノードに割当てるステップを含んでいる請求項１記載の方法。
【請求項３】
前記完成旅行料金ソリューションのサブセットは、予め定められた数の最低費用の旅行料金ソリューションである請求項１記載の方法。
【請求項４】
前記完成旅行料金ソリューションのサブセットは、前記完成旅行料金ソリューションの使い果たされたセットである請求項１記載の方法。
【請求項５】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは回帰的な方式で行われる請求項１記載の方法。
【請求項６】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは反復的な方式で行われる請求項１記載の方法。
【請求項７】
前記部分的旅行料金ソリューションは、しきい値費用に基づいて除去される請求項１記載の方法。
【請求項８】
前記部分的旅行料金ソリューションは、改良された低いほうのバウンドに基づいて除去される請求項１記載の方法。
【請求項９】
前記部分的旅行料金ソリューションは、優先度待行列中に記憶されている請求項１記載の方法。
【請求項１０】
前記完成旅行料金ソリューションは、優先度待行列から検索される請求項１記載の方法。
【請求項１１】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは、ブランチおよびバウンド最良旅行料金サーチルーチンの一部として行われる請求項１記載の方法。
【請求項１２】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは、到着地および出発地から逆方向および順方向の両方向において行われる請求項１記載の方法。
【請求項１３】
トリップに対する部分的旅行料金ソリューションのセットを決定し、
トリップに対する完成旅行料金ソリューションのセットを規定するために前記部分的旅行料金ソリューションにトリップ情報を追加し、
トリップ情報が部分的旅行料金ソリューションに追加されたときに、最適でない部分的ソリューションである部分的旅行料金ソリューションを除去し、
前記完成旅行料金ソリューションのサブセットをそのトリップに対する最良の旅行料金として戻すステップを含んでいるトリップに対する１以上の最良の旅行料金を発見するコンピュータ実行可能な命令を含むコンピュータ読出し可能な媒体。
【請求項１４】
トリップ情報を追加するステップは、
旅行料金問合せをソリューションツリー中のルートノードに提供し、
前記ルートノードに対応した旅行料金コンポーネントを複数の第１のノードに割当て、
前記第１のノードに対応した１以上の輸送業者を複数の第２のノードに割当て、
前記第２のノードに対応した１以上のフライトを複数の第３のノードに割当て、
前記第３のノードに対応した１以上の価格付け可能なユニットを複数の第４のノードに割当て、
前記第４のノードに対応した１以上の旅行料金を複数のリーフノードに割当てるステップを含んでいる請求項１３記載のコンピュータ読出し可能な媒体。
【請求項１５】
前記完成旅行料金ソリューションのサブセットは、予め定められた数の最低費用の旅行料金ソリューションである請求項１３記載のコンピュータ読出し可能な媒体。
【請求項１６】
前記完成旅行料金ソリューションのサブセットは、前記完成旅行料金ソリューションの使い果たされたセットである請求項１３記載のコンピュータ読出し可能な媒体。
【請求項１７】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは回帰的な方式で行われる請求項１３記載のコンピュータ読出し可能な媒体。
【請求項１８】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは反復的な方式で行われる請求項１３記載のコンピュータ読出し可能な媒体。
【請求項１９】
前記部分的旅行料金ソリューションは、しきい値費用に基づいて除去される請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２０】
前記部分的旅行料金ソリューションは、改良された低いほうのバウンドに基づいて除去される請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２１】
前記部分的旅行料金ソリューションは、優先度待行列中に記憶されている請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２２】
前記完成旅行料金ソリューションは、優先度待行列から検索される請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２３】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは、ブランチおよびバウンド最良旅行料金サーチルーチンの一部として行われる請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２４】
トリップ情報を追加し、部分的旅行料金ソリューションを除去するステップは、到着地および出発地から逆方向および順方向の両方向において行われる請求項１３記載のコンピュータ読出し可能な媒体。
【請求項２５】
トリップに対する部分的旅行料金ソリューションのセットを決定し、
トリップに対する完成旅行料金ソリューションのセットを規定するためにこの部分的旅行料金ソリューションにトリップ情報を追加し、
トリップ情報が部分的旅行料金ソリューションに追加されたときに、最適でない部分的ソリューションである部分的旅行料金ソリューションを除去し、
前記完成旅行料金ソリューションのサブセットをそのトリップに対する最良の旅行料金として戻すように動作する、トリップに対する１以上の最良の旅行料金を発見するための装置。
【請求項２６】
トリップ情報の追加は、
旅行料金問合せをソリューションツリー中のルートノードに提供し、
前記ルートノードに対応した旅行料金コンポーネントを複数の第１のノードに割当て、
前記第１のノードに対応した１以上の輸送業者を複数の第２のノードに割当て、
前記第２のノードに対応した１以上のフライトを複数の第３のノードに割当て、
前記第３のノードに対応した１以上の価格付け可能なユニットを複数の第４のノードに割当て、
前記第４のノードに対応した１以上の旅行料金を複数のリーフノードに割当てる請求項２５記載の装置。
【請求項２７】
前記完成旅行料金ソリューションのサブセットは、予め定められた数の最低費用の旅行料金ソリューションである請求項２５記載の装置。
【請求項２８】
前記完成旅行料金ソリューションのサブセットは、前記完成旅行料金ソリューションの使い果たされたセットである請求項２５記載の装置。
【請求項２９】
トリップ情報の追加および部分的旅行料金ソリューションの除去は回帰的な方式で行われる請求項２５記載の装置。
【請求項３０】
トリップ情報の追加および部分的旅行料金ソリューションの除去は反復的な方式で行われる請求項２５記載の装置。
【請求項３１】
前記部分的旅行料金ソリューションは、しきい値費用に基づいて除去される請求項２５記載の装置。
【請求項３２】
前記部分的旅行料金ソリューションは、改良された低いほうのバウンドに基づいて除去される請求項２５記載の装置。
【請求項３３】
前記部分的旅行料金ソリューションは、優先度待行列中に記憶されている請求項２５記載の装置。
【請求項３４】
前記完成旅行料金ソリューションは、優先度待行列から検索される請求項２５記載の装置。
【請求項３５】
トリップ情報の追加および部分的旅行料金ソリューションの除去は、ブランチおよびバウンド最良旅行料金サーチルーチンの一部として行われる請求項２５記載の装置。
【請求項３６】
トリップ情報の追加および部分的旅行料金ソリューションの除去は、到着地および出発地から逆方向および順方向の両方向において行われる請求項２５記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、オンライン交通手段予約処理に関し、とくに、オンライン予約または旅行料金問合せに対して最良の旅行料金を自動的に決定するシステム、装置および方法に関する。
【背景技術】
【０００２】
通信ネットワークはコンピュータ通信分野においてよく知られている。定義上、ネットワークとは、通信装置またはリンクによって接続されているコンピュータおよび関連した装置のグループである。ネットワーク通信はケーブルによるように永続的な性質であることが可能であり、あるいは電話または無線リンクによって行われた接続のように一時的な性質であることが可能である。ネットワークのサイズは、少数のコンピュータまたはワークステーションおよび関連した装置から構成されているローカルエリアネットワーク（ＬＡＮ）と、地理的に分散されているコンピュータおよびＬＡＮを相互接続する広域ネットワーク（“ＷＡＮ”）と、遠隔地コンピュータを一時的な通信リンクによって相互接続する遠隔アクセスサービス（“ＲＡＳ”）とでは異なっている可能性がある。したがって、インターネットワークとは、種々のネットワークからのデータ転送および変換を容易にするゲートウェイまたはルータによる類似したおよび類似していない多くのコンピュータネットワークの結合である。インターネットワークという用語に対するよく知られている略語が“インターネット”である。現在理解されているように、大文字で書かれた用語“インターネット”は、伝送制御プロトコル／インターネットプロトコル（“ＴＣＰ／ＩＰ”）またはユニフォームデータグラムパケット／インターネットプロトコル（“ＵＤＰ／ＩＰ”）のような上位のプロトコルと共にインターネットプロトコル（“ＩＰ”）を使用して互いに通信するネットワークおよびルータの集りを示している。
【０００３】
最近、インターネットは、位置されたコンピュータを世界中にリンクするその能力によって爆発的な成長を遂げた。インターネットの成長に伴って、ワールドワイドウェブ（“ＷＷＷ”または“ウェブ”）もまた成長した。ウェブとは、“ウェブサイト”でインターネットにより電子的に取り扱われるハイパーテキストマークアップ言語（“ＨＴＭＬ”）で相互接続されたまたは“ハイパーテキスト”文書の巨大な集まりである。ウェブは、ほとんどその簡単さおよび情報を種々のフォーマットで伝送するその能力のために、あっという間に一般的な情報伝播方法になった。情報をウェブによって利用できるようにするために、ユーザは典型的に、インターネットサービスプロバイダ（“ＩＳＰ”）によりウェブサイト上に配置された“ウェブページ”セットを構成する。ウェブサイトはインターネットに接続されたサーバ上に位置し、このサーバはハイパーテキスト文書、別名“ウェブページ”を記憶する大容量記憶装置を備え、それは、これらの記憶されているハイパーテキスト文書に対するリクエストに対処する管理用ソフトウェアを実行する。ハイパーテキスト文書は公称的にいくつかのハイパーリンク、すなわち、この文書を、インターネット上のどこかにあるウェブサイトにおそらく記憶されている別のハイパーテキスト文書にリンクするテキストの強調された部分を含んでいる。各ハイパーリンクは、インターネットに接続されたサーバ上におけるリンクされた文書の正確な位置を提供し、その文書を記述するユニフォームリソースロケータ（“ＵＲＬ”）と関連付けられている。したがって、ハイパーテキスト文書が任意のウェブサーバから検索された場合は常にその文書がウェブから検索されたと考えられる。
【０００４】
ウェブブラウザによって、ユーザはハイパーテキスト文書をウェブから検索する、すなわち、“ウェブをサーフする”ことが可能になる。ＮＥＴＳＣＡＰＥ  ＮＡＶＩＧＡＴＯＲ（商標名）インターネットエクスプローラまたはｐｈｏｎｅ．ｃｏｍのＵＰ．ｌｉｎｋ  ｍｉｃｒｏｂｒｏｗｓｅｒのようなウェブブラウザは、グラフィックユーザインターフェース（“ＧＵＩ”）をウェブに提供するようにウェブクライアント、すなわち、ユーザのコンピュータ、広域携帯電話または別のクライアント装置によって実行されるソフトウェアプログラムである。ユーザからウェブブラウザによってリクエストされたとき、ウェブクライアントは所望のハイパーテキストに対するＵＲＬおよびハイパーテキスト転送プロトコル（“ＨＴＴＰ”）として知られているプロトコルを使用して適当なウェブサーバからその文書にアクセスし、検索する。ＨＴＴＰはＴＣＰ／ＩＰより上位のプロトコルであり、とくに、ウェブの要求用に設計されている。それは、サーバとクライアントとの間でハイパーテキスト文書を転送するためにＴＣＰ／ＩＰに加えて使用される。
【０００５】
ウェブが出現したとき、インターネット上に記憶されている情報は一般に性格的に静的であったし、ウェブサイト上に与えられている情報の変更が所望された場合には、そのＨＴＭＬコードを書き直すことによりウェブサイトを慎重に構成することが必要であった。しかしながら、現在のウェブの発達段階では、多くのウェブサイトは、ユーザのクライアント装置上のウェブブラウザとウェブサイトとの間におけるユーザの対話に応じて変化する動的なコンテンツを提供している。これらの動的なハイパーテキスト文書は技術的によく知られており、ウェブサーバにより処理される共通ゲートウェイインターフェース（“ＣＧＩ”）スクリプトまたはウェブブラウザにより処理されるＪＡＶＡスクリプトのようなローカルスクリプトを使用することによる等の無数の異なったやり方で生成されてもよい。
【０００６】
本発明は、航空機チケット、列車チケット、バスチケット、フェリーチケット等を含む交通手段のチケットをインターネットによって顧客に提供する旅行サービスのようなネットワークベースおよびインターネットベースの旅行サービスに関する。このようなサービスにより、インターネットによって旅行サービスに接続されているコンピュータを使用する顧客は、航空機チケット、列車チケット、バスチケット、フェリーチケット等、またはその組合せを含んでいる動的に変化するインベントリからアイテムを購入することができる。典型的に、旅行サービスは中央コンピュータ予約システム（“ＣＲＳ”）と協力する。ＣＲＳは問合せに応答して、最新の旅行料金（トリップに対する価格またはトリップを含むルートの組合せ）、スケジュール（トリップまたはフライトの到着および出発の日付および時間）、ルール（どの事情の下でどの旅行料金が有効であるか）および利用可能性（特定の料金において設備を提供するための特定のトリップまたはフライトに対する収容能力）を提供するために旅行代理店の輸送手段提供者またはサービスと通信しているシステム／サービスである。この情報は、輸送業者により典型的に第３パーティを介してＣＲＳに提供される。しかしながら、旅行サービスはまた、割引契約または誘因計画のような、輸送業者と旅行サービスとの間の特定の関係を反映したローカルデータベースのような別のデータベースと協力することができる。したがって、インターネットベースのサービスは多くの輸送業者のインベントリおよび価格のソースにアクセスすることができる。
【０００７】
旅行サービスのビジネス環境では、同一または類似した最終商品を種々の価格で顧客に提供する多くの方法が存在している。輸送業者によって駆り立てられた好みのために、類似のインベントリを異なるように価格付けすることは費用的に有効かもしれない。たとえば、航空機の予約の場合、消費者が地点Ａから地点Ｂまで旅行することのできる方法の数は、航空輸送業者、異なる旅行経路、中心の位置およびその他の詳細の数を考慮したときに非常に多くなる。この理由のために、地点Ａから地点Ｂまでの特定の一般部分の価格は時間、航空輸送業者等にわたって大きく異なる可能性がある。さらに、複合価格バリエーションは、たとえば、出発時間近くに予約されるチケットに対する需要の増加等を反映することのできる価格感度である。さらに、個々の輸送業者と交渉された誘因および割引計画は、旅行サービスによって提供される価格にさらに影響を与えることができる。また、ある定まったクラスのインベントリは関連した高いまたは低い需要、あるいは高いまたは低い売上高を連想させているかもしれない。
【０００８】
さらに、消費者を駆り立てる多くの好み択が存在し、それらもまた価格付けに影響を及ぼすことができる。何人かの消費者はインベントリの所定のアイテムの個々の特徴を異なって評価するであろう。たとえば、航空機チケットの場合、消費者は、そのフライトがいつ行われる（ある場所から次の場所に飛行する）かを評価しないかもしれないし、一方別の消費者は特定の輸送業者をその他全てよりも高く評価するかもしれない。これらの好みは、消費者がその好みを指定したときに提供されるフライトのファクタに入れられることができる。これらおよびその他の理由により、同一または類似した最終商品の価値に影響を及ぼすことができる多くのファクタが存在する。
【０００９】
さらに、通常のインターネットベースの旅行サービスにおいて消費者は、所望の提供者インベントリに関するきわめて固有の情報を入力し、インターネットベースの旅行サービスは、その固有の問合せに一致するインベントリについてＣＲＳに問合せる。ＣＲＳは問合せに対する一致を見出すためにそのデータベースのサーチを行って、消費者により見られるように結果セットをインターネットベースの旅行サービスに戻す。
【００１０】
１つの限界は、同じ最終商品を消費者に提供する方法が多数存在するために生じる。たとえば、種々の提供者、旅行経路およびその他の詳細が考慮されたとき、地点Ａから地点Ｂまで旅行する方法の数は計算不可能なほど多い。したがって、経済的な理由のために、ＣＲＳは典型的に、問合せを満足させる情報を求めてそのデータベースをサーチするのに固定された量の時間を費やす。その結果、単に可能なインベントリ要素の順列または組合せの全てをサーチすることができないために、ＣＲＳは、それが問合せに応答して結果を旅行サービスに戻したときにその固有の問合せに対するごく限られた通常は最適でない結果を戻す。結果的に、問合せに一致するいくつかのインベントリは、ＣＲＳにより戻された結果のセット中に現れない。したがって、ＣＲＳサーチ時間および計算パワーを実質的にまたは法外に増加させずにもっと徹底した問合せを行うことのできるサービスを提供することが有益である。このような利点を提供することによって消費者の経験が豊富になり、その結果さらに多くの消費者を引きつけると同時にレピータ消費者を確保する。
【００１１】
さらに、出発地と到着地との間の少数の接続地点セットを通過する経路について料金を検査するだけで料金をサーチすることが技術的によく知られている。その後、出発地と接続地点と到着地との間の経路の全ての可能な組合せを明示的に列挙することによって最も低いコストの（時間および価格の両方において）経路を見出すことができる。しかしながら、このアプローチは依然コスト高であると共に不正確でフレキシブルではない。輸送業者によって新しい経路がスケジュール化され、あるいは除去されたとき、全ての予め定められた接続地点セットを再計算する必要がある。限られた数の接続地点しか提供されない場合でさえ、限られたセットの経路／料金の組合せでもそれを明示的に列挙することは依然として計算上法外なものとなる可能性がある。さらに、限られた数の接続地点しか検査されない場合でも、最適なソリューションが予め定められた接続地点に含まれていない接続地点を通過するものならば、その最適なソリューションを落とす可能性が高い。
【００１２】
当業者に知られている別の発見的アプローチは、出発地から到着地までの最良料金の決定が不正確なものとなるが、しかしながら、発見的アルゴリズムはそれらの性質上不正確であるため、これらの発見的アプローチは依然として厳密に一致したソリューションではない。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、計算的に法外ではない方法で最良料金を見出すための、厳密に一致する、可能な経路／料金組合せが最良の料金ではないことが分かっていない限りそれらを無視しないアプローチが必要とされている。
【課題を解決するための手段】
【００１４】
本発明は、可能な旅行ソリューションを非明示的に列挙して最良の料金ソリューションに至るブランチングおよびバウンディングベースの技術により問合せサーバを使用することによって計算的に法外ではない方法で最良の料金を見出す問題をこれを使用することによって解決する。
トリップに対する最良の料金を見出す１つの例示的な方法において、トリップに対する部分的料金ソリューションのセットを決定し、完成料金ソリューションのセットを規定するためにこの部分的料金ソリューションにトリップ情報を追加し、トリップ情報が部分的料金ソリューションに追加されたときに、最適でない部分的ソリューションである部分的料金ソリューションを除去することによって料金が見出される。その後、前記完成料金ソリューションのサブセット（予め定められた数または網羅的ないずれかのセット）をそのトリップに対する最良料金として戻す。
【００１５】
１実施形態においてトリップトリップ情報を追加するステップは、料金問合せをソリューションツリー中のルートノードに提供し、前記ルートノードに対応した料金コンポーネントを第１のレベルのノードに割当て、その料金コンポーネントに対する輸送業者を第２のレベルのノードに割当て、第３のレベルのノードに対応した輸送業者の当てられた料金コンポーネントにフライトを割当て、そのフライトを第４のレベルのノードに対応した価格付け可能なユニットにグループ化し、リーフノードにおいて料金を価格付け可能なユニットに割当てるステップを含んでいてもよい。
【００１６】
トリップ情報を追加し、部分的料金ソリューションを除去するステップは、可能なソリューションが少なくとも非明示的に検査される限り、回帰的または反復的な方式で行われる。実際に、トリップ情報を追加し、部分的料金ソリューションを除去するステップは、最良の料金のサーチをさらに分解するように到着地および出発地から逆方向および順方向の両方向において行われることができる。
【００１７】
本発明の別の例示的な実施形態において、部分的料金ソリューションは任意しきい値費用に基づいて除去され、一方別の部分的料金ソリューションは改良された低いほうのバウンドに基づいて除去される。
本発明のさらに別の例示的な実施形態において、部分的料金ソリューションおよび完成料金ソリューションは、優先度待行列中に記憶されている。
【００１８】
本発明は以下の詳細な説明および添付図面を参照とすることによりさらによく理解されるため、本発明の上述した特徴および付随する多くの利点がさらに容易に認識されるであろう。
【発明を実施するための最良の形態】
【００１９】
上述したように、大文字で書かれた用語“インターネット”は、インターネットプロトコル（“ＩＰ”）を使用して互いに通信するネットワークおよびルータの集りを示している。図１（従来技術）にはインターネット100の代表的なセクションが示されており、この図１においては、複数のＬＡＮ120およびＷＡＮ130がルータ110によって相互接続されている。ルータ110は一般に、１つのＬＡＮまたはＷＡＮを別のものにインターフェースするために使用される特殊目的のコンピュータである。ＬＡＮ内の通信リンクは撚線対または同軸ケーブルであってよく、一方ネットワーク間の通信リンクは５６Ｋｂｐｓのアナログ電話線または１ＭｂｐｓのデジタルＴ−１ラインおよび、または４５ＭｂｐｓのＴ−３ラインを使用することができる。さらに、コンピュータおよび別の関連した電子装置がモデムおよび一時的な電話リンクによってＬＡＮ120またはＷＡＮ130のいずれにも遠隔的に接続されることができる。図１においては、このようなコンピュータおよび電子装置140は破線のラインによりＬＡＮ120の１つに接続されているものとして示されている。インターネットは非常に多くのこのような相互接続されたネットワーク、コンピュータおよびルータを含んでおり、図１にはインターネット100の代表的なセクションのごく一部しか示されていないことが認識されるであろう。
【００２０】
他方において、ウェブは、インターネット100中に接続されているサーバ上に位置された相互接続された電気的に記憶された情報または“コンテンツ”の巨大な集りである。現在、多くの企業がウェブを使用してインターネット100によりサービスおよび彼らのコンテンツへのアクセスを提供している。たとえば、いくつかの企業はインターネット100により旅行サービスを提供し、これによってその顧客は交通手段および宿泊先のオンライン予約を行うことが可能になる。本発明によると、交通手段のチケットをオンラインで予約または購入することを検討しているユーザにより行われた旅行料金問合せに応答して利用可能な最良の旅行料金を決定する最適化されたシステムおよび方法が提供される。ここでは、本発明を説明するために一例として航空輸送およびフライトが使用されているが、当業者は、本発明が同様に、鉄道、道路、船舶のような別の形態の交通手段あるいは予約または料金問合せを受けることのできる任意の他の形態の交通手段に適応されることを認識するであろう。さらに、この市場では非常に多くの可能な組合せから低価格の商品を選択することが重要であるため、本発明は、関連商品と旅行を結びつける、ホテル滞在日数またはレンタカーのような関連した商品と旅行を組合せた価格付け商品に適応されることができる。さらに、本発明は、小包の経路設定および配達において最少の費用による小包配達の効率を上げるために最良料金サーチの利点を使用することができるため、旅客不在の旅行にも同様に適応されることができる。
【００２１】
図２は、クライアント装置210のユーザにより行われた問合せに応答して最良の旅行料金を決定するシステム200の機能ブロック図を示している。システム200は一般に、ネットワーク（インターネット100のような）により相互接続された個々のコンピュータシステムを含む分散形計算方式環境において動作する。しかしながら、当業者は、システム200が単一の独立型コンピュータシステムとしても同様に機能することができることを認識するであろう。記載されている実施形態において、予備処理サーバ300、ファイルサーバ240および問合せサーバ400は、インターネット100のようなインターネットワークによって、あるいはおそらくイントラネットワークによって１以上のクライアント装置210、ウェブサーバ220および旅行サーバ230と相互接続されている。以下、予備処理サーバ300および問合せサーバ400をそれぞれ図３および４を参照として説明する。システム200はまたＣＲＳ250に対する１以上の接続を含んでおり、このＣＲＳ250は、上述したように交通サービスに対する最新料金、スケジュールおよび利用可能性情報を提供するシステム/サービスである。当業者は、例示的なシステム200においてこれより多い、または少ない装置が使用されてもよいことを認識するであろう。たとえば、ファイルサーバ240は、問合せサーバ400が情報をＣＲＳ250から直接受取る場合は、不要かもしれない。さらに別の例において、料金情報を局部的に予備処理するために問合せサーバ400またはファイルサーバ240が設けられている場合は、予備処理サーバ300は必要ないかもしれない。
【００２２】
図３は、予備処理サーバ300の重要なコンポーネントのいくつかを示している。当業者は、予備処理サーバ300が図３に示されている数よりもっと多くのコンポーネントを含むことができることを認識するであろう。しかしながら、本発明を実施する例示的な形態を開示するために、これらの一般に慣例的なコンポーネントを示す必要はない。図３に示されているように、予備処理サーバ300は、インターネット100に接続するネットワークインターフェース330を含んでいる。当業者は、ネットワークインターフェース330がこのような接続に必要な回路を含んでおり、それはまたＴＣＰ／ＩＰプロトコルまたはインターネットＩｎｔｅｒ−ＯＲＢプロトコル（“ＩＩＯＰ”）のような次世代プロトコルによる使用に対して構成されていることを認識するであろう。
【００２３】
予備処理サーバ300はまた、処理装置310、ディスプレイ340およびメモリ350を含んでおり、これらは全てネットワークインターフェース330と共にバス320によって相互接続されている。メモリ350は一般に、ランダムアクセスメモリ（“ＲＡＭ”）と、読出し専用メモリ（“ＲＯＭ”）と、およびディスクドライブのような永久的大容量記憶装置とを含んでいる。メモリ350は、旅行料金レコード最適化ルーチン500を使用して本発明にしたがって旅行料金レコードを予備処理するために必要なプログラムコードを記憶している。さらに、メモリ350はまた旅行料金インデックス360と呼ばれるオプションの一時的旅行料金レコード記憶装置と、およびオペレーティングシステム355とを記憶している。これらのソフトウェアコンポーネントは、フロッピーディスク、テープまたはＤＶＤ／ＣＤ−ＲＯＭのようなコンピュータ読出し可能な媒体に関連したドライブ機構（示されていない）を使用して、あるいはネットワークインターフェース330を介してコンピュータ読出し可能な媒体から予備処理サーバ300のメモリ350中にロードされてもよいことが認識されるであろう。
【００２４】
一般的に通常の汎用計算装置に適合する例示的な予備処理サーバ300を説明してきたが、当業者は、予備処理サーバ300がインターネット100または問合せサーバ400と通信することのできる非常に多くの装置の任意のものであってもよいことを認識するであろう。
【００２５】
図４は問合せサーバ400の重要なコンポーネントのいくつかを示している。当業者は、問合せサーバ400が図４に示されている数よりもっと多くのコンポーネントを含むことができることを認識するであろう。しかしながら、本発明を実施する例示的な形態を開示するために、これらの一般に慣例的なコンポーネントを示す必要はない。図４に示されているように、問合せサーバ400は、ネットワークインターフェース430によってインターネット100に接続されている。当業者は、ネットワークインターフェース430が問合せサーバ400をインターネット100に接続するために必要な回路を含んでおり、それはまたＴＣＰ／ＩＰプロトコルまたは、それが含まれている動作環境の特定のネットワーク構成および特定のタイプの結合媒体であるＩＩＯＰのような次世代プロトコルによる使用に対して構成されていることを認識するであろう。
【００２６】
問合せサーバ400はまた処理装置410、ディスプレイ440および大容量メモリ450を含んでおり、これらは全てネットワークインターフェース430と共にバス420によって相互接続されている。メモリ450は一般に、ＲＡＭと、ＲＯＭと、およびハードディスクドライブ、テープドライブ、オプションドライブ、フロッピーディスクドライブまたはその組合せのような１以上の永久的大容量記憶装置とを含んでいる。大容量メモリ450は、メッセージを受取って処理し、フォーマット化して送信すると共に本発明にしたがってその処理の結果を送信者に提供するために必要なプログラムコードおよびデータを記憶している。とくに、メモリ450は最少費用マトリックス（“ＭＣＭ”）465を記憶しており、このＭＣＭ465は旅行地点（出発地と到着地）との間の予め計算された最少費用旅行料金を容易にアクセス可能なマトリックスフォーマットで記憶するために使用され、その結果出発地および到着地が与えられた場合にそれらの間を旅行する最少費用を見出すことができる。さらに、メモリ450は、旅行料金、スケジュールおよびルールデータベース（“ＦＳＲ”）470と、優先度待行列475と、およびオペレーティングシステム455とを記憶している。ＦＳＲは、図５を参照として以下に説明するように予備処理されている最適化された旅行料金、スケジュールおよびルールレコードの集りである。旅行料金レコードは、種々のトリップの出発地、到着地、日付、時刻、および価格のような詳細なトリップ情報を提供するが、それらに限定されない。ルールレコードは、特定の料金がいつまで有効であるか、およびそれがどのように使用されてもよいかをとくに指定するためにその旅行料金に関連付けられることのできる種々のルール（たとえば、その旅行商品は１４日前までに購入されなければならない、その旅行商品はデンバー経由で旅行する場合は利用できない等）を提供する。スケジュールレコードはもっと一般的なレコードであり、輸送業者により提供されている定期的にスケジュール化されたトリップを指定している。
【００２７】
他方において、優先度待行列475はとくに、この優先度待行列475から取出された（待ち行列から出された：ｄｅｑｕｅｕｅ）次の情報部分が最低費用項目とになるように、可能な最良料金に関する情報を記憶するように構成されている。上述されたソフトウェアコンポーネントは、フロッピー、テープまたはＤＶＤ／ＣＤ−ＲＯＭドライブのようなコンピュータ読出し可能な媒体に関連したドライブ機構（示されていない）を使用して、あるいはネットワークインターフェース430を介してコンピュータ読出し可能な媒体から問合せサーバ400の大容量メモリ450中にロードされることができることが認識されるであろう。
【００２８】
一般的に通常の汎用計算装置に適合する例示的な問合せサーバ400を説明してきたが、当業者は、問合せサーバ400がインターネット100によって通信することのできる非常に多くの装置の任意のものであってもよいことを認識するであろう。
以下詳細に説明するように、問合せサーバ400は最適化された旅行料金、スケジュールおよびルールレコードを予備処理サーバ300から周期的に受取る。その後、問合せサーバ400は、交通手段予約またはチケット購入に対して行われた問合せに応答して利用可能な最良の旅行料金を決定するときにその最適化された料金、スケジュールおよびルールレコードを使用する。図５には、料金、スケジュールおよびルールレコードを最適化する予備処理ルーチン500が詳細に示されている。予備処理ルーチン500の論理はブロック501から始まり、ブロック505に進み、ここで概算の旅行料金、スケジュールおよびルールレコードがＣＲＳ250またはファイルサーバ240から受取られる。概算の旅行料金、スケジュールおよびルールレコードは一般に、共にテキストベースである旅行料金およびルールレコード用のAirline Tariff Publishing Company（“ＡＴＰＣＯ”）フォーマットならびにスケジュールレコード用のStandard Schedules Information Manual（“ＳＳＩＭ”）フォーマットとしてＣＲＳ250により送信される。レコードの処理をもっと効率的にすることによってこれらのフォーマットを強化することが有用である。たとえば、ブロック510において、レコードは個々に検査され、不要な情報またはフィールドがそのレコードから除去される。ＣＲＳ250はレコードを多くの異なったタイプのサーバに提供するので、たとえば、機内食データ、旅行料金価格のソース、または旅行料金の決定に必要のない他の情報等の、最良の旅行料金を決定するのに必要ないレコードの中の情報を提供する可能性がある。レコード中の必要のない情報が除去されると、ブロック515に示されているように、中間レコードが予備処理サーバ300内の旅行料金インデックス360中に記憶される。その後、ブロック520において、ルーチン500は、旅行料金インデックス360中に記憶されている任意の他の中間レコードに対するリンクへの参照のために除去された中間レコードを検査する。たとえば、１実施形態において、ＣＲＳ250から受取られた旅行料金レコードは、その旅行料金に適用されることのできる１以上のルールレコードの記述を有している。それは、各旅行料金レコードがその旅行料金レコードに適用されることのできるルールを含む記述されたルールをサーチしなくてもよい場合、後の処理中にさらに迅速で効率的になる。リンクされたレコードに対する明示的なリンク（リンクされたレコードの位置へのポインタ、参照またはある別の直接マッピング）を生成することにより、リンクされたレコードを後処理中にサーチする必要がなくなる。したがって、ブロック520はこれらの結合（リンク）を見つけ出して識別し、旅行料金インデックス360を更新することによってそれらが見出された場所を示す。ブロック510、515および520は、ＣＲＳ250から受取られた各レコードが処理され、決定ブロック525において最後のレコードに達したことが決定されるまで繰返される。このようにして、ＣＲＳ250から受取られた未処理の各旅行料金レコードは検査され、除去され、そのリンクと共に中間レコードとして旅行料金インデックス360中に記憶される。
【００２９】
上述のようにＣＲＳ250から受取られた概算の旅行料金レコードの全てが処理された後、ブロック530において最適化が続行し、このブロック530において中間レコードが旅行料金インデックス360から検索される。その後、ブロック535において、最初に１以上の別のレコードへのリンクを有するものとして識別された全てのレコードをリンクすることにより各中間レコードが個々に処理される。これらの新しくリンクされたレコードは、その後中間レコードとして記憶され、関連したリンクへの明示的なリンクを有するさらに最適化された旅行料金レコードを形成する。次にブロック540において、現在の中間レコードに対していくつかの値が予め計算される。たとえば、旅行料金レコードはそれらがリンクすることのできる全てのルールレコードのリストを追加する。これによって、旅行料金がリンクされることのできないレコードに関連したあるランタイムリンク処理が除去されると共に、旅行の方向当りのドル費用（すなわち、往復のトリップ旅行料金の場合における旅行料金レベルの半分）が予め計算されるため、片道および往復のトリップ旅行料金がさらに直接的に比較可能なものになる。ブロック540において空港コード（３つの頭文字すなわち“ＴＬＡ”）に対応している都市コードを予め計算することもまた有用である。その後、ブロック545おいて、将来もっと容易にレコードを処理するためにレコード中の値が記録される。たとえば、日付は、年、月および日フォーマット（ＹＹＤＤＭＭ）としてではなく、固定されたベースからの日数として表されるように記録される。これによって日付は、それらに関して計算が行われる前に最初に変換されなければならないストリングではなく、整数として容易に比較されることが可能となる。その後、ブロック550においてレコードは、旅行料金レコード、ルールレコードまたはスケジュールレコードのいずれかとして後の検索のために、最適化された旅行料金レコードとしてＦＳＲ470中に記憶される。このプロセスは、旅行料金インデックス360からの最後の中間レコードが処理されたことを決定ブロック555が決定するまで、ブロック535、540、545および550により繰返される。その後、ブロック560において、ＦＳＲ470中に記憶された最適化された旅行料金レコードは、任意の出発および到着地点間の最低の旅行料金について検査される。その後、これらの最低費用の旅行料金は、後に問合せサーバ400が最良料金を決定するときに使用されるようにＭＣＭ465中に記憶される。その後、プロセスはブロック599で終了する。
【００３０】
予備処理ルーチン500は、新しい旅行料金、ルールおよびスケジュールレコードが利用可能になるように、周期的に動作する。一般に、旅行料金、ルールおよびスケジュールレコードは予備処理サーバ300による容易なアクセスのためにファイルサーバ240によってＣＲＳ250から検索されることができる。予め定められたインターバルで、あるいは新しいレコードが利用可能であることを示すある表示をファイルサーバ240またはＣＲＳ250から受取った後に、予備処理サーバはファイルサーバ240またはＣＲＳ250からレコードを検索し、予備処理ルーチン500を実行する。
【００３１】
ＦＳＲ470が最適化されたレコードを含み、ＭＣＭ465が構築されると、問合せサーバ400により実施される最良料金ルーチン700（図６乃至１２）を使用して最良の旅行料金を見出すことが可能となる。最良の旅行料金を見出すことに関する問題は、このタイプの問題についての容易な比較が存在しないことである。所定の最良旅行料金を保証するために、旅行料金は他の全ての可能な旅行料金ソリューションと比較されなければならない。これを明示的に行うには、全ての可能な別のソリューションを全て列挙する必要があり、それは計算上膨大である。したがって、本発明は可能な旅行料金ソリューションを他の全ての可能なソリューションと非明示的に比較し、その結果、全ての可能な別のソリューションの部分的な列挙を行ない、それによってＮＰ時間の問題を除去する。
【００３２】
従来のオンラインフライト予約システムにおいては、図１４に示されているように最良の利用可能な旅行料金を決定するために可能なソリューションの明示的な列挙が使用される。全ての可能なソリューションは、ユーザの旅行料金問合せを表すルートノード1405を有するソリューションツリー1400で編成されている。しかしながら、この時点で別のノードはソリューションツリー1400に追加されていない。その後、あるトリップ情報（本発明において使用されるタイプのトリップ情報：ブレークポイント、輸送業者、フライトおよび旅行料金、あるいはフライトを記述した任意の他の情報のような）が追加された“部分的ソリューション”を表す後続するノードが生成されて、ソリューションツリー1400に追加され、一方残りのトリップ情報はまだ割当てられていない。旅行料金を決定するために必要とされる全てのトリップ情報が割当てられると、このソリューションは完全であるとみなされる。十分な情報が追加されて完成ソリューション（リーフノード）を形成するまで、ツリーの各“レベル”において１つタイプが増加されたトリップ情報が新しい特有の部分的ソリューションに追加されて中間ノードを生成する。たとえば、レベル１では、ブレークポイント（旅行料金のために使用されるトリップに沿った任意の停止地点）1410が割当てられ、これはまた旅行料金コンポーネントを２つのブレークポイント間の旅行セグメントと定義している。レベル２において、輸送業者1415がブレークポイント間の旅行料金コンポーネントに割当てられる。その後、レベル３において航行便1400が輸送業者を有する旅行料金コンポーネントに割当てられる。次に、レベル４ではこれらのフライトが価格付け可能なユニット1425に割当てられる。価格付け可能なユニットには、輸送業者により単一の価格が割当てられている１以上の旅行料金コンポーネントのグループが含まれてもよい。最後にレベル５において、旅行料金（税およびいくつかの手数料を含む）が価格付け可能なユニットに割当てられる。最後（レベル５）のノードにおいてのみ、ツリーのいわゆる“リーフ”が“完成”ソリューション1430を表し、これは全てのトリップ情報がそのソリューションに追加されたことを意味する。
【００３３】
３２個の可能なリーフノードだけを有する図１４に示されている小規模のソリューションツリー1400では、全てのソリューションを明示的に列挙することは計算上禁止的なものではない。しかしながら、考慮する必要のある無数のルール、追加旅行料金およびその他のファクタに言及せずに、空港が６００（国際空港が含まれる場合には１０，０００）を越え、任意の２つの空港間における２以上のフライトを有している可能性のある輸送業者が４１以上であり、かつ、フライトと価格付け可能なユニットとの組合せが２以上存在している現実的な例においては、明示的列挙技術が使用された場合、部分的ソリューションの数は急速に計算が膨大なものになる。
【００３４】
本発明が航空輸送状況のような例示的な状況において可能なソリューションの、明示的な列挙ではなく非明示的列挙を使用して最良の旅行料金をどのようにして見出すことができるかを理解するときに、可能なソリューションを記述し、分割するために使用されるトリップ情報を理解することが助けとなる。図１３のＡは、地点Ａにおける出発地1310から地点Ｂにおける到着地1330までの単一のトリップを表している。このフライトに対するブレークポイント（たとえば、出発地および到着地を含むそのルートに沿った任意の地点）は地点Ａ1310、Ｃ1320およびＢ1330にある。地点Ｄ1315は、それがまた空港である可能性があるために重要であるが、輸送業者、フライトまたは旅行料金を決定するためのブレークポイントとはみなされない。それは単なる立ち寄り地点である。図１３のＡのトリップは、出発地点ＡとブレークポイントＣとの間において地点Ｄに立ち寄る便名“ＭＡ＃１００”を有する第１のフライト1335、およびブレークポイントＣと到着地点Ｂとの間の便名“ＨＡ＃２００”を有する第２の直行便1340の２つの旅行料金から構成されている。本発明の目的に対しては、このトリップの“費用”は地点Ａ1310から地点Ｂ1330に至るための実際の時間をそれらの間の飛行に対する旅行料金の合計と組合せたものから構成されている。この組合せは、さらに重要である価格または合計旅行時間を提供するために加重されてもよい。当業者は、価格および旅行時間（おそらく、待合せ時間を含むか、あるいは含まない）を使用して費用を決定するために任意の数の加重またはランク付け方式が使用されてもよいことを認識するであろう。価格および旅行時間に加えて、あるいはその代りに別の情報が使用されることができる。たとえば、輸送業者の信頼性および、または評判も考慮されることができる。
【００３５】
トリップに対する旅行料金を決定するとき、その旅行料金が適応される価格付け可能なユニットのタイプを決定することが慣例である。ほとんどの価格付け可能なユニットは、片道トリップ、往復トリップまたオープンジョー(open jaw)の３つのタイプのカテゴリーの１つに入る。図１３のＣは、到着地を示す簡単な例を表している。13Jから13Kを通って13Lに至り、13Jに戻るトリップは、多くの可能な価格付け可能なユニットの組合せにグループ化されることができる。たとえば、その最も簡単な形態では、それは往復トリップの下りの行程で13Kに立ち寄る13Jから13Lへの往復トリップである。それはまた、各旅行料金コンポーネント1380、1385および1390が片道の価格付け可能なユニットである３つの片道フライトのグループであることもできる。別のグループ化は、トリップの下り行程の出発地および任意の後続する行程が必ずしも同じではない（しかし、同じであることは可能である）いわゆる“オープンジョー”便である。１つのこのような例において、旅行料金コンポーネント1380および1385は、オープンジョーの価格付け可能なユニットの一部であることができ、旅行料金コンポーネント1390は片道の価格付け可能なユニットとなる。片道のフライトは１以上の旅行料金コンポーネントを含むことができる。一般に、往復フライトおよびオープンジョーフライトは、片道フライトより価格が安いので、トリップの費用を最少にしようと試みる場合、フライトをこれらのタイプの価格付けユニットと組合せることは非常に有益である。図１３のＣに示されている簡単な例からでさえ、多くのブレークポイントおよび僅か３つのタイプの価格付けユニットによりソリューションツリー1400に追加される可能な順列は、ソリューションの明示的な列挙を急速に実行不可能にすることを認識することができる。
【００３６】
本発明は、ソリューションツリー1400のようなソリューションツリー中のあらゆるノードを明示的に列挙しない。むしろ、任意のノードにおいて、任意の子ノードが最適なソリューションを含むことができる可能性があるか否かが決定される。これが行われる１つの方法は、しきい値を使用することによる。部分的ソリューションのコストがしきい値より上であることがすでに決定されている場合、部分的ソリューションを有するそのノードおよびその子ノードの全てがソリューションツリー1500において考慮を延期（ｄｅｆｅｒ）される。そのノードは、しきい値が変化したなら、後の時点で再訪されるてもよいが、最初は考慮されない。このプロセスは、本発明のブランチおよびバウンド技術と組合せて使用されてもよい。
【００３７】
本発明によると、ブランチおよびバウンド技術は、問合せから導出された部分的ソリューションのシーケンスを解くことにより最良の旅行料金をサーチするために使用される。たとえば、新しい部分的ソリューションの第１のレベルは、トリップが通過しなければならないブレークポイントによってのみその部分的ソリューションが制約されるようにソリューションツリー1500のノードとして生成され、この結果、問題は簡単なものになり、もっと少ない計算によりもっと容易に解決されることができる。ブランチングはプログラムを２つのプログラムに分割し、バウンディングは各下位の問題に対する低いほうのバウンド（現在の最良の場合）を計算する。下位の問題に対するその低いほうのバウンドがしきい値費用より悪い場合、下位の問題（可能なソリューション）全体は、しきい値費用が増加するまで延期される（いつか増加するならば）。この明細書では、ブランチおよびバウンドプロセスは、ツリー中のあらゆる全ての各ノードが下位の問題（部分的ソリューション）を表すツリーとして説明される。最初に、ツリーは、このツリーの非ルートノード中の全ての変数がルートノード中の緩和された変数によって緩和されて置換されている緩和された問題を表す単一のルートノードにより開始される。ブランチおよびバウンドサーチの各段階で、１つのアクティブなノードが選択され、関連した緩和された問題が解かれる。ソリューションに応じて、以下の３つのアクションの１つがとられる：
・延期：緩和された問題が現在の最良の実行可能な目標値より悪いソリューションを有している場合、そのノードの処理を延期する。
・改良：ソリューションが、各ノードについてその費用が前の低いほうのバウンドより低くなるものである場合には、低いほうのバウンドを更新する。
・ブランチング：緩和されたソリューションが完成したものでない場合およびそれの評価された値が現在の最良の実行可能なソリューションより良い場合、あるノードに関してブランチを行う。
【００３８】
しきい値費用が変化するまで延期されたノードより下の部分的ソリューションが無視されることのできる理由は、実行可能なソリューションの数がすでに決定され、予備処理サーバ300によって旅行料金、スケジュールおよびルールレコードの最適化期間中にＭＣＭ465中に位置されているからである。ＭＣＭ465中の実行可能なソリューションが有効であり、そのノード中の部分的ソリューションより費用的に低い（たとえば、価格、時間等の、使用されている任意の全ての費用基準に基づいて）場合、ＭＣＭ465はそのノードからのどのソリューションより良好なソリューションを有しているので、そのノードまたはそれの子ノードを考慮しても無駄である。したがって、これは、最適なソリューションに近づくヒューリスティックアプローチではない。むしろ、それは最適化ソリューションを見出す正確な最適化手順である。換言すると、上記の説明において、目的は、最少費用を有する１組のソリューションを見出すことである。本発明によると、実行可能なソリューションは、冒頭で述べたように予備処理段階中にＭＣＭ465を生成することにより最初に見出される。ＭＣＭ465中の情報により、前の最良のソリューションより良好なソリューションになることのできないツリー上のノードは安全に延期される。
【００３９】
したがって、次に、中間ノードにおける部分的ソリューションが完成したとき、その費用の値に関して“低いほうのバウンド”を計算する方法が必要とされる。この低いほうのバウンドの発見は繰返し（おそらく反復または再帰的）プロセスであり、このプロセスでは、可能なソリューションが比較されて、最良の旅行料金を提供する可能性があるものとして受け付けられるか、あるいは拒否されると、その低いほうのバウンドが連続的に改良される。前に最も廉価であった１つのソリューションが除去された（たとえば、それが無効の旅行料金である、その日に利用できるフライトがない、あるいは接続に十分な時間がないために、輸送業者がある旅行料金コンポーネントを別のものと組合せていない等）場合、次に廉価な旅行料金が低いほうのバウンドになる。このようにして、可能なソリューションは、低いほうのバウンドが再び変化しない限り（変化するまで）、系統的に無視されることができる。
【００４０】
前述したように、部分的ソリューションは、ソリューションツリー1500内の中間ノード1510、1515、1520および1525（レベル１乃至４における）に対する別の名称である。追加のトリップ情報が付加されていない最初の部分的ソリューション（ルートノード）1505と比較すると、ソリューションツリー1500のレベル５中で見出される完成ソリューション（リーフノード）1530は、旅行料金情報を含む全ての必要なトリップ情報を有している。
【００４１】
最良の旅行料金処理（以下において、図６乃至１２を参照としてさらに詳細に説明される）の１つの例示的な動作中、部分的ソリューション（ソリューションツリーノード）は任意しきい値費用にしたがって分割される（図１５内のブランチされたノードにおいて認められるように）。１つの例示的な実施形態において、しきい値費用は＄１００および１時間からスタートするが、それがおそらくＭＣＭ465によって決定される期待された旅行費用にある関係を明示する限り、任他の他の量が使用されることができる。各部分的ソリューションは、それがしきい値より低い完成ソリューションを提供することができる可能性があるか否かを決定するためにＭＣＭ465を使用して評価される。可能ならば、さらに別の情報が追加され（たとえば、現在のノードは分割されて、新しいレベルにおけるノードが追加され）、今度はそれらの新しい部分的ソリューションが評価される。否ならば、部分的ソリューションは処理されず（たとえば、それはノード1590におけるように延期され）、処理は、十分に完成ソリューションが見出されるか、あるいはその処理が時間切れになるまで続行する。十分に完成ソリューションが見出されておらず、時間が残っており、いくつかの部分的ソリューションが評価されていない場合、しきい値費用は増加され、評価されていないノードがその高いしきい値で再訪される。１つの例示的な実施形態においては、しきい値費用は５０＄および３０分だけ増加されるが、それがおそらくＭＣＭ465によって決定される期待された旅行費用に対してある関係を明示する限り、任意の他の量が使用されることができる。これは、十分な完成ソリューション（たとえば、任意の予め指定された数であることのできる完成したリーフノード；図１７Ａ乃至１７Ｃのウェブページは２組の３つのフライトを示し、合計９つの可能な完全ソリューションを提供する）が見出される）か、そのソリューションが使い果たされるか、あるいはその処理が時間切れになるまで続く。その時点で、任意の完成ソリューション（任意の数までの）がユーザに提供される（通常、最も適したソリューションが最初に与えられる）。
【００４２】
最良の旅行料金を見出す動作をさらによく例示するために、図６は、最良の旅行料金を見出すシステムにより行われるアクションの１つの例示的な実施形態を示している。本発明の例示的な適用を説明するために以下において航空輸送が使用されるが、当業者は、本発明が別の形態の輸送にも同様に適応されることを認識するであろう。図６のシステムは、クライアント装置210、ウェブサーバ220、旅行サーバ230、問合せサーバ400およびＣＲＳ250を含んでいる。以下、種々の装置の相互作用およびこれら装置によって行われるルーチンを後に図７乃至１３を参照としてさらに詳細に図示し、説明する。図６を参照とすると、クライアント装置210が特定のトリップに対する旅行料金605をウェブページ1600（図１６に示されているウェブページ1600のような）によってリクエストしたときに、問合せサーバ400による最良の旅行料金処理が開始される。旅行料金問合せはウェブサーバ220および旅行サーバ330を通過して、問合せサーバ400に到達する。問合せサーバ400は、ひとたび旅行料金問合せを受取ると、本質的にその問合せに対してソリューションツリー1500（図１５に示されているような）を構築する。とくに、可能なソリューションに対する旅行料金ブレークポイントが決定され、部分的ソリューションに割当てられる（ステップ610）。その後、問合せサーバ400は、ブレークポイントにより規定された旅行料金コンポーネント（旅行料金コンポーネントは２つのブレークポイント間のセグメントである）に可能な輸送業者を割当てる（ステップ615）。次に、輸送業者を割当てられた旅行料金コンポーネントに対してフライトが割当てられる（ステップ620）。その期間中に、問合せサーバ400はまた、ＣＲＳ250からのフライト利用可能性をチェックする（ステップ625）。ＣＲＳ250は、フライトの利用可能性データにより応答し（ステップ630）、その後問合せサーバは重複したフライトをチェックする。これによって、同じフライトであるが価格の高いものの列挙が阻止される。その後、問合せサーバ400はフライトを有する旅行料金コンポーネントを選び、これらを価格付け可能なユニットにグループ化する（ステップ635）。その後、これらの価格付け可能なユニットは、任意のルール、税および、または追加旅行料金と共に旅行料金を割当てられる（ステップ640）。その後、重複したソリューション（同じフライトであるが、その価格が同等以上）が除去される（ステップ645）。その後、最良の旅行料金を選択するために残りのソリューションが再検討され（ステップ650）、その旅行料金は旅行サーバ230およびウェブサーバ220によってクライアント装置210に転送される。図１７Ａ乃至１７Ｃには、例示的な旅行料金提供ウェブページ1710、1720および1730が示されている。以下、図７を参照として問合せサーバ400上での処理の詳細をさらに詳しく説明する。
【００４３】
当業者は、図６の任意のコンポーネントが本発明の動作に実質的に影響を与えずに変更されることが可能であることを認識するであろう。たとえば、問合せサーバ400および旅行サーバ230および、またはウェブサーバ220は、本発明の動作が損なわれることなく、同じ計算装置上に共存することができる。
【００４４】
図２、４および６に示されているように、本発明は、クライアント装置210によりリクエストされた最良の旅行料金を決定するために使用される問合せサーバ400を含んでいる。図７には、本発明の１つの実際の実施形態にしたがって最良の利用可能な旅行料金を決定するために問合せサーバ400によって実施される最良の旅行料金ルーチン700を示すフローチャートが示されている。最良旅行料金ルーチン700は、ブロック701からスタートし、旅行料金問合せが受取られるブロック705に進む。問合せは、第３パーティの旅行サーバまたは輸送業者のような無数のソースからのものであることができるが、例示のために、本発明の１実施形態においては問合せはクライアント装置220を使用して顧客から転送されている。次に、この問合せの中の情報は、旅行料金ブレークポイントを部分的ソリューションに追加すると共にしきい値費用より低いこれらの部分的ソリューションを優先度待行列475中に記憶されているソリューションツリー1500に追加するためにサブルーチンブロック800（以下、図８を参照としてさらに詳細に説明される）において使用される。この論理はサブルーチンブロック900（以下、図９を参照としてさらに詳細に説明される）に続き、このブロック900において、ブロック800で見出されたブレークポイントにより規定された旅行料金コンポーネントが、しきい値費用より低い部分的ソリューションを形成する場合、輸送業者を割当てられる。これらの輸送業者の割当は、優先度待行列475中の部分的ソリューションに追加される。輸送業者がひとたび割当てられると、処理はサブルーチンブロック1000（以下、図１０を参照としてさらに詳細に説明される）に続き、このブロック1000では、フライトが輸送業者を有する旅行料金コンポーネントに割当てられ、それはしきい値費用より低い部分的ソリューションを形成する。これらフライトの割当は、優先度待行列475中に記憶されているソリューションツリー1500の部分的ソリューションを更新する。次に、サブルーチンブロック1100（以下、図１１を参照としてさらに詳細に説明される）おいて、フライトが割当てられた旅行料金コンポーネントは、結果的に得られる部分的ソリューションがしきい値費用より低い場合に、価格付け可能なユニットを形成するようにグループ化される。その後、これらの価格付け可能なユニットは、優先度待行列475中の部分的ソリューションを更新するために使用される。その後、これに従ってサブルーチンブロック1200（以下、図１２に関して説明する）おいて、結果的に得られる部分的ソリューションがしきい値費用より低い場合に旅行料金を価格付け可能なユニットに割当てることができる。優先度待行列475中の部分的ソリューションはまた、これらの割当により更新される。処理はブロック710に続き、このブロック710において同じトリップ情報（旅行料金情報を除く）を有する部分的ソリューションが除去される。同じフライトに関する旅行料金データが提供されるが同等以上の旅行料金を有するものは必要ない。その後、決定ブロック715において、終了シナリオに達した（たとえば、予め定められた完成ソリューションセットに到達したか、全ての可能性が使い果たされたか、あるいは処理がある予め定められた時間制限を越えて時間切れになった）か否かが決定される。決定ブロック715において終了シナリオに到達していないことが決定された場合、処理はブロック725に進み、ここでしきい値費用が随意に選択された予め定められた量だけ増加され、処理がサブルーチン800に戻る。決定ブロック715において終了シナリオが到達された場合、処理はブロック720に続き、このブロック720において最低費用ソリューション（それぞれが１以上の価格付け可能なユニットおよび関連した旅行料金に関する完成したトリップ記述を含んでいる）が優先度待行列から除かれ、各最低費用ソリューションから旅行料金の合計価格をその最低費用ソリューションに対するトリップ記述と共に検索する（および合計する）ことによって旅行料金問合せに対する応答が発生される。その後、最終的な価格およびトリップ記述がフォーマット化され（図１７Ａ乃至１７Ｃのウェブページ1710、1720および1730におけるように）、リクエストした装置に送信される。ブロック799においてルーチン700は終了する。
【００４５】
上述したように、図８乃至１２においていくつかのサブルーチンが説明される。各サブルーチンはさらなる情報を分割し、これらを可能なソリューションのソリューションツリー1500に追加する。サブルーチンを詳細に調べる前に、図１４および１５にそれぞれ示されている２つのソリューションツリー1400および1500を考慮することが助けとなる。
【００４６】
図１４において、トリップ情報の各追加部分は各レベルでソリューションツリー1400に追加されるので、部分的ソリューションの数は指数関数的に増加する。この従来技術の例において各追加の層はソリューションを２つ多い部分的ソリューションに分割する。しかしながら、以下のサブルーチンに示されるように、ツリーを構築するときにノードの考慮を“延期する”プロセスにより、はるかに多くの管理可能なソリューションツリー1500が生成される。ある定まった費用より低いソリューションだけが考慮され、高過ぎる費用を有するものは、しきい値費用が増加するまで、さらなる処理に関して考慮されない（すなわち、延期される）。
【００４７】
図１５に示されているように、処理は、旅行料金問合せを表すルートノード1505から始まる。この時点では、詳細はソリューションツリー1500内の任意の他のノードに追加されていない。レベル１において、旅行料金ブレークポイント1510を有する部分的ソリューションがソリューションツリー1500に追加され（図８を参照）、例示的なソリューションツリー1500においては両ブレークポイントはしきい値費用より低い部分的ソリューションを可能にしている。レベル２において、輸送業者1515が割当てられる（図９を参照）が、４つの部分的ソリューションのうち３つだけがしきい値費用を満足させている。次にレベル３において、輸送業者を割当てられた旅行料金コンポーネントに対してフライトが割当てられ（1520）（図１０を参照）、６つの部分的ソリューションのうち３つだけがしきい値費用を満足させている。次にレベル４では、旅行料金コンポーネントが価格付け可能なユニットに割当てられ（1525）（図１１を参照）、６つの部分的ソリューションのうちの５つがしきい値費用を満足させている。最後にレベル５において、旅行料金（税およびいくつかの旅行料金を含む）が価格付け可能なユニットに割当てられ（図１２を参照）、１０の部分的ソリューションのうち７つだけがしきい値費用を満足させている。レベル５のノードだけが完成ソリューション1530のセットを表し、したがって可能なソリューションは、図１４に示されている３２個の代りに１０個となる。それ故、最低費用の完成ソリューション（リーフノード）をソリューションツリー1500から選択することははるかに簡単な作業となる。本発明の１実施形態において、選択は、最低費用ソリューションを最初に取出すことを可能にする優先度待行列475中に完成ソリューションを記憶することにより補助される。
【００４８】
図８乃至１２およびサブルーチン800乃至1200により延期されるソリューションツリー1500の構築の一般的な概要を説明してきたが、以下、サブルーチン800乃至1200および図８乃至１２をそれぞれさらに詳細に説明する。
図８から始めると、サブルーチン800はブロック801からスタートしてブロック805に進み、このブロック805において、新しい部分的ソリューションがしきい値費用（１実施形態では、呼出しルーチンにおいて同じしきい値が使用される）を越えないように、新しいブレークポイント（データ中に存在する任意の空港がブレークポイントとして追加されてもよい）がＭＣＭ465から検索され、ソリューションツリー1500のレベル１において新しい独特の部分的ソリューションに追加されるように努められ、そのブレークポイントは別の部分的ソリューション中にすでに存在するものと重複せず、また、ある輸送業者は旅行料金を公表して前のブレークポイントからの輸送手段を提供する。本発明を説明するために、例示的なソリューションツリー1500が使用されているが、しかしながら、当業者は、本発明の実際の実施形態により使用されるソリューションツリーが著しく複雑なものであってもよく、おそらく図１５に示されているソリューションツリー1500よりさらに多くのレベルおよび、またはノードを含んでいてもよいことを認識するであろう。ブレークポイントが追加されるべき前の部分的ソリューションはいずれも優先度待行列475から検索される。予備処理されたＭＣＭ465中の費用を使用して新しい可能な独特の部分的ソリューションの費用が決定され、それによって最少の実行可能な費用が決定される。とくに、部分的ソリューションの費用が全ての既知のトリップ情報を使用して計算され、その後ＭＣＭ465を使用することによって知られていないトリップ情報を最少費用の実行可能なトリップ情報で完成させる。ブロック805において、これは、ユーザの問合せおよび任意の前に決定されたブレークポイントだけが既知のトリップ情報であり、したがってＭＣＭ465が最少費用の実行可能な輸送業者、フライト、価格付け可能なユニットおよび旅行料金情報を可能な新しい独特のソリューションに提供することを意味する。トリップ情報の新しい各部分が部分的ソリューションに追加されると、部分的ソリューションの費用は改良され、おそらく増加し、増加した費用がしきい値を超えた場合、それは考慮から除外されるであろう。
【００４９】
決定ブロック810においてブレークポイントが発見されなかった場合、処理はブロック899に続き、このブロックにおいてブレークポイントが追加された部分的ソリューションが呼出しルーチンに戻される。そうではなく、ブレークポイントが発見された場合には、ブレークポイントを前のソリューション中の任意の既存のブレークポイントに追加し、ブロック815ではおそらく最後のブレークポイントとして到着地さえも追加し、および新しい独特のブレークポイントを優先度待行列475に追加することによって、新しい独特の部分的ソリューションが生成される。その後、処理はブロック805に戻って、ブレークポイントが追加されることのできる部分的ソリューションを求めてサーチする。
【００５０】
サブルーチン800は、ソリューションツリー1500のレベル１を位置させるために使用される。サブルーチン800（利用可能ならば）への呼出しを繰返すことにより可能なソリューション（すなわち、レベル１のノード）が提供され、その可能なソリューションはソリューションツリー1500の次のレベル（すなわち、レベル２のノード等）を構築するために後に使用されることとなる。レベル１はサブルーチン800によって全て同時に構築されるのではなく、反復または再帰により、サブルーチン800は呼出しを繰返され、現在のしきい値費用より低い可能なソリューションがインクリメントで追加される。しかしながら、サブルーチン800が終了してしまうと、最良の旅行料金を提供することとなる部分的ソリューションが追加されている可能性が高いため、その後ルーチン700はソリューションツリー1500のレベル２を構築する次のサブルーチン900を呼出す。
【００５１】
図９において、ソリューションツリー1500の構築は、ＭＣＭ465から検索された輸送業者情報を追加することにより次のレベルで続行する。サブルーチン900はブロック901からスタートし、ブロック905に進み、このブロック905では、旅行料金を公表し、旅行料金コンポーネントに追加されることとなる旅行料金コンポーネントに対して輸送手段を提供する輸送業者情報を見出し、しきい値費用（１実施形態において、呼出しルーチンにおいて同じしきい値が使用される）を越えない部分的ソリューションをＭＣＭ465を使用して形成することが試みられる。ブレークポイントが割当てられた部分的ソリューションは、優先度待行列475から検索される。予備処理されたＭＣＭ465内の費用を使用して新しい可能な独特の部分的ソリューションの費用が決定され、それによって最少の実行可能な費用が決定される。とくに、新しい部分的ソリューションの費用が全ての既知のトリップ情報を使用して計算され、その後ＭＣＭ465を使用することによって知られていないトリップ情報を最少費用の実行可能なトリップ情報により完成させる。ブロック905において、これは、ユーザの問合せ、ブレークポイントおよび前に割当てられた輸送業者だけが既知のトリップ情報であり、したがってＭＣＭ465が最少費用の実行可能なフライト、価格付け可能なユニットおよび旅行料金情報を新しい独特の可能なソリューションに提供することを意味する。トリップ情報の新しい各部分が部分的ソリューションに追加されると、部分的ソリューションの費用は改良され、おそらく増加し、増加した費用がしきい値を超えた場合、それは考慮から除外されるであろう。ブロック905においてこのような輸送業者が見出されなかった場合、処理はブロック999に続き、このブロックにおいて輸送業者が追加された部分的ソリューションが呼出しルーチン（この場合は、最良旅行料金ルーチン700）に戻される。そうではなく、輸送業者が発見された場合には、ブロック915おいて前のソリューションから検索された旅行料金コンポーネントに輸送業者を追加すると共に、優先度待行列475中に記憶されているソリューションツリー1500に部分的ソリューションを追加することによって、新しい独特の部分的ソリューションが生成される。その後、処理はブロック905に戻って、輸送業者が追加されることのできる部分的ソリューションを求めてサーチする。
【００５２】
サブルーチン800と同様に、サブルーチン900はソリューションツリー1500のレベル２を位置させるために使用される。サブルーチン900（利用可能ならば）への呼出しを繰返すことにより、輸送業者が可能なソリューション（すなわち、レベル２のノード）に提供され、その可能なソリューションはソリューションツリー1500の次のレベル（すなわち、レベル３のノード等）を構築するために後に使用されることとなる。サブルーチン900は呼出しを繰返され、現在のしきい値費用より低いソリューションをインクリメントに追加する。しかしながら、サブルーチン900が終了してしまうと、最良の旅行料金を提供することとなる部分的ソリューションが追加されている可能性が高いため、その後ルーチン700はソリューションツリー1500のレベル３を構築する次のサブルーチン1000を呼出す。
【００５３】
図１０には、割当てられた輸送業者にフライトを追加することによるソリューションツリー1500の構築が示されている。サブルーチン1000はブロック1001でスタートしてブロック1005に進み、このブロック1005において、割当てられた輸送業者を有する旅行料金コンポーネントに追加されるフライトをＦＳＲ470から見出し、しきい値費用（１実施形態において、呼出しルーチンにおいて同じしきい値が使用される）を越えない部分的ソリューションを形成することが試みられる。ブロック1005では、最も費用が安く、割当に利用できるフライトを決定するためにＭＣＭ465およびＦＳＲ470のスケジュールレコードの両方が使用される。輸送業者が割当てられた部分的ソリューションは、優先度待行列475から検索される。予備処理されたＭＣＭ465内の費用を使用して新しい可能な独特の部分的ソリューションの費用が決定され、それによって最少の実行可能な費用が決定される。とくに、新しい部分的ソリューションの費用が全ての既知のトリップ情報を使用して計算され、その後ＭＣＭ465を使用することによって知られていないトリップ情報を最少費用の実行可能なトリップ情報で完成させる。ブロック1005において、これは、ユーザの問合せ、ブレークポイント、輸送業者および前に割当てられたフライトだけが既知のトリップ情報であり、したがってＭＣＭ465が最少費用の実行可能な価格付け可能なユニットおよび旅行料金情報を新しい独特の可能なソリューションに提供することを意味する。トリップ情報の新しい各部分が部分的ソリューションに追加されると、部分的ソリューションの費用は改良され、おそらく増加し、増加した費用がしきい値を超えた場合、それは考慮から除外されるであろう。ブロック1005においてフライトが見出されなかった場合、処理はブロック1099に続き、このブロックにおいてフライトが追加された部分的ソリューションが呼出しルーチンに戻される。そうではなく、フライトが発見された場合には、ブロック1015おいて割当てられた輸送業者を有する旅行料金コンポーネントにフライト（ＣＲＳ250から検索された）を追加すると共に、優先度待行列475中に記憶されているソリューションツリー1500にそれを追加することによって、新しい独特の部分的ソリューションが生成される。その後、処理はブロック1005に戻って、フライトが追加されることのできる部分的ソリューションをサーチする。
【００５４】
サブルーチン800および900と同様に、サブルーチン1000はソリューションツリー1500のレベル３を位置させるために使用される。サブルーチン1000（利用可能ならば）への呼出しを繰返すことにより、フライトが可能なソリューション（すなわち、レベル３のノード）に提供され、その可能なソリューションはソリューションツリー1500の次のレベル（すなわち、レベル４のノード等）を構築するために後に使用されることとなる。サブルーチン1000は呼出しを繰返され、現在のしきい値費用より低いソリューションをインクリメントで追加する。しかしながら、サブルーチン1000が終了してしまうと、最良の旅行料金を提供することとなる部分的ソリューションが追加されている可能性が高いため、その後ルーチン700はソリューションツリー1500のレベル４を構築する次のサブルーチン1100を呼出す。
【００５５】
図１１には、旅行料金コンポーネントを価格付け可能なユニットにグループ化することによるソリューションツリー1500の構築が示されている。サブルーチン1100はブロック1101からスタートしてブロック1105に進み、このブロック1105において、フライトが割当てられているが価格付け可能なユニット（ＦＳＲ470から検索された）はまだ決定されていないしきい値費用（１実施形態において、呼出しルーチンにおいて同じしきい値が使用される）を越えない部分的ソリューションを見出すことが試みられる。ブロック1105では、どの価格付け可能なユニットが決定に利用可能かを決定するためにＦＳＲ470が使用される。フライトが割当てられた部分的ソリューションは、優先度待行列475から検索される。予備処理されたＭＣＭ465内の費用を使用して新しい可能な独特の部分的ソリューションの費用が決定され、それによって最少の実行可能な費用が決定される。とくに、新しい部分的ソリューションの費用が全ての既知のトリップ情報を使用して計算され、その後ＭＣＭ465を使用することによって知られていないトリップ情報を最少費用の実行可能なトリップ情報により完成させる。ブロック1105において、これは、ユーザの問合せ、ブレークポイント、輸送業者およびフライトだけが既知のトリップ情報であり、したがって新しい独特の可能なソリューションに対して、ＭＣＭ465が最少費用の実行可能な旅行料金情報を提供し、一方ＦＳＲ470が実際の価格付け可能なユニット情報を提供する。トリップ情報の新しい各部分が部分的ソリューションに追加されると、部分的ソリューションの費用は改良され、おそらく増加し、増加した費用がしきい値を超えた場合、それは考慮から除外されるであろう。ブロック1105において、価格付け可能なユニットがまだ定められていないしきい値費用より低い部分的ソリューションが見出されなかった場合、処理はブロック1199に続き、このブロックにおいて価格付け可能なユニットが決定されている部分的ソリューションは呼出しルーチンに戻される。そうではなく、基準を満たす部分的ソリューションが発見されたならば、部分的ソリューションが依然としてしきい値費用より低い全ての可能な組合せで価格付け可能なユニットに旅行料金コンポーネントをグループ化する（図１３のＣを参照として上述したように）ことによって、新しい独特の部分的ソリューションが生成される。その後、これらの新しい部分的ソリューションは追加され、それを優先度待行列475に追加する。その後、処理はブロック1105に戻り、価格付け可能なユニットがまだ決定されていない部分的ソリューションをサーチする。
【００５６】
サブルーチン800、900および1000と同様に、サブルーチン1100はソリューションツリー1500のレベル４を位置させるために使用される。サブルーチン1100（利用可能ならば）への呼出しを繰返すことにより、価格付け可能なユニットが可能なソリューション（すなわち、レベル４のノード）に提供され、その可能なソリューションはソリューションツリー1500の次のレベル（すなわち、レベル５のノード）を構築するために後に使用されることとなる。サブルーチン1100は呼出しを繰返され、現在のしきい値費用より低い可能なソリューションをインクリメントで追加する。しかしながら、サブルーチン1100が終了してしまうと、最良旅行料金を提供することとなる部分的ソリューションが追加されている可能性が高いため、その後ルーチン700はソリューションツリー1500のレベル５を構築する次のサブルーチン1200を呼出す。
【００５７】
図１２は、旅行料金を部分的ソリューションに割当て、それによって完成ソリューション（ソリューションツリー1500中のリーフノード）を生成することによりソリューションツリー1500の適格な部分的ソリューションに最終的なトリップ情報を追加する。サブルーチン1200はブロック1201からスタートしてブロック1205に進み、このブロック1205において、価格付け可能なユニットが定められており、しきい値費用（１実施形態において、呼出しルーチンにおいて同じしきい値が使用される）を越えない完成ソリューションを形成することとなる部分的ソリューションに追加されることとなる旅行料金を見出すことが試みられる。ブロック1205では、最も費用が安く、割当に利用できる旅行料金を決定するためにＭＣＭ465およびＦＳＲ470の両方が使用される。価格付け可能なユニットが割当てられた部分的ソリューションは、優先度待行列475から検索される。とくに、新しい部分的ソリューションの費用が全ての既知のトリップ情報を使用して計算され、その後ＭＣＭ465およびＦＳＲ470を使用することにより価格付け可能なユニットに対する実行可能なまたは実際の旅行料金で知られていないトリップ情報をそれぞれ完成させる。ブロック1205において、これは、ユーザの問合せ、ブレークポイント、輸送業者、フライトおよび価格付け可能なユニットが既知のトリップ情報であり、したがってＦＳＲ470が新しい独特の可能なソリューションに最少額の実際の旅行料金情報を提供するが、しかし全ての旅行料金があるトリップに対してまだ割当てられていない場合には、ＭＣＭ454もまた実行可能な旅行料金を提供することを意味する。トリップ情報の新しい各部分が部分的ソリューションに追加されると、部分的ソリューションの費用は改良され、おそらく増加し、増加した費用がしきい値を超えた場合、それは考慮から除外されるであろう。次に、決定ブロックにおいて、旅行料金が見出されたか否かが決定される。決定ブロック1210で旅行料金が見出されなかった場合、処理はブロック1299に続き、このブロックにおいて旅行料金が追加されている部分的ソリューションは呼出しルーチンに戻される。この時点で、最良の旅行料金ルーチン700は、それが終了状態（完成ソリューションが十分である、全ての可能なソリューションが使い果たされた、あるいは時間切れ）に達している場合、決定を行うことが必要であろう。
【００５８】
そうではなく、決定ブロック1210において旅行料金が発見されたならば、ブロック1215において旅行料金が割当てられていない旅行料金（ＦＲＳ470から検索された）を追加すると共に、それを優先度待行列475に追加することによって、新しい部分的ソリューションが生成される。次に、ブロック1220においてＦＲＳ470から検索された旅行料金ルールを使用して、価格付け変更が行われる必要があるか否か、あるいはその旅行料金が無効であるか否かが決定される。処理はブロック1225に進み、このブロックにおいて、ブロック1215において新しい部分的ソリューションに割当てられた旅行料金が有効な旅行料金であるか否かが決定される。決定ブロック1225において新しい部分的ソリューションが無効の旅行料金を含んでいることが決定された場合、その新しい部分的ソリューションは廃棄され、優先度待行列475から除去される。処理はブロック1205に戻り、旅行料金が追加されることのできる部分的ソリューションをサーチする。決定ブロック1225において無効の旅行料金であることが確実ではないことが決定された場合、処理はブロック1205に戻り、旅行料金が追加されることのできる部分的ソリューションをサーチする。
【００５９】
サブルーチン800、900、1000および1100と同様に、サブルーチン1200はソリューションツリー1500のレベル５を位置させるために使用される。しかしながら、サブルーチン800、900、1000および1100とは異なり、サブルーチン1200（利用可能ならば）への呼出しを繰返すことにより、完成ソリューションが提供され、この完成ソリューションはソリューションツリー1500の最終レベルを構築するために使用される。サブルーチン1200は呼出しを繰返され、現在のしきい値費用より低い完成ソリューションをインクリメントに追加する。サブルーチン1200が終了してしまうと、ルーチン700において終了状態が満足されているか否かを決定することができる。理想的には、ルーチン700で、十分な完成ソリューションが見出されていることが決定され、その場合はサブルーチン800、900、1000、1100または1200に対する呼出しはもはや必要なく、最良の旅行料金が見出されている（あるいは希な状況において旅行料金は全く見出されなかった、もしくは時間切れ状態のために限られた数の旅行料金しか見出されなかった）。
【００６０】
上記の図７乃至１２におけるサブルーチンの説明から認識されるように、トリップ情報の各追加は同様に処理される。各サブルーチンは新しい部分的ソリューション（サブルーチン1200の場合には完成ソリューション）を生成し、それらは生成されると優先度待行列475中のソリューションツリー1500に追加される。これらのソリューションを優先度待行列475中に置くことにより、それらが考慮に関して後に検査されたとき、最も可能性のある最良の旅行料金の候補だけを含む低い費用の可能なソリューションが最初に検査される。これは、優先度待行列475が、可能なソリューションが待ち行列から出されるときに最低費用のものを最初に提供するように設計されているためである。さらに、最良の旅行料金ルーチン700が中断されなかったと仮定すると、部分的ソリューションは優先度待行列から除去されないであろう。とくに、トリップ情報の全ての可能な組合せが試みられたなら、全てのノードは完成ソリューションとなるであろう。他方において、決定ブロック715において十分な数の完成ソリューションが発見された場合、完成ソリューションは常に低い費用であるとは限らず（部分ソリューションはしきい値を越えなかったが、完成ソリューションはしきい値を超えている）、また、十分な数の完成ソリューションが存在しているので、その数の完成ソリューションを待ち行列から除去することにより、部分的ソリューションは依然として除去されないであろう。
【００６１】
最良の旅行料金ルーチン700は本発明の１つの可能な最良の旅行料金ルーチンであり、本発明の別の例示的な実施形態ではソリューションツリーの可能なソリューションが“順方向”および“逆方向”の両方から検査されることに注意することが重要である。図１３のＢは、いくつかの“順方向ブレークポイント”13A乃至13Eおよび“逆方向ブレークポイント”13V乃至13Zをそのトリップの仮想“中間”1335の両側に示している。この実施形態において、ソリューションツリー1500は、出発地からの（順方向）および到着地からの（逆方向）フライトを両方検査することによって構築され、部分ソリューションは順方向部分および逆方向部分の両方に対しておそらく一度決定され、その後部分的ソリューション1360および1370として組合せられる。この順方向および逆方向分割は、部分的ソリューション分割して追加したときに図７乃至１２が順方向検査および逆方向検査を含むように、最良旅行料金ルーチンの各レベルにおいて適用されることができる。この“順方向および逆方向”処理の１つの利点は、ソリューションを見出す問題をもっと小さい問題にさらに分解するため、それが回帰的および、または並行処理によく適していることである。とくに、本発明の１つの実際の実施形態において、この分解により、最良の旅行料金ルーチンが非常に高価なメインフレームコンピュータ上ではなくパーソナルコンピュータ上で実行されることが可能となっている。
【００６２】
以上、本発明の好ましい実施形態を図示および説明してきたが、本発明の技術的範囲を逸脱することなく種々の変更を行うことができることが認識されるであろう。
【図面の簡単な説明】
【００６３】
【図１】インターネットのようなインターネットワークの代表的な部分を示す概略図（従来技術）。
【図２】本発明にしたがって旅行料金問合せに応答してインターネットワークに接続されているクライアント装置に最良旅行料金を提供するインターネットワークに接続されたいくつかの装置の概略図。
【図３】本発明にしたがって旅行料金レコードを最適化するために使用された図２に示されている予備処理サーバのコンポーネントのいくつかを示すブロック図。
【図４】本発明にしたがって旅行料金問合せに応答して最良の旅行料金を決定するために使用された図２に示されている問合せサーバのコンポーネントのいくつかを示すブロック図。
【図５】旅行料金レコードを最適化するために予備処理サーバにより行われる予備処理ルーチンを示す概観フロー図。
【図６】本発明にしたがって旅行料金問合せに応答して最良の旅行料金を決定するためにクライアント装置、ウェブサーバ、旅行サーバ、問合せサーバ、ファイルサーバおよびコンピュータ予約システムによりとられるアクションを示す概略図。
【図７】本発明にしたがって最良の旅行料金を決定するために問合せサーバにより行われる最良の旅行料金サーチルーチンを示す概観フロー図。
【図８】問合せサーバにより行われる最良の旅行料金ブレークポイント決定サブルーチンを示す概観フロー図。
【図９】問合せサーバにより行われる貨物便割当サブルーチンを示す概観フロー図。
【図１０】問合せサーバにより行われる旅客便割当サブルーチンを示す概観フロー図。
【図１１】問合せサーバにより行われる価格付け可能なユニット決定サブルーチンを示す概観フロー図。
【図１２】問合せサーバにより行われる旅行料金割当サブルーチンを示す概観フロー図。
【図１３】図７乃至１２に示されているフロー図の理解に役立つ経路およびブレークポイント図。
【図１４】本発明により提供される利益を理解するのに役立つ完全ソリューションツリー図（従来技術）。
【図１５】本発明により提供される利益を理解するのに役立つ完全ソリューションツリー図。
【図１６】顧客から旅行料金問合せを受取る例示的なウェブページの概略図。
【図１７Ａ】旅行料金問合せに対して受取られた応答を表示する例示的なウェブページの概略図。
【図１７Ｂ】旅行料金問合せに対して受取られた応答を表示する例示的なウェブページの概略図。
【図１７Ｃ】旅行料金問合せに対して受取られた応答を表示する例示的なウェブページの概略図。
【図１】
2005505025.tif 000003
【図２】
2005505025.tif 000004
【図３】
2005505025.tif 000005
【図４】
2005505025.tif 000006
【図５】
2005505025.tif 000007
【図６】
2005505025.tif 000008
【図７】
2005505025.tif 000009
【図８】
2005505025.tif 000010
【図９】
2005505025.tif 000011
【図１０】
2005505025.tif 000012
【図１１】
2005505025.tif 000013
【図１２】
2005505025.tif 000014
【図１３】
2005505025.tif 000015
【図１４】
2005505025.tif 000016
【図１５】
2005505025.tif 000017
【図１６】
2005505025.tif 000018
【図１７Ａ】
2005505025.tif 000019
【図１７Ｂ】
2005505025.tif 000020
【図１７Ｃ】
2005505025.tif 000021
【国際公開パンフレット】
2005505025.tif 000022
2005505025.tif 000023
2005505025.tif 000024
2005505025.tif 000025
2005505025.tif 000026
2005505025.tif 000027
2005505025.tif 000028
2005505025.tif 000029
2005505025.tif 000030
2005505025.tif 000031
2005505025.tif 000032
2005505025.tif 000033
2005505025.tif 000034
2005505025.tif 000035
2005505025.tif 000036
2005505025.tif 000037
2005505025.tif 000038
2005505025.tif 000039
2005505025.tif 000040
2005505025.tif 000041
2005505025.tif 000042
2005505025.tif 000043
2005505025.tif 000044
2005505025.tif 000045
2005505025.tif 000046
2005505025.tif 000047
2005505025.tif 000048
2005505025.tif 000049
2005505025.tif 000050
2005505025.tif 000051
2005505025.tif 000052
2005505025.tif 000053
2005505025.tif 000054
2005505025.tif 000055
2005505025.tif 000056
2005505025.tif 000057
2005505025.tif 000058
2005505025.tif 000059
2005505025.tif 000060
2005505025.tif 000061
2005505025.tif 000062
2005505025.tif 000063
2005505025.tif 000064
2005505025.tif 000065
2005505025.tif 000066
2005505025.tif 000067
2005505025.tif 000068
2005505025.tif 000069
2005505025.tif 000070
2005505025.tif 000071
2005505025.tif 000072
2005505025.tif 000073
2005505025.tif 000074
2005505025.tif 000075
【国際公開パンフレット（コレクトバージョン）】
2005505025.tif 000076
2005505025.tif 000077
【国際調査報告】
2005505025.tif 000078
2005505025.tif 000079
2005505025.tif 000080