摘 要：文章借鉴2011年国赛B题对交巡警平台的设置进行建模和研究，并推广应用到众多关于调度类问题领域。用Matlab建立描述交巡警平台网络图的权矩阵，采用求最短路的Floyd算法求出任意两节点的最短路径，构建最佳路径阵和距离矩阵，并分别建立各问题的数学模型，完成交巡警服务平台的设置与调度。
　　关键词：Floyd算法；双目标优化；0-1整数规划
　　1 交巡警平台管辖范围划分问题
　　为了尽量能在3分钟内有交巡警到达事发地，采用Floyd算法确定了任意两节点间的最短距离，找出距离节点最近的平台，利用Matlab软件得出合理的交巡警平台管辖范围。
　　每一個节点到各个平台的最短距离为，到最近平台的距离为，我们建立平台的管辖范围分配模型，见公式1、2。
　　使用Matlab中scatter函数绘制出散点图，并将标号标记在图上。构建一个 的距离矩阵。然后根据附件2全市交通路口的路线给出的路线起点（节点）标号和路线终点标号计算出各条路线的距离。将这些距离填入起点标号和终点标号对应的位置，得到邻接矩阵。 然后用Floyd算法对距离矩阵进行计算每一个节点到各个平台的距离，并找出92个节点到其最近的平台的距离。将节点分配给距离其最近的平台，并将最近距离与3km进行比较，得到判断结果。
　　对13条交通要道实现快速全封锁
　　之前得出的92个节点对应的20个平台数据矩阵中，找出需要封锁的13个节点和对应的20个平台组成矩阵 ，采用0-1整数规划模型建立封锁方案模型，在矩阵 中，搜索满足目标函数的元素，求得最优解，见公式3。
　　我们可以得出结论如下：3→38，4→62，5→30，6→16，7→29，8→48，10→12，11→23，12→24，13→22，14→21，15→28，16→14（前者为交巡警平台编号，后者为出入A区的路口编号）。
　　新增平台数量及位置
　　将节点发案率视为工作量，一个平台到最远节点的时间作为最长出警时间。首先对目标函数和约束条件的确定及含义一一分析，最后建立关于目标函数、约束条件的优化模型，以确定增设平台个数和位置。
　　将建立最少数量的交巡警平台作为目标函数，由Lingo可以得出结论，需要增加四个交巡警平台，再根据Lingo程序计算出这四个交巡警平台的具体位置，所以得出的最终结论如下，应该增加28，39，48，87这四个交巡警平台。
　　该市现有的交巡警服务平台设置方案的合理性分析
　　以出警超时的节点数少和各平台工作量均衡为评价标准，并考虑重新分配和设置新的交巡警平台。类似A区的做法，对B、C、D、E、F各区进行划分平台的管辖范围，再筛选出不合理的平台，对明显不合理的地方求解出解决方案，求得具体的优化配置方案，主要实现了对服务平台的管辖节点比例的优化。
　　将平台所管辖的所有节点的发案率视为此平台的工作量，将所有平台的工作量求取方差，作为考虑工作量是否均衡的指标。将一个平台到最远节点的时间作为最长出警时间。因此以方差最小，最长出警时间最短建立双目标优化模型，以出警超时的节点数少和各平台工作量均衡为评（下转第页）（上接第页）价标准，并考虑重新分配和设置新的交巡警平台，用Lingo进行求解。
　　最佳围堵方案
　　为了解决在P（第32个节点）犯案的犯罪嫌疑人围堵问题，我们使用Matlab进行动态仿真，借用图论中“割点”概念，调度全市警力尽快占据“割点”来在最短时间内达到将犯罪嫌疑人围堵在一个固定的区域。
　　为了快速搜捕嫌疑犯，需给出调度全市交巡警服务平台警力资源的最佳围堵方案。该问题等价于80个交巡警服务平台对17个出口的围堵问题，为了尽快进行围堵，需要让围堵时所行使的路线长度总和最小化，从而可建立出如下0-1规划模型：
　　其中表示第i个交巡警服务平台如果封锁第j个出口，则第i个交巡警服务平台到第j个出口之间的距离再加上3分钟的行驶时间3000m后的距离要小于等于案发现场到第j个出口的距离。
　　模型的评价及推广 ：能够合理的分配交巡警平台的管辖范围，是各个平台的工作效率能达到最大化，并及时地应对突发状况的发生，得到人力财力物力的最优分配。结合模型特点，该模型也可运用到其他最优选址问题中去，比如消防站、医院、超市等一些重要公共设施的选址问题、重大生产事故应急援救、公共交通的最优路径问题等。同时也可参考该模型算法，将其模型拓展在其他领域。