基于拓扑结构下的交巡警服务平台的设置与调度

摘 要：交巡警平台担负着完善交通环境，处理突发事件的责任。在城市中如何合理的设置交巡警服务平台的数量，确定管辖范围，制定服务平台的调度方案，是本文着重解决的问题。我们利用MATLAB软件建立交巡警平台管辖范围模型，针对突发事件进行合理的警力调配提出应急交巡警服务平台模型，该模型基于图论原理构建原始问题的拓扑结构，以满足在现有条件下，尽可能在指定时间内完成该区域的全封锁。可以得到优化的交巡警平台警力的合理调度方案，结合发案率，根据每个节点被服务平台覆盖的次数确定完善的交巡警服务平台的设置方案。将道路离散化处理，利用Floyd算法求解。建立相应的整数规划模型，利用贪婪算法近似求解，提出利用交巡警服务平台覆盖率和服务平台缺失率两个评价服务平台显著程度的指标。

关键词：遗传算法 计算几何 拓扑结构 贪心算法 图论法

中图分类号：G6 文献标识码：A 文章编号：1673-9795（2014）04（a）-0116-02

1 问题分析

根据某市设置交巡警平台的相关情况，为各交巡警平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。我们按照设置交巡警服务平台的原则和任务，设计了该区交巡警服务平台警力合理的调度方案。

2 交巡警服务平台覆盖模型[1]

现有交巡警警车的车速为60 km/h，要求交巡警在3分钟内到达事发地，经过计算交巡警的车速为1 km/h。

我们利用MATLAB软件编程：以交巡警服务平台为中心3 km为半径的圆，所得的圆为交巡警服务平台的覆盖范围。

设为道路节点集合为区域网络图中与每个节点相关联的到路边的集合，边的两个端点为和（假设）则，有

两个端点的距离为

，

针对上述模型1和2，采用Lingo、Lindo等软件按分支定界法求得精确解但过程是十分困难的，原因如下：

（1）分支定界法属于非多项式算法，当整数变量较多时求解困难。

（2）交巡警在3分钟内到达事发地点的比例不低于90%和3分钟以后到达重大事件部位的约束条件，很难用常规的线性与非线性表达式来精确表达。所以，该问题属于复杂非线性整数规划问题，难以精确求解，故考虑近似算法。我们选取贪婪算法进行近似求解。

5.2 评价交巡警平台设置是否合理的指标主要有以下几点

（1）交巡警服务平台收走路径包含的标记点数量占区域标记点总数的百分比。

（2）一直处在交巡警服务平台的控制区域之外的标记点数量占区域标记点总量的百分比。

我们分别用交巡警服务平台覆盖率和交巡警服务平台的缺失率来表示以上两个指标，交巡警服务平台覆盖率越高，巡警服务平台的缺失率越低，巡警服务平台设置就越显著。我们认为交巡警服务平台覆盖率达到90%以上，交巡警服务平台的缺失率低于10%时，巡警服务平台设置效果显著。

分别求解P=20～22时满足D1条件的交巡警服务平台设置方案，并给出相应的交巡警服务平台设置效果显著指标。

根据评价原则：交巡警平台覆盖率达到90%以上，同时交巡警平台的缺失率低于10%时，巡警平台设置效果显著。

结论：在A区增设2个交巡警平台；B区不用增设平台；C区增设2个平台；D区增设8个平台；E区增设5个平台；F区增设4个平台。

6 调度方案模型优缺点分析

该方案对道路数据的离散化处理，给模型建立和求解带来很大便利，对于D1要求中90%的比例，本文采用统计标记点的方式计算，精确性较高，本模型方法不依赖具体的街道走向以及城市的地理形状，具有普适性。可以推广到其他地区的交巡警服务平台的合理设置，稍加改进可用于其他有类似特点的设置问题如：巡逻问题，移动广告等，如果考虑到车流量以及道路方向本模型更具有实际意义。

参考文献

[1] 张志涌.MATLAB教程[M].北京：北京航空航天大学出版社，2004.

[2] 姜启源，谢金星，叶俊.数学模型[M].3版.北京：高等教育出版社，1997.

[3] 朱茵，江越.城市道路应急警力配置模型研究[J].中国安全科学学报2010，2011：170-176.

[4] 谢金星.优化建模与LINDO/LINGO软件[M].北京，清华大学出版社，2005.

[5] 林阳斌.110警车配置及巡逻方案[J].数学的实践与认识，2010，40（15）：186-195.