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

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

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