黑巖小說

數(shù)學(xué)建模（第4頁）

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

考慮到警車配置和巡邏方案需要滿足：警車在接警后叁分鐘內(nèi)趕到普通部位案發(fā)現(xiàn)場(chǎng)的比例不低于90，趕到重點(diǎn)部位必須控制在兩分鐘之內(nèi)的要求。設(shè)計(jì)算法的目標(biāo)就是求解出在滿足d1情況下，總的警車數(shù)目最小，即每個(gè)區(qū)域都盡可能多地覆蓋道路節(jié)點(diǎn)。由于警車的初始位置是未知的，我們可設(shè)警車初始?？奎c(diǎn)在道路上的任一點(diǎn)，即分布在圖4所示的762個(gè)離散點(diǎn)中的某些點(diǎn)節(jié)點(diǎn)上，總體思路是讓每?jī)奢v車之間盡量分散地分布，一輛警車管轄一個(gè)分區(qū)，用這些分區(qū)覆蓋整個(gè)區(qū)域。

于是我們?cè)O(shè)計(jì)算法1，步驟如下所示：

step1：將整個(gè)區(qū)域預(yù)分配為個(gè)分區(qū)，每個(gè)分區(qū)分配一輛警車，警車的初始?？课恢迷O(shè)在預(yù)分配區(qū)中心的道路節(jié)點(diǎn)上，假設(shè)區(qū)域的中心不在道路節(jié)點(diǎn)上，那么將警車放在離中心最近的道路節(jié)點(diǎn)上；

step2：統(tǒng)計(jì)分區(qū)不能覆蓋的節(jié)點(diǎn)，調(diào)整警車的初始停靠點(diǎn)，使分區(qū)覆蓋盡可能多的道路節(jié)點(diǎn)，調(diào)整分為區(qū)內(nèi)調(diào)整和區(qū)間調(diào)整方案：〔1〕區(qū)內(nèi)調(diào)整按照模擬退火思想構(gòu)造的函數(shù)，在區(qū)間調(diào)整調(diào)整車輛初始點(diǎn)的位置〔后文中有詳細(xì)說明〕，當(dāng)分區(qū)內(nèi)節(jié)點(diǎn)數(shù)較多時(shí)，調(diào)整的概率小些，分區(qū)內(nèi)節(jié)點(diǎn)數(shù)較少時(shí)，調(diào)整的概率大些，〔2〕當(dāng)區(qū)域中存在未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群〔大于等于叁個(gè)節(jié)點(diǎn)集中在一個(gè)范圍內(nèi)〕時(shí)，將警車初始位置的調(diào)整方向?yàn)槌@些未被覆蓋的節(jié)點(diǎn)按一定的規(guī)那么〔在

對(duì)算法的幾點(diǎn)說明：

〔1〕該算法所取的車輛數(shù)是由多到少進(jìn)行計(jì)算的，初始值設(shè)為20，這個(gè)值的選取是根據(jù)區(qū)域圖估算的。

（2）預(yù)分區(qū)的優(yōu)點(diǎn)在于使警車的初始位置盡可能均勻地分散分布，警車的初始?？奎c(diǎn)在一個(gè)分區(qū)的中心點(diǎn)附近尋找得到，比起在整個(gè)區(qū)域隨機(jī)生成?？奎c(diǎn)，計(jì)算效率明顯得到提高。

預(yù)分配之后，需要對(duì)整個(gè)區(qū)域不斷地進(jìn)行調(diào)整，調(diào)整時(shí)需要考慮調(diào)整方向和調(diào)整概率。

警車調(diào)整借鑒的是模擬退火算法的方法，為了使分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)較多的分區(qū)的初始停車點(diǎn)調(diào)整的概率小些，而分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)的少的分區(qū)內(nèi)的初始停車點(diǎn)調(diào)整的概率大些，我們構(gòu)造了一個(gè)調(diào)整概率函數(shù)，

〔1〕

〔1〕式中，均為常數(shù)，為整個(gè)區(qū)域車輛數(shù)，為第分區(qū)內(nèi)覆蓋的節(jié)點(diǎn)數(shù)，為時(shí)間，同時(shí)也能表征模擬退火的溫度變化情況：初始溫度較高，區(qū)域調(diào)整速度較快，隨著時(shí)間的增加，溫度不斷下降，區(qū)域調(diào)整速度逐漸變慢，這個(gè)調(diào)整速度變化也是比擬符合實(shí)際情況的。

由式〔1〕可以得出調(diào)整概率函數(shù)，假設(shè)在相同的溫度〔時(shí)間〕的條件下，由于總的車輛數(shù)目是定值，當(dāng)時(shí)，即第分區(qū)內(nèi)的節(jié)點(diǎn)數(shù)大于第分區(qū)的節(jié)點(diǎn)數(shù)時(shí)，分區(qū)調(diào)整的概率大些，分區(qū)的調(diào)整概率小些。分析其原因：當(dāng)分區(qū)內(nèi)包含了較多的節(jié)點(diǎn)個(gè)數(shù)時(shí)，該分區(qū)的警車初始?？课恢眠x取地比擬適宜了，而當(dāng)分區(qū)內(nèi)包含的道路節(jié)點(diǎn)數(shù)較少時(shí)，說明警車的初始?？课恢脹]有選好，需要更大概率的調(diào)整，這樣的結(jié)論也是比擬客觀的。

對(duì)于所有分區(qū)外未被覆蓋的道路節(jié)點(diǎn)和很多節(jié)點(diǎn)〔稱之為節(jié)點(diǎn)群〕，用來調(diào)整警車位置遷移的方向，其分析示意圖如圖5所示。調(diào)整方案目標(biāo)是使未被覆蓋的節(jié)點(diǎn)數(shù)盡量的少。在設(shè)計(jì)調(diào)整方向函數(shù)時(shí)，需要考慮：〔1〕節(jié)點(diǎn)群內(nèi)節(jié)點(diǎn)的數(shù)目；〔2〕警車距離節(jié)點(diǎn)群的位置。優(yōu)先考慮距離，所以在公式〔2〕中，用距離的平方來描述調(diào)整方向函數(shù)。

由于某一個(gè)區(qū)域范圍內(nèi)的未被覆蓋節(jié)點(diǎn)數(shù)，整個(gè)區(qū)域未被覆蓋的節(jié)點(diǎn)總數(shù)，分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離等幾個(gè)因素會(huì)影響到調(diào)整的方案，所以要綜合考慮這些因素。于是設(shè)計(jì)了區(qū)間調(diào)整函數(shù)，

式中，表示第個(gè)分區(qū)內(nèi)未被覆蓋的節(jié)點(diǎn)數(shù)，表示第分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離，表示未被覆蓋的節(jié)點(diǎn)和節(jié)點(diǎn)群個(gè)數(shù)。

現(xiàn)在簡(jiǎn)要分析第分區(qū)按區(qū)間調(diào)整函數(shù)的調(diào)整方案，當(dāng)某兩節(jié)點(diǎn)群的節(jié)點(diǎn)數(shù)目相等，但是距離不等時(shí)，如，由區(qū)間調(diào)整公式可知，該區(qū)間向節(jié)點(diǎn)群方向調(diào)整。當(dāng)某個(gè)分區(qū)與兩個(gè)節(jié)點(diǎn)群的距離相等，但節(jié)點(diǎn)群的內(nèi)節(jié)點(diǎn)個(gè)數(shù)不相等，如時(shí)，由〔4〕可知，該分區(qū)域會(huì)想節(jié)點(diǎn)群方向調(diào)整。

注意在整個(gè)調(diào)整過程中，調(diào)整幾率控制是否調(diào)整，調(diào)整方向函數(shù)控制調(diào)整的方向，尋找在這種調(diào)整方案下的最優(yōu)結(jié)果。

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

〔3〕在step3中，使用floyd算法計(jì)算出警車初始?？奎c(diǎn)到周邊各節(jié)點(diǎn)的最短距離，目的是當(dāng)區(qū)域內(nèi)有情況發(fā)生時(shí)，警車能在要求的時(shí)間限制內(nèi)到達(dá)現(xiàn)場(chǎng)。

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

警車的配置和巡邏方案

使用atb編程實(shí)現(xiàn)算法1得到，整個(gè)區(qū)域配備13輛警車，這些警車靜止在初始?？奎c(diǎn)時(shí)，能滿足d1要求。警車的初始?？课恢梅謩e為道路交叉節(jié)點(diǎn)6，25，30，37，82，84，110，111，126，214，253，258，278處。每個(gè)警車所管轄的交叉點(diǎn)〔原始的交叉節(jié)點(diǎn)〕如圖6所示，求解的分區(qū)結(jié)果見附錄所示。

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

13個(gè)分區(qū)共覆蓋了252個(gè)交叉點(diǎn)，另外的55個(gè)原始交叉點(diǎn)沒有被這些分區(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ū)方案下，這些點(diǎn)中，每?jī)蓚€(gè)相連的點(diǎn)間的道路離散值長(zhǎng)度占整個(gè)區(qū)域總的長(zhǎng)度的比值為。因此，在整個(gè)區(qū)域配置13輛警車，每個(gè)警車在初始?？奎c(diǎn)靜止不動(dòng)，當(dāng)有案件發(fā)生時(shí)，離案發(fā)現(xiàn)場(chǎng)最近的警車從初始?？奎c(diǎn)趕到現(xiàn)場(chǎng)。

評(píng)價(jià)巡邏效果顯著的指標(biāo)

110警車在街道上巡邏是目的是為了對(duì)違法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的平安感，同時(shí)還加快了接處警〔接受報(bào)警并趕往現(xiàn)場(chǎng)處理事件〕時(shí)間，提高了反響時(shí)效，為社會(huì)和諧提供了有力的保障。巡警在城市繁華街道、公共場(chǎng)所執(zhí)行巡邏任務(wù)，維護(hù)治安，效勞群眾，可以得良好的社會(huì)效應(yīng)[1]。

在整個(gè)區(qū)域中，由于案發(fā)現(xiàn)場(chǎng)都在道路上，道路上的每一點(diǎn)都是等概率發(fā)生的，因此警車巡邏的面越廣，所巡邏的街道數(shù)目越多，警車的巡邏效果就越好，對(duì)違法犯罪分子就越有威懾力，警車也能更及時(shí)地處理案件。

我們采用全面性來衡量巡邏的效果顯著性，即用警車巡邏所經(jīng)過的街道節(jié)點(diǎn)數(shù)占區(qū)域總節(jié)點(diǎn)數(shù)的比值。當(dāng)警車重復(fù)經(jīng)過同一條街道同一個(gè)離散點(diǎn)時(shí)，僅記錄一次。

〔3〕

式中，表示警車經(jīng)過的離散點(diǎn)數(shù)，代表整個(gè)區(qū)域總的離散點(diǎn)數(shù)。值越大，說明警車所經(jīng)過的街道數(shù)目越多，所取得的效果越顯著。