Novas formulações de fluxo para problemas de otimização combinatória

Novas formulações de fluxo para problemas de otimização combinatória

Author Silva, Tiago Tiburcio da Google Scholar
Advisor Chaves, Antônio Augusto Google Scholar
Graduate program Pesquisa Operacional
Abstract Neste trabalho aborda-se o Problema de Minimização de Trocas de Ferramentas (PMTF) e o Problema do Caixeiro Viajante Multiproduto com Prioridades (PCVMP). O PMTF consiste em determinar um sequenciamento de tarefas, de tal modo que a quantidade de trocas de ferramentas entre as tarefas seja a menor possível. Cada tarefa requer um conjunto de ferramentas distinto, e supõe-se que cada um destes conjuntos não contenha mais ferramentas do que suporta a máquina. Já o PCVMP consiste em determinar uma rota de entrega de mercadorias considerando ao mesmo tempo, o cliente e o vendedor, ou seja, minimizando os custos totais do vendedor e maximizando as preferências dos clientes. Neste estudo tem-se como objetivo modelar, baseado em fluxo multicommodity, os problemas citados. Modelos matemáticos de otimização foram propostos assim como alguns resultados teóricos foram desenvolvidos. No caso do PMTF, o melhor modelo proposto foi comparado com os modelos existentes na literatura, mostrando um melhor desempenho tanto em quantidade de instâncias resolvidas na otimalidade, quanto no valor da relaxação linear e no tempo de execução. Mostrou-se que o valor da relaxação linear nos modelos propostos corresponde a diferença entre a quantidade de ferramentas e a capacidade da máquina. Algumas matheurísticas baseadas em busca por proximidade e um método exato enumerativo considerando eliminação de simetria foram propostos e comparados com os resultados da literatura. Já no caso do PCVMP, o modelo proposto se mostrou eficiente em resolver instâncias de pequeno e médio porte. Duas metaheurísticas, BRKGA e BRKGA adaptativo, ambas com busca local, também foram propostas para o PCVMP, apresentando bons resultados.
Keywords Otimização combinatória
Modelos matemáticos
Problema do caixeiro viajante
xmlui.dri2xhtml.METS-1.0.item-coverage São José dos Campos
Language Portuguese
Sponsor Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Date 2020-02-18
Knowledge area Outra
Publisher Universidade Federal de São Paulo
Extent 164 f.
Access rights Open access Open Access
Type Thesis
URI https://repositorio.unifesp.br/handle/11600/53235

Show full item record




File

Name: tese_tiburcio_unifesp.pdf
Size: 3.288Mb
Format: PDF
Description:
Open file

This item appears in the following Collection(s)

Search


Browse

Statistics

My Account