全國(guó)數(shù)模競(jìng)賽

2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽承 諾 書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開(kāi)的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從A/B/C/D中選擇一項(xiàng)填寫(xiě)）： B 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）： 杭州電子科技大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 費(fèi)科斌 2. 楊志偉 3. 張佃鵬 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 數(shù)模組 日期： 年 月 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽編 號(hào) 專 用 頁(yè)賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度摘要為了更好地利用警務(wù)資源，需要根據(jù)城市的實(shí)際情況進(jìn)行合理的分配，本文研究的就是如何合理地設(shè)置交巡警服務(wù)平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源等五個(gè)問(wèn)題。針對(duì)問(wèn)題一，首先用Floyd算法求出任意兩點(diǎn)之間最短路徑，然后對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行討論，找出離每一路口節(jié)點(diǎn)最近的服務(wù)平臺(tái)作為該節(jié)點(diǎn)的服務(wù)平臺(tái)，其次根據(jù)每一條路線和路線兩個(gè)端點(diǎn)的性質(zhì)進(jìn)行了分類討論：如果路線的兩個(gè)端點(diǎn)歸同一服務(wù)平臺(tái)管轄，則這條路線歸該服務(wù)平臺(tái)管轄；如果端點(diǎn)不歸同一平臺(tái)管轄，那么在該條線段太長(zhǎng)的情況下，就把該路線平均分給兩個(gè)服務(wù)平臺(tái)管轄；在該線段不長(zhǎng)的情況下，就直接把該線段分給其中一個(gè)距離較近的平臺(tái)管轄。這樣既對(duì)節(jié)點(diǎn)又對(duì)路線進(jìn)行了管轄范圍的劃分，最后對(duì)模型的合理性進(jìn)行了分析，有92.5%長(zhǎng)度的路線能夠在三分鐘之內(nèi)到達(dá)。針對(duì)問(wèn)題二，要實(shí)現(xiàn)A區(qū)13個(gè)交通要道快速全部封鎖，必須使要調(diào)動(dòng)的13個(gè)服務(wù)平臺(tái)中所有到達(dá)交通要道出口所花時(shí)間的最大值最小化，以此為目標(biāo)建立0-1規(guī)劃，可以求得該最短封鎖時(shí)間為8.02分鐘，并進(jìn)一步在目標(biāo)值不變的情況下使總調(diào)度路程最小化建立0-1規(guī)劃的目標(biāo)函數(shù)求得最終的調(diào)度方案。針對(duì)問(wèn)題三，我們首先對(duì)A區(qū)根據(jù)各個(gè)節(jié)點(diǎn)的最短路徑進(jìn)行了聚類分析，把A區(qū)四次分成2,3,4,5塊，為了方便計(jì)算和求解，根據(jù)實(shí)際情況人為的對(duì)分好類的選址范圍中可能選到的點(diǎn)進(jìn)行了篩選，對(duì)于兩個(gè)不同的選址目的，我們將一個(gè)作為目標(biāo)函數(shù)，另一個(gè)作為約束條件，從聚類好的每一塊中選擇一個(gè)節(jié)點(diǎn)作為新的平臺(tái)，建立0-1規(guī)劃，最終求得最合理的方案是再新增加四個(gè)服務(wù)平臺(tái)，分別對(duì)應(yīng)的節(jié)點(diǎn)序號(hào)為：29，39，60，87。針對(duì)問(wèn)題四，依照設(shè)置服務(wù)平臺(tái)的原則和任務(wù)，首先我們規(guī)定了四個(gè)評(píng)價(jià)指標(biāo)分別為：距離服務(wù)平臺(tái)小于3千米的節(jié)點(diǎn)占總節(jié)點(diǎn)的比例；所有節(jié)點(diǎn)距離服務(wù)平臺(tái)的最長(zhǎng)距離；人口密度與服務(wù)平臺(tái)密度的比例；以及整個(gè)區(qū)域的綜合發(fā)案率。我們用問(wèn)題一的方法分別對(duì)六個(gè)區(qū)域中這些指標(biāo)進(jìn)行了求值，然后基于這四個(gè)指標(biāo)對(duì)每個(gè)區(qū)域以及全市的服務(wù)平臺(tái)設(shè)置進(jìn)行了模糊綜合評(píng)價(jià)，評(píng)價(jià)結(jié)果為較差，最后基于最小頂點(diǎn)覆蓋問(wèn)題對(duì)不合理的地方進(jìn)行了局部?jī)?yōu)化。針對(duì)問(wèn)題五，根據(jù)具體情況我們首先把嫌疑犯的活動(dòng)限制在少數(shù)的幾個(gè)城區(qū)內(nèi)，然后利用動(dòng)態(tài)規(guī)劃的思想，將對(duì)嫌疑犯的包圍圈逐漸往小縮，根據(jù)交警和嫌疑犯所花費(fèi)的時(shí)間進(jìn)行比較，直到嫌疑犯恰好不能逃出包圍圈的那一刻，停止往小縮，最終得到的包圍圈確定在A,C區(qū)某一小片區(qū)域內(nèi)。關(guān)鍵詞：Floyd算法 0-1規(guī)劃 聚類分析 模糊綜合評(píng)判 最小頂點(diǎn)覆蓋一問(wèn)題重述 “有困難找警察”，是家喻戶曉的一句流行語(yǔ)。警察肩負(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ù)部門(mén)面臨的一個(gè)實(shí)際課題。試就某市設(shè)置交巡警服務(wù)平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問(wèn)題：（1）附件1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見(jiàn)附件2。請(qǐng)為各交巡警服務(wù)平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警（警車的時(shí)速為60km/h）到達(dá)事發(fā)地。對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警服務(wù)平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出該區(qū)交巡警服務(wù)平臺(tái)警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。（2）針對(duì)全市（主城六區(qū)A，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺(tái)的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺(tái)設(shè)置方案（參見(jiàn)附件）的合理性。如果有明顯不合理，請(qǐng)給出解決方案。如果該市地點(diǎn)P（第32個(gè)節(jié)點(diǎn)）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請(qǐng)給出調(diào)度全市交巡警服務(wù)平臺(tái)警力資源的最佳圍堵方案。二.模型的假設(shè)（1）假設(shè)發(fā)生突發(fā)狀況時(shí)，警員能夠以60km/h的平均速度趕往現(xiàn)場(chǎng)。（2）假設(shè)各個(gè)交巡警服務(wù)平臺(tái)的職能和警力配備基本相同。（3）假設(shè)線段上的案發(fā)率可以用端點(diǎn)上的案發(fā)率進(jìn)行表示。（4）假設(shè)在逮捕犯罪嫌疑人時(shí)，犯罪嫌疑人的逃跑速度也為60km/h。（5）假設(shè)同一個(gè)交巡警服務(wù)平臺(tái)同時(shí)不能兼顧兩個(gè)節(jié)點(diǎn)。三城區(qū)A交巡警服務(wù)平臺(tái)優(yōu)化方案的設(shè)計(jì)3.1 符號(hào)說(shuō)明任意一條路線的長(zhǎng)度任意兩個(gè)交通路口節(jié)點(diǎn)之間的最短路徑原有的20個(gè)交巡警服務(wù)平臺(tái)對(duì)應(yīng)的140條路線服務(wù)平臺(tái)在三分鐘之內(nèi)能夠到達(dá)出事地點(diǎn)的滿意度能夠在三分鐘之內(nèi)到出事地點(diǎn)所有線路總長(zhǎng)所有線路總長(zhǎng)在分配服務(wù)平臺(tái)是對(duì)應(yīng)的選址0-1變量在進(jìn)行對(duì)13個(gè)交通要道封鎖時(shí)，所有路線中最長(zhǎng)路線全部封鎖各個(gè)要道所花費(fèi)的最短時(shí)間警車行駛的平均速度全部封鎖好各個(gè)要道所走的總路線長(zhǎng)度第個(gè)節(jié)點(diǎn)對(duì)應(yīng)的發(fā)案率第個(gè)服務(wù)平臺(tái)對(duì)應(yīng)的總的工作量各個(gè)服務(wù)平臺(tái)的總工作量的方差在選址時(shí)決定是否要選擇的0-1變量3.2 各交巡警服務(wù)平臺(tái)管轄范圍的分配3.2.1 問(wèn)題分析要想讓各交巡警服務(wù)平臺(tái)使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警到達(dá)事發(fā)地，我們認(rèn)為是在不考慮各個(gè)交巡警服務(wù)平臺(tái)工作量的情況下，使A區(qū)每條路線上的點(diǎn)和各個(gè)交通路口節(jié)點(diǎn)都可以在20個(gè)服務(wù)平臺(tái)內(nèi)找到路線離自己最短的服務(wù)平臺(tái)，這樣我們分別對(duì)各條路線和各交通路口節(jié)點(diǎn)進(jìn)行了分析和討論。對(duì)于各個(gè)交通路口節(jié)點(diǎn)來(lái)說(shuō)，為了找到任意兩個(gè)節(jié)點(diǎn)之間的最短路線，我們首先根據(jù)已知數(shù)據(jù)求出了圖中相鄰兩個(gè)節(jié)點(diǎn)之間各個(gè)路線的長(zhǎng)度，然后Floyd算法就可以求出任意兩個(gè)交通路口節(jié)點(diǎn)的最短路線，最后對(duì)每一個(gè)交通路口節(jié)點(diǎn)到各個(gè)服務(wù)平臺(tái)最短路線求最小值，這樣就可以得出每個(gè)交通路口節(jié)點(diǎn)對(duì)應(yīng)的平臺(tái)管轄范圍以及對(duì)應(yīng)平臺(tái)的巡警到該節(jié)點(diǎn)所用的最短時(shí)間。對(duì)于各條路線上的點(diǎn)來(lái)說(shuō)，根據(jù)實(shí)際情況我們盡量想把一條路線分在同一個(gè)管轄范圍之內(nèi)，因此我們對(duì)140條路線中每條路線的兩個(gè)路口節(jié)點(diǎn)進(jìn)行討論，如果這兩個(gè)路口節(jié)點(diǎn)在同一管轄范圍之內(nèi)，這條路線就在該管轄范圍內(nèi)；如果這兩個(gè)路口節(jié)點(diǎn)在不同的管轄范圍內(nèi)，要再次進(jìn)行分情況討論，根據(jù)路線的長(zhǎng)短以及該條路線的節(jié)點(diǎn)是否就是服務(wù)平臺(tái)進(jìn)行討論，最后確定是否要把這條路線分開(kāi)進(jìn)行管轄。最后我們對(duì)結(jié)果進(jìn)行了驗(yàn)證，對(duì)于所有能在3分鐘之內(nèi)到達(dá)的路線的長(zhǎng)度和能再3分鐘之內(nèi)達(dá)到的交通節(jié)點(diǎn)的個(gè)數(shù)在整體中所占的比例進(jìn)行了分析，對(duì)結(jié)果進(jìn)行了合理的驗(yàn)證。3.2.2 基于Floyd算法每個(gè)服務(wù)平臺(tái)所管轄的交通節(jié)點(diǎn)的求解（1）每?jī)牲c(diǎn)之間距離矩陣的建立首先建立一個(gè)距離矩陣，取任意兩個(gè)節(jié)點(diǎn)，如果這兩個(gè)節(jié)點(diǎn)有且僅有一條路線連接，則就等于該條路線的長(zhǎng)度，即：否則認(rèn)為該兩點(diǎn)的距離為，即：如果，則該兩點(diǎn)的距離為0，即：最后代入數(shù)據(jù)編程（程序見(jiàn)附錄）可求得該最短路徑矩陣，見(jiàn)附錄。（2）用Floyd算法求解。Floyd是一種動(dòng)態(tài)規(guī)劃算法，對(duì)于每一對(duì)頂點(diǎn) i和j，看看是否存在一個(gè)頂點(diǎn)i使得從i到k再到j(luò)比己知的路徑更短，如果是最短就更新它，最后把所有的可能的點(diǎn)都找完，就可以找到點(diǎn)i到點(diǎn)j的最短路徑path（i，j），其狀態(tài)轉(zhuǎn)移方程如下： 這樣根據(jù)其算法流程用matlab軟件編程（程序見(jiàn)附錄）可以求得這92交通節(jié)點(diǎn)中每?jī)蓚€(gè)點(diǎn)的最短路線矩陣path，見(jiàn)附錄。在以上求出任意兩個(gè)交通節(jié)點(diǎn)最短距離的基礎(chǔ)上，可以在20個(gè)交巡警服務(wù)平臺(tái)中找到離每個(gè)交通節(jié)點(diǎn)最近的交巡警服務(wù)平臺(tái)。求公式如下：根據(jù)上式可以求得對(duì)于第i個(gè)交通節(jié)點(diǎn)都有一個(gè)服務(wù)平臺(tái)與其相對(duì)應(yīng)。這樣就求出了每一個(gè)交巡警服務(wù)平臺(tái)所管轄的交通節(jié)點(diǎn)的所有數(shù)目如下表：交巡警服務(wù)平臺(tái)序號(hào) 各個(gè)服務(wù)平臺(tái)所管轄的交通節(jié)點(diǎn)序號(hào)11676869717374757678223940434470723354556566445760626364554950515253565859667730324748618833469931343545101011112627121225131321222324141415152829161636373817174142181880818283191977792020848586878889909192表 3-2-1 每個(gè)平臺(tái)所管轄的交通節(jié)點(diǎn)序號(hào)3.2.3 每個(gè)交巡警服務(wù)平臺(tái)所管轄的交通路線的求解對(duì)于各條路線上的點(diǎn)來(lái)說(shuō)，根據(jù)實(shí)際情況，我們盡量想把一條路線分在同一個(gè)交巡警服務(wù)平臺(tái)管轄范圍之內(nèi)，但是有些路線會(huì)太長(zhǎng)，有些路線還會(huì)直接與交巡警服務(wù)平臺(tái)相連接，針對(duì)這些情況，我們不能把一條路線分在同一個(gè)服務(wù)平臺(tái)的管轄范圍之內(nèi)，因此我們按照140條路線中每條路線的兩個(gè)交通路口節(jié)點(diǎn)的情況不同進(jìn)行了分類討論：（1） 如果某條路線兩個(gè)交通路口節(jié)點(diǎn)A,B在同一交巡警服務(wù)平臺(tái)M管轄范圍之內(nèi)，如下圖：MmA1B 圖 3-2-1這樣我們就把線段AB劃分在M交巡警服務(wù)平臺(tái)管轄范圍之內(nèi)。（2）如果某條路線的兩個(gè)交通路口節(jié)點(diǎn)A,B在不同的兩個(gè)交巡警服務(wù)平臺(tái)管轄 范圍之內(nèi)，如下圖：MmA1BNB圖 3-2-2其中 A節(jié)點(diǎn)屬于M服務(wù)平臺(tái)管轄，B節(jié)點(diǎn)屬于N服務(wù)平臺(tái)管轄，在這種情況下，我們首先要判斷一下這條線路的長(zhǎng)度，如果太長(zhǎng)，則不能歸同一個(gè)服務(wù)平臺(tái)管轄，因?yàn)榫€路太長(zhǎng)對(duì)其行駛時(shí)間的影響很大；反之，我們就可以把歸同一服務(wù)平臺(tái)管轄，根據(jù)實(shí)際情況，我們對(duì)線段的長(zhǎng)度按照一下規(guī)則進(jìn)行分類討論：在放在一個(gè)服務(wù)平臺(tái)范圍內(nèi)管轄時(shí)，我們比較一下兩個(gè)節(jié)點(diǎn)離其對(duì)應(yīng)服務(wù)平臺(tái)的最短路徑的大小進(jìn)行判斷來(lái)確定歸那個(gè)服務(wù)平臺(tái)管理：（3）還有一種情況是線段AB的兩個(gè)端點(diǎn)中本來(lái)自身就是服務(wù)平臺(tái)。如下圖： MMA1BN 圖3-2-3 針對(duì)這種情況，我們同樣要把線段AB平均分為兩段分在M,N兩個(gè)不同的服務(wù)平臺(tái)管轄范圍之內(nèi)。根據(jù)以上算法和思路，我們用matlab軟件編程（程序見(jiàn)附錄），可以求得每一個(gè)交巡警服務(wù)平臺(tái)所單獨(dú)管轄的各條路線的序號(hào)，如下表：交巡警服務(wù)平臺(tái)序號(hào)各個(gè)平臺(tái)所管轄的交通線路的序號(hào)11,2，197,99,100,102,103,104,105,106,107,110,111,112,114,115,116,117,12023,60,61,64,65,66,101,10935,67,83,85,96,9847,84,86,87,88,89,91,92,93,9558，9,71,75,76,77,78,79,80,81,82,90610,72711, 21,44,45,46,57,73,74814,48,49,68,69,70915,47,50,51,52,5410381117,18,37,391219,36,401332,33,34,3514201522,41,421624,53,55,56,581725,26,62,1828,29,113,124,125,126,1271930,118,119,121,1222031，128,129,130,131,132,133,134,135,137,138,139,140表3-2-2 每個(gè)平臺(tái)單獨(dú)管轄的交通路線序號(hào)并得出有些路線平均分開(kāi)歸兩個(gè)交巡警服務(wù)平臺(tái)管轄的情況如下表：由兩個(gè)平臺(tái)公共管轄的路線序號(hào)46131621232743596394這條路線對(duì)應(yīng)的兩個(gè)服務(wù)平臺(tái)的序號(hào)3 94 28 910 915 716 1417 1815 716 1717 204 20表3-2-3 由兩個(gè)服務(wù)平臺(tái)共同管轄的路線序號(hào)3.2.4 結(jié)果的分析和比較在解決該問(wèn)題時(shí)，我們的最終目標(biāo)是在為了讓交巡警服務(wù)平臺(tái)能盡量在三分鐘之內(nèi)到達(dá)事發(fā)地，為此，我們從各個(gè)方面對(duì)所求結(jié)果進(jìn)行了驗(yàn)證和分析：（1）首先我們對(duì)所有到達(dá)時(shí)間超過(guò)三分鐘的道路上的最長(zhǎng)達(dá)到時(shí)間進(jìn)行了統(tǒng)計(jì)（程序見(jiàn)附錄）如下表：道路序號(hào)5786420174023948482到達(dá)對(duì)應(yīng)服務(wù)平臺(tái)所需要的最長(zhǎng)時(shí)間（分鐘）3.04 3.11 3.22 3.26 3.27 3.30 3.37 3.45 3.45 3.45 道路序號(hào)3836587056925963643到達(dá)對(duì)應(yīng)服務(wù)平臺(tái)所需要的最長(zhǎng)時(shí)間（分鐘）3.54 3.59 3.71 3.87 4.11 5.21 5.41 5.92 5.96 9.42 表3-2-3 最長(zhǎng)達(dá)到時(shí)間的統(tǒng)計(jì)結(jié)果由以上表格中的數(shù)據(jù)可以發(fā)現(xiàn)，在140條路線中，交巡警力到達(dá)的最大時(shí)間超過(guò)3分鐘的只有20條路線，而且這些時(shí)間都在3分鐘附近，所以以上數(shù)據(jù)可以發(fā)現(xiàn)都?jí)虮M量滿足三分鐘內(nèi)到達(dá)。（2）然后為了驗(yàn)證結(jié)果做的是否滿意，我們規(guī)定了滿意度的公式為：即：通過(guò)matlab軟件編程（程序見(jiàn)附錄四）可以求得： 將其帶入得： 有上述分析可知，有92.5%的線路可以滿足在三分鐘之內(nèi)到達(dá)，所以結(jié)果基本符合要求，滿意度很高，這樣也同樣驗(yàn)證了我們解題方案的合理性。（3）在以上結(jié)果的基礎(chǔ)上并結(jié)合每個(gè)點(diǎn)的案發(fā)率的大小，在超過(guò)3分鐘到達(dá)的線路上，我們可以人工調(diào)整調(diào)度方案，犯罪嫌疑不會(huì)又逃脫的可能性，所以即使超出三分鐘也關(guān)系不是很大。3.3 根據(jù)0-1整數(shù)規(guī)劃制定服務(wù)平臺(tái)警力的調(diào)度方案3.3.1 問(wèn)題分析為了實(shí)現(xiàn)A區(qū)13個(gè)交通要道快速全部封鎖，我們需要從20個(gè)交巡警服務(wù)平臺(tái)中調(diào)動(dòng)13個(gè)服務(wù)平臺(tái)的警力分別去封鎖A區(qū)交通要道的出口，而且使13個(gè)平臺(tái)中所有到達(dá)交通要道出口所花時(shí)間的最大值最小化，這樣可以建立目標(biāo)函數(shù)用0-1整數(shù)規(guī)劃解決該問(wèn)題，并用lingo軟件編程求出要花費(fèi)最長(zhǎng)的時(shí)間。但是在該所花費(fèi)的最長(zhǎng)時(shí)間的前提下，同樣還有很多種調(diào)動(dòng)方案，為了盡快使每個(gè)路口都要交警到達(dá)，同時(shí)盡量節(jié)約時(shí)間和成本，我們需要讓所有服務(wù)平臺(tái)到達(dá)對(duì)應(yīng)的交通要道出口的總時(shí)間最短，這樣既可以進(jìn)一步減小嫌疑目標(biāo)逃離的可能性，同時(shí)減少了成本代價(jià)的付出。同樣以這個(gè)總時(shí)間最小化為目標(biāo)函數(shù)，建立0-1整數(shù)規(guī)劃方程，用lingo軟件可以求出最終的調(diào)度方案。3.3.2 各個(gè)平臺(tái)所花時(shí)間的最大值最小化模型的建立和求解我們所要解決的問(wèn)題是從20個(gè)服務(wù)平臺(tái)中選擇13個(gè)服務(wù)平臺(tái)進(jìn)行調(diào)度分配到13個(gè)交通要道出口處，為了盡快實(shí)現(xiàn)全部交通要道的封鎖目的，我們讓服務(wù)平臺(tái)警力到達(dá)每個(gè)交通要道出口的時(shí)間中的最大值最小化，這樣就可以實(shí)現(xiàn)我們的目的。設(shè)表示的內(nèi)容如下：由于每個(gè)服務(wù)平臺(tái)行駛的速度是一定的，因此我們可以把關(guān)于時(shí)間的目標(biāo)函數(shù)轉(zhuǎn)化成關(guān)于所有路程中最大值最小化的問(wèn)題，這樣我們可以建立目標(biāo)函數(shù)如下： 在以上目標(biāo)函數(shù)建立的基礎(chǔ)上，我們用lingo軟件編程（程序見(jiàn)附錄）可以求得：再將代入公式： 可求得實(shí)現(xiàn)全部封鎖各個(gè)交通要道所用的最短時(shí)間為：3.3.3 在最短時(shí)間封鎖要道的基礎(chǔ)上調(diào)度方案的進(jìn)一步優(yōu)化在上述所求出實(shí)現(xiàn)全部封鎖各個(gè)要道所用最短時(shí)間的情況下，同樣還存在很多種調(diào)動(dòng)方案，為了盡快使每個(gè)路口都有交警到達(dá)，我們需要讓所有服務(wù)平臺(tái)到達(dá)對(duì)應(yīng)的交通要道的總時(shí)間最短，這樣同時(shí)可以減少成本的浪費(fèi)和進(jìn)一步減小嫌疑目標(biāo)逃離的可能性，同樣設(shè)：以這個(gè)總時(shí)間最小化為目標(biāo)函數(shù)，建立0-1整數(shù)規(guī)劃方程如下：用lingo軟件編程（程序見(jiàn)附錄）求得實(shí)現(xiàn)全部封鎖各個(gè)交通要道，各個(gè)交巡警服務(wù)平臺(tái)所花費(fèi)的時(shí)間和為：并很容易得出最終的調(diào)度方案如下表：交通要道序出口號(hào)12345678910111213交通要道所對(duì)應(yīng)的路口節(jié)點(diǎn)序號(hào)12141621222324282930383962對(duì)應(yīng)的調(diào)度服務(wù)平臺(tái)序號(hào)12169141013111578254表4-3-1 交巡警服務(wù)平臺(tái)警力進(jìn)行快速全城封鎖合理的調(diào)度方案3.4 基于聚類分析的新服務(wù)平臺(tái)的選址優(yōu)化方案3.4.1 問(wèn)題分析如果要再選擇2到5個(gè)節(jié)點(diǎn)作為新的交巡警服務(wù)平臺(tái)，這屬于一個(gè)選址優(yōu)化問(wèn)題，由于整個(gè)A區(qū)的節(jié)點(diǎn)太多，這樣給選址問(wèn)題帶來(lái)了許多不便，為了使問(wèn)題變的容易一點(diǎn)，我們對(duì)A區(qū)中所有節(jié)點(diǎn)進(jìn)行了歐氏距離聚類分析，聚類的依據(jù)是每?jī)蓚€(gè)節(jié)點(diǎn)之間的最短路徑。這樣根據(jù)不同情況，可以對(duì)A區(qū)進(jìn)行不同數(shù)目的分塊。要選擇若干個(gè)節(jié)點(diǎn)作為新的交巡警服務(wù)平臺(tái)，就把A區(qū)分為若干個(gè)塊，這樣我們只需要從每一塊中選擇其中的一個(gè)節(jié)點(diǎn)就可以了。但是這樣聚類分塊以后，仍然會(huì)出現(xiàn)節(jié)點(diǎn)太多的情況，然后我們根據(jù)實(shí)際情況，一些顯而易見(jiàn)不會(huì)作為選址點(diǎn)的節(jié)點(diǎn)直接人為排除掉，這樣就大大減小了選擇的范圍，解決起來(lái)很方便。我們的最終目標(biāo)是希望交巡警服務(wù)平臺(tái)的工作量盡量均衡和出警時(shí)間盡量短，我們把出警時(shí)間作為約束條件，把工作量盡量均衡作為目標(biāo)函數(shù)，同時(shí)工作量可以認(rèn)為是每個(gè)區(qū)域內(nèi)所管轄的節(jié)點(diǎn)對(duì)應(yīng)的發(fā)案率的和，使各個(gè)交巡警服務(wù)平臺(tái)的工作量的方差最小化，建立0-1整數(shù)規(guī)劃，進(jìn)行求解，針對(duì)要選擇2到5個(gè)點(diǎn)分別進(jìn)行求解，最后比較結(jié)果進(jìn)行分析，決定要再選擇幾個(gè)交通服務(wù)平臺(tái)。3.4.2 基于最短距離聚類法對(duì)A區(qū)進(jìn)行分塊聚類分析需要依據(jù)節(jié)點(diǎn)的相似性能進(jìn)行分塊，根據(jù)實(shí)際情況，我們考慮到了每?jī)蓚€(gè)節(jié)點(diǎn)間最短路徑，把離的比較近的一些點(diǎn)分在一塊，這樣先將92個(gè)節(jié)點(diǎn)各自分為一類，計(jì)算它們之間的最短路徑長(zhǎng)度，選擇長(zhǎng)度最小的兩個(gè)節(jié)點(diǎn)歸為新的一類，再計(jì)算這個(gè)新類與其它節(jié)點(diǎn)的距離，選擇距離小的兩個(gè)節(jié)點(diǎn)（或兩個(gè)新類）歸為新的一類，每次合并縮小一個(gè)以上的類，直到所有樣本都劃入一個(gè)新類為止。這里規(guī)定兩點(diǎn)間的距離，兩類間的距離。步驟如下：（1） 看各數(shù)據(jù)量綱是否一致，如果不一致要對(duì)數(shù)據(jù)進(jìn)行正規(guī)化處理，并選擇一種計(jì)算距離的方法，我們這里選擇的是歐氏距離法。（2） 計(jì)算各樣本之間的距離，并記在分類距離對(duì)稱表中。（3） 選擇上述對(duì)稱表中的最短距離，設(shè)為，則將合成一個(gè)新類記為： （4） 計(jì)算新類與其它類之間的距離，并將第p，q行和列刪掉，作為一個(gè)新的對(duì)稱表。（5） 重復(fù)以上步驟，直到最后只剩下要實(shí)現(xiàn)的最終分類結(jié)果為止，并作聚類圖?；谝陨纤悸泛土鞒?，我們用matlab軟件進(jìn)行了編程（程序見(jiàn)附錄），分別得出在把A區(qū)分為2,3,4,5塊的情況下，各類中包含節(jié)點(diǎn)的數(shù)目和序號(hào)，用圖表示如下：A區(qū)10,11,12,13,14,15,21,22, 23,24,25,26 27,28,29 1,2,3,4,5,6,7,8,9,16,17,18,19,20,30,31,90,91,92圖3-4-1 將A區(qū)分為兩類的情況A區(qū)1,2,3,4,5,7,8,9,16,17,18,19,20,30,.37,41,60,62,91,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 圖3-4-2 將A區(qū)分為三類的情況A區(qū)7,8,9，16,30，32,33,34,35,36,37,45,46,47,48,926,31,38,39, 40,6110,11,12,13, 14,15,21,22, 23,24,25,26 27,28,29 1,5,17,20,41,44, 49,61,62,91圖3-4-3 將A區(qū)分為四類的情況A區(qū)7,8,9,16,30,32,3334,35,3637,45,4647,486,31,38,39,40,6110,11,1213,14,1521,22,2324,25,26 27,28,29 1,2,3,4,1720,31,384144,5455,59,62,915,49,50,51,52,5356,57,58,60,92圖3-4-4 將A區(qū)分為五類的情況3.4.3 人為減小選址的范圍由于選址范圍過(guò)大，導(dǎo)致編程很難實(shí)現(xiàn)，就難以做到很精確的選址。我們采取人為的方法對(duì)選址范圍進(jìn)行了調(diào)整。調(diào)整方法具體如下：（1）從地圖上很容易發(fā)現(xiàn)有些點(diǎn)距離已有的交巡警服務(wù)平臺(tái)很近，這些點(diǎn)我們就認(rèn)為是歸原有的交巡警服務(wù)平臺(tái)管轄，所以把這些點(diǎn)從選址范圍內(nèi)排除掉。我們給予的條件是把那些和已有的服務(wù)平臺(tái)最短路徑小于1.5千米的節(jié)點(diǎn)都排除掉，即如果第j個(gè)節(jié)點(diǎn)到原有的第i個(gè)服務(wù)平臺(tái)的距離：就把對(duì)應(yīng)第j個(gè)節(jié)點(diǎn)排除掉，這樣就減小了選址范圍。（2）在地圖上還可以找到一些處于出口位置的節(jié)點(diǎn)，如果在這些節(jié)點(diǎn)設(shè)置成服務(wù)平臺(tái)的話，周圍的節(jié)點(diǎn)太少，這樣其工作量就很低，不符合實(shí)際要求，因此我們同樣把這些點(diǎn)也排除掉。經(jīng)過(guò)以上重重篩選后，選址范圍大大減少了，選址也變的容易了。3.4.4 新增服務(wù)平臺(tái)的0-1整數(shù)規(guī)劃選址經(jīng)過(guò)上述聚類分析和人為減小選址范圍的情況下，我們就可以建立選址模型，對(duì)目標(biāo)進(jìn)行優(yōu)化。我們?cè)黾咏谎簿?wù)平臺(tái)的主要目的，是為了解決各個(gè)交巡警服務(wù)平臺(tái)工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際存在的問(wèn)題。這是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，解決起來(lái)不是很方便，因此我們把其中一個(gè)目的作為目標(biāo)函數(shù)，把另一個(gè)目的作為約束條件，這樣就把復(fù)雜的多目標(biāo)優(yōu)化選址問(wèn)題轉(zhuǎn)化為簡(jiǎn)單的單目標(biāo)優(yōu)化選址問(wèn)題。(1)目標(biāo)函數(shù)的確定我們把工作量盡量均衡作為目標(biāo)函數(shù)，首先考慮到影響工作量的因數(shù)既有所管轄范圍內(nèi)每條線路的長(zhǎng)度，也有每條線路對(duì)應(yīng)節(jié)點(diǎn)發(fā)案率的大小，這兩個(gè)因素都與工作量成正相關(guān)關(guān)系。我們這兩個(gè)因素的乘積作為每條線路的工作量。即第i個(gè)節(jié)點(diǎn)到第j個(gè)服務(wù)平臺(tái)的工作量大小可以用公式表示如下（其中表示第i個(gè)節(jié)點(diǎn)的發(fā)案率）：對(duì)于第j個(gè)服務(wù)平臺(tái)的總工作量可以表示為在它管轄范圍之內(nèi)的工作量之和：公式如下： 為了盡量使各個(gè)服務(wù)平臺(tái)的總工作量均衡，我們可以用方差表示目標(biāo)函數(shù)，方差越小，說(shuō)明各個(gè)服務(wù)平臺(tái)的總工作量越均衡。方差可以如下表示：這樣就可以確定目標(biāo)函數(shù)了。(2)另一個(gè)目標(biāo)變?yōu)榧s束條件 對(duì)于另一個(gè)目標(biāo)是使各個(gè)平臺(tái)出警時(shí)間盡量短，我們把出警時(shí)間作為一個(gè)約束條件，對(duì)于每一個(gè)平臺(tái)到其每一個(gè)管轄節(jié)點(diǎn)的出警時(shí)間都應(yīng)該在4分鐘之內(nèi)，也就是轉(zhuǎn)成路程的話就是在4千米之內(nèi)即：這樣就成功的把多目標(biāo)問(wèn)題轉(zhuǎn)化成了單目標(biāo)優(yōu)化問(wèn)題。(3)建立0-1規(guī)劃進(jìn)行求解 在對(duì)各種情況分類分好以后，設(shè)在每個(gè)選址范圍內(nèi)共有n個(gè)點(diǎn)供選擇，其中k個(gè)點(diǎn)是原有的服務(wù)平臺(tái)，我們需要從余下的n-k個(gè)點(diǎn)中選取一個(gè)點(diǎn)使目標(biāo)函數(shù)最優(yōu)。建立0-1規(guī)劃如下：根據(jù)以上目標(biāo)函數(shù)和約束條件可以用lingo軟件編程（程序見(jiàn)附錄）求得結(jié)果（見(jiàn)附錄）。最后對(duì)選擇的2,3,4,5個(gè)地址分別運(yùn)行程序，最終求得在選擇四個(gè)新服務(wù)平臺(tái)的情況下，目標(biāo)已經(jīng)很優(yōu)化了。下面是我們所選擇的這四個(gè)服務(wù)平臺(tái)所對(duì)應(yīng)的節(jié)點(diǎn)的序號(hào)和坐標(biāo)如表：新選服務(wù)平臺(tái)的位置29396087坐標(biāo)(246,337)(371,333)(369,388)(448,381)表3-4-1 新選交巡警服務(wù)平臺(tái)的位置我們把所選擇的新的服務(wù)平臺(tái)標(biāo)在地圖中如下：注：(1)大的五角星代表新選的服務(wù)平臺(tái)。(2)小的星號(hào)代表各個(gè)交通路口節(jié)點(diǎn)。圖3-4-5 新選擇的服務(wù)平臺(tái)四六區(qū)服務(wù)平臺(tái)的綜合評(píng)價(jià)和圍堵問(wèn)題4.1 符號(hào)說(shuō)明4.2 基于模糊綜合評(píng)價(jià)對(duì)全市六區(qū)服務(wù)平臺(tái)設(shè)置的評(píng)價(jià)4.2.1 問(wèn)題分析能夠反應(yīng)交巡警服務(wù)平臺(tái)設(shè)置是否合理的指標(biāo)有很多，我們根據(jù)實(shí)際情況選擇了其中四個(gè)指標(biāo)對(duì)其進(jìn)行評(píng)價(jià)，這四個(gè)指標(biāo)分別為在管轄范圍內(nèi)距離服務(wù)平臺(tái)小于3千米的節(jié)點(diǎn)占總節(jié)點(diǎn)的比例；在管轄范圍內(nèi)所有節(jié)點(diǎn)距離服務(wù)平臺(tái)的最長(zhǎng)距離；在管轄范圍內(nèi)的人口密度與服務(wù)平臺(tái)密度的比例；在管轄范圍內(nèi)節(jié)點(diǎn)綜合的發(fā)案率。首先根據(jù)題目中給的數(shù)據(jù)我們可以編程求得這些指標(biāo)對(duì)應(yīng)的值，然后我們根據(jù)各個(gè)指標(biāo)的重要性人為的對(duì)這些指標(biāo)賦予不同的權(quán)重，最后用模糊綜合評(píng)價(jià)的方法對(duì)六個(gè)區(qū)域服務(wù)平臺(tái)設(shè)置方案進(jìn)行了各自評(píng)價(jià)和綜合評(píng)價(jià)。根據(jù)評(píng)價(jià)的結(jié)果可以發(fā)現(xiàn)有些地區(qū)的平臺(tái)設(shè)置方案明顯不合理，但是對(duì)整個(gè)區(qū)域進(jìn)行調(diào)整很難，也不是很經(jīng)濟(jì)，所以我們依據(jù)最小割集，連通度，最小點(diǎn)覆蓋等方法依次舉例，對(duì)不合理的服務(wù)平臺(tái)設(shè)置進(jìn)行了調(diào)整。4.2.2 各個(gè)評(píng)價(jià)指標(biāo)的計(jì)算按照問(wèn)題一中的解題思路，我們以同樣的方法可以對(duì)六個(gè)區(qū)域?qū)茌牱秶歼M(jìn)行合理的分配，并用matlab軟件編程可以實(shí)現(xiàn)目的，最后求得各指標(biāo)。(1) 距離服務(wù)平臺(tái)小于3千米的節(jié)點(diǎn)占總節(jié)點(diǎn)的比例的計(jì)算由定義可知：第一指標(biāo)公式如下： 用matlab軟件進(jìn)行編程（程序見(jiàn)附錄）可求得結(jié)果如下表：區(qū)域ABCDEF0.93480.91780.69480.76920.67960.6296表4-2-1 各區(qū)域指標(biāo)一的計(jì)算結(jié)果(2) 所有節(jié)點(diǎn)距離服務(wù)平臺(tái)的最長(zhǎng)距離的計(jì)算公式如下： 同樣用matlab軟件編程（程序見(jiàn)附錄）可求得結(jié)果如下表：區(qū)域ABCDEF27.686413.399136.089830.863941.248938.8427表4-2-2 各區(qū)域指標(biāo)二的計(jì)算結(jié)果(3) 人口密度與服務(wù)平臺(tái)密度的比例的計(jì)算人口密度的計(jì)算公式是該區(qū)域的總?cè)丝谂c該區(qū)域總占地面積的比例，公式如下： 服務(wù)平臺(tái)密度計(jì)算公式是總得服務(wù)平臺(tái)的個(gè)數(shù)與總占地面積的比列，公式如下：所以該指標(biāo)最終計(jì)算公式如下：代入數(shù)據(jù)求得結(jié)果如下表：區(qū)域ABCDEF32.6252.8828.1115.0674.818表4-2-3 各地區(qū)指標(biāo)三的計(jì)算結(jié)果(4)節(jié)點(diǎn)綜合發(fā)案率的計(jì)算針對(duì)第四種指標(biāo)的計(jì)算我們做了這樣的假設(shè)，我們把某路口的發(fā)案率和該路口附近地區(qū)的發(fā)案率都?xì)w結(jié)到該路口處，以下圖為例，說(shuō)明一下我們的計(jì)算方法:1234圖4-2-1圖中四個(gè)圓為四個(gè)路口且第三路口只和這三個(gè)圓直接相連，每?jī)蓚€(gè)圓之間的線段為三條道路，它們的長(zhǎng)度分別用，來(lái)表示，第個(gè)節(jié)點(diǎn)的發(fā)案率用來(lái)表示，為了方便計(jì)算，我們把所有線段上的發(fā)案率都?xì)w結(jié)到一個(gè)點(diǎn)上，這樣第三個(gè)節(jié)點(diǎn)的平均發(fā)案率我們可以這樣計(jì)算： 根據(jù)以上表達(dá)式，將數(shù)據(jù)代入并編程求得結(jié)果如下：區(qū)域ABCDEF472812312722081表4-2-4 各地區(qū)指標(biāo)四的求解結(jié)果4.2.3 基于上述四個(gè)指標(biāo)對(duì)服務(wù)平臺(tái)設(shè)置的模糊綜合評(píng)價(jià)(1) 各指標(biāo)的正規(guī)化處理 由于在以上求出的各個(gè)評(píng)價(jià)指標(biāo)的量綱不一樣，因此在這里我們對(duì)各指標(biāo)進(jìn)行了正規(guī)劃處理，公式如下：由matlab編程（程序見(jiàn)附錄）計(jì)算結(jié)果如下表：區(qū)域ABCDEF指標(biāo)一10.940.210.460.160指標(biāo)二0.2410.070.1600.03指標(biāo)三0.0700.0510.450.4指標(biāo)四0.5410.120.1100.25表4-2-5（2）綜合評(píng)價(jià)的評(píng)價(jià)矩陣的確定這些量綱化后的值就可以作為單因素評(píng)價(jià)的評(píng)價(jià)結(jié)果，例如A區(qū)單因素評(píng)價(jià)后的結(jié)果為：由此可得綜合評(píng)價(jià)的評(píng)價(jià)矩陣為：R=（3）綜合評(píng)價(jià)權(quán)重的確定由于A為市區(qū)，所以占得比重應(yīng)該很大，其它的五個(gè)區(qū)域相對(duì)較少，所以平均可以進(jìn)行平均分配，這樣就可以得到評(píng)價(jià)的權(quán)重如下：W=0.5 0.1 0.1 0.1 0.1 0.1（4）進(jìn)行綜合評(píng)價(jià)通過(guò)權(quán)重矩陣W和評(píng)價(jià)矩陣R的模糊變換得到模糊評(píng)判集S的公式如下：其中為模糊合成算子，在四種模糊合成算子中，我們選擇的是算子，因?yàn)樵撍阕泳C合程度比較強(qiáng)，利用信息比較全，屬于加權(quán)平均型的。由上述算子求出了集合如下：S=0.68 0.25 0.23 0.42最后通過(guò)對(duì)模糊評(píng)判向量S的分析作出綜合評(píng)論，我們這里采用的是加權(quán)平均原則，可表示為：其中k為待定系數(shù)（k=1或k=2），目的使控制較大的所起的作用。如對(duì)S=（0.68 0.25 0.23 0.42），評(píng)價(jià)等級(jí)集合為V=很好，一般，較差，差，各等級(jí)賦值分別為4,3,2,1，仿照普通加權(quán)法的計(jì)算公式，有即該市交巡警服務(wù)平臺(tái)巡邏的情況綜合評(píng)價(jià)結(jié)果為較差，有許多需要解決的地方。4.2.4 基于最小頂點(diǎn)覆蓋定理對(duì)市區(qū)進(jìn)行局部?jī)?yōu)化由上述評(píng)價(jià)結(jié)果可以發(fā)現(xiàn)，該市區(qū)的交巡警分布平臺(tái)布置并不是很合理，尤其是地圖上有些局部的服務(wù)平臺(tái)的設(shè)置很不合理。我們選取該地圖上的一部分為例，利用最小頂點(diǎn)覆蓋定理對(duì)其進(jìn)行了局部?jī)?yōu)化。最小頂點(diǎn)覆蓋是指一個(gè)頂點(diǎn)能夠覆蓋的范圍越廣越好，我們利用這個(gè)思想，認(rèn)為與一個(gè)頂點(diǎn)連接的路線的數(shù)目越多越好，選擇這樣的點(diǎn)作為服務(wù)平臺(tái)的話，可以使該服務(wù)平臺(tái)在三分鐘之內(nèi)可以到達(dá)的節(jié)點(diǎn)個(gè)數(shù)增加，但是同時(shí)我們又要考慮到發(fā)案率的問(wèn)題，如果覆蓋太多路線的話，其總體發(fā)案率也會(huì)提高，這樣無(wú)形的增加了服務(wù)平臺(tái)的工作量。我們選取了C區(qū)中的局部地圖如下：圖4.2.4從圖4.2.4可以很明顯看出，顯然畫(huà)上圈的那個(gè)交巡警服務(wù)平臺(tái)設(shè)置的不合理，因?yàn)樵擖c(diǎn)只與一條線路相連接，其覆蓋線段的數(shù)目太少了。如果我們將其移動(dòng)到和它間隔一個(gè)節(jié)點(diǎn)的另外一個(gè)節(jié)點(diǎn)上的話，這樣該覆蓋中心就與三條線路相連接了，顯然可以增加能在三分鐘之內(nèi)到達(dá)的節(jié)點(diǎn)的個(gè)數(shù)。這樣借助最小頂點(diǎn)覆蓋問(wèn)題的思想，我們對(duì)圖中某些不合理的地方進(jìn)行的局部的優(yōu)化和改進(jìn)，方法很機(jī)動(dòng)和方便。4.3 調(diào)度全市警力資源對(duì)嫌疑犯進(jìn)行圍堵的最佳方案4.3.1問(wèn)題分析 對(duì)于此題，我們假設(shè)交巡警在搜捕之前已經(jīng)對(duì)目擊者進(jìn)行了詢問(wèn)，能夠確定嫌疑人的相貌，體型，和車的牌照和顏色，這樣，巡警就只要堵住關(guān)鍵的路口節(jié)點(diǎn)，根據(jù)具體情況把嫌疑犯的活動(dòng)限制在少數(shù)的幾個(gè)城區(qū)內(nèi)，實(shí)現(xiàn)快速搜捕。由于交巡警是案發(fā)后3分鐘才接到報(bào)警，所以首先要確定嫌疑犯在3分鐘的的活動(dòng)范圍。但這里我們要考慮一個(gè)問(wèn)題，就是嫌疑犯能否在3分鐘之內(nèi)逃離A區(qū)，這就要我們對(duì)嫌疑犯的駕車速度進(jìn)行討論，如果他的駕車速度不過(guò)于快，在報(bào)案前未能逃離A區(qū)，就只要調(diào)動(dòng)A區(qū)的交巡警可以先堵住出入A城區(qū)的入口，然后根據(jù)嫌疑犯所有可能的逃跑路線運(yùn)用不斷減小包圍圈的地毯式搜捕方法對(duì)嫌疑犯進(jìn)行搜捕。但如果嫌疑犯的駕車速度很快，3分鐘后能夠逃離A區(qū)，根據(jù)嫌疑犯的作案地點(diǎn)，在考慮他的駕車速度符合常理的情況下，比如和警車的速度一樣，那么根據(jù)下面的計(jì)算，可以知道嫌疑犯最多只能活動(dòng)在A城區(qū)和C城區(qū)，這就需要?jiǎng)佑眠@幾個(gè)區(qū)的警力進(jìn)行搜捕，方案也比前面所說(shuō)的復(fù)雜的多，因?yàn)檫@是嫌疑犯的逃跑路線非常的多，但各區(qū)的交巡警只要確定包圍圈，然后不斷減小這個(gè)包圍圈，就能達(dá)到目的，搜捕到嫌疑人。下面就是我們根據(jù)嫌疑犯是否能夠逃離A區(qū)制定的圍堵方案。4.3.2 嫌疑犯未能逃離A區(qū) 發(fā)生重大刑事案件的地點(diǎn)位于第32節(jié)點(diǎn)上，根據(jù)分析A城區(qū)的交通網(wǎng)絡(luò)圖，通過(guò)第一題已經(jīng)編號(hào)的程序可以求出這個(gè)節(jié)點(diǎn)與16節(jié)點(diǎn)城區(qū)出入口和30節(jié)點(diǎn)附近的7節(jié)點(diǎn)交巡警平臺(tái)的距離，分別為1.14km和3.31km。所以當(dāng)嫌疑犯的駕車速度小于22.8km/h時(shí)，嫌疑犯無(wú)法逃離A區(qū)，由于這個(gè)速度值比較小，不是很符合實(shí)際，只要嫌疑犯以正常的駕車速度逃離，并且熟悉城區(qū)的地形，他就能逃離A區(qū)，所以我們?cè)谶@里簡(jiǎn)單地討論一下嫌疑犯被困在A區(qū)內(nèi)時(shí)的搜捕方案。Stept1接到報(bào)案后迅速?gòu)淖罱姆?wù)平臺(tái)派出一部分警力封鎖城區(qū)出入口。Stept2同時(shí)確定在3分鐘內(nèi)嫌疑犯能夠逃離的范圍。Stept3根據(jù)嫌疑犯所有可能的逃離方向，所有可能到達(dá)的節(jié)點(diǎn)，從最近的服務(wù)平臺(tái)派出警力進(jìn)行圍堵。Stept4不斷縮小搜捕范圍，直到嫌疑人被捕。 以上就是交巡警搜捕嫌疑犯的總體方案，在這種情況下就不具體計(jì)算了。下面我們主要要研究的就是嫌疑犯能夠逃離A城區(qū)，動(dòng)用全市警力，對(duì)其所有可能藏身的城區(qū)進(jìn)行快速搜捕的最佳方案。4.3.3嫌疑犯能夠逃離A城區(qū)我們知道，嫌疑犯只要駕車速度超過(guò)22.8km/h就能夠逃離A城區(qū)，在這里，我們不妨先假設(shè)嫌疑犯的駕車速度和警車時(shí)速一樣為60km/h。所以3分鐘內(nèi)，嫌疑犯能夠逃跑的距離為3km，通過(guò)分析附圖一中A城區(qū)的交通路線圖，得出嫌疑犯有可能逃離A區(qū)經(jīng)過(guò)的所有出入口，通過(guò)觀察與計(jì)算，并運(yùn)用前面得出的公式，可得p點(diǎn)與這些節(jié)點(diǎn)的距離：所以嫌疑犯能夠在3分鐘之內(nèi)從16和48節(jié)點(diǎn)逃離A區(qū)，我們假設(shè)各交巡警服務(wù)平臺(tái)能夠行動(dòng)及時(shí)，將城區(qū)出入口這些關(guān)鍵節(jié)點(diǎn)給封鎖，所以我們只要考慮在A城區(qū)和C城區(qū)進(jìn)行搜捕即可。(1)具體逮捕方案一、犯罪嫌疑人想盡快逃出市區(qū)，可以從在3分鐘內(nèi)經(jīng)過(guò)服務(wù)臺(tái)或沒(méi)有服務(wù)臺(tái)的的地 方逃走，經(jīng)計(jì)算3分鐘內(nèi)經(jīng)過(guò)的服務(wù)臺(tái)為7,8,9服務(wù)臺(tái)。此時(shí)可能從38,28,29,30,48等出入A區(qū)的路口逃走，但是經(jīng)計(jì)算d(16,38)d(32,38)-3d(15,28)d(32,28)-3d(15,29)3d(48,235)+ d(48,32)3由此可知在去往C區(qū)的路上警察已開(kāi)始行動(dòng)。三、由d(173,235) d(30,237)+ d(30,32)-3得，嫌疑犯從30點(diǎn)逃到C區(qū)，但由于他到達(dá)237點(diǎn)時(shí)，236點(diǎn)已被173點(diǎn)占據(jù)，所以只能另去別處。四、從長(zhǎng)遠(yuǎn)目標(biāo)看擺在眼前有兩條路，一條須經(jīng)過(guò)239點(diǎn)，另一條需經(jīng)過(guò)247到246點(diǎn)，但很顯然第二條路行不通，因?yàn)閐(173,246)d(246,247)+d(247,237)所以只能去239點(diǎn)。五、表面上到了239有三條道，但239-29點(diǎn)這條道已被15點(diǎn)服務(wù)臺(tái)封鎖，而且d(239,240)d(237,240)+d(237,32)-3所以只能選擇248目標(biāo)點(diǎn)。六、經(jīng)計(jì)算d(248,167)d(237,248)所以只能被逮捕。(2) 結(jié)果分析下面是嫌疑犯最優(yōu)逃跑路線：目標(biāo)序號(hào)123456嫌疑犯所經(jīng)過(guò)的點(diǎn)32730237238239表5-4-1 最優(yōu)逃跑路線最優(yōu)交巡警服務(wù)調(diào)配方案;（1） 第一時(shí)間把市區(qū)一些路口封鎖，具體分配如下表：交通警服務(wù)臺(tái)32415716封鎖的路口55406028,2930,4838表5-4-2 分配方案（2） 對(duì)C區(qū)第一時(shí)間一些路口封鎖，下表是各服務(wù)臺(tái)需要去封鎖的路口：交巡警服務(wù)臺(tái)173169167封鎖的路口235,245,246240248表5-4-3（3） 如此之后對(duì)所限制的路線進(jìn)行地毯式全面搜索A區(qū)和C區(qū)。第一步：對(duì)A區(qū)虛線以上部分進(jìn)行搜索圖5.4.2注：虛線以上區(qū)域就是A區(qū)交巡警搜捕的范圍第二步：對(duì)C區(qū)虛線一下部分進(jìn)行搜索圖5.4.3注：虛線以下的區(qū)域就是C區(qū)交巡警的搜捕范圍五.模型的評(píng)價(jià)與改進(jìn)5.1 我們建立的模型和方案的優(yōu)點(diǎn)：（1）在解決第一問(wèn)分配各服務(wù)平臺(tái)管轄范圍時(shí)，我們考慮的比較全面，把每個(gè)節(jié)點(diǎn)分配到里各自最近的平臺(tái)后，還分析了幾種特殊情況，比如我們分配好各節(jié)點(diǎn)的“歸宿”后又考慮了當(dāng)一條街道的兩各節(jié)點(diǎn)不歸同一個(gè)平臺(tái)管轄時(shí)，怎么分配這條街道；還有當(dāng)一條街道過(guò)長(zhǎng)或者一條街道的兩個(gè)節(jié)點(diǎn)就是交巡警服務(wù)平臺(tái)時(shí)，怎么合理得將這條街道分配給兩個(gè)服務(wù)平臺(tái)管轄。（2）在得出結(jié)果后，我們還對(duì)其做了合理度分析