1、長江水道集裝箱運輸航線網絡優化摘要: 基于長江水道各航段的適航特征和沿岸港口間OD集裝箱運輸需求，構建整數規劃模型，以所有集裝箱運輸總成本最小為目標，優化長江水道上集裝箱航線網絡，確定各航線靠港、靠泊順序及所用船舶的類型與數量。優化時，首先確定適合長江航道的主要船型，其次，結合各段航道適航特征，針對可使用的各種船型，設定各航段的通行阻抗函數； 然后，設計基于 Frank-Wolf 法的遺傳算法進行求解。優化得到的集裝箱航線網絡呈現“大船在中間，小船在兩邊”的形態，與目前遵循的“小船走上游，大船走中下游”的船舶配置原則有所不同。1.引言長江是我國內河運輸的“黃金通道”，是中西部地區與世界實現經濟

2、交流的動脈，同時也是東西部經濟互補的橋梁。長江水系集裝箱運輸自1976年以來經歷了試驗、起步和發展三個階段，目前航線已由單一的內貿航線發展到國際航線、內支線、國內航線，集裝箱箱型由 5t箱變為20英尺和40英尺國際標準箱，運輸方式由頂推船隊為主發展到以自航船為主。2002年，長江水系集裝箱吞吐量為138萬TEU，主要港口集裝箱吞吐量為126萬TEU。集裝箱運輸已成為長江貨物運輸的新經濟增長點。目前，大約有20個航運公司主要從事集裝箱內河運輸，比如，中遠集裝箱運輸公司，中海集裝箱運輸公司、中外運集裝箱運輸公司、上海港口航運和駁船運輸公司，上海浦海航運有限公司和民生航運公司。在長江水系有100多條

3、集裝箱航線，包括長江干線港口間、長江港口至沿海港口的國內航線以及開往鄰近國家和地區的近洋航線，及其長江三角洲地區的無錫上海、常州上海、杭州上海、嘉興上海、湖州上海的集裝箱航線。由長江干線航道發展規劃可知，上起云南水富港、下至上海長江口的長江航道將得到加深。水富至宜賓河段，將由1.8m加深至2.7m，全年可通航由 1000t級駁船組成的船隊；城陵磯至武漢，加深至3.7m，可通航由3500t駁船組成的萬噸級船隊; 武漢至銅陵河段，通航由200050000t 級駁船組成的24萬t級船隊，可通航5000t級海船；銅陵至南京，加深至6m，可通航500010000t級海輪; 南京以下航道加深至12m以上，

4、可通航5萬t級以上海輪；瀏河口至長江口河段可通航第五代以上超大型集裝箱船。上述長江主要通道如圖1所示。圖1 長江主要通道眾所周知，長江上各港口間適航船舶的差異為沿長江設置多種集裝箱航線，構建沿江的集裝箱水運網絡提供了條件。根據交通需求和水道的條件，運營商可以設置幾個集裝箱運輸方案。運營者可以結合需求和航道情況，用適用性強的小型船舶實施點對點運輸；或在中下游用大型船舶，在中上游用小型船舶，實施干支線分離運輸。各種航線網絡效率和效益隨需求和航道變化而異，所以有必要針對長江航道進行集裝箱運輸航線網絡設計。2.文獻綜述有關水上航線設計的研究很多，但相關研究主要集中在海運領域，早期的代表性研究均為海運船

5、隊規劃問題。隨著班輪業的發展，航線所涉及的港口不斷增加，航線結構逐漸成為決定運營成本的關鍵。因此，研究者在船隊規劃的同時，開始關注船舶定線問題。ana等用整數規劃模型同時優化船隊規模和班輪路線；文獻以航線收益最大為目標，用集合劃分模型優化船隊規劃和船舶定線Agarwal等總結了班輪船舶調度、航線設計和船隊規劃等問題，并基于時空網絡建立混合整數規劃模型。另外，部分學者還研究了班輪航線優化與倉儲、空箱調運、時間約束、運輸需求季節性波動等的相互影響。Hsu等從承運人的角度，以最小運輸成本和庫存成本之和為目標，建立雙目標模型優化班輪航線、船隊規模、發班頻率。Shintani等建立雙層模型，同時處理航線

6、優化和空箱調度問題。Matthew等在有時間約束的條件下，設計集裝箱軸輻式航線網絡。Meng等研究了單一集裝箱班輪公司在運輸需求不確定時的短期班輪船隊規劃問題。只有少數學者針對各自國家的內河集裝箱運輸進行研究，且多是關于船型選擇、船型標準化、內河運輸與海港銜接等的研究。劉建峰等針對早期長江水道的航行條件，從經濟性上研究上游港口實施江海直達運輸時，近洋航線(到日本神戶、橫濱等港口)的最佳船型。在不考慮航線網絡和OD運輸量的情況下，通過裝載率不同所導致的單箱運輸成本變化來確定合理的船型。 賈瑞華等研究在長江上游運輸集裝箱時，水運方式與陸運方式的優劣，基于 AHP法構建評價體系，在宏觀層面上分析運輸

7、經濟性。該研究不涉及航道和航線等微觀層面細節，只研究陸路通道和水路通道的經濟性。 羅洪波等詳細分析長江通航情況，為重慶至洋山港間運輸設置了五種方案：直達、蘆潮中轉、武漢中轉、南京中轉、外高橋中轉，并用評價標準進行測試。該研究的缺點是沒有考慮貨流量和沿線其他港口的貨物。 與之類似，鐘華杰等研究了重慶、武漢、長沙、南京、張家港等地至洋山的集裝箱運輸方案，預先設定了 18 種可能的航線方案，然后確定各港口到洋山港的最佳運輸方案。這些研究的特點是不考慮港口間集裝箱流量，假設每種船型對應一個單箱運輸成本，然后確定運輸方案。上述研究的共同特點是，他們都沒有考慮集裝箱港口之間的OD貨流，并認為一種類型的船都

8、有一個特定單位集裝箱運輸成本，然后評估其他港口到洋山港班輪方案。Taylor等研究了美國俄亥俄河的駁船與動力船的指派問題，作者給出了一個基于仿真的調度系統，用以輔助決策駁船指派和動力船分配問題。Jonkeren等研究了氣候所導致的萊茵河水位變化對航運成本的影響，以及最終引起的水運份額的變化。他們利用NODUS軟件分析貨物在一個范圍廣泛的綜合運輸網絡中的路徑選擇問題，關注低水位對水運分擔率的影響，用宏觀網絡規劃軟件研究OD貨流在虛擬化的綜合運輸網絡上的路徑選擇問題，而非設計內河航運的運輸網絡。總之，內河集裝箱運輸的相關研究很少涉及航線網絡優化與航線配船，僅有的一些研究不適用于各航段通航條件不同、

9、水文狀況復雜的內陸河道運輸系統。因此，本文針對長江水道提出考慮航道水深限制和貨主運輸路徑選擇行為的集裝箱運輸航線網絡優化與船隊配置模型(COM)，以航線運營總成本最小為目標，確定各航線的靠泊港口、靠泊順序、船型與船舶數量。為求解模型，基于Frank-Wolf原理設計遺傳算法( GA)。本文的組織結構如下：第三節介紹了問題描述和提出了一些建立模型時應該處理的關鍵問題。第四部分描述了路網規劃和航線配船模型(NFDM)。第五節設計了相應算法。第六節舉例說明了計算結果。最后, 第七節為研究總結。3.問題描述3.1航線方案的表述方法為了設置航線配船模型，用數學方法來描述班輪航線計劃和由路線方案組成的運輸

10、路網應該被創建，該方法應該從各方面來考慮內河上所有班輪航線的結構特點。在海洋運輸中，班輪航線可拆分為去程子航線和回程子航線，因此確定海上班輪航線就是確定去程子航線和回程子航線的靠泊港口和靠泊順序。但是，長江航道結構單一，沒有可替代路徑，各港口沿水道順序排列，去程子航線由上游至下游順序靠泊，回程子航線由下游至上游順序靠泊。因此優化長江上的班輪航線時，只確定各子航線的靠泊港即可。假設圖2顯示了長江沿岸港口的位置，從上游到下游，第一個港口是港口1和最后一個港口是港口N。設某航線的去程子航線為：港2港3港l港 N，回程航線為：港N 港N 1港l 港2，由此可確定一個如圖 3 所示的航線。圖2 港口分布

11、示意圖圖3 航線組成由圖3可知，若某港為掛靠港，則其在航線中的角色可能是：（1）去程子航線的起始港（如港2）；或（2）去程子航線的中途靠泊港（如港3）；或（3）回程子航線的中途靠泊港（如港 N 1）；或（4）去程和回程子航線均掛靠的中途港（如港 l）；或（5）回程子航線的起始港（如港 N）。因此，可以用 0 1 變量 xitk來表述港口在航線中的角色，其中i為港口編號，t1，5為港口角色編號，k1，K為航線編號，K為預先設定的航線數量。若航線k掛靠i港，而i港在航線k中的角色為t，則xitk= 1，否則為0。另外，用 xi0k表示港口i是否被航線k掛靠，若是則xi0k= 1，否則為0。變量 x

12、itk與xi0k之間的關系為： （1）式（1）用于確保若港口i是掛靠港時，港口i在航線中只扮演一種角色； 而若港口i不是掛靠港時，xitk的取值則為0。 （2） （3）式（2） 、（3） 表明在一個航線中去程子航線和回程子航線都有且只有一個起始港。 （4） （5）式（4） 表明，航線中角色 1 的港口的上游不可能有角色 5 的港口。同樣，式（5） 表明角色 5 的港口的下游不可能有角色 1 的港口。 （6） （7）式（6）表明，航線中角色1的港口的上游不可能有掛靠港。而式（7）表明角色5 的港口的下游不可能有掛靠港。給定一組滿足約束條件的 xi1k與xi0k便可確定一個航線方案。例如，若 x2

13、0k= x30k=xi'0k= x（N-1）0k= xN0k= 1，而其他 xi0k= 0，則航線k的靠泊港口為2、3、l、N 1、N；同時，若 x21k= x32k= xl4k= x（N-1）2k= xN5k= 1，而其他 xitk= 0，則港口 1 與港口 N 分別為去程子航線與回程子航線的起始港，港口 2 為去程子航線的中途靠泊港，港口l為去程與回程子航線均掛靠的中途港，而港口N 1 僅是回程子航線的掛靠港。這里設 X =( xitk，t 0，5，i M，k 1，K)，zijk表示航線k中是否有港口 i 至港口j的航段。zijk與X的關系可表示如下： （8） （9） （10）式（

14、8）表示航線k的去程子航線的航段，式（9）表示回程子航線的航段。如果用A（X）= ( i，j)k| zijk= 1，i，j 1，K ，其中( i，j)k為網絡中航線k的港口i至港口j的有向航段。例如，在圖 3 所示的由兩條航線構成的網絡中，( 1，3)1表示航線 k = 1 由港口1 至港口3 的有向航段，( 2，3)2表示航線 k = 2 由港口 2 至港口 3的有向航段。至此，得到表示靠泊港口選擇、靠泊順序等航線結構的數學表述方法。圖4 航線網絡的描述方法3.2. 集裝箱貨流分配根據上述描述方法，所有的航線都可以用數學結構來表達。然而，要評價航線的優劣，需要估算集裝箱在航線網絡上的分布情況

15、。在水路運輸網絡中，托運人通常會選擇綜合運輸成本(運輸時間與費用的加權和)最低的運輸路徑運輸貨物，其行為符合UE原理，因此可以用UE分配模型計算各水路路段的集裝箱流量。此時，求解UE模型的關鍵是設定路段的阻抗函數。借鑒Meng等的研究給出如下阻抗函數： （11）其中: c0( i，j)k、t0( i，j)k、s( i，j)k分別為路段 (i，j)k的運價、自由流時間與流量; h1k、feqk分別為k航線上船舶的運力與班期密度；FEQ = feqk| k 1，K ；為時間價值；1、2、3為待定參數。基于上述阻抗函數，來計算用戶平衡狀態下，各路段的集裝箱流量，可以用變分不等式：for any （1

16、2） 其中，（X）為路段上集裝箱流量的集合。4.優化模型4.1.假設條件除前面假設外再增加假設：（1）一個班輪航線僅用一種船型；（2）船舶在各港口的在港時間相同；（3）必要時集裝箱可在不同班輪航線之間轉運；（4）同一航線的平均航速相同；（5）決策周期為7天。4.2.模型結構基于上述分析和假設，構建整數規劃模型，其解析表達式如下： （13）式（13）為最小化水運網絡的總運輸成本。其中：cgk為航線k的運營成本; cfk為航線k的燃油成本。約束條件除包括式（1）（12）外，還包括： （14）式（14）用于計算航線 k 的全程航行時間。其中：Disij為港i至港j的航行距離；vk為航線k的平均航速；

17、tp為船舶在港停泊時間。 （15） （16） （17）式（15）用于計算航線k所需的船舶數量h2k，其中，feqk為航線k的班期密度。式（16）用于計算cgk，其中，h3k為航線k上船舶日租金。式（16）用于計算 cfk，其中，h4k為航線k上船舶的日燃油消耗。 （18）式（18）為航道水深約束，其中，SLij為港口i至港口j航段水深。 （19） （20） （21） （22）式（19）、（20）給出路段集裝箱量與港口間OD 量間的關系。其中: O 為起運港集合；D為目的港集合；qrs為由港rO至sN的OD量；非負實數frsp表示水路網絡中連接OD對 r s 的路徑p上的流量；rs( i，j)k

18、，p為0 1 變量，當 OD 對 r s 間的路徑 p 經過路段( i，j)k時取1，否則為0。式（20）確保所有貨運需求均獲得充足的運力。式（22） 用于保證各航線班期密度至少為每周 1 班。5.模型的解決方案5.1.算法設計上述模型是一個帶有平衡約束的整數規劃問題，加之要考慮航線結構、港口選擇以及航道水深限制等，因此難以精確求解。為此設計一種嵌入Frank-Wolf 法的遺傳算法( FWGA) 。運行步驟如下:步驟1 (初始化)令 n = 0，生成初始種群 Pn= ( X，FEQ)v|v = 1，；其中，( X，FEQ)v表示遺傳算法的一個個體，包含兩部分：航線結構信息 X 與航線班期頻率

19、 FEQ；為種群規模；步驟2 (計算個體的適應度值)步驟2.1根據已知的(X，FEQ)v構建水運網絡Gv;步驟2.2采用 Frank-Wolf 法計算網絡Gv的用戶平衡狀態，獲得各路段的集裝箱流量：sv=( s( i，j)k，( i，j)k A( X) )；步驟2.3計算個體 v 的適應度值：其中: fitv為個體 v 的適應度值；M 為一個足夠大的正數；max（.）為取大函數。步驟3(判斷算法是否收斂)檢查當前種群的適應度最大值與平均值的差是否小于預設的，是則執行步驟 4，否則終止算法；步驟4( 執行選擇、交叉和變異操作)令n = n + 1，實施交叉、變異和選擇操作，獲得新個體Pn，然后回

20、到步驟 1。5.2編碼方法編碼由若干子編碼構成，子編碼個數取決于預先設定的航線數K。圖5為一個K = 2 時的隨機編碼，由子編碼k = 1和子編碼 k = 2 組成。其中，每個子編碼均由5部分構成。如圖6所示。Part 1表示靠泊港口，同時確定去 / 回程子航線的起始港。例如，0 1 1 1 1 表示去程子航線的起始港為港 2，回程子航線的起始港為港 5，該航線還掛靠港口 3 與港口 4。基于Part 1 確定靠泊港口與起始港后，便可根據 Part 2 Part 4 來確定各掛靠港在航線中的角色。具體地: 若港口 i 被選為靠泊港，且不是起始港，則 Part 2 的第 i 號基因的作用便是判斷

21、該港是否是僅隸屬于去程子航線的港口，若是則 Part 2 的第 i 號基因位的值為 1，否者為0。例如，在圖6中靠泊港3既不是去程子航線的起始港也不是回程子航線的起始港，且Part2的第3基因位的值為1，由此可知港口 3 僅隸屬于去程子航線。Part 3 與 Part 4 分別用于確定僅隸屬于單程子航線和同時隸屬于兩個子航程的港口，其判定方法與 Part2相同。圖5 編碼方法圖6 子編碼構成Part5用于確定航線方案k的班期頻率，是二進制編碼，位數等于預先設定的備選班期頻率 若備選班期頻率為每周 1、2、3、4 班，Part 5 便是一個2 位的二進制數，Part 5 =(0 0) 對應每周

22、1 班；Part5 = (0 1) 對應每周 2 班; Part 5 = (1 1) 對應每周 3班; Part 5 = (1 0) 對應每周 4 班。這種編碼方法可方便地表示任何一個航線方案與班期頻率的組合( X，FEQ)v 例如，根據子編碼 k = 1 可得到圖 7a 所示的航線 a，根據子編碼 k = 2 可得到圖 7b 所示的航線 b，兩者組合可表述圖 7c 所示的航線網絡c。圖7 子航線的組合圖8 長江流域港口位置6.數值分析61 數據收集選擇長江沿線港口中集裝箱 OD 量較大的 10個港口，從上游至下游依次為: 瀘州( LZ) 、重慶(CQ) 、荊州(JZ) 、城陵磯(CLJ) 、

23、武漢(WH) 、九江( JJ) 、南京( NJ) 、張家港(ZKG) 、南通(NT) 、上海(SH) 圖8顯示了長江流域港口間的位置。表 1 為港口間 OD 集裝箱流量，各港間運價取自實際公布的運價表。各港口間在枯水期和豐水期可通行的最大船舶噸位如表 2 所示。考慮到長江上、中、下游航段差異，這里選取最具代表性的三種船型: 1000MT、3000MT 和5000MT。表 3 為三種船舶的燃油消耗量、運行速度、滿載吃水、日租金和燃油成本。 參考長江集裝箱班輪航線的現狀特征，假定優化的航線網絡由三條航線構成，其中每條航線上只使用一種船型。另外假設班輪頻率為每周 1 班 每周 8 班。6.2 計算方

24、法設初始種群由100個個體構成，個體編碼包括3個子編碼，其中子編碼的Part 1 Part 4擁有10個基因位(備選港口有10個) ，Part 5 擁有3個基因位(航班頻率有8種可能)。最大迭代次數為 200，交叉率設定為 0.92，變異率為 0.01。算法終止條件為最大適應度與平均適應度間的差0.002。表1 集裝箱港口之間的OD流(TEU /周)表2 港口集裝箱吞吐量的運輸價格(20TUE/人民幣)表3 船舶相關數據表4 枯水期港口之間航道的通航船舶(ton)表5 豐水期港口之間航道的通航船舶(ton)圖9 枯水期收斂情況采用 C + + 語言編寫求解程序，并在Duo Core 2 53

25、計算機上運行，分別就枯水期和豐水期，針對不同船型進行計算。數據在表3 - 5用于不同的船舶類型。圖9和圖10為計算收斂情況。6.3結果分析表6和表7分別為枯水期與豐水期的航線網絡。圖 11、12分別為枯水期、豐水期航線覆蓋區域。枯水期航線網絡的最低運營成本為5658 346 元/周，豐水期最低運營成本為3833 551 元/周。實際上，目前班輪公司一直遵循著“小船走上游，大船走中下游”的原則。但是，實驗結果表明，不論是枯水期還是豐水期，航線網絡均呈現“大船在中間，小船在兩邊”的形態。這是因為下游水道的航程長，如果在中下游同時用大型船舶，為保班期(每周至少1班) 就必須增加大型船舶的數量，結果導

26、致運營成本增加和運力浪費。圖10 汛期收斂情況表6 旱期班輪航線網絡結構表7 汛期班輪航線網絡結構因此，合理的方案是在下游航段使用中型船舶，而非大型船舶。這樣做既能滿足運輸的要求，又能提高船舶利用率，降低航線的運營成本。因此,在這種情況下，當與陸路運輸相比航道可能比較強。因為水運輸成本減少，同時由于在相同的碼頭邊船只之間轉船運輸時間可能很難改變。此外，計算結果進一步表明,該運作模式為“大船在中間，小船在兩邊”，并非嚴格按照上游、中游和下游的邊界。如圖11和圖12所示，由于在枯水期5000MT型船只在中游航行的路線會變短。而且，1000MT 型船舶的運營區域相應減小。結果表明，在枯水期，使用14

27、艘小型船只，而在豐水期只使用8艘小型船只。因此，在枯水期的運輸成本更大。圖11在枯水期的運輸路線圖12在豐水期的運輸路線7.結論本文探討了長江水道集裝箱班輪航線網絡設計與船隊配置問題，開發了基于 UE 原理的優化模型，并設計啟發算法。與傳統的在通航能力大的流域使用大型船的做法不同，本文計算結果顯示，應該在長江中游使用大型船，在下游使用中型船，在上游使用小型船。通過這樣做，可以滿足集裝箱運輸的需求以及操作總成本最小化。在沿河的港口之間基于完整的OD矩陣得到上述結果。它表明,當一個操作員根據計劃做運輸業務，運輸成本可以大大降低。同時，操作員可以優化船舶的航行時間，減少轉運時間。隨著所節約成本的增大

28、和時間增量的減少，航道的競爭力變得更強壯從陸運模式去吸引更多的集裝箱。結果，長江沿岸地區的交通可能變得更加環保。參考文獻1Agarwal, R., and Ö. Ergun. 2008. “Ship Scheduling and Network Design for Cargo Routing in Liner Shipping.” Transportation Science 42 (2): 175196.2Cho, S.-C., and A. N. Perakis. 1996. “Optimal Liner Fleet Routeing Strategies.” Maritime

29、 Policy and Management 23 (3): 249259.3Claessens, E. M. 1987. “Optimization Procedures in Maritime Fleet Management.” Maritime Policy and Management 14 (1): 2748.5Fagerholt, K. 1999. “Optimal Fleet Design in a Ship Routing Problem.” International Transactions in Operational Research 6 (5): 453464.6H

30、su, C., and Y. Hsieh. 2007. “Routing, Ship Size, and Sailing Frequency Decision-Making for a Maritime Hub-and-Spoke Container Network.” Mathematical and Computer Modelling 45 (7):899916.7Jaramillo, D. I., and A. N. Perakis. 1991. “Fleet Deployment Optimization for Liner Shipping Part 2. Implementati

31、on and Results.” Maritime Policy and Management 18 (4): 235262.8Jia, R. H., Y. Zhang, and B. Yang. 2006. “Project Optimization of Container Transport for the Upper Reach of the Yangtze River.” Journal of Waterway and Harbor 27 (2): 127130.9Jonkeren, O., B. Jourquin, and P. Rietveld. 2011. “Modal-Spl

32、it Effects of Climate Change: The Effect of Low Water Levels on the Competitive Position of Inland Waterway Transport in the River Rhine Area.” Transportation Research Part A: Policy and Practice 45 (10): 10071019.10Karlaftis, M. G., K. Kepaptsoglou, and E. Sambracos. 2009. “Containership Routing wi

33、th Time Deadlines and Simultaneous Deliveries and Pick-Ups.” Transportation Research Part E:Logistics and Transportation Review 45 (1): 210221.11Lane, D. E., T. D. Heaver, and D. Uyeno.1987. “Planning and Scheduling for Efficiency in Liner Shipping.” Maritime Policy and Management 14 (2): 109125.12L

34、iu, J., and S. Qin. 1994. “Analysis of Container Ship Types and Transportation from the Yangtze River to Abroad.” Journal of East China Shipbuilding Institute 8 (4): 2129.13Luo, H. B., and J. Y. Sun. 2006. “Study on Container Transportation Modes from Chongqing to Shanghai.” Research on Waterborne T

35、ransportation 2: 1822.14Meng, Q., and S. Wang. 2011a. “Liner Shipping Service Network Design with Empty Container Repositioning.” Transportation Research Part E: Logistics and Transportation Review 47 (5):695708.15Meng, Q., and X. Wang. 2011b. “Intermodal Hub-and-Spoke Network Design: Incorporating

36、Multiple Stakeholders and Multi-Type Containers.” Transportation Research Part B:Methodological 45 (4): 724742.16Perakis, A. N., and D. I. Jaramillo. 1991. “Fleet Deployment Optimization for Liner Shipping Part 1.Background, Problem Formulation and Solution Approaches.” Maritime Policy and Managemen

37、t 18 (3): 183200.17Powell, B. J., and A. N. Perkins. 1997. “Fleet Deployment Optimization for Liner Shipping: An Integer Programming Model.” Maritime Policy and Management 24 (2):183192.18Rana, K., and R. G. Vickson. 1988. “A Model and Solution Algorithm for Optimal Routing of a Time-Chartered Containership.” Transportation Science 22 (2): 8395.19Rana, K., and R. G. Vickson. 1991. “Routing