有容量约束的随机多目标LIP模型及其求解算法

周愉峰,李 志

(重庆工商大学重庆市发展信息管理工程技术研究中心,重庆400067)

有容量约束的随机多目标LIP模型及其求解算法

周愉峰,李 志

(重庆工商大学重庆市发展信息管理工程技术研究中心,重庆400067)

针对某些特殊物资的物流网络设计问题,以系统总成本最小与系统实时性程度最高为目标,建立一个考虑随机需求、设施容量约束、客户时限约束、带提前期的选址-库存问题(LIP)模型。该模型被描述为一个双目标的非线性离散混合整数规划模型。针对该模型,基于小生境技术设计一种改进的非支配排序多目标遗传算法Π (NSGAΠ),以丰富非支配解的数量。算例与对照实验结果表明,NAGAΠ可得模型的Pateto前沿解集,与标准NSGAII相比具有明显的优势,该模型及算法可应用于血站或者某些应急药品仓库的选址布局与库存决策。决策者可根据实际需要及偏好在一簇Pateto解中选择合适的优化决策方案。

选址-库存问题;设施选址;库存控制;多目标优化;非支配排序遗传算法Π;混合整数规划

1 概述

选址-库存问题(Location-inventory Problem, LIP)将选址与库存整合起来进行决策以促进物流系统的优化。这一问题引起了研究者们的广泛关注。如文献［1-2］考虑集中库存带来的风险分担效应,基于非线性混合整数规划方法建立了一个随机需求下的分销中心LIP模型,并提出一种基于拉格朗日松弛与次梯度方法的启发式算法。文献［3］研究了考虑提前期与安全库存的单产品两阶段分销网络LIP。此外,部分文献也研究了不同背景下的LIP［4-6］。但这些文献均以系统成本最优为目标,研究的是单目标决策问题,没有考虑物流系统的服务及时性,设计的算法均针对的是单目标LIP［7-9］。

事实上,随着物流系统的发展,客户日益关注物流服务的效率,物流系统服务及时性目标的重要度日益凸显。在某些特殊物资的物流网络设计中,除了传统的成本目标,也必须着重考虑需求地的时限约束以及系统的整体及时性目标。例如,血液、某些应急药品的供应关系到人们的生命健康安全。因此,在血站及应急药品储备仓库的布局与库存体系设计时,就需要特别重视系统提供服务的及时度。但罕有文献研究了同时考虑系统成本与系统及时性目标的多目标LIP及其算法。尽管文献［10］建立了以调配时效和调配可靠性最大化为目标的血液储备库选址模型,但该文献没有集成库存决策,且设计的多目标算法是基于目标加权的方法,不能得到问题的Pareto前沿解集。

鉴于此,本文以系统总成本与系统及时性为目标,建立一个考虑随机需求、设施容量约束、客户时限约束、带提前期的物流网络离散LIP模型。设计一种改进的基于小生境技术的非支配排序遗传算法Π (No-dominated Sort Genetic Algorithm II, NSGAII),并与标准NSGAII进行比较,分析改进算法的性能。算法在得到Pareto前沿的同时,决策者可根据偏好与需要权衡预算与物资保障效果,在Pareto前沿面上给出各种优化决策方案。

2 有容量约束的随机LIP模型

2.1 问题描述

考虑由1个供应点、多个候选设施、多个客户构成的三级物流系统。系统中,候选设施点与客户处于同一区域内,其地理位置已知。供应点处于区域外,距离各个候选设施的距离既定。客户需求随机且有时限约束。候选设施有容量约束。系统设计在考虑运输成本、开放设施库存成本等费用因素的同时,也要求考虑客户需求的时限约束及整个物流系统的及时性因素。要解决的问题是:设施应该定位在哪里;需采取什么样的订货策略;已选设施如何在客户之间进行指派。基于上述分析,问题可被描述为一个有容量约束,考虑随机需求、时限约束、设施库存、带提前期的随机双目标设施选址-库存集成决策问题。

2.2 开放设施库存成本分析

以i表示客户下标,j表示候选设施点下标,不失一般性,假设客户需求独立同正态分布 N(μi,)。因此,服务客户的开放设施需求也满足正态分布N(μj,),假设开放设施采用连续性盘点的(S, s)库存策略［11］,则:

则提前期L内开放设施的需求量服从正态分布N(Lμj,L)。

开放设施的日常库存控制参数可以表示如下:

安全库存:

其中,zj是库存服务水平系数。

订货点:

订货量:

平均库存:

其中:

在式(7)中,TPj为j地2次连续订购的时间间隔。

开放设施的日常周转库存成本可以表示为:

在式(8)中,hj为单位库存持有成本;ocj为j地的单位订购成本;rcj为工厂至设施的单位运输成本。

2.3 数学模型

模型中需使用的符号和变量定义如下:

(1)参数

J:候选设施点集,j=1,2,…,n,j∈J。

I:客户集,i=1,2,…,m,i∈I。

fj:设施j的年固定设置成本。

dij:客户i到设施j=1,2,…,n的距离。

cij:客户i到设施j=1,2,…,n的单位运输成本,用两地间的距离乘单位运输成本表示。

tij:客户i到设施j=1,2,…,n的单位需求运输时间,tij=dij/v,v为运输工具的行驶速度。

Ti:客户i的时限约束参数,Ti越小表示客户i对物资供给的时效性要求越高。在现实中,可根据客户规模、性质、偏好等因素来设置不同的时限约束参数。

χ:年平均天数,用于将日需求和方差转化为年平均值。

capj:候选设施j的容量。

(2)决策变量

Xj:j处设施开放时为1,否则为0,j∈J。

Yij:设施j被指派给客户i时为1,否则为0,i∈I,j∈J。

Sj:设施j的库存定至点,j∈J。

建立的有容量约束随机多目标LIP模型表示如下:

目标函数式(9)表示系统总成本最小,其中第1项为开放设施的固定设置成本;第2项为库存持有成本;第3项为固定订购成本;第4项为设施至客户的运输成本;第5项为工厂至设施的运输成本,第2项、第3项、第5项3项成本构成了开放设施的日常周转库存。式(10)表示系统的及时性程度最高。式(11)、式(12)表示开放设施的需求均值与方差。约束式(13)表示每个客户仅指派给1个开放设施。约束式(14)为开放设施的容量约束。约束式(15)为客户的时限性约束。式(16)、式(17)为0-1整数性约束。

对目标函数式(9)中的Sj求导,令∂TC/∂Sj=0,可得:

则目标函数式(9)可以转化为式(19)。

3 改进的非支配排序多目标遗传算法

上述模型为非线性离散混合整数规划模型,属于NP-hard问题。在此采用具有良好鲁棒性和隐含并行特性的遗传算法对其进行求解。本文设计一种采用整数编码的改进非支配排序遗传算法(NSGAII),算法流程如图1所示。

图1 改进的非支配排序遗传算法流程

3.1 染色体编码/解码

模型要解决的问题是:(1)开放设施的定位; (2)开放设施在客户之间的指派;(3)开放设施库存定至点的确定。库存定至点可根据式(18)、式(19)计算。而开放设施与客户之间的指派关系Yij确定后,相应的选址决策Xj也可确定。因此,采用整数编码策略,若有m个客户,n个候选设施点,则令每条染色体上的基因位数为m,每个基因在1～n的整数内产生,用于表示客户点的指派关系。假设16个客户由8个开放设施进行服务。图2表示:选择开放第1个、第2个、第4个、第8个候选设施,客户1、客户2、客户4、客户7、客户12由设施2服务,客户3、客户5、客户6、客户8、客户13、客户16由设施1服务……

图2 染色体编码示例

3.2 非支配解排序

适应度评价后,即可对目标函数值TC和TT进行非支配解排序。

上述非支配解排序的算法流程如下［8］:

Step 1 令i表示前沿面,初始化i=1。令Sp=φ,表示由染色体p支配的所有染色体集合;令np= 0,表示染色体p支配其他染色体的数量;令Fi=φ,表示第i前沿面染色体集合。

Step 2 对种群中的每一条染色体q,若p支配q,则Sp=Sp∪{q};若q支配p,则np=np+1。

Step 3 若np=0,表示没有个体支配染色体p,则p为种群中的最优个体,属于第1前沿面,令其秩prank=1,更新第1前沿面集合,即F1=F1∪{p}。

Step 4 若Fi≠φ,则令Q=φ,用于存储第i+1前沿面对应的染色体,否则算法结束。

Step 5 遍历前沿面集合Fi中每一条染色体p,对于集合Sp中每一条染色体q,令nq=nq-1。若nq=0,表示在接下来的前沿面中没有任何个体支配q,则令qrank=i+1,Q=Q∪{q}。

Step 6 令i=i+1,Fi=Q,返回Step4。

3.3 小生境技术

生物学上把小生境定义为具有共同特性的组织或物种。在标准遗传算法操作中,具有高适应度值的个体有更大的生存概率,当某个个体的适应值大大高于种群的平均适应值时,它在种群中的数量会急剧增加甚至支配整个种群。该状态一旦产生,通过交叉操作难以生成新的个体,而偶尔的随机变异不能保证很快跳出这种状态,从而导致搜索过程徘徊不前,产生早熟收敛现象。为了克服这一缺点,设计一种基于小生境技术的改进遗传算法。小生境技术通过计算染色体周围的拥挤程度来计算适应度的降低程度以保证算法的多样性,其计算流程如下［12-13］:

Step 1 对任意前沿面Fi,设其有p个个体,初始化Fi(dj)=0,其中,j表示Fi中的第j个个体。

Step 2 针对每一个目标,基于该目标对前沿面Fi进行排序,S=sort(Fi,z)为排序结果。对小生境边界的个体赋予最大距离值,即I(d1)=∞,I(dp)=∞。

3.4 遗传操作

采用锦标淘汰赛对染色体进行选择操作,采用单点交叉和互换变异操作。

3.5 终止条件

当遗传算法迭代代数达到最大时,算法终止并输出结果。

4 算例与分析

在100×100的坐标平面内产生40个随机节点:包括30个客户点及10个候选设施点。客户相关参数见表1,候选设施相关参数见表2。

表1 客户相关参数

表2 候选设施相关参数

年平均天数χ=1,单位库存持有成本h=2元,单次订货成本oc=10元,工厂至设施的单位运输成本rc=120元,提前期L=1天,客户时限约束T=3,库存服务水平因子zj=1.96(95%的置信概率)［9］。

(1)实验结果

改进 NSGAII参数设置:种群规模popsize= 400,最大迭代代数maxgen=800,交叉概率pc= 0.9,变异概率pm=0.05［13］。采用Matlab语言编程实现上述算法,运行平台为 Intel(R)Core(TM) 2 Duo CPU T5470@1.60GHz,3GB内存, Windows 7操作系统的PC机。运行31.21 min,得到71个Pareto解,模型的部分运行结果见表3,Pareto最优解前沿见图3。

表3 改进NSGAII部分运行结果

图3 2种算法的Pareto前沿面对比

(2)对照实验

为了验证所提改进NSGAII的性能,构建3组算例,与标准NSGAII的运行结果进行对比分析,如表4所示。其中,20×10,10×10算例中所用客户数据分别为30×10算例中的前20个、前10个客户数据。结果表明,标准NSGAII与改进NSGAII均能有效得出模型的Pareto前沿解集。但改进NSGAII能得到数量更为丰富的Pareto候选解,且解的分布更为均匀;而在计算时间上,两者的效率相当。因此,与标准NSGAII相比,本文提出的改进算法具有明显的优势。

表4 标准NSGAII与改进NSGAII的运行情况对比

5 结束语

本文研究了一类有容量约束的随机多目标LIP,并设计了一种改进的NSGAII对问题进行求解。算例表明:算法可得模型的 Pateto前沿解集;改进NSGAII与标准NSGAII相比具有明显优势。该模型及算法可应用于血站或者某些应急药品仓库的选址布局与库存决策,决策者可根据实际需要在一簇Pateto解中选择合适的优化决策方案。下一步研究可以考虑建立多供应点、多候选设施与客户点的三级或者三级以上物流网络LIP;或者引入可靠性因素,研究考虑系统安全性目标的LIP;也可集成路径决策,研究相同背景下的选址-库存-路径问题。

［1］ Miranda P A,Garrido R A.Incorporating Inventory Control Decisions into a Strategic Distribution Network Design ModelwithStochasticDemand［J］.Transportation Research Part E,2004,(40):183-207.

［2］ Miranda P A,Garrido R A.A Simultaneous Inventory Control and Facility Location Modelwith Stochastic Capacity Constraints［J］.Networks and Spatial Economics, 2006,(6):39-53.

［3］ Sourirajan K,Ozsen L,Uzsoy R.A Genetic Algorithm for a Single Product Network Design Model with Lead Time and Safety Stock Considerations［J］.European Journal of Operational Research,2009,197:599-608.

［4］ Daskin M S, Shen Zuojun.An Inventory-location Model: Formulation, Solution Algorithm and ComputationalResults［J］.Annals of Operations Research,2002,110(1/4):83-106.

［5］ Shen Zuojun,QiLian.Incorporating Inventory and Routing Costsin Strategic Location Models［J］.European Journal of Operational Research,2007,179: 372-389.

［6］ Shen Zuojun,Coullard C,Daskin M.A Joint Locationinventory Model［J］.Transportation Science,2003, 37(1):40-55.

［7］ Yao Zhishuang,Lee L H,Jaruphongsa W,et al.Multisource Facility Location-allocation and Inventory Problem［J］.European Journal of Operational Research, 2010,207:750-762.

［8］ Liu Kaijun,Zhou Yonghong,Zhang Zigang.Capacitated Location Model with Online Demand Pooling in a MultichannelSupply Chain［J］.European Journalof Operational Research,2010,207:1016-1030.

［9］ Nozick L K,Turnquist M A.A Two-echelon Inventory Allocation and Distribution Center Location Analysis［J］.Transportation Research Part E:Logistics and Transportation Review,2001,37(6):425-441.

［10］ 孟 超.非常规突发事件应急血液战略储备保障模式研究［D］.成都:西南交通大学,2010.

［11］ Daskin M S,Coullard C R,Shen Zuojun.An Inventorylocation Model:Formulation,Solution Algorithm and ComputationalResults［J］.Annals of Operations Research,2002,110(1-4):83-106.

［12］ 林 焰,郝聚民.隔离小生境遗传算法研究［J］.系统工程学报,2000,15(1):86-91.

［13］ 李双琳,马祖军,郑 斌,等.震后初期应急物资配送的模糊多目标选址-多式联运问题［J］.中国管理科学,2012,21(2):144-152.

编辑 顾逸斐

Stochastic Multi-objective LIP Model with Capacity Constraint and Its Solving Algorithm

ZHOU Yufeng,LI Zhi
(Chongqing Engineering Technology Research Center for Information Management in Development, Chongqing Technology and Business University,Chongqing 400067,China)

Based on the characteristics of logistic network design problem of some special materials,a joint Locationinventory Problem(LIP)model with lead-time is built,considering stochastic demands,facility capacity constraints and the client time constraints.The goal is to minimize system cost and maximize system timeliness.A discrete nonlinear mixed integer programming model with 2 goals is built to describe the problem.An improved NSGAII based on niching technology is worked out to solve the model,in order to enrich the number of non-dominated solutions.Numerical example and control experiment indicate that the Pateto front solution set can be obtained and the improved NSGAII has obvious advantages compared with standard NSGAII.The model and algorithm can be used to make location and inventory decision of blood banks or other emergency medicine warehouses.And optimal decision schemes can be selected from a cluster of Pateto solutions according to the preferences and actual needs of decision makers.

Location-inventory Problem(LIP);facility location;inventory control;multi-objective optimization;Nodominated Sort Genetic Algorithm II(NSGAII);mixed integer programming

1000-3428(2014)11-0183-06

A

TP399

10.3969/j.issn.1000-3428.2014.11.036

国家科技支撑计划基金资助重大项目(2006BAH02A20);国家社会科学基金资助项目(10XGL013);重庆市科技攻关计划基金资助重大项目(CSTC2012ggC00002);重庆市科技攻关计划基金资助重点项目(CSTC,2010AB2102,CSTC,2008AB2084)。

周愉峰(1984-),男,博士研究生,主研方向:物流系统优化,物流网络设计;李 志(通讯作者),教授。

2013-11-18

2014-01-01E-mail:xtuzyf@qq.com

中文引用格式:周愉峰,李 志.有容量约束的随机多目标LIP模型及其求解算法［J］.计算机工程,2014,40(11):183-188.

英文引用格式:Zhou Yufeng,Li Zhi.Stochastic Multi-objective LIP Model with Capacity Constraint and Its Solving Algorithm［J］.Computer Engineering,2014,40(11):183-188.