Enhanced Filtering Algorithms for the Euclidean Traveling Salesperson Problem and its variants in Constraint Logic Programming

Imagine que você é um motorista de entregas com um mapa cheio de paradas para fazer. Você quer visitar cada parada exatamente uma vez e retornar para casa, mas também quer queimar o mínimo de combustível possível. Este é o clássico "Problema do Caixeiro Viajante", um enigma que tem desafiado matemáticos e cientistas da computação por décadas. Não se trata apenas de caminhões de entrega; trata-se de tudo, desde o roteamento de veículos inteligentes até a organização de dados em um chip de computador. A parte complicada é que, à medida que você adiciona mais paradas, o número de rotas possíveis explode tão rápido que até os computadores mais rápidos do mundo podem se perder no labirinto.

Para resolver isso, os computadores frequentemente usam um método chamado "Programação por Restrições". Pense nisso como um detetive superinteligente que não apenas adivinha rotas aleatoriamente. Em vez disso, o detetive estabelece uma série de regras (restrições) para eliminar opções impossíveis ou absurdas imediatamente. Por exemplo, "Você não pode visitar a mesma cidade duas vezes" ou "Você não pode dirigir em um círculo que ignore o resto da viagem". Geralmente, quando o problema envolve distâncias em um mapa plano (o que os cientistas chamam de caso "Euclidiano"), o computador apenas trata o mapa como uma lista genérica de números, ignorando o fato de que as paradas estão, na verdade, desenhadas em uma folha de papel com linhas retas e ângulos. É como tentar navegar em uma cidade olhando apenas para uma lista de nomes de ruas, sem nunca olhar para o mapa em si.

Este artigo faz uma pergunta simples, mas poderosa: E se parássemos de ignorar o mapa? Os autores, Alessandro Bertagnon e Marco Gavanelli, decidiram construir um novo conjunto de "regras" para o seu detetive de computador que realmente entenda de geometria. Eles criaram algoritmos especiais que sabem que, em um caminho perfeito e mais curto, as estradas não devem se cruzar como um "X" no céu, e que a borda externa de um grupo de pontos deve ser visitada em uma ordem circular organizada. Ao ensinar o computador a "ver" a forma do problema, eles encontraram uma maneira de eliminar milhões de palpites ruins muito mais rápido do que antes. Eles também mostraram que esses truques geométricos funcionam mesmo quando o problema se torna mais complicado, como quando você tem que visitar um grupo de cidades, mas só precisa parar em uma delas.

A Descoberta Central do Artigo

A principal descoberta deste trabalho é que, ao usar as propriedades geométricas específicas do Problema do Caixeiro Viajante (TSP) — especificamente o fato de que o caminho mais curto em um plano plano nunca se cruza e segue a borda externa de uma forma em uma ordem específica — os computadores podem resolver esses enigmas de roteamento significativamente mais rápido. Os autores implementaram essas novas regras em uma linguagem de programação chamada Programação Lógica de Restrições (CLP).

Eles testaram sua nova "filtragem geométrica" contra os melhores métodos existentes. Os resultados foram impressionantes: para mapas aleatórios com até 100 pontos, a nova abordagem dos autores reduziu o tempo para encontrar a melhor solução em cerca de 70% em média. Em termos de "passos de pensamento" do computador (nós de busca), eles reduziram o trabalho em aproximadamente 59% a 75%, dependendo da estratégia específica utilizada. Isso significa que o computador não apenas pensou mais rápido por passo; ele teve que pensar em muito menos passos para encontrar a resposta.

O Que Eles Descartaram e Como Fizeram

O artigo argumenta explicitamente contra a abordagem padrão de tratar os TSPs euclidianos (onde as distâncias são linhas retas em um plano) exatamente da mesma forma que os TSPs gerais. O método comum é calcular a distância entre cada par de pontos, criar uma tabela gigante de números e aplicar regras genéricas. Os autores mostram que essa abordagem "cega" ignora informações valiosas que já estão lá: as coordenadas dos pontos. Eles demonstram que ignorar a geometria leva a um espaço de busca muito maior e soluções mais lentas.

Eles também esclarecem o que o método deles não é. Eles não afirmam ter resolvido o TSP completamente ou ter criado uma solução mágica que funcione para todo tipo de problema de roteamento. Por exemplo, eles observam que sua regra de "não cruzamento" não se aplica a problemas onde as estradas devem se cruzar, como em grades urbanas do mundo real com ruas de mão única ou pontes, ou em problemas com janelas de tempo estritas onde um desvio pode ser necessário. O trabalho deles é especificamente para "instâncias euclidianas completas", onde os pontos estão em um plano plano e os cruzamentos são evitáveis.

A Magia do "Não Cruzamento" e do "Fecho Convexo"

Para tornar o computador mais inteligente, os autores introduziram dois conceitos geométricos principais:

1. A Regra do Não Cruzamento: Imagine que você está desenhando um laço com um barbante conectando pontos em uma mesa. Se o seu barbante se cruzar, você sempre pode puxar o barbante com mais força para fazer um laço mais curto que não se cruza. Os autores provaram matematicamente que o caminho ideal (mais curto) nunca terá linhas que se cruzam. Eles construíram um "filtro" especial em seu programa de computador que deleta instantaneamente qualquer opção de rota que causaria um cruzamento. Isso é como um segurança em uma boate que imediatamente expulsa qualquer pessoa que tenta entrar pela porta errada, economizando o tempo do segurança de ter que checar sua identidade mais tarde.

2. A Ordem do Fecho Convexo: Imagine esticar um elástico ao redor de um grupo de pregos em uma tábua. A forma que o elástico faz é chamada de "fecho convexo" (convex hull). Os autores mostraram que, no caminho mais curto, os pregos na borda extrema deste elástico devem ser visitados em uma ordem específica (horária ou anti-horária). Eles criaram regras que forçam o computador a respeitar essa ordem, impedindo-o de perder tempo verificando rotas que ziguezagueiam de um lado para o outro na borda.

Estendendo a Magia para Problemas de Grupo

O artigo também aborda uma versão mais difícil do problema chamada "Problema do Caixeiro Viajante Generalizado" (GTSP). Nesta versão, em vez de visitar cada cidade individualmente, você tem que visitar um conjunto de "clusters" (grupos de cidades), mas só precisa parar em uma cidade de cada grupo. Isso é como um motorista de entrega que tem que entregar pacotes em três bairros diferentes, mas só precisa visitar uma casa em cada bairro.

Os autores mostraram que suas regras geométricas puderam ser adaptadas para este problema mais difícil também. Eles definiram "vizinhos" com base na geometria dos clusters e aplicaram a mesma lógica de não cruzamento e ordenação. Em seus testes nesses problemas de grupo, a nova abordagem geométrica reduziu o tempo médio de resolução em até 76% para mapas agrupados e 67% para mapas em grade.

A Conclusão

Os autores são cuidadosos ao afirmar que, embora seu método seja uma grande melhoria em relação às técnicas anteriores de Programação por Restrições, ele ainda não é tão rápido quanto os solvers especializados mais poderosos do mundo (como o Concorde) para o TSP básico. No entanto, esses super-solvers muitas vezes não conseguem lidar com as versões "Generalizadas" mais complexas que os autores abordaram com sucesso.

O artigo conclui que, ao simplesmente prestar atenção à forma do problema — usando o fato de que as linhas não se cruzam e as bordas seguem uma curva — os computadores podem descartar respostas ruins de forma muito mais eficiente. Isso não apenas acelera o cálculo; isso muda a natureza da busca, permitindo que os computadores resolvam enigmas de roteamento maiores e mais complexos que eram anteriormente difíceis demais para serem decifrados em um tempo razoável. Os autores sugerem que essa abordagem geométrica pode inspirar melhorias semelhantes em outros problemas de roteamento, desde que as estradas não tenham que se cruzar de formas inevitáveis.