Um método Branch and Bound para o problema do caixeiro viajante com janelas de tempo e veículo elétrico

Abstract

O Problema do Caixeiro Viajante, ou Traveling Salesman Problem (TSP), consiste em encontrar a rota de menor custo que visita um conjunto de cidades exatamente uma vez e retorna ao ponto de partida. Este trabalho foca no desenvolvimento e na implementação de algoritmos baseados em programação dinâmica para variantes do problema que envolvem restrições de tempo e de consumo energético. O estudo tem como base o algoritmo exato de Balas (1999), sua extensão proposta por Balas e Simonetti (2001) para o Problema do Caixeiro Viajante com Janelas de Tempo (TSPTW) e o modelo apresentado por Roberti e Wen (2016) para o Problema do Caixeiro Viajante Elétrico com Janelas de Tempo (E-TSPTW). O algoritmo de Balas constrói um grafo acíclico dirigido (DAG) com uma única fonte s e um único sorvedouro t. Uma tour viável no TSP restrito corresponde a um caminho neste grafo de s até t. O mecanismo de ramificação (branching) do espaço de busca é, portanto, descrito pela própria estrutura do grafo. A partir dessas formulações, foi desenvolvida uma adaptação do algoritmo para considerar simultaneamente as janelas de tempo, o consumo de bateria dos veículos e as paradas em estações de recarga. Durante a construção do grafo, utilizamos limites de consumo de bateria e a estimativa de custo de rotas parciais para podar (bound) caminhos subótimos do espaço de busca. A implementação foi testada utilizando instâncias apresentadas por Roberti e Wen (2016), reproduzindo os resultados de distância reportados no artigo e confirmando o funcionamento do algoritmo desenvolvido.