Tecnologia de otimização matemática para navios de carga
(research.google)- A equipe de Operations Research do Google Research lançou a Shipping Network Design API, que otimiza em conjunto o desenho da rede, a programação e o roteamento de contêineres de navios porta-contêineres regulares
- Esse problema exige decidir ao mesmo tempo a ordem de visita dos navios aos portos, os horários de chegada e partida, e as rotas origem-destino dos contêineres, o que o torna complexo em escala de 500 navios e 200 portos no cenário WorldLarge
- A abordagem inicial, com geração dupla de colunas e CP-SAT, encontrou soluções ótimas comprováveis em problemas pequenos e médios, mas para problemas grandes foram necessárias heurísticas que combinam busca em grande vizinhança e busca em vizinhança variável
- No benchmark LINERLIB, o volume de contêineres movimentados em WorldSmall, EuropeAsia, Pacific e Mediterranean aumentou em 35%, 14%, 35% e 32%, respectivamente, enquanto o número de navios usados caiu 7%, 15%, 4% e 23%
- O Google considera esse o primeiro método capaz de resolver problemas de desenho de rede e programação em escala WorldLarge e passará a oferecer a Shipping Network Design API como parte das futuras Operations Research APIs
O problema de otimizar simultaneamente redes de transporte marítimo de contêineres
- 90% dos produtos no mundo se movem por via marítima, e grandes cargueiros podem ter 0,25 milha de comprimento, pesar 250 mil toneladas, transportar 12 mil contêineres e levar cargas avaliadas em até 1 bilhão de dólares
- Diferentemente de aviões, trens e caminhões, navios de carga operam quase continuamente e se deslocam em rotas circulares no mar
- Rotas e cronogramas ineficientes aumentam o tempo de permanência dos contêineres nos portos, fazem navios esperarem no mar e atrasam o fluxo logístico, afetando até o preço dos produtos
- A Shipping Network Design API do Google implementa uma nova solução para esse problema
- É mais rápida e escala melhor do que tentativas conhecidas anteriormente
- Pode dobrar o lucro das companhias de navegação de contêineres, transportar 13% mais contêineres e operar com 15% menos navios
As três decisões que o LSNDSP precisa resolver em conjunto
- O Liner Shipping Network Design and Scheduling Problem, ou LSNDSP, trata simultaneamente de três decisões
- Desenho da rede: decidir em que ordem os navios visitarão os portos
- Programação da rede: definir quando os navios chegam e partem
- Roteamento de contêineres: escolher que trajeto os contêineres seguirão da origem ao destino
- As companhias de transporte marítimo de contêineres precisam resolver os três problemas, mas normalmente fazem isso de forma sequencial
- Resolver os três ao mesmo tempo aumenta a dificuldade, mas também amplia a chance de encontrar soluções melhores
- O resultado do desenho da rede leva a um pequeno conjunto de linhas de serviço seguidas pelos navios
- Por exemplo, uma rota do Leste Asiático até o sul da Europa passando pelo Canal de Suez
- As linhas de serviço são publicadas com datas, para que os embarcadores saibam quando e onde preparar seus contêineres
Restrições criadas por atracação, transbordo e atrasos
- Navios porta-contêineres não podem atracar no porto quando quiserem; eles precisam usar janelas de atracação definidas com antecedência
- Depois de se aproximar do porto, o navio pode lançar âncora em uma área de fundeio e esperar até o momento disponível para atracar
- Se o porto estiver congestionado, essa espera pode durar horas ou dias
- Um cronograma de rede preciso inclui não só em que dia atracar, mas também em que horário
- O navio pode aumentar a velocidade para chegar em um horário específico
- Também pode reduzir a velocidade para economizar combustível
- Ao atracar, guindastes descarregam os contêineres e carregam no navio os contêineres da próxima perna da viagem
- Se o cronograma atrasar, pode ocorrer o cut-and-run, quando o navio parte antes de carregar todos os contêineres previstos
- Os contêineres restantes acabam sendo levados por um navio posterior
- Quando um contêiner passa tempo em um porto intermediário no caminho da origem ao destino, isso é chamado de transbordo
- O transbordo aumenta ainda mais o número de soluções possíveis para o LSNDSP
- É apenas uma entre várias restrições que afetam a geração de rotas de contêineres
Método de otimização: da geração de colunas à busca em vizinhança
- Todo problema de otimização é composto de variáveis, restrições sobre essas variáveis e uma função objetivo a ser minimizada ou maximizada
- Ex.: navios e portos são variáveis
- Ex.: o número de contêineres que cabem em um navio é uma restrição
- Ex.: maximizar o número de contêineres transportados é a função objetivo
- Variáveis e restrições normalmente são representadas em forma de matriz, em que colunas representam variáveis e linhas representam restrições
- Uma técnica comum para decompor problemas grandes é a geração de colunas
- No início, considera-se apenas parte das variáveis
- Depois, novas variáveis, isto é, novas colunas, são geradas para aproximar melhor o problema original
- O Google desenvolveu uma biblioteca de software que analisa o problema e prevê quais colunas vale a pena gerar
- Essa biblioteca será disponibilizada como open source por meio do framework de programação matemática MathOpt
Limites de duas abordagens básicas
- A geração dupla de colunas trata o desenho da rede e o roteamento de contêineres como dois problemas acoplados
- Cada problema é composto por um problema principal que escolhe as melhores opções e um subproblema de geração que encontra opções razoáveis
- Algoritmos de caminho mínimo são aplicados a cada par de problemas para gerar escolhas viáveis
- Em seguida, o solver de programação linear Glop é usado para escolher as melhores opções em cada problema
- A geração de colunas é aplicada aos dois problemas simultaneamente, de modo que os resultados intermediários de um influenciem o andamento do outro
- Embora tenha encontrado soluções ótimas comprováveis, essa abordagem escalou bem apenas até problemas de porte médio
- Também foi testada uma implementação baseada em CP-SAT
- Foi usado o solver de programação por restrições CP-SAT do Google
- Funcionou bem até redes de porte médio, mas não escalou para problemas de transporte marítimo em escala global
- Ambas as abordagens encontraram soluções ótimas comprováveis em problemas pequenos e médios, mas não tinham escalabilidade suficiente para os casos grandes
Heurísticas para escalar em problemas grandes
- Para aumentar a escalabilidade, foram aplicadas duas variações de busca local que procuram oportunidades de melhoria examinando a vizinhança de soluções existentes
- A busca em grande vizinhança fixa parte da solução e então aplica os métodos anteriores
- Ex.: fixar uma condição como “este navio visita Los Angeles em terças-feiras alternadas”
- Isso reduz o espaço de busca e melhora a escalabilidade
- A busca em vizinhança variável explora vizinhanças tanto da rede quanto da programação
- A busca é paralelizada e distribuída entre várias máquinas para avaliar muitas vizinhanças ao mesmo tempo
- Isso permite limitar o espaço de busca ao mesmo tempo em que incorpora conhecimento de Operations Research e da indústria marítima
- As duas abordagens usam um método incremental que trava partes promissoras da solução e parte de soluções já boas para encontrar soluções ainda melhores
- Tentativas anteriores não consideravam o tempo de transporte porque isso tornava o problema muito mais difícil, mas o Google verificou que incluí-lo melhora significativamente a qualidade da solução
Resultados no benchmark LINERLIB
- A avaliação de desempenho usou o benchmark industrial LINERLIB, voltado para problemas de desenho de redes marítimas
- O benchmark inclui frotas, portos e demanda de contêineres em cenários de transporte marítimo
- Os cenários de teste incluem WorldSmall, EuropeAsia e WorldLarge
- O WorldLarge inclui 500 navios, 200 portos e cerca de 140 mil contêineres
- O objetivo da otimização não é simplesmente maximizar o número de contêineres nem minimizar o número de navios
- Se só o número de contêineres for maximizado, mais navios podem ser colocados em operação, elevando os custos
- Se só o número de navios for minimizado, pode surgir um tempo de entrega irrealisticamente longo, como usar um único navio para transportar todos os contêineres
- O LINERLIB equilibra isso por meio de uma estimativa de lucro obtida subtraindo dos ganhos com entregas no prazo os custos de navegação e de movimentação de contêineres nos portos
- Em comparação com a linha de base, o método do Google roteou mais contêineres usando menos navios
- WorldSmall: volume de contêineres +35%, número de navios -7%
- EuropeAsia: volume de contêineres +14%, número de navios -15%
- Pacific: volume de contêineres +35%, número de navios -4%
- Mediterranean: volume de contêineres +32%, número de navios -23%
- Com base nas premissas econômicas do LINERLIB, a margem de lucro esperada também melhorou de forma significativa
API e materiais publicados em seguida
- O Google considera esse o primeiro método capaz de resolver problemas de desenho de rede e programação em escala WorldLarge
- Mais detalhes sobre os resultados podem ser vistos na página de benchmark do LSNDSP
- A Shipping Network Design API será uma das futuras Operations Research APIs
1 comentários
Opiniões no Hacker News
Estou do lado dos terminais desse setor e, embora seja interessante, parece muito acadêmico
Fico curioso para saber se isso foi feito de fato em colaboração com armadores. Do lado dos terminais, estamos profundamente envolvidos em otimização de contêineres, e é praticamente um pesadelo. Mesmo terminais pertencentes à mesma empresa operam de formas muito diferentes, e muitas vezes até a terminologia varia dentro da própria empresa. Mesmo que você otimize para um terminal, no terminal seguinte precisa refazer 80%, então qualquer solução é muito difícil de escalar
Por exemplo, engenheiros alemães resistiam a bloquear recursos de veículos antes da produção em massa, porque assim não poderiam usá-los para lazer. Na área médica, os custos de horas extras chegavam à casa dos bilhões, então parecia fácil melhorar as escalas, mas havia muitas restrições sindicais e também falta de oferta de contratações. Fico curioso para saber quão realista é a solução do Google. Ela também inclui restrições como mísseis houthis? Pela minha experiência, muitas vezes uma solução que se ajusta facilmente a mudanças inesperadas vale mais do que uma solução ótima comprovável
Concordo que a otimização objetiva em geral é acadêmica. Sempre há motivos pelos quais é difícil ou impossível seguir exatamente a versão mais eficiente de um processo padronizado. Às vezes são motivos “bobos” causados por pessoas, e frequentemente são motivos razoáveis que refletem externalidades como clima, downtime, interrupções na cadeia de suprimentos e a irregularidade dos sinais de demanda e das previsões por sazonalidade. Ainda assim, acho que quase sempre é melhor começar pelo processo mais eficiente e acrescentar o tratamento de exceções, em vez de criar um processo padrão com base nas exceções conhecidas. Se você deixa a exceção virar regra, sempre vai operar de forma menos eficiente do que o ótimo
Este setor é difícil, e o cenário político é ainda mais complicado porque os sindicatos de trabalhadores portuários tradicionalmente são fortes. Problemas que parecem poder ser separados de forma limpa e receber nomes, na prática, estão todos entrelaçados; se você espera que um algoritmo os resolva “magicamente” para o usuário, quase sempre vai fracassar. Este setor engole facilmente empresas de software fortes que entram pensando: “é só rodar o problema do caixeiro-viajante / um solucionador de restrições / a abordagem que eu quiser, não é?”. Pessoas inteligentes certamente são necessárias, mas é preciso começar com humildade e conversar primeiro com usuários reais. Não vejo informações de contato no perfil, mas, se quiser trocar ideias com outra empresa do setor, mande um e-mail. Estamos fazendo trabalhos interessantes especialmente no segmento de terminais com menos de 1 milhão de TEUs por ano, com alta participação de transporte intermodal
Estou lendo The Box, sobre a história inicial da conteinerização, e é realmente fascinante
Recomendo muito para quem procura uma leitura agradável que mistura engenharia, design, negócios e história. Também faz meus pequenos problemas de programação parecerem ridículos
Sei que isso provavelmente vai gerar muitas objeções, mas falando sinceramente, acho que o impacto do contêiner marítimo de 20 pés no mundo foi maior do que o impacto que grandes modelos de linguagem provavelmente conseguirão alcançar. Leiam o livro primeiro e depois me digam por que estou errado. Claro que não estou errado
Pelo visto, em frotas muito grandes, a otimização de contêineres ainda era um problema em aberto. Eu não sabia
Se a pesquisa operacional do Google melhorou a utilização em 10% a 20% em relação às soluções existentes, isso é impressionante
https://en.wikipedia.org/wiki/Packing_problems
Tenho muita curiosidade para saber se existe algum uso real deste endpoint de API publicado: https://developers.google.com/optimization/service/shipping/...
Ainda assim, é bem legal
Um exemplo típico é a Route Optimization API, que também foi exposta dessa forma pela equipe de pesquisa operacional corporativa e, depois, com o input de alguns clientes alfa, a solução Fleet Engine foi construída por cima dela. Enquanto uma API de pesquisa operacional não for exposta via Google Cloud, sem SLA nem garantias de confiabilidade, acho melhor não usá-la fora de fins acadêmicos. Meus dois centavos
https://developers.google.com/maps/documentation/transportat...
[1]: https://killedbygoogle.com/
Se demurrage não for considerado, não sei se realmente vale a pena tentar
https://developers.google.com/optimization/service/reference...
O podcast Omega Tau fez um episódio[0] muito bom sobre transporte marítimo de contêineres, e também aborda otimização de posicionamento de contêineres e planejamento de rotas. Recomendo muito
[0]: https://omegataupodcast.net/146-container-shipping/
A expressão “ao contrário dos aviões, cargueiros operam quase continuamente” dá um pouco para questionar
Cargueiros fazem bastante manutenção durante a navegação, mas, fora isso, acho que a diferença é bem menor. Nos portos, eles descarregam e carregam ao longo de vários dias enquanto fazem a rotação, e também podem ficar esperando por algumas horas ou dias por um berço. Olhando o caso do Delta A350, tirando as 3 horas de turnaround no aeroporto, ele fica praticamente em movimento 24 horas por dia: https://www.flightradar24.com/data/aircraft/n513dz
Isso me lembrou donos ou gerentes de lugares como restaurantes de bairro dizendo que sofrem para montar a escala de funcionários temporários, e até que é por isso que ganham bem
Fiquei pensando se não daria para resolver com algoritmos
Talvez dê para cobrir a noite em que metade da equipe foi ver Taylor Swift, mas, se você chama pessoas assim, os próximos turnos dessas pessoas também vão precisar ser cobertos por outras, e, quando isso continua, acaba surgindo uma escala totalmente diferente, com pessoas que nunca trabalharam juntas. Dá para corrigir colocando mais restrições, mas só listar tudo isso e definir prioridades já não é simples. Pessoas não são blocos de Lego
Tenho formação em pesquisa operacional, então isso sempre me pareceu estranho. Os problemas parecem simples de modelar e resolver com solvers genéricos, e parecem gerar muito valor mesmo sem técnicas avançadas. O problema é que a pesquisa operacional, de modo geral, é pouco acessível. A maioria dos solvers bem suportados faz você definir o problema em um paradigma matemático, e uma “pessoa comum” se sente sobrecarregada assim que vê aquilo. Existem soluções prontas para problemas comuns de escala, mas, se você não começou usando uma desde o início, cada negócio tem suas próprias variações, o que dificulta uma adoção completa. Ou elas não dão suporte a essa variação, ou não dá para saber como encaixá-la na ferramenta. Mesmo havendo vontade de resolver melhor as escalas, os cursos encontrados geralmente pressupõem bastante conhecimento prévio de programação ou matemática. Acho que deveria ser possível criar um ambiente de modelagem no-code para problemas de escala, que pudesse ser usado por “pessoas comuns” para quem Excel não basta, mas que não conseguem contratar um especialista em pesquisa operacional
Quase todos os grandes sistemas de RH/gestão de força de trabalho têm opções relacionadas. Por exemplo, https://www.workday.com/en-us/products/workforce-management/... e https://www.oracle.com/human-capital-management/workforce-ma... existem, além de muitas empresas especializadas. Mas, como outra pessoa disse, esses sistemas também foram controversos. Alguns são usados de formas que não consideram necessidades humanas normais. Por exemplo, podem alocar turnos consecutivos, mudar escalas com pouco aviso ou deixar de considerar circunstâncias reais, como cuidados com filhos, que um gerente humano poderia levar em conta
Mas o problema é que cada negócio tem restrições diferentes. Coisas como precisar de pelo menos 1 pessoa com primeiros socorros em um turno, Alice e Bob não se darem bem, não poder trabalhar dois sábados seguidos, os turnos mudarem a cada duas semanas, precisar haver pelo menos 12 horas entre turnos etc. Uma ferramenta flexível o bastante para ser usada por muitas organizações provavelmente acabaria ficando complexa demais para usar
Ainda fico curioso sobre o plano de estiva desses navios
Parece ser um problema que precisa ser resolvido de forma aproximada na etapa seguinte ao planejamento de rota de cada contêiner. O plano de estiva vem depois e tem restrições muito mais dependentes da situação do que uma perspectiva em nível de sistema global. Mesmo numa estimativa grosseiramente otimista, um guindaste de cais faz 30 a 50 movimentos por hora; há 2 ou 4 por navio, às vezes até 6; e é preciso descarregar em camadas, como se fosse uma casca. Um Ultra Large Container Vessel tem 14.501 TEU ou mais; um New Panamax, 10.000 a 14.500 TEU; um Post-Panamax, 5.101 a 10.000 TEU; e um Panamax, 3.001 a 5.100 TEU. Se considerarmos 24.000 TEU como 12 mil contêineres de 40 pés, então 4 guindastes × 50 contêineres por hora por guindaste × 24 horas por dia dá algo em torno de 1.200 contêineres por dia.
https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
Além da disponibilidade no porto, o plano de estiva do navio também envolve critérios aceitáveis de peso, equilíbrio, energia elétrica e valor da carga. Como o texto mencionava saída antecipada do porto, fiquei curioso sobre esse overhead e fiz uma conta aproximada
Do ponto de vista de quem realmente atua nessa área, há muitas formas de facilitar o próprio trabalho. O básico é planejar em blocos por tampa de escotilha e tratar contêineres agrupados por destino, tamanho e peso como substituíveis. Depois, antes do início da operação, o plano é enviado do navio para o terminal; como o terminal também sabe a posição dos contêineres no pátio, ele pode fazer otimização e remanejamento. Se você decide ignorar os detalhes de cada contêiner e se concentrar apenas nos grupos, o plano de estiva fica muito mais fácil. Com muito menos trabalho, o resultado é bastante parecido, e o terminal ganha mais flexibilidade para otimizar a operação