Optimisation du traitement des conteneurs au niveaud’une plateforme ferroviaire

Loubna BenabbouEcole Mohammadia

d’IngénieursRabat, Maroc

benabbou@emi.ac.ma

Najiba SbihiEcole Mohammadia

d’IngénieursRabat, Maroc

sbihi@emi.ac.ma

Sanae KouismiEcole Mohammadia

d’IngénieursRabat, Maroc

sanaekouismi@gmail.com

ABSTRACTPar rapport au fret provenant du port Tanger/Med a desti-nation de Casablanca, l’Office National de Chemins de Fer(ONCF) fait face a la concurrence des feeders, d’ou l’interetd’augmenter son offre de service au niveau de la plateformeMITA (port sec a Casablanca). Dans ce sens, l’objectif decet article est de maximiser le nombre de trains que MITApeut accueillir et traiter par jour, ou de maniere equivalentede minimiser la duree de traitement des trains.

KeywordsOptimisation, ordonnancement, conteneurs

1. INTRODUCTIONLe transport de conteneurs entre le port de Tanger Med etCasablanca est assure par camions, par train ou encore pardes petits bateaux (feeders). Actuellement, l’ONCF est con-fronte a la concurrence des feeders en termes de capacite detransport.Pour faire face a cette concurrence, l’ONCF cherche aa aug-menter sa capacite de transport sur cet axe en maximisantle nombre de trains que peut accueillir la plateforme MITA.Le terminal MITA est directement connecte au reseau fer-roviaire national et dispose de deux voies ferroviaires d’unelongueur totale de 1,4 km. Un conteneur arrivant aa MITApar train en provenance de Tanger Med passe par plusieursetapes: dechargement, transport et placement au moyende grues dans les aires de stockage. L’ordonnancement desoperations de manutention est par consequent crucial dansla gestion de la plateforme.

2. REVUE DE LA LITTÉRATUREE. Kozan [3] a etudie le probleme de minimisation de laduree totale de traitement des conteneurs dans un termi-nal depuis son arrivee jusqu’a son depart (ce temps etantegal a la somme du temps de manutention et du temps

d’acheminement ou de deplacement des conteneurs dans leterminal). Pour resoudre ce probleme, il a utilise le pro-gramme GAMS (General Algebraic Modeling System).C. Zhang et al.[5] ont determine les dates et les trajetsdes grues de facon a minimiser la charge totale de travaildans une zone de stockage. Les auteurs ont montre la NP-completude du probleme et ont developpe une approche detype branch and bound ainsi qu’une metaheuristique basesur le recuit simule.Y.Zhu et A.Lim [6] se sont interesses aux problemes d’ordo-nnancement des engins de manutention et des conteneursafin d’optimiser la productivite des RTG (Rubber TyredGantry Cranes).K. H. Kim et al.[2] ont presente un probleme d’ordonnance-ment des moyens de manutention en affectant des opera-tions a des intervalles de temps associes a l’utilisation de cesmoyens. Le terminal etudie contient trois types de moyensde manutention : les portiques a conteneurs, les camionscourts et les portiques de transfert. Afin d’utiliser ces equipe-

ments, les operateurs sont regroupes en equipes. Les au-teurs ont considere que le probleme d’ordonnancement demain d’œuvre englobe trois sous-problemes, le premier prob-leme est de programmer les listes des operateurs, dont lestravaux sont determines. Le second calcule le temps detraitement des equipements et le troisieme uonsiste a at-tribuer un operateur pour chaque piece d’equipement aucours de chaque intervalle de temps d’exploitation prevupour l’equipement. Le probleme est formule et resolu a l’aided’une technique de satisfaction de contraintes : le tempsd’exploitation, le temps d’arret, la qualification du fonction-nement d’un equipement, et les preferences des operateurs.Lee et al.[4] ont travaille sur l’ordonnancement des camionsde transport ainsi que sur l’allocation des zones de stockageaux conteneurs, l’objectif etant de minimiser les retards etle temps total de transport des camions pour les deux proce-dures : le chargement et le dechargement depuis et vers lenavire. Les auteurs ont resolu le probleme a l’aide de HIA(The Hybrid Insertion Algorithm).A.Galuszka et al. [1] ont modelise et analyse le probleme dedeplacement des conteneurs par les RSs dans un terminalde capacite limite, qui as pour objectif la determination desbaies des conteneurs apres le dechargement. L’heuristiqueproposee permet de trouver un plan de deplacement des RSset placer le conteneur vers sa destination tout en minimisantle nombre des operations de manutention.

3. FORMULATION MATHÉMATIQUEIl s’agit de minimiser la duree de traitement d’un train enattente sur le terminal ferroviaire du port sec MITA. Cetraitement comprend le dechargement, le transport et leplacement de tous les conteneurs a bord du train vers lesaires de stockage a l’aide des grues disponibles. Cela revienta affecter de maniere optimale les conteneurs aux grues etaux aires de stockage. Apres l’etude de l’existant sur le ter-rain, nous avons considere les hypotheses suivantes :

• Tous les conteneurs ont la meme duree de traitement;

• Le traitement des conteneurs est limite par la nondisponibilite des grues dans quelques periodes a traversl’horizon; MITA dispose de neuf grues;

• Une grue peut transporter un seul conteneur a la fois;

• Toutes les operations (dechargement et stockage)sonttraitees par des grues de type reach-stacker ;

• Une aire de stockage dispose d’une capacite limitee(en termes de nombre de conteneurs), MITA disposede quatre aires de stockage ;

• Le traitement d’un conteneur est non-preemptif :lorsqu’une grue commence le traitement d’un conteneur,elle ne peut s’arreter qu’apres le placement de ce con-teneur dans l’aire de stockage qui lui est affectee;

3.1 Paramètres• N : nombre total de conteneurs a decharger;

• l: nombre de grues disponibles;

• m : nombre d’aires de stockage;

• k : indice conteneur;

• i : indice grue;

• j : indice aire de stockage;

• τ : duree de traitement d’un conteneur par une gruevers une aire de stockage ;

• τ= τ+retour;

• cap(j) : capacite residuelle (en termes du nombre deconteneurs) de l’aire de stockage ;

• G(i) : duree de disponibilite de la grue i;

3.2 Variables de décision• Ck : variable entiere qui represente la date de fin de

traitement du conteneur k(1 ≤ k ≤ N);

• Cmax: variable entiere qui represente la date de fin dutraitement de tous les conteneurs;

• yijk : variable binaire egale a 1 si et seulement si leconteneur k est affecte a la grue i (1 ≤ i ≤ l) et a l’airede stockage j (1 ≤ j ≤ m);

• rik : variable binaire egale a 1 si et seulement si leconteneur k est affecte a la grue i;

• zjk : variable binaire egale a 1 si et seulement si leconteneur k est affecte a l’aire de stockage j;

• gk′ki′i : variable binaire egale a 1 si et seulement si leconteneur k′ est affecte a la grue i′ et le conteneur k ala grue i;

• sk′kj′j : variable binaire egale a 1 si et seulement sile conteneur k′ est affecte a l’aire de stockage j′ et leconteneur k a l’aire de stockage j;

• pk′k : variable binaire egale a 1 si et seulement si letraitement du conteneur k ne peut commencer qu’apresle traitement du conteneur k′;

3.3 Programme mathématiqueMinimiser :

Cmax

Sous contraintes :

Cmax ≥ ck, ∀(1 ≤ k ≤ N) (1)

ck −l∑

i=1

m∑j=1

τyijk ≥ 0, ∀(1 ≤ k ≤ N) (2)

l∑i=1

rik = 1, ∀(1 ≤ k ≤ N) (3)

m∑j=1

zjk = 1, ∀(1 ≤ k ≤ N) (4)

l∑i=1

m∑j=1

N∑k=1

yijk = N (5)

rik + zjk − 1 ≤ yijk ≤1

2(rik + zjk), (6)

∀(1 ≤ i ≤ l), ∀(1 ≤ j ≤ m), ∀(1 ≤ k ≤ N)

ri′k′ + rik − 1 ≤ gk′ki′i ≤1

2(ri′k′ + rik), (7)

∀(1 ≤ k′, k ≤ N), ∀(1 ≤ i′, i ≤ l)

zj′k′ + zjk − 1 ≤ sk′kj′j ≤1

2(zj′k′ + zjk), (8)

∀(1 ≤ k′, k ≤ N), ∀(1 ≤ j′, j ≤ m)

ck′ − (ck − τ)− (1− pk′k)M ≤ 0, ∀(1 ≤ k′, k ≤ N) (9)

ck′ − (ck − τ) + pk′kM ≥ 0, ∀(1 ≤ k′, k ≤ N) (10)

pk′k + pkk′ ≥ gk′kii, (11)

∀(1 ≤ k′, k ≤ N), k 6= k′, ∀(1 ≤ i ≤ l)

l∑i=1

N∑k=1

yijk ≤ cap(j),∀(1 ≤ j ≤ m) (12)

m∑j=1

N∑k=1

yijkτ ≤ G(i),∀(1 ≤ i ≤ l) (13)

(M est une constante suffisamment grande)

Dans cette formulation, les contraintes (1) et (2) definissentles proprietes des variables de decision Cmax et ck. La con-trainte (3) garantit que chaque conteneur est pris en chargepar une seule grue. La contrainte (4) assure que chaqueconteneur est place dans une seule aire de stockage. Lacontrainte (5) garantit le traitement de tous les conteneurs.La contrainte (6) definit la variable de decision yijk. Lacontrainte (7) definit les relations d’affectation conteneur-grue (rik) et les relations d’affectation couples de conteneurs,couples de grues (gk′ki′i). La contrainte (8)definit les rela-tions d’affectation conteneur-aire de stockage (zjk) et cou-ples de conteneurs-couple d’aires de stockage (sk′kj′j). Lescontraintes (9) et (10) expriment la relation de precedence :la contrainte (9)indique que lorsque k′ commence alors quek n’est pas termine alors ck′ − (ck − τ) > 0 et pour quecette contrainte soit satisfaite, il faut que pk′k = 0. La con-trainte (10) indique que lorsque k′ est termine avant que kne commence alors ck′ − (ck − τ) ≤ 0 ce qui oblige pk′k = 1.La contrainte (11) exprime la non simultaneite du traite-ment de deux conteneurs differents par la meme grue ( sideux conteneurs sont traites par la meme grue, alors il ex-iste une relation de precedence entre elles). La contrainte(12) traduit la satisfaction de la capacite residuelle de l’airede stockage j. La contrainte (13) exprime la satisfaction dela disponibilite de la grue i.

4. RÉSULTATSDes tests ont ete menes sur ce probleme pour verifier d’uncote que le programme mathematique donne des resultatsconformes a nos attentes pour trois capacites de train: 10,12 et 15 conteneurs. D’un autre cote de determiner le nom-bre minimum (inferieur a neuf) de grues necessaires pourminimiser la duree de traitement d’un train. Ces tests ontete realises a l’aide du solveur CPLEX et de ILOG OPL stu-dio en utilisant la formulation mathematique presentee dansla section 3.

Table 1: Resultats pour N=10N Instance Size (Nxlxm) valeur de CPU

Cmax (min) (sec)1 10x2 10 72002 10x3 6 213 10x4 6 3424 10x5 4 305 10x6 4 346 10x7 4 457 10x8 4 658 10x9 4 20

Table 2: Resultats pour N=12N Instance Size (Nxlxm) valeur de CPU

Cmax (min) (sec)1 12x2 11 72002 12x3 8 72003 12x4 6 72004 12x5 6 72005 12x6 4 3656 12x7 4 3267 12x8 4 1008 12x9 4 215

Table 3: Resultats pour N=15N Instance Size (Nxlxm) valeur de CPU

Cmax (min) (sec)1 15x2 14 54002 15x3 10 72003 15x4 8 72004 15x5 6 81005 15x6 6 72006 15x7 6 72007 15x8 5 10458 15x9 4 1671

Figure 1: La variation de Cmax en fonction de nom-bre de grues (pour N=10)

Figure 2: La variation de Cmax en fonction de nom-bre de grues (pour N=12)

Figure 3: La variation de Cmax en fonction de nom-bre de grues (pour N=15)

Pour chaque capacite de train nous faisons varier le nombrede grues de 2 a 9. On a fait tourner le solveur CPLEX ensupposant que la duree de traintement d’un conteneur estde deux minutes.

Les resultats dans le tableau 1, 2 et 3 montrent comme prevuque le makespan baisse lorsqu’on augmente le nombre degrues. On remarque egalement que pour 10 conteneurs, apartir de cinq grues on grade le meme niveau de qualitede solution (voir figure 1), pour 15 conteneurs, la duree demakespan ne se stabilise qu’a partir de six grues (voir figure2), et pour 15 conteneurs, la solution minimal est atteintelorsque le nombre de grues est egale a neuf.

5. CONCLUSIONDans ce papier, nous avons aborde le probleme de la min-imisation de la duree du traitement d’un train de conteneursdans la plateforme MITA. Apres l’analyse de l’existant, nousavons modelise ce probleme pour aboutir a un MIP de tresgrande taille (plus que 2000 variables et plus que 500 con-traintes). Nous avons resolu ce probleme en utilisant lesolveur CPLEX pour trois capacites du train( 10, 12 et 15conteneurs) et en faisant varier le nombre de grues de 2 a 9.Les resultats obtenus ont ete conformes a nos attentes. Eneffet, le makespan diminue avec l’augmentation du nombre

de grues. Au dela du seuil de 15 conteneurs, le temps CPUdepasse les 24 heures. Une piste d’amelioration de la reso-lution du probleme avec les donnees reelles (60 conteneurs)serait de developper des metaheuristiques de type recherchelocale. MITA peut exploiter les resultats de ce travail pourmaximiser le nombre de trains qu’elle peut accueillir par jouret egalement pour dimensionner son parc de grues confor-mement a ses objectifs de productivite.

6. REFERENCES[1] A. Galuszka, K. Skrzypczyk, D. Bereska, and

M. Pacholczyk. Re-Handling Operations in SmallContainer Terminal Operated by Reach Stackers.World Academy of Science, Engineering andTechnology, 70, 2010.

[2] K. H. Kim, K. W. Kim, H. Hwang, and C. S.Ko Operator-scheduling using a constraint satisfactiontechnique in port container terminals. Computers andIndustrial Engineering, 46 :373-381, 2004.

[3] E. Kozan Optimising container transfers atmultimodal terminals. Mathematical and ComputerModelling, 31 :235-243, 2000.

[4] D. H. Lee, J. X. Cao, and Q. X. ShiSynchronization of yard truck scheduling and storageallocation in container terminals. EngineeringOptimization, 41(7):659-672, 2009.

[5] C. Zhang, Y. Wan, J. Liu, and R.J. LinnDynamic crane deployment in container storage yards.Transportation Research-B, 36 :537-555, 2002.

[6] Y. Zhu, and A. Lim Crane Scheduling with SpatialConstraints: Mathematical Model and SolvingApproaches. AMAI, 2004.