Thuật toán phân loại/tối ưu hóa phòng khách sạn

Question

Có thuật toán phân loại/tối ưu hóa phòng nổi tiếng nào cho khách sạn không?

Vấn đề là phân phối lại phòng để tối đa hóa số người dùng. Giả sử tôi có 10 phòng, ngày bắt đầu và ngày kết thúc cho mỗi lần đặt trước. Một số phòng không thể được giao trong khi những phòng khác có thể (gắn cờ).

Bất kỳ gợi ý nào về hướng đi đúng sẽ tuyệt vời. Cảm ơn bạn.

Answer 1

Bạn muốn tìm kiếm Drools-Planer: http://www.jboss.org/drools.

Answer 2

Nếu bạn có một bộ đặt chỗ và một số phòng cố định thì câu hỏi không phải là cách tối đa hóa việc sử dụng nhưng để xác minh xem đặt phòng có thực sự được nhận ra hay không. Việc sử dụng rõ ràng vẫn giữ nguyên nếu tất cả các đặt phòng được thực hiện. Một trường hợp sử dụng có thể khác là bạn có một tập hợp đặt chỗ mà bạn biết có thể được nhận ra, và sau đó bạn cố gắng đặt chỗ mới, tức là khách hàng mới muốn đặt chỗ mới và bạn muốn kiểm tra xem liệu có phải đặt trước hay không. bạn có thể di chuyển một số đặt phòng để tạo phòng cho phòng mới.

Trong cả hai trường hợp, câu hỏi thực tế là cách kiểm tra xem có thể nhận được một bộ đặt trước nhất định hay không.

Đối với các đặt phòng không thể định vị lại, điều này là tầm thường, vì vậy giả sử chúng có thể được thực hiện và bạn muốn kiểm tra xem các đặt phòng có thể định vị lại có thể được nhận ra không.

Séc đầu tiên là tính toán cho mỗi đêm số lần đặt trước cho mỗi đêm đó; nếu vào bất kỳ đêm nào số lượng đặt phòng vượt quá số lượng phòng có sẵn sau khi đặt phòng cố định được tính cho bạn không thể nhận ra các đặt phòng bằng bất kỳ thủ thuật nào; khách sạn của bạn được đặt trước quá nhiều cho đêm đó.

Nếu không, bạn có thể sử dụng thuật toán tham lam để thử giải pháp: xử lý đặt trước theo thứ tự ngày bắt đầu và đặt mọi đặt phòng vào phòng đầu tiên (ví dụ: theo thứ tự số). Nếu điều này cung cấp cho bạn một giải pháp, sau đó bạn đã nhận ra các đặt phòng và bạn đã hoàn tất.

Nếu điều đó không hiệu quả, thì bạn có thể sử dụng GRAPH COLORING để giải quyết vấn đề, và đây là giải pháp phổ quát. Xây dựng một đồ thị, nơi mỗi đặt phòng là một nút và hai nút (đặt phòng) được kết nối nếu và chỉ khi chúng chồng chéo thời gian khôn ngoan. Bao gồm đặt chỗ cố định (không thể di chuyển) trong biểu đồ. Sau đó, cố gắng làm màu hoàn chỉnh của đồ thị với N màu sắc (N = tổng số phòng trong khách sạn của bạn) một khi bạn đã đổi màu các đặt phòng cố định với số phòng mà họ liên quan đến.

Bạn cũng có thể xử lý các đặt chỗ linh hoạt một phần theo cách này, thêm liên kết từ đặt trước đến nút đặc biệt n cho phòng n nếu và chỉ khi đặt phòng KHÔNG được thực hiện trong phòng n (ví dụ: phòng thấp hơn).

Thuật toán tô màu đồ thị này được sử dụng thành công, ví dụ: trong các trình biên dịch để phân bổ đăng ký.

Tất nhiên sau đó câu hỏi là làm thế nào để thực hiện màu đồ thị hiệu quả; cho rằng có sẵn sàng thực hiện.

Chúc may mắn!

Answer 3

Tính năng quay lại hoạt động khá tốt cho những vấn đề như vậy, theo kinh nghiệm của tôi.Chỉ cần bắt đầu bằng cách chỉ định đặt phòng đầu tiên cho loại phòng. Tiếp tục chỉ định đặt chỗ cho đến khi một người vẫn chưa được chỉ định. Sau đó, quay lại nơi bạn đã đi sai, và thay đổi quyết định trước đó cho phù hợp.

Bằng cách này, bạn sẽ tìm thấy một/tất cả các giải pháp khả thi (s), hoặc bạn sẽ chứng minh rằng không tồn tại.

Ưu điểm là bạn có thể chứng minh tính không khả thi. Hơn nữa, backtracking cho phép bạn tìm ra "nguyên nhân" của tính không khả thi.

Xem ví dụ: http://en.wikipedia.org/wiki/Backtracking

Answer 4

Có thể để mô hình hóa vấn đề của bạn sử dụng lập trình toán học hoặc chế lập trình, sử dụng trên của nhiều công cụ sẵn có sẵn (thử cplex hoặc gurobi cho MP và gecode hoặc cp trình tối ưu hóa cho CP, chỉ để đặt tên một vài) để lập mô hình và giải các lớp vấn đề này. Họ thường có các API có thể được gọi từ hầu hết các ngôn ngữ lập trình.

Tôi đoán câu trả lời này đến sau một thời gian rất dài, nhưng tôi hy vọng nó vẫn có thể giúp người khác :-)