【摘要】：本文研究了一系列具有次模特性的倉庫選址問題,包括：帶次模運營費用的倉庫選址問題,帶次模懲罰費用的倉庫選址問題,以及帶次模運營費用和次模懲罰費用的倉庫選址問題.我們分別對這三類問題設計近似算法.對於每一個本文研究的問題,我們的近似算法都具有目前最好的近似比. 在第一章,我們介紹了本文將用到的相關知識,研究的內容,背景以及我們的研究結果. 在第二章,我們研究了兩類帶次模運營費用的倉庫選址問題,即：倉庫零售商網路設計(WRND)問題和隨機運輸庫存網路設計(STIND)問題.這兩個問題都可以看做是經典的組合最佳化問題——無容量限制的設施選址(UFL)問題的推廣.在UFL問題的基礎上,WRND問題和STIND問題難度的增加主要在於引入一個新的費用——庫存費用：其中WRND問題引入了倉庫-零售商互相影響的兩層庫存費用,STIND問題引入了安全庫存費用.我們為這兩個問題設計了常數近似比的近似算法,可以用於解決大規模問題. 在第三章,我們研究了帶次模懲罰費用的倉庫選址(WLPSP)司題以及它的特殊情況帶線性懲罰的倉庫選址問題(WLPLP)我們先給出了關於WLPSP司題的2.044-近似算法,並把這個近似算法推廣成一個算法框架用以解決一系列的帶次模懲罰問題.具體的來說,我們給出的算法框架,可以把一個不帶次模懲罰問題基於捨入技巧的α-近似算法改造成帶次模懲罰問題的(1-e-1/α)-近似算法.另外,我們通過探索WLPSP問題和WLPLP司題的特殊結構,我們進一步給出WLPSP問題的一個改進算法,將近似比改進到2；進一步給出WLPLP問題的一個改進算法,將近似比改進到1.5148. 在第四章,我們繼續研究WLPSP問題,我們通過組合已有的原始對偶算法和我們的貪婪增廣算法,給出一個新的組合近似算法.這個算法是目前組合算法中近似比最好的算法,將目前原始對偶算法的近似比3改進到了2.375.並且如果不考慮第三章我們給出的算法,我們給出的組合算法實際上改進了已有最好的近似比2.488. 第五章,我們提出並研究了帶次模懲罰費用的倉庫零售商網路設計(WRNDSP)問題.在這個問題中我們允許以支付懲罰費用為代價不為一部分零售商提供服務.我們假設這個懲罰費用是一個關於被拒絕提供服務的零售商集合的不減次模函式.我們給出了關於這個問題的一個3-近似原始對偶算法.
【關鍵字】：倉庫選址次模函式近似算法組合最佳化
【學位授予單位】：北京交通大學
【學位級別】：博士
【學位授予年份】：2012
【分類號】：O224
【目錄】：
- 致謝5-6
- 中文摘要6-8
- ABSTRACT8-10
- 目錄10-12
- 第一章 引言12-28
- 1.1 準備知識12-18
- 1.1.1 次模函式12-13
- 1.1.2 設施選址問題與近似算法13-18
- 1.2 研究的內容與研究現狀18-27
- 1.2.1 帶次模運營費用的倉庫選址問題18-22
- 1.2.2 帶次模懲罰費用的倉庫選址問題22-25
- 1.2.3 帶次模運營費用和次模懲罰費用的倉庫選址問題25-27
- 1.3 我們的結果和文章結構27-28
- 第二章 帶次模運營費用的倉庫選址問題28-46
- 2.1 倉庫零售商網路設計(WRND)問題28-37
- 2.1.1 WRND問題的數學模型28-29
- 2.1.2 算法與分析29-37
- 2.2 隨機運輸庫存網路設計(STIND)問題37-44
- 2.2.1 STIND問題的數學模型37-38
- 2.2.2 算法與分析38-44
- 2.3 本章小結44-46
- 第三章 帶次模懲罰費用的倉庫選址問題——舍人算法46-62
- 3.1 對於一類帶次模懲罰問題的算法框架設計46-52
- 3.1.1 關於WLPSP問題的一個捨入算法46-51
- 3.1.2 關於一般的帶次模懲罰問題的捨入算法框架51-52
- 3.2 關於WLPSP問題更好的近似算法52-60
- 3.2.1 關於WLPSP問題更好的近似算法52-54
- 3.2.2 關於WLPLP問題更好的近似算法54-60
- 3.3 本章小結60-62
- 第四章 帶次模懲罰費用的倉庫選址問題——組合算法62-72
- 4.1 Du-Lu-Xu原始對偶算法62-63
- 4.2 貪婪增廣算法63-69
- 4.3 原始對偶算法+貪婪增廣算法69-71
- 4.4 本章小結71-72
- 第五章 帶次模運營費用和次模懲罰費用的倉庫選址問題72-82
- 5.1 WRNDSP問題的模型72-73
- 5.2 算法與分析73-80
- 5.3 本章小結80-82
- 第六章 結論與展望82-84
- 參考文獻84-89
- 作者簡介89-94
