110警車上街巡邏，不僅可以震懾犯罪分子，降低犯罪率，還可以增加市民的安全感。同時也加快了接警時間，提高了反應時間，為社會和諧提供了有力保障。
現在，給定壹個城市中某個區域的道路數據和地圖數據，這個區域中三個關鍵部分的坐標分別為(5112，4806)、(9126，4266)和(7434，1332)。這個地區有307個路口。為了簡化問題，將兩個相鄰交叉口之間的道路近似認為是壹條直線，所有事故地點都在下面的道路上。
全市計劃新增壹批配備GPS衛星定位系統和先進通信設備的110警車。假設110警車平均巡邏速度為20km/h，接警後平均行駛速度為40km/h..警車配置和巡邏方案應盡可能滿足以下要求:
D1。接警後三分鐘內到達現場的警車比例不低於90%；而且到達關鍵部位的時間必須在兩分鐘之內。
D2。使巡視效果更加顯著；
D3。警車的巡邏規則應該是隱蔽的。
現在我們需要解決以下問題:
1.如果需要D1，需要部署多少輛警車在該區域巡邏？
2.請給出相關指標評價巡視效果的顯著程度。
3.請給出滿足D1並盡可能滿足D2條件的警車巡邏方案及其評價指標值。
4.在第三個問題的基礎上，考慮D3條件，給出妳的警車巡邏方案及其評估指標值。
5.如果這個區域只有10輛警車，應該如何制定壹個盡可能滿足d1和D2的巡邏方案？
6.如果接到報警後警車平均速度提高到50km/h，回答問題3。
7.妳認為還有哪些因素和情況需要考慮？給出妳相應的解決方法。
雙問題分析
本課題是關於城市道路網中警車的配置和巡邏。在配置警車時，首先要考慮接警後在規定時間內到達現場的警車比例。在這種條件下，我們應該以最小的車數為目標來建模和求解問題。制定巡邏計劃時，要考慮巡邏的效果和隱蔽性。
第壹個問題只需要D1和最少的警車數量。可以認為警車是靜止的，三兩分鐘能到達的區域就是它的覆蓋範圍。相應地，在所有街道的覆蓋率不小於90%的條件下找到最優解。
問題二:評價巡邏效果，需要考慮兩個方面:壹是巡邏的全面性，即壹段時間後警車經過的街道數占總街道數的比例；二是巡邏的不均勻性，即壹段時間後，每條街經過的警車數量相差不大，用方差來衡量。
第三個問題是在滿足D1的條件下，盡可能滿足第二個問題給出的指標，並給出評價方案的指標。先找到壹組滿足D1的警車位置，然後在與警車位置相連的點中隨機找壹個點，判斷新點是否滿足D1。如果滿足D1，警車就開到這個點，否則再次搜索，直到滿足為止。壹段時間後，統計所有車通過的點數和每個點通過的次數，用問題2給出的兩個指標進行評價。結合這兩個指標，就可以判斷這條路徑的好壞，重復這個過程，直到綜合評價指標達到滿意值。
第四題增加了隱蔽要求。首先給出了評價隱蔽性的指標，可以用路線的隨機性來評價，並將其加入到第三個問題的模型中求解。
問題5限制警車數量為10。要綜合考慮D1和D2。首先分配這10輛車，使道路覆蓋率最高，然後按照問題3的步驟解決問題，其中每壹步只需要使道路覆蓋率盡可能高即可。
問題6和問題3壹樣，只是把速度改成50 km/h。
三種模式假說
1.警車在路上巡邏，不考慮巡警辦案的時間；
2.所有案發現場都在路上，案件發生在路上任意壹點的概率相等；
3.警車的初始停靠點是隨機的，但盡量做到分散，壹輛警車管轄壹個分區；
4.假設在每個劃分的區域內，短時間內最多發生壹例；
5.假設區域內的每條路都是雙行道，不考慮轉彎對結果的影響；
6.如果關鍵部位不在路上，假設這些關鍵部位在最近的路上；
7.圖中的水域對巡邏計劃沒有影響。
四符號描述
指示警車的數量
表示從警車的初始停靠點到每條道路的最短距離。
表示整個區域的總道路長度。
指示3分鐘內無法到達的區域的道路長度。
表示非重點部位警車不能在3分鐘內到達現場的比例。
這意味著三分鐘內從報警位置到事件現場的最大距離是
表示整個區域中離散點的總數。
表示區域中的節點數。
表示區域中的調整功能。
代表模擬退火時間，代表溫度值。
表示區間調整函數
指示綜合指數
指示不均勻性指數
代表壹個綜合評價指標
表示第壹輛車通過每條道路的次數。
代表每條道路穿過整個區域的平均次數。
五種模型的建立及算法設計
5.1當滿足D1時，該區域所需的最小警車數量和巡邏方案。
當5.1.1滿足D1的條件時，該地區警車最少的規律。
當題目要求警車配置和巡邏方案滿足D1的要求時，整個區域所需警車數量最少。假設警車都在路上，所有事故現場也都在路上，但是區域內的道路總長度是壹個恒定值；警車接警後到達案發現場有時間限制和概率限制:普通區域三分鐘內到達案發現場的比例不低於90%，到達重點部位的時間必須控制在兩分鐘內。由此可見，每輛警車的管轄範圍不會很大，所以我們考慮將整個區域劃分為若幹個分區，每輛警車管轄壹個分區。
從上面的分析來看，解決整個區域的警車數量最少的問題，可以轉化為解決每輛警車能夠管理盡可能大的壹條街道的問題。所以我們尋找規則，每輛警車應該有盡可能大的管轄權。為了簡化問題，不考慮90%概率到達現場的限制，只對警車三分鐘內能到達現場的情況進行定性分析。分析示意圖如圖1所示。警車的初始停放位置隨機分布在道路上的任意壹個節點。讓我們假設壹輛警車停在A點..
圖1警車轄區分析示意圖
由於壹輛警車的平均巡邏速度為20km/h，接警後的平均行駛速度為40km/h，由於距離信息容易獲取，我們將時間限制改為距離限制，便於分析和求解。警車接警時，三分鐘內從接警位置到事發現場的最大距離為，其中。
如圖1，我們假設警車的初始停放位置在A點，是1，2，3，4路的交叉口。我們僅以1路上巡邏的警車為例進行分析。警車在道路1上巡邏，速度在A和點之間，距離初始停靠點A的距離為。因為案件可能發生在道路上的任何壹點，當警車巡邏到A點時，如果案發現場發生在2、3、4路，警車會以40km/h的速度行駛到現場，警車在三分鐘內從A點到達現場的最大距離是。如果警車繼續在1道路上向前行駛，警車三分鐘內能到達現場的距離會繼續縮小。警車從初始點行駛到A點但未到達該點時，警車的最大管轄範圍大於警車到達該點時。為了讓警車的管轄範圍盡可能大，巡邏範圍越小越好。當警車在初始停靠點靜止時，警車的管轄範圍達到最大。
圖1的分析是特例，道路1，2，3，4是對稱分布的。現在讓我們分析壹下壹般情況，如圖2所示。
圖2.1圖2.2
圖2警車最大權限分析示意圖。
圖2.1所示的情況是道路分布不對稱。與圖1相比，圖2.1所示道路的方向和角度發生了變化，圖2.3的情況更加復雜。參考圖1的分析方法，分析這兩種情況下警車巡邏時三分鐘內能到達現場的最大距離的規律。我們只分析圖2.2的情況，1、2、3、4、5路在C點相交，1路和6路之間還有壹個道路交叉口D，因為巡邏時警車在道路上行駛。不影響路徑的長短，所以當警車巡邏到距離初始停靠點C較遠的D點時，如果此時有案件發生，警車應在三分鐘內到達現場處理案件，最大行駛距離在。如果警車繼續在1道路上向前行駛，警車在三分鐘內能夠到達現場的距離會繼續縮小。警車不開到D時，此時警車最大管轄比大。當警車靜止時，警車的管轄範圍可以達到最大。
以上分析只是定性分析，三個關鍵部分也可以同樣分析，結論是壹致的。以上分析不考慮90%的到達概率限制，但需要在設計算法中充分考慮。
綜上所述，當警車在初始停靠點靜止不動時，在三分鐘的時限內，警車從初始停靠點能到達現場的最大距離為。
5.1.2離散化道路
因為事發現場分布在等概率的道路上，所以從區域地圖上可以發現，整個區域的道路長度是不均勻的。為了使計算結果更加準確，可以將這些道路離散化。只要選擇合適的離散方案，警車在通過道路上的離散點時就可以通過道路。這樣，在求解警車初始停靠點或警車到達發現現場的道路時，計算結果顯然比只考慮整條道路的交叉口要準確得多。
該地區有307個道路交叉口和458條道路。我們采用線性插值的方法對道路進行離散化，以步行壹分鐘的距離為步長。壹分鐘時間的選擇參照問題3的結果要求設定。采用線性插值的方法，從道路的壹個方向進行線性插值，實現每條道路離散化的目的。考慮到有些路不是的整數倍，我們將討論壹般情況，分析圖如圖3所示。道路的長度AB是長度的總和。為了更準確地處理CB道路，需要考慮是否在CB之間插入新的點。根據長度的不同，相應的處理方法也不同。
圖3道路離散化分析示意圖
引入臨界指標，選擇大小的準則是使警車的等效平均巡邏速度與給定速度()之差盡可能小。經過計算，在不插入新坐標點的情況下，整個區域的道路分散效果可以更好。此時CB段的長度設置為processing，所以離散化後AB路的長度會比實際長度短；必要時，需要在兩點之間插入另壹點，因為這種處理可以使整個區域內整條道路的離散化效果比較理想。如圖3所示，在C和B之間插入壹個新的坐標點，插入位置在從C點開始的D點，這樣處理後的道路長度比實際長度長。利用這種方法進行線性插值，用MATLAB編程對整個區域的道路進行離散化。離散化結果如圖4所示。離散化後，得到762個節點，比原始數據多455個。離散化節點數據見附件“newpoint.txt”。
圖4全區離散結果圖
用這種插值方法將道路離散化後，將直線上的無窮多個點轉化為有限個點，便於分析問題和實現相應的算法。從圖4可以看出，整體的離散化效果還是比較理想的。
5.1.3按地區求解警車數量的算法設計
考慮到警車配置和巡邏方案需要滿足接警後三分鐘內到達普通部位案發現場的警車比例不低於90%，到達重點部位必須控制在兩分鐘以內的要求。設計算法的目標是在滿足D1的條件下，找出警車總數最小，即每個區域覆蓋盡可能多的道路節點。由於警車的初始位置未知，我們可以將警車的初始停止點設置在道路上的任意壹點，即圖4所示的762個離散點的某些節點上。總體思路是每兩輛車盡量分散分布，壹輛警車管轄壹個分區，用這些分區覆蓋整個區域。
於是我們設計了算法1，步驟如下:
Step1:將整個區域預分配成區，每個區分配壹輛警車。警車的初始停放位置設置在預分配區中心的道路節點上。如果區域的中心不在道路節點上，則警車被放置在離中心最近的道路節點上。
第二步:統計分區無法覆蓋的節點，調整警車的初始停靠點，使分區覆蓋盡可能多的道路節點。調整分為兩種方案:(1)調整分區內按照模擬退火思想構造的函數，調整區間內車輛初始點的位置(後面詳細描述)。當分區中節點較多時，調整的概率較小，當分區中節點較少時，調整的概率較小。(2)當區域內有未覆蓋的節點或節點群(壹個範圍內集中了三個或三個以上的節點)時，調整警車的初始位置，按照壹定的規則向這些未覆蓋的節點移動(詳細在算法描述中)，同時保證三個關鍵部位在2分鐘內能夠達到100%；
步驟3:利用Floyd算法計算警車初始停靠點與周圍道路節點的最短距離；
第四步:用每個劃分區域未覆蓋的道路總長度與整個區域的道路總長度的比值來表示警車不能在3分鐘內到達現場的概率；
第五步:模擬足夠的次數，如果是，從車輛數中減去1，跳轉到第1步；
第六步:計算結束後，比較當時對應的數值，當得到最小值時，記錄此時的區域劃分方案，即最少的警車數量。
算法的壹些解釋:
(1)該算法取的車輛數從最多到最少計算，初始值設為20。這個值的選擇是根據面積圖估計的。
(2)預分區的好處是警車的初始位置盡可能均勻分布，警車的初始停車點可以在壹個分區的中心附近找到，相比在整個區域內隨機生成停車點，明顯提高了計算效率。
預分配後，整個區域需要不斷調整，調整時需要考慮調整方向和調整概率。
警車調試借鑒了模擬退火算法的方法。為了使初始停車點調整在道路節點較多的分區中的概率較小，而初始停車點調整在道路節點較少的分區中的概率較大，我們構造了壹個調整概率函數。
(1)
在公式(1)中，都是常數，分別是整個區域的車輛數，第壹個分區覆蓋的節點數，時間。同時，它們也可以代表模擬退火的溫度變化:初始溫度越高，區域調整速度越快。隨著時間的增加，氣溫不斷降低，區域調整速度逐漸減緩，這也更符合實際情況。
調整概率函數可以從等式(1)獲得。假設同壹溫度(時間)下車輛總數不變，當第壹分區的節點數大於第壹分區的節點數時，分區的調整概率較大，分區的調整概率較小。分析其原因:當分區內節點較多時，警車在分區內的初始停放位置較為合適，而當分區內道路節點較少時，說明警車的初始停放位置未被選擇，需要以較大概率進行調整，這也是客觀存在的。
對於所有未覆蓋的道路節點和分區外的許多節點(稱為節點組)，用於調整警車位置遷移的方向，其分析示意圖如圖5所示。調整方案的目標是使未覆蓋節點的數量盡可能少。在設計調整方向函數時，需要考慮:(1)節點組中的節點數；(2)節點群中警車的位置。距離是優先的，所以在公式(2)中，調整方向函數用距離的平方來描述。
因為某個區域的未覆蓋節點數、整個區域的未覆蓋節點總數、子區域與未覆蓋節點或節點組的距離都會影響調整方案，這些因素都要綜合考慮。因此設計了間隔調整功能，
其中，表示第壹分區中未覆蓋節點的數量、第壹分區與未覆蓋節點或節點組之間的距離以及未覆蓋節點和節點組的數量。
現在我們根據區間調節函數簡單分析壹下第壹個分區的調節方案。當某個兩節點組中的節點數相等，但距離不相等時，例如根據間隔調整公式，將間隔調整到節點組方向。當壹個分區與兩個節點組之間的距離相等，但節點組中的節點數量不相等時，如果是這樣，則從(4)中可以知道，該分區將想要調整節點組的方向。
註意在整個調整過程中是否控制調整概率，調整方向函數控制調整方向，尋找在此調整方案下的最佳結果。
圖5調整子區域示意圖
(3)在步驟3中，利用Floyd算法計算警車初始停靠點與周圍節點的最短距離，使該區域發生事情時，警車能夠在要求的時限內到達現場。
(4)為了尋找更好的警車停放點，采用模擬退火算法計算局部最優方案。
5.1.4警車配置及巡邏方案
用MATLAB編程實現算法1，整個區域配備13輛警車，在初始停靠點靜止時能滿足D1的要求。警車初始停放位置分別為道路交叉口節點6、25、30、37、82、84、110、11、126、214、253、226。各警車管轄的路口(原路口節點)如圖6所示，分割結果見附錄。
圖6d 1條件下的區分圖。
13分區* * *覆蓋252個路口，另外55個原路口不在這些分區覆蓋範圍內:137，151，159，167，65438。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。在此分區方案下，在這些點中，每兩個相連點之間的道路離散值長度與整個區域總長度的比率為。因此，整個區域有13輛警車，每輛警車在初始停靠點都是靜止的。當案件發生時，離犯罪現場最近的警車從最初的停靠點到達現場。
5.2評估顯著巡視效果的指標
110警車上街巡邏的目的是震懾犯罪分子，降低犯罪率，增加市民的安全感。同時也加快了接警時間(接受報警並趕赴現場處理事件)，提高了反應時間，為社會和諧提供了有力保障。巡警在城市繁華街道和公共場所執行巡邏任務，維護公共秩序，服務群眾，可以取得良好的社會效果[1]。
在整個區域內，因為案發現場在馬路上，所以馬路上的每壹點都是等概率發生的。所以，警車巡邏的範圍越廣，巡邏的街道越多，警車的巡邏效果就越好，對犯罪分子就越有威懾力，警車就能更及時地處理案件。
我們用全面性來衡量巡邏的有效性，即警車巡邏的街道節點數與區域內節點總數的比值。當警車反復通過同壹街道、同壹離散點時，只記錄壹次。
(3)
式中，表示警車所經過的離散點，代表整個區域內的離散點總數。數值越大，警車經過的街道越多，效果越顯著。
同時考慮到在巡邏過程中可能會出現這樣的情況:在同壹時間段內，警車會對壹些街道進行多次巡邏，而壹些街道很少巡邏，甚至沒有警車到達，會造成壹些巡邏盲區。分布很不均勻。這樣，巡邏密度高的街道上的犯罪分子可能不敢在街道上作案，而逃到巡邏密度稀疏的街道上。因此，在警車數量相同的情況下，不均衡巡邏模式的巡邏效果更差，而更均衡巡邏模式的巡邏效果會更好。我們引入了巡視不均勻性來衡量巡視效果的顯著性。考慮到方差可以代表不平衡的程度，我們用方差的大小來表示不平衡。方差越大，巡視密度越不平衡，巡視效果越差。
(4)
問題1顯示符合D1條件的警車數量為13。此時，每輛警車仍在初始停靠點，只有轄區內發生案件時，警車才會從初始停靠點趕往案發現場辦案。警車在巡邏時，需要考慮的問題比較復雜，比如節點在移動時警車能否滿足D1的要求，警車如何移動，但基本的算法思想與問題1類似，得到的算法2的框圖如圖7所示。
為了簡化問題，我們假設各分區的警車在巡邏時，盡量保證所有警車的行駛方向壹致，所有警車都走雙向路，即當警車行駛到某個節點時，同時返回初始停靠點。警車有四個行駛方向，如圖6所示。
在圖6中，數字1代表巡邏的第壹步，2代表巡邏的方向與1相反。具體方案實施時，四個巡邏方向任意選擇，但保證所有警車盡可能同向巡邏。
圖6警車巡邏方向
我們用MATLAB編程計算這種巡邏模式，得到的車輛數為18，綜合評價指數為0。結果的巡視方案見附件“1193402-result 3 . txt”。
5.4在滿足第三個問題的基礎上，討論D3條件、警車巡邏方案和評價指標。
巡邏的隱蔽性體現在警車的巡邏路線和時間沒有明顯的規律性。主要目的是不給犯罪分子可乘之機，防止他們在非巡邏時間實施違法犯罪活動，危害人民生命財產安全。
為了使巡邏的規律隱藏起來，警車在巡邏時至少要有兩條不同的路線，最佳時間也不壹樣。所以考慮到隱蔽性，我們只需要在問題2的基礎上增加壹個隨機過程。至於其評價指標，由於警車有多條可選巡邏路線，當同壹條路線同時重復出現時，將再次執行設定的方案。我們用這個時間間隔來衡量隱蔽程度。當循環周期越長，說明可選的巡視方案越多，其規律越隱蔽。循環周期越小，說明巡視方案越少，隱蔽性越差。在巡邏狀態下，最差的隱蔽巡邏方案是只有壹個巡邏方案，時間固定。這樣的巡邏方案壹點隱蔽性都沒有。
5.5全區域10車輛時的巡邏方案。
根據第三個問題的結果，10的車輛數並不能完全覆蓋整個區域，其算法與算法2類似，只是此時車輛數已經固定，要求盡可能滿足D1和D2。我們得到的評價指標值為，巡視方案見附件“1193402-”
5.6平均行駛速度提高時的巡視方式及評價指標值。
問題6的分析方法和具體實現與問題3壹致，但接警後的警車平均速度比原來有所提高，因此各分區的覆蓋範圍也有所增加。將數值帶入問題3的算法中求解，計算出的指標值為，其巡視方案見附件“1193402-result 6 . txt”。
圖7算法2的框圖
六種模型的分析與評價
在解決滿足D1的條件下，整個區域需要多少警車的問題上，采用分區巡邏的思想，先分析各區管轄範圍何時能達到最大值的規律，由特殊到壹般逐層進行分析。邏輯嚴密，結果合理。
在求解區域和警車數量時，在初步設定警車停靠位置的基礎上，基於模擬退火算法的思想構造函數確定調整概率，在綜合考慮影響區間調整的因素後構造函數確定分區的調整方向。根據這兩個調整函數調整分區時，每個分區可以管轄盡可能多的道路節點，結果令人滿意。
參加考試，貢獻力量
[1]中小城市警察巡邏勤務模式探討，翔宇，江蘇公安學院學報，1998，第1期。
[2]Matlab7.0從入門到精通，科技求是，人民郵電出版社；
[3]車輛數不確定的隨機車輛路徑問題的模型與算法，雲等，工業工程，第10卷，第3期，2005年5月；
[4]隨機交通分配中有效路徑的確定方法，李誌春等，交通系統工程與信息技術學報，第3卷，第1期，2003年2月。