【正文】 ：人均發(fā)案率：節(jié)點(diǎn)等效的平均每天發(fā)生報(bào)警案件數(shù)量：區(qū)域平臺出警次數(shù)標(biāo)準(zhǔn)差：1個(gè)平臺最多只能管轄個(gè)路口節(jié)點(diǎn)：平臺工作量影響力的權(quán)重：一個(gè)節(jié)點(diǎn)最多可被ki個(gè)平臺管轄：出警時(shí)間影響力的權(quán)重：交巡警服務(wù)平臺的出警次數(shù)（工作量）五、問題一 平臺管轄范圍的確定 建模分析將所有路口看作節(jié)點(diǎn)vi（i=1,2，……，92），已知平臺Aj（j=1,2，……，20）也位于節(jié)點(diǎn)上。因?yàn)槠脚_與節(jié)點(diǎn)之間可能有多種到達(dá)方式，所以該網(wǎng)絡(luò)是一個(gè)加權(quán)無向圖。交巡警要在3分鐘內(nèi)以時(shí)速為60km/h到達(dá)事發(fā)地，則平臺距事發(fā)地的最短路應(yīng)不大于3000米。此外，在分配平臺管轄范圍時(shí)，也應(yīng)考慮到平臺出警次數(shù)的均衡性。 基于無向圖上任意兩點(diǎn)最短路模型的初始方案為了討論方便，先引入圖論中的相關(guān)定義：定義1 無向圖中，任意兩點(diǎn)路徑為保持兩點(diǎn)連通性的點(diǎn)集，兩點(diǎn)間路徑不是唯一的。定義2 路徑的權(quán)值為路徑上點(diǎn)權(quán)之和，最短路徑為加權(quán)最小的路徑。定義3 設(shè)G(V1,V2,E)是一個(gè)二分圖，M是E的一個(gè)子集，如果M不含環(huán)且任意兩邊都不相鄰，則稱M為G的一個(gè)匹配。在最短路理論中有以下定理：定理1 最短路徑的子路徑是最短路徑，最短路具有最優(yōu)結(jié)構(gòu)，可使用動態(tài)規(guī)劃解決。定理2 設(shè)Di,j,k為從i到j(luò)的只以(1,2,…,k)集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路的長度。1) 若最短路徑經(jīng)過點(diǎn)k，則Di,j,k = Di,k,k ? 1 + Dk,j,k ? 1；2) 若最短路徑不經(jīng)過點(diǎn)k，則Di,j,k = Di,j,k ? 1。因此，Di,j,k = min(Di,k,k ? 1 + Dk,j,k ? 1,Di,j,k ? 1)。FloydWarshall算法就是基于以上定理的一類動態(tài)規(guī)劃算法[1]。輸入無向圖的初始鄰接矩陣，使用它可以得到圖上任意兩點(diǎn)的最短路長度。首先，我們?yōu)槠脚_管轄制定下述規(guī)則：1)在交巡警轄區(qū)范圍內(nèi)，；2)節(jié)點(diǎn)發(fā)案時(shí)首先呼叫最近平臺，若最近平臺忙，則呼叫第二近的平臺，以此類推；3)若節(jié)點(diǎn)與任意平臺的距離均滿足，強(qiáng)制該點(diǎn)被距離最近的平臺管轄；4)當(dāng)Ci≥2，ki=3，優(yōu)先被最近的平臺管轄；5)當(dāng)1≤Ci2，ki=2，優(yōu)先被最近的平臺管轄；6)當(dāng)Ci1，ki=1, 只被最近平臺管轄。利用原始數(shù)據(jù)，可得初始化鄰接矩陣，使用FloydWarshall算法，得到任意兩點(diǎn)間最短路，結(jié)合規(guī)則1) ~6)可得平臺管轄范圍分配方案。 基于上下界網(wǎng)絡(luò)流模型的優(yōu)化方案上下界網(wǎng)絡(luò)流[4]是圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類最優(yōu)化問題。所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個(gè)連通的賦權(quán)有向圖G(V,E,C)，其中V是該圖的頂點(diǎn)集，E是有向邊(即弧)集，C是弧上的容量集。此外頂點(diǎn)集中包括一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)。網(wǎng)絡(luò)上的流就是由源點(diǎn)流向匯點(diǎn)的可行流，這是定義在網(wǎng)絡(luò)上的非負(fù)函數(shù)，它一方面受到容量的限制，另一方面除去源點(diǎn)和匯點(diǎn)以外，在所有中途點(diǎn)要求保持流入量和流出量平衡。我們假設(shè)一個(gè)平臺最多管轄Q個(gè)節(jié)點(diǎn)，并利用上下界網(wǎng)絡(luò)流中的容量限制來模擬平臺和路口的約束，從而得到一個(gè)較為平衡的解。算法1① 構(gòu)建二分圖；② 定義左集合代表A區(qū)所有路口節(jié)點(diǎn)，；③ 定義右集合代表A區(qū)所有交巡警服務(wù)平臺，；④ 設(shè)置源點(diǎn)S，向各點(diǎn)連接成邊，邊容量 ；⑤ 設(shè)置匯點(diǎn)T，從各點(diǎn)向T連接成邊， ，；⑥ 從各點(diǎn)向各自滿足的點(diǎn)連邊，=1 ；⑦ 用二分法枚舉Q值，判斷是否滿足在使用上下界網(wǎng)絡(luò)流算法后，各必要弧滿流（所有路口節(jié)點(diǎn)均被管轄）；⑧ 重復(fù)以上二分步驟逼近滿足條件的最小Q值。 結(jié)果及其分析與評價(jià)利用題設(shè)數(shù)據(jù)，使用FloydWarshall算法，，可得優(yōu)化的管轄范圍分配方案。在兩點(diǎn)間最短路基礎(chǔ)上，得平臺管轄范圍的初始分配方案1；再使用上下界網(wǎng)絡(luò)流算法得到各交巡警服務(wù)平臺管轄范圍優(yōu)化分配方案2， 。 A區(qū)交巡警服務(wù)平臺管轄范圍分配方案從方案1可見，共有六個(gè)問題節(jié)點(diǎn)28,29,38,39,61,92與任何平臺的最短路均大于3000米。A區(qū)交巡警服務(wù)平臺管轄范圍分配方案1雖然給出了各平臺管轄范圍，保證所有節(jié)點(diǎn)都能被平臺支配，但平臺管轄范圍分布不均。有些平臺如AA5轄區(qū)內(nèi)節(jié)點(diǎn)數(shù)量密集，一個(gè)平臺卻要負(fù)責(zé)十幾個(gè)路口；而有些平臺如AA12只負(fù)責(zé)一兩個(gè)節(jié)點(diǎn)，造成警務(wù)資源浪費(fèi)?？梢姶朔桨鸽m可行，但仍有不合理之處，故需要優(yōu)化。平臺管轄范圍優(yōu)化分配方案2中，給出了每個(gè)平臺管轄范圍?？梢悦黠@看出與方案1相比，方案2中各平臺轄區(qū)大小的分布更均勻，其中65%的平臺轄區(qū)內(nèi)路口數(shù)目均為6—7個(gè)，另外方案1中只負(fù)責(zé)一兩個(gè)路口的AA12等平臺轄區(qū)內(nèi)路口數(shù)目也有所適量增加，大大減少了平臺管轄范圍分配不均衡的現(xiàn)象。共有86個(gè)路口在3分鐘中內(nèi)能被交巡警到達(dá)，但28，29，38，39，61，92號這6個(gè)路口不能在3分鐘內(nèi)被任意平臺到達(dá)。 。 離最近平臺距離超過3千米的節(jié)點(diǎn)情況六、問題一 交巡警調(diào)度方案的確定 建模分析本題的目標(biāo)函數(shù)為從現(xiàn)有20個(gè)交巡警服務(wù)平臺中優(yōu)選出封鎖13個(gè)進(jìn)出該區(qū)路口的方案?？蓪煞N不同對象處理成二分圖的結(jié)構(gòu)，平臺和路口的可達(dá)關(guān)系處理成圖中的邊集，一對一的封鎖關(guān)系即是二分圖的一個(gè)匹配，整個(gè)問題是一個(gè)典型的二分圖完美匹配問題。我們使用二分逼近技術(shù)配合二分圖完美匹配的相關(guān)模型求解上述問題。 基于二分圖完美匹配模型的調(diào)度方案的確定求一個(gè)二分圖的完美匹配的普遍算法是Hungary最大匹配算法[5]，我們可以通過枚舉最遠(yuǎn)距離L后驗(yàn)證，從而將一個(gè)求解性問題轉(zhuǎn)化為判定性問題，簡化了問題的求解過程。