基于GASA的帶時間窗航運空箱調運模型

閔德權，孫海萍

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

0 引 言

各個國家之間因經濟、貿易、社會生產力發展的不平衡導致了世界范圍內各個港口的集裝箱分布不均。特別是受新冠疫情影響，許多國家的生產能力處于很低的水平，這讓率先步入生產正軌的中國在短時間內成為了世界工廠的中心。在上海、寧波、青島、連云港等大型港口中，集裝箱嚴重短缺導致了船舶的延遲停泊，而在歐美國家的許多港口卻因集裝箱激增導致了貨物運輸的擁堵[1]。基于此，應通過合理的空箱調運，及時將集裝箱過剩港口的空箱運往缺少集裝箱的港口。這樣不僅降低了集裝箱空箱庫存成本，提高了空箱、碼頭等資源的利用率；而且還及時滿足了客戶對集裝箱的需求，降低了集裝箱租賃成本和公司信譽損失。因此，研究空箱調運問題具有非常現實的意義。

目前，學界對航運集裝箱空箱調運進行了大量研究。孫佳慶等[2]在盡量降低系統成本和重箱分配計劃的前提下，對航運公司剩余的可用空箱和艙位進行集中分配；徐姍等[3]從航運公司角度出發，建立了考慮空箱調運的集裝箱網絡路徑優化模型；WANG Hua等[4]在同時考慮船舶航線的最佳出發時刻表和貨物分配方案的情況下，對空箱調運問題進行了研究；連峰等[5]根據集裝箱投入使用的年限對集裝箱生命周期進行了區分，并對班輪航線網絡的空箱調運進行了優化；陳俊軍等[6]在低碳背景下通過考慮空箱需求的不確定性，建立了港口空箱調運和航速的決策模型；計明軍等[7]針對沿海港口之間的集裝箱空箱調運問題，建立了以調運成本最小為目標的數學模型；A.G.WESPARP等[8]提出一種解決重、空集裝箱調運問題的模糊優化方法；丁敏等[9]采用優化策略的啟發式算法，計算了各港口的具體空箱調度方案； S.W.LAM等[10]利用優化模型給出了各港口空箱庫存上下限來求解空箱調度問題，采用啟發式算法求解以總成本最小化為目標的空箱調度優化模型；謝新連等[11]根據MDA分析法對特征變量重要性進行分析，建立了基于隨機森林算法的預測模型，并以大連港為案例進行驗證，得出隨機森林算法對預測港口集裝箱吞吐量準確性更高的結論；張欣等[12]研究了全球集裝箱海運網絡的脆弱性，運用復雜網絡理論在分析海運網絡拓撲結構特征的基礎上，模擬了港口失效連鎖反應。

綜合以上研究可看出，這些學者在對航運集裝箱空箱調運研究時，較少考慮因缺少集裝箱港口時間窗造成的堆積成本和機會損失成本。基于此，筆者針對集裝箱種類和運輸方式的多樣性，建立了以集裝箱空箱調運成本為優化目標，帶時間窗的航運集裝箱空箱調運模型；采用改進遺傳模擬退火算法(GASA)求解所建立的數學模型。引入模擬退火算法對遺傳算法進行改進后，既保留了遺傳算法全局搜索的特性，又提高了局部搜索能力，確保了搜尋結果是全局最優解，實現了航運集裝箱的空箱調運最少成本方案。

1 模型構建

1.1 問題描述

假設在一個航運服務運輸網絡中，有n個港口需要k類集裝箱空箱，有m個港口有多余的k類集裝箱空箱。各集裝箱需求港對集裝箱到港時間有一定要求，當空箱過早到達目的港口時會產生一定的港口堆積成本；當空箱過晚到達目的港口時會影響信譽度進而損失部分客戶，產生機會成本。筆者需要在有時間約束情況下制定出使總運輸成本最少的航運集裝箱空箱調運方案。

1.2 符號變量

1.3 目標函數建立

建立目標函數如式(1)～式(7)：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

目標函數式(1)由3部分組成，分別是不考慮時間約束的集裝箱調運成本、因集裝箱過早到達造成的集裝箱港口堆積成本、集裝箱過晚到達所產生的機會成本。在班輪運輸中，班輪公司很少因延遲交貨而對托運人進行補償，但由于船舶到達的正點率低或頻繁的延誤交貨，會影響船公司的服務水平和客戶信譽度，從而損失一部分客戶，影響其市場占有率，因此集裝箱延期到達會產生機會成本。

式(2)中：t時段從港口i通過運輸方式l運輸k類集裝箱到港口j的數量等于t時段港口j缺少k類集裝箱的數量。

式(3)中：t時段港口i提供k類集裝箱的數量不小于t時段從港口i通過運輸方式l運輸k類集裝箱到港口j的數量。

式(4)中：t時段港口i對k類集裝箱的供給量不超過t時段在港口i上k類集裝箱的產量。

式(5)中：t時段港口i存儲k類集裝箱的數量不超過t時段港口i存儲k類集裝箱的能力。

式(6)中：t時段從港口i到港口j通過運輸方式l運輸k類集裝箱的數量不超過t時段從港口i到港口j通過運輸方式l對k類集裝箱運輸的最大運輸數量。

式(7)中：t時段從港口i到港口j通過運輸方式l運輸第k類集裝箱的數量不小于0。

2 算法求解

遺傳算法是一種全局隨機優化算法，適用于求解帶有復雜多約束條件的數學模型。在優化目標函數時，可用更大的概率搜索全局最優解，它具有全局尋優和隱式并行的特性，但存在早熟收斂從而陷入局部最優解的弊端。模擬退火算法出發點是源于物理學中固體物質的退火過程，它能以一定概率跳出局部最優解，最終逼近全局最優解。該算法不僅能朝目標函數的優化方向迭代，還可以接受目標函數以一定概率的惡化，從而避免陷入局部最優解。但當搜索范圍變大時，存在收斂速度慢、執行時間長、容易受參數影響等缺點。遺傳模擬退火搜尋最優解過程如圖1。

圖1 遺傳模擬退火搜尋最優解過程Fig. 1 Search process of optimal solution for GASA

筆者將遺傳算法和模擬退火算法的優點相結合，在遺傳算法中引入模擬退火，提出一種混合遺傳模擬退火算法求解的集裝箱空箱調運模型，將這兩種算法的搜索能力得到相互補充，不僅提高了遺傳算法的局部搜索能力，還避免了遺傳算法陷入局部最優解，遺傳模擬退火算法流程如圖2。

圖2 遺傳模擬退火算法流程Fig. 2 Flow chart of GASA

2.1 初始種群

根據運輸問題性質，筆者采用自然數編碼產生初始可行解。用矩陣描述運輸問題，分配矩陣如式(8)：

(8)

式中：Xp代表種群中第p個染色體矩陣；xij代表從港口i運輸到港口j的集裝箱數量。

將Xp的每行首尾相連，該個體的基因型可描述為如下串結構，即有：X′p=[x11,x12, …,x1j,x21,x22, …,x2j, …,xi1,xi2, …,xij]。考慮到由港口i運往港口j的k類集裝箱和集裝箱運輸方式l不同，故將l和k插入到X′p中，即有：X″p=[x11,l,k,x12,l,k, …,x1j,l,k,x21,l,k,x22,l,k, …,x2j,l,k, …,xi1,l,k,xi2,l,k, …,xij,l,k]。

2.2 適應度函數

用目標函數值來評估染色體適應度大小，用eval(Xp)來表示染色體矩陣Xp的適應度函數值。故模型適應度函數可直接表達如式(9)：

(9)

2.3 約束條件處理

構造懲罰項，當滿足約束條件時，懲罰項為0；當不滿足約束條件時，加大懲罰，即加大不可行點處對應的目標函數值，使不可行點不能成為相應問題的最優解。不等式約束處理過程如圖3，等式約束處理過程如圖4。

圖3 不等式約束處理過程流程Fig. 3 Flow chart of inequality constraint processing

圖4 等式約束處理過程流程Fig. 4 Flow chart of equality constraint processing

2.4 交 叉

選擇一個較優秀的個體(累加概率大于均值為0，方差σ2=1，標準差σ=1的正態分布的隨機數)作為父親和母親，隨機設置交叉點，然后在該點相互交換兩個配對個體的部分染色體。交叉過程如圖5。

圖5 交叉過程Fig. 5 Cross process diagram

2.5 變 異

采用均勻變異且精英不參加的方法，分別用符合某一范圍內均勻分布的隨機數，以某一較小的概率來替換個體編碼串中各基因座上的原有基因值，變異流程如圖6。

圖6 變異流程Fig. 6 Variation flow chart

2.6 判 斷

引入模擬退火判斷是否變異。計算變異后的 種群適應度與變異前的適應度差值ε，若變異后的種群適應度優于變異前的種群適應度，則接受變異；若變異后的種群適應度劣于變異前的種群適應度，則以一定的退火概率exp(ε/T)來確定是否發生變異，退火流程如圖7。

圖7 退火流程Fig. 7 Annealing flow chart

3 算 例

設某航運運輸網絡有12個港口，其中6個港口有多余集裝箱，6個港口缺少集裝箱；現通過一般海運(L1)、海鐵聯運(L2)這兩種運輸方式進行空箱調運。假設各港口之間不管采用哪種運輸方式，運輸天數都一樣，且船舶運輸集裝箱空箱數量不超過30 TEU。提前到達目的港口所產生的堆積費用為每個集裝箱每天3元/箱，延期到達所產生的機會成本為6元/箱。各港口之間運輸時間見表1，各供給港多余集裝箱情況見表2，各需求港對集裝箱的需求情況見表3。采用L1運輸方式時，k1類集裝箱的運輸成本為50元，k2類為52元；采用L2運輸方式時，k1類集裝箱的運輸成本為51元，k2類為58元。

表1 各港口之間的運輸時間Table 1 Transport time between ports 天

表2 供給港多余集裝箱情況Table 2 Surplus containers at supply port

表3 需求港需要集裝箱情況Table 3 Container demand at demand port

根據改進遺傳模擬退火算法對12個港口進行空箱調度。當種群規模Z=600，進化次數NP=100，交叉概率Pc=0.6，變異概率Pm=0.1，初始溫度t0=100，結束溫度tf=45，溫度下降比例a=0.98時搜索效果較好。對上述實例，經MATLAB仿真得到模型的最優空箱調度方案如表4。

表4 改進遺傳模擬退火算法得出的最優空箱調度方案Table 4 Optimal empty container scheduling scheme obtained by improved GASA

供給港提供20 GP箱型集裝箱空箱總數為140箱，提供40 GP箱型集裝箱空箱總數為40箱；需求港20 GP箱型集裝箱空箱總接受量為125箱，40 GP箱型集裝箱空箱總接受量為40箱。除S2港到D2港采用海鐵聯運外，其余港口均選擇一般海運的運輸方式。總調運成本為8 281元，其中過早到達港口的港口堆積成本為45元，過晚到達港口的機會成本為78元，滿足約束條件。

4 結 語

筆者在傳統遺傳算法的基礎上，引入模擬退火法，允許在迭代過程中以一定概率接受與迭代方向相反的解，避免了過早收斂陷入局部最優解；通過精英保留策略保證了最優個體不被破壞，提高了算法的收斂能力；最后通過實例驗證了所構建的空箱調度模型為解決航運集裝箱空箱調運提供了一個非常有效地解決方法。