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

第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)建立 模拟 公交 车 运营时 的运行 模型，即在 某一确 定调度方 案下，公交 车在该线路 上运 行 过程 的数学 描述。一种 比较切合 实际一些 的是 随机模型，通过 随机模 拟来模拟运 行过程，由 维普资讯 http:/ 工程数学学报 第 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站时段 内，该 站的乘客到达量：维普资讯 http:/ 建 横 专辑 公 交 车词 度 问题 的数 学模 型 1 0 3 高峰时段 候 车超 时率 平 峰时段 候 竺 车 超 时 率 给 定 值 的 比 率 )计算 第 辆车驶 到 J站 后，在该站 实际上车 的乘客数 ：第一 步：按先 到先上 车 的排队原则，确定 在 站的乘客 当第(+1)辆车到达 时，仍 要等 候车辆数 的最大 值 h ，为此解 如下 问题(参看 图 2)：1【(r)J 图2 第二 步：若 =O，说 明此 时该 站上所有候车人 全能上 车，这 样，维普资讯 http:/ 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)：土 维普资讯 http:/ 建堡专辑 公变车调度问题的数学模型 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=上 下行 方向垒 天发 车总 辆数；按 照全程 行车时 间(考 虑每辆车反复 维普资讯 http:/ 1 0 6 工程数学学报 第 1 9 卷 运行)可记 录：上行方 向所 需车辆数(u p b u s)，下行方 向所需 车辆数(d a wnb 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 wnbu 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 中的(5，2，3)较优(黑体)。最 后，特别 要提 及 的是，该 问题 的基本数 据和参数 由北京 市 地铁研 究 所康 海燕 同志提供 编程及 计算 由清华大学 数学科 学系研究 生完 成，在 此对他们 表示感谢。A M a t he mat i c a l M o de l of Bu s S c he d ul i ng TAN Z e-g u a n g J I ANG Qj-y u a n (T s i n g h q a Un i v e r s i t y，Be i J i n g 1 0 0 0 8 4)Ab s t r a c t：I n t h i s p a p e r t h e b a c k g r o u n d o f t h e p r o b l e m a nd i d e a o f m a t h e ma t i c al mo d e l i n g a r e g i v e n A s p e c i f i c m a t h e me t i c al m o d e l a n d c o r r e s p o n d i n g nu me r i c a l r e s u l t s a r e p r e s e n t e d Ke y w o r d s：b u s s e h od u l i n g ma t h e ma t i c a I mo d e l 维普资讯 http:/