1.面向交通路网的时间序列图最优路径查询方法，其特征在于，包括以下步骤：

步骤一：交通路网模型的建立：将实际路网模型抽象化，对构成交通路网的路段和节点道路元素进行描述，使其能够表示实际道路相关路段的属性和几何信息；

步骤二：定义时间序列图：将交通路网模型给予形式化描述为时间序列图，为下一步进行最优路径查询做准备，并针对给定的时间序列图定义最优路径；

步骤三：采用入边表示法针对时间序列图进行标记和排序，可以快速得到某个路径顶点的所有入边邻居道路的信息，并根据实际情况建立B+树索引以提高查询效率；

步骤四：通过反向搜索，查询得到时间序列图中最优路径；

所述的步骤二的具体执行过程包括：

步骤2-1：时间序列图定义：

时间序列图是一个有向图，记作G＝(V,E,D,T,C)，V是路径顶点的集合，E是道路边的集合，D是路径顶点出发时间的集合，T是道路边的遍历时间的集合，C是道路边的费用代价的集合；

对于任意道路边e＝(a,b)，存在一个出发时间的集合Dab，一个遍历时间的集合Tab和一个费用代价的集合Cab，使得Dab、Tab和Cab中的元素相对应；对于Dab中的任意元素d，Tab存在唯一的元素t，Cab中存在唯一的元素c使得d，t，c相互对应；即开始从道路边e＝(a,b)于时间d出发时，遍历时间为t，费用代价为c；其中，费用代价c通常与出发时间和遍历时间相关，设定费用代价为离散值；同时，定义Tin(a)表示路径顶点a的入边邻居道路的集合，Tout(a)表示路径顶点a的出边邻居道路的集合，din(a)表示路径顶点a的入度，dout(a)表示路径顶点a的出度；对于无向图，将无向图的所有无向边均转换为方向相反的两条有向边，计算其入度和出度；

在时间序列图中，每一条道路边上的每对数字表示遍历时间和费用代价，在实际应用中遍历时间和费用代价必定是大于零的，故设定遍历时间和费用代价均大于零，带下划线的数字表示从该道路边出发的时间；对于任意的i(1＜i≤k)，将道路边ei＝(vi,vi+1)与Dvivi+1、Tvivi+1和Cvivi+1中相对应的元素组合连接成五元组(vi,di,vi+1,ti,ci)，该五元组满足di-di-1-ti-1＝ωi，ωi≥0即ωi为第i个路径顶点vi的等待时间，即从路径顶点vi出发沿着道路边ei到达vi+1，需要等待ωi时间，才能于时间di出发；因此，对于时间序列图中的路径有如下定义：对于任意的i(1＜i≤k)，路径P是五元组(vi,di,vi+1,ti,ci)的一个有序序列；同时定义：arrive(P)＝(dk+tk)，即路径P的到达时间；depart(P)＝d1，即路径P的出发时间；dura(P)＝arrive(P)-depart(P)，即路径P的持续时间；即路径P中的中转顶点的数量；即路径P的费用代价；

步骤2-2：最优路径定义：

给定时间序列图G，时间间隔[ts,te]，出发路径顶点Vs，目标路径顶点Ve，Vs到Ve的路径集合记作P；P中的路径P满足以下条件：depart(P)≥ts，arrive(P)≤te；由此扩展可得：最早到达路径P:P∈P，满足arrive(P)≤arrive(P')，

最晚出发路径P:P∈P，满足depart(P)≥depart(P')，

最少用时路径P:P∈P，且满足dura(P)≤dura(P')，

最少中转路径P:P∈P，且满足trans(P)≤trans(P')，

最小费用路径P:P∈P，并且满足cost(P)≤cost(P')，

因此，时间序列图最优路径包括：最早到达路径、最晚出发路径、最少用时路径、最少中转路径和最小费用路径的集合。

2.根据权利要求1所述的面向交通路网的时间序列图最优路径查询方法，其特征在于，所述的步骤一的具体执行过程包括：在对交通路网进行建模时，满足如下要求：由若干连续的点所组成的多边线，其中首尾点称作“结点”，中间点称作“接点”；“结点”表示道路的起始点和结束点，道路与道路之间通过结点相连；“接点”代表道路的数字化坐标，不具有表达拓扑关系的功能，首尾点间的所有中间点都是与该首尾点路段有可达或被可达关系的路段，一定程度上可以提高路径搜索的效率；在交通路网中对一条道路的数据结构详细描述如表1所示；

表1

交通路网模型示意图中部分道路的数据结构如表2所示；

表2。

3.根据权利要求1所述的面向交通路网的时间序列图最优路径查询方法，其特征在于，所述的步骤三的具体执行过程如下：与路径表示中的五元组(vi,di,vi+1,ti,ci)类似，将时间序列图中的路径顶点、道路边、出发时间、遍历时间和费用代价信息，组成(vi,di,vi+1,ti,ci)的五元组结构；采用入边表示法即对于时间序列图中的每个路径顶点以五元组的形式存储指向它的路径顶点以及道路边的信息，指向同一路径顶点的道路边按照路径顶点的标记和道路边的出发时间升序排列，同时可以根据实际情况建立索引以提高查询效率；基于时间序列图的入边表示法，可以快速的得到某个路径顶点的所有入边邻居道路的信息；同时建立B+树索引提高查询效率。

4.根据权利要求1所述的面向交通路网的时间序列图最优路径查询方法，其特征在于，所述的步骤四的具体执行过程如下：步骤4-1基于代价限制的反向搜索，过程如下：

反向搜索方法对于目标顶点Ve的每个入边邻居道路，查询扩展符合条件的道路边；首先，对于查询得到的第一个入边邻居道路u，初始时path(传递参数)为空，计算扩展以后，如果path仍为空，则查询下一个入边邻居道路；否则，判断u是否等于Vs，如果是，则将结果保存到resultPath(结果集)中，而后转向查询扩展Ve的另一个入边邻居道路；否则递归查询从出发顶点Vs到u的路径，时间间隔由[ts,te]更新为[ts,d]，其中d为最后一条添加到currPath(临时结果集)中的道路边的出发时间，该道路边的出发时间最大，即d最大；对于u的入边邻居道路v，此时path不为空，将查询得到的道路边与path执行连接操作，如果道路边的到达时间小于等于path中某条路径的出发时间并且道路边的代价加上path中路径的代价小于等于fee(最大代价)，则将该道路边插入到该路径中，作为初始道路边，结果保存到currPath中；如果没有能扩展的道路边，即currPath为空，则本次循环结束，转而递归查询u的另一个入边邻居道路；如果currPath不为空，则继续判断计算，直到目标顶点Ve所有的入边邻居道路都查询扩展完毕；

如果得到的resultPath为空，表示没有符合条件的路径，搜索过程结束；否则计算比较resultPath中每条路径的出发时间、到达时间、持续时间、中转站数和费用代价，得出最优路径；

步骤4-2时间序列图中的最优路径查询：

由步骤4-1可知，反向搜索方法采用了反向递归搜索的策略，从目标顶点出发，以满足时间条件和费用代价为判断依据，依次递归遍历入边邻居道路，计算查找符合代价限制的路径，因此，基于反向搜索特点，最优路径查询方法分为两个阶段：首先，调用基于代价限制的反向搜索方法计算得到所有符合限制条件的路径；其次是对符合条件限制的路径的时间代价和费用代价进行计算，基于不同的代价考虑，比较后得到最优路径；最优路径查询方法初始化时，resultPath和path被赋值为空，而后调用反向搜索方法计算符合时间条件和费用代价的路径，如果得到的resultPath为空，表示没有符合条件的路径，方法结束；否则执行路径选择阶段，计算resultPath中每条路径的出发时间、到达时间、持续时间、中转站数和费用代价，根据默认优先程度或者用户需求比较每条路径的相关数据，最后得出最优路径；结果路径默认的优先程度排列为：费用代价>遍历时间>到达时间>出发时间>中转次数；也可根据用户的需求，灵活设置相应的优先程度，据此来筛选结果，返回用户需要的结果。

5.根据权利要求4所述的面向交通路网的时间序列图最优路径查询方法，其特征在于，还包括步骤五：基于特定情况的可变阈值最优路径；所述的可变阈值最优路径，其搜索过程是针对反向搜索阶段的反向搜索方法进行扩展，即对时间序列图的入边表示法中的五元组进行扩展，增加一个阈值变量k，用来指示该道路边的状态；同时设置一个系统阈值κ；阈值变量k的值，根据实际情况，由相关领域专家进行赋值，并进行动态更新，系统阈值κ由相关领域专家设置为临界值；

执行扩展的反向搜索方法时，根据本次查询的入边信息的阈值变量k的值与系统阈值κ的比较情况，决定是否通过该道路边进行扩展查询；即当且仅当阈值变量k小于系统阈值κ时，才通过该道路边进行扩展查询，否则直接淘汰该道路边；

在基于特定情况的可变阈值最优路径的反向搜索阶段，执行时增加了对阈值变量的比较：当阈值变量小于系统阈值时，说明该道路边情况正常，不会影响查询结果，可以通过该道路边进行扩展计算；当阈值变量大于等于系统阈值时，说明发生异常情况，不能通过该道路边进行扩展计算，本次查询结束。