INTRODUCTION

Sea-borne container shipping plays a major and important role in the world transportation system and the global supply chain. A container terminal, as a nodal point in the transportation network, acts as an interchange of the different modes involved in the overall transportation process; therefore, efficiency and productivity improvements in terminal operations are crucial in reducing the overall trip duration and costs and have thus been gaining more attention lately.

This paper deals with efficient berth scheduling (or berth allocation), which determines an assignment of calling ships to berths for cargo handling. The primary aim of a terminal is a quick turnaround of calling ships. Also, the terminal attempts to utilise its costly infrastructure efficiently. Most decision-making tasks have a multi-objective nature. In a multi-user container terminal (MUT), the terminal operator primarily aims to maximise customer satisfaction (calling ships objective), while improving berth usage (his own internal objective).

The former objective may be represented by the customer's (ie, calling ship's) satisfaction. In container shipping service, the fast transit time from an origin port to a destination port is the first concern for shippers and consignees. However, it is equally important to keep port calling on schedule. In this respect, ship departure needs to be kept on schedule. Any delay in departure results in late arrival at the next port and consequently late departure from that port. After repeated delays at calling ports, ships suffer from a substantial delay at the final port to be called during a specific voyage, but even more important is that those containers that need to be transhipped to other vessels at hubs may lose their planned connection. Thus, the secured punctual departure schedule may be the ultimate goal of the shipping lines and this is the reason why shipping companies request committed time windows of service at the terminal. From the above discussion, the first of the two objectives is the minimisation of the delay in ships' departure.

For a terminal, the second objective, which is efficient berth usage, is vital to its competitiveness. As the berth construction costs are much higher than the costs associated with the required superstructure of the terminal, proper berth utilisation, that is, no berths are consistently under-utilised or over-utilised, is a major concern to the operator. The berth occupancy rate effectively indicates the level of berth utilisation, which is the total time when the berth is occupied by ships, over a given time period. However, there is a drawback in using this indicator, as in some cases ships may remain at a specific berth for a longer period of time, due to handling equipment limitations. For example, a particular ship that needs 10 h for loading and unloading at a specific berth may have to spend 12 h at another berth. In this context, the berth occupancy rate could be artificially increased by allocating this ship to undesirable berths despite the resulting unsatisfactory service. In other words, the increase in occupancy rate is correlated with the increased handling time; however, this obviously results in the waste of expensive port infrastructure. Therefore, higher utilisation is properly achieved by allocating as many desirable berths to ships as possible, and as a result this allocation principle minimises the total service time that consists of the waiting time for idle berths and the handling time of ships at their allocated berths. In summary, the minimisation of the total service time is considered as an indicator of efficient berth usage.

Based on the above discussions, this study addresses the berth allocation problem (BAP) with two objectives: the minimisation of total delay time in ship departure and the minimisation of total service time. We deal with these objectives independently for the following reason: Generally speaking, when a terminal operator evaluates his service level, he places different values to different ships. For instance, if a ship has a larger capacity with more cargo than another, the former is more valuable than the latter in a general sense. Therefore, the evaluation criterion in berth scheduling should take into account such ship characteristics as ship weight. The less the total service time, the less the total delay time in departure in the case of ships of equal weight. However, the total weighted delay time in departure is not necessarily proportional to the total service time. In other words, these times may conflict each other. This property is demonstrated in a later section. The property of the total weighted delay time and total service time asks the decision maker to find a set of noninferior solutions in terms of the two objectives. In order to identify the noninferior solution set, this paper employs two solution methods that have already been developed in existing studies for a single objective BAP.

The paper is organised as follows. The next section provides a literature review on berth allocation planning. A mixed integer programming of the BAP with two objectives is discussed in the subsequent section. This is followed by the next section that introduces solution methods for the problem. In the following section, a number of computational analyses are carried out, while the final section concludes the paper.

LITERATURE REVIEW

As there is an ever-growing demand for more efficiently operating MUTs, due to the continuous increase in container traffic, issues pertaining to the efficient berth allocation at an MUT have been receiving much attention lately.

Lai and Shih (1992) proposed 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) allocation strategy, which is not the case in our problem. Brown et al (1994, 1997) examined ship handling in naval ports. However, those studies seem inappropriate for commercial ports since the assumption made in the studies are not so common in commercial ports. Imai et al (1997) addressed the BAP in discrete index referred to as BAPD for commercial ports. They concluded that in order to achieve high port productivity, an optimal set of ship-to-berth assignments should be found without employing the FCFS rule. However, this principle may result in certain ships being dissatisfied with their order of service. In order to deal with the two conflicting evaluation criteria, that is, berth performance and dissatisfaction with the order of service, they developed a heuristic to find a set of noninferior solutions that maximise the former and minimise the latter. Their study assumes a static situation, where ships to be served for a planning horizon have all arrived at the port before the berth allocation planning process. Imai et al (2001, 2005a) extended the static version of the BAPD into a dynamic treatment that is similar to the static treatment, but with the difference that some ships arrive while work is already in progress. Their study assumes the same water depth for all berths, although in practice certain ports have berths with different water depths. Nishimura et al (2001) extended further the dynamic version of the BAPD for the multi-water depth configuration. They employed genetic algorithms (GAs) to solve that problem.

In some real situations, the terminal operator assigns different priorities to calling vessels. From this point of view, Imai et al (2003) extended the BAPD in Imai et al (2001, 2005a) to treat ships with different priorities and examined how the extended BAP differentiates ship handling in terms of their associated service time. In Imai et al (2007) the multiple ship treatment in the BAPD like Nishimura et al (2001) is applied to the indented terminal with a simple procedure to deal with small ships at indented berths. Also, comparisons in terminal performance between indented and conventional terminals are made. Imai et al (2008) studied efficient berth allocation at an extremely busy container terminal in a developing country where the berth capacity is very limited to handle a lot of calling ships. They considered berth allocation at the terminal, which allocates some ships to another terminal.

There is also another type of approach to the BAP, which is the one with a continuous location index (referred to as BAPC). There are some existing studies such as Lim (1998), Li et al (1998), Guan et al (2002), Park and Kim (2002), Kim and Moon (2003), Park and Kim (2003), Imai et al (2005b) and Cordeau et al (2005). Although the BAPC solution is more practical and efficient than the BAPD, the former is more complex than the latter in terms of problem definition and solution technique.

In closing this section, we note that there is only one BAP study with multiple objectives, that is, Imai et al (1997). The objectives in that study are similar to those of this study. In fact, one of the two objectives in both studies, that is, the total service time, is the same. Also, the second objective is nearly the same for the customer's (calling ship's) satisfaction (or dissatisfaction). Actually that objective in Imai et al (1997) is the dissatisfaction of service order for berthing and handling, while the one in this study is delay in ship's departure. We also want to notice the following discussion: regarding these issues with ship operators, it was mentioned that there are cases where earlier arriving ships are kept waiting till late arrival ones are berthed and served at berths. Nevertheless, it was also mentioned that such an overtaken service may be acceptable as long as the committed departure time is guaranteed. From this point of view, the minimisation of delay must be a more practical concern. In fact, as reviewed in this section, some existing studies addressed this issue. Note that the problem in Park and Kim (2002) has one objective, which consists of the costs related to delay time and the ones relative to berthing at an undesirable berth. While these two issues are evaluated as a single objective in a combined manner, they correspond (not exactly the same) to the two objectives to be evaluated in this study. However, as will be discussed later, these two issues are basically contradictory and therefore it is valuable that noninferior solutions are presented to the decision maker, in order to assist him in making more informative decisions.

PROBLEM FORMULATIONS

Overview

This study assumes that the handling time of a ship is dependent on the berth where the ship is served. As mentioned before, the BAP we address here deals with two objectives: one for customer satisfaction and the other for terminal efficiency.

For the former objective, the model serves ships within respective time windows of service as long as possible. Similar treatment of ships served within windows is performed in Park and Kim (2003), where penalty costs are incurred to early or late start of ship handling against the estimated times of ship arrival (which correspond to the beginning of the windows) and late departure from the terminal beyond the committed departure time (the end of the windows). On the other hand, this study is not concerned with the beginning of the time window, since secured departure on schedule is most important for ships.

For the latter objective, this study adopts the minimisation of the total service time of ships. Note that if the handling time of each ship did not depend on the berth, the total service time would remain unchanged regardless of the berth allocation. However, as this study assumes a dependent handling time, the total service time depends on the berth allocation.

As will be shown in the next sub-section, these two different objectives conflict with each other. This is the reason why this study treats these objectives independently. Also notice that this study does not explicitly charge the penalty costs incurred for a delayed departure as in Park and Kim (2003) because it is not easy to measure the penalty cost associated with each ship. This kind of treatment may be a future research topic. If the cost should be implicitly taken into consideration for practical application, the weight to be used in the delay-related objective in this study could be interpreted as the penalty cost. We introduce the weight in our BAP model to differentiate the level of dissatisfaction of ships, where the weight may be able to be defined based on ship size class or ship's expected handling time.

Relationship between total service time and delay in departure

For reference purposes, we prove here that the minimisation of total service time results in the minimisation of total delay time in ship departure when the weight is not taken into account.

Property 1:

The minimisation of total service time results in the minimisation of total delay time.

Proof:

Ship j's delay in departure, d_j, is defined as in equation (1):

where f_j is the completion time of handling ship j and F_j is the expected departure time of ship j.

Thus, the total delay over all calling ships (TD) is

where V is the set of ships.

In this study, F_j is assumed to be the ship departure time when the ship is served at the best berth (with the minimum handling time among others) as soon as it arrives at the port, that is,

where A_j is the arrival time of ship j and C_ij is the handling time spent by ship j at berth i.

As total service time (TST) is defined as the sum of the service times of ships, which is the time gap between ship arrival and departure, we have the following equality:

By equations (2) and (3), we have

As is constant for ship j, TST is proportional to TD. 

As demonstrated in the remark below, the minimisation of total service time does not result in the minimisation of the total delay time in ship departure when the weight is applied to the delay time.

Remark There is the case that the minimisation of total service time does not lead to the minimisation of total delay time. Consider the situation illustrated in Figure 1, where there is only one berth with two incoming ships A and B: ship A arriving at 1 p.m. with handling time of 10 h and ship B arriving at 2 p.m. with 4 h handling. There are two possible berth schedules: schedule 1 (ship A first and ship B next) and schedule 2 (ship B first and ship A next). The total service time for schedules 1 and 2 are 23 and 19 h, respectively. If their weights are all 1, the weighted delay in departure for both schedules are 9 and 5 h, respectively (see D-1 in Figure 1). However, in the case of different weights (3 for ship A and 1 for ship B), the weighted delays turn to be 9 and 15 h, respectively (see D-2).

Figure 1.

Service time and delay of departure.
Note: ST=service time (waiting time+handling time); D-1=Delay of departure (all ship weights=1); D-2=delay of departure (ship A's weight=3, ship B's weight=1).

Full figure and legend (53K)

From the above discussion, it is true that the two objectives are in conflict with each other, and therefore we should deal with them independently.

Formulation

There are two types of BAPs: discrete and continuous indexes. The discrete one has some drawbacks over the continuous one; however, one of the advantages is easiness of solution. The less flexible or inefficient solution in terms of berth space utilisation is found by the discrete BAP, but the discrete solution can be modified manually or theoretically based on Imai et al (2005a, 2005b). From this point of view, this study adopts the discrete berth index. Also, this treatment is justified by the fact that as shown in Imai et al (2008), at a busy container terminal with various sizes of calling ships, mooring locations are basically specified by berth.

The assumptions made in this study are:

1. The berth allocation ignores the FCFS rule
2. Each berth can handle one ship at a time
3. The handling time of a ship depends on its allocated berth
4. The handling of a ship is performed continuously without any interruption

Regarding assumption (2), usually a container terminal serves multiple small ships at a single berth at the same time if the ship and berth length restrictions are satisfied. From this point of view, the authors have already studied the BAP with such a constraint in Nishimura et al (2001). However, major container terminals, for example, port of Colombo, have very few cases of multiple ships to be served at a single berth at the same time. This justifies assumption (2).

The BAP formulation with two objectives is made based on the following notation:

i(=1, ..., I)B:

set of berths

j(=1, ..., T)V:

set of ships

k(=1, ..., T)U:

set of service orders

_j:

weight for ship j

S_i:

time when berth i becomes idle for the planning horizon (S_i0 assumed)

TM:

large constant

b_ijk:

start time of handling ship j at berth i as the kth ship

f_ijk:

completion time of handling ship j at berth i as the kth ship

x_ijk:

=1 if ship j is serviced as the kth ship at berth i, =0 otherwise

The two objective BAP may be formulated as follows:

where b_ijk+C_ijx_ijk=f_ijk for iB, jV, kU and _jVf_ij0=S_i for iB.

Notice that both the sets of ships and service orders have the same number of elements T because a feasible solution may assign all the ships to a particular berth even though a number of berths are provided in the system.

Decision variables are x_ijk's, b_ijk's, f_ijk's and d_j's. Objective (5) minimises the total of delay, in hours, of ships from the estimated departure time, whereas objective (6) minimises the total service time of ships. Constraint set (7) ensures that every ship must be served at some berth in any order of service. Constraints (8) enforce that every berth serves up to one ship at any time. Constraints (9) assure that a ship starts its handling after arrival. Constraints (10) define that the kth ship begins its handling at berth i after the (k-1)th ship finishes its handling. Constraints (11) ensure that b_ijk is set to 0 if its corresponding x_ijk=0, and set to a completion time otherwise. Constraint set (12) defines the delay of departure. Note that d_j may be negative if the actual departure time of ship j, that is, _iBkUf_ijk, is earlier than the estimated departure time, F_j. This is contradictory to the assumption that the time gap in the case of early ship departure is not taken into account. Therefore, d_j=0 if F_jiBkUf_ijk and this is guaranteed by constraints (15). Whether F_jiBkUf_ijk or not, d_j may have a large number, but it does not because of objective (5).

SOLUTION METHOD

There are some methods to identify a set of noninferior solutions. One of the well-known methods is the weighting method (Cohon, 1978), which solves a formulation that combines the two objectives as a single objective by using weights for different objectives. By changing those weights, it produces noninferior solutions. This method is, however, useful only when the combined formulation can be solved easily.

The authors have already developed two heuristics for a discrete indexed BAP with the objective of minimisation of the total service time: one by a subgradient optimisation procedure (SP) using a Lagrangean relaxation (Imai et al, 2001 and 2005a) and the other by GA in Nishimura et al (2001).

The SP iterates the process that builds a (better) feasible solution by modifying an infeasible solution as an optimal solution to the relaxed problem of the original problem to be solved. Through this iterative process, it improves the feasible solution and as a result it builds a lot of feasible solutions before reaching the final solution.

The GA is also an iterative procedure, where by changing chromosomes (solutions), superior chromosomes are handed over from a generation to the next generation during a predetermined number of generations and eventually the best chromosome is left at the end of process. In both solution methods, a number of feasible solutions are generated in the course of computation.

The weighting method for finding a noninferior solution set essentially generates a lot of feasible solutions, which are not necessarily optimal in terms of multiple objectives, at the same time. Therefore, it is a natural idea that the generating multiple feasible solutions by SP or GA is a substitution for the weighting method. For this computational property, in this study we utilise both SP and GA (for computational comparisons) to find some feasible solutions and then select noninferior solutions among the feasible ones.

The BAP with the objective of the total service time to be solved by SP and GA is formulated in Appendix A. The outlines of SP and GA procedures are summarised in Appendices B and C. As the computation procedure that selects noninferior solutions from the feasible ones is straightforward, we do not explain it further (cf Cohon (1978) for more).

Note that the GA developed in Nishimura et al (2001) solves an extended version of the BAP, which is solved by SP in Imai et al (2001), where the BAP by the GA allows multiple ships to be moored at a berth subject to ship and berth length constraints. Of course, this version of the BAP can be applied for the BAP with a single ship at a berth in this study.

NUMERICAL EXPERIMENTS

The programme codes for both SP and GA were implemented in 'C' language and they ran on PRIMEPOWER250 (made by Fujitsu Co.) equipped with a CPU of SPARC64 V.

We carried out experiments with 24 calling ships that arrive randomly at the terminal (four berths) with an exponential distribution of the average arrival interval of 7 h. This scenario corresponds to ship callings during 1 week. In addition to this basic scenario, we provide other scenarios with more frequent ship calling such as arriving intervals of 3 and 5 h. Note that in every scenario we generate 24 calling ships in order to examine resulting solutions on a common basis. The time span between the first arriving ship and the last ship in the case of arrival intervals of 3, 5 and 7 h are 58, 97 and 170 h, respectively. The ship handling time C_ij is generated randomly by a uniform distribution with the average values of 5, 7 and 9 h. A weight for ship j, _j, is defined by .

In total, we perform the experiments with nine cases based on different arrival interval and handling time settings. For each case, five different expected departure times are assumed based on the standard time plus different deviations such as +0, +3, +6, +9, +12. The standard time for the expected departure time of ship j, F_j, is set as the earliest departure of ship j when the ship starts its handling as soon as it arrives at the berth of the minimum C_ij, that is, , regardless of the berth's availability.

As mentioned before, two solving algorithms are engaged in order to identify the noninferior solution set and after that the solution outputs produced by both algorithms are compared. Figures 2, 3 and 4 show the results (ie, the service time and weighted delay time per ship) for three different arrival intervals. As it is easily seen, the service time increases by decreasing the arrival interval and increasing the handling time, both of which cause congested situations at the terminal. Comparing the results by SP and GA, we observe that the GA completely outperforms the SP. However, the solution gap between SP and GA is decreasing by increasing the arrival interval. For instance, the service time gap is 60% of the service time by SP in the case of the arrival interval=3 h and the handling time=9 h, while it is 10% in the case of the arrival interval=7 h and the handling time=9 h. The delay time gap also has such a trend, except for some cases. It is 80% of the delay time by SP in the case of the arrival interval=3 h and the handling time=9 h, whereas it is 10% in the case of the arrival interval=5 h and the handling time=9 h. We thus ascertain that in especially the service time, the GA constantly performs well with different situations of terminal congestion.

Figure 2.

Solutions for arrival time interval of 3 h.

Full figure and legend (92K)

Figure 3.

Solutions for arrival time interval of 5 h.

Full figure and legend (91K)

Figure 4.

Solutions for arrival time interval of 7 h.

Full figure and legend (92K)

For both GA and SP, in general the noninferior solutions are likely found in busy terminal states such as the cases of arrival interval of 3 h with all the different handling time scenarios as well as the cases of other arrival intervals with the handling time of 9 h. In the BAP, as one of the two objectives is the minimisation of the total service time, ships are likely allocated to berths with the minimum handling time being offered to them. In not busy situations, this allocation principle is firmly realised, resulting in the minimum delay in departure since in this solution ships can depart much earlier than in other solutions. On the other hand, in busy states of the terminal the limited quay space is shared by a lot of calling ships during a short period and therefore some ships compete with others to obtain the best berths for them. These results in that a number of ships are not likely allocated to their favourite berths. Consequently, while the total service time is minimised (not necessarily optimal due to the heuristics used in this study), ships not at preferable berths are delayed in departure. Alternatively, when ships with a large volume of cargo to be handled are allocated to preferable berths in a solution at a busy terminal, the total delay time of all the ships (therefore the average delay time per ship) is minimised. However, in this solution other ships are not allocated to desired berths or are served after ships with a lot of cargo; therefore, other ships suffer from long waiting and as a result total service time becomes long. These two solutions turn out to be noninferior in nature.

Figure 5 shows GA solutions in the case of the arrival interval of 7 h with the handling time of 9 h. As can be easily seen, a large F_j leads to a short delay. Also, it is found that when F_j is small, noninferior solutions are likely identified. These two characteristics cannot be confirmed by Figures 2, 3 and 4, but in fact this holds true for all the computation scenarios.

Figure 5.

Noninferior solutions by GA for arrival time interval of 7 h and handling time of 9 h.

Full figure and legend (41K)

Figure 6 portrays the service time and weighted delay time of ships in the two noninferior solutions by GA for F_j=+3 h, which are shown in Figure 5. Figure 7 shows the service time and nonweighed delay time (or actual delay time) for the two solutions. In solution 1, one ship has a long weighted delay; therefore, the average weighted delay is also large. On the other hand, ships do not associate such a long weighted delay with them in solution 2. However, the nonweighted time in solution 1 is not much longer than that of solution 2. The presence of those two noninferior solutions results from one ship with long handling time (therefore large weight).

Figure 6.

Ships' service and delay times (F_j=+3).

Full figure and legend (51K)

Figure 7.

Ships' service and nonweighted delay times (F_j=+3).

Full figure and legend (48K)

CONCLUSIONS

In this study, we examined two different evaluation factors for berth allocation: service time and (weighted) delay time of departure. Container terminal operators have essentially two major concerns: the service quality for calling ships and berth utilisation. Very often these objectives conflict each other. In this study, the former concern was defined by the weighted delay time in departure, while the latter was measured by the total service time of ship (including the waiting time for idle berths and the handling time of ships).

This study first proved that if the weight for the delay time is equal for all ships, that is, nonweighted delay time, both measured values of the concerns are proportional. Nevertheless, they most likely contradict each other if the delay time is weighted. Therefore, the problem of the minimisation of the weighted delay time of departure and the minimisation of the total service time likely yield noninferior solutions. For the identification of the noninferior solutions, this study implemented two heuristics based on existing procedures for the single objective BAP: the subgradient optimisation with the Lagrangian relaxation and the GA.

Through numerical experiments that were carried out, it was found that in most computation scenarios the GA outperforms the SP, especially in considerably congested terminal situations with a frequent ship calling and long ship handling time. Furthermore, we found that when the predetermined deadline of departure time is tight, noninferior solutions were likely identified.

Owing to the continuous trend of increased containership carrying capacity, major maritime container terminals will strengthen their role as hub ports, where a lot of deep-sea and short-sea ships are calling. Such terminals are confronted with the problems discussed in this paper. In this respect, the results provided in the study could be useful in assisting the operator's decision-making process for improving his container terminal operations.

References

1. Brown, GG, Lawphongpanich, S and Thurman, KP. 1994: Optimizing ship berthing. Naval Research Logistics 41: 1–15. | Article |
2. Brown, GG, Cormican, KJ, Lawphongpanich, S and Widdis, DB. 1997: Optimizing submarine berthing with a persistence incentive. Naval Research Logistics 44: 301–318. | Article |
3. Cohon, JL. 1978: Multiobjective programming and planning. Academic Press: New York.
4. Cordeau, J-F, Laporte, G, Legato, P and Moccia, L. 2005: Models and tabu search heuristics for the berth-allocation problem. Transportation Science 39: 526–538. | Article |
5. Guan, Y, Xiao, W-Q, Chueng, RK and Li, C-L. 2002: A multiprocessor task scheduling model for berth allocation: Heuristic and worst case analysis. Operations Research Letter 30: 343–350. | Article |
6. Imai, A, Nagaiwa, K and Chan, WT. 1997: Efficient planning of berth allocation for container terminals in Asia. Journal of Advanced Transportation 31: 75–94.
7. Imai, A, Nishimura, E and Papadimitriou, S. 2001: The dynamic berth allocation problem for a container port. Transportation Research Part B 35: 401–417. | Article |
8. Imai, A, Nishimura, E and Papadimitriou, S. 2003: Berth allocation with service priority. Transportation Research Part B 37: 437–457. | Article |
9. Imai, A, Nishimura, E and Papadimitriou, S. 2005a: Corrigendum to "The dynamic berth allocation problem for a container port" [Transportation Research Part B 35 (2001) 401–417]. Transportation Research Part B 39: 197. | Article |
10. Imai, A, Nishimura, E and Papadimitriou, S. 2005b: Berth allocation in a container port: Using a continuous location space approach. Transportation Research Part B 39: 199–221. | Article |
11. Imai, A, Nishimura, E, Hattori, M and Papadimitriou, S. 2007: Berth allocation at indented berths for mega-containerships. European Journal of Operational Research 179: 579–593. | Article |
12. Imai, A, Nishimura, E and Papadimitriou, S. 2008: Berthing ships at a multi-user container terminal with a limited quay capacity. Transportation Research Part E 44: 136–151. | Article |
13. Kim, KH and Moon, KC. 2003: Berth scheduling by simulated annealing. Transportation Research Part B 37: 541–560. | Article |
14. Lai, KK and Shih, K. 1992: A study of container berth allocation. Journal of Advanced Transportation 26: 45–60.
15. Li, C-L, Cai, X and Lee, C-Y. 1998: Scheduling with multiple-job-on-one-processor pattern. IIE Transactions 30: 433–445.
16. Lim, A. 1998: The berth planning problem. Operations Research Letters 22: 105–110. | Article |
17. Nishimura, E, Imai, A and Papadimitriou, S. 2001: Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research 131: 282–292. | Article |
18. Park, KT and Kim, KH. 2002: Berth scheduling for container terminals by using a sub-gradient optimization technique. Journal of the Operational Research Society 53: 1054–1062. | Article |
19. Park, Y-M and Kim, KH. 2003: A scheduling method for berth and quay cranes. OR Spectrum 25: 1–23. | Article |

Appendices

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<kU}; S_i is the time when berth i becomes idle for the planning horizon; W_i is the subset of ships with A_jS_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.

Figure C1.

GA procedure.

Full figure and legend (39K)

Figure C2.

Chromosome representation.

Full figure and legend (5K)

Acknowledgements

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