摘要
产品选址问题是组合优化中一类有重要理论意义和广泛实际背景的问题。问题的要求是要从若干厂址中选择一组厂址来建立工厂，给每个工厂指定一种需要生产的产品，并且给每一个客户提供一组指派使每个客户都能有一组工厂集合来为其供应不同的产品。对于此类问题，我们的优化目标是最小化运输费用。该问题模型在网络设施的安放、网格服务点的分布等诸多方面有着大量的应用。文中对2种产品选址问题的计算复杂性进行了分析。
The product location problem is one kind of important combinatorial optimization 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 facilities. The optimal goal of this problem is to minimize the sum of the shipping costs. The product location problem has extensive applications within production management, network communication and computer theory. Assuming that fixed setup cost are zero, we analyze the computational complexity of 2-PUFLPN.
出处
《湖南铁路科技职业技术学院学报》
2009年第2期47-49,共3页
Vocational Education Research on Rail Transit
关键词
启发式算法
选址问题
NP-完全
计算复杂性
heuristic algorithm
location problem
NP-complete
computational complexity
