武 威，董寶田，陳光偉，張曉棟

（1.北京交通大學(xué)?交通運(yùn)輸學(xué)院，北京?100044；2.中國鐵路信息技術(shù)中心,?北京?100844）

基于 Vague 集的鐵路車流徑路優(yōu)化

武 威1，董寶田1，陳光偉2，張曉棟1

（1.北京交通大學(xué)?交通運(yùn)輸學(xué)院，北京?100044；2.中國鐵路信息技術(shù)中心,?北京?100844）

為實(shí)現(xiàn)車流徑路時(shí)間消耗與距離消耗的雙重優(yōu)化，求得更合理徑路，針對以往徑路優(yōu)化模型沒有考慮徑路走行時(shí)間的問題，將車輛在車流徑路上的運(yùn)行時(shí)間分為在途時(shí)間與在站時(shí)間，并結(jié)合信息化手段對在站時(shí)間的歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析來確定在站時(shí)間參數(shù)，建立以車輛在路網(wǎng)上運(yùn)行的路徑最短和時(shí)間最短為目標(biāo)的多目標(biāo)優(yōu)化模型，采用?K?短路算法求出滿足約束的合理徑路集，并引入Vague?集來對合理徑路集進(jìn)行評價(jià)，從而得到滿意解，最后通過算例驗(yàn)證了模型的有效性與算法的可行性。

鐵路運(yùn)輸；K?短路算法；Vague?集；車流徑路；鐵路網(wǎng)

鐵路車流徑路問題是鐵路運(yùn)輸?shù)年P(guān)鍵性問題，不少專家和學(xué)者都對此問題展開深入研究與探討。宋建業(yè)[1]采用鄰接矩陣存儲的方法，并在基于支點(diǎn)站的全國鐵路環(huán)狀路網(wǎng)圖上，利用 dijkstra算法求解最短徑路，通過最短徑路線來確定起終點(diǎn)站為非支點(diǎn)站的情況，在路網(wǎng)規(guī)模較小時(shí)可以有效解決最短徑路的問題，但實(shí)際中隨著路網(wǎng)規(guī)模的擴(kuò)大，最短徑路往往難以確定；施其洲等[2]針對路網(wǎng)上的雙向空、重車流同時(shí)進(jìn)行多目標(biāo)線性規(guī)劃，從整體的角度優(yōu)化車流徑路并盡可能提高線路能力利用率；靳來勇等[3]分析影響區(qū)域車流徑路確定的因素并給出其制約因素和目標(biāo)函數(shù)；李明博等[4]結(jié)合鐵路現(xiàn)場的實(shí)際情況，提出合理非最短車流徑路存在的原因，并對其進(jìn)行理論解析，從宏觀上對車流的分流流向進(jìn)行分析。以上的車流徑路研究均以車輛走行距離為主要考慮因素，但運(yùn)輸時(shí)間也是客戶非常關(guān)心的問題，目前鐵路貨物運(yùn)到時(shí)間難以準(zhǔn)確預(yù)測，客戶無法有效掌控運(yùn)輸時(shí)間，致使很多運(yùn)輸時(shí)間敏感型客戶對選擇鐵路運(yùn)輸存有顧慮，對鐵路在運(yùn)輸市場上的競爭產(chǎn)生不利影響。因此，考慮信息化手段，利用鐵路大數(shù)據(jù)來估算車流徑路上的時(shí)間消耗，對車流徑路確定過程中的車輛走行時(shí)間消耗和距離消耗進(jìn)行雙目標(biāo)優(yōu)化，以求得滿意的車流徑路。

1車流徑路的時(shí)間消耗

圖1　車輛在車流徑路上走行的時(shí)間消耗

（1）車輛在途時(shí)間。車輛在途時(shí)間是指車輛在鐵路區(qū)間線路上的運(yùn)行時(shí)間。

（2）車輛在站時(shí)間。車輛在站時(shí)間包括如下。①對于裝車站，在站時(shí)間包括：等待取車時(shí)間、取車時(shí)間、集結(jié)作業(yè)時(shí)間、編組作業(yè)時(shí)間、出發(fā)作業(yè)時(shí)間。②對于編組站或區(qū)段站，在站時(shí)間包括：到達(dá)作業(yè)時(shí)間、解體作業(yè)時(shí)間、集結(jié)作業(yè)時(shí)間、編組作業(yè)時(shí)間、出發(fā)作業(yè)時(shí)間。③對于卸車站，在站時(shí)間包括：到達(dá)作業(yè)時(shí)間、解體作業(yè)時(shí)間、等待送車時(shí)間、送車時(shí)間。這些時(shí)間大多具有隨機(jī)性，有的時(shí)間波動小，如到達(dá)作業(yè)時(shí)間和出發(fā)作業(yè)時(shí)間；有的時(shí)間波動比較大，如車輛集結(jié)時(shí)間；采用不同作業(yè)方式的編組站，其解體和編組作業(yè)時(shí)間也不同。這些情況均對車輛在站時(shí)間的估計(jì)造成很大困難。

（3）中轉(zhuǎn)車平均停留時(shí)間。隨著信息技術(shù)革新和鐵路信息化的發(fā)展，信息化手段對監(jiān)測列車運(yùn)行位置和運(yùn)行狀態(tài)起到了關(guān)鍵作用。在實(shí)際運(yùn)營組織過程中，車輛在裝車站裝車時(shí)會提報(bào)裝車報(bào)文，掛運(yùn)該車輛的列車在出發(fā)時(shí)會提報(bào)列車出發(fā)報(bào)文，列車到達(dá)編組站時(shí)會提報(bào)列車到達(dá)報(bào)文，車輛在卸車站卸車時(shí)也會提報(bào)卸車報(bào)文。在計(jì)算車輛在裝車站的在站作業(yè)時(shí)間時(shí)，可以通過出發(fā)報(bào)文與裝車報(bào)文的時(shí)間差確定；同理，計(jì)算車輛在編組站的車輛中轉(zhuǎn)停留時(shí)間，也可以根據(jù)編組該車輛的列車在該站的列車到達(dá)報(bào)文和列車出發(fā)報(bào)文的時(shí)間差來確定。這樣就可以得到車輛的在站時(shí)間消耗。因此，統(tǒng)計(jì)每個(gè)車輛在經(jīng)由技術(shù)站的歷史中轉(zhuǎn)停留時(shí)間，采用求加權(quán)平均數(shù)的方法確定中轉(zhuǎn)車平均停留時(shí)間，計(jì)算公式為

式中：∑?N有t有為有調(diào)中轉(zhuǎn)車總停留車小時(shí)；∑?N無t無為無調(diào)中轉(zhuǎn)車總停留車小時(shí)；∑?N有為有調(diào)中轉(zhuǎn)車數(shù)；∑?N無為無調(diào)中轉(zhuǎn)車數(shù)。

2車流徑路的雙目標(biāo)優(yōu)化模型構(gòu)建

給定有向圖 G = (V，E，l，t)，V 是頂點(diǎn)集，E是邊集，l，t 是邊上的權(quán)。給定車流徑路為 f，xij定義為關(guān)于運(yùn)行徑路 f 上是否包含弧段 (i，j) 的 0-1 變量，當(dāng)弧段 (i，j) 在 f 上，車輛由 i 運(yùn)行到 j 時(shí) xij= 1，否則 xij= 0。

構(gòu)建優(yōu)化模型如下。

式中：Z 為目標(biāo)值；Z1為總車公里數(shù)；Z2為總走行時(shí)間；lij為 i 站與 j 站之間的站間里程；tij表示 i 站與 j 站之間的運(yùn)行時(shí)間；θ1為 Z1相對于總目標(biāo)值 Z的權(quán)重；θ2為 Z2相對于總目標(biāo)值 Z 的權(quán)重；s，t 分別代表徑路的起點(diǎn)和終點(diǎn)；xij為 0－1 變量，等于 0表示車輛運(yùn)行徑路不含弧段 (i，j)，等于 1 則表示徑路經(jīng)過弧段 (i，j)。

公式 ⑸ 表示節(jié)點(diǎn)守恒條件，對于徑路的經(jīng)由節(jié)點(diǎn) i，其他節(jié)點(diǎn)指向節(jié)點(diǎn) i 的有向線段與節(jié)點(diǎn) i 發(fā)出的有向線段數(shù)目相等；公式 ⑹ 表示在滿足公式⑸ 的條件下，對于任意一個(gè)節(jié)點(diǎn) i，至多只能有 1條徑路與其相鄰節(jié)點(diǎn)相連；公式 ⑺ 表示目標(biāo)值 Z1，Z2相對于總目標(biāo)值 Z 權(quán)重之和為 1。

第一，教材內(nèi)容要以市場需求為導(dǎo)向，內(nèi)容結(jié)構(gòu)設(shè)計(jì)上要將教材文字、電子課件、視頻教材、音聲等進(jìn)行統(tǒng)一起來，從而建立起立體化的實(shí)訓(xùn)教材，幫助學(xué)生更直觀、更準(zhǔn)確地把握商務(wù)日語的使用方法；第二，編制校本教材。商務(wù)日語是一個(gè)實(shí)踐性極強(qiáng)的復(fù)合型課程，各個(gè)高?？梢越Y(jié)合本地區(qū)產(chǎn)業(yè)布局及開發(fā)狀況，編寫符合本地區(qū)實(shí)際情況的校本教材，并在使用過程中進(jìn)行不斷地改進(jìn)和完善；第三，采取模塊化、互動式、多案例的編寫方法，逐步推進(jìn)商務(wù)日語的跨文化交際技能，將實(shí)訓(xùn)教材設(shè)計(jì)與高校專業(yè)特色實(shí)訓(xùn)室建設(shè)相結(jié)合，為學(xué)生模擬一個(gè)與實(shí)際工作崗位相似的環(huán)境，幫助學(xué)生盡快融入到實(shí)訓(xùn)課程當(dāng)中，并提高他們在商務(wù)場景中日語語言的應(yīng)用能力。

為方便討論，模型暫不考慮線路能力問題，只對給定 OD 的單一車流徑路進(jìn)行優(yōu)化。在求解多目標(biāo)優(yōu)化模型時(shí)，各目標(biāo)之間通常存在沖突，針對某個(gè)目標(biāo)具有優(yōu)勢的解對于另一個(gè)目標(biāo)來說可能并非最優(yōu)，因而對于這個(gè)多目標(biāo)最短路徑問題，其結(jié)果往往不存在最優(yōu)解，而只有滿意解。

3基于Vague集的車流徑路方案評價(jià)

Vague 集在 Fuzzy 集的基礎(chǔ)上[5]引入了真隸屬度 t 和假隸屬度 f，將一元隸屬度 t 擴(kuò)展至二元的真隸屬度 t 和假隸屬度 f，將 Vague 集用區(qū)間的形式表示為 A = [t，1- f ]，其中真隸屬度 t 表示支持，假隸屬度 f 表示反對，并且還可以表示出中立的比例為 1- t - f。以投票模型為例，如果 Vague 集A = [0.5，0.7]，則表示贊成投票的比例為 0.5，不贊成的為 0.3，棄權(quán)比例為 0.2[6]。可見，與 Fuzzy 集相比，Vague 集對不確定性的描述具有更加豐富的信息和意義。

對于真隸屬度 t 和假隸屬度 f 的確定，常常采用 Vague 集指標(biāo)公式。定量指標(biāo)分為效益型和成本型 2 類，效益型指標(biāo)值越大結(jié)果越優(yōu)，而成本型指標(biāo)值越小結(jié)果越優(yōu)。據(jù)此特點(diǎn)結(jié)合 Vague 集可將指標(biāo)值進(jìn)行規(guī)范化處理。

對于成本型指標(biāo)，規(guī)定真假隸屬度分別采用下式計(jì)算[7]。

式中：v 為車流徑路方案評價(jià)指值；vmax和 vmin分別為 v 該指標(biāo)的理論最大值和最小值，一般是 v 的計(jì)算最大指標(biāo)值和 v 的計(jì)算最小指標(biāo)值乘以對應(yīng)的最值系數(shù)。

對于效益型指標(biāo)，規(guī)定真假隸屬度分別采用下式計(jì)算[7]。

Vague 集的記分函數(shù)用來衡量備選方案滿足決策者要求的程度，記分值越高，方案越優(yōu)。根據(jù)Vague 集的相似度來構(gòu)造記分函數(shù)，假設(shè) 2 個(gè) Vague值為 X = [tx，1－ fx]，Y = [ty，1－ fy]，則它們之間的相似度定義為[8]

方案 Ai可以用 Vague 集表示為[9]

式中：C1，C2，…，Cn分別為從不同角度對方案 Ai的評價(jià)指標(biāo)；tij表示方案 Ai對評價(jià)指標(biāo) Cj的真隸屬度；fij表示方案 Ai對評價(jià)指標(biāo) Cj的假隸屬度。

對方案 Ai的各評價(jià)指標(biāo)的重要性賦權(quán)值，權(quán)重分別為 ω?= {ω1，ω2，…，ωn}，其中 ω1，ω2，…，ωn∈?(0，1)，并且 ω1+ ω2+ … + ωn= 1。假設(shè)理想方案的所有 Vague 值均為 [1，1]，則備選方案與理想方案之間的相似度記分函數(shù)計(jì)算公式為[8]

4實(shí)例分析

將鐵路網(wǎng)中銜接3個(gè)及3個(gè)方向以上線路的車站作為支點(diǎn)，建立以支點(diǎn)站為節(jié)點(diǎn)的路網(wǎng)或局部路網(wǎng)簡化拓?fù)浣Y(jié)構(gòu)，可以有效縮小問題規(guī)模，提高運(yùn)算效率。以如圖2所示的局部路網(wǎng)簡化拓?fù)鋱D為例，求解豐臺西到徐州北的車流徑路。路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖上只表示出支點(diǎn)站，邊上的權(quán)值表示兩站之間的距離。車站名與車站 ID 的對應(yīng)情況如表1所示。

如果區(qū)段起始站和結(jié)束站屬于同一鐵路局的管轄范圍，則查定對應(yīng)鐵路局的平均旅行速度統(tǒng)計(jì)值作為區(qū)段的平均旅行速度；如果區(qū)段的始發(fā)站和終到站分別屬于不同鐵路局，則求出兩局平均旅行速度統(tǒng)計(jì)值的算術(shù)平均值作為區(qū)段的平均旅行速度。通過區(qū)段里程除以區(qū)間平均旅行速度可以計(jì)算其相應(yīng)區(qū)段的運(yùn)行時(shí)間。路段參數(shù)如表2所示。

圖2　簡化的局部鐵路網(wǎng)結(jié)構(gòu)

表1車站名與車站 ID

通過對圖2中各站 30 d 的車輛到發(fā)報(bào)文進(jìn)行分析，統(tǒng)計(jì)其平均有調(diào)作業(yè)時(shí)間和無調(diào)作業(yè)時(shí)間，將二者加權(quán)平均數(shù)作為車輛中轉(zhuǎn)停留時(shí)間。各站的車輛中轉(zhuǎn)停留時(shí)間如表3所示。

確定豐臺西到徐州北的車流徑路時(shí)，分別以距離和時(shí)間為權(quán)值，運(yùn)用 K 短路算法計(jì)算前 K 條最短徑路，結(jié)果分別如表4和表5 所示。

從表4和表5可以看出，車流徑路一般不可能達(dá)到距離和時(shí)間同時(shí)最優(yōu)，因而提取以上 2 種徑路結(jié)果的交集，交集中的每一條徑路代表一個(gè)可行方案，如表6所示。

由于方案中的指標(biāo)屬于值越小目標(biāo)越優(yōu)的成本型指標(biāo)，采用公式 ⑻ 和 ⑼ 分別計(jì)算方案 A (i) 在指標(biāo) C1和 C2上的 Vague 集，定量指標(biāo) vmax為各備選方案中該指標(biāo)的最大值乘以系數(shù) 1.2，vmin為各備選方案該指標(biāo)的最小值乘以系數(shù) 0.8[7]，計(jì)算結(jié)果如表7所示。

表2　路段參數(shù)

表3　車輛中轉(zhuǎn)停留時(shí)間

表4　以距離為權(quán)值的最短徑路 　km

表5　以時(shí)間為權(quán)值的最短徑路 　h

表6　滿足時(shí)間和距離約束的徑路交集

表7　不同方案對應(yīng)不同指標(biāo)的 Vague 值

由于需求不同，客戶對運(yùn)輸距離 (成本) 和運(yùn)輸時(shí)間的預(yù)期也不同。令 ω1= 0.45，ω2= 0.55，根據(jù) ⒀ 式，計(jì)算出 3 種方案的記分函數(shù)值為M (A1) = 0.46，M (A2) = 0.44，M (A3) = 0.58，則M (A3) ＞ M (A1) ＞ M (A2) 。

由表6可知，方案 1 滿足距離最短，方案 3 滿足時(shí)間最短，方案 2 是折中方案。而用 Vague 集求解距離與時(shí)間協(xié)同優(yōu)化的結(jié)果是方案 3 優(yōu)于方案1，方案 1 優(yōu)于方案 2。這是由于在用計(jì)分函數(shù)求解時(shí)，采用的 Vague 集理想方案 [1，1] 代表同時(shí)滿足距離最短和時(shí)間最短的徑路，而這種理想方案在算例中并不存在，因而選擇合理徑路是在給定權(quán)重下選擇使距離和時(shí)間盡可能小的徑路。方案 1、方案 3 與理想方案的對比如表8所示。

在表8中，方案 2 相比理想方案的距離消耗為(806－775)/775 = 0.04，相比理想方案的時(shí)間消耗(39.79－33.38)/33.38 = 0.19，結(jié)合給定權(quán)重可以確定總的多余消耗為 0.04×0.45 + 0.19×0.55 = 0.12。其他方案的計(jì)算方法與此相同。加權(quán)消耗值表示相對于理想值的總增加消耗，總增加消耗越小越接近最優(yōu)，即最滿意方案為方案 3，其次為方案 1，再次為方案 2。

表8　各方案與理想方案的對比

5結(jié)束語

針對車流徑路的優(yōu)化問題，建立了以距離消耗最短和時(shí)間消耗最少的多目標(biāo)優(yōu)化模型，通過利用歷史數(shù)據(jù)確定車輛在途、在站的時(shí)間消耗參數(shù)，并結(jié)合 K 短路算法求出合理徑路集，運(yùn)用 Vague 集的方法來分析合理徑路集來確定滿足約束的滿意解。通過分析可知滿意解符合實(shí)際情況，并為確定車流徑路的時(shí)間消耗預(yù)測提供一種可行的方法，在一定程度上有助于貨物運(yùn)到時(shí)間的確定。下一步研究方向可以對相同 OD 的車輛在同一編組站的中轉(zhuǎn)停留時(shí)間分貨種、分方向進(jìn)行細(xì)分，更加精細(xì)化地確定車輛中轉(zhuǎn)停留時(shí)間，從而使車流徑路的時(shí)間消耗值預(yù)測更加準(zhǔn)確，使車流徑路的確定更加優(yōu)化。

[1] 宋建業(yè). 全國鐵路車流徑路計(jì)算方法的研究[J]. 蘭州鐵道學(xué)院學(xué)報(bào)，1990，9 (3)：37-44.

SONG Jian-ye. The Research on the Calculation Method of the Wagon Routing on the Railway Network[J]. Journal of Lanzhou Railway College，1990，9 (3)：37-44.

[2] 施其洲，施 勇. 具有雙向、空重車流的路網(wǎng)車流徑路多目標(biāo)線性規(guī)劃模型及算例[J]. 鐵道學(xué)報(bào)，1999，21(1)：1-9.

SHI Qi-zhou，SHI Yong. Multi-Objective Linear-Programming Model and Its Algorithm for Car Flow Routing with Bidirectional Heavy and Empty Cars in Railway Network[J]. Journal of the China Railway Society, 1999，21(1)：1-9.

[3] 靳來勇，葉玉玲，趙永旭，等. 區(qū)域性路網(wǎng)車流徑路的選擇[J]. 中國鐵路，2005(12)：49-51.

JIN Lai-yong，YE Yu-ling，ZHAO Yong-xu，et al. Choosing of Regional Railway Network Car Flow Routing [J]. Chinese Railways，2005(12)：49-51.

[4] 李明博，季 令. 合理的非最短車流徑路理論解析[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2008，30(6)：18-20.

LI Ming-bo，JI Ling. Theoretical Analysis of Reasonable Non-shortest Car Flow Routing[J]. Railway Transport and Economy，2008，30(6)：18-20.

[5] 江 偉. Vague 集理論及其在智能決策中的應(yīng)用研究[D].南寧：廣西大學(xué)，2008.

JIANG Wei. Application and Research of Vague Set Theory on Intelligent Decision[D]. Nanning：Guangxi University，2008.

[6] 符海東，盧正鼎. 基于 Vague 集距離的多評價(jià)指標(biāo)模糊決策方法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2003，31(8)：77-79.

FU Hai-dong，LU Zheng-ding. Fuzzy Decision Making with Multicriteria based on Distance of Vague Set[J]. Journal Huazhong University of Science & Technology (Nature Science Edition)，2003，31(8)：77-79.

[7] 陳 琨，張翠東，孫家駟. 基于 Vague 集的互通式立交方案綜合評價(jià)方法[J]. 公路交通技術(shù)，2008(4)：125-127.

CHEN Kun，ZHANG Cui-dong，SUN Jia-si. Synthetic Evaluation Method for Interchange Scheme based on Vague Set[J]. Technology of Highway and Transport，2008(4)：125-127.

[8] 李彥斌，張 恒，陳文姣. 基于 Vague 集的輸電線路設(shè)計(jì)方案的優(yōu)選[J]. 科技和產(chǎn)業(yè)，2011，11(11)：81-83.

LI Yan-bin，ZHANG Heng，CHEN Wen-jiao. Optional Option of Design Plans for Transmission Lines based on Vague Set[J]. Science Technology and Industry，2011，11(11)：81-83.

[9] 要瑞璞，沈惠璋. 基于 Vague 集投影及距離的模糊多指標(biāo)決策[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識，2009，39(2)：19-22.

YAO Rui-pu，SHEN Hui-zhang. Fuzzy Multicriteria Decision Making based on Projectivity and Distance of Vague Sets[J]. Mathematics in Practice and Theory，2009，39(2)：19-22.

責(zé)任編輯：吳文娟

Optimization of Car Flow Routing based on Vague Sets

WU Wei1, DONG Bao-tian1, CHEN Guang-wei2, ZHANG Xiao-dong1

(1.School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044，China；2.China Railway Information Technology Center, Beijing 100038，China)

Railway car flow routing optimization should take account of path distance as well as path realization time so as to mirror the real process of train operation. To overcome the shortage of lack of path realization time factor in previous optimization models, travelling time of freight car in car flow routing is divided into on-way time and on-station time, and IT technology methods are used to calculate on-station parameters based on historical data of on-station time so that a multiobjective optimization model is established with objectives of shortest path and shortest time; and reasonable path sets is obtained and estimated by Vague sets and algorithm of K-shortest path. Finally, the validity of the model and the feasibility of the algorithm are verified by computational example.

Railway Transportation; Algorithm of K-Shortest Path; Vague Sets; Car Flow Routing; Railway Network

1003-1421(2016)10-0042-06

U292.3

A

10.16668/j.cnki.issn.1003-1421.2016.10.09

2016-06-15

中國鐵路總公司科技研究開發(fā)計(jì)劃課題(2014X009-A)