Apresentamos uma solução até então desconhecida para o problema de planejamento e projeto de rede de transporte marítimo, que faz parte de nossa nova API de projeto de rede de transporte marítimo.
Olhe a sua volta. Provavelmente, algo em sua linha de visão navegou em um navio de carga. 90% das mercadorias mundiais viajam através do oceano, muitas vezes em navios de carga de escala gigantesca: 400 metros de comprimento, pesando 250.000 toneladas, contendo 12.000 contentores de mercadorias no valor colectivo de mil milhões de dólares. Ao contrário dos aviões, comboios e camiões, os navios de carga estão em operação quase constante, seguindo rotas cíclicas através dos oceanos.
Um navio porta-contêineres “pós-Panamax”, assim chamado porque é grande demais para caber no Canal do Panamá. Fonte da imagem: Wikipedia , licenciada sob CC BY-SA 4.0 .
Mas quais são as melhores e mais eficientes rotas para esses navios? Para um cientista da computação, este é um problema de teoria dos grafos; para um analista de negócios, um problema de cadeia de suprimentos. Se forem mal executados, os contentores permanecem nos portos, os navios ficam ociosos no mar, incapazes de atracar e, em última análise, os produtos tornam-se mais caros à medida que o fluxo de itens físicos se torna mais lento e imprevisível. Toda empresa de transporte de contêineres precisa resolver esses desafios, mas normalmente eles são resolvidos separadamente. Combiná-los multiplica a complexidade e, até onde sabemos, é um problema que nunca foi resolvido na escala exigida pelas maiores operações de contêineres (500 navios e 1.500 portos).
A equipe de pesquisa operacional do Google tem o orgulho de anunciar a API Shipping Network Design , que implementa uma nova solução para esse problema. Nossa abordagem é melhor dimensionada, permitindo soluções para problemas da cadeia de suprimentos em escala mundial, ao mesmo tempo em que é mais rápida do que qualquer tentativa anterior conhecida. É capaz de duplicar o lucro de um transportador de contentores, entregar 13% mais contentores e fazê-lo com 15% menos navios. Continue lendo para ver como fizemos isso.
Fundo
Existem três componentes no Problema de Projeto e Programação de Rede de Transporte Marítimo (LSNDSP). O design da rede determina a ordem em que os navios visitam os portos, a programação da rede determina os horários em que chegam e partem, e o roteamento dos contêineres escolhe a jornada que os contêineres fazem da origem ao destino. Toda empresa de transporte de contêineres precisa resolver todos os três desafios, mas eles normalmente são resolvidos sequencialmente. Resolver todos eles simultaneamente é mais difícil, mas também é mais provável que se descubram soluções melhores.
As soluções para a concepção de redes criam linhas de serviço seguidas por um pequeno conjunto de navios: por exemplo, navegando entre o leste da Ásia, através do canal de Suez, e para o sul da Europa. Essas linhas de serviço são publicadas com datas, para que os embarcadores saibam quando e onde deixar seus contêineres prontos no porto.
Parte de um projeto de rede para um hipotético transportador marítimo, mostrando como os navios podem circular entre nove portos.
Os navios porta-contêineres não podem atracar nos portos quando quiserem; eles têm slots de atracação pré-combinados. Ao se aproximarem de um porto, eles permanecem em uma área de fundeio , um local offshore onde podem lançar âncora até que seu cais fique livre. Quando um porto está congestionado, os navios podem acabar permanecendo no fundeadouro por horas ou dias. E assim a programação precisa da rede dos navios torna-se importante: não apenas em que dia atracar, mas em que hora, e se deve aumentar a velocidade para chegar a uma determinada hora (ou, inversamente, diminuir a velocidade para poupar combustível).
Assim que o navio atraca no porto, os guindastes descarregam os contêineres em pilhas e depois carregam outros contêineres nos navios para a próxima etapa da viagem. Se o navio se atrasar, por vezes irá parar e sair do porto antes de todos os contentores pretendidos terem sido carregados, dependendo de navios posteriores para recolher os contentores. Quando um contêiner passa algum tempo em um porto intermediário no trajeto da origem ao destino, isso é chamado de transbordo . Isto multiplica ainda mais o número de soluções possíveis para o LSNDSP. O transbordo é apenas uma das diversas restrições que entram em jogo na geração de rotas de contêineres.
Navio porta-contêineres atracado no porto, embaixo dos guindastes que carregam e descarregam contêineres. A imagem é de domínio público .
Resolver esses três problemas – projeto de rede, agendamento de rede e roteamento de contêineres – em escala envolve um espaço de pesquisa incrivelmente grande.
Métodos
Todo problema de otimização tem três componentes: variáveis (por exemplo, navios e portos), restrições sobre essas variáveis (por exemplo, um navio só pode acomodar tantos contêineres a bordo) e uma função objetivo a ser minimizada ou maximizada (por exemplo, maximizar o número de contêineres). contêineres enviados). As variáveis e restrições são frequentemente representadas como uma matriz na qual as colunas são as variáveis e as linhas são as restrições.
Uma técnica comum para decompor problemas tão grandes é a geração de colunas , na qual apenas um subconjunto das variáveis é considerado inicialmente, e depois novas variáveis — isto é, novas colunas — são geradas para aproximar-se mais do problema original. Para ajudar a gerenciar isso, desenvolvemos uma biblioteca de software que analisa o problema e prevê quais colunas são melhores para gerar. Esta biblioteca será de código aberto via MathOpt , nossa estrutura de programação matemática.
Com isso em mãos, definimos duas abordagens básicas para resolver o problema:
- Geração de Coluna Dupla
Consideramos o projeto de rede e o roteamento de contêineres como dois problemas acoplados, cada um consistindo em um problema de seleção primária (escolher a melhor opção) e um problema de geração subsidiária (identificar opções razoáveis). Aplicamos um algoritmo de caminho mais curto a cada par de problemas para gerar opções razoáveis, seguido por um programa linear (usando nosso solucionador de programação linear, Glop ) para escolher as melhores opções para cada um. Aplicamos a técnica de geração de colunas a ambos ao mesmo tempo, usando resultados intermediários em cada problema para influenciar o progresso do outro. Essa abordagem de geração de coluna dupla nos permitiu encontrar soluções comprovadamente ótimas, mas só foi bem dimensionada para problemas de tamanho moderado. - CP-SAT
Tentamos então uma implementação baseada em programação de restrições, usando nosso solucionador de programação de restrições CP-SAT . Isso também funcionou bem em redes de médio porte, mas não atendeu ao problema de transporte marítimo mundial.
Estas duas abordagens permitiram-nos encontrar soluções comprovadamente óptimas, mas apenas se adaptaram bem a problemas de pequena e média dimensão. Para melhorar sua escalabilidade, aplicamos uma estratégia heurística usando duas variantes de busca local nas quais examinamos vizinhanças em torno de soluções existentes para encontrar oportunidades de melhorias.
- Pesquisa em grandes bairros
Corrigimos partes da solução (por exemplo, “este navio visitará Los Angeles em terças-feiras alternadas”) antes de aplicar qualquer um dos métodos descritos acima. Isso melhora a escalabilidade, reduzindo o espaço de pesquisa. - Pesquisa variável de bairros
Exploramos bairros tanto na rede quanto na programação. Paralelizamos a exploração e a distribuímos por várias máquinas para avaliar muitas vizinhanças simultaneamente. Isso também melhora a escalabilidade, limitando o espaço de pesquisa, ao mesmo tempo que nos permite incorporar conhecimento da Pesquisa Operacional e da indústria naval.
Com ambas as abordagens, fizemos uso do incrementalismo: bloquear partes promissoras de uma solução para que pudéssemos partir de uma solução conhecidamente boa para torná-la melhor.
Por fim, também levamos em consideração os tempos de trânsito. As tentativas anteriores de resolver este problema não levaram em consideração os tempos de trânsito, pois tornam o problema muito mais difícil de resolver. Descobrimos que a inclusão de tempos de trânsito melhorou significativamente a qualidade da solução.
Uma pequena modificação na rede descoberta com a pesquisa de bairro pode afetar os lucros do transporte marítimo. Neste exemplo, o modelo pode sugerir uma nova conexão que possibilite o envio de contêineres entre portos que não estavam conectados anteriormente.
Resultados
Para quantificar o desempenho de nossas soluções, usamos o LINERLIB , uma referência do setor para problemas de projeto de rede de transporte marítimo, incluindo cenários de transporte de contêineres: frotas, portos e demandas de contêineres. Testamos nossa solução em três cenários: WorldSmall, EuropeAsia e o bestial WorldLarge, o último dos quais contém 500 navios, 200 portos e quase 140.000 contêineres.
Abaixo está a comparação de cinco cenários LINERLIB.
Uma comparação de nossas soluções com as soluções anteriormente mais conhecidas. O tamanho da bolha corresponde ao número de portas, indicando a escala do problema. Nossas soluções reduzem consistentemente o número de navios necessários para um determinado volume de contêineres.
Em qualquer cenário de otimização, é importante especificar o objetivo. Quer maximizar o número de contêineres enviados? Fácil: lançar mais navios para resolver o problema, aumentando os custos operacionais. Quer minimizar o número de embarcações utilizadas? Novamente, é fácil: fazer com que um navio entregue todos os contêineres do mundo, com prazos de entrega ridiculamente longos.
O benchmark LINERLIB equilibra isso calculando o lucro estimado : a receita de entregas dentro do prazo menos os custos de navegação e manuseio de contêineres no porto. A próxima figura mostra como o lucro da nossa solução se compara às tentativas anteriores.
Melhorias no lucro semanal de nossas soluções em comparação com as melhores soluções disponíveis anteriormente. Os lucros baseiam-se nos pressupostos económicos do conjunto de dados LINERLIB.
Em comparação com a linha de base, o nosso método foi capaz de encaminhar mais contentores com menos navios. Para cada um dos cenários LINERLIB, as nossas soluções melhoraram a eficiência global, aumentando o rendimento (35% mais contentores para WorldSmall, 14% para EuropeAsia, 35% para Pacífico, 32% para Mediterrâneo) ao mesmo tempo que utilizavam menos navios (7%, 15% , 4% e 23% respectivamente). Com base nos pressupostos económicos do LINERLIB, as nossas soluções também melhoraram consideravelmente as margens de lucro projetadas.
Conclusão
Como mostram os nossos resultados, a seleção cuidadosa de técnicas avançadas de otimização pode ter um efeito notável na eficiência das redes de transporte marítimo. Acreditamos que nosso método é o primeiro capaz de resolver o problema de projeto e escalonamento de redes na escala WorldLarge. Você pode examinar nossos resultados com mais detalhes em nossa página de benchmark . Esperamos que este trabalho inspire pesquisas adicionais neste domínio com o objetivo de construir cadeias de abastecimento globais mais eficientes e suaves.
A API Shipping Network Design faz parte de um conjunto de APIs de pesquisa operacional que adicionaremos no futuro, à medida que procuramos outros setores para otimizar.
