校车安排问题

校车安排模型摘要本文讨论了在不同情况下如何合理安排校车让教师和工作人员最大满意的问题。在问题一中，把50个区看成50个点，我们先利用佛洛依德算法求出了任意两点间最短路距离矩阵，得到的一个50阶的矩阵，在此基础上，我们以各区域到各自最近乘车点的距离总和最小为目标设置N个乘车点，对50个区域进行遍历分析，总共需要进行对两点最短距离的查找，在n较小的情况下借助数学工具MATLAB可以较快找出各个区域到各自最近乘车点的最小距离和建立模型一，找出n个最优乘车点。在第一问的基础上并利用已给的一般模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。在问题二中，根据满意度与距离成负相关的关系，把各区人数（各区到各自最近乘车点的最小距离）求和作为评价满意度的指标，由分析可知取最小值时教师职工的满意度最大然后以所有区域人员满意度最大为目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为19点和32点，总满意度为0.78。当建立3个乘车点时的最优解为第15，21，32点，满意度为0.83关键词：Floyd算法满意度最短距离MATLAB一问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。假设老校区的教室和工作人员分布在50个区。问题一：建立个乘车点，使各区人员到乘车点的距离最小，建立模型，并分别建立两个和三个乘车点的校车安排方案。问题二：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两个和三个乘车点的校车安排方案。(假定车只在起始点载人)问题三：在教师和工作人员尽量满意的前提下，在50个区内找出最优的三个乘车点的位置，并根据各个乘车点的人数，（车辆最多载客47人）确定车辆个数。最后，跟据以上所得出的结论，在提高乘车人员的满意度，又可节省运行成本的前提下，对如何改进校车的安排方案提出意见。二问题分析校车的安排并让教师职工尽量满意是个很重要的现实的问题，这里首先采用算法求得任意两点之间最短距离，得到一个50阶的佛洛依德矩阵，在这个距震中可以方便的查找到任意两点之间的最短距离和路径，其次在50个区域中任意选取n个区域作为乘车点，找出每个区域所对应的最近乘车点，最后以50个区域到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立2个和3个乘车点时的校车安排问题进行求解。算法的时间复杂度O(n^3)优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。借助MATLAB可以较快实现。第二问要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的衡量指标（各区人数到各自最近乘车点的距离最小距离的最小和），并对每个区的人数进行归一化处理，然后以总满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。第三问要去建立3个乘车点，在尽量使教师和工作人员满意的前提下所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。第四问中我们结合第三问的结果对车辆的安排情况提出了建议。三模型假设1、假设每个人采取到最近点乘车原则2、假设汽车中途不再载人3、假设每辆车的型号一致4、假设每个乘车点的乘车人数固定不变，即不考虑意外的发生和教师职工的搬迁。5、假设各区之间路径由题目给出，并且任意一个区到另外一个区都应经过由题目表中给出的距离的对应点。无距离对应的区域视为两点间没有直通路径。6、乘车点应设置在50个区域。7、校车中途无意外发生，交通秩序畅通。四符号说明Z区域各自最近乘车点的距离最短距离之和三个乘车点时的总满意度三个乘车点的总车辆数区域号区域到最近乘车点的最小距离乘车点（）各区域人数到第个乘车点的子集合满意度第各乘车点的车辆数区域到区域的最短距离矩阵=（）=（）五模型建立与求解问题一要求：建立n个乘车点，使各区人员到乘车点的距离最小，建立模型，并求的时的结果。5.0.1采用算法求得50个区域的最短距离矩阵，结合表一，利用算法求的任意两点之间最短距离（程序见附录【1】）。算法如下：1、先根据题目数据为初始矩阵赋值，其中没有给出距离的赋给一大值，以便于更新。2、进行迭代计算。对任意两点，若存在，使，则更新。3、直到所有点的距离不再更新停止计算。则得到最短路距离矩阵，。建立模型一在最短路距离矩阵的基础上，再做如下分析：首先，在50个区域中任意选取n个区域作为乘车点∈其次，引入变量，表示k区域到最近乘车点的最小距离然后，求出50个区域到各自最近乘车点的最短距离之和，最后，建立模型一最佳乘车点是使得50个区域到各自最近乘车点的最短距离之和最小的点，基于此建立目标函数：其中∈为选出的最佳乘车点。依据模型一，利用软件(程序见附录【2】)求得结果如下：当=2时，选18区的32个：1234567891011121415161718192021222324252627284446474849选32的区域有18个:132930313233343536373839404142434550 当=3时： 选择的三个乘车点为15,21,32。满意度为0.83。选15点有17个: 56789101112131415161718252627选21点有18个: 12341920212223242843444546474849选32点有15个:293031323334353637383940414250问题二要求：考虑每个区的乘车人数，使工作人员和教师的满意度最大，建立模型，并求得时的结果。1第区人数权重为：50个区的总人数1.3建立模型二在模型一的基础上，建立最高满意度乘车点选择模型，目标函数：最大满意度其中：表示选出的最高满意度下的最佳乘车点。依据模型二，利用软件求得结果如下（程序见附录【3】）：当=2时:选择的两个乘车点为19,32。满意度为0.78选19的区域有32个:1234567891011121415161718192021222324252627284446474849选32的区域有18个:132930313233343536373839404142434550 当=3时： 选择的三个乘车点为15,21,32。满意度为0.83。选15点有17个: 56789101112131415161718252627选21点有18个: 12341920212223242843444546474849选32点有15个:29303132333435363738394041425问题三：根据题目要求使得教师职工尽可能的满意同时乘车站点固定的情况下：即令上面的n=3；对问题二的分析求解，已知道当选择三个乘车点时，选择15,21,32为最近乘车点。于是： 区号：56789101112131415161718252627对应最近乘车点：15 区号：12341920212223242843444546474849对应最近乘车点：21 区号：293031323334353637383940414250对应最近乘车点：32 由以上可知，选择15，21，32作为乘车点时的车辆数为： 在15区乘车人数790，校车=17辆 在21区乘车人数879，校车=19辆 在32区乘车人数833，校车=18辆 共17+19+18=54辆而50个区的总人数为不管怎样至少需要安排的校车总数为：/47（向上取整）=54（辆）恰好是已经找到的三个乘车点需要安排的校车总数同时满足了使教师职工尽可能的满意问题四：在前三问的分析与解答中，均忽略了一定的实际决策因素，如：第一问中忽略了各区的人数和校车的容量，认为各区的人数相等或者均为单位1，并且校车的数量及可搭载量为任意；第二问中虽然考虑了人数，但仍然未考虑校车因素；第三问只照顾了教师和工作人的满意度：在保证所有人所走路程之和最小的前提下，各乘车点的小车可以任意增加，是第二问的具体化。而实际情况下，我们的目的是使乘车人员的满意度最大，即所走路程之和最小，校车的数量或者校车所花的费用尽量少，此外，站点的建立需要费用，故数量应少，而且必然会对周围的环境产生影响，等等，实际处理时往往要综合考虑。下面我们提出几点建议或者措施：根据实际需要，各校车的容量可以不同，因为各区的人员数量变化不会很大或者基本上在而一个稳定的状态。这样，在2问的理想假设下，人员多的站点安排大搭载量的车，人员不足一个校车搭载量的站点，则安排较小容量的车，人员小于一个大车搭载量而大于一个小车搭载量则安排容量处于之间的，等等，这样可以减少校车的数量。根据学校的教学时间表，可以得知教师及工作人员上班的人次，然后依据每天上、下午上班人数的不同，合理安排校车的发车量及发车时间.对于环境需求较高的地方，即使它是最大满意度点，不能建立乘车点。例如，很多实验室附近要尽量避免噪音、电磁辐射等等。参考文献：《运筹学》清华大学出版社《数据结构》清华大学出版社附录：第一问程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendend%M=100000A(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endd=zeros(n,1);d1=zeros(n,1);d2=zeros(n,1);mins1=100000;fori=1:n-1forj=i+1:nfork=1:nd(k)=min(B(k,i),B(k,j));ends=sum(d);if(s<=mins1)mins1=s;i1=i;j1=j;d1=d;endendendse11=zeros(1,n);num1=0;se12=zeros(1,n);num2=0;fork=1:nif(B(k,i1)<B(k,j1))num1=num1+1;se11(num1)=k;elsenum2=num2+1;se12(num2)=k;endendfprintf('\n问题一结果：\n');fprintf('选取两点时结果（%2d,%2d)=%5.2f\n',i1,j1,mins1);fprintf('\n选%2的点有%2d个：\n',i1,num1);fori=1:num1;fprintf('%2d',se11(i));endfprintf('\n');fprintf('选%2d的点有%2d个：\n',j1,num2);fori=1:num2;fprintf('%2d',se12(i));endfprintf('\n');mins2=100000;fori=1:n-2forj=i+1:n-1forp=j+1:nfork=1:nd(k)=min(min(B(k,i),B(k,j)),B(k,p));ends=sum(d);if(s<=mins2)mins2=s;i2=i;j2=j;p2=p;d2=d;endendendendrse11=zeros(1,n);rnum1=0;rse12=zeros(1,n);rnum2=0;rse13=zeros(1,n);rnum3=0;fork=1:nif(B(k,i2)<=B(k,j2)&&B(k,i2)<=B(k,p2))rnum1=rnum1+1;rse11(rnum1)=k;elseif(B(k,j2)<=B(k,i2)&&B(k,j2)<=B(k,p2))rnum2=rnum2+1;rse12(rnum2)=k;elseif(B(k,p2)<=B(k,i2)&&B(k,p2)<=B(k,j2))rnum3=rnum3+1;rse13(rnum3)=k;endendfprintf('\n\n选取三点时的结果（%2d,%2d,%2d）=%5.2f\n',i2,j2,p2,mins2);fprintf('\n选取%2d的点有%2d个：\n',i2,rnum1);fori=1:rnum1;fprintf('%2d',rse11(i));endfprintf('\n');fprintf('\n选取%2d的点有%2d个：\n',j2,rnum2);fori=1:rnum2;fprintf('%2d',rse12(i));endfprintf('\n');fprintf('\n选取%2d的点有%2d个：\n',p2,rnum3);fori=1:rnum3;fprintf('%2d',rse13(i));endfprintf('\n');第二问程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendend%M=100000A(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endmaxd=max(max(B));pp=[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];Total=sum(pp);W=zeros(50,1);W=pp/Total;d=zeros(n,1);d1=zeros(n,1);d2=zeros(n,1);r=zeros(n,1);s=zeros(n,1);r1=zeros(n,1);r2=zeros(n,1);maxs1=0;fori=1:n-1forj=i+1:nfork=1:nr(k)=min(B(k,i),B(k,j));s(k)=W(k)*(1-r(k)/maxd);endss=sum(s);if(ss>=maxs1)maxs1=ss;i1=i;j1=j;d1=d;endendendnum1=0;num2=0;fork=1:nif(B(k,i1)<B(k,j1))num1=num1+1;se11(num1)=k;elsenum2=num2+1;se12(num2)=k;endendfprintf('\n问题二结果：\n');fprintf('选取两点时结果（%2d,%2d)=%5.2f\n',i1,j1,maxs1);fprintf('\n选%2的点有%2d个：\n',i1,num1);fori=1:num1;fprintf('%2d',se11(i));endfprintf('\n');fprintf('选%2d的点有%2d个：\n',j1,num2);fori=1:num2;fprintf('%2d',se12(i));endfprintf('\n');maxs2=0;fori=1:n-2forj=i+1:n-1forp=j+1:nfork=1:nr(k)=min(min(B(k,i),B(k,j)),B(k,p));s(k)=W(k)*(1-r(k)/maxd);endss=sum(s);if(ss>=maxs2)maxs2=ss;i2=i;j2=j;p2=p;r2=d;endendendendrse11=zeros(1,n);rnum1=0;rse12=zeros(1,n);rnum2=0;rse13=zeros(1,n);rnum3=0;fork=1:nif(B(k,i2)<=B(k,j2)&&B(k,i2)<=B(k,p2))rnum1=rnum1+1;rse11(rnum1)=k;elseif(B(k,j2)<=B(k,i2)&&B(k,j2)<=B(k,p2))rnum2=rnum2+1;rse12(rnum2)=k;elseif(B(k,p2)<=B(k,i2)&&B(k,p2)<=B(k,j2))rnum3=rnum3+1;rse13(rnum3)=k;endendfprintf('\n\n选取三点时的结果（%2d,%2d,%2d）=%5.2f\n',i2,j2,p2,maxs2);fprintf('\选取3点时情形：\n');fprintf('\n选取%2d的点有%2d个：\n',i2,rnum1);fori=1:rnum1;fprintf('%2d',rse11(i));endfprintf('\n');fprintf('\n选取%2d的点有%2d个：\n',j2,rnum2);fori=1:rnum2;fprintf('%2d',rse12(i));endfprintf('\n');fprintf('\n选取%2d的点有%2d个：\n',p2,rnum3);fori=1:rnum3;fprintf('%2d',rse13(i));endfprintf('\n');第三问程序：n=50;A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendendA(1,2)=400;A(1,3)=450;A(2,4)=300;A(2,21)=230;A(2,47)=140;A(3,4)=600;A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200;A(6,7)=320;A(6,8)=340;A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285;A(9,10)=180;A(10,11)=150;A(10,15)=160;A(11,12)=140;A(11,14)=130;A(12,13)=200;A(13,34)=400;A(14,15)=190;A(14,26)=190;A(15,16)=170;A(15,17)=250;A(16,17)=140;A(16,18)=130;A(17,27)=240;A(18,19)=240;A(18,25)=180;A(19,20)=140;A(19,24)=175;A(20,21)=180;A(20,24)=190;A(21,22)=300;A(21,23)=270;A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;forj=1:nfori=1:j-1A(j,i)=A(i,j);endend[m,n]=size(A);B=zeros(m,n);B=A;forkk=1:4fori=1:nforj=1:nfork=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendendB;if(sum(sum(B-A))==0)break;endA=B;endmaxd=max(max(B));pp=[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,