公交最优路线乘模型.doc

公交最优路线换乘模型 摘 要 本文主要针对大量观众到 2008 年奥运会现场观看奥运比赛的出行问题进行 分析，对出行面临的多条公交线路的选择问题进行剖析，对公交的转乘情况进行 了尽可能的详尽研究。在对人们的出行行为习惯和心理因素进行统计分析的基础 上，并结合实际建立可行的模型与算法。为公司开发解决公交线路选择问题的自 主查询计算机系统提供理论依据。 首先，我们对附件中的公交信息数据进行处理，把数据换成统一的形式，即 每条线路均有上行线和下行线。然后，对各个问题分别进行建立模型和算法。 针对问题一，我们采用了基于最小转乘次数和最短出行时间的公交网络拓扑 模型，本模型根据实际的调查分析，考虑两种判断标准： （1）建立一个以转乘次数最小为第一目标、以出行时间最短为第二目标和 以出行费用最少作为第三目标的模型与算法。在所有可到达的线路中选择转乘次 数最小值 N，再选出满足条件的各条途经总站数 M ij 。并在此情况下找到出行时 间 t 最短的目标函数: t = min{t j / t j = 5* N + 3*(Mij ?1)，j=1,2L k)} (分钟)。 （2）在第一目标条件下考虑以出行费用最少为第二目标和以出行时间最短 作为第三目标的模型。模型的算法采用了结构体的存储方式，便于数据的调用。 最后，根据算法编写程序并在计算机中运行，得出相应的结果。 针对问题二：我们采用与问题一同样的思想来建立模型和算法，但由于地铁 信息数据与公交的不统一，模型和算法更加复杂。我们采用把相近的各公交车站 （地铁站附近）看作一点来考虑。另外我们将地铁线路图绘制出来后，利用网络 拓扑和图论的相关知识进行求解，我们设计了此种情况的算法。 针对问题三：我们主要考虑相近的不同站点间的步行时间，采用时间阻抗函 数最小为转乘的选择标准。 问题一结果： 关键字：换乘次数 拓扑模型 数学描述 最优公交路径 时间阻抗函数 Dijkstra 改进模型 一、 问题的重述 随着城市建设的飞速发展及公交系统的不断完善，公交车已成为城市居民出 行的主要交通工具。但由于城市公交线路四通八达，且随着城市扩建而快速发展， 新的公交线路在不断延伸和开辟，再加上单行道、禁左等道路交通约束，即使是 当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出 行的路径信息。因此，在2008年奥运会来临之际，北京应建立适合于公交线路查 询特点的公交数据模型，开发操作直观、便捷、快速、准确的城市公交查询系统， 为出行者提供全面、准确的公交信息，帮助出行者快速地选择出行路径、换乘路 线等,提升出行者的效率,优化公交资源的配置,提高交通运输的效率和城市的信 息服务化水平。 针对这种情况要求我们设计一个系统，其核心是线路选择的模型与算法，能 够从实际情况出发，满足查询者的各种不同需求。并解决以下三个问题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模 型与算法。并根据附录数据，利用所建立的模型与算法，求出以下 6 对起始站→ 终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，建立任意两站点之间线路选择问 题的数学模型。 二、 模型的假设条件 1. 所有站点和路线的数据都是准确的； 2. 相邻公汽站的行驶时间相等(包括停站时间)： 3 分钟； 3. 相邻地铁站的行驶时间相等(包括停站时间)： 2.5 分钟； 4. 公汽换乘公汽耗时相等： 5 分钟(其中步行时间 2 分钟)； 5. 地铁换乘地铁耗时相等： 4 分钟(其中步行时间 2 分钟)； 6. 地铁换乘公汽耗时相等： 7 分钟(其中步行时间 4 分钟)； 7. 公汽换乘地铁耗时相等： 6 分钟(其中步行时间 4 分钟)； 8. 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的 票价为：0～20 站：1 元；21～40 站：2 元；40 站以上：3 元 9. 顾客在车站等候各站车的时间相等，且仅考虑从起始站出发后开始计时，直 到到达终点站所需时间； 10.只考虑至多二次换乘的情况。 注：上述是模型假设讨论过程中的全局性假设，在后面的分布讨论中我们可能引 入新的全局性假设。 三、 符号说明 1. V（G）表示所有公交站点的集合； 2. TR = {TRi TRi ≤ (s0 , li1 , si1 , li 2 , si 2 ,L , sd )}(i = 1, 2, 3L , n) ，是包含起点 s0 和终点