周愉峰,李 志

(重慶工商大學重慶市發(fā)展信息管理工程技術(shù)研究中心,重慶400067)

有容量約束的隨機多目標LIP模型及其求解算法

周愉峰,李 志

(重慶工商大學重慶市發(fā)展信息管理工程技術(shù)研究中心,重慶400067)

針對某些特殊物資的物流網(wǎng)絡(luò)設(shè)計問題,以系統(tǒng)總成本最小與系統(tǒng)實時性程度最高為目標,建立一個考慮隨機需求、設(shè)施容量約束、客戶時限約束、帶提前期的選址-庫存問題(LIP)模型。該模型被描述為一個雙目標的非線性離散混合整數(shù)規(guī)劃模型。針對該模型,基于小生境技術(shù)設(shè)計一種改進的非支配排序多目標遺傳算法Π (NSGAΠ),以豐富非支配解的數(shù)量。算例與對照實驗結(jié)果表明,NAGAΠ可得模型的Pateto前沿解集,與標準NSGAII相比具有明顯的優(yōu)勢,該模型及算法可應(yīng)用于血站或者某些應(yīng)急藥品倉庫的選址布局與庫存決策。決策者可根據(jù)實際需要及偏好在一簇Pateto解中選擇合適的優(yōu)化決策方案。

選址-庫存問題;設(shè)施選址;庫存控制;多目標優(yōu)化;非支配排序遺傳算法Π;混合整數(shù)規(guī)劃

1 概述

選址-庫存問題(Location-inventory Problem, LIP)將選址與庫存整合起來進行決策以促進物流系統(tǒng)的優(yōu)化。這一問題引起了研究者們的廣泛關(guān)注。如文獻［1-2］考慮集中庫存帶來的風險分擔效應(yīng),基于非線性混合整數(shù)規(guī)劃方法建立了一個隨機需求下的分銷中心LIP模型,并提出一種基于拉格朗日松弛與次梯度方法的啟發(fā)式算法。文獻［3］研究了考慮提前期與安全庫存的單產(chǎn)品兩階段分銷網(wǎng)絡(luò)LIP。此外,部分文獻也研究了不同背景下的LIP［4-6］。但這些文獻均以系統(tǒng)成本最優(yōu)為目標,研究的是單目標決策問題,沒有考慮物流系統(tǒng)的服務(wù)及時性,設(shè)計的算法均針對的是單目標LIP［7-9］。

事實上,隨著物流系統(tǒng)的發(fā)展,客戶日益關(guān)注物流服務(wù)的效率,物流系統(tǒng)服務(wù)及時性目標的重要度日益凸顯。在某些特殊物資的物流網(wǎng)絡(luò)設(shè)計中,除了傳統(tǒng)的成本目標,也必須著重考慮需求地的時限約束以及系統(tǒng)的整體及時性目標。例如,血液、某些應(yīng)急藥品的供應(yīng)關(guān)系到人們的生命健康安全。因此,在血站及應(yīng)急藥品儲備倉庫的布局與庫存體系設(shè)計時,就需要特別重視系統(tǒng)提供服務(wù)的及時度。但罕有文獻研究了同時考慮系統(tǒng)成本與系統(tǒng)及時性目標的多目標LIP及其算法。盡管文獻［10］建立了以調(diào)配時效和調(diào)配可靠性最大化為目標的血液儲備庫選址模型,但該文獻沒有集成庫存決策,且設(shè)計的多目標算法是基于目標加權(quán)的方法,不能得到問題的Pareto前沿解集。

鑒于此,本文以系統(tǒng)總成本與系統(tǒng)及時性為目標,建立一個考慮隨機需求、設(shè)施容量約束、客戶時限約束、帶提前期的物流網(wǎng)絡(luò)離散LIP模型。設(shè)計一種改進的基于小生境技術(shù)的非支配排序遺傳算法Π (No-dominated Sort Genetic Algorithm II, NSGAII),并與標準NSGAII進行比較,分析改進算法的性能。算法在得到Pareto前沿的同時,決策者可根據(jù)偏好與需要權(quán)衡預算與物資保障效果,在Pareto前沿面上給出各種優(yōu)化決策方案。

2 有容量約束的隨機LIP模型

2.1 問題描述

考慮由1個供應(yīng)點、多個候選設(shè)施、多個客戶構(gòu)成的三級物流系統(tǒng)。系統(tǒng)中,候選設(shè)施點與客戶處于同一區(qū)域內(nèi),其地理位置已知。供應(yīng)點處于區(qū)域外,距離各個候選設(shè)施的距離既定。客戶需求隨機且有時限約束。候選設(shè)施有容量約束。系統(tǒng)設(shè)計在考慮運輸成本、開放設(shè)施庫存成本等費用因素的同時,也要求考慮客戶需求的時限約束及整個物流系統(tǒng)的及時性因素。要解決的問題是:設(shè)施應(yīng)該定位在哪里;需采取什么樣的訂貨策略;已選設(shè)施如何在客戶之間進行指派?；谏鲜龇治?問題可被描述為一個有容量約束,考慮隨機需求、時限約束、設(shè)施庫存、帶提前期的隨機雙目標設(shè)施選址-庫存集成決策問題。

2.2 開放設(shè)施庫存成本分析

以i表示客戶下標,j表示候選設(shè)施點下標,不失一般性,假設(shè)客戶需求獨立同正態(tài)分布 N(μi,)。因此,服務(wù)客戶的開放設(shè)施需求也滿足正態(tài)分布N(μj,),假設(shè)開放設(shè)施采用連續(xù)性盤點的(S, s)庫存策略［11］,則:

則提前期L內(nèi)開放設(shè)施的需求量服從正態(tài)分布N(Lμj,L)。

開放設(shè)施的日常庫存控制參數(shù)可以表示如下:

安全庫存:

其中,zj是庫存服務(wù)水平系數(shù)。

訂貨點:

訂貨量:

平均庫存:

其中:

在式(7)中,TPj為j地2次連續(xù)訂購的時間間隔。

開放設(shè)施的日常周轉(zhuǎn)庫存成本可以表示為:

在式(8)中,hj為單位庫存持有成本;ocj為j地的單位訂購成本;rcj為工廠至設(shè)施的單位運輸成本。

2.3 數(shù)學模型

模型中需使用的符號和變量定義如下:

(1)參數(shù)

J:候選設(shè)施點集,j=1,2,…,n,j∈J。

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

fj:設(shè)施j的年固定設(shè)置成本。

dij:客戶i到設(shè)施j=1,2,…,n的距離。

cij:客戶i到設(shè)施j=1,2,…,n的單位運輸成本,用兩地間的距離乘單位運輸成本表示。

tij:客戶i到設(shè)施j=1,2,…,n的單位需求運輸時間,tij=dij/v,v為運輸工具的行駛速度。

Ti:客戶i的時限約束參數(shù),Ti越小表示客戶i對物資供給的時效性要求越高。在現(xiàn)實中,可根據(jù)客戶規(guī)模、性質(zhì)、偏好等因素來設(shè)置不同的時限約束參數(shù)。

χ:年平均天數(shù),用于將日需求和方差轉(zhuǎn)化為年平均值。

capj:候選設(shè)施j的容量。

(2)決策變量

Xj:j處設(shè)施開放時為1,否則為0,j∈J。

Yij:設(shè)施j被指派給客戶i時為1,否則為0,i∈I,j∈J。

Sj:設(shè)施j的庫存定至點,j∈J。

建立的有容量約束隨機多目標LIP模型表示如下:

目標函數(shù)式(9)表示系統(tǒng)總成本最小,其中第1項為開放設(shè)施的固定設(shè)置成本;第2項為庫存持有成本;第3項為固定訂購成本;第4項為設(shè)施至客戶的運輸成本;第5項為工廠至設(shè)施的運輸成本,第2項、第3項、第5項3項成本構(gòu)成了開放設(shè)施的日常周轉(zhuǎn)庫存。式(10)表示系統(tǒng)的及時性程度最高。式(11)、式(12)表示開放設(shè)施的需求均值與方差。約束式(13)表示每個客戶僅指派給1個開放設(shè)施。約束式(14)為開放設(shè)施的容量約束。約束式(15)為客戶的時限性約束。式(16)、式(17)為0-1整數(shù)性約束。

對目標函數(shù)式(9)中的Sj求導,令?TC/?Sj=0,可得:

則目標函數(shù)式(9)可以轉(zhuǎn)化為式(19)。

3 改進的非支配排序多目標遺傳算法

上述模型為非線性離散混合整數(shù)規(guī)劃模型,屬于NP-hard問題。在此采用具有良好魯棒性和隱含并行特性的遺傳算法對其進行求解。本文設(shè)計一種采用整數(shù)編碼的改進非支配排序遺傳算法(NSGAII),算法流程如圖1所示。

圖1 改進的非支配排序遺傳算法流程

3.1 染色體編碼/解碼

模型要解決的問題是:(1)開放設(shè)施的定位; (2)開放設(shè)施在客戶之間的指派;(3)開放設(shè)施庫存定至點的確定。庫存定至點可根據(jù)式(18)、式(19)計算。而開放設(shè)施與客戶之間的指派關(guān)系Yij確定后,相應(yīng)的選址決策Xj也可確定。因此,采用整數(shù)編碼策略,若有m個客戶,n個候選設(shè)施點,則令每條染色體上的基因位數(shù)為m,每個基因在1～n的整數(shù)內(nèi)產(chǎn)生,用于表示客戶點的指派關(guān)系。假設(shè)16個客戶由8個開放設(shè)施進行服務(wù)。圖2表示:選擇開放第1個、第2個、第4個、第8個候選設(shè)施,客戶1、客戶2、客戶4、客戶7、客戶12由設(shè)施2服務(wù),客戶3、客戶5、客戶6、客戶8、客戶13、客戶16由設(shè)施1服務(wù)……

圖2 染色體編碼示例

3.2 非支配解排序

適應(yīng)度評價后,即可對目標函數(shù)值TC和TT進行非支配解排序。

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

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

Step 2 對種群中的每一條染色體q,若p支配q,則Sp=Sp∪{q};若q支配p,則np=np+1。

Step 3 若np=0,表示沒有個體支配染色體p,則p為種群中的最優(yōu)個體,屬于第1前沿面,令其秩prank=1,更新第1前沿面集合,即F1=F1∪{p}。

Step 4 若Fi≠φ,則令Q=φ,用于存儲第i+1前沿面對應(yīng)的染色體,否則算法結(jié)束。

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 小生境技術(shù)

生物學上把小生境定義為具有共同特性的組織或物種。在標準遺傳算法操作中,具有高適應(yīng)度值的個體有更大的生存概率,當某個個體的適應(yīng)值大大高于種群的平均適應(yīng)值時,它在種群中的數(shù)量會急劇增加甚至支配整個種群。該狀態(tài)一旦產(chǎn)生,通過交叉操作難以生成新的個體,而偶爾的隨機變異不能保證很快跳出這種狀態(tài),從而導致搜索過程徘徊不前,產(chǎn)生早熟收斂現(xiàn)象。為了克服這一缺點,設(shè)計一種基于小生境技術(shù)的改進遺傳算法。小生境技術(shù)通過計算染色體周圍的擁擠程度來計算適應(yīng)度的降低程度以保證算法的多樣性,其計算流程如下［12-13］:

Step 1 對任意前沿面Fi,設(shè)其有p個個體,初始化Fi(dj)=0,其中,j表示Fi中的第j個個體。

Step 2 針對每一個目標,基于該目標對前沿面Fi進行排序,S=sort(Fi,z)為排序結(jié)果。對小生境邊界的個體賦予最大距離值,即I(d1)=∞,I(dp)=∞。

3.4 遺傳操作

采用錦標淘汰賽對染色體進行選擇操作,采用單點交叉和互換變異操作。

3.5 終止條件

當遺傳算法迭代代數(shù)達到最大時,算法終止并輸出結(jié)果。

4 算例與分析

在100×100的坐標平面內(nèi)產(chǎn)生40個隨機節(jié)點:包括30個客戶點及10個候選設(shè)施點?？蛻粝嚓P(guān)參數(shù)見表1,候選設(shè)施相關(guān)參數(shù)見表2。

表1 客戶相關(guān)參數(shù)

表2 候選設(shè)施相關(guān)參數(shù)

年平均天數(shù)χ=1,單位庫存持有成本h=2元,單次訂貨成本oc=10元,工廠至設(shè)施的單位運輸成本rc=120元,提前期L=1天,客戶時限約束T=3,庫存服務(wù)水平因子zj=1.96(95%的置信概率)［9］。

(1)實驗結(jié)果

改進 NSGAII參數(shù)設(shè)置:種群規(guī)模popsize= 400,最大迭代代數(shù)maxgen=800,交叉概率pc= 0.9,變異概率pm=0.05［13］。采用Matlab語言編程實現(xiàn)上述算法,運行平臺為 Intel(R)Core(TM) 2 Duo CPU T5470@1.60GHz,3GB內(nèi)存, Windows 7操作系統(tǒng)的PC機。運行31.21 min,得到71個Pareto解,模型的部分運行結(jié)果見表3,Pareto最優(yōu)解前沿見圖3。

表3 改進NSGAII部分運行結(jié)果

圖3 2種算法的Pareto前沿面對比

(2)對照實驗

為了驗證所提改進NSGAII的性能,構(gòu)建3組算例,與標準NSGAII的運行結(jié)果進行對比分析,如表4所示。其中,20×10,10×10算例中所用客戶數(shù)據(jù)分別為30×10算例中的前20個、前10個客戶數(shù)據(jù)。結(jié)果表明,標準NSGAII與改進NSGAII均能有效得出模型的Pareto前沿解集。但改進NSGAII能得到數(shù)量更為豐富的Pareto候選解,且解的分布更為均勻;而在計算時間上,兩者的效率相當。因此,與標準NSGAII相比,本文提出的改進算法具有明顯的優(yōu)勢。

表4 標準NSGAII與改進NSGAII的運行情況對比

5 結(jié)束語

本文研究了一類有容量約束的隨機多目標LIP,并設(shè)計了一種改進的NSGAII對問題進行求解。算例表明:算法可得模型的 Pateto前沿解集;改進NSGAII與標準NSGAII相比具有明顯優(yōu)勢。該模型及算法可應(yīng)用于血站或者某些應(yīng)急藥品倉庫的選址布局與庫存決策,決策者可根據(jù)實際需要在一簇Pateto解中選擇合適的優(yōu)化決策方案。下一步研究可以考慮建立多供應(yīng)點、多候選設(shè)施與客戶點的三級或者三級以上物流網(wǎng)絡(luò)LIP;或者引入可靠性因素,研究考慮系統(tǒng)安全性目標的LIP;也可集成路徑?jīng)Q策,研究相同背景下的選址-庫存-路徑問題。

［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］ 孟 超.非常規(guī)突發(fā)事件應(yīng)急血液戰(zhàn)略儲備保障模式研究［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］.系統(tǒng)工程學報,2000,15(1):86-91.

［13］ 李雙琳,馬祖軍,鄭 斌,等.震后初期應(yīng)急物資配送的模糊多目標選址-多式聯(lián)運問題［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);重慶市科技攻關(guān)計劃基金資助重大項目(CSTC2012ggC00002);重慶市科技攻關(guān)計劃基金資助重點項目(CSTC,2010AB2102,CSTC,2008AB2084)。

周愉峰(1984-),男,博士研究生,主研方向:物流系統(tǒng)優(yōu)化,物流網(wǎng)絡(luò)設(shè)計;李 志(通訊作者),教授。

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.