動態(tài)多重網(wǎng)絡(luò)最短路阻斷問題研究.pdf

1、網(wǎng)絡(luò)阻斷是一類帶有博弈特點(diǎn)的優(yōu)化決策問題，該問題與網(wǎng)絡(luò)結(jié)構(gòu)密切相關(guān)，在軍事、交通運(yùn)輸、基礎(chǔ)設(shè)施領(lǐng)域具有廣泛的應(yīng)用背景。經(jīng)典的網(wǎng)絡(luò)阻斷問題以單層網(wǎng)絡(luò)為研究對象，包含上下兩層決策者：網(wǎng)絡(luò)運(yùn)營方與阻斷方；通常建模為二層混合整數(shù)數(shù)學(xué)規(guī)劃問題，以進(jìn)行定量的優(yōu)化決策。目前的研究僅針對單層網(wǎng)絡(luò)阻斷問題，然而實(shí)際中廣泛存在的多重網(wǎng)絡(luò)及其網(wǎng)間依賴關(guān)系，對與網(wǎng)絡(luò)相關(guān)的優(yōu)化問題具有顯著的影響。因此，本文在單層網(wǎng)絡(luò)最短路阻斷模型的基礎(chǔ)上，建立了動態(tài)多重網(wǎng)絡(luò)最短

2、路阻斷模型框架，并設(shè)計(jì)了相關(guān)算法。本文研究的核心在于問題建模和算法設(shè)計(jì)兩個方面，并通過仿真數(shù)據(jù)和實(shí)際案例數(shù)據(jù)對模型和算法進(jìn)行驗(yàn)證和分析，內(nèi)容如下：
　　1）節(jié)點(diǎn)阻斷型單層網(wǎng)絡(luò)最短路阻斷問題的建模與算法設(shè)計(jì)。通過引入節(jié)點(diǎn)阻斷的轉(zhuǎn)換約束，建立針對節(jié)點(diǎn)的單層網(wǎng)絡(luò)最短路阻斷模型；同時，在經(jīng)典的對偶算法和本德斯分解算法的基礎(chǔ)上，提出阻斷子圖分解算法及相關(guān)改進(jìn)策略。此外，以研究資源投入與阻斷收益的權(quán)衡為目的，建立最大化最短路-最小化阻斷資源的

3、雙目標(biāo)最短路阻斷模型，提出序列子圖分解算法，并以帕累托最優(yōu)解為基礎(chǔ)研究網(wǎng)絡(luò)阻斷問題的飽和特性，為資源投入與阻斷收益的權(quán)衡和決策提供了理論分析依據(jù)。
　　2）動態(tài)多重網(wǎng)絡(luò)最短路阻斷問題模型框架的建立與算法設(shè)計(jì)。以單層網(wǎng)絡(luò)最短路阻斷問題模型為基礎(chǔ)，通過引入依賴函數(shù)對多重網(wǎng)絡(luò)的網(wǎng)間依賴關(guān)系進(jìn)行建模，將多重網(wǎng)絡(luò)最短路阻斷問題轉(zhuǎn)換為單層網(wǎng)絡(luò)最短路阻斷問題。同時，以網(wǎng)間反饋關(guān)系為例，給出依賴函數(shù)的建模方法、邏輯約束的線性化方法，以建立存在此類

4、網(wǎng)間依賴關(guān)系的多重網(wǎng)絡(luò)的最短路阻斷模型。此外，本文提出針對動態(tài)多重網(wǎng)絡(luò)最短路阻斷模型的算法：對偶算法、本德斯分解算法；以雙層網(wǎng)絡(luò)最短路阻斷問題為例，通過利用多重網(wǎng)絡(luò)的結(jié)構(gòu)信息，提出基于反饋穩(wěn)態(tài)階段上界的算法改進(jìn)；在保證解的最優(yōu)性的前提下，該改進(jìn)策略可以大幅削減由于多重網(wǎng)絡(luò)動態(tài)失效（故障）傳播而引入的邏輯約束，以提高算法效率。
　　3）實(shí)驗(yàn)驗(yàn)證與案例分析。結(jié)合仿真網(wǎng)絡(luò)數(shù)據(jù)與實(shí)際案例數(shù)據(jù)，對上述模型和算法進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)對比分析了上

5、述算法的求解效率，同時分析網(wǎng)絡(luò)規(guī)模、阻斷資源總量、網(wǎng)絡(luò)結(jié)構(gòu)等對上述算法求解時間的影響。實(shí)驗(yàn)表明：提出的阻斷子圖分解算法和以之為基礎(chǔ)的序列子圖分解算法，大幅提高了單目標(biāo)和雙目標(biāo)最短路阻斷問題的求解效率、擴(kuò)大了可求解問題的規(guī)模；基于反饋穩(wěn)態(tài)階段上界的算法改進(jìn)策略大幅提升了原有算法的性能，使得雙層網(wǎng)絡(luò)最短路阻斷問題的求解效率得以提高。
　　綜上，本文對單層及動態(tài)多重網(wǎng)絡(luò)上最短路阻斷問題進(jìn)行了較為系統(tǒng)的研究，為該問題的研究提供了理論基礎(chǔ)和