Planeamento de rotas para técnicos com diferentes habilidades

O problema Skill Vehicle Routing Problem estudado neste trabalho consiste em determinar rotas para vários técnicos com diferentes especialidades de forma a visitarem os clientes satisfazendo os seus pedidos de serviço consoante a especialidade requisitada e na janela temporal especificada. O objetivo é estudar o Skill Vehicle Routing Problem, comparando o desempenho da heurística de melhoramento LNS com um método exato de programação linear inteira, medindo os tempos de execução e soluções encontrados em ambas as alternativas. Para obter as soluções pelo método exato são propostos dois modelos em programação linear inteira, um que considera a existência de apenas um técnico em cada especialidade e outro a de vários técnicos por especialidade. Ambos os métodos foram implementados em Python, sendo que no método exato foi usado o software de otimização Xpress. Foram testadas seis variações do problema todas elas com 20 amostras e 3 especialidades. Na primeira variação existem 20 clientes, 30 clientes na segunda variação e 40 clientes na terceira variação. Após a análise dos resultados apresentados pelos 2 modelos para as várias instâncias pode-se concluir que o método exato é melhor nas situações em que existem poucos clientes, ou quando existem mais de 30 clientes, mas é possível deixar a correr o Xpress mais tempo. Caso não se possa deixar correr esse tempo deve-se usar a metaheurística LNS no caso de 40 clientes quando o número de técnicos é suficiente para satisfazer as necessidades dos clientes e não existe folga de técnicos, causando ótimos locais.