乘公交看奥运g.doc

乘公交，看奥运叶树军，蒙宇明，郭 米指导教师 吴寿章摘要：本案例按照给出的北京公交线路，建立公交线路的最佳选择模型与算法。线路选择对不同的人又不同的选择方法.问题一仅考虑公汽线路，建立一般的数学模型和算法来给出任意两公汽站点间的最佳线路。通过心理学和调查表明，乘公交时换乘次数是人们的第一选择，其次是出行距离、出行费用、出行时间等因素。本模型基于最小换乘的原则，用广度优先的搜索算法实现公交选择策略，采用集合的逐步向外扩展和两个集合之间逐渐逼近的搜索方法，从而来寻找一条合理的路径，使得公交乘客的换乘次数最少。编写STL算法，运行程序得到问题要求的6种最佳选择路线。问题二在问题一的基础上加进了地铁线路，算法和问题一的基本一致，只是选择的路径多了一些。结果只有5、6组线路和第一问不同。问题三中给出了所有站点之间的步行时间，这就不得不考虑步行方式对线路选择的影响。具体地说，人们在转车时，并不是只在下车的站点处转车，有时需要步行一小段距离到附近的站点转车。在基于问题一、二的基础上，人们换乘往往会出现几种情况，怎样在这些因素中寻找最佳的换乘方式，又知道各相邻 站点的平均耗时，故我们可以用层次分析法找出比较优化的公交类型，然后利用规划理论找到较佳的换乘方式，并用罚函数进行验证，这样就完成了问题三的模型的建立。关键词: 最优路径；公交系统；最少换乘算法；层次分析法；罚函数；规划理论1 基本假设1在问题一和问题二中，假设乘客在下车站点后直接在下车的站点处转车，而不考虑乘客步行到领近的站点去转车；2所有公汽的行驶速度一样，所有地铁的行驶速度也一样；3所有公交路段的交通都是通畅的，不存在交通拥挤问题；4假设所有的乘客都能乘上第一辆达到的公交车；5. 假设本文中的乘客不考虑乘坐公交路途中的风景状况的因素；2 问题分析问题一的分析：假设乘客在下车站点后直接在下车的站点出转车，而不考虑乘客步行到领近的站点去转车。根据人们的出行习惯，在选择从A站点到B站的行车路线的时候，首先会先看经过A站的车是否有直接到B站的，如果有，则会优先选择直达车，如果存在不止一条的直达线路的时候，在考虑距离、时间、费用等综合因素的乘车方案；如果没有直达车，就会考虑第一次换车的乘车方案：即通过A站点的车与经过B站点的车有公共车点C没有？如果有，则可以在公共站点C处转车；如果没有则又要考虑二次换乘的乘车方案，即乘坐经过A站点的车到某一站点C下车，在经过C站点的车与经过B站点的车是否有公共站点D，如果有就在D转车，两次转车可到达B；如果还没有，则需要三次换乘或三次以上才可以到达目的地。 上述情况中存在不止一种的选择方案，则再考虑选择综合因素最高的作为优先的乘车方案。问题二的分析：问题二比问题一多考虑了地铁，这使求解的情况变得更为复杂，也将产生更多的乘车方案供我们选择。一个地铁站同时与N个公交车车站相交。这样，当我们搜索交点时，在地铁上面要复杂些。不但要区别T1、T2的行进方式（一个往返，一个环行），还要遍历每个汽车站才行。特别是搜索地铁和公交、地铁和地铁的交点时，要有清晰的区分。问题三的分析：在没有考虑各站点的步行时间时，我们往往得到的结果不是最佳的，因为有可能乘客通过步行换乘到另一个站点乘车，这是及其可能的事情。既然给了步行时间就要和没给步行时间对比，因为一个乘客可能步行到另一个站点并且另一个站点怎样选择，另外也有可能呆在原站点等待下一车次的到来。总的来说应该分成下面四种情况A、无需步行，呆在原地等下一车次的到来B、下车之后马上步行乘上另一车次前行C、在两线路交叉点有公共站点，可以下车后马上换乘D、需要步行并在另一站点等车换乘根据以上分析，加上题目中给出的各个站点间的等车耗时，我们可以利用层次分析法和规划论建立模型。然后再根据费用最低，时间最少模型，综合分析模型进行分别考虑。3 模型的建立与求解3.1 问题一和问题二的算法与模型建立：该问题用线路模型描述为用一个网络无向图，来表示公交路线及站点分布情况，其中表示可能的换车点的集合，是边集合，即能通车的路段。现有P路车在正常运行，设路别单元 表示第路车行经的所有站点， 。令是所有公交路线的集合，那么，我们的问题是寻找一条最少换乘次数的路径，即搜索最少的路别单元个数来包括这个站点。对于上述问题的求解，本文把集合的思想和广度优先搜索方法结合，采用集合的逐步向外扩展和两集合之间逐渐逼近的搜索方法，在一个庞大的有向交通网络中，寻找一个最少换乘序列的路径。以下是基于该思想的最小换乘算法。（1）公交最小换乘搜索算法思想：步骤一： 输入乘车的起始站点A和目的站点B；步骤二：初始化数据，从给定的文本文件中读取公交车的车次、路线等相关数据，存入自定义的公交车结构体内；步骤三： 搜索公交线路的数据(520条公交车线路)，将经过起始站点A的公交线路存为(；为正整数);将经过目的地站点B的公交线路存为(；为正整数)；步骤四：判断是否有=，如果有，将满足条件的线路存入集合中；若个数1,则公交线路，即为从站点A到站点B的直达最优线路，输出结果并结束运算；如果没有，则继续往下运行；步骤五：搜索公交线路的数据，将公交路线所包含的公交站点（如S3915、S3934等S开头的站点）存为公交换乘矩阵(；为正整数)，公交线路所包含的站点存为公交换乘矩阵；(；为正整数)步骤六：判断是否有=，实际上就是判断两条公交线路、有没有共同的站点，有共同的站点就说明乘客可以在该站点换乘其他车次的公交车。将满足条件的存入W，若W的个数1，则站点即为从站点A到站点B的一次换乘站点，公交线路、为换乘一次的可选路线，输出结果并结束运算；步骤七： 搜索公交线路的数据，将经过站点的公交线路存为(；为正整数)，公交线路所包含的站点(；为正整数)扩充到公交换乘矩阵中；步骤八：判断是否有=，将满足条件的存入，如，则站点即为从站点A到站点B的二次换乘站点，公交线路、为换乘二次的可选路线；步骤九：根据需要，计算出各条可选路线经过的站点数、时间以及总共的乘车费用，以便选择最合适的线路。根据各方案的要求，从待选方案中选出最优路线，输出结果。（2）问题一和问题二的模型建立：由以上算法可以得到基于换乘次数最少的公交换乘优先策略。但是基于这种优先策略所得出的乘车路线不是唯一的，按照不同查询者的不同需求所得到的乘车路线不同。由此建立以下模型：需求一、仅考虑出行耗时因素由试题附录1中给出的数据，我们可以建立时间需求模型： 式中，表示路线的第项事件所消耗的时间。这里的事件包括乘车的时间，换车的时间等。把L种路线按照出行耗时函数表达式T分别进行计算，然后按照T的大小来安排选择。为了节省时间，乘客首选T值较小的路线。当然最终的选择路线并不一定是唯一的，可能为多种平行选择。需求二：仅考虑出行费用因素；同理，由试题附录1中给出的数据，我们可以得到出行费用模型：其中：为公汽票价种类，分为单一票价和分段计价，表达式为：；表示是乘坐公汽还是乘坐地铁，表达式为：；把L种路线按照出行费用函数表达式M分别进行计算，然后在按照M的大小来安排选择。为了节省费用，乘客首选M值较小的路线。同理也存在最后的多种平行选择。需求三：综合考虑出行费用和出行耗时考虑到中国国民的经济情况，我们认为出行费用重要性比出行耗时的重要性的贡献略大。利用层次分析法建立此需求的模型；此需求受出行费用和出行耗时两个变量决定，由此建立层次结构模型如下所示： 需求三出行费用出行耗时图1 层次结构模型成对比较逆称方阵如下所示：表1出行费用重要性出行耗时重要性出行费用重要性13出行耗时重要性1/31通过计算得出权数： 则 即:出行费用重要性：3/4，出行耗时重要性：1/4。 由MATLAB 求出A 的最大特征值=2在利用判断一致阵定理CI= ，其中n=2，代入数据的CI=0。由一致阵定理得上面的判断矩阵是一致阵，即假设构造的矩阵合理。综合评价函数为：（X）= =3/4出行费用+1/4出行耗时 依次把初步得到的L种乘车路线的出行费用和出行耗时代入综合评价函数（X）的表达式中，得到（X）值最小的为乘客的最佳选择。3.2 问题一和问题二的求解：（1）问题一的求解 按照以上模型及算法，把问题中的6组数据：S3359S1828 S1557S0481 S0971S0485 S0008S0073 S0148S0485 S0087S3676分别代入算法程序当中即可得到基于最少换乘次数N的选择方式的乘车路线， 由于可行方案较多，为了得到最优的可行方案，先对以上可行方案进行初步的筛选，我们提出以下的筛选原则：原则一：出行费用和出行耗时两者都比较大的首先剔除掉。原则二：如图2所示：AFEDCB图2 两条或两条以上的路线在一段路线上有多个交点图中若公交A沿箭头方向行驶，而乘客想从A到B，那么只有转乘公交C、D、E、F中的任意一个才可以到达B,只保留其中任意一个即可。按照以上筛选原则对S3359S1828 、S1557S0481 、S0971S0485 、S0008S0073、S0148S0485、S0087S3676的可行方案进行筛选，结果略。然后算出对不同查询者不同需求下的最佳选择方案。例如：S3359S1828对不同查询者不同需求下的最佳选择方案：把剔除后所得到得可行方案分别代入式、式和式中，得到以下结果。表2起始站点A公汽线路转车站点公汽线路目的站点B出行费用出行耗时(分钟)（X）S3359L436S1784L167S1828310127.5L217310127.5由以上表格可以直观的得到，从S3359到达S1828时，乘坐L436到达S1784处，再在此处选择转乘L167还是选择转乘L217，所得到的出行耗时、出行费用和综合评价函数（X）都是一样的。同理可以得到剩下5组的相关信息。对于需求三而言，考虑两个因素的时候，由指标可以看到，应该选择最后一条路线：从S1557出发乘坐L363路公交，到达S1919车站转乘L189路公交，再一直坐到S3186车站转乘L460，就可以坐到目的地S0481了。对于有些线路（比如第5组）而言可能有许多条满足条件的乘车路线，乘客可任选其中一条出行。第5组S0148S0485的相关信息可以得到不同需求下的最佳路线。 对于需求二而言，有20条不同的路线符合最佳条件，费用都是3元。乘客可以从中任意的选择任意一条路线，我们在次仅也只写出其中的一条路线：从S0148乘坐L308到达S3604,再在S3604处转乘L454，乘坐L417到达S1893，再在S1893处转乘L104到达目的地S0485。（2）问题二的求解：按照问题分析中的思路，编写出相应的程序，我们得到加入地铁网络后的乘车方案。当然，加入地铁并不意味着我们一定要去乘坐，有些方案和第一问没有发生变化。下面简单给出每条路线的选择方案。根据程序，我们可以得到在满足查询者的不同需求的前提下，6对起始点到终点之间的最佳路线，其中：S3359S1828、S0971S0485、S1557S0481和S0008S0073的最佳路线分别和问题一中相应的小组最佳路线相同。对S0148S0485的数据进行剔除后可以得到最佳路线为：由于最终乘车费用和花费时间相同的也有数条路线，在此列出两条具有代表性的线路。其中第2条路线是问题一中S0148S0485的最佳路线。表3起始站点公汽线路第一次转车站点公交线路第二次转车站点公汽线路目的站点B出行耗时出行费用（X）S0148L24S1487T1D21（S0466）L51S048587.5525.625S0148L308S0036L156S2210L417S0485112330.25由上表可见，加入了地铁网络后，乘车方案有了新的选择，优于问题一中S0148S0485的最佳路线。对于需求一，时间优先的，可以选第一个方案；对于需求二，费用优先的，可以选第二个方案；对于需求三，根据判别函数应该选择方案一。表4起始站点公交线路目的站点B出行耗时(分钟)出行费用（X）S0087T2S36762538.5（3）问题三的求解 问题三是在问题一、二的基础上讨论的，故前面的