搜索
基于时间约束和均衡度的平台设置与调度模型摘要警察是社会中非常重要的角色，而警务资源是有限的。因此，本文针对如何合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源这一问题，建立了基于时间和均衡度约束的平台设置与调度模型。针对问题一第一小问，以总平台工作量最小、平台工作量均衡度最大、满足3min约束的路口数目最多这三个为综合目标函数，利用0—1规划，建立了A区各平台分配管辖范围模型。求解得出除路口28，29，38，39，61，92外，其他86个路口都满足3min约束，具体结果见表2。第二小问属于指派问题，我们在第一小问的基础上做些修改，将封锁路口的时间作为目标函数，求解得出实现最快封锁的调度方案需8.02min。第三小问从使所有路口满足3min约束和新增平台数目最少两方面考虑，得到10种可行方案，再从均衡度考虑，最终得出最优方案为增加平台28、40、48、87，此时各平台到所管辖的路口最长时间为2.9682min，满足时间约束。针对问题二第一小问，定义平台合理度为满足3min约束的路口数目所占比例，对各区分别进行评价，得出F区合理度最低，对其平台设置方案仿照第一问进行改进，应增加平台12、31、35、51、66、67、75、86、87、92、100、101、104、108，此时各平台到所管辖的路口最长时间为2.9530min，满足时间约束。第二小问将围堵嫌犯的动态过程转化为各个时刻的静态过程，对不同时刻求出嫌烦最大逃逸范围，当封锁最大逃逸范围所用时间Z(t)小于嫌犯的逃逸时间减去案发至报警的3min，则认为围堵成功。采用floyd算法最终求出最短围堵时间为10.9635min。关键词：均衡度时间约束指派问题平台合理度1一、问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析解决下面的问题：问题一：题目附件1（A区和全市六区交通网络与平台设置的示意图）中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2（全市六区交通网络与平台设置的相关数据表）。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题二：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、模型假设1.假设交巡警时速为平均速度。2.假设嫌犯逃逸速度为60km/h（题目未给出速度）。3.分析各区平台设置合理性时，假设交巡警平台到达区内平台的途中不经过其他区。4.为平台分配管辖范围时，假设题目给出的路口发案率指路口周边一定范围内的发案率。5.假设题目所给的路口坐标数据是精确、合理的。2三、符号定义各符号及含义见表1。表1符号含义说明符号含义v交巡警的速度tij交巡警从第i个平台到第j个路口节点所需时间pj第j个路口节点的发案率S满足时间要求的路口节点的集合Ge（S）集合S元素的个数N表示区内到任一平台时间均超过3min的路口数M表示区内路口总数q平台设置合理度σ工作量均衡度T封锁完所有要道的总用时C(t)完全封锁这个逃逸范围的最少路口集合四、问题分析问题一：题目第一小问要求为A区各交巡警服务平台分配管辖范围，需要从总平台工作量最小、各平台工作量最均衡、满足3min约束的路口数目最多这三方面考虑。第二小问要求调度交巡警对A区进行封锁，属于指派问题。第三小问要求对交巡警平台设置方案进行改进，应该从使所有路口满足3min约束和新增平台数目最少两方面考虑。问题二：题目第一小问要求评价该市交巡警服务平台设置方案的合理性，应该以满足3min约束的路口数目所占比例为主要指标，对各区分别进行评价，并给出改进方案。第二小问要求给出调度全市警力资源的最佳围堵方案，需要将围堵嫌犯的动态过程转化为各个时刻的静态过程，简化问题的求解。3五、模型的建立与求解5.1问题一模型的建立与求解5.1.1第一小问模型的建立与求解题目要求将92个路口节点分配给20个交巡警平台管辖，使交巡警在所管辖的范围内出现突发事件时，尽量能在3分钟内到达事发地，因此我们要综合交巡警到达时间和平台管辖的总路口节点数来考虑。设dij为第i个平台到第j个路口节点的距离，v为交巡警的速度，则交巡警从第i个平台到第j个路口节点所需时间tij为ijijdtv（1）由此可以得出各平台到每个路口节点的时间。对于时间均大于3min的节点令其归属于最近的平台；仅到一个平台时间小于3min的节点令其归属于对应的平台；到两个或两个以上平台时间小于3min的节点，我们选择任一个使工作量均衡度最大的平台，即满足（2）式最小即可。209220922111111(2020ijijijjijij)xpxpj（2）其中pj为第j个路口节点的发案率。设随机变量11,2,,201,2,,920ijijxiij第个平台管辖第个节点第个平台不管辖第个节点根据上述路口节点对应平台的选择原则，最终会有多种方案，在此前提下，选择各平台到每个节点的总用时最短的，即使得（3）式达到最小。（3）209211ijijijtx由于总有几个无法满足题目要求的路口节点，即无法使得交巡警在3min内到达，因此模型应尽可能的保证更多的点符合题意。设集合S为满足时间要求的路口节点，则|,3minijSjit使得为了使更多的点符合题意，令Ge（S）最大，其中Ge（S）为集合S元素的个数。综合上述分析，可以得到该问题的模型为：max()GeS4209211minijijijtx209220922111111min()2020ijijijijijijxpxp（4）2011.01,2,201,2,,920,1ijiijijxsttijx根据上述模型，我们使用Lingo及MatLab软件进行求解，工作量均衡度σ=7.7018，各平台管辖的路口结果见表2：表2A区各平台管辖的路口平台管辖的路口到达最远路口时间（min）1119717478801.7583239404243693.68223344545568762.7622445760626364662.8356564953582.94266550515256592.3841730323348614.1902879472.4777981635371.532510100111126271.64331212251.78891313212223242.70831414015152829315.70051634363845463.40591721741702.591118207279828589902.778519186567737577812.788020838486878891923.60135由表1可以看出，除路口28，29，38，39，61，92到相应管辖平台的时间超过3min外，其他路口若出现案件，交巡警平台都能及时到达。而且平台到路口的最远时间为5.7005min，已经是较好的结果了。根据表格结果我们绘出具体交巡警平台管辖范围图（见图1）：200250300350400450260280300320340360380400交通服务平台服务范围图‘.’表示交叉路口‘+’表示交通服务平台图1A区交巡警平台管辖范围图5.1.2第二小问模型的建立与求解对于这一小问，核心为指派问题，即从20个平台中选出一部分去封锁该区的13条要道，也就是13条关键路口节点。设随机变量11,2,,201,2,,130ijijijij第个平台封锁第个路口节点第个平台不封锁第个路口节点由于一个平台的警力最多封锁一个路口，则1311ijj（5）设第i个平台封锁第j个关键路口节点的时间为tij，则封锁完所有要道的总用时T以用时最长的为准，即maxijijiTt为实现快速封锁，选取总用时最短的方案。6综合上述分析，该问题的数学模型为：minmaxijijiTt（6）13120111.1,2,201,2,130,10ijjijiijijstijt根据上述模型，我们使用Lingo及MatLab软件进行求解，求解得出交巡警服务平台警力合理的调度方案见表3：表3交巡警服务平台警力合理的调度方案平台要道路口路径耗时(min)3163-45-35-36-166.034484-57-58-59-51-50-5-47-487.407297-30-298.028308-33-32-7-303.06102210-26-11-227.71112411-25-243.81121212-120132313-230.50142114-213.27152815-283.27161416-146.74193819-79-78-1-69-70-2-40-39-387.64206220-85-626.45由表3可以得出实现最快封锁的调度方案需8.02min。根据表格结果我们绘出具体交巡警服务平台警力合理的调度方案示意图（见图2）：7200250300350400450260280300320340360380400A区实现快速全封锁图点表示节点‘+’表示交警服务平台‘——’表示快速封锁线图2交巡警服务平台警力合理的调度方案示意图5.1.3第三小问模型的建立与求解为了使所有路口到所管辖平台的时间不超过3min，应考虑A区中到现有平台的时间均超过3min的路口，距这些特殊路口时间不超过3min的路口如表3。表4距特殊路口时间不超过3min的其他路口特殊路口其他路口282929283839403938406148928788899091因此,为使所有路口到所管辖平台的时间不超过3min，应增加新的平台，但新增平台数目被限制为2~5，且考虑到成本的问题，平台个数应越少越好，结合表3可以得到如下新增平台的10种方案：28,40,48,87,28,40,48,88,28,40,48,89,28,40,48,90,28,40,48,91,29,40,48,87,29,40,48,88,29,40,48,89,29,40,48,90,29,40,48,91,S设每种方案新增的4个平台统一为第21个新增平台。设随机变量811,2,,211,2,,881,2,,100kkijkkijxijij第个平台管辖第个节点第个平台不管辖第个节点k利用第一小问的模型与算法，可以求解得出每一种增设平台方案的均衡度，根据题目对均衡度的要求，选择均衡度最大，标准差最小的方案为最终方案。综合上述分析，该问题的数学模型为：218821882111111min()2424kkkki