O caminho a pé mais curto para visitar todos os 81.998 bares da Coreia é de 178 dias

xguru · 2025-04-23T09:31:02+09:00

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 In Pursuit of the Traveling Salesman: história e aplicações do TSP Traveling Salesman Problem: pesquisa sobre aplicação do método de planos de corte The Golden Ticket: introdução ao problema P vs. NP Opt Art: criação de imagens artísticas usando TSP Approximation Algorithms: pesquisas recentes sobre algoritmos de aproximação para TSP Computational Solutions for TSP Applications: livro sobre casos de aplicação publicado em 1994

(math.uwaterloo.ca)

23 pontos por xguru 2025-04-23 | 10 comentários | Compartilhar no WhatsApp

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

In Pursuit of the Traveling Salesman: história e aplicações do TSP
Traveling Salesman Problem: pesquisa sobre aplicação do método de planos de corte
The Golden Ticket: introdução ao problema P vs. NP
Opt Art: criação de imagens artísticas usando TSP
Approximation Algorithms: pesquisas recentes sobre algoritmos de aproximação para TSP
Computational Solutions for TSP Applications: livro sobre casos de aplicação publicado em 1994

10 comentários

ep6tri 2025-04-24

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.

skshin 2025-04-23

E como fica o deslocamento até as ilhas? A pé?

halfenif 2025-04-23

Como aparece walking and ferry, acho que vai de barco.

woalsdnd 2025-04-23

Como lidar com os casos em que novos estabelecimentos surgem e outros fecham em tempo real?

majorika 2025-04-23

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

kimjoin2 2025-04-23

Uau, então havia esse contexto. Obrigado por organizar e compartilhar.

kimjoin2 2025-04-23

Também fiquei curioso sobre o motivo de terem escolhido a Coreia 👀

firea32 2025-04-28

Provavelmente também ajudou o fato de ser possível obter dados de qualidade por 1.000 won :)