Collaborative Optimization of Continuous Berth Allocation and Shore Power Scheduling via a Q-Learning-Based Selection Hyper-Heuristic
-
摘要: 不考虑船岸接口兼容性和船舶接电功率上浮的连续泊位与岸电协同调度方法, 难以准确反映船舶实际岸电接入条件, 从而影响调度方案的可行性。为提高协同调度方案对实际接入条件的适应能力, 研究了船舶接电功率不确定性下的连续泊位与岸电协同调度优化问题。以连续泊位分配时空不重叠、岸电覆盖、船岸接口兼容和岸电供电容量上限等限制条件为约束, 综合考虑码头运营效率、能源使用成本、岸电接入条件和碳排放等因素, 构建以综合成本最小化为目标的混合整数规划模型。针对船舶接电功率上浮不确定性, 引入鲁棒预算对岸电供电容量上限约束进行线性鲁棒化处理, 形成鲁棒优化模型。为高效求解该问题, 提出基于Q学习的选择型超启发式算法(Q-learning-based selection hyper-heuristic algorithm, QLSHH), 采用混合编码表示船舶靠泊位置与岸电接入决策, 超启发式的高层通过Q学习动态选择底层启发式算子, 底层集成8种功能互补的搜索算子, 并设计结构化解码机制以满足复杂约束要求。算例实验表明, 小规模算例中QLSHH平均目标函数值相对Gurobi精确求解的偏差为0.1%~5.0%；中大规模算例中, 相较遗传算法与自适应大邻域搜索算法, QLSHH分别可降低综合成本4.12%~11.65%和3.75%~25.33%, 且平均岸电使用率保持在90%~95.41%。鲁棒性分析表明, 鲁棒预算增加可降低岸电使用率并推升综合成本, 岸电供电容量上限提升可提高岸电使用率并降低成本, 但超过4500 kW后边际效益明显递减。因此, 岸电供电容量配置应在既定鲁棒预算下, 结合实际用电需求合理确定。Abstract: This study addresses the joint scheduling of continuous berth allocation and shore power connection under uncertainty in ships' power demand. A mixed-integer programming model is formulated to minimize the total cost. The model considers non-overlapping spatiotemporal berth occupation, shore power coverage, ship-shore interface compatibility, and shore power capacity constraints. An uncertainty budget is introduced to reformulate the capacity constraint into a linear robust counterpart. A Q-learning-based selection hyper-heuristic algorithm (QLSHH) is proposed. A hybrid encoding scheme represents berthing positions and shore power decisions. Q-learning dynamically selects low-level heuristic operators, and eight complementary operators are integrated with a structured decoding mechanism. For small-scale instances, the average deviation of QLSHH from the exact solutions of Gurobi ranges from 0.1% to 5.0%. For medium and large-scale instances, QLSHH reduces the total cost by 4.12%-11.65% compared with a genetic algorithm (GA). It outperforms an adaptive large neighborhood search algorithm (ALNS) by 3.75%-25.33%. The average shore power utilization rate remains between 90% and 95.41%. As the uncertainty budget increases, the shore power utilization rate decreases and the total cost increases. A higher shore power capacity limit improves the utilization rate and reduces the total cost. However, the marginal benefit diminishes when the capacity exceeds approximately 4 500 kW. Therefore, the capacity should be configured according to practical electricity demand under a given uncertainty budget.
-
Key words:
- logistics engineering /
- berth scheduling /
- shore power management /
- power uncertainty /
- hyper-heuristic /
- Q-learning
-
图 6 鲁棒预算$ \varGamma $对综合成本与岸电使用率的影响
Figure 6. Impact of robust budget $ \varGamma $ on comprehensive cost and shore power utilization rate
图 7 岸电供电容量上限$ P_{\text {max}} $对综合成本与岸电使用率的影响
Figure 7. Impact of shore power capacity $ P_{\text {max}} $ on comprehensive cost and shore power utilization rate
图 8 鲁棒预算$ \varGamma $与岸电容量$ P_{\text {max}} $对综合成本影响的三维响应面图
Figure 8. Three-dimensional impact of robust budget $ \varGamma $ and shore power capacity $ P_{\text {max}} $ on comprehensive cost
表 1 参数符号定义
Table 1. Notation and parameter definitions
符号类别 符号 含义 符号类别 符号 含义 集合 Ⅰ 待服务船舶集合；$ I_{\mathrm{Y}} $为改造船, $ I_{\mathrm{E}} $为船岸接口不兼容的船舶；$ I_{\mathrm{N}} $为未改造船；$ I=I_{\mathrm{Y}} \cup I_{\mathrm{N}}, I_{\mathrm{E}} \subseteq I_{\mathrm{Y}} $ 参数 $ N_{k} $ k类船岸接口兼容装置的总数量 $ T $ 调度时段内的离散时间步集合 $ C^{\mathrm{ft}} $ 改造船岸电未接入调度成本 $ K $ 兼容装置类型的集合 $ \eta $ 单位时间岸电未接入调度成本系数 B 泊位段集合；$ B_{\mathrm{Y}} $为岸电覆盖段；$ B_{\mathrm{N}} $为非岸电覆盖段；$ B=B_{\mathrm{Y}} \cup B_{\mathrm{N}} $ $ C^{\mathrm{cp}} $ 船舶辅助发电机的污染物排放总成本 $ U $ $ \xi_{i t} $的预算不确定集 $ \omega $ 污染物排放系数 参数 $ L $ 岸线总长度 $ \varphi $ 船舶辅助发电机的污染物单位排放成本 $ l_{i} $ 船舶$ i $长度 $ P_{\max} $ 岸电供电容量上限 $ C^{\mathrm{cw}} $ 船舶等待成本 M 1个足够大的正数 $ C^{\text {int}} $ 能源使用成本 $ \tilde{P}_{i t} $ 船舶$ i $在时段t的实际功率需求 $ a_{i} $ 船舶$ i $到港时间 $ \hat{P}_{i} $ 船舶$ i $功率需求的最大上偏差 $ f_{i} $ 船舶$ i $预计离港时间 $ \xi_{i t} $ 标准化扰动系数 $ b^{\prime}{}_{i} $ 船舶$ i $期望靠泊位置 $ \varGamma $ 鲁棒预算参数 $ C_{i}^{\mathrm{p}} $ 船舶$ i $偏离偏好泊位成本 变量 $ e_{i} $ 船舶$ i $离港时间 $ C_{i}^{\mathrm{M}} $ 船舶$ i $锚地等待成本 $ x_{i j}$ 0-1变量, xij = 1时船舶$ i $在船舶$ j $的左侧位置，否则xij = 0 $ C_{i}^{Z} $ 船舶i滞期成本 yij 0-1变量, yij=1时船舶i工作结束时船舶j开始工作, 否则yij=0 CE 单位时间电价 zt 与鲁棒预算Γ对应的辅助变量 CD 柴油成本单价 Nit 鲁棒等价模型中的派生偏差上界量 $ W_{i}^{\rm E} $ 船舶i单位时间用电量 δint 0-1变量, δint=1时船舶i在t时停靠岸电覆盖段n上使用岸电, 否则δint=0 $ W_{i}^{\rm D} $ 船舶i单位时间柴油消耗量 Sik 0-1变量, Sik=1时船舶i与k类船岸接口兼容装置适配, 否则Sik=0 ψ 船舶辅机负载系数 vit 船舶i在时段t的功率偏差辅助变量 Pi 船舶i的辅助发电机功率 决策变量 si 船舶i开始靠泊时间 $ t_{i}^{b} $ 船舶i的在泊作业时长 oi 0-1变量, oi=1时船舶i在泊位工作期间由岸电提供用电, 否则oi=0 Ri 船舶i的辅机柴油消耗率 αin 0-1变量, αin=1时船舶i分配到岸电覆盖段n, 否则αin=0 CO 船岸接口兼容装置操作的单位时间成本 bi 船舶i的靠泊位置 $ t_{k}^{\rm A} $ k类船岸接口兼容装置的额外操作时间 uik 0-1变量, 当uik=1, 表示船舶i在泊期间使用了k类船岸接口兼容装置, 否则uik=0 $ C_{k}^{\rm A} $ k类船岸接口兼容装置使用成本 
下载: 导出CSV
表 2 底层算子库分类与功能描述
Table 2. Classification and functional description of the low-level operators
类别 算子名称 功能描述 探索类 随机交换扰动 双船编码交换, 实现结构扰动 开发类 自适应位置扰动 部分位置基因随机扰动, 扰动步长随迭代递减 全局反向学习 全部位置基因互补映射, 形成全局跳转搜索 偏好导向位置精炼 沿期望靠泊位置方向进行定向位置修正 岸电接入协同优化 以岸电决策调整为主, 位置小范围协同微调 小邻域联合搜索 局部邻域内联合调整位置与岸电决策并择优更新 修复类 编码一致性修复 位置基因截断与无效岸电决策修正 多样性类 多基因随机重置 部分编码重新采样, 恢复种群差异性
下载: 导出CSV
表 3 算例生成规则
Table 3. Generation rules of test cases
参数名称 取值范围 说明 船舶长度/m [150, 350] 船舶在连续泊位上的占用长度 到港时间 00：00-24：00 均匀分布 装卸时间/min [160, 520] 船舶在泊作业时长 功率/kW [1 200, 3 200] 船舶辅机发电机额定功率 偏好位置/m 岸线坐标范围 随机生成 偏离成本/元 [4, 14] 偏离期望泊位的单位成本 滞期成本/元 [11, 41] 超出计划离港时间的惩罚成本 岸电改造状态 是/否 约50%比例设定 船岸兼容接口类型 Ⅰ类/Ⅱ类 船岸接口兼容性需求
下载: 导出CSV
表 4 小规模算例下QLSHH与Gurobi求解结果对比
Table 4. Comparison of solution results between QLSHH and Gurobi for small-scale test cases
算例规模 Gurobi QLSHH 最优目标值/元 岸电使用率/% 求解时间/s 最优目标值/元 平均目标值/元 平均岸电使用率/% 求解时间/s 平均相对偏差/% 5 36697.55 66.67 11.30 36711.04 36745.92 66.67 15.48 0.1 7 45993.59 50.00 23.26 46178.24 47565.46 57.50 18.70 3.4 10 70137.20 83.33 28.60 70193.93 72030.94 73.33 26.37 2.7 12 83242.78 85.71 60.42 84594.41 86418.45 87.14 33.91 3.8 15 105535.13 75.00 75.58 109806.08 110612.74 80.00 39.43 4.8 17 119914.76 77.78 68.66 124147.25 125064.48 83.33 47.03 4.3 20 140988.95 81.82 111.01 145662.81 148093.54 85.45 49.85 5.0 22 158257.32 83.33 142.29 159565.53 163545.00 86.67 129.55 3.3 25 180704.91* 84.62 600.00 184857.27 186861.01 85.38 152.55 注：平均相对偏差=[(QLSHH均值—Gurobi最优值)/Gurobi最优值]$ \times 100 \% $, 当Gurobi未找到最优解时不作计算。
下载: 导出CSV
表 5 中大规模算例下不同算法求解结果对比
Table 5. Comparison of solution results of different algorithms for medium and large-scale test cases
算例规模 算法 最优目标值/元 平均目标值土标准差/元 平均岸电使用率/% 平均求解时间$/\mathrm{s} $ 相对改进率 Δ1/%/% Δ2/%/% 中规模 40 GA 301 160.95 311 759.09±6 849.59 90.00 310.10 4.12 3.75 ALNS 298 829.27 310 559.70±9 972.03 88.00 303.24 QLSHH 291 912.69 298 918.86±4 738.63 90.00 280.97 43 GA 327 199.42 337 118.73±5 856.08 91.90 401.09 5.17 6.87 ALNS 323 979.50 343 276.06±11 513.46 87.62 401.49 QLSHH 315 888.74 319 692.66±2 302.85 92.38 350.04 45 GA 355 495.06 362 157.92±8 343.69 91.36 522.49 4.47 5.38 ALNS 351 634.53 365 646.99±12 370.49 89.55 450.35 QLSHH 335 139.32 345 984.76±5 774.91 92.27 413.78 47 GA 370 354.41 385 388.70±13 351.36 91.82 544.78 6.40 8.36 ALNS 366 663.20 393 622.77±11 074.97 91.82 600.00 QLSHH 354 503.66 360 722.28±6 851.20 94.09 455.90 50 GA 416 926.50 426 199.79±7 581.47 91.74 579.32 7.91 6.81 ALNS 405 109.23 421 147.37±12 905.84 92.00 600.00 QLSHH 385 656.20 392 485.39±4 044.25 93.04 551.16 大规模 70 GA 688 888.02 724 808.87±23 406.62 91.47 800.00 11.65 18.03 ALNS 709 817.89 781 307.29±46 888.95 91.18 800.00 QLSHH 611 671.02 640 402.97±18 278.24 92.35 800.00 73 GA 744 699.28 781 633.38±26 025.29 91.94 800.00 9.28 22.21 ALNS 818 049.35 911 568.47±56 258.97 92.22 800.00 QLSHH 668 675.96 709 110.42±23 308.95 91.39 800.00 75 GA 768 984.47 792 114.99±15 049.75 91.08 800.00 7.59 16.98 ALNS 837 891.06 881 748.38±35 491.47 91.08 800.00 QLSHH 704 250.91 732 028.98±17 886.99 92.70 800.00 78 GA 789 677.53 867 309.40±40 395.66 90.81 800.00 9.16 22.65 ALNS 922 890.56 1 018 523.95±70 122.99 90.27 800.00 QLSHH 748 987.35 787 881.98±19 377.08 95.41 800.00 80 GA 820 071.17 861 729.88±28 063.09 92.31 800.00 7.70 25.33 ALNS 924 085.44 1 065 125.91±80 482.29 94.10 800.00 QLSHH 756 110.50 795 356.84±27 410.87 95.13 800.00 注：$ \Delta_{1}=[(\mathrm{GA} $均值-QLSHH均值 $ )/\mathrm{GA} $均值 $ ] \times 100 \%, \Delta_{2}=[(\mathrm{ALNS} $均值-QLSHH均值 $ )/\mathrm{ALNS} $均值 $ ] \times 100 \% $。
下载: 导出CSV
-
[1] 范爱龙, 严新平, 李忠奎, 等. 我国航运业绿色低碳发展的需求、路径与展望[J]. 船海工程, 2024, 53(4): 1-5, 12.FAN A L, YAN X P, LI Z K, et al. Demand, path and prospect of green and low-carbon development of China's shipping industry[J]. Ship & Ocean Engineering, 2024, 53(4): 1-5, 12. (in Chinese) [2] 王枭, 赵山峰, 张乾能, 等. 面向港口关键起重设备调峰的协调优化运行方法[J]. 交通信息与安全, 2025, 43(6): 148-158. doi: 10.3963/j.jssn.1674-4861.2025.06.014WANG X, ZHAO S F, ZHANG Q N, et al. A coordinated optimization method for peak-shaving operation of key port crane equipment[J]. Journal of Transport Information and Safety, 2025, 43(6): 148-158. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2025.06.014 [3] 彭云, 李相达, 王文渊, 等. 绿色集装箱港口节能减排策略综述[J]. 交通运输工程学报, 2022, 22(4): 28-46.PENG Y, LI X D, WANG W Y, et al. Research overview on energy conservation and emission reduction strategies for green container ports[J]. Journal of Traffic and Transportation Engineering, 2022, 22(4): 28-46. (in Chinese) [4] ZIS T. Prospects of cold ironing as an emissions reduction option[J]. Transportation Research Part A: Policy and Practice, 2019, 119: 82-95. doi: 10.1016/j.tra.2018.11.003 [5] 郑童, 李俊, 赵梦孺, 等. 考虑岸电分配的集装箱码头泊位调度优化研究[J]. 中国航海, 2025, 48(3): 73-81.ZHENG T, LI J, ZHAO M R, et al. Research on berth scheduling optimization of container terminals considering shore power allocation[J]. Navigation of China, 2025, 48(3): 73-81. (in Chinese) [6] ZHANG Z, ZHU Y, ZHU J, et al. Collaborative optimization of shore power and berth allocation based on economic, environmental, and operational efficiency[J]. Journal of Marine Science and Engineering, 2025, 13(4): 776. doi: 10.3390/jmse13040776 [7] 闵德权, 张志铎, 张伟航. 基于港口环境效益的岸电与泊位联合分配优化研究[J]. 重庆交通大学学报(自然科学版), 2023, 42(1): 83-90.MIN D Q, ZHANG Z D, ZHANG W H. Research on joint allocation optimization of shore power and berths based on port environmental benefits[J]. Journal of Chongqing Jiaotong University (Natural Science Edition), 2023, 42(1): 83-90. (in Chinese) [8] WANG Z, HU H, ZHEN L. Berth and quay cranes allocation problem with on-shore power supply assignment in container terminals[J]. Computers & Industrial Engineering, 2024, 188: 109910. [9] PENG Y, DONG M, LI X, et al. Cooperative optimization of shore power allocation and berth allocation: a balance between cost and environmental benefit[J]. Journal of Cleaner Production, 2021, 279: 123816. doi: 10.1016/j.jclepro.2020.123816 [10] MA K, FENG Y, YANG J, et al. Two-stage distributionally robust optimization for port integrated energy system with berth allocation under uncertainties[J]. Energy, 2025, 322: 135588. doi: 10.1016/j.energy.2025.135588 [11] ZHANG Y, LIANG C, SHI J, et al. Optimal port microgrid scheduling incorporating onshore power supply and berth allocation under uncertainty[J]. Applied Energy, 2022, 313: 118856. [12] LIU W, ZHU X, WANG L, et al. Rolling horizon based robust optimization method of quayside operations in maritime container ports[J]. Ocean Engineering, 2022, 256: 111505. doi: 10.1016/j.oceaneng.2022.111505 [13] LYU Y, ZOU M, LI J, et al. Dynamic berth allocation under uncertainties based on deep reinforcement learning towards resilient ports[J]. Ocean and Coastal Management, 2024, 252: 107113. doi: 10.1016/j.ocecoaman.2024.107113 [14] JO S, MOON I. A hierarchical reinforcement learning approach for real-time berth allocation and quay crane scheduling[J]. International Journal of Production Research, 2025, 63(24): 10027-10052. doi: 10.1080/00207543.2025.2542518 [15] BERTSIMAS D, SIM M. Robust discrete optimization and network flows[J]. Mathematical Programming, 2003, 98(1): 49-71. [16] ZHANG Z Q, QIAN B, HU R, et al. Q-learning-based hyper-heuristic evolutionary algorithm for the distributed assembly blocking flowshop scheduling problem[J]. Applied Soft Computing, 2023, 146: 110695. doi: 10.1016/j.asoc.2023.110695 [17] 李凯文. 基于深度强化学习的组合优化方法研究[D]. 长沙: 国防科技大学, 2022.LI K W. Research on combinatorial optimization methods based on deep reinforcement learning[D]. Changsha: National University of Defense Technology, 2022. (in Chinese) [18] ZHENG Q, XUAN H, ZHANG Y, et al. Q-learning-based multi-objective heuristic algorithm for solving multi-resource co-scheduling problem of ship-lock-channel considering water discharge[J]. IEEE Transactions on Intelligent Transportation Systems, 2025, 26(12): 21588-21604. doi: 10.1109/TITS.2025.3607755 [19] 文捷, 刘昊雨, 王永才, 等. 潮汐影响下基于长方体排列的船舶调度问题研究[J]. 中国航海, 2024, 47(3): 81-88. [20] HELLSTEN O E, SACRAMENTO D, PISINGER D. An adaptive large neighbourhood search heuristic for routing and scheduling feeder vessels in multi-terminal ports[J]. European Journal of Operational Research, 2020, 287(2): 682-698. doi: 10.1016/j.ejor.2020.04.050 -
点击查看大图
图(8) / 表(5)
计量
- 文章访问数: 18
- HTML全文浏览量: 10
- PDF下载量: 0
- 被引次数: 0