搜索
-1-出行系统中最优路线选择问题摘要本文在附件提供的公共交通信息的基础上，把所给数据处理成一个公交信息矩阵，便于Matlab软件的操作计算．从转乘次数出发逐层次地进行了较为深入的分析，将出行时间，出行费用，转乘次数三个方面综合起来考虑，最终选择出满足各种消费者的比较理想的出行线路选择方式．对于问题一，由公交信息矩阵得到所有站点的邻接矩阵，利用Floyd方法计算出任意两站A，B最少需要停靠的站点数，从而估计出两站间所有路线所需时间的下限．显然，因为转乘需要花费时间和增多费用，所以单方面考虑路线费或者是乘车费用，最优路线的换乘次数是有限的．由此给出定理一，由起始点A经过n次换乘到达终到点B的最短时间是时间最优解的充分条件为：对于换乘次数为n的最少费时路线，所需时间小于或等于(n+1)*5+3*(A，B最少需要经过的站点数)，则该路线是全局时间最优．这样，记录经过所给始末站点的全部公交车次，确定起始站和终到站之间是否可以有直达的车．如果有，统计出全部可以直达的车次，记录直达车经过的站点数以计算费用，由定理一判断出是否最优，若是最优，计算出具体时间，加权综合进行比较．如果不能直达，或者不是最优，则考虑所有由起始站经过一次换乘到达终点的情况．依此类推，考虑两次，三次…换乘，直到满足换乘到达终点并且满足定理一的条件为止．最后利用层次分析法根据消费者的不同需求加权选择出较为理想的线路．具体结果见表3(第7页)．对于问题二，首先将地铁系统作为单独系统考虑，用Floyd方法计算出地铁系统中任意出入口地铁行驶的最短时间；然后将地铁系统当成两个点集与公交网络相连，用问题一的算法，求出最少费时路线．综合考虑消费者的不同需求利用层次分析法加权选择出较为理想的线路．具体结果见表5(第10页)．对于问题三，在问题一和问题二的基础上，我们可以对模型进行简化，从而直接给出比较理想的线路选择．关键词：公交网络，换乘，时间，费用，Floyd算法，层次分析法(AnalyticHierarchyProcess)，最优方案-2-1．问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽、地铁等)出行．这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题．针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统．为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求．请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法．并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线(要有清晰的评价说明)．(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题．3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型．２．模型假设1．假设公共汽车，地铁，步行于相邻两站的时间是恒定的．2．假设三种出行方式的换乘时间是恒定的．3．假设所给公共汽车环形线路是单向的．4．假设两条地铁线路都是双向的．5．经过数据处理，假设一辆公车的上行和下行相当于两辆车，单行线公车也如此处理．6．基于费用和方便性的考虑，假设一次出行只进出一次地铁系统，并且在到达地铁系统之前若需要乘坐公交车，最多只转乘一次，出地铁系统之后也同样做这个假设．7．步行一站的时间是大于5分钟的，因此基于时间性的考虑，我们假设步行最多走两站．３．重要变量解释A起始点B终到点P公交车次和公交车次之间的邻接矩阵，其元素分别为1和0表示两车之间是否可以进行换乘L(A)经过起始站A的所有公交车次集合，其中元素是j1，j2，…，jmL(B)经过终到站B的所有公交车次集合，其中元素是k1，k2，…，kn-3-Sjp(1≦p≦m)L(A)中jp这辆车能够经过的站点集合Skq(1≦q≦n)L(B)中kq这辆车能够经过的站点集合T(D)地铁系统所有出入口组成的集合S(D)T(D)中出入口对应的公交车站组成的集合w层次分析法中的权系数(时间相对于费用的重要性，w越大，时间因素对结果的影响越大)注：其它临时变量在文中会有解释４．模型分析对于问题一，由于公汽行驶路线是固定的，对于只乘坐公交车的出行方式，若能直达，则费用能实现最小，但是就时间来讲不一定是最优值．我们可以利用Floyd算法给出两点之间经过的最小站点数，估计出时间的下界，并且进一步利用定理一确定出时间的最优值．但是对于时间的最优值，可能会出现要转乘多次的情况，而时间也没有节省多少．因此从实际情况出发，我们利用离散模型中的层次分析法进行分析，得到综合最优路线，也就能得到满足不同消费者不同要求的方案．问题二加入了地铁．从所给的数据可以看出，在地铁系统中的花费是常数，而且地铁的运行速度比公交车快很多．根据实际情况，可以想象，消费者都是以地铁作为首先选择的．我们可以将地铁系统单独提出来，相当于分段进行解决，并且可以利用问题一的算法．从实际情况出发，我们也能够得到综合最优解．最后可以综合问题一，重新利用层次分析法对方案进行加权处理，提供足够满足消费者要求的各种方案．问题三又进一步加入了步行，根据我们提出的假设7，可以这样分析：假设人步行一站来代替只坐一站的公交车，设人步行的时间是t，则比坐公交车节省1元，而时间多了(t-8)分钟；用人步行两站代替乘坐两站的公交车，节省一元，而时间多了(2t-11)分钟．根据这两个数据得到新的方案，加入层次分析法进行讨论．定理一：由起始点A经过n次换乘到达终到点B的最短时间是时间最优解的充分条件为：对于换乘次数为n的最少费时路线，若所需时间小于或等于(n+1)*5+3*p，则该路线是全局时间最优．p为A和B之间最少需要经过的站点数．证明：设经过n次换乘所需要的最短时间为t，经过n+1次换乘所需要的最短时间是t1．若t不是时间最优解，我们设t1(t)是时间最优的，则t1不小于所有经过n+1次换乘线路所需时间的下界，即t1≧5*(n+1)+3*p而由已知：5*(n+1)+3*p＞t说明t≤t1,与假设矛盾．定理得证．-4-5．模型的建立和求解5．1问题一的建立和求解我们从换乘次数出发，首先建立一个公交车次和公交车次之间的邻接矩阵P，来反映两辆公交车j，k是否能至少经过同一个站点，即两车之间是否可以进行换乘，分别用P(j,k)=1或P(j,k)=0表示．先考虑不需要换乘的情况．算出可以经过起始站A的所有公交车次，即集合L(A)，以及可以经过终到站B的所有公交车次，即集合L(B)．若有公交车m∈L(A)且m∈L(B)则说明从A到B可以通过公交车m直达，判断是否达到时间的最优解，并综合时间，费用两方面，找出能够直达的情况中相对最好的．再考虑需要转乘一次的情况．设L(A)中有m个元素，分别是j1，j2，……jm；L(B)其中有n个元素，分别是k1，k2……kn．若存在jp∈L(A)(1≦p≦m)，和kq∈L(B)(1≦q≦n)使得P(jp，kq)=1，则说明A，B两点可通过jp，kq两辆公交车转乘一次到达．另外，记L(A)中j1这辆车能够经过的站点集合记为Sj1，L(B)中k1这辆车能够经过的站点集合记为Sk1，以次类推．将Sjp(1≦p≦m)和Skq(1≦q≦n)两两作交，若有s同时属于Sjp和Skq，则s就是中转站．也就是说从A点可以乘坐jp到s然后转乘坐kq达到B．判断是否达到时间的最优解，同时从所有这种转乘一次的情况中找出所需时间最短或所需费用最少的方案，并可以与直达情况进行比较．进一步考虑需要转乘两次的情况．首先搜索这样的公交车d，d满足P(m，jp)=1且P(m，kq)=1，这就说明从A点乘坐jp出发，通过换乘d再换乘kq到达B．判断是否达到时间的最优解，同时从乘坐两次的情况中找出所需时间最短或所需费用最少的方案，并与上面两个方案进行比较．同理可以处理转乘三次及三次以上的情况．对于三次以上的情况，虽然可以通过计算确定它们会缩短一些时间，但缩短的程度不会很大，尤其进一步考虑费用和方便性，结合实际情况，这种线路的利用性不会很强．事实上，转乘三次之内的方案，虽然不能说它一定就是时间的最优，但综合时间，费用以及方便性，我们可以说它就是最优的．第二步，我们可以利用Floyd算法给出从A到B的最小站点数，用来估计出运行时间的下界，参看下面的表1．始末站最小站点数S0087→S3676S1557→S0481S0971→S0485S0008→S0073S0148→S0485S0087→S3676132527132510(表1)第三步，因为考虑到转乘次数的增多会使费用升高，同时时间也不会降低太大的幅度，我们仅在下面的表2中给出6条路线分别转乘一，二，三次的的情况，它们都实现了局部（对于转乘次数）费用的最优，另外给出了全局时间最优解，作以比较．需要注意的是所有的线路都没有直达车，S1557→S0481和S0148→S0485两条线没有转乘一次到达的车．-5-换乘次数始末站换乘一次时间最优换乘两次时间最优换乘三次时间最优全局时间最优S3359→S1828用时/分钟101737267(换乘五次)费用/元3346车站个数32211914路线下行L436至S1784转下行L167下行L352至S2903转上行L201至S1790转上行L041上行L015至S3917转环行L296至S0992转上行L475至S1671转上行L041上行L015至S1327转上行L328至S0525转上行L103至S0073转下行L480至S2704转上行L027至S1784转下行L167S1557→S0481用时/分钟1069999(换乘三次)费用/元344车站个数322828路线下行L363至S1919转下行L189至S3186转下行L460下行L084至S1919转下行L189至S3186转下行L091至S0902转上行L254下行L084至S1919转下行L189至S3186转下行L091至S0902转上行L254S0971→S0485用时/分钟128106105105(换乘三次)费用/元3344车站个数41323030路线下行L013至S2184转下行L417下行L263至S1609转下行L140至S2654转上行L469下行L263至S1609转上行L448至S2113转下行L002至2654转上行L469下行L263至S1609转上行L448至S2113转下行L002至2654转上行L469S0008→S0073用时/分钟83706359(换乘四次)费用/元2345车站个数29201613路线下行L463至S2083转上行L057上行L198至S1691转下行L476至S2083转上行L057上行L043至S1383转下行L282至S1327转上行L328至S0525转上行L103上行L198至S1691转下行L476至S2085转上行L017至S0483转上行L328至S0525转上行L073-6-S0148→S0485用时/分钟106102102(换乘三次)费用/元344车站个数322929路线上行L308至S0036转上行L156至S2210转下行L417上行L308至S3604转下行L081至S2361转上行L156至S2210转下行L417上行L308至S3604转下行L081至S2361转上行L156至S2210转下行L417S0087→S3676用时/分钟65465146(换乘两次)费用/元2343车站个数20121212路线上行L454至S3496转下行L209下行L021至S0088转环行L231至S0427转下行L462上行L206至S0088转环行L231至S1659转下行L4