Article Preview
TopIntroduction
Berth scheduling can be described as the problem of allocating berth space to incoming container vessels; a valuable resource of container terminals. Shipping lines, and therefore vessels, arrive at a container terminal over a period of time and compete for service at the available berths. Different factors affect the decision of a container terminal operator when deciding on the position and time slot assignment of each vessel along the terminal’s quay. Fierce terminal competition and the need to maximize resource utilization have led marine terminal operators to the development and application of a rich variety of berth scheduling policies (Steenken et al., 2004). Some of the factors affecting the berth scheduling policy to be applied include, the type and function of the port (dedicated or private terminal, transshipment hub, etc), the size of the port, the location, nearby competition, type of contractual agreement with the vessel carriers, among others (Theofanis et al., 2009).
Most real-world scheduling problems, like the berth scheduling problem, are implicitly or explicitly multi-objective. In the case of the problem addressed in this paper, several objectives (minimization of vessel turnaround time, maximization of port throughput, maximization of revenues, etc) can be considered by container terminal operators when defining berth schedules. Usually, these multiple objectives are non-commensurable and gaining an improvement on one objective often causes degradation performance in at least one other objective (i.e. minimization of the makespan of the berth schedule and minimization of the number of total quay cranes (QCs) employed). The majority of the berth scheduling policies found in the literature have not captured current port operators practices (Steenken et al., 2004; Theofanis et al., 2009), and until recently (Boile et al., 2007; Imai et al., 2007; Hansen et al., 2008; Golias et al., 2009;) researchers had not recognized the importance of simultaneously optimizing for the different objectives that a port operator needs to consider when scheduling for the berthing of vessels.
The later research presented a set of non-dominated berth schedules as the final solution of the problem, known as the Pareto-optimal set (Zeleny, 1982). However, they did not present a formal methodology that would assist the container terminal operator in the selection of the most preferred berth schedule out of the different schedules found in the Pareto front. Without a formal selection methodology, a significant effort is required for the selection of a good berth schedule within the Pareto front. This issue becomes very noticeable in the berth scheduling problem, where in most real-life instances, the Pareto front is usually in the range of a hundreds (Golias, 2007). This phenomenon is also amplified by the multi-optimal solution space of the problem (Pinedo, 2008). Literature presents that determination of a single solution for multi-objective problems is often performed using methods such as the weighted sum method, utility theory, goal programming, etc (Taboada & Coit, 2008). However, in these methods, the final solution can be highly sensitive to the weights (or costs or penalties) used in the scalarization process. Additionally, in methods such as in the case of the weighted sum method, the weights must be selected by the decision-maker prior to the determination of the optimal solution. Furthermore, even experienced practitioners have difficulty reliably selecting specific weight values even if they are intimately familiar with the problem domain.