Tecnologia de otimização matemática para navios cargueiros

Otimização da rede de transporte de navios cargueiros: técnicas de otimização matemática

Visão geral

• A equipe de pesquisa do Google anunciou uma nova Shipping Network Design API.
• Essa API ajuda a resolver problemas de projeto de rede e programação de navios cargueiros.
• Essa solução é mais rápida e eficiente do que os métodos existentes, dobra a receita e permite transportar mais contêineres com menos embarcações.

Contexto

• O LSNDSP (problema de projeto e programação de rede de embarcações) é composto por três elementos: projeto de rede, programação da rede e roteamento de contêineres.
• Tradicionalmente, esses problemas eram resolvidos separadamente, mas resolvê-los ao mesmo tempo pode levar a soluções melhores.

Metodologia

• Um problema de otimização é composto por variáveis, restrições e função objetivo.
• O Google resolveu o problema usando duas abordagens: Double Column Generation e CP-SAT.
• Esses métodos fornecem soluções ótimas para problemas de pequeno e médio porte, mas não são adequados para problemas de grande escala.
• Para resolver problemas de grande escala, foram usados Large Neighborhood Search e Variable Neighborhood Search.
• Esses métodos reduzem o espaço de busca e aumentam a eficiência por meio de processamento paralelo.

Resultados

• O desempenho foi avaliado usando o benchmark LINERLIB.
• A solução do Google permite transportar mais contêineres com menos embarcações.
• Em cada cenário, ela aumenta a eficiência e eleva significativamente a receita.

Conclusão

• A técnica de otimização do Google é o primeiro método capaz de resolver problemas de projeto e programação de redes de embarcações em grande escala.
• Espera-se que essa pesquisa contribua para aumentar a eficiência da cadeia global de suprimentos.

Opinião do GN⁺

• Contexto técnico: o LSNDSP é um problema complexo de otimização, no qual é necessário resolver simultaneamente projeto de rede, gestão de programação e roteamento.
• Importância industrial: como 90% do comércio global depende do transporte marítimo, resolver esse problema tem grande impacto econômico.
• Desafio técnico: para resolver problemas de grande escala, são necessárias técnicas avançadas como processamento paralelo e redução do espaço de busca.
• Produtos concorrentes: outras soluções de otimização com funções semelhantes incluem IBM CPLEX e Gurobi.
• Pontos a considerar: ao adotar uma nova tecnologia, pode haver custo inicial de configuração e curva de aprendizado. No entanto, no longo prazo, ela pode melhorar bastante a eficiência e a rentabilidade.

[GN⁺]

Comentários do Hacker News

• Opinião do ponto de vista do terminal: a otimização de terminais é muito complexa, e cada terminal funciona de um jeito diferente, o que dificulta a escalabilidade.
• Recomendação do livro "The Box": um livro sobre a história inicial da conteinerização, uma leitura interessante que mistura engenharia, design, negócios e história.
• Problema de otimização de contêineres: o problema de otimização de contêineres para grandes frotas ainda não foi resolvido.
• Melhoria do Google OR: o Google OR melhora as soluções existentes em 10% a 20%.
• Uso de API: há dúvidas se vale a pena tentar em uma situação em que a demurrage (taxa de sobre-estadia) não foi considerada.
• Curiosidade sobre o uso do endpoint da API: há curiosidade sobre usar na prática o endpoint de API oferecido pelo Google.
• Recomendação do Omega Tau Podcast: há um excelente episódio sobre transporte de contêineres e otimização.
• Execução em contêiner Docker: só funciona quando executado em um contêiner Docker.
• Sugestão de uso de algoritmo: talvez seja possível resolver o planejamento de escala de funcionários de meio período com um algoritmo.
• Oferta do OR-tools como serviço: parece que começaram a oferecer o OR-tools como serviço. Se houvesse uma API melhor, haveria disposição para pagar pelos custos de computação no GCP.
• Dúvida sobre planejamento de carregamento: o planejamento de carregamento é um problema que precisa ser resolvido na etapa seguinte ao planejamento de rota. É apresentado um cálculo aproximado da velocidade de operação dos guindastes e do processo de carga/descarga.
• Complexidade do planejamento de carregamento: o planejamento de carregamento inclui critérios como peso, equilíbrio, energia e aceitabilidade de valor. Por causa dessa complexidade, foi feita uma tentativa de cálculo simples.