Modelos e algoritmos para variações modernas do problema de roteamento de veículos.

Abstract

Um problema clássico da Computação é o problema do Caixeiro Viajante ou Traveling Salesman Problem (TSP). Nele, um caixeiro deseja sair de uma cidade de origem, visitar um conjunto de n cidades distintas e retornar à cidade de origem, de forma a percorrer a menor distância total possível. Uma variação do problema envolve janelas de tempo (TSPTW), ou seja, para cada cidade, o caixeiro deseja visitá-la em um tempo pré-determinado. Um algoritmo exato para o problema do TSPTW foi proposto por Balas. Outra variação mais recente do problema, envolve, além das janelas de tempo, o percorrimento da rota em um veículo elétrico (E-TSPTW). Neste caso, é necessário, o controle de carga e descarga da bateria do veículo. O problema e as variações citadas são NP-difíceis. Neste trabalho, adaptou-se o algoritmo proposto por Balas que resolve o TSP com janelas de tempo para resolver o TSP com janelas de tempo e carro elétrico (E-TSPTW).