動態(tài)規(guī)劃的集裝箱多式聯(lián)運系統(tǒng)運輸方式組合優(yōu)化＊

韓 駿 徐 奇 靳志宏

（大連海事大學(xué)交通運輸管理學(xué)院1） 大連 116026） （中國海運（香港）控股有限公司2） 香港 999077）

針對集裝箱多式聯(lián)運方面的研究，Jansen，et al［1］提出了一個基于港口的集裝箱運作計劃的模擬研究；Bérubé，et al［2］提出運用 Dijkstra算法的原理對確定型運輸時間的多式聯(lián)運網(wǎng)絡(luò)求解總成本最小的路徑優(yōu)化問題；蘇印與李鐵柱［3］、謝芳等［4］運用層次分析法對運輸線路進(jìn)行評價；賀竹磬等［5］采用遺傳算法來解決聯(lián)運路徑的選擇問題；靳志宏等［6］分別針對多式聯(lián)運裝卸與運輸一體化問題、集裝箱碼頭集卡調(diào)度優(yōu)化問題、集裝箱多式聯(lián)運系統(tǒng)拼箱集運優(yōu)化問題等進(jìn)行了研究.本文從集裝箱多式聯(lián)運組織者（多式聯(lián)運經(jīng)營人）的角度，構(gòu)筑了多式聯(lián)運運輸方式組合優(yōu)化的數(shù)學(xué)模型，實證研究顯示了該模型與方法的可行性與有效性.可為多式聯(lián)運經(jīng)營人在實際操作中進(jìn)行運輸方式組合的選擇提供決策參考.

1 基于動態(tài)規(guī)劃的運輸方式組合優(yōu)化模型

1.1 建模條件

1.2 參數(shù)說明

N為所有節(jié)點城市的個數(shù)；Mi為在第i個城市可選用的運輸方式集合（“1”表示公路運輸，“2”表示鐵路運輸，“3”表示水路運輸）.

Q為集裝箱多式聯(lián)運中貨物運輸總量；

飛灰主要是由燃煤中不可燃燒的灰份和部分未燃盡的碳粒組成，飛灰顆粒度越細(xì)則說明返料器分離效率越高，燒失量也就越低。經(jīng)過提效改造后，通過建立0.045mm篩分監(jiān)控設(shè)施，測量篩余占比由原26%，下降至12%，燒失量由原13%，下降至8%。

1.3 優(yōu)化模型

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

約束條件

目標(biāo)函數(shù)式（1）表示要求多式聯(lián)運的總運輸成本最小，其中第一部分表示將一批貨物從出發(fā)地送至目的地的總成本，第二部分表示不同運輸方式之間的轉(zhuǎn)換引起的對貨物進(jìn)行換裝所發(fā)生的成本.約束條件式（2）表示貨物從城市i到城市i＋1只能選擇一種運輸工具；式（3）表示貨物在城市i只發(fā)生一次換裝.

約束條件式（4）是確保運輸?shù)倪B續(xù)性.在i城市貨物由第k種運輸方式轉(zhuǎn)換到第l種運輸方式，即從i－1到i選擇l，從i到i＋1選擇k，如圖1所示.

圖1 確保運輸連續(xù)性示意圖

約束條件式（5）、（6）表示貨物在運輸過程中所花費的時間必須在承運人要求的時間范圍［tmin，tmax］之內(nèi)，其中不等式左邊第一部分均表示為貨物的運輸時間，第二部分為運輸方式轉(zhuǎn)換所產(chǎn)生的中轉(zhuǎn)時間；式（7）、（8）表示決策變量為0－1變量.

2 MATLAB的算法與程序設(shè)計

2.1 算法設(shè)計

步驟1 將多式聯(lián)運通道中的節(jié)點城市劃分階段，令每兩個城市之間的運輸過程為動態(tài)規(guī)劃中的一個階段，即n＋1個城市有n個階段.

步驟2 選擇貨物到達(dá)城市的運輸方式為該階段的狀態(tài)變量，如：第2階段的到達(dá)方式有公路、鐵路，則狀態(tài)變量S2可取值的范圍即為1、2，第二階段的可達(dá)狀態(tài)集合S2＝｛1，2｝，同理可確定其他階段的狀態(tài)變量.設(shè)計一個3×n的狀態(tài)矩陣，矩陣的第k列表示第k個階段的狀態(tài)變量構(gòu)造的列向量（該列向量中的第i行元素的值應(yīng)為i，如Sk中不含i，則用MATLAB中特有的常量NaN填充），將所得到的3×n狀態(tài)矩陣作為動態(tài)規(guī)劃程序的一個輸入變量.如一個3階段的問題，各階段的可達(dá)狀態(tài)集合分別為｛1｝，｛1，3｝，｛1，2，3｝，則該問題需輸入的狀態(tài)變量矩陣為

步驟3 確定決策變量和狀態(tài)轉(zhuǎn)移方程.在此例中，令從每一城市出發(fā)時所選擇的運輸方式作為該階段的決策變量uk.狀態(tài)轉(zhuǎn)移方程Sk＋1＝uk，即第k＋1階段的狀態(tài)直接等于第k階段的決策值.

步驟4 刪除不滿足時間強(qiáng)約束的可選擇方案，這也是與在一般情況下運用動態(tài)規(guī)劃求解問題的區(qū)別所在.由于在模型中限定了多式聯(lián)運總時間必須在顧客要求的范圍［tmin，tmax］之內(nèi)，因此在進(jìn)行選擇最優(yōu)方案之前應(yīng)該先排除不滿足時間要求的方案.

步驟5 由邊界條件k＝n開始，求出在該階段狀態(tài)為sk時所有允許決策下的指標(biāo)函數(shù)值，選取其中的最優(yōu)值作為該階段狀態(tài)為sk時的最優(yōu)值，求出最優(yōu)決策（sk）并進(jìn)行替換存儲.以此方法向k＝n－1，n－2，…，1逐步逆推，直到最后求出f1（s1），得到問題的指標(biāo)函數(shù)最優(yōu)值.

步驟6 由k＝1開始，按照與前一步驟相反的順序推算，記錄推算結(jié)果，則可得到每階段及全局的最優(yōu)路徑及最優(yōu)解，存儲結(jié)果并輸出.

2.2 程序設(shè)計

按照上述算法設(shè)計的思路所設(shè)計的解法程序主要由以下子程序組成：（1）主函數(shù)function［p＿opt，fval，tw］＝dyn（x，tm，tn，SubObjFun，TransFun，ObjFun），輸入狀態(tài)變量矩陣和顧客要求的時間約束，輸出的變量為全局最優(yōu)策略組（p＿opt）、最優(yōu)指標(biāo)函數(shù)值（fval）、完成該運輸任務(wù)所需要的時間（tw）；（2）階段指標(biāo)計算子函數(shù)function tmp00＝SubObjFun（ii，x，u），輸入階段數(shù)（ii）、狀態(tài)（x）、決策值（u），輸出的變量為處于該階段時，某一狀態(tài)和決策條件下所需的一階段成本tmp00，供主函數(shù)運行時調(diào)用；（3）狀態(tài)轉(zhuǎn)移計算子函數(shù)function tmp40＝TransFun（ii，x，u），輸入階段數(shù)（ii）、狀態(tài)（x）、決策值（u），返回處于該階段某一狀態(tài)和決策條件時下一階段將處的狀態(tài)值tmp40；（4）第k階段至最后階段指標(biāo)函數(shù)子函數(shù)function tmp80＝ObjFun（tmp00，f＿opt），輸入階段指標(biāo)值（tmp00）和后一階段至最后階段指標(biāo)值（f＿opt），輸出值為該階段至最后階段指標(biāo)值.

3 實證研究

將上述模型與算法應(yīng)用于上海－成都間多式聯(lián)運運輸方式組合的選擇中進(jìn)行實證研究［7－8］.依現(xiàn)狀，上海－成都間多式聯(lián)運通道的主要節(jié)點城市為南京與鄭州.現(xiàn)有一個貨主需要將2個TEU的集裝箱從成都運往上海，運輸路線為成都－鄭州－南京－上海，要求在貨物起運后25～30h之內(nèi)到達(dá)目的地.具體數(shù)據(jù)見表1、表2及表3.

表1 集裝箱多式聯(lián)運各種運輸方式中轉(zhuǎn)距離表（成都－上海）

表2 集裝箱多式聯(lián)運各種運輸方式的運載工具速度表

表3 集裝箱多式聯(lián)運各種運輸方式中轉(zhuǎn)時間表

對表1與2處理即可得出城市之間各種運輸方式的運輸時間，表3數(shù)據(jù)即為不同運輸方式之間的中轉(zhuǎn)時間.

集裝箱運輸成本根據(jù)所選擇的運輸工具的不同而不同，公路運輸采用高速公路的運輸數(shù)據(jù)，水路運輸采用集裝箱運輸專用船，鐵路運輸采用集裝箱運輸列車.各種運輸方式的集裝箱運輸成本計算如下［10］.

1）公路運輸?shù)募b箱車運輸成本

2）鐵路運輸?shù)募b箱運輸列車運輸成本

3）水路運輸?shù)募b箱船運輸成本 港口i和j之間的總運輸成本Cij，t的構(gòu)成如下.

式中：Cij，f為港口i和j之間的燃料費用；dyij為港口i和j之間的航運天數(shù)；pf（i）為港口i的港使費；Cij，o，Cij，c，Cij，m分別為港口i和j 之間船舶的運行費用、資本費用和管理費用為t型號集裝箱船的設(shè)計裝載量；為構(gòu)成港口i和j之間的使用t型號集裝箱船的實載率；為船舶的航行速度；vrij為構(gòu)成港口i和j之間的可變費用.

則可得出單位距離單箱運輸成本為

式中：α1的取值如表4所列；α2主要為裝卸、空箱以及準(zhǔn)備、維修和保險費用，與船型無關(guān)，一般α2＝591美元；α3為港口收費，根據(jù)港口以及船型的不同，收費標(biāo)準(zhǔn)也不同，本例中所采用的集裝箱運輸船運載量為3 000TEU，港口收費為84 033美元.

通過上述關(guān)于集裝箱運輸成本的計算，計算出此例中各城市之間的運輸成本，如表5所列.

表4 各船型α1的取值

表5 集裝箱多式聯(lián)運各種運輸方式的成本情況表美元／（km·TEU）

將上述參數(shù)輸入到優(yōu)化算法程序中，得到最優(yōu)的運輸方式組合策略為：成都－（公路）－鄭州－（公路）－南京－（鐵路）－上海.此時的最小運輸成本為39 631美元，完成運輸任務(wù)所需要的時間為29.11h.

如果對運輸時間的要求放寬至起運后40～50h之內(nèi)到達(dá)即可，此時再次對該問題求解，得到的最優(yōu)策略組合變?yōu)椋撼啥迹ㄨF路）－鄭州－（鐵路）－南京－（水路）－上海.此時的最小運輸成本為15 826美元，完成運輸任務(wù)所需要的時間為46.96h.

4 結(jié) 束 語

本文對集裝箱多式聯(lián)運系統(tǒng)中各個階段的多種運輸方式的組合優(yōu)化問題建立了以總運輸費用最小為目標(biāo)函數(shù)的優(yōu)化模型，并基于現(xiàn)實問題對其設(shè)定了時間約束，采用動態(tài)規(guī)劃的基本思想對其求解.通過MATLAB上機(jī)編程實現(xiàn)對該問題的求解，提供了通用的計算程序，獲取了最優(yōu)的運輸方式組合策略.并通過成都－上海間多式聯(lián)運各路段的運輸方式組合優(yōu)化的實證研究，顯示了該模型與方法的可行性與有效性.今后的研究將致力于進(jìn)一步完善模型的現(xiàn)實約束，并嘗試采用模擬仿真技術(shù)使多式聯(lián)運各種運輸方式的組合優(yōu)化決策問題可視化.

［1］Swinkels J，F(xiàn)leuren T.Operational planning of a large－scale multi－modal transportation system［J］.European Journal of Operational Research，2004，156（1）：41－53.

［2］BérubéJ，Potvin J，Vaucher J.Time－dependent shortest paths through fixed sequence of nodes：application to a travel planning problem［J］.Computers and Operations Research，2006，33：1838－1856.

［3］蘇 印，李鐵柱.國際多式聯(lián)運線路選擇的方法研究［J］.交通運輸系統(tǒng)工程與信息，2006，6（2）：91－94.

［4］謝 芳，張 楠，紀(jì)壽文.基于AHP的多式聯(lián)運路徑選擇［J］.物流科技，2006，29（31）：13－17.

［5］賀竹磬，孫林巖，李曉宏.時效性物流聯(lián)運方式選擇模型及其算法［J］.管理科學(xué)，2007，20（1）：8－12.

［6］靳志宏，樸惠淑，楊華龍.集裝箱多式聯(lián)運系統(tǒng)裝卸與運輸一體化優(yōu)化問題［J］.系統(tǒng)工程，2005，23（11）：1－7.

［7］曾慶成，楊忠振，靳志宏.集裝箱碼頭集卡調(diào)度優(yōu)化模型與算法［J］.系統(tǒng)工程，2006，24（增刊）：187－190.

［8］郭子堅，王 諾，霍 紅.多種運輸模式下國內(nèi)沿海集裝箱港口布局模型研究［J］.大連理工大學(xué)學(xué)報，2001，41（5）：598－601.