(57)【特許請求の範囲】
【請求項１】
旅行者によって入力された旅行条件データと、旅行業者及びシステム管理者によって入力されデータベースに格納された旅行情報データとを用いて、旅行計画を作成し、作成された前記旅行計画を前記旅行者に提示するための旅行計画作成コンピュータ・システムにおいて、前記旅行計画作成コンピュータ・システムの旅行計画作成サーバが旅行計画を作成する方法であって、
前記旅行計画作成サーバが、前記旅行条件データ内の旅行期間の各日について、前記データベースから受信した前記旅行情報データに含まれるスロット属性データに基づいて、各日の時間と、予め定められた開始時刻及び終了時刻によって決まる同一の時間幅及び／又は異なる時間幅を有する複数のスロットとを関連付けるステップと、
前記旅行計画作成サーバが、前記旅行期間内に前記旅行者が利用可能な１つ又は複数のサービスに関する情報を含むデータである利用可能リストを作成する、利用可能リスト作成ステップであって、前記１つ又は複数のサービスに関する情報は、前記複数のスロットの各々に付与された特性と適合するように予め関連付けが定義された１つ又は複数のアクティビティに関する情報を含み、前記利用可能リストは、アクティビティについて指定された前記旅行条件データに含まれる条件に基づいて、前記旅行情報データから取得されたデータを用いて作成される、利用可能リスト作成ステップと、
前記旅行計画作成サーバが、前記リストにおける前記１つ又は複数のサービスの各々を前記複数のスロットの各々に割り付けるかどうかを定義する決定変数を含む式で表現される複数の制約条件のうちの１つ又は複数を含む制約条件の組を作成する、制約条件構成ステップであって、前記複数の制約条件は、前記利用可能リストにおける前記１つ又は複数のサービスの各々を前記複数のスロットの各々に割り付けるときの優先度に応じた、前記決定変数の和と前記旅行条件データに含まれるアクティビティの実施回数との関係に関する制約条件、及び、前記複数のスロットの１つ又は複数に割り付けられるサービスの実施に必要な時間の長さと前記決定変数との積の和と、前記複数のスロットの１つ又は複数の時間幅の長さとの関係によって表される、時間に関する制約条件を含む、制約条件構成ステップと、
前記旅行計画作成サーバが、作成される旅行計画のアクティビティの実施回数に関する特性を表す所定の変数を含む項と時間に関する特性を表す所定の変数を含む項とを含む目的関数を作成する、目的関数構成ステップと、
前記旅行計画作成サーバが、前記制約条件の組と前記目的関数とを混合整数計画問題を解くための演算プログラムに入力し、前記演算プログラムから出力された、前記制約条件の組の下で前記目的関数を最適化又は近似最適化するための決定変数の組み合わせに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスのうち前記出力された決定変数に対応するサービスの各々と前記出力された決定変数に対応する前記複数のスロットの各々とを関連付けたデータを作成し、該データと前記旅行情報データとを用いて、少なくとも前記複数のスロットの各々とアクティビティとを関連付けたデータである旅行計画を作成する、旅行計画作成ステップと、
を含むことを特徴とする方法。
【請求項２】
前記利用可能リスト作成ステップは、
前記旅行計画作成サーバが、前記利用可能リストに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスの各々が複数のアクティビティを含む複合サービスであるかどうかを判定し、複合サービスであると判定した場合には、前記複合サービスに関するデータから、各々が１つのアクティビティを含む複数の新たなサービスに関するデータを作成する、複合サービス分割ステップ、及び／又は、前記旅行計画作成サーバが、前記利用可能リストに含まれるデータに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスの各々が、該サービスに含まれるアクティビティの実施に必要な時間幅が少なくとも１つのスロットの時間幅を越える長大サービスであるかどうかを判定し、長大サービスであると判定した場合には、前記長大サービスに関するデータから、各々の実施に必要な時間幅が１つのスロットの時間幅以下である複数の新たなサービスに関するデータを作成する、長大サービス分割ステップと、
前記旅行計画作成サーバが、前記複合サービスと前記長大サービスと前記複数の新たなサービスとの関係を表す関係データを作成する、関係データ作成ステップと、
前記旅行計画作成サーバが、前記利用可能リストにおいて、前記複合サービスに関するデータ及び／又は前記長大サービスに関するデータを前記複数の新たなサービスに関するデータに置換することによって新たなリストを作成する、新リスト作成ステップと、
をさらに含み、
前記制約条件構成ステップは、前記旅行計画作成サーバが、前記複数の新たなサービス相互間の関係に関する、前記決定変数を含む式で表現される制約条件を作成するステップをさらに含むことを特徴とする、請求項１に記載の方法。
【請求項３】
前記複合サービス分割ステップは、
前記旅行計画作成サーバが、前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがｓタイプであると判定した場合には、
前記旅行計画作成サーバが、前記複合サービスに含まれるアクティビティの各々の開始時刻と終了時刻とから、前記新たなサービスの各々の実施に必要な時間幅を算出するステップをさらに含み、
前記旅行計画作成サーバが、前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがａ１タイプであると判定した場合には、
前記旅行計画作成サーバが、前記旅行者が前記複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、前記旅行条件データに含まれていると判定したときは、前記指定時間と、前記アクティビティの各々を提供する前記旅行業者の営業時間とを比較して、時間の短い方を前記新たなサービスの各々の実施に必要な時間幅として設定し、
前記旅行計画作成サーバが、前記旅行者が前記複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、前記旅行条件データに含まれていないと判定したときは、前記新たなサービスの各々に含まれるアクティビティの実施に適した時間幅を前記新たなサービスの各々の実施に必要な時間幅として設定する、
ステップをさらに含み、
前記旅行計画作成サーバが、前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがａ２タイプであると判定した場合には、
前記旅行計画作成サーバが、前記新たなサービスの各々に含まれるアクティビティの実施に必要な時間幅を前記新たなサービスの各々の実施に必要な時間幅として設定するステップをさらに含み、
前記サービス・タイプに関するデータは、前記旅行情報データに含まれており、前記ｓタイプのサービスは、前記旅行業者によって前記１つ又は複数のサービスの各々に含まれるアクティビティの日付、開始時刻及び終了時刻が予め定められたサービスであり、前記ａ１タイプのサービスは、前記旅行業者によってアクティビティの開始時刻及び終了時刻は定められていないがアクティビティの実施に適した時間幅が定められ、かつ、前記旅行業者の営業時間内に利用可能なサービスであり、前記ａ２タイプのサービスは、前記旅行業者によってアクティビティの開始時刻及び終了時刻は定められてないがアクティビティの実施に必要な時間幅が定められ、かつ、前記旅行業者の営業時間内に利用可能なサービスであることを特徴とする、請求項２に記載の方法。
【請求項４】
前記長大サービス分割ステップは、
前記旅行計画作成サーバが、前記旅行情報データに基づいて、前記長大サービスのサービス・タイプがｓタイプであると判定した場合には、
前記旅行計画作成サーバが、前記長大サービスに含まれるアクティビティの開始時刻を含む最初のスロット、前記アクティビティの終了時刻を含む最後のスロット、及び、前記最初のスロットと前記最後のスロットとの間に前記最初のスロット及び前記最後のスロットとは別の１つ又は複数のスロットが存在するときには前記別の１つ又は複数のスロット、を特定するステップと、
前記旅行計画作成サーバが、前記長大サービスに関するデータから、前記最初のスロットに対応する最初の新たなサービスに関するデータ、前記最後のスロットに対応する最後の新たなサービスに関するデータ、及び、前記別の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータ、を作成するステップと、
前記旅行計画作成サーバが、前記アクティビティの前記開始時刻から前記最初のスロットの前記終了時刻までの時間幅を、前記最初の新たなサービスの実施に必要な時間幅として設定するステップと、
前記旅行計画作成サーバが、前記最後のスロットの前記開始時刻から前記アクティビティの前記終了時刻までの時間幅を、前記最後の新たなサービスの実施に必要な時間幅として設定するステップと、
前記旅行計画作成サーバが、前記別の１つ又は複数のスロットの時間幅を、前記１つ又は複数の新たなサービスの実施に必要な時間幅として設定するステップと、
をさらに含むことを特徴とする、請求項２又は請求項３に記載の方法。
【請求項５】
前記長大サービス分割ステップは、
前記旅行計画作成サーバが、前記旅行情報データに基づいて、前記長大サービスのサービス・タイプがａ１タイプ又はａ２タイプであると判定した場合には、
前記旅行計画作成サーバが、スロットの開始時刻又は終了時刻のいずれか一方が前記長大サービスを提供する前記旅行業者の営業開始時刻と営業終了時刻との間にあり、前記長大サービスに含まれるアクティビティの実施に適したスロット群と一致する、１つ又は複数のスロットを特定するステップと、
前記旅行計画作成サーバが、前記特定した１つ又は複数のスロットのうちの最初のスロットが、前記営業開始時刻を含むスロットであると判定したときは、前記営業開始時刻から前記最初のスロットの終了時刻までに対応する最初の新たなサービスに関するデータを作成し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、前記営業開始時刻から前記最初のスロットの前記終了時刻までの時間幅を前記最初の新たなサービスの実施に必要な時間幅として設定し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記１つ又は複数のスロットの時間幅を前記１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、前記長大サービスの実施に必要な時間幅から、前記最初の新たなサービスから前記最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定するステップと、
前記旅行計画作成サーバが、前記特定した１つ又は複数のスロットのうちの最初のスロットが、前記営業開始時刻を含むスロットより後のスロットであると判定したときは、前記最初のスロットに対応する最初の新たなサービスに関するデータを作成し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、前記最初のスロットの時間幅を前記最初の新たなサービスの実施に必要な時間幅として設定し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記１つ又は複数のスロットの時間幅を前記１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、前記長大サービスの実施に必要な時間幅から、前記最初の新たなサービスから前記最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定するステップと、
をさらに含むことを特徴とする、請求項２又は請求項３に記載の方法。
【請求項６】
前記利用可能リストは、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、前記利用可能リスト作成ステップの後に、前記旅行計画作成サーバが、前記利用可能リストに含まれる複数のデータ単位の前記利用可能リスト内での並び順を変更するステップをさらに含むことを特徴とする、請求項１に記載の方法。
【請求項７】
前記新たなリストは、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、前記新リスト作成ステップの後に、前記旅行計画作成サーバが、前記新たなリストに含まれる複数のデータ単位の前記新たなリスト内での並び順を変更するステップをさらに含むことを特徴とする、請求項２に記載の方法。
【請求項８】
旅行者によって入力された旅行条件データと旅行業者及びシステム管理者によって入力されデータベースに格納された旅行情報データとを用いて旅行計画を作成する処理をコンピュータに実行させるプログラム・コードを含むコンピュータ・プログラムであって、
前記処理が、
前記旅行条件データ内の旅行期間の各日について、前記データベースから受信した前記旅行情報データに含まれるスロット属性データに基づいて、各日の時間と予め定められた開始時刻及び終了時刻によって決まる同一の時間幅及び／又は異なる時間幅を有する複数のスロットとを関連付ける処理と、
前記旅行期間内に前記旅行者が利用可能な１つ又は複数のサービスに関する情報を含むデータである利用可能リストを作成する、利用可能リスト作成処理であって、前記１つ又は複数のサービスに関する情報は、前記複数のスロットの各々に付与された特性と適合するように予め関連付けが定義された１つ又は複数のアクティビティに関する情報を含み、前記利用可能リストは、アクティビティについて指定された前記旅行条件データに含まれる条件に基づいて、前記旅行情報データから取得されたデータを用いて作成される、利用可能リスト作成処理と、
前記リストにおける前記１つ又は複数のサービスの各々を前記複数のスロットの各々に割り付けるかどうかを定義する決定変数を含む式で表現される複数の制約条件のうちの１つ又は複数を含む制約条件の組を作成する、制約条件構成処理であって、前記複数の制約条件は、前記利用可能リストにおける前記１つ又は複数のサービスの各々を前記複数のスロットの各々に割り付けるときの優先度に応じた、前記決定変数の和と前記旅行条件データに含まれるアクティビティの実施回数との関係に関する制約条件、及び、前記複数のスロットの１つ又は複数に割り付けられるサービスの実施に必要な時間の長さと前記決定変数との積の和と、前記複数のスロットの１つ又は複数の時間幅の長さとの関係によって表される、時間に関する制約条件を含む、制約条件構成処理と、
作成される旅行計画のアクティビティの実施回数に関する特性を表す所定の変数を含む項と時間に関する特性を表す所定の変数を含む項とを含む目的関数を作成する、目的関数構成処理と、
前記制約条件の組と前記目的関数とを混合整数計画問題を解くための演算プログラムに入力し、前記演算プログラムから出力された、前記制約条件の組の下で前記目的関数を最適化又は近似最適化するための決定変数の組み合わせに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスのうち前記出力された決定変数に対応するサービスの各々と前記出力された決定変数に対応する前記複数のスロットの各々とを関連付けたデータを作成し、該データと前記旅行情報データとを用いて、少なくとも前記複数のスロットの各々とアクティビティとを関連付けたデータである旅行計画を作成する、旅行計画作成処理と、
を含むことを特徴とするコンピュータ・プログラム。
【請求項９】
前記利用可能リスト作成処理は、
前記利用可能リストに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスの各々が複数のアクティビティを含む複合サービスであるかどうかを判定し、複合サービスであると判定した場合には、前記複合サービスに関するデータから、各々が１つのアクティビティを含む複数の新たなサービスに関するデータを作成する、複合サービス分割処理、及び／又は、前記利用可能リストに含まれるデータに基づいて、前記利用可能リストにおける前記１つ又は複数のサービスの各々が、該サービスに含まれるアクティビティの実施に必要な時間幅が少なくとも１つのスロットの時間幅を越える長大サービスであるかどうかを判定し、長大サービスであると判定した場合には、前記長大サービスに関するデータから、各々の実施に必要な時間幅が１つのスロットの時間幅以下である複数の新たなサービスに関するデータを作成する、長大サービス分割処理と、
前記複合サービスと前記長大サービスと前記複数の新たなサービスとの関係を表す関係データを作成する、関係データ作成処理と、
前記利用可能リストにおいて、前記複合サービスに関するデータ及び／又は前記長大サービスに関するデータを前記複数の新たなサービスに関するデータに置換することによって新たなリストを作成する、新リスト作成処理と、
をさらに含み、
前記制約条件構成処理は、前記複数の新たなサービス相互間の関係に関する、前記決定変数を含む式で表現される制約条件を作成する処理をさらに含むことを特徴とする、請求項８に記載のコンピュータ・プログラム。
【請求項１０】
前記複合サービス分割処理は、
前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがｓタイプであると判定した場合には、
前記複合サービスに含まれるアクティビティの各々の開始時刻と終了時刻とから、前記新たなサービスの各々の実施に必要な時間幅を算出する処理をさらに含み、
前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがａ１タイプであると判定した場合には、
前記旅行者が前記複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、前記旅行条件データに含まれていると判定したときは、前記指定時間と、前記アクティビティの各々を提供する前記旅行業者の営業時間とを比較して、時間の短い方を前記新たなサービスの各々の実施に必要な時間幅として設定し、
前記旅行者が前記複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、前記旅行条件データに含まれていないと判定したときは、前記新たなサービスの各々に含まれるアクティビティの実施に適した時間幅を前記新たなサービスの各々の実施に必要な時間幅として設定する、
処理をさらに含み、
前記旅行情報データに基づいて、前記複合サービスのサービス・タイプがａ２タイプであると判定した場合には、
前記新たなサービスの各々に含まれるアクティビティの実施に必要な時間幅を前記新たなサービスの各々の実施に必要な時間幅として設定する処理をさらに含み、
前記サービス・タイプに関するデータは、前記旅行情報データに含まれており、前記ｓタイプのサービスは、前記旅行業者によって前記１つ又は複数のサービスの各々に含まれるアクティビティの日付、開始時刻及び終了時刻が予め定められたサービスであり、前記ａ１タイプのサービスは、前記旅行業者によってアクティビティの開始時刻及び終了時刻は定められていないがアクティビティの実施に適した時間幅が定められ、かつ、前記旅行業者の営業時間内に利用可能なサービスであり、前記ａ２タイプのサービスは、前記旅行業者によってアクティビティの開始時刻及び終了時刻は定められてないがアクティビティの実施に必要な時間幅が定められ、かつ、前記旅行業者の営業時間内に利用可能なサービスであることを特徴とする、請求項９に記載のコンピュータ・プログラム。
【請求項１１】
前記長大サービス分割処理は、
前記旅行情報データに基づいて、前記長大サービスのサービス・タイプがｓタイプであると判定した場合には、
前記長大サービスに含まれるアクティビティの開始時刻を含む最初のスロット、前記アクティビティの終了時刻を含む最後のスロット、及び、前記最初のスロットと前記最後のスロットとの間に前記最初のスロット及び前記最後のスロットとは別の１つ又は複数のスロットが存在するときには前記別の１つ又は複数のスロット、を特定する処理と、
前記長大サービスに関するデータから、前記最初のスロットに対応する最初の新たなサービスに関するデータ、前記最後のスロットに対応する最後の新たなサービスに関するデータ、及び、前記別の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータ、を作成する処理と、
前記アクティビティの前記開始時刻から前記最初のスロットの前記終了時刻までの時間幅を、前記最初の新たなサービスの実施に必要な時間幅として設定する処理と、
前記最後のスロットの前記開始時刻から前記アクティビティの前記終了時刻までの時間幅を、前記最後の新たなサービスの実施に必要な時間幅として設定する処理と、
前記別の１つ又は複数のスロットの時間幅を、前記１つ又は複数の新たなサービスの実施に必要な時間幅として設定する処理と、
をさらに含むことを特徴とする、請求項９又は請求項１０に記載のコンピュータ・プログラム。
【請求項１２】
前記長大サービス分割処理は、
前記旅行情報データに基づいて、前記長大サービスのサービス・タイプがａ１タイプ又はａ２タイプであると判定した場合には、
スロットの開始時刻又は終了時刻のいずれか一方が前記長大サービスを提供する前記旅行業者の営業開始時刻と営業終了時刻との間にあり、前記長大サービスに含まれるアクティビティの実施に適したスロット群と一致する、１つ又は複数のスロットを特定する処理と、
前記特定した１つ又は複数のスロットのうちの最初のスロットが、前記営業開始時刻を含むスロットであると判定したときは、前記営業開始時刻から前記最初のスロットの終了時刻までに対応する最初の新たなサービスに関するデータを作成し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、前記営業開始時刻から前記最初のスロットの前記終了時刻までの時間幅を前記最初の新たなサービスの実施に必要な時間幅として設定し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記１つ又は複数のスロットの時間幅を前記１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、前記長大サービスの実施に必要な時間幅から、前記最初の新たなサービスから前記最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定する処理と、
前記特定した１つ又は複数のスロットのうちの最初のスロットが、前記営業開始時刻を含むスロットより後のスロットであると判定したときは、前記最初のスロットに対応する最初の新たなサービスに関するデータを作成し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、前記最初のスロットの時間幅を前記最初の新たなサービスの実施に必要な時間幅として設定し、前記最初のスロットの次のスロットが前記営業終了時刻を含むスロットでないときには前記１つ又は複数のスロットの時間幅を前記１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、前記長大サービスの実施に必要な時間幅から前記最初の新たなサービスから前記最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定する処理と、
をさらに含むことを特徴とする、請求項９又は請求項１０に記載のコンピュータ・プログラム。
【請求項１３】
前記利用可能リストは、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、前記利用可能リスト作成処理の後に、前記利用可能リストに含まれる複数のデータ単位の前記利用可能リスト内での並び順を変更する処理をさらに含むことを特徴とする、請求項８に記載のコンピュータ・プログラム。
【請求項１４】
前記新たなリストは、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、前記新リスト作成処理の後に、前記新たなリストに含まれる複数のデータ単位の前記新たなリスト内での並び順を変更する処理をさらに含むことを特徴とする、請求項９に記載のコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、旅行者の要求に応答して最適化又は近似最適化した旅行計画を自動的に作成するための方法に関し、特に、混合整数計画問題を解くための演算プログラムに入力して演算を行うことによって最適化又は近似最適化した旅行計画を自動的に作成するために、混合整数計画問題に適用することができるように入力データを処理する方法に関する。
【背景技術】
【０００２】
旅行を旅行計画の側面から見ると、大きく個人旅行、手配旅行、及び主催旅行に分類することができる。個人旅行は、旅行者自らが旅行予定地の交通機関、観光施設及び宿泊施設の空き状況、営業時間、料金などを調査し、その結果に基づいて旅行計画を立案し、ホームページ又は電話などを用いて必要な手配を直接行う旅行形態である。手配旅行は、旅行者が、旅行代理店に赴き、旅行代理店の従業員に対して旅行予定地の交通機関、観光施設及び宿泊施設についての希望を提示し、それに対して旅行代理店の従業員が、旅行代理店の専用端末を通じて各機関又は施設の空き状況、営業時間、料金などを調査して旅行者に提示し、これらの調査結果に対して旅行者の了解が得られた場合に、各機関又は施設の手配を行う旅行形態である。主催旅行は、旅行代理店があらかじめ独自の旅行計画を企画し、旅行参加者を募集することによって、ある程度決まったスケジュールの旅行計画を提供する旅行形態である。上記の主催旅行は、比較的自由行動の多いものであっても旅行者の希望にきめ細かく応じることが難しいため、近年、旅行形態は、主催旅行から手配旅行又は個人旅行に移行する傾向が指摘されており、旅行単位は、団体から家族へ、家族から少人数グループ又は個人へと変化しつつある。
【０００３】
ところが、手配旅行は、上述のように旅行代理店を利用して必要な情報収集及び手配を行うものであるため、旅行者にとっては時間が拘束されると共に、費用がかかるという問題がある。これに対して、最近は、交通機関、観光施設、及び宿泊施設などがホームページを持つ場合も多く、旅行者は、インターネットを通じてこれらのホームページにアクセスして旅行計画に必要な情報を収集し、予約などの手配を直接行うことも可能になっている。このように、インターネットを利用すれば、旅行者は、時間の拘束を受けずに安価に、自分の好みに応じた旅行計画を立案することができる。
【０００４】
しかしながら、従来は、交通機関、観光施設、及び宿泊施設などがそれぞれ個別にホームページを持つのみであったため、旅行を計画する旅行者は、まず、数多くのホームページの中から自分が第一に希望する交通機関、観光施設、及び宿泊施設などのホームページを別個に検索し、各々の機関及び施設などの営業日時、料金、予約の可否などを確認すると共に、他の施設などの営業時間、料金、予約の可否等をも勘案しながら全体の計画を立案しなければならず、非常に手間がかかるという問題があった。
【０００５】
こうした問題を解決するため、個人旅行者の旅行計画立案とその実現に必要な支援を提供する技術が幾つか存在する。特許文献１は、ネットワークを介してコンピュータにアクセスしたブラウズ端末から、少なくとも出発地及び旅行先を含む旅行プラン策定のための諸条件を含む旅行プラン策定依頼を受信し、その諸条件を満たす旅行プランを策定して、策定した旅行プランのデータを該ブラウズ端末に送信するシステムを開示する。ブラウズ端末から、該ブラウズ端末に送信した旅行プランの修正依頼を受信した場合には、旅行プランを策定し直して、その策定し直した旅行プランのデータをブラウズ端末に送信する。この技術においては、旅行プランは、システムのコンピュータが、旅行プラン策定依頼から抽出した諸条件等を満足する旅行モデルひな形データを旅行モデルひな形データベースから抽出してブラウズ端末に提示し、提示されたひな形をユーザが修正した場合には、その修正に基づいて該ひな形データを変更してブラウザ端末に再提示することによって、策定される。
【０００６】
特許文献２は、所望の旅行先を訪問する際に費やされると予想される所要時間を取得し、それらと移動先の間の予想移動時間とを組み合わせることにより旅行スケジュールを自動作成するシステムを開示する。このシステムは、ユーザが画面に表示される訪問候補地を指定すると、各々の訪問候補地ごとの予想移動時間と予想所要時間とから、例えば最短コースを巡るスケジュールを作成し、作成したスケジュールをユーザに提示する。システムは、提示されたスケジュールをユーザがチェックした結果に基づいて、所要時間の変更、訪問候補地の追加又は削除などのスケジュール編集を行うことによって、最終的なスケジュールを作成する。
【０００７】
特許文献３は、旅行管理サーバがユーザ端末から旅行希望条件を受信すると、この旅行希望条件に基づいて観光施設等情報データベース等を検索し、希望条件に合った旅行先情報等を取得し、これらの情報に基づいて固有の旅行スケジュールを作成するシステムを開示する。旅行スケジュールの作成は、以下の処理によって行われる。まず、旅行管理サーバは、旅行期間内に利用可能な観光施設等を抽出する。次に、抽出された観光施設等を、旅行者が指定したプランニング条件の優先度合い（例えば、ホテルのランクについて、高、中、低など）によって重み付けして評価し、その評価点と各観光施設の評価値（例えば、ホテルのランク）とを比較する。評価値が一定以上の観光施設等を抽出して絞り込み、評価点の高い順にスケジュールに追加する。このとき、既に旅行スケジュール内に組み込まれている候補との位置関係（距離関係）、時間帯、利用交通手段等を考慮して最適な位置に観光施設等を新規追加していくことによって、旅行スケジュールを作成する。
【０００８】
【特許文献１】特開２００３−４４５５３号明細書
【特許文献２】特開２００２−１９７１５０号明細書
【特許文献３】特開２００２−７３７５６号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述の先行技術は、以下のような課題を有する。特許文献１の技術は、ユーザが指定した希望条件を満足する旅行プランを策定するものの、その旅行プランの原型はひな形データベースに既に格納されており、ユーザの要求に応じて該ひな形データベースからひな形データを検索して提示するものであるため、あくまでも限定されたプランしか提示することができない。また、特許文献２の技術は、ユーザが訪問したい観光地、名所、又は施設などの訪問候補地を端末から指定した場合に、それらの訪問候補地間の移動時間と各訪問候補地の所要時間とを組み合わせ、経路探索を行って旅行スケジュールを作成するものである。すなわち、本技術は、基本的には、ユーザが指定した訪問候補地を巡る時間的スケジュールを作成するものであって、ユーザの希望条件に応じて最適な観光施設の組み合わせまでも自動的に組み合わせてスケジュールを作成する技術ではない。特許文献３の技術は、旅行者が指定した優先度によって重み付けした評価点を各観光施設の評価点と比較する手法に基づいて旅行スケジュールを作成する方法であるが、本手法は、最適な組み合わせ問題を解決するための一般に認知された手法ではなく、したがって、極めて多くの選択肢の中から作成されたスケジュールが最適なものであるかどうかを客観的に評価することは困難である。
【００１０】
このように、上述の先行技術を含む従来技術においては、何らかの手法に基づいて旅行計画を作成する技術が開示されてはいるものの、一般的に広く認知されている客観的な最適化又は近似最適化手法を用いて自動的に旅行計画を作成する技術は見出すことができない。こういった事情に鑑み、本発明の目的は、一般的に認知された最適化手法である混合整数計画問題に基づいて、極めて多くの可能性のある旅行計画の中から旅行者の要求を満足する最適化又は近似最適化された旅行計画を自動的に作成する技術を提供することである。
【課題を解決するための手段】
【００１１】
上記の目的は、旅行者によって入力された旅行条件データと、旅行業者及びシステム管理者によって入力され、データベースに格納された旅行情報データとから、混合整数計画問題に適用することができるように処理した入力データを作成し、該入力データを混合整数計画問題を解くための演算プログラムに入力して演算処理を行うことにより、従来技術においては例のない、混合整数計画問題を利用して最適化又は近似最適化した旅行計画を自動的に作成することができるという知見に基づく以下の特徴を有する本発明によって達成される。
【００１２】
請求項１に記載の発明は、旅行者によって入力された旅行条件データと、旅行業者及びシステム管理者によって入力されデータベースに格納された旅行情報データとを用いて、旅行計画を作成し、作成された旅行計画を旅行者に提示するための旅行計画作成コンピュータ・システムにおいて、旅行計画作成コンピュータ・システムの旅行計画作成サーバが旅行計画を作成する方法であって、旅行計画作成サーバが、旅行条件データ内の旅行期間の各日について、データベースから受信した旅行情報データに含まれるスロット属性データに基づいて、各日の時間と予め定められた開始時刻及び終了時刻によって決まる同一の時間幅及び／又は異なる時間幅を有する複数のスロットとを関連付けるステップと、旅行計画作成サーバが、旅行期間内に旅行者が利用可能な１つ又は複数のサービスに関する情報を含むデータである利用可能リストを作成する、利用可能リスト作成ステップであって、１つ又は複数のサービスに関する情報は、複数のスロットの各々に付与された特性と適合するように予め関連付けが定義された１つ又は複数のアクティビティに関する情報を含み、利用可能リストは、アクティビティについて指定された旅行条件データに含まれる条件に基づいて、旅行情報データから取得されたデータを用いて作成される、利用可能リスト作成ステップと、旅行計画作成サーバが、リストにおける１つ又は複数のサービスの各々を複数のスロットの各々に割り付けるかどうかを定義する決定変数を含む式で表現される複数の制約条件のうちの１つ又は複数を含む制約条件の組を作成する、制約条件構成ステップであって、複数の制約条件は、利用可能リストにおける１つ又は複数のサービスの各々を複数のスロットの各々に割り付けるときの優先度に応じた、決定変数の和と旅行条件データに含まれるアクティビティの実施回数との関係に関する制約条件、及び、複数のスロットの１つ又は複数に割り付けられるサービスの実施に必要な時間の長さと決定変数との積の和と、複数のスロットの１つ又は複数の時間幅の長さとの関係によって表される、時間に関する制約条件を含む、制約条件構成ステップと、旅行計画作成サーバが、作成される旅行計画のアクティビティの実施回数に関する特性を表す所定の変数を含む項と時間に関する特性を表す所定の変数を含む項とを含む目的関数を作成する、目的関数構成ステップと、旅行計画作成サーバが、制約条件の組と目的関数とを混合整数計画問題を解くための演算プログラムに入力し、演算プログラムから出力された、制約条件の組の下で目的関数を最適化又は近似最適化するための決定変数の組み合わせに基づいて、利用可能リストにおける１つ又は複数のサービスのうち出力された決定変数に対応するサービスの各々と出力された決定変数に対応する複数のスロットの各々とを関連付けたデータを作成し、該データと旅行情報データとを用いて、少なくとも複数のスロットの各々とアクティビティとを関連付けたデータである旅行計画を作成する、旅行計画作成ステップと、を含むことを特徴とする。
【００１３】
請求項２に記載の発明は、利用可能リスト作成ステップが、旅行計画作成サーバが、利用可能リストに基づいて、利用可能リストにおける１つ又は複数のサービスの各々が複数のアクティビティを含む複合サービスであるかどうかを判定し、複合サービスであると判定した場合には、複合サービスに関するデータから、各々が１つのアクティビティを含む複数の新たなサービスに関するデータを作成する、複合サービス分割ステップ、及び／又は、旅行計画作成サーバが、利用可能リストに含まれるデータに基づいて、利用可能リストにおける１つ又は複数のサービスの各々が、該サービスに含まれるアクティビティの実施に必要な時間幅が少なくとも１つのスロットの時間幅を越える長大サービスであるかどうかを判定し、長大サービスであると判定した場合には、長大サービスに関するデータから、各々の実施に必要な時間幅が１つのスロットの時間幅以下である複数の新たなサービスに関するデータを作成する、長大サービス分割ステップと、旅行計画作成サーバが、複合サービスと長大サービスと複数の新たなサービスとの関係を表す関係データを作成する、関係データ作成ステップと、旅行計画作成サーバが、利用可能リストにおいて、複合サービスに関するデータ及び／又は長大サービスに関するデータを複数の新たなサービスに関するデータに置換することによって新たなリストを作成する、新リスト作成ステップと、をさらに含み、  制約条件構成ステップは、旅行計画作成サーバが、複数の新たなサービス相互間の関係に関する、決定変数を含む式で表現される制約条件を作成するステップをさらに含むことを特徴とする。
【００１４】
【００１５】
請求項３に記載の発明は、複合サービス分割ステップにおいて、旅行計画作成サーバが、旅行情報データに基づいて、複合サービスのサービス・タイプがｓタイプであると判定した場合には、旅行計画作成サーバが、複合サービスに含まれるアクティビティの各々の開始時刻と終了時刻とから、新たなサービスの各々の実施に必要な時間幅を算出するステップをさらに含み、旅行計画作成サーバが、旅行情報データに基づいて、複合サービスのサービス・タイプがａ１タイプであると判定した場合には、旅行計画作成サーバが、旅行者が複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、旅行条件データに含まれていると判定したときは、指定時間と、アクティビティの各々を提供する旅行業者の営業時間とを比較して、時間の短い方を新たなサービスの各々の実施に必要な時間幅として設定し、旅行計画作成サーバが、旅行者が複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、旅行条件データに含まれていないと判定したときは、新たなサービスの各々に含まれるアクティビティの実施に適した時間幅を新たなサービスの各々の実施に必要な時間幅として設定する、ステップをさらに含み、旅行計画作成サーバが、旅行情報データに基づいて、複合サービスのサービス・タイプがａ２タイプであると判定した場合には、旅行計画作成サーバが、新たなサービスの各々に含まれるアクティビティの実施に必要な時間幅を新たなサービスの各々の実施に必要な時間幅として設定するステップをさらに含み、  サービス・タイプに関するデータは、旅行情報データに含まれており、ｓタイプのサービスは、旅行業者によって１つ又は複数のサービスの各々に含まれるアクティビティの日付、開始時刻及び終了時刻が予め定められたサービスであり、ａ１タイプのサービスは、旅行業者によってアクティビティの開始時刻及び終了時刻は定められていないがアクティビティの実施に適した時間幅が定められ、かつ、旅行業者の営業時間内に利用可能なサービスであり、ａ２タイプのサービスは、旅行業者によってアクティビティの開始時刻及び終了時刻は定められてないがアクティビティの実施に必要な時間幅が定められ、かつ、旅行業者の営業時間内に利用可能なサービスであることを特徴とする。
【００１６】
請求項４に記載の発明は、長大サービス分割ステップにおいて、旅行計画作成サーバが、旅行情報データに基づいて、長大サービスのサービス・タイプがｓタイプであると判定した場合には、旅行計画作成サーバが、長大サービスに含まれるアクティビティの開始時刻を含む最初のスロット、アクティビティの終了時刻を含む最後のスロット、及び、最初のスロットと最後のスロットとの間に最初のスロット及び最後のスロットとは別の１つ又は複数のスロットが存在するときには別の１つ又は複数のスロットを特定するステップと、  旅行計画作成サーバが、長大サービスに関するデータから、最初のスロットに対応する最初の新たなサービスに関するデータ、最後のスロットに対応する最後の新たなサービスに関するデータ、及び、別の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを作成するステップと、旅行計画作成サーバが、アクティビティの開始時刻から最初のスロットの終了時刻までの時間幅を、最初の新たなサービスの実施に必要な時間幅として設定するステップと、旅行計画作成サーバが、最後のスロットの開始時刻からアクティビティの終了時刻までの時間幅を、最後の新たなサービスの実施に必要な時間幅として設定するステップと、旅行計画作成サーバが、別の１つ又は複数のスロットの時間幅を、１つ又は複数の新たなサービスの実施に必要な時間幅として設定するステップと、をさらに含むことを特徴とする。
【００１７】
請求項５に記載の発明は、長大サービス分割ステップにおいて、旅行計画作成サーバが、旅行情報データに基づいて、長大サービスのサービス・タイプがａ１タイプ又はａ２タイプであると判定した場合には、旅行計画作成サーバが、スロットの開始時刻又は終了時刻のいずれか一方が長大サービスを提供する旅行業者の営業開始時刻と営業終了時刻との間にあり、長大サービスに含まれるアクティビティの実施に適したスロット群と一致する、１つ又は複数のスロットを特定するステップと、旅行計画作成サーバが、特定した１つ又は複数のスロットのうちの最初のスロットが、営業開始時刻を含むスロットであると判定したときは、営業開始時刻から最初のスロットの終了時刻までに対応する最初の新たなサービスに関するデータを作成し、最初のスロットの次のスロットが営業終了時刻を含むスロットでないときには最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、営業開始時刻から最初のスロットの終了時刻までの時間幅を最初の新たなサービスの実施に必要な時間幅として設定し、最初のスロットの次のスロットが営業終了時刻を含むスロットでないときには１つ又は複数のスロットの時間幅を１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、長大サービスの実施に必要な時間幅から、最初の新たなサービスから最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定するステップと、旅行計画作成サーバが、特定した１つ又は複数のスロットのうちの最初のスロットが、営業開始時刻を含むスロットより後のスロットであると判定したときは、最初のスロットに対応する最初の新たなサービスに関するデータを作成し、最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、最初のスロットの時間幅を最初の新たなサービスの実施に必要な時間幅として設定し、１つ又は複数のスロットの時間幅を１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、長大サービスの実施に必要な時間幅から最初の新たなサービスから最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定するステップと、をさらに含むことを特徴とする。
【００１８】
請求項６に記載の発明は、利用可能リストが、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、利用可能リスト作成ステップの後に、旅行計画作成サーバが、利用可能リストに含まれる複数のデータ単位の利用可能リスト内での並び順を変更するステップをさらに含むことを特徴とする。
【００１９】
請求項７に記載の発明は、新たなリストが、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、新リスト作成ステップの後に、旅行計画作成サーバが、新たなリストに含まれる複数のデータ単位の新たなリスト内での並び順を変更するステップをさらに含むことを特徴とする。
【００２０】
請求項８に記載の発明は、旅行者によって入力された旅行条件データと旅行業者及びシステム管理者によって入力されデータベースに格納された旅行情報データとを用いて旅行計画を作成する処理をコンピュータに実行させるプログラム・コードを含むコンピュータ・プログラムであって、処理が、旅行条件データ内の旅行期間の各日について、データベースから受信した旅行情報データに含まれるスロット属性データに基づいて、各日の時間と予め定められた開始時刻及び終了時刻によって決まる同一の時間幅及び／又は異なる時間幅を有する複数のスロットとを関連付ける処理と、旅行期間内に旅行者が利用可能な１つ又は複数のサービスに関する情報を含むデータである利用可能リストを作成する、利用可能リスト作成処理であって、１つ又は複数のサービスに関する情報は、複数のスロットの各々に付与された特性と適合するように予め関連付けが定義された１つ又は複数のアクティビティに関する情報を含み、利用可能リストは、アクティビティについて指定された旅行条件データに含まれる条件に基づいて、旅行情報データから取得されたデータを用いて作成される、利用可能リスト作成処理と、リストにおける１つ又は複数のサービスの各々を複数のスロットの各々に割り付けるかどうかを定義する決定変数を含む式で表現される複数の制約条件のうちの１つ又は複数を含む制約条件の組を作成する、制約条件構成処理であって、複数の制約条件は、利用可能リストにおける１つ又は複数のサービスの各々を複数のスロットの各々に割り付けるときの優先度に応じた、決定変数の和と旅行条件データに含まれるアクティビティの実施回数との関係に関する制約条件、及び、複数のスロットの１つ又は複数に割り付けられるサービスの実施に必要な時間の長さと決定変数との積の和と、複数のスロットの１つ又は複数の時間幅の長さとの関係によって表される、時間に関する制約条件を含む、制約条件構成処理と、作成される旅行計画のアクティビティの実施回数に関する特性を表す所定の変数を含む項と時間に関する特性を表す所定の変数を含む項とを含む目的関数を作成する、目的関数構成処理と、制約条件の組と目的関数とを混合整数計画問題を解くための演算プログラムに入力し、演算プログラムから出力された、制約条件の組の下で目的関数を最適化又は近似最適化するための決定変数の組み合わせに基づいて、利用可能リストにおける１つ又は複数のサービスのうち出力された決定変数に対応するサービスの各々と出力された決定変数に対応する複数のスロットの各々とを関連付けたデータを作成し、該データと旅行情報データとを用いて、少なくとも複数のスロットの各々とアクティビティとを関連付けたデータである旅行計画を作成する、旅行計画作成処理と、を含むことを特徴とする。
【００２１】
請求項９に記載の発明は、利用可能リスト作成処理が、利用可能リストに基づいて、利用可能リストにおける１つ又は複数のサービスの各々が複数のアクティビティを含む複合サービスであるかどうかを判定し、複合サービスであると判定した場合には、複合サービスに関するデータから、各々が１つのアクティビティを含む複数の新たなサービスに関するデータを作成する、複合サービス分割処理、及び／又は、利用可能リストに含まれるデータに基づいて、利用可能リストにおける１つ又は複数のサービスの各々が、該サービスに含まれるアクティビティの実施に必要な時間幅が少なくとも１つのスロットの時間幅を越える長大サービスであるかどうかを判定し、長大サービスであると判定した場合には、長大サービスに関するデータから、各々の実施に必要な時間幅が１つのスロットの時間幅以下である複数の新たなサービスに関するデータを作成する、長大サービス分割処理と、複合サービスと長大サービスと複数の新たなサービスとの関係を表す関係データを作成する、関係データ作成処理と、利用可能リストにおいて、複合サービスに関するデータ及び／又は長大サービスに関するデータを複数の新たなサービスに関するデータに置換することによって新たなリストを作成する、新リスト作成処理と、をさらに含み、制約条件構成処理は、複数の新たなサービス相互間の関係に関する、決定変数を含む式で表現される制約条件を作成する処理をさらに含むことを特徴とするコンピュータ・プログラムを提供するものである。
【００２２】
【００２３】
請求項１０に記載の発明は、複合サービス分割処理において、旅行情報データに基づいて、複合サービスのサービス・タイプがｓタイプであると判定した場合には、複合サービスに含まれるアクティビティの各々の開始時刻と終了時刻とから、新たなサービスの各々の実施に必要な時間幅を算出する処理をさらに含み、旅行情報データに基づいて、複合サービスのサービス・タイプがａ１タイプであると判定した場合には、旅行者が複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、旅行条件データに含まれていると判定したときは、指定時間と、アクティビティの各々を提供する旅行業者の営業時間とを比較して、時間の短い方を新たなサービスの各々の実施に必要な時間幅として設定し、旅行者が複合サービスに含まれるアクティビティの各々に費やすことを希望する時間幅である指定時間が、旅行条件データに含まれていないと判定したときは、新たなサービスの各々に含まれるアクティビティの実施に適した時間幅を新たなサービスの各々の実施に必要な時間幅として設定する、処理をさらに含み、旅行情報データに基づいて、複合サービスのサービス・タイプがａ２タイプであると判定した場合には、新たなサービスの各々に含まれるアクティビティの実施に必要な時間幅を新たなサービスの各々の実施に必要な時間幅として設定する処理をさらに含み、サービス・タイプに関するデータは、旅行情報データに含まれており、ｓタイプのサービスは、旅行業者によって１つ又は複数のサービスの各々に含まれるアクティビティの日付、開始時刻及び終了時刻が予め定められたサービスであり、ａ１タイプのサービスは、旅行業者によってアクティビティの開始時刻及び終了時刻は定められていないがアクティビティの実施に適した時間幅が定められ、かつ、旅行業者の営業時間内に利用可能なサービスであり、ａ２タイプのサービスは、旅行業者によってアクティビティの開始時刻及び終了時刻は定められてないがアクティビティの実施に必要な時間幅が定められ、かつ、旅行業者の営業時間内に利用可能なサービスであることを特徴とするコンピュータ・プログラムを提供するものである。
【００２４】
請求項１１に記載の発明は、長大サービス分割処理において、旅行情報データに基づいて、長大サービスのサービス・タイプがｓタイプであると判定した場合には、長大サービスに含まれるアクティビティの開始時刻を含む最初のスロット、アクティビティの終了時刻を含む最後のスロット、及び、最初のスロットと最後のスロットとの間の１つ又は複数のスロットを特定する処理と、長大サービスに関するデータから、最初のスロットに対応する最初の新たなサービスに関するデータ、最後のスロットに対応する最後の新たなサービスに関するデータ、及び、１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを作成する処理と、アクティビティの開始時刻から最初のスロットの終了時刻までの時間幅を、最初の新たなサービスの実施に必要な時間幅として設定する処理と、最後のスロットの開始時刻からアクティビティの終了時刻までの時間幅を、最後の新たなサービスの実施に必要な時間幅として設定する処理と、１つ又は複数のスロットの時間幅を、１つ又は複数の新たなサービスの実施に必要な時間幅として設定する処理と、をさらに含むことを特徴とするコンピュータ・プログラムを提供するものである。
【００２５】
請求項１２に記載の発明は、長大サービス分割処理において、旅行情報データに基づいて、長大サービスのサービス・タイプがａ１タイプ又はａ２タイプであると判定した場合には、長大サービスを提供する旅行業者の営業開始時刻と営業終了時刻との間にあり、長大サービスに含まれるアクティビティの実施に適したスロット群と一致する１つ又は複数のスロットを特定する処理と、特定した１つ又は複数のスロットのうちの最初のスロットが、営業開始時刻を含むスロットであると判定したときは、営業開始時刻から最初のスロットの終了時刻までに対応する最初の新たなサービスに関するデータを作成し、最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、営業開始時刻から最初のスロットの終了時刻までの時間幅を最初の新たなサービスの実施に必要な時間幅として設定し、１つ又は複数のスロットの時間幅を１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、長大サービスの実施に必要な時間幅から、最初の新たなサービスから最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定する処理と、特定した１つ又は複数のスロットのうちの最初のスロットが、営業開始時刻を含むスロットより後のスロットであると判定したときは、最初のスロットに対応する最初の新たなサービスに関するデータを作成し、最初のスロットの次のスロット以降の１つ又は複数のスロットに対応する１つ又は複数の新たなサービスに関するデータを順次作成し、次いで、最初のスロットの時間幅を最初の新たなサービスの実施に必要な時間幅として設定し、１つ又は複数のスロットの時間幅を１つ又は複数の新たなサービスの実施に必要な時間幅としてそれぞれ設定し、最後の新たなサービスの実施に必要な時間幅は、長大サービスの実施に必要な時間幅から最初の新たなサービスから最後の新たなサービスの直前のサービスまでの実施に必要な時間幅の合計を引いた時間幅を設定する処理と、をさらに含むことを特徴とするコンピュータ・プログラムを提供するものである。
【００２６】
請求項１３に記載の発明は、利用可能リストが、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、利用可能リスト作成処理の後に、利用可能リストに含まれる複数のデータ単位の利用可能リスト内での並び順を変更する処理をさらに含むことを特徴とするコンピュータ・プログラムを提供するものである。
【００２７】
請求項１４に記載の発明は、新たなリストが、サービスに関する情報がサービス毎に１つのデータ単位として構成されており、新リスト作成処理の後に、新たなリストに含まれる複数のデータ単位の新たなリスト内での並び順を変更する処理をさらに含むことを特徴とするコンピュータ・プログラムを提供するものである。
【発明を実施するための最良の形態】
【００２８】
［システム構成］
以下に、本発明の１つの実施形態について説明する。当然のことながら、本発明は、この実施形態に限定されるものではない。図１は、本発明の１つの実施形態に係る旅行計画作成コンピュータ・システムの基本構成を示すブロック図である。図１に示すように、本旅行計画作成コンピュータ・システムは、旅行者、旅行業者、及びシステム管理者が利用する１つ又は複数の端末と、旅行計画を作成する旅行計画作成手段等を実装する旅行計画作成サーバと、アクティビティ及びサービスなどの、旅行計画作成コンピュータ・システムの作動に必要なデータを格納するデータベースとで構成される。ここで「アクティビティ」とは、宿泊、交通、施設見学、食事、又は登山などといった、旅行者が行う観光行動の類型を表す。また、「サービス」とは、１つ又は複数のアクティビティを含む、旅行業者が提供する商品の単位を表す。１つ又は複数の端末と該旅行計画作成装置とは、インターネットなどの通信網を介して接続される。１つ又は複数の旅行者用端末は、旅行者が旅行条件データを入力し、旅行計画作成サーバにおいて作成された旅行計画を表示するための端末である。「旅行条件データ」は、後述するように、旅行者が旅行計画に対して指定する希望条件に関するデータである。１つ又は複数の旅行者用端末は、パーソナル・コンピュータ、携帯電話、又は携帯情報端末（ＰＤＡ）などのネットワーク端末とすることができる。１つ又は複数の旅行業者用及びシステム管理者用端末は、旅行業者及びシステム管理者が旅行情報データを入力するための端末である。「旅行情報データ」は、後述するように、旅行業者及び／又はシステム管理者が提供及び／又は入力する、旅行計画を作成するために必要なデータである。１つ又は複数の旅行業者用及びシステム管理者用端末は、パーソナル・コンピュータ又は専用端末とすることができる。旅行者、旅行業者、及びシステム管理者が利用する１つ又は複数の端末は、ウェブ閲覧機能及びインターネットなどの通信網への接続機能を有すると共に、少なくとも、ＣＲＴ又は液晶ディスプレイなどの表示装置と、ハードディスク、ＲＡＭ、又はＣＤ−ＲＯＭなどの記憶装置と、キーボード、マウス、又はタッチパネルなどのデータ入力装置とを有する、汎用又は専用の端末装置であればよい。
【００２９】
旅行計画作成サーバは、インターネットなどの通信網への接続機能を有すると共に、少なくとも、オペレーティング・システム並びに本発明に係る処理をコンピュータに実行させるためのコンピュータ・プログラム（すなわち、コンピュータを図１に示される旅行計画作成サーバの手段の各々（例えば、利用可能リスト作成手段）として機能させるためのコンピュータ・プログラム）及び他のアプリケーション・プログラムを実行し、これらの全体動作を管理するＣＰＵと、各種のコンピュータ・プログラム又はデータを読み込むためのＲＡＭなどのメモリと、オペレーティング・システム並びに本発明に係る処理をコンピュータに実行させるためのコンピュータ・プログラム及び他のアプリケーション・プログラムを格納するハードディスク装置などの記憶装置と、これらの各種装置を接続するバスとを有するコンピュータとすることができる。旅行計画作成サーバには、必要に応じて、ＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭなどのドライブ装置と、キーボード又はマウスなどのデータ入力装置と、ＣＲＴ又は液晶ディスプレイなどの表示装置とを接続するようにしてもよい。
【００３０】
データベースは、インターネットなどの通信網への接続機能を有すると共に、少なくとも、オペレーティング・システム並びに本発明に係る処理を実行するためのコンピュータ・プログラム及び他の各種のアプリケーション・プログラムを実行させ、これらの全体動作を管理するＣＰＵと、各種のプログラム又はデータを読み込むためのＲＡＭなどのメモリと、オペレーティング・システム、本発明に係る処理を実行するためのコンピュータ・プログラム及び他のアプリケーション・プログラム、並びに、本発明に係る旅行計画作成に必要なアクティビティなどの旅行情報データを格納するハードディスク装置などの記憶装置と、これらの各種装置を接続するバスとを有するコンピュータとすることができる。データベースには、必要に応じて、ＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭなどのドライブ装置と、キーボード又はマウスなどのデータ入力装置と、ＣＲＴ又は液晶ディスプレイなどの表示装置とを接続するようにしてもよい。図１においては、データベースは、旅行計画作成サーバとは別に設置し、インターネットなどの通信網を介して該旅行計画作成サーバと接続されるものとしているが、データベースは、旅行計画作成サーバ内に構成することもできる。
【００３１】
図１に示すように、旅行計画作成サーバは、旅行計画に対して指定される旅行条件データを取得する旅行条件データ取得手段と、取得された旅行条件データをデータベースに送信する旅行条件データ格納手段と、該旅行条件データとデータベースに格納された旅行情報データとに基づいて利用可能リストを作成する利用可能リスト作成手段と、旅行計画を構成するサービスの選択可能な組み合わせに関する制約条件を構成する制約条件構成手段と、旅行計画の特性を表す変数を用いて目的関数を構成する目的関数構成手段と、該制約条件及び該目的関数から旅行計画を作成する旅行計画作成手段と、作成された旅行計画をユーザ端末に提供する旅行計画提供手段とを有する。「利用可能リスト」は、図１０を参照して後述するように、旅行者が希望する旅行期間内に提供を受けることが可能なサービスに関するデータをサービス毎に１つの単位とし、複数の単位を適当な順序で並べてリスト化したデータ群である。旅行計画作成サーバは、さらに、１つのサービスが複数のアクティビティを含む場合などに前述の利用可能リスト内のサービスを分割して新たなリストを作成する拡大利用可能リスト作成手段を有する。「拡大利用可能リスト」は、例えば１つのサービスが複数のアクティビティを含む場合などに、利用可能リスト内の当該サービスを相互に関連付けられた複数のサービスに分割し（すなわち、利用可能リスト内の当該サービスに関するデータから相互に関連付けられた複数のサービスに関するデータを作成する。これ以降、「１つのサービスを複数のサービスに分割する」とは、「１つのサービスに関するデータから複数のサービスに関するデータを作成する」ことを意味するものとする）、元のサービスに関するデータ群を、分割した複数のサービスに関するデータ群に置き換えることによって作成される新たなリストである。上記の各手段の機能は、本明細書において詳細に後述する。
【００３２】
一方、データベースは、旅行業者及びシステム管理者によって端末から入力されるか又は提供される、旅行計画を作成するために必要な旅行情報データを格納する。データベースに格納される旅行情報データは、一日（すなわち、２４時間）を同一の時間幅又は異なる時間幅に分割して得られる複数の時間帯の各々（以下、「スロット」という）に関する情報であるスロット属性データ（以下、「スロット表」という）（図５参照）と、旅行業者が提供するサービス及びアクティビティに関する情報であるサービス属性データ（以下、「サービス−アクティビティ表」という）（図９参照）と、アクティビティとスロットとを関連付ける情報であるアクティビティ−スロット関連付けデータ（以下、「アクティビティ−スロット表」という）（図７参照）と、を含む。なお、当然のことながら、データベースは、これらのスロット属性データ、サービス属性データ、アクティビティ−スロット関連付けデータ以外に、旅行計画を作成するために必要な各種のデータも格納することができる。また、当然のことながら、データベースは、後述される種々の処理を行う過程で生成され、その後の別の処理で使用される各種の中間的なデータも格納することができる。
【００３３】
旅行計画は、生産スケジュールなどとは異なり、時間的には余裕を多く含んだスケジュールであると考えられる。さらに、この余裕自体が柔軟性に富んだものである。したがって、スケジュールが決まったサービスを利用する場合でも、そのスケジュールの前後の時間の使い方は、柔軟性に富むものと考えるべきである。このような柔軟性を旅行計画作成コンピュータ・システムに組み込むために、本発明では、旅行期間を複数のスロットに分割する（すなわち、旅行期間の各日の時間をスロット表（スロット属性データ）に予め定められた複数のスロットと関連付ける）方法を採用する。スロットに関するデータであるスロット表は、図５を参照して後述するように、システム管理者によって端末から予め入力されるデータであり、１日を同一の時間幅又は異なる時間幅を有する複数の時間帯（例えば８つの時間帯）に分割して得られる、その時間帯の各々（スロット）に付与される例えばＡ〜Ｈの記号（以下、「スロット・タイプ」という）と、例えばスロット・タイプＡは早朝、Ｂは朝食、Ｃは午前などというように各々のスロットに付与される特性と、各々のスロットの開始時刻及び終了時刻とが関連付けられてデータベースに予め格納されているデータである。
【００３４】
サービス−アクティビティ表は、旅行業者によって提供及び／又は端末から入力されるデータであり、図９を参照して後述するように、サービスを特定するサービス・コード、そのサービスに含まれるアクティビティを特定するアクティビティ・コード、及びそのアクティビティの必要時間などが関連付けられてデータベースに格納されているデータである。さらに、アクティビティ−スロット表は、システム管理者が端末から入力して設定するデータであり、図７を参照して後述するように、アクティビティを特定するアクティビティ・コードと、各々のアクティビティの名称と、各々のアクティビティを実行するのに適した（又は、実行することが可能な）スロットのスロット・タイプ（以下、「適合スロット・タイプ」という）とが関連付けられてデータベースに格納されているデータである。このアクティビティ−スロット表によって、アクティビティとスロット特性との関連付けが定義されることになる。
【００３５】
データベースは、さらに、各々のサービスを提供する旅行業者の名称、所在地などの、旅行業者に関する情報であり、作成された旅行計画に含まれるサービスを予約／購入するのに必要な予約関連データを含む旅行業者データを格納することもできる。また、データベースは、必要に応じて、旅行業者が提供するサービス間の移動時間に関する情報である移動時間データ（図示せず）を格納することもできる。この移動時間データを用いて、サービスをスロットに割り付ける際に、該サービスの前又は後に該移動時間データを加算しながらサービスをスロットに割り付けるようにすることもできる。
【００３６】
２．旅行計画作成の概略的な手順
図２は、本発明の１つの実施形態に従って、旅行計画作成コンピュータ・システムによって旅行計画を作成する方法を概略的に示す。本方法においては、まず、旅行計画の作成を希望する旅行者が、旅行者用端末から、旅行開始日時、旅行終了日時、（例えば、大人、子供、及び乳幼児別の）人数、希望するアクティビティとその優先度及び実施回数、並びに、予算額などの旅行計画特性などといった、旅行計画に対して指定する旅行条件データを入力する。入力された旅行条件データは、インターネットなどの通信網を介して旅行計画作成サーバに送信され、該旅行計画作成サーバの旅行条件データ取得手段によって受信される。一方、旅行業者によって別の端末から入力された、サービスに含まれるアクティビティ、アクティビティの必要時間、サービスの開始日及び終了日、サービスの価格、又は受入人数（サービス対象単位及びグループ数）などのサービス属性データ（図９参照）は、インターネットなどの通信網を介して予めデータベースに送信され、格納される。次いで、旅行計画作成サーバの利用可能リスト作成手段が、旅行条件データ取得手段によって取得した旅行条件データと、スロット表のデータ（図５参照）、サービス−アクティビティ表のデータ（図９参照）、及び、アクティビティ−スロット表のデータ（図７参照）とを用いて、利用可能リストを作成する。スロット表のデータ、サービス−アクティビティ表のデータ、及びアクティビティ−スロット表のデータは、旅行情報データとして予めデータベースに格納される。
【００３７】
次いで、旅行計画作成サーバの制約条件構成手段が、作成された利用可能リスト内の複数のサービスについて、その選択可能な組み合わせを求める上で必要な複数の制約条件の組を構成する。さらに、旅行計画作成サーバの目的関数構成手段が、本システムによって自動的に作成される旅行計画の特性を表す変数を用いて目的関数を構成する。これらの制約条件及び目的関数は、利用可能リストの１つ又は複数のサービスを旅行期間内の１つ又は複数のスロットに割り付けるか又は割り付けないかを定めるための決定変数を用いて作成される。次いで、旅行計画作成サーバの旅行計画作成手段が、制約条件の下で目的関数を最適化又は近似最適化する選択可能なサービスの組み合わせを、混合整数計画法に基づく最適化手法を用いて求め、そのようにして求めたサービスの各々を旅行期間内のスロットの各々に割り付けることによって、最適化又は近似最適化した旅行計画を作成する。こうして作成された旅行計画は、旅行業者データと共に、旅行計画作成サーバの旅行計画提供手段によって、インターネットなどの通信網を介して旅行者が使用する端末に送られる。
【００３８】
利用可能リスト作成手段の後に、以下のように拡大利用可能リストの作成が行われる場合がある。例えば、ある旅行業者が、又は複数の旅行業者が提携して、ハイキングとバーベキューを組み合わせて提供するといったように、１つのサービスで複数のアクティビティが提供されることがある。このようなサービスは、複合サービスという。この場合には、旅行計画作成サーバの拡大利用可能リスト作成手段が、作成された利用可能リスト内のその複合サービスを、各々が１つのアクティビティを含む複数の新たなサービス（以下、「補助サービス」という）に分割し、元の利用可能リストの複合サービスに関するデータを複数の補助サービスのデータに置換したリスト（拡大利用可能リスト）を作成する。分割前の元の複合サービスと分割後の複数の補助サービスとの関係、及び、分割後の複数の補助サービス相互間の関係は、後述する方法で作成される関係データを用いて記述される。関係データの作成は、旅行計画作成サーバの拡大利用可能リスト作成手段によって行われる。こうして作成された拡大利用可能リスト及び関係データは、その後の制約条件作成、目的関数作成、及び旅行計画作成の際に用いられることになる。
【００３９】
また、例えば、朝食後から夕食前までスキーを行う場合など、１つのアクティビティを複数のスロットにわたって提供するサービスもある。この場合には、旅行計画作成サーバの拡大利用可能リスト作成手段は、利用可能リスト又は拡大利用可能リスト内のそのサービスを、各々が１つのスロットの時間幅以下の必要時間を有する複数の補助サービスに分割し、元のサービスに関するデータを複数の補助サービスのデータに置換した拡大利用可能リストを作成する。すなわち、複数のスロットにわたって提供される元のサービスは、複数の補助サービスからなる複合サービスとなる。この場合も同様に、分割前の元の複合サービスと分割後の複数の補助サービスとの関係、及び、分割後の複数の補助サービス相互間の関係は、後述する方法で作成される関係データを用いて記述される。関係データの作成は、旅行計画作成サーバの拡大利用可能リスト作成手段によって行われる。こうして作成された拡大利用可能リスト及び関係データは、その後の制約条件作成、目的関数作成、及び旅行計画作成の際に用いられることになる。
【００４０】
旅行計画作成を希望している旅行者が、端末に送信され表示された旅行計画を確認し、その旅行計画を変更又は修正する必要があると判断した場合には、旅行者は、端末から旅行計画の修正又は変更を行うことができる。旅行計画作成サーバは、旅行者からの旅行計画の修正又は変更の要求及びそれに必要なデータを受信すると、現在の旅行計画を修正又は変更する処理を実行し、新たな旅行計画を端末に送信する。この処理は、旅行者が満足する旅行計画が作成されるまで繰り返される。旅行者が、作成された旅行計画に満足した場合には、その旨は、旅行者が使用する端末から入力されて旅行計画作成サーバに送信され、旅行計画作成サーバは、最終的な旅行計画と、該旅行計画に含まれる各々のサービスを予約するのに必要な情報とを、端末に送信する。なお、旅行者から入力された旅行条件では旅行計画が作成できない場合には、旅行計画作成サーバは、旅行条件を指定し直すよう促すメッセージを端末に送信する。
【００４１】
３．利用可能リスト作成方法
以下に、図３〜図２３を参照して、本発明の１つの実施形態に係る旅行計画作成サーバが旅行計画を作成する処理を詳細に説明する。以下に説明される処理は、旅行計画作成サーバのＣＰＵが、コンピュータを旅行計画作成サーバ内の手段の各々として機能させるためのコンピュータ・プログラムを読み込んで順次実行することによって、実現される。図３〜図１０は、旅行計画作成サーバの利用可能リスト作成手段が利用可能リストを作成する手順、及び作成される利用可能リストを示す。利用可能リストは、利用可能リスト作成手段が、旅行期間表を作成し、旅程表を作成し、アクティビティ表を作成した上で、これらのデータを用いて作成する。
【００４２】
（１）旅行期間表の作成
図３は、旅行者が入力した旅行開始日及び旅行終了日から、旅行期間の日付と曜日とを対応させた旅行期間表を作成するための処理である。処理は、利用可能リスト作成手段が、旅行者によって端末から入力され旅行条件データ取得手段によって取得された旅行条件データから、旅行開始日及び旅行終了日を取得する（ステップ３０１）ことで開始する。利用可能リスト作成手段は、取得した旅行開始日を旅行期間の最初の日付として設定する（ステップ３０２）。利用可能リスト作成手段は、設定された最初の日付を旅行終了日と比較し（ステップ３０３）、その日付が旅行終了日より前であるか又は旅行終了日と同日の場合には、オペレーション・システムのカレンダー機能を利用して曜日を取得する（ステップ３０４）。次いで、利用可能リスト作成手段は、旅行期間の日付と曜日とを対応付けた旅行期間データを作成し（ステップ３０５）、日付を１日進めて（ステップ３０６）、処理はステップ３０３に戻る。以上のステップを、日付が旅行終了日と同日になるまで繰り返し、利用可能リスト作成手段は、日付が旅行終了日を越えた場合（ステップ３０３）には、それまでに作成した旅行期間データを順次格納した旅行期間表を作成し（ステップ３０７）、処理は終了する（ステップ３０８）。図３のフロー・チャートの処理を実行することによって、旅行期間の日付と曜日とを対応させたデータである旅行期間表が全旅行期間にわたって作成され、データベースに格納される。
【００４３】
（２）旅程表の作成
図４は、旅行期間内の複数のスロットについて、複数のスロットを特定するスロット・コードと、そのスロットのスロット・タイプと、そのスロットの開始時刻及び終了時刻とを対応させた旅程表を作成するための処理である。処理は、利用可能リスト作成手段が、旅行条件データ取得手段によって取得された旅行条件データから、旅行開始日時及び旅行終了日時を取得する（ステップ４０１）ことで開始する。次いで、利用可能リスト作成手段は、図３の処理で作成された旅行期間表から日付単位で旅行期間データを読み込み（ステップ４０２）、さらにデータベースからスロット表を取得する（ステップ４０４）。このスロット表は、図５に示すように、行ごとに、Ａ〜Ｈまでの記号で表されるスロット・タイプと、早朝、朝食、又は午前などといった、各スロットの特性を表すスロット特性と、各スロットの開始時刻及び終了時刻とが関連付けて格納されている関連付けデータであり、これらのデータは、システム管理者によって予め任意に設定され、システム管理者用の端末から入力される。すなわち、システム管理者は、スロットの各々の開始時刻及び終了時刻をどの時刻に設定するか（これによって、１日２４時間が幾つのスロットに分けられるかが決定される）、スロットの各々の記号（スロット・タイプ）をどのように表すか、及びスロットの各々に付与する特性をどのように表すか、といった事項を任意に設定し、これらの事項を表した図５に示されるスロット属性データをシステム管理者用の端末から入力する。入力されたデータは、データベースに予め格納される。スロット・タイプの数（すなわち、スロットの数）、スロット特性、及び（開始時刻及び終了時刻によって決まる）時間幅は、図５に示す例に限るものではなく、例えば、１日を６つの時間帯（すなわちスロット）に分割して各々の時間帯のスロット・タイプをＡ〜Ｆとし、スロット特性を、それぞれ朝食、午前、昼食、午後、夕食、及び夜間とし、スロットの時間幅を、それぞれ２時間、３時間、２時間、４時間、２時間、及び１１時間とすることもできる。また、各々のスロットには、複数のスロット特性を付与してもよい。例えば、午前９時から午前１０時までのスロットに、「朝食」及び「午前」の２つのスロット特性を付与し、旅行者がいずれかを選択できるようにすることも考えられる。ステップ４０４のデータ取得は、このスロット表の行単位で行われる。
【００４４】
次に、利用可能リスト作成手段は、旅行開始日時と、旅行期間データの日付と、取得したスロット表とを用いて、旅行期間データの最初の日付に対応する各スロットのスロット・タイプ、開始時刻、及び終了時刻のデータを編集テーブルに設定し（ステップ４０６）、ステップは４０４に戻る。最初の日付のすべてのスロットについて、ステップ４０４からステップ４０６までを繰り返し、最初の日付のすべてのスロットに対する処理が終了すると（ステップ４０５）、処理はステップ４０２に戻り、利用可能リスト作成手段は、旅行期間データの次の日付を読み込む。ステップ４０２からステップ４０６を繰り返し、旅行期間データのすべての日付について処理が終了すると（ステップ４０３）、利用可能リスト作成手段は、編集テーブルから、それまでに作成した旅程データを順次格納した旅程表を作成し（ステップ４０７）、処理は終了する（ステップ４０８）。図４のフロー・チャートの処理を実行することによって、旅行期間のスロットを特定するスロット・コードと、図５のスロット表の例の場合にはＡ〜Ｈまでのスロット・タイプと、各スロットの開始時刻及び終了時刻とを関連付けた旅程表が作成される。
【００４５】
（３）アクティビティ表の作成
図６は、旅行者が入力した旅行条件データをアクティビティごとにまとめ、各々のアクティビティをその適合スロット・タイプと対応させたアクティビティ表を作成するための処理である。処理は、利用可能リスト作成手段が、旅行者が入力した旅行条件データを取得する（ステップ６０１）ことで開始する。取得される旅行条件データは、旅行者が旅行期間内に実施することを希望するすべてのアクティビティを含む。次いで、利用可能リスト作成手段は、旅行条件データから取得したアクティビティ情報をアクティビティごとに読み込み（ステップ６０２）、後述するアクティビティ−スロット表から、ステップ６０２で読み込んだアクティビティに適合する１つ又は複数の適合スロット・タイプを取得する（ステップ６０４）。
【００４６】
アクティビティ−スロット表は、図７に示すように、行ごとに、アクティビティを特定するアクティビティ・コードと、各々のアクティビティの名称と、各々のアクティビティを実施するのに適した（又は、実施することが可能な）適合スロットのスロット・タイプとが関連付けて格納されている関連付けデータであり、これらのデータは、システム管理者によって予め設定され、システム管理者用の端末から入力され、、データベースに予め格納される。適合スロット・タイプは、アクティビティの特性によって決められるものであり、例えば、バーベキューは、早朝又は朝食時に行うことは考えにくく、昼食又は夕食として実施されるのが適しており、この場合には、バーベキューの適合スロット・タイプは、昼食又は夕食のスロットを表すＤ又はＦとなる。
【００４７】
次いで、利用可能リスト作成手段が、ステップ６０２で読み込んだアクティビティについて、アクティビティ・コードと、アクティビティ名称と、適合スロット・タイプと、後述する絞込条件とを含むアクティビティ・データを作成（ステップ６０５）した後、処理は６０２に戻り、利用可能リスト作成手段は次のアクティビティ情報を読み込む。ステップ６０２からステップ６０５までを繰り返し、取得したアクティビティ・コードのすべてについてアクティビティ・データが作成されると（ステップ６０３）、利用可能リスト作成手段は、作成されたアクティビティ・データを順次格納したアクティビティ表を作成し（ステップ６０６）、処理は終了する（ステップ６０７）。図６の処理を実行することによって、旅行者が入力した旅行条件データから、旅行者が旅行期間内に実施することを希望するすべてのアクティビティについて、その名称と、適合スロット・タイプと、絞込条件とが関連付けられて整理されたアクティビティ表が作成される。
【００４８】
（４）利用可能リストの作成
図８は、図３、図４、及び図６の処理で作成された旅行期間表、旅程表、及びアクティビティ表を用いて利用可能リストを作成するための処理のフロー・チャートである。処理は、利用可能リスト作成手段が、旅行期間表、旅程表、及びアクティビティ表を取得することで開始する（ステップ８０１）。次いで、利用可能リスト作成手段は、アクティビティ表から絞込条件を読み込む（ステップ８０２）。この絞込条件は、旅行者が各々のアクティビティについて指定した、優先度、指定時間、実施回数、実施地域、及びその他の絞込情報に関するデータである。ここで、「優先度」は、旅行者が各々のアクティビティについて指定する情報であり、旅行者が希望するすべてのアクティビティが旅行期間内に収まらない場合に、どのアクティビティを優先して旅行計画に組み込むかを定めるものである。本実施形態においては、優先度は、「必須」及び「二次」の２分類から選択して旅行者が指定するが、優先度の分類は２分類に限定されるものではなく、３分類以上とすることもできる。優先度が「必須」のアクティビティは、実施回数分が必ず旅行計画に組み込まれ、優先度が「二次」のアクティビティは、優先度が「必須」のアクティビティを組み込んだ後の旅行日程に組み込むことができる範囲内で、実施回数以下の回数が旅行日程に組み込まれることになる。「指定時間」は、旅行者が各々のアクティビティについて指定する情報であり、旅行者がそのアクティビティに費やすことが可能な（又は、費やすことを希望する）時間を定めるものである。「実施回数」は、旅行者が各々のアクティビティについて指定する情報であり、旅行者が、旅行期間内に希望するアクティビティの各々をそれぞれ何回ずつ実施することを希望するかを定めるものである。「実施地域」は、旅行者が各々のアクティビティについて指定する情報であり、旅行者がそのアクティビティを実施したい地域を定めるものである。「その他の絞込情報」は、例えば、ホテルの部屋のタイプ（例えば、禁煙室か喫煙室かなど）などといったその他の条件を指定する情報である。
【００４９】
次いで、利用可能リスト作成手段は、サービス−アクティビティ表から、旅行者が指定したアクティビティを含むサービスのデータを取得する（ステップ８０４）。このサービス−アクティビティ表は、データベースに予め格納されており、図９に示すように、サービスを特定するサービス・コードと、アクティビティを特定するアクティビティ・コードと、アクティビティの必要時間と、サービス対象単位（すなわち、サービスの対象となる１グループの人数）及びグループ数（すなわち、サービスが受入可能なグループ数）と、後述するサービス・タイプと、アクティビティの開始時刻及び終了時刻と、サービスの価格と、サービスの開始日、終了日、及び休日と、旅行者が入力するその他の絞込情報と照合するのに用いるその他の絞込条件と、実施地域と、が関連付けて格納されている関連付けデータである。これらのデータは、予め旅行業者によって端末から入力され、インターネットなどの通信網を介して、直接データベースに格納される。あるいは、これらのデータは、旅行業者によって端末から入力され、インターネットなどの通信網を介して旅行計画作成サーバに送られ、該旅行計画作成サーバの旅行情報データ取得手段（図示せず）において取得された後、データベースに格納されるようにしてもよい。さらに、これらのデータは、旅行業者によって何らかの手段でシステム管理者に提供された後、システム管理者によってシステム管理者用の端末から入力されるようにしてもよい。
【００５０】
サービス−アクティビティ表のサービス・タイプは、そのサービスが、提供されるスケジュールが決まっているものであるかどうかを表すデータである。本実施形態では、旅行業者が提供するサービスは、以下の３つのタイプに分類する。１つは、例えば、週２回、午後２時から午後４時までの間に実施されるラフティングのように、提供されるアクティビティのスケジュール、すなわち日付、開始時刻、及び終了時刻が旅行業者によって定められているサービスである。このようなサービスのサービス・タイプは、「ｓ」とする。ｓタイプのサービスについては、提供されるスケジュールが異なるものはすべて異なるサービスとして考慮されることになる。次に、例えば美術館でガイドを付けずに希望する時間だけ鑑賞する場合のように、提供を受けるのに「必要な時間幅」（必要時間）が旅行業者によって指定されていないアクティビティを含むサービスである。このようなサービスのサービス・タイプは、「ａ１」とする。スキー、温泉、宿泊なども、タイプａ１のサービスと考えられる（但し、本実施形態においては、宿泊はアクティビティを伴わない特殊なａ１サービスとして扱う。すなわち、必要時間は、スロット特性「睡眠」に該当するスロット・タイプＨ（図５参照）全体である）。ａ１タイプのサービスに含まれるアクティビティの必要時間は、旅行業者によって端末から「標準必要時間」、すなわちそのアクティビティを実施するのに「適した時間幅」として入力されるが、このタイプのサービスが旅行計画に組み込まれた場合には、旅行者がこの標準必要時間を自由に書き換えることができるものとする。最後は、例えば美術館における１時間ガイド付きツアーなどのように、スケジュールが旅行業者によって定められておらず、随時提供を受けることはできるが、必要時間が旅行業者によって指定されているアクティビティを含むサービスである。このようなサービスのサービス・タイプは、「ａ２」とする。ａ２タイプのサービスの必要時間は、旅行業者によって端末から入力される。ａ１タイプ及びａ２タイプのサービスに含まれるアクティビティの開始時刻及び終了時刻には、該アクティビティの提供が開始される時刻、例えば該アクティビティを提供する旅行業者の営業開始時刻と、該アクティビティの提供が終了する時刻、例えば該アクティビティを提供する旅行業者の営業終了時刻とが設定される。
【００５１】
ステップ８０５において、利用可能リスト作成手段は、旅行者が希望するすべてのアクティビティについて、そのアクティビティを含むサービスのうち、旅行者が指定した絞込条件に適合するサービスを絞り込む。例えば、旅行者が入力した人数が５人である場合には、ステップ８０２において利用可能リスト作成手段が、サービスの受入可能人数が少なくとも５人以上であるという条件を読み込み、ステップ８０５において、旅行期間内に５人以上の人数の受入が可能なサービスを絞り込む。あるいは、例えば旅行者が、サービス当たり１万円以下の費用という条件を入力した場合には、利用可能リスト作成手段は、費用が１万円以下のサービスを絞り込む。なお、指定時間は、ｓタイプのサービス及びａ２タイプのサービスに対しては、旅行者が許容できる最大の時間として絞り込みに利用される。すなわち、ｓタイプのサービス及びａ２タイプのサービスの場合、そのサービスに含まれるアクティビティの必要時間が指定時間以下のサービスが、絞込条件に適合するものとなる。それに対して、ａ１タイプのサービスについては、そのサービスの営業時間内であれば旅行者はいつでもそのサービスを受けることができるため、指定時間に基づく絞り込みは行わない。なお、営業時間は、旅行情報データに含まれていることは言うまでもない。
【００５２】
利用可能リスト作成手段は、このようにして絞り込んだ複数のサービスからサービス・データを作成し（ステップ８０６）、読み込むべき絞込条件がなくなると（ステップ８０３）、利用可能リストを作成して（ステップ８０７）、処理は終了する（ステップ８０８）。
【００５３】
以上の処理を経て、図１０に示すような利用可能リストが作成されることになる。利用可能リストは、旅行者が希望する旅行期間内に実施することが可能なすべてのサービスについて、サービスを特定するサービス・コードと、各々のサービスで提供されるアクティビティを特定するアクティビティ・コードと、アクティビティを実施するのに適した適合スロット・タイプと、サービスの対象単位及びグループ数と、サービス・タイプと、サービスに含まれるアクティビティの開始時刻及び終了時刻と、アクティビティの必要時間と、サービスの価格と、アクティビティの実施枠と、アクティビティの優先度と、アクティビティの指定時間と、アクティビティの実施回数と、アクティビティの実施地域とが関連付けられたデータである。ここで、「実施枠」は、旅行者が各々のアクティビティについて指定する情報であり、そのアクティビティを旅行期間中の何日目のどの時間帯に実施するかを定めるものである。なお、この利用可能リストの必要時間には、ｓタイプのサービスの場合は、該サービスに含まれるアクティビティの開始時刻及び終了時刻から計算される時間が設定され、ａ１タイプのサービスの場合は旅行業者によって端末から入力された、アクティビティの標準必要時間が設定され、ａ２タイプのサービスの場合は旅行業者によって端末から入力された、アクティビティの必要時間が設定される。
【００５４】
４．拡大利用可能リスト作成方法
ところで、前述の通り、例えば、ある旅行業者が又は複数の旅行業者が提携してトレッキングと昼食とを組み合わせて提供するといったように、１つのサービスで複数のアクティビティが提供される場合がある。上述の処理で作成された利用可能リストにこのような複合サービスが含まれる場合には、拡大利用可能リスト作成手段が、利用可能リストのその複合サービスを、各々が１つのアクティビティを含む複数の補助サービスに分割し、元の利用可能リストの複合サービスに関するデータを複数の補助サービスのデータに置換する。また、例えば、朝食後から夕食前までスキーを行うといったように、１つのアクティビティを複数のスロットにわたって提供するサービス（以下、「長大サービス」という）もある。このような場合も、拡大利用可能リスト作成手段は、利用可能リスト内のその長大サービス（この場合も同様に「複合サービス」として扱う）を、各々が１つのスロットの時間幅以下の必要時間を有する複数の補助サービスに分割し、元の利用可能リストの長大サービスに関するデータを複数の補助サービスのデータに置換する。以上のような処理を図１１〜図１３に示すフロー・チャートによって行うことによって、元の利用可能リストから図１４に示す拡大利用可能リストが作成される。なお、上述のように、拡大利用可能リストは、利用可能リストの複合サービスに関するデータを複数の補助サービスに関するデータに置換したものであり、図１０に示す利用可能リストのデータ項目と図１４に示す拡大利用可能リストのデータ項目は、拡大サービス・コード及びスロット・タイプを除いて同じものとすることができる。しかしながら、分かりやすくするため、図１４においては、図１０のデータ項目のうち、後の制約条件構成ステップなどにおいて利用するデータ項目のみを抽出して記載している。
【００５５】
（１）サービス−スロット表の作成
図１１は、複合サービスの分割及び拡大利用可能リストの作成に先立って、各々のサービスのサービス・コードと、該サービスに含まれるアクティビティの後述する実効スロットとを関連付けるサービス−スロット表を作成するための処理である。また、図１２及び図１３は、拡大利用可能リストを作成し、元のサービスと補助サービスとの関係及び補助サービス間の関係データを作成するための処理である。図１１においては、処理は、拡大利用可能リスト作成手段が、図５に示すスロット表、及び、図１０に示す利用可能リストを取得することで開始する（ステップ１１０１）。次いで、拡大利用可能リスト作成手段は、利用可能リストのサービス毎に該サービスに関するデータを読み込む（ステップ１１０２）。拡大利用可能リスト作成手段は、読み込んだサービス・データに含まれる開始時刻及び終了時刻とスロット表とから、該サービスの開始スロット及び終了スロットを決定し（ステップ１１０４）、決定された開始及び終了スロットから、ステップ１１０５〜ステップ１１０７に従って実効スロット候補を決定する。
【００５６】
ここで「実効スロット」とは、利用可能リスト内の各々のサービスに含まれるアクティビティの適合スロットのうち、旅行業者がそのサービスを提供する時間帯に含まれるスロットであり、「実効スロット・タイプ」は、実効スロットに付与される、例えばＡ〜Ｈの記号である。例えば、利用可能リスト内のあるサービスについて、そのサービスに含まれるアクティビティが提供される適合スロットのスロット・タイプがＣ（午前）及びＥ（午後）、サービス・タイプがａ１、旅行期間が例えば１０月１５日１２：００から１０月１８日１８：００であるとする。この場合、旅行者が該サービスに含まれるアクティビティを１０月１５日の午後（すなわち、対応するスロット・タイプはＥである）に実施することを指定し、その時間帯に該サービスの提供が可能なときは、そのサービスの実効スロット・タイプはＥ（午後）となる。同じ場合に、旅行者がそのサービスに含まれるアクティビティを１０月１６日に実施することを指定し、その時間帯に該サービスの提供が可能なときは、実効スロット・タイプはＣ（午前）及びＥ（午後）である。さらに同じ場合に、旅行者が実施を希望する日の指定をしていないときは、そのサービスに含まれるアクティビティの実効スロット・タイプは、１５日のＥ、１６日、１７日、及び１８日のＣ及びＥの、合わせて７個となる。或いは、例えば、利用可能リスト内のあるサービスについて、含まれるアクティビティの開始時刻が９：００、終了時刻が１６：００、サービス・タイプがｓの場合には、そのサービスに含まれるアクティビティの開始時刻と終了時刻との間にあるスロット・タイプ、すなわち、Ｃ（午前）、Ｄ（昼食）、及びＥ（午後）からなる集合が実効スロット・タイプとなる。さらに、例えば、旅行者があるアクティビティを夜間（すなわち、対応するスロット・タイプはＧである）に実施することを指定したときは、適合スロット・タイプがＧであるそのアクティビティを含むサービス、及び／又は、開始時刻と終了時刻がスロット・タイプＧのスロットに含まれる該アクティビティを含むサービスが利用可能リストに追加され、この場合には、該サービスの実効スロット・タイプはＧとなる。
【００５７】
ステップ１１０４において開始スロット及び終了スロットを決定した後、拡大利用可能リスト作成手段は、そのサービスのサービス・タイプが、ｓタイプであるか、ａタイプ（ａ１タイプ又はａ２タイプ）であるかを判断する（ステップ１１０５）。そのサービスがｓタイプの場合は、スケジュールが決まっているため、拡大利用可能リスト作成手段は、開始スロット及び終了スロットのスロット・タイプも含めて開始スロットと終了スロットとの間にあるスロット・タイプからなる集合を求め、そのスロット・タイプ集合を実効スロット・タイプとして取得する（ステップ１１０７）。一方、そのサービスがａタイプの場合は、拡大利用可能リスト作成手段は、開始スロット、すなわち該サービスを提供する旅行業者の営業開始時刻を含むスロットと、終了スロット、すなわち該サービスを提供する旅行業者の営業終了時刻を含むスロットとの間のスロット・タイプを求め、求めたスロット・タイプのうち、連続するスロット・タイプからなる集合で、該サービスに含まれる各アクティビティに対応する位置のスロット・タイプがその適合スロット・タイプと一致するものを実効スロット・タイプとして取得する（ステップ１１０６）。ステップ１１０６及びステップ１１０７の処理の結果、実効スロットが存在しない場合（ステップ１１０８）には、処理はステップ１１０２に戻り、拡大利用可能リスト作成手段は、次のサービス・データを読み込む。実効スロットが存在する場合には、そのサービスのサービス・コードと、該サービスの実効スロット・タイプとを関連付けたサービス−スロット・データを作成し（ステップ１１０９）、次のサービス・データを読み込む（ステップ１１０２）。拡大利用可能リスト作成手段は、ステップ１１０２からステップ１１０９を繰り返し、取得した利用可能リストのすべてのサービスについて実効スロット・タイプを取得すると（ステップ１１０３）、作成されたサービス−スロット・データからサービス・スロット表を作成し（ステップ１１１０）、処理は終了する。なお、実施可能リストに複合サービスが含まれない場合においても、同様の処理によって実効スロット・タイプが取得されることになる。
【００５８】
ところで、ａタイプのサービスの場合、ステップ１１０６において複数の実効スロット・タイプ集合が作成されることがある。例えば、３つのアクティビティを含む複合サービスについて、第１のアクティビティの適合スロット・タイプがＡ〜Ｃ、第２のアクティビティの適合スロット・タイプがＣ〜Ｅ、第３のアクティビティの適合スロット・タイプがＣ〜Ｇの場合を考える。第１のアクティビティの開始時刻をスロットＡの途中からとし、続く第２及び第３のアクティビティが共にそれぞれの適合スロットの範囲に収まり、第３のアクティビティの終了時刻がスロットＧに含まれる場合には、実効スロット・タイプ集合は、｛Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ｝である。次に、第１のアクティビティをスロットＢから開始するものとし、続く第２及び第３のアクティビティが共にそれぞれの適合スロットの範囲に収まり、第３のアクティビティの終了時刻がスロットＧに含まれる場合には、実効スロット・タイプ集合は、｛Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ｝である。しかしながら、第１のアクティビティをスロットＣから開始するものとし、第１のアクティビティがスロットＣ内には収まらずスロットＤまでまたがる場合には、スロットＤは第１のアクティビティの適合スロット・タイプではないため、スロットＣから開始する実効スロット・タイプ集合は作成できない。したがって、このような場合の実効スロット・タイプ集合は二組である。このように複数の実効スロット・タイプ集合が作成される場合には、作成された実効スロット・タイプ集合の個数だけサービス・コードを複製し、各々のサービス・コードに１つの実効スロット・タイプ集合が対応するようにする。なお、すべてのサービスに含まれるアクティビティが１つのスロット内に収まる場合には、この処理は不要である。
【００５９】
（２）拡大利用可能リスト及び補助サービス間関係データの作成
図１２は、複数のアクティビティを含む１つ又は複数の複合サービスを、各々が１つのアクティビティを含む複数の補助サービスに分割するための処理である。図１２においては、処理は、拡大利用可能リスト作成手段が、図１０に示す利用可能リストと、図１１の処理によって作成されたサービス−スロット表とを取得することで開始する（ステップ１２０１）。次いで、拡大利用可能リスト作成手段は、取得したサービス−スロット表から最初のサービス・コードを読み込む（ステップ１２０２）。ステップ１２０４において、拡大利用可能リスト作成手段は、取得済みの利用可能リストから最初のサービス・データを読み込み、該サービス・データのサービス・コードによって特定されるサービスが、複合サービス（すなわち、複数のアクティビティを含むサービス）又は単純サービス（すなわち、単一のアクティビティのみを含むサービス）のいずれであるかを判断する（ステップ１２０５）。この判断は、拡大利用可能リスト作成手段が、利用可能リストから読み込んだサービス・データにおいて、サービスのサービス・コードが複数のアクティビティ・コードと関連付けられているかどうかを判定することによって行われる。そのサービスが複合サービスではない場合には、拡大利用可能リスト作成手段は、そのサービスのデータを、利用可能リストの適合スロット・タイプを実効スロット・タイプに置き換えて、拡大利用可能リストに追加する（ステップ１２１３）。
【００６０】
そのサービスが複合サービスである場合には、拡大利用可能リスト作成手段は、次に、該サービスのサービス・タイプが、ｓタイプであるかａタイプであるかを判断する（ステップ１２０６）。そのサービスがｓタイプである場合には、拡大利用可能リスト作成手段は、そのサービスを、スケジュールに応じて、各々が１つのアクティビティを含む連続する複数の補助サービスに分割し、各々の補助サービスに含まれるアクティビティの開始時刻及び終了時刻から、各補助サービスの必要時間を算出する（ステップ１２０７）。各々のアクティビティの開始時刻及び終了時刻は、事前に旅行業者によって端末から入力され、データベースに格納されている。
【００６１】
ステップ１２０６に戻り、サービス・コードによって特定されるサービスがａタイプである場合には、拡大利用可能リスト作成手段は、さらにそのサービスがａ１タイプ又はａ２タイプのいずれであるかを判断する（ステップ１２０８）。サービスがａ２タイプである場合には、拡大利用可能リスト作成手段は、そのサービスを、各々が１つのアクティビティを含む連続する複数の補助サービスに分割し、各々の補助サービスに含まれるアクティビティの必要時間を各々の補助サービスの提供に必要な時間幅、すなわち、補助サービスの必要時間として設定する（ステップ１２０９）。サービスがａ２タイプではない場合、すなわちａ１タイプである場合には、拡大利用可能リスト作成手段は、そのサービスを、各々が１つのアクティビティを含む連続する複数の補助サービスに分割し、各々の補助サービスの必要時間を以下のように設定する（ステップ１２１０）。各々の補助サービスに含まれるアクティビティについて、そのアクティビティに費やすことを希望する（又は、費やすことが可能な）時間幅である指定時間が旅行者によって設定されている（すなわち、旅行条件データに含まれている）ときは、拡大利用可能リスト作成手段は、その指定時間と、該アクティビティを提供する旅行業者の営業時間の長さとを比較し、より短い方を補助サービスの必要時間として設定する。各々の補助サービスに含まれるアクティビティについて、指定時間が旅行者によって設定されていない（すなわち、旅行条件データに含まれていない）ときは、拡大利用可能リスト作成手段は、旅行業者によって入力された標準必要時間、すなわち該アクティビティを実施するのに適した時間を、補助サービスの必要時間として設定する。
【００６２】
ステップ１２０７、１２０９、又は１２１０において補助サービスの作成及び必要時間の設定が終了した後、拡大利用可能リスト作成手段は、１つの複合サービスを分割して生成された複数の補助サービスのデータを、元の複合サービスのデータと置換して、拡大利用可能リストに追加する（ステップ１２１１）。ここで、複合サービスを分割して得られる複数の補助サービスは、最終的に旅行計画を作成する段階で元のサービスに復元されなければならないこと、及び、１つの複合サービスを分割して作成される複数の補助サービスは、一括して旅行計画に組み込まれなければならないことから、元の複合サービスと補助サービスとの関係、及び、複数の補助サービス同士の関係を記述しておく必要がある。したがって、拡大利用可能リスト作成手段は、この時点で、そのための関係データを作成する（ステップ１２１２）。この関係データは、例えば、１つの複合サービスが、各々が１つのアクティビティを含む３つの補助サービスに分割された場合、拡大利用可能リスト作成手段が、最初に実施されるアクティビティを含む補助サービス（以下「根サービス」という）のサービス・コードとして、元の複合サービスのサービス・コード（例えば、１００）を付与し、２番目及び３番目の補助サービスのサービス・コードとして、「元の複合サービスのサービス・コード−２」（例えば、「１００−２」）及び「元の複合サービスのサービス・コード−３」（例えば、「１００−３」）を付与し、これらの関係を関係データ表として記述することによって作成することができる。なお、補助サービスのサービス・コードの付け方はこれらに限るものではなく、元の複合サービスと補助サービスとの関係及び補助サービス同士の関係を特定できるものであれば良い。拡大利用可能リスト内の各々のサービスには、サービスごとに新たに拡大サービス・コードが付与される。
【００６３】
以上の処理を行った後、ステップは１２０２に戻り、拡大利用可能リスト作成手段は、サービス−スロット表から次のサービス・コードを読み込む。サービス・スロット表のすべてのサービス・コードについて、ステップ１２０４〜ステップ１２１２を繰り返し、読み込むべきサービス・コードがなくなったら（ステップ１２０３）、処理は図１３のステップ１２１４に移る。図１３は、複数のスロットにまたがる１つ又は複数の長大サービスを、各々が１つのスロットの時間幅以下の必要時間を有する複数の補助サービスに分割する処理である。ステップ１２１４において、拡大利用可能リスト作成手段は、これまでに作成された拡大利用可能リストから最初の拡大サービス・データ（拡大サービス・コード及びそれに関連付けられたデータ）を読み込み、そのサービスが長大サービスであるかどうかを判断する（ステップ１２１６）。この判断は、そのサービスの実効スロットの組のうちの先頭スロットの時間幅と、そのサービスの必要時間とを比較することによって行われ、必要時間が先頭スロットの時間幅より長い場合には、そのサービスは長大スロットであると判断される。サービスが長大サービスではない場合には、ステップは１２１４に戻り、拡大利用可能リスト作成手段は、次の拡大サービス・データを読み込む。
【００６４】
サービスが長大サービスである場合には、次に、拡大利用可能リスト作成手段は、該サービスのサービス・タイプが、ｓタイプであるかａタイプであるかを判断する（ステップ１２１７）。そのサービスがｓタイプである場合には、拡大利用可能リスト作成手段は、該サービスを、該サービスに含まれるアクティビティの開始時刻を含むスロットに対応する補助サービスと、終了時刻を含むスロットに対応する補助サービスと、その両スロット間の複数のスロットに対応する複数の補助サービスとに分割し、各々のスロットの時間幅を、そのスロットに対応する補助サービスの必要時間として設定する（ステップ１２１８）。ここで、アクティビティの開始時刻が含まれるスロットに対応する補助サービスの必要時間は、該開始時刻から、該開始時刻が含まれるスロットの終了時刻までの時間幅が設定され、終了時刻が含まれるスロットに対応する補助サービスの必要時間は、該終了時刻が含まれるスロットの開始時刻から該終了時刻までの時間幅が設定される。したがって、開始時刻が含まれるスロットに対応する補助サービスの必要時間と、終了時刻が含まれるスロットに対応する補助サービスの必要時間は、それぞれのスロットの時間幅より短くなる場合がある。
【００６５】
そのサービスがａタイプである場合には、拡大利用可能リスト作成手段は、以下のように処理を行う（ステップ１２１９及び１２２０）。拡大利用可能リスト作成手段が、その長大サービスの実効スロットの組のうちの最初の実効スロットが該サービスを提供する旅行業者の営業開始時刻を含むスロットと等しいと判断したときは、拡大利用可能リスト作成手段は、該営業開始時刻から該最初の実効スロットの終了時刻までを最初の補助サービスとし、該営業開始時刻から該終了時刻までの時間幅をその最初の補助サービスの必要時間として設定する。次いで、拡大利用可能リスト作成手段は、順次、その長大サービスの実効スロットに対応する補助サービスを作成していき、各々の実効スロットの時間幅を、その実効スロットに対応する補助サービスの必要時間として設定する。最後の実効スロットに対応する補助サービスの必要時間は、最初の補助サービスから最後の実効スロットの直前の実効スロットに対応する補助サービスまでの複数の補助サービスの必要時間の合計を、この長大サービスの必要時間から引いた時間幅を設定する。一方、その長大サービスの実効スロットの組のうちの最初の実効スロットが、該サービスを提供する旅行業者の営業開始時刻を含むスロットより後のスロットであるときには、拡大利用可能リスト作成手段は、該最初の実効スロットに対応する補助サービスを最初の補助サービスとし、該最初の実効スロットの時間幅を該最初の補助サービスの必要時間として設定する。次いで、拡大利用可能リスト作成手段は、順次、その長大サービスの実効スロットに対応する補助サービスを作成していき、各々の実効スロットの時間幅を、その実効スロットに対応する補助サービスの必要時間として設定する。最後の実効スロットに対応する補助サービスの必要時間は、最初の補助サービスから最後の実効スロットの直前の実効スロットに対応する補助サービスまでの複数の補助サービスの必要時間の合計を、この長大サービスの必要時間から引いた時間幅を設定する。
【００６６】
ステップ１２１８〜１２２０を終了した後、１つの長大サービスを分割して生成された複数の補助サービスのデータを、元の長大サービスのデータと置換して、拡大利用可能リストに追加する（ステップ１２２１）。ここで、元の長大サービスを分割して生成された複数の補助サービスのうち、最初に実施される補助サービスを「補助根サービス」という。次いで、拡大利用可能リスト作成手段は、上述のステップ１２１２と同様に、元の複合サービス（すなわち、長大サービス）と補助サービスとの関係、及び、複数の補助サービス同士の関係を記述するための関係データを作成する（ステップ１２２２）。次いで、拡大利用可能リスト作成手段は、ステップ１２１２において作成した関係データから、ここで分割した長大サービスに続く補助サービスに長大なものが存在するかどうかを判断し（ステップ１２２３）、存在する場合には、その補助サービスの拡大サービス・データを読み込み（ステップ１２２４）、ステップ１２１７〜１２２２を繰り返す。ステップ１２１８〜１２２０において分割した長大サービスに補助サービスが存在しない場合には、処理はステップ１２１４に戻り、拡大利用可能リスト作成手段は、次の拡大サービス・データを読み込む。
【００６７】
ステップ１２１７〜１２２４までの処理を繰り返し、読み込むべき拡大サービス・データが無くなったら（ステップ１２１５）処理は終了することになる（ステップ１２２６）が、最終的な拡大利用可能リストが作成された段階で、拡大利用可能リスト作成手段は、該拡大利用可能リストのサービスをランダムに並べ替えることが好ましい（ステップ１２２５）。すなわち、利用可能リスト及び拡大利用可能リストのサービスに関する情報は、図１０及び図１４に示されるように、サービス毎に１つのデータ単位として構成されており、サービスをランダムに並べ替える処理は、リストに含まれる複数のデータ単位を並べ替えることによって行われる。この処理は、混合整数計画問題の解法の多くでは、同等のサービスであれば係数行列の一定の位置にあるサービスが選択されやすい特性があるため、及びモデルを構築する際のサービスの並びはデータベースからの検索結果に依存するため、旅行者からの同じ入力条件に対して作成される旅行計画に組み込まれるサービスが固定的にならないように、拡大利用可能リストのサービスの並び順を無作為に並び替える処理である。こうした処理を行うことによって、旅行者が同じ旅行条件データを入力した場合であっても、その都度異なる旅行計画が作成され、旅行者が当初想像していなかったような旅行を享受できるという利点がある。また、本発明のような支援サービスを実現するためには、データ入力に対する多数の旅行業者の協力が必要であるが、こうしたランダム化処理を行うことによって、各々の旅行業者の提供するサービスが選択される機会の公平性が担保され、旅行業者が支援サービスに参加するためのインセンティブとなるという利点もある。
【００６８】
以上の処理を実行することによって、利用可能リスト内のあるサービスが、複数のアクティビティを提供する複合サービス、及び／又は、複数のスロットにわたる複合サービス（すなわち長大サービス）である場合に、その複合サービスをアクティビティごとに、及び／又は実効スロット・タイプごとに分割し、その結果、サービスの各々に対して、１つのアクティビティと１つ以上の実効スロット・タイプとが対応する拡大利用可能リスト（図１４）が作成されることになる。
【００６９】
５．制約条件構成方法
（１）決定変数の作成
拡大利用可能リストが作成された後、リスト内のサービス（又は補助サービス）の選択可能な組み合わせを求める上での制約条件が作成されることになる。制約条件構成手段が、制約条件作成に先立って、制約条件の作成に用いるための決定変数ｘｉ，ｊを作成する。決定変数ｘｉ，ｊは、拡大利用可能リストの各々の拡大サービスｉについて、各々の拡大サービスｉをスロットｊに割り付けるか又は割り付けないかを定める変数である。なお、これ以降、拡大サービスｉというときは、拡大サービス・コードｉによって特定される拡大サービスを意味し、スロットｊというときは、スロット・コードｊによって特定されるスロットを意味する。あるサービスｉを割り付けることができるスロットｊに該サービスｉを割り付ける可能性がある場合にはｘｉ，ｊが作成され、可能性がない場合にはｘｉ，ｊが作成されない。例えば、拡大サービス・コードが１であるサービスの実効スロット・タイプがＣ（午前）、Ｅ（午後）、又はＧ（夜間）の場合に、旅程表（図１７（ｂ）を参照されたい）において、スロット・タイプＣに対応するスロット・コードが７及び１５であり、スロット・タイプＥに対応するスロット・コードが１及び９であり、スロット・タイプＧに対応するスロット・コードが３及び１１であるときには、決定変数ｘ１，１、ｘ１，３、ｘ１，７、ｘ１，９、ｘ１，１１、及びｘ１，１５が作成される。すなわち、拡大利用可能リストの各々の拡大サービスｉについて、各々の拡大サービスｉを各々のスロットｊに割り付けるかどうかを定めるということは、制約条件構成手段が、拡大利用可能リストに含まれる拡大サービスｉについてのスロットの特性（スロットの特性はスロット・タイプによって特定される）と、旅行期間に含まれるスロットの各々の特性とを比較し、特性が一致するスロットｊがあれば、その拡大サービスｉとスロットｊの対に対応するｘｉ，ｊが作成されることを意味する。このように、各サービスとそのサービスが割り付けられる可能性のある実効スロットとの対にのみ決定変数を定義することによって、すべてのサービスと実効スロットとの任意の組み合わせに対して決定変数を定義する場合と比べて、計算処理の規模が著しく小さくなるという利点がある。なお、ここでは拡大利用可能リストに基づいて説明したが、作成された利用可能リスト（図１０）に複合サービスが含まれない場合には、該利用可能リストを用いて、そのリスト内のサービス（この場合、このサービスは補助サービスではない）の各々について同様の方法で決定変数が作成されることになる。以下の処理においても同様である。
【００７０】
図１５は、決定変数を作成するための処理である。処理は、制約条件構成手段が、拡大利用可能リスト及び旅程表を取得することで開始する（ステップ１５０１）。次いで、制約条件構成手段は、拡大利用可能リストから最初の拡大サービス・データ（すなわち、拡大サービス・コード及びそれに関連付けられたデータ）を読み込み（ステップ１５０２）、さらに旅程表から最初の旅程データ（すなわち、スロット・コード及びそれに関連付けられたデータ）を読み込む（ステップ１５０４）。次に、制約条件構成手段は、読み込んだ最初の拡大サービス・コードに関連付けられたデータの中の実効スロット・タイプと、旅程表から読み込んだ最初のスロット・コードに関連付けられたスロット・タイプとを比較し（ステップ１５０６）、両者が一致する場合には、その拡大サービス・コードとスロット・コードの対に対応する決定変数（例えば、拡大サービス・コードが１、スロット・コードが１の場合には、決定変数ｘ１，１）を作成する（ステップ１５０７）。両者が一致しない場合には、処理はステップ１５０４に戻り（すなわち、決定変数は作成せず）、制約条件構成手段は、旅程表から次の旅程データを読み込む。ステップ１５０４からステップ１５０７を繰り返し、すべての旅程データについて処理を終了（ステップ１５０５）した時点で、制約条件構成手段は、最初の拡大サービス・コードについて決定変数の有無を判断し（ステップ１５０８）、作成された決定変数がない場合には、その拡大サービスを割り付けることができるスロットが存在しないことになるため、その拡大サービスを拡大利用可能リストから除外する（ステップ１５０９）。次いで、ステップは１５０２に戻り、制約条件構成手段は、拡大利用可能リストから次の拡大サービス・コード及びそれに関連付けられたデータを読み込み、ステップ１５０４からステップ１５０９を繰り返す。拡大利用可能リスト内のすべての拡大サービス・コードについてステップ１５０２から１５０９の処理を繰り返した後、処理は終了する（ステップ１５１０）。
【００７１】
ここで、図１６は、旅行条件データにおいて旅行者が指定したアクティビティの実施枠のデータを用いて、図１５において作成した決定変数を絞り込むための処理のフロー・チャートである。この処理を行うのは、図１５の処理で作成された決定変数に該当するサービスうち、旅行者が指定する実施枠に適合しないサービスについて作成された決定変数を削除することによって、計算処理の規模をさらに小さくするためである。処理は、制約条件構成手段が、利用可能リスト及び拡大利用可能リストを取得することで開始する（ステップ１６０１）。次いで、制約条件構成手段は、決定変数を取得する（ステップ１６０２）。制約条件構成手段は、拡大利用可能リストから最初のサービス・データ（拡大サービス・コード及びそれに関連付けられたデータ）を読み込み（ステップ１６０３）、さらに利用可能リストから最初のサービス・データを読み込む（ステップ１６０５）。ここで、制約条件構成手段は、その拡大サービス・コードで特定されるサービスに含まれるアクティビティについて、そのアクティビティを何日目のどの時間帯に実施するかを指定する実施枠のデータがあるかどうかを判定し（ステップ１６０６）、実施枠のデータがあれば、そのデータを用いて不要な決定変数をクリアする（ステップ１６０７）。次いで、処理はステップ１６０３に戻り、制約条件構成手段は、次の拡大サービス・データを読み込む。全ての拡大サービス・データについてステップ１６０３からステップ１６０７が繰り返されると、処理は終了する（ステップ１６０８）。
【００７２】
（２）制約条件の作成
図１９〜図２２は、拡大利用可能リストにリストアップされたサービスの選択可能な組み合わせを求める上での制約条件を作成するための処理である。ここでは、図３〜図１６に示す処理において、図１７（ａ）〜（ｄ）に例示するアクティビティ表、旅程表、サービス−アクティビティ表、及び利用可能リストを用いた結果、図１８に示す例示的な拡大利用可能リストが作成されたものとして、制約条件の作成について説明する。なお、図１７（ａ）〜（ｄ）及び図１８に表示されるデータ項目は、これまで説明した各々の表のデータ項目のすべてではなく一部のみが表示されているが、これは、分かり易くするために、これ以降の処理において最低限必要となるデータのデータ項目のみを抽出して表示しているためである。
【００７３】
図１９は、旅行者が旅行期間内に実施することを希望するアクティビティの実施回数及び優先度に関する制約条件１を作成するための処理である。この制約条件１は、旅行者が希望するあるアクティビティを提供するサービス集合の中の各拡大サービスｉと、そのサービスを割り付けることが可能なすべてのスロットｊに関して、決定変数ｘｉ，ｊの和を計算し、該アクティビティの優先度が必須の場合には、その和が旅行者によって指定された実施回数ｓと等しいことを表す以下の（１）式、
【数１】
0004268973.tif 000002
として表現することができ、該アクティビティの優先度が二次の場合には、その和が旅行者によって指定された実施回数ｓと等しいか又はそれより小さいことを表す以下の（２）式、
【数２】
0004268973.tif 000003
で表現することができる。例えば、拡大サービス・コードが１であるサービス（図１８の例の場合には、アクティビティ「温泉」（図１７（ａ）においてアクティビティ・コード１１によって特定される）を含むサービス）について決定変数ｘ１，１、ｘ１，３、ｘ１，７、ｘ１，９、ｘ１，１１、及びｘ１，１５が作成され、そのサービスの優先度が必須の場合には、（１）式を満たすように決定変数の組み合わせが計算される。その結果、そのサービスは、例えばスロット・コード９のスロット（図１８の例の場合には、スロット・タイプＥ、すなわち「午後」）に割り付けられることになる（すなわち、ｘ１，９＝１、ｘ１，１＝ｘ１，３＝ｘ１，７＝ｘ１，１１＝ｘ１，１５＝０となるため、（１）式を満たしていることになる）。
【００７４】
図１９の処理は、制約条件構成手段が、アクティビティ表と、拡大利用可能リストと、旅程表とを取得することで開始する（ステップ１９０１）。次いで、制約条件構成手段は、アクティビティ表から最初のアクティビティ・データ（アクティビティ・コード及びそれに関連付けられたデータ）を読み込み（ステップ１９０２）、さらに、拡大利用可能リストから最初の拡大サービス・データ（拡大サービス・コードｉ及びそれに関連付けられたデータ）を読み込む（ステップ１９０４）。制約条件構成手段が、ステップ１９０２で読み込んだアクティビティ・コードと、ステップ１９０４で読み込んだ拡大サービス・コードｉに対応するアクティビティ・コードとが一致し、かつ、その拡大サービスが根サービス、補助根サービス、又は単純サービスであると判定した場合（ステップ１９０６及びステップ１９０７）には、制約条件構成手段は、旅程表の各々のスロット・コードｊについて決定変数の有無をチェックし、決定変数が有れば、その決定変数ｘｉｊをこのアクティビティ・コードの決定変数集合に追加（ステップ１９０８）して、次の拡大サービス・データｉを読み込む（ステップ１９０４）。ステップ１９０２で読み込んだアクティビティ・コードと、ステップ１９０４で読み込んだ拡大サービスのアクティビティ・コードとが一致しない場合（ステップ１９０６）、又は、その拡大サービスが根サービス、補助根サービス、及び単純サービスのいずれでもない場合（ステップ１９０７）には、制約条件構成手段は、拡大利用可能リストから次の拡大サービス・データを読み込む（ステップ１９０４）。
【００７５】
拡大利用可能リストのすべての拡大サービス・データについて、ステップ１９０６〜１９０８の処理を終え（ステップ１９０５）、このアクティビティ・コードの決定変数集合に決定変数データが存在する（すなわち、集合が空ではない）場合には、制約条件構成手段は、その集合の決定変数ｘｉ，ｊの和を作成する（ステップ１９１０）。次いで、制約条件構成手段は、このアクティビティ・コードに対応するアクティビティについて旅行者が指定した優先度が「必須」か「二次」かを判断し（ステップ１９１２）、「必須」の場合には、
【数３】
0004268973.tif 000004
となる制約条件式を作成する（ステップ１９１３）。ここで、図１９に示される「一次式」は、決定変数の和を指す。ステップ１９１２において、このアクティビティ・コードに対応するアクティビティについて旅行者が指定した優先度が「二次」である場合には、制約条件構成手段は、
【数４】
0004268973.tif 000005
となる制約条件式を作成する（ステップ１９１４）。
【００７６】
ステップ１９０９において、このアクティビティ・コードの決定変数集合に決定変数データが存在しない（すなわち、集合が空である）場合には、制約条件構成手段は、このアクティビティ・コードに対応するアクティビティを実施できないものとしてマーク付けし（ステップ１９１１）、制約条件式を作成することなくステップは１９０２に戻り、アクティビティ表から次のアクティビティ・データを読み込む。ステップ１９１３又は１９１４において、制約条件構成手段は、このアクティビティ・コードに対応するアクティビティについて制約条件式を作成し終えた場合もまた、ステップは１９０２に戻り、次のアクティビティ・データを読み込む。アクティビティ表のすべてのアクティビティ・コードについてステップ１９０４〜１９１４を行った後、処理は終了する（ステップ１９１５）。
【００７７】
以上の処理を行うことによって、旅行者が希望するサービス（すなわちアクティビティ）ごとに、（１）式又は（２）式で表現される制約条件１が得られる。制約条件１は、図１７及び図１８の例においては、以下の（３）式となる。
（数５）
ｘ１，１＋ｘ１，３＋ｘ１，７＋ｘ１，９＋ｘ１，１１＋ｘ１，１５＝１
ｘ２，４＋ｘ２，１２＝２
ｘ３，３＋ｘ３，１１≦１
ｘ４，１＋ｘ４，７＋ｘ４，９＋ｘ４，１５＋ｘ５，７＝１                （３）
ｘ６，５＋ｘ６，１３＝１
ｘ７，７＋ｘ９，８＋ｘ１０，９≦１
ｘ８，８≦１
【００７８】
以上のように、本発明においては、あるサービスに複数のアクティビティが含まれる場合には、該サービスを各々が単独のアクティビティを含む複数の補助サービスに分割する方法を採用しているが、根サービス、補助根サービス、及び単純サービスに対応する決定変数のみを含む制約式を作成することによって、こうした場合にもアクティビティの選択回数を間違いなくカウントすることが可能である。
【００７９】
図２０は、サービス間の関係に関する制約条件２を作成するための処理である。例えば、前述の複合サービスのように、１つのサービスが複数のアクティビティを提供する場合には、拡大利用可能リスト作成手段は、この複合サービスを、各々が１つのアクティビティを含む複数の補助サービスに分割するが、このような複数の補助サービスは、最終的に旅行計画を作成するときに、すべての補助サービスが一括して選択されるか又は一括して選択されないようにしなければならない。すなわち、このような複数の補助サービスは相互に補完関係にあることになる。このことは、選択又は非選択を決める決定変数が、関連する補助サービスに関して等しいという条件、すなわち、互いに補完関係にある補助サービスｉ及びｋが割り付け可能なスロットをそれぞれｕ及びｖとすると、
（数６）
ｘｉ，ｕ＝ｘｋ，ｖ      （４）
という式で表現することができる。
【００８０】
図２０の処理は、制約条件構成手段が、補助サービス間の関係データ及び拡大利用可能リストを取得することで開始する（ステップ２００１）。次いで、制約条件構成手段は、拡大利用可能リストから最初の拡大サービス・データ（拡大サービス・コードｉ及びそれに関連付けられたデータ）を読み込み（ステップ２００２）、その拡大サービスが複合サービスの根サービス又は単純サービスであるかどうかを判断する（ステップ２００４）。その拡大サービスが根サービス及び単純サービスではない場合には、ステップ２００２に戻り、制約条件構成手段は次の拡大サービス・データを読み込む。その拡大サービスが根サービス又は単純サービスである場合には、制約条件構成手段は、その拡大サービスｉの決定変数集合を取得する（ステップ２００５）。この処理によって、すべてのスロットについて、拡大サービスｉの決定変数ｘｉ，＊を集める。ここで、ｘｉ，＊は、拡大サービス・コードｉを有するすべての決定変数、すなわち、例えばスロット・コードが１〜ｍの場合にはｘｉ，１〜ｘｉ，ｍを表す。制約条件構成手段は、こうして集めた決定変数の集合から決定変数ｘｉ，ｊを１つ読み込み（ステップ２００６）、該拡大サービスｉを根サービスとする補助サービスの関係データを読み込む（ステップ２００８）。次いで、制約条件構成手段は、その拡大サービスｉの補助サービスの拡大サービス・コードｋを読み込み（ステップ２００９）、すべてのスロットについて、該拡大サービスｋの決定変数集合ｘｋ，＊を取得する（ステップ２０１１）。次いで、ｘｋ，ｊがある場合には（ステップ２０１２）、制約条件構成手段は、ｘｉ，ｊ＝ｘｋ，ｊとなる制約条件式を作成してｋをｉと読み替え（ステップ２０１３）、ステップ２００９に戻って、次の補助サービスの拡大サービスを読み込む。
【００８１】
ステップ２０１２においてｘｋ，ｊがない場合には、制約条件構成手段は、次のスロット・コードｊ＋１についてｘｉ，ｊ＝ｘｋ，ｊ＋１となる制約条件式を作成してｋをｉに、ｊ＋１をｊに読み替え（ステップ２０１４）、ステップ２００９に戻って、次の補助サービスの拡大サービスを読み込む。読み込むべき補助サービスがなくなった場合には（ステップ２０１０）、ステップ２００６に戻り、制約条件構成手段は、別の決定変数ｘｉ＋１，ｊを読み込んでステップ２００８〜２０１４を繰り返す。読み込むべき決定変数がなくなった場合には（ステップ２００７）、ステップ２００２に戻って、制約条件構成手段は、次の拡大サービス・データを読み込み、ステップ２００４〜２０１４を繰り返す。すべての拡大サービス・データについてステップ２００２〜２０１４が行われた後、処理は終了する（ステップ２０１７）。
【００８２】
以上の処理を行うことによって、相互に補完関係にある補助サービス間の関係を表す、（４）式で表現される制約条件２が得られる。制約条件２は、図１７及び図１８の例においては、以下の（５）式となる。
（数７）
ｘ５，７＝ｘ８，８
ｘ７，７＝ｘ９，８            （５）
ｘ９，８＝ｘ１０，９
【００８３】
旅行計画を作成する際のさらに別の制約条件として考慮すべき事項に、時間の制約がある。旅行者が多くのアクティビティを必須アクティビティとして選択し、そのすべてを旅行計画に割り当てた場合に、選択された複数のアクティビティの実施に必要な総時間数が、それらのアクティビティを実施できる時間の総和を越えるようなことがあると、作成された旅行計画が実行不可能なものになる。このような現象を回避するために、（１）各々のスロットｊに割り付けられるサービス（すなわち、アクティビティ）ｉの必要時間ｔｉの総和が、各々のスロットｊの時間幅に一定の許容時間幅を加えた時間幅Ｔｊを超えないことを表す制約条件、及び／又は、（２）（システム管理者によって）指定された各々のスロット・タイプの集合Ｓ´（Ｓ´については後述する）について、旅行期間内における各々の日に、そのスロット・タイプ集合Ｓ´に含まれるスロット・タイプに割り付けられるサービスｉの必要時間ｔｉの総和が、そのスロット・コード集合Ｓに含まれるスロット・タイプの時間幅の総和である総時間長に一定の許容時間幅を加えた時間幅Ｔを超えないことを表す制約条件、を作成する（Ｔｊ及びＴの許容時間幅は、システム管理者によって設定され、システム管理者用端末から入力される）。これらの条件は、それぞれ以下の（６）式及び（７）式で表現することができる。ここで、集合Ｓ´は、後述するように、（７）で表される時間制約を作成したいスロット・タイプの集合であり、どのようなスロット・タイプの集合について制約条件を作成するかについては、システム管理者があらかじめ指定し、システム管理者用端末から入力される。また、集合Ｓは、集合Ｓ´に含まれるスロット・タイプに対応するスロット・コードの集合である。（６）式及び（７）式のいずれか一方の制約条件を用いるか、又は両方の制約条件を用いるかについては、システム管理者があらかじめ設定する。
【数８】
0004268973.tif 000006
【数９】
0004268973.tif 000007
【００８４】
ここで、いずれの場合にも「許容時間幅」を加えているが、これは、アクティビティを実施する際の時間の余裕の程度を設定するものである。すなわち、このような許容時間幅を組み込んでおくことによって、あるスロットで実施されるアクティビティが長引いて、その後のスロットにずれ込むような場合でも、後ろのスロットのアクティビティ実施に大きな影響を与えないようにする効果がある。許容時間幅は、システム管理者によって設定され、システム管理者用端末１１２から入力される。
【００８５】
図２１は、スロットごとの時間幅に関する制約条件３（すなわち、（６）式で表される制約条件）を作成するための処理を示し、図２２は、旅行日ごとの指定されたスロット集合Ｓ´の総時間幅に関する制約条件３´（すなわち、（７）式で表される制約条件）を作成するための処理を示す。図２１の処理は、制約条件構成手段が、スロット表、拡大利用可能リスト、及び旅程表を取得することで開始する（ステップ２１０１）。次いで、制約条件構成手段は、旅程表から最初のスロット・コードｊを読み込み（ステップ２１０２）、このスロットｊに対応する決定変数ｘ＊，ｊの集合を取得する（ステップ２１０４）。ここで、ｘ＊，ｊは、スロット・コードｊを有するすべての決定変数、すなわち、例えば拡大サービス・コードが１〜ｎの場合にはｘ１，ｊ〜ｘｎ，ｊを表す。次いで、制約条件構成手段は、その集合から決定変数ｘｉ，ｊを１つ読み込み（ステップ２１０５）、拡大サービス・コードｉに対応するサービス（すなわちアクティビティ）の必要時間ｔｉを取得し、ｔｉとｘｉ，ｊの積ｔｉ・ｘｉ，ｊを作成し（ステップ２１０７）、ステップ２１０５に戻って次の決定変数ｘｉ＋１，ｊを読み込む。ここで、図２１に示される「一次式」は、決定変数と時間の積の和を指す。制約条件構成手段は、決定変数ｘｉ＋１，ｊについても同様にｔｉ＋１・ｘｉ＋１，ｊを作成して、このｔｉ＋１・ｘｉ＋１，ｊをｔｉ・ｘｉ，ｊに加える。このように、制約条件構成手段は、ステップ２１０５〜２１０７を繰り返して、
【数１０】
0004268973.tif 000008
を作成し、スロットｊについて読み込むべき決定変数がなくなったら（ステップ２１０６）、該スロットｊの時間幅を算出する（ステップ２１０８）。この時間幅は、スロット表（図５）の開始時刻及び終了時刻から算出される。次いで、制約条件構成手段は、そのスロットｊの許容時間幅を読み込み（ステップ２１０９）、上記（８）式≦（スロットｊの時間幅）＋（許容時間幅）＝Ｔｊとなる制約条件式を作成する（ステップ２１１０）。次いで、ステップは２１０２に戻り、制約条件構成手段は、次のスロット・コードｊ＋１を読み込み、ステップ２１０４〜２１１０を繰り返す。すべてのスロットｊについてステップ２１０２〜２１１０が行われた後、処理は終了する（ステップ２１１１）。
【００８６】
以上の処理が行われることによって、スロットごとの時間幅に関する制約条件を表す、（６）式で表現される制約条件３が得られる。制約条件３は、図１７及び図１８の例においては、以下の（９）式となる。
（数１１）
６０ｘ１，１＋８０ｘ４，１≦２１０
６０ｘ１，３＋９０ｘ３，３≦２７０
６０ｘ１，７＋８０ｘ４，７＋１２０ｘ５，７＋２１０ｘ７，７≦２１０
６０ｘ１，９＋８０ｘ４，９＋６０ｘ１０，９≦２１０
６０ｘ１，１１＋９０ｘ３，１１≦２７０
６０ｘ１，１５＋８０ｘ４，１５≦２１０                                    （９）
４５０ｘ２，４≦４８０
４５０ｘ２，１２≦４８０
６０ｘ６，５≦１８０
６０ｘ６，１３≦１８０
６０ｘ８，８＋１２０ｘ９，８≦１５０
【００８７】
図２２の処理は、制約条件構成手段が、スロット集合表、決定変数集合、旅行期間表、及び旅程表を取得することで開始する（ステップ２２０１）。スロット集合表は、（７）式で表される時間制約を作りたいスロット・タイプの集合Ｓ´を記述したものであり、どのようなスロット・タイプの集合について制約条件を設定するかをシステム管理者があらかじめ決定し、記述するデータである。例えば、午前から午後までの時間帯について時間制約条件を作りたい場合には、スロット集合Ｓ´を｛Ｃ，Ｄ，Ｅ｝とし、午前と午後の時間帯について時間制約条件を作りたい場合には、スロット集合Ｓ´を｛Ｃ，Ｅ｝とし、1日について時間制約条件を作りたい場合には、スロット集合Ｓ´を｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝とする。次いで、制約条件構成手段は、ステップ２２０２において、スロット集合表から最初のスロット集合Ｓ´を読み取り、そのスロット集合Ｓ´に含まれる各スロット・タイプのスロット時間幅の総和に許容時間幅を加えた時間幅Ｔを算出する（ステップ２２０４）。次に、制約条件構成手段は、旅行期間表から最初の日付を読み込み（ステップ２２０５）、旅程表からその日付の旅程データ集合、すなわち、その日付に含まれるスロット・コード及びスロット・タイプの組を読み込む（ステップ２２０７）。ここで、制約条件構成手段は、スロット集合Ｓ´内のスロット・タイプが、その旅程データ集合のスロット・タイプに含まれるかどうかを判断し（ステップ２２０８）、含まれる場合には、その旅程データ集合から、スロット集合Ｓ´に含まれるスロット・タイプのスロット・コードｊを読み込む（ステップ２２０９）。スロット集合Ｓ´内のスロット・タイプが、その旅程データ集合のスロット・タイプに含まれない場合には、ステップ２２０５に戻り、制約条件構成手段は、次の日付を読み込む。
【００８８】
ステップ２２１１においては、制約条件構成手段は、決定変数集合からｘ＊，ｊの決定変数をすべて取り出し、そのうちの１つの決定変数ｘｉ，ｊを読み込む（ステップ２２１２）。次いで、制約条件構成手段は、拡大サービス・コードｉに対応するサービス（すなわちアクティビティ）の必要時間ｔｉを取得して、ｔｉとｘｉ，ｊの積ｔｉ・ｘｉ，ｊを作成し（ステップ２２１４）、ステップ２２１２に戻って次の決定変数ｘｕ，ｊを読み込む。制約条件構成手段は、決定変数ｘｕ，ｊについても同様にｔｕ・ｘｕ，ｊを作成して、このｔｕ・ｘｕ，ｊをｔｉ・ｘｉ，ｊに加える。このように、ステップ２２１２〜２２１４を繰り返して上述の（８）式を作成する。スロットｊについて読み込むべき決定変数がなくなったら、ステップ２２０９に戻り、制約条件構成手段は、次のスロット・コードを読み込み、ステップ２２１１〜２２１４の処理を繰り返す。制約条件構成手段は、読み込むべきスロット・コードがなくなるまでこれを繰り返して、
【数１２】
0004268973.tif 000009
を作成する。読み込むべきスロット・コードがなくなったら（ステップ２２１０）、制約条件構成手段は、上記（１０）式≦Ｔとなる制約条件式を作成する（ステップ２２１５）。ここで、図２２に示される「一次式」は、決定変数と時間の積の和を指す。次いで、ステップは２２０５に戻って、制約条件構成手段は、旅行期間表から次の日付を読み込み、ステップ２２０７〜２２１５を繰り返す。制約条件構成手段は、すべての日付についてステップ２２０５〜２２１５を行った後、次のスロット集合Ｓ´を読み取り、ステップ２２０４〜ステップ２２１５を繰り返し、すべてのスロット集合について（１０）式を作成した後、処理は終了する（ステップ２２１６）。
【００８９】
以上の処理を行うことによって、旅行日ごとの指定されたスロット集合の総時間幅に関する条件を表す、（７）式で表現される制約条件３´が得られる。例えば、制約条件を作成するスロット集合として日ごとのスロットを指定したとすると、１日の総時間幅に対する制約条件３´は、図１７及び図１８の例においては、以下の（１１）式となる。
（数１３）
６０ｘ１，７＋６０ｘ１，９＋８０ｘ４，７＋８０ｘ４，９＋１２０ｘ５，７＋
２１０ｘ７，７＋６０ｘ８，８＋１２０ｘ９，８＋６０ｘ１０，９≦４８０            （１１）
【００９０】
この例においては、各スロットの許容時間は３０分としている。例えば、（９）式の第１式は、スロット・コードｊ＝１のスロット（すなわちスロット・タイプＥ）の時間幅に関する制約条件であり、スロット・タイプＥの時間の長さは１８０分であるが、この式においては、そのスロットの時間幅に許容時間を３０分加算し、上限を２１０分として設定している。このように設定することができるのは、本発明においては、サービスの必要時間そのものが曖昧性を含んでいることを前提としているからである。
【００９１】
なお、本発明の旅行計画作成方法において組み合わせることが可能な制約条件は、上述の制約条件に限定されるものではない。例えば、スロットごとの時間幅に関する制約条件を使用せずに、一日に選択されるサービスの総必要時間が最初のスロット開始から最後のスロット終了までの時間に収まればよいものとし、上記の（６）式で表される制約条件を使用しないことも考えられるであろう。
【００９２】
６．目的関数構成方法
次いで、目的関数構成手段が、混合整数計画問題を解くための演算プログラムを使用することによって自動的に作成される旅行計画の特性を表す項を含む目的関数を作成する。旅行計画の特性として、例えば、旅行期間内に実施されるサービスの価格の総額が旅行予算額の範囲内であること、又は、旅行期間内にできるだけ多くのアクティビティが含まれること、などが考えられるが、旅行計画の特性はこれらに限定されるものではない。例えば、旅行計画の特性として、旅行期間内に実施されるサービスの価格の総額が一定の範囲に含まれること、又は、旅行者が希望するアクティビティの実施スケジュールが、旅行期間内に均等に分散する（又は、できるだけ集中する）ようにすること、などが考えられる。これらの特性を表現した式は、制約条件構成手段によって作成され、旅行計画作成手段が制約条件として用いることができる。
【００９３】
本実施形態においては、目的関数構成手段が、予算に関する特性と、時間に関する特性と、アクティビティ数に関する特性とを表す項を組み込んだ以下の目的関数（評価式ともいう）、
（数１４）
ａ（ｙ１＋ｙ２）＋ｂｘ−ｃＮ      （１２）
を作成し、旅行計画作成手段が、制約条件構成手段によって作成される上述の制約条件の組の下で、目的関数構成手段によって作成されるこの目的関数を最小化するような最適解を求める場合を考える。この式において、各項のｙ１、ｙ２、ｘ、及びＮは、この目的関数を作成するために導入される新たな変数であり、これらの変数の意味は、後述の処理フロー・チャートの説明の中で明らかにする。なお、目的関数を作成するためにこうした種々の変数を導入することは、当該技術分野では周知である。各項のａ、ｂ、及びｃは、作成される旅行計画の特性を表す重み係数（ａ、ｂ、ｃ＞０）であり、これらの係数は、システム管理者が端末から入力して設定しておくか、又は、プログラムのデータとしてあらかじめ設定しておくことができる。作成される旅行計画は、重み係数ａ、ｂ、及びｃの大きさを変えることによってその特性を定めることが可能であり、予算に関する特性を表すａ、時間に関する特性を表すｂ、及びアクティビティ数に関する特性を表すｃの値、並びにそれらの組み合わせを適宜選択することによって、例えば、予算重視の旅行計画が作成され（ａ＝ｂ＝１、ｃ＝０）、スケジュールに余裕のある旅行計画が作成され（ａ＝１、ｂ＝１００００００、ｃ＝０）、あるいは、多くのアクティビティが組み込まれる旅行計画が作成される（ａ＝１、ｂ＝０、ｃ＝１００００００）。
【００９４】
図２３は、旅行計画の特性を表現する式と目的関数とを作成するための処理のフロー・チャートである。処理は、制約条件構成手段が、決定変数集合と、拡大利用可能リストと、旅程表とを取得することで開始する（ステップ２３０１）。次いで、制約条件構成手段は、拡大利用可能リストから最初の拡大サービス・データ（拡大サービス・コードｉ及びそれに関連付けられたデータ）を読み込み（ステップ２３０２）、その拡大サービスが、根サービス、補助根サービス、又は単純サービスであるかどうかを判断する（ステップ２３０４）。その拡大サービスが、根サービス、補助根サービス、及び単純サービスのいずれでもない場合には、ステップ２３０２に戻り、制約条件構成手段は、次の拡大サービス・データを読み込む。その拡大サービスが根サービス、補助根サービス、又は単純サービスである場合には、制約条件構成手段は、その拡大サービスｉの決定変数集合を取得する（ステップ２３０５）。この処理によって、制約条件構成手段は、すべてのスロットについて、拡大サービスｉの決定変数ｘｉ，＊を集める。次いで、制約条件構成手段は、拡大サービスｉの価格ｐｉを読み込む（ステップ２３０６）。次に、制約条件構成手段は、各々のｘｉ，＊を一次式２に加える（ステップ２３０７）。一次式２は、根サービス、補助根サービス、及び単純サービスに対応するすべての決定変数を加えたものであり、アクティビティの総選択数を与える。次いで、制約条件構成手段は、拡大サービスｉが補助根サービスかどうかを判断し（ステップ２３０８）、補助根サービスであれば、ステップは２３０３に戻り、次の拡大サービス・データを読み込む。その拡大サービスｉが補助根サービスではない場合には、制約条件構成手段は、ｘｉ，＊ごとにｐｉとｘｉ，＊の積ｐｉ・ｘｉ，＊を作り、これをすべてのｊについて繰り返して、拡大サービスｉについて
【数１５】
0004268973.tif 000010
を作成する（ステップ２３０９）。次いで、ステップは２３０２に戻り、制約条件構成手段は、次の拡大サービス・データを読み込み、ステップ２３０４〜２３０９を繰り返す。
【００９５】
制約条件構成手段は、すべての拡大サービスについてステップ２３０２〜２３０９を行い、読み込むべき拡大サービス・コートがなくなったら（ステップ２３０３）、旅行者が入力した旅行条件データから1人あたり予算額Ｂを読み込み（ステップ２３１０）、以下の（１３）式を作成する（ステップ２３１１）。なお、図２３におけるステップ２３１１の「一次式」は、式（１３）の左辺を指す。次いで、制約条件構成手段は、非負の変数ｙ１及びｙ２を導入してこの（１３）式を以下の制約式（１４）に変形する（ステップ２３１２）。ここで、ｙ１及びｙ２は、それぞれ価格の不足分及び超過分を表す変数であり、これらの値の和ｙ１＋ｙ２を小さくすれば予算額Ｂに近い旅行計画が作成されることになる。
【数１６】
0004268973.tif 000011
【数１７】
0004268973.tif 000012
【００９６】
次に、制約条件構成手段は、別の変数Ｎを導入して、
（数１８）
一次式２−Ｎ＝０    （１５）
を作成する（ステップ２３１３）。ここでＮは、アクティビティの数を表す変数であり、この値を大きくすれば多くのアクティビティが組み込まれた旅行計画が作成されることになる。次いで、制約条件構成手段は、非負の１以下の変数ｘを導入して、式（６）で表される制約条件３及び式（７）で表される制約条件３´のうち、システム管理者があらかじめ指定した式（６）及び／又は（７）を、それぞれ、
（数１９）
（左辺）−Ｔｊｘ≦０      （１６）
及び／又は、
（数２０）
（左辺）−Ｔｘ≦０      （１７）
となるように変形する(ステップ２３１４)。ここでｘは、スケジュールの余裕を表す変数であり、ｘを小さくすればスケジュールに多くの余裕がある旅行計画が作成されることになる。
【００９７】
目的関数構成手段は、以上のように各制約式に導入される変数ｙ１、ｙ２、Ｎ、及びｘを用いて、目的関数（１２）式を作成する（ステップ２３１５）。当業者には周知のように、これらの変数の値は、旅行計画作成コンピュータ・システムが目的関数を最適化する解を求める計算を行う中で自動的に設定していくことになる。上述のように、ａ、ｂ、及びｃは、作成される旅行計画の特性を表す重み係数であり、作成される旅行計画は、重み係数ａ、ｂ、及びｃの大きさを変えることによってその特性を定めることが可能である。なお、以上の制約式、導入変数、及び目的関数式は例示的なものであり、最終的に作成される旅行計画に付与したい特性を適切に表現することができるような他の制約式、導入変数、及び目的関数をシステム管理者が自由に設定することができる。
【００９８】
７．旅行計画作成・提供方法
上述の処理によって作成された制約条件の組と目的関数とを用いて、旅行計画作成手段が、該制約条件の組の下で該目的関数を最適化又は近似最適化する決定変数ｘｉ，ｊの組み合わせを求める。すなわち、旅行計画作成手段が、例えば制約条件１（例えば、（３）式に例示した制約条件）、制約条件２（例えば、（５）式に例示した制約条件）、制約条件３及び３´（例えば、（９）式及び（１１）式に例示した制約条件）、予算に関する制約条件（例えば、（１４式）に例示した制約条件）、及び／又は、アクティビティ数に関する制約条件（例えば、（１５式）に例示した制約条件）の下で、目的関数（例えば、（１２）式に例示した目的関数）を最小化する解（すなわち、決定変数の組み合わせ）を決定するという混合整数計画問題を解くことになる。混合整数計画法は、様々な制約条件の下で対象とする問題の最適な解決策を求める手法である数理計画法の一種であり、目的関数も制約条件も１次式で表される問題を解く手法である線形計画法、又は、線形計画問題に「変数は整数値しかとらない」という制約（整数制約）を加えた問題を解く手法である整数計画法に対して、変数の幾つかが整数で、残りの変数が実数であるという制約を加えた問題を解く手法である。こうした問題を解くのに用いることができる市販の数理計画プログラム・パッケージは多数存在しており、これらのプログラム・パッケージを使用して、本実施形態に係る問題を解くことができる。このような市販プログラム・パッケージの例として、「ＣＰＬＥＸ」（日本のアイログ株式会社の製品）、「ＬＩＮＤＯ」（アメリカ合衆国、イリノイ州シカゴ所在のＬＩＮＤＯ  Ｓｙｓｔｅｍｓ社の製品）、又は、「ＭＯＳＥＫ」（デンマーク、コペンハーゲン所在のＭＯＳＥＫ  ＡｐＳ社の製品）が挙げられる。あるいは、これらの市販のプログラム・パッケージに代えて、こういった市販パッケージと同等の機能を有するコンピュータ・プログラムを作成し、それを用いて上述の問題を解くようにしても良い。
【００９９】
決定変数ｘｉ，ｊの組み合わせが求まると、選択されたサービス（又は補助サービス）ｉと、そのサービスが実施されることになる実効スロットｊとを決定することができる。選択されたサービスに補助サービスが含まれる場合には、旅行計画作成手段は、図１２のステップにおいて作成される補助サービス間の関係データに基づいて補完関係にある複数の補助サービスのデータを結合することによって、元のサービスのデータを復元する。旅行計画作成手段は、このようにして得られたサービスの各々とスロットの各々との組み合わせに基づいて、スロット・コードとサービス・コードとを関連付けたデータを作成し、このデータと、スロット表と、サービス−アクティビティ表とを用いて、少なくとも、旅行期間内のスロットの各々（すなわち、一日を複数の時間帯に分割したときの、各々の時間帯）の開始時刻及び終了時刻と、旅行者が実施することを希望するもののうちそのスロット（すなわち時間帯）に実施可能なアクティビティとを関連付けたデータである、最適化又は近似最適化旅行計画を作成する。作成された最適化又は近似最適化旅行計画は、旅行計画提供手段によって、あらかじめデータベースに格納されている旅行業者データ、例えば旅行業者の所在地及び電話番号などのデータと共に、旅行者が使用する端末に送信される。
【０１００】
なお、本実施形態においては、１つのサービスを終了する場所から次のサービスを受ける場所までの移動時間を明示的には考慮していない。これは、前述のように、旅行計画は時間的に多くの余裕を含んだスケジュールであり、さらにこの余裕自体が柔軟性に富んだものであるため、１つの旅行地域内であれば移動時間はこの柔軟性の範囲内に収まると考えられるからである。しかしながら、前述のように、データベースにサービス間の標準的な移動時間データを格納しておき、旅行計画作成の段階でサービスの前又は後に該移動時間データを加算しながらサービスをスロットに割り付けるようにすることもできる。
【０１０１】
８．旅行計画修正方法
旅行計画作成手段が、最適化又は近似最適化した旅行計画を旅行者が使用する端末に送信した後、旅行者が、端末に表示された旅行計画を確認し、その旅行計画の一部を変更又は修正する必要があると考えた場合には、旅行者は、端末からその旅行計画を修正又は変更できるようにすることができる。修正又は変更が、サービス（又は、そのサービスが含むアクティビティ）を提供する旅行業者を変更するものである場合には、旅行計画作成サーバは、旅行計画の変更又は修正の要求を受け取ると、現在の旅行計画の該サービスを実施するスロットにおいて同種のアクティビティを含むサービスを提供することが可能な別の旅行業者の情報をデータベースから検索し、検索結果に基づいて、変更又は修正用のサービス候補リストを作成する。作成された変更又は修正用のサービス候補リストは旅行者が使用する端末に送信され、旅行者は、そのリストに基づいて現在の旅行計画を修正又は変更する。旅行者によって行われた変更又は修正に関するデータは旅行計画作成サーバに送信され、旅行計画作成サーバは、現在の旅行計画において変更又は修正されるサービスを新たなサービスに置換することによって新たな旅行計画を作成し、端末に送信する。
【０１０２】
一方、修正又は変更が、サービス（又は、そのサービスが含むアクティビティ）を提供する旅行業者を変更するもの以外である場合、例えば旅行開始日時又は人数などの、旅行計画に対して指定する旅行条件データを変更するものである場合には、旅行計画作成サーバは、旅行者によって入力された、旅行条件データの該当項目の指定を修正又は変更するデータを受け取り、再び利用可能リスト作成ステップ以降の一連の処理を実行して、新たな旅行計画を作成する。こうして作成された新たな旅行計画は、旅行者が使用する端末に送信される。以上の処理は、旅行者が満足する旅行計画が作成されるまで繰り返される。旅行者が、作成された旅行計画に満足した場合には、その旨が旅行計画作成サーバに通知され、旅行計画作成サーバは、最終的な旅行計画と、該旅行計画に予約を必要とするサービスが含まれる場合には各々のサービスを予約するのに必要な情報とを、端末に送信する。なお、旅行者から入力された旅行条件では旅行計画が作成できない場合には、旅行計画作成サーバは、旅行条件を指定し直すよう促すメッセージを端末に送信する。
【０１０３】
上述の実施形態においては、最適化又は近似最適化した旅行計画と共に送られる予約関連データを用いて、旅行者自らが各々のサービスの予約を行うようになっているが、旅行計画作成サーバに予約手段及び決済手段を追加し、該予約手段及び該決済手段をによって各々のサービスの予約を行うようにすることもできる。この場合、旅行者はユーザ端末から、例えば、氏名、住所、電話番号、及びクレジットカード番号などの予約及び決済に必要な情報を入力し、各々のサービスを提供する旅行業者の予約及び決済管理サーバと接続された予約手段及び決済手段は、これらの情報を用いて、各々のサービスの予約及び決済を行う。これらの予約手段及び決済手段については、従来技術を利用することが可能であり、ここでは詳細に説明しない。
【０１０４】
本実施形態においては、上述のフロー・チャートの各々に示した処理をコンピュータに実行させることが可能なプログラム・コードを含むコンピュータ・プログラムを旅行計画作成サーバに格納して旅行計画作成装置を構成する例を示したが、該コンピュータ・プログラムを、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体に格納して提供することもできる。また、このプログラムを、インターネット又は無線通信などの通信網を介して伝送される伝送媒体に埋め込んで提供することもできる。
【０１０５】
本発明は、上記の実施形態に限定されるものではなく、特許請求の範囲内に記載された発明の範囲を逸脱することなく様々な変更又は修正が可能であり、これらの変更又は修正も本発明の範囲に含まれる。
【図面の簡単な説明】
【０１０６】
【図１】本発明の１つの実施形態に係る旅行計画作成コンピュータ・システムの基本構成を示すブロック図である。
【図２】本発明の１つの実施形態に従って、旅行計画作成コンピュータ・システムによって旅行計画を作成する方法である。
【図３】旅行期間表を作成するための処理のフロー・チャートである。
【図４】旅程表を作成するための処理のフロー・チャートである。
【図５】データベースに格納されているスロット表である。
【図６】アクティビティ表を作成するための処理のフロー・チャートである。
【図７】データベースに格納されているアクティビティ−スロット表である。
【図８】利用可能リストを作成するための処理のフロー・チャートである。
【図９】データベースに格納されているサービス−アクティビティ表である。
【図１０】作成される利用可能リストである。
【図１１】サービス−スロット表を作成するための処理のフロー・チャートである。
【図１２】拡大利用可能リストを作成し、元のサービスと補助サービスとの関係及び補助サービス間の関係データを作成するための処理のフロー・チャートである。
【図１３】拡大利用可能リストを作成し、元のサービスと補助サービスとの関係及び補助サービス間の関係データを作成するための処理のフロー・チャートである。
【図１４】作成される拡大利用可能リストである。
【図１５】決定変数を作成するための処理のフロー・チャートである。
【図１６】図１５において作成した決定変数を絞り込むための処理のフロー・チャートである。
【図１７】アクティビティ表、旅程表、サービス−アクティビティ表、及び利用可能リストの一例である。
【図１８】拡大利用可能リストの一例である。
【図１９】アクティビティの実施回数及び優先度に関する制約条件を作成するための処理のフロー・チャートである。
【図２０】サービス間の関係に関する制約条件を作成するための処理のフロー・チャートである。
【図２１】スロットごとの時間幅に関する制約条件を作成するための処理のフロー・チャートである。
【図２２】旅行日ごとの指定されたスロット集合の総時間幅に関する制約条件を作成するための処理のフロー・チャートである。
【図２３】目的関数を作成するための処理のフロー・チャートである。
【図１】
0004268973.tif 000013
【図２】
0004268973.tif 000014
【図３】
0004268973.tif 000015
【図４】
0004268973.tif 000016
【図５】
0004268973.tif 000017
【図６】
0004268973.tif 000018
【図７】
0004268973.tif 000019
【図８】
0004268973.tif 000020
【図９】
0004268973.tif 000021
【図１０】
0004268973.tif 000022
【図１１】
0004268973.tif 000023
【図１２】
0004268973.tif 000024
【図１３】
0004268973.tif 000025
【図１４】
0004268973.tif 000026
【図１５】
0004268973.tif 000027
【図１６】
0004268973.tif 000028
【図１７】
0004268973.tif 000029
【図１８】
0004268973.tif 000030
【図１９】
0004268973.tif 000031
【図２０】
0004268973.tif 000032
【図２１】
0004268973.tif 000033
【図２２】
0004268973.tif 000034
【図２３】
0004268973.tif 000035