برنامه ریزی اسکله توسط تفکیک خدمات مشتری: یک رویکرد چند هدفه

In this paper the discrete and dynamic berth allocation problem is formulated as a multi-objective combinatorial optimization problem where vessel service is differentiated upon based on priority agreements. A genetic algorithms based heuristic is developed to solve the resulting problem. A number of numerical experiments showed that the heuristic performed well in solving large, real life instances. The heuristic provided a complete set of solutions that enable terminal operators to evaluate various berth scheduling policies and select the schedule that improves operations and customer satisfaction. The proposed algorithm outperformed a state of the art metaheuristic and provided improved results when compared to the weighted approach.

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 (BSPs). Determining the best berth schedule depends on several factors including the type and function of the port (dedicated or private terminal, transshipment hub, etc.), size of the port, location, nearby competition, and type of contractual agreement between the terminal and the carriers (Theofanis et al., in press). The competitiveness of a container terminal depends on various factors, including the time in port for vessels (turnaround time) combined with low rates for loading and discharging. In container terminal operations, the objectives when defining optimal berth schedules include reducing vessel turnaround time and increasing port throughput, revenue, competitiveness and customer satisfaction. These multiple objectives are often non-commensurable and gaining an improvement on one objective often causes degrading performance on the others. Nevertheless, the need to simultaneously consider these objectives and find the schedule that optimizes the overall berth operations gives rise to the multi-objective nature of the problem. A multi-objective formulation similar to the one presented in this paper enables terminal operators to determine whether and when priority services may be given and to which customers, so that the overall service time is minimized while customer satisfaction is maximized. Research on berth allocation has recognized the multi-objective nature of the problem (Imai et al., 2003, Imai et al., 2007b, Steenken et al., 2004, Hansen et al., 2008 and Theofanis et al., in press). However, formulations presented to date are limited to combining the multiple objectives into a single scalar value (Imai et al., 2003 and Hansen et al., 2008), or restricting optimization to one of the objectives (a large portion of the literature focuses on the minimization of the vessels’ total handling and waiting time). The former approach consists of using a weighted aggregate function according to preferences set by decision-makers, and its complexity and accuracy lies in the proper selection of the weights used to depict the decision-maker preferences. In practice, it can be very difficult to precisely and accurately select these weights, even for someone familiar with the problem domain (Coello Coello, 2000 and Konak et al., 2006). In the berth allocation problem (BAP) selecting the appropriate weights for each vessel/customer to satisfy contractual agreements between the port operator and the liner shipping company may be a very cumbersome or even an impossible task. From the computational complexity theory, berth allocation (as with most scheduling problems) is known to be NP-hard or NP-complete depending on the formulation, objective function and constraint type (Papadimitriou and Steiglitz, 1982, Pinedo, 2002, Imai et al., 2003 and Imai et al., 2005). In addition, modeling different BSPs results in a number of different BAP formulations with different constraints some hard and other soft. Hard constraints must not be violated (for example each vessel must be served once and each berth can service one vessel at a time) while soft constraints, (for example contract service time window for preferential customer’s vessels) can be relaxed resulting in a schedule under which the terminal operator pays a delay penalty to the preferential customer. Satisfying both types of constraints is a difficult problem itself. When different constraints cannot be satisfied simultaneously, the problem is often deemed to admit no solution. On the other hand if constraints are relaxed, the problem solution is inferior (a vessel’s service time may exceed the desirable service time). A multi-objective formulation offers the advantage of treating these constraints as objectives, and can consistently outperform the single objective approach without a significant sacrifice in terms of performance (Coello Coello, 2000). This observation could prove to be very valuable in complex berth allocation problems where a number of the constraints that limit the feasible region of the problem can be viewed as objectives. In this paper we formulate the BAP as a multi-objective mixed integer optimization problem. Special attention is given to different groups of vessels by the use of different objective functions. As pointed out by Imai et al. (2003), vessels with a large container handling volume typically request higher priority over small vessels, leading to a decrease in berth productivity (high total service time for all the vessels at a given planning horizon). On the other hand, if vessels with small container handling volume are given priority then large vessels are forced to wait, leading to dissatisfaction of the large vessels. The multi-objective formulation presented in this paper overcomes the drawbacks of using weights to represent vessel priorities. The proposed approach provides the port operator with a variety of different berth schedules ranging from the schedule with the best overall berth performance (in terms of the total service time of all the vessels) to schedules with the minimum dissatisfaction for different groups of vessels (in terms of the total service time of each group). To our knowledge this is the first time that this BSP has been formulated and solved as a multi-objective optimization problem. A genetic algorithms (GAs) based heuristic with custom genetic operations and fitness/selection technique is also presented to solve the resulting problem. A number of numerical experiments are performed to evaluate the performance of the proposed heuristic and critically discuss the benefits of the proposed approach. Results from the computational experiments show that the proposed formulation outperforms the weighted approach while the proposed resolution algorithm outperforms a state of the art multi-objective heuristic (NSGA-II by Deb et al., 2002). The rest of the paper is organized as follows. The next section presents a brief literature review on the BAP and a brief description of the general problem. The model formulation is presented in Section 3, while Section 4 describes the solution approach. The Section 5 presents a number of experimental results and Section 6 concludes the paper.

This paper contributes to the literature of the discrete and dynamic berth allocation by introducing a new berth scheduling policy that can assist container terminal operators in scheduling vessels at the berths based on groups of vessels with different priorities in terms of the total service time within a planning period. The proposed berth scheduling policy provides the port operator with a clear measure of the berth productivity assisting in the different vessel-to-berth allocation decisions. The problem was formulated and solved for the first time as a multi-objective combinatorial problem. The solution approach adopted was the determination of a Pareto Front and a Genetic Algorithms based heuristic was proposed. The Pareto Front estimation approach was adopted for its computational simplicity and usability advantage as compared to its weighted approach counterpart, which has been used to solve multi-objective problems in container terminal operations (Imai et al., 2003 and Golias, 2007). Computational examples showed that the proposed heuristic performed well even for large instances of the problem. As compared to the weighted approach alternative and in terms of the computational complexity the proposed heuristic required a single run to evaluate a large number of feasible berth schedules without the need of a precise knowledge of the objective functions relative importance. Obtaining the same set of solutions using the weighted approach would require an enormous amount of time consuming computations, in which the same problem would be solved repetitively using different weight combinations. Furthermore, determining these weight combinations can be very difficult even with a very detailed knowledge of the system (Taboada, 2007). The disadvantage of the proposed heuristic is its inability to guarantee optimality of the Pareto Front, an issue also observed with the single objective formulation since the majority of resolution algorithms presented in the literature for the single objective BAP do not guarantee optimality. Future research can focus on exploring the computational efficiency of algorithms that could guarantee local optimality of the Pareto Front (Golias, 2007 and Taboada, 2007) and can be applied after a Pareto Front has been obtained by another (meta)heuristic; a procedure known as post-Pareto analysis.