面向多停泊基地的港口拖轮调度优化研究

王巍，赵宏，李强

1.天津工业大学 经济学院，天津 300387

2.天津港（集团）有限公司 科技设备部，天津 300461

面向多停泊基地的港口拖轮调度优化研究

王巍1，赵宏1，李强2

1.天津工业大学 经济学院，天津 300387

2.天津港（集团）有限公司 科技设备部，天津 300461

1 引言

船舶进入港口航道时需要拖轮护航和协助靠泊。同样，船舶在离开泊位出港时，也需要拖轮协助完成。另外，船舶可能在港口不同泊位之间装卸货物，还需要拖轮协助进行不同泊位间的移动。因此，拖轮作业在港口船舶装卸作业流程中具有相当重要的作用，拖轮作业调度的好坏将直接影响船舶的作业效率和进出港时间。

不同类型的船舶作业所需要的拖轮类型和数量互不相同，有的船舶需要一艘拖轮，有的则需要两艘甚至更多。因此，拖轮调度具有多机协同作业的特点。此外，随着现代港口规模的不断扩大和进出港船舶的不断增多，很多港口建设了多个拖轮停泊基地，实施分区域拖轮作业管理，这就使得拖轮调度的优化和决策成为一个更加复杂的问题。

目前，针对上述问题的研究主要集中在拖轮作业过程的仿真和资源配置方面[1-4]，考虑多停泊基地的拖轮调度优化研究尚未见报道。本文首先分析了拖轮调度的特点，并从多处理器任务调度的角度进行了阐述。其次，以最大完工时间和总作业油耗最小化为优化目标，建立了考虑多拖轮停泊基地的拖轮调度多目标优化模型。最后，采用演化策略算法对所建模型进行优化，并用算例进行了验证，取得了较好的结果。

2 拖轮调度的多处理器任务特点

多处理器任务调度强调同一时刻，存在一个或多个处理器来完成对某一个任务的作业，其产生于并行计算和计算机系统。多处理器任务调度主要分为并行处理器和专用处理器两种类型。在并行处理器中，强调每个处理器均是同类型的，并且按照任务所要求的处理器数量，所有处理器中的任意组合均可完成所给出的任务。在专用处理器中，每个处理器是不同类型的，每个任务均对应于一个处理器集合，任务的完成需要该集合中所有处理器同时工作[5-11]。

拖轮作业过程中，拖轮与船舶之间存在一定的配比关系。以某港口的拖轮作业为例，其拥有883 kW、1 912 kW、2 354 kW、2 500 kW、2 942 kW和3 678 kW等6种不同类型的拖轮，各类型拖轮的数量分别为{4，8，4，6，4，4}艘，根据船舶船长的拖轮配置方法如表1所示。

表1 拖轮与船舶的配比关系

首先，不同船型所需要的拖轮类型和数量是有差异的，每种船型所对应的拖轮集合均不同，拖轮集合中的拖轮总数均大于匹配原则所要求的数量（1艘或者2艘）。因此，每种船型对应着多个拖轮子集单元。拖轮作业的这种特点正好对应着多处理器任务调度的一般集合特性。

其次，对于拖轮调度问题，由于相同类型的拖轮数量均大于1（即存在多同类机的情况），每种船型所对应的拖轮集合中，都存在着多艘相同类型的拖轮。因此，拖轮调度属于基于多同类机的一般集合多处理器任务调度问题。

3 考虑多停泊基地的拖轮调度多目标优化建模

3.1 最大完工时间的计算

根据表1，这里分为两种情况讨论：

（1）第k艘船舶只需要一艘拖轮服务

假设分配给第k艘船舶的拖轮类型为i，第i种类型的拖轮数量为，因此，根据最短距离作业的原则，从第i种类型拖轮中，选择与第k艘船舶的起始位置用Pk_start距离最短的拖轮作为第k艘船舶的服务拖轮。因此，如果选择拖轮为第k艘船舶提供作业服务，那么第k艘船舶在拖轮上的作业完工时间表示如下所示。

①限制交叉作业模式：

（2）第k艘船舶需要两艘拖轮同时服务

假设被分配的拖轮类型分别是i1和i2，对于两种不同类型的拖轮，根据最短距离作业的原则，最终选择的拖轮分别是和。如果拖轮上的上次任务序号为k1，拖轮上的上次任务序号为k2，那么拖轮上第k1艘的作业完工时间表示为，拖轮上第k2艘的作业完工时间表示为。因此，可以通过公式（3）、（4）、（5）和（6）得到和，和表示拖轮和在分别完成对应的第k1和k2艘船舶的作业后，到达第k艘船舶起始地点的时间。

①限制允许交叉作业模式：

由上述公式可以得到不同拖轮配置数量情况下，第k艘船舶在拖轮上的作业完工时间。由于分配在拖轮上的船舶作业任务数量为，拖轮上所分配的所有船舶作业任务的最后完工时间可以表示为，可以由上述公式计算得到。因此，所有拖轮完成任务作业时间的最大值即为所有船舶作业任务的完工时间，如果用f1表示，则有：

3.2 总作业油耗的计算

可以表示如下：

3.3 考虑最大完工时间和作业油耗双目标最小的拖轮作业调度建模

如果考虑最大完工时间和作业油耗的多目标优化，那么这里采用加权平均的多目标优化方法建立拖轮作业调度优化模型。如果用f表示最大完工时间和总作业油耗的加权平均值，用F表示最大完工时间和总作业油耗多目标最小化函数值，那么结合公式（9）和（13）存在以下关系：

公式（14）和（15）中，α为加权系数，且0＜α＜1。

4 演化策略算法

演化策略算法，也称为进化策略算法，属于进化算法的一种[12-13]。本文采用(μ+λ)-ES演化策略算法来求解拖轮作业调度优化问题。在(μ+λ)-ES演化策略中，由μ个父体通过重组和变异产生λ个后代，然后从μ个父代和λ个后代所组成的(μ+λ)个个体中，选择μ个适应值最好的个体作为下一代的父体。

4.1 基于轮盘赌概率分配的多维实数编码和解码

4.1.1 多维实数编码

假设需要拖轮服务的到港船舶数量为n艘，演化策略算法的种群数量为D，那么种群中的第p个个体编码可以定义如表2所示。

表2 个体编码

表2中，Vpq表示不同船长的船型，具体根据表1，可以将船舶分为100 m以下，100～200 m，200～250 m，250～300 m以及300 m以上5种不同船型。因此，可以分别用数字1，2，3，4，5表示，即Vpq∈{1，2，3，4，5}。

根据表1中拖轮与船舶的配比关系，船舶船长，拖轮可以分为两大类型：一类是只需要一艘拖轮服务；另外一类是需要两艘拖轮服务。因此，apq和bpq为大于0的实数，可以表示如下：

4.1.2 基于轮盘赌概率分配的解码

（1）归一化处理

主要是将基因值apq和bpq经过计算后转换为（0，1）之间的概率值cpq和dpq，计算方法是将种群内各个个体相同基因位置上的基因值进行累加计算，然后将各个个体基因值与累加值相除即可。

（2）根据概率分配拖轮类型

对于每种船型，首先要计算其对应的拖轮类型中每种拖轮所对应的轮盘赌概率，然后根据概率值cpq和dpq，分配对应的拖轮类型。

假设个体编码中船舶q的船型Vpq对应的拖轮集合为Sq，集合Sq中有xq种不同的拖轮类型。集合Sq中xq种不同类型拖轮被分配船型Vpq的概率均是相等的，即概率为1/xq。因此，设定Sq中每种不同类型拖轮被分配船舶的轮盘赌概率为：

4.2 基于三点交叉互换的重组算子

重组算子采用三点交叉互换的杂交方法，以双亲双子法产生后代个体。首先随机从μ个个体中选择2个个体进行重组操作，然后在2个父代个体中随即选择3个交叉互换点，从而将父代个体分隔为4段，最后采取隔段互换的方式进行互换，从而得到2个子代个体。具体如图1所示。

4.3 基于个体内部基因互换的变异算子

变异操作采用的方法：在子代个体中，随机选择两种船舶船型相同的基因值，如果其拖轮分配不同，将它们的拖轮分配进行互换，具体如图2所示。对于每个子代个体，变异算子中设定随机选择基因值互换多次。

图2 基因值互换的变异算子

5 实证分析

在船舶靠离港作业过程中，不同船型的拖轮作业时间有一定差异。根据船型的大小，随机产生60艘船舶的相关作业数据，如表3所示。

表3 60艘船舶的作业数据

表4 不同位置之间的行驶时间min

表5 不同加权系数下最大完工时间（f1）和总作业油耗（f2）双目标优化的计算结果

表3中，分别用数字1，2，3，4，5表示5种不同船长的船型，作业时间则主要是指船舶在靠泊、离泊和移泊时的拖轮作业时间。

T1，T2，T3，T4，T5，T6，T7和T8分别表示8个不同的码头位置，T0表示船舶进港或离港时与拖轮在航道会合的位置。为了计算方便，这9种不同的位置以及与两个拖轮基地之间的距离用行驶时间来代替，具体数据如表4所示。所有6种类型的拖轮平均分配在两个拖轮基地，即两个拖轮基地的拖轮类型和数量是相同的。

在拖轮作业过程中，如果限制两个拖轮基地的拖轮进行交叉作业，那么此时，拖轮基地1的拖轮主要针对T1，T2，T3，T4这4个码头的船舶进行服务；而拖轮基地2的拖轮则针对T5，T6，T7，T8这4个码头的船舶进行服务。

设定表1中6种拖轮的运行油耗依次为{0.2，0.3，0.36，0.4，0.56，0.64}（t/h）。

设置演化策略算法的最大迭代次数为1 000，父代种群数量μ为50，子代种群数量λ为40，分别设置加权系数α= {0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9}，用公式（15）所建立的以最大完工时间和总作业油耗双目标最小的优化调度模型，不同加权系数设置下连续优化计算20次，计算结果如表5所示。

从表5的计算结果看，采用两种不同的作业模式，不同加权系数情况下，双目标优化找到的最小值中，最大完工时间和总作业油耗均好于相对应作业模式下的仿真运行结果。其中，最大完工时间最小值相比仿真运行结果取得较大的改善，不同作业模式下均减少了约16%。

同时，不同的作业模式对结果也有着不同的影响。其中，允许交叉作业模式下，双目标优化情况下的最大完工时间最小值明显好于限制交叉作业模式。这说明，尽管使用两个拖轮停泊基地，如果采用允许交叉作业模式将更能充分利用拖轮资源。

6 结束语

拖轮调度是港口生产系统的一个重要组成部分，其优化问题直接影响船舶能否及时进出。本文结合多处理器任务调度理论，以最大完工时间和总作业油耗双目标最小化为目标，对面向多停泊基地的拖轮作业调度问题进行了建模分析，并在拖轮调度模型中考虑了两种不同的作业模式。采用演化策略算法对多停泊基地拖轮作业调度多目标优化问题进行了计算，并对演化策略算法的编码和解码、重组算子和变异算子进行了设计。计算结果表明，演化策略算法可以得到较好的优化结果。

[1]董良才，徐子奇，宓为建.基于遗传算子粒子群算法的拖轮动态调度[J].数学的实践与认识，2012，42（6）：122-133.

[2]何涛，朱宏辉.遗传算法在拖轮调度中的应用[J].物流技术，2008，27（4）：138-139.

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

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

[5]刘莎，杨宏来.基于任务紧迫度的多处理器任务调度算法[J].电子测量技术，2012，35（9）：45-48.

[6]Jin S Y，Schiavone G，Turgut D.A performance study of multiprocessor task scheduling algorithms[J].Journal of Supercomputing，2008，43（1）：77-97.

[7]轩华，唐立新.带多处理器任务的动态混合流水车间调度问题[J].计算机集成制造系统，2007，13（11）：2254-2260.

[8]Ying K C，Lin S W.Multiprocessor task scheduling in multistage hybrid flow-shops：an ant colony system approach[J]. International Journal of Production，2006，44（16）：3161-3177.

[9]Ercan M F，Oğuz C P.Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks[J]. Computers and Electrical Engineering，2005，31（8）：537-555.

[10]Zhong Y，Yang J.A hybrid genetic algorithm for tasks scheduling in parallel multiprocessor systems[J].Journal of Fudan University：Natural Science，2004，43（5）：918-922.

[11]Oğuz C，Zinder Y，Do V，et al.Hybrid flow-shop scheduling problems with multiprocessor task systems[J].European Journal of Operations Research，2004，152（1）：115-131.

[12]毕志升，王甲海，印鉴.基于差分演化算法的软子空间聚类[J].计算机学报，2012，35（10）：2116-2128.

[13]牛思先，苏玉刚.基于多目标演化算法的交通系统实时优化技术[J].统计与决策，2011（1）：61-64.

WANG Wei1,ZHAO Hong1,LI Qiang2

1.School of Economy,Tianjin Polytechnic University,Tianjin 300387,China
2.Technology and Equipment Department,Tianjin Port（Group）Co.,Ltd.,Tianjin 300461,China

The tugboat scheduling is a typical multiprocessor tasks scheduling problem.A kind of port tugboat scheduling problem with multi-anchorage bases and different operation modes is presented,and the tugboat scheduling optimization model which objective is to minimize both the maximum completion time and total operation fuel wastage of all tugboats is described.The evolutionary strategy algorithm is applied to optimize the tugboat operation scheduling,and the multi-dimension real encoding and decoding based on the roulette probability assignment is introduced.Finally,the calculation results prove that the evolutionary strategy algorithm can effectively optimize the port tugboat scheduling problem,and the optimization results of the maximum completion time are improved and reduced about 16%than the simulation results on condition of different tugboat operation modes.Moreover,the calculation results show that different operation modes have much effect on the tugboat scheduling.

tugboat scheduling;multi-anchorage bases;multiprocessor tasks;evolutionary strategy algorithm;multi-objectives optimization

拖轮调度是典型的多处理器任务调度问题，针对多停泊基地和不同作业模式下的拖轮调度，以最大完工时间和总作业油耗最小化为目标，建立了拖轮调度多目标优化模型。采用演化策略算法对多停泊基地拖轮调度优化问题进行计算，提出一种基于轮盘赌概率分配的编码和解码方法。计算结果表明了演化策略算法的有效性和可行性，优化后的最大完工时间最小值相比仿真运行结果取得较大的改善，不同作业模式下均减少了约16%；计算结果还表明不同作业模式对拖轮调度结果会产生较大影响。

拖轮调度；多停泊基地；多处理器任务；演化策略算法；多目标优化

A

TP39

10.3778/j.issn.1002-8331.1302-0008

WANG Wei,ZHAO Hong,LI Qiang.Multi-objectives optimization for port tugboat scheduling considering multi-anchorage bases.Computer Engineering and Applications,2013,49（13）：8-12.

国家自然科学基金（No.70801047）；国家软科学研究计划项目（No.2011GXS2D015）；天津市哲学社会科学规划项目（No.TJYY11-2-042）。

王巍（1980—），女，博士，副教授，硕士生导师，研究方向为系统优化，机器学习，计量经济；赵宏（1963—），女，博士，教授，研究方向为产业经济学；李强（1982—），男，博士后，高级工程师，研究方向为港口设备管理，生产调度优化。E-mail：wangweiuser@126.com

2013-02-04

2013-03-24

1002-8331（2013）13-0008-05

CNKI出版日期：2013-03-29http://www.cnki.net/kcms/detail/11.2127.TP.20130329.1701.021.html