2011高教社杯全国大学生数学建模竞赛B题论文. 下载本文

内容发布更新时间 : 2024/12/25 4:13:49星期一 下面是文章的全部内容请认真阅读。

摘要

本文就某市的实际情况与需求,合理的建立了有关交巡警服务平台设置与调度的模型,通过图论模型、规划模型以及计算机程序的结合,对题中所述问题进行了求解,获得了比较满意的结果。

对于问题一,首先将出警时间的约束转换为距离约束,分别利用朴素的覆盖点集以及微变量逐次调控的方法,得出了该问题的预分配方案以及最后的优化方案。

问题一的第二个子问题是匹配问题,我们通过0-1变量match来标记每个交巡警服务平台是否参与道路的封锁。则当封锁路口时,需要全部13 个路口全部封锁才能达到目的。警车到达节点所花费的时间应该以最后一个到达对应的节点的警车所需要的时间来决定。于是借助MATLAB程序来解决此问题,由上文可得目标函数为:maxi{?[cost(i,j)?match(i,j)]},得到一个最佳的调度方案,封堵完

j?1n成的最短时间约为8分钟。

第三个子问题作为对第一个子问题的优化补充,我们基于前面的结果对各站点的工作量进行尽量的均衡分配,根据再分配的结果,在满足各个服务站点工作量平衡的前提下,得出结论分别要在编号为42,57,62,90的四个交点上添加4个新的服务站。

对于问题二,采取与问题一的第三个子问题相同的原则和任务要求,针对全市现有的服务平台数量进行平台管辖范围的分配,分配原理与问题一的第一个子问题基本类似,只是数据规模的一个扩大问题。而在后来的模型优化过程中,我们引入人口密度的因素,对现有服务平台管辖范围进行重新分配。并利用工作量的均衡性来度量设置方案合理性。

最后,对于问题二的最后一个子问题,我们建立了最佳围堵方案模型。考虑到警力资源的限制,不可能完全将该区域的任何一个点都围堵住,这时就需要在原有围堵的基础上改进方案,在那些未被围住的点继续以3分钟的圈往外延伸。最后得出合理的围堵方案。

关键词:0-1规划 变量微调 工作量均衡度

一、问题重述

警察肩负着刑事执法,治安管理,交通管理,服务群众四大职能。为了更有效地贯彻实施这些职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。如何根据城市的实际情况与需求合理地设置交巡警服务平台,分配各平台的管辖范围,调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的问题:

(1)附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图。请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警到达事发地。

对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加2至5个平台,请确定需要增加平台的具体个数和位置。

(2)针对全市的具体情况,按照设置交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理,请给出解决方案。

如果该市地点P处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯,请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、问题假设

(1) 每个交巡警平台的职能与警力的配置相同;

(2) 不考虑警车启动与停止,路上受到阻碍所花费的时间; (3) 假设巡警都按最短路径到达各案发路口; (4) 假设犯罪案件都在路口上发生; (5) 道路均为双向;

(6) 假设城区内道路无限速;

(7) 假设犯罪案件不会在同一时间内发生多起;

(8) 交巡警服务平台的节点的犯罪案件的解决不花费时间; (9) 假设犯罪车辆逃跑与警车的追赶速度相同;

三、符号说明

s1:交巡警管辖距离; v1:警车的平均速度;

v2:嫌疑人逃跑的平均速度;

t0:警车到达案发路口的时间限制; li:各点到管辖它的交巡警平台的距离;

?:各点的发案率; Ai:各点的工作量;

zi:各节点到管辖它的交巡警服务平台的距离; xi:第i个节点的横坐标; yi:第i各节点的纵坐标; d:两节点之间的距离; cost(i,j):i,j两点的实际最短距离;

四、模型预处理

(1)交巡警服务平台的管辖范围:

该问题要求在道路交点出现突发事件时,交巡警尽量能在3分钟内到达事发点。由于警车的时速均衡且为60km/h,所以可以将时间限制转换为距离限制,由于s1?v1?t0,可求出交巡警在时间限制内管辖范围的最大半径为3km。为了处理方便,我们使得交巡警服务平台以一整段路为标准来管辖各路段。同时根据附件2所给内容,基于各个路口的发案率,假设案件均发生在交叉路口。由此,即可将路段管理转化为对路口的管辖。当突发事件发生时,警车立即出动至所管辖的案发点。

(2)交巡警服务平台布置的合理性:

该问题主要考虑的是交巡警服务平台的工作量均衡问题,由于A区不同地域节点的密度不同,而且发案率也不相同,所以工作量可以表示为li与?的乘积,即Ai?li??。对每个交巡警服务点所管辖的范围以交点为单位,按照工作量均衡的原则去逐个改变交点所属的辖区,最终使各个交巡警平台的工作量达到最优均衡状态。

五、问题一的解决

问题1.1

d?(xi?xj)2?(yi?yj)2,由于两节点间的距离公式为:借助C语言程序(见

附录1),可得到各交巡警服务平台(共20个,编号1-20)到各节点(共72个,

编号21-92)的距离小于3km的各节点编号,得到下表 交巡警服务可管辖的节点编号 平台编号 1 42 43 44 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 2 40 41 42 43 44 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 3 38 39 40 43 44 54 55 63 64 65 66 67 68 69 70 75 76 4 54 55 56 57 58 60 62 63 64 65 66 67 68 75 76 77 5 30 32 33 46 47 48 49 50 51 52 53 56 57 58 59 61