Selecting Algorithms for the Efficient Solving of Large Berth Allocation Problems - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Selecting Algorithms for the Efficient Solving of Large Berth Allocation Problems

Résumé

In this presentation, the algorithm selection for the berth allocation problem (BAP) under solution time limits is considered. BAP consists in scheduling ships on berths subject to ready times and ship size constraints, in minimum turnaround time. For the purposes of strategic port capacity planning, BAP must be solved many times in extensive simulations, needed to account for uncertainties on ship traffic, handling times, and also to consider alternative terminal designs. Exact methods exist that solve BAP problems on medium size instances in a few minutes. However, theses methods cannot be adapted to solve many large instances in a short time limit. Even metaheuristics may be too consuming in this setting. The Algorithm Selection Problem (ASP) is the challenge of selecting algorithms with the best overall performance for the considered application. An approach is proposed here to select a portfolio of algorithms, that will each solve the considered BAP instances and return good solutions. The portfolio is built thanks to training instances. The performance is measured by runtime and solution quality. A linear program minimizing the solution quality loss, subject to overall runtime limit, is used to select the portfolio. Thus, the portfolio evolves with changing runtime limits, which is a key design decision in the simulations. For the training and validating datasets, random instances and real ship traffic logs are used. In our experimental study, a portfolio of heuristics is developed which can be used to solve efficiently very large instances of BAP, emerging when time horizons of months or years come into consideration. The evolution of the algorithm portfolios under changing runtime limits as well as their ability to solve new instances are studied.
Fichier principal
Vignette du fichier
LOGMS_2019_Abstract_Sanlaville.pdf (27.67 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02352354 , version 1 (06-11-2019)

Identifiants

  • HAL Id : hal-02352354 , version 1

Citer

Jakub Wawrzyniak, Maciej Drozdowski, Eric Sanlaville. Selecting Algorithms for the Efficient Solving of Large Berth Allocation Problems. 9th International Conference on Logistics and Maritime Systems, Aug 2019, Singapour, Singapore. ⟨hal-02352354⟩
45 Consultations
28 Téléchargements

Partager

Gmail Facebook X LinkedIn More