Technologie d’optimisation mathématique pour les cargos

 (research.google)
1 points par GN⁺ 2024-06-07 | 1 commentaires | Partager sur WhatsApp
  • L’équipe Operations Research de Google Research a dévoilé la Shipping Network Design API, qui optimise conjointement la conception du réseau, le planning et le routage des conteneurs pour les lignes régulières de porte-conteneurs
  • Ce problème exige de déterminer simultanément l’ordre des escales des navires, les heures d’arrivée et de départ, ainsi que les trajets origine-destination des conteneurs, ce qui le rend complexe jusqu’à l’échelle de 500 navires et 200 ports sur le cas WorldLarge
  • Une première approche reposant sur la génération de colonnes double et CP-SAT a permis de trouver des solutions optimales prouvables sur des problèmes de petite et moyenne taille, mais les grands problèmes ont nécessité des heuristiques combinant large neighborhood search et variable neighborhood search
  • Sur le benchmark LINERLIB, le débit de conteneurs a augmenté de 35 %, 14 %, 35 % et 32 % respectivement pour WorldSmall, EuropeAsia, Pacific et Mediterranean, tandis que le nombre de navires utilisés a diminué de 7 %, 15 %, 4 % et 23 %
  • Google présente cette méthode comme la première capable de résoudre des problèmes de conception de réseau et de planification à l’échelle de WorldLarge, et proposera la Shipping Network Design API dans le futur au sein des Operations Research APIs

Le problème de l’optimisation simultanée d’un réseau de transport maritime par conteneurs

  • 90 % des marchandises mondiales transitent par la mer, et un grand cargo peut mesurer 0,25 mile de long, peser 250 000 tonnes, transporter 12 000 conteneurs et embarquer pour 1 milliard de dollars de marchandises au total
  • Contrairement aux avions, trains et camions, les cargos opèrent presque en continu et suivent des routes circulaires en mer
  • Des itinéraires et plannings inefficaces augmentent le temps de séjour des conteneurs dans les ports, l’attente des navires en mer et les retards dans les flux logistiques, avec un impact sur le prix des produits
  • La Shipping Network Design API de Google implémente une nouvelle solution à ce problème
    • Elle est plus rapide et passe mieux à l’échelle que les tentatives connues jusque-là
    • Elle peut doubler les profits des compagnies de transport par conteneurs, acheminer 13 % de conteneurs en plus et fonctionner avec 15 % de navires en moins

Les trois décisions que le LSNDSP doit résoudre ensemble

  • Le Liner Shipping Network Design and Scheduling Problem, ou LSNDSP, traite simultanément trois décisions
    • Conception du réseau : déterminer dans quel ordre les navires visitent les ports
    • Planification du réseau : définir quand les navires arrivent et repartent
    • Routage des conteneurs : choisir quel trajet les conteneurs suivront entre leur origine et leur destination
  • Les compagnies maritimes de conteneurs doivent résoudre ces trois problèmes, mais les traitent généralement de façon séquentielle
  • Les résoudre en même temps augmente la difficulté, mais accroît aussi les chances de trouver une meilleure solution
  • Le résultat de la conception du réseau se traduit par un petit nombre de lignes de service suivies par les navires
    • Par exemple, un trajet reliant l’Asie de l’Est au sud de l’Europe via le canal de Suez
    • Les lignes de service sont publiées avec des dates, afin que les chargeurs sachent quand et où préparer leurs conteneurs

Les contraintes créées par les postes à quai, le transbordement et les retards

  • Les porte-conteneurs ne peuvent pas accoster quand ils le souhaitent et doivent utiliser des créneaux d’accostage définis à l’avance
  • Après son arrivée à proximité du port, un navire peut jeter l’ancre dans une zone de mouillage et attendre jusqu’au moment où il peut accoster
    • Si le port est congestionné, il peut y rester plusieurs heures ou plusieurs jours
  • Un planning de réseau précis ne se limite pas au jour d’accostage, mais inclut aussi l’heure exacte
    • Il est possible d’accélérer pour viser une heure précise
    • Ou au contraire de ralentir pour économiser du carburant
  • Une fois au quai, des grues déchargent les conteneurs et rechargent ceux destinés à l’étape suivante
  • Si le planning prend du retard, un cut-and-run peut se produire : le navire quitte le port avant d’avoir embarqué tous les conteneurs prévus
    • Les conteneurs restants seront alors pris en charge par un navire ultérieur
  • Lorsqu’un conteneur passe du temps dans un port intermédiaire avant d’atteindre sa destination, on parle de transbordement
    • Le transbordement augmente fortement le nombre de solutions possibles pour le LSNDSP
    • Ce n’est qu’une des nombreuses contraintes qui influencent la génération des itinéraires de conteneurs

Méthodes d’optimisation : de la génération de colonnes à la recherche de voisinage

  • Tout problème d’optimisation se compose de variables, de contraintes sur ces variables et d’une fonction objectif à minimiser ou maximiser
    • Exemple : les navires et les ports sont des variables
    • Exemple : le nombre de conteneurs qu’un navire peut embarquer est une contrainte
    • Exemple : maximiser le nombre de conteneurs transportés est une fonction objectif
  • Les variables et contraintes sont généralement représentées sous forme de matrice, les colonnes correspondant aux variables et les lignes aux contraintes
  • Une technique courante pour décomposer les grands problèmes est la génération de colonnes
    • Au départ, seule une partie des variables est prise en compte
    • De nouvelles variables, donc de nouvelles colonnes, sont ensuite générées pour mieux approximer le problème d’origine
  • Google a développé une bibliothèque logicielle qui analyse le problème pour prédire quelles colonnes il est pertinent de générer
    • Cette bibliothèque sera publiée en open source via MathOpt, un framework de programmation mathématique

Les limites de deux approches de base

  • La génération de colonnes double considère la conception du réseau et le routage des conteneurs comme deux problèmes couplés
    • Chaque problème se compose d’un problème maître qui choisit les meilleures options et d’un sous-problème de génération qui recherche des options raisonnables
    • Un algorithme de plus court chemin est appliqué à chaque paire de problèmes pour générer ces options raisonnables
    • Le solveur de programmation linéaire Glop est ensuite utilisé pour choisir les meilleures options de chaque problème
    • La génération de colonnes est appliquée simultanément aux deux problèmes, de sorte que les résultats intermédiaires de l’un influencent la progression de l’autre
    • Cette approche a permis de trouver des solutions optimales prouvables, mais elle ne passait bien à l’échelle que jusqu’aux problèmes de taille intermédiaire
  • Une implémentation basée sur CP-SAT a également été testée
    • Elle utilise le solveur de programmation par contraintes CP-SAT de Google
    • Elle fonctionnait bien jusqu’aux réseaux de taille intermédiaire, mais ne passait pas à l’échelle des problèmes mondiaux de transport maritime
  • Les deux approches ont trouvé des solutions optimales prouvables sur des problèmes petits et moyens, mais manquaient de scalabilité sur les grands cas

Des heuristiques pour passer à grande échelle

  • Pour améliorer la scalabilité, deux variantes de recherche locale ont été appliquées en explorant le voisinage d’une solution existante afin d’y détecter des opportunités d’amélioration
  • La large neighborhood search fixe une partie de la solution puis applique les méthodes précédentes
    • Par exemple, on peut fixer une contrainte comme « ce navire visite Los Angeles un mardi sur deux »
    • Cela réduit l’espace de recherche et améliore la scalabilité
  • La variable neighborhood search explore des voisinages à la fois du réseau et du planning
    • La recherche est parallélisée et distribuée sur plusieurs machines pour évaluer de nombreux voisinages simultanément
    • Cela permet de limiter l’espace de recherche tout en intégrant les connaissances de l’Operations Research et du secteur maritime
  • Les deux approches utilisent une méthode incrémentale qui verrouille certaines parties de solutions prometteuses et part d’une solution déjà bonne pour l’améliorer progressivement
  • Les tentatives précédentes n’intégraient pas les temps de transport, car cela rendait le problème bien plus difficile, mais Google a constaté que leur prise en compte améliore nettement la qualité des solutions

Résultats sur le benchmark LINERLIB

  • L’évaluation des performances s’appuie sur LINERLIB, un benchmark industriel pour les problèmes de conception de réseaux maritimes
    • Le benchmark inclut la flotte, les ports et la demande en conteneurs de différents scénarios de transport maritime
  • Les scénarios testés incluent WorldSmall, EuropeAsia et WorldLarge
    • WorldLarge comprend 500 navires, 200 ports et environ 140 000 conteneurs
  • L’objectif de l’optimisation n’est pas simplement de maximiser le nombre de conteneurs ni de minimiser le nombre de navires
    • Maximiser uniquement le nombre de conteneurs peut conduire à mobiliser davantage de navires et à augmenter les coûts d’exploitation
    • Minimiser uniquement le nombre de navires peut aboutir à des délais de livraison irréalistes, comme si un seul navire transportait tous les conteneurs
  • LINERLIB équilibre ces critères à l’aide d’un profit estimé, calculé en soustrayant du revenu des livraisons à l’heure les coûts de navigation et les coûts de manutention portuaire des conteneurs
  • Par rapport au baseline, la méthode de Google route davantage de conteneurs avec moins de navires
    • WorldSmall : +35 % de débit de conteneurs, -7 % de navires
    • EuropeAsia : +14 % de débit de conteneurs, -15 % de navires
    • Pacific : +35 % de débit de conteneurs, -4 % de navires
    • Mediterranean : +32 % de débit de conteneurs, -23 % de navires
  • D’après les hypothèses économiques de LINERLIB, le taux de profit attendu s’améliore aussi nettement

API et publications à venir

À lire aussi

1 commentaires

 
GN⁺ 2024-06-07
Commentaires Hacker News

  • Je travaille du côté des terminaux dans ce secteur ; c’est intéressant, mais ça paraît très académique
    Je me demande si cela a vraiment été conçu en collaboration avec des compagnies maritimes. Côté terminaux, nous sommes déjà très en profondeur dans l’optimisation des conteneurs, et c’est quasiment un cauchemar. Même entre terminaux appartenant à la même entreprise, les modes d’exploitation varient fortement, et même la terminologie diffère souvent en interne. Même si l’on optimise pour un terminal, il faut refaire 80 % du travail pour le suivant, ce qui rend n’importe quelle solution très difficile à étendre

    • Quand on regarde les problèmes d’optimisation industrielle, on a toujours l’impression qu’il y a énormément d’argent laissé sur la table, mais en réalité les contraintes centrées sur les personnes, non documentées, compliquent énormément les choses
      Par exemple, des ingénieurs allemands se sont opposés au verrouillage de certaines fonctions sur des véhicules avant production, parce que cela les empêchait de les utiliser pour leurs loisirs. Dans le secteur médical, les heures supplémentaires coûtaient des milliards, donc améliorer les plannings semblait facile, mais il y avait beaucoup de contraintes syndicales et l’offre de recrutement était insuffisante. Je me demande à quel point la solution de Google est réaliste. Prend-elle aussi en compte des contraintes comme les missiles houthis ? D’après mon expérience, une solution qui s’ajuste facilement aux changements imprévus a souvent plus de valeur qu’un optimum prouvable
    • Les données de benchmark utilisées pour l’évaluation des performances viennent de Maersk : https://github.com/blof/LINERLIB
    • Je n’ai pas travaillé dans le transport maritime, mais j’ai passé 15 ans dans l’industrie manufacturière, surtout en ingénierie de test et automatisation, ainsi qu’en gestion d’entrepôt/de matériaux et en transport/logistique. Mon master portait sur la recherche opérationnelle appliquée à l’industrie manufacturière
      Je suis d’accord pour dire que l’optimisation objective est généralement assez académique. Il y a toujours des raisons pour lesquelles il est difficile, voire impossible, de suivre tel quel la version la plus efficace d’un processus standardisé. Parfois ce sont des raisons « stupides » liées aux personnes, et souvent ce sont des raisons rationnelles qui reflètent des externalités comme la météo, les arrêts de production, les ruptures de chaîne d’approvisionnement, ou les irrégularités des signaux de demande et des prévisions liées à la saisonnalité. Malgré tout, je pense qu’il vaut presque toujours mieux partir du processus le plus efficace et y ajouter la gestion des exceptions, plutôt que de construire un processus standard à partir des exceptions connues. Si l’on laisse les exceptions devenir la règle, on fonctionne toujours avec moins d’efficacité que l’optimum
    • Je travaille aussi avec des terminaux et des entreprises de transport terrestre. Beaucoup de gens veulent résoudre des problèmes académiques qui « en jettent », comme l’optimisation des plans de chargement, l’affectation des postes à quai ou la répartition des grues, mais très peu de choses sont réellement mises en production
      Ce secteur est difficile, et le paysage politique l’est encore plus parce que les syndicats de dockers y sont historiquement puissants. Les problèmes que l’on peut découper proprement et nommer sont en réalité entremêlés, et si l’on s’attend à ce qu’un algorithme les résolve « magiquement » pour l’utilisateur, on échoue presque toujours. Ce secteur avale facilement les cadors du logiciel qui débarquent en se disant : « il suffit de lancer un problème du voyageur de commerce / un solveur de contraintes / l’approche de mon choix, non ? ». Il faut clairement des gens intelligents, mais il faut commencer avec humilité et parler d’abord aux utilisateurs réels. Je ne vois pas de coordonnées dans le profil ; si vous souhaitez échanger avec une autre entreprise du secteur, envoyez-moi un e-mail. Nous faisons des choses intéressantes, notamment sur le segment des terminaux de moins d’un million d’EVP par an, avec une forte part de transport intermodal
    • Pour ceux qui ne sont pas du domaine, pourrais-tu expliquer plus en détail ce que tu fais actuellement ?

  • Je suis en train de lire The Box, qui retrace les débuts de la conteneurisation, et c’est vraiment passionnant
    Je le recommande vivement à ceux qui cherchent une lecture agréable mêlant ingénierie, conception, business et histoire. Ça rend même dérisoires les petits problèmes de code auxquels je suis confronté

    • Excellent livre, et je suis d’accord avec la recommandation
      Je sais que cela va probablement susciter beaucoup d’objections, mais je le pense sincèrement : l’impact du conteneur maritime de 20 pieds sur le monde a été plus important que celui que les grands modèles de langage auront probablement un jour. Lisez d’abord ce livre, puis dites-moi pourquoi j’ai tort. Bien sûr, je n’ai pas tort
    • Article Wikipédia de “The Box” : https://en.m.wikipedia.org/wiki/The_Box_(Levinson_book)
    • Chez Flexport, ils donnaient ce livre aux nouveaux arrivants. En tout cas, c’était le cas il y a quelques années

  • Il semble que, pour les très grandes flottes, l’optimisation des conteneurs soit encore un problème non résolu. Je ne le savais pas
    Si la recherche opérationnelle de Google améliore le taux d’utilisation de 10 à 20 % par rapport aux solutions existantes, c’est remarquable

  • Je suis très curieux de savoir si quelqu’un utilise réellement cet endpoint d’API public : https://developers.google.com/optimization/service/shipping/...
    Cela dit, c’est plutôt cool

    • D’après mon expérience professionnelle chez Google Cloud entre 2015 et 2023, ce type d’API de recherche opérationnelle est 1) académique, et 2) surtout utilisé commercialement par les architectes de solutions et ingénieurs Google Cloud pour construire des solutions métier personnalisées pour des clients, fonctionnant sur GCP
      Un exemple représentatif est la Route Optimization API, également publiée par une équipe de recherche opérationnelle d’entreprise ; ensuite, avec les retours de quelques clients alpha, la solution Fleet Engine a été construite par-dessus. Tant qu’une API de recherche opérationnelle n’est pas exposée via Google Cloud, elle n’offre ni SLA ni garanties de fiabilité, donc je pense qu’il vaut mieux ne pas l’utiliser hors cadre académique. Juste mon avis
      https://developers.google.com/maps/documentation/transportat...
    • Ne pas l’essayer pourrait même être irresponsable. Je me demande si cela couvre toute la forme des problèmes et contraintes auxquels les planificateurs sont confrontés. Flexport est une entreprise basée à San Francisco, active dans ce domaine, avec 3,3 milliards de dollars de chiffre d’affaires
    • Le cimetière de Google[1] grossit rapidement, donc je me méfie des nouvelles annonces de Google. Ce genre d’API risque de poser de gros problèmes, surtout lorsqu’il faudra la remplacer à l’avenir
      [1]: https://killedbygoogle.com/

  • Si les surestaries ne sont pas prises en compte, je ne sais pas vraiment si cela vaut la peine d’être tenté
    https://developers.google.com/optimization/service/reference...

  • Le podcast Omega Tau a publié un très bon épisode[0] sur le transport de conteneurs, qui couvre aussi l’optimisation du placement des conteneurs et la planification des itinéraires. Je le recommande vivement
    [0]: https://omegataupodcast.net/146-container-shipping/

  • La formule « contrairement aux avions, les cargos sont presque toujours en exploitation » mérite peut-être d’être nuancée
    Les cargos font certes beaucoup de maintenance en mer, mais à part cela, la différence me semble bien moindre. Au port, ils passent plusieurs jours à décharger et charger avant de repartir, et peuvent aussi attendre des heures ou des jours qu’un poste à quai se libère. Si l’on regarde l’exemple de ce Delta A350, en retirant les 3 heures de rotation à l’aéroport, il est en fait en mouvement quasiment 24 h/24 : https://www.flightradar24.com/data/aircraft/n513dz

    • On peut aussi considérer qu’il est « en exploitation » pendant le déchargement

  • Cela me fait penser aux propriétaires ou managers de petits restaurants de quartier qui disent que planifier les horaires des employés à temps partiel est un casse-tête, au point de dire que c’est pour cela qu’ils sont bien payés
    Je me disais que ça devrait pouvoir se résoudre avec un algorithme

    • Beaucoup de gens n’aiment pas que leurs horaires changent fortement
      On peut peut-être combler la soirée où la moitié du personnel va voir Taylor Swift, mais si l’on fait venir des gens pour ça, il faudra ensuite que quelqu’un couvre leur prochain service, et ainsi de suite, jusqu’à obtenir un planning complètement différent avec des personnes qui n’ont jamais travaillé ensemble. On peut corriger cela en ajoutant davantage de contraintes, mais rien que les énoncer toutes et les prioriser n’est pas simple. Les gens ne sont pas des briques Lego
    • C’est exactement le problème que j’aimerais résoudre. J’entends la même chose de presque toutes les personnes qui font des plannings
      Ayant une formation en recherche opérationnelle, cela m’a toujours semblé étrange. Les problèmes paraissent assez simples à modéliser et à résoudre avec des solveurs génériques, et la valeur créée semble importante même sans techniques avancées. Le problème, c’est que la recherche opérationnelle est globalement peu accessible. La plupart des solveurs bien pris en charge obligent à définir le problème selon un paradigme mathématique, ce qui submerge immédiatement une « personne ordinaire ». Il existe aussi des solutions clés en main pour les problèmes courants de planning, mais si elles n’ont pas été utilisées dès le départ, chaque entreprise a ses propres variantes, ce qui rend l’adoption complète difficile. Soit ces variantes ne sont pas prises en charge, soit on ne sait pas comment les faire entrer dans l’outil. Même quand on a la volonté d’améliorer les plannings, les cours que l’on trouve supposent généralement des prérequis assez importants en programmation ou en maths. Je pense qu’il devrait être possible de créer, pour les problèmes de planning, un environnement de modélisation no-code utilisable par les « personnes ordinaires » pour lesquelles Excel ne suffit plus, mais qui ne peuvent pas embaucher un expert en recherche opérationnelle
    • C’est un problème vraiment important, et beaucoup de logiciels s’y attaquent déjà
      Presque tous les grands systèmes RH / de gestion des effectifs proposent des options liées à cela. Par exemple https://www.workday.com/en-us/products/workforce-management/... et https://www.oracle.com/human-capital-management/workforce-ma... ; il existe aussi de nombreux fournisseurs spécialisés. Cela dit, comme quelqu’un d’autre l’a mentionné, ces systèmes ont aussi suscité des controverses. Certains sont utilisés d’une manière qui ne tient pas compte de besoins humains normaux. Par exemple, ils peuvent enchaîner les services, modifier les horaires avec un préavis très court, ou ne pas prendre en compte des réalités comme la garde d’enfants, qu’un manager humain pourrait intégrer
    • Le même groupe de recherche opérationnelle propose un exemple de planning pour restaurant : https://developers.google.com/optimization/service/schedulin...
    • Ayant un peu d’expérience en optimisation combinatoire, j’ai déjà envisagé d’essayer des logiciels dans ce domaine, ou pour la planification des emplois du temps scolaires
      Mais le problème, c’est que chaque établissement a des contraintes différentes. Par exemple : il faut au moins une personne formée aux premiers secours par service ; Alice et Bob ne s’entendent pas ; on ne peut pas travailler deux samedis de suite ; les équipes changent toutes les deux semaines ; il doit y avoir au moins 12 heures entre deux services ; etc. Un outil assez flexible pour être utilisé par un grand nombre d’organisations finirait probablement par être trop complexe pour être facile à utiliser

  • Je me demande encore comment fonctionne le plan de chargement de ce type de navire
    J’imagine que c’est un problème à résoudre de façon approximative à l’étape qui suit la planification de l’itinéraire de chaque conteneur. Le plan de chargement vient plus tard et comporte des contraintes beaucoup plus dépendantes du contexte qu’une vision au niveau du système global. Même avec une estimation grossièrement optimiste, une grue de quai effectue 30 à 50 mouvements par heure ; il y en a 2 ou 4 par navire, parfois jusqu’à 6, et il faut décharger par couches, comme une coquille. Un Ultra Large Container Vessel fait 14 501 EVP ou plus, un New Panamax 10 000 à 14 500 EVP, un Post-Panamax 5 101 à 10 000 EVP, et un Panamax 3 001 à 5 100 EVP. Si l’on considère 24 000 EVP comme 12 000 conteneurs de 40 pieds, 4 grues × 50 conteneurs par heure et par grue × 24 heures par jour = environ 1 200 conteneurs par jour.
    https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
    Le plan de chargement d’un navire doit aussi respecter, au-delà de la disponibilité au port, des critères de poids, d’équilibre, d’alimentation électrique et de valeur admissible de la cargaison. L’article mentionnait un départ anticipé du port, ce qui m’a rendu curieux de ce type de surcoût, et j’ai fait un calcul approximatif.

    • Un chercheur de la Technical University of Denmark (DTU) a mis en ligne une conférence qui constitue une assez bonne introduction au problème de chargement : https://www.youtube.com/watch?v=9ltz4G-lPdg
      Du point de vue de quelqu’un qui travaille réellement dans ce domaine, il existe beaucoup de façons de se simplifier la vie. Planifier par blocs selon les panneaux de cale, et regrouper les conteneurs par destination, taille et poids pour les traiter comme interchangeables, c’est la base. Ensuite, si le navire envoie le plan au terminal avant le début des opérations, le terminal, qui connaît aussi l’emplacement des conteneurs dans le parc, peut optimiser et effectuer des remaniements. Si l’on décide d’ignorer les détails de chaque conteneur pour se concentrer uniquement sur les groupes, le plan de chargement devient beaucoup plus simple. Avec beaucoup moins de travail, le résultat est très similaire, et le terminal dispose aussi de davantage de flexibilité pour optimiser ses opérations.