专利名称：一种关键路径实时动态旅行时间计算的方法
技术领域：
本发明涉及一种关键路径实时动态旅行时间计算的方法，用于个性化的交通信息 服务，属于智能交通实时交通信息服务的技术领域。
背景技术：
交通信息服务是智能交通系统的重要组成部分，同时也是城市信息服务的重要内 容，特别是在城市道路交通需求矛盾突出、交通问题严重和对交通舒适性要求提高的环境 下，道路交通信息服务显得非常重要。多种方式的、个性化的道路交通信息服务，具有非常 迫切的发展需求。旅行时间是衡量一个城市交通运输系统效率的标准之一，也是实时交通信息服务 的重要信息组成部分。城市路网的复杂性、日益增长的交通需求，以及大型、持续性高强度 活动给城市交通带来了更大的挑战，同时也诱发了公众对于旅行时间为代表的实时交通信 息服务的迫切需求。目前，国内在交通信息服务领域的研究和应用还处于刚起步阶段，交通信息服务 模式与服务内容都比较单一，通常是在网站的地图上动态显示主要道路的实时交通路况， 而出行者更关心的旅行时间信息并不能获取。因此向出行者提供路径的实时动态旅行时间 是多样化与个性化交通信息服务的发展方向。

发明内容
本发明的目的是提供一种能够向出行者提供关键路径的旅行时间的方法。其中， 所谓关键路径就是承载城市重要交通流连续有端点的有向路段的集合，它主要针对承担较 大客流的道路脉络作为关键路径。关键路径的起终点一般为重要的交通枢纽、热点区域或 兴趣点，例如上海市的徐家汇至人民广场的关键路径。为了达到上述目的，本发明的技术方案是提供了一种关键路径实时动态旅行时间 计算的方法，其特征在于，步骤为步骤1、挑选关键点关键点是指城市路网中在城市交通运行中的重要节点；步骤2、确定关键点对选取一对关键点对作为城市路网中第k条实际关键路径的 起点与终点，其中，实际关键路径是指城市路网中实际存在的承担较大客流的道路脉络；步骤3、生成备选路径根据路径连通原则和路径有效性原则，生成步骤2中所述 关键点对所能形成的N条路径，该N条路径作为备选路径；步骤4、挑选关键路径从路径道路等级、路径路段数量、路径总长三方面对步骤3 中生成的N条备选路径进行分析评估，挑选出至少一条路径作为第k条实际关键路径，命名 为第k条计算关键路径；步骤5、计算关键路径的旅行时间累加第k条计算关键路径各路段的旅行时间。相对于城市的整个道路网络，关键路径是城市交通的关键命脉，本发明通过关键 路径交通信息的发布，引导出行者合理利用主要道路资源，充分发挥主要道路在城市交通
4中的作用。同时，关键路径的交通信息发布是一种少量优质资源信息的发布，不仅能够满足 多数用户的需求，还能达到最大限度的利用信息资源，从而提供精确度更高的交通信息。本发明的优点是挑选承载城市重要交通流连续有端点的有向路段的集合作为关 键路径，通过关键路径实时旅行时间的动态计算获得更精准的关键路径旅行时间，实现少 量优质资源信息的发布，从而满足多数出行者对个性化交通信息服务的需求。


图1为关键路径实时动态旅行时间计算方法的流程图；图2为关键点挑选步骤的流程图；图3为关键路径挑选步骤的流程图；图4为关键路径实时动态旅行时间计算步骤的流程图。
具体实施例方式以下结合实施例来具体说明本发明。实施例如图1所示，本发明提供了一种关键路径实时动态旅行时间计算的方法，步骤为步骤1、挑选关键点关键点是指城市路网中在城市交通运行中的重要节点。关键 点是关键路径形成的基础。对城市路网进行抽象，剔除城市路网中在城市交通运行中不重 要的节点，形成一个由关键点组成的城市交通抽象路网。如图2所示，关键点的挑选又分为 以下三个步骤步骤1. 1、挑选一级关键点一级关键点指的是城市的重要交通枢纽、热点区域及 重大集散中心。一级关键点包括如机场、火车站等综合交通枢纽点，以及广场、商业区等热 点区域。一级关键点通常吸引了重要的交通客流，交通负荷很大。步骤1. 2、挑选二级关键点二级关键点是由一级关键点衍生的关键点，由一级关 键点辐射到周围重要交通干道(例如城市快速路、城市立交、城市交通走廊等)形成的重要 交通点；步骤1. 3、挑选三级关键点三级关键点是城市路网中的主干道与主干道的交叉 口。这些重要交叉口是运载了大量客流的干道节点。步骤2、确定关键点对选取一对关键点对作为城市路网中第k条实际关键路径的 起点与终点，其中，实际关键路径是指城市路网中实际存在的承担较大客流的道路脉络。一对关键点对就是一条实际关键路径起点与终点形成的点对。关键点对的确定是 生成一条关键路径的前提。选取能够代表用户出行倾向的关键点对，即用户出行需求强烈 的起点与终点。关键点对确定的原则可以是(1) 一级关键点两两形成关键点对；(2)可衍生出二级关键点的一级关键点与衍生的二级关键点之间形成关键点对。步骤3、生成备选路径根据路径连通原则和路径有效性原则，生成步骤2中所述 关键点对所能形成的N条路径，该N条路径作为备选路径；路径连通性原则备选路径最基本的要求是该路径必须是连通的，在备选路径生 成时需要考虑路网的禁行信息与单向道信息。
5
路径有效性原则即生成的路径是由有效的路段组成。该步骤可以分为步骤3. 1、分别获取作为城市路网中第k条实际关键路径的起点及终点的关键点 的地理位置信息；步骤3. 2、将地理位置信息与城市路网基础信息、路网连通性信息、路网禁行信息、 三级关键点信息相结合，搜索出关键路径起点至终点的所有连通路径；步骤3. 3、在所有连通路径中挑选出N条有效路径作为备选路径，每条备选路径由 多条路段组成，根据城市路网路段编码原则为每条路段编号；所谓有效路径是指t (i) < t (j)且s (i) > s (j)，i和j分别为连通路径从起点至 终点的方向任意选取先后两个关键点，t表示从起点至关键点的旅行时间，s表示从关键点 至终点的旅行时间，即关键点i离起点的旅行时间要小于关键点j离起点的旅行时间，而关 键点i离终点的旅行时间要大于关键点j离终点的旅行时间；步骤4、挑选关键路径从路径道路等级、路径路段数量、路径总长三方面对步骤3 中生成的N条备选路径进行分析评估，挑选出至少一条路径作为第k条实际关键路径，命名 为第k条计算关键路径。该步骤遵循以下三个原则高等级道路原则关键路径是城市交通的关键命脉，主要以道路等级高的路段作 为首选对象。路径道路等级就是该原则的评分指标。长路段占多数原则关键路径的地面道路路段尽量长，即连续流路段的长度尽量 长，从而减少关键路径交通流被间断的次数。此外对于快速路路段其长度也尽量长，从而减 少匝道连接点形成的紊流区的影响。路径路段数量就是该原则的评分指标。路径简洁原则关键路径应该保持简洁，避免出现绕路情况，因此关键路径的总长 尽可能短。路径总长就是该原则的评分指标。上述三个评分指标通过加权平均方式获得备选路径的评选总分，将各备选路径的 总分按优到差进行排序，排名第一的备选路径即被挑选为关键路径。如果其他备选路径的 总分与第一位的总分非常接近，计算备选路径的总分与第一位总分的差值占第一位分值的 百分比，如果在5%之内，满足评选总分优秀的条件，这些备选路径也被挑选为关键路径。因 此相同关键点对的关键路径可以不唯一，如图3所示，其具体步骤为步骤4. 1、计算各条备选路径的路径道路等级，第i条备选路径的路径道路等级
权利要求
一种关键路径实时动态旅行时间计算的方法，其特征在于，步骤为步骤1、挑选关键点关键点是指城市路网中在城市交通运行中的重要节点；步骤2、确定关键点对选取一对关键点对作为城市路网中第k条实际关键路径的起点与终点，其中，实际关键路径是指城市路网中实际存在的承担较大客流的道路脉络；步骤3、生成备选路径根据路径连通原则和路径有效性原则，生成步骤2中所述关键点对所能形成的N条路径，该N条路径作为备选路径；步骤4、挑选关键路径从路径道路等级、路径路段数量、路径总长三方面对步骤3中生成的N条备选路径进行分析评估，挑选出至少一条路径作为第k条实际关键路径，命名为第k条计算关键路径；步骤5、计算关键路径的旅行时间累加第k条计算关键路径各路段的旅行时间。
2.如权利要求1所述的一种关键路径实时动态旅行时间计算的方法，其特征在于，所 述步骤1分为步骤1. 1、挑选一级关键点一级关键点指的是城市的重要交通枢纽、热点区域及重大 集散中心；步骤1. 2、挑选二级关键点二级关键点是由一级关键点衍生的关键点，由一级关键点 辐射到周围重要交通干道形成的重要交通点；步骤1. 3、挑选三级关键点三级关键点是城市路网中的主干道与主干道的交叉口。
3.如权利要求1所述的一种关键路径实时动态旅行时间计算的方法，其特征在于，所 述步骤3分为步骤3. 1、分别获取作为城市路网中第k条实际关键路径的起点及终点的关键点的地理位置信息；步骤3. 2、将地理位置信息与城市路网基础信息、路网连通性信息、路网禁行信息、三级 关键点信息相结合，搜索出关键路径起点至终点的所有连通路径；步骤3. 2、在所有连通路径中挑选出N条有效路径作为备选路径，每条备选路径由多条 路段组成，根据城市路网路段编码原则为每条路段编号，所谓有效路径是指t(i) <t(j)且 s (i) > s (j)，i和j分别为连通路径从起点至终点的方向任意选取先后两个关键点，t表示 从起点至关键点的旅行时间，s表示从关键点至终点的旅行时间，即关键点i离起点的旅行 时间要小于关键点j离起点的旅行时间，而关键点i离终点的旅行时间要大于关键点j离 终点的旅行时间；
4.如权利要求1所述的一种关键路径实时动态旅行时间计算的方法，其特征在于，所 述步骤4分为步骤4. 1、计算各条备选路径的路径道路等级，第i条备选路径的路径道路等级η{Link _ Iengthj χ Link _ Classj)Route_ClassRl =^---，其中，LinkJengthj 为第 i 条备选^ Link _ Iengthj >ι路径中第j条路段的路段长度，Link.Class,表示该第j条路段的道路等级，快速路道路等 级为1，城市重要走廊道路等级为2，城市主要干道道路等级为3，城市次要干道道路等级为4，城市支路道路等级为5，η表示第i条备选路径的路段总数；步骤4. 2、计算各条备选路径的路段总数，第i条备选路径的路段总数Link_NumKi = COUNT(Link_ID)，Link_ID为每条路段的编号，COUNT为计数运算；步骤4. 3、计算各备选路径的路径总长，第i条备选路径的路径总长ηRoute _ Lengthm = ^ Link _ Iengthj ；J=I步骤4. 4、计算各备选路径的评选总分，第i条备选路径的评选总分R0ute_N0teKi = aXRoute_ClassEi+bXLink_NumEi+cXRoute_lengthRi,其中，a、b、c 分另lj是 Route_ClassRi、 Link_NumEi 以及 Route_lengthKi 的权重；步骤4. 5、将N条备选路径以评选总分从小到大排列，排在第一位的备选路径作为第k 条实际关键路径，命名为第k条计算关键路径。
5.如权利要求4所述的一种关键路径实时动态旅行时间计算的方法，其特征在于，在 所述步骤4. 5中，计算除排在第一位的备选路径外其他各条备选路径的评选总分与排在第 一位的备选路径的评选总分的差值，计算该差值与排在第一位的备选路径的评选总分的百 分比，如果该百分比在5%以内，则该条备选路径被选为关键路径。
6.如权利要求1所述的一种关键路径实时动态旅行时间计算的方法，其特征在于，在 所述步骤5中，累加各路段在同一时间段的路段旅行时间或者随着路径行进的时间推移， 动态累加各路段所属时间段的路段旅行时间。
全文摘要
本发明提供了一种关键路径实时动态旅行时间计算的方法，其特征在于，步骤为步骤1、挑选关键点；步骤2、确定关键点对；步骤3、生成备选路径根据路径连通原则和路径有效性原则，生成步骤2中所述关键点对所能形成的N条路径，该N条路径作为备选路径；步骤4、挑选关键路径；步骤5、计算关键路径的旅行时间累加第k条计算关键路径各路段的旅行时间。本发明的优点是挑选承载城市重要交通流连续有端点的有向路段的集合作为关键路径，通过关键路径实时旅行时间的动态计算获得更精准的关键路径旅行时间，实现少量优质资源信息的发布，从而满足多数出行者对个性化交通信息服务的需求。
文档编号G01C21/34GK101982735SQ20101029009
公开日2011年3月2日 申请日期2010年9月25日 优先权日2010年9月25日
发明者冉斌, 朱景瑜, 裘炜毅, 邱志军, 陈烨 申请人:上海美慧软件有限公司