O Caixeiro Viajante, tomates e o código que move o mundo real Featured Post

Lembro-me do começo dos anos 2000, na faculdade, quando o "Problema do Caixeiro Viajante" (PCV) era uma espécie de bicho-papão teórico. Era o exemplo clássico de um problema NP-difícil, algo que a gente discutia em aulas de complexidade de algoritmos com um misto de fascínio e distanciamento acadêmico. Era um quebra-cabeça elegante, um desafio intelectual sobre encontrar a rota mais curta para visitar um conjunto de cidades. Naquela época, para mim e para muitos dos meus colegas, era isso: um problema de lousa, um exercício mental. A gente sonhava em construir o próximo sistema operacional, a próxima rede social, o próximo grande software que mudaria a forma como as pessoas interagiam com o digital.

Corta para hoje. Mais de duas décadas depois, com uma boa dose de cabelos brancos e cicatrizes de projetos que deram certo (e muitos que deram errado), eu me pego lendo um artigo científico que me jogou de volta para aquele tempo, mas com um banho de realidade tão forte que me fez abrir o blog pra escrever a respeito. O artigo não fala de cidades hipotéticas. Fala de Gana. Não fala de um vendedor abstrato. Fala da distribuição de polpa de tomate da marca "Sweet Mama Tomatoes Mix". E o desafio não é apenas a distância, mas um emaranhado de variáveis que fariam o nosso PCV da faculdade parecer um passeio no parque: frota de veículos com capacidades e custos diferentes, trânsito que muda de acordo com o dia da semana e a hora do dia, e a necessidade de entregar tudo em até seis dias.

Isso me pegou em cheio. Enquanto passamos os dias discutindo a melhor forma de implementar microsserviços, qual framework de JavaScript é o rei da vez ou como otimizar a latência de uma API em milissegundos, um time de pesquisadores estava usando matemática pesada para garantir que um caminhão de tomates chegasse ao seu destino da forma mais barata e eficiente possível.

E é sobre isso que eu quero falar hoje. Sobre a beleza do código que não vemos, sobre a complexidade dos problemas do mundo real e sobre como, talvez, a gente precise reavaliar o que consideramos ser um "desafio técnico interessante".

Mas o que diabos é QCMINLP e por que eu deveria me importar?

O título do artigo é uma sopa de letrinhas que assusta: "A quadratically constrained mixed-integer non-linear programming model for multiple sink distributions". Vamos ser honestos, se isso aparecesse em uma vaga de emprego, 98% dos desenvolvedores atuais passariam reto. Mas é assim que a gente separa os adultos das crianças. Quando a gente desempacota esses termos, a gente começa a entender a natureza do problema que eles estão resolvendo.

O nome da abordagem é Programação de Modelo Misto Inteiro Não Linear Quadraticamente Restrito (QCMINLP). Vamos traduzir isso para a nossa linguagem do dia a dia.

• Programação de modelo (Programming Model): Aqui, "programação" não é sobre escrever laços forou condicionais if. É sobre descrever um problema. Em vez de dizer ao computador como fazer algo (programação imperativa), você diz a ele o que você quer como resultado e quais são as regras do jogo (programação declarativa). Você define um objetivo (ex: minimizar o custo) e uma lista de restrições (ex: o caminhão não pode carregar mais de 10 toneladas; a entrega tem que ser feita esta semana).
• Misto inteiro (Mixed-Integer): Isso significa que algumas das suas variáveis de decisão têm que ser números inteiros. Por exemplo, você não pode enviar 2,5 caminhões. Ou você envia 2 ou envia 3. Outras variáveis, como a quantidade de combustível, podem ser fracionárias. Essa simples distinção aumenta a complexidade de forma brutal.
• Não linear (Non-Linear): Aqui a coisa fica séria. Em muitos problemas simples, a relação entre as variáveis é linear. Se um caminhão custa 100 por viagem, dois caminhões custam 200. Mas no mundo real, as coisas raramente são assim. O consumo de combustível, por exemplo, não aumenta de forma linear com a velocidade ou o peso. Existem eficiências e ineficiências que criam curvas, não retas. O modelo do artigo leva isso em conta.
• Quadraticamente restrito (Quadratically Constrained): É um tipo específico de não-linearidade, onde as restrições envolvem variáveis elevadas ao quadrado. Isso adiciona outra camada de complexidade, mas permite modelar relações mais realistas do mundo físico.

Por que você, arquiteto de software ou desenvolvedor sênior, deveria se importar com isso? Porque isso representa uma forma de resolver problemas que está fora da nossa bolha de APIs REST e bancos de dados CRUD. Nós estamos acostumados a construir sistemas que respondem a eventos. O usuário clica, nós processamos, gravamos no banco. É uma lógica reativa.

A programação matemática, por outro lado, é sobre encontrar a melhor solução possível dentro de um universo de possibilidades gigantesco. Os pesquisadores não escreveram um algoritmo que diz: "Se for segunda de manhã, pegue a Rota A". Eles descreveram o universo do problema: todos os caminhões, todos os varejistas, todas as janelas de tempo, todas as demandas, todas as regras. E então, eles entregaram essa descrição para uma ferramenta especializada, um "solver" (no caso, o Gurobi), que é um motor otimizado para explorar esse universo e encontrar a resposta ótima.

Isso é arquitetura de software em um nível diferente. Não é sobre desenhar caixinhas e setas entre serviços. É sobre modelar a realidade matematicamente de uma forma que um computador possa "entender" e otimizar.

Dissecando o problema real

O que mais me fascinou no artigo foi o quão profundamente eles mergulharam na sujeira do problema real. Isso não é teoria. Eles coletaram dados de diversas fontes: a frota de veículos da fábrica, as dimensões e pesos dos produtos, dados de GPS e Google Maps para distâncias e padrões de tráfego, e dados históricos de vendas para prever a demanda.

As restrições do modelo são um reflexo direto dos desafios do mundo real:

1. Frota heterogênea: Eles não têm uma frota de caminhões idênticos. Têm caminhões e uma van, cada um com sua própria capacidade de carga (volume e peso), custo de manutenção e consumo de combustível. Isso significa que a escolha do veículo para cada rota é, por si só, uma variável de otimização.
2. Múltiplas janelas de tempo: A distribuição ocorre de segunda a sábado, e cada dia é dividido em três períodos: manhã, tarde e noite. O trânsito em Kumasi, uma das cidades do estudo, não é o mesmo às 8h da manhã e às 8h da noite. O modelo precisa decidir não apenas qual rota seguir, mas quando segui-la.
3. Entregas em cadeia (Multi-Sink): Um caminhão não sai do armazém, entrega em um único varejista e volta. Isso seria um desperdício. O modelo otimiza rotas contínuas, onde um veículo visita múltiplos varejistas em sequência. A figura 9 do artigo ilustra isso perfeitamente. Vemos rotas onde um caminhão sai do armazém (WH), vai para o varejista Rt45, de lá para o Rt16, e do Rt16 se divide para atender outros varejistas como Rt66 e Rt41. Isso é o caixeiro viajante com esteroides.
4. Otimização de Carregamento: Não basta definir a rota, é preciso carregar o caminhão de forma inteligente. Se você vai visitar os varejistas A, B e C, nessa ordem, os produtos para o varejista C devem ser carregados primeiro (no fundo do caminhão), e os do varejista A por último (perto da porta). O estudo foi além e usou um software chamado PackVol para otimizar o empacotamento físico da carga, garantindo que o descarregamento fosse eficiente. A Figura 14 mostra essa visão, com a carga colorida por produto e por destino, uma visualização fantástica do resultado prático da otimização.

O resultado? Uma redução de custos de transporte de 27,59%. Eles tiraram o custo médio de GHS 20.270 (cerca de US$ 1.638) para GHS 14.676 (cerca de US$ 1.186). Isso não é uma otimização de 5% em um A/B test de um botão. Isso é um impacto real e massivo no resultado financeiro de uma empresa, que se traduz em sustentabilidade, preços mais competitivos e, no final das contas, na viabilidade do negócio.

E a Inteligência Artificial? Onde entra o Reinforcement Learning?

Agora, como o "provocador" que sou, não posso deixar de fazer a pergunta que muitos de vocês devem estar pensando. "Tudo isso é muito bonito, mas parece uma abordagem muito clássica, matemática, rígida. E a IA? E o aprendizado de máquina? Não poderíamos treinar um modelo de Reinforcement Learning (RL) para fazer isso de forma mais adaptativa?"

A resposta é: sim, poderíamos. E essa é a grande discussão arquitetural aqui. O próprio artigo, em sua revisão de trabalhos relacionados, cita estudos que usam deep reinforcement learning para otimização de rotas em tempo real.

Transformer Aided Supply Chain Network Design | Towards Data Science

Using transformer to help solve a classic problem in supply chain - facility location problem

Towards Data ScienceGuangrui Xie

Estamos diante de um clássico trade-off, uma escolha fundamental que nós, arquitetos e desenvolvedores, enfrentamos todos os dias, mesmo que em contextos diferentes. É a batalha entre a Otimização Clássica e o Aprendizado de Máquina.

A abordagem do artigo (otimização clássica com solvers):

• Prós:
  • Garantia de otimização: Dentro das premissas do modelo, a solução encontrada é provavelmente a melhor possível. O solver explora o espaço de soluções matematicamente para encontrar o ótimo global (ou chega muito perto dele).
  • Explicitabilidade: O modelo é explícito. Todas as restrições e a função objetivo são definidas por humanos. Se o resultado parece estranho, você pode auditar as equações e os dados de entrada para entender o porquê. Não é uma "caixa-preta".
• Contras:
  • Custo computacional: Encontrar essa solução ótima é extremamente pesado. O próprio artigo menciona que a solução levou 6 horas e 7 minutos para ser encontrada. Isso a torna inviável para replanejamento em tempo real.
  • Rigidez: O modelo é tão bom quanto os dados que o alimentam. Ele se baseia em médias de tráfego e demandas previstas. Se um caminhão quebra no meio da rota ou uma estrada é subitamente interditada, o modelo não tem como reagir. É preciso rodar todo o cálculo novamente, o que leva horas.
  • Complexidade de modelagem: Construir esse modelo matemático requer um conhecimento especializado profundo que a maioria das equipes de desenvolvimento não possui.

A abordagem alternativa (Reinforcement Learning):

• Prós:
  • Adaptabilidade e velocidade (em tempo de inferência): Um agente de RL, uma vez treinado, pode tomar decisões em milissegundos. Ele aprende uma "política" – um conjunto de regras sobre qual a melhor ação a tomar em um determinado estado. Se uma estrada fecha, o estado do ambiente muda, e o agente pode rapidamente decidir por uma nova rota com base no que aprendeu.
  • Capacidade de aprender com a experiência: O modelo pode ser continuamente retreinado com dados reais, aprendendo novos padrões de tráfego, tempos de descarregamento, etc., e melhorando com o tempo.
• Contras:
  • Sem garantia de otimização: A solução encontrada pelo RL é, por natureza, uma heurística. É uma solução "muito boa", mas raramente se pode provar que é a melhor solução possível.
  • Problema da "caixa-preta": Pode ser extremamente difícil entender por que o agente de RL tomou uma determinada decisão. A sua lógica está distribuída em milhões de pesos de uma rede neural.
  • Necessidade de dados massivos: O treinamento de um agente de RL robusto requer uma quantidade gigantesca de dados ou um ambiente de simulação muito preciso, o que, por si só, é um desafio de engenharia complexo.

Então, qual é a melhor? A pergunta está errada. A pergunta correta é: "Qual abordagem é a mais adequada para o problema em questão?"

Para um planejamento estratégico semanal, onde você tem tempo para rodar um cálculo pesado e o objetivo é encontrar o plano mais otimizado possível com base em dados históricos, a abordagem QCMINLP é fantástica. Ela te dá um plano mestre de altíssima qualidade.

Para uma operação em tempo real, onde um motorista precisa de uma nova rota agora porque há um acidente à frente, um modelo de RL seria infinitamente superior.

A solução ideal, na minha experiência, é muitas vezes um híbrido. Você usa a otimização clássica para criar o plano estratégico (o "o que" e "quando" geral) e usa modelos mais ágeis, talvez baseados em heurísticas ou ML, para o ajuste tático, do dia a dia (o "como" em tempo real).

Lições para Arquitetos e Desenvolvedores (mesmo que você não entregue tomates)

A essa altura, você pode estar pensando: "Ok, legal, mas eu construo APIs para uma fintech. O que a logística de tomates em Gana tem a ver comigo?". Eu acredito que tem tudo a ver. Este artigo é uma aula magna sobre princípios de engenharia e arquitetura de software que transcendem qualquer domínio.

1. Entenda a profundidade do problema: Os autores não pararam na superfície. Eles foram fundo para entender as nuances: os diferentes caminhões, as janelas de tráfego, a necessidade de entregas em cadeia. Com que frequência nós, como desenvolvedores, realmente mergulhamos no domínio de negócio dos nossos usuários? Ou nos contentamos em traduzir tickets do Jira em código, sem questionar as premissas? A melhor solução técnica nasce de uma compreensão profunda do problema humano.
2. Conheça suas ferramentas (além do básico): Nossa indústria é obcecada por frameworks web e bancos de dados. Mas o mundo da computação é vasto. Existem ferramentas como solvers (Gurobi, CPLEX), bibliotecas de computação científica (SciPy, NumPy), e plataformas de simulação. Saber que essas ferramentas existem, mesmo que você não seja um especialista, expande seu horizonte como arquiteto. Nem todo problema é um prego, e nem toda solução é um martelo de microsserviços.
3. A "Solução Perfeita" é um mito. Abrace os trade-offs: A discussão entre otimização clássica e RL é o exemplo perfeito. Não existe "a melhor arquitetura". Existe a arquitetura mais adequada para um conjunto de restrições, requisitos e objetivos. Nosso trabalho como arquitetos e líderes técnicos não é encontrar a resposta certa, mas sim fazer as perguntas certas e entender as consequências de cada escolha. Otimização vs. Adaptabilidade. Consistência vs. Disponibilidade. Custo vs. Performance. É nesse balanço que reside a nossa arte.
4. O código mais importante pode ser invisível: Ninguém vai postar no Instagram uma foto da linha de comando rodando o solver Gurobi por 6 horas. Não é "sexy". Não tem uma interface bonita. Mas o resultado desse código move o mundo físico. Ele economiza combustível, reduz emissões, torna um negócio viável e garante que produtos cheguem às prateleiras. Nós, na indústria de tecnologia, desenvolvemos uma obsessão pela interface, pela experiência do usuário visível. Mas precisamos celebrar e valorizar igualmente a engenharia de "back-office", a otimização de processos, o código que, silenciosamente, faz o mundo funcionar de forma um pouco melhor.

Ao final do dia, ler este artigo me trouxe uma dose de humildade e inspiração. Humildade para reconhecer a complexidade dos problemas do "mundo real" em comparação com os quebra-cabeças que muitas vezes criamos para nós mesmos no mundo digital. E inspiração para lembrar que a programação, em sua essência, é uma ferramenta para resolver problemas. Problemas de todos os tipos, desde conectar pessoas até, sim, garantir que a polpa de tomate chegue fresca ao seu destino.

Então, eu deixo uma pergunta para você. A última linha de código que você escreveu... que problema do mundo real ela realmente resolveu?