《数学建模-校车安排问题(共27页)》由会员分享，可在线阅读，更多相关《数学建模-校车安排问题(共27页)（27页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上校 车 问 题 的 分 析 报 告摘要本文是解决如何有效的安排校车让教师和工作人员尽量满意的问题。根据老校区教师和工作人员所在区的分布以及各区的人数，针对如何设置乘车点使得各区距离乘车点最近，教师和工作人员最满意，以及如何有效安排车辆等问题进行了深入分析，利用改进的Floyd算法，综合评价方法建立了最短乘车距离模型、满意度评价模型对问题做出了详细合理的解答。针对问题一，考虑到需要求得每个区到达乘车点的最小距离，我们建立了最短乘车距离模型并通过改进后的Floyd算法(见附件2)实现。首先运用Floyd算法思想得到各顶点之间的最短通路值，并得到最小距离矩阵，然后运用for
2、循环语句在各区中随机抽取n个区作为乘车点并在最小距离矩阵中取出对应的数据即乘车点到达任意一个区的最小距离向量。将这n个向量按位求最小值生成一个新向量A，对A向量各元素求和得到一个数S。最后将每次循环得到的S比较，最小值（S0）即为问题一的解。最后得出：n=2时应该在第18区和31区设立乘车点，其最短总距离为24492米。n=3时应该在第15区、21区和31区建立乘车点，最短距离为19660米。针对问题二，考虑到教师和工作人员的满意度受到距离与人数两个因素的影响，即满意度随着距离的增加而减小，而人数的多少会放大或减小距离对满意度的影响程度，从而建立了满意度评价模型。由于影响满意度的因素（人数、距
3、离）存在不同的单位所以我们分别对人数和距离做了无量纲化处理（见公式1、2）并得到了满意度评价函数（见公式3）。最后在模型一的基础上，结合满意度评价函数建立了问题二的求解算法（见附件3）。依据模型可知当求得的数值越小 表示不满意度越小即满意度越高，最终求解得到了：n=2时最优解为16区和36区不满意度为0.4980。当n=3时最优解为15区、22区和32区不满意度为0.3720。针对问题三，由于要求使用尽可能少的车辆让教师和工作人员的满意度尽量高，所以我们把车辆数作为一个限制满意度的条件。通过在问题二的基础上把车辆数考虑进去得到了问题三的求解公式和算法（见附4）。最终求解得到：当n=3时最优解为
4、至少需要54辆车对应的区域分别为15、22、32。对应的车辆数为20、16、18。针对问题四，我们通过对前三个问题的深入分析对校车安排问题提出了合理化的建议和措施。关键词：最短乘车距离模型 满意度评价模型 Floyd算法一、问题重述如今越来越多的学校需要经常将老校区的教师和工作人员用校车送到新校区，如何实现以最少的车辆让教师和工作人员尽量满意是个十分重要的问题。现已知老校区的教师和工作人员分布在50个区，以及各区的距离与各区人员分布情况。需要对以下问题进行研究：（1） 建立个乘车点，要求使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。（2） 若考虑
5、每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。（3） 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。（4） 关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。二、基本假设1.假设乘客的满意度只与小区到车站之间的距离以及车站乘车人数有关；2.在问题一、二中，假设每位教师及工作人员只会到最近的车站乘车；3.在问题一、二中，假设每位乘客到达车站后，都有校车乘坐；三、符号说明1. V1，V2，Vk，Vn表示各个区；2. A1，A
6、2，Ak,An表示第k个区到其他区的最短距离的矩阵；3.S表示任意一种随机取得的车站方式所得到的最短距离；4.S0表示所有可能存在的组合方式构成车站的最短距离；5.Y 满意度评价函数。四、模型的建立与求解4.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）将所有随机可能性得
7、出所有最终最短距离，进行比较，得到它们中的最小值S0，即为结果。如图1：随机取得n个小区作为车站V1，V2，Vk，Vn 求得n个最小距离行向量 A1，A2，Ak,An按位比较n个行向量，得到最终最小距离行向量A 将最小距离行向量A各项相加，得到此随机车站的最小总距离S将各种随机情况得到的最小总距离S比较，得到最小总距离S0，即为结果图1：最小距离模型建立的示意图4.1.2随机选取n个小区作为乘车站点： 我们运用n个for循环语句对随机选取n个小区作为乘车站点的所有情况进行一次历遍，以n=3为例，具体实现如算法1： for i=1:48 for j=2:49 for k=3:50 算法1算法1
8、是用循环的方法，将i，j，k分别从1取到48，2取到49，3取到50，这样就能得到从50个小区中随机选取三个作为乘车站点的所有可能，所选取的站点即为：Vi，Vj，Vk。4.1.3求得这n乘车站点到各个小区的最短距离：1.首先应得到由各个小区之间的距离组成的邻接矩阵（见附件1）；2.其次考虑到要计算任意两点之间的最短距离，我们采用了Floyd算法进行求算；示例：Floyd算法的基本步骤2如图2所示问题，要求的任意两点之间的对短距离建立相邻矩阵，见表1，则从上面的表1开始，对于每两个顶点u、v，在表1中存储着一条路径uv。现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如果ua
9、+avDbc=2，所以如果从a绕，反而远，又因为Dca+Dab=3+4Dcb= ，所以如果从a绕，更近，因此，由表1变成表2。从上面的表2开始，对于每两个顶点u、v，在表2中存储着一条路径uv。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果ub+bvuv的话，能够找到一条更短的路径。同样地，本来路径上源点或终点就有b的不必考虑。对角线上的也不必考虑，Dab+Dbc=6Dca=3，所以如果从b绕， 反而远，因此表2中的数据应该变为表3。 从上面的表2开始，对于每两个顶点u、v，在表2中存储。着一条路径uv。现在我们考察，试着把c加到u、v的路径上能否，得到一条更短的路径
10、，即如果uc+cvDab=4，所以如果从c绕，反而远，Dbc+Dca=2+3b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endendb,path算法2算法2即为Floyd算法的核心程序3得到n个乘车站点到各个小区的最短距离的行矩阵：在2中得到的b矩阵中提取出这n个小区对应的行的行向量，例如，选取第一个小区作为乘车站点，则将b矩阵中的第一行取出，作为行向量A1，其他的依此类推即可，由此可以得到各个乘车站点最短距离的行矩阵A1，A2，Ak,An。4.1.4求得各个小区到这n个乘车站点的最短距离S：因为得到的行矩阵A1，A2，Ak
11、,An的阶数是相同的，因此，我们按位求最小值，得出另一个行矩阵A，将A中各个元素相加就可以得到各小区到达这n个乘车站点的最小距离S，算法见算法3： for a=1:50 t=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; f(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
