公路旅客最少换乘次数乘车方案选择算法

李志明

（石家庄市公路工程管理处，河北 石家庄 050011）

0 引言

公路旅客从始发站至终点站沿途依次乘坐的列车及换乘站序列称为旅客乘车方案[1]。在进一步提高公路客运效益的研究中，不论是评价旅客列车开行方案和列车运行时刻表对旅客需求的满足程度，还是为旅客提供中转换乘咨询服务，旅客乘车方案优化都是一个十分重要的问题[2]。旅客乘车方案选择问题是多目标优化问题[3－4]，但应注意到绝大多数旅客在选择乘车方案时，都会优先选择换乘次数少的乘车方案，而后才会进一步考虑旅行时间、票价和列车等级等因素[5]，因此旅客乘车方案优化的关键，是如何在为数众多的可能乘车方案中选出换乘次数最少的乘车方案。对于公路旅客最少换乘次数乘车方案选择问题，目前主要有两类解决方法。一类方法是以K最短路算法在路网中求解两站点间的最短中转径路集，再从最短径路集中筛选出换乘次数少的乘车方案[1]。这类方法的实质是先以距离最短、再以换乘次数最少为目标分布进行乘车方案优选，可能导致换乘次数最少但里程较长的乘车方案落选。另一类方法是先根据列车时刻表数据构建换乘网络[2]，再采用经典的最短路径算法搜索发、到站之间的最短路径[3]，但这种方法不能保证找到两站间全部的最少换乘次数乘车方案，同时算法效率有待进一步提高。

本文在现有研究基础上，提出一种基于改进广度优先搜索算法的公路旅客乘车方案选择算法。该算法可以一次搜索出给定发车、到站间全部的最少换乘次数乘车方案，且具有较高的搜索效率，能够较好地解决公路旅客乘车方案优选问题。

1 公路客运换乘网络模型

对公路客运网络进行合适的建模是研究乘车方案选择算法的基础。早期的研究多以公路区间网络为基础构建路网模型[6]，这种模型可用于求解最短乘车里程径路，但因为没有列车车次信息，所以难以用于讨论换乘问题[2]。近来的研究已经注意到：换乘现象是存在于由列车及停靠站构成的逻辑网络中的，与公路客运网络的物理结构并无直接关系[7]，因此可以直接从列车时刻表构建公路客运换乘网络研究乘车方案优选问题[2]。

公路客运换乘网络可以用三元组G进行描述：

其中，V为公路网络中所有客运站的集合；E为客运站之间连接边的集合，如果旅客可乘坐某列车从车站u直达车站v，则u、v之间存在且仅存在一条边e；Re为边e上的列车车次集合。

上述模型是一个有向无权图模型，具有以下几点特性：

a）任意两顶点之间不存在重复边；

b）边没有权值，但可以通过Re找到边e上各车次的列车等级、票价、里程等信息；

c）如果图是连通的，则任意两顶点u、v之间至少存在一条简单路径，其中所经顶点数目最少的路径对应一组换乘次数最少的乘车方案。

通过采用上述数学模型描述公路客运换乘网络，将两站之间最少换乘次数乘车方案选择问题，转换为在有向无权图中搜索两顶点间的最短路径问题。

2 乘车方案选择算法

如果令式（1）中无权图的所有边权值为1，则使用任一种经典的最短路算法（如Dijkstra算法）均可完成最短路径搜索。但对于无权图存在效率更高的最短路径搜索算法，即广度优先搜索算法[8]。本节首先给出求解换乘网络中单一最短路径的基本广度优先搜索算法，再对基本广度优先搜索算法进行改进，使之能够搜索到换乘网络中的全部最短路径。

2.1 基本广度优先搜索算法

广度优先搜索算法是无权图最短路径搜索的一种高效算法，其基本思想是从起点开始，按邻接层次顺序遍历图中的顶点直至终点，再从终点回溯即可找到起终点间的一条最短路径[8]。下面针对公路换乘网络搜索问题，给出具体的算法步骤。

基本广度优先搜索算法步骤如下：

第1步：初始化，令迭代算子k＝1；输入换乘网络无权图G、始发站顶点s和终点站顶点t；令s点的访问状态标记为Ms＝k；其余顶点i的访问状态标记为Mi＝0；

第2步：对所有M＝k的顶点i，顺序访问其邻接顶点j；

第3步：如果j＝t，则令其前驱标记Pt＝i，转第6步，否则转第4步；

第4步：如果j的访问状态标记为0，则令Mj＝k＋1，Pj＝i；

第5步：令k＝k＋1，转第2步；

第6步：从k开始通过前驱标记Pt回溯，得到从s到t的顶点序列，即为s到t的最少换乘次数乘车方案，算法结束。

2.2 改进后的广度优先搜索算法

在实际的客运换乘网络中，两站间往往存在多个换乘次数相同的乘车方案，一个完善的算法应能搜索到全部得最少换乘次数乘车方案。而基本广度优先搜索算法只能搜索到两点间的一条最短路径，因此有必要对其进行改进，使之能够搜索两点间所有的最短路径，这一点对于乘车方案选择具有重要意义。

观察基本算法，对于每一个节点，基本算法仅进行1次状态标记，并记载其前驱，最终生成单一的路径。如果把标记条件放宽，即节点可以被同一层次的前驱节点多次标记，并记载每个前驱，则可生成多条最短路径。据此可以给出改进后的广度优先搜索算法步骤。

改进广度优先搜索算法步骤如下：

第1步：初始化，令迭代算子k＝1；输入换乘网络无权图G、始发站顶点s和终点站顶点t；令s点的访问状态标记为Ms＝k；其余顶点i的访问状态标记为Mi＝0；

第2步：对所有M＝k的顶点i，顺序访问其邻接顶点j；

第3步：如果j＝t，则令E＝k＋1，转第4步；

第4步：如果j的访问状态标记Mj＝0，则令Mj＝k＋1，n＝0，＝i；如果j的访问状态标记Mj＝k＋1，则令n＝n＋1，＝i；

第5步：令k＝k＋1，如果k＝E，转第6步，否则转第2步；

第6步：从t开始通过前驱标记Pt回溯，得到从s到t的顶点序列，即为s到t的所有最少换乘次数乘车方案，算法结束。

3 算例

本文采用文献[3]中的算例验证基本算法和改进算法的正确性。

设一由6个站点构成的路网，共有6趟列车开行，各列车车次和所经过的站点序列如下：

根据上述列车开行方案，生成如图1所示的换乘网络。现要求计算出1、3站点之间的最小换乘次数乘车方案。

图1 换乘网络示意图

根据基本广度优先搜索算法，所求最短路径为1→4→3。表示从顶点1至3最少换乘次数乘车方案为：先乘列车V1从顶点1至顶点4，再乘列车V2从顶点4至顶点3，换乘次数为1，与文献[3]中计算结果相同。

根据改进广度优先搜索算法，所求最短路径为1→4→3和1→6→3，两者换乘次数均为1，都是换乘次数最少的乘车方案。可见，通过改进广度优先搜索算法，可以一次搜索出换乘网络中给定发、到站间全部的最少换乘次数乘车方案。

4 算法效率分析

公路旅客乘车方案选择算法必须具有较高的执行效率，以适应公路客运信息查询、计算机联网售票等应用系统对算法响应时间的要求。本节对基本广度优先搜索算法和改进广度优先搜索算法的效率进行分析，并与普通最短路径算法的执行效率进行比较。

根据算法复杂性理论可知[8]，如果图采用邻接矩阵的结构储存，则基本广度优先搜索算法在最不利情况下，时间复杂度是Θ（|V|2）。在采用同样的储存结构时，单源最短路径算法——Dijkstra算法的时间复杂度也是Θ（|V|2）。表面看来基本广度优先搜索算法相较Dijkstra算法在效率上并无优势，但实际应用中基本广度优先搜索算法很少在“最不利情况”下运行。这里的“最不利情况”是指遍历完整个网络才找到终点，对于全路列车构成的换乘网络而言，任意两站之间的最小换乘次数上限是5次[7]，而实际中旅客换乘次数很少超过2次[4]，因此算法实际执行效率还是很高的。

为实际验证基本广度优先搜索算法的执行效率，用全路客运换乘网络对其进行测试。在根据全路列车时刻表数据生成的换乘网络中随机挑选1000对站点，分别用基本广度优先搜索算法和Dijkstra算法搜索两站点间的最短路径。算法测试的硬件平台为Intel Centrino 1.8GHz CPU，2GB内存，编程语言为C＋＋。算法效率对比结果见图2。

图2 基本广度优先搜索算法和Dijkstra算法效率对比

从图2可以看出，基本广度优先搜索算法执行时间与换乘次数正相关，而Dijkstra算法的执行时间与换乘次数无关。这是因为Dijkstra算法（事实上对所有单源最短路径算法都是如此）在搜索起终点间的最短路径时，实质上是搜索了从起点到图中所有节点的最短路径，因此平均搜索效率远低于基本广度优先搜索算法。

进一步分析改进广度优先搜索算法的执行效率。与基本广度优先搜索算法相比，改进广度优先搜索算法仅多记录了每个节点的前驱，因此算法时间复杂度仍是Θ（|V2|）。而采用K最短路算法搜索网络中的多条最短路径时，算法的时间复杂度是Θ（K|V2|），其中K是最短路径的数量。同样使用前述换乘网络，对比测试在搜索全部最短路径时，改进广度优先搜索算法与K最短路算法的执行效率，结果见图3。

图3 改进广度优先搜索算法和K最短路算法效率对比

从图3可以看出，在搜索起终点间的多条最短路径时，改进广度优先搜索算法由于根据节点前驱回溯最短路径的实际时间开销增大，效率低于基本广度优先搜索算法，但仍远优于K最短路算法。

5 结语

本文对公路旅客最少换乘次数乘车方案选择问题进行了研究。首先建立了描述公路客运换乘网络的有向无权图模型，将两站之间最少换乘次数乘车方案选择问题，转换为在权图中搜索两顶点间的最短路径问题。然后给出求解换乘网络中单一最短路径的基本广度优先搜索算法，再对基本广度优先搜索算法进行改进，使之能够搜索到换乘网络中的全部最短路径，并通过算例验证了两种算法的正确性。通过算法效率的分析和实测，本文算法在执行效率方面明显优于传统的最短路算法和K最短路算法，适用于公路客运信息查询系统等应用系统要求。

[1]史峰，马均培，向联慧，等.客运中转径路的换乘模型及算法[J].铁道学报，1999，21（5）：1－4.

[2]史峰，邓连波.旅客换乘网络优化设计[J].铁道科学与工程学报，2004，1（1）：78－82.

[3]江南，史峰，卢红岩，等.铁路旅客乘车方案优化决策模型研究[J].铁道学报，2007，29（3）：13－18.

[4]崔炳谋，马钧培，陈光伟，等.铁路旅客旅行换乘方案优选算法[J].中国铁道科学，2007，28（6）：122－127.

[5]傅冬绵.交通系统中最少换乘算法及其实现[J].华侨大学学报：自然科学版，2001，22（4）：348－350.

[6]张彦.铁路客票中转换乘多径路选择问题的研究[J].铁道运输与经济，1997，19（8）：11－13.

[7]赵伟，何红生，林中材，等.中国铁路客运网网络性质的研究[J].物理学报，2006，55（8）：3906－3911.

[8]Weiss M A.Data structures and problem solving with C++[M].2nd ed.New Jersey: Addison Wesley,1999.511-557.