2011数学建模全国竞赛B题求解
110警车上街巡逻，不仅可以震慑犯罪分子，降低犯罪率，还可以增加市民的安全感。同时也加快了接警时间，提高了反应时间，为社会和谐提供了有力保障。
现在，给定一个城市中某个区域的道路数据和地图数据，这个区域中三个关键部分的坐标分别为(5112，4806)、(9126，4266)和(7434，1332)。这个地区有307个路口。为了简化问题，将两个相邻交叉口之间的道路近似认为是一条直线，所有事故地点都在下面的道路上。
全市计划新增一批配备GPS卫星定位系统和先进通信设备的110警车。假设110警车平均巡逻速度为20km/h，接警后平均行驶速度为40km/h..警车配置和巡逻方案应尽可能满足以下要求:
D1。接警后三分钟内到达现场的警车比例不低于90%；而且到达关键部位的时间必须在两分钟之内。
D2。使巡视效果更加显著；
D3。警车的巡逻规则应该是隐蔽的。
现在我们需要解决以下问题:
1.如果需要D1，需要部署多少辆警车在该区域巡逻？
2.请给出相关指标评价巡视效果的显著程度。
3.请给出满足D1并尽可能满足D2条件的警车巡逻方案及其评价指标值。
第四，在第三个问题的基础上，考虑D3条件，给出警车在you中的巡逻方案及其评价指标值。
5.如果这个区域只有10辆警车，应该如何制定一个尽可能满足d1和D2的巡逻方案？
6.如果接到报警后警车平均速度提高到50km/h，回答问题3。
7.你认为还有哪些因素和情况需要考虑？给出你相应的解决方法。
双问题分析
本课题是关于城市道路网中警车的配置和巡逻。在配置警车时，首先要考虑接警后在规定时间内到达现场的警车比例。在这种条件下，我们应该以最小的车数为目标来建模和求解问题。制定巡逻计划时，要考虑巡逻的效果和隐蔽性。
第一个问题只需要D1和最少的警车数量。可以认为警车是静止的，三两分钟能到达的区域就是它的覆盖范围。相应地，在所有街道的覆盖率不小于90%的条件下找到最优解。
问题二:评价巡逻效果，需要考虑两个方面:一是巡逻的全面性，即一段时间后警车经过的街道数占总街道数的比例；二是巡逻的不均匀性，即一段时间后，每条街经过的警车数量相差不大，用方差来衡量。
第三个问题是在满足D1的条件下，尽可能满足第二个问题给出的指标，并给出评价方案的指标。先找到一组满足D1的警车位置，然后在与警车位置相连的点中随机找一个点，判断新点是否满足D1。如果满足D1，警车就开到这个点，否则再次搜索，直到满足为止。一段时间后，统计所有车通过的点数和每个点通过的次数，用问题2给出的两个指标进行评价。结合这两个指标，就可以判断这条路径的好坏，重复这个过程，直到综合评价指标达到满意值。
第四题增加了隐蔽要求。首先给出了评价隐蔽性的指标，可以用路线的随机性来评价，并将其加入到第三个问题的模型中求解。
问题5限制警车数量为10。要综合考虑D1和D2。首先分配这10辆车，使道路覆盖率最高，然后按照问题3的步骤解决问题，其中每一步只需要使道路覆盖率尽可能高即可。
问题6和问题3一样，只是把速度改成50 km/h。
三种模式假说
1.警车在路上巡逻，不考虑巡警办案的时间；
2.所有案发现场都在路上，案件发生在路上任意一点的概率相等；
3.警车的初始停靠点是随机的，但尽量做到分散，一辆警车管辖一个分区；
4.假设在每个划分的区域内，短时间内最多发生一例；
5.假设区域内的每条路都是双行道，不考虑转弯对结果的影响；
6.如果关键部位不在路上，假设这些关键部位在最近的路上；
7.图中的水域对巡逻计划没有影响。
四符号描述
指示警车的数量
表示从警车的初始停靠点到每条道路的最短距离。
表示整个区域的总道路长度。
指示3分钟内无法到达的区域的道路长度。
表示非重点部位警车不能在3分钟内到达现场的比例。
这意味着三分钟内从报警位置到事件现场的最大距离是
表示整个区域中离散点的总数。
表示区域中的节点数。
表示区域中的调整功能。
代表模拟退火时间，代表温度值。
表示区间调整函数
指示综合指数
指示不均匀性指数
代表一个综合评价指标
表示第一辆车通过每条道路的次数。
代表每条道路穿过整个区域的平均次数。
五种模型的建立及算法设计
5.1当满足D1时，该区域所需的最小警车数量和巡逻方案。
当5.1.1满足D1的条件时，该地区警车最少的规律。
当题目要求警车配置和巡逻方案满足D1的要求时，整个区域所需警车数量最少。假设警车都在路上，所有事故现场也都在路上，但是区域内的道路总长度是一个恒定值；警车接警后到达案发现场有时间限制和概率限制:普通区域三分钟内到达案发现场的比例不低于90%，到达重点部位的时间必须控制在两分钟内。由此可见，每辆警车的管辖范围不会很大，所以我们考虑将整个区域划分为若干个分区，每辆警车管辖一个分区。
从上面的分析来看，解决整个区域的警车数量最少的问题，可以转化为解决每辆警车能够管理尽可能大的一条街道的问题。所以我们寻找规则，每辆警车应该有尽可能大的管辖权。为了简化问题，不考虑90%概率到达现场的限制，只对警车三分钟内能到达现场的情况进行定性分析。分析示意图如图1所示。警车的初始停放位置随机分布在道路上的任意一个节点。让我们假设一辆警车停在A点..
图1警车辖区分析示意图
由于一辆警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h，由于距离信息容易获取，我们将时间限制改为距离限制，便于分析和求解。警车接警时，三分钟内从接警位置到事发现场的最大距离为，其中。
如图1，我们假设警车的初始停放位置在A点，是1，2，3，4路的交叉口。我们仅以1路上巡逻的警车为例进行分析。警车在道路1上巡逻，速度在A和点之间，距离初始停靠点A的距离为。因为案件可能发生在道路上的任何一点，当警车巡逻到A点时，如果案发现场发生在2、3、4路，警车会以40km/h的速度行驶到现场，警车在三分钟内从A点到达现场的最大距离是。如果警车继续在1道路上向前行驶，警车三分钟内能到达现场的距离会继续缩小。警车从初始点行驶到A点但未到达该点时，警车的最大管辖范围大于警车到达该点时。为了让警车的管辖范围尽可能大，巡逻范围越小越好。当警车在初始停靠点静止时，警车的管辖范围达到最大。
图1的分析是特例，道路1，2，3，4是对称分布的。现在让我们分析一下一般情况，如图2所示。
图2.1图2.2
图2警车最大权限分析示意图。
图2.1所示的情况是道路分布不对称。与图1相比，图2.1所示道路的方向和角度发生了变化，图2.3的情况更加复杂。参考图1的分析方法，分析这两种情况下警车巡逻时三分钟内能到达现场的最大距离的规律。我们只分析图2.2的情况，1、2、3、4、5路在C点相交，1路和6路之间还有一个道路交叉口D，因为巡逻时警车在道路上行驶。不影响路径的长短，所以当警车巡逻到距离初始停靠点C较远的D点时，如果此时有案件发生，警车应在三分钟内到达现场处理案件，最大行驶距离在。如果警车继续在1道路上向前行驶，警车在三分钟内能够到达现场的距离会继续缩小。警车不开到D时，此时警车最大管辖比大。当警车静止时，警车的管辖范围可以达到最大。
以上分析只是定性分析，三个关键部分也可以同样分析，结论是一致的。以上分析不考虑90%的到达概率限制，但需要在设计算法中充分考虑。
综上所述，当警车在初始停靠点静止不动时，在三分钟的时限内，警车从初始停靠点能到达现场的最大距离为。
5.1.2离散化道路
因为事发现场分布在等概率的道路上，所以从区域地图上可以发现，整个区域的道路长度是不均匀的。为了使计算结果更加准确，可以将这些道路离散化。只要选择合适的离散方案，警车在通过道路上的离散点时就可以通过道路。这样，在求解警车初始停靠点或警车到达发现现场的道路时，计算结果显然比只考虑整条道路的交叉口要准确得多。
该地区有307个道路交叉口和458条道路。我们采用线性插值的方法对道路进行离散化，以步行一分钟的距离为步长。一分钟时间的选择参照问题3的结果要求设定。采用线性插值的方法，从道路的一个方向进行线性插值，实现每条道路离散化的目的。考虑到有些路不是的整数倍，我们将讨论一般情况，分析图如图3所示。道路的长度AB是长度的总和。为了更准确地处理CB道路，需要考虑是否在CB之间插入新的点。根据长度的不同，相应的处理方法也不同。
图3道路离散化分析示意图
引入临界指标，选择大小的准则是使警车的等效平均巡逻速度与给定速度()之差尽可能小。经过计算，在不插入新坐标点的情况下，整个区域的道路分散效果可以更好。此时CB段的长度设置为processing，所以离散化后AB路的长度会比实际长度短；必要时，需要在两点之间插入另一点，因为这种处理可以使整个区域内整条道路的离散化效果比较理想。如图3所示，在C和B之间插入一个新的坐标点，插入位置在从C点开始的D点，这样处理后的道路长度比实际长度长。利用这种方法进行线性插值，用MATLAB编程对整个区域的道路进行离散化。离散化结果如图4所示。离散化后，得到762个节点，比原始数据多455个。离散化节点数据见附件“newpoint.txt”。
图4全区离散结果图
用这种插值方法将道路离散化后，将直线上的无穷多个点转化为有限个点，便于分析问题和实现相应的算法。从图4可以看出，整体的离散化效果还是比较理想的。
5.1.3按地区求解警车数量的算法设计
考虑到警车配置和巡逻方案需要满足接警后三分钟内到达普通部位案发现场的警车比例不低于90%，到达重点部位必须控制在两分钟以内的要求。设计算法的目标是在满足D1的条件下，找出警车总数最小，即每个区域覆盖尽可能多的道路节点。由于警车的初始位置未知，我们可以将警车的初始停止点设置在道路上的任意一点，即图4所示的762个离散点的某些节点上。总体思路是每两辆车尽量分散分布，一辆警车管辖一个分区，用这些分区覆盖整个区域。
于是我们设计了算法1，步骤如下:
Step1:将整个区域预分配成区，每个区分配一辆警车。警车的初始停放位置设置在预分配区中心的道路节点上。如果区域的中心不在道路节点上，则警车被放置在离中心最近的道路节点上。
第二步:统计分区无法覆盖的节点，调整警车的初始停靠点，使分区覆盖尽可能多的道路节点。调整分为两种方案:(1)调整分区内按照模拟退火思想构造的函数，调整区间内车辆初始点的位置(后面详细描述)。当分区中节点较多时，调整的概率较小，当分区中节点较少时，调整的概率较小。(2)当区域内有未覆盖的节点或节点群(一个范围内集中了三个或三个以上的节点)时，调整警车的初始位置，按照一定的规则向这些未覆盖的节点移动(详细在算法描述中)，同时保证三个关键部位在2分钟内能够达到100%；
步骤3:利用Floyd算法计算警车初始停靠点与周围道路节点的最短距离；
第四步:用每个划分区域未覆盖的道路总长度与整个区域的道路总长度的比值来表示警车不能在3分钟内到达现场的概率；
第五步:模拟足够的次数，如果是，从车辆数中减去1，跳转到第1步；
第六步:计算结束后，比较当时对应的数值，当得到最小值时，记录此时的区域划分方案，即最少的警车数量。
算法的一些解释:
(1)该算法取的车辆数从最多到最少计算，初始值设为20。这个值的选择是根据面积图估计的。
(2)预分区的好处是警车的初始位置尽可能均匀分布，警车的初始停车点可以在一个分区的中心附近找到，相比在整个区域内随机生成停车点，明显提高了计算效率。
预分配后，整个区域需要不断调整，调整时需要考虑调整方向和调整概率。
警车调试借鉴了模拟退火算法的方法。为了使初始停车点调整在道路节点较多的分区中的概率较小，而初始停车点调整在道路节点较少的分区中的概率较大，我们构造了一个调整概率函数。
(1)
在公式(1)中，都是常数，分别是整个区域的车辆数，第一个分区覆盖的节点数，时间。同时，它们也可以代表模拟退火的温度变化:初始温度越高，区域调整速度越快。随着时间的增加，气温不断降低，区域调整速度逐渐减缓，这也更符合实际情况。
调整概率函数可以从等式(1)获得。假设同一温度(时间)下车辆总数不变，当第一分区的节点数大于第一分区的节点数时，分区的调整概率较大，分区的调整概率较小。分析其原因:当分区内节点较多时，警车在分区内的初始停放位置较为合适，而当分区内道路节点较少时，说明警车的初始停放位置未被选择，需要以较大概率进行调整，这也是客观存在的。
对于所有未覆盖的道路节点和分区外的许多节点(称为节点组)，用于调整警车位置迁移的方向，其分析示意图如图5所示。调整方案的目标是使未覆盖节点的数量尽可能少。在设计调整方向函数时，需要考虑:(1)节点组中的节点数；(2)节点群中警车的位置。距离是优先的，所以在公式(2)中，调整方向函数用距离的平方来描述。
因为某个区域的未覆盖节点数、整个区域的未覆盖节点总数、子区域与未覆盖节点或节点组的距离都会影响调整方案，这些因素都要综合考虑。因此设计了间隔调整功能，
其中，表示第一分区中未覆盖节点的数量、第一分区与未覆盖节点或节点组之间的距离以及未覆盖节点和节点组的数量。
现在我们根据区间调节函数简单分析一下第一个分区的调节方案。当某个两节点组中的节点数相等，但距离不相等时，例如根据间隔调整公式，向节点组方向调整间隔。当一个分区与两个节点组之间的距离相等，但节点组中的节点数量不相等时，如果是这样，则从(4)中可以知道，该分区将想要调整节点组的方向。
注意在整个调整过程中是否控制调整概率，调整方向函数控制调整方向，寻找在此调整方案下的最佳结果。
图5调整子区域示意图
(3)在步骤3中，利用Floyd算法计算警车初始停靠点与周围节点的最短距离，使该区域发生事情时，警车能够在要求的时限内到达现场。
(4)为了寻找更好的警车停放点，采用模拟退火算法计算局部最优方案。
5.1.4警车配置及巡逻方案
用MATLAB编程实现算法1，整个区域配备13辆警车，在初始停靠点静止时能满足D1的要求。警车初始停放位置分别为道路交叉口节点6、25、30、37、82、84、110、11、126、214、253、226。各警车管辖的路口(原路口节点)如图6所示，分割结果见附录。
图6d 1条件下的区分图。
13分区* * *覆盖252个路口，另外55个原路口不在这些分区覆盖范围内:137，151，159，167，65438。186,188,189,211,215,226,242,255,260,261,262,263,267,270,271,272,275,282,283 ,284,287,288,289,292,296,297,299,304,305,307。在此分区方案下，在这些点中，每两个相连点之间的道路离散值长度与整个区域总长度的比率为。因此，整个区域有13辆警车，每辆警车在初始停靠点都是静止的。当案件发生时，离犯罪现场最近的警车从最初的停靠点到达现场。
5.2评估显著巡视效果的指标
110警车上街巡逻的目的是震慑犯罪分子，降低犯罪率，增加市民的安全感。同时也加快了接警时间(接受报警并赶赴现场处理事件)，提高了反应时间，为社会和谐提供了有力保障。巡警在城市繁华街道和公共场所执行巡逻任务，维护公共秩序，服务群众，可以取得良好的社会效果[1]。
在整个区域内，因为案发现场在马路上，所以马路上的每一点都是等概率发生的。所以，警车巡逻的范围越广，巡逻的街道越多，警车的巡逻效果就越好，对犯罪分子就越有威慑力，警车就能更及时地处理案件。
我们用全面性来衡量巡逻的有效性，即警车巡逻的街道节点数与区域内节点总数的比值。当警车反复通过同一街道、同一离散点时，只记录一次。
(3)
式中，表示警车所经过的离散点，代表整个区域内的离散点总数。数值越大，警车经过的街道越多，效果越显著。
同时考虑到在巡逻过程中可能会出现这样的情况:在同一时间段内，警车会对一些街道进行多次巡逻，而一些街道很少巡逻，甚至没有警车到达，会造成一些巡逻盲区。分布很不均匀。这样，巡逻密度高的街道上的犯罪分子可能不敢在街道上作案，而逃到巡逻密度稀疏的街道上。因此，在警车数量相同的情况下，不均衡巡逻模式的巡逻效果更差，而更均衡巡逻模式的巡逻效果会更好。我们引入了巡视不均匀性来衡量巡视效果的显著性。考虑到方差可以代表不平衡的程度，我们用方差的大小来表示不平衡。方差越大，巡视密度越不平衡，巡视效果越差。
(4)
问题1显示符合D1条件的警车数量为13。此时，每辆警车仍在初始停靠点，只有辖区内发生案件时，警车才会从初始停靠点赶往案发现场办案。警车在巡逻时，需要考虑的问题比较复杂，比如节点在移动时警车能否满足D1的要求，警车如何移动，但基本的算法思想与问题1类似，得到的算法2的框图如图7所示。
为了简化问题，我们假设各分区的警车在巡逻时，尽量保证所有警车的行驶方向一致，所有警车都走双向路，即当警车行驶到某个节点时，同时返回初始停靠点。警车有四个行驶方向，如图6所示。
在图6中，数字1代表巡逻的第一步，2代表巡逻的方向与1相反。具体方案实施时，四个巡逻方向任意选择，但保证所有警车尽可能同向巡逻。
图6警车巡逻方向
我们用MATLAB编程计算这种巡逻模式，得到的车辆数为18，综合评价指数为0。结果的巡视方案见附件“1193402-result 3 . txt”。
5.4在满足第三个问题的基础上，讨论D3条件、警车巡逻方案和评价指标。
巡逻的隐蔽性体现在警车的巡逻路线和时间没有明显的规律性。主要目的是不给犯罪分子可乘之机，防止他们在非巡逻时间实施违法犯罪活动，危害人民生命财产安全。
为了使巡逻的规律隐藏起来，警车在巡逻时至少要有两条不同的路线，最佳时间也不一样。所以考虑到隐蔽性，我们只需要在问题2的基础上增加一个随机过程。至于其评价指标，由于警车有多条可选巡逻路线，当同一条路线同时重复出现时，将再次执行设定的方案。我们用这个时间间隔来衡量隐蔽程度。当循环周期越长，说明可选的巡视方案越多，其规律越隐蔽。循环周期越小，说明巡视方案越少，隐蔽性越差。在巡逻状态下，最差的隐蔽巡逻方案是只有一个巡逻方案，时间固定。这样的巡逻方案一点隐蔽性都没有。
5.5全区域10车辆时的巡逻方案。
根据第三个问题的结果，10的车辆数并不能完全覆盖整个区域，其算法与算法2类似，只是此时车辆数已经固定，要求尽可能满足D1和D2。我们得到的评价指标值为，巡视方案见附件“1193402-”
5.6平均行驶速度提高时的巡视方式及评价指标值。
问题6的分析方法和具体实现与问题3一致，但接警后的警车平均速度比原来有所提高，因此各分区的覆盖范围也有所增加。将数值带入问题3的算法中求解，计算出的指标值为，其巡视方案见附件“1193402-result 6 . txt”。
图7算法2的框图
六种模型的分析与评价
在解决满足D1的条件下，整个区域需要多少警车的问题上，采用分区巡逻的思想，先分析各区管辖范围何时能达到最大值的规律，由特殊到一般逐层进行分析。逻辑严密，结果合理。
在求解区域和警车数量时，在初步设定警车停靠位置的基础上，基于模拟退火算法的思想构造函数确定调整概率，在综合考虑影响区间调整的因素后构造函数确定分区的调整方向。根据这两个调整函数调整分区时，每个分区可以管辖尽可能多的道路节点，结果令人满意。
参加考试，贡献力量
[1]中小城市警察巡逻勤务模式探讨，翔宇，江苏公安学院学报，1998，第1期。
[2]Matlab7.0从入门到精通，科技求是，人民邮电出版社；
[3]车辆数不确定的随机车辆路径问题的模型与算法，云等，工业工程，第10卷，第3期，2005年5月；
[4]随机交通分配中有效路径的确定方法，李志春等，交通系统工程与信息技术学报，第3卷，第1期，2003年2月。