面向隨機因素的多式聯運動態路徑優化

陳丹丹，洪 衛，賈 禹

(重慶交通大學 管理學院，重慶 400074)

?

面向隨機因素的多式聯運動態路徑優化

陳丹丹，洪 衛，賈 禹

(重慶交通大學 管理學院，重慶 400074)

針對隨機因素影響下多式聯運所表現的動態性和隨機性，在引入懲罰因子控制運輸質量的基礎上，以總費用最小化為目標，建立了具有軟時間窗約束的動態路徑優化模型；運用基于Dijkstra算法的改進路徑優化算法求解模型；設計了一個基于鐵路、公路、航空及水運等4種運輸方式的多式聯運問題的算例，驗證了模型的實用性和有效性。

交通運輸工程；多式聯運；隨機因素；動態路徑優化；改進的Dijkstra算法

0 引 言

隨著我國經濟的迅猛發展，單一的貨物運輸方式已不能滿足市場需求，人們越來越重視多式聯運技術在國際貨物運輸領域的應用。與傳統的運輸方式相比多式聯運具有高效、靈活、成本低、環保等特點，可降低運輸成本，提高運輸資源利用率以及企業競爭力。多式聯運動態路徑優化問題是目前多式聯運技術研究的核心內容，具有十分重要的研究意義。

多式聯運路徑優化的研究中，V.R.Reddy，等[1]認為運輸總費用由城市內中轉費用和城市間運輸費用組成，建立總費用最小的線性規劃模型優化路徑。A.Ziliaskopoulos，等[2]考慮多式聯運過程中的時間因素，以運輸時間最短前提建立模型求解。B.S.Boardman，等[3]以運輸時間最短和成本最小為優化目標，進行路徑優化。Tsung-sheng Chang[4]采用基于時間窗的多目標商品流模型解決多式聯運路徑選擇問題，為多式聯運路徑優化中普遍關心的問題提供一種求解方法。魏航，等[5-6]考慮時變網絡下多式聯運的最短路徑問題研究，采用標號法求解最短路問題。這些研究大多面向硬性的約束因素，以成本最小或運輸時間最短為目標進行多式聯運靜態的路徑優化。但是實際多式聯運過程中易受交通、天氣、機械故障等隨機因素的影響，對運輸過程中的運輸時間，運輸費用和運輸質量也有較大影響。肖天國，等[7]結合運輸時間與運輸成本兩個因素建立模型，并運用遺傳算法求解聯合運輸路徑優化問題。范志強，等[8]考慮運輸過程中各節點的軟時間窗約束問題，建立更加符合實際情況的多式聯運路徑優化模型。劉杰，等[9]考慮實際中航空、鐵路、水運出發時間固定對路徑選擇的影響，提出各節點運輸方式的備選集，建立多式聯運動態路徑優化模型。佟璐，等[10]研究多式聯運路徑優化模型與方法認為多式聯運路徑的選擇受到運輸成本、運輸時間，運輸質量和服務水平等相關因素的影響，將多式聯運問題轉化為一個最短路徑優化問題。這些研究普遍針對隨機因素影響下運輸時間和運輸費用兩個因素建立模型，其中對各節點時間窗問題的研究已經取得一定成果。大多結合運輸過程中的時間因素問題，把多式聯運路徑的動態路徑優化轉化為基于有限約束及總費用最小的最短路徑問題，而隨機因素影響下運輸質量控制并沒進行量化體現在優化模型中。

實際中，不同的運輸路段運輸費用、運輸時間不同，航空、鐵路、水運出發時間固定，貨物損失，都是運輸過程中隨機因素影響的表現，也是多式聯運動態路徑優化不能忽略的因素。筆者綜合考慮上述隨機因素中的軟時間窗約束和運輸質量控制問題，以總費用最小為目標建立數學規劃模型，并運用基于Dijkstra算法的改進路徑優化算法求解，使多式聯運的動態路徑優化模型更符合實際情況。

1 問題描述及模型建立

1.1 問題描述

一般多式聯運問題可描述為：某次物流作業需將貨物從起點O運送至終點D，運輸網絡由N個節點組成，任意兩節點間有K種交通方式可供選擇。各運輸方式的運輸能力，運輸時間，運輸成本均不同。運輸過程中各節點均可轉換運輸方式，運輸方式轉換便會產生中轉時間和中轉費用。

多式聯運的實際問題中，鐵路、水運、航空出發時間固定，運輸貨物要求在額定時間范圍內到達各節點。如果貨物早到，承運人則需等待，將會產生機會成本費用；如果晚到服務被延遲，可能產生多米諾效應，影響后面節點，應支付懲罰費用。模型中以到達終點時的貨損率作為運輸質量的衡量指標，并引入懲罰因子控制運輸質量。若貨物的貨損率超過額定貨損率，承運人應對貨物進行賠付且受到相應懲罰。

1.2 模型建立

1.2.1 假設條件

1)假設運輸路徑由起點O到終點D，任意兩節點間只能選擇一種運輸方式。

2)貨物運輸過程中，沒有貨物的增加或減少，貨物運輸量q恒定不變。

3)運輸過程中的貨損率和運輸距離成正比，且與運輸方式有關。

1.2.2 變量說明及模型

隨機因素影響下的多式聯運動態路徑優化模型如下。

總費用由運輸總費用、中轉總費用、運輸作業過程中提前到達節點的機會成本、運輸作業過程中晚到節點的懲罰成本、作業提前到達終點的機會成本 、作業晚到終點的懲罰成本、終點出現貨損時的賠付及懲罰成本構成，目標函數如式(1)：

(1)

約束條件如下：

1)運輸方式的選擇約束，即在物流作業過程中兩節點間只能選擇一種運輸方式：

(2)

2)在各節點中轉時，只能中轉到一種運輸方式，且同一節點只能中轉一次：

(3)

3)變量的邏輯約束：

(4)

4)各運輸路段的運輸能力約束，要求各路段能承載的貨物量小于其額定值：

(5)

5)目標函數(1)中ti的表達式：

(6)

6)中轉能力的約束：

(7)

7)各節點前后運輸方式對應約束，若在節點i采用運輸方式k，則由節點i到節點i+1采用運輸方式l：

(8)

8)貨損率ws的計算表達式：

ws=srηr+sfηf+ssηs+saηa+ηt

(9)

9)變量的非負約束：

q≥0,ti≥0,PE>0,PL>0,P>0,Cw>0

(10)

2 求解算法

路徑優化模型求解可看作是有限約束條件下的最短路徑問題，筆者采用基于Dijkstra算法的改進路徑優化算法即基于備選集的Dijkstra算法進行求解，劉杰[9]提到了該方法。基于備選集的Dijkstra算法是將運輸網絡中各節點的運輸方式進行拆分，并排除其中不能中轉或實際中不存在的中轉方式，將各節點可行的運輸方式形成備選集，然后在各節點選擇路徑時選擇備選集中的可中轉方式，從而找出最短路徑。與傳統的Dijkstra算法相比，改進后的方法能在各節點方便快捷的選擇中轉路徑，避免求解過程中的成本浪費，節約求解時間，降低求解難度。

由于各運輸方式的運輸距離、時間及運輸費用不同，求解過程中將各節點的標號形式記為[Ci，Ti，αi，βi，λi]，Ci表示物流作業從起點到節點i的成本費用，Ti表示到達節點i的時間，αi表示節點i之前的節點，βi表示節點i之前的運輸方式，λi表示節點i的運輸方式(標號中用1代表鐵路，2代表公路，3代表水路，4代表航空，5代表中轉)。

根據基于備選集的Dijkstra算法原理，運輸網絡圖中的標號分為兩類，一類為固定標號(S表示固定標號的集合)，另一類為臨時標號(∈表示臨時標號的集合)。從物流作業起點開始，計算起點到各節點備選集中各中轉方式的成本費用，總費用比較后將臨時標號改為固定標號，找到起點到終點運輸成本最小的固定標號集，固定標號集對應的節點集即為所求最短路徑。其中總費用費用為ci，ci=cαi+c(βi,αi)，c(βi,αi)為貨物從αi出發采用βi種交通方式的成本費用(若轉運則包括轉運成本)。

基于備選集的Dijkstra算法的求解步驟如圖1。

圖1 基于備選集的Dijkstra算法求解步驟Fig.1 The Dijkstra algorithm based on an alternative set

1)根據物流作業畫出運輸網絡圖，寫出各節點間實際的運輸方式，在各節點進行運輸方式拆分并根據經驗和實際情況去掉其中不能中轉路線和不存在的運輸方式，得到備選集運輸網絡圖。

2)從物流作業起點開始，記i=0，固定標號集S(0)={v0}，v0為物流作業的起點。其它節點全部為臨時標號記入∈，且有c0= 0，cvi=+∞，起點的標號為[0，Ti，-，-，-]，其它點的標號為[+∞，-，-，-，-]。

3)比較總費用修改與固定標號相連的臨時標號點。從物流作業起點出發，計算到各節點的總費用，運輸時間，并按前面提到的方式標號。

4)如果運輸網絡中的終點得到固定標號，則計算停止。計算從作業起點到各臨時標號點的總費用Ci，在各節點比較得出總費用最小的點標記為固定標號點，并將該點記入固定標號集合S中，其他點記入臨時標號集合∈。若在運輸網絡圖的終點沒有得到固定標號點集合則返回3)繼續計算，直到得出固定標號點集合即所求的最短路徑。

3 算法舉例

3.1 模型實用性驗證

為驗證文中模型與算法的實用性，現假設有一物流作業需將貨物重量q= 100 t，單價P=1 000 元/t的貨物從起點O運至終點D，運輸過程中運用鐵路、公路、航空、水運等4種運輸方式，且經過B，C，E，F共4個節點。額定時間范圍內的機會成本和懲罰成本PE=PL=100 元/h。額定貨損率w=3%，貨損比率ηr=0.1%，ηf=0.15%，ηs=0.08%，ηa=0.05%，ηt=1%，貨損懲罰成本cw=100 元/t。算例中的相關參數如表1和表2。

表1 不同運輸方式不同運輸路段的相關參數

(續表1)

運輸節點鐵路公路水運航空時間區間C-B—12/8/12———C-E20/10/1012/10/8——[35,37]C-F15/10/12——20/7/2—F-D16/15/2010/15/18——[45,50]E-D—12/13/10—25/5/1—

注：“·/·/·”第1個數值表示運輸單位貨物單位運距成本，元/(t·100 km)，第2個數值表示運輸距離，100 km，第3個數值表示運輸時間，h；時間區間表示貨物運輸到達節點的時間上限和時間下限，且服從一定的遞增規律。

表2 各運輸方式間轉運成本和運輸時間

注：“/”左邊為運輸成本，元；“/”右邊為運輸時間，h。

物流作業的運輸網絡如圖2。

圖2 O-D具體運輸網絡Fig.2 Specific transportation network diagram of O-D

實際問題中各節點間運輸方式存在限制，如圖2中起點O到節點A只有公路和鐵路兩種運輸方式，節點A到B只能通過公路和航空。按照基于備選集的Dijkstra算法原理對初始運輸網絡圖的各節點進行拆分，拆分后形成各節點備選集運輸網絡示意圖如圖3。

圖3 各節點備選集運輸網絡示意Fig.3 Transportation network diagram based on alternative set of each node

結合物流作業中貨物的特點和實際操作經驗，某兩種運輸方式之間不能直接中轉或實際節點不存在的中轉方式，該算例中設定備選的可中轉方式為：公路—鐵路，公路—水運，公路—航空。去掉運輸網絡中各節點不能中轉的路線得到的運輸網絡如圖4。

圖4 去掉不能中轉路線的備選集網絡Fig.4 Network based on alternative set of each node remove the can not transit one

圖4與圖3相比各節點的可中轉方式明顯減少，運輸網絡簡單化，更容易得到較優的最短路徑。

暫不考慮貨損率影響總費用的條件下，對運輸網絡中的各節點進行標號。標號完畢后，從作業終點D開始，在標號的節點中，尋找成本最小的點放入固定標號集合S中，得到一條最優路線。算例在圖4的基礎上，以總費用最小為約束，經過運算得出在不考慮貨物損失率前提下成本相對較小的3條路徑，最短路徑示意如圖5(圖5中將運輸費用最短的路徑進行標號)。

圖5 最短路徑示意Fig.5 Diagram of the shortest path

由圖5可清晰地看出，暫不考慮貨損率前提下最短路線為O—a1—a6—c2—c5—e2—e3—D。原始路徑為O—A—C—E—D，運輸成本為55 900 元，運輸時間為44 h，運輸方式為公路—鐵路—鐵路—鐵路—公路。模型中不僅要考慮多式聯運過程中運輸費用及運輸時間對路徑選擇的影響，還要考慮運輸質量即貨損率對路徑選擇的影響，下面將計算3條最短路徑的貨損賠付及懲罰情況，計算總的運輸費用，分析是否對路徑的選擇有所影響。3條費用最低的最短路徑，如表3。

表3 3條最短路徑

(續表3)

序號運費/元路徑原始路徑各節點運輸方式357600O—a2—a6—c2—c5—e2—e3—DO—A—C—E—D鐵路—鐵路—鐵路—鐵路—公路

運用模型中貨損率及貨損賠付公式計算每條路徑的貨損率，貨損賠付及罰金，總運輸費用，計算費用如表4。

表4 3條路徑貨損率，貨損賠付及總費用

表4的計算結果表明，模型中加入運輸質量控制后，第2條運輸路徑的費用為60 095 元，與沒有運輸質量控制下得到的第一條路徑相比，第2條路徑更優。即考慮貨損的情況下最短路徑為O—a1—a4—b2—b3—f1—f4—D，不考慮貨損情況下的最短路徑為O—a1—a6—c2—c5—e2—e3—D。各階段的運輸方式是公路—公路—公路—公路—公路，總運輸費用為60 095元，總運輸時間為52 h。加入運輸質量控制的模型分析得出，考慮貨損率對總費用的影響，最短路徑選擇會發生變化，更能體現路徑選擇過程的動態性和隨機性，從而驗證了模型的實用性。

3.2 模型有效性驗證

模型不僅考慮隨機因素對于運輸成本和運輸時間的影響，還考慮運輸質量即貨損率對總費用的影響。引入懲罰因子控制運輸質量的模型對于實際運輸路徑優化是否有效，是驗證模型有效性的關鍵。為驗證模型的有效性，比較分析3條備選路徑中貨損懲罰因子為100，2 100，4 100 元/t時的總費用，計算結果如表5。

表5 懲罰因子不同的情況下最優運輸路徑的選擇

Table 5 Selection of optimal transport path with different penalty factor

表5表明，不考慮運輸質量控制時，最優運輸路徑為路徑1，當貨損懲罰因子為1 100時，總費用發生變化，此時總費用最低的路徑為路徑2。隨著懲罰因子的不斷增大，賠付費用與處以的罰金增大，最優運輸路線的選擇也隨之發生明顯變化。在物流作業終點，隨著貨損懲罰因子增大，承運人選擇最優路徑時會在考慮總費用的同時選擇相對安全的運輸方式來減少罰金和賠付，從而選擇一條總費用少，時間短，相對較優的路徑。因此，運輸質量控制對最優運輸路徑的選擇影響較大，模型在實際操作中實用性較高。

4 結 語

多式聯運的運輸過程易受天氣、交通等隨機因素的影響，這些因素會造成運輸時間，運輸成本和運輸質量動態隨機變化而使多式聯運的動態路徑優化復雜化。筆者針對隨機因素影響的運輸費用，運輸時間和運輸質量3個方面，建立基于軟時間窗約束和引入懲罰因子運輸質量控制的多式聯運動態路徑優化模型，以運輸費用最小為目標，分析運輸網絡中各節點的運輸路徑備選集和中轉情況，運用改進的Dijkstra算法找出網絡中總費用最小，運輸質量較好的相對較優的路徑。算例表明，多式聯運過程中各節點在軟時間窗約束環境下運輸方式的選擇對運輸總費用和運輸質量有較大影響。運輸過程中若增大對貨物損失的懲罰因子，加大運輸質量控制力度對多式聯運的動態路徑優化有較大的積極作用，對企業有較大的實用性。

多式聯運是個復雜的物流系統，應該充分考慮其動態性，因此，采用更加優化的算法體現多式聯運的動態性，以及從供應鏈角度出發加強多式聯運路徑優化系統同其他子系統的關聯性將是今后的研究方向。

[1] Reddy V R,Kasilingam R G.Intermodal Transportation Considering Transfer Costs[C].Aruba:Proceedings of the 1995 Global Trends Conference of the Academy of Business Administration,1995.

[2] Ziliaskopoulos A,Wardell W.An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays[J].European Journal of Operational Research,2000,125(3):486-502.

[3] Boardman B S,Malstrom E M,Butler D P.Computer assisted routing of intermodal shipments[J].Computers & Industrial Engineering,1997,33(1/2):311-314.

[4] Chang Tsung-sheng.Best routes selection in international intermodal networks[J].Computers & Operations Research,2008,35(9):2877-2891.

[5] 魏航,李軍,蒲云.時變網絡下多式聯運的最短路徑問題研究[J].系統工程學報,2007,22(2):205-209. Wei Hang,Li Jun,Pu Yun.Study on the multi-modal shortest path in time-varying network [J].Journal of Systems Engineering,2007,22(2):205-209.

[6] 魏航,李軍,劉凝子.一種求解時變網絡下多式聯運最短路的算法[J].中國管理科學,2006,14(4):56-63. Wei Hang,Li Jun,Liu Ningzi.An algorithm for shortest path under the multimodal transport of time-varying network[J].Chinese Journal of Management Science,2006,14(4):56-63.

[7] 肖天國,符卓.基于遺傳算法的聯合運輸路徑優化[J].中國科技論文在線,2008,3(10):1-2. Xiao Tianguo,Fu Zhuo.Optimizing route of multi-modal transportation based on genetic algorithm [J].Science Paper Online,2008,3(10):1-2.

[8] 范志強,樂美龍.面向隨機環境的帶軟時間窗多式聯運路徑優化[J].工業工程與管理,2011,16(5):1-5. Fan Zhiqiang,Le Meilong.Research on multimodal transport routing problem with soft time windows under stochastic environment[J].Industrial Engineering and Management,2011,16(5):1-5.

[9] 劉杰,何世偉,宋瑞,等.基于運輸方式備選集的多式聯運動態路徑優化[J].鐵道學報,2011,33(10):1-6. Liu Jie,He Shiwei,Song Rui,et al.Study on optimization of dynamic paths of intermodal transportation network based on alternative set of transport modes[J].Journal of The China Railway Society,2011,33(10):1-6.

[10] 佟璐,聶磊,付慧伶.多式聯運路徑優化模型與方法研究[J].物流技術,2010,29(3):57-60. Tong Lu,Nie Lei,Fu Huiling.Research on optimization model and method of multi-modal transportation routing[J].Logistics Technology,2010,29(3):57-60.

Dynamic Paths Optimization of Multimodal Transport with Stochastic Factors

Chen Dandan, Hong Wei, Jia Yu

(School of Management, Chongqing Jiaotong University, Chongqing 400074, China)

Considering the dynamic and stochastic of multimodal transport and basing on transportation quality control with penalty factor, a model with the soft time windows restriction was presented for multimodal transport routing problem aiming at the minimize of total cost. Then the improved Dijkstra algorithm was used to solve the model. At last a multimodal transport problem formula based on four kinds of transport modes(the railway, highway, aviation, water transport) was designed to verify the practicality and effectiveness of the model.

traffic transportation engineering; multimodal transport; stochastic factors; optimization of dynamic paths; improved Dijkstra algorithm

10.3969/j.issn.1674-0696.2015.02.24

2012-11-05；

2013-10-09

陳丹丹(1989—)，女，四川資陽人，碩士研究生，主要從事物流與供應鏈管理方面的研究。E-mail：279178257@qq.com。

F 252.1

A

1674-0696(2015)02-112-06