OTIMIZAÇÃO COMBINATÓRIA: PROGRAMAÇÃO LINEAR INTEIRA, ALGORITMOS E O PROBLEMA DE ROTEIRIZAÇÃO

  • Matheus Vieira Ribeiro
  • Gudelia Morales
Palavras-chave: Otimização discreta, Roteirização, Logística reversa

Resumo

O projeto consiste no estudo de algoritmos de otimização combinatória inteira a serem usados na tomada de decisões discretas para obter a melhor solução possível dentro de um número finito de alternativas. O objetivo principal é aplicar algoritmos exatos para problemas de roteirização de veículos. O estudo se justifica pela capacitação de pessoas no desenvolvimento destes métodos para fornecer suporte à área de logística, setor de grande importância para a otimização de recursos das indústrias. No projeto, em fase inicial, foram feitas revisões bibliográficas sobre otimização combinatória, modelos de Programação Linear Inteira e estratégias de solução que utilizem o método Simplex. Estudou-se o algoritmo branch-and-bound e logo será o branch-and-cut. Eles utilizam estratégias dividir para conquistar, enumeração implícita e planos de corte. Consiste em dividir um problema P em um conjunto de subproblemas menores de forma que a solução de P possa ser obtida através da solução dos subproblemas. As divisões são feitas iterativamente, resultando em subproblemas de mais fácil resolução que o problema original e facilitando identificar subproblemas a descartar por não ter a solução ótima. Alguns problemas encontrados na literatura foram testados como exemplo em softwares de otimização tais como, Solver do Excel e Tora com o objetivo de facilitar o aprendizado do método branch-and-bound, pois a verificação manual de possíveis combinações torna-se exigente. Iniciou-se o uso do ambiente computacional Scilab 3.0 e que se pretende continuar no decorrer do projeto. Facilitou-se o entendimento das estratégias utilizadas nos algoritmos. Finalmente o uso de tais ferramentas computacionais traz uma maior familiaridade com os recursos disponíveis, trazendo assim um maior aproveitamento de informações relevantes e uma melhoria na interpretação de resultados. Distribuição ou coleta de bens com limitações de capacidade e demandas, por exemplo, a coleta seletiva efetuada por prefeituras leva à necessidade de uma modelagem via programação linear inteira. A otimização combinatória e algoritmos exatos, facilitam a resolução eficiente do problema roteirização.

Biografia do Autor

Matheus Vieira Ribeiro
Universidade Estadual do Norte Fluminense – UENF – CCT – LEPROD
Gudelia Morales
Universidade Estadual do Norte Fluminense – UENF – CCT – LEPROD