数学建模-班车的合理安排

1、第十一届学科竞赛之数学建模竞赛承诺书我们仔细阅读了大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权河大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正

2、式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：C参赛队员（打印并签名）：序号姓名（打印）所在学院（打印）签名（手签）1郭廷桢物理与机电工程学院2魏晓明物理与机电工程学院3岳春烈物理与机电工程学院指导教师或指导教师组负责人（打印并签名）：日期：2015年5月旦日评阅编号（由竞赛组委会评阅前进行编号）：第十届学科竞赛之数学建模竞赛评阅专用页评阅编号（由竞赛组委会评阅前进行编号）：评阅记录（供竞赛组委会评阅时使用）：评阅人评分备注评阅结果:获奖等级: 班车的合理安排摘要：本文针对班车的合理安排，关于发车时间、线路、每条路线的运行时间、班次和各个车辆的耗油成本的问题建立相应的数学

3、模型，在问题解决过程中采用了穷举算法和递归算法。分析、建立模型、求解过程中，利用MATLAB对数据进行分析、处理，并用C语言实现某些算法，得出相应的结论。问题1通过分析题中所给的数据，对线路1每天乘坐人数建立单因素方差分析模型，假设临界值为0.05，在MATLAB中用函数P=anoval(X)来计算概率值，得出P0.05，故认为问题1结果不存在显著的差异。问题2根据题中所给数据，通过研究分析，建立派车最优化组合模型，再增加耗油成本变量，建立单目标最优化模型,再通过C语言运用穷举法求出最优解,得出每日最低耗油成本同时确定了班车的安排方式，其安排方式见表5.6所示。对于问题3在问题2的基础上进一步

4、考虑班车之间运行的相互影响，深入改善建立单目标最优化模型，采用C语言穷举法求出班车运行时的最低耗油成本，得出最佳行车组合方式，其安排方式见表5.9所示。关键字：优化模型、C语言穷举算法、MATLAB单因素方差分析、递归算法一、问题重述班车的合理安排是一个优化合理模型。必须保证每位教职工有座且准时到达目的地，要考虑路线最佳车辆分配最为合理；也就是说在能保证老师被安全准时的前提下，车辆的安排要最省钱，也就最优分配；再分配过程中要考虑每辆车运送时间差是否满足运输时刻表的安排，同时也要考虑班车的座位是否满足需求。如何在校车运行与节约资源取得最大效益，已经成为了困扰众多高校的问题之一。本文就是为了解决这

5、一问题而撰写的。某高校地处市郊，共设立了五条不同方向的接送线路，从周一至周五每天用班车接送居住在市区沿途线路的教职工。这五条线路市区与学校之间的平均运行时间依次分别需要45分钟，70分钟，60分钟，20分钟和50分钟。目前学校配有五辆班车，分别是55座、45座、40座、33座和26座，根据经验和当前油价，这五辆班车的油耗大约分别是5元/分钟、4元/分钟、4元/分钟、3元/分钟和2元/分钟。此外，由于周一至周五每日的课程安排不同，因此每日乘坐同一班次的教职工人数也是不同的。对各条线路而言，每日早晨07:00从市区用哪一辆班车到学校，下午17:40就用这辆班车回到市区。要求每班次的车都应当保证有充

6、足的座位，即不能出现有人因座位不足而站着的情况。若校车到达终点站时，距离终点站返回学校下一班车时刻时尚早，或该终点站当日已经没有返回学校的班次，则空车返回学校或者视情况考虑安排到另一个线路的终点站再沿途接入学校。二、符号说明班车A:55座，耗油5元/分钟；班车B：45座，耗油4元/分钟；班车C：40座，耗油4元/分钟；班车D：33座，耗油3元/分钟；班车E：26座，耗油2元/分钟；S(i):星期一到星期五中每班次车最多人数Fy：A、B、C、D、E五辆车对应的价格/每分钟Sj：每条路线运行时长S:因素A的效应平方和；S:误差的平方和；S:总和、X.；线路1每天AETij每班次车所对应的人数；Hy

7、：耗油量Cz(i)：班车A、B、C、D、E的车座个数三、问题分析本问题是合理优化模型。必须保证每位老师有座并且准时到达目的地，且要考虑线路最佳车辆分配最为合理；具体就是在能保证老师被安全准时接送的条件下，车辆的安排要最省钱，也就是最优分配；在分配过程中要考虑每辆车运送时的时间差是否满足运输时刻表的安排。为方便建模求解经过分析将班次和时间绑定起来在分析过程中就可以简化一个决策变量，方便分析。为使每位老师都有座位我们把乘坐各班次的人数统计表中取其最大值，以保证每位老师都可以准时有座往返。尽可能在不影响建模求解准确性的情况下，简化决策变量，并以表格形式给出。3.1问题1的分析问题1属于单因素实验方差

8、分析的数学问题，解决此类问题一般用数学方法分析。由附件中给出的数据特点分析，取出其中的最大值建立模型、编程、对其所要求的结果进行分析。由于上述原因，建立单因素方差分析模型，对结果进行预测，并将结果进行比较。对问题1的具体分析如下：由于各个学校的排课时间不同，各教职工所居住的地方各不相同，因此，考虑线路1周一至周五教职工的乘车情况各不相同，现就此问题进行分析，将分析求出星期一至星期五平均每天运送的教职工人数差异。3.2问题2的分析由于许多城市交通拥挤，上班坐车不方便，经常遇到堵车或乘不上车等诸多问题，使得教职工不能按时到达指定的地点，现就此问题进行分析、讨论、建立数学模型,分配出合理的班次及路线

9、。对问题2的具体分析如下：问题2属于最优组合的数学问题，解决此类问题用数学分析法排列组合最佳的分配组合方式。运用穷举法和递归法解决排列组合的最优值。3.3问题3的分析对问题3的具体分析如下：由于许多城市交通拥挤，上班坐车不方便，经常遇到堵车或乘不上车等诸多问题，使得教职工不能按时到达指定的地点，现就此问题进行分析、讨论、建立数学模型，分配出合理的班次及路线。又考虑到车空返回时耗油成本问题，进行对问题的进一步优化，在问题二的基础上减少车的空泛情况在满足教职工人数和时间要求的基础上使得耗油成本达到最低，使问题更进一步得到优化。在问题三中，对于到达终点站距离该终点站返回学校的下一班车发车时刻尚早，或

10、该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情况考虑安排到另一个线路的终点站，再沿途接人到学校这一类情况。我们也可以确定一个新的分类方式与油耗成本计算方法。在所有的问题中，我们都要考虑到各站点运行时间问题和座位满足问题。同时也要考虑单位时间油耗成本问题。四、模型的假设在问题一的模型建立与数据处理计算中首先假设如表4.1中每天每班次车的人数都服从正态分布，即：XN（卩Q2）。iji表4.1一星期中每天最多人数统计图班次1班次6班次13班次7班次8班次14班次15星期一44253513271545星期二52204012381840星期三38153823451245星期四461

11、83616431542星期五50203221391650在问题二三的建模中我们假设：1、沿途没有堵车现象出现；2、每位教职工都能按时的在接送点等车并且上车时间忽略不计;3、所给数据基本上真实有效无误差；4、每位教职工临时有事请假不记。五、模型的建立与求解5.1问题1的模型建立与求解5.1.1问题1的模型建立为了比较线路一中星期一到星期五每天运送的教职工人数是否存在显著差异，分别以叽卩2,卩3,卩4,卩5代表星期一至星期五每天总人数的平均值，我们需要检验假设3二0.05)Ho:pl二|n2二卩3二|n4二卩5%:卩1,p2,p3,p4,p5不完全相等表4.1中所有变量：n=35,种类：r=5，各

12、种类对应变量：n1=n2=n3=n4=n5=7,T.=迓X,j=1,2,.,s,T.=YKX,i=1/=1i=1S=YYx2-nX2=YYx2-HTijijnj=1i=1j=1i=1S=Kn厂2-nX2=工巴-HAj.Jnnj=1j=1jS=S-SETA表5.1单因素方差分析表方差来源平方和自由度均方和F值显著性因子影响SAr-1S/(r1)A随机误差SEn一rS/(n一r)EF*总和STn一1要分析线路1星期一至星期五平均每天运送的教职工是否存在显著差异先求线路1每天所要运送的教职工人数S,首先验证S是否符合正态分布(这里显然是的)再以线路一每天所要运送的额教职工人数为检验变量进行单样本f检

13、验。5.1.1问题1的模型求解在MATLAB中使用p=anova1(X)比较X中各列数据的均值是否相等。此时输出的p是零假设成立时，数据的概率，当p0.05称差异是显著的，当p0.05,所以线路1星期一至星期五平均每天运送教职工人数不存在明显的显著差异。5.2问题2的模型建立与求解5.2.1问题2的模型建立（1）为使我们建立模型方便计算，我们简化表格减少决策变量，因为首先虑班车的座位是否满足需求，对一星期之中每班次车乘坐人数取最大值，所以得如下表格表5.2每班次车对应最多人数表班次12345678910人数52282622422523453024班次111213141516171819人数38

14、1540185026252042表5.3每日班车发车时刻及班次编号线路方向发车时刻班次编号发车时刻班次编号发车时刻班次编号发车时刻班次编号1上行0700109:00613:0013下行0950712:10815:501417:40152上行0700212:4011下行1210917:40163上行0700312:4012下行1740174上行07004下行12101017:40185上行07005下行174019（2）建立模型，首先考虑每班次的车都应当保证有充足的座位，再对剩余的进行排列组合，根据耗油费最少解出最优解。表5.4班次1-5与班次15-19最多人数班次1班次2班次3班次4班次5人数

15、5228262242班次15班次16班次17班次18班次19人数5026252042在07:00时五条路线要同时发车，且学校只有五辆校车，要同时从五条线路发车，再考虑满足座位需求的情况下，再对运费进行计算，则有唯一的派车方式，班次1，2,3,4,5分别派出A,E,D,C,B车，同理考虑满足座位需求的情况下，班次15到班次19也已经确定了派车安排方式。表5.5班次6-14最多人数班次6班次7班次8班次9班次10班次11班次12班次13班次14252345302438154018在09:00时线路一需派出一车而其它线路距离派车时刻尚早，且五辆车都处于空闲状态，因此考虑空车返回问题，乘坐班次6的教职

16、工有25人，所以派出E车是最合理的。同样的班次7的情况和班次6类似，乘坐的人数为13。E车在班次6时被派出，返校时间为09:45，时间不冲突，故班次7派出E车。班次8到班次13时间间隔比较小，因此应优先考虑时间问题。同时班次8和班次13应同时考虑，班次8不需要空车返回，所以班次8排出的车的座位必须满足班次13乘坐的教职工的需求。因此，只需考虑班次11,13的座位满足问题。班次11,13均需运载35人，可派出班车A,B,C；班次9,10,12可派出五辆车的任一辆。考虑到每条路线的运行时间和每辆车的运行成本，班次8派出A车，班次11可派出B车(或者C车)。班次9运行时间最久，因此派出E车。班次10

17、运行时间短可派出C车(或者B车)，班次12派出D车，而班次14时间间隔大，需空车返回，只需考虑座位满足和成本问题，可派出E车。F*minf(Hy)mins.t.S(i)Cz(i)T(i)=45,70,60,20,50Hy=5,4,4,3,2f.(Hy)=T(i)*Hymin5.2.2问题2的模型求解穷举法是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。for(x=0;x=n1；x+)for(y=0;y=n2;y+)for(z=0;z=n3;z+)for(m=0;m.1.S1.11亠J

18、-亠上J-YJ-_二-G00500AEDcn器2818益器=9=2=1db-i-44扣=3T牛抽芻爲油选选选述选eeap-cdda卡号E1slGl?i8lv丙由丙而辆辆辆辆辆的的疥由上悄小咲车车丰半车目fillip04耳亠斗I5678911七二七二Pressanijkeytacontline图5.2VisualC+运行结果经过对数据处理和考虑座位、时间间隔、耗费等综合因素情况下，得出既方便老师又节约的最佳每日班车的合理安排表：表5.6每日班车的合理安排表车次编号时间车辆代号起点方向线路终占k、八、耗费（元）17:00-7:45A终占一、八、上行线路一学校22527:00-8:10E终占二、八、

19、*上行线路二学校14037:00-7:45D终占三、八、上行线路三学校18047:00-7:20C终点四上行线路四学校80表5.6每日班车的合理安排表（续）57:00-7:50B终点五上行线路五学校20068:10-8:55E学校（空）下行线路一终占一、八、909:00-9:45E终占一、八、上行路线一学校9079:50-10:35E学校下行线路一终占一、八、90812:10-12:55A学校下行线路一终占一、八、225910:40-11:50E终占一、八、（空）上行线路一学校9012:10-13:20E学校下行路线二终占二、八、*1401012:10-12:30C学校下行线路四终点四8011

20、11:30-12:40B学校（空）下行线路二终占二、八、*28012:40-13:50B终占二、八、上行线路二学校2801211:40-12:40D学校（空）下行路线三终占三、八、18012:40-13:40D终占三、八、上行线路三学校1801313:00-13:45A终占一、八、上行线路一学校2251414:40-15:50E终占二、八、（空）上行路线二学校14015:50-16:35E学校下行线路一终占一、八、901517:40-A学校下行线路一终占一、八、2251616:55-17:40E终占一、八、（空）上行路线一学校9017:40-E学校下行线路二终占二、八、*1401717:40-

21、D学校下行线路三终占三、八、1801817:40-C学校下行线路四终点四801917:40-B学校下行线路五终点五1005.3问题3的模型建立与求解对于到达终点站距离该终点站返回学校的下一班车发车时刻尚早，或该终点站当日已经没有返回学校的班次，这时不必非得空车返回学校，可视情况考虑安排到另一个线路的终点站，再沿途接人到学校这一类情况下，在问题2的基础上，修改已建立的模型。表5.7班次1-5与班次15-19最多人数班次1班次2班次3班次4班次5人数5228262242班次15班次16班次17班次18班次19人数5026252042在07:00时五条路线要同时发车，且学校只有五辆校车，要同时从五条

22、线路发车，再考虑满足座位需求的情况下，再对运费进行计算，则有唯一的派车方式，班次1，2,3,4,5分别派出A,E,D,C,B车，同理考虑满足座位需求的情况下，班次15到班次19也已经确定了派车安排方式。表5.8班次6-14最多人数班次6班次7班次8班次9班次10班次11班次12班次13班次14252345302438154018在09:00时线路一需派出一车而其它线路距离派车时刻尚早，且五辆车都处于空闲状态，因此考虑空车返回问题，乘坐班次6的教职工有25人，所以派出E车是最合理的。从终点一到终点三之间的时间为10分钟，而班次12的返校时间为12:40时间不冲突，而且五天之内最多的人数为15人，

23、考虑耗油量最小，所以派E车，剩余的班次8,9,10,11,12,13因为其时间间隔较小，所以优先考虑时间问题，又因为班次13和11在这五天之内最多的人数分别为40,班次8所以应在A、B、C,三辆车之间选择，考虑耗油量问题，经穷举递归算法编程得到班次8选择B车,班次13又与B在同一条线路上而且班次13人数较多所以选择B车在13:00时原路返回，班次9和班次11也可通过与班次8和13同样的思路得到其应该派C车。在处理决策变量后将数据输入所编数学模型，得到结果：微软拼音半:PressanykeytocontinueD:CYuYanbinwwtemp.exe由由-EEBCDCEBEdsnsK部部部部睪

24、睪睪睪睪睪睪睪睪国目芻罚芻返返012312345678911111次次次次次次次次次次次次次次车rLLrLLrLLrLLrLLrLLrLLrLLrLLrLLrLLrLLrLLrLL-I3-JJ-JJ-JJ-3-JJ-JJ-JJ-TJJ-JJ-TJJ-3-TJJ-JJ-.0000000AEDCB00880828022991262119023由由由由由由由由由h:.-:远选选选选：；5678911111由日日日日500024800图5.3C/C+运行结果经过对数据处理和考虑座位、时间间隔、耗费等综合因素情况下，得出既方便老师又节约的最佳每日班车的合理安排表：表5.9最佳每日班车的合理安排表车次编号

25、时间车辆代号起点方向线路终占k、八、耗费（元）17:00-7:45A终占一、八、上行线路一学校22527:00-8:10E终占二、八、*上行线路二学校14037:00-7:45D终占三、八、上行线路三学校18047:00-7:20C终点四上行线路四学校8057:00-7:50B终点五上行线路五学校20068:10-8:55E学校（空）下行线路一终占一、八、909:00-9:45E终占一、八、上行路线一学校9079:50-10:35E学校下行线路一终占一、八、90812:10-12:55B学校下行线路一终占一、八、180表5.9最佳每日班车的合理安排表（续）912:10-13:20C学校下行路线

26、二终占二、八、2801012:10-12:30D学校下行线路四终点四601112:40-13:50C终占二、八、上行线路二学校2801212:30-12:40E终占一、八、终占三、八、2012:40-13:40E终占三、八、上行线路三学校1201313:00-13:45B终占一、八、上行线路一学校1801415:50-16:35E学校下行线路一终占一、八、901517:40A学校下行线路一终占一、八、2251616:55-17:40E终占一、八、（空）上行路线一学校9017:40-E学校下行线路二终占二、八、*1401717:40-D学校下行线路三终占三、八、1801817:40-C学校下行线

27、路四终点四801917:40-B学校下行线路五终点五100六、误差分析对给的参考数据我们为保证每位老师都有座位对其取了最大值，这样有可能不能使得资源最优配置。模型是建立在一系列假设的基础上，所得的结果与实际问题存在一定的偏差。七、模型应用及推广本模型可以应用于对学校的校车合理最优配置，以更方便老师节约资源。显而易见，这是一个典型的规划模型，通过资源配置最优化为杠杆平衡它们之间的分配关系。1、决策者要通过概念抽象、关系分析可将各类影响因子放入规划模型中，可以通过相关的计算软件得到兼顾全局的最优解。2、规划模型有着广泛的适用范围，涉及到投资时，有限的资金如何分配到各种投资方式上；工厂选址时，要兼顾

28、距离原料区和服务区的路程这一类问题均能得到较好的解决。规划模型在工业、商业、交通运输、工程技术、行政管理等领域都有着广泛的运用。3、通过数据的稍微处理，即可运用于各个行业的车辆调度。将线路换乘机器,油耗换乘能源，即可求出最有节能方案。模型运用范围极广。八、模型评价该模型结构简单易用，普适性强，可以针对不同校车时间安排表和乘坐各班次的人数统计表，给出最为合理的车次安排表。该模型不能直接被套用，还需要对数据进行处理才能带入。优点：1、建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；2、原始数据进行了处理，找出变量间的潜在关系；3、对模型涉及的众多影响因

29、素进行量化分析，使得论文更具有说服力。缺点：1、为保证所有老师都有座位对其取了最大值，这样有可能使得在资源不能得到最优配置。九、参考文献盛骤，谢式千，潘承毅，浙江大学，概率论与数理统计（第四版），高等教育出版社，2008年，起始页码：224页，终止页码：233页。唐向宏、岳恒立、郑雪峰，MATLBA及在电子信息类课程中的应用（第二版），北京：电子工业出版社，2009年。谭浩强，C语言程序设计（第三版），北京：清华大学出版社，2005年。何晓群，多元统计分析（第三版），中国人民大学出版社，2012年。（新西兰）MarkM.Meerschaert著，刘来福，黄海洋译，数学建模方法与分析，北京：机械

30、工业出版社，2005年。附录:(1)问题一MATLAB语言程序X=4425351327154552204012381840381538234512454618361643154250203221391650A=X;group=星期一，；星期二，；星期三，；星期四，；星期五;p=anoval(A,group);(2)问题二C语言程序#includestdio.hints=52,28,26,22,42,25,23,45,30,24,38,15,40,18,50,26,25,20,42;/星期一到星期五中每班次车最多人数intfy=5,4,4,3,2;/ABCDE五辆车对应的价格/每分钟intsj=

31、45,70,60,20,50;/每条路线运行时长charc=A,B,C,D,E;inti,Qa,Qb,hy,min=1000;voidmain()inthy1,hy2,hy3,hy4,hy5,hy6,hy7,hy8,hy9,hy10,hy11,hy12,hy13,hy14;intx,y,z;for(i=0;i5;i+)if(si=50)Qa=sj0;Qb=fy0;hy1=Qa*Qb;printf(班次%d与班次%d选择车辆%c耗油=%dn,i+1,i+15,ci,hy1);elseif(40=si&siints=52,28,26,22,42,25,23,45,30,24,38,15,40,18

32、,50,26,25,20,42;/星期一到星期五中每班次车最多人数intfy=5,4,4,3,2;/ABCDE五辆车对应的价格/每分钟intsj=45,70,60,20,50;/每条路线运行时长charc=A,B,C,D,E;inti,Qa,Qb,hy,min=1000;voidmain()inthy1,hy2,hy3,hy4,hy5,hy6,hy7,hy8,hy9,hy10,hy11,hy12,hy13,hy14;intx,y,z;for(i=0;i5;i+)if(si=50)Qa=sj0;Qb=fy0;hy1=Qa*Qb;printf(班次%d与班次%d选择车辆%c耗油=%dn,i+1,i+15,ci,hy1);elseif(40=si&si50)Qa=sj4;Qb=fy1;hy5=Qa*Qb;printf(班次%d与班次%d选择车辆%c耗油=%dn,i+1,i+15,c1,hy5);elsefor(x=2;x=4;x+)for(y=2;y=4;y+)for(z=2;z=4;z+)if(x!=y&x!=z)if(y!=z)hy2=sjl*fyx;hy3=s