Otimização do dimensionamento e roteamento de navios de linha regular com viagens fretadas

Resumo: Este trabalho aborda um problema de planejamento tático em empresas de transporte marítimo de carga que coletam e entregam as demandas contratadas por seus clientes. As viagens associadas a estas demandas são obrigatórias, mas a empresa pode também atender a demandas spot associadas com viagens opcionais para aumentar seu lucro durante um horizonte de tempo de médio prazo. O problema de otimização é formulado como um modelo de programação inteira mista que é definido em um grafo orientado em que nós representam viagens obrigatórias e opcionais. As decisões do modelo são determinar o número e tipo de navios que compõem a frota, designar um navio a um conjunto de viagens obrigatórias e opcionais, definir as rotas de cada navio e estipular os tempos de início de atendimento nos portos para cada viagem. Um algoritmo de busca tabu com uma lista de candidatos e um conjunto de soluções de elite são propostos para resolver instâncias do problema. Os resultados computacionais da busca tabu são comparados com as soluções ótimas e sub-ótimas encontradas pelo CPLEX para o modelo de programação inteira mista.Abstract: We address a tactical planning problem faced by many liner shipping companies that have committed contractual voyages while trying to serve optional spot voyages to increase its revenue over the medium-term horizon. The optimization problem is formulated as a mixed integer programming model that is defined on a directed graph whose nodes represent contractual and spot voyages. The decisions include the number and type of vessels deployed the assignment of vessels to contractual and spot voyages and the determination of vessel routes and schedules in order to maximize the profit. A tabu search algorithm with a candidate list and a pool of elite and diverse solutions is proposed in order to solve a set of benchmark instances of the problem. The results obtained by tabu search are compared to optimal and suboptimal solutions yielded by the CPLEX solver to the mixed integer programming formulation of the problem