基于遺傳算法的城市物流網(wǎng)絡設計研究概要.doc

第17卷 第5期 2008年lO月運 籌 與 管 理OPERATIONS RESEARCH AND MANAGEMENT SCIENCEV01.17,No.5 Oct.2008基于遺傳算法的城市物流網(wǎng)絡設計研究童明榮12, 薛恒新1(1.南京理工大學經(jīng)濟管理學院,江蘇南京210094;2.寧波市政府發(fā)展研究中心.浙江寧波315000摘 要:本文探討的是政府主導下的城市物流網(wǎng)絡設計。首先構(gòu)建了由物流園區(qū)、物流中心、配送中心組成的三 層城市正向物流基礎設施網(wǎng)絡;接著提出了一個混合整數(shù)規(guī)劃模型,優(yōu)化目標是使整個城市的物流費用達到最 小,并用遺傳算法求解;最后給出了一個算例,說明了模型和算法的有效性。關鍵詞:物流工程;城市物流網(wǎng)絡;遺傳算法;物流系統(tǒng)規(guī)劃中圖分類號:U492.3文章標識碼:A 文章編號:1007-3221(200805006904Research on the City Logistics Design Based on Genetic AlgorithmTONG Mingron91”,XUE Hengxin(1.School of Economics&Management,Nanjing University of Science&Technology,Nanjing 210094,China; 2.Ningbo Municipal Development&Research Center,Ningbo 315000,ChinaAbstract:This paper discusses the design of the city logistics net dominated by the government.Firstly,the threelayer city losgitics net composed of the logistics park,the logistics centerand the distribution center is con structed.After that,a mixed-integer programming mode is proposed,the optimal target is to minimize the whole city logistic fees,and the model is solved by genetic algorithm.Finally,a numerical example is given,and the result shows the approach is effective.Key words:logistics engineering;city logistics net;genetic algorithm;logistics system planning0引言城市物流是指物品在城市內(nèi)部的實體流動,城市與外部區(qū)域的貨物集散以及城市廢棄物清理的過程。 城市物流有兩種發(fā)展模式:一種是由企業(yè)自發(fā)地發(fā)展各類物流業(yè)務,另一種是由政府統(tǒng)一規(guī)劃,建立城市 物流系統(tǒng)。本文探討的政府主導下的城市物流基礎設施規(guī)劃。做好城市物流的規(guī)劃,有利于提升城市物流 行業(yè)的水平,緩解城市交通壓力,改善城市投資環(huán)境。研究表明,構(gòu)建由物流園區(qū)、物流中心、配送中心共同組成的三層物流服務體系是建設現(xiàn)代城市物流 網(wǎng)絡的合理途徑。根據(jù)規(guī)劃,北京在2010年將初步形成由3個物流園區(qū)、4個物流中心和10個配送中心 構(gòu)成的覆蓋全市的高效物流網(wǎng)絡;2010年上海市的物流網(wǎng)絡則由6個物流園區(qū),lO個物流中心,20個配 送中心構(gòu)成。理想的城市物流系統(tǒng)運轉(zhuǎn)模式是:市域范圍及進出城市的物流量絕大部分都先進入物流園區(qū)進行集 中處理,先進的城市物流體系依據(jù)物流信息中心的信息統(tǒng)一調(diào)度這些商品,將它們少品種大批量地轉(zhuǎn)運到 物流中心,經(jīng)過集中儲存再將它們進行多品種、小批量送到配送中心,配送中心再將商品配送給零售商。收稿日期:2008-02-10基金項目:國家863/CIMS主題資助項目(2002AA414040作者簡介:童明榮(1980.男.博士研究生.研究方向:物流工程;薛恒新(1946一,男,教授、博士生導師.研究方向:物流和供應鏈管理。70運 籌 與 管 理 2008年第17卷目前,研究企業(yè)主導的物流網(wǎng)絡設計的文獻已有不少231,但是政府主導的城市物流網(wǎng)絡設計還是較 新的研究領域,目前的研究報道很少。本文提出了一個混合整數(shù)規(guī)劃模型,計算城市整體的物流運輸費用 和物流樞紐的建設費用,優(yōu)化的目標函數(shù)是使整個城市的物流費用達到最小。2模型的建立2.1問題的提出考察圖1所示的城市物流網(wǎng)絡,要解決如下問題:零售點數(shù)量及地址確定,在待選的物流園區(qū)、物流中 心和配送中心中分別選擇開設哪些設施,使城市物流總費用最小。圖1城市物流網(wǎng)絡結(jié)構(gòu)圖2.2模型假設及符號說明為了便于分析和說明問題,我們作了如下的假設和簡化:(1單位運輸費用與距離成線性關系;(2每個設施之間是相互獨立的,不存在互相調(diào)用的情況;(3僅在規(guī)定的候選地點范圍內(nèi)選址,并且他們均有最大的數(shù)量限制;(4各種設施的處理能力以及投資成本、單位運營成本已知;(5僅考慮單周期可計量的經(jīng)濟成本,不考慮時間成本、社會效益等;(6各個零售點在單位時間內(nèi)的商品需求為已知常量;為方便敘述,引入如下符號:下標f表示已知的零售商的地點,i El,2,;_表示可能開設配送中心的地點,Jl,2,.,;后 表示可能開設物流中心的地點,k1,2,K;Z表示可能開設的物流園區(qū)的地點,Z1,2,。A, 表示配送中心的倉庫容量;鞏表示物流中心的倉庫容量;C。表示物流園區(qū)的倉庫容量;E,F。,G,分別表示 配送中心、物流中心、物流園區(qū)的設施投資成本;日,M。,N,分別表示配送中心、物流中心、物流園區(qū)單位時 間的運作費用;x,K,Z。分別表示在第_個待選配送中心、第后個待選物流中心和第Z個待選物流園區(qū)建 物流設施的決策變量,而x,y和z分別表示允許建立的配送中心、物流中心和物流園區(qū)的最大數(shù)目;x,= 0,1,Yk=0,1,Z,=0,1表示x,K和z;取值為0或1。髫口。分別為將配送中心_的物品運送到零售點i的數(shù)量和單位運輸費用;Yjt,bit分別為將物流中心后 的物品運送到配送中心.的數(shù)量和單位運輸費用;鉑,Ckl分別為將物流園區(qū)Z的物品運送到物流中心I|的 數(shù)量和單位運輸費用;u;為零售點i單位時間內(nèi)產(chǎn)生的物品需求數(shù)量?？?。,bjk,Ckl等單位運輸費用可以通 過物流設施間距離計算得到;茗,降,石“等不同層級物流節(jié)點之間商品運輸數(shù)量,本文借鑒交通規(guī)劃中的四 階段理論提出四階段法預測得到:(1采用組合預測法,對每個零售點物品需求進行分析和預測;(2采用 L-OD小區(qū)分類的方法,得出物流量分方向的分布情況;(3確定城市物流網(wǎng)絡中的主要物流通道;(4采 用總量分配修正法,確定兩層物流節(jié)點之間物流量的分配。2.3數(shù)學模型以單位時間內(nèi)系統(tǒng)運作費用最小為目標函數(shù)建立混合整數(shù)規(guī)劃模型第5期 童明榮,等:基于遺傳算法的城市物流網(wǎng)絡設計研究 7lmin:C=薈薈口一乃+善薈%一K+薈薈c薩“K乙+薈(易+馬-+ J K L(Ft+M。屹+三(G,+N一zr%=蠔 (2 髫口A,巧,%B。K,:“ctX, (3 膏u=石Il (4 =X,Yk=Y,Zr=Z (5, t l目標函數(shù)(1由整個網(wǎng)絡系統(tǒng)的運輸費用各設施的運作費用組成。約束條件中:式(2表示零售點的物品需求應得到完全滿足;式(3表示各設施的容量約束;式(5表 各設施的數(shù)量限制。3遺傳算法上述模型中,當整個網(wǎng)絡節(jié)點較多時,問題就變成一個NP難題,用分枝定界法等經(jīng)典數(shù)學方法求解 時不可避免地存在“維數(shù)災”問題,本文用遺傳算法求解。3.1基本步驟遺傳算法的運行過程為一個典型的迭代過程,其基本步驟為H】:(1選擇編碼策略,把參數(shù)集合和域 轉(zhuǎn)換為位串結(jié)構(gòu)空間;(2定義適應值函數(shù);(3確定遺傳策略,包括選擇、交叉、變異方法,確定交叉率、變 異率等參數(shù);(4隨機初始化生成群體;(5計算群體中個體位串解碼后的適應值;(6按照遺傳策略,運用 選擇、交叉和變異算子作用于群體,形成下一代群體;(7判斷迭代中止原則是否滿足,不滿足則返回步驟 6。3.2參數(shù)控制遺傳算法中的主要運行參數(shù)有:基因串的長度、群體大小M、交叉率P。變異率P。,和進化代數(shù)T。M 取值較小可能會導致GA早熟,取值過大時則會降低GA的運行速度,一般取20一50。中止代數(shù)是表示遺 傳算法中止條件的參數(shù),一般建議取1002000。雖然有大量的文獻研究并給出了GA的交叉率、變異率等參數(shù)的取值范圍,但是對于不同的優(yōu)化問 題,這些靜態(tài)的參數(shù)控制策略并非總能得到理想的效果。Zbigniew Michalewic1指出遺傳算法在本質(zhì)上是 一個動態(tài)的適應過程,演化過程的不同階段具有不同的最優(yōu)參數(shù)值,而實踐表明動態(tài)的參數(shù)控制策略對 GA來說更積極有效。本文采用確定的參數(shù)控制策略,根據(jù)某個確定的規(guī)則修改參數(shù),即用P(f代替參數(shù) P,其中,t為GA的演化代數(shù)。4算例假設系統(tǒng)有20個零售點,17個待選配送中心,8個待選物流中心,4個待選物流園區(qū),配送中心、物流 中心和物流園區(qū)的最大允許數(shù)目分別為10、4和2。限于篇幅,零售點和各待選物流物流設施的坐標、各 設施相互之間的距離、商品數(shù)量和單位運輸費用、各設施的倉庫容量和單位時間的運作費用等數(shù)據(jù)表格省 略。采用MATLAB語言編程計算,目前已有幾個遺傳算法工具箱,本文采用的是MATLAB7.0包含的 GADS工具箱1。編碼采用十進制編碼,基因交叉采用下式進行:c:l=Otcsn-1+(1一aict茬-1c:=Oict娌-1+(1一aictil-1(6 其中,c:l-1,cZl是父代染色體,c:。,c:2是子代染色體,a。是(0。1問的一個隨機數(shù),i=1,2,k,(k是進 行交叉的染色體的對數(shù)。72運 籌 與 管 理 2008年第17卷經(jīng)反復試驗,本文采用線性函數(shù),產(chǎn)生得到交叉率和變異率:P。=0.55+0.2X(當前代數(shù)/總代數(shù),P。=0.005+0.005X(當前代數(shù)/總代數(shù),M=30,T=500。 本文采用最大迭代數(shù)作為遺傳算法的停止準則。I晨憂崆一向I。、.、弋l、 、;2 1.5 l 0.5O 51015202530l伊 變量維數(shù)j=:,。心O 50100150200250300350400450500迭代次數(shù)圖2算法仿真過程50454035簧30攖25謠2015105O05101520253035404550圖3城市物流網(wǎng)絡結(jié)構(gòu)圖如圖2所示,在前50代計算過程中,隨著物流樞紐的空間分布和規(guī)模的變化,城市物流總費用明顯下 降。從第50代的計算開始,遺傳算法的適應度值小幅度降低,第50代的適應度值與第100代的適應度值 差別不大。這顯示出優(yōu)化模型具有很好的收斂性,程序運行500代后終止,并得到滿意解,運行時間為45秒,城市物流總費用為6.3X 107萬元,求解后得出的城市物流網(wǎng)絡結(jié)構(gòu)如圖3所示,空心圖形表示未被選 中的物流設施。5結(jié)束語確定城市物流網(wǎng)絡節(jié)點的數(shù)量和位置是個復雜的問題,本文的研究是以零售點的物流需求量的預測 值為數(shù)據(jù)基礎。但由于目前物流需求預測所依據(jù)的模型往往難以完全考慮城市經(jīng)濟發(fā)展的諸多復雜因 素,因此在進行城市物流網(wǎng)絡結(jié)構(gòu)和規(guī)模設計時,還應結(jié)合定性分析的方法,綜合考慮交通區(qū)位條件、城市 產(chǎn)業(yè)布局和城市用地規(guī)劃等因素。參考文獻:1張曉東.物流園區(qū)布局規(guī)劃理論研究M.北京:中國物資出版社,2004.4449.2Guide Jr V D R,Jayaraman V,Linton J D.Building contingency planning for closedloop supply chains with priduet recovery J.Journal of Operations Management,2003.3胡長英.逆向物流閉環(huán)雙層優(yōu)化模型及算法J.運籌與管理,2007,(163:26-3