Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Neste trabalho foram avaliadas matheurísticas para construir soluções viáveis para dois problemas de otimização combinatória, cujas formulações por programação linear inteira são modelos estendidos. As matheurísticas utilizadas foram a Relax&Fix, baseada na relaxação linear e a Large neighborhood search, baseada na destruição e reparo de uma solução já existente. Os modelos estendidos usados para avaliação foram originados de dois problemas, problema da rota lucrativa capacitada e problema de roteamento com frota particular e terceirizada, de modo que as matheurísticas foram utilizadas para resolver o subproblema de seleção de colunas após o uso da relaxação ng-route para resolver o pricing, relaxação esta a qual pode ser aplicada de forma heurística. Os resultados obtidos indicaram que o uso de ng-route heurístico e o uso das matheurísticas em alguns nos da árvore de enumeração de Branch&Price obtiveram os melhores resultados entre as abordagens propostas.