数学建模-校车安排问题

1校车问题的分析报告摘要本文是解决如何有效的安排校车让教师和工作人员尽量满意的问题。根据老校区教师和工作人员所在区的分布以及各区的人数，针对如何设置乘车点使得各区距离乘车点最近，教师和工作人员最满意，以及如何有效安排车辆等问题进行了深入分析，利用改进的Floyd算法，综合评价方法建立了最短乘车距离模型、满意度评价模型对问题做出了详细合理的解答。针对问题一，考虑到需要求得每个区到达乘车点的最小距离，我们建立了最短乘车距离模型并通过改进后的Floyd算法(见附件2)实现。首先运用Floyd算法思想得到各顶点之间的最短通路值，并得到最小距离矩阵，然后运用for循环语句在各区中随机抽取n个区作为乘车点并在最小距离矩阵中取出对应的数据即乘车点到达任意一个区的最小距离向量。将这n个向量按位求最小值生成一个新向量A，对A向量各元素求和得到一个数S。最后将每次循环得到的S比较，最小值（S0）即为问题一的解。最后得出：n=2时应该在第18区和31区设立乘车点，其最短总距离为24492米。n=3时应该在第15区、21区和31区建立乘车点，最短距离为19660米。针对问题二，考虑到教师和工作人员的满意度受到距离与人数两个因素的影响，即满意度随着距离的增加而减小，而人数的多少会放大或减小距离对满意度的影响程度，从而建立了满意度评价模型。由于影响满意度的因素（人数、距离）存在不同的单位所以我们分别对人数和距离做了无量纲化处理（见公式1、2）并得到了满意度评价函数（见公式3）。最后在模型一的基础上，结合满意度评价函数建立了问题二的求解算法（见附件3）。依据模型可知当求得的数值越小表示不满意度越小即满意度越高，最终求解得到了：n=2时最优解为16区和36区不满意度为0.4980。当n=3时最优解为15区、22区和32区不满意度为0.3720。针对问题三，由于要求使用尽可能少的车辆让教师和工作人员的满意度尽量高，所以我们把车辆数作为一个限制满意度的条件。通过在问题二的基础上把车辆数考虑进去得到了问题三的求解公式和算法（见附4）。最终求解得到：当n=3时最优解为至少需要54辆车对应的区域分别为15、22、32。对应的车辆数为20、16、18。针对问题四，我们通过对前三个问题的深入分析对校车安排问题提出了合理化的建议和措施。关键词：最短乘车距离模型满意度评价模型Floyd算法2一、问题重述如今越来越多的学校需要经常将老校区的教师和工作人员用校车送到新校区，如何实现以最少的车辆让教师和工作人员尽量满意是个十分重要的问题。现已知老校区的教师和工作人员分布在50个区，以及各区的距离与各区人员分布情况。需要对以下问题进行研究：（1）建立n个乘车点，要求使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪n个点。建立一般模型，并给出2,3n时的结果。（2）若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n个点。建立一般模型，并给出2,3n时的结果。（3）若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。（4）关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。二、基本假设1.假设乘客的满意度只与小区到车站之间的距离以及车站乘车人数有关；2.在问题一、二中，假设每位教师及工作人员只会到最近的车站乘车；3.在问题一、二中，假设每位乘客到达车站后，都有校车乘坐；三、符号说明1.V1，V2，…Vk，…Vn表示各个区；2.A1，A2，…Ak,…An表示第k个区到其他区的最短距离的矩阵；3.S表示任意一种随机取得的车站方式所得到的最短距离；4.S0表示所有可能存在的组合方式构成车站的最短距离；5.Y满意度评价函数。四、模型的建立与求解34.1最短乘车距离模型：4.1.1问题分析：要求得使每个小区与车站距离最小，可以用以下几步来实现：（1）随机选择n个小区作为车站V1，V2，…Vk，…Vn；（2）求得这n个车站到任意一个小区的最小距离，并得到n个50阶的行矩阵A1，A2，…Ak,…An；（3）按位比较这n个行向量，得到最终每个小区到达最近车站的最短距离A；（4）将A中每个元素加起来，得到S，即为最短距离。（5）将所有随机可能性得出所有最终最短距离，进行比较，得到它们中的最小值S0，即为结果。如图1：随机取得n个小区作为车站V1，V2，…Vk，…Vn求得n个最小距离行向量A1，A2，…Ak,…An按位比较n个行向量，得到最终最小距离行向量A4图1：最小距离模型建立的示意图4.1.2随机选取n个小区作为乘车站点：我们运用n个for循环语句对随机选取n个小区作为乘车站点的所有情况进行一次历遍，以n=3为例，具体实现如算法1：fori=1:48forj=2:49fork=3:50算法1算法1是用循环的方法，将i，j，k分别从1取到48，2取到49，3取到50，这样就能得到从50个小区中随机选取三个作为乘车站点的所有可能，所选取的站点即为：Vi，Vj，Vk。4.1.3求得这n乘车站点到各个小区的最短距离：1.首先应得到由各个小区之间的距离组成的邻接矩阵（见附件1）；2.其次考虑到要计算任意两点之间的最短距离，我们采用了Floyd算法进行求算；将最小距离行向量A各项相加，得到此随机车站的最小总距离S将各种随机情况得到的最小总距离S比较，得到最小总距离S0，即为结果5示例：Floyd算法的基本步骤如图2所示问题，要求的任意两点之间的对短距离建立相邻矩阵，见表1，则从上面的表1开始，对于每两个顶点u、v，在表1中存储着一条路径u…v。现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如果u…a+a…vu…v的话，能够找到一条更短的路径。图2本来路径上源点或终点就有a的不必考虑。对角线上的也不必考虑，并且D[b][a]+D[a][c]=6+11D[b][c]=2，所以如果从a绕，反而远，又因为D[c][a]+D[a][b]=3+4D[c][b]=∞，所以如果从a绕，更近，因此，由表1变成表2。从上面的表2开始，对于每两个顶点u、v，在表2中存储着一条路径u…v。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果u…b+b…vu…v的话，能够找到一条更短的路径。同样地，本来路径上源点或终点就有b的不必考虑。对角线上的也不必考虑，D[a][b]+D[b][c]=6D[a][c]，所以如果从b绕，更近，D[c][b]+D[b][a]=7+6D[c][a]=3，所以如果从b绕，反而远，因此表2中的数据应该变为表3。从上面的表2开始，对于每两个顶点u、v，在表2中存储。着一条路径u…v。现在我们考察，试着把c加到u、v的路径上能否，得到26一条更短的路径，即如果u…c+c…vu…v的话，能够找到一条更短的路径。同样地，本来路径上源点或终点就有c的不必考虑。对角线上的也不必考虑，D[a][c]+D[c][b]=6+7D[a][b]=4，所以如果从c绕，反而远，D[b][c]+D[c][a]=2+3D[b][a]=6，所以如果从c绕，更近，因此表3应该变成表4中的数据。现在，已经把所有的顶点都试了一遍，算法结束。每两个顶点之间的路径如表4所示。表1表2abca,0411b602c3∞0abca0411B602c3707表3表4A0即为我们要得到的任意两点之间的最小距离的矩阵，见算法2：b=a+a';path=zeros(length(b));fork=1:50abca046b602c370abca046b502c3708fori=1:50forj=1:50ifb(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path算法2算法2即为Floyd算法的核心程序3．得到n个乘车站点到各个小区的最短距离的行矩阵：在2中得到的b矩阵中提取出这n个小区对应的行的行向量，例如，选取第一个小区作为乘车站点，则将b矩阵中的第一行取出，作为行向量A1，其他的依此类推即可，由此可以得到各个乘车站点最短距离的行矩阵A1，A2，…Ak,…An。4.1.4求得各个小区到这n个乘车站点的最短距离S：因为得到的行矩阵A1，A2，…Ak,…An的阶数是相同的，因此，我们按位求最小值，得出另一个行矩阵A，将A中各个元素相加就可以得到各小区到达这n个乘车站点的最小距离S，算法见算法3：fora=1:50t=[b(i,a)b(j,a)b(k,a)];d(a,1)=min(t);end;f(u,1)=sum(d);f(u,2)=i;f(u,3)=j;9f(u,4)=k;u=u+1;算法34.1.5得出最终结果S0：遍历所有可能情况后，通过比较每种情况得出的S，得出其最小值，得到的S0即为最小距离，取得最小距离时随机选取的i，j，k即为乘车站点的设置地点。具体的程序实现见程序1。4.1.6求解结果：n=2时应该在第18区和31区设立乘车点，其最短总距离为24492米。n=3时应该在第15区、21区和31区建立乘车站，最短距离为19660米。4.2满意度评价模型：4.2.1问题分析：对距离以及人数两个指标进行无量纲化处理，得到两个指标的量化数据。将已经无量纲化后的指标参数相乘得到定义的不满意度指标。10图3如图3，对于满意度模型：①我们对人数以及距离两个指标进行无量纲化处理，使其量化；②对两组无量纲化后的数据相乘，得到满意度评价函数，即相乘的结果越小，其满意度越大，我们将其定义为不满意度；③再对所有小区进行历遍，选取n个小区作为乘车站点，对其不满意度进行比较；④最后得出最小的不满意度即为本问的解4.2.2对指标进行无量纲化：1.对人数进行无量纲化：我们采用每个小区人数除以总人数的方法来实现其无量纲化，Qj=Pj/P0（公式1）得到表5：表5区域人数区域人数10.0259792260.006394920.0267786270.037569930.0167866280.007194240.0135891290.011590750.0151878300.02997660.0115907310.003996870.0067946320.034372580.0255795330.027977690.0155875340.0223821100.0079936350.0259792将得到后的综合指标当作第一问中的距离指标，建立满意度评价函数，求解第二问中的变化后的距离的最小值。11110.0243805360.0103917120.018785370.0319744130.0263789380.0359712140.0083933390.018785150.0279776400.0159872160.0339728410.0227818170.0047962420.0159872180.0139888430.0275779190.0191847440.0267786200.0215827450.0079936210.0195843460.0071942220.0047962470.0271783230.0215827480.028777240.0183853490.0303757250.0303757500.0247802表5表示出每个小区人数所占总人数的比例，反映出每个小区人数对于不满意度的权重值Qj(j=0~50)。2.对距离进行极值差方法处理：对附录中的数值进行极值差方法处理，得到无量纲的量化结果，Bij′=Bij−（Bi）min(Bi)max−（Bi）min（公式2）其中：Bij表示B矩阵中的第i行第j列的元素（Bi）min=min{Bij}(1≤i≤50)，（Bi）max=max{Bij}(1≤i≤50)3.得出满意度评价函数：Y=(Bij-（Bi）min)/(（Bi）max-（Bi）min)*（Pj/P0）（公式3）4.2.3求解结果：n=2时最优解为16区和3