cumcm2011B-吴孟达-110警车的配置及巡逻方案-数模讲座26

研究生数模竞赛09年D题

“110警车的配置及巡逻方案”

解题思路解析及论文点评

国防科技大学吴孟达青岛中科院研究生院

2010年7月22日1目录题目命题思路解题思路论文点评综合评述2目录题目110警车配置及巡逻方案

110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社会和谐提供了有力的保障。考虑某城市内一区域，为简化问题，假定所有事发现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332）（见下图红点部位，蓝色部分为水域，道路数据见附件,相邻两个交叉路口之间的道路近似认为是直线）。

3题目4题目某城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案要尽量满足以下要求：

D1.

警车在接警后三分钟内赶到现场的比例不低于90％；而赶到重点部位的时间必须在两分钟之内。

D2.

使巡逻效果更显著；

D3.

警车巡逻规律应有一定的隐蔽性。5题目

请回答以下问题：一.若要求满足D1,该区最少需要配置多少辆警车巡逻？二.请给出评价巡逻效果显著程度的有关指标。三．请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。五．如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。6题目命题思路“110警车配置及巡逻方案”，是一个根据现实问题简化改造而成的数学建模问题，其背景知识较单纯，容易理解，初看起来比较容易上手，但是随着对问题分析的逐步深入，会发现这实际上是一个很难找到最优解的问题。如果只考虑警车的静态分布，要使之分布尽量均匀，是一件很容易做到的事情，但要考虑十几辆或者二十几辆警车在巡逻中的动态分布的“均匀性”，由于道路的限制，车辆不能随意行驶，则问题的难点就显现出来了。本题目希望同学们解决的问题就是警车巡逻时如何保持“动态均匀性”的问题，也就是说，要给出一个优化算法，使得由此算法计算得出的所有警车的巡逻路线分布越“均匀”越好。7命题思路在命题时，我们针对前些年竞赛中发现的有部分参赛队“凑结果”的现象，设置了结果验证环节，并在题目中明确告知结果需要验证，对结果输出格式也有严格要求。我们认为，作为将要从事科学研究的科技工作者，实事求是的工作态度，严谨不苟的工作作风，是十分重要的素质，也应该纳入本项竞赛活动所要达到的目标之一。8命题思路解题思路题意理解（1）关于“警车在接警后三分钟内赶到现场的比例不低于90％”，可以有两种不同理解。一种我们称之为“空间覆盖”，即一天内警车巡逻覆盖（三分钟内能到达）过的道路占所有道路的比例要不低于90％。另一种称之为“时间覆盖”，即一天内任意时刻警车覆盖的道路占所有道路的比例要不低于90％。

（2）关于“警车巡逻规律应有一定的隐蔽性”。9解题思路－题意理解解题方法第一问

着重看如何理解“警车在接警后三分钟内赶到现场的比例不低于90％”，以及如何实现这一目标。通常可以考虑区域划分的方法解决此问，例如采用聚类方法、集合覆盖算法、启发式搜索算法、遗传算法等算法作区域划分。静态处理也可以接受。严格说来，最少车辆数不少于17辆。10解题思路－第一问第二问

题目第二问要求给出“评价巡逻效果显著程度的有关指标”，我们认为，至少有以下四个指标（或类似指标）需要加以考虑：（a）平均覆盖率；（b）瞬时覆盖率达标比例；（c）到达率（或见警率）；（d）覆盖次数方差（或警力分配均匀度）。对此四个指标的含义解释如下。11解题思路－第二问（a）平均覆盖率：警车巡逻覆盖（三分钟内能到达）过的道路占所有道路的比例。按照题目要求，这一比例应不低于90％，这是一个硬指标，必须要达到。（b）瞬时覆盖率达标比例：覆盖率达到90％的时刻占所有时间的比例。这是针对“时间覆盖”情形提出的指标，大部分参赛队未考虑，评阅时是作为一个软指标来评价模型优劣的。12解题思路－第二问

（c）到达率（或见警率）：警车巡逻到达过的道路占所有道路的比例。由于警车巡逻的目的不止是为了能够及时处警，增加对企图作案者的震慑作用也是目的之一，所以仅有覆盖率还不足以度量巡逻效果的显著性，见警率也是度量巡逻效果的显著性的一个必不可少的指标，这一指标越大越好。（d）覆盖次数方差：道路上各点被覆盖次数的方差，用以度量警力分配的均匀度。此指标与平均覆盖率联合使用，方能较全面地反映覆盖率的真实效果。评阅时主要考察关于度量巡逻效果显著性的指标的考虑是否全面，对每一指标的理解与解释是否准确到位。以上考察反映建模者分析问题的能力，以及其对问题是否有全面且深刻的理解。13解题思路－第二问第三问

本问的主要技术难点在于要求二十几辆车在“动态巡逻”条件下保持“分布均匀性”，求最优解的计算复杂度太高，因此，寻找可接受的计算复杂度与结果的优化之间的平衡点，是本问的关键所在。本问的求解充分体现了建模方法的多样性，为参赛者充分发挥创造性提供了很好的机会。主要解题方法概述如下：14解题思路－第三问

1）单车分区法：按照覆盖率要求作区域划分，每个区域固定一辆警车巡逻。此方法主要特点是计算简单，但是其代价是需要车辆数较多。例如静态时17辆车即能满足覆盖率要求，如果分成17个区域，每个区域1辆车，则在动态时要保持满足覆盖率要求就非常困难了，所以不得不增加划分区域。此种方法通常要求配置3５辆车以上，才能达到覆盖率要求。15解题思路－第三问

2）多车分区法：为了改进以上单车分区法的缺点，可以考虑每个区域设置若干辆警车共同巡逻的方法，这样可以减少一些车辆，但代价是计算难度的增加，且每一区域配置的车辆越多，计算难度就越大。16解题思路－第三问

3）动静结合法：有的参赛队单纯从满足车辆数最少的目标出发，让有的车静止不动，这样即能满足覆盖率要求，车辆数又少。但这样做，见警率指标就很差了，于是就再安排一些车跑见警率。从覆盖率与见警率效果来看，此方法很不错，车辆数还不多（大约２２或２３辆），计算也相对简单，似乎是一种好方法。但是这样做，违背了问题本身的实际意义，所以未能得到评委们的认可。数学建模不是解数学题，一定要考虑问题的实际意义是什么，不能为了追求指标的好看而罔顾其实际背景。17解题思路-第三问

4）软分区法：此方法由方法１）延伸而来。与方法１）一样，本方法先划分区域，每个区域配置一辆警车，与方法１）不同的是，每个区域配置的警车并不是一定不能跨区域巡逻，而是设置了一个跨区域因子，此因子随着周围区域警车的位置以及其本身的位置关系而变化。再设置一个区域中心引力因子，以保证该车不会离开自己的区域中心太远。此方法的思想有创意，但在实现时由于各个因子之间较难平衡，所以效果改进不大。18解题思路－第三问

5）蚁群算法：此方法属于启发式搜索算法，在此次竞赛中成为主流解法，其思想是：在道路上设置一个“气味因子”，某段道路上跑过的车越多，则该段道路的“气味”变大，并且“气味”随时间变长而衰减。巡逻车每到一个路口，根据路口其它各段道路的“气味”大小，朝“气味”最小的方向前进。想法蛮有创意，在具体实现时还要处理好多辆车的协同问题等细节。如果细节处理得好，此方法所需要的车辆数大约为２５辆左右，不失为一种比较理想的方案。19解题思路－第三问

6）引力场方法：此方法与上一方法有类似之处，即每段道路依据走过的警车多少有一个“引力因子”，走过的车辆越多，则“引力”越小；同时，任两辆车之间依据距离远近有一个“斥力因子”，距离越近，则斥力越大。对每一辆警车而言，道路对它的“引力”与其它车辆对它的的“斥力”共同构成了一个“引力场”，它将向着“合成引力”最大的方向前进。这也是一种挺有创意的想法，难处在于细节的处理（例如引力与斥力的合成）及计算上的复杂性，对计算能力有较高的要求。20解题思路－第三问

7）切片叠加法：由于静态时车辆数较少，并且车辆可以达到“均匀分布”状态，因此一种想法是对时间进行“切片”处理：每一时刻为一个切片，在一个切片上给出所有车辆的一个“均匀分布”，构造出充分多（例如：１０００张）的不同切片，并且通过筛选使这些切片上的车辆分布点尽量分散，这是出于提高切片“叠加”后的车辆到达率指标的考虑。然后对这些切片按照“择近”原则进行排序，再对排序后的切片依次叠加，便得到一个班次（４小时或８小时）的巡逻方案。21解题思路－第三问这个方案的特点是车辆在巡逻时的速度可以不同，但每辆车的平均速度仍为２０公里/小时，其难点在于对切片的“择近”排序的计算量很大。这是一种很有创意的方法，效果也不错。大约需要２４辆车，可以使覆盖率及到达率指标都比较令人满意。可惜此种解法在本次竞赛论文中未发现使用。22解题思路－第三问

有的参赛队试图用整数规划方法解决此问，以车数最少为优化目标，但一则覆盖率及到达率约束条件不易表达，模型不好建立；二则无法求动态解，所以在此问题中这不是一种现实的方法。其它几问的解法较简单，从略。23解题思路－第三问论文点评24解题思路综合评述解题方法的多样性在参赛论文中体现得较充分，这是竞赛命题所追求的目标之一，这样，参赛者的创造性才可以有较大的发挥空间。25综合评述有过半的参赛队评价指标（第二问）部分完成的不理想，主要体现在指标考虑不全面及讨论不深入，反映出分析问题的能力有不足，对理解题意的重要性的认识也不够充分。事实上，对问题有深入透彻的理解，往往是好的创意的出发点，应有足够的重视。26综合评述计算能力不足成为制约许多参赛队成绩的主要因素。从参赛论文可以看出，有些参赛队不是没有想法，而是无法实现这些想法。据我们所知，有的研究生过于依赖现成软件，导致编程实践缺乏，编程能力下降，这是否当前研究生的一种较普遍的状态，值得所有关心研究生教育改革的人们的关注。27综合评述验证结果之差，超出了我们事先的预料。针对前些年竞赛中发现的有部分参赛队“凑结果”的现象，我们刻意设置了结果验证环节，并在题目中明确告知结果需要验证，对结果输出格式也有严格要求。有近半数的参赛队没有按要求提供巡逻方案数据或甚至没有数据，在按题目要求提供了结果数据的参赛队中，又有相当部分的验证结果与其论文中给出的结果有较大差异。这些现象至少说明了在严谨求实的作风方面，是存在问题的。28综合评述如何求得本问题的最优解，是一个可以继续研究的