值，我們使用MATLAB編程實(shí)現對整個(gè)區域道路的離散，所得的離散結果如圖4所示，離散后共得到762個(gè)節點(diǎn)，比原始數據多了455個(gè)節點(diǎn)，離散后的節點(diǎn)數據見(jiàn)附件中的“newpoint.txt〞。

    圖4         整個(gè)區域離散結果圖

    采用這種插值方法道路離散后，將直線(xiàn)上的無(wú)窮多個(gè)點(diǎn)轉化有限個(gè)點(diǎn)，便于分析問(wèn)題和實(shí)現相應的算法，由圖4可知，所取得的整體離散效果還是比擬理想的。

    5.1.3         分區域求解警車(chē)數目的算法設計

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

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

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

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

    對算法的幾點(diǎn)說(shuō)明：

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

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

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

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

    〔1〕

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

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

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

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

    式中，