Berth allocation with service priority
Introduction
In major ports in Japan and the US such as Kobe, Yokohama, Los Angeles and Oakland, shipping lines lease the container terminals (referred to as Dedicated Terminal or DT) in order for them to be directly involved in the processing and handling of the containers as they aim to achieve higher productivity and economies of scale. Whereas this may be warranted in the case of a firm that handles a large amount of containers with a corresponding number of ship calls, it may not be justified if these quantities are not sufficient, as it will have an adverse effect on costs. Over the past several years port related charges in Japanese ports have been consistently higher than those in other major ports. One of the reasons cited for the increased costs is the over-investment in ports with relatively small cargo volume.
A “Multi-User Container Terminal (MUT)” may be defined as a terminal with a long berth, that is able to handle simultaneously a number of vessels which are dynamically allocated to the berth and are not always assigned to specific berth locations. Some major container ports provide an MUT, while most of them feature DTs. Examples of the MUT are Hong Kong International Terminal (HIT) in Hong Kong, Pusan East Container Terminal (PECT) in Pusan, and Delta Multi-User Terminal (DMU) in Rotterdam. In addition, most container terminals in China are used as MUTs, since the limited terminal space due to a smaller construction budget has to be utilized efficiently in order to meet huge container traffic.
An MUT can reduce the required terminal space while handling containers with the same rate of productivity as a DT, thus resulting in substantial cost savings in cargo handling costs. One of the issues that affect the efficiency of MUT operations is the berth allocation to calling vessels. The berth allocation problem (BAP) has already been addressed and solved through a subgradient optimization with a Lagrangian relaxation technique (Imai et al., 2001), in order to minimize the total service time that comprises the handling time and the waiting time for an idle berth. This problem assumed that each vessel was treated without any differentiated priority. However, according to a survey for a port authority in Japan, it became evident that vessels with a large container handling volume preferred to be given a higher priority over small vessels when the berth was congested. In general the ship priority depends on the total throughput per shipping line; therefore the ship size (actually handling volume of that ship) as an index for the priority must be regarded as an intervening variable in that it is often closely correlated to the power of the shipping company which deploys it. This is the case, for example, in Tanjong Pager container terminal of Singapore.
On the other hand, some feeder shipping companies claim that small feeder vessels are very often dominated by large vessels, and they argue that they ought to be given the same priority treatment as larger vessels and, indeed, even higher priority since their handling times are much shorter. In fact, Dalian container terminal of China, which is an MUT, provides higher priorities to small feeder vessels when the terminal is busy, resulting in less waiting time to the following vessels. This advantage is demonstrated as follows: Given the situation that two vessels with different handling volumes have just arrived at the same time, the small vessel is forced to wait for long if the big one is served first, while the latter waits for a short time if it is served second.
From the above discussion, it is clear that service priority is important in terminal operations including berth allocation, especially for a situation which involves various sizes of ships with various cargo handling volumes at a particular port of call.
Xu and Parnas (2000) provide interesting insights into priority scheduling that schedules jobs (or processes) for limited resources (or processors), assuming: (a) the scheduling is performed at run time; (b) processes are assigned fixed priorities and whenever two processes compete for a processor, the process with higher priority wins. In accordance with their paper, the best-known representative of priority scheduling is the Rate Monotonic Scheduling (Liu and Layland, 1973). Furthermore, there is another scheduling policy named the Priority Ceiling Protocol (Sha et al., 1990). The former assumes that the major characteristics of all processes are known before run-time (that is corresponding to the pre-known handling time in the berth allocation). Fixed priorities are assigned to the processes according to their periods, the shorter the period, the higher the priority. At any time the process with the highest priority among all the processes ready to run is assigned to the processor. The Priority Ceiling Protocol makes the same assumptions as Rate Monotonic Scheduling, except that in addition, processes may have critical sections guarded by semaphores, and a protocol is provided for handling them. Each semaphore is assigned a priority ceiling, which is equal to the priority of the highest priority process that may use this semaphore. The process that has the highest priority among the processes ready to run is assigned to the processors, like the Rate Monotonic Scheduling.
In these scheduling policies the priority is treated explicitly, that is, processes are selected for processing in order of priority value, and a scheduling algorithm arbitrarily determines a solution with such a priority. In fact, terms such as priority rule, heuristics, or scheduling rule are often used synonymously in the scheduling literature.
The goal of this paper is to define a solution to the objective of minimized total service time, while differentiating priorities to ships by variation of their service times (including the waiting time for an idle berth) in the solution. In this study the priority is evaluated by the resulting service time for each ship; therefore the priority should not be, in a strong sense, defined in the problem formulation like the above scheduling methods. It is not necessarily true that the priorities being given to the formulation explicitly differentiates the resulting service times for ships, because ships have different (estimated or pre-known) handling times which may depend on the berth location they are assigned and they do not always arrive at the port at the same time. Consequently, the above-mentioned scheduling approaches, with the so-called hard priority are restricted to the BAP. By contrast, this study assigns the ships a softly defined-priority, that is, weights related to their handling volumes in a BAP mathematical programming formulation.
The objective of this paper is to modify the existing BAP formulation in order to deal with calling vessels with various service priorities. For solving the BAP with priority we first examine a subgradient method using a Lagrangian relaxation technique like the one used in Imai et al. (2001). However due to its complexity in the solution process, we finally propose a genetic algorithm (GA) based heuristic.
The paper is organized as follows. The next section provides a literature review on the berth allocation planning. A mixed integer programming of the BAP without priority consideration is discussed in Section 3. The fourth section introduces a new formulation of the BAP to take into account the priority concern. Following that, we describe a Lagrangian relaxation approach for the solution, then a GA based solution method for that problem. In the fifth section a number of computational analyses are carried out, while the final section concludes the paper.
Section snippets
Literature review on the BAP
Most port studies focus their attention to the strategic and tactical issues facing the port. As many container terminals are privately operated by specific shipping lines, very few studies have been conducted on berth allocation in a multi-user terminal system.
Lai and Shih (1992) propose a heuristic algorithm for berth allocation which is motivated by more efficient terminal (actually berth) usage in the HIT terminal of Hong Kong. Their problem considers a first-come-first-served (FCFS)
Formulation
This study develops a BAP with priority consideration based on the dynamic version of the BAP (Imai et al., 2001). This section overviews the formulation of the BAP without priority consideration, in order to assess the difficulty in the formulation and solution methodology for the BAP with priority consideration (PBAP).
There are some evaluation criteria to measure berth (or terminal) productivity such as the total handling time and the total service time that includes not only the handling
Formulation of the PBAP
The BAP discussed in the previous section treats ships without distinctive priority. That is, no service priority in terms of ship size, handling volume, etc. is taken into account when determining the berth allocation. However, as previously mentioned there are arguments for differentiating the treatment of vessels. For example, Tanjong Pager container terminal in Singapore is operated as an MUT, but with a higher priority assigned to ships with large handling volume. On the other hand, Dalian
Solution procedure
This section describes a solution procedure of the PBAP. As the BAP that is modified to model the PBAP was solved by the subgradient procedure with a Lagrangian relaxation to the BAP formulation in Imai et al. (2001), we first attempt to develop a Lagrangian relaxation formulation to the PBAP, in order to look into the availability of the subgradient procedure.
Numerical experiments
The solution procedure is coded in “C” language on a Sun SPARC-64G workstation. Problems used in the experiments were generated randomly, but systematically. We developed four basic problems in which 25, 50, 75, and 150 calling ships are served with various handling volumes at an MUT with five berths. Two data sets of ship sizes (actually container handling volume at the terminal being considered) were prepared for each of the four arriving ship sets. In one data set (Ship data A), the ship
Conclusions
In this study, we examined how the service priority can be incorporated into the BAP. The existing dynamic berth allocation formulation was extended in order to take the service priority into account in the objective function. The resulting formulation became non-linear and was difficult to solve. First we discussed how the problem was reduced to a Lagrangian relaxation problem in order to look into the availability of the subgradient optimization. Although the subgradient method was adaptable
References (28)
- et al.
A greedy genetic algorithm for the quadratic assignment problem
Computers and Operations Research
(2000) - et al.
On the quality of local search for the quadratic assignment problem
Discrete Applied Mathematics
(1998) - et al.
Approximating the maximum quadratic assignment problem
Information Processing Letters
(2001) - et al.
Network-based formulations of the quadratic assignment problem
European Journal of Operational Research
(1998) - et al.
A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
European Journal of Operational Research
(1998) - et al.
The dynamic berth allocation for a container port
Transportation Research Part B
(2001) - et al.
Constrained neural approaches to quadratic assignment problems
Neural Networks
(1998) The berth scheduling problem
Operations Research Letters
(1998)- et al.
Berth allocation planning in the public berth system by genetic algorithms
European Journal of Operational Research
(2001) Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem
SIAM Journal on Optimization
(2000)
A new bound for the quadratic assignment problem based on convex quadratic programming
Mathematical Programming, Series A.
Optimizing ship berthing
Naval Research Logistics
Optimizing submarine berthing with a persistence incentive
Naval Research Logistics
Solving large quadratic assignment problems in parallel
Computational Optimization and Applications
Cited by (255)
Dynamic berth allocation under uncertainties based on deep reinforcement learning towards resilient ports
2024, Ocean and Coastal ManagementIntegrated operation models with quay crane maintenance in a container terminal
2024, Ocean and Coastal ManagementDistributionally robust chance-constrained optimization for the integrated berth allocation and quay crane assignment problem
2024, Transportation Research Part B: MethodologicalBerth and quay cranes allocation problem with on-shore power supply assignment in container terminals
2024, Computers and Industrial EngineeringUnmanned surface vehicles (USVs) scheduling method by a bi-level mission planning and path control
2024, Computers and Operations Research