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

譚 巍

（西安理工大學(xué)自動(dòng)化與信息工程學(xué)院，陜西西安 710048）

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

譚 巍

（西安理工大學(xué)自動(dòng)化與信息工程學(xué)院，陜西西安 710048）

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

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

警察肩負(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í)際課題．

1 基本假設(shè)

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

1.2 在出入城區(qū)路口所設(shè)的交巡警服務(wù)平臺(tái)堵住該路口的時(shí)間為零．

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

1.4 相鄰兩個(gè)交叉路口之間的道路近似認(rèn)為是直線．

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

2 符號(hào)說明

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

3 模型的建立與求解

3.1 問題一

3.1.1 模型的建立與求解

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

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

表1 各交巡警服務(wù)平臺(tái)管轄路口標(biāo)號(hào)及其總案發(fā)案率

3.1.2 模型的建立與求解

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

設(shè)用

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

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

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

3.1.3 模型的建立與求解

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

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

圖1 出警速度與增設(shè)平臺(tái)數(shù)的關(guān)系

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

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

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

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

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

表3 增設(shè)平臺(tái)后A區(qū)各平臺(tái)管轄路口標(biāo)號(hào)及總發(fā)案率

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

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

圖4 各個(gè)平臺(tái)總發(fā)案率對(duì)方差的貢獻(xiàn)度

從圖4中可以明顯看出有4個(gè)平臺(tái)對(duì)方差的貢獻(xiàn)度較大，分別是A10，A13，A14及A21．其中A10，A14和A21均因離其他路口較遠(yuǎn)，管轄的路口數(shù)較少導(dǎo)致總發(fā)案率偏低，造成不可避免的較大的方差貢獻(xiàn)度．A13的方差貢獻(xiàn)度大則是因?yàn)樗茌牭穆房诎l(fā)案率都較高，在資源條件允許的情況下，可以考慮在附近路口再增設(shè)一個(gè)平臺(tái)來減輕A13的工作量，具體取舍要依實(shí)際情況而定．但我們?cè)贏13附近搜索第五個(gè)平臺(tái)的位置，總體方差下降并不顯著，故選擇增設(shè)四個(gè)平臺(tái)作為最終方案．

3.2 問題二的模型

3.2.2 全市平臺(tái)的合理性

3.2.2.1 綜合評(píng)價(jià)模型

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

由上提出以下3個(gè)評(píng)價(jià)指標(biāo)：

（1）出警時(shí)間達(dá)標(biāo)率η

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

（2）平均超出時(shí)間

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

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

（3）平均工作量

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

（4）確定指標(biāo)權(quán)重

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

具體步驟如下：

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

Step2：計(jì)算效益型矩陣B 和相對(duì)偏差矩陣．

Step3：利用列向量夾角定權(quán)W并計(jì)算分?jǐn)?shù)向量Q．

通過對(duì)模型求解，最后計(jì)算分?jǐn)?shù)向量

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

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

D 增加點(diǎn) 329 333 370刪除點(diǎn) 322 325 328 E 增加點(diǎn) 388 464刪除點(diǎn) 373 376

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

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

得出結(jié)果如下：

C增加點(diǎn) 209 239 258 287 313刪除點(diǎn) 166 169 F增加點(diǎn) 507 520 527刪除點(diǎn) 483

4 模型評(píng)價(jià)

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

[1]朱茵，江越.城市道路交通應(yīng)急警力配置模型研究[J].中國安全科學(xué)學(xué)報(bào)，2010（11）.

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

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

（責(zé)任編輯：于開紅）

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-），男，重慶萬州人，西安理工大學(xué)自動(dòng)化與信息工程學(xué)院學(xué)生．