复式航道港口拖轮配置仿真优化

郑红星，徐海栋，曹红雷

(大连海事大学 交通运输管理学院，辽宁 大连 116026)

复式航道港口拖轮配置仿真优化

郑红星，徐海栋，曹红雷

(大连海事大学 交通运输管理学院，辽宁 大连 116026)

为更好地指导复式航道港口拖轮资源的配置，构建了拖轮作业仿真模型。基于复式航道的特点，给出了基于Arena的仿真模型，并嵌入了以拖轮耗油总成本最小为目标的作业调度优化模型；给出了嵌入启发式规则的遗传算法用于求解该模型；并通过多次仿真实验，兼顾拖轮的作业耗油总成本和闲置率，筛选出当前的最优配置方案；通过拖轮闲置率随船舶类型和数量变化的仿真分析，并结合未来船舶大型化的趋势，给出了未来的拖轮最佳配置方案。

航道工程；复式航道；拖轮配置；遗传算法；拖轮闲置率

0 引 言

一般情况下，船舶在港口的进出港作业需要拖轮协助，拖轮的配置是影响港口作业效率和客户满意度的重要因素。拖轮的合理配置与港口航道模式、拖轮作业调度紧密相关，对拖轮资源进行合理调度，可以提高拖轮作业效率，降低作业成本，是提高港口竞争力的重要途径，也是港口作业的研究热点；而随着船舶大型化的发展，复式航道在港口中越来越普遍，复式航道兼具单向航道与双向航道的特点，因此研究复式航道更有意义。

近年来，国内外学者对相关问题进行了细致的研究，主要从以下3个方面评述。

在航道模式的研究方面，黄泰坤等[1]通过对比双向航道及复式航道下天津港运营情况，探讨了港口服务水平、锚地等待时间、航道等待时间等因素随着船流密度变化的趋势；唐国磊等[2]研究了航道尺度对泊位有效利用率的影响，构建了相应的仿真模型，并进行了系统分析。姬利娜[3]针对城市路网中存在畸形交叉口的客观事实，在分析畸形交叉口带来的交通问题的基础上，提出了畸形交叉口交通改善的基本思路和方法，可为船舶航道交通流研究提供借鉴；王江涛[4]基于非集计离散选择模型理论，结合通道内各种运输方式特性，给出了在运用 MNL 模型预测通道客运分担率时特性变量的选取原则,对航道通过率研究有一定指导意义。

在拖轮配置方面，陆海波[5]对影响拖轮总体配置的生产要素进行了全面的统计和分析，使港口拖轮配置规模和结构日趋合理，为港口的拖轮配置提供了相关借鉴；刘志雄[6]通过分析港口拖轮作业的过程及特点，通过仿真计算得到船舶的平均等待时间、最大排队队长及各种拖轮的利用率等参数，为决策者合理配置拖轮提供了科学依据。

在拖轮调度方面，WANG Su等[7]结合现有调度规则构建了拖轮调度问题的混合整数规划模型，通过数值实验证明了所构建模型的效用，并分析了拖轮的配置数量对到港船舶在港时间造成的影响；王巍等[8]和HE Tao等[9]分别针对多停泊基地和不同作业模式下的拖轮调度，以最大完工时间和总作业油耗最小为目标，建立了拖轮调度多目标优化模型，计算结果表明不同作业模式对拖轮调度结果会产生较大影响；WANG Su等[10]在集装箱终端拖轮调度问题研究的基础上，以最少船舶周转时间为目标，提出互相信任策略的蚁群算法，进一步提高了船舶进出港的效率；徐奇等[11-12]考虑了多阶段共用平行机特征的拖轮作业模式优化问题，建立了考虑两阶段与切换时间的调度优化模型，设计了启发式规则与模拟退火结合的求解算法，并运用Arena软件对拖轮助泊作业系统进行仿真实现；YU Wenhui[13]对港口拖轮的优化及仿真进行研究，采用启发式算法求解最优解，并进行了验证实验；LIN Jiahong等[14]通过Arena软件对虎门港的港口资源进行分析，提出以总成本和港口生产能力为指标的改进方案。

综上，现有研究大多侧重不同类型航道的通过能力，少有研究航道同其他港口作业资源集成的文献；大多数学者主要采用统计和预测的方法来研究拖轮的配置，鲜有兼顾航道类型和拖轮调度的文献；大多数文献主要考虑作业成本、等待时间等因素，建立调度优化模型并设计启发式算法求解，罕有将拖轮调度和配置融为一体的研究。因此，笔者在现有研究基础上，将拖轮配置和调度优化问题集成，并兼顾复式航道的特点，建立相应的仿真优化模型，分析不同配置方案的各项关键指标，得出合理的配置方案。

1 问题描述

在多数复式航道的港口中，中间主航道用来通行大型船舶，且分时段单向通航，两侧副航道通行中小型船舶，且分进出单向通航。

船舶从到达到离开港口，主要有以下3个拖轮作业过程。① 进港：船舶需要轮拖拽进入泊位进行相关装卸作业；② 移泊：船舶需要拖轮的协助在不同泊位之间移动以便于货物的装卸；③ 出港：船舶装卸完毕后需要拖轮协助离开泊位进入航道完成出港作业。

问题描述为：在复式航道的港口中，根据船舶到达的种类和数量，如何确定配置拖轮的类型及数量，在能够满足调度需要的条件下使拖轮作业成本最小。

2 优化模型

一般情况下，船舶在抵港前24 h会通知港方，港方以24 h为一个作业周期来安排拖轮作业，以作业周期内拖轮耗油总成本最低为目标，构建拖轮作业调度模型。

2.1 假设条件

1) 假设有内外两个拖轮基地；

2) 只考虑船舶进港靠泊和离泊出港两个阶段的拖轮作业任务；

3) 进港船舶按照到达先后顺序排列，出港船舶按照预计离港时间(EDT)先后顺序排列；

4) 船舶通过航道的时间一定，且拖轮空驶的速度远大于牵引作业的速度。

2.2 符号定义

2.2.1 参 数

I为所有船舶的集合，I={1，2，…，m}；J为拖轮类型的集合，J={1，2，…，n}；P为每种拖轮编号的集合，P={1，2，…，s}；W为所有作业时段的集合，W={1，2，…，12}；SNS为所有拖轮数量；Sij为第i条船所需第j种拖轮的数量；TATi为第i条船的到达时刻；TLOTi为船舶i装卸作业所需时长；TTUi为最晚装卸时间；TEDTi为第i条船预计离港时间；TH为第i条船船舶进(出)港在航道上的航行时间；Tk为拖轮空驶通过航道的时间；TS为两只船舶在航道上航行所需预留的安全间隔时长；T0为一个作业时段的长度；C1为拖轮单次作业耗油成本；C2为拖轮空驶耗油成本；C0j为第j种类型拖轮耗油系数。

2.2.2 决策变量

TITi为第i条船开始进港的时刻，TOTi为第i条船开始出港的时刻。

2.2.3 过程变量

2.3 模型建立

2.3.1 目标函数

2.3.2 约束条件

(1)

p∈P

(2)

(3)

(4)

TOTi+1=max{TOTi+TH+Tk,TEDTi};i∈I,

(5)

(6)

(w-1)T0≤TITi

(7)

(w-1)T0≤TOTi

(8)

(w-1)T0

(9)

(w-1)T0

(10)

p∈P

(11)

(12)

TITi+TH+TLOTi≤TLTi;i∈I

(13)

TITi+TH+TLOTi≥TATi;i∈I

(14)

TOTi≥TEDTi;i∈I

(15)

其中：式(1)表示为船舶服务的拖轮数量必须满足该船需求；式(2)表示一条船舶只能由同一种类型拖轮进行作业；式(3)～(4)表示船舶进港时间限制；式(5)～(6)表示船舶出港时间限制；式(7)～(8)表示主航道船舶必须在进港时段入港、出港时段出港；式(9)～(10)表示主航道船舶必须在进港时段结束前完成进港作业、在出港时段结束前完成进港作业；式(11)～(12)分别表示在内、外拖轮基地的拖轮数量小于拖轮总数量；式(13)～(14)表示船舶在港作业的时间不得早于到达时间且不能超过限制时间；式(15)表示船舶实际离港时间不得早于预计离港时间。

2.4 求 解

拖轮调度是NP-hard问题，基于模型特点，设计了嵌入启发式规则的遗传算法。

2.4.1 多维实数编码

笔者采用多维实数编码方式进行问题求解。每条船只能由1种类型且最多不超过2艘拖轮共同作业，则所需染色体共分为3层，见图1。

图1 染色体编码示意Fig.1 Chromosome coding schemes

按照已知的阶段顺序编码，从左到右依次对应各阶段所需接受拖轮服务的船舶。第1行表示服务该船的拖轮类型。第2，3行表示服务该船的拖轮的编号。染色体的长度由所需进、出港作业的船舶数量决定。

2.4.2 初始种群生成

在初始种群生成时，采用了首艘拖轮可用的启发式规则生成种子染色体，加快最优解的搜索速度，提高算法效率，该染色体满足船舶拖轮类型、数量的匹配要求以及时间约束，主要步骤如下：

Step1：当船舶根据预定顺序准备进(出)港作业时，首先判断当前时段是进港时段还是出港时段；其次，判断船舶类型，大船在进港时段通过主航道进港，在出港时段通过主航道出港，否则需要等相应作业时段才能进行进(出)港作业，中小船可以随时通过副航道进(出)港。

Step2：根据船舶进港规则完成判断后，需完成船舶拖轮匹配任务，首先，更新已有的拖轮信息；其次，按照拖轮的编号判断该拖轮基地第一种类型的拖轮跟船舶是否匹配，如果能够匹配，判断该种类型的拖轮数量是否足够，如果条件都满足，则完成匹配过程；如果不满足，则按序转到下一种型号拖轮继续匹配，直到找到满足条件的拖轮。

Step3：如果该拖轮基地所有种类的拖轮都不满足船舶进(出)港的要求，则要考虑其他拖轮基地拖轮空驶的情况，需要按照第二步的顺序判断空驶的拖轮基地的拖轮的种类、数量是否满足调度要求。如果满足，则拖轮空驶；否则，船舶等待。

2.4.3 适应度函数与选择规则

采用轮盘赌进行个体的选择，设f(x)为目标函数，则F(x)=1/f(x)。

2.4.4 交叉与变异

考虑交叉操作的实际意义，把染色体的3层同点同时进行交叉，在变异操作时，赋予每一层不同的变异范围；同时在交叉变异之后增加染色体的修复过程如下：

Step1：对于i=1∶n，若第2行染色体CTT(i)=0时，重新生成CTT(i)，转到Step2；

Step2：判断生成染色体的拖轮数量是否与拖轮船舶数量匹配，若匹配转到Step3，否则，转到Step4；

Step3：判断第2行染色体与第3行染色体拖轮编号有没有重复，若重复，重新生成第3行染色体，否则，转到Step5；

Step4：将不匹配的染色体选出，重新生成，转到Step2；

Step5：染色体修复完毕。

终止条件

当迭代次数达到预先设置代数时，算法终止。

3 仿真模型

笔者基于离散事件仿真原理，以7 d为仿真周期，仿真周期内每24 h做一次拖轮调度，以min为仿真步长，通过Arena软件建立相应的仿真模型，主要仿真流程如下。

首先，读取数据模块获取本次仿真的拖轮配置信息，并读取每天抵港船舶的相关信息、及基于调度优化模型给出的每天拖轮调度方案；其次，船舶拖轮匹配模块基于读取的数据，实时给抵港船舶分配拖轮和作业时段；第三，航道行驶模块用于仿真船舶基于设定的复式航道通行规则进出港，拖轮牵引船舶通过相应航道的作业过程；第四，拖轮释放模块用于仿真拖轮牵引船舶完成相应的进出港任务后，拖轮释放的过程。各模块示意如图2～5。限于篇幅，在船舶拖轮匹配模块中，只截取该模块中大型拖轮判断部分。

图2 数据读取模块示意Fig.2 Data reading module

图4 航道通航模块示意Fig.4 Navigation module

图5 拖轮释放模块示意Fig.5 Tugboat release module

4 算例实验

4.1 算例描述

某港拥有一条复式航道，其中主航道只允许大型船舶通航，每2 h为一个时段交替进行进、出港作业，在主航道两侧各有一条副航道，设有内、外两个拖轮基地，并配有大、中、小这3类拖轮，到港船舶遵守该港的实际船期表，船舶在拖轮的辅助作业下通过主副航道所需时间分别为0.6、0.4 h，两船之间的安全间隔时间为0.25 h，拖轮空驶通过航道的时间为0.15 h。小、中、大型拖轮单次作业费用为1 000、1 300、1 600元，空驶费用均为300元，不同船型与作业所需拖轮数量匹配情况如表1，周期内船舶进、出港作业顺序安排情况已知。

表1 船型与拖轮匹配情况Table 1 Matching condition of ship type and tugboat

注：“—”表示不能匹配。

4.2 算例分析

笔者采用MATLAB编写的遗传算法程序，在I7-5700HQ CPU@2.70 GHz 64位的电脑上运行。为了测试遗传算法效率，笔者选取了不同规模的数据进行实验，算法程序运行效率良好且稳定。

通过优化算法计算研究周期内各种不同拖轮配置的耗油总成本，计算结果见表2。

表2 不同拖轮配置每天作业成本Table 2 Daily operation cost of different tugboat configuration

从表2中可看出：在船舶进出港作业中，配置6艘拖轮，拖轮作业总成本最小，如果只考虑港口作业成本，优先配置6艘拖轮。如果综合考虑拖轮作业成本与港口作业的忙闲程度，需要考虑各种配置下拖轮的闲置率。将优化算法生成的各种配置下最优的拖轮配置方案和拖轮的调度方案输入到已经建立的仿真模型中，通过仿真模型调用优化算法生成的最优解来计算各种拖轮配置下不同类型拖轮的闲置率，每种配置下各类型拖轮闲置率见表3。

表3 不同拖轮配置下各类型拖轮闲置率统计Table 3 Various tugboat idle rate with different tugboat configuration

由表3可知：从配置拖轮类型来看，小型拖轮的闲置率最高，大中型拖轮闲置率基本相同，表明小型拖轮数量充足，大中型拖轮需求基本相同；从配置拖轮数量来看，随着拖轮数量的增加，拖轮的闲置率呈现上升趋势，并且当配置6艘拖轮时，各种类型的拖轮闲置率较其他配置低，说明配备6艘拖轮大多数时候拖轮工作状态较为忙碌，并且在实际仿真过程中，存在因拖轮数量不足引起的船舶在港等待造成延误的情况，所以如果综合考虑拖轮作业成本及港口作业忙闲程度，可考虑增加一艘拖轮。

4.3 拖轮闲置率影响参数分析

4.3.1 船舶数量变化

考虑货物季节性和周期性变化引起船舶进出港数量变化，在成本最低的2/2/2配置下，周期内平均每天进出港船舶的数量分别增加和减少16%、33%，进行灵敏度分析，得出各种类型拖轮的闲置率的情况，见表4。

由表4可知，随着船舶抵港数量的增加，各类型拖轮的闲置率都呈下降趋势，可是在船舶数量增加的过程中，某种特定类型的拖轮闲置率变化不明显，由于特定时刻拖轮数量不足，部分船舶在港口等待，当前仿真周期内没有完成进出港作业，所以闲置率变化不明显。从拖轮类型来看，中型拖轮的闲置率最低，考虑到进出港作业量的变化，可以考虑增加一艘中型拖轮。

表4 拖轮闲置率随船舶数量变化情况Table 4 Tugboat idle rate changing with ship number

4.3.2 船舶类型变化

考虑未来船舶大型化趋势，在成本最低的2/2/2配置下，继续将进出港大型船舶的数量分别增加20%，40%，60%，根据计算得出数据分别绘制各种配置下的拖轮闲置率随大型船舶数量变化的折线图，如图6。

图6 拖轮闲置率变化情况
Fig.6 Variation of tugboat idle rate

由图6可看出：随着大型船舶数量的增加，大中型拖轮的闲置率下降，小型拖轮的闲置率反而上升，这是由于大型船舶不能由小型拖轮完成作业任务；中型拖轮的闲置率最低，波动性也较大，并且随着大型船舶数量的增加，中型拖轮闲置率趋于相同，这是因为大型船舶作业主要使用中型拖轮，引起中型拖轮数量不足。由文中算例可知：每艘大型船舶使用中型拖轮比使用大型拖轮费用低600元，故从未来船舶大型化的角度，增加一艘中型拖轮，能够更好地满足需求。

综上，从船舶数量变化以及船舶大型化的角度，兼顾拖轮的作业耗油总成本和闲置率两项指标，并考虑港口作业的忙闲程度，优先增加一艘中型拖轮。

5 结 语

笔者从经济效益的角度对复式航道港口拖轮配置问题进行研究，建立了嵌入拖轮调度优化方案的仿真模型，刻画了复式航道下，拖轮配置同抵港船舶的种类、数量和拖轮作业调度方案的关联关系，为相关问题提供了一个有效的解决思路。未来研究可以考虑航道跟泊位联合调度问题。

[1] 黄泰坤，王元战，李绍武，等.海港复式航道通过能力动态系统仿真[J].大连海事大学学报，2015，41(1)：20-26.

HUANG Taikun，WANG Yuanzhan，LI Shaowu，et al.Dynamic system simulation on throughput capacity of compound channel of sea port[J].JournalofDalianMaritimeUniversity，2015，41(1)：20-26.

[2] 唐国磊，王文渊，郭子坚，等.航道尺度对集装箱码头泊位有效利用率的影响[J].哈尔滨工程大学学报，2016，37(1)：127-131.

TANG Guolei，WANG Wenyuan，GUO Zijian，et al.Impact analysis of channel dimensions on the effective utilization ratio of container terminal berths[J].JournalofHarbinEngineeringUniversity，2016，37(1)：127-131.

[3] 姬利娜，张金伟，亢凤林.城市道路畸形交叉口的交通改善方法[J].重庆交通大学学报(自然科学版)，2012，31(6)：1185-1188.

JI Lina，ZHANG Jinwei，KANG Fenglin.Traffic improvement method of deformed intersection in urban road[J].JournalofChongqingJiaotongUniversity(NaturalScience)， 2012，31(6)：1185-1188.

[4] 王江涛，马驷.预测通道客运分担率的MNL模型特性变量选取[J].重庆交通大学学报(自然科学版)，2010，29(6)：947-950.

WANG Jiangtao，MA Si.MNL model characteristic variables selection on forecasting corridor mode split[J].JournalofChongqingJiaotongUniversity(NaturalScience)， 2010，29(6)：947-950.

[5] 陆海波.宁波港拖轮船队优化配置研究[D].上海：上海海事大学，2007.

LU Haibo.StudyonOptimalAllocationofTugboatFleetinNingboHarbor[D].Shanghai：Shanghai Maritime University，2007.

[6] 刘志雄，王少梅.港口拖轮作业的计算机仿真研究[J].系统仿真学报，2004，16(1)：45-47.

LIU Zhixiong，WANG Shaomei.The computer simulation study of port tugboat operation[J].JournalofSystemSimulation，2004，16(1)：45-47.

[7] WANG Su，KAKU I，CHEN Guoyue，et al.Research on the modeling of tugboat assignment problem in container terminal[J].AdvancedMaterialsResearch，2012，433/440：1957-1961.

[8] 王巍，赵宏，李强.面向多停泊基地的港口拖轮调度优化研究[J].计算机工程与应用，2013，49(13)：8-12.

WANG Wei，ZHAO Hong，LI Qiang.Multi-objectives optimization for port tugboat scheduling considering multi-anchorage bases[J].ComputerEngineeringandApplication，2013，49 (13)：8-12.

[9] HE Tao，YE Wenwen.Research of tugboat operation scheduling problem based on hybrid evolutionary strategy[C]//2010 2ndInternationalConferenceonInformationScience&Engineering.U S A：IEEE，2010：1438-1441.

[10] WANG Su，ZHENG Kai，ZHENG Jun，et al.An improved discrete particle swarm optimization for tugboat scheduling problem in container terminal[J].InternationalConferenceonInformationManagement，2011，34(7)：573-579.

[11] 徐奇，李娜，靳志宏.考虑多阶段共用平行机特征的拖轮作业模式优化[J].运筹与管理，2014，23(5)：178-186.

XU Qi，LI Na，JIN Zhihong.Optimization on tugboat operation mode considering characteristics of the multi-stage common parallel machines[J].OperationsResearchandManagementScience，2014，23(5)：178-186.

[12] XU Q，SHAO Q Q，JIN Z H.Optimization on tugboat operation scheduling based upon the hybrid flow shop arrangement[J].SystemEngineeringTheoryandPractice，2014，34(2)：485-493.

[13] YU Wenhui.Heuristic algorithm for simulation and optimization system of port tugboats allocation[C]//2011InternationalConferenceonInternetComputingandInformationServices.U.S.A：IEEE，2011：306-309.

[14] LIN Jiahong，GAO Benhe，ZHANG Canrong.Simulation-based investment planning for human port[J].SimulationModelingPracticeandTheory，2014，40(1)：161-175.

(责任编辑：刘 韬)

Simulation Optimization of Compound Channel Port Tugboat Configuration

ZHENG Hongxing，XU Haidong，CAO Honglei

(Transportation Management College，Dalian Maritime University，Dalian 116026，Liaoning，P.R.China)

In order to better guide the compound channel tugboat configuration，a tugboat operation simulation model was put forward.Firstly，based on the characteristics of compound channel，the Arena simulation model was proposed，which embedded operation scheduling optimization model，with the aim of minimizing the total tugboat fuel consumption cost.Secondly，the embedded heuristic rules genetic algorithm was designed to solve the proposed model.Thirdly，through various simulation tests，the present optimal configuration scheme was selected，considering total tugboat fuel cost and tugboat idle rate.Then，through the simulation analysis on the tugboat idle rate changing with ship types and ship numbers as well as the combination with large scale trend of ship in the future，the future optimal tugboat configuration scheme was given.

waterway engineering；compound channel；tugboat configuration；genetic algorithm；tugboat idle rate

10.3969/j.issn.1674-0696.2017.08.18

2016-05-02；

2016-09-16

国家自然科学基金项目(71473024)

郑红星(1971—)，男，河北迁安人，副教授，博士，主要从事物流系统及仿真方面的研究。E-mail：zhredstar@dlmu.edu.cn。

徐海栋(1991—)，男，山东潍坊人，硕士研究生，主要从事物流系统及仿真方面的研究。E-mail：1835351671@qq.com。

U692.4

A

1674-0696(2017)08-102-08