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

第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 01 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