Programação Inteira para o Problema de Roteamento de Veículos

O Problema de Roteamento de Veículos (PRV) é um dos problemas de natureza combinatória mais estudados no campo de estudo de pesquisa operacional, que consiste em encontrar o menor caminho percorrido no atendimento de uma frota de veículos para um conjunto de clientes. Todos os veículos partem de um ponto de origem em comum denominado depósito. Cada cliente possui uma determinada demanda a ser suprida por um veículo, essa um as demandas podem ser diferentes para cada cliente. Cada um destes veículos possuem carga máxima, que deve ser maior ou igual a soma das demandas dos clientes que determinado veículo atenderá.
O interesse neste problema parte de sua aplicação prática, que pode auxiliar na decisão de diversas empresas ao construir uma solução para seu problema, que visa minimizar o custo necessário ou maximizar o lucro ao atender seus clientes. Entretanto, encontrar a melhor solução para este problema se torna uma tarefa difícil se realizado de maneira analítica, devido à quantidade elevada de combinações possíveis de rotas existentes. Devido a isto, a necessidade de um processo automatizado computacional se torna expressivo. Portanto, utilizando pesquisa operacional, o presente trabalho tem como objetivo o desenvolvimento de um modelo matemático exato de programação inteira para o PRV, como também, através da biblioteca IBM CPLEX para a linguagem C++, a aplicação computacional deste modelo.
No modelo desenvolvido é utilizada uma matriz binária tridimensional para representar as rotas que cada veículo da frota realiza, dentre estas dimensões estão os veículos, os clientes, e em qual tempo cada cliente é atendido. Um veículo pode em sua rota visitar uma mesma cidade mais de uma vez, assim como visitar uma cidade que outro veículo também visitou, aumentando o número de possibilidades, o que ocasiona em melhores chances de encontrar rotas de menor custo. Por ter a possibilidade de dois ou mais veículos visitarem um mesmo cliente, se torna necessária alguma forma de determinar quais destes veículos definitivamente atendeu cada cliente. Para isto é utilizada uma matriz binária bidimensional, cuja as dimensões são compreendidas em veículos e clientes.
A saída resultante do modelo desenvolvido é uma sequência de cidades para cada veículo, representando as rotas realizadas por cada um. A complexidade computacional para determinar a solução exata para o PRV é de ordem NP-difícil. Em instâncias com poucos clientes o tempo necessário para completar a tarefa se mostrou relativamente pequeno. Porém como a complexidade cresce exponencialmente para a presente solução exata deste modelo, há casos em que adicionar apenas uma cidade na instância torna inviável sua solução por demandar demasiado tempo.