。計算能滿(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)，否那么重新尋找，直到