Berth Allocation Problem

صفحه 1:
In ’The Name Of Allah Berth Allocation Problem (BAP) Zeinab ‘Terikan Fall 2008 

صفحه 2:
3 = ‏ای‎ ۰ ‘An introduction to berth allocation problem (BAP) “Berth allocation importance “BAP; past, present and future Berth Allocation Problem Some classifications “Modeling and solution techniques “Literature review on the BAP Some Samples *Kim and Moon(2003) “Nishimura, Imai and Papadimitriou(2001) “Lee and Chen(2008) Reference 

صفحه 3:
A good berth allocation can : “maximize the utilization of a wharf “reduce costs “lead to higher revenues o port “increase port throughput *zeduce turnapgund time Sboa) واه 

صفحه 4:
*FCFS rule “Negotiation “Trial-and-error “Graphic-user-interface in a computer system “Future perspective : “An optimization -based approach that can Lee and Chen(2008) earve ac tha rnre nf a firtiirea NSS that 

صفحه 5:
TaN a ۷ am ۳ ipa es ‏تم‎ ‎Coordi ft 2 wet | ‏ی‎ ‎ane ‎|) ‏ی‎ ‎3 ‎we |] aa, |] Gow a, 77 200 300 400 500 600 700 800 berth ali} NAMA 0 1607 51233 a }124 date 6000 0 2۳| ‏دج‎ ‎0 ‏دم عد‎ 00 0 Kim and Moon(2003) 

صفحه 6:
Terminal ‏العا‎ Terminal Bort Space Quay Space (MUT) Multi | User 

صفحه 7:
BAP Classificatia ‏ند‎ ‎ns ۱) ۰۰۳۳ © ۱ ‏حك ی‎ es 

صفحه 8:
Integer programming *Mixed-integer-linear programming (Kim and Moon(2003)) “Binary integer programming (Lee and Chen(2008)) “non-linear integer programming(Nishimura et al. (2001)) 

صفحه 9:
* Nishimura et al.(2001) ۱ * Guan et al.(2002) * Imai et al.(2005) the total * Imai ct al.(2007) * Imai et al.(2008) service time | Liang et al.(2008) 

صفحه 10:
1 ‏سه تس‎ Moon(2003) ‏تسس‎ | + Wang and Lim(2007) ‏اس نا‎ Lee and Chen(2008) ————— i) * Brown et al.(1994,1997) | (۳ + Lim(1998) \ 7 ۳ * Lie et al.(1998) | )_———— | * Imai(2001,2005a) { ‏سس‎ 

صفحه 11:
J. Solution Street ‏غم‎ ‎(۱۹4 

صفحه 12:
دود زا رای ‎Heuristic algorithm - FCFS allocation‏ ‎strategy‏ Naval ports - Maximize the sum of benefits for ships while in port Commercial and busy ports - Ignore FCFS allocation strategy - Static situation - Heuristic algorithm Minimizing the maximum amount of quay space used at any time - every ship berthed as soon as it arrived at the port Solved BAPC both with and without ship’s movement restriction - Minimize the مور ۳۰۱ Lai and Shih (1992) Brown et al. (1994,1997) Imai et al. (1997) Lim (1998) Li et al. (1998) 

صفحه 13:
DBAP - Maximize berth performance - Heuristic algorithm using subgradient method. with Lagrangian Relaxation - same water depth for all the berth DBAP with multi-water depth configuration - genetic algorithms Developed a heuristic for the BAPC with the objective that minimizes the total weighted completion time of ship services BAPC - minimize the costs of delayed departures of ships -subgradient optimization method vee Imai et al. (2001,2005a) Nishimura et al. (2001) Guan et al. (2002) Park and Kim (2002) 

صفحه 14:
تولو در زاب Extended the BAP in Imai et al. (2001, 2005a) - treat the ships with different priorities BAPC - heuristic algorithm - handling time depends on the berthing location of ship A tabu search heuristic for the DBAP - both discrete and continuous location indexes BAP with simultaneous berthing of multiple ships at the indented berth - potentially useful for fast turnaround of mega-containerships مور ۳-1 Imai et al. (2003) Imai et al. (2005b) Cordeau et al. (2005) Imai et al. (2007) 

صفحه 15:
“A linear integer program was formulated. “The objective is to minimize the penalty and the additional handling costs. “Simultaneously determines the berthing time and location. “The wharf is considered to be a continuous 

صفحه 16:
N: Thetotahumbeof vessels. L:Thelengthf a wharf. p,: Thelowestcostberthinkgcationf vessdl : Theberthingositiomf vessdl(adecisionariable). : Theberthintimef vessdl(adecisionariable). : Theestimatedtrivalimef vessel : Thedepartutimeequestebly vessel 5 :Thetimeequiretbr thehipoperatidior vessél G,; :Theadditionatavetostpemnitdistanderdeliverinthe containefer vessélresultinfyonnon- optimaberthin locationelativeothdowest costpoint. So / QL 

صفحه 17:
©, : Thepenaltyostpemnit timef vessel, resultirfyonn departudelayeHheyondheequestedctime J,: Thdengthf vessel. Thisvaluéncludesheequestedpbetweearjacenetssels. _ {lif vesselislocatetothdeftof vesse]jon thevharf a tn otherwise _{l:if vesselisberthdaeforeesse]jin time a 0 otherwise 

صفحه 18:
vessel j (رد زد vessel i در 

صفحه 19:
| _ ‏ا‎ : Min>) glx- pl+G(y+b- dl", ist where* =max0, x. 

صفحه 20:
( ان + ) ;9+ هه ۱۰ سل subject to ‎for alli‏ و وه رو ود ‏اه ها ‎—B,‏ 4 بر ‏ناکرا جرد ‎wth <x +M(1—21) forall iand j. 74 j, and a large positive number M ‏(ر )۸ رکه بر‎ foralliand j, i #j, and a large positive number M aytyt2, +721 foralléiand j, iA j ‎wea, for alli ‎4, Bi By mre O for all i ‎ ‎2.2), 0/1 integer for all iand j, iA f ‎3 

صفحه 21:
* Dynamic berth allocation to ships in the public berth system. “The objective is to minimize the total service time of incoming ships. *A non-linear integer program was 

صفحه 22:
{et fitness oF [Calculate objective function value] dissatisfied incvidull bo zero Tare are cane czsctypes each ob Tet fenear oF one inividiai be 20r9 Transform it to Riness value Generate inal individuals th water-depth in assigned NO Tet nanrauale havi better Frees be naw parents Feurent ‏ی‎ 11 (Genetic Operations 3 Generate new children 33 

صفحه 23:
حو حي 5۰ 2 ۶4 *The objective is to maximize the total utility. “Included a number of practical considerations not seen in previous papers. “The problem is dynamic. “The space is continuous. “The ships berthed within one of several preferred sections, which are independently defined by the agents of each ship. * Ships are berthed on a FCFS basis, but shifting the position of a ship to make space for another is also 

صفحه 24:
The proposed solution process solves the problem in three stages: * In the first stage it generates a number of candidate berthing allocations for each ship. * In the next stage it uses a neighborhood search heuristic to come up with a good combination of feasible ae yy ‏آ‎ 

صفحه 25:
و ‎[Use inital solution as best known solution‏ Randomly select a ship 5 Replace the sande ofS in ie coset | "Sition with atte candidate of oiled 2 ee Replace best ee] solution Flow chart of the rete rere tel Re veo Were 7039 ] neighborhood sean 

صفحه 26:
The simultaneous berth and quay crane allocati Sn = = 

صفحه 27:
planning in the public berth system by genetic algorithms. European Journal of Operational Research 131, 282-292. Kim, K., Moon, K., 2003. Berth scheduling by simulated annealing. Transportation Research B 37, 541-560. Imai, A., Sun, X., Nishimura, E., Papadimitriou, S., 2005. Berth allocation in a container port: using a continuous location space approach. 

صفحه 28:
Wang, F., Lim, A., 2007.A stochastic beam search for the berth allocation problem. Decision Support Systems 42, 2186-2196. Imai, A., Chen, H., Nishimura, E., Papadimitriou, S., 2008. The simultaneous berth and quay crane allocation problem. Transportation Research Part E 44, 900-920. Lee, Y., Chen, C., 2008. An optimization heuristic for the berth scheduling problem. European Journal of Operational Research, Article in press. 

صفحه 29:


Fall 2008 Content An introduction to berth allocation problem (BAP) Berth allocation importance BAP; past, present and future Berth Allocation Problem Some classifications Modeling and solution techniques Literature review on the BAP Some Samples Kim and Moon(2003) Nishimura, Imai and Papadimitriou(2001) Lee and Chen(2008) Reference Berth allocation importance A good berth allocation can : maximize the utilization of a wharf reduce costs lead to higher revenues of port increase port throughput reduce turnaround time of Kim and Moon(2003),Liang et al.(2008) BAP; past, present and future FCFS rule Negotiation Trial-and-error Graphic-user-interface in a computer system Future perspective : “An optimization –based approach that can Lee and Chen(2008) An example of a berth schedule Kim and Moon(2003) BAP Classifications BAP Classificatio ns (cont’d) BAP modeling Integer programming Mixed-integer-linear programming (Kim and Moon(2003)) Binary integer programming (Lee and Chen(2008)) non-linear integer programming(Nishimura et al. (2001)) BAP objective functions BAP objective functions(cont’d) Literature review on the BAP Paper Properties Lai and Shih (1992) Heuristic algorithm – FCFS allocation strategy Brown et al. (1994,1997) Naval ports – Maximize the sum of benefits for ships while in port Imai et al. (1997) Commercial and busy ports – Ignore FCFS allocation strategy – Static situation – Heuristic algorithm Lim (1998) Minimizing the maximum amount of quay space used at any time - every ship berthed as soon as it arrived at the port Li et al. (1998) Solved BAPC both with and without ship’s movement restriction – Minimize the Literature review on the BAP Paper Properties Imai et al. (2001,2005a) DBAP – Maximize berth performance – Heuristic algorithm using subgradient method with Lagrangian Relaxation – same water depth for all the berth Nishimura et al. (2001) DBAP with multi-water depth configuration genetic algorithms Guan et al. (2002) Developed a heuristic for the BAPC with the objective that minimizes the total weighted completion time of ship services Park and Kim (2002) BAPC - minimize the costs of delayed departures of ships –subgradient optimization method Literature review on the BAP Paper Properties Imai et al. (2003) Extended the BAP in Imai et al. (2001, 2005a) treat the ships with different priorities Imai et al. (2005b) BAPC – heuristic algorithm - handling time depends on the berthing location of ship Cordeau et al. (2005) A tabu search heuristic for the DBAP - both discrete and continuous location indexes Imai et al. (2007) BAP with simultaneous berthing of multiple ships at the indented berth - potentially useful for fast turnaround of mega-containerships Kim and Moon(2003) A linear integer program was formulated. The objective is to minimize the penalty and the additional handling costs. Simultaneously determines the berthing time and location. The wharf is considered to be a continuous Kim and Moon(2003) (cont’d) N : Thetotalnumber of vessels. L : Thelength of a wharf. pi : Thelowest- costberthing location of vessel i. xi : Theberthing position of vessel i (adecisionariable). v yi : Theberthing timeof vessel i (adecisionariable). v ai : Theestimated arrivaltimeof vessel i. di : Thedeparture timerequested by vessel i. bi : Thetimerequired for the shipoperation for vessel i. c1i : Theadditional travel costperunitdistance fordelivering the containers for vessel i, resulting fromnon- optimal berthing location relative tothelowest- costpoint. Kim and Moon(2003) (cont’d) c2i : Thepenalty costperunit time of vesseli, resulting froma departure delayed beyond therequested duetime. li : Thelength of vesseli. Thisvalue includes therequested gapbetween adjacentessels. v totheleftof vesselj on thewharf 1: if vesseli islocated z : 0 : otherwise x ij beforevesselj in time 1: if vesseli is berthed z : 0 : otherwise y ij Kim and Moon(2003) (cont’d) Kim and Moon(2003) (cont’d) N  Min c1i xi  pi  c2i  yi  bi  di  i 1 wherex max 0, x .   , Kim and Moon(2003) (cont’d) ishimura et al.(2001)  Dynamic berth allocation to ships in the public berth system. The objective is to minimize the total service time of incoming ships. A non-linear integer program was shimura et al.(2001) Lee and Chen(2008) The objective is to maximize the total utility. Included a number of practical considerations not seen in previous papers. The problem is dynamic. The space is continuous. The ships berthed within one of several preferred sections, which are independently defined by the agents of each ship.  Ships are berthed on a FCFS basis, but shifting the position of a ship to make space for another is also Lee and Chen(2008) (cont’d) The proposed solution process solves the problem in three stages:  In the first stage it generates a number of candidate berthing allocations for each ship.  In the next stage it uses a neighborhood search heuristic to come up with a good combination of feasible Lee and Chen(2008) (cont’d) The simultaneous berth and quay crane allocation Reference Nishimura, E., Imai, A., Papadimitriou, S., 2001. Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research 131, 282–292. Kim, K., Moon, K., 2003. Berth scheduling by simulated annealing. Transportation Research B 37, 541–560. Imai, A., Sun, X., Nishimura, E., Papadimitriou, S., 2005. Berth allocation in a container port: using a continuous location space approach. Reference(co nt’d) Wang, F., Lim, A., 2007.A stochastic beam search for the berth allocation problem. Decision Support Systems 42, 2186–2196. Imai, A., Chen, H., Nishimura, E., Papadimitriou, S., 2008. The simultaneous berth and quay crane allocation problem. Transportation Research Part E 44, 900–920. Lee, Y., Chen, C., 2008. An optimization heuristic for the berth scheduling problem. European Journal of Operational Research, Article in press.