2023全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題題目及參考答案

2023高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目〔請(qǐng)先閱讀“全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽論文格式標(biāo)準(zhǔn)〞〕B題交巡警效勞平臺(tái)的設(shè)置與調(diào)度“有困難找警察〞，是家喻戶曉的一句流行語(yǔ)。警察肩負(fù)著刑事執(zhí)法、治安管理、交通管理、效勞群眾四大職能。為了更有效地貫徹實(shí)施這些職能，需要在市區(qū)的一些交通要道和重要部位設(shè)置交巡警效勞平臺(tái)。每個(gè)交巡警效勞平臺(tái)的職能和警力配備根本相同。由于警務(wù)資源是有限的，如何根據(jù)城市的實(shí)際情況與需求合理地設(shè)置交巡警效勞平臺(tái)、分配各平臺(tái)的管轄范圍、調(diào)度警務(wù)資源是警務(wù)部門(mén)面臨的一個(gè)實(shí)際課題。試就某市設(shè)置交巡警效勞平臺(tái)的相關(guān)情況，建立數(shù)學(xué)模型分析研究下面的問(wèn)題：〔1〕附件1中的附圖1給出了該市中心城區(qū)A的交通網(wǎng)絡(luò)和現(xiàn)有的20個(gè)交巡警效勞平臺(tái)的設(shè)置情況示意圖，相關(guān)的數(shù)據(jù)信息見(jiàn)附件2。請(qǐng)為各交巡警效勞平臺(tái)分配管轄范圍，使其在所管轄的范圍內(nèi)出現(xiàn)突發(fā)事件時(shí)，盡量能在3分鐘內(nèi)有交巡警〔警車的時(shí)速為60km/h〕到達(dá)事發(fā)地。對(duì)于重大突發(fā)事件，需要調(diào)度全區(qū)20個(gè)交巡警效勞平臺(tái)的警力資源，對(duì)進(jìn)出該區(qū)的13條交通要道實(shí)現(xiàn)快速全封鎖。實(shí)際中一個(gè)平臺(tái)的警力最多封鎖一個(gè)路口，請(qǐng)給出該區(qū)交巡警效勞平臺(tái)警力合理的調(diào)度方案。根據(jù)現(xiàn)有交巡警效勞平臺(tái)的工作量不均衡和有些地方出警時(shí)間過(guò)長(zhǎng)的實(shí)際情況，擬在該區(qū)內(nèi)再增加2至5個(gè)平臺(tái)，請(qǐng)確定需要增加平臺(tái)的具體個(gè)數(shù)和位置?！?〕針對(duì)全市〔主城六區(qū)A，B，C，D，E，F(xiàn)〕的具體情況，按照設(shè)置交巡警效勞平臺(tái)的原那么和任務(wù)，分析研究該市現(xiàn)有交巡警效勞平臺(tái)設(shè)置方案〔參見(jiàn)附件〕的合理性。如果有明顯不合理，請(qǐng)給出解決方案。如果該市地點(diǎn)P〔第32個(gè)節(jié)點(diǎn)〕處發(fā)生了重大刑事案件，在案發(fā)3分鐘后接到報(bào)警，犯罪嫌疑人已駕車逃跑。為了快速搜捕嫌疑犯，請(qǐng)給出調(diào)度全市交巡警效勞平臺(tái)警力資源的最正確圍堵方案。題目B題交巡警效勞平臺(tái)的設(shè)置與調(diào)度摘要：本文研究的是某城區(qū)警車配置及巡邏方案的制定問(wèn)題，建立了求解警車巡邏方案的模型，并在滿足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é)果，本文利用模擬退火算法構(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)：一是全面性，即所有警車走過(guò)的街道節(jié)點(diǎn)數(shù)占總街道節(jié)點(diǎn)數(shù)的比例，用兩者之比來(lái)評(píng)價(jià)；二是均勻性，即所有警車經(jīng)過(guò)每個(gè)節(jié)點(diǎn)數(shù)的次數(shù)偏離平均經(jīng)過(guò)次數(shù)的程度，用方差值來(lái)大小評(píng)價(jià)。問(wèn)題三：為簡(jiǎn)化問(wèn)題，假設(shè)所有警車在同一時(shí)刻，大致向同一方向巡邏，運(yùn)動(dòng)狀態(tài)分為四種：向左，向右，向上，向下，記錄每個(gè)時(shí)刻，警車經(jīng)過(guò)的節(jié)點(diǎn)和能夠趕去處理事故的點(diǎn)，最后匯總計(jì)算得相應(yīng)的評(píng)價(jià)指標(biāo)。在考慮巡邏規(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é)果見(jiàn)附錄所示。本文最后還考慮到4個(gè)額外因素，給出每個(gè)影響因素的解決方案。關(guān)鍵詞：模擬退火算法；Floyd算法；離散化參賽密碼〔由組委會(huì)填寫(xiě)〕參賽隊(duì)號(hào)參賽密碼〔由組委會(huì)填寫(xiě)〕隊(duì)員姓名一問(wèn)題的重述110警車在街道上巡邏，既能夠?qū)`法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的平安感，同時(shí)也加快了接處警時(shí)間，提高了反響時(shí)效，為社會(huì)和諧提供了有力的保障。現(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)化問(wè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è)問(wèn)題：一.假設(shè)要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？二.請(qǐng)給出評(píng)價(jià)巡邏效果顯著程度的有關(guān)指標(biāo)。三．請(qǐng)給出滿足D1且盡量滿足D2條件的警車巡邏方案及其評(píng)價(jià)指標(biāo)值。四.在第三問(wèn)的根底上，再考慮D3條件，給出你們的警車巡邏方案及其評(píng)價(jià)指標(biāo)值。五．如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使D1、D2盡量得到滿足？六.假設(shè)警車接警后的平均行駛速度提高到50km/h，答復(fù)下列問(wèn)題三。七.你們認(rèn)為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。二問(wèn)題分析此題為城區(qū)道路網(wǎng)絡(luò)中警車配置及巡邏問(wèn)題。在進(jìn)行警車配置時(shí)，首先要考慮警車在接警后在規(guī)定時(shí)間內(nèi)趕到現(xiàn)場(chǎng)的比例，在此條件下，以車數(shù)最少為目標(biāo)，建模、求解；在制定巡邏方案時(shí)，要考慮巡邏的效果及隱蔽性問(wèn)題。問(wèn)題一只要求滿足D1，求最少的警車配置數(shù)，可以認(rèn)為警車是不動(dòng)的，在三分鐘或兩分鐘內(nèi)它能到達(dá)的區(qū)域就是它的覆蓋范圍。據(jù)此，在滿足所有街道的覆蓋率不低于90%的條件下，尋找最優(yōu)解。問(wèn)題二要評(píng)價(jià)巡邏效果，有兩個(gè)方面需要考慮：一是巡邏的全面性，即經(jīng)過(guò)一段時(shí)間后警車走過(guò)的街道數(shù)占總街道數(shù)的比例；二是巡邏的不均勻性，即經(jīng)過(guò)一段時(shí)間后警車經(jīng)過(guò)每一條街道的次數(shù)相差不大，用方差來(lái)衡量。問(wèn)題三是在滿足D1的條件上盡量滿足問(wèn)題二所給的指標(biāo)，并給出評(píng)價(jià)方案的指標(biāo)。首先找到一組滿足D1的各警車位置，然后在和各警車位置相連的點(diǎn)中隨機(jī)尋找一個(gè)點(diǎn)，判斷新的點(diǎn)是否滿足D1，如果滿足那么警車行駛到該點(diǎn)，否那么重新尋找，直到滿足為止。一段時(shí)間后統(tǒng)計(jì)所有車走過(guò)的點(diǎn)數(shù)及每個(gè)點(diǎn)被走過(guò)的次數(shù)，用問(wèn)題二給出的兩個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。綜合兩個(gè)指標(biāo)，可判斷此路徑的好壞，重復(fù)這個(gè)過(guò)程，直到綜合評(píng)價(jià)指標(biāo)到達(dá)一個(gè)滿意的值為止。問(wèn)題四增加了隱蔽性要求，首先給出評(píng)價(jià)隱蔽性的指標(biāo)，隱蔽性可用路線的隨機(jī)性來(lái)評(píng)價(jià)，將它參加到問(wèn)題三的模型中去進(jìn)行求解。問(wèn)題五限制警車數(shù)量為10，要綜合考慮D1、D2，先分配這10輛車使道路的覆蓋率最高，然后按照問(wèn)題三的步驟進(jìn)行求解，其中每一步對(duì)D1的判斷只需使道路的覆蓋率盡量高即可。問(wèn)題六同問(wèn)題三，只需將車速改為50km/h即可。三模型的假設(shè)警車都在路上巡邏，巡警去處理案件的時(shí)間不考慮；所有事發(fā)現(xiàn)場(chǎng)都在道路上，案件在道路上任一點(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)部位在離它們最近的道路上；7.圖中水域?qū)ρ策壏桨笡](méi)有影響。四符號(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)整函數(shù)表示模擬退火的時(shí)間，表征溫度值表示區(qū)間調(diào)整函數(shù)表示全面性指標(biāo)表示不均勻性指標(biāo)表示綜合評(píng)價(jià)指標(biāo)表示第輛車經(jīng)過(guò)每條道路的次數(shù)表示整個(gè)區(qū)域每條道路經(jīng)過(guò)的平均次數(shù)五模型的建立與算法的設(shè)計(jì)5.1滿足D1時(shí)，該區(qū)所需要配置的最少警車數(shù)目和巡邏方案5.1.1滿足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)。由此可知每輛警車的管轄范圍不會(huì)很大，于是考慮將整個(gè)區(qū)域分成假設(shè)干個(gè)分區(qū)，每輛警車管轄一個(gè)分區(qū)域。由上面的分析，求解整個(gè)區(qū)域的警車數(shù)目最少這個(gè)問(wèn)題可轉(zhuǎn)化為求解每一輛警車所能管轄的街道范圍盡量的大。于是我們尋找出使每輛警車管轄的范圍盡量大的規(guī)律。為了簡(jiǎn)化問(wè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í)間限制轉(zhuǎn)化為距離限制，這樣便于分析和求解。當(dāng)警車接警后，在三分鐘內(nèi)能從接警位置趕到事發(fā)現(xiàn)場(chǎng)的最大距離是，其中。如圖1所示，我們?cè)O(shè)警車初始?？课恢迷贏點(diǎn)，A點(diǎn)是道路1，2，3，4的道路交叉口。我們僅以警車在道路1巡邏為例來(lái)進(jìn)行分析，警車以的速度在道路1上A到點(diǎn)之間巡邏，與初始?？奎c(diǎn)A的距離為。由于案件有可能在道路上任一點(diǎn)發(fā)生，當(dāng)警車巡邏到A點(diǎn)時(shí)，假設(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)行駛但沒(méi)有到達(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.2圖2一輛警車最大管轄范圍分析示意圖圖2.1所示的情況是道路分布不對(duì)稱，與圖1相比，圖2.1所示的道路方向和角度都發(fā)生了改變，圖2.3中的情形更為復(fù)雜。參照對(duì)圖1的分析方法，我們分析這兩種情形下，警車巡邏時(shí)能在三分鐘內(nèi)趕到現(xiàn)場(chǎng)的最大距離的規(guī)律，我們只分析圖2.2的情況，道路1，2，3，4，5相交于點(diǎn)C,同時(shí)道路1與道路6也有個(gè)道路交叉口D，由于警車巡邏時(shí)是在道路上行駛的，行走的路線是分段直線,并不影響路徑的長(zhǎng)度，所以當(dāng)警車巡邏到距離初始停靠點(diǎn)C點(diǎn)遠(yuǎn)處的D，此時(shí)假設(shè)有案件發(fā)生時(shí)，該警車要在三分鐘內(nèi)能趕到現(xiàn)場(chǎng)處理案件，最大行駛距離在之內(nèi)，如果警車在道路1上繼續(xù)向前行駛，那么該警車能在三分鐘內(nèi)趕到現(xiàn)場(chǎng)的距離繼續(xù)縮小，當(dāng)警車沒(méi)有行駛到D點(diǎn)時(shí)，此時(shí)該警車的最大管轄范圍比大，為了使警車的管轄范圍盡量大，警車的巡邏范圍越小越好。當(dāng)時(shí)，即警車靜止不動(dòng)時(shí)，一輛警車的管轄范圍能到達(dá)最大值。以上分析的僅作定性的分析，對(duì)于三個(gè)重點(diǎn)部位也可以同理分析，所得的結(jié)論是一致的，以上的分析沒(méi)有考慮到90%的到達(dá)幾率限制，但在設(shè)計(jì)算法需要充分考慮。綜上所述，當(dāng)警車靜止在初始停靠點(diǎn)時(shí)，在三分鐘時(shí)間限制內(nèi)，警車能從初始?？奎c(diǎn)趕到事發(fā)現(xiàn)場(chǎng)的最大距離為。5.1.2將道路離散化由于事發(fā)現(xiàn)場(chǎng)是等概率地分布在道路上的，由區(qū)域地圖可以發(fā)現(xiàn)，整個(gè)區(qū)域中的道路長(zhǎng)度不均，為了使計(jì)算結(jié)果更加精確，可將這些道路離散化。只要選取適宜的離散方案，就能使警車在經(jīng)過(guò)道路上的離散的點(diǎn)時(shí)就相當(dāng)于經(jīng)過(guò)了這條道路。這樣，不管是求解警車初始停靠點(diǎn)還求解警車趕到事發(fā)現(xiàn)場(chǎng)所經(jīng)過(guò)的道路時(shí)，所計(jì)算得的的結(jié)果顯然比僅考慮整條道路的叉路口要精確得多。區(qū)域中共有307個(gè)道路交叉口，458條道路。我們采用線性插值方法對(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)那么是使盡量離散化后警車等效的平均巡邏速度和題目給定的速度〔〕的差值盡量小，經(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)行線性插值，我們使用MATLAB編程實(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)附件中的“newpoint.txt〞。圖4整個(gè)區(qū)域離散結(jié)果圖采用這種插值方法道路離散后，將直線上的無(wú)窮多個(gè)點(diǎn)轉(zhuǎn)化有限個(gè)點(diǎn)，便于分析問(wèn)題和實(shí)現(xiàn)相應(yīng)的算法，由圖4可知，所取得的整體離散效果還是比擬理想的。5.1.3分區(qū)域求解警車數(shù)目的算法設(shè)計(jì)考慮到警車配置和巡邏方案需要滿足：警車在接警后三分鐘內(nèi)趕到普通部位案發(fā)現(xiàn)場(chǎng)的比例不低于90%，趕到重點(diǎn)部位必須控制在兩分鐘之內(nèi)的要求。設(shè)計(jì)算法的目標(biāo)就是求解出在滿足D1情況下，總的警車數(shù)目最小，即每個(gè)區(qū)域都盡可能多地覆蓋道路節(jié)點(diǎn)。由于警車的初始位置是未知的，我們可設(shè)警車初始?？奎c(diǎn)在道路上的任一點(diǎn)，即分布在圖4所示的762個(gè)離散點(diǎn)中的某些點(diǎn)節(jié)點(diǎn)上，總體思路是讓每?jī)奢v車之間盡量分散地分布，一輛警車管轄一個(gè)分區(qū)，用這些分區(qū)覆蓋整個(gè)區(qū)域。于是我們?cè)O(shè)計(jì)算法1，步驟如下所示：Step1：將整個(gè)區(qū)域預(yù)分配為個(gè)分區(qū)，每個(gè)分區(qū)分配一輛警車，警車的初始?？课恢迷O(shè)在預(yù)分配區(qū)中心的道路節(jié)點(diǎn)上，假設(shè)區(qū)域的中心不在道路節(jié)點(diǎn)上，那么將警車放在離中心最近的道路節(jié)點(diǎn)上；Step2：統(tǒng)計(jì)分區(qū)不能覆蓋的節(jié)點(diǎn)，調(diào)整警車的初始?？奎c(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)整車輛初始點(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í)，將警車初始位置的調(diào)整方向?yàn)槌@些未被覆蓋的節(jié)點(diǎn)按一定的規(guī)那么〔在對(duì)算法的幾點(diǎn)說(shuō)明：〔1〕該算法所取的車輛數(shù)是由多到少進(jìn)行計(jì)算的，初始值設(shè)為20，這個(gè)值的選取是根據(jù)區(qū)域圖估算的。(2)預(yù)分區(qū)的優(yōu)點(diǎn)在于使警車的初始位置盡可能均勻地分散分布，警車的初始停靠點(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)整概率。警車調(diào)整借鑒的是模擬退火算法的方法，為了使分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)較多的分區(qū)的初始停車點(diǎn)調(diào)整的概率小些，而分區(qū)內(nèi)包含道路節(jié)點(diǎn)數(shù)的少的分區(qū)內(nèi)的初始停車點(diǎn)調(diào)整的概率大些，我們構(gòu)造了一個(gè)調(diào)整概率函數(shù),〔1〕〔1〕式中，均為常數(shù)，為整個(gè)區(qū)域車輛數(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í)間〕的條件下，由于總的車輛數(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ū)的警車初始?？课恢眠x取地比擬適宜了，而當(dāng)分區(qū)內(nèi)包含的道路節(jié)點(diǎn)數(shù)較少時(shí)，說(shuō)明警車的初始停靠位置沒(méi)有選好，需要更大概率的調(diào)整，這樣的結(jié)論也是比擬客觀的。對(duì)于所有分區(qū)外未被覆蓋的道路節(jié)點(diǎn)和很多節(jié)點(diǎn)〔稱之為節(jié)點(diǎn)群〕，用來(lái)調(diào)整警車位置遷移的方向，其分析示意圖如圖5所示。調(diào)整方案目標(biāo)是使未被覆蓋的節(jié)點(diǎn)數(shù)盡量的少。在設(shè)計(jì)調(diào)整方向函數(shù)時(shí)，需要考慮：〔1〕節(jié)點(diǎn)群內(nèi)節(jié)點(diǎn)的數(shù)目；〔2〕警車距離節(jié)點(diǎn)群的位置。優(yōu)先考慮距離，所以在公式〔2〕中，用距離的平方來(lái)描述調(diào)整方向函數(shù)。由于某一個(gè)區(qū)域范圍內(nèi)的未被覆蓋節(jié)點(diǎn)數(shù)，整個(gè)區(qū)域未被覆蓋的節(jié)點(diǎn)總數(shù)，分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離等幾個(gè)因素會(huì)影響到調(diào)整的方案，所以要綜合考慮這些因素。于是設(shè)計(jì)了區(qū)間調(diào)整函數(shù)，式中，表示第個(gè)分區(qū)內(nèi)未被覆蓋的節(jié)點(diǎn)數(shù)，表示第分區(qū)域與未被覆蓋的節(jié)點(diǎn)或節(jié)點(diǎn)群的距離，表示未被覆蓋的節(jié)點(diǎn)和節(jié)點(diǎn)群個(gè)數(shù)。現(xiàn)在簡(jiǎn)要分析第分區(qū)按區(qū)間調(diào)整函數(shù)的調(diào)整方案，當(dāng)某兩節(jié)點(diǎn)群的節(jié)點(diǎn)數(shù)目相等，但是距離不等時(shí)，如，由區(qū)間調(diào)整公式可知，該區(qū)間向節(jié)點(diǎn)群方向調(diào)整。當(dāng)某個(gè)分區(qū)與兩個(gè)節(jié)點(diǎn)群的距離相等，但節(jié)點(diǎn)群的內(nèi)節(jié)點(diǎn)個(gè)數(shù)不相等，如時(shí)，由〔4〕可知，該分區(qū)域會(huì)想節(jié)點(diǎn)群方向調(diào)整。注意在整個(gè)調(diào)整過(guò)程中，調(diào)整幾率控制是否調(diào)整，調(diào)整方向函數(shù)控制調(diào)整的方向，尋找在這種調(diào)整方案下的最優(yōu)結(jié)果。圖5調(diào)整分區(qū)域示意圖〔3〕在step3中，使用Floyd算法計(jì)算出警車初始停靠點(diǎn)到周邊各節(jié)點(diǎn)的最短距離,目的是當(dāng)區(qū)域內(nèi)有情況發(fā)生時(shí)，警車能在要求的時(shí)間限制內(nèi)到達(dá)現(xiàn)場(chǎng)?！?〕為求出較優(yōu)的警車?？奎c(diǎn)，采用模擬退火算法，算出局部最優(yōu)的方案。警車的配置和巡邏方案使用MATLAB編程實(shí)現(xiàn)算法1得到，整個(gè)區(qū)域配備13輛警車，這些警車靜止在初始停靠點(diǎn)時(shí)，能滿足D1要求。警車的初始停靠位置分別為道路交叉節(jié)點(diǎn)6，25，30，37，82，84，110，111，126，214，253，258，278處。每個(gè)警車所管轄的交叉點(diǎn)〔原始的交叉節(jié)點(diǎn)〕如圖6所示，求解的分區(qū)結(jié)果見(jiàn)附錄所示。圖6滿足D1條件下的區(qū)分劃分圖13個(gè)分區(qū)共覆蓋了252個(gè)交叉點(diǎn)，另外的55個(gè)原始交叉點(diǎn)沒(méi)有被這些分區(qū)域覆蓋：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。在這種分區(qū)方案下，這些點(diǎn)中，每?jī)蓚€(gè)相連的點(diǎn)間的道路離散值長(zhǎng)度占整個(gè)區(qū)域總的長(zhǎng)度的比值為。因此，在整個(gè)區(qū)域配置13輛警車，每個(gè)警車在初始停靠點(diǎn)靜止不動(dòng)，當(dāng)有案件發(fā)生時(shí)，離案發(fā)現(xiàn)場(chǎng)最近的警車從初始?？奎c(diǎn)趕到現(xiàn)場(chǎng)。評(píng)價(jià)巡邏效果顯著的指標(biāo)110警車在街道上巡邏是目的是為了對(duì)違法犯罪分子起到震懾作用，降低犯罪率，又能夠增加市民的平安感，同時(shí)還加快了接處警〔接受報(bào)警并趕往現(xiàn)場(chǎng)處理事件〕時(shí)間，提高了反響時(shí)效，為社會(huì)和諧提供了有力的保障。巡警在城市繁華街道、公共場(chǎng)所執(zhí)行巡邏任務(wù),維護(hù)治安,效勞群眾,可以得良好的社會(huì)效應(yīng)[1]。在整個(gè)區(qū)域中，由于案發(fā)現(xiàn)場(chǎng)都在道路上，道路上的每一點(diǎn)都是等概率發(fā)生的，因此警車巡邏的面越廣，所巡邏的街道數(shù)目越多，警車的巡邏效果就越好，對(duì)違法犯罪分子就越有威懾力，警車也能更及時(shí)地處理案件。我們采用全面性來(lái)衡量巡邏的效果顯著性，即用警車巡邏所經(jīng)過(guò)的街道節(jié)點(diǎn)數(shù)占區(qū)域總節(jié)點(diǎn)數(shù)的比值。當(dāng)警車重復(fù)經(jīng)過(guò)同一條街道同一個(gè)離散點(diǎn)時(shí)，僅記錄一次?！?〕式中，表示警車經(jīng)過(guò)的離散點(diǎn)數(shù)，代表整個(gè)區(qū)域總的離散點(diǎn)數(shù)。值越大，說(shuō)明警車所經(jīng)過(guò)的街道數(shù)目越多，所取得的效果越顯著。同時(shí)考慮到在巡邏過(guò)程中可能會(huì)出現(xiàn)這樣的情況：在相同的時(shí)段內(nèi)，警車會(huì)屢次巡邏局部街道，而一些街道卻很少巡邏甚至沒(méi)有警車到達(dá)，這樣會(huì)造成一些巡邏盲區(qū)。分布很不均衡。這樣就可能出現(xiàn)巡邏密度大的街道上的違法犯罪分子不敢在街道上作案，而流竄到巡邏密度稀疏的街道上作案，因此在相同的警車數(shù)目條件下，密度不均衡的巡邏方式的巡邏效果的效果較差，而密度較均衡的巡邏方式所取得的巡邏效果會(huì)更好些。我們引入一個(gè)巡邏的不均勻度來(lái)衡量巡邏效果的顯著性，考慮到方差能表示不均衡度，于是我們用方差的大小來(lái)表征不均衡，方差越大，巡邏密度越不均衡，所取得的巡邏效果越差?！?〕問(wèn)題1所給出的滿足D1條件下的警車數(shù)目為13輛，這時(shí)每輛警車在初始停靠點(diǎn)靜止不動(dòng)，只有該管轄區(qū)域內(nèi)發(fā)生了案件時(shí)，警車才從初始?？奎c(diǎn)趕到案發(fā)現(xiàn)場(chǎng)處理案件。當(dāng)警車在巡邏狀態(tài)時(shí)，所需要考慮的問(wèn)題就更復(fù)雜一些，如當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)時(shí)，警車還能否到達(dá)D1的要求，警車的運(yùn)動(dòng)方向如何等問(wèn)題，但根本算法思想與問(wèn)題1類似，所得的算法2的框圖如圖7所示，為了簡(jiǎn)化問(wèn)題，我們假設(shè)各分區(qū)警車的巡邏時(shí)候，盡量保證所有的警車的行駛方向相一致，且警車都走雙行道，即當(dāng)警車走到某個(gè)節(jié)點(diǎn)后，它們又同時(shí)返回初始停靠點(diǎn)，警車的行駛方向有四種方式，如6所示。在圖6中，數(shù)字1代表走巡邏走的第一步，2表示朝1的巡邏方向相反的方向巡邏。在具體程序?qū)崿F(xiàn)時(shí)，四種巡邏方向任意選擇，但是盡量保證所有的警車向同一個(gè)方向巡邏。圖6各警車巡邏方向圖我們用MATLAB編程對(duì)這種巡邏方式進(jìn)行計(jì)算，所得的車輛數(shù)目為18輛，綜合評(píng)價(jià)指標(biāo)為，其結(jié)果巡邏方案見(jiàn)附件中的“1193402-Result3.txt〞所示。在滿足問(wèn)題三的根底上討論D3條件，警車的巡邏方案和評(píng)價(jià)指標(biāo)巡邏的隱蔽性表達(dá)在警車的巡邏路線和時(shí)間沒(méi)有明顯的規(guī)律，主要目的是讓違法犯罪分子無(wú)可乘之機(jī)，防止他們?cè)诜茄策墪r(shí)間實(shí)施違法犯罪活動(dòng)