Rescheduling optimization of ships and berths at hub ports during short-term channel closures
Article Text (Baidu Translation)
-
摘要: 为灵活应对枢纽港短暂封航事件的冲击，研究了集装箱枢纽港船舶调度与泊位分配协同优化问题。首先针对某一个拥有单向航道的集装箱枢纽港，重点考虑航道内不确定性事件引发部分时段航道封闭的情况，同时考虑预期抵港干支线船舶的抵达信息变动对船舶调度与泊位分配的影响，提出应对不同场景的再调度决策机制；兼顾单向航道进出港时段限制及干支线转运衔接作业的时间约束，构建了以船舶总服务成本及未完成集运的支线船舶惩罚成本之和最小为优化目标的数学模型；针对模型特点设计了融入变邻域搜索思想的改进遗传算法，考虑到实际调度中的船舶进出港次序重组或局部调整的情况，分别设计了Cross算子、2-opt算子和Or-opt算子，为避免陷入局部最优，结合变邻域搜索的思想随机选择算子进行邻域搜索替代传统遗传算法中的交叉变异操作；为增加种群多样性，算法还设置了干扰规则，以防止搜索过程中出现早期收敛现象，设计并开展了多组不同规模的船舶算例试验。研究结果表明：相较于先到先服务方案和仅考虑泊位分配方案，通过文中模型和算法获得的船舶与泊位最佳的再调度方案可使总费用分别降低28.56%和11.78%，且该算法的求解效率优于和声搜索算法与免疫遗传算法；封航时段长度与封航时机均会对总目标造成影响，但封航时机对总目标的影响更为显著。研究成果可为港口提供一定的决策支持。Abstract: To flexibly respond to the impact of short-term closure events at hub ports, the coordinated optimization of ship scheduling and berth allocation at container hub ports was investigated. By focusing on a container hub port with a one-way channel, uncertainty events within the channel that caused partial closures during certain periods were primarily considered. The impact of variations in the expected arrival information of feeder and mainline ships on ship scheduling and berth allocation was taken into account, and a rescheduling decision mechanism was proposed to deal with different scenarios. Both the time constraints imposed by the arrival and departure schedules of the one-way channel and the time required for feeder-to-mainline transshipment operations were considered, and a mathematical model that minimized the sum of the total service cost of the ships and the penalty costs for uncompleted transshipment of feeder ships was constructed. Next, an improved genetic algorithm incorporating the variable neighborhood search (VNS) approach was designed based on the model characteristics. In consideration of the reordering of ship arrival and departure sequences and local adjustments in the actual scheduling process, Cross, 2-opt, and Or-opt operators were designed. To avoid local optima, the operators were randomly selected for neighborhood search based on the ideas of VNS to replace the traditional crossover and mutation operations in genetic algorithms. To enhance population diversity and prevent premature convergence in the search process, interference rules were also incorporated into the algorithm. Finally, multiple sets of ship scheduling case studies of different scales were conducted. The results show that compared to the first-come and first-served strategy and the scheme that only considers berth allocation, the optimal ship and berth resheduling plans obtained by the model and algorithm in this study can reduce the total cost by 28.56% and 11.78%, respectively. The solving efficiency of the algorithm is superior to that of the harmony search algorithm and the immune genetic algorithm. Both the duration and timing of closures affect the total cost, with the timing having a more significant impact. These findings provide valuable decision-making support for port operations.
-
表 1 染色体结构示意
Table 1. Schematic of chromosome structure
进港次序 1 2 3 4 5 6 7 8 9 10 首次靠泊泊位 5 2 7 4 4 5 2 7 1 2 移泊场景 0 0 0 0 0 0 0 0 1 0 移泊后靠泊泊位 5 2 7 4 4 5 2 7 7 2 首次靠泊时刻/刻 6 15 24 56 67 62 73 94 96 110 离泊时刻/刻 92 76 65 102 96 85 127 170 172 145 出港次序 4 2 1 6 5 3 7 9 10 8 
下载: 导出CSV
表 2 计划期内的船舶信息
Table 2. Ship information during the planning period
船舶编号 船舶类型 船长/m 预计到港时间/刻 装船作业时间/刻 卸船作业时间/刻 转运时间窗下界/刻 转运时间窗上界/刻 1 0 180 4 44 72 3 132 2 0 200 16 12 60 17 107 3 0 160 24 40 48 48 149 4 0 190 36 28 66 51 157 5 0 240 52 36 40 59 137 6 0 195 60 36 42 56 155 7 1 200 76 24 30 8 1 260 96 48 56 9 0 180 104 48 40 148 241 10 1 260 124 36 56 11 0 200 132 60 36 143 254 12 0 180 136 60 20 147 246 13 0 200 152 28 44 152 239 14 0 160 172 24 40 187 270 15 0 200 180 32 44 195 285
下载: 导出CSV
表 3 船舶信息变动场景
Table 3. Ship information variation scenarios
船舶编号 船舶型号 船长/m 预计到港时间/刻 装船作业时间/刻 卸船作业时间/刻 转运时间窗下界/刻 转运时间窗上界/刻 4 0 190 42 28 66 51 157 6 0 195 72 36 42 56 155 9 0 180 104 48 34 148 241 11 0 200 132 50 36 143 254
下载: 导出CSV
表 4 封航场景
Table 4. Port closure scenarios
时间/刻 原航道进出港类型 变动后航道进出港类型 35 0 0 36 0 0 37 0 0 38 0 2 $ \vdots$ 0 2 48 0 2 49 1 2 50 1 2 $ \vdots$ 1 2 61 1 2 62 1 1 63 1 1 注：“0”表示出港时段，“1”表示进港时段，“2”表示该时段航道封航。
下载: 导出CSV
表 5 进出港时刻
Table 5. Arrival and departure times
船舶编号 到锚地时刻/刻 进港时刻/刻 靠泊时刻/刻 离泊时刻/刻 出港时刻/刻 1 4 6 12 128 130 2 16 18 24 96 121 3 24 62 68 156 171 4 42 64 70 164 166 5 52 66 72 148 169 6 72 97 114 194 217 7 76 99 105 159 173 8 96 101 107 211 219 9 104 106 151 233 235 10 124 145 151 243 267 11 132 147 153 241 265 12 136 149 158 238 240 13 152 154 161 233 237 14 172 193 199 263 269 15 180 195 201 277 279
下载: 导出CSV
表 6 方案有效性分析
Table 6. Solution validity analysis
序号 算例规模/艘 船舶变动数量/艘 封航时段/刻 目标函数值/元 方案结果对比 方案1 方案2 方案3 GAP1/% GAP2/% 1 10 1 93 360 79 600 75 200 24.15 5.85 2 10 2 101 560 83 600 76 720 32.38 8.97 3 10 1 13~20 115 480 97 440 80 440 43.56 21.13 4 20 2 211 200 191 600 188 400 12.10 1.70 5 20 4 48~64 248 800 218 720 201 200 23.66 8.71 6 20 2 48~72 287 120 253 600 217 720 31.88 16.48 7 30 5 48~72 389 000 354 000 325 200 19.62 8.86 8 30 7 40~72 482 000 429 800 370 400 30.13 16.04 9 30 6 40~72 547 000 463 700 392 000 39.54 18.29 平均值 275 058 241 340 214 142 28.56 11.78
下载: 导出CSV
表 7 算法有效性分析
Table 7. Algorithm validity analysis
船舶数量/ 艘 变动船舶数量/艘 封航时段/ 刻 目标函数值/元 目标函数值相对误差/% 运行时长/s 本文算法 Gurobi 本文算法 Gurobi 10 1 56~64 74 290 74 290 0.00 3.84 1.06 12 1 56~72 95 910 95 910 0.00 5.86 2.04 14 1 80~96 105 110 105 110 0.00 6.55 4.68 16 2 80~96 127 200 126 500 0.55 8.47 6.78 18 2 80~96 159 490 158 580 0.57 11.76 9.77 20 2 80~96 181 240 172 500 4.82 14.80 29.77 22 3 96~108 212 400 203 090 4.38 25.34 71.83 24 2 96~108 242 580 231 840 4.43 44.97 294.45 26 3 96~108 261 470 249 090 4.73 78.53 3 505.26 28 4 96~108 283 130 286 470 -1.18 104.65 5 000.00 30 4 96~108 308 890 329 600 -6.70 136.76 5 000.00 32 5 108~120 336 250 357 720 -6.39 192.43 5 000.00 34 5 108~120 356 910 374 080 -4.81 269.59 5 000.00 36 5 108~120 384 680 405 160 -5.32 357.44 5 000.00
下载: 导出CSV
表 8 算法优越性分析
Table 8. Algorithm superiority analysis
船舶数量/ 艘 变动船舶数量/艘 封航时段/ 刻 目标函数值/元 GAP1/ % GAP2/ % 求解时长/s 本文算法 和声搜索算法 免疫遗传算法 本文算法 和声搜索算法 免疫遗传算法 10 1 56~80 74 290 74 290 74 290 0.00 0.00 3.84 2.13 3.89 12 1 56~80 95 910 95 910 95 910 0.00 0.00 5.86 4.26 6.12 14 1 56~80 105 110 105 110 105 110 0.00 0.00 6.55 6.48 6.89 16 2 56~80 127 200 127 200 127 200 0.00 0.00 8.47 8.82 9.33 18 2 96~108 159 490 159 870 159 490 0.24 0.00 11.76 12.49 12.58 20 2 96~108 181 240 184 680 182 350 1.86 0.61 14.80 16.37 17.23 22 3 96~108 216 400 219 650 217 540 1.48 0.53 25.34 29.52 32.66 24 2 96~108 242 580 247 390 244 500 1.94 0.79 44.97 48.73 52.32 26 3 96~108 261 470 266 640 264 870 1.94 1.30 78.53 82.39 87.45 28 4 108~120 283 130 287 870 283 900 1.65 0.27 104.65 110.52 115.27 30 4 108~120 308 890 314 280 311 360 1.72 0.80 136.76 147.88 159.61 32 5 108~120 336 250 342 820 340 400 1.92 1.23 192.43 204.65 230.23 34 5 108~120 356 910 364 790 361 390 2.16 1.26 269.59 295.43 321.26 36 5 108~120 384 680 393 410 389 800 2.22 1.33 357.44 401.25 437.35
下载: 导出CSV
-
[1] JIA Shuai, LI Chung-Lun, XU Zhou. A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port[J]. Transportation Research Part B: Methodological, 2020, 142: 174-196. doi: 10.1016/j.trb.2020.10.007 [2] 盛小曼, 刘旭, 廖川. 长江干线船舶水上交通事故分析与对策研究[J]. 水上安全, 2023(2): 50-53, 65.SHENG Xiao-man, LIU Xu, LIAO Chuan. Analysis and countermeasure research on water traffic accidents of ships in Yangtze River trunk line[J]. Maritime Safety, 2023(2): 50-53, 65. [3] ZHANG Xin-yu, LIN Jun, GUO Zi-jian, et al. Vessel transportation scheduling optimization based on channel-berth coordination[J]. Ocean Engineering, 2016, 112: 145-152. doi: 10.1016/j.oceaneng.2015.12.011 [4] LIU Dong-dong, SHI Guo-you, KANG Zhen. Fuzzy scheduling problem of vessels in one-way waterway[J]. Journal of Marine Science and Engineering, 2021, 9(10): 1064. doi: 10.3390/jmse9101064 [5] 郑红星, 刘保利, 王泽浩, 等. 考虑潮汐的多港池港口船舶调度优化[J]. 系统工程理论与实践, 2018, 38(10): 2638-2651.ZHENG Hong-xing, LIU Bao-li, WANG Ze-hao, et al. Ship scheduling optimization in multi-harbor basin port considering tidal influence[J]. Systems Engineering-Theory and Practice, 2018, 38(10): 2638-2651. [6] ZHANG Xin-yu, LI Rui-jie, CHEN Xiang, et al. Multi-object-based vessel traffic scheduling optimisation in a compound waterway of a large harbour[J]. Journal of Navigation, 2019, 72(3): 609-627. doi: 10.1017/S0373463318000863 [7] HILL A, LALLA-RUIZ E, VOß S, et al. A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem[J]. Journal of Scheduling, 2019, 22(2): 173-182. doi: 10.1007/s10951-018-0578-9 [8] DU Yu-quan, CHEN Qiu-shuang, QUAN Xiong-wen, et al. Berth allocation considering fuel consumption and vessel emissions[J]. Transportation Research Part E: Logistics and Transportation Review, 2011, 47(6): 1021-1037. doi: 10.1016/j.tre.2011.05.011 [9] YAN Shang-yao, LU Chung-cheng, HSIEH J H, et al. A network flow model for the dynamic and flexible berth allocation problem[J]. Computers & Industrial Engineering, 2015, 81: 65-77. [10] LU Zhen, ZHE Liang, ZHUGE Dan, et al. Daily berth planning in a tidal port with channel flow control[J]. Transportation Research Part B: Methodological, 2017, 106: 193-217. doi: 10.1016/j.trb.2017.10.008 [11] 郑红星, 刘保利, 张润, 等. 考虑减载移泊的散货港口船舶调度优化[J]. 交通运输工程学报, 2018, 18(5): 152-164. doi: 10.19818/j.cnki.1671-1637.2018.05.015ZHENG Hong-xing, LIU Bao-li, ZHANG Run, et al. Ship scheduling optimization on bulk cargo port considering ship lightening and berth shifting[J]. Journal of Traffic and Transportation Engineering, 2018, 18(5): 152-164. doi: 10.19818/j.cnki.1671-1637.2018.05.015 [12] TAN Cai-mao, HE Jun-liang, WANG Yu, et al. Berth template management for the container port of waterway-waterway transit[J]. Advanced Engineering Informatics, 2023, 58: 102151. doi: 10.1016/j.aei.2023.102151 [13] URSAVAS E, ZHU S X. Optimal policies for the berth allocation problem under stochastic nature[J]. European Journal of Operational Research, 2016, 255(2): 380-387. doi: 10.1016/j.ejor.2016.04.029 [14] LV Ya-qiong, ZOU Ming-kai, LI Jun, et al. Dynamic berth allocation under uncertainties based on deep reinforcement learning towards resilient ports[J]. Ocean & Coastal Management, 2024, 252: 107113. [15] LIU Bao-li, LI Zhi-chun, SHENG Dian, et al. Integrated planning of berth allocation and vessel sequencing in a seaport with one-way navigation channel[J]. Transportation Research Part B: Methodological, 2021, 143: 23-47. doi: 10.1016/j.trb.2020.10.010 [16] XU Ya, XUE Ke-lei, DU Yu-quan. Berth scheduling problem considering traffic limitations in the navigation channel[J]. Sustainability, 2018, 10(12): 4795. doi: 10.3390/su10124795 [17] 牛猛, 王钟逸, 李亚军, 等. 考虑使用优先权的泊位分配和船舶调度集成优化[J]. 高技术通讯, 2020, 30(9): 972-981.NIU Meng, WANG Zhong-yi, LI Ya-jun, et al. Berth allocation and ship scheduling integrated optimization considering the priority of berth in use[J]. Chinese High Technology Letters, 2020, 30(9): 972-981. [18] LIU Bao-li, LI Zhi-chun, WANG Ya-dong, et al. Short-term berth planning and ship scheduling for a busy seaport with channel restrictions[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 154: 102467. doi: 10.1016/j.tre.2021.102467 [19] LIU Guo-wei, REN Hong-xiang, XU Fu-quan, et al. Application of improved NSGA-Ⅱ algorithm in ship entry and exit dispatching[C]//IEEE. 12th International Conference on Software Engineering and Service Science (ICSESS). New York: IEEE, 2021: 277-281. [20] 郑红星, 姜雪, 段爽. 考虑减载移泊的散货港口泊位与船舶集成调度[J]. 高技术通讯, 2020, 30(4): 424-434.ZHENG Hong-xing, JIANG Xue, DUAN Shuang. Bulk port berth and ship integrated scheduling considering load shedding[J]. Chinese High Technology Letters, 2020, 30(4): 424-434. [21] LIU Bao-li, LI Zhi-chun, WANG Ya-dong. A two-stage stochastic programming model for seaport berth and channel planning with uncertainties in ship arrival and handling times[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 167: 102919. doi: 10.1016/j.tre.2022.102919 [22] EMDE S, BOYSEN N. Berth allocation in container terminals that service feeder ships and deep-sea vessels[J]. Journal of the Operational Research Society, 2016, 67(4): 551-563. doi: 10.1057/jors.2015.78 [23] JIN Jian-gang, MENG Qiang, WANG Hai. Feeder vessel routing and transshipment coordination at a congested hub port[J]. Transportation Research Part B: Methodological, 2021, 151: 1-21. doi: 10.1016/j.trb.2021.07.002 [24] 杨海宴, 王淑营. 变邻域遗传算法在车间物流调度中的应用[J]. 计算机系统应用, 2021, 30(12): 288-298.YANG Hai-yan, WANG Shu-ying. Application of variable neighborhood genetic algorithm in workshop logistics scheduling[J]. Computer Systems and Applications, 2021, 30(12): 288-298. [25] 郑红星, 徐海栋, 刘保利, 等. 单向航道船舶进港次序与泊位分配协同优化[J]. 运筹与管理, 2017, 26(9): 37-45.ZHENG Hong-xing, XU Hai-dong, LIU Bao-li, et al. One-way channel ship inbound order and berth allocation collaborative optimization[J]. Operations Research and Management Science, 2017, 26(9): 37-45. -
点击查看大图
图(12) / 表(8)
计量
- 文章访问数: 350
- HTML全文浏览量: 56
- PDF下载量: 18
- 被引次数: 0
