Technique d’optimisation mathématique pour les cargos

Optimisation du réseau de transport des cargos : techniques d’optimisation mathématique

Vue d’ensemble

• L’équipe de recherche de Google a annoncé une nouvelle API de Shipping Network Design.
• Cette API aide à résoudre les problèmes de conception de réseau et de planification des cargos.
• Cette solution est plus rapide et plus efficace que les méthodes existantes, permet de doubler les revenus et de transporter davantage de conteneurs avec moins de navires.

Contexte

• Le LSNDSP (problème de conception et de planification de réseau maritime) se compose de trois éléments : la conception du réseau, la planification du réseau et le routage des conteneurs.
• Jusqu’à présent, ces problèmes étaient résolus séparément, mais les traiter simultanément permet d’obtenir de meilleures solutions.

Méthodologie

• Un problème d’optimisation se compose de variables, de contraintes et d’une fonction objectif.
• Google résout ce problème avec deux approches : Double Column Generation et CP-SAT.
• Ces méthodes fournissent des solutions optimales pour les problèmes de petite et moyenne taille, mais ne conviennent pas aux problèmes de grande taille.
• Pour résoudre les problèmes à grande échelle, Google utilise Large Neighborhood Search et Variable Neighborhood Search.
• Ces méthodes réduisent l’espace de recherche et améliorent l’efficacité grâce au traitement parallèle.

Résultats

• Les performances ont été évaluées à l’aide du benchmark LINERLIB.
• La solution de Google permet de transporter davantage de conteneurs avec moins de navires.
• Elle améliore l’efficacité dans chaque scénario et augmente fortement les revenus.

Conclusion

• La technique d’optimisation de Google est la première méthode capable de résoudre des problèmes de conception et de planification de réseaux maritimes à grande échelle.
• Cette recherche devrait contribuer à améliorer l’efficacité de la chaîne d’approvisionnement mondiale.

L’avis de GN⁺

• Contexte technique : le LSNDSP est un problème d’optimisation complexe qui exige de résoudre simultanément la conception du réseau, la gestion des horaires et le routage.
• Importance industrielle : 90 % du commerce mondial dépend du transport maritime, donc la résolution de ce problème a un impact économique majeur.
• Défi technique : des techniques avancées comme le traitement parallèle et la réduction de l’espace de recherche sont nécessaires pour traiter les problèmes de grande taille.
• Produits concurrents : parmi les autres solutions d’optimisation offrant des fonctionnalités similaires figurent IBM CPLEX et Gurobi.
• Points à considérer : l’adoption d’une nouvelle technologie peut entraîner un coût de mise en place initial et une courbe d’apprentissage. Mais à long terme, elle peut considérablement améliorer l’efficacité et la rentabilité.

[GN⁺]

Avis sur Hacker News

• Avis du point de vue du terminal : l’optimisation des terminaux est très complexe, et comme chaque terminal fonctionne différemment, il est difficile de passer à l’échelle.
• Recommandation du livre "The Box" : un livre sur les débuts de l’histoire de la conteneurisation, une lecture intéressante mêlant ingénierie, design, business et histoire.
• Problème d’optimisation des conteneurs : le problème de l’optimisation des conteneurs pour les grandes flottes n’est pas résolu.
• Amélioration par Google OR : Google OR améliore de 10 % à 20 % les solutions existantes.
• Utilisation de l’API : certains se demandent si cela vaut la peine d’essayer dans une situation où les demurrage (frais de surestaries) ne sont pas pris en compte.
• Curiosité sur l’utilisation d’un endpoint API : curiosité quant à l’usage réel des endpoints API fournis par Google.
• Recommandation du podcast Omega Tau : il existe un excellent épisode sur le transport maritime par conteneurs et l’optimisation.
• Exécution dans un conteneur Docker : cela ne fonctionne que lorsqu’il est exécuté dans un conteneur Docker.
• Suggestion d’utiliser un algorithme : idée qu’un algorithme pourrait peut-être résoudre la planification des horaires d’employés à temps partiel.
• Fourniture d’OR-tools en tant que service : il semble qu’OR-tools commence à être proposé comme service. Si une meilleure API était disponible, certains seraient prêts à payer les coûts de calcul sur GCP.
• Question sur le plan de chargement : le plan de chargement est un problème à résoudre après la planification de l’itinéraire. Un calcul approximatif de la vitesse de travail des grues et des opérations de chargement/déchargement est présenté.
• Complexité du plan de chargement : le plan de chargement inclut des critères comme le poids, l’équilibre, l’alimentation électrique et l’acceptabilité de la valeur. Cette complexité conduit à tenter des calculs simples.