《数学建模2011b优秀论文》由会员分享，可在线阅读，更多相关《数学建模2011b优秀论文（17页珍藏版）》请在金锄头文库上搜索。
1、交巡警服务平台的设置与调度摘要本文针对交巡警平台的设置与调度进行建模。首先，对问题给定的数据进行预处理，分别到六个区路口的距离加权邻接矩阵以及整个市的邻接矩阵，对邻接矩阵应用FLOYD算法得到路口间的最短距离矩阵以及。对问题一，在考虑区20个交巡警平台的工作量尽量均衡的前提下，选取3分钟内不可达的路口个数最小作为目标函数建立规划模型，并用lingo软件得到20个交巡警平台的管辖范围和3分钟内不可达的6个路口编号。对问题二，首先假设交巡警平台警力要到达指定路口时选择最短路径，提取中20个交巡警平台到13个交通要道的最短路径矩阵。在保证每个交通要道都要封锁的前提下，以最长封锁时间最小为目标函数，建
2、立规划模型，最终得到最优围堵方案，时间约为8分钟。对问题三，以每个交巡警平台管辖路口发案率之和作为该平台工作量的衡量指标，在最长出警时间小于3分钟的约束下，以平台工作量的方差最小作为目标函数建立模型，分别增加平台个数为2,3,4,5进行试探求解，最终得到增加4个交巡警平台时达到最优，并得到增加4个交巡警平台的位置和此时24个交巡警平台的管辖范围。对问题四，以3分钟内不可达路口的百分比和各区交巡警平台的平均工作量作为合理性的衡量指标，并赋以相应的权重，依次考察每一个城区的合理性，得到城区C、D、E、F交巡警平台设置不合理。对于这四个城区中的每一个城区，以平台工作量方差最小作为目标函数，将3分钟内
3、不可达路口的百分比约束在均值(10%)附近，建立模型，对增加的平台数目从小到大进行试探求解，最终得到这四个城区增加平台数目分别为12、8、11、8，并给出增加平台后工作量尽量均衡的设置方案。对问题五，明确尽量缩小罪犯的逃窜范围，首先定义时刻可以围堵的路口中最小的路口集合，对进行求解，然后以交巡警平台到达需要围堵路口的时间不大于罪犯到达该路口的时间减去3分钟为约束，以最慢的交巡警到达路口的时间最小为目标函数，建立规划模型，并对模型进行求解，最终得到需要围堵的路口为24个并制定出这些路口的围堵方案，从得到报警到全部封锁路口所需要的时间为13.41分钟。最后，我们对模型进行了结果分析和优缺点评价，并
4、给出合理的改进建议。关键字：规划 最优围堵 合理性评价 工作量方差 封锁路口集合1 问题背景和重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、 警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服
5、务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 问题二：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。问题三：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题四：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服
6、务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。问题五：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。2 基本假设(1) 交巡警平台的工作量用所管辖路口的发案率之和表示。(2) 建设一个交巡警平台是需要一定成本的。(3) 罪犯逃跑是速度和警车的速度是一样的，均为。(4) 发生突发事件、封锁交通要道和围堵罪犯时，交巡警要到达指定路口是沿着从交巡警平台到该路口的最短路径走的。3 符号约定 ：0-1变量，1表示第
7、个 路口分配给第 个交巡警平台,0表示第个 路口不分配给第个交巡警平台； ：城区 的路口间的最短距离矩阵，是矩阵中第行第列的值，表示第个交巡警平台到第个路口的距离，同样的定义适用于,，； ：第个 路口的发案率，即每天接到的报案个数； ：第个交巡警平台辖区内的发案率之和；：0-1变量，1表示第个交巡警平台围堵第 个要道,0表示第个交巡警平台不围堵第 个要道； ：0-1变量，1表示第个路口成为交巡警平台，0表示第个路口不是交巡警平台； ：时间内罪犯可能经过的路口集合； ：时刻时，与集合内的路口直接相邻且不在的路口集合（和在下文中有明确定义）； ：城区A的路口数目，同样有 、 、 、 、 分别代表城
8、区B、C、D、E、F的路口数目； ：交巡警的警车速度， ； ：点罪犯逃跑的速度， ； :城区A的路口的邻接矩阵， 代表中第行第列的元素值。 ，此定义可类似推广到 , , , , 。4 模型准备题目的数据给定了全市路口的横纵坐标和连接两个可以直达的路口的路线的起点和终点。利用给出的每个路口的横纵坐标，可以算出相邻路口的距离。将A B C D E F每个城区分别看成一张加权无向图，所以每一个城区用一个带权的邻接矩阵表示。把每一个城区的带权邻接矩阵利用Floyd算法，计算出每个城区内任意两个路口的最短距离。把这个距离存放在矩阵中，每个城区对应一个 的矩阵(表示对应城区的路口数目)。5 模型的建立和求
9、解问题一问题分析：在A区共有92个路口，其中20个是交巡警平台，那么各个平台首先要管辖自己所在的路口。为各交巡警服务平台分配管辖范围，实际上就是把剩下的72个路口分配给这20个平台。分配的目标是所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。同时由于每个平台的警力配备基本相同，所以平台的工作量尽量均衡。在每一种分配方案中，一个路口必须且只能分配给一个交巡警平台。模型一：目标： ( )使3分钟内不可到达的路口数目最小。约束： 对于每一个路口 ，必然存在一个交巡警平台要对其负责。 每一个交巡警平台的工作量，用辖区内路口的发案率之和表示。并对工作量加以控
10、制，使得每个平台的工作量不会过高或者过低。 结合实际情况，每一个交巡警平台要对自己所在的路口负责。为了对该模型进行求解，我们首先去掉约束（3）得到三分钟内不可达的交巡警平台数目为6，然后再加上该约束不断加紧该约束以达到交巡警平台的工作量尽量均衡的目的。利用LINGO软件编程求解此0-1规划问题得到A区每个交巡警平台的管辖范围得到表格 1，同时得到6个路口3分钟内不可到达，分别是路口28、29、38、39、61、92。表格 1 A区交巡警平台的管辖范围交巡警平台管辖的路口编号交巡警平台管辖的路口编号11 65 68 71 72 76 77 78 791111 26 27 22 40 73 741
11、212 2533 44 54 55 56 67 951313 21 22 23 24 44 57 60 62 631414 29 3855 49 51 52 53 56 591515 31 9266 50 581616 35 3777 30 33 47 481717 41 42 43 88 36 45 461818 80 84 87 88 9199 32 341919 64 66 69 70 75 81 831010 28 39 612020 82 85 86 89 90我们对模型结果进行了分析，得到在此模型下该区交巡警平台的工作量的均值为6.23，不同交巡警平台的工作量的波动范围为，说明在这
12、个模型下，交巡警平台之间的工作量存在不合理性。问题二问题分析：要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。一个交巡警平台只能封锁一个交通要道，并且一个交通要道只能被一个平台封锁。目标是快速地全封锁，也就是从封锁行动开始到13个交通要道被全部封锁完毕，所用时间最短。模型二：目标： 20个交巡警平台到13个交通要道的最长距离最小。约束： 每一个交巡警平台至多封锁一个交通要道。 每一个交通要道 ，必然有一个交巡警平台 要对其进行封锁。利用LINGO 软件对上述模型进行求解，最终得到最小封锁时间为8.02分钟，求解结果见表格 2，围堵示意图见图 1 。表格 2
13、交通要道的封锁情况交通要道编号交巡警平台交通要道编号交巡警平台交通要道编号交巡警平台1106111119216713124328151317414951210表格 2中交通要道编号表示要围堵的交通要道的编号，交巡警平台表示A区负责围堵的交巡警平台编号。图 1 A区13个交通要道围堵方案示意图图 1中O 表示交巡警平台，*表示要围堵的交通要道，从O指向*的箭头表示交巡警平台围堵相应的交通要道。问题三问题分析：从该区剩下的72个路口中选取2至5个作为交巡警平台，使得交巡警平台的工作量均衡并且出警时间不要过长。工作量用辖区内的路口犯案率之和衡量。目标就是使所有平台的任务量方差最小，同时所有路口在3分
14、钟内可以到达。考虑到建设交巡警平台的成本，应当是取满足要求的最小平台数。模型三：目标： 计算交巡警平台工作量的方差，使得方差最小。约束： 对于每一个路口只能有一个交巡警平台来服务它。 如果路口 被选择作为交巡警平台，那么首先它要自己服务自己()，而且自己不会作为路口被服务()。 如果路口 没有被选择作为交巡警平台，那么其他路口不可能被它服务()。 前20个路口已经默认是服务平台，所以 这是一个分段函数线性化后的表达式，如果路口 没有被选择作为交巡警平台，那么它不可能服务其他路口，所以 。如果路口 被选择作为交巡警平台，那么它服务的路口数 。综合这两种情况，也就是满足，代表一个足够大的数，对于本
15、题而言不妨设为20，本质上不是对交巡警平台服务的路口数目进行限制。 限制每一个路口都是3分钟内可以到达的。 计算每一个交巡警平台辖区内路口的发案率之和，即每一个平台的工作量。 计算交巡警平台的平均工作量，为了便于对目标函数进行求解我们对92个路口都假设设置为交巡警平台，给出平均工作量的特殊形式。 限制交巡警平台的个数是 ， 代表已经存在的交巡警平台个数， 代表要增加的平台个数。利用LINGO软件对上述模型进行求解，依次取2、3、4、5。当 、 时，不存在可行解。当 、 时，存在可行解。为满足目标同时降低建设交巡警平台的投入，应当取 ，当时对上述模型求得最优解。求解结果：表格 3 A区增加的四个平台及各个平台的管辖范围交巡警平台管辖的路口编号交巡警平台
