校车安排问题的数学模型论文

目录摘要……………………………………………………………………………………1关键词…………………………………………………………………………………11问题重述……………………………………………………………………………21.1问题背景……………………………………………………………………22问题分析……………………………………………………………………………22.1研究意义……………………………………………………………………22.2研究现状……………………………………………………………………22.3存在问题……………………………………………………………………22.4解决方法……………………………………………………………………23模型假设……………………………………………………………………………24符号约定……………………………………………………………………………35模型建立与求解……………………………………………………………………45.1计算各点间的最短路程……………………………………………………45.1.1数据分析……………………………………………………………45.1.2模型建立与计算……………………………………………………45.2建立n个乘车点使各区人员到最近乘车点的距离最小的一般模型……55.2.1模型建立……………………………………………………………55.2.2模型求解……………………………………………………………55.3考虑每个区的乘车人数建立n个乘车点使各区人员到最近乘车点的距离最小的一般模型……………………………………………………………65.3.1模型建立……………………………………………………………65.3.2模型求解……………………………………………………………65.4建立3个乘车点的车辆安排……………………………………………75.4.1建立模型……………………………………………………………75.4.2模型求解……………………………………………………………85.5建议………………………………………………………………………86模型分析与评价…………………………………………………………………97模型的推广………………………………………………………………………9参考文献……………………………………………………………………………9附录…………………………………………………………………………………101校车安排问题摘要：本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，把校车安排问题抽象成由点线构成的网络模型，将问题转化为n-重心问题的求解。在问题解决过程中使用了佛洛依德算法，分析、建模、求解过程中利用MATLAB、Excel对数据进行分析处理，并用C语言实现某些算法，最终得出结论。1.仅考虑距离因素时：设立两个乘车点时，乘车点应设在区域18和区域31；设立三个乘车点时，乘车点应设在区域15、区域21和区域31。2.综合考虑距离及教师总体满意度时：设立两个乘车点时，乘车点应设在区域19和区域32；设立三个乘车点时，乘车点应设在区域15、区域21和区域32。3.为使教师及工作人员尽量满意，至少需要安排54辆校车：其中区域15安排校车17辆；其中区域21安排校车18辆；其中区域32安排校车19辆。4.通过对问题的求解可知当乘车点适当增加时，教师及工作人员的满意度上升，可在学校条件允许的情况下在合适位置适当增加乘车点。关键词：弗洛伊德算法；总体满意度；n-重心问题。21、问题重述1.1问题背景许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。（1）、建立n个乘车点，使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪n个点。（2）、考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪n个点。（3）、建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。2、问题分析2.1研究意义许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意。2.2研究现状许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。2.3存在问题如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。由于受到车辆数目的限制，即车辆花费的限制。还有乘车点的限制。我们只能在现有的条件下合理的安排乘车点和乘车数目使教师和工作人员尽量满意。2.4解决方法老校区的50个区域的大小、形状与问题的求解无关，可将50个区域抽象为50个点，区域间的连接道路抽象为点的连线，据此建立网络模型，用佛洛依德算法求出任意两点间最短路径的距离，将问题的求解转化为n-重心问题，由模型逐步求解得到乘车点的位置。3、模型假设（1）假设老校区的教师和工作人员分布在50个区，各区的距离见附录A。各区人员分布见附录B。3校区人数分布图01020304050607080901001234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950（2）50个区域抽象成50个点，附录1中标注距离的点间可以直接相通，未标注距离的点间无法直接相通，需通过其它点间接到达。（3）假设任一教师和工作人员的满意程度随距离的增加递减（4）乘车点只设在点上。（5）校车只在起始站点载人。4、符号约定A：点间距离的邻接矩阵；B：各点的最短距离矩阵ijd:i点到j点的最短距离；kijd:i到j的只以(1..k)集合中的节点为中间结点的最短路径的距离；naaa,,,21D:各个点到乘车点的总距离；minD:最短总距离；:乘客个体满意度；d:某点到乘车点所走距离；D:所有点中到乘车点的最大距离；F:所有乘客的总体满意度；4Los：重新安排乘车点的人员安重排前所走的路程；m:某区域的教师人数；M:教师及工作人员总人数；E:距乘车点的平均路程.5、模型建立与求解5.1计算各点间的最短路程5.1.1数据分析首先对题目所给的各区距离做统计分析，用Excel表格建立对应各点距离的邻接矩阵A，即5050502501250211501211aaaaaaaaA.其中ija为点i到点j的距离。当ija=∞，表示i点和j点不直接相通。5.1.2模型建立与计算用弗洛伊德算法计算任意两点间的最短距离。弗洛伊德算法的原理是动态规划，设kijd为从i到j的只以(1..k)集合中的节点为中间结点的最短路径的长度,若最短路径经过点k，则：1-kkj1-kikkijddd若最短路径不经过点k，则：1-kijkijdd因此，有：1-kkj1-kik1-kijkijdddmind，弗洛伊德算法的C语言实现见附录E。把邻接矩阵A作为弗洛伊德算法的输入矩阵，程序输出各点间最短距离矩阵B（结果见附录C）及取最短距离时各点间的走法（结果见附录D）。55.2建立n个乘车点使各区人员到最近乘车点的距离最小的一般模型5.2.1模型建立ijd为网络中i点到j点最短路径的权，表示i，j两点的最短距离；in为网络中i点的权，表示i点的人数，因为不考虑人数对乘车点的影响，固取1in，i,j（1，50）。问题的模型为特殊情况（1in）的n-重心模型：501501miniijiijiddnf5.2.2模型求解任取n个互异点naaa,,,21为乘车点，则从各点到乘车点的总路程为：501,,,,,,nm2121iiaiaiaaaanndddiD则取50个点的组合n50C做naaa,,,21，分别计算naaaD,,,21，取使得naaaD,,,21取最小值的naaa,,,21点即为所求乘车点。即：naaaDD,,,min21min.,,,}5021{,,,2121互异，，，，nnaaaaaa取n=2，3，计算结果，算法的C语言实现见附录E。程序计算得：n=2时，求得乘车点应设在区域18和区域31；n=3时，求得乘车点应设在区域15、区域21和区域31。65.3考虑每个区的乘车人数建立n个乘车点使各区人员到最近乘车点的距离最小的一般模型5.3.1模型建立ijd为网络中i点到j点最短路径的权，表示i，j两点的最短距离；in为网络中i点的权，表示i点的人数，i，j（1，50）。问题的模型为n-重心模型：501miniijidnf假设任一教师和工作人员的满意程度随距离的增加递减，即去乘车点的距离越大越不满意，则当所有人走的总距离最短时整体的满意度最大。定义为乘客个体满意度,有：10,1Dd其中d为某点到乘车点所走距离，D为任意两点最短距离的最大值。定义F为所有乘客的总体满意度，有：MDmdF1其中m为某点的人数，M为所有教师人数。定义E为教师及工作人员至乘车点的平均路程，即：MmdE5.3.2模型求解任取n个点naaa,,,21为乘车点，所有人到乘车点的总路程为：501,,,,,,m2121iiaiiaiiaiaaanndndndninD则取50个点的组合n50C做naaa,,,21，分别计算naaaD,,,21，取使得naaaD,,,21取最小值的naaa,,,21点即为所求乘车点。即：naaaD,,,min21minD7.,,,}5021{,,,2121互异，，，，nnaaaaaa取n=2，3，计算结果，算法的C语言实现见附录E。程序计算得：n=2时，求得乘车点应设在区域19和区域32，总体满意度F=77.94%；距乘车点的平均路程E≈497。n=3时，求得乘车点应设在区域15、区域21和区域32，总体满意度F=82.70%；距乘车点的平均路程E≈390。5.4建立3个乘车点的车辆安排5.4.1建立模型此问题为n-重心问题的进一步引申，以车辆数和总体满意度为双目标函数；任取3个点321,,aaa为乘车点，所有人到乘车点的总路程为：501,,321321,,miiaiiaiiaiaaadndndninD分别找出此时到ia点距离最近的ik个点，计算这ik个点的总人数iS。（i=1，2，3）则取50个点的组合350C做321,,aaa，分别计算321,,aaaD，取使得321,,aaaD取最小值的321,,aaa点即为所求乘车点。即：321,,minmin'DaaaD对iS取余得到车载满后的剩余人员数iMod，即：47modiisMod重新安排乘车点的人员安重排前所走的路程为：31501)](min[jiaiijDModLos}3,2,1{j8重安排乘车点的人员所走的最短路径minD为：321)(min501minjjjiaaaiDModModD.3,2,1}321{3,2,1互异且，，jjjjjj重新安排后所走总路径的最小值为:LosDDDminminmin'.,,}5021{,,321321互异，，，，aaaaaa以上算法最终通过C语言程序实现。5.4.2模型求解将最短距离矩阵B作为输入数据送入程序，计算得到结果：乘车点应设在区域15，21，32；其中：15区应安排17辆车，到15区乘车的的区域有：5，6，7，8，9，10，11，12，13，14，15，16，17，18，25，26，27；21区应安排18辆车，到21区乘车的的区域有：1，2，3，4，19，20，21，22，23，24，28，44，45，46，47，48，49；32区应安排19辆车，到32区乘车的的区域有：29，32，31，32，33，34，35，36，37，38，39，40，4