论文部分内容阅读
【摘 要】在庞大的公交网络系统中如何选择最优的出行方案是居民普遍关心的问题。文章基于计算机算法实现了对出行方案快速高效的选择,首先设计了公交网络数据结构,其次详细阐述基于SQL语言的算法步骤,最后以具体实例证实本研究的快速性及准确性,本文的研究为居民的出行提供了快速高效的解决方案。
【关键词】计算机算法 城市公交网络 出行路径
近年来,研究人们出行过程换乘交通工具决策优化问题,以提高人们的出行效率,是一个亟待解决的议题。本研究综合以往研究所用的方法并结合人们出行情况的问卷调查结果,建立了以最少换乘次数以及最短外出距离为最终出行目标的模型。为了避免数据爆炸的出现,选用的储存公交网络数据的数据库是大型的,这样便于对数据进行管理和维护,为了提高算法运算速度,选用Transace—SQL语言的求解算法。
公交网络数据结构
根据公交网络的构成情况,为了区分各方向上的线路及站点,本节首先对每个线路中的站点进行编号。例如,10路(南行)线路中的第一站a、中间站b、中间站c、最后一站d分别用1、2、3、4进行编号,那么10路(北行)线路中的站点第一站d、中间站c、中间站b、最后一站a的自然数编号为1、2、3、4。同时,借助SQL server设计如表1、表2所示的储存站点、线路以及编号的数据结构。
表1 线路站点
表2 公交站点间距
求解步骤
本算法的求解思想是:将两个目标进行分层处理,也就是说利用Transace—SQL语言的编写程序实现操作中所需的运算,能够得到不同换乘次数(0次即直达、1次、2次)的出行方案,并将所得的方案存储于相应的数据库表(如表3、表4所示)中,接着编写储存过程的参数,进而选出最优的出行方案。
表3 直达方案
表4 一次换乘方案
具体步骤如下:⑴创建一个带参数的存储过程,该参数包括初始站和目的站。⑵从表1中分别找出所有经过初始站和目的站的线路集合,命名为line-set-1,line-set-2。⑶将上一步所得的两个集合取交集,得到的集合命名为line-set-3。⑷判断上步所得到的交集中是否为空,如果不是空值,那么存在直达出行方案,进而将该方案存入表3,转到步骤⒀;如果是空值,则转到步骤⑸。⑸分别找出line-set-1和line-set-2所对应的所有站点的集合,依次命名为Transfer-stop-set-1和Transfer-stop-set-2。⑹将上一步得到的两个集合取交集得到的集合命名为Transfer-stop-set-3。⑺判断⑹得到的集合是否为空,如果不是空值,那么则说明通过一次换乘能到达目的站,转而进行步骤⑻;如果是空值,则转到步骤⑽。⑻找出Transfer-stop-set-3集合中所有的1次换乘线路,命名为line-set-4。⑼将集合line-set-1与line-set-4取交集,得到的集合命名为line-set-5,表示第一次乘车的路经集;将集合line-set-2与line-set-4取交集,得到的集合命名为line-set-6,表示第一次换乘的路经集;依据模式“初始站a—首次乘车路径L1—首次换乘站b”以及站a和换乘站b在路径L1中的自然数编号的大小来确定所选择的路径是否是正确的(例如10路(南行)路径正确,则10路(北行)路径错误),由此得到一次换乘中的上一段路径方案,如此类推可以得到下半段换乘方案。⑽分别找出Transfer-stop-set-1和Transfer-stop-set-2所对应的所有线路集合,命名为Transfer-line-1和Transfer-line-2;将所得的两个集合取交集,得到的新集合为第一次换乘线路集合,命名为Transfer-line-one。⑾如果上步最后所得到的集合是空集,则到步骤⒂;如果不是空集,则到步骤⑿。⑿找出Transfer-line-one里边的全部站点集合,命名为temp-transfer-stop,将其分别与Transfer-stop-set-1和Transfer-stop-set-2取交集,得到的集合依次命名为Transfer-stop-11和Transfer-stop-21;分别找出经过Transfer-stop-11和Transfer-stop-21的全部线路集合,依次命名为line-set-10、line-set-12,并将line-set-12与集合line-set-2取交集,得到的集合依次命名为Transfer-line-two,将line-set-10与line-set-1取交集,得到的集合line-set-11,并依照⑼中的方法将得到的外出方案存入transfer-two-time-trip表。⒀建立所有外出方案的外出距离的存储过程,并且都要带有输入和输出参数。⒁依照上步得到的外出距离找到最优的外出路线,则算法结束。⒂如果换乘次数是在3次及以上,则建议选用其他交通工具出行,则算法结束。
实际应用分析
利用上文给出的求解步骤,本文以武汉市的260个公交站点和25条公交线路数据为数据基础,建立数据库以及数据表。比如,出发站为“武汉车站”,目的站为“武汉大学”,需要在SQL查询分析器中输入:find-trip-strategy‘武汉车站’‘武汉大学’,系统立即可得到如下表所示方案。
表5 一次换乘方案
说明,从武汉车站到武汉大学之间没有直达的线路,所以得到了一次换乘方案,由于本研究基于的目标是最少的换乘次数,所以该表输出即为最终换乘结果方案表,接着依据所建立的外出方案距离的存储过程得到所需的最优外出路线。
结 语
该研究为解决庞大公交网络系统下的快速高效选择出行方案提供了可行思路,为人们的出行带来了一定程度的便利。参考文献:
[1]温金辉.用于最短路算法的公交网络模型构建[J].交通标准化,2011(08):35-38.
[2]汪涛,许乐,张继,方志耕.城市公交网络的拓扑结构及其演化模型研究[J].公路交通科技,2009(11):42-45.
[3]王东,刘刚.基于复杂网络的城市公交网络的研究[J].统计研究,2008(11):52.
作者单位:陕西国防工业职业技术学院 陕西西安
【关键词】计算机算法 城市公交网络 出行路径
近年来,研究人们出行过程换乘交通工具决策优化问题,以提高人们的出行效率,是一个亟待解决的议题。本研究综合以往研究所用的方法并结合人们出行情况的问卷调查结果,建立了以最少换乘次数以及最短外出距离为最终出行目标的模型。为了避免数据爆炸的出现,选用的储存公交网络数据的数据库是大型的,这样便于对数据进行管理和维护,为了提高算法运算速度,选用Transace—SQL语言的求解算法。
公交网络数据结构
根据公交网络的构成情况,为了区分各方向上的线路及站点,本节首先对每个线路中的站点进行编号。例如,10路(南行)线路中的第一站a、中间站b、中间站c、最后一站d分别用1、2、3、4进行编号,那么10路(北行)线路中的站点第一站d、中间站c、中间站b、最后一站a的自然数编号为1、2、3、4。同时,借助SQL server设计如表1、表2所示的储存站点、线路以及编号的数据结构。
表1 线路站点
表2 公交站点间距
求解步骤
本算法的求解思想是:将两个目标进行分层处理,也就是说利用Transace—SQL语言的编写程序实现操作中所需的运算,能够得到不同换乘次数(0次即直达、1次、2次)的出行方案,并将所得的方案存储于相应的数据库表(如表3、表4所示)中,接着编写储存过程的参数,进而选出最优的出行方案。
表3 直达方案
表4 一次换乘方案
具体步骤如下:⑴创建一个带参数的存储过程,该参数包括初始站和目的站。⑵从表1中分别找出所有经过初始站和目的站的线路集合,命名为line-set-1,line-set-2。⑶将上一步所得的两个集合取交集,得到的集合命名为line-set-3。⑷判断上步所得到的交集中是否为空,如果不是空值,那么存在直达出行方案,进而将该方案存入表3,转到步骤⒀;如果是空值,则转到步骤⑸。⑸分别找出line-set-1和line-set-2所对应的所有站点的集合,依次命名为Transfer-stop-set-1和Transfer-stop-set-2。⑹将上一步得到的两个集合取交集得到的集合命名为Transfer-stop-set-3。⑺判断⑹得到的集合是否为空,如果不是空值,那么则说明通过一次换乘能到达目的站,转而进行步骤⑻;如果是空值,则转到步骤⑽。⑻找出Transfer-stop-set-3集合中所有的1次换乘线路,命名为line-set-4。⑼将集合line-set-1与line-set-4取交集,得到的集合命名为line-set-5,表示第一次乘车的路经集;将集合line-set-2与line-set-4取交集,得到的集合命名为line-set-6,表示第一次换乘的路经集;依据模式“初始站a—首次乘车路径L1—首次换乘站b”以及站a和换乘站b在路径L1中的自然数编号的大小来确定所选择的路径是否是正确的(例如10路(南行)路径正确,则10路(北行)路径错误),由此得到一次换乘中的上一段路径方案,如此类推可以得到下半段换乘方案。⑽分别找出Transfer-stop-set-1和Transfer-stop-set-2所对应的所有线路集合,命名为Transfer-line-1和Transfer-line-2;将所得的两个集合取交集,得到的新集合为第一次换乘线路集合,命名为Transfer-line-one。⑾如果上步最后所得到的集合是空集,则到步骤⒂;如果不是空集,则到步骤⑿。⑿找出Transfer-line-one里边的全部站点集合,命名为temp-transfer-stop,将其分别与Transfer-stop-set-1和Transfer-stop-set-2取交集,得到的集合依次命名为Transfer-stop-11和Transfer-stop-21;分别找出经过Transfer-stop-11和Transfer-stop-21的全部线路集合,依次命名为line-set-10、line-set-12,并将line-set-12与集合line-set-2取交集,得到的集合依次命名为Transfer-line-two,将line-set-10与line-set-1取交集,得到的集合line-set-11,并依照⑼中的方法将得到的外出方案存入transfer-two-time-trip表。⒀建立所有外出方案的外出距离的存储过程,并且都要带有输入和输出参数。⒁依照上步得到的外出距离找到最优的外出路线,则算法结束。⒂如果换乘次数是在3次及以上,则建议选用其他交通工具出行,则算法结束。
实际应用分析
利用上文给出的求解步骤,本文以武汉市的260个公交站点和25条公交线路数据为数据基础,建立数据库以及数据表。比如,出发站为“武汉车站”,目的站为“武汉大学”,需要在SQL查询分析器中输入:find-trip-strategy‘武汉车站’‘武汉大学’,系统立即可得到如下表所示方案。
表5 一次换乘方案
说明,从武汉车站到武汉大学之间没有直达的线路,所以得到了一次换乘方案,由于本研究基于的目标是最少的换乘次数,所以该表输出即为最终换乘结果方案表,接着依据所建立的外出方案距离的存储过程得到所需的最优外出路线。
结 语
该研究为解决庞大公交网络系统下的快速高效选择出行方案提供了可行思路,为人们的出行带来了一定程度的便利。参考文献:
[1]温金辉.用于最短路算法的公交网络模型构建[J].交通标准化,2011(08):35-38.
[2]汪涛,许乐,张继,方志耕.城市公交网络的拓扑结构及其演化模型研究[J].公路交通科技,2009(11):42-45.
[3]王东,刘刚.基于复杂网络的城市公交网络的研究[J].统计研究,2008(11):52.
作者单位:陕西国防工业职业技术学院 陕西西安