校车优化配置.doc

队号：H94校车优化配置摘要本文解决的是一个校车配置及运行问题，目的是用尽可能少的车接送教职工，缩短他们的等车时间以及使他们在车上呆的时间尽可能短，同时校车耗油量较少，且不超载，并且要保证家住在不同地方的教职工均能准时上下班。文中提出了一种解决此问题的模型。通过分析知，一个时刻需要的车数只与该时刻某一校区的最大转移教职工数量有关，于是我们对题目所给的数据进行一系列变换处理，求出每个时刻的最大转移教职工数，得出一组数据。根据最大转移教职工数量及校车的载客量，求出该时刻所需校车数量的最小值。综合考虑等车时间，校车利用率等，我们可以给出一天中两个时间段（上午、下午和晚上）(划分依据详见问题分析)分别需要的校车总数，取这两个时间段所需校车数目的最大值，即为全天所需校车的最少辆数，多次重复运算，取各天所需校车最少辆数的平均值作为学校需购置的最少校车数。然后将乘车时间、校车耗油量及须接送家住校外的教职工等因素考虑进去，制定出一天中校车的分配及运行线路表。用我们构造的模型，求出了一个简单易行的配置计划，并给出了校车分配及运行线路表。模型1中全天两个时间段所需40座校车的最大数量的平均值为9，故学校需配置的校车最少辆数为9辆。模型2中需购置40座的校车6辆，20座的校车2辆，6座的校车4辆。一 问题的提出为学校制定校车的最优化配置问题，要综合考虑各时刻等待登车的教职工人数，他们的住所以及各趟的耗时、耗油等因素。题目给出了每天大约有450名教职工乘车从沙河校区到清水河校区上课，另外有一部分教职工需乘车到清水河校区上班；往返两校区之间有一、二、三这三条线路可供选择，其路况详见表1。问题1有如下限制：学校配置的校车全为40座的大型车；在保证所有等待上车的教职工上车后都有座位的前提下，每个时刻发出的校车最少；各个时刻发出的校车必须沿途接送家住在校外的教职工；各趟选择耗时较短且较节省油的线路。问题2有如下限制：学校需配置大型车（40座），中型车（20座），小型车（6座）三种类型的校车各数辆；根据各个时刻乘车人数的不同灵活分配校车的种类和数量；每个时刻发出的校车沿途接送家住在校外的教职工；各趟选择耗时最短且较节省油的线路。我们的目标就是根据题目所给的已知信息，把校车配置问题抽象成一个清晰完整的数学模型，并求解。根据我们的解，为学校制定合理的购车方案，并确定一天中（此处仅考虑周一至周五）不同时刻校车的最优分配及运行线路，使学校能有效降低成本，减少开支，但又不牺牲教职工的利益。讨论该配置及运行方案的合理性及可行性，并作改进。 表1 各线路路况详表参数线路总长(Km) 平均耗时(min) 路况第一条 45 3842 不易堵车第二条3040(非交通高峰期)5090(交通高峰期) 适中第三条 20 未知 极易堵车二 模型假设 1 由于每天从沙河校区到清水河校区上班的教职工必然能回到沙河校区，因此我们可将模型简化为只考虑一天中教职工在沙河校区登车的五个时刻（为什么是五个时刻的原因参见表2）的情况； 2 不考虑周六、周日到清水河校区上课及上班的教职工数目对所需配置的校车总数的影响（由于周末到清水河上课的教职工人数很少，故能满足周一至周五教职工上下班要求的校车数一定能满足周末的需要）； 3上午到达清水河的校车中午全部回到沙河校区，下午和晚上到达清水河校区的校车在22:20之前也必须全部开往沙河校区; 4忽略到清水河上班的教职工人数对校车分配的影响。认为每天到清水河上班的教职工与上课的教职工相比人数很少，可以将他们安排在多余的座位上或者站在校车上，不影响实际所需校车数； 5 在一天中五个时刻登车的教职工数与全天总登车人数之比服从01区间上均匀分布； 6 假设学校的校车每天均能正常工作，不出现故障； 7 假设校车运行时刻表是确定的，车辆高峰期时段也是确定的（7：009：00，12：0013：00，17：3019：00）； 8只考虑夏季工作时间，认为冬季各单位工作时间均在夏季的基础上推迟半小时，故可认为影响校车配置和运行的因素(如某时刻的登车人数、高峰期时间段长度等)不变；9 根据在网上所查资料（见附录二），可近似认为单位路程汽车的耗油量与座位数呈正比；10 假设学校购置的校车全为新车。三 变量说明 ：一天中沙河校区的第j个发车时刻，其中1j5，jN； ：第i天的时刻在沙河校区的登车的教职工人数，其中1i 10，iN； ：当校车全为40座时,第i天在时刻所需校车数，N，即对代数式 = 取整 ：当校车全为40座时,第i天所需校车数量，即第i天两个时间段所需校车数的最大值. 四 问题的分析我们应该在满足教职工准时上下班的前提下，合理安排各时刻车的发送数量，使各时刻发出的校车数最少，由此得到需要购置校车的最小值。然后综合考虑运行时间，校车耗油量及须接送家住校外的教职工等因素，制定出一天中校车的分配及运行线路方案。我们的目标是求每一时刻发车的辆数，发车数取决于该时刻要运送的教职工人数，那么我们就需要求出、五个时刻从沙河校区（只考虑沙河校区的原因在模型假设1中已述）发出的校车要运送的教职工人数，鉴于时间比较紧张，要统计一天中各时刻需要登车的教职工人数较难实现，我们采用数学方法对题目所给的数据进行了变换处理，即认为一天中五个时段需要登车的教职工是随机的，各时刻登车人数与全天总登车人数之比服从01区间上的均匀分布，用计算机模拟产生450个01区间上的随机数，统计出分别落入区间(00.2)，(0.20.4)，(0.40.6)，(0.60.8)，(0.81)上的随机数个数 (表示第i次模拟落入区间j(j取、)上的随机数个数)，以此估算出全天五个时刻登车的教职工人数（具体做法详见模型1），然后算出各时刻需要分配的校车数，并采用特定算法计算出某一天所需校车的最小值 (具体算法见模型1).为保证计算结果的准确性，我们将十次模拟产生的数据,用极大似然估计法取平均值，得到较为准确的校车配置数。再综合考虑教职工居住地，投入成本及时间耗费等因素，制定出沙河校区和清水河校区校车分配及运行方案。五 模型的建立和求解根据上课时间，同时保证教职工上班时间最短，制定校车往返时刻表如下：表2 (参照附录一)校车出发时间校车开往方向校车到达时间6:40()沙河校区至清水河校区7:408:40()沙河校区至清水河校区9:3010:00清水河校区至沙河校区11:0011:50清水河校区至沙河校区12:5013:20()沙河校区至清水河校区14:1015:10()沙河校区至清水河校区16:0016:30清水河校区至沙河校区17:3018:10()沙河校区至清水河校区17:1018:20清水河校区至沙河校区19:1022:20清水河校区至沙河校区23:10模型1先不考虑各时刻登车的教职工人数的差异，假设这450名教职工在全天五个时刻上车是随机的,令产生的随机变量X表示各时刻等待登车的教职工，若随机变量XU（0，1）,即X服从（0，1）区间上的均匀分布，则有P0X0.2=0.2， P0.2X0.4=0.2， P0.4X0.6=0.2， P0.6X0.8=0.2，P0.8X1=0.2. 用计算机模拟产生450个01区间上的随机数，附录中的程序中编入了计算机模拟产生的十组在区间（0，1）区间上均匀分布的随机数的具体算法，统计出分别落入区间（00.2），（0.20.4），（0.40.6），（0.60.8），（0.81）上的随机数个数 （表示第i次模拟产生的落入区间j(j可取、)上的随机数个数)我们认为某一时刻登车的教职工数近似等于该时刻X出现的频数，即=,表示第i天的时刻需要登车的教职工人数。由此我们绘出十天中各时刻等待登车的教职工人数分布表，见表3表3 十天中各时刻登车的教职工人数分布模拟表时刻登车人数次数19885761019028210991769238790839397499859087895931068979836768310299907871038581948781047788103989878994911084809810385根据模拟产生的表3可算出第i天在时刻所需校车的最少数量为 = (1i10; 1j5;i,jN)我们规定上午、时刻校车都到达清水河校区后,才有第一批校车回沙河校区,因为在此情况下能够避免校车空车返回,增大耗油量，并且由于路况因素未知可能使接送教职工的校车晚点,使等车时间延长,若、时刻发出的校车总数是当日学校所能调动的最大校车量,此数量可能就是学校配置的校车数,因此将、所在的时段看作一个整体;又由于时刻来上晚自习的教职工18:10就要在沙河校区登车,这个时间与下午回沙河的车时间上重叠,故将、所在的时段也看作一个整体,对第一个时段的分析方法对第二个时段同样也适用。由于要保证所有教职工都能准时上下班,故在两个时段所需校车总数中取最大值即为一天所需校车数量，也就是学校应配置的校车数N。为保证计算结果的准确性，我们将十次模拟产生的数据,用极大似然估计方法取平均值，得到较为准确的校车配置数。运行程序 得到第i天所需的校车总数为= max(+),(+) (1i10 i) (见表4) 表4 每天所需校车数量分布表天次第一天第二天第三天第四天第五天第六天第七天第八天第九天第十天车数8 8 99899899该十个样本的样本均值= =8.6依据数理统计中关于参数的极大似然估计方法，统计出学校需购校车数量的值为，但考虑到实际情况，取实际所需配置的校车数 N= =9此时样本方差= =0.24方差值很小，故可认为各天所需校车数与学校购置的校车数量基本相当，即该种购置方案具有合理性。运行方案：为使老师等车时间尽量少,在交通低峰期尽量走路程最短，耗油少的第二条或第三条线路，而在8：40从沙河发出的校车；11：50从清水河发出的校车；18：10从沙河发出的校车；18：20从清水河发出的校车尽量走不太拥挤，耗时短的第一条线路，但为保证能接送所有教职工准时上下班，每次往返于两校区之间的校车必须至少分配一辆走第三条线路，考虑到实际家住校外的教职工比例不是很大（据统计占全校教职工总数的比例不到20%），因此可以认为每个时刻分配一辆校车走第三条线路完全能接送完此刻需要登车的家住校外的教职工（假设各个时刻所有家住校外的教职工都乘坐走第三条线路的校车），因此为简化模型，将一天中每个高峰期走第三条线路的校车减少为一辆。由此我们得出校车分配和运行方案。模型2与模型1相同,产生450个0到1的随机数来模拟教职工在沙河校区的不同时刻(、)登车人数(参见表3)。增加变量：第i天的时刻所需40座的校车数；：第i天的时刻所需20座的校车数；：第i天的时刻所需6座的校车数。：统计十次模拟数据得到学校需购置的40座的校车数量的期望值；：统计十次模拟数据得到学校需购置的20座的校车数量的期望值；：统计十次模拟数据得到学校需购置的6座的校车数量的期望值。令、的初始值为0，对第i天的时刻登车人数求各种类型车的算法规定如下用除以40，得到的商为p，并求出余数q，综合考虑购置校车的成本，各种车型的耗油量及座位利用率等因素，得出宁愿选择一辆20座的中型车也不选用两辆6座的小型车的结论，确定算法如下： 当27q39时，再安排一辆40座的车，即=p+1, =0, =0；. 当21q25时，再安排一辆20座的车，一辆6座的车，=p，=1，=1； 当12q20时，再安排一辆20座的车；=p ，=1，=0； 当7q11时，再安排两辆6座的车；=p， =0，=2； 当1q6时，再安排一辆6座的车。=p，=0，=1.（具体算法详见附录四）通过此算法,求得各个时刻需要各类车数量见表5 表5 时刻 车型次数T1T2T3T4T5402064020640206402064020612102011002112022201300202100202320220220121021042102011022022025210211202100201610020121121020272022112012012108100211100202211920220220221020210201200210211201同样根据模型1的分析得：=max(+),(+)， 表示第i次模拟需要40座校车数量 =max(+),(+)， 表示第i次模拟需要20座校车数量 =max(+),(+)， 表示第i次模拟需要6座校车数量得到结果如表6表6车型座)车数次数40座20座6座15132504362446165523662376138513961410622同样根据模型1的分析, 采用数理统计中参数的极大似然估计方法，统计出学校需购各类校车数量的期望值=5.6；=1.3；=3.5.根据实际情况，可得学校需配置的40座的校车数为 X=6；需配置的20座的校车数为 Y=2；需配置的6座的校车数为Z=4.通过以上算法确定出了各类校车的配置数，以下说明校车的运行方案。运行方案： 根据我们统计的数据，住在每次住在市区的教职工上班人数不到总教职工上班人数的20%（在模型1中已作了说明），根据表5模拟产生的人数，统计出每次有不到26名家住校外的教职工需要登车。根据模型1中的思想，为使老师等车时间尽量少,在交通低峰期尽量走路程最短，耗油少的第二或第三条线路，而在8：40从沙河发出的校车；11：50从清水河发出的校车；18：10从沙河发出的校车；18：20从清水河发出的校车尽量走不太拥挤，耗时短的第一条线路，但为保证能接送所有教职工准时上下班，每次往返于两校区之间的校车在高峰期至多分配一辆20座和一辆6座的走第三号线路，具体分配方案根据当时家住校外的教职工人数而定,以期达到校车座位利用率和耗油量达到最优。六 模型评价及改进1 在确定校车数时，用计算机模拟来产生一天中五个时刻在沙河校区登车的教职工数，并采用样本估计总体的思想估计实际值，解决了时间有限从而采集数据难的困难，但由于模拟的次数不够多（只有十次）,得到结果与真实值之间存在一定误差。2 模型1和2只考虑从沙河校区登车教职工数，来确定校车数，忽略从清水河登车教职工数对校车数量的影响，简化了模型。因为在清水河上课的老师可能出现连续几节有课的情况，必然出现某个时刻在沙河校区不同时刻登车的教职工在清水河校区的同一时刻登车，使该时刻在清水河登车的教职工数大于一天中五个时刻分别在沙河登车的教职工人数的最大值，由于此种情况发生的概率小于我们假定情况发生的概率，因此这种简化方式具有合理性。3 模型1中在对校车制定分配及运行方案时,根据我们模拟的数据推算出各个时刻等待登车且家住校外的教职工人数少于40人,并假设他们在交通高峰期乘坐同一辆校车,这只是我们统计的一般情况,但若考虑一些偶然因素,将会带来校车的不同分配及运行安排.4 模型1简化了问题的处理,认为校车每天都正常工作,一天中各个时刻到清水河上课的教职工人数服从0450区间上的均匀分布,但是若某天有校车出现故障不能运行,必然导致所需的校车数得不到满足,势必带来校车的重新配置.同样,由于每天各个时刻来上课的教职工人数在严格意义上并不服从均匀分布,当某一天某个时段来上课的教职工人数过多时,可能造成校车紧缺. 但若我们统计出一天中5个时刻在沙河校区登车的教职工的准确概率，计算结果将更接近真实值，在我们的程序中可以做此修正，在程序运行时输入改成我们统计的各时刻的概率，算出的校车数就是更为精确的值。5 模型2中购买座位数不同的车，购车数较模型1有所增加，但根据附录三中的数据可知两种购车方案实际所需成本相当，并且根据我们的假设，单位路程校车耗油量与座位数呈线性关系，使得模型2在运行时，校车往返与两个校区之间总是耗油较模型1少。由于目前石油价格很高，若这些校车的使用年限足够长，若干年后在汽油耗费上节约的钱将会很多，那么在这种假设下，模型2明显优于模型1。若某天需要登车的教职工人数不是很多，可将两个模型中当天多余的一部分车对外出租或供学生搭乘。七 参考文献1 徐全智、吕恕.概率论与数理统计.北京：高等教育出版社，20072 徐全智、杨晋浩.数学建模.北京：高等教育出版社，20043 杨启帆、何勇、谈之奕.数学建模竞赛:浙江大学学生获奖论文点评1999-2004.浙江：浙江大学出版社，2006附录一 电子科技大学沙河校区、清水河校区夏季往返班车运行时刻表一、星期一至星期五沙河校区至清水河校区班车时刻表发车时间及地点到达时间及地点6:50八里小区二区3号门前7:40清水河校区学生活动中心6:50沙河校区学生活动中心8:40八里小区二区3号门前9:30清水河校区学生活动中心8:40沙河校区学生活动中心13:20八里小区二区3号门前14:10清水河校区学生活动中心13:20沙河校区学生活动中心15:10八里小区二区3号门前16:00清水河校区学生活动中心15:10沙河校区学生活动中心18:10沙河校区学生活动中心18:20八里小区二区3号门前19:10清水河校区学生活动中心二、星期一至星期五清水河校区至沙河校区班车时刻表发车时间及地点到达时间及地点10:00清水河校区学生活动中心11:00沙河校区学生活动中心11:50清水河校区学生活动中心12:50沙河校区学生活动中心16:30清水河校区学生活动中心17:30沙河校区学生活动中心18:20清水河校区学生活动中心19:10沙河校区学生活动中心22:20清水河校区学生活动