交巡警服务平台的设置与调度优化分析
摘 要
本文综合应用了Floyd算法，匈牙利算法，用matlab计算出封锁全市的时间为1.2012小时。并在下面给出了封锁计划。
为了得出封锁计划，首先根据附件2的数据将全市的道路图转为邻接矩阵，然后根据邻接矩阵采用Floyd算法计算出该城市任意两点间的最短距离。然后从上述矩阵中找到各个交巡警平台到城市各个出口的最短距离，这个最短距离矩阵即可作为效益矩阵，然后运用匈牙利算法，得出分派矩阵。根据分派矩阵即可制定出封锁计划：96-151,99-153,177-177,175-202,178-203,323-264,181-317, 325-325,328-328，386-332,322-362,100-387,379-418,483-483, 484-541, 485-572。除此以外，本人建议在编号为175的路口应该设置一个交巡警平台，这样可以大大减少封锁全市的时间，大约可减少50%。
关键词: Floyd算法 匈牙利算法 matlab
一、问题重述
“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
警车的时速为60km/h, 现有突发事件，需要全市紧急封锁出入口，试求出全市所有的交巡警平台最快的封锁计划，一个出口仅需一个平台的警力即可封锁。
二、模型假设
1、假设警察出警时的速度相同且不变均为60km/h。 2、假设警察出警的地点都是平台处。
3、假设警察接到通知后同时出警，且不考虑路面交通状况。
三、符号说明及一些符号的详细解释
A 存储全市图信息的邻接矩阵 D 任意两路口节点间的最短距离矩阵
X 0?1规划矩阵
aij i,j两路口节点标号之间直达的距离 dij 从i路口到j路口的最短距离 bij 从i号平台到j号出口的最短距离
xij 取0或1，xij?1表示第i号平台去封锁j号出口
在本文中经常用到i,j，通常表示路口的编号，但是在dij，bij，xij不再表示这个意思，i表示第i个交巡警平台，交巡警平台的标号与附件中给的略有不同，如第21个交巡警平台为附件中的标号为93的交巡警平台，本文的标号是按照程序的数据读取顺序来标注的，在此声明；j表示第j个出口，如：第5个出口对应于附件中的路口编号为203的出口。但在论文给出的结果中使用的是附件中给的标号。
四、问题分析
1
本题要求交巡警平台最快的封锁计划，即可以在最短的时间内完成全市的封锁。全市共有17个出口，80个交巡警平台，这就要求我们在这个80个平台中选出17个作为出警平台，使这17个出警平台比任意其他的17个出警平台都能在更短时间内完成全市的封锁。那么这17个平台分别取封锁哪个出口即是我们要求的。
由于出警时的速度都是60km/h，那么本题的核心就变为了最短路问题了，有最短的路径，就会有最短的时间。但是作为一个封锁计划，一定是全市各个出警平台同时开始封锁，那么我们只需求出这17个出警平台用时最多的那个最为本题要求的封锁时间。
这样我们的思路就非常明确了：
首先我们先求出80个交巡警平台到每一个出口的距离，这样就有了一个
80?17的距离矩阵。
然后我们开始对这80个交巡警平台进行任务分配，一个出口分一个平台，使每个平台到出口的距离之和最短。这个即匈牙利算法中的任务匹配问题了。
这样问题便得到了解决。
五、模型建立及求解
5.1模型的准备
1.为了便于分析，以及给读者更直观的理解，根据附件2中的“全市交通节
点数据”可以画出下图：
图1 全市交通图
2
2.将上述图转化为邻接矩阵，把数据存储在邻接矩阵中，如下矩阵所示
?a11??a21A?????a?582?1a12a22a1?5822??a2?582??， ??a582?582??a582?2其中aij表示i,j两路口节点标号之间直达的距离，当i,j两路口节点标号之间有连接两点的路线时，aij记为两者之间的距离，若没有有连接两点的直达的路线，则记为?。
5.2 问题模型建立及求解： 5.2.1 模型的建立
由上面的邻接矩阵A，根据Floyd算法可以算出任意两个路口节点标号之间的最短距离，得到如下的距离矩阵
?d11??d21D?????d?582?1d12d22d1?582??d2?582?? ??d582?582??d582?2
其中dij表示从i路口到j路口的最短距离。
根据交巡警平台路口编号以及出口位置的路口编号，我们从D中提取出交巡
警平台与各个出口之间的距离矩阵distance：
b12?b11?b22?b21distance?????b?80?1b80?2b1?17??b2?17?? ??b80?17??
为方便叙述，我们在此引入0?1矩阵X，与上面的distance矩阵具有相同的大小，X即为分配矩阵。
?x11??x21X?????x?80?1x12x22x1?17??x2?17?? ??x80?17??x80?23