多级物流节点选址问题建模与求解

*:为解决多级物流网络节点的选址问题,提出与现实中企业多元化经营范围相应的多级物流节点选址优化模型.该方法将物流节点选址问题转化为函数最小值求最优解问题;将多级网络按照节点层数分割成若干个3级规划模型;将每层的上一层级假设成供应商点,下一层级假设为客户点;用并行遗传算法,通过循环求解3级规划模型最优解,得出整个物流网络规划方案的最优决策.物流节点选址实例应用和仿真分析表明,该方法具有较强的可操作性和广泛的适用性,对优化物流节点以及类似设施选址具有一定的指导意义和参考价值.

Modeling and solving for locations of multi-level logistics network

HAN Hao, WANG Suling

(School of Transport & Communications, Shanghai Maritime Univ., Shanghai 200135, china)

Abstract:To solve the problem of locations for multi-level logistics network, an ptimization model for the locations of multi-level logistics network correspondent with the diversified scope of company is roposed. According to this method, selection of 韶关到晋城物流the locations is ransformed into finding the optimal solution of the minimum problem, nd multi-level network is divided into several three-layer planning modes ccording to the number of node layers. Each upper layer is assumed to be supplier’s site and the next layer is assumed to be customer’s site. The optimal solution of ntire logistics network is obtained by computing the optimal solution of the three-layer planning modes circularly using parallel genetic algorithm. pplication examples and simulation analysis show that the method has strong feasibility and extensive applicability, and it is of some guiding significance and reference value for the location selection optimization of logistics and other imilar facilities.

Key words:multi-level logistics network; location selection model; parallel genetic algorithm

0 引 言

随着现代物流功能及方式的不断进化,产品的物流过程逐步由从供应点到需求点的简单模式演变为从供应点到公共物流中心再到需求点的模式.物流节点是物流系统的重要组成部分,是商品进行周转、分拣、保管、在库管理、流通加工和信息处理的据点,能促进商品按顾客的要求进行流通、获得附加值以及克服物流过程中产生的时间和空间障碍.因此,合理选择物流节点位置,可降低供应链的流通成本,缩短运输路径,加快整个系统的反应速度,促进生产和消费的协调配合,进而促进周边企业乃至所在城市的发展.

现代物流节点选址的相关研究中,大多针对3层物流设施进行选址,而现实中企业往往多元化经营,物流网络结构也相应拉长,因此,基于标准3层物流设施选址在实际应用中存在不足.

[HJ*4/9]1 问题的提出

目前,国内外关于物流节点选址的研究主要分为定性分析和定量分析2大类.定性分析方法主要为层次分析法和模糊综合评价法相结合建立评价指标,并对各个方案进行评价,找出最优方案;定量分析方法主要包括重心法、运输规划法、Cluster法、CFLP法、Baumol-Wolf法、混合0-1整数规划法、双层规划法和遗传算法等.

虽然在定性和定量方面研究较多,但仍有不足:定性分析法考虑众多影响因素,通过对定性因素进行评测,可较全面、综合地对选址方案进行评比,但对其中需定量描述因素的分析较为薄弱,同时,大量的主观判断也会造成评价偏差较大;定量分析法中选址目标的确定多基于企业物流成本的最小化,未考虑物流中心的收益状况,这与企业更关注收益最大化的现实不符.在定性与定量结合进行综合分析方面,虽对设施选址的准确性和完备性相互补充,但由于仅是2种方法的简单叠加,无法克服其存在的根本缺陷,也难以贴近现实问题.[1]

遗传算法是20世纪美国Michigan大学的HOLLAND模仿自然界生物进化过程中“物竞天择,适者生存”的原理创立的1种多参数、多群体同时优化的方法.传统的遗传算法在诸多领域取得良好的效果,但在解决某些实际问题时,由于需要较多的个体数量和大量的计算,造成进化过程缓慢,且容易未成熟即收敛,难以满足实时性要求.其他定量分析法如整数规划法中的分支定界法,虽然计算相对简单,但在计算过程中需估算准确的权值,且耗费大量空间储存节点数据.

[HJ*5/9]并行遗传算法将计算机的高速并行性和遗传算法的天然并行性相结合,不仅提高求解速度,而且由于种群规模的扩大和各子种群的隔离,使种群的多样性得以保持和丰富,减少早熟的可能性,提高求解的质量,在实践中受到青睐.[2][HJ][LL]

基于物流节点选址通常需考虑设施服务能力、投资预算和生产能力等现实约束条件,构建有约束能力的物流设施选址模型.在实际中,物流节点的选址往往还涉及整个系统的效率、时间、服务水平、运输路网和环境污染等诸多因素,但系统总成本最低是物流节点规划的最根本要求.因此,本文建立费用最小模型,同时将并行遗传算法引入到物流节点选址模型的求解中.

2 模型的建立

物流节点选址属于最小化问题求最优解,即从若干备选节点中选出一定数目的节点,使其形成的物流网络运行费用最小.本文研究的是多级物流网络费用最小问题,可将多级网络按节点层数分割为若干3层规划模型,将每层的上一层级假设为供应商点,下一层级假设为客户点,通过循环求解3层规划模型的最优解,得到整个物流网络的最优决策.[3]

2.1 基本思想

设有a个供应商的商品经ni层物流节点运达b个客户.现拟从每层的ni个备选节点中选取若干个建立物流节点,使形成的物流网络总费用最小.其中,供应商的供应能力、客户的需求量及各节点的最大通过能力已知.多级物流网络结构示意见图1.[HT1.][HT]图1 多级物流网络结构示意

求解物流网络最小成本问题,即求解使运输成本、存储成本和建设成本之和最小的最优解.[4]为简化问题和模型,作如下假设:

(1)供应商的供货能力总能满足客户需求;

(2)每个客户的需求必须得到满足,且只能由1个物流节点进行满足;

(3)各物流节点的发货量与进货量保持平衡.

2.2 模型的建立

模型总费用目标函数为おИmin f=[ZK(]α[DD(]N-1n=1[DD)][DD(]Hn+1j=1[DD)][DD(]Hni=1[DD)]PijnEijn+β[DD(]N-1n=2[DD)][DD(]Hni=1[DD)]AinZ(Fin)+

β[DD(]N-1n=2[DD)][DD(]Hni=1[DD)]Bin(Fin)│泉+吉[DD(]N-1n珠海到阿勒泰物流=2[DD)][DD(]Hni=1[DD)]XinIin[ZK)][JY](1)お[HJ]式中:И[DD(]N-1n=1[DD)][DD(]Hn+1j=1[DD)][DD(]Hni=1[DD)]PijnEijn为运输成本;И[DD(]N-1n=2[DD)][DD(]Hni=1[DD)]A汕头到山东物流inZ(Fin)为固定存储费用;И[DD(]N-1n=2[DD)][DD(]Hni=1[DD)]Bin(Fin)θ为变动存储费用,θ与物流节点规模有关,通常取0.5[4];И[DD(]N-1n=2[DD)][DD(]Hni=1[DD)]XinIin为建设费用.

约束条件如下:ИFin≤Vin,i,n(2)

[DD(]Hni=1[DD)]Xin≤Mn,1≤n≤N-1[JY](3)

Fin=Fin-1Yin-1,i,n[JY](4)

Ein=FinYin,i,n[JY](5)

[DD(]Hn-1j=1[DD)]Ejin-1=[DD(]Hnj=1[DD)]Eijn,n,i[JY](6)

di≥0,i[JY](7)

Eijn≥0,i,j,n[JY](8)

Fin≥0,i,n[JY](9)

Vin≥0,i,n[JY](10)ИXin=(11)

Yijn=1, 若第n层上的节点i对于产品的

[KG*2][KG*2]需求由第n+1层上的节点满足

0, 否则(12)ИZ(x)=3 并行遗传算法设计

遗传算法通过对生物遗传和进化过程中的选择、交叉和变异机理的模仿,完成对问题最优解的自适应搜索过程;基本遗传算法只使用选择算子、交叉算子和变异算子等3种基本遗传算子,遗传进化过程较简单;并行遗传算法从以下4种并行性方面[5]进行改进和发展:

[HJ*5/9](1)个体适应度评价的并行性;

(2)整体群体中各个个体适应度评价的并行性;

(3)子代群体产生过程的并行性;

(4)基于群体分组的并行性.

所谓并行性,即对群体按一定的方式进行分组,分组后的单一或1组个体的遗传进化过程可在不同的处理机上独立进行.在适当的时候,各处理机之间以适当的方式交换一些信息,即不同个体或不同组个体的遗传进化过程并行进行.

3.1 并行遗传算法原理

将种群进行划分,目前比较成熟的分类方法为聚类分析法.对不同种群采用不同的方法进行初始化,在各个群体进行一定代数的独立进化后,分别从各个种群中选取一部分适应度高的个体,放到其他种群中进行不断的优化迭代,当计算结果满足一定条件后即停止计算.[6]并行遗传算法流程见图2.[HJ]

[HT1.][HT]图2 并行遗传算法流程[LL]3.2 编码方案

对模型中的决策变量进行分析,zd表示是否选中该备选节点,因此,宜采用二进制编码.对n个备选节点,取n个二进制作为染色体长度,每个基因赋值0或1,1表示该节点被选择,0表示该节点未被选择.

3.3 初始群体设定

选取聚类类别数k,┯锚C-均值聚类法对1个大种群进行分类,从备选集合中任取k个点作为聚类中心,将每个样本点按欧式距离‖xl-ci‖=‖xl-xj‖归入中心为Ci的类中,重新调整聚类中心,直到聚类中心不再变化,得m个独立的小种群,然后从每类随机选择1个节点,保证每类节点中至多有1个被选中.[7]

3.4 适应度函数设计

如何确定要交换的个体,是并行遗传算法的1个关键,直接影响到群体进化速度及优良程度.遗传算法中适应函数值越大越好,但在配送中心选址问题中要求解最小值,因此,可建立适应度函数Иg(X,Z)=C┆max-f(X,Z)[JY](14)И式中:C┆max为f(X,Z)的最大估计值.

3.5 计算步骤

在遗传算法中,子群体中的个体按照一定比例随机进行寻优操作,为保持进化的稳定性,同时加快进化速度,遗传算子β的取值应随进化代数的变化而不同,设ИЕ=θ1+(θ2-θ1)×t/T┆max(15)И式中:θ为比例因数,θ∈(θ1,θ2);t为当前进化代数;T┆max为最大进化代数.

具体步骤如下:

(1)初始化.设初始遗传代数t=0,按照实数编码方式在解空间中随机产生初始群体P(t)(其大小为N),┌椽C-均值聚类法将P(t)等分为m个子种群ИP(t)={P1(t),P2(t),…,Pm(t)}.И(2)复制、变异、交叉.对m个子种群Pi(t)(i=1,2,…,m)分别独立进化,计算Pi(t)中个体的适应[LL]度函数值,并按由大到小的顺序排序.

①根据式(15)计算θ,令S=floor(N×θ),S>n,floor()为取整运算,n为随机数;

②排在前面的n个个体直接复制到P′[KG-*2]i(t);

③从Pi(t)中取出第n+1到S之间的1个个体,与排在前面的n个个体组成n+1个节点,利用随机算法算出1个新点;依次取出1个个体,算出1个新点,直到算出S-n个新的个体到P′[KG-*2]i(t);

④采用比例选择法,从Pi(t)中挑选出N/m个个体到P″[KG-*2]i(t);

⑤采用算数交叉方法,以一定的交叉概率对[JP3]P″[KG-*2]i(t)中的个体进行交叉操作,得新的个体到P″[KG-*2]i(t);

[JP3]⑥采用高斯变异[8]方法,以一定的变异概率对P″[KG-*2]i(t)中的个体进行变异操作,得到新的子种群P′[KG-*2]i(t).

(3)计算适应度、筛选.分组计算P′[KG-*2]i(t)(i=1,2,…,m)中个体的适应度值;

(4)遗传.根据星型迁移模型[9]的信息交换模型,对各Pi(t)之间进行信息交换,得下一代群体;

(5)结果输出.用终止条件判断,若满足终止条件,则输出优化结果,否则转到步骤(2).考虑到并行遗[HJ*4/9]传算法本身具有很好的收敛性,为缩短计算时间,取最大进化代数为终止条件,即计算一定次数后返回最优值.

4 案例分析及仿真

为说明该算法的实际应用,可代表性地选取4层级物流网络进行演算.多于4层级的案例算法与此类似,仅需增加循环计算次数.

某大型生产企业因业务发展需要,计划在全国范围内建立多个配送中心,配送其生产的20多种商品,服务30个重要客户,其中:1级配送中心最多2个,2级配送中心最多4个.经初步考察,现有10个地点可供选择,其中:1级配送中心可选地4个,2级配送中心可选地6个,规划年限为5 a,利率γ=0.05,运输费用权重因数α=1,库存费用权重因数β=1,所建物流网络能满足所有用户的随机需求,基本数据见表1,[WTBZ]客户对商品的需求量见表2,运输费率见表3.[HJ][SD38*2]表1

备选地点基本数据待选设施1级备选点2级备选点1234123456建设费用/元18 10013 50026 40014 10013 00029 80028 50025 60010 00015 100通过能力/t3 6004 0804 9272 8403 6804 1504 8103 2004 6204 000可变存储费/(元•t-1)815988128867910413910377固定存储费/(元•t-1)1 5351 7632 4302 3012 9262 2971 6002 6932 9221 767

表2

客户对商品的需求量[JZ)][JY,1]t客户需求量1147295313241185113客户需求量61357116890912810143客户需求量119912971392141181572客户需求量169217146181241913720108客户需求量21772210323532413625102客户需求量26120279828129299830119注:因该企业的主要产品性质相差不大,对运输与仓储条件的要求基本相同,故不再细分每种商品的需求.

可见,使用此模型结合并行遗传算法可准确地选择备选节点,并快速得出最优解,使整个网络的物流成本最小.本文模型采用并行遗传算法求解,最优[HJ*5/9]结果收敛于860 110,可见,本文建立的费用最小模型具有较好的实用性.

5 结 论

本文在物流节点选址问题中引入并行遗传算法,将物流节点划分为几个子群体,各个子群体独立进行简单遗传算法的进化操作,在适当的时候,各个子群体间相互交换信息,从全局角度开发群体进化的并行性,有效提高遗传算法的运行速度,并且保持各处子群体进化的局部特征,[JP2]有效回避遗传算法的早熟现象.与常用的分支定界法相比,无需估算各节点权值,也无需存储许多叶子节点和对应的耗费矩阵,提高计算结果的准确性,也节省一定的内存空间.[JP]

物流节点选址问题是个混合的整数规划问题,各约束条件既相互联系又相互制约,给求解带来难度.本文建立的一般选址问题通用数学模型,运用并行遗传算法在求解过程中逐步优化,并通过实例进行论证,为今后的物流节点选址优化问题的研究提供参考.[HJ]