《数模竞赛B题,城公交线路选择优化模型设计方案》由会员分享，可在线阅读，更多相关《数模竞赛B题,城公交线路选择优化模型设计方案（18页珍藏版）》请在金锄头文库上搜索。
1、城市公交线路优化模型本文针对城市公交线路选择问题建立了两个模型，一个是基于集合寻线算法 模型，另一个是图论模型。基于集合寻线算法模型中，首先固定换乘次数n，通过集合论的相关知识把 确定换乘点的具体位置，转化成确定一些集合间的交集，从而建立集合寻线算 法，再根据集合相关公式，得到所有可行线路；进一步考虑时间和费用等因素， 对可行线路进行处理比较，得出最佳线路。图论模型中，通过图论的知识将整个北京市交通线路构建出一个有向图，每 个站点与有向图的顶点一一对应，同一线路上的相邻站点对应为有向边，通过不 同目标（时间、费用）给有向图进行不同的赋权，分别将不同目标转化为赋权有 向图寻找最短有向路，根据最短
2、路径算法，得到最佳线路。最后综合评价了两个 模型的优缺点。关键词：集合寻线算法；最短路算法；换乘点；赋权有向图1问题提出北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众， 其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。随 着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达 800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问 题。在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以 知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司 准备研制开发一个解决公交线路选择问题的自主查询计
3、算机系统。该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询 者的各种不同需求。根据附录1、附录2,解决如下问题：1. 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算 法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站一终到站之 间的最佳线路。（1） S3359-S1828（2） S1557-S0481 （3） S0971-S0485（4） S0008-S0073（5） S0148-S0485 （6） S0087-S36762. 同时考虑公汽与地铁线路，解决以上问题。3. 假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模型。2问题
4、分析为了研制开发一个解决公交线路最佳选择（即乘客在多条公交线路中根据自 己的需求获得最适合自己的线路）问题的自主查询计算机系统，只要乘客给出起 点站A和终点站B两个站点，系统就给出最佳交通线路，使得公众出行更加通畅、 便利。而问题核心是如何在多条线路选择中获得最佳线路。乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才 能到达终点站，但若多次换乘公交，可能导致乘客所花时间及其费用的增加，更 会给乘客造成不便。在奥运将在北京举行的背景下，我们知道乘客前往观看奥运 比赛时，主要注重的是能否及时到达，所以在为乘客选择线路时，力求乘坐花费 的时间尽可能少以及路程尽可能短的线路，同时考虑
5、换乘车辆以及乘车费用尽量 少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化，我 们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路， 再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。3模型准备3.1模型假设1. 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支 付地铁费）；2. 假设所有交通线路都不出现停运或者线路变动；3. 假设公汽的环行行驶线路是单向的。3.2符号约定c :相邻公汽站平均行驶时间（包括停站时间），c = 3min ；d :相邻地铁站平均行驶时间（包括停站时间），d = 2.5min ；e :公汽换乘公汽平均耗时
6、，e = 5min （其中步行时间2min ）；f :地铁换乘地铁平均耗时，f = 4min （其中步行时间2min ）； g :地铁换乘公汽平均耗时，g =7min （其中步行时间4min ）； h :公汽换乘地铁平均耗时，h = 6min （其中步行时间4min ）；七.：交通工具与交通工具换乘所需时间；k :地铁票价，k = 3兀；n :换乘次数；N.:乘客在可选择的从起始站到终点站线路中第/条线路的换乘点（包括始点和 . 终点），j = 0,1,2,.,n +1，N 为起点，N +1 为终点；M :乘客从第j -1换乘点上车到第）换乘点的下车所付的票价，j = 1,2,.,n +1 ；
7、W.:公交车从第j -1换乘点到第j换乘点经过的站点数（含第j换乘点）j = 1,2,n +1 ；C :公交车在第i线路上从第j换乘点到第j +1换乘点线路；kJ :公交车在第i线路上从第j -1换乘点到第j换乘点经过每站所需时间；TJ :只换乘n次乘客从起始站到终点站选择第i条线路所需要的总时间；S1:只换乘n次乘客从起始站到终点站选择第i条线路所需要的总费用。4基于集合寻线算法的模型4.1集合寻线算法的建立现实乘客换乘的次数n很小，公司在设计一个城市公交线路时，为了使线路 更合理，一般不会使乘客要通过多次换乘（超过3次）才到达终点站。则不妨假 设换乘次数n e（0,2， n e Z。我们可
8、以看到问题中关键要解决的是找出换乘点N的具体位置，显然换乘 ij点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。由于公交线路 不是一条直线段或者有一定几何规律的曲线，所以我们通过代数的相关知识，把 具有同一属性的站点放入同一集合中，这样就把问题转化成代数问题。基于此思 想，我们建立以下集合寻线算法：步骤1:找出经过终点B站的所有公交线路B存放到集合Y = B I B e B ， 以及这些线路B经过的所有站点存放到集合Q。jjj步骤2：找出经过起始站A的所有公交线路A，存放到集合X = A I A e A ，iii以及这些公交线路A.经过的站点存放到集合P。步骤3:判断X和Y的关系：1
9、.若X n Y 0，即存在i, j e Z +，使得a. = B，表示起始站A到终点站B 之间有一条或几条直达线路，乘客不必换乘公交车，算出这些直达线路各自所需 要的时间和票价；通过比较大小，得到该情况下的乘车最少时间T和最少费用 S .，以及其相应的线路。minmin 2.若X n Y = 0，则说明起始站A与终点站B之间不存在公交车直达的情 况，只能通过换乘才能到达终点站B，则要寻找换乘点。步骤4:查找公交线路A.与公交线路B.的所有共同站点a，存放到集合I = a I a = A n B.。集合I中的兀素是换乘点。步骤5:判断集合I :1. 如果集合I丈0，即乘客可以通过一次换乘就能到达
10、终点站。记录换乘 点及其相应线路。2. 如果集合I = 0，即乘客不能通过一次换乘到达终点站，则要选取新的起始点。步骤6：选取新的起始点：从集合P中任取一站点A （ A女A）,即遍历集合P中所有的元素，以站点 A代替原来的起始站A。转到步骤2,这样就能找出所有经过两次换乘的线路。步骤7：通过重复上面的6个步骤可得经过n次换乘的所有可能线路。4.2模型的建立4.2.1时间及费用计算我们固定换乘次数n，通过集合寻线算法，得到通过n次换乘的所有可达线 路，再对这些线路进行下面的运算：从起点站A到终点站8，A :经过起点站A的第i条公交线路；B :经过终点站B的第j条公交线路；j只通过n次换乘到达可选
11、择的线路共有U条，设第i条乘坐线路的换乘点为N., j = 0,1, ,n +1， N 0为起点，N +1为终点，第i条线路上从第j换乘点到第 j +1换乘点线路为C，其途径的站点数W , j = 0,1, ,n,所付的票价M ,相 邻站点平均行驶时间.，第j个换乘点需要的换乘时间为。j1）只考虑公汽线路：jja. 第i线路所需要的总时间：以W +E空成+ enmniij ijijij（1）j TjTjT其中，c表示公汽相邻两站的平均行使时间，e汽车换乘需要的平均耗时。b. 第i线路所需要的总费用：(2)（3）S 二寸 MjT11，其中，M2,ij3,C.段乘坐单一票价公汽0 Wj J2012
12、0 W 40ij0, W T 0ij2）同时考虑公汽与地铁线路：a.第i线路所需要的总时间:T TEW +niij ijijj t1j t1c，C段乘坐汽车 其中，kj = d，C段乘坐地铁l ije，公汽换乘公汽_ If，地铁换乘地铁% = jg，地铁换乘公汽h，公汽换乘地铁b.第i线路所需要的总费用:（4）S =mniijj=1L3,1, M = ij2,3 ,0,c段乘坐汽车单一票价线路cj.段乘坐地铁02020 W 40Jij3）同时考虑公汽、地铁和步行时间:吧=0a.第i线路所需要的总时间:T =lLkWj +lLtj（5）j=1j=1c，c段乘坐的是汽车 其中，k=d，cj段乘坐的
13、是地铁v，.段为步行e，公汽换乘公汽f，地铁换乘地铁 t =一 ,ij g，地铁换乘公汽h，公汽换乘地铁（6）b.第i线路所需要的总费用：S . =U Mj=113,1，M = ij2,3，C段乘坐汽车单一票价线路C段乘坐地铁020 120 W 40ij0, W = 0注意：由于步行不需费用,j所以要给个步行线路约束：步行时间不超过T。4.2.2目标函数的确定固定了换乘次数n，确立以下目标：1）时间目标：min）,即找出只通过n次换乘乘车时间最少的最佳线路及其时间；ni2）费用目标：min（S ）,即找出只通过n次换乘乘车费用最少的最佳线路及其费用。ni4.2.3最佳线路的处理由于公交线路很多
14、，在同一目标下，乘客可能还有较多条最佳线路的选择， 那么我们不可能把所有最佳线路给乘客选择，乘客也不能接受，所以我们可根据 下面几点进行处理：1）尽量满足时间最短的情况下，选择费用最少的线路；2）尽量不要把换乘站点安排在热门站点（即较多线路交叉点，不妨设最佳 线路大于5条时，通过查找经过换乘站点的所有交通线路，遍历所有换乘站点， 记录每一个站点对应的,，r较大就是热门站点）；3）可以随机抽取几条给乘客，避免某条线路上过于繁忙；4）尽量不要把繁忙线路（累加每一条线路上所有站点对应的r得到较大的 的线路为繁忙线路）安排为最佳线路，避免交通阻塞；4.2.4算法的时间复杂度由于所选的换乘次数最多两次，
15、所以此算法的时间复杂度为O（n2）。5基于图论的模型及其算法实现5.1图论模型的建立以每个站点为顶点，若站点A到站点B有公交线路并且A与B为相邻站点， 则连一条A到B有向边，根据所给的站点与线路我们建立一个得到一个有重边的 有向图D（V,E）。一条公交线路就是D（V,E）的一条有向路。5.1.1以时间为目标的线路模型1）仅考虑公汽线路对于有向图D（V,E），给每条有向边都赋权c （相邻公汽站点行驶时间），若 站点A有n条公汽线路，则把A变成n个点A1,气,A （相当于增加了 n 1假想 点，换乘公汽线路需要从A变为A .），A ,A,.：,A的每两顶点都连对称有向边，ij12n即这是一个n阶双向完全有向图（见图1
