楊 揚(yáng)，王 迪

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

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

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

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

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

本文將建立多箱種情況下的空箱調(diào)運(yùn)模型，目標(biāo)函數(shù)為在滿足重箱運(yùn)輸?shù)那疤嵯?，使空箱調(diào)運(yùn)的總費(fèi)用最少。總費(fèi)用由以下幾種費(fèi)用組成：空箱的運(yùn)輸費(fèi)用、在各節(jié)點(diǎn)的儲(chǔ)存費(fèi)用以及租箱費(fèi)用。

1.1 模型假設(shè)

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

1.2 模型建立

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

1.2.1 參數(shù)

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

1.2.2 目標(biāo)函數(shù)

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

1.2.3 約束條件

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

約束條件（3）表示各時(shí)段末各節(jié)點(diǎn)處的空箱庫(kù)存。

約束條件（4）表示各時(shí)段供應(yīng)節(jié)點(diǎn)的供應(yīng)量。

約束條件（5）表示在各個(gè)時(shí)段，節(jié)點(diǎn)之間的運(yùn)輸量不能超過(guò)該種運(yùn)輸方式的運(yùn)輸能力。

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

2 遺傳算法原理

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

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

3 算法描述及其實(shí)例

3.1 算法設(shè)計(jì)

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

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

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

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

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

算法流程圖如圖1所示。

圖1 算法流程圖

3.2 實(shí)例

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

圖2 運(yùn)輸網(wǎng)絡(luò)圖

表1 港口間的運(yùn)輸時(shí)間、費(fèi)用表 單位：天、$/TEU

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

表3 港口需求表 單位：TEU

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

4 結(jié) 論

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

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

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

[3]周紅梅，方芳.航運(yùn)集裝箱空箱調(diào)運(yùn)優(yōu)化模型的研究[J].武漢理工大學(xué)學(xué)報(bào)，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]王斌.海運(yùn)空箱調(diào)運(yùn)模糊優(yōu)化研究[J].港工技術(shù)，2007,8(4):11-13.

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

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