談戀愛(ài)之前驚濤駭浪，談戀愛(ài)之后平平淡淡。許愿心想，或許所有的關(guān)系最終都會(huì )走向歲月靜好。

    學(xué)生時(shí)代太忙了，連江昕甜都形容她自己和趙鈞塵為聚少離多，更別說(shuō)卷王許愿和大忙人任博遠。

    膩膩歪歪的時(shí)候也有。兩人一有時(shí)間就互相探索身體，不在一塊兒的時(shí)候也會(huì )互相報備行蹤。一起娛樂(lè )的時(shí)間很少，像尋常的學(xué)生戀愛(ài)：一起看電影、逛校園、去海洋館，那是沒(méi)有的。人都忙著(zhù)學(xué)習和競賽呢。

    這個(gè)學(xué)期許愿的競賽不多，唯一的大賽是明年的HMMT，其它的小競賽對她影響不大的她基本都不打算參加了。她沒(méi)必要去蟬聯(lián)冠軍，又不是奧運會(huì )。

    所以許愿加入了一個(gè)社團——數學(xué)建模社。這個(gè)社團其實(shí)是學(xué)校官方社團，由學(xué)生報名、競賽老師挑選，為全世界各地數學(xué)建模大賽輸送人才，跟別的學(xué)生社團不同。

    許愿開(kāi)始給自己的人生上難度了。她和她臨時(shí)組建的團隊——1名已經(jīng)拿到斯坦福offer的高三學(xué)姐和1名準備走強基計劃進(jìn)入京大的高三學(xué)長(cháng)（3人組隊這個(gè)模式適應比較多的數學(xué)建模大賽團隊要求，比如美國高中生數學(xué)建模競賽HiMCM團隊成員限制2-4人，數維杯全國大學(xué)生數學(xué)建模競賽團隊成員限制1-3人，全國大學(xué)生數學(xué)建模競賽團隊成員限制為3人），開(kāi)始撰寫(xiě)她們人生第一篇論文。

    競賽出題：“有困難找警察〞，是家喻戶(hù)曉的一句流行語(yǔ)。警察肩負著(zhù)刑事執法、治安管理、交通管理、效勞群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區的一些交通要道和重要部位設置交巡警效勞平臺。每個(gè)交巡警效勞平臺的職能和警力配備根本相同。由于警務(wù)資源是有限的，如何根據城市的實(shí)際情況與需求合理地設置交巡警效勞平臺、分配各平臺的管轄范圍、調度警務(wù)資源是警務(wù)部門(mén)面臨的一個(gè)實(shí)際課題。

    試就某市設置交巡警效勞平臺的相關(guān)情況，建立數學(xué)模型分析研究下面的問(wèn)題：

    〔1〕附件1中的附圖1給出了該市中心城區A的交通網(wǎng)絡(luò )和現有的20個(gè)交巡警效勞平臺的設置情況示意圖，相關(guān)的數據信息見(jiàn)附件2。請為各交巡警效勞平臺分配管轄范圍，使其在所管轄的范圍內出現突發(fā)事件時(shí)，盡量能在3分鐘內有交巡警〔警車(chē)的時(shí)速為60km/h〕到達事發(fā)地。

    對于重大突發(fā)事件，需要調度全區20個(gè)交巡警效勞平臺的警力資源，對進(jìn)出該區的13條交通要道實(shí)現快速全封鎖。實(shí)際中一個(gè)平臺的警力最多封鎖一個(gè)路口，請給出該區交巡警效勞平臺警力合理的調度方案。

    根據現有交巡警效勞平臺的工作量不均衡和有些地方出警時(shí)間過(guò)長(cháng)的實(shí)際情況，擬在該區內再增加2至5個(gè)平臺，請確定需要增加平臺的具體個(gè)數和位置。

    〔2〕針對全市〔主城六區A，B，C，D，E，F〕的具體情況，按照設置交巡警效勞平臺的原那么和任務(wù)，分析研究該市現有交巡警效勞平臺設置方案〔參見(jiàn)附件〕的合理性。如果有明顯不合理，請給出解決方案。

    如果該市地點(diǎn)P〔第32個(gè)節點(diǎn)〕處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報警，犯罪嫌疑人已駕車(chē)逃跑。為了快速搜捕嫌疑犯，請給出調度全市交巡警效勞平臺警力資源的最正確圍堵方案。

    她們的論文題目是：交巡警效勞平臺的設置與調度

    摘要：本文研究的是某城區警車(chē)配置及巡邏方案的制定問(wèn)題，建立了求解警車(chē)巡邏方案的模型，并在滿(mǎn)足D1的條件下給出了巡邏效果最好的方案。

    在設計整個(gè)區域配置最少巡邏車(chē)輛時(shí)，本文設計了算法1：先將道路離散化成近似均勻分布的節點(diǎn)，相鄰兩個(gè)節點(diǎn)之間的距離約等于一分鐘巡邏路程。由警車(chē)的數目m,將全區劃分成m個(gè)均勻的分區，從每個(gè)分區的中心點(diǎn)出發(fā)，找到最近的道路節點(diǎn)，作為警車(chē)的初始位置，由Floyd算法算出每輛警車(chē)3分鐘或2分鐘行駛路程范圍內的節點(diǎn)?？紤]區域調整的概率大小和方向不同會(huì )影響調整結果，本文利用模擬退火算法構造出遷移幾率函數，用遷移方向函數決定分區的調整方向。計算能滿(mǎn)足D1的最小車(chē)輛數，即為該區應該配置的最小警車(chē)數目，用MATLAB計算，得到局部最優(yōu)解為13輛。

    在選取巡邏顯著(zhù)性指標時(shí)，本文考慮了兩個(gè)方面的指標：一是全面性，即所有警車(chē)走過(guò)的街道節點(diǎn)數占總街道節點(diǎn)數的比例，用兩者之比來(lái)評價(jià)；二是均勻性，即所有警車(chē)經(jīng)過(guò)每個(gè)節點(diǎn)數的次數偏離平均經(jīng)過(guò)次數的程度，用方差值來(lái)大小評價(jià)。

    問(wèn)題三：為簡(jiǎn)化問(wèn)題，假設所有警車(chē)在同一時(shí)刻，大致向同一方向巡邏，運動(dòng)狀態(tài)分為四種：向左，向右，向上，向下，記錄每個(gè)時(shí)刻，警車(chē)經(jīng)過(guò)的節點(diǎn)和能夠趕去處理事故的點(diǎn)，最后匯總計算得相應的評價(jià)指標。

    在考慮巡邏規律隱蔽性要求時(shí)，文本將巡邏路線(xiàn)進(jìn)行隨機處理，方向是不確定的，采用算法2進(jìn)行計算，得出相應巡邏顯著(zhù)指標，當車(chē)輛數減少到10輛或巡邏速度變大時(shí)，用算法2計算巡邏方案和對應的參數，結果見(jiàn)附錄所示。

    本文最后還考慮到4個(gè)額外因素，給出每個(gè)影響因素的解決方案。

    關(guān)鍵詞：模擬退火算法；Floyd算法；離散化

    論文內容：一   問(wèn)題的重述

    110警車(chē)在街道上巡邏，既能夠對違法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的平安感，同時(shí)也加快了接處警時(shí)間，提高了反響時(shí)效，為社會(huì )和諧提供了有力的保障。

    現給出某城市內一區域，其道路數據和地圖數據，該區域內三個(gè)重點(diǎn)部位的坐標分別為：〔5112，4806〕，〔9126，   4266〕，〔7434   ，1332〕。該區域內共有307個(gè)道路交叉口，為簡(jiǎn)化問(wèn)題，相鄰兩個(gè)交叉路口之間的道路近似認為是直線(xiàn)，且所有事發(fā)現場(chǎng)均在下列圖的道路上。

    該市擬增加一批配備有GPS衛星定位系統及先進(jìn)通訊設備的110警車(chē)。設110警車(chē)的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車(chē)配置及巡邏方案要盡量滿(mǎn)足以下要求：

    D1.   警車(chē)在接警后三分鐘內趕到現場(chǎng)的比例不低于90％；而趕到重點(diǎn)部位的時(shí)間必須在兩分鐘之內。

    D2.   使巡邏效果更顯著(zhù)；

    D3.   警車(chē)巡邏規律應有一定的隱蔽性。

    現在我們需要解決以下幾個(gè)問(wèn)題：

    一.   假設要求滿(mǎn)足D1,該區最少需要配置多少輛警車(chē)巡邏？

    二.   請給出評價(jià)巡邏效果顯著(zhù)程度的有關(guān)指標。

    三．請給出滿(mǎn)足D1且盡量滿(mǎn)足D2條件的警車(chē)巡邏方案及其評價(jià)指標值。

    四.   在第三問(wèn)的根底上，再考慮D3條件，給出你們的警車(chē)巡邏方案及其評價(jià)指標值。

    五．如果該區域僅配置10輛警車(chē)，應如何制定巡邏方案，使D1、D2盡量得到滿(mǎn)足？

    六.   假設警車(chē)接警后的平均行駛速度提高到50km/h，答復下列問(wèn)題三。

    七.   你們認為還有哪些因素、哪些情況需要考慮？給出你們相應的解決方案。

    二   問(wèn)題分析

    此題為城區道路網(wǎng)絡(luò )中警車(chē)配置及巡邏問(wèn)題。在進(jìn)行警車(chē)配置時(shí)，首先要考慮警車(chē)在接警后在規定時(shí)間內趕到現場(chǎng)的比例，在此條件下，以車(chē)數最少為目標，建模、求解；在制定巡邏方案時(shí)，要考慮巡邏的效果及隱蔽性問(wèn)題。

    問(wèn)題一只要求滿(mǎn)足D1，求最少的警車(chē)配置數，可以認為警車(chē)是不動(dòng)的，在三分鐘或兩分鐘內它能到達的區域就是它的覆蓋范圍。據此，在滿(mǎn)足所有街道的覆蓋率不低于90%的條件下，尋找最優(yōu)解。

    問(wèn)題二要評價(jià)巡邏效果，有兩個(gè)方面需要考慮：一是巡邏的全面性，即經(jīng)過(guò)一段時(shí)間后警車(chē)走過(guò)的街道數占總街道數的比例；二是巡邏的不均勻性，即經(jīng)過(guò)一段時(shí)間后警車(chē)經(jīng)過(guò)每一條街道的次數相差不大，用方差來(lái)衡量。

    問(wèn)題三是在滿(mǎn)足D1的條件上盡量滿(mǎn)足問(wèn)題二所給的指標，并給出評價(jià)方案的指標。首先找到一組滿(mǎn)足D1的各警車(chē)位置，然后在和各警車(chē)位置相連的點(diǎn)中隨機尋找一個(gè)點(diǎn)，判斷新的點(diǎn)是否滿(mǎn)足D1，如果滿(mǎn)足那么警車(chē)行駛到該點(diǎn)，否那么重新尋找，直到滿(mǎn)足為止。一段時(shí)間后統計所有車(chē)走過(guò)的點(diǎn)數及每個(gè)點(diǎn)被走過(guò)的次數，用問(wèn)題二給出的兩個(gè)指標進(jìn)行評價(jià)。綜合兩個(gè)指標，可判斷此路徑的好壞，重復這個(gè)過(guò)程，直到綜合評價(jià)指標到達一個(gè)滿(mǎn)意的值為止。

    問(wèn)題四增加了隱蔽性要求，首先給出評價(jià)隱蔽性的指標，隱蔽性可用路線(xiàn)的隨機性來(lái)評價(jià)，將它參加到問(wèn)題三的模型中去進(jìn)行求解。

    問(wèn)題五限制警車(chē)數量為10，要綜合考慮D1、D2，先分配這10輛車(chē)使道路的覆蓋率最高，然后按照問(wèn)題三的步驟進(jìn)行求解，其中每一步對D1的判斷只需使道路的覆蓋率盡量高即可。

    問(wèn)題六同問(wèn)題三，只需將車(chē)速改為50km/h即可。

    三   模型的假設

    警車(chē)都在路上巡邏，巡警去處理案件的時(shí)間不考慮；

    所有事發(fā)現場(chǎng)都在道路上，案件在道路上任一點(diǎn)是等概率發(fā)生的；

    警車(chē)初始?？奎c(diǎn)是隨機的，但盡量讓它們分散分布，一輛警車(chē)管轄一個(gè)分區；

    假定各個(gè)劃分區域內，較短時(shí)間內，最多會(huì )發(fā)生一個(gè)案件；

    假設區域內的每條道路都是雙行線(xiàn)，不考慮轉彎對結果造成的影響；

    如果重點(diǎn)部位不在道路上的，假設這些重點(diǎn)部位在離它們最近的道路上；

    7.   圖中水域對巡邏方案沒(méi)有影響。

    四   符號說(shuō)明

    m   表示警車(chē)數目

    d   表示警車(chē)初始?？奎c(diǎn)到各道路的最短距離

    L   表示整個(gè)區域的總道路長(cháng)度

    l   表示不能在3分鐘內到達的區域的道路的長(cháng)度

    k   表示非重點(diǎn)部位的警車(chē)在3分鐘內不能到達現場(chǎng)的比例

    s   表示三分鐘內能從接警位置趕到事發(fā)現場(chǎng)的最大距離是

    n   表示整個(gè)區域總的離散點(diǎn)個(gè)數

    ni   表示第i區內的節點(diǎn)個(gè)數

    f1   表示區內調整函數

    t   表示模擬退火的時(shí)間，表征溫度值

    f2   表示區間調整函數

    r   表示全面性指標

    e   表示不均勻性指標

    h   表示綜合評價(jià)指標

    si   表示第i輛車(chē)經(jīng)過(guò)每條道路的次數

    -s   表示整個(gè)區域每條道路經(jīng)過(guò)的平均次數

    五   模型的建立與算法的設計

    5.1      滿(mǎn)足D1時(shí)，該區所需要配置的最少警車(chē)數目和巡邏方案

    5.1.1      滿(mǎn)足D1條件時(shí)，區域最少警車(chē)的規律

    題目要求警車(chē)的配置和巡邏方案滿(mǎn)足D1要求時(shí)，整個(gè)區域所需要配置的警車(chē)數目最少。由假設可知警車(chē)都在道路上，且所有事發(fā)現場(chǎng)也都在道路上，但區域內總的道路長(cháng)度是個(gè)定值的；警車(chē)在接警后趕到事發(fā)現場(chǎng)有時(shí)間限制和概率限制：三分鐘內趕到普通區域案發(fā)現場(chǎng)的比例不低于90％，而趕到重點(diǎn)部位的時(shí)間必須控制在兩分鐘之內。由此可知每輛警車(chē)的管轄范圍不會(huì )很大，于是考慮將整個(gè)區域分成假設干個(gè)分區，每輛警車(chē)管轄一個(gè)分區域。

    由上面的分析，求解整個(gè)區域的警車(chē)數目最少這個(gè)問(wèn)題可轉化為求解每一輛警車(chē)所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車(chē)管轄的范圍盡量大的規律。為了簡(jiǎn)化問(wèn)題，我們不考慮趕到現場(chǎng)的90%的幾率的限制，僅對警車(chē)能在三分鐘內趕到事發(fā)現場(chǎng)的情況作定性分析，其分析示意圖如圖1所示。警車(chē)的初始?？课恢檬请S機的分布在道路上的任一節點(diǎn)上，我們假設一輛警車(chē)?？吭贏(yíng)點(diǎn)上。

    圖1      一輛警車(chē)管轄范圍分析示意圖

    由于警車(chē)的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h，由于距離信息比擬容易得到，于是我們將時(shí)間限制轉化為距離限制，這樣便于分析和求解。當警車(chē)接警后，在三分鐘內能從接警位置趕到事發(fā)現場(chǎng)的最大距離是r，其中。

    如圖1所示，我們設警車(chē)初始?？课恢迷贏(yíng)點(diǎn)，A點(diǎn)是道路1，2，3，4的道路交叉口。我們僅以警車(chē)在道路1巡邏為例來(lái)進(jìn)行分析，警車(chē)以的速度在道路1上A到點(diǎn)之間巡邏，與初始?？奎c(diǎn)A的距離為。由于案件有可能在道路上任一點(diǎn)發(fā)生，當警車(chē)巡邏到A點(diǎn)時(shí)，假設案發(fā)現場(chǎng)在道路2，3，4上發(fā)生時(shí)，警車(chē)以40km/h的速度向事發(fā)現場(chǎng)行駛，警車(chē)能在三分鐘內從點(diǎn)趕到現場(chǎng)的最大距離為。如果警車(chē)在道路1上繼續向前行駛，那么該警車(chē)能在三分鐘內趕到現場(chǎng)的距離繼續縮小，當警車(chē)從初始點(diǎn)向A點(diǎn)行駛但沒(méi)有到達點(diǎn)時(shí)，此時(shí)該警車(chē)的最大管轄范圍比警車(chē)到達點(diǎn)時(shí)的最大管轄范圍大。為了使警車(chē)的管轄范圍盡量大，警車(chē)的巡邏范圍越小越好，當時(shí)，即警車(chē)在初始?？奎c(diǎn)靜止不動(dòng)時(shí)，警車(chē)的管轄范圍到達最大值。

    圖1所分析的是特殊的情況，道路1，2，3，4對稱(chēng)分布，現在我們來(lái)對一般的情況進(jìn)行分析，如圖2所示。

    圖2.1                                                                                             圖2.2

    圖2         一輛警車(chē)最大管轄范圍分析示意圖

    圖2.1所示的情況是道路分布不對稱(chēng)，與圖1相比，圖2.1所示的道路方向和角度都發(fā)生了改變，圖2.3中的情形更為復雜。參照對圖1的分析方法，我們分析這兩種情形下，警車(chē)巡邏時(shí)能在三分鐘內趕到現場(chǎng)的最大距離的規律，我們只分析圖2.2的情況，道路1，2，3，4，5相交于點(diǎn)C,同時(shí)道路1與道路6也有個(gè)道路交叉口D，   由于警車(chē)巡邏時(shí)是在道路上行駛的，行走的路線(xiàn)是分段直線(xiàn),并不影響路徑的長(cháng)度，所以當警車(chē)巡邏到距離初始?？奎c(diǎn)C點(diǎn)遠處的D，此時(shí)假設有案件發(fā)生時(shí)，該警車(chē)要在三分鐘內能趕到現場(chǎng)處理案件，最大行駛距離在之內，如果警車(chē)在道路1上繼續向前行駛，那么該警車(chē)能在三分鐘內趕到現場(chǎng)的距離繼續縮小，當警車(chē)沒(méi)有行駛到D點(diǎn)時(shí)，此時(shí)該警車(chē)的最大管轄范圍比大，為了使警車(chē)的管轄范圍盡量大，警車(chē)的巡邏范圍越小越好。當時(shí)，即警車(chē)靜止不動(dòng)時(shí)，一輛警車(chē)的管轄范圍能到達最大值。

    以上分析的僅作定性的分析，對于三個(gè)重點(diǎn)部位也可以同理分析，所得的結論是一致的，以上的分析沒(méi)有考慮到90%的到達幾率限制，但在設計算法需要充分考慮。

    綜上所述，當警車(chē)靜止在初始?？奎c(diǎn)時(shí)，在三分鐘時(shí)間限制內，警車(chē)能從初始?？奎c(diǎn)趕到事發(fā)現場(chǎng)的最大距離為。

    5.1.2      將道路離散化

    由于事發(fā)現場(chǎng)是等概率地分布在道路上的，由區域地圖可以發(fā)現，整個(gè)區域中的道路長(cháng)度不均，為了使計算結果更加精確，可將這些道路離散化。只要選取適宜的離散方案，就能使警車(chē)在經(jīng)過(guò)道路上的離散的點(diǎn)時(shí)就相當于經(jīng)過(guò)了這條道路。這樣，不管是求解警車(chē)初始?？奎c(diǎn)還求解警車(chē)趕到事發(fā)現場(chǎng)所經(jīng)過(guò)的道路時(shí)，所計算得的的結果顯然比僅考慮整條道路的叉路口要精確得多。

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

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

    引進(jìn)臨界指數，選取大小的準那么是使盡量離散化后警車(chē)等效的平均巡邏速度和題目給定的速度〔〕的差值盡量小，經(jīng)過(guò)計算得時(shí)，不再插入新的坐標點(diǎn)時(shí)能使整個(gè)區域的道路離散效果較好。此時(shí)，將CB段長(cháng)度設定為處理，于是離散后的AB道路長(cháng)度會(huì )比實(shí)際長(cháng)度短些；當時(shí)，需要在兩個(gè)點(diǎn)之間再插入一點(diǎn)，因為這樣處理能使整個(gè)區域的整體道路的離散化效果比擬理想。如圖3所示，在C與B間再插入新的坐標點(diǎn)，插入的位置在距C點(diǎn)的D點(diǎn)處,這樣處理后所得的道路長(cháng)度比實(shí)際長(cháng)度長(cháng)了。采用這樣的方法進(jìn)行線(xiàn)性插值，我們使用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ì )影響到調整的方案，所以要綜合考慮這些因素。于是設計了區間調整函數，

    式中，表示第個(gè)分區內未被覆蓋的節點(diǎn)數，表示第分區域與未被覆蓋的節點(diǎn)或節點(diǎn)群的距離，表示未被覆蓋的節點(diǎn)和節點(diǎn)群個(gè)數。

    現在簡(jiǎn)要分析第分區按區間調整函數的調整方案，當某兩節點(diǎn)群的節點(diǎn)數目相等，但是距離不等時(shí)，如，由區間調整公式可知，該區間向節點(diǎn)群方向調整。當某個(gè)分區與兩個(gè)節點(diǎn)群的距離相等，但節點(diǎn)群的內節點(diǎn)個(gè)數不相等，如時(shí)，由〔4〕可知，該分區域會(huì )想節點(diǎn)群方向調整。

    注意在整個(gè)調整過(guò)程中，調整幾率控制是否調整，調整方向函數控制調整的方向，尋找在這種調整方案下的最優(yōu)結果。

    圖5      調整分區域示意圖

    〔3〕在step3中，使用Floyd算法計算出警車(chē)初始?？奎c(diǎn)到周邊各節點(diǎn)的最短距離,目的是當區域內有情況發(fā)生時(shí)，警車(chē)能在要求的時(shí)間限制內到達現場(chǎng)。

    〔4〕為求出較優(yōu)的警車(chē)?？奎c(diǎn)，采用模擬退火算法，算出局部最優(yōu)的方案。

    警車(chē)的配置和巡邏方案

    使用MATLAB編程實(shí)現算法1得到，整個(gè)區域配備13輛警車(chē)，這些警車(chē)靜止在初始?？奎c(diǎn)時(shí)，能滿(mǎn)足D1要求。警車(chē)的初始?？课恢梅謩e為道路交叉節點(diǎn)6，25，30，37，82，84，110，111，126，214，253，258，278處。每個(gè)警車(chē)所管轄的交叉點(diǎn)〔原始的交叉節點(diǎn)〕如圖6所示，求解的分區結果見(jiàn)附錄所示。

    圖6   滿(mǎn)足D1條件下的區分劃分圖

    13個(gè)分區共覆蓋了252個(gè)交叉點(diǎn)，另外的55個(gè)原始交叉點(diǎn)沒(méi)有被這些分區域覆蓋：137，138，151，159，167，168，170，174，175，186，188，189，211，215，226，242，255，260，261，262，263，267，270，271，272，275，282，283，284，287，288，289，292，296，297，299，304，305，307。在這種分區方案下，這些點(diǎn)中，每?jì)蓚€(gè)相連的點(diǎn)間的道路離散值長(cháng)度占整個(gè)區域總的長(cháng)度的比值為。因此，在整個(gè)區域配置13輛警車(chē)，每個(gè)警車(chē)在初始?？奎c(diǎn)靜止不動(dòng)，當有案件發(fā)生時(shí)，離案發(fā)現場(chǎng)最近的警車(chē)從初始?？奎c(diǎn)趕到現場(chǎng)。

    評價(jià)巡邏效果顯著(zhù)的指標

    110警車(chē)在街道上巡邏是目的是為了對違法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的平安感，同時(shí)還加快了接處警〔接受報警并趕往現場(chǎng)處理事件〕時(shí)間，提高了反響時(shí)效，為社會(huì )和諧提供了有力的保障。巡警在城市繁華街道、公共場(chǎng)所執行巡邏任務(wù),   維護治安,   效勞群眾,   可以得良好的社會(huì )效應[1]。

    在整個(gè)區域中，由于案發(fā)現場(chǎng)都在道路上，道路上的每一點(diǎn)都是等概率發(fā)生的，因此警車(chē)巡邏的面越廣，所巡邏的街道數目越多，警車(chē)的巡邏效果就越好，對違法犯罪分子就越有威懾力，警車(chē)也能更及時(shí)地處理案件。

    我們采用全面性來(lái)衡量巡邏的效果顯著(zhù)性，即用警車(chē)巡邏所經(jīng)過(guò)的街道節點(diǎn)數占區域總節點(diǎn)數的比值。當警車(chē)重復經(jīng)過(guò)同一條街道同一個(gè)離散點(diǎn)時(shí)，僅記錄一次。

    〔3〕

    式中，表示警車(chē)經(jīng)過(guò)的離散點(diǎn)數，代表整個(gè)區域總的離散點(diǎn)數。值越大，說(shuō)明警車(chē)所經(jīng)過(guò)的街道數目越多，所取得的效果越顯著(zhù)。

    同時(shí)考慮到在巡邏過(guò)程中可能會(huì )出現這樣的情況：在相同的時(shí)段內，警車(chē)會(huì )屢次巡邏局部街道，而一些街道卻很少巡邏甚至沒(méi)有警車(chē)到達，這樣會(huì )造成一些巡邏盲區。分布很不均衡。這樣就可能出現巡邏密度大的街道上的違法犯罪分子不敢在街道上作案，而流竄到巡邏密度稀疏的街道上作案，因此在相同的警車(chē)數目條件下，密度不均衡的巡邏方式的巡邏效果的效果較差，而密度較均衡的巡邏方式所取得的巡邏效果會(huì )更好些。我們引入一個(gè)巡邏的不均勻度來(lái)衡量巡邏效果的顯著(zhù)性，考慮到方差能表示不均衡度，于是我們用方差的大小來(lái)表征不均衡，方差越大，巡邏密度越不均衡，所取得的巡邏效果越差。

    〔4〕

    問(wèn)題1所給出的滿(mǎn)足D1條件下的警車(chē)數目為13輛，這時(shí)每輛警車(chē)在初始?？奎c(diǎn)靜止不動(dòng)，只有該管轄區域內發(fā)生了案件時(shí)，警車(chē)才從初始?？奎c(diǎn)趕到案發(fā)現場(chǎng)處理案件。當警車(chē)在巡邏狀態(tài)時(shí)，所需要考慮的問(wèn)題就更復雜一些，如當節點(diǎn)運動(dòng)時(shí)，警車(chē)還能否到達D1的要求，警車(chē)的運動(dòng)方向如何等問(wèn)題，但根本算法思想與問(wèn)題1類(lèi)似，所得的算法2的框圖如圖7所示，

    為了簡(jiǎn)化問(wèn)題，我們假設各分區警車(chē)的巡邏時(shí)候，盡量保證所有的警車(chē)的行駛方向相一致，且警車(chē)都走雙行道，即當警車(chē)走到某個(gè)節點(diǎn)后，它們又同時(shí)返回初始?？奎c(diǎn)，警車(chē)的行駛方向有四種方式，如6所示。

    在圖6中，數字1代表走巡邏走的第一步，2表示朝1的巡邏方向相反的方向巡邏。在具體程序實(shí)現時(shí)，四種巡邏方向任意選擇，但是盡量保證所有的警車(chē)向同一個(gè)方向巡邏。

    圖6      各警車(chē)巡邏方向圖

    我們用MATLAB編程對這種巡邏方式進(jìn)行計算，所得的車(chē)輛數目為18輛，綜合評價(jià)指標為，其結果巡邏方案見(jiàn)附件中的“1193402-Result3.txt〞所示。

    在滿(mǎn)足問(wèn)題三的根底上討論D3條件，警車(chē)的巡邏方案和評價(jià)指標

    巡邏的隱蔽性表達在警車(chē)的巡邏路線(xiàn)和時(shí)間沒(méi)有明顯的規律，主要目的是讓違法犯罪分子無(wú)可乘之機，防止他們在非巡邏時(shí)間實(shí)施違法犯罪活動(dòng)，危害人民的生命和財產(chǎn)平安。

    為了使巡邏的規律具有隱蔽性，這就需要警車(chē)在巡邏時(shí)至少具有兩條不同的路線(xiàn)，時(shí)間最好也是不相同的。因此，考慮到隱蔽性時(shí)，只需要在問(wèn)題2的根底上加上一個(gè)隨機過(guò)程即可。對于其評價(jià)指標，由于警車(chē)有幾條可選的巡邏路線(xiàn)，當相同的路線(xiàn)在同一時(shí)間內重復出現時(shí)，重新將所設定的方案再執行一遍，我們用這個(gè)時(shí)間間隔來(lái)衡量隱蔽性的程度，當循環(huán)周期越大，說(shuō)明可選的巡邏方案越多，其規律就越具有隱蔽性，而循環(huán)周期越小時(shí)，說(shuō)明巡邏方案比擬少，其隱蔽性較差。在巡邏狀態(tài)時(shí)，最差的隱蔽性巡邏方案是巡邏方案只有一個(gè)，并且時(shí)間固定，這樣的巡邏方案沒(méi)有任何隱蔽性可言。

    5.5      整個(gè)區域為10輛車(chē)時(shí)的巡邏方案

    由第三問(wèn)的結果可知，10輛車(chē)的數量是不能把整個(gè)區域完全覆蓋的，其算法與算法2類(lèi)似，不同的是此時(shí)車(chē)的數目已經(jīng)固定了，要求使D1,D2盡量大的滿(mǎn)足，我們求得的評價(jià)指標值為，所得的巡邏方案見(jiàn)附件中的“1193402-Result5.txt〞所示。

    5.6      平均行駛速度提高到時(shí)的巡邏方式和評價(jià)指標值

    問(wèn)題六的分析方法與具體實(shí)現與問(wèn)題三一致，但是警車(chē)的接警后的平均速度由原來(lái)的提高到，于是各分區的覆蓋范圍也增大了，將數值帶入問(wèn)題3的算法中求解，   計算得的指標值為，其巡邏方案見(jiàn)附件中的“1193402-Result6.txt〞所示。

    圖7      算法2框圖

    六      模型的分析和評價(jià)

    在求解滿(mǎn)足D1的條件下，整個(gè)區域需要配備多少輛警車(chē)問(wèn)題中，采用分區巡邏的思想，先分析能使各區管轄范圍到達最大值時(shí)的規律，由特殊到一般層層進(jìn)行分析，邏輯嚴密，結果合理。

    在求解區域和警車(chē)數目時(shí)，在初步設定警車(chē)?？奎c(diǎn)位置的根底上，用模擬退火算法思路構造函數來(lái)確定調整的概率大小，綜合考慮了影響區間調整的因素后構造了函數來(lái)確定分區的調整方向，當分區按照這兩個(gè)調整函數進(jìn)行調整時(shí)，各分區能管轄盡可能多的道路節點(diǎn)，所取得效果也比擬理想。

    參   考   文   獻

    [1]中小城市警察巡邏勤務(wù)方式的探討，俞詳，江蘇公安專(zhuān)科學(xué)校學(xué)報，1998年第1期

    [2]Matlab7.0從入門(mén)到精通，求是科技，人民郵電出版社；

    [3]不確定車(chē)數的隨機車(chē)輛路徑問(wèn)題模型及算法，運懷立等，工業(yè)工程，第10卷第3期，2005年5月；

    [4]隨機交通分配中的有效路徑確實(shí)定方法，李志純等，交通運輸系統工程與信息，第3卷第1期，2003年2月。

    附         錄

    圖   問(wèn)題三巡邏路徑

    圖   問(wèn)題五巡邏路徑

    圖   問(wèn)題六巡邏路徑