一个关于求解k-种产品选址问题的近似算法

• 作者: 易斌 李荣珩
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 近似算法 工厂选址 k-种产品
• 年，卷（期）: 2008,（1）
• 所属期刊栏目: 产品、研发、测试
• 页码范围: 97-99
• 页数: 3页
• 分类号: TP301.6
• 字数: 3388字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.01.031

摘要

对于k-种产品工厂选址问题,有如下描述:存在一组客户和一组可以建立工厂的厂址.现在有k种不同的产品,要求每一个客户必须由k个不同的工厂来提供k种不同的产品,其中每个工厂都只能为客户提供唯一的一种产品.在该问题中,假定建厂费用以及任意两个结点之间的运输费用都为非负,并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质.问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品.对于此类问题,优化目标是最小化建厂费用以及运输费用.论文在假设建厂费用为零的前提下,提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	易斌	湖南师范大学数学与计算机学院	4	42	2.0	4.0
2	李荣珩	湖南师范大学数学与计算机学院	11	25	3.0	4.0