0 引言

航道和泊位是集装箱港口装卸作业中两种非常重要的资源，船舶调度方案与泊位分配计划直接影响着港口作业效率，二者之间的集成调度是集装箱港口研究的热点问题之一.

在船舶调度研究方面，国内外学者主要从单向航道、双向航道与复式航道三个方面进行研究.其中对于单向航道，徐国裕等^[1]基于优先级理论，引入工作排序理论建立船舶进出港最佳排序模式.王辉^[2]提出了一种更为准确的计算乘潮水位和通航时间的方法，并进一步确定编队船舶数量，以此来设计船舶乘潮进出港的通航组织方案.针对LNG船舶的作业特点，邬惠国等^[3]引入多目标格序决策理论，并构建基于安全性、经济性等管理因素的评价指标体系，以此来选择最佳的船舶进出港方案.由于船舶调度过程中会受到外界干扰因素的影响，张晓东等^[4]将干扰排队模型运用到进出港交通组织方案的仿真分析中，可更好地模拟航道船舶的通过状况，验证了干扰排队模型的有效性.刘佳等^[5]利用计算机仿真技术来构建港区船舶航行作业系统仿真模型，研究了不同船舶进出港规则对港口服务水平的影响.对于双向航道，Eduardo等^[6]考虑碳排放的影响，以船舶总等待时间最小为目标函数建立混合整数线性规划模型，并设计模拟退火算法对问题进行求解，最终给出了最佳船舶进出港调度方案.对于复式航道，陈向^[7]从港口调度的实际情况出发，以总调度时间最小和总等待时间最小为目标函数，建立了复式航道水域船舶调度优化模型，并设计多目标遗传算法来求解.从上述文献可知，已有船舶调度的研究中关于单向航道的文献最多，双向航道与复式航道的文献较少；现有文献主要考虑船舶优先级、现实作业中的干扰条件、船舶类型或者碳排放等因素，通过方案评价、排序理论与仿真方法来研究船舶调度问题，较少通过构建数学模型来给出优化调度方案，且国内外学者几乎未考虑泊位分配方案对船舶调度的影响.

在泊位分配问题研究方面，现有文献重点关注以下两个方面，未考虑船期与考虑船期.针对未考虑船期的情况，为得到最优的泊位分配方案，童珊^[8]考虑港口装卸效率和船舶优先权，以船舶在港总时间最小为目标函数，建立了一个混合整数规划模型，设计了启发式算法来求解模型；Ting^[9]考虑船舶的动态到达，以等待时间与装卸作业时间之和最小为目标函数，建立了一个混合整数规划模型，并设计了粒子群算法用于求解模型；许欢等^[10]考虑碳排放量，构建以船舶油耗量最小和离港延迟时间最短为目标的混合整数规划模型，并设计了多目标遗传算法；Dulebenets等^[11]考虑船舶可以改变靠泊港口这一条件，以船舶总服务成本最小为目标函数，建立混合整数非线性规划模型，并设计文化基因算法对其进行求解.针对考虑船期的泊位分配问题，为实现泊位分配方案的优化，Xu等^[12]考虑水深与潮汐因素，以船舶总完成时间最小为目标函数，建立混合整数线性规划模型，并分别针对船舶静态与动态到达情况设计启发式算法来求解模型；Nitish等^[13]考虑货物类型，以船舶总服务时间最小为目标构函数构建混合整数线性规划模型，并设计两种基于集划分的精确算法与一种启发式算法来求解模型；Du^[14]引入虚拟到达策略，构建以总成本最小为目标的混合整数非线性规划模型，并通过二阶锥规划技术来处理非线性约束；那广哲^[15]以码头服务船舶的总成本最小为目标函数，建立混合整数规划模型，并根据问题特性设计禁忌搜索算法来求解模型；Eduardo^[16]考虑水深和多个计划周期的限制，以到港船舶中转时间之和最小为目标函数，构建混合整数线性规划模型，并用CPLEX进行求解；王军等^[17]构建了基于在泊时间动态学习的泊位调度方案优化模型，并设计了包含动态学习过程的智能启发式算法进行求解.在有关泊位分配的文献中，大多文献考虑船舶动态到达、优先级、水深等因素，以船舶总在港时间或者总作业时间最小为优化目标，并设计相应的启发式算法进行求解，少有文献考虑船舶调度方案对泊位分配的影响.

在泊位分配与船舶调度集成优化问题研究方面，主要按照船舶待停靠泊位是否已知来进行分类.针对待靠泊位已知的情况，张新宇等^[18]根据先后调度两艘船舶的进出港方向和所停靠泊位的远近区分两船间的相对关系，以总等待时间最少为目标函数，构建混合整数规划模型，并通过模拟退火多种群遗传算法进行求解.在此基础上，Zhang等^[19]为了提高单向航道的船舶进出港效率，考虑船舶调度顺序、航行方向和泊位距离，以船舶总等待时间最少为目标函数，构建混合整数规划模型，并设计了多种群遗传算法来求解问题.针对待靠泊位未知的情况，郑红星等^[20]以在港总成本最小为目标函数，建立了混合整数规划模型，最后通过改进和声搜索算法来求解模型.已有文献大多数是在已知泊位分配的情况下来研究泊位分配与船舶调度集成优化，少有考虑待靠泊位未知的情况，同时罕有文献考虑潮汐对于集成调度的影响.

综上，现有文献关于船舶调度与泊位分配的研究日趋成熟，而泊位分配与船舶调度集成问题的相关研究较少，后者是现在港口调度领域研究的关键问题之一.区别已有文献，本文在现有研究的基础上，针对拥有单向航道的港口，聚焦于泊位分配与船舶调度集成优化问题，从降低总作业成本的视角出发，重点考虑潮汐对船舶调度和泊位分配的影响，兼顾船舶调度与泊位分配之间的交互影响，最终确定优化的船舶进出港次序与泊位分配方案.

1 问题描述

船舶海侧作业过程为：在预知船舶的抵港计划、船期和配载计划后，港口会为各船舶分配合理数量的岸桥，并确定其进港时间.当船舶到达锚地后，其先在锚地等待进港，当收到港方通知时，其会经过航道靠泊事先分配的泊位，装卸作业完成之后离开港口.为高效的进行装卸作业，同时实现调度成本的最小化，需要协同优化船舶调度与泊位分配.在此过程中，由于船舶与泊位具有多种类型，船舶靠泊泊位的类型需要与船舶类型匹配，即船舶规模不能超过泊位规模；同时考虑到单向航道的进出港时段交替进行，船舶进出港时刻与进出港时段的设置有关，其中进出港时段指船舶可以进行进港或者出港作业的一段时间；此外，潮汐会影响航道与泊位的水深，某些大船只有在涨潮时才能进出港口.

本文的问题可描述为：针对一单向航道的离散泊位集装箱港口，在固定的计划期内，已知船舶预计到港时刻、作业量和离港时刻等相关信息，以计划期内所有抵港船舶为研究对象，着重考虑大型船舶需要乘潮进出港口和进出港时段交替的作业现实，兼顾船舶进出港作业的时间约束，给出计划期内所有船舶进出港的具体时刻和泊位分配方案，使得到港船舶作业时间成本、偏离最优泊位成本和滞期成本之和最小.

2 模型建立 2.1 假设条件

1) 泊位类型为离散型泊位；

2) 船舶预计到港与离港时刻提前已知；

3) 每台岸桥的作业效率固定.

2.2 符号说明

1) 参数

I：到港船舶集合，且i∈I；J：港口泊位集合，且j∈J；IOP：进出港时段集合，且k∈IOP；TP：潮汐时段集合，且p∈TP；TS_i：船舶i到达外锚地时刻；TZ_i：船舶i所需装卸时间；EDT_i：船舶i的预计离港时刻；TH_ij：船舶i从外锚地航行到j泊位的航行时间；T₀：进、出港时段的长度；D_ij：各个泊位之间的距离；H_ij=1：船舶i的偏好泊位为j，否则为0；L_i：船舶i的类型，且1、2、3分别表示小型、中型、大型；B_j：泊位j的类型，1、2、3分别表示小型、中型、大型；∂_k=1表示此时段为进港时段，∂_k=0为出港时段；CH_i=1表示船舶i为乘潮船舶，否则为0；T^D表示第一个潮汐时段的开始时刻，T^U表示第一个潮汐时段的结束时刻，且12个小时为一个周期；CZ_i：船舶i的单位滞期成本；CP_i：船舶i的单位偏离成本；CD：船舶作业时间成本系数；M：充分大正数.

2) 决策变量

t_i：船舶i开始从锚地进港的时刻；tf_i：船舶i开始从泊位离港的时刻；tz_i：船舶i在泊位完成装卸作业的时刻；x_ij=1：船舶i的靠泊泊位为泊位j，否则为0；y_ij=1：船舶i在船舶j之后进港，否则为0；z_ij=1：泊位j上的船舶i发生滞期，否则为0；ws_ik=1：船舶i在时段k进港，否则为0；we_ik=1：船舶i在时段k出港，否则为0；ms_ip=1：船舶i在潮汐时段p进港，否则为0；me_ip=1：船舶i在潮汐时段p出港，否则为0.

2.3 数学模型

在集装箱港口作业中，成本是港口需要考虑的最重要因素，因此本文的目标函数是港口作业总成本最小，其包括船舶偏离偏好泊位的成本、船舶滞期成本与船舶在港口作业的时间成本.在选择约束条件时，需要考虑本文所研究的问题的特点，包括船舶类型与泊位类型相匹配、大型船舶需要乘潮进出港口和进出港时段交替.除此之外，船舶在进出港口时，开始进港时刻、泊位作业完成时刻、开始离港时刻这3个时间节点需要满足相应的时间约束，且需要考虑船舶进出港先后顺序的约束条件.

1) 目标函数

其中：为船舶偏离偏好泊位的成本；为船舶滞期成本；为船舶在港口作业的时间成本；三者之和的z为港口作业总成本.

2) 约束条件

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

其中，式(1)表示每艘船舶只能靠泊一个泊位；式(2)表示船舶类型与泊位类型需匹配；式(3)、(4)表示船舶实际离港时刻与预计离港时刻之间的关系；式(5)表示船舶开始调度时刻的时间约束；式(6)表示若两艘船靠泊同一泊位，则后进港船需在前进港船离港后开始进港；式(7)表示先后进港的两艘船舶的时间关系；式(8)表示船舶在泊位完成装卸作业的时刻的时间约束；式(9)表示实际离港时刻的时间约束；式(10)表示船舶必须选一个进港时段来完成进港；式(11)、式(12)表示船舶进港时段的时间约束；式(13)表示船舶必须选一个出港时段来完成出港；式(14)、式(15)表示船舶出港时段的时间约束；式(16)表示乘潮船舶必须选一个潮汐时段来完成进港；式(17)、式(18)表示乘潮船舶进港潮汐时段的时间约束；式(19)表示乘潮船舶必须选一个潮汐时段来完成出港；式(20)、式(21)表示乘潮船舶出港潮汐时段的时间约束.

3 算法设计

本文设计了改进禁忌搜索算法(ITS)来求解模型，采用多层编码方式来表示解，编码中包含了船舶的泊位分配计划和进出港次序的信息.相比于传统禁忌搜索算法，改进禁忌搜索算法增加了集中性策略与多样性策略、长短禁忌表、解修复，同时通过邻域与候选集相互配合来动态确定集中性与多样性搜索的时机.算法思路是基于启发式规则获得初始解，通过集中性解生成策略与多样性解生成策略来构造邻域，并在邻域中加入解修复策略来修正不可行或质量较劣的解.根据得到的邻域，获得不同类型解的数量随迭代次数而变化的候选集，并利用长—短禁忌表筛选用于下次迭代的初始解.结合文[21]，迭代终止条件包括两个，一是最优值连续一定迭代次数保持不变；二是算法达到最大迭代次数.

3.1 算法流程

算法参数包括最大迭代次数N，最优值连续不变次数K，邻域规模L，候选集规模H，集中性解的个数DL，上层邻域变换概率PL、中层突变概率PT、同层变换概率PC，且PL+PT+PC=1，短禁忌表长度DC，长禁忌表长度CL，允许出现的次数M，算法流程如图 1所示.

3.2 解的编码与初始解生成策略

解的编码为多层编码方式，上层为船舶进港次序，中层为船舶靠泊位置，下层为船舶出港次序，如图 2所示.

初始解生成策略如下所示：

步骤 1  根据船舶预计到港时刻从早到晚进行排序，从而生成船舶进港次序，即解的上层；

步骤 2  当船舶按照上述进港次序来进港时，根据以下方法来得到其靠泊位置，即解的中层.若某船没有偏好泊位，则靠泊泊位为任一满足靠泊约束的空闲泊位；若此船有偏好泊位且空闲，则靠泊泊位为偏好泊位，否则选取离偏好泊位最近的满足靠泊约束的空闲泊位，若此时无满足靠泊约束的空闲泊位，则等到下一进港时段再为该船分配泊位；

步骤 3  在已知船舶进港次序和靠泊位置时，按照船舶在泊位完成作业后的开始离港时刻从早到晚进行排序，从而生成船舶出港次序，即解的下层；

步骤 4  为保证船舶能够顺利进港并加快算法的收敛速度，对生成的解的上层按如下规则进行调整.

1) 若解中后进港船舶的预计抵港时刻满足下列条件之一，则解的上层保持不变.

(1) 晚于前进港船舶的预计离港时刻；

(2) 晚于前进港船舶作业必要完成时刻(船舶预计到港时刻、锚地与泊位之间的航行时间和船舶装卸所需时间之和)，且有“后船先进港，前船必然滞期”情况.

2) 若解中后进港船舶的预计抵港时刻晚于前进港船舶的预计到达时刻且早于前进港船舶作业必要完成时刻，并有滞期情况发生，则对解的上层按照如下规则调整.

(1) 若上述两艘船中有一艘需乘潮进港的船舶，则解的上层中此船排在另外一艘船的前面；

(2) 若上述两艘船都是乘潮船舶或者不乘潮船舶，则单位滞期成本高的船舶在解的上层中排在前面.

3.3 邻域与候选集的构造

本文基于集中性策略与多样性策略相结合的思想来构造邻域，前者用于加强对优良解的邻域进一步搜索，后者用于拓宽搜索区域尤其是未知区域.其中集中性策略如下：

步骤 1  任选一艘船舶，插入到解的上层中余下的船舶进港次序中，同时保持解的中层跟随变换，并根据前面变化来改变解的下层的顺序，从而生成船舶数量个新解；

步骤 2  计算新解中各船舶实际离港时刻与预计离港时刻之间的差值之和，选取数值最小的新解.

多样性生成策略共有三种，分别是上层邻域变换、中层突变与同层变换，且各种生成策略执行时机见图 1.上层邻域变换，即任选相邻两艘船舶交换其进港顺序；中层突变指选取一艘或者多艘船舶，在满足泊位约束条件下改变其靠泊泊位；同层变换表示任意选择两艘船舶，执行上中层同时互换策略，解的下层根据前面的变化随之改变.

候选集分成两部分，前半部分是由在邻域集中性策略生成的解中按照适应度值从小到大选取DL个解组成；后半部分则从邻域多样性策略生成的解中随机选取H-DL个解组成.同时DL随迭代次数而变化，其变化策略见图 1算法流程图.

3.4 解修复

解修复包含以下两种情景：第一，在邻域构造过程中，新解可能出现船型与泊位类型不匹配的情况，使得解不可行；同时，可能出现靠泊泊位相同的两艘船舶存在后进港船舶滞期的情况，使得解的质量较差；第二，部分乘潮船舶需要在潮期内进出港口，但由于乘潮船舶进港次序比较靠后或者靠泊泊位的影响，从而错过最近的潮期，只能在12小时后进出港口，导致非常高的滞期成本且影响后续船舶进出港口，使得解的质量较差.

1) 情景1

针对情景1，本文设计了解修复算子1，如图 3所示.

2) 情景2

针对情景2，本文设计了解修复算子2，步骤如下.

步骤 1  参数初始化，令i=1，m=1；

步骤 2  若解中第m艘乘潮船舶实际开始进出港时刻，大于离预计到达时刻或离开时刻最近的潮汐时段的结束时刻，则转到步骤3，否则转到步骤5；

步骤 3  若此船舶与某前进港船舶靠泊泊位相同，则把此船舶在解的中层中对应的靠泊泊位换成不影响后面乘潮船舶进出港时刻的大型空闲泊位；若无此类泊位，则解的中层船m对应的靠泊泊位为离偏好泊位最近的大型空闲泊位，否则靠泊泊位为最先开始空闲的大型泊位，从而生成新解，转到步骤4；

步骤 4  若此船与前面进港船舶无相同靠泊泊位，则在解的中层中从前面离此船最近的非乘潮进港船舶开始，与之执行同层变换策略，直到此船舶无错过潮汐时段的情况，从而生成新解，转到步骤5；

步骤 5  令m=m+1，若m大于潮汐船舶数，则转到步骤6，否则转到步骤2；

步骤 6  令i=i+1，若i大于邻域规模，则输出新邻域，否则，令m=1，转到步骤2.

3.5 禁忌表

为避免某个解多次出现，禁忌对象为解的适应度值.禁忌表分为短禁忌表和长禁忌表，短禁忌表为DC*1的矩阵，长禁忌表为CL*1的矩阵，禁忌表生成策略见图 4.

4 算例 4.1 基础数据

某个单向航道港口有6个离散泊位，编号为1~6，且1~2号是小型泊位，3~4号是中型泊位，5~6号是大型泊位.根据港口实际作业情况，船舶进出港时段长度为150 min，且船舶从锚地航行到各泊位的时间为25 min、25 min、35 min、35 min、45 min、45 min.此外，船舶在港口时间成本为每天每吨位3. 6元，且分配给船舶的岸桥数量与船舶长度以及是否需要乘潮进出港口有关.各个船舶的基本信息如表 1所示，其中6号、13号船舶需要乘潮进出港口，第一个潮汐时段的开始时刻为9: 00，结束时刻为15: 00，且潮汐时段的周期为12 h.

4.2 结果分析

设定最大迭代次数为5 000，最优值连续不变次数为500，邻域规模为100，候选集规模为30，集中性解的个数为15，上层邻域变换概率为0. 3、中层突变概率为0. 4、同层变换概率为0. 3，短禁忌表长度为25，长禁忌表长度为50，允许出现的次数为3；通过Matlab R2014a编写程序，并在2. 50 GHz Intel Core i5-2450M CPU和2 GB内存的双核计算机上运行程序.运行得到的调度方案如表 2所示，最优集成调度方案如图 5所示，最小作业总成本为25 490元.

4.3 方案有效性验证

本文研究泊位分配和船舶调度集成问题，因此为了验证前文提出的方案的有效性，分别与由码头实际作业规则得到的单独优化方案以及已有集成调度方案进行对比分析.现实作业中码头一般按如下规则安排作业：船舶按先到先服务策略进行船舶调度，同时优先安排潮汐船舶进出港口；在泊位分配时，以泊位偏离成本、船舶滞期成本之和最小为优化目标.单独优化下的调度方案如图 6所示.

从图 6可以看出，在先到先服务的方案中，9号船舶没有偏好泊位且到港时只有3号泊位空闲，因此9号船舶靠泊泊位为3号泊位.由于其占用了12号船舶的偏好泊位，使之偏离偏好泊位.除此之外，单独优化方案的成本为29 562元，协同优化方案的成本为25 490元，故采用本文的模型与算法得到的方案节约16. 00%的成本，验证了本文的调度方案比实际作业方案更好.

同时，考虑潮汐影响的集成调度方案的文献很罕见，且文[20]研究不考虑潮汐影响的泊位分配与船舶进出港调度优化.为了与已有集成方案对比，作者利用本文的模型与算法对文[20]算例中的数据进行计算，得到的方案总成本为28 009，文[20]得到的方案总成本29 186，采用本文算法与模型得到的方案节约4. 2%的成本，表明即使不考虑潮汐影响时本文得到的方案也更优，从而验证了方案的有效性.

4.4 算法效率验证

由于本文所建立的数学模型为线性规划混合整数数学模型，因此可以利用Cplex来得到精确解.通过Cplex与本文设计的改进禁忌搜索算法(ITS算法)求解不同抵港船舶数量下的问题，从而验证ITS算法的有效性，实验结果如表 3所示.

表 3中的同种船舶数量下的不同实验是改变船舶预计到达时刻与离港时刻而生成的，在所有算例中，根据ITS和CPLEX成本的差值占CPLEX成本的比例(GAP)，ITS目标值和精确解目标值的差值在5%以内；随着船舶规模的增大，CPLEX求解时间呈指数型剧烈增加，ITS求解时间变化幅度不大，且运行时间都在120s以内.综上，本文所设计的算法能在较短时间内求得质量较好的解，可有效解决文中所提出的问题.

4.5 敏感性分析

1) 船型变化分析

为分析船舶型号变化对港口调度的影响，改变抵港船舶的数量和类型，设置小型船居多、中型船居多、大型船居多三种不同算例，计算各抵港船舶规模下港口作业总成本，结果如表 4所示.

由表 4可知，当抵港船舶规模不同时，大型船舶居多时成本最高，中型船舶居多时次之，小型船居多时成本最低，这是由于小型船舶可以靠泊大、中、小三种泊位，大型船舶只能停靠大型泊位，不能靠泊中、小型泊位，大、中型船舶过多会造成船舶无法正常进出港口，滞期成本相应增加；小型船舶居多时的成本与正常规模下的抵港船舶到达港口靠泊时的成本相差不是特别大，这是由于偏好泊位的存在，小型船舶型号过多，会使得小型船舶偏离偏好泊位，靠泊大中型泊位.

2) 进出港时段设置分析

为保证船舶进出港时段长度设置的合理性，基于算例中的数据，通过改变船舶进出港时段长度与船舶的数量，研究其与作业总成本之间的关系，来确定不同情况下的合理时段长度，如表 5所示.

由表 5可知，当船舶的数量一定时，作业总成本随时段长度增加表现出先增加后降低再增加的变化趋势；当时段长度一定时，作业总成本随着船舶数量的增加而大幅度增长，且大多数情况下时段长度为90 min时的作业总成本较低，可以为港口进出港时段设置提供一定参考.

5 结论

船舶大型化的趋势使得越来越多的船舶需要乘潮进出港口，导致泊位分配和船舶调度之间的关联度越来越强，增加了港口作业调度的难度.为此，本文从降低港口作业总成本的角度出发，将泊位分配问题与船舶调度问题集成为一体，构建了相应的数学模型，并设计了启发式算法用于求解.

从本文的研究结果可知，集成调度方案明显优于单独调度方案，泊位分配与船舶调度之间的相互影响需重点关注；潮汐时段影响船舶进出港时间，从而影响后续船舶的进出港计划与泊位分配方案，因此在实际港口作业中，需优先考虑乘潮船舶的泊位分配与进出港次序；通过敏感性分析，确定了船舶类型对作业总成本的影响，得到了不同到港船舶数量下最佳的进出港时段长度，因此，在现实作业中可基于船舶规模与类型来动态设置进出港时段长度.

在未来的研究中，可考虑潮汐高度随时间变化，以及船舶调度、泊位分配和岸桥调度的协同优化问题.