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

Abstract

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.