校车安排问题(论文).pdf

校车安排问题 摘要 我们对老校区乘车点选址问题进行研究，根据校区内教师与员工的分布，提 出了最佳乘车点的选取办法，建立了满意度与区域到乘车点距离的函数关系，并 根据获得数据模拟了乘车点选址的最优化的模型，得到如下结果： 问题1：根据77 组给定数据，首先建立了动态规划模型，用Dijkstra 算法 （Matlab 软件实现)求解任意两个区域之间最小路程并检验，得到了任意两点间 的最短距离矩阵D50×50 。再建立选址规划模型，求解使各区域人员到最近乘车点 n n 距离最小得 个乘车点的位置。最后求得当 2 时，选取18 和31 点最佳，总最 n 短距离为24492m ；当 3 时，选取15、21 和31 点最佳，总距离为19660m。 问题2 ：我们用归一法定义满意度与距离的函数关系，根据问题1中的任意 两点间的最短距离矩阵D50×50 ，得到满意度矩阵M 50×50 。根据每个区域的人数， 得出考虑人数的满意度矩阵RM 50×50 。再建立选址规划模型，求解使教师和工作 n n 人员满意度最大的 个乘车点的位置。结果：当 2 时，选取19 和32 点为乘车 n 点最佳，总最大满意度为1945.877；当 3 时，选取15、21 和32 点最佳，总最 大满意度为2066.743 。 问题3 ：这是一个双目标规划问题，考虑运行成本和满意度两个目标函数， 建立双目标非线性规划模型。当各乘车点人数平均分配的时候，运行成本最低， k 1 k 2 k 1 k 2 定义 为三个乘车点人数的方差， 为总满意度，因此要尽量使 最小， k 2α2 最大。由此可利用 α1 的最大值求得使教师和工作人员尽量满意并降低运行成 k 1 α1 α2 本的3 个乘车点位置,其中， 、 为运行成本和满意度的权重。最后求得设 k 2α2 立3 个乘车点时，分别为15、21 和32 点，需要校车55 辆； α1 的最大值为12.962， k 1 1 2 其中α1 ,α2 ,方差k 1=2378.7 ，满意度k 2 =2276.025 。 3 3 问题4 ：对解决问题四采取的方法是把问题三推广到n 个乘车点的情况。根 据前3 问的方法求出更多的数据进行对比分析。考虑满意度，运行成本，乘车点 数目三个目标函数，建立多目标规划模型。分析出最佳乘车点数目，进而根据第 3 问的模型给出最大满意度和需要车辆数，给出的合理建议。 关键字：最小距离 归一法 0-1 规划法 多目标非线性规划 Dijkstra 算法满 意度矩阵 方差 权重 量纲分析法 1 一、问题的重述 许多学校都建有新校区，常需要将老校区的教师和工作人员用校车送到新校 区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。必须让 教师和工作人员尽量满意，并有效的安排车辆，节省运行费用。因此对乘车点的 设立、教师和工作人员满意度问题的研究十分重要。 我们需要解决的问题： 假设老校区的教师和工作人员分布在50 个区，各区的距离见表 1。各区人员分 布见表2 。 1、我们需要研究一个较为简单的乘车点建立问题，根据表中的数据，建立乘 n n 车点为 时的一般模型，并给出 2 ，3 时解