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