数学建模论文-乘公交，看奥运的最佳路径选择.doc

乘公交，看奥运的最佳路径选择摘要 本文通过数学建模的方法解决了乘公交，看奥运最佳路径的选择问题。首先我们把问题看做是求最短路径的问题，并分别尝试利用传统的最短路径算法dijkstra算法、蚂蚁算法来分析计算本题，但发现前面两种算法在解决本问题中存在很多缺点特别是在大量数据的情况下计算很繁琐，速度很慢，难以满足系统设计要求的需要在较短时间内完成。因此我们在结合dijkstra算法、蚂蚁算法的思想，提出了解决城市公交线路最短路径选择的一般算法。 在问题一上，我们通过分析公交系统，在仅仅考虑公共汽车线路，对于任意的起点与终点，分别讨论各种不同的换乘次数所选择的路径，并引入交通阻抗函数求解最优路径的模型及算法，并运用模型及算法编写了相应的matlab程序，求解计算出题目中要求的6对站点的最优路径。 在问题二上，当同时考虑公共汽车与地铁线路，人们选择路线的方式又会有所不同，因为地铁具有独特的优势，特别是其速度快，往往得到人们出行的选择的青睐。本文以讨论站点在公交系统中的各种位置情况分层次讨论求解出最佳路线，最后交通阻抗函数对考虑地铁存在的情况供人们选择的各种路径的阻抗值。阻抗值越小，该路径越优。在运用模型与算法求解题目中所给的6对站点，我们发现当同时考虑地铁的因素时，只有公汽地铁公汽的情况，即为算法中的8.3.1.1算法。因此，我们在问题一的基础上，先考虑直达的情况，后考虑一次换乘的情况（不考虑换乘两次以上的情况）。编写matlab程序，计算其结果。 在问题三上，首先又假设可知当考虑步行时共有八种不同情况，又由解决问题二的算法可求出对于任意两站点的最佳路径的最小交通阻抗值，又由题设知道每两个站点的步行时间已知，所以都可求，由模型知道交通阻抗值越小，路径越优，进而计算出最佳路径。关键词：最短路径；最优路径；交通阻抗值函数；交通阻抗值一、问题的重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。首先我们将解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。二、问题的分析公共交通系统是城市交通系统的重要组成部分，可作为公共交通网络优化的核心同时也是现代城市的动脉与国民经济、人民生活密切相关。正因为如此，建立一个科学、合理的公共交通系统来引导人们出行选择提供快捷、简便的交通路线也逐步成为社会的一个热点。由于公共交通对交通资源的高效利用,使得通过大力发展公共交通,实行公交优先成为缓解日趋严重的道路交通紧张状况的必然选择. 在路径选择时,公交出行者总希望选择最快捷的线路(即综合考虑时间、费用的交通阻抗值最小的线路) 出行,可称之为最短路因素. 但由于交通阻抗值大小很难直观判定,使路径选择带有不确定性,称之为随机因素. 两者主次地位取决于供选择路径间交通阻抗差值大小. 公交线路交通阻抗值是指乘客在公交线路上出行的出行时间、费用、方便性(如换乘) 等综合费用指标,是乘客选择公交线路的依据 . 人们在讨论城市道路交通线路问题时,着重考虑任意2 个节点间最短路径. 只要2 个节点有道路连接,就可进行搜索,而不考虑该路径换乘问题,这就可能造成搜索到的路径需多次换乘. 因换乘带来的换乘时间和车票费用会增加交通阻抗. 因此对司机来讲的最短路径,对乘客却并不是最佳选择. 在一个公交网络中寻找2 个节点间最佳路径,要综合考虑出行时间、费用和换乘等相关因素,使交通阻抗最小. 人们公交出行需求是人们对公交服务的期望，为了进一步说明这一问题，在此特别引入交通阻抗函数这一概念，交通阻抗主要指乘客对某一交通系统（线路）的阻抗程度，影响交通阻抗的因素主要有：出行者换乘次数、出行耗时、出行费用、出行距离等因素。石家庄近期在市内主要公交站点进行了一次居民对公交需求问卷调查，共发出调查表400份，回收有效表格367份，有效率91.8%。调查结论：希望换乘次数少占34.47%；出行时间占25.31%；出行所需距离短占18.59%；出行费用底占12.44%；其他为6.19%。可见人们出行选择公共交通路线时，以选用换车次数少为首要目标，出行耗时最少为第二重要因素，出行距离最短为第三重要因素；出行费用低为第四因素，其他因素因为具体事项比较难统一，又因为所占比例不高，在此将不考虑。这样如果我们假设，石家庄市的这次调查真实、可靠，并能作为类似城市的实际结果，因为北京市与石家庄市各方面相差不大，故可以得到影响北京市民出行选择公交路线的交通阻抗函数为： f=0.3447k+0.2531t+0.1859d+0.1244c （1）其中f越小表示乘客越满意。 三、问题的假设1公汽每通过相邻两站点的时间相等。2北京市居民对公共交通系统的选择方式与石家庄类似。3我国城市现有的公共交通系统已处于比较完善的水平。4如果一次出行需要换乘两次以上，居民一般不会考虑。如需要换乘两次以上，则视为无法到达。5. 每相邻两点的距离相等，且每辆公交车经过的时间也一样。6. 每一次由步行转公交或公交转步行算一次换车次数。四、符号说明l 城市所有的公共汽车路线，记为l= 城市所有的地铁路线。s城市所有公共汽车的站点，记为s=，表示任一公汽站点起始站点终站点站点到站点的直达路线经过站点的所有公共汽车线路经过站点的所有公共汽车线路线路上的所有公汽站点线路上的所有公汽站点经过站点的所有地铁线路线路上的所有地铁站点线路上的所有地铁站点从点到点的距离d每次出行所经过的总站点数c每次出行的总费用st每次出行的总时间f乘客对某路径的交通阻抗值步行的交通阻抗值从点到点采用公交系统的最小阻抗值k每次出行换乘次数t每次出行总时间t(a,b)任意两站点到的步行时间城市所有地铁站点表示任一地铁站点城市所有地铁站点附近的所有公共汽车站点，记为，表示任一地铁站点附近的任一公共汽车站点表示站点经路线上行（或下行）k个站点到达ii=1,2,3,jj=1,2,3,五、模型及算法的探索在公交查询中，要求的是从某点（始点）到另一点（终点）的最短路径，最短路径问题已经有大量的研究论文，所以现存求解两点间的最短路径算法很多。5.1传统的最短路径算法dijkstradijkstra算法是迪杰斯特拉1959年提出的，用于寻找两点间的最短路径的算法，也是目前被公认的解决同类问题的最好算法。dijkstra算法又称标号法，是一个反复标号的过程。要计算任意两站点、的最短路径。可从开始，每一轮标号修正各临时标号，确定一个前标号，直至终点标上标号。最后反向追踪得到一条从到的最短路径，其中站点间有路线连接可以搜索，不需要换乘。这样子算法看上去性能很稳定且不需要换乘，似乎满足乘客出行选择的首选，但是对大城市特别是北京市来说，其公交线路来说公交线路系统站点多到上千个，对dijkstra算法所采用的数据结构将十分庞大，其实现方法总体上来说，是比较困难的。再者以dijkstra算法计算公交路线最短路程在大量数据的情况下计算很繁琐，速度很慢，难以满足系统设计要求的需要在较短时间内完成。最后用dijkstra算法计算出来的结果可能是从到需要转好几次才能到达，与在实际生活中应以换乘次数少为首选原则相违背。因此，dijkstra算法并不是很适合公交系统选择最佳路径的算法。5.2蚂蚁算法在求解最短路径的应用5.2.1蚂蚁算法基本原理蚂蚁算法是一种源于大自然中生物世界随机搜索寻优仿生算法，这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，它吸收了昆虫王国中蚂蚁的行为特性,能通过其内在的搜索机制,在一系列困难的组合优化问题求解中取得成效. 生物世界中的蚂蚁有能力在没有任何可见提示下找出从窝巢至食物源的最短路径,并能随环境的变化而变化,适应性地搜索新的路径. 蚂蚁在寻找食物源时,能在其走过的路径上释放一种它特有的分泌物信息素,使得当有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素，从而更增加了该路径的信息素强度.5.2.2蚂蚁算法在公交系统的应用蚂蚁算法有如下特征:各个蚂蚁之间互相协作,每只蚂蚁在选择路径时是基于以前蚂蚁所事先留下的信息素. 这种协作行为也被称为自催化,它提供一种正反馈. 因为选择某条路径的蚂蚁越多,其他蚂蚁选择这条路径的可能性会越大. 因此,可将蚂蚁算法用于公交路线的最短路径查询.方案如下:5.2.2.1 初始化. 在一个城市中如果公交车的数量、路线不变,那么从一个站到另一站的路线基本上也不变. 先将所有点之间的路线求出,全部放在数据库中. 当乘客选择乘车路线时,根据实时的信息从数据库中选择可行的路线5 . 每条路径附带一个参数,即蚂蚁的信息素. 开始将所有路线上的信息素的值置为相同的值.5.2.2.2 选择路线.选择某路径的次数越多,说明此路径是比较优的路径,其信息素的值也越大,以后选择路径提供必要的信息. 本系统使用的时间越长,为乘客提供的信息越全面,越准确,系统也越智能化.由上可以发现，蚂蚁算法只能在掌握大量准确的最佳选择路径信息才能较合理的预测，并不适合当前问题的解决。因此本文将结合dijkstra算法、蚂蚁算法的思想，提出了解决城市公交线路最短路径选择的一般算法。六、 关于问题一算法及模型的建立仅考虑公共汽车线路，对于任意的起点与终点。可能存在的情况是：1可直达不需换乘，则应存在，使得,。2需换乘一次车，如下图所示：3需换乘两次车，如下图所示：4若1，2，和3都无法到达，则认为该城市交通系统存在问题，本文暂不考虑。由假设可知。当存在多条线路时则算出各条线路的交通阻抗值，再比较其之间的大小，最小的路线即为最佳路线。61算法的设计：1输入乘车始点、终点2求经过的所有线路及经过的所有线路3若有则说明、可直达。所有直达线路的集合为，依次算出中各条线路 所经过的站点数（d）、所用的时间（t）及费用（c），并代入式（1）找出交通阻抗值最小的路线，输出结果。 若没有往下执行。4分别求出线路、线路的所有站点、，若有 则说明可经过一次换乘到达。所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若没有，则往下执行。5若可求出两站点、，并且，则说明可经过两次换乘到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若不存在，表明两次转车走不通，则往下执行。6对站点，重复步骤4，直到路径可行通，往下执行。7比较（3）（5）的阻抗值，取阻抗值（）最小的路径为最佳路径，输出结果，结束运算。62模型及算法的运用根据附录数据，利用模型与算法，求以下6对起始站终到站之间的最佳路线。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s3676首先，以附表1.1 公汽线路信息建立矩阵导入matlab中,用matlab软件进行运算,得出可行路线。再根据所换乘次数、花费时间，花费费用，引入交通阻抗值函数，寻求最优路径。6.2.1建立路线信息矩阵a，先考虑题中所求的那六对站点是否存在直达路线，因此，我们可通过matlab编程解决。具体编程如下：function c1=comp(a,sa,sb)x0,x1=find(a=sa); y0,y1=find(a=sb);ans=intersect(x0,y0);我们发现，题中所要求的六对站点都不存在直达路线，因此，我们考虑通过换乘一次公交车的方式来实现。6.2.2考虑通过换乘一次公交车就能解决题中所要求的6对站点的最佳路径时，我们同样运用matlab程序来实现。（具体编程见附表a）若有则说明可经过一次换乘（地铁换公汽）到达。所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。输入题中所要求的6对站点，调用该程序，发现第二对和第五对站点仍得不到实现。其他四对结果分别如下：路径时间（分钟）费用（元）s3359s1784s18281013s3359s1784s18281013s0197s2184s04851283s0008832832832832832832832832832832832652因此，我们考虑通过换乘两次公交车的方式来解决第二对和第五对站点的最佳路径。同样，我们也是运用matlab程序来实现。但是，由于换乘两次不一定比比换乘一次省钱省时，因此我们通过交通阻抗值函数来比较两种方式的优劣，从而找出最优路径。（具体编程见附表b）输入题中所要求的6对站点，调用该程序，即可得到如下结果：路径时间（分钟）费用（元）733733733733733733733733733733733733733112311231063106310631063673106310631063463463463利用模型式（1）求出上表中各路径的交通阻抗值，得到如下结果：路径（s3359s1828）时间（分钟）费用（元）阻抗值s3359s1784s1828101332.2298s3359s1784s1828101332.229873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.442873323.4428路径（s1557s0481）时间（分钟）费用（元）112335.7304112335.7304路径（s0971s0485）时间（分钟）费用（元）阻抗值s0197s2184s0485128340.7366106333.84106333.84106333.84106333.84路径（s0008s0073）时间（分钟）费用（元）阻抗值s000883226.434283226.434283226.434283226.434283226.434283226.434283226.434283226.434283226.434283226.434283226.434267321.5524路径（s0148s0485）时间（分钟）费用（元）阻抗值106333.84106333.84106333.84路径（s0087s3676）时间（分钟）费用（元）阻抗值65220.73646314.93646314.93646314.936取各条线路中交通阻抗值最小即为最佳路径（如果最小值不只一个，则说明最佳路径有多条），得到结果如下：路径（s3359s1828）最佳路径路径时间（分钟）费用（元）733733733733733733733733733733733733733路径（s1557s0481）最佳路径路径时间（分钟）费用（元）11231123路径（s0971s0485）最佳路径路径时间（分钟）费用（元）1063106310631063路径（s0008s0073）最佳路径路径时间（分钟）费用（元）673路径（s0148s0485）最佳路径路径时间（分钟）费用（元）106310631063路径（s0087s3767）最佳路径路径时间（分钟）费用（元）463463463七、关于问题二模型及算法的建立 当同时考虑公共汽车与地铁线路，人们选择路线的方式又会有所不同，因为地铁具有独特的优势，特别是其速度快，往往得到人们出行的选择的青睐。本文将用交通阻抗函数对考虑地铁存在的情况供人们选择的各种路径的阻抗值。阻抗值越小，该路径越优。对任意两站，为了比较好说明根据题意我们把所有地铁站点图画出来并表出每个地铁站点附近的公汽站点同时还给出站点的可能位置情况。由上图可以清楚的知道居民出行的线路选择有如下几种情况:7.1若,则有以下几种情况:7.1.1若可直达,即不需要换乘,则需满足或.(问题一已解决)7.1.2若需要一次换乘,有以下情况:7.1.2.1地铁换地铁,需满足任意两条不同的地铁线7.1.2.2地铁换公汽或公汽换地铁,，有且仅有一点属于7.1.2.3公汽换公汽，则转为问题一7.1.3若需要二次换乘, 有以下情况：7.1.3.1地铁换乘地铁再换乘地铁7.1.3.2地铁换乘公汽再换乘地铁7.1.3.3地铁换乘地铁在换乘公汽7.1.3.4公汽换乘地铁再换乘公汽7.1.3.5公汽换乘地铁再换乘地铁7.1.3.6公汽换乘公汽再换乘地铁7.1.3.7公汽换乘公汽再换乘公汽（转为问题一）7.2若则有以下情况：7.2.1若可直达即不换乘则只能做公汽直达（已在问题一得到解决）7.2.2若需一次换乘，则有：7.2.2.1 若是先坐地铁再转公汽则且存在使得， 7.2.2.2 若是先坐公汽再转地铁则且存在使得， 7.2.2.3若是不做地铁，则转为问题一的一次换乘情况 7.2.3需二次换乘，则有： 7.2.3.1.若是从先做地铁并在地铁交点出转乘再转公共汽车则应有经过点的所有地铁线路与经过点的所有公共汽车线路分别存在一点使得。 7.2.3.2若是从先坐地铁再转公共汽车（一次换乘公交车车情况，问题一已解决）则应有经过点的所有地铁线路与经过点的所有公共汽车线路分别存在一点使得。 7.2.3.3若是先从先坐一次公共汽车转乘在做地铁到达，则应有经过点的所有公共汽车线路与经过点的所有地铁线路分别存在一点使得。 7.2.3.4若是从先做一次公汽再转乘两次地铁到达 则应有经过点的所有公共汽车线路与经过点的所有地铁线路分别存在一点使得。 7.2.3.5若是不只做公共汽车不做地铁则转为问题一两次换车的情况。7.3若 则有如下情况：7.3.1选择最佳路径需要乘做地铁7.3.1.1若是从先做公共汽车再转地铁然后转公共汽车到，则经过的所有公共汽车线路与经过的所有公共汽车线路 分别存在两个站点 使得。 7.3.2选择最佳路径不需成做地铁，问题转化为问题一得到解决。7.4算法设计：7.4.1.输入乘车始点、终点7.4.2.判断，是否属于7.4.2.1若 7.4.2.1.1求出 7.4.2.1.2.1若有则说明、可做公汽直达。转为问题一输出问题一求出的结果。 7.4.2.1.2.2若有则说明、可做地铁直达。所有直达线路的集合为，依次算出中各条线路 所经过的站点数（d）、所用的时间（t）及费用（c），并代入式（1）找出交通阻抗值最小的路线，输出结果。 若没有往下执行。7.4.2.1.3分别求出公汽线路、公汽线路的所有站点、地铁线路的所有站点，7.4.2.1.3.1若有则说明可经过一次公汽换公汽到达，转为问题一，运用问题一算法求出并输出结果。7.4.2.1.3.2若有则说明可经过一次地铁换地铁到达，所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 7.4.2.1.3.3若有则说明可经过一次地铁换地铁到达，所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。7.4.2.1.3.4若有则说明可经过一次地铁换体铁到达，所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。若没有，则往下执行。7.4.2.1.4.1若可求出两站点、，并且，则问题转为问题一，运用问题一算法求出并输出结果。7.4.2.1.4.2若可求出两站点、，并且，则说明可经过两次换乘（地铁转公汽再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 7.4.2.1.4.3若可求出两站点、，并且，则说明可经过两次换乘（地铁转地铁再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 7.4.2.1.4.4若可求出两站点、，并且，则说明可经过两次换乘（地铁转地铁再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若不存在，表明两次转车走不通，根据假设不考虑。继续往下执行。 7.4.3若 7.4.3. 1求出 7.4.3.2.若有则说明、可公汽直达，转为问题一，运用问题一算法求出并输出结果。若没有往下执行。 7.4.3.3若有则说明可经过一次换乘（地铁换公汽）到达。所有一次换乘路径的集合为，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若没有则往下执行。 7.4.3.4分别求出线路的所有站点、7.4.3.4.1若可求出两站点、，并且则转为问题一，运用问题一算法求出并输出结果。7.4.3.4.2若可求出两站点、，并且则说明可经过两次换乘（地铁转地铁再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 7.4.3.4.3若可求出两站点、，并且则说明可经过两次换乘（地铁转公汽再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若不存在，表明两次转车走不通，继续往下执行。7.4.3.4.4对站点、重复步骤7.4.3.4.3，直到路径可行通，往下执行。7.4.4若，此情况与7.4.2.2类似，只要把始点和终点对换，即可运用7.4.2.2的算法求出结果。若不存在往下执行。7.4.5若7.4.5.1选择路线不乘做地铁，则转为问题一，运用问题一算法求出并输出结果。 7.4.5.2选择的线路乘坐地铁，若可求出两站点、，并且则说明可经过两次换乘（公汽转地铁再转公汽）到达，所有两次换乘的路径集合为 ，依次算出集合中各条路径所经过的站点数、所用的时间及费用，并代入式（1）找出交通阻抗值最小的路径，输出结果。 若不存在，表明两次转车走不通，继续往下执行。7.4.5.3对站点，重复步骤7.4.5.2，直到路径可行通，往下执行。7.4.6比较7.42.17.42.4的阻抗值，取阻抗值（）最小的路径为最佳路径，输出结果，结束运算。7.5模型及算法的运用根据附录数据，利用模型与算法，求以下6对起始站终到站之间的最佳路线： (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s3676（具体编程见附表c）输入数据，并调用程序，整理得如下：s3359s0609(d12)s1961(d37)s1828s1557s0467(d21)s3321(d14)s0481s0971