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

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

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

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

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