A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem

A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem

Accepted Manuscript A Lagrangian Relaxation Approach for Solving the Integrated Quay Crane Assignment and Scheduling Problem Yi-Min Fu, Ali Diabat PII...

599KB Sizes 0 Downloads 7 Views

Accepted Manuscript A Lagrangian Relaxation Approach for Solving the Integrated Quay Crane Assignment and Scheduling Problem Yi-Min Fu, Ali Diabat PII: DOI: Reference:

S0307-904X(14)00349-7 http://dx.doi.org/10.1016/j.apm.2014.07.006 APM 10077

To appear in:

Appl. Math. Modelling

Received Date: Revised Date: Accepted Date:

25 October 2013 6 May 2014 8 July 2014

Please cite this article as: Y-M. Fu, A. Diabat, A Lagrangian Relaxation Approach for Solving the Integrated Quay Crane Assignment and Scheduling Problem, Appl. Math. Modelling (2014), doi: http://dx.doi.org/10.1016/j.apm. 2014.07.006

This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

A Lagrangian Relaxation Approach for Solving the Integrated Quay Crane Assignment and Scheduling Problem Yi-Min Fu, Ali Diabat* Department of Engineering Systems and Management Masdar Institute of Science and Technology, Abu Dhabi, UAE *Corresponding author’s email: [email protected] Abstract— Decisions on the quay crane assignment problem and the quay crane scheduling problem are typically made independently. However, the efficiency of container terminals can be increased when these decisions are made simultaneously due to the interrelation between quay crane assignment and scheduling.

A mathematical formulation for the integrated quay crane assignment and scheduling

problem (QCASP) is developed in this paper. Practical considerations are incorporated in the model, such as quay crane (QC) interference. A Lagrangian relaxation is proposed for the model. Feasible solutions are then obtained from the proposed heuristic. Computational results are provided for the proposed Lagrangian relaxation. Keywords: Quay crane assignment; quay crane scheduling; Lagrangian relaxation; Integrated models; integer programming. 1. Introduction Today’s global economic activities and industry globalization have led to a rapid increase in the exchange of products and materials between nations. Transport is an integral part of the entire supply chain; therefore, ports play an important role in the management of material. Ports are the sites connecting countries and provide the link between maritime and inland transport. Fig. 1 shows the sub-systems of sea port container terminals. These systems are the same for ports with different sizes, functions, and geometrical layouts. Starting from the lower part of Fig. 1, the relevant areas include the ship operation area, yard area, and the truck and train operation area, respectively. The ship operation area is used for loading and unloading vessels. The yard area, which may be divided into many blocks, is the place for storing inbound and outbound containers. Some of the block areas are reserved for containers with special requirements, such as those that may need electricity for cooling.

Figure 1: Operation areas of a seaport container terminal and flow of transports. [1] Fig. 2 illustrates the transportation and handling chain of containers. After arrival at a port, ships are moored, ready for unloading and loading containers. There are number of berths depending on the capacity of a port. The cost of constructing berths is very high; therefore, decisions that pertain to the number and length of berths are critical.

Figure 2: Chain of operations for containers. [1] After a vessel is moored in a berth, containers are discharged from the vessels by assigned quay cranes (QCs) according to a work schedule, and distributed to one of the storage blocks in the yard. A quay crane is a type of large dockside crane with a supporting framework. Quay cranes are located along the quay alongside a berthed vessel for unloading containers from and for loading to the vessel. The containers are then delivered by internal transportation to truck and train operation areas, which link the terminal to outside transportation. A container terminal contains three areas: quayside operations,

landside operations, and yard operations. Three issues of quayside operation planning need to be considered. The first is the assignment of quay space and service time to vessels, which is usually referred to as the berth allocation problem (BAP). Quay cranes transship containers between a vessel and the quay. The quay crane assignment problem (QCAP) deals with the assignment of these quay cranes to vessels. The quay crane scheduling problem (QCSP) determines work plans for the cranes. Research has produced various models for seaside operation planning in container terminals. Typically, decisions on quayside operations are made sequentially. However, the interrelations between them are ignored in sequential planning operations. Therefore, several integration approaches for quayside operations planning have been developed to make better decisions. Furthermore, quayside operations also interact with the yard operations. Decisions have to be made on the type of transport equipment used to transport containers and the route between quayside and landside. The activities of receiving and delivering inbound and outbound containers to and from the storage yard are addressed in landside operations. In order to meet the increasing demand of container transportation, terminals have to be highly productive. Current research aims to address seaside operation problems to achieve an effective and efficient functioning of the container terminal. The cost of constructing a berth and the cost of quay cranes is very high compared to the investment cost for other facilities in the terminal; therefore, the berth and quay cranes are the most critical resources for determining the capacity of a container terminal. An effective utilization of quay cranes leads to the reliable and fast service processing of vessels. This paper presents a model for the integrated quay crane assignment and scheduling problem (QCASP). The objective is to maximize the efficiency of container terminals by optimizing the quay cranes utilization. The paper is organized as follows. The relevant literature is reviewed in Section 2. A description for the model formulation is presented in Section 3. Section 4 explains the solution method. Section 5 presents an experimental analysis of the model. Finally, the results and recommendations for future research are summarized in Section 6. 2. Literature Review Many studies on seaside operations for container terminals can be found in the literature. The model presented considers different scenarios in reality. These include different arrival types of ships, different quay layouts, and various factors affecting handling time, which are considered in the BAP. Assignment of quay cranes is usually affected by the BAP. Different ways to categorize tasks in the QCSP are used in

different models. The interrelationship between these three problems is significant. Therefore, integrated models are introduced to address the correlation. In the BAP, the layout of the berth and the number of vessels to be served are known. Other information is also provided, such as the length of the vessels, expected time of arrival, and the handling time. The BAP aims to find where and when the vessels are served to utilize the berth efficiently and effectively. The BAP is usually categorized in different ways. Imai et al. [2] present a static berth allocation formulation and then extend it to the dynamic berth allocation model. Imai et al. [3] and Imai et al. [4] consider a discrete quay layout with the objective of minimizing the total handling time and waiting time. Continuous quay layout is considered in Park and Kim [5], Meisel and Bierwirth [6], Li et al. [7], and Guan et al. [8]. Handling time for ships can be static or dynamic. Li et al. [7] and Guan et al. [8] apply fixed handling time in the static continuous BAP. Handling time can be determined by berthing positions of vessels, number of quay cranes assigned, and the work schedule of assigned quay cranes. Imai et al. [2], Imai et al. [3], and Imai et al. [4] propose a model with dynamic handling time which depends on the berthing location. Park and Kim [5] and Meisel and Bierwirth [6] consider the number of quay cranes assigned to vessels during the planning of berth allocation. Handling time is shown in QC-hours; hence, with more quay cranes available, less time is required. Meisel and Bierwirth [6] further consider the interference between quay cranes. In the QCAP, the decision of quay cranes to vessels assignment is made. For the BAP with dynamic handling time depending on the number of assigned cranes, the QCAP is usually taken into account at the berth planning level. The model presented by Park and Kim [5] has two phases. The berthing position and time and number of quay cranes are decided in the first phase. The assignment of quay cranes to vessels is determined in the second phase to minimize the number of times quay cranes are transferred between vessels. In the QCSP, we consider the transshipment of containers between vessels and quay cranes. The tasks and the number of quay cranes are given. The solution is the schedule of containers being processed. The QCSP decides the sequence of containers assigned to a specific quay crane. The first study of QC scheduling, proposed by Daganzo [9], determines the number of QCs assigned to ship-bays of multiple vessels. A single bay is considered a task. Lee et al. [10] study a quay crane sequence problem, which considers loading and unloading operations in a bay as a task. Liu et al. [11] present a mixed integer linear programming model for the QCSP, in which a bay is also considered a task. Choo et al. [12] study the crane sequencing problem, considering multi-ship problems where the ships are linked by yard congestion constraints. The models presented by D.H. Jung et al. [13], Kim and Park [14], and Bierwirth and Meisel [15] deal with the quay crane sequence problem based on container groups. F. Meisel [16]

proposes a new approach for the QCSP. Time windows, which are given by terminal operators, restrict the availability of cranes at a vessel. The decisions on seaside operation are interrelated and have been addressed recently through integrated models. Park and Kim [5] are the first to integrate berth allocation and crane scheduling problems through a two-phase process. Meisel and Bierwirth [6] further extend the model by taking terminals’ productivity into account. Tavakkoli-Moghaddam et al. [17] extend the model proposed by Kim and Park [14] for a set of vessels in parallel. Diabat and Theodorou [18] introduce a novel formulation for the integrated assignment and scheduling problem, according to which they essentially transform it into a bay assignment problem and solve it using a GA. This paper formulates a mixed integer programming (MIP) model for the quay crane scheduling and assignment problem. A dynamic planning horizon is proposed. 3. Methodology 3.1 Problem Description In this section we provide a problem description for the QCASP. Then, a mathematical model for the QCASP is presented. 3.1 Problem Description The objective of the QCSP is to minimize the makespan for each vessel by determining the sequence of loading/unloading operations. Table 1 is an example of a load profile for 2 vessels with 3 and 4 bays. Fig. 3 shows a solution of a QCSP example with 3 cranes. QC assignment is determined in a previous phase. One and two cranes are assigned to vessel 1 and vessel 2, respectively. As shown in the figure, the total handling time can be improved if QC 2 is moved to vessel 1 during the operation. Fig. 4 gives an optimal solution for this example. Table 1. An example of a load profile

Figure 3. A solution for the example

Figure 4. An optimal solution for the example Fig. 4 shows that QCs are utilized more efficiently when the QCAP and QCSP are considered simultaneously. QCs can be moved from one vessel to another when necessary. The model presented in this paper determines the assignment of quay cranes to each vessel and the schedule for each crane. For the integrated QCASP, the berthing time and location of each vessel are given. The container terminal operator receives information about the load profile of each vessel. The goal is to determine the assignment of QCs as well as the sequence of loading and unloading operations within a planning horizon so that the makespan is minimized. Fig. 5 illustrates a planning horizon, in which the work completion flag is introduced. The work completion flag is set to 1 after the needed operation time of the vessel is achieved. The objective is to minimize the makespan of container terminals. Therefore, this model aims to maximize the work completion flags during a given planning horizon.

Figure 5. An example of a planning horizon 3.2 Formulation The notation used to formulate the problem is shown below: Sets:



≜    ,   



≜   ,   



≜     ,   .    , ℎ ℎ    !      !ℎ.

"

≜     ! ,   

Parameters:

# ≜       





 !

$#

≜          . % :  −   ! .



≜   $     

Decision Variables: #() = +1.        !            0 ℎ 

#)

= +1.        

 ℎ       0 ℎ 

)

= +1.     

 ℎ       0 ℎ 

The following is the IP formulation of this model. 4

1

/ 0 0  )

(1)

23 )23

subject to 4

56

0 0 #() ≤ 1

23 #23

:

0 #() ≤ 1

(23

4

56

23 #23 (23

56

4

∀ ∈ , ∀ ∈  , ∀ ∈ "

(3)

∀ ∈ "

(4)

∀ ∈ , ∀ ∈ "

(5)

∀ ∈ , ∀ ∈ 

(6)

∀ ∈ , ∀ ∈  , ∀ ∈ "

(7)

∀ ∈ , ∀ ∈  , ∀ ∈ "

(8)

56

0 0 # ∙ #,(<3,) − 0 0 # ∙ #() ≥ 

23 #23

:

(2)

:

0 0 0 #() ≤ 

4

∀ ∈ , ∀ ∈ "

23 #23

1

0 0 #() = $#

(23 )23

) ∑:@ (23 ∑?23 #(?

$#

#) ≥ )

#() , ) ∈ {0, 1}

≥ #)

∀ ∈ , ∀ ∈  , ∀ ∈ , ∀ ∈ "

(9)

The objective function (1) aims to maximize the sum of weighted work completion flags. Constraints (2) and (3), respectively, ensure that a QC can only be positioned at a single bay at any time period and that only one QC can be positioned at a bay at any time. Constraint (4) ensures that the total QC serving vessels does not exceed the total number of available QCs at any time. Constraint (5) enforces the QC clearance conditions, stating that if a QC is positioned at a bay, the next QC has to be positioned at least m bays away. Furthermore, constraint (5) also implies that QCs have to be positioned in increasing order from left to right, which is the QC ordering condition. Constraint (6) ensures that all the container assignment needs are completed within the planning horizon. The sum of total time segments of cranes working on a bay must satisfy the workload. Constraint (7) defines the work completion flag for each bay. #) is set to 1 after all containers in bay j of vessel k is completed. Constraint (8) ensures that a vessel is

finished after every bay in the vessel is completed. Constraint (9) makes sure that variables ,  and  are all binary. 4. Solution Method 4.1 Lagrangian Relaxation For large scale optimization problems, an alternative way to obtain optimal or near optimal solutions efficiently is to solve the relaxed problems. There are three ways to relax a problem. The first method is the linear programming relaxation, which ignores integer restrictions. Secondly, constraint relaxation simply eliminates some constraints altogether. The last one is Lagrangian relaxation, which moves some constraints to the objective function and penalizes them using Lagrangian multipliers. The solution from a relaxed problem is better than the solution from the original problem. Hence, for minimization problems, the relaxed problem gives a lower bound and an upper bound can be found through heuristics. The optimal solution is between the lower bound and upper bound. On the other hand, maximization problems get an upper bound from a relaxed problem and a lower bound from heuristics [19].

Figure 6. The coefficient matrix for the constraints Figure 6 shows the coefficient matrix for the constraints. In the proposed Lagrangian relaxation, we relax constraints (2), (3), and (4) to simplify the problem. Meanwhile, we also ensure that the solutions are not too far from the feasible ones. μDE , πGHE , ρE are the Lagrangian multipliers for constraints (2), (3), and (4), respectively. The Lagrangian relaxed problem is shown below. Lagrangian Relaxed Problem / 0 0  ) + 0 0 K() (1 − 0 0 #() ) + 0 0 0 N#) (1 − 0 #() ) 

)

(

)



#

+ 0 O) ( − 0 0 0 #() ) )



#

(

Subject to constraints (5) through (9) and K() , N#) , O) ≥ 0



#

)

(

Sub-problem / − 0 0 0 0 K() #() − 0 0 0 0 N#) #() − 0 0 0 0 O) #() + 0 0  ) 

#

(

)



#

(

)



#

(

)



)

Subject to constraints (5) through (9) and K() , N#) , O) ≥ 0 Lagrangian Dual Problem / 0 0 K() + 0 0 0 N#) +  0 O) + PQR (

)



#

)

)

PQR = / − ∑ ∑# ∑( ∑) K() #() − ∑ ∑# ∑( ∑) N#) #() − ∑ ∑# ∑( ∑) O) #() +

Where ∑ ∑)  )

Subject to constraints (5) through (9) and K() , N#) , O) ≥ 0 Lagrangian Master Problem / 0 0 K() + 0 0 0 N#) +  0 O) + S (

)



#

)

)

Subject to

S ≥ − 0 0 0 0 K() #() ? − 0 0 0 0 N#) #() ? 

#

(

)



#

(

)

∀ℎ

− 0 0 0 0 O) #() + 0 0  ) ?



#

(

)



)

The following provides the overall procedure for the cutting plan optimization procedure: Step 1. Use any values of K() , N#) , O) ≥ 0. Step 2. Use the Lagrangian multipliers to solve the sub-problem and to update the best solution (an upper bound

for

maximization)

ZLagrangian=min(ZLagrangian, ZUB)

for

the

sub-problem.

Update

the

minimum

upper

bound

by

Step 3. After solving the sub-problem, we get an optimal solution vector  ? for the sub-problem,

where ℎ ∈ T. Add one more cut to the master problem using the solution from the sub-problem at each iteration. T is the vector set of feasible solutions for the sub-problem. Step 4. Solve the new master problem and update the best solution (a lower bound) for the master problem. Lagrangian relaxation generates an upper bound for the problem. A lower bound can be found through a genetic algorithm (GA). By comparing the upper bound and lower bound, we can evaluate the performance of the proposed Lagrangian relaxation. 5. Computational results In this section, the performance of the proposed model and developed Lagrangian relaxation are tested by different size instances. The smaller problems are also solved optimally by GAMS. The GA is used to find a lower bound for every instance. Table 2 shows the experiment results. The upper bound is the Lagrangian bound from the proposed Lagrangian relaxation and the lower bound is from the GA. Fig. 7 shows the execution time and the gap between Lagrangian relaxation and GAMS as well as the gap between the upper bound and lower bound for the problems. As can be seen from the table and the figure, the execution time increases as the size of the instances grows. Lagrangian relaxation performs better than GAMS in terms of time. For larger problems, GAMS is not able to obtain optimal solutions. However, the Lagrangian relaxation and the GA provide an upper bound and a lower bound for every problem. This information helps to evaluate the effectiveness of the generated solution. For large sized problems, obtaining an optimal solution is infeasible or very time consuming. A near optimal solution can be generated relatively fast using GA, and then it can be compared to the upper bound from the proposed Lagrangian relaxation to verify its performance. These two solution methods provide a faster way to obtain a near optimal solution for the integrated QCASP.

Table 2. The experiment results

Figure 7. The comparison of each instance

6. Conclusion In this paper, a mathematical formulation is presented for the integrated Quay Crane Assignment and Scheduling Problem (QCASP) in port container terminals. The increased complexity of the resulting model, occurring due to the integration of two already complicated formulations, creates the need for an approach that simplifies the problem. Therefore, Lagrangian relaxation is implemented, allowing for the decomposition of the problem. Several problem instances are tested in order to verify the performance of

the proposed approach. The results are then compared to those obtained by the commercial software GAMS and to another heuristic, namely a Genetic Algorithm (GA).

Results demonstrate the superiority of the proposed Lagrangian relaxation approach, in terms of computational time, when compared to the commercial software. Furthermore, for large problem sizes, the commercial software fails to reach an optimal solution, while on the other hand both the Lagrangian relaxation and the GA provide an upper bound and lower bound for every tested problem. This underlines the importance of implementing heuristics for large sizes of the problem, in order to reach a good solution within reasonable time. Due to this advantage, the proposed method is recommended for use by container terminal operators, as it reaches highly satisfactory solutions within very good times, ensuring high performance of the container terminal.

Future work can focus on incorporating further realistic assumptions to the formulation, such as the traveling time of cranes between bays, which becomes critical when considering other physical constraints, such as the safety margins or the QC ordering. In addition, a more complete terminal operation planning approach can be achieved by integrating the berth allocation problem (BAP) into scenarios of this problem. References [1]

S. Voß, R. Stahlbock, and D. Steenken, “Container terminal operation and operations research - a classification and literature review,” OR Spectr., vol. 26, no. 1, pp. 3–49, Jan. 2004.

[2]

A. Imai, E. Nishimura, and S. Papadimitriou, “The dynamic berth allocation problem for a container port,” vol. 35, 2001.

[3]

A. Imai, H. C. Chen, E. Nishimura, and S. Papadimitriou, “The simultaneous berth and quay crane allocation problem,” Transp. Res. Part E Logist. Transp. Rev., vol. 44, no. 5, pp. 900–920, Sep. 2008.

[4]

A. Imai, E. Nishimura, and S. Papadimitriou, “Berthing ships at a multi-user container terminal with a limited quay capacity,” Transp. Res. Part E Logist. Transp. Rev., vol. 44, no. 1, pp. 136– 151, Jan. 2008.

[5]

Y. Park and K. H. Kim, “A scheduling method for Berth and Quay cranes *,” 2003.

[6]

F. Meisel and C. Bierwirth, “Heuristics for the integration of crane productivity in the berth allocation problem,” Transp. Res. Part E Logist. Transp. Rev., vol. 45, no. 1, pp. 196–209, Jan. 2009.

[7]

Li, Chung-Lun, X. Cai, and C. Lee, “Scheduling with multiple-job-on-one-processor pattern,” IIE Trans., vol. 30, no. 5, pp. 433–445, 1998.

[8]

Y. Guan, W.-Q. Xiao, R. K. Cheung, and C.-L. Li, “A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis,” Oper. Res. Lett., vol. 30, no. 5, pp. 343–350, Oct. 2002.

[9]

C. F. Daganzo, “The Crane Scheduling Problem,” Transp. Res. Part B Methodol., vol. vol. 23, no. 3, pp. 159–175, 1989.

[10]

D. Lee and J. X. Cao, “Integrated Quay Crane and Yard Truck Schedule for Inbound Containers,” pp. 1219–1223, 2008.

[11]

J. Liu, Y. Wan, and L. Wang, “Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures,” Nav. Res. Logist., vol. 53, no. 1, pp. 60–74, Feb. 2006.

[12]

S. Choo, D. Klabjan, and D. Simchi-Levi, “Multiship Crane Sequencing with Yard Congestion Constraints,” Transp. Sci., vol. 44, no. 1, pp. 98–115, Dec. 2009.

[13]

Y. Park, B. Lee, K. Kim, and K. Ryu, “A quay crane scheduling method considering interference of yard cranes in container terminals,” MICAI 2006 Adv. Artif. …, vol. 4293, pp. 461–471, 2006.

[14]

K. H. Kim and Y.-M. Park, “A crane scheduling method for port container terminals,” Eur. J. Oper. Res., vol. 156, no. 3, pp. 752–768, Aug. 2004.

[15]

C. Bierwirth and F. Meisel, “A fast heuristic for quay crane scheduling with interference constraints,” J. Sched., vol. 2009, no. 12, pp. 345–360, 2009.

[16] F. Meisel, “The quay crane scheduling problem with time windows,” Nav. Res. Logist., vol. 53, no. 1, pp. 45–59, 2011. [17]

R. Tavakkoli-Moghaddam, a. Makui, S. Salahi, M. Bazzazi, and F. Taheri, “An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports,” Comput. Ind. Eng., vol. 56, no. 1, pp. 241–248, Feb. 2009.

[18]

A. Diabat and E. Theodorou, “An Integrated Quay Crane Assignment and Scheduling Problem,” Comput. Ind. Eng., DOI: 10.1016/j.cie.2013.12.012..

[19]

M. L. Fisher, “An Applications Oriented Guide to Lagrangian Relaxation,” INFORMS J. Pract. Oper. Res., vol. 15, no. 2, pp. 10–21, 1985.

Table 1

Task (QCtime) vessel 1 vessel 2

bay 1 3 4

bay 2 4 4

bay 3 5 8

bay 4 2

Table 2

GAP (%) No.

No. Vessels

Ship Bays

No. QC

1 2 3 4 5 6 7

2 3 3 4 4 5 5

[4, 6] [4, 6, 5] [5, 7, 7] [4, 7, 5, 7] [5, 7, 7, 6] [5, 7, 7, 6, 5] [7, 6, 5, 7, 9]

3 5 6 7 8 8 10

No. Jobs QC hours 27 45 78 86 104 128 227

8

6

10

9

8

12

[10, 11, 15, 13, 16, 11] [17, 12, 16, 20, 13, 25, 30, 10]

Time (s)

LR & GAMS

LB & UB

GAMS

LR

22.69 16.06 17.63 20.79 19.63 18.73 20.35

22.69 16.9 22.1 24.61 24.55 23.24 24.91

0.47 6.49 39.77 62.74 104.47 594.79 994.41

1.06 2.57 6.03 6.82 7.26 17.92 33.7

450

-

20.97

-

40.04

900

-

22.28

-

124.1