基于列生成算法的集裝箱班輪運輸網(wǎng)絡(luò)優(yōu)化

吳瓊, 鄭士源, 朱太球

(1. 上海海事大學(xué) 交通運輸學(xué)院, 上海 201306; 2. 浙江榮盛控股集團(tuán) 人力資源部, 杭州 311247)

0 引 言

隨著航運市場的實時變動，集裝箱班輪運輸網(wǎng)絡(luò)優(yōu)化成為很多航運公司需要面對的重要問題.集裝箱班輪航線優(yōu)化是運輸網(wǎng)絡(luò)優(yōu)化的一部分.CHRISTIANSEN等[1]建立的班輪模型計算量大使得越來越多的班輪運輸網(wǎng)絡(luò)優(yōu)化模型相繼出現(xiàn)，班輪運輸網(wǎng)絡(luò)的優(yōu)化更加復(fù)雜化，運輸網(wǎng)絡(luò)優(yōu)化的模型規(guī)模也逐漸加大.目前求解大型運輸模型的方法主要有枚舉法、貪婪算法、列生成算法和Benders分解算法.枚舉法求解運輸模型效率較低，貪婪算法隨著模型規(guī)模的增大求解速度和準(zhǔn)確性降低.CHUANG等[2]通過包含有5個港口的小型案例解釋說明他們的遺傳算法，其目的是通過在不確定性部分運用遺傳算法與在離散部分運用遺傳算法相結(jié)合求出需求不確定時的最優(yōu)航線.GELAREH等[3]運用Benders分解原則求解模型并求出轉(zhuǎn)運港位置以及輻射港與轉(zhuǎn)運港連接的類型.本文采用啟發(fā)式列生成算法對運輸網(wǎng)絡(luò)模型分塊求解，既能提高求解效率又能增強求解結(jié)果的準(zhǔn)確性.

1 問題提出

在集裝箱班輪運輸中運輸路徑和貨物運量決定航運聯(lián)盟可以從此運輸網(wǎng)絡(luò)中獲得的收益.這兩者高度相關(guān)而且需要同時考慮，因此決策變量即為運輸路徑和貨物運量.在以利潤最大為目標(biāo)函數(shù)的同時，需要考慮以下約束：每段航線和港口貨物運量的平衡、船隊運能約束、運輸需求約束以及承運人船舶數(shù)量的約束.[4]本文根據(jù)設(shè)計模型的特點，選擇啟發(fā)式列生成算法，可以大幅減小模型規(guī)模，有效減少計算時間，并利用IBM-ILOG優(yōu)化平臺和IBM-ILOG CPLEX優(yōu)化引擎實現(xiàn)該算法，實驗計算表明該算法具有較高運算效率，能為求解大規(guī)模的航線網(wǎng)絡(luò)優(yōu)化問題提供一種可行有效的方法.[5]

2 模型建立與求解

2.1 參數(shù)假設(shè)

在集裝箱班輪運輸網(wǎng)絡(luò)優(yōu)化中可以忽略的因素[6]：(1)不考慮時間成本，即不考慮船舶在航行過程中因為時間問題產(chǎn)生的成本；(2)為簡化計算，每一類船舶在規(guī)劃子航線上的航次成本為現(xiàn)有航線上航次成本的平均值；(3)船舶的可變成本指在同一條航線上運輸空集裝箱的費用，在本文中忽略此費用[7]；(4)以現(xiàn)有航線的起始港與目的港之間的需求為主，假設(shè)每個轉(zhuǎn)運港口的貨物裝卸數(shù)量相等，即轉(zhuǎn)運港口達(dá)到貨物運量均衡.

2.2 模型建立

航運聯(lián)盟航線優(yōu)化的目標(biāo)函數(shù)是利潤最大.[8]現(xiàn)將模型[9-10]建立如下：

opt(X(o,d,m))

(1)

?v∈V,?(o,d,m)∈Θ

(2)

X(o,d,m)≤0， ?e∈E,?(o,d,m)∈Θ

(3)

(4)

(5)

(6)

X(o,d,m)=0,1

(7)

式(2)中，經(jīng)過港口v的所有航線組成網(wǎng)格，例如經(jīng)過港口4的航線有1-2-4-6，1-3-4-7，1-4-5，則Inedges(4)={2-4，3-4，1-4}，Outedges(4)={4-6，4-7，4-5}.

該問題主要有6個約束：式(2)表示網(wǎng)絡(luò)中每個轉(zhuǎn)運港的貨物運量平衡，保證每個轉(zhuǎn)運港的裝卸平衡；式(3)為供應(yīng)約束，表示每條航線的貨物運量必須小于所有船舶的總運能；式(4)為需求約束，表示o-d之間的所有規(guī)劃子航線的貨物運量小于o-d之間的貨物需求量；式(5)為船舶數(shù)量約束，即在規(guī)劃子航線(o,d,m)上運營的最多船舶數(shù)量要小于船舶的總數(shù)量；式(6)和(7)是對決策變量的取值范圍的約束.

2.3 列生成算法

2.3.1 算法比較

貪婪算法指先求出一個可行初始解，然后根據(jù)這個可行初始解進(jìn)行最優(yōu)化測度.貪婪算法步驟：第一步，建立數(shù)學(xué)模型描述問題；第二步，把求解問題分為若干個子問題；第三步，對每一個子問題求解，得到子問題的局部最優(yōu)解；第四步，把子問題的局部最優(yōu)解合成原來問題的一個解.從中可以看出該算法需要求解多個局部最優(yōu)解，比枚舉法有一定的優(yōu)勢但仍需大量的計算，不能直接排除不良的局部最優(yōu)解；而列生成算法在這些方面進(jìn)行改進(jìn).因此，選擇列生成算法進(jìn)行求解.

2.3.2 列生成算法

列生成算法在求解大規(guī)模混合整數(shù)規(guī)劃問題上具有突出的優(yōu)勢.考慮到航線優(yōu)化模型規(guī)模非常大，假設(shè)航運網(wǎng)絡(luò)中有7個港口，模型變量即達(dá)到幾十種之多，如果需要求解更大規(guī)模的問題，經(jīng)常會超過軟件規(guī)模限制，因此設(shè)計更精巧的算法是實現(xiàn)模型實用化的關(guān)鍵.列生成算法是數(shù)學(xué)規(guī)劃求解方法中經(jīng)常采用的方法之一，其特點是在需要的時侯生成有價值的變量.采用列生成算法可以有效減小模型規(guī)模、提高運算效率.

列生成算法將原線性規(guī)劃問題分為主問題和子問題.由于主問題變量數(shù)目巨大，選擇部分變量(至少包含一個可行解)作為限制主問題(Restrained Main Problem, RMP).主問題的規(guī)模盡可能小(假設(shè)每個裝貨港到卸貨港之間只由1艘船運送集裝箱)，求解RMP到最優(yōu)，將得到的對偶變量值傳遞給子問題，求解子問題形成具有正簡約成本的列(目標(biāo)函數(shù)為最大)，將正簡約成本最大的列加入RMP中，繼續(xù)求解RMP.重復(fù)上述過程，直到子問題不能產(chǎn)生正簡約成本的列為止，此時原問題達(dá)到最優(yōu)。如果原問題需要求得整數(shù)解，再利用分支定界法進(jìn)行求解.[12]

(8)

(9)

(10)

(11)

將初始X(o,d,m)代入RMP求得決策變量和對偶變量的值.下面構(gòu)造價格子問題.

式(9)的經(jīng)濟(jì)意義為將航運網(wǎng)絡(luò)的成本與運送集裝箱的邊際成本進(jìn)行比較.

(12)

式(12)的經(jīng)濟(jì)意義為對于運輸網(wǎng)絡(luò)上的運輸路徑如果存在3類船舶貨物運輸?shù)倪呺H收益高于目前運輸方案的邊際成本，則該運輸路徑可以改變主問題的目標(biāo)函數(shù)值，因此可以考慮運用式(12)作為列生成算法子問題的依據(jù).利用式(9)對所有的路徑進(jìn)行檢驗，以保證每條路徑的貨物運量都滿足需求約束.最優(yōu)情況即運能等于需求，即不等式取等.綜上考慮，列生成算法的子問題可以表示為

(13)

(14)

(15)

該算法實現(xiàn)步驟如下：

步驟1選擇初始解，根據(jù)選擇初始航線的規(guī)則初步選定航線P0.用k表示當(dāng)前迭代次數(shù)，k=0，構(gòu)建簡化的X(o,d,m)矩陣.

步驟3求解子問題，遍歷搜索所有的路徑.依次檢驗是否滿足式(14).如果滿足式(14)，尋找能夠運輸該o-d虛擬貨物的船舶a∈A，判斷是否滿足式(15)；如果滿足式(15)，則對可能的判斷是否滿足式(13)；如果滿足式(13)則為主問題找到一個新的列變量，否則繼續(xù)搜索下一個可能的組合.如果本組已搜索完畢，則繼續(xù)尋找下一個a；遍歷所有的船舶-o-d后，若能找到新變量，轉(zhuǎn)步驟4；若沒有找到新變量，則主問題已滿足最優(yōu)條件，轉(zhuǎn)步驟5.

步驟5求解恢復(fù)整數(shù)約束的主問題，并報告最終求解結(jié)果.

3 案例分析

結(jié)合第2節(jié)的數(shù)學(xué)模型理論，將這些理論運用到實際案例CKYH聯(lián)盟中，以進(jìn)一步驗證其優(yōu)越性并提出相應(yīng)的經(jīng)營策略.

3.1 已知參數(shù)

3.1.1 航線和港口的選取

選取CKYH聯(lián)盟從亞洲到地中海的4條航線(ABX，AMX，AES3，MD3)進(jìn)行研究[13]，根據(jù)對這4條航線上的各港口每年吞吐量的分析，運用Container Forecaster 11.4Q估算得出2013年CKYH聯(lián)盟在這4條航線上的航次貨物運量，見表1.

表1 CKYH聯(lián)盟在亞洲到地中海的運營航線概況

根據(jù)航線初選的原則，選擇包括這4條航線的起始港和目的港在內(nèi)的7個港口進(jìn)行航線優(yōu)化.這7個港口分別為上海、新加坡、康斯坦丁堡、巴塞羅那、鹿特丹、漢堡和勒阿弗爾.為表達(dá)簡便，設(shè)定這7個港口的代碼依次為1，2，…，7，那么這4條航線對應(yīng)4個o-d對，分別為2-3，1-4，2-6，1-7.

3.1.2 CKYH聯(lián)盟運能概況

由于CKYH聯(lián)盟在2012年5月開始與長榮海運合作遠(yuǎn)東至地中海區(qū)域的航線，統(tǒng)計資料也將長榮納入其中.CKYH聯(lián)盟船隊規(guī)模統(tǒng)計見表2.

表2 CKYH聯(lián)盟船隊規(guī)模分類統(tǒng)計

根據(jù)CKYH聯(lián)盟在亞洲-地中海航線上的貨運量占全球的比例分配船舶，為簡化計算，假設(shè)CKYH聯(lián)盟在亞洲到地中海運營的船舶類型為5 800，3 700，2700 TEU,即T1=5 800 TEU，T2=3 700 TEU，T3=2 700 TEU，對應(yīng)的船舶數(shù)量分別為225，117，110艘，即N1=225艘，N2=117艘，N3=110艘.

CKYH聯(lián)盟在7個港口之間的貨物運價見表3.船舶在運輸?shù)倪^程中肯定會產(chǎn)生一些費用，如船員工資、修理費、港口使費、船舶燃料費等，而且為更新設(shè)備或擴大再生產(chǎn)，還有機器折舊費.為支付這些費用并創(chuàng)造效益，航運公司就要向貨主收取一定的費用(即運費).運費單位價格就是運價，也就是說運價是單位運輸產(chǎn)品價值的貨幣表現(xiàn).[12]

表3 任意兩個港口之間的貨物運價 萬美元/TEU

表4 每條航線的航次固定成本 萬美元/航次

在實際計算中可以把規(guī)劃子航線的航次成本看作是經(jīng)過規(guī)劃子航線的現(xiàn)有航線航次固定成本平均值.每艘船舶在某航線上往返航次成本包括海上航行和港口停靠所產(chǎn)生的直接或間接總費用.

表5 不同船型在每條航線上的單位成本 萬美元/TEU

4 結(jié)果分析

按照第3.3節(jié)所述流程運用CPLEX編程進(jìn)行求解，結(jié)果見表6.

表6 CKYH聯(lián)盟亞洲-地中海航線網(wǎng)絡(luò)優(yōu)化結(jié)果

總利潤為所有規(guī)劃子航線的利潤之和.本文的規(guī)劃子航線有8條(見表6)，計算可得maxz=1 772.93萬美元，聯(lián)盟需要4艘5 800 TEU，11艘3 700 TEU和3艘2 700 TEU的船.

5 結(jié)論與展望

本文根據(jù)列生成算法求得CKYH聯(lián)盟在亞洲到地中海的最佳航運網(wǎng)絡(luò)，使聯(lián)盟利潤達(dá)到最大，可為CKYH聯(lián)盟和其他集裝箱班輪運輸公司提供一定的參考依據(jù).本文得出結(jié)論：(1)集裝箱班輪運輸網(wǎng)絡(luò)中的一些港口之間的貨物運量可以通過調(diào)整航線和運營船舶進(jìn)行交叉運送，初始港與目的港之間的貨物運量可以分為多條路徑和多艘不同類型船舶進(jìn)行運輸，這樣可以節(jié)省成本并減少航次時間和資金浪費.[14](2)列生成算法對于航運網(wǎng)絡(luò)優(yōu)化問題是適用的.當(dāng)混合整數(shù)規(guī)劃模型中存在大量的塊結(jié)構(gòu)并且列數(shù)大于行數(shù)(即決策變量多于約束條件)時可以采用列生成算法；為節(jié)省時間提高效率可以采用啟發(fā)式列生成算法.為算法設(shè)定特定的循環(huán)程序可以更快地求解.

本文僅選取含有7個港口的案例，運用啟發(fā)式列生成算法可以很快求得結(jié)果，但當(dāng)問題規(guī)模變大時該算法是否適用還有待進(jìn)一步研究.另外，本文是對航運聯(lián)盟整體進(jìn)行網(wǎng)絡(luò)優(yōu)化，航運聯(lián)盟要保持穩(wěn)定就必須滿足每個成員的利益并形成一定的機制[15]，所以列生成算法是否也能運用到每個成員的航線優(yōu)化也待進(jìn)一步研究.

參考文獻(xiàn)：

[1] CHRISTIANSEN M, FAGERHOLT K, NYGREEN B,etal. Handbooks in operations research and management science: transportation[J]. Maritime Transportation, 2007, 14: 189-284.

[2] CHUANG T N, LIN C T, KUNG J Y,etal. Planning the route of container ships: a fuzzy genetic approach[J]. Expert Systems with Applications, 2010, 37(4): 2948-2956.

[3] GELAREH S,PISINGER D. Fleet deployment, network design and hub location of liner shipping companies[J].Transportation Res,2011, 47(6): 947-964.

[4] 吳文一. 航運聯(lián)盟下的集裝箱運輸路徑選擇研究[D]. 上海: 上海海事大學(xué), 2004.

[5] AGARWAL R, ERGUN ?. Ship scheduling and network design for cargo routing in liner shipping[J]. Transportation Sci, 2008, 42(2): 175-196.

[6] LU H A. Modelling ship’s routing bounded by the cycle time for marine liner[J]. J Marine Sci & Technol, 2002, 10(1): 61-67.

[7] SHINTANI K, IMAI A, NISHIMURA E,etal. The container shipping network design problem with empty container repositioning[J]. Transportation Res Part E: Logistics & Transportation Rev, 2007, 43(1): 39-59.

[8] 陳繼紅, 真虹, 宗蓓華. 班輪配船模型的改進(jìn)及其在航運聯(lián)盟箱位租用中的應(yīng)用[J]. 交通運輸系統(tǒng)工程與信息, 2008, 8(3): 120-125.

[9] 楊秋平. 船隊規(guī)劃數(shù)學(xué)建模與算法研究[D]. 大連: 大連海事大學(xué), 2010.

[10] 張華歆. 逆向物流的網(wǎng)絡(luò)結(jié)構(gòu)和設(shè)計[D]. 上海: 上海海事大學(xué), 2004.

[11] CHU C W, KUO T C, SHIEH J C. A mixed integer programming model for routing containerships[J]. J Mar Sci Technol, 2003, 11(2): 96-103.

[12] 藍(lán)伯熊, 吳李知. 鐵路客運網(wǎng)絡(luò)列車開行方案優(yōu)化模型的列生成算法研究[J]. 運籌與管理, 2012, 21(1): 1-10.

[13] 任斐. 集裝箱班輪航線靠港選擇模型問題研究[D]. 大連: 大連海事大學(xué), 2007.

[14] CHRISTIANSEN M, FAGERHOLT K, RONEN D. Ship routing and scheduling: status and perspectives[J]. Transportation Sci, 2004, 38(1): 1-18.

[15] 鄭士源. 合作博弈理論的研究進(jìn)展——聯(lián)盟的形成機制以及穩(wěn)定性研究綜述[J].上海海事大學(xué)學(xué)報, 2011, 32(4): 53-59.