Roteirização e Programação em

Transportes

TSP - MTSP
Problema do Caixeiro-Viajante (Traveling
Salesman Problem – TSP)

Prof. Felipe Caleffi

1
 TSP
• O Problema do Caixeiro Viajante (TSP) é um problema que tenta
determinar a menor rota para percorrer uma série de cidades
(visitando uma única vez cada uma delas), retornando à cidade de
origem.

• Ele é um problema de otimização NP-difícil (NP-completo)

inspirado na necessidade dos vendedores em realizar entregas em
diversos locais (as cidades) percorrendo o menor caminho
possível, reduzindo o tempo necessário para a viagem e os
possíveis custos com transporte e combustível.

2
NP-difícil (NP-completo)?

3
 NP-difícil
• A classe NP, do acrônimo de Tempo Polinomial não Determinístico
(Non-deterministic Polynomial time), deriva da teoria fundamentada por
Cook (1971) e, como o próprio nome sugere, é composta por
problemas com instâncias de médio e grande porte que são
intratáveis por algoritmos determinísticos em tempo polinomial,
devido ao consumo demasiado de recursos computacionais.

• Desde então, o desenvolvimento de métodos heurísticos ganhou

bastante evidência na resolução dos problemas de otimização,
como é o caso do PCV.

Cook, S. A. (1971) The complexity of theorem-proving

procedures. In: Proceedings of the 3rd Annual ACM Symposium
on Theory of Computing, ACM, New York, NY, USA, pp. 151-
158. 4
 TSP
• O problema do caixeiro-viajante (TSP) é um problema de
otimização associado à determinação dos caminhos denominados
hamiltonianos.

• Sua origem advém de Willian Rowan Hamilton, que propôs um

jogo cujo desafio consistia em encontrar uma rota através dos
vértices de um dodecaedro de tal modo que a rota iniciasse e
terminasse no mesmo vértice, sem nunca repetir uma visita.

• Assim, o objetivo do TSP é encontrar um grafo G = (N,A) o

caminho hamiltoniano de menor custo, de forma que todos os
vértices sejam visitados uma única vez.

5
 TSP
• Dodecaedro

6
 TSP

• Nos anos de 1800, problemas relacionados com o TSP começaram

a ser desenvolvidos por dois matemáticos: o escocês William
Rowan Hamilton e o britânico Thomas Penyngton Kerkman.

7
 TSP
• O problema do caixeiro-viajante consiste na procura de um circuito
que possua a menor distância, começando numa cidade qualquer,
entre várias, visitando cada cidade precisamente uma vez e
regressando à cidade inicial.

8
 TSP
• Exemplo de ciclo hamiltoniano com n=7.

9
Formulação do Problema

10
 TSP

• Embora tenham sido desenvolvidos bons algoritmos de

aproximação para o TSP, o problema continua a oferecer uma
grande atração para a aplicação de novos algoritmos, tais como os
evolucionários.

• Isto deve-se, essencialmente, às seguintes razões:

11
 TSP

• A problemática do TSP pode ser entendida facilmente, uma vez

que se aproxima dos problemas populares do mundo real;

• O TSP demonstra o caso mais simples dos problemas de rotas que

são de enorme relevância para a programação de processos
industriais;

• Existem vários conjuntos de dados sobre o TSP que estão

disponíveis na literatura, de tal forma que os resultados são
comparáveis;

12
 TSP – Aplicações
• Logística

• Agendamento de uma máquina para fazer furos em uma placa de

circuito.

13
 TSP

• O problema do caixeiro é um clássico exemplo de problema de

otimização combinatória.

• A primeira coisa que podemos pensar para resolver esse tipo de

problema é reduzi-lo a um problema de enumeração: achamos
todas as rotas possíveis e calculamos o comprimento de cada uma
delas e então vemos qual a menor.
( É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que
estamos reduzindo o problema de otimização a um de enumeração ).

14
 TSP
• Para acharmos o número R(n) de rotas para o caso de n cidades,
basta fazer um raciocínio combinatório simples e clássico.

• Por exemplo, no caso de n = 4 cidades, a primeira e última posição

são fixas, de modo que elas não afetam o cálculo;
– na segunda posição podemos colocar qualquer uma das 3
cidades restantes B, C e D, e uma vez escolhida uma delas,
podemos colocar qualquer uma das 2 restantes na terceira
posição;
– na quarta posição não teríamos nenhuma escolha, pois sobrou
apenas uma cidade;
– consequentemente, o número de rotas é 3 x 2 x 1 = 6,
resultado que tínhamos obtido antes contando diretamente a
lista de rotas. 15
 TSP

• De modo semelhante, para o caso de n cidades, como a primeira é

fixa, o número total de escolhas que podemos fazer é:

– (n-1) x (n-2) x ... x 2 x 1.

– De modo que, usando a notação de fatorial: R(n) = (n - 1)!

16
 TSP
• Assim que nossa estratégia reducionista consiste em gerar cada
uma dessas R(n) = (n - 1)! rotas,

– calcular o comprimento total das viagens de cada rota e ver

qual delas tem o menor comprimento total.

– Trabalho fácil para o computador?

– Talvez não. Vejamos o porquê.

17
 Exemplos Práticos
• Um tour ideal por 15.112
cidades na Alemanha,
provou ser a solução ideal
em abril de 2001.

• Tempo de CPU:
22,6 anos

18
 Exemplos Práticos
• Dado os avanços tecnológicos que se sucederam a partir da
década de 1990, nos anos de 1994, 1998 e 2001, nos laboratórios
da AT&T Bell, pesquisadores, usando métodos heurísticos e plano
de corte, otimizaram instâncias contendo 7397, 13509 e 15112
cidades respectivamente.

• Em 2004, o mesmo grupo de pesquisadores, após 14 meses de

testes, propuseram a solução ótima para uma instância com 24978
cidades. Em 2006, Applegate et. al. (2006) alcançaram uma
otimização com 85600 pontos através do Concorde TSP Solver.

Applegate, D.; Bixby, R.; Chvátal, V.; Cook, W.. (2006) The Traveling Salesman Problem: A
Computational Study. Princeton University Press.

19
 TSP

• Suponha que temos um computador veloz, capaz de fazer 1 bilhão

de adições por segundo.

• No caso de 20 cidades, o computador precisa apenas de 19

adições para dizer qual o comprimento de uma rota e então será
capaz de calcular 109/19 = 53 milhões de rotas por segundo.

• Contudo, essa imensa velocidade é um nada frente à imensidão do

número 19! de rotas que precisará examinar.

20
 TSP

• Dessa forma, o valor de 19! é:

121 645 100 408 832 000 (ou, aproximadamente, 1.2 x 1017).

Consequentemente, ele precisará de:

• 1.2 x 1017 / ( 53 milhões ) = 2.3 x 109 segundos
• Ou 73 anos.

21
 TSP

n rotas por segundo ( n - 1 )! cálculo total

5 250 milhoes 24 insignificante
10 110 milhoes 362 880 0.003 seg
15 71 milhoes 87 bilhoes 20 min
20 53 milhoes 1.2 x 1017 73 anos
25 42 milhoes 6.2 x 1023 470 milhões de anos

Resumindo: Análise combinatória pode não ser eficiente.

22
 TSP – Métodos de Solução
Existem basicamente duas formas:

• Métodos exatos.
• Métodos heurísticos.

23
 Métodos Exatos
• Analisam todas as alternativas possíveis.

• A complexidade é fatorial!

• Por isto, os métodos mais usados são os do tipo ”branch-and-

bound”.
– Estes, consistem em expandir os nós e cortar caminhos de
pesquisa que não são promissores.

24
 Métodos Heurísticos
• Um método heurístico pode ser definido como uma técnica que
busca boas soluções, com um custo computacional (tempo)
relativamente inferior ao dos métodos determinísticos (exatos).

• Dentre as vantagens a serem consideradas como prerrogativas no

uso de métodos heurísticos, destacam-se:
– a capacidade de flexibilização para manipular as variáveis ou
características do problema;
– a proposição de mais de uma solução, possibilitando ao
analista verificar qual aquela que tem melhor qualidade para o
problema analisado;
– a geração de soluções satisfatórias sem recorrer ao formalismo
matemático aumentando a facilidade de implementação.
25
 Métodos Heurísticos
• Com base em heurísticas é possível encontrar soluções
aproximadas, isto é, não são soluções exatas mas fornecem um
resultado satisfatório em tempo hábil.

26
 Métodos Heurísticos
Basicamente, técnicas de inteligência artificial.

• Métodos de busca heurística (algoritmo guloso).

• Métodos de computação bioinspirada:

– Algoritmos genéticos.
– Colônia de formigas.

27
 Algoritmo Guloso
Algoritmo Guloso (greedy) pertence a classe de Heurísticas
Construtivas, e é uma solução comum para problemas de otimização
onde:

• Realiza a escolha que parece ser a melhor no momento na

esperança de que a mesma acarrete em uma solução ou
prevenção de futuros problemas a nível global;

• É simples e de fácil implementação;

• É míope: ele toma decisões com base nas informações disponíveis

na iteração corrente, e nunca reconsideram as decisões tomadas.

• Critério de escolha é basicamente local. 28

 Algoritmo Guloso
Pontos a favor
• Simples e de fácil implementação;
• Algoritmos de rápida execução;
• Podem fornecer a melhor solução (estado ideal).

Pontos Contra
• Dependentes de informações;
• Correm o risco de entrarem em loops infinitos;
• Situacionais, só resolvem tipos específicos de problemas;
• Decisões tomadas são irrevogáveis;

29
 Heurísticas Construtivas
Exemplo:

• Heurística do Vizinho mais Próximo.

• Heurística da Inserção Mais Barata.

• Heurística de Clark e Wright.

30
 Heurística do Vizinho mais Próximo
• Nearest neighbor search (NNS).

• Neste método heurístico, define-se uma cidade inicial da rota e

segue-se inserindo na rota corrente, a cidade que apresentar o
menor custo para se percorrer em relação à última cidade
adicionada.

• Uma vez que este método constrói a solução passo a passo,

segundo um conjunto de critérios pré-estabelecidos, pode ser
denominado como método guloso (greedy).

31
 Heurística do Vizinho mais Próximo
Rota da Heurística do Vizinho Mais Próximo, iniciando por c1.

A menor rota não será maior que:

Upper Bounds → Limite Superior 32
 Exercício 1
• Iniciando e terminando em 1, encontre a rota com menor custo.
(Vizinho mais próximo)

A menor rota não será maior que:

33
 Encontrando o Lower Bound

A menor rota não será menor que:

Lower Bounds → Limite Inferior

1. Deleta um Nó.
2. Elenque os pares (menor custo ao maior custo) até conectar
todos.
3. Somar os custos.
4. Conectar o Nó deletado novamente a rota (escolhendo os dois
caminhos de menor custo).

34
 Rota Ótima

Lower Bound <= Rota Ótima <= Upper Bound

35
 Heurística da Inserção Mais Barata
• Proposta por Karg e Thompson (1964) e referenciada como
Heurística da Inserção Mais Barata (HIMB) por Solomon (1987),
– este método heurístico procura definir um roteiro inicial com
somente três cidades, sendo as demais cidades ainda não
incluídas no roteiro, selecionadas para inserção no roteiro
parcial, aquelas que proporcionam menor acréscimo de
distância total percorrida.

Karg, R.L.; Thompson, G.L. A Heuristic Approach to Solving Travelling Salesman Problems.
Management Science, Vol. 10, pp.225-248. 1964.

Solomon, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time
Window Constraints. Operations Research Vol. 35, pp. 254−265. 1987.

36
 Heurística da Inserção Mais Barata
• Esse procedimento é repetido sucessivamente, com a análise da
inserção entre cada par de cidades do roteiro parcial, até que
todas as cidades sejam inseridas.

• O mecanismo de escolha da cidade a ser avaliada para inserção

pode ser implementado para proceder de forma sequencial,
aleatória ("Inserção Aleatória") ou baseado na cidade que está
mais distante do roteiro parcial ("Inserção Mais Distante").

37
 Heurística da Inserção Mais Barata
• Rota construída pela HIMB.

38
 Heurística de Clarke e Wright
• A Heurística de Clarke e Wright, também conhecida como
Heurística de Savings (economias), é um método econômico-
iterativo construtivo de busca de soluções para problemas de
roteirização.

• Proposta em 1964, este método heurístico inicia com um processo

iterativo que procura percorrer todas as cidades, duas a duas, de
forma a calcular as economias deste deslocamento e considerando
ainda, o custo de retornar à cidade inicial.

• Durante este processo iterativo, a função gulosa de inserção

escolhe sempre a maior economia dentre as possíveis.

39
 Heurística de Clarke e Wright
O algoritmo de Clarke & Wright pode ser dividido em 5 passos:

• Passo 1: Fazer a combinação dois a dois de todos os pontos;

• Passo 2: Calcular os ganhos de todos os pares de pontos;
• Passo 3: Ordenar os ganhos em ordem decrescente;
• Passo 4: Iniciar a análise dos pontos pelo par de maior ganho,
passando para o segundo par de maior ganho e assim
sucessivamente;
• Passo 5: Considerar duas rotas com os arcos e (i, 1) e caso o ganho
seja maior que zero, introduzir o arco (i, j) e deletar os outros arcos
iniciais. Continuar repetindo o passo 5 até que mais nenhuma
melhoria seja possível.

40
 Heurística de Clarke e Wright
• Dado estes 5 pontos e o custo (distâncias) entre eles.
• Origem em zero (0).

41
 Heurística de Clarke e Wright
• Formar rotas (pares) a partir do ponto de origem.

42
 Heurística de Clarke e Wright

Remover Adicionar

43
Heurística de Clarke e Wright

44
Heurística de Clarke e Wright

45
Heurística de Clarke e Wright

46
Heurística de Clarke e Wright

47
Heurística de Clarke e Wright

48
Heurística de Clarke e Wright

49
 Heurística de Clarke e Wright
• Ordenar os “Savings” do maior para o menor.

S23 (= S23) = 17
S34 (= S43) = 16
S12 (= S21) = 13
S24 (= S42) = 11
S13 (= S31) = 10
S14 (= S41) = 5

50
Heurística de Clarke e Wright

51
Heurística de Clarke e Wright

52
Heurística de Clarke e Wright

53
Heurística de Clarke e Wright

54
Heurística de Clarke e Wright

55
Heurística de Clarke e Wright

56
Meta Heurística

57
 Meta-Heurística
• Meta-Heurísticas podem fornecer boas soluções para diferentes tipos de
problemas, assim sendo consideradas heurísticas de uso e aplicação
geral.

• A característica primordial de uma Meta-Heurística é sua capacidade de

diversificar o campo de soluções evitando paradas em ótimos locais.

• Paradas, prematuras, em ótimos locais no processo iterativo de busca de

soluções são evitadas pelas Meta-Heurísticas por meio de mecanismos
de fuga, como combinação de escolhas aleatórias e conhecimento
histórico dos resultados anteriores adquiridos.

• Estes mecanismos atuam direcionando a busca para outras vizinhanças

dentro do vasto espaço de pesquisa.
58
 Meta-Heurísticas
Métodos que produzem uma solução única por iteração:
• Simulated Annealing (SA), Tabu Search (TS), Greedy Randomized
Adaptive Search Procedure (GRASP), Iterated Local Search (ILS),
Variable Neighborhood Search (VNS);

Métodos que produzem uma população de soluções por iteração:

• Evolutionary Algorithms (EA), Algoritmos Genéticos (AG), Scatter
Search (SS) e Adaptive Memory Procedures (AMP);

Métodos que, a cada iteração, obtém soluções através de

mecanismos de aprendizagem:
• Redes Neurais (RN), Colonia de Formigas (CF), Particle Swarm
Optimization (PSO).
59
 Meta-Heurísticas
• Nas próximas aulas, veremos algumas destas Meta-Heurísticas de
aplicação comum no TSP e na roteirização em geral.

60
 Meta-Heurística Híbrida

• Trata-se de um método heurístico construído a partir da junção de

duas ou mais Meta-Heurísticas em um mesmo procedimento.

• A intenção teórica desta proposta está em tentar evitar com maior

facilidade os ótimos locais, refletindo assim, em uma melhora nos
resultados obtidos na prática com os métodos heurísticos
combinados.

61
 Hiper-Heurística

• É uma técnica de otimização capaz de controlar um conjunto de

outras heurísticas na resolução de problemas de otimização.

• Este método visa equilibrar vantagens e desvantagens de um

conjunto de heurísticas específicas para um tipo de problema
onde, em cada ponto de decisão, uma heurística é devidamente
selecionada para ser aplicada.

62
 Exercício 2
• Partindo de “A”, encontre a rota de menor custo.
– Método do Vizinho mais próximo. (determinar Upper e Lower
Bound).
– Método de Clarke e Wright.

B
16 18
4
22 E 23
A C
7
14 19
D

63
 Exercício 3
• Partindo de “A”, encontre a rota de menor custo.
– Método do Vizinho mais próximo. (determinar Upper e Lower
Bound).
– Método de Clarke e Wright.
B 7
C

3
5 8
5
4 G 9
A D

4 4
3 7
8
F E
64
 MTSP
(Multiple Traveling Salesman Problem)

65
 Multiple Traveling Salesman Problem
(MTSP)
• Como o próprio nome sugere, nesta variação, múltiplos caixeiros
são designados para que todos os pontos do problema sejam
visitados.

• Logo, roteiros com o custo mínimo são configurados para que cada
caixeiro viajante atenda ao menos a um ponto da rede.

66
 MTSP

• É a base teórica para os problemas VRP (Vehicle Routing Problem).

• O MTSP pode ser considerado como um relaxamento do VRP, com

as restrições de capacidade removidas.

67
 (Depósitos únicos) x (múltiplos)

• No caso de depósito único, todos os vendedores começam e

terminam suas viagens em um único ponto.

• Por outro lado, se houver vários depósitos com um número de

vendedores localizados em cada um, os vendedores podem
retornar ao depósito original.

68
 Taxas fixas

• Quando o número de vendedores no problema não é fixo, cada

vendedor geralmente tem um custo fixo associado incorrido
sempre que esse vendedor é usado na solução.

• Nesse caso, a minimização do número de vendedor a ser ativado

na solução também pode ser preocupante.

69
 Janelas de tempo

• Nesta variação, certos nós precisam ser visitados em períodos de

tempo específicos, nomeados como janelas de tempo.

• Esta é uma extensão importante do MTSP, que tem aplicações

imediatas em problemas de agendamento de ônibus, navios,
linhas aéreas, etc.

70
 Outras restrições especiais

• Essas restrições podem consistir em limites no número de nós que

cada vendedor visita, na distância máxima ou mínima percorrida
por um vendedor ou em outras restrições especiais.

71