基于列车时刻表的服务路径搜索算法研究与系统开发

摘要

近年来，我国高速铁路发展迅速，路网规模不断扩大结构愈加复杂，路网中的旅客列车数量也在不断增加，导致路网中服务路径搜索的复杂度迅速增加，如何快速高效地搜索出合理的服务路径就成为客运产品与服务设计中的重要问题。
　　本文针对基于时刻表的服务路径的搜索问题，研究了服务网络的简化、服务路径的合理性等问题，进而实现了单一OD服务路径搜索算法和全路OD服务路径搜索算法，以期满足铁路运营管理部门及出行旅客的需求，提高高速铁路市场核心竞争力。
　　论文首先分析了国内外服务网络构建及路径搜索算法研究现状，研究了基于列车时刻表的服务网络的定义及构造方法，明确了物理网络与服务网络间的关系，分析了服务网络的特点，并提出了服务网络的简化方法及计算机模型。
　　针对服务网络规模大、服务路径数量多的特点，论文进一步针对服务路径的合理性展开研究，明确合理路径的定义并提出典型的4种不合理路径，据此归纳影响旅客对路径合理性判断的各类因素，深入分析探讨给出各类阈值参数。
　　在上述研究的基础上，论文以双向A*算法和广度优先算法为基础，综合运用物理网络K短路、并行算法及判断路径合理性的各类业务规则，分别设计了单一OD服务路径实时动态求解算法和全路OD服务路径一次性全搜索两类算法，实现了基于时刻表的服务网络中的服务路径快速搜索。
　　最后根据本文研究所得算法，实现基于列车时刻表的服务路径搜索与表达系统，以出行时间最短、换乘次数最少、换乘时间最短等目标进行展示，并以不同等级、不同地域、不同距离下的OD进行案例分析，说明系统的适用性与算法的可行性。

目录

声明

致谢

摘要

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 出行网络构建现状

1．2．2 影响旅客出行因素

1．2．3 出行路径求解算法

1．2．4 研究现状总结

1．3 主要研究内容及技术路线

1．3．1 研究内容

1．3．2 技术路线

2 基于列车时刻表的客运服务网络构造及表达

2．1 基于列车时刻表的服务网络概述

2．2 基础物理网络构造

2．2．1 基础物理网络设计

2．2．2 基础物理网络简化

2．3 基于列车时刻表的服务网络构造

2．3．1 服务网络基本设计方法

2．3．2 服务网络特点分析

2．3．3 服务网络的简化

2．4 计算机模型表达

2．4．1 图论定义及其存储表示

2．4．2 基础物理网络抽象表达

2．4．3 列车时刻表服务网络抽象表达

2．5 本章小结

3 合理服务路径概述

3．1 合理路径定义及影响要素

3．2 常见不合理路径特点分析

3．2．1 “回头’’换乘

3．2．2 “过多”换乘

3．2．4 “过长”换乘

3．3 合理路径的判别方法

3．3．1 时间相关因素

3．3．2 服务频率因素

3．3．3 距离相关因素

3．4 本章小结

4 路径搜索算法研究

4．1 路径搜索算法求解描述

4．1．1 路径求解算法流程

4．1．2 算法核心问题说明

4．2 基于双向A*的动态限制区域“点到点’’搜索算法

4．2．1 K短路算法选择分析

4．2．2 双向A*算法选择性分析

4．2．3 算法基本思想

4．2．4 直达路径搜索算法

4．2．5 换乘路径算法

4．2．6 约束原则

4．3 基于广度优先的并行服务路径全搜索算法

4．3．1 广度优先搜索选择性分析

4．3．2 并行算法选择性分析

4．3．3 算法基本思想

4．3．4 算法实现

4．3．5 约束原则

4．4 本章小结

5 路径搜索系统实现及案例分析

5．1 路径搜索系统实现

5．1．1 需求分析

5．1．2 开发与运行环境简介

5．1．3 系统实现

5．2 系统测试与案例分析

5．2．1 测试环境与指标

5．2．2 测试案例

5．3 本章小结

6．1 研究结论

6．2 研究展望

参考文献

附录

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集