2011全國大學(xué)生數(shù)學(xué)建模比賽全國二等獎(jiǎng)B

1、2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項(xiàng)填寫）：B 我們的參賽報(bào)名號為（如果賽區(qū)設(shè)置報(bào)

2、名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?江蘇省南京市東南大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期：2011年9月12日賽區(qū)評閱編號（由賽區(qū)組委會(huì)評閱前進(jìn)行編號）：2011高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會(huì)評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時(shí)使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會(huì)送交全國前編號）：全國評閱編號（由全國組委會(huì)評閱前進(jìn)行編號）：摘要： 為了更好地為人民服務(wù)，我們在城市的路口設(shè)立了許多交巡警服務(wù)平臺，然而由于警力資源的有限性，并基于節(jié)省資源的考慮，我們必須對交

3、巡警平臺進(jìn)行合理的建模，以求最佳方案。 交巡警平臺設(shè)置合理的原則有三：一者，出警時(shí)間不宜太長，以三分鐘為限；二，每個(gè)平臺的工作量不可相差過大；三，在必要的時(shí)候，能夠有效控制住關(guān)鍵要道，迅速完成圍堵任務(wù)。這是我們建模求解的目的所在。本題共有兩大問，五小問，分別是管轄范圍的合理分配，封鎖要道的警力安排，增加平臺彌補(bǔ)弊端，評價(jià)現(xiàn)有交巡警平臺分布并給出修正方案，對罪犯進(jìn)行圍堵。對于管轄范圍的合理分配，我們首先用出警時(shí)間小于三分鐘篩選出滿足條件的管轄大范圍，然后再在大范圍中建立優(yōu)化模型，平衡每個(gè)平臺的工作量，得到最優(yōu)解。對于罪犯的圍堵問題，我們用圖論中的生成樹來模擬罪犯出逃的路徑，通過封堵其葉結(jié)點(diǎn)來等價(jià)

4、實(shí)現(xiàn)對關(guān)鍵路口的封堵。由于算法比較復(fù)雜，我們通過模糊處理，成功算得一個(gè)完成封堵的時(shí)間為8.79分鐘可行解。關(guān)鍵詞：最短路徑；0-1規(guī)劃；多目標(biāo)規(guī)劃；生成樹；1問題重述警察肩負(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給出了該市中心城

5、區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見附件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)）的具體情況，

6、按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案（參7見附件）的合理性。如果有明顯不合理，請給出解決方案。如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。2. 問題分析“有困難，找警察”，為了更好地服務(wù)人民、打擊犯罪，在市區(qū)內(nèi)設(shè)立交巡警服務(wù)平臺已經(jīng)成為了一種新的治安方式。而有限的警務(wù)資源要求我們對平臺設(shè)置、管轄范圍和警力調(diào)度進(jìn)行合理的分配。本題正是基于這一實(shí)際課題，對某市設(shè)置交巡警服務(wù)平臺的相關(guān)情況進(jìn)行了建模與討論。問題一中的第一小問要求我們對中心

7、城區(qū)A的20個(gè)服務(wù)平臺進(jìn)行管轄范圍的分配。我們的首要要求是在所管轄區(qū)域內(nèi)出現(xiàn)突發(fā)事件時(shí)，服務(wù)平臺的交巡警能夠盡可能地在3分鐘之內(nèi)到達(dá)事發(fā)地，在盡可能滿足這一要求的情況下還要使各個(gè)服務(wù)平臺的工作量盡量均衡。我們可以建立分配管轄范圍的0-1規(guī)劃模型，以交巡警盡可能在3分鐘之內(nèi)到達(dá)事發(fā)地作為約束，各個(gè)服務(wù)平臺工作量均衡作為目標(biāo)函數(shù)進(jìn)行了最優(yōu)化求解，得出最合理的管轄范圍分布。第二小問要求我們調(diào)度20個(gè)平臺對13條交通要道進(jìn)行快速全封鎖，我們建立快速全封鎖的0-1規(guī)劃模型來求解這個(gè)問題。模型的規(guī)劃目標(biāo)主要有兩個(gè)，分別是完成全封鎖需要的時(shí)間和平均每條路封鎖的時(shí)間。如果輕視封鎖的完整性會(huì)使嫌疑人在某些路口有

8、機(jī)可乘，造成嚴(yán)重的損失和后果，所以我們可以采用分層求解法，首先以最大封鎖時(shí)間最小為目標(biāo)函數(shù)進(jìn)行規(guī)劃，得出一組最大封鎖時(shí)間相同的可行解，然后再在這些可行解中以平均封鎖時(shí)間最小為目標(biāo)函數(shù)進(jìn)行規(guī)劃得出一個(gè)最優(yōu)解。然后通過比較與以平均封鎖時(shí)間最小作為優(yōu)化目標(biāo)進(jìn)行規(guī)劃的平均封鎖時(shí)間，判斷解的合理性。第三小問要求我們增設(shè)25個(gè)平臺解決工作量不均衡和有些地方出警時(shí)間過長的情況。我們同樣可通過分層求解法來進(jìn)行規(guī)劃，以6個(gè)到最近平臺時(shí)間都超過3分鐘的節(jié)點(diǎn)作為出發(fā)點(diǎn)，先保證所有節(jié)點(diǎn)都處于至少一個(gè)平臺三分鐘出警的覆蓋范圍內(nèi)，然后再通過進(jìn)一步的規(guī)劃求出滿足該條件下工作量最平衡的增加方案。第二小題的第一問，我們?yōu)榱藢υ?/p>

9、市現(xiàn)有的服務(wù)平臺分布進(jìn)行評價(jià)，首先更具我們的擇優(yōu)規(guī)則：1宏觀上保證各個(gè)區(qū)域的工作量比較平均。2微觀上保證在每個(gè)區(qū)域內(nèi)盡量讓更多的點(diǎn)能被覆蓋在由以平臺為中心的覆蓋范圍之中，算出了最優(yōu)分配方案，然后將最優(yōu)分配方案與現(xiàn)有的服務(wù)平臺進(jìn)行比較，進(jìn)行評論。第二小問中要求我們?yōu)榱丝焖偎巡队?2號節(jié)點(diǎn)出逃的嫌疑犯，給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。我們可以利用圖論中的生長樹對嫌犯的出逃進(jìn)行模擬，建立生長樹模型，樹中結(jié)點(diǎn)生長的方向即為嫌犯出逃的方向，警方只要在嫌犯之前到達(dá)所有葉結(jié)點(diǎn)即表示圍堵結(jié)束。3模型假設(shè)1.假設(shè)案件均在節(jié)點(diǎn)上發(fā)生；2. 一個(gè)平臺的警力最多封鎖一個(gè)路口；3. 32號節(jié)點(diǎn)處犯罪嫌

10、疑人駕駛車的速度假定為和警車相同的60km/h；4. 警車只在節(jié)點(diǎn)上進(jìn)行圍堵；5. 犯罪嫌疑人呈輻射狀從32號節(jié)點(diǎn)向外逃竄，途中不回頭；4 符號說明符號說明第號節(jié)點(diǎn)和第號節(jié)點(diǎn)之間的直線距離表示節(jié)點(diǎn)是否在平臺的管轄范圍內(nèi)的0-1變量（在管轄范圍內(nèi)為1）第號節(jié)點(diǎn)和第號節(jié)點(diǎn)之間的最短距離第個(gè)節(jié)點(diǎn)的發(fā)案率第個(gè)要道是否由第個(gè)平臺封鎖（1表示是，0表示否）節(jié)點(diǎn)是否被平臺管理（1表示是，0表示否）號出口需要封鎖的最短路徑號平臺所管理節(jié)點(diǎn)的發(fā)案率和表示第個(gè)節(jié)點(diǎn)是否第個(gè)平臺的三分鐘覆蓋范圍內(nèi)（1表示是，0表示否）節(jié)點(diǎn)和節(jié)點(diǎn)間時(shí)間是否大于3分鐘（大于則為0）該市第32個(gè)節(jié)點(diǎn)、生長樹模型的葉結(jié)點(diǎn) 上表部分符號在某些

11、小節(jié)中如有不同含義，按照新定義。5模型建立與求解5.1 分配交巡警服務(wù)平臺管轄范圍圖1為A城區(qū)的交通網(wǎng)絡(luò)和平臺設(shè)置示意圖，我們從圖中和附表中可以確定A城區(qū)內(nèi)各節(jié)點(diǎn)及交巡警服務(wù)平臺的分布與位置。為交巡警服務(wù)平臺分配管轄范圍，我們的首要要求是在所管轄區(qū)域內(nèi)出現(xiàn)突發(fā)事件時(shí)，服務(wù)平臺的交巡警能夠盡可能地在3分鐘之內(nèi)到達(dá)事發(fā)地。在盡可能滿足這一要求的情況下，我們還要使各個(gè)服務(wù)平臺的工作量盡量均衡。圖1 A區(qū)的交通網(wǎng)絡(luò)與平臺設(shè)置的示意圖5.1.1 建立分配管轄范圍的0-1規(guī)劃模型據(jù)此，我們可以建立分配管轄范圍的0-1規(guī)劃模型，以節(jié)點(diǎn)是否在平臺的管轄范圍內(nèi)作為0-1變量，先通過節(jié)點(diǎn)到平臺的時(shí)間小于三分鐘這一

12、條件進(jìn)行篩選（若一個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)的時(shí)間均大于三分鐘則取其中時(shí)間最短的平臺），然后將工作量盡量均衡作為目標(biāo)進(jìn)行0-1規(guī)劃，我們就可以得出同時(shí)滿足兩個(gè)條件的最優(yōu)解。其中，我們已知警車的速度為60km/h，故我們可以把時(shí)間小于三分鐘的要求轉(zhuǎn)化為距離小于3000米。服務(wù)平臺的工作量是由平臺距案發(fā)地的距離和平臺管轄范圍內(nèi)的發(fā)案率同時(shí)決定的，由于警車由平臺趕往案發(fā)地的時(shí)間已均限定在三分鐘左右，故與處理案件的時(shí)間和工作相比可以不考慮路上的時(shí)間和工作量，所以我們可以以平臺管轄區(qū)域內(nèi)的總發(fā)案率來衡量該平臺的工作量，進(jìn)而可以以A城區(qū)內(nèi)20個(gè)平臺工作量的方差作為衡量工作量是否均衡的標(biāo)準(zhǔn)。我們的規(guī)劃目標(biāo)即為20個(gè)平

13、臺工作量的方差最小。5.1.2 篩選三分鐘內(nèi)平臺可覆蓋節(jié)點(diǎn)1.求解A城區(qū)內(nèi)任意兩個(gè)節(jié)點(diǎn)之間的最短距離在附表中，我們可以得出A城區(qū)內(nèi)第號節(jié)點(diǎn)和第號節(jié)點(diǎn)之間的直線距離，但是在警車執(zhí)行任務(wù)等實(shí)際情況中選擇的都是最短路線，即需要求出任意兩個(gè)節(jié)點(diǎn)之間的最短距離。我們利用Floyd算法，使用Matlab進(jìn)行編程求出了A城區(qū)內(nèi)節(jié)點(diǎn)間的最短距離（Matlab程序見附錄1）。附錄2展示了92個(gè)節(jié)點(diǎn)到20個(gè)平臺的最短距離。2. 篩選20個(gè)平臺3分鐘內(nèi)可覆蓋節(jié)點(diǎn)在得到92個(gè)節(jié)點(diǎn)到20個(gè)平臺的最短距離后，我們可以篩選出覆蓋0-1矩陣，其中=1表示第個(gè)節(jié)點(diǎn)可以在3分鐘內(nèi)得到第個(gè)平臺的幫助，如果對于一個(gè)節(jié)點(diǎn)來說所有平臺都

14、無法滿足3分鐘內(nèi)援助的要求，則將所用時(shí)間最短的平臺所對應(yīng)的值設(shè)為1。我們借助Matlab進(jìn)行了篩選，篩選后的0-1矩陣見附錄3所示。A城區(qū)中共有92個(gè)節(jié)點(diǎn)，每個(gè)都對應(yīng)一個(gè)管轄平臺，對于號節(jié)點(diǎn)，使=1的號平臺都有可能使=1，產(chǎn)生管轄關(guān)系，這樣對應(yīng)著若干種可行解。我們將以工作量均衡為目標(biāo)對轄區(qū)范圍進(jìn)行進(jìn)一步規(guī)劃。5.1.3 以工作量平衡為目標(biāo)進(jìn)行規(guī)劃根據(jù)上述分析，我們可以得出，對=1，必有=1，我們把該關(guān)系作為一個(gè)約束條件，以工作量平衡（即工作量的方差最?。槟繕?biāo)對進(jìn)行0-1規(guī)劃，以從中選出一個(gè)使20個(gè)平臺工作量最均衡的方案。（1）我們使用lingo對該模型進(jìn)行了求解（lingo代碼見附錄3），得

15、出了A城區(qū)管轄范圍的最優(yōu)方案，在該方案下，只有6個(gè)節(jié)點(diǎn)不滿足3分鐘之內(nèi)到達(dá)，且20個(gè)平臺工作量的方差僅為2.976。平臺的管轄范圍如表1所示：表1 平臺管轄范圍平臺節(jié)點(diǎn)平臺節(jié)點(diǎn)平臺節(jié)點(diǎn)平臺節(jié)點(diǎn)11335498811834455081611935455184717135555297180370553992173765599322394465946240457661010269460656111146265811264637301127464734466748761平臺節(jié)點(diǎn)平臺節(jié)點(diǎn)平臺節(jié)點(diǎn)1212163319651225163519671313163619681321163719731322163

16、81974132316451975132417219771414174119781515174219791528174320201529177220811531188420821885208318872086188820921889189018915.2 快速全封鎖的調(diào)度方案5.2.1 建立快速全封鎖的0-1規(guī)劃模型發(fā)生重大突發(fā)事件時(shí)，城區(qū)內(nèi)20個(gè)服務(wù)平臺的警力資源需要全部出動(dòng)對進(jìn)出該區(qū)的13條交通要道進(jìn)行快速全封鎖，且一個(gè)平臺的警力最多封鎖一個(gè)路口。突發(fā)事件的性質(zhì)決定了調(diào)度平臺的方案要在盡量短的時(shí)間內(nèi)進(jìn)行完全封鎖，故衡量方案合理性的因素有兩個(gè)，分別是完成全封鎖需要的時(shí)間和平均每條路封鎖的時(shí)間

17、。我們以第個(gè)要道是否由第個(gè)平臺封鎖作為0-1變量建立0-1規(guī)劃模型來求解這個(gè)問題。如果只考慮封鎖的完整性而忽視平均每條路封鎖的時(shí)間則會(huì)使犯罪嫌疑人在警方的封鎖結(jié)束以前已經(jīng)逃脫，而如果輕視了封鎖的完整性則會(huì)使嫌疑人在某些路口有機(jī)可乘，而后者造成的損失和后果更嚴(yán)重，所以我們可以采用分層求解法，首先以最大封鎖時(shí)間最小為目標(biāo)函數(shù)進(jìn)行規(guī)劃，得出一組最大封鎖時(shí)間相同的可行解，然后再在這些可行解中以平均封鎖時(shí)間最小為目標(biāo)函數(shù)進(jìn)行規(guī)劃得出一個(gè)最優(yōu)解。5.2.1 第一層 以封鎖完全時(shí)間最短為目標(biāo)函數(shù)目標(biāo)函數(shù)和約束條件如下： （2）我們由此可以得出一組可行解，均滿足最大封鎖時(shí)間最短，為8.0155分鐘。5.2.2

18、 第二層 以平均封鎖時(shí)間最小作為目標(biāo)函數(shù)目標(biāo)函數(shù)和約束條件如下： （3）我們使用lingo進(jìn)行了編程（lingo代碼見附錄4），得出最優(yōu)解對應(yīng)的要道、平臺及封鎖該路段所需時(shí)間如表2所示：表2 要道封鎖調(diào)度要道平臺距離12120141667.41716915.325211432.65221077.0823135241138.053281547.51829780.15530830.60838239.82248524.7586243.5我們可以求得13條要道的總封鎖路程為46.1886千米，平均封鎖時(shí)間為3.53分鐘，完全封鎖所需時(shí)間為8.0155分鐘。5.2.3 模型的可行性分析為了避免完全封鎖的

19、要求過度犧牲了平均封鎖時(shí)間，我們又以平均封鎖時(shí)間最小為目標(biāo)函數(shù)進(jìn)行了優(yōu)化，得出最小的平均封鎖時(shí)間為3.523分鐘，與上面所求最優(yōu)解差距甚微，且完成完全封鎖所需時(shí)間過長，作出了不必要且巨大的犧牲，所以我們選擇表2中的調(diào)度方案作為最優(yōu)方案采用。5.3 A城區(qū)平臺增加分析5.3.1 建立平臺增加多目標(biāo)規(guī)劃模型增加平臺的主要目的分別是改善平臺工作量不均衡和有些地方出警時(shí)間過長的實(shí)際情況，我們可以建立以平臺工作量均衡和出警時(shí)間過長節(jié)點(diǎn)最少為目標(biāo)的多目標(biāo)規(guī)劃模型。在解決平臺轄區(qū)分配的問題時(shí)，我們已經(jīng)盡可能地保證了平臺工作量的均衡，且工作量的均衡可以通過調(diào)整轄區(qū)范圍實(shí)現(xiàn)，而由于平臺的位置已經(jīng)固定，仍有個(gè)別節(jié)

20、點(diǎn)沒有三分鐘內(nèi)可提供援助的對應(yīng)平臺，這對緊急事故時(shí)的處理有著致命的影響。所以在增加平臺時(shí)我們把解決部分節(jié)點(diǎn)出警時(shí)間過長作為首要任務(wù)，其重要性遠(yuǎn)遠(yuǎn)高于平臺工作量的均衡。因此我們可以通過分層求解法來進(jìn)行規(guī)劃，以6個(gè)到最近平臺時(shí)間都超過3分鐘的節(jié)點(diǎn)作為出發(fā)點(diǎn)，先保證所有節(jié)點(diǎn)都處于至少一個(gè)平臺三分鐘出警的覆蓋范圍內(nèi)，然后再通過進(jìn)一步的規(guī)劃求出滿足該條件下工作量最平衡的增加方案。5.3.2 第一層 以出警時(shí)間為目標(biāo)增加平臺通過對附錄2進(jìn)行篩選，我們篩選出了到最近的平臺都要超過3分鐘的節(jié)點(diǎn)：28、29、38、39、61和92號。我們以這6個(gè)節(jié)點(diǎn)為中心，進(jìn)行了平臺3分鐘出警覆蓋范圍的確定。經(jīng)過計(jì)算，處于三分

21、鐘覆蓋范圍的平臺與對應(yīng)節(jié)點(diǎn)如表3所示：表3 三分鐘覆蓋范圍求解起始節(jié)點(diǎn)3分鐘能到達(dá)節(jié)點(diǎn)2828、292928、293838、39、403938、39、406148、619287、88、89、90、91、92為了節(jié)省人力、資源和成本，我們要盡可能地少增加平臺，即可找出節(jié)點(diǎn)所對應(yīng)覆蓋范圍的交集。從上表可以看出節(jié)點(diǎn)28和節(jié)點(diǎn)29可以共用一個(gè)平臺，節(jié)點(diǎn)38和節(jié)點(diǎn)39可以共用一個(gè)平臺，節(jié)點(diǎn)61和92則分別需要單獨(dú)的平臺。所以，我們至少需要從這6個(gè)節(jié)點(diǎn)所對應(yīng)的13個(gè)節(jié)點(diǎn)中選擇4個(gè)節(jié)點(diǎn)作為服務(wù)平臺才能解決有些地方出警時(shí)間過長的問題，下面我們通過引入第二層目標(biāo)（工作量均衡）進(jìn)行4個(gè)平臺的選取和管轄范圍的分配。

22、5.3.3 第二層 以工作量均衡為目標(biāo)進(jìn)行第二層規(guī)劃增加平臺勢必會(huì)對平臺工作量的均衡程度產(chǎn)生影響，我們從現(xiàn)有備選方案中，通過比較和篩選得出對工作量均衡程度影響較小或產(chǎn)生有利影響的方案作為最優(yōu)平臺增加方案。從表1查出在工作量較為均衡時(shí)6個(gè)節(jié)點(diǎn)所歸屬的服務(wù)平臺如表4所示：表4 最初6個(gè)節(jié)點(diǎn)歸屬平臺節(jié)點(diǎn)節(jié)點(diǎn)所屬平臺2815291538163926179220節(jié)點(diǎn)28、29所歸屬的服務(wù)平臺都是15，因此從這個(gè)角度上看，如果要在節(jié)點(diǎn)28和節(jié)點(diǎn)29中選取一個(gè)節(jié)點(diǎn)作為服務(wù)平臺，對總體的方差影響是一致的。然而節(jié)點(diǎn)29的犯罪率為1.4，節(jié)點(diǎn)28的犯罪率為1.3，為了能更快處理更多案件，我們在節(jié)點(diǎn)28和節(jié)點(diǎn)29里

23、面選擇的節(jié)點(diǎn)29作為增加的第一個(gè)節(jié)點(diǎn)。對節(jié)點(diǎn)38、39，我們逆向地分別把節(jié)點(diǎn)38、39、40作為服務(wù)平臺來觀察它們對總體方差的影響。將這3個(gè)點(diǎn)作為中心建立覆蓋模型，半徑為3分鐘的車程，可以得出這三個(gè)點(diǎn)分別作為平臺能覆蓋的點(diǎn)如表5所示：表5 節(jié)點(diǎn)38、39、40覆蓋范圍起始節(jié)點(diǎn)覆蓋節(jié)點(diǎn)3838、39、403938、39、40402、17、38、39、40、43、44從上表可以看出，節(jié)點(diǎn)40可覆蓋并聯(lián)系更多的節(jié)點(diǎn)，作為新的平臺對總體工作量的方差影響是最優(yōu)的，所以我們選擇40號節(jié)點(diǎn)作為增加的第二個(gè)節(jié)點(diǎn)。同理，節(jié)點(diǎn)48的覆蓋能力遠(yuǎn)遠(yuǎn)強(qiáng)于節(jié)點(diǎn)61，所以被選擇成為增加的第三個(gè)節(jié)點(diǎn)。以節(jié)點(diǎn)92為圓心，3分鐘

24、車程所形成覆蓋的節(jié)點(diǎn)編號分別為：87、88、89、90、91、92。我們分別以這幾個(gè)點(diǎn)作為中心建立覆蓋模型如表6所示：表6 87、88、89、90、91、92覆蓋范圍起始節(jié)點(diǎn)覆蓋節(jié)點(diǎn)8718、20、81、82、83、84、85、86、87、88、89、90、91、928818、20、81、82、83、84、85、86、87、88、89、90、91、928918、20、80、81、82、83、84、85、86、87、88、89、90、91、929018、20、80、81、82、83、84、85、86、87、88、89、90、91、929118、20、81、82、83、84、85、86、87、88

25、、89、90、91、929287、88、89、90、91、92從表6可以看出，覆蓋點(diǎn)數(shù)最多的節(jié)點(diǎn)是節(jié)點(diǎn)89和節(jié)點(diǎn)90，而節(jié)點(diǎn)90的發(fā)案率為1.4，節(jié)點(diǎn)89的發(fā)案率為0.9，因此我們選擇節(jié)點(diǎn)90作為第四個(gè)服務(wù)平臺。最后，我們選擇了29、40、48和90四個(gè)節(jié)點(diǎn)，為了使工作量盡可能均衡，我們建立了分配管轄范圍的0-1規(guī)劃模型，將個(gè)工作的平臺的管轄范圍重新進(jìn)行了規(guī)劃。最終解得工作量的方差為1.968594，比原來的2.975875減小了33.85%，不僅解決了部分節(jié)點(diǎn)出警時(shí)間過長的問題，也使工作量更加均衡，我們認(rèn)為這是一種合理的方案。5.4 分析全市平臺設(shè)置合理性及改進(jìn)方案要分析全市現(xiàn)有平臺設(shè)置的合

26、理性，我們首先要確立一個(gè)最優(yōu)目標(biāo)，然后拿最優(yōu)目標(biāo)與現(xiàn)有情況進(jìn)行比較，分析現(xiàn)有情況的不足，從而進(jìn)行改進(jìn)。5.4.1 求解最優(yōu)平臺設(shè)置1. 確定每個(gè)區(qū)域內(nèi)平臺設(shè)置個(gè)數(shù)在這個(gè)問題中，我們其實(shí)是對所有的平臺進(jìn)行了重新分配，因此我們首先就應(yīng)該使A-F各個(gè)區(qū)域的工作量相對平衡，具體做法就是將案件發(fā)生較多的區(qū)域分配較多的服務(wù)平臺，案件發(fā)生較少的地方分配較少的服務(wù)平臺。我們首先算出的了這個(gè)城市的總犯罪率674.5。然后對六個(gè)區(qū)域的犯罪率進(jìn)行了計(jì)算。計(jì)算結(jié)果如表7所示：表7 A-F區(qū)犯罪率區(qū)域代號犯罪率A124.5B66.4C187.2D67.8E119.4F109.2根據(jù)每個(gè)區(qū)域的犯罪率所占總犯罪率的比重分配

27、，我們可以分配每個(gè)區(qū)域內(nèi)服務(wù)平臺的個(gè)數(shù)如表8所示：表8 每個(gè)區(qū)域內(nèi)服務(wù)平臺的個(gè)數(shù)區(qū)域代號區(qū)域犯罪率占總犯罪率比例各個(gè)區(qū)域應(yīng)該分配的服務(wù)平臺數(shù)（四舍五入）A0.18458115B0.0984438C0.27753922D0.1005198E0.1770214F0.161898132. 建立0-1規(guī)劃模型求解平臺分布為了保證事故處理的及時(shí)性，我們首先要滿足的條件即為能使發(fā)生事件時(shí)警車能在3分鐘內(nèi)趕到的節(jié)點(diǎn)盡量多。其次，我們要考慮的就是區(qū)域內(nèi)工作量是否均衡。然而事實(shí)上這個(gè)要求主要取決于管轄范圍的分配，因此我們的目標(biāo)為在每個(gè)區(qū)域內(nèi)保證警車3分鐘內(nèi)所覆蓋的點(diǎn)最多。這是一個(gè)局部求解最優(yōu)化解的問題，我們對應(yīng)

28、這個(gè)問題建立了0-1規(guī)劃模型，分別對A-F每個(gè)區(qū)域進(jìn)行了規(guī)劃。目標(biāo)函數(shù)和約束條件如下所示：（3）我們利用lingo編程分別對6個(gè)區(qū)域進(jìn)行了求解（lingo代碼見附錄5所示），得到6個(gè)區(qū)域內(nèi)平臺分布如表9所示：表9 A-F內(nèi)平臺分布最優(yōu)方案（數(shù)據(jù)為節(jié)點(diǎn)號）ABCDEF10931663233724801194169325373482129517832837748414961833303784851597198332379486219819934438748722992003623894882310020137139151024202407511262034175412720441956328215

29、4205612923847158239239474922402482512522532542552665.4.2 分析現(xiàn)有平臺設(shè)置合理性從題目給出的數(shù)據(jù)我們可以得到每一個(gè)區(qū)域的初始平臺數(shù)：表10 每個(gè)區(qū)域的初始平臺數(shù)區(qū)域編號服務(wù)平臺數(shù)A20B8C17D9E9F11從上表我們可以看出，從宏觀上來看整個(gè)城市各個(gè)區(qū)域的工作量是不平等的，A處平臺設(shè)置顯著偏多，C和E處平臺設(shè)置則偏少。除此之外，在這6個(gè)區(qū)域中存在若干節(jié)點(diǎn)不滿足發(fā)生案件時(shí)能有警車在3分鐘之內(nèi)到達(dá)的情況，這不符合警察執(zhí)行事務(wù)要效率第一的思想，更無法確保事件處理的及時(shí)性。我們做出的最優(yōu)解最大限度地保證了警察的效率和事件處理的及時(shí)即保證能被3分

30、鐘警車車程覆蓋的節(jié)點(diǎn)點(diǎn)數(shù)最大。所以我們可以看出，現(xiàn)有平臺的設(shè)置是不盡合理的，而且結(jié)合六城區(qū)的人口和面積來考慮，如E城區(qū)人口和面積均為最大，而分配給它的平臺數(shù)只有9個(gè)，不僅無法滿足覆蓋范圍和警察效率的要求，更無法保證突發(fā)事件的及時(shí)處理，所以應(yīng)該參照最優(yōu)方案進(jìn)行重新設(shè)置。5.5 最佳圍堵方案確定5.5.1 建立生長樹模型進(jìn)行圍堵分析由于犯罪嫌疑人并不明顯地被總部所知，所以我們假設(shè)罪犯在沒被抓到之前處在一個(gè)共存態(tài)，也就是說罪犯可以向所有可能的方向逃竄。而交巡警的任務(wù)就是在路口節(jié)點(diǎn)出設(shè)下路障進(jìn)行圍堵。罪犯的逃竄方向是不定的，可能向前，也有可能又繞回了原點(diǎn)，這里我們必須考慮到最壞的情況，也就是說罪犯是往

31、外逃竄的，離P點(diǎn)是越來越遠(yuǎn)的，所有可能的情況是越來越多的，只要把這個(gè)最壞的情況堵住則罪犯就無法逃竄?；诖?，我們建立了一個(gè)圖論中的生長樹模型。此模型中的樹有兩個(gè)權(quán)值，權(quán)值1表示按此路徑案發(fā)地點(diǎn)到此點(diǎn)的距離，權(quán)值2表示該點(diǎn)的出度（默認(rèn)罪犯不走回頭路）。我們把案發(fā)地點(diǎn)作為這個(gè)樹的根，根的權(quán)值1為0，表示距離為0，權(quán)值2為3，表示有三條路可以走。如圖2所示。圖2 生長樹模型示意圖我們按照罪犯往外逃竄方向生長結(jié)點(diǎn)。長好第一層后我們就可以進(jìn)行第一次判斷，判斷一下警車能否在罪犯之前到達(dá)a1,a2,a3三個(gè)葉結(jié)點(diǎn)。如果能，則圍堵結(jié)束；如果不能，則說明至少有一個(gè)節(jié)點(diǎn)不滿足要求，我們按照權(quán)值2，舍去一個(gè)權(quán)值最小

32、的節(jié)點(diǎn)（如果權(quán)值最小的有好幾個(gè)，選擇距離案發(fā)地點(diǎn)最近的那個(gè)節(jié)點(diǎn)舍去），對剩下的警車進(jìn)行圍堵，如果不能，再舍去剩下來的節(jié)點(diǎn)中權(quán)值最小的節(jié)點(diǎn)，再進(jìn)行圍堵嘗試，如此往復(fù)，直至能成功地圍堵所有剩下的節(jié)點(diǎn)，或者全部不能圍堵；然后對那些沒有能圍堵的結(jié)點(diǎn)進(jìn)行樹的生長。再對所有的葉結(jié)點(diǎn)進(jìn)行圍堵嘗試，方法如上。如果罪犯走回頭路，則對警方有利，便于處理，而我們只考慮最壞的情況，所以假設(shè)罪犯不走回頭路。由于生長樹的高度越大，相對于警方而言，那些葉結(jié)點(diǎn)的圍堵難度其實(shí)并不會(huì)發(fā)生太大的變化，而對于罪犯而言，距離是在不斷累積的。所以圍堵難度總體趨勢是逐漸變小的，當(dāng)在某一次不能對所有的葉結(jié)點(diǎn)進(jìn)行圍堵時(shí)，我們最先舍棄的是那些出

33、度小的，而不去具體分析警車的攔截難度及再下一層的出度。5.5.2 求解圍堵問題對于此模型，我們采用matlab來存儲并計(jì)算結(jié)點(diǎn)的數(shù)據(jù)，然后用使用lingo進(jìn)行可行性分析。最終得到如下可行解：表11 圍堵過程示意表需要堵的節(jié)點(diǎn)離案發(fā)點(diǎn)的距離攔截警車平臺警車距離需堵節(jié)點(diǎn)的距離4107.55694011106.265411014100.432714017106.503917027104.69841233.04941107.15271674.13743106.76892860108.0835538.65836495.3964321.0716689.50841923.54056797.50111841.839970107.3712