校车安排问题.doc

校车安排问题一、 摘要本论文主要对学校安排校车接送教职工，校车站点建在哪些区域进行了分析研究，并建立了校车安排方案的优化数学模型。从乘车点的距离最小，满意度最大又可节省运行成本等方面考虑，依据题目中所给条件分别建模求解。对于问题一，我们运用01变量优化模型，使用最短路程处理方法，借助MATLAB软件的优化工具箱找出最优划分方法，从而确定出站点的位置；当n2时将站点建立在18、31区，当n3时将站点建立在15、21、31区。对于问题二，同样是运用01变量优化模型和matlab的优化工具箱主要解决了使教职工到乘车站点的满意度最大而将站点建立在哪些区域的问题。得出当n2时满意度为7.7089，将站点建立在19、32区，当n3时满意度为9.6391，将站点建立在15、21、32区。对于问题三，在问题二n3的基础上整合至各乘车点的总人数计算出使教职工满意度最大而运行成本最小时的车辆安排数（每台车辆的载人数限定）得出在15、21、32区各派17、19、18辆校车的最优方案。对于问题四，综合考虑距离模型，满意度模型，运营成本以及现实中的各种因素，我们假设它们与乘车点数、乘车点位置、校车数等因素之间存在着关系，并根据以上分析给出1、校车多站点载人。2、在超过47人区设立多站点再将剩余人数的乘车点优化。这两个方面对校车安排提出一些建议和考虑： 关键词：01变量优化模型、校车安排问题、分配问题、matlab优化、满意度二、 问题重述现实中，许多学校有新老校区，教职工要往返于心老校之间，为此，学校安排校车接送教职工。校车安排的不同将直接影响着学校的经费开支和教职工的满意度。因此，校车安排问题有很大的必要性。有一学校老校区的教师和工作人员分布在50个区，各区的距离见表1。各区人员分布见表2。 问题1：如要建立 个乘车点，为使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪 个点。建立一般模型，并给出 时的结果。 问题2：若考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪 个点。建立一般模型，并给出 时的结果。 问题3 若建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。 问题4；关于校车安排问题，你还有什么好的建议和考虑。可以提高乘车人员的满意度，又可节省运行成本。 三、模型假设3.1 站点按站点序列号依次排列。 3.2 不考虑教职工在站点的等待时间。 3.3不考虑各个站点之间路面的情况，在我们的模型中，我们忽略现实中的道路状况不同所带来的影响，假设路面情况是一样的。3.4假设每个区域教职工只能去一个固定的站点。3.5假设每个区域去本区域乘车点的满意度为1。3.6假设每个区域去本区域乘车点的距离为0。3.7假设每辆车尽量装满人。四、符号说明4.1 问题一中表示是否分配i区域的人员去j区域乘车4.2 问题一中表示是否在第j区域设立乘车点4.3 n 表示问题一中设立的乘车点数4.4 问题二中表示是否分配i区域的人员去j区域乘车4.5 问题二中表示是否在第j区域设立乘车点4.6 m 表示问题而中设立的乘车点数4.7 问题一中表示i区域到j区域乘车的最短距离4.8 问题一中表示各个区域去各自乘车区域的区域最短总距离4.9 问题二中表示i区域所有人到j区域乘车的最短总距离4.10 问题二中表示各个区域的所有人去各自乘车区域的所有人的最短总距离4.11 问题一中表示是否在第j区域设立乘车点4.12 问题三中表示去各个乘车点的人数4.13 各个乘车点所需最少的车辆数五、问题分析本题主要解决教职工到乘车站点的满意度，在假设基础上分析和解决问题，是满意度最大，就必须将站点建立在最优的区域内。我们在假设条件下，引进01变量建立优化模型，并设计程序用matlab优化工具箱求解。在第一个问题中，我们建立01变量优化模型运用最短路程的思想求解出最小距离的n个乘车站点。问题二则是在问题一的基础上计算出所有各区人员乘以各区距离的总距离矩阵，并设计程序用各区域人员至乘车点的最小距离来表示满意度最大，通过求解出建立站点的区域做进一步处理得出其满意度。问题三则是在问题二n3的基础上算出至各乘车站点的乘车区域的人数，进而可得出各个站点的校车数量。问题四则是拓展思维，提出即提高乘车人员满意度又节约运行成本的关于校车的建议。六、模型分析、建立、求解6. 1.1问题一模型分析和建立问题一要求的是各区人员到最近乘车点的距离最小，并且一个区域的人员只能去一个乘车点。由各方面的约束条件，则建立优化模型。优化模型由三个部分组成，决策变量、约束条件和变量范围。从上面问题分析和模型假设：来分步建立模型。第一步设立决策变量：设1,分配i区域的人员去j区域乘车0 ，否则1，表明在第j区域设立乘车点0， 否则第二步确立目标函数第三步写出约束条件 设立n个乘车点 （i1，50） 每一个区域的人员只能去同一个乘车点 （i1，50；j1，50） 区域人员只去有乘车点的区域最后一步确定变量的范围 （i1，50；j1，50）6. 1.2问题一模型求解及结果分析考虑到每个区按距离车站的远近选择车站，根据01规划原理，建立01规划模型，用matlab优化工具箱找出建立站点的最优方法。编程序求出各区之间的最短距离，建立5050矩阵。依据matlab对矩阵的强大操作能力运用bintprog命令，对于n（n2或3）个乘车点，列举出到n个所建立乘车站点的各个区域，建立一个只包含0和1的矩阵；对于每个所选站点，既是经过优化处理的所求的所有区的乘车最小距离。（程序及最后输出结果见附页。）结果为：n=2：乘车点建立在18，31区域 距离为：24492 至18乘车点的区域为：121、2427、47区至31乘车点的区域为：22、23、2846、48、49、50区 n=3：乘车点建立在1，21，31区域 距离为：19660至15乘车点的区域为：618、2527区至21乘车点的区域为：14、1924、4449区至31乘车点的区域为：2843、50区62.1问题二模型分析与建立问题二主要是要考虑人员的满意度，而总的满意度跟所有走的总距离成反比，总距离最小则满意度就最高。同时在最短总距离算出来的情况下可以求出一个满意度。首先建立总距离最小的模型：第一步设立决策变量：设1,分配i区域所有的人员去j区域乘车0 ，否则1，表明在第j区域设立乘车点 0，否则第二步确立目标函数第三步写出约束条件 设立m个乘车点 （i1，50） 每一个区域的人员只能去同一个乘车点 （i1，50；j1，50） 区域人员只去有乘车点的区域最后一步确定变量的范围 （i1，50；j1，50）此时建立满意度函数 同时定义区域去自己区域的满意度为1，最后加总每个区域的满意度，为总的满意度。62.2问题二模型求解及结果分析问题二的模型同问题一的思路基本上是一致的，同样是用matlab优化工具箱找出建立站点的最优方法。只是问题二要解决的是使教职工到乘车站点的满意度最大而建立的站点区域，又因为使所有教职工的满意度最大也就是使所有区域的人员步行至车站的总距离最小，即依据总距离最小也就是满意度最大的思路来建立使教职工满意度最大的乘车站点。考虑到各区人数的不同，首先将问题一建立的最小距离矩阵中的各区之间的最小距离乘上各区人数，建立综合考虑人数与最短路径的区间的总满意度矩阵，对矩阵进行操作，求解01整数规划模型，优化处理了当n为2或3时各个区域所有人员到乘车点总距离最短，也就是满意度最大时站点的建立位置。运用matlab编程求出最大满意度，进而得出满意度模型对应的选站方案。（程序及最后输出结果见附页。）结果为：n=2：乘车点建立在19，31区域 距离为：1.2429e+006至19乘车点的区域为：128、44、4649区至32乘车点的区域为：13、2943、45、50区 n=3：乘车点建立在1，21，31区域 距离为：972800至15乘车点的区域为：518、2527区至21乘车点的区域为：14、1924、28、4349区至32乘车点的区域为：2942、50区满意度的求解：路径到19人数距离满意度 路径到32人数距离满意度X1,19659500.068421053X13,32668000.0825X2,19675500.121818182X29,32294200.069047619X3,19429100.046153846X30,32754700.159574468X4,19343100.109677419X31,32102300.043478261X5,19385200.073076923X32,328601X6,19296840.042397661X33,32701900.368421053X7,19173640.046703297X34,32564000.14X8,19645340.119850187X35,32651400.464285714X9,19397340.053133515X36,32262400.108333333X10,19206640.030120482X37,32803000.266666667X11,19618140.074938575X38,32904350.206896552X12,19479540.049266247X39,32474200.111904762X13,192111540.018197574X40,32404300.093023256X14,19706940.100864553X41,32575700.1X15,19855040.168650794X42,32406000.066666667X16,19123340.035928144X43,32696800.101470588X17,19354740.073839662X45,32208900.02247191X18,19482040.235294118X50,32624400.140909091X19,195401X20,19491400.35X21,19123200.0375X22,19546200.087096774X23,19464150.110843373X24,19761750.434285714X25,19163450.046376812X26,19946350.148031496X27,19184950.036363636X28,19673050.219672131X44,19185650.031858407X45,19208900.02247191X46,196810800.062962963X47,19726700.107462687满意度4.1632581353.54564994总满意度7.708908076表1：m2的满意度满意度的求解在excel表中计算出来的，从表1以得出 路径（到15）人数距离满意度路径(到21)人数距离满意度路径（到32）人数距离满意度X5,15386550.058015267X1,21656300.103174603X29,32294200.06904762X6,15296250.0464X2,21672300.291304348X30,33754700.15957447X7,15174550.037362637X3,214210800.038888889X31,32102300.04347826X8,15642850.224561404X4,21345300.064150943X32,328601X9,15393400.114705882X19,21483200.15X33,32701900.36842105X10,15201600.125X20,21541800.3X34,32564000.14X11,15613100.196774194X21,214901X35,32651400.46428571X12,15474500.104444444X22,21123000.04X36,32262400.10833333X13,15666500.101538462X23,21542700.2X37,32803000.26666667X14,15211900.110526316X24,21463700.124324324X38,32904350.20689655X15,157001X28,21185000.036X39,32474200.11190476X16,15851700.5X43,21696800.101470588X40,32404300.09302326X17,15122500.048X44,21674200.15952381X41,32575700.1X18,15353000.116666667X45,21205700.035087719X42,32406000.06666667X25,15764800.158333333X46,21187600.023684211X50,32624400.14090909X26,15163800.042105263X47,21683500.194285714X27,15944900.191836735X48,21724800.15X49,21766800.111764706满意度3.1762706043.1236598553.33920744总满意度9.6391379表2：3的满意度满意度的求解在excel表中计算出来的，从表可以得出 63.1问题三模型分析与建立模型求解及结果分析考虑到每个人都会选择离自己最近的乘车点，故我们以满意度最大，距离最小为目标，根据问题二得出的每个区的选乘地点算出至固定选乘地点的乘车人数再除以车辆的限载人数即可得出所需的车辆数，因此此种方案下的满意度是固定的。路径（到站点15）人数路径(到21)人数路径（到32）人数X5,1538X1,2165X29,3229X6,1529X2,2167X30，3275X7,1517X3,2142X31,3210X8,1564X4,2134X32,3286X9,1539X19,2148X33,3270X10,1520X20,2154X34,3256X11,1561X21,2149X35,3265X12,1547X22,2112X36,3226X13,1566X23,2154X37,3280X14,1521X24,2146X38,3290X15,1570X28,2118X39,3247X16,1585X43,2169X40,3240X17,1512X44,2167X41,3257X18,1535X45,2120X42,3240X25,1576X46,2118X50,3262X26,1516X47,2168X27,1594X48,2172X49,2176总人数站点乘车人数7908798332502站点车辆数16.81018.7017.753.23404问题三是建立3个乘车点，并使教职员工尽量满意。则可以借用问题二中m3的结论。从表可以得出去每个乘车点的总人数（用表示）。然后用除以每辆车载客最多的人数（47）。得出每个乘车点所需最少的车辆数（用表示）。790； 879； 833； ；最后应取17；应取19；应取18，总共需要54辆校车。如果所有人在一个站点乘车，总人数有2502人，则至少需车辆，最后取54。这个结果是车辆用得最少的方案，也是成本最低的方案。所以我们第三问算出来的结果也是成本最少的，我们既达到了满意度高也达到了成本低的要求。64.1问题四模型分析与建立问题四是针对提高乘车人员的满意度并节省运行成本等关于校车安排问题提出一些建议和考虑。仔细分析了有可能影响满意度和成本的因素，综合考虑距离模型，满意度模型，运营成本以及现实中的各种因素，我们假设它们与乘车点数、乘车点位置、校车数等因素之间存在着关系，根据以上分析我们给出校车安排的一些建议：建议一：我们的校车站点模型建立是从一开始就假定车只在起始点载人，比如我们的问题二的最优化模型解出在15，21，32区域建立站点，车就只能在这三个站点载人。而若要提高教职工的满意度，本质上就应减少教职工从居住区域至乘车站点的路程，若我们安排校车除了在起始点载人外还可中途在一些区域停车载人，则会减少教职工的乘车距离路程，也就是提高了满意度。不置可否，校车在中途经停，必然会增加行驶路程，增加燃油消耗量，因此也就提高了成本，但是我们可以寻求经停站点与成本提高之间的平衡，也就是通过多目标规划寻求最优值。建议二：在以上的模型建立中，我们只是考虑了在固定站点设置n的条件下使教职工至乘车站点距离最小的情况，且n2或3时站点的设置区太少，每一站点的设置区集中了较多的校车，增加了教职工从所在区域至乘车站点之间路程，如：从问题三的解答中，我们可以看出15、21、32三个站点设置区域的校车分别为17、19、18辆。我们观察各区人员分布表，可以看出区域1、2、8、11、12、13等较多地方都超过了一辆校车的限载人数47人，通过思考，我们可以在超过校车限载人数的区域都安排一辆校车，而该区域超过47的人数和不足47教职工的区域再建立模型，重新安排使其到乘车区域路程最小的乘车点，以此来减少运营成本和提高教职工的满意度。 七、模型评价7.1模型优点：首先，我们在研究校车安排问题时，建立起了0-1变量优化模型，在这个模型中我们既采用0、1变量，又运用了优化的思想。用优化的思想，一步一步地讨论了模型的建立情况，使所建立的模型最大限度的接近实际问题，此模型具有很强的实用性。7.2模型缺点：我们采用matlab优化工具箱编写程序，以期求出最优解，但在求解最优解的过程数据导入繁琐，要浪费大量时间，且容易出错。对现实中的一些特殊情况进行了简化处理，与现实稍有偏颇。在问题三模型建立过程中，是在满意度高的情况下求解出来的结果来检验运费最小的。并没有建立多目标规划模型。八、模型推广这篇论文建立的模型以0-1变量的优化模型为主，此类模型应用性比较广，对于在n个地方建立多少个站点达到最优，此类问题都可以解决。还有分配问题，整数规划问题都可以解决。参考文献：1胡运权等。运筹学基础及应用。高等教育出版社。2姜启源，谢金星，叶俊。数学模型。高等教育出版社。3张志涌，杨祖樱等。Matlab教程。北京航空航天大学出版社。4王文波，数学建模及其基础知识详解。武汉大学出版社。附录问题一的程序：当n=2时Matlab程序距离矩阵的建立a=;for i=1:50 for j=1:50 if (i=1&j=2) a(i,j)=400; elseif (i=1&j=3) a(i,j)=450; elseif (i=2&j=4) a(i,j)=300; elseif (i=2&j=21) a(i,j)=230; elseif (i=2&j=47) a(i,j)=140; elseif (i=3&j=4) a(i,j)=600; elseif (i=4&j=5) a(i,j)=210; elseif (i=4&j=19) a(i,j)=310; elseif (i=5&j=6) a(i,j)=230; elseif (i=5&j=7) a(i,j)=200; elseif (i=6&j=7) a(i,j)=320; elseif (i=6&j=8) a(i,j)=340; elseif (i=7&j=8) a(i,j)=170; elseif (i=7&j=18) a(i,j)=160; elseif (i=8&j=9) a(i,j)=200; elseif (i=8&j=15) a(i,j)=285; elseif (i=9&j=10) a(i,j)=180; elseif (i=10&j=11) a(i,j)=150; elseif (i=10&j=15) a(i,j)=160; elseif (i=11&j=12) a(i,j)=140; elseif (i=11&j=14) a(i,j)=130; elseif (i=12&j=13) a(i,j)=200; elseif (i=13&j=34) a(i,j)=400; elseif (i=14&j=15) a(i,j)=190; elseif (i=14&j=26) a(i,j)=190; elseif (i=15&j=16) a(i,j)=170; elseif (i=15&j=17) a(i,j)=250; elseif (i=16&j=17) a(i,j)=140; elseif (i=16&j=18) a(i,j)=130; elseif (i=17&j=27) a(i,j)=240; elseif (i=18&j=19) a(i,j)=204; elseif (i=18&j=25) a(i,j)=180; elseif (i=19&j=20) a(i,j)=140; elseif (i=19&j=24) a(i,j)=175; elseif (i=20&j=21) a(i,j)=180; elseif (i=20&j=24) a(i,j)=190; elseif (i=21&j=22) a(i,j)=300; elseif (i=21&j=23) a(i,j)=270; elseif (i=21&j=47) a(i,j)=350; elseif (i=22&j=44) a(i,j)=160; elseif (i=22&j=45) a(i,j)=270; elseif (i=22&j=48) a(i,j)=180; elseif (i=23&j=24) a(i,j)=240; elseif (i=23&j=29) a(i,j)=210; elseif (i=23&j=30) a(i,j)=290; elseif (i=23&j=44) a(i,j)=150; elseif (i=24&j=25) a(i,j)=170; elseif (i=24&j=28) a(i,j)=130; elseif (i=26&j=27) a(i,j)=140; elseif (i=26&j=34) a(i,j)=320; elseif (i=27&j=28) a(i,j)=190; elseif (i=28&j=29) a(i,j)=260; elseif (i=29&j=31) a(i,j)=190; elseif (i=30&j=31) a(i,j)=240; elseif (i=30&j=42) a(i,j)=130; elseif (i=30&j=43) a(i,j)=210; elseif (i=31&j=32) a(i,j)=230; elseif (i=31&j=36) a(i,j)=260; elseif (i=31&j=50) a(i,j)=210; elseif (i=32&j=33) a(i,j)=190; elseif (i=32&j=35) a(i,j)=140; elseif (i=32&j=36) a(i,j)=240; elseif (i=33&j=34) a(i,j)=210; elseif (i=35&j=37) a(i,j)=160; elseif (i=36&j=39) a(i,j)=180; elseif (i=36&j=40) a(i,j)=190; elseif (i=37&j=38) a(i,j)=135; elseif (i=38&j=39) a(i,j)=130; elseif (i=39&j=41) a(i,j)=310; elseif (i=40&j=41) a(i,j)=140; elseif (i=40&j=50) a(i,j)=190; elseif (i=42&j=50) a(i,j)=200; elseif (i=43&j=44) a(i,j)=260; elseif (i=43&j=45) a(i,j)=210; elseif (i=45&j=46) a(i,j)=240; elseif (i=46&j=48) a(i,j)=280; elseif (i=48&j=49) a(i,j)=200; elseif i=j a(i,j)=0; else a(i,j)=inf; end end endt=triu(a);r=t;c=t+r;建立计算最短距离的函数文件function D,R=floyd(a)% D,R=floyd(a)% Floyd算法求最短路径，输入矩阵a为各点的带权邻接矩阵，Inf表示两点不通。% 输出矩阵D为各点间最短距离，矩阵R为最短路径。n=size(a,1); D=a; for i=1:n for j=1:n Ri,j=num2str(i), num2str(j); end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); l=length(Ri,k)-length(num2str(k);Ri,j=Ri,k(1:l),Rk,j; end end endend调用函数文件并把矩阵用向量C形式输出D,R=floyd(a)for num = 1: 50eval(f,num2str(num),=,D(num,:);endC=f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 f17 f18 f19 f20 f21 f22 f23 f24 f25 f26 f27 f28 f29 f30 f31 f32 f33 f34 f35 f36 f37 f38 f39 f40 f41 f42 f43 f44 f45 f46 f47 f48 f49 f50;建立优化模型中等式和不等式约束的系数A=zeros(2500,2500);for i=1:50 for j=1:50 m=j+50*(i-1);n=j+50*(j-1); A(m,m)=1;A(m,n)=-1; endendfor k=1:50 s=k+50*(k-1); A(s,:)=0;end b=zeros(2500,1);aeq=zeros(51,2500);for i=1:50 for j=1:50 aeq(i,50*(i-1)+j)=1; endendfor k=1:50 aeq(51,k+50*(k-1)=1;endbeq=ones(1,51);beq(1,51)=2;调用bintprog函数求解优化方程 x,fval=bintprog(C,A,b,aeq,beq);对输出的结果进行处理，最后以矩阵的形式输出x=x;x1=x(1:50);x2=x(51:100);x3=x(101:150);x4=x(151:200);x5=x(201:250);x6=x(251:300);x7=x(301:350);x8=x(351:400);x9=x(401:450);x10=x(451:500);x11=x(501:550);x12=x(551:600);x13=x(601:650);x14=x(651:700);x15=x(701:750);x16=x(751:800);x17=x(801:850);x18=x(851:900);x19=x(901:950);x20=x(951:1000);x21=x(1001:1050);x22=x(1051:1100);x23=x(1101:1150);x24=x(1151:1200);x25=x(1201:1250);x26=x(1251:1300);x27=x(1301:1350);x28=x(1351:1400);x29=x(1401:1450);x30=x(1451:1500);x31=x(1501:1550);x32=x(1551:1600);x33=x(1601:1650);x34=x(1651:1700);x35=x(1701:1750);x36=x(1751:1800);x37=x(1801:1850);x38=x(1851:1900);x39=x(1901:1950);x40=x(1951:2000);x41=x(2001:2050);x42=x(2051:2100);x43=x(2101:2150);x44=x(2151:2200);x45=x(2201:2250);x46=x(2251:2300);x47=x(2301:2350);x48=x(2351:2400);x49=x(2401:2450);x50=x(2451:2500);x=x1;x2;x3;x4;x5;x6;x7;x8;x9;x10;x11;x12;x13;x14;x15;x16;x17;x18;x19;x20;x21;x22;x23;x24;x25;x26;x27;x28;x29;x30;x31;x32;x33;x34;x35;x36;x37;x38;x39;x40;x41;x42;x43;x44;x45;x46;x47;x48;x49;x50;结果18、31列x的值，其余列为01010101010101010101010101010101010101010100101101010100101010101010101010101010101010101010110010101当n=3时程序和n2时基本一样；只有n值不一样。运行结果如下：15、21、31列x的值，其余列为0010010010010100100100100100100100100100100100100100100010010010010010010100100100001001001001001001001001001001001001001001001001010010010010010010001问题二的matlab程序：当n=2时矩阵D运用第一问的运行结果，然后建立所有人的最短距离矩阵，并用向量C的形式输出h=65 67 42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 48 54 49 12 54 46 76 16 94 18 29 75 10 86 70 56 65 26 80 90 47 40 57 40 69 67 20 18 68 72 76 62;E=diag(h);g=E*D;for num = 1: 50eval(f,num2str(num),=,g(num,:);endC=f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 f17 f18 f19 f20 f21 f22 f23 f24 f25 f26 f27 f28 f29 f30 f31 f32 f33 f34 f35 f36 f37 f38 f39 f40 f41 f42 f43 f44 f45 f46 f47 f48 f49 f50;建立优化模型中等式和不等式约束的系数A=zeros(2500,2500);for i=1:50 for j=1:50 m=j+50*(i-1);n=j+50*(j-1); A(m,m)=1;A(m,n)=-1; endendf