Uma análise comparativa de cruzamentos em algoritmos genéticos para otimização de rotas: estudos de caso de Astana e Shymkent, Cazaquistão

Por que rotas de ônibus mais inteligentes importam

Quem já esperou demais em um ponto de ônibus ou precisou fazer várias baldeações sabe que atravessar uma cidade não é apenas uma questão de distância. Dois lugares podem parecer próximos num mapa, mas ser difíceis de alcançar se as linhas de ônibus corretas não os conectam. Este artigo explora como uma classe de métodos de busca inspirados na evolução — algoritmos genéticos — pode ser ajustada para projetar rotas de ônibus melhores que respeitem redes de transporte reais em cidades como Astana e Shymkent, no Cazaquistão. O trabalho foca em um ingrediente crucial desses algoritmos, chamado etapa de cruzamento (crossover), e mostra como escolhê‑lo com sabedoria pode significar a diferença entre trajetos tortuosos e indiretos e rotas rápidas e realistas.

De mapas urbanos confusos a uma busca inteligente

Planejadores de rota tradicionais frequentemente tratam as cidades como se os viajantes pudessem se deslocar livremente entre quaisquer dois pontos, levando em conta apenas a distância física. Sistemas reais de ônibus não funcionam assim: você só pode ir onde as linhas realmente passam, e cada elo ausente ou desvio forçado custa tempo e dinheiro. Os autores modelam essa realidade representando locais importantes da cidade como pontos, as vias e conexões de ônibus como ligações, e uma viagem completa como um caminho que visita cada ponto exatamente uma vez. Eles então estabelecem um objetivo em duas partes: primeiro, evitar passos “ilegais” onde não existe ônibus direto; segundo, entre as rotas legais, escolher a de menor distância total. Isso cria um quebra‑cabeça difícil com muitas rotas possíveis, em que checar cada opção rapidamente se torna impossível à medida que a cidade cresce.

Como a evolução ajuda a encontrar rotas melhores

Algoritmos genéticos atacam esses problemas imitando a seleção natural. Em vez de testar uma rota de cada vez, mantêm uma população inteira de rotas candidatas. A cada geração, rotas melhores são favorecidas, e novas são criadas misturando e alterando levemente as existentes. A etapa chave de mistura — o crossover — decide como pedaços de duas rotas‑pais são combinados em uma nova rota‑filha. Para o planejamento de ônibus, essa etapa é crítica: bem feita, ela transmite padrões úteis de paradas conectadas; mal feita, pode quebrar ligações e produzir rotas que ignoram a rede de ônibus. Os autores testam nove estilos diferentes de crossover que variam em como preservam a ordem das paradas, as posições exatas das paradas ou as ligações reais entre paradas.

Testando várias formas de combinar rotas

Para ver quais estilos de crossover funcionam melhor, a equipe realiza uma ampla bateria de experimentos com dados reais de trânsito de Konya (uma cidade de referência de trabalhos anteriores) e de Astana e Shymkent. Para cada cidade, selecionam 14 destinos importantes, vinculam‑nos a paradas próximas e constroem três tabelas de dados principais: distâncias entre locais, quais pares têm ônibus direto e penalidades por tentar viajar onde não há ônibus. Em seguida, exploram centenas de configurações, variando o tamanho da população, com que frequência o crossover é usado e com que frequência pequenas mudanças aleatórias (mutações) são aplicadas. Para cada configuração, repetem o algoritmo muitas vezes para levar em conta a aleatoriedade, e medem não apenas quão curtas são as rotas finais, mas com que frequência o método encontra qualquer rota legal e quão rapidamente atinge esse ponto.

A estratégia vencedora para viagens realistas

Nas três cidades, um estilo de crossover se destaca: recombinação por arestas (edge recombination). Ao contrário de métodos que se preocupam principalmente com a ordem das paradas, a recombinação por arestas dá atenção a quais paradas estão diretamente conectadas e se esforça para preservar essas ligações ao construir novas rotas. O estudo mostra que essa abordagem focada em arestas é muito mais provável de produzir viagens de ônibus viáveis, reencontra com mais frequência as melhores rotas conhecidas e normalmente o faz em apenas algumas gerações. Um segundo estilo, chamado crossover baseado em ordem, também tem bom desempenho e é mais rápido de computar, oferecendo um bom equilíbrio quando são necessárias execuções em grande número. Outros crossovers comuns que rearranjam as paradas de forma mais agressiva tendem a ter desempenho inferior, exigindo mais tempo e entregando menos rotas de alta qualidade.

O que isso significa para o deslocamento cotidiano

Para um público não especializado, a conclusão é que a “receita” usada dentro de um algoritmo genético pode ter grande impacto em quão bem ele projeta viagens de ônibus no mundo real. Ao favorecer regras de crossover que mantêm ligações realistas intactas enquanto ainda exploram novas combinações, planejadores podem gerar rotas que obedecem à rede de ônibus existente e mantêm a distância total de viagem baixa. Em testes sobre recortes urbanos pequenos porém realistas, o algoritmo genético melhor ajustado não só igualou rotas encontradas por métodos matemáticos exatos como o fez de forma rápida e confiável. Isso sugere que, à medida que as cidades se tornam mais complexas e ricas em dados, buscas evolutivas bem desenhadas podem ajudar agências de transporte a planejar rotas que parecem mais diretas, exigem menos baldeações incômodas e fazem melhor uso de veículos e combustível.

Citação: Kazbek, R., Sergaziyev, M., Kenzhe, D. et al. A comparative analysis of crossovers in genetic algorithms for route optimization: case studies from Astana and Shymkent, Kazakhstan. Sci Rep 16, 13816 (2026). https://doi.org/10.1038/s41598-026-43898-7

Palavras-chave: roteamento de transporte público, algoritmos genéticos, mobilidade urbana, otimização de rotas, planejamento de cidades inteligentes