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