The Berth Allocation Problem with Service Time and Delay Time Objectives

This study addresses a two-objective berth allocation problem: ship service quality expressed by the minimisation of delay in ships' departure and berth utilisation expressed by the minimisation of the total service time. In this problem, noninferior solutions are expected to be identified. Two heuristics, which are implemented based on two existing procedures of the subgradient optimisation and genetic algorithm, are proposed for solving this problem. Through numerical experiments, it was found that in most cases the genetic algorithm outperformed the subgradient optimisation. Also the tight time window yielded noninferior solutions.

This research was partially supported by the JSPS Grant-in-Aid for Exploratory Research Grant 19656232.

Authors and Affiliations

1. Graduate School of Maritime Sciences, Kobe University, Fukae, Higashinada, 658-0022, Kobe, Japan

   Akio Imai, Jin-Tao Zhang & Etsuko Nishimura

2. World Maritime University, PO Box 500, Malmo, S-201 24, Sweden

   Akio Imai

3. Department of Maritime Studies, University of Piraeus, 80 Karaoli & Dimitriou Str., Piraeus, GR185 32, Greece

   Stratos Papadimitriou

Appendix A

BAP WITH THE OBJECTIVE OF THE TOTAL SERVICE TIME

The BAP with the objective of minimising the total service time to be solved by SP and GA is formulated as follows:

where i(=1, …, I)∈B is the set of berths; j(=1, …, T)∈V is the set of ships; k(=1, …, T)∈U is the set of service orders; A _j is the arrival time of ship j; P _k is the subset of U such that P _k ={p∣p<k∈U}; S _i is the time when berth i becomes idle for the planning horizon; W _i is the subset of ships with A _j ≥S _i ; C _ij is the handling time spent by ship j at berth i; x _ijk is =1 if ship j is served as the (T−k+1)th last ship at berth i, and =0 otherwise; y _ijk is the idle time of berth i between the departure of the (T−k+2)th last ship and the arrival of the (T−k+1)th last ship when ship j is served as the (T−k+1)th last ship.

The decision variables are x _ijk 's and y _ijk 's. Objective (A.1) minimises total service time. Constraint set (A.2) ensures that every ship must be served at some berth in any order of service. Constraints (A.3) ensure that every berth serves up to one ship at any time. Constraints (A.4) ensure that ships are served after their arrival. For the detailed derivation of the formulation, see Imai et al (2001, 2005a). [PS] models the BAP with the minimisation of the total service time, which exactly corresponds to (1), (6), (7), (8), (9), (10) and (11), (13) and (14) in [P].

Appendix B

SUBGRADIENT OPTIMISATION

In SP, in order to find an approximate solution for [PS], its Lagrangian relaxation [PR], which is defined as follows, is solved iteratively by changing Lagrangian multipliers updated by the previous iteration.

where λ _ijk (≥0) is a Lagrangian multiplier for berth i, ship j, and service order k.

This formulation can be rewritten as follows, because y _ijk 's are redundant as they are not in any constraints.

Problem [P1] is further reformulated by introducing representative cost in the objective function, where E _ijk is the representative cost.

In summary, by relaxing constraint set (A.4) of formulation [PS], [PS] becomes a three-dimensional assignment problem [P2] that is further reduced to the classical two-dimensional assignment problem and therefore easily solved. For the outline of the SP, see Imai et al (2001).

Appendix C

GA

The GA is outlined in Figure C1, where a chromosome is represented as Figure C2. In Figure C1, the numbers in cells represent ship numbers as served from the left cell. ‘0’ in cell 5 is a separated that divides service orders in berth 1 and those in berth 2.

GA procedure.

Full size image

Chromosome representation.

Full size image

Reprints and permissions