最优公交线路选择模型

1 最优公交线路选择模型最优公交线路选择模型 摘摘 要要 本文讨论了公众出行时多条线路选择的问题 给出了在已知公交系统中任 意两公交站点之间线路选择的模型和算法 使得出行时的时间 费用和换乘次 数都尽量的少 在问题 1 中 我们仅考虑公汽线路 将 520 条公汽线路信息读入到两个矩 阵当中 利用矩阵表示站点间的直达经过站数和线路 用 matlab 编程求解分别 得到换乘 1 次和换乘 2 次时 6 对起始站 终到站之间的最佳路线 仅在此给出 S3359 S1828 的最佳路线 其余结果见正文 表 1 换乘 1 次时 S3359 S1828 的最优线路方案 起点站终点站线路 1中转站线路 2时间 分 费用 元 S3359S1828L436 下 S1784L167 下 1013 表 2 换乘 2 次时 S3359 S1828 的最优线路方案 起点站终点站线路 1 中转站 1 线路 2 中转站 2 线路 3时间费用 S3359S1828L015 下 S2903 L027 环 S1784 L167 下 733 问题 2 要求同时考虑公汽与地铁线路 我们首先将增加的地铁线路信息添 加到问题 1 建立的两个矩阵中 利用与问题 1 相似的编程思路 求解得到换乘 1 次和换乘 2 次时 6 对起始站 终到站之间的最佳路线 S3359 S1828 的最佳 路线与问题 1 的相同 其余结果见正文 问题 3 要求同时考虑公汽 地铁和步行 我们建立了全局替换模型和局部 替换模型 最后我们对模型进行了推广 给出了线路 满载度 的定义 在考虑 满 载度 之后 建立了新的模型 关键词 关键词 多目标规划多目标规划 最少时间最少时间 相关矩阵相关矩阵 满载度满载度 2 一 问题提出一 问题提出 我国人民翘首企盼的第 29 届奥运会明年 8 月将在北京举行 届时有大量观 众到现场观看奥运比赛 其中大部分人将会乘坐公共交通工具 简称公交 包 括公汽 地铁等 出行 这些年来 城市的公交系统有了很大发展 北京市的 公交线路已达 800 条以上 使得公众的出行更加通畅 便利 但同时也面临多 条线路的选择问题 针对市场需求 某公司准备研制开发一个解决公交线路选 择问题的自主查询计算机系统 为了设计这样一个系统 其核心是线路选择的模型与算法 应该从实际情 况出发考虑 满足查询者的各种不同需求 请你们解决如下问题 1 仅考虑公汽线路 给出任意两公汽站点之间线路选择问题的一般数学模型与 算法 并根据附录数据 利用你们的模型与算法 求出以下 6 对起始站 终到 站之间的最佳路线 要有清晰的评价说明 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S3676 2 同时考虑公汽与地铁线路 解决以上问题 3 假设又知道所有站点之间的步行时间 请你给出任意两站点之间线路选择问 题的数学模型 附录 1 基本参数设定 相邻公汽站平均行驶时间 包括停站时间 3 分钟 相邻地铁站平均行驶时间 包括停站时间 2 5 分钟 公汽换乘公汽平均耗时 5 分钟 其中步行时间 2 分钟 地铁换乘地铁平均耗时 4 分钟 其中步行时间 2 分钟 地铁换乘公汽平均耗时 7 分钟 其中步行时间 4 分钟 公汽换乘地铁平均耗时 6 分钟 其中步行时间 4 分钟 公汽票价 分为单一票价与分段计价两种 标记于线路后 其中分段计价的票 价为 0 20 站 1 元 21 40 站 2 元 40 站以上 3 元 地铁票价 3 元 无论地铁线路间是否换乘 注 以上参数均为简化问题而作的假设 未必与实际数据完全吻合 附录 2 公交线路及相关信息 见数据文件 B2007data rar 3 二 问题假设二 问题假设 1 假设题目给定的公交线路均合理有效 2 假设题目中所给的基本参数合理有效 不会对最终结果的准确性造成影响 3 假设不存在因公汽或地铁满载 使公交到站后 等车的乘客无法上车的情况 4 假设公交行驶过程中不受地形 天气 路况和上车人数的影响 相邻公交站 的平均行驶时间 包括停站时间 固定不变 5 假设乘客选择乘车路线时仅考虑三个因素 时间 费用和换乘次数 6 假设每个乘客从出发地到达目的地最多乘坐 3 辆公交车 在能够到达的情况 下 7 假设环行的公汽没有始发站和终点站 在客观情况允许的情况下 会绕着环 行线路一直开下去 即乘客上车后无需下车再乘 就可以从环行线路的一站 到达环行线路其他任意站 8 假设地铁直接换乘地铁时只需购买一次地铁票 花费 3 元 当地铁换乘公汽 后再换乘地铁时需要购买两次地铁票 花费 6 元 三 符号约定三 符号约定 仅考虑公汽线路时 从公汽站 i 到公汽站 j ij 直达 只乘坐一辆公交 ij a 就可到达 行驶所经过最少的路段 相邻两公交站的路程称为一个路段 数目 当不能直达或 i j 时 0 ij a 仅考虑公汽线路时 从公汽站 i 到公汽站 j 直达行驶所经过最少的路段数 ij b 目的公汽线路 当不能直达或 i j 时 0 ij b A 公交站点相关矩阵 其中存放元素 ij a B 直达公交线路矩阵 是矩阵 A 的对应矩阵 其中存放元素 ij b 从起点到终点所利用的公交线路总数 n 换乘的次数 s n 1 s 乘客第 k 次乘坐公交时所乘坐的站数 由假设 6 知 k 可取 1 2 3 k m 乘客第 k 次乘坐公交时所需要的费用 由假设 6 知 k 可取 1 2 3 k P 从起点 i 到终点 j 的所需要的时间 ij T 4 从起点 i 到终点 j 的所需要的费用 ij P 相邻公汽站平均行驶时间 包括停站时间 t汽 相邻地铁站平均行驶时间 包括停站时间 t铁 公汽换乘公汽平均耗时 t汽汽 地铁换乘地铁平均耗时 t铁铁 地铁换乘公汽平均耗时 t铁汽 公汽换乘地铁平均耗时 t汽铁 同一地铁站对应的两公汽之间通过地铁站换乘的平均耗时 t汽铁汽 四 问题分析四 问题分析 奥运会明年 8 月将在北京举行 届时有大量观众到现场观看奥运比赛 其 中大部分人将会乘坐公共交通工具 简称公交 包括公汽 地铁等 出行 这 些年来 城市的公交系统有了很大发展 北京市的公交线路已达 800 条以上 使得公众的出行更加通畅 便利 但同时也面临多条线路的选择问题 怎样才 能在众多的公交线路中找出既省时又省钱的公交线路 是人们所关心的问题 此文即要求给出线路选择的模型与算法 从实际情况出发考虑 满足乘客的各 种不同需求 4 1 问题问题 1 的分析的分析 仅考虑公汽线路 某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统 为了设计这样一个系统 其核心是线路选择的模型与算法 应该从实际情况出 发考虑 满足查询者的各种不同需求 问题 1 要求在仅考虑公汽线路的情况下 给出任意两公汽站点之间线路选择的一般数学模型与算法 在文本文档公汽线 路信息中一共给出了 520 条公汽线路 3957 个公汽站点 乘客选择乘车路线时 主要考虑三个方面的因素 时间 费用和换乘次数 三者之间是既有联系又有 区别的 一般情况下 换乘次数比较少时所用的时间也比较少 同时花费的费 用也比较少 换乘次数比较多时所用的时间也比较多 同时花费的费用也比较 多 但也不排除换乘次数多时花费的时间反而比较少的情况 考虑到人们的心 理因素 人们对换乘次数有一个最大的承受上限 不能无限制的换乘下去 所 以我们限定最大换乘次数为 2 即最多利用 3 条公交线路从起点站到达终点站 即使换乘次数大于 2 时存在需要时间和费用更少的路线我们也不再考虑 其实 我们有理由相信这种事件的概率是非常小的 甚至是不存在的 所以我们先建 立模型 搜索出换乘次数小于或等于 2 的所有的可行线路 再分别计算出这些 5 线路学要的时间和费用 根据乘客不同的需求 即不同的目标函数 选择最优 解 从起点 i 到终点 j 的所需要的总时间由两部分构成 一是公交的行驶时 ij T 间 二是乘客换乘时的耗时 包括换乘时的步行时间和等待时间 公交的行驶 时间等于相邻站点间的平均行驶时间乘以公交行驶的站数 即 多次换 k tm 汽 乘时 只要将每次乘坐的行驶时间求和即可 即 乘客换乘时的耗时 1 n k k tm 汽 等于换乘次数乘以每次换乘所需的时间 即 所以总的耗时可以用下s t 汽汽ij T 面的表达式来表示 1 n ijk k Tmts t 汽汽汽 乘客从起点 i 到终点 j 的所需要的总费用为乘坐每一辆公交所需费用的 ij P 加和 乘坐公汽时的收费分为两种情况 一种是单一票价的 无论乘坐多少站 均收费 1 元 另一种是分段计价 分段计价的票价为 0 20 站 1 元 21 40 站 2 元 40 站以上 3 元 将收费方式用数学表达式表示可写成以下的形式 1 20 k k k P m k 乘客第次乘坐的公汽为单一票价时 乘客第次乘坐的公汽为分段计价时 其中 表示对上取整 即取不小于的最小整数 乘客从起点 i 到终 20 k m 20 k m 20 k m 点 j 的所需要的总费用为乘坐每一辆公交所需费用的加和 即 ij P n k 1 ijk PP 4 2 问题问题 2 的分析的分析 同时考虑公汽与地铁线路 问题 2 在问题 1 的基础上增加了地铁线路 乘车时间和乘车费用的表达式 都将改变 在从起点 i 到终点 j 的所需要的总时间由三部分构成 一是公交 ij T 的行驶时间 二是乘客换乘时的耗时 包括换乘时的步行时间和等待时间 三 是当起始站和终点站乘车为地铁时需要先由公汽站进地铁站或从地铁站走到公 汽站点的步行时间 这个步行时间我们定义为修正时间 而在中途遇到进地铁 的情况则没有修正时间 因为步行时间已经包含在换乘时间内 公交的行驶时 间等于相邻站点间的平均行驶时间乘以公交行驶的站数 但公交此时分为公汽 和地铁 而且两者相邻站点间的平均行驶时间不同 为和 每一次乘坐公t汽t铁 交的行驶时间可表示为以下形式 6 k k k mtk T mtk 汽 铁 行 乘客第次乘坐的公交为公汽时 乘客第次乘坐的公交为地铁时 换乘也存在 5 种情况 5 种换乘的时间分别为 和 t汽汽t铁铁t铁汽t汽铁t汽铁汽 每一次的换乘时间表示如下 k tk tk Ttk tk tk 汽汽 铁铁 铁汽 汽铁 汽铁汽 换 乘客第次换乘为公汽换乘公汽时 乘客第次换乘为地铁换乘地铁时 乘客第次换乘为地铁换乘公汽时 乘客第次换乘为公汽换乘地铁时 乘客第次换乘为公汽换乘公汽需通过地铁时 修正时间可表示如下 10 6 0 T 修正 当初始乘车为地铁 最终乘车也为地铁时 当初始乘车为地铁 最终乘车为公汽时 4 当初始乘车为公汽 最终乘车为地铁时 当初始乘车为公汽 最终乘车也为公汽时 总的耗时可以用下面的表达式来表示 ij T 1 11 nn ijkk kk TTTT 行换 修正 乘客从起点 i 到终点 j 的所需要的总费用为乘坐每一辆公交所需费用的 ij P 加和 乘坐公汽时的收费分为两种情况 一种是单一票价的 无论乘坐多少站 均收费 1 元 另一种是分段计价 分段计价的票价为 0 20 站 1 元 21 40 站 2 元 40 站以上 3 元 乘坐地铁时单一票价 3 元 无论地铁线路间是否 换乘 将两种收费方式用数学表达式表示可写成以下的形式 1 20 k k k m k P k k 乘客第次乘坐的公交为单一票价的公汽时 乘客第次乘坐的公交为分段计价的公汽时 3乘客第次乘坐的公交为地铁且为公汽换乘的地铁时 0乘客第次乘坐的公交为地铁且为地铁换乘的地铁时 其中 表示对上取整 即取不小于的最小整数 乘客从起点 i 到终 20 k m 20 k m 20 k m 点 j 的所需要的总费用为乘坐每一辆公交所需费用的加和 即 ij P n k 1 ijk PP 7 4 3 问题问题 3 的分析的分析 考虑公汽 地铁和步行 问题 3 要求同时考虑公汽 地铁和步行三种情况 对这个问题 我们建立 两种不同的模型 模型 1 的核心思路是将所有站点之间的步行时间信息添加到 问题 2 的矩阵 A B 当中 利用问题 2 中的算法直接求解 模型 2 的核心思路 是直接利用问题 2 中所求得的结果 利用步行信息对其结果进行分析 改进 五 问题一的建模与求解五 问题一的建模与求解 5 1 模型的建立模型的建立 问题 1 要求在仅考虑公汽线路的情况下 给出任意两公汽站点之间线路选 择的一般数学模型与算法 乘客选择乘车路线时主要考虑三个方面的因素 换 乘次数 时间和费用 三者之间是既有联系又有区别的 一般情况下 换乘次 数比较少时所用的时间也比较少 同时花费的费用也比较少 但也存在换乘次 数多时需要的时间和费用反而比较少 而换乘次数少时需要的时间和费用反而 比较多的情况 考虑到人们的心理因素 人们对换乘次数有一个最大的承受上 限 不能无限制的换乘下去 所以我们限定最大换乘次数为 2 即从起点站到 达终点站最多利用 3 条公交线路 即使换乘次数大于 2 时存在时间和费用更少 的路线我们也不再考虑 从起点 i 到终点 j 的所需要的总时间由两部分构成 一是公交的行驶时 ij T 间 二是乘客换乘时的耗时 公交的行驶时间等于相邻站点间的平均行驶时间 乘以公交行驶的站数 即 多次换乘时 只要将每次乘坐的行驶时间求和 k tm 汽 即可 即 乘客换乘时的耗时等于每次换乘所需的时间乘以换乘次数 1 n k k tm 汽 即 所以总的耗时可以用下面的表达式来表示 s t 汽汽ij T 1 n ijk k Tmts t 汽汽汽 其中为从起点到终点所利用的公交线路总数 为乘客第 k 次乘坐公交n k m 时所乘坐的站数 由假设 6 知 k 1 2 3 为相邻公汽站平均行驶时间 包t汽 括停站时间 为换乘的次数 s n 1 为公汽换乘公汽平均耗时 由题目st汽汽 中的基本参数知 3 分钟 5 分钟 代入数据得 t汽t汽汽 1 35 n ijk k Tms 乘客从起点 i 到终点 j 的所需要的总费用为乘坐每一辆公交所需费用的 ij P 加和 乘坐公汽时的收费分为两种情况 一种是单一票价的 无论乘坐多少站 8 均收费 1 元 另一种是分段计价 分段计价的票价为 0 20 站 1 元 21 40 站 2 元 40 站以上 3 元 将两种收费方式用数学表达式表示可写成以下的 形式 1 20 k k k P m k 乘客第次乘坐的公汽为单一票价时 乘客第次乘坐的公汽为分段计价时 其中 表示对上取整 即取不小于的最小整数 如 26 时 20 k m 20 k m 20 k m k m 2 乘客从起点 i 到终点 j 的所需要的总费用为乘坐每一辆公交所需费 20 k m ij P 用的加和 即 n k 1 ijk PP 选择最优公交线路的目标有三个 一为乘车时间最少 二为需要费用最少 三为换乘次数最少 即利用的公交线路数最少 所以我们可以建立如下模型建立如下模型 1 n k 1 min35 min min n ijk k ijk Tms PP n s t 13 1 02 1 20 k k k n m s k P m k 乘客第次乘坐的公汽为单一票价时 乘客第次乘坐的公汽为分段计价时 其中为从起点到终点所利用的公交线路总数 为乘客第 k 次乘坐公交n k m 时所乘坐的站数 由假设 6 知 k 可取 1 2 3 为换乘的次数 s n 1 为s k P 乘客第 k 次乘坐公交时所需要的费用 通过分析乘坐公汽时的两种收费分方式 我们可以得到感性的认识 乘车 时间和乘车费用是相互关联的 多数情况下 乘车时间越多 所需要的费用就 越多 即两个目标是统一的 但也不排除在个别情况下 所用时间最少时 所 9 需费用并不是最少的 出现这种情况的主要原因有两个 一是由于单一票价的 收费形式 当乘坐单一票价的公交时 可能已经乘坐了很多站 用了很多时间 但费用却并没有相应的增加 类似的乘坐分段计价的公交时 如乘坐 020 站 时 费用均为 1 元 费用也没有和时间同步增长 5 2 模型的求解模型的求解 对该模型我们可以直接全局搜索出时间和价格的最优解 但直接搜索算法 需要大量的时间 而且得到的单一解不利于我们对问题进行分析 同时这样做 也是没有必要的 所以我们首先对换乘次数进行限制 首先搜索是否有路线可 以直接从起点到达终点 如果没有直达线路 再搜索通过 1 次换乘 利用 2 条 线路是否可以到达 有几种方案可以到达 分别计算出每种方案所需的时间和 费用 从中选取最优方案 如果通过 1 次换乘仍不可以从起点到达终点 则搜 索通过 2 次换乘 利用 3 条线路是否可以到达 有几种方案可以到达 分别计 算出每种方案所需的时间和费用 从中选取最优方案 我们假设通过 2 次换乘 仍不可以从起点到达终点的情况是不存在的 因为题目中已说明这些年来 北 京的城市公交系统有了很大的发展 已经比较完善 对于一个完善的公交系统 我们有理由假设通过两次换乘 利用 3 条公交线路 可以连接任意两公汽站点 而且数据文件所给出的公交线路信息中一共有 3957 个公汽站点 由 520 条公汽 线路相互连接 由概率论的知识我们也可以假设通过 2 次换乘仍不可以从起点 到达终点的情况是不存在的 当然以上假设是我们从感性认识和定性分析中得 到的 此假设不成立的情况也是有可能存在的 但存在的可能性是非常小的 可能对于极个别的某两个站点不成立 但对于绝大多数站点是一定成立的 此 绝大多数的概率几乎为 1 还有一个要解决的问题是如果某两个站点之间通过 1 次换乘可以到达 我 们是否有必要再搜索通过 2 次换乘的到达方案 通过分析数据可以知道换乘 2 次的方案有可能比换乘 1 次的方案所需的时间和费用都更少 所以我们有必要 在换乘 1 次已经找到可行方案后任然搜索换乘 2 次的方案 然后在这所有的方 案中选择最优解 但同样的 换乘 3 次的方案也有可能比换乘 1 次或 2 次的方 案所需的时间和费用更少 但我们是否也要将换乘 3 次甚至换乘 3 次以上的方 案统统搜索一遍呢 我们认为没有必要这么做 原因如下 1 每将换乘次数增 加 1 算法的时间复杂度将成倍增长 2 当换乘已经达到两次后 再增加换乘 次数对时间和费用的减少的帮助已经不大 3 考虑到乘客的心理因素 人们对 换乘次数有一个最大的承受上限 不能无限制的换乘下去 我们认为乘坐 3 辆 车从一个地方到另一个地方还是可以接受的 但要乘坐 4 辆车 对一般的乘客 而言是难以接受的 综上我们将搜索起点到终点之间所有的利用 1 条线路 2 条线路和 3 条线路的达到方案 在其中选取最优方案 以下将对求解过程进行 具体的说明 首先进行求解的准备工作 求解矩阵 A 和矩阵 B 其中 A 为公交站点相关矩阵 其中存放元素 为仅考虑公汽线路时 ij a ij a 从公汽站 i 到公汽站 j 直达行驶所经过最少的路段数目 ij 当不能直达或 i j 时 0 B 为直达公交线路矩阵 是矩阵 A 的对应矩阵 其中存放元素 ij a 10 为仅考虑公汽线路时 从公汽站 i 到公汽站 j 直达行驶所经过最少的路 ij b ij b 段数目的公汽线路 当不能直达或 i j 时 0 ij b 1 整理和完善路公汽线路数据 利用 C 语言编程 将公汽线路信息中的所 有下行线是上行线原路返回的线路的下行补全 将环行路线在其后面原样粘贴 一次 注意粘贴时起点和终点相同 不要重复粘贴 并在其下一行补一行全 0 行 2 读取数据 将已在上步中整理好的数据用 matlab 读出 并存成矩阵形式 得到初始化矩阵 D 该矩阵有 520 2 1040 行 520 为公汽线路总数 每一行 的行数除以 2 的得数上取整即为该行线路对应公汽线路信息中的线路号 3 转换矩阵 得到矩阵 A B 求解矩阵 A B 的步骤如下 step1 将矩阵 A 初始化为 3957 3957 值的矩阵 初始时任意两站之间均没 1000 有联系 矩阵 B 初始化为 3957 3957 的零矩阵 step2 对于存有站点信息的矩阵 D 如果 0 0 1 2 1040 ijikijik DDDDi 表示站点在同一公交线路上 线1 2 145 1 1040 jki i ijik DD与 路号为 从 2ixx 代表对上取整 ijik DDki 到要乘坐站 step3 如果 则 转 step2 ijik D D kia ijik D D aki 2 ijik D D bi step4 对于矩阵 A 如果 将置零 1000 ijik D D a ijik D D a 以下我们给出矩阵 A 和 B 的一部分 对两矩阵的意义进行说明 12345678910 10000000000 200023002000 30000000000 402400484722000 500050010000 600049100000 702021000000 800000000011 90000000000 1000000001100 12345678910 10000000000 2000270027000 30000000000 4015200223223152000 500022302230000 600022322300000 70152027000000 800000000043 90000000000 1000000004300 矩阵 A 的部分示例 矩阵 B 的部分示例 矩阵 A 的第 1 行第 2 列为 0 表示从公汽站点 1 到公汽站点 2 没有直达 的线路 所以对应矩阵 B 的第 1 行第 2 列也为 0 矩阵 A 中第 4 行第 6 列为 11 47 表示从公汽站点 4 到公汽站点 6 可以直达 且直达时最少乘坐 47 站 对应的矩阵 B 中第 4 行第 6 列的 223 表示从公汽站点 4 到公汽站点 6 最短 的直达线路是公汽线路 L223 观察矩阵 A 发现题目中所给的 6 对起始站和终点站对应的元素均为 0 表示这 6 对站点之间均不可以直达 下面我们首先搜索 1 次换乘 利用两条线 路的路线选择方案 一 换乘 1 次的情况 换乘次数 s 已经确定为 1 时 从起点到终点所利用的公交线路总数 s 1 2 也就确定了 所以我们的模型改写成以下形式 n 1 n k 1 min35 min n ijk k ijk Tms PP s t 2 1 11 1 20 k k k n m sn k P m k 乘客第次乘坐的公汽为单一票价时 乘客第次乘坐的公汽为分段计价时 其中为从起点到终点所利用的公交线路总数 为乘客第 k 次乘坐公交n k m 时所乘坐的站数 换乘 1 次时 k 1 2 为换乘的次数 s n 1 为乘客s k P 第 k 次乘坐公交时所需要的费用 首先我们利用第一对起始站和终点站 S3359 S1828 对我们算法的整体思 想进行说明 判断矩阵 A 中元素是否为 0 为 0 则从起始站 3359 1828 a S3359 到终点站 S1828 无法直达 然后搜索矩阵 A 的第 3359 行 找到第 3359 行的第一个非 0 元素 假设在第 j 列 判断 1828 列的第 j 行元素是否 1828j a 同时为非 0 元素 若非 0 则记录下 j 和 3359 j a 1828j a 3359 j b 1828j b 表示从公汽站点 S3359 乘坐公汽线路 经过站后 在公汽站点 Sj 3359 j b 3359 j a 下车 然后换乘公汽线路 经过站后 到达公汽站点 S1828 用一个 1828j b 1828j a 简图表示即为 若为 0 则继 3359 1828 3359 1828 S3359SjS1828 jj jj bb aa 经站经站 1828j a 12 续搜索矩阵 A 的第 3359 行的下一个非 0 元素 依次类推 直到将矩阵 A 的 第 3359 行中的 3957 个元素全部搜索完毕 则得到了换乘 1 次时从起始站 S3359 到终点站 S1828 的可行的线路选择方案 其中一定包含了最优的线路选 择方案 然后计算得到的方案的时间和费用 给出最优解 下面给出从起始站 i 到终点站 j 编程求解的具体步骤 step1 令 k 1 判断是否为 0 若非 0 记录 i j a i j a i j b step2 判断是否为 0 若非 0 判断是否为 0 若非 0 判断 i k a k j a 与是否相等 相等时表示可以直达 若不等 记录 i k b k j b k i k a k j a i k b k j b step3 k k 1 判断 k 是否大于 3957 若不大于 转 step2 step4 计算所以可行线路方案需要的时间和费用 由上述步骤 利用 Matlab 编程 可以得到换乘 1 次的情况下从任意起点到 任意站点的可行线路选择方案 我们仍然以第一对起始站和终点站 S3359 S1828 为例 利用上述解法可以得到 9 种可行的方案 如下表所示 起点站终点站线路 1中转站线路 2时间 分 费用 元 L436 下 S1784L167 下 1013 L436 下 S1241L167 下 1073 L436 下 S3695L217 下 1133 L436 下 S2606L217 下 1253 L469 上 S0304L217 下 1373 L469 上 S0727L217 下 1373 L469 上 S2364L217 下 1373 L469 上 S3192L217 下 1373 S3359S1828 L469 上 S0519L167 下 1404 表 1 换乘 1 次时 S3359 S1828 的可行路线 由表 1 我们很容易发现 S3359 S1828 的可行线路方案中 时间最少的 方案恰好也同时为费用最少的方案 就是说模型中的两个目标 1 n k 1 min35 min n ijk k ijk Tms PP 在此情况下是统一的 我们得到换乘 1 次时 S3359 S1828 的时间和费用同时 最优的最佳路线如下 13 起点站终点站线路 1中转站线路 2时间 分 费用 元 S3359S1828L436 下 S1784L167 下 1013 表 2 换乘 1 次时 S3359 S1828 的最佳路线 分别计算问题 1 中给出的其他 5 对起始站和终点站 得到的可行路线方案数目 如下 2 S1557 S0481 0 种 3 S0971 S0485 11 种 4 S0008 S0073 62 种 5 S0148 S0485 0 种 6 S0087 S3676 2 种 说明 利用的线路 1 和线路 2 完全相同 只是中转站不同的方案我们算作 2 种 方案 其中 S1557 S0481 和 S0148 S0485 无法通过 1 次换乘到达 也就无所谓 最优线路选择方案 S0971 S0485 S0008 S0073 和 S0087 S3676 均有多于 1 种的可行线路选择方案 而且与 S3359 S1828 具有相同的特点 即可行线路 方案中 时间最少的方案恰好也同时为费用最少的方案 就是说模型中的两个 目标 1 n k 1 min35 min n ijk k ijk Tms PP 在此情况下是统一的 我们得到换乘 1 次时 6 对起始站到终点站之间的时间和 费用同时最优的最佳路线如下最佳路线如下 起点站终点站线路 1中转站线路 2时间 分 费用 元 1S3359S1828L436 下 S1784L167 下 1013 2S1557S0481无 3S0971S0485L013 下 S2184L417 下 1283 4S0008S0073L159 上 S0291L058 下 832 5S0148S0485无 6S0087S3676L454 上 S3496L209 下 652 表 3 换乘 1 次时 6 对起始站 终点站的最佳路线 说明 时间和费用同时达到最优的方案可能有多种 我们仅在此给出其中的一 部分方案 以上我们给出了换乘一次时 6 对起始站到终点站之间的最佳线路 发现有 2 对无法通过换乘 1 次到达 其他的可以通过换乘 1 次到达的 换乘 1 次的方 案也不一定是时间和费用的最优方案 所以 有必要给出换乘 2 次的算法 二 换乘 2 次的情况 14 换乘次数 s 为 2 时 从起点到终点所利用的公交线路总数 s 1 3 模型n 改写成以下形式 1 n k 1 min35 min n ijk k ijk Tms PP s t 3 1 12 1 20 k k k n m sn k P m k 乘客第次乘坐的公汽为单一票价时 乘客第次乘坐的公汽为分段计价时 其中为从起点到终点所利用的公交线路总数 为乘客第 k 次乘坐公交时所n k m 乘坐的站数 换乘 2 次时 k 1 2 3 为换乘的次数 s n 1 为乘客第s k P k 次乘坐公交时所需要的费用 下面给出从起始站 i 到终点站 j 换乘 2 次时的求解步骤 Step1 令 m n 1 Step2 判断是否为 0 若非 0 判断是否为 0 若非 0 判断 i m a m n a 是否为 0 若非 0 判断 是否相等 若 n j a i m b m n b n j b i m b 两两不等 记录 m n m n b n j b i m a m n a n j a i m b m n b n j b Step3 n n 1 判断 n 是否大于 3957 若不大于 转 step2 Step4 m m 1 判断 m 是否大于 3957 若不大于 转 step2 Step5 计算所以可行线路方案需要的时间和费用 由上述步骤 利用 Matlab 编程 可以得到换乘 2 次的情况下从任意起点到 任意站点的可行线路选择方案 我们仍然以第一对起始站和终点站 S3359 S1828 为例 利用上述解法可以得到 4016 种可行的方案 介于篇幅原 因 就不在此列表给出 观察这 4016 种可行的方案 发现与换乘 1 次时具有相 同的特点 时间最少的方案恰好也同时为费用最少的方案 就是说模型中的两 个目标 15 1 n k 1 min35 min n ijk k ijk Tms PP 在此情况下是统一的 我们得到换乘 2 次时 S3359 S1828 的时间和费用同时 最优的最佳路线如下 起点站终点站线路 1中转站 1线路 2中转站 2线路 3时间费用 L015 下 S2903L027 环 S1784L167 下 L015 下 S2903L201 上 S0458L041 上 L015 下 S2903L201 上 S1671L041 上 L015 下 S2903L201 上 S1783L041 上 L015 下 S2903L201 上 S1790L041 上 L015 下 S2903L201 上 S1792L041 上 L324 下 S1746L027 环 S1784L167 下 L324 下 S2027L027 环 S1784L167 下 L324 下 S2027L201 上 S0458L041 上 L324 下 S2027L201 上 S1671L041 上 L324 下 S2027L201 上 S1783L041 上 L324 下 S2027L201 上 S1790L041 上 L324 下 S2027L201 上 S1792L041 上 L484 下 S3697L027 环 S1784L167 下 S3359S1828 L484 下 S3727L027 环 S1784L167 下 733 表 4 换乘 2 次时 S3359 S1828 最佳路线 换乘 2 次时 一共有 15 种方案 使 S3359 S1828 的时间和费用同时为最 小 这 15 种方案的时间 费用和换乘次数均完全相同 所以这 15 种方案并没 有优劣之分 均是换乘 2 次时 S3359 S1828 最优线路方案 分别计算问题 1 中给出的其他 5 对起始站和终点站 得到的可行路线方案 数目如下 2 S1557 S0481 128 种 3 S0971 S0485 3738 种 4 S0008 S0073 14435 种 5 S0148 S0485 316 种 6 S0087 S3676 460 种 说明 利用的线路 1 和线路 2 完全相同 只是中转站不同的方案我们算作 2 种 方案 所有起始站到终点站均可以通过 2 次换乘到达 且均有多于 1 种的可行线 路选择方案 而且与 S3359 S1828 具有相同的特点 即可行线路方案中 时 间最少的方案恰好也同时为费用最少的方案 就是说模型中的两个目标 16 1 n k 1 min35 min n ijk k ijk Tms PP 在此情况下是统一的 我们得到换乘 2 次时 6 对起始站到终点站之间的时间和 费用同时最优的最佳路线如下最佳路线如下 起点站终点站线路 1 中转站 1 线路 2 中转站 2 线路 3时间费用 1S3359S1828L015 下 S2903 L027 环 S1784 L167 下 733 2S1557S0481L084 下 S1919 L189 下 S3186 L460 下 1063 3S0971S0485L013 上 S1609 L140 下 S2654 L469 上 1063 4S0008S0073L043 下 S1383 L296 环 S2184 L345 上 673 5S0148S0485L308 上 S0036 L156 上 S2210 L417 下 1063 6S0087S3676L021 下 S0088 L231 环 S0427 L097 上 463 表 5 换乘 2 次时 6 对起始站 终点站的最佳路线 说明 时间和费用同时达到最优的方案可能有多种 我们仅在此给出其中的一 种方案 5 3 所得方案的评价所得方案的评价 以上我们分别给出了 6 对站点之间换乘 1 次和换乘 2 次的最佳路线 下面 将综合评价这些最佳路线的优劣 首先列表比较两种情况下最佳路线的时间和 费用 123456 方案时间费用时间费用时间费用时间费用时间费用时间费用 换乘 1 次1013无1283832无652 换乘 2 次733106310636731063463 表 6 两种方案最佳路线的时间 费用对比表 发现除第 2 与第 4 对站点之间只有换乘两次的路线之外 其余的 4 对站点 的时间最优解均在换乘 2 次时出现 而费用的最优解一般在换乘 1 次时出现 以第 4 对站点的最佳路线为例 换乘 1 次的时间 83 分钟大于换乘 2 次的时间 67 分钟 但换乘 1 次的费用 2 元小于换乘 2 次的费用 3 元 两者之间谁更优呢 而第 1 对站点 换乘 1 次的时间 101 分钟大于换乘 2 次的时间 73 分钟 换乘 1 次的费用 3 元等于换乘 2 次的费用 3 元 但就可以说换乘 2 次的最佳路线比换 乘 1 次的最佳路线更优吗 但换乘 1 次比换乘 2 次的换乘次数少 换乘次数 时间和费用三个主要影响人们乘车线路选择的因素对不同乘客 不同时间而言地位是不同的 对于对时间比较看中的乘客 如白领 年轻人和 赶时间的时候 而言 时间的权值就比较高 对于对费用比较看中的乘客 如 低收入人群 而言 费用的权值就比较高 对于对换乘次数比较看中的乘客 17 如行动不是很方便的老年人和残疾人 而言 换乘次数的权值就比较高 所 以只有当一条路线的时间 费用和换乘次数均比另一条路线少时我们才可认为 这条路线更优 经过以上的分析我们认为每对站点之间的两组最佳路线各有优劣 对于不 同目标 它们都有可能是最优解 还原到题目的背景信息 某公司准备研制开 发一个解决公交线路选择问题的自主查询计算机系统 我们建议在系统界面上 给出一个查询条件 乘客可以自行选择是根据时间 费用和换乘其中的哪一个 为首要目标进行查询 系统根据首要目标 选择输出最佳路线 六 问题二的建模与求解六 问题二的建模与求解 6 1 模型的建立 问题 2 要求在同时考虑公汽与地铁线路的情况下 给出任意两公汽站点之间 线路选择的一般数学模型与算法 问题 2 与问题 1 的目标相同 还是时间最少 与费用最少 但是时间与费用的计算方式比问题 1 要复杂很多 从起点 i 到终点 j 的所需要的总时间由三部分构成 一是公交的行驶时 ij T 间 二是乘客换乘时的耗时 三是当起始站和终点站乘车为地铁时需要先由公 汽站进地铁站或从地铁站走到公汽站点的步行时间 这个步行时间我们定义为 修正时间 而在中途遇到进地铁的情况则没有修正时间 因为步行时间已经包 含在换乘时间内 公交的行驶时间等于相邻站点间的平均行驶时间乘以公交行 驶的站数 但公交分为公汽和地铁 两者相邻站点间的平均行驶时间不同 3 分钟 2 5 分钟 每一次乘坐公交的行驶时间可表示为以下形式 t汽t铁 3 2 5 k k k mk T mk 行 乘客第次乘坐的公交为公汽时 乘客第次乘坐的公交为地铁时 换乘也存在 5 种情况 5 种换乘的时间分别为 5 分钟 4 分钟 t汽汽t铁铁 7 分钟 6 分钟和平均耗时 t铁汽t汽铁通过地铁的公汽换乘公汽t汽铁汽 从公汽站点步行到地铁的时间 从地铁站点步行到另一公汽站点的时间 t汽铁汽 等待公汽到来的时间 4 4 7 4 11 分钟 每一次的换乘时间表示如下 5 4 k k k Tk k k 换 乘客第次换乘为公汽换乘公汽时 乘客第次换乘为地铁换乘地铁时 7乘客第次换乘为地铁换乘公汽时 6乘客第次换乘为公汽换乘地铁时 11乘客第次换乘为公汽换乘公汽需通过地铁时 18 修正时间表示如下 10 6 0 T 修正 当初始乘车为地铁 最终乘车也为地铁时 当初始乘车为地铁 最终乘车为公汽时 4 当初始乘车为公汽 最终乘车为地铁时 当初始乘车为公汽 最终乘车也为公汽时 综上总的耗时可以由下面的表达式来表示 ij T 1 11 nn ijkk kk TTTT 行换 修正 乘客从起点 i 到终点 j 的所需要的总费用为乘坐每一辆公交所需费用的 ij P 加和 乘坐公汽时的收费分为两种情况 一种是单一票价的 无论乘坐多少站 均收费 1 元 另一种是分段计价 分段计价的票价为 0 20 站 1 元 21 40 站 2 元 40 站以上 3 元 乘坐地铁时单一票价 3 元 无论地铁线路间是否 换乘 将两种收费方式用数学表达式表示可写成以下的形式 1 20 k k k m k P k k 乘客第次乘坐的公交为单一票价的公汽时 乘客第次乘坐的公交为分段计价的公汽时 3乘客第次乘坐的公交为地铁且为公汽换乘的地铁时 0乘客第次乘坐的公交为地铁且为地铁换乘的地铁时 其中 表示对上取整 即取不小于的最小整数 乘客从起点 i 到终 20 k m 20 k m 20 k m 点 j 的所需要的总费用为乘坐每一辆公交所需费用的加和 即 ij P n k 1 ijk PP 选择最优公交线路的目标有三个 一为乘车时间最少 二为需要费用最少 三为换乘次数最少 即利用的公交线路数最少 所以我们可以建立如下模型建立如下模型 1 11 n k 1 min min min nn ijkk kk ijk TTTT PP n 行换修正 19 s t 13 1 02 1 20 k k k n m s k m k P k k 乘客第次乘坐的公交为单一票价的公汽时 乘客第次乘坐的公交为分段计价的公汽时 3乘客第次乘坐的公交为地铁且为公汽换乘的地铁时 0乘客第次乘坐的公交为地铁且为地铁换乘的地铁时 其中为从起点到终点所利用的公交线路总数 为乘客第 k 次乘坐公交n k m 时所乘坐的站数 由假设 6 知 k 1 2 3 为换乘的次数 s n 1 为乘客s k P 第 k 次乘坐公交时所需要的费用 6 2 模型的求解模型的求解 首先修改矩阵 A B 由于地铁线路的加入使得各个公汽站点的联系发生变化 所对应的 A B 矩阵也随之发生变化 因此我们将对 A B 矩阵进行修改 使其能够反应出新 的联系 具体的修改规则如下 1 同一地铁站对应多个公汽站的情况 如 D01 S0567 S0042 S0025 若之前两公交站点 i j 无直达车次 则 均为零 因为现在通过地铁 i j a i j b 使公汽站点 i j 之间有联系 B 矩阵修改为 1000 表示站点通过地铁 1 号线联系 A 矩阵仍为 0 表示站点间并没有乘车 若之前两公交站点 i j 有直达车次 则 均非零 因为现在通过地铁使公汽站点 i j 之间有新的联系 令 B 矩阵 i j a i j b 的相应元素 若通过 2 号线增加的联系则令 则 1000 i ji j bb 2000 i ji j bb B 矩阵的元素包含了双重信息 的最高位为 1 表示通过地铁 1 号线 最 i j b i j b 高位为 2 表示通过地铁 2 号线 低 3 位表示的仍为公汽线路号 A 矩阵的元素 不变 2 不同地铁站点对应的不同公汽站点的情况 如 D01 S0567 S0042 S0025 和 D12 S0609 S0608 所对应的公汽站之间 原 A 矩阵中的数据表示的是两公汽站点 i j 通过公汽到达所需要的最 i j a 短站数 现在需要 A 矩阵的数据既可以表示公汽线路站数又可以表示出地铁 i j a 线路的站数 我们所采取的方法是令 地铁相距站数 1000 公汽站数 同 i j a 20 时令 B 矩阵中相应元素 若通过 2 号线增加的联系则令 1000 i ji j bb 经过这样修改之后 A B 矩阵就同时包含了公汽和地铁的信 2000 i ji j bb 息 其中各元素 的低 3 位仍然表示公汽线路的关系 高位表示地铁线 i j a i j b 路的关系 如 8034 1284 高位 8 表示站点 i j 通过地铁最少需 i j a i j b i j a 要 8 站直达 高位 1 表示利用的是地铁 1 号线 低三位的数据 034 和 284 表 i j b 示站点 i j 通过公汽最少需要 34 站直达 利用的公汽线路 L284 3 两站点之间有多条地铁线路直达的情况 D12 和 D18 为两条地铁线路的交 点 当公汽站是从 D12 到 D18 时 两条地铁站均能到达 经比较发现 T1 线经 过的站数少于 T2 线 因此凡是从 D12 到 D18 的公汽站均写入 T1 站的信息 经过以上修改 我们得到既包含公汽线路信息又包含地铁线路信息的新的 矩阵 A 和矩阵 B 观察矩阵 B 发现题目中所给的 6 对起始站和终点站中 S0087 S3676 对应 的元素为非 0 元素 则 S0087 S3676 可以直达 线路表示如下 87 3676 b 起点站终点站线路时间价钱 S0087S3676T02353 表 7 S0087 S3676 的直达路线 一 换乘 1 次的情况 换乘次数 s 已经确定为 1 时 从起点到终点所利用的公交线路总数 s 1 2 也就确定了 所以我们的模型改写成以下形式 n 1 11 n k 1 min min nn ijkk kk ijk TTTT PP 行换修正 21 s t 2 1 11 1 20 k k k