全國數(shù)學(xué)建模競賽一等獎?wù)撐?在線瀏覽
2025-05-22 03:22本頁面
【正文】 臺管轄范圍分配方案。所謂網(wǎng)絡(luò)或容量網(wǎng)絡(luò)指的是一個連通的賦權(quán)有向圖G(V,E,C)，其中V是該圖的頂點(diǎn)集，E是有向邊(即弧)集，C是弧上的容量集。網(wǎng)絡(luò)上的流就是由源點(diǎn)流向匯點(diǎn)的可行流，這是定義在網(wǎng)絡(luò)上的非負(fù)函數(shù)，它一方面受到容量的限制，另一方面除去源點(diǎn)和匯點(diǎn)以外，在所有中途點(diǎn)要求保持流入量和流出量平衡。算法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值。在兩點(diǎn)間最短路基礎(chǔ)上，得平臺管轄范圍的初始分配方案1；再使用上下界網(wǎng)絡(luò)流算法得到各交巡警服務(wù)平臺管轄范圍優(yōu)化分配方案2， 。A區(qū)交巡警服務(wù)平臺管轄范圍分配方案1雖然給出了各平臺管轄范圍，保證所有節(jié)點(diǎn)都能被平臺支配，但平臺管轄范圍分布不均。可見此方案雖可行，但仍有不合理之處，故需要優(yōu)化?？梢悦黠@看出與方案1相比，方案2中各平臺轄區(qū)大小的分布更均勻，其中65%的平臺轄區(qū)內(nèi)路口數(shù)目均為6—7個，另外方案1中只負(fù)責(zé)一兩個路口的AA12等平臺轄區(qū)內(nèi)路口數(shù)目也有所適量增加，大大減少了平臺管轄范圍分配不均衡的現(xiàn)象。 。可將兩種不同對象處理成二分圖的結(jié)構(gòu)，平臺和路口的可達(dá)關(guān)系處理成圖中的邊集，一對一的封鎖關(guān)系即是二分圖的一個匹配，整個問題是一個典型的二分圖完美匹配問題。 基于二分圖完美匹配模型的調(diào)度方案的確定求一個二分圖的完美匹配的普遍算法是Hungary最大匹配算法[5]，我們可以通過枚舉最遠(yuǎn)距離L后驗證，從而將一個求解性問題轉(zhuǎn)化為判定性問題，簡化了問題的求解過程。 結(jié)果及其分析與評價利用二分圖的完美匹配模型，得出A區(qū)20個平臺封鎖13個路口的最佳調(diào)度方案，即每個平臺應(yīng)該負(fù)責(zé)封鎖的路口，路程距離和出警時間。七、問題一 平臺設(shè)置調(diào)整方案的確定 建模分析在A區(qū)增加2至5個平臺，建立模型求解平臺增數(shù)和位置。 通過分析題目，平臺設(shè)置方案可以從交巡警服務(wù)平臺工作量的均衡性和出警時間長短兩個方面進(jìn)行評價。已知交巡警時速為60km/h，則出警時間可用平臺與路口節(jié)點(diǎn)的最短路距離來衡量。建立基于不同權(quán)重的平臺調(diào)整評價模型，求解對應(yīng)平臺增數(shù)的所增平臺位置，得出結(jié)論。定義這n條最短路中距離最長的為該區(qū)最遠(yuǎn)距離Dmax，對應(yīng)最長出警時間。hj：定義平臺工作量hj指其平均每天需要處理的報警案件的總次數(shù)。：定義平臺工作量的標(biāo)準(zhǔn)差 。下面給出增加不同平臺數(shù)時的可行方案，算法規(guī)則：（1）節(jié)點(diǎn)與平臺間的距離Dij應(yīng)盡量在3000m以內(nèi)；（2）當(dāng)節(jié)點(diǎn)發(fā)案率C≥2，至少被最近的2個平臺管轄；（3）當(dāng)節(jié)點(diǎn)發(fā)案率C2，至少被最近的1個平臺管轄。 基于枚舉算法的增加平臺方案 基于不同權(quán)重的平臺調(diào)整評價模型(1)權(quán)重參數(shù)定義平臺工作量均衡性影響力的權(quán)重為u，用出警次數(shù)標(biāo)準(zhǔn)差衡量；出警時間影響力的權(quán)重為v，用平臺到節(jié)點(diǎn)的最短路距離衡量。u，v的大小可根據(jù)實際情況及具體需求確定。通過調(diào)整這兩個權(quán)值來調(diào)整平臺工作量均衡性、出警時間長短對平臺設(shè)置的相對影響程度，反映評價方案優(yōu)劣過程中對各個指標(biāo)的側(cè)重程度。2)若增加平臺后，Dmax減小，則出警時間被優(yōu)化，即出警時間減小。定義表示最優(yōu)方案中的區(qū)域工作量標(biāo)準(zhǔn)差，表示最優(yōu)方案中的最遠(yuǎn)距離。定義的變化率，的變化率 。為糾正變化率誤差，引入系數(shù)（）。根據(jù)題設(shè)，令x=1對應(yīng)的方案為初始最優(yōu)方案，即=、=：①若，則方案x優(yōu)于原有最優(yōu)方案，令=，=；②若，則原有最優(yōu)方案優(yōu)于方案x，、取值不變；③若，則、取值不變；④每比完一次，令x= x+1，用和所得的S值與和所得的S值進(jìn)行比較。通過用以上算法，可從兩個方案中選出較好的一個，窮舉所有方案，可得最優(yōu)方案。標(biāo)準(zhǔn)差體現(xiàn)了區(qū)域內(nèi)各平臺間工作量的差異大小。得到新增4個平臺的具體增加方案及其對應(yīng)的標(biāo)準(zhǔn)差和最遠(yuǎn)距離，、：其中，（） 不同權(quán)重值下新增2個平臺后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離 不同權(quán)重值下新增3個平臺后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離 不同權(quán)重值下新增4個平臺后工作量標(biāo)準(zhǔn)差和最遠(yuǎn)工作距離，有的平臺位于高發(fā)案率區(qū)域，工作量過重；有的平臺位于低發(fā)案率區(qū)域，工作量較輕。運(yùn)用基于不同權(quán)重的平臺調(diào)整評價模型，我們共給出了33組可行解，均可滿足設(shè)置平臺的基本原則和任務(wù)?！?)增加2個平臺時，有1組建議可行解；2)增加3個平臺時，有8組建議可行解；3)增加4個平臺時，有5組建議可行解。可根據(jù)具體要求選擇不同方案?！?，分析比較參數(shù)在不同權(quán)重下對兩個指標(biāo)的影響：(a)(b) 圖(a)中直線表示沒有增加平臺時的最遠(yuǎn)距離，三條虛線分別表示增加4個平臺時在不同權(quán)重v下的最遠(yuǎn)距離。上述范圍內(nèi)的方案均得到優(yōu)化。圖(b)中直線表示沒有增加平臺時工作量的標(biāo)準(zhǔn)差，三條虛線分別表示增加4個平臺時在不同權(quán)重u下的標(biāo)準(zhǔn)差?？梢钥闯觯瑱?quán)重u越大，使標(biāo)準(zhǔn)差盡量小這一原則得到的優(yōu)化越好。八、問題二 平臺設(shè)置方案評價及調(diào)整 建模分析首先明確設(shè)置交巡警服務(wù)平臺的原則和任務(wù)，其次計算六區(qū)的工作量標(biāo)準(zhǔn)差和超距比例p，對該市現(xiàn)有方案合理性進(jìn)行評價，判斷是否合理。設(shè)置交巡警服務(wù)平臺時應(yīng)滿足以下兩個原則和任務(wù)：1)使各交巡警服務(wù)平臺的工作量盡量均衡；2)使各交巡警中最長出警時間盡量短。p值越大，說
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1