校園電動巡邏車配備方案

鄭玙

（湖北大學(xué)計算機與信息工程學(xué)院，湖北 武漢 430062）

1 模型的建立與求解

給定：在后臺接聽到校內(nèi)有報警電話打出后的四分鐘內(nèi)，有不低于90%的校園巡邏車能及時趕到報警現(xiàn)場，即在一天當(dāng)中任意一個時刻當(dāng)校內(nèi)有不低于90%的區(qū)域發(fā)生案件后，均有巡邏車可以在報警電話打出的四分鐘內(nèi)趕到現(xiàn)場。

1.1 數(shù)據(jù)預(yù)處理

1.1.1 地理信息離散化

為了方便我們建模過程中的計算與數(shù)據(jù)處理，可先將此道路抽象化，在分塊后的每一段道路中分別采樣，將道路運用線性插值的方法離散成一個一個的端點，設(shè)每250 米取一個點。整個校園區(qū)域就可以看作是由若干個結(jié)點和邊構(gòu)造成的無向圖，從而建立了校園區(qū)域網(wǎng)拓撲關(guān)系。

則校園巡邏車的時間信息就可以用模型經(jīng)過的離散點的數(shù)量來抽象，而巡邏車行駛過程則是模擬成從一個離散點到下一個離散點，便于清晰地觀察與分析。

1.1.2 建立巡邏仿真系統(tǒng)

采用計算機仿真的方法，建立校園巡邏車巡邏仿真系統(tǒng)，要模擬出任意時刻的校園巡邏車的行駛狀態(tài)。該計算機仿真系統(tǒng)會在每一個時刻計算出巡邏車當(dāng)前的行駛參數(shù)是否符合給定的要求，若不符合則根據(jù)給定的要求進行調(diào)整，直至檢測到行駛參數(shù)在符合要求的范圍內(nèi)達到動態(tài)平衡，輸出此時校園巡邏車的行駛方案，如圖1。

圖1 巡邏仿真系統(tǒng)工作流程

1.2 模型建立與求解

1.2.1 模型建立的基本思想

1.2.1.1 按照一般思路，求解如何使區(qū)域內(nèi)的校園巡邏車數(shù)目最少，可將問題轉(zhuǎn)化為求解如何使每一輛校園巡邏車所能管轄的道路范圍最大。假設(shè)一輛校園巡邏車停靠在A（0，0）。

設(shè)當(dāng)后臺接收到報警電話后巡邏車的平均行駛速度是20km/h，而它正常巡邏時平均行駛速度是10km/h，當(dāng)校園巡邏車收到警報后，在四分鐘內(nèi)能從接警位置趕到事發(fā)現(xiàn)場的最大距離是1km。

如上圖2，假設(shè)校園巡邏車最開始?？坑诘缆?，2，3，4 交叉的位置A，A 點即4 條道路的中心點。我們對校園巡邏車在y 軸正半軸的道路1 上行駛的這個例子來進行分析，車輛以7km/h 的平均速度在道路1 上0 到2 之間行駛，設(shè)0 到2 之間的距離為xkm。如果報警電話從2，3，4 其他三條道路上的任意一點呼出，當(dāng)校園巡邏車行駛到A 點之后便以平均速度15km/h 行駛到案發(fā)現(xiàn)場，在收到報警電話后的四分鐘內(nèi)，校園巡邏車從道路1 趕到案發(fā)現(xiàn)場的最大距離是(1-x)km。但是另一種情況，如果在后臺接到報警電話之前校園巡邏車?yán)^續(xù)在y 軸正半軸上朝向正無窮方向行駛，那么校園巡邏車按原15km/h 行駛趕往案發(fā)現(xiàn)場則會超過4 分鐘，也就是說這種情況下巡邏車要在收到報警電話后的4 分鐘內(nèi)趕往報警現(xiàn)場需要用更快的行駛速度，此時可計算出校園巡邏車的最大巡邏覆蓋區(qū)域比車輛到達A′點時的最大巡邏覆蓋區(qū)域大，就是說在巡邏車從初始點向區(qū)域的中心點行駛但未達到x=2 這個點時，校園巡邏車巡邏的區(qū)域范圍越小，它的巡邏覆蓋區(qū)域面積范圍越大。當(dāng)x=0 時，校園巡邏車的管轄范圍達到最大值1km，即校園巡邏車在初始停靠點靜止不動時達到最大值。

圖2 一輛校園巡邏車管轄范圍效果示意圖

以上是對特例進行分析，道路之間互相垂直、分布對稱。以下簡單分析一下一般的普遍情況。

圖3 所示為一般情況，道路呈不對稱分布。和上圖情形比起來會更為復(fù)雜，道路角度和方向都在靈活變化，建立的模型也會更加復(fù)雜。對圖3 進行分析，道路1 與道路6 之間的轉(zhuǎn)彎點是點D，道路1 更靠近區(qū)域中心位置，道路1，2，3，4，5 相交于區(qū)域的中心點點C。由于校園巡邏車在道路上巡邏時，行走的路線是分段直線，并不影響路徑的長度，所以當(dāng)校園巡邏車巡邏到D 點處（距離初始?？康腃 點xkm 遠處）要求該校園巡邏車在四分鐘內(nèi)趕到現(xiàn)場處理剛剛發(fā)生的案件，最大行駛距離在(1-x)km 之內(nèi)；若校園巡邏車在道路1 上繼續(xù)向前行駛，則該校園巡邏車能在三分鐘內(nèi)趕到現(xiàn)場的距離繼續(xù)縮小，當(dāng)校園巡邏車沒有行駛到D 點時，此時該校園巡邏車的最大管轄范圍比(1-x)km 大，故校園巡邏車的巡邏范圍越小，它的管轄范圍盡量大。當(dāng)x=0 時，即校園巡邏車靜止不動時，一輛校園巡邏車的管轄范圍能達到最大值。

圖3 一輛校園巡邏車最大管轄范圍分析示意圖

1.2.1.2 由以上可知，當(dāng)校園巡邏車的覆蓋區(qū)域達到一定的大小時，即只要校園巡邏車能夠符合條件（1）中的接收警報后的發(fā)車時間，就可以證明和校園巡邏車的巡邏效果對巡邏車的覆蓋率沒有影響，以此來確定需要配置的校園巡邏車數(shù)量的最小值。進行優(yōu)化可知，模型靜態(tài)狀態(tài)下要想達到要求的覆蓋率最少需要的巡邏車車輛數(shù)為n。此時計算出的n 是在一個幾乎最優(yōu)的配置方案下符合要求覆蓋率90%的最少數(shù)量要求。但校園巡邏車在校內(nèi)的分布情況會隨著時間的變化而變化，這種動態(tài)的改變很可能導(dǎo)致配置的巡邏車偏離這個最優(yōu)分布，從而導(dǎo)致巡邏車在某一些時間段內(nèi)不能滿足達到不低于90%覆蓋率的要求。因此，我們計算動態(tài)的情況下所需要的最小車輛數(shù)一定要大于或等于在靜態(tài)情形下靜態(tài)優(yōu)化所得到的車輛數(shù)。

這個問題我們用到動靜態(tài)相結(jié)合的方法：我們用靜態(tài)下的情形模擬出情況，其中的狀態(tài)結(jié)果包含有靜態(tài)優(yōu)化過后的校園巡邏車位置圖及在這種模型下所需最小的巡邏車車輛數(shù)目。然后用這個靜態(tài)優(yōu)化后的狀態(tài)作為動態(tài)模型最開始的狀態(tài)，來模擬時間的變化。時間演化的目標(biāo)函數(shù)是覆蓋率的增加，覆蓋區(qū)域包含三個重點部位。

若在模擬過程中任何一個時間都可以達到90%及以上的覆蓋率，并且能在120 秒內(nèi)到達所有重點區(qū)域，則該模擬時間演化的車輛數(shù)是可行的。若不是，就應(yīng)該繼續(xù)增大車輛數(shù)，然后重新模擬動態(tài)優(yōu)化、動態(tài)仿真，檢驗車輛數(shù)增加后是否符合所給出的條件，以此類推，直到符合條件要求。

1.2.2 模擬退火算法運用

根據(jù)以上內(nèi)容分析，我們將該道路離散化，然后在新的地圖上思考。不妨設(shè)道路交叉路口數(shù)量為N，校園巡邏車的數(shù)量為n，且任何路口都有一個對應(yīng)的鄰域，記Ai為第i 個路口的鄰域。問題可看作是，求m 個路口，使得新地圖上所有路口都各有一輛校園巡邏車時，m 個鄰域的并集所含的點數(shù)最多。

△n 指的是鄰域法和臨點法兩種算法算出解得誤差值；n（C′）指的數(shù)值大的一方：n（C）指的數(shù)值小的一方。

（5）接受準(zhǔn)則。由于為最大優(yōu)化問題，所以接受準(zhǔn)則為：

即當(dāng)?n≤0 時，則以概率exp（?n/bT）（其中b 為控制參數(shù)，T 為冷卻參數(shù)）接受新解為當(dāng)前解。當(dāng)?n＞0 時，以概率1 接受新解為當(dāng)前解。

1.2.3 模擬退火算法搜索結(jié)果及分析

表1 列出了在不同校園巡邏車數(shù)目下通過模擬退火算法搜索得到的優(yōu)化覆蓋率結(jié)果：

表1 16-20 輛校園巡邏車的優(yōu)化覆蓋率參數(shù)對比

分析上表數(shù)據(jù)可知，滿足條件（在動態(tài)優(yōu)化后的分布中校園巡邏車的覆蓋率等于或大于90%）的校園巡邏車數(shù)量為20 輛。

1.2.4 運動中的環(huán)形區(qū)域切割法

之所以采用非傳統(tǒng)的環(huán)形區(qū)域切割法，是因為傳統(tǒng)區(qū)域分割無法將車輛間相互交換檢查巡邏的靈活關(guān)系考慮在內(nèi)，這會導(dǎo)致我們計算出的巡邏車數(shù)量偏大。出于對數(shù)據(jù)的謹慎，我們將同時兼顧切割方法和考慮到正在運動的車輛。在一指定區(qū)域內(nèi)，設(shè)有若干條環(huán)形路線和若干輛校園巡邏車，每一條環(huán)線上的巡邏車都以相同的環(huán)繞方向行駛，這樣一來每一輛巡邏車的覆蓋區(qū)域也會隨之改變，可以很好地降低覆蓋區(qū)重疊率，同時也避免了巡邏車行駛導(dǎo)致的原覆蓋區(qū)被忽略沒有覆蓋的情形。這樣便于我們更好更加明顯地得出結(jié)論，校園巡邏車的行駛方案完全可以在車輛數(shù)很少的情形之下符合要求。我們要計算出任何一個時刻巡邏車的道路覆蓋率為多少，當(dāng)覆蓋率高于90%時就減少車輛數(shù)，反之覆蓋率高于90%時就增加車輛數(shù)，直至達到一個在任一時刻下巡邏車的環(huán)繞行駛均符合上述要求的動態(tài)平衡。由上可知，分配校園巡邏車數(shù)量的關(guān)鍵之處在于，環(huán)形線路如何規(guī)定以及校園巡邏車如何在給定的環(huán)形線路上運動。

環(huán)形線路的確定方法：

（1）按照從外環(huán)至內(nèi)環(huán)的順序確定環(huán)線；

（2）計算給定區(qū)域邊界距離環(huán)形路線最外環(huán)大概為2km 左右，即校園巡邏車在環(huán)形路線的最外環(huán)運動時的4 分鐘內(nèi)，覆蓋區(qū)幾乎到達該區(qū)域的邊界；

（3）計算給定區(qū)域邊界距離環(huán)形路線次外環(huán)大概為4km左右，即校園巡邏車在最外環(huán)和次外環(huán)運動時的4 分鐘內(nèi)，覆蓋區(qū)幾乎相接或者少部分重疊，依照此情形我們可以確定相鄰的內(nèi)環(huán)；

（4）計算給定區(qū)域邊界距離最內(nèi)環(huán)離環(huán)中心大概為2km左右，即校園巡邏車在環(huán)形路線的最內(nèi)環(huán)運動時的4 分鐘內(nèi)，覆蓋區(qū)域幾乎將所有內(nèi)環(huán)里面的道路覆蓋。

校園巡邏車放置方案：

（1）將校園巡邏車均勻分配到各個環(huán)形道路上，保證放置后前后兩車之間的距離大約是4km左右，已達到相鄰兩輛車行駛的4 分鐘內(nèi)運動的覆蓋范圍幾乎相接或者有少部分重疊的效果；

（2）依照上述（1）情形放置好后，計算校園巡邏車靜態(tài)條件下的道路覆蓋率，如果覆蓋率小于90%，則遍歷道路上的點，在其中選擇一點增加一輛校園巡邏車，來保證該輛校園巡邏車放置后，能使得道路覆蓋率的增加值最大；

（3）重復(fù)步驟（2）直至靜態(tài)條件下的巡邏車道路覆蓋率能達到90%以上，且三個關(guān)鍵部位全都被覆蓋到為止；

（4）此時得到靜止條件下滿足要求的情況，此時的校園巡邏車數(shù)為第一問要求的校園巡邏車數(shù)目的下限，因為一旦校園巡邏車運動，就會出現(xiàn)覆蓋區(qū)重疊增加，從而不能滿足要求的現(xiàn)象，校園巡邏車數(shù)目就需要增加。

動態(tài)條件下滿足要求：

（1）規(guī)定所有的校園巡邏車都朝向同一環(huán)繞方向行駛（全部順時針行駛或者全部逆時針行駛），計算所有時刻校園巡邏車的覆蓋率，若有某一時刻不符合要求的情況，則校園巡邏車數(shù)量加一，直至使得該時刻符合要求情況，以此類推；

（2）定義校園巡邏車的運動步數(shù)上限為T，我們繼續(xù)模擬車輛的行駛，當(dāng)達到T 時，就認為本次模擬結(jié)束，如果在T 步內(nèi)的任何一個時刻，都能滿足題設(shè)要求，則視為目標(biāo)達成。在設(shè)計的程序中不妨取T=4000 步，此時車輛在最外環(huán)至少行駛一圈以上，不難看出這是車輛運動基本達到一個動態(tài)平衡，且此時車輛繼續(xù)行駛的任一時刻也都能滿足題設(shè)的要求；

（3）按（1）（2）步驟處理后的校園巡邏車總數(shù)量即為符合要求的最少數(shù)量。

綜上所述，校園巡邏車的行駛路線應(yīng)用運動中的環(huán)形區(qū)域分割法定義，且依據(jù)以上步驟從符合要求的靜止?fàn)顟B(tài)到最后符合要求的動態(tài)相對穩(wěn)定狀態(tài)。通過計算得到該問題的結(jié)果為：要想符合題設(shè)要求，則最少需要配置20 輛校園巡邏車。

2 現(xiàn)實因素

2.1 實際因素

因素一：事發(fā)現(xiàn)場并不是都在道路上。

這是很現(xiàn)實的問題，要想解決這一問題，要對該區(qū)域的地形有進一步深入的了解，并對整個區(qū)域進行離散化，而不是僅僅對道路離散化。并且還要考慮從道路上到事發(fā)現(xiàn)場（如公園或者小區(qū)內(nèi)部）所花費的時間。

因素二：道路并非都是雙行道

模型假設(shè)中把所有道路當(dāng)作雙行道來處理，其實并不是不能處理單行道的情況，而是沒有實際數(shù)據(jù)，無法得知哪條道路是單行道。如果可以得到道路單雙行的信息，我們建立的系統(tǒng)也是可以使用的，只是需要對道路多加上一個標(biāo)記。原本得到的巡邏路線可能由于某條道路不能反向通行而改變。但是模型中基本的規(guī)則、做法還是可行的。

因素三：用平均速度計算與實際情況有差別

警車的巡邏速度實際上是位置與時間的函數(shù)，比如某些地段，某些時間段車流量大，交通擁擠。這些因素會影響警車巡邏的速度。如果可以大致得到這些統(tǒng)計數(shù)據(jù)，可以不認為警車的速度是恒定的，而是根據(jù)不同地點，不同時間有所變化的，則可以得到更切合實際的結(jié)果。

因素四：巡邏路線隱匿性

電動巡邏車的路線應(yīng)具有一定的隱匿性和隨機性，不可具體的預(yù)測路線，以對有作案心理的人員造成心理壓力。

2.2 實際情況討論

情況一：有多個地點同時發(fā)生案件

雖然多個地點同時發(fā)生案件的概率相當(dāng)小，但是萬一發(fā)生這樣的事件，系統(tǒng)需要對這種情況進行有效的處理。比如，若一輛車的覆蓋范圍內(nèi)同時發(fā)生兩起案件，而這兩個地點又都是僅僅在這一輛警車的覆蓋范圍內(nèi)，那么，該警車處理哪起案件，如何調(diào)度其他警車到另一案件的事發(fā)現(xiàn)場處理案件，其他警車到該地方的接處警時間會不會過大，就是需要解決的問題。解決的辦法一般是，首先根據(jù)案件性質(zhì)，選擇最重要的案件，由該案件反覆蓋區(qū)內(nèi)的警車處理；若兩起案件重要性相當(dāng)，則根據(jù)最短路原則，選擇事發(fā)地點最接近警車的案件。再根據(jù)周圍警車巡邏狀態(tài)，選擇另外一輛距離較近的警車，盡量減小接處警時間。

情況二：天氣環(huán)境

天氣相對于來說是一種不可測的條件，但它又應(yīng)該納入考慮。常見天氣變化，雨、雪等也會對巡邏產(chǎn)生一定影響（個別的確甚至有臺風(fēng)、沙塵暴等惡劣天氣）。在比較惡劣的天氣情況下，可以將巡邏車靜止守候，如同問題一。在常見天氣變化時，應(yīng)該根據(jù)情況改良巡邏車，減小惡劣環(huán)境對巡邏車速度的減益。或者重新獲取在雨、雪天氣時巡邏車的速度，再根據(jù)問題二可算出此時所需配備巡邏車的數(shù)目。

情況三：上下課人流高峰

上下課時，人流量較大，巡邏車的速度也會受到減益，但考慮到上下課時間會比較集中在課前、課后半小時內(nèi)，在這短期時間內(nèi)。遠離人群稠密地區(qū)的巡邏車可以按正常情形來行駛。在人群稠密區(qū)內(nèi)，考慮到此段時間并不會太長，且人多時間段作案的概率會大幅降低，人流量大的區(qū)域巡邏車可以暫時靜止。

3 模型評價與推廣

模型優(yōu)點：

（1）本模型分析得比較深入，模型結(jié)構(gòu)也比較清晰，其中定義的假設(shè)與引入的新概念都清晰明了且易懂，很符合我們生活中的實際情況，有利于我們對模型的理解。（2）建立模型的方法簡單且容易實行，本模型應(yīng)用了靜態(tài)優(yōu)化與動態(tài)優(yōu)化相互結(jié)合的方法，其中利用了動態(tài)仿真及模擬退火算法，給出了符合不同條件下的相對而言最佳的巡邏路線。本模型的原理也十分清晰易懂，采取了啟發(fā)式算法，計算原理也比較簡單，模型的實用性強，故該模型具有極高的創(chuàng)新性和應(yīng)用價值，并且應(yīng)用在實際生活中它的穩(wěn)定性也很好。

模型缺點：

（1）本模型在對于道路的處理過程是將道路離散化成若干個點，然后將道路當(dāng)作若干個點來處理，目的是更加形象便于觀察，且將道路離散成無數(shù)個點，把道路看作點的集合，這樣的處理方法可以將誤差忽略不計，但是在實際計算的時候，細化的點數(shù)越多我們的計算量就越大，這又有與“將誤差忽略不計”的多點數(shù)離散相悖。除此之外，本模型針對不同的目標(biāo)制定出的路線只是相對而言較好一點的結(jié)果，并不是所有情況下的最優(yōu)路線，此處要注意。（2）由于模型中將連續(xù)的道路以250m 為一個單位進行離散化，每一條道路上并不能得到整數(shù)個節(jié)點，因此計算得到的坐標(biāo)值會有一定的誤差。（3）由于不依賴于該區(qū)域的地圖，所以針對性不強。