您现在的位置: 通信界 >> 工业自动化 >> 技术正文  
 
基于深度优先搜索的铁路中转路线规划研究
[ 通信界 / 郭怡然 / www.cntxj.net / 2023/7/23 18:30:06 ]
 

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

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

一、引言

随着我国铁路行业的飞速发展,铁路出行已经成为很多人出行的首选。随着高铁、动车的车次越来越多,铁路网变得愈加复杂。如何在错综复杂的铁路线路中规划出一条花费最少,或者到达时间最早,又或者是换乘次数最少的乘车方案愈发显得重要。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]

 

作者:郭怡然 合作媒体:中国新通信 编辑:顾北

 

 

 
 热点技术
普通技术 网络认知对抗的中文学术研究历史演进研究
普通技术 境外认知战作战力量及技术装备综述
普通技术 我国当前面临的主要网络认知威胁分析
普通技术 提升工业和硬件安全!我国牵头提出的两项网安国际标准发布
普通技术 6G通信感知一体化网络的感知算法研究与优化
普通技术 多地址的时间型区块链隐蔽通信方法研究
普通技术 基于CHAN 的改进卡尔曼滤波室内定位算法
普通技术 基于吸收马尔可夫链攻击图的网络攻击分析方法研究
普通技术 短波通信接入网广域协作资源分配算法
普通技术 基于子载波补给索引调制的OFDM 传输方案
普通技术 基于随机Transformer 的多维时间序列异常检测模型
普通技术 面向高混响环境的欠定卷积盲源分离算法
普通技术 移动边缘计算网络下基于静态贝叶斯博弈的入侵响应策略研究
普通技术 基于IRS辅助的MIMO车联网系统联合波束成形设计
普通技术 基于IOC-CSMP 的OFDM 系统稀疏信道快速重构算法
普通技术 频控阵MIMO雷达的目标数与方位参数联合估计方法
普通技术 SPS 结构大规模S 盒设计与分析
普通技术 意图抽象与知识联合驱动的6G 内生智能网络架构
普通技术 软件定义网络抗拒绝服务攻击的流表溢出防护
普通技术 数据安全中台构筑企业数据生命线
  版权与免责声明: ① 凡本网注明“合作媒体:通信界”的所有作品,版权均属于通信界,未经本网授权不得转载、摘编或利用其它方式使用。已经本网授权使用作品的,应在授权范围内使用,并注明“来源:通信界”。违反上述声明者,本网将追究其相关法律责任。 ② 凡本网注明“合作媒体:XXX(非通信界)”的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。 ③ 如因作品内容、版权和其它问题需要同本网联系的,请在一月内进行。
通信视界
吴春波:华为如何突破美国6次打压的逆境?
刘烈宏:以数字化网络化智能化助力数字经济与
普通对话 高通中国区董事长孟樸:5G与AI结合,助力提升
普通对话 雷军发布小米年度演讲:坚持做高端,拥抱大模
普通对话 闻库:算网融合正值挑战与机遇并存的关键阶段
普通对话 工信部副部长张云明:我国算力总规模已居世界
普通对话 邬贺铨:我国互联网平台企业发展的新一轮机遇
普通对话 张志成:继续加强海外知识产权保护工作 为助力
普通对话 吴春波:华为如何突破美国6次打压的逆境?
普通对话 刘烈宏:以数字化网络化智能化助力数字经济与
普通对话 消息称微软将把OpenAI人工智能技术整合至Offi
普通对话 中国电信董事长柯瑞文:数字科技引领新消费
普通对话 中国移动董事长杨杰出席GSMA创新论坛并作主旨
普通对话 中国信科何书平:“一体两翼”大力支撑数字政
普通对话 中兴徐子阳:泛在协同,筑“算网”坦途
普通对话 中国移动陈国:智慧中台对外输出数百项高价值
普通对话 中兴通讯总裁徐子阳:数贯东西,融达天下,共
通信前瞻
亨通光电实践数字化工厂,“5G+光纤”助力新一
邬贺铨院士解读ChatGPT等数字技术热点
普通对话 亨通光电实践数字化工厂,“5G+光纤”助力新一
普通对话 中科院钱德沛:计算与网络基础设施的全面部署
普通对话 工信部赵志国:我国算力总规模居全球第二 保持
普通对话 邬贺铨院士解读ChatGPT等数字技术热点
普通对话 我国北方海区运用北斗三号短报文通信服务开展
普通对话 华为云Stack智能进化,三大举措赋能政企深度用
普通对话 孟晚舟:“三大聚力”迎接数字化、智能化、低
普通对话 物联网设备在智能工作场所技术中的作用
普通对话 软银研发出以无人机探测灾害被埋者手机信号的
普通对话 AI材料可自我学习并形成“肌肉记忆”
普通对话 北斗三号卫星低能离子能谱仪载荷研制成功
普通对话 为什么Wi-Fi6将成为未来物联网的关键?
普通对话 马斯克出现在推特总部 收购应该没有悬念了
普通对话 台积电澄清:未强迫员工休假或有任何无薪假计
普通对话 新一代载人运载火箭发动机研制获重大突破