設(shè)施選址中的一些模型與算法.pdf

1、本文主要研究用一些元啟發(fā)式算法來求解一些經(jīng)典的設(shè)施選址問題及其擴(kuò)展問題。
　　 首先,本文簡單闡述了設(shè)施選址的發(fā)展以及研究現(xiàn)狀,介紹了一些經(jīng)典的設(shè)施選址模型,包括Weber問題、集合覆蓋問題等。選址問題是常見的優(yōu)化問題,其中很多都是NP-難問題。已有許多方法來求解設(shè)施選址問題,本文首先介紹了幾種常見的算法,包括傳統(tǒng)方法和元啟發(fā)式算法。傳統(tǒng)方法有Weiszfeld算法、分枝定界法和拉格朗日松弛算法等；元啟發(fā)式算法有交鄰域搜索算法,

2、遺傳算法等。
　　 其次,本文綜合了點(diǎn)上帶權(quán)和邊上帶權(quán)的k-CARD問題,提出了一種更為一般和實(shí)際的模型,并應(yīng)用一種新的變鄰域搜索方法進(jìn)行求解。它根據(jù)模型的特點(diǎn)劃分鄰域,通過貪婪算法的思想選擇初始點(diǎn),并且在變鄰域過程中采用簡單的交換葉子的思想簡化算法。這三點(diǎn)極大地提高了變鄰域搜索方法求解此推廣問題的計(jì)算效率。
　　 再次,對于經(jīng)典模型中的p-中位問題,本文提出一種新的變鄰域搜索算法。該算法嵌套使用鄰域變換思想,并且在搜索

3、局部最優(yōu)解時(shí)應(yīng)用了一種基于自然界蜘蛛網(wǎng)模型的蛛網(wǎng)搜索,避免了一些不必要的搜索路徑。實(shí)驗(yàn)證明該算法求解p-中位問題是有效的。
　　 緊接著,針對一種p不定的推廣p-中位問題,本文應(yīng)用了簡單啟發(fā)式算法、變鄰域搜索算法和改進(jìn)的遺傳算法進(jìn)行求解。在變鄰域搜索算法的鄰域變換中采用以概率選取鄰域的思想；在遺傳算法中加入了種群改進(jìn)策略、局部搜索策略和最優(yōu)保存策略。實(shí)驗(yàn)表明遺傳算法求解該推廣p-中位問題比另外兩種算法有效。
　　 最后,