用智能優(yōu)化算法求解固定費(fèi)用運(yùn)輸問(wèn)題.pdf

1、固定費(fèi)用運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題。與線性運(yùn)輸問(wèn)題的特征相似，固定費(fèi)用運(yùn)輸問(wèn)題也需滿足供應(yīng)與需求約束，且具有運(yùn)輸網(wǎng)絡(luò)特征，但固定費(fèi)用的出現(xiàn)使得目標(biāo)函數(shù)出現(xiàn)不連續(xù)性，從而導(dǎo)致其成為一個(gè)NP難問(wèn)題。該問(wèn)題的求解目標(biāo)是在滿足目的地需求的同時(shí)，分配每個(gè)源地可用供應(yīng)量，以使得分配后所產(chǎn)生的總的變化成本和固定成本之和最小。 求解固定費(fèi)用運(yùn)輸問(wèn)題的方法很多。起初人們用一些精確算法來(lái)求解，例如切平面法，極點(diǎn)排列法，分枝定界法等。但這些方法

2、被證明低效且計(jì)算費(fèi)時(shí)，只適合求解較小規(guī)模問(wèn)題。為了克服計(jì)算時(shí)間過(guò)長(zhǎng)的問(wèn)題，一些啟發(fā)式方法被用于求解該問(wèn)題，例如拉格朗日松馳法，鄰近極點(diǎn)法等。雖然這些方法計(jì)算耗時(shí)較少，但所獲得的解的質(zhì)量較差。近年來(lái)，相繼出現(xiàn)一些現(xiàn)代啟發(fā)式遺傳算法求解該問(wèn)題，例如基于矩陣排列編碼的遺傳算法、禁忌搜索算法、利用邊集編碼的遺傳算法等。經(jīng)實(shí)驗(yàn)證明，它們也各有其優(yōu)點(diǎn)與不足。 本論文的總體框架如下： 第一章簡(jiǎn)要介紹了運(yùn)輸問(wèn)題的四個(gè)研究分支，深入分析了

3、固定費(fèi)用運(yùn)輸問(wèn)題的背景、國(guó)內(nèi)外研究現(xiàn)狀及各類求解方法。 第二章深入討論了智能優(yōu)化算法的基本概念和定理，如標(biāo)準(zhǔn)遺傳算法，免疫遺傳算法等，并給出了技術(shù)路線、實(shí)現(xiàn)方法和研究?jī)?nèi)容。 第三章介紹了基于Prufer數(shù)編碼的生成樹方法，分析了它的優(yōu)點(diǎn)與不足。 第四章提出了一種森林補(bǔ)充式多點(diǎn)交叉操作的遺傳算法。為了進(jìn)一步改進(jìn)智能優(yōu)化算法求解固定費(fèi)用運(yùn)輸問(wèn)題的性能，利用其解是運(yùn)輸圖的一棵生成樹的特性，對(duì)采用先根遍歷邊構(gòu)成有序邊集編

4、碼的生成樹，提出了一種新的森林補(bǔ)充式多點(diǎn)交叉操作的啟發(fā)式遺傳算法。通過(guò)理論證明和不同類型和規(guī)模實(shí)驗(yàn)檢測(cè)實(shí)驗(yàn)，結(jié)果表明該算法所得解的質(zhì)量?jī)?yōu)于基于邊集編碼的遺傳算法。該算法豐富了近似求解固定費(fèi)用運(yùn)輸問(wèn)題的思路。 第五章提出了一種求解固定費(fèi)用運(yùn)輸問(wèn)題的免疫遺傳算法。為了進(jìn)一步體現(xiàn)該遺傳算法的性能，與基于矩陣編碼的遺傳算法和基于邊集編碼的遺傳算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果表明，免疫遺傳算法的綜合性能優(yōu)于其他兩種方法。該算法豐富了近似求解固定費(fèi)