Selecting Algorithms for the Efficient Solving of Large Berth Allocation Problems

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02352354
Contributor : Eric Sanlaville <>
Submitted on : Wednesday, November 6, 2019 - 6:17:43 PM
Last modification on : Saturday, November 9, 2019 - 1:58:44 AM

File

LOGMS_2019_Abstract_Sanlaville...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02352354, version 1

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

6