公交线路选择模型与算法

公交线网规划的模型与算法的开题报告一、研究方向：公交线网规划的模型与算法研究二、研究内容：公交线网规划是交通规划和公共交通运营的重要组成部分，对城市交通运行和出行有着至关重要的影响。

本研究将围绕公交线网规划的模型与算法展开研究，主要内容包括以下三个方面：1. 公交线网规划模型的建立针对当前公交线网规划中存在的问题，如公交线路布局不合理、车辆调度不科学、线网转乘尚未优化等，本研究将以城市规模和空间布局为考虑因素，建立合理、可行、优化的公交线网规划模型。

2. 公交线网规划的算法设计本研究将调研和借鉴国内外相关文献和成功案例，深入研究公交线网规划中的优化算法，如最优配线、网络流模型、动态调度等，并将针对不同城市规模和特点，设计符合实际情况的优化算法。

3. 算法实现与应用验证本研究将基于设定的模型和算法，结合实际城市公交线网规划，编写相应的算法实现程序，通过仿真和实际应用验证算法的可行性和优越性。

三、研究意义：公交线网规划模型与算法的研究具有重要的理论和实践意义。

理论上，本研究可以通过分析、总结、总结国内外各种公交规划模型的优缺点，在此基础上建立更为合理、可行的公交线网规划模型。

实践上，研究结果可以为城市公交规划的实际操作提供更具可行性的指导和依据。

四、研究方法：本研究将运用多种研究方法，包括文献研究、案例分析、调查问卷、数学模型和计算机仿真等，以期达到最佳的研究成果。

五、研究预期成果：本研究的预期成果包括：针对城市不同规模和特点建立公交线网规划模型；设计优化的公交线网规划算法；开发相应的算法实现程序；实际应用验证算法的可行性和优越性；论文撰写和发表。

六、研究难点和问题：1. 公交线网规划模型的建立涉及到城市规模和空间布局等多方位因素的考虑，需要通过大量实证研究和数据分析，加深对相关因素的理解和把握。

2. 公交线网规划的算法设计需要深入研究各种优化算法的原理和应用思路，以保证算法的严谨性和实用性。

3. 算法实现与应用验证需要寻找合适的实际应用场景和大规模数据集，以帮助验证算法的可行性和性能表现。

北京市公交最优乘车路径选择的数学模型摘要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一致。

公交路线中最优路线的查询算法设计与实现1．摘要本文针对公交线路选择问题建立了相应的数学模型，并给出具体算法以实现查询最优路线的目标。

针对问题一，在仅考虑公汽线路的情况下，我们根据公汽线路信息建立一个广义邻接矩阵，以存储任意两公汽站点之间的相关信息。

基于该矩阵可以查找出任意两站点之间的所有可通路线。

然而，考虑到公交系统如此庞大，任意两站点间的路线都有可能又多又复杂，查找算法的实现将耗费大量的时间。

而另一方面，查询者并不关心两站点间的所有路线，只是希望根据个人的需求查询到相对最优的路线。

因此我们结合实际，借助站点的广义邻接矩阵，以换乘2次为上限，查找从指定的始发站到终点站间所有可通的路线。

充分考虑到查询者的需求，我们定义四种不同的查询方式，分别为：少换乘、少步行、较快捷、较经济。

然后以查询者的具体需求(即查询方式)为首要决策变量，并扩充查询系统的实力，建立多目标动态优化模型，在局部最优的基础上，给查询者提供全局最优路线。

对于问题二，分两步考虑：1).不考虑地铁与公汽之间换乘的信息，单独利用地铁线路信息扩充问题一中的广义邻接矩阵，使之包含任意两公交站点(包括公汽站点和地铁站点)之间的相关信息，实际上这里公汽站与地铁站之间没有任何联系；2).考虑到地铁与公汽之间换乘的信息，我们把每个地铁站以及它所对应的所有公汽站组成一个站点集合，则同一集合中的站点可以通过步行连通；当指定始发站和终点站时，问题转化为查询这两站点分别对应的站点集合之间的最优路线。

利用问题一中的查找算法，以1)中得到的扩充后的邻接矩阵为参数信息，查找所有中转站，将中转站对应为相应的中转站点集合。

遍历始发站集合、中转站集合、终点站集合的所有元素组合，可以得到始发站到终点站的所有路线；最后根据查询者的需求查找最优路线。

问题三已知所有站点之间的步行时间，则所有站点可以通过步行连通，构成一个站点集合，等效于问题二中的站点集合，则可利用问题二的思想求解。

乘公交，看奥运摘要本文讨论了从众多可行线路中根据乘客的不同需求选出最优线路的问题，属于最优路径的选择问题。

在选择路径时，我们采用了广度优先遍历算法。

对于问题一，首先利用MATLAB编程将公交线路及其信息储存在元胞数组中，在仅考虑了公汽线路的条件下，建立了3个评价指标，即花费的时间T，所需的费用C和换乘次数j。

在选择最优线路时，采用广度优先遍历算法，遍历出换乘次数不超过2次，经过起始点和终点的所有线路，并根据3个评价指标对路线进行评估。

对于要求出的6条线路，利用MATLAB软件编程，最终求出了分别以换乘次数最少，花费时间最少，所需费用最低为查询要求的最优线路（见表6.1,6.2）。

对于问题二，我们将地铁线路、地铁站当做新的公汽线路、公汽站，将公汽站和地铁站的转乘站当做二者的交汇点，在同时考虑了公汽线路和地铁线路的条件下，建立了4个评价指标，即花费的时间T，所需的费用C，公汽换乘次数j，和地铁的换乘次数f。

在选择最优线路时，采用广度优先遍历算法，遍历出公汽和地铁换乘次数都不超过2次，经过起始点和终点的所有线路，并根据4个评价指标对路线进行评估。

对于要求出的6条线路，利用MATLAB软件编程，最终求出了分别以换乘次数最少，花费时间最少，所需费用最低为查询要求的最优线路（见表7.1,7.2）。

对于问题三，在问题二的基础上，把步行当做新的交通选择方式，将任意两个站点之间花费的时间分为公交的行驶时间和乘客的等待时间，建立了5个评价指标，即花费的时间T，所需的费用C，公汽换乘次数j，地铁的换乘次数f和步行时间P，如果所求的线路满足设定的要求，则可以选择步行方式。

关键字：最少换乘次数最小费用最短时间广度优先遍历一、问题重述1.1 问题背景随着我国经济社会的迅猛发展，作为城市人们主要出行工具的公共交通（简称公交，包括公汽、地铁等）亦发生了翻天覆地的变化，城市越变越大，人们能够选择的公交线路也越来越多，并往往难以一站到达。

公交乘车最优线路的数学模型与算法
蔺焕泉
【期刊名称】《长春大学学报》
【年(卷),期】2008(018)006
【摘要】本文运用图论理论，建立了公交乘车优化模型。

用换乘矩阵描述换乘公交的次数，计算出换乘的次数以及乘车所耗费的时间。

运用数据库中遍历的方法，计算出乘车最优线路。

【总页数】5页(P19-23)
【作者】蔺焕泉
【作者单位】长春大学应用数学系,吉林长春130022
【正文语种】中文
【中图分类】O224
【相关文献】
1.公交最优路径选择的数学模型及算法 [J], 雷一鸣
2.城市公交最优路径选择的数学模型及其算法 [J], 王庆;潘荣英
3.洛阳公交最优乘车线路模型 [J], 张国利;刘晓姣
4.最优公交线路选择问题的数学模型及算法 [J], 周文峰;李珍萍;刘洪伟;王吉光
5.公交乘车最优线路的数学模型与算法 [J], 蔺焕泉
因版权原因，仅展示原文概要，查看原文内容请购买。

B题：重庆市主城区公交线网的优化与评价姓名学院年级专业学号联系电话相关学科成绩高等数学线性代数概率统计数学模型数学实验英语四级英语六级徐清鹏09电气学院07班0989 87573 475张雅洁09电气学院01班0991 75566 480刘维09电气学院0109 92 83 525重庆市主城区公交线网的优化与评价摘要: “畅通重庆”是建设五个重庆的战略目标之一，通过有效融合公交网和轻轨网的,是实现这一目标的有效途径。

因此对重庆市主城区现有的地面公交线路进行优化和调整具有十分重要的意义。

针对问题一：采用定性与定量相结合的递阶层次分析法(AHP)对重庆市市现有的公交线路网现状进行进行分析，筛选了与公交线路网评价有关的四个方面（线路网络能力、客运能力、经济效益、环境影响）下的12个主要指标建立模型。

建立各个层次的判断矩阵，通过MATLAB 软件计算各个方面的总权重值并进行排序，并采用一致性判断指标决定判断的合理程度。

最后采用线性加权的的方法建立综合评价模型：N =∑E 1i ω1i +∑E 2i ω2i +∑E 3i ω3i +∑E 4i ω4i 3i=13i=13i=13i=1依据查询在重庆市主城通行的公交车数据及与选取指标相关数据，计算出各指标的有关系数，并参照公交线网络指标评价标准的建议值对各个指标评分，得出其得分为，等级为中。

针对问题二：鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra 算法,而是采用了基于公交停靠站换乘功能进行OD 预测。

算出铁路（或轻轨）停靠站的公交客运量。

同时建立了分别以剩余客流量,接运站点数量为目标的优化模型。

然后对OD 客流量剩余值进行确定，得到的由三部分（需要保留的路线，改变的路线布设，合并和消除的路线）构成的“轨道-接运公交网”。

针对问题三:我们主要以轻轨地铁路线为主干线对重庆市主城的公交线路进行规划设计。

由于规划年限较短，我们对乘坐公交的人口，公交车数量，客流量等因素采用马尔萨斯（Malthus ）模型。

最佳公交线路的实时查询模型及算法摘要本文针对查询者的不同需求，为公交查询系统提供了最佳线路查询的模型与算法。

查询者的需求从换乘次数少、时间少和费用少三方面进行考虑。

故查询算法从换乘次数（从实际出发，换乘不超过两次）入手：对直通的任意两站点，可设计出较简单的最佳直通线路查询算法（直通算法）。

故对需要查询的两站点，算法先由线路、站点的原始数据判断此两站点是否直通，若是，便可通过直通算法进行查询。

不论是否存在直通线路，算法都考虑对换乘的情形进行查询。

考虑到城市公交系统中的站点基数较大，可行的换乘方案数也将较大，故查询算法根据所有可行的一、二换乘点必与起、止站点直通的原则，对可能成为给定两站点的换乘点的站点进行了筛选，得到相关站点集，较大的缩小了查询的范围。

得到相关站点集后，建立了反映站点集中任意两站点直通关系的连通矩阵，并通过矩阵乘法，较快地得出了所有可行的一次、二次换乘点。

考虑到所有可行的换乘点可能较多，特别是二次换乘的情形，故查询算法采用分支定界法以较高效率对最佳方案进行了最后的筛选。

在考虑地铁的公交系统时，本文从实际出发，对模型进行了一定的修改。

同时，本文考虑了引入站点之间的步行时间的情况，提出了线路选择的模型。

由于筛选算法、矩阵乘法和分支定界法的高效性，整个查询算法具有很高的效率，并能在换乘次数不超过两次的条件下，求得全局最优解，得出满足查询者不同需求的所有最佳方案。

并且，从系统设计的角度出发，整个系统需要预存的数据量很小，系统的实用性很强。

对给定的六对站点，采用本算法进行查询，在1.7GHZ的CPU环境下，平均运行时间为：1.27秒，最长运行时间为7.43秒，验证了算法的实时性。

同时，对每一对站点，得到了满足不同查询需求的所有最佳线路方案，验证了模型与算法的精确性。

关键词：最佳线路、实时、筛选算法、分支定界一、问题重述第29届奥运会将于今年8月在北京举行，届时有大量观众到现场观看比赛，其中大部分人将乘坐公共交通工具（包括公汽、地铁等）出行。

承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：数模指导组日期： 2011 年 8 月 26 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公交查询系统的研究与设计摘要本文旨在设计一个解决公交线路选择问题的自主查询计算机系统。

问题一，鉴于实际生活中公交路线复杂多样，我们将不同公交线路抽象化。

把公汽换乘和直达综合考虑，模型比较复杂，所以我们首先建立公汽直达数据库Q，用户查询时，系统首先查询Q，得到所有直达车方案。

在需要转乘时，针对不同用户需求，分别以转乘次数最少、总耗时最短、总费用最少为目标，量化不同目标为有向赋权图的不同权矩阵，始、终点连通为约束建立 0-1 整数线性规划模型来设计最佳路线。

为了能提供多种公交线路备选方案，我们首先使用基于Dijkstra 的邻接算法求解，得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们采用Lingo 软件直接求得全局最优解。

综合方案集(见5.1.6模型表1.1-1.6)，其中6条线路时间最短目标分别为67、102、106、62、105、49(分钟)。