交巡警服務(wù)平臺(tái)的設(shè)置與調(diào)度

1、B 題： 110 警車在街道上巡邏，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又 能夠增加市民的安全感，同時(shí)也加快了接處警時(shí)間，提高了反應(yīng)時(shí)效，為社會(huì)和 諧提供了有力的保障?，F(xiàn)給出某城市內(nèi)一區(qū)域，其道路數(shù)據(jù)和地圖數(shù)據(jù)已知，該區(qū)域內(nèi)三個(gè)重點(diǎn)部位的 坐標(biāo)分別為：（5112，4806），（9126， 4266），（7434 ，1332）。該區(qū)域內(nèi) 共有307 個(gè)道路交叉口，為簡(jiǎn)化問題，相鄰兩個(gè)交叉路口之間的道路近似認(rèn)為是 直線，且所有事發(fā)現(xiàn)場(chǎng)均在下圖的道路上。該市擬增加一批配備有 GPS 衛(wèi)星定位系統(tǒng)及先進(jìn)通訊設(shè)備的 110 警車。設(shè) 110 警車的平均巡邏速度為20km/h，接警后的平均行駛速

2、度為40km/h。警車配置及 巡邏方案要盡量滿足以下要求：D1. 警車在接警后三分鐘內(nèi)趕到現(xiàn)場(chǎng)的比例不低于 90；而趕到重點(diǎn)部位的時(shí) 間必須在兩分鐘之內(nèi)。D2. 使巡邏效果更顯著；D3. 警車巡邏規(guī)律應(yīng)有一定的隱蔽性?，F(xiàn)在我們需要解決以下幾個(gè)問題：若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？請(qǐng)給出評(píng)價(jià)巡邏效果顯著程度的有關(guān)指標(biāo)。三請(qǐng)給出滿足 D1 且盡量滿足 D2 條件的警車巡邏方案及其評(píng)價(jià)指標(biāo)值。在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評(píng)價(jià)指 標(biāo)值。如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使DI、D2盡量得到滿 足？若警車接警后的平均行駛速度提高到50km/h

3、，回答問題三。你們認(rèn)為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。B 題解析：要： 本文研究的是某城區(qū)警車配置及巡邏方案的制定問題，建立了求解警車巡邏方案 的模型，并在滿足D1的條件下給出了巡邏效果最好的方案。在設(shè)計(jì)整個(gè)區(qū)域配置最少巡邏車輛時(shí)，本文設(shè)計(jì)了算法1：先將道路離散化成近 似均勻分布的節(jié)點(diǎn)，相鄰兩個(gè)節(jié)點(diǎn)之間的距離約等于一分鐘巡邏路程。由警車的 數(shù)目 ,將全區(qū)劃分成個(gè)均勻的分區(qū)，從每個(gè)分區(qū)的中心點(diǎn)出發(fā)，找到最近的道路 節(jié)點(diǎn)，作為警車的初始位置，由 Floyd 算法算出每輛警車 3 分鐘或 2 分鐘行駛路 程范圍內(nèi)的節(jié)點(diǎn)。考慮區(qū)域調(diào)整的概率大小和方向不同會(huì)影響調(diào)整結(jié)果，本文利

4、用模擬退火算法構(gòu)造出遷移幾率函數(shù)，用遷移方向函數(shù)決定分區(qū)的調(diào)整方向。計(jì) 算能滿足D1的最小車輛數(shù)，即為該區(qū)應(yīng)該配置的最小警車數(shù)目，用MATLAB計(jì)算， 得到局部最優(yōu)解為 13 輛。在選取巡邏顯著性指標(biāo)時(shí)，本文考慮了兩個(gè)方面的指標(biāo)：一是全面性，即所有警 車走過的街道節(jié)點(diǎn)數(shù)占總街道節(jié)點(diǎn)數(shù)的比例，用兩者之比來(lái)評(píng)價(jià)；二是均勻性， 即所有警車經(jīng)過每個(gè)節(jié)點(diǎn)數(shù)的次數(shù)偏離平均經(jīng)過次數(shù)的程度，用方差值來(lái)大小評(píng) 價(jià)。問題三：為簡(jiǎn)化問題，假設(shè)所有警車在同一時(shí)刻，大致向同一方向巡邏，運(yùn)動(dòng)狀 態(tài)分為四種：向左，向右，向上，向下，記錄每個(gè)時(shí)刻，警車經(jīng)過的節(jié)點(diǎn)和能夠 趕去處理事故的點(diǎn)，最后匯總計(jì)算得相應(yīng)的評(píng)價(jià)指標(biāo)。在考慮巡

5、邏規(guī)律隱蔽性要求時(shí)，文本將巡邏路線進(jìn)行隨機(jī)處理，方向是不確 定的，采用算法 2 進(jìn)行計(jì)算，得出相應(yīng)巡邏顯著指標(biāo)，當(dāng)車輛數(shù)減少到 10 輛或 巡邏速度變大時(shí)，用算法 2 計(jì)算巡邏方案和對(duì)應(yīng)的參數(shù)，結(jié)果見附錄所示。本文最后還考慮到 4個(gè)額外因素，給出每個(gè)影響因素的解決方案。關(guān)鍵詞：模擬退火算法；Floyd算法；離散化問題的重述110 警車在街道上巡邏，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又 能夠增加市民的安全感，同時(shí)也加快了接處警時(shí)間，提高了反應(yīng)時(shí)效，為社會(huì)和 諧提供了有力的保障。現(xiàn)給出某城市內(nèi)一區(qū)域，其道路數(shù)據(jù)和地圖數(shù)據(jù)已知，該區(qū)域內(nèi)三個(gè)重點(diǎn)部位的 坐標(biāo)分別為：（5112， 4806）

6、，（9126，4266），（7434 ， 1332）。該區(qū)域內(nèi)共有307 個(gè)道路交叉口，為簡(jiǎn)化問題，相鄰兩個(gè)交叉路口之間的道路近似認(rèn)為是 直線，且所有事發(fā)現(xiàn)場(chǎng)均在下圖的道路上。該市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進(jìn)通訊設(shè)備的110警車。設(shè)110 警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車配置及 巡邏方案要盡量滿足以下要求：D1. 警車在接警后三分鐘內(nèi)趕到現(xiàn)場(chǎng)的比例不低于 90；而趕到重點(diǎn)部位的時(shí) 間必須在兩分鐘之內(nèi)。D2. 使巡邏效果更顯著；D3. 警車巡邏規(guī)律應(yīng)有一定的隱蔽性?，F(xiàn)在我們需要解決以下幾個(gè)問題：若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？

7、請(qǐng)給出評(píng)價(jià)巡邏效果顯著程度的有關(guān)指標(biāo)。三請(qǐng)給出滿足 D1 且盡量滿足 D2 條件的警車巡邏方案及其評(píng)價(jià)指標(biāo)值。在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評(píng)價(jià)指 標(biāo)值。如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使DI、D2盡量得到滿 足？若警車接警后的平均行駛速度提高到50km/h，回答問題三。你們認(rèn)為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。問題分析本題為城區(qū)道路網(wǎng)絡(luò)中警車配置及巡邏問題。在進(jìn)行警車配置時(shí)，首先要考慮警 車在接警后在規(guī)定時(shí)間內(nèi)趕到現(xiàn)場(chǎng)的比例，在此條件下，以車數(shù)最少為目標(biāo)，建 模、求解；在制定巡邏方案時(shí)，要考慮巡邏的效果及隱蔽性問題。問題一只

8、要求滿足D1,求最少的警車配置數(shù)，可以認(rèn)為警車是不動(dòng)的，在三分 鐘或兩分鐘內(nèi)它能到達(dá)的區(qū)域就是它的覆蓋范圍。據(jù)此，在滿足所有街道的覆蓋 率不低于 90%的條件下，尋找最優(yōu)解。問題二要評(píng)價(jià)巡邏效果，有兩個(gè)方面需要考慮：一是巡邏的全面性，即經(jīng)過一段 時(shí)間后警車走過的街道數(shù)占總街道數(shù)的比例；二是巡邏的不均勻性，即經(jīng)過一段 時(shí)間后警車經(jīng)過每一條街道的次數(shù)相差不大，用方差來(lái)衡量。問題三是在滿足D1的條件上盡量滿足問題二所給的指標(biāo)，并給出評(píng)價(jià)方案的指 標(biāo)。首先找到一組滿足 D1 的各警車位置，然后在和各警車位置相連的點(diǎn)中隨機(jī) 尋找一個(gè)點(diǎn)，判斷新的點(diǎn)是否滿足D1,如果滿足則警車行駛到該點(diǎn)，否則重新 尋找，直

9、到滿足為止。一段時(shí)間后統(tǒng)計(jì)所有車走過的點(diǎn)數(shù)及每個(gè)點(diǎn)被走過的次數(shù)， 用問題二給出的兩個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。綜合兩個(gè)指標(biāo)，可判斷此路徑的好壞，重復(fù) 這個(gè)過程，直到綜合評(píng)價(jià)指標(biāo)達(dá)到一個(gè)滿意的值為止。問題四增加了隱蔽性要求，首先給出評(píng)價(jià)隱蔽性的指標(biāo)，隱蔽性可用路線的隨機(jī) 性來(lái)評(píng)價(jià)，將它加入到問題三的模型中去進(jìn)行求解。問題五限制警車數(shù)量為10,要綜合考慮DI、D2,先分配這10輛車使道路的覆蓋 率最高，然后按照問題三的步驟進(jìn)行求解，其中每一步對(duì)D1的判斷只需使道路 的覆蓋率盡量高即可。問題六同問題三，只需將車速改為 50km/h 即可。模型的假設(shè)警車都在路上巡邏，巡警去處理案件的時(shí)間不考慮；所有事發(fā)現(xiàn)場(chǎng)都在道

10、路上，案件在道路上任一點(diǎn)是等概率發(fā)生的；警車初始?？奎c(diǎn)是隨機(jī)的，但盡量讓它們分散分布，一輛警車管轄一個(gè)分 區(qū)；假定各個(gè)劃分區(qū)域內(nèi)，較短時(shí)間內(nèi)，最多會(huì)發(fā)生一個(gè)案件；假設(shè)區(qū)域內(nèi)的每條道路都是雙行線，不考慮轉(zhuǎn)彎對(duì)結(jié)果造成的影響；如果重點(diǎn)部位不在道路上的，假設(shè)這些重點(diǎn)部位在離它們最近的道路上；圖中水域?qū)ρ策壏桨笡]有影響。符號(hào)說(shuō)明表示警車數(shù)目表示警車初始?？奎c(diǎn)到各道路的最短距離表示整個(gè)區(qū)域的總道路長(zhǎng)度表示不能在 3 分鐘內(nèi)到達(dá)的區(qū)域的道路的長(zhǎng)度表示非重點(diǎn)部位的警車在 3 分鐘內(nèi)不能到達(dá)現(xiàn)場(chǎng)的比例表示三分鐘內(nèi)能從接警位置趕到事發(fā)現(xiàn)場(chǎng)的最大距離是表示整個(gè)區(qū)域總的離散點(diǎn)個(gè)數(shù)表示第 區(qū)內(nèi)的節(jié)點(diǎn)個(gè)數(shù)表示區(qū)內(nèi)調(diào)整函

11、數(shù)表示模擬退火的時(shí)間，表征溫度值表示區(qū)間調(diào)整函數(shù)表示全面性指標(biāo)表示不均勻性指標(biāo)表示綜合評(píng)價(jià)指標(biāo)表示第 輛車經(jīng)過每條道路的次數(shù)表示整個(gè)區(qū)域每條道路經(jīng)過的平均次數(shù)模型的建立與算法的設(shè)計(jì)滿足 D1 時(shí)，該區(qū)所需要配置的最少警車數(shù)目和巡邏方案滿足 D1 條件時(shí)，區(qū)域最少警車的規(guī)律題目要求警車的配置和巡邏方案滿足 D1 要求時(shí)，整個(gè)區(qū)域所需要配置的警 車數(shù)目最少。由假設(shè)可知警車都在道路上，且所有事發(fā)現(xiàn)場(chǎng)也都在道路上，但區(qū) 域內(nèi)總的道路長(zhǎng)度是個(gè)定值的；警車在接警后趕到事發(fā)現(xiàn)場(chǎng)有時(shí)間限制和概率限 制：三分鐘內(nèi)趕到普通區(qū)域案發(fā)現(xiàn)場(chǎng)的比例不低于 90，而趕到重點(diǎn)部位的時(shí) 間必須控制在兩分鐘之內(nèi)。由此可知每輛警車

12、的管轄范圍不會(huì)很大，于是考慮將 整個(gè)區(qū)域分成若干個(gè)分區(qū)，每輛警車管轄一個(gè)分區(qū)域。由上面的分析，求解整個(gè)區(qū)域的警車數(shù)目最少這個(gè)問題可轉(zhuǎn)化為求解每一輛警車 所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車管轄的范圍盡量大的 規(guī)律。為了簡(jiǎn)化問題，我們不考慮趕到現(xiàn)場(chǎng)的90%的幾率的限制，僅對(duì)警車能在 三分鐘內(nèi)趕到事發(fā)現(xiàn)場(chǎng)的情況作定性分析，其分析示意圖如圖 1 所示。警車的初 始?？课恢檬请S機(jī)的分布在道路上的任一節(jié)點(diǎn)上，我們假設(shè)一輛警車?？吭贏 點(diǎn)上。圖 1 一輛警車管轄范圍分析示意圖由于警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h，由于距 離信息比較容易得到，于是我們將時(shí)間

13、限制轉(zhuǎn)化為距離限制，這樣便于分析和求 解。當(dāng)警車接警后，在三分鐘內(nèi)能從接警位置趕到事發(fā)現(xiàn)場(chǎng)的最大距離是，其中 。如圖1所示，我們?cè)O(shè)警車初始停靠位置在A點(diǎn)，A點(diǎn)是道路1, 2, 3, 4的道路 交叉口。我們僅以警車在道路 1 巡邏為例來(lái)進(jìn)行分析，警車以的速度在道路 1 上A到點(diǎn)之間巡邏，與初始停靠點(diǎn)A的距離為。由于案件有可能在道路上任一 點(diǎn)發(fā)生，當(dāng)警車巡邏到A點(diǎn)時(shí)，若案發(fā)現(xiàn)場(chǎng)在道路2，3，4上發(fā)生時(shí)，警車以 40km/h 的速度向事發(fā)現(xiàn)場(chǎng)行駛，警車能在三分鐘內(nèi)從點(diǎn)趕到現(xiàn)場(chǎng)的最大距離為。 如果警車在道路 1 上繼續(xù)向前行駛，則該警車能在三分鐘內(nèi)趕到現(xiàn)場(chǎng)的距離繼續(xù) 縮小，當(dāng)警車從初始點(diǎn)向A點(diǎn)行駛但沒

14、有達(dá)到點(diǎn)時(shí)，此時(shí)該警車的最大管轄范圍 比警車到達(dá) 點(diǎn)時(shí)的最大管轄范圍大。為了使警車的管轄范圍盡量大，警車的巡 邏范圍越小越好，當(dāng)時(shí)，即警車在初始?？奎c(diǎn)靜止不動(dòng)時(shí)，警車的管轄范圍達(dá)到 最大值 。圖 1 所分析的是特殊的情況，道路 1， 2， 3， 4 對(duì)稱分布，現(xiàn)在我們來(lái)對(duì)一般的 情況進(jìn)行分析，如圖 2 所示。圖 2.1圖 圖 2.1圖 2 一輛警車最大管轄范圍分析示意圖圖 2.1 所示的情況是道路分布不對(duì)稱，與圖 1 相比，圖 2.1 所示的道路方向和角 度都發(fā)生了改變，圖 2.3 中的情形更為復(fù)雜。參照對(duì)圖 1 的分析方法，我們分析 這兩種情形下，警車巡邏時(shí)能在三分鐘內(nèi)趕到現(xiàn)場(chǎng)的最大距離的規(guī)

15、律，我們只分 析圖2.2的情況，道路1，2，3，4，5相交于點(diǎn)C,同時(shí)道路1與道路6也有個(gè) 道路交叉口 D，由于警車巡邏時(shí)是在道路上行駛的，行走的路線是分段直線，并 不影響路徑的長(zhǎng)度，所以當(dāng)警車巡邏到距離初始?？奎c(diǎn)C點(diǎn)遠(yuǎn)處的D，此時(shí)若有 案件發(fā)生時(shí)，該警車要在三分鐘內(nèi)能趕到現(xiàn)場(chǎng)處理案件，最大行駛距離在之內(nèi)， 如果警車在道路 1 上繼續(xù)向前行駛，則該警車能在三分鐘內(nèi)趕到現(xiàn)場(chǎng)的距離繼續(xù) 縮小，當(dāng)警車沒有行駛到 D 點(diǎn)時(shí)，此時(shí)該警車的最大管轄范圍比大，為了使警車 的管轄范圍盡量大，警車的巡邏范圍越小越好。當(dāng)時(shí)，即警車靜止不動(dòng)時(shí)，一輛 警車的管轄范圍能達(dá)到最大值。以上分析的僅作定性的分析，對(duì)于三個(gè)重點(diǎn)

16、部位也可以同理分析，所得的結(jié)論是 一致的，以上的分析沒有考慮到90%的到達(dá)幾率限制，但在設(shè)計(jì)算法需要充分考 慮。綜上所述，當(dāng)警車靜止在初始?？奎c(diǎn)時(shí)，在三分鐘時(shí)間限制內(nèi)，警車能從初始停 靠點(diǎn)趕到事發(fā)現(xiàn)場(chǎng)的最大距離為。將道路離散化由于事發(fā)現(xiàn)場(chǎng)是等概率地分布在道路上的，由區(qū)域地圖可以發(fā)現(xiàn)，整個(gè)區(qū)域中的 道路長(zhǎng)度不均，為了使計(jì)算結(jié)果更加精確，可將這些道路離散化。只要選取合適 的離散方案，就能使警車在經(jīng)過道路上的離散的點(diǎn)時(shí)就相當(dāng)于經(jīng)過了這條道路。 這樣，不論是求解警車初始?？奎c(diǎn)還求解警車趕到事發(fā)現(xiàn)場(chǎng)所經(jīng)過的道路時(shí)，所 計(jì)算得的的結(jié)果顯然比僅考慮整條道路的叉路口要精確得多。區(qū)域中共有 307 個(gè)道路交叉口

17、，458 條道路。我們采用線性插值方法對(duì)道路進(jìn)行 離散化，以的速度行走一分鐘的距離作為步長(zhǎng)，一分鐘時(shí)間的選擇是參照問題三 的結(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)則是使盡量離散化后警車等效的平均巡邏速度 和題目給定的速度（ ）的差值盡量小，經(jīng)過計(jì)算得時(shí)，不再插入新的坐標(biāo)點(diǎn)時(shí) 能使整個(gè)區(qū)域