軌道交通系統(tǒng)票務(wù)清分算法

《軌道交通系統(tǒng)票務(wù)清分算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、軌道交通系統(tǒng)票務(wù)清分算法黃勝,孟世聰,胡幼華(華東師范大學(xué)計算機(jī)科學(xué)技術(shù)系,上海200062)摘要:提出了一個實現(xiàn)軌道交通系統(tǒng)票務(wù)清分的算法。給出了清分的精確算法,在論證精確算法的不可實現(xiàn)性的基礎(chǔ)上,演變出切實可行的票務(wù)清分的近似算法,并通過一個清分實例來進(jìn)一步闡述如何實現(xiàn)清分。關(guān)鍵詞:票務(wù)清分算法;中圖法分類號:TP30116最短路徑;次短路徑文獻(xiàn)標(biāo)識碼:A文章編號:100123695(2004)0620104203AnAlgorithmofIncomeDistributionoftheUndergroundSystemHUANGSheng,ME

2、NGShi2cong,HUYou2hua(Dept.ofComputerScience&Technology,EastChinaNormalUniversity,Shanghai200062,China)Abstract:Analgorithmispresentedinthispaperfordistributingticketsincomeofthecityundergroundsystem.Tobeginwith,aprecisedistributingalgorithmisgivenbutafterwardsprovedunrealizabl

3、e.Basedonsuchconclusion,anapproximateandrealizabledistributingalgorithmisputforwardinsteadwithadistributingexampletoillustratehowitworks.Keywords:AlgorithmofTicketsIncomeDistribution;ShortestPath;SecondShortestPath近年來軌道交通系統(tǒng)規(guī)模不斷擴(kuò)大,軌道交通系統(tǒng)將成為一個空前復(fù)雜的網(wǎng)狀結(jié)構(gòu),其中各條線路又有不同的營運方。在這樣一個復(fù)雜的網(wǎng)狀結(jié)

4、構(gòu)中,從站點s到站點t,很可能有多種路徑,而每條路徑很可能經(jīng)過了若干中轉(zhuǎn)站點,即該路徑可能跨過了不同的幾條軌道線路(無論走過哪條路徑,從s點到t點的票價Q是固定的)。清分的目的便是要把Q合理地分配給從s到t所經(jīng)過的各條線路的營運方,這是軌道交通營運必須解決的一個重要問題。的長度,就需要記錄下持卡者此次旅程所經(jīng)過的站點。這要求在各個換乘站點中增設(shè)大量的刷卡機(jī)。而這是難以實現(xiàn)的:(1)刷卡機(jī)是比較昂貴的硬件設(shè)備,增設(shè)刷卡機(jī)必然帶來巨額的硬件投入。(2)在換乘軌道線路時刷卡,將使人流速度降低,在客流高峰期必將出現(xiàn)擁擠。(3)由于人流量很大,即便是只需要記

5、錄進(jìn)站和出站時兩點的信息,數(shù)據(jù)庫也需要占用很大存儲空間。如果再加上換乘點的信息,則存儲空間將成數(shù)量級的增加,這必然導(dǎo)致數(shù)據(jù)庫維護(hù)備份復(fù)雜度的提高和清分?jǐn)?shù)據(jù)源安全可靠性的降低。因此要求提出一種合理可行的方法。112路徑近似算法設(shè)Pm是乘客選擇第m短路徑的概率,Wij表示以站點i為起點,j為終點所獲得的收入。設(shè)Lij,1表示站點i到站點j的最短路徑,這條路徑經(jīng)過了線段

6、S1S2

7、1,

8、S2S3

9、2,?,

10、SdSd+1

11、d(其中

12、SdSd+1

13、表示線段長度,下標(biāo)表示相應(yīng)線段所屬的線路號分別為1,2,?,d)。于是這d條線路的所獲權(quán)值分別為(

14、S1S2

15、1

16、×P1×Wij)÷Lij,1,(

17、S2S3

18、2×P1×Wij)÷Lij,1,?,(

19、SdSd+1

20、d×P1×Wij)÷Lij,1。其中P1表示乘客選擇最短路徑換乘的概率。同理Lij,2表示站點i到站點j的次短路徑,Lij,3表示站點i到站點j的次次短路徑?。每一條路徑又可以為各自所經(jīng)過1清分算法的提出和分析111精確算法精確算法是指從站點s到站點t,各條所經(jīng)線路按各自在這次路途中所占的長度來分得票務(wù)收入。設(shè)第p張交通卡的編號為Np,Np號交通卡第q次使用的花費為Npq,第p張交通卡第q次使用所經(jīng)過的總長度為Lpq,在第k條路線上通過的距離為Lpqk

21、,則第k條線路所獲得的權(quán)值Vk的計算公式為nmNpqVk=∑∑Lpqk×(1)Lpqp=1q=1式中n表示卡的總數(shù),m表示該卡總的使用次數(shù)。第k條線路的營運方應(yīng)分得的收入InCk為VkInCk=All2Income×(2)t∑Vi的線路分得一個權(quán)值。第k條線路的權(quán)值V就是不同路徑i=1k,1式中All2Income為軌道交通系統(tǒng)營運總收入,Vi為第i條線路的權(quán)值,t為總線路數(shù)。為了實現(xiàn)精確算法必須獲得每一張卡在各條線路所走過下通過該線路所得的權(quán)值的總和:nnMV=∑∑∑

22、SS

23、PW/L()3ghkmijij,mk,1i=1j=1m=1式中

24、SgSh

25、

26、k為從站點i到站點j的第m短的路徑中經(jīng)過線路k上的總長度,M表示從站點i到站點j的所有路徑數(shù),n表示站點總數(shù)。易證在Pm