使得A城区各服务平台的工作量得到较好的均衡，出警时间及时。 7.1 模型的分析
要在现有交巡警服务平台的基础上对A区增加平台以使得工作量均衡并尽可能减少出警时间，为了合理分配增加服务台的数量和位置，就要从服务平台覆盖率、各服务台管辖路口节点的工作量均衡度和出警时间三个方面对服务平台数量个位置进行优化分析。 7.2 模型的建立
工作量可以通过该平台管辖范围内发案率的累积量来评判，工作量均衡则可以通过各平台到所管辖路口节点的距离来衡量。为了保证及时出警，还需要平台到路口节点的距离来限制约束。此外增加服务平台必然存在一定的成本，增加的平台越多成本也将越高，在尽可能小的成本条件下，我们考虑在满足服务平台覆盖率、各平台管辖路口节点的工作量、及时出警的条件下增加尽量少的交警服务平台，在以此作为目标函数，建立优化决策模型。 7.2.1 确定目标函数
考虑到增加服务平台存在一定的成本，增加的平台越多成本也将越高，在尽可能小的成本条件下，我们考虑在满足服务平台覆盖率、各平台管辖路口节点的工作量、及时出警的条件下增加尽量少的交警服务平台，在以此作为边界条件，建立最优的平台建设模型，即
min?yi
i?1927.2.2 确定约束条件
（1）交巡警服务平台需在3分钟内到达所管辖的路口节点，也即平台到路口节点的距离（图上距离）不超过30mm
xijdij?30
（2）A城区交巡警服务平台必须至少管辖一个路口节点
?xj?192ij?1
（3）A城区中92个路口节点必须有一个对应的服务平台对其管辖
?xi?19292ij?1
（4）在A城区现有的20个服务平台的基础上再增加2至5个平台，所以A城区总的服务平台最少不低于22个，最多不多于25个
22??yi?25
i?1（5）xij表示第i个交巡警服务平台是否管辖第j个路口节点的决策变量，取值为1，即第i个交巡警服务平台管辖第j个路口节点；取值0则不管辖，因此有
11
?1，节点j由平台i管辖 xij??0，否则?（6）yi 表示是否在第i个节点处设立为交巡警服务平台的决策变量，取值为1 时表示在第i个节点处设立交巡警服务平台；取值为0时，则不在第i个节点设立交巡警。
?1，设置节点i为交警服务平台 yi???0，否则综上所述，问题三的目标函数
min?yi
i?192?xijdij?30?92?x?1ij??j?1?92? s..t??xij?1?i?192??22??yi?25i?1??xij?(0,1),yi?(0,1)?7.3 模型的求解
用Lingo（编程代码见附录八）对问题三中为均衡各交巡警服务平台的工作量和出警时间所建的新增2-5个平台的优化决策模型进行求解，最优的方案为新增4个交警服务平台，分别为节点28、40、48、89。如何使这2个交巡警服务平台的工作量和出警时间尽可能均衡，我们通过数据处理中最短距离矩阵和各节点的案发率的数据发现，
（1）对于节点28到其他节点的距离除了29节点小于30km，其他距离全部大于30km，对于29节点同样如此，为了满足所有节点到平台时间不超过3分钟这一约束条件，因此28、29节点必须设有一个平台，故在案发率的条件约束下设28节点为交警服务平台。
（2）对于节点38来说，除了39、40节点与其距离小于30km以外，其他节点到该节点的距离均大于30km，同样，对于39、40节点来说同样如此，因此38、39、40这3个节点中必须要设一个交警服务平台，故在其他条件约束下设38节点为交警服务平台。
（3）对于节点48来说，除了本身，与47、61节点距离小于30km，考虑案发率的约束，故设48节点为交警服务平台。
（4）对于节点89来说，除了本身，还与84、87、88、89、90、91、92这6个节点距离小于30km，综合考虑案发率及其相互间的距离约束，设89节点为交警服务平台。
综合上面的分析得到增设4个交巡警服务平台后A城区24个服务平台对应所管辖的路口节点的情况如下表
12
表7-1：24个服务平台及其所管辖的节点
服务平台 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 40 48 89 2 43 44 70 72 3 54 55 65 66 4 57 60 62 63 所管辖的路口节点 1 67 68 69 71 73 74 75 76 77 78 5 49 50 51 52 53 56 58 59 6 7 30 32 8 33 46 9 31 34 35 45 10 11 26 27 12 25 13 21 22 23 24 14 15 16 17 21 18 80 81 82 83 19 77 79 20 85 86 28 29 38 39 40 47 48 61 84 87 88 89 90 91 92 从上表中可以发现，新增了4个交警服务平台，分别为节点28、40、48、89。此时在对A城区交巡警服务平台工作量和出警时间的约束下，前20个交巡警服务平台所管辖的路口节点较问题一中也有所优化调动。 7.4 问题三的结果分析
为了检验所增的节点数量和所管辖路口节点的合理性，需要进一步统计分析交巡警服务平台对所管辖节点工作量是否均衡，对此统计了新分配的交巡警服务平台的工作量的情况。
表7-2：增设平台后对应管辖的节点的案发率
交巡警服务平台 1 2 3 4 5 6 7
13
平台管辖节点的报案数 10.3 6.6 5.6 6.6 9.7 2.5 6.0 8 9 10 11 12 13 14 15 16 17 18 19 20 28 40 48 89 5.0 8.2 1.6 4.6 4.0 8.5 2.5 2.1 3.8 5.3 6.1 3.4 4.5 2.7 4.3 3.6 7.0 由表可知，新增节点28、40、48、89这4个服务平台后A城区24个服务平台的案发数，也即这24个交巡警服务平台的工作量，为了更直观的看到新增设这4个服务平台带来的优化效果，我们与问题一中只有20个交巡警服务平台就发案率做了比较分析，效果见下图
图7-1：增设平台前后工作量的比较图
由7-1增设前后案发率的数据点折线图可知，增设了4个平台后各交巡警的工作量较增设平台前各交巡警服务平台的工作量波动幅度小，说明问题三中增设的28、40、48、89这4个路口节点和这24个服务平台所管辖的路口节点较好的实现了A城区各平台工作量的均衡。
8 问题四的解答
分别派出A城区第1和第11两个交巡警服务平台的两支警力进行城区A各路口节点的巡逻执勤任务，在此需要设计最优的路径方案，使得这两支警力在巡逻完规定的路口节点后返回各自的平台的距离最优。可见这是在有限空间内对两个目标函数设计最优的路径问题，对此可对应建立模拟退火算法的模型。
14
8.1 模型的分析
8.1.1 模拟退火算法的简介
模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983年S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能。
8.1.2 模拟退火算法的原理
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。
用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 8.1.3 模拟退火算法步骤
模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火算法的基本步骤：
(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L
(2)对k=1，……，L做第(3)至第6步： (3)产生新解S′
(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
(5)若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
(6)如果满足终止条件则输出当前解作为最优解，结束程序。 终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7)T逐渐减少，且T->0，然后转第2步。
综上可知模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火算法能够较好的运用在本文对平台1和11的警力最优巡逻的路径选择上。 8.2 模型的建立
15
