《273编号2011全国大学生数学建模竞赛B题题目及参考答案》由会员分享，可在线阅读，更多相关《273编号2011全国大学生数学建模竞赛B题题目及参考答案（25页珍藏版）》请在金锄头文库上搜索。
1、2011 高教社杯全国大学生数学建模竞赛题目 （请先阅读“全国大学生数学建模竞赛论文格式规范” ） B 题题 交巡警服务平台的设置与调度交巡警服务平台的设置与调度 “有困难找警察” ，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、 交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交 通要道和重要部位设置交巡警服务平台。 每个交巡警服务平台的职能和警力配备基本相 同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平 台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析
2、研究下面的问题： （1） 附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服 务平台的设置情况示意图，相关的数据信息见附件 2。请为各交巡警服务平台分配管辖 范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时 速为 60km/h）到达事发地。 对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区 的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出 该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟 在该区内再增加 2
3、 至 5 个平台，请确定需要增加平台的具体个数和位置。 （2）针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服 务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理 性。如果有明显不合理，请给出解决方案。 如果该市地点 P（第 32 个节点） 处发生了重大刑事案件， 在案发 3 分钟后接到报警， 犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资 源的最佳围堵方案。 1 题 目 B 题题 交巡警服务平台的设置与调度交巡警服务平台的设置与调度 摘 要： 本文研究的是某城区警车配置及巡逻方案的制定问题，建立了求解警车巡逻方案
4、的 模型，并在满足 D1 的条件下给出了巡逻效果最好的方案。 在设计整个区域配置最少巡逻车辆时，本文设计了算法 1：先将道路离散化成近似 均匀分布的节点，相邻两个节点之间的距离约等于一分钟巡逻路程。由警车的数目,m 将全区划分成个均匀的分区，从每个分区的中心点出发，找到最近的道路节点，作为m 警车的初始位置，由 Floyd 算法算出每辆警车 3 分钟或 2 分钟行驶路程范围内的节点。 考虑区域调整的概率大小和方向不同会影响调整结果， 本文利用模拟退火算法构造出迁 移几率函数，用迁移方向函数决定分区的调整方向。计算能满足 D1 的最小车辆数，即 为该区应该配置的最小警车数目，用 MATLAB 计
5、算，得到局部最优解为 13 辆。 在选取巡逻显著性指标时，本文考虑了两个方面的指标：一是全面性，即所有警车 走过的街道节点数占总街道节点数的比例，用两者之比来评价；二是均匀性，即所有警 车经过每个节点数的次数偏离平均经过次数的程度，用方差值来大小评价。 问题三：为简化问题，假设所有警车在同一时刻，大致向同一方向巡逻，运动状态 分为四种：向左，向右，向上，向下，记录每个时刻，警车经过的节点和能够赶去处理 事故的点，最后汇总计算得相应的评价指标。 在考虑巡逻规律隐蔽性要求时，文本将巡逻路线进行随机处理，方向是不确定的， 采用算法2进行计算， 得出相应巡逻显著指标， 当车辆数减少到10辆或巡逻速度变
6、大时， 用算法 2 计算巡逻方案和对应的参数，结果见附录所示。 本文最后还考虑到 4 个额外因素，给出每个影响因素的解决方案。 关键词：模拟退火算法；Floyd 算法；离散化 参赛队号 11*02 队员姓名 一 问题的重述 110 警车在街道上巡逻，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能 够增加市民的安全感，同时也加快了接处警时间，提高了反应时效，为社会和谐提供了 有力的保障。 现给出某城市内一区域， 其道路数据和地图数据已知， 该区域内三个重点部位的坐 标分别为：（5112，4806） ， （9126， 4266） ， （7434 ，1332） 。该区域内共有 307 个道路 交
7、叉口，为简化问题，相邻两个交叉路口之间的道路近似认为是直线，且所有事发现场 均在下图的道路上。 该市拟增加一批配备有 GPS 卫星定位系统及先进通讯设备的 110 警车。设 110 警车 的平均巡逻速度为 20km/h，接警后的平均行驶速度为 40km/h。警车配置及巡逻方案要 参赛密码 （由组委会填写）（由组委会填写） 2 尽量满足以下要求： D1. 警车在接警后三分钟内赶到现场的比例不低于 90； 而赶到重点部位的时间必须在 两分钟之内。 D2. 使巡逻效果更显著； D3. 警车巡逻规律应有一定的隐蔽性。 现在我们需要解决以下几个问题： 一. 若要求满足 D1,该区最少需要配置多少辆警车巡
8、逻？ 二. 请给出评价巡逻效果显著程度的有关指标。 三请给出满足 D1 且尽量满足 D2 条件的警车巡逻方案及其评价指标值。 四. 在第三问的基础上，再考虑 D3 条件，给出你们的警车巡逻方案及其评价指标值。 五如果该区域仅配置 10 辆警车，应如何制定巡逻方案，使 D1、D2 尽量得到满足？ 六. 若警车接警后的平均行驶速度提高到 50km/h，回答问题三。 七. 你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。 二 问题分析 本题为城区道路网络中警车配置及巡逻问题。在进行警车配置时，首先要考虑警车 在接警后在规定时间内赶到现场的比例，在此条件下，以车数最少为目标，建模、求解
9、 ； 在制定巡逻方案时，要考虑巡逻的效果及隐蔽性问题。 问题一只要求满足 D1，求最少的警车配置数，可以认为警车是不动的，在三分钟 或两分钟内它能到达的区域就是它的覆盖范围。据此，在满足所有街道的覆盖率不低于 90%的条件下，寻找最优解。 问题二要评价巡逻效果，有两个方面需要考虑：一是巡逻的全面性，即经过一段时 间后警车走过的街道数占总街道数的比例；二是巡逻的不均匀性，即经过一段时间后警 车经过每一条街道的次数相差不大，用方差来衡量。 问题三是在满足 D1 的条件上尽量满足问题二所给的指标， 并给出评价方案的指标。 首先找到一组满足 D1 的各警车位置， 然后在和各警车位置相连的点中随机寻找一
10、个点， 判断新的点是否满足 D1，如果满足则警车行驶到该点，否则重新寻找，直到满足为止。 一段时间后统计所有车走过的点数及每个点被走过的次数， 用问题二给出的两个指标进 行评价。综合两个指标，可判断此路径的好坏，重复这个过程，直到综合评价指标达到 一个满意的值为止。 问题四增加了隐蔽性要求，首先给出评价隐蔽性的指标，隐蔽性可用路线的随机性 来评价，将它加入到问题三的模型中去进行求解。 问题五限制警车数量为 10，要综合考虑 D1、D2，先分配这 10 辆车使道路的覆盖 率最高，然后按照问题三的步骤进行求解，其中每一步对 D1 的判断只需使道路的覆盖 率尽量高即可。 问题六同问题三，只需将车速改
11、为 50km/h 即可。 三 模型的假设 1. 警车都在路上巡逻，巡警去处理案件的时间不考虑； 2. 所有事发现场都在道路上，案件在道路上任一点是等概率发生的； 3 3. 警车初始停靠点是随机的，但尽量让它们分散分布，一辆警车管辖一个分区； 4. 假定各个划分区域内，较短时间内，最多会发生一个案件； 5. 假设区域内的每条道路都是双行线，不考虑转弯对结果造成的影响； 6. 如果重点部位不在道路上的，假设这些重点部位在离它们最近的道路上； 7. 图中水域对巡逻方案没有影响。 四 符号说明 表示警车数目m 表示警车初始停靠点到各道路的最短距离d 表示整个区域的总道路长度L 表示不能在 3 分钟内到
12、达的区域的道路的长度l 表示非重点部位的警车在 3 分钟内不能到达现场的比例k 表示三分钟内能从接警位置赶到事发现场的最大距离是r 表示整个区域总的离散点个数n 表示第 区内的节点个数 i ni 表示区内调整函数 1 f 表示模拟退火的时间，表征温度值t 表示区间调整函数 2 f 表示全面性指标r 表示不均匀性指标e 表示综合评价指标h 表示第 辆车经过每条道路的次数 i si 表示整个区域每条道路经过的平均次数s 五 模型的建立与算法的设计 5.1 满足 D1 时，该区所需要配置的最少警车数目和巡逻方案5.1 满足 D1 时，该区所需要配置的最少警车数目和巡逻方案 5.1.1 满足 D1 条
13、件时，区域最少警车的规律 题目要求警车的配置和巡逻方案满足 D1 要求时，整个区域所需要配置的警车数目 最少。由假设可知警车都在道路上，且所有事发现场也都在道路上，但区域内总的道路 长度是个定值的；警车在接警后赶到事发现场有时间限制和概率限制：三分钟内赶到普 通区域案发现场的比例不低于 90， 而赶到重点部位的时间必须控制在两分钟之内。 由 此可知每辆警车的管辖范围不会很大，于是考虑将整个区域分成若干个分区，每辆警车 管辖一个分区域。 4 由上面的分析，求解整个区域的警车数目最少这个问题可转化为求解每一辆警车所 能管辖的街道范围尽量的大。于是我们寻找出使每辆警车管辖的范围尽量大的规律。为 了简
14、化问题，我们不考虑赶到现场的 90%的几率的限制，仅对警车能在三分钟内赶到事 发现场的情况作定性分析，其分析示意图如图 1 所示。警车的初始停靠位置是随机的分 布在道路上的任一节点上，我们假设一辆警车停靠在 A 点上。 图 1 一辆警车管辖范围分析示意图 由于警车的平均巡逻速度为 20km/h，接警后的平均行驶速度为 40km/h，由于距离 信息比较容易得到，于是我们将时间限制转化为距离限制，这样便于分析和求解。当警 车 接 警 后 ， 在 三 分 钟 内 能 从 接 警 位 置 赶 到 事 发 现 场 的 最 大 距 离 是， 其 中r 。kmr240 60 3 如图 1 所示，我们设警车初
15、始停靠位置在 A 点，A 点是道路 1，2，3，4 的道路交叉 口。我们仅以警车在道路 1 巡逻为例来进行分析，警车以的速度在道路 1 上 Ahkm/20 到点之间巡逻，与初始停靠点 A 的距离为。由于案件有可能在道路上任一点 A Axkm 发生，当警车巡逻到 A 点时，若案发现场在道路 2，3，4 上发生时，警车以 40km/h 的 速度向事发现场行驶，警车能在三分钟内从点赶到现场的最大距离为。如 Akmx)2( 果警车在道路 1 上继续向前行驶，则该警车能在三分钟内赶到现场的距离继续缩小，当 警车从初始点向 A 点行驶但没有达到点时， 此时该警车的最大管辖范围比警车到达 A A 点时的最大
16、管辖范围大。为了使警车的管辖范围尽量大，警车的巡逻范围越小越好，当 时，即警车在初始停靠点静止不动时，警车的管辖范围达到最大值。0 xkm2 图 1 所分析的是特殊的情况，道路 1，2，3，4 对称分布，现在我们来对一般的情 况进行分析，如图 2 所示。 5 图 2.1 图 2.2 图 2 一辆警车最大管辖范围分析示意图 图 2.1 所示的情况是道路分布不对称，与图 1 相比，图 2.1 所示的道路方向和角度 都发生了改变，图 2.3 中的情形更为复杂。参照对图 1 的分析方法，我们分析这两种情 形下， 警车巡逻时能在三分钟内赶到现场的最大距离的规律， 我们只分析图 2.2 的情况， 道路 1，2，3，4，5 相交于点 C,同时道路 1 与道路 6 也有个道路交叉口 D， 由于警车 巡逻时是在道路上行驶的，行走的路线是分段直线,并不影响路径的长度，所以当警车
