《全国大学生数学建模竞赛中公交车调度问题的求解》由会员分享，可在线阅读，更多相关《全国大学生数学建模竞赛中公交车调度问题的求解（16页珍藏版）》请在金锄头文库上搜索。
1、全国大学生数学建模竞赛中公交车调度问全国大学生数学建模竞赛中公交车调度问题的求解题的求解成都航空职业技术学院lounudofCh.g,hAeronauticVocatiomlTechnicall2002 年 6 月第 2 期(总第 5l 期)Vo1.18No.2(SerialNo.51)2002全国大学生数学建模竞赛中公交车调度问题的求解成都航空职业技术学院刘红张强杜瑜摘要:本文首先对题目进行了综合分析,分析出模型的主要特点,找出问题及解决问题的主要方法一阿克玛(Akirna)方法;然后对该模型进行了详细求解,最后对这个调度问题给出了一个明确,完整的数学模型,并在采集运营数据方面给出了相关的建
2、议,同时也对该模型进行了推广.关键词:阿克玛(Akirna)方法曲线拟合计算机模拟我国正处在加快城市基础设施建设阶段,城市建设中,交通问题是关系到经济发展速度的一个重要因素.在交通问题中,公交是一个城市的命脉,为此,我们有必要对城市的公交车调度问题找出一套最优化的方案,以期在城市基础设施建设中作出自己的贡献.1.问题提出公共交通是城市交通的重要组成部分,作好公交车的调度对于完善城市交通环境,改进市民出行状况,提高公交公司的经济和社会效益,都具有重要意义.下面考虑一条公交线路上公交车的调度问题,其数据来自我国一座特大城市某条公交线路的客流调查和运营资料.该条公交线路上行方向共 l4 站,下行方向
3、共 l3站,给出的是典型的一个工作日两个运行方向各站上下车的客数量统计.公交公司配给该线路同一型号的大客车,每辆标准载客 100 人,据统计客车在该线上运行的平均速度为 20 公里/小时.运营调度要求,乘客侯车时间一般不要超过 l0 分钟,早高峰时一般不要超过 5 分钟,车辆满载率不应超过 120%,一般也不要低于 50%.试根据这些材料和要求,为该线路设计一个便于操作的全天(工作日)的公交车调度方案,包括两个起点站的发车时刻,一共需要多少辆车,这个方案以怎样的程度照顾到了乘客和公交公司双方的利益等等.2.问题总体分析通过对问题的分析和理解,本问题有以下几大特点:首先,本模型是个双目标(公交公
4、司的最大效益和乘客的满意度)最优化模型,但在本模型中,目标一乘客的满意度(服务质量和候车时间的长短),侧重于候车时间的长短上,而候车时间的长短直接体现在合理的公交车调度上,因此,此双目标问题可通过转化为单目标问题得以解决;同时可以预测出,整个模型的建立,按常规用一个完整的数学解析式建立数学模型是非常困难的,在此可考虑把问题分解处理的办法,本模型的求解就是采用分解成一些小问题求解,然后采用部分枚举法得出最优解.其次,本模型给出了大量数据,这是自开展此项竞赛以来数据最多的一道竞赛题,对大量数据的处理,通常都要用到阿克玛(Akima)方法(拟合的方法),本题将充分使用此方法.首先将所有数据拟合成一条
5、曲线,然后通过曲线的特点得出它的规律一曲线服从泊松分布,最后得出不同站点间的人流量,通过人流量以及其它因素得出发车量和发车时间分布.再次,由于本模型数据多的特点,采取先用数据模拟出曲线,再由曲线得出泊松分布函数,在整个求解过程中,阿克玛(Akima)方法是解决整个问题的关键,由于此方法的特点是误差较大,因此,本模型对误差的合理性及应用性检验成为本模型的又一重点和难点.最后,我国是一个人口大国,尤其是大,中城市,?35?全国大学生数学建模竞赛中公交车调度问题人口更加稠密,因此在现实生活中,经常存在排队现场,另外,随着计算机技术的迅速发展,需要计算机对大量数据进行处理,本文在对排队问题,尤其是调度
6、问题以及计算机对数据的处理方面得出了较宝贵的思想方法和解决办法.3.基本的假设(1)假设交通畅通无阻,客车不会在路上发生任何意外.(2)假设在同一线路上的客车彼此赶不上,而且不存在超车的问题.(3)假设上下乘客互不干扰,即前门上后门下.(4)假设每名乘客上下车的时间分别服从4,121,7的均匀分布.站.(6)假设公交公司配给该线路同一型号的大客车.(7)假设公交车在站停留时间不规定在乘客等待时间范围内.(8)假设同一时间段内前后两辆车的载客情况相同.关于假设,需要说明的是:假设非常重要,假设过多,问题的实用面减少,假设过少,对问题的求解增加较大难度,同时,假设还分常规假设和重点假设,常规假设一
7、般要与实际相符合,重点假设主要是为了求解.如上述假设(4),(8)就是重点假设,但需注意,假设必须检验,特别是重点假设.(5)假设客车在站停留期间不会有乘客到达车 4.符号的说明符号假设内容T 发车时间间隔(分)Nh 汽车总量(辆)(i 一 1)T 第 i 辆车离开起点站时刻(分)Ti(i,j)第 i 辆车到达 j 站的时刻(分)Ta(i,j)第 i 辆车离开 j 站的时刻(分)N(i,j)在 j 站上 i 车的乘客人数(个)N(i,j)在 j 站下 i 车的乘客人数(个)S 第(j 一 1)站到 j 站的距离(米)tt 第(j 一 1)站到 j 站的时间(分)Vt 汽车的行驶速度(米/分)每
8、个乘客上车所需要的时间(分)bt 每个乘客下车所需要的时间(分)Ri,j 第 j 站客到达的平均速度(米/分)Mi,j 任一时刻在第 j 站等待上车的人数5.问题的分析本题需要考虑到两方面的利益:一是乘客满意度,具体分析见前面;二是公交公司获得最大的利益,公交公司在为了节约成本的情况下,派出的车量应尽可能少,并且在到达终点以后,可以经过一段时间的休整,再返回起点站,这样就可以尽可能的提高客车的利用率,这样一来我们需要把发车的时间间隔调到最合适,而调节时间的主要依据是根据各个?36?时间段的客流量的大小.6.模型的建立首先通过题目中所给的数据(数据略),利用曲线拟合程序,拟合出了一天中每一站上车
9、人数的曲线图,这里我们以上行方向中的 A13 的数据所拟合的曲线为例来说明.其图形如图 1 所示.从曲线图和所给数据很容易看出,在一天中客流量有两个高峰,分别是上午的 7:O)_一 8:00 和下午 17:O)_一 18:全国大学生数学建模竞赛中公交车调度问题00,经过观察与分析,我们可近似地认为图 1 是由上午 5:00 卜_.12:00 和下午 13:00 卜_.23:00 的两个泊松分布所组成.用程序将这两个泊松分布叠加在一起,就可以得出 A13 站一天来上车乘客人数分布规律,如图 2 所示,通过图 2,得出理论的泊松分布图.由于在每一站一天内乘客到站上车人数是服从泊松分布的,并且在计算
10、每名乘客间隔到站时间中也要用的有关泊松分布相关参数,所以对理论上的泊松分布进行了检验.O24158,O1214,8,820图 1 时间 t人数 M 的曲线图图 2 时间 t人数 M 的泊松分布图汽车 i 在 J 站的停留时间(Td(i,j)一 rIi(i,j)的大小取决于上车时间(nN.(i,j)-9 下车时间(biNf(i,i)中的最大值.则有:Ta(i,J)一 Ti(i,j)=nlaxatN(i,J),btNt(i,J)在每个时间段内客流的到达速度为:R(i,j)=rr(M(i,j)其中肌(x)中X 表示取整.根据汽车离开 j 站时刻=汽车到达 j 站时刻+上下车所需要的最大时间=汽车到达
11、 i 一 1 站时刻+上下车所需要的最大时间+ti建立初步模型:(i,J)=Ti(i,J)+maxatN(i,J),b,Nt(i,j)=Ti(i,j_1)+maxatN(i,j),bNf(i,j)+根据模型,从理论上可以求出任何一辆车到任何一站的时刻,根据前后两辆车的时刻差,可以求出发车的间隔时间.需要说明的是,我们考虑把同一时间段内前后两辆车的载客情况视为相同,这样可以避免在各个站因上下人而引起的停留时间不同,以至于求出的发车时间间隔的错误.而 Ne(i,J)要根据 Nf(i,j)来求解,则可以分以下两种情况来讨论:第一种情况:120 一一即 Ne(i.j):M(i.j)也就是说汽车在到达第
12、 i 个站时,车上的空位置要多于车站上候车的人数.第二种情况:120 一【一即 Ne(ij)=120 一【一题中要求车辆满载率不应超过 120ok,一般也不低于 50%,即:50sXA.N(i,j)一 Nt(i,j)s1207.计算机程序模拟的结果分析根据上述模型,用 Maple 编写出的模拟程序(从略),可得出每一特定时间内各站的具体情况.下面以上行方向(A13 开往 A0)6:007:00 时间段内 A12站为例来进行示例说明.在不过分追求结果精度的情况下,可以用穷举的方法来寻求发车时间间隔的最优.根据题目中的已知条件,显然只有 10 种可能:最快每一分钟发一辆车,最慢每 10 分钟发一辆
13、车.这里只需用计算机模拟出各种情况,其中既能最大限度的把在站等候的乘客在规定的时间内全部带走,又能尽量少发车,提高每一辆车的利用率的情况,即为所求.下面分别假设发车时间间隔 T=2 分钟,T=3分钟,T=4 分钟(余省略)的情况下,对系统内一些相关的性能指标进行分析(这里由于相关数据较多,所以我们只取前 7 辆的数据进行分析与比较,并只?37?全国大学生数学建模竞赛中公交车调度问题对 T=3 分钟情形模拟,余相同),可以得出,T=3 分车时刻表,由于在 7:O08:O0 是一个高峰期的顶钟是最优解,它既让 95%的乘客上车,又为公交公点,此时的营运的车辆最多,公司也应该以此时所要司获得了最大利
14、益,座位利用率为 98%,达到了双求的车辆数投入营运,这时总时间为 Ti,i,0=62 分赢的目的.同理在计算其它时间段的间隔发车时间钟,需要车辆 Nb=46 辆;采用相同的方法,可求出下时,都可按上述方法求出它的最优解,不同的是,只行方向的发车时刻表,将上行方向的发车时刻表与要改变程序中的相应站的泊松分布数据和假设的发下行方向的发车时刻表进行综合,取同一时段中间车间隔就可以了,于是通过程序,得出上行方向的发隔时间较小的作为最后的发车时刻如下:时间段 5:O06:O06:O07:O07:O08:O08:O09:O09:O010:O010:O0ll:O0发车间隔 1032357时间段 ll:O0
15、12:O012:O013:O013:O014:O014:O015:O015:O016:O016:O017:O0发车间隔 788763时间段 17:O018:O018:O019:O019:O02O:O020:O021:O021:O022:O022:O023:0o发车间隔 237101010通过计算机模拟计算,得出两个起点站的发车客候车时间一般要超过 lO 分钟,所以应当缩小一般时刻表见上,需要车辆 Nb=46 辆.情况下的发车时间.8.结果的分析与检验在 T=2 分钟的模拟中,在站停留时间为零,这首先,对由曲线拟合泊松分布产生的误差的检显然是不符合事实的,主要原因是由于为了使结果验,在用计算机模
16、拟系统时,所用的泊松分布与指数例于分析,在程序中都用 Maple中的 floor 进行取整分布均与实际的曲线有一定的误差,不过在检验泊造成的,这也充分说明了公交车在站停留时间比较松分布时,误差控制在了 2%_5%的范围.短,基本上小于一分钟.其次,我们得出的结果是在理想化的假设下求最后,假设(4)从实际中得出服从均匀分布的,得时,在实际问题中将要考虑到汽车之间的相互超其误差可省略,假设(8)中的一般情形可见模型推广车,也就是造成汇车,在有些情况下甚至有多次汇车中的(3).现象,特别是在高峰期的时间内,一方面是因为发车 9.模型推广的间隔时间短,在上下班的高峰期在某个路段容易一般的调度问题可总结出下面抽象的双目标模造成堵车,使多辆车堵在某个路段,另一方面司机的型:经验不同,开车的速度也不同,所以我们在考虑发车目标一:对于公司是载客量/车次为最大;的时候就按照哪一辆车先到终点站,哪一辆车先发.目标二:对于乘客是在系统时间等于等待时间再次,在求解上行方向和下行方向所发
