Berth Planning by customer service differentiation: A multi-objective approach

Maria Boilea, Sotirios Theofanisa, Mihalis Goliasa, and David Coitb
aDepartment of Civil and Environmental Engineering, Rutgers, The State University of New Jersey, 100 Brett Road, Piscataway, NJ 08854 USA
bDepartment of Industrial Engineering, The State University of New Jersey, 96 Frelinghuysen Rd.,Piscataway, NJ 08854 USA

Abstract: The berth-allocation problem (BAP) aims to optimally schedule and assign ships to berthing areas along a quay. Berth planning models that have appeared in the literature differ in the assumptions made on the physical constraints and the BAP objectives. In this paper the BAP is formulated as a multi-objective optimization problem and special attention is given to customer service differentiation. Two modeling approaches are presented and a small computational example using a bi-objective implementation of the proposed formulations is used to critically discuss the advantages and disadvantages of the proposed approach.

1.	Introduction
The Berth Allocation Problem (BAP) in a container terminal can be simply described as the problem of allocating berth space to vessels. The problem has two planning/control levels: the strategic/tactical and the operational. At the strategic/tactical level the number and length of berths/quays that should be available at the port to service the anticipated traffic are determined. Adequate berthing capacity can be provided either at the initial port construction phase or when an expansion, or even when a berthing space reallocation between port functions is considered. At the operational level the allocation of berthing space to a set of ships scheduled to call at the port within a few days time horizon has to be decided upon. This paper deals with the operational BAP. 
At the operational level the BAP is typically formulated as combinatorial optimization problem (i.e. machine scheduling problem, 2D packaging problem), although initially queuing models where used (Edmond and Maggs, 1978). Several berth allocation models have appeared in the literature, differing in the assumptions made, the mathematical formulation, and solution approach. Usually, the formulation of the problem leads to NP-hard or NP-complete problems requiring the use of heuristics and meta-heuristics to obtain solutions in a computationally acceptable time.
The BAP can be modeled as a discrete problem where the quay is viewed as a finite set of berths, each serving one ship at a time, or as a continuous problem where ships can berth anywhere along the quay. In the discrete case, the BAP can be modeled as an unrelated parallel machine-scheduling problem, where a ship is treated as a job and a berth as a machine. In the continuous case the BAP is treated as a packaging or the two-dimensional cutting stock problem, where one dimension is time and the other the size of the vessels. 
The BAP can be modeled as a static problem (SBAP) if all ships to be serviced are already in the port at the time the scheduling begins, or as a dynamic problem (DBAP) if some of the ships have not yet arrived but their arrival times are known in advance. Although the BAP had initially been treated as a First Come First Serve (FCFS) problem, later published research work considers service priorities by assigning weights to ships. Some research approaches, appearing in the literature, have penalized berthing assignments by a factor proportional to its distance from an “ideal” point, relating to the distance of the berthing area from the storage yard area, where containers to be loaded on board the given ship are stored (also known as the preferred berthing point). According to Cordeau et al. (2005) though, planners prefer to handle this aspect by increasing the expected handling time according to the quay segment where the ship moors. Finally, technical restrictions such as berthing draft, inter-ship and end-berth clearance distance, that bring the problem formulation closer to real world conditions, are other assumptions that have been considered.
The problems of the SBAP and DBAP along with the discrete and continuous BAP have been widely studied in different combinations. Most of the studies, as will be seen more thoroughly in the next section, try to minimize the total service and waiting time (total completion time-TCT) and/or the deviation from the preferred berth, since it is expected that minimization of the deviation from the preferred berthing position will reduce service time and operator’s cost. These objectives, however, do not take into account the issue of meeting contractual agreements for the ships’ scheduled start of cargo handling operations and/or departure (which can be denoted as the time of departure after the scheduled arrival in the port). Contractual arrangements can vary from berthing (and start of cargo handling operations) upon arrival, to guaranteed service time window and/or guaranteed service productivity (UNCTAD, 1986). Earliness or lateness of a ship’s handling operations completion time (loading/unloading of containers) implies benefits or costs to both the port operator and the ocean carrier. If these operations are completed after a specified and  agreed time, the port operator may pay a penalty to the ocean carrier, while if these operations are completed before that date the carrier may pay a premium fee to the port operator, subject to the contractual arrangements, although in practice premium may be compensated with past or future penalties assigned to the port operator due to failure to meet the terms of the contract. Although early departures are seldom reported to happen, they can help ocean carriers in managing the time factor of their service schedules, by providing time buffer to cope with time lost in other ports (Notteboom, 2006). Early premiums can be offset by reducing voyage operating cost through reducing the voyage speed and therefore the fuel consumption. In fact, recently, ocean carriers seek to reduce operating cost through voyage speed reduction, while maintaining service punctuality (Savvides, 2006 and Lloyds List, 2006).
To our knowledge, research deviating from the general formulations and considering some kind of penalty, has only been presented by Kim and Moon (2003), Park and Kim (2003), and lately by Wang and Lim (2006). Kim and Moon (2003) studied the continuous SBAP with the objective to minimize the cost from non-optimal berthing and the penalty from delaying the departure of a vessel. Their formulation considered handling times as independent of the berth assignment and benefits by early departures were not considered. Park and Kim (2003) minimized the weighted sum of the handling cost of containers, the penalty cost incurred by berthing earlier or later than the expected time of arrival, and the penalty cost incurred only by the delay of the departure beyond the specified due time. Wang and Lim (2006) also consider only the penalty costs from delayed departures. A study presented by Imai et al. (2003) could also be considered relevant to the one presented in this paper. In Imai et al. (2003) the DBAP with ship service priorities is formulated as a MIP problem, giving different priorities to ships, using weights assigned based on the volume of containers of each ship to be handled at the port.
In the present paper the dynamic and discrete BAP is formulated as a multi-objective optimization problem (MDDBAP) with two objectives: a) minimize the total service time and b) minimize the delays of a set of preferential customers. Special attention is given to customer service differentiation. Therefore, instead of considering all the ships as one entity, each customer, represented by any number of ships, is assigned a separate minimization function. The application of this approach yields a set of Pareto optimal solutions that could allow the terminal operator to select the maximum number of customers receiving preferential service, while retaining satisfactory levels of service for the rest of the customers. Defining the number of customers that can be serviced based on preferential treatment, while maintaining satisfactory service for the rest of the customers is of crucial importance for the terminal operator, when shaping the service policy. The next section presents a comprehensive literature review on the BAP and the application of Genetic Algorithms (GA) on multiobjective machine scheduling problems. The model formulation is presented in the third section, while the fourth section describes the solution approach. The fifth section presents a small computational example discussing the advantages and disadvantages of the approach. The paper ends with a brief discussion for future research.
2.	Literature Review
	2.1 The Berth Allocation Problem
Several papers have appeared in the literature dealing with the BAP. One of the first papers presented in this area was by Lai and Shih (1992). The authors assumed that a wharf is represented as a continuous line that could be partitioned into several sections, to each of which only one vessel could be allocated at any specific time. A heuristic algorithm was developed considering a first-come-first-served (FCFS) rule. Brown et al. (1994, 1997) treated the BAP in naval ports. They identified the optimal set of ship-to-berth assignments that maximizes the sum of benefits for ships while in port. Imai et al. (1997) first introduced the idea that for high port throughput, optimal ship-to-berth assignments should not be based on the First Come First Served (FCFS) rule. However, their formulation may result in some ships' dissatisfaction regarding order of service. Lim (1998) addressed the continuous BAP with the objective of minimizing the maximum amount of quay space used at any time with the assumption that once a ship is berthed, it will not be moved to any place else along the quay before it departs. He also assumed that every ship is berthed as soon as it arrives at the port. Li et al. (1998) formulated the SBAP as a scheduling problem with a single processor through which multiple jobs can be processed simultaneously. The objective was the minimization of the make-span. Similar to Li et al. (1998), Guan et al. (2002) considered the berth allocation problem as a multiprocessor task scheduling. They developed a heuristic to minimize the total weighted completion time of ship service and performed worst-case analysis. Weights were assigned to each job depending on the vessel’s size. Imai et al. (2001) addressed the DBAP with the objective to minimize the sum of a ship’s waiting and handling time. Handling time was assumed deterministic and dependent on the berth. In the same context Nishimura et al. (2001) addressed the same problem but for a public berth system. The authors extended the work done by Imai et al. (2001) to include physical restrictions (water-depth and quay length). They also dropped the assumption that each berth can handle one ship at a time. Service priority relied on the FCFS rule. The objective was to minimize service time (including waiting time). Imai et al. (2003) modified and extended the discrete DBAP formulation of Imai et al (2001) and Nishimura et al.(2001) in order to include service priority constraints. The objective was to minimize the total service time, while assigning priorities to ships by variation of their service time in the solution. Imai et al. (2005) extended their previous work by solving the DBAP in a continuous berth space with the objective of minimizing the total completion time.
Guan and Cheung (2004) presented a berth allocation model that allows multiple vessels to moor at a berth, considers vessel arrival time and optimizes the total weighted flow time. Following the idea by Imai et al. (2003) they apply a weight coefficient to each ship. They develop a tree procedure and a heuristic that combines the tree procedure with the heuristic presented in Guan et al. (2002). Kim and Moon (2003) studied the continuous SBAP. They formulated a MIP model and used simulated annealing to find near optimal solutions. The objective was to minimize delays and handling cost by non-optimal locations of the ships’ berthing. Unlike Lim (1998), Imai et al (2001), Brown et al. (1994, 1997) and Lai and Shi (1992), Park and Kim (2002) consider the continuous BAP with the objective of estimating the berthing time and location by minimizing the total waiting and service time and the deviation from the preferred berthing location. 
Park and Kim (2003), extend their previous work to combine the BAP with consideration of quay crane capacities. Their study determined the optimal start times of ship services and associated mooring locations while at the same time determines the optimal assignment of quay cranes to ships. The handling time was considered independent from the mooring location of the ship. Lee et al. (2006) following the work of Park and Kim (2003) presented a method for scheduling berth and quay cranes, which are critical resources for the seaside operations in container ports. A bi-level programming model with the objective of minimizing the sum of total completion time of all the vessels and the completion time for all the quay cranes is formulated by considering various practical constraints, such as interference between the quay cranes. Cordeau et al. (2005) considered the discrete case of the DBAP and provided two formulations: a formulation similar to Imai et al. (2001) and a formulation similar to the Multi Depot Vehicle Routing Problem with Time Windows. To avoid simplifications contrary to Park and Kim (2003) the authors did not solve the BAP and the Quay Crane Assignment Problem (QCAP) simultaneously. The objective was the minimization of the total (weighted) service time for all ships, defined as the time elapsed between the arrival in the port and the completion of handling operations. 
Imai et al., (2006a) addressed the berth allocation problem at a multi-user container terminal with indented berths for fast handling. A new integer linear programming formulation was presented, which was then extended to model the berth allocation problem at a terminal with indented berths, where both mega-containerships and feeder ships are to be served for higher berth productivity. Wang and Lim (2006) solved the DBAP by minimizing un-allocation, position and delay costs, using a Stochastic Beam Search Heuristic. Imai et al. (2006b) addressed a variation of the BAP at multi-user terminals, as ships for which their expected wait time exceeds a given time limit were assigned to an external terminal. The objective of the problem was to minimize the total service time of ships at the external terminal. A GA based heuristic was developed and numerical experiments showed that the heuristic performed well in reducing external terminal usage. Boile et al. (2006) have proposed a linear formulation of the BAP with service priorities. Golias et al. (2007a) modified this approach to reflect service delay penalties and early premiums. Golias et al. (2007b) extended the work of Golias et al. (2007a) by presenting a BSP for the DBAPD reflecting time window service deadlines. The problem was formulated as a MIP linear problem with the objective to simultaneously minimize the cost from the vessel late departures and maximize the benefits from the vessel early and timely departures. The authors considered premiums and penalties from early departures. A critical review of the berth allocation problem literature is presented in Theofanis et al. (2007). 
	2.2 Multi-Objective Scheduling
Literature on multi-objective scheduling is vast. Excellent reviews of the principles of evolutionary multiobjective optimization and recent developments are provided by Coello et al. (2002), Van Valdhuizen and Lamont (2000), and Jimenez (2006). We will focus the literature review on multi-objective machine scheduling related problems, since the discrete BAP belongs to this general category of problems. The interested reader is referred to Silva et al. (2004), Hoogeveen (2005), T’kindt and Billaut (2002), and the excellent online directory of multi-objective optimization by Coello for a more analytical literature review and an introduction to multi-objective metaheuristics for scheduling. Murata et al. (1996) proposed a multi-objective genetic algorithm (MOGA) and applied it to flow-shop scheduling. Hyun et al. (1998) developed a new selection scheme in GA, and showed its superiority for multi-objective scheduling problems in assembly lines. Also using GAs, Chen et al. (1996) studied the radiological worker allocation problem in which multiple constraints are considered. Constraints are classified as hard and soft. Each solution must satisfy the hard constraints and performance of the solution is measured by the violation of soft constraints. The GA approach was compared with conventional optimization techniques such as goal programming and simplex method, and the GA showed superior results. Other heuristics such as simulated annealing and tabu search have also been studied. 
Marett and Wright (1996) compared these two heuristics for flow shop scheduling problems with multiple objectives. The performance of the methods was compared as the number of objectives increased. Simulated annealing was found to perform better than tabu search as the number of objectives increased.  They also mentioned that the complexity of combinatorial problems is strongly influenced by the type of objectives as well as their number. Yim and Lee (1996) used Petri nets and heuristic search to solve multi-objective scheduling for flexible manufacturing systems. Pareto optimal solutions were obtained by minimizing the weighted summation of the multiple objectives. Jaszkiewicz (1997) combined the genetic algorithm with simulated annealing to solve a nurse-scheduling problem. The maximization of multiple objectives is represented by a single scalar function, which is the summation of a scalar multiplying the difference between current and previous solutions for each objective. The scalar is greater than one if the objective is improved or less than one if no improvement is found. Cohran et al. (2003) proposed a two-stage multi-population genetic algorithm (MPGA) to solve parallel machine scheduling problems with multiple objectives. Their approach is applied in parallel machine scheduling problems with two objectives: makespan and total weighted tardiness (TWT). The MPGA was compared with a benchmark method, the multi-objective genetic algorithm (MOGA), and showed better results for all of the objectives over a wide range of problems. The MPGA was extended to scheduling problems with three objectives: makespan, TWT, and total weighted completion times (TWC), for which also performed better than MOGA. Chang et al. (2005) introduced a two-phase sub population genetic algorithm to solve the parallel machine-scheduling problem. The two-phase sub-population genetic algorithm was applied to solve the parallel machine-scheduling problems in testing of the efficiency and efficacy. Experimental results were reported and the superiority of this approach was discussed. Taboada & Coit (2006a) and Taboada et al. (2007) formulated the redundancy allocation problem (RAP) as a multi-objective problem with the system reliability to be maximized, and cost and weight of the system to be minimized. The Pareto-optimal set was initially obtained using the fast elitist nondominated sorting genetic algorithm (NSGA-II) originally proposed by Deb et al. (2002). Then, the decision-making stage was performed by applying two proposed pruning methods to reduce the size of the Pareto-optimal set and obtain a smaller representation of the multi-objective design space. For those studies, NSGA-II was effective. However, NSGA-II is a general multi objective evolutionary algorithm (MOEA) for any type of problem. This implies that the problem formulation needs to be properly adapted. Moreover, in these studies, the final Pareto front found by NSGA-II contained many repeated solutions, so in order to obtain a large number of solutions; several runs had to be performed. Thus, if a decision-maker must solve many similar RAP problems, then a custom MOEA, especially designed to solve multiobjective design allocation problems, offers great advantage. MOEA-DAP, (Taboada & Coit, 2006b) was developed to address these difficulties. MOEA-DAP is a multiple objective evolutionary algorithm specifically designed to solve system design allocation problems. Thus, this new approach has the strength of a problem-oriented technique. MOEA-DAP, mainly differs from other MOEAs in the type of crossover operation performed. In this step, several offspring are created through multi-parent recombination. Thus, the mating pool contains a great amount of diversity of solutions. This disruptive nature of the proposed type of crossover, subsystem rotation crossover (SURC), appears to encourage the exploration of the search space.
3.	Problem Formulation
The two most common ways of solving multiple objective problems are: a) combine the different objectives into a single objective function (i.e. weighted method, utility functions), or b) obtain a set of non-dominated Pareto-optimal solutions. In this section we present both; a formulation using the weighted method and a formulation that separates the objective functions and obtains a set of non-dominated Pareto-optimal solutions. The two approaches are applied for a lump cost delay penalty and for late birthing/departure penalization based on an hourly cost function. In the next section a small instance of the BAP is used to compare the two approaches and draw some conclusions.
3.1	Lump Cost Delay Penalty
In this formulation the port operator is penalized by a lump value irrespectively of the amount of time a vessels’ berthing/departure date is delayed. To formulate the DDBAP with a lump cost function for the delayed departures/berthing (DDBAPL) we define the following: 
i=(1,……,I)  B set of berths, 
j=(1,….,T)  T set of ships, 
k=(1,….,T)  O set of service orders, 
c=(1,…….K)  set of customers
p=(1,…….,P)  set of preferential customers
Si= Time when berth becomes idle, 
Aj= Arrival time, 
Cij= Handling time of ship j at berth i,
yijk= Idle time of berth i between departure of ship j, belonging to customer c, and its immediate predecessor
 = 1 if ship j, belonging to customer c, is serviced at berth i as the kth ship and departs/berths before the requested date and zero otherwise, 
=1 if ship j, belonging to customer c, is serviced at berth i as the kth ship and departs/berths after the requested date and zero otherwise, 
tdj= Requested departure date of ship j (usually given in hours after the ship’s scheduled arrival),
tbj= Requested berth date of ship j (usually given in hours after the ship’s scheduled arrival),
cdj= Cost (lump) of late departure of ship j
cbj= Cost (lump) of late berth of ship j
=1 penalizing late departures of ship j, belonging to preferential customer p, and 0 penalizing late berthing of ship j, belonging to preferential customer p.
The formulation of the multiobjective DDBAPL (MDDBAPL) is as follows:
[MDDBAPL]: 				     (1)
							     (2)
Subject to: 								     (3)
									     (4)
		     (5)
 			     (6)
    			    (7)
, .

The first objective function (1) minimizes the total of waiting and handling time for every ship while the second objective minimizes the delays of the selected customer sets. In this formulation all preferential customers are represented by the minimization function (2). In the general case each customer may be presented by its own objective function. Constraints (3) ensure that ships must be serviced once; constraints (4) that each berth services one ship at a time; and constraints (5) that each ship is serviced after its arrival. Constraints (6) and (7) define the decision variables  and . If  ship j, that belongs to customer c, will finish or start service after the scheduled time, and if  ship j, that belongs to the customer c, will finish or start service before the scheduled time. In the first objective function (1) the term Cij is weighted to ensure that if a ship is served with k successors the appropriate waiting time will be added to these successors.
The formulation of the weighted DDBAPL (WDDBAPL) is as follows:
[WDDBAPL]: min,			    (8)
Subject to:  (3)-(7)
w1+w2=1												   (9)
where: w1, w2 are the weights for each objective. 
In practice, there is no real need or requirement for the weight terms to sum to one. However, this constraint is convenient and is often added when the objective functions have been similarly scaled e.g., 0 to 1. The scaling approach adopted in this paper is discussed in the next section.
3.2	Hourly Cost Function
In this formulation the port operator is penalized for late berthing/departure of vessels on an hourly basis. To formulate the multiobjective DDBAP with an hourly cost function (MDDBAPH) we need to redefine the cost function and introduce an auxiliary variable that will estimate the difference between the scheduled and actual departure/berthing time: 
cdj= Cost per hour of late departure of ship j
cbj= Cost per hour of late berthing of ship j
= Difference of scheduled and actual departure/berthing time of ship j belonging to preferential customer p.
The formulation of the MDDBAPH is as follows:
[MDDBAPH]: 			(10)
							   (11)
Subject to: 								   (12)
									   (13)
		    (14)
   			   (15)
 			  (16)
 			   (17)
, , .
Assuming the same approach as previously, the formulation of the weighted DDBAPH (WDDBAPH) is as follows:
[WDDBAPH]: 		(18)
Subject to:  (12)-(17)
w1+w2=1												   (19)
where: w1, w2 are the weights for each objective. 
4.	Computational Examples
A computational example for a small instance of the BAP (2 berths, 20 ships, 4 customers, and 1 preferential customer) is used to illustrate the advantages and disadvantages of the proposed approach. In this example it is assumed that only one of the customers, representing 50% of the total container terminal traffic, receives preferential treatment. 50% of the preferential vessels request timely berthing and 50% timely departure. For the rest of the customers a zero cost is given for late departures or berthing of their vessels. Furthermore in order to simplify the analysis, and without loss of generality, late berthing costs were considered equal to late departure cost. The optimal set was obtained using a simple multi-objective algorithm devised by the MIEMP laboratory and implemented within Skylab. Initially, the fast elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) originally proposed by Deb et al. (2002), was used but the algorithm could not produce any feasible solutions even for large combinations of the population and generation parameters (the maximum number of population and the maximum number of generation used with no optimal solution found was 500 and 75000 respectively). The weighted solution was obtained using classical MIP branch and bound algorithm. For the weighted approach the main difficulty was the choice of the correct weights. Since simulated data was used for the experiments, a procedure using a combination of weights was applied (fig. 1), in order to, and for comparison purposes, obtain multiple solutions. As mentioned in section 3 both objective functions where scaled. Scaling was accomplished by dividing each function by a different constant number, equal to the value of that objective function when its weight was equal to one.
<Figure 1>
One of the reasons for using the iterative procedure shown in figure 1 was to show how cumbersome the weighted approach can become if the weights are not known in advance or are difficult to substantiate (which is generally the case). In the conducted experiments delay costs for all preferential customers were represented by one function. In other setups though, each customer or sets of different preferential customers, could be represented by a separate function, increasing the number of weights used. In that case the procedure shown in figure 1 would become very tedious. One could argue that this iterative approach would provide global optimality, unlike NSGA-II, since the later is a metaheuristic approach. Unfortunately, for medium/large instances of the problem, solving the MIP at Step 2 would also require the use of  (meta)heuristics (typically GA based heuristics have been used for the BAP, Steenken et al., 2004) since an optimal solution cannot be obtained in a reasonable computational time using conventional algorithms (Imai et al. 2003, 2006a, 2006b).
Figure 2 shows results of the weighted approach, both for the lump and hourly cost cases. The three dimensional graphs show the change of the two separate objectives in relation to the change of the w1, while the two dimensional graphs show the change of both objectives in relation to the change of w1.The increase/decrease step parameter a (fig. 1) was set equal to 0.1 and the termination parameter b equal to zero. As expected, the second formulation [WDDBAPH] provides the smaller delay cost, and as w1 decreases the value of the total service time increases and vice versa for the total delay. The cases corresponding to (w1, w2)=(1, 0) and (w1, w2)=(0, 1) were solved as single-objective problems, removing the weights and the scaling constants, although for consistency purposes in the two dimensional graphs results are shown for the scaled objectives for these two cases. We should note that the solutions are at most cases strongly dependent on how the weights were chosen and/or how the objective functions were scaled. 
<Figure 2>
For the multiobjective approach no preference, in any form, was stated between the two objectives. The outcome of this optimization is shown in figure 3 as a set of feasible solutions that reflect the trade-off between the objectives. The second set of graphs in figure 3, present the normalized total objective function for each generation. One disadvantage of the multiobjective approach is that the Pareto-optimal set may contain hundreds or even thousands of solutions, making it difficult for the decision maker to select one solution as final implementation. Taboada (2007) presents an excellent review of existing methods and a new approach for reducing (also called pruning) the Pareto set. For the example in this paper and due to the small size of the problem ranking is not needed since the Pareto-optimal solution can be found at the inner edges of the 2-dimentionsl graphs. From a practitioners point of view the advantage of the second approach is obvious; a larger number of solutions are available for the berth planner to select from. The disadvantages of the second approach is that: a) general machine scheduling multi-objective algorithms do not exist and thus customized solutions need to be built from scratch, and b) the global optimal values of the single objective counterparts (i.e. cases corresponding to (w1, w2)=(1, 0) and (w1, w2)=(0, 1) in the weighted approach) are not guaranteed that will be obtained.
<Figure 3>
5.	Conclusions
In this paper the BAP was formulated as a multi-objective optimization problem and special attention was given to customer service differentiation. Two formulations were presented that can handle multiple objectives at the same time, namely minimization of the total service time and the cost from delayed departures of vessels belonging to preferential sets of customers, considered as a lump cost or an hourly delay cost. Two solution approaches, a combination of the objectives into a single weighted function and a Pareto-optimal set approach, were presented and applied for a small instance of the BAP using simulated data. It can be concluded that if sufficient knowledge and familiarity with the problems’ domain, and an intelligent and accurate way of either scaling the objectives or quantifying the cost of the total service time can be ensured, then the former approach is preferable. On the other hand if uncertainty or doubt exists on the scaling of the objectives or the monetary value of the total service time, then obtaining a Pareto-optimal set would be more beneficial for the port operator. This of course requires more programming effort, and a robust and efficient technique for reducing (pruning) the (often) large Pareto-optimal set.
Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant No.0538901. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation
The authors would like to thank Dr. H. A. Taboada and Mr. S. Jamakiraman for their help in implementing the multi-objective algorithm NSGA-II.
References
Boile, M., Theofanis, S. and Golias, M. (2006) “Berth allocation with service priorities: A linear reformulation”. Proceedings of the 5th WSEAS International Conference on System Science and Simulation in Engineering, Tenerife, Canary Islands, Spain.
Bramlette, M.F. (1991) “Initialization, mutation and selection methods in genetic algorithms for function optimization”. Proceedings of the 4th International Conference on Genetic Algorithms. 
Brown, G.G., Lawphongpanich, S., and Thurman, K.P. (1994) “Optimizing Ship Berthing”, Naval Research Logistics, 41, pp. 1–15.
Brown, G.G., Cormican, K.J , Lawphongpanich, S.  and Widdis, D.B. (1997) “Optimizing Submarine Berthing with a Persistence Incentive”, Naval Research Logistics, 44, pp. 301–318.
Chang, P-C, Chen, S-H and Lin, K-L. (2005) “Two-phase sub population genetic algorithm for parallel machine scheduling problem”, Expert Systems with Applications,  23(3), pp. 705-712.
Chen, Y, Narita, M, Tsuji, M. and Sa, S. (1996) “A genetic algorithm approach to optimization for the radiological worker allocation problem”, Health Physics, 70, p.p.180-186.
Cohran, K.J., Horng, S-M. and Fowler, W.J. (2003) “A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines”, Computers and Operations Research, 30, 1087-1102.
Coello, C.C.A, Van Veldhuizen, D.A, and Lamont G.B. (2002). Evolutionary algorithms for solving multiobjective problems, Kluwer Academics Publishers.
Cordeau, J-F., Gaudioso M., Laporte, G., Moccia, L.(2007) “The Service Allocation Problem at the Gioia Tauro Maritime Terminal”, European Journal of Operational Research, 176(2), pp.1167-1184.
Edmond, E. D. and Maggs R. P. (1978) “How Useful are Queue Models in Port Investment Decisions for Container Berths?”, Journal of the Operational Research Society, 29, pp. 741–750.
Golias, M., Boile, M., and Theofanis, S. (2007a) “The Berth Allocation Problem: A formulation reflecting service delay penalties and early premiums”. Proceedings of the Transportation Research Board 87th Annual Meeting, Washington, D.C.
Golias, M., Boile, M., and Theofanis S. (2007b) “The Berth Allocation Problem: A formulation reflecting time window service deadlines”. Proceedings of the 48th Annual Transportation Research Forum, Boston, Massachusetts.
Guan, Y. and Cheung, R. K. (2004) “The Berth Allocation Problem: Models and Solution Methods”, OR Spectrum,  26, pp.75–92.
Guan, Y., Xiao, W-Q. , Cheung, R. K. and Li., C-L. (2002) “A Multiprocessor Task Scheduling Model for Berth Allocation: Heuristic and Worst Case Analysis”, Operations Research Letters, 30,  pp. 343–350.
Guan, Y., and Cheung, K.R. (2004) “The Berth Allocation Problem: Models and Solution Methods”, OR Spectrum, 26, pp. 75-92.
Hoogeveen, H (2005) “Multicriteria Scheduling”, European Journal of Operational Research, 167, pp. 592-623.
Hyun, C.J, Kim, Y. and Kin, YK. (1998) “A genetic algorithm for multiple objective sequencing problems in mixed model assembly”, Computers & Operations Research, 25(7-8), pp.675-690.
Imai, A., Nagaiwa, K. and Tat, C-W. (1997) “Efficient Planning of Berth Allocation for Container Terminals in Asia”, Journal of Advanced Transportation, 31, pp. 75–94.
Imai, A., Nishimura, E. and Papadimitriou, S. (2001) “The Dynamic Berth Allocation for a Container Terminal”,. Transportation Research Part B, 35, pp. 401-417.
Imai, A., Nishimura, E. and Papadimitriou, S. (2003) “Berth Allocation with Service Priority”, Transportation Research Part B, 37, pp. 437-457.
Imai A., Sun, X., Nishimura, E. and Papadimitriou, S. (2005) “Berth Allocation in a Container Port: Using Continuous Location Space Approach”, Transportation Research Part B, Vol. 39, 2005, pp. 199–221.
Imai, A., Nishimura, E. and Papadimitriou, S. (2006) “Berthing ships at a multi-user container terminal with a limited quay capacity”, Transportation Research Part E (In Print) 
Imai, A., Nishimura, E., Hattori, M. and Papadimitriou, S. (2007) “Berth Allocation at Indented Berths for Mega-Containerships”, European Journal of Operational Research, 179(2), pp. 579-593.
Jaszkiewicz, A. (1997) “A metaheuristic approach to multiple objective nurse scheduling”, Foundations of Computing and Decision Sciences, 22, pp.169-183.
Kim, K.H. and Moon, K.C. (2003) “Berth Scheduling by Simulated Annealing” Transportation Research Part B, 37, pp. 541–560.
Lai, K.K, and Shih, K. (1992) “A Study of Container Berth Allocation”,  Journal of Advanced Transportation,  26, pp. 45–60.
Lee, D-H, Song L. and Wang, H. (2006) “A Genetic Algorithm for a Bi-level Programming Model of Berth Allocation and Quay Crane Scheduling”. Proceedings of the 2006 Annual Transportation Research Board Meeting. Washington D.C.
Li, C-L, Cai, X. and Lee C-Y.(1998) “Scheduling with Multiple-Job-on-One-Processor Pattern”, IIE Transactions, 30, pp. 433–445.
Lim, A. (1998) “The Berth Planning Problem”, Operations Research Letters, 22, pp. 105–110.
Lloyds List (2006) “Asia-Europe lines cut speed to save fuel and soak up overcapacity”, October 20, 2006.
Marett, R. and Wright, M. (1996) “A comparison of neighborhood search techniques for multi-objective combinatorial problems”, Computers and Operations Research, 23, pp. 465-483.
Murata, T., Ishibuchi, H. and Tanaka H. (1996) “Multi-objective genetic algorithm and its application to How shop scheduling”, Computers and Industrial Engineering, 30, pp. 957-968.
Nishimura E., Imai, A., Papadimitriou S. (2001) “Berth Allocation Planning in the Public Berth System by Genetic Algorithms”, European Journal of Operational Research, 131, pp. 282–292.
Notteboom, T.E. (2006) “The time factor in Liner Service”, Maritime Economics and Logistics, 8, p.p.19-39.
Park, M.Y. and Kim, H.K. (2003) “A. Scheduling Method for Berth and Quay Cranes”, Operations Research Spectrum, 25, pp.1-23.
Pinedo, M. (2002) Scheduling: Theory, Algorithms, and Systems.  Prentice-Hall, Inc.
Savvides, N. (2006) “Grand Alliance slows Asia/Europe ships to cut costs as low rates hit returns”, CI-Online, October 19, 2006. [online]. Available from:  http://www.ci-online.co.uk/ [cited October 2006].
Silva, L.J.D. and Burke, K.E. (2004). Available from: www2.lifl.fr/PM2O/Reunions/04112002/dario.pdf
Steenken, D., Voss, S. and Stahlbock, R. (2004) “Container terminal operation and operations research – a classification and literature review”, OR Spectrum, 26, pp. 3-49.
Theofanis, S., Boile, M., and Golias, M. (2007) “Container Terminal Seaside Operations Scheduling: Does Current Research Address the Practical Challenges of Berth Planning? - A Critical Review”. Paper presented at the 2007 Annual Forum Transportation Research Forum, March 15-17, 2007, Boston University, Boston, MA
T’kindt, V. and Billaut, J-C. (2002). Multicriteria scheduling: Theory, Models and Algorithms. Springer Berlin.
Taboada, H. A. (2007) “A. Multi-Objective Optimization Algorithms Considering Objective Preferences and Solution Clusters.” PhD Dissertation. Rutgers University.
Taboada, H. A. and Coit, D. W. (2006a) “Data Clustering of Solutions for Multiple Objective System Reliability Optimization Problems”, Quality Technology & Quantitative Management Journal (in print).
Taboada, H., Baheranwala, F., Coit, D. W. and Wattanapongsakorn, N. (2007) “Practical Solutions of Multi-Objective Optimization: An Application to System Reliability Design Problem”,. Reliability Engineering & System Safety, 92(3), pp.314-322
Taboada, H. and Coit, D. (2006b) “MOEA-DAP: A new Multiple Objective Evolutionary Algorithm for solving Design Allocation Problems”, Engineering Applications of Artificial Intelligence (submitted).
Van Veldhuizen, D.A, and Lamont G.B. (2000). “Multiobjective Optimization with messy genetic algorithms”.  Proceedings of the 2000 ACM Symposium on applied computing, pp. 470-476. Villa Olmo, Como, Italy
UNCTAD (1986) “Rights and duties of Container Terminal Operators and Users”. UNCTAD/ST/SHIP/6, Geneva..
Wang, F., and Lim, A. (2007) “A Stochastic Beam Search for the Berth Allocation Problem”, Decision Support Systems, 42(2), pp. 2186-2196.
Yim S.J. and Lee, D.Y. (1996) “Multiple objective scheduling for flexible manufacturing systems using petri nets and heuristic search”. Proceedings IEEE International Conference on Systems, Man, and Cybernetics 1996; 4, 2984-9.

List of Figures
Figure 1 Iterative solutions process for the weighted formulation
Figure 2 Weighted Approach Solutions (Lump and Hourly)
Figure 3 Feasible and Optimal solutions (Lump and Hourly)

a=increase/decrease of weights, b= stopping criterion
Figure 1 Iterative solution process for the weighted formulation

Figure 2a Weighted Approach Solutions (Lump)

Figure 2b Weighted Approach Solutions (Hourly)

Lump Cost Estimation

Hourly Cost Estimation

Figure 3 Feasible Solution and Pareto Front (Lump and Hourly) Multi-Objective Approach