數學建模（第4頁）

513分區域求解警車數目的算法設計

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

于是我們設計算法1，步驟如下所示：

step1：將整個區域預分配為個分區，每個分區分配一輛警車，警車的初始停靠位置設在預分配區中心的道路節點上，假設區域的中心不在道路節點上，那么將警車放在離中心最近的道路節點上；

step2：統計分區不能覆蓋的節點，調整警車的初始?？奎c，使分區覆蓋盡可能多的道路節點，調整分為區內調整和區間調整方案：〔1〕區內調整按照模擬退火思想構造的函數，在區間調整調整車輛初始點的位置〔后文中有詳細說明〕，當分區內節點數較多時，調整的概率小些，分區內節點數較少時，調整的概率大些，〔2〕當區域中存在未被覆蓋的節點或節點群〔大于等于叁個節點集中在一個范圍內〕時，將警車初始位置的調整方向為朝著這些未被覆蓋的節點按一定的規那么〔在

對算法的幾點說明：

〔1〕該算法所取的車輛數是由多到少進行計算的，初始值設為20，這個值的選取是根據區域圖估算的。

(2）預分區的優點在于使警車的初始位置盡可能均勻地分散分布，警車的初始?？奎c在一個分區的中心點附近尋找得到，比起在整個區域隨機生成停靠點，計算效率明顯得到提高。

預分配之后，需要對整個區域不斷地進行調整，調整時需要考慮調整方向和調整概率。

警車調整借鑒的是模擬退火算法的方法，為了使分區內包含道路節點數較多的分區的初始停車點調整的概率小些，而分區內包含道路節點數的少的分區內的初始停車點調整的概率大些，我們構造了一個調整概率函數，

〔1〕

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

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

對于所有分區外未被覆蓋的道路節點和很多節點〔稱之為節點群〕，用來調整警車位置遷移的方向，其分析示意圖如圖5所示。調整方案目標是使未被覆蓋的節點數盡量的少。在設計調整方向函數時，需要考慮：〔1〕節點群內節點的數目；〔2〕警車距離節點群的位置。優先考慮距離，所以在公式〔2〕中，用距離的平方來描述調整方向函數。

由于某一個區域范圍內的未被覆蓋節點數，整個區域未被覆蓋的節點總數，分區域與未被覆蓋的節點或節點群的距離等幾個因素會影響到調整的方案，所以要綜合考慮這些因素。于是設計了區間調整函數，

式中，表示第個分區內未被覆蓋的節點數，表示第分區域與未被覆蓋的節點或節點群的距離，表示未被覆蓋的節點和節點群個數。

現在簡要分析第分區按區間調整函數的調整方案，當某兩節點群的節點數目相等，但是距離不等時，如，由區間調整公式可知，該區間向節點群方向調整。當某個分區與兩個節點群的距離相等，但節點群的內節點個數不相等，如時，由〔4〕可知，該分區域會想節點群方向調整。

注意在整個調整過程中，調整幾率控制是否調整，調整方向函數控制調整的方向，尋找在這種調整方案下的最優結果。

圖5調整分區域示意圖

〔3〕在step3中，使用floyd算法計算出警車初始?？奎c到周邊各節點的最短距離，目的是當區域內有情況發生時，警車能在要求的時間限制內到達現場。

〔4〕為求出較優的警車?？奎c，采用模擬退火算法，算出局部最優的方案。

警車的配置和巡邏方案

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

圖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。在這種分區方案下，這些點中，每兩個相連的點間的道路離散值長度占整個區域總的長度的比值為。因此，在整個區域配置13輛警車，每個警車在初始?？奎c靜止不動，當有案件發生時，離案發現場最近的警車從初始停靠點趕到現場。

評價巡邏效果顯著的指標

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

在整個區域中，由于案發現場都在道路上，道路上的每一點都是等概率發生的，因此警車巡邏的面越廣，所巡邏的街道數目越多，警車的巡邏效果就越好，對違法犯罪分子就越有威懾力，警車也能更及時地處理案件。

我們采用全面性來衡量巡邏的效果顯著性，即用警車巡邏所經過的街道節點數占區域總節點數的比值。當警車重復經過同一條街道同一個離散點時，僅記錄一次。

〔3〕

式中，表示警車經過的離散點數，代表整個區域總的離散點數。值越大，說明警車所經過的街道數目越多，所取得的效果越顯著。