\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Integrated proactive-reactive approach and a hybrid adaptive large neighborhood search algorithm for berth and quay crane scheduling under uncertain combination

  • *Corresponding author: Jin Zhu

    *Corresponding author: Jin Zhu

The first author is supported by Shanghai Pujiang Program (16PJC043)

Abstract / Introduction Full Text(HTML) Figure(6) / Table(7) Related Papers Cited by
  • The integrated berth and quay crane scheduling problem is frequently encountered in port management issue, and the dynamic random data obtained by the container terminals under uncertain combination usually makes it unworkable to execute the scheduling. To promote sustainability and adaptivity of container terminals, this paper focuses on developing an integrated proactive-reactive approach for berth and quay crane scheduling under the fluctuation of vessels' arrival time and breakdown of quay crane. The problem is modelled as a two-stage mixed integer program where the baseline schedule with robustness is established in the first stage, and the recovery schedule is established in the second stage. This study aims to minimize the total management cost deviation and total time deviation of the terminal scheduling, so as to implement minimal changes compared with the baseline schedule. Therefore, the scheduling performance such as robustness, recoverability and adaptability is considered. To solve this model, a hybrid adaptive large neighborhood search (HALNS) algorithm framework combined with variable neighborhood search is developed, and the greedy algorithm is developed to construct the initial feasible solution. The performance evaluation tests of the proposed algorithm are performed on the three scales of benchmark. Computational results indicate the strength of solution methods and effectiveness of the proposed model.

    Mathematics Subject Classification: Primary: 90B06, 90B50; Secondary: 90C27.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An illustration of the baseline schedule model with robustness

    Figure 2.  An illustration of the recovery schedule model

    Figure 3.  The dynamic process of implementing proactive-reaction approach

    Figure 4.  Overall flowchart of HALNS

    Figure 5.  Convergence tendency of GAP(%) between HALNS and ALNS

    Figure 6.  Comparison of average CPU time and average GAP of three algorithms

    Table 1.  Summary of related literatures

    literature Berth property Uncertain combination Strategy Algorithm
    Zhou et al. [43] Discrete AT+OT Proactive GA
    Han et al. [7] Discrete AT+OT Proactive GA
    Rodriguez et al. [24] Continuous AT+OT Proactive Meta-heuristic
    Xiang et al. [36] Discrete AT+QC quantity Proactive Decomposition algorithm (DA)
    Zeng et al. [41] Continuous Disruption events Reactive Local rescheduling and tabu search
    Li et al. [17] Continuous AT+OT Reactive Heuristic
    Xiang et al. [37] Discrete Disruption events Reactive Rolling horizon heuristic
    Iris et al. [12] Continuous AT+QC handling rates Proactive-reactive Heuristic
    Tan et al. [27] Continuous AT+OT Proactive-reactive GA with heuristic
    Our study Continuous AT+breakdown of QC Proactive-reactive Hybrid ALNS
     | Show Table
    DownLoad: CSV

    Table 2.  Parameters for setting instance size.

    Instance size N L Q Planning horizon
    Small-size 18 1200 12 3 days
    20
    Medium-size 30 1800 18 4 days
    34
    Large-size 44 2400 24 5 days
    50
     | Show Table
    DownLoad: CSV

    Table 3.  Vessel's information in the benchmark

    Class Vessel length (m) Handling volume (TEU) Number of QCs can be assigned
    Feeder U[70,200] U[400,600] [1, 2]
    Medium U[210,300] U[1000, 1200] [2, 4]
    Jumbo U[310,400] U[1800, 2400] [4, 6]
     | Show Table
    DownLoad: CSV

    Table 4.  Comparison results

    HALNS ALNS GA
    No N Z OBJ T(s) GAP(%) OBJ T(s) GAP(%) OBJ T(s) GAP(%)
    Large-size 1 18 134.16 {135.73 622 1.17 136.59 521 1.81 140.63 479 4.82
    2 18 122.36 122.42 567 0.05 122.62 491 0.21 128.50 456 5.02
    3 18 142.18 145.35 590 2.23 145.69 582 2.47 149.69 471 5.28
    4 18 107.07 108.70 489 1.52 109.40 495 2.18 110.05 434 2.78
    5 18 134.43 137.43 582 2.30 138.37 469 2.93 143.75 441 6.93
    6 20 123.47 123.87 590 0.32 124.78 547 1.06 127.00 502 2.86
    7 20 122.83 126.31 637 2.83 125.66 563 2.30 129.59 531 5.50
    8 20 156.30 158.27 529 1.26 156.74 499 0.28 164.08 465 4.98
    9 20 107.10 110.56 598 3.23 109.42 546 2.17 110.27 481 2.96
    10 20 133.44 137.32 616 2.91 137.60 542 3.12 141.01 517 5.67
    avg 582 1.78 526 1.85 478 4.68
    Medium-size 1 30 183.24 187.36 1248 2.25 188.98 1133 3.13 195.04 984 6.44
    2 30 194.45 201.74 1147 3.75 203.57 1044 4.69 208.63 970 7.29
    3 30 195.41 199.22 1322 1.95 199.92 1293 2.31 206.27 991 5.56
    4 30 184.96 187.20 1129 1.21 188.16 954 1.73 194.17 838 4.98
    5 30 173.43 178.04 1241 2.66 180.28 1157 3.95 181.84 946 4.85
    6 34 198.97 205.12 1544 3.09 207.98 1427 4.53 212.42 1054 6.76
    7 34 167.02 174.35 1302 4.39 177.26 1003 6.13 181.63 951 8.75
    8 34 213.42 220.72 1353 3.42 223.96 1278 4.94 230.13 836 7.83
    9 34 204.55 212.16 1405 3.72 214.00 1369 4.62 214.51 1152 4.87
    10 34 229.28 239.51 1319 4.46 241.13 1212 5.17 245.95 1098 7.27
    avg 1301 3.09 1187 4.12 982 6.46
    Large-size 1 44 289.20 306.84 2249 6.10 312.36 2387 8.01 338.71 1957 17.12
    2 44 237.32 247.43 2368 4.26 251.04 2283 5.78 283.60 2211 19.50
    3 44 238.21 253.24 2144 6.31 256.62 2489 7.73 278.85 2016 17.06
    4 44 261.24 275.76 2524 5.56 280.75 2396 7.47 308.42 1962 18.06
    5 44 338.41 349.00 2485 3.13 359.49 2378 6.23 396.08 2027 17.04
    6 50 353.96 372.54 2621 5.25 383.76 2474 8.42 423.23 2283 19.57
    7 50 263.45 283.50 2752 7.61 287.69 2477 9.20 310.77 2403 17.96
    8 50 343.36 361.25 2519 5.21 371.55 2456 8.21 398.61 2236 16.09
    9 50 370.09 380.64 2910 2.85 390.78 2849 5.59 425.64 2261 15.01
    10 50 246.81 265.37 2783 7.52 268.21 2711 8.67 283.41 2284 14.83
    avg 2536 5.38 2490 7.53 2164 17.22
     | Show Table
    DownLoad: CSV

    Table 5.  Performance of the proposed model

    Instance size Costs and efficiency Robustness Recoverability
    Total management cost of terminal Average operation Time for a vessel Average time deviation for a vessel The operating cost of QCs Average buffer time for a vessel The Number of rescheduled vessels
    20 416.23 8.51 3.21 93.61 8.02 3.25
    20 528.74 8.05 2.73 96.19 7.53 2.60
    20 445.03 9.10 3.61 88.23 8.25 3.29
    20 377.20 8.42 2.88 93.52 7.32 1.83
    20 401.56 8.27 3.27 88.23 8.14 3.18
    Avg 433.75 8.47 3.14 92.39 7.85 2.83
    30 585.32 8.90 3.59 219.02 5.71 5.39
    30 615.37 8.39 3.28 200.96 5.98 4.61
    30 549.75 9.05 3, 12 201.79 6.22 5.65
    30 608.15 8.63 3.03 206.00 5.56 5.87
    30 538.17 8.50 3.47 215.08 6.38 5.93
    Avg 579.35 8.69 3.30 208.57 5.97 5.49
    50 862.37 8.43 3.84 482.95 4.80 9.25
    50 878.68 8.61 3.07 458.19 4.58 9.51
    50 975.12 8.09 3.92 501.41 4.02 9.98
    50 938.42 9.23 3.23 465.80 4.34 8.50
    50 802.21 8.91 3.78 450.75 5.11 9.46
    Avg 891.36 8.65 3.57 471.82 4.57 9.34
     | Show Table
    DownLoad: CSV

    Table 6.  Impact of uncertainty degree $ \Delta B $

    Instance size $ \Delta B $ $ P_a $ Our model Rescheduling model
    $ C I $ ADP of CI $ T I $ ADP of TI $ C I $ ADP of CI $ T I $ ADP of TI
    2 50% 178.32 1.94 181.70 2.61
    20 4 30% 216.00 219.33 2.47 2.28 253.14 248.09 3.04 2.96
    6 15% 293.27 2.76 361.51 3.58
    8 5% 427.51 3.11 541.34 4.21
    2 50% 255.30 1.55 263.21 2.82
    30 4 30% 281.35 298.73 2.63 2.19 332.75 321.16 3.23 3.15
    6 15% 353.26 3.08 407.10 3.71
    8 5% 473.72 3.23 573.28 4.33
    2 50% 301.24 1.89 357.51 3.17
    50 4 30% 392.53 365.60 2.53 2.33 442.38 428.34 3.82 3.61
    6 15% 462.10 2.96 552.73 4.20
    8 5% 558.12 3.72 679.25 4.92
     | Show Table
    DownLoad: CSV

    Table 7.  Impact of uncertainty degree $ t_d $

    Instance size $ t_d $ $ P_b $ Our model Rescheduling model
    $ C I $ ADP of CI $ T I $ ADP of TI $ C I $ ADP of CI $ T I $ ADP of TI
    5 20% 175.31 1.41 211.05 2.36
    20 15 60% 248.70 265.79 1.98 1.92 295.26 312.60 4.78 4.82
    25 20% 407.52 2.23 466.17 7.39
    5 20% 213.65 1.58 256.30 2.62
    30 15 60% 286.21 305.42 2.02 2.08 347.52 364.49 5.15 5.22
    25 20% 454.84 2.77 523.60 8.02
    5 20% 285.30 1.86 334.73 3.20
    50 15 60% 352.63 371.39 2.46 2.44 445.80 451.90 6.14 6.23
    25 20% 513.74 2.97 587.35 9.52
     | Show Table
    DownLoad: CSV
  • [1] Ö. Ş. Akpunar and Ş. Akpinar, A hybrid adaptive large neighbourhood search algorithm for the capacitated location routing problem, Expert Systems with Applications, 168 (2021), 114304.  doi: 10.1016/j.eswa.2020.114304.
    [2] C. Bierwirth and F. Meisel, A follow-up survey of berth allocation and quay crane scheduling problems in container terminals, European Journal of Operational Research, 244 (2015), 675-689.  doi: 10.1016/j.ejor.2014.12.030.
    [3] J. H. ChenD.-H. Lee and J. X. Cao, A combinatorial benders' cuts algorithm for the quayside operation problem at container terminals, Transportation Research Part E: Logistics and Transportation Review, 48 (2012), 266-275.  doi: 10.1016/j.tre.2011.06.004.
    [4] S. W. ChoH. J. Park and C. Lee, An integrated method for berth allocation and quay crane assignment to allow for reassignment of vessels to other terminals, Maritime Economics & Logistics, 23 (2021), 123-153.  doi: 10.1057/s41278-020-00173-4.
    [5] E. DemirT. Bektaş and G. Laporte, An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research, 223 (2012), 346-359.  doi: 10.1016/j.ejor.2012.06.044.
    [6] M. GoliasI. PortalD. KonurE. Kaisar and G. Kolomvos, Robust berth scheduling at marine container terminals via hierarchical optimization, Computers & Operations Research, 41 (2014), 412-422.  doi: 10.1016/j.cor.2013.07.018.
    [7] X.-l. HanZ.-q. Lu and L.-f. Xi, A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time, European Journal of Operational Research, 207 (2010), 1327-1340. 
    [8] J. HeC. TanW. YanW. HuangM. Liu and H. Yu, Two-stage stochastic programming model for generating container yard template under uncertainty and traffic congestion, Advanced Engineering Informatics, 43 (2020), 101032.  doi: 10.1016/j.aei.2020.101032.
    [9] M. HendriksM. LaumannsE. Lefeber and J. T. Udding, Robust cyclic berth planning of container vessels, OR spectrum, 32 (2010), 501-517.  doi: 10.1007/s00291-010-0198-z.
    [10] Q.-M. HuZ.-H. Hu and Y. Du, Berth and quay-crane allocation problem considering fuel consumption and emissions from vessels, Computers & Industrial Engineering, 70 (2014), 1-10.  doi: 10.1016/j.cie.2014.01.003.
    [11] IMF, Global Trade's Recovery Hits Record High, Managing divergent recoveries, Washington, DC, 2021.
    [12] Ç. Iris and J. S. L. Lam, Recoverable robustness in weekly berth and quay crane planning, Transportation Research Part B: Methodological, 122 (2019), 365-389.  doi: 10.1016/j.trb.2019.02.013.
    [13] Ç. IrisD. Pacino and S. Ropke, Improved formulations and an adaptive large neighborhood search heuristic for the integrated berth allocation and quay crane assignment problem, Transportation Research Part E: Logistics and Transportation Review, 105 (2017), 123-147.  doi: 10.1016/j.tre.2017.06.013.
    [14] J. KarafaM. M. GoliasS. IveyG. K. Saharidis and N. Leonardos, The berth allocation problem with stochastic vessel handling times, The International Journal of Advanced Manufacturing Technology, 65 (2013), 473-484.  doi: 10.1007/s00170-012-4186-0.
    [15] C.-Y. Lee and D.-P. Song, Ocean container transport in global supply chains: Overview and research opportunities, Transportation Research Part B: Methodological, 95 (2017), 442-474.  doi: 10.1016/j.trb.2016.05.001.
    [16] H. LiC. ZhouB. K. LeeL. H. LeeE. P. Chew and R. S. M. Goh, Capacity planning for mega container terminals with multi-objective and multi-fidelity simulation optimization, Iise Transactions, 49 (2017), 849-862.  doi: 10.1080/24725854.2017.1318229.
    [17] M. Z. LiJ. G. Jin and C. X. Lu, Real-time disruption recovery for integrated berth allocation and crane assignment in container terminals, Transportation Research Record, 2479 (2015), 49-59.  doi: 10.3141/2479-07.
    [18] C. LiangY. Huang and Y. Yang, A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning, Computers & Industrial Engineering, 56 (2009), 1021-1028.  doi: 10.1016/j.cie.2008.09.024.
    [19] C. LiuL. Zheng and C. Zhang, Behavior perception-based disruption models for berth allocation and quay crane assignment problems, Computers & Industrial Engineering, 97 (2016), 258-275.  doi: 10.1016/j.cie.2016.04.008.
    [20] R. MassonF. Lehuédé and O. Péton, An adaptive large neighborhood search for the pickup and delivery problem with transfers, Transportation Science, 47 (2013), 344-355.  doi: 10.1287/trsc.1120.0432.
    [21] G. R. MauriG. M. RibeiroL. A. N. Lorena and G. Laporte, An adaptive large neighborhood search for the discrete and continuous berth allocation problem, Computers & Operations Research, 70 (2016), 140-154.  doi: 10.1016/j.cor.2016.01.002.
    [22] G. Mejía and F. Yuraszeck, A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times, European Journal of Operational Research, 285 (2020), 484-496.  doi: 10.1016/j.ejor.2020.02.010.
    [23] F. Rodrigues and A. Agra, An exact robust approach for the integrated berth allocation and quay crane scheduling problem under uncertain arrival times, European Journal of Operational Research, 295 (2021), 499-516.  doi: 10.1016/j.ejor.2021.03.016.
    [24] M. Rodriguez-Molins, M. A. Salido and F. Barber, Robust scheduling for berth allocation and quay crane assignment problem, Mathematical Problems in Engineering, 2014 (2014), Art. ID 834927, 17 pp. doi: 10.1155/2014/834927.
    [25] X. T. ShangJ. X. Cao and J. Ren, A robust optimization approach to the integrated berth allocation and quay crane assignment problem, Transportation Research Part E: Logistics and Transportation Review, 94 (2016), 44-65.  doi: 10.1016/j.tre.2016.06.011.
    [26] J. F. SzeS. Salhi and N. Wassan, A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem, Expert Systems with Applications, 65 (2016), 383-397.  doi: 10.1016/j.eswa.2016.08.060.
    [27] C. Tan and J. He, Integrated proactive and reactive strategies for sustainable berth allocation and quay crane assignment under uncertainty, Annals of Operations Research, (2021), 1-32. doi: 10.1007/s10479-020-03891-3.
    [28] G. Tasoglu and G. Yildiz, Simulated annealing based simulation optimization method for solving integrated berth allocation and quay crane scheduling problems, Simulation Modelling Practice and Theory, 97 (2019), 101948.  doi: 10.1016/j.simpat.2019.101948.
    [29] Y. B. TürkoğullarıZ. C. TaşkınN. Aras and İ. K. Altınel, Optimal berth allocation and time-invariant quay crane assignment in container terminals, European Journal of Operational Research, 235 (2014), 88-101.  doi: 10.1016/j.ejor.2013.10.015.
    [30] Y. B. TürkoğullarıZ. C. TaşkınN. Aras and İ. K. Altınel, Optimal berth allocation, time-variant quay crane assignment and scheduling with crane setups in container terminals, European Journal of Operational Research, 254 (2016), 985-1001.  doi: 10.1016/j.ejor.2016.04.022.
    [31] N. UmangM. Bierlaire and A. L. Erera, Real-time management of berth allocation with stochastic arrival and handling times, Journal of Scheduling, 20 (2017), 67-83.  doi: 10.1007/s10951-016-0480-2.
    [32] UNCTAD, Global Trade's Recovery Hits Record High, Global Trade Update, United Nations, New York and Geneva, 2021.
    [33] E. Ursavas and S. X. Zhu, Optimal policies for the berth allocation problem under stochastic nature, European Journal of Operational Research, 255 (2016), 380-387.  doi: 10.1016/j.ejor.2016.04.029.
    [34] K. WangL. ZhenS. Wang and G. Laporte, Column generation for the integrated berth allocation, quay crane assignment, and yard assignment problem, Transportation Science, 52 (2018), 812-834.  doi: 10.1287/trsc.2018.0822.
    [35] Z. Wang and C. Guo, Minimizing the risk of seaport operations efficiency reduction affected by vessel arrival delay, Industrial Management & Data Systems, 118 (2018), 1498-1509.  doi: 10.1108/IMDS-12-2017-0563.
    [36] X. Xiang and C. Liu, An almost robust optimization model for integrated berth allocation and quay crane assignment problem, Omega, 104 (2021), 102455.  doi: 10.1016/j.omega.2021.102455.
    [37] X. XiangC. Liu and L. Miao, Reactive strategy for discrete berth allocation and quay crane assignment problems under uncertainty, Computers & Industrial Engineering, 126 (2018), 196-216.  doi: 10.1016/j.cie.2018.09.033.
    [38] X. XiangC. Liu and L. Miao, A bi-objective robust model for berth allocation scheduling under uncertainty, Transportation Research Part E: Logistics and Transportation Review, 106 (2017), 294-319.  doi: 10.1016/j.tre.2017.07.006.
    [39] Y. XuQ. Chen and X. Quan, Robust berth scheduling with uncertain vessel delay and handling time, Annals of Operations Research, 192 (2012), 123-140.  doi: 10.1007/s10479-010-0820-0.
    [40] H. YangV. LowC. ZhangL. Zheng and L. Miao, Behaviour perception-based disruption models for the parallel machine capacitated lot-sizing and scheduling problem, International Journal of Production Research, 55 (2017), 3058-3072.  doi: 10.1080/00207543.2016.1234083.
    [41] Q. ZengZ. Yang and X. Hu, Disruption recovery model for berth and quay crane scheduling in container terminals, Engineering Optimization, 43 (2011), 967-983.  doi: 10.1080/0305215X.2010.528411.
    [42] L. Zhen and D.-F. Chang, A bi-objective model for robust berth allocation scheduling, Computers & Industrial Engineering, 63 (2012), 262-273.  doi: 10.1016/j.cie.2012.03.003.
    [43] P.-f. Zhou and H.-g. Kang, Study on berth and quay-crane allocation under stochastic environments in container terminal, Systems Engineering-Theory & Practice, 28 (2008), 161-169.  doi: 10.1016/S1874-8651(09)60001-6.
    [44] I. ŽuljS. Kramer and M. Schneider, A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem, European Journal of Operational Research, 264 (2018), 653-664.  doi: 10.1016/j.ejor.2017.06.056.
  • 加载中

Figures(6)

Tables(7)

SHARE

Article Metrics

HTML views(2010) PDF downloads(199) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return