校车安排问题数学建模

1、题目：校车安排问题摘要本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，建立了校车安排方案的优化模型。从乘车点的距离最小，满意度最大又可节省运行成本等方面考虑，依据题目中所给条件分别建模求解。在问题解决过程中使用了Warshall-Floyd算法，分析、建模、求解过程中利用MATLAB编写相应程序并对数据进行分析处理，最终得出结论如下：问题1：仅考虑到每个区按距离车站的远近选择车站n=2时，乘车点：18 、31 距离：24492n=3时，乘车点：15 、21 、31 距离：19660问题2：综合考虑距离及教师总体满意度n=2时，乘车点：19 、32 满意度：77.77%n=3时，乘车点

2、：15 、21 、32 满意度：82.60%问题3：为使教师及工作人员尽量满意，至少需要安排54辆校车区15：安排17辆校车区21：安排19辆校车区32：安排18辆校车问题4：综合考虑距离模型，满意度模型，运营成本以及现实中的各种因素，给出校车安排的一些建议：在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题，在条件允许的范围内尽量增加乘车点以提高总体满意度。关键词：Warshall-Floyd算法 总体满意度 距离矩阵 MATLAB1、 问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何

3、有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。有如下问题待设计解决：假设老校区的教师和工作人员分布在50个区，各区的距离见表1。各区人员分布见表2。（1）问题1：如要建立n个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪n个点。建立一般模型，并给出n=2,3时的结果。 （2）问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n个点。建立一般模型，并给出n=2,3时的结果。 （3）问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。（4）问题4；关

4、于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2、 模型的假设及符号分析2.1 模型的假设 （1）50个区域看做50个点，附录A中标注距离的点间可以直接连通，而未标注的点则不能，必需通过其他点间接到达。（2）假设所有乘车点设立在各小区（点）上，乘车站点不设立在路上。（3）假设教师和工作人员的满意度只与距离有关，而忽略其他因素对其满意度的影响。（4）校车只在各个点上载人，行驶途中不载人。（5）假设所有人员均乘车。（6）假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。2.2 符号说明A：各点间距离的邻接矩阵；B：各点间的最短距离矩阵；dij：顶点

5、i到顶点j的最短距离；ij：图中i点到j点最短路径的权；ni：图中i点的权，表示i点（即i区）的人数；Dv1，v2，v3，vn：各个点到乘车点的总距离；Dmin：最短总距离;:乘客个体的满意度；：所有乘客的总体满意度；d：某点走到乘车点的距离；D：任意两点最短距离的最大值；R：教师及工作人员走到乘车点的平均距离。3、 模型的建立与求解3.1 计算各区（点）之间的最短路3.1.1 数据分析及处理用附录A中的各区之间距离建立对应各点距离的邻接矩阵A，即A=a11a12a21a150a250a501a502a5050其中aij表示点i到点j的距离，当aij=inf ，表示点i和点j不直接相通。3.1

6、.2 用Warshall-Floyd算法计算任意两点间的最短路设i为图G中的顶点。令dij是顶点i到顶点j的最短距离，ij是顶点i到顶点j的权。对于任何一个顶点，顶点i到顶点j的最短路经过顶点k或者不经过顶点k。比较dij与dik+dkj的值。若dij>dik+dkj，则令dij=dik+dkj，保持dij是当前搜索的顶点i 到顶点j的最短距离。重复这一过程，最后当搜索完所有顶点k时，dij就是顶点i到顶点j的最短距离。这一算法的具体实现由MATLAB编程实现，具体程序见附录D。将邻接矩阵A作为Warshall-Floyd算法的输入矩阵，程序输出各点间的最短距离矩阵B（结果见附录B）以及

7、取最短距离时部分点间的走法（结果见附录C）。3.2 建立n个乘车点使各区人员到最近乘车点的距离最小的数学模型3.2.1 模型的建立ij为图中i点到j点最短路径的权，表示从i点到j点的最短距离；ni为图中i点的权，表示i点（即i区）的人数，由于不考虑人数对乘车点的影响，取ni=1，i，j（1,50）。问题1的模型为ni=1时的特殊情况：Min f = i=150niij=i=150ij3.2.2 模型的求解任取n个互异点v1，v2，v3，vn为乘车点，则从各点到乘车点的总路程为：Dv1，v2，v3，vn=i=150min(iv1,iv2,ivn)则取50个点的组合C50n做v1，v2，v3，vn

8、，分别计算Dv1，v2，v3，vn，取得使Dv1，v2，v3，vn取最小值的v1，v2，v3，vn点即为所求乘车点。即：Dmin=min（Dv1，v2，v3，vn）其中v1，v2，v3，vn1,2,50, 且v1，v2，v3，vn互不相等取n=2,3，计算结果，算法的MATLAB实现减附录D .由程序计算得：n=2时，求得乘车点应在区域18和31，且Dmin=24492n=3时，求得乘车点应在区域15、21和31，且Dmin=196603.3 考虑每个区的乘车人数建立n个乘车点，使教师和工作人员满意度最大3.3.1 模型的建立ij为图中i点到j点最短路径的权，表示从i点到j点的最短距离；ni为

9、图中i点的权，表示i点（即i区）的人数，取ni=1，i，j（1,50）。则Min f =i=150niij可以想象，去乘车点的距离越大越不满意，即满意度随距离的增加而降低，假设为线性关系，当所有人走的总距离最短时满意度最大。定义为乘客个体满意度，依假设有：=1 - dD其中d为某点走到乘车点的距离，D为任意两点最短距离的最大值。定义为所有乘客的总体满意度，有：=1 - mdMD其中m为某点的人数，M为所有教师人数。定义R为教师及工作人员走到乘车点的平均距离，即：R=mdM3.3.2 模型的求解任取n个点v1，v2，v3，vn为乘车点，所有人到乘车点的总路程为：Dv1，v2，v3，vn=i=15

10、0min（ni*iv1,ni*iv2,ni*ivn)则取50个点的组合C50n做v1，v2，v3，vn，分别计算Dv1，v2，v3，vn，取得使Dv1，v2，v3，vn取最小值的v1，v2，v3，vn点即为所求乘车点。即：Dmin=min（Dv1，v2，v3，vn）其中v1，v2，v3，vn1,2,50, 且v1，v2，v3，vn互不相等取n=2,3，计算结果，算法的MATLAB实现减附录D .由程序计算得：n=2时，求得乘车点应取区域19和32，总体满意度=77.77%；距离乘车点的平均距离R=496.8n=3时，求得乘车点应取区域15、21和32，总体满意度=82.60%；距离乘车点的平均

11、距离R=388.83.4 建立3个乘车点的数学模型3.4.1 模型的建立此问题以车辆数和总体满意度为双目标函数；任取3个点v1，v2，v3为乘车点，所有人到乘车点的总路程为：Dv1，v2，v3=i=150min（ni*iv1,ni*iv2,ni*ivn)分别找出此时到vi点距离最近的ki个点，计算这ki个点的总人数si。（i=1,2,3）则取50个点的组合C503做v1，v2，v3，分别计算Dv1，v2，v3，取得使Dv1，v2，v3取最小值的v1，v2，v3点即为所求乘车点。即：Dmin=min（Dv1，v2，v3）从而车辆数 K=i=13si47 ( 表示向上取整)3.4.2 模型求解以上

12、算法通过MATLAB编程实现。(具体程序见附录D)将最短距离矩阵B和各区人数座位输入数据输入程序，计算得到结果：乘车点应设在区域15、21、32（由模型3.3可知）；其中：15区应安排17辆车，到15区乘车的区域有：5 、 6 、 7 、 8 、 9 、 10 、 11 、 12 、 13 、 14 、 15 、 16 、 17 、 18 、 25 、 26 、 2721区应安排19辆车，到21区乘车的区域有：1 、 2 、 3 、 4 、 19 、 20 、 21 、 22 、 23 、 24 、 28 、 43 、 44 、 45 、 46 、 47 、 48 、49 32区应安排18辆车

13、，到32区乘车的区域有：29 、 30 、 31 、 32 、 33 、 34 、 35 、 36 、 37 、 38 、 39 、 40 、 41 、 42 、 50 3.5 建议1.从问题求解过程中，我们可以看出固定的校车出发点使得校车利用率降低。因此我们建议空闲的校车到其他的乘车点去运送乘车人员。从而使需要的校车数目减少一至两辆。2.适当增加乘车点的数量，使乘车人员的不满意度进一步减小。3.在一天内的不同时间点应安排不同辆数的校车。上下课时间为乘车高峰期，应多安排车辆，其它时间应少安排。这样可有效节省运行成本。4.尽量将人员的上下班时间统一在几个固定的时间段，在这几个时间段安排足够的车辆

14、，保证每名员工都能及时乘坐校车，也可增加校车的运营效率。5.在非高峰期可适当停止部分站点的使用。4.模型的分析与评价本文就高校校车安排问题建立网络模型，进而转化为图论中最短路问题，具有一定的科学性。但模型是建立在一系列假设的基础上，所得结果与实际问题会存在一定偏差，需要通过与实际情况比较而进行修正。模型优点：1、本模型运用相关数学及计算机知识，成功解决了如何安排有限个站点使老师和工作人员满意度最高的问题。在假设条件下，该模型精确地给出了站点位置。2、通过MATLAB编程我们可以得到任意两个区之间的最短路径，并且可以得了任意两个区最短路径具体的路线。模型缺点：1、本模型在理想条件下，通过编程可得

15、出精确结果，但程序运行较为复杂，当设置的乘车点较多时，程序运算量非常大。2、乘客个体满意度公式过于理想，忽略了很多其他因素。5、模型的推广：本模型可推广到公共站点设置、服务中心位置选择、垃圾运输等最短路径及选址问题。本模型利用计算机程序实现了对结果的精确定位，可应用于各种与此类型相关的场合。6、参考文献【1】王海英 黄强 等，图论算法及其MATLAB实现，北京航空航天大学出版社，2010年2月第1版【2】龚劬，图论与网络最优化算法，重庆大学出版社，2009年10月第1版【3】姜启源 谢金星 叶俊，数学模型，高等教育出版社，2003年8月【4】李得宜 李明，数学建模，科学出版社，2009年5月7

16、、附录附录A：各区距离表区域号区域号距离区域号区域号距离区域号区域号距离124001517250293119013450161714030312402430016181303042130221230172724030432102471401819204313223034600182518031362604521019201403150210419310192417532331905623020211803235140572002024190323624067320212230033342106834021232703537160781702147350363918071816022441603

17、640190892002245270373813581528522481803839130910180232424039413101011150232921040411401015160233029040501901112140234415042502001114130242517043442601213200242813043452101334400262714045462401415190263432046482801426190272819048492001516170282926012345678948495010400450700910114011101280148011101310

18、151024000850300510740710880108071091011103450850060081010401010118013801560176018754700300600021044041058078010101210127559105108102100230200370570122014201485611407401040440230032034054014501650162071110710101041020032001703701164136413008128088011805803703401700200133415341470914801080138078057054

19、0370200015341734164048111071015601010122014501164133415340200110049131091017601210142016501364153417342000130050151011101875127514851620130014701640110013000附录B：点间最短距离矩阵附录C:各点间取最短距离的走法（仅列出以1为出发点的路径）目的地最短路径21231341245124561245671245781245789124578910122120191816151011122120191816151011121221201918161

20、510111213122120191816151011121314122120191816151415122120191816151612212019181617122120191816171812212019181912212019201221202112212212212223122123241221202425122120242526122120242827262712212024282728122120242829122123293012212330311221232931321221232931323312212329313233341221202428272634351221232

21、9313235361221232931363712212329313235373812212329313639383912212329313639401221232931364041122123293136404142122123304243122123444344122123444512212245461221224846471247481221224849122122484950122123293150附录D：MATLAB程序/Warshall-Floyd算法/%给邻接矩阵赋值，邻接矩阵记为w（i，j）for i=1:50 for j=1:50 if i=j w(i,j)=0; else

22、w(i,j)=inf; end endendw(1,2)=400; w(1,3)=450; w(2,4)=300; w(2,21)=230;w(2,47)=140; w(3,4)=600; w(4,5)=210; w(4,19)=310;w(5,6)=230; w(5,7)=200; w(6,7)=320; w(6,8)=340;w(7,8)=170; w(7,18)=160; w(8,9)=200; w(8,15)=285;w(9,10)=180; w(10,11)=150;w(10,15)=160;w(11,12)=140;w(11,14)=130;w(12,13)=200;w(13,34

23、)=400;w(14,15)=190;w(14,26)=190;w(15,16)=170;w(15,17)=250;w(16,17)=140;w(16,18)=130;w(17,27)=240;w(18,19)=204;w(18,25)=180;w(19,20)=140;w(19,24)=175;w(20,21)=180;w(20,24)=190;w(21,22)=300;w(21,23)=270;w(21,47)=350;w(22,44)=160;w(22,45)=270;w(22,48)=180;w(23,24)=240;w(23,29)=210;w(23,30)=290;w(23,44)

24、=150;w(24,28)=130;w(24,25)=170;w(26,27)=140;w(26,34)=320;w(27,28)=190;w(28,29)=260;w(29,31)=190;w(30,31)=240;w(30,42)=130;w(30,43)=210;w(31,32)=230;w(31,36)=260;w(31,50)=210;w(32,33)=190;w(32,35)=140;w(32,36)=240;w(35,37)=160;w(36,39)=180;w(36,40)=190;w(37,38)=135;w(38,39)=130;w(39,41)=310;w(40,41)=

25、140;w(40,50)=190;w(42,50)=200;w(43,44)=260;w(43,45)=210;w(33,34)=210;w(45,46)=240;w(46,48)=280;w(48,49)=200;for i=1:50 for j=1:50 if w(i,j)=0 w(j,i)=w(i,j); end endend%以k1=1，k2=25为例k1=1;k2=25;%初始化n=length(w);U=w;m=1;%利用求最短路的warshallfloyd算法的思想，求最短距离矩阵while m<=n for i=1:n for j=1:n if U(i,j)>U(i

26、,m)+U(m,j) U(i,j)=U(i,m)+U(m,j); end end end m=m+1;endu=U(k1,k2); %最短距离%求任意给定两个点k1和k2间的最短路所包含的顶点p1=zeros(1,n);k=1;p1(k)=k2;v=ones(1,n)*inf;kk=k2;while kk=k1 for i=1:n v(1,i)=U(k1,kk)-w(i,kk); if v(1,i)=U(k1,i) p1(k+1)=i; kk=i; k=k+1; end endendk=1;wrow=find(p1=0);for j=length(wrow):(-1):1 p(k)=p1(wr

27、ow(j); k=k+1;end /Warshall-Floyd算法/3.2.2中n=2时/%以最短距离矩阵作为矩阵d的输入for i=1:49 for j=i+1:50 D(i,j)=0; endendfor i=1:49 for j=i+1:50 for k=1:50 if d(k,i)>d(k,j) dmin=d(k,j); else dmin=d(k,i); end D(i,j)=D(i,j)+dmin; end endenddistance=D(1,2);station1=1;station2=2;for i=1:49 for j=i+1:50 if D(i,j)<dis

28、tance distance=D(i,j); station1=i; station2=j; end endend/3.2.2中n=2时/3.2.2中n=3时/%以最短距离矩阵作为矩阵d的输入for i=1:48 for j=i+1:49 for k=j+1:50 D(i,j,k)=0; end endendfor i=1:48 for j=i+1:49 for k=j+1:50 for l=1:50 if d(l,i)<=d(l,j)&&d(l,i)<=d(l,k) dmin=d(l,i); else if d(l,j)<=d(l,k) dmin=d(l,j

29、); else dmin=d(l,k); end end D(i,j,k)=D(i,j,k)+dmin; end end endenddistance=D(1,2,3);station1=1;station2=2;station3=3;for i=1:48 for j=i+1:49 for k=j+1:50 if D(i,j,k)<distance distance=D(i,j,k); station1=i; station2=j; station3=k; end end endend/3.2.2中n=3时/3.3.2中n=2时/%以最短距离矩阵作为矩阵d的输入for i=1:49 fo

30、r j=i+1:50 D(i,j)=0; endendn=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=1:49 for j=i+1:50 for k=1:50 if d(k,i)*n(k)>d(k,j)*n(k); dmin=d(k,j)*n(k); else dmin=d(k,i)*n(k); end D(i,j)=D(

31、i,j)+dmin; end endenddistance=D(1,2);station1=1;station2=2;for i=1:49 for j=i+1:50 if D(i,j)<distance distance=D(i,j); station1=i; station2=j; end endendmax=d(1,2); %max为任意两点间的最短距离的最大值for i=1:49 for j=i+1:50 if d(i,j)>max max=d(i,j); end endendM=0; %M为所有教师人数for i=1:50 M=M+n(i);endmd=0;for i=1:

32、50 if d(i,station1)<=d(i,station2) md=md+n(i)*d(i,station1); else md=md+n(i)*d(i,station2); endendmanyidu=1-md/(M*max);R=md/M;/3.3.2中n=2时/3.3.2中n=3时/%以最短距离矩阵作为矩阵d的输入for i=1:48 for j=i+1:49 for k=j+1:50 D(i,j,k)=0; end endendn=65 67 42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 48 54 49 12 54 46

33、 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=1:48 for j=i+1:49 for k=j+1:50 for l=1:50 if d(l,i)*n(l)<=d(l,j)*n(l)&&d(l,i)*n(l)<=d(l,k)*n(l) dmin=d(l,i)*n(l); else if d(l,j)*n(l)<=d(l,k)*n(l) dmin=d(l,j)*n(l); else dmin=d(l,k)*n(l); end end D(i,j,k)=D(i,j,k)+dmin; end end endenddistance=D(1,2,3);station1=1;station2=2;station3=3;fo