S hip Plannin g S y s tem for Efficient Cran e Operation of Cont ain er T ermin al 2000 2
Ship Planning System for Efficient Crane Operation of Container Terminal Tae-Yeong Ha Department of Logistics Engineering Graduate School of Korea Maritime University Abstract In case of th e cont ainer t erm in al, as som ething affectin g in the productivity, the t erm in al w orking plan for loadin g and disch arging th e cont ain er is prob ably divided by berth allocation plan, y ard allocation plan, loadin g an d dischargin g plan, g at e operation plan. Loading and Dischargin g plan is classified the gantry crane allocation plan, loading, disch ar ging plan t o t ake the respon sibility of th e ship loading and unloading w ork. T he ba sic purpose of th ese w orkin g plan s can redu ce unloadin g tim e th at is for loadin g and discharging activities of container. Reducin g the dischargin g tim e can r edu ce not only additional cost at the position of th e - i -
shipping company, but also can in crease th e rat e of service at th e position of the t erm in al. th erefore it can b e expect ed attractin g shippin g com pany. It can be said that the t otal dischargin g tim e that is for loading and disch arging activities of containers are gen erally the w ork tim e an d th e setup tim e. Becau se the need tim e for loading and unloading depen ds on m achin e ' s efficien cy, it is the m ore reliable in m achin e ' s efficiency than in a m athem atical analy sis. T h erefore, th e efficient w orkin g plan can reduce setup tim e, an d it is directly connected t o redu ce loading and disch arging tim e of containers. In this paper, it sug gest the m athem atical m odel ab out y ard ' s am ount of th e m at erials for the allocation an d h at ch allocation per g antry cr ane t o t ake the r espon sibility of the ship loading an d unloadin g w ork aft er the berth allocation and the y ard ' s am ount of the m at erials. - ii -
A BST RA CT, 1 1 1.1 1 1.2 3 1.3 5 2 6 2.1 6 2.1.1 7 2.1.2 7 2.1.3 8 2.2 9 2.2.1 9 2.2.2 10 2.2.3 10 2.3 12 3 14 3.1 14 3.1.1 (G/ C) 14 3.1.2 16 3.2 20 3.2.1 (G/ C) 20 3.2.2 (T / C) 22 - iii -
3.2.3 (Y/ T ) 23 3.3 23 3.3.1 (Block ) 23 3.3.2 (Bay ) 24 3.3.3 (Row ) 25 3.3.4 25 3.4 26 3.4.1 26 3.4.2 27 3.4.3 30 4 34 4.1 34 4.2 42 5 45 47 - iv -
[ 3-1] T / C 24 [ 4-1] G/ C 35 [ 4-2] 35 [ 4-3] 40 [ 4-4] 41 [ 4-5] 42 [ 4-6] G/ C 43 [ 4-7] ( ) 43 - v -
[ 2-1] 6 [ 2-2] 7 [ 2-3] 8 [ 2-4] 11 [ 2-5] 12 [ 3-1] Hat ch 15 [ 3-2] 21 [ 3-3] (T / C) 22 [ 3-4] 24 [ 3-5] 24 [ 3-6] 25 [ 3-7] 26 [ 4-1] 34 [ 4-2] 2 36 [ 4-3] 3 37 [ 4-4] 4 38 [ 4-5] G/ C 44 - v i -
1 1.1 90%. (Multi- m odal T ran sportation )..,., T EU,.,.,.,,. - 1 -
.,,.,.,,,.,,..,. (w ork tim e) (setup tim e ).,.,., (Gantry Cran e, G/ C) Hat ch.. Hat ch,. (T ran sfer Cran e, T / C). - 2 -
. 1.2.. (v essel st ability ). (1995) (Decision Support Sy st em ), (Expert Sy st em ). (1996) (Artificial Int elligen ce), P rot otype, Dum bleton, J.J.(1990) Plann er. Jonathan J. Shields (1984), (M ont e Carlo) (random search ) (penalty ). (1990) Shift (Int eg er Program m in g ), (bran ch an d bound ), (Dyn am ic P rogram m ing ) - 3 -
. (1997), (Gen etic Alg orithm ). (Straddle Carrier, S/ C). D. J. S agnin aw II A. N. P erakis (1989),. (Lagran gean Relx ation ) Ran a & Vick son (1991), F ish er & Rosein (1989), Dagan zo & P eterk ofsky (1990).. (1997), (Heuristic). (1995) (S/ C), Quadratic Program m in g. (1998) (T ran sfer Crane, T / C), F CF S (fir st com e, fir st service), UT (unidirection al trav el), NT (nearest tru ck first serv ed ), SPT (sh ortest processing tim e rule ),. (1986) (GM ),. (1999)., T SP (T rav elin g S alesm an - 4 -
P roblem ) T our Con stru ction T our Improv em ent,,..,. 1.3 1,. 2. 3, (Real tim e ) (H euristic). 4. 5. - 5 -
2 (cont ainer t erm in al).,. 2.1,.. (1) (b erth allocation planning ) (2) (y ard allocation plannin g ) (3) (unloading/ loading planning ) (gat e),. [ 2-1], - 6 -
.. 2.1.1.,., 1,.. [ 2-2] 2.1.2 (M ar shalling )..,,, - 7 -
., (T / C, S/ C).,,.. [ 2-3] 2.1.3..,... (1) (g antry crane allocation planning ) (2) (unloading planning ) (3) (loading planning ) - 8 -
,. 2.2 2.2.1, (G/ C, T / C, Yard T ract or )..,. (H atch ),., H atch, H atch H at ch. Hatch., Hat ch H at ch.,. ( + ) H atch ( ), ( ) - 9 -
2.2.2. (Stow age Plan ), W orking S chedule.. (h at ch cov er, cell guide) (shiftin g cont ain er ) (Dischargin g S equ en ce List ). 2.2.3.,. (Gen eral St ow age Plan ) (Loading Container N o List ), (Bay Plan ) (Loading S equen ce List ).. (1) : - 10 -
. (P ort side) (Starboard ) (Starboard ) (P ort side ) Vertical order Horizont al order v ertical order [ 2-4] (2) 20, 40, 45 ov er - dim en sion, break - bulk, reefer, flat - rack un der deck, on deck, un der w at er line Em pty (3) - 11 -
(Loading S equen ce List ). 2.3.,,. [ 2-5] - 12 -
(code),.,,,, H at ch.. H atch. H atch.,.,,.,. - 13 -
3 3.1 3.1.1 (G/ C ),.,. (H at ch ),. (Lin e Balan cin g ). H at ch, Hat ch H atch. H at ch, Hat ch, H at ch H atch Deck H old.... - 14 -
., Hat ch. [ 3-1]. [ 3-1] H atch.,... - 15 -
3.1.2.. Hat ch. H at ch Deck Hold.,. Deck Hold, H old Deck. H at ch,.,...,.. n = m = a i = i D = ( i, j ) - 16 -
x k 1 : i k i = { 0 : other wise t i = i T = n Deck H old, 0, T. T.. M in im iz e T (1) S u bj ect T o x 1 i + 2 x 1 i, i = 1, 2,..., n - 2 (2) x k i + 2 x k - 1 i + x k i, i = 1, 2,..., n - 2, k = 2, 3,..., m (3) x m i + 2 x m i, i = n + 1, n + 2,...2 n - 2 (4) x k i + 2 x k + 1 i + x k i, i = n + 1, n + 2,..., 2 n - 2, k = 1, 2,..., m - 1 (5) x k i = 1, i = 1, 2,..., 2 n (6) k t i + a i T, i = 1, 2,...2n (7) t i + a i t i + 1, i = 1, 3,..., 2 n - 1 (8) x k i = 1 an d x k j = 1 t i + a i t j, i = 1,..., 2 n - 1, j = i + 1,..., 2n, k (9) x k i = 1 an d x k j = 1 t j + a j t i or t i + a i t j, ( i, j ) D, k /= k (10) t i + a i t 2 n - i + 1, i = 1, 2,..., n (11) t i 0, i = 1, 2,..., 2 n (12) x k i {0, 1}, i = 1, 2,..., 2 n, k = 1, 2,..., m (13) - 17 -
(2) (3) Deck H old, H old Deck (4) (5). (6). (7). (8) H atch Deck H old, H old Deck. (9),. (10), (11). (12), (13).., (9) (10) OR., Hatch, H at ch a i m ij a i + m ij. t i, a i, m ij t k i, a k i, m k ij... P seu do Code,. Pseudo Code. Line 1 : { Calculate bound b [0], b [1] } Line 2 : for i := 0 to 1 do - 18 -
Line 3 : begin Line 4 : { Initialize k and s } Line 5 : for j := 1 to n do Line 6 : begin Line 7 : s := s + a[i, j]; Line 8 : if { s exceed the bound b [j] } then Line 9 : { Assign s to crane k } Line 10 : s := 0; Line 11 : else Line 12 : { Assign s - a[i, j] to crane k } Line 13 : a := a[i, j]; Line 14 : end if Line 15 : end; Line 16 : end; Line 17 : while { exist exchangeable job } do Line 18 : begin Line 19 : T1 := T; Line 20 : repeat Line 21 : { select exchangeable job i } Line 22 : { exchange selected job i } Line 23 : { calculate ending time T2 } Line 24 : if T2 T1 then Line 25 : T1 := T2; Line 26 : j := i; Line 27 : end if Line 28 : until { All exchangeable job checked }; Line 29 : if T1 T then Line 30 : { exchange job j } Line 31 : T := T1; Line 32 : end if Line 33 : end;. (Line 1) Deck H old (Line 2 16). (Line 17 33). ( - 19 -
, 1998). H at ch, H at ch.. Hat ch, (T / C). 3.2... 3.2.1 (G/ C ) Hatch (Yard T ract or, Y/ T ) (Cell).,. [ 3-2] (,,, ). - 20 -
[ 3-2],... (1, 2, 3, 4) (A, B, C) 4, A 2 B 2, 4 C2 4 C2 = 36, C 2 4 C2 4 C2 4 C2 = 216-21 -
., (,, ).. 3.2.2 (T / C ),., G/ C 1 T / C 2-3, Y/ T 5. T / C G/ C G/ C. G/ C T / C. T / C [ 3-3]. [ 3-3] (T / C) G/ C T / C, G/ C,. T / C, T / C - 22 -
. 3.2.3 (Y/ T ) (Y/ T ) G/ C T / C. T / C G/ C. Y/ T. 3.3 G/ C T / C. T / C T / C. T / C,, T / C. 3.3.1 (B lock ) G/ C T / C,. T / C., T / C., - 23 -
[ 3-4]. [ 3-1] T / C T/C CNTR (1 ) (1bay) 10km/h 30 sec 2.34 sec 175.32 sec [ 3-4] 3.3.2 (B ay ) G/ C,. G/ C. T / C., [ 3-5]. [ 3-5] - 24 -
3.3.3 (R ow ) T / C (Row ) (Spreader ).. G/ C (Re- h andling )., [ 3-6]. [ 3-6] 3.3.4 T / C (,, ) G/ C. T / C.,. [ 3-7]. - 25 -
[ 3-7] 3.4 3.4.1 T / C... G/ C T / C, Y/ T, H at ch.,,.,... T / C,,. - 26 -
.. 3.4.2. m : n : ( ) l : (bay ) r : (row ) A : G : (G/ C) W B W b W r W t W d : : : : : d ij : i j, ( i, j = 1, 2,..., m ) S n j : j, ( j = 1, 2,..., m ) S b j : j, ( j = 1, 2,... l) S r j : j, ( j = 1, 2,... r ) D a : a, ( a = 1, 2,..., A ) G k a : G/ C k a ( a = 1, 2,..., A ), ( k = 1, 2,..., G) - 27 -
. 1 : i G/ C k x k i = { 0 : other wise ( i = 1, 2,..., n ) 1 : j G/ C k B k j = { 0 : other w ise ( j = 1, 2,... m ) 1 : bay j G/ C k H k j = { 0 : other wise ( j = 1, 2,... l ) 1 : row j G/ C k I k j = { 0 : other wise ( j = 1, 2,... r ) 1 : i i + 1 G/ C E k ii + 1 = { 0 : other wiz e ( i = 1, 2, 3,..., n - 1 ) (, i S n j, i + 1 S n j ) 1 : i j G/ C k F k ij = { 0 : other wise ( i, j = 1, 2, 3,..., m ) (, i /= j ) G/ C.,,,. G/ C. G k m j B k j + G k j l H k j + G k r j I k j + G k n - 1 i E k ii + 1 + G k m i m j d ij F k ij - 28 -
,, G m W B k j + W t G B k j + W b G n - 1 k i l k j E k ii + 1 + W d G H k j + W r G m m k i j r I k j k j d ij F k ij (1) G/ C. x k i - B k j 0 (2) G/ C, x k i - H k j 0, x k i - I k j 0 (3), (4) G/ C. G/ C G/ C, G/ C. x k i - x k i + 1 E k ii + 1, B k i + B k j - 1 F k ij (5), (6),. M in im iz e W B G m k j + W t G B k j + W b G n - 1 k i l k j E k ii + 1 + W d G H k j + W r G m m k i j r I k j k j d ij F k ij (1) - 29 -
S u bj ect T o x k i - B k j 0, ij ( i S n j ), k (2) x k i - H k j 0, ij ( i S b j ), k (3) x k i - I k j 0, ij ( i S r j ), k (4) x k i - x k i + 1 E k ii + 1, i = 1, 2,..., n - 1, k, ( i S n j, i + 1 S n j ) (5) B k i + B k j - 1 F k ij, k, ij ( i /= j ) (6) G k x k i = 1, i, ( k = 1, 2,..., G) (7) n i D a x k i = G k a, a, k (8) x k i = {0, 1}, i, k (9) B k j, H k j, I k j = {0, 1}, j, k (10) E k ii + 1 = {0, 1}, i ( i S n j, i + 1 S n j, j ) (11) F k ij = {0, 1}, k, ( i, j ), i j (12) (7) G/ C, (8) G/ C. (9), (10), (11), (12). (Integ er P rogram m - ing, IP ). 4. 3.4.3., - 30 -
..,,.. k : ( k = 1, 2,... m ) T S : QB j Qb j Qr j S B : j (block ) : j (b ay ) : j (row ) : S b S r G k U i : : : k : P has e 1. S e t S e q ue nc e S te p 1 : k! G/ C U i, G/ C k. i = 1, k = 1. S te p 2 : if i > k! then M in {U * i } O *. else Phase 2. P has e 2. B lo c k A llo c at io n S te p 1 : U i G/ C k S B G k j. - 31 -
S te p 2 : if j = th en Ph ase 3. else M ax { Q B j } k. S te p 3 : if G k = then k = k + 1, Ph ase 1. else Step 1. P has e 3. Bay A llo c at io n S te p 1 : G k, j R S te p 2 : S b R and Q bj G k j. S te p 3 : if j = th en Ph ase 4. else M ax { Q bj } k. S te p 4 : if G k = then k = k + 1, Ph ase 2. else Step 1. P has e 4. Row A llo c at io n S te p 1 : G k,,, j R. S te p 2 : S r R and Q rj G k j. S te p 3 : if j = th en c R c k. else M ax { Q rj } k. Step 3 S te p 4 : if k = m then U i U * i. i = i + 1, k = 1, Ph ase 1 Step2 else k = k + 1, P hase 2 G/ C,, G/ C - 32 -
., G/ C. G/ C G/ C 2 S et 1(G/ C #1 G/ C #2), S et 2(G/ C #2 G/ C #1), G/ C 4 4!., ( ).,. - 33 -
4 4.1 G/ C. G/ C 2 3, 4. G/ C, [ 4-1]. Lay out 6 4.,.. [ 4-1] - 34 -
[ 4-1] G/ C 2, 3, 4, G/ C G/ C,. [ 4-1] G/ C : 2 3 4 G/ C #1 G/ C #2 G/ C #1 G/ C #2 G/ C #3 G/ C #1 G/ C #2 G/ C #3 G/ C #4 A 33 30 27 20 16 20 17 14 12 63 B 20 28 11 13 24 5 13 12 18 48 C 30 20 20 19 11 15 12 8 15 50 D 26 30 14 20 22 13 15 12 16 56 109 108 72 72 73 53 57 46 61 217 217 217 W B W b W r W t W d.. [ 4-2] 1 2 3 4 W B 1000000 1 1 2 3 W b 50000 2 1 1 2 W r 5000 3 2 1 1 W t 500 4 3 2 1 W d 1, (LINDO). - 35 -
[ 4-2] 2-36 -
[ 4-3] 3-37 -
[ 4-4] 4-38 -
,., G/ C., G/ C #1 1, 3, 4, G/ C #2 1, 2. 1 G/ C G/ C., 1 G/ C, G/ C #1 3[4], 5[6], 7[8], G/ C #2 1[2], 3[4], 5[6], 9[10]., 3[4], 5[6] G/ C #1 3[4] 3, 4, 6 5[6] 1, 2, 3, 4, 6, G/ C #2 5[6] 6.,,. 3 4. 3 2, 4,.,,,,..,. 2 3[4] G/ C #2 5 ( 3 )..., 2 G/ C 3.. - 39 -
.... [ 4-3] Case 1 Case 2 Case 3 Case 4 Case 5 Case 6 Case 7 Case 8 Case 9 Case 10 B H I E D 5 10 32 2 14 5661014 6 9 32 2 24 6611024 6 10 32 2 24 6661024 6 10 32 2 24 6661024 6 10 32 2 24 6661024 6 10 32 2 24 6661024 5 10 33 2 14 5666014 5 10 33 2 14 5666014 5 10 32 2 16 5661016 5 10 32 3 16 5661516 5 9 33 1 18 5615518 5 9 33 1 18 5615518 6 10 32 3 24 6661524 6 10 32 3 24 6661524 5 9 33 1 14 5615514 5 9 33 1 14 5615514 5 10 32 3 14 5661514 5 10 33 3 16 5666516 5 9 32 1 16 5610516 5 9 32 1 16 5610516 B : G/ C H : G/ C I : G/ C E : G/ C D : G/ C - 40 -
... [ 4-4]. [ 4-4] Case 1 Case 2 Case 3 Case 4 Case 5 Case 6 Case 7 Case 8 Case 9 Case 10 B H I E D 5 9 33 1 14 5615514 5 9 33 3 16 5616516 5 9 33 2 14 5616014 5 9 34 6 16 5623016 5 9 32 1 16 5610516 5 9 32 2 16 5611016 5 8 32 1 16 5560516 5 8 32 1 16 5560516 5 9 32 3 14 5611514 5 9 33 3 14 5611514 5 9 32 3 18 5611518 5 9 32 3 18 5611518 5 8 32 1 18 5560518 5 8 32 1 18 5560518 5 9 32 2 14 5611014 5 9 32 2 14 5611014 5 9 33 1 16 5615516 5 9 32 2 16 5615516 5 9 32 2 18 5611018 5 9 32 2 18 5611018 B : G/ C H : G/ C I : G/ C E : G/ C D : G/ C [ 4-5]. - 41 -
[ 4-5] Case 1 Case 2 Case 3 Case 4 Case 5 Case 6 Case 7 Case 8 Case 9 Case 10 B H I E D 5 9 32 1 16 5610516 5 9 32 1 16 5610516 5 9 32 2 18 5611018 5 9 32 2 18 5611018 5 9 33 2 16 5616016 5 9 33 2 16 5616016 5 9 32 1 16 5610516 5 9 32 2 16 5611016 5 9 32 1 18 5610518 5 9 32 2 14 5611014 5 9 33 2 14 5616014 5 10 33 3 14 5666514 5 9 32 1 14 5610514 5 9 33 2 16 5616016 5 9 32 1 18 5610518 5 9 33 2 16 5616016 5 9 33 2 18 5616018 6 9 33 3 34 6616534 5 9 32 2 14 5611014 5 9 32 3 14 5611514 B : G/ C H : G/ C I : G/ C E : G/ C D : G/ C. 4.2. 1998 Kaw asaki Contain er T erm inal,., - 42 -
,. 6 4 7 4.,. G/ C (A, B,...,W ) [ 4-5] T / C [ 4-6]. [ 4-6] G/ C A B C D E F G H I J K L M N O P Q R S T U V W G/C #1 0 0 5 0 0 6 0 0 0 10 0 0 75 7 2 2 5 0 38 20 30 1 1 202 G/C #2 79 55 28 26 12 0 1 1 1 0 2 2 0 0 0 0 0 1 16 24 7 0 0 255 79 55 33 26 12 6 1 1 1 10 2 2 75 7 2 2 5 1 54 44 37 1 1 457 [ 4-7] ( ) 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 2 1 1 2 3 4 5 6 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 6 5 4 3 2 1 1 2 7 6 5 4 3 2 1 1 8 7 6 5 4 3 2 1.,,. [ 4-5]. - 43 -
[ 4-5] G/ C ( 2-3[4]).,,. - 44 -
5,.,,...,,... H at ch,..,, H atch.,.. - 45 -
,,.., (setup tim e)..,.,.,.,..,. - 46 -
Dagan zo, C.F.(1989), T he Cran e S chedulin g Problem, T ransp ortation R es earch B, V ol. 23B, No. 3, pp.159-175. Dagan zo, C.F. an d R.I. P eterkofsky (1990), A Branch and Bound S olution M ethod for th e Cran e S ch eduling Problem, T ransp ortation R es earch B, V ol. 24B, pp.159-172. Dum bleton, J.J.(1990), Expert Sy stem Application on Ocean Shippin g - A Statu s Report, M arine T echn ology, V ol. 27, pp.265-284. F isher, M.L. an d M.B. Rosen w ein (1989), An Interactiv e Optim ization Sy stem for Bulk - Cargo Ship S chedulin g, N aval R es earch L og is tics, Vol.36, pp.27-42. H w an, Kim Kap, Bae Kim H on g (1999), "S egreg ating space allocation m odels for container inv entories in port cont ain er t erm in als, I n ternational J ournal Of P rod uction E conom ics (59)1-3, pp.415-423. Kim Kap H w an, Kim Ki Young (1999), Routin g straddle carrier s for th e loadin g operation of containers u sing a beam search alg orithm, Comp uters A nd I ndus trial E ng in eering (36)1, pp.109-136. Rana, K. an d R.G. Vick son (1991), Routin g Cont ainer Ship s U sin g Lagran gean Relax ation and Decomposition, T ransp ortation S cience, Vol. 25, N o. 3, pp.201-214. S agnin aw II, D.J. and A.N. P erakis (1989), A Decision Support Sy st em for Cont ainer ship St ow age Planning, M arin e T echnology, V ol. 26, pp.47-61. S cheith auer Guntram (1999), LP - based boun ds for the contain er and m ulti- - 47 -
container loadin g problem, I n ternational T ransactions I n Op erational R es earch (6)2, pp.199-213. Shields, J.J.(1984), Cont ain er St ow ag e : A Com puter - Aided Preplannin g Sy st em, M arine T echnology, V ol. 21, pp.370-383. Youn g Kim Ki, Hw an Kim Kap (1999), A routing algorithm for a sin gle straddle carrier t o load ex port cont ainer s ont o a cont ain er ship, I n ternational J ournal Of P rod uction E conom ics (59)1-3, pp.425-433. Yun W on Youn g, Choi Yon g S eok (1999), A sim ulation m odel for cont ain er - t erm in al operation analy sis u sing an object - orient ed approach, I n ternational J ournal Of P rod uction E conom ics (59)1-3, pp.221-230. (1996),,. (1995),,. (1996),,, 10, 2, pp.43-50. (1996),, 96, pp.36-41. (1995),, 1995, 9 1, pp.19-32. (1997),,, 11, 1, pp.65-73. - 48 -
(1998),, 98, pp.14-17. (1997),,, pp.64-67. (1999),,. (1996),,, pp.473-476. (1994),. (1998),,. (1998),, 98, pp.309-313. (1997),, 22 4, pp.115-131. (1986),,. - 49 -