數(shù)學(xué)建模交巡警平臺的設(shè)置與調(diào)度

1、交巡警服務(wù)平臺的設(shè)置與調(diào)度一、問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺。每個(gè)交巡警服務(wù)平臺的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個(gè)實(shí)際課題。試就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：（1）附件1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2。請

2、為各交巡警服務(wù)平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車的時(shí)速為60km/h）到達(dá)事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺的警力最多封鎖一個(gè)路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時(shí)間過長的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺，請確定需要增加平臺的具體個(gè)數(shù)和位置。（2）針對全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參見附件）

3、的合理性。如果有明顯不合理，請給出解決方案。如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。二、問題分析2.1問題一（1）問要求為A區(qū)的20個(gè)交巡警服務(wù)平臺劃分管轄范圍，使每個(gè)路口盡量在3分鐘內(nèi)能夠由交巡警趕到。根據(jù)實(shí)際情況，每個(gè)交巡警服務(wù)平臺的資源是基本均衡且有限的。我們規(guī)定xij=1, 路口i被平臺j管轄0，路口i不被平臺j管轄，則此問題可看作是一個(gè)多目標(biāo)01規(guī)劃問題。目標(biāo)函數(shù)為：一：盡量多的路口能由交巡警在3分鐘內(nèi)趕到；二：若某路口不能由交巡警在3分鐘內(nèi)到達(dá)，則交巡警

4、到達(dá)此路口的時(shí)間應(yīng)盡量短；三：各交巡警平臺的工作量盡量均衡。求解此模型時(shí)，首先用matlab對數(shù)據(jù)進(jìn)行初步整理，然后將目標(biāo)一、二作為約束條件把多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)01規(guī)劃問題，利用lingo軟件求解。 （2）問中要求對進(jìn)出A區(qū)的交通要道實(shí)現(xiàn)快速全封鎖?？梢詫r(shí)間最小化問題轉(zhuǎn)化為距離最短問題。建立以平臺到封鎖的交通要道中的最長距離最短為目標(biāo)函數(shù)，以一個(gè)平臺的警力最多封鎖一條要道、每條要道必須被一個(gè)平臺封鎖為約束條件的規(guī)劃模型。將此模型用lingo軟件解出后，有多種調(diào)度方案，我們可以繼續(xù)建立以封鎖交通要道的總距離最短為目標(biāo)函數(shù)，以解出的最長距離的最小值為約束條件的規(guī)劃模型進(jìn)行進(jìn)一步優(yōu)化，用lin

5、go解出最終的封鎖調(diào)度方案。 （3）問要求增加平臺，解決平臺工作量不均衡和某些地方出警時(shí)間過長的問題。在（1）問中得到28,29,38,39,61,92這6個(gè)路口不能由交巡警在3分鐘內(nèi)到達(dá)。只要在離這6個(gè)路口距離不大于3km的路口處增加平臺，就可以使得所有路口都能由交巡警在3分鐘內(nèi)到達(dá)，可以認(rèn)為解決了出警時(shí)間過長的問題，并且可以求解出應(yīng)增加的最少平臺數(shù)。進(jìn)而解決工作量不均衡的問題，可建立01變量fj=1, 在路口j處增加平臺0, 不在路口j處增加平臺，將平臺工作量均衡度最大為目標(biāo)函數(shù)，將解出的增加平臺的可行數(shù)量作為約束條件建立規(guī)劃模型，用lingo可求解出增加平臺的具體位置。最后綜合分析出應(yīng)增

6、加的平臺數(shù)量和具體位置。三、基本假設(shè)與符號說明3.1基本假設(shè)1.假設(shè)每個(gè)巡警服務(wù)臺的職能和警力配備基本相同； 2.假設(shè)每個(gè)路口只由一個(gè)巡警服務(wù)平臺進(jìn)行管轄； 3.假設(shè)每個(gè)巡警服務(wù)平臺至少管轄一個(gè)路口； 4.假設(shè)巡警都按最短路徑到達(dá)各案發(fā)路口； 5.假設(shè)每個(gè)路段道路暢通，可以雙向行駛，沒有堵車現(xiàn)象；6.假設(shè)犯罪案件都在路口上發(fā)生； 7.假設(shè)在重大案件發(fā)生時(shí)，每個(gè)平臺只有封鎖一個(gè)路口的能力； 8.工作量：每個(gè)巡警服務(wù)臺所管轄范圍內(nèi)的所有路口案發(fā)率之和； 9.出警時(shí)間：巡警到達(dá)案發(fā)路口所需時(shí)間； 10.每個(gè)區(qū)的交巡警平臺只可管轄本區(qū)內(nèi)的路口，不可跨區(qū)管轄。11.假設(shè)巡警車和犯罪嫌疑人的車行駛中速度保

7、持勻速且車速均為60km/h；12.假設(shè)巡警在接到報(bào)案后并不知道逃犯的逃跑方向；3.2符號說明1. xij=1, 路口i被平臺j管轄0，路口i不被平臺j管轄；2. dij：路口i到j(luò)的最短距離；3. U0：交巡警能夠在3分鐘內(nèi)到達(dá)的路口集合；4. Vi：能夠在3分鐘內(nèi)到達(dá)路口i的交巡警平臺的集合；5. U1：交巡警不可在3分鐘內(nèi)到達(dá)的路口集合；6. ri：第i個(gè)路口的發(fā)案率；7. r：交巡警服務(wù)平臺的平均工作量；8. rrj：平臺j的工作量；9. yij=1, 第i條交通要道由交巡警服務(wù)平臺j封鎖0，第i條交通要道不由交巡警服務(wù)平臺j封鎖；10. sij：第i條交通要道到平臺j的最短距離；11

8、. fj=1, 在路口j處增加平臺0, 不在路口j處增加平臺；12.n：增加的交巡警服務(wù)平臺的個(gè)數(shù)；四、模型的建立與求解4.1 問題一（1）：管轄區(qū)域的確定4.1.1 模型建立 此問要求在A區(qū)20個(gè)交巡警服務(wù)平臺位置確定的情況下，分配管轄范圍，使交巡警盡量能夠在3分鐘內(nèi)到達(dá)事發(fā)地。本文考慮了三個(gè)分配原則即為三個(gè)目標(biāo)。一：交巡警盡量能在3分鐘內(nèi)到達(dá)事發(fā)地。二：在不能滿足3分鐘內(nèi)到達(dá)事發(fā)地的情況下，交巡警到達(dá)事發(fā)地的時(shí)間應(yīng)盡量短。三：由于各交巡警平臺的職能和警力配備基本相同，因此各交巡警平臺的工作量應(yīng)盡量均衡。由以上分析可知，此問為一個(gè)多目標(biāo)規(guī)劃問題。對于第一個(gè)目標(biāo)，可以轉(zhuǎn)化為交巡警能在3分鐘內(nèi)到

9、達(dá)管轄路口的路口數(shù)應(yīng)盡量多。建立01變量：xij=1, 路口i被平臺j管轄0，路口i不被平臺j管轄。假設(shè) dij為路口i到交巡警平臺j的最短距離。U0為交巡警可在3分鐘內(nèi)到達(dá)的路口集合，即若j1,220, 使得dij3km，則iU0。Vi為能夠在3分鐘內(nèi)到達(dá)路口i的交巡警平臺的集合。此目標(biāo)可表示為：maxf1=iU0jVixij； 對于第二個(gè)目標(biāo)，假設(shè)U1為交巡警不可再3分鐘內(nèi)到達(dá)的路口集合，此目標(biāo)可表示為：minf2=j=120xij*dij, iU1;對于第三個(gè)目標(biāo)，本文用每個(gè)平臺所管轄路口發(fā)案率的和表示平臺的工作量，用工作量的變異系數(shù)來度量各平臺工作量的均衡度，各平臺工作量越均衡，變異系

10、數(shù)越小。假設(shè)ri為第i個(gè)路口的發(fā)案率，r為所有平臺的平均工作量，rrj為第j個(gè)平臺的工作量，此目標(biāo)可表示為：minf3=119j=120(rrj-r)2r; r=i=192ri20;滿足條件為：1.每個(gè)路口由一個(gè)交巡警服務(wù)平臺管轄：j=120xij=1, i=1,292;2.每個(gè)交巡警服務(wù)平臺至少管轄一個(gè)路口：i=192xij1, j=1,220;3.每個(gè)交巡警服務(wù)平臺必須管轄本路口：xij=1, i=j;i,j=120; 4.1.2 模型求解 對于模型中的多目標(biāo)規(guī)劃問題，本文將之轉(zhuǎn)化為單目標(biāo)規(guī)劃問題。首先將目標(biāo)一和目標(biāo)二解出，然后將這兩個(gè)目標(biāo)作為約束條件，以目標(biāo)三作為最終的單目標(biāo)用lingo

11、軟件求出最終解。1.各路口間最短距離的確定。首先用公式算出兩兩之間的距離（如果有路），得出582*582的鄰接矩陣，其中矩陣中的元素表示兩兩之間的距離，若不存在路，則用一個(gè)較大的數(shù)代替,在matlab環(huán)境下利用floyd算法求出最短路程矩陣D，矩陣D中兩兩之間的距離即為dij。程序見附錄一。 Floyd算法的基本步驟如下： 令dij是頂點(diǎn)vi到頂點(diǎn)vj 的最短距離, wij是頂點(diǎn)vi到vj的權(quán)。STEP1:輸入臨界矩陣W。對所有i, j, 有dij=wij, k=1。STEP2: 更新dij。對所有i, j, 若dik+dkjdij, 則令dij=dik+dkj。STEP3: 若dii0, 則

12、存在一條含有頂點(diǎn)vj 的負(fù)回路, 停止; 或者k=n停止, 否則轉(zhuǎn)到STEP2。 2.目標(biāo)一和目標(biāo)二的求解 用MATLAB編程從上述得到的各路口的最短距離中抽出92個(gè)路口分別到20個(gè)服務(wù)平臺的最短距離。篩選出dij3km的點(diǎn)，求出交巡警可在3分鐘內(nèi)到達(dá)的所有路口（集合U0），剩下的路口則為交巡警不可能在3分鐘內(nèi)到達(dá)的路口（集合U1）。程序見附錄二。 為滿足目標(biāo)一，只需要滿足：j=120xij*dij3, iU0; 為滿足目標(biāo)二，將集合U1=28,29,38,39,61,92中的路口直接分配給距離此路口最近的交巡警服務(wù)平臺。結(jié)果如下：交巡警平臺15162720管轄路口28、2938396192

13、3.最終方案的確定 將目標(biāo)一、二作為約束條件，目標(biāo)三作為最終單目標(biāo)，可得如下最終模型：minf3=119j=120(rrj-r)2rs.t.r=i=192ri20;j=120xij*dij3, iU0;xij=1, iU1, j=vi;j=120xij=1, i=1,292;i=192xij1, j=1,220;xij=1, i=j;i,j=120;xij0,1其中vi表示交巡警不能在3分鐘內(nèi)趕到的路口i被平臺vi管轄。用lingo求解得最小變異系數(shù)為1.934，,最終分配方案如下（程序見附錄三）：交巡警服務(wù)平臺管轄路口工作量（次）11、67、69、76、77、79、807.122、40、43

14、、73、757.233、44、54、55、66、686.944、57、60、62、63、64、657.355、49、53、56、596.166、50、51、52、586.177、30、485.988、34、37、475.899、32、33、456.41010、29、394.41111、26、274.61212、254.01313、21、22、23、248.51414、38、614.31515、28、315.01616、35、36、466.31717、41、42、70、727.01818、74、84、85、87、887.21919、71、78、81、82、837.12020、86、89、90、9

15、1、927.34.2 問題一（2）：封鎖方案的確定4.2.1模型建立 本問要求調(diào)度20個(gè)交巡警服務(wù)平臺對A區(qū)的13條交通要道實(shí)現(xiàn)快速封鎖，且每個(gè)平臺最多封鎖一個(gè)路口。實(shí)現(xiàn)完全封鎖的時(shí)間取決于13條交通要道中被封鎖最長的時(shí)間。本文將時(shí)間問題轉(zhuǎn)化為距離問題。對13條要道實(shí)現(xiàn)最快封鎖，即是將平臺到13條被封鎖要道中的最長距離最小化。可建立01規(guī)劃模型。 建立01變量：yij=1, 第i條交通要道由第j個(gè)交巡警服務(wù)平臺封鎖0，第i條交通要道不由第j個(gè)交巡警服務(wù)平臺封鎖。假設(shè)sij為第i條交通要道到第j個(gè)平臺的距離。其中i=1,213;j=1,220。目標(biāo)函數(shù)：平臺到13條被封鎖要道中的最長距離最小 ：

16、mins=maxyij*sij i=1,213;j=1,220約束條件為：1.每條交通要道必須有一個(gè)交巡警服務(wù)平臺進(jìn)行封鎖。j=120yij=1, i=1,213。 2.每個(gè)交巡警平臺最多封鎖一條交通要道。i=113yij1, j=1,220。綜上所述，此優(yōu)化模型為：mins=max1i201j13yij*sijs.t.j=120yij=1, i=1,213;i=113yij1, j=1,220;yij0,1用smin表示上述模型解出的最小值。將上述模型解出后，依然存在多種封鎖方案，我們做進(jìn)一步優(yōu)化?？紤]到警力資源有限，以封鎖距離總和最短為目標(biāo)函數(shù)，上述模型解出的最小值smin為約束條件進(jìn)一步

17、做01規(guī)劃求得最終封鎖的調(diào)度方案。模型如下：minf4=i=113j=120yij*sijs.t.max1i201j13yij*sijsmin;j=120yij=1, i=1,213;i=113yij1, j=1,220;yij0,14.2.2模型求解首先從最短路程矩陣D中，篩選出13條交通要道到各交巡警平臺的最短距離，并且依照13條交通要道的順序進(jìn)行113編號，得到13*20的要道和平臺間的距離矩陣。然后用lingo對上述兩個(gè)模型分別進(jìn)行編程求得最優(yōu)解。程序分別見附錄四與附錄五。最終結(jié)果如下：smin=8.02km，最短封鎖時(shí)間為8.02min。封鎖方案為：路口標(biāo)號1214162122232

18、4282930384862平臺標(biāo)號12169141013111578254時(shí)間（min）06.471.533.267.020.503.814.758.023.063.982.480.354.3 問題一（3）：確定增加平臺的個(gè)數(shù)與位置4.3.1 模型建立本問要求在A區(qū)內(nèi)增加2至5個(gè)平臺，解決現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時(shí)間過長的實(shí)際情況。本文認(rèn)為只要增加平臺能夠使得A區(qū)全部路口可以由交巡警在3分鐘內(nèi)全部趕到，（A區(qū)所有路口到管轄平臺間的距離不大于3km），即是解決了出警時(shí)間過長的問題。可以由問題一（1）中的結(jié)果中求得最小應(yīng)增加的平臺數(shù)，具體求解過程見模型求解部分。然后我們在所有

19、路口都能夠由交巡警3分鐘內(nèi)到達(dá)的前提下，考慮如何解決平臺工作量不均衡的問題。 對于交巡警服務(wù)平臺工作量不均衡的問題，利用問題一（1）中的方法，用工作量的變異系數(shù)衡量平臺工作的均衡度，以工作量的變異系數(shù)取得最小值為目標(biāo)函數(shù)建立01規(guī)劃模型。建立01變量：fj=1, 在路口j處增加平臺0, 不在路口j處增加平臺， xij=1, 路口i被平臺j管轄0，路口i不被平臺j管轄。n 為新增加交巡警平臺的個(gè)數(shù)。目標(biāo)函數(shù)可表示為：minf5=119+n j=192(i=192xij*ri-r)2rr=i=192ri（20+n）;其中ri為路口i的發(fā)案率，r為所有平臺的平均工作量。約束條件為：1.交巡警平臺個(gè)數(shù)

20、為20+n：j=192fj=20+n; 2.所有路口到管轄平臺間的距離不大于3km：j=192xij*dij3, i=1,292； 其中dij為路口i和路口j之間的距離。 3.每個(gè)路口都要被一個(gè)平臺進(jìn)行管轄：j=192xij=1, i=1,292；4.每個(gè)交巡警服務(wù)平臺必須管轄本路口：xij=1, fj=1;i=j;i,j=192; 5.只有當(dāng)路口j處增加了平臺j時(shí)，才可以管轄其他的路口:xijfj, j=1,292; 6.第1,220個(gè)路口處原本就設(shè)有平臺：fj=1, j=1,220;綜上所述，此模型為：minf5=119+n j=192(i=192xij*ri-r)2rs.t.r=i=19

21、2ri（20+n）;j=192fj=20+n;j=192xij*dij3, i=1,292；j=192xij=1, i=1,292；xij=1, fj=1;i=j;i,j=192;xijfj, i=1,2,20, j=1,292；fj=1, j=1,220；xij、fj0,1;4.3.2 模型求解 由問題一（1）的求解可知，在A區(qū)現(xiàn)有20個(gè)平臺的設(shè)置下，集合U1=28，29，38，39，61，92中的路口不能由交巡警在3分鐘內(nèi)及時(shí)趕到。從最短路程矩陣D中搜索出A區(qū)距離U1中各路口距離小于等于3km的路口，結(jié)果如下：U1路口標(biāo)號282938396192符合條件的路口28,2928,2938,39

22、,4038,39,4048,6187,88,89,90,91,92 從上面結(jié)果可知，最少增加4個(gè)平臺才可以使得這6個(gè)路口可以由交巡警在3分鐘內(nèi)趕到，這樣就滿足了所有路口都可以由交巡警在3分鐘內(nèi)趕到。因此為解決有些地方出警時(shí)間過長的問題，需要增加4或5個(gè)平臺。 將n=4和n=5分別代入上述0-1規(guī)劃模型，用lingo求解，程序見附錄六，得到如下結(jié)果：增加平臺數(shù)平臺增加位置均衡度（變異系數(shù)）428、40、48、901.74910528、39、48、87、881.69758 從表格可以看出增加5個(gè)平臺要比4個(gè)平臺均衡度高，但是由于兩者均衡度相差并不大，都可以解決出警時(shí)間過長的問題，且實(shí)際問題中增加一

23、個(gè)平臺所需花費(fèi)很多，因此最終選擇為： 增加4個(gè)平臺，位置為路口28、40、48和87。4.4 問題二（1）交巡警平臺設(shè)置的評價(jià)與改進(jìn)現(xiàn)有交巡警平臺設(shè)置的合理性的評價(jià)本文對現(xiàn)有交巡警平臺的設(shè)置定義了兩個(gè)評價(jià)原則： 1.交巡警能在3分鐘內(nèi)到達(dá)案發(fā)路口 2.各平臺的工作量均衡度盡量高 依據(jù)這兩個(gè)評價(jià)原則，分別對6個(gè)區(qū)現(xiàn)有的平臺設(shè)置進(jìn)行評價(jià)。 首先將6個(gè)區(qū)的平臺依據(jù)問題一（1）的方式進(jìn)行管轄區(qū)域的劃分，得到結(jié)果如下：區(qū)域不能由交巡警3分鐘內(nèi)到達(dá)的路口個(gè)數(shù)（U1）U1路口所占總路口的比重平臺工作量均衡度（變異系數(shù)）A區(qū)66.5%1934B區(qū)68.2% 1925C區(qū) 47 30.5% 4083D區(qū) 122

24、3.1% 2253E區(qū) 32 31.1% 3798F區(qū) 35 32.4% 4562 對于原則一：A區(qū)和B區(qū)不能由交巡警在3分鐘內(nèi)到達(dá)的路口個(gè)數(shù)即U1路口個(gè)數(shù)比較少，較符合原則一的要求。C、E、F三個(gè)區(qū)U1路口所占比重過高，明顯不合理。對于原則二，在問題一（1）中，我們已經(jīng)分析到對于變異系數(shù)為1.934的A區(qū)，工作量的均衡度是比較好的，因此我們可以推測B區(qū)的均衡度也是比價(jià)好的。而C、E、F三個(gè)區(qū)的變異系數(shù)過高，因此均衡度較差。 綜上所述，A區(qū)和B區(qū)的設(shè)置較合理，D區(qū)稍不合理，而C、E、F區(qū)嚴(yán)重不合理4.4.2 交巡警服務(wù)平臺設(shè)置的優(yōu)化4.4.2.1 模型建立 由上面分析可知，很多區(qū)不能由交巡警在

25、3分鐘趕到的路口過多，出警時(shí)間過長，因此我們首要選擇增加交巡警服務(wù)平臺對每個(gè)區(qū)進(jìn)行優(yōu)化，優(yōu)化方式按照問題一（3）中的模型，對每個(gè)區(qū)有：1.集合U1中的路口表示不能由交巡警在3分鐘內(nèi)及時(shí)趕到的該區(qū)路口，從最短路程矩陣D中搜索出該區(qū)距離U1中各路口距離小于等于3km的路口，解出初步增加的平臺個(gè)數(shù)，使得該區(qū)每個(gè)路口都可由交巡警在3分鐘內(nèi)到達(dá)，解決了某些地方出警時(shí)間過長的問題。2解決平臺工作量不均衡的問題，建立如問題一（3）的模型：min f6=1Xm+n j=ZmYm(i=ZmYmxij*ri-r)2rs.t.r=i=ZmYmri（Xm+n）;j=ZmYmfj=Xm+n;j=ZmYmxij*dij3

26、, i=ZmYm；j=ZmYmxij=1, i=ZmYm；xij=1, fj=1;i=j;i,j=ZmYm;xijfj, i=ZmYm, j=Zmzm；fj=1, j=Zmzm；xij、fj0,1;其中Xm表示第m個(gè)區(qū)現(xiàn)有的平臺數(shù)量； Ym 表示第m個(gè)區(qū)起始的路口編號；Zm 表示第m個(gè)區(qū)終止的路口編號；zm表示第m個(gè)區(qū)現(xiàn)有最后一個(gè)平臺所在的路口編號。4.4.2.12模型求解將上述模型用lingo求解，得到最終結(jié)果如下：區(qū)域增加平臺個(gè)數(shù)增加平臺位置平臺工作量均衡度（變異系數(shù)）A428、40、48、901.74910B2104、1471.65277C20183、208、201、203、206、21

27、4、238、240、246、248、251、256、260、263、267、287、297、299、313、3151.97824D8329、332、333、338、344、362、369、3701.87644E15387、388、390、393、404、408、419、420、421、438、451、459、462、472、4741.85262F11486、505、510、503、515、520、525、540、541、558、5602.09867 在做如上優(yōu)化后，6個(gè)區(qū)的所有路口都可由交巡警在3分鐘內(nèi)到達(dá)，解決了某些地方出警時(shí)間過長的問題，而且6個(gè)區(qū)的工作量均衡度均在1.62.1之間，相比之

28、前得到了很大的提高。4.5問題二（2）圍堵方案的確定4.5.1模型建立根據(jù)題意，為了快速搜捕嫌疑犯，也就是說，各個(gè)平臺到封鎖路口的時(shí)間要最短，即最大搜索距離最短，首先求出需要封鎖的路口，具體做法為：先計(jì)算出嫌疑犯3分鐘走的路程為30，再以P32點(diǎn)為圓心，以30為半徑形成一個(gè)包圍圈，在這個(gè)包圍圈的鄰域內(nèi)選出若干個(gè)路口，再以這些路口為圓心，10t為半徑形成若干個(gè)包圍圈，從而建立模型如下： 目標(biāo)函數(shù)： 約束條件： 即 4.5.2模型求解將上述模型用lingo求解，（程序見附錄七）結(jié)果如下：路口平臺1517315193963821539517717720217520318023516236152641

29、82317178181325324328327332380362323387100418375483478541476572484578485479此時(shí)最短時(shí)間為：12.68027min。附錄附錄一（matlab）data=xlsread(cumcm2011B附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表.xls,1);x=data(:,2); %每個(gè)路口的橫坐標(biāo)y=data(:,3); %路口的縱坐標(biāo)rate=data(:,5); %路口的發(fā)案率boolean=zeros(582,582); route=xlsread(cumcm2011B附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表.xls,2)

30、;route=route(2:929,1:2);for i=1:928 %直接連接的兩路口，矩陣元素為1，否則為0 boolean(route(i,1),route(i,2)=1; boolean(route(i,2),route(i,1)=1;endfor i=1:582 boolean(i,i)=1;endw=zeros(582,582); %求出鄰接矩陣 for i=1:582 for j=1:582 if boolean(i,j)=1 w(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); else w(i,j)=9999; end endendD,R=floyd(w

31、);functionD,R=floyd(a) %弗洛伊德算法n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endend for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end endend附錄二（matlab）d=D(1:20,1:92);U0=;U1=;for i=1:92 sum=0; for j=1:20 if d(j,i)=1 U0=U0,i; else U1=U1,i; endend附錄三（lingo）

32、sets:lukou/1.92/:r;pingtai/1.20/:rr;link(lukou,pingtai):x,d;endsetsdata:r=ole(G:/數(shù)學(xué)建模/國賽/2011/B/cumcm2011B附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表.xls,rate);d=ole(G:/數(shù)學(xué)建模/國賽/2011/B/shortdistance.xlsx,distance);enddatamin=(z/19)0.5;for(pingtai(j):rr(j)=sum(lukou(i):x(i,j)*r(i);rp=sum(lukou:r)/20;z=sum(pingtai:(rr-rp)2)

33、;for(link(i,j)|i#ne#28 #and# i#ne#29 #and# i#ne#38 #and# i#ne#39 #and# i#ne#61 #and# i#ne#92:x(i,j)*d(i,j)=1);for(link:bin(x);附錄四（lingo）sets:yaodao/1.13/;pingtai/1.20/;link(yaodao,pingtai):s,y;endsetsdata:s=ole(G:/數(shù)學(xué)建模/國賽/2011/B/交通要道與交巡警平臺的距離.xlsx);enddatamin=max(link:y*s);for(yaodao(i):sum(pingtai(

34、j):y(i,j)=1);for(pingtai(j):sum(yaodao(i):y(i,j)=1);for(link:bin(y);附錄五（lingo）sets:yaodao/1.13/;pingtai/1.20/;link(yaodao,pingtai):s,y;endsetsdata:s=ole(G:/數(shù)學(xué)建模/國賽/2011/B/交通要道與交巡警平臺的距離.xlsx,s);enddatamin=sum(link:y*s);max(link:y*s)80.155;for(yaodao(i):sum(pingtai(j):y(i,j)=1);for(pingtai(j):sum(yaod

35、ao(i):y(i,j)=1);for(link:bin(y);附錄六（lingo）sets:lukou/1.92/:r,f;link(lukou,lukou):x,d;endsetsdata:r=ole(cumcm2011B附件2_全市六區(qū)交通網(wǎng)路和平臺設(shè)置的數(shù)據(jù)表.xls,rate);d=ole(shortdistance.xlsx,d);enddatamin=(z/23)0.5/rp;z=sum(lukou(j):(sum(lukou(i):x(i,j)*r(i)-rp)2);rp=sum(lukou:r)/24;sum(lukou:f)=24;for(lukou(i)|i#le#20:f(