基于列生成算法的集裝箱班輪運輸網絡優化

吳瓊, 鄭士源, 朱太球

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

0 引 言

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

1 問題提出

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

2 模型建立與求解

2.1 參數假設

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

2.2 模型建立

航運聯盟航線優化的目標函數是利潤最大.[8]現將模型[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)中，經過港口v的所有航線組成網格，例如經過港口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)表示網絡中每個轉運港的貨物運量平衡，保證每個轉運港的裝卸平衡；式(3)為供應約束，表示每條航線的貨物運量必須小于所有船舶的總運能；式(4)為需求約束，表示o-d之間的所有規劃子航線的貨物運量小于o-d之間的貨物需求量；式(5)為船舶數量約束，即在規劃子航線(o,d,m)上運營的最多船舶數量要小于船舶的總數量；式(6)和(7)是對決策變量的取值范圍的約束.

2.3 列生成算法

2.3.1 算法比較

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

2.3.2 列生成算法

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

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

(8)

(9)

(10)

(11)

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

式(9)的經濟意義為將航運網絡的成本與運送集裝箱的邊際成本進行比較.

(12)

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

(13)

(14)

(15)

該算法實現步驟如下：

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

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

步驟5求解恢復整數約束的主問題，并報告最終求解結果.

3 案例分析

結合第2節的數學模型理論，將這些理論運用到實際案例CKYH聯盟中，以進一步驗證其優越性并提出相應的經營策略.

3.1 已知參數

3.1.1 航線和港口的選取

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

表1 CKYH聯盟在亞洲到地中海的運營航線概況

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

3.1.2 CKYH聯盟運能概況

由于CKYH聯盟在2012年5月開始與長榮海運合作遠東至地中海區域的航線，統計資料也將長榮納入其中.CKYH聯盟船隊規模統計見表2.

表2 CKYH聯盟船隊規模分類統計

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

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

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

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

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

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

4 結果分析

按照第3.3節所述流程運用CPLEX編程進行求解，結果見表6.

表6 CKYH聯盟亞洲-地中海航線網絡優化結果

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

5 結論與展望

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

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

參考文獻：

[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] 吳文一. 航運聯盟下的集裝箱運輸路徑選擇研究[D]. 上海: 上海海事大學, 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]. 交通運輸系統工程與信息, 2008, 8(3): 120-125.

[9] 楊秋平. 船隊規劃數學建模與算法研究[D]. 大連: 大連海事大學, 2010.

[10] 張華歆. 逆向物流的網絡結構和設計[D]. 上海: 上海海事大學, 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] 藍伯熊, 吳李知. 鐵路客運網絡列車開行方案優化模型的列生成算法研究[J]. 運籌與管理, 2012, 21(1): 1-10.

[13] 任斐. 集裝箱班輪航線靠港選擇模型問題研究[D]. 大連: 大連海事大學, 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].上海海事大學學報, 2011, 32(4): 53-59.