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

重庆科技学院课程论文 题 目 校车安排问题 院 （系） 专业班级 学生姓名 学号 指导教师 职称 评阅教师 职称 2012年 1 月 2 日目 录摘要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建立个乘车点使各区人员到最近乘车点的距离最小的一般模型55.2.1 模型建立55.2.2 模型求解55.3 考虑每个区的乘车人数建立个乘车点使各区人员到最近乘车点的距离最小的一般模型 65.3.1 模型建立65.3.2 模型求解65.4 建立3个乘车点的车辆安排 75.4.1 建立模型75.4.2 模型求解85.5 建议 86模型分析与评价 97模型的推广 9参考文献 9附录10摘要：本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，把校车安排问题抽象成由点线构成的网络模型，将问题转化为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-重心问题。1、问题重述1.1问题背景许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。（1）、建立个乘车点，使各区人员到最近乘车点的距离最小，该将校车乘车点应建立在哪个点。（2）、考虑每个区的乘车人数，为使教师和工作人员满意度最大，该将校车乘车点应建立在哪个点。 （3）、建立3个乘车点，为使教师和工作人员尽量满意，至少需要安排多少辆车？给出每个乘车点的位置和车辆数。设每辆车最多载客47人。2、问题分析2.1研究意义许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于每天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽量满意。2.2研究现状许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。2.3存在问题如何有效的安排车辆及让教师和工作人员尽量满意是个十分重要的问题。由于受到车辆数目的限制，即车辆花费的限制。还有乘车点的限制。我们只能在现有的条件下合理的安排乘车点和乘车数目使教师和工作人员尽量满意。2.4解决方法老校区的50个区域的大小、形状与问题的求解无关，可将50个区域抽象为50个点，区域间的连接道路抽象为点的连线，据此建立网络模型，用佛洛依德算法求出任意两点间最短路径的距离，将问题的求解转化为n-重心问题，由模型逐步求解得到乘车点的位置。3、模型假设（1）假设老校区的教师和工作人员分布在50个区，各区的距离见附录A。各区人员分布见附录B。（2）50个区域抽象成50个点，附录1中标注距离的点间可以直接相通，未标注距离的点间无法直接相通，需通过其它点间接到达。（3）假设任一教师和工作人员的满意程度随距离的增加递减（4）乘车点只设在点上。（5）校车只在起始站点载人。4、符号约定A：点间距离的邻接矩阵；B：各点的最短距离矩阵:i点到j点的最短距离；:i到j的只以(1.k)集合中的节点为中间结点的最短路径的距离；:各个点到乘车点的总距离；:最短总距离；:乘客个体满意度；:某点到乘车点所走距离；:所有点中到乘车点的最大距离；:所有乘客的总体满意度；：重新安排乘车点的人员安重排前所走的路程；:某区域的教师人数；:教师及工作人员总人数；: 距乘车点的平均路程.5、模型建立与求解5.1计算各点间的最短路程5.1.1 数据分析首先对题目所给的各区距离做统计分析，用Excel表格建立对应各点距离的邻接矩阵A，即.其中为点i到点j的距离。当=，表示i点和j点不直接相通。5.1.2 模型建立与计算用弗洛伊德算法计算任意两点间的最短距离。弗洛伊德算法的原理是动态规划，设为从i到j的只以(1.k)集合中的节点为中间结点的最短路径的长度, 若最短路径经过点k，则：若最短路径不经过点k，则：因此，有：弗洛伊德算法的C语言实现见附录E。把邻接矩阵A作为弗洛伊德算法的输入矩阵，程序输出各点间最短距离矩阵B（结果见附录C）及取最短距离时各点间的走法（结果见附录D）。5.2建立个乘车点使各区人员到最近乘车点的距离最小的一般模型5.2.1 模型建立为网络中i点到j点最短路径的权，表示i，j两点的最短距离；为网络中i点的权，表示i点的人数，因为不考虑人数对乘车点的影响，固取，i,j（1，50）。问题的模型为特殊情况（）的n-重心模型：5.2.2 模型求解任取n个互异点为乘车点，则从各点到乘车点的总路程为：则取50个点的组合做，分别计算，取使得取最小值的点即为所求乘车点。即：取n=2，3，计算结果，算法的C语言实现见附录E。程序计算得：n=2时，求得乘车点应设在区域18和区域31；n=3时，求得乘车点应设在区域15、区域21和区域31。5.3 考虑每个区的乘车人数建立个乘车点使各区人员到最近乘车点的距离最小的一般模型5.3.1 模型建立为网络中i点到j点最短路径的权，表示i，j两点的最短距离；为网络中i点的权，表示i点的人数，i，j（1，50）。问题的模型为n-重心模型：假设任一教师和工作人员的满意程度随距离的增加递减，即去乘车点的距离越大越不满意，则当所有人走的总距离最短时整体的满意度最大。定义为乘客个体满意度,有：其中d为某点到乘车点所走距离，D为任意两点最短距离的最大值。定义F为所有乘客的总体满意度，有：其中m为某点的人数，M为所有教师人数。定义E为教师及工作人员至乘车点的平均路程，即：5.3.2 模型求解任取n个点为乘车点，所有人到乘车点的总路程为：则取50个点的组合做，分别计算，取使得取最小值的点即为所求乘车点。即：取n=2，3，计算结果，算法的C语言实现见附录E。程序计算得：n=2时，求得乘车点应设在区域19和区域32，总体满意度F=77.94%；距乘车点的平均路程E497。n=3时，求得乘车点应设在区域15、区域21和区域32，总体满意度F=82.70%；距乘车点的平均路程E390。5.4 建立3个乘车点的车辆安排5.4.1 建立模型此问题为n-重心问题的进一步引申，以车辆数和总体满意度为双目标函数；任取3个点为乘车点，所有人到乘车点的总路程为：分别找出此时到点距离最近的个点，计算这个点的总人数。（i=1，2，3）则取50个点的组合做，分别计算，取使得取最小值的点即为所求乘车点。即：对取余得到车载满后的剩余人员数，即：重新安排乘车点的人员安重排前所走的路程为：重安排乘车点的人员所走的最短路径为：重新安排后所走总路径的最小值为:以上算法最终通过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，41，42，43，50.总体满意度F=82.48%。总体满意度较4.3中的82.70%略有下降。5.5 建议定义为成本增加率，有：其中为总车辆数，增加的车辆数。计算得由4.3和4.3的用车数据算得，即提高0.22%的满意度增加了1.89%的成本，不划算。由4.3，4.4及以上的结论可知适当增加乘车点数能增加教师和工作人员的总体满意度。而减少校车数量与增加总体满意度相矛盾。因此，在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题，在条件允许的范围内尽量增加乘车点以提高总体满意度。6、模型的分析与评价本文就高校校车运行问题建立网络模型，进而转化为网络最短路径问题的求解及n-重心问题的求解，具有一定的科学性。但因某些实际因素（如满意度等）不能直接运用求解，而作了一定的理想化假设，所得结果与实际问题会存在一定偏差，需要通过与实际情况的比较进一步修正模型。7、模型的推广由模型的求解结果可以看出适当增加乘车点数能降低平均步行距离、增加教师和工作人员的总体满意度。而减少校车数量与增加总体满意度相矛盾。因此，在校车安排时应综合考虑教师的满意度和增加校车与乘车点的成本问题，在条件允许的范围内尽量提高总体满意度。参考文献：1数学模型编写组.数学模型.广州：华南理工大学出版社，2003.2湖北省大学生数学建模竞赛专组:数学建模（本科册）.华中科技大学出版社，2006.3王树禾.图论.科学出版社.2005.4唐坤.车辆路径问题中的遗传算法设计.华东大学学报，2002.5宁正元,王秀丽.算法与数据结构.清华大学出版社，2006年1月，第1版.附录A： 各区距离表区域号区域号距离(m)区域号区域号距离(m)区域号区域号距离(m)1240015172502931190134501617140303124024300161813030421302212301727240304321024714018192043132230346001825180313626045210192014031502104193101924175323319056230202118032351405720020241903236240673202122300333421068340212327035371607817021473503639180718160224416036401908920022452703738135815285224818038391309101802324240394131010111502329210404114010151602330290405019011121402344150425020011141302425170434426012132002428130434521013344002627140454624014151902634320464828014261902728190484920015161702829260附录B：各区人员分布区域人数区域人数16526162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436919484467205445202149461822124768235448722446497625765062附录C：用存储的点间最短距离矩阵备注：（x，y）处的值为x区域到y区域的最短距离附录D：各点间取最短距离的走法（因篇幅有限仅列出以1点为出发点的路径）目的地最短路径21-231-341-2-451-2-4-561-2-4-5-671-2-4-5-781-2-4-5-7-891-2-4-5-7-8-9101-2-21-20-19-18-16-15-10111-2-21-20-19-18-16-15-10-11121-2-21-20-19-18-16-15-10-11-12131-2-21-20-19-18-16-15-10-11-12-13141-2-21-20-19-18-16-15-14151-2-21-20-19-18-16-15161-2-21-20-19-18-16171-2-21-20-19-18-16-17181-2-21-20-19-18191-2-21-20-19201-2-21-20211-2-21221-2-21-22231-2-21-23241-2-21-20-24251-2-21-20-24-25261-2-21-20-24-28-27-26271-2-21-20-24-28-27281-2-21-20-24-28291-2-21-23-29301-2-21-23-30311-2-21-23-29-31321-2-21-23-29-31-32331-2-21-23-29-31-32-33341-2-21-20-24-28-27-26-34351-2-21-23-29-31-32-35361-2-21-23-29-31-36371-2-21-23-29-31-32-35-37381-2-21-23-29-31-36-39-38391-2-21-23-29-31-36-39401-2-21-23-29-31-36-40411-2-21-23-29-31-36-40-41421-2-21-23-30-42431-2-21-23-44-43441-2-21-23-44451-2-21-22-45461-2-21-22-48-46471-2-47481-2-21-22-48491-2-21-22-48-49501-2-21-23-29-31-50附录E：部分程序代码/弗洛伊德算法/for(p=1;p=Vertex;p+)for(q=1