- O que é roteirização e o problema do caixeiro viajante
- Mapa visual da roteirização
- Dados do exemplo: depósito e 5 clientes
- Vizinho mais próximo: construir a rota
- Melhoria 2-opt: trocar dois trechos
- Do caixeiro viajante à roteirização de veículos
- Onde a roteirização entra na operação
- Erros comuns e limitações
- Perguntas frequentes
O que é roteirização e o problema do caixeiro viajante
A roteirização define em que ordem um veículo visita um conjunto de pontos para gastar o mínimo de distância ou tempo. Quando um único veículo precisa passar por todos os pontos e voltar à origem, isso é o problema do caixeiro viajante (TSP, do inglês Traveling Salesman Problem).
Com vários veículos, capacidade de carga e janelas de horário, o problema passa a se chamar roteirização de veículos (VRP). É o dia a dia de quem entrega produto acabado, coleta material de fornecedores ou abastece a linha com milk run.
O TSP é difícil porque o número de rotas explode. Com 5 clientes existem 5! = 120 sequências possíveis; com 10 clientes, 10! = 3.628.800. Por isso, na prática se usam heurísticas: regras simples que dão uma boa rota em segundos, sem garantir a melhor.
Mapa visual da roteirização
O mapa resume o exemplo deste artigo: a rota construída pelo vizinho mais próximo e a melhoria por 2-opt.
Dados do exemplo: depósito e 5 clientes
Exemplo fictício, só para ilustrar o cálculo. O depósito D fica na origem e cada unidade da grade equivale a 1 km. Coordenadas (x, y): D (0, 0), F (1, 3), A (2, 6), B (5, 1), C (6, 5) e E (9, 2).
d = √[(x₂ − x₁)² + (y₂ − y₁)²]
Exemplo: de D até F, d = √(1² + 3²) = √10 = 3,16 km. A tabela traz todas as distâncias entre os pontos, em km.
| D | F | A | B | C | E | |
|---|---|---|---|---|---|---|
| D | – | 3,16 | 6,32 | 5,10 | 7,81 | 9,22 |
| F | 3,16 | – | 3,16 | 4,47 | 5,39 | 8,06 |
| A | 6,32 | 3,16 | – | 5,83 | 4,12 | 8,06 |
| B | 5,10 | 4,47 | 5,83 | – | 4,12 | 4,12 |
| C | 7,81 | 5,39 | 4,12 | 4,12 | – | 4,24 |
| E | 9,22 | 8,06 | 8,06 | 4,12 | 4,24 | – |
Em operação real, troque a distância em linha reta pela matriz de distâncias ou tempos de viagem por estrada. As heurísticas funcionam do mesmo jeito.
Vizinho mais próximo: construir a rota
É a heurística mais simples. Parta do depósito e, a cada passo, vá ao cliente ainda não visitado que estiver mais perto. Ao visitar todos, volte ao depósito.
- De D, o mais próximo é F (3,16 km), contra A (6,32), B (5,10), C (7,81) e E (9,22).
- De F, o mais próximo é A (3,16 km).
- De A, o mais próximo é C (4,12 km).
- De C, B (4,12 km) é menor que E (4,24 km), então vai para B.
- De B, resta apenas E (4,12 km).
- De E, volta a D (9,22 km).
| Passo | De | Para | Distância (km) |
|---|---|---|---|
| 1 | D | F | 3,16 |
| 2 | F | A | 3,16 |
| 3 | A | C | 4,12 |
| 4 | C | B | 4,12 |
| 5 | B | E | 4,12 |
| 6 | E | D | 9,22 |
| Total | 27,91 |
A rota D–F–A–C–B–E–D soma 27,91 km. Note o defeito típico do método: nos últimos passos sobram os clientes distantes, e o retorno E–D de 9,22 km pesa sozinho um terço da rota.
Melhoria 2-opt: trocar dois trechos
O 2-opt parte de uma rota pronta e testa trocar dois trechos (arestas) por outros dois, invertendo a ordem do pedaço entre eles. Se o total diminuir, aceita a troca e repete até nenhuma troca ajudar.
ganho = (aresta 1 + aresta 2) removidas − (aresta 3 + aresta 4) novas
Na rota D–F–A–C–B–E–D, remova C–B e E–D. Reconecte C com E e B com D, invertendo o trecho B–E. A sequência passa a D–F–A–C–E–B–D.
| Rota | Sequência | Arestas trocadas | Total (km) |
|---|---|---|---|
| Antes (vizinho mais próximo) | D–F–A–C–B–E–D | C–B (4,12) + E–D (9,22) = 13,34 | 27,91 |
| Depois (2-opt) | D–F–A–C–E–B–D | C–E (4,24) + B–D (5,10) = 9,34 | 23,91 |
O ganho é 13,34 − 9,34 = 4,00 km, ou 14,3% de redução (de 27,91 para 23,91 km). Testadas todas as trocas restantes, nenhuma melhora mais. Conferi o resultado listando as 120 sequências: 23,91 km é de fato o menor percurso deste exemplo. Nem sempre o 2-opt chega ao ótimo, mas quase sempre chega perto.
Do caixeiro viajante à roteirização de veículos
O TSP supõe um veículo, sem limite de carga. A realidade da fábrica e da distribuição acrescenta restrições:
- Capacidade: o veículo não leva todos os pedidos de uma vez; é preciso dividir os clientes em várias rotas.
- Janelas de horário: o cliente só recebe entre 8h e 11h, por exemplo.
- Frota mista: veículos de tamanhos e custos diferentes.
- Tempo de serviço: descarga, conferência e jornada máxima do motorista.
- Coleta e entrega: pontos que recebem e pontos que enviam.
Para dividir clientes em rotas, um método clássico é o das economias de Clarke e Wright (1964), que junta rotas quando isso reduz a distância total. Problemas maiores ou com muitas restrições pedem modelagem em programação linear inteira ou software de roteirização.
Onde a roteirização entra na operação
- Milk run externo: coleta em vários fornecedores numa mesma viagem, como na logística de abastecimento.
- Distribuição: entregas a clientes, onde o frete é parte relevante do custo; veja também o cross docking.
- Armazém: a ordem de visita dos endereços no picking é um pequeno TSP.
- Manutenção e inspeção: ronda de técnicos por vários equipamentos.
- Cadeia de suprimentos: a rota é uma peça da cadeia que define prazo e custo logístico.
Erros comuns e limitações
- Achar que o vizinho mais próximo é o ótimo. Ele é só um ponto de partida; no exemplo ficou 17% acima do melhor (27,91 contra 23,91 km).
- Usar linha reta no lugar da malha viária. Rio, ferrovia e mão única mudam a ordem ideal.
- Ignorar tempo. O menor percurso nem sempre é o menor tempo; trânsito e janelas pesam.
- Esquecer restrições. Capacidade, horário de recebimento e jornada do motorista precisam entrar antes de comparar rotas.
- Não validar com o motorista. Quem dirige conhece bloqueios, docas e filas que o mapa não mostra.
- Calcular uma vez só. Quando os pedidos mudam, a rota muda; refaça a cada ciclo de entrega.
Perguntas frequentes
O que é o problema do caixeiro viajante?
É o problema de achar a menor rota que passa uma vez por cada ponto de uma lista e volta ao ponto de partida.
O que é roteirização de veículos?
É a definição das rotas de uma frota para atender clientes, respeitando capacidade, horários e custo mínimo de distância ou tempo.
Como funciona o vizinho mais próximo?
Parte-se do depósito e, a cada passo, vai-se ao cliente não visitado mais próximo, até visitar todos e voltar ao início.
O que é o 2-opt?
É uma melhoria que troca duas arestas da rota por outras duas, invertendo o trecho entre elas, quando isso reduz a distância total.
O vizinho mais próximo dá a melhor rota?
Não garante. No exemplo deu 27,91 km, e o 2-opt chegou a 23,91 km, o mínimo verificado entre as 120 sequências.
Quantas rotas existem com 10 clientes?
10! = 3.628.800 sequências a partir de um depósito, motivo pelo qual se usam heurísticas em vez de testar todas.
Fontes
- APPLEGATE, D. L. et al. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
- TOTH, P.; VIGO, D. (org.). The Vehicle Routing Problem. SIAM, 2002.
- CROES, G. A. A method for solving traveling-salesman problems. Operations Research, v. 6, 1958.
- CLARKE, G.; WRIGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, v. 12, 1964.
- BALLOU, R. H. Gerenciamento da Cadeia de Suprimentos / Logística Empresarial. Porto Alegre: Bookman.
Para estudar mais: fontes e links confiáveis
- INFORMS: What is Operations Research? (em inglês)
- INFORMS: Institute for Operations Research and the Management Sciences (em inglês)
Guarde este endereço: o Manufatura Enxuta é a sua escola de manufatura enxuta. Volte sempre que precisar estudar, com artigo completo, mapa visual e fontes confiáveis. Siga uma das trilhas de estudo ou consulte o glossário A–Z.
Quer um fluxo sem idas e vindas?
Baixe o e-book gratuito "Guia de Bolso Lean" e aprenda a enxergar o fluxo antes de mudar o layout.
Baixar e-book
Sobre o autor
Especialista em Lean Manufacturing e Gestão Comportamental
Mais de 20 anos de indústria automotiva e metalmecânica (GM e Dana), especialista em Lean Manufacturing desde 2006. Instrutor e mentor do SENAI no programa Brasil Mais Produtivo, com consultorias, treinamentos e auditorias em mais de 50 empresas, unindo qualidade, produtividade e desenvolvimento de pessoas.
