基于ransac-sql的大规模公交网络出行路径选择算法

基于ransac-sql的大规模公交网络出行路径选择算法

0求解多目标规划问题的算法随着城市化进程的加快，公共交通的半径也在增加。因此，对于城市公共交通，行人在移动过程中会同时发送多次。如果你的交换次数过多，这将给行人带来极大的不便。因此，国内外对城市公交公共交通的决策和优化进行了大量研究，以尽量减少行人的交通不便。目前,出行决策模型方面的研究主要集中在以换乘次数最少和出行距离最短为目标形成的一个多目标规划问题.求解模型的算法主要是在将多目标问题模型转化为带有惩罚函数的单目标问题后用改进的Dijksta算法或Floyd算法求解;另一类主要是将多目标规划转化为有主次之分的两个单目标规划后用广度优先搜索或深度优先搜索算法求出行方案,然后在此基础上应用最短路径算法;第一类算法存在的不足主要是将最少换乘次数目标和出行距离最短目标用统一的尺度去度量,在统一为同一个量度的过程中难以标定换算的系数;第二类主要是在用深度优先搜索或广度优先搜索算法求出行选择方案的过程中搜索了大量不合理的出行路径,增加了算法不必要的执行次数.最重要的是大部分算法难以应用于大规模的实际公交网络或计算机实现时采用的数据结构大多是基于数组和链表结构,这种方法在应用到大规模公交网络中时容易产生维数爆炸或不方便管理维护数据.根据文献中对城市出行居民出行心理和行为调查研究的结果,本文建立以换乘次数最少和出行距离最短依次为目标的出行选择模型,为方便管理维护数据,公交网络数据结构采用大型数据库来存储,求解算法采用基于数据库技术中的存储过程和Transact-SQL语言来实现以提高算法执行效率.1线路和网点的设置考虑到实际公交网络规模都很大,尤其是大城市、特大城市的公交网络;比如,北京市将近650条公交线路,站点数约1万个左右,为使得公交线路、站点等相关数据易于维护、更新、管理及考虑计算机实现的方便程度和执行效率,这里考虑采用大型数据库SQLServer来存储线路、站点及站间距等有关数据.1.1线路运行方向城市公交网络主要是由线路和站点组成,线路方向类型主要有:东行、西行、南行、北行和环形线路,而实际线路号并没有区分方向,为维护数据的一致性和区别有方向的线路,在设计数据结构时根据实际运行方向给线路加上方向,比如101路公交线对应101路(东行)和101路(西行)两条不同线路或其它的方向(方向按实际情况确定),环形线路不考虑方向.线路主要是由公交站点组成,地理位置接近的同名站点考虑为同一站点,对于地理位置不接近的站点,对其中一个站点附加较出名的地理名称或建筑物名称形成别名来区别,比如:兰州市公交网络中,在黄河市场附近(较出名地理位置)有桥北站点,而在距此很远的中山桥(较出名建筑物)也有桥北站点,那么可将其中之一的站点名后附加较出名地理位置名称或建筑物名称,如桥北(中山桥).1.2设置合理路径或乘车路段根据公交网络组成及分析,考虑如何区分东、西行或南、北行等有方向的线路,给线路内部的站点附加线路内站点序号,比如:3路(东行)线路中的(起始)站点A、中间站点B、中间站点C、(终止)站点D依次标以自然数1,2,3,4,那么3路(西行)线路中的站点顺序为(起始)站点D、中间站点C中间站点B、(终止)站点A,线路内部序号依次为1,2,3,4.那么在出行路径选择中就可以通过站点在线路内部的序号来确定这是不是一条合理路径(或者乘车路段),例如,路径R1:站点A(序号为1)—3路(东行)—站点B(序号为2)为合理路径,而路径R2:站点A(序号为4)—3路(东行)—站点B(序号为2)就是不合理路径(或者乘车路段),因为根据公交站点在线路内部的序号和一条合理路径(或者乘车路段)模式“站点1—线路号—站点2”可知站点1的序号要低于站点2的序号.综上,借助大型数据库SQLServer设计如下数据结构来存储线路、站点、站间距等数据.表1(line_stop)存储线路、站点、站点在线路内部的序号,表2(distance)存储站点间距资料,它们的具体数据结构如表1和表2所示.2通过构造和无特别关联线路集合找准出行方案为了便于应用于实际中的大规模公交网络,本文借助数据库技术中实现关系代数运算简洁、迅速的优点,采用Transact-SQL语言编程思路和数据库中在服务器端运行且可以提高运算性能、效率的存储过程技术,设计了简洁、高效率的计算机算法.算法主要思路:将出行决策模型中的两个目标分层计算来实现,即先利用Transact-SQL语言编写存储过程实现关系代数中的有关运算从而得出直达、1次换乘、2次换乘出行方案,并将直达出行选择方案、1次换乘出行选择方案和2次换乘出行决策方案依次存储在数据库表zhida_fangan_trip、transfer_one_time_trip和表transfer_two_time_trip中,然后编写带参数的存储过程依次求解最佳出行方案.表zhida_fangan_trip、transfer_one_time_trip中的数据结构如表3,4所示,表transfer_two_time_trip的数据结构类似表4.算法实现的具体步骤如下:Step1创建带出发站点和目的地站点参数的存储过程;Step2从表line_stop中找出经过起始出发站点的所有线路集合#line_set_1(数据库中为临时表),从表line_stop中找出经过目的地站点的所有线路集合#line_set_2;Step3将集合#line_set_1和#line_set_2取交集得到集合#line_set_3;Step4判断集合#line_set_3是否为空,即临时表#line_set_3中是否有记录,若不为空,则存在从起始出发站点直达目的地站点的出行方案,并将方案存入数据库直达出行方案表zhida_fangan_trip中,转step13.若为空,转step5;Step5#line_set_3为空表示没有直达出行线路存在.找出线路集合#line_set_1的所有站点的集合#transfer_stop_set_1,找出线路集合#line_set_2的所有站点的集合#transfer_stop_set_2;Step6将站点集合#transfer_stop_set_1和#transfer_stop_set_2取交集得集合#transfer_stop_set_3;Step7判断集合#transfer_stop_set_3是否为空.如果不为空,则表示集合#transfer_stop_set_3是1次换乘站点集合,转step8;如果为空,表示通过1次换乘不能到达目的地,转step10;Step8找1次换乘出行方案:找出经过1次换乘站点集合#transfer_stop_set_3的所有线路集合line_set_4(具体实现时为数据库表,表中只有stop_name一个站点名称字段);Step9找出集合#line_set_1和集合line_set_4的交集line_set_5(具体实现时为数据库表,表中只有line_name一个线路名称字段)为第1次乘车的线路集合;找出集合line_set_4和#line_set_2的交集line_set_6(具体实现时为数据库表,表中只有line_name一个线路名称字段)为第1次换乘线路集合;按照“起始站点A—第1次乘车线路R1(集合)—第1次换乘站点B”模式及站点A和换乘站点B在线路R1中序号的大小判断线路是否可行(例如3路(东行)线路可以,则3路(西行)线路不可以)来得到1次换乘方案中的前半程方案,后半程方案如此类推,最后将可行1次换乘出行方案存入数据库1次换乘出行方案表transfer_one_time_trip中.Step10找2次换乘出行方案:找出经过站点集合#transfer_stop_set_1中任一站点的所有线路集合#transfer_line_1,找出经过站点集合#transfer_stop_set_2中任一站点的所有线路集合#transfer_line_1;找出集合#transfer_line_1和#transfer_line_1的交集#transfer_line_one,即为第1次换乘线路集合;Step11如果集合#transfer_line_one为空,转Step15,否则,转Step12;Step12找出2次换乘方案中第1次换乘集合#transfer_line_one中的所有站点集合#temp_transfer_stop;找出集合#temp_transfer_stop和#transfer_stop_set_1的交集#transfer_stop_11,即为2次换乘出行方案中的第1次换乘站点集合;找出集合#temp_transfer_stop和#transfer_stop_set_2的交集#transfer_stop_21,即为2次换乘出行方案中的第2次换乘站点集合;找出经过集合#transfer_stop_21的所有线路集合#line_set_12;找出集合#line_set_12与#line_set_2的交集#transfer_line_two,即为2次换乘出行方案的第2次换乘线路集合;找出经过1次换乘站集合#transfer_stop_11的所有线路集合#line_set_10,找出集合#line_set_10和#line_set_1的交集得2次换乘出行方案中的第1次乘车线路集合#line_set_11,按照step9中判断合理出行路径(或路段)的方式找出出行方案存入数据库2次换乘出行方案表transfer_two_time_trip中.Step13创建带输入、输出参数的求每一出行方案的出行距离的存储过程;Step14根据求得的出行距离找出最佳出行路径,算法终止.Step15没有2次换乘以内的公交出行方案,建议选择其它交通方式出行,算法终止.以上步骤中的集合运算在算法的计算机实现过程中均表示对应数据库中的表(table),表名前加有符号#的表示为数据库中的临时表,否则为数据库中的永久表(或对象),算法步骤中的集合运算均只需一条SQL语句即可实现集合运算,如Step2和Step3的具体实现语句如下:SELECTline_nameINTO#line_set_1FROMline_stopWHEREstop_name=@begin_stop_nameSELECTline_nameINTO#line_set_2FROMline_stopWHEREstop_name=@end_stop_nameSELECTline_nameINTO#line_set_3FROM#line_set_1WHEREline_nameIN(SELECTline_nameFROM#line_set_2)采用SQLServer中Transact-SQL语言来编写在服务器端运行的存储过程,存储过程将要处理数据的程序移动到离数据更近的地方,从而有力地保证了算法实现的计算机执行效率.3最佳出行路径创建在SQLServer中建立了公交网络数据库,并在系统中建立了相应的数据表,录入了兰州市24条公交线路数据和259个公交站点(如果按每条线路包含的公交站点计算,即有的站点有多条不同公交线路通过,那么,则有866个站点),基于本文中的假设:非环形线路都考虑双向运营,即或东行或西行或南行或北行中的两个方向,那么数据库系统中共有48条有方向的公交线路数据资料.经在SQLServer查询分析器工具中执行查找出行换乘方案的带任意出发站点、目的地站点参数的存储过程,找到直达出行方案、1次换乘出行方案和2次换乘出行方案的执行时间均不到1秒,执行时间基本上是以毫秒级来度量,而且经人工在兰州市公共交通地图(有详细站点和线路)上检验所得方案均是合理的最佳方案.算法程序运行的软、硬件环境:ACER台式机,操作系统为Windows2003Server,CPU为IntelPentium2.6GHz,内存为256MB,数据库服务器为SQLServer2000EnterpriseEdition.例如在SQLServer查询分析器工具中输入、执行存储过程:find_trip_strategy‘兰州车站’,‘交通大学’.系统马上输出查询到的方案如表5所示:因为程序没有找到直达出行方案,所以输出的是1次换乘出行方案,在找到1次换乘出行方案后,程序不再查找2次换乘出行方案,因为本文中的目标是以换乘次数最少为首要目标,即认为出行换乘次数比出行距离占有不可替代的权重.然后利用创建的求出行方案旅行距离的存储过程即可找