公交查询系统的最佳乘车方案设计1

公交查询系统的最佳乘车方案设计摘要本文研究的问题是针对已知的公交线路信息如何设计出最佳的乘车方案。首先，进行数据处理，用excel对数据进行整合处理，建立起公交线路矩阵。然后，上网查阅了公交乘客乘车心理分析的资料，得出影响乘客出行的三个主要因素分别为：换乘次数、出行时间、出行费用，通过互联网调查研究的数据，得出换乘次数最少是乘客出行考虑的最主要因素，其次是出行时间和出行费用。随后，建立了站点—线路序列模型。利用公交乘客的出行过程抽象为站点—线路的交替转换的思想，从而确定了出行者出行路线的一般数学表达式。针对问题一，仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标、乘车费用为第三目标，建立起多目标最优化分层求解模型。并依靠站点—线路序列模型确定的出行线路表达式，采用图论中计算方法并结合广度搜索法经matlab编程(见附录一)得到了公交乘客的最少换乘次数，所经过的站点，出行时间、出行费用(见表)。针对问题二，在问题一的基础上考虑了地铁线路，处理的方法是将地铁线当成特殊的公交线，将地铁站点当成公交站点并与给定的公交站连接。建立起多目标最优化分层求解模型，并以换乘次数最少、出行时间、乘车费用分别为一、二、三目标。按照问题一的算法得到乘客的最少换乘次数，所经过的站点，出行时间、出行费用(见表)。针对问题三，在问题二的基础上考虑了所有站点之间的步行时间，设出相邻两站之间人步行时间是公汽时间的k倍。步行线路设计与公汽线路相同但每条均有上行和下行。将步行线路矩阵与公交线路矩阵整合后建立多目标最优化分层求解模型按照问题二的算法得到乘客的最少换乘次数，所经过的站点，出行时间、出行费用(见表)。最后，建立公交负载模型对前三问的模型进行了改进。考虑到了实际中公交线路堵车的情况，将堵车线路拆分为两段新的线路并相应改变公交线路矩阵。算法与前三问算法相同，但使得最佳路径的选择更加灵活且更符合实际情况。关键词：分层求解交替序列多目标最优化改进广度搜索法1问题重述1.1问题背景我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。1.2需要解决的问题为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2模型的假设及符号说明2.1模型假设假设1：假设乘客都是理性乘车且能顺利到达目的地假设2：假设不考虑红绿灯造成的等待时间，不考虑堵车，车祸等因素假设3：假设乘客能接受的最大换乘次数为2次假设4：假设乘客乘车过程中不能2次经过同一站点。假设5：假设公交与地铁换乘距离固定，换乘步行时间为常数2.2符号说明符号说明SS公汽站点集，395700020001,,,SSSSLL表示公汽线路集，520002001,,,LLLLDD地铁站点集，390201,,,DDDDTT表示地铁线路集，21,TTTvikikv出行者选择第i条公交线路所经过的第k个站点(Svik或Dvik)ikPikP出行者选择第i条公交线路所乘坐的第k辆公交工具(LPik或TPik)Ni换乘次数Si途经的车站数ti行程时间Qi所需费用3问题分析本文研究的问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑，以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。针对问题一：问题一要求只考虑公汽线路，给出最佳路径。通过查阅相关资料，知道对乘客影响最大的三个因素：换乘次数，行程时间，所需费用(重要性从大到小)。据此，我们建立以换乘次数为第一目标，行程时间最为第二目标，所需费用为第三目标的多目标最优化模型。对于换乘次数，联系被选择线路上的站点—线路交替序列TRi个数可以表示出来；站点总数则采用给同一线路上的站点排序的方法也可以求到，由于只考虑了公汽之间的换乘，则出行时间只与换乘次数和所历站数有关；对于出行费用则在换乘次数的基础上，引入分段计价的加价函数也可求得。针对问题二：问题二在一得基础上考虑可以搭乘地铁，乘客的选择更加灵活。主要变化为：地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少；地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费耗时换乘到下一个公汽站。我们可以把跨公交站的步行视为一种免费耗时的交通方式，据此分层求解。针对问题三：考虑到出行者在步行时，所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知，步行时所经过的两站点之间的步行时间是一个已知值。当换乘的两站之间站数不多时，我们考虑步行，这要可以减少换乘次数，节约金钱。4数据处理及分析4.1数据处理4.1.1数据统计我们运用Excel软件对给的“公汽线路信息”和“地铁线路信息”进行统计得到如下数据：表1公汽线路站点数地铁线路分段计价单一票价上下行路径不同上下行路径相同环形路线公汽站点地铁站点直行线路环形线路283条237条409条89条22条3957个39个1条1条公交系统共有公汽线路520条总站点3996个地铁线路共2条根据表一并结合本文参数设定中的票价信息，综合考虑，分析如下：在分段计价路线中，共有27条的公汽站点数不超过20，有148条的公汽站点数在21~40之间，公汽站点数超过40的线路有108条。因此，从单独的计算角度来考虑，可以将分段计价中站数不超过20的线路归为单一票制1元的线路，因此上述信息可修正为：票价信息为单一票制1元的线路264条；在分段计价的路线中，共有256条，其中有148条的公汽站点数在21~40之间，公汽站点数超过40的线路有108条。4.1.2数据的储存与处理由于所给的数据格式不利于程序软件直接读取和操作，我们运用Excel将数据处理为规范格式，建立起公交线路矩阵A。(1)把公汽线路信息以及地铁线路信息分别导入到Excel表格中(2)将公汽数据中的上下行相同、上下行不同、环行的线路分别找出并归类。(3)将上下行相同的上行序列倒序后作为下行序列。则每条线路对应两个行向量。(4)环行线路若有n个站点，则依次以每个站点为起点和终点建立起n条首位相同的线路序列。(5)在第k条线路对应的所有序列前加上数字k作为标记列，其意义为第k条路线。(6)运用Excel的查找替换功能将公汽站点编号“S”和地铁站点编号“D”分别用0和111代替。目的是为了在汽车站和地铁站区别的条件下让matlab可以识别和进行矩阵操作。(7)将所有的序列整合到同一个excel表中，建立交线路矩阵A，每一行储存一条线路站点信息，没有信息的点用“0”填充。公交线路矩阵A11121312122232123...ddnnnndvvvvvvvvAvvvv建立交线路矩阵A后，我们可以把矩阵A导入MATLAB中，运用改进广度搜索算法求解最佳路径。5模型的准备5.1乘客心理调查北京公交车线路达800条以上，每一个公交站点可能有多条线路贯穿，通往不同的起点或终点，同样，一个目的地也可由多条线路到达，错综复杂的公交车路线犹如网状般将各站点联系起来，将城市的行人们带到其各自的目的地。我们通过互联网查阅相关资料发现，影响乘客公交线路的选择，主要有以下几个因素：换乘次数，行程时间，所需费用，途经的总站数等。其中有18.6%的乘客出行时，首先考虑的是乘车费用，30.4%的乘客首先考虑的是行程时间，42%的乘客首先考虑的是换乘次数.图1：乘客出行调查图0.00%5.00%10.00%15.00%20.00%25.00%30.00%35.00%40.00%45.00%所需费用行程时间换乘次数其它就乘客本身而言，公交乘客出行更多考虑的是出行的方便性和舒适性，下面就影响公交乘客出行的各因素进行具体分析，不妨将以上影响因素作如下归纳解释：(1)换乘次数：出行者完成一次从出发点到终点出行过程中所换车的次数。(2)行程时间：出行者在一次乘公交出行过程中所用的总时间。(3)所需费用：出行者在完成一次由起点到达目的地过程中所花的车费。(4)途径的总站数：出行者完成一次出发点到终点过程中所经过的车站总数5.2影响选择因素分析“换乘次数”和“行程时间”是影响出行者的两个独立的因素，经研究表明多数的公交乘客希望换乘次数最少，况且公交公司对公交线路的设计也是尽量减少乘客的平均换乘次数；而且公交乘客出行时还受到行李、地理位置等客观因素的影响，这样更不希望有较多的换乘。其次对于看奥运非常心切的出行者来讲，出行耗时对他们也是比较关键的。在此当给出供乘客选择的公交路线也应当尽可能的满足公交乘客的需求。当然，在此基础上我们还要考虑乘车费用。综上所述，可以以换乘次数最少为第一目标，再选择易于量化的“出行时间”和“所需费用”作为第二位的优化目标。由此，我们认为，乘客在选择路线时，可以根据自己的不同需求，对线路进行选择。5.3最优乘车方案算法分析在站点上放置一个便于乘客查询到达目的地的理想乘车方案的计算机系统，必须让计算机收集到本站到其他任意一站的路径与换乘信息，因此单独设计这样的算法是相当困难的，而且算法的精度要求也比较高。对本文附件中的公交系统中所列的3957个公汽站点和39个地铁站点来说，直接要得到所有任意两站点之间的最优公交路径的计算量是相当大的。当面对这样一个密集的交通网络来说，对路线的选择主要是将面临一个P类问题，根据P类问题的处理特点，可以用某种主次改进的方法来求解。由于每次改进中的计算量都是多项式界的，改进的次数也是多项式界的。目前已找到具有这种特性的算法，如椭球算法，卡马卡算法，但都相当复杂。因此要满足出行者的路线需求，则有必要对目标进行归类筛选，以降低不必要的选择、计算与搜索。不妨采用改进的广度优先搜索算法，基于改进次数为多项式界的算法理论，本文选择从某次乘公交的起点和终点的两端进行同时搜索，在满足换乘次数最少的条件下寻找不同线路中的共同站点或不同站点之间的相同线路，并计算其总路线的中的乘车时间和站点数。6站点—线路交替序列模型的建立6.1模型的建立本文所要解决的根本问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑，以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。我们建立交替序列模型寻找最优线路。6.1.1模型的预处理出行者所选择出行的起始站为v0，终到站为vd，从v0到vd的所有路径的集合也为TR，其中第i条路径为TRi，所乘坐的第k节公交工具为pik。进一步分析和考虑出行者乘公交的具体情况，一个出行者的出行可简单描述为如下路径图2：出行者选乘公交路径规律分析示意图从图中内容也可以反应，出行者出行乘公交的路径可看着是站点、车次、站点、车次的交替进行，直至到达终到站。为区别前后的车次或站点，使得前后排列的站点与车次都有一定的顺序，由于出行者不能在同一站点上出现两次，即vik各不相同，特别地令0