校车安排问题.doc

《校车安排问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、校车的最优化安排问题摘要本文研究了如何合理安排车辆并让教师和工作人员满意的问题。对于问题1，本文利用Floyd算法求出了最短路距离矩阵，在此基础上，本文以各区域到最近乘车点的距离和最小为目标函数对50个区域进行遍历分析，建立模型一，找出n个最优乘车点。并利用模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。对于问题2，为了表示满意度随距离的增大而减小的关系，本文建立满意度函数，然后以所有区域人员平均满意度最大为

2、目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为区域24和32，总满意度为0.7239。当建立3个乘车点时的最优解为区域16、23和32。平均满意度为0.7811。对于问题3，本文在模型二的基础上，设立满意度最低标准，添加满意度的约束条件Hk>h，建立车辆数模型。求得满意度最大的情况下的3个乘车点车辆使用情况，确定车辆最少需要54辆，三个站点所在的区域分别为2、26、31，对应的车辆数分别为12、19、23。对于问题4得出，我们结合模型对校车的安排问题提供了建议。关键词：Floyd算法；最短距离；满意度；最

3、优解；MATLAB1问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。现有如下四个问题需要设计解决。假设老校区的教室和工作人员分布在50个区，各区的距离见附录中表1。各区人员分布见附录中表2。问题1：如果建立n个乘车点，为使各区人员到最近乘车点的距离最小，建立模型，并分别给出2，3时的结果。问题2：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两

4、个和三个乘车点的校车安排方案。(假定车只在起始点载人)问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车。假设每辆车最多载客47人（假设车只在起始站点载人）。问题4：关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2问题的基本假设与说明1．假设未给出距离的两个区可以通过其他区间接到达。2．每位教师及工作人员均选择最短路径乘车。3．乘车点均建在各区内，不考虑区与区之间。4.教师及工作人员到各站点乘车的满意度与到该站点的距离有关系，距离近则满意度高，距离远则满

5、意度低。5.假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。6.在乘车点区内的人员乘车距离为零。7.根据实际情况，我们假设所设置的乘车点数不大于50。8.假设所有人员均乘车。9.假设每辆车只载一次人。10.假设汽车中途不再载人。11.假设每辆车的型号一致。12.假设每个乘车点的乘车人数固定不变。符号表示意义B(i,j)各个区通路的邻接矩阵B*(i,j)各个区完备图的邻接矩阵Pi第i乘车点所在的区lk第k个区到最近乘车点的距离Z50个区到各自最近乘车点的距离之和Hk第k区乘客的满意度所有乘客的平均满意度Wi第

6、i个乘车点的车辆数W所有乘车点的总车辆数mk第k区的人数h每个区满意度的下限（0

7、建立关于满意度的函数，然后以平均满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。问题3要求建立3个乘车点，在尽量使教师和工作人员满意的前提下，所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。问题4中我们结合第3问的结果对车辆的安排情况提出了建议。5模型的建立与求解5.1问题1的模型建立与求解5.1.1Floyd算法简介Floyd算法是弗洛伊德（floyd）提出的一种解决每对节点之间最短路径问题的的算法。算法的基本思想：直接在图的带权邻接矩阵中，用插

8、入顶点的方法依次构造出v个矩阵D(1)、D(2)、…、D(v),使最后得到的矩阵D(v)为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。1.在邻接矩阵G中表示第i个区域到第j个区域之间的距离；2.用矩阵R来记录插入点的信息，其中表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原