CN110309962B - 基于时间扩展模型的铁路行程路线规划方法及装置 - Google Patents

Abstract

本发明提供一种基于时间扩展模型的铁路行程路线规划方法及装置，通过比较标准时间扩展模型与中国铁路网络实际情况的差异，对标准的时间扩展模型进行改进，获取适用于中国铁路网的时间扩展模型，并且以此模型为基础建立基于时间扩展模型的空铁联运模型和空铁地联运模型；然后基于改进模型使用Dijkstra算法求解铁路行程规划最优路径问题，并基于回溯算法思想求解铁路行程规划K优路径问题；最后利用模型压缩和A*算法对行程规划算法进行加速处理，使算法可以实现旅客出行方案的实时计算，与现有技术相比，本发明提供的铁路行程路线规划方法效率显著提高。

Description

基于时间扩展模型的铁路行程路线规划方法及装置

技术领域

本发明属于铁路路径优化领域，特别涉及一种基于时间扩展模型的铁路行程路线规划方法及装置。

背景技术

随着社会的发展，人们的出行需求逐渐增大。铁路作为基本交通方式之一，具有价格低、速度较快等特点，因此它所承受的客运量也变得越来越大。根据中国国家统计局公布的《2018年国民经济和社会发展统计公报》得到：2018年我国全年运输总量(铁路、公路、水运、民航)179亿人次，其中铁路运输量33.7亿人次，比去年增长9.4％。铁路已经成为人们的重要出行方式之一。显然，根据旅客的出行需要(换乘最少、票价最低以及时间最少等)来得到两地之间的铁路乘车方案是旅客选择铁路方式出行需要面临的首要问题。

国内外所有的运输部门都是根据时刻表来进行服务的。时刻表中记录了所有车辆发车时间以及经停站等等，所谓行程规划，就是根据时刻表以及旅客本身的需求，在所有可能的方案中找到一个或者多个最优解。

一个典型的行程规划系统，应当能解决以下几个目标下的最优路径问题：最少换乘问题，旅客从起始站去目标站，要求是换乘的次数最少；最短行程时间问题，目标是使得旅客在行程中所花费的时间(包含在站内等待的时间)最短；最早到达问题，目标是使得旅客能最早到达目标站；多目标优化问题，综合考虑以上几种目标，实现帕累托最优。

中国铁路网络具有特殊性和复杂性，需要对现有技术公开的时间扩展模型以及算法进行改进来实现中国铁路路径的行程规划。

发明内容

为了解决现有技术中存在的问题，本发明提供一种基于时间扩展模型的铁路行程路线规划方法。

本发明具体技术方案如下：

本发明提供一种基于时间扩展模型的铁路行程路线规划方法，该方法包括如下步骤：

构建适用于铁路网的时间扩展模型；其中，铁路网优选为中国铁路网；构成时间扩展模型的时间扩展图G＝(V,E)，V表示节点集合，E表示边集合，节点集合包括到达节点、出发节点和换乘节点；且对于任意一个节点v∈V，v具有以下属性：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间t的分钟数；STATION(v)表示v所属车站；TRAIN(v)表示v所代表的全车次；CITY(v)代表v所属的城市；如果(u,v)∈E，那么一定有TIME(u)≤TIME(v)，边集合包括到达节点指向换乘节点的边、到达节点指向出发节点的边、换乘节点指向换乘节点的边、换乘节点指向出发节点的边及出发节点指向到达节点的边；

在时间扩展图上，搜索从出发节点指向到达节点的各边组成的路径中权值最小的路径，获取最优路径。

进一步的改进，所述的构建适用于铁路网的时间扩展模型包括如下步骤：

读入站和城市信息：建立站与城市的索引，站与城市的关系表以及可出发站表；

读入列车开行周期：根据列车的开行周期获得扩展时刻表，依据扩展时刻表建立时间扩展模型的雏形；

添加站内换乘边：对于每一个允许换乘的站S，将属于站S的所有换乘节点按照时间排序，排序后的节点为v₁，…，v_k，添加边(v_i，v_i+1)1≤i≤k-1；遍历S中的到达节点，对于每一个满足STATION(u)＝S的到达节点u，找到最小的i满足TIME(v_i)-TIME(u)≥TRANSFER(S)，添加边(u，v_i)；

添加同城换乘边：站S₁与站S₂之间允许同城换乘，遍历站S₁中的所有到达节点，对每一个满足STATION(u)＝S₁的到达节点，在站S₂的换乘节点序列v₁，…，v_k中，找到最小的i满足TIME(v_i)-TIME(u)≥t，添加边(u，v_i)，其中t为同城换乘的最小换乘时间。

进一步的改进，基于时间扩展模型运行Dijkstra算法获取最优路径具体包括：

给边设置权值；

运用Dijkstra算法在时间扩展图中进行搜索，获得最优路径。

进一步的改进，所述方法还包括在获取的最优路径基础上，利用回溯算法获取K优路径。

进一步的改进，所述方法还包括在适用于铁路网的时间扩展模型的基础上构建基于时间扩展模型的空铁联运模型和/或空铁地联运模型。

进一步的改进，运行Dijkstra算法采用的数据结构包括Dial桶、N元堆、Radix堆、Fib堆或二元堆。

进一步的改进，获取K优路径包括如下步骤：

one-to-all：用于求解起点到其它点的最优路径权值；

回溯：通过反向查找获取前K优路径。

进一步的改进，利用回溯算法获取K优路径还包括对K优路径算法的优化，包括对时间扩展图进行压缩或利用A*算法对回溯算法中的one-to-all过程进行加速。

进一步的改进，本发明还提供一种基于时间扩展模型的中国铁路行程路线规划装置，该装置包括：

模型构建组件：所述模型构建组件被配置为构建适用于铁路网的时间扩展模型，构成时间扩展模型的时间扩展图G＝(V,E)，V表示节点集合，E表示边集合，节点集合包括到达节点、出发节点和换乘节点；且对于任意一个节点v∈V，v具有以下属性：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间t的分钟数；STATION(v)表示v所属车站；TRAIN(v)表示v所代表的全车次；CITY(v)代表v所属的城市；如果(u,v)∈E，那么一定有TIME(u)≤TIME(v)，边集合包括到达节点指向换乘节点的边、到达节点指向出发节点的边、换乘节点指向换乘节点的边、换乘节点指向出发节点的边及出发节点指向到达节点的边；

搜索组件：所述搜索组件被配置为在时间扩展图上，搜索从出发节点指向到达节点的各边组成的路径中权值最小的路径，获取最优路径。

本发明提供一种基于时间扩展模型的铁路行程路线规划方法及装置，该方法在考虑同城换乘、结算站、列车开行周期等问题基础上，建立了适合中国铁路应用需求的时间扩展模型，并且基于时间扩展模型的票程规划计算模型，提出了基于Dijkstra算法获取最优路径及基于回溯算法获取K优路径，与现有技术相比，本发明提供的中国铁路行程路线规划算法效率显著提高。

附图说明

图1为基本的时间扩展模型；

图2为读入时刻表数据后的时间扩展模型；

图3为适合中国铁路网的时间扩展模型；

图4为多种数据结构下Dijkstra算法的效率；

图5为N元堆中n对Dijkstra算法效率的影响；

图6为算法实例图；

图7为One-to-all步骤给各点的标记图；

图8为回溯过程中R的变化；

图9空铁联运的时间扩展模型；

图10空铁地联运三层时间扩展模型；

图11单纯的大巴模型；

图12空铁地联运时间扩展模型

图13为改进之后的时间扩展模型；

图14为压缩模型对响应效率的影响；

图15为A*算法对响应效率的影响；

图16四种目标下的K优路径算法实验结果；

图17回溯算法与MS算法的对比；

图18回溯算法与YEN算法的对比；

图19回溯算法与加速后YEN算法的对比；

图20列车晚点算法响应效率；

图21票程规划算法效率。

附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行。虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所描述的步骤。

具体实施方式

由于本发明的方法描述是在计算机系统中实现的，该计算机系统可以设置在服务器或客户端的处理器中。例如本文所述的方法可以实现为能以控制逻辑来执行的软件，其由服务器中的CPU来执行。本文所述的功能可以实现为存储在非暂时性有形计算机可读介质中的程序指令集合。当以这种方式实现时，该计算机程序包括一组指令，当该组指令由计算机运行时其促使计算机执行能实施上述功能的方法。可编程逻辑可以暂时或永久地安装在非暂时性有形计算机可读介质中，例如只读存储器芯片、计算机存储器、磁盘或其他存储介质。除了以软件来实现之外，本文所述的逻辑可以利用分立部件、集成电路、与可编程逻辑设备(诸如，现场可编程门阵列(FPGA)或微处理器)结合使用的可编程逻辑，或者包括它们任意组合的任何其他设备来体现。所有此类实施均落入本发明的范围之内。

在理解本申请发明要点之前，需要先了解以下内容：

时间扩展模型建模的主要思路是将铁路网络中的每一个发车和到站事件作为图的一个节点；属于不同站点的节点相连，代表一辆列车在两个站间运行；同一站点内的节点按时间顺序相连，代表旅客在站内的等待。这样一个站点就按照时间展开得到多个节点，每个节点同时包含了空间信息(所属的站点)和时间信息(发车或者到站时刻)，铁路网络被构建为一个时空网络，称为时间扩展模型，如图1所示。

Dijkstra算法是很有代表性的最短路算法。传统的Dijkstra算法用于寻求从固定起点到其余各点的最短路径，它是按路径长度递增的次序产生最短路径的算法。

Dijkstra算法的基本思想是生成一棵以固定起点为根的最短路径生成树。根到树中每个结点的路径即为根到该点的最短路径，因为传统Dijkstra算法所求问题的网络中不存在负权，所以这棵最短路径生成树在生成过程中将对各结点按其距固定起点的远近以及点间的邻接关系来逐个地加入到树中，先近后远。

下边结合具体实施例阐述本发明所要保护的内容。

本发明的一个实施例提供一种基于时间扩展模型的铁路行程路线规划方法，该方法包括如下步骤：

S1：构建适用于中国铁路网的时间扩展模型；

步骤S1中构建具有如下时间扩展图的适用于中国铁路网的时间扩展模型，其中，时间扩展图G＝(V,E)，V代表节点集合，E代表边集合，G具有以下性质：

V中有三种节点：到达节点、出发节点与换乘节点；且对于任意一个节点v∈V，v具有以下属性：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间t的分钟数；STATION(v)表示v所属车站；TRAIN(v)表示v所代表的全车次；CITY(v)代表v所属的城市。

如果(u,v)∈E，那么一定有TIME(u)≤TIME(v)；E中的边分为如下五类：

(a)到达节点指向换乘节点的边。该边代表了换乘事件的发生。如果两个节点在同一个站里，表示站内换乘，该站为可换乘的；否则代表了同城换乘，这两个站为可同城换乘的。

(b)到达节点指向出发节点的边。该边代表旅客在该站不下车，直接坐同一趟车离开该站。

(c)换乘节点指向换乘节点的边。该边代表了旅客在站内等待下一趟车的到来。

(d)换乘节点指向出发节点的边。该边代表了车已经准备出发，旅客上车出站。

(e)出发节点到到达节点的边。该边代表旅客乘车去下一站。

比如，另一些实施例中，介绍了适用于中国铁路网的时间扩展模型的构建包括如下步骤：

S11：读入站和城市信息

即建立站与城市的索引，站与城市的关系表以及可出发站表。采用哈希表来存储所有的站和城。城用一个结构体表示，包含的信息有城市码、城市名、属于城市的换乘节点集合。站也用一个结构体表示，包含的信息有站码、站名、所属城市、标记、换乘节点集合、到达节点集合。其中标记用来表示该站是不是可出发站，换乘节点集合和到达节点集合表示属于这个站的所有换乘节点和到达节点集合。

S12：读入列车开行周期

根据列车的开行周期来得到扩展时刻表，然后依据扩展时刻表建立时间扩展模型的雏形。如图2所示，图中的每一个节点都由一个结构体来表示，包含了以下信息：节点编号、节点所属站、节点代表的时间、节点代表的列车全车次、节点代表的列车站车次、节点属性。比如优选的实施例中，节点可以有三种属性，1代表到达节点，2代表换乘节点，3代表出发节点。

对于扩展时刻表中的每一条记录，生成三种类型的节点各一个，并填写节点相应的信息，最后扩充站和城结构体中的点集结构。每一个点都会加到相应的站的点集中去，但仅仅当站属于可出发站时，点才能加到相应的城市点集中。每当遍历了一趟车的所有节点时，把这趟车对应的到达节点和出发节点以及换乘节点和出发节点用一条边连接起来。

S13：添加站内换乘边

对于每一个允许换乘的站S，将属于站S的所有换乘节点(这可以通过站的结构体直接得到)按照时间排序，排序后的节点为v₁，…，v_k，添加边(v_i，v_i+1)1≤i≤k-1。

最后，遍历S中的到达节点，对于每一个满足STATION(u)＝S的到达节点u，找到最小的i满足TIME(v_i)-TIME(u)≥TRANSFER(S)，添加边(u，v_i)。

S14：添加同城换乘边

与添加站内换乘边的过程类似，如果站S₁与站S₂之间是允许同城换乘的，遍历站S₁中的所有到达节点，对每一个满足STATION(u)＝S₁的到达节点，在站S₂的换乘节点序列v₁，…，v_k中，找到最小的i满足TIME(v_i)-TIME(u)≥t，添加边(u，v_i)，其中t为同城换乘的最小换乘时间。

最终，获得的时间扩展模型如图3所示。图中一共有三个站A，B，C。其中A和B都是允许换乘而且可以同城换乘的，C则是不允许换乘。

S2：基于步骤S1构建的时间扩展模型运行Dijkstra算法获取最优路径。

步骤S2中，基于步骤S1构建的适用于中国铁路网的时间扩展模型运行Dijkstra算法获取最优路径的问题描述为：在时间[t₁，t₂]从城市S₁出发去城市S₂有很多种方案，用

f＝(ST_1a，ST_1d，Z₁，t_1a，t_1d，ST_2a，ST_2d，Z₂，t_2a，t_2d，…，ST_(n-1)a，ST_(n-1)d，Z_n-1，t_(n-1)a，t_(n-1)d)来表示一个可行的方案，说明旅客在t_1d时刻乘坐Z₁从站ST_1d出发，在时刻t_1a到达ST_1a。然后在时刻t_2d乘坐Z₂从站ST_2d出发，在时刻t_2a到达ST_2a，……最终在时刻t_(n-1)d乘坐Z_n-1出发，在时刻t_(n-1)a到达ST_(n-1)a。为了保证该方案的合理性，必须满足以下条件：

ST_1d＝S₁

ST_(n-1)a＝S₂

t_1d∈[t₁，t₂]

ST_ia≡ST_(i+1)d或者ST_ia与ST_(i+1)d可进行同城换乘

令F＝{f|f为在时间[t₁，t₂]从S₁出发去S₂的方案}，即F是所有在时间[t₁，t₂]从城市S₁出发去城市S₂的方案的集合，对于旅客而言，其中就有一些方案是优于其他方案的，用Value(f)表示旅客在某种判断标准下对方案f的评价，那么最优问题转换成为一个优化问题：

由于旅客的偏好不同，因此，对Value(f)的计算有很多种不同的标准，这些标准引出了不同的行程规划问题。

最常用的标准分为以下几个：

(a)旅行时间

根据Value(f)计算方式的不同，该判断标准又可以分为两个子问题：

最早到达问题：Value(f)＝t_(n-1)a

最短行程时间问题：Value(f)＝t_(n-1)a-t_1d。

(b)换乘次数

倒车往往会给旅客带来不便和一些新的开销，所以大部分旅客是偏向于换乘次数较少的方案的。由这一判断标准可引出最少换乘问题。定义

transi表明了旅客在ST_ia是否倒车；最少换乘问题可取

(c)票价

对于某些旅客而言，省钱才是最重要的，他们愿意为了节约一些钱而选择一些倒车次数或者旅行时间很长的方案。由这个判断标准可引入最低票价问题；用price_i表示乘坐Z_i从STi_d到ST_ia的价格，最低票价问题可取

(d)综合考虑以上四种因素

旅客在选择乘车方案的时候不会只有一个判断标准，会综合考虑各种标准，然后选出一个满意的方案。由这个判断标准可引入pareto最优行程规划问题。用λ₁，λ₂，λ₃，λ₄分别表示旅客对到达时间、旅途时间、倒车次数、票价的偏好，那么pareto最优行程规划问题可取

为了能使用时间扩展模型来解决提出的优化问题，需要得到一个从方案f到时间扩展图中的一个路径P的一一对应关系。

时间扩展图中每一个点都代表了一个事件的发生，而方案f唯一对应了2(n-1)个事件的发生，把这2(n-1)个点组成的路径连接起来，就可以得到方案f对应的路径P(f)。

在时间扩展图中设置合适的权值使得cost(P(f))＝Value(f)，就可以利用Dijkstra算法解决提出的优化问题。由此得到了利用时间扩展模型解决优化问题的基本流程如下：

给边设置合适的权值使得cost(P(f))＝Value(f)；

运用Dijkstra算法在时间扩展图中进行搜索，获得最优路径。

影响Dijkstra算法的因素主要有：图的规模、优先队列的选取以及点对的实际距离。

适用于Dijkstra算法的常用数据结构有N元堆、Radix堆、Fib堆、二元堆以及Dial桶，多种数据结构的时间复杂度如下表所示：

表1多种数据结构的时间复杂度对比

由上表可以看出，Dial桶各项操作的复杂度都是最低的，因此，Dial桶是最合适的数据结构。下面举例证明。

用多种数据结构实现Dijkstra算法，并进行测试，测试中使用的时间扩展图中一共有1513754个点，2575593条边，选择的优化目标为最短行程时间。测试结果见图4和图5。

图中每一种数据结构都对应一个盒子，每个盒子都有五条线，从下到上分别为测试数据中的最小值、四分之一值、中位数、四分之三值、最大值。矩形则是测试点的主要分布区域。其中，中位数反映平均的响应效率，而最大值与最小值之差反映出响应时间的波动范围。

从图中可以看出，Dial桶的效率最高，平均只要14ms就可以响应一次请求，而且对于不同的点对，Dial桶的响应时间变化范围也是最小的。由于Dial桶具有最低的复杂度和最高的效率，最终采用了Dial桶来实现Dijkstra算法。

运行Dijkstra算法实现不同标准下的路径优化，具体包括如下：

1.最短行程时间算法获取最短行程时间路径

本发明以旅途时间为判断标准处理最短行程时间问题。

最短行程时间问题：给定两个城市S₁和S₂以及一个出发时间区间[t₁，t₂]，目标是找到行程时间最短的路径。

这个问题等价于下面的优化问题：

令(u，v)∈E，设置cos t(u，v)＝TIME(v)-TIME(u)，那么有cos t(P(f))＝Value(f)

证明：令P(f)＝{v₁，v₂，…，v_m}，由于P(f)与f是相互对应的，故以下等式成立：

TIME(v₁)＝t_1d，TIME(v_m)＝t_(n-1)a

对v∈V，用cost(v)表示点v的权值，对(u，v)∈E，用cost(u，v)表示边(u，v)的权值，故对于路径P＝{v₁，v₂，…，v_n}，有

TIME(v₁)＝t_(n-1)a-t_1d+cos t(v₁)

故如果选取cost(v₁)＝0，就有cost(P(f))＝Value(f)。

将最短行程时间问题转变成为了一个最短路径问题，这个问题可以使用Dijkstra算法进行解决，用T表示优先队列，T.insert表示往T中插入一个元素，T.deleteMin表示删除T中权值最小的元素，T.decreaseKey表示减小T中指定元素的权值，用pre来记录每个点的前继节点。通过Dijkstra算法可以得到一条最短路径P，然后把P映射成为一个方案f，即获得最短行程时间路径。

2.最早到达行程规划算法获取最早到达路径

以旅途时间为判断标准来处理最早到达问题。

最早到达问题：给定两个城市S₁和S₂以及一个出发时间区间[t₁，t₂]，目标是找到行程时间最短的路径。

这个问题等价于下面的优化问题：

令(u，v)∈E，设置cos t(u，v)＝TIME(v)-TIME(u)，那么有cos t(P(f))＝Value(f)。

证明：令P(f)＝{v₁，v₂，…，v_m}，由于P(f)与f是相互对应的，故以下等式成立：

TIME(v₁)＝t_1d，TIME(v_m)＝t_(n-1)a。

对v∈V，用cos t(v)表示点v的权值，对(u，v)∈E，用cos t(u，v)表示边(u，v)的权值，故对于路径P＝{v₁，v₂，…，v_n}，有

故如果选取cos t(v₁)＝TIME(v₁)＝t_1d，就有cos t(P(f))＝Value(f)。

将最早到达问题转变成为了一个最短路径问题，这个问题和最短行程时间类似，也可以采用Dijkstra算法解决，唯一的区别在于，当点v需要加入到优先队列时，其初始权值为TIME(v)而不是0。

3.最少换乘行程规划算法获取最少换乘路径

以换乘次数为判断标准来处理最少换乘问题。

最少换乘问题：给定两个城市S₁和S₂以及一个出发时间区间[t₁，t₂]，目标是找到换乘最少的方案。

这个问题等价于下面的优化问题：

令(u，v)∈E，设置

那么cost(P(f))＝Value(f)。

证明：令P(f)＝{v₁，v₂，…，v_m}，显然，方案f被分为多段，如下所示：f＝{(ST_1a，ST_1d，Z₁，t_1a，t_1d)，(ST_2a，ST_2d，Z₂，t_2a，t_2d)，…，(ST_(n-1)a，ST_(n-1)d，Z_n-1，t_(n-1)a，t_(n-1)d)}考察

可以发现trans_i就是表示了第i-1段和第i段的车次Z是否相同。假定点u代表乘坐Z_i-1到达ST_(i-1)a，点v代表乘坐Z_i离开STi_d，那么P(f)中一定会有一条从u到v的子路径P′。如果Z_i≠Z_i-1，那么显然P′会有一条从到达节点去换乘节点的边，如果Z_i＝Z_i-1，那么不会存在这样一条边。因此，在这种权值设置下，cos t(P(f))＝Value(f)是成立的。

将最少换乘转变成为了一个最短路径问题。也可以采用Dijkstra算法解决。

4.多目标pareto最优行程规划算法获取最优路径

单一的目标很难准确地描述旅客的需求，因此需要综合考虑换乘次数以及行程时间来对方案进行比较。

以换乘次数和行程时间为判断标准来处理pareto最优问题。

pareto最优问题：给定两个城市S₁和S₂以及一个出发时间区间[t₁，t₂]，目标是找到换乘和行程综合起来权值最小的方案。

这个问题等价于下面的优化问题：

令(u，v)∈E，设置

v是换乘节点，那么有cos t(P(f))＝Value(f)

这个算法也可以使用Dijkstra算法来实现。

本发明另一个实施例提供的基于时间扩展模型的铁路行程路线规划方法还包括基于构建的时间扩展模型利用回溯算法获取K优路径。

行程规划中的K优路问题如下：

K优路问题：在所有方案集合F中，找到k个使得Value(f)最小的方案f。

就是找到一个集合Fk满足：

1.

而且如果|F|≤k，那么F_k＝F，否则|F_k|＝k；

2.对任意f₁∈F_k，f₂∈F-F_k，有Value(f₁)＜Value(f₂)。

随着Value(f)取值的不同，K优路问题可分为K短行程问题、K早到达问题、K少换乘问题以及多目标pareto K优路问题。

时间扩展图实际上就是一个非负权值的有向图，因此利用时间扩展模型来解决K优路问题的基础，就是非负权值有向图的点对点K优路问题。

非负权值有向图的点对点K优路问题：在图G＝(V，E)中，给定两个点s，t，搜索从s到t的所有路径中，权值最小的K条路径。

用P表示从s到t的所有路径的集合，目标是找到一个集合P_k满足：

1.

而且如果|P|≤k，那么P_k＝P，否则|P_k|＝k；

2.对任意p₁∈P_k，p₂∈P-P_k，有cos t(p₁)＜cos t(p₂)。

非负权值有向图的点对点K优路径算法介绍如下：

该算法先求解从起点到其他点的最短路距离，然后从终点出发反向查找，在标记过的点集中寻找前K短路径。

给定有向图G＝(V，E)，源点s和终点t，用cos t(u，v)表示边(u，v)的权值，其中u，v∈V，(u，v)∈E。对于任意的u∈V.Distance(u)表示从点s到点u的最短路径距离。Q表示open表，T表示close表。R表示路径集合，R中的每一个元素由一个三元组(P(s，v₁，t)，key,postKey)组成，其中P(s，v₁，t)为一条从s到t且经过v₁的最短路径，用{v₁，…，v_k,t}表示，key表示这条路径的总权值，postKey表示从v₁到t的子路径的总权值，num表示已找到的路径数。

该算法分为两步，one-to-all以及回溯。其中one-to-all用于求解起点到其它点的最优路径权值；回溯过程是通过反向查找确定前K短路径。

以最短距离问题为了，介绍one-to-all以及回溯的步骤的具体操作。

1.one-to-all

用Dijkstra算法确定从源点s到其它任意节点u的最短路距离Distance(u)，采用open表和close表的方式来实现Dijkstra算法。

2.回溯

初始化R为仅含一个三元组({t}，Dis tan ce(t)，0)的集合，并初始化变量num＝0。假设目前已经回溯到了点v₁，我们用集合{v₁，…，v_k，t}表示v₁到t的路径。因此，s到t的路径由两段组成，前半段为从s到v₁的最短路径，这条路径在one-to-all过程中被确定，后半段路径为{v₁，…，v_k，t}。

然后重复以下步骤：

删除R中key值最小的元素。

如果v₁＝s，那么记录找到了第num短路径，然后num加1。

如果v₁≠s，那么，对于所有满足(v，v₁)∈E的点v，如果v在one-to-all过程中得到了一个距离标签Dis tan ce(v)，将b＝({v，v₁，…，v_k，t}，Dis tan ce(v)+postKey+cos t(v，v₁)，postKey+cos t(v，v₁))插入R中。如果R中的元素数目超过了K，那么删除R中key值最大的元素直到R中的元素数目为K。

当

(此时没有更多的路径可供搜索)或num＝K(此时已经找到了前K短路径)时，回溯过程结束。

算法正确性证明：

引理一：集合R中的每一个三元组({v₁，…，v_n，t}，key，postKey)都代表了一条路径且该路径权值为key。

证明：由Dijkstra算法可知，存在一条从s到v₁的路径{s，u₁，…，u_n，v₁}，其总权值为Distance(v₁)，假设v₁到t路径{v₁，…，v_n，t}的权值为postKey。考虑下式：

key＝postKey+Distance(v₁)

于是有，从s到t的路径{s，u₁，…，u_n，v₁，…，v_n，t}的权值为key。

引理二：通过R.deleteMin()得到的三元组，其key值不会减小。

令({v₁，…v_n，t}，key，postKey)＝R.deleteMin()，那么对于R中任何一个三元组其关键值key₁肯定是大于等于key的。所以，只要证明接下来加入R的三元组，其关键值也大于等于key即可。从回溯的步骤可知，新加入的三元组具有如下的形式：({u，v₁，…v_n，t}，key₁，postKey₁)，其中

postKey＝COST{v₁，…v_n，t}，key＝DISTANCE(v₁)+postKey

postKey₁＝COST{u，v₁，…v_n，t}＝cos t(u，v₁)+postKey，key₁＝DISTANCE(u)+postKey₁于是，key₁-key＝DISTANCE(u)+cos t(u，v₁)-DISTANCE(v₁)；

因为DISTANCE(u)表示s到u最短路长度，于是DISTANCE(u)+co st(u，v₁)表示s到v₁的一条路径的长度。又DISTANCE(v₁)表示s到v₁的最短路径长度，于是有key₁-key＝DISTANCE(u)+cos t(u，v₁)-DISTANCE(v₁)≥0，引理得证。

由回溯算法求得的K条路径是前K短路径。

证明：由回溯的步骤可以知道，如果允许R集合无穷大，即算法中不删除R中key值最大的元素，那么实际上回溯是枚举了所有从s到t的可行路径。在这种情况下，由引理二可以知道，第一次通过R.deleteMin()得到的从s到t的路径是最短路径，第二次通过得到的从s到t的路径是次短路径，以此类推。

现在R中最多保存K条路径，只要证明，R中未保存的路径肯定不会是前K短路径即可。由引理一可以知道，对应于R中任何一个三元组的key，一定会存在一条路径其权值为key。当某一条路径通过R.deleteMax()从R中删除的时候，R中一定有K个元素，且这些元素的key值均小于被删除的路径的权值。于是，当一条路径通过R.deleteMax()删除的时候，这条路径一定不会是前K短路径中的一条。

综上所述，每次通过R.deleteMin()得到的从s到t的路径均属于K短路，且后一次得到的路径长度大于等于前一次得到的路径长度。

算法实例说明

对于图6所示的例子，假定起始点是0，终点是7，我们的目标是找到从0到7的前两条最短路径。

在经过one-to-all步骤之后，各点的标记如图7所示。

回溯步骤R的变化如图8所示。

可以看到，算法最终找到了最短路径{1，2，3，4，7}以及次短路径{1，2，3，6，4，7}。

与之前介绍的算法不同，城市可以看作是点的集合，所以这实际上是点集之间的前K优路径搜索问题，而且，由于到达时间是不确定的，因此，实际上只能确定出发点集，而不能确定到达点集。

K短路径行程规划算法包括如下：

1.K短行程规划算法获取k最短路径

在乘车时间K短行程问题中选取Value(f)＝t_(n-1)a-t_1d，其解决方法是在时间扩展图中设置边的权值cos t(u，v)＝TIME(v)-TIME(u)，并且设置起点的初始权值为0。

用{s₁，s₂，…s_k}表示出发点集合，用{t₁，t₂，…t_m}表示目标点集合。一个最简单的想法就是把点集转换为点。可以增加两个新的点S和T作为新的源点和目标点，并添加边(S，s_i)1≤i≤k以及(T，t_i)1≤i≤m，同时把这些新添加的边的权值都设置为零。于是点集{s₁，s₂，…s_k}到点集{t₁，t₂，…t_m}的前K短路径搜索就被转换为点S到T的前K短路径搜索。对于最后得到的路径P＝(S，v₁，v₂，…，v_n，T)，只需要去掉首尾两侧的点S和T即可。

接下来就是这两个点集的确定。城是由一个结构体表示的，该结构体中记录了城市中的所有出发节点和到达节点(这些节点可能分属不同的站，但一定是可出发站)。所以，出发点集的确定很简单，只要遍历城S₁的出发节点集合，找出所有满足TIME(u)＞t的点u，他们组成的集合就是出发点集合。到达点集则需要动态确定，对于城S₂的到达节点集合里的每一个点，如果它在one-to-all过程中得到了距离标签，就把它加入到到达节点集合中。

上述算法存在的问题为：需要对图进行改变，添加新的边，而时间扩展图作为全局变量是不能更改的。分析算法可知，在one-to-all过程中，点S一开始就会从优先队列中删除，然后将出发点集{s₁，s₂，…s_k}加入到优先队列中；在回溯过程中，点T一开始就会从R中删除，然后把到达点集{t₁，t₂，…t_m}加入到R中。所以，考虑对算法稍作改进，跳过点S和T。

在one-to-all部分，模仿加入了S的行为，不再把S加入到优先队列中，直接就把出发点集{s₁，s₂，…s_k}加入到优先队列，权值设置为0。在回溯部分，初始的R不再加入T，把到达点集{t₁，t₂，…t_m}中的点都加入到R中，然后开始回溯。因为源点S并不存在，所以回溯时判断找到一条路径的标准也需要更改。当删除的点v∈{s₁，s₂，…s_k}时，认为找到了一条路径。

2.K早到达行程规划算法获取K早到达路径

在乘车时间K短行程问题中选取Value(f)＝t_(n-1)a，其解决方法是在时间扩展图中设置边的权值cos t(u，v)＝TIME(v)-TIME(u)，并且设置起点v的初始权值为TIME(v)。

K早到达问题和K短行程问题对于边权值的设置是一样的，因此二者的算法相似。但是由于起始点的初始权值不同，这使得两者之间有一定的区别。对于K早到达问题，很容易证明任意点v在one-to-all步骤中如果能得到标记，那么这个标记一定会是TIME(v)，而且不会存在权值减少的问题。

由此得出，在one-to-all中，不需要保存所有节点的权值，close表只需要记录所有节点的状态，大大降低了算法的空间复杂度。而且，由于不存在节点权值减少这一过程，算法的时间复杂度也可以得到一定的提高。算法的回溯部分和K短行程问题一致。

3.K少换乘行程规划算法获取K少换乘路径

在K少换乘问题中选取

其解决方法是在时间扩展图中设置边的权值

并且设置起点v的初始权值为0。

算法和K早到达完全一样，仅仅是权值不同。

4.票价K低行程规划算法获取票价K低路径

对于旅客提出的K最低票价的查询需求，给出的是基于最少换乘条件下的最低票价的策略。由于换乘系数越多的车次，价格肯定比同等级的直达车贵很多，并且在购票难度、换乘难度、方案实用性方面，优势都已不再明显，因此基于最少换乘下的票价最低策略是合理且实用的。欲得出K最低票价的策略，先采用最少换乘算法将前K’条最少换乘的策略求出(K’大于等于K且为整数)，然后调用票价引擎得到每一条路线的票价权值，最后进行计算，按票价筛选出前K条票价较低的策略。

由此得到的票价最低算法如下：

(a)运行K少换乘算法，求出前K’条最短换乘的路径；

(b)计算搜索出的前K’条路径的权值；

(c)前K条较小权值的路径即为所求。

5.多目标pareto K优行程规划算法获取多目标pareto K优路径

针对多目标pareto K优路径仅考虑行程时间和换乘次数的pareto 优化，在多目标pareto K优行程问题中选取

设置边权值

v是换乘节点

算法和K短行程完全一致，由此得出当选取λ₁＝0，λ₂＝1时，就是K短行程问题，当选取λ₁＝1，λ₂＝0时，就是K少换乘问题。

需要注意，K少换乘权值设置，会在K少换乘问题中引入新的问题：停留超时问题和南辕北辙问题。

所谓停留超时问题，是指旅客在一个站内停留了超过一天的时间。假定时刻表如下表所示：

表2一个假定的时刻表

天津去北京有两趟车，T1和T2，北京去上海只有一趟车T3，但是它在这两天都会运行。显然，合理的最少换乘的两条路径应该是做T1或者T2到达北京，再从北京乘坐当天的T3去上海。但实际上可能会得到这样两条路径：乘坐T1去北京，然后乘坐当天的T3去上海或者在北京等一天，乘坐第二天的T3去上海。显然，第二个方案虽然在数学意义上是正确的，但它是不合理的，必须将其舍弃。

解决方法：当用Dijkstra算法第一次搜索到某个站S时，给该站一个时间标签t(S)，表示旅客最早可以在时间t(S)到达。接下来的搜索过程中，如果某个点u满足STATION(u)＝S，TIME(u)-t(S)＞1440，算法直接跳过u，不对其设置距离标签。这可以有效解决停留超时问题。但是，这种方法也会造成最优解的丢失。

所谓南辕北辙问题，就是说旅客先远离目的地，再前往目的地。这无论是行程时间还是票价开销都是比较高的，显然是不合理的方案，但是它的换乘次数可能会比较少，因而在算法中无法对这种方案进行排除。比如，假定北京去上海没有直达车，那么换乘一次是最优的结果，那么很有可能给出先从北京去内蒙古，再从内蒙古去上海的方案来。这种方案虽然在数学意义上是正确的，但是对于旅客而言，这种方案的质量很低，应当被排除。可以考虑利用各个站的经纬度来限制搜索范围，不允许旅客乘坐的车远离目标城市，但同样会造出最优解的丢失。

采用多目标最优可以很好地解决停留时间过长和南辕北辙问题。

因为这两个问题的出现，是行程规划系统没有考虑行程时间引起的。针对停留时间过长和南辕北辙问题，虽然方案的换乘次数是一样的，但质量较差的方案往往会导致行程时间很长，这样，在pareto K优问题中，质量较差的方案权值就会偏大，从而达到筛选的目的。

应当注意到，由于单纯的最短行程时间和最少换乘得到的解的质量太低，所以实际上并没有采用单纯的最短行程时间和最少换乘，而是用多目标优化来模拟这两个问题。

对于K短行程问题，选取λ₁＝10，λ₂＝1来进行模拟。之所以不选取λ₂＝0，是因为按照换乘次数对结果进行排序。考虑到行程时间会远大于换乘次数，这种参数选择导致的结果是，行程时间占主要影响，当行程时间一样的时候，会优先推荐换乘次数更少的方案。

对于K少换乘问题，选取λ₁＝1，λ₂＝7200。旅客在五天以内能到达任何地方，所以，这个参数的选择会使得换乘次数为主要影响因素，因为行程时间不会超过7200。而在换乘次数一样的路径中，行程时间更短的路径会被优先。

6.指定换乘城市行程规划算法

有时候，旅客可能会想先去某个城市办一件事情，然后再去目的地。在这种情况下，旅客的请求将变为(S₁，S₂，t₁，t₂，t₃，t₄，S₃，t₅，t₆)，表示旅客希望在时刻(t₁，t₂)从城市S₁出发，在(t₃，t₄)到达城市S₃，然后在(t₅，t₆)从城市S₃出发前往目的地S₂。目标则依然是找到前K条最短路径。

考虑到旅客一般会是在城市S₃办一件事情，这一部分的时间旅客并不在旅途中，所以，旅客在城市S₃停留的时间是不应该计算在方案的时间消耗里的。因此，指定换乘城市的算法可以拆分为两部分。

第一部分就是普通的换乘K少算法，分别求出从S₁到S₃的前K短路径以及从S₃到S₂的前K短路径。这一部分相当于调用两次换乘K少算法。

第二部分则是一个路径组合的问题。上述的两个前K短路径可以组合生成一共K*K条路径，然后从这K*K条路径里选择出权值最小的K条作为最终的结果。用F_1k表示从S₁到S₃的前K个方案，F_2k表示从S₃到S₂的前K个方案。

7.指定避让城市行程规划算法

有时候，旅客可能会不想经过某一个城市。在这种情况下，旅客的请求将变为(S₁，S₂，t₁，t₂，S₃)，表示旅客希望在时刻(t₁，t₂)从城市S₁出发，目的城市为S₂，而且旅客希望不经过城市S₃。目标则是求出在这种情况下的前K短路径。

在前面的规划算法里，进行one-to-all的时候，并没有考虑点的城市属性(点属于哪一个城市)。由于现在需要不经过城市S₃，因此，在one-to-all的时候需要对CITY(v)进行考虑。如果CITY(v)正好是S₃，那么直接跳过点v。

这样，由于one-to-all过程中，所有属于S₃的节点都不会被标记，因此在回溯的时候，所有的路径也不会经过城市S₃，满足要求。

8.票程规划算法

票程算法需要调用行程规划算法和调用存储席位的数据库，返回指定日期、车次、席别的余票信息，将余票信息和查询结果同时返回。

票程规划包括相对独立的两个部分，行程规划和余票库查询。行程同上，余票库查询过程如下：

余票库存储着每一趟车每天的余票信息，包括该车次拥有的所有的席位以及对应的余票数目。余票库采用ORACLE数据库来存储这些信息，算法使用固定的接口来调用余票信息查询函数，查询函数通过访问数据库来获取实时的余票信息，返回给所有的余票信息。列车的查询分为全程复用列车余票查询和非全程复用列车余票查询，对于非全程复用列车来讲，需要保证查询时起始站顺严格相等，终止站顺介于售票的最近站顺和最远站顺之间；对于全程复用列车来讲，终止站顺介于售票的最近站顺和最远站顺之间不变，起止站顺可以大于等于查询到的起始站顺，将满足条件的所有余票信息按席别求和后，返回结果。余票查询函数的输入参数格式如下：全车次|发车时间|起始站顺|终止站顺|全程复用标志|。返回的结果参数为JSON数组，里面存储的对象格式为：席别和对应的余票数量。

在行程查询后，调用余票查询接口，查询函数自行查询数据库后返回实时信息，而后将这些余票信息和行程规划一起打包返回即可，旅客根据搜索到的行程规划线路和对应的余票信息便可以自行规划较优的旅程。

以K早到达下的票程规划算法为例，详细的算法流程如下所示：

(a)调用K早到达算法，计算在给定出发时间区间内，给定的起点至终点的最早到达路径；

(b)对于每条路径的每条乘车方案，调用余票信息查询接口，返回余票信息；

(c)将余票信息和对应的路径方案作为结果返回即可。

9.列车晚点算法

之前的所有算法假定了时刻表是完全正确的，也就是说，无论什么情况下，如果时刻表上说明了该车会在18:00到站，那么这趟车就一定会在18:00到站。但实际上，这个假设是很难保证的，无论采用多少方法，列车晚点是难以避免的一个现实问题，在某些情况下，晚点甚至会导致一些方案不可行。比如表2所示的时刻表，如果不出现任何意外，旅客乘坐D29到达天津之后，是可以换乘D195去上海的。但如果由于某种原因，D29晚点了一个小时，这样，旅客就无法乘坐D195去上海了，如果在得知D29晚点之后，依然向旅客推荐D29换乘D195的方案，显然是不正确的。由于列车晚点是客观存在的，所以必须对列车晚点进行处理，当得知某一趟车晚点之后，在接下来的推荐方案里，就必须考虑到晚点的情况。

为了处理列车晚点问题，首先需要估计一趟车晚点之后的影响。这种影响是无法估计的，因为一趟车晚点，会导致整个铁路调度系统的变化，从而影响到其他车次，铁路局可能会选择让这趟车加速，使得在接下来的站点里该车没有晚点，也可能会选择让这趟车减速或者避让其他车次，以保证其他车次的正常运行。这给处理列车晚点问题带来了很大的困难，作如下假设：

列车晚点假设：如果一趟车在站S晚点t分钟，那么在接下来的所有站里，该车都会晚点t分钟。

考虑到实际中处理晚点情况都是已知晚点之后对图做更新，所以可以分别处理每列列车晚点情况，因此可以基于该假设进行模型更新方法研究。

接下来，就应该在时间扩展模型中处理晚点问题。应当注意到，时间扩展图中的每一个点都代表了列车到达或者出发事件的发生，而当列车晚点的时候，相应的节点不再能代表列车的到达和出发事件，因此需要对这些节点及其相应的边进行改动。假设列车在站S晚点了t分钟，用v表示列车在站内的到达节点，u表示列车在站内的换乘节点，把一个城市内所有换乘节点组成的链称为换乘链，那么对站S的处理如下所示：

(a)TIME(v)＝TIME(v)+t，TIME(u)＝TIME(u)+t；

(b)对于每一条边(k，u)∈E，删除这条边，如果k是到达节点，那么将k加入到一个集合T中；

(c)把u从换乘链中删除；

(d)在换乘链中找到相邻的两个节点s，t，满足TIME(s)＜TIME(u)＜TIME(t)，在s，t中间插入u；

(e)对于T中的每一个元素k，在换乘链中找到TIME(t)最小的一个点t满足TIME(k)+TRANSFER(S)＜TIME(t)，插入边(k，t)。

考虑到列车晚点假设，只需要对站S以及接下来列车将经过的所有站执行上述步骤即可。

本发明第三个实施例提供的基于时间扩展模型的铁路行程路线规划方法还包括基于构建的适用于中国铁路网的时间扩展模型构建空铁联运模型。

构建的空铁联运模型如下：对于时间扩展图G＝(V，E)，其中V代表顶点集合，E′代表边集合，G具有以下性质：

1.V中有三种节点：到达节点、出发节点与换乘节点；且对于任意一个点v∈V，v具有这些标签：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间的分钟数；STATION(v)表示v所属站；TRAIN(v)表示v所代表的全车次或者飞机班次；CITY(v)代表v所属的城市；LEVEL(v)表示v所属的层。

2.如果(u，v)∈E，那么一定有TIME(u)≤TIME(v)。E中的边分为五类，如下所示：

(a)到达节点指向换乘节点的边。该边代表了换乘事件的发生；如果两个节点在同一个站里，表示站内换乘，该站一定是可换乘的；否则代表了同城换乘，这两个站一定是可同城换乘的。

(b)到达节点指向出发节点的边。该边代表旅客在该站不下车，直接坐同一趟车离开该站。

(c)换乘节点指向换乘节点的边。该边代表了旅客在站内等待下一趟车的到来。

(d)换乘节点指向出发节点的边。该边代表了车已经准备出发，旅客上车出站。

(e)出发节点到到达节点的边。该边代表旅客乘车去下一站。

空铁联运模型如图9所示。

模型分为两层。第一层为铁路模型；第二层为航空模型。层的内部都是时间扩展模型。层与层之间以同城换乘的形式来进行联通。即：火车站通过同城换乘去飞机场，飞机场也通过同城换乘去火车站。为了使得层与层之间可以联通，增加假设：所有的飞机场都是“大站”，能够作为到达站以及进行同城换乘。

因此，单纯的铁路模型和单纯的航空模型就被合并成为了一个空铁联运模型。当处理铁路规划的时候，仅仅在第一层中进行搜索；当处理航空规划的时候仅仅在第二层中搜索；当处理空铁联运的时候，在两层中都进行搜索。

本发明第四个实施例提供的基于时间扩展模型的铁路行程路线规划方法还包括基于构建的适用于中国铁路网的时间扩展模型构建空铁地联运模型。

由于大巴也是基于时刻表来给旅客提供服务的，因此建立一个三层的空铁地联运模型，如图10所示。

从图中可以看出，在三层时间扩展模型中，大巴也被建模成为了一个时间扩展模型，并且作为新的一层加入到空铁联运模型中，于是，在空铁地联运模型中一共有三层：铁路层、飞机层以及大巴层。与空铁联运模型类似，为了使得层与层之间是相通的，同样假定大巴层与铁路层和飞机层之间采用同城换乘的方式进行联通，并且选取出一些长途车站作为可同城换乘的站。

构建大巴模型时，假定大巴的开行时间、开行周期以及开行线路都是确定的，且从站A去站B是否有直达的大巴。

大巴模型中，每一个节点代表了一个站。当两站之间有一趟大巴经过的时候，就在节点之间增加一条边。

大巴模型为：对于时间扩展图G＝(V，E)，任意节点v∈V代表了一个站，任意边(u，v)∈E代表了有一趟大巴从站u去站v。两个节点之间可能有多条边。

单纯的大巴模型如图11所示。

构建的空铁地联运模型如下，模型分为三部分：大巴模型、空铁联运模型以及模型的连接线。模型的连接线是一些站到站的边，如果S₁只有大巴，那么(S₁，S₂)表示从该站出发乘坐大巴能到达站S₂，(S₂，S₁)表示从S₂出发乘坐大巴能到达该站。

空铁地联运时间扩展模型如图12所示。

红线表示，当起点站没有火车和飞机的时候，旅客乘坐大巴去一个有火车或者飞机的站点。黑线表示，当终点站没有火车和飞机的时候，旅客乘坐大巴去终点站。

本发明第五个实施例提供了对算法的优化，具体如下：

5.1时间扩展图的压缩

为了提高算法的效率，对实施例1中步骤S1构建的适用于中国铁路网的时间扩展模型进行优化，具体优化步骤如下：

删除时间扩展图中所有的出发节点，然后添加相应的边以保证图的拓扑结构不变。最终改进之后的模型如图13所示。

图中站A为可以换乘的大站，站B为不允许换乘的站。把图中所有的出发节点删除，将相应的换乘节点作为出发节点来处理。然后对于每一个出发节点u，如果(v，u)∈E，(u，k)∈E，删除点u以及与之相关的所有边，然后添加边(v，k)，以保证图的拓扑结构不变。

对于时间扩展模型，在做了如上的改进之后，图规模的变化如下表所示：

表3模型改进对图规模的影响

可以发现，压缩模型(改进之后的模型)，图中点的数目减少了33.3％，边的数目减少了22.7％，这将极大的加快响应时间。

对上述模型进行测试，利用21天的中国铁路网规模大小如下表所示进行测试。

表4模型中21天的中国铁路网规模

选取K＝15，测试在铁路模型上进行，在K短行程问题中选取了λ₁＝10，λ₂＝1，测试结果如图14所示。

从图中可以看出，压缩之后，时间扩展图的点减少了33.3％，边减少了22.7％。对于最短行程时间问题，提高了43.2％的效率。

5.2时间扩展图上搜索算法的改进

加速算法主要从以下三个方面着手：

1.A*算法加速

A*算法中，最重要的就是A*表的选择。标准的A*算法中，需要对每一个点对之间的最短距离做出一个估计，并以此形成一个A*表。但是当图的规模很大的时候，这种A*表就显得很大，需要大量的额外空间。所以把图分成几个部分，A*表中仅仅存储这几个部分之间最短距离的估计值。由于时间扩展图中含有站的信息，可以考虑按照点所属于的站来对时间扩展图进行划分。

用S_i表示站，用Dis tan c e(S_i，S_j)表示站S_i到站S_j所需要时间下界的估计。最开始的时候，如果有列车从站S_i到达站S_j，选择其中耗时最少的一趟所花费的时间作为Distan c e(S_i，S_j)。而如果没有列车从站S_i到站S_j，设置Dis tan c e(S_i，S_j)为无穷大。

接下来，对得到的A*表进行Floyd算法，对于任意三个站S_i，S_j，S_k，满足下面三角不等式：

Dis tan c e(S_i，S_j)+Dis tan c e(S_j，S_k)≥Dis tan c e(S_i，S_k)

显然，这样得到的A*表的估计值不会超过实际值，因而可以保证不会丢失最优解。然而，为了解决城市C_i到城市C_j的k短路径问题，考虑到城市中往往有多个站，所以这个A*表是不能满足需求的。稍作改进即可。用Dis tan c e(S_i，C_j)表示站S_i到城市C_j的最短路径的下界。Dis tan c e(S_i，C_j)由下式决定：

这样就生成了解决本文的问题所需要的A*表，表中是站到城所需时间的估计。

2.缩小目标点集

从算法的回溯部分，可以发现只要在K短路径上点全部有距离标签，那在回溯过程中就不会丢失解。因此，在进行one-to-all的时候，只要标记了K短路径上的所有点就行了，所以，可以在one-to-all过程中估计已经找到的路径条数K′，当K′＞K时one-to-all过程就可以结束了。

在Dijkstra算法中，可以记录下每个点的前继，最终可以通过这样一个前继表来直接得到最短路径。如果最短路径不止一条，则可通过在算法过程中对每个点记录多个标号相同的前继得到所有的最短路径。对于时间扩展模型，目标站对应着多个节点(表示不同的到达时刻)。可以对这些节点分别做此操作，以此估计标号范围。具体做法如下：

每当搜索到一个目标站里的到达节点v_i时，遍历这个点的前继表，就可以得到从源点到达该点的最短路径的数目，记为NUM(v_i)。设Dijkstra算法标记的目标站里的节点依次为v₁，v₂，…v_m，如果

则标记算法停止。

采用了这种标号范围估计方法之后，在搜索K＝15时，平均只要找到目标站到达节点集中的5至6个点就可以结束标号过程了，大大提高了算法效率。

3.缩小时间扩展图

对时间扩展图G＝(V，E)内子图G′＝(V′，E′)进行搜索。其中，V′是V中五天以内的所有点的集合，而E′是E中五天内相应的边。设定出发时间为t，如果节点v满足TIME(v)-t＞7200，就不给节点v距离标签。

搜索算法改进的实例：

采用21天的中国铁路网数据规模如下表所示：

表5 A*算法中铁路网规模

模型大小如下所示：

表6 A*算法中模型规模

经过以上方法的加速，算法的效率如图15所示，对于最短行程时间问题，选择λ₁＝10，λ₂＝1；对于最少换乘问题，选择λ₁＝1，λ₂＝7200，选择K＝15。

由上图可以看出，以上三步的加速效果很明显，对于K短行程问题，加速效率为54.7％，对于K少换乘问题，加速效率为28.3％。

本发明第六个实施例对最优路径搜索效率进行了比较，具体如下：

6.1实验条件测试硬件和软件环境如下表所示：

表7测试环境

模型的规模如下表所示：

表8时间扩展图规模

旅客的搜索请求格式为(出发城市，到达城市，最早出发时间，最迟出发时间)。实验一共采用了440组搜索请求测试数据，搜索15条方案。

6.2四种目标下的K优路径算法实验分析

在时间扩展模型下测试了K早到达、K短行程、K少换乘以及票价K低算法的效率。算法中的Dijkstra算法采用Dial桶实验，一共进行了两组测试：测试1是在时间扩展模型中进行搜索，以此来模拟铁路模型的结果；测试2为在空铁联运模型中对铁路层和飞机层同时进行搜索。测试数据为前面选取的440组请求，测试结果如图16所示。

四种目标下的算法响应平均值如下表所示：

表9四种目标下的K优路算法响应平均值

横向对比，可以看到票价K低算法的响应效率最低，这是因为在票价K低算法中，需要求出远远超出K条方案来，然后对这些方案进行排序，严重影响了算法的效率。K少换乘算法效率远低于K短行程，这是因为，在选取换乘次数为优化目标的时候，一旦搜索到达了某个换乘节点，那么就一定会遍历该换乘节点之后的所有换乘节点，因为换乘节点之间的边权值为0，大大地扩大了搜索范围，因此K少换乘算法响应效率偏低。K短行程和K早到达算法效率是最高的，而且这两个算法仅仅只有起始节点的初始权值不同，但是K早到达算法效率要远高于K短行程，原因在于，K早到达算法中，对于任意节点v，其在close表中的值就是TIME(v)，这使得不需要记录close表中节点的权值，节约了大量的时间。

纵向对比，需要考虑两种影响：规模扩大带来的影响使得算法效率变低，因为测试2需要同时搜索铁路层和飞机层，这无形中增大了搜索的范围；最优解数值降低带来的影响使得算法效率变高，这是因为飞机的速度会远远大于火车，将导致最优解数值降低，因此算法会更早结束，从而提高了算法效率。对于K短行程和K早到达而言，最优解数值降低的影响更加明显，因此测试2的效率要高于测试1。但对于票价K低而言，由于票价K低是基于K少换乘的，在K少换乘算法中，如果搜索到了一个换乘节点，会遍历这个换乘节点之后的所有节点，因此在票价K低算法中，规模扩大的影响是占主导地位的，这使得测试2的效率低于测试1。对于K少换乘算法而言，两种影响几乎平衡，因此测试1和测试2的效率几乎一致。

6.3回溯算法和MS算法实验分析

对比回溯算法以及MS算法在K短行程、K少换乘以及K早到达算法下的效率，测试在空铁联运模型上进行，但仅仅针对铁路层进行搜索，所得到的实验结果如图17所示：

回溯算法与MS算法的平均响应时间对比如下表所示：

表10回溯算法与MS算法平均响应时间对比

由上表可以看出，对于K短行程、K少换乘以及K早到达问题，回溯算法优于MS算法。

6.4回溯算法和YEN算法实验分析

对比回溯算法和YEN算法在K短行程、K少换乘算法下的效率，测试在空铁联运模型下进行，但仅仅针对铁路层进行搜索。得到的测试结果如图18所示：

回溯算法与YEN算法响应的平均时间对比如下表所示：

表11回溯算法与YEN算法平均响应时间对比

可以看到，对于K短行程以及K少换乘而言，回溯算法优于YEN算法。

对YEN算法也进行了一定的加速，在其one-to-all过程里也采用了A*算法、缩小目标点集等方法来进行加速，得到的测试结果如图19所示。

回溯法与YEN算法的平均响应时间对比如下表所示：

表12回溯算法与加速后YEN算法平均响应时间对比

由上表可以看到，即便在YEN算法的one-to-all过程中采用了回溯法中同样的加速手段，回溯法的效率依然高于YEN算法。

6.5列车晚点算法测试

假定了一个列车晚点的数据，对于时间扩展图中的每一个到达节点，假定有

的概率选中该节点，并认为该节点所代表的车晚点了60分钟，最终选取了883个节点，并认为这883个节点代表的车晚点了60分钟，对这883个节点进行列车晚点算法的处理，其响应图如图20所示。

可以看到，每列列车晚点处理算法的平均响应时间是微秒量级的，能够满足票程规划系统实际应用需求。

6.6票程规划算法测试

在加入了余票信息之后，由于对所有的方案都需要查询余票信息，所以这会导致搜索算法效率降低。测试了加入余票查询后算法的效率。测试在空铁联运模型上进行，但只对铁路层进行搜索。测试结果如图21所示。

从图中可以看出，余票查询对于算法效率的影响是很明显的，为了更准确地分析这种影响，数据整理成下表：

表13余票查询对算法的影响

从差值里面可以看出，余票查询对票价K低和K少换乘算法影响基本一致，对K短行程和K早到达算法影响基本一致。这是因为，在K少换乘和票价K低的方案里面，得到的解大多数是只换乘一两次的方案，这样需要进行余票查询的次数比较少，因此，余票查询对这两个算法影响基本一致。而在K早到达和K短行程算法中，得到的解经常会换乘四五次，这样就使得余票查询的次数变多，从而余票查询对这两个算法影响基本一致，而且使得这两个算法效率降低得更加明显，因为需要进行余票查询的次数更多。但是这些影响均在10ms级，在实际的互联网等应用中是可以接受的。

Claims (8)

1.一种基于时间扩展模型的铁路行程路线规划方法，其特征在于，所述方法包括如下步骤：

构建适用于铁路网的时间扩展模型，构成时间扩展模型的时间扩展图G=（V,E），V表示节点集合，E表示边集合，节点集合包括到达节点、出发节点和换乘节点；且对于任意一个节点v∈V，v具有以下属性：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间t的分钟数；STATION(v)表示v所属车站；TRAIN(v)表示v所代表的全车次；CITY(v)代表v所属的城市；如果（u,v）∈E，那么一定有TIME(u)≤TIME(v)，边集合包括到达节点指向换乘节点的边、到达节点指向出发节点的边、换乘节点指向换乘节点的边、换乘节点指向出发节点的边及出发节点指向到达节点的边；

在时间扩展图上，搜索从出发节点指向到达节点的各边组成的路径中权值最小的路径，获取最优路径；

所述的构建适用于铁路网的时间扩展模型包括如下步骤：

读入站和城市信息：建立站与城市的索引，站与城市的关系表以及可出发站表；

读入列车开行周期：根据列车的开行周期获得扩展时刻表，依据扩展时刻表建立时间扩展模型的雏形；

添加站内换乘边：对于每一个允许换乘的站S，将属于站S的所有换乘节点按照时间排序，排序后的节点为v₁,⋯,v_k，添加边(v_i,v_i+1)，1≤i≤k-1；遍历S中的到达节点，对于每一个满足STATION(u)=S的到达节点u，找到最小的i满足TIME(v_i)-TIME(u)≥TRANSFER(S)，添加边(u,v_i)；

添加同城换乘边：站S₁与站S₂之间允许同城换乘，遍历站S₁中的所有到达节点，对每一个满足STATION(u)=S₁的到达节点，在站S₂的换乘节点序列v₁,⋯,v_k中，找到最小的i满足TIME(v_i)-TIME(u)≥t，添加边(u,v_i)，其中t为同城换乘的最小换乘时间。

2.如权利要求1所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，所述在时间扩展图上，搜索从出发节点到到达节点的各边组成的路径中权值最小的路径，获取最优路径具体包括：

给边设置权值；

运用Dijkstra算法在时间扩展图中进行搜索，获得最优路径。

3.如权利要求2所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，所述方法还包括在获取的最优路径基础上，利用回溯算法获取K优路径。

4.如权利要求1所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，所述方法还包括在适用于铁路网的时间扩展模型的基础上构建基于时间扩展模型的空铁联运模型和/或空铁地联运模型。

5.如权利要求2所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，运行Dijkstra算法采用的数据结构包括Dial桶、N元堆、Radix堆、Fib堆或二元堆。

6.如权利要求3所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，获取K优路径包括如下步骤：

one-to-all：用于求解起点到其它点的最优路径权值；

回溯：通过反向查找获取前K优路径。

7.如权利要求6所述的基于时间扩展模型的铁路行程路线规划方法，其特征在于，所述利用回溯算法获取K优路径还包括对K优路径算法的优化，包括对时间扩展图进行压缩或利用A*算法对回溯算法中的one-to-all过程进行加速。

8.一种基于时间扩展模型的铁路行程路线规划装置，其特征在于，所述装置包括：

模型构建组件：所述模型构建组件被配置为构建适用于铁路网的时间扩展模型，构成时间扩展模型的时间扩展图G=（V,E），V表示节点集合，E表示边集合，节点集合包括到达节点、出发节点和换乘节点；且对于任意一个节点v∈V，v具有以下属性：ATTR(v)表明v是哪一种节点；TIME(v)表示v代表事件发生时间相对于最早时间t的分钟数；STATION(v)表示v所属车站；TRAIN(v)表示v所代表的全车次；CITY(v)代表v所属的城市；如果（u,v）∈E，那么一定有TIME(u)≤TIME(v)，边集合包括到达节点指向换乘节点的边、到达节点指向出发节点的边、换乘节点指向换乘节点的边、换乘节点指向出发节点的边及出发节点指向到达节点的边；

搜索组件：所述搜索组件被配置为在时间扩展图上，搜索从出发节点指向到达节点的各边组成的路径中权值最小的路径，获取最优路径；

所述的构建适用于铁路网的时间扩展模型包括如下步骤：

读入站和城市信息：建立站与城市的索引，站与城市的关系表以及可出发站表；

读入列车开行周期：根据列车的开行周期获得扩展时刻表，依据扩展时刻表建立时间扩展模型的雏形；

添加站内换乘边：对于每一个允许换乘的站S，将属于站S的所有换乘节点按照时间排序，排序后的节点为v₁,⋯,v_k，添加边(v_i,v_i+1)1≤i≤k-1；遍历S中的到达节点，对于每一个满足STATION(u)=S的到达节点u，找到最小的i满足TIME(v_i)-TIME(u)≥TRANSFER(S)，添加边(u,v_i)；

添加同城换乘边：站S₁与站S₂之间允许同城换乘，遍历站S₁中的所有到达节点，对每一个满足STATION(u)=S₁的到达节点，在站S₂的换乘节点序列v₁,⋯,v_k中，找到最小的i满足TIME(v_i)-TIME(u)≥t，添加边(u,v_i)，其中t为同城换乘的最小换乘时间。

Images