黄书强,江秀美,范人胜

1(暨南大学 理工学院光电工程系,广州 510632)2(广东省农村信用社联合社,广州 510000)

1 引 言

选址问题是运筹学中经典的一种决策问题,有着非常广泛的应用,主要研究如何选择设施的数目和确定最优位置从而为用户提供相应的服务,有着巨大的经济和社会意义.自1964年Hakimi提出了K中心选址问题[1]之后,许多学者加入到研究这个问题的队伍中,纷纷提出自己的解决办法并且有了较大的进展.K中心选址问题是指在网络平面上选定K个建立服务站的最优位置,也就是在全局范围内寻找使得所有需求点到最近服务站的最大距离值最小的部署方案.K中心选址问题是研究其他选址问题的基础,在工厂、仓库、加油站、物流中心等的部署中都有应用.将中心选址问题以选取服务站方式进行分类可分为:离散和连续两种中心选址问题.离散K中心选址问题是指在给定的网络节点上选取K个最优位置建立服务站,而连续K中心选址问题则是在整个网络平面上选取最优的部署方案.连续K中心选址问题相对于基于节点的离散K中心选址问题,其服务站部署位置的选取对于环境的适应性更强,并且选取位置更具有一般性,但是求解过程的复杂度也更大[2].

对于K中心选址问题,目前大多数研究都是以离散中心选址为主,对于离散K中心选址问题的研究相对比较成熟.文献[3]提出先求得最大距离,之后再求最大覆盖问题,得到离散K中心选……