Soutenance mémoire
Avec la croissance économique, le volume de biens transportés par voie maritime devient de plus en plus important grâce à la massification offerte par ce type de transport. C’est un moyen de transfert adapté aux matières pondéreuses transportées sur de longues distances par des gros navires. La voie maritime est très peu onéreuse (elle coûte trente fois moins cher que la voie terrestre), elle permet non seulement l’acheminement des marchandises de grandes masses, mais aussi de transporter des petits lots et à des courtes distances. Pour obéir à cette évolution, les sociétés de transport maritime ont été obligées d’améliorer leurs moyens en augmentant les tailles des navires pour qu’ils puissent supporter ce grand volume de biens ainsi que celles des ports pour être capable d’offrir aux navires de grande taille un bon amarrage. Avec cette accroissement du volume de marchandises transportées et l’augmentation des tailles des ports, les équipements traditionnels des ports deviennent inefficaces et les opérations de chargement et de déchargement des navires deviennent de plus en plus lentes. La conteneurisation qui conssite à stocker les marchandises dans des boites spécifiques ayant des tailles fixes a fortement contribué au gain de l’éspace de stockage et à favoriser la réduction des temps des opérations de chargement et déchargement des navires. Ainsi, l’automatisation des ports a pu être facilité par cette conteneurisation et a permet l’accélération du transfert des conteneurs du navire vers les clients et inversement. Malhereusement, l’automatisation d’un port est un investissement assez lourd et très couteux finacièrement elle n’est appliquée que dans un nombre limité des ports .
Le problème majeur lié au développement des terminaux portuaire de la région Nord-Ouest de l’Europe dépend de la gestion interne du trafic et de l’optimisation au sein de leurs espaces confinés. Une solution a été proposée pour la sélection de ports importants, comme le port de Rotterdam, Düsseldorf et Hambourg, pour automatiser leurs manutentions de marchandise en conteneurs, en utilisant le système Automated Guided Véhicules (AGV). Cette solution a permis de résoudre certains problèmes relatifs au trafic interne. En revanche, la solution suggérée a permis d’identifier de nombreuses limites.
• L’infrastructure portuaire devrait s’adapter à l’utilisation du système AGV, ce qui rendra difficile toute tentative de généralisation sur d’autres ports Européens.
• Le système AGV est alimenté par un moteur de combustion interne, ce qui augmentera le niveau de pollution dans l’espace d’activité portuaires.
• L’échec de gestion d’un tel système de transport n’est pas pris en compte. Par exemple, lorsqu’un véhicule est en panne, il bloque le parcours des véhicules suivants.
Ainsi, nos travaux s’inscrivent en partie dans le projet ‘Intelligent Transportation for Dynamic Environment’ (InTraDE, 2009-2013) [1] qui avait pour vocation de lever ces incovénieants et de contribuer à l’amélioration de la gestion du trafic ainsi qu’à l’optimisation des espaces dans les zones confinées en développant un système de transport intelligent et écologique, offrant une meilleure sécurité. Ce système est apte à s’adapter aux exigences spécifiques de l’environnement, et pourrait être transféré à des ports et terminaux quelle que soient leurs dimensions. Le système de transport suggéré fonctionne en conjonction avec un logiciel de simulation virtuelle dans le site, permettant ainsi une supervision robuste (en temps réel), des opérations de manutention des conteneurs; d’où l’infrastructure existant d’un port donné ne nécessite aucun investissement [1]. Le véhicule qui sera utilisé pour transporter des marchandises d’une zone de stockage vers une autre, est différent de l’AGV. Il s’agit d’un véhicule intelligent qui peut se déplacer d’une manière autonome et sécurisé (capable d’éviter des obstacles). Ce véhicule portera le nom de véhicule automatique intelligent AIV (Automated Intelligent Vehicle).
Les problèmes d’optimisation et les approches de résolution
Dans le monde réel, en particulier dans le domaine industriel tel que la mécanique, la chimie, la télécommunication, l’environnement, le transport,…etc, les problèmes sont complexes et de grandes tailles, ce qui les rendent difficiles à résoudre, bien qu’ils soient souvent faciles à définir. L’optimisation, qui représente une partie très importante de la recherche opérationnelle, s’occupe de ce type de problèmes. En effet, la plupart de ces problèmes appartiennent à la classe des problèmes NP difficiles et ne possèdent donc pas à ce jour de solutions algorithmiques efficaces et valables pour toutes les données. Dans la littérature, plusieurs travaux de recherche se sont intéressés à la résolution de ces problèmes d’optimisation. Les chercheurs ont divisé ce type de problème en deux groupes: problème mono-objectif et problème multi-objectif. Les problèmes mono-objectifs existent rarement dans les applications réelles par contre les problèmes multi-objectifs caractérisés par des critères généralement contradictoires et qui doivent être satisfaits simultanément, représentent une majorité des situations réelles.
Classification des problèmes d’optimisation
Indépendamment du degré de difficulté du problème d’optimisation, sa résolution nécessite tout d’abord sa classification par rapport aux problèmes existants dans la littérature. Cette classification n’est pas seulement un moyen pour montrer l’importance du problème mais également, une façon de faciliter sa résolution en le traitant par analogie par exemple par rapport à un autre problème existant. Le domaine industriel est regorge des différents types de problèmes qui ont été groupés en deux classes principales: La première classe représente les problèmes de décision qui sont caractérisés par une solution réduite à une simple réponse «oui » ou « non ». Par contre, la deuxième classe concerne les problèmes d’optimisation possédant une solution admissible qui doit être construite et qui permet de minimiser ou maximiser la fonction objectif. Un type particulier de problèmes n’ayant aucune méthode de résolution et qui sont les plus difficiles sont les problèmes indécidables.
Malgré que cette classification montre une indépendance entre ces deux types de problèmes, la littérature montre un lien très fort entre les problèmes de décision et les problèmes d’optimisation. La résolution d’un problème d’optimisation dont l’objectif est de minimiser ou maximiser la valeur de la fonction objectif, nécessite indirectement la résolution d’un problème de décision qui consiste à étudier l’existence ou non d’une solution admissible optimale. D’une manière réciproque, l’étude de la complexité d’un problème de décision permet de donner les indications relatives aux problèmes d’optimisation associés [4]. D’une manière générale, un problème quelconque qu’il soit de décision ou d’optimisation doit appartenir à l’une de ces trois classes suivantes:
Problème de classe P
L’appartenance d’un problème quelconque à cette classe nécessite qu’il soit un problème de décision et ayant au moins un algorithme polynomial comme méthode de résolution, il est nommé facile ou de classe P. La vérification de l’existence d’un tel algorithme est obligatoire pour montrer l’appartenance du problème à cette classe.
Problème de classe NP
Le problème de cette classe ne peut pas être résolu dans un temps polynomial, il est dit NP difficile. Les méthodes de résolution utilisées sont les heuristiques qui permettent de trouver une solution optimale mais non démontrables. Les problèmes de classe P peuvent être résolus par les algorithmes ordinaires ou exacts qui sont inclus dans la famille des heuristiques, par la suite la classe P est inclus dans la classe NP.
Problème de classe NP-Complet
Un problème de décision P est dit NP-complet s’il appartient à la classe NP et si pour tout problème P’ de NP, on a les propriétés suivantes :
• Il existe une application polynomiale qui transforme toute instance I’ de P’ en une instance I de A.
• P’ admet une réponse «oui » pour l’instance I’, si et seulement si P admet une réponse oui pour l’instance I.
Une propriété générale des problèmes NP complet : Si un seul problème NP-complet est Polynomial, alors tous les problèmes NP-complet sont polynomiaux. Si le problème est NPdifficile, il n’existe pas d’algorithme polynomial le résolvant [5].
Optimisation multi-objectif
L’origine de l’optimisation multi-objectif date du 19ème siècle, elle a été appliquée dans les domaines de la gestion et l’économie par Edgeworth et Pareto. Ce pendant elle a connu un essort plus important dans les année 1980, ensuite elle a été élargie aux sciences de l’ingénieur dans les années 1996. Les chercheurs se sont intéressés au début aux problèmes bi-objectifs. Pour résoudre ce type de problème, ils ont utilisé les méthodes exactes telles que Branch and Bound [8], l’algorithme A* [9] et la programmation linéaire [10]. Les travaux ont montré l’efficacité de ces méthodes pour les problèmes de petites tailles, mais aussi leurs inefficacités pour ceux de grandes tailles ou multicritères. Pour un problème multicritères ou de grande taille, la complexité du problème devient plus grande. Les méta-heuristiques ont été proposées comme approches de résolution de ces problèmes, vu l’inexistence des méthodes exactes efficaces pour résoudre ces problèmes. Contrairement à l’optimisation mono-objectif qui consiste à trouver une solution unique, l’optimisation multi-objectif permet de trouver un ensemble des solutions qui représente l’ensemble des solutions Pareto optimale.
|
Table des matières
INTRODUCTION
Chapitre 1 Introduction
I. Introduction
II. Contexte de la thèse
III. Problématique et Objectifs
IV. Positionnement Sciemtifique du probleme
V. Conclusion
Chapitre 2 Les problèmes d’optimisation et les approches de résolution
I. Introduction
II. Optimisation combinatoire
II.1. Définition
II.2. Classification des problèmes d’optimisation
II.3. Complexité d’un problème
III. Optimisation multi-objectif
III.1. Définition
III.2. Concepts d’optimalité au sens de Pareto
III.2.1. Notion de dominance
III.2.3. Frontière de Pareto
III.2.4. Notion de dominance avec contraintes
III.2.5. Optimum au sens de Pareto
III.3. Approches de résolution d’un problème d’optimisation multi-objectif’
III.3.1. Transformation d’un problème multi-objectif en un problème mono-objectif
III.3.2. Approche non-Pareto (non agrégée)
III.3.3. Approche Pareto
IV. Méthodes de résolution d’un problème d’optimisation multi-objectif
IV.1. Méthodes exactes
IV.1.1. Branch and Bound
IV.1.2. Programmation dynamique
IV.2. Méta-heuristiques
IV.2.1. Algorithme de recuit simulé
IV.2.2. Recherche Tabou
IV.2.3. Colonie de fourmis
IV.2.4. Algorithme Génétique
V. Algorithmes non elitistes et Algorithmes elitistes
V.1. Algorithmes non elitistes
V.1.1. Vector Evaluated Genetic Algorithm(VEGA)
V.1.2. Multi Objective Genetic Algorithm (MOGA)
V.1.3. Niched Pareto Genetic Algorithm (NPGA)
V.1.4. Non dominated Sorting Genetic Algorithm (NSGA-I)
V.2. Algorithmes élitistes
V.2.1. Strength Pareto Evolutionary Algorithm (SPEA)
V.2.2. Strength Pareto Evolutionary Algorithm 2(SPEA2)
V.2.3. Non dominated Sorting Genetic Algorithm II(NSGA-II)
VI. Conclusion
Chapitre 3 Gestion des opérations portuaires et Etat de l’art sur l’affectation des conteneurs aux AGVs
I. Introduction
II. Transport maritime
II.1. Phases d’évolution du transport maritime
II.1.1. Première phase : Conteneurisation
II.1.2. Deuxième phase : Multi-modalité
II.1.3. Troisième phase : Automatisation
II.2. Système de manutention dans un port
II.2.1. Système à grue simple (stacking cranes)
III. Gestion des opérations portuaire
III.1. Zone d’opérations portuaires
III.1.1. Les équipements de manutention
III.1.2. Les Véhicules internes
III.3. Zone d’opérations terrestres
III.4. Operations portuaires
III.4.1. Allocation des postes du quai (Berth Allocation Problem: BAP)
IV. Processus de chargement et déchargement
V. Système d’AGVs et ordonnancement des tâches
V.1. Problème d’affectation
V.1.1. Choix du véhicule le plus loin
V.1.2. Choix du véhicule le plus proche
V.1.3. Choix aléatoire du véhicule
V.2. Problème de Routage
V.3. Problème d’ordonnancement
VI. Problèmes d’affectation des AGVs et approches utilisées
VII. Problèmes d’ordonnancement des AGVs et approches utilisées
VIII. Affectation dynamique des tâches aux AGVs et approches utilisées
IX. Routage dynamique et approches de résolutions
X. Conclusion
CONCLUSION
Télécharger le rapport complet
