公交查询系统报告资料

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

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

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

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

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

6、B的直达线路S(I)(4)求线路S(I)上的站点E(I,U)以及线路T(J)判断是否存在相同站点，即E(I,U)=F(J,V)线路S(I),T(J)即为一次转车的线路，E(I,U)面。(6)求经过E(I,U)的线路集R(K),判断有R(K)=Y(O)吗？如果有，则线路S(I),R(K),T(J)输出结果。继续执行下面。(8)求线路R(K)上的站点G(K,W)经过F(J,V)的所有线路集T(J);即T(J),输出结果，进行下一步。上的站点F(J,V);。如果满足E(I,U)=F(J,V),则即为转车站点；输出结果。再执行下的线路集Y(O);为两次换车的线路，换车站点为E(I,U)和5(J,V),

7、和线路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：00-9:00,下班

8、时间也集中在16:00-18:00左右。所以我以乘客的人数多少将公车的运行时间分为几个时段。一是早上平峰时段，二是早上高峰时段，三是中午平峰时段，四是傍晚的高峰时段，五是晚上的平峰时段。这样我可以分别对每一时段单独进行分析求解，使得问题简化。我只采用了上行的测试数据，下行同样可求。下面是线路上行时段划分。上行:15:00-6:0026:00-9:0039:00-16:00416:00-18:00518:00-23:00因为在我划分的一个时段里，情形都是相近的。每个乘客到达车站又是相互独立事件,所以我可以认为在我划分的每个时间段里到达车站的乘客人数是均匀的。由于乘客到达的均匀性，则一个时间段里发

9、车也可以看成是均匀的。而总人数Pi除以时间段Ti的运力，就可以得到满载率的目标函数。下面我们先来求解上行路线。时间段i的平均发车时间间隔为：bi=Ti/Bi;第k辆车到达站点j时，站点j上的等待上车的人数PW(i,k,j)=Pl(i,k-1,j)+bi*Kij而设Pl(i,0,j)=0,当k=1时PW(i,1,j)、*Kij;第k辆车到达站点j时，下车人数D(i,k,j)=bi*JiI而D(i,k,0)=0,即起点站没人下车。第k辆车到达站点j时，车上乘客下车后车上的最大容量为：On(i,k,j)=Max120-(PLB(i,k,j-1)-D(i,k,j),0;第k辆车离开站点j后车上的人数P

10、LB(i,k,j)=PLB(i,k,j-1)-D(i,k,j)+maxO(i,k,j),PW(I,j,k)第k辆车离开站点j后车上的超载人数C(i,k,j)=maxPLB(i,k,j)-100,0第k辆车离开站点j后，站点上还剩下的等待人数PL(i,k,j)=maxPA(i,j,k)-On(i,k,j),0时间段i车上的总人数Y黑印第k辆车到达站点j时超额等待的乘客人数为平峰期：If(T(i,k,j)-10>T(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)-5>T(i,k-1,j

11、)W(i,k,j)=maxKij*(T(i,k,j)-5-T(i,k-1,j),数据及类型描述下面是公交查询里用到的数据和函数ElemTypevtail,vhead;/要查询的起点和终点，作为全局变量boolev600100,fv600100;/eij为线路i会进入站点j,fij为线路i会从站点j出来structARcType/弧结点：弧头在顶点数组中的序号，权值，指向下一条弧结点的指针structVErtexType/顶点结点：结点名字，指向第一条弧结点的指针classGraph/公交线路图类VErtexTypegraph4100;存储公交线路图的邻接表VErtexTypegraph1410

12、0;/公交线路图的逆邻接表intvertexnum,arcnum;/顶点数和弧定点数intL550;/记录线路i能经过几次换乘到达终点ElemTypee600100,f600100;/eij为线路i会进入站点j,fij为线路i会从站点j出来inten600,fn600;/ei有多少个站点boolticket550;/0为单一票制，1为分段计价boolround550;/是环形路为真，否则为假voidinitiate。;/初始化en,fnvoidinitiate2();ElemTyper6000,y6000;/从E(I,U)站点发出的线路集R(K),进入立点F(J,V)的线路集Y(O);intg

13、etdata();/从文件中读入数据intLocateVertex(ElemTypestr);/查找名为str的顶点在数组graph中的序号，返回。没有返回-1intfindpathout(ElemTypes100,ElemTypea);/求出经过站点a的所有线路名字，复制到si中intfindpathout(ElemTypes100,ElemTypea,ElemTypehi);intfindpathin(ElemTypes100,ElemTypea);/求出经过站点a的所有线路名字，复制到si中intCreateDN();/创建有向有权图的邻接表voidInsertarc(inti,intj

14、,ElemTypelinename,ElemTypestrh,ElemTypestrt);/在图中加入一条弧，由序号i的点指向序号j的点voidInsertarc(inti,intj,ElemType&linename,ElemTypestrh,ElemTypestrt,charch);voidShowUDN();/显示图的领接表的结构intdirectpath(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有直接路线intispath(ElemTypevhead,ElemTypevtail,ElemTypehi);/判断vhea

15、d和vtail是不是线路hi上的先后两点intoncepath(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有转一次车路线，即看线路i和j有没有公共的站点voidoncepathtime(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有转一次车路线，输出最小时间voidoncepathsometime(ElemTypeh100,ElemTypet100,intcounth,intcountt);/看是否有转一次车路线，输出最小时间inttwiceandthreepath(ElemT

16、ypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1);/看是否有转2次车路线，即看线路i和j有没有公共的站点voidtwiceandthreepathtime(ElemTypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1);/看转两次车的最快时间voidtwiceandthreepathsometime(ElemTypeh100,ElemTypet100,intcounth0,intcountt0,intcounth1,intcountt1

17、);/看转两次车的最快几次时间intnum1(intfasttime5,inttime,intcount)看time在fasttime数组中是第几快的，返回数组中的序号，如果不能入前3快，返回-1,如果count没有3个，则前count快。voidnames(ElemTypes,intn)/给公交站点命名intcheckarcname(ElemTypestr)/检查输入的弧名是否正确："L+三位数字"，正确就返回1,否则0intchangel(ElemTypestr)/将站点名转为相应的数字intchange(ElemTypestr)/将弧名转为相应的数字voidnamel

18、(ElemTypelinename,intbusline)/根据线路的号码给线路命名voidShowall()/显示所有线路的情况GRaphnet;/全局变量，存储站点信息下面是公交调度的相关数据和函数描述：intB6;/Bi,时间段Ti内发出的车辆数floatb6;/时间段i的平均发车时间间隔为floatPL69020;/PL(i,k,j)时间段i内第k辆车离开第j个站点时，站点j上的人数floatPW69020;/PW(i,k,j)时间段Ti内第k辆车到达站点j时，站点j的等待上车人数floatC69020;/时间段i第k辆车离开站点j时的超载人数floatK620;/时间段i内单位时间平

19、均到站j的人数floatL620;/时间段i内单位时间平均在站j下车的人数floatT6;/时间段i的长度intstart6;/5个时段的开始时刻floatt14;/起点到各个站点的时间floatD69020;/D(i,k,j),时间段Ti内第k辆车到达站点j时，下车的人数floatOn69020;/On(i,k,j),时间段Ti内第k辆车到达站点j时，乘客下车后，车能容纳上车的最大人数floatPLB69020;/PLB(i,k,j)时间段i内第k辆车离开第j个站点时，车上的人floatW69020;/时间段Ti内第k辆车到达站点j时，等待时间过长的乘客floatw6,c6,z6;/记录各个

20、目标函数的数值。intb1;/全局变量，要调度的线路的站点数voidinitiate1()/划分各个时段intchange(intn)/看开始时间n是第几时段intlarger(inta,intb)/比较，返回大数intless(inta,intb)/比较，返回小数voidgetdata()/从要调度的线路读出文件，并初始化相关数据voidfindbestBi(inti,intb1)/求时段i最佳发车数数量Biintcusmenu()/乘客菜单函数intguanli()/管理员菜单测试方法描述(1)输入密码进入管理员菜单，进行相关操作，先是初始化公交查询系统。(2)然后测试函数：查看某站点的出

21、入站的线路的情况(3)查看所有线路的情况。由于数据太多，近500多条线路，所以一开始会出现类似闪屏的情况。运行过程如下。匕：，F门教据结杓、融据结构大作业UuCDMusMju-me*什：S277B-S1717-S0404-S005-S3B78-S3443-SB9e4-S2354-SB907-S25Bl-S3757-S294B-SlJi；S2890-S2778-S2353-S3947-S2567-S3740-S3718-S1747-S2302行；S2302-S3718-S3740-S2967-S347-S2353-S2778-S2890rb_£1&-T_u3-£-79

22、g29g1,2-2611W3s9£2is一TiJJ。w;?=彳0<10Vr-£3749-Si465一StmifiG-S154-S22S-S11R9-E2RO1-S241-S17R4-S17R3-K1671-K2(4)接着是根据文件的数据进行公交车的调度。可以将每个线路的具体情况放在不同的文件中，这样就可以对不同的线路进行调度和相关数据预测。由于时间关系这里我只存储了xianlul这一个文件。测试结果如下。c：v"F:、数据结构、数据结构大作业.eze请选择n：4请输入公交调度所需数据所在的文件名(目前只有“xianlul”这个文件).xianlul根据文件的

23、数据可以膏出公交调度及相关数据如下：时段1：5:00-6：00,最崔通度为:每间隔12分钟发一班车军瓶礴者薮翦滕;盥U择待超时乘客比例为自.148063,超载的乘客比例为0.09573412:6:00-9:00度为:每间隔2.酩897分钟发一班车0.886415,等待超时乘客比例为目.眄自4幽816,超载的乘客比例为目.晒943H73：9：眄-16：股,最佳调度为:每间隔H.83333分钟发一班车筌勰霹鬻建曹香0.755558,等待超时乘客比例为目.0753063,超载的乘客比例为0.0189075时间段4：16：醴-18：皿,最佳调度为:每间隔3.07692分钟发一班车褊履鬻H翳嚼0.897

24、04,等待超时乘客比例为0加眄9172回3,超载的乘客比例为0.0711743时间段5：18：醴-23：皿,最佳调度为:每间隔17.6471分钟发一班车善履器鳗熟癖0.716921,等待超时乘客比例为目.261883,超载的乘客比例为0.0467687Ld(5)接下来进入乘客菜单，先输入乘客想查询的起点和终点。F门裁祖结构、救撮结构大作业tbu曲Dguet)U3.¥ZC输入起点和终点."季直达或只转一次车的路练0,求换乘多次的路线口"求时间最短的线路.卜提供几条村间狡麴号路口"返回主菜单.展择施八起点：M呢64疑入缘点：鼻341F-乘客选择菜单，：输起点

25、和终点*卜=苹直达我只转一次车的路线中卜式换乘多次的路线.卜玄时间最短的线路“(6)然后大多数乘客为了舒适性会选择查询直达或只转一次车的路线，结果如下，可惜这两个站点没有直达路线，系统会作出提醒。口|冥gF:数据结构,数据结构大作业bu£Debugbu3.exeH：返回王菜单.线线线车2的路的次n:车达车一直次转选需有一有请不小售仅为线。路的乘客选择菜单U输入起点和终点。2：求直达或只转一次车的路线。3：求换乘多次的路线。4：求时间最短的线路。5：提供几条时间较短线路。H：返回主菜单.请选择居多次车在所有线路为:(7)然后乘客可以选择查看需要换乘多次的所有路线，结果如下。10八FC数

26、抠结杓、救据结构大作业UrtinDeLug'lm#.eze卜提供几条时同较期线路。L返回主菜单.dd33333333333333以加那斯死缸泳湖知初知知知知他用月月±21;目,H-R-月月月月月月月月费将费S串2a，«，呼*#*，S2525252524707736363636364712144111iLILIil-l'll'ilL知力对尢尢为"五步为为也为知尢fe叫叫日.一日iT5"T£-Bl印可TrEE-fJttarrrrrrrFrFrbX卜选择n二信多次半的所有线路为：SSWb-1->L37JD->S38

27、b?->L2B7U->Sd2Vb->LSBV->SlJ41KWWfc4->L37dD->S38b9->L2B7U->S329S->LU89->S1341S006->L373D->S0063->L287U->S3295->L509->S1341S0064->L373D->S0063->L287U->S3295->LB89->S1341E006->L373D->S3618->L287U->S3295->L509->S1341E006

28、4->L373D->S3&18->L287U->S3295->LB89->S1341E0064-JL373D->S3607->L287U->S3295->L509->S1341E0064-JL373D->S36e7->L287U->S3295->L089->S134173D->S3410->L2*7II->S329S->LS->S1341卜4-7LW73D->E141B->L2*7II->K3295-M.HS9->S1341卜130t72

29、D->C2G<49->L2S7U->S229E->L509->S1341E006d->L373D->S2&<ie->L287U->E329E->L09?->G1341丽的4>L373D->G3ie5->Lei&U->Gie31->LS0V->G1341>13?5»>3305->1015(|->51©31-007->81341BB064->L28ZD->S3293->L468U->S3295-?L509->S1341S306->L202D-?S3273->L468U->S1B31->L50?->S134J(8)如果乘客赶时间，想找时间最快的路线:c：vF:、数据结构、数据结构大作业bu3Dcbugbug.eze5：提供几条时间较短线路。：返回主菜单.请选择n：4周乘次数为2次以内的最快路线为：S0064->L373D->S3405->L015U->S1831->L509->S1341所用时间为：117.费用为：3乘客选择菜单U输入起点和终点。2：求直达或只转一次车的路线。3：求换乘多次的路线。4：求时间最短