王巍，趙宏，李強

1.天津工業(yè)大學 經(jīng)濟學院，天津 300387

2.天津港（集團）有限公司 科技設備部，天津 300461

面向多停泊基地的港口拖輪調(diào)度優(yōu)化研究

王巍1，趙宏1，李強2

1.天津工業(yè)大學 經(jīng)濟學院，天津 300387

2.天津港（集團）有限公司 科技設備部，天津 300461

1 引言

船舶進入港口航道時需要拖輪護航和協(xié)助靠泊。同樣，船舶在離開泊位出港時，也需要拖輪協(xié)助完成。另外，船舶可能在港口不同泊位之間裝卸貨物，還需要拖輪協(xié)助進行不同泊位間的移動。因此，拖輪作業(yè)在港口船舶裝卸作業(yè)流程中具有相當重要的作用，拖輪作業(yè)調(diào)度的好壞將直接影響船舶的作業(yè)效率和進出港時間。

不同類型的船舶作業(yè)所需要的拖輪類型和數(shù)量互不相同，有的船舶需要一艘拖輪，有的則需要兩艘甚至更多。因此，拖輪調(diào)度具有多機協(xié)同作業(yè)的特點。此外，隨著現(xiàn)代港口規(guī)模的不斷擴大和進出港船舶的不斷增多，很多港口建設了多個拖輪停泊基地，實施分區(qū)域拖輪作業(yè)管理，這就使得拖輪調(diào)度的優(yōu)化和決策成為一個更加復雜的問題。

目前，針對上述問題的研究主要集中在拖輪作業(yè)過程的仿真和資源配置方面[1-4]，考慮多停泊基地的拖輪調(diào)度優(yōu)化研究尚未見報道。本文首先分析了拖輪調(diào)度的特點，并從多處理器任務調(diào)度的角度進行了闡述。其次，以最大完工時間和總作業(yè)油耗最小化為優(yōu)化目標，建立了考慮多拖輪停泊基地的拖輪調(diào)度多目標優(yōu)化模型。最后，采用演化策略算法對所建模型進行優(yōu)化，并用算例進行了驗證，取得了較好的結果。

2 拖輪調(diào)度的多處理器任務特點

多處理器任務調(diào)度強調(diào)同一時刻，存在一個或多個處理器來完成對某一個任務的作業(yè)，其產(chǎn)生于并行計算和計算機系統(tǒng)。多處理器任務調(diào)度主要分為并行處理器和專用處理器兩種類型。在并行處理器中，強調(diào)每個處理器均是同類型的，并且按照任務所要求的處理器數(shù)量，所有處理器中的任意組合均可完成所給出的任務。在專用處理器中，每個處理器是不同類型的，每個任務均對應于一個處理器集合，任務的完成需要該集合中所有處理器同時工作[5-11]。

拖輪作業(yè)過程中，拖輪與船舶之間存在一定的配比關系。以某港口的拖輪作業(yè)為例，其擁有883 kW、1 912 kW、2 354 kW、2 500 kW、2 942 kW和3 678 kW等6種不同類型的拖輪，各類型拖輪的數(shù)量分別為{4，8，4，6，4，4}艘，根據(jù)船舶船長的拖輪配置方法如表1所示。

表1 拖輪與船舶的配比關系

首先，不同船型所需要的拖輪類型和數(shù)量是有差異的，每種船型所對應的拖輪集合均不同，拖輪集合中的拖輪總數(shù)均大于匹配原則所要求的數(shù)量（1艘或者2艘）。因此，每種船型對應著多個拖輪子集單元。拖輪作業(yè)的這種特點正好對應著多處理器任務調(diào)度的一般集合特性。

其次，對于拖輪調(diào)度問題，由于相同類型的拖輪數(shù)量均大于1（即存在多同類機的情況），每種船型所對應的拖輪集合中，都存在著多艘相同類型的拖輪。因此，拖輪調(diào)度屬于基于多同類機的一般集合多處理器任務調(diào)度問題。

3 考慮多停泊基地的拖輪調(diào)度多目標優(yōu)化建模

3.1 最大完工時間的計算

根據(jù)表1，這里分為兩種情況討論：

（1）第k艘船舶只需要一艘拖輪服務

假設分配給第k艘船舶的拖輪類型為i，第i種類型的拖輪數(shù)量為，因此，根據(jù)最短距離作業(yè)的原則，從第i種類型拖輪中，選擇與第k艘船舶的起始位置用Pk_start距離最短的拖輪作為第k艘船舶的服務拖輪。因此，如果選擇拖輪為第k艘船舶提供作業(yè)服務，那么第k艘船舶在拖輪上的作業(yè)完工時間表示如下所示。

①限制交叉作業(yè)模式：

（2）第k艘船舶需要兩艘拖輪同時服務

假設被分配的拖輪類型分別是i1和i2，對于兩種不同類型的拖輪，根據(jù)最短距離作業(yè)的原則，最終選擇的拖輪分別是和。如果拖輪上的上次任務序號為k1，拖輪上的上次任務序號為k2，那么拖輪上第k1艘的作業(yè)完工時間表示為，拖輪上第k2艘的作業(yè)完工時間表示為。因此，可以通過公式（3）、（4）、（5）和（6）得到和，和表示拖輪和在分別完成對應的第k1和k2艘船舶的作業(yè)后，到達第k艘船舶起始地點的時間。

①限制允許交叉作業(yè)模式：

由上述公式可以得到不同拖輪配置數(shù)量情況下，第k艘船舶在拖輪上的作業(yè)完工時間。由于分配在拖輪上的船舶作業(yè)任務數(shù)量為，拖輪上所分配的所有船舶作業(yè)任務的最后完工時間可以表示為，可以由上述公式計算得到。因此，所有拖輪完成任務作業(yè)時間的最大值即為所有船舶作業(yè)任務的完工時間，如果用f1表示，則有：

3.2 總作業(yè)油耗的計算

可以表示如下：

3.3 考慮最大完工時間和作業(yè)油耗雙目標最小的拖輪作業(yè)調(diào)度建模

如果考慮最大完工時間和作業(yè)油耗的多目標優(yōu)化，那么這里采用加權平均的多目標優(yōu)化方法建立拖輪作業(yè)調(diào)度優(yōu)化模型。如果用f表示最大完工時間和總作業(yè)油耗的加權平均值，用F表示最大完工時間和總作業(yè)油耗多目標最小化函數(shù)值，那么結合公式（9）和（13）存在以下關系：

公式（14）和（15）中，α為加權系數(shù)，且0＜α＜1。

4 演化策略算法

演化策略算法，也稱為進化策略算法，屬于進化算法的一種[12-13]。本文采用(μ+λ)-ES演化策略算法來求解拖輪作業(yè)調(diào)度優(yōu)化問題。在(μ+λ)-ES演化策略中，由μ個父體通過重組和變異產(chǎn)生λ個后代，然后從μ個父代和λ個后代所組成的(μ+λ)個個體中，選擇μ個適應值最好的個體作為下一代的父體。

4.1 基于輪盤賭概率分配的多維實數(shù)編碼和解碼

4.1.1 多維實數(shù)編碼

假設需要拖輪服務的到港船舶數(shù)量為n艘，演化策略算法的種群數(shù)量為D，那么種群中的第p個個體編碼可以定義如表2所示。

表2 個體編碼

表2中，Vpq表示不同船長的船型，具體根據(jù)表1，可以將船舶分為100 m以下，100～200 m，200～250 m，250～300 m以及300 m以上5種不同船型。因此，可以分別用數(shù)字1，2，3，4，5表示，即Vpq∈{1，2，3，4，5}。

根據(jù)表1中拖輪與船舶的配比關系，船舶船長，拖輪可以分為兩大類型：一類是只需要一艘拖輪服務；另外一類是需要兩艘拖輪服務。因此，apq和bpq為大于0的實數(shù)，可以表示如下：

4.1.2 基于輪盤賭概率分配的解碼

（1）歸一化處理

主要是將基因值apq和bpq經(jīng)過計算后轉換為（0，1）之間的概率值cpq和dpq，計算方法是將種群內(nèi)各個個體相同基因位置上的基因值進行累加計算，然后將各個個體基因值與累加值相除即可。

（2）根據(jù)概率分配拖輪類型

對于每種船型，首先要計算其對應的拖輪類型中每種拖輪所對應的輪盤賭概率，然后根據(jù)概率值cpq和dpq，分配對應的拖輪類型。

假設個體編碼中船舶q的船型Vpq對應的拖輪集合為Sq，集合Sq中有xq種不同的拖輪類型。集合Sq中xq種不同類型拖輪被分配船型Vpq的概率均是相等的，即概率為1/xq。因此，設定Sq中每種不同類型拖輪被分配船舶的輪盤賭概率為：

4.2 基于三點交叉互換的重組算子

重組算子采用三點交叉互換的雜交方法，以雙親雙子法產(chǎn)生后代個體。首先隨機從μ個個體中選擇2個個體進行重組操作，然后在2個父代個體中隨即選擇3個交叉互換點，從而將父代個體分隔為4段，最后采取隔段互換的方式進行互換，從而得到2個子代個體。具體如圖1所示。

4.3 基于個體內(nèi)部基因互換的變異算子

變異操作采用的方法：在子代個體中，隨機選擇兩種船舶船型相同的基因值，如果其拖輪分配不同，將它們的拖輪分配進行互換，具體如圖2所示。對于每個子代個體，變異算子中設定隨機選擇基因值互換多次。

圖2 基因值互換的變異算子

5 實證分析

在船舶靠離港作業(yè)過程中，不同船型的拖輪作業(yè)時間有一定差異。根據(jù)船型的大小，隨機產(chǎn)生60艘船舶的相關作業(yè)數(shù)據(jù)，如表3所示。

表3 60艘船舶的作業(yè)數(shù)據(jù)

表4 不同位置之間的行駛時間min

表5 不同加權系數(shù)下最大完工時間（f1）和總作業(yè)油耗（f2）雙目標優(yōu)化的計算結果

表3中，分別用數(shù)字1，2，3，4，5表示5種不同船長的船型，作業(yè)時間則主要是指船舶在靠泊、離泊和移泊時的拖輪作業(yè)時間。

T1，T2，T3，T4，T5，T6，T7和T8分別表示8個不同的碼頭位置，T0表示船舶進港或離港時與拖輪在航道會合的位置。為了計算方便，這9種不同的位置以及與兩個拖輪基地之間的距離用行駛時間來代替，具體數(shù)據(jù)如表4所示。所有6種類型的拖輪平均分配在兩個拖輪基地，即兩個拖輪基地的拖輪類型和數(shù)量是相同的。

在拖輪作業(yè)過程中，如果限制兩個拖輪基地的拖輪進行交叉作業(yè)，那么此時，拖輪基地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）。

設置演化策略算法的最大迭代次數(shù)為1 000，父代種群數(shù)量μ為50，子代種群數(shù)量λ為40，分別設置加權系數(shù)α= {0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9}，用公式（15）所建立的以最大完工時間和總作業(yè)油耗雙目標最小的優(yōu)化調(diào)度模型，不同加權系數(shù)設置下連續(xù)優(yōu)化計算20次，計算結果如表5所示。

從表5的計算結果看，采用兩種不同的作業(yè)模式，不同加權系數(shù)情況下，雙目標優(yōu)化找到的最小值中，最大完工時間和總作業(yè)油耗均好于相對應作業(yè)模式下的仿真運行結果。其中，最大完工時間最小值相比仿真運行結果取得較大的改善，不同作業(yè)模式下均減少了約16%。

同時，不同的作業(yè)模式對結果也有著不同的影響。其中，允許交叉作業(yè)模式下，雙目標優(yōu)化情況下的最大完工時間最小值明顯好于限制交叉作業(yè)模式。這說明，盡管使用兩個拖輪停泊基地，如果采用允許交叉作業(yè)模式將更能充分利用拖輪資源。

6 結束語

拖輪調(diào)度是港口生產(chǎn)系統(tǒng)的一個重要組成部分，其優(yōu)化問題直接影響船舶能否及時進出。本文結合多處理器任務調(diào)度理論，以最大完工時間和總作業(yè)油耗雙目標最小化為目標，對面向多停泊基地的拖輪作業(yè)調(diào)度問題進行了建模分析，并在拖輪調(diào)度模型中考慮了兩種不同的作業(yè)模式。采用演化策略算法對多停泊基地拖輪作業(yè)調(diào)度多目標優(yōu)化問題進行了計算，并對演化策略算法的編碼和解碼、重組算子和變異算子進行了設計。計算結果表明，演化策略算法可以得到較好的優(yōu)化結果。

[1]董良才，徐子奇，宓為建.基于遺傳算子粒子群算法的拖輪動態(tài)調(diào)度[J].數(shù)學的實踐與認識，2012，42（6）：122-133.

[2]何濤，朱宏輝.遺傳算法在拖輪調(diào)度中的應用[J].物流技術，2008，27（4）：138-139.

[3]陸海波.寧波港拖輪船隊優(yōu)化配置研究[D].上海：上海海事大學，2007.

[4]劉志雄，王少梅.港口拖輪作業(yè)的計算機仿真研究[J].系統(tǒng)仿真學報，2004，16（1）：45-48.

[5]劉莎，楊宏來.基于任務緊迫度的多處理器任務調(diào)度算法[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]軒華，唐立新.帶多處理器任務的動態(tài)混合流水車間調(diào)度問題[J].計算機集成制造系統(tǒng)，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]牛思先，蘇玉剛.基于多目標演化算法的交通系統(tǒng)實時優(yōu)化技術[J].統(tǒng)計與決策，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

拖輪調(diào)度是典型的多處理器任務調(diào)度問題，針對多停泊基地和不同作業(yè)模式下的拖輪調(diào)度，以最大完工時間和總作業(yè)油耗最小化為目標，建立了拖輪調(diào)度多目標優(yōu)化模型。采用演化策略算法對多停泊基地拖輪調(diào)度優(yōu)化問題進行計算，提出一種基于輪盤賭概率分配的編碼和解碼方法。計算結果表明了演化策略算法的有效性和可行性，優(yōu)化后的最大完工時間最小值相比仿真運行結果取得較大的改善，不同作業(yè)模式下均減少了約16%；計算結果還表明不同作業(yè)模式對拖輪調(diào)度結果會產(chǎn)生較大影響。

拖輪調(diào)度；多停泊基地；多處理器任務；演化策略算法；多目標優(yōu)化

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）；天津市哲學社會科學規(guī)劃項目（No.TJYY11-2-042）。

王巍（1980—），女，博士，副教授，碩士生導師，研究方向為系統(tǒng)優(yōu)化，機器學習，計量經(jīng)濟；趙宏（1963—），女，博士，教授，研究方向為產(chǎn)業(yè)經(jīng)濟學；李強（1982—），男，博士后，高級工程師，研究方向為港口設備管理，生產(chǎn)調(diào)度優(yōu)化。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