校车的最优化安排问题
摘要
本文研究了如何合理安排车辆并让教师和工作人员满意的问题。
对于问题1，本文利用Floyd算法求出了最短路距离矩阵，在此基础上，本文以各区域到最近乘车点的距离和最小为目标函数对50个区域进行遍历分析，建立模型一，找出n个最优乘车点。并利用模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。
对于问题2，为了表示满意度随距离的增大而减小的关系，本文建立满意度函数，然后以所有区域人员平均满意度最大为目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为区域24和32，总满意度为0.7239。当建立3个乘车点时的最优解为区域16、23和32。平均满意度为0.7811。
对于问题3，本文在模型二的基础上，设立满意度最低标准，添加满意度的约束条件H k>h，建立车辆数模型。求得满意度最大的情况下的3个乘车点车辆使用情况，确定车辆最少需要54辆，三个站点所在的区域分别为2、26、31，对应的车辆数分别为12、19、23。
对于问题4得出，我们结合模型对校车的安排问题提供了建议。
关键词：Floyd算法；最短距离；满意度；最优解；MATLAB
1 问题重述
许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。现有如下四个问题需要设计解决。
假设老校区的教室和工作人员分布在50个区，各区的距离见附录中表1。各区人员分布见附录中表2。
问题1：如果建立n个乘车点，为使各区人员到最近乘车点的距离最小，建立模型，并分别给出
n2，3时的结果。
问题2：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两个和三个乘车点的校车安排方案。(假定车只在起始点载人)
问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车。假设每辆车最多载客47人（假设车只在起始站点载人）。
问题4：关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。
2问题的基本假设与说明
1．假设未给出距离的两个区可以通过其他区间接到达。
2．每位教师及工作人员均选择最短路径乘车。
3．乘车点均建在各区内，不考虑区与区之间。
4. 教师及工作人员到各站点乘车的满意度与到该站点的距离有关系，距离近则满意度高，距离远则满意度低。
5. 假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。
6. 在乘车点区内的人员乘车距离为零。
7. 根据实际情况，我们假设所设置的乘车点数不大于50。
8. 假设所有人员均乘车。
9. 假设每辆车只载一次人。
10. 假设汽车中途不再载人。
11. 假设每辆车的型号一致。
12. 假设每个乘车点的乘车人数固定不变。
3 符号说明
4问题的分析
问题1要求建立n个乘车点，使各区人员到最近乘车点的距离最小。首先结合表1，利用Floyd算法求得任意两点之间最短距离；其次在50个区域中任意选取n个区域作为乘车点，，找出每个区域所对应的最近乘车点，最后以50个区域到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立2个和3个乘车点时的校车安排问题进行求解。
问题2要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的函数，然后以平均满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。
问题3要求建立3个乘车点，在尽量使教师和工作人员满意的前提下，所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。
问题4中我们结合第3问的结果对车辆的安排情况提出了建议。
5 模型的建立与求解
5.1 问题1的模型建立与求解 5.1.1 Floyd 算法简介
Floyd 算法是弗洛伊德（floyd ）提出的一种解决每对节点之间最短路径问题的的算法。
算法的基本思想：直接在图的带权邻接矩阵中，用插入顶点的方法依次构造出v 个矩阵D (1)、D (2)、…、D (v),使最后得到的矩阵D (v)为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
1.在邻接矩阵G 中ij G 表示第i 个区域到第j 个区域之间的距离；
2.用矩阵R 来记录插入点的信息，其中ij R 表示第i 个区域到达第j 个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，
m in(,)ij ij ik kj G G G G =+，如果ij G 的距离变小，则ij R =k ，并把最短距离记录在矩阵
D 中。算法完成后则R 中包含了最短通路的信息，ij D 中包含了最短路径的信息。
关于本文具体问题的算法（算法程序见程序1）如下：
1.先根据题目所给的各个连通区域之间距离的数据为初始矩阵(,)B i j 赋值，其中没有给出距离的赋给无穷大，其中B(i,j)=0(i=j)。
2.进行迭代计算。对任意两点(,)i j ，若存在k ，使(,)(,)(,)B i k B k j B i j +<，则更新(,)(,)(,)B i j B i k B k j =+。
3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵
B *(i,j)(,1,2,...,50)i j =。
5.1.2 模型一的建立
在上述最短路距离矩阵B *(i,j)的基础上，分析建立n 个乘车点的情况： 首先，在50个区域中任意选取n 个区域作为乘车点
{}n p p p ,...,,21{}50,...,2,1∈
