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

重庆科技学院课程论文题目 校车安排问题 院（系） 专业班级 学生姓名 学号 指导教师 职称 评阅教师 职称 2012年1月2日目录TOC\o"1-5"\h\z摘要 1关键词 11问题重述 2问题背景 22问题分析 2研究意义 2研究现状 2存在问题 2解决方式 23模型假设 24符号约定 35模型成立与求解 4计算各点间的最短路程 45.1.1数据分析 45.1.2模型成立与计算 4成立"个搭车点使各区人员到最近搭车点的距离最小的一样模型……55.2.1模型成立 55.2.2模型求解 5考虑每一个区的搭车人数成立"个搭车点使各区人员到最近搭车点的距离最小的一样模型 65.3.1模型成立 65.3.2模型求解 6成立3个搭车点的车辆安排 75.4.1成立模型 75.4.2模型求解 8建议 86模型分析与评判 97模型的推行 9\o"CurrentDocument"参考文献 9附录 10摘要：本文针对高校新校区校车运行的安排问题，通过合理的抽象假设，把校车安排问题抽象成山点线组成的网络模型，将问题转化为n-重心问题的求解。在问题解决进程中利用了佛洛依德算法,分析、建模、求解进程中利用MATLAB、Excel对数据进行分析处置，并用C语言实现某些算法，最终得出结论。仅考虑距离因素时：设立两个搭车点时，搭车点应设在区域18和区域31：设立三个搭车点时，搭车点应设在区域1五、区域21和区域31。综合考虑距离及教师整体中意度时：设立两个搭车点时，搭车点应设在区域19和区域32；设立三个搭车点时，搭车点应设在区域1五、区域21和区域32。为使教师及工作人员尽可能中意，至少需要安排54辆校车：其中区域15安排校车17辆；其中区域21安排校车18辆；其中区域32安排校车19辆。通过对问题的求解可知当搭车点适当增加时，教师及工作人员的中意度上升，可在学校条件许诺的情形下在适合位置适当增加搭车点。关键词：弗洛伊德算法；整体中意度；n-重心问题。一.问题重述问题背景许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。由于天天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽可能中意是个十分重要的问题。、成立"个搭车点，使各区人员到最近搭车点的距离最小，该将校车搭车点应成立在哪"个点。、考虑每一个区的搭车人数，为使教师和工作人员中意度最大，该将校车搭车点应成立在哪〃个点。、成立3个搭车点，为使教师和工作人员尽可能中意，至少需要安排多少辆车？给岀每一个搭车点的位置和车辆数。设每辆车最多载客47人。二、问题分析研究意义许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。山于天天到新校区的教师和工作人员很多，往往需要安排许多车辆。如何有效的安排车辆及让教师和工作人员尽可能中意。研究现状许多学校都建有新校区，常常需要将老校区的教师和工作人员用校车送到新校区。存在问题如何有效的安排车辆及让教师和工作人员尽可能中意是个十分重要的问题。111于受到车辆数量的限制，即车辆花费的限制。还有搭车点的限制。咱们只能在现有的条件下合理的安排搭车点和搭车数量使教师和工作人员尽可能中意。解决方式老校区的50个区域的大小、形状与问题的求解无关，可将50个区域抽象为50个点，区域间的连接道路抽象为点的连线，据此成立网络模型，用佛洛依德算法求出任意两点间最短路径的距离,将问题的求解转化为n-重心问题，由模型慢慢求解取得搭车点的位置。3、模型假设（1）假设老校区的教师和工作人员散布在50个区，各区的距离见附录A。各区人员散布见附录Bo校区人数分布图（2） 50个区域抽象成50个点，附录1中标注距离的点间能够直接相通,未标注距离的点间无法直接相通，需通过其它点间接抵达。（3） 假设任一教师和工作人员的中意程度随距离的增加递减（4） 搭车点只设在点上。（5） 校车只在起始站点载人。4、符号约定A：点间距离的邻接矩阵;

B：各点的最短距离矩阵%:i点到j点的最短距离；或：i到j的只以(l..k)集合中的节点为中间结点的最短路径的距离:D。,.—：各个点到搭车点的总距离；DmJ最短总距离;■乘客个体中意度；〃：某点到搭车点所走距离；D：所有点中到搭车点的最大距离；F:所有乘客的整体中意度；Los：从头安排搭车点的人员安重排前所走的路程；m:某区域的教师人数；M:教师及工作人员总人数；E：距搭车点的平均路程.五、模型成立与求解汁算各点间的最短路程5.1.1数据分析第一对题LI所给的各区距离做统计分析，用Excel表格成立对应各点距离的邻接矩阵A,即anaana!2a5O5()a21a501a5O2a5O5()其中a»为点i到点j的距离。当a»二8,表示i点和j点不直接相通。5.1.2模型成立与计算用弗洛伊德算法计算任意两点间的最短距离。弗洛伊德算法的原理是动态计划，设d点为从i到j的只以(1..k)集合中的节点为中间结点的最短路径的长度，若最短路径通过点k,则：忡計+常若最短路径不通过点k,则:4因此，有：d；=min（d『,dj+d『）弗洛伊德算法的C语言实现见附录E。把邻接矩阵A作为弗洛伊德算法的输入矩阵，程序输出各点间最短距离矩阵B（结果见附录C）及取最短距离时各点间的走法（结果见附录D）。成立〃个搭车点使各区人员到最近搭车点的距离最小的一样模型5.2.1模型成立%为网络中i点到j点最短路径的权，表示i,j两点的最短距离；卩为网络中i点的权，表示i点的人数，因为不考虑人数对搭车点的阻碍，固取叫=1,i,j€（1,50）o问题的模型为特殊情形（比=1）的n-重心模型：TOC\o"1-5"\h\z50 50min/==工如5.2.2模型求解任取n个互异点勺，…，化为搭车点，则从各点到搭车点的总路程为：5° / \i=l则取50个点的组合做““2,…，别离计算久勺,…心，取使得乞知…心取最小值的幻“2,…，5点即为所求搭车点。即：Dmin=nin ）〜，・•・<g{12・・・，50卜1 二 tl牛卫2,…卫”互异•取n二2,3,计算结果，算法的C语言实现见附录E。程序计算得：n二2时，求得搭车点应设在区域18和区域31；n二3时，求得搭车点应设在区域1五、区域21和区域31。考虑每一个区的搭车人数成立"个搭车点使各区人员到最近搭车点的距离最小的一样模型5.3.1模型成立%为网络中i点到j点最短路径的权，表示i,j两点的最短距离；山为网络中i点的权，表示i点的人数，i,je(1,50)o问题的模型为n-重心模型：50假设任一教师和工作人员的中意程度随距离的增加递减，即去搭车点的距离越大越不中意，则当所有人走的总距离最短时整体的中意度最大。概念纟为乘客个体中意度，有：其中d为某点到搭车点所走距离，D为任意两点最短距离的最大值。概念F为所有乘客的整体中意度，有：F=1一型MD其中m为某点的人数，M为所有教师人数。概念E为教师及工作人员至搭车点的平均路程，B|J：E= M5.3.2模型求解任取n个点①，/，…，〜为搭车点，所有人到搭车点的总路程为：50 / \%吋“=Sm/HVL・％心•血「…宀•%)<=1则取50个点的组合©做幻，勺，…"，别离计算久.吋5,取使得久心…吗取最小值的竹<2,…点即为所求搭车点。即：Dmm=min…心)竹卫2,…卫”互异•取n二2,3,计算结果，算法的C语言实现见附录E。程序计算得：n二2时，求得搭车点应设在区域19和区域32,整体中意度F二张距搭车点的平均路程E~497。n二3时，求得搭车点应设在区域15、区域21和区域32,整体中意度2%；距搭车点的平均路程E~390。成立3个搭车点的车辆安排5.4.1成立模型此问题为n-重心问题的进一步引申，以车辆数和整体中意度为双口标函数；任取3个点竹“2,9为搭车点，所有人到搭车点的总路程为：50D®e⑷=工m加也•%,ns•%,n{・d认）匸I别离找出现在到竹点距离最近的心个点，计算这心个点的总人数S,。（i二1,2,3）则取50个点的组合做SOT,别离计算Qg®,取使得取最小值的竹‘勺宀点即为所求搭车点。即:Dm.n=min（£>w）对刀取余取得车载满后的剩余人员数M°4,即：Modt=mod47从头安排搭车点的人员安重排前所走的路程为：3Los=V[min（Mod；•£）.）]；e{1,2,3}重安排搭车点的人员所走的最短路径为：*=磁）（％%+M%2%儿j2,j3g{1,2,3}月儿J2,j3互异.从头安排后所走总路径的最小值为：Dgn=%'+£)——Los

mm minmina{,a0卫3e{12…，50},a{,a2，匕互异.以上算法最终通过C语言程序实现。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区搭车的的区域有：b2,3,4,19,20,21,22,23,24,2&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=%。整体中意度较中的%略有下降。建议概念P为本钱增加率，有：其中&为总车辆数，从增加的车辆数。计算得由和的用车数据算得P=L89%，即提高％的中意度增加了％的本钱，不划算。lib及以上的结论可知适当增加搭车点数能增加教师和工作人员的整体中意度。而减少校车数量与增加整体中意度相矛盾。因此，在校车安排时应综合考虑教师的中意度和增加校车与搭车点的本钱问题，在条件许诺的范圉内尽可能增加搭车点以提高整体中意度。六.模型的分析与评判本文就高校校车运行问题成立网络模型，进而转化为网络最短路径问题的求解及n-重心问题的求解，具有必然的科学性。但因某些实际因素（如中意度等）不能直接运用求解，而作了必然的理想化假设，所得结果与实际问题会存在必然误差，需要通过与实际情形的比较进一步修正模型。7、模型的推行山模型的求解结果能够看出适当增加搭车点数能降低平均步行距离、增加教师和工作人员的整体中意度。而减少校车数量与增加整体中意度相矛盾。因此，在校车安排时应综合考虑教师的中意度和增加校车与搭车点的本钱问题，在条件许诺的范围内尽可能提高整体中意度。参考文献：［1］ 《数学模型》编写组.数学模型.广州：华南理工大学出版社，2003.［2］ 湖北省大学生数学建模竞赛专组:数学建模（本科册）.华中科技大学出版社，2006.［3］ 王树禾.图论..科学出版社.2005.［4］ 唐坤.车辆路径问题中的遗传算法设计•华东大学学报，2002.［习宁正元,王秀丽.算法与数据结构.淸华大学出版社，2006年1月，第1版.

附录A：各区距离表区域号区域号距离(m)区域号区域号距离(m)区域号区域号距离(m)12400151725029311901345016171403031240243001618130304213022123017272403043210247140181920431322303460018251803136260452101920140315021041931019241753233190562302021180323514057200202419032362406732021223003334210683402123270353716078170214735036391807181602244160364019089200224527037381358152852248180383913091018023242403941310101115()2329210404114010151602330290405019011121402344150425020011141302425170434426012132002428130434521013344002627140454624014151902634320464828014261902728190484920015161702829260附录B：各区人员散布区域人数区域人数1652616267279434228184342929538307562931107173286864337093934561020356511613626124737801366389014213947157040401685415717124240183543691948446720544520214946182212476823544872

2446497625765062附录C：用Eexce1存储的点间最短距离矩阵^-ss^-sss-ffiK^ECH”^-ss^-sss-ffiK^ECH”二,JlKsMssMES.-亠話sAwi善且鶯曽低二三丘器£時W禺盅圧f工2-爺器£活王§£=盟5:菓55霊s-K.^m虽s!55:s會怎SSH•普Isswwxssss:冬rMJKMts.--£-<E豈s-TT-r-rs员WJJX5詈2.E5-0uuwn:luu*w«lnu«»<JEVJiilwu*ulluEL・i!1«g»:'lM&uu创wk:]u"231Hs:1uMK*«aM«xA]M"lu・•>«匹需Un益和W善善al亠;51亠ISI.wwlFWEElpz^ssAsisKsiSIsizTSJssCN益vrMn器f”兰瓷心益■善嘉豈菩善菩善*盘篥二召歎唇呼盐栄熱弓25:»”s:;:“5:5£5:ss*s:話zs:1益誇::謊;5豈”::带25器盐盟“常瘁席於主，力::器肚::幣Qersz::嘗H-s«xw:wt诂嘗冒乂豈鴛MASKA凭6>::二常広:2二二忙花器：器以盘6*山牴::£衣;£-菩菩器一■盂复3-»:sroMEEm“G»>=*s:£:::"&-tss-tK-rssM£«9»x2*>参S6告5S盂釁^lMIs-r囂£粹5話T斗^#.>JLs:-«r#^^^^^HaB*hffi:aa*H.£爲•i'TJK^sMWEWJMM盘sse=sM«M=rM二"豈5M2T覧=5=-2->:・£:囂瓷wnwsAc也農x£書X工工-5.S孟二二圧三二誥誌瓷活邑轻1zs:mE:«»::t1»::iLD»v*5:«Bs:l>l»::m,w»m::M»5:M»::川x:lo*E:吨adwXIEE<!1!:£说=6Mm=R%_lLse-5;2K:£tww)ulissl^sMW・二需话益2乍直|<1!嚣・豈£二曽专冒3黒』£ixm善ss-tTY-g-B”囂-2s-ts:2::;UWR±.5t-w嚣5普帑JLsmmlK二SS5SSSAT2^f1»3:ws:*«;:E2:t1awM«l»»・a»*l»^M*x:M»5:n»5:mi::l>»^忖?:<»»5:*t»s:m0•\JIiLJilJJ.JLil<Emw专MgmEHWw.普KEEns_・E冒壬盅力曇鵲^益:”常囂敷・2:gMmtfaSM:・n«"»M^z*M:r«w£v:;:;s:s:=^^s:*專：SZIMJS芽MMMIaMMHsM^sss。盅矍豈EWA策亲左焉益黨箱豈获需廳嚣■KMMK:::盘Ev«ms・k:nwjlb-==k盅益k!-ssmm£:s-£:js-ZS-SM且；：Js_王・E善SIsWIAsEUMMsMtss-sMs:虫益層53・易5盲姣覧=|»存£:二二2書=5;!|2爺肘二氏WVMCS直IHEEAm豈器翼W聘—总莖冷2虽*Em詈三舊薰篥話=豈當器”。善JLs-二盅曇虽畧誰£常嚮5鵲嚣5:.5:£:範^■专弓書負焙S422囂二S:51S'IMS1MI.5::S書SS・唸=工,衣挨?:=且盂v£K-=二Mxisxz器sm/>=5:J善JLS-亠畳二2-2蛊弓盍唇5:.="三篥5:5!-=蛊盅.MIMl>uwglMwo«E・wlv*5MLws:glMu:la!2Aw<KLi:LJi氐»9uR5»JMnL»tM⑴W1MHIMB1HE常MS!:盂常說MS黑器*s=u盅J\-^會益翼署案囂蛊怎盅署盟药益篥誥豈笛::备注：(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—>27

281—>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=l;p<=Vertex;p++)for(q=l;q<=Vertex;q++){fin»Map[p][q]; /*输入邻接矩阵至Map[p][q]*/Dist[p][q]二Hap[p][q];}for(k=l;k<=Vertex;k++)for(p=l;p<=Vertex:p++