寧楠楠 李國(guó)寧 李恒宇 宋一葦

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

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

一、基于Floyd算法的交巡警服務(wù)平臺(tái)管轄范圍的分配模型

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

（一）管轄范圍分配模型

目標(biāo)矩陣：M={mij}20×92，其中：mij=0 路口j由服務(wù)平臺(tái)i管轄1 路口j不由服務(wù)平臺(tái)i管轄

約束條件：

Step3：按一定分配原則對(duì)各個(gè)路口節(jié)點(diǎn)分配其所對(duì)應(yīng)的交巡警服務(wù)平臺(tái)，分配原則如表2所示。

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

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

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

（一）模型建立與求解

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

利用MATLAB和Lingo進(jìn)行求解，步驟如下。

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

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

三、基于雙目標(biāo)優(yōu)化的服務(wù)平臺(tái)調(diào)整模型

由于出警時(shí)間過(guò)長(zhǎng)及工作量不均衡，需對(duì)全區(qū)平臺(tái)進(jìn)行調(diào)整，即增加一定數(shù)量的服務(wù)平臺(tái)。同時(shí)兩個(gè)因素必須考慮。

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

2.平臺(tái)建設(shè)是需要解決目前存在的出警時(shí)間和工作量?jī)煞矫鎲?wèn)題。因此該問(wèn)題是一個(gè)雙目標(biāo)規(guī)劃問(wèn)題。

（一） 模型建立與求解

記交巡警服務(wù)平臺(tái)i的工作量為：wi=∑pij

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

1.出警時(shí)間：由模型一的結(jié)果，標(biāo)號(hào)為28，29，38的6個(gè)路口節(jié)點(diǎn)因任何服務(wù)平臺(tái)都無(wú)法在規(guī)定時(shí)間內(nèi)到達(dá)，存在出警時(shí)間過(guò)長(zhǎng)的問(wèn)題。

2.工作量的平衡：由定義的工作量計(jì)算模型一分配方案中各交巡警服務(wù)平臺(tái)的工作量。

由圖1可知，有些服務(wù)平臺(tái)的管轄范圍與工作量均較大，如1，7，13，20；而10，12，14服務(wù)平臺(tái)則相對(duì)較小。存在交巡警資源浪費(fèi)和工作量過(guò)負(fù)荷等問(wèn)題，故A區(qū)服務(wù)平臺(tái)的設(shè)置不合理?？捎尚略黾臃?wù)平臺(tái)來(lái)平衡各服務(wù)平臺(tái)的工作量，為此建立如下雙目標(biāo)優(yōu)化模型。

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

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

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

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

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

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

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

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

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

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

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

（一）模型建立與求解

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

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

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

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

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

（二）最佳圍堵方案

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

參考文獻(xiàn)：

[1]楊豐梅，華國(guó)偉，鄧猛，等.選址問(wèn)題研究的若干進(jìn)展[J].運(yùn)籌與管理，2005（06）.

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

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

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