基于量子遺傳混合算法的泊位聯(lián)合調(diào)度

蔡 蕓，劉朋青，熊禾根

（1. 冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室（武漢科技大學(xué)），武漢430081；2. 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室（武漢科技大學(xué)），武漢430081）

（*通信作者電子郵箱:lpq13618640356@163.com）

0 引言

傳統(tǒng)泊位或拖輪調(diào)度通常只考慮其單一調(diào)度，通常泊位調(diào)度以最小化總體船舶在港時(shí)間［1］、總體船舶服務(wù)成本［2］或提高經(jīng)濟(jì)績(jī)效［3］為目標(biāo)，拖輪調(diào)度以最小化作業(yè)時(shí)間［4］、節(jié)省燃油成本［5］為目標(biāo)，問(wèn)題求解算法較多，例如入侵野草算法［1］、多目標(biāo)遺傳算法［6］、包含動(dòng)態(tài)學(xué)習(xí)的粒子群算法［7］等。

為了提高集裝箱港口作業(yè)效率及顧客的服務(wù)滿意度，必須合理地利用泊位、拖輪。拖輪和泊位聯(lián)合調(diào)度有利于縮短船舶在港時(shí)間，提升港口服務(wù)效率。但是，目前針對(duì)拖輪及泊位聯(lián)合調(diào)度的研究較少，問(wèn)題模型通常含靠泊、離泊和泊位裝卸服務(wù)三個(gè)作業(yè)階段，優(yōu)化目標(biāo)為最小化船舶等待費(fèi)用與拖輪服務(wù)費(fèi)用［8］、最小化所有船舶中最晚完成靠泊時(shí)刻［9］等，聯(lián)合調(diào)度求解方法常采用遺傳與模擬退火的混合算法［8］、嵌入局部搜索功能的進(jìn)化算法［9］、改進(jìn)遺傳算法［10］等。

由于船舶拖期，港口需要給付罰金，減小拖期時(shí)間可以降低船舶滯留成本，提高顧客滿意度。為此，本文在已有研究基礎(chǔ)上，分析了拖輪、泊位聯(lián)合調(diào)度和岸橋分配問(wèn)題中存在的相關(guān)約束，并建立相關(guān)問(wèn)題模型，展開(kāi)了基于量子遺傳混合算法的泊位聯(lián)合調(diào)度研究。

1 問(wèn)題分析

泊位的聯(lián)合調(diào)度問(wèn)題可以分為三個(gè)階段:第一階段根據(jù)船舶的到港信息，對(duì)船舶分配拖輪、?？坎次?，由拖輪將船舶從錨地拖曳至泊位；第二階段根據(jù)船舶的裝卸量和岸橋的可調(diào)用情況，對(duì)靠泊船舶分配岸橋進(jìn)行裝卸作業(yè)；第三階段安排拖輪將完成裝卸的船舶拖曳出泊位。

在人工調(diào)度過(guò)程中，負(fù)責(zé)船舶靠離泊的拖輪調(diào)度、泊位調(diào)度和負(fù)責(zé)在泊位裝卸貨物的岸橋分配，通常相互獨(dú)立進(jìn)行，容易導(dǎo)致船舶和拖輪阻塞，或按計(jì)劃靠泊后岸橋卻不能立即到位，造成船舶既占用了泊位資源，又增加了船舶在港時(shí)間。如果將拖輪、泊位進(jìn)行聯(lián)合調(diào)度，就有利于使靠泊、裝卸、離泊三階段作業(yè)連貫有序地進(jìn)行，降低船舶的在港時(shí)間，減少港口的作業(yè)成本同時(shí)提高客戶的滿意度。

拖輪和岸橋資源分配必須滿足以下調(diào)度規(guī)則:

1）拖輪調(diào)度規(guī)則。拖輪調(diào)度要求是按照集裝箱船舶的船長(zhǎng)（不考慮裝卸貨物量）分配相應(yīng)種類和數(shù)量的拖輪協(xié)助作業(yè)，具體配置規(guī)則如表1［5］所示。

表1 船舶類型與拖輪馬力匹配原則Tab. 1 Matching principle of ship type and tugboat horsepower

2）岸橋調(diào)度規(guī)則。岸橋的分配與船舶的裝卸量有關(guān)，當(dāng)船舶裝卸量小于200 箱時(shí)，安排1～2 臺(tái)岸橋；裝卸量在200～500箱時(shí)，安排2～3臺(tái)岸橋；裝卸量在500～1 000箱時(shí)，安排3～4臺(tái)岸橋；裝卸量大于1 000箱時(shí)，安排4～6臺(tái)岸橋。

2 模型建立

2.1 模型假設(shè)

1）周期內(nèi)到港船舶數(shù)據(jù)已知；

2）不考慮船舶在泊位間移泊；

3）拖輪與船舶之間是一種多對(duì)一的動(dòng)態(tài)匹配關(guān)系；

4）各類型船舶與拖輪匹配關(guān)系和由不同拖輪組服務(wù)所需時(shí)間已知；

5）岸橋與船舶的匹配關(guān)系已知；

6）岸橋總數(shù)以及裝卸速度已知。

2.2 數(shù)學(xué)模型

1）集合和參數(shù)。

計(jì)劃周期內(nèi)到港船舶的集合為N（N=｛1，2，…，n｝），用i表示到港船舶編號(hào)；港口泊位的集合為M（M=｛1，2，…，m｝），用j表示港口泊位編號(hào)；拖輪的集合為T（T=｛1，2，…，t｝），用u表示拖輪編號(hào)；拖輪u的馬力值為TPu；船舶i的安全船長(zhǎng)（含橫向安全預(yù)留長(zhǎng)度）為NLi；船舶i的安全水深（含縱向安全預(yù)留長(zhǎng)度）為NDi；泊位j的長(zhǎng)度為MLj；泊位j的水深為MDj；拖動(dòng)船舶i所需的拖輪艘數(shù)為Qi；船舶i的裝載箱量為Ii；船舶i的卸載箱量為Ei；岸橋的裝卸速度為v；分配給船舶i的最小和最大岸橋數(shù)為；碼頭可用岸橋總數(shù)為C。船舶i的到港時(shí)刻為ai；船舶i的預(yù)計(jì)離港時(shí)刻為Di；船舶i開(kāi)始被拖輪拖離錨地至泊位j的時(shí)刻為Aij；船舶i的在港時(shí)間為sti。

2）決策變量。

若船舶i在泊位j上作為第h艘船舶被服務(wù)，則就取值為1，否則取值為0；若船舶i由拖輪u拖曳至泊位j，則Yiju=1，否則取值為0；若船舶i由拖輪u拖離泊位j，則Y′iju=1，否則取值為0。

2.3 目標(biāo)函數(shù)

在實(shí)際求解中，將兩個(gè)目標(biāo)加權(quán)求和轉(zhuǎn)化為單目標(biāo)進(jìn)行計(jì)算:

因此目標(biāo)函數(shù)為:

其中:加權(quán)系數(shù)C1、C2取值分別為0.7、0.3（咨詢專家打分獲得）。

2.4 約束條件

式（5）保證每個(gè)泊位上被服務(wù)的船舶數(shù)之和為到港船舶的總數(shù)；式（6）保證每條船舶必須在某個(gè)泊位被服務(wù)且只被服務(wù)一次；式（7）保證同一泊位同時(shí)最多?？恳凰掖?；式（8）保證船舶i到港后才被拖輪拖曳至泊位；式（9）保證停靠在泊位j的船i的長(zhǎng)度應(yīng)小于泊位j的長(zhǎng)度；式（10）保證?？吭诓次籮的船i的吃水深度小于泊位j的安全深度；式（11）保證同一拖輪同時(shí)最多服務(wù)于一艘船舶；式（12）保證同一時(shí)刻被調(diào)度用于助泊作業(yè)的拖輪數(shù)不超過(guò)港口總拖輪數(shù)；式（13）、式（14）保證船舶i配置的拖輪數(shù)等于匹配規(guī)則表內(nèi)船舶i所需的拖輪數(shù)；式（15）保證分配給船舶i的岸橋數(shù)在最大和最小岸橋數(shù)的范圍內(nèi)；式（16）保證同一時(shí)刻在工作的岸橋數(shù)不超過(guò)港口總岸橋數(shù)；式（17）、式（18）、式（19）為決策變量。

3 混合算法設(shè)計(jì)

3.1 混合算法流程

拖輪和泊位聯(lián)合調(diào)度目前多采用啟發(fā)式算法或混合算法求解［8-9］，為了研究不同算法求解該類問(wèn)題的效果，本文進(jìn)行了量子遺傳混合算法的應(yīng)用研究。量子遺傳算法（Quantum Genetic Algorithm，QGA）是一種結(jié)合量子計(jì)算與遺傳算法的概率進(jìn)化算法，相比遺傳算法擁有更好的多樣性特征以及全局尋優(yōu)能力［11］。本文在保留交叉、變異遺傳操作的基礎(chǔ)上，采用動(dòng)態(tài)調(diào)整量子門旋轉(zhuǎn)角大小的策略取代固定旋轉(zhuǎn)角策略，對(duì)量子門更新操作進(jìn)行改進(jìn)；為了獲得更好的優(yōu)化效果，將量子遺傳算法與禁忌搜索（Tabu Search，TS）算法［12］進(jìn)行串行混合，以量子遺傳算法的優(yōu)化解作為禁忌搜索算法的初始解，有效解決了TS對(duì)于初始解有較強(qiáng)依賴性的缺陷，防止搜索過(guò)程陷入局部最優(yōu)，達(dá)到了更好的搜索效果。混合算法步驟如下:

1）初始化種群及各參數(shù)，隨機(jī)生成m個(gè)個(gè)體，并對(duì)個(gè)體的染色體進(jìn)行量子比特編碼。

2）對(duì)染色體進(jìn)行測(cè)量，得到對(duì)應(yīng)的解。

3）對(duì)各確定解進(jìn)行適應(yīng)度評(píng)估，并記錄最優(yōu)解和對(duì)應(yīng)的適應(yīng)度；

4）判斷是否滿足量子遺傳算法的終止條件:若滿足終止條件，輸出量子遺傳算法的最優(yōu)解，作為禁忌搜索的初始解，進(jìn)入步驟7）；否則繼續(xù)以下步驟5）。

5）對(duì)染色體進(jìn)行交叉、變異遺傳操作。

6）量子旋轉(zhuǎn)門調(diào)整策略更新，利用動(dòng)態(tài)量子旋轉(zhuǎn)門更新種群，返回步驟3）。

7）選擇候選解（選擇當(dāng)前最優(yōu)解）。

8）判斷是否滿足禁忌搜索的終止條件:若滿足，混合算法結(jié)束并輸出結(jié)果；否則，繼續(xù)以下步驟9）。

9）生成鄰域候選解。

10）計(jì)算適應(yīng)度函數(shù)值（解碼）。

11）更新禁忌表，判斷是否滿足藐視規(guī)則:若滿足，將滿足藐視規(guī)則的解作為當(dāng)前解，同時(shí)將其放在禁忌列表第一個(gè)位置，更新最優(yōu)解；若不滿足，確定候選解的質(zhì)量，選取未被禁忌的最優(yōu)解作為當(dāng)前解，同時(shí)將其放在禁忌列表第一個(gè)位置。返回步驟7）。

3.2 混合算法的關(guān)鍵技術(shù)

3.2.1 染色體結(jié)構(gòu)

針對(duì)本文調(diào)度問(wèn)題，采用雙染色體結(jié)構(gòu)。第一條染色體采用實(shí)數(shù)編碼，確定到港船舶的服務(wù)順序；第二條染色體采用矩陣編碼，確定港口資源的調(diào)度安排，其結(jié)構(gòu)如下。:

其中:n為到港船舶的數(shù)量，Pb表示每艘到港船舶?？坎次坏木幪?hào)，Pt表示每艘船舶靠泊使用的拖輪組的編號(hào)，P′t表示每艘船舶離泊使用的拖輪組的編號(hào)，Pq表示給每艘船舶分配的岸橋數(shù)量，種群中每個(gè)個(gè)體對(duì)應(yīng)一個(gè)調(diào)度方案。

將實(shí)數(shù)編碼轉(zhuǎn)換為二進(jìn)制編碼后再進(jìn)行量子比特編碼，編碼方式參考文獻(xiàn)［13］，每個(gè)基因Xi的量子比特編碼為（α，β），α、β的取值范圍均為［0，1］，且滿足:

每個(gè)基因Xi對(duì)應(yīng)角度θi的取值范圍在［0，π 2］，如圖1所示。

圖1 量子門更新示意圖Fig. 1 Schematic diagram of quantum gate update

3.2.2 測(cè)量染色體

對(duì)種群中的各個(gè)染色體測(cè)量，獲得一組確定的二進(jìn)制解。每個(gè)基因?qū)?yīng)0 或1 是根據(jù)量子比特的概率選擇得到。具體測(cè)量的方法為:產(chǎn)生一個(gè)［0，π 2］內(nèi)的隨機(jī)數(shù)rand，若隨機(jī)數(shù)小于θ，則測(cè)量結(jié)果為1；否則為0。

3.2.3 計(jì)算適應(yīng)度

該問(wèn)題的優(yōu)化目標(biāo)是最小化總體船舶在港時(shí)間和總拖期時(shí)間的加權(quán)和。因此，在該步驟設(shè)適應(yīng)度函數(shù)為目標(biāo)函數(shù)的相反數(shù)，即目標(biāo)函數(shù)值越小的個(gè)體，其適應(yīng)度值越大。解碼時(shí)，若染色體違反約束條件（5）～（19），則該染色體無(wú)效；若染色體有效，則依據(jù)染色體及調(diào)度規(guī)則生成相應(yīng)調(diào)度方案，計(jì)算出其個(gè)體適應(yīng)度值，并記錄最優(yōu)個(gè)體及其適應(yīng)度值。

3.2.4 遺傳操作

在遺傳算法中，通過(guò)對(duì)原有的兩條染色體進(jìn)行交叉操作，可能會(huì)得到更優(yōu)異的子代染色體，這有利于種群的進(jìn)化。本文采用兩點(diǎn)交叉機(jī)制進(jìn)行交叉操作，首先隨機(jī)選擇一對(duì)父代染色體，確定交叉基因的起止位置（兩個(gè)染色體被選取位置相同），分別找出交叉基因在另一染色體中的位置，再將其余基因按順序放入生成一對(duì)子代染色體。該方法的優(yōu)勢(shì)在于不會(huì)造成基因沖突，交叉操作如圖2所示。

圖2 交叉操作示意圖Fig. 2 Schematic diagram of crossover operation

當(dāng)種群在進(jìn)化中陷入搜索空間中某個(gè)超平面時(shí)，通過(guò)變異操作可有助于擺脫這種困境。變異操作采用換位變異機(jī)制，隨機(jī)選擇一條染色體，確定兩個(gè)變異基因，交換其位置，生成新的染色體。

3.2.5 動(dòng)態(tài)量子門更新

與傳統(tǒng)遺傳算法不同，量子遺傳算法的搜索尋優(yōu)是在相位空間中利用量子門更新量子位概率幅實(shí)現(xiàn)［14］。本文量子門更新如圖1 所示:θ′表示當(dāng)前記錄的最佳基因位，θ表示現(xiàn)在要進(jìn)行更新的基因位，θ旋轉(zhuǎn)Δθ角度后更新到θ′。旋轉(zhuǎn)門的目的是朝著有利于進(jìn)化的方向更新種群，1 表示逆時(shí)針旋轉(zhuǎn)，-1 表示順時(shí)針旋轉(zhuǎn)，0 表示不旋轉(zhuǎn)，因此旋轉(zhuǎn)角旋轉(zhuǎn)方向可表示為:

一般量子旋轉(zhuǎn)門調(diào)整策略的角度是給定的，因而會(huì)給算法造成一定的限制。旋轉(zhuǎn)角幅度太小，會(huì)導(dǎo)致算法收斂較慢，反之則會(huì)導(dǎo)致出現(xiàn)早熟。采用動(dòng)態(tài)旋轉(zhuǎn)角取代給定旋轉(zhuǎn)角可解決這一問(wèn)題［15］，本文設(shè)計(jì)一種旋轉(zhuǎn)角動(dòng)態(tài)選擇策略:

其中:Δθ的取值區(qū)間為［0.001π，0.05π］，區(qū)間上的最小值用θmin表示，最大值用θmax表示，f′ =(fx-fmax)fx，fmax表示記錄的最優(yōu)個(gè)體的適應(yīng)度值，fx表示當(dāng)前個(gè)體的適應(yīng)度值。因此，當(dāng)fx與fmax的差值越小時(shí)，旋轉(zhuǎn)角越小，該旋轉(zhuǎn)角動(dòng)態(tài)選擇策略既可提高收斂速度，又可有效避免早熟現(xiàn)象。量子旋轉(zhuǎn)門可表示為:

3.2.6 終止策略

設(shè)置最大迭代次數(shù)為混合算法的終止條件，當(dāng)混合算法的迭代次數(shù)達(dá)到最大值時(shí)，停止迭代并輸出最優(yōu)解，若目標(biāo)值小于給定閾值時(shí)，可提前終止迭代。禁忌搜索算法的終止策略為適應(yīng)度值小于指定誤差。

4 算例分析

4.1 算例數(shù)據(jù)

某港口人工調(diào)度的生產(chǎn)數(shù)據(jù)如表2所示。

表2 生產(chǎn)數(shù)據(jù)Tab. 2 Production data

該工作周期內(nèi)總體船舶在港時(shí)間為80 h，總拖期時(shí)間為8.5 h。該港口泊位的總數(shù)為4，編號(hào)為1～4 號(hào)，泊位的長(zhǎng)度分別為:200 m、300 m、300 m、400 m，泊位水深分別為:12 m、12 m、15 m、15 m；可用于入泊和離泊的拖輪共有6 艘，編號(hào)為1～6，馬力值分別為1 200、2 600、3 200、3 400、3 400、4 000 匹；共有12 個(gè)岸橋可供使用，每個(gè)岸橋的裝卸速度為40箱/h。

由于類型為S1的船舶在入泊和離泊都只需要一艘拖輪為其服務(wù)，所以1～6 號(hào)拖輪所需要的服務(wù)時(shí)間分別為0.6 h、0.5 h、0.4 h、0.3 h、0，3 h、0.3 h。拖輪馬力越大，其拖拽同一類型的船舶所需要的時(shí)間越短，但是拖拽時(shí)間也是有一個(gè)下限的，所以所需要的時(shí)間不是一直減小的。不同類型的船舶使用不同類型的拖輪組合所需要的拖拽時(shí)間如表3所示。

表3 不同船舶類型由不同拖輪組合服務(wù)所需時(shí)間 單位：hTab. 3 Time required for different ship types to be serviced by different tugboat combinations unit:h

4.2 參數(shù)選擇

為驗(yàn)證混合算法的有效性，將混合算法與自適應(yīng)遺傳算法調(diào)度結(jié)果進(jìn)行對(duì)比。自適應(yīng)遺傳算法采用自然數(shù)編碼，染色體包含5 個(gè)子染色體，分別表示服務(wù)順序、泊位編號(hào)、靠泊拖輪組、離泊拖輪組、岸橋數(shù)目。采用輪盤賭選擇，交叉采用兩點(diǎn)交叉法，變異采用換位變異。

混合算法參數(shù)的選擇會(huì)影響到求優(yōu)效果，為奠定調(diào)度應(yīng)用研究的基礎(chǔ)。本文將量子遺傳混合算法用于Rastrigin's 函數(shù)和Schaffer函數(shù)，校驗(yàn)了混合算法的有效性并初步鎖定了算法參數(shù)范圍，根據(jù)實(shí)驗(yàn)結(jié)果的經(jīng)驗(yàn)分析，本文確定自適應(yīng)遺傳算法的參數(shù)為:種群規(guī)模為20，交叉概率為0.8，變異概率為0.01，最大迭代次數(shù)為50。為進(jìn)行有效對(duì)比，量子遺傳混合算法的參數(shù)選擇與自適應(yīng)遺傳算法保持一致，旋轉(zhuǎn)角選擇策略如式（23）所示。

4.3 結(jié)果分析

算法搜索過(guò)程如圖3 所示，從圖中可以看出，混合算法比遺傳算法有更高的收斂精度，但是迭代次數(shù)較多。

圖3 迭代優(yōu)化曲線Fig. 3 Iterative optimization curves

圖4、5 分別為混合算法和遺傳算法的調(diào)度結(jié)果甘特圖，橫軸表示船舶在港時(shí)間跨度，縱軸表示泊位編號(hào)，甘特圖反映了所有到港船舶入泊、裝卸、離泊三個(gè)階段所用的時(shí)間，其中T 表示拖輪編號(hào)，N 表示船舶編號(hào)，Q 表示分配岸橋數(shù)量。通過(guò)比較可以發(fā)現(xiàn)，在混合算法的調(diào)度方案下，第一艘船舶開(kāi)始入泊到最后一艘船舶結(jié)束離泊的時(shí)間跨度為20.82 h，與遺傳算法的調(diào)度方案相比減少了3.04 h，且相鄰兩個(gè)工作階段的等待間隔明顯減小，有效避免了港口資源不足時(shí)船舶出現(xiàn)等待的情況。

圖4 混合算法調(diào)度結(jié)果Fig. 4 Scheduling result of hybrid algorithm

圖5 遺傳算法調(diào)度結(jié)果Fig. 5 Scheduling result of genetic algorithm

人工調(diào)度下總體船舶在港時(shí)間約為80 h，總拖期時(shí)間為8.5 h。遺傳算法調(diào)度下最優(yōu)解的總體船舶在港時(shí)間為68.1878 h，比人工調(diào)度減少了14.8%；總拖期時(shí)間為6.285 3 h，比人工調(diào)度減少了26.1%。混合算法調(diào)度下最優(yōu)解的總體船舶在港時(shí)間為60.793 4 h，相比人工調(diào)度減少了24%，相比遺傳算法減少了10.9%；總拖期時(shí)間為4.871 8 h，相比人工調(diào)度減少了42.7%，相比遺傳算法減少了22.5%。兩類調(diào)度算法均可有效節(jié)約船舶時(shí)間成本，但混合算法調(diào)度后節(jié)省的時(shí)間多于遺傳算法，求解精度更高，其優(yōu)化能力更強(qiáng)。

5 結(jié)語(yǔ)

1）為了克服以往只考慮單一泊位調(diào)度和忽略離泊拖輪調(diào)度問(wèn)題模型的缺陷，本文模型同時(shí)考慮了拖輪-泊位聯(lián)合調(diào)度和岸橋分配，以及最小化總拖期時(shí)間問(wèn)題，使問(wèn)題模型更加貼近生產(chǎn)實(shí)際，更利于指導(dǎo)生產(chǎn)實(shí)踐。

2）綜合量子遺傳算法的全局尋優(yōu)能力和禁忌搜索算法的局部搜索能力，并改進(jìn)了量子門的旋轉(zhuǎn)策略，設(shè)計(jì)了量子遺傳算法-禁忌搜索混合算法，為求解拖輪-泊位聯(lián)合調(diào)度模型提供了新思路。

3）結(jié)合生產(chǎn)算例對(duì)設(shè)計(jì)的算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，計(jì)算結(jié)果表明:相比遺傳算法，混合算法可以取得更有效的調(diào)度方案，降低了總體船舶在港時(shí)間和總拖期時(shí)間，在目前嚴(yán)峻的港口競(jìng)爭(zhēng)中，不但可以為港口節(jié)省時(shí)間成本，還可以提高客戶滿意度。