Optimization of Quay Crane Dynamic Scheduling Based on Berth Schedules in Container Terminal

Optimization of Quay Crane Dynamic Scheduling Based on Berth Schedules in Container Terminal

JOURNAL OF TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION TECHNOLOGY Volume 11, Issue 3, June 2011 Online English edition of the Chinese language ...

323KB Sizes 0 Downloads 30 Views

JOURNAL OF TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION TECHNOLOGY Volume 11, Issue 3, June 2011 Online English edition of the Chinese language journal RESEARCH PAPER

Cite this article as: J Transpn Sys Eng & IT, 2011, 11(3), 58í64.

Optimization of Quay Crane Dynamic Scheduling Based on Berth Schedules in Container Terminal JIN Zhihong, LI Na* Transportation Management College, Dalian Maritime University, Dalian 116026, Liaoning, China

Abstract: The quay crane dynamic scheduling problem based on berth schedules in container terminal involves the allocation of limited quay crane resources and the scheduling of loading and unloading tasks on each ship, with its berth time and location known, in order to reduce the total time of all the ships arriving at the terminal in the planning horizon. Under the real constraints of non-crossing of quay cranes and the sequence requires among tasks, the non-linear mathematical planning model is set up. A genetic algorithm is proposed according to the characteristics of the problem, and the chromosome representation is structured on the sequence of tasks. The model and the algorithm are proved effectiveness via the comparisons of scheduling results with results with literature on a single ship, the comparisons of scheduling results between multi-ships and single ship, and the simulation of quay crane dynamic scheduling among multi-ships. Key Words:

system engineering; waterway transportation; quay crane allocation; dynamic scheduling; non-linear planning;

genetic algorithm

1

Introduction

The turnaround time for container ships at ports is determined by the loading and unloading plan of quay cranes (QCs), besides the plan of berth allocation. The loading and unloading of quay cranes comprises two segments, namely, the quay crane assignment problem (QCAP) and the quay crane scheduling problem (QCSP). The QCAP involves the assigning of QCs to vessels. And the QCSP involves determining the work plan of each QC among the tasks of the vessel. As shown in Fig. 1, the location of a container in a vessel is

defined by the bay, stack and tier together. The bay is the order of cross sections in the longitudinal section (Fig.1a). The odd number represents a 20-ft container. And the even number represents a 40-ft container. As in Fig.1b, the stack stands for the order of rows in the cross section, and the tier defines the height. Tasks to be scheduled can be defined in different ways, including bay areas or single bays (Fig.1a) and container groups, container stacks or individual containers (Fig.1b). In this paper, tasks are defined on container groups, which are located in adjacent slots of the same bay. Grouped containers usually have a common destination.

(a) The longitudinal view of a ship (b) The cross-sectional view of a bay Fig. 1 Storage location structure of a vessel

Received date: Apr 11, 2011; Revised date: Apr 22, 2011; Accepted date: May 3, 2011 *Corresponding author. E-mail: [email protected] Copyright © 2011, China Association for Science and Technology. Electronic version published by Elsevier Limited. All rights reserved. DOI: 10.1016/S1570-6672(10)60123-7

JIN Zhihong et al. / J Transpn Sys Eng & IT, 2011, 11(3), 58í64

The research of QCSP in a single ship is studied widely. Zhang and Kim[1] studied the QCSP in a ship bay by one quay crane through an optimal container stack sequencing. The aim is to minimize the number of operation cycles for a quay crane. Meisel and Wichmann[2] studied QCSP based on single containers. Meisel and Bierwirth[3] presented benchmark instances for QCSP of single ships. Besides, the scheduling of QCs was frequently combined with other resources at ports in some research studies. Han et al.[4] studied the coordinated optimization of discrete berth allocation and QC scheduling. Ji & Jin[5] designed optimal routes for yard trailers with the aim of minimizing the working time of QCs. As to QCSP of multiple ships, Tavakkoli-Moghaddam et al.[6] set up a mixed integer planning model and proposed a genetic algorithm. However, the starting of the planning horizon happens when a vessel arrives or leaves the port. The quay crane assignment and scheduling were static indeed. The problem of dynamic QC assignment and scheduling of multiple ships still needs effective research. In this paper, dynamic QC scheduling of multiple ships can be explained as follows. In the planning horizon, the berth time and location for each arriving ship are already known in advance. The problem involves optimally allocating the limited quay cranes to these ships and then scheduling quay cranes on all tasks on each ship.

2

Assumption and notation

Considering the characteristics of the problem and real constraints, the assumptions are as follows: (1) The quay is continuous. For convenience, quay is divided into 1-meter segments and time is divided into 1-minute period segments. They constitute two dimensional axes, with quay as the horizontal axis and time as the vertical axis. (2) The estimated berth time and location for each ship are known. (3) Tasks are defined on container groups. Some of them have precedence relationships or cannot be performed simultaneously. (4) The QCs are located on the same track and marked with ^1,2,3ˈ` from left to right on the axis; the safe space for two adjacent quay cranes is one bay. (5) The horizontal moving time of quay crane is the divisor of moving distance and horizontal average velocity. 2.1 Sets and indices V is the set of vessels to be scheduled, with i1 & i2 representing different ships. V denotes the total number of vessels. Q is the set of quay cranes, the total number of which is Q . And k1 , k2 and k c represent different quay cranes on the same track. T is the set of time in the planning horizon.

:i is the set of all loading and unloading tasks on ship i , and n1 , n2 and nc represent different tasks. ) i is the set of ordered pairs of tasks with a precedence relationship on ship i .
3

Mathematical model

3.1 State variables of QCs Once QC k finishes serving the task n on ship i , the location and free time of the crane must be updated. That is, if n X ijk 1 the state of the crane at period T is decided by the following equations: lkT

n X ijk ˜ lin

(1)

ckT

n X ijk ˜ EBin

(2)

For the reason of non-crossing constraints, some unassigned cranes have to move passively. As in Fig. 2, if QC3 is assigned to serve the task n , QC4 and QC5 have to move to the right

JIN Zhihong et al. / J Transpn Sys Eng & IT, 2011, 11(3), 58í64

lkTc

side in order to give space for QC3. QC4 and QC5 are the passively moved cranes. In general, the location and free time of passively moved crane k c at period T are expressed as Eqs. (3) and (4).

ckTc

>

n X ijk ˜ lin  (k c  k ) ˜ 'l

§ lin  ( k c  k ) ˜ 'l  l kTc1 n ¨ T 1 X ijk ˜ ¨ ck c  v ¨ ©

QC3

QC5

QC4

(3)

· ¸ ¸¸ ¹

(4)

n

n

QC1 QC2

@

QC1

QC2

QC5

QC3 QC4

Fig. 2 Illustration of passively moved QCs

i  V , k  Q ˈn  :i

The total moving time t kn of all the cranes is as given in equation (5), which dismisses the saved time if multiple cranes can move simultaneously.

lin  l kT 1  ¦ lin  (k c  k ) ˜ 'l  l kTc1 kc

n X ijk ˜

t kn

(5)

v 3.2 Non-linear mathematical model According to the characteristic of the problem, the following non-linear mathematical model is set up. Minimize Z ¦ ( EBi  SBi ) (6) i

Subject to SBi min j ˜ Yijk Yijk

^

`

1 ˈ

i  V , k  Q ˈ j  T EBi

max n

¦¦Y

ijk

i k rimin d

¦X

(7)

^ `ˈ i  V EBin

(8)

d Q ˈj  T

¦Y

ijk

(9)

d rimax ˈi  V ˈ j

SBi

(10)

k

n ijk

Yijk ˈ i  V ˈ k  Q ˈ j  T

(11)

n

¦¦ X k

min ˈi  V ˈn  :i

n ijk

j

^

(12)

`

SBin

n max (tkn  ckT ) ˜ X ijk , SBi ˈ i  V ˈ

SBin

min

k  Q ˈj  T ˈn  :i



Z in1n 2



EBin

Z in 2 n1

ˈ i  V ˈ n  :i

(14)

=1ˈi  V ˈ(n1 , n2 ) 
(15)

EBin1  SBin2 d 0 ˈ i  V ˈ (n1 , n2 )  ) i EBin1



SBin2

d M (1 

n1 X ijk

˜

n2 X ijk

˜ Z in1n2

 lkT1 ) ˜ (bi2

(lkT2

 lkT1 ) ˜ (lin2

(17)

 bi1 ) ˜ Yi1 jk1 ˜ Yi 2 jk 2 t 0 ˈ

i1 , i2  V ˈj  T ˈk1 , k2  Q  lin1 ) ˜

n1 X ijk 1

˜

n2 X ijk 2

(18)

t0ˈ

i  V ˈn1 , n2  :i ˈk1 , k2  Q ˈj  T n X ijk , Yijk , Z in1n2

(16)



i  V , n1 , n2  :i ˈj  T ˈk  Q (lkT2

(19)

 ^0,1` , i, i1 , i2  V  V c ,

j  T , k  Q , n  :i

ri , lin

(13)

t 0 and are integers,

(20)

SBi , EBi , SBin , EBin , tkn

(21)

t0ˈ

i V , k  Q ˈn  :i

(22)

The objective function (6) minimizes the total turnaround time of all the vessels. Constraints (7) and (8) define the ships’ starting and completion serving times, respectively. Constraint (9) reflects the number of QCs in use at any time; it cannot exceed the total number of available QCs. Constraint (10) guarantees that only when the number of available QCs achieve [rimin , rimax ] can ship i be served. Constraint (11) restricts that one QC can serve only one task at one time. Constraint (12) ensures that every task on every ship is assigned to a crane, the working time of which satisfies the capacity demand of the task. Constraints (13) and (14), respectively, determine the tasks’ starting and completion serving times. The pairs of tasks’ precedence relationships and non-simultaneous constraints in a ship are reflected in constraints (15) and (16), respectively. When the two tasks on the same ship are served by a common crane, the relationship between their working times is defined by Constraint (17). By constraints (18) and (19), the interference among QCs both between ships and between tasks in a ship can be avoided. Formulas (20)–(22) are the definitions of decision variables.

4

Solution procedure

The proposed genetic algorithm for dynamic QC scheduling among multiple ships is as follows. 4.1 Chromosome representation and initial solution procedure Construct a two-dimensional matrix with ( V u A) genes. V denotes the number of vessels. A is the biggest number of tasks of all the vessels. As in Fig. 3, each vertical row belongs to one ship. The figure in a row denotes the serial number of a task, which is selected randomly for generation. The permutation is the order in which tasks must to be allocated. If the task number of a ship is less than A , rest of the genes are filled by 0 . 4.2 QC allocation and scheduling The procedure of the solution is depicted in Fig. 4.

JIN Zhihong et al. / J Transpn Sys Eng & IT, 2011, 11(3), 58í64

According to the permutation of tasks in the initial solution, each task on each ship is assigned to a QC at a proper time. When more than one QC are available, the selection criteria are first the free time and then the distance between the QC and the task.

locations with the uncrossed genes that remain in parent 2 with the same sequence. The rest genes are filled with 0 . Based on a certain mutation probability, a chromosome at current population is selected randomly. All the columns of the chromosome must be mutated. Choose two tasks of each vessel randomly and swap their position. The Roulette wheel sampling is used for selecting an operator. At each generation, whenever a better solution is found it is recorded in a mnemon. The aim of the mathematical model is minimization. So the fitness function is switched as formula (25): 1

f ( x)

(25)

(1  exp( Z ( x ) 1000))

Fig. 3 Illustration of chromosome representation

To avoid inference between QCs, the starting time of the task should be later than other tasks being served between the QC and the task, besides considering the horizontal moving time of QCs. Assuming that task n is assigned to QC k and task nc , which has already been assigned to QC k c located between task n and QC k , QC k can move to task n only after the completion of task nc . That is, if

SBin  EBinc  Let

SBin

EBinc 

2 lin

 linc

 2'l

v 2 lin

 linc

i

ri min

rimin, rimax

(23)

i

 2 'l

(24) v The state of both the serving QC and passively moved QCs must be updated. When the passively moved QCs cannot move to the proper location, the solution is treated as unfeasible and the fitness function of the chromosome is set to 0. By assigning the tasks to QCs, the precedence and non-simultaneity constraints must be satisfied. Suppose that task n2 is to be assigned; then, check all the other tasks on ship i , e.g., n1 . While (n1 , n2 )  ) i , if task n1 has been assigned let SBin2 EBin1 ; if not, switch the gene locations of task n1 and task n2 in the chromosome. While (n1 , n2 ) 
SBi

i i

i 1

n

n

n  1

Fig. 4 Procedure of quay crane allocation and scheduling

5

Numerical experiments

To prove the effectiveness of the aforementioned model and algorithm, three experiments are conducted, including comparisons of QC scheduling results of single ships with results mentioned in the literature, comparisons of multiple ships’ QC scheduling and individual ship’s QC scheduling, and finally simulation of dynamic QC scheduling among multiple ships. 5.1 Comparisons of QC scheduling results of single ships with results in the literature There is little research about dynamic QC scheduling among multiple ships at present in our search scope. To verify

JIN Zhihong et al. / J Transpn Sys Eng & IT, 2011, 11(3), 58í64

Table 1 Comparison of the results of QC scheduling of single ships with those in Ref. [3] Handling rate

20%

50%

80%

Distribution

cl1

cl 2

uni

uni

cl1

cl 2

uni

1

321

330

326

777

1256

1249

1240

2

322

336

323

782

1241

1239

1239

3

320

325

326

783

1260

1249

1245

4

319

322

328

780

1231

1245

1247

5

313

324

317

779

1236

1238

1259

Average

319

327

324

780

1245

1244

1246

Improved

32.8%

11.0%

7.3%

–1.2%

–2.6%

–2.9%

-3.1%

Table 2 Comparison of results between multiple ships and single ship Handling rate Distribution

20% cl1

cl2

50%

uni

uni

80% cl1

cl2

uni

Multi-ships scheduling

396

434

408

982

1,562

1,540

1,583

Decreased

24.1%

32.7%

25.9%

25.9%

25.5%

23.8%

27.0%

the effectiveness of the proposed model and algorithm, they are used to solve the QC scheduling of individual ships. The results are compared with those reached by Meisel and Bierwirth[3]. Suppose the number of bays is 15 and the number of tasks is 50. The capacity per bay is 400 containers. The handling rates are 20%, 50% and 80%. Each ship is assigned to 4 QCs. The three spatial distributions of tasks on each vessel are uniform distribution, normal distribution, and double normal distribution. They are denoted as uni , cl1 and cl 2 , respectively. According to the three distributions of tasks, 35 instances are generated by the program QCSPgen of Meisel and Bierwirth[3]. In Ref. [3], the moving time of QC through one bay is set to 1. For comparison, supposing the length of each bay is 7 meters the horizontal velocity of QC is 7 m/min. The number of vessels is set to 1. To solve the 35 instances by the model and algorithm proposed in this paper, the results of which are listed in Table 1 (unit: minute). Compared with the scheduling results of Meisel and Bierwirth[3], the average time of optimal solutions for single ships is decreased by 15.5% when the handling rate is 20%. When the handling rate is 50%, the average time of optimal solutions is increased by 1.2%. When the handling rate is 80%, the average time is increased by 2.9%. The algorithm proposed in this paper has excellent adaptability in the low handling rate QC scheduling problem. As the handling rate increases, the adaptability weakens slightly. 5.2 Comparisons of QC scheduling results between multiple ships and single ships Suppose the aforementioned 35 vessels are the total number of ships arriving in the planning horizon. Further, there are 15 available QCs, which are initially located along the 1000-meters quay uniformly from the left side to the right side. Based on a feasible berth plan, the QCs are scheduled dynamically to the 35 vessels. As shown by the results in Table 2 (unit: min), when the ships are scheduled together the

results are worse than those when ships are schedued separately. The average time of QC scheduling in multiple ships are extended by 26.4%. Thus the working efficiency of QCs is lowered obviously, by the disturbance of other vessels and non-working QCs. The optimization QC scheduling of single ships can hardly be realized in the complicated multiple ships’s case, which reflects the importance of performing more research on the QC scheduling of multiple ships. 5.3 The simulation of multiple ships’ dynamic QC scheduling As there is no literature on dynamic QC scheduling of multiple ships available for comparison, the following simulated instances are designed. The parameters of terminal quay and QCs are the same as those aforementioned. The planning horizon is one week. Three sets of instances, which, respectively, have 64, 45 and 34 vessels arriving, are generated. Within each instance, the vessel sets consist of three kinds of ships. 60% of ships belong to Feeder and 30% of ships belong to Medium, whereas 10% of ships belong to Jumbo. For each type of ships, the number of bays distribute uniformly between [10, 15], [12, 18] and [15, 20], respectively. The allowable minimum and maximum numbers of simultaneously working quay cranes for each vessel type are [1, 2], [2, 4] and [4, 6]. In each instance, the following parameters are assumed. Each of the three space distributions of tasks takes up 1/3 of the whole vessel set. The capacities of ship bays distribute normally between [100, 300]. The handling rates of bays distribute normally between [20%, 50%]. The densities of precedence relations of pairs of tasks distribute normally between [0%, 30%]. The densities of non-simultaneity of pairs of tasks take up 0% or 5% in half. Input the aforementioned parameters in the program QCSPgen. The QC capacity demand (QC-minutes) and the located bay of each task of each vessels are generated.

JIN Zhihong et al. / J Transpn Sys Eng & IT, 2011, 11(3), 58í64

Optimal time of each generation (h)

Input the three instances to the proposed VB program on a computer of 2.53 GHz double cores. Based on a feasible berth plan, the approximate optimal solutions are found within the acceptable time. The optimal objectives are 548.62 h, 360.93 h and 241.88 h, whose convergences of the evolutions are depicted in Fig. 5. All the three instances’ objectives are improved through the evolutions. As the arriving vessels’ number is 64 in the planning horizon, the improvement through evolution is the most remarkable one. The objective is decreased by 19%.

Further research will deal with the combined dynamic scheduling of berth and QC, as well as the exploitation of decision support systems for QC scheduling.

Acknowledgements This research was funded by the Research Fund for the Doctoral Program of Higher Education (No. 20070151002), Liaoning Provincial Natural Science Foundation (N0. 20082141), and Liaoning Provincial Research Program of Higher Education (No. 2008S028).

References

730 680 630 580 530

|V |=64

480 430 380 330 280

[1]

operations of quay cranes in container terminals. Computers & Industrial Engineering Intelligent Manufacturing and Logistics. 2009, 56(3): 979–992.

|V |=45

[2]

|V |=34 10

Fig. 5

6

19

28

37

46 55 Generation

64

73

82

91

100

[3] Meisel F, Bierwirth C. A unified approach for the evaluation of quay crane scheduling models and algorithms. Computers &

Results of convergence of the algorithm

Conclusions

In the planning horizon, there are many vessels that arrive at the port in succession. Based on a berth plan, how to assign the QCs to vessels and schedule the QCs among the tasks of each vessel simultaneously is the main problem discussed in detail in this paper. In the processes of model construction and algorithm design, both the non-crossing of QCs and the serving relation constraints of pairs of tasks are adequately considered. The effectiveness of the model and algorithm is verified through three experiments.

Meisel F, Wichmann M. Container sequencing for quay cranes with internal reshuffles. OR Spectrum. 2010, 32(3): 569–591.

230 1

Zhang H, Kim K H. Maximizing the number of dual-cycle

Operations Research. 2011, 38(3): 683–693. [4]

Han J, Sun X N, Jin Z H. Coordinated optimization method for berth and quay crane allocation in container terminal. Journal of Dalian Maritime University. 2008(2): 117–121.

[5]

Ji M J, Jin Z H. A united optimization of crane scheduling and yard trailer routing in a container terminal. Journal of Fudan University (Natural Science). 2007(4): 476–480.

[6]

Tavakkoli-Moghaddam R, Makui A, Salahi S, et al. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports. Computers & Industrial Engineering. 2009, 56(1): 241–248.