07年高教社杯全国大学生数学建模竞赛B题.pdfVIP

1 2007 高教社杯全国大学生数学建模竞赛 B 题 【摘要】 本文根据人们出行习惯、 情绪等特点 , 确定任意两站点之间的最佳线路的模 型和算法。在只考虑公汽的情况下，在以换乘次数最小为主要因素 , 通过建立换 乘次数及线路选择模型 , 在要求时间，费用最小的条件下，通过进行权重分析， 建立最小花费函数，从而得到最佳路线。通过运用广度优先遍历算法和 MATLAB 编程，由已知的数据运算得到任意给定两站点之间的所有线路选择及其最优线 路。 在同时考虑地铁、公汽线路时，沿用此模型思想、算法确定最佳路线。 假设又考虑步行时间，可通过建立最小路径成本模型，运用最优路径改进算 法，确定最优路线。 最后针对对所作的模型、算法进行评价与推广，提出可行有效的改进如 Dijkstra 算法。 【关键词】：公交 最小换乘次数 广度优先遍历 最佳路线 2 一、 问题重述 这些年来，城市的公交系统有了很大发展， 使得公众的出行更加通畅、 便利， 但同时也面临多条线路的选择问题。 如何从实际情况出发考虑， 满足查询者的各 种不同需求。 现需要解决的问题如下： 分别在只考虑公交线路， 同时考虑公交与地铁， 或 同时考虑已知站点之间的步行时间的情况下确定其最佳路线。 （1）、仅考虑公汽线路， 任意两公汽站点之间线路选择问题的一般数学模型与算 法。并根据附录数据， 在只考虑公交线路的情况下， 求出以下 6 对已知站点之间 的最佳路线（要有清晰的评价说明） 。 (1) 、S3359 S1828 (2) 、S1557 S0481 (3) 、 S0971 S0485 (4) 、 S0008 S0073 (5) 、 S0148 S0485 (6) 、 S0087 S3676 二、 问题分析 实现公交网络查询系统的最优路径查询的重点在于如何实现查询者的个人 满意度最高的问题。 在公交换乘的过程中， 有多种优先策略考虑。 比如换乘次数最少、 费用最少、 时间最短等。 每个人考虑的重要因素不同， 但大多数人对换乘次数的多少比较在 意，因此我们考虑用基于换乘次数最少的公交换乘优先策略， 其次考虑时间最短， 最后考虑费用最少，这比较符合大众出行时的心理情况。 对于只考虑公交换乘方案的问题一， 则可依次寻找两站点间是否存在直达线 路、一次换乘线路、二次换乘线路等直达线路一致，有结果则输出。若二次换乘 仍没有结果则输出“没有找到换乘次数少于 2 次的最优换乘方案” ，结束运算。 对于问题二， 需同时考虑公交与地铁线路， 考虑到目前大众心理对地铁的便 利性、快捷性的认同感，在考虑了换乘次数最少的情况下可优先考虑地铁换乘， 其次再考虑公交换乘， 其目的在于将行程的最大时间消耗不妨利用地铁的快捷减 少时间上的损耗。 对于问题三，在已知站点间的步行时间的条件下，对环行路线的影响较大， 我们可只考虑环行路线。 三、模型的假设和符号说明 3 （一）模型的假设：