课程设计：最佳乘车路线

《课程设计：最佳乘车路线》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、点换乘次数（次）乘车费用（元）所需时间（分钟）S3359——S1828L436S3359S178413101L217S1784S1828S1557——S0481L363S1557S191923106L189S1919S3186L460S3186S0481S0971——S0485L013S0971S218413128L417S2184S0485S0008——S0073L463S0008S20831283L057S2083S0073S0148——S0485L308S0148S003623106L156S0036S33

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

5、。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。因此我们主要解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用设计出的模型与算法，求出以下6对起始站→终到站之间的最佳路线：(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设

6、又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、符号说明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(vm)-------起点到vm的最短路径e(vn)---

7、-----起点到vn的最短路径三、问题分析本题的目的是针对市场需求，结合实际情况，在满足查询者不同需求的情况下，设计出任意两个站点之间的最佳线路，研制开发一个解决公交线路选择问题的自主查询计算机系统。从任意两个站点之间的路线来看，有多种路线供乘客选择。而公共交通工具又分为公汽、地铁等，同时线路的选择还受乘车路程、乘车费用及换乘次数等诸多因素的影响。建立优化模型[1]是解决公交线路选择的最佳方案。结合实际情况，分别以换乘次数最少和乘车时间最少分别作为目标函数提出两种开发方案。针对不同方案所得结果，对其优缺点及其适用

8、性进行评价。四、基本假设1、相邻两公汽站点之间距离相等。2、所有公汽和地铁的乘车条件同样好。3、不考虑堵车情况下，公交运力的分配。五、模型的建立（一）乘坐公交车需要转两次或多次车的情况，我们运用图论中关于最短路程的研究，进行套用，从而得出结果。最短路径的算法研究，讨论最短路径算法及根据实际问题对经典算法进行优化，以提高运行效率。1.连通性。其中被广泛采用连通性城市道路网络