作者:贾鹏,王莹,欧阳坚,本文获全国一等奖 公交车的调度 摘要: 本文讨论城市公交车的高效调度问题,对主要因素进行了细致研究。为了得到一个简 单又高效的调度方案(两个起点站的发车时刻表,需要的车辆数等),我们把问题归结成 个阶段不确定多阶段动态规划问题,递进的建立了五个模型。 模型一以一定的时段等分工作日,在同一时段内等间隔发车,使乘客只等一趟车,用计 算机搜索,最大化满足约束条件的发车间隔。以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
13:00-13:306.9 22:00-22:3010 13:30-14:0016,7 22:30-23:0010 下行线 时间段 发车间隔时间段 发车间隔 (分钟) 分钟 5:00-5:30 5:30-6:00 10 14:30-15:007 6:00-6:30 6.9 15:00-15:305.5 7:00-7:30 16:00-16:303,2 7:30-8:00 16:30-17:003.3 8:00-8:30 17:00-17:301.9 8:30-9:00 2,2 17:30-18:001.9 :00-9:30 l8.00-18 30-10:00 18:30-19:00 10:00-10:30|6.5 19:00-19:30|6.5 10:30-11:006.5 19:30-20;006.5 l1:00-11:307.3 20:00-20:30 l1:30-12:007.2 20:30-21:00 12:00-12:308.6 12:30-13:008.6 21:30-22:009.3 13:00-13:30 13:30-1400〖8 30-23:00 10 各时间段第一辆车的发车时间为此时间段的起点 由上表可以看出,存在发车间隔不能整除时间段的情况。我们在程序中考虑到了这一点: 如出现这种情形,就将剩余的时间内流向各站的乘客数累加至下一段,由下一段处理。 所需车辆数的求解: 在A0和A13处的发车时间表确定后就可以确定这一天发出的总车次数,任意时刻同时 工作的车辆数和为了按表上时间发车所需要得最小车辆数。 天发出的总车次数=A0发车时间表的元素个数+A13发车时间表的元素个数 但由于车调度问题:一天中同时工作的车辆数的最大值并不等于所需要得最小车辆数 定理1:一天中同时工作的车辆数的最大值是所需要得最小车辆数的下界。 上面定理的得出是很明显的,我们略掉证明。 下面给出根据A0和A13处的发车时间表确求任意时刻同时工作的车辆数N()和为了按表上 时间发车所需要得最小车辆数NUM的方法 (1)作一个序偶集合A0out纪录A0所有的发车时间,其形如 40发车时间1,1}.{40发车时间n,l…} (2)作一个序偶集合A13in纪录A3所有的车进入时间,其形如 40发车时间1+ts,2}40发车时间n+152}}。其中ts为车从AO到A13上行的总时间
第6页 共 24 页 13 00-13 30 6 9 22 00-22 30 10 13 30-14 00 6 7 22 30-23 00 10 下行线 时间段 发车间隔 分钟 时间段 发车间隔 分钟 5 00-5 30 10 14 00-14 30 7 5 30-6 00 10 14 30-15 00 7 6 00-6 30 6 9 15 00-15 30 5 5 6 30-7 00 6 3 15 30-16 00 5 7 00-7 30 2 6 16 00-16 30 3 2 7 30-8 00 2 5 16 30-17 00 3 3 8 00-8 30 2 2 17 00-17 30 1 9 8 30-9 00 2 2 17 30-18 00 1 9 9 00-9 30 3 9 18 00-18 30 2 9 9 30-10 00 3 9 18 30-19 00 2 9 10 00-10 30 6 5 19 00-19 30 6 5 10 30-11 00 6 5 19 30-20 00 6 5 11 00-11 30 7 3 20 00-20 30 9 2 11 30-12 00 7 2 20 30-21 00 9 2 12 00-12 30 8 6 21 00-21 30 9 3 12 30-13 00 8 6 21 30-22 00 9 3 13 00-13 30 8 22 00-22 30 10 13 30-14 00 8 22 30-23 00 10 各时间段第一辆车的发车时间为此时间段的起点 由上表可以看出 存在发车间隔不能整除时间段的情况 我们在程序中考虑到了这一点 如出现这种情形 就将剩余的时间内流向各站的乘客数累加至下一段 由下一段处理 所需车辆数的求解: 在 A0 和 A13 处的发车时间表确定后就可以确定这一天发出的总车次数 任意时刻同时 工作的车辆数和为了按表上时间发车所需要得最小车辆数 一天发出的总车次数=A0 发车时间表的元素个数+ A13 发车时间表的元素个数; 但由于车调度问题 一天中同时工作的车辆数的最大值并不等于所需要得最小车辆数 定理 1 一天中同时工作的车辆数的最大值是所需要得最小车辆数的下界 上面定理的得出是很明显的 我们略掉证明 下面给出根据 A0 和 A13 处的发车时间表确求任意时刻同时工作的车辆数 N(t) 和为了按表上 时间发车所需要得最小车辆数 NUMmin 的方法 1 作一个序偶集合 A0out 纪 录 A0 所有的发车时间 其形如 {{A0发车时间11}...{A0发车时间n 1}...} 2 作一个序偶集合 A13in 纪录 A13 所有的车进入时间 其形如 {{A0发车时间1+ ts 2}...{A0发车时间n + ts 2}...} 其中 ts 为车从 A0 到 A13 上行的总时间
14.58 =0.729小时。 (3)作一个序偶集合A13ou纪录A3所有的发车时间,其形如 413发车时间3}.{413发车时间n,3} (4)作一个序偶集合AOin纪录A0所有的车进入时间,其形如 413发车时间1+t,4}….{413发车时间n+1x,4}}。其中tx为车从A0到A13上行的 总时间,tx 14.61 0.7305小时。 (5)一天发出的总车次数=|A00(+|13ol=|40ml+|13ml (6)集合H=A0om∪A3inUA13ouUA0i,由于各自的标志不同 AOout A3inAl3out AOin四集合中没有相同的元素。则H包含了A0和A13一天中出车和入车情况的所 有信息。 (7)将H中所有元素按其第一个分量时间排序。 (8)记A0处的净出车数为A0c(A0c=A0的出车数A0的入车数), A13处的净出车数为A13c(A3c=413的出车数A13的入车数), A0c,A13c为负数时表示有车停在相应处未开出 同时工作的车辆数为che,che=0。 (9)=1起到H,顺序检查H的个元素H[] 若H口的第二分量为1则:A0c=A0c+1,che=che+l; 若H口的第二分量为2则:413c=A13c-1,che=che-l 若H口的第二分量为3则:A13c=A13c+1,che=che+l; 若H]的第二分量为4则:A0c=A0c-1,che=che-l 检查过程中记录下A0c的最大值 AOCMAX,A13c的最大值A3cMAX,che的最 大值 cheMEX。 按表上时间发车所需要得最小车辆数=Max{40cMAX,A3cMAx, cheMex}; 据此我们求出模型一需要的车辆数为56辆,工作日总车次为468 最优车辆分配: 路面及起始终点站内的车的分布及流动可以看作是循环的车流,用图表示如下 A0站 A13站
第7页 共 24 页 0.729 20 14.58 ts = = 小时 3 作一个序偶集合 A13out 纪 录 A13 所有的发车时间 其形如 {{A13发车时间13}...{A13发车时间n 3}...} 4 作一个序偶集合 A0in 纪 录 A0 所有的车进入时间 其形如 {{A13发车时间1+ tx 4}...{A13发车时间n + tx 4}...} 其中 tx 为车从 A0 到 A13 上行的 总时间 0.7305 20 14.61 tx = = 小时 5 一天发出的总车次数 = A0out + A13out = A0in + A13in 6 集合 H = A0out U A13in U A13out U A0in ,由于各自的标志不同 A0out A13in A13out A0in 四集合中没有相同的元素 则 H 包含了 A0 和 A13 一天中出车和入车情况的所 有信息 7 将 H 中所有元素按其第一个分量时间排序 8 记 A0 处的净出车数为 A0c A0c =A0 的出车数-A0 的入车数 A13 处的净出车数为 A13c A13c =A13 的出车数-A13 的入车数 A0c A13c 为负数时表示有车停在相应处未开出 同时工作的车辆数为 che che=0 9 i = 1起到 H 顺序检查 H 的 i个元素 H[i] 若 H[i]的第二分量为 1 则 A0c = A0c +1 che=che+1 若 H[i]的第二分量为 2 则 A13c = A13c -1 che=che-1 若 H[i]的第二分量为 3 则 A13c = A13c +1 che=che+1 若 H[i]的第二分量为 4 则 A0c = A0c -1 che=che-1 检查过程中记录下 A0c 的最大值 A0cMAX A13c 的最大值 A13cMAX che 的 最 大值 cheMAX 按表上时间发车所需要得最小车辆数 = Max{A0cMAX, A13cMAX, cheMAX} 据此,我们求出模型一需要的车辆数为 56 辆 工作日总车次为 468 最优车辆分配 路面及起始终点站内的车的分布及流动可以看作是循环的车流 用图表示如下 A0 站 A13 站
AO站和A13站相当与两个节点,任意时刻输出等于输入。 当上行和下行方向同一时刻车流密度不同时,则在起始站和终点站需要备有一定的车辆 补充,同时也要存储一定的车辆,当在一段时间内上行始终大于下行方向上的车流(或相反), 则要求在起始站存储相当数量的车备用,相应的也将有大量的车滞留在终点站,相同的车次 要求下,势必造成车辆资源的浪费。而且本题的数据显示上行方向的车流密度大多数时刻大 于下行方向上的车流密度,所以要求对模型进行调节。 目标函数:Mm[Max(An 约束条件:每时刻A,B节点的输入等于输出。 由约束条件,显然可以得到, Marla]=MaB1-B2,则 Min[May(An) Min( Max B1-B2I 调整方法如下 所需要得最小车辆数=Max{A0cMAX,MAX, cheMeX}; 若MaxA0cMAX,AcMX, chemex}= che MAX则再增加总车次也不能使 cheMEX减小 che MAX就是所需要得最小车辆数。 A Max( A0cMAX, A13cMAX, cheMAX)=A0cMAX, i A0c(t)=A0cMAX 由A0c(tn)+A13c(tn)=che(tn)≤ cheMa 即A0cMAX+A13c(tn)=che(tn)≤ chemex, 又A0cMAX≥ cheMeX,得A13c(tn)≤0。由此我们可以看出在tn时刻,40c()取到最大值, 而A1x(tn)≤0表明A3处有车闲置,若想办法将tn时刻A13处的车移到A0处这可见小 AOC MAX的值,直到A13c(tn)≥0为止 将tn时刻A13处的车移到A0处的一个有效的办法是,A13的发车表中tn的前几个时段适当 减小A13下行车的发车间隔。这种方法的优点是能有效减小所需要得最小车辆数,减小了部 分乘客的等车时间,缺点是增加了总的车次数 以前面ddt取30分钟的情况为例,只需把6:00和6:30的发车间隔分别从69分/辆,63 分/辆,改为4分/辆和3.5分辆,所需要得最小车辆数就从56辆减小到了49辆,只是总的
第8页 共 24 页 Ain Aout A0 站和 A13 站相当与两个节点 任意时刻输出等于输入 当上行和下行方向同一时刻车流密度不同时 则在起始站和终点站需要备有一定的车辆 补充 同时也要存储一定的车辆 当在一段时间内上行始终大于下行方向上的车流 或相反 则要求在起始站存储相当数量的车备用 相应的也将有大量的车滞留在终点站 相同的车次 要求下 势必造成车辆资源的浪费 而且本题的数据显示上行方向的车流密度大多数时刻大 于下行方向上的车流密度 所以要求对模型进行调节 目标函数 [ ( )] Min Max Ain 约束条件 每时刻 A B 节点的输入等于输出 由约束条件 显然可以得到 Max[Ain ] = Max B1- B2 则 [ ( )] Min Max Ain Min[Max B1- B2] 调整方法如下 所需要得最小车辆数= Max{A0cMAX, A13cMAX, cheMAX}; 若 Max{A0cMAX , A13cMAX ,cheMAX}=cheMAX 则再增加总车次也不能使 cheMAX 减小 cheMAX 就是所需要得最小车辆数 若 Max{A0cMAX , A13cMAX ,cheMAX}= A0cMAX 设 A0c(t m ) = A0cMAX 由 A0c(tm ) + A13c(tm ) = che(t m ) £ cheMAX 即 A0cMAX + A13c(t m ) = che(tm ) £ cheMAX 又 A0cMAX ³ cheMAX 得 13 ( ) m A c t £ 0 由此我们可以看出在 m t 时刻 A0c(t) 取到最大值 而 13 ( ) m A c t £ 0 表明 A13 处有车闲置 若想办法将 m t 时刻 A13 处的车移到 A0 处这可见小 A0cMAX 的值 直到 13 ( ) m A c t ³ 0为止 将 m t 时刻 A13处的车移到 A0 处的一个有效的办法是 A13的发车表中 m t 的前几个时段适当 减小 A13下行车的发车间隔 这种方法的优点是能有效减小所需要得最小车辆数 减小了部 分乘客的等车时间 缺点是增加了总的车次数 以前面 ddt 取 30 分钟的情况为例 只需把 6 00 和 6 30 的发车间隔分别从 6.9 分/辆 6.3 分/辆 改为 4 分/辆和 3.5 分/辆 所需要得最小车辆数就从 56 辆减小到了 49 辆 只是总的
车次数从468辆增加到了474辆,且此时有A13c(tn)=0,所需要的最小车辆数不能再减小了。 同理:若Mx{40cMAX,A3cMAX, cheMex}=A3cMAX时只需相应的减小A0发车表中的几 个间隔即可 根据这个调整方法,模型一调整后需车辆数49辆,工作日总车次为475。 分析车辆数费用和车次的费用: 汽油费用为p升/元,客车耗油量为q升/千米,工作人员一次出车得报酬及 客车损耗共c元,一次出车获得平均收入g元,;路线长度lm,客车平均寿命y年,客车 价格k元,客车全年运营。设每天多发n次车可以节省m辆车,则当 n×365×y×(1xp/q+c-g)<mxk时,可以考虑调整车次;否则就不用考虑。 模型二:在求解模型1中我们发现缩短等间隔发车时间段,所得结果会更为理想,(如 上行时500600发车间隔为61分钟缩短为5:00-5:30发车间隔为10分钟)。原因是很明显 的,正是如前所述的“越界”问题造成的。时间段越长,“越界”问题越明显。以5:00-600 为一时间段,必然要考虑6007:00的乘车状况,而6:00-7:00为乘车高峰期,发车间隔必须 较短,因此总体考虑5:00-6:00的发车间隔就不能太长。而以5:00-5:30为时间段则“越界” 影响较小 很自然的,我们想到,如果把时间段无限缩小,使各段间互不影响,就可以得到更优的 解 程序流程与模型1同,只是ddt取得更小。 实际上dMt反映了t到t+ddt间隔中单位时间内发出的车辆数,即发车的快慢,ddt越 小对发车情况的描述就越细致,理论上当ddt趋近于0时可以得到一条关于t的发车密度曲 线g(,能得出细致发车方案,即间隔M取方程∫g(=1的解。但实际中,d趋于0 程序是无法计算的,我们取dt=6分。 计算出的发车时刻表见附录1。模型二需要的车辆数为54,工作日总车次为466 模型三:分别以5:00-6:00,6:00-7:00…18个时间段中13个下行站的上车人数 s,(i=1…18,j=1…13)为分量做出18个向量S=(s1,S2…s13)。经计算,我们发现向量之 间的相关度P=S·S,(S5j=1-18)是很好的,最小值也为0994行站下车人数, 上行站上车人数与下行站下车人数也符合这个规律。这是可以理解的,由于各个地区居住的 总人数及设施布局基本保持稳定,各站上下车人数也应存在一定的比例关系。对于这个特点 我们做出了相应的模型 我们先求出14个车站上车人数的归一化比例向量(以下行为例){a,a1…a3}和下车
第9页 共 24 页 车次数从 468 辆增加到了 474 辆 且此时有 13 ( ) m A c t =0 所需要的最小车辆数不能再减小了 同理 若 Max{A0cMAX , A13cMAX ,cheMAX}= A13cMAX 时只需相应的减小 A0 发车表中的几 个间隔即可 根据这个调整方法 模型一调整后需车辆数 49 辆 工作日总车次为 475 分析车辆数费用和车次的费用: 汽油费用为 p 升/元 客车耗油量为 q 升/千米 工作人员一次出车得报酬及 客车损耗共 c 元 一次出车获得平均收入 g 元 路线长度 lkm,客车平均寿命 y 年 客车 价 格 k 元 客车全年运营 设每天多发 n 次车可以节省 m 辆 车 则 当 n ´ 365´ y´ (1´ p / q + c - g) < m ´ k 时 可以考虑调整车次 否则就不用考虑 模型二 在求解模型 1 中我们发现缩短等间隔发车时间段 所得结果会更为理想 如 上行时 5:00-6:00 发车间隔为 6.1 分钟,缩短为 5:00-5:30 发车间隔为 10 分钟 原因是很明显 的 正是如前所述的 越界 问题造成的 时间段越长 越界 问题越明显 以 5:00-6:00 为一时间段 必然要考虑 6:00-7:00 的乘车状况 而 6:00-7:00 为乘车高峰期 发车间隔必须 较短 因此总体考虑 5:00-6:00 的发车间隔就不能太长 而以 5:00-5:30 为时间段则 越界 影响较小 很自然的 我们想到 如果把时间段无限缩小 使各段间互不影响 就可以得到更优的 解 程序流程与模型 1 同,只是 ddt 取得更小 实际上 ddt/ Dt 反映了t到t +ddt 间隔中单位时间内发出的车辆数 即发车的快慢 ddt 越 小对发车情况的描述就越细致 理论上当 ddt 趋近于 0 时可以得到一条关于 t的发车密度曲 线 g(t) 能得出细致发车方案 即间隔 Dt 取方程 ò +D = t t t g(t)dt 1的解 但实际中 ddt 趋于 0 程序是无法计算的 我们取 ddt=6 分 计算出的发车时刻表见附录 1 模型二需要的车辆数为 54 工作日总车次为 466 模型三 分别以 5:00-6:00 6:00-7:00 … … 1 8 个时间段中 13 个下行站的上车人数 i j s , (i = 1L18, j = 1L13) 为分量做出 18 个向量 ( , ) i i,1 i ,2 i,13 S = s s Ls 经计算 我们发现向量之 间的相关度 = · /( ) (i, j = 1L18) r Si S j Si S j 是很好的 最小值也为 0.9944 上行站下车人数 上行站上车人数与下行站下车人数也符合这个规律 这是可以理解的 由于各个地区居住的 总人数及设施布局基本保持稳定 各站上下车人数也应存在一定的比例关系 对于这个特点 我们做出了相应的模型 我们先求出 14 个车站上车人数的归一化比例向量 以下行为例 { , , } a1 a1 La13 和下车
人数的归一化比例向量AA1-A},其中发以=1月=,4=二。,B同。 ∑∑S 这样在第i站下车的人数m,=PB∑B,P,=P-1+,()-m,其余条件保持不 变,按模型1的解法得到结果见附录2。模型三需要的车辆数为74,工作日总车次为606。经 过调整,需要车辆数为70,工作日总车次为625。 解出的结果和模型2有些区别,这主要是因为我们归一化得到的向量是对各种具体情况 的加权综合,而模型2是对每一种具体情况而言,因此模型2所得结果要优于模型3。 模型四ε考虑实际情况,不能保证每个乘客都一定上得了车:车过于拥挤时,他可以选 择离开乘坐别的交通工具,也可以选择等待下一辆车。出现这种情况时,乘客是不满意的。 综合这些因素,我们以t=∑(每一等车人次x此人次等车时间)为变量构造一个费用函 我们假定当t等于0时,他的不满意度为0;当ν小于1000分钟时,不满意度增加较 为缓慢;但当等车时间大于1000分钟时,不满意度会迅速增加。据此我们建立费用函数 f(w)=axwt/(b-w1),这里a=0.4b=3000;如图所示: t=1000时f(w)=0.2;t=2000时,f(n1)=0.8。 我们假设wa表示第j辆车到达第i站载完乘客后剩下的上不去车的人数,u1表示第 j辆车到达第i站时上车的乘客数,t为第i辆车发车时间,P为在第j辆车在第站上完乘 客后车上的乘客数,建立模型如下: 第10页〔共24页
第10页 共 24 页 人数的归一化比例向量{ , , } b1 b1 Lb13 其中å å = = = = 13 1 13 1 1, 1 i i i ai b åå å = = = = 13 1 18 1 , 18 1 , i j i j j i j i s s a bi 同ai 这样在第i 站下车的人数 å= = - 13 1 / k i dni pi bi bi i i i dni p = p -1 + w (t)Dt - 其余条件保持不 变 按模型 1 的解法得到结果见附录 2 模型三需要的车辆数为 74 工作日总车次为 606 经 过调整,需要车辆数为 70 工作日总车次为 625 解出的结果和模型 2 有些区别 这主要是因为我们归一化得到的向量是对各种具体情况 的加权综合 而模型 2 是对每一种具体情况而言 因此模型 2 所得结果要优于模型 3 模型四 考虑实际情况 不能保证每个乘客都一定上得了车 车过于拥挤时 他可以选 择离开乘坐别的交通工具 也可以选择等待下一辆车 出现这种情况时 乘客是不满意的 综合这些因素 我们以 wt = å (每一等车人次´ 此人次等车时间) 为变量构造一个费用函 数 我们假定当 wt等于 0 时 他的不满意度为 0 当 wt小于 1000 分钟时 不满意度增加较 为缓慢 但当等车时间大于 1000 分钟时 不满意度会迅速增加 据此我们建立费用函数 f (wt) = a ´wt /(b - wt) 这里a = 0.4,b = 3000 如图所示 500 1000 1500 2000 2500 0.5 1 1.5 2 wt = 10 00 时 f (wt) = 0.2 wt = 20 00 时 f (wt) = 0.8 我们假设 wa j,i 表示第 j 辆车到达第 i站载完乘客后剩下的上不去车的人数 u j,i表示第 j 辆车到达第i站时上车的乘客数 j t 为第i 辆车发车时间 p j ,i 为在第 j 辆车在第i站上完乘 客后车上的乘客数 建立模型如下