基于GASA的帶時(shí)間窗航運(yùn)空箱調(diào)運(yùn)模型

閔德權(quán)，孫海萍

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026)

0 引 言

各個(gè)國(guó)家之間因經(jīng)濟(jì)、貿(mào)易、社會(huì)生產(chǎn)力發(fā)展的不平衡導(dǎo)致了世界范圍內(nèi)各個(gè)港口的集裝箱分布不均。特別是受新冠疫情影響，許多國(guó)家的生產(chǎn)能力處于很低的水平，這讓率先步入生產(chǎn)正軌的中國(guó)在短時(shí)間內(nèi)成為了世界工廠的中心。在上海、寧波、青島、連云港等大型港口中，集裝箱嚴(yán)重短缺導(dǎo)致了船舶的延遲停泊，而在歐美國(guó)家的許多港口卻因集裝箱激增導(dǎo)致了貨物運(yùn)輸?shù)膿矶耓1]?；诖耍瑧?yīng)通過(guò)合理的空箱調(diào)運(yùn)，及時(shí)將集裝箱過(guò)剩港口的空箱運(yùn)往缺少集裝箱的港口。這樣不僅降低了集裝箱空箱庫(kù)存成本，提高了空箱、碼頭等資源的利用率；而且還及時(shí)滿足了客戶對(duì)集裝箱的需求，降低了集裝箱租賃成本和公司信譽(yù)損失。因此，研究空箱調(diào)運(yùn)問(wèn)題具有非常現(xiàn)實(shí)的意義。

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

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

1 模型構(gòu)建

1.1 問(wèn)題描述

假設(shè)在一個(gè)航運(yùn)服務(wù)運(yùn)輸網(wǎng)絡(luò)中，有n個(gè)港口需要k類集裝箱空箱，有m個(gè)港口有多余的k類集裝箱空箱。各集裝箱需求港對(duì)集裝箱到港時(shí)間有一定要求，當(dāng)空箱過(guò)早到達(dá)目的港口時(shí)會(huì)產(chǎn)生一定的港口堆積成本；當(dāng)空箱過(guò)晚到達(dá)目的港口時(shí)會(huì)影響信譽(yù)度進(jìn)而損失部分客戶，產(chǎn)生機(jī)會(huì)成本。筆者需要在有時(shí)間約束情況下制定出使總運(yùn)輸成本最少的航運(yùn)集裝箱空箱調(diào)運(yùn)方案。

1.2 符號(hào)變量

1.3 目標(biāo)函數(shù)建立

建立目標(biāo)函數(shù)如式(1)～式(7)：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

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

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

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

式(4)中：t時(shí)段港口i對(duì)k類集裝箱的供給量不超過(guò)t時(shí)段在港口i上k類集裝箱的產(chǎn)量。

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

式(6)中：t時(shí)段從港口i到港口j通過(guò)運(yùn)輸方式l運(yùn)輸k類集裝箱的數(shù)量不超過(guò)t時(shí)段從港口i到港口j通過(guò)運(yùn)輸方式l對(duì)k類集裝箱運(yùn)輸?shù)淖畲筮\(yùn)輸數(shù)量。

式(7)中：t時(shí)段從港口i到港口j通過(guò)運(yùn)輸方式l運(yùn)輸?shù)趉類集裝箱的數(shù)量不小于0。

2 算法求解

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

圖1 遺傳模擬退火搜尋最優(yōu)解過(guò)程Fig. 1 Search process of optimal solution for GASA

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

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

2.1 初始種群

根據(jù)運(yùn)輸問(wèn)題性質(zhì)，筆者采用自然數(shù)編碼產(chǎn)生初始可行解。用矩陣描述運(yùn)輸問(wèn)題，分配矩陣如式(8)：

(8)

式中：Xp代表種群中第p個(gè)染色體矩陣；xij代表從港口i運(yùn)輸?shù)礁劭趈的集裝箱數(shù)量。

將Xp的每行首尾相連，該個(gè)體的基因型可描述為如下串結(jié)構(gòu)，即有：X′p=[x11,x12, …,x1j,x21,x22, …,x2j, …,xi1,xi2, …,xij]?？紤]到由港口i運(yùn)往港口j的k類集裝箱和集裝箱運(yùn)輸方式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 適應(yīng)度函數(shù)

用目標(biāo)函數(shù)值來(lái)評(píng)估染色體適應(yīng)度大小，用eval(Xp)來(lái)表示染色體矩陣Xp的適應(yīng)度函數(shù)值。故模型適應(yīng)度函數(shù)可直接表達(dá)如式(9)：

(9)

2.3 約束條件處理

構(gòu)造懲罰項(xiàng)，當(dāng)滿足約束條件時(shí)，懲罰項(xiàng)為0；當(dāng)不滿足約束條件時(shí)，加大懲罰，即加大不可行點(diǎn)處對(duì)應(yīng)的目標(biāo)函數(shù)值，使不可行點(diǎn)不能成為相應(yīng)問(wèn)題的最優(yōu)解。不等式約束處理過(guò)程如圖3，等式約束處理過(guò)程如圖4。

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

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

2.4 交 叉

選擇一個(gè)較優(yōu)秀的個(gè)體(累加概率大于均值為0，方差σ2=1，標(biāo)準(zhǔn)差σ=1的正態(tài)分布的隨機(jī)數(shù))作為父親和母親，隨機(jī)設(shè)置交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。交叉過(guò)程如圖5。

圖5 交叉過(guò)程Fig. 5 Cross process diagram

2.5 變 異

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

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

2.6 判 斷

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

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

3 算 例

設(shè)某航運(yùn)運(yùn)輸網(wǎng)絡(luò)有12個(gè)港口，其中6個(gè)港口有多余集裝箱，6個(gè)港口缺少集裝箱；現(xiàn)通過(guò)一般海運(yùn)(L1)、海鐵聯(lián)運(yùn)(L2)這兩種運(yùn)輸方式進(jìn)行空箱調(diào)運(yùn)。假設(shè)各港口之間不管采用哪種運(yùn)輸方式，運(yùn)輸天數(shù)都一樣，且船舶運(yùn)輸集裝箱空箱數(shù)量不超過(guò)30 TEU。提前到達(dá)目的港口所產(chǎn)生的堆積費(fèi)用為每個(gè)集裝箱每天3元/箱，延期到達(dá)所產(chǎn)生的機(jī)會(huì)成本為6元/箱。各港口之間運(yùn)輸時(shí)間見(jiàn)表1，各供給港多余集裝箱情況見(jiàn)表2，各需求港對(duì)集裝箱的需求情況見(jiàn)表3。采用L1運(yùn)輸方式時(shí)，k1類集裝箱的運(yùn)輸成本為50元，k2類為52元；采用L2運(yùn)輸方式時(shí)，k1類集裝箱的運(yùn)輸成本為51元，k2類為58元。

表1 各港口之間的運(yùn)輸時(shí)間Table 1 Transport time between ports 天

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

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

根據(jù)改進(jìn)遺傳模擬退火算法對(duì)12個(gè)港口進(jìn)行空箱調(diào)度。當(dāng)種群規(guī)模Z=600，進(jìn)化次數(shù)NP=100，交叉概率Pc=0.6，變異概率Pm=0.1，初始溫度t0=100，結(jié)束溫度tf=45，溫度下降比例a=0.98時(shí)搜索效果較好。對(duì)上述實(shí)例，經(jīng)MATLAB仿真得到模型的最優(yōu)空箱調(diào)度方案如表4。

表4 改進(jìn)遺傳模擬退火算法得出的最優(yōu)空箱調(diào)度方案Table 4 Optimal empty container scheduling scheme obtained by improved GASA

供給港提供20 GP箱型集裝箱空箱總數(shù)為140箱，提供40 GP箱型集裝箱空箱總數(shù)為40箱；需求港20 GP箱型集裝箱空箱總接受量為125箱，40 GP箱型集裝箱空箱總接受量為40箱。除S2港到D2港采用海鐵聯(lián)運(yùn)外，其余港口均選擇一般海運(yùn)的運(yùn)輸方式?？傉{(diào)運(yùn)成本為8 281元，其中過(guò)早到達(dá)港口的港口堆積成本為45元，過(guò)晚到達(dá)港口的機(jī)會(huì)成本為78元，滿足約束條件。

4 結(jié) 語(yǔ)

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