← Back to agents

AGENTS.md from phelys/vrptw-studies

Repository
⭐ 0 starsLast commit Aug 12, 2025

Guia de Uso: Opções de Algoritmos para Otimização de Rotas

Bem-vindo ao guia de instruções para a API de Otimização de Rotas! Este documento explica as opções disponíveis de algoritmos, como eles funcionam e oportunidades de uso em cenários logísticos reais. A aplicação suporta configurações flexíveis via JSON de entrada, permitindo adaptar a otimização a necessidades específicas, como redução de custos com combustível, segurança para motoristas (com pausas HOS) e diminuição de emissões de CO2.

Para usar a API, envie uma requisição POST para o endpoint `/solve` com um JSON contendo campos como `scenario`, `solver_mode`, `problem_type`, entre outros (veja exemplos de curl em documentações anteriores). Agora, vamos explorar as opções!

1. Opções de Modo de Solver (`solver_mode`)

O `solver_mode` define o tipo de algoritmo usado para resolver o problema de roteirização. Escolha com base no equilíbrio entre velocidade e precisão.

Heurístico (`heuristic`)

  • **Como funciona**: Utiliza abordagens aproximadas, como construção gulosa (inserindo pedidos em rotas de forma eficiente) seguida de melhorias locais (ex.: 2-opt ou relocate). Integra checagens incrementais para janelas de tempo (TW), capacidade, HOS (inserindo breaks automáticos) e precedência (pickup antes de delivery). É baseado em ALNS (Adaptive Large Neighborhood Search) para destruir e reparar soluções, adaptando operadores dinamicamente.
  • **Vantagens**: Rápido, escalável para instâncias grandes (milhares de pedidos), e robusto para uso online. Limita-se a soluções "boas o suficiente", não necessariamente ótimas.
  • **Oportunidades de uso**: Ideal para operações diárias em tempo real, como entregas urbanas com tráfego variável. Pergunte-se: "Se eu preciso de rotas viáveis em segundos para uma frota de entregas fracionadas (LTL), isso seria suficiente para reduzir custos sem atrasos excessivos?"

Exato (`exact`)

  • **Como funciona**: Emprega branch-price-and-cut com formulação set-partitioning (mestre) e SPPRC (Shortest Path Problem with Resource Constraints) no subproblema para gerar colunas (rotas viáveis). Usa label-setting com dominância para recursos como tempo, carga, HOS e janelas. Híbrido com heurísticas para aceleração inicial.
  • **Vantagens**: Garante soluções ótimas ou com bounds de qualidade, perfeito para planejamento tático. Mais computacionalmente intensivo, adequado para instâncias médias (até centenas de pedidos).
  • **Oportunidades de uso**: Útil em planejamento estratégico, como otimização de rotas anuais para cargas fechadas (FTL) com múltiplos depósitos. Reflita: "Em um cenário de logística sustentável, onde minimizar CO2 é crucial, valeria o tempo extra para uma solução exata que equilibra todos os objetivos?"

2. Tipos de Problemas (`problem_type`)

O `problem_type` adapta o solver a variantes do VRP, suportando coletas/entregas múltiplas, depósitos variados e cargas fracionadas/fechadas.

PDPTW (Pickup and Delivery Problem with Time Windows)

  • **Como funciona**: Cada pedido tem pickup e delivery com precedência (pickup antes), janelas de tempo, capacidade e HOS. Rotas respeitam FIFO em tempos dependentes.
  • **Oportunidades de uso**: Perfeito para entregas porta-a-porta com horários fixos, como e-commerce. Imagine: "Como isso ajudaria uma empresa de frete a coordenar coletas em vários pontos e entregas em destinos distantes, reduzindo pausas desnecessárias?"

VRPTW (Vehicle Routing Problem with Time Windows)

  • **Como funciona**: Foco em entregas (sem pickups explícitos), com janelas de tempo e capacidade. Similar ao PDPTW, mas sem precedência dupla.
  • **Oportunidades de uso**: Adequado para distribuição de mercadorias de um depósito central. Pergunte: "Em uma rede de varejo, como rotas otimizadas com janelas poderiam melhorar a eficiência sem violar regras de jornada?"

MDVRP (Multi-Depot Vehicle Routing Problem)

  • **Como funciona**: Veículos partem de múltiplos depósitos, alocando pedidos dinamicamente. Extensão do VRP com retornos ao depot de origem.
  • **Oportunidades de uso**: Ideal para redes logísticas regionais com armazéns distribuídos. Reflita: "Se sua operação tem depósitos em cidades diferentes, como isso exploraria rotas mais curtas para economizar combustível?"

SDVRP (Split Delivery Vehicle Routing Problem)

  • **Como funciona**: Permite dividir demandas de um pedido entre veículos/rotas, com checagens de frações.
  • **Oportunidades de uso**: Útil para cargas fracionadas (LTL) onde um pedido grande pode ser atendido por múltiplos veículos. Pense: "Em entregas de alto volume, como isso evitaria sobrecarga e melhoraria a sustentabilidade?"

FTL (Full Truckload)

  • **Como funciona**: Rotas dedicadas a cargas fechadas (um pedido por veículo), priorizando eficiência direta sem splits.
  • **Oportunidades de uso**: Para transportes de contêineres ou cargas completas. Questione: "Como isso se aplica a envios industriais onde velocidade e custo fixo são chave?"

LTL (Less Than Truckload)

  • **Como funciona**: Compartilhamento de veículos para cargas fracionadas, com consolidação de múltiplos pedidos.
  • **Oportunidades de uso**: Comum em hubs de distribuição para otimizar espaço. Imagine: "Em uma rede de e-commerce, como consolidar pedidos reduziria emissões de CO2?"

3. Cenários de Otimização (`scenario`)

Escolha um cenário para ajustar pesos automaticamente na função de custo (multiobjetivo: custo + penalidades + CO2).

Econômico (`economic`)

  • **Ajustes**: Aumenta peso em custo (x2.0), diminui CO2 (x0.5).
  • **Oportunidades de uso**: Foco em rotas curtas para menor combustível. Útil em operações com margens apertadas.

Ecológico (`ecologic`)

  • **Ajustes**: Aumenta peso em CO2 (x2.0), diminui custo (x0.8), estende tempo de solver (+200s).
  • **Oportunidades de uso**: Alinha com ESG, minimizando emissões. Ideal para empresas sustentáveis.

Eficiente (`efficient`)

  • **Ajustes**: Reduz tempo de solver (//2), força heurístico.
  • **Oportunidades de uso**: Respostas rápidas para decisões ágeis, como entregas urgentes.

Dicas Finais

  • Combine opções: Ex.: `exact` com `pdptw` e `ecologic` para planejamento sustentável exato.
  • Teste com JSON de exemplo e ajuste via `time_limit_sec`.
  • Oportunidades gerais: Integre com Valhalla para mapas reais, escalando para milhares de usuários via Celery/Docker.

Guia para Melhorar o Algoritmo de Otimização de Rotas

Este guia auxilia IAs como OpenAI Codex a refinar o solver de Rich VRP, focando em ALNS heurístico e branch-price-and-cut exato para variantes como PDPTW, MDVRP, SDVRP.

Melhorias no ALNS (Heurístico)

  • Integre tempos dependentes com FIFO via oracle aproximado, evitando loops negativos.<grok-card data-id="28fb4e" data-type="citation_card"></grok-card>
  • Adicione operadores destroy/repair para splits em SDVRP, permitindo divisão de demandas.<grok-card data-id="6f518b" data-type="citation_card"></grok-card>
  • Híbrido com local search (2-opt, 3-opt) e GLS para escapar de ótimos locais.<grok-card data-id="f60485" data-type="citation_card"></grok-card>
  • Considere múltiplos trips por veículo em time-dependent TDVRP.<grok-card data-id="dfab34" data-type="citation_card"></grok-card>
  • Incorpore tabu search para soft TW e penalidades.<grok-card data-id="ea3118" data-type="citation_card"></grok-card>

Avanços no Branch-Price-and-Cut (Exato)

  • Use ng-route relaxation em SPPRC para fortalecer bounds em PDPTW.<grok-card data-id="a62a5f" data-type="citation_card"></grok-card>
  • Adapte pricing para splits em SDVRP com cobertura fracionada no mestre.<grok-card data-id="2dda5f" data-type="citation_card"></grok-card>
  • Nested BPC para MDVRP com múltiplos depósitos no subproblema.<grok-card data-id="b3607d" data-type="citation_card"></grok-card>
  • Integre cortes subset-row e rounded capacity para variantes.<grok-card data-id="b8759f" data-type="citation_card"></grok-card>
  • Label-setting avançado com recursos para HOS e proportional service time.<grok-card data-id="b7fe71" data-type="citation_card"></grok-card>

Integração de Variantes e Ajustes Gerais

  • Para FTL/LTL: Limite rotas a cargas cheias ou consolidadas, ajustando capacidade.<grok-card data-id="f76772" data-type="citation_card"></grok-card>
  • Acelere pricing com heurísticas iniciais e pool de colunas de ALNS.<grok-card data-id="a647b1" data-type="citation_card"></grok-card>
  • Teste em instâncias reais com time-dependent travel e congestion avoidance.<grok-card data-id="eb3a31" data-type="citation_card"></grok-card>
  • Paralelize ALNS operators e SPPRC extensions para escalabilidade.

Requisição curl para heuristic, pdptw, economic

curl -X POST "http://localhost:8000/solve" -H "Content-Type: application/json" -d '{ "scenario": "economic", "depots": [{"id": "D1", "loc": {"lat": -25.5, "lon": -49.2}, "tw": [["2025-08-12T06:00:00", "2025-08-12T22:00:00"]]}], "vehicles": [{"id": "V1", "depot": "D1", "capacity": {"weight": 12000, "volume": 38}, "costs": {"fixed": 200, "per_km": 1.8, "per_h": 85}, "hos": {"max_continuous_drive_min": 270, "break_min": 30, "max_work_min": 720, "daily_rest_min": 660}}], "requests": [{"id": "R101", "pickup": {"loc": {"lat": -25.45, "lon": -49.25}, "tw": [["2025-08-12T08:00:00", "2025-08-12T10:00:00"]], "svc_min": 15}, "delivery": {"loc": {"lat": -25.60, "lon": -49.30}, "tw": [["2025-08-12T11:00:00", "2025-08-12T13:00:00"]], "svc_min": 20}, "demand": {"weight": 3200, "volume": 9.5}}], "travel_time": {"mode": "time-dependent", "valhalla_url": "https://security.cargomaps.com.br", "costing": "truck"}, "objectives": {"cost": 1.0, "lateness_penalty": 50, "co2_per_km": 0.9}, "settings": {"solver_mode": "heuristic", "time_limit_sec": 300}, "problem_type": "pdptw" }'

Requisição curl para exact, vrptw, ecologic

curl -X POST "http://localhost:8000/solve" -H "Content-Type: application/json" -d '{ "scenario": "ecologic", "depots": [{"id": "D1", "loc": {"lat": -25.5, "lon": -49.2}, "tw": [["2025-08-12T06:00:00", "2025-08-12T22:00:00"]]}], "vehicles": [{"id": "V1", "depot": "D1", "capacity": {"weight": 12000, "volume": 38}, "costs": {"fixed": 200, "per_km": 1.8, "per_h": 85}, "hos": {"max_continuous_drive_min": 270, "break_min": 30, "max_work_min": 720, "daily_rest_min": 660}}], "requests": [{"id": "R101", "pickup": {"loc": {"lat": -25.45, "lon": -49.25}, "tw": [["2025-08-12T08:00:00", "2025-08-12T10:00:00"]], "svc_min": 15}, "delivery": {"loc": {"lat": -25.60, "lon": -49.30}, "tw": [["2025-08-12T11:00:00", "2025-08-12T13:00:00"]], "svc_min": 20}, "demand": {"weight": 3200, "volume": 9.5}}], "travel_time": {"mode": "time-dependent", "valhalla_url": "https://security.cargomaps.com.br", "costing": "truck"}, "objectives": {"cost": 1.0, "lateness_penalty": 50, "co2_per_km": 0.9}, "settings": {"solver_mode": "exact", "time_limit_sec": 300}, "problem_type": "vrptw" }'

Requisição curl para heuristic, mdvrp, efficient

curl -X POST "http://localhost:8000/solve" -H "Content-Type: application/json" -d '{ "scenario": "efficient", "depots": [{"id": "D1", "loc": {"lat": -25.5, "lon": -49.2}, "tw": [["2025-08-12T06:00:00", "2025-08-12T22:00:00"]]}, {"id": "D2", "loc": {"lat": -25.6, "lon": -49.3}, "tw": [["2025-08-12T06:00:00", "2025-08-12T22:00:00"]]}], "vehicles": [{"id": "V1", "depot": "D1", "capacity": {"weight": 12000, "volume": 38}, "costs": {"fixed": 200, "per_km": 1.8, "per_h": 85}, "hos": {"max_continuous_drive_min": 270, "break_min": 30, "max_work_min": 720, "daily_rest_min": 660}}], "requests": [{"id": "R101", "pickup": {"loc": {"lat": -25.45, "lon": -49.25}, "tw": [["2025-08-12T08:00:00", "2025-08-12T10:00:00"]], "svc_min": 15}, "delivery": {"loc": {"lat": -25.60, "lon": -49.30}, "tw": [["2025-08-12T11:00:00", "2025-08-12T13:00:00"]], "svc_min": 20}, "demand": {"weight": 3200, "volume": 9.5}}], "travel_time": {"mode": "time-dependent", "valhalla_url": "https://security.cargomaps.com.br", "costing": "truck"}, "objectives": {"cost": 1.0, "lateness_penalty": 50, "co2_per_km": 0.9}, "settings": {"solver_mode": "heuristic", "time_limit_sec": 300}, "problem_type": "mdvrp" }'