Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems

Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems

Computers & Industrial Engineering xxx (2016) xxx–xxx Contents lists available at ScienceDirect Computers & Industrial Engineering journal homepage:...

1MB Sizes 0 Downloads 8 Views

Computers & Industrial Engineering xxx (2016) xxx–xxx

Contents lists available at ScienceDirect

Computers & Industrial Engineering journal homepage: www.elsevier.com/locate/caie

Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems A. Karam a,b,⇑, A.B. Eltawil b a b

Mechanical Engineering Department, Faculty of Engineering at Shoubra, Benha University, Cairo, Egypt Department of Industrial Engineering and Systems Management, Egypt-Japan University of Science and Technology (E-JUST), Alexandria, Egypt

a r t i c l e

i n f o

Article history: Available online xxxx Keywords: Berth allocation Quay crane assignment Container terminal Functional integration

a b s t r a c t In container terminals, the integrated planning of berth allocation and quay crane assignment problems has attracted much attention in literature. These problems can be integrated either by functional integration or by deep integration approaches. In the functional integration approach, these problems are integrated by being divided into two sub-problems and a feedback loop is used to interconnect them. A presumed vessel handling time is used for each vessel at first to initiate the integration mechanism. The functional integration approach achieves the required performance of each problem and is less complicated compared with the deep integration in which the two problems are merged into a unified model. However, the sensitivity of the solution to the assumed vessel handling time and the non-convergence to a stable state are the weak points of the functional integration approach. This paper presents a new functional integration approach for the following problems: berth allocation, quay crane assignment and specific quay crane assignment. Numerical experiments are conducted to test the performance of the proposed approach. The results illustrate that the proposed approach shows no sensitivity to the presumed handling time and a significant improvement in the convergence to stable state. Compared to a unified model from literature, the effectiveness of the proposed approach is investigated. In addition, by using actual container terminal data, the applicability of the proposed approach is demonstrated. Ó 2016 Elsevier Ltd. All rights reserved.

1. Introduction The development of containerized shipment provided cheap and fast transport of goods around the world. Therefore, containerized trade grew with an average annual rate of 6.5% from 1996 to 2013 (UNCTAD, 2014). Moreover, the share of containerized trade in the total volume of global trade increased from 22% in 1980 to 67% in 2012 (Chiang, 2013). This drastic growth and the competitive environment together put more pressure on container terminals to improve their performance. Therefore, the optimization of container terminal operations has been paid increasing attention in the scientific literature over the last few years. Container terminal operations can be grouped into quay side, transfer, yard and gate operations (Voß, Stahlbock, & Steenken, 2004). In this paper, we concentrate on the integrated planning

⇑ Corresponding author at: Mechanical Engineering Department, Faculty of Engineering at Shoubra, Benha University, 108, Shoubra Street, Cairo, Egypt. Tel.: +20 1008240548. E-mail addresses: [email protected], [email protected] (A. Karam).

of quay side operations. Planning decision problems at the quay side include the Berth Allocation Problem (BAP), the Quay Crane Assignment Problem (QCAP), the Specific Quay Crane Assignment Problem (SQCAP) and the Quay Crane Scheduling Problem (QCSP). In the BAP, the berthing position, berthing time and departing time of each vessel are determined using estimates of the vessels’ handling times and taking into account temporal and spatial constraints. In the QCAP, the vessel handling times are calculated based on a number of QCs assigned to each vessel, the number of containers to be handled and the average productivity of quay cranes (container moves/hour), taking into account the quay crane capacity of the terminal. The SQCAP follows the QCAP and determines the specific quay cranes to serve each vessel. The QCSP follows the quay crane assignment problem and determines the detailed schedules of the assigned quay cranes by providing the sequence of container unloading and loading operations on each vessel that a quay crane is supposed to perform. This paper specifically addresses the integration of the Berth Allocation Problem (BAP), the Quay Crane Assignment Problem (QCAP) and the Specific Quay Crane Assignment Problem (SQCAP). Fig. 1 shows the inputs and outputs of these three problems as well as their interrelations.

http://dx.doi.org/10.1016/j.cie.2016.04.006 0360-8352/Ó 2016 Elsevier Ltd. All rights reserved.

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

2

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

Fig. 1. Planning of berth allocation and quay crane assignment in container terminal.

These problems are typically solved independently as suggested by initial research. However, the planning decisions of berth allocation and quay crane assignment problems are tightly interrelated as the handling times of vessels, which are input to the BAP, can be determined by the QCAP. On the other hand, the berth schedules of vessels (berthing time, berthing position and departing time) which are input to the QCAP are determined by the BAP. For this reason, current research trends in container terminal management are focusing on the integrated planning of quay side operations. Efficient planning of quay side operations directly affects the vessel turnaround time which is the most important performance measure for rating container terminals. In general, there are two main approaches for integrating subproblems, namely the deep integration approach and the functional integration approach (Geoffrion, 1994). The deep integration approach involves merging the sub-problems into a unified model. For example, the BAP and the QCAP can be deeply integrated by unifying them into one problem of berth allocation and quay crane assignment. In the functional integration approach, the subproblems are divided into a top level problem and a base level problem according to the hierarchical relation between them. To integrate the two levels, an integration mechanism is constructed between them. The integration mechanism includes a coupling variable, i.e. the shared variable between the sub-problems and a feedback loop. For example, the vessel handling time is used as a coupling variable to functionally integrate the BAP and the QCAP. To initiate the integration mechanism, the vessel handling times are presumed to solve the BAP which determines the berth schedule for the vessels. The berth schedule is then input to the base level problem (QCAP), in which the handling time for each vessel is determined. The results of the QCAP are returned again to the BAP by the feedback loop. The vessel handling times are updated in such way until this loop terminates once the iterative approach converges to the stable state at which the same berth schedule is obtained in successive iterations. Compared with the deep integration approach, many merits of the functional integration approach are reported in literature (Yang, Wang, & Li, 2012). The most important merits are the reduced complexity, the flexibility to consider more practical issues and the consideration of the performance of each problem. However, the sensitivity of the solution to the assumed handling time as well as the non-convergence to a stable state, are still weak points in the existing approaches (Meier & Schumann, 2007; Yang et al., 2012). In this paper, we introduce a new functional integration approach for the BAP, QCAP and SQCAP. There is only one func-

tional integration approach for the BAP and the QCAP proposed by Yang et al. (2012). In the approach of Yang et al., practical aspects related to the quay crane assignments are ignored such as the time-variant QC assignments. The consideration of the time-variant QC assignments well improves the solutions as will be illustrated in Section 4.3. In addition, we include the SQCAP in the proposed approach. To investigate the performance and the applicability of the proposed approach, comparisons of the proposed approach with the optimal solutions of two different deep integration approaches proposed by Meisel and Bierwirth (2009) and Türkogulları, Taskın, Aras, and Altınel (2014) are conducted. The remainder of this paper is organized as follows: Section 2 provides a review of related studies in recent years. Section 3 discusses the frame work of the proposed approach. Numerical experiments are introduced in Section 4. The conclusions and recommendations are in the last section. 2. Literature review In this section, we review only studies related to the integration approaches of the quay side operations. The BAP is classified according to the berth layout and the arrival of vessels. According to Bierwirth and Meisel (2015), there are three cases for the berth layout, namely discrete, continuous and hybrid berth layout. In the discrete layout, the quay is divided into a finite set of sections, called berths, and only one vessel is allocated a single berth at time. Moreover, the lengths of the single berths are usually different. In the continuous case, the quay is divided into equally sized berthing sections and each vessel is allocated a number of berthing sections equal to the vessel length, a safety distance should be included among vessels when they are berthed adjacently. The continuous case provides better utilization of the quay as two vessels, if their length together is less than the length of a single berth, can be berthed simultaneously at it. The hybrid berth layout is similar to the discrete berth layout but a number of small vessels can be served at a single berth, while a large vessel can be served at a number of berths. Besides the berth layout, the BAP can be further classified according to the arrival time of vessels which can be static or dynamic. The static case assumes that all vessels are already in the port when the berth allocation is planned, whereas the dynamic case restricts the earliest berthing times of vessels such that vessels can’t be berthed earlier than its arrival time. Quay crane assignment is also classified into the time-invariant quay crane assignment and the time-variant quay crane assignment. In the time-invariant quay crane assignment, the number

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

of quay cranes assigned to the vessel cannot be changed during the handling operation of the vessel while in the time-variant quay crane assignment, the number of quay cranes can be changed dynamically between the minimum and maximum limits of quay cranes that can be assigned to the vessel. It should be noted that changing the number of assigned quay cranes is sometimes necessary for better utilization of quay cranes as well as less handling times. For example, some of the quay cranes assigned to vessels are moved to start handling operations of other vessels. In literature, there are different integrated versions of the BAP, QCAP, and SQCAP. Integrating the BAP and the QCAP leads to an integrated problem called Berth Allocation Crane Assignment Problem (BACAP) while if the BACAP is extended to determine the specific quay cranes to serve each vessel. In that case, it is called the Berth Allocation Crane Assignment Specific Problem (BACASP). The deeply integrated BACAP has been pioneered by Park and Kim (2003). In their work, they inserted the QCAP as constraints into the BAP to determine the handling times of vessels. On the other hand, the functionally integrated approach has been pioneered by Meier and Schumann (2007). They functionally integrated the berth allocation approach proposed by Guan and Cheung (2004) and the quay crane scheduling approach proposed by Zhu and Lim (2006). The handling time for each vessel is assumed then the BAP is solved by simulated annealing. The obtained berth schedule is then sent to the quay crane scheduling problem which is solved by a genetic algorithm. A feedback loop is used to update the BAP by the handling time of each vessel which is determined by the QCSP. The loop iterates until a stable state is reached. They reported that the simple coordination between the two sub-problems leads to results similar to the results obtained from the sequential method. Furthermore, their approach didn’t converge to a stable state in the numerical experiment. The deep and functional integration approaches suggested by Park and Kim (2003) and Meier and Schumann (2007) respectively, are then adopted in recent research by other researchers. Studies that addressed deep integration when solving the BACAP and the BACASP can be found in (Chang, Jiang, Yan, & He, 2010; Giallombardo, Moccia, Salani, & Vacca, 2010; Imai, Chen, Nishimura, & Papadimitriou, 2008; Liang, Huang, & Yang, 2009; Meisel & Bierwirth, 2009; Park & Kim, 2003; Türkogulları et al., 2014; Ursavas, 2014; Vacca, Salani, & Bierlaire, 2013; Zhang, Zheng, Zhang, Shi, & Armstrong, 2010). These papers introduce optimization models to decide on the berthing time, the completion time, the berthing position, and the number of quay cranes assigned for each vessel. In some cases, the specific quay cranes used for serving the vessels are also determined (Imai et al., 2008; Türkogulları et al., 2014; Ursavas, 2014; Zhang et al., 2010). In these studies, the problems of berth allocation and quay crane assignment are unified into one optimization model. Thus, the interrelations between these problems can be considered and therefore, this results in more efficient planning than the sequential method. However, the objective function of the unified model is only related to the BAP and therefore, the performance of quay crane assignment is not taken into consideration. This is because the consideration of the performance of quay crane assignment in the unified model requires additional constraints which in turn increase the complexity of the unified model to a large extent. Thus, the unified model may be unsolvable even for a small problem size. In addition, Some studies impose assumptions to reduce the complexity of the proposed unified models (Liang et al., 2009; Türkogulları et al., 2014; Zhang et al., 2010). The most employed assumption is the time-invariant QC assignment, which is referred to as the QCAP (time-invariant). According to Meisel (2009), the consideration of the time-variant quay crane assignment is essential for improved solution quality and practical application.

3

However, this leads to an increased complexity of the proposed model. The functional integration approach has been adopted in few studies of quay side problems (Lokuge & Alahakoon, 2007; Meier & Schumann, 2007; Meisel & Bierwirth, 2013; Song, Cherrett, & Guan, 2012; Yang et al., 2012). The only functional integration approach of the BACAP found in literature, is proposed by Yang et al. (2012). In their work, they used the BAP proposed by Guan and Cheung (2004) while a time-invariant QCA model was proposed following the formulation introduced by Legato, Gullì, and Trunfio (2008). Moreover, the BAP and the QCAP were solved by employing a genetic algorithm for each problem and a feedback loop is used to interconnect the two problems. They compared their approach to the deep integration approach proposed by Park and Kim (2003). They could improve the average service time per vessel and the average quay crane shift per vessel by 9.27% and 23.8% respectively. However, the authors reported that the solution of the proposed approach is affected by the value of the assumed handling time. Moreover, in case of assuming a too small handling time for the vessel, the proposed approach doesn’t converge to a stable state. To sum up, the functional integration approach of the BAP, QCAP and SQCAP is not considered in literature. To the best of our knowledge, there is only one functional integration approach for the BAP and the QCAP proposed by Yang et al. (2012). In the approach of Yang et al., they considered the time-invariant QC assignemnts. Nevertheless the performance of the quay crane assignments depends on minimizing the vessels handling times as well as the QC shifts from a vessel to another (Legato et al., 2008). Yang et al. (2012) considered only the minimization of the QC shifts. In addition, the robustness of the existing functional integration approach is weak in the sense that some scholars (Meier & Schumann, 2007; Yang et al., 2012) reported major issues such as the effect of the assumed container handling time on the final solution and the non-convergence to stable state. Moreover, validation of the functional integration approach against the optimal solutions of the deep integration approach is ignored in literature. For this reason, in this paper, a functional integration approach for the BAP, QCAP (time-variant) and SQCAP is proposed to fill the existing gaps in literature. The proposed approach is validated against the optimal solutions provided by two deep integration models found in literature. 3. The modeling approach In order to functionally integrate the BAP, QCAP and the SQCAP, the three problems are reduced to two problems as follows; the top level problem is the BAP while the base level problem is made up by merging the QCAP and the SQCAP into one problem called the Quay Crane Assignment Specific Problem (QCASP). Then, the two problems are solved optimally and functionally integrated by using a feedback loop. In this section, the formulations of the BAP and the QCASP are explained in details, then, the procedures of the functional integration approach are discussed. 3.1. The berth allocation model We present a formulation for the BAP similar to the formulation in Türkogulları et al. (2014) in which the continuous berth layout and dynamic arrival of vessels are considered. The berth allocation model is formulated based on the following assumptions: 1. All vessels are previously planned for a desired berthing position. 2. The arrival time of all the vessels are known in advance. 3. The berthing position of the vessel is not affected by its draft.

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

4

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

3.2. The quay crane assignment specific model

The following notations are used: Sets V Set of vessels, V = {1, . . . , n} (indexed by i). T Set of time periods, T = {1, . . . , N} (indexed by t). B Set of berthing positions, B = {1, . . . , L) (indexed by j).

The QCAS model not only assigns QCs to each vessel but it also specifies the individual QCs to serve each vessel while respecting the non-crossing constraint of the quay cranes. The QCAS model is formulated based on the following assumptions:

Parameters li The length of vessel i, including the allowance distance between vessels. hti The assumed handling time of vessel i. ai The expected arrival time of vessel i. di The expected departure time of vessel i. The desired berthing position of vessel i. bi

1. The handling operation of the vessel can’t be interrupted once it has started. 2. The handling operation of the vessel starts only if the number of quay cranes assigned to the vessel is between its maximum and minimum specified limits of QCs. 3. There is an enough number of internal trucks to transfer containers.

L N n c1 c2 c3

Number of berthing positions. Number of time periods. Number of incoming vessels. The penalty cost for unit distance deviation between the berthing position and the desired one bi . The penalty cost for the delayed berthing time of the vessel. The penalty cost for the delayed departure time of the vessel.

The following notations are used: Sets Q

Sets of quay cranes, Q = {1, . . . , qc} (indexed by k).

Parameters P i þ1 PNhti þ1 bti The berthing time of vessel i, bti ¼ Ll t  xijt t¼ai j¼1

Decision variables xijt 1, if the vessel i is berthed at berthing position j and its berthing time starts at t, 0 otherwise.

cti bpi

The promised departing time of vessel i, cti = bti + hti - 1. The berthing position of vessel i, P i þ1 PNhti þ1 bpi ¼ Ll j  xijt . t¼ai j¼1

NC i

The number of the loading and discharging containers of vessel i in (TEU). Maximum number of quay cranes that can be assigned to vessel i. Minimum number of quay cranes that should be assigned to vessel i. Available total number of quay cranes. Average time consumed in one QC shift from a vessel to another. The productivity of the quay crane, TEU/h. A sufficiently large positive constant.

qimax The model is formulated as follows:

Obj:1 : Minimize

i þ1Nht XLl X Xi þ1

i2V

j¼1

qimin

ðc1  jj  bi j þ c2  ðt  ai Þ þ c3

qc r

t¼ai

 maxð0; t þ ht i  1  di ÞÞ  xijt

pr M

Subjected to

X

0 minðLl Xi þ1;j Þ

0 minðNht Xi þ1;t Þ

0

xijt 6 1 8j 2 B;

t0 2 T

ð1Þ

i2V j¼maxð1;j0 li þ1Þt¼maxðai ;t 0 ht i þ1Þ

Ll i þ1Nht X Xi þ1 j¼1

xijt ¼ 1 8i 2 V

ð2Þ

t¼ai

Decision variables 1, if quay crane k is assigned to vessel i in time period t, qkit 0 otherwise. Integer, the difference between the number of quay f it cranes assigned at time period (t + 1) and those assigned at time period t. 1, if vessel i is handled at time period t, 0 otherwise. hit Integer, the position of quay crane k at time period t. bkt

xijt 2 f0; 1g 8i 2 V; j 2 1; . . . ; L  li þ 1; t ¼ ai ; . . . ; N  hti þ 1 ð3Þ The objective function aims at minimizing the weighted sum of the handling costs of containers and was used before in literature (Türkogulları et al., 2014; Zhang et al., 2010). The handling cost of containers comprises three cost components. The first cost is the cost of deviation between the berthing position of the vessel and the yard where the outbound containers of the corresponding vessel are stored. The yard is represented by the desired berthing position of the vessel. The second cost component is the penalty cost, when the berthing time of vessel is later than the expected arrival time of the corresponding vessel. The third cost component is the penalty cost incurred when the departure time of the vessel is later than the expected departure time. Constraint (1) ensures that each berth section is allocated to only one vessel at each time period. Thus, this constraint guarantees that vessels don’t overlap with each other in the space–time diagram. Constraint (2) ensures that each vessel is served within the planning horizon. Constraint (3) is a binary constraint.

The model is formulated as follows

Obj:2 : Minimize

X 1 X max ðt  hit  bt i Þ þ r  jf it j n i2V t¼ST i ;...;CT i i

!

Subjected to

hit P hiðtþ1Þ pr 

ct i XX

8i 2 V; t ¼ bti ; . . . ; cti

qkit P NC i

8i 2 V

ð4Þ ð5Þ

k2K t¼bti i 1 XbtX

qkit ¼ 0 8i 2 V

ð6Þ

k2K t¼1 N X X

qkit ¼ 0 8i 2 V

ð7Þ

k2K t¼ct i þ1

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

X qkit 6 1 8k 2 K; t 2 T

5

ð8Þ

3.3. The solution procedures

ð9Þ

The detailed flow chart of the proposed approach is shown in Fig. 2. First, an initial value of the handling time for each vessel hti is assumed. The vessel handling time is initially estimated by

i2V

X qkit 6 qimax  hit

8i 2 V; t ¼ bti ; . . . ; ct i

k2K

NC i , s

bkt 2 f1; . . . ; Lg 8k 2 K; t 2 T

ð17Þ

where s is the productivity obtained from assigning a number of quay cranes simultaneously to a vessel for one hour. Note that s differs from a vessel to another according to the number of quay cranes assigned to each vessel. Therefore, we assume that s ranges from 100 to 200 which results from preliminary experiments. In case that s is lower than 100, the initial value of the vessel handling time may be too large. While if s is over 200, the initial value of the vessel handling time may be too small. Note that if the initial value of the vessel handling time is too large or small, this would negatively affect the computational time of the proposed approach as will be discussed in Section 4.1. It is important to note that the assumed handling time is used only at the first iteration to initiate the integration mechanism of the functional integration. As shown in Fig. 2, the berth schedule is obtained from the BA model and used as input to the QCAS model. If feasible QC assignments are obtained, the handling time of each vessel is sent to the BA model through the feasible loop to revise the berth schedule based on the updated handling times. The loop terminates and the final solution is found once a stable state is reached. The stable state means that the BA model provides the same solution two times successively. On the other hand, if no feasible QC assignments are obtained, the handling time of each vessel hti is increased by a factor (m) which is randomly selected from 1.1 to 2.0. Then the updated handling time is returned again to the BA model through the infeasible loop to revise the berth schedule.

hit ; qkit 2 f0; 1g 8i 2 V; 8k 2 K; t 2 T

ð18Þ

4. Numerical experiments

X qkit P qimin  hit

8i 2 V; t ¼ bti ; . . . ; cti

ð10Þ

k2K

XX qkit 6 Q

8t 2 T

ð11Þ

k2K i2V

X X qkiðtþ1Þ  qkit 6 f it k2K

8i 2 V; t ¼ bt i ; . . . ; cti

8k 2 K; t 2 T

bkt < bðkþ1Þt bkt P bpi  qkit

ð13Þ

8i 2 V; 8k 2 K; t 2 T

bkt 6 ðbpit þ l  1Þqkit þ Mð1  qkit Þ 8i 2 V; 8k 2 K; t 2 T max ðk  qkit Þ 

k2fKjqckit ¼1g

(

ð12Þ

k2K

X qkit

min

k2fKjqckit ¼1g

ð14Þ ð15Þ

ðk  qkit þ Mð1  qkit ÞÞ þ 1

8i 2 V; 8k 2 K; t 2 T

ð16Þ

k2K

The objective function aims at minimizing the average handling time per vessel. The handling time of the vessel represents the length of time between the berthing time at which the vessel is berthed and the departure time at which the vessel leaves the berth. The average handling time per vessel can be defined as the sum of the handling times for all the vessels divided by the number of vessels. The first term represents both, the handling time and the waiting time for handling containers on the vessel while the second term represents the time incurred when there is change in the number of QCs during handling operation. Constraint (4) guarantees that the vessel operation can’t be interrupted once it has started. Constraint (5) ensures that the containers on each vessel must be completely handled between its berthing and promised departure times. Constraints (6) and (7) ensure that no quay cranes are used in handling containers on any vessel outside the window between its berthing and promised departure times. Constraint (8) guarantees that any quay crane can be assigned to only one vessel at each time period. Constraints (9) and (10) ensure that the number of quay cranes assigned to each vessel is between the maximum and minimum specified limits. Constraint (11) ensures that at each time period, the number of quay cranes assigned to all vessels do not exceed the total available number of quay cranes. Constraint (12) defines the variable fit. Constraint (13) ensures that the non-crossing constraint of the quay cranes is respected. This means that the position of quay crane k is always lower than the position of quay crane (k + 1) all through the planning horizon. Constraints (14) and (15) ensure that if quay crane k is assigned to vessel i, then the position of the quay crane must be within the first and last berthing positions of vessel i. Constraint (16) ensures that the quay cranes assigned to vessel i are adjacent. Constraint (17) ensures that each QC is positioned within the berth boundaries. Constraint (18) defines domains for the remaining decision variables.

To test the effectiveness of the proposed approach, three experiments are carried out. First, the performance of the proposed approach under different handling time estimates is investigated. Second, a comparison of the proposed approach with the optimal solutions obtained by a unified model found in literature is done. Finally, the proposed approach is examined in some real cases. In the following, the proposed approach is referred to as the Feedback Loop Function Integration Approach (FLFIA). All the experiments are conducted on a PC with 2.3 GHz processor and 4 GB RAM working under windows 7 operating system. Both of the BAP and QCAP are solved optimally using CPLEXTM 12.2. The feedback loop is also coded in CPLEXTM 12.2. 4.1. Testing the proposed approach with different estimates of handling time As illustrated in literature, existing functionally integrated approaches (Meier & Schumann, 2007; Yang et al., 2012) reported that the result was sensitive to the assumed vessel handling time. The proposed approach in this paper does not suffer from this issue. For clarification, an instance is solved by the FLFIA at differNC i NC i NC i NC i NC i ent estimates of the handling time of 110 , 130 , 150 , 170 and 190 respectively. Fig. 3 shows the effect of the assumed handling time on the final solutions (Obj.1 and Obj.2), the number of iterations and the computational time on a dimensionless scale. The solutions (Obj.1 and Obj.2) of FLFIA show no sensitivity to the assumed handling time at the different handling time estimates. Moreover, the FLFIA converges to a stable state in case of using large estimate     NC i NC i NC i NC i or small estimate 170 ; ; 190 of the vessel handling time. It 130 110

can be noted from Fig. 3 that in case of assuming a large handling

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

6

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

Fig. 2. The flow chart of the proposed approach.

4.2. Comparison with the Meisel–Bierwirth approach

Fig. 3. Variations of objective functions, computational time and number of iterations with different estimates of vessel handling time.

time, this leads to a larger number of iterations. Therefore, the computational time needed to reach the stable state is relatively longer than the case of assuming a smaller handling time. Compared to the approach of Yang et al. (2012), the improvement in the robustness of the solution produced by the FLFIA, is mainly caused by the objective function of the QCAS model. This can be explained as follows; the objective function of the QCAS model aims at minimizing the vessel handling time and the number of QC shifts. Consequently, if the vessel handling time is assumed as a large value, the QCAS model reduces the vessel handling time to the needed value and returns it again to the BA model through the feedback loop. While in the Yang et al.’s approach, the objective function of the QCA model aims at minimizing only the number of QC shifts. So, Yang et al.’s approach has no control to minimize the large handling time that is why their approach suffered from the sensitivity of the final solution to the assumed handling time. It can be also observed from Fig. 3 that the computational time NC i and the number of iterations are relatively low at 150 . Consequently, this handling time estimate is used in all experiments in Section 4.2 and 4.3.

To test the performance of the FLFIA, the optimal solutions of the deeply integrated BACAP proposed by Meisel and Bierwirth (2009) is compared with the solutions of the FLFIA. The objective function of the Meisel–Bierwirth approach is changed into the BA model’s objective of the FLFIA. Moreover, constraints (13)–(17) were eliminated from the QCAS model in all experiments as they aren’t considered in Meisel–Bierwirth approach. A set of small congested instances were randomly generated using data and distributions from Zhang et al. (2010). The word ‘‘congested” means that the vessels in these instances arrive approximately at the same time and are heavily overlapped. Such instances are hard to solve and can effectively test the performance of optimization models (Salani & Bierlaire, 2010). Therefore, the arrival time of the vessels is randomly generated from UD[1, 2] if the number of vessels is 4, while the arrival time is randomly generated from UD[1, 4] if the number of vessels is 6. In addition, the number of the containers on each vessel is generated from UD[500, 1000]. The productivity of the quay crane (pr) is set to 30 TEUs/h while c1 , c2 and c3 are set to 1000, 1000 and 2000 respectively. Table 1 includes the data associated with an instance of four vessels. The solutions of this instance with 12 quay cranes and 24 berthing positions by the FLFIA and the Meisel–Bierwirth approach are shown in Figs. 4 and 5 respectively. For this sample problem instance, the two approaches could produce the same handling cost of vessels (obj.1) which is $3000. However, the FLFIA

Table 1 The data for the sample problem instance. Vessel

li

ai

di

bi

qimax

qimin

NC i

1 2 3 4

5 6 6 5

1 2 1 2

12 15 12 13

19 11 2 5

4 5 5 4

2 3 3 2

600 750 540 780

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

produces better QC assignments compared with the Meisel– Bierwirth approach. For the clarification, consider vessel 2 in Figs. 4 and 5 as an example. It can be noted that the QC assignments of vessel 2 in Fig. 4 incurs fewer QC shifts (3 QC shifts) compared with the QC assignments of vessel 2 in Fig. 5 which incurs 5 QC shifts. It is important to note that, the more the QC shifts, the more crane movements during the service of vessels, which in turn disrupts the smoothness of the handling operations and incurs additional time due to the setup of the QCs. Furthermore, it can be also noted that the handling time of vessel 2 in Fig. 4 is less than that in Fig. 5 by one hour. On average, the FLFIA improved the average handling time of the vessels (obj.2) by 5.9% compared with the Meisel– Bierwirth approach. Eight small instances are further generated while in total, 24 combinations are generated by solving each instance at (qc = 12, L = 24), (qc = 12, L = 18) and (qc = 10, L = 24) respectively. Table 2 shows the comparison of the results obtained from the FLIA against the Meisel–Bierwirth approach. In Table 2, the ‘‘no convergence” entry designates that no solutions were found by the FLFIA for instances #7, 11, 15, 22 and 23. The reason is that the FLFIA doesn’t converge to a stable state in these instances and therefore the termination of the iterated procedure doesn’t occur. The main cause of this event to occur, is that most of the vessels, in such instances, have the same arrival time. For example, in instance #23, the first four vessels have an arrival time of 1 while the fifth and sixth vessels have an arrival time of 2 and 3 respectively. The extent of overlapping is much higher in this instance and may not occur in reality. Therefore, a feasible QC assignment is hard to be found especially with the limited number of quay cranes. Consequently, instances #7, 11, 15, 22 and 23 are excluded as they may not occur in reality. Compared with the Meisel–Bierwirth approach, we can see that the FLFIA could obtain the optimal value of the handling cost of vessels (obj.(1)). However, there are some exceptions, such as the instance #9. This may be caused by the limitation of the FLFIA when the extent of overlapping the vessels with each other is much higher. On average, the handling cost of vessels produced by the FLFIA slightly increased the optimal solutions by 2.46%.

7

On the other hand, the FLFIA well improves the average handling time of vessels by 10.61%. This is to say that the FLFIA could guarantee the performance of the individual problems, i.e. BAP and QCAP, when integrated. In other words, holistically solving the integrated berth allocation and quay crane assignment problem may not be effective due to considering the performance of one problem, i.e. BAP and ignoring the performance of the other problem, i.e. QCAP. 4.3. Using the proposed FLFIA to solve realistic problems The purpose of this section is to test the applicability of the FLFIA in realistic size problems. Seven instances were derived from the data in the work of Zhang et al. (2010). In this data, there are 21 vessels and 12 quay cranes where the 1200 m long berth is divided into 24 berth slots each of which is 50 m and the planning horizon is 200 h. Türkogulları et al. (2014) provided the optimal solutions for the seven instances produced by a deeply integrated BACAP (time-invariant). Therefore, for comparison with Türkogulları et al.’s approach, constraints (13)–(17) were eliminated from the FLFIA in all experiments. Table 3 shows the comparison of the solutions produced by the FLFIA with the optimal solutions provided by the deeply integrated BACAP (time-invariant) of Türkogulları et al. (2014). The FLFIA provides better objective values to the seven instances solved optimally by Türkogulları et al. (2014). The reason is that the QC time-variant assignment is considered in the FLFIA while the approach of Türkogulları et al. (2014) uses the QC time-invariant assignment. We can also note that the CPU time of the FLFIA exceeded that of Türkogulları et al. (2014). Nevertheless, the CPU time of the proposed approach is still suitable for practical application. 5. Conclusions and future research direction In this work, the berth allocation, the quay crane assignment and the specific quay crane assignment problems have been

Fig. 4. The solution produced by the FLFIA for the sample problem instance given in Table 1.

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

8

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

Fig. 5. The optimal solution produced by the Meisel–Bierwirth approach for the sample problem instance given in Table 1.

Table 2 Results of solving the small instances. Combinations n  qc  L

Instances

The FLFIA Obj.(1) ($)

4  12  24 4  12  24 4  12  24 4  12  24 4  12  24 6  12  24 6  12  24 6  12  24 4  10  24 4  10  24 4  10  24 4  10  24 4  10  24 6  10  24 6  10  24 6  10  24 4  12  18 4  12  18 4  12  18 4  12  18 4  12  18 6  12  18 6  12  18 6  12  18

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

The BACAP Obj.(2) (h)

9000 6.33 3000 5.13 8000 6.33 7000 5.53 8000 4.93 11,000 6.33 No convergence 22,000 6.13 10,000 5.93 3000 5.53 No convergence 7000 6.73 10,000 4.93 16,000 5.93 No convergence 24,000 8.73 10,000 3.93 4000 5.93 19,000 4.53 24,000 5.13 11,000 4.73 No convergence No convergence 37,000 7.13

No. of iterations

CPU time (s)

5 4 4 2 6 4

4 3 3 2 6 3

4 5 4

4 6 10

2 6 4

4 10 6

4 5 3 2 2 5

6 4 3 2 2 7

4

5

Obj.(1) ($)

Obj.(2) (h)

CPU time (s)

9000 3000 8000 7000 8000 11,000 23,000 22,000 10,000 3000 13,000 7000 9000 14,000 25,000 22,000 10,000 4000 18,000 24,000 11,000 18,000 49,000 37,000

6.45 6.25 6.45 5.65 6.05 6.45 6.45 7.25 7.25 5.53 5.65 7.65 5.85 7.05 8.85 9.05 5.85 5.93 5.05 5.65 5.25 4.28 6.25 8.25

12 10 15.8 12.4 11.3 10 17.8 12.4 78.1 61.2 110.4 100.2 88 98 100 102 70.1 65.2 110.4 100.2 88 391 240 139

Table 3 Results of the realistic instances. Instances

1 2 3 4 5 6 7

Number of vessels

3 6 9 12 15 18 21

Planning horizon (day)

1 1.8 2.5 4.5 5 6 8

The FLFIA

Türkogulları’s approach

Objective function value ($)

No. of iterations

CPU time (s)

Objective function value ($)

CPU time (s)

2000 15,000 18,000 18,000 27,000 33,000 33,000

6 7 11 12 9 11 11

17.2 100.6 167.6 312.43 612.6 710.5 817.6

2000 21,000 21,000 21,000 35,000 43,000 43,000

15.2 45.4 56.3 64.5 107.8 132.4 119.0

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006

A. Karam, A.B. Eltawil / Computers & Industrial Engineering xxx (2016) xxx–xxx

functionally integrated using a feedback loop structure. In the proposed approach, the performance of each sub-problem is considered. On the contrary, the deeply integrated approach usually considers the objective function of one sub-problem. This makes the proposed approach more suitable for practical application. Compared to a functionally integrated approach of the berth allocation and quay crane assignment problem found in literature, the proposed approach considers the time-variant quay crane assignments which are more suitable for practice. Moreover, the numerical experiments showed that the proposed approach could tackle the weak points of previous solutions including the sensitivity of the solution to the presumed handling times and the non-convergence to a stable state, which are reported with the functionally integrated approaches found in literature. The performance of the proposed approach is tested by comparison with the optimal solutions of small congested instances produced by a deeply integrated approach found in literature. The results showed that on average, the handling cost of vessels produced by the proposed approach slightly increased the optimal solutions by 2.46%. While the proposed approach well improves the average handling time of vessels by 10.61%. Generally speaking, the proposed approach could guarantee the performance of the individual problems, i.e. the berth allocation and quay crane assignment problems when integrated. However, there are some instances which can’t be solved by the proposed approach due to non-convergence to stable state. To demonstrate the applicability of the proposed approach, seven instances derived from a realistic case were solved using the proposed approach. The results showed that the proposed approach converged to a stable state in all the instances. Moreover, compared to the optimal solutions of a deeply integrated approach (time-invariant), the proposed approach achieved a better objective function value for all the instances. In the future, a matheuristic approach can be devised by developing a heuristic algorithm to solve the QCASP while the BAP is solved by an exact solver. This can significantly reduce the computational time of the proposed approach and improves the solution quality.

References Bierwirth, C., & Meisel, F. (2015). A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 244(3), 1–15. http://dx.doi.org/10.1016/j.ejor.2014.12.030. Chang, D., Jiang, Z., Yan, W., & He, J. (2010). Integrating berth allocation and quay crane assignments. Transportation Research Part E: Logistics and Transportation Review, 46(6), 975–990. http://dx.doi.org/10.1016/j.tre.2010.05.008. Chiang, J. (2013). Outlook of global container port market with a focus on Asia. In 11th ASEAN port and shipping. . Geoffrion, A. (1994). Structured modeling: Survey and future research directions. ORSA CSTS Newsletter, 15(1), 11–20.

9

Giallombardo, G., Moccia, L., Salani, M., & Vacca, I. (2010). Modeling and solving the tactical berth allocation problem. Transportation Research Part B: Methodological, 44(2), 232–245. http://dx.doi.org/10.1016/j.trb.2009.07.003. Guan, Y., & Cheung, R. K. (2004). The berth allocation problem: Models and solution methods. OR Spectrum, 26(1), 75–92. http://dx.doi.org/10.1007/s00291-0030140-8. Imai, A., Chen, Hsieh Chia, Nishimura, E., & Papadimitriou, S. (2008). The simultaneous berth and quay crane allocation problem. Transportation Research Part E, 44, 900–920. http://dx.doi.org/10.1016/j.tre.2007.03.003. Legato, P., Gullì, D., & Trunfio, R. (2008). The quay crane deployment problem at a maritime. In Proceedings of the 22th European conference on modelling and simulation (pp. 53–53). Nicosia Cyprus. Liang, C., Huang, Y., & Yang, Y. (2009). A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Computers & Industrial Engineering, 56(3), 1021–1028. http://dx.doi.org/10.1016/ j.cie.2008.09.024. Lokuge, P., & Alahakoon, D. (2007). Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents. European Journal of Operational Research, 177(3), 1985–2015. http://dx.doi.org/10.1016/j. ejor.2005.12.016. Meier, L., & Schumann, R. (2007). Coordination of interdependent planning systems, a case study. In R. Koschke, H. Otthein, K.-H. Rödiger, & M. Ronthaler (Eds.), Lecture notes in informatics (LNI) (pp. 389–396). Meisel, F. (2009). Seaside operations planning in container terminals.Heidelberg: Physica-Verlag HD. doi:10.1007/978-3-7908-2191-8. Meisel, F., & Bierwirth, C. (2009). Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E: Logistics and Transportation Review, 45(1), 196–209. http://dx.doi.org/10.1016/j. tre.2008.03.001. Meisel, F., & Bierwirth, C. (2013). A framework for integrated berth allocation and crane operations planning in seaport container terminals. Transportation Science, 130–147 (March 2014). Park, Y. M., & Kim, K. H. (2003). A scheduling method for Berth and Quay cranes. OR Spectrum, 25(1), 1–23. http://dx.doi.org/10.1007/s00291-002-0109-z. Salani, M., & Bierlaire, M. (2010). Optimization of operations in container terminals: Hierarchical vs integrated approaches. In 10th Swiss transport research conference, Ascona, Switzerland, September 1–3. Song, L., Cherrett, T., & Guan, W. (2012). Study on berth planning problem in a container seaport: Using an integrated programming approach. Computers & Industrial Engineering, 62(1), 119–128. http://dx.doi.org/10.1016/ j.cie.2011.08.024. Türkogulları, Y. B., Taskın, Z. C., Aras, N., & Altınel, I. K. (2014). Optimal berth allocation and time-invariant quay crane assignment in container terminals. European Journal of Operational Research, 235, 88–101. http://dx.doi.org/ 10.1016/j.ejor.2013.10.015. UNCTAD (2014). Review of maritime transport. In United Nations Conference on Trade and Development . Ursavas, E. (2014). A decision support system for quayside operations in a container terminal. Decision Support Systems, 59, 312–324. http://dx.doi.org/10.1016/j. dss.2014.01.003. Vacca, I., Salani, M., & Bierlaire, M. (2013). An exact algorithm for the integrated planning of berth allocation and quay crane assignment. Transportation Science, 47(2), 148–161. Voß, S., Stahlbock, R., & Steenken, D. (2004). Container terminal operation and operations research – A classification and literature review. OR Spectrum, 26(1), 3–49. http://dx.doi.org/10.1007/s00291-003-0157-z. Yang, C., Wang, X., & Li, Z. (2012). An optimization approach for coupling problem of berth allocation and quay crane assignment in container terminal. Computers & Industrial Engineering, 63(1), 243–253. http://dx.doi.org/10.1016/ j.cie.2012.03.004. Zhang, C., Zheng, L., Zhang, Z., Shi, L., & Armstrong, A. J. (2010). The allocation of berths and quay cranes by using a sub-gradient optimization technique. Computers & Industrial Engineering, 58(1), 40–50. http://dx.doi.org/10.1016/ j.cie.2009.08.002. Zhu, Y., & Lim, A. (2006). Crane scheduling with non-crossing constraint. The Journal of the Operational Research Society, 57(12), 1464–1471.

Please cite this article in press as: Karam, A., & Eltawil, A. B. Functional integration approach for the berth allocation, quay crane assignment and specific quay crane assignment problems. Computers & Industrial Engineering (2016), http://dx.doi.org/10.1016/j.cie.2016.04.006