nm?z???dijXij?minXj?1i?1??21n?m??Xij??i??????min???Xn?1j?1?i?1???minmaxdX?X1?i?mijij1?j?n??
其中，ij表示第i个路口到第j个平台的的最短距离，该距离可由Floyd算法求出（见
附录一 表格1）。
然后确定了两个约束条件，一是当每个路口节点有突发事件发生时，有且只有一个服务平台的交巡警到达现场处理事件；二是要求每一个交巡警服务平台至少管辖一个路口节点。
?n??Xij?1,i?1,2,?,m?j?1?m??Xij?1,j?1,2,?,ns..t?i?1??1,当路口i由平台j管辖时，?Xij??且Xij?1,当i?j时0，其他，????i?1,2,?,m;j?1,2,?,n.
第三个目标有最小值，并且该量可由模型直接计算出来（程序见附录一 lingo1），而且在比较优的可行解中为常数，所以不必作为优化目标，可以仅仅作为简单的约束条件。于是问题就转化为求下面的模型二。 模型二：
其相应目标函数及其约束条件如下：
nm?z???dijXij?minXj?1i?1??2?1n?m???min???Xij??i????Xn?1j?1?i?1??d?minmaxdijXij?i?m?X11?j?n?n?X?1,i?1,2,?,mij??j?1s..t??m??Xij?1,j?1,2,?,n?i?1?Xij??0,1?,且Xij?1,当i?j时. i?1,2,?,m;j?1,2,?,n?
3、 模型求解
该问题需要先根据所给数据用matlab编程求出A区所有节点的邻接矩阵A0和其加权邻接矩阵A，其中当两节点有路相连时，权值赋为两点的直接距离；当两1（见附录一 表二）点相同时为其赋值为0；当两节点不直接相连时，权值赋为inf。
根据floyd算法通过matlab求出20个交巡警服务平台到92个路口节点的最短距离矩阵D92?20（相应算法与结果见附录一 表三）。 根据目标函数及其约束条件，运用LINGO求解（其相应程序与结果见附录一 表四）。但由于0—1整数变量比较多，所以在求解时需要的时间比较长。该程序是一个双目标规划问题，而在LINGO中无法直接求解，因此我们对目标函数做相应的加权处理，将其转化成一
5
个单目标规划问题。根据文献以及对问题的分析与计算，我们将第一个目标函数的权值赋为0.995，将第二个目标函数赋为0.005。再用LINGO进行求解。
利用LINGO求解得到了各平台的管辖范围，根据结果分析可知，在保证工作量均衡的条件下，该区内有6个盲点（3分钟之内无法到达的点）28、29、38、39、61、92。因此，只能根据邻近原则进行分配。从而得出管辖范围的分配结果如表1-1，其中红色数字表示服务盲点的节点编号。
表1-1 A区服务平台管辖范围表 平台 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 67 40 44 57 49 47 30 32 31 26 25 22 21 28 36 41 81 76 85 68 43 54 60 50 58 48 33 34 27 23 29 37 42 82 77 86 管辖范围 69 70 55 62 51 59 61 46 35 24 38 83 78 87 71 72 65 63 52 45 39 84 79 88 73 66 64 53 89 80 90 74 56 91 75 92 【3】
根据该最优解，通过LINGO可知道其全部调度的距离总和、平台的工作量的标准差及其最大出警时间最大的三个指标所对应的值，如表1-2
表1-2 A区平台设置各指标值
最大出警时间 5.7min 平台工作量的标准差 1.8417 全部调度的距离总和 1039.515 各平台最大出警时间和工作量见表1-3. 表1-3 各服务平台的最大出警时间和工作量
服务平台 最大出警时间 工作量 服务平台 最大出警时间 工作量 1 1.62 8.4 11 1.64 4.6 2 1.91 7.2 12 1.79 4 3 2.27 6.9 13 2.39 7.1 4 1.94 6.6 14 3.26 3.9 5 2.45 8.4 15 5.7 4.8 6 2.38 6.1 16 3.71 6.4 7 4.19 5.3 17 0.98 5.3 8 1.34 6.6 18 1.82 7.7 9 2.06 8.2 19 6.1 10 0 1.6 20 9.1 1.43 3.6
6
问题二：全封锁的调度优化模型
1、 模型建立
根据对问题的分析，要实现对要道的快速全封锁，关键在于控制封锁要道所需时间最长的服务平台的出警时间，使其达到最小值。
设问题的决策变量为
Yij是0-1变量，即
?1,j平台的警力出警到i出口Yij??,
?0,其他其中
模型一：1-1优化匹配模型：
从实际出发，如果被封锁的路口其本身就有交巡警服务平台，则该交巡警服务平台便可直接封锁该路口。因此我们需要考虑增加以下约束条件：
Yij?0或1,且Yjj?1,i?1,2,?,n;j?1,2,?,p 然后确定了两个约束条件，一是当每个路口节点有突发事件发生时，有且只有一个服务平台的交巡警到达现场处理事件；二是一个平台的警力最多封锁一个路口。
i?1,?,p;j?1,?,n
??Yij?1,i?1,?,p?js..t???Yij?1,j?1,?,n?i
第一步：
首先以最大封锁距离最小作为目标，作下面的0-1整数规划问题：
minz?maxdijYij?XYi,j????Yij?1,i?1,?,p?j ?s..t??Yij?1,j?1,?,n?i?Yij?0或1,且Yjj?1,i?1,2,?,n;j?1,2,?,p?由该模型所得到的最优解并唯一，这些组解的共同特点是最远的调度距离都是由平台
j0到出口i0的距离。所以完成该去全封锁的最短时间就由此决定，即
第二步：
以总调度距离最短作为目标函数，对除平台步做0—1规划，模型为：
t?di0j0v 。
j0 和出口i0以外的出口和交巡警平台进一
minz1???dijYiji?1j?1p?1n?1?max(dijYij)?di0j0?1?i?p?1
??Yij?1,i?1,?,p?1?s..t?j??Yij?1,j?1,?,n?1?i?Y??0,1?,i?1,2,?,n;j?1,2,?,p?ijz1表示除平台j0 和出口i0以外的总调度距离，p?1表示除平台j0以外的平台
i总数，n?1表示除出口0以外的出口总数。
其中，
7
模型二：模型一的改进方案
在模型一的前提下，不再考虑平台本身就是封锁路口的约束。这样既保证了最长封锁时间最短，又保证了总封锁时间最短。改进模型一的第一步如下：
minz?max?dijYij??XYi,j??Yij?1,i?1,?,p?j ?s..t??Yij?1,j?1,?,n?i?Yij??0,1?,i?1,2,?,n;j?1,2,?,p?第二步同模型一，用LINGO求解即可。 2、 模型求解
首先，利用matlab在模型一求得的距离矩阵D92?20中提取20个交巡警平台到13个出口12、14、16、21、22、23、24、28、29、30、38、48、62的距离矩阵D13?20。 然后，利用LINGO编程分别对模型一、二求解。
模型一的实现首先将12、14、16对应的出口和平台除去，然后利用LINGO求解（程序见附录二 表一）。第一步结果见表2.1：
表2-1：第一步封锁求解（考虑出口本身就是平台）
封锁平封锁路台 口 A1 A3 A4 A5 38 30 62 28 封锁时间 5.8809 8.1995 0.35 11.369 封锁平封锁路封锁平封锁路封锁时间 台 口 台 口 A9 A10 A11 A12 21 22 24 12 11.5392 7.7079 3.8053 0 A14 A15 A16 14 29 16 封锁时间 0 5.7005 0 A7 48 1.2902 A13 23 0.5 实现全封锁的最长时间为11.539分钟，由平台9封锁出口21决定。现将平台9和出口21除去，再利用LINGO求解（程序见附录二 表二）。第二步结果见表2.2：
表2-2：A区全封锁调度（考虑出口本身就是平台）
封锁平台 封锁路口 封锁时间 封锁平台 封锁路口 封锁时间 封锁平台 封锁路口 封锁时间 A2 A4 A5 A7 38 62 48 30 3.9822 0.35 2.4758 5.831 A10 A11 A12 A13 24 22 12 23 7.7079 3.8053 0 0.5 A15 A16 A9 28 16 21 4.7518 0 11.5392 A8 29 10.4932 A14 14 0 实现全封锁的最长时间为11.539分钟，总平均封锁时间为3.553分钟。 模型二的实现直接利用LINGO编程求解（程序见附录二 表三）。第一步结果如表2.3：
表2-3：第一步封锁求解（不考虑出口本身就是平台）
封锁平台 封锁路口 封锁时间 封锁平台 封锁路口 封锁时间 封锁平台 封锁路口 封锁时间 A2 A4 A5 A7 A8
16 62 48 29 30 7.3881 0.35 2.4758 8.0155 3.0608 A10 A11 A12 A13 A14 22 24 12 23 21 8
7.7079 3.8053 0 0.5 3.265 A15 A16 A17 28 14 38 4.7518 6.7417 4.7557
相关推荐：
loading