校车安排问题、杜廷宇

《校车安排问题、杜廷宇》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、校车安排问题摘要问题一，运用题目给出的各区距离，建立了邻接矩阵，用了floyd算法求任意两点的最短路径，确定了最短距离矩阵。根据距离矩阵，以各区域到最近乘车点的距离之和为最小目标，筛选出乘车点n=2时，选择乘车点在18和31，归属区到乘车点的距离为24492。n=3时，选择的乘车点在15,21,31，归属区到乘车点的距离为19660。问题二，，结合问题一中的距离矩阵，建立了与距离有关的满意度函数模型。根据每个区乘客的满意度不同，每个区的人数也不同，建立了平均满意度函数模型。当时，选择的2个乘车点为区域24和区域32，平均满意度为0.7239。当时，选择的三个乘车点为区域16、区域2

2、3和区域32。平均满意度为0.7811。问题三，首先根据题目给出的各区人数，求出了最少需要54辆。求得满意度最大的情况下的3个乘车点车辆使用情况，将其与最少需要车辆进行比较，得出三个站点所在的区域分别为2、16、31，对应的车辆数分别为12、19、23。问题四，结合前三问的求解，考虑到了教职工每天上班时间，教职工乘车人数，等车时间，车辆型号大小等方面，根据实际情况给出了建议与考虑。关键字：校车安排乘车点距离矩阵满意度16一、问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及

3、让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。假设老校区的教师和工作人员分布在50个区。各区的距离见表1。各区人员分布见表2。问题1：如要建立个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。(假定车只在起始点载人)问题3若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。问题4；关于校车安排问题，你还有什么好的建

4、议和考虑。可以提高乘车人员的满意度，又可节省运行成本。各区的距离见附录表1，各区人员分布见附录表2。二、符号说明w：邻接矩阵：区域到区域构成的距离矩阵：i区到j区的距离：第i区乘客的满意度：总体乘客满意度的平均值：第i个区离本区最远区的距离：第i个区离本区最近区的距离：第n个乘车站点的车辆数16：第i个区的乘车人数一、问题假设1、假设教职工在去往乘车点途中不会发生意外2、假设校车准时到达乘车点3、假设每辆校车的行驶速度是一定的4、假设校车不能重复经过各区5、乘车点只能建立在各区上，不能在区与区之间6、教职工的满意度与等车时间没有直接联系二、问题分析针对问题一，没有给出各个区的方位，

5、是一个无向路线的问题。使各区人员到最近乘车点的距离最小，可以用Floyd算法先计算出各区之间的最短路径。在选择合适乘车点的问题上，用筛选矩阵的方法，每个区之间距离都要进行比较。进行多次循环找出各区到最近距离的乘车站点。针对问题二，教师与工作人员的最大满意度与等车时间没有直接关系，只与距离有关，乘车距离越近，教职工的满意度越高，所以要建立与距离有关的满意度函数。在问题一的基础上，选择出最高满意度的乘车点。建立平均满意度，得到各区对乘车点的平均满意度。针对问题三，根据题目可以算出最少的乘车辆，要设立三个乘车点有种可能，利用问题二的模型计算出每种可能性的教职工人员满意度、总车辆数。然后让

6、其与最小车辆数进行比较，筛选出较合适的车辆数，再结合教职工满意度，确定乘车点。针对问题四，可以在教职工每天上班时间，教职工乘车人数，等车时间，车辆型号大小等方面进行建议，提高效率，提高满意度。五、模型的建立与求解5.1、问题一的模型建立于求解5.1.1、Floyd的距离矩阵算法原理[1]Floyd算法：求任意两点之间的最短路径16。首先根据题目给出的各区距离表，构造带权邻接矩阵w，作为距离矩阵的初值即。带权邻接矩阵中的元素是由权构成的，此题中，权表示的到各区距离，每一行即表示分别到的距离，若没有该区到下一个区直接路径，将该权值可视为无穷值。距离矩阵可以理解为，其中是表示到的只允许以

7、作为中间点的路径中最短路的长度。即是从到中间可插入任何顶点的路径中最短路的长度，因此，即是距离矩阵。经过matlab的计算（程序一）可得的距离矩阵如图表1（只列出了1-15个地区的距离矩阵）表11-15个地区的距离地区1234567891011121314151040045070091011401110128014801614176419042104164414542400085030051074071088010801214136415041704124410543