一种基于大数据的面向个人的应急引导方法及系统

摘要

本发明涉及一种基于大数据的面向个人的应急引导方法及系统。当应急事件发生时，用户采用客户端发送所在地的GPS和应急救援请求。服务器端搜索事发地点周围一定范围内具有较高运载能力的城市干道和提供相应急救援服务的地点，综合考虑用户前往主干道所需要的时间，用户在主干道上等车的时间以及用户从干道前往应急服务点的时间，选择一条从事发点出发中转某一干道前往目标应急服务提供点的全局最优路径。客户端根据服务端返回的最优路径进行实时跟踪引导。本发明采用大数据统计分析处理技术，能够实时跟踪用户行进情况做动态调整，综合考虑全流程的时间成本做全局优化，对应急情况下的个人提供最大化的帮助。

说明书

技术领域

本发明涉及浮动车辆数据分析，位置相关服务，路径寻优，移动计算等领域，涉及一种 面向个人的应急情况下的自救引导方法及系统。在应急事件发生时，能根据用户选择的应急 救援场景，基于海量浮动车辆数据构建的道路运载能力模型为用户选择最优应急救援干道， 结合移动设备跟踪到的用户实时位置信息，对用户行进路径做最优指引，利用简洁的文字提 示和语音辅助帮助用户尽快到达指定地点，获得救援服务。

背景技术

随着现代经济社会的发展，应急安全越来越受到人们的重视。这类事件具有突发性和急 迫性，而且往往危害巨大。应急安全领域，长期以来都受到国家以及相关研究者们的高度关 注，在这一领域也产出了不少的研究成果。已有的应急安全研究，主要研究群体性的，公共 安全事件上面。如面临火灾、地震等公共安全事件时的逃生、疏散的研究，涉及建筑设计、 城市规划、资源调度、人的行为模式、心理模式等诸多方面。

实际上，在日常生活当中，个人也会遇到一些应急事件，有时候会需要一些应急救援服 务。比如个人感觉身体不适，需要尽快前往医院得到救治；再比如在路上遇到有人受伤，需 要尽快获得医疗服务。目前尚没有针对个人的应急类、安全类服务或者研究。但是在应急情 况下，如果能够对个人进行有效的引导，帮助他们尽快获得需要的应急救援服务，对个人而 言也是非常有价值的。

以个人需要紧急医疗服务举例，这个时候可能需要能够尽快获取到有效的交通手段，前 往医院。但是用户在当前位置，可能附近有若干条城市干道，但是究竟应该去哪里打车，用 户实际上是不清楚的。人们对于道路情况的感知总是经验性的、模糊的，尤其交通状况还是 动态变化的，因而在应急情况下，人很难做出科学的决策。本发明所设计的个人应急引导服 务，就是致力于满足个人的这种需要。

发明内容

针对公共安全类的应急自救的需求，本发明提出了一种面向个人的应急自救引导服务的 实现方法，能够面向城市路网系统进行实时感知的用户应急自救引导，支持移动终端的快速 请求响应服务。

为实现上述目的，本发明采用的技术方案如下：

一种基于大数据的面向个人的应急引导方法，其步骤包括：

1）用户在遭遇应急事件时通过客户端向服务器发送应急救援请求，并通过客户端的GPS 定位服务将用户所在地（记为p）的GPS坐标发送至服务器；

2）服务器以用户所在地的GPS坐标点为圆心，搜索一定半径r内符合条件的干道和半 径R内符合条件的应急服务提供点，其中：半径r和R（R>r）允许在一个设定的区间内动态 浮动，以确保尽可能地搜索到干道和应急服务提供点；干道指的是拥有较高属性等级和较强 运载能力的城市道路；应急服务提供点指的是公共服务设施（主要为医院、公安局、加油站 等）；

3）对于搜索到的每一条干道MRoad=<E,V>，搜索从事发点p步行到MRoad的最短路径， 其中：E是构成主干道的路段（edge）集合；V是构成主干道的路段的端点集合；p到MRoad 的最短路径指的是P到端点集合V中所有端点的连通路段中路程最短的一条路径；对于每个 应急服务提供点，搜索从每条MRoad上的步行到达点打车前往应急服务提供点的最短路径；

4）计算每个应急服务提供点对于p的到达成本Cost_p(spot),然后选择到达成本最小的应 急服务提供点推荐给用户，返回到达该应急服务提供点的最佳路径到客户端；所述到达成本 包含t₁、t₂、t₃，其中：t₁是用户沿规划的最短路径步行前往干道所需要的时间；t₂是用户在干 道上等车所用的时间；t₃是用户沿规划的最短路径从干道乘车前往应急服务点所需要的时间；

5）客户端接收服务器返回的疏散路径，根据该疏散路径通过文字和语言指引的方式持续 引导用户到达应急服务提供点。

一种采用上述方法的基于大数据的面向个人的应急引导系统，其包括：

客户端，用于向服务器发送应急救援请求，并通过GPS定位服务将用户所在地的GPS坐 标发送至服务器，并接收服务器返回的疏散路径进行实时引导；

服务器，与客户端建立通信连接，用于响应应急救援请求，计算最佳的疏散路径并发送至 客户端，包括：

干道和应急服务提供点搜索模块，用于以用户所在地的GPS坐标点为圆心，搜索一定半 径r内符合条件的干道和半径R内符合条件的应急服务提供点，其中：半径r和R允许在一 个设定的区间内动态浮动，以确保尽可能地搜索到干道和应急服务提供点；干道指的是拥有 较高属性等级和较强运载能力的城市道路；应急服务提供点指的是公共服务设施；

最短路径搜索模块，连接干道和应急服务提供点搜索模块，用于对于搜索到的每一条干道 MRoad=<E,V>，搜索从事发点p步行到MRoad的最短路径，其中：E是构成主干道的路段 （edge）集合；V是构成主干道的路段的端点集合；p到MRoad的最短路径指的是P到端点 集合V中所有端点的连通路段中路程最短的一条路径；对于每个应急服务提供点，搜索从每 条MRoad上的步行到达点打车前往应急服务提供点的最短路径；

到达成本计算模块，连接最短路径搜索模块，用于计算每个应急服务提供点对于p的到达 成本Cost_p(spot),然后选择到达成本最小的应急服务提供点推荐给用户，返回到达该应急服务 提供点的最佳路径到客户端；所述到达成本包含t₁、t₂、t₃，其中：t₁是用户沿规划的最短路 径步行前往干道所需要的时间；t₂是用户在干道上等车所用的时间；t₃是用户沿规划的最短路 径从干道乘车前往应急服务点所需要的时间；

最佳路径返回模块，连接到达成本计算模块，用于根据到达成本计算结果，选择到达成本 最小的应急服务提供点推荐给用户，并返回到达该应急服务提供点的最佳路径到客户端。

下面分4个部分具体阐述本发明的主要内容：

1.基于载客车辆的历史运营记录，对交通道路网络建立道路运载能力的统计模型 CCM-RNS

交通道路网络数据就是一个电子地图，可以通过GIS地图进行数据转换处理得到，它包含 交通网络中的每条道路信息和道路之间连接的节点信息。道路的信息包括路段的标识、路段 的种类、路段的宽度、路段的长度、路段的等级、起始节点的标识、结束节点的标识，节点 的信息包括节点的标识、经度值、纬度值。

首先我们通过浮动车辆的历史运营记录，获取整个路网范围的客运流量记录的原始记录。 原始记录数据包括车辆标识、触发事件、运营状态、记录时间、经度值、纬度值、瞬时速度、 行驶方向等数据项。

道路运载能力和该路段上的车流量有着很强的关联关系，特别是和空载流量的趋势有着直 接关系。参照市民的出行和作息规律，本发明以周为基础对原始数据集进行加工，并考察了 两个维度一种是分为工作日和休息日两种，另一种是分为周一至周日七个类型。

首先给出一些描述性定义。定义一天时间为T，将一天的时间分为n个等分，作为基于时 序统计数据的n个单元t_i，那么T={t₁,t₂,t₃,…,t_n}。定义整个路段为E，整个路网可由m个定 向的路段edge_j连接组成，那么E={edge₁,edge₂,edge₃,…,edge_m}；定义节点为V，每一个路 段edge_j都有两个端点(节点)，用V_s(edge_j)和V_e(edge_j)表示路段edge_j的入度和出度端点,每一 个端点就是一个地理坐标v_i，地理坐标包含经度和纬度两个属性，我们分别用lng和lat来表 示，那么v_i=(lng_j,lat_k)；定义一个路段edge_j内包含u个分段记录seg_k串联而成,那么edge_j={seg₁, seg₂,seg₃,…,seg_u}。针对不同日期类型d_x、不同的时间点t_i、不同的路段edge_j以及路段edge_j上的分段seg_k生成一个经验运载流量记录，记为eflow(d_x,edge_j,t_i,seg_k)。

在此基础之上，针对具体的路段edge_j以及路段内的分段seg_k和一定时间范围的空载流量 记录，建立了运载通量计算表达式，记为表明某个具体的地点具体 时间范围内的运载通量大小。

在上述操作定义的基础上，下面我们具体给出运载能力统计计算步骤。

(1)按车辆归并记录并过滤无效记录

原始GPS记录并没有按照车辆标识独立记录，并且记录时间顺序不完全一致，需要重新 排列。另外需要过滤一些无效的GPS记录，如GPS记录状态不正确、记录超时或记录间距 过大等情形。

(2)车辆行程记录与路网匹配，建立车辆行程轨迹

车辆行程记录有一组GPS记录组成，通过GPS记录的经纬度查找候选道路，使用 MapMatching算法和A-Star算法计算出与这一组GPS记录最佳匹配的车辆行程轨迹 Ry={edge₀,edge₁,edge₂,…,edge_z}。由于GPS记录有疏有密，同一个道路上可以有多个GPS记 录对应，而某个中间道路这可能没有GPS记录对应。在具体计算的过程不仅使用了 MapMatching算法进行道路匹配，还是用A-Star算法进行行程轨迹的补齐。如果出现无法匹 配的一组GPS记录片段，则视为需要过滤的无效GPS记录。

(3)车辆行程轨迹分片筛选，区分不同运营状态的轨迹片段

每辆车在运营的过程中存在不同的运营状态，主要包括载客、空载、驻车和停运四种状态。 车辆行程轨迹分片筛选就是根据不同的运营状态切分标记，便于后续统计分析。

(4)按天统计车流量

针对各个道路对每一天的不同车辆的行程记录进行合并，计算出各个道路一天内各个时间 点片段内的车流量。车流量统计主要包括空载流量值和行车(包括载客和空载两种状态)流量 值。

根据GPS记录中的瞬时车速累计平均，计算出各个道路一天内各个时间点片段内的平均 瞬时速度。本发明还根据各个车辆行程轨迹分片的路程长度合并计算出各个道路一天内各个 时间点片段内的平均车速。

(5)按是非工作日统计车流量

在按天统计车流量的基础上进一步统计合并，区分是非工作日两种日期类型，合并计算上 一步骤得出的统计值，作为道路运载能力计算的基础。

(6)按周一至周日七天统计车流量差异

本发明不仅考察了是非工作日车流量统计的情形，也考察了一周七天各自车流量的统计 值，并与上一步骤统计结果比对，得出周一至周日与是非工作日统计结果值之间的差值。作 为不同日期类型的进一步的细化调节因子。

(7)为统计数据建立文件索引

为了离线计算结果可以重复使用，需要将统计分析结果存储成数据文件。同时为了快速查 找数据和最终运载能力值评估计算，实现了一种便捷高效的文件索引。

每个统计单元的数据量很小，如果独立存储将会生成大量零碎文件，影响文件系统的性能。 本发明允许数据文件合并存储，同时可以分段存储，具体的分段存储数据量大小可以调整。 在分段存储数据文件的基础上，建立一个文件索引数据文档，记录各个道路标识和不同日期 类型下的统计结果信息存储在某个具体的分段数据文件中的某一个起始偏移量值某一个偏移 量结束。每一个索引单元对应的统计数据，包括了具体一个道路和具体日期类型下的一天内 所有时间点片段单元的统计记录。

(8)预备运载能力计算方法实现

在获取目标路段和一个具体的日期时间的情况下，读取相关的统计数据，使用线性平滑方 式，以当天的时序作为坐标轴建立载客运载能力平滑曲线，纵坐标为与流量相关的载客能力 统计值，一段时间内的运载能力的计算即相当于对运载能力平滑曲线的积分计算。

2.适用于应急自救的候选干道和应急服务提供点快速确定方法GB-ESS

该方法的实现主要包含2个步骤：1）借助栅格化索引EO-Grid选取事发点周围指定半径 覆盖到的所有路段edge和应急服务提供点；2）使用PEBMR-Recovery算法从候选的edge集 合中识别和恢复出干道。下面对各个步骤的实现机制进行说明。

2.1基于EO-Grid的疏散路段候选集选择

本发明中我们对的路网构建了栅格化索引。下面给出栅格化索引的定义。

定义1(针对路段edge和应急点的栅格化索引EO-Grid)：针对路段edge和应急服务提供点 的栅格化索引可以定义为EO-Grid=<LT,RB,Set<cell>,hn,vn>，其中LT,RB为索引的路网范 围，LT为路网矩形左上角的GPS坐标，RB为路网矩形右下角的GPS坐标，Set<cell>为索引 后的cell集合，hn为横向（东西向）划分的cell数目，vn为纵向（南北向）划分的cell数目。 索引对路网的划分如图1(a)所示。

定义2(索引栅格cell)：一个EO-Grid被切分成hn×vn个cell，一个cell可以定义为cell=<LT, RB,ID,Set<edge>>，其中LT,RB分别为cell的左上角和右下角GPS坐标，ID为cell的编号， Set<edge>为落在该cell下的edge集合。cell的表示如图1(b)所示。

给定一个GPS点，栅格化索引为其快速返回以其为圆心指定半径范围内的edge候选集和 应急服务提供点候选集。下面将重点介绍如何确定落入指定范围内的cells,然后再确定edge 候选集合和应急服务提供点候选集合。

定义3(应急服务提供点spot)：一个应急服务提供点可以定义为spot=<ID,type,GPS, edge>，其中ID为spot的编号，type为应急服务提供点的类型（如医院、警察局、加油站等）， GPS为spot所在的GPS坐标，edge为spot所在的路段。

落入搜索范围的cells的确定过程：

1.给定事发点GPS坐标P(lat,lng)，其中lat为纬度，lng为经度。基于EO-Grid索引， 在使用Hash存储索引的情况下，可以在O(1)时间复杂度内定位坐标点所在的cell，记为X。

2.给定干道的搜索半径r和应急服务提供点的搜索半径R（R>r），确定X周围被半径r 和R扫过的所有cell。我们使用公式(1)来计算每个cell到P的最短距离D_min(p,cell)：

其中dis(GPS1,GPS2)用于计算两个GPS点之间的欧式距离。我们将那些D_min<r和D_min<R 的cell分别作为确定干道和应急服务提供点的候选cell集合，而注册在这些cell上的edge即 为用于候选路段、应急服务提供点即为候选应急服务提供点。Cell的选择以及候选edge、应 急服务提供点的确定如图2所示。以事发地点为中心，半径r范围内，我们找到了4条候选 路段，分别为主干道2上的{edge3}和主干道1上的{edge4,edge8,edge9}。以事发点为中心， 半径R范围内，我们找到了2个应急目的地（假设我们的应用场景以医院为应急目的地）， 分别是spot1和spot2。

2.2基于候选路段集合的主干道识别恢复方法PEBMR-Recovery

上一步获取的候选路段（edge）集合并非主干道。城市主干道是由若干一定级别的路段连 接构成的。在实际引导过程中，本发明将引导用户到达某条城市主干道上任意一个相对于当 前事发点来说最近的位置即可。为此提出了主干道识别恢复方法（Partly-Edge-Based Main  Road Recovery，简称PEBMR-Recovery），将候选的主干道从候选路段集合中识别出来。

定义4(基于路段edge的沿拓)：给定一条路段edge，记为EX，从该路段出发，在首尾两 个方向上查找符合约束条件的相连edge依次延展，直至找不到满足约束条件的相连edge为 止，延展结束。路段延展的目的即为了恢复初始edge EX所在的主干道。

定义5(主干道MRoad)：一条主干道可以定义为MRoad=<E,V>,其中E为构成主干道的 edge集合，V为连接路段的节点vertice集合（实际路网中一般为路口）。edge和vertice的排 列顺序遵循主干道的行进方向。

定义6(路段edge筛选条件)：路段的级别决定了其表示的道路的级别，我们关注应急能 力较强的城市主干道。根据路网数据中给出的详细路段属性，我们可以筛选出满足级别条件 的候选路段。

定义7(路段edge偏角θ)：基于同一主干道上的相邻路段edge近似连接成一条直线的假设， edge偏角θ定义相邻edge同方向上的偏转角度。如果θ<5°，则认为相邻两个edge是同一主 干道上的edge，可以继续向下沿拓。

候选主干道的发现和恢复过程：

1.给定路段候选集合，筛选出符合条件的路段;

2.给定一个路段，注册一条主干道MRoad，记为MR。从该路段开始，向首尾两个方向 拓展，直到找不到满足θ的新路段为止。将遍历过的路段注册到MR。

3.对每一条候选路段重复1.-2.操作，同一主干道上的路段不重复操作，最终得到候选主 干道集合。

如图3所示，使用PEBMR-Recovery算法，我们从候选edge集合{edge₃,edge₄,edge₈,edge₉} 中识别出了{干道1，干道2}。干道1可以表示为<E={edge₂,edge₄,edge₈,edge₉},V={v₁,v₃,v₆, v₇,v₈}>，干道2可以表示为<E={edge₁,edge₃,edge₄},V={v₂,v₃,v₄,v₅}>。

3.最佳应急服务提供点的选择方法

针对最佳应急服务提供点的快速选择，提出了基于最短路径和干道运载能力的应急服务提 供点到达成本模型（Reaching Cost Model,简称RCM）。到达成本考虑3方面因素：1）从事 发点步行前往干道所需要的时间t₁；2）在干道上等车的时间t₂；3）从干道打车前往应急服 务提供点所需要的时间t₃。为此，针对1）基于Dijkstra的由事发点至候选干道（由点及线） 的无向最短路径寻路算法（Vertex-to-Edge-Oriented Shortest Path Searching，简称V2E-SPS算 法）；针对2）利用道路运载能力统计模型CCM-RNS计算主干道上用户所在位置处的最长等 车时间；3）利用Dijkstra算法搜索出干道到应急服务提供点的最短路径。下面分两部分进行 阐述：首先介绍最短寻路算法V2E-SPS，然后给出针对应急服务提供点的到达成本模型，阐 述模型是如何利用最短路径和主干道运载能力来计算应急服务提供点的到达成本的。

3.1基于Dijkstra的（由点及线）无向最短路径寻路方法V2E-SPS

该方法利用路网数据，搜索出事发地点到达一条干道的最短路径。每条干道MRoad由一 个路段集合MRoad.E和一个端点集合MRoad.V组成。我们定义“到达主干道”为从事发点出 发，找一条连通路径到达MRoad.V中的任何一个端点。事发地点是由用户客户端GPS设备 提交的GPS坐标，并不对应路网数据上的端点。为了基于路网进行最短路径搜索，我们将事 发点的GPS坐标映射到路网上相应路段（如图2所示，事发点坐标映射到路段edge₁₁上）。

给定主干道MRoad和事发点GPS坐标p，从事发点到一条主干道的最短寻路过程可表示 如下：

1.利用路网匹配技术将p映射到路网上相应的路段e；

2.对于路段e上的首位节点vs和se，利用Dijkstra算法分别计算两点到主干道上所有节 点的最短路径，得到两个最短路径集合，记为{traj_s1,traj_s2,…,traj_sn},{traj_e1,traj_e2,…,traj_en}， 其中n为干道上的端点数；

3.选择两个集合中路径最短的路径作为从事发点p到干道MRoad的最佳路径，记为 traj_MR。

由于服务是面向处于应急救援状态下的个人，其到达干道的方式一般为步行，因此不需要 考虑路段的方向。V2E-SPS执行的是一个无向图上的最短路径搜索过程。为了提高后台服务 的相应效率，我们利用Dijkstra算法的特性对寻路过程进行简化。Dijkstra在寻路过程中能够 确定所有经过节点最短路径，利用这一点，当我们在寻找事发点p到干道上某个节点v_m的最 短路径时，如果寻路过程中恰好经过了主干道上的另一个节点v_k,则寻路算法立即结束。因 为到达节点v_k即已经满足了“到达主干道”的定义。

如图所3所示，使用V2E-SPS算法，我们可以找到从事发点撤离到主干道1和主干道2 的最短路径分别是traj_1min={edge₁₁,edge₁₂,edge₇}和traj_2min={edge₁₁,edge₁₂,edge₁₆,edge₅}。

3.2适用于个人自救的应急点到达成本模型RCM

一个应急服务提供点的到达成本用用户从事发点步行前往干道并从干道打车到达应急服 务提供点消耗的总时间来表征，记为T(spot)。T(spot)包含3部分时间：1）引导用户步行通过 最短路径到达干道的时间，记为t₁；2）用户在干道上打到车所需要的等待时间，记为t₂；3） 用户坐车前往应急点所需要的时间t₃。

在得到用户步行到达干道的最短路径后，可以得到路径的长度，记为L₁。根据经验，我 们假设人的平均步行速度为s，则用户步行通过最短路径到达干道所消耗的时长:

$t_1=\frac{L_1}{s}---\left(2\right)$

到达干道后等到空车的最长等待时间跟两个因素有关：a）用户所在的seg上的运载能力， 记为C(Δt)；b）用户所在的seg上的应急请求数（即与当前用户在同一地点等待空车的人数）， 记为N。C(Δt)表示当用户到达主干道的那个时间点t_q开始向后的Δt时间内，用户所在的seg 上的运载能力（用空载出租车流量来表征），根据CCM-RNS模型，C(Δt)可表示为：

$C\left(\mathrm{\Delta t}\right)={\int }_{t_q}^{t_q+\mathrm{\Delta t}}\mathrm{eflow}(d_x,{\mathrm{edge}}_j,t,{\mathrm{seg}}_k)={\mathrm{EF}}_{(d_x,{\mathrm{edge}}_j,{\mathrm{seg}}_k)}(t_q,t_{q+\mathrm{\Delta t}})---\left(3\right)$

已知当前seg上的应急需求是N，加上当前用户的需求计数值就是N+1，在同一个路段为N+1 个用户提供运载服务，则需要较多的运载时间和运载能力，。参考先来先救援的规则进行救援 指引，当前用户需要排队等待第N+1车次，预计得到成功救援。假设当前用户需要等待的时 间为t₂，则t₂满足：

C(t₂)=N+1+ζ(4)

其中ζ为松弛因子，该值默认可为0。在实际使用中，该变量的取值动态可配置，可根据历 史失效请求记录的经验比例值α，计算得出松弛因子ζ=-α(N+1)。

利用等式（4）求出用户在主干道上的等待时间t₂。

利用Dijkstra算法我们搜索出用户在干道上的位置点到应急服务提供点的最短路径，这条 路径上的行驶时间取决于浮动车在各个路段上的行驶速度，假设最短路径为 各个路段的长度依次为根据海量浮动车历史数据 得到各路段上的平均行驶速度为则：

$t_3=\underset{i=1}{\overset{n}{\Sigma }}\frac{l_{\mathrm{ki}}}{s_{\mathrm{ki}}},$

综合t₁、t₂和t₃，应急服务提供点对于事发点p的到达成本表示为：

Cost_p(spot)=T(spot)=t₁+t₂+t₃(5)

(5)式即为应急服务提供点的到达成本模型（Reaching Cost Model,简称RCM）。

当拿到候选的干道集合和应急服务提供点集合后，本发明使用RCM评估用户中转各条主 干道到达各个应急点的成本，选择到达成本最小的应急服务提供点和相应的引导路径返回给 用户。

关于N值的确定。我们为每条干道上的每个seg设置一个计数器，当客户端提交事发点坐 标到服务端，服务端计算确定最优引导路径所对应的干道的某个seg并且开始引导时，将当 前用户注册到该干道的指定seg，计数器即+1。当用户到达干道时，取消该用户的注册，计数 器-1。

4.客户端根据服务端返回最优引导路径进行用户自救指引，并持续跟踪用户GPS位置与 设定路线是否一致，发生不一致时提交更新指引任务

首先在每个需要自救指引的移动对象上安装GPS定位设备和无线通讯设备，并配备应急 自救指引客户端程序,可称为“Help me”应急引导程序。客户端程序内置与服务器通过交通 道路路网数据，在客户端系统中可以准确地计算出各个路段长度与各个路段间的方向性。

对于预计方向判定识别主要通过向量旋转角度计算得出。首先基于两个邻接路段的最近路 段内的分段seg，获得两个向量记为和向量方向与靠右行驶方向一致，计算向量积与余 弦夹角。当向量积为正数时，顺时针方向旋转角度为θ，即右转弯。当向量积为负数时，逆 时针方向旋转角度为，即左转弯。当计算出的向量积为0且余弦夹角为0度时，可能是向前 直行也可能是逆向行驶，因此特殊情形还需要检查向量符号一致与否。

用户通过移动对象发起应急自救服务请求后，服务端将会返回最优引导路线，可以用 Ry={edge₀,edge₁,edge₂,…,edge_z}来表示，客户端系统将依次返回一系列的快速指引，诸如“向 左100米”，“靠右侧转弯”，“前方200米处等待”。客户端系统需要持续跟踪用户GPS位置， 适时的更新指引消息并进行语音播报，还需验证移动方向和行经路线与预期设定路线是否一 致，如果发现不一致情形，则需要向服务器发起更新指引任务请求，再次获取服务端响应并 更新本地引导指令。

首先给出一些描述性定义。根据客户端持续跟踪用户GPS位置变化，考虑两个相邻近的 某两个位置坐标，记为ν_uk和ν_uk+1，记为行经轨迹的标志向量。根据两点坐标位置的 中间点查找最相近路段的分段seg_k，seg_k的两端坐标分别为ν_k和ν_k+1，记为引导 向量。

具体判断用户行进路线偏离预定轨迹的方法：

1）计算与seg_k间垂直距离为d_uk，d_uk满足小于最大允许偏差d_max，超出就为偏离预 定的指引路线。

2）计算与指引路线的邻近的主要节点V_i的距离是否小于d'_min，如果小于视为不偏离 预定轨迹的估计，如果大于进行下一步计算。

3）计算行经轨迹的标志向量相对于引导向量的旋转角度θ，如果|θ|大于给定的阈值λ， 则判定用户偏离了预定的轨迹。θ值的计算方法参照如下

$\theta =\mathrm{sgn}(\overrightarrow{v_{\mathrm{uk}}{v}_{\mathrm{uk}+1}}\times \overrightarrow{v_k{v}_{k+1}})\arccos (\overrightarrow{v_{\mathrm{uk}}{v}_{\mathrm{uk}+1}}·\overrightarrow{v_k{v}_{k+1}})/\left(\right|\overrightarrow{v_{\mathrm{uk}}{v}_{\mathrm{uk}+1}}\left|\right|\overrightarrow{v_k{v}_{k+1}}\left|\right),$θ为正 数表示顺时针方向旋转角度为|θ|，θ为负数表示逆时针方向旋转角度为|θ|。当θ为0的特殊情 形，有为负数时，实际θ为顺时针方向旋转180度。

本发明设计的是基于海量的浮动车辆数据构建道路运载能力模型，可以结合用户当前的 位置、提交请求的时间以及周围的环境因素，对用户给出精准的推荐以及傻瓜式的引导，极 大的减轻了用户在紧急情况下的决策负担，同时降低了用户获得救援运输服务的不确定性。

本发明提供的服务区别于打车推荐系统，打车推荐系统只关注打车地点的推荐，而不关 注用户如何前往这些打车地点。它们只是根据用户当前的位置，为用户推荐附近打到车概率 最高或者等车时间最短的地点。本发明设计的系统，不仅结合打到车的概率以及等车时间对 候选的应急救援干道做筛选和推荐，更是综合考虑了用户从当前位置到达打车位置的行走时 间，用户在打车位置的等待时间以及用户打到车以后到达指定类别的应急服务提供点的行驶 时间，对整个用户获得应急服务的过程做全流程的最佳规划。同时在用户前往应急救援干道 的行进过程中，根据用户移动设备上传的用户位置进行实时跟踪，如果发现用户偏离预设路 径，会自动重新计算和筛选应急救援干道，并计算最优路径，直到用户到达最优应急救援干 道。另外，当本系统提供的应急服务被规模化使用以后，所有订阅服务的用户还可以收到附 近其他用户的应急救援请求，从而从概率上进一步帮助需要救援的用户尽早的获得相应的服 务或者救援。从这个意义上讲，出租车打车推荐系统是不能完全满足个人在应急场景下的救 援需求的。

通过以上分析可以看出，本发明填补了应急领域只关注公共安全事件，而对个人应急安 全关注不够的一项空白，对紧急环境下的个人做实时的救援引导，帮助他们尽快的获得相应 的运输服务。同时，区别于打车推荐系统，本发明会实时跟踪用户行进情况做动态调整，综 合考虑全流程的时间成本做全局优化，达到整体的最优效果，对应急情况下的个人提供最大 化的帮助。

附图说明

图1a是对路网进行栅格化划分的示意图，图1b是Grid索引中cell结构的示意图。

图2是确定事发点周围指定半径范围内的候选edge集合和候选应急服务提供点集合的示 意图。

图3是从候选edge集合中恢复出干道集合，并确定事发点到每条主干道的最短路径以及中 转各条干道到达相应最近应急服务提供点的路线的示意图。

图4是确定到达成本最小的应急服务提供点的示意图。

图5是本发明的应急引导流程图。

具体实施方式

下面通过具体实施例和附图，对本发明做进一步说明。

本发明面向城市路网系统进行实时感知的用户应急自救引导，支持移动终端的快速请求 响应服务，所采用的应急引导流程如图5所示，对其主要内容说明如下：

(1)基于浮动车辆的历史运营记录，对交通道路网络建立道路运载能力的统计模型 (Carrying Capacity Model Of Road Network System,简称CCM-RNS)。首先我们通过浮动车辆的 历史运营记录，获取整个路网范围的客运流量的原始记录。然后结合交通道路网络数据对运 营记录进行加工处理，并进一步统计载客运营能力，进而对交通道路网络建立道路运载能力 的经验模型。

(2)根据应急自救请求的时间地点查找临近的干道以及应急服务提供点（在本发明中，应 急服务提供点指的是医院、警察局、加油站等提供公共应急服务的设施，根据应用场景的不 同选择不同的目的地）。为了快速确定事发点周围可能的干道和应急目的地，提出了基于栅格 化索引的路段及应急服务提供点快速筛选算法（Grid-based Evacuation Spots Selection,简称 GB-ESS算法）。栅格化索引能够有效地对路段和应急服务提供点进行划分和定位，快速确定 事发点周围的道路和应急服务提供点。在确定事发点的位置之后，以事发点为中心一定半径 范围覆盖的所有栅格所包含的路段作为预选的路段，而包含的应急点作为候选的应急服务提 供点。每条主干道都由若干的路段首尾连接而成，为此我们基于路网模型和路段属性，提出 了基于预选路段集合的主干道识别恢复（Partly-Edge-Based Main Road Recovery，简称 PEBMR-Recovery）算法。

(3)计算事发点至各个候选应急服务提供点的最优引导路径，并计算相应的到达成本。选 择到达成本最小的应急服务提供点以及到达该目的地的最优路径返回给用户。到达成本包括 三部分时间：用户从事发点前往干道的时间t₁,用户在干道上等车的时间t₂,用户坐车前往应 急服务提供点的时间t₃。针对到达成本最小的应急服务提供点的快速选择，提出了基于最短 路径与干道运载能力的到达成本模型（Reaching Cost Model,简称RCM）。应急服务提供点的 选择需要考虑3方面的因素：1）从事发点到干道的距离要尽可能的短，即要能尽快的跑到干 道；2）干道的应急能力要尽可能的强，即要尽可能的容易打到车；3）从干道到应急目的地 的路程要尽可能的短。针对1）我们设计了基于Dijkstra的由事发点至候选干道（由点及线） 的无向最短路径算法（Vertex-to-Edge-Oriented Shortest Path Searching，简称V2E-SPS算法）。 针对2）我们利用CCM-RNS对干道的运载能力进行度量。针对3）我们利用Dijkstra算法搜 索从干道到候选应急服务提供点的最短路径。

(4)客户端根据服务端返回最优引导路径进行用户引导，并持续跟踪用户GPS位置与设定 路线是否一致，发生不一致时提交，更新疏散指引请求。

下面通过实际应急自救场景的举例来进一步说明本发明在具体应急场景下如何交互和发 挥作用，但不以任何方式限制本发明的范围。

如图2示，用户在火焰标示的位置遇到紧急情况，需要应急引导服务。用户拿出手持移 动设备，打开HelpMe客户端程序，选择主界面上相应的应急引导服务，比如医疗救援服务。 HelpMe程序自动启动手持设备上的GPS设备，开始对用户定位，并将定位结果以及用户选 择的应急服务类型上传至HelpMe服务端，附带请求引导标识。HelpMe服务端收到用户上传 的带有请求引导标识的GPS位置以后，以用户位置为中心，半径r搜索用户附近的满足空闲 运载能力条件的路段，同时以半径R搜索候选应急服务提供点，经过筛选，发现符合条件的 路段{edge₃,edge₄,edge₈,edge₉}，以及符合条件的服务提供地点{spot1,spot2}。

在确定了候选的路段后，系统将这些路段还原成完整的主干道。如图3所示，候选路段 被恢复成了{干道1，干道2}。这两条干道即为用户可能的获取到救援运输服务的地点。干道 1可以表示为<E={edge₂,edge₄,edge₈,edge₉},V={v₁,v₃,v₆,v₇,v₈}>，干道2可以表示为 <E={edge₁,edge₃,edge₄},V={v₂,v₃,v₄,v₅}>。下一步需要确定事发点到达两条主干道的最短路 径，作为评估到达两条主干道时间成本的重要依据。如图3所示，系统经过搜素发现从事发 点到两条主干道的最短路径分别是traj_1min={edge₁₁,edge₁₂,edge₇}和traj_2min={edge₁₁,edge₁₂, edge₁₆,edge₅}。

有了最短路径，系统就能获得用户前往候选主干道的最短路程，然后根据路程就可以计 算用户从当前位置到达候选干道的行走时间，记为t₁。此外，系统使用基于海量交通数据建 立的道路运载能力模型计算候选主干道的运载能力，根据运载能力，便可以计算出用户到达 指定干道以后的预计等待时间，也即用户多久以后可以打到车，这段时间记为t₂。接下来， 系统会再为每个候选主干道搜索到达最优应急服务提供点的最短路径，并根据海量浮动车的 历史数据计算每个候选主干道抵达其最优应急服务提供点的行驶时间，记为t₃。综合考虑这 三种因素，用户获得应急救援服务的综合成本为T=t₁+t₂+t₃，系统对T进行排序，为用户 选择最优的应急服务提供点，然后将用户从当前位置，到达最优应急服务提供点的路径返回 给客户端。如图4所示，最终的计算结果显示spot2的总体成本最低，因此路径traj_1min={edge₁₁, edge₁₂,edge₁₆,edge₅,edge₄}作为最优引导路径返回给用户。HelpMe服务端返回给客户端的信 息包括引导目的地的GPS位置，名称，以及引导路径上所有途径的路口关键点的GPS位置。

HelpMe客户端收到服务端返回的引导目的地的GPS位置、名称和关键点GPS序列以后， 启动本地的导航模块，根据关键点GPS序列的顺序，开始对用户进行实时引导。首先，引导 程序先告知用户引导目的地的名称。紧接着开始对用户的行进行为做实时引导，引导包含文 字和语音两方面，即屏幕上显示下一步的行为，并用语音模块播出。如“请向前方300米，并 在路口右拐”。在用户行进过程中，每远离一个路径关键点时，引导模块便对用户的行进方向 做判断。如果用户未按照预设的引导路径行进，则HelpMe客户端将用户最新的GPS位置上 传至服务端，同样附带请求引导标识，再次触发服务端的筛选和计算过程。如果用户一直按 照预设的引导路径行进，最终将到达指定的引导目的地。此时，HelpMe客户端再次上传用户 的GPS位置，并附带引导结束标识。

HelpMe服务端收到用户上传的带有引导结束标识的GPS位置以后，将发布一条求救消 息，所有消息的订阅者都可以收到包含位置信息的求救消息，以进一步帮用户缩短获得救援 运输服务的时间。

以上通过实例对本发明进行了详细的描述，本领域的技术人员应当理解，在不超出本发 明的精神和实质的范围内，对本发明做出一定的修改和变动，比如对服务器返回数据的具体 表示格式进行修改，或对索引的组织方式及搜索过程进行局部修改，仍然可以实现本发明的 目的。本发明的保护范围以权利要求书所述为准。