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

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個候選設施點?？蛻粝嚓P參數見表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.