數(shù)學建模論文校車安排問題的數(shù)學模型論文

重慶科技學院課程論文題目 校車安排問題 院（系） 專業(yè)班級 學生姓名 學號 指導教師 職稱 評閱教師 職稱 2012年1月2日目錄TOC\o"1-5"\h\z摘要 1關鍵詞 11問題重述 2問題背景 22問題分析 2研究意義 2研究現(xiàn)狀 2存在問題 2解決方式 23模型假設 24符號約定 35模型成立與求解 4計算各點間的最短路程 45.1.1數(shù)據(jù)分析 45.1.2模型成立與計算 4成立"個搭車點使各區(qū)人員到最近搭車點的距離最小的一樣模型……55.2.1模型成立 55.2.2模型求解 5考慮每一個區(qū)的搭車人數(shù)成立"個搭車點使各區(qū)人員到最近搭車點的距離最小的一樣模型 65.3.1模型成立 65.3.2模型求解 6成立3個搭車點的車輛安排 75.4.1成立模型 75.4.2模型求解 8建議 86模型分析與評判 97模型的推行 9\o"CurrentDocument"參考文獻 9附錄 10摘要：本文針對高校新校區(qū)校車運行的安排問題，通過合理的抽象假設，把校車安排問題抽象成山點線組成的網(wǎng)絡模型，將問題轉化為n-重心問題的求解。在問題解決進程中利用了佛洛依德算法,分析、建模、求解進程中利用MATLAB、Excel對數(shù)據(jù)進行分析處置，并用C語言實現(xiàn)某些算法，最終得出結論。僅考慮距離因素時：設立兩個搭車點時，搭車點應設在區(qū)域18和區(qū)域31：設立三個搭車點時，搭車點應設在區(qū)域1五、區(qū)域21和區(qū)域31。綜合考慮距離及教師整體中意度時：設立兩個搭車點時，搭車點應設在區(qū)域19和區(qū)域32；設立三個搭車點時，搭車點應設在區(qū)域1五、區(qū)域21和區(qū)域32。為使教師及工作人員盡可能中意，至少需要安排54輛校車：其中區(qū)域15安排校車17輛；其中區(qū)域21安排校車18輛；其中區(qū)域32安排校車19輛。通過對問題的求解可知當搭車點適當增加時，教師及工作人員的中意度上升，可在學校條件許諾的情形下在適合位置適當增加搭車點。關鍵詞：弗洛伊德算法；整體中意度；n-重心問題。一.問題重述問題背景許多學校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車送到新校區(qū)。由于天天到新校區(qū)的教師和工作人員很多，往往需要安排許多車輛。如何有效的安排車輛及讓教師和工作人員盡可能中意是個十分重要的問題。、成立"個搭車點，使各區(qū)人員到最近搭車點的距離最小，該將校車搭車點應成立在哪"個點。、考慮每一個區(qū)的搭車人數(shù)，為使教師和工作人員中意度最大，該將校車搭車點應成立在哪〃個點。、成立3個搭車點，為使教師和工作人員盡可能中意，至少需要安排多少輛車？給岀每一個搭車點的位置和車輛數(shù)。設每輛車最多載客47人。二、問題分析研究意義許多學校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車送到新校區(qū)。山于天天到新校區(qū)的教師和工作人員很多，往往需要安排許多車輛。如何有效的安排車輛及讓教師和工作人員盡可能中意。研究現(xiàn)狀許多學校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車送到新校區(qū)。存在問題如何有效的安排車輛及讓教師和工作人員盡可能中意是個十分重要的問題。111于受到車輛數(shù)量的限制，即車輛花費的限制。還有搭車點的限制。咱們只能在現(xiàn)有的條件下合理的安排搭車點和搭車數(shù)量使教師和工作人員盡可能中意。解決方式老校區(qū)的50個區(qū)域的大小、形狀與問題的求解無關，可將50個區(qū)域抽象為50個點，區(qū)域間的連接道路抽象為點的連線，據(jù)此成立網(wǎng)絡模型，用佛洛依德算法求出任意兩點間最短路徑的距離,將問題的求解轉化為n-重心問題，由模型慢慢求解取得搭車點的位置。3、模型假設（1）假設老校區(qū)的教師和工作人員散布在50個區(qū)，各區(qū)的距離見附錄A。各區(qū)人員散布見附錄Bo校區(qū)人數(shù)分布圖（2） 50個區(qū)域抽象成50個點，附錄1中標注距離的點間能夠直接相通,未標注距離的點間無法直接相通，需通過其它點間接抵達。（3） 假設任一教師和工作人員的中意程度隨距離的增加遞減（4） 搭車點只設在點上。（5） 校車只在起始站點載人。4、符號約定A：點間距離的鄰接矩陣;

B：各點的最短距離矩陣%:i點到j點的最短距離；或：i到j的只以(l..k)集合中的節(jié)點為中間結點的最短路徑的距離:D。,.—：各個點到搭車點的總距離；DmJ最短總距離;■乘客個體中意度；〃：某點到搭車點所走距離；D：所有點中到搭車點的最大距離；F:所有乘客的整體中意度；Los：從頭安排搭車點的人員安重排前所走的路程；m:某區(qū)域的教師人數(shù)；M:教師及工作人員總人數(shù)；E：距搭車點的平均路程.五、模型成立與求解汁算各點間的最短路程5.1.1數(shù)據(jù)分析第一對題LI所給的各區(qū)距離做統(tǒng)計分析，用Excel表格成立對應各點距離的鄰接矩陣A,即anaana!2a5O5()a21a501a5O2a5O5()其中a?為點i到點j的距離。當a?二8,表示i點和j點不直接相通。5.1.2模型成立與計算用弗洛伊德算法計算任意兩點間的最短距離。弗洛伊德算法的原理是動態(tài)計劃，設d點為從i到j的只以(1..k)集合中的節(jié)點為中間結點的最短路徑的長度，若最短路徑通過點k,則：忡計+常若最短路徑不通過點k,則:4因此，有：d；=min（d『,dj+d『）弗洛伊德算法的C語言實現(xiàn)見附錄E。把鄰接矩陣A作為弗洛伊德算法的輸入矩陣，程序輸出各點間最短距離矩陣B（結果見附錄C）及取最短距離時各點間的走法（結果見附錄D）。成立〃個搭車點使各區(qū)人員到最近搭車點的距離最小的一樣模型5.2.1模型成立%為網(wǎng)絡中i點到j點最短路徑的權，表示i,j兩點的最短距離；卩為網(wǎng)絡中i點的權，表示i點的人數(shù)，因為不考慮人數(shù)對搭車點的阻礙，固取叫=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牛衛(wèi)2,…衛(wèi)”互異?取n二2,3,計算結果，算法的C語言實現(xiàn)見附錄E。程序計算得：n二2時，求得搭車點應設在區(qū)域18和區(qū)域31；n二3時，求得搭車點應設在區(qū)域1五、區(qū)域21和區(qū)域31?？紤]每一個區(qū)的搭車人數(shù)成立"個搭車點使各區(qū)人員到最近搭車點的距離最小的一樣模型5.3.1模型成立%為網(wǎng)絡中i點到j點最短路徑的權，表示i,j兩點的最短距離；山為網(wǎng)絡中i點的權，表示i點的人數(shù)，i,je(1,50)o問題的模型為n-重心模型：50假設任一教師和工作人員的中意程度隨距離的增加遞減，即去搭車點的距離越大越不中意，則當所有人走的總距離最短時整體的中意度最大。概念纟為乘客個體中意度，有：其中d為某點到搭車點所走距離，D為任意兩點最短距離的最大值。概念F為所有乘客的整體中意度，有：F=1一型MD其中m為某點的人數(shù)，M為所有教師人數(shù)。概念E為教師及工作人員至搭車點的平均路程，B|J：E= M5.3.2模型求解任取n個點①，/，…，?為搭車點，所有人到搭車點的總路程為：50 / \%吋“=Sm/HVL?％心?血「…宀?%)<=1則取50個點的組合?做幻，勺，…"，別離計算久.吋5,取使得久心…嗎取最小值的竹<2,…點即為所求搭車點。即：Dmm=min…心)竹衛(wèi)2,…衛(wèi)”互異?取n二2,3,計算結果，算法的C語言實現(xiàn)見附錄E。程序計算得：n二2時，求得搭車點應設在區(qū)域19和區(qū)域32,整體中意度F二張距搭車點的平均路程E~497。n二3時，求得搭車點應設在區(qū)域15、區(qū)域21和區(qū)域32,整體中意度2%；距搭車點的平均路程E~390。成立3個搭車點的車輛安排5.4.1成立模型此問題為n-重心問題的進一步引申，以車輛數(shù)和整體中意度為雙口標函數(shù)；任取3個點竹“2,9為搭車點，所有人到搭車點的總路程為：50D?e⑷=工m加也?%,ns?%,n{?d認）匸I別離找出現(xiàn)在到竹點距離最近的心個點，計算這心個點的總人數(shù)S,。（i二1,2,3）則取50個點的組合做SOT,別離計算Qg?,取使得取最小值的竹‘勺宀點即為所求搭車點。即:Dm.n=min（￡>w）對刀取余取得車載滿后的剩余人員數(shù)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衛(wèi)3e{12…，50},a{,a2，匕互異.以上算法最終通過C語言程序實現(xiàn)。4.2模型求解將最短距離矩陣B作為輸入數(shù)據(jù)送入程序，計算取得結果:搭車點應設在區(qū)域15,21,32；其中：15區(qū)應安排17輛車,到15區(qū)搭車的的區(qū)域有：5,6,7,8,9,10,11,12,13,14,15,16,17,18,25,26,27；21區(qū)應安排18輛車,到21區(qū)搭車的的區(qū)域有：b2,3,4,19,20,21,22,23,24,2&44,45,46,47,48,49；32區(qū)應安排19輛車,到32區(qū)搭車的的區(qū)域有：29,32,31,32,33,34,35,36,37,38,39,40,41,42,43,50.整體中意度F=%。整體中意度較中的%略有下降。建議概念P為本錢增加率，有：其中&為總車輛數(shù)，從增加的車輛數(shù)。計算得由和的用車數(shù)據(jù)算得P=L89%，即提高％的中意度增加了％的本錢，不劃算。lib及以上的結論可知適當增加搭車點數(shù)能增加教師和工作人員的整體中意度。而減少校車數(shù)量與增加整體中意度相矛盾。因此，在校車安排時應綜合考慮教師的中意度和增加校車與搭車點的本錢問題，在條件許諾的范圉內盡可能增加搭車點以提高整體中意度。六.模型的分析與評判本文就高校校車運行問題成立網(wǎng)絡模型，進而轉化為網(wǎng)絡最短路徑問題的求解及n-重心問題的求解，具有必然的科學性。但因某些實際因素（如中意度等）不能直接運用求解，而作了必然的理想化假設，所得結果與實際問題會存在必然誤差，需要通過與實際情形的比較進一步修正模型。7、模型的推行山模型的求解結果能夠看出適當增加搭車點數(shù)能降低平均步行距離、增加教師和工作人員的整體中意度。而減少校車數(shù)量與增加整體中意度相矛盾。因此，在校車安排時應綜合考慮教師的中意度和增加校車與搭車點的本錢問題，在條件許諾的范圍內盡可能提高整體中意度。參考文獻：［1］ 《數(shù)學模型》編寫組.數(shù)學模型.廣州：華南理工大學出版社，2003.［2］ 湖北省大學生數(shù)學建模競賽專組:數(shù)學建模（本科冊）.華中科技大學出版社，2006.［3］ 王樹禾.圖論..科學出版社.2005.［4］ 唐坤.車輛路徑問題中的遺傳算法設計?華東大學學報，2002.［習寧正元,王秀麗.算法與數(shù)據(jù)結構.淸華大學出版社，2006年1月，第1版.

附錄A：各區(qū)距離表區(qū)域號區(qū)域號距離(m)區(qū)域號區(qū)域號距離(m)區(qū)域號區(qū)域號距離(m)12400151725029311901345016171403031240243001618130304213022123017272403043210247140181920431322303460018251803136260452101920140315021041931019241753233190562302021180323514057200202419032362406732021223003334210683402123270353716078170214735036391807181602244160364019089200224527037381358152852248180383913091018023242403941310101115()2329210404114010151602330290405019011121402344150425020011141302425170434426012132002428130434521013344002627140454624014151902634320464828014261902728190484920015161702829260附錄B：各區(qū)人員散布區(qū)域人數(shù)區(qū)域人數(shù)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創(chuàng)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盂釁^(qū)lMIs-r囂￡粹5話T斗^#.>JLs:-?r#^^^^^HaB*hffi:aa*H.￡爲?i'TJK^sMWEWJMM盤sse=sM?M=rM二"豈5M2T覧=5=-2->:?￡:囂瓷wnwsAc也農(nóng)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區(qū)域到y(tǒng)區(qū)域的最短距離附錄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++