(57)【要約】【課題】現実的な時間内に、リソースを予約に割当可能か否かを判定する予約処理装置を提供する。【解決手段】予約処理装置Ａは、複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定する変数設定部５０と、予約に対するリソースの割り当て可否を表す第１の制約条件を生成する第１制約条件生成部５１と、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成する第２制約条件生成部５２と、第１の制約条件及び前記第２の制約条件を含む制約条件を変数で表現した論理式を満たす変数の解をＳＡＴソルバに検索させるＳＡＴ処理実行部５４と、ＳＡＴソルバによる検索結果に基づいて予約に対するリソースの割り当て可否を判定する割当可否判定部５５と、を有する。【選択図】図１
2015032159.tif 000002
【特許請求の範囲】
【請求項１】
開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定する変数設定部と、
予め設定された前記リソースに関するデータ及び前記予約に関するデータに基づき、前記予約に対する前記リソースの割り当て可否を表す第１の制約条件を生成する第１制約条件生成部と、
前記予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成する第２制約条件生成部と、
前記第１の制約条件及び前記第２の制約条件を含む制約条件を前記変数で表現した論理式を満たす前記変数の解をＳＡＴソルバに検索させるＳＡＴ処理実行部と、
前記ＳＡＴソルバによる検索結果に基づいて前記予約に対する前記リソースの割り当て可否を判定する割当可否判定部と、
を有する、予約処理装置。
【請求項２】
前記ＳＡＴ処理実行部は、系統的ソルバと確率的ソルバとを含む少なくとも二種類のＳＡＴソルバを並列に動作させ、検索結果が早い方の解を採用するように構成されている、請求項１に記載の予約処理装置。
【請求項３】
前記予約の数をＮとし、前記リソースの数をＭとした場合に、前記複数の変数は、Ｎ×Ｍ個に設定される、請求項１又は２に記載の予約処理装置。
【請求項４】
受付可能か否かの判定対象となる新規予約と、既存予約と、を合わせた複数の予約に対し、前記リソースとしてのサービス提供者が割り当て可能か否かを、前記割当可否判定部に判定させるとともに、
前記複数の予約に対し、前記リソースとしての施設が割り当て可能か否かを、前記割当可否判定部に判定させ、
前記サービス提供者及び前記施設の双方が割当可能と判定された場合に、前記新規予約が受付可能であると判定する一方、前記サービス提供者及び前記施設の少なくとも一方が割当不可能と判定された場合に、前記新規予約が受付不可能であると判定する予約受付可否判定部を、有する、請求項１〜３のいずれかに記載の予約処理装置。
【請求項５】
開始時間及びサービス内容を含む新規予約に必要なデータの入力を受け付ける操作部と、
請求項４に記載の予約処理装置とネットワークを介して通信可能な通信部であって、受け付けた新規予約が受付可能か否かを、前記予約処理装置の前記予約受付可否判定部に判定させ、その判定結果を受信する通信部と、
前記通信部が受信した判定結果を表示するディスプレイと、
を備える、予約受付端末。
【請求項６】
サービス内容及びその開始時間を含む新規予約に必要なデータが入力される入力部と、
前記新規予約と前記サービス内容が同じ予約であって、既に確定している既存予約の終了時間から開始する又は前記既存予約の開始時間に終了する代替予約を生成する代替予約生成部と、
前記代替予約それぞれについて、当該代替予約と、前記既存予約と、を合わせた複数の予約に対し、サービスの提供に必要となるリソースが割り当て可能か否かを判定する割当検証部と、
前記割当検証部により割当可能と判定された代替予約を提示する提示部と、
を有する、予約処理装置。
【請求項７】
前記代替予約生成部により生成された代替予約から、当該代替予約の開始時間と前記新規予約の開始時間の差が所定時間以下となる代替予約を抽出する代替予約抽出部を備え、
前記割当検証部は、前記代替予約抽出部により抽出された前記代替予約について前記リソースが割当可能か否かを判定する、請求項６に記載の予約処理装置。
【請求項８】
開始時間及びサービス内容を含む新規予約に必要なデータの入力を受け付ける操作部と、
請求項６又は７に記載の予約処理装置とネットワークを介して通信可能な通信部であって、受け付けた新規予約に対応する代替予約のうち、前記割当検証部により割当可能と判定された代替予約を受信する通信部と、
前記通信部が受信した代替予約を表示するディスプレイと、
を備える、予約受付端末。
【請求項９】
コンピュータが実行する方法であって、
開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定するステップと、
予め設定された前記リソースに関するデータ及び前記予約に関するデータに基づき、前記予約に対する前記リソースの割り当て可否を表す第１の制約条件を生成するステップと、
前記予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成するステップと、
前記第１の制約条件及び前記第２の制約条件を含む制約条件を前記変数で表現した論理式を満たす前記変数の解をＳＡＴソルバに検索させるステップと、
前記ＳＡＴソルバによる検索結果に基づいて前記予約に対する前記リソースの割り当て可否を判定するステップと、
を有する、予約処理方法。
【請求項１０】
系統的ソルバと確率的ソルバとを含む少なくとも二種類のＳＡＴソルバを並列に動作させ、検索結果が早い方の解を採用するステップを含む、請求項９に記載の予約処理方法。
【請求項１１】
前記予約の数をＮとし、前記リソースの数をＭとした場合に、前記複数の変数は、Ｎ×Ｍ個に設定される、請求項９又は１０に記載の予約処理方法。
【請求項１２】
受付可能か否かの判定対象となる新規予約と、既存予約と、を合わせた複数の予約に対し、前記リソースとしてのサービス提供者が割り当て可能か否かを判定するとともに、
前記複数の予約に対し、前記リソースとしての施設が割り当て可能か否かを判定し、
前記サービス提供者及び前記施設の双方が割当可能と判定された場合に、前記新規予約が受付可能であると判定する一方、前記サービス提供者及び前記施設の少なくとも一方が割当不可能と判定された場合に、前記新規予約が受付不可能であると判定するステップを、
有する、請求項９〜１１のいずれかに記載の予約処理方法。
【請求項１３】
コンピュータが実行する方法であって、
サービス内容及びその開始時間を含む新規予約と前記サービス内容が同じ予約であって、既に確定している既存予約の終了時間から開始する又は前記既存予約の開始時間に終了する代替予約を生成するステップと、
前記代替予約それぞれについて、当該代替予約と、前記既存予約と、を合わせた複数の予約に対し、サービスの提供に必要となるリソースが割り当て可能か否かを判定するステップと、
割当可能と判定された代替予約を提示するステップと、
を有する、予約処理方法。
【請求項１４】
前記生成した代替予約から、当該代替予約の開始時間と前記新規予約の開始時間の差が所定時間以下となる代替予約を抽出するステップを有し、
抽出した前記代替予約について前記リソースが割当可能か否かを判定する、請求項１３に記載の予約処理方法。
【請求項１５】
請求項９〜１４のいずれかに記載の予約処理方法をコンピュータに実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サービスを提供する業務に用いられ、サービス提供者や施設などのサービスの提供に必要なリソースを予約に割当可能か否かを判定する予約処理装置、予約受付端末、予約処理方法、及びコンピュータプログラムに関する。
【背景技術】
【０００２】
美容室、時間貸し会議室、病院、歯科医院、エステティックサロン、リラクゼーション、ネイルサロンなどのサービスを提供する業務においては、サービスの提供に必要なリソースを、予約に割当可能か否かを判定する必要がある。リソースの例として、サービス提供者（例えば施術サービスであれば施術者）や施設（例えば施術サービスであればベッド等の設備）が挙げられる。店舗は、施術者や施設などのリソースを複数有し、複数の予約を受け付けて業務を実施する。円滑に業務を進めるためには、予約管理が必須となる。予約管理には、受け付けた既存予約に対するリソース（施術者や施設）の最適な割当、及び、新規予約の問い合わせがあるときに、当該新規予約を受けることが可能か否かを顧客に返答するために、新規予約にリソースを割当可能か否かの判定、が含まれる。
【０００３】
上記予約管理は、特許文献１でも述べられている通り、二次元の予約表を用いて人手で行われていることが多い。例えば、予約表の縦軸には、店舗が有する施術者及び施設が記載され、予約表の横軸には、時間軸が記載される。予約表において予約に対してリソースの割り当てがなされる。予約管理者（一般的には受付スタッフ）が、予約表を適宜最適化する。このような人手による最適化作業及び割当可否判定は、作業者の熟練や感覚に頼る面が大きい。また、受け付けた予約が許容量を超えるのを恐れるため、余裕を見て新規予約を取りこぼすおそれがある。
【０００４】
上記作業を自動化する技術として特許文献１が開示されている。特許文献１には、上記予約表に対して、所定の並び替え処理及び空き時間抽出処理を実施することにより、リソースの割当可否判定及び最適化を自動化できる旨が記載されているようである。
【０００５】
特許文献２には、交通機関の座席を予約するシステムにおいて、予約に座席を割り当てる処理を、制約充足割当処理により実現することが記載されている（例えば段落００１３，００３０，００３１参照）。制約充足割当処理の詳細は、記載されていないため不明である。
【０００６】
特許文献３は、予約管理とは異なるが、複数の看護師が勤務する日時を決定するスケジューリング方法が開示されている。ここでは、各看護師の勤務時間を表す変数と、変数の値に存在する制約と、制約の重要度を表す数値と、を構成要素とする重み付き制約充足問題として定式化することが記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第４８８１６１２号
【特許文献２】特開平１１−３２８２７８号公報
【特許文献３】特開２００５−２６７５９１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、サービスを提供する業務における予約に対するリソースの割当最適化、及び、割当可否判定は、非常に難しい問題である。施術サービスを例に説明すると、複数の種類の施術サービスが提供されており、施術者には、技術の有無によって、担当可能な施術サービスと担当不可な施術サービスがある。更に、施設には、その機能及び用途によって、割当可能な施術サービスと割当不可な施術サービスがある。予約に対するリソースの割当が適切であれば、新規予約を受任可能となる。一方、予約に対するリソースの割り当てが適切でなければ、新規予約を受け付けるためのリソースが残っていないと誤判定してしまい、新規予約の受任を取りこぼすおそれがある。
【０００９】
予約に対するリソースの割当が適切か否かは、予約とリソースの組み合わせを検証する必要がある。しかし、予約の数が増えるに従って予約とリソースの割当パターンの数が指数関数的に増大してしまう。具体的には、予約数がＮ件、リソースがＭ個の場合、単純な組み合わせはＭＮ個存在する。予約が１件増えるだけで、計算量がＭ倍となってしまう。例えば総当たり法で予約に対してリソースの割り当てを計算したのでは、解を得るまでに数日〜数ヶ月も要する場合があり、業務において許容できる現実的な時間（例えば数秒〜数十秒）内では解を得ることができない。
【００１０】
特許文献２や３に基づき、リソースの割り当てを制約充足問題と捉え、制約充足問題を解く代表的なバックトラッキング法（総当たり検索の改良案）を用いて、割当可否判定処理を試験的に実装したが、予約数が数十件を超えるあたりから計算量が莫大となり、解を得ることができなくなってしまう。
【００１１】
特許文献１の方法は、予約とリソースの組み合わせを検証することを諦めた方法であり、単純な並び替えにより、予約にリソースを割り当てる方法のようである。したがって、予約とリソースの組み合わせを検証していないため、予約に対するリソースの割当が適切とは言えない。
【００１２】
本発明の発明者は、種々の試行や検討を重ねたところ、予約に対するリソースの割当問題を、特許文献２や３で言う制約充足問題としてとらえるのではなく、充足可能性問題（SATisfiability problem, SAT）に変換し、ＳＡＴソルバを用いて解を求めるのであれば、制約充足問題としてとらえるよりも高い確率で現実時間内に解を見つけることができるという新たな知見を得た。当然ながら、予約とリソースの割当問題をＳＡＴに変換する手法や技術は、先行文献に開示も示唆もされてないようである。
【００１３】
本発明は、このような課題に着目してなされたものであって、現実的な時間内に、リソースを予約に割当可能か否かを判定する予約処理装置、予約受付端末、予約処理方法、及びコンピュータプログラムを提供することである。
【課題を解決するための手段】
【００１４】
本発明は、かかる目的を達成するために、次のような手段を講じている。
【００１５】
すなわち、本発明の予約処理装置は、開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定する変数設定部と、
予め設定された前記リソースに関するデータ及び前記予約に関するデータに基づき、前記予約に対する前記リソースの割り当て可否を表す第１の制約条件を生成する第１制約条件生成部と、
前記予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成する第２制約条件生成部と、
前記第１の制約条件及び前記第２の制約条件を含む制約条件を前記変数で表現した論理式を満たす前記変数の解をＳＡＴソルバに検索させるＳＡＴ処理実行部と、
前記ＳＡＴソルバによる検索結果に基づいて前記予約に対する前記リソースの割り当て可否を判定する割当可否判定部と、を有する。
【００１６】
このように、予約とリソースの割り当て状態を表す複数の変数を設定し、予約とリソースの割当可否を表す第１の制約条件を生成し、予約時間を考慮するための第２の制約条件を生成し、これら制約条件を変数の論理式に変換して、ＳＡＴソルバで解を得るので、割当問題を制約充足問題ではなく充足可能性問題に変換でき、現実的な時間内で割当可否を判定することが可能となる。
【００１７】
現実時間内で解が見つかる確率を向上させるためには、前記ＳＡＴ処理実行部は、系統的ソルバと確率的ソルバとを含む少なくとも二種類のＳＡＴソルバを並列に動作させ、検索結果が早い方の解を採用するように構成されていることが好ましい。
【００１８】
計算コストの増大を抑制するためには、前記予約の数をＮとし、前記リソースの数をＭとした場合に、前記複数の変数は、Ｎ×Ｍ個に設定されることが好ましい。
【００１９】
サービスの提供にあたり、サービス提供者と施設の両方が必要となる業務に適用するためには、受付可能か否かの判定対象となる新規予約と、既存予約と、を合わせた複数の予約に対し、前記リソースとしてのサービス提供者が割り当て可能か否かを、前記割当可否判定部に判定させるとともに、前記複数の予約に対し、前記リソースとしての施設が割り当て可能か否かを、前記割当可否判定部に判定させ、前記サービス提供者及び前記施設の双方が割当可能と判定された場合に、前記新規予約が受付可能であると判定する一方、前記サービス提供者及び前記施設の少なくとも一方が割当不可能と判定された場合に、前記新規予約が受付不可能であると判定する予約受付可否判定部を、有することが好ましい。
【発明の効果】
【００２０】
本発明は、以上説明した構成であるので、割当問題を制約充足問題ではなく充足可能性問題に変換でき、現実的な時間内で割当可否を判定することが可能となる。したがって、従来ではコンピュータで実現できていなかった、予約とリソースの全組み合わせパターンを考慮した割当可否判定を実現することが可能となる。よって、より高品質な予約システムを構築することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１実施形態の予約処理装置を示すブロック図。
【図２Ａ】予約の一例を示す図。
【図２Ｂ】リソースとしてのサービス提供者の一例を示す図。
【図２Ｃ】図２Ａ〜Ｂの場合において、予約とサービス提供者の割当可否を表す第１の制約条件Ｃを示す図。
【図３Ａ】予約の一例を示す図。
【図３Ｂ】図３Ａの場合において、予約と施設の割当可否を表す第１の制約条件Ｅを示す図。
【図４Ａ】図２Ａの場合において、第２の制約条件Ｄを示す図。
【図４Ｂ】図３Ａの場合において、第２の制約条件Ｄを示す図。
【図５】第１実施形態の予約処理装置が実行する予約処理ルーチンを示すフローチャート。
【図６】第１実施形態の予約処理装置が実行する割当可否判定処理ルーチンを示すフローチャート。
【図７】第１実施形態の変形例を示すブロック図。
【図８】第２実施形態の予約処理装置を示すブロック図。
【図９Ａ】希望の新規予約と既存予約との関係を示す図。
【図９Ｂ】代替予約生成処理に関する説明図。
【図９Ｃ】代替予約抽出処理に関する説明図。
【図１０】第２実施形態の予約処理装置が実行する予約処理ルーチンを示すフローチャート。
【発明を実施するための形態】
【００２２】
＜第１実施形態＞
以下、本発明の第１実施形態に係る予約処理装置、予約受付端末、予約処理方法、及びコンピュータプログラムについて、図面を参照して説明する。ここでは、理解を容易にするために、リラクゼーション等の施術サービスをサービスの例として説明する。施術サービスには、例えばボディマッサージ、タイ式マッサージ、足底マッサージ、スウェーデンマッサージなどの複数のコースがあるとする。サービスの提供に必要となるリソースの例として、サービス提供者（施術者）及び施設（ボディ用ベッド、タイ式用ベッド、足底用ベッド、スウェーデン用ベッドなど）が挙げられる。なお、これらは理解を容易にするために例示しているのに過ぎないため、本発明は、これらに限定されない。
【００２３】
予約処理装置Ａは、入力部１と、制御部２と、予約情報記憶部３と、リソース情報記憶部４と、割当検証部５と、出力部６と、を有する。新規予約に関するデータが入力部１に入力されると、予約情報記憶部３に記憶されている既存予約と当該新規予約を合わせた複数の予約に対し、リソース（施術者、施設）が割当可能か否かを割当検証部５が判定する。制御部２は、割当検証部５が割当可能であると判定した場合には、ディスプレイ等の出力部６を通じて新規予約が受付可能である旨を出力する。制御部２は、割当検証部５が割当可能でないと判定した場合には、出力部６を通じて新規予約が受付不可である旨を出力する。
【００２４】
予約処理装置Ａを構成する上記各部１〜６は、図示しないＣＰＵ、記憶部（メモリ等）、操作部及びディスプレイを有するパーソナルコンピュータにおいてＣＰＵが、記憶部に記憶されている所定のコンピュータプログラムを実行し、ソフトウェアとハードウェア資源が協働することにより、実現される。本実施形態では、一台のパソコンにより予約処理装置Ａが構成されるスタンドアロン型として説明する。
【００２５】
図１に示すように、入力部１は、キーボードやタッチパネルなどの操作部を介してユーザから新規予約に関するデータの入力を受け付ける。新規予約に関するデータには、予約の開始時間及び終了時間、サービスの種類（コース等）、及び指定情報（施術者の指名、施術者の性別指定等）が含まれる。入力部１へデータを入力するユーザは、顧客又は受付スタッフのいずれでもよい。
【００２６】
予約情報記憶部３は、既に確定している既存予約を記憶する既存予約記憶部３０と、新規予約を記憶する新規予約記憶部３１と、を有する。既存予約は、顧客との間で予約が確約された予約である。新規予約は、顧客との間で予約が確約されていない予約であり、割当検証部５が利用するために一時的に記憶される。既存予約に関するデータは、新規予約と同様に、予約の開始時間及び終了時間、サービスの種類（コース等）、及び指定情報（施術者の指名、施術者の性別指定等）が含まれる。
【００２７】
リソース情報記憶部４は、リソースに関する情報を記憶するもので、サービス提供者情報記憶部４０と、施設情報記憶部４１と、を有する。本実施形態では、リソース情報記憶部４は、リレーショナルデータベースシステムを用いて構成されている。サービス提供者情報記憶部４０は、少なくとも一人のサービス提供者（施術者）に関する情報を記憶する。施術者に関する情報の例として、施術者が担当可能（施術可能）なサービス（コース）、施術者の性別、施術者の勤務可能時間（勤務時間、休憩時間）などが挙げられる。施設情報記憶部４１は、少なくとも１つの施設に関する情報を記憶する。施設に関する情報の例として、割当可能なサービス（コース）などが挙げられる。これらの情報は、リソースとサービスの割当可否を表す制約データ、リソースと予約の割当可否を表す制約データとも言える。
【００２８】
制御部２は、上記各部１〜６の動作を制御することで、装置Ａ全体の動作を制御する。
【００２９】
図１に示すように、割当検証部５は、リソース情報記憶部４及び予約情報記憶部３に記憶されているデータに基づき、新規予約及び既存予約を合わせた複数の予約（全予約）に対して、リソースを割当可能か否か判定する。割当検証部５は、サービス提供者（施術者）の割当可否判定処理と、施設の割当可否判定処理と、を実行することになる（図５のＳ１０２，Ｓ１０３参照）。
【００３０】
具体的に、割当検証部５は、変数設定部５０と、第１制約条件生成部５１と、第２制約条件生成部５２と、基本制約生成部５３と、ＳＡＴ処理実行部５４と、割当可否判定部５５と、を有する。
【００３１】
変数設定部５０は、既存予約及び新規予約を合わせた全ての予約に対し、サービスの提供に必要となるリソースの割り当て状態を示す複数の変数を設定する。ここで、説明のために、サービス提供者（施術者）の割当を考える。サービス提供者がＭ人、予約がＮ件とすれば、上記複数の変数Ｘは、次のように表すことができる。
2015032159.tif 000003
ｘi j＝１は、サービス提供者ｉが予約ｊを担当することを意味し、ｘi j＝０は、担当しないことを意味する。複数の変数は、ｘ1 1、…、ｘM NというようにＭ×Ｎ個あり、各変数が予約とリソースの割り当て状態を表している。
【００３２】
これら変数を論理変数で表現すると、次のようになる。
2015032159.tif 000004
ｔは真を表し、ｆは偽を表す。ある予約ｊに対してサービス提供者ｉが割り当てられた場合は、ｘi j＝ｔ（真）となる。
【００３３】
第１制約条件生成部５１は、予約情報記憶部３及びリソース情報記憶部４に記憶されているデータを参照し、予め設定されたリソースに関するデータ及び予約に関するデータに基づき、予約に対するリソースの割り当て可否を表す第１の制約条件（Ｃ，Ｅ）を生成する。
【００３４】
サービス提供者（施術者）の割当において、第１の制約条件には、性別指定による制約、勤務時間による制約、休憩時間による制約、施術可能（担当可能）による制約、施術者の指名による制約などがある。サービス提供者（施術者）の割当において、第１の制約条件Ｃは、次のように表すことができる。
2015032159.tif 000005
サービス提供者ｉが予約ｊを担当可能（施術可能）である場合は、ｃi j＝０となり、担当不可の場合はｃi j＝１となる。このとき、以下の制約が成立する。
2015032159.tif 000006
論理式では、次のように表される。
2015032159.tif 000007
すなわち、予約ｊとサービス提供者ｉが割当不可のとき、論理式ｘj iは偽となる。
【００３５】
ここで、サービス提供者（施術者）の割当について、施術可能（担当可能）による制約を例として説明する。図２Ａに示すように、既存予約１〜３があり、新規予約４を受け付けるか否かを判定するとする。既存予約１，２がタイ式マッサージ、予約３が足底マッサージ、予約４がスウェーデンマッサージとする。図中では、予約の時間を斜線にて表している。例えば予約１の開始時間は１４：００であり、終了時間は１４：３０である。図２Ｂに示すように、サービス提供者としての施術者（トレーナ）は４人とし、施術者１〜４の施術可能なコースは図中に示す通りである。”○”が担当可能を表し、”×”が担当不可を表す。この場合、予約数が４件、施術者の数が４人なので、１６個の変数が設定される。第１の制約条件Ｃは、図２Ｃ及び次のように生成される。
2015032159.tif 000008
”０”は、割当可能を示し、”１”は割当不可を示す。
【００３６】
施設の割当において、第１の制約条件には、割当可能なサービス（コース）による制約がある。施設の割当において、第１の制約条件Ｅは、次のように表すことができる。
2015032159.tif 000009
施設ｉが予約ｊに割当可能である場合は、ｅi j＝０となり、割当不可の場合はｅi j＝１となる。このとき、以下の制約が成立する。
2015032159.tif 000010
論理式では、次のように表される。
2015032159.tif 000011
すなわち、予約ｊと施設ｉが割当不可のとき、論理式ｘj iは偽となる。
【００３７】
ここで、施設の割当について例を用いて説明する。図３Ａに示すように、既存予約１〜３があり、新規予約４を受け付けるか否かを判定するとする。予約１，２がタイ式マッサージであり、予約３，４が足底マッサージである。図中では、予約の時間を斜線にて表している。施設として、タイ式ベッドが３つ、足底用ベッドが２つある。タイ式ベッドはタイ式マッサージに使用でき、足底マッサージには利用できない。足底用ベッドは、足底マッサージに使用でき、タイ式マッサージには利用できない。この場合、予約数が４件、施設の数が５つとなるので、２０個の変数が設定される。第１の制約条件Ｅは、図３Ｂ及び次のように生成される。
2015032159.tif 000012
”０”は、割当可能を示し、”１”は割当不可を示す。
【００３８】
図１に戻り、第２制約条件生成部５２は、予約情報記憶部３に記憶されているデータを参照し、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成する。第２の制約条件Ｄは、次のように表すことができる。
2015032159.tif 000013
Ｄは、上三角行列であり、対角要素はすべて０である。ｄj1  j2＝０は、同一の施術者が予約j1と予約j2を施術（担当）できないことを表す。このとき、次の式が成立する。
2015032159.tif 000014
論理式では、次のように表される。
2015032159.tif 000015
これは、予約j1と予約j2を同一の施術者が担当できないときは、
2015032159.tif 000016
という論理式が真になることを意味する。
【００３９】
ここで、第２の制約条件の具体例を説明する。図２Ａに示す例の場合には、予約１は予約２と重複するものの、他の予約と重複していない。予約２は予約１，３と重複するものの、他の予約と重複していない。予約３は予約２，４と重複するものの、他の予約と重複していない。予約４は、予約３と重複するものの、他の予約と重複していない。この場合、第２の制約条件Ｄは、図４Ａ及び次のように生成される。
2015032159.tif 000017
図３Ａに示す例の場合は、図４Ｂ及び次のように生成される。
2015032159.tif 000018
【００４０】
なお、時間を所定間隔で区切ったタイムテーブル形式のように、各時間帯に一つの変数を設けることが考えられるが、この場合は、必要となる変数が膨大となり、計算時間が増大してしまうことが考えられる。さらに、区切った単位ではなく、３０分単位や１分刻みなどの任意の時間を指定することができない。しかし、本発明のような第２の制約条件Ｄであれば、予約同士が重複するか否かを見るだけなので、３０分、１分などの任意の時間を指定することが可能になる。それでいて、変数の数がＭ×Ｎ個で必要最低限の数なので、計算時間が無駄に増大することもない。
【００４１】
図１に戻り、基本制約生成部５３は、変数設定部５０が設定した変数を参照し、予約とリソースの割当において自明な制約を生成する。自明な制約は、１つの予約に対して必ず１つのリソース（サービス提供者、施設）を割り当てる必要があり、割り当てるリソースの数が２以上や０であってはならないとする制約である。この制約は、次のように表すことができる。
2015032159.tif 000019
論理式で表現するには、at-least-one制約とat-most-one制約の二つの式に分けて表現できる。
at-least-one制約は、ある予約に対して割り当てるリソースが少なくとも１つ存在することを意味する。論理式では、次のように表される。
2015032159.tif 000020
at-most-one制約は、ある予約に対して割り当てるリソースが多くても１つ存在することを意味する。論理式では、次のように表される。
2015032159.tif 000021
ただし、Ｍは２以上である。
【００４２】
ＳＡＴ処理実行部５４は、第１の制約条件及び第２の制約条件を含む制約条件を変数で表現した論理式を満たす変数の解をＳＡＴソルバに検索させる。具体的には、ＳＡＴ処理実行部５４は、論理式変換部５４ａと、系統的ソルバ５４ｂと、確率的ソルバ５４ｃと、を有する。
【００４３】
論理式変換部５４ａは、第１制約条件生成部５１、第２制約条件生成部５２及び基本制約生成部５３が生成した制約条件（Ｃ，Ｅ，Ｄ等）を、変数設定部５０が設定した変数Ｘの論理式に変換する。例えば、図２Ａの例では、第１の制約条件Ｃは、
2015032159.tif 000022
であるので、論理変数Ｘi  j（i∈｛1,2,3,4｝、j∈｛1,2,3,4｝）を用いて表現すると、
第１の制約条件Ｃの論理式は、
2015032159.tif 000023
となる。
【００４４】
図２Ａに例示する第２の制約条件Ｄは、
2015032159.tif 000024
である。これを論理変数を用いて表現すると、第２の制約条件Ｄの論理式は、
2015032159.tif 000025
となる。
【００４５】
自明な論理式のうち、at-least-one制約は、例えばＮ＝４，Ｍ＝４のとき、
2015032159.tif 000026
となる。
【００４６】
自明な論理式のうち、at-most-one制約は、例えばＮ＝４，Ｍ＝４のとき、
2015032159.tif 000027
となる。
【００４７】
第１の制約条件Ｃ、第２の制約条件Ｄ及び自明な制約を含む制約条件を論理式で表すと、
（第１の制約条件Ｃの論理式）∧（第２の制約条件Ｄの論理式）∧（自明な制約の論理式）
となる。すなわち、第１の制約条件と、第２の制約条件と、自明な制約条件とをＡＮＤ（∧）で結合した論理式を生成する。ＡＮＤ結合しているのは、上記全ての論理式が真となる解をＳＡＴソルバに検索させるためである。この論理式を、ＳＡＴソルバに入力するために、ＳＡＴソルバの標準入出力形式であるＤＩＭＡＣＳ形式に変換する。上記では論理変数Ｘi  j（i∈｛1,2,3,4｝、j∈｛1,2,3,4｝）を用いて論理式を構築しているが、ＤＩＭＡＣＳ形式にするために、論理変数Ｘi  j（i∈｛1,2,3,4｝、j∈｛1,2,3,4｝）を１６個の論理変数（Ｘ1，Ｘ2，…，Ｘ15，Ｘ16）に対応させ、１６個の論理変数にて論理式を構築する。なお、ＤＩＭＡＣＳ形式はＳＡＴソルバに用いる標準形式であるので、説明は省略する。
【００４８】
ＳＡＴ（SATisfiability problem, SAT）ソルバは、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題を解くプログラムである。その出力情報としては、与えられた論理式が真となる組み合わせが存在することを意味する「ＳＡＴ」、存在しないことを意味する「ＵＮＳＡＴ」がある。「ＳＡＴ」の場合、割当可能であることを表しており、そのときに解も出力される。
【００４９】
ＳＡＴソルバには、系統的ソルバ５４ｂ（systematic solver）と、確率的ソルバ５４ｃ（stochastic solver）と、の二種類がある。系統的ソルバ５４ｂは、系統的検索を行うアルゴリズムに基づいており、十分な時間があれば「ＳＡＴ」、「ＵＮＳＡＴ」のいずれかを判定可能である。系統的検索アルゴリズムに基づくので、同じ問題は毎回同じ時間で解くことができる。ただし、解けない問題（苦手問題）が存在する。本実施形態では、系統的ソルバである「MiniSAT」を用いている。勿論、系統的ソルバであれば、「MiniSAT」以外も採用可能である。
【００５０】
系統的ソルバ５４ｂに対し、確率的ソルバ５４ｃは、乱数を用いた確率的局所検索を行うアルゴリズムに基づいており、苦手問題が存在せず、一般的に系統的ソルバにより「ＳＡＴ」を判定する能力に優れている。その一方で、確率的ソルバ５４ｃは、ＵＮＳＡＴ判定ができないとい欠点があり、更に、乱数を用いているため、同じ問題でも求解に要する時間が毎回異なる。本実施形態では、確率的ソルバである「WalkSAT」を用いている。勿論、確率的ソルバであれば、「WalkSAT」以外も採用可能である。
【００５１】
ＳＡＴ処理実行部５４は、論理式変換部５４ａにより変換された論理式を、系統的ソルバ５４ｂと、確率的ソルバ５４ｃとの両方に入力し、同時に並行して解を検索させる。そして、いずれか一方のソルバから検索結果が返ってきた場合には、他方のソルバの実行を止め、検索結果が早い方の解を採用する。
【００５２】
割当可否判定部５５は、ＳＡＴ処理実行部５４による検索結果に基づいて予約に対するリソースの割り当て可否を判定する。具体的には、「ＳＡＴ」である場合には、割当可能であると判定し、「ＵＮＳＡＴ」の場合又は所定時間経過しても回答がない場合には、割当不可であると判定する。
【００５３】
上記装置の動作を説明する。
【００５４】
図１及び図５に示すように、制御部２は、新規予約に関するデータが入力部に入力されると（Ｓ１０１：ＹＥＳ参照）、ステップＳ１０２において、予約情報記憶部３に記憶されている既存予約と当該新規予約を合わせた複数の予約に対し、サービス提供者（リソース）が割当可能か否かを割当検証部５に判定させる。また、制御部２は、ステップＳ１０３において、上記複数の予約に対し、施設（リソース）が割当可能か否かを割当検証部５に判定させる。Ｓ１０２の処理及びＳ１０３の処理は、並列に実行してもよく、順次実行する場合には実行順序は任意に変更可能である。次に、制御部２は、ステップＳ１０４において、サービス提供者及び施設の双方が割当可能と判定された場合（Ｓ１０４：ＹＥＳ）には、ステップＳ１０５にて新規予約が受付可能であると判定する。一方、サービス提供者及び施設の少なくとも一方が割当不可能と判定された場合（Ｓ１０４：ＮＯ）には、ステップＳ１０６にて新規予約が受付不可能であると判定する予約受付可否判定部２０として機能する。次に、制御部２は、新規予約が受付可能と判定した場合には、出力部６を通じて新規予約が受付可能である旨を出力する（Ｓ１０７）。一方、制御部２は、新規予約が受付不可と判定した場合には、出力部６を通じて新規予約が受付不可である旨を出力する（Ｓ１０７）。
【００５５】
図６は、複数の予約に対してリソースが割当可能か否かを判定する割当可否判定処理ルーチンをフローチャートである。制御部２により割当可否判定処理の実行が指示されると、図１及び図６に示すように、割当検証部５は、ステップＳ２０１において、リソース情報記憶部４及び予約情報記憶部３に記憶されているリソース及び予約に関するデータを取得する。次のステップＳ２０２において、変数設定部５０は、複数の予約に対するリソースの割り当て状態を表すための複数の変数Ｘを設定する。次のステップＳ２０３において、第１制約条件生成部５１は、リソース及び予約に関するデータに基づき、予約に対するリソースの割り当て可否を表す第１の制約条件を生成する。例えば、図２Ｃや図３Ｂに示す制約条件（Ｃ，Ｅ）が挙げられる。次のステップＳ２０４において、第２制約条件生成部５２は、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成する。例えば、図４Ａや図４Ｂに示す制約条件（Ｄ）が挙げられる。次のステップＳ２０５において、基本制約生成部５３が、リソースの数と予約の数に基づき自明な制約を生成する。次のステップＳ２０６において、論理式変換部５４ａが、第１の制約条件（Ｃ、Ｅ）、第２の制約条件Ｄ及び自明な制約を含む制約条件を、上記変数の論理式に変換する。次のステップＳ２０７において、ＳＡＴ処理実行部５４が、系統的ソルバ５４ｂ及び確率的ソルバ５４ｃを並列実行する。次のステップＳ２０８において、ＳＡＴ処理実行部５４は、いずれかのソルバからの返答が所定時間内にあるか否かを判定する。所定時間内に返答があった場合には（Ｓ２０８：ＹＥＳ）、他方のソルバの実行を中止し、次のステップＳ２０９において、ＳＡＴ処理実行部５４は、ソルバの返答結果が「ＳＡＴ」であるか否かを判定する。ステップＳ２０９において、結果が「ＳＡＴ」であるときは（Ｓ２０９：ＹＥＳ）、次のステップＳ２１０において、割当可否判定部５５が割当可能と判定し、割当可否判定処理を終了する。一方、ステップ２０８において所定時間内に返答が無かった場合（Ｓ２０８：ＮＯ）、又は、ステップＳ２０９においてソルバからの返答結果が「ＳＡＴ」でなかった場合（Ｓ２０９：ＮＯ）には、割当可否判定部５５が割当不可と判定し（Ｓ２１１）、割当可否判定処理を終了する。
【００５６】
＜第１実施形態の変形例＞
第１実施形態では、入力部１は、操作部を介して新規予約を受け付けるように構成されており、出力部６がディスプレイであり、予約処理装置Ａがいわゆるスタンドアロン型であったが、Ｗｅｂサーバなどのサーバクライアント型に構築しても良い。Ｗｅｂアプリケーションの場合、入力部１及び出力部６は、Ｗｅｂアプリケーションのインターフェイス（例えばCGIなど）となる。
【００５７】
また、図７に示すように、予約処理装置Ａを、予約受付端末Ｂを介してユーザからの操作を受け付けるように構成してもよい。この場合には、入力部１及び出力部６は、インターネットやＬＡＮなどのネットワークＮＷを介して予約受付端末Ｂと通信する通信部となる。予約受付端末Ｂは、開始時間及びサービス内容を含む新規予約に必要なデータの入力を受け付ける操作部Ｂ１と、予約処理装置ＡとネットワークＮＷを介して通信可能な通信部Ｂ３であって、受け付けた新規予約が受付可能か否かを、予約処理装置Ａの予約受付可否判定部２０に判定させ、その判定結果を受信する通信部Ｂ３と、通信部Ｂ３が受信した判定結果を表示するディスプレイＢ２と、を有する。予約受付端末Ｂは、図示しないＣＰＵやメモリを有するコンピュータにより構成される。
【００５８】
以上のように、第１実施形態の予約処理装置Ａは、開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数Ｘを設定する変数設定部５０と、予め設定されたリソースに関するデータ及び予約に関するデータに基づき、予約に対するリソースの割り当て可否を表す第１の制約条件（Ｃ，Ｅ）を生成する第１制約条件生成部５１と、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件Ｄを生成する第２制約条件生成部５２と、第１の制約条件及び第２の制約条件を含む制約条件（Ｃ，Ｅ，Ｄ）を変数Ｘで表現した論理式を満たす変数Ｘの解をＳＡＴソルバに検索させるＳＡＴ処理実行部５４と、ＳＡＴソルバによる検索結果に基づいて予約に対するリソースの割り当て可否を判定する割当可否判定部５５と、を有する。
【００５９】
このように、予約とリソースの割り当て状態を表す複数の変数Ｘを設定し、予約とリソースの割当可否を表す第１の制約条件（ＣやＥ）を生成し、予約時間を考慮するための第２の制約条件Ｄを生成し、これら制約条件を変数Ｘの論理式に変換して、ＳＡＴソルバで解を得るので、割当問題を制約充足問題ではなく充足可能性問題に変換でき、現実的な時間内で割当可否を判定することが可能となる。
【００６０】
第１実施形態では、ＳＡＴ処理実行部５４は、系統的ソルバ５４ｂと確率的ソルバ５４ｃとを含む少なくとも二種類のＳＡＴソルバを並列に動作させ、検索結果が早い方の解を採用するように構成されている。
【００６１】
この構成によれば、解がないことを判定できるものの苦手な問題を有する系統的ソルバと、苦手な問題が少ないものの解がないことを判定できない確率的ソルバと、を並列に動作させて二重化しているので、解が見つからないといった発散状態に陥ることを避けて、現実時間内で解が見つかる確率を向上させることが可能となる。
【００６２】
さらに、第１実施形態では、予約の数をＮとし、リソースの数をＭとした場合に、複数の変数Ｘは、Ｎ×Ｍ個に設定される。このようにすれば、変数の数を必要最低限に抑えることができるので、計算コストの増大を抑制することが可能となる。
【００６３】
さらに、第１実施形態では、受付可能か否かの判定対象となる新規予約と、既存予約と、を合わせた複数の予約に対し、リソースとしてのサービス提供者が割り当て可能か否かを、割当可否判定部５５に判定させるとともに、
複数の予約に対し、リソースとしての施設が割り当て可能か否かを、割当可否判定部５５に判定させ、
サービス提供者及び施設の双方が割当可能と判定された場合に、新規予約が受付可能であると判定する一方、サービス提供者及び施設の少なくとも一方が割当不可能と判定された場合に、新規予約が受付不可能であると判定する予約受付可否判定部２０を、有する。
【００６４】
この構成によれば、サービスの提供にあたり、サービス提供者と施設の両方が必要となる業務に適用することが可能となる。
【００６５】
第１実施形態の予約受付端末Ｂは、開始時間及びサービス内容を含む新規予約に必要なデータの入力を受け付ける操作部Ｂ１と、予約処理装置ＡとネットワークＮＷを介して通信可能な通信部Ｂ３であって、受け付けた新規予約が受付可能か否かを、予約処理装置Ａの予約受付可否判定部２０に判定させ、その判定結果を受信する通信部Ｂ３と、通信部Ｂ３が受信した判定結果を表示するディスプレイＢ２と、を備える。このような予約受付端末Ｂは、ネットワークＮＷ経由で予約処理装置Ａを利用できるので、有用である。
【００６６】
第１実施形態の予約処理装置Ａは、次に述べる予約処理方法を実行することになる。すなわち、予約処理方法は、コンピュータが実行する方法であって、開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定するステップ（Ｓ２０２）と、予め設定されたリソースに関するデータ及び予約に関するデータに基づき、予約に対するリソースの割り当て可否を表す第１の制約条件を生成するステップ（Ｓ２０３）と、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成するステップ（Ｓ２０４）と、第１の制約条件及び前記第２の制約条件を含む制約条件を前記変数で表現した論理式を満たす前記変数の解をＳＡＴソルバに検索させるステップ（Ｓ２０６，Ｓ２０７）と、ＳＡＴソルバによる検索結果に基づいて予約に対するリソースの割り当て可否を判定するステップ（Ｓ２１０，Ｓ２１１）と、を有する。この方法を実行することによっても、上記装置と同様の作用効果を奏することが可能となる。
【００６７】
第１実施形態の予約処理装置Ａは、次に述べるコンピュータプログラムを実行することで実現可能となる。すなわち、コンピュータプログラムは、開始時間及び終了時間を有する複数の予約に対し、サービスの提供に必要なリソースの割り当て状態を表すための複数の変数を設定するステップ（Ｓ２０２）と、予め設定されたリソースに関するデータ及び予約に関するデータに基づき、予約に対するリソースの割り当て可否を表す第１の制約条件を生成するステップ（Ｓ２０３）と、予約の開始時間及び終了時間に基づき、時間が重複する複数の予約に対して同一のリソースが割り当て不可であることを表す第２の制約条件を生成するステップ（Ｓ２０４）と、第１の制約条件及び前記第２の制約条件を含む制約条件を前記変数で表現した論理式を満たす前記変数の解をＳＡＴソルバに検索させるステップ（Ｓ２０６，Ｓ２０７）と、ＳＡＴソルバによる検索結果に基づいて予約に対するリソースの割り当て可否を判定するステップ（Ｓ２１０，Ｓ２１１）と、をコンピュータに実行させる。
【００６８】
＜第２実施形態＞
本発明の第２実施形態に係る予約処理装置、予約処理方法、コンピュータプログラムについて説明する。なお、第１実施形態と共通の部分は同じ符号を付して説明を省略する。
【００６９】
図８に示すように、予約処理装置Ａ’は、制御部１０２を有する。制御部１０２は、上記予約受付可否判定部２０としても機能するとともに、代替予約生成部２１、代替予約抽出部２２としても機能する。
【００７０】
代替予約生成部２１は、入力部１に入力された顧客の希望である新規予約の代わりとなる代替予約を生成する。代替予約は、新規予約とは開始時間が異なるが、時間以外、例えばサービスの内容（種類、指定情報など）が同じ予約である。代替予約は、顧客の希望する開始時間で予約を受付することができない場合や、予約を受付することはできるが、店舗にとって有利な開始時間となるように顧客を誘導したい場合に利用できる。代替予約は、既に確定している既存予約の終了時間から開始すること、又は、既存予約の開始時間に終了することを条件としている。代替予約生成処理は、既存予約のデータを取得し、既存予約の開始時間及び終了時間に、顧客が希望する新規予約に要する時間を加減算することにより、代替予約の開始時間を算出し、代替予約を生成する。
【００７１】
代替予約生成処理を具体例を用いて説明する。図９Ａにて既存予約を斜線で示すように、１４：１０開始の３０分コースの既存予約１と、１４：１０開始の５０分コースの既存予約２とが存在する場合に、新規予約として１４：３０開始の４０分コースが希望されたとする。この場合、そのまま予約を受け付けると、同時間帯に最大３つの予約が重複するので、リソースの有効活用の面では好ましいとは言えない。そこで、代替予約生成部２１は、予約情報記憶部３に記憶されている既存予約に関するデータを参照し、既存予約の終了時間から開始すること又は既存予約の開始時間に終了することを条件とする代替予約を生成する。図９Ａの例では、既存予約が２つあるので、図９Ｂに示すように、各々の既存予約の開始時間に終了する代替予約と終了時間から開始する代替予約を計４つ生成する。代替予約１は、開始時間が１３：３０であり、既存予約１の開始時間１４：１０に終了する予約である。代替予約２は、開始時間が１３：４０であり、既存予約２の開始時間１４：２０に終了する予約である。代替予約３は、開始時間が１４：４０であり、既存予約１の終了時間１４：３０から開始する予約である。代替予約４は、開始時間が１５：１０であり、既存予約の終了時間１５：１０から開始する予約である。
【００７２】
代替予約抽出部２２は、代替予約生成部２１により生成された代替予約１〜４から、当該代替予約の開始時間と新規予約の開始時間の差が所定時間以下となる代替予約を抽出する。所定時間は予め設定されており、例えば３０分や４０分、１時間などが挙げられる。この処理は、顧客が希望する予約の開始時間から大幅な時間差がある代替案を提案することは好ましくない場合に、そのような代替予約を除去するために実行する。
【００７３】
代替予約抽出処理を具体例を用いて説明する。図９Ｂに示す例において、所定時間を５０分とすれば、図９Ｃに示すように、代替予約１〜４のうち、顧客希望の新規予約の開始時間１４：３０の前後５０分以内に開始時間が存在する代替予約２〜４が抽出される。代替予約１は、条件に合致しないために除外される。具体的には、代替予約１〜４毎に、代替予約の開始時間と新規予約の開始時間との差を算出する。そして、算出した時間差が５０分以下となる代替予約を検索する処理を行う。
【００７４】
上記割当検証部５が、代替予約抽出部２２により抽出された代替予約それぞれについて、代替予約と、既存予約と、を合わせた複数の予約に対し、サービスの提供に必要なリソースが割当可能か否かを判定する。勿論、第１実施形態のように予約受付可否判定部２０を介して割当検証部５に判断させてもよい。
【００７５】
出力部としての提示部１０６は、割当検証部５により割当可能と判定された代替予約を提示する。具体的には、割当可能と判定された１又は複数の代替予約を列挙する形でディスプレイに表示してもよく、ネットワークを介して他の装置のディスプレイに表示させてもよい。
【００７６】
上記装置の動作を、図８、図９Ａ〜Ｃ及び図１０を参照して説明する。まず、サービス内容及びその開始時間を含む新規予約に必要なデータが入力部１に入力されると（Ｓ３０１：ＹＥＳ参照）、ステップＳ３０２において、代替予約生成部２１が、既存予約記憶部３０に記憶されている既存予約データを取得する。次のステップＳ３０３において、代替予約生成部２１が、新規予約とサービス内容が同じであり、既存予約の終了時間から開始すること又は既存予約の開始時間に終了することを条件として代替予約を生成する。図９Ｂの例では代替予約１〜４が生成される。次のステップＳ３０４において、代替予約抽出部２２が、代替予約の開始時間と前記新規予約の開始時間の差が所定時間以下となる代替予約を抽出する。図９Ｃの例では代替予約１〜４から２〜４が抽出される。次のステップＳ３０５において、割当検証部５が、代替予約と既存予約とを合わせた予約に対してリソースが割当可能か否かを判定する。この判定処理は、代替予約２〜４全てについて個別に検証される。全ての代替予約が判定されると（Ｓ３０６：ＹＥＳ参照）、次のステップＳ３０７において、提示部１０６が、割当可能と判定された代替予約を提示する。
【００７７】
＜第２実施形態の変形例＞
第２実施形態では、代替予約抽出部２２を設けているが、代替予約抽出部２２を省略することも可能である。このようにすれば、店舗スタッフが利用する場合において、顧客に提示する代替予約に範囲に制限がないので、より選択肢の広い提案を容易に実施することが可能となる。
【００７８】
また、第２実施形態では、入力部１は、操作部を介して新規予約を受け付けるように構成されており、出力部６がディスプレイであり、予約処理装置Ａがいわゆるスタンドアロン型であったが、Ｗｅｂサーバなどのサーバクライアント型に構築しても良い。Ｗｅｂアプリケーションの場合、入力部１及び出力部６は、Ｗｅｂアプリケーションのインターフェイス（例えばＣＧＩ）となる。また、図７に示すように、予約処理装置Ａを、予約受付端末Ｂを介してユーザからの操作を受け付けるように構成してもよい。具体的構成は、上記で説明したのと同様である。すなわち、予約受付端末Ｂは、開始時間及びサービス内容を含む新規予約に必要なデータの入力を受け付ける操作部Ｂ１と、上記予約処理装置Ａ’とネットワークを介して通信可能な通信部Ｂ３であって、受け付けた新規予約に対応する代替予約のうち、割当検証部５により割当可能と判定された代替予約を受信する通信部Ｂ３と、通信部Ｂ３が受信した代替予約を表示するディスプレイＢ２と、を備える。
【００７９】
以上のように、第２実施形態の予約処理装置Ａ’は、サービス内容及びその開始時間を含む新規予約に必要なデータが入力される入力部１と、新規予約とサービス内容が同じ予約であって、既に確定している既存予約の終了時間から開始する又は前記既存予約の開始時間に終了する代替予約（１〜４）を生成する代替予約生成部２１と、代替予約（１〜４）それぞれについて、代替予約と、既存予約と、を合わせた複数の予約に対し、サービスの提供に必要となるリソースが割り当て可能か否かを判定する割当検証部５と、割当検証部５により割当可能と判定された代替予約を提示する提示部１０６と、を有する。
【００８０】
顧客が希望する開始時間の新規予約をそのまま受け付けると、同時間帯に重複する予約が増える場合や、予約と予約との間に無駄な空き時間が生じることがあり、リソースの有効活用の面では好ましいとは言えない。本実施形態のように構成されていれば、既存予約の開始時間に終了する又は既存予約の終了時間から開始するように代替予約が生成され、リソース割当の可否が判定され、割当可能と判定された代替予約を提示することができるので、同時間帯に重複する予約が増えることや、予約と予約との間に無駄な空き時間が生じることを抑制することが可能となる。
【００８１】
さらに、第２実施形態では、代替予約生成部２１により生成された代替予約から、代替予約の開始時間と新規予約の開始時間の差が所定時間以下となる代替予約を抽出する代替予約抽出部２２を有する。割当検証部５は、代替予約抽出部２２により抽出された前記代替予約についてリソースが割当可能か否かを判定する。この構成によれば、顧客が希望する予約の開始時間から大幅な時間差がある代替案を提案することを回避できるので、有用な提案ができる。それでいて、割当検証する代替予約の数を低減できるので、計算コストを低減することも可能となる。
【００８２】
第２実施形態の予約処理装置Ａ’は、次に述べる予約処理方法を実行することになる。すなわち、予約処理方法は、コンピュータが実行する方法であって、サービス内容及びその開始時間を含む新規予約とサービス内容が同じ予約であって、既に確定している既存予約の終了時間から開始する又は既存予約の開始時間に終了する代替予約（１〜４）を生成するステップ（Ｓ３０３）と、代替予約それぞれについて、当該代替予約と、既存予約と、を合わせた複数の予約に対し、サービスの提供に必要となるリソースが割り当て可能か否かを判定するステップ（Ｓ３０５）と、割当可能と判定された代替予約を提示するステップ（Ｓ３０７）と、を有する。この方法を実行することによっても、上記装置Ａ’と同様の作用効果を奏することが可能となる。
【００８３】
第２実施形態の予約処理装置Ａ’は、次に述べるコンピュータプログラムを実行することで実現可能となる。すなわち、コンピュータプログラムは、サービス内容及びその開始時間を含む新規予約とサービス内容が同じ予約であって、既に確定している既存予約の終了時間から開始する又は既存予約の開始時間に終了する代替予約（１〜４）を生成するステップ（Ｓ３０３）と、代替予約それぞれについて、当該代替予約と、既存予約と、を合わせた複数の予約に対し、サービスの提供に必要となるリソースが割り当て可能か否かを判定するステップ（Ｓ３０５）と、割当可能と判定された代替予約を提示するステップ（Ｓ３０７）と、をコンピュータに実行させる。
【００８４】
以上、本発明の実施形態について図面に基づいて説明したが、具体的な構成は、これらの実施形態に限定されるものでないと考えられるべきである。本発明の範囲は、上記した実施形態の説明だけではなく特許請求の範囲によって示され、さらに特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれる。
【００８５】
例えば、本実施形態では、リソースを、サービス提供者（施術者；トレーナ）と、施設として説明しているが、これに限定されない。また、１つの予約に対して２つのリソース（施術者と施設）を割り当てているが、これに限定されない。例えば、１つの予約に１つのリソースを割り当てるようにしてもよいし、１つの予約に３つ以上のリソースを割り当てるようにしてもよい。
【００８６】
例えば、第２実施形態において、割当検証部５は、第１実施形態で述べたＳＡＴソルバを用いた割当判定処理を実施しているが、第２実施形態で述べた代替予約を提示する発明において、予約に対するリソースの割当可否を判定することができれば、第１実施形態の内容に限定されない。例えば、特許文献１〜３、その他、何らかの方法により割当可否を判定するようにしてもよい。
【００８７】
各部の具体的な構成は、上述した実施形態のみに限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形が可能である。
【符号の説明】
【００８８】
Ａ，Ａ’…予約処理装置
２０…予約受付可否判定部
５０…変数設定部
５１…第１制約条件生成部
５２…第２制約条件生成部
５４…ＳＡＴ処理実行部
５４ｂ…系統的ソルバ
５４ｃ…確率的ソルバ
５５…割当可否判定部
Ｂ…予約受付端末
Ｂ１…操作部
Ｂ２…ディスプレイ
Ｂ３…通信部
【図１】
2015032159.tif 000028
【図２Ａ】
2015032159.tif 000029
【図２Ｂ】
2015032159.tif 000030
【図２Ｃ】
2015032159.tif 000031
【図３Ａ】
2015032159.tif 000032
【図３Ｂ】
2015032159.tif 000033
【図４Ａ】
2015032159.tif 000034
【図４Ｂ】
2015032159.tif 000035
【図５】
2015032159.tif 000036
【図６】
2015032159.tif 000037
【図７】
2015032159.tif 000038
【図８】
2015032159.tif 000039
【図９Ａ】
2015032159.tif 000040
【図９Ｂ】
2015032159.tif 000041
【図９Ｃ】
2015032159.tif 000042
【図１０】
2015032159.tif 000043