网站首页  词典首页

请输入您要查询的论文:

 

标题 软容量约束的物流设施选址问题的改进差分进化算法
范文 张新邦++邢航++李贵栋++汪恭书



摘 要:研究了广泛存在于物流系统设计与管理中的软容量约束的物流设施选址问题,主要决策每个客户需求由哪个设施服务以及每个设施开放的次数,目标为最小化设施开放成本和运输成本之和。为了有效求解该问题,提出了一种改进的差分进化算法,编码方式上采用实数编码策略,较为简单易于实现且能得到较好结果,进化过程采用多种变异算子并进行对比。对以往文献给出的算例采用5种变异算子进行测试,计算结果表明,DE/rand-to-best/1/bin变异算子最好,且所有算子都能得到较好结果,DE算法在软容量约束的设施选址问题上应用具有可行性。
关键词:物流设施选址问题;软容量约束;差分进化;实数编码
中图分类号:F253.9 文献标识码:A
Abstract: This paper studies the soft-capacitated logistics facility location problem that is widely existed in the design and management of logistics system. The problem is to make decision that each customer demand should be serviced by which facility and the open times for each facility so as to minimize the sum of facility opening cost and transportation cost. To solve the problem efficiently, we proposed an improved differential evaluation algorithm. The proposed algorithm uses a real number coding strategy to implement easily, and compares multiple mutation operators in the evolutionary process. We test 5 mutation operators over the instances collected from an existing article. The computational results show that the DE/rand-to-best/1/bin has the best mutation operator, and all other mutation operators can also get better solution for some instances. This verifies that it is feasible to use differential evaluation algorithm to solve the soft-capacitated logistics facility location problem.
Key words: logistics facility location problem; soft-capacitated; differential evaluation; real number coding
0 引 言
设施选址问题是物流与供应链管理领域一类重要的组合优化问题,其在企业选址、网络设施及服务点的分布等众多方面都有应用。自1909年韦伯发表了关于设施选址问题的第一篇论文至今,该类问题备受众多研究者青睐。这一问题受到广泛关注是因为对设施选址问题的研究存在着极为重要的实际意义。选址决策属于长期的,具有战略意义的决策,决策的好坏对于服务方式、服务质量、生产成本等方面都有很大的影响,通常一个较好的设施选址方案会很大程度减少不必要的费用,对一个企业而言,甚至还会极大、长久地影响到其生产经营、市场竞争力甚至企业的发展命运。从宏观而言,设施选址影响着经济、政治、文化、社会、生态各个方面,以及系统的运行效率。
设施选址问题常被分为有容量约束的设施选址问题(Capacitated Facility Location Problem)、无容量约束的设施选址问题(Un-capacitated Facility Location Problem)和软容量约束的设施选址问题(Soft-capacitated Facility Location Problem)。目前对设施选址问题的研究已有一些不错的研究成果。如Guha & Khuller[1]将一维的无容量限制的设施选址问题推广至k维,并通过实验得到1.463的硬度近似比;Jain et al[2]的研究表明贪婪算法可以用于求解带惩罚的无容量约束设施选址问题且近似比为2;Charikar & Guha[3]将原始对偶方法与增强的贪心算法相结合得到近似比为1.853。
本文主要研究了软容量约束的设施选址问题。软容量指的是在考虑设施提供服务的有限性的同时,考虑到现实生活中设施可以多次开设并支付费用来增加自身容量。该类问题的目标是使设施开设费用和连接费用之和的最小。对于此类问题,Arya et al[4]提出了一种局部搜索算法,得到了一个近似比为3.72的优化结果;Jain et al[5]的研究表明软容量近似比可以达到3。徐大川等[6]研究两阶段模型,考虑随机性与容错率,使用原始—对偶近似算法进行求解。Holmberg et al[7]针对有容量约束的设施选址问题,提出了最优化精确算法,可求得中小规模问题的最优解。
从目前的研究情况来看,运用近似算法来求解该类问题,虽然步骤简洁和计算复杂度低,但其优化结果较最优解还有较大距离。运用最优化算法来进行求解,虽然能得到最优解,但从最优化算法自身的特点来看,其无法解决大规模问题。目前有一种备受学术界关注的优化算法—智能优化算法,其能够在短时间内获得高质量解的优化算法,能从一定程度上弥补以上两种算法在求解该类问题时的缺点,且其不受问题结构的限制,是一种优化问题的较好选择。本文正是尝试运用目前一种较好的智能优化算法—差分进化算法来求解软容量约束的设施选址问题。
差分进化算法是1995年Storn和Price提出的一种仿生物进化的智能优化算法[8],近年由于其较好的鲁棒性与收敛性得到越来越多学者的关注。应用DE求解设施选址问题关键是对编码方法、变异和交叉过程等进行合理设计,使其得到较为理想的结果。
本文针对软容量约束的设施选址问题的特点,对差分进化算法编码、变异以及交叉过程进行设计,编码过程采用实数编码策略,改进了差分算子,并且对不同差分算子进行了比较,选择过程采用贪婪策略。通过实验可以看出,本文应用差分进化算法解决该类问题具有可行性。
4 结 论
本文研究了一类广泛存在于物流系统设计与管理中的软容量约束条件下的设施选址问题,建立了问题的混合整数规划模型,提出了收敛速度与鲁棒性较好的差分进化算法的求解方法,并通过实验对比了不同变异算子作用下的结果,验证了差分进化算法在此类问题上的可行性。
参考文献:
[1] Guha S, Khuller S. Greedy Strikes Back: Improved Facility Location Algorithms[J]. Journal of Algorithms, 1999,31(1):228-248.
[2] Jain K, Mahdian M, Markakis E, et al. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP[J]. Journal of the Acm, 2002,50(6):127-137.
[3] Charikar M, Guha S. Improved Combinatorial Algorithms for Facility Location Problems[J]. Foundations of Computer Science Annual Symposium on, 1999,34(4):378-388.
[4] Arya V, Garg N, Khandekar R, et al. Local Search Heuristics for k-median and Facility Location Problems[J]. Siam Journal on Computing, 2004,33(3):21-29.
[5] Jain K, Mahdian M, Saberi A. A New Greedy Approach for Facility Location Problems[C] // Proceedings of Annual Acm Symposium on the Theory of Computing, 2010:731-740.
[6] 徐大川,万玮,吴晨晨,等. 随机容错设施选址问题的原始—对偶近似算法[J]. 运筹学学报,2014,18(2):17-28.
[7] Holmberg K, Ronnqvist M, Yuan D. An exact algorithm for the capacitated facility location problems with single sourcing[J]. European Journal of Operational Research, 1999,113:544-559.
[8] Storn R, Price K V. Differential evolution: A simple and efficient adaptive scheme for global optimization over continuous spaces[J]. Journal of Global Optimization, 1995,23(4):341-359.
随便看

 

科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

 

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间:2025/1/4 22:23:41