ホテルの部屋の最適化/ソートアルゴリズム

Question

ホテルの部屋の最適化/ソートアルゴリズムはよく知られていますか？

問題は、占有率を最大にするために部屋を再分配することです。すべての予約で10部屋、開始日、終了日があるとします。一部の部屋は、他の人が（フラグを立てる）ことができる間に配置することはできません。

正しい方向へのヒントはすばらしいでしょう。ありがとうございました。

Answer 1

Drools-Planerを検索する：http://www.jboss.org/drools

Answer 2

予約数と部屋数が固定されている場合は、利用状況を最大限に引き出す方法ではなく、予約が実際に実現できるかどうかを確認することです。すべての予約が実現されれば、利用は明らかに同じままです。

もう1つの可能性のあるユースケースは、実現可能であることがわかっている一連の予約をしてから、新しい予約を入れることです。つまり、新しい顧客が新しい予約をしたい場合、新しい予約のために予約の一部を再配置することができます。

どちらの場合でも、実際の問題は、所定の予約セットが実現できるかどうかを確認する方法です。

リロケータブルでない予約については、これは自明なので、実現可能であり、再配置可能な予約が実現可能かどうかを確認したいと考えてください。

最初のチェックは、毎晩、その1泊あたりの予約数を計算することです。夕方に予約の数が利用可能な部屋の数を超えた場合は、固定予約が計上されると、あなたはどんなトリックで予約を実現することはできません。あなたのホテルはその夜の予約を超過しています。

それ以外の場合は、の解決策を試すことができます。開始日の順番で予約を処理し、利用可能な最初の部屋（たとえば部屋の数値順）に予約ごとに予約します。これにより解決策が得られれば、あなたは予約を実現し、完了しました。

問題が解決しない場合は、GRAPH COLORINGを使用して問題を解決することができます。これが普遍的な解決策です。すべての予約がノードであり、時間的に重複する場合にのみ2つのノード（予約）が接続されるグラフを作成します。 固定（再配置不可能）予約をグラフに含めます。 N個の色（N =ホテル内の部屋の総数）のグラフの完全な色付けをしようとすると、それに関係する部屋番号で固定予約を事前に色づけします。

部屋nで予約が実現できない場合に限り、予約rから部屋nの特別なn-precoloredノードへのリンクを追加して、この方法で部分的に柔軟な予約も処理できます（たとえば、 ）。

この同じグラフの着色アルゴリズムは、レジスタの割り当てのためのコンパイラで。

もちろん、問題はグラフの色付けを効率的に実装する方法です。そのためには既成の実装があります。

幸運を祈る！

Answer 3

バックトラックは、私の経験では、このような問題のためにかなりうまく機能します。最初の予約をルームタイプに割り当てることから始めてください。未割り当てのままになるまで予約を割り当て続けます。その後、あなたが間違っていた場所をバックトラックし、それに応じて以前の決定を変更します。

この方法では、実現可能な解決策が見つかるか、または存在しないことが証明されます。

利点は、実現不可能であることを証明できることです。さらに、バックトラッキングにより、実現不可能の「原因」を見つけることができます。

http://en.wikipedia.org/wiki/Backtracking

Answer 4

それは、数理計画または制約が多くすぐ利用可能なツールの上で使用して、をプログラミングを使用して、あなたの問題をモデル化することが可能である（またはMPのためgurobiとgecodeまたはCP CPLEX を試してみてくださいオプティマイザ、CPの場合のみ）、これらのクラスの問題をモデル化して解決します。彼らは通常、ほとんどのプログラミング言語から呼び出すことができるAPIを持っています。

私はこの答えは非常に長い時間後に到着したと思いますが、私はそれはまだ