交巡警服务平台的

1、交巡警服务平台的设置与调度刘俊东 刘奕明 史文杰1题目回顾2“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：3问题1（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意

2、图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。4问题2（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市

3、现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。5问题一模型的建立(1)各路口之间距离的确定 假设A区的交通网络与平台设置示意图中A路口的坐标为 ,B路口的坐标为 且A 、B之间有道路两桶，根据比例尺，两路口距离为 6 利用Floyd算法求解出每两个路口之间的最小路程 假设图G权的邻接矩阵为A0,经过计算,28、29、38、39、61、92这六个路口交巡警服务平台是无法再3min内到达的。78

4、Floyd算法简介弗洛伊德算法的基本思想(1)给出网络的邻接矩阵D，令D(0)=D,其元素为dij(0) 9邻接矩阵v1V3V4V226184图110(2)在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生n个矩阵（n为网络结点数） 用公式表示就是，对于K=1,2,3n,第k个矩阵运算过程中K从1开始，而 i，j 则分别从1到n取遍所有值，然后k加1，直到k等于n时停止。1121:22:42弗洛伊德算法演示ABDC123227103211221:22:42ABDC12322710321923BADDAB弗洛伊德算法演示1321:22:42ABDC1

5、232271032134ABCDABCDAB弗洛伊德算法演示1421:22:42ABDC123227103217954ABCDBCDADBAD弗洛伊德算法演示15data=xlsread(D:data.xls);connect=xlsread(D:connect.xls);A=zeros(92);for t=1:140 point_i=connect(t,1); point_j=connect(t,2); x_i=data(point_i,1); y_i=data(point_i,2); x_j=data(point_j,1); y_j=data(point_j,2); d_ij=(x_i-x

6、_j).2+(y_i-y_j).2).0.5*0.1; A(point_i,point_j)=d_ij;end16for i=1:92 for j=1:92 if A(i,j)=0 A(j,i)=A(i,j); end endendfor t=1:8464 if A(t)=0 A(t)=inf; endend17for k = 1:92 for i = 1:92 for j = 1:92 if A(i,k)+A(k,j) A(i,j) A(i,j) = A(i,k)+A(k,j); end end endend18(1)0-1变量约束.为表示第i路口的平台是否管辖第j路口的0-1变量，即(2)

7、每个路口都必须被管辖.要求每个路口由且仅由一个平台管辖,即(3)设置了平台的路口的约束.对于有平台的路口,应直接由该平台进行管辖,不应考虑其他情况,即19(4)尽量3min内赶到事发地的约束.除了6个特殊点意外,其他的点都要满足3min内有交巡警赶到,即到交巡警服务平台的距离应小于等于3km,因此有(5)对于6个3min内不能到达的路口,应该由与其距离最近的路口的平台来管理,即20MODEL:SETS:NOTE/N1.N92/:N;PLATFORM/P1.P20/:G;LINK(PLATFORM,NOTE):DISTANCE,F;ENDSETSMIN=0.05*SUM(PLATFORM(K):

8、SQRT(PLATFORM(I):G(K)-SUM(G(I);DATA:DISTANCE=OLE(G:data2.xls,data);N=OLE(G:data.xls,times);ENDDATAFOR(LINK(I,J):BIN(F(I,J);FOR(PLATFORM(I):SUM(NOTE(J):F(I,J)=1);FOR(LINK(I,J):F(I,J)=1|I#EQ#J); FOR(LINK(I_2,J_2)|J_2#NE#28#NE#29#NE#38#NE#39#NE#61#NE#92:F(I_2,J_2)*DISTANCE(I_2,J_2)3);FOR(LINK(I_3,J_3)|

9、J_3#EQ#28#EQ#29#EQ#38#EQ#39#EQ#61#EQ#92:F(I_3,J_3)*DISTANCE(I_3,J_3)MIN(LINK(I_4,J_4):DISTANCE(I_4,J_4);END2113条交通要道的封锁我的方案：（1）从20个平台中选择13个平台，使13个A区出入口都能在最快的时间完成封锁；（2）其余7个平台根据抵达时间和最小的原则，每个平台前往一个出入口。必须强调，我的方案是真正合理而符合实际的！方案一：使最后一个完成封锁的路口时间最少。22方案一的模型：23新增交巡警平台的布置问题（1）由于28,29,38,39,61,92这6个路口没有平台能在3min

10、内赶到，因此需要新增的平台能使得这6个路口可以有平台在3min内赶到。（2）在满足（1）的前提下，要使得工作量最大的平台工作量尽可能的小，工作量的分配尽可能的平衡。24第一层目标函数：第二层目标函数：25多目标规划问题简单介绍26引例1： 投资问题 某公司在一段时间内有a(亿元)的资金可用于建厂投资。若可供选择的项目记为1，2，.，m。而且一旦对第i个项目投资，就用去ai亿元；而这段时间内可得收益ci亿元。问如何如确定最佳的投资方案？ 对第i个项目投资不对第i个项目投资约束条件为：27最佳的投资方案投资最少、收益最大投资最少：收益最大双目标规划28引例2： 生产问题 某工厂生产两种产品，产品A

11、每单位利润为10元，而产品B每单位利润为8元，产品A每单位需3小时装配时间而B为2小时，每周总装配有效时间为120小时。工厂允许加班，但加班生产出来的产品利润减去1元，根据最近的合同，厂商每周最少得向用户提供两种产品各30单位。要求:1) 必须遵守合同；2)尽可能少加班；3)利润最大. 问怎样安排生产？29约束条件为：加班最少利润最大每周正常时间生产得A产品数量x1每周正常时间生产得B产品数量x3每周加班时间生产得A产品数量x2每周加班时间生产得B产品数量x430多目标规划的模型一般形式:求目标函数的最大值或约束条件为大于等于零的情况，都可通过取其相反数化为上述一般形式31定义1 把满足问题中

12、约束条件的解XRn称为可行解(或可行点)，所有可行点的集合称为可行集(或可行域)记为D即:原问题可简记为32定义2 x*是绝对最优解fj(X)fj(x*), 任意XD, j=1 px*是有效解不存在XD , 使得fj(X)fj(x*), j=1 px*是弱有效解 不存在XD , 使得fj(X)fj(x*), j=1 p绝对最优解=有效解有效解=弱有效解33定义3 像集F(R)=F(x)|xD约束集R在映像F之下的值域F*是有效点 不存在FF(D), 使得FF*；F *是弱有效点 不存在FF(R), 使得F0, 即此目标值再差也是可接受的!39多目标规划的基本解法3. 功效系数法对不同类型的目标

13、函数统一量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。40线性型功效系数法，还有其它类型的方法，如指数型方法41多目标规划的基本解法4. 评价函数法这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：42原理：距理想点最近的点作为最优解!4.1 理想点法：定义评价函数：求解非线性规划问题：434.2 平方和加权法：定义评价函数：求解非线性规划问题：先设定单目标规划的下界(想象中的最好值),即其中j为事先给定的一组权系数，满足：44原理：平方和加权法体现了通常的“自报公议”原则那些强调各自目标重要

14、者预先给出一个尽可能好的估计，然后“公议”给出一组表明各目标性的权系数，最后求解非线性规划给出解答。虚拟目标法45多目标规划的基本解法4.3 线性加权法：再定义评价函数：求解非线性规划问题：事先按目标函数f1(X)、.、fp(X)的重要程度给出一组权系数j，满足：46多目标规划的基本解法4.4 “min-max”法(极小极大法)定义评价函数：求解非线性规划问题：原理：在最不利的情况下找出一个最有利的策略!悲观主义决策47多目标规划的基本解法4.4 “min-max”法(极小极大法)(转化)此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：但可方便转化为一个简单非线性规划问题！则该规划问

15、题可等价为： 该技巧非常有用，将一个不可微的规划问题转化为可微的约束规划！48多目标规划的基本解法4.5 乘除法考虑两个目标的规划问题：求解非线性规划问题:则定义评价函数： 最优解点 如f1(x)为投资总金额，而f2(x)为投资后的总收益，则最优结果应是单位投资的总收入最大！49多目标规划的基本解法理论性结果以上所有方法所得到的最优解都是有效解(线性加权法当有权系数为零时得到的是弱有效解)!50新增交巡警平台的布置问题模型的求解：利用lingo求解第一层规划，得到结果为：然后将这个结果作为约束，代入第二层规划模型中。51全市交巡警平台设置方案52对全市现有交巡警服务平台设置合理性评价:(1)服

16、务平台警力大部分集中在A区,警力充足,而D区F区的警力明显不足;(2)C区和F区平均每个平台处理的案件数目较多,服务平台的工作强度较大;(3)D区交巡警服务平台管辖面积大,人口多,而平台数却相对较少;(4)除了A区各平台3min内无法到达的路口较少外,其他各区这样的路口都比较多,会造成这些地区到某些路口的出警时间过长,无法满足迅速到达案发地点的要求.53(1)需要对各区的人口数和面积进行加权平均,得到警力分配的指标;(2)将分配的指标转化为比例,确定各区警力的数量;(3)在确定了各区警力数量的基础上,对各区平台进行优化分配,确定最终方案.而对各区警力分配方案的确定可以参考上几问.全市交巡警平台

17、设置方案54全市范围最佳围堵方案假设:1.嫌犯的踪迹在案发后不可追踪,即3分钟内嫌犯可以跑到路程范围内允许的一切地方,而警方对此没有具体信息.2.嫌犯充分狡猾,如果有任意一条逃离市区的线路没有在合适的时间被封锁,抓捕工作都会失败.3.嫌犯的车速可快可慢,可掉头、转弯，但最大车速固定，记作v. 554.抓捕工作分两步完成:首先建立包围圈,若无法建立这样一个包围圈,则抓捕工作失败;其次,在包围圈内搜索嫌犯,基本前提是不能放跑嫌犯,目标为在尽量短的时间内抓获嫌犯,若效率相当,则使用警力越少越好.全市范围最佳围堵方案56全市范围最佳围堵方案两个定义:定义1:若点j属于点集S,且其所有邻点均属于S,则称点j为集合S的内点；反之，称其为S的边界点。将内点集记作 ，边界点集记作 . ， .定义2:若点 ,将j的所有邻点加入S称为对j的一次增广.57全市范围最佳围堵方案 如果我们能够找到一个点集S,包含嫌疑犯的出发点,且集合S的所有边界点警察都能赶在嫌犯之前到达,则围堵成功;否则围堵失败.我们希望在最小的地理范围内进行围堵.58全市范围最佳围堵方案步骤1将嫌犯在案发3分钟内可能到达过的顶点(在路上不算)集定义为初始集,记作 ;步骤2将 的所有边界点一起增广,新得到