单向航道下连续泊位分配与船舶调度集成优化

doi:10.3778/j.issn.1002-8331.2009-0447

摘要/Abstract

摘要： 为改善单向航道连续泊位港口的运营效率，研究泊位分配与船舶进出港调度集成优化。考虑潮汐、进出港时段交替与偏好泊位的影响，建立0-1整数线性规划模型，以船舶偏离偏好泊位成本和滞期成本为优化目标，确定各艘船舶的靠泊位置与进出港时刻。针对问题情境和其特有的约束条件，将原数学模型通过Dantzig-Wolfe分解方法分成主问题模型和子问题模型，提出了满足问题特性的分支定界和列生成相结合的精确型分支定价算法。在列生成算法中，给出了适合本问题的列选取策略；在分支定界算法中，设计了广度优先策略来提升求解效率。采用多组算例来验证了方案与算法的有效性，并通过不同规模算例分析了进出港时段长度变化对方案的影响，可为港口的实际作业安排提供参考。

关键词: 单向航道, 船舶调度, 泊位分配, 分支定价算法

Abstract: The integrated optimization of berth allocation and ship inbound and outbound port scheduling is studied to improve the operational efficiency of the one-way channel continuous berth port. Considering the influence of tidal, inbound and outbound port period and preference berth, a 0-1 integer linear programming model is established to optimize the deviation cost of ship from preference berth and demurrage cost and the model finally gives the berthing position and entry and exit time of each ship. According to the problem definitions and its unique constraints, the original mathematical model is divided into a master problem model and a sub-problem model through Dantzig-Wolfe decomposition, and the exact branch-and-price algorithm is designed based on the branch-and-bound and column generation. What’s more, the column selection strategy suitable for this problem is proposed, and the breadth-first search strategy is put forward to speed up the search efficiency. The effectiveness of the proposed scheduling scheme and algorithm are tested by numerical experiments and the effect of the length of inbound and outbound port period changing on the scheme is analyzed by different sized examples, which can provide the reference for the actual operation arrangement of the port.

Key words: one-way channel, ship scheduling, berth allocation, branch-and-price algorithm

吴云强, 张戎. 单向航道下连续泊位分配与船舶调度集成优化[J]. 计算机工程与应用, 2022, 58(9): 246-255.

WU Yunqiang, ZHANG Rong. Integrated Optimization of Continuous Berth Allocation and Ship Scheduling Under One-Way Channel[J]. Computer Engineering and Applications, 2022, 58(9): 246-255.

参考文献

[1] 徐国裕，郭涂城.单向水道船舶进出港最佳排序模式[J].大连海事大学学报，2008，34（4）：150-153.
XU G Y，GUO T C.Optimum scheduling model for ship in/outbound harbor in one-way traffic fairway[J].Journal of Dalian Maritime University，2008，34（4）：150-153.
[2] 邬惠国，刘春姣，肖英杰.基于格序决策理论的LNG船舶进出港组织方案比选[J].上海海事大学学报，2012，33（2）：10-13.
WU H G，LIU C J，XIAO Y J.Organization scheme selection for arrival and departure of LNG vessels based on lattice order decision-making theory[J].Journal of Shanghai Maritime University，2012，33（2）：10-13.
[3] 郑红星，刘保利，王泽浩.考虑潮汐的多港池港口船舶调度优化[J].系统工程理论与实践，2018，38（10）：2638-2651.
ZHENG H X，LIU B L，WANG Z H.Ship scheduling optimization in multi-harbor basin port considering tidal influence[J].Systems Engineering Theory & Practice，2018，38（10）：2638-2651.
[4] EDUARDO L R，SHI X N，STEFAN V.The waterway ship scheduling problem[J].Transportation Research Part D，2018，60：191-209.
[5] 张新宇，李瑞杰，林俊，等.双向通航港口船舶调度优化模型与算法[J].中国航海，2018，41（2）：36-40.
ZHANG X Y，LI R J，LIN J，et al.Vessel scheduling optimization in two-way traffic ports[J].Navigation of China，2018，41（2）：36-40.
[6] 陈向.复式航道条件下的港口船舶调度优化[D].大连：大连海事大学，2017.
CHEN X.Vessel scheduling optimization under the condition of compound waterway[D].Dalian：Dalian Maritime University，2017.
[7] ZHENG Z L，YANG B，HU Z H.Container port discrete berth allocation under restriction of preference berth[J].Port and Waterway Engineering，2013，486（12）：64-68.
[8] 孙少文，杨斌.潮汐影响下的港口离散泊位分配问题研究[J].合肥工业大学学报，2014，37（4）：486-492.
SUN S W，YANG B.Research on discrete berth allocation under tidal influence at container terminal[J].Journal of Hefei University of Technology，2014，37（4）：486-492.
[9] TING C J，WU K C，CHOU H.Particle swarm optimization algorithm for the berth allocation problem[J].Expert Systems with Applications，2014，41（4）：1543-1550.
[10] EDUARDO L R，CHRISTOPHER E I，BELEN M B，et al.A set-partitioning-based model for the berth allocation problem under time-dependent limitations[J].European Journal of Operational Research，2016，250（3）：1001-1012.
[11] DULEBENETS M A，GOLIAS M，MISHRA S.A collaborative agreement for berth allocation under excessive demand[J].Engineering Applications of Artificial Intelligence，2018，69：76-92.
[12] MIHALIS G，MARIA B，SOTIRIS T，et al.The berth-scheduling problem：maximizing berth productivity and minimizing fuel consumption and emissions production[J].Transportation Research Record，2018.
[13] SONG Y，ZHANG J，LIU M，et al.The berth allocation optimization with the consideration of time-varying water depths[J].International Journal of Production Research，2019，57（1/2）：488-516.
[14] NISHI T，OKURA T，LALLA-RUIZ E，et al.A dynamic programming-based matheuristic for the dynamic berth allocation problem[J].Annals of Operations Research，2020，286：391-410.
[15] 秦天保，沙梅.动态连续泊位分配问题的约束规划模型[J].工业工程与管理，2013，18（6）：27-31.
QIN T B，SHA M.Constraint programming for the dynamic continuous berth allocation problem[J].Industrial Engineering and Management，2013，18（6）：27-31.
[16] 曾庆成，赵孝峰，胡祥培，等.集装箱码头泊位计划的鲁棒优化模型[J].运筹与管理，2015，24（2）：71-77.
ZENG Q C，ZHAO X F，HU X P，et al.Robust optimization model for berth planning problem in container terminals[J].Operations Research and Management Science，2015，24（2）：71-77.
[17] URSAVAS E.Priority control of berth allocation problem in container terminals[J].Annals of Operation Research，2015：1-20.
[18] LIU C，XIANG X，ZHENG L.A two-stage robust optimization approach for the berth allocation problem under uncertainty[J].Flexible Services and Manufacturing Journal，2019，32：425-452.
[19] ZHANG X Y，LIN J，GUO Z J.Vessel transportation scheduling optimization based on channel-berth coordination[J].Ocean Engineering，2016，112：145-152.
[20] JIA S，LI C L，XU Z.Managing navigation channel traffic and anchorage area utilization of a container port[J].Transportation Science，2019，53（3）：728-745.
[21] 郑红星，徐海栋，刘保利.单向航道船舶进港次序与泊位分配协同优化[J].运筹与管理，2017，26（9）：37-45.
ZHENG H X，XU H D，LIU B L.One-way channel ship inbound order and berth allocation collaborative optimization[J].Operations Research and Management Science，2017，26（9）：37-45.
[22] LüBBECKE M E，DESROSIERS J.Selected topics in column generation[J].Operations Research，2005，53（6）：1007-1023.