二次多背包問題及其擴展問題的啟發(fā)式算法研究.pdf

1、二次多背包問題是經(jīng)典0-1背包問題的一個擴展，在實際生活著中有著廣泛的應用，例如當不同工人相互合作時有不同效率的情況下將工人分配到不同的任務、有預算約束下通信衛(wèi)星的地球站選址問題以及鐵路站點、貨物運輸終端、機場的選址問題等。與之相關的組成醫(yī)療小組問題來源于意大利米蘭的某個醫(yī)療服務中心，該問題與二次多背包問題有著相似的結構，可以看成二次多背包問題的變種問題。這兩個問題除了廣泛的實際應用背景，也是一類十分復雜的組合優(yōu)化問題，對于設計啟發(fā)式算

2、法求解十分有挑戰(zhàn)。鑒于其實用性和理論挑戰(zhàn)性，已經(jīng)吸引了大批學者的目光，在文獻中提出了各類求解這兩個問題的啟發(fā)式算法，但是仍然存在不足之處，還需要進一步的深入研究。本文擬在在已有的研究求解二次多背包問題以及組成醫(yī)療小組問題文獻的基礎上，提出更為高效的啟發(fā)式算法并提升現(xiàn)有文獻中的最好解，為求解這類問題提供更多的選擇。
　　首先，研究了使用混合了可行與不可行局部搜索的禁忌搜索算法求解二次多背包問題。該算法引入了不可行解搜索階段，允許算法

3、在搜索過程中搜索不可行解，能夠為算法帶來更多的自由度。然后，我們在算例上進行了大量的實驗來證明該算法的有效性并分析了算法各個重要組成部分的關鍵作用。
　　其次，本文根據(jù)二次多背包問題的分組特性，提出了一種基于backbone交叉算子混合算法求解該問題，該算子能夠保留父代中的物品分配信息并遺傳到子代，產(chǎn)生高質量的解。我們將該混合算法在不同時間限制下的計算結果與文獻中求解QMKP最好的幾種算法進行了對比，證明了該算法優(yōu)異性并給出了小結

4、。
　　第三，研究了由二次多背包問題變種而來的組成醫(yī)療小組問題，結合該問題的特點，提出了一種求解組成醫(yī)療小組問題的二階段禁忌搜索算法。該算法中的二階段局部搜索過程可以很好的處理目標函數(shù)和約束之間相互影響的關系，能夠防止算法過早地陷入局部最優(yōu)。我們通過實驗將該算法與文獻中的最好算法進行了對比，并分析了二階段搜索過程對算法性能的影響，最后給出了小結。
　　第四，延續(xù)了第五章所研究的組成醫(yī)療小組問題，根據(jù)該問題的分組特性，將求解二