網(wǎng)絡(luò)選址中的若干模型和算法研究.pdf

1、選址問題是運(yùn)籌學(xué)中的經(jīng)典問題之一,在生產(chǎn)生活甚至軍事中都有著非常廣泛的應(yīng)用。網(wǎng)絡(luò)是大多數(shù)選址主體進(jìn)行選址決策的載體,所以對網(wǎng)絡(luò)選址的研究往往更有實(shí)際意義。
　　 論文主要研究用改進(jìn)的元啟發(fā)式算法來求解網(wǎng)絡(luò)選址中的若干模型,這些模型都是NP-難問題。論文的具體內(nèi)容如下:第一章介紹了課題研究的背景及選址問題的研究現(xiàn)狀,并闡述了本文的主要工作。第二章介紹了一些經(jīng)典的網(wǎng)絡(luò)選址問題。第三章介紹了一些元啟發(fā)式算法。
　　 第四章,針

2、對規(guī)模較大的集合覆蓋問題,提出改進(jìn)的遺傳算法進(jìn)行求解。對遺傳算法的改進(jìn)主要包括初始種群的產(chǎn)生、對不可行解和重復(fù)個(gè)體的處理、以及新的交叉和變異方法的提出。最后在數(shù)值實(shí)驗(yàn)中與其他算法進(jìn)行了比較,并分析了算法改進(jìn)的有效性。
　　 第五章,針對規(guī)模較大的頂點(diǎn)p-中心問題,通過綜合遺傳算法和模擬退火算法的優(yōu)點(diǎn),提出了一種單親遺傳和模擬退火的混合算法進(jìn)行求解,并設(shè)計(jì)了自適應(yīng)選擇法和自適應(yīng)基因重組操作,最后在數(shù)值實(shí)驗(yàn)中與其他三種算法進(jìn)行了比較

3、,結(jié)果表明本章算法更有效。
　　 第六章提出了一種多目標(biāo)反p-中心問題,并利用線性加權(quán)和法將其轉(zhuǎn)化為單目標(biāo)問題,然后建立了其整數(shù)規(guī)劃模型,并且嘗試用單親遺傳模擬退火算法來求解。最后針對不同的權(quán)重,分別進(jìn)行了數(shù)值實(shí)驗(yàn),并分析了算法的有效性。
　　 第七章,針對廣義最小生成樹問題,設(shè)計(jì)了兩種改進(jìn)的元啟發(fā)式算法來求解。在改進(jìn)的禁忌搜索算法中,通過在兩種鄰域進(jìn)行搜索來避免陷入局部最優(yōu)。最后通過數(shù)值實(shí)驗(yàn)對這兩種算法進(jìn)行了比較,并驗(yàn)