可持续发展理念下的配送中心选址模型及算法研究

汤希峰，丁俊武

(1.河海大学 土木与交通学院，江苏 南京　210098；2.扬州大学 信息工程学院，江苏 扬州　225127)



可持续发展理念下的配送中心选址模型及算法研究

汤希峰1，丁俊武2

(1.河海大学 土木与交通学院，江苏 南京210098；2.扬州大学 信息工程学院，江苏 扬州225127)

摘要：配送中心选址对物流运作产生重要影响.随着市场竞争的不断加剧、社会环保意识的不断增强，配送中心选址不仅仅需要考虑成本，还需要考虑服务水平、环境影响等因素.该文以FCLP模型为基础，建立了以物流成本最小化、服务可靠度最大化和CO2排放最小化为目标的配送中心选址模型，并运用NSGA-Ⅱ对模型进行了求解.算例分析表明，NSGA-Ⅱ算法不仅能够快速求得问题的Pareto最优解，而且与传统优化算法相比，得到的解也具有更优性.

关键词：可持续发展；配送中心选址；多目标；NSGA-Ⅱ；Pareto最优解

配送中心作为物流网络的一种重要节点，其选址对物流运作的效率、成本等产生着举足轻重的影响，因此一直是物流学研究的重点问题之一.传统的配送中心选址模型通常考虑的主要是物流成本，即是以物流成本最小化为目标[1].随着市场竞争的不断加剧、社会环保意识的不断增强，配送中心选址问题的研究正面临着新的挑战，不仅需要考虑物流成本，还须兼顾配送的服务水平、配送过程带来的环境影响等，也就是配送中心的选址应该能够最大程度地契合可持续发展的理念要求[2].

针对可持续发展理念下的配送中心选址问题，近年来国内外许多学者给予了高度关注，也取得了一定的研究成果.Harris等[3]以燃料消耗作为计算配送车辆CO2排放的基础参数，建立了以物流成本和碳排放最小化为目标配送中心选址模型；Chaabane等[4]以碳排放成本和物流成本最小化为目标，建立了配送中心选址的混合整数规划模型；汤希峰等[5-6]将服务可靠度作为配送服务水平的一种测度，以FCLP模型为基础建立了配送中心选址的多目标优化模型；以FCLP模型为基础，建立了以物流成本最小化、服务可靠度最大化以及CO2排放最小化为目标的配送中心选址模型.在这两篇文章中，主要是运用约束法和贪婪取走启发式算法等传统优化算法对所建模型进行了求解.与现代优化算法相比，传统的优化算法虽然能够求解所建的多目标选址模型，但往往需要决策者提供更多的信息，而且仅能得到较少的非劣解，大大限制了决策者的选择空间.为此，文章拟将后一篇文章所建的多目标选址模型作为基础，采用NSGA-Ⅱ算法进行求解，比较不同算法的求解结果，以期为选址决策提供更加有效的参考和支持.

1问题描述及建模

作为一种固定费用选址模型，FCLP模型一直是许多配送中心选址问题的重要基础模型，它是假定每个客户的需求量和位置已知、每个候选点的位置和建设成本已知，要求从候选点中选择若干个进行配送中心建设，使得配送中心的建设成本与从配送中心向客户配送产品的运输成本之和最小.在可持续发展的理念下，本文将服务可靠度作配送服务水平的一种测度，它是指配送车辆在规定的时间内将满足需求的产品及时送达客户的概率；此外，鉴于车辆在配送过程中产生的碳排放要比配送中心其它物流作业大得多，因而本文仅将配送车辆产生的CO2排放作为配送中心的环境影响指标.

若记：I为配送中心候选点集(i=1,2,…,I)；J为客户集(j=1,2,…,J)；fi为在候选点i建设配送中心的固定成本；hj为客户j的需求量；cij为候选点i到客户j的单位运输成本；dij为候选点i与客户j之间的距离；Fv(·)为配送车辆的速度分布函数；tj为客户j要求的配送时限；εvf为配送车辆满载时的碳排放系数；εve为配送车辆空载时的碳排放系数；w为配送车辆的标准载重；xi为决策变量；候选点i用于建设配送中心时取值为1，否则为0；yij为决策变量；候选点i为客户j提供配送服务时取值为1，否则为0.

则基于可持续发展理念的配送中心选址模型如下所示：

(1)

(2)

(3)

S.t.yij

(4)

(5)

(6)

(7)

其中：式(1)~(3)为目标函数，分别表示物流成本最小化、服务可靠度最大化和CO2排放量最小化；式(4)表示若候选点没有建设配送中心，则无法为客户提供服务；式(5)表示每个客户只能由一个配送中心提供服务；式(6)、(7)为数值约束.

2算法设计及求解

对于多目标优化问题，传统的优化算法一般是通过加权法或约束法将其转化为单目标优化问题进行求解，在转化过程中需要决策者提供部分目标函数的权重系数、取值约束等信息，而且针对给定的参数，往往只能得到的唯一的非劣解，只有通过不断地调整参数，才能得到一组或多组非劣解，不利于决策者的选择.相比而言，现代优化算法在求解多目标优化问题方面具有明显的优势，为此本文运用NSGA-Ⅱ算法，并对其适当改进以求解所建模型，算法的主要步骤如下：

1)初始化种群P0.随机生成N个用二进制编码的染色体，染色体中每个基因的取值表示候选点是否被选中，如“1”表示候选点被选中用于建设配送中心、“0”则表示候选点不被用于建设配送中心.

2)客户分配.针对每个染色体给出的选址方案，运用贪心法完成客户分配，即客户总是由距离其最近的配送中心提供服务.

3)目标函数评估.根据选址方案和分配方案，分别计算模型中的3个目标函数的值.

5)选取父辈.采用二进制锦标赛法，从初始种群中选取N/2个染色体用于产生后代，记为Ppool；选取父辈时，优先选择排序序号小的染色体，对于具有相同序号的染色体，则选择3个目标函数拥挤度之和最大的那个.

6)产生后代.运用交叉、变异等遗传操作生成下一代，具体包括：①从Ppool中随机选择两个染色体，采用单点交叉的方法产生下一代.②从Ppool随机选择一个染色体，采取二进制变异策略产生下一代，也就是将该染色体变异位的基因从“1”变成“0”或从“0”变成“1”.后代种群产生后，进行客户分配并计算目标函数值.

7)产生新种群.将产生的后代种群与初始种群合并，先进行非支配排序，再采用二进制锦标赛法从合并后的种群中选择N个染色体生成新的种群.选择时，同样优先选择排序序号小的染色体，对于具有相同序号的染色体，则选择3个目标函数拥挤度之和最大的.

8)循环执行步骤2)~7)直至满足预定的进化代数.

3算例求解及分析

为便于比较不同算法的求解结果，本文依然采用文献[6]中给出的算例：假定有10个候选点可供选建配送中心，记为F1,F2,…,F10，其建设成本如表1所示；有25个客户，记为C1,C2,…,C25，其需求量及其与候选点之间的距离如表2所示；候选点与客户之间的单位运输成本均为cij=1元/(t·km)；配送车辆为单一车型，标准载重为25t，满载时碳排放系数εvf=1.096kg/km，空载时碳排放系数εve=0.722kg/km，车速服从均值为80km/h、方差为10的正态分布；客户要求的送达时限均为2h.

表1　候选点的配送中心建设成本　元

表2　客户的需求量及其与候选点之间距离

在运用NSGA-Ⅱ算法求解所建模型时，初始种群的规模取为候选点数量的2倍，即N=20；交叉概率取Pc=0.9，变异概率取Pm=0.1；最大进化代数取200次.通过独立的运行程序20次，发现每次解的个数基本稳定在15个左右，且得到的解非常类似，表明NSGA-Ⅱ算法在求解多目标优化问题具有较好的收敛性和鲁棒性，这里任取其中一组，如图1所示.从图中不难看出，所建模型3个目标函数之间的冲突性，若单纯地追求物流成本最小化，往往会导致较低的服务可靠度和较高的CO2排放量，反之亦然.同时，也不难发现在Pareto前沿的中间区域可以找到问题的一些Pareto最优解.

另外，若将运用传统优化算法与NSGA-Ⅱ算法得到的解进行比较(如表3所示)，明显可以看出，一是NSGA-Ⅱ算法不需要决策者提供更多的信息就能得到很多的解可供决策者选择，从而使得决策者能够在不同目标之间进行充分权衡；二是NSGA-Ⅱ算法能够得到一些比传统优化算法得到的更优的解，这也充分说明对于求解多目标优化问题，现代优化算法比传统优化算法更具优势.

表3　传统优化算法与NSGA-Ⅱ算法求解结果对比

4结论

传统的配送中心选址模型通常以追求成本最小化为目标，随着市场竞争的不断加剧和环保意识的不断增强，配送中心选址问题的研究也亟需在可持续发展的理念下展开.本文将服务可靠度最大化、CO2排放量最小化作为目标实现对FCLP模型的有效拓展，并通过改进NSGA-Ⅱ算法实现对所建模型的顺利求解，算例分析充分表明以NSGA-Ⅱ为代表的现代优化算法在求解多目标优化问题方面比传统优化算法具有明显优势.

配送中心选址问题一直是物流学科研究的重点之一，可持续发展理念的导入又让该问题的研究面临新的机遇和挑战，本文正是在这个方向上的一次探索.以后研究可在以下几个方面进行拓展：1)本文提出的服务可靠度、碳排放的计算方法具有很好的可移植性，可以用于对Baumol-Wolfe、Kuehn-Hamburger等选址模型的改进；2)可以将FCLP这一基础模型从无能力约束拓展到有能力约束；3)选址决策过程严格来讲，不仅包括选址的决策还包括客户分配的决策，两者紧密相连又相互影响，本文在客户分配时采用的是贪心法，以后可以进一步考察不同的客户分配规则对选址决策的影响.

参考文献：

[1] DASKIN M S,SNYDER L V,BERGER R T.Facility location in supply chain design.In:Langeven A,Riopel D,ed.Logistics Systems:Design and Optimization[M].New York:Springer,2005:39-65.

[2] TEROUHID S A,RIES R,FARD M M.Towards sustainable facility location-a literature review[J].International Journal of Sustainable Development,2012,5(7):18-34.

[3] HARRIS I,NAIM M,PALMER A,et al.Accessing the impact of cost optimization based on infrastructure modelling on CO2emissions[J].International Journal of Production Economics,2011(131):313-321.

[4] CHAABANE A,RAMUDHIN A,PAQUET M.Design supply chain with sustainability consideration[J].Production Planning & Control,2011(22):727-741.

[5] 汤希峰,毛海军,李旭宏.物流配送中心选址的多目标优化模型[J].东南大学学报(自然科学版),2009,39(2):404-407.

[6] TANG X F,ZHANG J,XU P.A multi-objective optimization model for sustainable logistics facility location[J].Transportation Research Part D:Transport and Environment,2013,22(4):45-48.

[7] DEB K,AGRAWAL S,PRATAP A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation:NSGA-II[C]//International Conference on Parallel Problem Solving from Nature.Springer-Verlag,2000:849-858.

(编辑崔思荣)

Models and Algorithms for Locating Distribution Center in Consideration of Sustainability

TANG Xifeng1, DING Junwu2

(1.School of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China；2.Information Engineering College, Yangzhou University, Yangzhou 225127, China)

Abstract:Location decision of distribution centers has critical influence on logistics performance. Recent concerns regarding commercial competition and environmental pollution, gradually,are shifting the focus of modelling to incorporate not only economic cost but also service level and carbon emissions.Based on the FCLP,a location model which includes three objectives-logistics cost minimization,service reliability maximization and CO2 emissions minimization-is proposed.The NSGA-Ⅱ algorithm is adopted to solve the proposed model,and test results show that NSGA-Ⅱ algorithm can obtain Pareto optimal solutions efficiently and better performance notably in contrast with some traditional optimization techniques.

Key words:Sustainable development; distribution center location; multiple objectives; NSGA-Ⅱ; Pareto-optimal solution

中图分类号：F505

文献标志码：A

文章编号：1674-358X(2016)01-0048-05

作者简介：汤希峰(1980-)，男，博士，主要从事运输与物流工程研究.

收稿日期：2015-12-03