西电数模校车安排问题.docVIP

校车安排问题 摘要 本文研究的是校车安排问题。通过运用优化的思想理论，在分析问题的条件和要求的基础上，建立了三个模型。即模型一是总距离最小的优化模型；模型二是满意度最大的优化模型；模型三是基于3个乘车点的多目标优化模型。 关键字 一 问题的重述 要用校车将老校区的教师和工作人员送到新校区，这便涉及如何有效的安排车辆及让教师和工作人员尽量满意的问题。假设老校区的教师和工作人员分布在50个区（详见表2），各区域间存在一定的距离（详见表1）。现有如下问题： 1、如要建立个乘车点，为使各区人员到最近乘车点的距离最小，应该将 校车乘车点建立在哪个点。建立一般模型，并给出时的结果。 2、若考虑每个区的乘车人数，为使教师和工作人员满意度最大，应该将校车乘车点建立在哪个点。建立一般模型，并给出时的结果 (假定车只在起始点载人) 。 3、 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。 4、关于校车安排问题，是否还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。 二 模型的假设与符号说明 3.1 模型的假设 （1）（2）-----距离矩阵 -----点到最近乘车点的距离 -----目标函数 -----选出的第个乘车点 -----第区人数 -----第区人数权重 -----50个区域的总人数 -----各区人员的满意度 -----第个乘车点的车辆数 三 问题的分析 要接送学校老校区的教师和工作人员到新校区，由于人员分布在50个区，各区之间存在一定距离，因此如何有效的安排车辆及让教师和工作人员尽量满意成为一个十分重要的问题。 对于问题1，首先求解出任意两区之间的最短距离，然后以到最近乘车点的总距离最小为目标函数，确定具体的乘车点位置。 对于问题2，为使教师和工作人员的满意度最大，可将每个区人数作为权重，建立满意度函数，从而求解出乘车点位置。 对于问题3，可由问题2建立的模型确定乘车点的位置，再以总车辆最少为目标函数，求解出出所需的车辆数。 四 模型的建立与求解 4.1问题1模型的建立与求解 4.1.1问题1一般模型的建立 要确定具体乘车点的位置，首先应求得任意两点的最短距离。将任意两点的距离转换成一个距离矩阵，，采用Floyd算法求解最短距离矩阵（程序见附录1）。具体算法如下： 1) 先根据题目数据给初始距离矩阵赋值，其中没有给出距离的赋一大值（例如1000000），以便于更新。 2) 进行迭代计算。对任意两点，，若存在，使，则更新。 3) 直到所有点的距离不再更新停止计算。则得到最短距离矩阵，。 然后建立以总距离最小为目标函数的优化模型 (1) 其中，为的子集，表示选出的个乘车点。 4.1.2 当时的模型求解 当时，； 当时，。 在Matlab软件中求解得出结果如下（程序见附录1）： 选两个乘车点时为18和31，总距离为24492米。 选18的点有26个: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 24 25 26 27 47 选31的点有24个: 22 23 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 48 49 50 选三个乘车点时为15,21,31，总距离为19660米。 选15的点有17个: 5 6 7 8 9 10 11 12 13 14 15 16 17 18 25 26 27 选21的点有16个: 1 2 3 4 19 20 21 22 23 24 44 45 46 47 48 49 选31的点有17个: 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 50 4.2问题2模型的建立与求解: 问题2应该建立满意度函数，将每个区人数作为权重，目标函数为总满意度最大。 4.2.1 各区人数的归一化处理 设第区人数为，总人数为。 则第区人数权重为。 4.2.2 建立满意度函数 可建立任意随距离递增单调递减的满意度函数，建立如下满意度函数。 设两点之间最小距离的最大值为。 设满意度函数为距离为0时满意度为1，距离为时满意度为0的线性函数，即： 则目标函数满意度最大：