陳丹丹,洪 衛(wèi),賈 禹
(重慶交通大學(xué) 管理學(xué)院,重慶 400074)
?
面向隨機因素的多式聯(lián)運動態(tài)路徑優(yōu)化
陳丹丹,洪 衛(wèi),賈 禹
(重慶交通大學(xué) 管理學(xué)院,重慶 400074)
針對隨機因素影響下多式聯(lián)運所表現(xiàn)的動態(tài)性和隨機性,在引入懲罰因子控制運輸質(zhì)量的基礎(chǔ)上,以總費用最小化為目標(biāo),建立了具有軟時間窗約束的動態(tài)路徑優(yōu)化模型;運用基于Dijkstra算法的改進路徑優(yōu)化算法求解模型;設(shè)計了一個基于鐵路、公路、航空及水運等4種運輸方式的多式聯(lián)運問題的算例,驗證了模型的實用性和有效性。
交通運輸工程;多式聯(lián)運;隨機因素;動態(tài)路徑優(yōu)化;改進的Dijkstra算法
隨著我國經(jīng)濟的迅猛發(fā)展,單一的貨物運輸方式已不能滿足市場需求,人們越來越重視多式聯(lián)運技術(shù)在國際貨物運輸領(lǐng)域的應(yīng)用。與傳統(tǒng)的運輸方式相比多式聯(lián)運具有高效、靈活、成本低、環(huán)保等特點,可降低運輸成本,提高運輸資源利用率以及企業(yè)競爭力。多式聯(lián)運動態(tài)路徑優(yōu)化問題是目前多式聯(lián)運技術(shù)研究的核心內(nèi)容,具有十分重要的研究意義。
多式聯(lián)運路徑優(yōu)化的研究中,V.R.Reddy,等[1]認為運輸總費用由城市內(nèi)中轉(zhuǎn)費用和城市間運輸費用組成,建立總費用最小的線性規(guī)劃模型優(yōu)化路徑。A.Ziliaskopoulos,等[2]考慮多式聯(lián)運過程中的時間因素,以運輸時間最短前提建立模型求解。B.S.Boardman,等[3]以運輸時間最短和成本最小為優(yōu)化目標(biāo),進行路徑優(yōu)化。Tsung-sheng Chang[4]采用基于時間窗的多目標(biāo)商品流模型解決多式聯(lián)運路徑選擇問題,為多式聯(lián)運路徑優(yōu)化中普遍關(guān)心的問題提供一種求解方法。魏航,等[5-6]考慮時變網(wǎng)絡(luò)下多式聯(lián)運的最短路徑問題研究,采用標(biāo)號法求解最短路問題。這些研究大多面向硬性的約束因素,以成本最小或運輸時間最短為目標(biāo)進行多式聯(lián)運靜態(tài)的路徑優(yōu)化。但是實際多式聯(lián)運過程中易受交通、天氣、機械故障等隨機因素的影響,對運輸過程中的運輸時間,運輸費用和運輸質(zhì)量也有較大影響。肖天國,等[7]結(jié)合運輸時間與運輸成本兩個因素建立模型,并運用遺傳算法求解聯(lián)合運輸路徑優(yōu)化問題。范志強,等[8]考慮運輸過程中各節(jié)點的軟時間窗約束問題,建立更加符合實際情況的多式聯(lián)運路徑優(yōu)化模型。劉杰,等[9]考慮實際中航空、鐵路、水運出發(fā)時間固定對路徑選擇的影響,提出各節(jié)點運輸方式的備選集,建立多式聯(lián)運動態(tài)路徑優(yōu)化模型。佟璐,等[10]研究多式聯(lián)運路徑優(yōu)化模型與方法認為多式聯(lián)運路徑的選擇受到運輸成本、運輸時間,運輸質(zhì)量和服務(wù)水平等相關(guān)因素的影響,將多式聯(lián)運問題轉(zhuǎn)化為一個最短路徑優(yōu)化問題。這些研究普遍針對隨機因素影響下運輸時間和運輸費用兩個因素建立模型,其中對各節(jié)點時間窗問題的研究已經(jīng)取得一定成果。大多結(jié)合運輸過程中的時間因素問題,把多式聯(lián)運路徑的動態(tài)路徑優(yōu)化轉(zhuǎn)化為基于有限約束及總費用最小的最短路徑問題,而隨機因素影響下運輸質(zhì)量控制并沒進行量化體現(xiàn)在優(yōu)化模型中。
實際中,不同的運輸路段運輸費用、運輸時間不同,航空、鐵路、水運出發(fā)時間固定,貨物損失,都是運輸過程中隨機因素影響的表現(xiàn),也是多式聯(lián)運動態(tài)路徑優(yōu)化不能忽略的因素。筆者綜合考慮上述隨機因素中的軟時間窗約束和運輸質(zhì)量控制問題,以總費用最小為目標(biāo)建立數(shù)學(xué)規(guī)劃模型,并運用基于Dijkstra算法的改進路徑優(yōu)化算法求解,使多式聯(lián)運的動態(tài)路徑優(yōu)化模型更符合實際情況。
1.1 問題描述
一般多式聯(lián)運問題可描述為:某次物流作業(yè)需將貨物從起點O運送至終點D,運輸網(wǎng)絡(luò)由N個節(jié)點組成,任意兩節(jié)點間有K種交通方式可供選擇。各運輸方式的運輸能力,運輸時間,運輸成本均不同。運輸過程中各節(jié)點均可轉(zhuǎn)換運輸方式,運輸方式轉(zhuǎn)換便會產(chǎn)生中轉(zhuǎn)時間和中轉(zhuǎn)費用。
多式聯(lián)運的實際問題中,鐵路、水運、航空出發(fā)時間固定,運輸貨物要求在額定時間范圍內(nèi)到達各節(jié)點。如果貨物早到,承運人則需等待,將會產(chǎn)生機會成本費用;如果晚到服務(wù)被延遲,可能產(chǎn)生多米諾效應(yīng),影響后面節(jié)點,應(yīng)支付懲罰費用。模型中以到達終點時的貨損率作為運輸質(zhì)量的衡量指標(biāo),并引入懲罰因子控制運輸質(zhì)量。若貨物的貨損率超過額定貨損率,承運人應(yīng)對貨物進行賠付且受到相應(yīng)懲罰。
1.2 模型建立
1.2.1 假設(shè)條件
1)假設(shè)運輸路徑由起點O到終點D,任意兩節(jié)點間只能選擇一種運輸方式。
2)貨物運輸過程中,沒有貨物的增加或減少,貨物運輸量q恒定不變。
3)運輸過程中的貨損率和運輸距離成正比,且與運輸方式有關(guān)。
1.2.2 變量說明及模型
隨機因素影響下的多式聯(lián)運動態(tài)路徑優(yōu)化模型如下。
總費用由運輸總費用、中轉(zhuǎn)總費用、運輸作業(yè)過程中提前到達節(jié)點的機會成本、運輸作業(yè)過程中晚到節(jié)點的懲罰成本、作業(yè)提前到達終點的機會成本 、作業(yè)晚到終點的懲罰成本、終點出現(xiàn)貨損時的賠付及懲罰成本構(gòu)成,目標(biāo)函數(shù)如式(1):
(1)
約束條件如下:
1)運輸方式的選擇約束,即在物流作業(yè)過程中兩節(jié)點間只能選擇一種運輸方式:
(2)
2)在各節(jié)點中轉(zhuǎn)時,只能中轉(zhuǎn)到一種運輸方式,且同一節(jié)點只能中轉(zhuǎn)一次:
(3)
3)變量的邏輯約束:
(4)
4)各運輸路段的運輸能力約束,要求各路段能承載的貨物量小于其額定值:
(5)
5)目標(biāo)函數(shù)(1)中ti的表達式:
(6)
6)中轉(zhuǎn)能力的約束:
(7)
7)各節(jié)點前后運輸方式對應(yīng)約束,若在節(jié)點i采用運輸方式k,則由節(jié)點i到節(jié)點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)
路徑優(yōu)化模型求解可看作是有限約束條件下的最短路徑問題,筆者采用基于Dijkstra算法的改進路徑優(yōu)化算法即基于備選集的Dijkstra算法進行求解,劉杰[9]提到了該方法。基于備選集的Dijkstra算法是將運輸網(wǎng)絡(luò)中各節(jié)點的運輸方式進行拆分,并排除其中不能中轉(zhuǎn)或?qū)嶋H中不存在的中轉(zhuǎn)方式,將各節(jié)點可行的運輸方式形成備選集,然后在各節(jié)點選擇路徑時選擇備選集中的可中轉(zhuǎn)方式,從而找出最短路徑。與傳統(tǒng)的Dijkstra算法相比,改進后的方法能在各節(jié)點方便快捷的選擇中轉(zhuǎn)路徑,避免求解過程中的成本浪費,節(jié)約求解時間,降低求解難度。
由于各運輸方式的運輸距離、時間及運輸費用不同,求解過程中將各節(jié)點的標(biāo)號形式記為[Ci,Ti,αi,βi,λi],Ci表示物流作業(yè)從起點到節(jié)點i的成本費用,Ti表示到達節(jié)點i的時間,αi表示節(jié)點i之前的節(jié)點,βi表示節(jié)點i之前的運輸方式,λi表示節(jié)點i的運輸方式(標(biāo)號中用1代表鐵路,2代表公路,3代表水路,4代表航空,5代表中轉(zhuǎn))。
根據(jù)基于備選集的Dijkstra算法原理,運輸網(wǎng)絡(luò)圖中的標(biāo)號分為兩類,一類為固定標(biāo)號(S表示固定標(biāo)號的集合),另一類為臨時標(biāo)號(∈表示臨時標(biāo)號的集合)。從物流作業(yè)起點開始,計算起點到各節(jié)點備選集中各中轉(zhuǎn)方式的成本費用,總費用比較后將臨時標(biāo)號改為固定標(biāo)號,找到起點到終點運輸成本最小的固定標(biāo)號集,固定標(biāo)號集對應(yīng)的節(jié)點集即為所求最短路徑。其中總費用費用為ci,ci=cαi+c(βi,αi),c(βi,αi)為貨物從αi出發(fā)采用βi種交通方式的成本費用(若轉(zhuǎn)運則包括轉(zhuǎn)運成本)。
基于備選集的Dijkstra算法的求解步驟如圖1。
圖1 基于備選集的Dijkstra算法求解步驟Fig.1 The Dijkstra algorithm based on an alternative set
1)根據(jù)物流作業(yè)畫出運輸網(wǎng)絡(luò)圖,寫出各節(jié)點間實際的運輸方式,在各節(jié)點進行運輸方式拆分并根據(jù)經(jīng)驗和實際情況去掉其中不能中轉(zhuǎn)路線和不存在的運輸方式,得到備選集運輸網(wǎng)絡(luò)圖。
2)從物流作業(yè)起點開始,記i=0,固定標(biāo)號集S(0)={v0},v0為物流作業(yè)的起點。其它節(jié)點全部為臨時標(biāo)號記入∈,且有c0= 0,cvi=+∞,起點的標(biāo)號為[0,Ti,-,-,-],其它點的標(biāo)號為[+∞,-,-,-,-]。
3)比較總費用修改與固定標(biāo)號相連的臨時標(biāo)號點。從物流作業(yè)起點出發(fā),計算到各節(jié)點的總費用,運輸時間,并按前面提到的方式標(biāo)號。
4)如果運輸網(wǎng)絡(luò)中的終點得到固定標(biāo)號,則計算停止。計算從作業(yè)起點到各臨時標(biāo)號點的總費用Ci,在各節(jié)點比較得出總費用最小的點標(biāo)記為固定標(biāo)號點,并將該點記入固定標(biāo)號集合S中,其他點記入臨時標(biāo)號集合∈。若在運輸網(wǎng)絡(luò)圖的終點沒有得到固定標(biāo)號點集合則返回3)繼續(xù)計算,直到得出固定標(biāo)號點集合即所求的最短路徑。
3.1 模型實用性驗證
為驗證文中模型與算法的實用性,現(xiàn)假設(shè)有一物流作業(yè)需將貨物重量q= 100 t,單價P=1 000 元/t的貨物從起點O運至終點D,運輸過程中運用鐵路、公路、航空、水運等4種運輸方式,且經(jīng)過B,C,E,F(xiàn)共4個節(jié)點。額定時間范圍內(nèi)的機會成本和懲罰成本PE=PL=100 元/h。額定貨損率w=3%,貨損比率ηr=0.1%,ηf=0.15%,ηs=0.08%,ηa=0.05%,ηt=1%,貨損懲罰成本cw=100 元/t。算例中的相關(guān)參數(shù)如表1和表2。
表1 不同運輸方式不同運輸路段的相關(guān)參數(shù)
(續(xù)表1)
運輸節(jié)點鐵路公路水運航空時間區(qū)間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個數(shù)值表示運輸單位貨物單位運距成本,元/(t·100 km),第2個數(shù)值表示運輸距離,100 km,第3個數(shù)值表示運輸時間,h;時間區(qū)間表示貨物運輸?shù)竭_節(jié)點的時間上限和時間下限,且服從一定的遞增規(guī)律。
表2 各運輸方式間轉(zhuǎn)運成本和運輸時間
注:“/”左邊為運輸成本,元;“/”右邊為運輸時間,h。
物流作業(yè)的運輸網(wǎng)絡(luò)如圖2。
圖2 O-D具體運輸網(wǎng)絡(luò)Fig.2 Specific transportation network diagram of O-D
實際問題中各節(jié)點間運輸方式存在限制,如圖2中起點O到節(jié)點A只有公路和鐵路兩種運輸方式,節(jié)點A到B只能通過公路和航空。按照基于備選集的Dijkstra算法原理對初始運輸網(wǎng)絡(luò)圖的各節(jié)點進行拆分,拆分后形成各節(jié)點備選集運輸網(wǎng)絡(luò)示意圖如圖3。
圖3 各節(jié)點備選集運輸網(wǎng)絡(luò)示意Fig.3 Transportation network diagram based on alternative set of each node
結(jié)合物流作業(yè)中貨物的特點和實際操作經(jīng)驗,某兩種運輸方式之間不能直接中轉(zhuǎn)或?qū)嶋H節(jié)點不存在的中轉(zhuǎn)方式,該算例中設(shè)定備選的可中轉(zhuǎn)方式為:公路—鐵路,公路—水運,公路—航空。去掉運輸網(wǎng)絡(luò)中各節(jié)點不能中轉(zhuǎn)的路線得到的運輸網(wǎng)絡(luò)如圖4。
圖4 去掉不能中轉(zhuǎn)路線的備選集網(wǎng)絡(luò)Fig.4 Network based on alternative set of each node remove the can not transit one
圖4與圖3相比各節(jié)點的可中轉(zhuǎn)方式明顯減少,運輸網(wǎng)絡(luò)簡單化,更容易得到較優(yōu)的最短路徑。
暫不考慮貨損率影響總費用的條件下,對運輸網(wǎng)絡(luò)中的各節(jié)點進行標(biāo)號。標(biāo)號完畢后,從作業(yè)終點D開始,在標(biāo)號的節(jié)點中,尋找成本最小的點放入固定標(biāo)號集合S中,得到一條最優(yōu)路線。算例在圖4的基礎(chǔ)上,以總費用最小為約束,經(jīng)過運算得出在不考慮貨物損失率前提下成本相對較小的3條路徑,最短路徑示意如圖5(圖5中將運輸費用最短的路徑進行標(biāo)號)。
圖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,運輸方式為公路—鐵路—鐵路—鐵路—公路。模型中不僅要考慮多式聯(lián)運過程中運輸費用及運輸時間對路徑選擇的影響,還要考慮運輸質(zhì)量即貨損率對路徑選擇的影響,下面將計算3條最短路徑的貨損賠付及懲罰情況,計算總的運輸費用,分析是否對路徑的選擇有所影響。3條費用最低的最短路徑,如表3。
表3 3條最短路徑
(續(xù)表3)
序號運費/元路徑原始路徑各節(jié)點運輸方式357600O—a2—a6—c2—c5—e2—e3—DO—A—C—E—D鐵路—鐵路—鐵路—鐵路—公路
運用模型中貨損率及貨損賠付公式計算每條路徑的貨損率,貨損賠付及罰金,總運輸費用,計算費用如表4。
表4 3條路徑貨損率,貨損賠付及總費用
表4的計算結(jié)果表明,模型中加入運輸質(zhì)量控制后,第2條運輸路徑的費用為60 095 元,與沒有運輸質(zhì)量控制下得到的第一條路徑相比,第2條路徑更優(yōu)。即考慮貨損的情況下最短路徑為O—a1—a4—b2—b3—f1—f4—D,不考慮貨損情況下的最短路徑為O—a1—a6—c2—c5—e2—e3—D。各階段的運輸方式是公路—公路—公路—公路—公路,總運輸費用為60 095元,總運輸時間為52 h。加入運輸質(zhì)量控制的模型分析得出,考慮貨損率對總費用的影響,最短路徑選擇會發(fā)生變化,更能體現(xiàn)路徑選擇過程的動態(tài)性和隨機性,從而驗證了模型的實用性。
3.2 模型有效性驗證
模型不僅考慮隨機因素對于運輸成本和運輸時間的影響,還考慮運輸質(zhì)量即貨損率對總費用的影響。引入懲罰因子控制運輸質(zhì)量的模型對于實際運輸路徑優(yōu)化是否有效,是驗證模型有效性的關(guān)鍵。為驗證模型的有效性,比較分析3條備選路徑中貨損懲罰因子為100,2 100,4 100 元/t時的總費用,計算結(jié)果如表5。
表5 懲罰因子不同的情況下最優(yōu)運輸路徑的選擇
Table 5 Selection of optimal transport path with different penalty factor
表5表明,不考慮運輸質(zhì)量控制時,最優(yōu)運輸路徑為路徑1,當(dāng)貨損懲罰因子為1 100時,總費用發(fā)生變化,此時總費用最低的路徑為路徑2。隨著懲罰因子的不斷增大,賠付費用與處以的罰金增大,最優(yōu)運輸路線的選擇也隨之發(fā)生明顯變化。在物流作業(yè)終點,隨著貨損懲罰因子增大,承運人選擇最優(yōu)路徑時會在考慮總費用的同時選擇相對安全的運輸方式來減少罰金和賠付,從而選擇一條總費用少,時間短,相對較優(yōu)的路徑。因此,運輸質(zhì)量控制對最優(yōu)運輸路徑的選擇影響較大,模型在實際操作中實用性較高。
多式聯(lián)運的運輸過程易受天氣、交通等隨機因素的影響,這些因素會造成運輸時間,運輸成本和運輸質(zhì)量動態(tài)隨機變化而使多式聯(lián)運的動態(tài)路徑優(yōu)化復(fù)雜化。筆者針對隨機因素影響的運輸費用,運輸時間和運輸質(zhì)量3個方面,建立基于軟時間窗約束和引入懲罰因子運輸質(zhì)量控制的多式聯(lián)運動態(tài)路徑優(yōu)化模型,以運輸費用最小為目標(biāo),分析運輸網(wǎng)絡(luò)中各節(jié)點的運輸路徑備選集和中轉(zhuǎn)情況,運用改進的Dijkstra算法找出網(wǎng)絡(luò)中總費用最小,運輸質(zhì)量較好的相對較優(yōu)的路徑。算例表明,多式聯(lián)運過程中各節(jié)點在軟時間窗約束環(huán)境下運輸方式的選擇對運輸總費用和運輸質(zhì)量有較大影響。運輸過程中若增大對貨物損失的懲罰因子,加大運輸質(zhì)量控制力度對多式聯(lián)運的動態(tài)路徑優(yōu)化有較大的積極作用,對企業(yè)有較大的實用性。
多式聯(lián)運是個復(fù)雜的物流系統(tǒng),應(yīng)該充分考慮其動態(tài)性,因此,采用更加優(yōu)化的算法體現(xiàn)多式聯(lián)運的動態(tài)性,以及從供應(yīng)鏈角度出發(fā)加強多式聯(lián)運路徑優(yōu)化系統(tǒng)同其他子系統(tǒng)的關(guān)聯(lián)性將是今后的研究方向。
[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] 魏航,李軍,蒲云.時變網(wǎng)絡(luò)下多式聯(lián)運的最短路徑問題研究[J].系統(tǒng)工程學(xué)報,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] 魏航,李軍,劉凝子.一種求解時變網(wǎng)絡(luò)下多式聯(lián)運最短路的算法[J].中國管理科學(xué),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] 肖天國,符卓.基于遺傳算法的聯(lián)合運輸路徑優(yōu)化[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] 范志強,樂美龍.面向隨機環(huán)境的帶軟時間窗多式聯(lián)運路徑優(yōu)化[J].工業(yè)工程與管理,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] 劉杰,何世偉,宋瑞,等.基于運輸方式備選集的多式聯(lián)運動態(tài)路徑優(yōu)化[J].鐵道學(xué)報,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] 佟璐,聶磊,付慧伶.多式聯(lián)運路徑優(yōu)化模型與方法研究[J].物流技術(shù),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—),女,四川資陽人,碩士研究生,主要從事物流與供應(yīng)鏈管理方面的研究。E-mail:279178257@qq.com。
F 252.1
A
1674-0696(2015)02-112-06