B题： 交巡警服务平台的设置与调度
摘要
本题要根据实际情况分配交巡警平台的管辖范围，调度警务资源，合理设置交巡警平台的等问题。我们本着两个原则来设置管辖平台：1.尽可能使所有路口都能在3分钟内赶到；2.使平台间工作量较为平均。 本着最快封锁住全城，最快围堵住嫌犯的原则来调度警务资源。
针对问题一第一小问的分配管辖问题，我们用图论的知识将实际地图转化为无向图，再用matlab求出每两个路口间的最短路径，最后用c++程序把每个路口分配到距离其最近的平台管辖范围内。分配结果见正文，有6个路口：28、29、38、39、61、92无法在3分钟内赶到。
针对问题一第二小问的调度警员封锁路口问题，为了最快封锁完全区，封锁时间取决于交警最后达到的一个路口所花费的时间决定，用图论中的最大最小化模型，求出到达最远路口的最短时间。将原来的双目标最大最小化问题转化为单目标最优化问题，利用0-1规划，约束13个路口和13个不同的平台一一对应，求出所有交警在路途上花费的总时长最短，用lingo得到调度方案，封锁全城需要时间8.0155分钟。
下个路口见 mp3
出入口标号
12
14
16
21
22
23
24
28
29
30
38
48
62
派往的平台
12
16
9
14
10
13
11
15
7
8
2
5
4
针对问题一第三小问，我们考虑到第一小问分配结果有6个路口28、29、38、39、61、92无法在3分钟内赶到。所以我们以3分钟内到达6个路口为目标得到72种添加方法，在这些方案中，用平台间工作量不均衡度（即各个平台的工作量方差）决定最合理的增添方案。
针对问题二第一小问，我们看：1.所有路口是否能在3分钟内赶到；2.平台间工作量是否较为平均，来评判该城区的平台设置是否合理，发现有138个路口无法在3分钟内赶到，对于582个路口而言快达到四分之一了，并且平台之间的工作量差异巨大可以看出严重不合理。我们采用自己的方法用最大集合覆盖模型在平台数量不变的基础上重新设置平台。
针对问题五，我们对动态围堵逃犯的问题，我们先算出嫌犯分钟内可能到达的路口合集，再让警方围堵住嫌犯可能到达的路口的毗邻路口，如果无法围堵，扩大范围，围堵下一圈可能到达的路口，通过lingo算出能在11.28分钟内完成围堵，方案见正文。
关键字：0-1规划，图论，最大路径最小值，集合模型
一．问题重述：
  “有困难警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、
服务众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
  （1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
  （2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二.符号说明：
：表示路口和路口之间的权值。
：表示第个交警平台到第个出入口的最短路径长。
：表示0-1变量，表示第个交警平台调度去第个出入口，表示不调度。
：表示交警达到最后一个出入口经过的路程。
：表示0-1变量，表示第个路口分配给第个交巡警平台，表示第个路口不分配给第个交巡警平台。
：表示第个路口的发案率。
：表示平台的工作量，为平台所管辖的所有路口的案发率之和
：表示工作量不均衡度，为得到的各个平台工作量方差和
三.条件假设：
  1.如果案件发生在道路之中，则案件归离事发点最近的路口所属的服务平台管辖。
  2.每个服务平台最少管辖一个路口。
  3.各条道路均不是单行线，均可以双向行驶。
  4.不考虑每条道路上的拥挤情况，出警分配根据巡警平台和案发地点的距离决定。
  5.考虑到出警时是特殊情况，出警时警车车速稳定在60千米每小时。
  6.假设每条道路均为直线，路程长度按照直线距离推算。
  7.嫌犯的逃跑速度和警车逃跑速度一样都为60千米每小时。
 
四.模型建立与求解：
4.1.1问题一的分析
问题一的第一小问给出了市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图和相关数据，让我们根据警力资源分配管辖范围。我们先对已知图和数据进行预处理，并且根据图论知识，求出每段路的路程，并求出每两个路口的最短距离，将其转化为权重为路段长度的无向图，然后将每个路口划分到距离其最近的交巡警服务平台的管辖范围里。
    问题一的第二小问让我们对特殊案件发生时进行路口封锁处理。首先，假设所有交警同时从平台出发，13条交通要道全部封锁所需的时间，由所有出入口中，交警最后达到的一个所
花费的时间决定，所以应当使得交警达到最后一个出入口经过路程最短，但是同时又应当使得所有交警在路途上花费时间尽量少。因此，我们考虑使用最大最小化问题的0-1规划方法，用lingo编程解决。
    第三小问要针对出警时间过长和平台工作量不均衡的问题增加2-5个平台。针对出警时间过长，我们考虑到第一小问分配结果遗留了6个路口28、29、38、39、61、92无法在3分钟内赶到，我们要让所有路口能在3分钟内赶到，确定至少要增添4个平台。用c++程序发现有72种增添平台方案，再定义工作量不均衡度=各个平台工作量方差和，求出不均衡度最小的平台增添方案。得到结果。
4.1.2 数据、图像预处理
  1.每条路段长度的求解
    根据附件给出的数据，可以对每个路口进行标号，A区共有92个路口，其中20个路口处设置了交巡警服务平台，13个路口是出入该区的路口节点。附件中给出了每个路口的横纵坐标值和哪两个路口之间存在道路，根据C++程序（见附录）可以得到每条道路的距离，部分道路距离可见下表。
表1-1 部分A区道路长度
路线起点(节点）标号
路线终点（节点）标号
相距距离（千米）
1
75
0.930054
1
78
0.640312
2
44
0.948683
3
45
4.24647
3
65
1.52398
4
39
4.56098
4
63
1.03078
5
49
0.5
5
50
0.848528
6
59
1.60312
7
32
1.14018
7
47
1.28062
8
9
1.15974
8
47
2.07966
9
35
0.424264
10
34
4.92164
11
22
3.26956
11
26
0.9
12
25
1.78885
2.转换为无向图
  根据图论的知识，该题中，市区的交通网络图可以转化成一个无向图，权重为路程长度。假设表示路口和路口之间的权值，可以得到：