Berth Allocation Problem (BAP)

Berth Allocation Problem (BAP) 

Quand un navire arrive au port, il attend son tour pour accoster au quai. Les sections du quai réservées où l’accostage s’effectue sont appelées zones d’accostage. Les problèmes d’allocation de ces zones consistent à assigner, d’une manière optimale, les navires entrant aux ports à ces postes d’accostage. Le responsable logistique est confronté alors à deux décisions : Où et Quand le navire doit-il accoster?

Classiquement, le problème est représenté par un diagramme bidimensionnel temps-espace  où les navires sont des rectangles dont les dimensions sont leurs longueurs respectives (y compris les marges de sécurité) et le temps de manutention correspondant au déchargement de leurs cargaisons. Ces rectangles doivent être placés dans l’espace de décision sans chevauchement et satisfaisant certaines contraintes. Pour la dimension spatiale, il y’a par exemple la contrainte relative à la profondeur de l’eau. Pour la dimension temporelle, les contraintes sont exprimées comme des fenêtres de temps relatives au temps de service (temps de chargement/déchargement). Ce temps de manutention dépend de la position du point d’accostage et est fonction de la distance séparant cette zone d’accostage et la zone d’entreposage des conteneurs qui vont être chargés ou déchargés. Cette dépendance affecte fortement la performance des services du port.

L’horizon de planification pour ces problèmes est d’une semaine mais le plan d’accostage doit être mis à jour quotidiennement en raison des événements imprévus qui peuvent survenir (maintenance de certaines zones du quai, non concordance des arrivées effectives avec les planifications). Le temps d’arrivée des navires est estimé à l’avance, et chaque navire a sa propre fenêtre de temps déterminée par son temps d’arrivée et la durée maximale allouée à son service (chargement/déchargement).

Les responsables de logistique veulent alors optimiser à la fois les coûts du port et des clients (armateurs) qui sont liés au temps de service. L’objectif ultime des problèmes d’allocation des zones d’accostage est donc d’optimiser l’efficacité du service sur le port pour tous les navires.

Revue de littérature relative au BAP 

Il y a presque unanimité sur le fait que l’allocation des zones d’accostage a un impact primordial sur l’efficacité des opérations sur le terminal puisque, ces zones d’accostage sont les ressources les plus importantes dans un terminal à conteneurs. De ce fait une allocation efficace des zones aux navires entrants améliore la satisfaction des armateurs et accroît la productivité du terminal. Les travaux publiés qui traitent du problème d’allocation des zones d’accostage ont démarré avec « the efficient Planning of Berth Allocation for container terminal in Asia » (Imai et al. 1997). Les auteurs ont voulu mettre l’accent sur le niveau opérationnel de la prise de décision dans la gestion d’un terminal.

Se basant sur le rapport annuel du port de Singapore de 1994, indiquant que l’un des problèmes majeurs de planification était de décider comment accoster les navires arrivant au port aux différentes sections du quai en respectant certaines contraintes, Lim (1998) présente une description du Berth Planning Problem (BPP) ainsi qu’une représentation géométrique (digramme bidimensionnel espace-temps) et une représentation de graphes du problème. Il s’appuie sur les travaux de (Garey et Johnon, 1979) pour conclure que le problème est NP complet et que la résolution par une méthode approchée (heuristique) est plus adaptée.

Dans la littérature, le problème BAP a été étudié selon deux variantes : statique et dynamique. Le problème est dit statique si on suppose que les navires arrivent au port avant que les sections de quais (berths) ne deviennent disponibles. La variante dynamique, la plus réaliste, permet que les navires arrivent au fur et à mesure de la planification, càd, avant ou après la disponibilité des zones d’accostage (Hansen, 2008). Les deux versions du problème BAP ont été étudiées chacune majoritairement selon deux classes de modèles : discret et continu. En effet, les zones d’accostage sont considérées soit comme ressources discrètes, soit comme ressources continues, dépendamment de la construction et la topologie du terminal. Selon le scénario d’une ressource discrète, les zones d’accostages sont des ressources individuelles et chaque navire doit être assigné à une seule et unique section ou zone d’accostage. Selon le scénario d’une ressource continue, le quai, lui-même, est traité comme une seule grande section à laquelle plusieurs navires peuvent s’accoster simultanément. Comparés aux modèles discrets,les modèles  continus sont plus flexibles dans le sens où les responsables logistiques sont plus libres de décider quant à l’assignation des zones d’accostage. Il y a aussi ce que Bierwith et Meisel (2010) appellent le modèle hybride.