校車安排問題數(shù)學(xué)建模

1、題目：校車安排問題摘要本文針對高校新校區(qū)校車運(yùn)行的安排問題，通過合理的抽象假設(shè)，建立了校車安排方案的優(yōu)化模型。從乘車點(diǎn)的距離最小，滿意度最大又可節(jié)省運(yùn)行成本等方面考慮，依據(jù)題目中所給條件分別建模求解。在問題解決過程中使用了Warshall-Floyd算法，分析、建模、求解過程中利用MATLAB編寫相應(yīng)程序并對數(shù)據(jù)進(jìn)行分析處理，最終得出結(jié)論如下：問題1：僅考慮到每個(gè)區(qū)按距離車站的遠(yuǎn)近選擇車站n=2時(shí)，乘車點(diǎn)：18 、31 距離：24492n=3時(shí)，乘車點(diǎn)：15 、21 、31 距離：19660問題2：綜合考慮距離及教師總體滿意度n=2時(shí)，乘車點(diǎn)：19 、32 滿意度：77.77%n=3時(shí)，乘車點(diǎn)

2、：15 、21 、32 滿意度：82.60%問題3：為使教師及工作人員盡量滿意，至少需要安排54輛校車區(qū)15：安排17輛校車區(qū)21：安排19輛校車區(qū)32：安排18輛校車問題4：綜合考慮距離模型，滿意度模型，運(yùn)營成本以及現(xiàn)實(shí)中的各種因素，給出校車安排的一些建議：在校車安排時(shí)應(yīng)綜合考慮教師的滿意度和增加校車與乘車點(diǎn)的成本問題，在條件允許的范圍內(nèi)盡量增加乘車點(diǎn)以提高總體滿意度。關(guān)鍵詞：Warshall-Floyd算法 總體滿意度 距離矩陣 MATLAB1、 問題重述許多學(xué)校都建有新校區(qū)，常常需要將老校區(qū)的教師和工作人員用校車送到新校區(qū)。由于每天到新校區(qū)的教師和工作人員很多，往往需要安排許多車輛。如何

3、有效的安排車輛及讓教師和工作人員盡量滿意是個(gè)十分重要的問題。有如下問題待設(shè)計(jì)解決：假設(shè)老校區(qū)的教師和工作人員分布在50個(gè)區(qū)，各區(qū)的距離見表1。各區(qū)人員分布見表2。（1）問題1：如要建立n個(gè)乘車點(diǎn)，為使各區(qū)人員到最近乘車點(diǎn)的距離最小，該將校車乘車點(diǎn)應(yīng)建立在哪n個(gè)點(diǎn)。建立一般模型，并給出n=2,3時(shí)的結(jié)果。 （2）問題2：若考慮每個(gè)區(qū)的乘車人數(shù)，為使教師和工作人員滿意度最大，該將校車乘車點(diǎn)應(yīng)建立在哪n個(gè)點(diǎn)。建立一般模型，并給出n=2,3時(shí)的結(jié)果。 （3）問題3 若建立3個(gè)乘車點(diǎn)，為使教師和工作人員盡量滿意，至少需要安排多少輛車？給出每個(gè)乘車點(diǎn)的位置和車輛數(shù)。設(shè)每輛車最多載客47人。（4）問題4；關(guān)

4、于校車安排問題，你還有什么好的建議和考慮?？梢蕴岣叱塑嚾藛T的滿意度，又可節(jié)省運(yùn)行成本。2、 模型的假設(shè)及符號分析2.1 模型的假設(shè) （1）50個(gè)區(qū)域看做50個(gè)點(diǎn)，附錄A中標(biāo)注距離的點(diǎn)間可以直接連通，而未標(biāo)注的點(diǎn)則不能，必需通過其他點(diǎn)間接到達(dá)。（2）假設(shè)所有乘車點(diǎn)設(shè)立在各小區(qū)（點(diǎn)）上，乘車站點(diǎn)不設(shè)立在路上。（3）假設(shè)教師和工作人員的滿意度只與距離有關(guān)，而忽略其他因素對其滿意度的影響。（4）校車只在各個(gè)點(diǎn)上載人，行駛途中不載人。（5）假設(shè)所有人員均乘車。（6）假設(shè)任意時(shí)刻任意站點(diǎn)均有車，不考慮教師及工作人員的等車時(shí)間。2.2 符號說明A：各點(diǎn)間距離的鄰接矩陣；B：各點(diǎn)間的最短距離矩陣；dij：頂點(diǎn)

5、i到頂點(diǎn)j的最短距離；ij：圖中i點(diǎn)到j(luò)點(diǎn)最短路徑的權(quán)；ni：圖中i點(diǎn)的權(quán)，表示i點(diǎn)（即i區(qū)）的人數(shù)；Dv1，v2，v3，vn：各個(gè)點(diǎn)到乘車點(diǎn)的總距離；Dmin：最短總距離;:乘客個(gè)體的滿意度；：所有乘客的總體滿意度；d：某點(diǎn)走到乘車點(diǎn)的距離；D：任意兩點(diǎn)最短距離的最大值；R：教師及工作人員走到乘車點(diǎn)的平均距離。3、 模型的建立與求解3.1 計(jì)算各區(qū)（點(diǎn)）之間的最短路3.1.1 數(shù)據(jù)分析及處理用附錄A中的各區(qū)之間距離建立對應(yīng)各點(diǎn)距離的鄰接矩陣A，即A=a11a12a21a150a250a501a502a5050其中aij表示點(diǎn)i到點(diǎn)j的距離，當(dāng)aij=inf ，表示點(diǎn)i和點(diǎn)j不直接相通。3.1

6、.2 用Warshall-Floyd算法計(jì)算任意兩點(diǎn)間的最短路設(shè)i為圖G中的頂點(diǎn)。令dij是頂點(diǎn)i到頂點(diǎn)j的最短距離，ij是頂點(diǎn)i到頂點(diǎn)j的權(quán)。對于任何一個(gè)頂點(diǎn)，頂點(diǎn)i到頂點(diǎn)j的最短路經(jīng)過頂點(diǎn)k或者不經(jīng)過頂點(diǎn)k。比較dij與dik+dkj的值。若dij>dik+dkj，則令dij=dik+dkj，保持dij是當(dāng)前搜索的頂點(diǎn)i 到頂點(diǎn)j的最短距離。重復(fù)這一過程，最后當(dāng)搜索完所有頂點(diǎn)k時(shí)，dij就是頂點(diǎn)i到頂點(diǎn)j的最短距離。這一算法的具體實(shí)現(xiàn)由MATLAB編程實(shí)現(xiàn)，具體程序見附錄D。將鄰接矩陣A作為Warshall-Floyd算法的輸入矩陣，程序輸出各點(diǎn)間的最短距離矩陣B（結(jié)果見附錄B）以及

7、取最短距離時(shí)部分點(diǎn)間的走法（結(jié)果見附錄C）。3.2 建立n個(gè)乘車點(diǎn)使各區(qū)人員到最近乘車點(diǎn)的距離最小的數(shù)學(xué)模型3.2.1 模型的建立ij為圖中i點(diǎn)到j(luò)點(diǎn)最短路徑的權(quán)，表示從i點(diǎn)到j(luò)點(diǎn)的最短距離；ni為圖中i點(diǎn)的權(quán)，表示i點(diǎn)（即i區(qū)）的人數(shù)，由于不考慮人數(shù)對乘車點(diǎn)的影響，取ni=1，i，j（1,50）。問題1的模型為ni=1時(shí)的特殊情況：Min f = i=150niij=i=150ij3.2.2 模型的求解任取n個(gè)互異點(diǎn)v1，v2，v3，vn為乘車點(diǎn)，則從各點(diǎn)到乘車點(diǎn)的總路程為：Dv1，v2，v3，vn=i=150min(iv1,iv2,ivn)則取50個(gè)點(diǎn)的組合C50n做v1，v2，v3，vn

8、，分別計(jì)算Dv1，v2，v3，vn，取得使Dv1，v2，v3，vn取最小值的v1，v2，v3，vn點(diǎn)即為所求乘車點(diǎn)。即：Dmin=min（Dv1，v2，v3，vn）其中v1，v2，v3，vn1,2,50, 且v1，v2，v3，vn互不相等取n=2,3，計(jì)算結(jié)果，算法的MATLAB實(shí)現(xiàn)減附錄D .由程序計(jì)算得：n=2時(shí)，求得乘車點(diǎn)應(yīng)在區(qū)域18和31，且Dmin=24492n=3時(shí)，求得乘車點(diǎn)應(yīng)在區(qū)域15、21和31，且Dmin=196603.3 考慮每個(gè)區(qū)的乘車人數(shù)建立n個(gè)乘車點(diǎn)，使教師和工作人員滿意度最大3.3.1 模型的建立ij為圖中i點(diǎn)到j(luò)點(diǎn)最短路徑的權(quán)，表示從i點(diǎn)到j(luò)點(diǎn)的最短距離；ni為

9、圖中i點(diǎn)的權(quán)，表示i點(diǎn)（即i區(qū)）的人數(shù)，取ni=1，i，j（1,50）。則Min f =i=150niij可以想象，去乘車點(diǎn)的距離越大越不滿意，即滿意度隨距離的增加而降低，假設(shè)為線性關(guān)系，當(dāng)所有人走的總距離最短時(shí)滿意度最大。定義為乘客個(gè)體滿意度，依假設(shè)有：=1 - dD其中d為某點(diǎn)走到乘車點(diǎn)的距離，D為任意兩點(diǎn)最短距離的最大值。定義為所有乘客的總體滿意度，有：=1 - mdMD其中m為某點(diǎn)的人數(shù)，M為所有教師人數(shù)。定義R為教師及工作人員走到乘車點(diǎn)的平均距離，即：R=mdM3.3.2 模型的求解任取n個(gè)點(diǎn)v1，v2，v3，vn為乘車點(diǎn)，所有人到乘車點(diǎn)的總路程為：Dv1，v2，v3，vn=i=15

10、0min（ni*iv1,ni*iv2,ni*ivn)則取50個(gè)點(diǎn)的組合C50n做v1，v2，v3，vn，分別計(jì)算Dv1，v2，v3，vn，取得使Dv1，v2，v3，vn取最小值的v1，v2，v3，vn點(diǎn)即為所求乘車點(diǎn)。即：Dmin=min（Dv1，v2，v3，vn）其中v1，v2，v3，vn1,2,50, 且v1，v2，v3，vn互不相等取n=2,3，計(jì)算結(jié)果，算法的MATLAB實(shí)現(xiàn)減附錄D .由程序計(jì)算得：n=2時(shí)，求得乘車點(diǎn)應(yīng)取區(qū)域19和32，總體滿意度=77.77%；距離乘車點(diǎn)的平均距離R=496.8n=3時(shí)，求得乘車點(diǎn)應(yīng)取區(qū)域15、21和32，總體滿意度=82.60%；距離乘車點(diǎn)的平均

11、距離R=388.83.4 建立3個(gè)乘車點(diǎn)的數(shù)學(xué)模型3.4.1 模型的建立此問題以車輛數(shù)和總體滿意度為雙目標(biāo)函數(shù)；任取3個(gè)點(diǎn)v1，v2，v3為乘車點(diǎn)，所有人到乘車點(diǎn)的總路程為：Dv1，v2，v3=i=150min（ni*iv1,ni*iv2,ni*ivn)分別找出此時(shí)到vi點(diǎn)距離最近的ki個(gè)點(diǎn)，計(jì)算這ki個(gè)點(diǎn)的總?cè)藬?shù)si。（i=1,2,3）則取50個(gè)點(diǎn)的組合C503做v1，v2，v3，分別計(jì)算Dv1，v2，v3，取得使Dv1，v2，v3取最小值的v1，v2，v3點(diǎn)即為所求乘車點(diǎn)。即：Dmin=min（Dv1，v2，v3）從而車輛數(shù) K=i=13si47 ( 表示向上取整)3.4.2 模型求解以上

12、算法通過MATLAB編程實(shí)現(xiàn)。(具體程序見附錄D)將最短距離矩陣B和各區(qū)人數(shù)座位輸入數(shù)據(jù)輸入程序，計(jì)算得到結(jié)果：乘車點(diǎn)應(yīng)設(shè)在區(qū)域15、21、32（由模型3.3可知）；其中：15區(qū)應(yīng)安排17輛車，到15區(qū)乘車的區(qū)域有：5 、 6 、 7 、 8 、 9 、 10 、 11 、 12 、 13 、 14 、 15 、 16 、 17 、 18 、 25 、 26 、 2721區(qū)應(yīng)安排19輛車，到21區(qū)乘車的區(qū)域有：1 、 2 、 3 、 4 、 19 、 20 、 21 、 22 、 23 、 24 、 28 、 43 、 44 、 45 、 46 、 47 、 48 、49 32區(qū)應(yīng)安排18輛車

13、，到32區(qū)乘車的區(qū)域有：29 、 30 、 31 、 32 、 33 、 34 、 35 、 36 、 37 、 38 、 39 、 40 、 41 、 42 、 50 3.5 建議1.從問題求解過程中，我們可以看出固定的校車出發(fā)點(diǎn)使得校車?yán)寐式档?。因此我們建議空閑的校車到其他的乘車點(diǎn)去運(yùn)送乘車人員。從而使需要的校車數(shù)目減少一至兩輛。2.適當(dāng)增加乘車點(diǎn)的數(shù)量，使乘車人員的不滿意度進(jìn)一步減小。3.在一天內(nèi)的不同時(shí)間點(diǎn)應(yīng)安排不同輛數(shù)的校車。上下課時(shí)間為乘車高峰期，應(yīng)多安排車輛，其它時(shí)間應(yīng)少安排。這樣可有效節(jié)省運(yùn)行成本。4.盡量將人員的上下班時(shí)間統(tǒng)一在幾個(gè)固定的時(shí)間段，在這幾個(gè)時(shí)間段安排足夠的車輛

14、，保證每名員工都能及時(shí)乘坐校車，也可增加校車的運(yùn)營效率。5.在非高峰期可適當(dāng)停止部分站點(diǎn)的使用。4.模型的分析與評價(jià)本文就高校校車安排問題建立網(wǎng)絡(luò)模型，進(jìn)而轉(zhuǎn)化為圖論中最短路問題，具有一定的科學(xué)性。但模型是建立在一系列假設(shè)的基礎(chǔ)上，所得結(jié)果與實(shí)際問題會存在一定偏差，需要通過與實(shí)際情況比較而進(jìn)行修正。模型優(yōu)點(diǎn)：1、本模型運(yùn)用相關(guān)數(shù)學(xué)及計(jì)算機(jī)知識，成功解決了如何安排有限個(gè)站點(diǎn)使老師和工作人員滿意度最高的問題。在假設(shè)條件下，該模型精確地給出了站點(diǎn)位置。2、通過MATLAB編程我們可以得到任意兩個(gè)區(qū)之間的最短路徑，并且可以得了任意兩個(gè)區(qū)最短路徑具體的路線。模型缺點(diǎn)：1、本模型在理想條件下，通過編程可得

15、出精確結(jié)果，但程序運(yùn)行較為復(fù)雜，當(dāng)設(shè)置的乘車點(diǎn)較多時(shí)，程序運(yùn)算量非常大。2、乘客個(gè)體滿意度公式過于理想，忽略了很多其他因素。5、模型的推廣：本模型可推廣到公共站點(diǎn)設(shè)置、服務(wù)中心位置選擇、垃圾運(yùn)輸?shù)茸疃搪窂郊斑x址問題。本模型利用計(jì)算機(jī)程序?qū)崿F(xiàn)了對結(jié)果的精確定位，可應(yīng)用于各種與此類型相關(guān)的場合。6、參考文獻(xiàn)【1】王海英 黃強(qiáng) 等，圖論算法及其MATLAB實(shí)現(xiàn)，北京航空航天大學(xué)出版社，2010年2月第1版【2】龔劬，圖論與網(wǎng)絡(luò)最優(yōu)化算法，重慶大學(xué)出版社，2009年10月第1版【3】姜啟源 謝金星 葉俊，數(shù)學(xué)模型，高等教育出版社，2003年8月【4】李得宜 李明，數(shù)學(xué)建模，科學(xué)出版社，2009年5月7

16、、附錄附錄A：各區(qū)距離表區(qū)域號區(qū)域號距離區(qū)域號區(qū)域號距離區(qū)域號區(qū)域號距離124001517250293119013450161714030312402430016181303042130221230172724030432102471401819204313223034600182518031362604521019201403150210419310192417532331905623020211803235140572002024190323624067320212230033342106834021232703537160781702147350363918071816022441603

17、640190892002245270373813581528522481803839130910180232424039413101011150232921040411401015160233029040501901112140234415042502001114130242517043442601213200242813043452101334400262714045462401415190263432046482801426190272819048492001516170282926012345678948495010400450700910114011101280148011101310

18、151024000850300510740710880108071091011103450850060081010401010118013801560176018754700300600021044041058078010101210127559105108102100230200370570122014201485611407401040440230032034054014501650162071110710101041020032001703701164136413008128088011805803703401700200133415341470914801080138078057054

19、0370200015341734164048111071015601010122014501164133415340200110049131091017601210142016501364153417342000130050151011101875127514851620130014701640110013000附錄B：點(diǎn)間最短距離矩陣附錄C:各點(diǎn)間取最短距離的走法（僅列出以1為出發(fā)點(diǎn)的路徑）目的地最短路徑21231341245124561245671245781245789124578910122120191816151011122120191816151011121221201918161

20、510111213122120191816151011121314122120191816151415122120191816151612212019181617122120191816171812212019181912212019201221202112212212212223122123241221202425122120242526122120242827262712212024282728122120242829122123293012212330311221232931321221232931323312212329313233341221202428272634351221232

21、9313235361221232931363712212329313235373812212329313639383912212329313639401221232931364041122123293136404142122123304243122123444344122123444512212245461221224846471247481221224849122122484950122123293150附錄D：MATLAB程序/Warshall-Floyd算法/%給鄰接矩陣賦值，鄰接矩陣記為w（i，j）for i=1:50 for j=1:50 if i=j w(i,j)=0; else

22、w(i,j)=inf; end endendw(1,2)=400; w(1,3)=450; w(2,4)=300; w(2,21)=230;w(2,47)=140; w(3,4)=600; w(4,5)=210; w(4,19)=310;w(5,6)=230; w(5,7)=200; w(6,7)=320; w(6,8)=340;w(7,8)=170; w(7,18)=160; w(8,9)=200; w(8,15)=285;w(9,10)=180; w(10,11)=150;w(10,15)=160;w(11,12)=140;w(11,14)=130;w(12,13)=200;w(13,34

23、)=400;w(14,15)=190;w(14,26)=190;w(15,16)=170;w(15,17)=250;w(16,17)=140;w(16,18)=130;w(17,27)=240;w(18,19)=204;w(18,25)=180;w(19,20)=140;w(19,24)=175;w(20,21)=180;w(20,24)=190;w(21,22)=300;w(21,23)=270;w(21,47)=350;w(22,44)=160;w(22,45)=270;w(22,48)=180;w(23,24)=240;w(23,29)=210;w(23,30)=290;w(23,44)

24、=150;w(24,28)=130;w(24,25)=170;w(26,27)=140;w(26,34)=320;w(27,28)=190;w(28,29)=260;w(29,31)=190;w(30,31)=240;w(30,42)=130;w(30,43)=210;w(31,32)=230;w(31,36)=260;w(31,50)=210;w(32,33)=190;w(32,35)=140;w(32,36)=240;w(35,37)=160;w(36,39)=180;w(36,40)=190;w(37,38)=135;w(38,39)=130;w(39,41)=310;w(40,41)=

25、140;w(40,50)=190;w(42,50)=200;w(43,44)=260;w(43,45)=210;w(33,34)=210;w(45,46)=240;w(46,48)=280;w(48,49)=200;for i=1:50 for j=1:50 if w(i,j)=0 w(j,i)=w(i,j); end endend%以k1=1，k2=25為例k1=1;k2=25;%初始化n=length(w);U=w;m=1;%利用求最短路的warshallfloyd算法的思想，求最短距離矩陣while m<=n for i=1:n for j=1:n if U(i,j)>U(i

26、,m)+U(m,j) U(i,j)=U(i,m)+U(m,j); end end end m=m+1;endu=U(k1,k2); %最短距離%求任意給定兩個(gè)點(diǎn)k1和k2間的最短路所包含的頂點(diǎn)p1=zeros(1,n);k=1;p1(k)=k2;v=ones(1,n)*inf;kk=k2;while kk=k1 for i=1:n v(1,i)=U(k1,kk)-w(i,kk); if v(1,i)=U(k1,i) p1(k+1)=i; kk=i; k=k+1; end endendk=1;wrow=find(p1=0);for j=length(wrow):(-1):1 p(k)=p1(wr

27、ow(j); k=k+1;end /Warshall-Floyd算法/3.2.2中n=2時(shí)/%以最短距離矩陣作為矩陣d的輸入for i=1:49 for j=i+1:50 D(i,j)=0; endendfor i=1:49 for j=i+1:50 for k=1:50 if d(k,i)>d(k,j) dmin=d(k,j); else dmin=d(k,i); end D(i,j)=D(i,j)+dmin; end endenddistance=D(1,2);station1=1;station2=2;for i=1:49 for j=i+1:50 if D(i,j)<dis

28、tance distance=D(i,j); station1=i; station2=j; end endend/3.2.2中n=2時(shí)/3.2.2中n=3時(shí)/%以最短距離矩陣作為矩陣d的輸入for i=1:48 for j=i+1:49 for k=j+1:50 D(i,j,k)=0; end endendfor i=1:48 for j=i+1:49 for k=j+1:50 for l=1:50 if d(l,i)<=d(l,j)&&d(l,i)<=d(l,k) dmin=d(l,i); else if d(l,j)<=d(l,k) dmin=d(l,j

29、); else dmin=d(l,k); end end D(i,j,k)=D(i,j,k)+dmin; end end endenddistance=D(1,2,3);station1=1;station2=2;station3=3;for i=1:48 for j=i+1:49 for k=j+1:50 if D(i,j,k)<distance distance=D(i,j,k); station1=i; station2=j; station3=k; end end endend/3.2.2中n=3時(shí)/3.3.2中n=2時(shí)/%以最短距離矩陣作為矩陣d的輸入for i=1:49 fo

30、r j=i+1:50 D(i,j)=0; endendn=65 67 42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 48 54 49 12 54 46 76 16 94 18 29 75 10 86 70 56 65 26 80 90 47 40 57 40 69 67 20 18 68 72 76 62 ;for i=1:49 for j=i+1:50 for k=1:50 if d(k,i)*n(k)>d(k,j)*n(k); dmin=d(k,j)*n(k); else dmin=d(k,i)*n(k); end D(i,j)=D(

31、i,j)+dmin; end endenddistance=D(1,2);station1=1;station2=2;for i=1:49 for j=i+1:50 if D(i,j)<distance distance=D(i,j); station1=i; station2=j; end endendmax=d(1,2); %max為任意兩點(diǎn)間的最短距離的最大值for i=1:49 for j=i+1:50 if d(i,j)>max max=d(i,j); end endendM=0; %M為所有教師人數(shù)for i=1:50 M=M+n(i);endmd=0;for i=1:

32、50 if d(i,station1)<=d(i,station2) md=md+n(i)*d(i,station1); else md=md+n(i)*d(i,station2); endendmanyidu=1-md/(M*max);R=md/M;/3.3.2中n=2時(shí)/3.3.2中n=3時(shí)/%以最短距離矩陣作為矩陣d的輸入for i=1:48 for j=i+1:49 for k=j+1:50 D(i,j,k)=0; end endendn=65 67 42 34 38 29 17 64 39 20 61 47 66 21 70 85 12 35 48 54 49 12 54 46

33、 76 16 94 18 29 75 10 86 70 56 65 26 80 90 47 40 57 40 69 67 20 18 68 72 76 62 ;for i=1:48 for j=i+1:49 for k=j+1:50 for l=1:50 if d(l,i)*n(l)<=d(l,j)*n(l)&&d(l,i)*n(l)<=d(l,k)*n(l) dmin=d(l,i)*n(l); else if d(l,j)*n(l)<=d(l,k)*n(l) dmin=d(l,j)*n(l); else dmin=d(l,k)*n(l); end end D(i,j,k)=D(i,j,k)+dmin; end end endenddistance=D(1,2,3);station1=1;station2=2;station3=3;fo