公交转车问题(数学建模).ppt

公交转车问题 南京邮电大学理学院杨振华制作yangzhenhua 南京邮电大学数理学院杨振华制作yangzhenhua 公交转车问题 针对市场需求 某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统 为了设计这样一个系统 其核心是线路选择的模型与算法 应该从实际情况出发考虑 满足查询者的各种不同需求 公交 指公共交通工具 包括公共汽车与地铁 南京邮电大学数理学院杨振华制作yangzhenhua 公交转车问题 1 仅考虑公汽线路 给出任意两公汽站点之间线路选择问题的一般数学模型与算法 并根据附录数据 利用你们的模型与算法 求出以下6对起始站 终到站之间的最佳路线 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同时考虑公汽与地铁线路 解决以上问题 南京邮电大学数理学院杨振华制作yangzhenhua 基本参数设定 相邻公汽站平均行驶时间 包括停站时间 3分钟相邻地铁站平均行驶时间 包括停站时间 2 5分钟公汽换乘公汽平均耗时 5分钟 其中步行时间2分钟 地铁换乘地铁平均耗时 4分钟 其中步行时间2分钟 地铁换乘公汽平均耗时 7分钟 其中步行时间4分钟 公汽换乘地铁平均耗时 6分钟 其中步行时间4分钟 公汽票价 分为单一票价与分段计价两种 标记于线路后 其中分段计价的票价为 0 20站 1元 21 40站 2元 40站以上 3元地铁票价 3元 无论地铁线路间是否换乘 注 以上参数均为简化问题而作的假设 未必与实际数据完全吻合 南京邮电大学数理学院杨振华制作yangzhenhua 公汽线路信息 公汽运行方式 1 环形 2 上下行 有可能上下行路线一致 公汽收费方式 1 分段计价 2 单一票制1元 南京邮电大学数理学院杨振华制作yangzhenhua 公汽线路信息 文件列出了520条公汽线路 下面是其中的一条 L001分段计价 S0619 S1914 S0388 S0348 S0392 S0429 S0436 S3885 S3612 S0819 S3524 S0820 S3914 S0128 S0710该线路是分段计价 且上下行路线一致的 南京邮电大学数理学院杨振华制作yangzhenhua 地铁线路信息 T1票价3元 本线路使用 并可换乘T2 D01 D02 D03 D04 D05 D06 D07 D08 D09 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23T2票价3元 本线路使用 并可换乘T1 环行 D24 D25 D26 D12 D27 D28 D29 D30 D31 D32 D18 D33 D34 D35 D36 D37 D38 D39 D24 南京邮电大学数理学院杨振华制作yangzhenhua 地铁T1线换乘公汽信息 D01 S0567 S0042 S0025D02 S1487D03 S0303 S0302D04 S0566D05 S0436 S0438 S0437 S0435D06 S0392 S0394 S0393 S0391D07 S0386 S0388 S0387 S0385D08 S3068 S0617 S0619 S0618 S0616D09 S1279D10 S2057 S0721 S0722 S0720D11 S0070 S2361 S3721D12 S0609 S0608D13 S2633 S0399 S0401 S0400D14 S3321 S2535 S2464D15 S3329 S2534D16 S3506 S0167 S0168D17 S0237 S0239 S0238 S0236 S0540D18 S0668D19 S0180 S0181D20 S2079 S2933 S1919 S1921 S1920D21 S0465 S0467 S0466 S0464D22 S3457D23 S2512 南京邮电大学数理学院杨振华制作yangzhenhua 地铁T2线换乘公汽信息 D24 S0537 S3580D25 S0526 S0528 S0527 S0525D26 S3045 S0605 S0607D12 S0609 S0608D27 S0087 S0088 S0086D28 S0855 S0856 S0854 S0857D29 S0631 S0632 S0630D30 S3874 S1426 S1427D31 S0211 S0539 S0541 S0540D32 S0978 S0497 S0498D18 S0668D33 S1894 S1896 S1895D34 S1104 S0576 S0578 S0577D35 S3010 S0583 S0582D36 S3676 S0427 S0061 S0060D37 S1961 S2817 S0455 S0456D38 S3262 S0622D39 S1956 S0289 S0291 南京邮电大学数理学院杨振华制作yangzhenhua 问题分析 从实际情况考虑 不同的查询者有不同的要求 在数学上体现出目标的不同 一般可以考虑转车次数 乘车费用 乘车时间这3个目标 问题可以归结为多目标优化问题 南京邮电大学数理学院杨振华制作yangzhenhua 问题分析 如何处理上面的多个目标 多目标的处理最常用的方法是单目标化 即采用加权平均等方法将多个目标结合形成一个单一的目标 本问题中 单目标化并不合适 比较适当的方法是对每个目标寻求最佳线路 然后让乘客按照自己的需求进行选择 南京邮电大学数理学院杨振华制作yangzhenhua 模型建立 我们先仅考虑公汽线路的情况 设N表示问题中的公汽站点数 即N 3957 A0 a i j 0 N N是直达最小站数矩阵 当存在公共汽车从站点直达站点时 表示从直达的最小站数 否则该元素取为 南京邮电大学数理学院杨振华制作yangzhenhua 模型建立 令Am a i j m N N是m次转乘最小站数矩阵 其元素a i j m 表示m次转车情形下 从Si到Sj的最小站数 显然 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型 对于给定的公汽站点Si与Sj 最小转车次数模型可以写为 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型 转车次数为m时 从Si到Sj的总时间为5m 3a i j m 转一次车5分钟 每乘一站 用时3分钟 下面是最小乘车时间模型 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车费用模型 最小乘车费用模型可以写为如下的形式 该模型是形式上的 对于求解没有实质性的作用 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 对于给定的公汽站点Si与Sj 只要逐次求出 a i j m 直到其为有限值即可 在实际求解时 先根据公汽线路的数据将a i j 0 的数据存储在矩阵A0中 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 算法一 逐次查找 对于给定的i j 1 若a i j 0 表明转车次数为0 否则转 2 2 k从1到N进行搜索 若a i k 0 a k j 0 则转车次数为1 否则转 3 3 k1 k2从1到N进行搜索 若a i k1 0 a k1 k2 0 a k2 j 0 则转车次数为2 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 逐次查找算法的复杂度若只要转一次车 则循环的步数为N 若要转2次车 循环的步数为N2 若要转3次车 循环的步数为N3 由于N 3957 N3 6 2 1010 普通计算机运行时间较长 若要转4次车 很难承受计算量 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 算法二 存储逐次查找 1 若a i j 0 表明转车次数为0 否则转 2 2 求出矩阵A1 a i j 1 N N 其每个元素通过上面的表达式 用k从1到N循环求得 若对给定的i j 有a i j 1 表明转车次数为1 类似可以计算多次转车的情况注 矩阵A0 A1等计算后存储在计算机中 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 存储逐次查找算法的复杂度矩阵A1的计算 一共计算N2个元素 每个元素的计算要循环N步 计算量为N3 运行时间依然较长 优点 矩阵Am m 1 的计算工作量与A1一致 有可能计算转多次车 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 在前面的两个算法中 每次循环都要进行N次 事实上 对给定的i 满足a i k 0 的k是很少的 我们只要对这些k进行循环 在实际问题中 任何一个城市中 任何一个公汽站点所能到达的公汽站点只是城市中的一些 线 相对于整个城市而言 数目是比较少的 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 算法三 有限搜索逐次查找 给出矩阵B 其第i行记录的是满足a i k 0 的所有的 k 将存储逐次查找算法中的k从1到N循环改为正对矩阵B第i行中的 k 进行循环 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 有限搜索逐次查找算法的复杂度矩阵Am的计算 一共计算N2个元素 每个元素的计算要循环的步数大大小于N 大约为N 10 计算量约为N3 10 一般的计算机可以实现 南京邮电大学数理学院杨振华制作yangzhenhua 最小转车次数模型求解 对于题目中给出的六组公汽站点 其最小转车次数分别为 1 S3359 S18281 2 S1557 S04812 3 S0971 S04851 4 S0008 S00731 5 S0148 S04852 6 S0087 S36761 南京邮电大学数理学院杨振华制作yangzhenhua 转车次数 由于算法复杂性的问题 许多参赛队都假设 最多转2次车 少数参赛队考虑转3次车 个别的参赛队考虑转4次车或更多 由于所给的6组站点最小转车次数为1或2 似乎假设最多转2次车是合理的 根据题目中的数据 北京市的任意两个公汽站点之间一般需转几次车 南京邮电大学数理学院杨振华制作yangzhenhua 转车次数 N 3957 一共有N N 1 15653892对公汽站点 我们给出它们的最小转车次数 根据题目中的数据 北京市的公汽站点转5次车可以全部到达 根据表中的数据 假设转最多2次车是不合理的 假设转最多3次车有一定的合理性 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车费用 左边的表给出的时最小转车次数 即对应的一种乘车方案的乘车费用 关于最小乘车费用 其模型一般只有形式上的 对求解没有直接的作用 我们对具体的六对站点给出讨论的结果 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车费用 易见 第二 四 五 六对站点对应的费用是最小费用 为什么 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车费用 对于第一个点对S3359 S1828 如果换乘次数大于等于2 显然费用至少为3 若换乘次数为1 采用枚举方法将乘车方案全部列出 一共由9种方案 其中8种费用为3元 一种费用为4元 因此 最小乘车费用为3 类似 第三个点对的换乘次数为1的11种方案的最小费用也是3 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 根据上面的模型 若已知a i j m 的值 则可以求出tS i j m 关于m的最小值 由于m的取值从0到无穷大 必须采用一定的技巧来求出最小值 注 参赛队一般选取m从0到2 或0到3 是不合理的 不过也 成功 避免了求解的困难 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 考虑第一对公汽站点1 S3359 S1828最小转车次数为1 a i j 0 tS i j 0 a i j 1 32 tS i j 1 101 由于a i j m m 1 有tS i j m 8m 3 若m 13 则tS i j m 105 tS i j 1 因此 我们可以将m的范围放在0到12内求最优 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 若m的范围过大 求解会有一定困难 能否缩小m的范围 在上页的讨论中 不等式a i j m m 1的含义是总站数比转车次数至少大一 我们可以给出a i j m 更好的下界 从而缩小m的范围 南京邮电大学数理学院杨振华制作yangzhenhua 两站点之间的最小站数 a i j m 表示m次转车下 从Si到Sj的最小站数 设nS i j 表示站点Si到Sj的最小站数 可以转车任意次 显然a i j m nS i j 我们有tS i j m 5m 3a i j m 5m 3nS i j 南京邮电大学数理学院杨振华制作yangzhenhua 两站点之间的最小站数 将公汽站点设为有向图中的结点 若Si乘公汽1站可以到达Sj 我们就设一条有向边从结点i指向结点j 对于每一条有向边 指定其权为1 显然求nS i j 就转化为有向图中结点到结点的最短路径问题 对任意给定的i j 我们可以采用Dijkstra算法求得nS i j 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 对于第一对公汽站点i 3359 j 1828 nS i j 13 我们给出求解过程 a i j 0 tS i j 0 a i j 1 32 tS i j 1 101 m 2时 tS i j m 5 2 3 13 49 因此 最小乘车时间在区间 49 101 上 为求精确的最优解 必须接着求解 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 a i j 2 18 tS i j 2 64 m 3时 tS i j m 5 3 3 13 54 最优解位于区间 54 64 a i j 3 18 tS i j 3 69 m 4时 tS i j m 5 4 3 13 59 最优解位于区间 59 64 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 a i j 4 17 tS i j 4 71 m 5时 tS i j m 5 5 3 13 64 重复上述过程 tS i j 0 tS i j 1 101 tS i j 2 64 tS i j 3 69 tS i j 4 71 m 5时 tS i j m 64 可以看出 最小乘车时间为64 在转2次车时可以在此时间到达 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解算法 由上面的例子 我们只要找到一个转车次数m 转车次数不大于m时 最小乘车时间为TS i j m min tS i j k k m 转车次数大于m时 乘车时间的下界为5 m 1 3nS i j 若TS i j m 5 m 1 3nS i j 则TS i j m 为最优解 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解算法 Step1用Dijkstra算法求出nS i j 令m 0 Step2求出a i j m 令tS i j m 5m 3a i j m Step3若TS i j m min tS i j k k m 5 m 1 3nS i j 则TS i j m 即为最短乘车时间 否则令m m 1 转Step2 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 第四对公汽站点S0008 S0073的求解过程可以用下面的表格表示 nS i j 13 最小乘车时间为59 需转4次车 其它答案参见评阅要点 该要点给出的答案中包含了起始的3分钟 南京邮电大学数理学院杨振华制作yangzhenhua 综合考虑公汽与地铁 1 最小转车次数将地铁线路看成公汽线路 最小转车次数这一目标的讨论难度没有增加 只是增加了几条公汽线路 对于题中给的六组站点 其前5组站点都不在地铁边 因此增加地铁后 最小乘车次数没有变化 仍然是原来的1或2 第6组2个站点都在地铁线上 最小转乘次数为0 南京邮电大学数理学院杨振华制作yangzhenhua 综合考虑公汽与地铁 2 最小乘车费用对于一般的两个站点之间的最小乘车费用 仅考虑公汽时讨论就很复杂 增加了地铁之后讨论还是差不多复杂 要用枚举法来求解 也可以说 难度没有增加 对于题中给的六组站点 仅考虑公汽时 最小费用为2元或3元 因此在综合考虑公汽与地铁时依然是最优解 乘一次地铁3元 南京邮电大学数理学院杨振华制作yangzhenhua 综合考虑公汽与地铁 3 最小乘车时间增加了地铁后乘车时间的讨论变得相当复杂 注 如果假设换成次数最多为2或3 会将问题大大简化 在此 为了将问题合理的简化 我们首先研究这样一个问题 在考虑时间最少时 线路中是否存在先乘地铁 再转公汽 再乘地铁这样的乘车方案 南京邮电大学数理学院杨振华制作yangzhenhua 地铁 公汽 地铁 考察下面两种方案 A 从地铁站Dk乘地铁到地铁站Dk1然后由公汽站Ss1乘到公汽站Ss2 再转地铁站Dl1 乘地铁到地铁站Dl B 直接乘地铁由地铁站Dk到Dl 直观认识 A 的时间 B 的时间 南京邮电大学数理学院杨振华制作yangzhenhua 地铁 公汽 地铁 设tDB i j 表示乘地铁由地铁站Di到地铁站Dj的最短时间 nSA i j 表示可以由地铁站Di转乘的公汽站乘公汽到可以由地铁站Dj转乘的公汽站的最小公汽站数 于是 TB tDB k l 如果 A 方案中没有公汽转车TA tDB k k1 3nSA k1 l1 tDB l1 l 1313表示换车时间如果有公汽转车 等号要换成大于等于号 南京邮电大学数理学院杨振华制作yangzhenhua 地铁 公汽 地铁 TA TB tDB k k1 3nSA k1 l1 tDB l1 l 13 tDB k l 3nSA k1 l1 13 tDB k1 l1 tDB k k1 tDB k1 l1 tDB l1 l tDB k l 最后一个中括号中的式子是非负的 因此TA TB 3nSA k1 l1 13 tDB k1 l1 如果右式非负 则有TA TB 0 南京邮电大学数理学院杨振华制作yangzhenhua 地铁 公汽 地铁 3nSA k1 l1 13 tDB k1 l1 0 一共有39个地铁站 我们通过计算机程序 k1 l1对从1到39进行遍历搜索 来判断上式左边的值 发现有四组地铁站对应的值为负 分别是 13 30 16 30 30 15 30 16 这四组站点对应的nSA k1 l1 值均为1 对这四组点 再观察TA TB tDB k k1 3nSA k1 l1 tDB l1 l 13 tDB k l 右端的值 南京邮电大学数理学院杨振华制作yangzhenhua 地铁 公汽 地铁 tDB k k1 3nSA k1 l1 tDB l1 l 13 tDB k l tDB k k1 tDB l1 l 16 tDB k l 对于前面四组k1 l1 对k l进行循环搜索 可以得到tDB k k1 tDB l1 l 16 tDB k l 的最小值都是2 最终得到TA TB 0 结论 对于题中给的数据 为了时间最省 不存在 地铁 公汽 地铁 这种换乘方案 换言之 地铁一次乘完 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型 对于任意两个公汽站点 不乘地铁的时间最小方案在问题一中已经求得 下面考虑必须乘地铁的方案 乘p次 转p 1次 公汽 再乘地铁 最后乘次q 转q 1次 公汽到达终点的方案 下面将这样的方案记为pDq 注 该方案包含了仅乘地铁的情况 p q 0 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型 下面主要针对题中前5组站点进行研究 这五组站点均不能由地铁站直接转乘 因此p q 1 求任意公汽站点Si到公汽站点Sj在方案下的最短时间 即对任意的p q 以及任意的地铁站Dk Dl 求出起点乘p次公汽到可以直接转乘地铁站Dk的公汽站的最短时间 加上Dk到Dl的最短时间 再加上可以由地铁站Dl直接转乘的公汽站乘q公汽次到达终点公汽站的最短时间 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型 1 站数 N1 i k p 1 乘车时间 3N1 i k p 1 转车时间5 p 1 Si Dk Sj Dl 1 p次 3 q次 3 站数 N2 l j q 1 乘车时间 3N2 l j q 1 转车时间5 q 1 2 2 乘车时间 tD k l 4 公汽转地铁 地铁转公汽时间 13 总时间 tSDS i j p q k l 3N1 i k p 1 5 p 1 tD k l 3N2 l j q 1 5 q 1 13 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型 数学模型min tSDS i j p q k l 1 p q 1 k l 39 k l 在tSDS i j p q k l 表达式中 地铁乘坐时间tD k l 是很容易计算的 若没有转车 tD k l 2 5nD k l 每站2 5分钟 若转1次车 tD k l 2 5nD k l 4 不存在转2次以上的情况 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 tSDS i j p q k l 3N1 i k p 1 5 p 1 tD k l 3N2 l j q 1 5 q 1 13对于固定的i j 我们要遍历p q k l来求上式的最小值 对于k l进行遍历是比较简单的 为了缩小p q的取值范围 可以类似于问题一来给出站数 公汽与地铁 的下界 南京邮电大学数理学院杨振华制作yangzhenhua 下界 设nSDS i j 表示从Si乘车 公汽或地铁 可以转车任意次 到Sj的最小乘车站数 我们可以用Dijkstra求最短路径来求出这个数 记M N1 i k p 1 N2 l j q 1 为乘车方案中公汽的站数 根据公汽的站数加地铁站数不小于最小乘车站数 有M nD k l nSDS i j 南京邮电大学数理学院杨振华制作yangzhenhua 下界 将M N1 i k p 1 N2 l j q 1 代入tSDS i j p q k l 3N1 i k p 1 5 p 1 tD k l 3N2 l j q 1 5 q 1 13得tSDS i j p q k l 3M tD k l 5 p q 3由于tD k l 2 5nD k l 或2 5nD k l 4 有tSDS i j p q k l 3M 2 5nD k l 5 p q 3 0 5M 2 5M 2 5nD k l 5 p q 3M nD k l nSDS i j 南京邮电大学数理学院杨振华制作yangzhenhua 下界 tSDS i j p q k l 0 5M 2 5M 2 5nD k l 5 p q 3再由M nD k l nSDS i j 得tSDS i j p q k l 0 5M 2 5nSDS i j 5 p q 3另外 M表示乘公汽的站数 显然M p q 一共乘了p q次公汽 每次至少一站 我们最终得到tSDS i j p q k l 2 5nSDS i j 5 5 p q 3根据这一下界 搜索不多的p q就得到最小时间 南京邮电大学数理学院杨振华制作yangzhenhua 最小乘车时间模型求解 对第一个点对 i 3359 j 1828 nSDS i j 12 由于增加了地铁 最小站数小了 1 p