启发式算法在轨道交通换乘路径求解问题的应用

张小丹

(呼和浩特铁路局科研所,内蒙古呼和浩特 010050)

启发式算法在轨道交通换乘路径求解问题的应用

张小丹

(呼和浩特铁路局科研所,内蒙古呼和浩特 010050)

在城市轨道交通系统中,换乘是一个关键环节。文章建立了轨道交通简化模型,初步提出启发式算法并引用到轨道交通换乘路径选择问题上来,结合某市轨道交通运营线路进行试算,最后证明该算法的有效性。

轨道交通 换乘 启发式算法

目前,轨道交通已成为人们出行选择的常用交通工具,乘客可以方便地从一条线路换乘到另一条线路。因为不同轨道交通线路通常隶属于不同的运营公司,所以在轨道交通运营过程中存在不同运营商之间分配车资的问题,即“清分问题”。随着轨道交通建设的迅速扩大和轨道交通网络的日益复杂,乘客在换乘时往往有多条路径可以选择,因此合理求解轨道交通清分问题是十分必要的。

现已有多种清分模型用于求解轨道交通清分问题,如理性情况清分模型、人工分账清分模型、最短路径清分模型和K条最佳路径清分模型。前三种清分模型存在明显的缺陷,因此一般采用K条最佳路径模型来求解 。这些清分模型的算法主要是对一些经典算法(如Floyd算法,Dijkstra算法等)的改进。目前,启发式算法已被成功应用到控制、规划、设计等各个领域用来求解实际问题 ,并展现出其广泛的应用前景。对于城市轨道交通网络中多条备选路径的选择算法,目前国内外已有一定研究。本文将启发式算法应用到轨道交通换乘路径的求解过程中,提出一个求解轨道交通K条最佳换乘路径的启发式算法。

1 换乘路径求解问题

1.1 问题描述

轨道交通换乘路径求解问题描述为:已知乘客在不同轨道交通线路中乘车的起始站点和目标站点,求乘客从起始站点到目标站点的乘车路径。其中换乘路径需满足以下条件:

(1)起始站点和目标站点不属于同一条线路;

(2)从起始站点到目标站点的路径必须是连通的;

(3)从起始站点到目标站点的路径中不允许有回路。

实际的轨道交通路网规模比较复杂,我们在求解轨道交通的换乘路径时需对其进行简化。

1.2 简化的轨道交通路网

简化后的轨道交通路网用有权无向图G=(V,E,C)来描述,其中:

(1)V是轨道交通路网中线路的关键站点的集合。用一组从l开始的连续自然数逐条对轨道交通线路中的不同关键站点进行编号,每个车站拥有唯一的编号。因此,V是由一组连续的自然数组成的集合。

(2)E是图中边的集合,边(i,j)表示关键站点i和j之间存在轨道交通线路。

图1 某市轨道交通运营线路

(3)权值矩阵C=[Cij]。Cij表示边(i,j)上的权值,即从车站i到车站j之间所经过的距离以及车站个数。

对轨道交通网的简化是为建立模型和提出算法服务的,如果不进行简化,对于以后的计算会非常麻烦,为了简便起见,我们对它进行简化。

2 模型建立与算法设计

2.1 建立模型

轨道交通网络可以抽象为有向赋权图的形式:

其中G为轨道交通网络的有向赋权图:V为轨道交通网络中所有站点的集合:E为连接相邻两个轨道交通站点之间路段(边)的集合;R为经过路段e的轨道交通线路集合;W为边的非负权值(距离)。为了保证轨道交通网络的连通性,可以根据一定原则将相邻轨道交通站点抽象为图中的同一节点。

2.2 算法设计

对于上述换乘路径选择模型,可以用Dijkstra算法进行求解。由于换乘所带来的时间损失是产生在轨道交通网络中两条线路相交的站点上的,而Dijkstra算法不能直接用于节点带权图的路径搜索。此外,需要结合Dijkstra算法的路径搜索过程,将发生在节点上的时间损失转移到相应的路段阻抗上。以下是轨道交通网络单路径算法的具体描述:

step0:初始化,定义拟搜索路径的起点为r,终点为S;d(i)为起点r到节点i的权值,w(i,j)为连接i、j路段的权值;定义已标记节点的集合为P,未标记节点的集合为T,R(i,j)为连接i、j的路段上的轨道交通线路集合,Re为当前使用的轨道交通线路集合。step1:对所有的节点i,如果i≠r,则d(i)=∞,将i加入未标记节点集合T;否则d(i)=0,将i加入已标记节点集合P。step 2:检验从所有已标记的点i到与其直接连接的未标记的点j的权重,令,其中,为路段距离,φ为换乘影响因子,δ为换乘开关变量,v为轨道交通车辆平均运营速度,t为平均换乘时间;如果i=r,令;否则如果空集,令;否则令,δ=0。step3:选取下一个点,从集合T中选取d（）j中最小的一个i值,对应点i被选为最短路径中的一点,将i加人集合P。step4:如果所有节点均已被标记,则转入step5;否则,转入step2。step5:算法结束,通过最优路径上路段的反向查找统计出最优路径距离或时间值、所使用轨道交通线路组合、换乘站点位置、换乘次数、经过站点数等信息。

3 案例分析

在实际的轨道交通路网模型中,关键站点之间可能存在多条路径,其边上的权值是经过相邻换乘站点之间的时间和平均站点数。图l是简化后的某市轨道交通运营线路。

边上的权值是两相邻换乘点之间的时间和所经过的站点数。上图中轨道交通线路与换乘站点之间的关系如下:1号线:11-12-13-14-15;2号线:7-8-9-14-15;4号线:2-7-12-16;5号线:1-5-8-12-17;8号线:4-18;10号线:2-3-4-5-6-10-15;13号线:7-3-1-6-9。

本文主要研究从7到10的换乘路径选择,由于从7到10的路径有很多种,一一列出不太现实,所以只抽取一部分线路进行研究,可供选择的路径有以下8条,最后得出最有路径为7—8—9—10和7—3—4—5—6—10,虽然第二条路径所经历的站点数较多,但是总时间并不比第一条多很多,两条路径相差不多,所以都可以确定为最优路径。经验证它与实际相符,如果我们要从7到10,通常会选择2号线换乘直接到达10,或者选择13号线换乘10号线到达10,这与我们正常的选择方法近似,所以认为模型是有效的。

4 结语

随着我国轨道交通的发展,换乘问题已经成为影响轨道交通建设、运营的一个重要因素。由于人们出行的需要,要为各自的出行目的选择最优的出行路径,现在大部分人都会倾向于选择乘坐轨道交通,考虑时间、距离、换乘次数等因素,换乘次数太多,以本人就会无法接受,会倾向于换乘次数较少的路径。鉴于此,本文提出了一个关于选择轨道交通换乘路径的算法,也就是通过建立简单模型而归纳的启发式算法,这种算法以前曾经也有人提过,但是本文把它应用在轨道交通换乘路径选择上来,并验证了它的可行性。