摘要
本文就目前大学各区域与新校区之间校车乘车点的安排及教师和工作人员的满意程度展开研究，通过合理的抽象和假设，将乘车点的安排问题转化为无向图的多源最短距离的搜索问题，并通过一定的实地调查，将教师员工的满意度问题与校车运营成本结合起来，并在计算过程中运用exel,matlab等一系列计算机软件，得到了一些较为实际和精确的结果。
1、问题一：不考虑各点的人数，仅考虑各点到乘车点的总距离最短。
当乘车点n=3时，选择的乘车点是15,21,31三个点，最短总距离为19660； 当乘车点n=4时，选择的乘车点是11,18,22,32四个点，最短总距离为16961； 2、问题二：考虑到各点的人数，使将人数计算在内的总体距离最短（此时认为总体距离最短就是最满意）
当乘车点n=3时，选择的乘车点是16,23,32三个点，满意度为0.7811； 当乘车点n=4时，选择的乘车点是2,15,23,32四个点，满意度为0.8170； 3.问题三：为使教员和工作人员达到相对满意的的程度，又要求车辆最少，综合考虑到总体满意度和个体最小满意度。得到三个点为x,x,x;安排车辆数为y. 4.问题四：经过一定的实际情况调查，考虑到车辆运行成本和车辆满座率，乘车时间等实际问题，量化给出较为优化的解决方案。
关键词：搜索算法，最短距离矩阵，总体满意度，个人满意度，实际方案。
1、问题重述：
某学校建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。现有如下问题请你设计解决。
假设老校区的教师和工作人员分布在50个区，各区的距离见表1。各区人员分布见表2。
问题1：如要建立n个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪 个点。建立一般模型，并给出n=3,4时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n个点。建立一般模型，并给出n=3,4时的结果。
问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客45人（假定车只在起始站点载人）。
问题4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。 2、问题分析
2.1研究意义
就我校而言，就建有理学院新校区，各专业学院及教员小区与新校区之间就要靠校车解决。同时学校车辆有限，考虑到交通状况也不可能每个点都有车辆到达，如何安排车辆和乘车点使教员和工作人员满意，同时又能节约成本使资源得到最大的运用就是一个十分实际而有意义的问题。 2.2研究现状
/.
目前大多数校车乘车点和车辆安排都是在经验下做出的，没有做到量化处理，使方案达到最优化。 2.3存在问题
满意度的具体定义，乘车点和车辆怎样安排才能使教员和工作人员达到相对满意的程度，同时怎样在保证相对满意的条件下使车辆的运营成本最小，就牵扯到运营成本的具体量化，最后提出一套量化解决方案。 2.4解决方法
首先这50个区域可以简化成由50个点组成的无向图，题设中给出的点点之间的距离就是无向图中的边的权值，题目一可简化为无向图中其他点到选出点的最短距离问题，可以用floyd算法算出所有点之间的最短距离，再用穷举比较的方法计算各点到选出点的最短距离和的最小值。问题二可建立关于人数的满意度函数，在问题一的基础上算出最大满意度的方案。问题三则要考虑到校车的运营成本问题，综合总体满意度和个人满意度，给出一个教员相对满意且用车最少的方案，问题四则要结合一些实际问题考虑，如人的高峰时间、校车的满座率、校车的运行线路后才能给出一个较为实际和完备的方案。
3.模型假设
(1)未给出距离的两个区可以由其他区间接到达。
(2)乘车点只设在某几个区域内不能选择50个点以外的点作为乘车点。 (3)所有的教员都乘车，且都会去离自己最近的乘车点乘车。
(4)教员的满意度与离乘车点的距离有关，距离越远满意度越低，距离越近满意度越高。
(5)作为乘车点的区域的人到乘车点的距离为0。 (6)乘车点的选取数目不超过50。
4.符号约定
p:区域个数。 n:乘车点的个数.
X:题设给出的个点之间的稀疏矩阵。 Z:个点之间的最短距离矩阵。
xi,j：题设给出的i,j点原始距离。
1,2,3?p?这五十个区域中的节点相连得到的最短距离 zip,j：i,j两个点之间通过?zi,j：i,j点之间的最短距离。
S:五十个点到选出的乘车点的距离之和。
ZPi:第i个点的人数。
ZDi：第i个点距乘车点的最短距离。 ZYi：第i个点距离他最远点的距离。 M:教员的总体满意度。
/.
mi：第i个区的区域满意度。
5.模型的建立和求解
5.1最短距离矩阵的计算——floyd算法
对有权无向图 来说计算点与点之间的最短距离的方法有基于动态规划的floyd算法和dijkstra算法，其中的floyd算法具有速度快，且能方便记录路径的特点，所以我们选用floyd算法。
(1)在稀疏矩阵G中Gij表示第i个区域到第j个区域之间的距离； (2)用矩阵R来记录插入点的信息，其中Rij表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，
Gij?min(Gij,Gik?Gkj)，如果Gij的距离变小，则Rij=k，并把最短距离记录在矩阵
D中。算法完成后则R中包含了最短通路的信息，Dij中包含了最短路径的信息。
5.1.1数据分析
题设已经给出了一定的点之间的距离列表，由matlab求出个点之间距离的稀疏矩阵X.其中没有给出距离的点置为无穷大inf
?x1,1?x2,1 X= ?????x50,1x1,2???x50,2?x1,50?x2,50?? ???x50,50?再由floyd算法，进行迭代计算。对任意两点(i,j)，若存在z，使
?1p?1pzi,j?zip,p?zp,j，则更新zi,j?zi,j。
3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵
zi,j（i,j=1,2,...50) Matlab的代码将在附录一中给出，下图是由matlab生成的最 小距离矩阵的示意图，其中颜色越深表示距离越短。
/.
5.2使各区到乘车点的距离最小
5.2.1模型建立 为使个区人员到乘车点的距离最小，我们考虑个区人员到乘车点的总距离应该最小。
首先考虑仅设立一个乘车点的情况.设选出的乘车点是p1,则最短总距离
则为最短距离矩阵中其他点到选出点的距离之和
i?1,i?p1?ZD50(p1)i
在考虑设立两个乘车点的情况。当n=2时，我们就要考虑到一个乘车点的选择问题，第i点到底是选择p1作为乘车点，还是选择p2作为乘车点呢？应该是在这两种方案中选出距离较短的点作为i点的乘车点。
ZDi
则选取的两个点应使目标函数
?min(ZDi,ZDi)
p1p2/.
最小。
?ZDi?150i
下面我们考虑乘车点数为n的情况，当乘车点为n时的情况其实与乘车点为二是的情况没有什么区别，区别在与对乘车点的选择上需要比较更多的情况。
p3pnp1p2ZD?min(ZD,ZD,ZD,?,ZD iiiii)
乘车点的选择应使目标函数最小。 5.2.2模型求解
具体的matlab程序将在附录二中给出 由程序计算得当n=3时
选择的乘车点应为15,21,31三个点，最短总距离为19660。且到15乘车点的区域有5,6,7,8,9,10,11,12,13,14,15,16,17,18,25,26,27；到21乘车点的区域有1,2,3,4,19,20,21,22,23,24,44,45,46,47,48,49；到31乘车的区域有28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,50.
当n=4时
选择的乘车点应为11,18,22,32四个点，最短总距离为16961。且到11乘车点的区域有9,10,11,12,13,14,26,27；到18乘车点的区域有3,4,5,6,7,8,15,16,17,18,19，20,24,25；到22乘车点的区域有1,2,21,22,23,43,44,45,46,47,48,49；到
32
乘车点的区域有
29,30,31,32,33,34,35,36,37,38,39,40,41,42,50.
5.3乘车点的设置使各区人员满意度最大的模型 5.3.1模型建立
首先靠考虑到在该种情况下满意度的定义是什么，很明显在问题二的情况下啊，乘客满意的情况是到乘车点的距离越短越好，当乘车点就是该点的时候满意度就为最大，如果将满意度定为一的话，那么此时的满意度即为1,；如果乘车点世道该点最远的点时，此时乘客的满意度应为最小，即为0，由此我们可以建立满意度方程：
数学建模解决乘车点安排问答
