Détail document
Optimisation du stockage des conteneurs dans un terminal portuaire
Résumé
Un terminal à conteneurs constitue une interface inter-modale importante pour le système de transport mondial. La compétitivité d'un port se mesure par l'efficacité de ses terminaux.
[...]
La manutention efficace des marchandises représente un point critique de la chaîne de transport, la réduction des coûts de stockage et de gestion.Le problème de stockage de conteneurs (PSC), est l'un des plus courants et importants problèmes dans un terminal à conteneurs. L'objectif de ce problème est de créer un plan de stockage optimal qui définit l'emplacement idéal pour chaque conteneur tout en tenant compte des contraintes réelles de la zone de stockage.Dans cette thèse, nous traitons le problème du stockage de conteneurs dans un terminal portuaire, en nous concentrant sur deux cas :- Le cas statique qui vise à déterminer la meilleure stratégie de stockage pour les conteneurs importés.- Le cas critique qui consiste à trouver un plan optimal de stockage pour les conteneurs dangereux.Dans ce mémoire, nous donnons un état de l'art et une recherche bibliographique dans lesquels sont décrits les travaux antérieurs sur ce sujet. Ensuite, nous abordons respectivement les deux cas de stockage. Nous proposons une étude approfondie pour chacun d'entre eux, ainsi qu'une modélisation mathématique efficace qui modélise la situation réelle et nous détaillons les méthodes d'optimisation proposées pour résoudre ce problème. Pour effectuer une étude théorique de ce problème, nous proposons une démonstration de sa complexité, ce qui confirme encore son caractère NP-difficile. Ce type de problème est difficile à résoudre avec des méthodes exactes. Ceci est vérifié par des simulations numériques réalisées à l'aide du logiciel d'optimisation "GUROBI". Cependant, ce logiciel a des limites car il est gourmand en place mémoire, et il prend beaucoup de temps d'exécution lorsque le nombre de conteneurs à stocker devient plus grand, ce qui ajoute à la complexité du problème.En conséquence, nous avons proposé un algorithme de recherche locale itérée, un algorithme glouton randomisé, un algorithme génétique, un algorithme à base de recuit simulé et un algorithme de colonie d’abeilles comme algorithmes méta-heuristiques. Ces algorithmes proposés sont des méthodes de résolution approchées, ce qui signifie que l'optimalité des solutions qu'ils fournissent ne peut être garantie. Cependant, les comparaisons avec les résultats obtenus par « GUROBI », sur des instances de tailles raisonnables, ont démontré la bonne qualité de nos solutions.Des hybridations entre ces algorithmes méta-heuristiques distincts ont été développées afin de tirer profit de leurs avantages respectifs et d'éviter ainsi la convergence prématurée vers des optima locaux. La première hybridation proposée est une méthode qui renforce l'algorithme de recherche locale itérée par un algorithme glouton randomisé, tandis que la seconde est un algorithme génétique hybridé avec le recuit simulé comme opérateur de mutation. Ces hybridations ont accéléré la convergence de nos algorithmes et, dans certains cas, amélioré la qualité des meilleures solutions obtenues..A container terminal is an important intermodal interface for the global transport system. The competitiveness of a port is measured by the efficiency of its terminals. The efficient handling of goods represents a critical point in the transport chain, reducing storage and management costs.The container storage problem (CSP), is one of the most common and important problems in a container terminal. The objective of this problem is to create an optimal storage plan that defines the ideal location for each container while taking into account the real constraints of the storage area.In this thesis, we deal with the problem of container storage in a port terminal, focusing on two cases:- The static case which aims to determine the best storage strategy for imported containers.- The critical case which consists of finding an optimal storage plan for dangerous cotainers.In this report, we give a state of the art and a bibliographic research in which are described the previous works on this subject. Next, we discuss the two storage cases respectively. We propose an in-depth study for each of them, as well as an efficient mathematical modeling that models the real situation and we detail the optimization methods proposed to solve this problem. To perform a theoretical study of this problem, we propose a proof of its complexity, which further confirms its NP-hard character. This type of problem is difficult to solve with exact methods. This is verified by numerical simulations carried out using the "GUROBI" optimization software. However, this software has limitations because it is memory intensive, and it takes a lot of execution time when the number of containers to store becomes larger, which adds to the complexity of the problem.Accordingly, we have proposed iterated local search algorithm, randomized greedy algorithm, genetic algorithm, simulated annealing based algorithm and bee colony algorithm as meta-heuristic algorithms. These proposed algorithms are approximate solution methods, which means that the optimality of the solutions they provide cannot be guaranteed. However, comparisons with the results obtained by “GUROBI”, on instances of reasonable size, have demonstrated the good quality of our solutions.Hybridizations between these distinct meta-heuristic algorithms have been developed in order to take advantage of their respective advantages and thus avoid premature convergence towards local optima. The first proposed hybridization is a method that reinforces the iterated local search algorithm with a randomized greedy algorithm, while the second is a genetic algorithm hybridized with simulated annealing as the mutation operator. These hybridizations have accelerated the convergence of our algorithms and, in some cases, improved the quality of the best solutions obtained.