毕业论文-公交线路转乘选择的优化模型.doc
《毕业论文-公交线路转乘选择的优化模型.doc》由会员分享,可在线阅读,更多相关《毕业论文-公交线路转乘选择的优化模型.doc(31页珍藏版)》请在咨信网上搜索。
1、公交线路转乘选择的优化模型摘 要本文以奥运会的公交线路换乘为大背景,建立了在公汽线路、地铁以及步行三种方式中综合进行路线转乘的模型。此问题可以归结为两个站点之间的最短路问题,由于直接以站点构建最短路问题计算量较大,本文在处理三个问题时分别提出了相应的模型与求解算法,以乘坐时间最短为标准回答了问题一与问题二,对问题三提出了最短路模型。在问题一建模过程中,我们以任意两条线路是否可以直接换乘为突破口,建立了以每条线路为顶点,两条线路之间的换乘信息为弧的图,将问题一归结为弧长可变的最短路问题,提出了结合动态规划方法与分枝定界思想的算法。首先将题目所给出的路线与站点信息翻译为两条线路是否可以直接相交以及
2、在何处相交的信息矩阵;其次以换乘时间最短或者费用最小为决策函数,建立动态规划问题;再次设计相应的算法进行求解。通过求解,以最短时间为目标,问题一的结果如下所示(以(1),(2)组为例,其它见正文表1):组(1):S3359S1828,最短时间73分钟,费用3元;组(2):S1557S0481,最短时间106分钟,费用3元。同时文章对运算结果进行了相关分析。在问题二建模过程中,沿用问题一的求解思想,将新增加的地铁视为新的线路,将所有线路信息转化为新的转乘矩阵,同时按照新的背景得到新的乘车时间与费用计算方法,同样以最短时间为目标,相同的算法可以得到问题二的结果(以(5),(6)组为例,具体见正文表
3、2):组(5):S0148S0485,最短时间87.5分钟,费用5元;组(6):S0087S3676,最短时间28分钟(已经加上地铁站到地面站点的步行时间,其中地铁运行时间20分钟),费用3元。在问题三建模过程中,由于增加了步行的信息,问题一、二的方法无法直接使用,文章建立了一个新的最短路问题。以每个站点为顶点,以两个顶点之间的最短路径(最短达到时间或者最小到达费用)为弧构造有向图,其中最短达到时间由问题二得到的两个站点之间使用公交网络的换乘时间与步行时间的最小值决定。从而将问题三归结为一个有向图的最短路模型,文章对此模型给出了算法建议。最后文章对所提出的模型进行了优缺点分析与推广评价。关键词
4、:城市公交线路、图与网络、最短路模型、动态规划一、 问题重述:近些年来,城市公共交通系统有了很大发展,使得公众的出行更加通畅、便利。绝大多数市民出行时首先会考虑选择公交设施,同时也面临如何在众多条线路中如何选择合适线路的问题。针对市场需求,要求开发一个解决公交线路选择问题的自主查询计算机系统,可以满足查询者的各种不同需求,对不同的起点和终点给出最佳的公交转乘路线。竞赛要求设计线路选择的模型与算法,解决以下三个问题:1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用模型与算法,求出以下6对起始站终到站之间的最佳路线(要有清晰的评价说明)。 (1)、S
5、3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路,解决以上问题。3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。二、 问题分析:(1) 从影响出行选择的因素看,每个人主要会从两个标准对线路进行选择与优劣衡量:从起点到终点所需要的总时间最短;从起点到终点需要花费的费用。(2) 从本质上讲,选择线路的问题可以归结为最短路问题,但是考虑到转乘线路需要时间,并且一条公交线路不能按照站点进行拆分,因此以每个站点构造路线图不利于
6、解决问题。注意到从起点站到目标站关键是选择乘坐哪些公交线路,需要在公交线路中如何选择转乘线路,因此可以以公交线路为顶点,以两个站点之间是否可以转乘为弧构造图,而点到点之间最佳路线的选择可以转化为经过分别两个端点的公交线路集合之间的最短路问题。同时我们需要任意两个线路之间是否可以转乘的信息。(3) 在给出的线路信息中,我们发现主要有三类线路:下行线路与上行线路不同,下行线路是上行线路的原路返回,环形线路。为了区分同一条线路不同的运行方向,我们人为地将每一条线路变为两条线路,这样做既可以分清楚所换乘的是那条线路的哪个方向,同时也可以将两条线路换乘点的信息与每个站点在本条线路上的位置相联系,这样可以
7、用来判断乘坐某条线路公交车从某个站点出发时,可以换乘哪些公交线路(换乘站点必须在乘车点沿着公交车运行方向的后方)。(4) 在公交线路信息中,与决策目标有关的元素还有每条线路的计费方式及每条线路乘坐时花费的时间。对于计费方式,我们按照单一票价与分段计价进行识别,分段计价与乘坐的站点数有关,这也是我们需要每个站点在每条线路上具体位置的原因;同样运行时间也与站点的具体位置有关。(5) 问题一仅对公共汽车进行分析,可以转化为一个图论问题,使用动态规划方法进行算法设计与计算。问题二增加两条地铁信息后,对问题一模型的影响仅在于需要考虑线路数的增加,也只需要将地铁线路与公车线路是否可以换乘的信息表现出即可。
8、问题三增加步行信息后,问题变得较为复杂,因为我们并不知道在哪些地方将会步行,因此我们采用简单列举的方法建立模型。三、 模型假设:1 乘客在乘坐公交线路过程中,以平均耗时为实际乘车、等车、转乘耗时;2 乘客在选择转乘线路时,考虑的因素有两个:花费的时间最少与费用最小;3 在计算换乘时间时,由公交车换公交车、地铁换地铁、公交车换地铁以及地铁换公交车时不单独计算步行时间;4 由起点所在站点直接乘坐地铁及从地铁直接到终点时,需单独计算步行时间。四、 符号说明及定义:衡量每条线路在每个站点是否停靠的01矩阵;:衡量每条线路经过的每个站点是从起点起算的第几站的矩阵;:线路的停靠站点向量:存储每条线路的收费
9、信息;:停靠的所有公交线路的集合;:线路停靠的所有站点;:乘坐从其第站到第()站的费用:表示从线路的第站到第站的时间函数:表示相邻公汽站平均行驶时间,本题为3:从站点经过一系列线路到达的总时间:从站点经过一系列线路到达的总费用:所有线路的转乘矩阵:公交线路,两两转乘集合;:为所有站点集合;:有向图中表示两个站点之间最短距离(最少时间或者最少费用)信息五、 问题一建模与求解一个城市所有的公交线路和停车点构成了一个复杂的网络图, 这些停车点可以看作该网络图的结点, 这些结点由相应的公交路线相连。 结点之间的边就是公交路线。 有的结点之间有边相连(即在某一条公交线上) , 有的结点之间无边相连(即这
10、两个结点不在任何一条公交线上)。 因此, 城市的公交路线网络图非常复杂, 结点很多, 公交线路纵横交错。描述公交线路网络的一个简单方法是以每个站点为顶点,以两个顶点之间的公交线路信息(需要花费的时间、花费的费用等)为弧建立赋权图,本题中站点个数共有3957个,这样得到的矩阵将是3957阶方阵,如此庞大的矩阵在使用计算机处理时,将会遇到很大的困难,我们所拥有的计算机硬件达不到要求。因此我们需要从另外一个角度重新描述公交线路网络。进而我们可以使用通过动态规划方法、最短路方法等建模思想构造算法、编写程序,使问题得到圆满地解决。5.1 原始数据处理(1)公交线路处理我们将题中给出的520条公交线路进行
11、处理,将每条线路人为地变成两条,每一条代表一个具体的行驶方向,得到1040条起点终点固定的单方向行驶的公交线路。具体的处理方法如下:a) 对于上行与下行站点相同的线路,如图1中(a),将上行与下行视为不同的两条线路,每一条作为一条新的单方向行驶的公交线路,即及;由于两个走向站点相同,因此这两条线路经过的站点集合相同,但是每个站点在两条线路中的位置不同,这对衡量从某个站点出发乘坐该线路是否可以换乘其他线路,以及换乘哪条线路非常重要(详细说明见后续命题);b) 对于上行与下行站点不同的线路,如图1中(b),将上行方向与下行方向视为两个不同的线路及,这两条线路经过的站点集合不同,从而每个站点在两条线
12、路中的站点位置也不同;c) 对于环形线路,如图1中(c),起点与终点为的环形道路,从中间某个站点断开,作为前一路线的终点以及后一路线的起点,这样就形成两条新的线路。由于环线中间某些站可能重合,因此分割线路时要保证同一线路中没有公共站点(编程设计的需要)并且兼顾两条新线路长度均等。AB(a)AB(b)(c)A图1通过以上处理,我们将所有情况统一转化为以起点和终点确定的1040条具有单一方向的有向线段。(2)建立站点与线路关系矩阵利用(1)得到的1040条线路及其上每个站点的信息,构造下列两个反映1040条线路与3957个站点相关信息的矩阵,称为停靠信息矩阵:与。为1040行3957列的矩阵,元素
13、为0或者1,反映每条线路是否经过每个站点,元素取值为:。也为1040行3957列的矩阵,元素为0或者某个自然数,反映每条线路经过每个站点时,从该线路的起始点算起,该站为第站,元素取值为:。定义向量为线路的停靠向量,为线路停靠的站点集合:。为停靠站点的公汽线路集合:。(3)每条线路的计费信息定义向量为每条线路的计费信息,按照题中所给出的计费信息,元素取值为。若,则线路为单一收费,票价均为1元;若,则线路为分段收费,按照题中所给定的公汽票价方案,可以得到乘坐从其第站到第()站的费用为,其中。可以发现单一收费情形可以并入上述公式,因此所有公汽线路(包括单一收费与分段收费)的费用计算可以合并为一个函数
14、,其中。称函数为沿着公交线路从其第站到第站的费用函数。相应于费用函数,用函数表示从该线路的第站到第站的时间函数,其中表示相邻公汽站平均行驶时间,在本题中取值为。5.2 判别两条线路之间是否可以换乘,得到任意两条线路之间的换乘矩阵命题1:乘客从出发,乘坐线路可以直接到站点的充要条件为,并且。同时可以得到花费的时间为花费的车费为。命题2:设线路的停靠向量为, 的停靠向,那么,线路可以转乘线路的充要条件为中有元素2,并且2所对应的站点为到的中转站。证明:按照停靠向量的定义,均为元素为0或者1的向量。因此若的第个分量为2,则,说明两条线路在站点相交,从而可以在站点处换乘。定义:设与在处相交,,在上为第
15、站,在上为第站,则称二元数对为线路到的换乘数对,记。若与不可换乘,则记;同时。注意到换乘数对与换乘线路之间的关系,若为线路到的换乘数对,则为线路到的换乘数对。将所有线路之间的换乘信息构成矩阵,称此矩阵为换乘矩阵,记为,。同时集合表示能够与实现直接换乘的线路集合。命题3:设线路到线路的换乘数对为乘客从站点出发,乘坐线路,通过换乘线路,到达站点的充要条件为在中存在一个换乘数对,使得且。同时,花费时间为:,其中表示公汽换乘公汽的时间,在本题取值为。花费费用为。命题4:若经由转乘再转乘到,而,分别为到,到的换乘数对集合,则必存在,使得,同时,花费时间为花费费用为。按照上面所述的四个命题的规律,可以得到
16、具有任意条中转线路的公汽路线的条件以及所花费的时间与费用。命题5:若乘客从出发,通过换乘线路,到达,则 必存在个换乘数对使得:(a),;(b)(c)同时花费的时间为花费的费用为。5.3 任意两点之间寻找换乘方式的动态规划模型利用5.1中所得到的元素,构造反映任意两条线路之间的换乘图,如图2所示,其中图的顶点表示每一条线路(一共有1040个顶点),而两个顶点之间的弧表示两个顶点的换乘信息。L1L2L3LjL1040Ljtr(i,j)图2 所有公汽线路的换乘图需要说明的是,由于与与的顺序有关,因此在后续提出的动态规划模型中,将按照计算的次序与换乘线路的先后次序将换乘图配上不同的方向,这些方向与计算
17、以及花费的时间与费用有关。假设某个乘客需要从站点通过公汽网络到达站点,则我们需要寻找从公汽集合到达集合在上述换乘图中的最短路径,这样问题一可以归结为下面寻求最短路问题:寻找换乘线路,使得,乘客从出发,可以通过此线路到达(满足5.2节中命题5),并且在所有可能的转乘线路中在下列两个目标下最优:(a)所花费的总时间最短;(b)所花费的总费用最小;这两个目标函数由5.2节命题5给出。5.4 求解问题一的算法由于上述最短路问题中所涉及的数据量较大,并且不同于传统最短路问题之处在于在图中我们得到的并不是相邻两点的路径,而是可以换乘的两条线路换乘的信息,因此不能直接用求解传统最短路问题的算法,如Dijst
18、ra算法进行计算。为了解决上述问题,我们给出下列算法,算法的主要思想如下:i. 使用动态规划的顺序或者逆序算法,将求解此问题的三个主要方面:a) 判断是否能在所给出的两点实现换乘;b) 计算每次换乘所需要的时间与费用;c) 判别是否达到时间最短或者费用最小结合在一起。ii. 在算法设计过程中,采用整数线性规划的分枝定界思想,以换乘的次数为分枝变量,以已经实现换乘情形下的时间或者费用为定界变量,实现在增加换乘次数的同时判别没有到达终点的换乘序列是否可能达到最优,即若当前存储实现成功换乘的最短时间或者最小费用为,则以为剪枝标准,在没有达到终点的线路中,如果所花费的时间或者费用已经超过,则不需要进一
19、步换乘寻找。算法I(给定起点与终点,判别两个站点是否在同一条线路上)1) 分别求出停靠与的所有线路集合,;2) 若,则退出;3) 若,则对任意的线路,计算所需时间与费用;4) 返回最小的时间或者费用,以及对应的线路。算法II(给定公汽线路停靠信息矩阵、换乘矩阵,计算任意起点到终点的最优路径):1) 输入起点,终点,对最短时间后者最小费用变量赋初值,;2) 按照算法1,判断,是否在一条公汽线路上,若在一条线路上, ,存储乘坐信息,否则转下一步;3) 写出,;4) 对任意的,按照换乘矩阵写出能够与进行换乘的所有线路,按照5.2节命题3判断中的线路能否实现一次换乘到;5) 若存在能够一次换乘到的线路
20、,计算需要的最短时间或者最小费用,转6),否则转7);6) 若,则或者若,则,存储换乘信息,否则转7);7) 对于不能实现换乘一次到达的线路中,计算通过能够换乘到的线路得换乘点需要的时间或者费用,或者,以或者为标准判断,若或者,则从下一步搜索路线集合中删去此换乘方式;8) 令为7)剩下的路线集合,返回4);9) 输出或者,以及换乘信息集合。5.5 问题一的求解结果利用MATLAB实现上述算法,并将此算法用来求解题目中所给出的六组换乘站点,求解结果如下表(由于结果较多,在表中仅列举出一种,在表后将进行适当的评价):表1. 问题一求解结果序号换乘站点对以时间最短为目标结果及对应时间与费用(1)S3
21、359S1828最短时间73分钟,费用3元(2)S1557S0481最短时间106分钟,费用3元(3)S0971S0485最短时间106分钟,费用3元(4)S0008S0073最短时间67分钟,费用3元(5)S0148S0485最短时间106分钟,费用3元(6)S0087S3676最短时间46分钟,费用3元对问题一结果的评价:a) 在所有得到的以时间最短的最优解中,费用均为3元。通过检验,6组站点对都不能实现直接达到,因此即使存在换乘一次的线路,所需要的费用至少为2元,这与最终每个时间最短的最优解花费3元相比,相差不大,因此我们在求解过程中主要以时间最短为优化目标。b) 在对每个站点对进行最优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业论文 公交线路 转乘 选择 优化 模型
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。