上傳人：6***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：吳**（實(shí)名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時(shí)間：2021-11-11 格式：DOC 頁數(shù)：20 大?。?28KB 積分：28 舉報(bào) 版權(quán)申訴

1、2012年數(shù)學(xué)建模大賽全國一等獎(jiǎng)?wù)撐?交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度摘要本文結(jié)合某城市實(shí)際情況對交巡警服務(wù)平臺(tái)的設(shè)置和調(diào)度進(jìn)行了深入研究，解決了以下問題：借助于Warshall-Floyd算法得出了區(qū)任意兩點(diǎn)間的最短路，并按照距離最近原則將各路口分派給相應(yīng)的平臺(tái)，得到各平臺(tái)的管轄范圍（見表1），其中，除6個(gè)節(jié)點(diǎn)外，其余86個(gè)節(jié)點(diǎn)的出警時(shí)間均小于3分鐘。建立二部圖的最大匹配模型解決了13條要道快速全封鎖問題，得最短封鎖時(shí)間約8分1秒，各平臺(tái)警力調(diào)度方案如下：服務(wù)臺(tái)號(hào)4571011封鎖路口4830291221以出警時(shí)間不超過3分鐘為首要準(zhǔn)則分析得出需增加4個(gè)服務(wù)平臺(tái)，通過計(jì)算機(jī)搜索比較了所有可能的72

2、種方案后，按照工作量均方差最小原則確定出新增平臺(tái)位置分別為28、39、48、87號(hào)路口，此時(shí)，工作量均方差取得最小值2.3703。在引入影響巡警服務(wù)平臺(tái)設(shè)置合理性的3個(gè)指標(biāo)基礎(chǔ)上，建立熵權(quán)模糊評(píng)判模型，對平臺(tái)設(shè)置合理性進(jìn)行判決，得出現(xiàn)有平臺(tái)設(shè)置不合理，其中區(qū)和區(qū)尤為明顯，針對其工作量大且3km內(nèi)平臺(tái)覆蓋率低的情況提出了解決方案。證明了關(guān)于圍堵的一個(gè)結(jié)論，提出了一端圍堵法，確定出了為實(shí)現(xiàn)圍堵所需要封鎖的隨時(shí)間變化而變化的路口集合，并將其與全城所有服務(wù)平臺(tái)構(gòu)成動(dòng)態(tài)二部圖，根據(jù)匈牙利算法得出了在此方法下的最短圍堵時(shí)間為10.79分鐘，需調(diào)用37個(gè)平臺(tái)警力，具體圍堵方案如下：服務(wù)平臺(tái)171661671

3、68169170171172封鎖路口92248252175254178182213關(guān)鍵詞 Warshall-Floyd算法 二部圖 匈牙利算法 模糊評(píng)判 1一 問題的重述警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、服務(wù)群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警服務(wù)平臺(tái)。每個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門面臨的一個(gè)實(shí)際課題。試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問題：（1）附件1中的附圖1給出了該市中

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

5、況，按照設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案（參見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。二 模型的分析本題主要研究交巡警管轄范圍分配、設(shè)置與調(diào)度問題。能否及時(shí)響應(yīng)一個(gè)或者多個(gè)路口的服務(wù)請求，是此問題所迫切的要求。由于交巡警平臺(tái)設(shè)置及服務(wù)要求都在路口，自然可將問題抽象成圖論模型。管轄范圍的確立首先依賴于各節(jié)點(diǎn)間的最短路，這可借助于圖論中的最短路算法Warshall-Floyd得以解決

6、，進(jìn)而以最快出警時(shí)間為原則進(jìn)行分配。對于多個(gè)路口的同時(shí)請求服務(wù)，需要盡快的分配各個(gè)不同平臺(tái)警力到相應(yīng)路口，由于要求每個(gè)平臺(tái)至多服務(wù)一個(gè)路口，將問題轉(zhuǎn)化為由平臺(tái)和路口所構(gòu)成的二部圖的匹配問題。當(dāng)需要圍堵犯罪嫌疑人時(shí)，首要問題是確定需要封鎖的依時(shí)間變化的路口集合，進(jìn)而可將其轉(zhuǎn)化為動(dòng)態(tài)二部圖的匹配問題。在考慮已有交巡警設(shè)置方案合理性時(shí)，先結(jié)合全市的具體情況尋找決定六區(qū)各交巡警服務(wù)平臺(tái)設(shè)置合理性的一些指標(biāo)，采用熵權(quán)的模糊評(píng)判方法，對平臺(tái)設(shè)置合理性進(jìn)行判決，并針對判決結(jié)果對設(shè)置方案進(jìn)行合理的調(diào)控。三 模型假設(shè)1. 犯罪嫌疑人和警車速度均為60km/h；2. 服務(wù)平臺(tái)接警后即可立即出警；3. 一個(gè)服務(wù)平臺(tái)

7、的警力最多封鎖一個(gè)路口；4. 交巡警服務(wù)平臺(tái)均設(shè)在路口；5. 相鄰節(jié)點(diǎn)間的道路為直線段。四 符號(hào)說明：初始距離矩陣（表示路線的距離，若路口之間無直達(dá)路線，?。鹤疃叹嚯x矩陣：（=1,2,3，20）表示區(qū)的20個(gè)交巡警服務(wù)平臺(tái)：以為頂點(diǎn)劃分為邊集的二部圖：二部圖的匹配：嫌疑人或者警車的移動(dòng)速度五 模型的建立與求解5.1 基于Warshall-Floyd算法的最短距離分配5.1.1 基本思想運(yùn)用Floyd算法計(jì)算城區(qū)中任意兩點(diǎn)間的最短路程，并將每個(gè)路口交給距離最近的交巡警服務(wù)平臺(tái)管轄。5.1.2 最近距離分配算法Step1：由全市交通路口的路線及路口節(jié)點(diǎn)坐標(biāo)數(shù)據(jù)，由假設(shè)5根據(jù)勾股定理計(jì)算出初始距離

8、矩陣（程序見附錄1）。Step2：然后依據(jù)Warshall-Floyd算法得出任意兩個(gè)路口之間的最短距離矩陣（程序見附錄2），記其中的前20行為。Step3：對的每一列取最小值，并記錄最小值大于3km的數(shù)值，設(shè)第列的最小值由第行取得，則將路口交由第個(gè)服務(wù)平臺(tái)管轄（若有兩行均取得最小值則任取其一即可）（程序見附錄3）。5.1.3 分配結(jié)果及分析表1 A區(qū)交巡警平臺(tái)管轄范圍表巡警平臺(tái) 12345管轄的路口1、67、68、69、71、73、74、75、76、782、39、40、43、44、70、723、54、55、65、66 4、57、60、62、63、645、49、50、 51、52、53、56、

9、58、59巡警平臺(tái)678910管轄的路口67、30、32、34、47、48、61、8、33、469、31、34、35、4510巡警平臺(tái)1112131415管轄的路口11、26、2712、2513、21 、22 、23、 241415、28、29巡警平臺(tái)1617181920管轄的路口16、36、37、3817、41、4218、80、81、82、8319、77、7920、84、85、86、87、88、89、90、91、92由于1-20號(hào)設(shè)置了巡警平臺(tái)，因此由自己管轄， 28、29、38、39、61、92號(hào)路口與最近的巡警平臺(tái)的距離均大于3km，分別為4.75、5.70、3.41、3.68、4.19

10、、3.60（單位：km），即無法在3min內(nèi)到達(dá)。能在三分鐘之內(nèi)能到達(dá)的路口節(jié)點(diǎn)占總結(jié)點(diǎn)數(shù)的93.5%。5.2 基于二部圖的快速全封鎖方案由假設(shè)2可知，一個(gè)巡警平臺(tái)的警力最多封鎖一個(gè)路口，要實(shí)現(xiàn)快速全封鎖，就是要使13條交通要道在最短時(shí)間內(nèi)全部由20個(gè)巡警平臺(tái)中的某13個(gè)平臺(tái)一一封鎖（封鎖時(shí)間以最后一個(gè)路口被封鎖的時(shí)間計(jì)）。5.2.1 基于二部圖的快速全封鎖方案的思想對于某個(gè)時(shí)間，建立一個(gè)二部圖，其中分別表示13個(gè)要道與A區(qū)的20個(gè)服務(wù)平臺(tái)。邊表示平臺(tái)可在時(shí)間內(nèi)到達(dá)要道，即。使用匈牙利算法得到的最大匹配。如果飽和，表明可從得到一個(gè)全封鎖。否則，就增大時(shí)間，重新循環(huán)上述操作。5.2.2 基于二部

11、圖的快速全封鎖方案的實(shí)現(xiàn)設(shè)20個(gè)巡警平臺(tái)分別到達(dá)13個(gè)交通要道的時(shí)間從小到大依次是。設(shè)，由二部圖邊的構(gòu)造知。故若可在時(shí)間內(nèi)封鎖（即找到飽和的匹配），則一定可在時(shí)間內(nèi)封鎖。即有下述結(jié)論：結(jié)論1：最短封鎖時(shí)間一定是某個(gè)巡警平臺(tái)到達(dá)某個(gè)交通要道的時(shí)間。基于上述結(jié)論，封堵時(shí)間依次取，直到對應(yīng)的二部圖存在飽和的匹配，即可找到最短全封鎖時(shí)間。Step1：表示13個(gè)交通要道距離20個(gè)巡警平臺(tái)的最短距離矩陣，記20個(gè)巡警平臺(tái)分別到達(dá)13個(gè)交通要道的時(shí)間從小到大依次是.Step2：依次取,確定二部圖，記其對應(yīng)的鄰接矩陣為，其中Step3：使用匈牙利算法得到（）的最大匹配，若飽和，則當(dāng)前為最短全封鎖時(shí)間，算法終止

12、，否則轉(zhuǎn)Step2。5.2.3 最快封鎖方案及其檢驗(yàn)由附錄程序4，得最小全封鎖時(shí)間=8分1秒，此時(shí)對應(yīng)的二部圖具有一個(gè)飽和13個(gè)要道的匹配由此矩陣，得全封鎖方案如下（矩陣的1-13行分別表示12、14、16、21、22、23、24、28、29、30、38、48、62號(hào)路口，1-20列分別表示1-20號(hào)巡警服務(wù)臺(tái)）.表2 A區(qū)對13條要道的全封鎖方案服務(wù)臺(tái)號(hào)12345710封鎖路口38166248302912距離5.887.394.397.403.188.027.59服務(wù)臺(tái)號(hào)111213141516封鎖路口212224232814距離5.076.882.396.474.756.74經(jīng)檢驗(yàn)（上表第

13、3行），服務(wù)臺(tái)到各個(gè)對應(yīng)封鎖路口的距離均不超過8.02km（約合8分1秒）,表明所得結(jié)果是正確的。5.3 A區(qū)交巡警服務(wù)平臺(tái)調(diào)整方案5.3.1 交巡警平臺(tái)各指標(biāo)定義服務(wù)平臺(tái)工作量：指該服務(wù)平臺(tái)管轄的各路口節(jié)點(diǎn)日均報(bào)案率之和；某地的出警時(shí)間：指管轄該地的巡警從交巡警平臺(tái)到達(dá)該地的時(shí)間。5.3.2 總體調(diào)整思路交巡警服務(wù)平臺(tái)增設(shè)原則：以對轄區(qū)所有節(jié)點(diǎn)的快速響應(yīng)為首要考慮因素，統(tǒng)籌兼顧各服務(wù)平臺(tái)工作量的均衡性。即平臺(tái)設(shè)置的首要目標(biāo)是增加盡可能少的服務(wù)平臺(tái)（2-5個(gè)）以實(shí)現(xiàn)對該區(qū)所有節(jié)點(diǎn)3分鐘以內(nèi)的全覆蓋，并且在新增平臺(tái)后，全區(qū)所有路口節(jié)點(diǎn)的管轄權(quán)按就近原則重新分配后各平臺(tái)工作量盡可能均衡。Step1

14、：新增平臺(tái)數(shù)目確定篩選出出警時(shí)間長于3分鐘（即距離管轄平臺(tái)大于3千米）的路口節(jié)點(diǎn)，稱其為偏遠(yuǎn)節(jié)點(diǎn)。表3 長于三分鐘的偏遠(yuǎn)節(jié)點(diǎn)與巡警平臺(tái)的距離偏遠(yuǎn)節(jié)點(diǎn)282938396192出警距離（km）4.75.73.43.64.13.6上述6個(gè)出警時(shí)間超過3分鐘的節(jié)點(diǎn)可分為4組（如圖1所示），從最短距離矩陣中可知，不同組類節(jié)點(diǎn)間距離均大于6km，故新增一個(gè)節(jié)點(diǎn)至多能使一類節(jié)點(diǎn)的出警時(shí)間降到3分鐘以內(nèi)，因此至少需要新增4個(gè)服務(wù)平臺(tái)。圖1 四組偏遠(yuǎn)路口另一方面，從4組中各取一個(gè)節(jié)點(diǎn)作為服務(wù)平臺(tái)即可滿足對這6個(gè)節(jié)點(diǎn)3分鐘的全覆蓋。初步方案可定為在28、 38、 61、92位置設(shè)立服務(wù)平臺(tái)，從新分配管轄范圍后工作

15、量的均方差為3.1005。Step2：平臺(tái)位置的確定總體思想：新增四個(gè)平臺(tái)，在滿足所有節(jié)點(diǎn)出警時(shí)間均不超過3分鐘的前提下，使得調(diào)整后的工作量具有盡可能小的均方差。記為這6個(gè)節(jié)點(diǎn)（28、29;38、39;61;92）的3km以內(nèi)鄰域節(jié)點(diǎn)，因?yàn)橐粋€(gè)服務(wù)平臺(tái)最多只能覆蓋一個(gè)組類，故新增的4個(gè)節(jié)點(diǎn)應(yīng)分別取自以及。由最短距離矩陣得，故共有種新增方案。用計(jì)算機(jī)對這些方案進(jìn)行比較，選出使各服務(wù)平臺(tái)工作量方差最小的新增位置，分別為28、39、 48、87號(hào)，按5.1重新分配后工作量均方差為2.3703。圖2 兩種方案下不同平臺(tái)的工作量圖注釋：方案一為根據(jù)28,38,61,92共4個(gè)點(diǎn)選擇的分配方案結(jié)果 方案二

16、為根據(jù)28，39，48，87共4個(gè)點(diǎn)選擇的分配方案結(jié)果由圖可知方案二的各平臺(tái)工作量較方案一有明顯收斂，即各平臺(tái)工作量較均衡，工作負(fù)荷很大（9以上）和很?。?以下）的平臺(tái)數(shù)量都明顯減少，但圖中大部分平臺(tái)的工作量并未改變，這是由以下兩方面原因造成的：一是由于問題節(jié)點(diǎn)的位置原本就比較偏遠(yuǎn)，其周邊的節(jié)點(diǎn)有限，因此新增服務(wù)點(diǎn)后，能產(chǎn)生的影響有限；二是由于要優(yōu)先滿足3分鐘覆蓋這一限制條件，因此新增服務(wù)臺(tái)的位置被限定在一定的區(qū)域內(nèi)，無法全局安排，因此，只能產(chǎn)生局部影響。5.4基于熵權(quán)的交巡警服務(wù)平臺(tái)設(shè)置的模糊綜合評(píng)價(jià)模型5.4.1基本思想 先確定影響主城六區(qū)各交巡警服務(wù)平臺(tái)設(shè)置合理性的3個(gè)影響指標(biāo)（各區(qū)服務(wù)

17、平臺(tái)平均的工作量、各區(qū)服務(wù)平臺(tái)節(jié)點(diǎn)平均覆蓋率、各區(qū)服務(wù)平臺(tái)服務(wù)人口密度），再采用熵權(quán)的模糊評(píng)判方法，對平臺(tái)設(shè)置合理性進(jìn)行判決，并針對判決結(jié)果對設(shè)置方案進(jìn)行合理的調(diào)控。5.4.2確定影響合理性因素 根據(jù)設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，結(jié)合現(xiàn)有服務(wù)平臺(tái)工作量的不均衡和部分地方出警時(shí)間過長情況，可以確定出影響交巡警服務(wù)平臺(tái)設(shè)置合理性的3項(xiàng)指標(biāo)：服務(wù)平臺(tái)的工作量、服務(wù)平臺(tái)節(jié)點(diǎn)覆蓋率、平臺(tái)服務(wù)人口密度。 針對全市各區(qū)的具體情況，基于全局的考慮，先將各指標(biāo)具體闡述如下： 1）各區(qū)服務(wù)平臺(tái)的平均工作量2）各區(qū)服務(wù)平臺(tái)節(jié)點(diǎn)覆蓋率 基于第一問Warshall- Floyd算法計(jì)算出區(qū)中各路口與最近的巡警平臺(tái)的距

18、離均大于3km的服務(wù)平臺(tái)個(gè)數(shù)為6個(gè)的方法，求出全城582個(gè)節(jié)點(diǎn)間的最短路矩陣，通過Matlab編程依次可以算出剩余五區(qū)（）各個(gè)路口與最近的巡警平臺(tái)的距離均大于3km的服務(wù)平臺(tái)個(gè)數(shù)，記為平臺(tái)覆蓋不到的路口數(shù)，那么各區(qū)服務(wù)平臺(tái)節(jié)點(diǎn)覆蓋率為： 3）區(qū)服務(wù)平臺(tái)服務(wù)人口密度5.4.3 模型算法 Step1：建立影響交巡警服務(wù)平臺(tái)設(shè)置合理性的因素域 Step2：建立評(píng)判集 Step3：在影響交巡警服務(wù)平臺(tái)設(shè)置合理性的因素域與評(píng)判集之間進(jìn)行隸屬度分析，建立模糊關(guān)系矩陣 矩陣中表示因素域中第個(gè)因素對于等級(jí)域中第個(gè)等級(jí)的隸屬度。 Step4：確定，其為3個(gè)因素對交巡警服務(wù)平臺(tái)合理性指標(biāo)的權(quán)重，并滿足 Step5

19、：求出，評(píng)價(jià)結(jié)果屬于中最大值對應(yīng)的合理性等級(jí)。5.4.4 建立評(píng)價(jià)集 服務(wù)平臺(tái)設(shè)置合理性大小是相對且模糊的，不可能定性描述，是屬于模糊集理論。那么根據(jù)模糊數(shù)學(xué)理論，可以將3個(gè)指標(biāo)分為6個(gè)等級(jí)，分別為非常合理，較合理，合理，不是很合理，不合理，明顯不合理。 熵權(quán)法權(quán)重向量的確定 1）判斷矩陣權(quán)值 要比較3個(gè)指標(biāo)、對于服務(wù)平臺(tái)設(shè)置的影響，根據(jù)上述指標(biāo)計(jì)算公式，通過Excel和Matlab編程求解得各區(qū)服務(wù)平臺(tái)平均的工作量、各區(qū)服務(wù)平臺(tái)節(jié)點(diǎn)平均覆蓋率以及各區(qū)服務(wù)平臺(tái)服務(wù)人口密度（萬人/服務(wù)平臺(tái)）如下表：表4 6城區(qū)3項(xiàng)指標(biāo)的統(tǒng)計(jì)結(jié)果區(qū)域各服務(wù)平臺(tái)平均工作量各服務(wù)平臺(tái)節(jié)點(diǎn)平均覆蓋率各服務(wù)平臺(tái)服務(wù)人密度

20、A6.22593.75%3B8.391.78%2.625C11.01169.48%2.882D7.53376.92%8.111E7.9668.93%5.067F9.92767.59%4.818將上述6城區(qū)3項(xiàng)指標(biāo)歸一化為判斷矩陣： 2）3個(gè)評(píng)價(jià)指標(biāo)的熵值 根據(jù)熵權(quán)法的公式中熵的定義公式計(jì)算出3個(gè)評(píng)價(jià)指標(biāo)的熵值為： 5.4.5 模型的求解 交巡警服務(wù)平臺(tái)合理性模糊綜合評(píng)價(jià)等于與兩個(gè)矩陣的乘積， 即 Matlab編程（見附錄5）求解得： 結(jié)合評(píng)價(jià)指標(biāo)的熵值： 根據(jù)最大隸屬度原則,0.195最大，所對應(yīng)的是明顯不合理，故全市六區(qū)的巡交警服務(wù)平臺(tái)設(shè)置不合理。5.4.6解決方案 結(jié)合表4，發(fā)現(xiàn)區(qū)服務(wù)平臺(tái)

21、的平均工作量為11.011（發(fā)案率），是六個(gè)區(qū)中工作量最大的，而區(qū)服務(wù)平臺(tái)對道路節(jié)點(diǎn)的平均覆蓋率為69.48%，又是六個(gè)區(qū)中非常低的，服務(wù)人口還較少，說明區(qū)平臺(tái)設(shè)置很不合理，而區(qū)服務(wù)平臺(tái)平均工作量也很大，節(jié)點(diǎn)平均覆蓋率最低，區(qū)平臺(tái)設(shè)置也不合理。即： 1）從服務(wù)節(jié)點(diǎn)的覆蓋率出發(fā) 根據(jù)前面求得六區(qū)各路口與最近的巡警平臺(tái)的距離均大于3km的服務(wù)平臺(tái)個(gè)數(shù)和對應(yīng)的節(jié)點(diǎn)，得出、區(qū)交巡警平臺(tái)覆蓋不到3km部分路口如下：表5 C、F交巡警平臺(tái)未覆蓋路口城區(qū) 該城區(qū)覆蓋不到的節(jié)點(diǎn)名稱覆蓋不到總節(jié)點(diǎn)數(shù) 183，199，200，201，202，203，205，206，20747 486，487，505，506，50

22、7，508，509，510，51235故建議在上述孤立節(jié)點(diǎn)附近增設(shè)服務(wù)平臺(tái)，以增大服務(wù)節(jié)點(diǎn)的覆蓋率。 2）從服務(wù)平臺(tái)的工作量出發(fā) 從全市六區(qū)交通網(wǎng)絡(luò)與平臺(tái)設(shè)置的示意圖看出、區(qū)是在郊區(qū)，同時(shí)、兩區(qū)的工作量又很大，故建議在原有服務(wù)平臺(tái)上增加值班巡警人數(shù)基礎(chǔ)上，在所轄城區(qū)邊上安排機(jī)動(dòng)巡邏車，進(jìn)行機(jī)動(dòng)巡邏。5.5基于全動(dòng)態(tài)二部圖的圍堵方案要實(shí)現(xiàn)對犯罪嫌疑人的圍堵，最完美的設(shè)想是將犯罪嫌疑人剛剛經(jīng)過的節(jié)點(diǎn)和正在前往的節(jié)點(diǎn)分別封鎖，從而將犯罪嫌疑人限定在兩個(gè)有連線且已經(jīng)封鎖的節(jié)點(diǎn)間。5.5.1 一種嘗試的封堵方案：兩端封堵法由最短距離矩陣可以確定從32節(jié)點(diǎn)出城所需的最短時(shí)間，確定封堵時(shí)間上限設(shè)，記表示距離

23、32號(hào)節(jié)點(diǎn)車程不超過的所有路口，表示所有與中任一節(jié)點(diǎn)相鄰的路口集合，易知，若能在時(shí)刻封鎖，則是一個(gè)可行的圍堵時(shí)間。Step1：依次此取 ，Step2：建立二部圖,其中表示全城所有的服務(wù)平臺(tái)集合，其中的邊表示平臺(tái)可在時(shí)間內(nèi)到達(dá)路口，即與的車程不超過Step3：求的最大匹配，若飽和，算法結(jié)束，否則轉(zhuǎn)Step1。結(jié)果：執(zhí)行此算法未找到飽和匹配，表明此方案下不能完成圍堵任務(wù)。5.5.2 改進(jìn)的封堵方案：一端封堵法與兩端封堵法相對應(yīng)，一端封堵法在于封鎖，相應(yīng)于兩端封鎖法，此方法只需封鎖更少的節(jié)點(diǎn)。結(jié)論二： 若交巡警可在時(shí)間內(nèi)全封鎖，則嫌疑人無法逃離本市。證明：反證法。假設(shè)嫌疑人可以逃離本市，設(shè)其逃離本市

24、經(jīng)過的路口序列為：，其中表示本城17個(gè)出城口之一。因，顯然有。記，注意到，故。由的最小性，知。因相鄰路口，故，從而有. 另一方面，因包含了從32節(jié)點(diǎn)車程不超過的所有路口以及，故嫌疑人到達(dá)的時(shí)間大于. 這是一個(gè)矛盾，因?yàn)樵跁r(shí)刻已被某巡警封鎖，證畢。算法實(shí)現(xiàn)：將兩端封鎖法中的改為即可（程序見附錄6）。結(jié)果分析：當(dāng)時(shí)，算法找到一組圍堵方案如下表所示：表6 交巡警平臺(tái)要封鎖的路口號(hào)及其之間的距離服務(wù)平臺(tái)123451011121314封鎖路口8485901861932224471459487平臺(tái)與路口的距離（km）4.096.647.857.2210.27.713.816.45.059.64服務(wù)平臺(tái)16

25、17166167168169170171172173封鎖路口52192248252175254178182213221平臺(tái)與路口的距離（km）10.75.488.713.814.982.226.1784.899.7服務(wù)平臺(tái)174175178179320321372475476477封鎖路口274212275277370371491568530535平臺(tái)與路口的距離（km）6.996.493.17.818.9810.18.014.655.63服務(wù)平臺(tái)478480481482483484485封鎖路口544554555563528565567平臺(tái)與路口的距離（km）2.138.145.638.26

26、10.69.065.1檢驗(yàn)：由表中的平臺(tái)與路口的距離均不超過10.8km，結(jié)果合理。六 模型的評(píng)價(jià)與改進(jìn)6.1 模型的評(píng)價(jià)1.模型的優(yōu)點(diǎn)1）在設(shè)置新的交巡警平臺(tái)時(shí)，在優(yōu)先考慮到出警時(shí)間的同時(shí)也統(tǒng)籌兼顧到各平臺(tái)工作量的平衡性；2）運(yùn)用到了模糊評(píng)判模型，將模糊的且不易定性描述的合理性大小進(jìn)行量化評(píng)判。3）將封鎖固定路口及圍堵嫌疑人的問題統(tǒng)一轉(zhuǎn)化為依時(shí)間變化的二部圖的匹配問題，借助于匈牙利算法，得以簡單高效解決。2.模型的缺點(diǎn)過于強(qiáng)調(diào)出警時(shí)間（3km覆蓋），使得交巡警服務(wù)平臺(tái)的工作量不太均衡。6.2 模型的改進(jìn)放松對出警時(shí)間的要求，建立工作量和出警時(shí)間的多目標(biāo)規(guī)劃，以使得管轄方案的配置更為合理。參考

27、文獻(xiàn)1王文波，數(shù)學(xué)建模及其基礎(chǔ)知識(shí)詳解M，武漢：武漢大學(xué)出版社.2劉振航，數(shù)學(xué)建模，M北京：中國人民大學(xué)出版社，2004.3李明哲，金俊，石端銀，圖論及其算法M, 北京：機(jī)械工業(yè)出版社，2010.4劉衛(wèi)國，MATLAB程序設(shè)計(jì)教程M，北京：中國水利水電出版社，2005.5姜啟源，謝金星，數(shù)學(xué)建模案例選集M，北京：高等教育出版社，2006.19附錄1. A區(qū)初始距離矩陣MalLab程序function M=initdisM()load JDLX % 載入節(jié)點(diǎn)和路線的數(shù)據(jù)M=inf(92,92);for i=1:92 M(i,i)=0;endm,n=size(LX);for i=1:m start

28、=LX(i,1); endd=LX(i,2); if(start<=92&&endd<=92) M(start,endd)=sqrt(JD(start,1)-JD(endd,1)2+(JD(start,2)-JD(endd,2)2); M(endd,start)=M(start,endd); endend2最短距離矩陣functionD,R=floydwarshall()D=initdisM();n=length(D);for(i=1:n) for(j=1:n) R(i,j)=j; endendfor(k=1:n) for(i=1:n) for(j=1:n) if(

29、D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=k; end; end; endend3.管轄范圍的分配load JDLXD,R=floydwarshall()D20_92=D(1:20,1:92);Min=min(D20_92)a=zeros(92,1);for i=1:92 a(i)=find(D20_92(:,i)=Min(i);enda %分配方案b=zeros(20,1);for i=1:20 ctrlby_i=find(a=i); fananlv=JD(:,3); b(i)=sum(fananlv(ctrlby_i);end

30、b %每個(gè)平臺(tái)的工作量4.1匈牙利最大匹配算法%二部圖的最大匹配算法匈牙利算法%A為二部圖的矩陣表示%返回值M為最大匹配function M=maxmatch(A)m n=size(A);M=zeros(m,n);y=zeros(1,n);%求一個(gè)極大初始分配for i=1:m for j=1:n if(A(i,j)&y(j) M(i,j)=1; y(j)=1; break; end endendwhile(1) x=zeros(1,m); %0表示未標(biāo)記 y=zeros(1,n); for i=1:m if(any(M(i,:) %xi是非飽和的 x(i)=-(n+1); %標(biāo)記，-

31、表示未掃描, y共有n個(gè) end end while(1) %嘗試尋找M增廣鏈 flag=0; for i=1:m if(x(i)<0) %標(biāo)記但未掃描 x(i)=-x(i); %正號(hào)表已掃描 for j=1:n if(A(i,j)&y(j)=0&M(i,j)=0) y(j)=-i; flag=1;%出現(xiàn)新標(biāo)記的y end end end end if(flag=0) break;end flag=0; for j=1:n if(y(j)<0) y(j)=-y(j); for i=1:m if(A(i,j)&x(i)=0&M(i,j)=1) x(i)

32、=-j; flag=1;%出現(xiàn)新標(biāo)記的x end end end end if(flag=0) break;end end flag=0; for j=1:n if(y(j)>0&any(M(:,j) %Breakthrough:找到增廣鏈。存在一個(gè)標(biāo)記且非飽和的yj flag=1; k=y(j); M(k,j)=1; while(x(k)=n+1) %倒退求M增廣鏈，修改M M(k,x(k)=0; M(y(x(k),x(k)=1; k=y(x(k); end break; end end if(flag=0) break;end %Non-Breakthrough end 4.

33、2基于二部圖匹配的13條交通要道的封鎖方案m=13;n=20;FF=1:20;%20個(gè)服務(wù)平臺(tái)YD=12 14 16 21 22 23 24 28 29 30 38 48 62;%13個(gè)要道D=floydwarshall();L=D(YD,FF);l=sort(L(:);for i=1:length(l) a=l(i); A=(L<=l(i)+eps) %建立二部圖，其中邊表示在了平臺(tái)與要道距離不超過了l(i) Q=maxmatch(A)if (sum(Q(:)=length(YD) % 飽和13個(gè)路口 break; %找到最小的距離（時(shí)間） endenda 5.模糊評(píng)判程序functi

34、on Example8_6A=1/12,1/6,1/3,2/3,1/6,1/12;R=0.12 0.16 0.22 0.15 0.16 0.19; 0.20 0.20 0.15 0.16 0.15 0.14; 0.11 0.10 0.11 0.31 0.19 0.18 'fuzzy_zhpj(3,A,R) %調(diào)用綜合評(píng)判函數(shù)end%functionB=fuzzy_zhpj(model,A,R) %模糊綜合評(píng)判B=;m,s1=size(A);s2,n=size(R);if(s1=s2) disp('A的列不等于R的行');else if(model=1) %主因素決定型 for(i=1:m) for(j=1:n) B(i,j)=0; for(k=1:s1) x=0; if(A(i,k)<R(