【正文】 十、參考文獻(xiàn)[1] Robert W. Floyd. Algorithm 97 (SHORTEST PATH). Communications of the ACM. 5(6):345, 1962.[2] Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 9(1):1112, 1962.[3] Lestor R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.[4] Jack Edmonds and Richard M. Karp. Theoretical improvements in the algorithmic efficiency for network flow problems. Journal of the ACM, 19:248164, 1972.[5] John E. Hopcroft and Richard M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225231, 1973.[6] 徐俊明，圖論及其應(yīng)用，合肥：中國科學(xué)技術(shù)大學(xué)出版社，2006。所以，圍堵的第二階段是從除去封鎖A區(qū)的13個平臺以外的67個平臺中找出與C、F區(qū)的9個路口的最佳匹配進(jìn)行封鎖?？勺羁熳ゲ兜阶锓?。對于D、E區(qū)而言，人均發(fā)案率較低，交巡警工作量不大，因此應(yīng)優(yōu)先考慮縮短出警時間提高執(zhí)法效率。如果增加平臺，在，時所得結(jié)論是只考慮優(yōu)化工作量的均衡，而最遠(yuǎn)距離不變。因此，B、C區(qū)不需要改變現(xiàn)有平臺數(shù)目。此外，在城市規(guī)劃中，市中心的資源配置同城市其他區(qū)域相比相對最好。 模型求解帶入所給數(shù)據(jù)，對現(xiàn)有交巡警服務(wù)平臺方案進(jìn)行分析，確定平臺增加數(shù)。 各區(qū)域工作量標(biāo)準(zhǔn)差和超距比例，A區(qū)的兩項評價指標(biāo)均遠(yuǎn)優(yōu)于其他五區(qū)?？梢钥闯?，權(quán)重u越大，使標(biāo)準(zhǔn)差盡量小這一原則得到的優(yōu)化越好?？筛鶕?jù)具體要求選擇不同方案。標(biāo)準(zhǔn)差體現(xiàn)了區(qū)域內(nèi)各平臺間工作量的差異大小。定義的變化率，的變化率 。u，v的大小可根據(jù)實際情況及具體需求確定。hj：定義平臺工作量hj指其平均每天需要處理的報警案件的總次數(shù)。 通過分析題目，平臺設(shè)置方案可以從交巡警服務(wù)平臺工作量的均衡性和出警時間長短兩個方面進(jìn)行評價?？蓪煞N不同對象處理成二分圖的結(jié)構(gòu)，平臺和路口的可達(dá)關(guān)系處理成圖中的邊集，一對一的封鎖關(guān)系即是二分圖的一個匹配，整個問題是一個典型的二分圖完美匹配問題。A區(qū)交巡警服務(wù)平臺管轄范圍分配方案1雖然給出了各平臺管轄范圍，保證所有節(jié)點都能被平臺支配，但平臺管轄范圍分布不均。所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個連通的賦權(quán)有向圖G(V,E,C)，其中V是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量集。定理2 設(shè)Di,j,k為從i到j(luò)的只以(1,2,…,k)集合中的節(jié)點為中間節(jié)點的最短路的長度。(4)符號說明：路口節(jié)點：交通網(wǎng)絡(luò)中任意兩點間最短路距離：最遠(yuǎn)距離：該節(jié)點平均每天的發(fā)生報警案件數(shù)量：人均發(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é)點上。確定評價指標(biāo)，對現(xiàn)有方案合理性進(jìn)行評價，通過計算比較確定需要增加平臺的具體個數(shù)和位置。(5)P（32號節(jié)點）處發(fā)生重大案件，案發(fā)3分鐘后接到報警，罪犯已逃跑。每個交巡警服務(wù)平臺的職能和警力配備基本相同，但警務(wù)資源有限。得出B、C區(qū)各需改變2個平臺的位置，新方案與現(xiàn)狀比較，表明新方案比現(xiàn)狀更合理。對問題一，首先以出警時間最短和出警次數(shù)盡量均衡為約束條件，利用無向圖上任意兩點最短路徑模型得到平臺管轄范圍，并運用上下界網(wǎng)絡(luò)流模型優(yōu)化解,得到A區(qū)平臺管轄范圍分配方案。發(fā)現(xiàn)有6個路口不能在3分鐘內(nèi)被任意平臺到達(dá)。D、E、F區(qū)分別需新增2個平臺。故需根據(jù)城市的實際情況與需求建立數(shù)學(xué)模型來合理設(shè)置交巡警服務(wù)平臺、分配各平臺的管轄范圍、調(diào)度警務(wù)資源。需用最短時間搜捕罪犯。三、模型假設(shè)(1)假設(shè)一個路口節(jié)點可以被多個交巡警服務(wù)平臺管轄管轄。因為平臺與節(jié)點之間可能有多種到達(dá)方式，所以該網(wǎng)絡(luò)是一個加權(quán)無向圖。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。此外頂點集中包括一個源點和一個匯點。有些平臺如AA5轄區(qū)內(nèi)節(jié)點數(shù)量密集，一個平臺卻要負(fù)責(zé)十幾個路口；而有些平臺如AA12只負(fù)責(zé)一兩個節(jié)點，造成警務(wù)資源浪費。我們使用二分逼近技術(shù)配合二分圖完美匹配的相關(guān)模型求解上述問題。交巡警服務(wù)平臺工作量的均衡性體現(xiàn)為區(qū)域內(nèi)各平臺間出警次數(shù)差異的大小，可用其標(biāo)準(zhǔn)差來衡量。若第j個平臺轄區(qū)內(nèi)共有n個節(jié)點，則其工作量。u越大越側(cè)重于均衡平臺的工作量；v越大越側(cè)重于縮短出警時間。由于與的變化率不同，若直接引入?yún)?shù)，會出現(xiàn)較大誤差。 不同權(quán)重時，增加平臺的方案通過對所有