软容量约束的物流设施选址问题的改进差分进化算法

《软容量约束的物流设施选址问题的改进差分进化算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、软容量约束的物流设施选址问题的改进差分进化算法　　摘要：研究了广泛存在于物流系统设计与管理中的软容量约束的物流设施选址问题，主要决策每个客户需求由哪个设施服务以及每个设施开放的次数，目标为最小化设施开放成本和运输成本之和。为了有效求解该问题，提出了一种改进的差分进化算法，编码方式上采用实数编码策略，较为简单易于实现且能得到较好结果，进化过程采用多种变异算子并进行对比。对以往文献给出的算例采用5种变异算子进行测试，计算结果表明，DE/rand-to-best/1/bin变异算子最好，且所有算子都能得到较好结果，DE算法在软容量约束的设施选址问题上应用具有可行性。　

2、　关键词：物流设施选址问题；软容量约束；差分进化；实数编码　　中图分类号：F253.9文献标识码：A　　Abstract：Thispaperstudiesthesoft-capacitatedlogisticsfacilitylocationproblemthatiswidelyexistedinthedesignandmanagementoflogisticssystem.Theproblemistomakedecisionthateachcustomerdemandshouldbeservicedbywhichfacilityandtheopentimesf

3、oreachfacilitysoastominimizethesumoffacilityopeningcostandtransportationcost.Tosolvetheproblemefficiently，weproposedanimproveddifferentialevaluationalgorithm.Theproposedalgorithmusesarealnumbercodingstrategytoimplementeasily，andcomparesmultiplemutationoperatorsin5theevolutionaryproce

4、ss.Wetest5mutationoperatorsovertheinstancescollectedfromanexistingarticle.ThecomputationalresultsshowthattheDE/rand-to-best/1/binhasthebestmutationoperator，andallothermutationoperatorscanalsogetbettersolutionforsomeinstances.Thisverifiesthatitisfeasibletousedifferentialevaluationalgo

5、rithmtosolvethesoft-capacitatedlogisticsfacilitylocationproblem.　　Keywords：logisticsfacilitylocationproblem；soft-capacitated；differentialevaluation；realnumbercoding　　0引言　　设施选址问题是物流与供应链管理领域一类重要的组合优化问题，其在企业选址、网络设施及服务点的分布等众多方面都有应用。自1909年韦伯发表了关于设施选址问题的第一篇论文至今，该类问题备受众多研究者青睐。这一问题受到广泛关注是因为对

6、设施选址问题的研究存在着极为重要的实际意义。选址决策属于长期的，具有战略意义的决策，决策的好坏对于服务方式、服务质量、生产成本等方面都有很大的影响，通常一个较好的设施选址方案会很大程度减少不必要的费用，对一个企业而言，甚至还会极大、长久地影响到其生产经营、市场竞争力甚至企业的发展命运。从宏观而言，设施选址影响着经济、政治、文化、社会、生态各个方面，以及系统的运行效率。　　设施选址问题常被分为有容量约束的设施选址问题（CapacitatedFacilityLocation5Problem）、无容量约束的设施选址问题（Un-capacitatedFacilityLo

7、cationProblem）和软容量约束的设施选址问题（Soft-capacitatedFacilityLocationProblem）。目前对设施选址问题的研究已有一些不错的研究成果。如Guha&Khuller[1]将一维的无容量限制的设施选址问题推广至k维，并通过实验得到1.463的硬度近似比；Jainetal[2]的研究表明贪婪算法可以用于求解带惩罚的无容量约束设施选址问题且近似比为2；Charikar&Guha[3]将原始对偶方法与增强的贪心算法相结合得到近似比为1.853。　　本文主要研究了软容量约束的设施选址问题。软容量指的是在考虑设施提供服务的有限

8、性的同时，考虑到现实生活