Berth allocation with service priority

Abstract

Over the past several years, port related charges in Japanese ports have been substantially higher than those charged in other major international hub ports. All major container ports in Japan feature so-called Dedicated Terminals in which cost-effectiveness is justified by huge container volume to be handled. One of the reasons cited for high port charges is a relative decrease in handling volume compared to the terminal capacity, resulting in inefficient use of the existing capacity. The use of the Multi-User Container Terminal (MUT) concept employed in some of the major container hub ports such as Hong Kong, Pusan, Hamburg and Rotterdam reduces redundant terminal space and results in substantial cost savings in cargo handling costs and therefore is desired for ports in Japan as well. One of the key issues in the MUT operation is the berth allocation to calling vessels. In a recent study, an allocation problem for the MUT was examined, in which each vessel was treated equally. However, as some vessel operators desire high priority services, the goal of this paper is to modify the existing formulation of the berth allocation problem in order to treat calling vessels at various service priorities by developing a genetic algorithm based heuristic for the resulting non-linear problem.

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.