楊 揚，王 迪

（1.廈門海洋職業(yè)技術學院，福建 廈門 361012；2.大連海事大學 交通運輸管理學院，遼寧 大連 116026）

隨著經(jīng)濟全球化、貿(mào)易國際化的深入發(fā)展，國際海運業(yè)得到迅猛發(fā)展，集裝箱運輸具有運量大、裝卸及疏運快、節(jié)約包裝材料、安全便捷等優(yōu)點，越來越多的散雜貨選擇集裝箱運輸，所以，集裝箱運輸已成為全球國際貿(mào)易中最重要的運輸方式之一。然而集裝箱海運業(yè)的繁榮對其自身的經(jīng)營管理模式及網(wǎng)絡結構提出了更高要求，高效、有序的港口集裝箱運輸網(wǎng)絡有待完善與優(yōu)化。由于地區(qū)間經(jīng)濟貿(mào)易的不平衡性以及船運公司集裝箱管理水平存在差異，空箱調(diào)運在整個集裝箱運輸系統(tǒng)中占據(jù)了大量比重。研究如何減少集裝箱空箱調(diào)運，對于促進集裝箱運輸快速發(fā)展、協(xié)調(diào)多式聯(lián)運、提高企業(yè)經(jīng)濟效益具有重要意義。

由于空箱調(diào)運產(chǎn)生的成本對船公司的運營收益產(chǎn)生了很大影響，船公司對該問題非常重視，并引發(fā)了學術界的研究興趣。集裝箱調(diào)運問題主要研究的是何時從何地將多少數(shù)量的空箱通過何種運輸方式調(diào)運到有需求的指定地點?？障湔{(diào)運問題具有隨時間推移供需地發(fā)生變化的動態(tài)性，箱種、節(jié)點、運輸工具眾多的復雜性，以及空箱需求與供給的隨機性和運輸能力及供應時間的限制性等多方面特性。由于空箱調(diào)運問題中過程參數(shù)、不確定因素眾多使問題相當復雜。當前國內(nèi)相關專家、學者對此問題進行了較多的研究，取得了相當?shù)某晒?，并對實際運營過程做出有益的參考。其中，施欣對海上空箱調(diào)運的過程進行分析，并建立了系統(tǒng)優(yōu)化模型[1]；劉恒江等以航線經(jīng)營人為主體，建立了空箱調(diào)運的Petri網(wǎng)模型[2]；周紅梅等借鑒了鐵路空車調(diào)度優(yōu)化模型，建立了海運空箱調(diào)運優(yōu)化模型[3]；Florez等建立利潤優(yōu)化模型來研究遠洋航運企業(yè)空箱租賃和重新配置問題[4]；Shen等構建了海運空箱調(diào)運決策支持系統(tǒng)[5]。

然而這些研究在建立模型時都進行了大量假設，考慮因素較少，與實際系統(tǒng)相差較遠，大大降低了模型的實用性。本文擬在考慮多箱種的情況下，建立合理的空箱調(diào)運動態(tài)優(yōu)化模型，并運用遺傳算法進行優(yōu)化求解，并用某港口實例數(shù)據(jù)對模型進行了驗證，證明了模型的正確性和遺傳算法的有效性。

1 空箱調(diào)運模型

本文將建立多箱種情況下的空箱調(diào)運模型，目標函數(shù)為在滿足重箱運輸?shù)那疤嵯拢箍障湔{(diào)運的總費用最少?？傎M用由以下幾種費用組成：空箱的運輸費用、在各節(jié)點的儲存費用以及租箱費用。

1.1 模型假設

（1）每一期每個節(jié)點的空箱數(shù)量已知、每個節(jié)點的空箱需求量已知；（2）不考慮集裝箱的維修、報廢情況，即所有集裝箱均是可用的；（3）不存在轉(zhuǎn)運現(xiàn)象，空箱是直接由供應地向需求地的直達運輸；（4）各航線的集裝箱運輸不允許不同箱型相互替換；（5）考慮兩種箱型：20英尺和40英尺；（6）空箱調(diào)運決策期為1周（5天計算），決策間隔以天計算；（7）需求客戶的需求必須得到滿足，不存在棄貨問題；（8）只有到時段末還未運送的集裝箱發(fā)生堆存費用。

1.2 模型建立

根據(jù)以上假設及其空箱調(diào)運實際情況，可以建立如下空箱調(diào)運模型，相關參數(shù)和變量規(guī)定如下：

1.2.1 參數(shù)

T：為計劃周期；Dt：t時段時所有需求點的集合；St：t時段是所有供給點的集合；：t時段節(jié)點i缺k種箱型的數(shù)量；：t時段節(jié)點j能供應k種箱型的數(shù)量；M：所有供給點和需求點的集合；K：各種箱型的集合，包括20英尺和40英尺兩種；：在時段t從i到j運輸?shù)趉種箱型的單位運輸費用；：在時段t從i到j運輸?shù)趉種箱型的箱量；：在時段t節(jié)點i的第k種箱型的存儲量；：節(jié)點i的存儲能力限制；：在時段t節(jié)點i的k種箱的單位存儲費用；：在時段t節(jié)點i和j之間由k種箱運輸?shù)恼{(diào)運量；τij：從節(jié)點i到j得運輸時間；：運輸能力限制；：系統(tǒng)外調(diào)箱的單位費用；：系統(tǒng)外調(diào)箱量；：t時段m點本地產(chǎn)生的空箱。

1.2.2 目標函數(shù)

目標函數(shù)考慮各期在需求客戶和供給客戶之間的空箱調(diào)運費用最少。

1.2.3 約束條件

約束條件（2）表示客戶的集裝箱需求量必須滿足。

約束條件（3）表示各時段末各節(jié)點處的空箱庫存。

約束條件（4）表示各時段供應節(jié)點的供應量。

約束條件（5）表示在各個時段，節(jié)點之間的運輸量不能超過該種運輸方式的運輸能力。

約束條件（6）表示各節(jié)點的存箱量不能超過該點的容量。

2 遺傳算法原理

遺傳算法（Genetic Algorithms，GA）是由美國Michigan大學的John H.Holland教授創(chuàng)建的，它模擬了自然選擇和進化過程中的繁殖、雜交和突變現(xiàn)象。其基本思想為：按照“適者生存”和“優(yōu)勝劣汰”的原理，從優(yōu)化問題一個種群（即一組可行解）開始，逐代進化產(chǎn)生出越來越好的一個新的種群（一組的可行解）。在每一代，根據(jù)個體（可行解）適應度（目標函數(shù)值）的優(yōu)劣挑選一分優(yōu)良個體復制（繁殖）到下一代，被選擇的個體經(jīng)過交叉和變異算子的作用生成新的一代，新的個體由于繼承了上一代的一些優(yōu)良性狀，因而在性能上優(yōu)于上一代，這個過程將導致種群類似自然進化一樣，子代種群比父代種群更加適于環(huán)境，也就是生成新的可行解優(yōu)于舊的可行解，最后，將整個進化過程中最優(yōu)個體作為問題的最終解。

由于遺傳算法對適應度函數(shù)沒有連續(xù)可微的要求，具有高效的全局優(yōu)化能力，并且其操作對象是編碼個體，可以處理諸如矩陣、樹和圖等結構形式的對象，因此在解決高維復雜優(yōu)化問題上顯示出很強的生命力，在實際中得到了廣泛的應用?；谶z傳算法的特點和空箱調(diào)運問題的特征，本文采用了遺傳算法對該問題進行優(yōu)化。

3 算法描述及其實例

3.1 算法設計

（1）編碼方案：根據(jù)本文模型決策變量的特征，本文采用多維的實數(shù)編碼形式。例如，用實數(shù)集合M=｛1, 2 ,…,n｝表示港口集合，K=｛1,2｝表示箱型（20英尺和40英尺），則t時段的一個可行解表示為：

這個解直觀的表達就是：港口1向港口2調(diào)運x1個集裝箱（箱型是20英尺），港口5向港口3調(diào)運x2個集裝箱（箱型是40英尺），……。

（2）選擇：采用輪盤賭選擇算子，這雖然增大了遺傳算法的隨機性，但保證群體的多樣性，使算法不至于過早收斂。

（3）交叉：交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關鍵作用。由于基本交叉算子單點交叉、多點交叉不能滿足本文空箱調(diào)運問題的特殊性要求（它們都會產(chǎn)生大量不可行解），所以本文采用的交叉算子為循環(huán)交叉算子，該算子能修正交叉過程中生成的不可行解。

（4）變異：變異是指將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它是必不可少的一個運算步驟。變異本身是一種全局隨機搜索，與選擇算子結合在一起，保證了遺傳算法的有效性，使遺傳算法具有全局的隨機搜索能力，同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。本文在考慮編碼設計及問題實際的情況下采用均勻變異算子對種群進行變異操作。

算法流程圖如圖1所示。

圖1 算法流程圖

3.2 實例

本文考慮六個港口的空箱調(diào)運問題，算例中假設運輸能力和堆存能力無限制，只考慮一種箱型（40英尺），在一個計劃期內(nèi)，航線掛靠順序不變。這六個港口的運輸網(wǎng)絡模型如圖2所示。港口運輸時間、費用如表1所示。港口初始庫存和各時段需求狀況分別如表2、表3所示。

圖2 運輸網(wǎng)絡圖

表1 港口間的運輸時間、費用表 單位：天、$/TEU

表2 港口空箱基本數(shù)據(jù)

表3 港口需求表 單位：TEU

該算法利用matlabR2009程序?qū)崿F(xiàn)，取最大迭代數(shù)G=500，本文針對不同種群規(guī)模進行了大量測試，結果表明當種群規(guī)模N=100左右時效率最高；對交叉概pc為0.7、0.8、0.9分別進行了10次試驗發(fā)現(xiàn)交叉概率的變化對算法的效率影響并不是很大，所以取交叉概率pc=0.8。最后，我們進行了三組實驗，分別取變異概率pm為0.001、0.01、0.1，由實驗結果分析得出當變異概率時pm=0.01，效果最好。最終得出最優(yōu)解，第一期調(diào)運結果：由港口B至A調(diào)運空箱80個，由E至C調(diào)運空箱163個，由F至E調(diào)運空箱10個，總費用為6 119美元，其中庫存費用為2 158美元；第二期調(diào)運結果：由B至A調(diào)運空箱75個，由E至A調(diào)運空箱9個，由C至E調(diào)運空箱13個，總費用為5 051美元，其中庫存費用為3 014美元；第三期調(diào)運結果：由B至A調(diào)運空箱119個，由E至C調(diào)運空箱110個，總費用為6 734美元，其中庫存費用為3 065美元；第四期調(diào)運結果：由B至C調(diào)運空箱24個，由A至E調(diào)運空箱23個，由D至E調(diào)運空箱200個，總費用為8 738美元，其中庫存費用為2 065美元；第五期調(diào)運結果：由B至A調(diào)運空箱76個，由E至C調(diào)運空箱125個，由D至E調(diào)運空箱46個，總費用為6 938美元，其中庫存費用為3 075美元，租箱費用為315美元。這一周期的總費用為33 580美元。

4 結 論

本文力求與實際情況接近，充分考慮了空箱調(diào)運問題中多箱型的現(xiàn)實情況，應用動態(tài)規(guī)劃的思想，建立了多箱型的集裝箱空箱調(diào)運優(yōu)化模型。最后，本文運用遺傳算法對所建立的模型在matlab平臺下進行了編程仿真，為港口間空箱調(diào)運提供了具體的方案。本文模型的目的在于提高航運企業(yè)的空箱調(diào)運管理水平和調(diào)運效率，節(jié)省不必要的運輸費用。

[1]施欣.集裝箱海運空箱調(diào)運優(yōu)化分析[J].系統(tǒng)工程理論與實踐，2003(23):70-75.

[2]劉恒江，施欣.基于Petri網(wǎng)的集裝箱空箱調(diào)運方針分析[J].交通運輸工程報，2002,2(3):97-102.

[3]周紅梅，方芳.航運集裝箱空箱調(diào)運優(yōu)化模型的研究[J].武漢理工大學學報，2003,2(7):384-387.

[4]Florez.H.Empty container Repositioning and Leas2ing:An Optimization Model[R].Ph.D Dissertation,Polytechnic Institute of New York,New York,1986.

[5]W.S.Shen,C.M.Khoong.A DSS for empty container distribution planning[J].Decision Support Systems,1995(15):75-82.

[6]王斌.海運空箱調(diào)運模糊優(yōu)化研究[J].港工技術，2007,8(4):11-13.

[7]王小平，曹立明.遺傳算法—理論、應用與軟件實現(xiàn)[M].西安：西安交通大學出版社，2002.

[8]趙道致，黃健.基于海陸運整體成本的集裝箱空箱調(diào)運優(yōu)化研究[J].北京交通大學學報，2008,7(4):48-52.