资源描述：
《轨道交通系统票务清分算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、轨道交通系统票务清分算法黄胜,孟世聪,胡幼华(华东师范大学计算机科学技术系,上海200062)摘要:提出了一个实现轨道交通系统票务清分的算法。给出了清分的精确算法,在论证精确算法的不可实现性的基础上,演变出切实可行的票务清分的近似算法,并通过一个清分实例来进一步阐述如何实现清分。关键词:票务清分算法;中图法分类号:TP30116最短路径;次短路径文献标识码: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近年来轨道交通系统规模不断扩大,轨道交通系统将成为一个空前复杂的网状结构,其中各条线路又有不同的营运方。在这样一个复杂的网状结
4、构中,从站点s到站点t,很可能有多种路径,而每条路径很可能经过了若干中转站点,即该路径可能跨过了不同的几条轨道线路(无论走过哪条路径,从s点到t点的票价Q是固定的)。清分的目的便是要把Q合理地分配给从s到t所经过的各条线路的营运方,这是轨道交通营运必须解决的一个重要问题。的长度,就需要记录下持卡者此次旅程所经过的站点。这要求在各个换乘站点中增设大量的刷卡机。而这是难以实现的:(1)刷卡机是比较昂贵的硬件设备,增设刷卡机必然带来巨额的硬件投入。(2)在换乘轨道线路时刷卡,将使人流速度降低,在客流高峰期必将出现拥挤。(3)由于人流量很大,即便是只需要记
5、录进站和出站时两点的信息,数据库也需要占用很大存储空间。如果再加上换乘点的信息,则存储空间将成数量级的增加,这必然导致数据库维护备份复杂度的提高和清分数据源安全可靠性的降低。因此要求提出一种合理可行的方法。112路径近似算法设Pm是乘客选择第m短路径的概率,Wij表示以站点i为起点,j为终点所获得的收入。设Lij,1表示站点i到站点j的最短路径,这条路径经过了线段
6、S1S2
7、1,
8、S2S3
9、2,⋯,
10、SdSd+1
11、d(其中
12、SdSd+1
13、表示线段长度,下标表示相应线段所属的线路号分别为1,2,⋯,d)。于是这d条线路的所获权值分别为(
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的次次短路径⋯。每一条路径又可以为各自所经过1清分算法的提出和分析111精确算法精确算法是指从站点s到站点t,各条所经线路按各自在这次路途中所占的长度来分得票务收入。设第p张交通卡的编号为Np,Np号交通卡第q次使用的花费为Npq,第p张交通卡第q次使用所经过的总长度为Lpq,在第k条路线上通过的距离为Lpqk
21、,则第k条线路所获得的权值Vk的计算公式为nmNpqVk=∑∑Lpqk×(1)Lpqp=1q=1式中n表示卡的总数,m表示该卡总的使用次数。第k条线路的营运方应分得的收入InCk为VkInCk=All2Income×(2)t∑Vi的线路分得一个权值。第k条线路的权值V就是不同路径i=1k,1式中All2Income为轨道交通系统营运总收入,Vi为第i条线路的权值,t为总线路数。为了实现精确算法必须获得每一张卡在各条线路所走过下通过该线路所得的权值的总和:nnMV=∑∑∑
22、SS
23、PW/L()3ghkmijij,mk,1i=1j=1m=1式中
24、SgSh
25、
26、k为从站点i到站点j的第m短的路径中经过线路k上的总长度,M表示从站点i到站点j的所有路径数,n表示站点总数。易证在Pm
