《校车安排问题论文》doc版.doc

12摘要本文研究了如何合理安排车辆并让教职工满意的问题。本论文主要对学校安排校车接送教职工，校车站点建在哪些区域进行了分析研究，并建立了校车安排方案的优化数学模型。从到乘车点的距离最小，满意度最大等方面考虑，依据题目中所给条件分别建模求解。对于问题2，我们运用01变量优化模型，使用最短路程处理方法，借助Lingo软件求出最优解，从而确定出站点的位置。对于问题3，同样是运用01变量优化模型主要解决了使教职工到乘车站点的满意度最大而将站点建立在哪些区域的问题。对于问题4，根据题目的要求，为了既满足所用的车辆最少又使得教职工满意，我们尽量使得车辆满载并使得在某站点等车的教职工全部上车。对于问题5，综合考虑距离模型，满意度模型以及现实中的各种因素，我们假设它们与乘车点数、乘车点位置、校车数量等因素之间存在着关系，并根据以上分析给出校车多站点载人以及在超过25人区设立多站点再将剩余人数的乘车点优化。这两个方面对校车安排提出一些建议和考虑： 关键词：01变量优化模型、校车安排问题、分配问题、满意度一、问题重述现实中，许多学校有新老校区，教职工要往返于心老校之间，为此，学校安排校车接送教职工。校车安排的不同将直接影响着学校的经费开支和教职工的满意度。因此，校车安排问题有很大的必要性。有一学校老校区的教师和工作人员分布在5个区，各区的人数见表1。各区距离见表2。 问题2：如要建立乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个乘车点。建立一般模型，并给出时的结果。 问题3：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。建立一般模型，并给出时的结果。 问题4：若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客25人。 问题5；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。 二、问题的基本假设与说明2.1 有5个区，5个站点。 2.2 不考虑教职工在站点的等待时间。 2.3 不考虑各个站点之间路面的情况。2.4 每个区域教职工可以去多个站点。2.5 每辆车尽量装满人。2.6 每位教师及工作人员均选择最短路径乘车。2.7 每个乘车点的乘车人数固定不变。2.8 如果每个小区到每个站点的距离超过就认为不可达。三、符号说明3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.73.8四、问题的分析问题1：根据我们的实际调查大概有5个预选站点：王营校区、芙蓉园、富丽花园、北京路校区、淮海广场、枚乘路校区（终点站），每个区到各个站点的距离见表1。可以将教职工分为5个区，每个区的人数表2。问题2：建立n个乘车点，使各区人员到最近乘车点的距离最小。首先结合表2，利用0-1算法求得任意两点之间最短距离；其次在5个区中任意选取n个区域作为乘车点，找出每个区域所对应的最近乘车点，最后以5个区到各自最近乘车点的最短距离和的最小值为目标函数建立模型一。并对设立3个和4个乘车点时的校车安排问题进行求解。问题3要求在教师和工作人员的满意度最大为前提条件下选出最佳乘车点。为此需要建立关于满意度的函数，然后以平均满意度最高为目标函数建立模型二，并对设立3个和4个乘车点时的校车安排问题进行求解。问题4要求建立3个乘车点，在尽量使教师和工作人员满意的前提下，所需的车辆最少，我们利用模型二和总车辆数最少函数的双目标函数进行优化求解，得出最优解。问题5中我们结合前几问的结果对车辆的安排情况提出了建议。五、模型的建立与求解5.1问题1的调查 根据我们的实际调查大概有5个预选站点：王营校区、芙蓉园、富丽花园、北京路校区、淮海广场、枚乘路校区，其中枚乘路校区是终点站，我们不考虑。每个区到各个站点的距离见表1：站点小区123451560Inf420450Inf2200350Inf4204503Inf500280Inf5804320300640340Inf5620480350590380表1可以将教职工分为5个区，每个区的人数表2：站点小区1234512010120212081030140243111535415150总人数105205015表25.2 问题2的模型建立与求解5.2.1模型的建立如下：建立针对问题1所述的数学模型：题中要求我们从5个站点中选取个站点，我们设由题意可以得出：。又由假设可知，每一个区只能选取一个站，则我们可以得到：选取出来的站点为,同时该小区也要选取相应的站点，才能满足题意。为了保证此条件得到：。为了使目标站点的距离和最小，最佳乘车点是使得所有教职工从各自的小区到最近乘车点的距离之和最小的点，基于此建立目标函数为：解出的所对应的值，为选出的n个最佳乘车点。5.2.2求解结果：依据模型，利用Lingo软件求得结果如下（程序见附录）：当时，最佳站点为第2站点和第3站点。即是芙蓉园和富丽花园。选择芙蓉园站点的是第2个和第4个小区，选择富丽花园站点的是第1个小区、第3个小区和第5个小区。各个区到各自最近乘车点的最短距离之和。当时，最佳站点为第1站点,第3站点和第4个站点。即是王营校区, 富丽花园和淮海广场。选择王营校区站点的是第4个小区，选择富丽花园站点的是第1个和第3个小区，选择北京路校区的是第2个和第5个小区。各个区到各自最近乘车点的最短距离之和当时，最佳站点为第1站点, 第2站点，第3站点和第4个站点。即是王营校区, 芙蓉园，富丽花园和北京路校区。选择王营校区站点的是第2个小区，选择芙蓉园站点的是第4个小区, 选择富丽花园的是第3个和第5个小区。选择北京路校区站点的是第1个小区。各个区到各自最近乘车点的最短距离之和5.3 问题3的模型建立与求解5.3.1模型的建立：在模型二的基础上建立目标函数为：约束条件和模型二一样。5.3.2求解的结果：依据模型，利用Lingo软件求得结果如下（程序见附录）：当时，最佳站点为第1站点和第2站点。即是王营校区和芙蓉园。选择王营校区站点的是第2个和第3个小区，选择芙蓉园站点的是第1个小区，第4个小区和第5个小区。各个区到各自最近乘车点的最短距离之和。当时，最佳站点为第1站点,第2站点和第3个站点。即是王营校区,芙蓉园和富丽花园。选择王营校区站点的是第3个小区，选择芙蓉园站点的是第1个，第4个和第5小区,选择富丽花园的是第2个小区。各个区到各自最近乘车点的最短距离之和当时，最佳站点为第1站点, 第2站点，第3站点和第4个站点。即是王营校区, 芙蓉园，富丽花园和北京路校区。选择芙蓉园站点的是第1个，第4个和第5个小区，选择富丽花园站点的是第2个小区, 选择北京路校区站点的是第3个小区，各个区到各自最近乘车点的最短距离之和没有人在王营校区站点上车说明建立的车站点数越多，教职工的满意度越高，可以任选站点上车。 5.4 问题4的模型建立与求解5.4.1模型四的建立：由第个小区上的人数得到： =由调查可知，乘车的总人数为100人得到：由于每一个站点的实际乘载的人数要少于在该站点等候乘车的人数：又由于每一辆车的最大承载量为25人，得到：可得到结论：第一辆车经过1站点乘载10个人，经过4站点乘载15个人；第二辆车经过2站点乘载5个人， 经过4站点乘载20个人；第三辆车经过3站点乘载20个人，经过4站点乘载5个人；第四辆车经过4站点乘载10个人，经过5站点乘载15个人；所需车辆最少为四辆。5.5 问题5的解答 通过对第前几问结果的分析可知，每个站点都存在空座的情况，所以我们建议在站点校车空座率较高的情况下时，在其他站点进行一次巡游。当校车型号单一时，很容易造成某些站点乘客难以乘车而其他某些站点又大量空座的情况，这种方案最大限度的节省了资源，相当于所有乘客集中乘车，同时因为乘客依然可以在对自己满意度高的站点候车，也达到了使满意度逼近甚至达到最大的效果。六、模型的优缺点分析优点：模型结构简单，成功解决了校车调度问题，给出了较为满意的调度方案，具有一定的普适性和实用性，而且便于计算。当小区量十分庞大的时候，模型的误差变大，所以，我们考虑到对于小区量很大时，以小区量密集度（人数的多少）为决策量，选出密集度高的小区为乘车点被选区，在对乘车点被选区利用本文模型进行求解，这样使得问题变得简单化。缺点：模型的影响因素过于单一化，使得结果与实际情况有些误差。比如存在车载量未满开走或车辆等候教师及工作人员而停滞的现象。未考虑到天气（阴雨天）、时间（节假日）及每个人的具体情况。七、模型的改进及其推广改进方案：在上述模型中，为了简化问题的求解，我们做了不考虑时间的假设，但在实际情况中，由于公路堵塞、汽车故障、自然灾害等因素的影响，时间这一因素应该被考虑进去，我们应以时间为决策量，选出到小区花费时间最少的乘车点为被选区，在对乘车点被选区利用本文模型进行求解。同时我们的模型所设的乘车人数是固定不变的，但是在雨雪天气等特殊情况时，乘车的人数是改变的，相应的决策也要发生改变。八、参考文献1 苏鸣鹤.公共汽车调度管理.北京：高等教育出版社，19912 熊启才.张东升.数学模型方法及应用.重庆：重庆大学出版社，20053 秦新强.赵凤群.线性代数学习指导.北京：机械工业出版社，20064 邬学军.周凯.数学建模竞赛铺导教程.杭州：浙江大学出版社，2009附录：问题2的求解程序：min=(560*y11+200*y21+1000*y31+320*y41+620*y51)*x1+(1000*y12+350*y22+500*y32+300*y42+480*y52)*x2+(420*y13+1000*y23+280*y33+640*y43+350*y53)*x3+(350*y14+420*y24+1000*y34+340*y44+590*y54)*x4+(1000*y15+450*y25+580*y35+1000*y45+380*y55)*x5; n=2;x1+x2+x3+x4+x5=n;x1*y11+x2*y12+x3*y13+x4*y14+x5*y15=1;x1*y21+x2*y22+x3*y23+x4*y24+x5*y25=1;x1*y31+x2*y32+x3*y33+x4*y34+x5*y35=1;x1*y41+x2*y42+x3*y43+x4*y44+x5*y45=1;x1*y51+x2*y52+x3*y53+x4*y54+x5*y55=1;bin(y11);bin(y12);bin(y13);bin(y14);bin(y15);bin(y21);bin(y22);bin(y23);bin(y24);bin(y25);bin(y31);bin(y32);bin(y33);bin(y34);bin(y35);bin(y41);bin(y42);bin(y43);bin(y44);bin(y45);bin(y51);bin(y52);bin(y53);bin(y54);bin(y55);bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);解答结果：n=3Local optimal solution found. Objective value: 1500.000 Extended solver steps: 6 Total solver iterations: 51 Variable Value Reduced Cost Y11 0.000000 210.0000 Y21 1.000000 -220.0000 Y31 0.000000 0.000000 Y41 1.000000 20.00068 Y51 0.000000 30.00000 X1 1.000000 -199.9993 Y12 0.000000 0.6500000E-03 Y22 0.000000 -0.7000000E-04 Y32 0.000000 -0.5000000E-03 Y42 1.000000 0.000000 Y52 0.000000 -0.1100000E-03 X2 0.000000 0.000000 Y13 0.000000 70.00000 Y23 0.000000 580.0000 Y33 1.000000 -720.0000 Y43 0.000000 340.0007 Y53 1.000000 -240.0000 X3 1.000000 -960.0000 Y14 1.000000 0.000000 Y24 0.000000 0.000000 Y34 0.000000 0.000000 Y44 0.000000 40.00068 Y54 0.000000 0.000000 X4 1.000000 0.000000 Y15 0.000000 0.000000 Y25 0.000000 0.000000 Y35 0.000000 0.000000 Y45 0.000000 0.000000 Y55 0.000000 0.000000 X5 0.000000 0.000000 N 3.000000 0.000000n=4Local optimal solution found. Objective value: 1480.000 Extended solver steps: 6 Total solver iterations: 50 Variable Value Reduced Cost Y11 0.000000 210.0000 Y21 1.000000 -150.0000 Y31 0.000000 500.0000 Y41 0.000000 0.000000 Y51 0.000000 140.0000 X1 1.000000 -150.0000 Y12 0.000000 650.0000 Y22 0.000000 0.000000 Y32 0.000000 0.000000 Y42 1.000000 -20.00000 Y52 0.000000 0.000000 X2 1.000000 -20.00000 Y13 0.000000 70.00000 Y23 0.000000 650.0000 Y33 1.000000 -220.0000 Y43 0.000000 320.0000 Y53 1.000000 -130.0000 X3 1.000000 -350.0000 Y14 1.000000 0.000000 Y24 0.000000 70.00000 Y34 0.000000 500.0000 Y44 0.000000 20.00000 Y54 0.000000 110.0000 X4 1.000000 0.000000 Y15 0.000000 0.000000 Y25 0.000000 0.000000 Y35 0.000000 0.000000 Y45 0.000000 0.000000 Y55 0.000000 0.000000 X5 0.000000 0.000000 N 4.000000 0.000000问题3的求解程序：min=(560*y11*2+200*y21*1+1000*y31*0+320*y41*3+620*y51*4)*x1+(1000*y12*0+350*y22*2+500*y32*1+300*y42*1+480*y52*1)*x2+(420*y13*10+1000*y23*0+280*y33*4+640*y43*1+350*y53*5)*x3+(350*y14*12+420*y24*8+1000*y34*0+340*y44*15+590*y54*15)*x4+(1000*y15*0+450*y25*10+580*y35*2+1000*y45*3+380*y55*0)*x5; n=3;x1+x2+x3+x4+x5=n;x1*y11+x2*y12+x3*y13+x4*y14+x5*y15=1;x1*y21+x2*y22+x3*y23+x4*y24+x5*y25=1;x1*y31+x2*y32+x3*y33+x4*y34+x5*y35=1;x1*y41+x2*y42+x3*y43+x4*y44+x5*y45=1;x1*y51+x2*y52+x3*y53+x4*y54+x5*y55=1;bin(y11);bin(y12);bin(y13);bin(y14);bin(y15);bin(y21);bin(y22);bin(y23);bin(y24);bin(y25);bin(y31);bin(y32);bin(y33);bin(y34);bin(y35);bin(y41);bin(y42);bin(y43);bin(y44);bin(y45);bin(y51);bin(y52);bin(y53);bin(y54);bin(y55);bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);解答结果：n=3Local optimal solution found. Objective value: 780.0000 Extended solver steps: 10 Total solver iterations: 73 Variable Value Reduced Cost Y11 0.000000 1120.000 Y21 0.000000 200.0000 Y31 1.000000 -500.0000 Y41 0.000000 320.0000 Y51 0.000000 2000.000 X1 1.000000 -500.0000 Y12 1.000000 0.000000 Y22 0.000000 700.0000 Y32 0.000000 0.000000 Y42 1.000000 -340.0000 Y52 1.000000 0.000000 X2 1.000000 -340.0000 Y13 0.000000 4200.000 Y23 1.000000 0.000000 Y33 0.000000 620.0000 Y43 0.000000 0.000000 Y53 0.000000 1270.000 X3 1.000000 0.000000 Y14 0.000000 0.000000 Y24 0.000000 0.000000 Y34 0.000000 0.000000 Y44 0.000000 0.000000 Y54 0.000000 0.000000 X4 0.000000 0.000000 Y15 0.000000 0.000000 Y25 0.000000 0.000000 Y35 0.000000 0.000000 Y45 0.000000 0.000000 Y55 0.000000