彭懷軍，秦　勇，張尊棟，楊艷芳

(1.北京交通大學　軌道交通控制與安全國家重點實驗室，北京　100044;2.北方工業(yè)大學　城市道路交通智能控制技術北京市重點實驗室，北京　100144)

?

基于遺傳算法的二元覆蓋模型在交通警力部署中的應用

彭懷軍1，秦勇1，張尊棟2，楊艷芳1

(1.北京交通大學軌道交通控制與安全國家重點實驗室，北京100044;2.北方工業(yè)大學城市道路交通智能控制技術北京市重點實驗室，北京100144)

研究了以出警時間作為依據的警力部署問題，并應用基于二元覆蓋的集合覆蓋模型和最大覆蓋模型解決問題。在介紹這兩類模型后，分析了最大覆蓋模型的限定條件，即限定資源數量不大于集合覆蓋模型求得的結果。在應用遺傳算法對兩種模型求解時，闡述了算法實現(xiàn)過程中關鍵問題的處理和求解最大覆蓋模型時算法的改進方法，并以北京部分路網數據對實現(xiàn)的算法進行了驗證。試驗表明了遺傳算法求解的不穩(wěn)定性和偏差有限的特點，驗證了最大覆蓋模型應用的限定條件。提出在解決資源受限的警力部署問題時，應結合集合覆蓋模型求得的結果應用最大覆蓋模型求解。

交通工程；交通警力部署；遺傳算法；二元覆蓋；限定

0　引言

在交通日益擁堵的城市里，維護交通秩序、疏導擁堵交通路段、快速處理交通事故是交警日常勤務管理工作中的重要工作[1]。然而基層交通警力不足是我國交通管理部門面臨的普遍問題，如何在有限的警力條件下科學合理地配置警力、快速有效地調度警力一直是我國各級交通管理部門探索的問題[2-3]。交通警力優(yōu)化部署問題是交通管理中交警勤務管理工作的難點，現(xiàn)有國內外研究中針對交通警力資源部署的模型和算法成果并不多見。

出警時間是衡量城市交警響應快慢的主要指標，很多城市交管部門向公眾公布了最快出警時間。在最小的警力資源配置下，合理部署警力和劃分責任范圍才能保障區(qū)域內出警時間能達到相關的規(guī)定，提高公眾服務滿意度。將出警時間作為依據進行警力部署，可以應用經典的二元覆蓋模型解決交通警力部署問題。集合覆蓋模型(SetCoveringLocationModel,SCLM)和最大覆蓋模型(MaximumCoveringLocationModel,MCLM)是兩類基本覆蓋模型[4]，其覆蓋函數是二元化的，因此屬于二元覆蓋模型[5-6]。根據警力資源是否有最大數量限制，可將交通警力部署問題分成無資源限制和資源受限的兩類警力部署問題，本文應用SCLM和MCLM來解決這兩類問題。

常見的優(yōu)化算法中，單純形法、梯度法、分枝定界法等屬于確定性的優(yōu)化算法，目的是求得全局最優(yōu)解，但受計算效率的影響，對大規(guī)模優(yōu)化問題明顯不足。遺傳算法具有魯棒性強、簡單易行、計算速度快、可求出較好質量近似解的特點，被不少專家應用在求解SCLM和MCLM中[7-11]。

本文在介紹SCLM和MCLM在交通警力部署問題中的應用后，分析了最大覆蓋模型應用的限定條件，然后應用遺傳算法求解兩種模型，并應用北京市交通警力部署案例進行實例驗證。

1　應用于交通警力部署的二元覆蓋模型

1.1模型參數說明

在交通警力部署問題中，將城市路網定義為網絡空間N(C,R)，C和 R分別為N的節(jié)點(路口)集合和邊(路段)集合，路口節(jié)點數記為m=|C|。設P為可部署交通警力地點的集合，本文中警力部署地點只可在任意一個路口上，因此有P=C。定義Dc為警力在規(guī)定出警時間內能達到的覆蓋距離，dij為路口i到可部署警力的地點j之間的最短距離(?i∈C,?j∈P)。

模型用到的變量定義如下：

aij為0-1變量;Xj和Zi為決策變量；

wi為路口i的警力需求量或權重(如路口交通事件量、路口等級等)；

p為可部署的最大警力數量。

1.2模型假設

為了簡化計算分析，模型應用中提出以下假設：

(1)將出警時間作為警力部署的依據，忽略交通事故分布、工作量等其他影響因素。

(2)假定需要出警需求點和警力部署地點都只在路口上。

(3)不考慮區(qū)域特點、重點保障道路等情況，假設所有地區(qū)出警時間要求一致。

(4)假設出警速度一致，不考慮道路條件和不同時段實際交通擁堵狀態(tài)的影響。

(5)只考慮主干道，忽略次干道和低級別道路。

(6)假定覆蓋函數是限定0-1變量的二元化的函數，需求要么被覆蓋，要么不被覆蓋。當dij≤DC時，則認為路口i被地點j部署的警力覆蓋；dij>DC時，則路口i不被地點j部署的警力覆蓋。

1.3集合覆蓋模型

SCLM最早由Roth[12]和Toregas[13]提出，用于解決應急型公共服務設施選址問題。無資源限制的警力部署問題實際是一種集合覆蓋問題，是尋找最小警力資源部署點的集合，使得每個路口節(jié)點至少被1個警力在規(guī)定的出警時間內覆蓋。解決這一問題的SCLM可以表示為：

(1)

(2)

目標函數(1)是要找到最佳的警力部署集合使得部署的警力總數最少；約束條件(2)表示每個路口都能被至少1個警力所覆蓋。

1.4最大覆蓋模型

MCLM最早由Church和Velle在1974年提出[14]。資源受限的警力部署問題實際是一種最大覆蓋問題，是在有限的警力資源下如何進行警力部署，使得在規(guī)定的出警時間內覆蓋盡可能多的路口。解決這一問題的MCLM可以表示為：

(3)

(4)

(5)

1.5應用最大覆蓋模型的限定條件

在MCLM中限定了可部署的最大警力數量p，接下來研究p的約束條件。

由于當p≥p′時，Zi=1，則約束條件(4)與SCLM的約束條件(2)一致。由于假定p是變量，約束條件(5)與SCLM目標函數(1)一致?？梢姡琾′是使所有需求點都被覆蓋的最小設施數量，這正是SCLM求的結果：

(6)

在交通警力部署應用中，應將SCLM求得的全覆蓋最小警力資源數與可部署的警力數量相比較，如果可部署的警力數量較少，可以應用MCLM求解，否則需應用SCLM求得的結果。

2　應用遺傳算法求解模型

2.1遺傳算法介紹

遺傳算法(Genetic Algorithm，GA)是模擬生物進化過程的隨機搜索優(yōu)化算法，最早由J.Holland教授于1975年提出[15]。GA將問題的變量編碼為染色體，再利用選擇、交叉和變異3個基本算子進行運算來交換染色體信息，生成符合優(yōu)化目標的染色體，再進行解碼得到優(yōu)化結果[16]。GA基本運算流程如圖1所示，具體過程如下：

(1)染色體編碼：根據問題對變量進行編碼，設定染色體長度；

(2)種群初始化：設置進化代數計數器g=0，隨機生成設定的M個個體作為初始種群Pg=0；

(3)適應度計算：對種群Pg中各個體進行解碼，并根據適應度函數F(x)計算的每個個體的適應度；

(4)選擇運算：根據選擇概率ps和各個體的適應度，通過選擇算子選取優(yōu)良個體進行下一代繁衍，實現(xiàn)基因的優(yōu)勝劣汰；

(5)交叉運算：根據交叉概率pc對種群兩兩個體進行基因交換，形成新個體；

(6)變異運算：對新個體以一定的變異概率pm進行基因值的變異操作，最終生成下一代種群Pg+1；

(7)終止條件判斷：根據遺傳代數或適應度提升情況判斷是否滿足條件，如果滿足條件，則終止計算，以進化過程中具有最大適應度的個體作為最優(yōu)解輸出，否則跳轉到步驟(3)進行下一代運算。

圖1　遺傳算法流程圖Fig.1　Flowchart of genetic algorithm

2.2GA算法實現(xiàn)的關鍵問題

決策變量的編解碼、適應度函數的設計和約束條件的處理是SCLM和MCLM優(yōu)化算法實現(xiàn)的關鍵問題。下面從這3個角度闡述GA實現(xiàn)中的處理方法。

(1)決策變量的編解碼

編解碼是為了便于算法的計算機編程處理而進行的信息格式轉換，為了編程計算方便，一般將編碼設計成長二進制的形式。編解碼的設計影響到最優(yōu)解搜索和解碼計算效率，對算法的收斂性和運行效率有很大影響。在GA中，要將問題的變量編碼為染色體，在計算適應度和輸出最優(yōu)解時進行解碼處理。

在SCLM和MCLM中，決策變量Xj和Zi均為0-1變量，每種決策變量的數量為路口節(jié)點數量m，將所有變量組成一個長二進制，直接用于算法流程中。

(2)適應度函數的設計

適應度函數也稱評價函數，在GA迭代過程中，用其求得可行解的適應度作為可行解的擇優(yōu)指標，通過優(yōu)勝劣汰尋找最優(yōu)解。適應度函數在迭代過程中調用，計算越簡單越能提升算法總體效率。由于在選擇運算過程中要進行個體比較排序，適應度函數要具有單調一致、非負、最大化和計算量小的特點。

(3)約束條件的處理

約束條件的處理是優(yōu)化算法研究的熱點內容，也是處理實際問題經常遇到的難題，目前還沒有適合各類約束的普適性方法。在應用中，常用處理約束條件的方法有限定搜索方向法、改變迭代算法、可行解變換法、罰函數法。其中，前3種算法常處理一些簡單的約束條件，罰函數法則是應用最廣的一種方法。在罰函數法中,罰函數及懲罰因子設計是難點，既要體現(xiàn)出不可行解對約束條件的不滿足程度而加快算法收斂，又具有較高的計算效率。

在本文GA的算法實現(xiàn)中，SCLM的約束條件(2)采用罰函數法進行處理，算法迭代過程中，不滿足約束條件的個體通過懲罰因子淘汰。而在MCLM中有兩個約束條件(4)和(5)，很難設計兩個條件不滿足程度的罰函數，同時用兩個罰函數處理時出現(xiàn)不能收斂的現(xiàn)象，因此需要進行算法改進。

2.3求解MCLM的GA算法改進

求解MCLM的GA算法實現(xiàn)中，由于難以處理兩個約束條件，本文研究中對算法進行了優(yōu)化改進。

算法實現(xiàn)中，用約束條件(4)和決策變量Xj計算出Zi，既減少了編碼長度，也處理了約束條件，大大提升了算法效率。

3　實例分析

3.1試驗環(huán)境及數據說明

為了驗證算法的有效性，本文應用Matlab 2014a編程實現(xiàn)GA算法，并在CPU Intel Xeon E5-2643 3.30 GHz、內存64 G的Win Server 2008 R2 64位操作系統(tǒng)上運行。

試驗數據是北京市海淀區(qū)和西城區(qū)二環(huán)到四環(huán)的主要路口和道路(包含成府路和學院路部分路口)的路網數據，數據中包含106個路口節(jié)點，181條邊(邊長為實際道路長度)。這部分路網屬于城市道路的核心區(qū)域，路口分布比較均勻，沒有特別長的路段，比較適合只按照到達時間的單一條件進行警力部署。

試驗中假定路口發(fā)生事故后交警要在規(guī)定3 min內到達。根據北京市交通道路的平均交通狀況，假定交警車輛行駛速度為30 km/h，則交警有效的覆蓋半徑為1.5 km。為簡化模型計算，假定事故發(fā)生和警力部署位置都按照路口來計算，因此本試驗中的需求和部署點是所有的路口節(jié)點。

3.2試驗結果與分析

由于GA每次計算結果不完全一致，試驗中，對SCLM和MCLM(限定警力資源數p=17)的算法各運行100次，記錄每次運行結果的目標函數值，形成兩種模型的運行結果統(tǒng)計圖，如圖2所示。

圖2　SCLM和MCLM的運行結果統(tǒng)計圖Fig.2　Statistical operation results of SCLM and MCLM

由圖2可以看出：

(1)SCLM的最優(yōu)解目標函數為17，MCLM(p=17)的最優(yōu)解目標函數為106；

(2)GA求得的解不是唯一的，可見GA求解具有不穩(wěn)定性；

(3)GA求得的所有解接近最優(yōu)解。

將每次迭代過程中的最優(yōu)目標函數值記錄下來繪制成迭代進程圖，如圖3和圖4所示。

圖3　SCLM的迭代進程圖Fig.3　Iterative process of SCLM

圖4　MCLM(p=17)的迭代進程圖Fig.4　Iterative process of MCLM (p=17)

將SCLM與MCLM(p=17)計算最優(yōu)結果按照選址路口和覆蓋路口范圍進行對比，如表1所示。

從表1可以看出，選址路口有8個是重合的，其余基本上是相近的，每個路口覆蓋的范圍也都近似，可見兩模型求得結果是相近的。

將限定警力資源數p從1一直到20改變，重復計算MCLM最優(yōu)的覆蓋結果，得到路口節(jié)點覆蓋度與限定警力資源數量的關系，如圖5所示。

圖5　MCLM限定警力數量與覆蓋度的關系Fig.5　Relationship between limited number of police and coverage in MCLM

可以看出，隨著限定警力資源數量的增大，覆蓋度增大趨勢變緩，當限定警力資源數量大于等于17時，覆蓋度達到最大值100%。前面試驗結果中，SCLM求得的最優(yōu)解為17個路口節(jié)點，這正是MCLM中覆蓋度達到100%的限定警力資源數量臨界值。這說明試驗結果與式(6) 結果是一致的。

表1　SCLM與MCLM選址路口和覆蓋范圍對比Tab.1　Contrast of located intersections and covering scopes

4　結論

本文應用二元覆蓋的兩類基本覆蓋模型SCLM和MCLM來解決無資源限制和資源受限的兩類交通警力部署問題，并采用遺傳算法對兩種覆蓋模型進行了求解。以北京部分路網數據對模型的算法進行了驗證和分析。根據試驗結果，GA求解具有不穩(wěn)定性，每次求得的解與最優(yōu)解可能存在一定的偏差，但這種偏差是有限的。

試驗結果表明，MCLM的限定警力數量不是任意大，不能大于SCLM求得的最小警力數量。在資源受限的交通警力部署應用中，應先用SCLM求出全覆蓋下的最小警力資源數。再與限定的警力數量進行對比，如果限定的警力數量較少，則應用MCLM求解；如果限定的警力數量大，則直接應用SCLM求解結果，不必部署所有的警力。

[1]張準民, 周云金, 王時杰，等. 探索和建立交通管理“責任區(qū)”勤務模式[J]. 上海公安高等?？茖W校學報, 2002, 12(5):51-52.

ZHANGZhun-min,ZHOUYun-jin,WANGShi-jie,etal.ProbeintoandEstablishthe“ResponsibilityArea”DutyModelofTrafficAdministration[J].JournalofShanghaiPublicSecurityAcademy, 2002, 12(5): 51-52.

[2]張湛. 北京市高峰勤務機制實施效果分析[J]. 道路交通與安全, 2010, 10(5): 46-48.

ZHANGZhan.TheEvaluationof“RushHourTrafficPolicingMode” [J].RoadTraffic&Safety, 2010, 10(5): 46-48.

[3]張兵. 高峰交通勤務工作的實踐探索與理性思考[J]. 公安研究, 2014(4): 26-30.

ZHANGBing.PracticeExplorationandRationalThinkingofPeakTrafficServiceWOrk[J].PolicingStudies, 2014(4): 26-30.

[4]DASKINM.NetworkandDiscreteLocation:Models,AlgorithmsandApplications[J].JournaloftheOperationalResearchSociety, 1996, 48(7):763.

[5]BERMANO,KRASSD,DREZNERZ.TheGradualCoveringDecayLocationProblemonaNetwork[J].EuropeanJournalofOperationalResearch, 2003, 151(3):474-480.

[6]張宗祥,楊超,陳中武. 基于服務質量的多目標逐漸覆蓋問題研究[J]. 公路交通科技, 2013, 30(10): 92-97.

ZHANGZong-xiang,YANGChao,CHENZhong-wu.Multi-objectiveGradualCoveringProblemBasedonServiceQuality[J].JournalofHighwayandTransportationResearchandDevelopment, 2013, 30(10): 92-97.

[7]BEASLEYJE.AnAlgorithmforSetCoveringProblem[J].EuropeanJournalofOperationalResearch, 1987, 31(19:85-93.

[8]BEASLEYJE,CHUPC.AGeneticAlgorithmfortheSetCoveringProblem[J].EuropeanJournalofOperationalResearch, 1994, 94(2):392-404.

[9]GROSSMANT,WOOLA.ComputationalExperiencewithApproximationAlgorithmsfortheSetCoveringProblem[J].EuropeanJournalofOperationalResearch, 1997, 101(1):81-92.

[10]BERMANO,KRASSD.TheGeneralizedMaximalCoveringLocationProblem[J].Computers&OperationsResearch, 2002, 29(6):563-581.

[11]AYTUGH,SAYDAMC.SolvingLarge-scaleMaximumExpectedCoveringLocationProblemsbyGeneticAlgorithms:AComparativeStudy[J].EuropeanJournalofOperationalResearch, 2002, 141(3):480-494.

[12]ROTHR.ComputerSolutionstoMinimum-coverProblems[J].OperationsResearch, 1969, 17(3):455-465.

[13]TOREGASC,SWAINR,REVELLEC,etal.TheLocationofEmergencyServiceFacilities[J].OperationsResearch, 1971, 19(2):93-95.

[14]RICHARDC,VELLECR.TheMaximalCoveringLocationProblem[J].PapersinRegionalScience, 1974, 32(1):101-118.

[15]HOLLANDJH.AdaptationinNatureandArtificialSystems[M].AnnArbor:UniversityofMichiganPress,1975.

[16]於昊, 陳峻, 王煒, 等. 基于遺傳算法的停車設施選址規(guī)劃[J]. 公路交通科技, 2000, 17 (6): 53-55.

YUHao,CHENJun,WANGWei,etal.GeneticAlgorithmBasedMethodforParkingFacilityPlanning[J].JournalofHighwayandTransportationResearchandDevelopment, 2000, 17(6): 53-55.

Application of Dual Coverage Model Based on Genetic Algorithm in Traffic Police Deployment

PENG Huai-jun1, QIN Yong1, ZHANG Zun-dong2, YANG Yan-fang1

(1.StateKeyLabofRailTrafficControlandSafety,BeijingJiaotongUniversity,Beijing100044,China;2.BeijingKeyLabofUrbanIntelligentTrafficControlTechnology,NorthChinaUniversityofTechnology,Beijing100144,China)

Tocopewiththeproblemofpolicedeploymentonthebasisofthepoliceresponsetime,weusedthesetcoveringlocationmodelandmaximumcoveringlocationmodelbasedondualcoveragetosolvetheproblem.Afterintroducingthe2typesofmodel,wepresentedthelimitationofthemaximumcoveringlocationmodel,thatisthelimitednumberofresourceslessthantheresultofthesetcoveringlocationmodel.Whensolvingthe2modelsbyutilizingthegeneticalgorithm,weexplainedthekeystepsofthealgorithmimplementationandthealgorithmimprovementtosolvethemaximumcoveringlocationmode.Then,weusedpartoftheBeijingroadnetworkdatatotestthealgorithm.Theexperimentalresultindicatesthatthegeneticalgorithmisnotstablewhilethedeviationistolerate,anditverifiedthelimitationofthemaximumcoveringlocationmodel.Itisproposedthattheresultofthesetcoveringlocationmodelshouldbeemployedinapplyingthemaximumcoveringlocationmodeltosolvetheproblemofrestricted-resourcepolicedeployment.

trafficengineering;trafficpolicedeployment;geneticalgorithm;dualcoverage;limitation

2015-09-10

“十二五”國家科技支撐計劃項目(2014BAG01B02)

彭懷軍(1977 -)，男，河南商城人，博士研究生.(hnphj@sina.com)

10.3969/j.issn.1002-0268.2016.10.019

U491

A

1002-0268(2016)10-0125-06