论文部分内容阅读
本文研究了一系列具有次模特性的仓库选址问题,包括：带次模运营费用的仓库选址问题,带次模惩罚费用的仓库选址问题,以及带次模运营费用和次模惩罚费用的仓库选址问题.我们分别对这三类问题设计近似算法.对于每一个本文研究的问题,我们的近似算法都具有目前最好的近似比.在第一章,我们介绍了本文将用到的相关知识,研究的内容,背景以及我们的研究结果.在第二章,我们研究了两类带次模运营费用的仓库选址问题,即：仓库零售商网络设计(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-近似原始对偶算法.