基于GIS的最短路径剩余算法研究

基于GIS的最短路径剩余算法研究

邵斌

九江市城市规划市政设计院江西九江332000

摘要：论文针对国内目前OD调查数据处理的方法，提出了更加合理的基于GIS的最短路径剩余法，介绍了算法的计算流程，并给出了实际的算例，提出了以算法为核心的调查数据处理子系统。

关键词：OD调查；公路网；最短路径剩余算法；公路网OD基础数据库

1最短路径剩余算法的提出

公路网总的OD矩阵是通过各个调查点的OD矩阵合成的，而这种合成又不是矩阵中各OD对值的简单相加。不能简单相加的原因主要是：一辆车有可能会在一次出行中在多个调查点被重复调查到，这样不同调查点的OD矩阵中的同一个OD对就会包涵同一辆车的出行信息，如果将各调查点OD矩阵的各OD对值简单相加，就会重复计算这些OD对的车辆数。

对于公路网OD调查来说，特别是对省级以上大型公路网来说，如何处理这些被重复调查到的车辆数信息，保证单点OD矩阵合并后的数据符合实际的出行状况，具有重要意义；也可以说单点OD矩阵合成方法的优劣在很大程度上决定着大型公路网OD总矩阵的精度。

目前，国内对OD调查数据处理的方法主要有两类：一是针对项目级的OD调查数据的处理主要采用直接生成法，即针对调查OD点较少，各个OD点重复易于判断和计算的特点，直接得到区域或通道上的OD；二是针对公路网规划进行的OD调查，采用“串并联”法则处理，所谓串并联处理法就是把道路比作车辆的导体，认为车辆通过道路从甲地驶往乙地，就像电流通过导体从甲地送往乙地一样，当一条道路上有多个OD调查截面时，其统计调查交通量即为各调查点调查数据的平均值（有时也可取其最大值），这又与电流中的串联原理相似，当同一截面上有多条道路时，其截面OD量即为各条道路端面OD量之和，这与电流中的并联原理相同。

当在一个OD对之间的联系道路的所有路段上都布设了调查点的时候，利用出入交通小区道路法和串并联法是可以获得很高精度的OD数据结果的。但是实际的OD调查情形是：一个OD对之间往往会遗漏一些调查点或者是调查点布设得不合理引起复杂的调查点关系判断，也正是这些情形致使每一种合并方法在处理调查点遗漏和调查结果重复计算方面都会有缺陷。

在调查点遗漏和调查点布设不合理的情况下，要得到很高精度的调查结果是不可能的，但是可以用某种方法来估计被遗漏的OD流量以及可能被重复计算的OD流量，这样则可以在一定程度上提高调查结果的精度。最短路径剩余算法就是基于以上考虑提出来的方法。

2.算法的计算流程

本研究提出的“最短路径剩余算法”，根据车辆出行一般选择最短路径（时间或综合费用）的特点，建立基于GIS的路网计算平台，不仅可以消除“串并联”法主观人为判断的缺陷，同时也可以得到各个OD对的调查精度。其具体计算流程图如下图1所示。

图1最短路径剩余算法流程图

3.算例

如图2所示，路网中有4个调查点，每个调查点都能调查到A点和B点之间的OD流量，={N1，N2，N3，N4}，同时记OD（A-B）N1、OD（A-B）N2、OD（A-B）N3和OD（A-B）N4分别为调查点N1、N2、N3和N4的OD（A-B），设OD（A-B）N1＝1000，OD（A-B）N2＝600，OD（A-B）N3＝1000，OD（A-B）N4＝1000。

令K=1，寻找AB间的最短路径，最短路径为：A－S1－S2－S3－S5－B，该最短路径包含了测点N2和测点N4，OD（A-B）最小的是测点N2，其OD量Δ＝600，T（A-B）＝0＋600＝600，OD（A-B）N4＝1000－600＝400，OD（A-B）N2＝0，于是删除路段S5，删除集合中的N2。此时集合还没有空。

令K=2，寻找AB间的最短路径，最短路径为：A－S1－S2－S3－S4－B，该最短路径只包含了测点N4，因此Δ＝400，T（A-B）＝600＋400＝1000，OD（A-B）N4＝400－Δ＝400－400＝0，于是删除路段S3，删除集合中的N4。此时集合还没有空。

令K=3，寻找AB间的最短路径，最短路径为：A－S1－S7－B，该最短路径只包含了测点N1，因此Δ＝1000，T（A-B）＝1000＋1000＝2000，OD（A-B）N1＝1000－Δ＝0，于是删除路段S7，删除集合中的N1。此时集合还没有空。

令K=4，寻找AB间的最短路径，最短路径为：A－S1－S2－S6－B，该最短路径只包含了测点N3，因此Δ＝1000，T（A-B）＝2000＋1000＝3000，OD（A-B）N3＝1000－Δ＝0，于是删除路段S6，删除集合中的N3。此时集合为空，结束运算。

最后得到的A点和B点之间的OD流量T（A-B）为3000。

图2路网流量示意图

图3调查数据处理子系统技术流程图

4.基于GIS的公路网OD基础数据库

从上述计算流程和算例可以看出，OD调查数据的处理过程是非常繁杂的，而且公路网OD调查数据又是非常广泛和巨大的，为了有效的存储和管理这些数据，就必须合理的选择数据库平台，并进行有效的计算，以达到减少数据冗余，又能方便的查询。

采用GIS作为基础平台可以满足以下几个方面的要求：

首先，管理方式简洁。要准确计算公路网络上的出行距离与出行时间，必须要对路网形状、道路交叉口、以及交通小区作正确的描述，同时需要表示根据不同分析目的合并而成的交通大区、某几条高速公路等一系列复杂的交通特性，传统方法需要数量繁多的不同格式的文件进行存放，不便于管理，而借助于GIS，可以使各种数据库采用统一的文件格式进行存放，大大减轻了数据管理的工作量，同时提高了可靠性。

其次，建模效率更高。计算机模型高速调用数据的需求，需要一种新型的数据库管理方式，在GIS基础上抽象出的network特殊数据形式，可以满足建模数据库复杂多样的需要。

第三，实现了数据可视化。模型公式可以与GIS关联，可以将交通模型的输入输出数据在GIS表示出来，不仅专业人员可以看懂，非专业人员也能够对图形结果一目了然。

第四，表现功能丰富。就GIS本身来说，模型公式与地理分区不存在捆绑关系，模型公式相对独立，GIS模块并可以分别应用于不同的地理文件或者图层。除了交通规划，GIS也可用于地理分析等功能。

基于GIS的公路网OD基础数据库系统可以包含很多子系统，例如调查数据处理子系统、OD数据管理子系统以及未来年OD生成子系统，其中的调查数据处理子系统就是以最短路径剩余算法为核心实现OD数据处理功能，特别是解决车辆路径的重复观测问题和补偿解决车辆路径的遗漏观测问题。

5.结语

基于公路网OD调查数据处理的需要，提出了基于GIS的最短路径剩余算法，该算法结合公路网OD基础数据库应用于公路网可以很好的处理调查点的遗漏和重复问题，大大提高调查成果的精度，但也存在一些缺点。希望通过本算法的研究为今后的数据处理方法提供参考。

参考文献：

[1]葛亮，邓卫，蒋大治，王炜.基于低抽样率的公路交OD实用模型研究.公路交通科技，2004年第6期

[2]谭先林.OD调查数据处理过程中消除重复的“串并联”法.公路，1997年第12期

[3]陈超纲，马蕴.关于公路机动车OD调查方法的改进及处理.华东公路，2003年第1期

[4]廖利钊，顾保南.OD调查中的抽样率问题.上海铁道大学学报，1996年第2期

作者简介：

邵斌（1976一），男，江西省都昌县人，九江市城市规划市政设计院工程师，硕士，注册城市规划师，主要研究方向：交通运输与规划。