Problema da distribuição Hoteleira
UnB-\(\gamma\)
Table of Contents
1. Preâmbulo
Joca DivideQuarto é um organizador de eventos reconhecido na região do Distrito Federal por realizar eventos pomposos. No entanto, com o passar dos anos, Joca percebeu que sua idade avançada está afetando sua agilidade e eficiência na realização de tarefas de eventos.
Um dos problemas que Joca enfrenta é alocar os participantes de seus eventos em hotéis, uma tarefa que se tornou cada vez mais desafiadora à medida que o número de participantes aumenta. Com casais viajando juntos e irmãos preferindo ficar juntos nos quartos, a distribuição adequada das pessoas tornou-se ainda mais complexa.
Além disso, a distribuição de quartos também deve levar em consideração as preferências dos participantes em relação às localizações dos quartos, vistas panorâmicas, facilidades de acesso, tamanhos de cama, serviços de quarto, dentre outros fatores. Esses fatores podem influenciar na satisfação dos participantes e, consequentemente, na avaliação geral do evento.
Desta forma, Joca está enfrentando um grande desafio ao tentar alocar todos os participantes nos melhores quartos, de acordo com suas preferências individuais, de modo a garantir uma experiência agradável para todos. Para superar esse desafio, Joca pode buscar a ajuda de ferramentas de gestão de eventos, que podem auxiliá-lo na organização e distribuição dos quartos de forma mais eficiente e personalizada, atendendo às expectativas de cada participante.
2. Problemática
O problema da distribuição hoteleira consiste em alocar um conjunto de pessoas em um conjunto de quartos em um hotel.
3. Entrada
3.1. Quartos
A entrada é composta por um conjunto de quartos, que possuem a seguinte disposição:
- Quarto de cama de casal
- Quarto Duplo
- Quarto Triplo
- Quarto Quádruplo
Além das quantidades de cada quarto, é passado o custo de uma diária do quarto.
Os quartos possuem numeração de forma que diferenciam os andares a qual pertencem e também números sequenciais representam quartos adjacentes.
3.1.1. Sobres os custos
Na entrada, é especificado o preço por quarto individualmente, mesmo que existam \(k\) quartos duplos, cada um dos \(k\) quartos podem ter tarifas diferentes.
3.1.2. Exemplo de entrada quartos
A entrada de descrição dos quartos é composta por diversas linhas, a primeira linha possui um número inteiro \(T\), representando o total de quartos, depois existirão \(T\) linhas \(Q_i\), cada uma representando o tipo de quarto e o preço. As letras podem ser:
C- para quarto de casal (1 cama king inseparável)D- para quarto duplo ( 2 camas de solteiro que podem ser unidas e se transformar em uma cama de casal)T- para quarto triplo ( 3 camas de solteiro que podem ser unidas e se transformar em uma cama de casal)Q- para quarto quádruplo ( 4 camas de solteiro que podem ser unidas e se transformar em duas camas de casal)
Abaixo um exemplo:
10 C 100 C 150 C 1000 D 150 D 200 T 250 T 600 T 250 Q 360 Q 990
3.2. Hóspedes
A entrada referente aos hópostes é composta por uma alocação única. Para cada pessoa ela informa alguns parâmetros
- Se é casal e quem é o par
- O casal pode compartilhar quarto com outras pessoas?
- Quando não for casal, informa uma lista de pessoas que prefere dividir o
quarto, com um nível de preferência dividido em:
- intervalo \([0,100]\) sendo:
- \(0\) não quer dividir com aquela pessoa (de jeito nenhum!)
- \(100\) quero dividir obrigatoriamente com a pessoa
- O padrão é \(50\)
- Quando há conflito entre os valores o que deve ser feito?
- Estratégias diferentes são incentivadas
- Por padrão, pessoas de sexos diferentes atribuem \(0\) para todos, e \(50\) para o mesmo sexo
- intervalo \([0,100]\) sendo:
A entrada, para os hóspedes, é composta por diversas linhas. A primeira linha possui um número inteiro \(M\) seguido do caractere \(M\), representando a quantidade de pessoas do sexo Masculino. A segunda linha possui \(M\) nomes, representando todas as pessoas do sexo Masculino. A terceira linha, do caso de teste, possui o inteiro \(F\) seguido do caractere \(F\), representando a quantidade de pessoas do sexo feminino. A quarta linha possui \(F\) nomes, representando todas as pessoas do sexo feminino.
A quinta linha do caso de teste possui um número inteiro \(C\), e o caractere \(C\), representando a quantidade de casais, seguido de \(C\) linhas, cada uma com um par de nomes, representando os casais.
Na linha \(C+6\) haverá um número inteiro \(P\), representando a
quantidade de pessoas que informaram uma preferência. Depois haverão
\(P\) linhas contendo as preferências das pessoas. As linhas de
preferência são compostas pelo Nome da pessoa, seguida por um espaço e
um caractere de :, depois existirão diversos pares de Nome e nota,
indicando a preferência da pessoa em ficar com aquela indicada. Os
casais são implícitos que querem ficar juntos, mas mesmo assim podem
apontar algumas preferências, caso não seja possível.
Abaixo segue um exemplo:
5 M Bruno Otaviano Casimiro Igor DavyJones 4 F Iasmine Chris Vanessa Rose 2 C Bruno Rose Otaviano Vanessa 9 Bruno : Casimiro 20 Otaviano : Igor 40 Iasmine 65 Casimiro : Igor 0 DavyJones 2 Igor : DavyJones 90 DavyJones : Bruno 70 Igor 70 Iasmine : Chris 90 Vanessa 30 Igor 40 Chris : Iasmine 90 Vanessa 45 Rose 90 Vanessa : Otaviano 100 Iasmine 60 Chris 60 Rose : Vanessa 70 Chris 80
4. Objetivo
O objetivo deste trabalho é acomodar todas as pessoas em quartos no hotel. A acomodação depende de alguns fatores:
- OTIMIZAÇÕES BÁSICAS ( Obrigatória para todos os grupos)
- Honrar todos os pedidos
- Se não for possível honrar todos os pedidos:
- Alocar considerando somente o desejo dos casais e Sexos;
- Somente a regra dos sexos;
- Definir alguma métrica para atender o máximo de desejos possíveis
4.1. Métricas adicionais
- Inventar estratégias para:
- minimizar custo
- maximizar conforto
- cobrança de taxas extras
- considerar proximidade dos quartos
- entre outras…
5. Entrega e Apresentações
5.1. Apresentação
- Dias
13 e 1527 e 29 de junho - A equipe deve estar completa
- Um dos membros será sorteado para apresentar
- outros podem complementar
- O que apresentar?
- Definição rápida da problemática
- Formulação
- O algoritmo que escreve a formulação
- Experimentos Resultados
- Conclusão
5.2. Artigo Científico - Relatório
- Cada equipe entregará um artigo científico e a apresentação (slides)
- O que deve ter no artigo?
- Introdução (definição da problemática)
- Pesquisa de formulação semelhante (trabalhos relacionados)
- Formulação proposta
- Como codificar a formulação
- pysathq? Como usa?
- solver direto na fórmula pseudo-booleana (qual solver e parâmetros)
- Como é o algoritmo que gera a codificação e qual a estratégia
para chavear entre os objetivos
- múltiplas fórmulas?
- conseguiu formular tudo em uma única fórmula
- Experimentos
- Rodar o conjunto de entradas (compartilhadas por todos)
- cada equipe deve gerar ao menos 10 entradas, e compartilhar com todos
- Todos os grupos devem rodar todos os casos de teste para as otimizações básicas
- Utilizar as máquinas abaixo da chococino
- cm{1..4} são iguais, bem como pos{1..2} e gpu{1..3}
- usar o timelimit mínimo de $600$s.
- Rodar o conjunto de entradas (compartilhadas por todos)
- Conclusão
- Idioma do artigo: português ou inglês
- Os melhores artigos serão selecionados para serem melhorados e para possível submissão no ENIAC - 26 de junho
- Limite de \(14000 \leq C \leq 42000\) caracteres