No dordre : 76

ECOLE CENTRALE DE LILLE

THSE

En co-tutelle avec lEcole Nationale des Sciences de lInformatique de Tunis

prsente en vuedobtenir le grade de

Docteuren

Spcialit : Automatique et Informatique Industriellepar

Meriam Kefi GazdarDOCTORAT DELIVRE PAR LECOLE CENTRALE DE LILLE

Titre de la thse :Optimisation Heuristique Distribue du Problme de Stockage de Conteneurs

dans un Port

Soutenue le 23 Juin 2008 devant le jury compos de :

M. Faouzi Ghorbel Prof. ENSI PrsidentM. Moncef Tagina Prof. ENSI RapporteurM. Ren Mandiau Prof. UVHC RapporteurM. Khaled Ghdira Prof. ENSI Directeur de thseM. Pascal Yim Prof. ECL Directeur de thse

Thse prpare dans le Laboratoire LAGIS, Ecole Centrale de LilleEcole Doctorale SPI 072

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

A mes trs chers parents, dont leur tmoin ducatif est transmis leurs enfants ;A mon cher poux Achraf ;

A mes chers frres ;A tous les miens.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Remerciements

Jexprime mes profonds remerciements Monsieur Khaled Ghdira, professeur lENSI,

directeur de cette thse en Tunisie, responsable du laboratoire SOIE et directeur de lENSI qui

na jamais compt prcieux conseils et judicieuses suggestions. Quil soit assur de ma gratitude

et de ma reconnaissance pour son soutien durant ces annes de recherche.

Je tiens remercier galement Monsieur Pascal Yim, Professeur lECL, qui ma co-encadr au

cours de ces annes dans le cadre dune cotutelle, pour son aide et son soutien inconditionnels.

Mes plus vifs remerciements vont galement Monsieur Faouzi Ghorbel, professeur lENSI,

pour avoir accept de prsider le jury de cette thse.

Je tiens exprimer toute ma reconnaissance Monsieur Ren Mandiau, professeur lUniversit

de Valenciennes et du Hainaut-Cambrsis, et Monsieur Moncef Tagina, Matre de confrences

lENSI, pour avoir accept de rapporter cette thse et pour leurs critiques constructives qui

ont permis damliorer la qualit de ce manuscrit.

Jadresse mes remerciements galement Monsieur Ouajdi Korbaa, Matre de confrences

lISITC de Hammam Sousse pour mavoir suivie de prs tout au long de cette thse.

Jaimerais remercier aussi Monsieur Mohamed Ben Ahmed, Professeur mrite lENSI davoir

apport des jugements trs constructifs permettant lamlioration du manuscrit et je lui en suis

reconnaissante.

Mes remerciements vont aussi lOffice de la Marine Marchande et tout particulirement Mon-

sieur Foued Ben Othman, directeur de lOMMP et Madame Olfa Elphil pour stre intresss

mon travail et mavoir aid accomplir mon tude exprimentale au sein du port de Rads.

Je remercie Mme Safya Belghith, Professeur lENIT et Directrice de lESTI de Tunis pour

mavoir aid mener bien ce travail.

Mes remerciements vont mes collgues de SOIE, LI3, ENSI, ESTI et LAGIS avec qui jai

pass des moments inoubliables. Jen garderai de bons souvenirs.

Merci mes parents et mes deux frres pour leur soutien moral et lintrt quils ont toujours

port ce que je faisais ...

Merci Achraf pour avoir subi plus que les autres ma thse et pour sa prsence inestimable

mes cots.

Ma profonde gratitude tous les membres de ma famille, et particulirement une pense tous

ceux qui me sont chers et qui ne sont plus parmi nous.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Il faut faire de la vie un rve et dun rve une ralit.Pierre Curie

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Rsum

Les terminaux conteneurs constituent des interfaces inter-modales essentielles pour le r-seau de transport mondial. Une manutention efficace des conteneurs dans des terminaux estdune importance cruciale pour la rduction des cots de transport et la dtermination desplans dembarquement. Dans ce rapport de thse, nous proposons principalement une approchede rsolution distribue travers la description dun modle doptimisation heuristique distri-bue baptis COSAH (COntainer Stacking via multi-Agent approach and Heuristic method)qui permet de simuler, rsoudre et optimiser lespace de stockage disponible pour manier lesdparts et les arrives des conteneurs dans un port fluvial ou maritime. Autrement dit, CO-SAH permet de minimiser le nombre total de mouvements parasites tout en respectant descontraintes dynamiques despace et de temps.

Les performances de COSAH sont ensuite values sur des instances gnres alatoirement,ainsi que des instances extraites de la ralit dun port maritime tunisien : le port de Rads.En effet, nous avons procd une tude exprimentale implmentant et comparant COSAH la version centralise associe, toutes deux bases sur un algorithme de recherche non informeet un algorithme de recherche informe. Les rsultats obtenus, prsents et illustrs, montrentlefficacit de COSAH en particulier, et dune mthode doptimisation heuristique distribuealliant les deux concepts : Agent et Heuristique, en gnral.

Mots cls : approche multi-agent, co-rsolution, mthode heuristique, rseaux de Petricolors, rsolution distribue de problmes, stockage de conteneurs, transport conteneuris.

Abstract

Container terminals are essential intermodal interfaces in the global transportation network.Efficient container handling at terminals is of vital importance for the reduction of transporta-tion costs as well as the determination of shipping schedules. In this thesis report, we propose adistributed solving approach through the development of a distributed Heuristic-Optimizationmodel denoted COSAH (COntainer Stacking via multi-Agent approach and Heuristic method)that allows to simulate, solve and optimize the amount of storage space for handling containerdepartures and arrivals within a fluvial or maritime port. COSAH allows to minimize the ex-pected total number of rehandles while respecting spatio-temporal constraints. Performancesof COSAH are then evaluated based on random-generated instances, as well as on instancesextracted from a real-world case study : the port of Rads. Indeed, we conducted an experi-mental study implementing and comparing COSAH to the associated centralized version basedon non informed-search algorithm and an informed-search algorithm. The obtained results,presented and illustrated, evince the efficiency of COSAH in particular, and of a distributedheuristic-optimization method combining two concepts : Agent and Heuristic, in general.

Keywords : colored Petri nets, container stacking, containerized transport, distributedproblem-solving, eco-solving, heuristic method, multi-agent approach.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Table des matires

Table des matires 1

Table des figures 5

Liste des algorithmes 7

Introduction Gnrale 9

I tat de lart 15

1 Transport Conteneuris 171.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2 Le transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3 Le transport maritime . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3.1 Le transport de marchandises . . . . . . . . . . . . . . . . 191.3.2 Les trois rvolutions du transport maritime . . . . . . . . . 21

1.4 Le transport fluvial . . . . . . . . . . . . . . . . . . . . . . . . . . 221.5 La conteneurisation . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.5.1 La rvolution du conteneur . . . . . . . . . . . . . . . . . . 231.5.2 1956, naissance dun concept . . . . . . . . . . . . . . . . . 241.5.3 Le principe de la standardisation . . . . . . . . . . . . . . 241.5.4 Manutention et expditions . . . . . . . . . . . . . . . . . 251.5.5 Les oprations dans un terminal conteneurs . . . . . . . 261.5.6 Les systmes dinformation . . . . . . . . . . . . . . . . . . 261.5.7 La multimodalit Multimodal Transport . . . . . . . . . . 28

1

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

2 Table des matires

1.5.8 Avantages et Inconvnients de la conteneurisation . . . . . 291.6 Les ports conteneuriss . . . . . . . . . . . . . . . . . . . . . . . . 301.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2 Problme de Stockage de Conteneurs (PSC) 332.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.2 Processus dans un terminal Conteneurs . . . . . . . . . . . . . . 34

2.2.1 Planification de navires . . . . . . . . . . . . . . . . . . . . 352.2.2 Transport sur le quai Quay Transport . . . . . . . . . . . . 392.2.3 Ordonnancement des quipements de manutention . . . . . 41

2.3 Problme de Stockage de Conteneurs -PSC Container StackingProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.3.1 Dfinition du PSC . . . . . . . . . . . . . . . . . . . . . . 472.3.2 Formulation du PSC . . . . . . . . . . . . . . . . . . . . . 472.3.3 Problmes analogues . . . . . . . . . . . . . . . . . . . . . 512.3.4 Mthodes existantes pour la rsolution du PSC . . . . . . 52

2.4 Classification des travaux selon les ports conteneuriss dans le monde 592.5 Bilan et synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

II Approche propose 63

3 Mthodes et approches adoptes 653.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.2 Les systmes multi-agent . . . . . . . . . . . . . . . . . . . . . . . 66

3.2.1 Pourquoi avons-nous opt pour les systmes multi-agent ? . 663.2.2 Quelques concepts . . . . . . . . . . . . . . . . . . . . . . 683.2.3 Rsolution par coordination : lco-rsolution . . . . . . . . 753.2.4 Formalisation des Systmes Multi-Agent . . . . . . . . . . 77

3.3 Les rseaux de Petri . . . . . . . . . . . . . . . . . . . . . . . . . 813.3.1 Dfinition dun rseau de Petri . . . . . . . . . . . . . . . . 813.3.2 Rseaux de Petri colors et la plate-forme CPN-Tools . . . 82

3.4 Optimisation heuristique . . . . . . . . . . . . . . . . . . . . . . . 833.4.1 Que faire face un problme NP-dur ? . . . . . . . . . . . 83

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Table des matires 3

3.4.2 Classes dheuristiques . . . . . . . . . . . . . . . . . . . . . 863.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4 Le modle COSAH : Un modle dOptimisation Heuristique Dis-tribue du PSC 914.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.2 Modle de base : ContEco . . . . . . . . . . . . . . . . . . . . . . 92

4.2.1 Description de la version relaxe du PSC : PSCR . . . . . 934.2.2 Description de ContEco . . . . . . . . . . . . . . . . . . . 95

4.3 Le modle COSAH . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.3.1 Description du problme tudi . . . . . . . . . . . . . . . 1024.3.2 Description du modle COSAH . . . . . . . . . . . . . . . 104

4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

5 Validation Exprimentale 1355.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1355.2 Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

5.2.1 Critres de choix . . . . . . . . . . . . . . . . . . . . . . . 1365.2.2 Prsentation de JADE . . . . . . . . . . . . . . . . . . . . 137

5.3 Exprimentations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1385.3.1 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1385.3.2 Rsultats numriques . . . . . . . . . . . . . . . . . . . . . 138

5.4 Cas dtude : Port de Rads . . . . . . . . . . . . . . . . . . . . . 1455.4.1 Prsentation du port . . . . . . . . . . . . . . . . . . . . . 1465.4.2 Exprimentations . . . . . . . . . . . . . . . . . . . . . . . 149

5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

Conclusion Gnrale 151

Bibliographie 167

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

4 Table des matires

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Table des figures

1.1 Le turnover mondial de conteneurs (en million EVP) . . . . . . . 21

2.1 Succession des oprations dans un terminal conteneurs . . . . . 352.2 Types dquipements de manutention . . . . . . . . . . . . . . . . 442.3 Illustration de la reprsentation dun tat . . . . . . . . . . . . . . 482.4 Modle uncertain doptimisation plusieurs tapes . . . . . . . . 502.5 Exemple de manipulation des cubes . . . . . . . . . . . . . . . . 522.6 Analogie entre le PSC et le problme du monde des cubes . . . . 53

3.1 Evolution des paradigmes de programmation . . . . . . . . . . . . 683.2 Tir dune transition sensibilise . . . . . . . . . . . . . . . . . . . 82

4.1 Schma Conceptuel de lapproche propose . . . . . . . . . . . . . 924.2 Configuration initiale et configuration finale atteindre . . . . . . 954.3 Composants dun agent Conteneur et ses interactions . . . . . . . 964.4 Module dautonomie dun agent Conteneur . . . . . . . . . . . . . 994.5 Module de rception dun agent Conteneur . . . . . . . . . . . . . 994.6 Message " Tu_me_gnes (G) " . . . . . . . . . . . . . . . . . . . 1004.7 Message " Chercher_Place (CP) " . . . . . . . . . . . . . . . . . 1004.8 Message " Sur_Toi (ST) " . . . . . . . . . . . . . . . . . . . . . . 1014.9 Message " Tu_es_Libre (L) " . . . . . . . . . . . . . . . . . . . . 1014.10 Composants du module de prise de dcision dun agent Conteneur 124

5.1 Comparaison DistNIS par rapport CentNIS . . . . . . . . . . . 1395.2 Comparaison de DistIS par rapport CentIS . . . . . . . . . . . . 1405.3 Comparaison de CentIS par rapport CentNIS . . . . . . . . . . 141

5

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

6 Table des figures

5.4 Comparaison de DistIS par rapport DistNIS . . . . . . . . . . . 1425.5 Mesure de performance de COSAH par rapport la borne maxi-

male . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1435.6 Exemple de calcul de la borne maximale du nombre de mouvements1445.7 Sensibilit de DistIS et de DistNIS la hauteur moyenne . . . . . 1455.8 Mesure de performance de COSAH par rapport la politique ac-

tuelle du port . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Liste des Algorithmes

4.1 Comportement global des agents Conteneur . . . . . . . . . . . . 1104.2 Comportement de dpart des agents Conteneur A . . . . . . . . . 1114.3 Messages changs entre les agents Conteneur . . . . . . . . . . . 1124.4 Comportement des agents Conteneur recevant le message gn() . 1134.5 Comportement des agents Conteneur perturbs . . . . . . . . . . 1134.6 Comportement des agents Conteneur recevant le message Cher-

cherPlace() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134.7 Comportement des agents Conteneur recevant le message JeSuis-

Libre() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1144.8 Comportement des agents Conteneur recevant le message Dsol() 1154.9 Comportement des agents Conteneur recevant le message Migrer () 1164.10 Comportement des agents Conteneur recevant le message Confir-

mer () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.11 Comportement des agents Conteneur recevant le message Rejeter () 1174.12 Comportement des agents Conteneur recevant le message TuEs-

Libre () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174.13 Traitement des arrives lime dpart . . . . . . . . . . . . . . . 1194.14 Algorithme doptimisation heuristique . . . . . . . . . . . . . . . . 131

7

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

8 Liste des Algorithmes

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Introduction Gnrale

Cette introduction a pour objectif de dfinir notre problmatique de rechercheet de prsenter le positionnement scientifique de notre dmarche pour y rpondre :

Problmatique

Le transport fluvial et maritime devient, de nos jours, de plus en plus impor-tant et reprsente une alternative crdible et intressante au transport terrestre etarien. Linterdpendance entre commerce et flux de biens et de services, en voiedvolution continue, fait que ce systme de transport reprsente une proccupa-tion dune importance cruciale. En effet, les diffrentes compagnies et entreprisesfournissent de grands efforts dans le but de dtecter des possibilits de rductiondes cots associs ce transport. Ces cots sont affects par les temps morts dansle cas de navires improductifs immobiliss dans un port, et aux changes entre lesdiffrents modes de transport dans les ports (terrestre, ferroviaire ou navigable)dans le cas de transport multimodal. Cest donc la recherche les rduire au mi-nimum afin dcourter la distance navire-zone de stockage et dquilibrer les deuxcycles : le cycle Bord (Grue de quai-quai) et le cycle Terre (quai-vhicules-zone destockage). Lune des solutions retenues entre autres, est la conteneurisation quisest vritablement gnralise pour le transport maritime et fluvial des marchan-dises solides sur toutes les mers du globe. Cette solution a permis de raliser desconomies via la standardisation des dimensions, la scurit des marchandises,lacclration des oprations de manutention favorisant lautomatisation du char-gement (ou gerbage) et du dchargement (ou enlvement) et lattnuation desruptures de charge lors des transbordements dun mode de transport lautre.

La conteneurisation peut induire cependant des cots levs lis aux investisse-

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

10 Introduction Gnrale

ments en espace de stockage, lapprovisionnement et entretien des quipements,aux temps morts ou mouvements inutiles durant le processus dchargement-stockage-chargement des conteneurs et au dsquilibre du flux de marchandisesimposant des transports de conteneurs vides.

Toutefois, pour tre comptitif, le transport fluvial ou maritime doit amliorerses services et baisser ses cots. De ce fait, plusieurs interrogations simposent :Comment peut-on assurer un meilleur cheminement de marchandises ? Commentpeut-on minimiser les retards ?, Comment doit-on procder afin daugmenter lescapacits de stockage ? etc. Toutes ces questions se posent au niveau des diffrentesactivits sexerant dans un port conteneurs, et constituent des objectifs soucisdes thoriciens et praticiens tel quils sont dcrits dans [SVS04, GG06].

Dans le contexte dun port fluvial ou maritime devant grer un trafic de conte-neurs au croisement de voies terrestres, ferroviaires et fluviales/ maritimes et ga-lement responsable de la gestion dun stock de conteneurs sur son site, la gestiondes quais constitue un ensemble de problmes de dcision rsoudre pour faireface un aux important de conteneurs et une augmentation de la taille desnavires. On est men soit augmenter la taille des ports, alternative coteuse enterme de ressources spatiales et matrielles mais facile car elle ne demande aucuneffort doptimisation, soit amliorer la productivit, solution plutt raisonnablemais demandant de grands efforts de rflexion lchelle pratique et thorique.

Dans notre cadre, amliorer la productivit revient minimiser le temps passpar un conteneur ou un navire dans un port que ce soit en import ou en export.

Nanmoins, loptimisation de la gestion et de la logistique des conteneurs dansun port et plus prcisment la gestion fine de placement des conteneurs apparatcomme un problme part entire avec ses difficults propres jouant un rle pr-pondrant dans la minimisation des temps morts. Ce problme est connu dans lalittrature par Container Stacking (Storage ou encore Handling) Problem. Il seradsign dans la suite par lacronyme PSC : " Problme de Stockage de Conte-neurs ". Il sagit de la manutention des conteneurs en import ou en export quipeut conduire de nombreux dplacements ou remaniements inutiles, consistant dpiler un nombre de conteneurs pour atteindre un conteneur bien dterminplac en dessous de la pile. Lobjectif donc est de rduire ces dplacements appelsmouvements parasites ou remaniements Shifting moves/ unproductive moves. Ce

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Introduction Gnrale 11

problme est modlis par un systme complexe, dynamique et incertain dans le-quel les interactions entre ses diffrents lments (conteneurs, navires, ressourcesmatrielles, etc.) sont en perptuelle volution (arrives imprvues de conteneurs,dparts estims pour les conteneurs en export, changements continus de variables)ncessitant, de ce fait, la remise en question de sa structure et de sa dynamique.

En rsum, la problmatique dfinie ci-dessus snonce par : Comment d-velopper une mthode capable de modliser, simuler, rsoudre et optimiser leprocessus de stockage de conteneurs dans un port ?

Objectifs

Ainsi dcrit et par analogie aux problmes classiques de planification, le pro-blme de stockage de conteneurs PSC est considr NP-difficile et NP-complet.Une solution optimale de ce problme est un plan dactions de dpilement/empilementde conteneurs de longueur minimale, cest--dire constitu dun nombre de mou-vements de dplacements minimal, tenant compte des contraintes dynamiquesque ce soit en terme despace ou de temps. Les interactions, les collaborations etles dynamiques qui en dcoulent font que le PSC est modlis par un systmecomplexe dune part, cest dire constitu de nombreux composants en interac-tion dynamique entre eux et avec le monde extrieur ; et dautre part ouvert, cest dire capable de maintenir ses fonctions malgr les arrives et dparts de ses com-posants. Peu de travaux de recherche lui ont t consacrs. En effet, nous avonsconstat que ces travaux utilisent pour la plupart des modles analytiques (lesmodles mathmatiques et la programmation dynamique) rgis par des lois sto-chastiques, et des modles de simulation comme ceux qui font appel lapprocheoriente objet ou lapproche multi-agent. Nous retrouvons aussi des mthodesincompltes tels que les algorithmes gntiques qui sinteressent minimiser letemps pass par un navire au quai dun port de terminaux conteneurs. Cesmodles savrent trs limits face la dynamique et la nature combinatoire dece problme.

tant donns ses multiples aspects, il serait intressant daborder globalementet en profondeur cette problmatique dans cette thse. Nous aurons recours deuxnotions fondamentales : Les Systmes Multi-Agent, et les Heuristiques. Dune

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

12 Introduction Gnrale

part, les systmes multi-agent connaissent actuellement un certain engouement, etconstituent une solution propose par la communaut de lintelligence artificielledistribue qui semble adapte de nombreux problmes en raison de leur capacit aborder les systmes complexes et ouverts.

Dautre part, les heuristiques permettent de fournir des solutions ralisables dequalit acceptable souvent trs proches de loptimal et dtermines en un tempsraisonnable (complexit polynomiale). Elles sont situes mi-chemin entre lesmthodes exactes de recherche oprationnelle qui se limitent la nature combina-toire de ces problmes rendant difficile la rsolution des problmes rels tels que lePSC et les mtaheuristiques dont linconvnient relve de leur sensibilit aux dif-frents problmes doptimisation combinatoire vu quelles ncessitent un contrleprcis des paramtres dexcution et souvent des changements dynamiques de cesparamtres pour sadapter chaque problme.

Notre travail consiste alors associer les concepts de systmes Multi-agentet de loptimisation heuristique, et ce en proposant un modle doptimisationheuristique distribue baptis COSAH pour COntainer Stacking based on multi-Agent approach and Heuristic method qui allie dune part, les caractristiques dessystmes Multi-agent pour la prise de dcision, la communication et la coopra-tion inter agents limage de conversation humaine et dautre part, la mise enface dune certaine "intelligence" supporte par des heuristiques. Nous pensonsque la combinaison des deux notions : distribution et heuristique qui, spar-ment, fournissaient de bons rsultats, reprsente une potentialit damliorationintressante.

Dans un contexte bien dtermin, selon des motivations et des enjeux que nousallons dfinir, et considrant des hypothses de travail que nous allons dcrire,le modle COSAH doit optimiser le placement des conteneurs dans la zone destockage (statique ou dynamique selon les dparts ou les arrives de navires oucamions ou de conteneurs en import ou en export) en minimisant le nombre demouvements improductifs respectant un nombre de contraintes spatio-temporelleset tenant compte de plusieurs paramtres pouvant catgoriser les conteneurs etdfinir une certaine priorit entre eux (destination, taille, date de dpart, horizondes arrives des barges ou navires associs).

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Introduction Gnrale 13

Organisation du Rapport

Lorganisation de cette thse suit une progression ordonne. Ce document sedcompose en deux parties correspondant au cheminement de notre dmarchescientifique.

Partie 1 : tat de lartLa premire partie expose notre contexte de travail dans deux chapitres. Le

premier chapitre prsente le transport conteneuris, contexte de notre problma-tique, et dfinit les diffrentes terminologies et concepts intrinsques. Le deuximechapitre survole, en premier lieu la littrature des problmes de dcision rencon-trs et dcoulant de lactivit et de la logistique des conteneurs sur un terminal conteneurs. En deuxime lieu, ce chapitre se concentre sur le problme tudi :le PSC en faisant un tour dhorizon des problmes analogues, et des mthodesde rsolution qui lui sont ddies. Cela permet de souligner la complexit, ladynamique et louverture caractrisant le PSC.

Cette partie nous permet ainsi de nous positionner par rapport notre probl-matique et de spcifier nos orientations et nos choix qui serviront de fondements notre proposition.

Partie 2 : Approche ProposeLa deuxime partie sera ddie lapproche de rsolution distribue que nous

proposons pour la rsolution et loptimisation du problme de stockage de conte-neurs. Elle sarticule autour de trois chapitres : le premier chapitre prsentedabord les concepts cls de notre rflexion : le paradigme Multi-agent, le for-malisme rseaux de Petri colors et les mthodes heuristiques, afin de dfinirquelques notions que nous retrouvons au fil de cette thse et de justifier des choixque nous adoptons dans notre proposition.

Le deuxime chapitre prsente notre proposition constitue de deux contribu-tions : Dabord, une premire contribution releve par un modle multi-agent debase baptis ContEco traitant une version relaxe du PSC dsigne par PSCR. Cemodle est conu et dvelopp par analogie au modle dco-rsolution dvelopppour le problme de planification classique " le monde des cubes ". En outre, ce

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

14 Introduction Gnrale

chapitre expose une formalisation de ce modle utilisant la mthode formelle : lesrseaux de Petri colors.

Ensuite, une deuxime et principale contribution releve par le modle CO-SAH. Ce chapitre analyse en dtails larchitecture, les connaissances de base, etla dynamique des agents mis en jeu. Il sattarde sur la mthode heuristique miseen oeuvre dans ce modle ainsi que sur les tapes attractives du comportementdes agents.

Le troisime chapitre valide notre modle COSAH en procdant une tudeempirique et comparative implmentant et simulant celui -ci, et des exprimen-tations visant valuer ses performances via des jeux de tests gnrs alatoire-ment. Il propose un prototype sappuyant sur la plate-forme multi-agent JADEet intgrant toutes les particularits inhrentes notre problme et au modleCOSAH. Il dcrit en outre lenvironnement de limplmentation, les paramtresdexprimentations et les rsultats obtenus. Il vrifie enfin la validit de notreproposition utilisant un jeu de tests rels dans le cas dun port maritime : le portde Rads en Tunisie.

Enfin nous concluons notre travail tant au niveau des apports que des ouver-tures envisages.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Premire partie

tat de lart

15

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Chapitre 1

Transport Conteneuris

1.1 Introduction

Indubitablement, le transport joue un rle capital au sein de lconomie depar son omniprsence dans la chane de production et ce, toute chelle go-graphique. Le transport se conoit comme une composante intgrale du cycle deproduction-consommation. En fait, bien souvent les entreprises et les individusdoivent prendre des dcisions sur les routes emprunter afin dacheminer dufret ou des individus travers lespace conomique. Il nest pas exceptionnel deconstater que les cots de transport peuvent reprsenter 20% du prix total dunbien. Le choix du mode de transport pour acheminer de la marchandise ou desindividus dune origine une destination devient grand dans un contexte mar-qu par la production de biens de consommation lgers et par des techniques deproduction de plus en plus avances. Ce choix dpend dun nombre de facteurstelles que la nature des biens, les infrastructures disponibles, les origines et lesdestinations.

Les modes de transport sont : le transport terrestre, le transport fluvial ou ma-ritime et transport arien. Ils reprsentent une part importante de la gographiedes transports en tant que pourvoyeurs de mobilit.

Le transport maritime ou fluvial a t traditionnellement un vecteur de com-merce et de progrs trs fortement concurrenc aujourdhui par le chemin de feret la route. Compares dautres modes de transport, les voies navigables offrent

17

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

18 Transport Conteneuris

plusieurs avantages sur lesquels les constructeurs ont su capitaliser. Leur cot estfaible, ramen la tonne-kilomtre. En effet, 25000 milliards de Tonnes-Km defret parcourent les ocans annuellement compars 7000 pour le rail et 3 000 pourla route. Il sagit de pas moins de 71% de tout le fret mondial transport. Lesdernires annes, les compagnies leaders de ce mode de transport peu consomma-teur dnergie ont su le fiabiliser et ladapter aux grands volumes de fret. Commeles modes arien et terrestre, le transport maritime volue sur son espace propre :un espace la fois gographique par ses attributs mais aussi stratgique par sonrle.

Les plus rcentes avances technologiques touchant au transport par voie na-vigable ont cherch modifier les cluses et les canaux, augmenter la taille, automatiser et spcialiser les navires (porte-conteneurs, vraquier, navire-citerneetc.), et dployer la conteneurisation du transport. Ces transformations sont lorigine en partie, du dveloppement dun trafic maritime attentif la demandeaccrue en combustibles ainsi qu la gographie des grands marchs craliers.Dans ce qui suit, nous proposons une dfinition profonde des notions ci intro-duites, savrant ncessaire pour dlimiter le cadre gnral de la problmatiquesouleve dans ce travail. Nous nous rfrons Steenken et al. [SVS04] et desstatistiques extraites des notes dISEMAR [NS002, NS003].

1.2 Le transport

Le transport est le dplacement de personnes ou de biens dun endroit unautre. Les transports modernes constituent un systme. Chaque sous-systme(selon le mode de transport) est constitu dune infrastructure (linaire pourles transports terrestres et ponctuelle pour les transports maritimes et ariens),de vhicules (individuels ou regroups en rames) ou de flux continus (pour lestransports par conduites : gazoducs, oloducs) et de techniques dexploitationparticulires.

De nos jours, le transport de personnes (voyageurs) et le transport de mar-chandises (fret), plus ou moins confondus jusqu une poque rcente, constituentdeux systmes de plus en plus indpendants, mme sils utilisent parfois les mmesinfrastructures et plus rarement les mmes vhicules. Lensemble des oprations

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Le transport maritime 19

de transport de fret, ainsi que tous les services impliqus dans la rception, lalivraison et la manutention des biens pour que ceux-ci soient livrs au momentvoulu chez le destinataire constitue la logistique.

1.3 Le transport maritime

Associe aux transports terrestres que furent le portage ( dos danimal oudhomme) et le roulage (voies romaines), la navigation maritime constitua le pre-mier systme de transport. Elle favorisa, en premier lieu, les littoraux situs surles mers les plus propices au trafic maritime courte distance (cabotage), par-ticulirement de lAsie du Sud-est, et plus encore celui de la Mditerrane et delEurope du nord-ouest. Cest donc dabord de ces mers fermes que partit le d-veloppement des transports. La navigation maritime connut un premier saut tech-nologique avec lapparition au XIXe sicle de la machine vapeur. Celle-ci permiten effet dacclrer les transports sur leau en saffranchissant des contraintes na-turelles (vents et courants) pesant sur les routes maritimes.

Lavnement du commerce lectronique et des flux dmatrialiss ne sonne pasle glas des transports internationaux. La conclusion en ligne de contrats portantsur des biens meubles accompagnera, au contraire, le dveloppement de la fonctionlogistique et des transports internationaux.

Les socits de transport rapide sont ainsi indispensables aux oprateurs ducommerce lectronique pour assurer la livraison des produits commands sur lesrseaux. En amont de la relation entre le distributeur et le client final, lactivitconomique repose sur des changes entre des partenaires loigns et le transportmaritime savre alors indispensable. Une augmentation du tonnage et du traficmaritime accompagne ainsi la croissance de la production mondiale. Cela vautbien sr pour le transport de pondreux et de matires premires, mais au-delpour les biens de consommation et lensemble de la production industrielle.

1.3.1 Le transport de marchandises

Les navires appartiennent gnralement des armateurs. Ceux-ci peuvent ex-ploiter directement leurs navires sur des lignes rgulires ou au contraire les louer

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

20 Transport Conteneuris

laffrtement sous la forme du tramping. Afin de rduire les cots, les naviressont de plus en plus spcialiss un type de cargaison (ptrolier, mthanier, ba-nanier, minralier, vraquier, porte-conteneurs, etc.). Ils sont aussi de plus en plusgrands, de manire transporter des quantits de plus en plus importantes, cequi pose le problme du changement dchelle des volumes transports sur terreet sur mer : 3 000 tonnes au plus par train ou convoi fluvial, 100 200 fois plussur mer. Les plus rcents porte-conteneurs peuvent emporter quelque 6 000 conte-neurs qui, une fois terre, ncessiteront 6 000 camions ou 30 trains complets !Ce problme ne peut tre rsolu que par la capacit de stockage des installationsportuaires ou bien par la transformation des matires importes sur place dansles zones industrialo-portuaires.

Un navire est improductif lorsquil est immobilis dans un port. La rductionde ces temps morts a dabord t obtenue par lacclration des oprations demanutention grce lunification des charges qui permet lautomatisation duchargement et du dchargement. Dautre part, dans le transport maritime, unelarge partie des cots est affecte aux changes dans les ports. On a donc cherch les rduire au minimum en supprimant les ruptures de charge de la marchandiseentre les diffrents modes de transport.

Lune des solutions retenues est la spcialisation des navires et des postesdamarrage, rservs un seul type de cargaison (terminal offshore et sea-line).Les porte-barges Lighter Aboard Ship-LASH permettent de rentrer des bargesfluviales dans un navire de mer, la manuvre pouvant soprer au large desctes. Le transroulage (Ro-Ro : Roll on-Roll off ), qui consiste embarquer lessemi-remorques directement avec leur tracteur sur le navire ferry, sest gnralissur les traverses courtes de lAmrique du nord, de lExtrme-Orient, et surtoutde lEurope.

Enfin, la conteneurisation (Lo-Lo : Lift on-lift off ) sest vritablement gnra-lise pour le transport maritime des marchandises solides sur toutes les mers duglobe. Ces dernires annes, lutilisation de conteneurs pour le transport maritimeintercontinental a augment. La figure 1.1 extraite de [Tur] montre la croissancedu turnover mondial de conteneurs. Commencer avec 50 million EVP en 1985,ce turnover a atteint plus de 350 million EVP en 2004. Une croissance conti-nuelle est attendue dans les prochaines annes, surtout entre lAsie et lEurope.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Le transport maritime 21

Fig. 1.1 Le turnover mondial de conteneurs (en million EVP)

Cependant, cette croissance ncessite de grandes surfaces de stockage et des qui-pements trs lourds de manutention : les portiques transconteneurs. Ces quipe-ments ne prennent place quen certains points (grands ports et portes des grandesagglomrations) qui deviennent ainsi de vritables plates-formes multimodales deredistribution.

1.3.2 Les trois rvolutions du transport maritime

Le secteur du transport maritime qui est un " instrument " privilgi ducommerce international, a lui-mme connu plusieurs rvolutions qui ont concouru une rduction des cots du transport.

1.3.2.1 Premire rvolution

Cette rvolution, sest faite sur linitiative dun oprateur amricain, MalcomMc Lean, la fin des annes 1950. Il a donn naissance la " conteneurisation". Le transport des marchandises dans des conteneurs constitue une forme destandardisation dans le secteur maritime. Les conteneurs constituent des units

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

22 Transport Conteneuris

standards qui peuvent faire lobjet dun chargement et dun dchargement plusrapide. Le stockage est galement plus facile pendant les priodes de transit.

1.3.2.2 Deuxime rvolution

Cest celle du transport multimodal. Pour arriver une destination, la mar-chandise transporte dans un conteneur, empruntera successivement plusieursmoyens de transport : navire, route, rail, etc.

1.3.2.3 Troisime rvolution

Actuellement en marche, cest celle de linformatisation et de lautomatisa-tion. Linformatisation permet lacclration de la circulation des documents detransport maritime et la rduction des cots traditionnellement associs. Au-del,elle permet au transporteur de dvelopper des services personnaliss comme lesuivi des marchandises au cours du voyage.

1.4 Le transport fluvial

Principal mode de transport prindustriel, lutilisation de la voie deau sestlargement dveloppe avec la construction des grands canaux, dabords latrauxaux rivires, puis de jonction inter bassins. Cest dans ce cadre que se multiplirentles ouvrages dart : innombrables des cluses, dont certaines parfois groupes enescalier, des souterrains, ou des ponts-canaux. Dautres ouvrages, plus labors,furent conus ultrieurement, tels que les ascenseurs navires, les cluses grandgabarit, ou encore les plans inclins.

Ce rseau important (qui cumula 12 780 km au XIXe sicle, mais qui nencompte plus que 8 000 km actuellement) et relativement dense, fit lobjet dunepremire phase de modernisation au XIXe sicle dans le cadre du plan Freycinetdestin unifier lensemble des voies navigables au gabarit de 350 tonnes. partirdu dbut du sicle, le halage hippomobile fit souvent place au tracteur lectrique,avant dtre lui-mme dtrn par lintroduction de la pniche automotrice.

Dans la seconde moiti du XIXe sicle, le chemin de fer, disposant dun rseauplus dense et offrant une plus grande rapidit de transport, exera une concurrence

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

La conteneurisation 23

victorieuse sur le transport fluvial, souvent au moyen dune politique tarifaire trsagressive. Dans ce contexte, le rseau de voies navigables demeura trs largement lcart de toute modernisation dans la premire moiti du XXe sicle, au fur et mesure que simposait le monopole du chemin de fer.

Dans cette mme priode, les techniques de transport fluvial voluaient ra-pidement : accroissement du gabarit (3 000 tonnes aux normes internationales),utilisation de convois pousss, puis de barges porte-conteneurs et de navires fluvio-maritimes. Cette mutation exigeait une modernisation profonde des voies navi-gables (chenalisation des fleuves, canalisation des rivires, rduction du nombreet agrandissement notable des cluses, lvation des ponts pour respecter le tirantdair).

1.5 La conteneurisation

La conteneurisation sest dveloppe durant ces vingt dernires annes. Leconteneur est un moyen de transport qui a permis de rduire les cots et les d-lais grce la standardisation. Dans cette section, nous voyons de plus prs lesconcepts lis la conteneurisation, ses composants, ses avantages et ses inconv-nients.

1.5.1 La rvolution du conteneur

En moins de 50 ans, ce dernier sest impos comme le premier moyen dchangede biens de consommation lchelle mondiale entranant une vritable rvolutiondans les transports mondiaux. En 1960, la rotation dun cargo de ligne de 10 000tonnes de capacit, dploye sur le trajet Europe-Japon-Europe prenait cinq mois.Prs de la moiti du temps tait passe au port, avec des escales atteignant parfoisquatre ou cinq jours. En 2000, un grand porte-conteneurs offre une capacit de60 000 tonnes et boucle le mme trajet en deux mois avec des escales qui durentdune dizaine 36 heures. En mme temps, lautomatisation a fait son chemin : lecargo fonctionnait avec un quipage de 35 hommes alors quaujourdhui les porte-conteneurs nont plus besoin que dune quinzaine de marins pour naviguer. Plusrapides, plus srs, plus performants, les transports maritimes sont aussi moins

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

24 Transport Conteneuris

coteux : lacheminement dun conteneur charg de 400 tlviseurs entre Tawanet le Havre cote 3000 EUR environ. Le prix de ce transport aurait cot aumoins trois fois plus cher dans les annes 1960.

1.5.2 1956, naissance dun concept

Le transport maritime conteneuris est n sous limpulsion dun entrepreneuramricain Malcolm Mac Lean qui, en 1956, adapta 4 navires pour transporterdes remorques de camions par voie maritime. En 1956, lIdeal X reliait NewYork Houston avec 58 remorques son bord. Lexprience se rvlant positive,Mac Lean franchit vritablement le pas en conteneurs manutentionns qui sontidentiques dans leur conception.

1.5.3 Le principe de la standardisation

Un conteneur container, est une " boite " rectangulaire de dimension univer-selle : la cl de son succs rside dans sa standardisation. Les conteneurs secs dryde vingt et quarante pieds de longueur (environ six et douze mtres) sont les plusutiliss. Ils servent au transport des marchandises dites sches, conditionnes encaisses, cartons, balles, palettes, etc. Mais dautres conteneurs plus spcifiquesont t cres comme les conteneurs-citernes tank container et les plein-ciel opentop, les conteneurs frigorifiques reefer. Le conteneur standard de vingt pieds sertdunit de rfrence pour estimer les capacits dun navire et valuer les flux. Onparle alors en Equivalent Vingt Pieds-EVP Twenty Equivalent Unit-TEU ce quicorrespond un volume utile de 33 m3.

Chaque conteneur est identifi par une srie dinscriptions permanentes surses parois (propritaire, numro dimmatriculation, masse brute maximale, tareet charge utile). Presque toute la vaste gamme des marchandises transportesjadis comme marchandises non groupes peuvent faire actuellement lobjet duntransport par conteneur. Ce sont essentiellement des biens dquipement et deconsommation plus ou moins labors qui empruntent cette voie, mais le conte-neur souvre galement aux produits en vrac si ce choix prsente des avantages :logistique facilite pour les petits lots de crales, les oprations de transvasementrduites pour les produits chimiques, la possibilit de services porte porte pour

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

La conteneurisation 25

les fruits, etc.

Concluons que la spcialisation des sites de production lchelle plantaire,la recherche des moindres cots de production, la tendance dassurer un servicerapide, fiable et de qualit suprieure, de mme que lappel croissant la sous-traitance et la spcialisation des units de production ont entran une augmen-tation des changes entre usines et industries, et entre producteurs et consomma-teurs. La simplification des circuits dchanges effectus par les gestionnaires etles logisticiens passe bien souvent par lutilisation du conteneur, interchangeable(rapidit de dplacement), repositionnable, multimodal (intgration facile de tousles modes de transport). Le conteneur a rendu possible la fabrication mondiale,dont la croissance a, son tour, acclr le dveloppement du conteneur et en afait le moyen de transport prfr et un auxiliaire de la production industrielle.

1.5.4 Manutention et expditions

Deux termes dfinissent le chargement et le dchargement de la marchandisedun conteneur : lempotage et le dpotage. Tout ou presque peut se ctoyer dansun conteneur : des bouteilles dhuile avec des planches voile, des ttines debiberons avec des camras vido, etc. ; Toutefois le bon sens interdira lempo-tage de produits dangereux avec des denres alimentaires. Mais, il existe des casde contaminations moins vidents, comme un chargement de carottes contami-nes par lodeur des oignons prsents dans le mme conteneur. Lempotage desmarchandises dangereuses est quant lui soumis une rglementation stricte,contenue dans le code IMDG (International Maritime Dangerous Goods) et unesignaltique spcifique est appose sur le conteneur en fonction de la nature duproduit. Il existe deux possibilits dexpdier les marchandises : soit par conteneurcomplet Full Container Load-FCL, cest la solution la plus rpandue o toute lamarchandise appartient un mme client qui loue la bote. Soit par groupage ma-ritime Less than Container Load-LCL, cette mthode est utilise pour les petitsenvois (1 10 m3). Dans ce cas, on regroupe les lots afin dobtenir un conteneurcomplet et lempotage est effectu par la compagnie maritime ou lorganisateurde transport (transitaire).

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

26 Transport Conteneuris

1.5.5 Les oprations dans un terminal conteneurs

Les oprations de manutention se ralisent au terminal conteneurs (ensemblede quais et parcs de stockage spcialiss par type de marchandises). Les naviresse placent quai au regard des portiques (grues de quai pour soulever les conte-neurs). A bord du navire, les dockers dsarriment les conteneurs qui sont lis lesuns aux autres par les pices de coin durant la traverse. Le portiqueur peut alorsplacer le spreader (structure o sont fixs les verrous permettant daccrocher etde soulever le conteneur) laplomb du conteneur et commencer le dchargement.Au pied de chaque portique un homme ou un systme vido veille pour reprerlimmatriculation du conteneur et prciser sa position (rangement dans le parc destockage ou placement sur remorque ou wagon) un autre docker prsent dansun cavalier gerbeur straddle carrier qui va se charger de la manuvre.

Une fois le dchargement ralis, les manuvres sinversent pour les opra-tions de chargement. A peine quelques heures suffisent. Lvolution technologiquelie la conteneurisation a profondment modifi les conditions de travail des do-ckers : ils sont moins nombreux, mais plus spcialiss et qualifis. Les dockersprparent le matriel, participent louverture des panneaux de cale, guident lesconducteurs de portiques et pilotent les chariots lvateurs terre. Le pointeurest responsable de la gestion du parc conteneurs. Depuis son terminal informa-tique, il affecte les marchandises des emplacements prcis en fonction de leursdestinations. Il est galement charg didentifier et de contrler les conteneurs quiquittent le terminal. Le planificateur de navire ship planner est charg dorgani-ser le plan de chargement sur un navire : il doit attribuer chaque conteneur unemplacement prcis bord du navire. Il veille ce que la stabilit du navire soitrespecte. En effet, le placement des conteneurs est effectu de faon faciliterleur dchargement dans la chronologie de leurs destinations cest--dire les portsde dbarquement.

1.5.6 Les systmes dinformation

Les gigantesques progrs informatiques ont permis dacclrer et de simplifierle transit des navires et des marchandises dans les ports ; en voici deux exemplesmis en place par le port autonome de Nantes/Saint-Nazaire, le systme GIM-

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

La conteneurisation 27

NAUTE (Gestion Informatique des Mouvements des Navires Avec Utilisation desTechnologies Extranet), qui permet lensemble des intervenants (agents mari-times, capitainerie, pilotes, lamaneurs, etc.) de correspondre et dintervenir entemps rel grce au rseau informatique, remplaant le tlphone et le fax. Lesystme ADEMAR (Acclration des Expditions Maritimes) est un rseau in-formatique oprationnel au Havre depuis 1983 qui gre en temps rel toutes lesoprations administratives, douanires et logistiques concernant le passage desmarchandises par le port.

Linformatique est aussi prsente pour vrifier et seconder lhomme dans toutesles tches ncessaires sur les terminaux (contrles douaniers, positionnement desconteneurs sur les navires et les parcs de stockage, etc.). Au Havre toujours, lesystme Sycoscan des Douanes permet le contrle des conteneurs sur un terminalinformatique via un scanner plac dans un tunnel par o transitent les botesquil nest plus ncessaire douvrir pour en vrifier le contenu.

Depuis la moiti des annes 1990, les systmes Global Positionning Systems-GPS sont installs dans les terminaux conteneurs. Initialement, ils ont tutiliss pour identifier automatiquement la position des conteneurs dans la zonede stockage. Par la suite, la mise en place de Differential GPS [Ste99] est devenuencessaire tenant compte de la taille des conteneurs et de laspect de la zone destockage. Les composants dun DGPS ne sont plus installs dans les conteneursmais au sommet des quipements de transport et de stockage. La position dunconteneur est exprime en terme de coordonnes dans la zone de stockage et trans-mise lordinateur au moment de lempilement et de dpilement de ce conteneur.Des systmes alternatifs aux DGPS tels que les systmes optiques comme LaserRadar sont utiliss aussi pour reprer les conteneurs.

Des transpondeurs Transponder et des circuits lectriques sont utiliss pourguider les grues de transport et les vhicules automatiquement guids tandis queles DGPS sont utiliss pour guider les cavaliers gerbeurs automatiquement etdautres quipements de manutention.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

28 Transport Conteneuris

1.5.7 La multimodalit Multimodal Transport

Les transporteurs maritimes ont dvelopp des chanes de transport lint-rieur des continents. Le caractre dinterchangeabilit du conteneur est loriginede lessor des rseaux de transport mondiaux et des chanes de transport quiassocient le rail, la route et le fleuve au transport maritime pour concevoir untransport de bout en bout et de porte porte. Les conteneurs peuvent tre ache-mins indiffremment par camions, barges, wagons ou navires. Laccroissementdu trafic conteneuris induit un formidable dveloppement des transports de pret post-acheminement, cest dire apportant les marchandises du continent jus-quau navire de chargement et lemmenant du navire dcharg sa destinationfinale sur le continent. Le parcours terrestre est fondamental car il est le premieret le dernier maillon de la chane logistique multimodale.

La route est un lment stratgique qui prsente des avantages certains :souplesse, limitation des transferts de charge, assurance du suivi, etc. Mais lescamions ne peuvent pas transporter plus de deux EVP ou un 40 pieds en mmetemps : il en rsulte une augmentation du trafic routier et une saturation decertaines voies.

Les dessertes ferroviaires et fluviales offrent les solutions les plus adaptes pourfaire face la massification et la congestion du trafic routier. La commissioneuropenne vise tablir sur le territoire communautaire des corridors de fretferroviaires freeways pour faciliter la desserte des continents : ce sont des voiesddies aux transports de marchandises en liaison avec lutilisation des trains-blocs et des convois de trains de conteneurs qui sillonnent lEurope. Aux Etats-Unis, les trains-blocs double stacks (conteneurs sur deux tages) peuvent atteindreune longueur de cinq kilomtres et relient la cte est la cte ouest constituantun vritable " pont terrestre " ou " pont ferroviaire ".

Aujourdhui, le souci dun dveloppement durable largit considrablement,quand cela est possible, la place du fluvio-maritime dans la circulation des conte-neurs lintrieur des continents. Les conteneurs sont empils sur plusieurs ni-veaux sur des barges qui assurent des liaisons entre les ports maritimes et lesports fluviaux, voir entre les ports et les usines et dpts quand ils sont localissle long de la voie deau.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

La conteneurisation 29

Le cabotage (transport ctier) repose sur les navires nourriciers feeders, quirelient les ports moyens aux ports principaux et aux hubs o les navires-mresfont escale. Les feeders alimentent ainsi les navires transocaniques en conteneurset redistribuent les cargaisons dans les plus petits les ports de ces mmes grandsnavires. Cette organisation de collecte et de redistribution des marchandises creun vritable rseau mondial de transport et de distribution, complt par lescorridors de fret ferroviaires et les autoroutes continentales.

1.5.8 Avantages et Inconvnients de la conteneurisation

Le dplacement des marchandises par conteneurs a plusieurs avantages parrapport au transport de marchandises non groupes. Le conteneur favorise lauto-matisation de plusieurs oprations de manutention, ce qui acclre le chargementet le dchargement et autorise un transfert plus rapide dun mode de transport un autre. En outre, le conteneur protge les marchandises des intempries et duchapardage et la manutention, devenant plus simple, se traduit par une quantitmoindre de dommages.

Les avantages inhrents aux conteneurs ont pu tre raliss grce aux capi-taux considrables que les exploitants ont investis en navires, terminaux, grues,wagons deux niveaux de chargement et autres installations ou quipements demanutention spcialiss.

Toutefois, les oprateurs, les ports et les autorits de tutelle faisant en sortede sadapter aux contraintes de la logistique moderne, se heurtent un certainnombre de limites de la conteneurisation. Les contraintes physiques aussi biendans les transports courts que sur longues distances ncessitent un minimum deprotection prventive. En effet, les tempratures leves ainsi que la ventilationrduite dans le conteneur entranent trs souvent de lourds dommages si lonny prend pas garde. La temprature provoque la dessiccation des marchandises(cacao) ou des emballages (carton, bois darrimage ou de calage, bois de palette,etc.). La vapeur deau, une fois libre, se condense dans les zones les plus froidesdu conteneur et en gnral lors de lalternance jour-nuit. Cest alors une pluiequi semble retomber sur les marchandises, avec des dgts irrmdiables faciles imaginer.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

30 Transport Conteneuris

1.6 Les ports conteneuriss

Dans le transport par voies navigables quest le couple chemin de fer-navire vapeur, cest le port, lieu dchanges privilgi, qui constitue le rouage essentiel,avec ses immenses triages dans les zones portuaires et son lacis de voies ferres surtous les quais, entre les diffrents bassins. Le dveloppement des ports est dautantplus important que la machine vapeur ait permis un trs grand accroissementde la taille des navires, donc de leur capacit. De nombreux bassins sont creussdans les ports qui sagrandissent en raison de la croissance du trafic. Ces bassins,qui sont difis partir de 1830, offrent des dimensions inconnues jusqualors(de lordre du kilomtre en longueur). Ils constituent les premiers lments despaysages portuaires traditionnels (grues, entrepts, marchandises en vrac sur lesquais, voies ferres) en continuit directe avec la ville portuaire. Dans les mers forte mare, les bassins sont accessibles mare haute grce des cluses : cesont les bassins flot. Dans les mers sans mares, ce sont des darses. Il sen estsuivi la dissociation de la ville portuaire traditionnelle et du port proprement dit,cest--dire de la fonction technique de chargement et dchargement des navires,maintenance et avitaillement, dune part, et de la fonction commerciale, dautrepart. Cette volution sest traduite par le glissement du port vers laval par rap-port la ville et par le passage de la notion de port celle de terminal spcialis,cest--dire un simple poste technique de manutention, souvent totalement auto-matis, dpourvu de toute urbanisation (Antifer, par exemple, pour Le Havre).Comme pour les rseaux linaires, la densit des ports ou des terminaux apparattrs ingale selon les rgions du monde. Il en est de mme du niveau de dvelop-pement technique. Les deux zones du globe les plus densment pourvues en portssont lEurope : de la Baltique la Mditerrane, et lAsie du sud-est, la secondeprsentant cependant un niveau gnral de dveloppement technique moindre quela premire, sauf au Japon et dans les autres ports de premier niveau.

Un port moderne est un ensemble de terminaux spcialiss. Les plus grands(voir tableau 3.1) [Por06] jouent le rle de plate-forme de concentration / clate-ment de dimension continentale.

Ainsi, les ports principaux main ports tels que : Los Angeles, Rotterdam,Hong Kong, etc. ont-ils merg. Dans certains, les hubs, les conteneurs ne font

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Conclusion 31

Tab. 1.1 Les 10 premiers ports conteneurs dans le monde en 2006Ports Trafic en milliers dEVP

Singapour 24 792Hong Kong 23 234Shanghai 21 710Shenzhen 18 468Pusan 12 030

Kaoshiung 9 774Rotterdam 9 690

Dubai 8 923Hamburg 8 861

Los Angeles 8 469

que transiter entre les grands navires mres est-ouest et les relais nord-sud ou entreles navires mres et les feeders rgionaux. Parmi les hubs les plus importants, ontrouve Algsiras (Espagne), Gioia Tauro (Italie) et Kingston (Jamaque). Ainsi,un conteneur qui doit se rendre de Tokyo Abidjan empruntera un navire mrede 5000 EVP reliant le Japon lEurope du nord avec une escale Algsiras (prsde Gibraltar) o le conteneur sera dbarqu pour tre aussitt rembarqu surun navire de 1500 EVP qui descend des ports de la mer du nord vers lAfriquede louest. Le trajet Tokyo / Abidjan aura dur une quarantaine de jours. Toutelorganisation portuaire est donc trs hirarchise et repose autant sur un petitnombre de grands ports mondiaux que sur un nombre plus important de portsmoyens.

1.7 Conclusion

Nous avons tent dans ce chapitre introductif de dcrire le cadre gnral denotre travail et de connatre au mieux les nouveaux concepts sy posant, et cedans le but de contourner et de matriser la problmatique ci tudie.

Comme nous le constatons, la conteneurisation et la logistique des termi-naux conteneurs mettent en questions plusieurs problmes de dcisions ma-

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

32 Transport Conteneuris

nant des diffrentes oprations effectues au sein dun terminal conteneurs.Ces problmes peuvent tre classs parmi les problmes de transport et dordon-nancement [BGAB83] comme par exemple le problme de tournes de vhicules[TV02]et les problmes daffectation qui sont largement abords dans la littra-ture. Dans le chapitre suivant, nous prsentons un tat de lart exhaustif de cesproblmes. Nous nous penchons sur le Problme de Stockage de Conteneurs-PSCauquel nous nous intressons dans cette thse.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Chapitre 2

Problme de Stockage deConteneurs (PSC)

2.1 Introduction

De nos jours, les navires de conteneurs sont dchargs et chargs dans delarges terminaux conteneurs. La figure 2.1 illustre le processus de dchargementet de chargement dans un terminal conteneurs. Ce processus peut tre divisen oprations ou activits qui vont tre prsentes en dtail dans les sectionssuivantes. Lorsquun navire arrive au port, des portiques ou des grues de quaisQuay Cranes-QCs dchargent les conteneurs en import par ce navire. Puis, cesconteneurs sont transfrs de ces grues des vhicules se dplaant entre le navireet la zone de stockage des conteneurs. Cette zone est constitue dun nombre debaies o les conteneurs peuvent tre stocks en piles pendant une certaine priode.Des quipements comme les grues ou les cavaliers gerbeurs straddle carriers sontaffects ces baies.

Un cavalier gerbeur peut la fois transporter des conteneurs et les stockerdans une zone de stockage. Il est possible aussi dutiliser des vhicules ddis autransport des conteneurs. Si un vhicule atteint la zone de stockage, il dpose sacharge ou bien une grue de stockage dcharge le conteneur et le stocke dans lazone. Aprs une certaine priode, les conteneurs sont retrouvs par les grues dansla zone de stockage pour tre conduits sur des vhicules vers diffrents moyens de

33

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

34 Problme de Stockage de Conteneurs (PSC)

transport : barges, navires, trains ou camions selon diffrents modes de transport :voie navigable, voie ferroviaire ou voie terrestre. Pour le chargement des conte-neurs en export sur un navire, ces activits sont excutes dans lordre inverse.La plupart des terminaux utilisent des quipements manuellement guids : les ca-valiers gerbeurs straddle carriers, les grues cranes et les systmes multi-remorquemulti-trailer systems. Toutefois, quelques terminaux sont automatiss. Dans detels terminaux, deux diffrents types de vhicules automatiques sont utiliss pouracheminer les conteneurs dun mode de transport un autre : des vhicules auto-matiquement guids Automated Guided Vehicles-AGVs ayant besoin dune gruepour charger et dcharger un conteneur, et des vhicules lvateurs automatiquesAutomated Lifting Vehicles-ALVs capables dlever un conteneur de manire au-tonome. La comparaison et la dcision du choix entre ces deux types dquipe-ments sont discutes dans [VH04]. De plus, le processus dempilement peut treeffectu automatiquement via des grues dempilement automatiques.

Lvolution du transport conteneuris incite au dveloppement des terminaux conteneurs, autant de la logistique des conteneurs que des quipements tech-niques de manutention. Une concurrence entre les ports et un dveloppementcontinuel de lactivit portuaire, particulirement entre les plus proches gogra-phiquement, a accompagn cette volution. En consquence, lobjectif global estla minimisation du temps pass par un navire dans le port tenant compte desdiffrentes oprations se droulant dans un port.

Lobjectif de ce chapitre est de fournir une classification de ces oprations.En se basant sur cette classification, nous prsentons une revue de littraturedes travaux inhrents qui dcrivent diffrentes approches incluant des mthodesexactes, des mthodes heuristiques ainsi que des approches bases sur des simu-lations, centralises et distribues.

2.2 Processus dans un terminal Conteneurs

Dans ce qui suit, nous allons parcourir les diffrentes activits rencontresdans un terminal conteneurs 2.1)allant du dchargement dune barge ou dunnavire (camion ou train) jusqu leur chargement sur camion ou train (barge ounavire) pour les conteneurs en import (en export). Nous nous intressons aussi

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Processus dans un terminal Conteneurs 35

aux diffrents quipements de manutention qui leur sont associs, et discuterdes diffrents problmes qui en dcoulent. Nous allons aussi survoler quelquestravaux inhrents incluant les mthodes exactes, les mthodes heuristiques et lesapproches bases sur des simulations en se rfrant [VK03, SVS04, GG06].

2.2.1 Planification de navires

Le processus de planification de navires se compose de trois sous-oprations :lallocation des postes quai, larrimage de conteneurs et lallocation des portiques(ou grues de quais).

2.2.1.1 Allocation des postes quai Berth Allocation

La stratgie Premier Arriv Premier Servi First In First Out-FIFO sembletre une manire rationnelle daffecter les navires arrivant aux postes quai dis-ponibles, mais elle peut tre inefficace dans le cas o le temps de manipulationdes navires dpendrait des postes quai correspondant. En effet, dans le cadre demanipulation des conteneurs, une politique dempilement de conteneurs consis-

Fig. 2.1 Succession des oprations dans un terminal conteneurs

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

36 Problme de Stockage de Conteneurs (PSC)

tant empiler les conteneurs charger dans un mme navire lintrieur dunezone de stockage ddie.

En consquence, il est prfrable que les postes quai soient proches de cettezone. Lors de lallocation dun navire un poste quai, on doit tenir comptede la disponibilit des postes quai et des grues responsables du chargement etdu dchargement du navire. Diffrents travaux de recherche traite ce problmenomm : le problme dallocation de postes quai Berth Allocation Problem-BAP.

Le problme dallocation de postes quai, dit encore le problme daffectationdes navires aux postes quai, a pour objectif de minimiser la somme du tempsdattente et du temps de manutention des navires. Chaque poste quai ne peutsupporter quun seul navire la fois, et le temps de manipulation dun naviredpend du poste quai associ.

Dans [LM01], les auteurs prsentent un modle de rseaux de files dattente etune tude exprimentale pour la simulation de larrive, lallocation et le dpartde navires.

Dans [INP01], Imai et al. considrent plusieurs versions relatives ce problmedont les plus tudies : le BAP statique et le BAP dynamique : dans la premireversion, il est suppos que tous les navires arrivent dj au port au dbut delhorizon de planification. Dans ce cas, il nexiste pas de temps morts entre lesnavires manipuls dans un certain poste quai. Le problme ainsi dfini peuttre formul par un problme daffectation deux dimensions pouvant tre rsoluen un temps polynomial. Imai et al. considrent le BAP statique objectifsmultiples : la minimisation de la somme du temps dattente et de manipulationdes navires et la minimisation de linsatisfaction du navire dpendant de lordrede laffectation. Notons que lordre optimal daffectation, tenant compte du tempsdattente et du temps de manutention, peut ne pas correspondre lordre danslequel les navires sont arrivs.

Le BAP dynamique suppose que les navires arrivent tout au long de la priodede planification, donc il peut y avoir un temps dinactivit entre deux naviresconscutifs desservis dans un poste quai. Le problme ainsi dfini ne peut pasalors tre rsolu en un temps polynomial. Imai et al. [INP01] considrent aussi leBAP dynamique o il nest permis de manipule quun seul navire la fois tant quela longueur totale des navires est infrieure celle du poste quai considr. En

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Processus dans un terminal Conteneurs 37

outre, ils incluent la contrainte additionnelle quun navire ne peut tre servi dansun poste quai que si la profondeur de leau ncessaire pour sa mobilisation draftest infrieure la profondeur de leau au poste quai. [Lim98] tudie ce problmecomme tant une version particulire du problme du paquetage bin-packing deux dimensions.

Dans [PK01] tudient lallocation des postes quai en supposant que les na-vires sont proches de la zone o les conteneurs associs sont empils, et visent minimiser le temps turnaround des navires. [KM03] propose un modle de pro-grammation linaire en nombres entiers mixte Mixed Integer linear Programming-MIP pour formuler le BAP, et appliquent lalgorithme de recuit simul pour lersoudre. Les rsultats exprimentaux ont montr que les solutions retrouves parle recuit simul sont similaires aux solutions optimales retrouves par le modleMIP.

Dans [GC04], Guan et Cheung proposent une procdure se basant sur un arbrede recherche et des heuristiques pour rsoudre de problmes de grande taille dansle but de minimiser le temps de flux total Total weighted flow time.

2.2.1.2 Arrimage de conteneurs Container Stowage

Il sagit de la planification darrimage des conteneurs dans un navire. Engnral, un navire fait escale dans un nombre de ports o les conteneurs serontchargs et dchargs. Ceux qui sont chargs sont destins un nombre de portssuccessifs tout au long la route du navire en question.

Ce problme considre laffectation des conteneurs diffrentes positions dansle navire tout en maintenant sa stabilit et en minimisant le nombre de mouve-ments inutiles ou parasites unproductive moves. Ces derniers apparaissent dansun port lorsquon y dispose de conteneurs stocks au-dessus dautres destins ce port, alors ils doivent tre dchargs et rechargs de nouveau. Le placementdes conteneurs dans le navire doit alors tre accompli de manire maintenirsa stabilit, sa torsion et sa force. videmment, les conteneurs lourds sont g-nralement stocks au fond du navire, les conteneurs lgers sont alors empilsau-dessus [KPR00]. Notons que les conteneurs de tailles diffrentes ne peuventpas tre empils les uns sur les autres.

En plus du poids et de la taille, dautres critres sont pris en considration :

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

38 Problme de Stockage de Conteneurs (PSC)

les conteneurs frigorifiques par exemple demandent une puissance lectrique exis-tant seulement dans des positions spcifiques dans le navire, certains conteneurstransportant des matriaux dangereux exigent des conditions darrimage biendtermines distinctes de celles des autres. Outre ces restrictions techniques, ladestination des conteneurs doit tre prise en compte.

Avriel et al. [APS00] se concentrent sur la planification darrimage dans le butde minimiser le nombre de mouvements unproductifs. Ils proposent un modle deprogrammation linaire binaire.

Dans [WR00], les auteurs divisent ce problme en deux sous-problmes selonun niveau de planification stratgique et tactique. Ils utilisent la mthode Branchand Bound B&B pour rsoudre le problme daffectation de conteneurs une zonedans le navire, et la mthode de recherche tabou pour dterminer un plan dtailldaffectation des conteneurs des emplacements spcifiques dans le navire. Debons rsultats sont obtenus en un temps raisonnable.

Les deux travaux [RW02, WRW01] prsentent un algorithme gntique pourgnrer automatiquement des plans darrimage stratgiques.

La simulation et loptimisation en ligne sont considres dans [Win00]et [SWZ01].Les temps dattente des grues et la congestion des quipements de transport sontminimiss afin dviter la rduction de la productivit. Le travail de [SWZ01]prsente un modle MIP pour modliser un ordonnancement juste temps Just-in-time JIT dune portique, et des mthodes exactes et heuristiques pour la r-solution.

A un niveau plus dtaill, laffectation des navires aux postes quai peut treaccomplie tenant compte de laffectation de portiques aux navires. Certainement,le nombre de portiques affectes un navire influe le temps de manipulation dece dernier. Ceci donne naissance au problme dordonnancement des grues Cranescheduling problem qui a t tudi par [Dag89].

[Bis03] tudie ce problme comme tant une composante dun plus grand pro-blme appelMultiple-crane-constrained Vehicle Scheduling and Location problem-MVSL. Il dveloppe une mthode heuristique pour minimiser le temps total passpar un ensemble de navires aux quais.

Ce problme est aussi class en deux versions : le problme statique o unnombre de portiques doit servir un nombre de navires tout en minimisant les

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Processus dans un terminal Conteneurs 39

cots associs au retard des navires, en supposant que tous les navires manipulersoient arrivs au poste quai linstant zro.

Le problme dordonnancement statique des grues peut tre gnralis afin desupporter le cas de navires arrivant diffrentes dates et les contraintes de capa-cit relatives aux postes quai : cest un problme dordonnancement dynamiquedes grues.

2.2.2 Transport sur le quai Quay Transport

Aprs une observation des diffrents terminaux conteneurs travers le mondeentier, on a pu constater que trois systmes de manipulation pour le transportsur le quai sont les plus usits :

1. Le premier systme utilise les grues dempilement stacking cranes pour larcupration des conteneurs empils dans la zone de stockage. Ces gruespeuvent tre soit rubber-tired ou rail-mounted. Selon le premier mode, lesgrues peuvent gnralement se dplacer dune range de piles une autre,et ce suivant lemplacement des conteneurs destins un navire bien d-termin. Aprs avoir retrouv le conteneur recherch, la grue dempilementle charge sur un vhicule transporteur, gnralement un wagon transpor-teur de terminal truck terminal ou un vhicule guid automatis AutomatedGuided Vehicle-AGV, capable de transporter un ou deux conteneurs. Toute-fois, quelques terminaux utilisent les systmes multi-remorque multi-trailercapable de transporter 10 TEU. Le vhicule du terminal conduisent lesconteneurs vers la grue de quai approprie, qui se charge de leur soulve-ment. Dans la plupart des terminaux, les grues dempilement et les wagonstransporteurs du terminal sont manuellement dirigs (plusieurs terminaux Rotterdam possdent un quipement automatis).

2. Un systme alternatif pour le transport des conteneurs dans un quai consiste utiliser des cavaliers gerbeurs straddle carriers ou yard machines. Cesderniers combinent les proprits dune grue et celles dun vhicule. En effet,ils sont capables de retrouver les conteneurs recherchs et de les amener versles portiques. tant donn que ces vhicules peuvent eux-mmes charger etdcharger les conteneurs, ils nont pas besoin dattendre une grue condition

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

40 Problme de Stockage de Conteneurs (PSC)

quil existe une zone tampon de capacit suffisante. En vue de ces diffrentsarguments, les cavaliers gerbeurs semblent tre une composante prconisede lquipement dun terminal.Cependant, ils sont trop coteux et beaucoup plus incertains quun systmealliant des grues dempilement et des vhicules de terminaux. De plus, lescavaliers gerbeurs ncessitent plus despace pour pouvoir fonctionner.

3. Le troisime systme possible nest plus utilis : il consiste empiler tousles conteneurs sur des chssis. Ensuite, seuls les wagons transporteurs duterminal sont utiliss pour conduire les remorques aux portiques. Ce sys-tme a lavantage de pouvoir accder directement chaque conteneur ce quifacilite le fonctionnement dans un terminal, mais son inconvnient majeurest de requrir un grand espace de stockage puisque chaque conteneur estempil sur un chssis.

Le choix entre ces trois alternatives est un problme typiquement stratgique.Lun des paramtres intervenant dans ce choix, est celui de lemplacement gogra-phique du terminal. Par exemple, les terminaux asiatiques (Hong Kong et Singa-pour) utilisent le premier systme vu que les grues dempilement permettent unempilement plus lev (atteignant 6 au port de Busan au Japon), en comparaisonau deuxime systme, qui est limit un empilement de 3 4 conteneurs (exp. :port de Rads en Tunisie). Dautre part, si lespace de stockage est largementvacant, par exemple dans les ports des USA, un systme utilisant des remorquesest de prdilection pour la facilit relative de faire fonctionner un tel systme.

En Europe, la situation est diffrente : bien que lempilement est relativementpeu lev (2 4 conteneurs), les cavaliers gerbeurs (Hambourg, Bremen, Rot-terdam et Antwerp), les grues dempilement automatiques Automated StackingCrane -ASCs et les vhicules automatiques guids Automated Guided VehiclesAGVs (Rotterdam) sont tous utiliss.

En vue de comparer et de dcider quel systme il faut utiliser, Vis et al.[VKS01] ont procd une tude par simulation. Ils prtendent quen moyenne,le nombre de cavaliers gerbeurs requis uniquement pour le transport des conte-neurs et non pas pour lempilement est environ 30% de moins que le nombre devhicules automatiques guids requis. Cette constatation encourage lutilisationdes cavaliers gerbeurs, mais tenant compte dautres paramtres tels que le cot

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Processus dans un terminal Conteneurs 41

et la fiabilit, ces quipements seront moins encourags.

Dans ce contexte, le travail de (Yim et al.) traite un problme peu abord,cest le problme daffectation des conteneurs dans un port fluvial, quils appellentaussi problme de rotation de barges et daffectation de conteneurs. Il sagit deminimiser le nombre de barges utilises et de dterminer sur quelles barges lesconteneurs seront chargs tout en satisfaisant un ensemble de contraintes addi-tionnelles. Une fois que les conteneurs affects aux barges retenues, le plan dechargement de chacune delles peut tre dtermin en rsolvant le problme dar-rimage stowage problem voqu dans la section 2.2.2. Ce problme est clairementreli au problme de rotation des barges. Yim et al. Dveloppent un modle deprogrammation linaire en nombres entiers -PLNE pour modliser ce problme.

Dans ce qui suit, nous allons discuter des divers problmes dordonnancementdrivs du problme principal de transport sur le quai. Ces problmes paraissentau niveau de dcision oprationnel. Rappelons que le but est doptimiser lutilisa-tion de lquipement disponible, et que lobjectif global est de minimiser le tempspass par les navires dans le port.

2.2.3 Ordonnancement des quipements de manutention

Plusieurs travaux sintressent au problme dordonnancement des quipe-ments de manutention. Ces travaux se distinguent selon le type des quipementsde manutention ordonnancer. Nous pouvons les classer comme suit :

Ordonnancement des Grues dEmpilement Scheduling of Stacking Cranes. Ordonnancement des Vhicules Automatiques Guids scheduling of AGVs. Contrle du trafic des Vhicules automatiques guids trafic Control of AGVs. Ordonnancement intgr des grues dempilement et des vhicules automa-

tiques guids Integrated Scheduling of Stacking Cranes and AGVs. Ordonnancement des cavaliers gerbeurs Straddle Carriers.

Un rsum de ces travaux est donn dans le tableau 2.1

En outre, le principe de fonctionnement ainsi quune tude comparative desperformances des quipements de manutention dans un terminal conteneurs estreprsente dans la figure 2.2 extraite de [Equ].

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

42 Problme de Stockage de Conteneurs (PSC)

Le problme de stockage de conteneurs auquel nous nous intressons constitueaussi un problme de dcision reprsentant lactivit de stockage de conteneurs,composante prpondrante de tout le processus de gestion dun port. En cons-

Tab. 2.1 Tableau rcapitulatif des algorithmes dordonnancement des quipe-ments de manutention

Classe de Problmes Rfrence Problme tudi Caractristiques de la solution

Ordonnancement deGrues dempilement

[KK98] Optimisation des tour-nes dune seule gruedempilement

*Classement des conteneurs en catgories(taille, poids, port de destination, etc.).*Plusieurs baies peuvent contenir des conte-neurs de mme catgorie.

[MJLZ+00] Redistribution desgrues dempilement detype rubber-tired

*Un terminal avec des zones de stockage aux-quelles est associe une charge de travail lorsde chaque dplacement.*Une grue dempilement est autorise se d-placer dun bloc un autre.*Minimiser la quantit de la charge de travail.

[ZWLL02] Optimisation de la pro-ductivit dun type degrues dempilement deconteneurs : les RubberTyred Gantry Cranes-RTGs

*Retrouver les dates et les itinraires de dpla-cement de ces grues de manire minimiser lacharge de travail totale retarde dans une zonede stockage.*Formulation via un modle de programma-tion entire mixte.*Rsolution par une relaxation lagrangienne.

Ordonnancement dedes AGVs

[KB98] Distribution dAGVs *Pour chaque conteneur, introduire des datesassocies des vnements event times quidoivent tre satisfaits (dates exactes de char-gement /dchargement de chaque conteneur).*Rduire le problme un problme daffecta-tion.

[dM00] Distribution dAGVs *Etudier des rgles de distribution[MW01b] Distribution dAGVs *Ajustement des rgles de distribution dans le

cas dun port conteneuris automatique[VKRP01] Dtermination du

nombre dAGVs re-quis dans un terminal conteneurs semi-automatique

*Les conteneurs sont disponibles des instantsconnus court terme et changent constam-ment au cours du temps.

Ordonnancement desdiffrents quipementsde manutention

[KKHK04] Ordonnancement desoprateurs operator-scheduling problem

*Affectation des oprateurs des intervalles detemps associs lutilisation des quipements.*Formulation et rsolution via une techniquede satisfaction de contraintes (le temps dex-ploitation, le temps darrt, les prfrences desoprateurs).

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Processus dans un terminal Conteneurs 43

Contrle des AGVs

Evers et Kop-pers (1996)

*Flexibilit de reprsentation du systme detransport.*Peu de communication ncessaire pour lecontrle des AGVs (les AGVs communiquentseulement avec des zones locales).*Dates de dplacement des AGVs stochas-tiques.*Assurer que les AGVs se placent dans laqueue dans le bon ordre.

Duinkerken etOttjes (2000)

*Etudes par simulation tendues*Evaluer la performance dun tel systme sousun contrle intelligent du trafic.

Ordonnancement int-gr des grues dempile-ment et des AGVs

Meersmans etal. (2001)

Planification de lacti-vit des grues de quai,des grues dempilementet des AGVs de ma-nire intgre

*Modles prenant en considration la typologiedu terminal : cas o les AGVs passeraient parun point commun alors lordre dans lequel ilscommencent soulever leur conteneur suivant,dtermine compltement la partie qui reste duplan.Cas contraire : formulation base sur MIP d-rivant des classes dingalits valides.

Ordonnancemen tdescavaliers gerbeurs

[BRSV00] Distribution des cava-liers gerbeurs

*Algorithme gntique pour minimiser les re-tards de transferts aux portiques.*Une affectation statique puis une affectationdynamique des cavaliers gerbeurs (dans le casde leur collision).*Rsultats exprimentaux montrant quune af-fectation dynamique peut accrotre considra-blement la productivit.

[Win00] Combinaison de la pla-nification de larrimagedun navire avec lor-donnancement des ca-valiers gerbeurs

*Classement des conteneurs charger, puis af-fectation dune squence des catgories char-ger chaque grue de quai.*Choix libre dun conteneur spcifique durantle chargement dun navire.

[KP99] Optimisation destransferts de conte-neurs par les cavaliersgerbeurs

*Minimisation la dure passe par les naviresdans le port. Proposer des modles qui traitentles remaniements des conteneurs en introdui-sant les dates de setup.

quence, nous y attardons et consacrons toute la suite de ce chapitre.

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

44 Problme de Stockage de Conteneurs (PSC)

Fig. 2.2 Types dquipements de manutention

2.3 Problme de Stockage de Conteneurs -PSC

Container Stacking Problem

Rcemment, vu la grande concurrence entre les ports, lamlioration du ser-vice clientle est devenu un problme important pour un port de terminaux conteneurs. Lune des mesures de performance du service clientle est le tempstotal pass par les navires aux quais dun port berthing time ou throughout time.Ce temps est compos en majeur partie du temps de chargement et de dchar-gement des conteneurs. Dans le but de rduire le temps de chargement, il estncessaire de choisir des emplacements de stockage pour les conteneurs en importou en export de manire pouvoir tre chargs efficacement dans le navire, lecamion, ou le wagon associ.

Dans cette section, nous nous focalisons sur lopration alliant transborde-ment, empilement et dpilement des conteneurs. Cette opration constitue unproblme reprsentant un maillon fort important de la chane des problmes dedcision rencontrs dans un terminal conteneurs : cest le Problme de Stockagede Conteneurs Container Stacking Problem ou Container Handling Problem. Ce

tel-0

0366

467,

ver

sion

1 - 7

Mar

200

9

Problme de Stockage de Conteneurs -PSC Container Stacking Problem 45

problme sera dsign dans la suite par lacronyme PSC . Le processus de sto-cker et de retrouver les conteneurs doit tre excut de manire assurer unbon droulement du reste des oprations ayant lieu dans le terminal. Lefficacitde ce processus dpend entre autres du taux doccupation des zones de stockageainsi que des stratgies dfinies pour le stockage et la recherche des conteneursen import ou en export.

Commenons par introduire une notion de base rencontre dans la ralit delactivit de stockage de conteneurs, et adopte tout au long de notre travail : Lapile (appele aussi colonne).

Dans notre contexte, la pile permet aux activits diverses de transport de seproduire indpendemment lune de lautre. Si aucune pile nexiste, alors chaquearrive de navire (ou autre mode) devrait tre suivie directement par la dchargeaux vhicules transporteurs. Ceci constitue une opration logistique complexe cartoutes les arrives devraient tre coordonnes. Toutes ces contraintes causeraientbeaucoup de congestion et seraient susceptibles aux retards invitables.

Il existe diffrents systmes dempilement. Dans notre cadre, nous considronslempilement en piles dans une zone de stockage. En fat, cest le systme adoptdans la plupart des terminaux conteneurs.

Quelques conteneurs comme par exemple les conteneurs frigorifiques reefersexigent des emplaceme