作者:贾鹏,王莹,欧阳坚,本文获全国一等奖 公交车的调度 摘要: 本文讨论城市公交车的高效调度问题,对主要因素进行了细致研究。为了得到一个简 单又高效的调度方案(两个起点站的发车时刻表,需要的车辆数等),我们把问题归结成 个阶段不确定多阶段动态规划问题,递进的建立了五个模型。 模型一以一定的时段等分工作日,在同一时段内等间隔发车,使乘客只等一趟车,用计 算机搜索,最大化满足约束条件的发车间隔。以30分钟为时段得到发车时间表,得出上行 时7:30到8:00的发车间隔最小,为14分钟;下行时17:30到18:00的发车间隔最小, 为19分钟。共需要车56辆,工作日总车次468次 模型二令等分工作日的时段趋于零,得到一连续的发车速度曲线f(),由它构造发车时 间表,工作日总车次的最小值为457次。 模型三从上下行的数据表中发现各时间的同一车站,同一时间的不同车站,上下车的平 均人流的比例关系很稳定。故将一张表简化成两个向量表示,给出发车时间表,共需要车74 辆,工作日总车次606次。 模型四考虑乘客等多趟车的情况,给出一个乘客不满意度函数,允许乘客采用别的交通 方式离开车站,同时保证总共等车时间不能超过一个数值。得出的结果为共需要车53辆, 工作日总车次427次。 模型五考虑各种随机因素,给出了用计算机模拟的求解方法 最后我们考虑对发车时间表调整,在适度增大车次情况下减小了需要的车数。调整后 模型一需要车49辆,工作日总车次475次。模型三需要车70辆,工作日总车次625次。 第1页〔共24页
第1页 共 24 页 作者:贾 鹏 , 王 莹 , 欧阳坚 , 本文获全国一等奖 公交车的调度 摘要: 本文讨论城市公交车的高效调度问题 对主要因素进行了细致研究 为了得到一个简 单又高效的调度方案 两个起点站的发车时刻表 需要的车辆数等 我们把问题归结成一 个阶段不确定多阶段动态规划问题 递进的建立了五个模型 模型一以一定的时段等分工作日 在同一时段内等间隔发车 使乘客只等一趟车 用计 算机搜索 最大化满足约束条件的发车间隔 以 30 分钟为时段得到发车时间表 得出上行 时 7 30 到 8 00 的发车间隔最小 为 1.4 分钟 下行时 17 30 到 18 00 的发车间隔最小 为 1.9 分钟 共需要车 56 辆 工作日总车次 468 次 模型二令等分工作日的时段趋于零 得到一连续的发车速度曲线 f (t) 由它构造发车时 间表 工作日总车次的最小值为 457 次 模型三从上下行的数据表中发现各时间的同一车站 同一时间的不同车站 上下车的平 均人流的比例关系很稳定 故将一张表简化成两个向量表示 给出发车时间表 共需要车 74 辆 工作日总车次 606 次 模型四考虑乘客等多趟车的情况 给出一个乘客不满意度函数 允许乘客采用别的交通 方式离开车站 同时保证总共等车时间不能超过一个数值 得出的结果为共需要车 53 辆 工作日总车次 427 次 模型五考虑各种随机因素 给出了用计算机模拟的求解方法 最后我们考虑对发车时间表调整 在适度增大车次情况下减小了需要的车数 调整后 模型一需要车 49 辆 工作日总车次 475 次 模型三需要车 70 辆 工作日总车次 625 次
二问题的提出: 公共交通是城市交通的重要组成部分,具有重要的意义。要求根据我国一座特大城市 某条公交线路上一个典型的工作日两个运行方向各站上下车的乘客数量的统计数据,为该线 路设计一个便于操作的全天(工作日)的公交车调度方案,包括两个起点站的发车时刻表; 共需要多少辆车;这个方案以怎样的程度照顾到了乘客和公交公司双方的利益,并将这个 调度问题抽象成一个明确、完整的数学模型,指岀求解模型的方法;根据实际问题的要求, 如果要设计更好的调度方案,应如何采集运营数据。 设该条公交线路上行方向共14站,下行方向共13站,公交公司配给该线路同一型号的 大客车,每辆标准载客100人,据统计客车在该线路上运行的平均速度为20公里/小时。运 营调度要求,乘客候车时间一般不要超过10分钟,早高峰时一般不要超过5分钟,车辆满 载率不应超过120%,一般也不要低于50%。 二问题分析 从统计表中容易看出该公交车的行驶路线是同一条路的两边,只是上行时比下行时多停 站(A1)。由于各站所处地区的人口密度不同,不同时间对不同地区的人流情况的影响也 不同,所以同一时刻单位时间内到达不同站的人数,不同时刻单位时间内到达同一车站的人 数都是各不相同的。公交车运营通常通过起点站,终点站处发车时间来调节,比如在早晨和 深夜适当延长发车间隔以降低运营成本,在上下班髙峰期适当缩短发车间隔,以满足人们的 出行需要。 但降低运营成本与满足人们的需要是相互制约的,较好的调度方案能通过等车人数不同 时间不同站点的分布特点,给出公交车起始站和终点站的发车时刻表,在满足人们的需要(少 等车)的情况下,尽量降低运营成本(少用车次),使运营成本与乘客在系统中逗留费用之 和的期望值最小。 如果尽量加大发车时间间隔,就等效于减少车次,因此我们把模型的目标之一定为最大 化发车间隔但这样会增大乘客等车时间因此我们必须在目标或约束条件中体现出对乘客的 考虑 客车从线路一端走到另一端需要大概44分钟,而乘客流分布是以整点时段内均匀分布 计算的,如果客车在600从AO开往A13,则全段行驶时间都在600-700间这时上车下车的 乘客流就应该以6007:00的数据为标准,但如果客车在6:40从A0开往A13,当它到达A11,A12 时必然过了7点这样上车下车的乘客流就应该以700-8。00的数据为标准这种“越界”问题 增加了解题的复杂程度。 另外需要注意的是所用车次尽量少,并不能保证所用的总车辆数是最少的。所以我们在 尽量减少车次的前提下再对车辆数进行优化,令之达到较满意的程度。 三模型假设: (1)表中的数据有代表性,能反映该路线乘车人按时间和站点分布的普遍情况 (2)乘客上下车时间及到达两个终点站A0及A13的周转时间忽略不记 (3)客车在行驶中保持匀速,即20公里小时途中不会出现阻塞现象 第2页〔共24页
第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 公里/小时.途中不会出现阻塞现象
(4)乘客等车时间不允许超过10分钟早高峰是一般不能超过5分钟。 (5)车辆满载率不超过能120%,一般也不低于50%。(满载率为客车运行期间车上的乘 客数量与标准载客量的比值) (6)各个站点在5:00→6:00,6:00→7:00,…,22:00→23:00各整点时段内到达时刻 是均匀分布的,即单位时间内等车人数增加量相等。 (7)调度时间精确到分钟,因为在实际生活中调度时间过于精确不可能也没有必要 (8)规定具体时间段内,如5:00→5:30,5:30→6:00-,22:30→23:00发车间隔是固 的 四符号说明: t第一辆车发车时间 l-1:第i站与+1站的距离(=0…12) 车速 Mt:发车间隔 P第j辆车在第站上完乘客后车上的乘客数 T:允许的最大发车间隔,一般等于10分钟,早高峰时等于5分钟 R:允许的最大满载率,般为120% R:允许的最小满载率,般为50% ():t时刻i站的上车流速率(人分钟)(在假设流动均匀时, =一个时间段内上车总人数时间段长度) d(1):t时刻i站的下车流速率(人/分钟)(需要说明的是,在实际中下车是一下完成的, 不存在什么速率,但为了形式的统一,我们假想乘客是匀速往下流动的) m:一条线路的总站数 n:一条线路一天发车的总车次数 a第j辆车到达第i站的时间 文中用到符号另行说明
第3页 共 24 页 (4)乘客等车时间不允许超过 10 分钟,早高峰是一般不能超过 5 分钟 (5)车辆满载率不超过能 120%,一般也不低于 50% (满载率为客车运行期间车上的乘 客数量与标准载客量的比值) (6)各个站点在 5: 00 ® 6 : 00, 6 : 00 ® 7 : 00,......,22 : 00 ® 23 : 00各整点时段内到达时刻 是均匀分布的 即单位时间内等车人数增加量相等 (7)调度时间精确到分钟,因为在实际生活中,调度时间过于精确不可能也没有必要 (8)规定具体时间段内,如 5: 00 ® 5: 30, 5: 30 ® 6 : 00,......,22 : 30 ® 23: 00 发车间隔是固 定的. 四.符号说明 0 t :第一辆车发车时间 i,i+1 l :第 i站与i +1站的距离 (i = 0,L12) v :车速 Dt :发车间隔 p j ,i :第 j 辆车在第 i站上完乘客后车上的乘客数 Tmax :允许的最大发车间隔,一般等于 10 分钟,早高峰时等于 5 分钟 Rmax :允许的最大满载率,一般为 120% Rmin :允许的最小满载率,一般为 50% w (t) i :t时刻i站的上车流速率(人/分钟) 在假设流动均匀时 wi =一个时间段内上车总人数/时间段长度 d (t) i :t时刻i站的下车流速率(人/分钟) (需要说明的是,在实际中下车是一下完成的, 不存在什么速率,但为了形式的统一,我们假想乘客是匀速往下流动的) m :一条线路的总站数 n :一条线路一天发车的总车次数 at j ,i :第 j 辆车到达第 i站的时间 文中用到符号另行说明
五模型建立与求解 首先说明的是由于上行线下行线情况相似,我们建立的模型只针对一条线路而言。 模型一:先构造最理想的模型,在此模型中不出现乘客因客车太满而坐不上车的情况。我们 的目标是最大化发车间隔,对于乘客满意程度我们放在约束条件中考虑,既调整发车间隔的 上限和满载率的上下限。我们把一天的运营时间分为若干时间段,在各时间段内发车间隔保 持不变。 针对一个具体的时间段d P,P//-l Ja, -a(w()-d, (o)dt (1)(=1…w,1=1…m) t,1,+△t (3) P,0 100Rm≤P/≤100R M≤Tm 三 其中(1)式表示(第j辆车在第i站上完乘客后车上的乘客数)=(第j辆车在第i-1站 上完乘客后车上的乘客数)+(在第i站上第j辆车的乘客数-在第i站下第j辆车的乘客数) (2)式表示(第j辆车到达第i站的时间)=(第j-1辆车到达第i站的时间)+(发车 间隔) 3)式表示(第1辆车到达第i站的时间)=(第1辆车发车时间)+(1站与i站间的距 离)/车速 如果上下车流速均匀 Pii=p (w,(0-d() dt at-At Px+(w,-d)x△t( 求解此模型的程序流程如下,以时间间隔ddt=30分钟为例 (1)time=5:00,△t=10分钟,E=0.1分钟 (2)判断time是否大于2300,是:停;输出各个时间段内的发车间隔。否:继续。 ( )t=time 第4页〔共24页
第4页 共 24 页 五.模型建立与求解 首先说明的是由于上行线下行线情况相似 我们建立的模型只针对一条线路而言 模型一 先构造最理想的模型,在此模型中不出现乘客因客车太满而坐不上车的情况 我们 的目标是最大化发车间隔 对于乘客满意程度我们放在约束条件中考虑 既调整发车间隔的 上限和满载率的上下限 我们把一天的运营时间分为若干时间段 在各时间段内发车间隔保 持不变 针对一个具体的时间段ddt ú û ú ê ë ê D = D £ £ £ = = = + = + D = + - = = D å ò - = + - -D - t ddt w t T R p R p at t at t l v at at t p p w t d t j w st Max t j i j i k i k k j i j i i i at at t j i j i j i j i max min , max ,0 1,1 0 1 1 1, 0 , 1 , 1, , , 1 100 100 0 / (3) (2) ( ( ) ( )) dt (1) ( 1 ,i 1 m) . . : , , LL LL LL L L 其中 1 式表示 第 j 辆车在第i站上完乘客后车上的乘客数 = 第 j 辆车在第i -1站 上完乘客后车上的乘客数 + 在第i站上第 j 辆车的乘客数-在第i站下第 j 辆车的乘客数 2 式表示 第 j 辆车到达第 i站的时间 = 第 j -1辆车到达第i 站的时间 + 发车 间隔 3 式表示 第1辆车到达第i站的时间 = 第 1 辆车发车时间 + 1 站与i站间的距 离 /车速 如果上下车流速均匀 (w ) t (i 1 m) ( ( ) ( )) dt , 1 i , , 1 , , = + - ´D = L = + - - -D - ò j i i i i at at t j i j i p d p p w t d t j i j i 求解此模型的程序流程如下 以时间间隔 ddt=30 分钟为例 (1) time=5:00, Dt =10 分钟, e=0.1 分钟; (2) 判断 time 是否大于 23:00 是: 停 输出各个时间段内的发车间隔 否: 继续 (3) t =time
(4)r时刻发出一辆车,由公式1=1+l1/v推出其经过第个站的时间t (5)在由公式P=P4+(m(0)-d(O)dta=1…m)得出该车离开各站上时车上的人 数 (6)若所有的p1均满足条件100Rm≤P1≤100m转(7),否则M=Mt-E,转(4); (7)若t< time+ddt,则t=1+M,转(4,否则纪录tine对应的Mt,time= time+ddt,转(2) 上面的算法保证在时间段t0到t0+dt之内找到一个足够小的△t,使从t到to+dt以Mt为间 隔等间隔发车,所有的车在所有的站上均满足车上的人数在100R到100R之间。且Mt是 满足条件的最大的值。 在模型求解中,如果严格要求满载率大于50%,则很难找到可行解,这是因为总存在 段时期各个车站坐车的人都很少,比如下行线5:00-6:00总共上车的人才为50人,不能 因此就不发车,所以我们在程序中没有严格规定满载率大于50%,而求解出的大部分情况都 是满足要求的。另外,车在5:00发车,到达最后一站用时44分钟,后几站等车的时间必 然大于10分钟,这时要忽略这种情况。早高峰时等车时间不能大于5分钟,我们在程序中 没有做这个规定,但可以想到,等车人很多时,发车必然增多,发车间隔必然缩短,根据我 们得到的结果,早高峰是的等车时间都是小于5分钟的。 为了减小”越界影响,同时也为调度方便我们取时间间隔为30分钟。 得出结果如下(每半个小时内发车间隔是一样的 上行线 时间段 发车间隔时间段 发车间隔 5:00-5:30 1440014:308.1 5:306:006.2 14:30-15:008.1 6:00-6:30 15:00-15:30 00 15:30-16:006,2 7: 16:00-16:303 匚7:30-8:001.416:30-17:003 8:00-8:302.6 17:00-17:302.5 7:30-18:002.5 9:00-9:30 18:00-18:308 9:30-10:00 l8:30-19:008 10:00-10:30|6 19:00-19:30|3.3 10:30-11:005.4 9:30-20;003 l1:00-11:30|5.3 20:00-20:30 l1:30-12:005.3 20:30-21:002.5 12:00-12:30 21:00-21:3010 12:30-13:005.9 21:30-22:0010 第5页〔共24页
第5页 共 24 页 (4) t时刻发出一辆车 由公式t t l v i i i i / = -1 + -1, 推出其经过第i个站的时间 i t (5) 在由公式 ( ( ) ( )) dt (i 1 m) . = 1 + ò - = L -D - p p w t d t i i t t t i i i i 得出该车离开各站上时车上的人 数 (6) 若所有的 pi 均满足条件100Rmin £ pi £ 100Rmax 转 7 否则Dt =Dt -e 转(4) (7) 若t <time+ddt 则 t =t +Dt 转(4) 否则纪录 time 对应的 Dt time=time+ddt 转 2 上面的算法保证在时间段 0 t 到 0 t +ddt 之内找到一个足够小的 Dt 使从 0 t 到 0 t +ddt 以Dt 为间 隔等间隔发车 所有的车在所有的站上均满足车上的人数在100Rmin 到100Rmax 之间 且Dt 是 满足条件的最大的值 在模型求解中 如果严格要求满载率大于 50% 则很难找到可行解 这是因为总存在一 段时期各个车站坐车的人都很少 比如下行线 5 00-6 00 总共上车的人才为 50 人 不能 因此就不发车 所以我们在程序中没有严格规定满载率大于 50% 而求解出的大部分情况都 是满足要求的 另外 车在 5 00 发车 到达最后一站用时 44 分钟 后几站等车的时间必 然大于 10 分钟 这时要忽略这种情况 早高峰时等车时间不能大于 5 分钟 我们在程序中 没有做这个规定 但可以想到 等车人很多时 发车必然增多 发车间隔必然缩短 根据我 们得到的结果 早高峰是的等车时间都是小于 5 分钟的 为了减小”越界”影响,同时也为调度方便,我们取时间间隔为 30 分钟 得出结果如下 每半个小时内发车间隔是一样的 上行线 时间段 发车间隔 分钟 时间段 发车间隔 分钟 5 00-5 30 10 14 00-14 30 8 1 5 30-6 00 6 2 14 30-15 00 8 1 6 00-6 30 2 4 15 00-15 30 8 2 6 30-7 00 2 1 15 30-16 00 6 2 7 00-7 30 1 4 16 00-16 30 3 3 7 30-8 00 1 4 16 30-17 00 3 1 8 00-8 30 2 6 17 00-17 30 2 5 8 30-9 00 2 6 17 30-18 00 2 5 9 00-9 30 4 7 18 00-18 30 8 9 30-10 00 4 7 18 30-19 00 8 10 00-10 30 6 19 00-19 30 3 3 10 30-11 00 5 4 19 30-20 00 3 1 11 00-11 30 5 3 20 00-20 30 2 5 11 30-12 00 5 3 20 30-21 00 2 5 12 00-12 30 5 9 21 00-21 30 10 12 30-13 00 5 9 21 30-22 00 10