交巡警服务平台的设置与调度模型与算法求解

宿爱静

【摘 要】本文根据城市的实际情况与需求，合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。针对交巡警服务平台管辖范围的分配与警力调度问题，利用Floyd算法确定交通网络中任意两节点间的最短路径，根据其路径值建立优化模型对问题进行求解。

【关键词】交巡警服务平台的设置调度；最短路径；Floyd算法

0.引言

为了更有效地贯彻实施警察刑事执法、治安管理、交通管理、服务群众四大职能，在市区的一些交通要道和重要部位设置交巡警服务平台，使得案件发生后，巡警能够尽快抵达出事现场。本文考虑了具有完善交通路网城区各交巡警服务平台分配管辖范围的情景，使其在所管辖的范围内出现突发事件时，尽量能在规定时间内有交巡警到达事发地。当有突发事件发生时，需调度全区交巡警服务平台的警力资源，对进出该区交通要道实现快速全封锁。

为解决这一问题，我们首先用Floyd算法求出城区平台到路口的最短路径及其距离，然后进行分配。对于每一个路口，找出距离它最近的平台，并将路口归这个平台管辖，按此方法即可得到交巡警服务平台的分配方法，使事故发生时，交巡警能以最快的速度赶到。当事故发生时，需要从全部平台中选一定数量的平台分配。所以我们用Floyd算法求出该城区所有平台到所有路口的最短路径及其距离，然后以最晚到达封锁路口的警力所需要的时间最短为优化目标进行优化，得到最佳方案。

1.案例说明与模型的建立

为了方便建立模型并使得模型更符合实际需求，本文首先对模型做了以下假设：（1）出警过程中，警车行驶的总是最短路径；（2）所有道路均为双行道；（3）在较短的时间内，服务平台管辖范围里不会出现两个以上的突发事件；（4）假设出现突发事件后立即有人报警，交巡警服务平台接警后，准备时间忽略不计，视为立刻出发，即出警时间仅包含警方从服务平台驱车到达事发地的时间.（5）假设一个平台的警力最多封锁一个路口。（6）假设每个交巡警服务平台的职能和警力配备基本相同。（7）假設嫌犯逃窜的速度与警车平均时速相同。

本文规定rij为任意两节点i与j间的最短路径；xij表示节点i是否属于平台j管辖，若等于1则i属于j管辖，等于0则i不属于j管辖；dij表示节点i和j的最短距离；S为警力封锁最后一个路口所用的时间；ri表示路口i的案发率。

本文参考了2011年“高教杯”全国数学建模比赛B题的数据。要为城区A各交巡警服务平台分配管辖范围，我们先用Floyd算法求出该区20个平台到92个路口的最短路径及其距离，然后对于每一个路口，找出距离它最近的平台，并使此路口归这个平台管辖，即可得到分配结果。根据图论，以城区各路口节点为图G的顶点，以交通网中任意两路口节点之间路线为图G相应两顶点的边，得图G。对G的每一边e，赋以一个实数w（e）表示连接两路口节点路线的长度，称为该边的权，得到赋权图G。利用matlab编程求出图G中有边的任意两节点i与j间的路径rij及其长度dij，若节点i与j间不连通则dij，（1≤i≤92，1 ≤j≤20），得到邻接矩阵。用matlab编出Floyd算法，代入邻接矩阵，从而求出A区20个平台到92个路口的最短路径及其距离。

根据上面的结果，对于每一个路口，找到距离它最近的平台，将此路口归这个平台管辖，按此方法即可得到交巡警服务平台最终的分配方法，如下表1所示：

本文考虑了为调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，所以我们要在20个平台中选13个进行优化分配，使最晚到达路口的警力所需时间最短。首先以城区各路口节点为图G的顶点，城区交通网中连接两路口节点路线为图G相应两顶点的边，得图G。对G的每一边e，赋以一个实数w（e）表示连接两路口节点路线的长度，称为该边的权，得到赋权图G。

利用matlab编程得到距离矩阵，代入到Floyd算法，求出20个平台到13个节点的最短距离dij（1<=i<=20，1<=j<=13）。引用0-1规划模型，用xij表示路口是否归平台管辖（等于1为i归j管辖，等于0为i不归j管），S为警力封锁最后一个路口所用的时间。以最晚到封锁路口的警力所走距离S最短为优化目标，以每个平台到所管辖路口距离小于S、每一个路口有且仅有一个平台管辖、一个平台至少管一个路口为约束条件进行优化，所建立的优化模型如下：

2.结论

本文以交巡警平台的设置和调度问题的情境下，考虑了如何对交巡警平台的警力分配问题，建立模型并用Matlab软件求解，在处理数据过程中，利用Excel 软件对数据进行处理并作出各种图表，简便、直观并运用多种数学软件（如Matlab、LINGO），取长补短，使计算结果更加准确；同时也对一些数据进行了必要的近似处理，会带来一定的误差，另外模型中为使计算简便，使所得结果更理想化，忽略了一些次要的影响因素。 [科]

【参考文献】

[1]陈华友.运筹学[M].合肥：中国科技大学出版社，2008.

[2]韩中庚.实用运筹学[M].北京：清华大学出版社，2007.

[3]韩中庚.数学建模方法及其应用[M].北京：高等教育出版社，2005.

[4]杨桂元，黄己立.数学建模[M].合肥：中国科技大学出版社，2008.

[5]谢金星，薛毅.优化模型与LINDO/LINGO 软件[M].北京：清华大学出版社，2005.