基于量子遺傳混合算法的泊位聯合調度

蔡 蕓，劉朋青，熊禾根

（1. 冶金裝備及其控制教育部重點實驗室（武漢科技大學），武漢430081；2. 機械傳動與制造工程湖北省重點實驗室（武漢科技大學），武漢430081）

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

0 引言

傳統泊位或拖輪調度通常只考慮其單一調度，通常泊位調度以最小化總體船舶在港時間［1］、總體船舶服務成本［2］或提高經濟績效［3］為目標，拖輪調度以最小化作業時間［4］、節省燃油成本［5］為目標，問題求解算法較多，例如入侵野草算法［1］、多目標遺傳算法［6］、包含動態學習的粒子群算法［7］等。

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

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

1 問題分析

泊位的聯合調度問題可以分為三個階段:第一階段根據船舶的到港信息，對船舶分配拖輪、停靠泊位，由拖輪將船舶從錨地拖曳至泊位；第二階段根據船舶的裝卸量和岸橋的可調用情況，對靠泊船舶分配岸橋進行裝卸作業；第三階段安排拖輪將完成裝卸的船舶拖曳出泊位。

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

拖輪和岸橋資源分配必須滿足以下調度規則:

1）拖輪調度規則。拖輪調度要求是按照集裝箱船舶的船長（不考慮裝卸貨物量）分配相應種類和數量的拖輪協助作業，具體配置規則如表1［5］所示。

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

2）岸橋調度規則。岸橋的分配與船舶的裝卸量有關，當船舶裝卸量小于200 箱時，安排1～2 臺岸橋；裝卸量在200～500箱時，安排2～3臺岸橋；裝卸量在500～1 000箱時，安排3～4臺岸橋；裝卸量大于1 000箱時，安排4～6臺岸橋。

2 模型建立

2.1 模型假設

1）周期內到港船舶數據已知；

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

3）拖輪與船舶之間是一種多對一的動態匹配關系；

4）各類型船舶與拖輪匹配關系和由不同拖輪組服務所需時間已知；

5）岸橋與船舶的匹配關系已知；

6）岸橋總數以及裝卸速度已知。

2.2 數學模型

1）集合和參數。

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

2）決策變量。

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

2.3 目標函數

在實際求解中，將兩個目標加權求和轉化為單目標進行計算:

因此目標函數為:

其中:加權系數C1、C2取值分別為0.7、0.3（咨詢專家打分獲得）。

2.4 約束條件

式（5）保證每個泊位上被服務的船舶數之和為到港船舶的總數；式（6）保證每條船舶必須在某個泊位被服務且只被服務一次；式（7）保證同一泊位同時最多停靠一艘船舶；式（8）保證船舶i到港后才被拖輪拖曳至泊位；式（9）保證停靠在泊位j的船i的長度應小于泊位j的長度；式（10）保證停靠在泊位j的船i的吃水深度小于泊位j的安全深度；式（11）保證同一拖輪同時最多服務于一艘船舶；式（12）保證同一時刻被調度用于助泊作業的拖輪數不超過港口總拖輪數；式（13）、式（14）保證船舶i配置的拖輪數等于匹配規則表內船舶i所需的拖輪數；式（15）保證分配給船舶i的岸橋數在最大和最小岸橋數的范圍內；式（16）保證同一時刻在工作的岸橋數不超過港口總岸橋數；式（17）、式（18）、式（19）為決策變量。

3 混合算法設計

3.1 混合算法流程

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

1）初始化種群及各參數，隨機生成m個個體，并對個體的染色體進行量子比特編碼。

2）對染色體進行測量，得到對應的解。

3）對各確定解進行適應度評估，并記錄最優解和對應的適應度；

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

5）對染色體進行交叉、變異遺傳操作。

6）量子旋轉門調整策略更新，利用動態量子旋轉門更新種群，返回步驟3）。

7）選擇候選解（選擇當前最優解）。

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

9）生成鄰域候選解。

10）計算適應度函數值（解碼）。

11）更新禁忌表，判斷是否滿足藐視規則:若滿足，將滿足藐視規則的解作為當前解，同時將其放在禁忌列表第一個位置，更新最優解；若不滿足，確定候選解的質量，選取未被禁忌的最優解作為當前解，同時將其放在禁忌列表第一個位置。返回步驟7）。

3.2 混合算法的關鍵技術

3.2.1 染色體結構

針對本文調度問題，采用雙染色體結構。第一條染色體采用實數編碼，確定到港船舶的服務順序；第二條染色體采用矩陣編碼，確定港口資源的調度安排，其結構如下。:

其中:n為到港船舶的數量，Pb表示每艘到港船舶停靠泊位的編號，Pt表示每艘船舶靠泊使用的拖輪組的編號，P′t表示每艘船舶離泊使用的拖輪組的編號，Pq表示給每艘船舶分配的岸橋數量，種群中每個個體對應一個調度方案。

將實數編碼轉換為二進制編碼后再進行量子比特編碼，編碼方式參考文獻［13］，每個基因Xi的量子比特編碼為（α，β），α、β的取值范圍均為［0，1］，且滿足:

每個基因Xi對應角度θi的取值范圍在［0，π 2］，如圖1所示。

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

3.2.2 測量染色體

對種群中的各個染色體測量，獲得一組確定的二進制解。每個基因對應0 或1 是根據量子比特的概率選擇得到。具體測量的方法為:產生一個［0，π 2］內的隨機數rand，若隨機數小于θ，則測量結果為1；否則為0。

3.2.3 計算適應度

該問題的優化目標是最小化總體船舶在港時間和總拖期時間的加權和。因此，在該步驟設適應度函數為目標函數的相反數，即目標函數值越小的個體，其適應度值越大。解碼時，若染色體違反約束條件（5）～（19），則該染色體無效；若染色體有效，則依據染色體及調度規則生成相應調度方案，計算出其個體適應度值，并記錄最優個體及其適應度值。

3.2.4 遺傳操作

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

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

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

3.2.5 動態量子門更新

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

一般量子旋轉門調整策略的角度是給定的，因而會給算法造成一定的限制。旋轉角幅度太小，會導致算法收斂較慢，反之則會導致出現早熟。采用動態旋轉角取代給定旋轉角可解決這一問題［15］，本文設計一種旋轉角動態選擇策略:

其中:Δθ的取值區間為［0.001π，0.05π］，區間上的最小值用θmin表示，最大值用θmax表示，f′ =(fx-fmax)fx，fmax表示記錄的最優個體的適應度值，fx表示當前個體的適應度值。因此，當fx與fmax的差值越小時，旋轉角越小，該旋轉角動態選擇策略既可提高收斂速度，又可有效避免早熟現象。量子旋轉門可表示為:

3.2.6 終止策略

設置最大迭代次數為混合算法的終止條件，當混合算法的迭代次數達到最大值時，停止迭代并輸出最優解，若目標值小于給定閾值時，可提前終止迭代。禁忌搜索算法的終止策略為適應度值小于指定誤差。

4 算例分析

4.1 算例數據

某港口人工調度的生產數據如表2所示。

表2 生產數據Tab. 2 Production data

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

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

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

4.2 參數選擇

為驗證混合算法的有效性，將混合算法與自適應遺傳算法調度結果進行對比。自適應遺傳算法采用自然數編碼，染色體包含5 個子染色體，分別表示服務順序、泊位編號、靠泊拖輪組、離泊拖輪組、岸橋數目。采用輪盤賭選擇，交叉采用兩點交叉法，變異采用換位變異。

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

4.3 結果分析

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

圖3 迭代優化曲線Fig. 3 Iterative optimization curves

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

圖4 混合算法調度結果Fig. 4 Scheduling result of hybrid algorithm

圖5 遺傳算法調度結果Fig. 5 Scheduling result of genetic algorithm

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

5 結語

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

2）綜合量子遺傳算法的全局尋優能力和禁忌搜索算法的局部搜索能力，并改進了量子門的旋轉策略，設計了量子遺傳算法-禁忌搜索混合算法，為求解拖輪-泊位聯合調度模型提供了新思路。

3）結合生產算例對設計的算法進行實驗驗證，計算結果表明:相比遺傳算法，混合算法可以取得更有效的調度方案，降低了總體船舶在港時間和總拖期時間，在目前嚴峻的港口競爭中，不但可以為港口節省時間成本，還可以提高客戶滿意度。