兼顧成本與時間保證率的泊位及岸橋協同調度優化

宋云婷， 王 諾， 吳 暖

(大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引言

泊位和岸橋是集裝箱碼頭最重要的資源，恰當合理地對這些資源進行協同調度，可以有效降低生產成本，提高企業管理水平。在合理選擇泊位的基礎上，采取盡可能地利用相鄰泊位的岸橋協同作業，以便最大限度地減少岸橋的投入數量，降低碼頭作業成本便是其中一種重要的調度策略。研究這一泊位及岸橋協同調度方案的制定過程，構建相應的優化模型并設計有效的計算方法，對于港口生產的科學管理具有重要的現實意義。

目前，關于集裝箱碼頭裝卸調度的優化已有較多成果，如針對碼頭集卡與岸橋的協調調度問題，建立船舶在港時間最短、碼頭生產成本最小的優化模型[1～3]；利用混合交叉作業方法與同步優化技術，建立集成調度優化模型等[4]；針對泊位偏離和岸橋工作損失建立集裝箱港口泊位和岸橋的混合整數線性規劃模型等[5]。上述研究都有一個共同的前提，即無論船舶離港的時間是否緊急，無論需要裝卸的箱量是否較多，都以船舶在港作業時間最短為優化目標[6～10]，對于集裝箱班輪而言，按照船期表規定的時間在港口完成裝卸作業是其運行的基本性質，但對于如何結合泊位計劃尋求岸橋開工數量以合理放緩作業速度的優化，則有待深入研究。

關于多目標問題的求解方法，也有諸多成果[11～13]。由于泊位分配、岸橋調度等屬于NP-hard問題，因而通常利用優化算法求解[14～18]。為解決同時兼顧船舶靠泊位置和不同時刻岸橋工作狀態問題，有的學者結合局部搜索算法對遺傳算法進行了改進[19]，采用兩階段啟發式算法有效提高求解效率；針對計劃期內泊位的狀態和岸橋的同步調度相互關聯的反饋關系設計嵌入啟發式規則的遺傳算法對其進行求解[20]，但對于連續型泊位下泊位及岸橋協同調度的多目標求解問題還需要進行相應的改進和深化。

關于從Pareto解集中選擇合理方案的問題，有的研究結合決策者的偏好[21～25]在求解過程中嵌入向量評價微粒群算法[26]，或者以Pareto最優解和任何其它解沖突的大小進行排序[27]，通過對雙層規劃上下層的協商尋求滿意解以及建立指標評價體系[28,29]進行打分遴選，計算各Pareto非劣解相對于不同目標函數偏向度對Pareto非劣解進行量化評價[30]等等。但有關Pareto非劣解的尋優方法在港口管理中并未見到具體應用。

針對以上諸多問題，本文結合港口生產的實際特點，提出了新的優化思路，其主要的創新點及貢獻是：①根據集裝箱班輪按計劃到離港的運行特點，引入集裝箱班輪按計劃離港保證率的概念，定量分析集裝箱班輪在規定時間內完成裝卸作業的概率；②以班輪按計劃離港的保證率最大和碼頭裝卸作業成本最低為目標建立多目標優化模型，采用帶精英策略非支配排序的遺傳算法求解，在此基礎上以嵌入疊加式局部搜索算法解決相鄰作業船舶共享使用岸橋問題，得到泊位及岸橋協同調度的Pareto解集；③利用“性價比”的方法對Pareto非劣解進行分析，確定既能滿足集裝箱班輪按計劃離港的要求，又能夠降低港口作業成本的最優方案，解決了在Pareto非劣解集中尋優的問題。最后，通過對大連港集裝箱碼頭真實案例的分析，驗證了本文優化模型的合理性和計算方法的有效性。

1 模型構建

1.1 模型假設

根據集裝箱班輪靠泊的特點，本文采用連續型泊位的“柔性”分配方法，即沿碼頭岸線依次安排船舶靠泊。為簡化起見，需做如下假設：①碼頭各泊位水深能夠滿足所有到港船舶要求；②船舶裝卸效率與參與裝卸的岸橋數成正比，即岸橋的單臺作業效率不因岸橋數量的增加而改變；③允許岸橋在作業過程中移至其他船舶進行作業；④忽略岸橋移動過程的成本。

1.2 符號定義

(1)參數

(2)決策變量

1.3 目標函數

為計算船舶按計劃離港的保證率，首先需建立有關概念。

定義在正常裝卸速度下，集裝箱班輪能夠在規定時間內完成裝卸作業并按計劃駛離港口的概率為船舶按時完成作業保證率。

設船舶i在港接受服務時間的概率服從愛爾朗分布，則集裝箱班輪的按計劃離港的保證率可表示為：

(1)

式中，T代表船公司與港方約定的船舶在港服務時間，μi代表船舶i的平均裝卸效率，其取值由岸橋的單機作業效率和配置數量決定。

由以上分析，建立優化模型如下:

目標函數1：要求到港船舶能夠按計劃離港的平均保證率最大，即:

(2)

式中，P為所有到港船舶按計劃離港的平均保證率，s為船舶數量。

目標函數2：要求碼頭裝卸成本最低，即：

(3)

1.4 約束條件

Pi≥Pmin

(4)

(5)

(6)

(7)

(8)

(9)

(10)

上式中，式(4)表示任意船舶按計劃離港保證率均需滿足最低保證率要求；式(5)表示任意時刻作業的岸橋數不得超過港口配備的岸橋總數量；式(6)表示任意時刻所有靠泊船舶不得超過碼頭岸線范圍；式(7)表示為每艘船舶配備的岸橋數量不能超過其可配備的最大岸橋數量；式(8)～(10)表示任意兩艘船舶在停靠時間和停靠位置上不能發生沖突。

2 算法設計

對于多目標優化問題，需要找出解空間的Pareto邊界供決策者選擇。在算法選擇時，由于帶精英策略非支配排序的遺傳算法(non-dominated sorted genetic algorithm-II, NSGA-II)具有隱含的并行性、隨機性和高度魯棒性特點，因而在多目標求解問題中具有較廣的應用。但對于本文問題，為達到降低成本的目的，可允許岸橋在作業過程中在相鄰船舶間協同使用，即在滿足某一船舶能按時完成裝卸作業的前提下，允許配備給該船舶的部分岸橋可中途轉移至相鄰船舶繼續作業，這一調度策略大大增加了求解的復雜性。對此，本文專門設計了疊加式局部搜索算法，并將其嵌入NSGA-Ⅱ算法中。計算時，以遺傳算法確定船舶的靠泊順序與岸橋配置數量，以疊加式局部搜索算法對岸橋進行協同調度，兩者不斷交叉反饋推動計算進程，最終得到滿足優化問題的Pareto解集。

2.1 嵌入疊加式局部搜索算法的NSGA-Ⅱ算法設計

2.1.1 染色體編碼

采用十進制編碼方式對染色體進行編碼，設染色體長度為2s，第1到s位染色體代表船舶1到船舶s的靠泊順序，第s+1位到2s位染色體代表船舶1到船舶s配置的岸橋數目。例如，當靠泊船舶為5艘時，染色體編碼方式見圖1。

圖1 染色體編碼方式

為保證種群的多樣性，采用隨機生成種群的方法，從第1到第s位染色體為1到s的隨機整數序列，即船舶1到船舶s的靠泊順序；第s+1到第2s位染色體為從船舶可配置的最小岸橋數到最大岸橋數之間的隨機整數，即船舶1到船舶s配置的岸橋數量。

2.1.2 適應度函數

由于本文是解決多目標優化問題，因此個體的適應度值可通過個體的目標函數值比較得到。首先將種群中個體對目標函數值的表現進行排序，得到可行解的排序序列Xj，根據排序序列得到個體的排序號Ri(Xj)，并通過式(11)～(12)可得到個體的適應度函數值，即:

(11)

(12)

式中，N為種群中個體數量，n為目標函數數量。

2.1.3 遺傳操作

選擇操作采用輪盤賭選擇算子。交叉操作采用部分匹配交叉，即在染色體的第1至s位基因隨機生成兩個交叉點，把兩個交叉點之間的基因序列插入對方染色體的第1個基因之前，然后將交叉段基因與原染色體基因相比較，再依次去除交叉段基因中相同的基因，將第s+1至2s位基因按照與前s位基因的對應關系重新排序，交叉過程見圖2。

圖2 染色體交叉過程

變異操作采用逆轉變異法，分別對染色體的前后兩段基因進行變異，以Pm為變異概率，在染色體的1至s位基因和s+1至2s位基因中分別隨機生成2個位點，將2點之間的基因反轉插入，產生新一代種群，變異過程見圖3。

圖3 染色體變異過程

2.1.4 疊加式局部搜索算法設計

所謂疊加式局部搜索，是指在局部搜索時，不斷疊加前程搜索已完成的結果，在此基礎上再拓展搜索范圍循序進行。由于已有算法無法實現在作業中的岸橋從一艘船舶轉移至另一艘船舶繼續作業的調度方式，不能連續記錄岸橋的工作和轉移所需的時間，因此需要嵌入疊加式局部搜索予以解決。這一算法的核心思想是：當船舶i靠泊后，首先根據染色體編碼確定船舶i的靠泊位置和初始配備岸橋數量，分析其相鄰正在作業船舶的岸橋情況，以最低保證率和岸橋移動距離兩方面判斷是否采用協同調配策略：若能滿足上述要求，則生成岸橋協同調配方案，確定船舶i的岸橋配備編號，記錄對應的起止作業時間，同時更新受影響船舶的調度計劃；若不滿足，則依據染色體編碼，在未參與作業的岸橋中確定新的調配方案。

2.1.5 算法步驟

以上算法的具體步驟如下：

Step1根據染色體編碼規則生成染色體，得到初始的船舶靠泊順序和岸橋配置數量；

Step2進行疊加式局部搜索，從確定的靠泊順序(I1，I2，I3，…，Is)中選取首個待靠泊船舶，令i=Is；

Step3判斷剩余岸線長度是否大于船舶i的船長。若是，令船舶i的靠泊位置距離前一艘停靠船舶舶船尾的所在位置向右l0米處；若否，令船舶i的靠泊位置距離碼頭岸線起始端安全距離l0米處，即yi=l0；

Step5令船舶i的靠泊時間延遲至沖突船舶j離港時間安全時間t0小時后，轉Step4；

Step6判斷船舶i需要配置的岸橋數目是否超過最大岸橋數目的限制。若是，進入Step7；否則，轉Step8；

Step7按染色體生成規則重新生成新染色體，轉Step2；

Step8判斷船舶i和船舶i-1之間能否共用岸橋。若是，生成共用岸橋調度計劃，并調整受影響船舶的調度計劃；否則，生成船舶i的調度計劃；

Step9判斷船舶i是否為整個靠泊序列中的最后一艘船，即判斷i

Step10輸出該靠泊船舶序列的作業調度計劃，疊加式局部搜索結束；

Step11根據所得作業調度計劃，依據目標函數計算船舶序列的平均按計劃離港保證率和作業成本；

Step12根據目標函數值篩選初始非劣解集；

Step13根據個體的非劣解水平進行非支配排序生成不同序值和前端，并計算同一前端不同個體之間的擁擠距離；

Step14依據遺傳操作規則進行染色體的選擇、交叉及變異，同一前端中序值小、擁擠距離大的個體將優先被選擇，獲得子代B；

Step15將父代A和子代B種群進行合并，重新進行非支配排序和擁擠距離的計算；

Step16利用修剪函數對合并后的種群進行修剪，修剪規則為序值小擁擠距離大的個體予以保留，得到個體數等于種群大小的新種群C；

Step17判斷是否滿足最大迭代次數要求。若不滿足，轉Step2；

Step18篩選出最終非劣解集，得到Pareto解集，結束。

2.2 Pareto最優解的選擇

由多目標優化模型可知，在提高按計劃離港保證率和降低作業成本之間要進行兩全的選擇，在這一對矛盾中不能有偏倚，需要在按計劃離港保證率最大和作業成本最低的兩個優化目標之間尋找一個平衡點，即尋求各目標均能接受即偏向最小的解，本文利用分析Pareto前沿性價比的方法選擇其最優方案。所謂性價比量化方法的基本思想是，根據Pareto前沿的幾何分布特點，其幾何變化率分別相對于兩個優化目標最靈敏的交點所對應的解即為無偏向的最優解[30](圖4)。

圖4 Pareto前沿各點平均變率的幾何關系圖(min-max模型)

基于上述思路，設J為Pareto解集的個數，可由小至大依次排列進行編號，P(j)表示第j個Pareto解的平均船舶按計劃離港保證率，j∈{1,2,…,J}；C(j)表示第j個Pareto解的平均裝卸作業成本，j∈{2,3,…,J}，則上述兩目標的平均變化率為:

(13)

(14)

(15)

(16)

(17)

(18)

在此基礎上，可得到相對于各目標的靈敏比:

(19)

(20)

為方便比較，需對上述結果進行無量綱化處理，具體表達式為：

(21)

設靈敏比無量綱化差值的絕對值為Δε，有

(22)

式中符號意義同上。

由以上分析可知，靈敏比差值絕對值的最小值(Δε)min即為所對應的Pareto解即為所尋求的最優方案，即：

(Δε)min=min{Δε(1),Δε(2),…,Δε(J)}

(23)

式中符號意義同上。

3 算例分析

3.1 基本數據

現以大連港集裝箱碼頭2010年11月16日實際生產的調度過程為背景。由現場調度記錄，當時共有10艘班輪先后循序到港，各班輪的平均裝卸箱量為341TEU，具體信息見表1。該碼頭岸線總長796m，配備有8臺岸橋。由統計分析知，大連港集裝箱班輪在港服務的時間服從8階愛爾朗分布，班輪在港服務時間約定為16小時，要求任意1艘班輪按計劃離港的保證率不低于80%。

根據集裝箱碼頭的裝卸工藝，裝卸設備是以岸橋為核心，與場橋和集卡等按比例進行編組。由作業現場調查統計，岸橋、場橋和集卡按表2配備，當單船裝卸量較少時，按下限值配備；反之按上限值配備。碼頭作業成本[27]見表3。

表1 到港船舶信息

表2 岸橋、場橋、集卡編組配置

表3 效率、成本的取值

3.2 方案優化

利用前面建立的基于疊加式局部搜索的遺傳算法，采用MATLAB編程，運算在P4CPU、內存2G、主頻2.81HZ的環境下進行，取種群數量N=50，交叉概率Pc=0.5，變異概率Pm=0.1，最終得到12個滿足最低保證率要求的Pareto非劣解(見圖5)。由式(13)～(23)，得到各非劣解對應的靈敏比無量綱化差值的絕對值(見表4、圖6)。由式(23)求得(Δε(j))min=Δε(7)，即圖5中最小值的7#(亦即圖6中的7#)所對應的方案為最優。由表4可見，Pareto非劣解集中7#方案完成作業的平均保證率達到90.27%，比保證率最低的1#方案高出達5.01%，而作業成本僅增加0.34%，綜合結果最優。

按照方案7#，其作業計劃具體為：當船舶1靠泊時，安排1#岸橋投入作業；當船舶2靠泊時，3#、4#岸橋投入作業；當船舶3靠泊時，4#岸橋由船舶2轉至船舶3協同作業；當船舶4靠泊時，5#、6#、7#岸橋投入作業；當船舶5靠泊時，1#岸橋協同作業、2#岸橋投入作業；當船舶6靠泊時，2#岸橋協同作業；當船舶7靠泊時，4#、5#岸橋協同作業；當船舶8靠泊時，7#岸橋協同作業；當船舶9靠泊時，4#岸橋協同作業；船舶10靠泊時，1#岸橋協同作業(見圖7)，整個過程采取協同作業方式，自始至終只開動了8臺岸橋中的7臺作業，保留1臺處于停產狀態。與港口未優化前調度方案的對比可知，在滿足所有船舶按計劃離港保證率均大于80%的前提下，通過壓縮岸橋的配置數量，使得港口裝卸作業成本降低了1.04%(表5)。

圖5 多目標優化模型的Pareto非劣解集

表4 Pareto解集對應的參數表

圖6 靈敏比無量綱化差值的絕對值與作業成本的變化曲線注：括號中數字為與圖5對應的Pareto解集編號

圖7 泊位分配及作業安排示意圖

表5 未采取協同策略的作業計劃與7#方案優化效果對照表

4 結論

本文解決的是泊位及岸橋的協同調度問題，即在合理選擇泊位的基礎上，以保證按規定時間完成裝卸作業為前提，采用對相鄰靠泊船舶的作業岸橋協同支援的方式，最大限度地減少岸橋等設備的投入數量、降低了碼頭作業成本。與以往研究的泊位及岸橋的常規調度問題相比，本文同時考慮了集裝箱班輪按計劃離港的要求和碼頭作業成本最低兩個目標，結合泊位計劃尋求岸橋協同調度的最佳配置和作業速度，因而大大增加了問題的復雜性。

本文引入按計劃離港保證率的概念，以到港船舶按計劃離港保證率最大和碼頭作業成本最低為目標，構建了泊位及岸橋協同調度的多目標優化模型。為求解岸橋協同調度問題，采用嵌入疊加式局部搜索算法的NSGAcvⅡ算法，以遺傳算法決定船舶的靠泊順序與岸橋配置數量；依據生成的靠泊順序和岸橋數量，利用疊加式局部搜索方法，經過相互交叉反饋運算，得到了以目標函數進行非支配排序生成的Pareto非劣解。在此基礎上，根據Pareto前沿的幾何分布特點，以性價比的概念得到對應兩個優化目標偏向最小的最優解。最后，以大連港集裝箱碼頭的真實案例進行分析，結果顯示，以本文的優化思路得到的泊位及岸橋協同調度計劃與港口實際調度計劃相比，在所有船舶按時離港的保證率均大于80%的前提下，通過壓縮岸橋參與生產的配置數量，可使港口裝卸作業成本降低1.04%，驗證了文中提出的優化思路和算法在解決實際問題中的有效性，取得了既滿足船舶按時完成作業要求，又降低港口作業成本的效果。

研究中，本文將集裝箱班輪在港作業時間設為常量，實際中，還存在部分班輪公司要求船舶在港作業時間不同甚至會出現臨時變化的情況，如何在更為復雜的情況下尋求協同調度的優化方案，是下一步需要研究的課題。