数模竞赛B题,城公交线路选择优化模型设计方案

1、城市公交线路优化模型摘要本文针对城市公交线路选择问题建立了两个模型， 一个是基于集合寻线算法 模型，另一个是图论模型。基于集合寻线算法模型中，首先固定换乘次数 n ，通过集合论的相关知识把 确定换乘点的具体位置 , 转化成确定一些集合间的交集，从而建立集合寻线算 法，再根据集合相关公式，得到所有可行线路；进一步考虑时间和费用等因素， 对可行线路进行处理比较，得出最佳线路。图论模型中， 通过图论的知识将整个北京市交通线路构建出一个有向图， 每 个站点与有向图的顶点一一对应， 同一线路上的相邻站点对应为有向边， 通过不 同目标（时间、费用）给有向图进行不同的赋权，分别将不同目标转化为赋权有 向图寻

2、找最短有向路， 根据最短路径算法， 得到最佳线路。 最后综合评价了两个 模型的优缺点。关键词： 集合寻线算法；最短路算法；换乘点；赋权有向图1问题提出北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众， 其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。随 着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达 800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问 题。在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以 知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司准备研制开发一个解决

3、公交线路选择问题的自主查询计算机系统。该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询者的各种不同需求。根据附录1、附录2,解决如下问题：1. 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算 法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站一终到站之 间的最佳线路。（1）S3354 S1828（2） S1557 S0481（3） S0971 S0485 S000IS0073（5） S0148 S0485 （6） S0087 S36762. 同时考虑公汽与地铁线路，解决以上问题。3假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模

4、型。2问题分析为了研制开发一个解决公交线路最佳选择 （即乘客在多条公交线路中根据自 己的需求获得最适合自己的线路） 问题的自主查询计算机系统，只要乘客给出起 点站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 ）；tij:交通工具与交通工具换乘所需时间；k :地铁票价，k =3元；n :换乘次数；Nj :乘客在可选择的从起始站到终点站线路中第i条线路的换乘点（包括始点和终点），j =0,1,2,n+1，Nio为起点，Nj出为终点；Mj :乘客从第j -1换乘点上车到第j换乘点的下车所付的票价，j =1,2 - , n 1 ；Wj :公

7、交车从第j -1换乘点到第j换乘点经过的站点数（含第 j换乘点）j =1,2, ,n 1 ；Cj :公交车在第i线路上从第j换乘点到第j 1换乘点线路；kj :公交车在第i线路上从第j -1换乘点到第j换乘点经过每站所需时间； Tni :只换乘n次乘客从起始站到终点站选择第i条线路所需要的总时间；5 :只换乘n次乘客从起始站到终点站选择第i条线路所需要的总费用。4基于集合寻线算法的模型4.1集合寻线算法的建立现实乘客换乘的次数n很小，公司在设计一个城市公交线路时，为了使线路 更合理，一般不会使乘客要通过多次换乘（超过 3次）才到达终点站。则不妨假 设换乘次数n 0,2 1， n Z。我们可以看

8、到问题中关键要解决的是找出换乘点Nj的具体位置，显然换乘点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。由于公交线路 不是一条直线段或者有一定几何规律的曲线，所以我们通过代数的相关知识，把 具有同一属性的站点放入同一集合中， 这样就把问题转化成代数问题。基于此思 想，我们建立以下集合寻线算法：步骤1:找出经过终点B站的所有公交线路Bj存放到集合丫二Bj | B Bj， 以及这些线路Bj经过的所有站点存放到集合Q。步骤2:找出经过起始站A的所有公交线路A，存放到集合X = A I AW A， 以及这些公交线路A经过的站点存放到集合P。步骤3:判断X和Y的关系：1 若X Y -.，即存在

9、i, j Z ，使得A二Bj ,表示起始站A到终点站B 之间有一条或几条直达线路，乘客不必换乘公交车，算出这些直达线路各自所需 要的时间和票价；通过比较大小，得到该情况下的乘车最少时间Tmin和最少费用Smin，以及其相应的线路。2若X Y Y，则说明起始站A与终点站B之间不存在公交车直达的情 况，只能通过换乘才能到达终点站 B，则要寻找换乘点。步骤4:查找公交线路 A与公交线路Bj的所有共同站点a,存放到集合I =a|a = A “Bj。集合I中的元素是换乘点。步骤5:判断集合I :1 如果集合I =一，即乘客可以通过一次换乘就能到达终点站。记录换乘 点及其相应线路。2如果集合I =以，即乘

10、客不能通过一次换乘到达终点站，则要选取新的起始点。步骤6:选取新的起始点：从集合P中任取一站点A* （ A丰A）,即遍历集合P中所有的元素，以站点 A代替原来的起始站A。转到步骤2,这样就能找出所有经过两次换乘的线路。步骤7:通过重复上面的6个步骤可得经过n次换乘的所有可能线路。4.2模型的建立时间及费用计算我们固定换乘次数n，通过集合寻线算法，得到通过n次换乘的所有可达线 路，再对这些线路进行下面的运算：从起点站A到终点站B，A :经过起点站A的第i条公交线路；Bj :经过终点站B的第j条公交线路；只通过n次换乘到达可选择的线路共有U条，设第i条乘坐线路的换乘点为 Nj,j=0,1,，n，1

11、， Nio为起点，N i ,n 1为终点,第i条线路上从第j换乘点到第 j 1换乘点线路为Cij，其途径的站点数 Wj，j =0,1,ni，所付的票价Mij,相邻站点平均行驶时间kj，第j个换乘点需要的换乘时间为tj。1）只考虑公汽线路：a. 第i线路所需要的总时间：nnnTni八八cWj enj mj m j m其中，c表示公汽相邻两站的平均行使时间，e汽车换乘需要的平均耗时b. 第i线路所需要的总费用：1,Sni 八 M ijjECij段乘坐单一票价公汽(2)2）1，0 400，Wj =0同时考虑公汽与地铁线路：a.第i线路所需要的总时间： Cij段乘坐按段收费公汽nnTni八kijWj、

12、tijj壬j(3)其中,c，Cj段乘坐汽车 d，Gj段乘坐地铁6，公汽换乘公汽仁地铁换乘地铁 t“ =ij g，地铁换乘公汽、h，公汽换乘地铁b.第i线路所需要的总费用:Mj1,3,1,2,3,0,nSn I - X M |jj 4C jj段乘坐汽车单一票价线路C段乘坐地铁(4)0 :：: Wjj 乞 2020 : Wj G段乘坐按段收费汽车Ij(6)注意：由于步行不需费用，所以要给个步行线路约束：步行时间不超过 目标函数的确定固定了换乘次数n，确立以下目标：1) 时间目标：m I n(Tm),即找出只通过n次换乘乘车时间最少的最佳线路及 其时间；2) 费用目标：m I n(Sm),即找出只通

13、过n次换乘乘车费用最少的最佳线路及 其费用。最佳线路的处理由于公交线路很多，在同一目标下，乘客可能还有较多条最佳线路的选择， 那么我们不可能把所有最佳线路给乘客选择， 乘客也不能接受，所以我们可根据 下面几点进行处理：1）尽量满足时间最短的情况下，选择费用最少的线路；2）尽量不要把换乘站点安排在热门站点（即较多线路交叉点，不妨设最佳 线路大于5条时，通过查找经过换乘站点的所有交通线路，遍历所有换乘站点， 记录每一个站点对应的r， r较大就是热门站点）；3）可以随机抽取几条给乘客，避免某条线路上过于繁忙；4） 尽量不要把繁忙线路（累加每一条线路上所有站点对应的r得到较大的 的线路为繁忙线路）安排

14、为最佳线路，避免交通阻塞；算法的时间复杂度由于所选的换乘次数最多两次，所以此算法的时间复杂度为0（n2）。5基于图论的模型及其算法实现5.1图论模型的建立以每个站点为顶点，若站点 A到站点B有公交线路并且A与B为相邻站点， 则连一条A到B有向边，根据所给的站点与线路我们建立一个得到一个有重边的 有向图D（V,E）。一条公交线路就是D（V,E）的一条有向路。以时间为目标的线路模型1 ）仅考虑公汽线路对于有向图D（V,E），给每条有向边都赋权c （相邻公汽站点行驶时间），若 站点A有n条公汽线路,则把A变成n个点a，A2,，代（相当于增加了 n-1假想 点，换乘公汽线路需要从A变为Aj），A,A2

15、,，An的每两顶点都连对称有向边， 即这是一个n阶双向完全有向图（见图1）,每条边都赋权e（公汽换乘公汽耗时）， 于是得到一个赋权有向图D（V,E,W）。则任意两公汽站点之间线路最少时间选择问题就转化为求D（V,E,W）的对应两顶点的最短有向路问题。A1A32) 同时考虑公汽和地铁对于有向图D(V,E)，给每条公汽线路的有向边都赋权C,每条地铁线路的有向边都赋权d，若站点B有m n条公交线路(其中m条公汽线，n条地铁线)， 则把B变成m+n个顶点022川Om; R,P2,H|,P (相当于增加了 m + n1个假想 点)，边为m - n个顶点都连对称有向边，它一个m - n阶完全双向有向图(见

16、图2)。 0i,02,|,0m间的边赋权e (公汽换乘公汽耗时)，P,P2,|山Pn间的边赋权f (地铁 换乘地铁耗时)，OiQ,川,0m的每点到PR,川,P,的每点的边赋权h (公汽换乘地 铁耗时)，PR,川,Pn的每点到0iQ，川,0m的每点的边赋权g (地铁换乘公汽耗 时)。得到一个赋权有向图H(V,E,W)。则任意两公汽站点之间线路最少时间选择问题就转化为求H (V, E,W)的对应两顶点的最短有向路问题。3) 同时考虑公交与步行时间在赋权有向图H(V,E,W)中任两点之间(除去假想点)连接对称有向边， 其边赋权为V，从而得到一个新的赋权有向图J(V,E,W)。则任意两公汽站点之间线路

17、最少时间选择问题就转化为求J (V , E,W)的对应两顶点的最短有向路问题。以费用为目标的线路模型1) 仅考虑公汽的线路对于公交线路有向图D(V,E)，给所经过的同一公汽线路上的最大站点数n的有向路进行赋权：若单一票价，则赋权f。；若分段计价，则赋权1,0 _ n _20Ifn)#2,21兰n幺0，于是得到一个动态赋权有向图 G(V,E,W) 0、3,n41则任意两公汽站点之间线路最少费用选择问题就转化为求动态赋权有向图 G(V,E,W)的对应两顶点的最短有向路问题。2) 同时考虑公汽和地铁对于城市公交线路自然图D(V,E)，给所经过的同一公汽线路上的最大站点 有向路进行赋权：若单一票价，则

18、赋权fo ;若分段计价，则赋权1,0 一 n _20fn) = 2,21兰n乡0 (n为最大站点数)，给所经过的同一地铁线路赋权 f?，于是 、3,n 41得到一个动态赋权有向图 H(V,E,W)。于是任意两公交站点之间线路最少费用选择问题就转化为求H(V,E,W)的对应两顶点的最短有向路问题。3) 同时考虑公交和步行由于步行是不需要费用的，则在赋权图是H(V,E,W)上任意两点间连上对称 的有向边，但其权为0,显然费用最少为0,即步行到终点站。显然是不合理的。 故这里不能用赋权图对应线路。5. 2最短路径算法 上面模型可以通过如算法实现:步骤1:通过计算式子r计叫1(必1,乙1f(n )=0

19、(其中n是终点,是起点，终点的f(n) =0,从终点出发逐步向起点推算，j是与i相邻，f(j)为已知j点到终点的最小线路)，得到最短路。此算法时间复杂度为：O(n2)步骤2：通过对上面最短路经过的站点的搜索和判断，找出换乘点和换乘次数。 步骤3：把步骤1最短路的权值与步骤2换乘目标值相加，得到最终的最短路6模型的求解因为乘坐的费用比较少，乘客还是偏重与对时间的选择，本文下面的求解都 是以时间为目标得到的最佳线路。6.1基于集合寻线算法模型的求解仅考虑公汽根据模型求解出问题中通过模型得到了6对查询点都不能通过一条线路直接到达，也得到1, 2次换乘的最佳线路。见下表：S335X S1828的不同线

20、路乘车方 案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次 数1L436 下行S1784L16732101312L436 下行S1784L21732101313L015下行S2903L027上行S1784L167下行2173324L015下行S2903L027上行S1784L217下行2173325L015下行S2903L201上行S1790L041上行2173326L015下行S2903L201上行S0458L041上行2173327L015下行S2903L201上行S1792L041上行2173328L015下行S2903L201上行S1783L041上行2173329L015

21、下行S2903L201上行S1671L041上行21733210L123上行S2903L027上行S1784L167下行21733211L123上行S2903L027上行S1784L217下行21733212L123上行S2903L201上行S1790L041上行217332S155 S0481的不同最优解路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L084下行S1919L189下行S3186L46032106222L363S1919L189S3186L4603210622下行下行S0971 S0485的最佳路线乘车方案线路一换乘点1线路二换乘点2线路总站数总时间

22、总费用换乘次数1L013下行S2184L417下行41128312L013上行S1690L140下行S2654L46932106323L013下行S2517L296上行S2480L41732106324L024下行S1690L140下行S2654L46932106325L094上行S1690L140下行S2654L46932106326L119下行S1690L140下行S2654L46932106327L263下行S1690L140下行S2654L4693210632SOOOIS0073最佳路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L159下行S2683L058

23、下行2683212L159下行S0291L058下行2683213L159下行S3614L058下行2683214L159下行S0491L058下行2683215L159下行S2559L058下行2683316L159下行S3315L058下行2683317L159下行S2559L464上行2683318L159下行S0400L474上行2683219L159下行S2633L474上行26832110L159下行S3053L474上行26832111L355下行S2263L345上行26832112L355下行S3917L345上行26832113L355下行S2303L345上行268321

24、14L463下行S2083L057上行26832115L198上行S3766L296上行S2184L345196732S014M S0485的不同最优解路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L308上行S36L156上行S3351L417下行3210622SOO87 S3676的最佳路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L454上行S3496L209下行2065212L021下行S0088

25、L231环行S0427L462下行124632通过模型得到了 6对查询点都不能通过一条线路直接到达，换乘一次，两次的较优线路，根据乘客的不同的需求，确定目标，选择适合自己的最佳线路。例 如上面从站点S3359到站点S1828，如果乘客不想多次换乘，那么他就可以选择 换乘一次的两条线路的一条，如果乘客想尽快到达终点站，那么他可以选择换乘 两次的10条线路中的一条。同时考虑公汽和地铁我们先算出问题中6对查询点一定上要一次地铁的最佳线路见表3:表3乘坐一次地铁的最佳线路始点t终占八、公汽线路一换乘点地铁线路地铁 起点地铁终占八、公汽线路二换乘点时间费用S3359tS1828线路超过二次换乘，无法提供

26、具体线路S1557tS0481L084 下行S0978T2D32D24L516 上行S0537116.55S0971tS0485L094 上行S0567T1D1D20L417 下行S207999.55S0008tS0073L159 下行S2633T1D13S12L057 上行S060975.55S0148tS0485L024 下行S1487T1D2D20L417 下行S2079915S0087tS3676一一T2D27D36一一363再与只考虑公汽的最佳线路进行比较，选择时间最短的，得到S3354S1828, S1557 S0481，S0008 S0073 只乘坐公汽，S0971HS0485,

27、 S0148 S0485, S0087 S3676要乘坐地铁才能获得最短时间。6.2图论模型的求解因为根据此模型得到的结果，根上面模型基本一致，在此本文就不再赘述， 有兴趣的读者可以通过算法得到。7 模型评价7.1 基于集合寻点算法的模型的评价基于集合寻点算法的模型所给的查询系统是固定换乘次数 n 基础上，算出能 通过n次换乘的所有线路。再通过对不同换乘数所得到的这些最佳线路，对这些 线路的时间，费用的分别比较， 通过层层的对比筛选排除， 通过一些条件对最佳 线路的进行处理，最后乘客可以根据自己的不同需求进行选择。其优点：模型中紧紧抓住选择最佳线路问题的突破点一一换乘次数，通过集合的相关知识把

28、难点换乘点的具体位置的确定 , 转化成确定一些集合间的交 集，从而把站点，线路与集合中的元素一一对应起来，建立起集合寻线算法，再 根据集合相关公式， 通过线路计算式子， 有效地计算出最佳线路， 并且考虑一些 因素，如时间等对最佳线路进行处理。 算法中有效的摒弃一些无效站点， 从而大 大减少了计算量和时间， 明显比运用图论求得最短路要有效的多。 能为查询者提 供不同换乘次数下时间与路程最少的最佳线路， 以及对于多条最佳线路， 查询系 统尽量采用不太热门的公交线路， 随机地为查询者提供指定数目的线路， 避免同 一最佳线路过热的情况发生。其缺点：就是此模型只能为查询者提供换乘次数较少下的最佳线路，

29、当换乘 次数大于三时，模型实现的时间较长。7.2 图论模型的评价由图论模型所得的查询系统， 是以图论知识中的最短路有向图为基础， 对不 同线路经过同一站点时， 假设多个假想点，并将各不同站点之间所需时间作为权， 对各线路站点赋权， 分别确定以时间、 费用、换乘为目标转化为寻找有向的完全 图，并根据实际情况，建立出动态赋权有向图，得出最佳线路。其优点：模型充分利用公交线路其实就是一个有向图， 而且在比较成熟的最 短路算法基础上，通过插入换乘时间，得到最佳线路。算法还是比较容易实现。其缺点：模型在引入步行， 求费用最少， 却不能实现。 而且运用最短路算法， 得到不一定是真正意义上的最佳线路，只能是

30、近似最佳线路。8 模型的推广建立此模型的思想， 不但能应用到现在这种公交线路中， 并能推广到海、陆、 空多种交通线路之间寻找最优线路。 通过实际情况对模型的进行调整， 模型就能 适应更多情况。例如图论模型中对有向图的权进行调整就能实现不同时间差站点 的最佳线路的选择。参考文献1 姜启源，谢金星数学模型M（第三版）.北京：高等教育出版社，2003.2 孙惠泉. 图论及其应用 M. 北京:,2004.3 边肇祺,张学工等.模式识别M（第二版）.北京:清华大学出版社，1999.4 蔡自兴 ， 徐光祐 . 人工智能及其应用 M（ 第二版 ）. 北京 ： 清华大学出版 社，1996. 袁新生，邵大宏，郁

31、时炼.LINGO和EXCELS数学建模中的应用M.北京：科学 出版社，2007.程序 附录部分程序%数据的初始处理clcfid=fopen(QCLS.txt,r);Data=fread(fid);len=length(Data);gcl=0;qq=0;for i=1:len-1if char(Data(i)=L&qq=0gcl=gcl+1; GCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3); i=i+4; elseif char(Data(i)=L&qq=1for j1=1:length(GCLSgcl3) GCLSgcl4j1=GCL

32、Sgcl3length(GCLSgcl3)+1-j1;endgcl=gcl+1;qq=0; GCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3); i=i+4; elseif char(Data(i)*256+Data(i+1)= 。 &char(Data(i+4)=Sx=3;i=i+3;qq=1;s=0;elseif char(Data(i)*256+Data(i+1)= 分 GCLSgcl2=1;i=i+8;elseif char(Data(i)*256+Data(i+1)= 单 GCLSgcl2=2;i=i+11;elseif cha

33、r(Data(i)*256+Data(i+1)= 上 x=3;i=i+4;qq=0;s=0;elseif char(Data(i)*256+Data(i+1)= 下 x=4;i=i+4;qq=0;s=0;elseif char(Data(i)*256+Data(i+1)= 环 x=5;i=i+4;qq=0;s=0;elseif char(Data(i)=Ss=s+1; GCLSgclxs=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3),Data(i+4);clci=i+4;end endfor i1=1:520if length(GCLSi1)=5n=

34、length(GCLSi13); GCLSFi11=GCLSi11; GCLSFi12=GCLSi12;for i2=1:nGCLSFi13i2=GCLSi13n-i2+1;endn=length(GCLSi14);GCLSFi11=GCLSi11;GCLSFi12=GCLSi12;for i2=1:nGCLSFi14i2=GCLSi14n-i2+1;endelseif length(GCLSi1)=5n=length(GCLSi15);GCLSFi11=GCLSi11;GCLSFi12=GCLSi12;for i2=1:nGCLSFi15i2=GCLSi15n-i2+1;endendendclc%地铁情况的运算Untitled% 读取文件DCLS% 地铁文件处理ZHANDIAN2%