服务平台的设置与调度7Word文档格式.docx

1、本文将问题转化为：从20个服务平台中选出13个对13条交通要道进行封锁，且这13个平台所用的时间要最小的规划问题。本文引入0-1变量表示一个巡警服务台是否封锁一条交通要道，从而建立这个问题的0-1规划模型，并借助数学软件LINGO进行求解。（3）根据问题一（1）的分配方案可知：当标号为39、61、28、29、38、92的路口有案件发生时，标号为2、7、15、16、20的巡警服务台的出警时间将超过3min，即出警时间过长。 此时每个巡警服务台的工作量分别为：按问题一（1）的分配方案20个巡警服务台的工作量平台标号12345678910工作量10.38.35.66.69.72.58.21.6111

2、213141516171819204.68.52.1.3.85.36.13.410.7此时巡警服务台的工作量不均衡度为8.4314。由1），2）可知现有巡警服务台的工作量极其不均衡且有些地方出警时间过长。针上述问题题目要求再增加25个巡警服务台来解决上述问题。本文首先建立集合覆盖的0-1规划模型，然后利用MATLAB对模型进行求解，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加巡警服务台的数目与位置。问题二：（1）本文定义了两个评价原则：原则一：巡警能在3min之内到达案发路口 根据以上两个原则对该城区现有巡警服务台的设置方案的合理性进行评价。 若现有巡警服务台的设置不

3、合理，本文则提出方案对全城的巡警服务台设置进行优化：方案：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；（2）当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台警力围堵嫌疑犯。因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌疑犯逃跑方向，所以此问题可转化为以下模型：对于任意时间，嫌疑犯驾车逃跑的最大范围为：在时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，记为，将的边界点集记为。所谓最快围堵方案，即寻找一个最短时间，适当的调配巡警警力，使其在时间内能够到达边界点，这样嫌疑犯就被控制在区域中，

4、此时嫌疑犯将无法逃脱。三符号说明Cij：巡警平台i与路口j之间的最短距离Cj：j号巡警平台的工作量，其中j=124tij =I：C类路口的集合：平均工作量工作量不均衡度i路口的发案次数，其中i=1,292Q：需要增加巡警服务台的路口的候选集Y：嫌疑人最大逃跑范围的边缘节点的集合X：所有巡警平台的集合E：X中一点到Y中一点的最短路径的集合t：接到报案后时间的增量四模型假设1.每个巡警服务平台的服务能力相同。2.每个路口只由一个巡警平台负责。3.每个巡警平台至少负责一个路口。4.巡警按最短路劲前往案发路口。5.案件都发生在路口。6每个巡警平台辖区内所有路口案发率之和为该平台一天的工作量。7.逃犯的

5、逃跑速度与警车速度相同。8.以所有巡警平台工作量的方差，作为工作量不均衡度。五模型建立和求解问题一问题1.1问题1.1中，要将92个路口纳入20个交巡警平台的管辖范围。必须保证，每个路口都在一个交巡警平台的管辖范围内。同时，每个路口所属的交巡警平台，要是所有20个平台中到该路口距离最短的。如果一路口，在其3km路程内，仅有一个巡警平台，称其为A类路口。如果一路口，在其3km路程内，有多个巡警平台，称其为B类路口，将它分到最近的平台。如果一路口，在其3km路程内，没有巡警平台，称其为C类路口，将它分到最近的平台。 根据以上要求，分别为92个路口找到距离最短的交巡警平台，这是典型的最短路问题。最短

6、路是图论研究中的一个经典算法问题。最短路问题, 一般来说就是从给定的网络中找出任意两点之间距离最短的一条路径。求最短路有的一种主要方法是求图上任意两点之间最短距离的Floyd- Warshall 算法。根据Floyd- Warshall 算法及其在C语言程序上的运用【1】， 编写C语言程序（见附录1），进行求解，得出分配方案如下表（表1）：交巡警服务平台管辖范围表服务平台管辖路口1，67，68，69，71，73，74，75，76，7811，26，272，39，40，43，44，70，7212，253，54，55，65，6613，21，22，23，244，52，56，57，60，62，63，64

7、5，49，50，51，5315，28，296，58，5916，36，37，387，30，32，47，48，6117，41，428，33，4618，80，81，82，839，31，34，35，4519，77，7920，84，85，86，87，88，89，90，91，92表1问题1.2问题1.2中，要对20个巡警平台进行调度，封锁13个路口。要使得实现全封锁的时间最短。这是图论中的指派问题【2】。指派问题可以看做是0-1规划问题。 记20个巡警平台分别为i=1,220；记13个需要封锁的路口按标号从小到大的顺序，分别为j=113.，记巡警平台i与路口j之间的最短距离为Cij。引入0-1变量xij，

8、如果平台i对路口j进行封锁，记xij=1，否则记xij=0。目标函数： 其中i=120，j=113。约束条件：每个路口都要有一个平台对其封锁，即：，j=113 每个平台最多封锁一个路口，即： ， i=120综上所述，此问题的优化模型为：利用C语言程序和Lingo进行编程求解，程序见附录2，过程如下：1根据Floyd-Warshall算法，编写C程序对Cij求解，得到20个巡警平台到13个路口的最短距离Cij。2.将上一步中得到的数据导入Lingo中，根据已知的目标函数和约束条件，用Lingo求的最优解。Lingo解得的结果表明，实现全封锁的最短用时为8.0155分钟，具体的平台调度方案如下表（

9、表2）：调度方案表路口标号21222324用时（min）3.79146.74176.02563.26507.70790.5003.59162829303848624.75188.01553.21355.88092.47586.4489表2问题1.31、 初步分配方案的确定同样运用问题一中的方法可以得到：距离C类各个路口小于3km的路口集合，如下表（表3）：距离C类各个路口小于3km的路口集合表C类路口标号3992集合28,2938,39,4048,6187,88,89,90,91,92表3对上表中的6个集合求并，得到需要增加巡警服务台的路口的候选集Q=28,29,38,39,40,48,61,

10、87,88,89,90。本文将要在候选集Q中选择2-5个路口设置巡警服务台，使需求集I=28,29,38,39,61,92中的所有路口在案发生时均有巡警在3min之内能赶到。集合覆盖模型的建立首先，建立覆盖矩阵T613 ，其元素：i=1,26,j=1,213。其次，建立集合覆盖模型：满足：.其中：最后，利用MATLAB运用搜索法得到：至少从候选集Q中选出4个路口来设置巡警服务台，才能解决出警时间过长的问题。此时共有48种可能的分配方案。分别如下表（表4）所示：48种分配方案表28,38,48,8728,38,61,8728,39,48,8728,39,61,8729,38,48,8729,38

11、,61,8729,39,48,8729,39,61,8728,38,48,8828,38,61,8828,39,48,8828,39,61,8829,38,48,8829,38,61,8829,39,48,8829,39,61,8828,38,48,8928,38,61,8928,39,48,8928,39,61,8929,38,48,8929,38,61,8929,39,48,8929,39,61,8928,38,48,9028,38,61,9028,39,48,9028,39,61,9029,38,48,9029,38,61,9029,39,48,9029,39,61,9028,38,48

12、,9128,38,61,9128,39,48,9128,39,61,9129,38,48,9129,38,61,9129,39,48,9129,39,61,9128,38,48,9228,38,61,9228,39,48,9228,39,61，9229,38,48,9229,38,61，9229,39,48,9229,39,61，92表42、最终分配方案的确定 1） 为每种方案中的24个巡警服务台分配管辖范围。步骤一：同样按照问题一（1）中的求解过程1和2可得到有24个巡警服务台的集合覆盖矩阵K9224。步骤二：此时由上述集合覆盖矩阵可将城区A的92个路口分为A、B两类：A类：已只由一个巡警服

13、务台进行管辖；B类：可被多个巡警服务台进行管辖；将A类中的路口直接分配给对其进行管辖的唯一的巡警服务台。对于B类的路口，在综合距离最近与工作量平均的情况下来进行分配。首先选择距离路口i最近的巡警服务台j（j=1,224），然后利用公式计算巡警服务台j的工作量，若则将路口i分配给巡警服务台j管辖，否则选择次短距离的巡警服务台进行同样考虑。最后得到每种分配方案中24个巡警服务台的管辖范围。步骤三：根据平局工作量公式与工作量不均衡度公式，利用MATLAB分别对48中分配方案中巡警服务台的工作量不均衡度进行计算。得到下表（表5）：48中分配方案对应的工作量不均衡度表3.48904.71943.0742

14、4.30464.64904.24983.49164.66723.07684.2524表5由表中数据可得：最小不均衡度为3.0742，有8种分配方案。如下表（表6）所示：满足题目一（3）要求的4个巡警服务台的路口标号表表6本文仅给出其中方案一（在路口标号为28、39、48、87处增加巡警服务台）对应的城区A的24个巡警服务台的管辖范围（表7）与每个巡警服务台对应的工作量，如下表（表8）：方案一中24个巡警服务台的管辖范围表服务台管辖范围1,67,68,69,7113,21,22,23,242,43,44,70,7254,55,3,65，15,4,57,60,62,6316,36,3753,5,4

15、9,50,5141,17,426,52,56,58,5918,74,80,81,827,30,3219,75,76,77,788,33,45,46，20,85,86,90,91,9,31,34,3528,2938,39,4011,26,2761,67,4812,258792,83,83,87,88表7方案一中每个巡警服务台对应的平均工作量表6.56.46.85.1875不均衡度3.86.32.74.33.6表8 问题二问题2.1根据题目中提到的信息，我们从两个方面对现有设置方案进行评价：巡警服务台的工作量均衡度尽量小 依据问题分析中的两个评价原则，分别对现有巡警服务台的设置方案进行评价。讨论现

16、有设置方案是否满足原则一 ：全城六区A，B，C，D，E，F现有个80巡警服务台、582个路口，运用问题一（1）中的算法，得到全城C类路口的数目与位置，如下表（表9）：C类路口的位置标号6112212312415115215318319920020120220320520620720820921021523823924024724825125225325725926126226326426826928528628728829930030130230330431231331431531631731831932933033133233633733934436236937037138738838939

17、0391392393395407408409411412413417418419420438439443445446451452455458459464469471474486487505506507508509510512513514515516517518519522523524525526527529533540541559560561566569574575578582表9计算结果表明：582个路口中共有138个C类路口，即在案发时巡警不能在3min到达此路口，约占全城总路口数的1/4。讨论现有设置方案是否满足原则二 ：运用问题一（3）中的方法，为每个巡警服务台分配管辖范围，并计算工作

18、量及巡警服务台的工作不均衡度。结果如下（表10）：现有配置下每个巡警服务台的工作量巡警服务台931784.53782.69411.31793797.4959.518038017.19611.51816.23819718212.23829812.13208.738340.4993218341003224.43859.11663234.23861673247.947513.11684.73252.24761693265.147739.617012.693277.64787.217112.43286.747912.91723725.248028.41733734.148117410.13745.54826.