校车安排问题.doc

校车安排问题的研究 摘要本文主要对现实中学校安排校车接送教职工，对于满足不同的情况下校车站点建在哪些区域进行了分析研究，并建立了数学模型和求解方法。问题一中，首先根据floyd算法计算出每个区域到达其他区域的最短路径矩阵，然后根据穷举法利用计算机进行求解。得知当n=2时，在区域18和31处建立乘车点，最短距离和为24492.当n=3时，在区域15、21和31处建立乘车点，最短距离和为19660.问题二中，为了考虑教师和工作人员的满意度、各区域的乘车人数。本文把满意度理解为随距离而递减的一种关系，并定义最简单的关系式.同时为了考各虑区域的人数，本文把各区域的人数乘以满意度来作为问题一中最短路径矩阵的权值。然后同样根据穷举法利用计算机进行求解。得知当n=2时，在区域16和32建立乘车点，最大满意度为12.1945.当n=3时，在区域16、27和32处建立乘车点，最大满意度为14.1716.问题三中，为了使教师的满意度最高，同时使所需要的车辆数目最少。这本是一个多目标最优化问题，为简化问题，本文定义为新的目标函数。这样的最大值就是题目所要求的结果。同样按照穷举法求解得知当在区域16、27和32处建立乘车点，最大满意度为14.1716。其中在区域16乘车点乘车的人数为609，需要车辆数14；在区域27乘车点乘车的人数为982，需要车辆数21.在区域32乘车点乘车的人数为911，需要车辆数20.一共需要车辆数为55. 关键词：最短路径；floyd算法；穷举法；满意度；简化问题一. 问题的重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在50个区，各区的距离见附件表1。各区人员分布见附件表2。问题1：如要建立个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。问题4：关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。二问题分析对于问题一的求解，要建立乘车点的位置，使各区人员到乘车点的距离和最小。本文首先必须计算出各区域之间的最短距离，然后可以考虑穷举法利用计算机搜索出建立乘车点的最佳位置。对于问题二的求解，首先可以根据距离来定义一个满意度函数，把问题一中的最短路径矩阵转化成满意度矩阵。然后考虑区域人数因素，对满意度矩阵进行权值处理，然后可以按照问题一中的穷举法求出建立乘车点的最佳位置。对于问题三，为了使教师和工作人员的满意度最大，而安排的车辆最少，这是一个多目标最优化问题。在问题二的基础上，可以同时考虑满意度和车辆数进行最优化求解。三符号说明n 站点个数G 各区域间距离的邻接矩阵 表示第i个区域 最短路径矩阵 考虑满意度和各区域人数后的权值矩阵 表示最短路径矩阵中第i个区域到第j个区域的最短距离 第i个区域的人员数 满意度系数 第i个区域人员的到第j个乘车点乘车的满意度四模型假设：1.不考虑教职工在站点的等待时间；2.不考虑各个站点之间路面的情况；3.不考虑各区域的面积大小。五模型的建立与求解5.1 问题一的模型建立与求解 根据题意，为了建立n个乘车点，使各区域人员到最近乘车点的距离总和最小。首先本文根据floyd最短路径算法5求出每个区域到其他各区域的最短路径。其中floyd算法的过程如下:1.在邻接矩阵G中表示第i个区域到第j个区域之间的距离；2.用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，如果的距离变小，则=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，中包含了最短路径的信息。在得到了包含最短路径信息的矩阵后，本文采用了穷举法找出了建立n个乘车点的最优解，穷举法的过程如下:在总区域中任选n个区域 (n=2,3)，计算V中每个区域到的最短距离的总和。在这些最短距离的总和中，最小的那个距离总和就是本题的最优方案。本文用计算机对n=2和n=3的情况进行了求解，具体的求解结果如下1.当n=2时，应该在第18和第31区域建立乘车点，最短路径和为24492.其中到第18区域乘车点的乘车的区域有:.到第31区域乘车点乘车的区域有:2.当n=3时，应该在第15，21和31区域建立乘车点，最短路径和为19960.其中到15区域乘车点乘车的区域有.到21区域乘车的区域有：.到31区域乘车的区域有：.5.2问题二的模型建立与求解在问题一得基础上，要考虑每个区域的乘车人数和教师、工作人员的满意度。首先，根据本文的理解，教师的乘车满意度应该是随距离增大而递减的一个函数。在本文中定义的第i个区域的人员到第j个区域乘车的满意度与第i个区域和第j个区域的最短距离成反比，即其中k是满意度系数，在本文中不妨取k=1.其次为了考虑区域的人数这个因素，本文将区域的人数乘以该区域的满意度矩阵作为权值，则重新考虑后的权值矩阵为 ， 对任意的j=1，2，50.其中i=1，2，50.把矩阵换成问题一中矩阵后重新用穷举法对n=2，3的情况进行计算机求解有 当n=2时，在区域16和区域32处建立乘车点，最大满意度为12.1945.其中到16区域乘车点的区域有：.到区域32处的乘车的区域有：. 当n=3时，在区域16、区域27和区域32处建立乘车点，最大满意度为14.1716.其中到16区域乘车点乘车的区域有：.到27区域乘车点乘车的区域有：.到32区域乘车点乘车的区域有：.5.3 问题三的模型建立与求解为了使教师的满意度最大，而所需要的车辆最少，这是一个两个目标的最优化问题，为了简化求解过程。本文定义目标函数 (1)从(1)式可以看出，若教师的满意度最大，所需的车辆最少，则得值越大。这样原问题就转化成为求目标函数的最大值。同样根据模型二的方法，当n=3时利用计算机进行穷举搜索后得在第16，27和32区域建立乘车点。最大满意度为14.1716.其中去16区域乘车点乘车的区域有：.一共609人，需要车辆的数目14.去27区域乘车点乘车的区域有：.一共982人，需要的车辆的数目为21.去32区域乘车点的乘车的区域有：.一共911人，需要车辆的数目为20.综上可知，在第16、27和32区域建立乘车点，最大满意度为14.1716.需要的总车辆数为55辆。5.4 问题四的一些建议考虑到教师与工作人员可能上班的时间不同，可以通过加开班车次数而不加校车的策略来提高乘车人员的满意度，此外，还可以让未坐满的校车可以先到各区去搭乘超载的教师与工作人员，来减少校车数量，降低运行成本。六、模型的评价与改进本文在问题的解决中均采用穷举法进行最优解搜索，求解得结果还是令人满意的。但是穷举法在算法的时间消耗上时比较大的，在n=3时，程序求解的时间达到15秒之多。这是本文今后所需要改进了方向，寻找一个搜索效率比较的好的算法。在问题二中，在得到满意度是随距离而递减的一个关系时，本文定义的满意度关系式比较简单，在实际中，满意度的定义应通过调查后由相关信息所得出。再问题三中，在同时考虑满意度和车辆数的情况下，这本是一个多目标最优化问题本文定义了一个新的目标函数，大大简化了原问题，使得原问题的求解变得十分方便。七、参考文献1.孙家广，陈玉建，幸凯宁.计算机辅助几何造型技术M，北京，清华大学出版社，19902.陈东彦，李冬梅，王树忠.数学建模M，北京，科学出版社，20073.李荣华，刘博.微分方程数值解M,北京，高等教育出版社，20094.孙麟平.运筹学M，北京，科学出版社，20085.严蔚敏.数据结构M，北京，清华大学出版社，2008附件：部分程序代码function D,R=floyd(varargin)%原始数据-r=1 1 2 2 2 3 4 4 5 5 6 6 7 7 8 8 9 10 10 11 11 12 13 14 14 15 15 16 16 17 18 18 19 19 20 20 21 21 21 22 22 22 23 23 23 23 24 24 26 26 27 28 29 30 30 30 31 31 31 32 32 32 33 35 36 36 37 38 39 40 40 42 43 43 45 46 48;c=2 3 4 21 47 4 5 19 6 7 7 8 8 18 9 15 10 11 15 12 14 13 34 15 26 16 17 17 18 27 19 25 20 24 21 24 22 23 47 44 45 48 24 29 30 44 25 28 27 34 28 29 31 31 42 43 32 36 50 33 35 36 34 37 39 40 38 39 41 41 50 50 44 45 46 48 49;s=400 450 300 230 140 600 210 310 230 200 320 340 170 160 200 285 180 150 160 140 130 200 400 190 190 170 250 140 130 240 204 180 140 175 180 190 300 270 350 160 270 180 240 210 290 150 170 130 140 320 190 260 190 240 130 210 230 260 210 190 140 240 210 160 180 190 135 130 310 140 190 200 260 210 240 280 200;people=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;S=sparse(r,c,s,50,50);a=full(S);%初始化矩阵-for i1=1:50 for j1=i1:50 a(j1,i1)=a(i1,j1); endend for i=1:50 for j=1:50 if a(i,j)=0&(i=j) a(i,j)=Inf; else continue; end endend% Floyd算法求最短路径，输入矩阵a为各点的带权邻接矩阵，Inf表示两点不通。% 输出矩阵D为各点间最短距离，矩阵R为最短路径。%-n=size(a,1); D=a; for i=1:n for j=1:n Ri,j=strcat(num2str(i),),strcat(num2str(j),);end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(j,k) C(i,j)=C(i,j)+D(i,k); Cki,j(1,k)=k; else C(i,j)=C(i,j)+D(j,k); Cki,j(2,k)=k; end end endend%-%输出结果-max(C(:)i,j=find(C=max(C(:)Cki,j(1,:)Cki,j(2,:) 表1 各区域的距离表区域号区域号距离(m)1240013450243002212302471403460045210419310562305720067320683407817071816089200815285910180101115010151601112140111413012132001334400141519014261901516170151725016171401618130172724018192041825180192014019241752021180202419021223002123270214735022441602245270224818023242402329210233029023441502425170242813026271402634320272819028292602931190303124030421303043210313223031362603150210323319032351403236240333421035371603639180364019037381353