- O professor William Cook, da Universidade de Waterloo, calculou no que é o primeiro caso do mundo o problema do caixeiro-viajante (TSP) para a rota mais curta que visita 81.998 bares da Coreia
- Usando o Open Source Routing Machine (OSRM), foram calculados cerca de 3,3 bilhões de pares de tempos de caminhada, e foi provado matematicamente que a rota é ótima
- O resultado mostra que, caminhando sem parar, seriam necessários 15.386.177 segundos no total, ou 178 dias, 1 hora, 56 minutos e 17 segundos
- As ferramentas LKH e Concorde foram usadas na otimização do TSP, com aplicação do método de planos de corte
- Trata-se do maior caso do mundo de TSP baseado em malha viária já resolvido, superando a rota anterior de 57.912 pontos nos Países Baixos
O problema do caixeiro-viajante para percorrer todos os bares da Coreia
- Foi calculada a rota mais curta para visitar todos os 81.998 bares da Coreia e retornar ao ponto de partida
- É a primeira vez no mundo que um problema de TSP com tantos locais foi resolvido de forma ótima
- Os tempos de caminhada de um total de 3.361.795.003 pares entre bares foram calculados com o OSRM - Open Source Routing Machine
- Foi demonstrado matematicamente que não existe rota mais curta que esta
- Este problema é o maior da história em número de pontos visitados entre os casos de TSP
Tempo necessário para a rota mais curta
- Seguindo a rota ótima calculada e caminhando sem parar, o tempo total é de 15.386.177 segundos
- Isso corresponde a 178 dias, 1 hora, 56 minutos e 17 segundos
- Na prática, seria difícil concluir exatamente nesse tempo, já que seria preciso descansar ou beber durante o percurso
- É uma rota ótima baseada em tempos de caminhada do OSRM, impossível de reduzir nem em 1 segundo
Contexto histórico do TSP e quebra de recorde
- O recorde anterior era uma rota de bicicleta por 57.912 pontos nos Países Baixos
- Esta rota korea81998 é um caso de resolução de TSP em escala ainda maior
- Os cálculos foram realizados entre dezembro de 2024 e março de 2025 na Universidade de Roskilde e na Universidade de Waterloo
- Os detalhes do cálculo podem ser consultados em uma página de cálculo separada
Como visualizar a rota
- A rota pode ser explorada em um mapa interativo, dividido em 7 regiões
- Há vários modos de visualização disponíveis, como mapa colorido por distância e escala de cinza
- Também são fornecidas imagens em alta resolução de partes da rota
- Visualizações ampliadas por cidade estão disponíveis na página das cidades
Estratégia para resolver o TSP e equívocos comuns
- Alguns veículos de mídia dizem que até mesmo 22 cidades levariam 1.000 anos, mas isso se refere ao caso de testar aleatoriamente todas as rotas possíveis
- Na prática, muitos pontos podem ser resolvidos com técnicas avançadas de otimização
- No caso de
korea81998, o número de rotas possíveis chega a um número 2 seguido de 367.308 zeros
- A solução combinou o algoritmo LKH (Lin-Kernighan Heuristic) com o Concorde TSP Solver - método de planos de corte
Resumo do conceito de método de planos de corte
- Baseia-se em programação linear
- Em vez de representar apenas se uma estrada é usada ou não, expressa-se o grau de conexão com valores entre 0 e 1
- Restrições são adicionadas em etapas para encontrar a rota mais curta
- Explicações detalhadas podem ser encontradas na Scientific American e em uma palestra no YouTube
O problema P vs NP
- O TSP é um problema NP-completo e um exemplo clássico da questão P vs NP
- Discussões interessantes relacionadas aparecem em um artigo do professor Lance Fortnow
- Este é um dos problemas em aberto mais famosos da ciência da computação
O significado da otimização matemática
- Este projeto é um experimento com métodos gerais de otimização e uma base para seu avanço
- Há grande potencial de aplicação em áreas como indústria, comércio, medicina e meio ambiente
- A modelagem matemática é uma ferramenta importante para usar recursos finitos de forma eficaz
Apresentação dos pesquisadores
- William Cook: Universidade de Waterloo, Canadá
- Daniel Espinoza: Alicanto Labs, Chile
- Marcos Goycoolea: Universidade Adolfo Ibáñez, Chile
- Keld Helsgaun: Universidade de Roskilde, Dinamarca
Agradecimentos
- IBM CPLEX Optimizer: agradecimento pelo fornecimento gratuito para pesquisa acadêmica
- Os mapas foram produzidos com Leaflet, OpenStreetMap, Carto e Stadia Maps
- Dr. Sang-Il Eom forneceu os dados de localização dos bares com base em dados da Agência Nacional de Polícia da Coreia
- O cálculo dos tempos de caminhada utilizou o OSRM
Exemplos de projetos de TSP em outros países
- Japão: 40.426 lojas de conveniência
- Reino Unido: 49.687 pubs
- Estados Unidos: 49.603 locais históricos
- Países Baixos: 57.912 monumentos
Materiais adicionais de estudo
10 comentários
A página em inglês é https://www.math.uwaterloo.ca/tsp/korea/index.html.
O tour claramente é irrealista. Pelo visto, ele não considera rotas marítimas de balsa ao se deslocar do continente para Jeju ou Ulleungdo. Basta ver esta imagem: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
O ponto não deve ser calcular com precisão o tempo estimado necessário para a visita, mas sim dar valor ao fato de que o TSP foi resolvido com dados do mundo real.
E como fica o deslocamento até as ilhas? A pé?
Como aparece
walking and ferry, acho que vai de barco.Como lidar com os casos em que novos estabelecimentos surgem e outros fecham em tempo real?
> Eu estava programado para dar uma aula sobre TSP no KAIST, em Daejeon, em março de 2024, e estava procurando um conjunto de dados local para um tour TSP por Daejeon. Em dezembro de 2023, o Dr. Sang-il Eom me enviou um e-mail dizendo: “Você precisa de um conjunto de dados nacional de bares criado pela Agência Nacional de Polícia? O arquivo mais recente custa 1.000 won e tem 90.680 registros.” Uau. Depois de confirmar primeiro se 1.000 won valia menos de 1 dólar (foi bom verificar se a taxa de câmbio não estava invertida), respondi: “Obrigado!”
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
Uau, então havia esse contexto. Obrigado por organizar e compartilhar.
Também fiquei curioso sobre o motivo de terem escolhido a Coreia 👀
Provavelmente também ajudou o fato de ser possível obter dados de qualidade por 1.000 won :)
> Eu estava programado para dar uma aula sobre TSP no KAIST, em Daejeon, em março de 2024, e estava procurando um conjunto de dados local para um tour TSP em Daejeon.
Acho que eu estava procurando informações relacionadas porque ia dar uma palestra na Coreia.
Será que escolheram esse tema porque há bares demais na Coreia..