交巡警服務平臺的設置與調度

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

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

關鍵詞：圖論；Floyd算法； 0-1整數規劃；雙目標規劃；優化搜索

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

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

（一）管轄范圍分配模型

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

約束條件：

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

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

二、基于0-1整數規劃的警力調度模型

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

（一）模型建立與求解

（二）封鎖調度結果

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

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

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

三、基于雙目標優化的服務平臺調整模型

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

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

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

（一） 模型建立與求解

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

式中，pij為服務平臺i管轄范圍內的路口節點j的發案率。接著對現有交巡警服務平臺情況進行分析。

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

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

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

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

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

（二）平臺調整結果

直接求解該雙目標規劃模型難度較大，故將其轉化為單目標問題求解。

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

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

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

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

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

四、基于優化搜索的最佳圍堵方案模型

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

（一）模型建立與求解

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

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

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

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

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

（二）最佳圍堵方案

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

參考文獻：

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

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

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

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