公交查询系统报告资料

1、北京化工大学北方学院课程设计报告课程名称数据结构课程设计设计题目公交查询系统专业、班级软件工程0901学号090203018姓名高博指导教师周建敏老师设计时间2012年9月10日-2012年9月23日2012年 9 月 25 日一、引言（简要说明设计题目的目的、意义、内容、主要任务等）设计解决公交线路选择问题的自主查询计算机系统系统，其核心是线路选择的模型与算 法，特别是满足不同乘客的查询需求。而我，依据对公交乘客出行心理调查的统计结果，指出 换乘次数最少是乘客出行时考虑的首要因素，所以这里提出一种基于换乘次数最少的公交短 路径算法，并根据公交系统的特点，以图的邻接表作为数据结构。至于公交车的

2、调度，需要同时考虑到公车公司和乘客的利益，必须尽量在满足双方的利 益上做出合理的调度。所以这是一个多目标最优的问题，一是公车公司的成本低，即提高每 辆车的满载率，或者说发车的车次尽量少；二是等待时间过长的乘客所占的比例尽量少；三 是超载的情况尽量不发生，让乘客尽量感到舒适。关键词：公交路线网络化，图的邻接表，公交查询，乘客的需求，换乘次数，广度搜索，公 交调度，分时段调度，公交公司与乘客的利益关系公交的调度系统：公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城 市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。为了 建立一个有效的公交调度，我需要采集需要调

3、度的线路的相关数据。根据采集到的数据，我 的公交调度系统就可以为这条线路设计一个全天的公交调度方案。二、正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编程 原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正 文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严 谨，符合各学科、专业的有关要求。）1、1、设计解决公交线路选择问题的自主查询计算机系统系统，其核心是线路选择的模型与算 法，特别是满足不同乘客的查询需求。通常乘客选择出行路线时受到以下几个因素的作用：“换乘次数”、“出行距离”、“出 行耗时”、“出行费用”。换乘

4、次数是指乘客在完成一次出行过程中所换车的次数。实际上 这几个出行因素是相互影响的，如换乘次数和出行费用就是相关联的，特别是在一些实行一 票制的城市中，这两个因素可以说是一致的。根据早期的测试的结果发现的确如此，所用的 费用基本都是以换乘次数为界划分的。2、2、传统的Dijkstra算法无疑是解决一般最短路径问题的最优算法，但接下来我们会看到传统 的Dijkstra算法在公交查询系统是不适合的。依据对公交乘客出行心理调查的统计结果, 指出换乘次数最少是乘客出行时考虑的首要因素，所以这里提出一种基于换乘次数最少的公 交最短路径算法，并根据公交系统的特点，以图的邻接表作为数据结构。3、3、根据经验表

5、明,在北京这样的大都市的公交网络上,换3次车即乘坐4条线路的公交车,方 可到达目的地的情况都是很少发生的。所以本文认为两次以内的转车是比较合理的。换乘次数为2次及以下的情况中，会产生出行时间最小和费用最低等相应情形。有些乘 客可能有急事所以较为倾向时间最小，有些乘客因为经济上的考虑会选择费用最低，有些乘 客就会做出折中的选择。为满足各种乘客的需求，我提出了基于广度优先搜索，求解所有的 换乘次数为2次及以下的路线。并根据乘客的需求判断出最优选择。针对考虑公交的换乘情 况，主要算法描述如下。(1)输入乘车的起始站点A及目的站点B ;(2)求经过站点A的所有线路集S ( I)和经过站点B的所有线路集

6、T( J );(3)判断有S ( I) = T( J )吗？如果有，则找到了从站点A到站点B的直达线路S ( I)即1( J),输出结果,进行下一步。(4)求线路S ( I)上的站点E( I ,U)以及线路1( J)上的站点F( J ,V);(5)判断是否存在相同站点，即E( I ,U) = F( J ,V)。如果满足E( I ,U) = F( J ,V),则 线路S ( I) , T( J)即为一次转车的线路，E( I ,U)即为转车站点;输出结果。再执行下 面。(6)求经过E( I ,U)的线路集R ( K),经过F( J ,V)的线路集丫( O);(7)判断有R ( K) = Y( O)

7、吗？如果有，则线路S ( I) , R (K) , T( J)为两次换车的线路，换车站点为E( I ,U)和F(J,V), 输出结果。继续执行下面。(8)求线路R ( K)上的站点6( K ,W)和线路Y( O)上的站点L ( O , X);(9)判断是否存在相同站点，即G( K ,W) = L ( O , X)如果满足G( K ,W) = L ( O , X), 则线路 S ( I) , R (K) ,Y(O) ,T( J)即为三次转车的线路，E( I ,U) , G(K ,W) , F( J,V) 即为转车站点。公交调度：通过对分析我觉得公车的调度问题是一个双方利益兼顾的问题，乘客的利益是

8、超时等待 的比例尽量少和超载的情况尽量少发生，公交公司的利益则是满载率尽量高，以提高效益。 接下来我将这三个目标量化，化为目标函数，以得到最优调度。根据数据大家可以看出在一定的时段里乘客的人数有一定的相似性，这也比较容易理解， 因为大家上班的时间大都集中在8： 00-9： 00，下班时间也集中在16： 00-18： 00左右。所 以我以乘客的人数多少将公车的运行时间分为几个时段。一是早上平峰时段，二是早上高峰 时段，三是中午平峰时段，四是傍晚的高峰时段，五是晚上的平峰时段。这样我可以分别对 每一时段单独进行分析求解，使得问题简化。我只采用了上行的测试数据，下行同样可求。 下面是线路上行时段划分

9、。上行：15： 00-6： 0026： 00-9： 0039： 00-16： 00416： 00-18： 00518： 00-23： 00因为在我划分的一个时段里，情形都是相近的。每个乘客到达车站又是相互独立事件, 所以我可以认为在我划分的每个时间段里到达车站的乘客人数是均匀的。由于乘客到达的均 匀性，则一个时间段里发车也可以看成是均匀的。而总人数Pi除以时间段Ti的运力，就可以得到满载率的目标函数。下面我们先来求解上行路线。时间段i的平均发车时间间隔为：bi=Ti/Bi；第k辆车到达站点j时，站点j上的等待上车的人数PW(i，k，j)=Pl(i,k-1,j)+bi*Kij而设 Pl(i，0，

10、j)=0，当 k=1 时 PW(i，1，j)=二*Kij；第k辆车到达站点j时，下车人数D(i,k,j)=bi*-而D(i，k，0)=0，即起点站没人下车。第k辆车到达站点j时，车上乘客下车后车上的最大容量为：On(i,k,j)=Max 120-(PLB(i，k，j-1)-D(i，k，j)，0)；第k辆车离开站点j后车上的人数PLB(i,k,j)=PLB(i,k,j-1)-D(i,k,j)+max O(i,k,j)，PW(I,j,k) 第k辆车离开站点j后车上的超载人数C(i,k,j)=max PLB(i,k,j) 100，0)第k辆车离开站点j后，站点上还剩下的等待人数PL(i,k,j)=m

11、ax PA(i,j,k)- On(i,k,j)，0)时间段i车上的总人数Pi二”巳 PLB (i, k, j)第k辆车到达站点j时超额等待的乘客人数为平峰期：If (T(i，k，j)-10T(i,k-1,j W(i，k，j) =maxKij* (T (i，k，j)-10-T (i,k-1,j )， PL(i,k-1,j)高峰期：If (T (i, k, j) -5T (i,k-1,j) W (i, k, j) =maxKij* (T (i, k, j) -5-T (i,k-1,j), 数据及类型描述下面是公交查询里用到的数据和函数ElemType vtail,vhead;要查询的起点和终点，作

12、为全局变量bool ev600100,fv600100;eij为线路 i 会进入站点 j, fij为线路 i 会从 站点j出来struct ARcType弧结点：弧头在顶点数组中的序号，权值，指向下一条弧结点的指针struct VErtexType顶点结点：结点名字，指向第一条弧结点的指针class Graph公交线路图类VErtexType graph4100;存储公交线路图的邻接表VErtexType graph14100;公交线路图的逆邻接表int vertexnum,arcnum;顶点数和弧定点数int L550;记录线路i能经过几次换乘到达终点ElemType e600100,f60

13、0100;eij为线路 i 会进入站点 j, fij为线路 i会从站点j出来int en600,fn600;ei有多少个站点bool ticket550;/0为单一票制，1为分段计价bool round550;/是环形路为真，否则为假void initiate。；/初始化 en, fnvoid initiate2();ElemType r6000,y6000;/从 E( I ,U)站点发出的线路集 R ( K)，进入站点 F( J,V) 的线路集Y( O);int getdata();/从文件中读入数据int LocateVertex(ElemType str);/查找名为str的顶点在数组g

14、raph中的序号，返 回。没有返回-1int findpathout(ElemType s100,ElemType a);/求出经过站点 a 的所有线路名字， 复制到si中int findpathout(ElemType s100,ElemType a,ElemType hi);int findpathin(ElemType s100,ElemType );/求出经过站点 a 的所有线路名字，复 制到si中int CreateDN();/创建有向有权图的邻接表void Insertarc(int i,int j,ElemType linename,ElemType strh,ElemType

15、strt);/在图 中加入一条弧，由序号i的点指向序号j的点void Insertarc(int i,int j,ElemType &linename,ElemType strh,ElemType strt,char ch);void ShowUDN();显示图的领接表的结构int directpath(ElemType h100,ElemType t100,int counth,int countt);/ 否有直接路线int ispath(ElemType vhead,ElemType vtail,ElemType 反)；/判断 vhead 和 vtail 是 不是线路hi上的先后两点int

16、 oncepath(ElemType h100,ElemType t100,int counth,int countt);/看是否 有转一次车路线,即看线路i和j有没有公共的站点void oncepathtime(ElemType h100,ElemType t100,int counth,int countt);/ 看是否有转一次车路线,输出最小时间void oncepathsometime(ElemTypeh100,ElemTypet100,int counth,intcountt);/看是否有转一次车路线,输出最小时间int twiceandthreepath(ElemType h100

17、,ElemType t100,int counth0,int countt0,int counth1,int countt1);/看是否有转2次车路线，即看线路i和j有没有公共 的站点void twiceandthreepathtime(ElemType h100,ElemType t100,int counth0,int countt0,int counth1,int countt1);/看转两次车的最快时间void twiceandthreepathsometime(ElemType h100,ElemType t100,int counth0,int countt0,int counth

18、1,int countt1);/看转两次车的最快几次时间int num1(int fasttime5,int time,int count) /看 time 在 fasttime 数组中是第几 快的，返回数组中的序号，如果不能入前3快，返回-1，如果count没有3个，则前count 快。void names(ElemType s,int n)/给公交站点命名int checkarcname(ElemType str)/检查输入的弧名是否正确:L+三位数字”，正确就返回1， 否则0int changel(ElemType str)/将站点名转为相应的数字int change(ElemType

19、str)/将弧名转为相应的数字void namel(ElemType linename,int busline)/根据线路的号码给线路命名void Showall()/显示所有线路的情况GRaph net;/全局变量，存储站点信息下面是公交调度的相关数据和函数描述：int B6;/Bi,时间段Ti内发出的车辆数float b6;/时间段i的平均发车时间间隔为float PL69020;/PL（i，k，j）时间段i内第k辆车离开第j个站点时，站点j上的 人数float PW69020;/PW (i, k, j)时间段Ti内第k辆车到达站点j时，站点j的等待 上车人数float C69020;/时

20、间段i第k辆车离开站点j时的超载人数float K620;/时间段i内单位时间平均到站j的人数float L620;/时间段i内单位时间平均在站j下车的人数float T6;/时间段i的长度int start6;/5个时段的开始时刻float t14;/起点到各个站点的时间float D69020;/D(i,k,j)，时间段Ti内第k辆车到达站点j时，下车的人数float On69020;/On(i,k,j)，时间段Ti内第k辆车到达站点j时，乘客下车后，车 能容纳上车的最大人数float PLB69020;/PLB(i，k，j)时间段i内第k辆车离开第j个站点时，车上的人 数float W6

21、9020;/时间段Ti内第k辆车到达站点j时，等待时间过长的乘客float w6,c6,z6;/记录各个目标函数的数值。int b1;/全局变量，要调度的线路的站点数void initiate1()/划分各个时段int change(int n)/看开始时间n是第几时段int larger(int a,int b)/比较，返回大数int less(int a,int b)/比较，返回小数void getdata()/从要调度的线路读出文件,并初始化相关数据void findbestBi(int i,int b1)/求时段 i 最佳发车数数量Biint cusmenu()/乘客菜单函数int g

22、uanli()/管理员菜单测试方法描述(1)输入密码进入管理员菜单，进行相关操作，先是初始化公交查询系统。乘客菜单X结束程序,直看某玷点为出入站情投。1:看看所有浅珞 日于线路过冬一开始会出现闵庠的 根据采集的嵯躇的数据灯该线瞬冲行会车的调度1返回主菜单.（3）查看所有线路的情况。由于数据太多，近500多条线路，所以一开始会出现类似闪屏的情况。运行过程如下。（2）然后测试函数：查看某站点的出入站的线路的情况co F: 数据结构,数据结构大作业buwDcbugbus. exer5 -F乘客菜单X结束程序,直看某玷点为出入站情投。1:看看所有浅珞 日于线路过冬一开始会出现闵庠的 根据采集的嵯躇的数

23、据灯该线瞬冲行会车的调度1返回主菜单.（3）查看所有线路的情况。由于数据太多，近500多条线路，所以一开始会出现类似闪屏的情况。运行过程如下。（2）然后测试函数：查看某站点的出入站的线路的情况co F: 数据结构,数据结构大作业buwDcbugbus. exer5 -F二 数抠结构、歙据结构大作业lmnDcbugtniM. eien ： 1公交查狗系统成功。b:查看某站点的出入站情况。3;查看所有线路（由于线路过多一开始会出现闪屏儿卜：根据采集的线路的数据对该线路进行公车的调度快返回主菜单。二富蟹菜单E1459-L271D82062if入站点名：S1459E1459-L271US1461E14

24、59-L244DS2062K1459-L244U 81143怅入站点后145痴线路情况为:K1461-L271D81459E2062-L271U 81459E1143-L244DS1459E2062-L244U81459输人管理员密码Hl）： 111管理反菜单1初始化公.爻查询下院E-丁 I s - 一行0-行3苴一一叫T157E-丁 I s - 一行0-行3苴一一叫T157497 甘LT 45 141210 8 3 fl- 7 3 7 2 2 .283 ZMr s s Jt 7 1: s IIM或IT仃u段行行 3分-宝IL5介二”、L513lui ”这个文件）o超载的乘客比例为0.0957

25、341团716921,等待超时乘客比例为.261883,超载的乘客比例为0刃467687时间段5： 18：豳-23： M最佳调度为：每间隔17.6471分钟发一班车0.89704,等待超时乘客比例为.000917203,超载的乘客比例为0lui ”这个文件）o超载的乘客比例为0.0957341团716921,等待超时乘客比例为.261883,超载的乘客比例为0刃467687时间段5： 18：豳-23： M最佳调度为：每间隔17.6471分钟发一班车0.89704,等待超时乘客比例为.000917203,超载的乘客比例为0.0711743时间段4： 16：股-18：网最佳调度为：每间隔3.769

26、2分钟发一班车即同段,：，：孙16：吗隼佳调度为:每间隔5.83333分钟发一班车霜窑露饕飘墙 厚待超时乘客比例为.0753063,超载的乘客比例为四.0189075时回段? ： 6 ： 00-9 ： 00,霜褊鹦明蕊乩,等待超时乘客比例为,000408816,超载的乘客比例为0.0594357鹊度为:每间隔2. M897分钟发一班车（5）接下来进入乘客菜单，先输入乘客想查询的起点和终点。CA7：敦据结构数据结构大作业11式。611/113.6屋日回in an:公工件1:闻酒 择入111文段时的 选输an!辆 请请1X1根翳车亡 1#若阳 -Fn 才可有 只 前 目4次口后调为麻交度.辅出赛5

27、5管取测78以0,预98可:0关0.据-6%数眄的率的5:暮露需鹦霜熟嚼桨1鹦露露器-,，总直达或只转一次中的路编“京换乘:多次为路线b提供凡品时可较超号路。向返回主菜单.b，总直达或只转一次中的路编“京换乘:多次为路线:豆的线路,，总直达或只转一次中的路编“京换乘:多次为路线b提供凡品时可较超号路。向返回主菜单.b，总直达或只转一次中的路编“京换乘:多次为路线:豆的线路脚人起点:SB864输入终点:1341拿客选择菜聿卜输入起点和终点.(6)然后大多数乘客为了舒适性会选择查询直达或只转一次车的路线，结果如下，可惜这 两个站点没有直达路线，系统会作出提醒。 为为线路。路的线线线车 为为线路。路

28、的线线线车2的踣的次n:车达车一囊直次转选需有一有请不认食仅卜乘客选择菜单输入起点和终点。卜求直达或只转一次车的路线。,求换乘多次的路线。卜求时间最短的线路。卜提供几条时间较短线路。k返回主菜单.转多次车的所有线路为: (7)然后乘客可以选择查看需要换乘多次的所有路线，结果如下。105 F： Sfc无结构速据结构大作业以Debugbus. exeh提供凡圣时间较短线路.忸返回主荣单.慢选择n二特多次丰的所.有线路大：SUtlb4-L373D-S3ijV-L27U-S32?5-L50?-SlJ41 SKItlb4-?LJ73D-SJB5y-LliB7U-S32V5-?LUBy-SlJ41 S30

29、64-L373D-S0063-L287U-S329E-L509-S1341 S0064-L373D-S0063-L287U-S3295-L089-S1341 S3064-L373D-S3618-L287U-S329E-L509-S1341 S0064-L373D-S3618-L287U-S3295-L089-S1341 S3064-L373D-S3607-L287U-S3295-L509-S1341 S0064-L373D-S3607-L287U-S329E-L089-S1341 RHflA4-T73D-R41R-L2fl7ll-R39R-LSR9-R141 RW(J|f；4-L371D-R4

30、10-L2n7ll-S339-LnS9-S1 41 G0064-L373D-E264S-L287U-G329E-L509-S1341 E00G4-L273D-E2t4e-L287U-S329E-L0e9-Gia41 S30G4-L3?3D-E3465 L015U G1S31 L50?-S1J41 S0BG4-L373D-S3465 LB15U 31031 L08?-S1J41 S0e64-L282D-S3293-L468U-S3295-L507-S1341 S0e64-L282D-S3293-L468U-S1831-L50?-S1341听听工b.可可可.一日音=日司司.司司司可可可司 特多次丰

31、的所.有线路大：SUtlb4-L373D-S3ijV-L27U-S32?5-L50?-SlJ41 SKItlb4-?LJ73D-SJB5y-LliB7U-S32V5-?LUBy-SlJ41 S3064-L373D-S0063-L287U-S329E-L509-S1341 S0064-L373D-S0063-L287U-S3295-L089-S1341 S3064-L373D-S3618-L287U-S329E-L509-S1341 S0064-L373D-S3618-L287U-S3295-L089-S1341 S3064-L373D-S3607-L287U-S3295-L509-S1341

32、S0064-L373D-S3607-L287U-S329E-L089-S1341 RHflA4-T73D-R41R-L2fl7ll-R39R-LSR9-R141 RW(J|f；4-L371D-R410-L2n7ll-S339-LnS9-S1 41 G0064-L373D-E264S-L287U-G329E-L509-S1341 E00G4-L273D-E2t4e-L287U-S329E-L0e9-Gia41 S30G4-L3?3D-E3465 L015U G1S31 L50?-S1J41 S0BG4-L373D-S3465 LB15U 31031 L08?-S1J41 S0e64-L282D-S3293-L468U-S3295-L50