UM MODELO EXATO PARA O ORIENTEERING PROBLEM COM SELEÇÃO DE HOTÉIS

O Orienteering Problem com seleção de hotéis (OPHS) considera um conjunto de hotéis e um conjunto de clientes, onde cada cliente possui uma pontuação pré-estabelecida. O problema visa determinar um número fixo de viagens conectadas, começando e terminando em um dos hotéis, limitadas em tempo, que maximize a soma das pontuações obtidas ao visitar os clientes. Para resolver o problema, propomos pela primeira vez um modelo exato, consistindo em um algoritmo de Branch-and-Cut-and-Price implementado com auxílio da ferramenta computacional VRPSolver. O diferencial do modelo proposto é que este considera variáveis para as viagens ao invés das jornadas completas. A concatenação das viagens é garantida através de variáveis e restrições que são incluídas no problema mestre. O modelo foi aplicado em instâncias propostas na literatura com até 102 nós, 8 hotéis e 4 viagens. Resultados mostram que o modelo encontrou a solução ótima para 165 dentre as 175 instâncias testadas.