公交线路查询模型及算法.pdf

公交线路查询模型及算法 摘要 为求解已知公交网络的线路查询问题（一、二问），本文将公交站点视为顶点，相 邻两站点间线路为有向边，以抽象图代表公交网络。我们建立了非步行线路公交模型， 根据三类乘客的不同需求，分别以时间、价钱和换乘次数最小化作为目标函数，并同时 考虑仅通过公汽线路与通过公汽和地铁线路两种情况下的最优线路。在建立了数组为基 础、链表为内核的公交站点数据结构基础上，我们提供了点搜索（修改的 Dijkstra 算法） 和线路搜索两种算法，并根据资料在后者引入换乘次数上限，分别对不同目标函数用 C 语言编程加以求解。对第一问中（ 1 ）的时间最短目标，点搜索算法得最优线路 L 484 L 485 L167 S 3359 ⎯⎯⎯→S 3727 ⎯⎯⎯→S1784 ⎯⎯⎯→S1828 和最短耗时 64 分钟；线路搜索算法得 L 015 L 485 L167 最优线路S 3359 ⎯⎯⎯→S 2903 ⎯⎯⎯→S1784 ⎯⎯⎯→S1828 和最短耗时64分钟。 通过结果分析，我们认为两种算法均可在一定的范畴内搜索到最佳线路。通过算法 时间复杂度分析、结果分析和模型优缺点评价，我们肯定了点搜索算法的计算效率、理 论最优性和线路搜索算法使用递归思想的方法易懂性、实用性，也提出了模型目标单一 导致的算得结果不便实践的缺点。在灵敏度分析中我们将相邻公汽线路平均行驶时间增 大，得到与实际较为符合的结果并对前后结果进行比较分析，认为相邻公汽线路平均行 驶时间与出行交通工具的选择和换乘次数多少有密切联系。我们也在模型扩展中提出同 时选择首要和次要目标来求解，以解决单一目标的问题。 第三问中我们建立了步行线路公交模型，考虑将步行作为公交方式的一种，把所有 站点做成一个环路加入公交网络，沿用上述模型和方法。同时我们分析了数据庞大使得 算法失效的可能性，提出只使用每个站点附近步行权值的办法，并建议使用点搜索算法 求解该问题。 关键字：Dijkstra 算法，公交线路查询，点搜索，线路搜索 1 目录 问题重述 3 问题分析 3 模型一：非步行公交线路模型 3 模型分析 3 模型假