出行系统中最优路线选择问题摘要本文在附件提供的公共交通信息的基础上，把所给数据处理成一个公交信息矩阵，便于Matlab软件的操作计算．从转乘次数出发逐层次地进行了较为深入的分析，将出行时间，出行费用，转乘次数三个方面综合起来考虑，最终选择出满足各种消费者的比较理想的出行线路选择方式．对于问题一，由公交信息矩阵得到所有站点的邻接矩阵，利用Floyd方法计算出任意两站A，B最少需要停靠的站点数，从而估计出两站间所有路线所需时间的下限．显然，因为转乘需要花费时间和增多费用，所以单方面考虑路线费或者是乘车费用，最优路线的换乘次数是有限的．由此给出定理一，由起始点A经过n次换乘到达终到点B的最短时间是时间最优解的充分条件为：对于换乘次数为n的最少费时路线，所需时间小于或等于（n+1）*5+3*（A，B最少需要经过的站点数），则该路线是全局时间最优．这样，记录经过所给始末站点的全部公交车次，确定起始站和终到站之间是否可以有直达的车．如果有，统计出全部可以直达的车次，记录直达车经过的站点数以计算费用，由定理一判断出是否最优，若是最优，计算出具体时间，加权综合进行比较．如果不能直达，或者不是最优，则考虑所有由起始站经过一次换乘到达终点的情况.依此类推，考虑两次，三次…换乘，直到满足换乘到达终点并且满足定理一的条件为止．最后利用层次分析法根据消费者的不同需求加权选择出较为理想的线路．具体结果见表3（第7页）．对于问题二，首先将地铁系统作为单独系统考虑，用Floyd方法计算出地铁系统中任意出入口地铁行驶的最短时间；然后将地铁系统当成两个点集与公交网络相连，用问题一的算法，求出最少费时路线．综合考虑消费者的不同需求利用层次分析法加权选择出较为理想的线路．具体结果见表5（第10页）．对于问题三，在问题一和问题二的基础上，我们可以对模型进行简化，从而直接给出比较理想的线路选择．关键词：公交网络，换乘，时间，费用，Floyd算法，层次分析法（AnalyticHierarchyProcess）最优方案1．问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具(简称公交，包括公汽、地铁等)出行．这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题．针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统．为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求．请你们解决如下问题：2 1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法•并根据附录数据，利用你们的模型与算法，求出以下6对起始站一终到站之间的最佳路线(要有清晰的评价说明)．(1)、S3354S1828(2)、S1557—S0481(3)、S0971—S0485(4)、S000IS0073(5)、S0148—S0485(6)、S0087—S36762、同时考虑公汽与地铁线路，解决以上问题．3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型．.模型假设3 1．假设公共汽车，地铁，步行于相邻两站的时间是恒定的．2．假设三种出行方式的换乘时间是恒定的．3．假设所给公共汽车环形线路是单向的．4．假设两条地铁线路都是双向的．5．经过数据处理，假设一辆公车的上行和下行相当于两辆车，单行线公车也如此处理．6．基于费用和方便性的考虑，假设一次出行只进出一次地铁系统，并且在到达地铁系统之前若需要乘坐公交车，最多只转乘一次，出地铁系统之后也同样做这个假设．7．步行一站的时间是大于5分钟的，因此基于时间性的考虑，我们假设步行最多走两站．.重要变量解释起始点终到点公交车次和公交车次之间的邻接矩阵，其元素分别为j2，,，jmk2，,，kn表示两车之间是否可以进行换乘L(A)L(B)经过起始站A的所有公交车次集合，其中元素是j1，经过终到站B的所有公交车次集合，其中元素是k1，Sp(1三p三m)L(A)中jp这辆车能够经过的站点集合Skq(1三q三n)L(B)中kq这辆车能够经过的站点集合T(D)地铁系统所有出入口组成的集合S(D)T(D)中出入口对应的公交车站组成的集合w层次分析法中的权系数(时间相对于费用的重要性，w越大，时间因素对结果的影响越大)4 注：其它临时变量在文中会有解释.模型分析对于问题一，由于公汽行驶路线是固定的，对于只乘坐公交车的出行方式，若能直达，则费用能实现最小，但是就时间来讲不一定是最优值.我们可以利用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不是时间最优解，我们设ti(vt)是时间最优的，贝Uti不小于所有经过n+1次换乘线路所需时间的下界，即ti=5*(n+1)+3*p而由已知：5*(n+1)+3*p>t说明t