课程设计最佳乘车路线

《课程设计最佳乘车路线》由会员分享，可在线阅读，更多相关《课程设计最佳乘车路线（14页珍藏版）》请在金锄头文库上搜索。

1、 论文题目：最佳乘车路线论文题目：最佳乘车路线 论文作者论文作者 1 1： 学号：学号： 班级：班级： 在设计中你的工作：写作 程序设计 构建模型及应用论文作者论文作者 2 2： 学号：学号： 班级：班级： 在设计中你的工作：写作 程序设计 构建模型及应用论文作者论文作者 3 3： 学号：学号： 班级：班级： 摘要：摘要：本文针对公交线路选择的自主查询计算机系统的研制开发问题，以乘坐公交 车路程最短、花费最少和换乘次数最少为前提，分别以任意两线路之间的换乘 次数为 0 次、1 次和多次为方案建立了图与网络模型，给出了公交线路选择的 合理方案。 我们利用 Excel 函数求解换乘次数为 0 次或

2、 1 次时，可以筛选出任意两公汽 站点之间的最佳线路；根据图与网络模型中的最短路径的 Dijkstra 算法和弗洛 伊德算法，可以求出换乘次数为任意数目时，任意两公汽站点之间的最佳线路。利用 Excel 函数，制作公交向导，可以筛选出任意两公汽站点换乘次数为 0 次 或 1 次的公交向导。这样就方便了乘客的查询。 由于北京的公交线路众多，根据图论中最短路径的求法，利用 Dijkstra 算 法及其改进的算法和弗洛伊德算法则能够解决乘坐公交车需要转两次或多次车 的情况。我们是用 C+及 Matlab 等编程工具，分析了 Dijkstra 算法在改进后 的实用性,经过运算得到相应的结果如下：指定站

3、点公交线 路上车站 点下车站 点换乘次数 （次）乘车费用 （元）所需时间 （分钟）L436S3359S1784S3359S1828L217S1784S182813101L363S1557S1919L189S1919S3186S1557S0481L460S3186S048123106L013S0971S2184S0971S0485L417S2184S048513128L463S0008S2083S0008S0073L057S2083S00731283S0148S0485L308S0148S003623106L156S0036S3351L417S3351S0485L454S0087S3496S00

4、87S3676L209S3496S36761265从而验证了模型的执行力。我们结合了两种方案的有缺点，对公交车站模型 进行了进一步的分析，并提出了较为合理的建议。 关键词：关键词：公交线路选择 图论 最短距离 弗洛伊德算法 Excel 应用一、问题的提出一、问题的提出公交线路的选择问题是城市公交系统发展的核心问题，它可以满足查询者的 不同需求，使得公众的出行更加通畅、便利，所以，在这种情况下，研制开发 解决公交线路选择问题的自主查询计算机系统对城市的公交系统至关重要。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况 出发考虑，满足查询者的各种不同需求。因此我们主要解决如下问

5、题： 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与 算法。并根据附录数据，利用设计出的模型与算法，求出以下 6 对起始站终 到站之间的最佳路线：(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的 数学模型。二、符号说明二、符号说明G = ( V , E , L ) 无向图（公交网络） V m 个 节点构成的点集（公交站点） E

6、n 条边 构成的边集（公交车站间线路） L 路权集（公交车站间路程） vi (i=1,2,3,N)- 站点名称代码 T 标号-临时标号 P 标号-固定标号 P , Q -v1 、终点 vN 开始的扩展点(固定标号) 集合 vm ,vn -P , Q 的当前扩展点; d ( v m) -起点到 vm 的最短路径 e ( v n)-起点到 v n 的最短路径三、问题分析三、问题分析本题的目的是针对市场需求，结合实际情况，在满足查询者不同需求的情况 下，设计出任意两个站点之间的最佳线路，研制开发一个解决公交线路选择问 题的自主查询计算机系统。 从任意两个站点之间的路线来看，有多种路线供乘客选择。而公

7、共交通工具 又分为公汽、地铁等，同时线路的选择还受乘车路程、乘车费用及换乘次数等 诸多因素的影响。 建立优化模型1是解决公交线路选择的最佳方案。结合实际情况，分别以 换乘次数最少和乘车时间最少分别作为目标函数提出两种开发方案。针对不同 方案所得结果，对其优缺点及其适用性进行评价。四、基本假设四、基本假设1、相邻两公汽站点之间距离相等。 2、所有公汽和地铁的乘车条件同样好。 3、不考虑堵车情况下，公交运力的分配。五、模型的建立五、模型的建立（一）乘坐公交车需要转两次或多次车的情况，我们运用图论中关于最短路程 的研究，进行套用，从而得出结果。 最短路径的算法研究，讨论最短路径算法及根据实际问题对经

8、典算法进行优化， 以提高运行效率。 1.连通性。 其中被广泛采用连通性城市道路网络中的道路交叉点无差异地 连接着与该路口连通的多条路段，而两路公交线路的站点在同一点时，同路公 交路段之间的连通性和不同公交线路的连通性是有差别的，这是因为两路不同 公交线路在空间上的同一站点的连通，要换车而增加了时间消耗。另外多条公 交线路虽然可以相交于空间上的同一个点，但是该点不一定是公交停靠站点， 或者不是同时有站点，因而不同公交线路在此是不连通的。 2.节点的特性。 虽然不同的公交线路在行程上有重叠，但是各自的站点不 可能是完全的几何重叠，因而要做有效的站点间叠加分析。在实际通勤中必然 要求在不同的公交线路

9、之间实现换车以到达目的地，这就要求相对应的网络图 上不同属性的边在节点上的连通，这是公共交通网络分析的意义。在公交网络 叠加分析时，要求把空间上相近的异线站点合理抽象成图. 线性规划的一类重要的应用是网络最优化的问题。我们用符号 G（V，E）来表 示，V 为节点集，E 为弧集。 最短路问题是对一个赋权的有向图 D（在本文中就是路程的长度）中的指定 的两个点 vs 到 vt 的最短路。这条路上所有弧的权数的总和被称之为 vs 到 vt 的距离。 则无向图 G = ( V , E , L ) 。其中, V m 个节点构成的点集; E n 条边构成的边集; L 路权集, 同时满足: (1) G 为一

10、个简单图, 不含环和多重边; (2) 路权具有可加性。若有路径 vi - vk - vj ,则有 l ( vi , vj) = l ( vi , vk) + l ( vk , vj) 求 A , B 间的最短路径 P 满足： min L =min l ( vi , vk) + minl ( vk , vj)最短路径算法：最短路径算法： 目前最短路径问题的最成熟算法是 Dijkstra 算法。Dijkstra 算法的思想 是:先给赋权图的每一顶点记 1 个数(称标号) ,临时标号( T 标号) 或固定标 号( P 标号) 。T 标号表示从始点到这一点还没有寻找到最短路径; P 标号则 表示从始点

11、到这一点已寻找到最短路径。计算的每一步是把某个点的 T 标号变 成 P 标号。这样一旦终点得到 P 标号,计算就停止。若寻求从始点到每一点的 最短路径, 则最多经过 N - 1 步计算, 计算就要停止（N 是 G 的顶点数)。 1.算法步骤如下: step1 :给始点 v1 标上 P 标号 d（v1）=0 给其他各点标上 T 标号 d ( vj ) = l1 j ( j = 2 , 3 , 4 , LN) ; step2 :在所有 T 标号中取出最小者, 比如: d( vj0) = l1v j0,则把该点的 T 标号改为 P 标号;step3 :重新计算具有 T 标号的其他各点 T 标号:选

12、vj 点的 T 标号与 d ( vk) + l j 中较小者作为 vj 的新标号。 一般情况下,设 P = vj | vj 具有 P 标号 , T = vj | vj 具有 T 标号 , V P ( V 为图 G 的顶点集合) 。令 d ( vk)= l1vk0 为点的 P 标号,于是 vk P0 把 T vk 中的点 vj 的 T 标号修改为 min d ( vj) , d ( vk) + lk step4 :重复上述步骤,直到 vN P ,这时 d ( vN) 是从 v1 到 vN 的最短路径.2. 改进算法 最短路径问题就是两点之间的最短路径,首先考虑是否将此问题分解多个子 问题进行求解

13、。这样可以降低问题复杂度,符合并行处理思想。Dijkst ra 最短 路径算法是从起点到终点求最短路径, 同样也可以表述为从终点到起点求最短 路径。于是考虑最短路径问题是否可以分解为由起点到终点求解最短路径和由 终点到起点求解最短路径 2 个子问题。 算法步骤如下: step1 :开始时, P = , Q = ,易知 vm = v1 , v n= vN 。P , Q 分别是由 开始点 v1 、终点 vN 开始的扩展点(固定标号) 集合, vm , v n 分别是集合 P , Q 的当前扩展点; step2 :d(vm)= e ( v n ) = min e( vy) 其中, d ( v m)

14、和 e ( v n) 分别为起点到 vm 、终点到 v n 的最短路径。PY v m P , Q Y v n Q ; step3 :重复 step2 直到 PIQ = vm 且 v m 唯一时终止; step4 :计算最短路径l1 = d ( vm) + e ( v n)l2 = d ( v x ) + e ( vy) + l ( v x , vy) 式中, l ( v x , vy ) 表示 v x , vy 相邻两点的路权值。 l ( v x , vy) 0 ; v x P; vy Q 。 最短路径为 lmin = min l1 , l2式中, lmin 为最短路径。算法程序框图如 图 1 所示。 图 1 改进算法程序框图图指由一组给定的点（称为顶点）及一组连接这些店的线（称为边或弧） 组成的总体（如交通图） ，而图论则是研究图的理论。 最短路问题是对一个赋权的有向图（赋权根据此题的要求为每两个站点之间 的长度）中的指定的两个点起点 A 和终点 B 找到一条从 A 到 B 的路，使得这条 路上所有弧的权数的总和最小，这条路被称之为从 A 到 B 的最短路，这条路上 所有