1、數(shù)學(xué)建模解決乘車點(diǎn)安排問題摘要本文就目前大學(xué)各區(qū)域與新校區(qū)之間校車乘車點(diǎn)的安排及教師和工作人員的滿意程度展開研究,通過合理的抽象和假設(shè),將乘車點(diǎn)的安排問題轉(zhuǎn)化為無向圖的多源最短距離的搜索問題,并通過一定的實(shí)地調(diào)查,將教師員工的滿意度問題與校車運(yùn)營(yíng)本錢結(jié)合起來,并在計(jì)算過程中運(yùn)用exel,matlab等一系列計(jì)算機(jī)軟件,得到了一些較為實(shí)際和精確的結(jié)果.1、問題一：不考慮各點(diǎn)的人數(shù),僅考慮各點(diǎn)到乘車點(diǎn)的總距離最短.當(dāng)乘車點(diǎn)n=3時(shí),選擇的乘車點(diǎn)是15,21,31三個(gè)點(diǎn),最短總距離為19660;當(dāng)乘車點(diǎn)n=4時(shí),選擇的乘車點(diǎn)是11,18,22,32四個(gè)點(diǎn),最短總距離為16961;2、問題二：考慮到各

2、點(diǎn)的人數(shù),使將人數(shù)計(jì)算在內(nèi)的總體距離最短此時(shí)認(rèn)為總體距離最短就是最滿意當(dāng)乘車點(diǎn)n=3時(shí),選擇的乘車點(diǎn)是16,23,32三個(gè)點(diǎn),滿意度為0.7811;當(dāng)乘車點(diǎn)n=4時(shí),選擇的乘車點(diǎn)是2,15,23,32四個(gè)點(diǎn),滿意度為0.8170;3 .問題三：為使教員和工作人員到達(dá)相對(duì)滿意的的程度,又要求車輛最少,綜合考慮到總體滿意度和個(gè)體最小滿意度.得到三個(gè)點(diǎn)為x,x,x;安排車輛數(shù)為y.4 .問題四：經(jīng)過一定的實(shí)際情況調(diào)查,考慮到車輛運(yùn)行本錢和車輛滿座率,乘車時(shí)間等實(shí)際問題,量化給出較為優(yōu)化的解決方案.關(guān)鍵詞：搜索算法,最短距離矩陣,總體滿意度,個(gè)人滿意度,實(shí)際方案.1、問題重述：某學(xué)校建有新校區(qū),常常需

3、要將老校區(qū)的教師和工作人員用校車送到新校區(qū).由于每天到新校區(qū)的教師和工作人員很多,往往需要安排許多車輛.如何有效的安排車輛及讓教師和工作人員盡量滿意是個(gè)十分重要的問題.現(xiàn)有如下問題請(qǐng)你設(shè)計(jì)解決.假設(shè)老校區(qū)的教師和工作人員分布在50個(gè)區(qū),各區(qū)的距離見表1.各區(qū)人員分布見表2.問題1:如要建立n個(gè)乘車點(diǎn),為使各區(qū)人員到最近乘車點(diǎn)的距離最小,該將校車乘車點(diǎn)應(yīng)建立在哪個(gè)點(diǎn).建立一般模型,并給出n=3,4時(shí)的結(jié)果.問題2:假設(shè)考慮每個(gè)區(qū)的乘車人數(shù),為使教師和工作人員滿意度最大,該將校車乘車點(diǎn)應(yīng)建立在哪n個(gè)點(diǎn).建立一般模型,并給出n=3,4時(shí)的結(jié)果.問題3假設(shè)建立3個(gè)乘車點(diǎn),為使教師和工作人員盡量滿意,至

4、少需要安排多少輛車？給出每個(gè)乘車點(diǎn)的位置和車輛數(shù).設(shè)每輛車最多載客45人假定車只在起始站點(diǎn)載人.問題4;關(guān)于校車安排問題,你還有什么好的建議和考慮.可以提升乘車人員的滿意度,又可節(jié)省運(yùn)行本錢.2、問題分析1.1 研究意義就我校而言,就建有理學(xué)院新校區(qū),各專業(yè)學(xué)院及教員小區(qū)與新校區(qū)之間就要靠校車解決.同時(shí)學(xué)校車輛有限,考慮到交通狀況也不可能每個(gè)點(diǎn)都有車輛到達(dá),如何安排車輛和乘車點(diǎn)使教員和工作人員滿意,同時(shí)又能節(jié)約本錢使資源得到最大的運(yùn)用就是一個(gè)十分實(shí)際而有意義的問題.1.2 研究現(xiàn)狀目前大多數(shù)校車乘車點(diǎn)和車輛安排都是在經(jīng)驗(yàn)下做出的,沒有做到量化處理,使方案到達(dá)最優(yōu)化.1.3 存在問題滿意度的具體

5、定義,乘車點(diǎn)和車輛怎樣安排才能使教員和工作人員到達(dá)相對(duì)滿意的程度,同時(shí)怎樣在保證相對(duì)滿意的條件下使車輛的運(yùn)營(yíng)本錢最小,就牽扯到運(yùn)營(yíng)本錢的具體量化,最后提出一套量化解決方案.1.4 解決方法首先這50個(gè)區(qū)域可以簡(jiǎn)化成由50個(gè)點(diǎn)組成的無向圖,題設(shè)中給出的點(diǎn)點(diǎn)之間的距離就是無向圖中的邊的權(quán)值,題目一可簡(jiǎn)化為無向圖中其他點(diǎn)到選出點(diǎn)的最短距離問題,可以用floyd算法算出所有點(diǎn)之間的最短距離,再用窮舉比擬的方法計(jì)算各點(diǎn)到選出點(diǎn)的最短距離和的最小值.問題二可建立關(guān)于人數(shù)的滿意度函數(shù),在問題一的根底上算出最大滿意度的方案.問題三那么要考慮到校車的運(yùn)營(yíng)本錢問題,綜合總體滿意度和個(gè)人滿意度,給出一個(gè)教員相對(duì)滿意

6、且用車最少的方案,問題四那么要結(jié)合一些實(shí)際問題考慮,如人的頂峰時(shí)間、校車的滿座率、校車的運(yùn)行線路后才能給出一個(gè)較為實(shí)際和完備的方案.3 .模型假設(shè)(1)未給出距離的兩個(gè)區(qū)可以由其他區(qū)間接到達(dá).乘車點(diǎn)只設(shè)在某幾個(gè)區(qū)域內(nèi)不能選擇50個(gè)點(diǎn)以外的點(diǎn)作為乘車點(diǎn).所有的教員都乘車,且都會(huì)去離自己最近的乘車點(diǎn)乘車.(4)教員的滿意度與離乘車點(diǎn)的距離有關(guān),距離越遠(yuǎn)滿意度越低,距離越近滿意度越高.(5)作為乘車點(diǎn)的區(qū)域的人到乘車點(diǎn)的距離為00(6)乘車點(diǎn)的選取數(shù)目不超過50.4 .符號(hào)約定p:區(qū)域個(gè)數(shù).n:乘車點(diǎn)的個(gè)數(shù).X:題設(shè)給出的個(gè)點(diǎn)之間的稀疏矩陣.Z:個(gè)點(diǎn)之間的最短距離矩陣.X,j:題設(shè)給出的i,j點(diǎn)原始

7、距離.zpj：i,j兩個(gè)點(diǎn)之間通過1,2,3p這五十個(gè)區(qū)域中的節(jié)點(diǎn)相連得到的最短距離4/：i,j點(diǎn)之間的最短距離.S:五十個(gè)點(diǎn)到選出的乘車點(diǎn)的距離之和.ZR:第i個(gè)點(diǎn)的人數(shù).ZQ:第i個(gè)點(diǎn)距乘車點(diǎn)的最短距離ZY：第i個(gè)點(diǎn)距離他最遠(yuǎn)點(diǎn)的距離M:教員的總體滿意度.mi：第i個(gè)區(qū)的區(qū)域滿意度.5 .模型的建立和求解5.1 最短距離矩陣的計(jì)算一一floyd算法對(duì)有權(quán)無向圖來說計(jì)算點(diǎn)與點(diǎn)之間的最短距離的方法有基于動(dòng)態(tài)規(guī)劃的floyd算法和dijkstra算法,其中的floyd算法具有速度快,且能方便記錄路徑的特點(diǎn),所以我們選用floyd算法.(1)在稀疏矩陣G中Gj表示第i個(gè)區(qū)域到第j個(gè)區(qū)域之間的距離；

8、(2)用矩陣R來記錄插入點(diǎn)的信息,其中Rj表示第i個(gè)區(qū)域到達(dá)第j個(gè)區(qū)域所要經(jīng)過點(diǎn)的記錄,把各個(gè)區(qū)域插入圖中,比擬插入?yún)^(qū)域后的距離與原來的距離,Gjmin(Gj,GikGkj),如果Gj的距離變小,那么Rj=k,并把最短距離記錄在矩陣D中.算法完成后那么R中包含了最短通路的信息,Dj中包含了最短路徑的信息.5.1.1 數(shù)據(jù)分析題設(shè)已經(jīng)給出了一定的點(diǎn)之間的距離列表,由matlab求出個(gè)點(diǎn)之間距離的稀疏夕!陣X.其中沒有給出距離的點(diǎn)置為無窮大infX=X1,1X1,2X2,1X1,50X2,50x50,1x50,2X50,50再由floyd算法,進(jìn)行迭代計(jì)算.對(duì)任意兩點(diǎn)(i,j),假設(shè)存在z,Z,j

9、zipp1zp,j1,那么更新jzipj3.直到所有點(diǎn)的距離不再更新停止計(jì)算,那么得到最短路距離矩陣Matlab的代碼將在附錄一中給出,下列圖是由matlab生成的最小距離矩陣的示意圖,其中顏色越深表示距離越短.3C20401510F和15的253035Hl5.2 使各區(qū)到乘車點(diǎn)的距離最小5.2.1 模型建立為使個(gè)區(qū)人員到乘車點(diǎn)的距離最小,我們考慮個(gè)區(qū)人員到乘車點(diǎn)的總距離應(yīng)該最小.設(shè)選出的乘車點(diǎn)是p1,那么最短總距離那么為最短距首先考慮僅設(shè)立一個(gè)乘車點(diǎn)的情況離矩陣中其他點(diǎn)到選出點(diǎn)的距離之和50ZDi(p1)i1,ipl在考慮設(shè)立兩個(gè)乘車點(diǎn)的情況當(dāng)n=2時(shí),我們就要考慮到一個(gè)乘車點(diǎn)的選擇問題,第

10、i點(diǎn)到底是選擇pl作為乘車點(diǎn),還是選擇p2作為乘車點(diǎn)呢？應(yīng)該是在這兩種方案中選出距離較短的點(diǎn)作為i點(diǎn)的乘車點(diǎn).ZDimin(ZDiPl,ZDiP2)那么選取的兩個(gè)點(diǎn)應(yīng)使目標(biāo)函數(shù)50ZQi1最小.下面我們考慮乘車點(diǎn)數(shù)為n的情況,當(dāng)乘車點(diǎn)為n時(shí)的情況其實(shí)與乘車點(diǎn)為二是的情況沒有什么區(qū)別,區(qū)別在與對(duì)乘車點(diǎn)的選擇上需要比擬更多的情況.ZDimin(ZDiPl,ZDiP2,ZDiP3,ZDiPn)乘車點(diǎn)的選擇應(yīng)使目標(biāo)函數(shù)最小.5.2.2 模型求解具體的matlab程序?qū)⒃诟戒浂薪o出由程序計(jì)算得當(dāng)n=3時(shí)選擇的乘車點(diǎn)應(yīng)為15,21,31三個(gè)點(diǎn),最短總距離為196600且到15乘車點(diǎn)的區(qū)域有5,6,7,8

11、,9,10,11,12,13,14,15,16,17,18,25,26,27;到21乘車點(diǎn)的區(qū)域有1,2,3,4,19,20,21,22,23,24,44,45,46,47,48,49;至U31乘車的區(qū)域有28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,50.當(dāng)n=4時(shí)選擇的乘車點(diǎn)應(yīng)為11,18,22,32四個(gè)點(diǎn),最短總距離為16961.且到11乘車點(diǎn)的區(qū)域有9,10,11,12,13,14,26,27;至U18乘車點(diǎn)的區(qū)域有5.2.3 ,6,7,8,15,16,17,18,19,20,24,25;至U22乘車點(diǎn)的區(qū)域有5.2.4 1,22,23

12、,43,44,45,46,47,48,49;到32乘車點(diǎn)的區(qū)域有29,30,31,32,33,34,35,36,37,38,39,40,41,42,50.5.3 乘車點(diǎn)的設(shè)置使各區(qū)人員滿意度最大的模型5.3.1 模型建立首先靠考慮到在該種情況下滿意度的定義是什么,很明顯在問題二的情況下啊,乘客滿意的情況是到乘車點(diǎn)的距離越短越好,當(dāng)乘車點(diǎn)就是該點(diǎn)的時(shí)候滿意度就為最大,如果將滿意度定為一的話,那么此時(shí)的滿意度即為1,;如果乘車點(diǎn)世道該點(diǎn)最遠(yuǎn)的點(diǎn)時(shí),此時(shí)乘客的滿意度應(yīng)為最小,即為0,由此我們可以建立滿意度方程：miZDZY該方程認(rèn)為滿意度與距離之間是簡(jiǎn)單的線性關(guān)系.m2RZP由于問題二中每個(gè)點(diǎn)都有不

13、同的人數(shù)存在,即無向圖的每個(gè)點(diǎn)都有了一定的權(quán)重,我們不可能使每個(gè)區(qū)域的滿意度都到達(dá)最大,所以在計(jì)算最終的滿意程度時(shí)要將人數(shù)的因素加權(quán)進(jìn)入方程：MM即為模型二的目標(biāo)函數(shù).5.3.2 模型求解相關(guān)的matlab程序?qū)⒃诟戒浫薪o出.當(dāng)n=3時(shí),選擇的點(diǎn)為16,23,32.滿意度為0.7811.其中選擇16為乘車點(diǎn)的區(qū)域有3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,25,26,27;選擇23為乘車點(diǎn)的區(qū)域有1,2,20,21,22,23,24,28,29,30,42,43,44,45,46,47,48,49;選擇32為乘車點(diǎn)的區(qū)域有13,31,32,33,34,

14、35,36,37,38,39,40,41,50.當(dāng)n=4時(shí),選擇的點(diǎn)為2,15,23,32.滿意度為0.8107.其中選擇2為乘車點(diǎn)的區(qū)域有1,2,3,4,5,20,21,47;選擇15為乘車點(diǎn)的8,9,10,11,12,13,14,15,16,17,18,26,27;選擇23為乘車點(diǎn)的區(qū)域有19,22,23,24,25,28,29,30,41,42,43,44,45,46,48,49;選擇32為乘車點(diǎn)的區(qū)域有31,32,33,34,35,36,37,38,39,40,41,50.點(diǎn)數(shù)越來越多的情況等會(huì)考慮.5.4 建立三個(gè)乘車點(diǎn)時(shí),使教員相對(duì)滿意且用車最少的模型5.4.1 模型建立如果我們以

15、考慮教員的滿意程度為主,那么乘車點(diǎn)一定與模型二的選擇一樣,且車輛數(shù)也不一定是最少的.所以在該模型中應(yīng)該建立兩個(gè)目標(biāo)函數(shù),一個(gè)是教員的滿意程度,另一個(gè)那么是車輛的數(shù)量.由于ZPmod45有很大的時(shí)機(jī)不等于零,對(duì)于每個(gè)點(diǎn)整數(shù)輛的車裝不滿的人,是再安排一輛車去接這幾個(gè)人,還是讓這幾個(gè)人自己去不那么近的乘車點(diǎn)降低以下滿意度呢?下面就這兩種不同的方案建立模型.(1)剩余人再派車接.在模型二的根底上,設(shè)到各個(gè)乘車點(diǎn)的總?cè)藬?shù)為CPk(第k乘車點(diǎn)的人數(shù))那么每個(gè)乘車點(diǎn)的車輛數(shù)Ck為CkCPkmod451那么總的車輛數(shù)為nZCmin(CPk)k1使ZC最小的乘車點(diǎn)即為所需要的狀態(tài).(2)剩余的人到離自己相對(duì)近的

16、乘車點(diǎn)乘車,犧牲一定的滿意程度.任是在模型二的根底上,選擇乘車點(diǎn).每個(gè)乘車點(diǎn)僅安排能滿載的車輛數(shù),設(shè)為MZk,那么滿足MZkCP45每個(gè)點(diǎn)剩下的人數(shù)SZk為:SZkCPkmod45再考慮這些剩下的人應(yīng)該怎樣辦？我們的解決方法是,再運(yùn)用模型二,不過這次只有這三個(gè)乘車點(diǎn)和每個(gè)乘車點(diǎn)剩下的人再做一次乘車點(diǎn)優(yōu)化,使這些人到三個(gè)乘車點(diǎn)的某個(gè)點(diǎn)的距離最短即使目標(biāo)函數(shù)SZkm'kSZk最小,其中m'k為二次優(yōu)化中各乘車點(diǎn)剩下的人的滿意度函數(shù).5.4.2 模型求解由matlab得出以下結(jié)果車輛數(shù)滿息度選擇乘車點(diǎn)力殺1570.781118,23,32力殺2560.768216,23,32(23)

17、有結(jié)果可以看出,中選擇較小的車輛數(shù)的時(shí)候,滿意度會(huì)有所降低,選擇較大的滿意度的時(shí)候,車輛數(shù)會(huì)有所增加.5.5 建議和意經(jīng)過一定的實(shí)踐考察我們得出教員和工作人員出行的時(shí)間如下圖IJiW失刖一般來說教員的出行幾種在上午上課,下午上課以及黃昏放學(xué)這三個(gè)時(shí)段,是有頂峰的出行,而且有出行集中,不能遲到的特點(diǎn),由此并結(jié)合問題一,二,三提出以下建議：1 .在資金和人員允許的情況下適當(dāng)?shù)脑黾映塑圏c(diǎn)的數(shù)量,這樣可以有效的提升教員的滿意度.2 .安排一輛或者兩輛速度較快的巡游車在各個(gè)乘車點(diǎn)和新校區(qū)之間巡游及時(shí)帶走沒有趕上車的教員.3 .改善教學(xué)課表,使教員能夠分時(shí)段上車,讓一局部的車輛能夠循環(huán)使用,不用一起派出大

18、量的車在較短的時(shí)間里將教員送到新校區(qū).4 .建議購(gòu)置不同大小的車,使各個(gè)站點(diǎn)的老師正好乘坐,即不留一個(gè)老師也不遺漏一個(gè)空位.5 .對(duì)教員提出要求,要求教員在一定的乘車時(shí)間內(nèi)乘車,防止由于某些人遲到而導(dǎo)致的等人,空載的情況.6 .某型的分析與評(píng)價(jià)6.1 優(yōu)點(diǎn)1、本文的根底采用floyd算法,由于有成熟的算法,使得帶權(quán)鄰接矩陣的得出十分流暢,算法效率很高.2、采用分布計(jì)算方法,使得乘車點(diǎn)事先確定后的最值求出,再使乘車點(diǎn)的可能性取遍所有可能,較容易用程序循環(huán)實(shí)現(xiàn).3、將人的心理滿意度函數(shù)化,較貼切的反映了人的心理,具有較強(qiáng)的現(xiàn)實(shí)性.4、模型建立的合理性,模型的建立是在對(duì)給的數(shù)據(jù)進(jìn)行充分的挖掘的根底上

19、,通過數(shù)據(jù)之間的關(guān)系提煉出各個(gè)區(qū)域之間的關(guān)系并建立起模型.5、模型的建立是根據(jù)問題的解決的思路進(jìn)行的,分析和發(fā)現(xiàn)很有規(guī)律,然后對(duì)規(guī)律進(jìn)行評(píng)價(jià),最后建模.6.2 缺點(diǎn)1、把人的滿意度隨距離成正比,對(duì)模型的求解帶來一定的誤差2、程序耗時(shí)長(zhǎng),時(shí)間復(fù)雜度太大.3、考慮問題的全面性還不夠.7模型的推廣本例的延伸對(duì)于解決各種交通問題,物流問題,計(jì)算機(jī)網(wǎng)絡(luò)問題等問題.8 .參考文獻(xiàn)【1】?高等數(shù)學(xué)問題的matlab求解?2?數(shù)學(xué)模型?姜啟元謝金星9 .附錄各點(diǎn)距離分布圖區(qū)域號(hào)區(qū)域號(hào)距離(m)12400134502430022123024714034600452104193105623057200673206

20、834078170718160892008152859101801011150101516011121401114130121320013344001415190142619015161701517250161714016181301727240181920418251801920140192417520211802024190212230021232702147350224416022452702248180232424023292102330290234415024251702428130262714026343202728190282926029311903031240304213030

21、43210313223031362603150210323319032351403236240333421035371603639180364019037381353839130394131040411404050190425020043442604345210454624046482804849200各點(diǎn)人員分布區(qū)域人數(shù)區(qū)域人數(shù)16526162672794342281843429295383075629311071732868643370939345610203565116136261247378013663890142139471570404016854157171242401835436

22、919484467205445202149461822124768235448722446497625765062附錄一clear;clc;n=50;a=zeros(n);a(1,2)=400;a(1,3)=450;a(2,4)=300;a(2,21)=230;a(2,47)=140;a(3,4)=600;a(4,5)=210;a(4,19)=310;a(5,6)=230;a(5,7)=200;a(6,7)=320;a(6,8)=340;a(7,8)=170;a(7,18)=160;a(8,9)=200;a(8,15)=285;a(9,10)=180;a(10,11)=150;a(10,15)

23、=160;a(11,12)=140;a(11,14)=130;a(12,13)=200;a(13,34)=400;a(14,15)=190;a(14,26)=190;a(15,16)=170;a(15,17)=250;a(16,17)=140;a(16,18)=130;a(17,27)=240;a(18,19)=204;a(18,25)=180;a(19,20)=140;a(19,24)=175;a(20,21)=180;a(20,24)=190;a(21,22)=300;a(21,23)=270;a(21,47)=350;a(22,44)=160;a(22,45)=270;a(22,48)=

24、180;a(23,24)=240;a(23,29)=210;a(23,30)=290;a(23,44)=150;a(24,28)=130;a(24,25)=170;a(26,27)=140;a(26,34)=320;a(27,28)=190;a(28,29)=260;a(29,31)=190;a(30,31)=240;a(30,42)=130;a(30,43)=210;a(31,32)=230;a(31,36)=260;a(31,50)=210;a(32,33)=190;a(32,35)=140;a(32,36)=240;a(35,37)=160;a(36,39)=180;a(36,40)=190;a(37,38)=135;a(38,39)=130;a(39,41)=310;a(40,41)=140;a(40,50)=190;a(42,50)=200;a(43,44)=260;a(43,45)=210;a(33,34)=210;a(45,46)=240;a(46,48)=280;a(48,49)=200;a=a+a'M=max(max(a)*nA2;a=a+(a=0)-eye(n)*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j