2007B-2010-8培训.ppt

2007年B题 乘公交 看奥运 2010年8月暑期集中培训 2007年B题 乘公交 看奥运 我国人民翘首企盼的第29届奥运会明年8月将在北京举行 届时有大量观众到现场观看奥运比赛 其中大部分人将会乘坐公共交通工具 简称公交 包括公汽 地铁等 出行 这些年来 城市的公交系统有了很大发展 北京市的公交线路已达800条以上 使得公众的出行更加通畅 便利 但同时也面临多条线路的选择问题 针对市场需求 某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统 为了设计这样一个系统 其核心是线路选择的模型与算法 应该从实际情况出发考虑 满足查询者的各种不同需求 请你们解决如下问题 1 仅考虑公汽线路 给出任意两公汽站点之间线路选择问题的一般数学模型与算法 并根据附录数据 利用你们的模型与算法 求出以下6对起始站 终到站之间的最佳路线 要有清晰的评价说明 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同时考虑公汽与地铁线路 解决以上问题 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 L001分段计价 S0619 S1914 S0388 S0348 S0392 S0429 S0436 S3885空行L002分段计价 上行 S3748 S2160 S1223 S1404 S2377 S1477 S2017 S2019 S1321 S1381 S1383 S1691 S3766下行 S0004 S1968 S0012 S2636 S2113 S2112 S2833 S0618 S1327 S2303 S3917 S3231L003单一票制1元 S0417 S0272 S1973 S3425 S1433 S3476 S2337 S1027 S1065 S2974 S0234 S0521 S3737 一 问题分析 如何换车 车与车之间的关系 乘车人关心的问题 1 换乘次数最少2 费用最低3 时间最短4 步行最少5 是否有座位 二 建立直达矩阵 不考虑地铁时建立直达矩阵设 公汽站点个数 表示由站点直达站点付出的代价 可以为时间或费用 根据的意义不同 可分别称为直达时间矩阵或直达费用矩阵 则直达矩阵 其中 二 建立直达矩阵 考虑地铁时建立直达矩阵此时 公汽站点个数 地铁站点个数 当站点与站点同为公汽站点或同为地铁站点时 直达矩阵中之定义与上面相同 当站点与站点中一个为公汽站点 另一个为地铁站点时 分为以下情形 1 站点是公汽站点 站点是地铁站点 1 1 若站点不是站点所在公汽线路L与地铁线的地铁换乘站点 则令 二 建立直达矩阵 1 2 若站点是站点所在公汽线路L与地铁线的地铁换乘站点 设站点为公汽线路L与地铁线的公汽换乘站点 若为直达时间矩阵 则令若为直达费用矩阵 则令 二 建立直达矩阵 2 站点是公汽站点 站点是地铁站点 2 1 若站点不是站点所在公汽线路L与地铁线的地铁换乘站点 则令2 2 若站点是站点所在公汽线路L与地铁线的地铁换乘站点 设站点为公汽线路L与地铁线的公汽换乘站点 若为直达时间矩阵 则令若为直达费用矩阵 则令注 经过如此处理 除换乘时间不同 在以下建模与求解过程中 就不必区分站点类型了 三 优化目标考虑 从乘客角度考虑 优化目标应是以下三个目标之一 换乘次数最少 费用最省 时间最短 分别考虑对此三个目标的优化 按照第一目标最优 第二 三目标在第一目标最优前提下 最优或次优来求解 四 矩阵算子 的定义 定义矩阵算子 如下 设A B分别为n阶方阵定义 1 其中 2 其中定义如下 当考虑费用矩阵之间运算时 当考虑时间矩阵之间运算时 表示换乘时间 具体来说 当或 以下设 当为公汽站点而为地铁站点 或者为地铁站点而为公汽站点时 令 四 矩阵算子 的定义 其他形式有考虑直达矩阵 令 3 记 四 矩阵算子 的定义 由 1 2 式可知 对直达时 费用 矩阵 表示从站点到站点至多换乘1次能够到达所需的最短时间 最少费用 同理 表示从站点到站点至多换乘k次能够到达所需的最短时间 最少费用 五 换乘次数最少 考虑换乘次数最少为第一目标 对直达时间矩阵按 3 式重复地进行 运算得到 当 时 表示从站点到站点最少换乘k次能够到达 且即表示换乘k次到达所需的最短时间 在运算过程中可记录下换乘站点信息 随之可得到相关线路信息 若有若干条最小换乘路线 则比较另外两个目标选择最佳线路 六 费用最省 考虑费用最省为第一目标 对直达费用矩阵按 3 式重复地进行 运算得到 运算适当次数后若 则表示已得到所有站点间的最小费用 即表示从站点到站点所需的最少费用 在运算过程中可记录下换乘站点信息 随之可得到相关线路信息 若有若干条最小换乘路线 则比较另外两个目标选择最佳线路 七 时间最短 考虑时间最短为第一目标 对直达时间矩阵按 3 式重复地进行 运算得到 运算适当次数后若 则表示已得到所有站点间的最短时间 即表示从站点到站点所需的最少费用 在运算过程中可记录下换乘站点信息 随之可得到相关线路信息 若有若干条最小换乘路线 则比较另外两个目标选择最佳线路 八 已知所有站点间步行时间的优化模型 注 同一公交线的往返路线视为两条单行线 记 共有m条单行公交线 构造一个m 2个点构成的完全图 点 a为起点 出发点 b为终点 目的地 此外每条公交线也视为一个点 边 边表示两点之间的步行关系 边权 步行时间为边权 针对不同的边可分为上车前 下车后和换车时步行时间 构成步行时间矩阵 行依次表示的是m条公交线与起点 列依次表示的是m条公交线与终点 八 已知所有站点间步行时间的优化模型 点权 第个公交线点还有三个信息为点权 1 公交线名称及上行或下行 2 类型及票价方式 3 乘车站数表矩阵 其中表示从c到d经过i号公交线时需要乘车的站数 c到d利用不上i时取无穷大 这个矩阵的行列表示用S 八 已知所有站点间步行时间的优化模型 原问题转化为在这个图上求a到b的最短路 最短的概念可以是换车数最少 乘车的总站数最少 总的步行时间最少 总车费最少这样几个目标的各种组合方式 例如 m 5 八 已知所有站点间步行时间的优化模型 一些预备计算8 1 上车前步行时间 即起点到各公交线及终点的步行时间 共m 1个 从a到第c条公交线的第k站的步行时间记为则且对应站号例 八 已知所有站点间步行时间的优化模型 一些预备计算8 2 下车后步行时间 与上车前步行时间计算类似 可得到 从第d条公交线的第k站到b的步行时间记为则且对应站号例 八 已知所有站点间步行时间的优化模型 一些预备计算8 3 换车步行时间 即两条公交线间步行时间 共m m 1 个 对第c条公交线与第d条公交线的任何两站之间的步行时间取最小 得同时得到两条公交线上的分别两个站号即换乘的两个站例 八 已知所有站点间步行时间的优化模型 一些预备计算8 4 利用上面关于 的结果 计算全部 可以用0 1整数规划解决这个问题 方法是分出恰乘一次公交车 恰乘两次公交车 恰乘三次公交车 恰乘四次公交车四种情况分别求出最优解然后比较得出最优解 八 已知所有站点间步行时间的优化模型 恰乘一次公交车的模型如下 变量全部是0 1变量 共有3m个 表示选不选择去第i条公交线的路 表示选不选择乘第i线公交车 表示选不选择从第i条公交车下车后走到目的地的路 注 它们都是取1表示选择而取0表示不选择 约束条件 共2m 1个 含义是只选择一条公交线 含义是要乘第i条公交线就要走相应的两条路 八 已知所有站点间步行时间的优化模型 恰乘一次公交车的模型如下 目标函数 据用户选择的情况用点权和边权构造 共同点都是最小值 1 步