湯希峰,丁俊武
(1.河海大學(xué) 土木與交通學(xué)院,江蘇 南京 210098;2.揚(yáng)州大學(xué) 信息工程學(xué)院,江蘇 揚(yáng)州 225127)
?
可持續(xù)發(fā)展理念下的配送中心選址模型及算法研究
湯希峰1,丁俊武2
(1.河海大學(xué) 土木與交通學(xué)院,江蘇 南京210098;2.揚(yáng)州大學(xué) 信息工程學(xué)院,江蘇 揚(yáng)州225127)
摘要:配送中心選址對物流運(yùn)作產(chǎn)生重要影響.隨著市場競爭的不斷加劇、社會環(huán)保意識的不斷增強(qiáng),配送中心選址不僅僅需要考慮成本,還需要考慮服務(wù)水平、環(huán)境影響等因素.該文以FCLP模型為基礎(chǔ),建立了以物流成本最小化、服務(wù)可靠度最大化和CO2排放最小化為目標(biāo)的配送中心選址模型,并運(yùn)用NSGA-Ⅱ?qū)δP瓦M(jìn)行了求解.算例分析表明,NSGA-Ⅱ算法不僅能夠快速求得問題的Pareto最優(yōu)解,而且與傳統(tǒng)優(yōu)化算法相比,得到的解也具有更優(yōu)性.
關(guān)鍵詞:可持續(xù)發(fā)展;配送中心選址;多目標(biāo);NSGA-Ⅱ;Pareto最優(yōu)解
配送中心作為物流網(wǎng)絡(luò)的一種重要節(jié)點(diǎn),其選址對物流運(yùn)作的效率、成本等產(chǎn)生著舉足輕重的影響,因此一直是物流學(xué)研究的重點(diǎn)問題之一.傳統(tǒng)的配送中心選址模型通??紤]的主要是物流成本,即是以物流成本最小化為目標(biāo)[1].隨著市場競爭的不斷加劇、社會環(huán)保意識的不斷增強(qiáng),配送中心選址問題的研究正面臨著新的挑戰(zhàn),不僅需要考慮物流成本,還須兼顧配送的服務(wù)水平、配送過程帶來的環(huán)境影響等,也就是配送中心的選址應(yīng)該能夠最大程度地契合可持續(xù)發(fā)展的理念要求[2].
針對可持續(xù)發(fā)展理念下的配送中心選址問題,近年來國內(nèi)外許多學(xué)者給予了高度關(guān)注,也取得了一定的研究成果.Harris等[3]以燃料消耗作為計(jì)算配送車輛CO2排放的基礎(chǔ)參數(shù),建立了以物流成本和碳排放最小化為目標(biāo)配送中心選址模型;Chaabane等[4]以碳排放成本和物流成本最小化為目標(biāo),建立了配送中心選址的混合整數(shù)規(guī)劃模型;湯希峰等[5-6]將服務(wù)可靠度作為配送服務(wù)水平的一種測度,以FCLP模型為基礎(chǔ)建立了配送中心選址的多目標(biāo)優(yōu)化模型;以FCLP模型為基礎(chǔ),建立了以物流成本最小化、服務(wù)可靠度最大化以及CO2排放最小化為目標(biāo)的配送中心選址模型.在這兩篇文章中,主要是運(yùn)用約束法和貪婪取走啟發(fā)式算法等傳統(tǒng)優(yōu)化算法對所建模型進(jìn)行了求解.與現(xiàn)代優(yōu)化算法相比,傳統(tǒng)的優(yōu)化算法雖然能夠求解所建的多目標(biāo)選址模型,但往往需要決策者提供更多的信息,而且僅能得到較少的非劣解,大大限制了決策者的選擇空間.為此,文章擬將后一篇文章所建的多目標(biāo)選址模型作為基礎(chǔ),采用NSGA-Ⅱ算法進(jìn)行求解,比較不同算法的求解結(jié)果,以期為選址決策提供更加有效的參考和支持.
1問題描述及建模
作為一種固定費(fèi)用選址模型,F(xiàn)CLP模型一直是許多配送中心選址問題的重要基礎(chǔ)模型,它是假定每個客戶的需求量和位置已知、每個候選點(diǎn)的位置和建設(shè)成本已知,要求從候選點(diǎn)中選擇若干個進(jìn)行配送中心建設(shè),使得配送中心的建設(shè)成本與從配送中心向客戶配送產(chǎn)品的運(yùn)輸成本之和最小.在可持續(xù)發(fā)展的理念下,本文將服務(wù)可靠度作配送服務(wù)水平的一種測度,它是指配送車輛在規(guī)定的時間內(nèi)將滿足需求的產(chǎn)品及時送達(dá)客戶的概率;此外,鑒于車輛在配送過程中產(chǎn)生的碳排放要比配送中心其它物流作業(yè)大得多,因而本文僅將配送車輛產(chǎn)生的CO2排放作為配送中心的環(huán)境影響指標(biāo).
若記:I為配送中心候選點(diǎn)集(i=1,2,…,I);J為客戶集(j=1,2,…,J);fi為在候選點(diǎn)i建設(shè)配送中心的固定成本;hj為客戶j的需求量;cij為候選點(diǎn)i到客戶j的單位運(yùn)輸成本;dij為候選點(diǎn)i與客戶j之間的距離;Fv(·)為配送車輛的速度分布函數(shù);tj為客戶j要求的配送時限;εvf為配送車輛滿載時的碳排放系數(shù);εve為配送車輛空載時的碳排放系數(shù);w為配送車輛的標(biāo)準(zhǔn)載重;xi為決策變量;候選點(diǎn)i用于建設(shè)配送中心時取值為1,否則為0;yij為決策變量;候選點(diǎn)i為客戶j提供配送服務(wù)時取值為1,否則為0.
則基于可持續(xù)發(fā)展理念的配送中心選址模型如下所示:
(1)
(2)
(3)
S.t.yij (4) (5) (6) (7) 其中:式(1)~(3)為目標(biāo)函數(shù),分別表示物流成本最小化、服務(wù)可靠度最大化和CO2排放量最小化;式(4)表示若候選點(diǎn)沒有建設(shè)配送中心,則無法為客戶提供服務(wù);式(5)表示每個客戶只能由一個配送中心提供服務(wù);式(6)、(7)為數(shù)值約束. 2算法設(shè)計(jì)及求解 對于多目標(biāo)優(yōu)化問題,傳統(tǒng)的優(yōu)化算法一般是通過加權(quán)法或約束法將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行求解,在轉(zhuǎn)化過程中需要決策者提供部分目標(biāo)函數(shù)的權(quán)重系數(shù)、取值約束等信息,而且針對給定的參數(shù),往往只能得到的唯一的非劣解,只有通過不斷地調(diào)整參數(shù),才能得到一組或多組非劣解,不利于決策者的選擇.相比而言,現(xiàn)代優(yōu)化算法在求解多目標(biāo)優(yōu)化問題方面具有明顯的優(yōu)勢,為此本文運(yùn)用NSGA-Ⅱ算法,并對其適當(dāng)改進(jìn)以求解所建模型,算法的主要步驟如下: 1)初始化種群P0.隨機(jī)生成N個用二進(jìn)制編碼的染色體,染色體中每個基因的取值表示候選點(diǎn)是否被選中,如“1”表示候選點(diǎn)被選中用于建設(shè)配送中心、“0”則表示候選點(diǎn)不被用于建設(shè)配送中心. 2)客戶分配.針對每個染色體給出的選址方案,運(yùn)用貪心法完成客戶分配,即客戶總是由距離其最近的配送中心提供服務(wù). 3)目標(biāo)函數(shù)評估.根據(jù)選址方案和分配方案,分別計(jì)算模型中的3個目標(biāo)函數(shù)的值. 5)選取父輩.采用二進(jìn)制錦標(biāo)賽法,從初始種群中選取N/2個染色體用于產(chǎn)生后代,記為Ppool;選取父輩時,優(yōu)先選擇排序序號小的染色體,對于具有相同序號的染色體,則選擇3個目標(biāo)函數(shù)擁擠度之和最大的那個. 6)產(chǎn)生后代.運(yùn)用交叉、變異等遺傳操作生成下一代,具體包括:①從Ppool中隨機(jī)選擇兩個染色體,采用單點(diǎn)交叉的方法產(chǎn)生下一代.②從Ppool隨機(jī)選擇一個染色體,采取二進(jìn)制變異策略產(chǎn)生下一代,也就是將該染色體變異位的基因從“1”變成“0”或從“0”變成“1”.后代種群產(chǎn)生后,進(jìn)行客戶分配并計(jì)算目標(biāo)函數(shù)值. 7)產(chǎn)生新種群.將產(chǎn)生的后代種群與初始種群合并,先進(jìn)行非支配排序,再采用二進(jìn)制錦標(biāo)賽法從合并后的種群中選擇N個染色體生成新的種群.選擇時,同樣優(yōu)先選擇排序序號小的染色體,對于具有相同序號的染色體,則選擇3個目標(biāo)函數(shù)擁擠度之和最大的. 8)循環(huán)執(zhí)行步驟2)~7)直至滿足預(yù)定的進(jìn)化代數(shù). 3算例求解及分析 為便于比較不同算法的求解結(jié)果,本文依然采用文獻(xiàn)[6]中給出的算例:假定有10個候選點(diǎn)可供選建配送中心,記為F1,F2,…,F10,其建設(shè)成本如表1所示;有25個客戶,記為C1,C2,…,C25,其需求量及其與候選點(diǎn)之間的距離如表2所示;候選點(diǎn)與客戶之間的單位運(yùn)輸成本均為cij=1元/(t·km);配送車輛為單一車型,標(biāo)準(zhǔn)載重為25t,滿載時碳排放系數(shù)εvf=1.096kg/km,空載時碳排放系數(shù)εve=0.722kg/km,車速服從均值為80km/h、方差為10的正態(tài)分布;客戶要求的送達(dá)時限均為2h. 表1 候選點(diǎn)的配送中心建設(shè)成本 元 表2 客戶的需求量及其與候選點(diǎn)之間距離 在運(yùn)用NSGA-Ⅱ算法求解所建模型時,初始種群的規(guī)模取為候選點(diǎn)數(shù)量的2倍,即N=20;交叉概率取Pc=0.9,變異概率取Pm=0.1;最大進(jìn)化代數(shù)取200次.通過獨(dú)立的運(yùn)行程序20次,發(fā)現(xiàn)每次解的個數(shù)基本穩(wěn)定在15個左右,且得到的解非常類似,表明NSGA-Ⅱ算法在求解多目標(biāo)優(yōu)化問題具有較好的收斂性和魯棒性,這里任取其中一組,如圖1所示.從圖中不難看出,所建模型3個目標(biāo)函數(shù)之間的沖突性,若單純地追求物流成本最小化,往往會導(dǎo)致較低的服務(wù)可靠度和較高的CO2排放量,反之亦然.同時,也不難發(fā)現(xiàn)在Pareto前沿的中間區(qū)域可以找到問題的一些Pareto最優(yōu)解. 另外,若將運(yùn)用傳統(tǒng)優(yōu)化算法與NSGA-Ⅱ算法得到的解進(jìn)行比較(如表3所示),明顯可以看出,一是NSGA-Ⅱ算法不需要決策者提供更多的信息就能得到很多的解可供決策者選擇,從而使得決策者能夠在不同目標(biāo)之間進(jìn)行充分權(quán)衡;二是NSGA-Ⅱ算法能夠得到一些比傳統(tǒng)優(yōu)化算法得到的更優(yōu)的解,這也充分說明對于求解多目標(biāo)優(yōu)化問題,現(xiàn)代優(yōu)化算法比傳統(tǒng)優(yōu)化算法更具優(yōu)勢. 表3 傳統(tǒng)優(yōu)化算法與NSGA-Ⅱ算法求解結(jié)果對比 4結(jié)論 傳統(tǒng)的配送中心選址模型通常以追求成本最小化為目標(biāo),隨著市場競爭的不斷加劇和環(huán)保意識的不斷增強(qiáng),配送中心選址問題的研究也亟需在可持續(xù)發(fā)展的理念下展開.本文將服務(wù)可靠度最大化、CO2排放量最小化作為目標(biāo)實(shí)現(xiàn)對FCLP模型的有效拓展,并通過改進(jìn)NSGA-Ⅱ算法實(shí)現(xiàn)對所建模型的順利求解,算例分析充分表明以NSGA-Ⅱ?yàn)榇淼默F(xiàn)代優(yōu)化算法在求解多目標(biāo)優(yōu)化問題方面比傳統(tǒng)優(yōu)化算法具有明顯優(yōu)勢. 配送中心選址問題一直是物流學(xué)科研究的重點(diǎn)之一,可持續(xù)發(fā)展理念的導(dǎo)入又讓該問題的研究面臨新的機(jī)遇和挑戰(zhàn),本文正是在這個方向上的一次探索.以后研究可在以下幾個方面進(jìn)行拓展:1)本文提出的服務(wù)可靠度、碳排放的計(jì)算方法具有很好的可移植性,可以用于對Baumol-Wolfe、Kuehn-Hamburger等選址模型的改進(jìn);2)可以將FCLP這一基礎(chǔ)模型從無能力約束拓展到有能力約束;3)選址決策過程嚴(yán)格來講,不僅包括選址的決策還包括客戶分配的決策,兩者緊密相連又相互影響,本文在客戶分配時采用的是貪心法,以后可以進(jìn)一步考察不同的客戶分配規(guī)則對選址決策的影響. 參考文獻(xiàn): [1] DASKIN M S,SNYDER L V,BERGER R T.Facility location in supply chain design.In:Langeven A,Riopel D,ed.Logistics Systems:Design and Optimization[M].New York:Springer,2005:39-65. [2] TEROUHID S A,RIES R,FARD M M.Towards sustainable facility location-a literature review[J].International Journal of Sustainable Development,2012,5(7):18-34. [3] HARRIS I,NAIM M,PALMER A,et al.Accessing the impact of cost optimization based on infrastructure modelling on CO2emissions[J].International Journal of Production Economics,2011(131):313-321. [4] CHAABANE A,RAMUDHIN A,PAQUET M.Design supply chain with sustainability consideration[J].Production Planning & Control,2011(22):727-741. [5] 湯希峰,毛海軍,李旭宏.物流配送中心選址的多目標(biāo)優(yōu)化模型[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,39(2):404-407. [6] TANG X F,ZHANG J,XU P.A multi-objective optimization model for sustainable logistics facility location[J].Transportation Research Part D:Transport and Environment,2013,22(4):45-48. [7] DEB K,AGRAWAL S,PRATAP A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation:NSGA-II[C]//International Conference on Parallel Problem Solving from Nature.Springer-Verlag,2000:849-858. (編輯崔思榮) Models and Algorithms for Locating Distribution Center in Consideration of Sustainability TANG Xifeng1, DING Junwu2 (1.School of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China;2.Information Engineering College, Yangzhou University, Yangzhou 225127, China) Abstract:Location decision of distribution centers has critical influence on logistics performance. Recent concerns regarding commercial competition and environmental pollution, gradually,are shifting the focus of modelling to incorporate not only economic cost but also service level and carbon emissions.Based on the FCLP,a location model which includes three objectives-logistics cost minimization,service reliability maximization and CO2 emissions minimization-is proposed.The NSGA-Ⅱ algorithm is adopted to solve the proposed model,and test results show that NSGA-Ⅱ algorithm can obtain Pareto optimal solutions efficiently and better performance notably in contrast with some traditional optimization techniques. Key words:Sustainable development; distribution center location; multiple objectives; NSGA-Ⅱ; Pareto-optimal solution 中圖分類號:F505 文獻(xiàn)標(biāo)志碼:A 文章編號:1674-358X(2016)01-0048-05 作者簡介:湯希峰(1980-),男,博士,主要從事運(yùn)輸與物流工程研究. 收稿日期:2015-12-03