一种推广的ufclp的变邻域搜索方法

《一种推广的ufclp的变邻域搜索方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第27卷第2期贵州大学学报(自然科学版)V01．27No．22010年4月JournalofGuizhouUniversity(NaturalSciences)Apr．2010文章编号1000—5269(2010)02—0018～05一种推广的UFCLP的变邻域搜索方法夏福全，吴仆(1．南京航空航天大学理学院，江苏南京211106；2．蚌埠学院理学系，安徽蚌埠233000)摘要：UFCLP问题是在经典P一中位问题上去掉中位点个数的限制，并且在目标函数中加入设施的建设费用。目前有很多启发式算法用来解决这

2、类NP一难问题。本文将UFCLP问题进行推广，加入投资限制，并且考虑距离和费用的权重。针对此推广模型的特点，提出了一种变邻域搜索方法。数值实验结果表明此VNS方法求解此推广UFCLP问题是有效的。关键词：UFCLP；变邻域搜索；NP一难；启发式算法中图分类号：0221文献标识码：A经典的P一中位问题有三个假设，其一，每个否则不建；决策变量Y，=1表示顾客i被设施_『服设施的建设费用相同；其二，每个设施没有容量限务，否则Y=0．制，顾客只被分配到离它最近的设施；其三，设施的上面的模型一方面要使得顾客到服

3、务设施的数量固定，都是P个。如果设施的建设费用根据每距离之和达到最小，另一方面又要投资费用尽可能个点的情况而不同，设施也加人容量限制，我们就的小，且不要超过总的投资。对于不同的投资者来可以建立一个简单的含有建设费用的设施选址问说，他们考虑的重点也不一样，实力雄厚的投资者题(FixedChargeLocationProblem，简称FCLP)⋯，可能更看重设施的服务效率，而一些实力稍微弱些目标函数是建设费用和运输费用之和。如果不考的投资者更看重自己的投资费用。综合考虑，我们虑设施的容量限制，就是UFCL

4、P模型。根据以上可以简单的对二者进行加权求和，不同的投资者可定义，UFCLP问题可以用以下模型表示：以取不同的权重。因此，我们考虑以下模型：UFCLP：minJ∑E』+c∑I∈IJ∑EJd∥(1)EUFCLP：min∑』I∈IJ∑EJdo．y+∑J∈J，J(2)s．t．∑iEJY=1，ViE，(1a)．∑Y=1，Vi(2a)JY～≤0，ViE1,j∈J(1b)Y一≤0，Vi∈1,j∈J(2b)Y∈{0，1}，Vi∈，，∈J∑≤B(2c)(1c)Y∈{0，1}，V∈I,j∈J∈{0，1}，V∈’，(1d

5、)其中：(2d)，～表示需求点的集合；xj∈{0，1}，V(2e)一表示设施候选点的集合；其中：d～表示需求点到设施点的距离；卜表示设施候选点的集合；一表示在点建立设施的固定费用；卜一表示设施候选点的集合；c一表示每单位单位距离的运费。一表示距离的权重；目标函数(1)是求建设费用和运输费用之和卢一表示建设费用的权重；的最小值；等式约束(1a)保证每个顾客都被服务一表示在点处建立服务设施的费用；到；不等式约束(1b)保证只有设施被建立了才可一表示点到点J．的距离；能服务顾客；决策变量=1表示在点建立设施

6、，一表示建设服务中心的最大费用。收稿日期：2010～02—20作者简介：夏福全(1978一)，男，安徽蚌埠人，硕士研究生，研究方向：非线性优化，Email：xfq78830@163．corn．t通讯作者：夏福全，Email：xfq78830@163．corn．第2期夏福全等：一种推广的UFCLP的变邻域搜索方法·l9·不等式约束(2e)保证设施的建设费用要少于最大邻域q)；总投资。其他的约束与UFCLP对应的约束相同。(1)令q=gIn；UFCLP问题是一个NP一难问题J。目前有(2)(邻域变换)随机

7、寻找∈(T)；多种启发式算法应用来解决UFCLP问题，比如，禁(3)应用局部搜索在的某一邻域内寻找最忌搜索法。]，遗传算法。VNS算法[圳是应用优解”；多种邻域结构的元启发式算法。一般的元启发式(4)如果比好，并且达到结束条件，则算法采用单一的方法构造邻域解并进行搜索，VNS就是所求的局部最优解，程序结束；否则令=，算法根据某种机制不断地改变邻域结构，从而改变g=q返回步骤(2)；如果”不比好，令g=g+搜索范围来寻找近似最优解。根据VNS方法衍生gst。。，返回步骤(2)。出了VNDS(Variab

8、leNeighbourhoodDecomposition1．2求解推广UFCLP问题的变邻域搜索方法Search)方法和SVNS(SkewedVNS)方法。前者就是通过某种技术，把原来的问题规模变小；后者我们采用点的下标集合来表示问题的解，只不主要就是在最优解取代的问题上放宽要求。过对于不同的解它们包含的点的数目也不一样。假如点3，5，8，9，12，是要建立设施的点，则该解就对于上述推广UFCEP模型，本文提出了一种可以表示为向量=[358912]；而如