[PDF] Contribution à lOptimisation du Chargement et du Déchargement

View - Download Contribution à lOptimisation du Chargement et du Déchargement

Previous PDF

Next PDF

THESE

Pour obtenir le diplôme de doctorat

Spécialité : Informatique

Préparée au sein de l'Université Le Havre Normandie En partenariat international avec la FST de Fès, USMBA, Maroc des Conteneurs dans le cas des Transports Routier et Fluvial

Présentée et soutenue par

Mme. Amina EL YAAGOUBI

Thèse codirigée par Jaouad BOUKACHOUR (et Ahmed EL HILALI ALAOUI), Laboratoire de

Mathématiques Appliquées du Havre (LMAH)

Thèse soutenue publiquement le 19 janvier 2019

devant le jury composé de

Mr. Abdelhamid BENAINI Professeur des universités/ Université Le Havre Normandie, France Président

Mr. Laurent AL FANDARI Professeur des universités/ ESSEC Business School de Cergy-Pontoise, France Rapporteur

Mr. Mohammed DOUIMI Professeur des universités/ ENSAM de Meknès, Maroc Rapporteur Mr. Mohammed EL KHOMSSI Professeur des universités/ FST Fès, Maroc Examinateur Mr. Mohammed DAHANE Maître de conférences HDR/ ENIM de Metz, France Examinateur Mme. Fatima EL KHOUKHI Professeur/ FLSH, Meknès, Maroc Examinatrice Mr. Jaouad BOUKACHOUR Maître de conférence-HDR/ Université Le Havre

Normandie, France Directeur de thèse

Mr. Ahmed EL HILALI ALAOUI Professeur des universités/ FST Fès, Maroc Codirecteur de thèse i

Avant Propos

(France) et et préparée au sein des deux laboratoires : Laboratoi Havre Normandie et Laboratoire Modélisation et Calcul Scientifique (LMCS) à la Faculté des

Sciences et Techniques de Fès.

Cette thèse a été dirigée par Monsieur Jaouad BOUKACHOUR, Maître de conférences et Habilité

et Monsieur Ahmed EL HILALI ent Supérieur à la FST de Fès. e National pour

la Recherche Scientifique et Technique (CNRST) du Maroc et par des projets de la région

Normandie, France.

ii Remerciement A doctorales.

J Monsieur Jaouad

accueilli au sein du Laboratoire de Mathématiques Appliquées du H multiples conseils et remarques et opportunités. J humaines d'écoute et de compréhension tout au long de ce travail doctoral. La recherche semble toujours simple et passionnante à ses côtés. Je tiens également à remercier vivement mon directeur de thèse, Monsieur Ahmed EL HILALI Laboratoire Modélisation et Calcul Scientifique. Ma profonde gratitude pour son encadrement pédagogique et scientifique, son appui constant et ses qualités humaines, pour T connaissances scientifiques, vos discussions productives et remarques pertinentes que ce travail a pu être mené à terme.

Je souhaiterais remercier l'ensemble des membres de mon jury pour l'intérêt qu'ils ont porté à

mes travaux et pour avoir humblement accepté de juger et de poser un regard critique sur les travaux de recherche de cette thèse. U Norma honore et nous comble de satisfaction. Je vous présente mes vifs remerciements pour le grand honneur que vous faites en acceptant de juger ce travail. iii

Je tiens à remercie

Meknès, et Monsieur EL KHOMSSI Mohammed, Professeur à la Faculté des Sciences conseils.

Je tiens à remercier chaleureusement

Metz, et Madame EL

remarques et vos conseils pertinents. Nul remerciement ne serait suffisant pour exprimer mon amour et mon immense gratitude à : ma mère et mon père : Meriem et

Ismail. Vous avez été ma plus grande

et vous la resterez toujours. Sans vous, sans vos prières et vos bénédictions, je ne serais pas où je suis aujourd'hui. Que Dieu vous protège. Je remercie mon frère Karim et ma Stephy. Pour moi, vous êtes ma petite, chère et belle famille.

M de mon amour, je ne

prononcerai aucun mot à ce niveau. Un grand merci à Anass my Lucy. Un grand merci à mes chers Nisrine, Manal, Imad et Marouane pour leur bonne humeur, leur vous tous J Appliquées du Havre pour leurs sympathie, leurs soutiens et leurs conseils. Vous resterez dans le partage et la bienveillance.

Enfin, mes remerciements à celles et à ceux qui ont participé de près ou de loin à la réalisation

de cette thèse doctorale. iv

For you

A.O.M.S.K.S.H.M.N.

v

Résumé

chargement/déchargement, appelés " shiftings », dans les problèmes de transport. Notre étude concerne

deux contextes, notamment le problème de routage dans le cas du transport routier et le problème

Dans le premier contexte, nous introduisons le problème de shifting dans le cas du voyageur de commerce,

que nous notons " Shifting Traveling Salesman Problem, (ShTSP) ». Le coût de shifting total varie en fonction

oduits est chargé dans une pile de

telle sorte que, pour décharger un produit, il est nécessaire de décharger puis recharger tous les produits

qui se trouvent au-dessus. Notre objectif principal est de chercher un circuit hamiltonien qui optimise à la

fois le coût de déplacement et le coût de shifting. Nous proposons une modélisation mathématique du

Comme le problème est NP-complet,

nous adaptons la méta- " Ant Colony Optimization,

(ACO) » sous sa forme séquentielle (ACO-séquentielles) et parallèle (ACO-parallèles) pour le résoudre.

appelés barges. Ce problème consiste à chercher

déchargement dans la chronologie des ports à visiter, tout en respectant les contraintes structurelles et

opérationnelles liées à la fois aux barges et aux conteneurs (structure cellulaire de la barge, fragilité et

poids des conteneurs, taille des conteneurs, etc.). En premier lieu, nous introduisons une modélisation

rge où différents ports du trajet ont des coûts opérationnels de chargement/déchargement non-

total de shifting et de maximiser la stabilité longitudinale et transversale de la barge. En deuxième lieu,

problème est traité sur la base de sa relation avec le problème de bin-packing en trois dimensions. Nous

en nombres entiers, dans lequel

multi-objectif en optimisant le nombre de shiftings, la stabilité du convoi et le nombre de barges réellement

utilisées dans le convoi. Afin de résoudre cette nouvelle variante, nous adaptons la méthode évolutionnaire

multi-objectif NSGA-II (Non-dominated Sorting Genetic Algorithm-II) et, ceci, en se basant sur un ensemble

bin-packing

résultats numériques obtenus est évalué en utilisant des mesures de performances adaptées à la variante du

problème traité.

Mots-Clés Shifting ; Conteneurs ; Barge ; Stabilité ; Fragilité ; Bin-Packing ; Programmation Mathématique ;

Optimisation Multi-objectif ; ACO-parallèle ; NSGA-II. vi

Abstract

This work outlines the optimization of unproductive loading/unloading movements, called " shiftings », in

transport problems. Our study concerns two contexts including routing problems in the case of road

transportation and stowage problems in the case of river transportation.

In the first context, we introduce shifting in the case of the traveling salesman problem, which we refer to as

the " ShTSP ». The total shifting cost varies according to the order of the visited clients during the tour.

Indeed, a set of products is loaded into a stack so that, to unload a product, it is necessary to unload and

reload all products that are above. Our main goal is to find a Hamiltonian circuit that optimizes both the

travel cost and the shifting cost. We propose a mathematical modeling of the ShTSP as a mixed nonlinear

mathematical program. Since the problem is NP-complete, we adapt the ant colonies meta-heuristics (ACO)

in its sequential and parallel form to solve it. In the second context, we address the three-dimensional container stowage planning problem of inland

vessels called barges. This problem consists in finding the most suitable location of each container in the

barge in order to facilitate its retrieval in the chronology of ports to be visited, while satisfying the context-

dependent structural and operational constraints related both to the barge and to the containers. In the

first hand, we introduce a novel mathematical formulation of the problem in the case of a single barge

where different ports are of non-uniform operational costs. The main objective is to minimize the total

shiftings fees and to maximize, both, the longitudinal and transversal stability of the barge. In the second

hand, we generalize our problem to the case of barge convoy systems with uniform operational costs. This

problem is treated on the basis of its relation with the three-dimensional bin-packing problem. Firstly, we

propose a mathematical model, in which, we consider the multi-objective aspect by optimizing the total

number of shiftings, the stability of the convoy and the number of the real-used barges in the convoy. In

order to solve this new variant, we propose a novel adaptation of the multi-objective evolutionary

algorithm NSGA-II (Non-Dominated Sorting Genetic Algorithm-II) based on a set of heuristics introduced

by the bin-packing problem resolution methods. The numerical results are evaluated using performance measures adapted to the problem.

Keywords Shifting ; Container ; Barge ; Stability ; Fragility ; Bin-Packing ; Mathematical Programming ;

Multi-Objective Optimization ; parallel-ACO ; NSGA-II. vii

Table des matières

Avant Propos .................................................................................................................................................................................... i

Remerciement ................................................................................................................................................................................ ii

Résumé .............................................................................................................................................................................................. v

Abstract ...........................................................................................................................................................................................vi

Liste des figures .............................................................................................................................................................................. x

Liste des tableaux ........................................................................................................................................................................ xii

Introduction générale ................................................................................................................................................................. 13

Chapitre I Les problèmes de chargement/déchargement dans le cas du transport conteneurisé : généralités et

contexte ............................................................................................................................................................................. 17

1 .......................................................................................................................................... 17

2 Transport conteneurisé .................................................................................................................................................. 18

2.1 La conteneurisation ...................................................................................................................................... 18

2.2 Modes de transport ........................................................................................................................................... 19

2.2.1 Transport routier ................................................................................................................................................... 19

2.2.2 Transport ferroviaire ............................................................................................................................................ 19

2.2.3 Transport maritime ............................................................................................................................................... 19

2.2.4 Transport fluvial .................................................................................................................................................... 20

2.2.5 Situation en Europe ............................................................................................................................................... 22

2.2.6 Performance environnementale des différents modes de transport.......................................................... 23

2.2.7 Transport intermodal ........................................................................................................................................... 25

3 Opérations dans un terminal à conteneurs ............................................................................................................................. 25

4 ....................................................................... 26

4.1 Définition du problème....................................................................................................................................................... 26

4.2 .................................................................................................................................................... 27

4.2.1 Approche en plusieurs phases ............................................................................................................................. 27

4.2.2 Approche en une seule phase............................................................................................................................... 29

5 Le problème de bin-packing .................................................................................................................................................... 32

5.1 Le bin-packing en une dimension (BPP-1D) ................................................................................................................ 32

5.2 Le bin-packing en deux dimensions (BPP-2D) ............................................................................................................ 34

5.3 Le bin-packing en trois dimensions (BPP-3D) ............................................................................................................ 35

5.3.1 Méthodes de résolution ........................................................................................................................................ 36

6 ................................................................................................................................................. 36

Chapitre II Le

shifting dans le problème de voyageur de commerce : de la modélisation à la résolution .............. 38

1 Introduction et travaux antérieurs ........................................................................................................................................... 38

2 Description du problème ................................................................................................................................................... 41

3 Formulation mathématique du ShTSP .................................................................................................................................... 46

Table des matières

viii

4 Résolution du ShTSP ................................................................................................................................................... 50

4.1 e colonie de fourmis (ACO) .............................................................................................. 50

4.2 ...................................................................................... 51

4.3 Algorithme direct ..................................................................................................................................................... 52

4.4 ................................................................................... 53

4.5 Réglage des paramètres ..................................................................................................................................................... 54

4.6 Résultats expérimentaux ................................................................................................................................................... 54

4.6.1 Génération des instances ..................................................................................................................................... 55

4.6.2 Résultats numériques et discussion ................................................................................................................... 57

5 Conclusion .................................................................................................................................................. 61

neurs avec coût de shifting

non-uniforme ...................................................................................................................... 62

1 Introduction ................................................................................................................................................... 62

2 Transport vert : transport par barge comme alternative écologique aux autres modes du transport intermodal63

3 64

3.1 Structure physique de la barge ......................................................................................................................................... 64

3.2 La politique du " dernier entré, premier sorti » (LIFO) ........................................................................................... 66

3.3 Les frais non-uniformes des opérations de manipulation des conteneurs ............................................................. 67

3.4 Notion de stabilité de la barge .......................................................................................................................................... 69

3.4.1 Stabilité transversale : la gîte .............................................................................................................................. 70

3.4.2 Stabilité longitudinale ....................................................................................................................... 72

3.5 Coordonnées des positions de la barge .......................................................................................................................... 73

3.6 Notion de fragilité des conteneurs et son influence sur le poids limite de chaque pile ..................................... 77

3.7 ............................................................................. 81

4 Formulation mathématique du 3D-BCSPP ............................................................................................................................ 82

5 Résolution et discussion des résultats ...................................................................................................................................... 91

5.1 .................................................................................................................................. 91

5.2 Génération des instances du 3D-BCSPP ....................................................................................................................... 92

5.3 Résultats numériques et discussion ................................................................................................................................ 96

5.4 Comparaison numérique .................................................................................................................................................... 99

5.4.1 La performance des mesures de stabilité ......................................................................................................... 99

5.4.2 Comparaison des frais de shiftings dans le cas uniforme et non-uniforme ............................................ 102

6 Conclusion ................................................................................................................................................ 103

Chapitre IV Optimisation multi-objectif

système de convoi de barges: modélisation et résolution par le NSGA-II ........................................................ 105

1 Introduction ................................................................................................................................................. 105

2 Transport fluvial par un système de convoi de barges ...................................................................................................... 106

3 Description du problème ................................................................................................................................................ 107

3.1 Relation du 3D-CCSPP avec le problème de bin-packing en 3D ........................................................................... 109

3.2 La stabilité de la barge selon la distance métacentrique GM ................................................................................ 109

3.3 Aspect multi-objectif du 3D-CCSPP ............................................................................................................................ 110

4 Formulation mathématique du 3D-CCSPP .......................................................................................................................... 112

5 Méthodes de résolution ................................................................................................................................................ 119

5.1 Aspect multi-he de résolution ..................................................................................................... 120

5.2 Principe général de la méthode NSGA-II ................................................................................................................... 120

5.3 Adaptation du NSGA-II pour le 3D-CCSPP.............................................................................................................. 121

5.3.1 .......................................................................................................................................... 121

5.3.2 Génération de la population initiale ............................................................................................................... 123

5.3.2.1 Règles de chargement ....................................................................................................................... 124

5.3.2.2 Heuristique de chargement des conteneurs dans une seule barge H_UniBarge ............... 125

5.3.2.3 Rand H_UniBarge ................................................................ 126

5.3.2.4 Heuristique de chargement des conteneurs dans un convoi de barges H_MultiBarge ... 127

Table des matières

ix

5.3.2.5 Diversification de la population initiale ........................................................................................ 130

5.3.3 Classification des individus ............................................................................................................................... 130

5.3.3.1 La notion de non-dominance ........................................................................................................... 130

5.3.3.2 Le mécanisme de sélection Pareto " ranking »............................................................................ 130

5.3.3.3 Préservation de la diversité ............................................................................................................. 131

5.3.4 Opérateur de sélection ........................................................................................................................................ 132

5.3.5 Etape de reproduction ........................................................................................................................................ 133

5.3.5.1 Opérateur de croisement .................................................................................................................. 133

5.3.5.2 Heuristique de la vérification de faisabilité des individus (HVF) .......................................... 135

5.3.5.3 Opérateur de mutation ...................................................................................................................... 139

5.3.6 Etape de remplacement ...................................................................................................................................... 140

5.3.7 ................................................................................................................................................ 140

5.4 Résultats numériques et expérimentaux ..................................................................................................................... 140

5.4.1 Environnement expérimental et réglage des paramètres ......................................................................... 141

5.4.2 Génération des instances du 3D-CCSPP ...................................................................................................... 141

5.4.3 Résultats numériques et discussion ................................................................................................................ 143

5.4.3.1 Résolution du modèle mathématique par CPLEX .................................................................... 144

5.4.3.2 Résultats numériques obtenus par le NSGA-II .......................................................................... 146

5.4.3.3 ............................................... 150

5.4.3.4 Analyse des résultats : comparaison et discussions ................................................................... 152

5.4.3.5 Analyse de performance des plans de chargement obtenus par NSGA-II .......................... 156

6 Conclusion ................................................................................................................................................ 163

Conclusion générale et travaux futurs .................................................................................................................................. 165

quotesdbs_dbs29.pdfusesText_35

[PDF] Le conte oriental en France, de Galland ? Nerval - DEA - Debreceni

[PDF] Modèle de contrat d 'engagement - KTV ATP

[PDF] Contrat de Maintenance et de Suivi Informatique - Actiline

[PDF] CONTRAT DE MAINTENANCE DES LOGICIELS INGETELDATA

[PDF] Critique de film, aut2009 - Portail pour l 'enseignement du français

[PDF] Ecrire une critique de film - Atelier critique

[PDF] CV et lettre de motivation

[PDF] votre cv en anglais et en français - ACIFR

[PDF] CV Conseils Bac Pro Recherche de stage - Académie de Nancy-Metz

[PDF] Préparer votre candidature pour décrocher un contrat en alternance

[PDF] Guide sur le CV - Services ? la vie étudiante - UQAM

[PDF] DEDICACES

[PDF] demande d ouverture d établissement pharmaceutique de - Ansm

[PDF] Guide sur le brevet d 'invention - Office Marocain de la Propriété

[PDF] MODELE DE DEMANDE DE CANDIDATURE - laatechnet