譚 巍

（西安理工大學自動化與信息工程學院，陜西西安 710048）

交巡警服務平臺的設置與調(diào)度

譚 巍

（西安理工大學自動化與信息工程學院，陜西西安 710048）

文章以2011年全國大學生數(shù)學建模競賽B題中的數(shù)據(jù)和假設為基礎，根據(jù)圖論中的Floyd算法和運籌學中的指派模型，研究了如何對現(xiàn)有交巡警服務平臺的管轄范圍進行合理地分配．建立對現(xiàn)有平臺管轄的綜合評價模型，并結合出警時間盡可能短的原則，對模型進行了優(yōu)化，得到了交巡警服務平臺管轄范圍的合理分配方案．

0-1規(guī)劃；Floyd算法；綜合評價模型；夾角余弦法

警察肩負著刑事執(zhí)法、治安管理、交通管理、服務群眾四大職能．為了更有效地貫徹實施這些職能，需要在市區(qū)的一些交通要道和重要部位設置交巡警服務平臺．每個交巡警服務平臺的職能和警力配備基本相同．由于警務資源是有限的，如何根據(jù)城市的實際情況與需求合理地設置交巡警服務平臺、分配各平臺的管轄范圍、調(diào)度警務資源是警務部門面臨的一個實際課題．

1 基本假設

1.1 假設發(fā)案率只在節(jié)點上發(fā)生，不用考慮在本區(qū)之外的情況．

1.2 在出入城區(qū)路口所設的交巡警服務平臺堵住該路口的時間為零．

1.3 所有道路都是雙向且暢通無阻的，警車由最短路徑到達事發(fā)地點．

1.4 相鄰兩個交叉路口之間的道路近似認為是直線．

1.5 警車以60km/h的速度勻速行駛，不考慮車輛的調(diào)頭、啟動、停止時的加減速過程．

2 符號說明

A0：存放各個節(jié)點之間的距離的鄰接矩陣；μ：A區(qū)所有平臺案發(fā)率的平均值；α：A區(qū)單位平臺總發(fā)案率；tij：從i到j的時間矩陣；z1：表示從所有交巡臺出發(fā)到達指定路口的距離；αij：從i到j的距離矩陣．

3 模型的建立與求解

3.1 問題一

3.1.1 模型的建立與求解

根據(jù)城市交通路口的路線，利用Floyd算法[3]求出對應點之間的最短時間路徑．由Floyd算法得到的結果對20個平臺管轄分配建立了一個整數(shù)規(guī)劃模型：

由LINGO編程求解出管轄范圍，從結果中看出，除標號28、29、38、61、92這個6點外，93.5%的路口都能在3分鐘到達．將結果整理，得到各交巡警平臺管轄路口標號及其總案發(fā)案率（如表1）．

表1 各交巡警服務平臺管轄路口標號及其總案發(fā)案率

3.1.2 模型的建立與求解

對于將二十個交巡警分配到十三個路口封堵，我們建立一個雙目標整數(shù)規(guī)劃模型：

設用

z2：表示從交巡臺出發(fā)到指定路口的時間和．

通過LINGO程序求解得出滿足條件的最小時間為8.055分鐘，與之相對應的調(diào)度方案如表2．

表2 A區(qū)快速封鎖交通要道的最佳分配方案

3.1.3 模型的建立與求解

警務部門在增設平臺時，主要考慮優(yōu)化的兩個因素是出警速度和工作量均衡度．參考信息得知，我國很多大中城市都對市區(qū)發(fā)生事故有出警時間的硬指標，故此處出警速度以最長出警時間tmax衡量；工作量均衡度以所有平臺各自管轄區(qū)域內(nèi)總發(fā)案率的方差衡量．[1]

采用寬容分層序列法，[1]來分析這兩個指標．縮短出警時間是警務部門增設服務平臺的首要目標，當出警時間被縮短到一定范圍內(nèi)時，我們可以近似地將落在這個范圍內(nèi)的出警時間看作是無差異的．若假設范圍上限為T，則[0，T]內(nèi)的出警速度都是可以接受的．采用第一小問中的要求，取T=3.在確定增設的平臺數(shù)量后，枚舉所有可能的位置，求出tmax的下界．（如圖1）其中使得解落在[0，3]內(nèi)的最小增設平臺數(shù)為4．

圖1 出警速度與增設平臺數(shù)的關系

現(xiàn)在來調(diào)整4個新增平臺的具體位置來最優(yōu)化工作量均衡度．假設l21,l22,l23,l24為4個新增平臺

的位置，ri表示平臺i(1≤i≤24)管轄區(qū)域內(nèi)的總發(fā)案率，表示各平臺管轄區(qū)域內(nèi)總發(fā)案率的平均值，則工作量均衡度的最優(yōu)化模型可以表示為：

由于未設平臺的路口有72個，采用模擬退火算法[3]求近似最優(yōu)解．

圖2 A區(qū)新增平臺位置示意圖

用模擬退火算法得到最優(yōu)工作量均衡度為2.4111，與之對應的新增平臺的具體位置為28，40，48，91（如圖2）．新增平臺后各個平臺的管轄路口標號及總發(fā)案率數(shù)據(jù)見表2.

表3 增設平臺后A區(qū)各平臺管轄路口標號及總發(fā)案率

為了驗證我們上訴4個平臺增加的合理性，畫出新增平臺后管轄區(qū)總發(fā)案率（圖3）和各個平臺的貢獻度（圖4）．

圖3 各個平臺管轄區(qū)內(nèi)總發(fā)案率

圖4 各個平臺總發(fā)案率對方差的貢獻度

從圖4中可以明顯看出有4個平臺對方差的貢獻度較大，分別是A10，A13，A14及A21．其中A10，A14和A21均因離其他路口較遠，管轄的路口數(shù)較少導致總發(fā)案率偏低，造成不可避免的較大的方差貢獻度．A13的方差貢獻度大則是因為它所管轄的路口發(fā)案率都較高，在資源條件允許的情況下，可以考慮在附近路口再增設一個平臺來減輕A13的工作量，具體取舍要依實際情況而定．但我們在A13附近搜索第五個平臺的位置，總體方差下降并不顯著，故選擇增設四個平臺作為最終方案．

3.2 問題二的模型

3.2.2 全市平臺的合理性

3.2.2.1 綜合評價模型

從出警速度的角度考慮，假設所有路口均按照模型一匹配到最近的平臺，將此時的出警速度作為評判一個區(qū)的平臺設置在時間上的合理性．

由上提出以下3個評價指標：

（1）出警時間達標率η

出警時間的達標率是指達標路口數(shù)占該區(qū)總路口數(shù)的百分比，一定程度上可以反映該區(qū)平臺設置的整體合理程度．以A區(qū)為例，設A區(qū)總路口數(shù)為NA，其中達標路口數(shù)為，不達標路口數(shù)為則

（2）平均超出時間

平均超出時間是指某區(qū)不達標路口的出警時間超出規(guī)定時間（3分鐘）部分的平均值．以A區(qū)來說，有

平均超出時間越大，該區(qū)的設置越不合理．

（3）平均工作量

先忽略區(qū)域內(nèi)工作量要平均的要求，取而代之的是區(qū)與區(qū)之間工作量的平均程度，這樣做的根據(jù)是區(qū)內(nèi)的平均程度可以容易地通過平臺的調(diào)整、增加以及算法二的安排來優(yōu)化．平均工作量是指某區(qū)所有平臺處理事件數(shù)的平均值．以A為例，設A區(qū)平臺數(shù)為nA，則為A去第i平臺的發(fā)案率．根據(jù)各區(qū)之間平均工作量的比較結果，可以為工作量大的城區(qū)增加平臺．

（4）確定指標權重

指標權重的合理確定是綜合評價結果是否可信的一個核心問題，為了避免主觀性因素的影響，我們采用客觀賦權法來確定權重．考慮到每個指標的大小是否合理要與該市整體的實際情況相聯(lián)系，而夾角余弦法很好地滿足了這種要求，故采用夾角余弦法.[3]

具體步驟如下：

Step1：求出理想的最佳方案R和最劣方案T．

Step2：計算效益型矩陣B 和相對偏差矩陣．

Step3：利用列向量夾角定權W并計算分數(shù)向量Q．

通過對模型求解，最后計算分數(shù)向量

Q=(0.9321 0.7940 0.3036 0.3875 .05080 0.4491)T看出六個城區(qū)交巡警服務平臺設置相對合理度的高低為ABEFDC，A，B兩區(qū)的綜合分數(shù)遠遠高于其他各區(qū)；同樣地，利用成本型矩陣，可以得到六個城區(qū)平臺設置相對合理度的高低為ABEDFC．從綜合評價值結果與排序可以看出A，B兩區(qū)的平臺設置方案相對合理，而其余四區(qū)存在明顯問題．

D，E兩區(qū)小，但是出警速度卻很慢，通過觀察發(fā)現(xiàn)，在平臺的設置上，有一些點明顯不合理，針對這種現(xiàn)象，我們的做法是將這些明顯不合理的點刪去，再加入等量多的平臺，使其出警速度得以優(yōu)化．對于重新加入的平臺位置選擇，采用枚舉法加快出警速度，對所有η、到一定指標的方案進行人工刪選，并在位置固定后用模型三安排每個平臺服務的節(jié)點．得出結果如下：

D 增加點 329 333 370刪除點 322 325 328 E 增加點 388 464刪除點 373 376

C，F(xiàn)兩區(qū)大，警力明顯不足，警速度也很慢，而且在平臺的設置上，也有一些點明顯不合理，針對這種現(xiàn)象，我們先將這些明顯不合理的點刪去，再加入比所刪平臺數(shù)量更多的平臺，多增加的平臺數(shù)目主要由確定，使其平均工作量降到與其他四區(qū)大概相等的水平．在數(shù)目確定的情況下，枚舉所有可能選擇，對所有η、達到一定指標的方案進行人工刪選，并在位置固定后用算法三安排每個平臺服務的節(jié)點．

由于C區(qū)點數(shù)過多，枚舉所有可能情況不切實際，且C區(qū)的發(fā)案率分布較為均勻，我們將已經(jīng)設置的平臺的周圍節(jié)點從枚舉范圍中除去，運行速度大大提升．在實際操作中，取η=0.8，=0.5規(guī)定平臺周圍的節(jié)點據(jù)平臺直線距離小于1公里．

得出結果如下：

C增加點 209 239 258 287 313刪除點 166 169 F增加點 507 520 527刪除點 483

4 模型評價

通過建立兩個不同的整數(shù)優(yōu)化模型，得到各個交巡警的管轄范圍和發(fā)生突發(fā)事件后的調(diào)動發(fā)案；采用夾角余弦法的綜合評價法，量化全市的平臺設置方案．模型簡單方便，具有很強的實用型、推廣性，可以用來解決類似的城市的緊急服務設施，如醫(yī)療救護中心、消防中心、110報警中心等等的優(yōu)化設置和合理設置的問題．

[1]朱茵，江越.城市道路交通應急警力配置模型研究[J].中國安全科學學報，2010（11）.

[2]袁新生，邵大宏，郁時練.LINGO和EXCEL在數(shù)學建模中的應用[M].北京：科學出版社，2007.

[3]劉衛(wèi)國.MATLAB程序設計與應用[M].北京：高等教育出版社，2006.

（責任編輯：于開紅）

Abstract:Based on data and assumptions in the 2011 National Mathematical Contest in Modeling Problem B is assigned according to the Floyd algorithm in graph theory and operations research model to study the how the jurisdiction of the existing Traffic Patrol service platform rational allocation. The establishment of a comprehensive evaluation model under the jurisdiction of the existing platform, combined with the principle of police time is as short as possible; the model is optimized and rational allocation of program service platform under the jurisdiction of the Traffic and Patrol Police.

Keywords:0-1 planning; Floyd algorithm; evaluation model; cosine method

Traffic Patrol service platform settings and scheduling

TAN Wei
(Xi'an University of Technology Automation and Information Engineering, Xi'an, Shanxi 710048, China)

O29

A

1009-8135（2012）03-0106-05

2012-01-20

譚 ?。?990-），男，重慶萬州人，西安理工大學自動化與信息工程學院學生．