关于公交车调度的数学模型

公交公交车调车调度度 关于公交关于公交车调车调度的数学模型度的数学模型 摘要 本文根据典型的一个工作日两个运行方向各站上下车的乘客 数量统计 首先探讨了如何利用平滑法来确定一个有价值并且效率高的 车辆运行时刻表 使其满足乘客的舒适性和公交公司低成本的服务 接着 又利用最优化的基本思想 对此问题进行了进一步的讨论 得到了最小配 车辆的数量 然后针对满意度的评价水平问题 建立了几个良好刻画公司 以及乘客满意度的满意度函数并求出了乘客与公交公司双方的满意度 最后 我们对新提出的模型进行了模型的评价和模型改进方向的讨论 并 对如何采集公交车客运量的数据 提出了几个中肯的建议 完成了对关于 公交车调度问题的较为详细而合理的讨论 一 一 问题问题重述重述 公共交通是城市交通的重要组成部分 作好公交车的调度对于完善城 市交通环境 改进市民出行状况 提高公交公司的经济和社会效益 都具 有重要意义 下面考虑一条公交线路上公交车的调度问题 其数据来自我 国一座特大城市某条公交线路的客流调查和运营资料 该条公交线路上行方向共 14 站 下行方向共 13 站 第 3 4 页给出的 是典型的一个工作日两个运行方向各站上下车的乘客数量统计 公交公 司配给该线路同一型号的大客车 每辆标准载客 100 人 据统计客车在该 线路上运行的平均速度为 20 公里 小时 运营调度要求 乘客候车时间一 般不要超过 10 分钟 早高峰时一般不要超过 5 分钟 车辆满载率不应超 过 120 一般也不要低于 50 试根据这些资料和要求 为该线路设计一个便于操作的全天 工作日 的公交车调度方案 包括两个起点站的发车时刻表 一共需要多少辆车 这个方案以怎样的程度照顾到了乘客和公交公司双方的利益 等等 如何将这个调度问题抽象成一个明确 完整的数学模型 指出求解模型的 方法 根据实际问题的要求 如果要设计更好的调度方案 应如何采集运 营数据 二 定 二 定义义与符号与符号说说明明 1 T I 第 I 个时段 I 1 2 18 2 A J 第 J 个公交车站 J 1 2 15 3 P I 在第 I 个时段内的配车量 4 L I 在第 I 个时段内的客流量 5 G I 在第 I 个时段内的满载率 6 S I 在第 I 个时段内的乘客候车时间期望值 7 V 客车在该线路上运行的平均速度 8 L J 第 J 1 个公交车站到第 J 个公交车站之间的距离 9 T I 第 I 个时段内相邻两辆车发车间隔时间 10 L 收 发车站之间的距离 三 模型的假 三 模型的假设设 基本假设 1 乘客在各个时段内到达公交车站的时间均服从均匀分布 2 乘客上车的时间可以忽略不计 3 公共汽车在每个时段内发车的时间间隔相同 4 公共汽车始终以大小为 V 的速率匀速前进 5 公交车和乘客的到来都是随机现象 被调查的线路上的客 流量不会受到其它线路上客流量的影响 6 如果产生拥挤现象 那么仅可能是在车站发生 四 模型的分析 四 模型的分析 1 数据的特征分析 为了加深对数据变化情况的了解 我们对数据进行了插值 并绘出 公交 车上行客流量数据总图 图一 由图中我们可以直观地看到 1 对于不同的车站 A J J 1 2 14 在 T 3 时段 7 00 8 00 处 均达 到客流量的最高峰 2 对于不同的车站 A J J 1 2 14 在 T 13 时段 17 00 18 00 处 均 达到客流量的次高峰 3 在其余时段内 客流量分布较为平缓 图一 2 模型的初步分析 由于编制车辆运行时刻表的复杂性 传统的时刻表一般是采用经验法 即参考路线的客流量情况和路线计划配车数 确定运行时间 周转时间及 间隔 以下是应用于计算的理论公式 运行时间 运行线路长度 车速 60 2 周转时间 运行时间 规定站停站时间 0 行车时间 小时 小时通过的车次 配车数 一次周转时间 行车间隔 发车间隔 周转时间 配车数 通过以上的计算公式计算出各个参数 然后考虑早晚高峰 首末班车 的发车时间 路上行车的实际情况等若干因素 并结合以往丰富的经验确 定行之有效的运行时刻表 五 模型的建立与求解 五 模型的建立与求解 模型模型 1 平滑法模型 平滑法模型 采用确定公交调动中发车间隔的方法来寻求最优的发车间隔时间 进而求得整条线路的最小配车数 编制出一套较为实用的车辆运行时刻 表 1 发车间隔的具体计算方法讨论 确定发车间隔的原则是 正确处理好车辆的供给和乘客的需求关系 既要保证有足够 的服务质量 又要保证配车数最小 应用于计算的具体公式 Pi Di ki C Di Ni 1 Pi Hi ki C Hi Ni 2 Pi max Qi E G i C L Hi C max Qi Ni L Hi C 3 其中 Pi i 时段内的配车数 车次 Di i 时段内的日最高流通量 Hi i 时段内的小时最高流通量 C 车的最大容量 E G i i 时段内的期望满载率 Ni i 时段内的期望占用量 人 Qi i 时段内的乘客周转量 人 km 步 骤 1 我们从题目所给的 典型工作日两个运行方向各站上下车的乘客数 量统计表转化为便利于我们计算的基础数据表 我们取定几个时间段作 为分析样本 结果见下表 注 表 1 中的断面客流量 Li 算公式 上行 Li max Ri 0 下行 Li max Ri 0 Ri R i 1 ui di Ri R i 1 ui di Ri 第 i 个站的断面客流量 R i 1 第 i 1 个站的断面客流量 Ui 第 I 个 站点的上客量 di 第 i 个站点的下客量 基基础础客流量数据表 下行 客流量数据表 下行 站 距 km 站名06 00 07 00 07 00 08 00 08 00 09 00 09 00 10 00 A0795232827061556 1 56A2868241428141603 1A3995298531481777 0 44A41039275232231822 1 2A51006246228771647 0 97A6989231725371444 2 29A7903174020141108 1 3A889315381830975 2A993014951817974 0 73A1086611771509774 1A1184410501425737 0 5A127527221435545 1 62A13 周转量 人公 里 12628 5726627 5430514 1117445 41 平均断面通过 量 人 866 21828 32092 91196 5 车容量 人 120120120120 期望满载率96 99 5 99 8 98 75 期望占用量 人 115 4119 7119 7119 5 表 2 步骤 2 确定时段配车数 Pi 车次 间 隔 Hd min 上行数据 方法 1方法 2方法 3时间段 PiHd m in PiHd m in PiHd m in 06 00 07 00 6 00106 00105 8410 27 07 00 08 00 23 922 5242 524 522 45 08 00 09 00 41 091 43421 4342 121 43 10 00 11 00 21 642 73222 7322 542 66 表 3 步骤 3 确定相邻时间段的间隔 从表面观察数据可知 两个相邻时间段之间有一定的联系 我们的目标就 是要找出相邻时间段 如 5 00 6 00 与 6 00 7 00 之间的转换段内的发 车时间 基本思路基本思路 对于相邻的两个时间段来说 前一时间段内发的车是有可能运载后一 时间段内的 乘客 这是因为一个时间段为一个小时 在这么长的时间里 如果发车时间跟时间段的上限值接近 如 5 00 6 00 中 6 00 就是上限值 发车时间若为 5 50 则它就很接近 6 00 则该趟车还未走完上行或下行的 路线就已经进入下一个时间段 基本原理基本原理 确定两相邻时间段的发车数和发车时间的相互影响 平均间隔法是一 种最简单但又粗略的方法 它计算出来的结果有可能导致在一条运行路 线上出现过分拥挤或者车辆利用率不足的现象 下面采用的是平滑法 使 用平滑法将运用到步骤 2 中的计算结果 根据步骤 2 计算的时段配车数 先确定在前一时段内第一辆车的发车时间 而在相邻时段之间的转换段 内综合考虑前后两种配车数 设置平均期望占用量而不是平均间隔 例如 在 7 00 8 00 8 00 9 00 两个时间段内 假设 第一辆车为 7 00 发车 根据表 3 两个时段内的配车数和发车间隔分别为 23 92 车次 2 5 min 42 车次 1 43 min 前一段时间所须要的配车数的 0 92 车次被留在 7 57 之后 与下一时段的 0 08 车次结合 因此 0 92 车次的期望占用量为 116 8 人 0 08 车次的期望占用量为 120 35 后一时间每分钟需求的配车 数 斜率为 42 60 相应的 0 08 车次要运行 0 08 42 60 1 15 min 所以 求得后一时间段内第一辆车发车时间为 8 02 几种不同的间隔确定方法 方法 1 采用公式 2 Pi Hi ki C Hi Ni 方法 2 采用公式 3 同时增加了限制时间段内通过量大于 Pi C 的线路 长度 Pi max Qi E G i C L Hi C max Qi Ni L Hi C 方法 3 综合运用法 该方法的特点是将不同的方法运用于不同的时间段以确定时段配 车数 它最大的好处就是能够根据实际情况作灵活的动态调度 比如可以 根据高峰期和平峰期到来的时间段及流动数量的多少来选择不同的方法 确定理想的配车数 模型模型 2 根据基本假设 1 4 我们着手建立关于总配车量 A Pi Pi I 1 18 的优化模型 1 确定决策变量 易见 Pi 可作为模型的决策变量 但注意到 Pi 60 T i 5 Pi 60 T i 6 其中 T i 为上行线路 i 时段内的发车间隔时间 单位 分钟 T i 为下行线路 i 时段内的发车间隔时间 单位 分钟 所以 可以等价地将 T i 作为 决策变量 2 确定目标函数 问题 1 的目的是为了寻找在满足乘客和公交公司双方的一定利益 的情况下 总配车量 A Pi Pi 的最小值 将 5 6 式代入 可得总 配车量 A 为 A 60 T i 60 T i i 1 18 3 确定约束条件 1 首先 乘客候车时间一般不要超过 10 分钟 早高峰时一般不要超 过 5 分钟 由假设条件4 乘客的到来满足均匀分布 则在第 I 个时段内的流通的乘客候车时间期望值 E S i 满足 E S i t k 1 T i dt T i i 1 18 T i 2 所以我们有 T i 2 10 i U T i 2 10 i U T i 2 5 i V T i 2 5 i V 其中 集合 U 为上行早高峰期的时段集合 U 为下行早高峰期的时 段集合 V 为上行非早高峰期的时段集合 V 为下行非早高峰期的时 段集合 为了获得对早高峰期的明确时间范围 我们将客流量的数据进行 了线性插值处理 并将 14 个车站作为 14 个样本 利用聚类分析的方 法可以得出如下早高峰期定义 上行早高峰期为 6 00 9 00 下行早高峰期为 7 00 10 00 2 其次 车辆满载率 G i 不应超过 120 一般也不要低于 50 即 G i 1 2 7 E G i 0 5 8 又因为在每个时段内都应该尽量满足乘客的最大客流量 所以 G i C 60 T i Hi 9 我们将 9 代入 8 7 再区分上下行可以得出相应的约束条 件如下 Hi C 60 T i 1 2 i 1 18 Hi C 60 T i 1 2 i 1 18 E Hi C 60 T i 0 5 i 1 18 E Hi C 60 T i 0 5 i 1 18 4 优化模型的建立 通过 1 3 的分析 我们建立优化模型 如下式 min A 60 T i 60 T i i 1 18 st T i 2 10 i U T i 2 10 i U T i 2 5 i V T i 2 5 i V Hi C 60 T i 1 2 i 1 18 Hi C 60 T i 1 2 i 1 18 E Hi C 60 T i 0 5 i 1 18 E Hi C 60 T i 0 5 i 1 18 4 优化模型的求解 方法 1 由于 1 中含有决策变量以及其期望值 属于非线性概率 规划范畴 不利于显式求解 可以利用时间步长法进行模拟 进而获得最 优值 方法 2 将 中的约束条件 E Hi C 60 T i 0 5 i 1 18 E Hi C 60 T i 0 5 i 1 18 修改为 Hi C 60 T i 0 5 i 1 18 Hi C 60 T i 0 5 i 1 18 并且令 B i 1 T i 则原规划 可以化为如下线性规划 min A 60 B i 60 B i i 1 18 st B i 1 20 i U B i 1 20 i U B i 1 10 i V B i 1 10 i V 1 0 5 C 60 B i Hi 1 1 2 i 1 18 1 0 5 C 60 B i Hi 1 1 2 i 1 18 利用数学规划软件 Lindo 可以获得其解 模型 3 1 我们在这一小节将讨论 我们的方案以怎样的程度照顾到了乘 客和公交公司双方的利益 为了评价不同方案对乘客和公交公司双方的利益的照顾水平 我们将着手建立乘客和公交公司的满意度函数 1 乘客满意度函数 Y1 容易看出 乘客满意度函数 Y1 为整个时段的乘客候车时间的期 望值 E T 与公交汽车上的乘车拥挤度 w 的函数 令 Y1 a E T 1 a w 0 a 1 则函数 Y1 具有以下三个性质 1 E T 0 则 Y1 1 E T 10 则 Y1 0 1 其中 E T 0 则 Y1 0 1 为我们根据实际情况作出的假定 2 w 0 则 Y1 1 w 1 则 Y1 0 3 Y1 分别为 E T w 的凸函数 不妨假设 Y1 分别为 E T w 的二次凸函数 由 1 2 3 可知 Y1 E T 以及 Y1 w 的图象以及函数方 程如下所示 其方程为 Y1 1 0 009 E T 2 其方程为 Y1 1 w 2 取 a 0 7 综合可得 Y1 0 7 1 0 009 E T 2 0 3 1 w 2 2 公交公司的满意度函数 公交公司的满意度函数 Y2 为满载率的期望值 E G 的函数 且 函数 Y2 具有以下三个性质 1 E G 0 则 Y2 0 E G 1 2 则 Y2 1 2 Y2 为 E G 的凸函数 不妨假设 Y1 为 E G 的幂函数 由 1 2 可知 Y1 E T 的图象以及函数方程如下所示 方程 Y2 5 6 E G 0 5 3 总结 由模型 1 2 确定出 E T E G w 则由 1 2 中的满意度函数即可以 求出乘客和公交公司双方的满意程度 模型 模型 为了在获得最小配车数量的同时 兼顾了乘客以及公交公司双方的满 意程度将模型 和模型 想结合 可以得到如下的多目标规划模型 min 60 B i 60 B i Y1 Y2 i 1 18 st B i 1 20 i U B i 1 20 i U B i 1 10 i V B i 1 10 i V 1 0 5 C 60 B i Hi 1 1 2 i 1 18 1 0 5 C 60 B i Hi 1 1 2 i 1 18 其中 Y1 0 7 1 0 009 E T 2 0 3 1 w 2 Y2 5 6 E G 0 5 6 模型的 模型的检验检验与与结结果果 模型模型 1 时间段 Hd 发车间隔时 间 上行 min P 时段配车 数 上行 次 Hd 发车间隔时 间 下行 min P 时段配车数 下行 次 5 00 6 0010691 6 00 7 002 5246 79 7 00 8 001 43422 623 8 00 9 002 7222 327 9 00 10 004 6134 115 10 00 11 006 796 79 11 00 12 005 5117 58 12 00 13 006108 67 13 00 14 006 797 58 14 00 15 001067 58 15 00 16 007 585 511 16 00 17 003 5173 318 17 00 18 002 6231 931 18 00 19 007 58320 19 00 20 001546 79 20 00 21 00203106 21 00 22 002038 67 22 00 23 00 1203 说明 在一个时间段内 公司发车的总次数为 P 它们以均匀的发车时间间隔 Hd 均匀发车 比如 说 在 12 00 13 00 这个时间段内 它从 12 00 开始发车 每隔 10 分钟发一辆车 计算结果 上行的发车数量为 42 辆 下行的发车数量为 31 辆 对上 下行的发车时刻以及顾客的流量进行均衡调度 由下式 A min 42 31 14 58 20 60 60 53 2 即得最小配车数量 A min为 54 辆 模型模型 2 计算结果 上行的发车数量为 44 辆 下行的发车数量为 32 辆 对上 下行的发车时刻以及顾客的流量进行均衡调度 由下式 A min 44 32 14 58 20 60 60 55 4 即得最小配车数量 A min为 56 辆 乘客平均等待时间 E T T i 2 18 2 78 分钟 i 1 18 平均满载率 E G G i