关于公交车调度的优化问题.pdf

第1 9 卷 建模 专辑 工程数学学 报。月 J OURNAL OF ENGI NEERI NG M ATHEM ATI CS vo l 1 9 St-叩 Fe b，2 oo 2 文 章编号：1 0 0 5 3 0 8 5(2 0 0 2)0 5 0 0 8 9 0 6 关于公交车调度的优化 问题 傅昌建，杨彩 霞，秦敏 指导老 师：陈敬 敏(四川 丈 学数 学学 院 成 都 6 1 0 0 6 4)螭者 按：车 文 以公 司利益 作 为 目标 函数，以概 率描 述 的乘客 利益作 为 约束 条 件 建立 了完 整 的理论 模 堑。由于具 休计 算 时使 用 了过于 简化 的线 性 规埘模 型，因而善 案稍 大 一些。摘要：车文主要是研究公 变车调度的最优策略问题。我们建立了一十以公变车的利益 为 目标函散 的优化攘 直 同时保1 正 等 车时 问超 过 1 0分钟(或者 超 过 5分 钟)的乘 客人数 在 总的 等车 乘 客教 所 占的 比重 小 于 一十 事 先培 定 的较 小值。首 先 利用 最 小二 乘法 拟音 出 各坫 上(下)车人教 的非参 数分 布 函数，求 解 时先 用 一种 倚单 方法 估算 出最 小配 车敦 4 3 辆。搽后依此为骞厢值 耐用 M p l e 优化工具得到一十整体最优解：最小配车数为 4 8辆，井绐出了在公空车囊喜量 不同条件下的最优车辆诵度方案 使得公司的收益得蓟最太 并且乘客等车的时间不宜过长 最后 对整十模型进行 了推广 和评 价 指 出 了有教 改进 方 向 关 蕾词：公空 车 调度；优化 模 型 最 小 二乘 法 分 类号：AMS(2 0 0 0)9 0 C 0 8 中 图分 类号：T BI I 4 1 文献 标识 码：A 1 问题 的重述(略)2基本假设 1)该公 交路线 不存 在堵 塞现象，且公共 汽车之 间依次 行进 不存 在超 车现象。2)公共汽 车满 载后，乘 客不 能再 上，只得等待 下一 辆车 的到来。3)上行、下行 方 向的头班 车同时从起始站 出发。4)该公交 路线上 行方 向共 1 4站，下行 方 向共 1 3站。5)公交车 均为 同一 型号，每 辆标 准载 客 1 0 0名，车辆 满载 率 不应 超 过 1 2 0 o k，一 般 也不 要 低 于 5 0。6)客车在该 路线上 运行 的平均 速度 为 2 0公 里 小 时，不 考虑乘 客上下 车时间。7)乘客侯 车时 间一 般不超 过 1 0分钟，早 高峰 时一般 不超过 5分钟。8)一开始 从 A 3 出发 的车辆，与一开始从 A0 出发 的车辆不发 生交替，两循 环独立。3 符号说明 N：从 总站 A】3 始发 出的公交车 的总次数(上 行方 向)：从 总站 A。始 发 出的公交 车 的总次数(下行方 向)T1：上行方 向早高 峰发车 间隔时问 维普资讯 http:/ 工程数学学报 第 l 9卷 T 2：上 行 方 向 平 时 发 车 间 隔 时 间 T 3：上 行方 向晚高 峰发车 间隔时间 T ：下 行方 向早高 峰发车 间隔时间：下 行方 向平 时发 车 间隔时 间 T6：下 行方 向晚高峰 发车间隔时 间(，J)：第 i辆车 到达第 j站 的时刻 1(i，j)：在 J站离开第 辆车的 乘客数(，J)：在 J站 上第 辆 车的乘 客数 D(j，J一1)：第 站 与第(一1)站 间距，l()：上 行方 向第 站 的上 车乘客的密度 函数 g 1(j)：上行 方 向第 J站 的下 车乘客的密度 函数 _厂 2()：下行 方 向第 J站 的上 车乘客 的密度 函数 g 2()：下行 方 向第 J站 的下 车乘客的密度 函数 G：一 天 内 公 交 公 司 的 总 收 人 A：公 交 车 出车一 次 的支 出，为定值 B：公交 公 司每 天的 固定 支 出，为定值：=1，2，3，为一小概 率事件 的概 率(t)：某 车站全天 的上(下)车乘 客数：第 时 间段此站 的上(下)车人数 0(，J)：第 辆 车到达第 站时的车上人数 4 建模 前的准备 1)对 问题 的初步分 析 我 们考虑 三组相关 的 因素：公共 汽车，汽车站与 乘客对模 型 的影 响。i)与公共汽 车有关 的 因素：离开公 共汽 车总 站的 时 间，到 达 每一 站 的时 间，在 每一 站 下 车 的乘客数，在每 一站 的停 留时 间，载 客总数，行进 速度等。i i)与车站有关 的 因素：线 路上汽 车的位置，车站间距，乘 客到来的 函数 表示，等车 的乘 客 数，上一 辆车离 开车站过 去 的时间等。i i i)与 乘客有关 的 因素：到达某一车 站的时间，乘车距 离(站数)，侯 车时间等。2)曲线 的拟合 分析样 本 数 据，可 知对 于某 车站 全 天 的上(下)车乘 客 数 ()是 时 间 t的 递 增 函数，N(t)=N(一1)q ，其 中 q 为第 t时间 内此站的上(下)车人数，我们可 以 由此来拟合其分 布函数。由样本数 据知每 一车站 每天有两次 波峰，故 根 据最 f i z z乘 法 将 分 布函数 拟台 为关 于 的 五 次 多 项 式。5分析与 建模 分析 样本 数据，在上行 方 向 2 2：o 0 2 3：0 0和下行方 向 5：0 0 6：0 0的上、下车人 数较 其它 时段偏小，为使 模 型更 好地 体现普遍性，我们 单独讨论上 面的两 个 时段。易 知各 站 只需一 辆车 就可 以满足 需求。维普资讯 http:/ 建模 专辑 美 于公 交 车调 度 的优化 问 题 9 1 由题 设要求 可 知，所求方 案须兼 顾乘客和公 交公 司 的利益，但 实际 上，不可 能 同时使 双方 都 达到晟优值。因此我们 将公 司利益作 为 目标 函数，将 乘 客利益 作 为约束条 件。公 司利 益 Z=G 一(+)A B 其 中 G 为总收人，因样本数据 为典型工 作 日，因而 可 以看作定 值，(+)A+B为 支 出。：+=c +乘 客的利益 在此处 即为侯 车时间，由于乘 客侯 车时间带有 随机性，不可 能总小 于(或大 于)某 个定值，因而 可用概 率来描 述乘客 的利 益，得 如下模 型：f：ma xZ=G 一(+)A B，f P 等待 时间 1 0分 钟的人 1 2 0l n 2 P Q(，J)+(，)一 (i，)5 0 l 5分 钟的人 t 1 2 0 2 P Q(f，)+(i，)一 (i，)5 0 0，i=I，2 分析样本数 据可 以发 现：i)对 于上 行 车 道，A1 3，A1 2，Al 1，A1 0，A9的 上 车人 数 下 车 人 数，对 于 其余 站 点则 相 反；i i)对 于下行 车道，A0，A2，A3，A 的上 车人 数 下车人数，而 其余站 点则相反；因而对 于约 束条件。只 需 取前 5个(或 4个)，对 于模 型，我 们 可 以根 据 拟 合 分 布 函数 F。，G，将 约束条 件转化 为 T 的函数，利用 Ma t l a b软件容易求 解。解 略。分析 所得 结果，易 知在高 峰时间段 中，结果 T有较 大误 差，是 由于拟 合 函数 的误差而 引 起 的。为 了减小 误差，可 以分段拟合 分布 函数 F ，G 。为计 算 方便，可 以认为 在每 小 时内，每 站 的到 达人数 与时 间成 正 比，每 站的下车人数亦 与时间成 正 比，即 F (t)=t，G，()：P ，A 为斜 率，令=5 9 6，于是 将模型 简化为：I l l：ma x T s t 1 9 t一 2 0 0 0(或 1 9 t一 1 0 0 0)1 t一 1 2 0 0 1 t+2 t P2 t一 1 2 0 0 1 t+k 2 t P2 t+3 一 3 t一 1 2 0 0 愚 1 t+愚 2 t P2 t+愚3 t一 3 t+愚4 一 4 t一 1 2 0 0 愚 1 t+2 t 2 t+愚 3“一 声 3 t十愚 4 t一 4 t+愚 5 t P5 t一 1 2 0 0 t 0 (平时及 晚 高峰取 1 9 t一2 0 0 0，早高峰取 l g t一1 0 0 0)当上行时，取所 有约束 条件，下行 时取 前 5个 约 柬条 件。模 型 为线 性 规划，利用 Ma t l a b 求 解，结果 如下：发车 间距 时 间表 5：Oo-6：6：OO 7：O0 7：日：S：5 o 9 0 0 9：O0 1 O oo 1 o：00 1 1：1 1：oo 1 2：o o 1 2：oo 1 3：0。1 3：Oo-1 4：1 0 5 2 2 4 5 1 4 3 4 2 8 4 8 5 4 9 6 2 6 0 3 5 2 5 3 1 3 7 5 6 4 7 9 6 9 2 3 1 1 6 9 2 9 2 6 l 6 2 2 3 3 9 3 9 5 1 6 5 8 7 4 7 3 0 丝 8 6 7 4 7 8 0 8 1 4：0 0 1 5：O 0 1 5：00 1 6：O0 1 6 O0 1 7：0 0 1 7：O0 1 8：O0 1 8：O 0，1 9：D O 1 9：OD 2 0 O0 2 0：0 0 21：0 0 21：O0 22：D O 2 2：0 0 2 3：0 0 8 1 7 2 5 8 2 66 4 3 3 7 5 5 2 5 9 7 4 8 0 2 6 8 1 0 5 2 6 1 0 5 2 6 l O 5 2 6 7 0 7 9 5 5 3 3 2 7 8 7 1 9 9 3 4 2 97 8 9 6 5 9 9 5 9 21 9 0 9 3 0 2 3 1 0 5 2 6 3 注：第 2、5排为 上行，3、6排为下行(单 位皆为分钟)对 模 型、进 行 误 差 分 析 在上 文中，我们 已提及 到模型 的误差，究其原 因主要 是 由于拟合 函数 的误 差引起 的。如 上 行方 向 A1 3站 的 7：O 08：O O 发 车 间距 T=：5 2 6分，显 然此 时 的 T无 法 使 3 6 2 6名乘 客正 常运行，而 此时 由拟 合 函数算 出来 的乘客总数为 2 0 2 3。误差=3 6 2 6 2 0 2 3=1 6 0 3(人)。为使误差减小，因而可 以对 函数 进行 分段拟合。如模型 中，以每小 时为一 段。此时求解 的结果 能很好 的使样 本数据 的乘 客正常运行。当然此 时 的解亦有 误差 ，因而 T 可有 一波 动 维普资讯 http:/ 建模 专 辑 关 于公 交 车调度 的 优化 问题 范 围。在 此解 的情况下，容 易知道 客车满载率 1 2 0(约束条 件)。乘 客等 待 时间过长 的概率 5。空载情形，大部分 只有在最 后一站方 出现空载情形(满 载率 5 0)。2)对 无滞 留 乘 客 条 件 下 的 最 小 配 车 数 初 步 求 解 我们 对数 据 作进 一 步的处理，估算 出每一段上、下行所 需 的 最小 配车 数，从 而得 出一天 内 所需 配备 的最小 车辆 数。为最小 配车数 的求解 找到一个参 照值。我们 首先考 虑 以-s b时 为时间间距来 考查 一天 的最 小配 车数(即设 公 交 车在各 车 站所 停 的时间为一 定值)。分 析数据 可知 满足各 站均无 滞 留乘客，各 发车 时刻均有 车可发 的最 小配车 数应 为 6 5辆 车。这 只是 一 个 初步 解，为得 到进 一步 的精 确解 我们 考 虑 以 4 4分 为一 时 间间 距，通过 拟舍 的分布 函数得到 各车满 载时各时段的所 需最小配 车数。满足各站无滞 留乘客，各 发车时刻均 有车可发 的最 小配车 数为 4 3辆。3】公交公 司调 度 方案模型 的建立 与求解 i)我 们制订 调度方 案，应使公 交 公 司和乘 客双方 的利 益 达 到均衡。一 方 面公交 公 司希 望 配置尽可 能少 的汽车 以降低 固定 成本，又要在保 证接送 全部 乘 客 的前 提下 尽可 能减小 出车 次数，以降低 可变成 本；另 一方面 应 实现乘客满 意，即规定 发 车时 段必 定 有车 可 乘，尽可 能 缩 短等 车 时间。j i)制订调 度方案 时，我们发 现有下难点：A)一方 车站 到 了发 车时 间但 没有 车 可发，另 一方 面却 有 囤积。此 问题 有 两种解 法：一 是 购置 新 车，二是 调节班 次。前 者使成本 变高，后 者引起 连锁 反 应，使整 个 计算 量变 大且有 可 能 求 不 出最 优解。B)若 迫不得 已要改 变 总车配 置数 必须调动 各个 时 间间隔使 车优 化 配置，全局 最优 化。这是一个 最优 问题。c)总 配置 数一定 调 节 总车班 次使总车次 数增加 越少，总 车班 次数 越小，则求 得 的解越 优。这又是 一个极 值优化 问题。为解 决 以上难 点，我们建 立 了一个 线性规划模 型，用 Ma p l e优化 软件求 解。设 某 j 时 间段 发车数为 x 车站 内车辆总数 为 G。=墓 萎 芸 萎 茎 m 为 总 配 置 数，为 总 班 次 m i n z：X s f C0+C=Xl】=Cl Xi i 0 X0 l=C0一 Xm 0 x l=c 1+x o x 1 0 X 0 =C 0+x 1 一 X 0 0 X。=x 1)6 01 2 0调度方 案模型 维普资讯 http:/ 工程数学学报 第 l 9卷 若考虑 到各 站点 乘客上 下车时 间相等，总行程 总需 耗时 6 0分，每 辆车 都载 1 2 0人。在初 步解 的模型 中，配置最小 车辆为 6 0，用 Ma p l e软件包开 始搜索优 化选择，=2，3 1 8。搜索 出整体 最优 解为：C 0=6 2 Cl=4 m=6 6，z=4 7 6，调度方 案 时刻表略。2)4 4 1 2 0调 度 方 案 模 型 考虑乘 客上 下车瞬 间完成，公交车 驶完全程 需 4 4分。每 辆 车均 载 1 2 0人，此 模型 中步长 为 4 4分钟，所 考 虑时段 的乘客数 均 由拟台 函数 给 出，初 始值 为 4 3辆，由 Ma p l e软 件包 优化选 择，得 到：m=4 8 C0：4 2，Cl=6，=5 9 0。调度方 案略。7 模型的推广 与改进 在设计公 交车 调度方 案时 并未充 分考 虑乘 客利益，在进 行改 进 时，可 以试着 想 其它 办法 找到一些更好 的规 则来进 行 对 比与 评价，从 而得 到 更加 优 化 的方 案，使 双方 利益 达 到充 分均 衡 这是模 型改 进 的方 向。另 外，模 型求 得 的数 据相 对 精确度 较 高，在 现 实 生 活 中不太 实用。问题 的关键是 所给 的数据 太少 所得到 的调度方 案稳定 性 很差 灵 敏 度 较高，可 以试 着找 其它 方 法解决，从而 求解。我们建立 了一 个调度 方案 的一般模型，并提 出了一个较 普遍 与实用 的方 法 放此 模型可用 于现实生 活 中其它运 输业 的涠配，类似 交通 运输之类 的调配问题，从而 达 到资源 的优 化配置。8模型的 自我评价 我们通过 一些 台理 的假设，针对公 交车调度 问题建 立 了一 般模型。先对模 型进行 了简化，采用 由简单 到复 杂，逐 步深人 的方法，充分 利用 Ma p l e 优化 软件包进 行搜 索，优 化求解，从而得 到一 个整体最 优解。在求解(2)小题时，提 出一 个方法 即每 次都 从每 段 时 间 的起 点 均有 车发 出，到最后 一班 车持续 等时段发 出，最 后剩余小 段时间丢去 不予 考 虑。列 出了不 同时段 的公交 车调度 时刻表。同时引人 概率 来 刻划 顾 客利 益 从 而 可 以使 抽象 概念 定性分析 定量 化，也是本模 型 的一 大优点。但本题 中因 只给 了某 一个 工作 H的数据 样本，具 有典型性，得 出 的结 果在长 时间 内可行性 较 差，其次 设计 调度方 案 时着重 考虑公 司利益与 大部 分顾 客利 益，使 双方 利 益趋 于 均衡，并 未 同 时达 到 双方 满 意，这 是 我 们 模 型 的缺 点所 在。参考 文献：】姜启 探 数学 模 型 M 北 京：高等 教育 出版 桂 2 1叶其 孝 大学 生 数 学建 模竞 赛辅 导教 材 M 长：胡 南教 育 出版 杜 3 王 拣Ma t bh 5 0与科 学计 算 M 北 京；清华 大学 出版 桂 4j 费培 之，程 中瑷 教 学模 型实 用教 程 M 成都：四川 大学 出J 鹾社 下转 1 0 0页 维普资讯 http:/ 1 0 0 工程数学学报 第 1 9卷 o f b u s e s f i l e i n a nd 0 u t d ur i n g a pera t i o n p e r i o d wh d e w e h a v e n nl y d(t h e r e e a r c h o n t h e u ne v 朗 u da t i o n o f t h e p a 跚 n r fl ow i n t i me an d s p a c e，t he r 删c h 0 n t h e Laws o f ho w t o d i s p a t c h b u s es a r L d we h a ve e a t a b i s h e d a t a x g e t p a n t d ng d wh i th h a s r e a Li d t h e d i s p a t c hin g p l a n o f”【y a nd$O t t te lat e”a n d whe n t he r e a o r e，wh e n t h e r e fl d e e we r Und t h e唧岫 S t a n o 8 o f e n s ur i n g c e r t a i n b en e fi t s a n d t h e s a t i s f a c t io n of p a s s e n ge r s t h e a v e r a l i op e r a t ing t i me of t he bu i n o p er a ti o n ha s b e e n ma d et h e s h o r t t t h e d 卸 a t e lng t i me t a b l e h a s b e e n g o t w k i l et h e n u mb e r rt h el e a t b u 螂i s 4 2 a n d t h e r a t i o Q f s a 吐 di。T 1 t w t t p a s s e n a n d b u s c o mpa m s i s 0 48：0 4 6 Ke y wo r ds：Bu s Di s pa t c hi n gPa s s e ng Fl o w；Ta r g e t Pl an n i ng 上 接 9 4煎 Opt i m i z at i o n of Di s pa t c hi n g Bus e s FU Ch a n g-j inn Ya n g C a i x l a Qi n M i n Ad v i s o r：CHEN J i n mi n (S i C h u a n Un i v e r s i t y，Ch e n g d u 6 1 0 0 6 4)A b s t r ac t：h is t o f ind O U tt h e b e s twa yt o d i s p at c h bu W e s e t a o p t i m iz e d mo d e lwho s et a e t un e dis th e pr of i t o fb t l s c 0 m p a r At t h e s a 他 t i me，i t g u a r a n t ee t h e p r o p o r t i o n t h a t t h e p a&r,e nge w a it i n g f o r the i r b t Is e s II 1 0 t h a n 1 0 mi n(O f 5 min)i n t h e t o t a li s】th a n d g i v e n b e f o r e Fi r s t e e r y s t a t ion s n on p a T a m e t e r d i s t r i b uti o n f cti o n a b o ut t h e n u m b e r o f p i sf i t t e d by me t h o d o f l e a s t s q u a r e s W e s i mp l e m e t h o d t o e s t i ma t e t h a t a t e a s t 43 b n e ed e da r I d t k e n M a p l e t o g e t th e o pt i l s o l u t ion re f e r t o i t I t s h o w s t he b es t p l a n s o r d i s p a t c h i n g b u s e s i n di f f e r e n t e o Li t Lo ns o f t h e n u m b er o f p a s n g e r s I t c B“h e p b 1 l s c o m p an n y t o ge t t h e t op p r o fit m e a n wh i l e t h e p a s s e n g e r s m a y n o t wa i t o r t he i r b u s f o r a l o ng t i me I n t h e en d，we e v a l u-a t e an d p o pu l a r i t h e mo d e 1 an d p o i n t o u t t he e f e ct i v e wa y t o i mpur e i t Ke y wo r d s：di s p a t c l ng b u s e s；o p t i mi d mo d e l；t hed o f e a s t s q 维普资讯 http:/