吳瓊, 鄭士源, 朱太球

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

0 引 言

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

1 問題提出

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

2 模型建立與求解

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

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

2.2 模型建立

航運(yùn)聯(lián)盟航線優(yōu)化的目標(biāo)函數(shù)是利潤(rùn)最大.[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個(gè)約束：式(2)表示網(wǎng)絡(luò)中每個(gè)轉(zhuǎn)運(yùn)港的貨物運(yùn)量平衡，保證每個(gè)轉(zhuǎn)運(yùn)港的裝卸平衡；式(3)為供應(yīng)約束，表示每條航線的貨物運(yùn)量必須小于所有船舶的總運(yùn)能；式(4)為需求約束，表示o-d之間的所有規(guī)劃子航線的貨物運(yùn)量小于o-d之間的貨物需求量；式(5)為船舶數(shù)量約束，即在規(guī)劃子航線(o,d,m)上運(yùn)營(yíng)的最多船舶數(shù)量要小于船舶的總數(shù)量；式(6)和(7)是對(duì)決策變量的取值范圍的約束.

2.3 列生成算法

2.3.1 算法比較

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

2.3.2 列生成算法

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

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

(8)

(9)

(10)

(11)

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

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

(12)

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

(13)

(14)

(15)

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

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

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

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

3 案例分析

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

3.1 已知參數(shù)

3.1.1 航線和港口的選取

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

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

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

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

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

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

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

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

表3 任意兩個(gè)港口之間的貨物運(yùn)價(jià) 萬美元/TEU

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

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

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

4 結(jié)果分析

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

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

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

5 結(jié)論與展望

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

本文僅選取含有7個(gè)港口的案例，運(yùn)用啟發(fā)式列生成算法可以很快求得結(jié)果，但當(dāng)問題規(guī)模變大時(shí)該算法是否適用還有待進(jìn)一步研究.另外，本文是對(duì)航運(yùn)聯(lián)盟整體進(jìn)行網(wǎng)絡(luò)優(yōu)化，航運(yùn)聯(lián)盟要保持穩(wěn)定就必須滿足每個(gè)成員的利益并形成一定的機(jī)制[15]，所以列生成算法是否也能運(yùn)用到每個(gè)成員的航線優(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] 吳文一. 航運(yùn)聯(lián)盟下的集裝箱運(yù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)及其在航運(yùn)聯(lián)盟箱位租用中的應(yīng)用[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2008, 8(3): 120-125.

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

[10] 張華歆. 逆向物流的網(wǎng)絡(luò)結(jié)構(gòu)和設(shè)計(jì)[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)伯熊, 吳李知. 鐵路客運(yùn)網(wǎng)絡(luò)列車開行方案優(yōu)化模型的列生成算法研究[J]. 運(yùn)籌與管理, 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)盟的形成機(jī)制以及穩(wěn)定性研究綜述[J].上海海事大學(xué)學(xué)報(bào), 2011, 32(4): 53-59.