交巡警服务平台的设置与调度问题(论文).pdf

交巡警服务平台的设置与调度问题摘要本文针对交巡警服务平台的设置及调度问题，基于平台设置的原则和任务，建立数学模型研究了服务平台管辖范围分配、警力资源调度以及合理设置平台个 数、位置等实际问题。针对问题一的第一问，我们建立了平台管辖范围分配模型，给出了 A区20 个服务平台的最优管辖范围分配方案。考虑到“尽量到达时间不超过3分钟”的 快速出警原则以及硬约束下无可行解的情况，我们利用基于损失时间的罚函数法 对“到达时间超出3分钟”的点进行“惩罚”。最终建立以全区各平台到达所管 辖节点最短时间之和最小为目标函数的平台管辖范围分配模型，并利用dijkstra 算法计算图中任意两个节点的最短距离，进行模型求解。针对问题一的第二问，我们建立了交通要道封锁警力调度模型，给出了封锁 13个交通要道的警力调度方案。该模型以整个封锁过程所用最长时间最短为目 标函数，解决从20个服务平台中选出13个平台完成封锁道路的指派问题。针对问题一的第三问，我们建立平台工作的均衡优化模型，对平台出警次数、出警时间等指标进行定量分析，给出了增设平台个数及其位置的方案。我们建立 以各平台出警次数及出警时间差异最小为目标函数的优化模型，利用局部最优逼 近全局最优的搜索算法，不断削减不均衡点峰值的思想达到系统的整体均衡，通 过模型求解最终给出了分别增加平台时的分配方案。针对问题二的第一问，我们基于城区系统间比较指标建立了平台设置的评价 模型，并对现有平台设置不合理之处给出了解决方案。首先，我们利用平台管辖 范围分配模型对全市6个区的平台划分管辖范围，利用警民比例、平台办案率、平均出警时间等指标建立平台设置合理性的综合评价函数，针对现有平台设置方 案不合理之处，我们又建立平台设置优化模型，通过增减每个区的平台数量最终 找到最优平台设置方案。针对问题二的第二问，我们建立了最佳围堵模型，给出了围堵成功率最大时 的警力调度方案。针对围堵逃窜嫌疑犯问题我们进行了合理假设，并富有创新性 地使用动态圆圈搜索的方法确定最大围堵成功率，给出在该围堵成功率下的警力 资源调度方案。最后，我们对上述模型进行了优缺点分析，并提出了改进方向。关键词 Dijkstra算法综合评价多目标规划动态圆圈搜索法1一、问题重述1.1 问题背景警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有 效地贯彻实施这些职能，既保证警务资源的合理利用，又能及时有效解决人民群 众的危机困难，许多城市都在城区的交通要道和重要部位设置交巡警服务平台。交巡警服务平台有接受公民报警，维持警区内的日常治安秩序，警戒突发性治安 事件现场等多种职责。1.2 需要解决的问题就某市设置交巡警服务平台的相关情况，建立数学模型进行合理设置交巡警 服务平台、分配各平台的管辖范围、调度警务资源等实际问题的分析。（1）分配A区的各交巡警服务平台的管辖范围：现已知A区的交通网络以 及20个交巡警服务平台的节点位置，要求为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发 地。（2）给出A区突发情况下封锁道路的交巡警服务平台警力调度方案：考虑 应对重大突发事件的情况，需要调度全区20个交巡警服务平台的警力资源，对 进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一 个路口，要求给出该区交巡警服务平台警力合理的调度方案。（3）A区交巡警服务平台的再调整：根据现有交巡警服务平台的工作量不 均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，要 求确定需要增加平台的具体个数和位置。（4）评价全市的交巡警服务平台设置方案并改进：针对全市（主城六区A,B,C,D,E,F）的具体情况，按照设置交巡警服务平台的原则和任务，分析 研究该市现有交巡警服务平台设置方案的合理性。对于明显不合理之处给出解决 方案。（5）调度全市交巡警服务平台警力资源的最佳围堵方案：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑 2人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的 最佳围堵方案。二、模型假设1、每个交巡警服务平台的职能和警力配备基本相同且警务资源有限。2、警车的时速为常值60km/h。3、在应对重大突发事件时，一个服务平台的警力最多封锁一个路口。4、主城六区A,B,C,D,E,F分别用序号16表示。5、交巡警服务平台下简称平台，路口节点下简称节点。6、计算出警时间时仅考虑到达时间（从平台接到报案时间算起，巡警赶到 事故现场终止），认为平台进行日常巡查的警力和时间为常数，不予考虑。7、接到报案后警车沿最短路径从平台到达事故发生地。8、犯罪嫌疑人驾车逃逸速度与警车速度相同，为60km/h。3三、符号说明i,j 路口节点标号，i=l,2,.,92 j=1,2,.,92km 第k区的机号平台，机的取值依赖于,k=1,2,.,64j，号节点与，号节点间的直线距离，i=l,2,.,92 j=l,2,.,92 irjPu i号节点与/号节点间是否有通路，i=l,2,.,92 J=1,2,.,92 i手jM，号节点是否有人报警，J=l,2,.,92Mkmj加号平台到j号节点的最短距离，尸1,2,92tkmj 而号平台到，号节点的最短时间，J=l,2,.,92v 每辆警车的时速，v=60km/hfkinj 碗号平台到，号节点的损失时间的惩罚函数，J=l,2,.,92卬骁 km号平台是否封锁i号路口，tkmi km号平台到j号节点的最短时间mkmi km号平台到j号节点的最短距离W；，号节点是否设置平台，J=l,2,.,92q j号节点平均发案次数（发案率），2,.,92Nkm 的2平台的出警次数Tkm 的/平台的出警时间Pk 化区的警民比例，2=1,2,.,6pek k区的人口总数，4=1,2,6xk 左区的新增平台数，&eZ,当 0时表示增加平台，当&0表示减少平台，4=1,2,.,64四、问题分析1.1 问题分析交巡警服务平台系统中的平台设置个数、覆盖管辖范围、重大突发事件的应 急能力、警务资源利用情况等都会影响整个交巡警服务平台系统的使用效率，因 此，只有合理配置交巡警服务平台系统的相关指标，才能达到服务效率、警力资 源利用效率的最优化。1.2 平台管辖范围分配模型交巡警服务平台负责其管辖区域内的日常治安管理，要随时接受“110”报 警电话，快速反应，及时出警尽量于3分钟内赶赴事故发生现场进行处理，这是 服务平台的基本职能。如何将A城区进行合理划分，将其分配给每个平台进行管 辖以保证平台日常工作基本职能实现的最优化是我们要考虑的问题。对于路段及路口节点的归属问题，我们给出合理假设，路段。（，,/）（f的管辖权归于管辖节点i的服务平台。对于事故发生地的界定为当i节点和j节点确定的路段。a,/）上发生事故时，认为事故发生地在节点，即将事故的发生地 统一于路口节点。因此，我们只需讨论各个路口节点归哪个服务平台管辖即可将 整个区进行管辖范围划分。基于对题目的初步分析，我们认为若将到达时间（从平台接到报案时间算起,巡警赶到事故现场终止）硬性规定在3分钟内，会由于个别节点到周围任意平台 的最短时间均超过3分钟，无法满足要求而造成模型的无解，也基于对于题目中“尽量”二字的理解，故我们放宽要求，利用罚函数法求解该模型，建立增广目 标函数，由损失时间约束函数构造出“惩罚”项，对“到达时间超出3分钟”的 点进行“惩罚”。基于以上分析建立平台管辖范围分配模型，以全区各平台到达所管辖节点最 短时间之和最小为目标函数，以，节点是否为加平台管辖的0-1变量为决策变量,考虑损失时间判罚、到达时间限制、平台管辖限制等约束条件，利用dijkstra算 法计算图中任意两个节点的最短距离，进行模型求解。最终给出了基于A城区现 有交通网络和20个服务平台下的最优平台管辖范围的分配方案。1.3 交通要道封锁警力调度模型重大突发事件发生时，需要调度全区20个交巡警服务平台的警力资源，对 进出该区的13条交通要道出入口实现快速全封锁。全区的交通网络、20个平台 的节点位置以及13条交通要道的出入口位置节点均为已知，我们只需判断出如 何在20个平台中选出13个平台令其出警，使得在最短的时间内完成13条交通 要道出入口的全封锁。基于以上分析建立交通要道封锁警力调度模型，以13条交通要道出入口的 全部封锁完成时间最小为目标函数，节点是否属于需要封锁的交通要道出入口 5的0-1变量为决策变量，以需要封锁的路口数、每个出入口只能由一个平台的警 力封锁、每个平台的警力只能封锁一个出入口等要求为约束条件。通过模型求解,给出重大突发情况下的交通要道封锁警力调度方案。1.4 平台工作的均衡优化模型在现有的交巡警服务平台的设置中，平台工作量（平均每天出警次数）不均 衡及部分平台出警时间过长的问题显著。考虑平台工作量差异度和平台出警时间 差异度两个指标建立以平台间工作量和出警时间差异度最小为目标函数的平台 工作的均衡优化模型，考虑该模型计算量过大，不易求解，故利用局部最优逼近 全局最优的搜索算法来求解此模型。该算法的实现思想是通过求解小系统的最优近似逼近总体系统的最优。我们 将A区20个平台按照其管辖范围的界定分成20个较为独立的小系统进行考虑,在每个小系统内部采用削减峰值的方法确定需要优化的小系统的优先权，然后建 立新的优化模型确定系统中添置新服务平台的位置，使得该系统的工作量和出警 时间趋于均衡。最终通过对每个小系统的优化逼近整个A区所有平台工作量均衡 的优化。需要说明的是，在对新增一个服务平台所耗资源信息缺失的情况下，我们给 出了分别增加2至5个平台的4种情况下的增加平台个数和位置的方案，并给出 了如何确定新增平台个数的简单分析。1.5 平台设置的评价模型及其优化方案我们需要考虑的问题是综合考虑全市6个区（主城六区A,B,C,2及尸）的 服务平台设置情况，根据设置交巡警服务平台的原则和任务，对设置交巡警平台 合理性进行定量评价，改进现有分配方案。首先，我们给出了交巡警服务平台 设置的具体原则和任务，并根据该原则和任务建立了城区系统间比较指标（警民 比例、平台办案率、平均出警时间），我们建立目标函数为指标差异度最小的平 台设置优化模型，考虑仅有城区系统间指标才能有效降低全市总体的平台工作的 不均衡度，故选取警民比例、平台办案率、平均出警时间三个指标方差和最小作 为目标函数，主要考虑服务平台的工作均衡原则。我们针对方案一（增减部分服 务平台数量）建立平台设置优化模型，主要基于快速出警原则及平台工作均衡原 则使得全市系统的平台设置合理性提高。最终，我们给出了全市6个区的服务平台增减情况以及具体增减平台的节点 位置，通过图像直观分析与模型结果对比，验证了我们建立的平台设置优化模型 的合理性。1.6 最优围堵模型本题讨论的问题是在嫌疑犯逃逸3分钟后，如何合理调度安排交巡警服务平 台的警力资源进行围堵，给出围堵方案，在缉捕嫌疑犯的成功率达到最大。6我们假设嫌疑犯犯案后从尸点以速度60z/2随机向四周逃窜，在一段时间（3分钟）内嫌疑犯的逃窜路径我们未知嫌疑犯在1时间经过路线总长度记为考虑极端情况，嫌疑犯从p点出发后沿着一条直线路径逃逸，/时刻时经过 的距离为厂，以一为半径、p点为圆心画圆，可知无论嫌疑犯选择哪条逃逸 路径，其现在所处位置必位于该圆覆盖的区域内。将该区域内的所有节点统计出 来，个数记为加，认为这些节点为嫌疑犯1时刻可能到达的节点。把能够在Ct-3）分钟内赶到这些节点进行围堵的平台数记为八Cn（t）m（t）,用越小，越大，围堵嫌疑犯的成功率就越高，故我们选取函数M/）=&刻画围 m（r）堵嫌疑犯的成功率。本题利用圆圈搜索法进行模型求解，即随着时刻的变化动态地画圆覆盖嫌疑 犯可能到达的区域范围，令时刻按照较短的步长增长，不断计算相应的警方围堵 成功率，在搜索较多的点后，可找到最大的警方围堵成功率，也可得到最佳围堵 嫌疑犯的方案。5.1平台管辖范围分配模型（第一问：问题1）5.1 数据分析 图像数据处理我们根据题目附件中给出的交通路口路线、交通路口节点、全区交巡警服务 平台设置位置等数据，利用MATLAB软件对题目信息进行了初步处理，得到了 A区的交通网络与平台设置示意图（见附录1）,这里给出截图（见图1）。7图1 A区的交通网络与平台设置示意图(部分截图)Dijkstra算法计算两点最短路径长度Dijkstra算法山用来求两点之间的最短距离，并给出最短路径的算法。记某 图G中两点之间的最短距离为,其基本思想是按距为从近到远为 顺序，依次求得从到的各顶点的最短路和距离，直至%算法结束。为避免重复 并保留每一步的计算信息，采用了标号算法。下面是该算法。Step 1 令/(o)=O,对vWMo，令/=8,So=4),)=0Step 2 对每个 vSj(S,=VSJ,用 min/(v),/()+()代替/(v)。计算 min/(v),把达到这个最小值的一个顶点记为生+1，令号讨=5/.+1)。Step 3若，=1卜1,则停止；若1卜卜1,则用i+1代替i,转Step2。算法结束时，从外到各顶点丫的距离由丫的最后一次的标号/(v)给出。在丫进 入S,之前的标号/)叫T标号，v进入。时的标号/)叫P标号。算法就是不断 修改各顶点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获 得P标号所由来的边在图上标明，则算法结束时，为至各项点的最短路也在图 上标示出来了。交巡警在处理案件时要遵循“快速出警原则”，即接警后迅速到达现场，我 们认为出警时沿最短路径到达事故发生地，因此需要利用Dijkstra算法计算出交 通网络图中任意两点间的最短距离。85.2模型准备交巡警服务平台在接到报案电话后，应尽量在3分钟内派出警力赶赴事故发 生现场，在满足该条件的情况下，如何合理分配A区每个平台的管辖范围是我 们考虑的主要问题。两个个概念的说明(1)到达时间：从平台接到报案起，巡警沿最短路径赶到事故现场终止所花费 的时间。(2)损失时间：当到达时间不大于3分钟时，损失时间为0；当到达时间大于3 分钟时，损失时间二到达时间-3。即口小旺W，到达时间不超过3分钟损失时间=C,tb.-3,otherwise其中，K表示A区机号平台到j号节点的最短时间，；=1,2,.,92 管辖范围和事故发生地的界定A区的交通网络由路口节点与连通节点的各个路段组成，在管辖范围的划分 时我们必须考虑节点、路段如何归属的问题。我们定义路段Q(i,j)(ij)是由节点i和节点/连通而成的路段，路段中间不存在节点。考虑事故发生地的界定，当事故发生在路口节点，时，我们认为事故发生地 即为节点i；当事故发生在路段Q(i,j)(ij)时，考虑路段长度一般较小，简 化处理，认为事故发生地为节点儿这样即把事故的发生地统一于路口节点。考虑节点、路段的归属范围，当平台机管辖节点，时，我们认为平台机管辖 路段。(i,j)(i3000m),故无论如何分配，管辖节点28的平台到达 该节点的时间都大于3分钟，不满足要求。因此，我们利用罚函数法求解该模型(该模型实际上为带约束的非线形规 划问题)，其思想是：利用问题的原目标函数和损失时间约束函数构造出增广目 9标函数，把该问题转化为不考虑损失时间约束的非线形规划问题来求解。增广目标函数由两个部分构成，一部分是原目标函数，另一部分是由损失时 间约束函数构造出的“惩罚”项，“惩罚”项的作用是对“到达时间超出3分钟”的点进行“惩罚”。我们采用外部罚函数法，这种方法的迭代点一般在可行域的 外部移动，随着迭代次数的增加，“惩罚”的力度也越来越大，从而迫使迭代点 向可行域靠近。我们设法加大不可行点处对应的目标函数值，使不可行点不能成为非线性约 束问题的最优解，于是对于可行域基于损失时间作一惩罚函数，如下：_ 10,3),4句 3 minK3minm=1,2,.,20 j=1,2,.,92其中，%,表示A区机号平台到j号节点的最短时间，；=1,2,.,92如果损失时间大于0,则以10倍的损失时间10”加广3）作为“惩罚”项对“到 达时间超出3分钟”的点进行“惩罚”；如果损失时间为0,则说明到达时间不 超出3分钟，不予惩罚。5.3模型建立1、决策变量题目中关键是确定路口节点的分配方案，即节点j是否属于加服务平台管 辖，服务平台编号如表示第七区的第加个服务平台，出=1,2,.,6分别代表6个城区，故模型的决策变量为1,j号路口节点由1加号平台管辖叱=彳.，机=1,2,.,200,otherwise2、增广目标函数题目要求当服务平台管辖的范围内出现突发事件时，交巡警尽量能在3分钟 内到达事发地。从全区的服务平台服务情况考虑，取所有平台到各个节点的总时 间最小为目标函数，同时考虑损失时间约束函数构造出增广目标函数，利用外部 罚函数法对“到达时间超出3分钟”的点进行“惩罚”。增广目标函数如下：20 92 20 92向11 乞2嫉+22工回m=j=l m=j=l其中，（l）九可表示bn号平台到j号节点的最短时间，J=1,2,.,92 m=l,2，,20（2）/啊.表示1加号平台到，号节点的损失时间的惩罚函数，j=l,2,.,92m=1,2,.,203、约束条件10服务平台数量限制A区的交巡警服务平台共20个，约束如下：92Z%叼=2 m=1,2,.,20 J=l,2,.,92i 事故管辖权归属限制我们认为一起事故仅由管辖该事故发生地的服务平台负责解决，即每一个路 口节点仅有一个服务平台管辖，约束如下：20吗切=1 机=L2,.,20 j=l,2,.,92m=事故发生地到达时间限制此为该问题的关键限制条件。事故发生后，管辖该路口节点的服务平台尽量 在3分钟内派出交巡警到达现场。根据前面对此限制条件的分析，我们利用罚函 数法将此约束放到目标函数中，罚函数如下：嫉=1 2。7=1，2,.,92Zb.3 minm=1,2,.,20 j=1,2,.,92其中，（1）a.表示，号节点是否有人报警，7=1,2,.,92（2）M的表示1加号平台到j号节点的最短距离，j=l,2,.,92（3）v表示每辆警车的时速，v=60km/h 综上所述，我们给出平台管辖范围分配模型，如下:11min20 92 20 92m=j=l m=j=J。，3min加=1,2,.,20 j=1,2,.,925.4模型求解对上述模型利用ling o软件求解（代码见附录3）,其中可表示加号平台到j号节点的最短距离，j=l,2,.,92,可由dijskstra算法得到（见附录2）。最终计算结果数据及平台管辖范围方案（见表1），下给出分配方案的示意图（图 2）o12400图2 A区平台管辖范围分配方案表1各平台的管辖范围分配平台 编号所管辖节点编号11,67,68,69,71,73,74,75,76,7822,39,40,43,44,70,7233,54,55,65,6644,57,60,62,63,6455,49,50,51,52,53,56,58,596677,30,32,47,4888,3399,31,34,35,4510101111,26,271212,251313,21,22,23,2414141515,28,291616,36,37,381717,41,421818,80,81,82,831919,772020,84,85,86,87,88,89,90,91,92六、交通要道封锁警力调度模型（第一问：问题2）136.1模型分析本题考虑交巡警服务平台应对重大突发事件时的应急能力O如何在紧急情况下调度全区20个交巡警服务平台的警力资源，使得封锁完全部13条交通要道 出入口的时间最少。我们认为只要封锁交通要道出入口即封锁了该交通要道。根据假设，每 个平台的警力资源最多封锁一个交通要道出入口，出于警务资源的利用有效性的 考虑，每个交通要道出入口仅需要一个平台的警力资源进行封锁，故此问题的木 质是在全区20个服务平台中选出13个平台出警完成封锁道路的指派问题，且保 证完成整个封锁过程所用最长时间最短。6.2模型建立1、决策变量此问题研究的是如何选出13个服务平台完成封锁13个交通要道出入口的指 派问题，故选取0-1变量作为决策变量，如下：口 1,i节点属于需要封锁的交通要道出入口.4w.=,州。%，相=12.,92 j=l7T二噩吐噩 T其中，（1）乂机表示1加平台的出警次数（2）九表示加平台的出警时间（3）河表示所有平台的出警次数的平均值（4）了表示所有平台的出警时间的平均值（5）NN表示平台工作量差异度，7T表示平台出警时间差异度算得在现有的交巡警服务平台的设置下，平台工作量差异度为1.67,平台出 警时间差异度为2.3,差异度越大，表明不均衡程度越大，可看出平台间的工作 量和出警时间都呈现出较大的不均衡，限于部分服务平台仅负责其所在节点的事 故处理，导致其出警时间始终为0,这是造成出警时间差异度大的较为重要的原 因。由于出警到达时间尽量不超过3分钟是服务平台工作的大前提，故这些点的 工作量和出警时间很难得到优化，将其作为特殊点不予考虑，对其他平台相关指 标进行优化即可。建模思路为了减少平台工作量的差异性，保持出警时间在各个平台间的均衡性，在A 18区原有服务平台位置不变的情况下，增加25个服务平台，添加平台的个数不 定，平台的设置位置不定。此题目是在平台管辖范围分配模型的基础上，增添了 平台间工作量和出警时间均衡的约束条件，建立平台工作的均衡优化模型，以平 台间工作量和出警时间差异度最小为目标，求解增加平台的个数及相应位置。特 别地，对于部分只管辖其所在节点的服务平台考虑到尽量3分钟到达时间的限 定，无法令其改变现在的管辖状况，故最后考虑增设平台时不考虑这些特殊点。7.2模型建立1、决策变量本题目关键考虑增加平台的具体个数（2-5个之间）及其相应位置，使得平 台间工作量和出警时间均衡度达到最优，故0-1变量/节点处是否设置服务平台 一旦确定，增添平台的方案即确定。故决策变量如下：W，j节点处设置服务平台.I,otherwise，E，2,，922、目标函数为了刻画平台工作量以及出警时间是否均衡，我们建立了平台工作量差 异度NN及平台出警时间差异度TT两个指标，差异度越小平台间的工作越均衡,根据分析主观确定了两个指标的重要性权重，分别为勺和&2,目标函数为两个指 标的加权求和最小，如下：min k NN+k2-TT其中，NN表示平台工作量差异度，7T表示平台出警时间差异度，尤和上2分 别为两个指标的重要性权重。3、约束条件 增设服务平台数量限制前20个平台的设置位置不变，考虑在标号为21-92的节点中选出2-5个节 点增设平台，约束如下：92 2W；1ma x（N.）-min（N.）NN 二必一92、1 机-92、.-N92几m=1,2,92j=ima x（加）-min（7m）TT-1区92 仁长92一 N其中，（1）表示1加平台的出警次数（2）几表示1加平台的出警时间（3）q表示j号节点平均发案次数（发案率），；=1,2,.,92（4）4句表示加号平台到j号节点的最短时间，j=l,2,.,92（5）后表示所有平台的出警次数的平均值（6）了表示所有平台的出警时间的平均值（7）AW表示平台工作量差异度，TT表示平台出警时间差异度20综上所述，建立平台工作的均衡优化模型，如下：min kx-NN+k2-TT 927=21叼=2092 92 皿=92 m=l j=922卬二必旬=1，厂,92 m=lSf.Wj 加=1，2,.,92j=l92Tlm=机=1,2,，92j=ima x（Nim）-min（Nlm）NN V92 1V，”M92.Nma xg”J-min（Tim）YY 二 臼-92 许 1V，V92 、-N其中，叼为o-i决策变量，叼=，汴点处设置服务平台，j 0,otherwise（2）乂机表示加平台的出警次数（3）几表示加平台的出警时间（4）q表示/号节点平均发案次数（发案率），尸1,2,.,92（5）表示加号平台到/号节点的最短时间，j=l,2,.,92（6）至表示所有平台的出警次数的平均值（7）表示所有平台的出警时间的平均值（8）NN表示平台工作量差异度，7T表示平台出警时间差异度（9）叱.表示号平台是否封锁，号路口，m=l,2,.,927.3模型求解21我们建立的模型基于全区20个交巡警服务平台考虑，增设平台的原则是使 得平台间的工作量差异度和出警时间差异度加权求和的值（平台工作差异度）进 行最小化，也就是达到平台工作分配的最优均衡。根据我们建立的模型，每增设一个服务平台，就可能使得周围临近平台的管 辖范围发生变动，需要在兼顾“尽量3分钟到达事故现场”的原则下重新全局考 虑平台工作差异度最小，这样的算法虽然理论上可行，但存在数据量过大、程序 运行时间过长、不易求解等缺点。同时，我们认为直接为工作量较大、出警时间 较长的平台管辖区域增设新的服务平台，同样可以有效解决平台与平台间工作 量、出警时间不均衡的问题，且这样的优化方案下不增设服务平台的区域无需进 行管辖范围的调整，在实际生活中更加方便可行。故我们利用局部最优逼近全局 最优的搜索算法来求解此模型。1、局部最优逼近全局最优的搜索算法该算法的主要思想是：将全区根据现有平台管辖范围划分为20个独立的小 区域，每个小范围中的一个服务平台及若干个由该平台管辖的路口节点组成一个 小系统，系统标号与服务平台标号一致，小系统间相互独立。每个系统都有自己 的平均出警时间和平均工作量指标，我们通过不断优化小系统的指标来完成整个 区域大系统的优化。若某个小系统的两个指标与该指标的总体均值差异较大，则说明该系统在加 大整体系统差异度中贡献较大，也就是说，采用降低该系统差异度能够有效地降 低整体系统的差异度指标。我们考虑造成小系统两个指标（每天平均出警时间、每天平均工作量）与相 应指标均值差异大的原因有两个：其一为该指标的值与指标的均值相比过小，表 示该系统的平台警力资源闲置情况较为严重；其二为该指标的值与指标的均值相 比过大，即该系统的平台警力资源过度使用，具体表现为工作量过多或出警时间 过长。优化两个指标可通过以下两种方法进行：（1）填补谷值，即加大系统平台管辖范围，使得系统闲置资源充分利用。（2）削减峰值，添置服务平台分担原系统平台的工作量。考虑到题目要求,在现有服务平台设置地点不变情况下增设2-5个服务平台，若采用填补谷值的方法，需要改变每个小系统原有的管辖范围，使得问题再次转 变为全局问题，违背了我们局部优化逼近全局优化的思想，同时在计算上较为繁 杂，故我们不采用该方法。若采用削减峰值的方法，即找出指标严重偏离均值的 小系统，在该系统中添置新的服务平台，在保证系统总工作量基本不变的前提下 分担原有服务平台的工作量，使得该系统的工作量和出警时间趋于均衡，具有可 行性。下面我们只需找出指标严重偏离均值的小系统，为其添设平台，降低该系 统的两个指标值，从而降低整个系统的差异度，优化平台乍的均衡度。2、新增平台的分配方案在该题目中，我们已经分析了现有20个服务平台平均每天的出警时间和出 警次数，将其与平台间的平均值进行比较（见图5、6）o由图5可知，平台的每 天平均出警时间严重超出平均值的共有7个平台，按其超出程度严重性对平台编 22号由高到低排序：20、5、15、2、1、7、4o同样，由图6可知，平台每天工作 量严重超出平均值的共有7个平台，按其超出程度严重性对平台编号由高到低排 序：20、1、2、5、7、13、90每天平均工作量 平台间工作量均值14-1-1210-tttttlrn lintnin1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20图6平台平均每天工作量与均值的比较综合以上两个指标的考虑，我们仍按照前面的分析认为平台的出警时间在很 大程度上受工作量（出警次数）的影响，故优先考虑对平台工作量指标进行削减 峰值的处理。每个小系统最多添设一个服务平台，否则会造成该系统平台的警力 资源闲置的情况发生。基于以上考虑，我们给出分别添设2-5个平台的情况下新 增平台的分配方案（见表3）。表3新增平台的分配方案增加平台数量需要增加平台的系统标号220、1320、1、2420、1、2、5520、1、2、5、7233、新增平台系统内位置确定及工作量分配方案上述分析中我们考虑平台平均每天工作量与该指标平均水平的偏差情况，偏 差越大即认为该系统分得新增平台的优先级越高。下面我们具体讨论在已知某系 统需要新增一个服务平台的情况下，如何确定该平台在系统中的节点位置。我们在每一个小系统（下考虑的是有两个服务平台，若干个路口节点组成的 小系统）中，应使得两个平台的工作量尽量接近，即两个平台工作量差值的绝对 值尽量小。建立简单的优化模型确定系统内新增平台位置及工作量的分配。决策变量由于我们需要确定新增的平台在小系统中的位置，并为系统中的两个平台划 分管辖范围，从而算出系统中两个平台的工作量、出警时间等数据，故取0-1变量叱，和0-1变量均为决策变量，如下：fl,在，节点设置服务平台0,otherwiseuz fl,j节点归i平台管辖典二0,otherwise 目标函数小系统平台工作均衡度的优化主要体现在两个平台的工作量差值的绝对值 尽量小，故选取如下目标函数：minn.n ij I 其中，”为，平台的出警次数。约束条件（1）系统中节点数量限制，设该系统共包含e个节点，约束如下：ZZ 叫一 i J（2）系统内平台数量限制，一个系统中仅有两个节点处设置平台，约束如下:叱=2i（2）每个节点由一个平台管辖，约束如下：i（2）每个平台最多管辖（域+1）个节点，约束如下：-%（申+1）叫j 2（2）每个平台最少管辖1个节点，约束如下：叱/叱j24（5）每个平台管辖自己所在位置的节点，约束如下:%=（）%=叱 i=j（6），平台出警次数的表达式%叱J其中，（1）J.表示j节点的发案率（2）表示，平台的出警次数。综上所述，给出系统内新增平台位置及工作量的分配模型min 4-nA四 I z fl,在，节点设置服务平台Wi=0,otherwiseuz fl,j节点归i平台管辖%=10,otherwisei jZ叱=2泛叱%=1 i2%/叱1印加左=1,2,.,6jNkfNkm k=1,2,.,6叫m其中，（1）4表示女城区的平台数量（2）表示如平台的平均每天出警次数，=1,2,6（3）乂表示左城区平均每个平台每天出警次数，七=1,2,.,6城区平台办案率城区平台办案率指的是某城区内所有平台办案数量之和与该区内平台总数 的比值，它反映了该城区平台的平均办案效率。该指标越大，表示该城区每个平 台分配的工作量越大。城区平台办案率的计算公式如下：k=1,2,.,6nnk其中，（1）J表示j节点的发案率（2）表示区的平台总数，k=l,2,.,6（3）为表示左区的城区平台的平均办案效率，女=1,2,.,628城区平台平均出警时间城区平台平均出警时间指的是某城区内所有平台出警时间之和与该区内平 台总数的比值，它反映了该城区平台的平均出警时间。该指标越大，表示该城区 每个平台分配的工作量越大。城区平台平均出警时间的计算公式如下：几bk=-k=1,2,.,6J其中，(1)C/表示j节点的发案率(2)如表示区的平台总数，=1,2,.,6(3)4表示区的城区平台的平均出警时间，笈=1,2,6警民比例警民比例指的是每个城区内的平台总数与该区人口总数的比值，即人均平台 拥有数。该指标数值越大，说明每个人可享受的平台服务越多，体现了方便群众 的原则。警民比例的计算公式如下：pk =1,2,.,6夕,其中，(1).表示区的警民比例,k=(2)夕,表示女区的人口总数，k=l,2,.,6(3)即&表示区的平台总数，k=l,2,.,6基于上述分析，我们根据设置交巡警服务平台所遵循的原则和任务，已经建 立了城区平台出警次数差异度、城区平台出警时间差异度、警民比例、城区平台 平均办案率、城区平台平均出警时间等5个衡量平台设置是否合理的指标,其中，在平台的管辖范围分配时已考虑了快速出警原则及方便群众的原则，而城区平台 出警次数差异度、城区平台出警时间差异度衡量了城区内部系统平台工作分配是 否均衡。同时我们计算平台办案率及平台出警时间时均考虑了管辖节点的发案29率，兼顾了安全性原则。我们考虑将指标划分为城区系统内部指标以及城区系统 间比较指标两种：(1)城区系统内部指标：出警次数差异度、出警时间差异度(2)城区系统间比较指标：警民比例、平台办案率、平均出警时间经计算得到全市6个城区的上述指标值及相关数据(见表4,图7)。表4全市6个区相关指标值城区ABCDEF出警次数 差异度0.190.080.010.070.010.15出警时间 差异度0.300.010.120.750.020.18平台总数20.008.0017.009.0015.0011.00人口总数60.0021.0049.0073.0076.0053.00面积22.00103.00221.00383.00432.00274.00警民比例0.330.380.350.120.200.21平台办案 率6.238.3111.017.537.969.98平均出警 时间10.3236.9942.3128.9434.5048.19图7(1)城区系统内部指标30T一平台总数一-警民比例*平台办案率平均出警时间图7(2)城区系统间比较指标由图中数据可知，D区内部系统平台出警时间差异度过大，即在D区内部 平台的工作分配极不均衡，需要对设置的平台进行管辖范围的重新分配。而A 区平台的出警次数差异度及出警时间差异度也较大，需要对平台设置进行优化或 改变平台的管辖范围以降低区域内各平台工作的不均衡性。A区的出警时间过短，说明其警力资源闲置较多，而C区、F区的平均出警 时间分别高达42.31,48.19,工作量负担过重，故可考虑在A区适当减少服务平 台，而在C区、F区增设部分服务平台，使平台的平均出警时间在各个区之间达 到均衡。每个区的平台办案率差异不大，警民比例在各个区的值差异也不大，仅就这 两个指标来看基本达到了平台工作均衡的要求。平台工作均衡度综合评价函数我们综合考虑城区系统间比较指标：警民比例、平台办案率、平均出警时间，他们均在一定程度上反映了平台工作分配的均衡情况，由于没有更多的信息参 考,我们认为三个指标的重要性权重相同，故建立平台工作均衡度综合评价函数,如下：fpk,ak,bk)=pk+g 4+g 48.3平台设置优化模型通过上述分析，我们建立目标函数为指标差异度最小的平台设置优化模型，考虑仅有城区系统间指标才能有效降低全市总体的平台工作的不均衡度，我们选取警民比 例、平台办案率、平均出警时间三个指标方差和最小作为目标函数，主要考虑服 务平台的工作均衡原则。现共有两个方案可以有效提高全市的平台工作均衡度。方案一：增减部分服务平台数量31对于警力资源利用率低的地区可以适当减少服务平台数量，使该区域内其他 服务平台的工作量得到提高；对于平台出警时间过长、出警次数过多的地区，可 适当增加服务平台的数量，使该区域内原有服务平台的工作量得到显著降低，最 终使得整个全市系统的服务平台工作量均衡度显著提高。方案二：改变现有平台的管辖范围此方案不改变现有平台的设置位置，通过改变每个平台的管辖范围，使其满 足”尽量3分钟内赶到事故发生地”的快速出警原则。建立平台设置优化模型 目标函数：总体指标差异度最小，考虑方案二的优化模型本质与平台管辖范围分配模型（第一问的问题1）相 同，只是优化的范围由A区全区变为全市6个区，模型的求解方法并无不同，在此不再给出详细介绍。我们针对方案一（增减部分服务平台数量）建立平台设置优化模型，主要基 于快速出警原则及平台工作均衡原则使得全市系统的平台设置合理性提高。1、决策变量我们考虑以增减平台的数量为决策变量，即决策变量为4,xk gZ,当4 0时表示增加平台，当/0表示减少平台，k=l,2,.,62、目标函数我们考虑该区的办案率即警民比例的波动程度，波动程度越小，表示该区内 部的服务平台工作量越均衡，故目标函数为32mi