鄭玙

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

1 模型的建立與求解

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

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

1.1.1 地理信息離散化

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

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

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

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

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

1.2 模型建立與求解

1.2.1 模型建立的基本思想

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

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

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

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

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

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

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

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

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

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

1.2.2 模擬退火算法運(yùn)用

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

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

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

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

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

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

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

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

1.2.4 運(yùn)動(dòng)中的環(huán)形區(qū)域切割法

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

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

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

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

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

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

校園巡邏車放置方案：

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

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

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

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

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

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

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

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

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

2 現(xiàn)實(shí)因素

2.1 實(shí)際因素

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

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

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

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

因素三：用平均速度計(jì)算與實(shí)際情況有差別

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

因素四：巡邏路線隱匿性

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

2.2 實(shí)際情況討論

情況一：有多個(gè)地點(diǎn)同時(shí)發(fā)生案件

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

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

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

情況三：上下課人流高峰

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

3 模型評(píng)價(jià)與推廣

模型優(yōu)點(diǎn)：

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

模型缺點(diǎn)：

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