校车乘车点的分配毕业论文.doc

《校车乘车点的分配毕业论文.doc》由会员分享，可在线阅读，更多相关《校车乘车点的分配毕业论文.doc（18页珍藏版）》请在三一办公上搜索。

1、渭南师范学院本科毕业论文题 目： 校车乘车点的分配 专 业： 信息与计算科学 系 班： 数学与信息科学系06级数本1班 毕业年份： 2010年 姓 名： 学 号： 060741123 指导教师： 职 称： 讲 师 渭南师范学院教务处 制目 录1 毕业论文任务书 12 毕业论文开题报告 . 33 毕业论文登记表 .54 毕业论文文稿 85 答辩记录18渭南师范学院本科毕业论文（设计）任务书论文（设计）题目最小生成树算法及其应用学生姓名杨飞系、专业、班级数学与信息科学系06级数本1班毕业年份2010年7月学 号060741123指导教师张先叶职 称讲师一、文献查阅指引1 图与网络的模型及方法，2

2、袁新生、邵大宏、郁时炼，LINGO和EXCEL在数学建模中的应用，科学教育出版社，2006.3.3 李占利,运筹学简明教程,西北工业大学出版社,2003.7.4 吴孟达,数学建模的理论与实践,国防科技大学出版社,1999.5 谢謇会,最优化原理与方法,国防科技大学出版社,1999.6 杨炳儒.图论概要.天津科学出版社.7 方世昌.离散数学（第二版）.西安电子科技大学出版社. 8 D.J. Baker and A. Ephremides, The architectural organization of a mobile radio network via a distributed algo

3、rithm, IEEE Transactions on Communications COM-29 11 (1981) 16941701.二、内容要求1 仔细查阅国内外目前对此问题研究现状的有关文献.2 分析解决校车乘车点的分配问题.3格式规范,论点明确,论据充分.4 叙述简洁完整,有见解;文字通顺,书写工整规范.三、进度安排毕业论文撰写时间安排:1、动员：2009年12月2日2、论文设计总时间 12周（12月7日12月27日；3月1日5月2日）（1）选题与填写开题报告（09年12月7日10年3月7日）（2）论文撰写35天（3月8日4月11日）（26周）（3）论文定稿打印7天 （4月12日4月

4、18日）（7周）（4）论文评阅及答辩审查7天（4月19日4月25日）（8周）（5）论文答辩7天（4月26日5月2日）（9周）（6）论文成绩评定 7天（5月3日5月9日）（10周）3、论文撰写停课时间：3月15日5月2日（29周）四、起止日期 2009年12 月2 日至2010 年 5 月9 日指导教师（签名） 教研室主任（签名） 系主管主任（签名） 年 月 日注：1. 任务书由指导教师填写、经教研室主任及系主管教学副主任审批后，在第七学期末之前下达给学生。2. 文献查阅指引，应是对查阅内容和查阅方法的指引，即查阅什么和怎样查阅。渭南师范学院本科毕业论文（设计）开题报告论文（设计）题目校车乘车点

5、的分配学生姓名杨飞系、专业、班级数学与信息科学系06级数本1班毕业年份2010年学 号060741123指导教师张先叶职 称讲师一、 一、拟开展研究的价值、意义本文主要研究了在校车乘车点的分配中如何解决教师的满意度及运行成本问题,主要考虑了在乘车时，采用哪种路线所用时间最短.二、研究步骤、方法及措施1.查找收集与图论相关的资料.2.在指导老师的帮助下对题目中的数据进行处理.3.根据题目要求建立一般的数学模型.3.根据处理的数据及建立的模型进行相关计算.4.完成整片论文.三、论文拟定提纲1.问题重述;2.基本假设;3.符号说明;4.问题分析;5.模型的建立及求解5.1问题一模型的建立及求解5.1

6、.1模型的建立;5.1.2模型的求解;5.1.3模型的验证;5.2问题二模型的建立及求解5.2.1模型的建立;5.2.2模型的求解;5.3问题三模型的建立及求解5.4建议及考虑6.模型的评价6.1优点6.2缺点7.模型的推广8.参考文献四、主要参考文献1 图与网络的模型及方法，2 袁新生、邵大宏、郁时炼，LINGO和EXCEL在数学建模中的应用，科学教育出版社，2006.3.3 李占利,运筹学简明教程,西北工业大学出版社,2003.7.4 吴孟达,数学建模的理论与实践,国防科技大学出版社,1999.5 谢謇会,最优化原理与方法,国防科技大学出版社,1999.6 杨炳儒.图论概要.天津科学出版社

7、.7 方世昌.离散数学（第二版）.西安电子科技大学出版社. 8 D.J. Baker and A. Ephremides, The architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications COM-29 11 (1981) 16941701.指导教师意见： 指导教师签字： 年 月 日系主管主任意见： 系主管主任签字： 年 月 日注：开题报告是在导师的指导下，由学生填写。渭南师范学院本科毕业论文（设计）登记表论文（设计）

8、题目校车乘车点的分配学生姓名杨飞系、专业、班级数学与信息科学系06级数本1班毕业年份2008年学 号040742085指导教师张先叶职 称讲师一、论文摘要（中文）本文主要研究了在校车乘车点分配中如何解决教师的满意度及运行成本问题,主要考虑了在乘车时，采用哪种路线所用时间最短.对所给的数据进行预处理,得到50个区域的邻接矩阵.问题一:为使得各区人员到个乘车点的距离和最小，相对应建立了两个整数规划模型,分别为乘车距离的最大化和乘车距离的最大值的最小化.再将两个模型进行比较，最终解的当时,将校车乘车点建立在区域4和区域32;当时,将校车乘车点分别建立在区域4,区域26和区域30.问题二:我们用第区的

9、人数第个乘车点第个区的距离的积的倒数来定义满意度.要使满意度最大,即要使第区的人数第个乘车点第个区的距离的积,解得当时,将校车乘车点建立在27区和28区;当时,将校车乘车点建立在4区、26区和30区.问题三:在第二问的基础上,当时,将校车的乘车率视为第二满意度,即当总人数除以47时,所得的整数值加上1,可得需要安排的车辆数为55.问题四:结合问题一、问题二和问题三的结论,针对乘车点距离和最小,满意度最大,确定了更完整的整数规划模型.二、论文摘要（英文）The distribution of school bus travel PointYANG Fei（Class 1 Grade 2010,

10、department of Mathematics and information Science,Weinan Teachers University）Abstract: This paper mainly studies how the adjacency matrix of satisfaction of teachers and running costs。Major consideration in the car, the time spent by the shortest route which。Given by the problem of data preprocessin

11、g, and 50 regional minimum Adjacency Matrix.Question one: to enable district personnel to a travel point and the minimum, corresponding to the establishment of two integer programming models, respectively, the maximum travel distance and travel distance to minimize the maximum. Then compare the two

12、models, solution of the time and point when the regional school bus ride.Problem II: the first area we were traveling the first point of the number of districts from the product defines the reciprocal satisfaction. For maximum satisfaction, that the first area to make the first month the number of d

13、istricts by car Point distance product, solution when the school bus was traveling at that time and point of the region.Question 3: In the second question, based on the time, the school bus ridership satisfaction rate as the second, that when the total number divided by 4 plus 1 integer value, the n

14、umber of vehicles may need 55 .Key words: integer programming; The shortest path; Adjacency matrix三、成绩评定指导教师评语：.本文通过各乘车点之间的距离，利用图论的相关知识，得到了校车乘车点分配点.写作过程中该生能够独立运用所学的建模知识解决实际问题.符号统一，书写规范，文章综述简练完整，有一定见解.指导教师签字： 年 月 日评阅人评语：从文章内容可看出，该生查阅文献有一定广泛性，有综合归纳资料的能力，综述简练完整. 年 月 日答辩小组评语：文章阐述中用清晰的语言表达了论文的结构，回答问题时用理论

15、依据，基本概念清楚，答辩通过. 成 绩(分数)答辩小组组长签字： 年 月 日答辩委员会审核意见：答辩委员会主席签字： 年 月 日待添加的隐藏文字内容2校车乘车点的分配杨飞（渭南师范学院 数学与信息科学系 06级数本1班）摘 要：本文主要研究了在校车乘车点的分配中如何解决教师的满意度及运行成本问题,主要考虑了在乘车时，采用哪种路线所用时间最短.对所给的数据进行预处理,得到50个区域的邻接矩阵.问题一:为使得各区人员到个乘车点的距离和最小，相对应建立了两个整数规划模型,分别为乘车距离的最大化和乘车距离的最大值的最小化.再将两个模型进行比较，解的当时和时校车乘车点的区域.问题二:我们用第区的人数第个

16、乘车点第个区的距离的积的倒数来定义满意度.要使满意度最大,即要使第区的人数第个乘车点第个区的距离的积,解得当时和时校车乘车点的区域.问题三:在第二问的基础上,当时,将校车的乘车率视为第二满意度,即当总人数除以4的整数值加1,得需要的车辆数为55.关键词: 整数规划; 最短路; 邻接矩阵1问题概述在许多学校都有新校区,为了使老校区的教师和工作人员能够按时到达新校区,则需要安排许多车辆.为了使教师和工作人员都能满意，我们需要有效的安排这些车辆.现需设计解决以下问题:问题1:为了使各区人员能尽快到达乘车点,现建立个乘车点,应将校车的乘车点建立在那几个点,建立一般模型,并给出时的结果.问题2:若考虑各

17、区人数,使教师和工作人员满意度最大,应将校车乘车点建立在那几个点,建立一般模型,并给出时的结果.问题3:在问题一或问题二的基础上,为使教师和工作人员尽量满意,建立3个乘车点,至少需要安排多少辆车?并给出乘车点位置和车辆数.问题4:在让乘车人员满意的基础上,又可节省运行成本,关于校车安排问题,还有什么好的建议和考虑.2基本假设2.1假设各个区人员步行速度相同;2.2假设每个区之间都能直线到达;2.3假设每个区没有人不乘车;2.4假设在乘车时，没有时间限制;2.5假设满座为原则,不考虑给1人都安排1辆车;2.6假设乘车点都建立在某一个区域内;2.7假设每辆车最多能坐47人;2.8假设车上无空座位.

18、3符号说明符 号涵 义建立乘车点的个数第个乘车点第个区第个乘车点与第个区的距离变量第个区的人数4问题分析要将老校区的教师和工作人员用校车送到新校区.在最短的时间内，尽量用最少的车辆,将老校区的人员送到新校区是至关重要的.因此在设计方式时,应该尽量遵循两条原则:原则一:尽可能的用最短的时间内让老校区的人员到达乘车点;原则二:所有的区域都能涉及到.对原则一,在实际问题时,只需保证让所有的教师和工作人员到达乘车点所走的路程最短.对于原则二,将乘车点尽量安排在所分区域中心.根据信息我们先根据题目所告诉的50个区域之间的距离把50个区域所在的位置画出来.再根据将各个区域间的距离化成一个的矩阵.对于问题一

19、,我们建立个乘车点,我们先根据各个区域的位置特点,将整个区域分成个小区域,再根据小区域内部各个点间的距离关系,在每个区域内寻找出个点,求出小区域内各个区到点的距离,再根据对比,最终确定出乘车点位置.对于问题二,与问题一想法相同,再根据各个区的人数,设满意度为（1/各个区的人数乘以各个区到乘车点的距离和）,要是满意度最大,即使各个区的人数乘以各个区到乘车点的距离和最小,最终确定出乘车点位置,见问题.对于问题三,在问题一或问题二的基础上,我们在第二问的基础上,当时,再将校车的乘车率视为第二满意度,即当总人数除以47时，所得的整数值加上1,最终解得需要安排的车辆数.对于问题四，在乘车人员满意的基础上

20、，又可节省运行成本，提出相应的建议.5模型的建立及求解5.1问题一模型的建立及求解此类问题可用动态规划方法来解决,以下为最短路问题的网络解法.的基本思想是将点集划分为(标号点集,Permanent label)和(称标号点集,tentative label).要求的最短路, 的具体步骤如下:开始,把中的分化为和,使;,令.第一步:若时,计算终止,此时对每个,并反向追踪求的的最短路,否则转入第二步.第二步:若时,反复按如下进行:(1)对每一,若,则把修改为.转(2).(2)令,若这样的不止一个,可任取一个.(3)令,将归为,(即把的标号变为标号),并置,转第一步.图形比例为 1:100标号法的求

21、解过程也可用表格表示出来,最终得到一个的矩阵.(见附录) 5.1.1模型的建立要建立乘车点,先根据各个区域的位置特点，将整个区域分成个小区域，再根据小区域内部各个点间的距离关系,建立的模型一为：,确定点所在区域.我们还可根据,两点间的距离最大值的最小值,建立模型二的.5.1.2模型的求解模型的算法为:将整个区域分解成个小区域,然后再根据个小区域间的距离来确定个点;在邻接矩阵中找出区域到点的距离;对各个小区域中的所有到达点的区域的距离求和;将模型一与模型二进行比较,求得最小距离,确定乘车点的位置.最终所得结果为:当时，第一个乘车点在区域4内.X: 到乘车点1（区域4）的所有区的区域号;Y: 乘车

22、点1（区域4）与所有区的距离X123791011192021224547Y70030060041078096011103104505308301100440第二个乘车点的位置在区域31内.X: 到乘车点2（区域31）的所有区的区域号;Y: 乘车点2（区域31）与所有区的距离X8131415161718232425Y1260103097011301020880930400580750X26272829303233343637Y780640450190240230420630260530X38394142434446484950Y5704405403706807809008901090210当时，

23、第一个乘车点在区域30内.X: 到乘车点1（区域30）的所有区的区域号;Y: 乘车点1（区域30）与所有区的距离X192022232428293136Y705720600290530660660240500X394142434445464849Y680660130210420420660780980第二个乘车点在区域4内.X: 到乘车点2（区域4）的所有区的区域号;Y: 乘车点2（区域4）与所有区的距离X1235672147Y700300600210440410530440第三个乘车点在区域17内.X: 到乘车点3（区域17）的所有区的区域号;Y: 乘车点3（区域17）与所有区的距离X8910

24、111213141516Y535590410560700900440250140X182526273233343538Y2704503802401100910700124014505.1.3模型验证通过将模型一与模型二的比较，最终解得当时，应将校车乘车点建立在区域4和31内;当时,应将校车乘车点建立在区域4、17和30内.5.2 问题二模型的建立及求解5.2.1模型的建立我们要建立个乘车点,先根据各个区域的特点,将整个区域分成个小区域，再根据小区域内部各个点间的距离关系,及其各个小区的人数,定义满意度为，如果要使满意度最大,即目标函数为,确定乘车点的位置.5.2.2模型的求解模型的具体算法为:

25、(1)在问题一所确定乘车点基础上,根据每个小区域中各个区域的人数关系,重新确定个点;(2)在邻接矩阵中,找出每个小区域中所有区域到乘车点的距离;(3)在找出的区域到乘车点的距离乘以各区人数,即;(4)对各个小区域中所有求和;(5)将确定的点进行比较,确定最终的乘车点最终所得结果为:当时，确定的乘车点为：区域4和区域32.第一个乘车点在区域4内.X: 到乘车点1（区域4）的所有区的区域号;Y: 乘车点1（区域4）与所有区的距离;Z:乘车点的人数的总距离.X123791011Y7003006004107809601110Z4555020100252006970304201920067710X454

26、719202122Y1100440310450530830Z322000299201488024300259709960第二个乘车点在区域32内.X: 到乘车点2（区域32）的所有区的区域号;Y: 乘车点2（区域32）与所有区的距离. Z:乘车点的人数的总距离.X131516171826282930Y8001100124011001160860420470230Z5280077000105400132000406001376075601363017250X313334353637383940Y230190400140240300435565630Z23001330022400910062402

27、4000391502655525200X4142434445464950Y77060068078089011301320435Z4389024000469205226017800203401003226970当时，第一个乘车点在区域4内.X: 到乘车点1（区域4）的所有区的区域号;Y: 乘车点1（区域4）与所有区的距离;Z:该区乘车的人数和.X1235672147Y700300600210440410530440Z4550020100252007980127606970259702990第二个乘车点为区域26.X: 到乘车点2（区域26）的所有区的区域号;Y: 乘车点2（区域26）与所有区的距

28、离;Z: 该区乘车的人数和.X8910111213141516Y665650470320460660190380520Z4256025350940019520216204356039902660044200X182527323334353738Y65063014072053032086010201155Z2275047800131606192037100179205590081600103950第三个乘车点在区域30内.X: 到乘车点3（区域30）的所有区的区域号;Y: 乘车点3（区域30）与所有区的距离;Z: 该区乘车的人数和.X192022232428293136Y705720600290

29、530660660240500Z3384033840720015060243801188019140240013000X394243444546484950Y680130210420420660780980810Z31960520014490281408400118805616074480405005.3 问题三模型的建立及求解对于问题三:我们在第二问的基础上求解,当时,我们再将校车的乘车率视为第二满意度,即当总人数除以47时,即车辆数=（总人数47）所得整数+1.根据题中所给的各区人员分布解得:到乘车点一（区域4 ）的总人数为409,即需要车辆数为9.到乘车点2（区域26）的总人数为1141

30、,该乘车点需要车辆数25.到乘车点3（区域30）的总人数为952,所需车辆数为21.所以所需总车辆数为55.5.4建议及考虑如果当余数小于10时将不再重新安排车辆,即车辆数为乘车点的总人数除以47时,可以考虑不用再安排车辆,可以让剩余的人站在车上,已达到资源的合理利用.如果在安排车辆时,应考虑到,剩余的人尽可能的少,这样,就可对各个区域剩余的人安排一辆车,这就可以转换为最小生成树的问题.6模型的评价6.1优点：6.1.1对于问题一给出了不同的模型进行对比6.1.2在不规则图形中，给出多条路线进行对比，最后求出最短路.6.2缺点：本模型不适用于区域形状规则的情况7模型的推广7.1可以将此问题推广

31、到多个路线寻找最短路问题及邮递员投递问题中.7.2对于问题二还可以定义不同的满意度进行对比求解.（指导老师：张先叶）参考文献1 图与网络的模型及方法，2 袁新生、邵大宏、郁时炼，LINGO和EXCEL在数学建模中的应用，科学教育出版社，2006.3.3 李占利,运筹学简明教程,西北工业大学出版社,2003.7.4 吴孟达,数学建模的理论与实践,国防科技大学出版社,1999.5 谢謇会,最优化原理与方法,国防科技大学出版社,1999.6 杨炳儒.图论概要.天津科学出版社.7 方世昌.离散数学（第二版）.西安电子科技大学出版社. 8 D.J. Baker and A. Ephremides, Th

32、e architectural organization of a mobile radio network via a distributed algorithm, IEEE Transactions on Communications COM-29 11 (1981) 16941701.The distribution of school bus travel PointYANG Fei（Class 1 Grade 2010, department of Mathematics and information Science,Weinan Teachers University）Abstr

33、act: This paper mainly studies how the adjacency matrix of satisfaction of teachers and running costs。Major consideration in the car, the time spent by the shortest route which。Given by the problem of data preprocessing, and 50 regional minimum Adjacency Matrix.Question one: to enable district perso

34、nnel to a travel point and the minimum, corresponding to the establishment of two integer programming models, respectively, the maximum travel distance and travel distance to minimize the maximum. Then compare the two models, solution of the time and point when the regional school bus ride.Problem I

35、I: the first area we were traveling the first point of the number of districts from the product defines the reciprocal satisfaction. For maximum satisfaction, that the first area to make the first month the number of districts by car Point distance product, solution when the school bus was traveling

36、 at that time and point of the region.Question 3: In the second question, based on the time, the school bus ridership satisfaction rate as the second, that when the total number divided by 4 plus 1 integer value, the number of vehicles may need 55 .Key words: integer programming; The shortest path; Adjacency matrix