校车安排问题.docVIP

校车安排模型

摘要

本文讨论了在不同情况下如何合理安排校车让教师和工作人员最大满意的问题。

在问题一中，把50个区看成50个点，我们先利用佛洛依德算法求出了任意两点间最短路距离矩阵，得到的一个50阶的矩阵，在此基础上，我们以各区域到各自最近乘车点的距离总和最小为目标设置N个乘车点，对50个区域进行遍历分析，总共需要进行对两点最短距离的查找，在n较小的情况下借助数学工具MATLAB可以较快找出各个区域到各自最近乘车点的最小距离和建立模型一，找出n个最优乘车点。在第一问的基础上并利用已给的一般模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。

在问题二中，根据满意度与距离成负相关的关系，把各区人数（各区到各自最近乘车点的最小距离）求和作为评价满意度的指标，由分析可知取最小值时教师职工的满意度最大然后以所有区域人员满意度最大为目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为19点和32点，总满意度为0.78。当建立3个乘车点时的最优解为第15，21，32点，满意度为0.83

关键词：Floyd算法满意度最短距离MATLAB

一问题重述

许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。

假设老校区的教室和工作人员分布在50个区。

问题一：建立个乘车点，使各区人员到乘车点的距离最小，建立模型，并分别建立两个和三个乘车点的校车安排方案。

问题二：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两个和三个乘车点的校车安排方案。(假定车只在起始点载人)

问题三：在教师和工作人员尽量满意的前提下，在50个区内找出最优的三个乘车点的位置，并根据各个乘车点的人数，（车辆最多载客47人）确定车辆个数。

最后，跟据以上所得出的结论，在提高乘车人员的满意度，又可节省运行成本的前提下，对如何改进校车的安排方案提出意见。

二问题分析

校车的安排并让教师职工尽量满意是个很重要的现实的问题，这里首先采用

算法求得任意两点之间最短距离，得到一个50阶的佛洛依德矩阵，在这个距震中可以方便的查找到任意两点之间的最短距离和路径，其次在50个区域中任意选取n个区域作为乘车点，找出每个区域所对应的最近乘车点，最后以50个区域到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立2个和3个乘车点时的校车安排问题进行求解。

算法的时间复杂度

O(n^3)

优缺点分析

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；

缺点：时间复杂度比较高，不适合计算大量数据。借助MATLAB可以较快实现。

第二问要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的衡量指标（各区人数到各自最近乘车点的距离最小距离的最小和），并对每个区的人数进行归一化处理，然后以总满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。

第三问要去建立3个乘车点，在尽量使教师和工作人员满意的前提下所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。

第四问中我们结合第三问的结果对车辆的安排情况提出了建议。

三模型假设

1、假设每个人采取到最近点乘车原则

2、假设汽车中途不再载人

3、假设每辆车的型号一致

4、假设每个乘车点的乘车人数固定不变，即不考虑意外的发生和教师职工的搬迁。

5、假设各区之间路径由题目给出，并且任意一个区到另外一个区都应经过由题目表中给出的距离的对应点。无距离对应的区域视为两点间没有直通路径。

6、乘车点应设置在50个区域。

7、校车中途无意外发生，交通秩序畅通。

四符号说明

Z区域各自最近乘车点的距离最短距离之和

三个乘车点时的总满意度

三个乘车点的总车辆数

区域号

区域到最近乘车点的最小距离

乘车点（）

各区域人数

到第个乘车点的子集合

满意度

第各乘车点的车辆数

区域到区域的最短距离矩阵

=（）

=（）

五模型