1、1、 课程设计的主要内容通常乘客选择出行路线时受到以下几个因素的作用:“换乘次数”、“出行距离”、“出行耗时”、“出行费用”。换乘次数是指乘客在完成一次出行过程中所换车的次数。实际上这几个出行因素是相互影响的,如换乘次数和出行费用就是相关联的,特别是在一些实行一票制的城市中,这两个因素可以说是一致的。根据早期的测试的结果发现的确如此，所用的费用基本都是以换乘次数为界划分的。2、 测试方法描述 传统的Dijkstra 算法无疑是解决一般最短路径问题的最优算法，但接下来我们会看到传统的Dijkstra 算法在公交查询系统是不适合的。依据对公交乘客出行心理调查的统计结果,指出换乘次数最少是乘客出行时
2、考虑的首要因素，所以这里提出一种基于换乘次数最少的公交最短路径算法，并根据公交系统的特点，以图的邻接表作为数据结构。3、 编译原理数据分析根据经验表明,在北京这样的大都市的公交网络上,换3次车即乘坐4条线路的公交车,方可到达目的地的情况都是很少发生的。所以本文认为两次以内的转车是比较合理的。换乘次数为2次及以下的情况中，会产生出行时间最小和费用最低等相应情形。有些乘客可能有急事所以较为倾向时间最小，有些乘客因为经济上的考虑会选择费用最低，有些乘客就会做出折中的选择。为满足各种乘客的需求，我提出了基于广度优先搜索，求解所有的换乘次数为2次及以下的路线。并根据乘客的需求判断出最优选择。针对考虑公交
3、的换乘情况，主要算法描述如下。（1） 输入乘车的起始站点A 及目的站点B ;（2） 求经过站点A 的所有线路集S （ I） 和经过站点B 的所有线路集T（ J ） ;（3） 判断有S （ I） = T（ J ） 吗?如果有,则找到了从站点A 到站点B 的直达线路S （ I） 即T（ J） ,输出结果,进行下一步。（4） 求线路S （ I） 上的站点E（ I ,U） 以及线路T（ J） 上的站点F（ J ,V） ;（5） 判断是否存在相同站点,即E（ I ,U） = F（ J ,V） 。如果满足E（ I ,U） = F（ J ,V） ,则线路S （ I） , T（ J） 即为一次转车的线路, E
4、（ I ,U） 即为转车站点;输出结果。再执行下面。（6） 求经过E（ I ,U） 的线路集R （ K） ,经过F（ J ,V） 的线路集Y（ O） ; （7） 判断有R （ K） = Y（ O） 吗?如果有,则线路S （ I） , R （ K） , T（ J ） 为两次换车的线路,换车站点为E（ I ,U） 和F（ J ,V） ,输出结果。继续执行下面。（8） 求线路R （ K） 上的站点G（ K ,W） 和线路Y（ O） 上的站点L （ O , X） ;（9） 判断是否存在相同站点,即G（ K ,W） = L （ O , X） ,如果满足G（ K ,W） = L （ O , X） , 则线
5、路S （ I） , R （ K） ,Y（ O） ,T（ J ） 即为三次转车的线路, E（ I ,U） , G（ K ,W） , F（ J ,V） 即为转车站点。公交调度：通过对分析我觉得公车的调度问题是一个双方利益兼顾的问题，乘客的利益是超时等待的比例尽量少和超载的情况尽量少发生，公交公司的利益则是满载率尽量高，以提高效益。接下来我将这三个目标量化，化为目标函数，以得到最优调度。根据数据大家可以看出在一定的时段里乘客的人数有一定的相似性，这也比较容易理解，因为大家上班的时间大都集中在8：00-9：00，下班时间也集中在16：00-18：00左右。所以我以乘客的人数多少将公车的运行时间分为几个
6、时段。一是早上平峰时段，二是早上高峰时段，三是中午平峰时段，四是傍晚的高峰时段，五是晚上的平峰时段。这样我可以分别对每一时段单独进行分析求解，使得问题简化。我只采用了上行的测试数据，下行同样可求。下面是线路上行时段划分。上行：15：00-6：0026：39：00-16：416：518：00-23： 因为在我划分的一个时段里，情形都是相近的。每个乘客到达车站又是相互独立事件，所以我可以认为在我划分的每个时间段里到达车站的乘客人数是均匀的。由于乘客到达的均匀性，则一个时间段里发车也可以看成是均匀的 。而总人数Pi除以时间段Ti的运力，就可以得到满载率的目标函数。下面我们先来求解上行路线。时间段i的
7、平均发车时间间隔为：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*而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辆车离开
8、站点j后车上的超载人数C（i,k,j）=max PLB（i,k,j）100，0第k辆车离开站点j后，站点上还剩下的等待人数PL（i,k,j）=max PA（i,j,k）- On（i,k,j），0时间段i车上的总人数Pi=第k辆车到达站点j时超额等待的乘客人数为平峰期：If（T（i，k，j）-10T（i,k-1,j）W（i，k，j）=max Kij*（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）=max Kij*（T（i，k，j）-5- T（i,k-1,j），数据及类型描述下面是公交查询里用到的数据和
9、函数ElemType vtail,vhead;/要查询的起点和终点，作为全局变量bool ev600100,fv600100;/eij为线路i会进入站点j，fij为线路i会从站点j出来struct ARcType/弧结点：弧头在顶点数组中的序号，权值，指向下一条弧结点的指针struct VErtexType/顶点结点：结点名字，指向第一条弧结点的指针class Graph/公交线路图类 VErtexType graph4100;/存储公交线路图的邻接表 VErtexType graph14100;/公交线路图的逆邻接表 int vertexnum,arcnum;/顶点数和弧定点数 int L5
10、50;/记录线路i能经过几次换乘到达终点 ElemType e600100,f600100; int en600,fn600;/ei有多少个站点 bool ticket550;/0为单一票制，1为分段计价 bool round550;/是环形路为真,否则为假 void initiate（）;/初始化en，fn void initiate2（）; ElemType r6000,y6000;/从E（ I ,U）站点发出 的线路集R （ K） ,进入站点F（ J ,V） 的线路集Y（ O） ; int getdata（）;/从文件中读入数据 int LocateVertex（ElemType str
11、）;/查找名为str的顶点在数组graph中的序号，返回。没有返回-1 int findpathout（ElemType s100,ElemType a）;/求出经过站点a的所有线路名字,复制到si中 int findpathout（ElemType s100,ElemType a,ElemType hi）; int findpathin（ElemType s100,ElemType a）; int CreateDN（）;/创建有向有权图的邻接表void Insertarc（int i,int j,ElemType linename,ElemType strh,ElemType strt）;/
12、在图中加入一条弧，由序号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 hi）;/判断vhead和vtail是不是线路hi上的先后两点 int once
13、path（ElemType h100,ElemType t100,int counth,int countt）;/看是否有转一次车路线,即看线路i和j有没有公共的站点 void oncepathtime（ElemType h100,ElemType t100,int counth,int countt）;/看是否有转一次车路线,输出最小时间 void oncepathsometime（ElemType h100,ElemType t100,int counth,int countt）; int twiceandthreepath（ElemType h100,ElemType t100,int
14、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 counth1,int countt1）;/看转
15、两次车的最快几次时间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 str）/将弧名转为相应的数字void namel（
16、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;/时间段i第k辆车离开站点j时的超载人数float K620;/时
17、间段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 W69020;/时间段Ti内第k辆车到达站点j时，等待时间过长的乘客f
18、loat 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 guanli（）/管理员菜单测试方法描述（1）输入密码进入管理员菜单，进
19、行相关操作，先是初始化公交查询系统。（2）然后测试函数：查看某站点的出入站的线路的情况（3）查看所有线路的情况。由于数据太多，近500多条线路，所以一开始会出现类似闪屏的情况。运行过程如下。（4）接着是根据文件的数据进行公交车的调度。可以将每个线路的具体情况放在不同的文件中，这样就可以对不同的线路进行调度和相关数据预测。由于时间关系这里我只存储了xianlu1这一个文件。测试结果如下。（5）接下来进入乘客菜单，先输入乘客想查询的起点和终点。（6）然后大多数乘客为了舒适性会选择查询直达或只转一次车的路线，结果如下，可惜这两个站点没有直达路线，系统会作出提醒。（7）然后乘客可以选择查看需要换乘多次
20、的所有路线，结果如下。（8）如果乘客赶时间，想找时间最快的路线：（9） 如果此时乘客担心时间最快的路线人数太多，会拥挤，可以选择查看几条最快线路三、结论（应当准确、完整、明确精练；也可以在结论或讨论中提出建议、设想、尚待解决问题等。首先我分析公交线路的特点，将公交系统化为多重带权图，并采用邻接表进行存储。在设计公交查询系统时，我从实际出发，参考了报纸等媒体对乘客出行的心里需求的分析，满足乘客希望的换乘次数较少，时间较快等个性化需求，甚至考虑到一些特殊下的特殊需求，比如一些用户因为某些特殊原因可能想途中经过某个站，或者不想经过某个站，这样乘客就可以选择查看所有线路；再或者某项大型比赛，集会结束后，如果大家都想走最优路线会造成线路拥挤，所以提出了多条最快路线让用户选择。在设计公交调度系统时，我为之建立了数学模型，分析各个时间的乘客人数变化，求出各个时间的公交发车间隔，和预测了相关数据。四、参考文献1：王建林 ，基于换乘次数最少的城市公交网络最优路径算法 ，经济地理 2005-92：严蔚敏,吴伟民. 数据结构M . 北京:清华大学出版社3、c语言编程常见问题，清华大学出版社 1996年12月4、姜仲秋等主编，C语言程序设计，南京大学出版社，1998年1月五、 指导教师评语 签名： 年 月 日课程设计成绩（五级分制）
