Face à la globalisation du monde, de plus en plus d'échanges de marchandises sont réalisés entre les différentes parties de la planète. Cette forte augmentation des volumes à acheminer oblige les ports à se réinventer pour gagner en efficacité. Afin de gagner en rapidité, des solutions automatisées peuvent être proposées pour le transfert des conteneurs entre les quais, où se trouvent les navires, et les espaces de stockage du port. Ces solutions utilisent des véhicules automatisés, les AGVs (Automated Guided Vehicles), ainsi que des conteneurs de taille standardisée. Il est ainsi nécessaire d'optimiser les trajectoires de ces AGVs tout en évitant les situations bloquantes (ex : deux AGVs ne doivent pas entrer en collision).

Le port étudié dans ce problème est composé de trois zones principales : les zones de stockage, les quais, et, entre elles, une zone de circulation dédiée aux AGVs (voire figure 1). Nous considérons un ensemble de m missions et autant d'AGVs. Chaque mission correspond soit à une tâche de chargement (ramener un conteneur d'une zone de stockage vers un des quais), soit à une tâche de déchargement (ramener un conteneur d'un des quais vers une des zones de stockage) des navires. Nous considérons que chaque AGV est affecté à une mission et est déjà positionné au point de départ de celle-ci. Deux missions n'ont pas les mêmes points de départ ou d'arrivée, mais le point de départ d'une mission peut être le point d'arrivée d'une autre. L'objectif du problème considéré est donc de calculer les trajectoires des AGVs permettant d'éviter les collisions tout en minimisant le makespan. 

Contrairement à la majorité des articles qui traitent ce problème en se plaçant dans un cas unidirectionnel (les différents tronçons ne peuvent être traversés que dans une unique direction prédéfinie, ce qui limite les conflits potentiels ([1]), nous souhaitons étudier le cas bidirectionnel ([2,3,4]) qui représente mieux la réalité du port étudié. De plus, nous nous basons sur la structure particulière du port de Dunkerque illustrée sur la figure 1 alors que les travaux de la littérature se basent soit sur des grilles, soit sur des graphes simplifiés composés d'une ligne horizontale pour les quais, d'une autre pour les zones de stockage, et d'un ensemble de lignes verticales pour faire le lien entre les deux parties. Enfin, dans l'état de l'art, le nombre d'AGVs est généralement réduit (inférieur ou égal à 60).

Pour l'environnement portuaire étudié, un programme linéaire mixte en nombres entiers (MILP) a été proposé par [5], améliorant celui de [6]. Ce modèle s'avère efficace pour de petites instances, mais ses performances se dégradent fortement lorsque le nombre de missions augmente. Pour traiter des instances de plus grande taille, une méthode basée sur la construction d'une solution initiale ainsi que sur l'utilisation d'une recherche locale appelée IPR a alors été introduite par [7]. La construction de la solution initiale consiste à calculer le plus court chemin pour chaque AGV sans tenir compte des conflits, puis à ajouter des temps d'attente le long des trajectoires fixées pour éviter les collisions. Une telle procédure ne garantit pas l'obtention d'une solution sans aucune collision, et il arrive en pratique qu'aucune solution réalisable ne soit obtenue. Les tests numériques montrent qu'IPR permet d'aboutir à des solutions de bonne qualité lorsqu'une solution initiale réalisable lui est fournie.

Notre objectif est d'être capable de déterminer rapidement une solution initiale réalisable, i.e. sans collision, quelle que soit l'instance du problème.