校车安排问题.doc

校车安排模型摘要本文研究了如何合理安排车辆并让教师和工作人员满意的问题。在问题一中，我们利用算法求出了最短路距离矩阵，在此基础上，我们以各区域到最近乘车点的距离和最小为目标函数对50个区域进行遍历分析，建立模型一，找出n个最优乘车点。并利用模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。在问题二中，为了表示满意度随距离的增大而减小的关系，我们建立满意度函数，并对各区人数进行了归一化处理，然后以所有区域人员满意度最大为目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为19点和32点，总满意度为0.78。当建立3个乘车点时的最优解为第15，21，32点，满意度为0.83。在处理问题三时，我们利用总满意度最大模型和最少车辆的双目标函数，求得满意度最大的情况下的3个乘车点车辆使用情况；然后与“全区极限最少车辆数53.23”进行比较，发现和模型结果一致，于是确定车辆最少需要54辆，并且15，21，32三个乘车点各需17，19，18辆车。最后，我们结合模型对校车的安排问题提供了建议。一 问题提出许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。假设老校区的教室和工作人员分布在50个区。问题一：建立个乘车点，使各区人员到乘车点的距离最小，建立模型，并分别建立两个和三个乘车点的校车安排方案。问题二：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两个和三个乘车点的校车安排方案。(假定车只在起始点载人)问题三：在教师和工作人员尽量满意的前提下，在50个区内找出最优的三个乘车点的位置，并根据各个乘车点的人数，（车辆最多载客47人）确定车辆个数。最后，跟据以上所得出的结论，在提高乘车人员的满意度，又可节省运行成本的前提下，对如何改进校车的安排方案提出意见。二 模型分析第一问要求建立个乘车点，使各区人员到最近乘车点的距离最小。首先结合表一，利用算法求得任意两点之间最短距离；其次在50个区域中任意选取n个区域作为乘车点，找出每个区域所对应的最近乘车点，最后以50个区域到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立2个和3个乘车点时的校车安排问题进行求解。编辑本段定义Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。编辑本段核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n3);编辑本段算法描述a)初始化：Du,v=Au,vb)For k:=1 to nFor i:=1 to nFor j:=1 to nIf Di,jDi,k+Dk,j ThenDi,j:=Di,k+Dk,j;c)算法结束：D即为所有点对的最短路径矩阵编辑本段算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=空值。定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。编辑本段时间复杂度O(n3)编辑本段优缺点分析Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。第二问要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的函数（任意随距离单调递减的函数），并对每个区的人数进行归一化处理，然后以总满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。第三问要去建立3个乘车点，在尽量使教师和工作人员满意的前提下所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。第四问中我们结合第三问的结果对车辆的安排情况提出了建议。三 模型假设1、假设每个人只遵循最近点乘车原则2、假设每辆车只载一次人3、假设汽车中途不再载人4、假设每辆车的型号一致 5、假设每个乘车点的乘车人数固定不变四 符号说明 各区域到最近乘车点的总距离 三个乘车点时的总满意度 三个乘车点的总车辆数 总人数 区域号 区域到最近乘车点的最小距离 乘车点（） 各区域人数 到第个乘车点的子集合 满意度 第各乘车点的车辆数 区域到区域的最短距离矩阵 =（） =（）五 模型建立与求解5.0 问题一要求：建立n个乘车点，使各区人员到乘车点的距离最小，建立模型，并求的 时的结果。5.0.1采用算法求得50个区域的最短距离矩阵，结合表一，利用算法求的任意两点之间最短距离（程序见附录【1】）。算法如下：1、先根据题目数据为初始矩阵赋值，其中没有给出距离的赋给一大值，以便于更新。2、进行迭代计算。对任意两点，若存在，使，则更新。3、直到所有点的距离不再更新停止计算。则得到最短路距离矩阵，。5.0.2 建立模型一在最短路距离矩阵的基础上，再做如下分析：首先，在50个区域中任意选取n个区域作为乘车点其次，引入变量，表示k区域到最近乘车点的最小距离然后，求出50个区域到各自最近乘车点的最短距离之和，最后，建立模型一最佳乘车点是使得50个区域到各自最近乘车点的最短距离之和最小的点，基于此建立目标函数：其中 为选出的最佳乘车点。依据模型一，利用软件(程序见附录【2】)求得结果如下：当=2时：选两个乘车点时为18和31，总距离=24492米选18的区域有26个: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 24 25 26 27 47 选31的区域有24个:22 23 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 48 49 50当=3时：选三个乘车点时为15,21,31，总距离为=19660米选15的区域有17个: 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 选21的区域有16个: 1 2 3 4 19 20 21 22 23 24 44 45 46 47 48 49 选31的区域有17个:28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 50 5.1 问题二要求：考虑每个区的乘车人数，使工作人员和教师的满意度最大，建立模型，并求得 时的结果。5.1.1将各区人数归一化处理设第区人数为，总人数为第区人数权重为： 5.1.2建立满意度函数建立任意随距离单调递减的满意度函数，设为两点之间最小距离的最大值。当距离为0时满意度为1，距离为时为0 。建立满意度函数为：5.1.3 建立模型二结合满意度函数，在模型一的基础上，建立最高满意度乘车点选择模型，目标函数： 其中 表示选出的最高满意度下的最佳乘车点。依据模型二，利用软件求得结果如下（程序见附录【3】）：当=2时:选择的两个乘车点为19,32。满意度为0.78选19的区域有32个: 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 44 46 47 48 49 选32的区域有18个:13 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 45 50 当=3时：选择的三个乘车点为15,21,32。满意度为0.83。选15点有17个: 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 选21点有18个: 1 2 3 4 19 20 21 22 23 24 28 43 44 45 46 47 48 49 选32点有15个:29 30 31 32 33 34 35 36 37 38 39 40 41 42 50 5.2问题三要求：在教师和工作人员尽量满意的前提下，在50个区内找出最优的三个乘车点的位置，并根据各个乘车点的人数，确定最少车辆个数。求解问题三需要考虑两个约束条件：条件1为满意度最大；条件2为总的车辆数最少。设到第个乘车点的子集合为 。（表示向上取整） （1）其中为第个乘车点的车辆数， 表示各区域人数，三个乘车点的总车辆数。对问题二的分析求解，已知道当选择三个乘车点时，选择15,21,32为最近乘车点。于是：=5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27=1 2 3 4 19 20 21 22 23 24 28 43 44 45 46 47 48 49=29 30 31 32 33 34 35 36 37 38 39 40 41 42 50代入（1）式得：=17，=19，=18，=54由以上可知，选择15，21，32作为乘车点时的车辆数为：乘车点为15,21,32。在15点乘车人790，车16.81=17辆在21点乘车人879，车18.70=19辆在32点乘车人833，车17.72=18辆共17+19+18=54辆结合表二数据可知，全区总人数为2502，每辆车最多可载47人，全区极限最少车辆数为2502/47=53.23，即54辆，和模型结果一致，为最优解。5.3问题四通过对第三问的结果的分析可知，每个站点都存在空座的情况，所以我们建议在站点校车空座率较高的情况下时，在其他站点进行一次巡游。当校车型号单一时，很容易造成某些站点乘客难以乘车而其他某些站点又大量空座的情况，这种方案最大限度的节省了成本相当于所有乘客集中乘车，同时因为乘客依然可以在对自己满意度高的站点候车，也达到了使满意度逼近甚至达到最大的效果。六 模型评价与改进优点： 模型结构简单，而且便于计算，当数据量很大时，此优势更加突出。缺点： 模型的影响因素过于单一化，使得结果与实际情况有些误差。比如存在车载量未满开走或车辆等候教师及工作人员而停滞的现象。改进方案：本文模型适合于区域较少的情况，当区域量十分庞大的时候，模型的误差变大，所以我们考虑到，对于区域量很大的情况，以区域密集度为决策量，选出密集度高的区域作为乘车点被选区，在对乘车点被选区利用本文模型进行求解，这样使得问题变得简单化。七 参考文献1 vinglemar最短路径算法具体演示 /vinglemar/archive/2008/12/25/3605813.aspx2009年8月13日2 paincupid 数模归一化汇总 /paincupid/archive/2009/06/16/4273970.aspx2009年8月13日附录附录1通过求解最短路径的过程：n=50; %总共50个点A=zeros(n,n);for i=1:n for j=1:n if(i=j) A(i,j)=0; else A(i,j)=100000; end endend A(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)=204; 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;for j=1:n for i=1:j-1 A(j,i)=A(i,j); %使对称 endend m,n=size(A);B=zeros(m,n);B=A;%利用Flod算法计算最短距离矩阵for kk=1:4 kkfor i=1 :n for j=1:n for k=1:n t=B(i,k)+B(k,j); if tB(i,j) B(i,j)=t; end end endend if(sum(sum(B-A)=0) break; endA=B;End附录2问题1计算d=zeros(n,1);d1=zeros(n,1);d2=zeros(n,1); %计算各点k到把(i,j)点作为选定点时的距离 mins1=1000000; for i=1:n-1 for j=i+1:n for k=1:n d(k)=min(B(k,i),B(k,j); end s=sum(d); if(s=mins1) mins1=s; i1=i;j1=j; d1=d;end % fprintf(%2d,%2d)=%5.2fn,i,j,s); end end %计算选两个点情形 sel1=zeros(1,n); num1=0; sel2=zeros(1,n); num2=0; for k=1:n if(B(k,i1)B(k,j1) num1=num1+1; sel1(num1)=k; else num2=num2+1; sel2(num2)=k; end end %num1为到i1点的乘车点数,sel1(num1)存储具体的点 %num2为到j1点的乘车点数,sel2(num2)存储具体的点 fprintf(n问题1结果:n); fprintf(选两点时结果(%2d,%2d)=%5.2fn,i1,j1,mins1); fprintf(n选%2d的点有%2d个:n,i1,num1); for i=1:num1; fprintf(%2d ,sel1(i); end fprintf(n); fprintf(选%2d的点有%2d个:n,j1,num2); for i=1:num2; fprintf(%2d ,sel2(i); end fprintf(n); %计算选三个点情形 rsel1=zeros(1,n); rnum1=0; rsel2=zeros(1,n); rnum2=0; rsel3=zeros(1,n); rnum3=0; for k=1:n if(B(k,i2)=B(k,j2)&B(k,i2)=B(k,p2) rnum1=rnum1+1; rsel1(rnum1)=k; elseif(B(k,j2)=B(k,i2)&B(k,j2)=B(k,p2) rnum2=rnum2+1; rsel2(rnum2)=k; elseif(B(k,p2)=B(k,i2)&B(k,p2)=maxs1) maxs1=ss; i1=i;j1=j; r1=r;end % fprintf(%2d,%2d)=%5.2fn,i,j,s); end end %计算选两个点情形 sel1=zeros(1,n); num1=0; sel2=zeros(1,n); num2=0; for k=1:n if(B(k,i1)=maxs2) maxs2=ss; i2=i;j2=j; p2=p; r2=r;end % fprintf(%2d,%2d,%2d)=%5.2fn,i,j,p,s); end end end rsel1=zeros(1,n); rnum1=0; rsel2=zeros(1,n); rnum2=0; rsel3=zeros(1,n); rnum3=0; for k=1:n if(B(k,i2)B(k,j2)&B(k,i