Two decision models for berth allocation problem under uncertainty considering service level

Flexible Services and Manufacturing Journal - Tập 29 - Trang 312-344 - 2017
Changchun Liu1, Xi Xiang2, Li Zheng1
1Department of Industrial Engineering, Tsinghua University, Beijing, China.
2Logistics Engineering and Simulation Laboratory, Graduate School at Shenzhen, Tsinghua University, Shenzhen, China

Tóm tắt

This paper examines the berth allocation problem, which is to assign a quay space and a service time to the vessels that have to be loaded and unloaded at a container terminal within a given planning horizon, with consideration of uncertain factors, mainly including the arrival and operation time of the calling vessels. Based on the concept of conflict, two kinds of service level are proposed and two decision models are constructed to minimize the total operational cost, which includes delay cost and non-optimal berthing location cost. The first model satisfies the service level of a specific scenario and the second one considers the service level across all scenarios. Due to the NP-hardness of the constructed model, a two-stage heuristics algorithm is employed to solve the problem. Finally, extensive numerical experiments are conducted to test the performances of the two proposed models and algorithm and help the port planners make decisions.

Tài liệu tham khảo

Bierwirth C, Meisel F (2010) A survey of berth allocation and quay crane scheduling problems in container terminals. Europ J Oper Res 202(3):615–627 Bierwirth C, Meisel F (2015) A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. Europ J Oper Res 244(3):675–689 Chang D, Yan W, Chen C-H, Jiang Z (2008) A berth allocation strategy using heuristics algorithm and simulation optimisation. Int J Comput Appl Technol 32(4):272–281 Chen CY, Hsieh TW (1999) A time-space network model for the berth allocation problem. In: 19th IFIP TC7 Conference on system modeling and optimization, Cambridge Dai J, Lin W, Moorthy R, Teo CP (2008) Berth allocation planning optimization in container terminals. In: Tang CS, Teo CP, Wei KK (eds) Supply chain analysis: a handbook on the interaction of information, system and optimization. Springer, New York, pp 69–105 Du Y, Xu Y, Chen Q (2010) A feedback procedure for robust berth allocation with stochastic vessel delays. Intell Control and Automation IEEE 20:2210–2215 Gao C, Zhang R, Du Y, Chen Q (2010) A proactive and reactive framework for berth allocation with uncertainties. In: 2010 IEEE international conference on advanced management science (ICAMS), Vol. 3; pp. 144–149 Giallombardo G, Moccia L, Salani M, Vacca I (2010) Modeling and solving the tactical berth allocation problem. Trans Res Part B Methodological 44(2):232–245 Guan Y, Xiao W-Q, Cheung RK, Li C-L (2002) A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis. Oper Res Lett 30(5):343–350 Guan Y, Cheung RK (2004) The berth allocation problem: models and solution methods. OR Spectr 26:75–92 Golias MM (2011) A bi-objective berth allocation formulation to account for vessel handling time uncertainty. Maritime Econ Logist 13(4):419–441 Golias M, Portal I, Konur D, Kaisar E, Kolomvos G (2014) Robust berth scheduling at marine container terminals via hierarchical optimization. Comput Oper Res 41:412–422 Han X, Lu Z, Xi (2010) A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time. Europ J Oper Res 207:1327–1340 Hansen P, Oguz C, Mladenovic N (2008) Variable neighborhood search for minimum cost berth allocation. Europ J Oper Res 191:636–649 Hansen P, Oguz C (2003) A note on formulations of static and dynamic berth allocation problems. Les Cahiers du GERAD 30:1–17 Hendriks M, Laumanns M, Lefeber E, Udding JT (2010) Robust cyclic berth planning of container vessels. OR Spectr 32(3):501–517 Imai A, Nagaiwa K, Chan W (1997) Efficient planning of berthing allocation for container terminals in Asia. J Adv Trans 31:75–94 Imai A, Nishimura E, Papadimitriou S (2001) The dynamic berth allocation problem for a container port. Trans Res Part B Methodological 35:401–417 Imai A, Nishimura E, Papadimitriou S (2003) Berth allocation with service priority. Trans Res Part B Methodological 37(5):437–457 Imai A, Sun X, Nishimura E, Papadimitriou S (2005) Berth allocation in a container port: Using a continuous location space approach. Trans Res Part B Methodological 39:199–221 Imai A, Nishimura E, Hattori M, Papadimitriou S (2007) Berth allocation at indented berths for mega-containerships. Europ J Oper Res 179(2):579–593 Imai A, Chen HC, Nishimura E, Papadimitriou S (2008) The simultaneous berth and quay crane allocation problem. Trans Res Part E Logist Trans Rev 44(5):900–920 James RJ, Almada-Lobo B (2011) Single and parallel machine capacitated lotsizing and scheduling: new iterative MIP-based neighborhood search heuristics. Comput Oper Res 38(12):1816–1825 Karafa J, Golias MM, Ivey S, Saharidis GK, Leonardos N (2013). The berth allocation problem with stochastic vessel handling times. The Int J Adv Manuf Technol, 1–12 Kim K, Moon K (2003) Berth scheduling by simulated annealing. Trans Res Part B Methodological 37:541–560 Li CL, Cai X, Lee CY (1998) Scheduling with multiple-job-on-one-processor pattern. IIE Trans 30(5):433–445 Liu C, Xiang X, Zhang C, Zheng L (2016a) A decision model for berth allocation under uncertainty considering service level using an adaptive differential evolution algorithm. Asia-Pacif J Oper Res 33(6):1–28 Liu C, Zheng L, Zhang C (2016) Behavior perception-based disruption models for berth allocation and quay crane assignment problems. Comput Ind Eng 97:258–275 Liu C, Zhang C, Zheng L (2017) A bi-objective model for robust yard allocation scheduling for outbound containers. Eng Optim 49(1):113–135 Meisel F, Bierwirth C (1998) Heuristics for the integration of crane productivity in the berth allocation problem. Trans Res Part E Logist Trans Rev 45(1):196–209 Meisel F, Bierwirth C (2013) A framework for integrated berth allocation and crane operations planning in seaport container terminals. Trans Sci 47(2):131–147 Monaco MF, Sammarra M (2007) The berth allocation problem: a strong formulation solved by a Lagrangean approach. Trans Sci 41(2):265–280 Moon K (2000) A mathematical model and a heuristic algorithm for berth planning. Ph.D. Thesis, Pusan National University, Pusan 2000 Moorthy R, Teo CP (2006) Berth management in container terminal: the template design problem. OR spectrum 28:495–518 Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper Res 43(2):264–281 Murty KG, Liu J, Wan YW, Linn R (2005) A decision support system for operations in container terminal. Decis Support Syst 39:309–332 Nishimura E, Imai A, Papadimitriou S (2001) Berth allocation planning in the public berth system by genetic algorithms. Europ J Oper Res 131:282–292 Park K, Kim K (2002) Berth scheduling for container terminals by using a sub-gradient optimization technique. J Oper Res Soc 53:1054–1062 Steenken D, VoB S, Stahlbock R (2004) Container terminal operation and operations researchłłA classification and literature review. OR spectrum 26(1):3–49 Stahlbock R, VoB S (2008) Operations research at container terminals: a literature update. OR spectrum 30(1):1–52 Schepler X, Balev S, Michel S, Sanlaville E (2017) Global planning in a multi-terminal and multi-modal maritime container port. Trans Res Part E: Logist Trans Rev 100:38–62 Ursavas E, Zhu SX (2016) Optimal policies for the berth allocation problem under stochastic nature. Europ J Oper Res 255(2):380–387 Umang N, Bierlaire M, Vacca I (2013) Exact and heuristic methods to solve the berth allocation problem in bulk ports. Trans Res Part E: Logist Trans Rev 54:14–31 Vis IFA, Koster R (2003) Transshipment of containers at a container terminal: an overview. Europ J Oper Res 147(1):1–16 Wang F, Lim A (2007) A stochastic beam search for the berth allocation problem. Decis Support Syst 42:2186–2196 Xu Y, Chen Q, Quan X (2012) Robust berth scheduling with uncertain vessel delay and handling time. Ann Oper Res 192(1):123–140 Yu CS, Li HL (2000) A robust optimization model for stochastic logistic problems. Int J Prod Econ 64(1):385–397 Zhang C, Zheng L, Zhang Zh, Shi L, Armstrong AJ (2010) The allocation of berths and quay cranes by using a sub-gradient optimization technique. Comput Ind Eng 58(1):40–50 Zhen L, Chang D (2012) A bi-objective model for robust berth allocation scheduling. Comput Ind Eng 63:262–273 Zhen L, Chew EP, Lee LH (2011a) An integrated model for berth template and yard template planning in transshipment hubs. Trans Sci 45:483–504 Zhen L, Lee LH, Chew EP (2011b) A decision model for berth allocation under uncertainty. Europ J Oper Res 212:54–68 Zhen L (2014) Container yard template planning under uncertain maritime market. Trans Res Part E Logist Trans Rev 69:199–217 Zhen L (2015) Tactical berth allocation under uncertainty. Europ J Oper Res 247:928–944 Zhen L, Wang S, Wang K (2016) Terminal allocation problem in a transshipment hub considering bunker consumption. Naval Research Logistics, Hoboken Zhou P, Kang H, Lin L (2006) A dynamic berth allocation model based on stochastic consideration. In: The sixth world congress on intelligent control and automation, WCICA 2006. Vol.2, pp. 7297–7301. IEEE Xplore Zhou PF, Kang HG (2008) Study on berth and quay-crane allocation under stochastic environments in container terminal. Syst Eng Theory & Practice 28(1):161–169