Le problème de la planification portuaire

La manutention des conteneurs

Un terminal à conteneurs est une infrastructure où des conteneurs sont déchargés et chargés de et sur des véhicules de transport et où ils peuvent être stockés entretemps. Un terminal est équipé pour la prise en charge de certains modes de transport. Différents types de terminaux existent. Un terminal maritime multimodal réalise des transferts de conteneurs entre des navires aux longs cours, des navires caboteurs, des barges fluviales, des trains et des camions.

En général, il y a une période de stockage comptée en jours entre le déchargement d’un conteneur et son chargement sur le véhicule de transport qui l’acheminera à sa prochaine destination.

La manutention des conteneurs sur les véhicules nécessite des équipements dépendant du mode de transport. Un conteneur de 40 pieds fait un peu plus de 12 mètres de long et peut peser plus de 25 tonnes. Pour les bateaux, cette manutention s’effectue avec des grues de quai montées sur rails . Pour les trains, les conteneurs sont en général déchargés et chargés par des portiques, montés sur rails ou sur roues . Pour les camions, la manutention des conteneurs est réalisée avec des équipements variés, par exemple des chariots cavaliers ou des chariots élévateurs, ou encore des portiques.

A l’intérieur d’un terminal, le transport des conteneurs est assuré par des véhicules pouvant être des chariots cavaliers, des camions, des véhicules à guidage automatique, etc. Dans la zone de stockage, l’empilement et le dépilement des conteneurs peut faire intervenir des équipements comme des portiques, des chariots élévateurs, des chariots cavaliers, etc. Entre les terminaux, le transport des conteneurs peut être réalisé par exemple avec des navettes ferroviaires comme c’est prévu au port du Havre, ou par des camions avec plusieurs remorques, comme c’est le cas actuellement au port de Rotterdam.

Présentation du modèle

Le PPP englobe la gestion des véhicules de transport de conteneurs, la gestion des équipements pour la manutention de leurs conteneurs, et la gestion de bout en bout des conteneurs dans les terminaux du port. Nous proposons un modèle tactique pour ce problème. La planification avec ce modèle fournit une ligne directrice pour la gestion opérationnelle des terminaux à conteneurs coopérant dans le port, sur un horizon de temps donné. Dans le modèle proposé, la planification de l’allocation de postes à quai attribue à chaque bateau – navire au long cours, navire caboteur, barge fluviale – au moins une position d’amarrage dans un terminal, et détermine les périodes de prise en charge correspondantes. Un plan est aussi calculé pour les trains, qui sont affectés aux voies ferrées dans les terminaux au cours du temps. Les camions sont considérés par groupe. Dans un groupe, les camions sont assignés aux terminaux par les décisions prises pour leurs conteneurs. Ci-après, le mot véhicule désigne un bateau, un train ou un groupe de camions. Un véhicule a une date d’arrivée et une dernière période de présence possible dans le port (date échue, ou deadline en anglais). Un bateau ou un train a de plus une date de départ souhaitée (date d’échéance, ou due date en anglais) ainsi qu’un coût de retard. Ce coût augmente par période de présence au port après la date d’échéance. L’objectif global est de minimiser la somme des coûts des retards, le coût de retard dépendant de l’importance du bateau ou du train. En pratique, il est en général possible de fixer des rendez-vous aux camions. Nous supposons que ces rendez-vous permettent d’éviter leur retard à un niveau tactique et par conséquence les camions n’ont pas de coût de retard dans notre modèle. Toutefois, leur retard reste possible à un niveau opérationnel.

L’horizon de planification est divisé en périodes de durées égales. Le choix de la durée d’une période dépend de plusieurs critères. Premièrement, dans notre modèle, les décisions d’allocation de ressources aux véhicules doivent être prises pour des périodes complètes. Par exemple, un poste à quai est alloué à un bateau pour des périodes consécutives indivisibles. Il en est de même pour l’affectation d’une grue à un bateau. Afin que l’allocation de ressources soit efficiente, la durée d’une période doit être suffisamment petite. Deuxièmement, la durée d’une période a un impact important sur la planification produite et les décisions qui y sont prises. Ainsi, dans le cas de terminaux non automatisés, la durée d’un shift de travail est à prendre en compte, c’est à dire le nombre d’heures travaillées à la suite par une équipe. Un shift de travail dure en général plus de quatre heures. Choisir une durée de période qui en est un nombre diviseur permet de définir des tâches par période ensuite groupées par shift de travail. Troisièmement, les méthodes de résolution proposées pour ce problème sont naturellement plus rapides avec un petit nombre de périodes. A partir de ces critères parfois contradictoires, nous avons décidé d’utiliser une durée de période d’une ou deux heures lors des expériences numériques.

Dans ce modèle, le niveau de granularité pour les conteneurs est le lot. Un lot est un ensemble de conteneurs qui sont déchargés d’un véhicule source et chargés plus tard sur un autre véhicule destinataire. Rappelons qu’un groupe de camions est considéré comme un seul véhicule. Un conteneur déchargé de son véhicule source est souvent transporté à l’intérieur du terminal vers la zone de stockage. Il peut rester empilé là, ou être transporté vers un autre terminal. Il est ensuite chargé sur le véhicule destinataire, en général plusieurs jours après son déchargement. Une solution fournit les terminaux et les périodes pour décharger, charger et stocker les lots de conteneurs, ainsi que les périodes pour les transporter entre terminaux. Le sous-problème d’assigner aux conteneurs des blocs de stockage dans les terminaux est hors du champ du modèle proposé , une revue de la littérature est effectuée, où le problème d’allocation de stockage par bloc est présenté. Pour une revue détaillée des opérations de transport et de stockage dans les terminaux à conteneurs, le lecteur est redirigé vers .

Deux ressources principales sont considérées explicitement pour décharger et charger les conteneurs des véhicules : les zones de prise en charge et les groupes de grues . Les zones de prise en charge sont les endroits où les conteneurs sont manutentionnés sur les bateaux et sur les trains, c’est à dire respectivement les postes à quai et les groupes de voies ferrées. Un quai est partitionné en postes à quai. Un groupe de voies ferrées rassemble des voies ferrées adjacentes. L’allocation d’espace aux camions au cours du temps n’est pas considérée, car la ressource limitant leur prise en charge est supposée ici être les grues assurant la manutention de leurs conteneurs il y a trois zones de prise en charge : deux postes à quai et un groupe de voies ferrées.

Les grues opérant directement sur les véhicules sont l’autre ressource principale. Les grues pour les bateaux sont groupées par quai. Les grues pour les trains sont considérées par groupe de voies ferrées. Celles pour les camions sont groupées par terminal à conteneurs. il y a un groupe de neuf grues de quai opérant dans deux postes à quai, un groupe de portiques opérant sur les voies ferrées et un groupe de chariots cavaliers opérant pour les camions. Toutes ces grues sont soit montées sur rails, soit sur roues, et donc mobiles.

L’affectation des grues aux bateaux est déterminée dans notre modèle. Le nombre de grues assignées à un bateau peut changer d’une période à une autre, les grues d’un groupe pouvant se déplacer le long du quai où elles opèrent. Il est supposé que les grues de quai d’un même groupe ont des caractéristiques identiques. Un groupe de grues pour bateaux est caractérisé par son nombre de grues de quai et par leur productivité marginale, étudiée dans [55]. Par exemple, supposons qu’une grue de quai seule peut manutentionner en moyenne 25 conteneurs par heure. Alors, quatre grues assignées au même bateau soulèveront au plus 75 conteneurs par heure, à cause des interférences entre elles. Cinq grues assignées au même bateau ne pourront soulever plus de 90 conteneurs par heure, pour la même raison. Ainsi, le nombre maximum de conteneurs manutentionnés en une période par un nombre donné de grues de quai opérant simultanément sur un bateau fait partie des données du modèle.

Puisque les grues pour les trains et celles pour les camions opèrent sur plusieurs véhicules dans de courtes périodes de temps avec peu d’interférences entre elles, un groupe de grues pour trains ou camions a seulement une caractéristique : un nombre maximum de conteneurs qu’il peut manutentionner par période. Les sous-problèmes de calculer des ordonnancements détaillés pour les grues, notamment un par bateau, sont hors du champ du problème étudié. Par exemple, il s’agit d’ordonnancement tenant compte du plan d’arrimage du bateau, avec des contraintes opérationnelles de précédence sur la manutention des conteneurs liées à leur ordre d’empilement et à la stabilité du bateau. Pour une revue détaillée des problèmes d’ordonnancement des grues de quai, le lecteur est redirigé vers .

Une solution à une instance simplifiée de ce problème , avec une durée de période de deux heures. Un navire au long cours est amarré au poste à quai en haut à gauche du terminal 1, de la période 20 à la période 30. Le lot b de trois conteneurs est déchargé de ce navire de la période 25 à la période 26. D’une part, l’affectation de grues de quai à ce bateau est nécessaire pour que ce déchargement soit possible. D’autre part, son déchargement est réalisable si une contrainte est respectée sur la quantité de conteneurs manutentionnés dans ce terminal par période. Cette contrainte par terminal et par période limite les flux de conteneurs entrant et sortant (déchargements/chargements de conteneurs par les groupes de grues et émissions/réceptions de conteneurs par transport inter terminal). Cette limitation est imposée pour prendre en compte les ressources de transport de conteneurs à l’intérieur d’un terminal ainsi que celles de dépilement et d’empilement des conteneurs dans sa zone de stockage. Ensuite, ce lot b est stocké dans ce terminal de la période 25 à la période 35. Le nombre de conteneurs empilés dans un terminal doit toujours rester sous une limite donnée. Ensuite, ce lot b est transporté vers le terminal 2 à la période 35, pour être finalement chargé sur un navire caboteur pendant les périodes 41 et 42. La manutention de cinq autres lots est aussi décrite dans la figure où les périodes sont omises dans un souci de lisibilité. Plusieurs contraintes additionnelles doivent être respectées pour le transport inter-terminal des conteneurs. Le transport du terminal 1 au terminal 2 prend un nombre fixé de périodes, ici une période.

Table des matières

Introduction générale
Le transport conteneurisé
La compétition entre ports à conteneurs
Structure de la thèse
1 Le problème de la planification portuaire
1.1 Introduction
1.2 La manutention des conteneurs
1.3 Présentation du modèle
1.4 Revue de la littérature
1.4.1 Problème d’allocation de postes à quai
1.4.2 Problème d’allocations simultanées de postes à quai et de grues
1.4.3 Problème d’allocations simultanées de postes à quai et de stockage
1.4.4 Prise en charge des camions et des trains
1.4.5 Autres modèles de gestion de flux de conteneurs portuaire
1.5 Génération des instances
1.5.1 Méthode de génération du trafic
1.5.2 Classes d’instances 1 à 16
1.5.3 Classes d’instances I, II, III et A, B, C
1.6 Conclusion
2 Méthodes de décomposition et heuristiques
2.1 Introduction
2.2 Algorithme par séparation et évaluation progressive
2.2.1 Présentation
2.2.2 Règle de branchement utilisée
2.2.3 Génération de coupes
2.2.4 Implémentation par un solveur
2.3 Décomposition de Dantzig-Wolfe
2.3.1 Formulation matricielle du problème
2.3.2 Décomposition de la formulation
2.3.3 Génération de colonnes
2.3.4 Stabilisation de la génération de colonnes
2.3.5 Algorithme par séparation et génération de colonnes progressive
2.3.6 Problèmes liés à la dégénérescence
2.4 Heuristiques basées sur une décomposition
2.4.1 Heuristique du problème maître restreint
2.4.2 Heuristique de relaxation et fixation
2.4.3 Heuristique de restriction et fixation
2.5 Conclusion
3 Modèles mathématiques et résolution exacte
3.1 Introduction
3.2 Formulations
3.2.1 Notations
3.2.2 Formulation compacte
3.2.3 Formulation étendue
3.3 N P-difficulté
3.4 Expériences numériques
3.4.1 Résultats de la formulation compacte
3.4.2 Résultats de la formulation étendue
3.5 Allocation de postes à quai
3.5.1 Formulation compacte
3.5.2 Formulation étendue
3.5.3 Expériences numériques
3.6 Conclusion
4 Résolution heuristique
4.1 Introduction
4.2 Principe
4.3 Pré-affectation aux terminaux
4.4 Heuristiques de résolution du PLVM
4.4.1 Heuristique du problème maître restreint
4.4.2 Heuristique de relaxation et fixation
4.4.3 Heuristique de restriction et fixation
4.4.4 Stratégie structurelle de partitionnement des variables
4.5 Expériences numériques
4.5.1 Classes d’instances 9 à 16
4.5.2 Classes d’instances I, II, III, A, B et C
4.6 Conclusion
5 Planification en horizon glissant
5.1 Introduction
5.2 Principe
5.3 Application au problème de la planification portuaire
5.3.1 Modèle d’incertitude
5.3.2 Paramétrage de l’horizon glissant
5.4 Expériences numériques
5.4.1 Déroulement
5.4.2 Résultats
5.5 Conclusion
Conclusion

Lire le rapport complet