黑巖小說

數學建模（第4頁）

513分區(qū)域求解警車數目的算法設計

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

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

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

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

對算法的幾點說明：

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

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

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

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

〔1〕

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

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

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

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

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

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

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

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

〔3〕在step3中，使用floyd算法計算出警車初始停靠點到周邊各節(jié)點的最短距離，目的是當區(qū)域內有情況發(fā)生時，警車能在要求的時間限制內到達現場。

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

警車的配置和巡邏方案

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

圖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ū)域總的長度的比值為。因此，在整個區(qū)域配置13輛警車，每個警車在初始?？奎c靜止不動，當有案件發(fā)生時，離案發(fā)現場最近的警車從初始停靠點趕到現場。

評價巡邏效果顯著的指標

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

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

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

〔3〕

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