数学建模-2001年的公交车调度问题.doc

《数学建模-2001年的公交车调度问题.doc》由会员分享，可在线阅读，更多相关《数学建模-2001年的公交车调度问题.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数学建模-2001年的公交车调度问题.精品文档.第三篇 公交车调度方案的优化模型2001年 B题 公交车调度公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，表3-1给出的是典型的一个工作日两个运行方向各站上下车的乘客数量统计。公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运行的平

2、均速度为20公里/小时。运营调度要求，乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟，车辆满载率不应超过120%，一般也不要低于50%。试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益；等等。如何将这个调度问题抽象成一个明确、完整的数学模型，指出求解模型的方法；根据实际问题的要求，如果要设计更好的调度方案，应如何采集运营数据。表3-1 某路公交汽车各时组每站上下车人数统计表 上行方向：A13开往A0站名A13A12A11A10A9A8A7A6A5A4A

3、3A2A1A0站间距(公里)1.60.510.732.041.262.2911.20.411.030.535:00-6:00上3716052437690488385264545110下08913204845813218242585576:00-7:00上1990376333256589594315622510176308307680下0991051642395885428004072083002889216157:00-8:00上3626634528447948868523958904259465454990下020522727246110581097179380146956063618711

4、4598:00-9:00上2064322305235477549271486439157275234600下010612316930063462197144024533940811327599:00-10:00上118620516614728130417232426778143162360下0817512018140741155125013618723377448310:00-11:00上92315112010821521411921220175123112260下052558113629928044217810515316753238511:00-12:00上9571811571332542

5、6413525326074138117300下054588413132129142019611915915353434012:00-13:00上87314114010821520412923222165103112260下046497111126325638916411113414848833313:00-14:00上779141103841861851032111736610897230下03941701032211972971378511311638426314:00-15:00上6251041088216218090185170497585200下03639477818917633913

6、9809712038323915:00-16:00上635124988215218080185150498585200下0363957882091963391298010711035322916:00-17:00上1493299240199396404210428390120208197490下0808513519445044173133515725525180055717:00-18:00上2011379311230497479296586508140250259610下0110118171257694573957390253293378122879318:00-19:00上69112410

7、789167165108201194539382220下04548801082372313901508913112542833619:00-20:00上3506455469185508889274847110下0222334631161081968348646620413920:00-21:00上304504336727540776022383790下01617243880841435934464716011721:00-22:00上209373226535529475216282760下0141421337863125623040411289222:00-23:00上193325535513

8、210下03358181727127993221表3-1（续） 某路公交汽车各时组每站上下车人数统计表 下行方向：A0开往A13站名A0A2A3A4A5A6A7A8A9A10A11A12A13站间距(公里)1.5610.441.20.972.291.320.7310.51.625:00-6:00上22342443331100下02116775342396:00-7:00上795143167841511881091371304553160下070404018420519514793109751082717:00-8:00上2328380427224420455272343331126138450

9、下02941561577107808495453744442653739588:00-9:00上2706374492224404532333345354120153460下026615814975682785652936742823737611679:00-10:00上15562042741252353081622031987699270下01571008041051149833619927613621955610:00-11:00上902147183821552061201501435059180下010359592463463201911471859615443811:00-12:00上8

10、47130132671271501081041074148150下09448481992382561751221436812834612:00-13:00上70690118661051449295883440120下0704040174215205127103119659826113:00-14:00上7709712659102133971021043643130下0754343166210209136901276011530914:00-15:00上839133156691301651011181204249150下08448482192382461551121537811834615:00

11、-16:00上1110170189791691941411521665464190下0110736325330734121513616710214442516:00-17:00上183726033014630540422927725395122340下01759610645961754940126630416226978417:00-18:00上3020474587248468649388432452157205560下03301931947379341016606416494278448124918:00-19:00上1966350399204328471289335342122132400

12、下0223129150635787690505304423246320101019:00-20:00上939130165881381871241431474856170下011359592663062902011471558615439820:00-21:00上6401071266911215387102943643130下075434318623021914690127709531921:00-22:00上636110128561051448295983440120下07341421902431921321071236710129022:00-23:00上294435124465835414

13、2151750下035202087108926947603349136公交车调度方案的优化模型本文获2001年全国一等奖。队员：叶云，周迎春，齐欢，指导教师：朱家明等。摘要：本文建立了公交车调度方案的优化模型，使公交公司在满足一定的社会效益和获得最大经济效益的前提下，给出了理想发车时刻表和最少车辆数。并提供了关于采集运营数据的较好建议。在模型中，对问题1建立了求最大客容量、车次数、发车时间间隔等模型，运用决策方法给出了各时段最大客容量数，再与车辆最大载客量比较，得出载完该时组乘客的最少车次数462次，从便于操作和发车密度考虑，给出了整分发车时刻表和需要的最少车辆数61辆。模型建立模糊分析模型，

14、结合层次分析求得模型带给公司和乘客双方日满意度为（0.941，0.811）根据双方满意度范围和程度，找出同时达到双方最优日满意度(0.8807,0.8807)，且此时结果为474次50辆；从日共需车辆最少考虑，结果为484次45辆。对问题2，建立了综合效益目标模型及线性规划法求解。对问题3，数据采集方法是遵照前门进中门出的规律，运用两个自动记录机对上下车乘客数记录和自动报站机(加报时间信息)作录音结合，给出准确的各项数据，返站后结合日期储存到公司总调度室。关键词：公交调度；模糊优化法；层次分析；满意度1 问题的重述一、问题的基本背景公交公司制定公交车调度方案，要考虑公交车、车站和乘客三方面因素

15、。我国某特大城市某条公交线路情况，一个工作日两个运营方向各个站上下车的乘客数量统计见表3-1。二、运营及调度要求1公交线路上行方向共14站，下行方向共13站；2公交公司配给该线路同一型号的大客车，每辆标准载客100人，据统计客车在该线路上运营的平均速度为20公里/小时。车辆满载率不应超过120%，一般也不低于50%；3乘客候车时间一般不要超过10分钟，早高峰时一般不要超过5分钟。三、要求的具体问题1试根据这些资料和要求，为该线路设计一个便于操作的全天（工作日）的公交车调度方案，包括两个起点站的发车时刻表；一共需要多少辆车；这个方案以怎样的程度照顾到了乘客和公交公司双方的利益，等等；2如何将这个

16、调度问题抽象成一个明确完整的数学模型，并指出求解方法；3据实际问题的要求，如果要设计好更好的调度方案，应如何采集运营数据。3.2 问题的分析本问题的难点是同时考虑到完善城市交通环境、改进市民出行状况、提高公交公司的经济和社会效益等诸多因素。如果仅考虑提高公交公司的经济效益，则只要提高公交车的满载率，运用数据分析法可方便地给出它的最佳调度方案；如果仅考虑方便乘客出行，只要增加车辆数的次数，运用统计方法同样可以方便地给出它的最佳调度方案，显然这两种方案是对立的。于是我们将此题分成两个方面，分别考虑到：公交公司的经济效益，记为公司的满意度；乘客的等待时间和乘车的舒适度，记为乘客的满意度。显然公交公司

17、的满意度取决于每一趟车的满载率，且满载率越高，公交公司的满意度越高；乘客的满意度取决于乘客等待的时间和乘车的舒适度，而乘客等待时间取决于车辆的班次，班次越多等待时间越少，满意度越高；乘客的舒适度取决于是否超载，超载人数越少，乘客越满意。很明显可以知道公交公司的满意度与乘客的满意度相互矛盾，所以我们需要在这两个因素中找出一个合理的匹配关系，使得双方的满意度达到最好。3.3 模型的假设1道路：交通情况、路面状况良好，无交通堵塞和车辆损坏等意外情况；2公交车：发车间隔取整分钟，行进中彼此赶不上且不超车，到达终点站后调头变为始发车； 3乘客：在每时段内到达车站的人数可看作是负指数分布，乘客乘车是按照排

18、队的先后有序原则乘车，且不用在两辆车的间隔内等待太久；4数据：“人数统计表”中的数据来源准确、可信、稳定、科学；5票价：乘车票价为定值，不因乘车远近而改变。3.4 定义与符号说明序号符号意义1上或下行第j时段第k站上车人数；2上或下行第j时段第k站下车人数；3上或下行第j时段最大客容量；4上或下行时第j时段平均载客量；5日所需总车次；6上或下行第j时段的车次；7上或下行第j时段平均发车时差；8上或下行第j时段平均载客量；9上或下行的平均发车时间间隔；10上或下行时公交公司日平均满意度；11上或下行时乘客整体日平均满意度；12上或下行时公交公司各时段的满意度；13上或下行时乘客各时段的满意度；1

19、4日所需车辆数。注：（表示上行运动（），表示下行运动（），。3.5 模型的建立与求解3.5.1 模型：相关量及车辆数的确定模型对问题1为设计便于操作的公交车调度方案，根据表3-1给出的一个工作日两个运营方向各个站上下车的乘客数量统计，假设各时段车辆平均足够载完在相等时间内到达的乘客，乘客也只能乘坐该路车而没有太大的不满，我们要设计两个起点站的发车时刻表，计算需要的车辆数，首先可建立以下各模型来求相关量。1相关量上下行各时间段内最大客容量：建立模型如下运用模型和表3-1中的上下车乘客数，算出上下行各时间段内最大客容量如下：上行：716,2943,5018,2705,1528,1193,1355,

20、1200,1040,881,871,2133,2722,897,464,410,275,19;下行：7,1039,2752,3223,1822,1093,986,830,891,1017,1302,2196,361,2417,1091,781,774,337.其直观的双峰直方图如图3-1。图3-1 (1)上行各时间段内最大客容量 图3-1 (2)下行各时间段内最大客容量车次数：因为座位数为100的客车满载率在50%和120%之间，即，在满足客车满载率和载完各时段所有乘客前提下，由模型：,（其中Z+是正整数）可计算每个时段的详细车次数如下：上行：6,25,42,23,13,10,12,10,9,

21、8,8,18,24,8,4,4,3,4；下行：3,9,23,27,16,10,9,7,8,9,11,19,31,21,10,7,7,4。求和可得出全工作日可行的最少车次总数：。安排发车时间间隔：用每个时段60分钟除以车次数，即：，经计算可得出该时段平均发车时间间隔依次如下：上行：10,2.4,1.4,2.6,4.6,6,5,6,6.7,7.5,7.5,3.3,2.5,7.5,15,15,20,20；下行：20,6.7,2.6,2.2,3.8,6,6.7,8.6,7.5,6.7,5.5,3.1,1.9,2.8,6,8.6,20。由的值有分数出现，而现实中列车、客车等时刻表的最小单位为分钟，故间隔

22、应取整数。当取整数时，可直接安排等时间发车次。当某个取小数时，不妨设和是与相邻的两个连续整数且，由模型：可求出以为间隔的班次和以为间隔的班次，再分别以发车间隔；为和，兼顾发车密度，将此时间段进行适当划分。将上述各与值代入方程组，可相应地求出具体的发车间隔的次数，考虑到公交车调度方案的可操作性和公交公司的利益所在，在同时段线路上的车辆不宜过多，我们对结果进行了分析比较，将相邻时间段内发车间隔相等的班次尽量安排在一起，并且对高峰时期发车的先后顺序作了调整，得出了全天（一个工作日）内的公交车调度方案，见表3-5。2日所需车辆数由汽车平均速度20千米小时和A0A13的距离千米、A13A0的距离千米，可

23、求得车辆从起点站到终点站的时间约为44分钟；又由假设可知车辆到达终点站后立即调头往回开且不跑空车，由于早高峰乘客数最多，故此时车辆实际占用数也应是当日的上限，考虑到8：00之前从A13发出的车次每个时段都多于A0发出的车次，且最大逆差数为即从A13多发出38辆车；8：00到9：00虽然从A0发来的车辆多于从A13发出的车辆，但从8：00到8：44仍要从A13发出的15辆车，由假设恰在8：44时对方开来的车辆到站并调头再结合动态车辆有8辆赶不上时差。故早高峰车辆实际占用为61辆，也即当天共需开动的车辆最少为61辆。3.5.2 模型 最小车次数线性规划模型问题明显可看作是一个排队随机服务系统，我们

24、把汽车看作是“顾客”，将各个车站看作是“服务台”，则此公交系统可看作是一个顾客不消失的、单通道多级服务台串联的排队系统。因此，这里所遇到的，主要是排队问题。归纳起来，需要考虑三种活动：首站发车活动：根据发车时刻表确定；到达中途站活动：在中途站主要考虑和计算上下车人数、车上的总人数和上下车时间；到达终点站调头活动：在终点站根据发车时刻表确定。我们先考上行时乘客在站的逗留时间，即乘客在站的等待时间，它包括相邻两趟车到达站的时间间隔即发车间隔和乘客上下车的服务时间。因为假设每个乘客上车时间和下车时间不计，即0。可以得出：故此问题可以转化为满足下列条件下的公交公司全天的总利益取最大的规划问题：乘客等待

25、时间在一般时间段不超过10分钟；早高峰时间段不超过5分钟；各个时间段内的最大满载率不超过120；各个时间段内的最小满载率不超过50。公交公司全天的总利益为全天所有车辆运行公里数最小，因为线路长度一定，只要考虑站车次即可得出目标函数：利用模I中的数据，我们可以求出各个时间段内的发车次数和间隔，因为此解法是在满足乘客的情况下求的最小解，所以乘客等待时间的满意度为100，但是从舒适度考虑，上下行分别有11和9人不满意，所以乘客总满意度为86.1，公交公司满意度为（109+111）/24010091.7，按模型方法考虑，此时结果为最少车辆数50辆，最少运行474车次。3.5.3 模型 满意度分析模型1

26、前期工作准备工作满意度的层次分析据问题分析，我们在设计两个起点站的发车时刻表时，应着重考虑到此时刻表带给公交公司和乘客两者的利益，即公交公司和乘客对应的日平均满意度与，各时段的满意度和。为此，我们采用层次分析法来讨论影响总体性能的两个相关因素。在乘客源一定的情况下，影响的最主要因素是车上的载客量，一般情况。在多个站点位置固定的条件下，影响的最主要因素是乘客的等车时间与车上的平均载客量。设，分别是各时段乘客因等车时间与的影响而产生的满意度，则即可表示为：=A，其中A是关于因素，的权重集。考虑到，对于乘客，对的影响是不相等的。上下车的乘客都在动态的变化着，但对车辆而言，车辆的满载率达120时，最大

27、超载的20由于缺少座位，而注重舒适度的影响，而无暇过分顾及等待时间的影响；而100的乘客因为有座，而无需过分考虑舒适，更多的是考虑等车时间的影响。又设,其中，、分别是因素、的重要程度，用层次分析中成对比较法，可知：，同时，A应满足归一性和非负性条件，即：。可解得，因此模糊优化设计模糊优化设计问题的一般模型是其中是关于x是维设计变量的目标函数；C是包括各种约束的模糊约束集，即其中和分别是第v约束的容许上下限。在求模糊目标优化设计问题时，必须确定出目标函数：的模糊优化解集的上确界M和下确界m，即其中是模糊约束集的模糊子集，即。2模型的正式建立与求解先考虑上行问题（此时）：注意到模型，是最大限度的减

28、少了车次，即增大车上的平均载客量，故此刻，公交公司的满意度达到最大。把等车的乘客看作是一个整体，因为车次最少，故乘客的平均等车时间和超载量达到最大，此刻乘客的满意度可能达最小。取各个时段的平均载客量的满意度的平均数，为公交公司日载客量的平均满意度。不妨设，则 ，而（）且 通过模型一表中数据的分析，可得日平均载客量，日平均发车时差，日平均载客量的标准差，日平均发车时差的标准差。根据检验法，可发现模型一中时，不满足，故可看作是奇异值不予以一起考虑。可求得的直方图见图3-2。图3-2 上行各时间段内满意度直方图此刻，可求得公交公司的日平均满意度可达我们可以把，满意度函数看作是常见的降半梯形分布（3-

29、1）（3-2）对于乘客，对的影响是不相等的。用成对比较法，当在早高峰时，上下车的乘客都在动态的变化着。但对车辆而言，车辆的满载率达120时，最大超载的20由于缺少座位，而注重舒适度的影响，而无暇过分顾及等待时间的影响；而100的乘客因为有座，而无需过分考虑舒适，更多的是考虑等车时间的影响，故（3-3）用图象表示为图3-3。利用公式（3-1）（3-3），可分别求得各个时段的，直方图如图3-4所示。当车辆平均满载率最大限度地接近于50时，所需的车次最多，公交公司的满意度达到最小。相应的，起始站的平均发车时间间隔最短，即乘客的平均等待时间达到最小，故此时乘客的满意度达最大。图3-3 早高峰时各时间段

30、内乘客的满意度 图3-4 各时间段内乘客满意度直方图分布同理设，第18位数据看作是特殊值。则，此刻，。可计算各时段车次与平均发车时间间隔：14, 51,100,54,30,23,27,24,20,17,17,42,54,17,9,8,8,5,6；：4.3,1.2,0.6,1.1,2,2.6,2.2,2.5,3,3.5,3.5,1.4,1.1,3.5,6.7,7.5,12,10。因此，对于上行方向，公交公司的满意度一般在。乘客的满意度能满足。根据（0.4324，1）和（0.9476，0.7838），我们可利用插值函数画出其曲线的大致走向，如图3-5。图3-5 上行方向乘客满意度关于公交公司满意度

31、拟合曲线 图3-6 上行方向匹配最优点用二次函数拟合曲线为函数：本题要求能最大限度地照顾到乘客和公交公司双方的利益，这就要求能尽可能取大，令 。通过对拟合曲线的分析，可知当平行线与相切时，如图3-6。此刻，v=1，即：。解得上行行驶时乘客和公交公司双方的匹配问题的最优满意度为：0.8805。可计算这种情形下，各时段车次与平均发车时间间隔： 6，25，42，23，13，10，12，10，10，10，10，18，24，10，6，6，4，3：10，2.4，1.4，2.6，4.6，6，5，6，6，6，6，3.3，2.5，6，12，15，15，20下行问题（此时）：同理，可求得公交公司的满意度为：，乘客

32、的满意度能满足：，根据（0.4309，1）和（0.948，0.8227），我们可利用插值函数画出其曲线的大致走向，如图3-7。图3-7 下行方向乘客满意度关于公交公司满意度拟合曲线用二次函数拟合曲线为函数：同理，求得下行行驶时的模糊最优满意度为：故可求得公交公司和乘客的日最优满意度是（0.8807,0.8807），运用逆向思维，根据日最优满意度，可找出最优的调度方案，此刻各时段车次与平均发车时间间隔为： 3, 9,23,27,16,10,12,10,10,9,11, 19,31,21,12,8,8,3：20,6.7,2.6,2.2,3.8,6,5, 6,6,6.7,5.5,3.1,1.9,2.

33、8,5,7.5,7.5,203.6 对问题3的建议二十一世纪是信息时代，随着高新科技的迅猛发展，人们对信息和数据的采集也呈现为自动化和多媒体等现代化手段的运用。现代化手段具有快捷、准确、详细、客观等显著特征。建议采集运营数据的条件和方法如下：就目前大城市公交车接待乘客的方式为“前门进中门出”特征。公交公司可运用在前后门安装两个具备多媒体功能的自动记录机，一方面，对上下车乘客数逐站作详细的记录，另一方面对加入报时间信息在内自动报站机作站名、方向和日期等作录音结合处理，给出准确的各项数据，返站后结合日期储存到公司总调度室，分别以日、月、季节等作统计分析。这对目前城市人员呈增长发展，新型的地铁、轻轨

34、电车的出现、快客的发展等随机因素的干扰，乘客量和成本的变动规律的复杂性。这种现代化手段明显比以往的发收卡片的方法更具有接近时代的优越性，也加快捷地掌握规律，按此种方案采集数据就必然会得到第一手资料，使模型设计更加符合实际。3.7 模型进一步分析3.7.1 稳定性分析一个好的模型不能因初始数据的微小误差而导致结果的较大改变。我们对最大满载率及乘客在一般时期内的等待时间做随机的微小波动，分别对模型、模型和模型加以检验，从检验的结果可以得出三个模型的稳定性比较好，其中模型和模型结果波动范围接近且稍大于模型的波动范围，因此我们认为模型是相对来说最优化模型。cij：6，30，30，30，20，12，12

35、，12，10，10，10，20，15，10，6，6，4，3；tij：10，2，2，2，3，5，5，5，6，6，6，3，4，6，10，10，15，20。总次数514次，车辆为41次，满意度分别为(0.7828，0.9373) 。 3.7.2 实时性分析由于本题可以推广为一个实时控制问题，故需要一套响应极快的实时控制系统，把现实中出现的各种随机意外情况通过控制系统传输到公交车上，使得调度员和司机对各种情况作出及时的调整。从而提高公共交通的可靠性和安全性，改善公司服务水平和提高乘客的舒适度以及公交公司的经济、社会效益。3.8 模型的评价与推广3.8.1 优缺点1普适性强：此模型对任意客流调查和运营资

36、料都可以给出较优的调度方案。2考虑全面：模型不仅解出较优的调度方案，且给出了该方案照顾到乘客和公交公司双方利益的灵敏度。3稳定性好：该模型较稳定，不随某一控制量的微小变化而导致方案的较大改变。4易操作：一方面公交公司的时刻表比较合理可行，另一方面驾驶员能容易记住自己的上班时间，以避免时间表混乱而引起误车现象。5不足之处：用光滑曲线拟合的方法无法模拟真实的客流量曲线。3.8.2 模型推广根据前面的模型所建立的运输系统可以很好的解决公交线上公交车的调度问题。然而，在建模过程中，简化了许多因素，因而与实际问题有偏差，因此，要想建立更好的调度方案，可以对一条实际运营的公共汽车线路的运行过程进行计算机模

37、拟，将调查得到的实际数据输入计算机程序，便可以得出更优的调度方案。参考文献1车克健等.在公共交通管理中应用计算机模拟的初步探讨J.系统工程理论与实践.1982.第2期：13-18. 2贺仲雄.模糊数学及其应用M.天津科技出版社.1983.1.3张韵华.Mathematica符号计算系统实用教程M.科技大学出版社.1998.9.4白其峥.数学建模案例分析M.海洋出版社.2000.1.5寿纪麟.数学建模方法与范例M.西安交通大学出版社.1993.12.6刘余善,谷宝贵主编.实用管理系统工程M.浙江人民出版社.1983.7.7胡运权.运筹学基础及其应用M.哈尔滨工业大学出版社.1997.4.附表表3

38、-2 数据统计分析表（1）时间组GT(I)上行A13开往A0下行A0开往A13最大客容量 车次最大均载客量发车时差最大客容量 车次 最大均载客量发车时差5:006:00716611910分273920分6:007:002943251182.4分103991156.7分7:008:005018421191.4分2752231202.6分8:009:002705231172.6分3223271192.2分9:0010:001528131174.6分1822161133.8分10:0011:001193101196分1093101096分11:0012:001355121135分98691096.7

39、分12:0013:001200101206分83071188.6分13:0014:00104091156.7分89181117.5分14:0015:0088181107.5分101791136.7分15:0016:0087181097.5分1302111185.5分16:0017:002133181183.3分2196191153.1分17:0018:002722241132.5分3612311161.9分18:0019:0089781167.5分2417211162.8分19:0020:00464411615分1091101096分20:0021:00410410215分78171118.6分21:0022:0027539