2011B交巡警问题_赛题讲解

2011B题交巡警服务平台的设置与调度“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。附件1：A区和全市六区交通网络与平台设置的示意图。附件2：全市六区交通网络与平台设置的相关数据表（共5个工作表）。问题1对该问题的解决，我们先建立数学模型，将需要达到的目标，包括到达事发地的时间尽量短，各服务平台的工作量尽量均衡，用目标函数表达出来，同时将需要满足的约束也表达出来，构成合适的数学模型。然后讨论求解算法，最后给出具体的计算结果。我们的路口管辖分配方案分为两步。第一步：对3jT的路口，分配给到达第j个路口时间最少的平台。第二步：对3jT的所有路口，根据尽量使各平台分配的任务量尽量均衡的原则进行优化。表13分钟不能到达的路口及所属平台信息序号路口任务量所属平台最短时间(分钟)1281.3154.752291.4155.703381.2163.414391.423.685610.674.196920.8203.60因此，我们将这6个路口分配给最近的平台，剩下的86个路口建立模型，根据任务量尽量均衡的原则进行优化。模型建立设有20个平台，路口有86个。ijd表示第i个平台与第j个路口之间的最短路，由Floyd算法求得。1,2,...,20;1,2,...,86ijv为警车行驶速度。这里取60v公里/小时=1000米/分。建立决策变量10ijjixji第个路口分配给第个平台第个路口不分配给第个平台每个路口只分配给一个平台，有约束：20111,2,..,86ijixj第j个路口到指派的平台的时间为jt，满足：201./1,2,..,86jijijitxdvj其时间应满足不超过3份钟，则有：31,2,..,86jtj计算第i个平台分配的路口数的任务量为。设已知第j个路口的任务量（平均每天的发生报警案件数量）为jf，1,2,...,86j，则第i个平台已经分配到的任务量：861.1,2,...,20iijijjswfxiiw为各平台已分路口数的任务量。由表1知为21.4w，70.6w，151.41.32.7w，161.2w，200.8w。其余为0。各平台分配的任务量平均值为：20120iiss我们的目标是各平台分配的任务量的标准差尽量小。即：2021()min201iissZ因此我们得到的综合模型为：2021()min201iissZ20120186120111,2,..,86./1,2,..,8631,2,..,86...1,2,...,2020011,2,...,20;1,2,...,86ijijijijijiijijjiiijxjtxdvjtjstswfxissxij或采用Lingo12优化得到Z=2.06(计算时间1分52秒)，表示每个平台的任务量平均有2件的波动。各平台的分配方案见表2。表2各平台管辖的路口分配及任务量平台管辖的路口总任务量最长时间(分钟)12,19,69,71,7371.923,17,39,756.93.68344,54,55,65,67,68,766.52.7644,57,60,62,63,646.61.9455,6,49,537.22.94648,50,51,52,56,58,596.42.7577,8,61,307.54.19816,34,475.92.69931,32,33,36,37,5.72.061010,1.601111,25,26,276.2212122.401313,21,22,23,248.52.7114142.501515,28,294.85.7169,35,38,45,467.33.411740,41,42,43,707.12.691820,72,84,85,87,88,89,90,9110.12.78191,66,74,77,78,79,806.82.382018,81,82,83,86,927.53.6问题2给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，现在要给出该区交巡警服务平台警力合理的调度方案。对该问题的解决，我们先建立最优的调度模型，使各服务平台到达交通要道的时间尽量的短。然后讨论求解算法，最后给出具体的计算结果。模型建立对于重大突发事件，需要调度城市的交巡警服务平台的警力资源，对进出该区的多条交通要道实现快速全封锁。采用的模型如下。设该市有20个平台，要封锁的交通要道有13个。ijd表示第i个平台与第j个交通要道之间的最短路，由Floyd算法求得。v为警车行驶速度。这里取60v公里/小时=1000米/分钟设0-1决策变量1j0jijx第个路口分配给第i个平台围堵第个路口不分配给第i个平台围堵对每个交通要道，需要且只需要分配一个平台的警力，则有：20111,2,...,13ijixj每个交巡警服务平台的警力最多到一个交通要道去围堵，因此有：13111,2,...,20ijjxi设jT表示到第j个路口的时间。则有：201/jijijiTdxv1,2,...,13j我们选取的第一目标是到交通要道的最长时间最小化,这样可使最长时间尽量小。则第一目标函数为：1113minmaxjjZT当最长时间最小情况下，我们同时对小于最时间的分配方式进行优化，使到达各交通要道的时间平均时间最小。则第二目标函数为：1312min13jjTZ综合上述，我们建立的的综合模型为：1113minmaxjjZT1312min13jjTZ20113120111,2,...,1311,2,...,20../01ijiijjjijijiijxjxistTdxvx或该结果的计算可以采用Lingo先求解第一目标，使最长时间最小。当求解出第一目标后，将到各交通要道的时间不超过最长时间变为约束，然后求最二目标，使平均时间最小。但第一目标是非线性，通常Lingo并不能得到最优解，且计算很耗时。为此。我们另外设计算法，便于快速求解，并得到满意结果。3、算法设计我们的求解算法采用三步完成。第一步，先利用贪婪法尽量使各平台到达交通要道的时间尽量短。第二步，对到各交通要道的时间再进行调整，进一步优化，直到最长时间不能再减少为止。第三步，在保证最长时间不增大的情况下，对到各交通要道的平均时间进行调整，直到不再减小为止。1.先将13个交通要道依次分配给最近的路口。2.将时间最长的要道与其余的要道分配的平台对换，若最长时间可以减少，则对换。实际中可在对换后，另一要道在剩余平台中选择最近的平台。3.重复2，直到最长时间不再减少为止。对平均时间的减少采用同样的方法。直到总时间或平均时间不再减小结束。输出各路口对应平台及时间，平均时间。4、结果计算示例一对问题2中的A区，要封锁的交通要道有13m个，其集合为J={12,14,16,21,22,23,24,28,29,30,38,48,62}。可供指派的平台有20n个，其集合为P={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,17,18,19,20}。采用步骤一中贪婪法求得最长时间为13.67分钟，平均时间为3.95分钟。详细结果见表1。该结果需要调整最长时间。表1贪婪法求得各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间(分钟)112120214140316160421132.71522113.27623109.11724913.67828154.7592978.02103083.06113823.98124852.48136240.35采用步骤二中减少最长时间的算法，经过5次调整，最长时间达到最小。最长时间为8.02分钟，平均时间为3.78分钟。该结果最长时间达到了最小。详细结果见表2。该方案的平均时间需要调整。表2调整最长时间后各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间(分钟)112107.59214166.7431691.53421143.26522113.27623130.5724123.59828154.7592978.02103083.06113823.98124852.48136240.35采用步骤三中减少平均时间的算法，最长时间仍然为8.02分钟，有3个交通要道指派的平台经过了调整。平均时间由3.78分钟减小到3.55分钟。该结果最长时间达到了最小，平均时间也达到最小，结果达到了最优。详细结果见表3。表3调整平均时间后各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间(分钟)112120214166.7431691.53421143.26522107.71623130.5724113.81828154.7592978.02103083.06113823.98124852.48136240.35示例二：全市有交巡警平台80个，全市出入口位置有17个。要封锁的交通要道17m个，其集合为J={151,153,177,202,203,264,317,325,328,332,362,387,418,483,541,572,578}。可供分配的平台80n个，其集合为P={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,93,94,95,96,97,98,99,100,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,320,321,322,323,324,325,326,327,328,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,475,476,477,478,479,480,481,482,483,484,485}。采用步骤一中贪婪法求得最长时间为12.68分钟，平均时间为5.07分钟。该结果通过调整并不能减少最长时间，可以验证，该分配方案中，除202号交通要道外，其余各交通要道都分配的到达时间最短的平台。而到达20