數(shù)學(xué)建模獎優(yōu)秀論文-交巡警服務(wù)平臺的設(shè)置與調(diào)度

1、交巡警服務(wù)平臺的設(shè)置與調(diào)度摘要警察肩負著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。交巡警服 務(wù)平臺的設(shè)置與調(diào)度直接關(guān)系到上述職能的實現(xiàn)，因此做好交巡警服務(wù)平臺的設(shè) 置與調(diào)度優(yōu)化極為重要。木文重點解決的是對某地區(qū)交警服務(wù)平臺的設(shè)置與調(diào)度 優(yōu)化問題.首先以a區(qū)為研究對彖，運用floyd算法，并對相應(yīng)的算法建立流程圖，計 算出各個節(jié)點之間的最短距離及其路徑，根據(jù)最短距離優(yōu)先以及在三分鐘內(nèi)盡量 到達報警地的原則，對各平臺分配管轄范圍.為了實現(xiàn)對a區(qū)13條交通耍道的快速封鎖，調(diào)度原則為在最短的時間實現(xiàn) 全部封鎖，根據(jù)由上界找上確界的原則得到封鎖全區(qū)的最短時間為8. 02分鐘以 及相應(yīng)封鎖的方案為：

2、服務(wù)站4578910ii12封鎖的要道6248293016222412時間（分鐘）0. 352.488.023.061.537. 713.80服務(wù)站1314151617131415封鎖的要道2321281438232128吋間（分鐘）0. 53. 274. 756. 744. 760. 53.274. 75對出警時間過長的問題,增加了四個節(jié)點分別為:28 （或29）、38 （或39）、 61、9,根據(jù)工作量不平衡的情況，采用貪婪算法，在工作量最大的服務(wù)平臺周 圍增加，新增個數(shù)由工作量的大小決定，為此得到新增的節(jié)點數(shù)為5,增加的位 置分別分布在：a5> a?、a?。以及a1a2a3處，綜合

3、以上兩個方面得到需增 加的服務(wù)站為：28 48 39 91 66.對問題二，針對全市六區(qū)現(xiàn)有交警服務(wù)平臺的設(shè)置進行合理性評價，既找到 了合理之處，同時也發(fā)現(xiàn)了存在的明顯不足，即c、f區(qū)交警平臺管轄的平均發(fā) 案率明顯高于其他區(qū)，需要對這兩區(qū)增加新的交巡警服務(wù)平臺，使全山每個區(qū)的 服務(wù)平臺處理的發(fā)案率相差不多，得到新增平臺數(shù)，然后結(jié)合地圖決定其位置。 當p處發(fā)生重大刑事案件，在全市范圍內(nèi)進行圍堵時，在滿足圍堵成功的前提下, 盡量縮小圍堵范圍，減少調(diào)度平臺的個數(shù)，從而得到最優(yōu)的圍堵方案，為此分析 計算a區(qū)是否能夠成功圍堵時發(fā)現(xiàn)，從a區(qū)逃跑后僅可能進入c區(qū)和f區(qū)，再對c、f區(qū)進行圍堵，圍堵時采用與問題

4、一中圍堵a區(qū)時相同的算法。舍掉了 b、d、e區(qū)，減少了圍堵范圍，比較合理。同吋，由于對a區(qū)進行了全封鎖，又對 c和f區(qū)進行了出口處得封鎖，形成三個封鎖圈，從而很大程度上降低了進一步 搜索的困難程度；當一個嫌疑犯確定了所在區(qū)時，可以將另外兩區(qū)解除封鎖，減 少對屈民生活的不便，因而比較合理.一問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負著刑事執(zhí)法、治安 管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實施這些職能，。每 個交巡警服務(wù)平臺的職能和警力配備基本相同。由于警務(wù)資源是冇限的，如何根 據(jù)城市的實際情況與需求合理地設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、 調(diào)度警務(wù)資源是警務(wù)部

5、門而臨的一個實際課題。試就某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問 題：（1）附件1中的附圖1給出了該市中心城區(qū)a的交通網(wǎng)絡(luò)和現(xiàn)冇的20個交 巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件2。請為各交巡警服務(wù) 平臺分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，盡量能在3分鐘內(nèi) 有交巡警（警車的時速為60km/h）到達事發(fā)地。對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進 出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個 路】，給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。根據(jù)現(xiàn)冇交巡警服務(wù)平臺的工作量不均衡和冇些地方出警時間過

6、長的實際 情況，擬在該區(qū)內(nèi)再增加2至5個平臺，確定需要增加平臺的具體個數(shù)和位置。（2）針對全市（主城六區(qū)a, b, c, d, e, f）的具體情況，按照設(shè)置交巡 警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參見附 件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點p （第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后 接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，給出調(diào)度全市交巡警 服務(wù)平臺警力資源的最佳圍堵方案。二模型的假設(shè)和符號說明2. 1模型假設(shè)（1）題口屮所給的數(shù)據(jù)真實可靠；（2）案件發(fā)生在節(jié)點處，對每個調(diào)度站的管轄的范圍確定到節(jié)點處，忽略 發(fā)生

7、在節(jié)點間路上的事故；（3）交巡警在工作時不會出現(xiàn)堵車等意外情況；（4）所有巡警執(zhí)行任務(wù)都是按照最短路徑行走；（5）犯罪嫌疑人的車速不超過60km/h2. 2.符號說明dmij: m區(qū)2號節(jié)點與丿號服務(wù)平臺之間的最短路徑距離；vv, : a區(qū)各節(jié)點所組成的無向圖的鄰接矩陣；比廠所有節(jié)點組成的無向圖的鄰接矩陣；fmj： m區(qū)第j號服務(wù)平臺的工作量；p腫m區(qū)第，號平臺的發(fā)案率（m代表a b c d e f）；其余符號文中說明三問題分析此題是與圖論有關(guān)的分配、調(diào)度問題，在進行具體的問題解決時，首先運用 matlab軟件根據(jù)題目中的各個節(jié)點的坐標將節(jié)點編號與具體圖形相接合，將圖 形中各點進行編號，并求出

8、有連線的點的距離。第一問要求a區(qū)各點在出現(xiàn)突發(fā)事件時，在3分鐘內(nèi)冇交巡警到達事發(fā)地， 即要求a區(qū)在劃分節(jié)點歸屬時，結(jié)點距離最近的平臺為隸屬平臺，即可滿足。對于服務(wù)站的指派問題，要求a區(qū)發(fā)生重大突發(fā)事件吋，對進出a區(qū)的13 條交通要道實現(xiàn)快速全封鎖的調(diào)度方案，以各種方案中最人調(diào)度距離的最小值為 目標函數(shù)，根據(jù)各個節(jié)點的最短距離表格(已求出)，就可以確定最優(yōu)調(diào)度方案。對服務(wù)站的再分配問題，是由于出于對某些工作交巡警服務(wù)平臺的工作量不 均和出警時間過長問題，則先單獨考慮出警時間過t問題，給出一種增加平臺的 個數(shù)和位置，然后根據(jù)工作量不均問題，找出不均點，在其周圍新增交警服務(wù)平 臺，即綜合權(quán)衡來決定新

9、増平臺的最后位置。第二問分析全市服務(wù)平臺設(shè)置合理性時，只針對發(fā)案率盡量平均的指標，按 照a區(qū)的分析方法進行分析，再根據(jù)平臺設(shè)置點自身的發(fā)案率大小評判合理性， 還可以考慮區(qū)域面積、人口密度等因素對平臺設(shè)置方案的影響來評判。當p點發(fā)生重大刑事案件吋，求最佳圍堵方案吋，在確保圍堵一定成功的前 提下，盡量減少交巡警力；盡量避免多區(qū)圍堵，首先計算a區(qū)情況及可能逃跑到 外區(qū)的路徑，再考慮外區(qū)的圍堵方案，采用排除法，逐步化簡，從而得到最佳的 圍堵方案。四模型的建立與求解4. 1問題1模型的建立與求解4.1. 1最短路徑模型1、當管轄范圍無交集時比巡警在城市出警，若要便得其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時，能在

10、3分鐘 內(nèi)有交巡警(警車的吋速為60km/h)到達事發(fā)地。為了盡量迅速，同時每個平 臺能夠有更大的覆蓋范圍。首先把該問題轉(zhuǎn)化為帶權(quán)無向圖最短路徑問題。a區(qū)各個平臺，節(jié)點，要道可以看做是圖g屮的節(jié)點，g = (v,e), it屮g屮邊的權(quán)為d(e),利用floyd算法可以計算出任意兩個節(jié)點之間的最短距離。floyd算法步驟由于是帶權(quán)無向圖最短路徑問題，用巴表示無向圖的帶權(quán)鄰接矩陣。矩陣屮菲 零元素的數(shù)值表示直接相連兩點間的距離，用+8表示沒有直接相連的節(jié)點，求 圖屮任意兩點間的最短路徑。令循環(huán)控制數(shù)p=l,對于一個n個點的帶權(quán)鄰接短 陣。(1)如果在兩節(jié)點i, j之間加入節(jié)點p,若+ vvp.

11、< w.，則將節(jié)點p放入路徑(i,j)中，則路徑變?yōu)?i,p,j)o若w(-p + wpjwy則路徑不變。p=p+l(2)判斷p>n是，則退出，否則回到1 遍丿力圖屮所冇節(jié)點，即可以得到任意兩點間的最短路徑矩陣d。a區(qū)具體計算見 后附錄lob.利用最短路徑優(yōu)先法劃分平臺管轄范圍在任意兩點間最短距離矩陣d屮，d的表示a區(qū)i號節(jié)點與丿號服務(wù)平臺之間 的最短路徑距離。由于要求在三分鐘內(nèi)到達的時間要求，且為了盡力提高出警速 度，完成刑事執(zhí)法治安管理交通管理服務(wù)群眾四大職能。我們選擇利用最短 路徑優(yōu)先的方法，為每個平臺設(shè)置服務(wù)范圍。根據(jù)前面的假設(shè)，案件或服務(wù)發(fā)生在路口節(jié)點上，因此該問題實際上

12、變化成了將 不同的m節(jié)點分配到n個平臺上的分配問題。在本題中m=72,n=20；本文在對平臺劃分管轄范圍的時候采用最短路徑優(yōu)先的原則，即將毎一個普 通節(jié)點，根據(jù)上述己經(jīng)計算好的最短路徑矩陣d, d的表示a區(qū)i號節(jié)點與廣號服 務(wù)平臺之間的最短路徑距離。令m,i=min(da,), jt屮i記錄最短路所對應(yīng)的服 務(wù)平臺。最終獲得結(jié)果如下表1 a區(qū)各交警服務(wù)平臺管轄范圍服務(wù)站號服務(wù)站所服務(wù)的路口11 67 68 69 71 73 74 75 76 7822 59 40 43 44 70 7233 54 55 64 65 6644 57 60 62 6355 49 50 51 52 53 56 58

13、596677 30 32 47 48 6188 33 4699 31 34 35 4510101111 26 271212 251313 21 22 23 2414141515 28 291616 36 37 381717 41 421818 80 81 82 831919 77 792020 84 85 86 87 88 89 90 91 92各平臺前往所管轄區(qū)域小節(jié)點所走的路徑為最短路徑，該最短路徑由前述 floyd算法求得，例如1號平臺前往71號所走路徑為1>69>71.2、當管轄范圍有交集時利用路徑圓法劃分管轄范圍以每個平臺節(jié)點為圓心，以三分鐘所能行走的最大路徑為半徑，在a

14、區(qū)域內(nèi) 每個平臺節(jié)點上畫出“路徑圓”。區(qū)別丁“直線距離圓二在路徑圓內(nèi)每個節(jié)點到圓 心的最短路徑一定小于等于路徑圓半徑，因此可以將每個圓心所包括的節(jié)點作為 平臺所管轄范圍。此種方法獲得的范圍是存在交集的表2冇交集劃分范圍服務(wù)站號服務(wù)站所服務(wù)的路口11 22 23 24 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5859 6022 20 22 23 24 46 47 48 49 50 51 52 53 54 55 56 5833 23 24 34 35 44 45 46 47 48 50 5644 37 38 40 42 43 44 45 4655 27

15、28 29 30 31 32 33 36 38 3966 27 28 30 31 32 36 38 3977 10 11 12 13 14 27 2888 11 12 13 14 15 16 17 25 26 2799 11 12 13 14 15 16 17 25 261010ii115671212 513123414141515 111613 14 15 16 17 25 261717 20 21 22 23 50 5218151 52 53 54 57 58 59 60 61 62 63 64 65 67 68 69 70 711947 48 49 50 51 53 54 55 56 5

16、7 58 59 60 61 62 632064 65 66 67 68 69 70 71對于有交集的情況，在交集內(nèi)的節(jié)點處發(fā)生事故時，如果只有一處發(fā)生故障, 則按照就近原則，如果有兩處發(fā)生事故，則兩個服務(wù)站都安排處理。4.1.2分配封鎖模型*西2兀1,2()x2兀22x2,20表示一個分派，其中©=0或1。并且一個要道兀13兀13,2：x3,2().僅能被分配到一個平臺屮。一個平臺小也最多僅能被分配到一個要道。因此20為要道i在當前分派下路徑上的距離。在所有的13個要道的分配 j=i方案中，需要盡可能的快速保證在最短的時間內(nèi)，所有要道均被封鎖。也即使所 有要道的分配方案中最大的路徑盡

17、可能的短。因此要道分配的數(shù)學(xué)模型為：mnmax(z)20乙嚴工xydjj門工/=!20工冃=1xij gxij = 1195131 < j < 202模型的計算結(jié)合貪婪算法的思想，建立“木塞算法”模型計算法，解決此模型的計算。將一個木塞放入水屮，木塞一定能夠指示出水面的最小上界，但是在木塞指 示最小上界的過程中，必然有沉降與上升的過程。在上面的模型中，所冇路徑的 分配方案，便構(gòu)成了一潭水，分配的要求即是找到該潭水的最小上界，也即來尋 找分配路徑方案屮的最小上界數(shù)值。首先針對要道i,均有一部分平臺可以分配于該特定要道i,這些平臺便構(gòu)成 了要道i的可行域 =1表示j平臺可以被分配給要道

18、i, 6=0表示j平臺 不能被分配給要道i?？尚杏蚓仃嚨某跏贾凳且粋€全1的矩陣。接下來對所有需要的要道求解到達最遠平臺的長度，從屮選擇一個最小值 maxd,記錄該路徑的起點和終點，極為flagl,flag2o接下來，以這個maxd為 標準，若其他要道與平臺的距離出現(xiàn)了大于maxd的情況，則令爲=0,也即 將i的可行域中去掉平臺j。接下來需耍根據(jù)修改可行域后的結(jié)果，來判斷余下的節(jié)點述能否進行冇效的2013 20分配。當出現(xiàn)工爲=0或工工第<13,(心弘時，一定無法使 ；=1/=1 ；=1余下的要道成功分派。因此需要退后到上一步中次短的路徑，并進行以上同樣過 程。若可行威顯示分配可以保證后續(xù)

19、分配的執(zhí)行，則再次執(zhí)行上述過程，直到尋 找到最小上界為止。算法流程圖如下：結(jié)束圖1主要流程init圖2 change過程完成可行域的改變圖3 downward找到最小上界計算過程：1. 初始化/為13x20全1矩陣，根據(jù)前而計算所得獲得各個要道到各個平臺的 最短路徑矩陣d, maxd,i=min(max(d)o可得到要道12到平臺16為第一 個上界速度=km! min ,路程= 14.543如，可以得到所用的時間為14 543«14.543(min),2. 可以看出14.543并非最優(yōu)解，實際的時間述可繼續(xù)縮短。接下來對各個要道的可行域進行修改?？梢缘玫?00000001111110

20、10000_011011111111111000011111111 111111111111000000111111101000000000001 11111101000000000000 1111110100000000000011111000000000011111000011000000001111 10000011000011111111 11100111111011111111100011111111111111111001111111i1111111 1000001111113. 通過前所述judge (5),可以判斷可以對剩余節(jié)點進行分配，因此要進一步 下沉。4. 令d矩陣與5矩

21、陣元素相乘，從中再回到第一步進行，就可以得到最終結(jié)果, 最小的上界距離為80.155百米，29號要道由7號平臺負責(zé)。全部分配結(jié)果如 下表3封鎖結(jié)果服務(wù)站45789101112封鎖的要道6248293016222412時間（分鐘）0.352.488.023.061.537.713.80服務(wù)站1314151617131415封鎖的要道2321281438232128時間0.53.274.756.744.760.53.274.75即需要8.0155分鐘即可將全區(qū)封鎖。4.1.3平臺增加與評價模型根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警吋間過長的實際情況，擬在該區(qū)內(nèi)再增加2至5個平臺。增加平

22、臺的首要原則是，盡可能讓全區(qū)的每個節(jié)點有緊急事件發(fā)生時，在三分鐘內(nèi)都有交巡警到達；第二原則是，齊個交巡警服務(wù)平臺的工作量和出警時間盡可能均衡。就時間問題的討論 由問題1的分配數(shù)據(jù)結(jié)果（見附錄1）可得,節(jié)點2& 29, 3& 39, 61, 92四個節(jié)點在有突發(fā)事件發(fā)生時，三分鐘之內(nèi)沒有交巡警能夠到達，為能夠在此處有事故發(fā)生時，民警快速到達，需要在上述節(jié)點出增加服務(wù)平臺。由前述問題一中結(jié)果可知，節(jié)點28和29, 38和39距離很近，當一處右巡 警平臺時，另一處在三分鐘內(nèi)就能到達，因此這兩處各增加一個服務(wù)平臺即可。 所以根據(jù)三分鐘內(nèi)能夠處理突發(fā)事件的原則，應(yīng)增加四個節(jié)點，分別在29

23、 39 6192四處的附近；（2）就工作量的討論考慮合理分擔工作量這一因索，在未增加服務(wù)站的情況下通過建立工作量函 數(shù)：其中工 是對所有屬于j平臺的節(jié)點的求和，工作量的單位為1,得到調(diào)整 前a區(qū)的120號服務(wù)平臺的工作量如k:表4各平臺工作量平臺a2a3a4a5a6a7a8a9a。工作量9.39.76.45.810. 12.5& 758.21.6平臺ana2a3aya15ai6a7a|8a%a 20工作量4.64& 52.54.85.25.36. 13.411.5由上表可見，工作量的分配不均勻，最小為l6,表示該服務(wù)站只負責(zé)自己所在服務(wù)臺處，最大為11.5,求得20個服務(wù)臺的平

24、均工作量: 利用可以得到在這個區(qū)的平均工作量為：6.52 o當增加四個服務(wù)站時這個區(qū)的平均工作量為：5.43,綜合分擔工作量來看需 要在a】、a?以及4、&、之間附近增加服務(wù)站；綜合(1) (2)的兩種情況，91處得新增平臺可以減小舛。的工作量，企和出的工作量可以由39處新增平臺分擔，由于厲、a?處工作量仍然比較大，在這兩 處附近增加新的交巡警平臺，選定66號來完成此任務(wù)?？傊?8 48 39 66 91 五處增加服務(wù)站平臺；在考慮以上兩個因素的情況下，對路i進行新的安排，得到的結(jié)果如2表5服務(wù)站號服務(wù)站所服務(wù)的路口169 71 73 74 78240 43 44 70 72354

25、 55 64457 60 62 63549 52 53 56650 51 58 59732 47833 46934 35 451026112712251322 23 24142115311635 36 371741 421880 81 82 831977 792084 85 86 87 88282939384830 616665 67 75 769189 90 924. 2問題二模型的建立與求解4.2.1全市服務(wù)平臺評價模型合理性的評價：由題口屮所給的有關(guān)全市城區(qū)面積和城區(qū)人口的信息可得，各區(qū)的人口密度如下：2 0 8 611 11各區(qū)平均發(fā)案率各區(qū)平均發(fā)案率表6全市城區(qū)面積和城區(qū)人口的信息城

26、區(qū)編號abcdef人口密度（力人每平方公里）2. 700. 200. 220. 190. 180. 19交巡警平臺個數(shù)2081791511發(fā)案率總和124.566.4187.267.8119.4109.2每個平臺處理的平均發(fā)案率6. 238. 3011.017. 537. 969. 931平臺設(shè)置方案合理z處：（1）該山的絕大多數(shù)的交巡警平臺的設(shè)置點為發(fā)案率最高的節(jié)點，即是在市區(qū) 的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺，能夠快速的處理所發(fā)生的事 件，降低了出警時間，相對的減少了工作量，能夠更好的完成治安管理、交通管 理、服務(wù)群眾等職能。圖5各區(qū)平均發(fā)案率（2）從各區(qū)的平均發(fā)案率來看a區(qū)的平

27、均發(fā)案率較其他區(qū)域較小，由人口密度分析可知，a區(qū)為城市屮心 區(qū)域。其他區(qū)域人口密度較a區(qū)明顯小，而a區(qū)的交巡警平臺的數(shù)目也相對的多 于其他區(qū)域的數(shù)口，使得a區(qū)的交巡警平臺的平均發(fā)案率更為合理，能夠更好的 服務(wù)好市區(qū)居民。b、i）、e區(qū)的平均發(fā)案率比a區(qū)稍高，考慮到該三區(qū)的人口密度較小，加z 警力資源的冇限，該三區(qū)的平均發(fā)案率可以接受。2方案屮明顯不合理處：c、f兩區(qū)交巡警平臺的平均發(fā)案率明顯高，為明顯不合理處，不利于刑事執(zhí) 法、治安管理、交通管理、服務(wù)群眾。3、解決方案：增加相應(yīng)區(qū)交巡警平臺的個數(shù)，在交巡警平臺資源有限吋，由于c區(qū)各交巡警平臺的平均發(fā)案率最高，首先給c區(qū)增加，其次考慮f區(qū)。1若

28、要求各區(qū)每個交巡警平臺的平均發(fā)案率不超過8,則需要增加的平臺的 個數(shù)如下：表7城區(qū)編 號abcdef新增平 臺個數(shù)017003壇后的 發(fā)案率6.237.387.807.537.967.802 c區(qū)新增加平臺的具體位置:首先，在原c區(qū)交巡警平臺個數(shù)時，按照“節(jié)點距離哪個平臺最近，隸屬個 平臺管理”原則劃分c區(qū)各個節(jié)點的歸屬。由matlab軟件，讓算出c區(qū)兩兩節(jié) 點的距離矩陣（見附件），比較篩選得到各個節(jié)點的歸屈如2表8 c區(qū)分配結(jié)果編號隸屬該平臺分配的站點1166、 262、 263、 264、 2652167、 248、 249、 250、 251、 252、 255、 258、 259、 2

29、60、 2613168、 189、 190、 191、 1924169、 2545170、 222、 223、 224、 225、 226、 273、 276、 277、 2836171、 215、 216、 230、 231、 240、 241、 242、 243、 244、 246、 2537172、 217、 218、 227、 228、 2298173、 232、 233、 234、 235、 236、 237、 238、 239、 245、 2479174、 211、 212、 213、 214、 219、 220、 22110175、 183、 193、 194、 195、 196

30、、 197、 198、 19911176、 184、 185、 186、 187、 18812177、 200、 201、 20213178、 203、 204、 205、 206、 207、 208、 209、 210、 284、 286、 28714179、274、275、278、279、280、281、282、285、288、289、290、291、292、 295、 29615180、 268、 269、 270、 297、 298、 299、 300、 301、 302、 303、 304、 305、306、 307、 8308> 309、 310、 311、 312、 313

31、、 314、 315、 31616181、 266、 267、 317、 318、 31917182、 256、 257、 272、 293、 294c區(qū)各個交警平臺隸屈節(jié)點總的發(fā)案率:表9 c區(qū)各平臺總發(fā)案率編號123456789發(fā)案率6.313.54.73.412.215.5& 31510. 1編號1011121314151617發(fā)案率11& 14.311.318.426. 1& 5& 9分析上表可得，15號平臺發(fā)案率最高，14、8、6、5、2發(fā)案率相對較高， 結(jié)合地圖的實際情況，在上述平臺周圍增加新的平臺，以減少平臺的工作量，貝 體增加的結(jié)果為：c區(qū)在23

32、2、241、260、277、281、301、314處各增加一個交 巡鑿平臺。與c區(qū)類似處理方案，f區(qū)增加三個平臺，可考慮增加在發(fā)案率高、周圍平 臺工作量大的結(jié)點的周圍，f區(qū)在節(jié)點505、527、529處各增加一個交巡警平臺。 警力資源充足時，b區(qū)可以在155處增加一個平臺，使得六個區(qū)的平均發(fā)案率趨 于均勻o4. 2. 2全市封堵模型1. 模型建立地點f （第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警, 犯罪嫌疑人已駕車逃跑，現(xiàn)在需調(diào)動全市警力對嫌犯進行圍堵。堅持原則是在保 證必定圍堵成功的前捉下，盡量縮小圍堵范圍；各區(qū)交巡警在所屈區(qū)內(nèi)圍堵全市共有6個區(qū)，各區(qū)在對要道進行圍堵時，模

33、型采用問題二中模型。在確 定方案后，各區(qū)圍堵同吋進行2. 模型求解首先，觀察a區(qū)能否一定圍堵成功。據(jù)前所述，將a區(qū)全面封鎖的最短時間 是8.0155分鐘，因此將3+8. 0155=11. 0155分鐘犯罪嫌疑人仍未到達的a區(qū)的出 口點進行封鎖。首先由問題一可得到p點到各出站口的最短路徑，利用時間二路程/速度得到p點到各路口的最短-時間，如下:表10 p到a區(qū)各出口的最短時間a區(qū)出 口12141621222313.8103.313.313.915.3a區(qū)出 口2829303848628.89.21. 76.52.49.3將全區(qū)各岀站口封鎖的時間如下表:表11 a區(qū)出口封鎖用時出站口1214162

34、122232406.703.27. 70.53.8出站口282930384862284.88.03. 14.82.50.44.8因為，接到報警吋，嫌犯已逃跑3分鐘，所以當s+3w：時，嫌犯無法從出口 i逃脫。通過封鎖時間與犯罪嫌疑人到出口處的時間對比。可以得到只冇29、30、38、48是無法堵住的，所以在下圖屮標注的出口點 處進行圍堵：26%0a區(qū)400380360340320300280250300350400450圖6由此可以得到犯罪嫌疑人到達不了 b、e兩區(qū)，因此無需對b、e兩區(qū)進行 布控。利用floyd算法可以得到該市各節(jié)點之間的最短路徑(見附錄2),下面 對a區(qū)的29、30、38、4

35、8四個節(jié)點進行討論：(1) 對29節(jié)點的討論:犯罪嫌疑人走到出站口 29后的路線有29370371、2923()兩條路線走， 由各節(jié)點z間的最短路徑可以得到3229370的長度為16. 772km,從而得到32 到370的時間為16. 772min,封鎖370的最快的 平臺是320, 320到達370的最 短吋間是7. 81min,由于10.81<16.772 ,所以在犯罪嫌疑人趕到370站點吋能夠?qū)?其堵住，即犯罪嫌疑人只能到達d區(qū)的370路口處，不能到達d區(qū)的內(nèi)部，所以 只封鎖370這一路口即可；通過29230這條路線犯罪嫌疑人有可能進入c區(qū)，從最短路徑屮得到32到 29再到230的

36、距離為:17.94km,從而得到犯罪嫌疑人在這條路徑上的到達230 的吋間為17.94min, c區(qū)封鎖230的最快路徑為169封鎖230,所用吋間為 11. 06min,由11.06+3v 17.94可以知道犯罪分子不能從出站口 29處進入c區(qū)。(2) 分析30、48兩個點經(jīng)過這兩個點犯罪分子可以到達c區(qū)，因此耍對c區(qū)的所冇出站口進行封 鎖，c區(qū)封鎖的原則可以按照a區(qū)站點分配原則得到封鎖c區(qū)的方案，如下表所 示：表12封鎖方案平臺166167175176177178181封鎖的路口264248177183202203317時間6.63.79.04.36.54.45.5p到相應(yīng)路口的時間為27

37、20.525.320.327.921.825.2由以上的時間對比可以看出將c區(qū)全面封鎖的最長時間為9. 0214min, 9.0214-3=12.021 min是小于p到任何一個出口點的時間，所以將以上幾個點封鎖 后，犯罪分子不可能從c區(qū)逃離。(3)對38站點的討論犯罪分子經(jīng)過38站點后進入f區(qū)，因此要對f區(qū)進行封鎖，具討論類似于c 區(qū)，在此不再贅述，其封鎖方案及其所需時間如下：表13平臺479481483484485封鎖的路口578486483541572時間5. 73.9507. 0421.66p到相應(yīng)路口的時間為30.815.32724.821. 7由此得到的封鎖路徑如下圖所示:圖7從圖

38、中我們可以看到有些出口點處無需封鎖，犯罪分了也無法在該處逃離， 如a區(qū)的出站口 14, 16和22封鎖后將無需再對14封鎖，按照這樣的原則，對 封鎖路線上的點進行優(yōu)化，得到圍堵的點如下圖所標注的點以上是再利用警力最少的情況下能夠?qū)⒎缸锵右扇俗カ@，所封鎖的點為：10、14、177、 202、 203、 248、 264、 317 、 370、 486、 483、 541、 572、 57&但為了盡快抓捕犯罪嫌疑人，則應(yīng)防止犯罪嫌疑人在a、f、c區(qū)內(nèi)來回穿得到封鎖的點為:10、14、16、29、30、38、48、62、177、183、202、203、 248、 264、 317 、 370

39、、 486、 483、 541、 572、 578.但由于p到f區(qū)的561處的距離是8. 7969km,離561處最近的服務(wù)站是475, 其距離為：4. 3548km,這樣f區(qū)的561出站口在犯罪嫌疑人到達之前就封鎖，所 以犯罪分子到達不了 f區(qū)，只要對a、c進行封鎖即可得到的封鎖路口如下圖：圖10最終封鎖的路線是：10、16、164、177、183、202、203、317、349、369、561.這時能將犯罪嫌疑人堵住的時間為：9分鐘，這時最后一個堵上的路口是 177.得到命令的交巡警平臺，均立即行動前往所派點，即各行動交巡警都僅落后 嫌疑犯3分鐘。交巡警行動9分鐘后即可將犯罪嫌疑人堵住.五

40、模型的檢驗經(jīng)過對已建立數(shù)學(xué)模型的進一步思考，可以將所冇問題看成是問題的匹配與 調(diào)度來檢驗，在建立的模型的基礎(chǔ)上，再通過建立優(yōu)化的模型進行檢驗，從而確 定模型的可實用性。首先木著調(diào)動比較小的思想，建立目標函數(shù)，設(shè)第i個節(jié)點到第j個巡警服務(wù)站變動到第k個服務(wù)站，要使變動較小則要求-dik最小，所以建立的目標函數(shù)為:minz = （dif d乂 ）2在進行調(diào)整的原則上，要求服務(wù)站到出事點的用時不超過3分鐘，并且調(diào)整 后的每個服務(wù)區(qū)的工作量要在總平均工作量的附近波動，由于考慮到某些服務(wù)站 附近的節(jié)點較少，對工作量了下限不做要求，但工作量的上限不得高于平均工作 量+1,此處的上限值可以根據(jù)不同的地區(qū)要求

41、進行設(shè)定，由此得到了約束條件 為：4 <= 30工/加 v= 6.2, i = l,2,3.k = 21,22. .dik > 0不妨以這個模型對第一問的第三個問題進行檢驗，得到每個服務(wù)區(qū)的節(jié)點如卜圖所示,服務(wù)站號服務(wù)站所服務(wù)的路口169、 71、 73、 74、 78240、 43、 44、 70、 72354、 55、 64、457、 60、 62、 63549、 52、 53、 56650、 51、 58、 59732、47833、46934、 35、 451026112712251322、 23、 24142115311635、 36、 371741、421880、 81、

42、 82、 83、 841977、792085、 86、 87、 88282939384830、616665、 67、 75、 769189、 90、 92表12對比第一問的第三個問題的結(jié)果可以得到只有其中的一組是不同的，即原來 20組的84分配到了 18組，經(jīng)過驗證得到84到18和20的距離是一樣的，因此在滿足目標函數(shù)最小的要求，按照faj = x pm得到原模型中1的工作量為93,5的工作量為10. 1, 7的工作量為8. 7,20的工作量為11. 5,經(jīng)調(diào)整后得到1的工作量為5,5的工作量為4. 2, 7的工作量為2. 8,20的工作量為4. 6,兩個組的數(shù)據(jù)都在要求之內(nèi)，也就是說在這一問

43、中兩個解都符合要求，且均為最優(yōu) 解，由此可以驗證模型是可實用的。六模型的優(yōu)缺點:優(yōu)點：1、模型在已冇算法的基礎(chǔ)上進行了改進，得到了適合本類問題的可實用算法；2、在進行圍堵的過程中，分塊處理，使得問題的復(fù)雜程度降低，得到了更符合 實際的圍堵方案；缺點：1、算法的復(fù)雜程度沒冇降低，運算的量較大，對于數(shù)據(jù)量稍有增加的問 題，所用時間會增加較快2、模型的檢驗較為復(fù)雜，沒冇尋找到一個簡單的檢驗指標。參考文獻【1】姜啟源，數(shù)學(xué)模型（第三版），北京：高等教育出版社，2003【2】耿國華，數(shù)據(jù)結(jié)構(gòu)c語言描述，西安:西安電子科技大學(xué)出版社，2002【3】韓屮庚，數(shù)學(xué)建模方法及其應(yīng)用（第二版），北京：高等教育出版社，2009附錄1:各區(qū)域標號圖380360340320300280160125433-2971 磁-10附錄"8£昭2-643幺9 a47493_-t677專978659蝕30346v5 m3£7 3<39v7<3840-6000450i11 1161*162 -1581