摘要
对于k-种产品工厂选址问题,有如下描述:存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品。在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题,优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。
A k-product uncapacitated facility location problem can be described as follows.There is a set of clients and a set of potential sites where facilities can be set up.There are k different kinds of products.Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non- negative fixed cost.There is a nonnegative cost of shipping goods between each pair of locations.These costs are assumed to be symmetric and satisfy the triangle inequality within the problem.The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k facilities.The optimal goal of this problem is to minimize the sum of the setup costs and the shipping costs.Assuming that fixed setup cost are zero,we have gived a 3k/2-1 approximation algorithm for the problem.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第1期97-99,共3页
Computer Engineering and Applications
基金
湖南省教育厅资助科研课题(the Research Project of Department of Education of Hunan Province
China under Grant No.05A037)。
关键词
近似算法
工厂选址
k-种产品
approximation algorithms
facility location
k-product
