Quais et conteneurs vides : deux articles de recherche dans notre planificateur

Un modèle classique de tournées de véhicules vérifie chaque tournée isolément. Chaque tournée a sa propre capacité, ses propres créneaux horaires et son propre chauffeur, et les tournées ne se rencontrent que dans le coût total. C'est ce qui rend le problème soluble en pratique. C'est aussi pourquoi tant de plans optimisés s'effondrent dans la cour.

Deux réalités du fret brisent cette indépendance. Un quai ne peut accueillir qu'un camion à la fois, quelle que soit sa tournée. Un conteneur vide pris par une tournée n'est plus là pour la suivante. Nous avons étudié comment la recherche opérationnelle traite ces deux cas, et intégré ces idées au planificateur qui fait tourner l'optimiseur de Transportial et /vrp/solve.

Quais : Bombelli et Fazi (2022)

A. Bombelli et S. Fazi ont étudié des camions qui collectent du fret aérien chez des transitaires et le livrent à des handlers au sol (ground handlers) dans un aéroport. Un handler ne leur réserve qu'un ou deux quais. Leur article le modélise comme un problème de collecte et livraison avec fenêtres de temps, dans lequel un handler ne peut pas servir plus de camions à la fois qu'il n'a de quais.

Leur heuristique est une recherche adaptative à grand voisinage. Chaque itinéraire reste réalisable isolément, mais le plan dans son ensemble peut surbooker un quai moyennant une pénalité. Après chaque insertion, un résolveur parcourt les conflits de quai par ordre chronologique. Pour chacun, il retarde le camion dont le décalage est le plus faible, ce qui ne coûte rien si ce camion a de la marge.

Leurs conclusions méritent d'être connues de quiconque planifie avec des quais :

• Sans coordination, les camions faisaient la queue jusqu'à environ trois heures, et certains plans devenaient irréalisables.
• La coordination des quais a réduit le temps de parcours de 2 à 19 %.
• Un second quai comptait surtout pour la faisabilité : les deux quais n'étaient utilisés simultanément que moins de 10 % du temps.

Ce que nous avons construit

Notre planificateur tient une chronologie par lieu à capacité limitée : un quai, une rampe, un poste d'amarrage ou une voie de desserte ferroviaire, de la même façon pour tous les modes. Cette chronologie contient les séjours de chaque tournée du plan. Elle contient aussi ce qui est occupé en dehors du plan : les autres trajets déjà présents sur ce lieu et les créneaux de quai déjà réservés.

Lorsque le planificateur calcule les horaires d'une tournée, il interroge la chronologie à chaque arrêt limité. Le service commence dès qu'un quai est libre pendant toute la durée du service, si les créneaux horaires le permettent encore. L'attente compte comme une vraie attente, dans la journée du chauffeur et dans la durée et le coût de la tournée. Chaque arrêt limité ne coûte qu'une consultation : tester une candidate reste donc peu coûteux, et un plan sans limite de quai s'exécute exactement comme avant.

Ici, nous nous sommes volontairement écartés de l'article. Notre algorithme de recherche jongle aussi avec les compteurs des chauffeurs, les remorques, les compartiments et le stock de matériel, et un quai surbooké rendrait chacun de ces horaires incertain. Nous gardons donc chaque plan que la recherche manipule réalisable du point de vue des quais :

• Faire de la place. Lorsqu'une tournée candidate ne peut pas attendre sans manquer son créneau, les tournées qui la gênent passent après elle si elles tiennent encore dans leurs créneaux. C'est le « le camion qui peut se décaler cède la place » de l'article. La candidate paie leur temps supplémentaire, et si aucun décalage ne fonctionne, l'insertion est refusée.
• Le résolveur. Après chaque mouvement accepté, une tournée qui attend obtient le quai en premier lorsque la tournée qui l'occupe pourrait attendre à moindre coût. Il s'agit généralement d'un décalage dans la marge, et l'échange n'est conservé que si la durée cumulée des deux tournées diminue.
• Réservations fixes. Les trajets existants et les créneaux réservés ne bougent jamais.

Si vous préférez autoriser le surbooking, réglez la règle dock_capacity sur avertir. Une tournée peut alors surbooker un quai moyennant un coût par minute, et c'est signalé, comme dans l'article.

Conteneurs vides : Fazi, Choudhary et Dong (2023)

S. Fazi, S.K. Choudhary et J.X. Dong ont étudié des transporteurs de conteneurs opérant depuis un terminal intérieur. Un camion effectue plusieurs rotations par jour, un conteneur à la fois.

• D'où viennent les conteneurs vides. Un export a besoin d'un conteneur vide : issu du stock limité du terminal, d'un import qui vient d'être déchargé (un street-turn) ou d'un dépôt éloigné.
• La contrainte forte. Le stock de conteneurs vides du terminal ne peut jamais passer sous zéro, à aucun moment. Cela lie entre elles les rotations de différents camions.
• Leur solution. Ils le résolvent de manière exacte, par branch-and-price. La contrainte de stock n'est vérifiée qu'aux « instants critiques » : les moments où une rotation sort un conteneur vide, car le stock ne peut manquer qu'au moment où une unité est prise. Un détour par le dépôt est intégré au prix de l'arc au lieu de devenir un arrêt supplémentaire.

Sur des cas réels près de Tilburg et de 's-Hertogenbosch, leurs plans étaient de 25 à 43 % moins chers que ceux établis par les planificateurs, avec moins de rotations. Ils ont aussi testé ce qui se passe lorsque les conditions se resserrent. Moins d'occasions de street-turn ont augmenté les coûts de 2 à 12 % dans les cas réels, et commencer la journée sans conteneurs vides en stock les a augmentés jusqu'à 27 %.

Ce que nous avons construit

Un envoi peut désormais indiquer qu'il a besoin d'une unité à l'enlèvement, qu'il en libère une après sa livraison, ou les deux. Une unité peut être un conteneur vide, une caisse mobile ou une remorque en pool.

Lorsque le planificateur construit une tournée, il cherche une source pour chaque unité nécessaire, dans cet ordre :

1. Une unité libérée plus tôt sur la même tournée, si les deux envois autorisent un street-turn et que le camion peut la transporter entre-temps.
2. Le stock ou le dépôt qui ajoute le moins de distance, desservi sur le chemin de l'enlèvement.

Une unité libérée qui n'est pas réutilisée retourne dans un stock sur le chemin, après la livraison. Comme les arcs vers le dépôt de l'article, ces passages sont intégrés au tronçon en temps, distance et coût, au lieu de devenir des arrêts.

D'une tournée à l'autre, un seul registre tient chaque stock suivi : son niveau de départ, les arrivées et départs connus, et les prises et retours de chaque tournée. Comme dans l'article, il ne vérifie un stock qu'au moment où une unité est prise. Une prise qui ferait passer un stock sous zéro passe à la source suivante, et s'il n'en reste aucune, c'est la règle equipment_stock qui décide. Les trajets déjà existants comptent avec leurs prises et retours en attente.

Nous n'utilisons pas le branch-and-price. Une recherche à grand voisinage démonte des plans et les reconstruit, et retirer une tournée peut priver une autre tournée du conteneur vide sur lequel elle comptait. La recherche facture donc chaque unité manquante comme un envoi laissé de côté, et la passe finale trouve une autre source ou retire tout ce qui manque encore. Le plan que vous obtenez n'envoie jamais deux camions chercher le dernier conteneur vide du parc.

Là où les deux se rencontrent

Le plus intéressant se trouve là où les deux mécanismes se touchent. Lorsque le planificateur recale une tournée pour un quai, le moment où cette tournée prend ou rend un conteneur se déplace avec elle. Si un retour glisse après la prise d'une autre tournée, un stock qui semblait suffisant peut soudain manquer. Dans notre planificateur, une tournée recalée emporte son plan de matériel avec elle, de sorte que le registre de stock reflète toujours les horaires réels de la tournée.

C'est tout l'intérêt de tout réunir dans une seule recherche. Avec des outils séparés, personne ne le remarquerait. L'écran des quais repousserait un camion, le service des conteneurs vides aurait raison sur le stock du matin, et le plan échouerait quand même.

Ce que nous avons laissé de côté

• Les quais séparés de chargement et de déchargement, et les quais réservés à certains types de véhicules. Tous les quais opérationnels d'un site comptent ensemble.
• Les pools de châssis. La source du conteneur est planifiée ; un pool de châssis partagé entre camions ne l'est pas.
• Les types de conteneurs équivalents (groupes de taille et type ISO) et la capacité du parc. Les types doivent correspondre exactement, et les retours ne sont jamais refusés pour cause de parc plein.
• Le stock de matériel et les services ferroviaires ou fluviaux réguliers dans une même requête. Pour l'instant, planifiez les parcours routiers comme des envois.

Lire les articles

• A. Bombelli et S. Fazi (2022). The ground handler dock capacitated pickup and delivery problem with time windows: a collaborative framework for air cargo operations. Transportation Research Part E 159, 102603.
• S. Fazi, S.K. Choudhary et J.X. Dong (2023). The multi-trip container drayage problem with synchronization for efficient empty containers re-usage. European Journal of Operational Research 310(1), 343–359.

Nous nous sommes appuyés sur les travaux publiés. Les auteurs n'y ont pas été associés, et les éventuelles faiblesses de notre adaptation sont les nôtres. Pour tout ce que le planificateur décide d'autre dans la même recherche, lisez Une seule recherche, tout le plan de transport. Pour les champs à utiliser, consultez le guide du VRP multimodal.