交巡警平台设计.

交巡警服务平台的设置与调度2011全国大学生数学建模竞赛B题解析陈恩水201208.181.1根据附件信息，为各交巡警服务平台分配管辖范围。使尽量能在3分钟内有交巡警到达事发地。1.2对于重大突发事件，需要调度全区20个交巡警服务平台警力资源对进出该区13条交通要道实现快速全封锁。要求给出该区交巡警服务平台警力合理调度方案。问题一1.3为缓解现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题一2.1针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。给出合理方案。。2.2如果该市地点P处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。请给出调度全市交巡警服务平台警力资源的最佳围堵方案。问题二模型假设1.一个平台的警力最多封锁一个路口；2.巡警台控制范围的划分以路口节点来衡量，而不是路程；3.有一个巡警台的警力封住路口即认为罪犯逃不出该路口。4.本区的巡警平台只负责管辖本区。ijdijb：警务台Ai到路口节点j的最短路程：警务台Ai到路口节点j的最短路程连接权jf各个路口节点的犯案率ijkiA到13个出入A城区路口节点j的最短路程iA符号说明1.1分配城区A警务台分配管辖范围·路口的节点*路口节点○服务平台点这是优化问题，应该明确优化指标（准则）。分配原则：尽量3分钟内达到任务尽可能均衡就近分配需要知道各路口到就近警台的距离如何计算各路口到警台距离•该问题可看作为加权图问题Floyd算法可用来计算相关距离矩阵可用来作为该问题的数学描述列表给出距离的相关结果（后续问题的关键）最好简化计算20*92的距离矩阵。•结果分析：有六个路口节点发案时，各警务台3分钟内不能到达；分别为28,29,38,39,61,92。不能在3分钟内有交巡警到达的路口节点分配原则为就近分配。•定义•根据就近原则，有10ijijXij警台管辖节点警台不管辖节点1303ijijbij警台到节点距离不超过分钟（公里）警台到节点距离超过分钟（公里）X15,28X1529X16,38X2,39X7,61X20,921，问题的一般模型•目标函数（基于总出警路程最小）1Mmin)s.t201*1ijijiXb(28,29,38,39,61,92)jiD921*ijijjdXijX0,1Xi,iX15,28X15,29X16,38X2,39X7,61X20,921，，201iiD•目标函数（同时考虑距离及任务量）2021minMSiiDF（），（加权任务方差）201*1ijijiXb(28,29,38,39,61,92)j921**ijijijjDFfXdijX0,1Xi,iX15,28X15,29X16,38X2,39X7,61X20,921•前一个模型考虑问题不全面，虽然结果差不多，没有第2个模型好。•虽然1.1问没有任务量要求，但从解决问题的角度，应该更全面地去处理问题，特别是有些后续问题中提到的因素，更要考虑。相关结果•模型一总发案率标准差=2.903695。总的出警路程=102.6696km模型二结果•总的出警路程=137.4178km，总发案率标准差=2.002998•不同的模型分配方案不同，模型一方案：•1.2封锁路口警力合理的调度方案•目标：封锁路口最长时间尽可能小•每个平台最多负责一个路口•每个路口只能一个平台131201minmax*X.X1,X1,X=01ijijjiijjijiijkstij，X:ijij其中：平台选择，k：最短路程linge求解调度方案模型结果•最快需要8.0155min。1.3确定增加平台的个数和位置•设•1,()0ixi将节点设为警务平台，不将节点i设为警务平台921min()iyxiX(),ijxi（非平台无管地）9211,ijib（至少有一个平台3分钟到达）1X1,(1)yiji必有个平台管辖j()1xi1,,20i::ijijXibi平台管辖选择平台的距离函数X=0,1ij9212225ix模型求解•该模型求解比较复杂，可穷举给出次优结果。•原20个平台已经在3分钟内能覆盖86各个节点，先穷举需增加几个平台才可以覆盖此6个节点。•给出能覆盖6个节点的所有节点位置：•Q={28,29,38,39,40,48,61,87,88,89,90}•固定其中几个，优化另几个位置（可穷举）。结果，增加4个平台•有多种方案，如:•节点位置：29,40,61,92•节点位置：29,40,61,88•节点位置：29,38,48,92•计算上述方案的任务均衡性，29,38,48,92是更理想的选择。2.1全市现有平台合理性•各区状况分析•结论：原来的警务台设置造成了各区出警时间、任务量不平衡。优化目标:任务尽可能均匀。优化方案设计•准则：（1）改善3分钟到达率（2）改善任务均衡性（3）是否增加平台数建模思路：（1）分区优化（2）全市优化（3）以调整为主基于任务量均衡的考虑•保持全市平台总数不变（1）全市每个警务台平均处理的发案率：582jj=1f=8.4312580（2）各区警务台发案率总和•结论：A区减少5个，C区增加5个，•D，E区个减少1个，F区增加两个，其他不变。•改进后各区平均任务量各城区警务台重新设置•A城区建立如下模型（其他区类似)209211151201minX1,()15(15)()0,21,,92jijijijijiifdXxixii（节点j有仅有1个平台管辖）个平台结论•从A区将6、8、10、16、19号节点处5个交巡警服务平台调出；•调入5个平台到C区的208、240、260、285、303号节点处；•从D区将322号节点处的平台调出；•从E区将376号节点处的平台调出；•调入2个平台到F区的518、525号节点处；•其他区不变。方案比较•区号ABCDEF全市•当前方案的工作量方差•8.43115.4732.1312.7717.1526.7120.73•优化后方案的工作量方差•14.6515.4714.3615.1314.9313.1413.592.2围堵方案（给定警车速度）••（1）计算嫌疑犯从点P逃出城市最短时间T，则围堵必须在T前完成。•围堵模型：801()1minmax()1()1()0,1,3(3)jjjijijiijintijjijpjjttXdjXjXiXtTdtvtt犯（合围时间最短）围堵节点所需时间路口必须有一个平台平台至多负责1个节点，(),Y1,,()nttnt时刻合围最小边界节点数（n）=边界节点编号寻找次优解•5,=7,=9,()208.98jtttntt无法围堵，n(t)12无法围堵,n(t)18可以围堵，min•序号1234567位置16562361555232平台1656173153171围堵时间0000.6301.271.91逃逸时间3.303.883.914.094.145.215.72次优结果•序号891011121314位置103402465616041平台1021717247541围堵时间02.112.694.724.351.744.44逃逸时间6.196.487.966.558.87.7410.5结果序号151617181920位置4240168370371248平台168169175320321167围堵时间3.707.055.07.818.983.68逃逸时间8.810.1512.4816.3415.8920.52•被围堵区域可能到达节点如下：欢迎交流