不規則型泊位與岸橋集成分配問題的優化建模和算法研究

趙 姣，胡 卉，袁華智

(1.長安大學運輸工程學院，西安 710064；2.蘭州理工大學土木工程學院，蘭州 730050)

1 引 言

國際物流過程中集裝箱港口的運營條件、服務質量、管理水平等均會影響到港口運輸物流市場的競爭實力，而泊位和岸橋等港口資源的高效利用是提升各集裝箱港口核心競爭力的主要因素.通常，針對每艘到港船舶均會有一個預設的離港時間，如果未能在預計離港時間之前完成船舶裝卸任務，港口將繳納滯期金.因此，如何通過泊位、岸橋等資源的合理分配，縮短船舶在港停泊時間，以及提高港口作業效率，進而為更多船舶提供高效、快捷的靠泊裝卸服務是集裝箱港口運營管理過程中重點關注的問題.

針對泊位分配和岸橋分配問題，已有學者開展了大量研究，并在提升集裝箱港口作業效率方面取得了較大進展[1-5].在泊位分配問題研究方面，現有文獻主要研究離散型和連續型泊位分配問題.離散型泊位分配問題是將泊位看作若干相互獨立的泊位，且每個泊位在同一時間段內只能?？恳凰掖?，如圖1所示.離散型泊位分配問題的研究方面，張新宇等[1]以總等待時間最少為目標，建立了考慮兩艘船的離散泊位分配問題數學模型，設計了模擬退火多種群遺傳算法進行求解.鄭紅星等[3]針對考慮潮汐影響的離散泊位分配問題進行了研究，并采用禁忌搜索算法進行求解.Bacalhau等[4]針對動態離散泊位分配問題進行研究，并針對此離散問題提出了一種混合遺傳算法進行求解.泊位分配問題是提高港口運營效率的一個重要因素，與之相鄰的岸橋優化問題則是確?？焖傺b卸作業的另一個關鍵因素.因此，近年來，如何對有限的泊位、岸橋資源進行集成優化的問題受到國內外學者的廣泛關注.Song等[5]針對離散泊位分配問題和岸橋調度問題進行了研究，其中所有的船舶都在調度計劃開始前到達港口，每個泊位一次只能為一艘船服務，并為該問題提供一個多種方法集成的綜合解決方案.

圖1 離散型泊位分配問題

連續型泊位分配問題則是把泊位區看作連續的一段空間，船舶可在保持安全距離的情況下臨近停泊，如圖2所示.范志強[6]針對連續泊位分配問題進行了優化建模，并設計了遺傳算法進行求解.王軍等[7]采用動態學習方法對離散泊位分配方案進行了優化.Guo等[8]針對考慮天氣情況下的連續泊位分配問題進行研究，并設計了粒子群算法進行求解.與離散泊位分配問題類似，連續型泊位和岸橋集成優化問題已吸引了眾多學者的關注.Hendriks等[9]研究了一種聯合運營的連續泊位分配問題，在該問題中，集裝箱運營商為同一港口內的多個公司提供集裝箱裝卸物流服務，一個泊位可以服務多艘船.吳迪等[10]討論了連續型泊位與岸橋集成分配問題，并設計了模擬植物生長交替進化算法進行求解.Wawrzyniak等[11]研究了連續型泊位和岸橋分配問題，并設計了啟發式算法進行求解.Rodrigues等[12]針對連續型泊位和岸橋分配問題進行研究，設計了一種精確算法進行求解.

圖2 連續型泊位分配問題

此外，在一些空間受限的集裝箱港口(如比利時安特衛普港和新加坡港等)，泊位線往往不呈一條直線，這些集裝箱港口的泊位線，包含若干條直線，一條直線上包含多個泊位，即：同時包含離散和連續兩種泊位分配情況，如圖3所示.以往研究中對于空間受限的泊位分配問題研究較少.Imai等[13]最早針對鋸齒型泊位分配問題進行了優化研究, 在此基礎上，Imai等[14]考慮了由平行泊位線組成航道情況下的泊位分配問題.Correcher等[15]針對不規則布局的泊位分配問題進行研究，并設計了啟發式算法進行求解.

圖3 不規則型泊位分配問題

針對不規則型泊位和岸橋分配問題的特點，將一條直線上的泊位定義為一個“泊位段”，每個泊位段有多個泊位和岸橋.當研究的港口只有一個泊位段，且每個泊位段內包含多個泊位時，則該問題為連續型泊位和岸橋分配問題；當研究的港口包含多個泊位段，且每個泊位段內只包含一個泊位時，則該問題為離散型泊位和岸橋分配問題.綜上，離散和連續泊位和岸橋分配問題均可看作本文研究的不規則型泊位和岸橋分配問題的特殊情況.因此，已有的針對離散或連續型泊位和岸橋集成優化的方法，并不適用于不規則型泊位和岸橋分配問題.不管是直線型泊位或是不規則型泊位，當船舶在分配的泊位停泊后，均需由岸橋進行裝卸作業，岸橋分配的數量直接影響船舶的裝卸效率，因此有必要將不規則型泊位分配和岸橋分配進行集成優化.而現有的不規則型泊位分配問題的研究，很少同時考慮岸橋分配問題，且未對模型進行優化，導致建立的數學模型無法在短時間內獲得最優解.為解決上述問題，本文首先建立了兩種不規則型泊位和岸橋集成分配問題的數學模型，并對兩種數學模型的求解效果進行了比較和分析；其次，提煉并加入了三個有效不等式，進一步改進了建立的數學模型；最后，設計了改進的粒子群算法對不規則型泊位和岸橋集成分配問題進行了求解，從而提高不規則型泊位類型港口的作業效率，降低運營成本.

2 問題描述與模型構建

2.1 問題描述

已知計劃期內若干艘將入港船舶的長度、預計到港時間以及所需要的最大和最小岸橋數目，所有船舶必須在到港后開始?？坎次徊⑦M行裝卸作業.需決策每艘船的?？坎次欢?，以及在該泊位段上的停泊位置、時間和岸橋，使得計劃期內所有船舶在港停泊時間之和最小.某一不規則型泊位和岸橋分配結果如圖4所示.每個矩形左下角的“數字”表示船號.每個矩形的左下角和左上角所在縱坐標的位置分別表示序號中對應船舶在分配到的泊位裝(卸)貨的開始時間和結束時間.同樣，每個矩形的左下角和右下角對應的橫坐標位置分別表示序號中對應船舶在分配到的泊位的起始位置和結束位置.在圖4中，帶虛線的矩形中的數字表示分配給每艘船的岸橋編號.

圖4 不規則型泊位和岸橋分配方案

2.2 數學模型

考慮船舶之間的相對位置和服務時間，基于以下參數和決策變量建立不規則泊位和岸橋集成分配問題的數學模型.

已知參數如下，T為計劃期內時間單位的集合，T={1，…，K}，其中K是計劃期間的時間單位總數；Ω為計劃期內來港船舶的集合，Ω={1，…，N}，其中N為計劃期內來港船舶總數；Ψ為泊位段集合，Ψ={1，…，M}，其中M是泊位段的總數；Qj為泊位段j的岸橋數；Pijc為船i在泊位段j上分配c臺岸橋時的卸載時間；li為船i的長度；Lj泊位段j的長度；εi為可用于i船的港口岸橋的最大數量；θi為可用于i船的港口岸橋的最小數量；ri為船i的到達時間.

建立不規則型泊位和岸橋集成分配問題的數學模型：

(1)

?i∈Ω,i′∈Ω{i},j∈Ψ

(2)

?i∈Ω,i′∈Ω{i},j∈Ψ

(3)

?i∈Ω,i′∈Ω{i},j∈Ψ

(4)

?i∈Ω,i′∈Ω{i},j∈Ψ

(5)

?i∈Ω,i′∈Ω{i},j∈Ψ

(6)

(7)

?i∈Ω,j∈Ψ

(8)

(9)

(10)

(11)

(12)

(13)

Di≤K?,i∈Ω

(14)

?i∈Ω,i′∈Ω{i},j∈Ψ

(15)

?i∈Ω,j∈Ψ

(16)

2.3 有效不等式

為進一步提高2.2部分不規則型泊位和岸橋集成分配問題數學模型的求解效果，結合問題特性和變量關系，提煉出該模型的三個有效不等式如下.

(17)

(18)

(19)

3 算法設計

粒子群算法是由Eberhart等[16]提出的一種基于種群的智能優化算法.由于其收斂快速以及需要設置的參數較少等特點，粒子群算法已經得到了廣泛的應用[17-19].在粒子群算法中，種群由若干粒子組成，且每個粒子在每次迭代中都有一個位置和速度向量，位置決定解的質量，而速度決定粒子在下一代的移動方向.粒子的速度和位置更新公式如下.

(20)

(21)

(22)

3.1 解的表示和初始解的生成

由于離散和連續泊位和岸橋分配問題均可看作本文研究的不規則型泊位和岸橋分配問題的特殊情況，即：當研究的港口只有一個泊位段，且每個泊位段內包含多個泊位時，則該問題為連續型泊位和岸橋分配問題；當研究的港口包含多個泊位段，且每個泊位段內只包含一個泊位時，則該問題為離散型泊位和岸橋分配問題.因此，不同于離散型泊位和岸橋分配問題的粒子群算法，針對不規則泊位和岸橋分配問題進行研究，同一時段內，每個泊位段不只停留一艘船，而是可以停留多艘船，在粒子群算法解碼過程中，不僅需要決策船舶的?？坎次?，還需要決策船舶在分配的泊位段上的具體停泊位置；不同于連續型泊位和岸橋分配問題的粒子群算法，針對不規則泊位和岸橋分配問題進行研究，不僅包含一個泊位段，而是每個泊位段均需決策哪些船舶在該泊位段上停泊，以及具體的停泊位置.即：不規則型泊位和岸橋集成調度問題需要決策每艘船?？康牟次欢?，以及在該泊位段上的停泊位置、停泊時間和分配的岸橋號.首先采用粒子群算法進行泊位段的分配和岸橋數目的分配，然后再設計啟發式對船舶的停泊位置和停泊時間進行分配，從而得到不規則型泊位和岸橋集成分配問題的優化方案.

定義1N=|Ω|，代表需要?？康拇皵的?，用一個2N維的序列表示一個解.其中第一個N維代表為相應的船舶分配的泊位段的編號，每一維的值都是0到M之間的一個實數值.第k維的值Xk表示船舶i被分配給泊位段?Xi?停泊并進行裝卸作業.第二個N維代表每艘船被分配的岸橋數目，每一維的值都是0到q′=min(εi，Qj)之間的一個實數值，其中Qj為泊位段j上的岸橋數量，εi為船舶i的最大服務岸橋數量.第N+k維的值Xk+N表示船舶i在對應的泊位段上被分配的岸橋數量.圖5中為3個泊位段，每個泊位段有3臺岸橋，到港5艘船的粒子群算法初始解.第一個N維代表為每艘船舶分配的泊位段的編號，將圖中前5個隨機生成的實數向上取整，得到1～5號船舶的?？坎次欢畏謩e為1,3,2,2,1；第二個N維代表每艘船被分配的岸橋數目，將圖中后5個隨機生成的實數向上取整，得到1～5號船舶的分配的岸橋數量分別為1,3,2,3,2.分配每艘船舶所在的泊位段后，將每個泊位段上的船舶按照到達時間從小到大進行排序，依次計算每艘船的停泊位置和停泊時間，以及分配的岸橋.每一艘船舶分配停泊位置和岸橋后，計算該泊位段當前剩余空閑長度和空閑岸橋數量，當剩余泊位段長度不滿足下一艘船的長度要求，或者剩余岸橋數目少于下一艘船所需要的最小岸橋數目時，計算當前占用該泊位段的所有船舶服務結束時間，當占用該泊位段的所有船舶服務結束后，下一艘船開始接受服務.

圖5 粒子編碼和解碼示意圖

采用隨機的方式產生初始解以保證解的多樣性.每一個粒子的第一個N維在0到M之間隨機產生，第二個N維在0到Qj之間隨機產生.

3.2 適值計算及算法終止條件

適應度值根據原始目標函數值計算，一個粒子對應的適應度值為：計劃期內所有到港船舶在港停泊時間之和.

判斷當前迭代次數是否達到最大迭代次數(Max_iteration)，若是，停止迭代，選擇適應度值最小的粒子所對應的解作為不規則型泊位和岸橋集成分配問題的優化解輸出；否則，繼續進行迭代，直到達到最大迭代代數為止.

3.3 粒子群求解過程

基于上述描述，下面給出粒子群算法求解不規則型泊位和岸橋集成分配問題的過程.

步驟1：初始化種群中的所有粒子，得到泊位和岸橋分配方案.迭代次數設為1.

步驟2：對于每一個粒子，根據分配的泊位段和岸橋數目，計算每艘船所在泊位段的停泊位置、停泊時間以及服務岸橋號.

步驟3：計算每個粒子的適應度值.

步驟4：更新每個粒子的最好位置值以及種群的最好位置值.

步驟5：根據式(22)和式(21)更新每一個粒子的速度和位置值.

步驟6：如果達到最大迭代次數，算法停止；否則，轉到步驟2.

4 計算實驗

4.1 算例產生

采用CPLEX 12.5軟件求解不規則型泊位和岸橋集成分配問題的最優解，但對船舶數較多問題的求解時，CPLEX12.5無法在1 h內獲得問題的可行解，因此采用C++編碼的PSO算法，所有實驗在一臺cpu 3.2 GHz，4 GB內存的計算機上進行.結合港口實際情況和文獻[20]的數據，設定每個泊位段長度為300 m，岸橋數目為5臺，到港船舶的長度在li=U[80, 300],i=1,2,…,N.每艘船舶的到港時間和一臺岸橋的服務時間分別服從[1, 100]和[10, 60]的均勻分布.服務每艘船舶的最大和最小岸橋數目為εi=li/50,θi=1+0.3εi.將每個泊位段均看作50 m為1個單位長度，同時將船舶也看作50 m為1個單位長度，將實際泊位段和船舶長度轉換為若干單位長度，從而針對不規則型泊位和岸橋集成分配問題進行求解，最后將求解到的結果再乘以50轉化為泊位段和船舶的實際長度，既加快了CPLEX的求解時間，同時也基本不影響原問題的優化結果.

4.2 計算結果

采用CPLEX軟件求解泊位段為2，船舶數為5的8個算例，針對原模型(記為M)和加入有效不等式后的模型(記為M′)的求解結果如表1所示，其中，Gap =(模型M求解時間-模型M′求解時間)×100%/模型M求解時間.針對加入有效不等式前后的模型進行求解均獲得了最優解，從表2可以看出，加入有效不等式后，模型的平均求解時間減少了83.39%.

表1 加入有效不等式前后CPLEX求解模型M的結果對比

以船舶數目為8的算例為例，該算例中的已知數據見表2，不規則型泊位和岸橋集成分配的優化方案如圖6所示.船舶3，4和6被分配到泊位段1；船舶2和5被分配到泊位段2；船舶1，7和8被分到泊位段3.在泊位段1中，船舶6最先到達，岸橋1和2為其進行裝卸作業，開始和結束時間分別為2和19，停泊位置從1到150；岸橋1為船舶3進行裝卸作業，開始和結束時間分別為22和31，停泊位置從51到150；岸橋3和4為船舶4進行裝卸作業，開始和結束時間分別為12和31，停泊位置從151到300.

圖6 不規則型泊位和岸橋分配方案

表2 船舶數為8的算例已知參數

表3和表4為不同迭代代數和隨機學習因子參數設置下的求解結果，可以看出當迭代代數為1000代，學習因子c3取1.5時，PSO算法的求解結果更優，因此，將迭代代數設置為1000代，隨機學習因子設置為1.5.

表3 改進PSO算法不同迭代次數的結果

表4 改進PSO隨機學習因子參數設置

表5為標準粒子群算法、改進粒子群算法以及CPLEX求解結果的對比，偏差1=(SPSO-IPSO)×100%/IPSO；偏差2=(IPSO-CPLEX)×100%/CPLEX.從實驗結果可以看出，改進前后粒子群算法求解結果偏差的最大值為25.52，在所有實驗中，偏差的平均值為16.62.隨著船舶數量的增加，偏差呈現逐漸增大的趨勢.改進粒子群算法的求解結果與CPLEX算法求解結果的最大偏差為4.37%，平均偏差為2.89%，而CPLEX軟件的平均求解時間為253.77，改進粒子群算法的平均求解時間僅為0.39 s，證明了設計的粒子群算法的有效性.

表5 標準PSO、改進PSO和CPLEX結果對比

為了驗證本文改進粒子群算法在求解較大規模問題時的有效性，分別采用標準PSO和改進PSO對不同規模的問題進行求解，結果如表6所示，表中偏差 =(SPSO-IPSO)×100%/IPSO，每個規模的結果均為10組同規模算例求解所得的平均值.可以看到，在各個規模下，改進PSO的結果均優于標準PSO的結果，證明了改進PSO在求解較大規模問題時的有效性.

表6 標準PSO和改進PSO結果對比

綜上，在模型中加入有效不等式后，模型的求解時間明顯減少.在所有算例中，改進粒子群算法的求解結果均優于標準粒子群算法的求解結果，這是由于標準粒子群算法容易陷入局部最優，加入隨機學習因子后，增加了粒子尋優的范圍，更容易找到優化解.從表5和表6可以看出，改進粒子群算法相比標準粒子群算法，在求解質量上分別提高了16.62%和33.80%,即：針對全部17個算例，求解質量平均提高了25.21%.

5 結 論

本文研究了集裝箱港口不規則型泊位和岸橋集成分配問題.針對該問題，我們建立了線性規劃數學模型，并通過CPLEX軟件進行求解；針對問題規模增加，求解時間變長的問題，在模型中加入三個有效不等式，使模型的求解時間降低了83.23%.針對船舶數目增加后，CPLEX軟件無法在可接受時間內求解的情況，本文提出了粒子群算法進行求解.實驗結果證明，改進粒子群算法相比標準粒子群算法，求解質量提高了25.21%，證明了本文設計的改進粒子群算法在求解不規則型泊位和岸橋分配問題時的有效性.

本文的研究為針對計劃期內所有船舶到港時間不再發生變化的情況，且只考慮了岸橋進行貝位作業的分配，未考慮岸橋進行對應貝位裝卸作業的先后順序安排，未來將針對船舶到達時間不確定的不規則泊位和岸橋集成調度問題進行建模和優化研究.