Ying LI soutient sa thèse de doctorat le lundi 6 décembre 2021 à 14h30. La soutenance se déroule au Grand Amphithéatre du site IBGBI.
Titre : Modèles et méthodes efficaces pour de nouveaux problèmes d’affectation intégrée des navires aux postes à quai et aux grues
Mots clés : port, maintenance, incertitude, optimisation mathématique, heuristique, algorithmes génétiques
Résumé :
La gestion d’opérations aux terminaux est un des grands défis du transport maritime. Dans la gestion de terminaux portuaires, l’allocation des postes à quai et l’affectation de grues sont deux éléments clés. La plupart des travaux existants pour le problème d’affection intégrée des navires aux postes à quai et aux grues (BACAP) supposent que les grues de quai (QCs) sont disponibles à tout moment et que la productivité des QCs est constante. Mais dans la pratique, certains QCs peuvent être indisponibles à cause de l’activité de maintenance préventive planifiée périodiquement, et leur productivité incertaine en raison de divers facteurs tels que les conditions météorologiques, etc. Ceux-ci peuvent grandement affecter la performance des terminaux portuaires. Dans ce contexte, nous étudions trois nouveaux BACAPs considérant l’activité de maintenance des QCs et la productivité incertaine des QCs.
Tout d’abord, nous investirons un nouveau BACAP avec l’activité de maintenance des QCs, dans lequel la maintenance des QCs doit être effectuée dans des fenêtres de temps. L’objectif est de minimiser le temps de rotation total des navires. D’abord, un modèle de programmation linéaire en nombres entiers a été construit pour ce problème NP-difficile. Ensuite, une heuristique basée sur ajustement des navires le plus à gauche-au plus tôt et le plus à droite-au plus tôt (LRVA) et un algorithme génétique sont développés pour résoudre le problème. Des expériences numériques sur 112 instances générées aléatoirement sont menées pour analyser l’impact de la maintenance des QCs et évaluer les algorithmes proposés.
Deuxièmement, nous étudions un bi-objectif BACAP avec l’activité de maintenance des QCs, dans lequel la maintenance des QCs est effectuée hors des fenêtres de temps à cause d’un coût supplémentaire. Ce travail vise à trouver le meilleur compromis entre le temps de rotation total des navires et le coût généré par un non-respect des fenêtres de temps. Pour ce problème, un nouveau modèle de programmation linéaire en nombres entiers a été établi, et une heuristique itérative à deux phases basée sur la méthode epsilon-contrainte est conçue. Les résultats issus d’une étude de cas et de 480 instances générées aléatoirement démontrent la supériorité de l’algorithme développé.
Enfin, un nouveau BACAP avec une productivité incertaine des QCs est abordé, dans lequel seules des informations partielles sur la productivité des QCs sont connues. L’objectif est de minimiser le temps de rotation total des navires. Pour ce problème, un modèle avec chance-contrainte a été formulé. Ensuite, basé sur l’analyse du problème, le modèle proposé a été approximativement transformé en un modèle déterministe. Pour réduire l’espace de solutions du modèle, trois inégalités valides efficaces sont développées. Enfin, à partir des caractéristiques du problème, une heuristique itérative améliorée à deux phases est adapté. Des expériences numériques sur 95 instances générées aléatoirement ont été conduites pour évaluer la qualité du modèle, l’efficacité de ces inégalités valides et la performance de l’heuristique développée.
Composition du jury de thèse
| Membre du jury | Titre | Lieu d’exercice | Fonction dans le jury |
|---|---|---|---|
| Kondo Hloindo ADJALLAH | Professeur des Universités | Université de Lorraine | Examinateur |
| Eric ANGEL | Professeur des Universités | Université d’Évry, Université Paris-Saclay | Examinateur |
| Feng CHU | Professeure des Universités | Université d’Évry, Université Paris-Saclay | Directrice de thèse |
| Gilles GONCALVES | Professeur des Universités | Université d’Artois | Rapporteur |
| Antoine JOUGLET | Professeur des Universités | Université de Technologie de Compiègne | Rapporteur |
Title: Efficient models and methods for new variants of integrated berth allocation and quay crane assignment problem
Keywords : port, maintenance, uncertainty, mathematical optimization, heuristic, genetic algorithm
Abstract :
Growing global trade brings a big challenge for maritime container terminals. In terminal management, berth allocation and quay crane assignment are two key elements. Most existing researches for the integrated berth allocation and quay crane assignment problem (BACAP) assume that quay cranes (QCs) are available at any moment and QC’s productivity is deterministic. However, in practice, some QCs can be unavailable due to periodically scheduled preventive maintenance activity and QC’s productivity may be uncertain due to various factors such as weather, etc. These factors can greatly affect the container terminal performance. In this thesis, we study three new problems of BACAP with the consideration of QC maintenance activity and uncertain productivity.
First of all, we investigate a new BACAP with QC maintenance activity, in which QCs’ maintenance activities must be implemented in time windows. The objective is to minimize the total turnaround time of vessels. First, an integer linear programming model is constructed for this NP-hard problem. Next, a leftmost-earliest and rightmost-earliest vessel adjustment (LRVA) heuristic and a genetic algorithm are developed to solve the problem. Numerical experiments on 112 randomly generated instances are conducted to analyze the impact of QC maintenance and evaluate the proposed algorithms.
Secondly, we study a bi-objective BACAP with QC maintenance activity, in which performing QC maintenance outside of time windows results in additional costs. This work aims to find the best trade-off between the total turnaround time of vessels and the total cost generated by not respecting the maintenance time windows. For this problem, a new integer linear programming model is established, and an epsilon-constraint-based two-phase iterative heuristic is designed. Computational results on a case study and 480 randomly generated instances demonstrate the superiority of the developed algorithm.
Finally, a new BACAP with uncertain QC productivity is addressed, in which only partial information of QC productivity is known. The objective is to minimize the total turnaround time of vessels. For this problem, a chance-constrained model is constructed. Based on the problem analysis, the proposed model is approximately transformed into a distribution-free one. To reduce the solution space of the model, three efficient valid inequities are developed. Finally, based on the characteristics of the problem, an enhanced two-phase iterative heuristic is adapted. Numerical experiments on 95 various randomly generated instances are conducted to evaluate the quality of the distribution-free model, the efficiency of the proposed valid equalities and the performance of the developed heuristic.
- Date : lundi 06/12/2021, 14h30
- Lieu : Grand Amphithéatre du site IBGBI
- Doctorante : Ying LI, Université d’Évry Université Paris Saclay, IBISC équipe AROB@S
- Directrice de thèse : Feng CHU (PR IUT Évry, IBISC équipe AROB@S)
