【文章內(nèi)容簡介】 算法2① 建二分圖；② 定義左集合代表出入A區(qū)的所有路口， ；③ 定義右集合代表A區(qū)所有交巡警服務(wù)平臺(tái)，；④ 二分法枚舉出節(jié)點(diǎn)與平臺(tái)匹配的最遠(yuǎn)距離L，然后將和中最短路距離Dij≤L的點(diǎn)對(duì)連邊，使用Hungary最大匹配算法判斷是否能夠得到左集合的完美匹配；⑤ 重復(fù)以上二分步驟逼近滿足條件的最小L值。 結(jié)果及其分析與評(píng)價(jià)利用二分圖的完美匹配模型，得出A區(qū)20個(gè)平臺(tái)封鎖13個(gè)路口的最佳調(diào)度方案，即每個(gè)平臺(tái)應(yīng)該負(fù)責(zé)封鎖的路口，路程距離和出警時(shí)間。 ： A區(qū)20個(gè)平臺(tái)封鎖13個(gè)路口的調(diào)度方案，在13條封鎖路徑中。七、問題一 平臺(tái)設(shè)置調(diào)整方案的確定 建模分析在A區(qū)增加2至5個(gè)平臺(tái)，建立模型求解平臺(tái)增數(shù)和位置。首先制定評(píng)價(jià)指標(biāo)對(duì)現(xiàn)有平臺(tái)設(shè)置方案進(jìn)行評(píng)價(jià)，分析比較新方案與現(xiàn)有方案的優(yōu)劣。 通過分析題目，平臺(tái)設(shè)置方案可以從交巡警服務(wù)平臺(tái)工作量的均衡性和出警時(shí)間長短兩個(gè)方面進(jìn)行評(píng)價(jià)。交巡警服務(wù)平臺(tái)工作量的均衡性體現(xiàn)為區(qū)域內(nèi)各平臺(tái)間出警次數(shù)差異的大小，可用其標(biāo)準(zhǔn)差來衡量。已知交巡警時(shí)速為60km/h，則出警時(shí)間可用平臺(tái)與路口節(jié)點(diǎn)的最短路距離來衡量。平臺(tái)與節(jié)點(diǎn)間的最短路應(yīng)盡量在3000米以內(nèi)。建立基于不同權(quán)重的平臺(tái)調(diào)整評(píng)價(jià)模型，求解對(duì)應(yīng)平臺(tái)增數(shù)的所增平臺(tái)位置，得出結(jié)論。 指標(biāo)體系Dmax：某區(qū)域共有n個(gè)節(jié)點(diǎn)，則轄區(qū)內(nèi)從各個(gè)平臺(tái)出發(fā)到達(dá)各個(gè)節(jié)點(diǎn)共有n條最短路。定義這n條最短路中距離最長的為該區(qū)最遠(yuǎn)距離Dmax，對(duì)應(yīng)最長出警時(shí)間。：第i號(hào)節(jié)點(diǎn)可被ki個(gè)平臺(tái)管轄，定義該節(jié)點(diǎn)的等效發(fā)案率。hj：定義平臺(tái)工作量hj指其平均每天需要處理的報(bào)警案件的總次數(shù)。若第j個(gè)平臺(tái)轄區(qū)內(nèi)共有n個(gè)節(jié)點(diǎn)，則其工作量。：定義平臺(tái)工作量的標(biāo)準(zhǔn)差 。其中，為工作量的平均值。下面給出增加不同平臺(tái)數(shù)時(shí)的可行方案，算法規(guī)則：（1）節(jié)點(diǎn)與平臺(tái)間的距離Dij應(yīng)盡量在3000m以內(nèi)；（2）當(dāng)節(jié)點(diǎn)發(fā)案率C≥2，至少被最近的2個(gè)平臺(tái)管轄；（3）當(dāng)節(jié)點(diǎn)發(fā)案率C2，至少被最近的1個(gè)平臺(tái)管轄。利用此規(guī)則，分別計(jì)算出增加n（n=2,3,4,5）個(gè)平臺(tái)后的標(biāo)準(zhǔn)差和最遠(yuǎn)距離， 。 基于枚舉算法的增加平臺(tái)方案 基于不同權(quán)重的平臺(tái)調(diào)整評(píng)價(jià)模型(1)權(quán)重參數(shù)定義平臺(tái)工作量均衡性影響力的權(quán)重為u，用出警次數(shù)標(biāo)準(zhǔn)差衡量；出警時(shí)間影響力的權(quán)重為v，用平臺(tái)到節(jié)點(diǎn)的最短路距離衡量。；且。u，v的大小可根據(jù)實(shí)際情況及具體需求確定。u越大越側(cè)重于均衡平臺(tái)的工作量；v越大越側(cè)重于縮短出警時(shí)間。通過調(diào)整這兩個(gè)權(quán)值來調(diào)整平臺(tái)工作量均衡性、出警時(shí)間長短對(duì)平臺(tái)設(shè)置的相對(duì)影響程度，反映評(píng)價(jià)方案優(yōu)劣過程中對(duì)各個(gè)指標(biāo)的側(cè)重程度。(2)平臺(tái)調(diào)整評(píng)價(jià)模型1)增加k個(gè)平臺(tái)后，區(qū)域平臺(tái)工作量標(biāo)準(zhǔn)差的增量，若即A區(qū)平臺(tái)工作量標(biāo)準(zhǔn)差減小，則區(qū)域平臺(tái)工作量被優(yōu)化，即工作量更均衡。2)若增加平臺(tái)后，Dmax減小，則出警時(shí)間被優(yōu)化，即出警時(shí)間減小。假設(shè)在k個(gè)節(jié)點(diǎn)處增加k個(gè)平臺(tái)(每個(gè)節(jié)點(diǎn)處增加一個(gè)平臺(tái))，若共有i個(gè)節(jié)點(diǎn)，則有種方案。定義表示最優(yōu)方案中的區(qū)域工作量標(biāo)準(zhǔn)差，表示最優(yōu)方案中的最遠(yuǎn)距離。對(duì)于增加k個(gè)平臺(tái)時(shí)的第x(x=1,2,…,X)個(gè)方案,定義表示區(qū)域工作量標(biāo)準(zhǔn)差，表示區(qū)域的最遠(yuǎn)距離。定義的變化率，的變化率 。由于與的變化率不同，若直接引入?yún)?shù)，會(huì)出現(xiàn)較大誤差。為糾正變化率誤差，引入系數(shù)（）。設(shè) 。根據(jù)題設(shè)，令x=1對(duì)應(yīng)的方案為初始最優(yōu)方案，即=、=：①若，則方案x優(yōu)于原有最優(yōu)方案，令=，=；②若，則原有最優(yōu)方案優(yōu)于方案x，、取值不變；③若，則、取值不變；④每比完一次，令x= x+1，用和所得的S值與和所得的S值進(jìn)行比較。重復(fù)第④步，直到比完x=為止。通過用以上算法，可從兩個(gè)方案中選出較好的一個(gè)，窮舉所有方案，可得最優(yōu)方案。 結(jié)果及其分析與評(píng)價(jià) 標(biāo)準(zhǔn)差的計(jì)算。標(biāo)準(zhǔn)差體現(xiàn)了區(qū)域內(nèi)各平臺(tái)間工作量的差異大小。 不同權(quán)重時(shí)，增加平臺(tái)的方案通過對(duì)所有可行方案窮舉，利用基于不同權(quán)重的平臺(tái)調(diào)整評(píng)價(jià)模型給出權(quán)重u和v 在[0,1]。得到新增4個(gè)平臺(tái)的具體增加方案及其對(duì)應(yīng)的標(biāo)準(zhǔn)差和最遠(yuǎn)距離，、：其中，（） 不同權(quán)重值下新增2個(gè)平臺(tái)后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離 不同權(quán)重值下新增3個(gè)平臺(tái)后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離 不同權(quán)重值下新增4個(gè)平臺(tái)后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離，有的平臺(tái)位于高發(fā)案率區(qū)域，工作量過重；有的平臺(tái)位于低發(fā)案率區(qū)域，工作量較輕。為了對(duì)警務(wù)資源合理利用，分別給出了增加2，3，4個(gè)平臺(tái)時(shí)在11對(duì)不同的（u，v）影響下A區(qū)工作量的標(biāo)準(zhǔn)差和最長出警時(shí)間。運(yùn)用基于不同權(quán)重的平臺(tái)調(diào)整評(píng)價(jià)模型，我們共給出了33組可行解，均可滿足設(shè)置平臺(tái)的基本原則和任務(wù)。其中，表中用陰影底面突出的數(shù)據(jù)為工作量均衡性和出警時(shí)間均得到優(yōu)化的可行解，為建議可行解?！?)增加2個(gè)平臺(tái)時(shí)，有1組建議可行解；2)增加3個(gè)平臺(tái)時(shí)，有8組建議可行解；3)增加4個(gè)平臺(tái)時(shí)，有5組建議可行解。它們使A區(qū)平臺(tái)的工作量和出警時(shí)間均得到優(yōu)化?？筛鶕?jù)具體要求選擇不同方案。現(xiàn)給出一組示例——新增平臺(tái)設(shè)置方案如下：考慮到現(xiàn)有交巡警服務(wù)平臺(tái)的工作量不均衡和有些地方出警時(shí)間過長，決定增加4個(gè)平臺(tái)，令u=，v=，新增平臺(tái)分別位于22464號(hào)路口節(jié)點(diǎn)處?！?，分析比較參數(shù)在不同權(quán)重下對(duì)兩個(gè)指標(biāo)的影響：(a)(b) 圖(a)中直線表示沒有增加平臺(tái)時(shí)的最遠(yuǎn)距離，三條虛線分別表示增加4個(gè)平臺(tái)時(shí)在不同權(quán)重v下的最遠(yuǎn)距離。由圖可知增加2個(gè)平臺(tái)時(shí)，當(dāng)時(shí)，最遠(yuǎn)距離比現(xiàn)狀距離短且遞