摘要
基于在建立的设施的个数未知的前提下需要决定如何建立初始设施集,同时要求,当新的设施集建立后,前面已经建立的设施不能被删除的实际选址约束条件下,从占线理论出发考虑了待选址个数不确定的动态选址问题.设计了一个多项式时间的竞争算法,证明了该算法具有的竞争比,该竞争比结果优于已有的结果.
Based on the actual constrain in locating facility, that is, the decision-maker must determine where to locate the initial facilities when the final number of facilities is uncertain, and, the constructed facilities can not be removed when the new facility is built, we studies the dynamics facility location problem with the uncertain number of facilities from the online theory view. We present a polynomial competitive algorithm, whose competitive ratio is better than the existed results.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2007年第10期159-164,共6页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(10371094
70471035
70602004)
国家杰出青年基金(70525004)
博士点基金项目(20050698048)
关键词
选址
占线中心
算法
竞争比
facility location
online median
algorithm
competitive ratio
