General Information
This page comprises supplementary information for the Algorithm Selection Problem
(ASP) for large Berth Allocation Problem (BAP).
More on the problem, test instance generation, algorithm portfolio construction
and evaluation, can be found in:
J.Wawrzyniak, M.Drozdowski, E.Sanlaville,
Selecting Algorithms for Large Berth Allocation Problems, 2019,
European Journal of Operational Research,
Volume 283, Issue 3, 16 June 2020, Pages 844-862
https://doi.org/10.1016/j.ejor.2019.11.055
Test Instances
Values of the following parameters were drawn (pseudo)randomly:
• ship ready times, r_j,
• ship processing times, p_j,
• ship importance(or value, weight), w_j,
• ship and berth lengths L_i,\lambda_j.
Collections of the instances:
• random instances N - in order to test impact of the number of ships
n, the range of n has been swept by visiting
n=2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000.
For each test value of n, 100 test instances were generated.
The remaining parameters r_j, p_j, w_j, \lambda_i, L_j, were generated pseudorandomly
as follows: m~U[1,100], r_j~U[0,1000], p_j~U[1,24], w_j~U[1,1000],
L_j~U{200; 215; 290; 305; 400}.
By U[a,b] we denote that certain parameter is generated from discrete uniform
distribution with integer values in range [a,b].
~U{a,...,b} denotes that the parameter values are chosen with discrete uniform
distribution from the set {a,...,b}.
In the collection of 1200 random instances N, a subset of the instances with
n=10000 has been singled out.
The former set of all random instances N is called dataset 1,
the latter set of n=1000 instances is called dataset 2.
• random instances M - were generated to test the impact
of the number of berths m.
The range of m has been swept by assuming
m=1,2,5,10,20,50,100
while the remaining parameters r_j, p_j, w_j, \lambda_i, L_j,
were randomized as described above.
For each test value of m, 100 test instances were generated.
In the collection of 700 random instances M, a subset of the instances with
m=2 has been singled out.
The former set of all random instances M is called dataset 3,
the latter set of m=2 instances is called dataset 4.
• real instances - ship arrivals of Gdynia,
Long Beach, Los Angeles, Le Havre, Hamburg, Rotterdam,
Shanghai, Singapore over 2016.
Instance File Format
Instance files are text files with data in the following order:
- 1st line: number of the ships (n)
- lines 2 to n+1 - ship data (in the order): id (j), ready time (r_j), length (\lambda_j), processing time (p_j), weight (importance, w_j), ship owner (o_j - can be ignored)
- line n+2: number of berths (m)
- line n+2 (the last line): berth lengths from the first to the last (L_1,...,L_m)
File Name Convention
• Random instances N are named:
ship#ninst#.txt
where
ship# is the number of ships (n),
inst# is the number of the instance generated for the current value of n.
• Random instances M are named:
berth#minst#.txt
where
bert# is the number of berths (m),
inst# is the number of the instance generated for the current value of m.
• Real instances - filenames derived from port names.
The instances are collected in the following files
| # | instances | comments |
|---|---|---|
| 1. | instances-Nall.zip | all random instances N - dataset 1, 16.1M |
| 2. | instances-N10k.zip | n=2 random instances N - dataset 2, 8.4M |
| 3. | instances-Mall.zip | all random instances M - dataset 3, 3.1M |
| 4. | instances-M2.zip | m=2 random instances N - dataset 4, 0.4M |
| 5. | instances-real.zip | 8 real port instances - dataset 5, 0.4M |
Portfolios
All the algorithm portfolios, and their performance scores, for the considered
problem are shown in this report:
J.Wawrzyniak, M.Drozdowski, É.Sanlaville,
Algorithm Portfolios for Large Berth Allocation Problem Instances,
Institute of Computing Science,
Poznan University of Technology,
Research Report RA-7/18, 2018.