基于深度优先搜索的铁路中转路线规划研究

摘要：目前，许多长距离铁路出行没有直达列车，或直达列车绕路，导致额外的时间和金钱花费。本文针对这一现象，将复杂的铁路路线数据抽象成计算机方便处理的图，使用带有剪枝优化的深度优先搜索算法，对可能的乘车中转方案进行遍历，根据不同目标（如花费最少、耗时最短、到达时间最早等）挑选出不同中转方案，供用户出行参考。根据软件设计的原则和方法，给出了使用实现该算法的系统的设计。

关键词：铁路中转方案；深度优先算法；剪枝优化；软件系统设计

一、引言

随着我国铁路行业的飞速发展，铁路出行已经成为很多人出行的首选。随着高铁、动车的车次越来越多，铁路网变得愈加复杂。如何在错综复杂的铁路线路中规划出一条花费最少，或者到达时间最早，又或者是换乘次数最少的乘车方案愈发显得重要。12306 官方网站提供的各种换乘方案无法让用户自己设定最早出发时间，最晚到达时间，以及最小换乘时间的限制，而且最多只能换乘一次，灵活性受限。提供的换乘方案又多又杂，用户体验不好。

本文以开发一个能够帮助用户更加灵活地规划乘车方案的系统为目标，弥补 12306 官网提供的服务的缺点，支持用户自己定制各种条件，包括最早出发时间、最晚到达时间、最小换乘时间、最大换乘次数。为用户规划出行路线提供一定参考。

二、算法设计

算法主要分为两部分，一部分是根据铁路数据构建出图，另一部分是在图上进行搜索。

（一）构建图

将每个站点抽象成点，两个站点之间的铁路线路抽象成边。设计站点的数据结构如下，后期可以方便地进行属性的添加。设计路线的数据结构如下，维护了始发站、终点站、始发时间、到达时间、座位类型（二等座/硬座）、价格、编号等信息。

采用邻接表数据结构存储图，即对于每个站点Station，存储离开它的所有线路，图的数据结构如图1：

为了方便剪枝和输出最终方案，创建方案的数据结构如下，即维护花费、到达时间、总用时、与期望时间差异程度等各项评价参数：

方法：betterInAllAspects和atLeastBetterInOneAspect，分别用于对其他方案进行剪枝和决定是否对当前方案剪枝。

（二）图的搜索

常用的搜索算法主要有两类，深度优先和广度优先。广度优先可以保证第一次搜索到站时可以保证在某方面最优，但空间复杂度较大。由于本系统是需要提供多个不同指标最优化的方案，因此广度优先的这个性质并不能很好地被利用。同時考虑到图的点数和边数较多，因此选用空间复杂度较小的深度优先搜索算法来实现。

算法核心流程：构建一个Traveler对象模拟各种乘车方案，具体来讲，当traveler到达某个站点后，看一下在当前时间所有可以乘坐的车次，依次尝试各个可以乘坐的车次，同时更新花费和到达时间，到达下一个车站后重复上述过程。当到达一个车站发现没有任何一辆车次可以乘坐，则回退到上一个车站尝试其他车次，具体实现如下：

// 尝试从当前站乘车

for （Line line ： graph.map.get（currentStation.id）） {

if （！path.empty（） && ！path.peek（）.id.equals（line.id） &&

（line.startTime.getTime（） - currentDate.getTime（）） <

（long） minMinutesForSameStationTransfer * 60 * 1000）

continue;

if （line.startTime.compareTo（currentDate） < 0） continue; // 防止跨天

// 更新换乘次数

int newTransferTimes = transferTimes;

if （！path.isEmpty（） && ！（path.peek（）.id）.equals（line.id）） newTransferTimes++;

if （newTransferTimes > maxTransferTimes） continue;

path.push（line）;

travel（line.endStation， line.endTime， currentCost + line.price， newTransferTimes）;

path.pop（）;

}

（三）剪枝优化

为了缩短用户查询时间，需要对上述算法进行优化。通过之前定义的Scheme数据结构可以方便地对搜索过程进行剪枝。剪枝可以分为两部分，一部分根据用户的限制条件进行剪枝，例如当前时间已经超出用户设置的可以接受的最晚到达时间，则没有必要继续扩展当前搜索子树。另一种是通过和历史经过该站点的方案进行比较，如果当前方案在所有方面均比历史方案差，则没有必要在此方案的基础上继续尝试。

（四）方案评价与复杂度分析

曾考虑过效率更高的动态规划算法，但为了更高的灵活性和可扩展性以及易实现性选用了搜索算法。搜索算法在最坏情况下时间复杂度将是指数级别。但由于乘车问题具有时间限制其复杂度远远低于指数。在最初测试时对于用户查询大概可以在几分钟内返回结果。这样的表现显然不尽如人意。于是采用“剪枝”对算法进行优化，优化之后，通过测试，平均可以在5s内可以返回查询结果。

三、系统设计

本文所设计的系统是一个后端系统，为前端提供查询服务接口，主要借助Spring平台。

系统分为四个模块：数据获取模块、核心算法处理模块、数据库交互模块、WEB模块。各模块之间的依赖关系如图3。

WEB模块负责处理前端发送的请求，将请求传递给算法处理模块，并将处理结果返回给前端。

核心算法模块在初始化时从数据库中将铁路路线信息加载进内存，接受请求，通过搜索，将结果返回给WEB模块。

数据库交互模块使用Mybatis框架，负责将数据库数据映射成Java对象。

数据获取模块使用并发优秀的WebMagic框架，负责访问接口获取铁路信息，并将信息存入数据库。同时使用Spring Task做定时任务框架，每日定时更新铁路信息。

同时系统采用分布式架构，各个服务之间使用Dubbo进行通信。整个系统的部署图如图4。

四、结论

基本实现了预期功能。

五、解决方案持有的问题

①暂时无法提供跨天乘车方案，一是因为数据不充足，二是算法处理时间较长，无法在5s内返回用户想要的方案。

②虽然在爬虫系統方面采取种种措施保证数据完整性，但还会丢失0.2%的数据。难以在数据完整性和爬取速度方面达到平衡。

③由于采用将整条路线拆分成一段段的路径类和求花费，使用这种方案计算出的价格和实际价格可能有0.5元或者1元的误差。

六、后续研究方向

①增加跨天乘车方案的功能。

②加强对数据获取的控制，争取达到更高的数据完整性和更快的获取速度。

作者单位：郭怡然 重庆市重庆邮电大学2019级软件工程学院

参  考  文  献

[1]林开钦，白羽，王倩，柴强. 一种改进的星间链路深度优先路由搜索算法[C]//第十二届中国卫星导航年会论文集——S06 时间基准与精密授时.[出版者不详]，2021：98-101.DOI：10.26914/c.cnkihy.2021.002192.

[2]https：//redis.io/documentation [2021.10.2]

[3]https：//www.rabbitmq.com/getstarted.html [2021.10.3]

[4]https：//dubbo.apache.org/zh/docs/ [2021.10.5]

[5]http：//webmagic.io/docs/zh/ [2021.10.1]