校车安排问题(数学建模)

1、数学建模竞赛校车安排摘要：校车安排问题涉及到最短距离的求出与资源的最优化配置，以及教师工作人员对这种安 排的满意度，和相关经费等问题。关于这些问题的解决，可以利用计算机计算求解结果，然后统 一实施安排。最后，我们充分考虑现实生活中存在的一些情况，提出一些建议，以提高乘车人员 的满意度，而且可以有效节省运行成本及相关费用。关键词：数学建模；最短距离；车辆安排；floyd函数；lingo函数；满意度；计算机计算， 图论；matlabo1 问题重述：近年来，许多大学都建有新校区，自然就涉及到新老校区教师及有关工作人员的运送问题。主要 体现在校车的合理安排上，一种情况是教师及有关工作人员到乘车点走的路

2、太多，另一种情况是 教师及有关工作人员在乘车点等待的时间太久，其次还有汽车的能耗问题，这就要求我们提供一 种比较合理的令人满意的比较经济的乘车地点的选择和发车时间的安排。依据题中所给的数据完成以下问题：（1）、如要建立77个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在 哪斤个点。建立一般模型，并给出h = 2,3时的结果。（2）、若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪刃 个点。建立一般模型，并给出 =2,3时的结果。（3）、若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘 车点的位置和车辆数。设每辆车最

3、多载客47人（假定车只在起始站点载人）。（4）、关于校车安排问题，你述有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省 运行成本2 模型的假设及符号声明2.1模型的假设(1) 、假设所有乘车点设立在各小区(点)上，乘车站点不设立在路上。 为简单起见，假设所有的站点和小区为一个质点不考虑它的实际大小。(2) 、题目中表1所给出的两区距离的两小区之间可以直达，未给出小区距离的两小区之间必须 通过有已知距离小区绕行。(3) 、假设在校园里交通是畅通无阻的，在路上不会发生任何意外。(4) 、假设车的状况都相同。(5) 、忽略坐上车之后耗时(根据绝大多数人的心理，坐上车之后就感觉很快就会到达目的

4、地) 及其他因素对学生满意程度的影响。(6) 、假设人们对满意度的评价只和去乘车点所走路程总和为参考，假设所有人走路速度基本相 同，假设人们坐上车就会很快岀发。2.2符号声明和术语声明(1</<50)小区的编号q(1d)n个乘车点中的第i个乘车点q(j = l,2,50)小区pj(l< j< 50)到乘车点ql<i<n< 50)的最短路程b(n)各小区到达n个乘车点中距离各自最近的乘车点的最短路程之和厶(1550)表示在小区50)内的总人数3 模型的分析3.1问题一的分析这是一个最优化问题。目的是在校园里设立斤个乘车点，使各区人员到最近乘车点的距离最小

5、。在假设所有乘车点都设在各区域内，而不设在路上前提下，50</1的情况就没有意义，所以仅考 虑1<«<50的情况。这时我们分四步思考：首先，我们从50个小区屮任意选出刃个小区作为乘 车点；然后，算出每个小区分别到这斤个乘车点的可能途径的路程，再经过比较确定每一个小区 到这q个乘车点中每一个乘车点的最短路程；之后可确定每一个小区的最近乘车点，再把每一个 小区到距离它最近的乘车点的路程加起来得工,依次类推把这c50种可能工 的都算出来；比 较这五十工,其小的工 对应的川个小区就作为建立“个乘车点的最佳乘车点！3. 2问题二的分析3. 3问题三的分析该问要同时求出最优的三

6、个乘车点和最优的车辆分配方案，为简化模型起见，我们肓接用问题二 的3个点17, 22, 31点作为乘车点，使教师和工作人员尽量满意，我们假设这个满意度是以教师 和工作人员到乘车点所走的总距离和为量度。一、考虑到现实情况屮并不是所有的教师会在同一时间坐车去新校区，因为并不是所有的教师都 在同一吋间上课，二、考虑到因为是学校内部的教师专用车，所以通常教师坐车会集中在几个时间段，大致服从以 下坐标系的分布三、一般而言，早上坐车的老师在一天中所占比例最高，设为pl,这个比例的求出可以通过抽样 调查的方式确定。对全体2501位老师进行抽样调查，得出他们在上午8点坐车的比例在每周的五 个工作日的平均值。3

7、4问题四的分析我们要解决的问题是：提高乘车人员的满意度；节省运行成本。即协调乘车人员想随到随走的期 望和运行商想车座满后再走的孑盾。分两个方面考虑：乘车人员、运行商4模型的建立、求解及结果表示4. 1问题1的模型4.1.1问题1模型的建立用b（n）表示各小区到达n个乘车点中距离各自最近的乘车点的最短路程之和用2, .（； = 1,2,50）表示小区50）到乘车点q （1 9 k 50）的最短路程当选取n个乘车点时，共有种选择情况，对于每一种情况均可得出以下两个矩阵0qi 12 j、q 2qi 2qn 2q 3 q2 3 qn 3 1 q 50q2 50qn 50)q i = minq qn ,

8、q2 2 = minq2 qn 2 g. 3=minei3 . q 3爲 50 = min q 50qn 50（其中，qn，qi2，qj ,q&有可能就是同一个乘车点）50 从而可得： 側=工0 k k=针对每一种情况考虑b（）,对结果进行比较得到：口标函数: min叭得出min b（jl）所对应那一种组合（q q2qn）即可得个乘车点的具体位置4.1.2问题一的求解由题目给出的各区距离表1及假设1、2运用floyd算法（参见附录一 floyd.m文件，矩阵及 表示表1各点之间的距离），可以求出50区中任意两区之间的最短路。2当n=2吋，在50个点中一共有c 种取法，分别对每一种取法运

9、用matlab进行运算，可以得50到驳2）,求出min b（2）所对应的两乘车点（具体的matlab运算程序参见附录二）3同理，当n=3吋，在50个点中一共有c 种取法，分别对每一种取法运用matlab进行运算，50可以得到b3）,求出min s3所对应的三乘车点（具体的matlab运算程序参见附录三）当n>3吋，在50个点中一共有c”种取法，依然分别对每一种取法求出求出min hq50所对应的n个乘车点。但随着n值的增大，此时虽然在计算机编程上理论上可行，但是计算量明 显增多，例如取25个点吋需要几十年的吋间才能完成计算，显然不合理。但由于在现实情况中， 50个区一般不可能安置10个以

10、上的乘车点，而且如果乘车点过多，那么就相当于每两三个区的 人共用一个乘车点，乘车点再多些就成了好像每一家都拥有私家车一样。所以对于本题，我们不 考虑n>10的情况。对于n介于4和10之间的情况，我们选取到所有其他点最短距离和小于40000 的n个点（50个区之间任意两点的距离已由floyd算法算出），并在这n个点中间选出相对距离较 远的几个点，以保证这n个点不会过于集中，从而确定此n点的位置。4. 1.3问题一的结果表示运用floyd算法后，得出50区中任意两区之间的最短距离，由于篇幅有限，下表仅列岀1区 与10区任意两区之间的最短距离表411区与10区任意两区z间的最短距离区域号123

11、456789101040045070091011401110128014801614240008503005107407108801080121434508500810600830800970117013504700300600021044041058078096059105108102100230200370570750611407401040440230032034054072071110710101041020032001703705508128088011805803703401700200380914801080138078057054037020001801016141214156

12、09607507205503801800当冲2时，可以求出当乘车点建在18号区域和31号区域时，各区人员到最近乘车点的距离最小，最短距离为 24338m当n=3时，可以求出当乘车点建在15号区域、21号区域和31号区域时，各区人员到最近乘车点的距离最小，最短距离为19660m4. 1问题1的模型4. 3. 1问题三的模型建立去17点坐车的点及其人数区域号34567891011121314151617181925262728合计人数423438291764392061476621708512354876169418932路程123078463075043053559041056070090044

13、0250140027047445038()24043010593suml = spointxnumber of teachers xpl,number of buses二suml/47 去22点坐车的点及其人数区域号12202122232443444546474849合计人数6567544912544669672018687276737路程93053048030003105504201602704606501803805620sum2=zpointxnumber of teachers xpl,number of buses二sum2/47去31点坐车的点及其人数区域号293031323334

14、353637383940414250合计人数297510867056652680904740574062833路程19024002304206303702605305704404005403702105400sum3=epointxnumber of teachers xpl,number of buses=sum3/47.sum3=spointxnumber of teachers xpl,坐车人数比例系数的确定p1=e (number 1 /number2) /5其屮numbcr2为每工作口被调查的人数，numbcrl为每工作口被调查者屮会在早上8点出发的人 数。调查五天，取平均值得出pl

15、。假设是0.4。由此得出的车辆数基木可以保证在人流最多的时候不 会出现教师滞留的情况因而影响了教学。假设p1满足正态分布n ( » , o，求出p >pl置信率为0. 95的区间上限为0. 4由于每一个乘车点总会有多余出来部分老师而不够盛满一辆车的情况，可以在三个乘车点共用一 辆专门负责共同剩余老师的车，在三个点之间转一圈，而口这辆车的速度很快，以保证坐不上车 的老师不会晚点。虽然大部分老师会选择在上课时间前的坐车人流高峰期走，但是还有一部分老师会在人流低峰期 出行，对于这部分占比例很小的可以安排一辆专用车，等待时间较长且循环负责这类老师4. 3. 2问题三的求解及结果表示用m

16、atlab求出正态分布的置信区间，因为缺乏社会调查的实践资料，所以设pl为0.4,求出的17, 22, 31点各需要安排9, 6, 7辆车，专门载剩余乘客的车1辆，专门 载乘车分散期的乘客的车2辆。44问题四的模型我们要解决的问题是：提高乘车人员的满意度；节省运行成本。即协调乘车人员想随到随走的期 望和运行商想车座满后再走的矛盾。分两个方面考虑：乘车人员、运行商。我们分两部分考虑：即集中发车时间段配车的优化、非集中发车时段配车的优化。我们可以通过对客观事实上的乘车人员的出行时刻来制定出既满足乘车人员需要有不太影响运行 商的利益的合理方案：首先：我们模拟一个大致的乘车人员岀行时刻表，以三个乘车点

17、为例，如表401时段集中发车时段非集中发车时段乘车点总数上午下午晚上其他每天的不去人 员占得比例100%30%30%10%20%10%q話79322802809318693q1=p227372212217414774q3=p38332502508316783变换成直角坐标，如下（图4-02）表4-01 乘车人员出行时刻表人数/个百分比a28030%a9310%7uv-p7:0012:305:30时间/1(a) 到第17号区域的时间/人数大致分布图心个百分比/22130%a a7410%丿 w寻7：0012：305：30时间/t(b) 到第22号区域的时间/人数大致分布图心个百征匕125030%

18、aa8310%丿17 va7:0012:305:30时间/1(c) 到第31号区域的时间/人数大致分布图图4-02到所选区域的时间/人数大致分布图以下，对图402作进一步的详述：图402 (a), (b), (c)也就是说，按照百分比/时间这三条曲线下的面积都为0.9,其屮在上午、中午、晚上的集中时间段乘车人员占70% （为三个峰值处曲线与时间轴所夹的面积），在非集中 时间段乘车的教师及工作人员占20% （除三个峰值附近处以外部分曲线与时间轴所夹的而积）。我们分两部分考虑：即集中发车时间段配车的优化、非集中发车时段配车的优化。一.集中发车时间段配车的方案图403集屮发车时间段配车方案在集中发车

19、时间段，因为教师及工作人员乘车的不确定性，在绝大多说境况下，都会有一小部分 人（往往小于47许多），为了使资源合理利用并冃考虑到运行商的利益，可以用一较小的辆在老 校区里的各乘车点之间进行短距离运输。二、非集中发车时间段配车的方案图4-04非集中发车时间段配车的方案由于非集中区需要乘车的教师及工作人员相对较少，所以不可能像公交汽车一样儿分钟或十儿分钟发一次车， 否则就极大的伤害了运行商的利益，但是也不能一长段时间不发车，否则就耽误了教师及工作人员的事情，所 以我们要设计一种方案，来协调这种矛盾，如图4()4所示：可以每个乘车点取侮隔(斤表示有多少个乘车 点，/表示非集屮发车时间段每隔/时间有一

20、辆车从老校区发往新校区)时间发一次车，这样既可以保证在 一个小的时间段里会有校车去新校区，也保证了运行商有一个相对较高的满座率。5、模型的推广通过对题目的解读我们不难发现这是一类规划问题。仔细分析我们建立的模型不难发现：这个模型不仅仅适用于出版社的资源配置问题，它对规划类问题的求解都可以起到指导作用。规划问题是运筹学的一个重要分支。它在解决工业生产组织、经济计划、组织管理人机系统 中，都发挥着重要的作用。例如超市、医院、水源选址问题。本文模型的建立是为了解决一定量的资源分配给多部门的问题，若a部门分到的资源多，其 余部门分的资源就会相对的减少。通过资源配置最优化为杠杆平衡它们之间的分配关系。决

21、策者 要通过概念抽彖、关系分析可将各类影响因子放入规划模型中，可以通过相关的计算机软件得到 兼顾全局的最优解。木题的求解是一个典型的规划问题，我们模型的使用范围非常广泛，涉及到投资时，有限的 资金如何分配到各种投资方式上；工厂选址时，要兼顾距离原料区和服务区的路程这一类问 题均能得到较好的解决。规划模型在工业、商业、交通运输、工程技术、行政管理等领域有着广 泛的应用。6、模型优缺点评价优点1、具有一定的原创性；2、建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用 性和推广性；3、模型的计算采用专业的数学软件，可信度较高；4、对附件屮的众多表格进行了处理，找出了

22、许多变量z间的潜在关系；5、对模型中涉及到的众多影响因素进行了量化分析，使得论文有说服力。缺点1、模型的基本假设条件有点简单；2、顾客满意度调查的权重系数人为确定缺少理论依据，缺少实际调查；3、没有很好地把握论文的重心，让人感觉论文有点散。4、由于是第一次参赛，模型建立不够成熟和专业7 参考文献:赵静,但琦.数学建模与数学实验（第二版）.北京:高等教育出版社,2000罗建军，杨 琦，精讲多练matlab.西安：西安交通大学出版社，2002附录附录一 floyd函数在matlab里的程序 %floyd.mfunction d,p=floyd(a) n=size(a,l); d=a;for k=l:nfor i=l:nforj=l:nif d(i,k)+d(k,