基于换乘次数优先的公交路线选择模型中国地质大学（武汉）方俊赵志江赵科指导教师朱小宁湖北省二等奖摘要：随着城市建设的飞速发展及公交系统的不断完善，公交车已成为城市居民出行的主要交通工具。
但由于城市公交线路四通八达，且随着城市扩建而快速发展。
新的公交线路在不断延伸和开辟，再加上单行道、禁左等道路交通约束，即使是当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出行的路径信息。
因此，建立适合于公交线路查询特点的公交数据模型，开发操作直观、便捷、快速、准确的城市公交查询系统，为出行者提供全面、准确的公交信息，是城市公交建设与发展的迫切需要。
影响乘客公交出行路线的选择主要有以下四个因素：换乘次数、出行距离、出行时间和出行费用。
通过查找资料和分析，得出它们对乘客的影响大小依次为：换乘次数、出行时间、出行距离和出行费用。
其中出行时间和出行距离可以看做一个整体用出行时间来衡量。
本文针对人们的出行心理并根据以上三个因素的重要程度和公交线网的实际布线情况，建立基于最优换乘次数条件下出行时间最短、出行费用最小的换乘算法模型。
在模型中，判断的原则是优先考虑换乘次数少的路径，在换乘次数相同的情况下，再考虑出行时间最短。
这种基于最优换乘次数算法能够更好的满足实际应用的需求，很好的解决了居民出行公交路线选择的问题，使公众的出行更加通畅、便利。
一、对于公汽网络中最佳路线的选择问题，我们首先定义了两个矩阵line[][]、stat_line[][]，分别存储各条线路的站点信息和通过各站点的线路信息，建立了一个完整、详细的公交网络。
然后利用广度优先搜索(BFS)及类似于递归的方法，从解空间中依次查找满足约束条件零次换乘(直达)，一次换乘，两次换乘的时间最优路线。
多次换乘路线的选取则可以综合利用启发式搜索算法和递归原理进行查找。
广度优先搜索得到的结果更准确，但是效率较低。
启发式搜索则提高了效率和方向性。
在换乘次数相同的情况下，考虑出行时间最少的路线，最后将得到的各种换乘次数最少、出行时最短路线输出，并给出各种路线的出行费用，提供给用户参考选择。
二、对于在公汽地铁混合的公交网络中查寻最优路线的问题，我们先把地铁线和公汽线输入到问题一建立的两个矩阵line[][]、stat_line[][]中（重新定义），从而构成一个大的公交网络，再建立一个矩阵stat_stat[][]，用于存储站点的邻接点，即不需要乘车，可以直接联系起来的站点。
先编写出直达的程序，然后利用类似于递归的方法，查找出最优换乘次数的路线。
由于多次换乘实际应用价值较小且数据量大我们不予考虑。
三、对于考虑步行后出行路线选择的问题，它的解决模型是问题二的模型的扩展。
虽然知道了所有站点之间的步行时间，但是我们根据实际情况只考虑步行一站，站点的邻接点增多，最优路线增多。
关键词：换乘次数广度优先搜索公交网络递归算法启发式搜索邻接点一、问题的提出一、一、一、我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。
这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。
针对市场需求，可准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。
需要解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。
并根据附录[1]提供的数据，利用本文建立的模型与算法，求出以下6对起始站→终到站之间的最佳路线。
(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。
二、问题的分析乘车方案选择的最终目的是尽最大可能地满足乘客的出行需求。
所以建立合理的乘客出行路线选择模型很重要的一点是通过对居民出行心理进行研究，以确定模型的优化目标和约束条件。
居民公交出行需求是居民对公交服务的期望，故应首先分析乘客出行考虑的因素及其重要性。
我们通过查找资料(参考文献[4])得到石家庄在市内主要公交站点进行的一次居民公交需求问卷调查的结果：34．47％的居民希望换乘次数最少；其次是时问最短为25．31％；路程最短为l8．59％；出行费用最低为12．44％；其他为6．19％。
可见影响居民公交出行的主要因素有以下3个：换乘次数、出行距离和出行时间。
图1：重要性比例图换乘次数是指乘客完成一次出行过程所需的换乘次数。
调查结果表明，换乘次数对公交的选择影响最大，若换乘次数较多，出行者会放弃对公交的选择。
转向其他更便捷的方式。
此外，换乘次数的增多往往也意味着出行费用的增加。
换乘比例高是我国城市公交出行的一个普遍现象，换乘次数的多少已成为影响居民公交出行的首要因素。
出行时间是影响居民公交出行的另一主要因素。
当其中任何一种出行方式时间过长时，居民都有可能改选其他出行方式。
出行距离尤其是车外距离对居民公交出行影响也比较明显，但是出行距离往往与出行时间成正比，而出行时间更能反映心理中出行距离的远近，故综合起来只考虑出行时间，即出行距离和出行时间看作一个因素考虑。
出行费用对居民出行路线选择的影响最小，因为一般情况下，换乘次数是不会超过两次的，不同路线的出行费用相差很小，在乘客的承受范围之内。
根据以上分析，确定选定乘车路线的原则为：首先选择换乘次数最少的路线，其次是时间最短。
最后将得到的换乘次数最少、出行时间最短的路线输出，并给出各路线的出行费用，供乘客参考选择。
其次我们对公共交通工具进行分析。
公共交通工具简称公交，本题中包括公汽、地铁两种。
其中公汽又可以分为三种：环线车、往返车，上下线车。
因为车的种类很多，线路各有特点，比如上下线车的上下线路站点不完全一样，环行车的起始点和终点一样等，为了研究的方便必须进行统一的处理，然后建立一个完整、详细的公交网，利用这个公交网进行查询。
我们利用公交网可以查找到换乘次数最少的路线，但是换乘次数相同的路线往往不止一条，在换乘次数相同的情况下，还需要考虑出行时间。
公交的出行时间由三部分组成，即公共交通乘行时间、步行时间、候车时间，计算时间时按部分分开计算。
分析了以上问题后，我们对具体问题进行具体分析。
问题一只考虑公汽的换乘，利用已经建立的公交网络，建立查询模型相对容易。
搜索的方法可以采用启发式搜索算法、广度优先搜索算法及类似于递归的方法进行查找。
得到换乘次数最少的路线后，再计算出行时间，最后给出供选择路线的出行费用，供乘客参考。
问题二加入了地铁线路，地铁线和公汽线构成了一个大的公交网络。
但是在问题二中不同站点间可不乘车而通过地铁站联系起来，即不同站点近似成一个站点了。
因为这些站点是通过地铁站联系起来的，而不是通过线路连接起来的，它们间的关系在公交网中无法体现出来，所以我们应该建立一个矩阵来存储站点间的关系，该矩阵要能反映出可以通过地铁站联系起来的站点间的关系。
然后根据该矩阵，利用地铁线路和公汽线构成的公交网络进行查找，原理同问题一的一样，即可以得到结果。
问题三又考虑了步行的情况。
它比问题二的范围更广，也更符合现实情况。
问题一中只有当不同线路之间具有公共点时才能进行转车，问题二可以通过地铁站在不同的站点换乘，但是它们计算出来的结果有时并不符合实际情况，比如在实际出行时只需换乘两次便可以到达目的地，但是计算出来的结果却需要乘三次或四次。
出现这种情况的原因就是忽视了现实生活中人们步行小段距离再转车的现象。
具体地说，人们在转车时，并不是下车后直接在下车的站点处转车，往往需要步行一小段距离到附近的站点去转车。
问题三即考虑了这种情况，它和问题二都是同一类的问题，即不同站点间可以转车，只是它的联系方式有两种：地铁站和步行。
我们只需将问题二建立的矩阵扩大一下，加入步行后站点间的关系，就可以利用问题二的模型计算出结果。
三、模型假设考虑实际问题情况和解决问题的方便，我们对问题进行了简化，做出如下的假设：(1)乘客出行路线的选择依据的先后顺序都为：换乘次数、出行时间、出行费用。
(2)不考虑道路交通运行条件的影响；(3)公汽、地铁等相邻站点间运行时间相同，不考虑各站间距离、交通状况对行驶时间的影响，即：相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟(4)各种公交在不同地点的换乘所需时间都统一处理，即不考虑各种公交的发车频率、行驶速度以及其他一些因素的影响。
即：公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)(5)乘坐各种公交时所需的等待时间一定。
即：乘坐公汽需要的等待时间为3分钟、乘坐地铁所需要的等待时间为2分钟。
(6)地铁站点相对应的公汽站点间的换乘时间是由从一对应公汽站走到地铁站的4分钟、再由地铁站走到另一对应的公汽站的4分钟以及乘坐公汽所需的等待时间3分钟组成。
即通过地铁站点相对应的公汽站点间的换乘时间为11分钟。
四、参数定义S：起始点；F：终到点；C：中转站；line[][]：存储各条线路的站点信息的矩阵；stat_line[][]：存储通过各站点的线路信息的矩阵；stat_stat[][]：存储邻接点的矩阵；type[]：保存存储的路线的收费情况:分段计费或单一制1元计费；L:公汽线路；S:公汽站点；T:地铁线路；D:地铁站点。
五、模型的建立及求解五、五、五、1. 1.问题一模型的建立及求解本问题的建模思路为：首先对题目所给的数据进行处理、输入，建立公交网络；然后根据公交网络进行搜索，找到换乘次数最少的路线；再算出各路线的出行时间，找出出行时间最短的路线；最后算出路线的出行费用，将换乘次数最少、出行时间最短的路线输出，并输出其出行费用。
公交网络路线查询算法：1)1)读入数据，建立公交网络存储的数据结构。
将原始数据进行特殊处理，便于存储。
每一条线包括4-5行，如下：第一行：线路的编号,在存储的时候将分成两条线来存储;第二行：线路的类型,0:分段计价，1:单一制1元计价;第三行：线路的条数，1:往返线，2:上下行线，3:环形线;第四行：线路经过的节点(若有上下行线则还有第五行);公交路线的存储：建立line[]矩阵，如表一所示：a ．上下行线：对于上行和下行分别当成两条路线来处理，且编号相差520。
