2007数模竞赛B题,城市公交线路选择优化模型论文

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

1问题提出 北京将于2008年举行奥运会，届时会有从四面八方而来观看奥运比赛观众，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。随着现代化的步伐加快，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。在现实生活中，公交线路以及其相应经过的站点非常多且密，乘客往往难以知道如何选择公交线路，所以针对市场需求以及公交线路选择上的问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。该系统的核心在于线路选择的模型与算法，应该从实际情况出发，满足查询者的各种不同需求。根据附录1、附录2，解决如下问题：1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立的模型与算法，求出以下6对起始站→终到站之间的最佳线路。(1)S3359→S1828(2)S1557→S0481(3)S0971→S0485(4)S0008→S0073(5)S0148→S0485(6)S0087→S36762.同时考虑公汽与地铁线路，解决以上问题。3.假设知道所有站点之间步行时间，给出任意两站点之间线路选择的数学模型。2问题分析为了研制开发一个解决公交线路最佳选择（即乘客在多条公交线路中根据自己的需求获得最适合自己的线路）问题的自主查询计算机系统，只要乘客给出起点站和终点站两个站点，系统就给出最佳交通线路，使得公众出行更加通畅、便利。而问题核心是如何在多条线路选择中获得最佳线路。乘客往往不能只乘一辆公交便直达终点，而是要通过换乘一辆或多辆公交才能到达终点站，但若多次换乘公交，可能导致乘客所花时间及其费用的增加，更会给乘客造成不便。在奥运将在北京举行的背景下，我们知道乘客前往观看奥运比赛时，主要注重的是能否及时到达，所以在为乘客选择线路时，力求乘坐花费的时间尽可能少以及路程尽可能短的线路，同时考虑换乘车辆以及乘车费用尽量少的最佳线路，而现实是很难同时满足上面三个目标的。为了使问题简单化，我们分别以乘车时间、乘车费用以及换乘次数为目标函数，得到各自的较优线路，再通过对比，有效地处理这些线路，最终得出查询系统给出的结果。3模型准备3.1模型假设1.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费）；2.假设所有交通线路都不出现停运或者线路变动；3.假设公汽的环行行驶线路是单向的。3.2符号约定：相邻公汽站平均行驶时间（包括停站时间），；：相邻地铁站平均行驶时间（包括停站时间），；：公汽换乘公汽平均耗时，（其中步行时间2）；：地铁换乘地铁平均耗时，（其中步行时间2）；：地铁换乘公汽平均耗时，（其中步行时间4）；：公汽换乘地铁平均耗时，（其中步行时间4）；：交通工具与交通工具换乘所需时间；：地铁票价，元；：换乘次数；：乘客在可选择的从起始站到终点站线路中第条线路的换乘点（包括始点和终点），，为起点，为终点；：乘客从第换乘点上车到第换乘点的下车所付的票价，；：公交车从第换乘点到第换乘点经过的站点数（含第换乘点）；：公交车在第线路上从第换乘点到第换乘点线路；：公交车在第线路上从第换乘点到第换乘点经过每站所需时间；：只换乘次乘客从起始站到终点站选择第条线路所需要的总时间；：只换乘次乘客从起始站到终点站选择第条线路所需要的总费用。4基于集合寻线算法的模型4.1集合寻线算法的建立现实乘客换乘的次数很小，公司在设计一个城市公交线路时，为了使线路更合理，一般不会使乘客要通过多次换乘（超过3次）才到达终点站。则不妨假设换乘次数，。我们可以看到问题中关键要解决的是找出换乘点的具体位置，显然换乘点是公交线路的交叉点，或者说站点至少要有两条公交线路经过。由于公交线路不是一条直线段或者有一定几何规律的曲线，所以我们通过代数的相关知识，把具有同一属性的站点放入同一集合中，这样就把问题转化成代数问题。基于此思想，我们建立以下集合寻线算法：步骤1：找出经过终点站的所有公交线路存放到集合，以及这些线路经过的所有站点存放到集合。步骤2：找出经过起始站的所有公交线路，存放到集合，以及这些公交线路经过的站点存放到集合。步骤3：判断和的关系：1．若，即存在，使得，表示起始站A到终点站B之间有一条或几条直达线路，乘客不必换乘公交车，算出这些直达线路各自所需要的时间和票价；通过比较大小，得到该情况下的乘车最少时间和最少费用，以及其相应的线路。2．若，则说明起始站与终点站之间不存在公交车直达的情况，只能通过换乘才能到达终点站，则要寻找换乘点。步骤4：查找公交线路与公交线路的所有共同站点，存放到集合。集合中的元素是换乘点。步骤5：判断集合：1．如果集合，即乘客可以通过一次换乘就能到达终点站。记录换乘点及其相应线路。2．如果集合，即乘客不能通过一次换乘到达终点站，则要选取新的起始点。步骤6：选取新的起始点：从集合中任取一站点（），即遍历集合中所有的元素，以站点代替原来的起始站。转到步骤2，这样就能找出所有经过两次换乘的线路。步骤7：通过重复上面的6个步骤可得经过次换乘的所有可能线路。4.2模型的建立4.2.1时间及我们固定换乘次数，通过集合寻线算法，得到通过次换乘的所有可达线路，再对这些线路进行下面的运算：从起点站到终点站，：经过起点站的第条公交线路；：经过终点站的第条公交线路；只通过次换乘到达可选择的线路共有条，设第条乘坐线路的换乘点为,，为起点，为终点,第条线路上从第换乘点到第换乘点线路为，其途径的站点数，，所付的票价,相邻站点平均行驶时间，第个换乘点需要的换乘时间为。1）只考虑公汽线路：a.第线路所需要的总时间：（1）其中，表示公汽相邻两站的平均行使时间，汽车换乘需要的平均耗时。b.第线路所需要的总费用：（2）其中,2）同时考虑公汽与地铁线路：a.第线路所需要的总时间：（3）其中，b.第线路所需要的总费用：（4）3）同时考虑公汽、地铁和步行时间：a.第线路所需要的总时间：（5）其中，b.第线路所需要的总费用：（6）注意：由于步行不需费用，所以要给个步行线路约束：步行时间不超过。4.2.2固定了换乘次数，确立以下目标：1）时间目标：，即找出只通过次换乘乘车时间最少的最佳线路及其时间；2）费用目标：，即找出只通过次换乘乘车费用最少的最佳线路及其费用。4.由于公交线路很多，在同一目标下，乘客可能还有较多条最佳线路的选择，那么我们不可能把所有最佳线路给乘客选择，乘客也不能接受，所以我们可根据下面几点进行处理：1）尽量满足时间最短的情况下，选择费用最少的线路；2）尽量不要把换乘站点安排在热门站点（即较多线路交叉点，不妨设最佳线路大于5条时，通过查找经过换乘站点的所有交通线路，遍历所有换乘站点，记录每一个站点对应的，较大就是热门站点）；3）可以随机抽取几条给乘客，避免某条线路上过于繁忙；4）尽量不要把繁忙线路（累加每一条线路上所有站点对应的得到较大的的线路为繁忙线路）安排为最佳线路，避免交通阻塞；4.2.4算法的由于所选的换乘次数最多两次，所以此算法的时间复杂度为。5基于图论的模型及其算法实现5.1图论模型的建立以每个站点为顶点，若站点A到站点有公交线路并且A与为相邻站点，则连一条到有向边，根据所给的站点与线路我们建立一个得到一个有重边的有向图。一条公交线路就是的一条有向路。5.1.1以时间为目标的线路模型1）仅考虑公汽线路对于有向图，给每条有向边都赋权c（相邻公汽站点行驶时间），若站点有条公汽线路,则把A变成个点（相当于增加了假想点，换乘公汽线路需要从变为），的每两顶点都连对称有向边，即这是一个阶双向完全有向图（见图1），每条边都赋权e（公汽换乘公汽耗时），于是得到一个赋权有向图。则任意两公汽站点之间线路最少时间选择问题就转化为求的对应两顶点的最短有向路问题。图1图22）同时考虑公汽和地铁对于有向图，给每条公汽线路的有向边都赋权c，每条地铁线路的有向边都赋权d，若站点B有条公交线路（其中条公汽线，条地铁线）,则把B变成个顶点（相当于增加了个假想点），边为个顶点都连对称有向边，它一个阶完全双向有向图(见图2)。间的边赋权e（公汽换乘公汽耗时），间的边赋权f（地铁换乘地铁耗时），的每点到的每点的边赋权h（公汽换乘地铁耗时），的每点到的每点的边赋权g（地铁换乘公汽耗时）。得到一个赋权有向图。则任意两公汽站点之间线路最少时间选择问题就转化为求的对应两顶点的最短有向路问题。3）同时考虑公交与步行时间在赋权有向图中任两点之间（除去假想点）连接对称有向边，其边赋权为，从而得到一个新的赋权有向图。则任意两公汽站点之间线路最少时间选择问题就转化为求的对应两顶点的最短有向路问题。5.1.2以费用为目标的线路模型1）仅考虑公汽的线路对于公交线路有向图，给所经过的同一公汽线路上的最大站点数的有向路进行赋权：若单一票价，则赋权；若分段计价，则赋权，于是得到一个动态赋权有向图。则任意两公汽站点之间线路最少费用选择问题就转化为求动态赋权有向图的对应两顶点的最短有向路问题。2）同时考虑公汽和地铁对于城市公交线路自然图，给所经过的同一公汽线路上的最大站点有向路进行赋权：若单一票价，则赋权；若分段计价，则赋权，给所经过的同一地铁线路赋权，于是得到一个动态赋权有向图。于是任意两公交站点之间线路最少费用选择问题就转化为求的对应两顶点的最短有向路问题。3）同时考虑公交和步行由于步行是不需要费用的，则在赋权图是上任意两点间连上对称的有向边，但其权为0，显然费用最少为0，即步行到终点站。显然是不合理的。故这里不能用赋权图对应线路。5.2最短路径算法上面模型可以通过如算法实现：步骤1：通过计算式子（其中是终点，1是起点，终点的，从终点出发逐步向起点推算，是与相邻，为已知点到终点的最小线路），得到最短路。此算法时间复杂度为：步骤2：通过对上面最短路经过的站点的搜索和判断，找出换乘点和换乘次数。步骤3：把步骤1最短路的权值与步骤2换乘目标值相加，得到最终的最短路。6模型的求解 因为乘坐的费用比较少，乘客还是偏重与对时间的选择，本文下面的求解都是以时间为目标得到的最佳线路。6.1基于集合寻线算法模型的求解6.1.1仅考虑公汽 根据模型求解出问题中通过模型得到了6对查询点都不能通过一条线路直接到达，也得到1，2次换乘的最佳线路。见下表:S3359→S1828的不同线路乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L436下行S1784L16732101312L436下行S1784L21732101313L015下行S2903L027上行S1784L167下行2173324L015下行S2903L027上行S1784L217下行2173325L015下行S2903L201上行S1790L041上行2173326L015下行S2903L201上行S0458L041上行2173327L015下行S2903L201上行S1792L041上行2173328L015下行S2903L201上行S1783L041上行2173329L015下行S2903L201上行S1671L041上行21733210L123上行S2903L027上行S1784L167下行21733211L123上行S2903L027上行S1784L217下行21733212L123上行S2903L201上行S1790L041上行217332S1557→S0481的不同最优解路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L084下行S1919L189下行S3186L46032106222L363下行S1919L189下行S3186L4603210622S0971→S0485的最佳路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L013下行S2184L417下行41128312L013上行S1690L140下行S2654L46932106323L013下行S2517L296上行S2480L41732106324L024下行S1690L140下行S2654L46932106325L094上行S1690L140下行S2654L46932106326L119下行S1690L140下行S2654L46932106327L263下行S1690L140下行S2654L4693210632S0008→S0073最佳路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L159下行S2683L058下行2683212L159下行S0291L058下行2683213L159下行S3614L058下行2683214L159下行S0491L058下行2683215L159下行S2559L058下行2683316L159下行S3315L058下行2683317L159下行S2559L464上行2683318L159下行S0400L474上行2683219L159下行S2633L474上行26832110L159下行S3053L474上行26832111L355下行S2263L345上行26832112L355下行S3917L345上行26832113L355下行S2303L345上行26832114L463下行S2083L057上行26832115L198上行S3766L296上行S2184L345196732S0148→S0485的不同最优解路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L308上行S36L156上行S3351L417下行3210622S0087→S3676的最佳路线乘车方案线路一换乘点1线路二换乘点2线路三总站数总时间总费用换乘次数1L454上行S3496L209下行2065212L021下行S0088L231环行S0427L462下行124632通过模型得到了6对查询点都不能通过一条线路直接到达，换乘一次，两次的较优线路，根据乘客的不同的需求，确定目标，选择适合自己的最佳线路。例如上面从站点到站点，如果乘客不想多次换乘，那么他就可以选择换乘一次的两条线路的一条，如果乘客想尽快到达终点站，那么他可以选择换乘两次的10条线路中的一条。6.1.2同时考虑公汽和地铁我们先算出问题中6对查询点一定上要一次地铁的最佳线路见表3：表3乘坐一次地铁的最佳线路始点→终点公汽线路一换乘点地铁线路地铁起点地铁终点公汽线路二换乘点时间费用S3359→S1828线路超过二次换乘，无法提供具体线路S1557→S0481L084下行S0978T2D32D24L516上行S0537116.55S0971→S0485L094上行S0567T1D1D20L417下行S207999.55S0008→S0073L159下行S2633T1D13S12L057上行S060975.55S0148→S0485L024下行S1487T1D2D20L417下行S2079915S0087→S3676——T2D27D36——363 再与只考虑公汽的最佳线路进行比较，选择时间最短的，得到S3359→S1828，S1557→S0481，S0008→S0073只乘坐公汽，S0971→S0485，S0148→S0485，S0087→S3676要乘坐地铁才能获得最短时间。6.2图论模型的求解 因为根据此模型得到的结果，根上面模型基本一致，在此本文就不再赘述，有兴趣的读者可以通过算法得到。7模型评价7.1基于集合寻点算法的模型的评价基于集合寻点算法的模型所给的查询系统是固定换乘次数基础上，算出能通过次换乘的所有线路。再通过对不同换乘数所得到的这些最佳线路，对这些线路的时间，费用的分别比较，通过层层的对比筛选排除，通过一些条件对最佳线路的进行处理，最后乘客可以根据自己的不同需求进行选择。其优点：模型中紧紧抓住选择最佳线路问题的突破点――换乘次数，通过集合的相关知识把难点――换乘点的具体位置的确定,转化成确定一些集合间的交集，从而把站点，线路与集合中的元素一一对应起来，建立起集合寻线算法，再根据集合相关公式，通过线路计算式子，有效地计算出最佳线路，并且考虑一些因素，如时间等对最佳线路进行处理。算法中有效的摒弃一些无效站点，从而大大减少了计算量和时间，明显比运用图论求得最短路要有效的多。能为查询者提供不同换乘次数下时间与路程最少的最佳线路，以及对于多条最佳线路，查询系统尽量采用不太热门的公交线路，随机地为查询者提供指定数目的线路，避免同一最佳线路过热的情况发生。其缺点：就是此模型只能为查询者提供换乘次数较少下的最佳线路，当换乘次数大于三时，模型实现的时间较长。7.2图论模型的评价由图论模型所得的查询系统，是以图论知识中的最短路有向图为基础，对不同线路经过同一站点时，假设多个假想点，并将各不同站点之间所需时间作为权，对各线路站点赋权，分别确定以时间、费用、换乘为目标转化为寻找有向的完全图，并根据实际情况，建立出动态赋权有向图，得出最佳线路。其优点：模型充分利用公交线路其实就是一个有向图，而且在比较成熟的最短路算法基础上，通过插入换乘时间，得到最佳线路。算法还是比较容易实现。其缺点：模型在引入步行，求费用最少，却不能实现。而且运用最短路算法，得到不一定是真正意义上的最佳线路，只能是近似最佳线路。8模型的推广建立此模型的思想，不但能应用到现在这种公交线路中，并能推广到海、陆、空多种交通线路之间寻找最优线路。通过实际情况对模型的进行调整，模型就能适应更多情况。例如图论模型中对有向图的权进行调整就能实现不同时间差站点的最佳线路的选择。参考文献[1]姜启源，谢金星.数学模型[M](第三版).北京:高等教育出版社,2003.[2]孙惠泉.图论及其应用[M].北京:,2004.[3]边肇祺,张学工等.模式识别[M](第二版).北京:清华大学出版社,1999.[4]蔡自兴,徐光祐.人工智能及其应用[M](第二版).北京:清华大学出版社,1996.[5]袁新生,邵大宏,郁时炼.LINGO和EXCEL在数学建模中的应用[M].北京:科学出版社,2007.

程序附录部分程序%数据的初始处理clcfid=fopen('QCLS.txt','r');Data=fread(fid);len=length(Data);gcl=0;qq=0;fori=1:len-1ifchar(Data(i))=='L'&qq==0gcl=gcl+1;GCLS{gcl}{1}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3)]);i=i+4;elseifchar(Data(i))=='L'&qq==1forj1=1:length(GCLS{gcl}{3})GCLS{gcl}{4}{j1}=GCLS{gcl}{3}{length(GCLS{gcl}{3})+1-j1};endgcl=gcl+1;qq=0;GCLS{gcl}{1}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3)]);i=i+4;elseifchar(Data(i)*256+Data(i+1))=='。'&char(Data(i+4))=='S'x=3;i=i+3;qq=1;s=0;elseifchar(Data(i)*256+Data(i+1))=='分'GCLS{gcl}{2}=1;i=i+8;elseifchar(Data(i)*256+Data(i+1))=='单'GCLS{gcl}{2}=2;i=i+11;elseifchar(Data(i)*256+Data(i+1))=='上'x=3;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1))=='下'x=4;i=i+4;qq=0;s=0;elseifchar(Data(i)*256+Data(i+1))=='环'x=5;i=i+4;qq=0;s=0;elseifchar(Data(i))=='S's=s+1;GCLS{gcl}{x}{s}=strcat([Data(i),Data(i+1),Data(i+2),Data(i+3),Data(i+4)]);clci=i+4;endendfori1=1:520iflength(GCLS{i1})~=5n=length(GCLS{i1}{3});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{3}{i2}=GCLS{i1}{3}{n-i2+1};endn=length(GCLS{i1}{4});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{4}{i2}=GCLS{i1}{4}{n-i2+1};endelseiflength(GCLS{i1})==5n=length(GCLS{i1}{5});GCLSF{i1}{1}=GCLS{i1}{1};GCLSF{i1}{2}=GCLS{i1}{2};fori2=1:nGCLSF{i1}{5}{i2}=GCLS{i1}{5}{n-i2+1};endendendclc%地铁情况的运算Untitled%读取文件DCLS%地铁文件处理ZHANDIAN2%各公交车站点处理k=input('输入初始站点');t=input('输入终点站');n=[];ZCSL1{1}=[];ZCSL1{2}=[];ZCSL2{1}=[];ZCSL2{2}=[];DDT1=[];DDT2=[];ZCSL1{3}=[];ZCSL2{3}=[];ZCSL1{4}=[];ZCSL2{4}=[];ll=size(ZD{k});DIST0=9999;fori=1:ll(1)n=str2num(ZD{k}(i,2:4));l=length(GCLS{n}{SL{k}(i)});forj=1:lifstr2num(GCLS{n}{SL{k}(i)}{j}(2:5))==kforjj=j+1:lif(jj-j)*3+10<DIST0ZCSL1{1}=[ZCSL1{1},str2num(GCLS{n}{1}(2:4))];ZCSL1{2}=[ZCSL1{2},GCLS{n}{2}];ZCSL1{3}=[ZCSL1{3},SL{k}(i)];ZCSL1{4}=[ZCSL1{4},jj-j];DDT1=[DDT1,str2num(GCLS{n}{SL{k}(i)}{jj}(2:5))];endendifSL{k}(i)==5forjj=2:j-1if(l-j+jj)*3+10<DIST0ZCSL1{1}=[ZCSL1{1},str2num(GCLSF{n}{1}(2:4))];ZCSL1{2}=[ZCSL1{2},GCLSF{n}{2}];ZCSL1{3}=[ZCSL1{3},SL{k}(i)];ZCSL1{4}=[ZCS