A rota a pé mais curta para visitar os 81.998 bares da Coreia

 (math.uwaterloo.ca)
2 pontos por GN⁺ 2025-04-25 | 2 comentários | Compartilhar no WhatsApp
  • O problema do caixeiro-viajante (TSP) foi resolvido para encontrar a rota mais curta que visita 81.998 bares coreanos, usando o Open Source Routing Machine (OSRM)
  • Essa rota é uma rota ótima que leva mais de 178 dias, comprovada pelos cálculos do OSRM
  • Usando o código LKH e o código Concorde, foi aplicado o cutting-plane method para resolver um problema de TSP em larga escala
  • Otimização matemática e pesquisa operacional têm foco no desenvolvimento de ferramentas para aumentar a eficiência de recursos
  • A pesquisa foi realizada na Roskilde University e na University of Waterloo, com uso do IBM CPLEX Optimizer e da biblioteca Leaflet

A rota mais curta para visitar os 81.998 bares da Coreia

  • O problema do caixeiro-viajante (TSP) foi resolvido para encontrar a rota mais curta que visita 81.998 bares coreanos, usando o Open Source Routing Machine (OSRM)
  • Essa rota é uma rota ótima que leva mais de 178 dias, comprovada pelos cálculos do OSRM
  • Usando o código LKH e o código Concorde, foi aplicado o cutting-plane method para resolver um problema de TSP em larga escala

Resolvendo um problema de TSP em larga escala

  • Otimização matemática e pesquisa operacional têm foco no desenvolvimento de ferramentas para aumentar a eficiência de recursos
  • A pesquisa foi realizada na Roskilde University e na University of Waterloo, com uso do IBM CPLEX Optimizer e da biblioteca Leaflet

Equipe de pesquisa e agradecimentos

  • A equipe de pesquisa foi formada por William Cook, Daniel Espinoza, Marcos Goycoolea e Keld Helsgaun
  • A pesquisa foi realizada com o CPLEX Optimizer da IBM e a biblioteca Leaflet
  • As localizações dos bares coreanos foram obtidas por meio do banco de dados da Agência Nacional de Polícia da Coreia

Leituras relacionadas

2 comentários

 
xguru 2025-04-25

Publiquei no Hacker News com a conta do GeekNews o post A rota de caminhada mais curta para visitar todos os 81.998 bares da Coreia leva 178 dias.
Recebeu muitos votos, ficou no topo por 6 horas e acabou virando um post popular, então foi reimportado para o GN+ novamente.

Como esse post também tinha uma versão em inglês, resolvi tentar assim; de vez em quando, vou tentar postar no Hacker News textos que incluam inglês.
 
GN⁺ 2025-04-25
Comentários do Hacker News
  • Impressionante a solução de TSP envolvendo 133 milhões de vértices
    • Esse tour tem 1,0038 vezes o comprimento do caminho mais curto
    • Fico curioso para saber quão pior seria o resultado usando o algoritmo probabilístico do Bell Labs
  • Explicação da abordagem clássica para TSP
    • Conecta todos os nós em um caminho aleatório
    • Corta o caminho em dois pontos para formar três partes
    • Reorganiza as três partes das seis maneiras possíveis e escolhe a mais curta
    • Repete as etapas 2 e 3 até não haver mais melhorias
    • Não garante o resultado ótimo, mas na maioria dos problemas reais chega ao ótimo ou muito perto dele
  • Estranho não mencionarem a distância total
    • O objetivo é resolver o tempo de deslocamento, mas também seria interessante saber a distância real percorrida
    • Daria para calcular o gasto calórico ou ver o quanto isso se desvia da rota de menor distância
  • Fico impressionado ao pensar que um país do tamanho de Ohio tem quase 82 mil bares
  • Durante a COVID, defini a meta de caminhar por todas as ruas da minha cidade usando o CityStrides
    • Ele acompanha a distância caminhada e mostra qual porcentagem da cidade você já percorreu
    • Não otimizei a rota, mas foi um quebra-cabeça mental divertido tentar caminhar o máximo possível sem repetição
    • Ferramentas de automação também podem ser divertidas, mas fazer isso manualmente fazia parte da jornada
    • Ao explorar o site do CityStrides, dá para ver os LifeMaps das pessoas
    • Algumas pessoas caminham quantidades impressionantes
  • Isso me lembrou de uma pergunta feita ao exército irlandês nos anos 60
    • "Como ir de Bachelor's Walk até Collins Barracks sem passar por um bar?"
    • A resposta era "entrando em todos os bares"
  • Impressionante terem encontrado esse conjunto de dados, mas não é algo mais difícil
    • É um equilíbrio sutil entre bater o último recorde do caixeiro-viajante e não conseguir terminar o cálculo
  • NP volta a parecer P
    • Na escola me ensinaram que 13 era o máximo, e nos anos 80 um professor disse que já tinha avançado para 15
    • Depois veio 20, 20.000, e agora 80.000 ficou demonstrado
    • Na página World TSP o recorde é 1 milhão
    • O maior valor ótimo comprovado atualmente é 3.178.031
    • Tem que ser com CUDA, não dá para fazer isso com C comum
  • Branch-and-bound é um algoritmo "de livro"
    • Se você tratar o resolvedor de LP como uma caixa-preta, ele é fundamentalmente bem simples, mas muito útil
  • Parece que alguns bares novos abriram e alguns fecharam
    • Hora de recalcular