乘公交-看奥运

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B 我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：2010年7赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：B:乘公交，看奥运【摘要】：这些年来，城市的公交系统有了很大发展，城市的公交系统的发展带给人们便利的同时也带来了路线选择的问题。这是一个最优路径选择问题。在路径选择上我们采用遍历法，找出可能的从路径源到目的地的路径，并根据用户的实际需求（时间最短，费用最少，最方便）作为约束条件进行优化选择，最终得到符合每个客户需求的路径选择方案。在问题一中只有汽车这种工具可供选择。问题二在问题一的基础上加入地铁系统，地铁系统和公交系统的信息存在差异性，找出两个系统相关信息的共同点并把这两个系统相关信息整合到一起是求解的关键。问题三是一个开放性的问题，约束条件少，灵活程度大，我们以现实生活中的实际情况为根据，在建模过程中我们定义了代价P。根据P的定义式计算出从起点到终点全部乘车和步行1站，步行2站……步行全程的所有代价，P值最小的方案就是最终结果。关键词：最少换乘；最少时间；最少花费；公交网络；出行路径选择模型；代价问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。问题分析在城市电子地图中，公共交通信息模块是必不可少的，它为各种交通信息的搜索查询，统计提供方便直观的手段，公共交通信息的查询倍受用户的关注。在现有的公交线路与站点的情况下，设计合理的交通网络查询模型有助于人们确定出发的时间，出行线路和换乘方案。即当乘客在一个查询系统里直接输入起始点与目标点之后，系统会自动生成最优的出行路径。通过对乘客的出行心理进行研究，其结果是“换乘次数”是大部分公交乘客在选择出行时首先考虑的因素，其次是出行时间和距离的长短，而出行耗费的时间与换乘的次数及距离的长短密切相关。对公交车换乘问题的研究，我们做出如下假设。

三、模型假设1、假设车站不重名；2、假设各路经上公交车发车频度相同；3、假设相邻站点间平均行驶时间一定；4、假设不出现交通阻塞，公交运行顺畅；5、假设不出现车辆故障及道路交通事故；6、假设始发终点出入地铁需要步行4分钟；7、假设公交准点到达，不考虑红绿灯等待时间。8、票价一定，不会变更9、地铁为往返线路四、符号说明：乘汽车、地铁、走路和交通工具转换所花费的时间；：乘汽车和地铁所花的费用；：北京市公共汽车交通图；：图G的所有站点集合；：图G的所有公汽线路集合；：代价；：公交线路信息矩阵。五、模型的建立对居民的公交出行心理问询调查，公交乘客选择出行路径的决策过程主要受到3个因素的作用：换乘次数、所花费用和出行耗时。本文根据这三个因素，确定查询者的不同需求有三种：第一种情况是最普遍的一种情况，那就是尽量出行方便，少换车；第二种是所花的费用最少；最后一种是所花费的时间最短（路程最短）。因此，我们要解决的问题是：根据查询者查询的起始点、终点找出换乘次数最少的路径，花费最少的线路和时间最少的路径，以提供给查询者参考。问题一：问题一为只考虑公共汽车系统下的任意两点间的路径选择问题，我们在此做出一个局部假设:在这种情况下不能通过地铁站来换乘汽车（或者说地铁系统不可用）。根据查询者的三种不同需求，找出三类符合不同要求的路径集。第一类：换乘次数最少的路径，分别是查询者查询的起点和终点。1.如果使得,,则，同在一条公汽线路上，即从到无需换乘；2.如果，,若，,则，通过，相连，连接点是，即从到需换一次车，换车点是；3.如果,，,，，若，，则，通过，，相连，连接点是,，即从到需换两次车，乘坐线公汽到站，再乘坐线公汽到站，最后乘坐线公汽到终点。以此类推，可找出换乘次数最少的路径。采用遍历法找出从到的所有路径，根据组成路径的线路情况计算每一条路径的所花费用、所用时间。出行方式只有乘汽车一种，所花的时间只有汽车上的时间和换车所花费的时间，总的时间为：------------------------------------------------（1）所花的费用为公共汽车的车费的总和：----------------------------------------------------（2）第二类：费用最少的路径比较所有路径的车费总和，把费用最少的路径组成一个集合,再比较这个集合中的所有路径的花费时间，找出其中花费时间最少的路径，并把这些路径组成一个新的集合，这个集合中的所有元素就是提供给查询者的从起点到终点的费用最少路径。第三类：花费时间最少的路径与第二类费用最少路径的选择类似，首先比较所有路径的时间总和，把时间最少的路径组成一个集合，再比较这个集合中所有路径的费用总和，找出其中费用最少的路径，并把这些路径组成一个新的集合，这个集合中的所有元素就是个提供给查询者的从起点到终点的花费时间最少的路径。问题二：问题二中新增了一种交通工具地铁，为乘客提供了更多的乘车选择。乘客可以通过地铁、汽车间的换乘方便快捷的到达目的地。但是公汽和地铁是两个不同的系统，它们的线路及相关信息存在着差异，如何把这两个系统的信息整合到一起是我们要解决的首要问题。我们从地铁换乘公汽（对应的，公汽在这一站也可换乘地铁）这一信息数据出发，根据模型假设4，把地铁站和与之对应的所有公汽站用一个相同的站号代替，形成新的公交系统（此时已无公汽系统，地铁系统之分）。此时游客到达目的地可以选择汽车或者是地铁中的一种或者是同时采用，那么总的时间花费为：--------------------------------------------（3）费用的总开消为：----------------------------------------（4）新整合的公交系统与问题一中的公汽系统无本质区别，因此可以采用问题一的解决方法求解。问题三：在问题三中可以步行的方式往返于任意两站点之间，并且是知道了任意站点之间的步行时间。此时尤其值得注意的是“任意”，因为有的站点之间可能汽车是没有直接相通的，地铁也没有直接相通，那么此时我们可以采用步行的方式来节省中间的时间开。也就是说游客到达目的地可以采用步行和交通工具相结合的方式。总的时间为：-------------------------------------（5）费用的总开销为：------------------------------------------（6）六、模型求解本题的特点是数据量巨大，数据是字符型数据。因为字符运算比数值运算要麻烦，所以我们考虑用数值型数据代替字符型数据。分析公汽线路信息，我们得到以下数据特点：1、公汽线路编号格式：“”+三位数字。如“”；2、公汽站点编号格式：“”+四位数字。如“”。用003表示，0028表示，就可以实现数据类型转换。转换成数值型数据后就可以用向量表示每一条公汽线路的信息。每条公汽线路的信息包括：线路号，收费方式，方向和所有经过站点。向量=[线路号，收费方式，方向，所有经过站点]（收费方式：1表示分段收费，2表示单一费用，方向：3表示上行，4表示下行，5表示环形或者是往返线路）。如此得到将近1000个向量，原始数据得到了有效的处理。但是如此多的向量在运算中仍然很繁琐，于是我们想了矩阵。以最长向量的长度为准，其余向量在末端增加0，使所有向量与最长向量等长，然后把所有向量组合成一个矩阵，这个矩阵用表示。问题一：在问题一中只能采用汽车这种出行方式，按照人们一般要求简单的习惯，我们首先考虑是否有公共汽车直接从乘客的始发站到乘客的终点站。为此，我们根据乘客的始发站可以得到所有的经过站点的汽车集，然后根据乘客的终点站可以得到所有的经过站点的汽车集。如果在和中间有交集，那么这些数据很可能是满足乘客需求的，此时我们需要对这些交集做出合理性判断，满足要求的线路必须符合符合下列3个条件中的一个：(1)环行车；(2)往返车；(3)从开往的（从开往是不符合的）。但是很有可能没有在和中间是没有交集的，此时需要考虑一次换乘的情况，首先我们找出集中所有线路的汽车经过的所有站点集，同时在集中找出所有汽车所经过的所有站点集。如果在两组站点之间有交集，那么此时这些站点可以考虑作为中转站点。但是要能够成为中转站点还必须符合一个条件那就是站点必须在乘客的起点站和终点站之间。如果和之间有交集并且只有1条线路符合线路条件，那么很明显乘客选用此条线路是比较合理的，因为很方便；但是如果选用的这条线路经济花费较高（直达终点站3元，换乘一次2元可达终点站），乘客有可能选择采用换乘的方式来降低花费。如果交集中不仅1条线路符合条件，那么此时乘客可根据自己的尽一步需求，选择所花经济最少的或者是采用时间最短的。如果和之间没有交集，很明显游客还是必须要乘坐集中的一辆汽车来出来，并且乘坐集中的一辆汽车来到达目的地，但是究竟乘坐其中的哪一辆汽车，我们可以再次遍历、集中所有线路汽车经过的站点。从前提条件得到他们之间没有公共的站点，但是可以再次从经过这些车辆的站点入手，最后得到经过其中2个站点的汽车集合，并且求出所花费的时间和金额的供乘客选择。以此类推，根据我们的假设5，任意两个站点之间都可以通过有限次的车辆换乘来到达对方。由此我们得到流程图如下：图SEQ图\*ARABIC1：程序算法流程图根据流程图我们编出matlab程序，在程序中我们通过输入路径的起点站和终点站，可以得到满足不同要求的路径集合，我们在这些集合中选择一条路径为代表，得到如下的路径选择方案：表格SEQ表格\*ARABIC1：路径方案选择情况表客户需求路径方案选择所用时间费用开销换乘次数33591828436路车（下行）1784站167路车(下行)1013115570481363路车(下行)1919站417路车(上行)2424站312路车（下行）112320971048513路车(下行)2184站417路车(下行)1283100080073159路车(下行)2683站58路车(下行)832101480485308路车(上行)36站156路车(上行)2210站417路车(下行)1063200873676454路车(上行)3496站209路车（下行）6521表格说明：我们以从3359站到1828站为例，应该在3359站乘坐436路车的下行线，到达1784站下车然后换乘167路车的下行线到达终点。问题二：问题二中新增了一种交通工具地铁。此时不仅多了一种交通工具，多了可以选择的线路，同时还为我们乘坐汽车带来了方便，我们可以通过地铁站来换乘汽车，这是免费的。从上述三个方面来分析地铁系统带来的好处。多了一种交通工具我们可以理解为有了这种交通工具后可以减少我们的行车时间，能够更快的到达目的地；多了可以选择的线路，但是同时注意到地铁线路上的所有站点都是以前有的公交站点并没有新增站点，所以我们可以将地铁线理解为新增的普通的公交线路，这样我们在选择某些路径时可以更直接的、换乘次数更少的到达目的地；同时地铁站也为我们换乘汽车带来方便，通过地铁站的使用，我们能够更灵活的换乘汽车，在换乘次数相同的情况下有了地铁站我们能够更快的到达目的地。由于地铁线的费用较高，所以不能为我们出行降低路费。新增地铁系统后主要是在方便、快捷上给人们带来了实惠。但是公汽和地铁是两个不同的系统，它们的线路及相关信息存在着差异，如何把这两个系统的信息整合到一起是我们要解决的首要问题。我们从地铁换乘公汽（对应的，公汽在这一站也可换乘地铁）这一信息数据出发，根据模型假设4，把地铁站和与之对应的所有公汽站用一个相同的站号代替，形成新的公交系统（此时已无公汽系统，地铁系统之分）。新整合的公交系统与问题一中的公汽系统无本质区别，因此可以采用问题一的解决方法求解。具体编程时，地铁站和与之对应的所有公汽站用一个相同的站号代替，这个站号由两部分共5位整数构成。低两位由地铁站号中的两位数字构成，高三位统一由100构成，以与四位的汽车站号区别。如和与之相对应所有公汽站都用10001代替。地铁线路可表示为：1000110002…1002210023。再运用原始数据的处理方法处理、线路，把处理后的数据加入矩阵，形成新的L矩阵。再运用问题一的求解方法对问题二求解，得到满足不同需求的路径集合，集合中的元素包含以下信息：起始的线路，换乘的站点，经过的线路，中间经过的站点数（以线路的不同分别记录）。接下来我们要做的就是还原替换的站点。这种还原是一对多的还原，如某个10001号站点到底是还原成？还是？还是？还是？我们还是采用遍历法，从路径集合中提取出该站点（如10001）所在线路的线路号，根据替换前的矩阵元素的分布规律判断：当线路号>=521时，即该站点是地铁站，再对该站点号除以100后取小数再乘100，既得地铁站号的编号；当线路号<=520时，即该站点是公汽站，首先用上述方法得到该站点对应的地铁站号，再用该地铁站号对应的公汽站号与向量（线路号，:）中的所有元素进行比较，当存在该向量的元素与某个公汽站号相等时，就用这个公汽站号代替站点号，得出满足不同需求的信息明确的路径集合。我们在这些集合中选择一条路径为代表，得到如下的路径选择方案：表格SEQ表格\*ARABIC2:加入地铁系统后的公交选择路径客户需求路径方案选择所用时间费用开销换乘次数33591828436路车（下行）1784站167路车（下行）101311557048184路车（下行）1919站417路车（上行）2424站254路车（上行）109320971048513路车（下行）2184站417路车（下行）1283100080073159路车（下行）D13站474路车（上行）802101480485306路车（上行）3604站454路车（上行）1919站2079站417路（下行）1033200873676直达2530问题三：问题三是一个开放性的问题，约束条件少，灵活程度大，所以能够从很多角度出发建立不同的数学模型。我们充分考虑现实生活中的实际情况，以最符合人们普遍的选择为前提，建立数学模型并做如下局部假设：任意两个公交站点之间都可以步行到达（经过公交线路或可以不经过公交线路），并且已知站点之间的步行时间。人们都不愿意长时间走路，即走路的路程太远时选择乘车。人的步行速度小于公汽或者地铁的速度。在现实生活中，我们也经常通过走路的方式去我们想去的地方。一般我们选择走路去目的地有2个可能：一个是目的地不是很远，“走几步”路就到了，没有必要去花钱乘车；另一种情况是想去的地方交通不是很方便，公汽不是经过两点之间的近似直线到达目的地而是绕行了很远，甚至还有可能不仅要绕行很远，还必须要换乘公汽，在这个时候我们也会选择走路到距离目的地较近的一个站点乘车然后直达目的地或者是直接就走到目的地去（如果这个距离不是太远，没有超出我们愿意承受的走路距离）。定义在乘车过程中，花费时间产生时间代价，花费费用产生费用代价。时间代价和费用代价的和称为总代价，简称为代价，用P表示。时间代价=(为时间代价因子，为时间)-------------------------（7）费用代价=(为费用代价因子，为费用)------------------------（8）--------------------------------------------------（9）从网络上查找到信息：正常的平均步行速度为，北京市公交车在市区的平均速度为，相同距离的步行时间与乘车时间比为3。相邻公汽站平均行驶时间3分钟，相邻公汽站平均步行时间为9分钟。假设个公汽站远的距离选择走路和选择乘车的人数一样多，也就是说个站点的距离对人们来说走路和乘车的代价是是近似的。根据常理可知是一个很小的整数，所以在计算这个站距离的乘车代价时取，由此我们可以得出代价式子：------------------------------（10）-----------------------------（11）由于代价相等，我们可以得出式子：------------------------------（12）得到，令费用代价因子b=1，得到：---------------------------------（13）的取值可以通过问卷调查的方法统计出来，即是可已知的，所以有确定的值。现在假设需要从地到地。如果采用乘坐公汽或者是地铁的方式需要经过个公汽站和个地铁站，并且需要元的车费，那么此时的代价为：----------------------------（14）如果我们直接从起点站走到第其中的第个站，已知花费时间为，在剩下的个车站中要到达目的地还需要经过个公汽站和个地铁站，并且还要支付元的车费（、、都是可计算的），那么此时的代价为：--------------------------------------------（15）最后我们通过程序让遍历所有线路中的站点，如果存在说明可以采用走一段路，并且找出其中的差值最大的时候站点才开始乘车。如果遍历所有的值都没有，说明从到不适合走路。七、模型评价模型优点：在问题一和问题二中在已知时间信息和费用信息的情况下，找出所有可能的从源到目的地的路径集，从这些路径集中找出转乘次数最少，时间最少，花费最少的路径给用户。思路简单清晰，易于编程实现计算机处理。在问题三中虽然没有补充信息说明，但是我们通过以现实生活为依据，建立了普遍实用的数学模型，当给出源和目的地时，模型能够确定的判断出是否应该走路。如果应该走路的话还能够得出应该走路到什么地方再上车。模型缺点：从原始数据可以看出北京市交通系统比较发达，公交线路在800条以上，所以在模型中我们只考虑了最多两次转乘就能够到达目的地的情况。如果2次转乘还不能到达目的地本模型将不能给出答案。模型推广：首先，这是一个静态的交通系统，所有的信息都已经给定。通过本题的数学模型，只要给出路径源和目的地，我们就可以通过算法求得应该走的路线，所花的时间以及所需的费用。但是在现实生活中，交通系统随时都可能在发生变化，常见的如：上下班时候的某些线路运力不足，由于交通事故某两个站点之间的线路暂时中断，但是这些在本题中都没有能够反应出来，这样我们的路径推荐模型就可能将用户带到已经中断或者是非常拥挤的线路中。所以从实际出发，我们应该建立动态的系统，将交通系统查询计算机网络化，每一个查询终端类比为一个路由器，同时采用类似于路由算法的实时更新算法。这样才能够根据最新的数据信息判断出最优方案。八、参考文献【1】周文峰等，运筹与管理-最优公交线路选择问题的数学模型及算法，2008年10月第17卷第5期【2】王兵团，数学建模基础.北京：清华大学出版社，昆明大学出版社，2004年11月【3】朱道元，数序建模案例精选.北京：科学技术出版社，2005年5月附录：functiony=findline(x)

%xisabusstation%aimistofindallbuslinethroughxloadbusstation[l_a,t]=find(A==x);y=l_a(find(t>3));

functiony=findstation_come(b,x)%bisagoalstation%xisthebuslinethroughb%theaimistofindallstationgoingtobloadbusstationlast_b=max(find(A(x,:)==b));y=A(x,4:last_b);

functiony=findstation_to(a,x)%aisastartingstation%xisthebuslinethrougha%theaimistofindallstationcomingfromaloadbusstationhead_a=max(4,min(find(A(x,:)==a)));

%mincolumnlast_a=max(find(A(x,:)~=0));

%maxcolumny=A(x,head_a:last_a);

functiony=nochange(a,b)l_a=findline(a);l_b=findline(b);y.line=intersect(l_a,l_b);y.connecting=[];

functiony=changeone(a,b)x=[];

fori=1:length(l_a)

forj=1:length(l_b)

x_a=findstation_to(a,l_a(i));

x_b=findstation_come(b,l_b(j));

cap=intersect(x_a,x_b);

if~isempty(cap)

t=cap;

select_line_a=l_a(i);

select_line_b=l_b(j);

select=[select_line_a,select_line_b,t];

x(i,j).line=[select_line_a,select_line_b];

x(i,j).connecting=