《交巡警平台警力调度方案的优化模型与算法设计chap2》由会员分享，可在线阅读，更多相关《交巡警平台警力调度方案的优化模型与算法设计chap2（10页珍藏版）》请在金锄头文库上搜索。
1、交巡警平台警力调度方案的优化模型与算法设ii(chap2)# / 8交巡警平台警力调度方案的优化模型与算法设ii(chap2)交巡警平台警力调度方案的优化模型与算法设计摘要:关键词；服务平台，交巡警，优化模型，算法设计1、问题提出“有困难找警察”，是家喻戸晓的一句流行语。警察肩负着刑事执法、治安管理、交通 管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和 重要部位设宜交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务 资源是有限的，如何根据城币的实际情况与需求合理地设巻交巡警服务平台、分配各平台的 管辖范用、调度警务资源是警务部门而临的一个实际
2、课题。给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图， 相关的数据信息见附件2。对于重大突发事件，需要调度全区20个交巡警服务平台 的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的 警力最多封锁一个路口，现在要给岀该区交巡警服务平台警力合理的调度方案。对该问题的解决，我们先建立最优的调度模型，使各服务平台到达交通要道的时间尽量 的短。然后讨论求解算法，最后给岀具体的讣算结果。2、模型建立对于重大突发事件，需要调度城市的交巡警服务平台的警力资源，对进出该 区的多条交通要道实现快速全封锁。采用的模型如下。设该市有“个平台，用集合P表示，其序号为21
3、,2,./。要封锁的交通要道有加个，用集合丿表示，其序号为丿 =1,2，,加。心表示第i个平台与第丿个交通要道之间的最短路，III Floyd算法求得。v为警车行驶速度。这里取y = 60公里/小时=1000米/分钟设决策变量州毗第i个平台指派到第j个路口第i个平台不指派到第j个路口每个交巡警服务平台的警力最多到一个交通要道去围堵，因此有:fn工兮 1 i = 12丿对每个交通要道，需要且只需要分配一个平台的警力，则有:ft工勺=1 j = 1,2,加 j-i设7；表示到第丿个路口的时间。则有:nTj =工血无j 丿= 1,2,冲r-l我们选取的第一 LI标是到交通要道的最长时间最小化，这样可
4、使最长时间尽 量小。则笫一 H标函数为：min Zj = max Tjjm当最长时间最小情况下，我们同时对小于最时间的分配方式进行优化，使到 达各交通要道的时间平均时间最小。则第二目标函数为：YJjmin Z.= m综合上述，我们建立的的综合模型为:niin 乙=max 7jmmin Z2 =m# / 8交巡警平台警力调度方案的优化模型与算法设ii(chap2)nt为X” 1i = 1,2,# / 8交巡警平台警力调度方案的优化模型与算法设ii(chap2)# / 8交巡警平台警力调度方案的优化模型与算法设ii(chap2)该结果的计算可以采用Lingo先求解第一 口标，使最长时间最小。当求解
5、岀 笫一 LI标后，将到各交通要道的时间不超过最长时间变为约束，然后求最二U标, 使用平均时间最小。但第一目标是非线性，通常Lingo并不能得到最优解，且计 算很耗时。为此。我们另外设计算法，便于快速求解，并得到满意结果。3、算法设计我们的求解算法釆用三步完成。第一步，先利用贪婪法尽量使各平台到 达交通要道的时间尽量短。第二步，对到各交通要道的时间再进行调整，进一步 # / 8交巡警平台警力调度方案的优化模型与算法设ii（chap2）优化，直到最长时间不能再减少为止。第三步，在保证最长时间不增大的情况下, 对到各交通要道的平均时间进行调整，直到不再减小为止。步骤一：贪婪法Stepl：对第1个交
6、通要道，在“个平台中分配到达时间最短的一个。令最短时间为人，分配的平台为A ,则有：7； = ! /V = niin J, /v）；令剩下的平台集合为片，则有： = P-和。Step2：对第k个交通要道，在剩下的平台集合人“中，分配到达时间最短的 个。令最短时间为7；,分配的平台为L，则有:Tk=d, A /v = min4/v）;令剩 剛t下的平台集合为a，则有： m 伙=2,3,.,加）。Step3：重复Step2,直到对所有交通要道都完成平台分配。通过贪婪法，可使各平台到达交通要道的时间尽量短，但不能保证最优。下 面通过第二步的较少最长时间，可使最长时间达到最小，从而实现最优。步骤二：减
7、少最长时间算法该算法采用交换平台的思想，若交换后使最最长时间减小则成功一次，直到 不能再减小为止。算法描述如下：Stepl：根据步骤一确定出到第丿个交通要道的时间0 = 1,2，,加），第丿个 nt交通要道指派的平台匕（）= 12冲八 剩余未分配的平台集合r = p-Qt/.Step2：求出到各交通要道的最长时间mnxT = Tk =minTf,其对应交通要道 J序号为k,分配的平台序号为匕。Step3：循环执行/ = 1,2,z （/工）计算对交通要道k指派第/个路口对应的平台4,平台到要道的时间计算将交通要道以前分配的平台匕加入剩余平台后的集合ntY = P-JUj+UkAl计算交通要道/
8、从剩余平台集合中分配平台的最短时间G = min d,，/v), 分配的平台为旷。若斤max72max7,则表示调整成功，最长时间减小。存储到第k个要 道的新时间Tk=,新平台Uk=Ut；到第/个要道的新时间T,=t2；新平台U,=t在该循环体中若成功，则跳出该循环；若始终无法成功，则直到循环完成跳 出。Step4：重复Stepl, Step2, Step3o直到最长时间maxT不再减小结束。输 出各路口对应平台及时间。步骤三、减小平均时间算法该算法与步骤二中算法思想类似。只是将标函数山最长时间变为平均时 间。算法描述如下：Stepl：根据步骤一确定出到第丿个交通要道的时间7, (j = l,
9、2，,加)，第丿个 nt交通要道分配的平台匕()= 12冲八 剩余未分配的平台集合Y = PJUt7-1m亍TjStep2：求出到各交通要道的平均时间=上。mStep3：循环执行 I = 1,2 m: r = 1,2,，加(/ r)计算对交通要道厂指派第/个路口对应的平台匕，平台到交通要道的时间计算将交通要道，以前分配的平台匕加入剩余平台后的集合ntY = P-JUj+Urj-i计算交通要道/从剩余平台集合中分配平台的最短时间分配的平台为旷。若片+/2+石，且/, maxr,r2 max?则表示调整成功，最长时间没有增大，总时间减小，从而平均时间减小。存储到第r个要道的新时间Tr=fl,新平
10、台S 到第/个要道的新时间7；=r2；新平台Ut=T在该循环体中若成功，则跳出该循环；若始终无法成功，则直到循环完成跳 出。Step4：重复Stepl, Step2, Step3。直到总时间或平均时间不再减小结束。 输出各路口对应平台及时间，平均时间。4、结果计算示例一对问题2中的A区，要封锁的交通要道有加=13个，其集合为 J =12,14,16,21,22,23,24,28,29,30,38,48,62。可供指派的平台有 “ =20 个，其集 合为 P二1,2,3,4,5,6,7,&9,10,11,12,13,14,15,1,17,1 & 19,20。采用步骤一中贪婪法求得最长时间为13.
11、67分钟，平均时间为3.95分钟。详 细结果见表1。该结果需要调整最长时间。表1贪婪法求得各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间（分钟）112120214140316160421132.71522113.276231091724913.67828154.7592978.02103()S3.06113S23.9812斗852.48136240.35采用步骤二中减少最长时间的算法，经过5次调整，最长时间达到最小。最 长时间为&02分钟，平均时间为3.78分钟。该结果最长时间达到了最小。详细 结果见表2。该方案的平均时间需要调整。表2调整最长时间后各交通要道到达时间与分配的
12、平台序号交通要道号分配的平台号到达时间（分钟）1121()7.59214166.7431691.53421143.26522113.27623130.5724123.59828154.7592978.021030S3.06113823.98124852.48136240.35采用步骤三中减少平均时间的算法，最长时间仍然为8.02分钟，有3个交 通要道指派的平台经过了调整。平均时间由3.78分钟减小到3.55分钟。该结果 最长时间达到了最小，平均时间也达到最小，结果达到了最优。详细结果见表3。表3调整平均时间后各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间(分钟)1121202
13、14166.7431691.53421143.26522107.71623130.5724113.81828154.7592978.021030S3.06113823.98124852.48136240.35示例二：全市有交巡警平台80个，全市岀入口位宜有17个。要封锁的交通要道加=17个，其集 合为 J=151,153,177, 202, 203, 264, 317, 325, 32& 332, 362, 387, 418, 483, 541, 572, 578可 供分配的平台 rt = 8O个，其集合为P= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12, 13,
14、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, # / 8交巡警平台警力调度方案的优化模型与算法设ii(chap2)377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 475, 476, 477,478, 479,480, 481, 482, 483, 484 ,485o采用步骤一中贪婪法求得最长时间为12.68分钟，平均时间为5.07分钟。该 结果通过调整并不能减少最长时间
