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

1、交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度一、問題重述“有困難找警察”，是家喻戶曉的一句流行語。警察肩負(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給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警服 務(wù)平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息

2、見附件 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í)間過長的實(shí)際情況，擬 在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置。(2)針對(duì)全市(主城六區(qū)A, B, C, D, E, F)的具體情況，按照設(shè)置交巡警服務(wù) 平臺(tái)的原則和任務(wù)，分析研究該

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

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

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

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

7、車行駛中速度保持勻速且車速均為60km/h ;12 .假設(shè)巡警在接到報(bào)案后并不知道逃犯的逃跑方向；13 2符號(hào)說明彳路口被平臺(tái)管轄1. _ _、；,路口不被平臺(tái)管轄2 .:路口 i到j(luò)的最短距離；3 .:交巡警能夠在3分鐘內(nèi)到達(dá)的路口集合；4 .:能夠在3分鐘內(nèi)到達(dá)路口 i的交巡警平臺(tái)的集合；5 .:交巡警不可在3分鐘內(nèi)到達(dá)的路口集合；6 .:第i個(gè)路口的發(fā)案率；7 .一：交巡警服務(wù)平臺(tái)的平均工作量；8 .:平臺(tái)j的工作量；第 條交通要道由交巡警服務(wù)平臺(tái)封鎖9 .,第條交通要道不由交巡警服務(wù)平臺(tái)封鎖10 .:第i條交通要道到平臺(tái)j的最短距離；一在路口處增加平臺(tái)11 .不在路口 處增加平臺(tái)12

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

9、口不被平臺(tái)管轄麻、幾0假設(shè)管轄為路口 i到交巡警平臺(tái)j的最短距離。為交巡警可在分鐘內(nèi)到達(dá)的路口集合，即若使得,則 。為能夠在3分鐘內(nèi)到達(dá)路口 i的交巡警平臺(tái)的集合。止匕目標(biāo)可表小為:對(duì)于第二個(gè)目標(biāo), 為：假設(shè) 為交巡警不可再3分鐘內(nèi)到達(dá)的路口集合，此目標(biāo)可表示對(duì)于第三個(gè)目標(biāo)，本文用每個(gè)平臺(tái)所管轄路口發(fā)案率的和表示平臺(tái)的工作量，用工 作量的變異系數(shù)來度量各平臺(tái)工作量的均衡度，各平臺(tái)工作量越均衡，變異系數(shù)越小。假設(shè) 為第i個(gè)路口的發(fā)案率，一為所有平臺(tái)的平均工作量，為第j個(gè)平臺(tái)的工作量, 此目標(biāo)可表小為:滿足條件為:1 .每個(gè)路口由一個(gè)交巡警服務(wù)平臺(tái)管轄:2 .每個(gè)交巡警服務(wù)平臺(tái)至少管轄一個(gè)路口 :

10、3 .每個(gè)交巡警服務(wù)平臺(tái)必須管轄本路口 :4.1.2模型求解對(duì)于模型中的多目標(biāo)規(guī)劃問題，本文將之轉(zhuǎn)化為單目標(biāo)規(guī)劃問題。首先將目標(biāo)一和 目標(biāo)二解出，然后將這兩個(gè)目標(biāo)作為約束條件，以目標(biāo)三作為最終的單目標(biāo)用lingo軟件求出最終解。1 .各路口間最短距離的確定。2 2首先用wj = sqrt （xi - Xj ） +（yj - yj ）公式算出兩兩之間的距離（如果 有路），得出582*582的鄰接矩陣，其中矩陣中的元素表示兩兩之間的距離，若不存在 路，則用一個(gè)較大的數(shù)代替，在matlab環(huán)境下利用floyd算法求出最短路程矩陣D,矩 陣D中兩兩之間的距離即為。程序見附錄一。Floyd算法的基本步驟

11、如下：令是頂點(diǎn)到頂點(diǎn)的最短距離，是頂點(diǎn)到的權(quán)。STEP1輸入臨界矩陣 W對(duì)所有i, j, 有 二,k=1。STEP2:更新 。對(duì)所有i, j, 若 +< ，則令 =+。STEP3:若 <0,則存在一條含有頂點(diǎn)的負(fù)回路，停止；或者k=n停止，否則轉(zhuǎn)到STEP22.目標(biāo)一和目標(biāo)二的求解用MATLA編程從上述得到的各路口的最短距離中抽出 92個(gè)路口分別到20個(gè)服務(wù) 平臺(tái)的最短距離。篩選出的點(diǎn)，求出交巡警可在3分鐘內(nèi)到達(dá)的所有路口 （集合），剩下的路口則為交巡警不可能在 3分鐘內(nèi)到達(dá)的路口（集合）。程序見附錄二。為滿足目標(biāo)一，只需要滿足：中的路口直接分配給距離此路口最近為滿足目標(biāo)二，將集合

12、 的交巡警服務(wù)平臺(tái)。結(jié)果如下:交巡警平臺(tái) 151620管轄路口28、29383961923.最終方案的確定將目標(biāo)一、二作為約束條件，目標(biāo)三作為最終單目標(biāo)，可得如下最終模型:其中 表示交巡警不能在3分鐘內(nèi)趕到的路口 i被平臺(tái) 管轄。用lingo求解得最小變異系數(shù)為1.934,最終分配方案如下（程序見附錄三）交巡警服務(wù)平臺(tái)管轄路口工作量（次）11、 67、 69、 76、 77、 79、 807.122、40、43、73、757.233、 44、 54、 55、 66、 686.944、 57、 60、 62、 63、 64、 657.355、 49、 53、 56、 596.166、 50、 5

13、1、 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、 91、 927.34.2 問題一（2）:封鎖方案的確定4.2.1 模型建立本問要求調(diào)

14、度20個(gè)交巡警服務(wù)平臺(tái)對(duì)A區(qū)的13條交通要道實(shí)現(xiàn)快速封鎖，且每個(gè) 平臺(tái)最多封鎖一個(gè)路口。實(shí)現(xiàn)完全封鎖的時(shí)間取決于13條交通要道中被封鎖最長的時(shí)問。本文將時(shí)間問題轉(zhuǎn)化為距離問題。對(duì) 13條要道實(shí)現(xiàn)最快封鎖，即是將平臺(tái)到 13條 被封鎖要道中的最長距離最小化?？山?01規(guī)劃模型。建立01變量:第 條交通要道由第個(gè)交巡警服務(wù)平臺(tái)封鎖,第條交通要道不由第個(gè)交巡警服務(wù)平臺(tái)封鎖假設(shè) 為第i條交通要道到第j個(gè)平臺(tái)的距離。其中i=1,2 -13;j=1,2 200目標(biāo)函數(shù)：平臺(tái)到13條被封鎖要道中的最長距離最小：約束條件為：1.每條交通要道必須有一個(gè)交巡警服務(wù)平臺(tái)進(jìn)行封鎖。2.每個(gè)交巡警平臺(tái)最多封鎖一條交通

15、要道。綜上所述，此優(yōu)化模型為:用表示上述模型解出的最小值。將上述模型解出后，依然存在多種封鎖方案，我們做進(jìn)一步優(yōu)化?？紤]到警力資源有限，以封鎖距離總和最短為目標(biāo)函數(shù)，上述模型 解出的最小值為約束條件進(jìn)一步做0 1規(guī)劃求得最終封鎖的調(diào)度方案。模型如下:4.2.2 模型求解首先從最短路程矩陣D中，篩選出13條交通要道到各交巡警平臺(tái)的最短距離，并 且依照13條交通要道的順序進(jìn)行113編號(hào)，得到13*20的要道和平臺(tái)間的距離矩陣。 然后用lingo對(duì)上述兩個(gè)模型分別進(jìn)行編程求得最優(yōu)解。程序分別見附錄四與附錄五。 最終結(jié)果如下：,最短封鎖時(shí)間為8.02min 封鎖方案為：路口標(biāo)寧121416212223

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

17、分。 然后我們?cè)谒新房诙寄軌蛴山谎簿?3分鐘內(nèi)到達(dá)的前提下，考慮如何解決平臺(tái)工作量 不均衡的問題。對(duì)于交巡警服務(wù)平臺(tái)工作量不均衡的問題，利用問題一（1）中的方法，用工作量的變異系數(shù)衡量平臺(tái)工作的均衡度，以工作量的變異系數(shù)取得最小值為目標(biāo)函數(shù)建立01 規(guī)劃模型。建立 01變量在路口處增加平臺(tái)不在路口 處增加平臺(tái)路口被平臺(tái) ,路口不被平臺(tái)管轄。n為新增加交巡警平臺(tái)的個(gè)數(shù)。 管轄目標(biāo)函數(shù)可表示為:其中 為路口 i的發(fā)案率，一為所有平臺(tái)的平均工作量 約束條件為：1 .交巡警平臺(tái)個(gè)數(shù)為20+n：2 .所有路口到管轄平臺(tái)間的距離不大于3km其中為路口 i和路口 j之間的距離。3 .每個(gè)路口都要被一個(gè)平臺(tái)

18、進(jìn)行管轄：；4 .每個(gè)交巡警服務(wù)平臺(tái)必須管轄本路口 ：5 .只有當(dāng)路口 j處增加了平臺(tái)j時(shí)，才可以管轄其他的路口6 .第1,220個(gè)路口處原本就設(shè)有平臺(tái)：綜上所述，此模型為：4.3.2模型求解由問題一（1）的求解可知，在A區(qū)現(xiàn)有20個(gè)平臺(tái)的設(shè)置下，集合 中的路口不能由交巡警在3分鐘內(nèi)及時(shí)趕到。從最短路程矩陣D中搜索出A區(qū)距離 中各路口距離小于等于3km的路口，結(jié)果如下:路口稱號(hào)282938396192符合條件的路口28,2928,2938,39,4038,39,4048,6187,88,89,90,91,92從上面結(jié)果可知，最少增加4個(gè)平臺(tái)才可以使得這6個(gè)路口可以由交巡警在3分鐘 內(nèi)趕到，這樣

19、就滿足了所有路口都可以由交巡警在 3分鐘內(nèi)趕到。因此為解決有些地方 出警時(shí)間過長的問題，需要增加 4或5個(gè)平臺(tái)。將n=4和n=5分別代入上述0-1規(guī)劃模型，用lingo求解，程序見附錄六，得到如 下結(jié)果：增加平臺(tái)數(shù)平臺(tái)增加位置均衡度（變異系數(shù)）428、40、48、901.74910528、39、48、87、881.69758從表格可以看出增加5個(gè)平臺(tái)要比4個(gè)平臺(tái)均衡度高，但是由于兩者均衡度相差并 不大，都可以解決出警時(shí)間過長的問題，且實(shí)際問題中增加一個(gè)平臺(tái)所需花費(fèi)很多，因 此最終選擇為：增加4個(gè)平臺(tái)，位置為路口 28、40、48和87。4.4 問題二（1）交巡警平臺(tái)設(shè)置的評(píng)價(jià)與改進(jìn)4.4.1

20、現(xiàn)有交巡警平臺(tái)設(shè)置的合理性的評(píng)價(jià)本文對(duì)現(xiàn)有交巡警平臺(tái)的設(shè)置定義了兩個(gè)評(píng)價(jià)原則：1 .交巡警能在3分鐘內(nèi)到達(dá)案發(fā)路口2 .各平臺(tái)的工作量均衡度盡量高依據(jù)這兩個(gè)評(píng)價(jià)原則，分別對(duì)6個(gè)區(qū)現(xiàn)有的平臺(tái)設(shè)置進(jìn)行評(píng)價(jià)。首先將6個(gè)區(qū)的平臺(tái)依據(jù)問題一 （1）的方式進(jìn)行管轄區(qū)域的劃分，得到結(jié)果如下:區(qū)域不能由交巡警3分鐘 內(nèi)到達(dá)的路口個(gè)數(shù)（）路口所占總路口 的比重平臺(tái)工作量均衡度 （變異系數(shù)）A區(qū)66.5%1.934B區(qū)68.2%1 .925C區(qū)4730.5%4 .083D區(qū)1223.1%2 .253E區(qū)3231.1%3 .798F區(qū)3532.4%4 .562對(duì)于原則一：A區(qū)和B區(qū)不能由交巡警在3分鐘內(nèi)到達(dá)的路口個(gè)

21、數(shù)即路口個(gè)數(shù)比較少，較符合原則一的要求。C、E、F三個(gè)區(qū) 路口所占比重過高，明顯不合理。對(duì)于原則二，在問題一（1）中，我們已經(jīng)分析到對(duì)于變異系數(shù)為 1.934的A區(qū)，工 作量的均衡度是比較好的，因此我們可以推測 B區(qū)的均衡度也是比價(jià)好的。而 G E、F 三個(gè)區(qū)的變異系數(shù)過高，因此均衡度較差。綜上所述，A區(qū)和B區(qū)的設(shè)置較合理，D區(qū)稍不合理，而 G E、F區(qū)嚴(yán)重不合理4.4.2 交巡警服務(wù)平臺(tái)設(shè)置的優(yōu)化4.4.2.1 模型建立由上面分析可知，很多區(qū)不能由交巡警在 3分鐘趕到的路口過多，出警時(shí)間過長， 因此我們首要選擇增加交巡警服務(wù)平臺(tái)對(duì)每個(gè)區(qū)進(jìn)行優(yōu)化，優(yōu)化方式按照問題一（3）中的模型，對(duì)每個(gè)區(qū)有：

22、1 .集合 中的路口表示不能由交巡警在 3分鐘內(nèi)及時(shí)趕到的該區(qū)路口，從最短路程 矩陣D中搜索出該區(qū)距離 中各路口距離小于等于 3km的路口，解出初步增加的平臺(tái) 個(gè)數(shù)，使得該區(qū)每個(gè)路口都可由交巡警在 3分鐘內(nèi)到達(dá)，解決了某些地方出警時(shí)間過長 的問題。2 .解決平臺(tái)工作量不均衡的問題，建立如問題一（3）的模型：其中表示第個(gè)區(qū)現(xiàn)有的平臺(tái)數(shù)量;表不第m個(gè)區(qū)起始的路口編號(hào);表示第m個(gè)區(qū)終止的路口編號(hào)；表示第m個(gè)區(qū)現(xiàn)有最后一個(gè)平臺(tái)所在的路口編號(hào)。4.4.2.12模型求解將上述模型用lingo求解，得到最終結(jié)果如下:區(qū)域增加平臺(tái)個(gè)數(shù)增加平臺(tái)位置平臺(tái)工作量均衡度 （變異系數(shù)）A428、40、48、901.74

23、910B2104、 1471.65277C20183、208、201、203、206、214、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ū)的所有路口都可由交巡

24、警在 3分鐘內(nèi)到達(dá)，解決了某些地方 出警時(shí)間過長的問題，而且6個(gè)區(qū)的工作量均衡度均在1.62.1之間，相比之前得到了 很大的提高。4.5 問題二（2）圍堵方案的確定4.5.1 模型建立根據(jù)題意，為了快速搜捕嫌疑犯，也就是說，各個(gè)平臺(tái)到封鎖路口的時(shí)間要最短，即 最大搜索距離最短，首先求出需要封鎖的路口，具體做法為：先計(jì)算出嫌疑犯3分鐘走的路程為30,再以P32點(diǎn)為圓心，以30為半徑形成一個(gè)包圍圈，在這個(gè)包圍圈的 名鄰 域內(nèi)選出若干個(gè)路口，再以這些路口為圓心，10t為半徑形成若干個(gè)包圍圈，從而建立模型如下：目標(biāo)函數(shù)：min= max(dJxj)約束條件：二1選擇第i個(gè)路口節(jié)點(diǎn)到第j個(gè)服務(wù)平臺(tái)xij

25、 - o不選才i第i個(gè)路口節(jié)點(diǎn)到第j個(gè)服務(wù)平臺(tái)maxdjSxijLmkSp/v -3/60)即 max(dj* xij),二 min(Sp -30)563、xij < 1j H80"xj -1 i 14.5.2 模型求解將上述模型用lingo求解，(程序見附錄七)結(jié)果如下:路口平臺(tái)151731519396382153951771772021752031802351623615264182317178181325324328327332380362323387100418375483478541476572484578485479此時(shí)最溫時(shí)間為：12.68027min0附錄附錄一

26、（matlab）data=xlsread（'cumcm2011B附件2_全市六區(qū)交通網(wǎng)路和平臺(tái)設(shè)置的數(shù)據(jù)表.xls',1）;x=data(:,2);y=data(:,3);rate=data(:,5);boolean=zeros(582,582);%每個(gè)路口的橫坐標(biāo)%路口的縱坐標(biāo)%路口的發(fā)案率route=xlsread（'cumcm2011B 附件2_全市六區(qū)交通網(wǎng)路和平臺(tái)設(shè)置的數(shù)據(jù)表.xls',2）;route=route(2:929,1:2);for i=1:928否則為0%直接連接的兩路口，矩陣元素為1,boolean(route(i,1),route(i

27、,2)=1;boolean(route(i,2),route(i,1)=1; endfor i=1:582boolean(i,i)=1; endw=zeros(582,582);for i=1:582for j=1:582if boolean(i,j)=1w(i,j)=sqrt(x(i)-x(j)A2+(y(i)-y(j)A2);else w(i,j)=9999;end%求出鄰接矩陣endendD,R=floyd(w);function D,R=floyd(a)%n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end弗洛伊德算法endfor k=1

28、:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendend附錄二(matlab)d=D(1:20,1:92);U0=;U1=;for i=1:92sum=0;for j=1:20if d(j,i)<=30sum=sum+1;endendif sum>=1U0=U0,i;elseU1=U1,i;endend附錄三(lingo)sets :lukou/1.92/:r;pingtai/1.20/:rr;link(lukou,pingtai):x,d;endse

29、tsdata :r= ole ('G:/數(shù)學(xué)建模/國賽/2011/B/cumcm2011B 附件2_全市六區(qū)交通網(wǎng)路和平臺(tái)設(shè)置的數(shù)據(jù)表.xls',rate);d= ole ('G:/數(shù)學(xué)建模 /國賽/2011/B/shortdistance.xlsx',distance);enddatamin =(z/19)A0.5;for (pingtai(j):rr(j)=sum(lukou(i):x(i,j)*r(i);rp= sum(lukou:r)/20;z= sum(pingtai:(rr-rp)A2);for (link(i,j)|i#ne#28#and# i#n

30、e#29 #and# i#ne#38 #and# i#ne#39 #and# i#ne#61#and# i#ne#92:x(i,j)*d(i,j)<=30);for (link(i,j)|i#eq#28#and#j#eq#15 #or# i#eq#29#and#j#eq#15 #or#i#eq#38#and#j#eq#16 #or# i#eq#39#and#j#eq#2 #or# i#eq#61#and#j#eq#7 #or#i#eq#92#and#j#eq#20:x(i,j)=1);for (lukou(i):sum(pingtai(j):x(i,j)=1);for (pingtai(

31、j):sum(lukou(i):x(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/交通要道與交巡警平臺(tái)的距離.xlsx');enddatamin =maxjink:y*s);for (yaodao(i):sum(pingtai(j):y(i,j)=1);for (pingtai(j):sum(yaodao(i):y(i,j)<=1);for (

32、link: bin (y);附錄五(lingo)sets :yaodao/1.13/;pingtai/1.20/;link(yaodao,pingtai):s,y;endsetsdata :s= ole ('G:/數(shù)學(xué)建模/國賽/2011/B/交通要道與交巡警平臺(tái)的距離.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(yaodao(i):y(i,j)<=1);for (link: bi

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