1、交巡警服务平台的设置与调度交巡警服务平台的设置与调度刘俊东刘俊东 刘奕明刘奕明 史文杰史文杰 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题1 （1）附件1中的附图1给出了该市中心城区A的交通网络和现有
2、的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题2 （2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置
3、交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。 如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。问题一模型的建立(1)各路口之间距离的确定 假设A区的交通网络与平台设置示意图中A路口的坐标为 ,B路口的坐标为 且A 、B之间有道路两桶，根据比例尺，两路口距离为 ),(11yx),(22yx)( 1 . 0)()(221221ABkmyyxxd 利用Floyd算法求解出每两个路口之间的最小路程 假设图
4、G权的邻接矩阵为A0,经过计算,28、29、38、39、61、92这六个路口交巡警服务平台是无法再3min内到达的。Floyd算法简介弗洛伊德算法的基本思想(1)给出网络的邻接矩阵D，令D(0)=D,其元素为dij(0) 不相连，相连jijijildijij,0,)0(邻接矩阵v1V3V4V226184图图108480124106260) 0(D(2)在原路径里增加一个新结点，如果产生的新路径比原路径更小，则用新路径值代替原路径的值。这样依次产生n个矩阵（n为网络结点数） 用公式表示就是，对于用公式表示就是，对于K=1,2,3n,第第k个矩阵个矩阵,min)1()1()1()(kkjkikki
5、jkijdddd运算过程中运算过程中K从从1开始，而开始，而 i，j 则分别从则分别从1到到n取遍所有取遍所有值，然后值，然后k加加1，直到，直到k等于等于n时停止。时停止。1:32:07弗洛伊德算法演示弗洛伊德算法演示ABDC1232271长度长度0123001712022023130路径路径01230ABAD1BABC2CD3DADB0321( 1) . Di jG arcsi j1:32:07ABDC12322710321长度长度012300171202202310路径路径01230ABAD1BABC2CD3DA(0)( 1)( 1)( 1) , 00 Di jM in Di j DiD
6、j(0)( 1)( 1) 1 3 , 1 0 0 3 ,27 ,99DM inDDM inM in(0) 3 13,112DM in92 3BADDAB弗洛伊德算法演示弗洛伊德算法演示1:32:07(1)(0)(0)(0) 3 2 3 2 , 3 1 1 2 ,2 24DM i n DDDM i n ABDC12322710321长度长度01230017120292023120路径路径01230ABAD1BABCBAD2CD3DA(1)(0)(0)(0) , 1 1 Di jM i n Di j DiDj(1)(0)(0)(0) 0 2 0 2 , 0 1 1 2 , 1 23DM i n D
7、DDM i n 3 4ABCDABCDAB弗洛伊德算法演示弗洛伊德算法演示1:32:07ABDC12322710321长度长度01230013120220231240路径路径01230ABABC1BABC2CD3DADABDABC(2)(1)(1)(1) 1 3 1 3 , 1 2 2 3 9,2 24DM i n DDDM i n(2)(1)(1)(1) , 2 2 Di jM i n Di j DiDj(2)( 1)( 1)( 1) 0 3 0 3 , 0 2 2 3 7,3 25DM i n DDDM i n7954ABCDBCDADBAD弗洛伊德算法演示弗洛伊德算法演示 data=xl
8、sread(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_j).2+(y_i-y_j).2).0.5*0.1; A(point_i,point_j)=d_ij; end for i=1:92 for j=1:92 if A(i
9、,j)=0 A(j,i)=A(i,j); end end end for t=1:8464 if A(t)=0 A(t)=inf; end end for 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 end end1 , 0ijf(1)0-1变量约束.为表示第i路口的平台是否管辖第j路口的0-1变量，即(2)每个路口都必须被管辖.要求每个路口由且仅由一个平台管辖,即(3)设置了平台的路口的约束.对于有平台的路口,应直接由该平台进行管辖,不应考虑其他情况,即1
10、201iijf1ijf(4)尽量3min内赶到事发地的约束.除了6个特殊点意外,其他的点都要满足3min内有交巡警赶到,即到交巡警服务平台的距离应小于等于3km,因此有(5)对于6个3min内不能到达的路口,应该由与其距离最近的路口的平台来管理,即3ijijdfiijijijddf)min(MODEL:SETS:NOTE/N1.N92/:N;PLATFORM/P1.P20/:G;LINK(PLATFORM,NOTE):DISTANCE,F;ENDSETSMIN=0.05*SUM(PLATFORM(K):SQRT(PLATFORM(I):G(K)-SUM(G(I);DATA:DISTANCE=O
11、LE(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)|J_3#EQ#28#EQ#29#EQ#38#EQ#39#EQ#61#EQ#92:F(I_3,
12、J_3)*DISTANCE(I_3,J_3)MIN(LINK(I_4,J_4):DISTANCE(I_4,J_4);END13条交通要道的封锁我的方案：（1）从20个平台中选择13个平台，使13个A区出入口都能在最快的时间完成封锁；（2）其余7个平台根据抵达时间和最小的原则，每个平台前往一个出入口。必须强调，我的方案是真正合理而符合实际必须强调，我的方案是真正合理而符合实际的！的！方案一：使最后一个完成封锁的路口时间最少。方案一的模型：1 ,0,.,2,1,1,.,2,1,1s.t.)max(min111iijijijliijnjijjxlkxnjxxsZ新增交巡警平台的布置问题（1）由于28
13、,29,38,39,61,92这6个路口没有平台能在3min内赶到，因此需要新增的平台能使得这6个路口可以有平台在3min内赶到。（2）在满足（1）的前提下，要使得工作量最大的平台工作量尽可能的小，工作量的分配尽可能的平衡。第一层目标函数：)max(min921jjijnf第二层目标函数：2241_)(241miniigg.92,2,1,24,2,1,1,3,1 ,0.241jiffdftsiijijijij多目标规划问题简单介绍引例引例1： 投资问题投资问题 某公司在一段时间内有某公司在一段时间内有a(亿元亿元)的资金可用的资金可用于建厂投资。若可供选择的项目记为于建厂投资。若可供选择的项目
14、记为1，2，.，m。而且一旦对第。而且一旦对第i个项目投资，就用个项目投资，就用去去ai亿元；而这段时间内可得收益亿元；而这段时间内可得收益ci亿元。问亿元。问如何如确定最佳的投资方案？如何如确定最佳的投资方案？ mixxaxaiimiii, 2 , 1, 011 01ix对第对第i个项目投资个项目投资不对第不对第i个项目投资个项目投资约束条件为：约束条件为：最佳的投资方案最佳的投资方案投资最少、收益最大投资最少、收益最大投资最少：投资最少：miiimxaxxxf1211),(min收益最大收益最大 miiimxcxxxf1212),(max双目标规划双目标规划引例引例2： 生产问题生产问题
15、某工厂生产两种产品，产品某工厂生产两种产品，产品A每单位利润每单位利润为为10元，而产品元，而产品B每单位利润为每单位利润为8元，产品元，产品A每每单位需单位需3小时装配时间而小时装配时间而B为为2小时，每周总装小时，每周总装配有效时间为配有效时间为120小时。工厂允许加班，但加小时。工厂允许加班，但加班生产出来的产品利润减去班生产出来的产品利润减去1元，根据最近的元，根据最近的合同，厂商每周最少得向用户提供两种产品各合同，厂商每周最少得向用户提供两种产品各30单位。要求单位。要求:1) 必须遵守合同；必须遵守合同；2)尽可能少尽可能少加班；加班；3)利润最大利润最大. 问怎样安排生产？问怎样
16、安排生产？ 0120233030314321ixxxxxxx约束条件为：约束条件为：加班最少加班最少4223minxx 利润最大利润最大432178910maxxxxx 每周正常时间生产得每周正常时间生产得A产品数量产品数量x1每周正常时间生产得每周正常时间生产得B产品数量产品数量x3每周加班时间生产得每周加班时间生产得A产品数量产品数量x2每周加班时间生产得每周加班时间生产得B产品数量产品数量x4多目标规划的模型多目标规划的模型一般形式一般形式: XfXfXfV-pRXn,min 21 .,.,2 , 1 0 ;1,2,., 0. lkXhmjXgtskj满足满足函数函数kjihgf,R:
17、RR, h: RR, g: Rfnknjni求目标函数的最大值或约束条件为大于等于求目标函数的最大值或约束条件为大于等于零的情况零的情况，都可通过取其相反数化为上述一都可通过取其相反数化为上述一般形式般形式2 p nkjRXXhXgXD , 0 , 0|定义定义1 把满足问题中约束条件的解把满足问题中约束条件的解XRn称为可行解称为可行解(或可行点或可行点)，所有可行点的集，所有可行点的集合称为可行集合称为可行集(或可行域或可行域)记为记为D即即:原问题可简记为原问题可简记为 XfXfXfV-pDX,min 21 定义定义2 x*是是绝对最优解绝对最优解fj(X)fj(x*), 任意任意XD,
18、 j=1 px*是是有效解有效解不存在不存在XD , 使得使得fj(X)fj(x*), j=1 px*是弱是弱有效解有效解 不存在不存在XD , 使得使得fj(X)fj(x*), j=1 p绝对最优解绝对最优解=有效解有效解有效解有效解=弱有效解弱有效解定义定义3 像集像集F(R)=F(x)|xD约束集约束集R在映在映像像F之下的值域之下的值域F*是是有效点有效点 不存在不存在FF(D), 使得使得FF*；F *是弱是弱有效点有效点 不存在不存在FF(R), 使得使得F0, 即即此目标值再差此目标值再差也是可接受也是可接受的的! 多目标规划的基本解法多目标规划的基本解法3. 功效系数法功效系数
19、法对不同类型的目标函数统一对不同类型的目标函数统一量纲，分别得到一个功效系数函数，然后求所量纲，分别得到一个功效系数函数，然后求所有功效系数乘积的最优解。有功效系数乘积的最优解。 XfXfXfV-pDX,min 21 XffXffjDXjjDXj maxminmaxmin1 , 0)()(minmaxmax jjjjjffXffXdpj, 2 , 1 pjjDXXd1)(max pjjDXXd1)(max或或线性型线性型功效系数法，还有其它类型的方法，功效系数法，还有其它类型的方法，如指数型方法如指数型方法多目标规划的基本解法多目标规划的基本解法4. 评价函数法评价函数法这是一种最常见的方法，
20、就这是一种最常见的方法，就是用一个评价函数来集中反映各不同目标的重是用一个评价函数来集中反映各不同目标的重要性等因素，并极小化此评价函数，得到问题要性等因素，并极小化此评价函数，得到问题的最优解。常见的以下几种方法：的最优解。常见的以下几种方法： XfXfXfV-pDX,min 21 XffjDXj min*pj, 2 , 1 pjjjpfXfffhXFh121*)(),()()(minXFhDX 原理：距理想点最近的点作为最优解原理：距理想点最近的点作为最优解!4.1 理想点法：理想点法：定义评价函数：定义评价函数：求解非线性规划问题：求解非线性规划问题： XfXfXfV-pDX,min 2
21、1 XffjDXj min0pj, 2 , 1 pjjjjfXfXFh120)()( )(minXFhDX 4.2 平方和加权法：平方和加权法：定义评价函数定义评价函数：求解非线性规划问题：求解非线性规划问题：先设定单目标规划的下界先设定单目标规划的下界(想象中的最好值想象中的最好值),即即其中其中j为为事先给定的一组权系数，满足：事先给定的一组权系数，满足：1;, 2 , 1, 01 pjjjpj 原理：平方和加权法体现了通常的原理：平方和加权法体现了通常的“自报公自报公议议”原则原则那些强调各自目标重要者预先那些强调各自目标重要者预先给出一个尽可能好的估计，然后给出一个尽可能好的估计，然后
22、“公议公议”给给出一组表明各目标性的权系数，最后求解非出一组表明各目标性的权系数，最后求解非线性规划给出解答。线性规划给出解答。 211200)()( pjjjjffXfXFh虚拟目标法虚拟目标法 多目标规划的基本解法多目标规划的基本解法 XfXfXfV-pDX,min 21 pjjjXfXFh1)()( )(minXFhDX 4.3 线性加权法：线性加权法：再定义评价函数：再定义评价函数：求解非线性规划问题：求解非线性规划问题：事先按目标函数事先按目标函数f1(X)、.、fp(X)的重要程度给出的重要程度给出一组权系数一组权系数j，满足：，满足：1;, 2 , 1, 01 pjjjpj )(
23、RF1f2f*2f*1f,21 ,21 多目标规划的基本解法多目标规划的基本解法 XfXfXfV-pDX,min 21 )(max)(1XfXFhjpj )(maxmin)(min1XfXFhjpjDXDX4.4 “min-max”法法(极小极大法极小极大法)定义评价函数：定义评价函数：求解非线性规划问题：求解非线性规划问题：xf)(1xf)(2xf )(),(max21xfxf*x原理：原理：在最不利的情况在最不利的情况下找出一个最有利的策下找出一个最有利的策略略!悲观主义决策悲观主义决策 多目标规划的基本解法多目标规划的基本解法 )(maxmin)(min1XfXFhjpjDXDX4.4
24、“min-max”法法(极小极大法极小极大法)(转化转化)此非线性规划问题目标函数不可微，不能直接此非线性规划问题目标函数不可微，不能直接用基于梯度的算法：用基于梯度的算法：但可方便转化为一个简单非线性规划问题但可方便转化为一个简单非线性规划问题！)(max1Xftjpj 令令则该规划问题可等价为：则该规划问题可等价为：1 2,min(), ,X tjtfXt jpXD 该技巧非常有用，将该技巧非常有用，将一个不可微的规划问题转一个不可微的规划问题转化为可微的约束规划！化为可微的约束规划！ 多目标规划的基本解法多目标规划的基本解法)()()(12XfXfXFh )()(max)(max12Xf
25、XfXFhDXDX 4.5 乘除法乘除法考虑两个目标的规划问题：考虑两个目标的规划问题：求解非线性规划问题求解非线性规划问题:则定义评价函数：则定义评价函数：max)(min)(21XfXfDXXfXf , 0)(0)(21，且且1f2f*2f*1f 最优解点最优解点 如如f1(x)为投资总金额，为投资总金额，而而f2(x)为投资后的总收益，为投资后的总收益，则最优结果应是单位投资则最优结果应是单位投资的总收入最大！的总收入最大！ 多目标规划的基本解法多目标规划的基本解法理论性结果理论性结果以上所有方法所得到的最优解都是以上所有方法所得到的最优解都是有效有效解解(线性加权法当有权系数为零时得到
26、的是弱线性加权法当有权系数为零时得到的是弱有效解有效解)!新增交巡警平台的布置问题模型的求解：利用lingo求解第一层规划，得到结果为：然后将这个结果作为约束，代入第二层规划模型中。5 . 8)max(min921jjijnf全市交巡警平台设置方案对全市现有交巡警服务平台设置合理性评价对全市现有交巡警服务平台设置合理性评价:(1)服务平台警力大部分集中在A区,警力充足,而D区F区的警力明显不足;(2)C区和F区平均每个平台处理的案件数目较多,服务平台的工作强度较大;(3)D区交巡警服务平台管辖面积大,人口多,而平台数却相对较少;(4)除了A区各平台3min内无法到达的路口较少外,其他各区这样的
27、路口都比较多,会造成这些地区到某些路口的出警时间过长,无法满足迅速到达案发地点的要求.(1)需要对各区的人口数和面积进行加权平均,得到警力分配的指标;(2)将分配的指标转化为比例,确定各区警力的数量;(3)在确定了各区警力数量的基础上,对各区平台进行优化分配,确定最终方案.而对各区警力分配方案的确定可以参考上几问.全市交巡警平台设置方案全市范围最佳围堵方案假设:1.嫌犯的踪迹在案发后不可追踪,即3分钟内嫌犯可以跑到路程范围内允许的一切地方,而警方对此没有具体信息.2.嫌犯充分狡猾,如果有任意一条逃离市区的线路没有在合适的时间被封锁,抓捕工作都会失败.3.嫌犯的车速可快可慢,可掉头、转弯，但最大
28、车速固定，记作v. 4.抓捕工作分两步完成:首先建立包围圈,若无法建立这样一个包围圈,则抓捕工作失败;其次,在包围圈内搜索嫌犯,基本前提是不能放跑嫌犯,目标为在尽量短的时间内抓获嫌犯,若效率相当,则使用警力越少越好.全市范围最佳围堵方案全市范围最佳围堵方案 两个定义: 定义1:若点j属于点集S,且其所有邻点均属于S,则称点j为集合S的内点；反之，称其为S的边界点。将内点集记作 ，边界点集记作 . ， . 定义2:若点 ,将j的所有邻点加入S称为对j的一次增广.1V2V21VVS21VVSVj2全市范围最佳围堵方案 如果我们能够找到一个点集S,包含嫌疑犯的出发点,且集合S的所有边界点警察都能赶在
29、嫌犯之前到达,则围堵成功;否则围堵失败.我们希望在最小的地理范围内进行围堵.全市范围最佳围堵方案1S0S10SS 步骤1将嫌犯在案发3分钟内可能到达过的顶点(在路上不算)集定义为初始集,记作 ;步骤2将 的所有边界点一起增广,新得到的点集记作 .显然步骤3若不能再目前的点围堵成功,则选择其中一个边界点进行增广,在进行评判.在边界点的选择上,我们采用贪婪算法,选择嫌疑犯到达时间和最近平台到达时间差最大的边界点,基本想法是增广最难包围的边界点.0S全市范围最佳围堵方案判断是否可以包围的算法:步骤1:从源道所有平台连一条流量上限为1的 边;步骤2:从所有边界点向汇集点连一条流量上限为1的边;步骤3:若平台i到边界点j的时间 ,则从平台i向边界点j连一条流量上限为1的边;步骤4:计算给定包络集下模型的最大流量;步骤5:若流量等于边界点数,围堵成功. 搜捕模型,太复杂了,我现场演示吧!
