2023全國大學生數(shù)學建模競賽A題參考答案

城市表層土壤重金屬污染分析

隨著城市經(jīng)濟的快速發(fā)展和城市人口的不斷增加，人類活動對城市環(huán)境質(zhì)量的影響

日顯突出。對城市土壤地質(zhì)環(huán)境異樣的查證，以及如何應(yīng)用查證獲得的海量數(shù)據(jù)資料開

展城市環(huán)境質(zhì)量評價，探討人類活動影響下城市地質(zhì)環(huán)境的演化模式，日益成為人們關(guān)

注的焦點。

依據(jù)功能劃分，城區(qū)一般可分為生活區(qū)、工業(yè)區(qū)、山區(qū)、主干道路區(qū)及公園綠地區(qū)

等，分別記為1類區(qū)、2類區(qū)、……、5類區(qū)，不同的區(qū)域環(huán)境受人類活動影響的程度

不同。

現(xiàn)對某城市城區(qū)土壤地質(zhì)環(huán)境進行調(diào)查。為此，將所考察的城區(qū)劃分為間距1公里

左右的網(wǎng)格子區(qū)域，依據(jù)每平方公里1個采樣點對表層土(0~10厘米深度)進行取樣、

編號，并用GPS記錄采樣點的位置。應(yīng)用特地儀器測試分析，獲得了每個樣本所含的

多種化學元素的濃度數(shù)據(jù)。另一方面，依據(jù)2公里的間距在那些遠離人群及工業(yè)活動的

自然區(qū)取樣，將其作為該城區(qū)表層土壤中元素的背景值。

附件1列出了采樣點的位置、海拔高度及其所屬功能區(qū)等信息，附件2列出了8種

主要重金屬元素在采樣點處的濃度，附件3列出了8種主要重金屬元素的背景值。

現(xiàn)要求你們通過數(shù)學建模來完成以下任務(wù)：

(1)給出8種主要重金屬元素在該城區(qū)的空間分布，并分析該城區(qū)內(nèi)不同區(qū)域重金

屬的污染程度。

(2)通過數(shù)據(jù)分析，說明重金屬污染的主要緣由。

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

(4)分析你所建立模型的優(yōu)缺點，為更好地探討城市地質(zhì)環(huán)境的演化模式，還應(yīng)收

集什么信息？有了這些信息，如何建立模型解決問題?

摘要：

本文探討的是某城區(qū)警車配置及巡邏方案的制定問題，建立了求解警車巡邏方案的

模型，并在滿足D1的條件下給出了巡邏效果最好的方案。

在設(shè)計整個區(qū)域配置最少巡邏車輛時，本文設(shè)計了算法1：先將道路離散化成近似

勻稱分布的節(jié)點，相鄰兩個節(jié)點之間的距離約等于一分鐘巡邏路程。由警車的數(shù)目〃?，

將全區(qū)劃分成加個勻稱的分區(qū)，從每個分區(qū)的中心點動身，找到最近的道路節(jié)點，作為

警車的初始位置，由Floyd算法算出每輛警車3分鐘或2分鐘行駛路程范圍內(nèi)的節(jié)點。

考慮區(qū)域調(diào)整的概率大小和方向不同會影響調(diào)整結(jié)果，本文利用模擬退火算法構(gòu)造出遷

移幾率函數(shù)，用遷移方向函數(shù)確定分區(qū)的調(diào)整方向。計算能滿足D1的最小車輛數(shù)，即

為該區(qū)應(yīng)當配置的最小警車數(shù)目，用MATLAB計算，得到局部最優(yōu)解為13輛。

在選取巡邏顯著性指標時，本文考慮了兩個方面的指標：一是全面性，即全部警車

走過的街道節(jié)點數(shù)占總街道節(jié)點數(shù)的比例，用兩者之比來評價；二是勻稱性，即全部警

車經(jīng)過每個節(jié)點數(shù)的次數(shù)偏離平均經(jīng)過次數(shù)的程度，用方差值來大小評價。

問題三：為簡化問題，假設(shè)全部警車在同一時刻，大致向同一方向巡邏，運動狀態(tài)

分為四種：向左，向右，向上，向下，記錄每個時刻，警車經(jīng)過的節(jié)點和能夠趕去處理

事故的點，最終匯總計算得相應(yīng)的評價指標。

在考慮巡邏規(guī)律隱藏性要求時，文本將巡邏路途進行隨機處理，方向是不確定的，

采納算法2進行計算，得出相應(yīng)巡邏顯著指標，當車輛數(shù)削減到10輛或巡邏速度變大

時，用算法2計算巡邏方案和對應(yīng)的參數(shù)，結(jié)果見附錄所示。

本文最終還考慮到4個額外因素，給出每個影響因素的解決方案。

關(guān)鍵詞：模擬退火算法；Floyd算法；離散化

參賽隊號11***02參賽密碼--------------

(由組圣會填寫)

隊員姓名*佳**梅*巍

-問題的重述

110警車在街道上巡邏，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能

夠增加市民的平安感，同時也加快了接處警時間，提高了反應(yīng)時效，為社會和諧供應(yīng)了

有力的保障。

現(xiàn)給出某城市內(nèi)一區(qū)域，其道路數(shù)據(jù)和地圖數(shù)據(jù)已知，該區(qū)域內(nèi)三個重點部位的坐

標分別為：(5112,4806),(9126,4266),(7434,1332)。該區(qū)域內(nèi)共有307個道路

交叉口，為簡化問題，相鄰兩個交叉路口之間的道路近似認為是直線，且全部事發(fā)覺場

均在下圖的道路上。

該市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進通訊設(shè)備的110警車。設(shè)110警車

的平均巡邏速度為20km/h,接警后的平均行駛速度為40km/h。警車配置及巡邏方案要

盡量滿足以下要求：

D1.警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于90%；而趕到重點部位的時間必需在

兩分鐘之內(nèi)。

D2.使巡邏效果更顯著；

D3.警車巡邏規(guī)律應(yīng)有肯定的隱藏性。

現(xiàn)在我們須要解決以下幾個問題：

一.若要求滿足D1,該區(qū)最少須要配置多少輛警車巡邏？

二.請給出評價巡邏效果顯著程度的有關(guān)指標。

三.請給出滿足D1且盡量滿足D2條件的警車巡邏方案及其評價指標值。

四.在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評價指標值。

五.假如該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使DI、D2盡量得到滿足？

六.若警車接警后的平均行駛速度提高到50km/h,回答問題三。

七.你們認為還有哪些因素、哪些狀況須要考慮？給出你們相應(yīng)的解決方案。

-問題分析

本題為城區(qū)道路網(wǎng)絡(luò)中警車配置及巡邏問題。在進行警車配置時，首先要考慮警車

在接警后在規(guī)定時間內(nèi)趕到現(xiàn)場的比例，在此條件下，以車數(shù)最少為目標，建模、求解;

在制定巡邏方案時，要考慮巡邏的效果及隱藏性問題。

問題一只要求滿足D1,求最少的警車配置數(shù)，可以認為警車是不動的，在三分鐘

或兩分鐘內(nèi)它能到達的區(qū)域就是它的覆蓋范圍。據(jù)此，在滿足全部街道的覆蓋率不低于

90%的條件下，找尋最優(yōu)解。

問題二要評價巡邏效果，有兩個方面須要考慮：一是巡邏的全面性，即經(jīng)過一段時

間后警車走過的街道數(shù)占總街道數(shù)的比例；二是巡邏的不勻稱性，即經(jīng)過一段時間后警

車經(jīng)過每一條街道的次數(shù)相差不大，用方差來衡量。

問題三是在滿足D1的條件上盡量滿足問題二所給的指標，并給出評價方案的指標。

首先找到一組滿足D1的各警車位置,然后在和各警車位置相連的點中隨機找尋一個點，

推斷新的點是否滿足D1,假如滿足則警車行駛到該點，否則重新找尋，直到滿足為止。

一段時間后統(tǒng)計全部車走過的點數(shù)及每個點被走過的次數(shù)，用問題二給出的兩個指標進

行評價。綜合兩個指標，可推斷此路徑的好壞，重復這個過程，直到綜合評價指標達到

一個滿足的值為止。

問題四增加了隱藏性要求，首先給出評價隱藏性的指標，隱藏性可用路途的隨機性

來評價，將它加入到問題三的模型中去進行求解。

問題五限制警車數(shù)量為10,要綜合考慮DI、D2,先安排這10輛車使道路的覆蓋

率最高，然后依據(jù)問題三的步驟進行求解，其中每一步對D1的推斷只需使道路的覆蓋

率盡量高即可。

問題六同問題三，只需將車速改為50km/h即可。

三模型的假設(shè)

1.警車都在路上巡邏，巡警去處理案件的時間不考慮；

2.全部事發(fā)覺場都在道路上，案件在道路上任一點是等概率發(fā)生的；

3.警車初始?？奎c是隨機的，但盡量讓它們分散分布，一輛警車管轄一個分區(qū);

4.假定各個劃分區(qū)域內(nèi)，較短時間內(nèi)，最多會發(fā)生一個案件；

5.假設(shè)區(qū)域內(nèi)的每條道路都是雙行線，不考慮轉(zhuǎn)彎對結(jié)果造成的影響；

6.假如重點部位不在道路上的，假設(shè)這些重點部位在離它們最近的道路上；

7.圖中水域?qū)ρ策壏桨笡]有影響。

四符號說明

m表示警車數(shù)目

d表示警車初始?？奎c到各道路的最短距離

L表示整個區(qū)域的總道路長度

I表示不能在3分鐘內(nèi)到達的區(qū)域的道路的長度

k表示非重點部位的警車在3分鐘內(nèi)不能到達現(xiàn)場的比例

r表示三分鐘內(nèi)能從接警位置趕到事發(fā)覺場的最大距離是

n表示整個區(qū)域總的離散點個數(shù)

表示第i區(qū)內(nèi)的節(jié)點個數(shù)

/,表示區(qū)內(nèi)調(diào)整函數(shù)

t表示模擬退火的時間，表征溫度值

/2表示區(qū)間調(diào)整函數(shù)

r表示全面性指標

e表示不勻稱性指標

h表示綜合評價指標

s,表示第i輛車經(jīng)過每條道路的次數(shù)

5表示整個區(qū)域每條道路經(jīng)過的平均次數(shù)

五模型的建立與算法的設(shè)計

5.1滿足D1時，該區(qū)所須要配置的最少警車數(shù)目和巡邏方案

5.1.1滿足D1條件時，區(qū)域最少警車的規(guī)律

題目要求警車的配置和巡邏方案滿足D1要求時，整個區(qū)域所須要配置的警車數(shù)目

最少。由假設(shè)可知警車都在道路上，且全部事發(fā)覺場也都在道路上，但區(qū)域內(nèi)總的道路

長度是個定值的；警車在接警后趕到事發(fā)覺場有時間限制和概率限制：三分鐘內(nèi)趕到一

般區(qū)域案發(fā)覺場的比例不低于90%,而趕到重點部位的時間必需限制在兩分鐘之內(nèi)。由

此可知每輛警車的管轄范圍不會很大，于是考慮將整個區(qū)域分成若干個分區(qū)，每輛警車

管轄一個分區(qū)域。

由上面的分析，求解整個區(qū)域的警車數(shù)目最少這個問題可轉(zhuǎn)化為求解每一輛警車所

能管轄的街道范圍盡量的大。于是我們找尋出訪每輛警車管轄的范圍盡量大的規(guī)律。為

了簡化問題，我們不考慮趕到現(xiàn)場的90%的幾率的限制，僅對警車能在三分鐘內(nèi)趕到事

發(fā)覺場的狀況作定性分析，其分析示意圖如圖1所示。警車的初始?？课恢檬请S機的分

布在道路上的任一節(jié)點上，我們假設(shè)一輛警車停靠在A點上。

1

4

3

圖1一輛警車管轄范圍分析示意圖

由于警車的平均巡邏速度為20km/h,接警后的平均行駛速度為40km/h,由于距離

信息比較簡單得到，于是我們將時間限制轉(zhuǎn)化為距離限制，這樣便于分析和求解。當警

車接警后，在三分鐘內(nèi)能從接警位置趕到事發(fā)覺場的最大距離是廣，其中

3

r=—x40=2km。

60

如圖1所示，我們設(shè)警車初始?？课恢迷贏點，A點是道路1,2,3,4的道路交叉

口。我們僅以警車在道路1巡邏為例來進行分析，警車以20人?/的速度在道路1上A

到A’點之間巡邏，A'與初始?？奎cA的距離為由于案件有可能在道路上任一點

發(fā)生，當警車巡邏到A點時，若案發(fā)覺場在道路2,3,4上發(fā)生時，警車以40km/h的

速度向事發(fā)覺場行駛，警車能在三分鐘內(nèi)從A'點趕到現(xiàn)場的最大距離為(2-x)人加。假

如警車在道路1上接著向前行駛，則該警車能在三分鐘內(nèi)趕到現(xiàn)場的距離接著縮小，當

警車從初始點向A點行駛但沒有達到A'點時，此時該警車的最大管轄范圍比警車到達4

點時的最大管轄范圍大。為了使警車的管轄范圍盡量大，警車的巡邏范圍越小越好，當

x=0時，即警車在初始?？奎c靜止不動時，警車的管轄范圍達到最大值2而7。

圖1所分析的是特別的狀況，道路1,2,3,4對稱分布，現(xiàn)在我們來對一般的狀

況進行分析，如圖2所示。

圖2一輛警車最大管轄范圍分析示意圖

圖2.1所示的狀況是道路分布不對稱，與圖1相比，圖2.1所示的道路方向和角度

都發(fā)生了變更，圖2.3中的情形更為困難。參照對圖1的分析方法，我們分析這兩種情

形下，警車巡邏時能在三分鐘內(nèi)趕到現(xiàn)場的最大距離的規(guī)律，我們只分析圖2.2的狀況,

道路1,2,3,4,5相交于點C,同時道路1與道路6也有個道路交叉口D,由于警車

巡邏時是在道路上行駛的，行走的路途是分段直線，并不影響路徑的長度，所以當警車

巡邏到距離初始?？奎cC點x遠處的D,此時若有案件發(fā)生時，該警車要在三分鐘內(nèi)能

趕到現(xiàn)場處理案件，最大行駛距離在(2-x)Kn之內(nèi)，假如警車在道路1上接著向前行駛,

則該警車能在三分鐘內(nèi)趕到現(xiàn)場的距離接著縮小，當警車沒有行駛到D點時，此時該警

車的最大管轄范圍比(2-為左根大，為了使警車的管轄范圍盡量大，警車的巡邏范圍越小

越好。當x=0時，即警車靜止不動時，一輛警車的管轄范圍能達到最大值。

以上分析的僅作定性的分析，對于三個重點部位也可以同理分析，所得的結(jié)論是一

樣的，以上的分析沒有考慮到90%的到達幾率限制，但在設(shè)計算法須要充分考慮。

綜上所述，當警車靜止在初始?？奎c時，在三分鐘時間限制內(nèi)，警車能從初始?？?/p>

點趕到事發(fā)覺場的最大距離為20叫

5.1.2將道路離散化

由于事發(fā)覺場是等概率地分布在道路上的，由區(qū)域地圖可以發(fā)覺，整個區(qū)域中的道

路長度不均，為了使計算結(jié)果更加精確，可將這些道路離散化。只要選取合適的離散方

案，就能使警車在經(jīng)過道路上的離散的點時就相當于經(jīng)過了這條道路。這樣，不論是求

解警車初始?？奎c還求解警車趕到事發(fā)覺場所經(jīng)過的道路時，所計算得的的結(jié)果明顯比

僅考慮整條道路的叉路口要精確得多。

區(qū)域中共有307個道路交叉口，458條道路。我們采納線性插值方法對道路進行離散

化，以20為%的速度行走一分鐘的距離作為步長，一分鐘時間的選擇是參照問題三的

結(jié)果要求來設(shè)定的，步長。=LX20=』K〃。用線性插值的方法，從道路的一個方向進

603

行線性插值，實現(xiàn)將每條道路離散化的目標，考慮到有些道路不是,％加的整數(shù)倍，我們

3

就一般狀況進行探討，其分析示意圖如圖3所示。道路AB長度為〃個〃與

長度的和，為了更精確處理CB段道路，那么就要考慮在CB之間是否要插入一個新的點，

依據(jù)x的長度不同，其對應(yīng)的處理方式也有所不同。

CDB

-I_____I___I

-Km-Km

33

圖3道路離散化分析示意圖

引進臨界指數(shù)y,選取y大小的準則是使盡量離散化后警車等效的平均巡邏速度和題

目給定的速度(20W/?)的差值盡量小，經(jīng)過計算得y=0.189癡?時，不再插入新的坐

標點時能使整個區(qū)域的道路離散效果較好。此時，將CB段長度設(shè)定為處理，于是

3

離散后的AB道路長度會比實際長度短些；當xNO.189Xm時，須要在兩個點之間再插入

一點，因為這樣處理能使整個區(qū)域的整體道路的離散化效果比較志向。如圖3所示，在

C與B間再插入新的坐標點，插入的位置在距C點〃的D點處,這樣處理后所得的道

3

路長度比實際長度長了g-采納這樣的方法進行線性插值，我們運用MATLAB編

程實現(xiàn)對整個區(qū)域道路的離散，所得的離散結(jié)果如圖4所示，離散后共得到762個節(jié)點,

比原始數(shù)據(jù)多了455個節(jié)點，離散后的節(jié)點數(shù)據(jù)見附件中的“newpoint.txt”。

采納這種插值方法道路離散后，將直線上的無窮多個點轉(zhuǎn)化有限個點，便于分析問

題和實現(xiàn)相應(yīng)的算法，由圖4可知，所取得的整體離散效果還是比較志向的。

5.1.3分區(qū)域求解警車數(shù)目的算法設(shè)計

考慮到警車配置和巡邏方案須要滿足：警車在接警后三分鐘內(nèi)趕到一般部位案發(fā)覺

場的比例不低于90幅趕到重點部位必需限制在兩分鐘之內(nèi)的要求。設(shè)計算法的目標就

是求解出在滿足D1狀況下，總的警車數(shù)目最小，即每個區(qū)域都盡可能多地覆蓋道路節(jié)

點。由于警車的初始位置是未知的，我們可設(shè)警車初始?？奎c在道路上的任一點，即分

布在圖4所示的762個離散點中的某些點節(jié)點上，總體思路是讓每兩輛車之間盡量分散

地分布，一輛警車管轄一個分區(qū)，用這些分區(qū)覆蓋整個區(qū)域。

于是我們設(shè)計算法1,步驟如下所示：

Stepl：將整個區(qū)域預安排為加個分區(qū)，每個分區(qū)安排一輛警車，警車的初始?？课恢?/p>

設(shè)在預安排區(qū)中心的道路節(jié)點上，若區(qū)域的中心不在道路節(jié)點上，則將警車放

在離中心最近的道路節(jié)點上；

Step2：統(tǒng)計分區(qū)不能覆蓋的節(jié)點，調(diào)整警車的初始?？奎c，使分區(qū)覆蓋盡可能多的道

路節(jié)點，調(diào)整分為區(qū)內(nèi)調(diào)整和區(qū)間調(diào)整方案：（1）區(qū)內(nèi)調(diào)整依據(jù)模擬退火思想

構(gòu)造的函數(shù)，在區(qū)間調(diào)整調(diào)整車輛初始點的位置（后文中有具體說明），當分區(qū)

內(nèi)節(jié)點數(shù)較多時，調(diào)整的概率小些，分區(qū)內(nèi)節(jié)點數(shù)較少時，調(diào)整的概率大些，（2）

當區(qū)域中存在未被覆蓋的節(jié)點或節(jié)點群（大于等于三個節(jié)點集中在一個范圍內(nèi)）

時，將警車初始位置的調(diào)整方向為朝著這些未被覆蓋的節(jié)點按肯定的規(guī)則（在

算法說明中有具體敘述）移動，同時要保證3個重點部位能在2分鐘之內(nèi)100%

到達；

SteP3：用Floyd算法計算出警車初始?？奎c到周邊各道路節(jié)點的最短距離4；

Step4：以加個劃分區(qū)域未覆蓋的總的道路長度/與整個區(qū)域的道路總長度L的比值

%,x100%來表示警車不能3分鐘內(nèi)到達現(xiàn)場的概率；

J.J

Step5：模擬足夠多的次數(shù)，若攵＜10%,將車輛數(shù)〃，減1,跳轉(zhuǎn)到Stepl；

Step6：計算結(jié)束后，比較當左W10%時所對應(yīng)的加值，當加取得最小值時，記錄此時

的區(qū)域劃分方案，加即為最少的警車數(shù)。

對算法的幾點說明：

（1）該算法所取的車輛數(shù)加是由多到少進行計算的，加初始值設(shè)為20,這個值的

選取是依據(jù)區(qū)域圖估算的。

（2）預分區(qū)的優(yōu)點在于使警車的初始位置盡可能勻稱地分散分布，警車的初始?？奎c

在一個分區(qū)的中心點旁邊找尋得到，比起在整個區(qū)域隨機生成?？奎c，計算效率明顯得

到提高。

預安排之后，須要對整個區(qū)域不斷地進行調(diào)整，調(diào)整時須要考慮調(diào)整方向和調(diào)整概

率。

警車調(diào)整借鑒的是模擬退火算法的方法，為了使分區(qū)內(nèi)包含道路節(jié)點數(shù)較多的分區(qū)

的初始停車點調(diào)整的概率小些，而分區(qū)內(nèi)包含道路節(jié)點數(shù)的少的分區(qū)內(nèi)的初始停車點調(diào)

整的概率大些，我們構(gòu)造了一個調(diào)整概率函數(shù)力，

（1）式中，。力均為常數(shù)，加為整個區(qū)域車輛數(shù)，〃,為第i分區(qū)內(nèi)覆蓋的節(jié)點數(shù)，f

為時間，同時f也能表征模擬退火的溫度變更狀況：初始溫度較高，區(qū)域調(diào)整速度較快,

隨著時間的增加，溫度不斷下降，區(qū)域調(diào)整速度漸漸變慢，這個調(diào)整速度變更也是比較

符合實際狀況的。

由式（1）可以得出調(diào)整概率函數(shù)力，假設(shè)在相同的溫度f（時間）的條件下，由于

總的車輛數(shù)目機是定值，當〃,2%時，即第i分區(qū)內(nèi)的節(jié)點數(shù)大于第/分區(qū)的節(jié)點數(shù)時，

分區(qū)i調(diào)整的概率大些，分區(qū)./的調(diào)整概率小些。分析其緣由：當分區(qū)內(nèi)包含了較多的

節(jié)點個數(shù)時，該分區(qū)的警車初始?？课恢眠x取地比較合適了，而當分區(qū)內(nèi)包含的道路節(jié)

點數(shù)較少時，說明警車的初始?？课恢脹]有選好，須要更也許率的調(diào)整，這樣的結(jié)論也

是比較客觀的。

對于全部分區(qū)外未被覆蓋的道路節(jié)點和許多節(jié)點（稱之為節(jié)點群），用來調(diào)整警車位

置遷移的方向，其分析示意圖如圖5所示。調(diào)整方案目標是使未被覆蓋的節(jié)點數(shù)盡量的

少。在設(shè)計調(diào)整方向函數(shù)時，須要考慮：（1）節(jié)點群內(nèi)節(jié)點的數(shù)目；（2）警車距離節(jié)點

群的位置。優(yōu)先考慮距離，所以在公式(2)中，用距離的平方來描述調(diào)整方向函數(shù)。

由于某一個區(qū)域范圍內(nèi)的未被覆蓋節(jié)點數(shù)，整個區(qū)域未被覆蓋的節(jié)點總數(shù)，分區(qū)域

與未被覆蓋的節(jié)點或節(jié)點群的距離等幾個因素會影響到調(diào)整的方案，所以要綜合考慮這

些因素。于是設(shè)計了區(qū)間調(diào)整函數(shù)人，

式中，〃，表示第，個分區(qū)內(nèi)未被覆蓋的節(jié)點數(shù)，表示第i分區(qū)域與未被覆蓋的節(jié)

點或節(jié)點群的距離，p表示未被覆蓋的節(jié)點和節(jié)點群個數(shù)。

現(xiàn)在簡要分析第i分區(qū)按區(qū)間調(diào)整函數(shù)的調(diào)整方案，當某兩節(jié)點群的節(jié)點數(shù)目相

等，但是距離不等時，如由區(qū)間調(diào)整公式可知，該區(qū)間向節(jié)點群,方向調(diào)整。

當某個分區(qū)與兩個節(jié)點群的距離相等，但節(jié)點群的內(nèi)節(jié)點個數(shù)不相等，如〃,〈力時，由

(4)可知，該分區(qū)域會想節(jié)點群/方向調(diào)整。

留意在整個調(diào)整過程中，調(diào)整幾率限制是否調(diào)整，調(diào)整方向函數(shù)限制調(diào)整的方向，

找尋在這種調(diào)整方案下的最優(yōu)結(jié)果。

圖5調(diào)整分區(qū)域示意圖

(3)在step3中，運用Floyd算法計算出警車初始?？奎c到周邊各節(jié)點的最短距離d,

目的是當區(qū)域內(nèi)有狀況發(fā)生時，警車能在要求的時間限制內(nèi)到達現(xiàn)場。

(4)為求出較優(yōu)的警車?？奎c，采納模擬退火算法，算出局部最優(yōu)的方案。

5.1.4警車的配置和巡邏方案

運用MATLAB編程實現(xiàn)算法1得到，整個區(qū)域配備13輛警車，這些警車靜止在初始

?？奎c時，能滿足D1要求。警車的初始?？课恢梅謩e為道路交叉節(jié)點6,25,30,37,

82,84,110,111,126,214,253,258,278處。每個警車所管轄的交叉點(原始的

交叉節(jié)點)如圖6所示，求解的分區(qū)結(jié)果見附錄所示。

9000

圖6滿足D1條件下的區(qū)分劃分圖

13個分區(qū)共覆蓋了252個交叉點，另外的55個原始交叉點沒有被這些分區(qū)域覆蓋：

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。在這種分區(qū)方案下，這些點中，每

兩個相連的點間的道路離散值長度占整個區(qū)域總的長度的比值為

^=1xl00%=90.18%o因此，在整個區(qū)域配置13輛警車，每個警車在初始?？奎c靜

止不動，當有案件發(fā)生時，離案發(fā)覺場最近的警車從初始?？奎c趕到現(xiàn)場。

5.2評價巡邏效果顯著的指標

110警車在街道上巡邏是目的是為了對違法犯罪分子起到震懾作用，降低犯罪率，

又能夠增加市民的平安感，同時還加快了接處警（接受報警并趕往現(xiàn)場處理事務(wù)）時間，

提高了反應(yīng)時效，為社會和諧供應(yīng)了有力的保障。巡警在城市繁華街道、公共場所執(zhí)行

巡邏任務(wù)，維護治安，服務(wù)群眾，可以得良好的社會效應(yīng)

在整個區(qū)域中，由于案發(fā)覺場都在道路上，道路上的每一點都是等概率發(fā)生的，因

此警車巡邏的面越廣，所巡邏的街道數(shù)目越多，警車的巡邏效果就越好，對違法犯罪分

子就越有威懾力，警車也能更剛好地處理案件。

我們采納全面性r來衡量巡邏的效果顯著性，即用警車巡邏所經(jīng)過的街道節(jié)點數(shù)占

區(qū)域總節(jié)點數(shù)的比值。當警車重復經(jīng)過同一條街道同一個離散點時，c僅記錄一次。

r=—(3)

n

式中，c表示警車經(jīng)過的離散點數(shù)，鹿代表整個區(qū)域總的離散點數(shù)。r值越大，表

明警車所經(jīng)過的街道數(shù)目越多，所取得的效果越顯著。

同時考慮到在巡邏過程中可能會出現(xiàn)這樣的狀況：在相同的時段內(nèi)，警車會多次巡

邏部分街道，而一些街道卻很少巡邏甚至沒有警車到達，這樣會造成一些巡邏盲區(qū)。分

布很不均衡。這樣就可能出現(xiàn)巡邏密度大的街道上的違法犯罪分子不敢在街道上作案，

而流竄到巡邏密度稀疏的街道上作案，因此在相同的警車數(shù)目條件下，密度不均衡的巡

邏方式的巡邏效果的效果較差，而密度較均衡的巡邏方式所取得的巡邏效果會更好些。

我們引入一個巡邏的不勻稱度e來衡量巡邏效果的顯著性，考慮到方差能表示不均衡度,

于是我們用方差的大小來表征不均衡，方差越大，巡邏密度越不均衡，所取得的巡邏效

果越差。

(4)

問題1所給出的滿足D1條件下的警車數(shù)目為13輛，這時每輛警車在初始?？奎c靜

止不動，只有該管轄區(qū)域內(nèi)發(fā)生了案件時，警車才從初始?？奎c趕到案發(fā)覺場處理案件。

當警車在巡邏狀態(tài)時，所須要考慮的問題就更困難一些，如當節(jié)點運動時，警車還能否

達到D1的要求，警車的運動方向如何等問題，但基本算法思想與問題1類似，所得的

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

為了簡化問題，我們假設(shè)各分區(qū)警車的巡邏時候，盡量保證全部的警車的行駛方向

相一樣，且警車都走雙行道，即當警車走到某個節(jié)點后，它們又同時返回初始?？奎c，

警車的行駛方向有四種方式，如6所示。

在圖6中，數(shù)字1代表走巡邏走的第一步，2