基于协PSO算法的物流配送中心选址研究

摘要:针对多目标物流配送中心选址问题,建立选址模型,并设计离散协粒子群算法,最后利用该算法进行了实例研究,结果表明该算法是有效、可行的。

Abstract: To solve the problem of multiobjective location of logistics distribution centres, this paperestablished the model of location and designed the algorithm of discrete co-PSO, gavegiven an instance using this algorithm. The results indicated that the algorithm was effective and feasible.

关键词:协粒子群算法;配送中心;多目标优化

Key words: Particle Swarm Optimization(PSO);distribution center;multiobjective optimization

中图分类号:F25 文献标识码:A文章编号:1006-4311(2010)31-0021-02

0引言

物流配送中心作为连接供应商和客户之间的纽带,是从供应到消费过程中实现调节跟踪服务的主体机构[1],可以起到降低运作成本,提高物流流通效率等作用。配送中心的位置选择对于其运作成本和效率的高低起着至关重要的影响。目前对该问题国内外学者已经展开相关研究并取得一定的成果。常用的选址方法有多重心法、混合-整数线性规划法、目标规划法、树型搜索法、动态规划法等常规方法[2]以及目前兴起的智能算法,如遗传算法、蚁群算法、粒子群算法等,对于解决复杂选址问题具有独特优势[3,4]。

粒子群优化(PSO)算法[5,6]是基于群体智能理论的新型演化计算技术,具有通用性强、全局寻优、并行计算等优点,已经在复杂问题在连续空间和离散空间求最优解中获得广泛应用。本文提出一种基于协粒子群算法的选址算法,针对A市某连锁超市物流配送中心选址问题展开实例研究。

1问题描述

本文解决基于多级物流配送中的最底层配送中心的选址问题,即供应是由上级配送中心来统一,主要功能是满足单一区域内的各门店订货需求。其配送模式可以归纳为自营配送模式,即企业自建并承担所有费用,配送成本、服务质量是反映企业配送效率的两个最重要的指标,此外考虑到连锁企业总是随着城市的发展不断在数量上进行扩张,选址时必须具有前瞻性,即选址的动态性,影响选址评价指标的因素中既有定性因素,又有定量因素,各指标及因素间的递阶层次结构如图1所示。

2模型建立

本文假设:①已知客户的数量、需求量和位置;②已知若干个候选配送中心地址;③供应商和上级配送中心对各候选地址的运输成本基本一致;④不考虑配送中心的容量限制;⑤每个客户只由一个配送中心提供服务;⑥相同重量下单位距离运费相同,单位产品管理费用相同。选址问题可以描述为选择合理的地址建设配送中心,使得从这些配送中心向用户配送产品的运输成本和配送中心的建设成本之和最小,同时寻求整个系统的服务可靠度最大及所选中心具有良好的可持续发展性。

这里记客户集合记为N={1,2,…,n},候选地址集合记为M= {1,2,…,m},候选地址i(i∈M)与客户j(j∈N)之间的单位运输费用记为cij,dij为配送中心i与客户j之间的距离;候选地址i建设配送中心的固定费用记为fi。可设计m×(n+1)阶矩阵X。如果候选地址i建设配送中心,则xin+1=1,否则xin+1=0;如果候选地址i建设的配送中心服务于客户j,则xij=1,否则xij=0,则配送中心选址的多目标优化模型如下所示:

Min f(x)=wf(x)+w/f(x)+w/f(x)(1)

s.t. xxi∈M,j∈N(2)

xij=1 j∈N(3)

x∈0,1x∈0,1i∈M,j∈N(4)

其中:f1(x)=fx+qdcxij (5)

f(x)=(6)

w=1 0w1 k∈1,2,3 (7)

式(1)是目标函数,根据图1中的层次结构计算出各分目标的权重;式(2)表示若候选地址i没有建设配送中心,则不能为客户提供物流服务;式(3)表示每个客户只由一个配送中心提供服务;式(5)为成本函数,包括固定成本和运营成本,式(6)为服务质量函数,经过统计,服务质量可靠度与其他几个平行指标成正相关性,因此这里使用文献[7]中的服务可靠度来表示服务质量,其中,tj为客户j给定的送货时限;Vij为车辆从配送中心i至客户j的行驶速度;Fvij(•)为车辆从配送中心i至客户j的速度分布函数,车辆的行驶速度具有统计规律,其分布是车辆性能、道路性质与状况、交通状态及驾驶水平等随机因素综合作用的结果,一般具有正态分布或威布尔分布的特征[7] ,可以利用统计的方法对其进行标定;f3(x)为可持续性评价函数,以各候选地址在可持续性指标下的相对重要对大小来衡量,值大的表示可持续性较好。

3基于协PSO的模型求解

协进化PSO(CPSO)将种群分为多个部分,各个种群在独自进化的同时相互间交互和共享信息,实现经验共享,从而使整个系统协同进化,从而获得最优解。CPSO算法包含两类种群,一类种群包含M2个子种群S1,子种群规模均为M1,种群中每个微粒Ai则表示问题的一个决策解,该类种群用于进化决策解;另外一个种群S2规模为M2,其每个微粒Bj代表一组罚因子,用于计算S1中各微粒的罚函数值。算法流程如图2所示。

微粒的速度和位置更新根据自身和同伴的飞行经验,在微粒自身速度,自身最佳位置和群体最佳位置的相互作用下设计如下的离散位置更新公式:

X=cg(cg(f(X),pB),gB) (8)

其中,c1,c2均为0到1之间的数值,pB和gB分别为第k代进化时微粒的自身最佳位置和群体最佳位置,f(X)表示对X的第a分量与第b分量实施交换,a和b是微粒中随机的两个不同位置的分量,cg(f(X),pB)为微粒根据自身的最佳位置所作出的调整。首先产生0到1之间均匀分布的一个随机数ρ,如果ρ

cg(f(X),pB)=f(X),ρ

cg(f(X),pB)=f(X),ρc

其中函数g(X,pB)为微粒位置更新函数,更新规则为根据X,pB的适配值大小利用赌对各位置分量进行随机交换。cg(cg(f(X),pB),gB) 为微粒根据群体的最佳位置所作出的调整,调整规则同上。

4实例研究

A市现有某连锁店共有45家,包括购物广场、社区店、标准超市、便利店、好的便利店等五种业态,各分店的坐标相关数据如表1所示。

综合考虑各因素,在区域内筛选出四个物流配送中心备选方案,分别记为P1,P2,P3,P4,各方案的坐标分别为P1(-1600,-2500),P2(-2700,-2600),P3(2300,-400),P4(-2800,-500),客户要求的配送时限tj=8,配送车辆的速度Vij～N(50,120)。各备选中心的固定投资分别为表2所示。

利用AHP方法经过专家打分计算出的各因素相对多目标选址的权重值为w1=0.63,w2=0.21,w3=0.16且可持续性指标相同;CPSO算法中参数设置为:M1=50,M2=20,G1=25,G2=80,S1种群微粒的编码方式因不涉及到排序问题,设计为固定排序下对各位置向量的0,1操作,S2种群中微粒位置的最大值和最小值设置为1,max=2,max=1000,1,min=2,min=0。算法运行30次,与普通的PSO算法比较后结果为表3所示,结果表明此算法明显优于普通PSO算法。

经过结果分析,四个方案的优劣顺序为:P2,P3,P1,P4,且方案P2明显优于P1,P3,P4。所以选择P2(2700,-2600)作为A市物流配送中心的地址。

5结论

本文利用CPSO算法对物流配送中心选址问题展开实例研究,结果表明利用此算法可以有效应用于多目标物流配送中心选址中,选址涉及到多方面因素,本文只考虑了重点因素,紧密联系实际建立更加合理的数学模型,并利用多种优化算法展开比较研究将是以后的研究方向。

参考文献:

[1]丁浩,李电生.城市物流配送中心选址方法的研究.华中科技大学学报(城市科学版),2004,26(21):50-53.

[2]龚延成,郭晓汾,蔡团结等.物流配送点选址模型及其算法研究[J].中国公路学报,2003,16(2):123-126.

[3]郝栋梁,汝宜红,徐秀全.遗传算法在配送中心选址的应用[J].物流技术,2010.4:75-77

[4]郜振华.粒子群优化算法在配送中心连续性选址中的应用[J].计算机应用,2008,28(9):2401-2403.

[5]王凌,刘波.微粒群优化与调度算法[M].北京:清华大学出版社,2008.

[6]许珂,刘栋.多粒子群协同进化算法[J].计算机工程与应用,2009,45(3):51-54.

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