数学建模解决乘车点安排问题
摘要
本文就目前大学各区域与新校区之间校车乘车点的安排及教师和工作人员的满意程度展开研究，通过合理的抽象和假设，将乘车点的安排问题转化为无向图的多源最短距离的搜索问题，并通过一定的实地调查，将教师员工的满意度问题与校车运营成本结合起来，并在计算过程中运用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 :个点之间的最短距离矩阵。
j i x ,：题设给出的i,j 点原始距离。
p j i z ,：i,j 两个点之间通过(
)p Λ3,2,1这五十个区域中的节点相连得到的最短距离 j i z ,：i,j 点之间的最短距离。
S :五十个点到选出的乘车点的距离之和。
i ZP :第i 个点的人数。
i ZD ：第i 个点距乘车点的最短距离。
i ZY ：第i 个点距离他最远点的距离。
M:教员的总体满意度。
i m ：第i 个区的区域满意度。
5.模型的建立和求解
5.1最短距离矩阵的计算——floyd 算法
对有权无向图 来说计算点与点之间的最短距离的方法有基于动态规划的
floyd 算法和dijkstra 算法，其中的floyd 算法具有速度快，且能方便记录路径的
特点，所以我们选用floyd 算法。
(1)在稀疏矩阵G 中ij G 表示第i 个区域到第j 个区域之间的距离；
(2)用矩阵R 来记录插入点的信息，其中ij R 表示第i 个区域到达第j 个区域
所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距
离，min(,)ij ij ik kj G G G G =+，如果ij G 的距离变小，则ij R =k ，并把最短距离记录
在矩阵D 中。算法完成后则R 中包含了最短通路的信息，ij D 中包含了最短路径
的信息。
5.1.1数据分析
题设已经给出了一定的点之间的距离列表，由matlab 求出个点之间距离的
稀疏矩阵X.其中没有给出距离的点置为无穷大inf
X= ?????
???????50,502,501,5050,21,250,12,11,1x x x x x x x x ΛM O M O Λ 再由floyd 算法，进行迭代计算。对任意两点(,)i j ，若存在z ，使
1,1,,--+=p j p p p i j i z z z ，则更新p j i j i z z ,,=。
3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵
j i z ,（i,j=1,2,...50)
Matlab 的代码将在附录一中给出，下图是由matlab 生成的最 小距离矩阵的
示意图，其中颜色越深表示距离越短。
5.2使各区到乘车点的距离最小
5.2.1模型建立
为使个区人员到乘车点的距离最小，我们考虑个区人员到乘车点的总距
离应该最小。
首先考虑仅设立一个乘车点的情况.设选出的乘车点是p1,则最短总距离则为最短距
离矩阵中其他点到选出点的距离之和
∑≠=501,1)1(p i i p i ZD
在考虑设立两个乘车点的情况。当n=2时，我们就要考虑到一个乘车点的选择
问题，第i 点到底是选择p1作为乘车点，还是选择p2作为乘车点呢？应该是
在这两种方案中选出距离较短的点作为i 点的乘车点。
),min(21p i p i i
ZD ZD ZD =
则选取的两个点应使目标函数