基于遗传算法的二元覆盖模型在交通警力部署中的应用

彭怀军，秦　勇，张尊栋，杨艳芳

(1.北京交通大学　轨道交通控制与安全国家重点实验室，北京　100044;2.北方工业大学　城市道路交通智能控制技术北京市重点实验室，北京　100144)



基于遗传算法的二元覆盖模型在交通警力部署中的应用

彭怀军1，秦勇1，张尊栋2，杨艳芳1

(1.北京交通大学轨道交通控制与安全国家重点实验室，北京100044;2.北方工业大学城市道路交通智能控制技术北京市重点实验室，北京100144)

研究了以出警时间作为依据的警力部署问题，并应用基于二元覆盖的集合覆盖模型和最大覆盖模型解决问题。在介绍这两类模型后，分析了最大覆盖模型的限定条件，即限定资源数量不大于集合覆盖模型求得的结果。在应用遗传算法对两种模型求解时，阐述了算法实现过程中关键问题的处理和求解最大覆盖模型时算法的改进方法，并以北京部分路网数据对实现的算法进行了验证。试验表明了遗传算法求解的不稳定性和偏差有限的特点，验证了最大覆盖模型应用的限定条件。提出在解决资源受限的警力部署问题时，应结合集合覆盖模型求得的结果应用最大覆盖模型求解。

交通工程；交通警力部署；遗传算法；二元覆盖；限定

0　引言

在交通日益拥堵的城市里，维护交通秩序、疏导拥堵交通路段、快速处理交通事故是交警日常勤务管理工作中的重要工作[1]。然而基层交通警力不足是我国交通管理部门面临的普遍问题，如何在有限的警力条件下科学合理地配置警力、快速有效地调度警力一直是我国各级交通管理部门探索的问题[2-3]。交通警力优化部署问题是交通管理中交警勤务管理工作的难点，现有国内外研究中针对交通警力资源部署的模型和算法成果并不多见。

出警时间是衡量城市交警响应快慢的主要指标，很多城市交管部门向公众公布了最快出警时间。在最小的警力资源配置下，合理部署警力和划分责任范围才能保障区域内出警时间能达到相关的规定，提高公众服务满意度。将出警时间作为依据进行警力部署，可以应用经典的二元覆盖模型解决交通警力部署问题。集合覆盖模型(SetCoveringLocationModel,SCLM)和最大覆盖模型(MaximumCoveringLocationModel,MCLM)是两类基本覆盖模型[4]，其覆盖函数是二元化的，因此属于二元覆盖模型[5-6]。根据警力资源是否有最大数量限制，可将交通警力部署问题分成无资源限制和资源受限的两类警力部署问题，本文应用SCLM和MCLM来解决这两类问题。

常见的优化算法中，单纯形法、梯度法、分枝定界法等属于确定性的优化算法，目的是求得全局最优解，但受计算效率的影响，对大规模优化问题明显不足。遗传算法具有鲁棒性强、简单易行、计算速度快、可求出较好质量近似解的特点，被不少专家应用在求解SCLM和MCLM中[7-11]。

本文在介绍SCLM和MCLM在交通警力部署问题中的应用后，分析了最大覆盖模型应用的限定条件，然后应用遗传算法求解两种模型，并应用北京市交通警力部署案例进行实例验证。

1　应用于交通警力部署的二元覆盖模型

1.1模型参数说明

在交通警力部署问题中，将城市路网定义为网络空间N(C,R)，C和 R分别为N的节点(路口)集合和边(路段)集合，路口节点数记为m=|C|。设P为可部署交通警力地点的集合，本文中警力部署地点只可在任意一个路口上，因此有P=C。定义Dc为警力在规定出警时间内能达到的覆盖距离，dij为路口i到可部署警力的地点j之间的最短距离(∀i∈C,∀j∈P)。

模型用到的变量定义如下：

aij为0-1变量;Xj和Zi为决策变量；

wi为路口i的警力需求量或权重(如路口交通事件量、路口等级等)；

p为可部署的最大警力数量。

1.2模型假设

为了简化计算分析，模型应用中提出以下假设：

(1)将出警时间作为警力部署的依据，忽略交通事故分布、工作量等其他影响因素。

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

(3)不考虑区域特点、重点保障道路等情况，假设所有地区出警时间要求一致。

(4)假设出警速度一致，不考虑道路条件和不同时段实际交通拥堵状态的影响。

(5)只考虑主干道，忽略次干道和低级别道路。

(6)假定覆盖函数是限定0-1变量的二元化的函数，需求要么被覆盖，要么不被覆盖。当dij≤DC时，则认为路口i被地点j部署的警力覆盖；dij>DC时，则路口i不被地点j部署的警力覆盖。

1.3集合覆盖模型

SCLM最早由Roth[12]和Toregas[13]提出，用于解决应急型公共服务设施选址问题。无资源限制的警力部署问题实际是一种集合覆盖问题，是寻找最小警力资源部署点的集合，使得每个路口节点至少被1个警力在规定的出警时间内覆盖。解决这一问题的SCLM可以表示为：

(1)

(2)

目标函数(1)是要找到最佳的警力部署集合使得部署的警力总数最少；约束条件(2)表示每个路口都能被至少1个警力所覆盖。

1.4最大覆盖模型

MCLM最早由Church和Velle在1974年提出[14]。资源受限的警力部署问题实际是一种最大覆盖问题，是在有限的警力资源下如何进行警力部署，使得在规定的出警时间内覆盖尽可能多的路口。解决这一问题的MCLM可以表示为：

(3)

(4)

(5)

1.5应用最大覆盖模型的限定条件

在MCLM中限定了可部署的最大警力数量p，接下来研究p的约束条件。

由于当p≥p′时，Zi=1，则约束条件(4)与SCLM的约束条件(2)一致。由于假定p是变量，约束条件(5)与SCLM目标函数(1)一致。可见，p′是使所有需求点都被覆盖的最小设施数量，这正是SCLM求的结果：

(6)

在交通警力部署应用中，应将SCLM求得的全覆盖最小警力资源数与可部署的警力数量相比较，如果可部署的警力数量较少，可以应用MCLM求解，否则需应用SCLM求得的结果。

2　应用遗传算法求解模型

2.1遗传算法介绍

遗传算法(Genetic Algorithm，GA)是模拟生物进化过程的随机搜索优化算法，最早由J.Holland教授于1975年提出[15]。GA将问题的变量编码为染色体，再利用选择、交叉和变异3个基本算子进行运算来交换染色体信息，生成符合优化目标的染色体，再进行解码得到优化结果[16]。GA基本运算流程如图1所示，具体过程如下：

(1)染色体编码：根据问题对变量进行编码，设定染色体长度；

(2)种群初始化：设置进化代数计数器g=0，随机生成设定的M个个体作为初始种群Pg=0；

(3)适应度计算：对种群Pg中各个体进行解码，并根据适应度函数F(x)计算的每个个体的适应度；

(4)选择运算：根据选择概率ps和各个体的适应度，通过选择算子选取优良个体进行下一代繁衍，实现基因的优胜劣汰；

(5)交叉运算：根据交叉概率pc对种群两两个体进行基因交换，形成新个体；

(6)变异运算：对新个体以一定的变异概率pm进行基因值的变异操作，最终生成下一代种群Pg+1；

(7)终止条件判断：根据遗传代数或适应度提升情况判断是否满足条件，如果满足条件，则终止计算，以进化过程中具有最大适应度的个体作为最优解输出，否则跳转到步骤(3)进行下一代运算。

图1　遗传算法流程图Fig.1　Flowchart of genetic algorithm

2.2GA算法实现的关键问题

决策变量的编解码、适应度函数的设计和约束条件的处理是SCLM和MCLM优化算法实现的关键问题。下面从这3个角度阐述GA实现中的处理方法。

(1)决策变量的编解码

编解码是为了便于算法的计算机编程处理而进行的信息格式转换，为了编程计算方便，一般将编码设计成长二进制的形式。编解码的设计影响到最优解搜索和解码计算效率，对算法的收敛性和运行效率有很大影响。在GA中，要将问题的变量编码为染色体，在计算适应度和输出最优解时进行解码处理。

在SCLM和MCLM中，决策变量Xj和Zi均为0-1变量，每种决策变量的数量为路口节点数量m，将所有变量组成一个长二进制，直接用于算法流程中。

(2)适应度函数的设计

适应度函数也称评价函数，在GA迭代过程中，用其求得可行解的适应度作为可行解的择优指标，通过优胜劣汰寻找最优解。适应度函数在迭代过程中调用，计算越简单越能提升算法总体效率。由于在选择运算过程中要进行个体比较排序，适应度函数要具有单调一致、非负、最大化和计算量小的特点。

(3)约束条件的处理

约束条件的处理是优化算法研究的热点内容，也是处理实际问题经常遇到的难题，目前还没有适合各类约束的普适性方法。在应用中，常用处理约束条件的方法有限定搜索方向法、改变迭代算法、可行解变换法、罚函数法。其中，前3种算法常处理一些简单的约束条件，罚函数法则是应用最广的一种方法。在罚函数法中,罚函数及惩罚因子设计是难点，既要体现出不可行解对约束条件的不满足程度而加快算法收敛，又具有较高的计算效率。

在本文GA的算法实现中，SCLM的约束条件(2)采用罚函数法进行处理，算法迭代过程中，不满足约束条件的个体通过惩罚因子淘汰。而在MCLM中有两个约束条件(4)和(5)，很难设计两个条件不满足程度的罚函数，同时用两个罚函数处理时出现不能收敛的现象，因此需要进行算法改进。

2.3求解MCLM的GA算法改进

求解MCLM的GA算法实现中，由于难以处理两个约束条件，本文研究中对算法进行了优化改进。

算法实现中，用约束条件(4)和决策变量Xj计算出Zi，既减少了编码长度，也处理了约束条件，大大提升了算法效率。

3　实例分析

3.1试验环境及数据说明

为了验证算法的有效性，本文应用Matlab 2014a编程实现GA算法，并在CPU Intel Xeon E5-2643 3.30 GHz、内存64 G的Win Server 2008 R2 64位操作系统上运行。

试验数据是北京市海淀区和西城区二环到四环的主要路口和道路(包含成府路和学院路部分路口)的路网数据，数据中包含106个路口节点，181条边(边长为实际道路长度)。这部分路网属于城市道路的核心区域，路口分布比较均匀，没有特别长的路段，比较适合只按照到达时间的单一条件进行警力部署。

试验中假定路口发生事故后交警要在规定3 min内到达。根据北京市交通道路的平均交通状况，假定交警车辆行驶速度为30 km/h，则交警有效的覆盖半径为1.5 km。为简化模型计算，假定事故发生和警力部署位置都按照路口来计算，因此本试验中的需求和部署点是所有的路口节点。

3.2试验结果与分析

由于GA每次计算结果不完全一致，试验中，对SCLM和MCLM(限定警力资源数p=17)的算法各运行100次，记录每次运行结果的目标函数值，形成两种模型的运行结果统计图，如图2所示。

图2　SCLM和MCLM的运行结果统计图Fig.2　Statistical operation results of SCLM and MCLM

由图2可以看出：

(1)SCLM的最优解目标函数为17，MCLM(p=17)的最优解目标函数为106；

(2)GA求得的解不是唯一的，可见GA求解具有不稳定性；

(3)GA求得的所有解接近最优解。

将每次迭代过程中的最优目标函数值记录下来绘制成迭代进程图，如图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)计算最优结果按照选址路口和覆盖路口范围进行对比，如表1所示。

从表1可以看出，选址路口有8个是重合的，其余基本上是相近的，每个路口覆盖的范围也都近似，可见两模型求得结果是相近的。

将限定警力资源数p从1一直到20改变，重复计算MCLM最优的覆盖结果，得到路口节点覆盖度与限定警力资源数量的关系，如图5所示。

图5　MCLM限定警力数量与覆盖度的关系Fig.5　Relationship between limited number of police and coverage in MCLM

可以看出，随着限定警力资源数量的增大，覆盖度增大趋势变缓，当限定警力资源数量大于等于17时，覆盖度达到最大值100%。前面试验结果中，SCLM求得的最优解为17个路口节点，这正是MCLM中覆盖度达到100%的限定警力资源数量临界值。这说明试验结果与式(6) 结果是一致的。

表1　SCLM与MCLM选址路口和覆盖范围对比Tab.1　Contrast of located intersections and covering scopes

4　结论

本文应用二元覆盖的两类基本覆盖模型SCLM和MCLM来解决无资源限制和资源受限的两类交通警力部署问题，并采用遗传算法对两种覆盖模型进行了求解。以北京部分路网数据对模型的算法进行了验证和分析。根据试验结果，GA求解具有不稳定性，每次求得的解与最优解可能存在一定的偏差，但这种偏差是有限的。

试验结果表明，MCLM的限定警力数量不是任意大，不能大于SCLM求得的最小警力数量。在资源受限的交通警力部署应用中，应先用SCLM求出全覆盖下的最小警力资源数。再与限定的警力数量进行对比，如果限定的警力数量较少，则应用MCLM求解；如果限定的警力数量大，则直接应用SCLM求解结果，不必部署所有的警力。

[1]张准民, 周云金, 王时杰，等. 探索和建立交通管理“责任区”勤务模式[J]. 上海公安高等专科学校学报, 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]於昊, 陈峻, 王炜, 等. 基于遗传算法的停车设施选址规划[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