2023全国大学生数学建模竞赛A题参考答案

城市表层土壤重金属污染分析

随着城市经济的快速发展和城市人口的不断增加，人类活动对城市环境质量的影响

日显突出。对城市土壤地质环境异样的查证，以及如何应用查证获得的海量数据资料开

展城市环境质量评价，探讨人类活动影响下城市地质环境的演化模式，日益成为人们关

注的焦点。

依据功能划分，城区一般可分为生活区、工业区、山区、主干道路区及公园绿地区

等，分别记为1类区、2类区、……、5类区，不同的区域环境受人类活动影响的程度

不同。

现对某城市城区土壤地质环境进行调查。为此，将所考察的城区划分为间距1公里

左右的网格子区域，依据每平方公里1个采样点对表层土(0~10厘米深度)进行取样、

编号，并用GPS记录采样点的位置。应用特地仪器测试分析，获得了每个样本所含的

多种化学元素的浓度数据。另一方面，依据2公里的间距在那些远离人群及工业活动的

自然区取样，将其作为该城区表层土壤中元素的背景值。

附件1列出了采样点的位置、海拔高度及其所属功能区等信息，附件2列出了8种

主要重金属元素在采样点处的浓度，附件3列出了8种主要重金属元素的背景值。

现要求你们通过数学建模来完成以下任务：

(1)给出8种主要重金属元素在该城区的空间分布，并分析该城区内不同区域重金

属的污染程度。

(2)通过数据分析，说明重金属污染的主要缘由。

(3)分析重金属污染物的传播特征，由此建立模型，确定污染源的位置。

(4)分析你所建立模型的优缺点，为更好地探讨城市地质环境的演化模式，还应收

集什么信息？有了这些信息，如何建立模型解决问题?

摘要：

本文探讨的是某城区警车配置及巡逻方案的制定问题，建立了求解警车巡逻方案的

模型，并在满足D1的条件下给出了巡逻效果最好的方案。

在设计整个区域配置最少巡逻车辆时，本文设计了算法1：先将道路离散化成近似

匀称分布的节点，相邻两个节点之间的距离约等于一分钟巡逻路程。由警车的数目〃?，

将全区划分成加个匀称的分区，从每个分区的中心点动身，找到最近的道路节点，作为

警车的初始位置，由Floyd算法算出每辆警车3分钟或2分钟行驶路程范围内的节点。

考虑区域调整的概率大小和方向不同会影响调整结果，本文利用模拟退火算法构造出迁

移几率函数，用迁移方向函数确定分区的调整方向。计算能满足D1的最小车辆数，即

为该区应当配置的最小警车数目，用MATLAB计算，得到局部最优解为13辆。

在选取巡逻显著性指标时，本文考虑了两个方面的指标：一是全面性，即全部警车

走过的街道节点数占总街道节点数的比例，用两者之比来评价；二是匀称性，即全部警

车经过每个节点数的次数偏离平均经过次数的程度，用方差值来大小评价。

问题三：为简化问题，假设全部警车在同一时刻，大致向同一方向巡逻，运动状态

分为四种：向左，向右，向上，向下，记录每个时刻，警车经过的节点和能够赶去处理

事故的点，最终汇总计算得相应的评价指标。

在考虑巡逻规律隐藏性要求时，文本将巡逻路途进行随机处理，方向是不确定的，

采纳算法2进行计算，得出相应巡逻显著指标，当车辆数削减到10辆或巡逻速度变大

时，用算法2计算巡逻方案和对应的参数，结果见附录所示。

本文最终还考虑到4个额外因素，给出每个影响因素的解决方案。

关键词：模拟退火算法；Floyd算法；离散化

参赛队号11***02参赛密码--------------

(由组圣会填写)

队员姓名*佳**梅*巍

-问题的重述

110警车在街道上巡逻，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能

够增加市民的平安感，同时也加快了接处警时间，提高了反应时效，为社会和谐供应了

有力的保障。

现给出某城市内一区域，其道路数据和地图数据已知，该区域内三个重点部位的坐

标分别为：(5112,4806),(9126,4266),(7434,1332)。该区域内共有307个道路

交叉口，为简化问题，相邻两个交叉路口之间的道路近似认为是直线，且全部事发觉场

均在下图的道路上。

该市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。设110警车

的平均巡逻速度为20km/h,接警后的平均行驶速度为40km/h。警车配置及巡逻方案要

尽量满足以下要求：

D1.警车在接警后三分钟内赶到现场的比例不低于90%；而赶到重点部位的时间必需在

两分钟之内。

D2.使巡逻效果更显著；

D3.警车巡逻规律应有肯定的隐藏性。

现在我们须要解决以下几个问题：

一.若要求满足D1,该区最少须要配置多少辆警车巡逻？

二.请给出评价巡逻效果显著程度的有关指标。

三.请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。

四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。

五.假如该区域仅配置10辆警车，应如何制定巡逻方案，使DI、D2尽量得到满足？

六.若警车接警后的平均行驶速度提高到50km/h,回答问题三。

七.你们认为还有哪些因素、哪些状况须要考虑？给出你们相应的解决方案。

-问题分析

本题为城区道路网络中警车配置及巡逻问题。在进行警车配置时，首先要考虑警车

在接警后在规定时间内赶到现场的比例，在此条件下，以车数最少为目标，建模、求解;

在制定巡逻方案时，要考虑巡逻的效果及隐藏性问题。

问题一只要求满足D1,求最少的警车配置数，可以认为警车是不动的，在三分钟

或两分钟内它能到达的区域就是它的覆盖范围。据此，在满足全部街道的覆盖率不低于

90%的条件下，找寻最优解。

问题二要评价巡逻效果，有两个方面须要考虑：一是巡逻的全面性，即经过一段时

间后警车走过的街道数占总街道数的比例；二是巡逻的不匀称性，即经过一段时间后警

车经过每一条街道的次数相差不大，用方差来衡量。

问题三是在满足D1的条件上尽量满足问题二所给的指标，并给出评价方案的指标。

首先找到一组满足D1的各警车位置,然后在和各警车位置相连的点中随机找寻一个点，

推断新的点是否满足D1,假如满足则警车行驶到该点，否则重新找寻，直到满足为止。

一段时间后统计全部车走过的点数及每个点被走过的次数，用问题二给出的两个指标进

行评价。综合两个指标，可推断此路径的好坏，重复这个过程，直到综合评价指标达到

一个满足的值为止。

问题四增加了隐藏性要求，首先给出评价隐藏性的指标，隐藏性可用路途的随机性

来评价，将它加入到问题三的模型中去进行求解。

问题五限制警车数量为10,要综合考虑DI、D2,先安排这10辆车使道路的覆盖

率最高，然后依据问题三的步骤进行求解，其中每一步对D1的推断只需使道路的覆盖

率尽量高即可。

问题六同问题三，只需将车速改为50km/h即可。

三模型的假设

1.警车都在路上巡逻，巡警去处理案件的时间不考虑；

2.全部事发觉场都在道路上，案件在道路上任一点是等概率发生的；

3.警车初始停靠点是随机的，但尽量让它们分散分布，一辆警车管辖一个分区;

4.假定各个划分区域内，较短时间内，最多会发生一个案件；

5.假设区域内的每条道路都是双行线，不考虑转弯对结果造成的影响；

6.假如重点部位不在道路上的，假设这些重点部位在离它们最近的道路上；

7.图中水域对巡逻方案没有影响。

四符号说明

m表示警车数目

d表示警车初始停靠点到各道路的最短距离

L表示整个区域的总道路长度

I表示不能在3分钟内到达的区域的道路的长度

k表示非重点部位的警车在3分钟内不能到达现场的比例

r表示三分钟内能从接警位置赶到事发觉场的最大距离是

n表示整个区域总的离散点个数

表示第i区内的节点个数

/,表示区内调整函数

t表示模拟退火的时间，表征温度值

/2表示区间调整函数

r表示全面性指标

e表示不匀称性指标

h表示综合评价指标

s,表示第i辆车经过每条道路的次数

5表示整个区域每条道路经过的平均次数

五模型的建立与算法的设计

5.1满足D1时，该区所须要配置的最少警车数目和巡逻方案

5.1.1满足D1条件时，区域最少警车的规律

题目要求警车的配置和巡逻方案满足D1要求时，整个区域所须要配置的警车数目

最少。由假设可知警车都在道路上，且全部事发觉场也都在道路上，但区域内总的道路

长度是个定值的；警车在接警后赶到事发觉场有时间限制和概率限制：三分钟内赶到一

般区域案发觉场的比例不低于90%,而赶到重点部位的时间必需限制在两分钟之内。由

此可知每辆警车的管辖范围不会很大，于是考虑将整个区域分成若干个分区，每辆警车

管辖一个分区域。

由上面的分析，求解整个区域的警车数目最少这个问题可转化为求解每一辆警车所

能管辖的街道范围尽量的大。于是我们找寻出访每辆警车管辖的范围尽量大的规律。为

了简化问题，我们不考虑赶到现场的90%的几率的限制，仅对警车能在三分钟内赶到事

发觉场的状况作定性分析，其分析示意图如图1所示。警车的初始停靠位置是随机的分

布在道路上的任一节点上，我们假设一辆警车停靠在A点上。

1

4

3

图1一辆警车管辖范围分析示意图

由于警车的平均巡逻速度为20km/h,接警后的平均行驶速度为40km/h,由于距离

信息比较简单得到，于是我们将时间限制转化为距离限制，这样便于分析和求解。当警

车接警后，在三分钟内能从接警位置赶到事发觉场的最大距离是广，其中

3

r=—x40=2km。

60

如图1所示，我们设警车初始停靠位置在A点，A点是道路1,2,3,4的道路交叉

口。我们仅以警车在道路1巡逻为例来进行分析，警车以20人?/的速度在道路1上A

到A’点之间巡逻，A'与初始停靠点A的距离为由于案件有可能在道路上任一点

发生，当警车巡逻到A点时，若案发觉场在道路2,3,4上发生时，警车以40km/h的

速度向事发觉场行驶，警车能在三分钟内从A'点赶到现场的最大距离为(2-x)人加。假

如警车在道路1上接着向前行驶，则该警车能在三分钟内赶到现场的距离接着缩小，当

警车从初始点向A点行驶但没有达到A'点时，此时该警车的最大管辖范围比警车到达4

点时的最大管辖范围大。为了使警车的管辖范围尽量大，警车的巡逻范围越小越好，当

x=0时，即警车在初始停靠点静止不动时，警车的管辖范围达到最大值2而7。

图1所分析的是特别的状况，道路1,2,3,4对称分布，现在我们来对一般的状

况进行分析，如图2所示。

图2一辆警车最大管辖范围分析示意图

图2.1所示的状况是道路分布不对称，与图1相比，图2.1所示的道路方向和角度

都发生了变更，图2.3中的情形更为困难。参照对图1的分析方法，我们分析这两种情

形下，警车巡逻时能在三分钟内赶到现场的最大距离的规律，我们只分析图2.2的状况,

道路1,2,3,4,5相交于点C,同时道路1与道路6也有个道路交叉口D,由于警车

巡逻时是在道路上行驶的，行走的路途是分段直线，并不影响路径的长度，所以当警车

巡逻到距离初始停靠点C点x远处的D,此时若有案件发生时，该警车要在三分钟内能

赶到现场处理案件，最大行驶距离在(2-x)Kn之内，假如警车在道路1上接着向前行驶,

则该警车能在三分钟内赶到现场的距离接着缩小，当警车没有行驶到D点时，此时该警

车的最大管辖范围比(2-为左根大，为了使警车的管辖范围尽量大，警车的巡逻范围越小

越好。当x=0时，即警车静止不动时，一辆警车的管辖范围能达到最大值。

以上分析的仅作定性的分析，对于三个重点部位也可以同理分析，所得的结论是一

样的，以上的分析没有考虑到90%的到达几率限制，但在设计算法须要充分考虑。

综上所述，当警车静止在初始停靠点时，在三分钟时间限制内，警车能从初始停靠

点赶到事发觉场的最大距离为20叫

5.1.2将道路离散化

由于事发觉场是等概率地分布在道路上的，由区域地图可以发觉，整个区域中的道

路长度不均，为了使计算结果更加精确，可将这些道路离散化。只要选取合适的离散方

案，就能使警车在经过道路上的离散的点时就相当于经过了这条道路。这样，不论是求

解警车初始停靠点还求解警车赶到事发觉场所经过的道路时，所计算得的的结果明显比

仅考虑整条道路的叉路口要精确得多。

区域中共有307个道路交叉口，458条道路。我们采纳线性插值方法对道路进行离散

化，以20为%的速度行走一分钟的距离作为步长，一分钟时间的选择是参照问题三的

结果要求来设定的，步长。=LX20=』K〃。用线性插值的方法，从道路的一个方向进

603

行线性插值，实现将每条道路离散化的目标，考虑到有些道路不是,％加的整数倍，我们

3

就一般状况进行探讨，其分析示意图如图3所示。道路AB长度为〃个〃与

长度的和，为了更精确处理CB段道路，那么就要考虑在CB之间是否要插入一个新的点，

依据x的长度不同，其对应的处理方式也有所不同。

CDB

-I_____I___I

-Km-Km

33

图3道路离散化分析示意图

引进临界指数y,选取y大小的准则是使尽量离散化后警车等效的平均巡逻速度和题

目给定的速度(20W/?)的差值尽量小，经过计算得y=0.189痴?时，不再插入新的坐

标点时能使整个区域的道路离散效果较好。此时，将CB段长度设定为处理，于是

3

离散后的AB道路长度会比实际长度短些；当xNO.189Xm时，须要在两个点之间再插入

一点，因为这样处理能使整个区域的整体道路的离散化效果比较志向。如图3所示，在

C与B间再插入新的坐标点，插入的位置在距C点〃的D点处,这样处理后所得的道

3

路长度比实际长度长了g-采纳这样的方法进行线性插值，我们运用MATLAB编

程实现对整个区域道路的离散，所得的离散结果如图4所示，离散后共得到762个节点,

比原始数据多了455个节点，离散后的节点数据见附件中的“newpoint.txt”。

采纳这种插值方法道路离散后，将直线上的无穷多个点转化有限个点，便于分析问

题和实现相应的算法，由图4可知，所取得的整体离散效果还是比较志向的。

5.1.3分区域求解警车数目的算法设计

考虑到警车配置和巡逻方案须要满足：警车在接警后三分钟内赶到一般部位案发觉

场的比例不低于90幅赶到重点部位必需限制在两分钟之内的要求。设计算法的目标就

是求解出在满足D1状况下，总的警车数目最小，即每个区域都尽可能多地覆盖道路节

点。由于警车的初始位置是未知的，我们可设警车初始停靠点在道路上的任一点，即分

布在图4所示的762个离散点中的某些点节点上，总体思路是让每两辆车之间尽量分散

地分布，一辆警车管辖一个分区，用这些分区覆盖整个区域。

于是我们设计算法1,步骤如下所示：

Stepl：将整个区域预安排为加个分区，每个分区安排一辆警车，警车的初始停靠位置

设在预安排区中心的道路节点上，若区域的中心不在道路节点上，则将警车放

在离中心最近的道路节点上；

Step2：统计分区不能覆盖的节点，调整警车的初始停靠点，使分区覆盖尽可能多的道

路节点，调整分为区内调整和区间调整方案：（1）区内调整依据模拟退火思想

构造的函数，在区间调整调整车辆初始点的位置（后文中有具体说明），当分区

内节点数较多时，调整的概率小些，分区内节点数较少时，调整的概率大些，（2）

当区域中存在未被覆盖的节点或节点群（大于等于三个节点集中在一个范围内）

时，将警车初始位置的调整方向为朝着这些未被覆盖的节点按肯定的规则（在

算法说明中有具体叙述）移动，同时要保证3个重点部位能在2分钟之内100%

到达；

SteP3：用Floyd算法计算出警车初始停靠点到周边各道路节点的最短距离4；

Step4：以加个划分区域未覆盖的总的道路长度/与整个区域的道路总长度L的比值

%,x100%来表示警车不能3分钟内到达现场的概率；

J.J

Step5：模拟足够多的次数，若攵＜10%,将车辆数〃，减1,跳转到Stepl；

Step6：计算结束后，比较当左W10%时所对应的加值，当加取得最小值时，记录此时

的区域划分方案，加即为最少的警车数。

对算法的几点说明：

（1）该算法所取的车辆数加是由多到少进行计算的，加初始值设为20,这个值的

选取是依据区域图估算的。

（2）预分区的优点在于使警车的初始位置尽可能匀称地分散分布，警车的初始停靠点

在一个分区的中心点旁边找寻得到，比起在整个区域随机生成停靠点，计算效率明显得

到提高。

预安排之后，须要对整个区域不断地进行调整，调整时须要考虑调整方向和调整概

率。

警车调整借鉴的是模拟退火算法的方法，为了使分区内包含道路节点数较多的分区

的初始停车点调整的概率小些，而分区内包含道路节点数的少的分区内的初始停车点调

整的概率大些，我们构造了一个调整概率函数力，

（1）式中，。力均为常数，加为整个区域车辆数，〃,为第i分区内覆盖的节点数，f

为时间，同时f也能表征模拟退火的温度变更状况：初始温度较高，区域调整速度较快,

随着时间的增加，温度不断下降，区域调整速度渐渐变慢，这个调整速度变更也是比较

符合实际状况的。

由式（1）可以得出调整概率函数力，假设在相同的温度f（时间）的条件下，由于

总的车辆数目机是定值，当〃,2%时，即第i分区内的节点数大于第/分区的节点数时，

分区i调整的概率大些，分区./的调整概率小些。分析其缘由：当分区内包含了较多的

节点个数时，该分区的警车初始停靠位置选取地比较合适了，而当分区内包含的道路节

点数较少时，说明警车的初始停靠位置没有选好，须要更也许率的调整，这样的结论也

是比较客观的。

对于全部分区外未被覆盖的道路节点和许多节点（称之为节点群），用来调整警车位

置迁移的方向，其分析示意图如图5所示。调整方案目标是使未被覆盖的节点数尽量的

少。在设计调整方向函数时，须要考虑：（1）节点群内节点的数目；（2）警车距离节点

群的位置。优先考虑距离，所以在公式(2)中，用距离的平方来描述调整方向函数。

由于某一个区域范围内的未被覆盖节点数，整个区域未被覆盖的节点总数，分区域

与未被覆盖的节点或节点群的距离等几个因素会影响到调整的方案，所以要综合考虑这

些因素。于是设计了区间调整函数人，

式中，〃，表示第，个分区内未被覆盖的节点数，表示第i分区域与未被覆盖的节

点或节点群的距离，p表示未被覆盖的节点和节点群个数。

现在简要分析第i分区按区间调整函数的调整方案，当某两节点群的节点数目相

等，但是距离不等时，如由区间调整公式可知，该区间向节点群,方向调整。

当某个分区与两个节点群的距离相等，但节点群的内节点个数不相等，如〃,〈力时，由

(4)可知，该分区域会想节点群/方向调整。

留意在整个调整过程中，调整几率限制是否调整，调整方向函数限制调整的方向，

找寻在这种调整方案下的最优结果。

图5调整分区域示意图

(3)在step3中，运用Floyd算法计算出警车初始停靠点到周边各节点的最短距离d,

目的是当区域内有状况发生时，警车能在要求的时间限制内到达现场。

(4)为求出较优的警车停靠点，采纳模拟退火算法，算出局部最优的方案。

5.1.4警车的配置和巡逻方案

运用MATLAB编程实现算法1得到，整个区域配备13辆警车，这些警车静止在初始

停靠点时，能满足D1要求。警车的初始停靠位置分别为道路交叉节点6,25,30,37,

82,84,110,111,126,214,253,258,278处。每个警车所管辖的交叉点(原始的

交叉节点)如图6所示，求解的分区结果见附录所示。

9000

图6满足D1条件下的区分划分图

13个分区共覆盖了252个交叉点，另外的55个原始交叉点没有被这些分区域覆盖：

137,138,151,159,167,168,170,174,175,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。在这种分区方案下，这些点中，每

两个相连的点间的道路离散值长度占整个区域总的长度的比值为

^=1xl00%=90.18%o因此，在整个区域配置13辆警车，每个警车在初始停靠点静

止不动，当有案件发生时，离案发觉场最近的警车从初始停靠点赶到现场。

5.2评价巡逻效果显著的指标

110警车在街道上巡逻是目的是为了对违法犯罪分子起到震慑作用，降低犯罪率，

又能够增加市民的平安感，同时还加快了接处警（接受报警并赶往现场处理事务）时间，

提高了反应时效，为社会和谐供应了有力的保障。巡警在城市繁华街道、公共场所执行

巡逻任务，维护治安，服务群众，可以得良好的社会效应

在整个区域中，由于案发觉场都在道路上，道路上的每一点都是等概率发生的，因

此警车巡逻的面越广，所巡逻的街道数目越多，警车的巡逻效果就越好，对违法犯罪分

子就越有威慑力，警车也能更刚好地处理案件。

我们采纳全面性r来衡量巡逻的效果显著性，即用警车巡逻所经过的街道节点数占

区域总节点数的比值。当警车重复经过同一条街道同一个离散点时，c仅记录一次。

r=—(3)

n

式中，c表示警车经过的离散点数，鹿代表整个区域总的离散点数。r值越大，表

明警车所经过的街道数目越多，所取得的效果越显著。

同时考虑到在巡逻过程中可能会出现这样的状况：在相同的时段内，警车会多次巡

逻部分街道，而一些街道却很少巡逻甚至没有警车到达，这样会造成一些巡逻盲区。分

布很不均衡。这样就可能出现巡逻密度大的街道上的违法犯罪分子不敢在街道上作案，

而流窜到巡逻密度稀疏的街道上作案，因此在相同的警车数目条件下，密度不均衡的巡

逻方式的巡逻效果的效果较差，而密度较均衡的巡逻方式所取得的巡逻效果会更好些。

我们引入一个巡逻的不匀称度e来衡量巡逻效果的显著性，考虑到方差能表示不均衡度,

于是我们用方差的大小来表征不均衡，方差越大，巡逻密度越不均衡，所取得的巡逻效

果越差。

(4)

问题1所给出的满足D1条件下的警车数目为13辆，这时每辆警车在初始停靠点静

止不动，只有该管辖区域内发生了案件时，警车才从初始停靠点赶到案发觉场处理案件。

当警车在巡逻状态时，所须要考虑的问题就更困难一些，如当节点运动时，警车还能否

达到D1的要求，警车的运动方向如何等问题，但基本算法思想与问题1类似，所得的

算法2的框图如图7所示，

为了简化问题，我们假设各分区警车的巡逻时候，尽量保证全部的警车的行驶方向

相一样，且警车都走双行道，即当警车走到某个节点后，它们又同时返回初始停靠点，

警车的行驶方向有四种方式，如6所示。

在图6中，数字1代表走巡逻走的第一步，2