图论结课论文

《图论结课论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、乘公交，看奥运通信学院10级研一8班学号【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstra算法，而采用了高效的广度优先算法。其基本思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后对可行解进行进一步处理。为满足不同查询者要求，我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的

2、优化模型。本文的主要特点在于，所用算法的效率十分显著。在对原始数据仅做简单预处理的条件下，搜索任意站点间的最优路线所需的平均时间不超过0.5秒。另外，本文所建立的模型简单、所用算法比较清晰，易于程序实现，对公交线路自主查询计算机系统的实现具有现实指导作用。关键字：转乘次数广度优先算法查询效率实时系统一问题的重述为了迎接2008年奥运会，北京公交做了充分的准备，首都的公交车大都焕然一新，增强了交通的安全性和舒适性，公交线路已达800条以上，使得公众的出行更加通畅、便利。但同时也面临多条线路的选择问题。为满足公众查询公交线

3、路的选择问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决的问题有：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型算法，求出以下6对起始站到终到站最佳路线。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑

4、公汽与地铁线路，解决以上问题。二符号说明：第i条公汽线路标号,i=1,2…10400,当时,表示上行公汽路线,当时,表示与上行路线相对应的下行公汽路线；：经过第i条公汽路线的第g个公汽站点标号；13：第j条地铁路线标号,j=1,2；：经过第j条地铁线路的第h个地铁站点标号；：转乘n次的路线；：选择第k种路线的总时间；：选择第k种路线公汽换乘公汽的换乘次数；：选择第k种路线地铁换乘地铁的换乘次数；：选择第k种路线地铁换乘公汽的换乘次数；：选择第k种路线公汽换乘地铁的换乘次数；：第k种路线、乘坐第m辆公汽的计费方式，其中：

5、表示实行单一票价，表示实行分段计价；：第k种路线，乘坐第m辆公汽的费用；：选择第k种路线的总费用；：选择第k种路线，乘坐第m辆公汽需要经过的公汽站个点数；：选择第k种路线，乘坐第n路地铁需要经过的地铁站个点数；：表示对于第k种路线的第m路公汽的路线是否选择步行，为0-1变量，表示不选择步行，表示选择步行；：对于第k种路线的第n路地铁的路线是否选择步行，为0-1变量，表示不选择步行，表示选择步行；三模型假设3.1基本假设1、相邻公汽站平均行驶时间(包括停站时间)：3分钟2、相邻地铁站平均行驶时间(包括停站时间)：2.5分

6、钟3、公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)4、地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)135、地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)6、公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)7、公汽票价：分为单一票价与分段计价两种；单一票价：1元其中分段计价的票价为：0～20站：1元21～40站：2元40站以上：3元8、地铁票价：3元（无论地铁线路间是否换乘）9、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费3.2其它假设10、查询者转乘公交的次数不超过两次；

7、11、所有环行公交线路都是双向的；12、地铁线T2也是双向环行的；13、各公交车都运行正常，不会发生堵车现象；14、公交、列车均到站停车四问题的分析在北京举行奥运会期间，公众如何在众多的交通路线中选择最优乘车路线或转乘路线去看奥运，这是我们要解决的核心问题。针对此问题，我们考虑从公交线路的角度来寻求最优线路。首先找出过任意两站点（公众所在地与奥运场地）的所有路线，将其存储起来，形成数据文件。这些路线可能包含有直达公交线路，也有可能是两条公交线路通过交汇而形成的（此时需要转乘公交一次），甚至更多公交线路交汇而成。然后在这

8、些可行路线中搜寻最优路线。对于路线的评价，我们可以分别以总行程时间，总转乘次数，总费用为指标，也可以将三种指标标准化后赋以不同权值形成一个综合指标。而最优路线则应是总行程时间最短，总费用最少或总转乘次数最少，或者三者皆有之。之所以这样考虑目标，是因为对于不同年龄阶段的查询者，他们追求的目标会有所不同，比如青年人比较热衷于比赛，因而