课程的设计最佳乘车路线.docVIP

? 论文题目：最佳乘车路线 论文作者1： 学号： 班级： 在设计中你的工作：□写作 □程序设计 □构建模型及应用 论文作者2： 学号： 班级： 在设计中你的工作：□写作 □程序设计 □构建模型及应用 论文作者3： 学号： 班级： 摘要： ? 本文针对公交线路选择的自主查询计算机系统的研制开发问题，以乘坐公交车路程最短、花费最少和换乘次数最少为前提，分别以任意两线路之间的换乘次数为0次、1次和多次为方案建立了图与网络模型，给出了公交线路选择的合理方案。 我们利用Excel函数求解换乘次数为0次或1次时，可以筛选出任意两公汽站点之间的最佳线路；根据图与网络模型中的最短路径的Dijkstra算法和弗洛伊德算法，可以求出换乘次数为任意数目时，任意两公汽站点之间的最佳线路。 利用Excel函数，制作公交向导，可以筛选出任意两公汽站点换乘次数为0次或1次的公交向导。这样就方便了乘客的查询。 由于的公交线路众多，根据图论中最短路径的求法，利用Dijkstra算法及其改进的算法和弗洛伊德算法则能够解决乘坐公交车需要转两次或多次车的情况。我们是用C++及Matlab等编程工具，分析了Dijkstra算法在改进后的实用性,经过运算得到相应的结果如下： ? 指定站点 公交线路 上车站点 下车站点 换乘次数（次） 乘车费用（元） 所需时间（分钟） S3359——S1828 L436 S3359 S1784 1 3 101 L217 S1784 S1828 S1557——S0481 L363 S1557 S1919 2 3 106 L189 S1919 S3186 L460 S3186 S0481 S0971——S0485 L013 S0971 S2184 1 3 128 L417 S2184 S0485 S0008——S0073 L463 S0008 S2083 1 2 83 L057 S2083 S0073 S0148——S0485 L308 S0148 S0036 2 3 106 L156 S0036 S3351 L417 S3351 S0485 S0087——S3676 L454 S0087 S3496 1 2 65 L209 S3496 S3676 从而验证了模型的执行力。我们结合了两种方案的有缺点，对公交车站模型进行了进一步的分析，并提出了较为合理的建议。? ? ? 关键词：公交线路选择? 图论? 最短距离? 弗洛伊德算法? Excel应用 ? ? 一、问题的提出 公交线路的选择问题是城市公交系统发展的核心问题，它可以满足查询者的不同需求，使得公众的出行更加通畅、便利，所以，在这种情况下，研制开发解决公交线路选择问题的自主查询计算机系统对城市的公交系统至关重要。S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。 3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。 二、符号说明 G = ( V , E , L ) ――――――无向图（公交网络） V ——— m 个 节点构成的点集（公交站点） E ———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 的最短路径 三、问题分析 本题的目的是针对市场需求，结合实际情况，在满足查询者不同需求的情况下，设计出任意两个站点之间的最佳线路，研制开发一个解决公交线路选择问题的自主查询计算机系统。 从任意两