数学建模论文——校车安排问题

校车的最优化安排问题之论文摘要本文研究了如何合理安排车辆并让教师和工作人员满意的问题。对于问题1，本文利用Floyd算法求出了最短路距离矩阵，在此基础上，本文以各区域到最近乘车点的距离和最小为目标函数对50个区域进行遍历分析，建立模型一，找出n个最优乘车点。并利用模型求出了如果设立2个乘车点则区号为18区和31区，其最短总距离为24492米。如果设立3个乘车个点则分别为15区、21区和31区，其最短总距离为19660米。对于问题2，为了表示满意度随距离的增大而减小的关系，本文建立满意度函数，然后以所有区域人员平均满意度最大为目标函数建立模型二。并依据模型求出当建立2个乘车点时最优解为区域24和32，总满意度为0.7239。当建立3个乘车点时的最优解为区域16、23和32。平均满意度为0.7811。对于问题3，本文在模型二的基础上，设立满意度最低标准，添加满意度的约束条件Hkh，建立车辆数模型。求得满意度最大的情况下的3个乘车点车辆使用情况，确定车辆最少需要54辆，三个站点所在的区域分别为2、26、31，对应的车辆数分别为12、19、23。对于问题4得出，我们结合模型对校车的安排问题提供了建议。关键词：Floyd算法；最短距离；满意度；最优解；MATLAB1问题重述许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。有效的安排车辆并让教师和工作人员尽量满意是个十分重要的问题。现有如下四个问题需要设计解决。假设老校区的教室和工作人员分布在50个区，各区的距离见附录中表1。各区人员分布见附录中表2。问题1：如果建立n个乘车点，为使各区人员到最近乘车点的距离最小，建立模型，并分别给出n2，3时的结果。问题2：考虑每个区的乘车人数，使工作人员和教室的满意度最大，建立模型，并分别建立两个和三个乘车点的校车安排方案。(假定车只在起始点载人)问题3：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车。假设每辆车最多载客47人（假设车只在起始站点载人）。问题4：关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。2问题的基本假设与说明1．假设未给出距离的两个区可以通过其他区间接到达。2．每位教师及工作人员均选择最短路径乘车。3．乘车点均建在各区内，不考虑区与区之间。4.教师及工作人员到各站点乘车的满意度与到该站点的距离有关系，距离近则满意度高，距离远则满意度低。5.假设任意时刻任意站点均有车，不考虑教师及工作人员的等车时间。6.在乘车点区内的人员乘车距离为零。7.根据实际情况，我们假设所设置的乘车点数不大于50。8.假设所有人员均乘车。9.假设每辆车只载一次人。10.假设汽车中途不再载人。11.假设每辆车的型号一致。12.假设每个乘车点的乘车人数固定不变。3符号说明4问题的分析问题1要求建立n个乘车点，使各区人员到最近乘车点的距离最小。首先结合表1，利用Floyd算法求得任意两点之间最短距离；其次在50个区域中任意选取n个区域作为乘车点，，找出每个区域所对应的最近乘车点，最后以50个区域到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立2个和3个乘车点时的校车安排问题进行求解。问题2要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的函数，然后以平均满意度最高为目标函数建立模型二，并对设立2个和3个乘车点时的校车安排问题进行求解。问题3要求建立3个乘车点，在尽量使教师和工作人员满意的前提下，所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。符号表示意义B(i,j)各个区通路的邻接矩阵B*(i,j)各个区完备图的邻接矩阵Pi第i乘车点所在的区lk第k个区到最近乘车点的距离Z50个区到各自最近乘车点的距离之和Hk第k区乘客的满意度H所有乘客的平均满意度Wi第i个乘车点的车辆数W所有乘车点的总车辆数mk第k区的人数h每个区满意度的下限（0h1）n共要建的站点数问题4中我们结合第3问的结果对车辆的安排情况提出了建议。5模型的建立与求解5.1问题1的模型建立与求解5.1.1Floyd算法简介Floyd算法是弗洛伊德（floyd）提出的一种解决每对节点之间最短路径问题的的算法。算法的基本思想：直接在图的带权邻接矩阵中，用插入顶点的方法依次构造出v个矩阵D(1)、D(2)、…、D(v),使最后得到的矩阵D(v)为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。1.在邻接矩阵G中ijG表示第i个区域到第j个区域之间的距离；2.用矩阵R来记录插入点的信息，其中ijR表示第i个区域到达第j个区域所要经过点的记录，把各个区域插入图中，比较插入区域后的距离与原来的距离，min(,)ijijikkjGGGG，如果ijG的距离变小，则ijR=k，并把最短距离记录在矩阵D中。算法完成后则R中包含了最短通路的信息，ijD中包含了最短路径的信息。关于本文具体问题的算法（算法程序见程序1）如下：1.先根据题目所给的各个连通区域之间距离的数据为初始矩阵(,)Bij赋值，其中没有给出距离的赋给无穷大，其中B(i,j)=0(i=j)。2.进行迭代计算。对任意两点(,)ij，若存在k，使(,)(,)(,)BikBkjBij，则更新(,)(,)(,)BijBikBkj。3.直到所有点的距离不再更新停止计算,则得到最短路距离矩阵B*(i,j)(,1,2,...,50)ij。5.1.2模型一的建立在上述最短路距离矩阵B*(i,j)的基础上，分析建立n个乘车点的情况：首先，在50个区域中任意选取n个区域作为乘车点nppp,...,,2150,...,2,1其次，由于每个区的乘客都选距离本区最近的乘车点乘车，引入变量kl，表示第个k区域到最近乘车点的距离),(),...,,(),,(min21nkpkBpkBpkBl（k=1,2,…50）然后，求出50个区域到各自最近乘车点的最短距离之和501kklZ最后，建立针对问题1所述的数学模型。最佳乘车点是使得50个区域到各自最近乘车点的距离之和最小的点，基于此建立目标函数min501kklZ（1）其中),(),...,,(),,(min21nkpkBpkBpkBl，nppp,...,,2150,...,2,1为选出的n个最佳乘车点所在的区域号。5.1.3模型一的求解依据模型一，利用MATLAB软件(程序见附录中程序2)求得结果如下当2n时：乘车点设立在18区和31区，各个区域到各自最近乘车点的最短距离之和为Z=24492米。选18区域有:1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、24、25、22、26、27、47。选31区域有：23、28、29、30、31、32、33、34、35、36、37、38、38、40、41、42、43、44、45、46、48、49、50。当3n时：乘车点设立在15区、21区和31区，各个区域到各自最近乘车点的最短距离之和Z=19660米。选15区域有:5、6、7、8、9、10、11、12、13、14、15、16、17、18、2425、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。由结果可看出当乘车点越多时，Z值越小。5.2问题2的模型建立与求解5.2.1建立满意度函数如果车站就建在自己的区，则乘客就非常的满意，如果离自己区最近的车站比较远，则乘客就不满意。乘客对车站点的满意度取决于自己区到最近乘车点的距离。为此我们建立满意度函数minmaxmaxllllHkk其中,maxl为第k个区离本区最远区的距离，minl为第k个区离本区最近区的距离，当然离自己区的距离最近，即0minl。化简得max1llHkk（2）Hk的值越大，满意度就越大。如果乘车点就建在自己的区,则d=0,Hk=1,该区的乘客非常满意；如果让乘客去距离本区最远的区乘车，则Hk=0,为极度不满意。5.2.2模型二的建立结合满意度函数，在模型一的基础上，建立最高满意度乘车点选择模型，由于每个区乘客的满意度不同，每个区的人数也不同，我们不可能使每个区乘客的满意度都最大，因此我们关注的是全体乘客的平均满意度H501501kkkkkmmHH为使教师和工作人员的满意度最大，为此我们将全体人的平均满意度作为目标函数Max501501kkkkkmmHH（3）5.2.3模型二的求解依据模型二，利用MATLAB软件求得结果如下（程序见附录附录中程序3）：当2n时:选择的2个乘车点为区域24和区域32，平均满意度为0.7239。选区域有36个:1、2、3、4、5、6、7、8、9、10、11、12、13、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、43、44、45、46、47、48、49、50。选区域有14个:14、30、31、32、33、34、35、36、37、38、39、40、41、42。当3n时：选择的三个乘车点为区域16、区域23和区域32。平均满意度为0.7811。选16有:1、2、25、26、27。选23有:3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、42、43、44、45、46、47、48、49。选32有:20、21、22、23、24、28、29、30、31、32、33、34、35、36、37、38、39、40、41、50。由计算结果可看出，建立车站数越多，乘客的平均满意度越高。5.3问题3的模型建立与求解5.3.1模型三的建立对所需车辆数wk的分析。设到第i个乘车点的区域的子集合为iA47ikkAiPw。（表示向上取整）（4）123min由于每个站点的人数不恰好是车辆满载乘客数的整数倍，每个站点就有可能有一辆车不能满载，所以当站点数越多，不能满载的车辆数就越多，从而导致所需车辆总数的增加。当n=1时,w=54，这也是所需车辆数的最小值。关于模型二当n=3时结出的结果，其中平均满意度是在建立3个站点的请况下最大的结果，经运算得需车辆数为56，但车辆数不是最小。在模型二中，虽然使得平均满意度最大，但个别区的满意度却相当的小，比如第三个区的满意度仅为0.4434。为了兼顾平均满意度尽可能的大、车辆数尽可能小，建立以下模型：在每个区的满意度都大于最低满意度标准的情况下，即Hkh，其中h可人为地设定且0h1，求出H的最大值，即Max501501kkkkkmmHH（5）s.t.Hkh（0h1）5.3.2模型三的求解依据模型三利用MATLAB软件求得结果如下（程序见附录附录中程序4）：当3n时,H取不同的值时，算得在平均满意度较高的几种情况下，站点、平均满意度及车辆数的情况如表1所示：表1站点、平均满意度及车辆数于是可取得在H=0.533，车辆数达到了最小值54，平均满意度为0.769，相对比较高。三个站点所在的区域分别为2、26、31，对应站点的车辆数分别为12、19、23。5.4问题四的解答通过对第三问的结果的分析可知，每个站点都存在空座的情况，所以我们H平均满意度总车辆数站点p1站点p2站点p3p1的车辆数p2的车辆数p3的车辆数0.5000.7809551823322028170.5330.769054216311219230.5470.756554723331523160.5500.746955214231017280.5700.742455192334162118建议在站点校车空座率较高的情况下时，在其他站点进行一次巡游