Mathematical models and heuristic algorithms for routing problems with multiple interacting components.

Nenhuma Miniatura disponível
Data
2021
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Muitos problemas de otimização com aplicações reais têm vários componentes de interação. Cada um deles pode ser um problema pertencente à classe N P-difícil, e eles podem estar em conflito um com o outro, ou seja, a solução ótima para um componente não representa necessariamente uma solução ótima para os outros componentes. Isso pode ser um desafio devido à influência que cada componente tem na qualidade geral da solução. Neste trabalho, foram abordados quatro problemas de roteamento complexos com vários componentes de interação: o Double Vehicle Routing Problem with Multiple Stacks (DVRPMS), o Double Traveling Salesman Problem with Partial Last-InFirst-Out Loading Constraints (DTSPPL), o Traveling Thief Problem (TTP) e Thief Orienteering Problem (ThOP). Enquanto os DVRPMS e TTP já são bem conhecidos na literatura, os DTSPPL e ThOP foram recentemente propostos a fim de introduzir e estudar variantes mais realistas dos DVRPMS e TTP, respectivamente. O DTSPPL foi proposto a partir deste trabalho, enquanto o ThOP foi proposto de forma independente. Neste trabalho são propostos modelos matemáticos e/ou algoritmos heurísticos para a solução desses problemas. Dentre os resultados alcançados, é possível destacar que o modelo matemático proposto para o DVRPMS foi capaz de encontrar inconsistências nos resultados dos algoritmos exatos previamente propostos na literatura. Além disso, conquistamos o primeiro e o segundo lugares em duas recentes competições de otimização combinatória que tinha como objetivo a solução de uma versão bi-objetiva do TTP. Em geral, os resultados alcançados por nossos métodos de soluções mostraram-se melhores do que os apresentados anteriormente na literatura considerando cada problema investigado neste trabalho.
Descrição
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Palavras-chave
Programação linear, Heurística, Otimização combinatória
Citação
CHAGAS, Jonatas Batista Costa das.Mathematical models and heuristic algorithms for routing problems with multiple interacting components. 2021. 132 f. Tese (Doutorado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2021.