点线搜索逐步扩展的公交线路查询模型及算法

1点线搜索逐步扩展的公交线路查询模型及算法摘要第29届奥运会明年8月将在北京举行，北京市的交通网络十分庞大，其中大部分人将会乘坐公共交通工具，包括公汽、地铁等出行。观众从一个地方到另一个地方需要查询可达的方式及路线，那么如何选择路线才可以适合观众的要求？本文针对任意输入两个站点，可以迅速查询到可达方式及路线的问题，分为仅仅考虑公汽线路之间的乘坐和转乘，同时考虑公汽和地铁之间的乘坐和转乘，公汽、地铁、步行混合交通出行三种情况，给出线路选择的模型与算法，并应用Matlab软件编程实现，检验了模型与算法是合理、高效的。该问题的关键是解决如何在多线路、多方式、多站点的复杂网络中任意选择两个站点，快速找到出行方式和路线的问题。为此通过所给线路和站点的数据，巧妙构造一个带有查找特征“站点——线路关系”的矩阵，把所有站点进行编号，作为矩阵的列的编号；把所有线路区分上行、下行进行编号作为矩阵的行的编号。矩阵中元素的填法为：与列的站点编号对应，将每条线路在运行途中的第一个站点标注为1，第二个站点标为2，不经过的站点标为0依此类推，直到最后一个站点。实际上构造了一个有向图。这样构造的矩阵的优点是：能反映每条线的运行方向、可判断任意两站之间的站点数，横看为该条线路上的站点、竖看为该站点有几条线路通过；便于建立站点和线之间的“点——线”对应关系，即找经过该点的线路和该线路对应的站点；而且该矩阵便于Matlab编程操作。基于所构造的矩阵，可以构造基于集合理论的“逐步扩展搜索法”，对不同的出现方式、对任意两输入点毫无疏漏地查找直达线路、转乘点、转乘线路、转乘次数；把地铁线路和步行作为特殊线路加入表中，即可以顺序解决所提到的三个问题，这样建立的模型和算法简捷、耗时非常短，完全可以满足适时查询要求。根据人们选乘公交出行的偏好——考虑时间最短、费用最省、尽可能的少转车，对查找到的站点和路线进行目标优化，最后给出结果。任意输入两个站点，三个问题的结果是：（1）问题一，只考虑公汽线路时建立了模型与算法并利用所建模型求出了给定两个站的最优路线；（2）问题二，同时考虑公汽与地铁线路时建立了模型与算法并利用所建模型求出了给定两个站的最优路线；（3）问题三，假设任意两站之间的人的步行时间为10分钟，在考虑可以步行转乘的情况下建立了模型与算法。并且比较得出若增加约束条件后最优路线可能改变的结论。用程序验证了当站点数和线路数比目前所给的站点数和线路数更多时，所提出这种“点——线”逐步扩展搜索法在时间运行上几乎不受影响。关键词：有向图点线交替运算逐步扩展搜索法站点路线2一模型的分析乘公交，看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。目前北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。为此，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决如下问题：1仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用所建立的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762同时考虑公汽与地铁线路，解决以上问题。3假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。因为站点数和线路数较多，因此这是一个在高度复杂网络中查找线路的问题，一般情况下用图论和矩阵的相应方法建立模型求解。但本问题的拓扑结构复杂，可以有多种方法建立模型，大多数程情况下程序实现较为困难，特别是计算时间需要较长，不能适应适时快速查询的要求。为此需要寻求一种快速、高效的方法。问题涉及到的因素有人、道路、站点、车，还有省时、省钱的问题。解决问题的关键为站点和线路的查找，因此建立一个站点与线路相对应的邻接矩阵，构造有向图；又因为站点与线路的问题是元素与集合的问题，所以用集合理论来建立查找站点和路线，由站点找到线路，再进行优化，从而解决问题。二问题初始化与模型假设1．基本参数设定A.相邻公汽站平均行驶时间(包括停站时间)：3分钟B.相邻地铁站平均行驶时间(包括停站时间)：2.5分钟C.公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)D.地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)E.地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)F.公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合2．定义集合与矩阵A.线集合：iLi=1，…1040；B.站点集合：iSi=1，…3957；C.矩阵ij1044*88B=(b)，i=1041，1042时为地铁线，1043步行。前2到87列顺序记录iL线上所途径的站点，第88列记录票价情况，单一票价记为-2，分段计价记为-1，地铁线记为-3，。3D.矩阵ijA=(a)，其中若jS站不在Li线上则ija0，否则ija表示jS站位于Li线上的站点次序。i=1，…1043；j=1，…39573．假设以下几个条件：A.公交车运行时间不因交通环境变化而改变。B.乘环行公交到起始站乘客必须全部下车，重新乘车，视为换乘。C.假设公交车的运量不受限制，车到站乘客即可上车。D.假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，只分别考虑一次地铁换公交，公交换地铁的时间，即13分钟。E.假设人行走时的平均速度是一定的。F.假设不论是公汽线，地铁线以及步行求最优解时只考虑单一因素。三问题的预处理该问题是要求给出公交查询系统的算法模型，便于乘客查询出行更加通畅、便利的乘坐路线。以节省时间、最短路程、转乘次数最少建立模型进行优化，以适应不同需求的乘客。该问题的重点在于找到直达，转乘一次可达，转乘两次以及两次以上可达的路线。我们首先对题目中的数据进行了处理。1．线路重编号因为公交车的运行方式有三种：单程，上下行，环行。所以我们针对三类数据给出了三种处理方法。单程是公交车上行和下行的站点完全相同，上下行是公交车的运行的过程有不同的站点，环行则没有起始站和终到站的区别。这样我们把给出的520个编号的线路都分成了两条线，这两条线的编号相差520。单程：（以L001为例）上行：L001S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710S0619S1914S0388S0348S0392S0429S0436S388512345678S3612S0819S3524S0820S3914S0128S07109101112131415那么它的另一条路线是下行：L521（L001的反向线）S0710-S0128-S3914-S0820-S3524-S0819-S3612-S3885-S0436-S0429-S0392-S0348-S0388-S1914S0619上下行（以L111为例）上行：L111S3543-S0202-S1023-S2293-S3170-S1954-S1955-S1957-S2323-S2321-S2397S3543S0202S1023S2293S3170S1954S1955S1957S2323S2321S2397S0710S0128S3914S0820S3524S0819S3612S388512345678S0436S0429S0392S0348S0388S1914S0619910111213141541234567891011下行：L531S2397-S0147-S2321-S2323-S1957-S1955-S2962-S3170-S2293S2293-S1023-S3813-S3543S2397S0147S2321S2323S1957S1955S2962S317012345678S2293S1023S3813S35439101112环行：根据观察我们发现环行线有两种，可分别等价成两种不同的路线来考虑。总的思想是去环。单环（只是首尾相接的）：以L027为例，只需把他的首尾站去掉一个，然后当成只有去路的上行线来考虑。它所对应的“下行线”的编号即为L547，它不通过任何一个站点。第二种环：采用破圈法以L425为例。S1042-S0130-S3019-S0969-S3741-S1963-S3741-S3019-S0477-S1042，由S1963站点分开为上下行线。上行：L425S1042-S0130-S3019-S0969-S3741-S1963S1042S0130S3019S0969S3741S1963123456下行：L945S1963-S3741-S3019-S0477-S1042S1963S3741S3019S0477S104212345据此，所有公交车都区分为上、下行线路。这样所有线路相当于有1040路单行公交车。这样做在计算中可以大大减少计算量：（1）按先后顺序编号，可以看出公交车的运行方向，且只有编号小的站可以到达编号大的站。（2）可以直接看出公交车各站点之间的距离。2．站点处理题目给出了3957个站点，若用关联矩阵建立任意两个点之间的关系，那么可以生成一个39573957的矩阵，这样建立模型较为复杂。所以先建立了一个简单的矩阵B。它的行标为1—1043，列标为所有公交车线路中经过的最大站点数。它反映的是i线上的车站顺序，即（i，j）元上存放的是在i线上的站点号。并且在最后一列，增加一列，作为标志区分几种计价方式。与前定义集合与矩阵中的B同。3．费用计算如果记录为-1，则为单一计价，此时费用c=1。如果记录为-2，则为分段计价，需判断d与站数20，40的函数关系，进而求出费用c。如果记录为-3，那么此时为地铁线路，这时判断两汽车站是否在同一地铁站点上，若在c=0，否则c=3。如果记录为-4此时代表步行，c=0。四模型建立1算法思想利用基于集合理论的“逐步点线扩展搜索法”。5核心思想：根据所建立的关联矩阵，根据站点和线路的对应关系，“点——线——点”或“线——点——线”转换，即乘客在s站点，欲到t站点，则遍历所有经过s站点的公交线路，并求该路线上的站点组成的集合。数学描述：设()iA表示经过iS站点的线路集，i=1，…3957；()jB表示经过第j条路线的站点集，j=1，…3957。1．不需要转乘的情况：在关联矩阵中表现为sS和tS两个不同的站点在同一行内可找到，即在同一条线上，且矩阵对应元素不为零。集合描述为：对s、t两个不同的站点对应的站点集分别为()sA和()tA，如果()()stAA，那么s、t两站点间有直达车，对直达线路进行优化，给出最便捷的线路；如果()()stAA，则说明这两个站点没有直达车，至少需要转乘。执行下一步程序。2．需要转乘一次的情况：通过站点s的所有线路不通过站点t，而通过站点t的所有路线都不通过站点s。在关联矩阵中表现为s、t站点对应的不为零的数不在同一行。由通过s站点的所有公交线路上的站点组成集合()sA，通过t站点的所有公交线路上的站点组成集合()tA。然后求站点集之间的交集，()()stAA，则s、t两个站点的关系是需要转乘一次。那么设()()()slAEsBl，即将通过s站点的所有线路上的站点求一个并集。()()()tlAEtBl即将通过t点的所有线路上的点求一个并集。()Bl为l线上的站点的集合。()()EsEt，说明s,t两站点转一次车即可到达，转车点为()()EsEt，在进行优化，选择最便捷的。如果()()EsEt，那么一次转乘不能达到，考虑转乘两次，转入下一步。3．需要转乘两次：通过s、t两个站点的线路上的站点集没有交集，()