公交车的调度

第1页 共 24页 作者:贾 鹏 , 王 莹 , 欧阳坚 , 本文获全国一等奖 公交车的调度 摘要: 本文讨论城市公交车的高效调度问题 对主要因素进行了细致研究 为了得到一个简 单又高效的调度方案 两个起点站的发车时刻 需要的车辆数等 我们把问题归结成一 个阶段不确定多阶段动态规划问题 递进的建立了五个模型 模型一以一定的时段等分工作日 在同一时段内等间隔发车 使乘客只等一趟车 用计 算机搜索 最大化满足约束条件的发车间隔 以 30 分钟为时段得到发车时间表 得出上行 时 7 30到 8 00的发车间隔最小 为 1.4分钟 下行时 17 30到 18 00的发车间隔最小 为 1.9分钟 共需要车 56辆 工作日总车次 468次 模型二令等分工作日的时段趋于零 得到一连续的发车速度曲线 )(tf 由它构造发车时 间表 工作日总车次的最小值为 457次 模型三从上下行的数据表中发现各时间的同一车站 同一时间的不同车站 上下车的平 均人流的比例关系很稳定 故将一张表简化成两个向量表示 给出发车时间表 共需要车 74 辆 工作日总车次 606次 模型四考虑乘客等多趟车的情况 给出一个乘客不满意度函数 允许乘客采用别的交通 方式离开车站 同时保证总共等车时间不能超过一个数值 得出的结果为共需要车 53 辆 工作日总车次 427次 模型五考虑各种随机因素 给出了用计算机模拟的求解方法 最后我们考虑对发车时间表调整 在适度增大车次情况下减小了需要的车数 调整后 模型一需要车 49辆 工作日总车次 475次 模型三需要车 70辆 工作日总车次 625次 第2页 共 24页 一.问题的提出 公共交通是城市交通的重要组成部分 具有重要的意义 要求根据我国一座特大城市 某条公交线路上一个典型的工作日两个运行方向各站上下车的乘客数量的统计数据 为该线 路设计一个便于操作的全天 工作日 的公交车调度方案 包括两个起点站的发车时刻表 一共需要多少辆车 这个方案以怎样的程度照顾到了乘客和公交公司双方的利益 并将这个 调度问题抽象成一个明确 完整的数学模型 指出求解模型的方法 根据实际问题的要求 如果要设计更好的调度方案 应如何采集运营数据 设该条公交线路上行方向共 14 站 下行方向共 13 站 公交公司配给该线路同一型号的 大客车 每辆标准载客 100 人 据统计客车在该线路上运行的平均速度为 20 公里/小时 运 营调度要求 乘客候车时间一般不要超过 10 分钟 早高峰时一般不要超过 5 分钟 车辆满 载率不应超过 120% 一般也不要低于 50% 二.问题分析 从统计表中容易看出该公交车的行驶路线是同一条路的两边 只是上行时比下行时多停 一站 A1 由于各站所处地区的人口密度不同 不同时间对不同地区的人流情况的影响也 不同 所以同一时刻单位时间内到达不同站的人数 不同时刻单位时间内到达同一车站的人 数都是各不相同的 公交车运营通常通过起点站 终点站处发车时间来调节 比如在早晨和 深夜适当延长发车间隔以降低运营成本 在上下班高峰期适当缩短发车间隔 以满足人们的 出行需要 但降低运营成本与满足人们的需要是相互制约的 较好的调度方案能通过等车人数不同 时间不同站点的分布特点 给出公交车起始站和终点站的发车时刻表 在满足人们的需要 少 等车 的情况下 尽量降低运营成本 少用车次 使运营成本与乘客在系统中逗留费用之 和的期望值最小 如果尽量加大发车时间间隔,就等效于减少车次 因此我们把模型的目标之一定为最大 化发车间隔.但这样会增大乘客等车时间,因此我们必须在目标或约束条件中体现出对乘客的 考虑 客车从线路一端走到另一端需要大概 44 分钟 而乘客流分布是以整点时段内均匀分布 计算的 如果客车在 6:00从 A0开往 A13,则全段行驶时间都在 6:00-7:00 间,这时上车下车的 乘客流就应该以 6:00-7:00的数据为标准 但如果客车在6:40从A0开往A13,当它到达A11,A12 时必然过了 7 点,这样上车下车的乘客流就应该以 7:00-8:00 的数据为标准.这种 越界 问题 增加了解题的复杂程度 另外需要注意的是所用车次尽量少 并不能保证所用的总车辆数是最少的 所以我们在 尽量减少车次的前提下再对车辆数进行优化 令之达到较满意的程度 三.模型假设 ( )1 表中的数据有代表性 能反映该路线乘车人按时间和站点分布的普遍情况 ( )2 乘客上下车时间及到达两个终点站 A0及 A13的周转时间忽略不记 ( )3 客车在行驶中保持匀速, 即 20公里/小时.途中不会出现阻塞现象 第3页 共 24页 ( )4 乘客等车时间不允许超过 10分钟,早高峰是一般不能超过 5分钟 ( )5 车辆满载率不超过能 120%,一般也不低于 50% (满载率为客车运行期间车上的乘 客数量与标准载客量的比值) ( )6 各个站点在 00:2300:22,......,00:700:6 ,00:600:5 ®®® 各整点时段内到达时刻 是均匀分布的 即单位时间内等车人数增加量相等 ( )7 调度时间精确到分钟,因为在实际生活中,调度时间过于精确不可能也没有必要 ( )8 规定具体时间段内,如 00:2330:22,......,00:630:5 ,30:500:5 ®®® 发车间隔是固 定的. 四.符号 0t :第一辆车发车时间 1, +iil :第 i站与 1+i 站的距离 )12,0( L=i v :车速 tD :发车间隔 ijp , :第 j辆车在第 i站上完乘客后车上的乘客数 maxT :允许的最大发车间隔,一般等于 10分钟,早高峰时等于 5分钟 maxR :允许的最大满载率,一般为 120% minR :允许的最小满载率,一般为 50% )(twi : t时刻 i站的上车流速率(人/分钟) 在假设流动均匀时 iw =一个时间段内上车总人数/时间段长度 )(td i : t时刻 i站的下车流速率(人/分钟) (需要说明的是,在实际中下车是一下完成的, 不存在什么速率,但为了形式的统一,我们假想乘客是匀速往下流动的) m :一条线路的总站数 n :一条线路一天发车的总车次数 ijat , :第 j辆车到达第 i站的时间 文中用到符号另行说明 第4页 共 24页 五.模型建立与求解 首先说明的是由于上行线下行线情况相似 我们建立的模型只针对一条线路而言 模型一 先构造最理想的模型 ,在此模型中不出现乘客因客车太满而坐不上车的情况 我们 的目标是最大化发车间隔 对于乘客满意程度我们放在约束条件中考虑 既调整发车间隔的 上限和满载率的上下限 我们把一天的运营时间分为若干时间段 在各时间段内发车间隔保 持不变 针对一个具体的时间段ddt úû ú êë ê D = £D ££ = = += D+= ==-+= D å ò - = + - D-- t ddt w Tt RpR p tat vltat tatat wjtdtwpp ts tMax ij j i k kki ijij ii at tatijij ij ij max max,min 0, 01,1 1 1 1,0,1 ,1, 1,, 100100 0 )3( / )2( m)1i,1( (1)dt ))()(( .. : , , LL LL LLLL 其中 1 式表示 第 j辆车在第 i站上完乘客后车上的乘客数 = 第 j辆车在第 1-i 站 上完乘客后车上的乘客数 + 在第 i站上第 j辆车的乘客数-在第 i站下第 j辆车的乘客数 2 式表示 第 j辆车到达第 i站的时间 = 第 1-j 辆车到达第 i站的时间 + 发车 间隔 3 式表示 第1辆车到达第 i站的时间 = 第 1 辆车发车时间 + 1 站与 i站间的距 离 /车速 如果上下车流速均匀 ( ) m)1(it w dt ))()(( i1, 1,, , , L=D´-+= -+= - D-- ò iij ii at tatijij dp tdtwpp ij ij 求解此模型的程序如下 以时间间隔 ddt=30分钟为例 (1) time=5:00, tD =10分钟,e=0.1分钟; (2) 判断 time是否大于 23:00 是: 停 输出各个时间段内的发车间隔 否: 继续 (3) t =time 第5页 共 24页 (4) t时刻发出一辆车 由公式 vltt iiii /,11 -- += 推出其经过第 i个站的时间 it (5) 在由公式 m)1(idt ))()(( . 1 L=-+= ò D-- tdtwpp ii t ttii i i 得出该车离开各站上时车上的人 数 (6) 若所有的 ip 均满足条件 maxmin 100100 RpR i ££ 转 7 否则 tD = tD -e 转(4) (7) 若 t