Modelo matemático acelera em 17x a divisão de redes viárias

O que aconteceu

O artigo "The Edge-based Contiguous p-median Problem with Connections to Logistics Districting" (arXiv:2608.11230, submetido em 30 de julho de 2026 na área de Inteligência Artificial) define o problema edge-based contiguous p-median (ECpM): particionar as ruas de uma rede viária em um número pré-definido de territórios compactos e contíguos. Duas formulações de programação binária foram propostas, ambas com distância de rede. A primeira usa restrições baseadas em cortes (cut set), em número exponencial, combinadas a um algoritmo de branch-and-cut. A segunda usa restrições de caminho mais curto (SPC), em número polinomial, e pode ser resolvida com solvers de prateleira.

Os testes foram feitos em redes viárias com mais de 2.700 nós e cerca de 3.400 arestas, gerando modelos com mais de 9,6 milhões de variáveis binárias. Segundo o resumo do paper, a resolução do modelo SPC com branch and bound padrão atingiu aceleração de até 17x no tempo computacional em relação à implementação com cut set e branch-and-cut.

Contexto

O problema p-mediana é clássico em pesquisa operacional: escolher p pontos para atender uma demanda minimizando distâncias. A versão edge-based desloca o foco dos nós para as arestas — no caso, as próprias ruas —, o que é mais adequado para distritização. O artigo também mostra que as restrições SPC são supervalid inequalities do modelo edge-based p-median (EpM), que não exige contiguidade: elas podem eliminar algumas soluções viáveis inteiras, inclusive ótimas, do problema mais simples.

O trabalho conecta o ECpM ao problema de distritização baseado em arestas (EBD), que adiciona um critério de equilíbrio de carga de trabalho entre os territórios.

Por que importa

Divisão de territórios é uma operação recorrente para empresas de delivery, varejo e serviços urbanos: definir regiões de entrega compactas e contíguas impacta diretamente o custo e o tempo de rota. No Brasil, onde a logística urbana pesa na operação de e-commerce e na distribuição de carga, um modelo que resolve o problema mais rápido e com software comercial reduz a barreira de entrada para técnicas avançadas de otimização.

Impacto

O ganho mais concreto aparece no problema EBD: o modelo anterior baseado em cut set não encontrou solução viável em 12 horas em nenhuma das instâncias testadas, enquanto o modelo baseado em SPC resolveu a maioria delas até a otimalidade. Na prática, isso significa tirar o problema da zona de inviabilidade computacional e levá-lo a soluções ótimas em tempo razoável.

O que muda

O uso de restrições de caminho mais curto em vez de cortes muda o custo-benefício de modelar contiguidade em redes viárias. Equipes sem acesso a implementações proprietárias passam a resolver o problema com solvers disponíveis no mercado. Além disso, o fato de as restrições SPC serem supervalid inequalities do EpM abre espaço para abordagens híbridas, em que essas restrições funcionam como cortes eficientes em modelos mais simples.

O que vem agora

O artigo não detalha próximos passos. A expectativa natural é a validação da abordagem em redes maiores, a combinação com outros critérios de balanceamento e eventuais aplicações em distritos logísticos reais.

Fontes

• arXiv (cs.AI): The Edge-based Contiguous p-median Problem with Connections to Logistics Districting — https://arxiv.org/abs/2608.11230