李伯棠，王智利，周海英，任陽(yáng)軍

(1.廣州航海學(xué)院 港口與航運(yùn)管理學(xué)院，廣東 廣州 510725；2.上海海事大學(xué) 經(jīng)濟(jì)管理學(xué)院，上海 201306)

0 引言

近年來(lái)，隨著船舶的大型化發(fā)展，大型船舶進(jìn)出港口靠離碼頭、在港內(nèi)不同碼頭和泊位之間貨物裝卸、系離浮筒和臨時(shí)拋錨等輔助作業(yè)都需要拖輪協(xié)助完成。由于不同船舶(如散貨船、集裝箱船和郵輪等)的操縱性能及其尺寸存在差異，船舶靠離的區(qū)域、所需拖輪數(shù)量和作業(yè)時(shí)間均不相同。同時(shí)，隨著港口吞吐量的上升，進(jìn)出港口的船舶數(shù)量不斷增加，港口會(huì)建設(shè)多個(gè)拖輪停泊基地來(lái)實(shí)施拖輪作業(yè)管理，拖輪往往被調(diào)派到不同的基地開(kāi)展輔助作業(yè)，使得拖輪調(diào)度成為一個(gè)更加復(fù)雜的問(wèn)題。傳統(tǒng)的拖輪調(diào)度主要依靠調(diào)度人員的經(jīng)驗(yàn)，隨著輔助作業(yè)量和停泊基地?cái)?shù)量的增加，該方法不再適用。因此，尋找科學(xué)高效的拖輪調(diào)度計(jì)劃成為解決問(wèn)題的關(guān)鍵。

本文研究拖輪的分配問(wèn)題，其在某種程度上與經(jīng)典分配問(wèn)題有關(guān)[1]。Kuhn等[2]為多種變形的分配問(wèn)題提供了新的解決方法；Zhang等[3]提出一種基于閾值的最優(yōu)分配策略，將批量到達(dá)的作業(yè)分配給異構(gòu)服務(wù)器，并給出了計(jì)算閾值的顯式公式；Pisinger[4]將載貨駁船分配給有能力的拖輪，類似于多重背包問(wèn)題，該問(wèn)題可以歸結(jié)為將n項(xiàng)任務(wù)分配給m個(gè)拖輪的背包問(wèn)題；Laalaoui等[5]考慮一臺(tái)機(jī)器在某些時(shí)期無(wú)法使用的準(zhǔn)時(shí)作業(yè)調(diào)度問(wèn)題，建立了一個(gè)基于二進(jìn)制的多背包問(wèn)題模型；Dimitrov等[6]研究了單個(gè)倉(cāng)庫(kù)分配卡車到各個(gè)項(xiàng)目的決策問(wèn)題；Kataoka等[7]設(shè)計(jì)了一種多項(xiàng)式時(shí)間算法求解多背包分配模型。在海上運(yùn)輸研究領(lǐng)域，學(xué)者們對(duì)船舶的泊位分配的優(yōu)化問(wèn)題進(jìn)行了廣泛研究[8-9]，但是很少有針對(duì)船舶拖輪調(diào)度優(yōu)化的研究。

目前，國(guó)內(nèi)外學(xué)者對(duì)拖輪調(diào)度優(yōu)化的研究不多，鮮有針對(duì)不確定情況的拖輪調(diào)度優(yōu)化進(jìn)行研究，而且對(duì)拖輪調(diào)度的求解大多都采用啟發(fā)式算法。劉志雄等[10-12]采用基于進(jìn)化策略的混合算法對(duì)所建立的拖輪調(diào)度模型進(jìn)行求解；董良才等[13]采用基于動(dòng)態(tài)遺傳算子的改進(jìn)粒子群優(yōu)化算法求解以“拖輪馬力溢出”及船舶等待拖輪的時(shí)間最小為目標(biāo)函數(shù)的拖輪調(diào)度問(wèn)題；王巍等[14]針對(duì)多停泊基地和不同作業(yè)模式下的拖輪調(diào)度，以最大完工時(shí)間和總作業(yè)油耗最小化為目標(biāo)，建立了拖輪調(diào)度多目標(biāo)優(yōu)化模型，并提出一種基于輪盤(pán)賭概率分配的編碼和解碼求解算法；徐奇等[15]構(gòu)建了以拖輪總作業(yè)時(shí)間最小化為目標(biāo)函數(shù)、考慮多停泊基地條件下的一體化調(diào)度優(yōu)化模型，并設(shè)計(jì)了混合模擬退火算法進(jìn)行求解；徐奇等[16]建立了對(duì)多停泊基地不同作業(yè)模式下考慮靠泊與停泊兩階段的拖輪調(diào)度優(yōu)化模型，并設(shè)計(jì)了啟發(fā)式規(guī)則與模擬退火相結(jié)合的混合算法求解模型；鄭紅星等[17]基于復(fù)式航道的特點(diǎn)，給出基于Arena的仿真模型，并嵌入了以拖輪耗油總成本最小為目標(biāo)的作業(yè)調(diào)度優(yōu)化模型，最后設(shè)計(jì)了嵌入啟發(fā)式規(guī)則的遺傳算法(Genetic Algorithm, GA)用于模型求解；Zhen等[18]研究了一個(gè)位于河口的港口拖船調(diào)度問(wèn)題，建立了一種混合整數(shù)規(guī)劃模型，并提出一種基于分支定價(jià)法的求解方法?？傮w上，上述文獻(xiàn)同樣考慮多停泊基地的拖輪調(diào)度問(wèn)題，但其所建立的可求解的線性規(guī)劃模型均未考慮拖輪可停靠任意停泊基地的情況。在現(xiàn)實(shí)的碼頭作業(yè)中，拖輪完成一項(xiàng)輔助作業(yè)后必須?？吭谌我庖粋€(gè)合理的停泊基地，在此基礎(chǔ)上，本文針對(duì)多停泊基地對(duì)多拖輪和不確定的情況建立一個(gè)混合整數(shù)線性規(guī)劃模型。

綜上，本文根據(jù)傳統(tǒng)調(diào)度模型，提出多停泊基地的港口拖輪調(diào)度優(yōu)化模型，在此基礎(chǔ)上考慮不確定性，運(yùn)用模糊規(guī)劃理論，建立相應(yīng)的模糊港口拖輪調(diào)度模型，同時(shí)設(shè)計(jì)一種基于調(diào)度計(jì)劃編碼的鯨魚(yú)—遺傳混合算法(Whale Optimization-Genetic hybrid Algorithms based on Scheduling Plan coding, SPWOGA)進(jìn)行求解。

1 問(wèn)題描述

首先明確5個(gè)定義：

(1)任務(wù) 在拖輪開(kāi)始作業(yè)前，港口通過(guò)顧客申請(qǐng)接收船舶的作業(yè)需求來(lái)安排當(dāng)天的作業(yè)計(jì)劃。因此，可以預(yù)先獲知單個(gè)船舶作業(yè)的服務(wù)內(nèi)容、所需拖輪數(shù)量和功率、開(kāi)始和結(jié)束時(shí)間以及開(kāi)始和結(jié)束地點(diǎn)，本文將這4個(gè)方面的信息定義為任務(wù)。

(2)拖輪作業(yè) 拖輪完成一項(xiàng)任務(wù)后行駛至某個(gè)基地?？坎⒌却乱豁?xiàng)任務(wù)。

(3)預(yù)處理 為了避免港口擁堵，根據(jù)任務(wù)和拖輪作業(yè)的定義，首先按照開(kāi)始時(shí)間對(duì)任務(wù)按排序，如果一項(xiàng)任務(wù)的結(jié)束時(shí)間和下一項(xiàng)任務(wù)的開(kāi)始時(shí)間接近，則可將前后兩項(xiàng)任務(wù)合并為一項(xiàng)新任務(wù)，其開(kāi)始時(shí)間和地點(diǎn)為前項(xiàng)任務(wù)的開(kāi)始時(shí)間和地點(diǎn)，結(jié)束時(shí)間和地點(diǎn)為后項(xiàng)任務(wù)的結(jié)束時(shí)間和地點(diǎn)，作業(yè)時(shí)間為前后兩項(xiàng)任務(wù)作業(yè)時(shí)間與前后兩項(xiàng)任務(wù)銜接時(shí)間之和。如果前后兩項(xiàng)任務(wù)需要的拖輪數(shù)量不同，例如前項(xiàng)需要2艘拖輪，后項(xiàng)需要3艘拖輪，則將后項(xiàng)任務(wù)分解為一項(xiàng)任務(wù)需要2艘拖輪、另一項(xiàng)需要1艘拖輪，并將需要2艘拖輪的任務(wù)和前項(xiàng)任務(wù)合并，將需要1艘拖輪的任務(wù)作為新增的任務(wù)，對(duì)于前項(xiàng)所需拖輪數(shù)多于后項(xiàng)任務(wù)的情況同理。另外，將兩項(xiàng)最大功率作為新任務(wù)的拖輪功率。

(4)初始狀態(tài) 指前一天任務(wù)完成后，拖輪所停靠的基地。

(5)調(diào)度計(jì)劃 指結(jié)合各拖輪的初始狀態(tài)，根據(jù)當(dāng)天的任務(wù)集合為每項(xiàng)任務(wù)安排拖輪服務(wù)。

本文所研究的多停泊基地的港口拖輪調(diào)度問(wèn)題是多停泊基地、多拖輪和多任務(wù)之間的調(diào)度分配問(wèn)題，拖輪可?？吭谌我庖粋€(gè)停泊基地，其須從某個(gè)基地出發(fā)，完成一項(xiàng)任務(wù)后回到某個(gè)基地后再等待后續(xù)任務(wù)(不一定是緊接的任務(wù))。如圖1所示，彎曲的港口岸線上有4個(gè)停泊基地，每個(gè)基地上有一定數(shù)量的拖輪(初始狀態(tài))，應(yīng)用預(yù)處理將任務(wù)按時(shí)間順序排序，任務(wù)通過(guò)單向進(jìn)港航道依次進(jìn)入港口，任務(wù)的形狀大小表示任務(wù)所需拖輪的數(shù)量，例如任務(wù)1需要兩個(gè)拖輪，調(diào)度員分別從停在基地3和4的拖輪各抽調(diào)一艘拖輪完成任務(wù)1，作業(yè)完成后從基地3出發(fā)的拖輪前往基地2，從基地4出發(fā)的拖輪前往基地1等待后續(xù)任務(wù)。

拖輪服務(wù)按拖輪作業(yè)艘次計(jì)費(fèi)，任務(wù)確定后收費(fèi)總額也確定，調(diào)度計(jì)劃的優(yōu)劣取決于作業(yè)成本的高低，作業(yè)成本以燃油成本為主。因此，本文目標(biāo)是最小化燃油成本，其由從基地到任務(wù)開(kāi)始地點(diǎn)和從任務(wù)結(jié)束地點(diǎn)到基地的行駛?cè)加统杀?按距離計(jì)算)，以及完成任務(wù)的作業(yè)燃油成本(按時(shí)間計(jì)算)組成。

在實(shí)際生產(chǎn)作業(yè)中，受不確定因素的干擾，調(diào)度人員不能準(zhǔn)確掌握港口環(huán)境和作業(yè)變化。因此，本文設(shè)定某些參數(shù)具有不確定性，參數(shù)的變化用對(duì)稱的三角模糊數(shù)表示。

基于以上描述，本文針對(duì)不確定的情況，以行駛?cè)加统杀竞妥鳂I(yè)燃油成本之和的總成本最小化為目標(biāo)，利用模糊規(guī)劃方法建立拖輪調(diào)度模糊規(guī)劃模型，研究拖輪分配計(jì)劃問(wèn)題。

2 模型建立

2.1 模型假設(shè)與符號(hào)說(shuō)明

本文提出以下假設(shè)條件：①調(diào)度計(jì)劃期為1天；②港口的進(jìn)出航道為單行，且船舶不能并行進(jìn)入；③拖輪在當(dāng)天所有任務(wù)開(kāi)始前都?？坑诨?；④不考慮基地外泊位和內(nèi)泊位的區(qū)別；⑤拖輪備車的時(shí)間短，其靠離基地泊位的時(shí)間忽略不計(jì)；⑥不同拖輪有各自固定的速度(最佳經(jīng)濟(jì)航速)；⑦每個(gè)基地可停泊的拖輪數(shù)量不限。

定義如下符號(hào)：

(1)集合J，J′為任務(wù)的集合，j∈J={1,2,…,NJ}，j′∈J′={0,1,2,…,NJ}；0表示當(dāng)天任務(wù)開(kāi)始前的0時(shí)刻任務(wù)(即初始狀態(tài))；I為拖輪的集合，i∈I={1,2,…,NI}；K為基地的集合，k∈K={1,2,…,NK}。

2.2 目標(biāo)函數(shù)與約束條件

本文研究的港口拖輪調(diào)度問(wèn)題含有模糊參數(shù)，因此建立一種基于可信性的模糊規(guī)劃模型[19-20]，將期望值方法(用于目標(biāo)函數(shù))和機(jī)會(huì)約束規(guī)劃方法(用于約束條件)結(jié)合進(jìn)行建模，得到基于可信性的模糊機(jī)會(huì)約束規(guī)劃模型M1：

(1)

(2)

(3)

Pi≥Mjxij,?i∈I,j∈J；

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

其中：目標(biāo)函數(shù)式(1)的第1部分表示拖輪從基地出發(fā)到達(dá)任務(wù)開(kāi)始地點(diǎn)所用的燃油成本，第2部分表示拖輪從任務(wù)開(kāi)始地點(diǎn)到結(jié)束地點(diǎn)作業(yè)所用的燃油成本，第3部分表示拖輪從任務(wù)結(jié)束地點(diǎn)到基地所用的燃油成本；式(2)表示滿足任務(wù)所需拖輪數(shù)需求的可信性不能小于α∈[0,1]；式(3)表示拖輪當(dāng)天初始停泊基地的位置；式(4)表示執(zhí)行任務(wù)的拖輪功率必須大于任務(wù)所需功率；式(5)表示執(zhí)行第1個(gè)任務(wù)的拖輪必須在第1個(gè)任務(wù)開(kāi)始前到達(dá)任務(wù)開(kāi)始地點(diǎn)的可信性不能小于α∈[0,1]；式(6)表示拖輪必須執(zhí)行完上一個(gè)任務(wù)回到某一基地，再?gòu)脑摶爻霭l(fā)，在下一個(gè)任務(wù)開(kāi)始前到達(dá)任務(wù)開(kāi)始地點(diǎn)的可信性不能小于α∈[0,1]；式(7)表示拖輪必須執(zhí)行完上一個(gè)任務(wù)回到某一基地才能執(zhí)行下一個(gè)任務(wù)；式(8)表示某一個(gè)基地的拖輪總量不能少于執(zhí)行任務(wù)的拖輪總量；式(9)表示一個(gè)拖輪只能停泊在一個(gè)基地；式(10)表示任意拖輪如果不執(zhí)行當(dāng)前任務(wù)，則繼承上一個(gè)任務(wù)所?？康幕匚恢?；式(11)表示變量為0-1變量。

由于模型中存在兩類變量相乘而造成的非線性部分，下面對(duì)非線性部分進(jìn)行線性化處理：

(12)

(13)

(14)

(15)

則式(1)、式(5)和式(6)分別變?yōu)槭?16)、式(17)和式(18)：

(16)

(17)

(18)

3 模型的處理

(19)

模糊排序公式(19)可以根據(jù)可信度度量重新表述為

ac+(2α-1)wa≤bc+(1-2α)wb,?α∈[0,1]。

(0.8+0.4α)ac≤(1.2-0.4α)bc,

?α∈[0,1]。

(20)

由式(20)和梯形模糊數(shù)的期望值，可以將式(2)、式(16)和式(17)變?yōu)槭?21)～式(24)：

(21)

(22)

(23)

?i∈I,j∈{2,3,…,NJ}。

(24)

綜上所述，本文建立以式(22)為目標(biāo)函數(shù)，以式(3)、式(4)、式(7)～式(15)、式(21)、式(23)和式(24)為約束條件的港口拖輪調(diào)度模糊規(guī)劃模型M2。

4 解決方法

模型M2在求解小規(guī)模問(wèn)題時(shí)可采用成熟的商業(yè)求解器(如CPLEX，Xpress, CAMS)求解，然而對(duì)于大規(guī)模問(wèn)題，現(xiàn)存求解器的求解效率變低。GA是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，但其存在易早熟和局部收斂等問(wèn)題[22-23]。鯨魚(yú)優(yōu)化算法(Whale Optimization Algorithm, WOA)具有操作簡(jiǎn)單、調(diào)整參數(shù)少、全局部搜索能力強(qiáng)等特點(diǎn)[24-25],已被成功應(yīng)用于工業(yè)設(shè)計(jì)[26]、最優(yōu)控制[27]、流水作業(yè)調(diào)度問(wèn)題[28]等領(lǐng)域，但其局部搜索能力較差。本文利用WOA的全局優(yōu)化優(yōu)勢(shì)和GA的局部收斂特點(diǎn),提出SPWOGA對(duì)模型進(jìn)行求解，算法流程如圖2所示。

4.1 鯨魚(yú)優(yōu)化算法

已有文獻(xiàn)指出，WOA是一種模仿座頭鯨泡泡網(wǎng)覓食行為的隨機(jī)群體智能算法[24-25]，其流程用數(shù)學(xué)描述如下：

(1)包圍獵物

X(t+1)=X*(t)-A·|C·X*(t)-X(t)|。

(25)

式中：t為當(dāng)前迭代次數(shù)；X*為截止到當(dāng)前最優(yōu)解的位置向量；X為當(dāng)前解的位置向量；A=2a·r1-a和C=2·r2，r1和r2為[0,1]之間的隨機(jī)向量；a=2-2t/T，T為最大迭代次數(shù)。

(2)螺旋氣泡網(wǎng)攻擊

鯨以螺旋運(yùn)動(dòng)不斷接近獵物，通過(guò)式(26)計(jì)算當(dāng)前解X和截止當(dāng)前最優(yōu)解X*之間的距離來(lái)模擬螺旋運(yùn)動(dòng)的過(guò)程。

X(t+1)=D′·ebl·cos(2πl(wèi))+X*(t)。

(26)

式中：D′=|X*(t)-X(t)|為鯨魚(yú)X和獵物的距離；b為螺旋形狀定義的常量；l為取值在[-1,1]間的隨機(jī)數(shù)。

(3)隨機(jī)搜尋獵物

鯨魚(yú)除了用泡泡網(wǎng)捕食，還采用隨機(jī)選擇的方法更新位置。當(dāng)|A|<1時(shí),進(jìn)行(2)的收縮包圍和螺旋更新，|A|≥1時(shí)，執(zhí)行等式

X(t+1)=Xrand(t)-A·|C·Xrand(t)-X(t)|。

(27)

式中Xrand為從當(dāng)前種群中隨機(jī)選取的鯨魚(yú)位置向量。

4.2 鯨魚(yú)優(yōu)化算法操作

如圖2所示，將當(dāng)前最優(yōu)解作為獵物的位置，每條鯨魚(yú)(個(gè)體)向其靠近，首先產(chǎn)生[0,1]范圍內(nèi)的隨機(jī)數(shù)m，若m≤0.5，則按式(26)更新；否則，判斷是否|A|>1，是則按式(25)更新位置，否則按照式(27)更新位置。該操作只用于變更所有任務(wù)欄部分拖輪的位置，而且保持任務(wù)所需的拖輪總量不變。

4.3 個(gè)體編碼結(jié)構(gòu)

本文的個(gè)體編碼采用港口拖輪調(diào)度計(jì)劃表表示，即在滿足任務(wù)所需功率和能否按時(shí)到達(dá)任務(wù)所要求的作業(yè)起點(diǎn)兩個(gè)條件下，安排某一拖輪從哪個(gè)基地出發(fā)完成了第幾個(gè)任務(wù)再回到哪個(gè)基地，不執(zhí)行任務(wù)的拖輪的基地位置不發(fā)生變化，具體示例如表1所示。表1為一個(gè)可行的港口拖輪調(diào)度計(jì)劃，假設(shè)有8個(gè)可用拖輪、3個(gè)基地和5個(gè)任務(wù)，表中：任務(wù)右邊括號(hào)里的數(shù)字表示當(dāng)前任務(wù)所需的拖輪數(shù)；第1行表示拖輪1的調(diào)度計(jì)劃，即拖輪1從初始基地1出發(fā)完成任務(wù)1后回到基地1，然后不執(zhí)行任務(wù)2和任務(wù)3(任務(wù)2和任務(wù)3的任務(wù)欄為0)留在基地1，接著從基地1出發(fā)完成任務(wù)4后回到基地3，最后不執(zhí)行任務(wù)5并留在基地3，拖輪2～8的調(diào)度計(jì)劃以此類推。

表1 一個(gè)可行的港口拖輪調(diào)度計(jì)劃

4.4 適應(yīng)度與選擇操作

適應(yīng)度為目標(biāo)函數(shù)值的倒數(shù)，即適應(yīng)度=1/個(gè)體目標(biāo)函數(shù)值。選擇操作采用最優(yōu)保存策略和輪盤(pán)選擇法相結(jié)合的方法。

4.5 交叉操作

采用單點(diǎn)交叉的方法確定交叉操作的父代，隨機(jī)將父代個(gè)體群兩兩分組，每組重復(fù)以下過(guò)程(交叉操作的偽代碼)：

輸入：拖輪總數(shù)M；任務(wù)總數(shù)N；父代個(gè)體P1(1:M,1:N)，P2(1:M,1:N)。

輸出：子代個(gè)體G1(1:M,1:N)，G2(1:M,1:N)。

步驟1 在[1,N-1]隨機(jī)選擇一個(gè)整數(shù)z。

步驟2 以任務(wù)z作為分界線，交換任務(wù)z后面的部分，即：

G1(1:M,1:z)=P1(1:M,1:z),G1(z+1:N)=P2(1:M,z+1:N)；

G2(1:M,1:z)=P2(1:M,1:z),G2(z+1:N)=P1(1:M,z+1:N)。

步驟3 合理地調(diào)整交換后兩個(gè)個(gè)體的調(diào)度計(jì)劃。

采用表1作為示例，具體操作如下：

步驟1確定兩個(gè)不同的個(gè)體，并在[1,4]的整數(shù)中隨機(jī)選擇(例如選擇數(shù)字2)。交換前的個(gè)體如表2和表3所示。

表2 交換前的個(gè)體1

表3 交換前的個(gè)體2

步驟2以任務(wù)2為分界線，交換任務(wù)2后面的部分，并合理地調(diào)整交換后兩個(gè)個(gè)體的調(diào)度計(jì)劃，如表4和表5所示。

表4 交換后的個(gè)體1

表5 交換后的個(gè)體2

4.6 變異操作

按照50%的概率采用交換變異或變化變異，具體操作如下(以表1的可行計(jì)劃為例)：

(1)交換變異 對(duì)任務(wù)1～任務(wù)5取一列中的兩行數(shù)字進(jìn)行交換，例如交換任務(wù)3的第2行和第6行，并合理地調(diào)整交換后拖輪2和拖輪6的調(diào)度計(jì)劃，經(jīng)過(guò)檢查，拖輪6的調(diào)度計(jì)劃合理，拖輪2任務(wù)3和任務(wù)4的基地需要更改為3，如表6所示。

表6 交換變異操作后的個(gè)體

(2)變化變異 對(duì)于任務(wù)1～任務(wù)5取一列中的基地?cái)?shù)字進(jìn)行改變，例如將任務(wù)2中拖輪3的基地更改為3，并合理地調(diào)整拖輪3的調(diào)度計(jì)劃，經(jīng)過(guò)檢查，拖輪3的任務(wù)3和任務(wù)4的基地需要更改為3，如表7所示。

表7 變化變異操作后的個(gè)體

4.7 修復(fù)操作

交叉和變異操作后的個(gè)體可能會(huì)打破解的可行性，即不符合拖輪按時(shí)到達(dá)任務(wù)所要求的作業(yè)起點(diǎn)，此時(shí)需要對(duì)個(gè)體編碼進(jìn)行可行性修復(fù)，修復(fù)操作的偽代碼如下：

輸入：

M：拖輪的總數(shù)

P1，P2：父代個(gè)體

G：子代個(gè)體

輸出：

R：子代可行個(gè)體

步驟1 For i=1:M。

步驟2 If當(dāng)前任務(wù)結(jié)束時(shí)間+當(dāng)前任務(wù)地點(diǎn)回到基地的時(shí)間+從該基地到下一任務(wù)所用時(shí)間>下一任務(wù)開(kāi)始時(shí)間。

步驟3 then用P1或P2當(dāng)前拖輪對(duì)應(yīng)任務(wù)所停靠的基地編號(hào)在G相應(yīng)位置進(jìn)行替換。

End If

步驟4 合理地調(diào)整拖輪i的整個(gè)調(diào)度計(jì)劃。

End For

步驟5 R=G。

例如對(duì)交叉后的個(gè)體2進(jìn)行可行性檢查，檢查到拖輪3執(zhí)行完任務(wù)2后回到基地3，而且從基地3到任務(wù)5的起點(diǎn)超過(guò)任務(wù)5的開(kāi)始時(shí)間，此時(shí)需要更改完成任務(wù)2后到達(dá)的基地，參考交叉操作前的個(gè)體2，需要將任務(wù)的基地3改為2，同時(shí)對(duì)其合理性進(jìn)行調(diào)整，即將任務(wù)3和任務(wù)4的基地改為2，如表8所示。

表8 修復(fù)操作后的個(gè)體

5 算例分析

為了評(píng)價(jià)SPWOGA在港口拖輪調(diào)度問(wèn)題中的性能，將其與文化基因算法(Memetic Algorithm,MA)進(jìn)行比較。與本文所提SPWOGA的特點(diǎn)類似，MA結(jié)合基于群體的搜索方法和鄰域知識(shí)[29-30]，其個(gè)體編碼、適應(yīng)度、選擇操作、交叉操作和修復(fù)操作與本文一樣，其中鄰域搜索的操作方法采用動(dòng)態(tài)鄰域搜索，具體操作如下：

鄰域搜索:75%的概率進(jìn)行下面的步驟

步驟1 For i=1 to(10+g/8)

步驟2 If i<4 then運(yùn)用本文變異操作中的交換方法

步驟3 Else運(yùn)用本文變異操作中的變化方法

End If

步驟4 If所得鄰域文化基因的適應(yīng)度值比當(dāng)前文化基因的適應(yīng)度值好then所得鄰域文化基因替換當(dāng)前文化基因

步驟5 Else以(0.05×w)的概率將當(dāng)前文化基因替換為所得鄰域文化基因

End If

End For

其中：g為當(dāng)前迭代的次數(shù)；w=(n-g)/(3×n)，n為總迭代數(shù)。

另外，M2模型在CPLEX12.8上編碼和運(yùn)行，將SPWOGA與求解器所得結(jié)果進(jìn)行對(duì)比。SPWOGA和MA算法均采用軟件MATLAB 7.0編寫(xiě)代碼，軟件MATLAB 7.0和CPLEX的運(yùn)行環(huán)境為Intel(R)Core(TM)i7 2.70 GHz處理器、4 GB內(nèi)存、Window10(64 bit)操作系統(tǒng)的手提電腦。本文根據(jù)表9和表10隨機(jī)生成12個(gè)規(guī)模不同的算例。

表9 算例的規(guī)模

表10 算例中的參數(shù)范圍

設(shè)定置信水平為1，SPWOGA和MA的交叉率和變異率分別取60%～70%和10%～15%。算法對(duì)每個(gè)算例運(yùn)行20次，結(jié)果如表11所示。

表11 運(yùn)算結(jié)果

續(xù)表11

表11中，對(duì)于算例1和算例2，SPWOGA的運(yùn)行時(shí)間比CPLEX長(zhǎng)，但SPWOGA所得目標(biāo)函數(shù)值與CPLEX相同，表明SPWOGA適用于規(guī)模較小的問(wèn)題，但效率明顯比CPLEX低；對(duì)于算例3和算例4，SPWOGA所得目標(biāo)函數(shù)值比CPLEX大，且運(yùn)行時(shí)間比CPLEX長(zhǎng)；對(duì)于算例5～算例9，SPWOGA所得目標(biāo)函數(shù)值比CPLEX大，但是運(yùn)行時(shí)間明顯比CPLEX短，表明對(duì)于規(guī)模稍大的問(wèn)題，SPWOGA的精度降低，效率明顯提高；對(duì)于算例10，SPWOGA所得目標(biāo)函數(shù)值比CPLEX小，且運(yùn)行時(shí)間比CPLEX短；對(duì)于算例11和算例12，CPLEX在系統(tǒng)內(nèi)存不足的情況下不能給出可行解，而SPWOGA能夠在可接受的時(shí)間范圍內(nèi)給出一個(gè)較好的解。因此，由以上分析可得，SPWOGA具有較高的精度。

另外，對(duì)于算例1和算例2，SPWOGA與MA得到的最好目標(biāo)值相同；對(duì)于算例3～算例12，SPWOGA得到的目標(biāo)值比MA小；對(duì)于全部測(cè)試問(wèn)題，MA運(yùn)行時(shí)間比SPWOGA長(zhǎng)，而且隨著算例規(guī)模的增大，MA所用時(shí)間增加得越多。這是由于MA的動(dòng)態(tài)鄰域搜索操作花費(fèi)的時(shí)間較多，而SPWOGA可以在較短時(shí)間內(nèi)得到較好的解，說(shuō)明SPWOGA的求解效率較高，尤其是在求解大規(guī)模問(wèn)題時(shí)更具優(yōu)勢(shì)。

為了比較SPWOGA和MA的收斂速度和求解精度，選取大規(guī)模測(cè)試算例10進(jìn)行求解，結(jié)果如圖3和圖4所示。圖3中，在迭代次數(shù)、種群規(guī)模及其他各個(gè)參數(shù)相同的情況下，SPWOGA在全局和局部搜索以及尋優(yōu)精度上都表現(xiàn)出了優(yōu)越性；圖4中，在時(shí)間、種群規(guī)模及其他各個(gè)參數(shù)相同的情況下，SPWOGA的收斂速度較MA快，并找到了精度更高的可行解，證明了混合算法的優(yōu)越性。

實(shí)際生活生產(chǎn)中，港口管理者經(jīng)常面對(duì)規(guī)模很大的調(diào)度安排問(wèn)題，希望盡快得到一個(gè)較好的調(diào)度方案來(lái)降低成本，而一般優(yōu)化軟件需要較長(zhǎng)的時(shí)間才能得到解決方案，因此并不適用。本文所提SPWOGA可以在合理的時(shí)間內(nèi)得到一個(gè)較優(yōu)的解決方案，權(quán)衡計(jì)算時(shí)間和最優(yōu)方案，具有一定的實(shí)際應(yīng)用意義。

為了分析模糊參數(shù)對(duì)物流網(wǎng)絡(luò)的影響，本文利用算例1研究網(wǎng)絡(luò)模型，并給出主要數(shù)據(jù)，如表12和表13所示。

表12 與拖輪相關(guān)的數(shù)據(jù)

表13 與任務(wù)相關(guān)的數(shù)據(jù)

在0%～100%之間取置信水平，采用SPWOGA求解，得到各置信水平下閉環(huán)供應(yīng)鏈網(wǎng)絡(luò)模型的計(jì)算結(jié)果，如表14～表16所示。

表14 置信水平變化時(shí)的目標(biāo)函數(shù)值

表15 置信水平為10%～100%的調(diào)度計(jì)劃

表16 置信水平為0%的調(diào)度計(jì)劃

由表14～表16可見(jiàn)，置信水平0%～10%的目標(biāo)值增加，這是因?yàn)樵黾又眯潘绞沟萌蝿?wù)所需拖輪數(shù)量增加，從而增加拖輪的航行成本和作業(yè)成本；置信水平10%～100%的目標(biāo)值不變，這是因?yàn)樵黾又眯潘經(jīng)]有導(dǎo)致任務(wù)所需拖輪數(shù)量增加，不需要增加額外的航行成本和作業(yè)成本。因此，置信水平影響目標(biāo)值，存在一定風(fēng)險(xiǎn)。

對(duì)比表15和表16的調(diào)度方案可知，置信水平為0%所得調(diào)度方案與置信水平為10%～100%的不同在于，置信水平為0%的方案在拖輪2完成了任務(wù)3和任務(wù)4后分別回到基地3和基地1，拖輪3不執(zhí)行任務(wù)4以及拖輪6在任務(wù)3和任務(wù)4作業(yè)期間均?？吭诨?，說(shuō)明置信水平影響調(diào)度計(jì)劃。

綜上所述，由于置信水平對(duì)調(diào)度計(jì)劃有明顯的影響，企業(yè)管理者需要正確合理地分析和估計(jì)港口作業(yè)的變化來(lái)確定作業(yè)強(qiáng)度，在選擇適當(dāng)?shù)闹眯潘降耐瑫r(shí)承擔(dān)相應(yīng)的風(fēng)險(xiǎn)水平，戰(zhàn)略性地安排調(diào)度計(jì)劃。

6 結(jié)束語(yǔ)

本文以港口拖輪為研究對(duì)象，考慮參數(shù)的不確定性，以燃油總成本最小化為目標(biāo)，建立了一個(gè)多停泊基地、多任務(wù)和多拖輪的模糊調(diào)度混合線性規(guī)劃模型，并設(shè)計(jì)了SPWOGA，最后通過(guò)算例證明了算法的有效性和模型的適用性，所得結(jié)果具有決策支持和方法指導(dǎo)的意義。

未來(lái)研究如下：①在多目標(biāo)方面，除了成本最少化之外，現(xiàn)實(shí)中為了使拖輪調(diào)度問(wèn)題更貼近實(shí)際，還需要考慮拖輪調(diào)度的效率最大化；②在不確定性方面，因故障導(dǎo)致拖輪不能按時(shí)完成既定的任務(wù)時(shí)，在中斷的情況下對(duì)調(diào)度計(jì)劃進(jìn)行調(diào)整并保持其優(yōu)越性。