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

寧楠楠 李國寧 李恒宇 宋一葦

摘要：文章研究在警力資源有限的情況下，根據(jù)城市的實際情況與需求，利用圖論、目標規(guī)劃、優(yōu)化搜索等數(shù)學模型與算法，給出合理設(shè)置交巡警服務平臺、分配各平臺的管轄范圍、調(diào)度警務資源方案。

關(guān)鍵詞：圖論；Floyd算法； 0-1整數(shù)規(guī)劃；雙目標規(guī)劃；優(yōu)化搜索

一、基于Floyd算法的交巡警服務平臺管轄范圍的分配模型

服務平臺的管轄范圍劃分依據(jù)為其能在有突發(fā)事件情況下，能在規(guī)定時間內(nèi)到達事發(fā)現(xiàn)場，在已知警車速度的條件下，轉(zhuǎn)化為服務平臺與其負責的管轄范圍最短距離是否滿足要求。因此，首先需求得各個路口節(jié)點的彼此最短路徑矩陣，然后對路口節(jié)點的性質(zhì)進行分析，最終確定其歸屬服務平臺。

（一）管轄范圍分配模型

目標矩陣：M={mij}20×92，其中：mij=0 路口j由服務平臺i管轄1 路口j不由服務平臺i管轄

約束條件：

Step3：按一定分配原則對各個路口節(jié)點分配其所對應的交巡警服務平臺，分配原則如表2所示。

求解以上模型最后得到如表3的分配方案。

二、基于0-1整數(shù)規(guī)劃的警力調(diào)度模型

警力調(diào)度可轉(zhuǎn)化為20個服務平臺中選擇13個服務平臺的0-1整數(shù)規(guī)劃問題。因各交巡警平臺的警察視為同時出動，則對全區(qū)全封鎖所需時間可用各出動的服務平臺中完成對應線路封鎖所需時間最長的來刻畫，即maxTime，因此目標函數(shù)即為所需最長的時長最短min（maxTime），時間問題可轉(zhuǎn)化為距離問題。

（一）模型建立與求解

（二）封鎖調(diào)度結(jié)果

利用MATLAB和Lingo進行求解，步驟如下。

1.同模型一的最短路徑矩陣求解方法，MATLAB中使用Floyd算法求解出20個服務平臺與13條交通要道間的最短路徑dij。

2.按交巡警服務平臺及交通要道進行對應的標號，引入決策變量xij，根據(jù)模型二0～1規(guī)劃模型，利用Lingo進行規(guī)劃求解。經(jīng)過求解后得到如表4的警力封鎖調(diào)度方案。

三、基于雙目標優(yōu)化的服務平臺調(diào)整模型

由于出警時間過長及工作量不均衡，需對全區(qū)平臺進行調(diào)整，即增加一定數(shù)量的服務平臺。同時兩個因素必須考慮。

1.考慮投入則不能為減少平均工作量而過多的建設(shè)平臺。

2.平臺建設(shè)是需要解決目前存在的出警時間和工作量兩方面問題。因此該問題是一個雙目標規(guī)劃問題。

（一） 模型建立與求解

記交巡警服務平臺i的工作量為：wi=∑pij

式中，pij為服務平臺i管轄范圍內(nèi)的路口節(jié)點j的發(fā)案率。接著對現(xiàn)有交巡警服務平臺情況進行分析。

1.出警時間：由模型一的結(jié)果，標號為28，29，38的6個路口節(jié)點因任何服務平臺都無法在規(guī)定時間內(nèi)到達，存在出警時間過長的問題。

2.工作量的平衡：由定義的工作量計算模型一分配方案中各交巡警服務平臺的工作量。

由圖1可知，有些服務平臺的管轄范圍與工作量均較大，如1，7，13，20；而10，12，14服務平臺則相對較小。存在交巡警資源浪費和工作量過負荷等問題，故A區(qū)服務平臺的設(shè)置不合理。可由新增加服務平臺來平衡各服務平臺的工作量，為此建立如下雙目標優(yōu)化模型。

3.決策變量：引入覆蓋矩陣T描述路口節(jié)點i是否滿足出警時長規(guī)定，即該節(jié)點與相應路口節(jié)點j的最短路徑dij是否在3km內(nèi)，組成元素tij為決策變量：tij=1 dij≤3km0 dij≥3km

4.描述路口節(jié)點i建立服務臺，引入決策變量ki=1 i建立服務平臺0 i不建立服務平臺 i=21，…，92

（二）平臺調(diào)整結(jié)果

直接求解該雙目標規(guī)劃模型難度較大，故將其轉(zhuǎn)化為單目標問題求解。

Step1：根據(jù)目標函數(shù)一，確定可增加服務平臺的路口節(jié)點候選集E，以及所需增加的服務平臺的最低數(shù)目N。

MATLAB求解得路口節(jié)點候選集E={28，29，38，39，61，92}；最低需求數(shù)目N=4。

Step2：將Step1中求解的結(jié)果作為新的約束條件，結(jié)合最低需求數(shù)目N，進行遍歷搜索，找出工作量方差最低的方案去求解目標函數(shù)二。具體求解方案如表5所示。

步驟1：同模型一的求解過程，求得交巡警服務平臺與路口節(jié)點的最短路徑矩陣D={dij}24×92；并按I，II類對各路口節(jié)點進行劃分，此時不存在III類節(jié)點。

步驟2：I類節(jié)點仍直接分配給唯一符合要求的交巡警服務平臺；II類路口節(jié) 點，綜合就近原則與工作量的均衡兩方面，即首先考慮距路口i最近的交巡警服務平臺j，計算該服務平臺的工作量wj，及此時的平均工作量w′。若wj≤w′，則將該路口 節(jié)點歸為該服務平臺管轄；否則選擇次短距離的服務平臺，進行同樣的考慮。最終得到相應的分配方案。

四、基于優(yōu)化搜索的最佳圍堵方案模型

假設(shè)逃犯對全區(qū)線路熟悉，即逃犯不會駛向有交巡警服務平臺的路口節(jié)點。若想在路口節(jié)點成功圍堵逃犯，則相應的服務平臺的警方必須比逃犯先到達該路口節(jié)點，因警方是在逃犯出逃3分鐘后接到通知，則成功圍堵的條件為t逃犯-i≥t警方-i+3。同時采用優(yōu)化搜索的思想進行迭代計算。，若能將逃犯所有的出逃路線都圍堵成功，那么該方案即為最佳方案。

（一）模型建立與求解

結(jié)合圍堵成功的約束條件：t逃犯-i≥t警方-i+3，確定逃犯3分鐘內(nèi)可到達的節(jié)點集E={e1，e2，…，en}，此時E為逃犯可活動范圍；找出與E中節(jié)點相連通的節(jié)點集合E′={e1′，e2，′…，en′}，該集合中的節(jié)點即為逃犯下一步可能出逃的路線節(jié)點；并且E中與之相連的節(jié)點集合為G={g1，g2，…，gn}，即逃犯可以從gi出發(fā)到達下一個出逃節(jié)點ei′。當G=？覫時，表明此時逃犯沒有可以選擇出逃的路線，即圍堵成功。接著進行如下計算過程：

Step1：取gi和ei′，滿足gi與ei′直接相連；

Step2：計算逃犯和距離ei′最近的交巡警服務平臺與ei′的最短距離d逃犯，d警方。若d逃犯≤d警方，則ei′加入E和G，表明此時ei′為逃犯可活動范圍；若d逃犯≥d警方，則ei′將從E′中刪除，即逃犯不可逃往該節(jié)點。

Step3：判斷gi是否仍與E′連通。若不存在這樣的節(jié)點，則將gi從G中刪除，即逃犯不可從節(jié)點gi出逃。

Step4：判斷是否成立。若G=？覫成立，則結(jié)束該過程求解；若不成立則重復Step1。

（二）最佳圍堵方案

最終得到如表6圍堵方案。

參考文獻：

[1]楊豐梅，華國偉，鄧猛，等.選址問題研究的若干進展[J].運籌與管理，2005（06）.

[2]李幫義，姚恩瑜.關(guān)于最短路問題的一個雙目標優(yōu)化問題[J].運籌學學報，2001（04）.

[3]祁榮賓，馮汝鵬.求解一類0-1整數(shù)規(guī)劃問題的新方法——混沌搜索算法[J].控制與決策，2003（06）.

（作者單位：寧楠楠、李恒宇、宋一葦，南京郵電大學；李國寧，蘭州理工大學）