交巡警平台警力调度方案的优化模型与算法设计(chap2).doc

交巡警平台警力调度方案的优化模型与算法设计摘要：关键词：服务平台，交巡警，优化模型，算法设计1、问题提出“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，现在要给出该区交巡警服务平台警力合理的调度方案。对该问题的解决，我们先建立最优的调度模型，使各服务平台到达交通要道的时间尽量的短。然后讨论求解算法，最后给出具体的计算结果。2、模型建立对于重大突发事件，需要调度城市的交巡警服务平台的警力资源，对进出该区的多条交通要道实现快速全封锁。采用的模型如下。设该市有个平台，用集合表示，其序号为。要封锁的交通要道有个，用集合表示，其序号为。 表示第个平台与第个交通要道之间的最短路，由Floyd算法求得。 为警车行驶速度。这里取公里/小时=1000米/分钟 设0-1决策变量每个交巡警服务平台的警力最多到一个交通要道去围堵，因此有：对每个交通要道，需要且只需要分配一个平台的警力，则有：设表示到第个路口的时间。则有： 我们选取的第一目标是到交通要道的最长时间最小化,这样可使最长时间尽量小。则第一目标函数为：当最长时间最小情况下，我们同时对小于最时间的分配方式进行优化，使到达各交通要道的时间平均时间最小。则第二目标函数为：综合上述，我们建立的的综合模型为：该结果的计算可以采用Lingo先求解第一目标，使最长时间最小。当求解出第一目标后，将到各交通要道的时间不超过最长时间变为约束，然后求最二目标，使用平均时间最小。但第一目标是非线性，通常Lingo并不能得到最优解，且计算很耗时。为此。我们另外设计算法，便于快速求解，并得到满意结果。3、算法设计 我们的求解算法采用三步完成。第一步，先利用贪婪法尽量使各平台到达交通要道的时间尽量短。第二步，对到各交通要道的时间再进行调整，进一步优化，直到最长时间不能再减少为止。第三步，在保证最长时间不增大的情况下，对到各交通要道的平均时间进行调整，直到不再减小为止。步骤一：贪婪法Step1：对第1个交通要道，在个平台中分配到达时间最短的一个。令最短时间为，分配的平台为，则有：；令剩下的平台集合为，则有：。Step2：对第个交通要道，在剩下的平台集合中，分配到达时间最短的一个。令最短时间为，分配的平台为，则有：；令剩下的平台集合为，则有：，。Step3：重复Step2，直到对所有交通要道都完成平台分配。通过贪婪法，可使各平台到达交通要道的时间尽量短，但不能保证最优。下面通过第二步的较少最长时间，可使最长时间达到最小，从而实现最优。步骤二：减少最长时间算法该算法采用交换平台的思想，若交换后使最最长时间减小则成功一次，直到不能再减小为止。算法描述如下：Step1：根据步骤一确定出到第个交通要道的时间，第个交通要道指派的平台。剩余未分配的平台集合Step2：求出到各交通要道的最长时间，其对应交通要道序号为，分配的平台序号为。Step3：循环执行计算对交通要道指派第个路口对应的平台，平台到要道的时间。计算将交通要道以前分配的平台加入剩余平台后的集合计算交通要道从剩余平台集合中分配平台的最短时间，分配的平台为。若，则表示调整成功，最长时间减小。存储到第个要道的新时间，新平台；到第个要道的新时间；新平台在该循环体中若成功，则跳出该循环；若始终无法成功，则直到循环完成跳出。Step4：重复Step1，Step2，Step3。直到最长时间不再减小结束。输出各路口对应平台及时间。步骤三、减小平均时间算法该算法与步骤二中算法思想类似。只是将目标函数由最长时间变为平均时间。算法描述如下：Step1：根据步骤一确定出到第个交通要道的时间，第个交通要道分配的平台。剩余未分配的平台集合Step2：求出到各交通要道的平均时间。Step3：循环执行；计算对交通要道指派第个路口对应的平台，平台到交通要道的时间。计算将交通要道以前分配的平台加入剩余平台后的集合计算交通要道从剩余平台集合中分配平台的最短时间，分配的平台为。若，且则表示调整成功，最长时间没有增大，总时间减小，从而平均时间减小。存储到第个要道的新时间，新平台；到第个要道的新时间；新平台在该循环体中若成功，则跳出该循环；若始终无法成功，则直到循环完成跳出。Step4：重复Step1，Step2，Step3。直到总时间或平均时间不再减小结束。输出各路口对应平台及时间，平均时间。4、结果计算示例一对问题2中的A区，要封锁的交通要道有个，其集合为=12,14,16,21,22,23,24,28,29,30,38,48,62。可供指派的平台有个，其集合为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个。要封锁的交通要道个，其集合为=151,153,177,202,203,264,317,325,328,332,362,387,418,483,541,572,578。可供分配的平台个，其集合为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号交通要道外，其余各交通要道都分配的到达时间最短的平台。而到达202号交通要道的时间最少的平台为177，次之为175，177号平台分配给177号交通要道最佳，从而分配175号平台给202号交通要道最佳。可验证该结果即为最优结果。即最长时间最小为12.68分钟，平均时间最小为5.07分钟。详细结果见表1。表4 各交通要道到达时间与分配的平台序号交通要道号分配的平台号到达时间(分钟)1151963.192153994.4731771770420217511.6252