公交最优路径选择的数学模型及算法_雷一鸣

公交线路中寻求最优路线的模型与算法摘要本文对公交线路查询问题进行了研究。

根据查询者的各种不同需求，以换乘车次最少为约束条件，分别以出行耗时和出行费用为目标函数，建立多目标规划模型，运用公交换乘搜索算法可得到合理的出行路线。

针对问题一，在仅考虑公汽线路时，用520条公汽线路构建公共交通矩阵。

以此矩阵作为搜索对象，运用基于广度优先的公交换乘搜索算法，找出符合“换乘次数最少”的可行解。

分别以出行耗时和出行费用为目标建立规划模型。

然后，对有限个可行解采用枚举法，将其出行耗时和出行费用一一求出，通过比较得到规划模型的最优解，结果见正文第6页表3。

同时，在换乘次数和是否穿过地铁站等方面对结果作了清晰评价。

公汽线路。

重新构建共公交通矩阵。

在考虑地铁站与公汽站点相互连通的情况下，运用问题一的解法求得规划模型的最优解，结果见正文第7页表4。

针对问题三，当已知所有站点之间的步行时间时，在模型二的基础上对公交换乘搜索算法改进，相邻近的两站点间乘客可以通过步行到达，并对整个乘车过程中步行次数和步行时间进行约束得出了问题三的模型。

关键词：公共交通矩阵公交换乘搜索算法目标规划相邻站点第29届奥林匹克运动会将于2008年8月在首都北京举行，这是我国第一次成功的申办奥运会，极大的鼓舞了全国人民。

经过近六年筹备，各大奥运会场馆相继竣工。

作为奥运会的重要交通工具，举办城市的公共交通系统也有了很大发展。

现在北京市的公汽线路已达800以上，较好的满足了到现场观看奥运比赛的国内外观众的交通需求，使公众的出行更加通畅、便利，与此同时人们也面临着多条线路的选择问题。

因此，根据市场需求，某公司准备研制开发一个解决公汽线路选择问题的自主查询计算机系统，系统核心是线路选择的模型与算法。

设计该系统要从实际情况出发考虑，满足查询者的各种不同需求，现有三个问题需要解决：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型和算法。

利用此模型与算法，求出以下6对起始站到终到站之间的最佳路线，并给出清晰的评价说明。

北京市公交最优乘车路径选择的数学模型摘要2008年8月，奥运圣火将在北京点燃。

盛大的奥运赛事聚焦了全世界人民的目光，明年的北京将绽放最绚丽的光彩。

届时，客流量将会大幅上升，环境、交通、城市建设都将面临很大考验。

怎样才能更好的解决奥运期间市民和游客的出行问题呢？针对这样的实际问题，我们设计了一个城市公交线路的自主查询系统，建立了关于城市公交最优乘车路径选择的数学模型和算法，巧妙的运用Java语言编写程序，解决了现实生活中乘车路径选择的问题。

针对问题 1，在只考虑公汽线路时，首先求出起始站和终到站所有公交线路集合的交集，若此交集为非空交集，则选择所有直达线路中途经站点数最少，即花费最少的线路出行；若交集为空，选择起始站附近的站点，求出此站和终到站所有公交线路集合的交集，若为非空交集，则可选择换乘一次的方法出行；否则，换乘两次，换乘三次……直到找到换乘N次的乘车方案为止。

存在多条乘车线路时，考虑途经站点最少的乘车方式。

在此基础上，通过运用Java语言编程，确定了所需的最优乘车路径：（1）乘坐L436路公交车从S3359到S1784站，在S1784站换乘L167或L217路到S1828站，全程换乘一次，耗时101分钟，乘车费用为3元；（2）乘坐L84路公交车从S1557到S1919站，在S1919站换乘L189到S1402站,在S1402换乘L460到S0481站，全程换乘两次，耗时112分钟，乘车费用为3元；（3）乘坐L13路公交车从S0971到S2184，在S2184站换乘L417路到S0485站，全程换乘一次，耗时128分钟，乘车费用为3元；（4）乘坐L43路公交车从S0008到S1383，在S1383站换乘L282路到S0073站，全程换乘一次，耗时113分钟，乘车费用为3元；（5）乘坐L308路公交车从S0148到S0302，在S0302站换乘L427到S2027站，在S2027站换乘L469到S0485,全程换乘两次，耗时118分钟，乘车费用为3元；（6）乘坐L454路公交车从S0087到S3469，在S3469站换乘L209路到S3676站，全程换乘一次，耗时65分钟，乘车费用为2元；针对问题 2，要求同时考虑公汽线路和地铁线路，在同一地铁站对应的任意公汽站间可免费换乘，利用问题1的思想建立数学模型，运用Java语言编程，得到同时考虑公汽和地铁时的最优乘车路径：前五对起始站→终到站的最优乘车路径的选择与问题1一致。

公交最优路线问题摘要针对公交系统的特点，该文把环形路线和往返路线做成上下行路线，由此构造了1040行、100列的矩阵K（矩阵的每个非零元素为对应路线的站点）。

矩阵的行下标对应公交系统中的线路号（行数为偶数：线路号=行数/2；行数为奇数：线路号=（行数+1）/2），矩阵的列下标对应每条路线上公汽经过站点的次序，当路线中的站点不足100个时，矩阵中对应的位置以0代替。

鉴于公交系统网格的复杂性，没有采用常规的迪克斯特拉（Dijkstra）算法，而是提出了一个能高效搜索任意两站点之间的路线选择的算法。

基本思想时从经过起始站的路线出发，搜寻出任意两站点间转乘次数不超过两次的可行路线，然后对可行解进一步处理，建立了以时间最少为目标的优化模型。

从实际情况出发，经过尝试与探索，为了满足查询者的不同需求，归纳出直达，换乘一次，换乘两次的情况，并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的站点，最后提出了进一步的意见和建议。

利用此模型和算法求解所给的6对起始站→终到站之间的最佳（最省时）路线。

这6对路线的具体情况如表1表1 6对起始站→终到站之间的最佳（最省时）路线关键字：优化模型，最优路线，搜索筛选，换乘次数，乘车时间。

一 问题重述城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。

如果能够提供一种服务，为市民特别是外来旅游、出差、就医等急需了解本地道路情况的人提供方便、快捷、经济、高效的乘车方案，将方便他们的出行和生活，同时减少不必要的交通流量，提高交通运输效率。

这已是一个越来越迫切急于解决的现实问题。

针对市场需求，本文研制开发了一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。

需解决如下问题：给出任意两公汽站点之间线路选择问题的一般数学模型与算法。

以用增加厚度和横向联系、或设置代替承载力的补充结构的方法来加固。

３．２．１在原拱圈下增设拱圈在桥下净空允许时，可在原有的拱圈下部增设拱圈，紧贴原拱圈下面，喷射钢丝网水泥拱圈或浇筑混凝土拱圈。

３．２．２在原拱上增设钢筋混凝土拱圈加固法在拱圈上面加一层新拱圈，即挖开原拱顶填土层直到拱背，洗净修补好，凿毛，加筑新拱圈。

此法不仅加固了拱圈，而且将原有开裂的拱连在一起，有利于桥梁排水。

３．２．３降低拱脚水平推力，采用钢杆拉结法为防止拱脚位移，提高拱的承载力，也可在拱圈根部凿开混凝土，对外露钢筋可焊接钢拉杆铆座（或在清理混凝土表层后以环氧砂浆粘结铆座），装上拉杆螺栓铆固拱脚。

３．２．３石拱桥拱圈加固的钢板箍（或钢拉杆）与螺栓锚固法对石拱桥亦可在拱圈的跨中和１／４处加设三道（或多道，视具体情况而定）钢板箍（钢板厚可取６ｍｍ～８ｍｍ）或钢拉杆，用螺栓在拱底及拱侧钻孔锚固，并注意将锚固点设在拱圈厚度的１／３处。

作者简介：刘克礼（１９６０－），男，广西靖西县人，工程师，长期从事农村公路建设和养护管理工作；黄凤姣（１９７０－），女，广西荔浦县人，高级工程师，长期从事农村公路建设和养护管理工作；张丽新（１９６７－），女，广西横县人，工程师，长期从事农村公路建设和养护管理工作。

收稿日期：２００７－１２－０７!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!公交最佳出行线路的一个模型及算法魏峰，夏小刚，张守刚，杨云峰（西安科技大学基础部，陕西西安７１００５４）摘要：在分析影响最佳出行线路选择评价指标的基础上，建立的最佳出行线路选择模型，可很好地解决最佳出行线路的选择问题，对此类问题的研究具有一定的指导意义。

关键词：最短路径；最少换乘次数；最佳出行线路；改进Ｆｌｏｙｄ算法中图分类号：Ｕ４９１．２文献标识码：Ａ文章编号：１００２－４７８６（２００８）０６－０１５５－０４ＡＭｏｄｅｌａｎｄＡｌｇｏｒｉｔｈｍｆｏｒＯｐｔｉｍｕｍＴｒｉｐＲｏｕｔｅｉｎＰｕｂｌｉｃＴｒａｎｓｉｔＳｙｓｔｅｍＷＥＩＦｅｎｇ，ＸＩＡＸｉａｏ－ｇａｎｇ，ＺＨＡＮＧＳｈｏｕ－ｇａｎｇ，ＹＡＮＧＹｕｎ－ｆｅｎｇ（１．ＤｅｐａｒｔｍｅｎｔｏｆＢａｓｉｃＣｏｕｒｓｅｓ，Ｘｉ′ａｎＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅｓａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｉ′ａｎ７１００５４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｅｏｐｔｉｍｕｍｔｒｉｐｒｏｕｔｅｓｅｌｅｃｔｍｏｄｅｌｅｓｔａｂｌｉｓｈｅｄｏｎｔｈｅａｎａｌｙｓｉｓｏｆｅｖａｌｕａｔｉｎｇｉｎｄｅｘｏｆｔｈｅｏｐｔｉｍｕｍｔｒｉｐｒｏｕｔｅｓｅｌｅｃｔｉｏｎ，ｃａｎｅｆｆｅｃｔｉｖｅｌｙｓｏｌｖｅｔｈｅｉｓｓｕｅｏｆｓｅｌｅｃｔｉｎｇｔｈｅｏｐｔｉｍｕｍｔｒｉｐｒｏｕｔｅ，ａｎｄｐｒｏ－ｖｉｄｅｓｏｍｅｒｅｆｅｒｅｎｃｅｆｏｒｔｈｅｓｉｍｉｌａｒｒｅｓｅａｒｃｈａｓｗｅｌｌ．１５５Ｋｅｙｗｏｒｄｓ：ｔｈｅｓｈｏｒｔｅｓｔｐａｔｈ；ｔｈｅｍｉｎｉｍｕｍｎｕｍｂｅｒｔｏｔｒａｎｓｆｅｒ；ｔｈｅｏｐｔｉｍｕｍｔｒｉｐｒｏｕｔｅ；ｉｍｐｒｏｖｅｄＦｌｏｙｄａｌｇｏｒｉｔｈｍ０引言随着我国汽车工业与公路建设的不断发展和完善，公众的出行也更加通畅、便利，但同时也面临多条线路的选择问题。

公交线路优化选择模型及算法摘要本文主要是针对两公汽站点之间的最佳公交路线选择问题而建立模型，对于给定的三种不同的具体情况，我们建立了以总换乘次数最少，乘车所消耗总时间最短以及乘车费用最少的多目标规划模型。

为建模方便，我们首先设定由起始站到终到站所经过的站点序列，并构建了各个站点换乘情况的0-1决策变量，将所有站点的换乘情况进行叠加得到总换乘次数。

乘车所消耗的总时间和总乘车费用，在不同情况下计算方式不同。

问题一只考虑公汽。

由从起点到终点经过的站点数目和换乘次数可得到总消耗时间，同时引入计价因子表示公汽计价方式计算乘车费用。

我们在5.1.5中设计了适当的算法并用Visual C++编程计算，得到各个目标值如下：按照起始站→终到站, 换乘次数, 总时间, 总票价的顺序为S3359→S1828, 1, 101, 3；S1557→S0481, 2, 106, 3；S0971→S0485, 1, 128, 3；S0008→S0073, 1, 83, 2；S0148→S0485, 2, 106, 3；S0087→S 3676, 1, 65, 2；详细结果及分析见5.1.6和附录1；同时我们还在5.1.7和5.1.8中讨论了适当增加换乘次数对乘车时间和费用的影响。

问题二同时考虑加入地铁的情况。

我们假定只有公汽换乘地铁和地铁换乘公汽两种情况。

乘地铁消耗的时间类似乘公汽消耗时间可计算得出；因换乘消耗的时间与初始的交通方式相关，我们引入了起点乘车方式因子λ。

总乘车费用类似问题一的情况可得。

利用Visual C++编程计算，我们得到此时各目标值如下：起始站→终到站, 换乘次数, 总时间, 总票价, S3359→S1828, 2, 101, 5；S1557→S0481, 2, 117, 5；S0971→S0485, 2, 96, 5, 13, 20；S0008→S0073, 2, 65.5, 5；S0148→S0485, 2, 87.5, 5；S0087→S 3676, 0, 33, 3；详细结果及分析见5.2.6。

出行系统中最优路线选择问题摘要本文在附件提供的公共交通信息的基础上，把所给数据处理成一个公交信息矩阵，便于Matlab软件的操作计算．从转乘次数出发逐层次地进行了较为深入的分析，将出行时间，出行费用，转乘次数三个方面综合起来考虑，最终选择出满足各种消费者的比较理想的出行线路选择方式．对于问题一，由公交信息矩阵得到所有站点的邻接矩阵，利用Floyd方法计算出任意两站A，B最少需要停靠的站点数，从而估计出两站间所有路线所需时间的下限．显然，因为转乘需要花费时间和增多费用，所以单方面考虑路线费或者是乘车费用，最优路线的换乘次数是有限的．由此给出定理一，由起始点A经过n次换乘到达终到点B的最短时间是时间最优解的充分条件为：对于换乘次数为n的最少费时路线，所需时间小于或等于(n+1)*5+3*(A，B最少需要经过的站点数)，则该路线是全局时间最优．这样，记录经过所给始末站点的全部公交车次，确定起始站和终到站之间是否可以有直达的车．如果有，统计出全部可以直达的车次，记录直达车经过的站点数以计算费用，由定理一判断出是否最优，若是最优，计算出具体时间，加权综合进行比较．如果不能直达，或者不是最优，则考虑所有由起始站经过一次换乘到达终点的情况．依此类推，考虑两次，三次…换乘，直到满足换乘到达终点并且满足定理一的条件为止．最后利用层次分析法根据消费者的不同需求加权选择出较为理想的线路．具体结果见表3(第7页)．对于问题二，首先将地铁系统作为单独系统考虑，用Floyd方法计算出地铁系统中任意出入口地铁行驶的最短时间；然后将地铁系统当成两个点集与公交网络相连，用问题一的算法，求出最少费时路线．综合考虑消费者的不同需求利用层次分析法加权选择出较为理想的线路．具体结果见表5(第10页)．对于问题三，在问题一和问题二的基础上，我们可以对模型进行简化，从而直接给出比较理想的线路选择．关键词：公交网络，换乘，时间，费用，Floyd算法，层次分析法(Analytic Hierarchy Process)，最优方案1．问题重述我国人民翘首企盼的第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．基于费用和方便性的考虑，假设一次出行只进出一次地铁系统，并且在到达地铁系统之前若需要乘坐公交车，最多只转乘一次，出地铁系统之后也同样做这个假设．7．步行一站的时间是大于5分钟的，因此基于时间性的考虑，我们假设步行最多走两站．３．重要变量解释A起始点B终到点P 公交车次和公交车次之间的邻接矩阵，其元素分别为1和0表示两车之间是否可以进行换乘L(A) 经过起始站A的所有公交车次集合，其中元素是j1，j2，…，j m L(B) 经过终到站B的所有公交车次集合，其中元素是k1，k2，…，k nS jp(1≦p≦m) L(A)中j p这辆车能够经过的站点集合S kq(1≦q≦n) L(B)中k q这辆车能够经过的站点集合T(D) 地铁系统所有出入口组成的集合S(D) T(D)中出入口对应的公交车站组成的集合w 层次分析法中的权系数(时间相对于费用的重要性，w越大，时间因素对结果的影响越大)注：其它临时变量在文中会有解释４．模型分析对于问题一，由于公汽行驶路线是固定的，对于只乘坐公交车的出行方式，若能直达，则费用能实现最小，但是就时间来讲不一定是最优值．我们可以利用Floyd算法给出两点之间经过的最小站点数，估计出时间的下界，并且进一步利用定理一确定出时间的最优值．但是对于时间的最优值，可能会出现要转乘多次的情况，而时间也没有节省多少．因此从实际情况出发，我们利用离散模型中的层次分析法进行分析，得到综合最优路线，也就能得到满足不同消费者不同要求的方案．问题二加入了地铁．从所给的数据可以看出，在地铁系统中的花费是常数，而且地铁的运行速度比公交车快很多．根据实际情况，可以想象，消费者都是以地铁作为首先选择的．我们可以将地铁系统单独提出来，相当于分段进行解决，并且可以利用问题一的算法．从实际情况出发，我们也能够得到综合最优解．最后可以综合问题一，重新利用层次分析法对方案进行加权处理，提供足够满足消费者要求的各种方案．问题三又进一步加入了步行，根据我们提出的假设7，可以这样分析：假设人步行一站来代替只坐一站的公交车，设人步行的时间是t，则比坐公交车节省1元，而时间多了(t-8)分钟；用人步行两站代替乘坐两站的公交车，节省一元，而时间多了(2t-11)分钟．根据这两个数据得到新的方案，加入层次分析法进行讨论．定理一：由起始点A经过n次换乘到达终到点B的最短时间是时间最优解的充分条件为：对于换乘次数为n的最少费时路线，若所需时间小于或等于(n+1)*5+3*p，则该路线是全局时间最优．p为A和B之间最少需要经过的站点数．证明：设经过n次换乘所需要的最短时间为t，经过n+1次换乘所需要的最短时间是t1．若t不是时间最优解，我们设t1(<t)是时间最优的，则t1不小于所有经过n+1次换乘线路所需时间的下界，即t1≧5*(n+1)+3*p而由已知：5*(n+1)+3*p＞t说明t≤t1,与假设矛盾．定理得证．5．模型的建立和求解5．1 问题一的建立和求解我们从换乘次数出发，首先建立一个公交车次和公交车次之间的邻接矩阵P，来反映两辆公交车j，k是否能至少经过同一个站点，即两车之间是否可以进行换乘，分别用P(j,k)=1或P(j,k)=0表示．先考虑不需要换乘的情况．算出可以经过起始站A的所有公交车次，即集合L(A)，以及可以经过终到站B的所有公交车次，即集合L(B)．若有公交车m ∈L(A)且m∈L(B)则说明从A到B可以通过公交车m直达，判断是否达到时间的最优解，并综合时间，费用两方面，找出能够直达的情况中相对最好的．再考虑需要转乘一次的情况．设L(A)中有m个元素，分别是j1，j2，……j m；L(B)其中有n个元素，分别是k1，k2……k n．若存在j p∈L(A)(1≦p≦m)，和k q ∈L(B)(1≦q≦n)使得P(j p，k q)=1，则说明A，B两点可通过j p，k q两辆公交车转乘一次到达．另外，记L(A)中j1这辆车能够经过的站点集合记为S j1，L(B)中k1这辆车能够经过的站点集合记为S k1，以次类推．将S jp(1≦p≦m)和S kq(1≦q ≦n)两两作交，若有s同时属于S jp和S kq，则s就是中转站．也就是说从A点可以乘坐j p到s然后转乘坐k q达到B．判断是否达到时间的最优解，同时从所有这种转乘一次的情况中找出所需时间最短或所需费用最少的方案，并可以与直达情况进行比较．进一步考虑需要转乘两次的情况．首先搜索这样的公交车d，d满足P(m，j p)=1且P(m，k q)=1，这就说明从A点乘坐j p出发，通过换乘d再换乘k q到达B．判断是否达到时间的最优解，同时从乘坐两次的情况中找出所需时间最短或所需费用最少的方案，并与上面两个方案进行比较．同理可以处理转乘三次及三次以上的情况．对于三次以上的情况，虽然可以通过计算确定它们会缩短一些时间，但缩短的程度不会很大，尤其进一步考虑费用和方便性，结合实际情况，这种线路的利用性不会很强．事实上，转乘三次之内的方案，虽然不能说它一定就是时间的最优，但综合时间，费用以及方便性，我们可以说它就是最优的．第二步，我们可以利用Floyd算法给出从A到B的最小站点数，用来估计(表1)第三步，因为考虑到转乘次数的增多会使费用升高，同时时间也不会降低太大的幅度，我们仅在下面的表2中给出6条路线分别转乘一，二，三次的的情况，它们都实现了局部（对于转乘次数）费用的最优，另外给出了全局时间最优解，作以比较．需要注意的是所有的线路都没有直达车，S1557→S0481和S0148→S0485两条线没有转乘一次到达的车．(表2)最后一步，我们用层次分析法对消费者的各种需求进行决策，从而挑选出最合适的路线推荐给消费者．关于层次分析法的操作，我们做如下说明：1)对于指定的一条线路，将决策问题分解为3个层次，最上层为目标层，即选择线路方案；最下层是方案层，有m 个选择方案；中间层为准则层，有费用和时间两个准则，个层间的联系用相连的直线表示，如图2(图1 )2)通过消费者的不同侧重来确定个准则对于目标的权重，以及各方案对于每一个准则的权重，这些权重在人的思维过程中通常是定性的．3)将方案层对准则层的权重及准则层的权重进行综合，最终确定方案曾对目标层的权重，得到最终的决策结果，也就是线路选择结果．现在，我们以图表的形式给出满足消费者各种需求的最佳路线.(表3)5．2问题二的建立和求解第一步，首先我们将地铁系统考虑成一个独立的系统，所有出入口组成的集合记为T(D) ，这里需要对出入口的个数进行一个处理．从附件中可以看出，D012和D018地铁口是环行地铁和直行地铁的换乘点，而这两条地铁不可能是在同一层的，因此事实上地铁系统中是有两个D012和两个D018，我们需要对它们进行区别，具体的做法是用D040和D041来替换T2中的D012和D018．做41*41的邻接矩阵Q，对于任意D i∈T(D)和D j∈T(D)，若D i和D j在一条地铁线上相邻，则权为2.5，也就是地铁经过D i和D j行驶的时间(单位：分钟)，另外特别的，D12和D40之间以及D18和D41之间的权是4，也就是转乘地铁需要的时间，若D i和D j不相邻，权为∞．由于地铁是双向行驶的，因此Q是对角线为0的对称矩阵．图2这样，利用Floyd算法，可以求出地铁系统中任意D i和D j之间所需要的最短时间．第二步，将地铁系统放入大环境中，记T(D)中出入口对应的公交车站组成的集合为S(D)．首先分析A，B与S(D)的关系，具体分为以下3种：1）A∈S(D)且B∈S(D)，说明要从起始站A到终到站B不用坐公交车，可以通过地铁直接到达．2）A∉S(D)，B∈S(D)，说明在进入地铁系统之前需要乘坐公交车．3）A∉S(D)，B∈S(D)，说明在离开地铁系统之后需要乘坐公交车．4）A∈S(D)且B∉(D)，这种情况相对复杂，它说明要想通过地铁实现从A 到B的路线，在进入地铁系统之前并且离开地铁系统之后都需要坐公交车．对于第二种情况，我们采取这样一种方法来寻找需要选择的公交线路，将其称为一维搜索法：对于任意p∈S(D)，p 代表进入地铁系统的入口，我们将它想象成一个新的终到站，利用解决问题一的算法，建立起始站A到终到站p的新模型，根据假设，我们只需要考虑有直达的公交车或者转乘一次到达的公交车．第三种情况同理可以解决，将任意q∈S(D)，q代表离开地铁系统的出口，想象成一个新的始发站，建立起始站q到中终到站B的新模型，也只考虑有直达的公交车或者转乘一次到达的公交车．之所以称为一维搜索法，主要是想突出只需要从S(D)中选择一个变量遍历．这两种情况事实上是将起始站A到终到站B分成了两段，这两段加起来所需要的时间和费用都是很容易算出来的．第四种情况要更复杂一些，我们采用二维搜索法来解决：对于任意p,q∈S(D)，p，q分别代表进入地铁系统的入口和离开地铁系统的出口．同样将p想象成一个新的终到站来建立起始站A到终到站p的公交模型，同时要将q想象成一个新的始发站，建立起始站q到中终到站B的公交模型．之所以称为二维搜索法，主要也是想突出需要从S(D)中选择两个变量遍历．这一种情况事实上是将起始站A到终到站B分成了三段，这三段加起来所需要的时间和费用也都是很容易算出来的．第三步，我们分别从时间和费用方面来分析一下得到的数据．在乘坐地铁这一段，费用是常数3元，而时间我们已经求出来是最短的，因此在这一段时间和费用都达到了最优．在乘坐公交车的路段上，因为是沿用了问题一的算法，因此可以说我们可以找到一种时间相当不错而费用达到最优的线路．下面的表3给出了一些非常好的路线的详细情况，需要注意的是，“直达”表示起点A和终点B都有直接到达地铁系统的车次；“经转一次”的意思是在进入地铁系统前或离开地铁系统后乘坐公交车会有一次转乘的情况．另外，我们是从最优时间进行考虑的，没有填写的项目都是直接被排除了(表4)最后，综合问题一，重新用层次分析法对消费者的各种需求进行决策，从而挑选出最合适的路线推荐给消费者．见表5(表5)5．3 问题三的特殊情况由于时间问题，我们对问题三没有做出比较到位比较好的解决．我们现在能够找到一条比较好的可以通过步行走的路线．这条路线本来是从S0087乘坐一站下行L021至S0088转坐10站环行L231至S0427转坐一站下行L462到达S3676．因为有两辆公共汽车分别只坐了一站，于是我们可以从S0087步行到S0088然后乘坐10站环行L231至S0427然后步行到S3676，这样只要1元钱，但是时间增加了．6．模型总结评价及优缺点分析本模型在对问题一的解决上先给出了n次换乘时间最优解问题的时间下界，为我们进一步利用定理一来判断是否达到时间最优解做了很好的准备工作；从换乘次数出发，并且加以利用动态规划方法，不仅给出了时间最优解，而且为最后的层次分析法提供了宝贵的数据；从实际出发，使用离散模型中的层次分析法给出满足不同消费者的不同要求的最理想路线．问题二是建立在问题一的基础上的，给出了比较好的线路，并且综合第一问利用层次分析法给出满足不同消费者的不同要求的最理想路线．另外，某些符合客观实际的模型假设极大地简化了模型，使求解变得更加方便．但是在问题三的处理上确实不够理想，有想法但是还没有具体实现，最好的想法就是能够结合三个问题使用不同权重的层次分析法，但是很遗憾我们还没有做到．另外还有一个比较遗憾的地方就是我们没有把问题二的时间最优给出来，而只是接近最优的时间，但是综合时间，费用方面来看，这个近似最优解是合理的．7．参考文献[1]姜启源谢金星叶俊，数学模型(第三版)，高等教育出版社：224—226页，2006年[2]张乃孝裘宗燕，数据结构(修订版)，高等教育出版社：325—326页，2003年。

On the Mathematical Models and Algorithms of Optimal Public Transport Lines 作者： 王庆;潘荣英
作者机构： 苏州市职业大学数理部,江苏苏州215104
出版物刊名： 苏州市职业大学学报
页码： 58-61页
年卷期： 2014年 第4期
主题词： 公交;Dijkstra算法;最优路径
摘要：通过对城市公交路径选择问题的分析,在常用的Dijkstra最短路径算法基础上进行改进,根据乘客的不同需求给出出行总距离最短、出行总费用最少、出行总时间最短的最优路径选择模型.综合考虑距离、时间、费用等多种因素给出的出行满意度最大的最优路径模型,同时以算例验证了模型和算法的合理性和实用性.。

公交车的定位方式以及预测公交到站的数学模型随着城市快速发展，公共交通服务已经成为人们出行的重要方式之一。

为了提高公交出行的效率和便捷性，公交车的定位方式和到站预测成为当前公共交通系统中的重点研究方向。

本文将介绍公交车的定位方式以及预测公交到站的数学模型。

一、公交车定位方式公交车的定位方式是指确定公交车在道路中的位置，并且能够实时更新位置信息。

目前，常用的公交车定位方式主要有以下几种：1.卫星定位系统（GPS）GPS是一种广泛应用于各种交通领域的定位技术。

通过安装GPS接收机在车辆上，可以实时接收到卫星发出的信号，并计算出当前车辆的位置信息。

GPS定位方式准确性高、实时性好，因此被广泛应用于公交车的定位。

2.基站定位基站定位方式主要用于没有GPS信号时的公交车定位。

当公交车进入固定的信号范围内时，基站可以通过接收到公交车的无线信号来确定其位置。

由于基站信号覆盖范围有限，因此基站定位方式的定位精度相对较低。

3.惯性导航定位惯性导航定位是一种基于车辆自身传感器测量实现的定位方式。

它通过测量车辆的加速度、角速度等参数来推算车辆的位置。

惯性导航定位方式的精度较高，但需要进行定位误差补偿以保证定位的准确性。

对于公交车的到站预测，通常采集公交车的历史到站记录建立数学模型。

常用的到站预测数学模型主要有以下几种：1.基于历史数据的统计模型基于历史数据的统计模型是一种简单有效的到站预测方法。

通过统计历史数据中相同时间段内到站的概率来预测当前公交车是否将到站。

这种方法能够准确预测到站时间，但受到历史数据的限制，预测精度可能受到影响。

2.基于时间序列的预测模型时间序列模型是一种常见的预测模型，通过对历史数据进行分析，建立公交车到站时间的时间序列模型。

预测时，根据时间序列模型来预测当前时间下一次到站的时间。

这种方法能够较为准确地预测到站时间，但需要大量的历史数据作为基础，还需要不断调整模型参数才能保持预测精度。

机器学习是一种利用算法从数据中自动学习和开发模型的技术。

市民对公交现状满意度0%10%20%30%40%50%60%优化城市公交线路站点的数学模型课题组成员：汕头一中高一（3）班：许毅、徐栩、吴岳峰、江琳、李奕莹、李晓枫、林木松、林枫润课题组长：许毅 相关课程：数学 指导老师：汤威摘要：本文讨论的是日常生活中公交线路设站选址的合理性问题。

主要针对本市第20路公交车的运行状况及其设站选址进行调查研究，通过建立数学模型，对现有的设站选址进行评价和改进，阐述我们对“合理选取城市公交线路站点”的看法。

首先根据实地调查、访问得到的真实数据，在现有的设站选址基础上找出弊端，运用已有的数学、经济学、统计学知识，建立数学模型，然后对模型加以修改，使修改后的模型更具合理性。

接着，为了弥补修改后的模型仍存在的不足，又重新建立了一个新的模型——高峰期辅助路线。

新的模型与改进后的模型并用，将能发挥更大的作用。

关键词：设站选址、满载率、运行效率、公交站点一、问题的提出公共交通作为城市交通动脉的重要组成部分，关系到百姓生活的切身利益。

良好的交通状况，对带动城市经济持续、健康、稳定的发展，发挥着越来越重要的作用。

公交事业的发展受到广泛的关注，而在百姓对公交事业表现出强烈需求的情况下，根据一份我们对汕头市乘客的调查显示，有50%以上的人对公交现状持勉强接受的态度。

认为基本满意的不到40%，甚至有一些人对公交现状表示极为不满。

这一调查充分说明了现行公交状况无法满足乘客的需求。

如何通过合理设站选址优化城市公交线路站点，以完善城市交通状况，方便市民出行，提高公交车的运行效率，将是我们探讨的重点。

图一二、对数学模型的假设和说明由于本课题所涉及到的实际干扰因素繁多，其影响无法估计，故需在此做一些假设和说明，排除一些次要因素的影响，才有可能建立数学模型。

1． 题目中所调查来的20路一个工作日高峰期客流量统计数据是具有代表性的。

2． 其他工作日高峰期客流量大致相同。

3． 公交线路上的所有车辆正常运行。