到4個額外因素，給出每個影響因素的解決方案。

關鍵詞：模擬退火算法；floyd算法；離散化

論文內容：一 問題的重述

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

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

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

d1 警車在接警后叁分鐘內趕到現場的比例不低于90％；而趕到重點部位的時間必須在兩分鐘之內。

d2 使巡邏效果更顯著；

d3 警車巡邏規律應有一定的隱蔽性。

現在我們需要解決以下幾個問題：

一 假設要求滿足d1,該區最少需要配置多少輛警車巡邏？

二 請給出評價巡邏效果顯著程度的有關指標。

叁．請給出滿足d1且盡量滿足d2條件的警車巡邏方案及其評價指標值。

四 在第叁問的根底上，再考慮d3條件，給出你們的警車巡邏方案及其評價指標值。

五．如果該區域僅配置10輛警車，應如何制定巡邏方案，使d1、d2盡量得到滿足？

六 假設警車接警后的平均行駛速度提高到50k/h，答復下列問題叁。

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

二 問題分析

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

問題一只要求滿足d1，求最少的警車配置數，可以認為警車是不動的，在叁分鐘或兩分鐘內它能到達的區域就是它的覆蓋范圍。據此，在滿足所有街道的覆蓋率不低于90的條件下，尋找最優解。

問題二要評價巡邏效果，有兩個方面需要考慮：一是巡邏的全面性，即經過一段時間后警車走過的街道數占總街道數的比例；二是巡邏的不均勻性，即經過一段時間后警車經過每一條街道的次數相差不大，用方差來衡量。

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

問題四增加了隱蔽性要求，首先給出評價隱蔽性的指標，隱蔽性可用路線的隨機性來評價，將它參加到問題叁的模型中去進行求解。

問題五限制警車數量為10，要綜合考慮d1、d2，先分配這10輛車使道路的覆蓋率最高，然后按照問題叁的步驟進行求解，其中每一步對d1的判斷只需使道路的覆蓋率盡量高即可。

問題六同問題叁，只需將車速改為50k/h即可。

叁 模型的假設

警車都在路上巡邏，巡警去處理案件的時間不考慮；

所有事發現場都在道路上，案件在道路上任一點是等概率發生的；

警車初始停靠點是隨機的，但盡量讓它們分散分布，一輛警車管轄一個分區；

假定各個劃分區域內，較短時間內，最多會發生一個案件；

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

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

7 圖中水域對巡邏方案沒有影響。

四 符號說明

表示警車數目

d 表示警車初始停靠點到各道路的最短距離

l 表示整個區域的總道路長度

l 表示不能在3分鐘內到達的區域的道路的長度

k 表示非重點部位的警車在3分鐘內不能到達現場的比例

s 表示叁分鐘內能從接警位置趕到事發現場的最大距離是

n 表示整個區域