本论文考虑k-层有容量约束设施选址问题,此问题为NP-难问题.k-层有容量设施选址问题具有一般性,经典的无容量约束设施选址问题、1-层有容量约束设施选址问题和k-层无容量约束设施选址问题都是该问题的特殊情况.在论文中,关于1-层有容量约束设施选址问题介绍了多交换局部搜索算法和线性规划舍入算法(针对所有设施的开设费用都相等的特例);关于k-层无容量约束设施选址问题介绍了参数路径贪婪退化算法、分裂递归路径算法和随机舍入算法.在论文中,给出了k-层有容量约束设施选址问题的第一个(组合的)近似算法.在算法设计过程中,首先,根据给定的k-层有容量约束设施选址问题构造一个特殊的1-层有容量约束设施选址问题和一个特殊的(k-1)-层有容量约束设施选址问题;其次,通过调用多交换局部搜索算法给出1-层有容量约束设施选址问题的一个可行解,递归地解得(k-1)-层有容量约束设施选址问题的一个可行解;然后,通过解运输问题求得需求从第一层设施集合到路径集合的指派;最后,构造出原问题的一个可行解.在算法分析中,通过递归法给出近似比k+2+(?)+ε(ε>0).