# Integrated Berth Allocation-Quay Crane Assignment Problem: Reformulations, Improved Constraints and Computational Results

- Authors:
- Abstract:
- Nowadays, large container terminals can process more than 30 million containers a year, and are constantly in search for the best ways to optimize processing time and deliver high quality, and profitable, services. Most of the operational problems on a container terminal are interconnected. The productivity of container terminals heavily relies on the efficiency of quay cranes operations, and the usage of the berthing area. Optimizing the allocation of ships to berth and the related assignment of cranes are important problems that are mostly covered as two separate cases in the literature. However, since the handling time of the vessels primarily depends on the number of containers to be handled and the number of cranes deployed, it would be beneficial to consider the integration of those two problems. In this work we extend the current state of the art by strengthening the current best formulation and by proposing novel set partitioning models. Finally, computational experiments are carried out to analyze the performances of the new formulations with respect to modeling capabilities, solution quality and execution time. Considerable amount of studies have been done on the berth allocation problem (BAP) and the quay crane assignment problem (QCAP). Such integrated problem is known in the literature ([1]) as the Berth Allocation and Crane Assignment Problem (BACAP). The state-of-the-art [1] models this problem using two decision variables X_ij and Y_ij, representing respectively the partial order of the time and space dimension of the berth assignment, where i and j are two vessels. Moreover the variables r_itq define the number of cranes q to be assigned to vessel i at time t, and a set of auxiliary variables such as the vessel start time S_i. An optimal solution to the BACAP minimizes a number of operational costs, such as the tardiness of the schedule, vessel speedup cost, and crane operation cost. The contribution of this work is twofold. First, we improve the model presented in [1] by proposing a number of valid inequalities. Second, we introduce a novel set partitioning formulation and present preliminary results. We propose an improved version of this model in the form of a set of valid inequalities aimed at improving the LP bound of the formulation. First we focus on the vessel start time. Increasing these bounds will, most likely, increase the lower bound obtained from LP relaxation since start-time variables S_i are integrated into objective function. Inequality (1) is based on the following two observations. First, if vessel i berths before vessel j (X_ij=1), then the start time of vessel j (Sj) should be larger than the start time of vessel i plus its minimum expected processing time (m_i\R_max^i). Second, the start time of j cannot be earlier than the earliest possible time of arrival (EST). Another inequality forces at most one kind of crane assignment plan for each of periods and vessels (2). The berthing time of vessel should be within the interval of minimum and maximum possible processing time (3). Finally, there cannot be any processing before the earliest arrival time of vessels (4). Preliminary results on the first 10 instances of the benchmark in [1] are presented in Table 1. The table compares the model from [1] and our improved version (BACAP+). It is observed that given the time limit of 10 minutes, BACAP+ finds improvements Table 1. CPLEX Results for BACAP+ Meisel and Bierwirth [1] Results Valid Inequalities (BACAP+) Ins. Z LB GAP1 Obtained LB Integer Solution Obtained GAP2 CPU Time Z LB GAP3 CPU Time 1 84,1 84,0 0,12% 76,0 X 10,67% 600* 84,1 80,79 4,10%(l) 600* 2 53,9 53,9 0,00% 53,9 + 0,00% 289,6* 53,9 53,9 0,00% 31,4 3 77,4 75,2 2,93% 66,6 X 16,25% 600* 78,4 71,2 10,07% 600 4 76,2 75,8 0,52% 68,1 X 11,30% 600* X 73,1 3,60%(l) 600 5 56,8 56,8 0,00% 56,8 + 0,00% 453* 56,8 56,8 0,00% 368 6 57,6 57,6 0,00% 57,2 X 0,79% 600* 57,6 57,6 0,00% 27 7 68,0 67,5 0,74% 63,0 X 7,97% 600* 68,0 67,9 0,19% 600 8 56,1 56,1 0,00% 51,3 X 9,42% 600* 56,1 55,8 0,59% 600* 9 75,1 75,0 0,13% 74,9 X 0,33% 600* 75,1 75,0 0,15% 600* BACAP can also be formulated as Generalized Set Partitioning Problem (GSPP). The model is an extension of the BAP formulation in [2] where we add new set definitions and constraints that relate to the crane assignment. Here each column represents a feasible assignment plan for a vessel (that includes both crane allocation and berth assignment). Let the variable λ_p∈{0,1} be the selection of the assignment plans p∈ω. The model minimizes the time dependent costs (D_p) and the crane assignment costs (C_p). Constraints ensure that each vessel is assigned to one plan, that at a given time t and position s at most one plan can be selected, and that at most one crane amount can be selected in a given plan with the knapsack constraint ∑_(p∈ω)▒〖D_p^t λ_p≤Q〗 ∀t∈T, where the number of cranes is captured by the parameter Q. The results shown in Table.2 are for fixed number of QC through stay at port. Table 2. CPLEX Results for GSPP and [1] Meisel and Bierwirth [1] results for Fixed QC number GSPP results for Fixed QC number Ins. Z LB GAP1 GAP2 CPU Time Z LB Number of columns Column Time Solver Time 1 X 81,1 - 14,50% 1200* 89,0 89,0 312410 50,56 590,42 2 56,2 56,2 0,00% 0,00% 556* 56,2 56,2 334321 42,88 327,6 3 X 76,3 - 14,94% 1200* 85,7 85,7 249518 39,18 533,98 4 X 61,2 - 38,27% 1200* 81,8 81,8 385867 56,16 612,5 5 X 55,6 - 14,01% 1200* 59,2 59,2 271922 43,5 152,15 6 61,2 59,2 3,38% 9,46% 210* 59,2 59,2 301834 40,93 235,16 7 78,2 69,8 12,8% 15,81% 1200* 75,2 75,2 326629 44,67 561,45 8 X 53,6 - 27,66% 1200* 61,4 61,4 355334 47,32 584,23 9 X 73,7 - 7,22% 1200* 78,1 78,1 312410 50,56 562,3 Results show that model [1] is not capable to find an integer solution in most cases where number of QC is not changing through the stay of vessel at terminal. However, set partitioning formulation obtains optimum values in reasonable computational time.
- Type:
- Conference abstract
- Language:
- English
- Main Research Area:
- Science/technology
- Review type:
- Peer Review
- Conference:
- 4th International Conference on Computational Logistics, 2013
- Submission year:
- 2013
- Scientific Level:
- Scientific
- ID:
- 250261551