方法對(duì)道路進(jìn)行離散化，以的速度行走一分鐘的距離作為步長(zhǎng)，一分鐘時(shí)間的選擇是參照問(wèn)題叁的結(jié)果要求來(lái)設(shè)定的，步長(zhǎng)。用線性插值的方法，從道路的一個(gè)方向進(jìn)行線性插值，實(shí)現(xiàn)將每條道路離散化的目標(biāo)，考慮到有些道路不是的整數(shù)倍，我們就一般情況進(jìn)行討論，其分析示意圖如圖3所示。道路ab長(zhǎng)度為個(gè)與長(zhǎng)度的和，為了更精確處理cb段道路，那么就要考慮在cb之間是否要插入一個(gè)新的點(diǎn)，根據(jù)的長(zhǎng)度不同，其對(duì)應(yīng)的處理方式也有所不同。

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

引進(jìn)臨界指數(shù)，選取大小的準(zhǔn)那么是使盡量離散化后警車(chē)等效的平均巡邏速度和題目給定的速度〔〕的差值盡量小，經(jīng)過(guò)計(jì)算得時(shí)，不再插入新的坐標(biāo)點(diǎn)時(shí)能使整個(gè)區(qū)域的道路離散效果較好。此時(shí)，將cb段長(zhǎng)度設(shè)定為處理，于是離散后的ab道路長(zhǎng)度會(huì)比實(shí)際長(zhǎng)度短些；當(dāng)時(shí)，需要在兩個(gè)點(diǎn)之間再插入一點(diǎn)，因?yàn)檫@樣處理能使整個(gè)區(qū)域的整體道路的離散化效果比擬理想。如圖3所示，在c與b間再插入新的坐標(biāo)點(diǎn)，插入的位置在距c點(diǎn)的d點(diǎn)處,這樣處理后所得的道路長(zhǎng)度比實(shí)際長(zhǎng)度長(zhǎng)了。采用這樣的方法進(jìn)行線性插值，我們使用atb編程實(shí)現(xiàn)對(duì)整個(gè)區(qū)域道路的離散，所得的離散結(jié)果如圖4所示，離散后共得到762個(gè)節(jié)點(diǎn)，比原始數(shù)據(jù)多了455個(gè)節(jié)點(diǎn)，離散后的節(jié)點(diǎn)數(shù)據(jù)見(jiàn)附件中的“newpottxt〞。

圖4 整個(gè)區(qū)域離散結(jié)果圖

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

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

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

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

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

step2：統(tǒng)計(jì)分區(qū)不能覆蓋的節(jié)點(diǎn)，調(diào)整警車(chē)的初始停靠點(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)整車(chē)輛初始點(diǎn)的位置〔后文中有詳細(xì)說(shuō)明〕，當(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í)，將警車(chē)初始位置的調(diào)整方向?yàn)槌@些未被覆蓋的節(jié)點(diǎn)按一定的規(guī)那么〔在

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

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

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

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

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

〔1〕

〔1〕式中，均為常數(shù)，為整個(gè)區(qū)域車(chē)輛數(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í)間〕的條件下，由于總的車(chē)輛數(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ū)的警車(chē)初始停靠位置選取地比擬適宜了，而當(dāng)分區(qū)內(nèi)包含的道路節(jié)點(diǎn)數(shù)較少時(shí)，說(shuō)明警車(chē)的初始停靠位置沒(méi)有選好，需要更大概率的調(diào)整，這樣的結(jié)論也是比擬客觀的。

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