帶次模特性的倉庫選址問題研究.pdf

1、本文研究了一系列具有次模特性的倉庫選址問題，包括:帶次模運(yùn)營費(fèi)用的倉庫選址問題，帶次模懲罰費(fèi)用的倉庫選址問題，以及帶次模運(yùn)營費(fèi)用和次模懲罰費(fèi)用的倉庫選址問題.我們分別對這三類問題設(shè)計(jì)近似算法.對于每一個(gè)本文研究的問題，我們的近似算法都具有目前最好的近似比.
　　在第一章，我們介紹了本文將用到的相關(guān)知識(shí)，研究的內(nèi)容，背景以及我們的研究結(jié)果.
　　在第二章，我們研究了兩類帶次模運(yùn)營費(fèi)用的倉庫選址問題，即:倉庫零售商網(wǎng)絡(luò)設(shè)計(jì)(WR

2、ND)問題和隨機(jī)運(yùn)輸庫存網(wǎng)絡(luò)設(shè)計(jì)(STIND)問題.這兩個(gè)問題都可以看做是經(jīng)典的組合優(yōu)化問題——無容量限制的設(shè)施選址(UFL)問題的推廣.在UFL問題的基礎(chǔ)上，WRND問題和STIND問題難度的增加主要在于引入一個(gè)新的費(fèi)用——庫存費(fèi)用:其中WRND問題引入了倉庫-零售商互相影響的兩層庫存費(fèi)用，STIND問題引入了安全庫存費(fèi)用.我們?yōu)檫@兩個(gè)問題設(shè)計(jì)了常數(shù)近似比的近似算法，可以用于解決大規(guī)模問題.
　　在第三章，我們研究了帶次模懲罰費(fèi)

3、用的倉庫選址(WLPSP)問題以及它的特殊情況帶線性懲罰的倉庫選址問題(WLPLP).我們先給出了關(guān)于WLPSP問題的2.044-近似算法，并把這個(gè)近似算法推廣成一個(gè)算法框架用以解決一系列的帶次模懲罰問題.具體的來說，我們給出的算法框架，可以把一個(gè)不帶次模懲罰問題基于舍入技巧的α-近似算法改造成帶次模懲罰問題的(1-e-1/α)-近似算法.另外，我們通過探索WLPSP問題和WLPLP問題的特殊結(jié)構(gòu)，我們進(jìn)一步給出WLPSP問題的一個(gè)改進(jìn)

4、算法，將近似比改進(jìn)到2;進(jìn)一步給出WLPLP問題的一個(gè)改進(jìn)算法，將近似比改進(jìn)到1,5148.
　　在第四章，我們繼續(xù)研究WLPSP問題，我們通過組合已有的原始對偶算法和我們的貪婪增廣算法，給出一個(gè)新的組合近似算法.這個(gè)算法是目前組合算法中近似比最好的算法，將目前原始對偶算法的近似比3改進(jìn)到了2,375.并且如果不考慮第三章我們給出的算法，我們給出的組合算法實(shí)際上改進(jìn)了已有最好的近似比2.488.
　　第五章，我們提出并研究了