数学建模竞赛论文-校车安排问题的论文.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： J1814 所属学校（请填写完整的全名）： 西安财经学院 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 5 月 27 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：校车安排问题摘要本文研究的事校车安排问题。首先将50个区抽象成一张无向赋权图G(V,E),采用图论中的经典算法Floyd算法求出任意两个区之间的最短距离。基于G(V,E)，我们对其余问题展开分析和研究。对于站点分布问题，由于最短距离已经得出，只需按需选择出距离最短的n个区最为站点。站点的选出可根据到所有点距离的总和这个相对值来确定。对于满意度问题，我们综合考虑距离和各站点人数的因素抽象出一个求满意度的函数，分别求出这两个因素下的满意度，求和，得出最能是大家满意的n个站点。对于车辆分配的问题，我们把车辆的分配比例转换成站点乘车人数的比例。依据教职工们以距离最短为原则选择站点乘车。由于每辆车不得多于47人，我们可以求出最少共需要54辆车，所以最终得到的三个站点车辆数的总和应该最但限度的接近54。最终我们得出是那个站点安排的车辆数应该为16区安排18辆，21区安排20辆，32区安排17辆。总共55辆车。关键词： Floyd算法 满意度 无向带权图一、问题重述问题1：如要建立个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。问题4；关于校车安排问题，怎样既可以提高乘车人员的满意度，又可节省运行成本。二、问题分析 校车安排问题中，乘车人员主要考虑的因素是距离，而对于校车来说就是最少车辆数安排最多乘员的原则安排，所以可对该问题作出如下分析：问题一：该文主要考虑距离因素，本着距离最短的原则则将该问题简化成求最短路径的问题。问题二：要使教职工满意则须到乘车点的距离最短，要使大家都满意则需要考虑各个区的乘车人数。综合考虑这两者问题，求出满意度，取满意度最大的前n位。所以该问可简化为求满意度的一个抽象函数的问题。问题三：该文中车辆数的安排所考虑的因素是乘车人数，所以将车辆在3个站点的安排比例就转化成各站点乘车人数的比例。根据人数，本着“不空车，不超载”的原则求出一个车辆数使得它尽可能的接近最小车辆数。三、模型假设1假设未给出距离的两个区可以通过其他区间接到达。2每位教师及工作人员均选择最短路径乘车。3乘车点均建在各区内，不考虑各区内的距离。4. 教师及工作人员到各站点乘车的满意度与到该站点的距离有关系，距离近则满意度高，距离远则满意度低。5. 假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。6、假设车辆不超载。7、假设所有人员均乘车。四、符号说明符号表示意义符号i表示意义Vi第i个区域 i=1,2,3,.50dij第i区与第j区的最短距离 i=1,2,3,.50 j=1,2,3,.50D任意两区的最短距离矩阵rij含义是从Vi到Vj的最短路要经过点号为rij的点R任意两区最短距离路径矩阵St表示t区教师和工作人员到最近乘车点的距离Pt表示t区的乘车人数，Bt表示nt乘车点应安排的车辆数。t=1,2,3Wt表示t区人数Pt乘以距离St n第i个区域 i=1,2,3,.50ni第i个区域 i=1,2,3,.50Vi第i个区域 i=1,2,3,.50dij第i区与第j区的最短距离 i=1,2,3,.50 j=1,2,3,.50D任意两区的最短距离矩阵rij含义是从Vi到Vj的最短路要经过点号为rij的点五、模型建立与求解第一步:用Floyd算法求出距离矩阵D=（dij）vv .1. 算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D(1)、 D(2)、 、D()，使最后得到的矩阵D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径2.算法原理（1）求距离矩阵的方法把带权邻接矩阵W作为距离矩阵的初值，即D(0)=根据题目所给各区距离表列出D(0)=5050距离矩阵 D(1)= ，其中是从Vi到Vj的只允许以V1作为中间点的路径中最短路的长度. D(2)= ，其中是从Vi到Vj的只允许以V1 、 V2作为中间点的路径中最短路的长度 D(V)=，其中是从Vi到Vj的只允许以V1、V2、VV作为中间点的路径中最短路的长度即是从Vi到Vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵(2)求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R，R=,rij的含义是Vi到Vj的最短路要经过点号为rij的点, 每求得一个D(k)时，按下列方式产生相应的新的R(k)即当Vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 D(v)时求得R(v),可由R(v) 来查找任何点对之间最短路的路径(3)查找最短路径的方法若，则点p1是点i到点j的最短路的中间点. 然后用同样的方法再分头查找若：（） 向点i追朔得：,（） 向点j追朔得：,则由点i到j的最短路的路径为：3.算法步骤Floyd算法：求任意两点间的最短路D(i,j)：i到j的距离R(i,j)：i到j之间的插入点输入: 带权邻接矩阵w(i,j)（） 赋初值：对所有i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新d(i,j), r(i,j)对所有i,j，若d(i,k)+d(k,j)d(i,j)，则d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若k=，停止否则kk+1，转（）用Matlab编程得D(50)=（dij）5050，其中dij即为两点最短距离，同时可求出路径矩阵D(50)=（dij）5050矩阵如下：123456789484950104004507009101140111012801480111013101510240008503005107407108801080710910111034508500600810104010101180138015601760187547003006000210440410580780101012101275591051081021002302003705701220142014856114074010404402300320340540145016501620711107101010410200320017037011641364130081280880118058037034017002001334153414709148010801380780570540370200015341734164048111071015601010122014501164133415340200110049131091017601210142016501364153417342000130050151011101875127514851620130014701640110013000第二步：设置n个乘车点时的取点情况算法思路：我们假设教师和工作人员去乘车时都去最近的乘车点。这样，他们走的路程越短，就越满意。在我们设置好乘车点后，由于不考虑每个区的乘车人数，每个区人员到最近乘车点乘车，乘车所走最短距离相加所得的总和最小时，教师和工作人员乘车的总体满意度就最高。步骤如下：dit表示t区到i区的最短距离,当N=2时，以n1, n2区为乘车点时，St表示t区教师和工作人员到最近乘车点的距离，即mindn1t , dn2t。S总dn1t,dn2t,因为有50个区，这样就有种选择乘车点位置的方法，S总共有个，用C语言编程选出最小值的S总，此时S总值对应的n1, n2值即为乘车点应选择的区。当N=3时，以n1,n2,n3区为乘车点时，St表示t区教师和工作人员到最近乘车点的距离，即mindn1t , dn2t ,dn3t。S总dn1t,dn2t,dn3t,因为有50个区，这样就有种选择乘车点位置的方法，S总共有个，用C语言编程选出最小值的S总，此时S总值对应的n1, n2,n3值即为乘车点应选择的区。当N=50时，以n1, n2, n3 nn区为乘车点时，St表示t区教师和工作人员到最近乘车点的距离，即mindn1t , d n2t，dn3tdnnt。S总=(dit,djtdpt),因为有50个区，这样就有种选择乘车点位置的方法，S总共有个，用C语言编程选出最小值的S总，此时S总值对应的n1, n2,n3 nn值即为乘车点应选择的区。问题二模型的建立及求解算法思路：我们假设教师和工作人员去乘车时都去最近的乘车点。这样，他们走的路程越短，满意度就越高。在我们设置好乘车点后，考虑到每个区的人数不同，小区内人数越多，满意度就越高。这样，影响满意度的因素可认为是两个：1.人到达乘车点的距离；2.小区内人数。且这两个因素对满意度的影响各占50%。步骤如下：Pi表示i区的人数；Lij 表示i区与j区的最短路径值。当N=3时，假设乘车站点为i,用Lij表示每一个小区教师和工作人员到i乘车点的距离，即Si=Lij 假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量，即 Pi。 。则满意度I可用公式I=(Lij /Si)*50%+(Pi/Pi)*50%得到。用软件计算I得值最小的2个i点应设为乘车站点。当N=3时，假设乘车站点为i,用Wi表示每一个小区教师和工作人员到i乘车点的距离，即Si=Lij。假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量，即Pi。则满意度I可用公式I=(Lij /Si)*50%+(Pi/Pi)*50%得到。用软件计算I得值最小的3个i点应设为乘车站点。当N=n时(n应在小于50的范围内考虑，否则无意义。),假设乘车站点为i,用Wi表示每一个小区教师和工作人员到i乘车点的距离，即Si=Lij。假设乘车站点为i,用Pi表示每一个小区教师和工作人员数量，即Pi。则满意度I可用公式I=(Lij /Si)*50%+(Pi/Pi)*50%得到。用软件计算I得值最小的n个i点应设为乘车站点。问题三模型的建立及求解算法思路：假设所有工作人员均乘车。由问题二已确定了乘车点所在的区域，为n1, n2, n3区，其他任意区的教师及工作人员选择去某个乘车点乘车的依据是到乘车点的路径最小。现在只需用C语言编程计算出去n1, n2, n3区乘车点的乘车人数，然后再计算出所需车辆数。步骤如下：Bt表示nt乘车点应安排的车辆数。t=1,2,3三个站点为n1=16，n2=21, n3=32，设到n1站点乘车有p1人，n2站点乘车有p2人，n3站点乘车有p3人，每辆车最多载47人。则总共需要车辆数：B=B1+B2+B3设住在1区域到n1乘车的人数为a1，住在2区域到n1乘车的人数为a2住在50区域到n1乘车的人数为a50住在1区域到n2乘车的人数为b2，住在2区域到n2乘车的人数为b2住在50区域到n2乘车的人数为b50住在1区域到n2乘车的人数为c2，住在2区域到n3乘车的人数为c2住在50区域到n3乘车的人数为c50则p1=a1+a2+a3+a50P2=b1+b2+b3+b50P3=c1+c2+c3+c50问题三结果： p1=824 ,p2=923 ,p3=755 .故 B1=18,B2=20 ,B3=17 .即B=B1+B2+B3=55故学校至少需要安排55辆车，16区安排18辆，21区安排20辆，32区安排17辆。问题四1、将区域划成块，每一块有专车在专门点接送。各位教职工去自己所属的乘车点乘车。2、在有些人员较少得点，可以没有站点负责，由有空位的车辆环路接送。3、有的车辆有不满客的情况，所以可以换成小型客车。六、模型评价本文的主要优点：1、本文根据问题要求利用优化的思想，一步一步地讨论了模型的建立情况，使所建立的模型最大限度的接近实际问题。2、本文建立的模型具有一般性，其他的学校或单位均可采用，可以减少学校或其他单位的经费开销。本文的主要缺点： 1、数据导入MATALAB繁琐，要浪费大量时间，且容易出错。2、对现实中的一些特殊情况尽情了简化处理，与现实稍有偏颇。3、 本文中我们计算任意两各路口间的最短距离时，采用了Floyd算法，而Floyd算法的时间复杂度比较高，争对本文中的大批量数据处理时计算时间比较长。七、模型推广本模型可推广到公共站点设置、服务中心位置选择、垃圾运输等最短路径、建筑选址问题。本模型利用计算机程序实现了对结果的精确定位，还可应用于各种与此类型相关的场合。参考文献1 耿国华，数据结构C语言描述（第二版）西安电子科技大学出版社 2008。2 MATLAB基础教程孙祥，清华大学出版社 2005。3 张志涌，精通MATLAB 6.5版M，北京：北京航空航天大学出版社，2005。4 宋兆基、徐流美，MATLAB6.5在科学计算中的应用M，北京：清华大学出版社，2005。5 方世昌，离散数学（第三版）西安电子科技大学出版社 2008.附录A 表1 各区距离表区域号区域号距离(m)1240013450243002212302471403460045210419310562305720067320683407817071816089200815285910180101115010151601112140111413012132001334400141519014261901516170151725016171401618130172724018192041825180192014019241752021180202419021223002123270214735022441602245270224818023242402329210233029023441502425170242813026271402634320272819028292602931190303124030421303043210313223031362603150210323319032351403236240333421035371603639180364019037381353839130394131040411404050190425020043442604345210454624046482804849200表2 各区人员分布区域人数区域人数16526162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484467205445202149461822124768235448722446497625765062附录B问题一的程序代码（任意两个区之间的最短路径D矩阵，路线R矩阵）functionD,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendRfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D REnd问题一的程序代码（N=2时，乘车点的区域）#include int min(int x,int y) int z; z=xy?x:y; return(z);/*比较两个数的值，并返回较小的值*/void main() int i,j,t,s=0; int u5050=0; int a5050=此为D矩阵每个值按顺序排列/*以任意两个区最短路径的值定义一个二维数组*/for(i=0;i50;i+) for(j=i+1;j50;j+) for(t=0;t50;t+) s=s+min(ait,ajt); /*当以i，j区作为乘车点时，其他每个区到最近乘车点的最短路径相加*/ uij=s;/*其他每个区到最近乘车点的最短路径相加的和赋值给以i,j为下标二维的数组元素*/ s=0; int n1=0,n2=0,m=10000000000; for(i=0;i50;i+) for(j=0;j50;j+) if(uij!=0&uijm) m=uij; n1=i+1; n2=j+1; /*选出其他每个区到最近乘车点的最短路径相加的和为最小时的乘车点*/ printf(nn当建立两个乘车点时，乘车点应选择的区域为：nn); printf(%d区和%d区nn各区人员到最近乘车点的最小距离总和为:n%dnnnn,n1,n2,m);printf(请按从小到大顺序输入任意两个区,并以这两个区作为乘车点：n); scanf(%d%d,&i,&j); printf(则以%d区和%d区作为乘车点时，各区人员到最近乘车点的最小距离总和为:n,i,j); printf(%dnnn,ui-1j-1);/*可以以其他任意两个区作为乘车点时，与最优解比较各区人员到最近乘车点的最小距离总和*/问题一的程序代码（N=3时，乘车点的区域）#include int min(int x,int y,int w)int z; z=(xy?x:y)w?(xy?x:y):w; return(z);/*比较三个数的值，并返回较小的值*/void main() int i,j,k,t,s=0; int u505050=0; int a5050= 此为D矩阵每个值按顺序排列/*以任意两个区最短路径的值定义一个二维数组*/for(i=0;i50;i+) for(j=i+1;j50;j+) for(k=j+1;k50;k+) for(t=0;t50;t+) s=s+min(ait,ajt,akt); /*当以i，j, k区作为乘车点时，其他每个区到最近乘车点的最短路径相加*/ uijk=s;/*其他每个区到最近乘车点的最短路径相加的和，赋值给以i,j,k为下标的三维数组元素*/ s=0; int n1=0,n2=0,n3=0,m=10000000000; for(i=0;i50;i+) for(j=0;j50;j+) for(k=0;k50;k+) if(uijk!=0&uijkm) m=uijk; n1=i+1; n2=j+1;n3=k+1; /*选出其他每个区到最近乘车点的最短路径相加的总路程为最小时的乘车点*/ printf(nn当建立三个乘车点时，乘车点应选择的区域为：nn); printf(%d区和%d区%d区nn各区人员到最近乘车点的最小距离总和为:%dnnnn,n1,n2,n3,m);printf(请按从小到大顺序输入任意三个区,并以这三个区作为乘车点：n); scanf(%d%d%d,&i,&j,&k); printf(则以%d区和%d区和%d区作为乘车点时，各区人员到最近乘车点的最小距离总和为:n,i,j,k); printf(%dnnn,ui-1j-1k-1);/*可以以其他任意三个区作为乘车点时，与最优解比较各区人员到最近乘车点的最小距离总和*/问题二的程序代码（N=2时，乘车点的区域）#include int min(int x,int y)int z; z=xy?x:y; return(z);/*比较两个数的值，并返回较小的值*/void main() int i,j,t,s=0; int u5050=0; int v5050=0; int a5050= 此为D矩阵每个值按顺序排列/*以任意两个区最短路径的值（一共1225条）定义一个二维数组*/ int p50= 65,67,42,34,38,29,17,64,39,20,61,47,66,21,70,85,12,35,48,54,49,12,54,46,76, 16,94,18,29,75,10,86,70,56,65,26,80,90,47,40,57,40,69,67,20,18,68,72,76,62;/*以每个区的人数定义一个一维数组*/for(i=0;i50;i+) for(j=i+1;j50;j+) for(t=0;t50;t+) vit=ait*pt; vjt=ajt*pt; s= s+min(vit,vjt); /*当以i，j区作为乘车点时，其他每个区到最近乘车点的最短路径与该区人数相乘的值相加*/ uij=s;/*当以i，j区作为乘车点时，其他每个区到最近乘车点的最短路径与该区人数相乘的值相加的总和赋值给以i,j为下标二维的数组元素*/ s=0; int n1=0,n2=0,m=10000000000; for(i=0;i50;i+) for(j=0;j50;j+) if(uij!=0&uijm) m=uij; n1=i+1; n2=j+1; printf(nn当建立两个乘车点时，乘车点应选择的区域为：nn); printf(%d区和%d区nnW值为:%dnnnn,n1,n2,m);printf(请按从小到大顺序输入任意两个区,并以这两个区作为乘车点：n); scanf(%d%d,&i,&j); printf(则以%d区和%d区作为乘车点时，W值为:n,i,j); printf(%dnnn,ui-1j-1);/*可以以其他任意两个区作为乘车点时，与最优解比较W值*/问题二的程序代码（N=3时，乘车点的区域）#include int min(int x,int y,int w)int z; z=(xy?x:y)w?(xy?x:y):w; return(z);/*比较三个数的值，并返回较小的值*/void main() int i,j,t,k,s=0; int u505050=0; int v5050=0; int a5050= 此为D矩阵每个值按顺序排列/*以任意两个区最短路径的值（一共1225条）定义一个二维数组*/ int p50= 65,67,42,34,38,29,17,64,39,20,61,47,66,21,70,85,12,35,48,54,49,12,54,46,76, 16,94,18,29,75,10,86,70,56,65,26,80,90,47,40,57,40,69,67,20,18,68,72,76,62;/*以每个区的人数定义一个一维数组*/ for(i=0;i50;i+) for(j=i+1;j50;j+) for(k=j+1;k50;k+) for(t=0;t50;t+) vit=ait*pt; vjt=ajt*pt;vkt=akt*pt; s= s+min(vit,vjt,vkt);/*当以i，j, k区作为乘车点时，其他每个区到最近乘车点的最短路径与该区人数相乘的值相加*/ uijk=s;/*当以i，j，k区作为乘车点时，其他每个区到最近乘车点的最短路径与该区人数相乘的值相加的总和赋值给以i,j,k为下标三维的数组元素*/ s=0; i