交巡警服務(wù)平臺的設(shè)置與調(diào)

1、摘要：本文有關(guān)節(jié)點分配給平臺，也可認為對總數(shù)少于節(jié)點數(shù)的平臺分配給哪個節(jié)點的問題，怎樣分配調(diào)度是最優(yōu)的方案，考慮工作量、出警時間、路程、發(fā)案率、人口、地區(qū)面積的要素，運用運籌學中0-1整數(shù)規(guī)劃,給出最優(yōu)方案,最短路程要素通過Matlab寫的Dijstra算法算出是否能在3min到達的矩陣。針對問題一：把節(jié)點分配給平臺的優(yōu)化度問題，考慮各種要素建立目標函數(shù)，函數(shù)對應(yīng)的約束條件，通過Lingo求解得出結(jié)論。針對問題二：在問題一的基礎(chǔ)上，研究全市的優(yōu)化度，并通過模型解出最合理的設(shè)置方案，若與原圖出入較大，則調(diào)整某些個使合理度最低的點，再把模型調(diào)整采用某種方法解出時間最優(yōu)解。關(guān)鍵詞：線性規(guī)劃 0-1整

2、數(shù)規(guī)劃 優(yōu)化 動態(tài)規(guī)劃1、 問題提出（1）給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個交巡警服務(wù)平臺的設(shè)置情況示意圖。請為各交巡警服務(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ù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，擬在該區(qū)內(nèi)再增加2至5個平臺，請確定需要增加平臺的具體個數(shù)和位置。（2）針對全市（主城六區(qū)A

3、，B，C，D，E，F(xiàn)）的具體情況，按照設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，分析研究該市現(xiàn)有交巡警服務(wù)平臺設(shè)置方案的合理性。如果有明顯不合理，請給出解決方案。如果該市地點P（第32個節(jié)點）處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請給出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。2、 模型假設(shè)和符號系統(tǒng)1. 平臺和事件設(shè)置、發(fā)生在節(jié)點處;2. 事件發(fā)生的報警時間，平臺的反應(yīng)時間忽略不計;3. 警車經(jīng)過節(jié)點拐彎時間忽略不計;4. 道路，平臺，節(jié)點位置一切以圖像為準;5. 車輛的速率是穩(wěn)定的60km/h;6. 工作量不計在路上的時間;7. 兩個事件不會在同

4、一平臺管轄同時發(fā)生。變量表示的含義i第i個平臺j第j個節(jié)點最短路徑矩陣優(yōu)化度從i到j(luò)點間的最短路徑長度(km)發(fā)案率(次)t時間(min)i與j標號路是否最短路徑的路程在3公里以內(nèi)，滿足則為1，否則為0第i平臺需要的工作量3、 問題分析首先建立模型，從問題總體看出是優(yōu)化度的模型，優(yōu)化度要用到線性規(guī)劃算法，線性規(guī)劃主要解決對分配問題的優(yōu)化度，建立最終的目標函數(shù)，由警車最短行走路程，發(fā)案率的約束條件限制。算法，還有假設(shè)2條道路是否連同，連通則為1，否則為0，形成連通或斷開矩陣，便于了解真實道路狀況，來算出最短路徑，0-1整數(shù)規(guī)劃解決。接下來的算法，是Dijkstra求權(quán)算法，求權(quán)算法是求出不同路徑

5、最短路徑的長度。那么如何解模，用Lingo語言來解決目標函數(shù)。4、 模型的建立用線性規(guī)劃，建立A區(qū)優(yōu)化度：用第一題做例，目標函數(shù)：約束條件：策變量:決用Lingo解出對應(yīng)模型的:5、 模型的求解通過CAD畫出所有平臺3公里內(nèi)的區(qū)域:圖一3分鐘到達的，由圖可以直接排除29號，其余的還有28號等可以大致排除。1）用Dijstra計算最短路徑的長度，在matlab用Dijstra算法作為一個函數(shù)，代碼見附件。填入數(shù)據(jù)，統(tǒng)計excel參數(shù)B和y,見附件：求出Dij的矩陣：12345201Inf222Inf92表一在matlab輸入代碼:>> B=1751782449192;y=14.49;

6、gjdij(B,y)得出不同路徑最短路徑，再化為0-1數(shù)據(jù)：>> y<=3得到：1234520101000021010003010000400000092000000表二紅色標注最短距離在3公里以內(nèi)的,120是平臺，192是節(jié)點。同時，由圖篩選出了6個所有平臺3 min鐘內(nèi)無法到達的點分別為：j=28,29,38,39,61,92分別對應(yīng):i=15,15,16,2,7,20方案一可以選擇篩選找出大致的分配方案，并作最后答案的參考，以測驗結(jié)果的合理性，結(jié)果如下：平臺節(jié)點11,67,68,69,71,73,74,75,76,7822,40,43,44,70,7233,54,55,

7、6544,57,60,62,63,64,6655,49,50,51,52,53,56,58,5966,4777,30,32,4888,33,4699,31,34,35,4510101111,26,271212,251313,21,22,23,24141415151616,36,371717,41,421818,80,81,82,831919,77,792020,84,85,86,87,88,89,90,91表三表三僅基于距離而言的最優(yōu)方案。方案二：由距離與發(fā)案率的乘積。目標函數(shù)： 約束條件：決策變量:用Lingo解出最優(yōu)的,代碼部分見附件。得到目標函數(shù)的最優(yōu)方案:119，70，7423，39，

8、40，69，73，7532，44，54，55，67，7544，57，60，62，63，64，65，66549，5366，50，51，52，56，58，5975，30，33，48，6188，34，35，36，4797，32，4610101111、26、271212、251313、21、22、23、2414141515、28、29、31169、16、37、38、451717、41、42、431820、71、80、82、88、89、90191、18、76、77、78、79、832081、84、85、86、87、91、92表四方案三：僅由發(fā)案率討論。目標函數(shù)： 約束條件：決策變量:用Lingo解出模型

9、，代碼見附件。得到的最優(yōu)方案如下：11、67、68、69、71、73、74、75、76、7822、39、40、43、44、70、7233、54、55、65、66457、60、62、63、64549、50、51、52、53、56、58、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表四2）建立第二問

10、的模型，目標函數(shù):約束條件：同理用Lingo解出最優(yōu)的,輸入代碼，代碼在附件。得到運算結(jié)果，如下:節(jié)點12141621222324282930384862總路程平臺121631410131115781791路程06.7 3.3 7.7 0.5 3.8 4.8 8.0 3.1 4.8 4.2 4.9 57.8 表五綜上，平均要min到達13個路口,分配如上。3） 第三問的求解:根據(jù)現(xiàn)有交巡警服務(wù)平臺的工作量不均衡和有些地方出警時間過長的實際情況，需要增加2至5個平臺。由第一問可知有6個路口出警時間超過3min，等同于平臺到路口3km：信息如下表：交通路口序號282938396192出警路程（km

11、）表六再列出A區(qū)內(nèi)92個路口中，能夠分別滿足28、29、38、39、61、92這6個路口點在3min內(nèi)的警車車程趕到的所有點，如下表：交通路口序號3min內(nèi)車程的交通路口序號2828、292928、293838、39、403938、39、406148、60、619287、88、89、90、91、92表七用說理方式解決方案:首先由此可知，28，29兩點任選其一作為一平臺；38，39，40三選一作為一平臺，而60路口并不在需要緩解的路口范圍之內(nèi)，而48在，所以選48作為一個平臺；87，88，89，90，91中選一個作為平臺。因此，為滿足出警時間條件，至少新增4個平臺。其次再逐個細分，28，29中，

12、29的發(fā)案率高于28，所以選29作為交巡警平臺，29管轄28；38，40由于距離限制都不能緩解其他平臺的壓力，而39被高工作量的2平臺管轄，所以選39作為交巡警平臺，能緩解2平臺的壓力；87，88，89，90，91路口中只有89能在3min內(nèi)到達高工作量的20平臺，所以選89作為一交巡警平臺，能緩解20平臺的工作壓力。綜上所述，得到最終優(yōu)化的增設(shè)方案是：在29、39、48、89四個路口處設(shè)為交巡警服務(wù)平臺。通過CAD畫出全市所有平臺3km內(nèi)的區(qū)域：圖三在問題一的基礎(chǔ)上我們把A區(qū)擴展到全市，題中已給出全市交巡警服務(wù)平臺的位置，問題在于如何判斷題中交巡警服務(wù)平臺的位置是否合理。1) 要建立全市的模

13、型：目標函數(shù)： 決策變量：約束條件：通過Lingo軟件解出該模型，從而分配全市各平臺所管轄的各個節(jié)點。再根據(jù)上圖找出該市交巡警服務(wù)平臺在3min內(nèi)不能到達的節(jié)點。區(qū)域3min之內(nèi)不可到達的節(jié)點不合理節(jié)點附近的點C區(qū)200，201，202174D區(qū)362362E區(qū)387，388，389，390407表八由Lingo可知，看出180，477，這2個平臺的工作量太大，并且有一個平臺的工作量相對于其他平臺太小。明顯可見現(xiàn)有的交巡警分布是不合理的。解決方案：在180，477周圍增設(shè)平臺，根據(jù)平臺管轄的各個節(jié)點，考慮案發(fā)率的情況，在174，407處設(shè)為新增交巡警服務(wù)平臺，362路口很孤立，所以單獨設(shè)為新增

14、平臺，綜上，在174，362，407三處增設(shè)交巡警服務(wù)平臺，使其工作量大大減少。2) 問題二可以分析得到：3min后接警，在第一問基礎(chǔ)上，警車能在3min到達所有的節(jié)點，由圖畫出罪犯可能到達的最大范圍:圖三警車行走3min封鎖住出口，罪犯在3min大致最多走到中圓，由圖知在大圓和中圓之間的環(huán)狀區(qū)域可最快封鎖所有可能逃脫的節(jié)點出口，只要篩選出大中圓中所有節(jié)點，找出標號，調(diào)用全市警車到達這些節(jié)點?？捎玫谝活}第二問的同種方式解決，這里不再列出求解過程。6、 模型的評價問題一模型采用Lingo解出數(shù)據(jù)的統(tǒng)計的直白與清楚，再結(jié)合圖二測試結(jié)果。如圖二，直接給出3分鐘出警所能到達的點。并且建立的時候，省去一

15、些不必要考慮的因素，比如警察平臺工作量是統(tǒng)計件數(shù)，只需要發(fā)案率，而不必將出警時間也納入工作量，從而使模型理想化，便于量化與建模解模。問題二模型是問題一的擴展，分析現(xiàn)有的全市警務(wù)平臺的設(shè)置是否合理，接著對犯罪嫌疑人有可能逃往的路徑進行分析，確立出嫌疑犯有可能逃竄經(jīng)過的節(jié)點離服務(wù)平臺的最短距離，并制定出調(diào)度全市交巡警服務(wù)平臺警力資源的最佳圍堵方案。本模型仍存在不足之處，將工作量對發(fā)案率和距離的依賴簡單的看成一種線性關(guān)系，這雖然給我們的計算帶來了方便，但與實際情況還存在較大的差距。7、 參考文獻附件1.Dijstra算法程序matlab語言:function dd=gjdij(sw,swjuli)%

16、附錄一 Dijkstra算法求解最短路徑程序A=sw;y=swjuli;B=inf*ones(92);for i=1:size(A,1) B(A(i,1),A(i,2)=y(i); B(A(i,2),A(i,1)=y(i);endfor h=1:20 s=zeros(92,1); D=zeros(92,1);for v=1:92 D(v)=B(h,v);ends(h)=1;for v=1:91 j=1; while j<=92&&s(j)=1 j=j+1;endfor i=j+1:92 if s(i)=0&&D(i)<D(j) j=i;endends

17、(j)=1;for k=1:92if s(k)=0&&D(j)+B(j,k)<D(k) D(k)=D(j)+B(j,k);endendendyyh=D;enddd=yy1 yy2 yy3 yy4 yy5 yy6 yy7 yy8 yy9 yy10 yy11 yy12 yy13 yy14 yy15 yy16 yy17 yy18 yy19 yy20;2.（1）問題一(1)方案二的Lingo程序：(發(fā)案率)model:sets:ii/1.20/;jj/1.92/;perhaps/1.92/:v;links(pingtai,jiedian):w,x;endsetsmin=max(i

18、i(I):sum(jj(J):x(I,J)*v(J);)-min(ii(I):sum(jj(J):x(I,J)*v(J););for(jj(J):sum(ii(I):w(I,J)*x(I,J)=1;);for(links:BIN(x););data:w=v=ole('F:/shumoruanjian/3.xls',data1);enddataend2.（2）問題一(1)方案三的Lingo程序：(發(fā)案率*距離)model:sets:num_i/1.20/:q;num_j/1.92/:v;link(num_i,num_j):x,w;endsetsdata:v=ole('F:/shumoruanjian/3.xls',data1);w=ole('F:/shumoruanjian/4.xls',data2);enddataOBJmin=max(num_i(i):sum(num_j(j):v(j)*x(i,j);););for(link:x<=w;);for(num_j(j):sum(num_i(i):x(i,j)*w(i,j)=1;);for(link:BIN(x););END3.問題一(2)的Lingo程序：mod