Selecting algorithms for large berth allocation problems

Jakub Wawrzyniak, Maciej Drozdowski and Éric Sanlaville

European Journal of Operational Research, 2020, vol. 283, issue 3, 844-862

Abstract: This paper considers algorithm selection for the berth allocation problem (BAP) under algorithm runtime limits. BAP consists in scheduling ships on berths subject to ship ready times and size constraints, for a certain objective function. For the purposes of strategic port capacity planning, BAP must be solved many times in extensive simulations, needed to account for ship traffic and handling times uncertainties, and alternative terminal designs. The algorithm selection problem (ASP) consists in selecting algorithms with the best performance for a considered application. We propose a new method of selecting a portfolio of algorithms that will solve the considered BAP instances and return good solutions. The portfolio selection is based on the performance on the training instances. The performance is measured by the runtime and solution quality. In order to select the portfolio, a linear program minimizing the solution quality loss, subject to overall runtime limit is used. Thus, the portfolio evolves with the runtime limit, which is a key parameter in designing the port capacity simulations. For the training and validating datasets, random instances and real ship traffic logs are used. A portfolio of heuristics is developed which can be used for solving large instances of BAP, emerging when time horizons of months or years are considered. The evolution of the algorithm portfolios under changing runtime limits is studied. The portfolio abilities to solve new instances are assessed.

Keywords: Scheduling; Heuristics; Algorithm selection problem; Berth allocation problem; Quality-runtime trade-off; Algorithm portfolios (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719309671
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:283:y:2020:i:3:p:844-862

DOI: 10.1016/j.ejor.2019.11.055

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().