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

方案。

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.

推荐访问:求解 调度 服务平台 算法 模型