徐 标，陈 昊，杨文芳，鲁 群，张 硕

(淮北师范大学 数学科学学院，安徽 淮北 235000)

此问题为2011年全国大学生建模竞赛的B题第一部分，问题的背景见文[1]，主要是结合重庆市交巡警服务平台设置的相关情况，建立数学模型分析研究下面的问题:

图1给出该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见文献[2].请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3 min内有交巡警(警车的时速为60 km/h)到达事发地.

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁.实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案.

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2－5个平台，请确定需要增加平台的具体个数和位置.

1 问题分析

首先利用Floyd[3]算法分别求出每个坐标节点到各平台 i(i=1，2，…，20)的最短距离，对各节点 j，选择使得距离 dij最小的路线.对于每个节点 j，将其划分到离它最近的平台管辖的区域，则得到一个初步的管辖范围，再对结果进行优化.

对于调度方案，本文采用最大时间最小化的方法[4－5]，即选取到达每一个交通要道的时间最短的路线，而封锁的时间为选取的时间中最大的时间，再争取该最大时间最小，表示为max mindij，同时尽可能保证总……