公交车调度问题的数学模型

第1 9 卷 建模 专辑 工 程 数学 学 报 v l 9 s u 口 p 月 J OURNAL OF ENGI NEERI NG MATHEM ATI C S F e b 2 0 0 2 文章 编 号 1 0 0 5 3 0 8 5 2 0 0 2 0 5 0 1 0 1 0 6 公 交 车调度 问题 的数学模 型 谭 泽光 姜启源 清华 大学 北 京 1 0 0 0 8 4 捕要 给 出奉 问题 的 背景 建模 思路 一 个具 体 的确定 性数 学模 型 及 相应 的计 算 结果 关 词 公文 车 调度 运行 模 型 多 目标规 划 丹 赛号 A s 2 o o O 9 0 09 8 中国井 粪号 T BI 1 4 t 空麻 标识 码 A 1 问题的背景和要求 公交车 调度 问题 的背景 是某大城 市公交部 门提 出的一个 实际科研课 题 该课 题要求对 一 条确定 的公 交路线 解决 三个方 面的 问题 第一 根 据历史 积 累和必要 的补充调查数 据 提 出沿路 各站来 站 与离站 的乘客分布规 律 第二 研 制一个 模拟该 线路公 交运行过程 的数学模 型 第三 在前两 条的基 础上 为该 线路 提 出一 个配 备 车辆 和 司 机 售 票员 人员 数 目的方 案 以及 一个在 通常情况 下车辆 的运行时 间表 根据这 个背景 我们 在有 关人员 的大力支持下 对 问题 作 了大 幅度 的简化 提 出了如下 建 模问题 首先 选择 了该 市一条 比较 典 型 的公 交 线路 沿 线上 行 方 向共 1 4站 下 行方 向共 1 3 站 根据 多年来沿 线各 站乘客 来 离站 的人数调 查数据 给 出 了该 线 一个 工作 日两 个运 行方 向 各站上下 车的乘 客数量按 时 间的分布 为简单 明确起见 同时假 设 公交公 司配给该 线路 同一 型号的大客 车 每辆标 准载客 1 0 0人 客车在该 线路 上运 行 的平 均 速度 为 2 0公 里 J 时 并顾 及 社会效益 对运 营调度提 出的基本要 求 为 乘客候 车 时 间一般 不要 超 过 1 O分 钟 早 高峰 时一 般不要 超过 5分钟 车辆满载 率不应超 过 1 2 0 同时又考 虑到 提 高公 交公 司运 营效 益 提出 了车辆满载 率一 般也 不要低 于 5 0 的指标 问题要 求根 据上述 数据 在尽可 能适 当考 虑公交 社会效益 和公 交公 司利益 的 目标下 为该 线路设 计一个便 于操作 的仝 天 工作 日 的公 交车调度方 案 即两个起 点站 的发车时刻表 并 指 出实现这个 方案 至少需要 配 备多少辆车 给 出这 种方案 照 顾乘 客和 公交 公 司双 方 的利益 程度 的数量 指标 从 而将 这个调 度 问题抽 象成一个 明确 完整的数学 模型 并指 出求解模 型的方法 2 建立模型的思路和框架 该 调度 问题 可 分成 三个 子问题 1 建立 模拟 公交 车 运营时 的运行 模型 即在 某一确 定调度方 案下 公交 车在该线路 上运 行 过程 的数学 描述 一种 比较切合 实际一些 的是 随机模型 通过 随机模 拟来模拟运 行过程 由 维普资讯 更多数学建模资料请关注微店店铺 数学建模学习交流 工程数学学报 第 l 9卷 决策 变量 及原 始数据 取得要求 的各种 目标数值 另一种 是建立确 定性 模 型 把 运行过 程看作 一 个 按一定时 间表 发 车的 公交 车 在一定 要求 下 顺序将沿 线乘客送 达 璜定 地点 的确定过程 2 通过 运行 模 型优 化所 需的 目标 本 问题实 际上 是一 个多 目标规 划 至 少有 二个 目标 要考 虑 一 个是反 映乘客 利益 的乘 客等 待时 间 另一个是 反映公交 公司利 益的载客 率 如何通 过优 化算 法 求解 这个双 目标规划 是该模 型 的第二 个问题 3 配车模 型 即确定 实现调度方 案所需的最步 车辆 数 这 是一个 带时序 的分配问题 3 建 立确定 性模 型的一 个例子 1 运行模 型及其 求解 1 己知 数据 车 站标记 1 2 来 客密度 在 时刻 t到达 J站乘客的密度 u j t J 1 2 下车 乘客 密度 在时刻 t 从 站下车乘客 的密度 t j 1 2 n 站间行 车时间 从 J一1 站 到J站站间行 车时间 包括 在 站 的仃车时 间 J 2 一 n 每辆 车的载客容量 B 载客 容量上限 百 交 通高 峰时段等 待时间上界 i 交通 平峰时段 等待时 间上 界 t 2 决 策变量及 相关变 量 决 策变 量 发车 时刻表 向量 T To Ti T T 其 中 To 第一辆 车 到达 起点 站 J 1的时刻 第 辆车驶 离起 点 站J l的时刻 1 2 m 相关 变量 盘 第 辆 车驶 离J站 的时刻 T k 1 T k i Tk 1 J 2 3 一1 f 1 第 辆车驶 离j站时该 车上 的乘 客数 T k 1 2 m 1 2 n一1 第 k辆 车驶 到J站 时 该站 上候 车乘客的分布 函数 w 0 从 一 1 到 T 目时段 的来客数 第 k辆 车驶 到J站时 该站上 己等侯过 h趟车仍 未能上 车的乘客数 第 辆车驶到 j站 时 该 站上等待最久 乘客的候 车趟数 w 0 1 0 运 行模 型 框图 图 1 见下 页图 3 相 关变量 的计算公 式 第 k辆 车驶 到 站后 等到该站 的乘 客下完后 车上仍 留下 的乘客数 d m a x t 一 1 d t 0 第 辆 车驶到j站后 等 到该站 的乘客下完 后 j站可容 纳的上 车乘客数上界 b B 第 k一 1辆车 驶离 站到第 辆车驶到J站时段 内 该 站的乘客到达量 维普资讯 建 横 专辑 公 交 车词 度 问题 的数 学模 型 1 0 3 高峰时段 候 车超 时率 平 峰时段 候 竺 车 超 时 率 给 定 值 的 比 率 计算 第 辆车驶 到 J站 后 在该站 实际上车 的乘客数 第一 步 按先 到先上 车 的排队原则 确定 在 站的乘客 当第 1 辆车到达 时 仍 要等 候车辆数 的最大 值 h 为此解 如下 问题 参看 图 2 1 r J 图2 第二 步 若 O 说 明此 时该 站上所有候车人 全能上 车 这 样 维普资讯 1 0 4 工程数学学报 第 1 9卷 第 三步 若 P 且 置 W k j h 同时令 h 0 0 0 说 明此 时该 站上候车人 不能全上 车 这 样 同 时令 h 1 1 1 wH h 0 1 一1 l J w 一 这样 我们 有 第 k辆 车驶 离 站 的时该 车上 的乘 客数 P P f n 若 0 0 百 若 0 k 1 2 一m J l 2 一1 t4 目标值 的计算 第 k辆 车驶 到 站时 该站上 己等候 h趟车 的乘客数 是 wb h h 1 他们 已等 侯 的时 间是 w 一 一 h 1 H 确定 交 通高峰 时段 E t1 t 整个 时段 T1 T 则 交 通 高 峰 时 段 候 车 超 时 率 壹 些 堕 譬 蓄 馨 譬 辜 墨 记 作 f WT h 5 1 I t 2 一 交 通 平 峰 时 段 候 车 超 时 率 壬 监 堕 等 莲 磬 堂 厶 塑 记 作 0v e t W 2 T I 1 0 1 t 2 满 载 率 低 于 5 0 的 段 数 百 分 比 孽 蓑 记 作 I C a p L o w T 土 维普资讯 建堡专辑 公变车调度问题的数学模型 1 0 5 5 优 化模 型 求 T T0 Tl I T2 rr m 使 得 m i nC 口Ov e r W 1 T 卢Ov e r W 2 T 十 C a p l o w T 其 中 为给定 的权 重 系数 关 于决 策变 量可 以简化为 分段 等时分布 即先确定高 峰时段 和平峰 时段 在这 两 种时段 内等 间隔发 车 这样 变量就 少多 了 6 模 型求解 无约束 优化 问题 直 接法 如复 合形方 法 数 值微分 的 下降方 法 等 在 实际求 解 中 如果 决策 变量不 多 利 用求 出一 系列可行解 的方 法 求出近似最优解 也是 可取的 2 配 车模型及 其求解 在分别 求 出上 下行 两个方 向的优化后 的调 度 时间表 之后 就可 以进行配 车 该模型可 图 示如 图 3 其 中两个 时间轴 轴上 虚线 表示上行 车辆 虚线带 箭 头的线 表示 上行 转 为下行 轴上 实线 表示下行 车辆 实线 带箭 头的线表示 下行转为上行 围3 这 里只是一 种模 型 实 际上做 法 是多 种多样 的 从 建模 的角度 看 把 上 下行 分 开 将运 行 与配车两个模 型分 开 都是 简化 不过这 可能是必 要 的 否 则 问题 会变 得 很 复杂 以至 于无 法 求解 数值 计算结果 根据所 给数 据 按 照上述模 型的基本思 路 用 给定发车 间隔 计 算 目标 函数 通过 比较选优 的办法 提供合适 的方案 1 假设用 所给数 据 中每 时段 1小时 在 每一 站 的上车 人 数和 下车 人数 就是 该时 段 到 达该 站和离去 的人数 即通过 这些 数据计算 出 t 和 d t 2 用所 给数据 中站 间距 和平均 车速 忽略 上下车时 间 得到 B 1 0 0 B 1 2 0 3 根据 所 给数据 中始发站 的上车人数 确定早 晚高 峰时段为 早高 峰 6 4 O 9 4 0 晚 高峰 1 5 5 0 1 S 5 0 于是 全天分为 3 个时段 平峰 时段 早 高峰时 段 f 2 晚高峰时段 3 高峰时段等 待 时间上界 5 分钟 平 峰 时段等 待时间上界 f 1 0 分钟 4 给定 决策变 量为 3个时段的发 车间隔 I 几 J 3 由此 可计算 出 T0 丁l T 5 对于上行和下行方向均可计算 得到如下结果 记 O v e r W1 早高峰时段候车超时 率 Ov e r W 平峰 时段 候 车超 时率 C a p l o w 满载 率低 于 5 0 的段数 百分 比 选择 极重系 数 n 口 均为 1 3 得 目标 函数 c 计算 中可记 录 To t a l 上 下行 方向垒 天发 车总 辆数 按 照全程 行车时 间 考 虑每辆车反复 维普资讯 1 0 6 工程数学学报 第 1 9 卷 运行 可记 录 上行方 向所 需车辆数 u p b u s 下行方 向所需 车辆数 d a wn b u s 为保证每 个始发 站每天早 发车前 与晚收车后 的车辆 状态 都不 变 给定 的发车 间 隔有 下列 两 种 A 上行 与 下行 方 向发车 时间间隔相 同 1 2 3 Ov e r W2 Ov e r Wl C a p I O W C T 0 t u p b u s d o wn bu s 3 2 2 0 0 0 0 6 0 0 9 4 1 J 0 6 1 7 5 0 2 3 7 4 4 2 0 2 2 2 2 4 2 3 0 0 4 8 8 0 1 1 6 1 0 4 1 4 0 0 1 9 3 0 3 3 L 2 2 2 2 4 3 3 0 1 0 1 6 0 3 1 9 4 0 4 0 3 L 0 2 7 4 7 3 0 1 1 5 1 5 5 2 3 0 0 5 1 7 0 1 3 3 6 0 3 3 9 0 0 1 7 4 8 2 9 5 2 2 2 2 5 3 3 0 L 2 0 4 0 3 5 8 5 0 3 1 5 0 0 2 6 4 6 2 6 5 1 5 1 5 5 2 4 0 1 5 6 5 0 1 3 3 6 0 3 3 0 1 0 2 0 6 7 2 8 0 2 2 2 2 6 2 2 0 0 3 6 4 0 1 6 3 2 0 3 4 1 4 0 1 8 0 3 2 9 9 2 2 2 2 6 3 3 0 1 3 4 4 0 3 7 0 4 0 2 5 4 7 0 2 5 3 2 2 4 0 1 5 1 5 B 上 行 与下 行方 向早 高 峰和晚高 峰时间间隔对换 如 4 3 2 表示 上行 为 4 3 2 下行为 4 2 3 J1 J 2 3 Ov e r W 2 Ov e r W l Ca p l O W C T0 t u p b u s d o wn b u s 4 3 2 0 0 1 8 4 0 i 7 3 3 0 4 1 2 6 0 2 0 1 4 3 3 0 4 5 1 5 4 2 3 0 0 8 6 0 0 2 5 4 7 0 4 5 0 7 0 2 6 3 8 3 3 1 1 5 4 5 5 3 1 0 0 2 5 2 0 0 8 4 2 0 5 6 7 2 0 2 2 5 5 3 8 5 1 3 5 1 5 5 3 2 0 0 2 5 0 0 l 9 I 2 0 3 3 4 1 0 1 8 3 4 2 9 5 4 5 t 5 5 2 3 0 1 0 3 5 0 2 9 3 3 0 3 7 9 0 0 2 5 8 6 2 9 5 1 5 4 5 5 3 3 0 l 2 0 4 0 3 5 8 5 0 3 1 5 0 0 2 6 4 6 2 6 5 1 5 1 5 5 4 2 0 0 9 2 2 0 2 9 L 2 0 3 2 6 0 0 2 3 6 5 2 8 0 5 6 1 1 6 3 2 0 0 5 2 8 0 2 2 0 3 0 2 7 9 3 0 1 8 4 1 2 6 9 4 5 1 5 从 以上各种 方案 的 目标 函数 C及所需 车辆数看 A 中的