物流節(jié)點動態(tài)布局優(yōu)化模型及其求解算法研究＊

張得志，李雙艷

(1.華中科技大學 管理學院，湖北 武漢 430074;2.威勝集團 物流中心，湖南 長沙 410205;3.中南大學 交通運輸工程學院，湖南 長沙 410075)

物流節(jié)點動態(tài)布局優(yōu)化模型及其求解算法研究＊

張得志1，2，3，李雙艷3

(1.華中科技大學 管理學院，湖北 武漢 430074;2.威勝集團 物流中心，湖南 長沙 410205;3.中南大學 交通運輸工程學院，湖南 長沙 410075)

在分析物流節(jié)點定義及其布局內涵的基礎上，針對本文所研究的物流節(jié)點系統(tǒng)結構特點，構建了多時期、多物流節(jié)點、多種類型物流的物流節(jié)點系統(tǒng)動態(tài)布局優(yōu)化模型，該模型考慮物流節(jié)點建設固定成本、物流處理費用和物流節(jié)點的規(guī)模經(jīng)濟效益等因素。針對該模型的特點，設計了基于擴展最小費用最大流的混合遺傳算法。

物流節(jié)點;動態(tài)選址;優(yōu)化模型;啟發(fā)式規(guī)則;遺傳算法

物流節(jié)點，是物流網(wǎng)絡中連接物流線路的結節(jié)之處［1］。廣義的物流節(jié)點是指所有進行物資中轉、集散和儲運的節(jié)點，包括港口、空港、火車貨運站、公路樞紐、大型公共倉庫及現(xiàn)代物流(配送)中心、物流園區(qū)等。狹義的物流節(jié)點僅指現(xiàn)代物流意義的物流(配送)中心、物流園區(qū)和配送網(wǎng)點。

物流節(jié)點布局就是在區(qū)域范圍內部確定不同物流節(jié)點(物流園區(qū)、物流中心、配送中心等)的規(guī)模、數(shù)量、功能;以及物流節(jié)點之間的協(xié)調、物流節(jié)點與物流需求之間的協(xié)調等。本文主要研究區(qū)域內容不同時期物流節(jié)點中的物流量的變化，物流節(jié)點最優(yōu)協(xié)同布局問題。

國外對于物流節(jié)點布局(選址理論)研究的文獻比較多，其研究理論也比較成熟。近年來的研究趨勢與熱點是將經(jīng)典選址問題和車輛路徑、庫存管理綜合考慮，并考慮帶隨機需求和多階段動態(tài)選址是研究的重點和熱點，主要包括以下幾個方面［2－5］:

(1)經(jīng)典的選址模型。主要包括:P－中位問題(p－median problems)、P－中心問題(p－center problems)、覆蓋問題(covering problems)等。

(2)選址結合庫存控制網(wǎng)絡設計模型(Location–Inventory Network Design Problem)，該類模型將選址和庫存控制一起考慮，使得整體費用最小。

(3)設施選址結合車輛徑路問題(Location－Routing Network Design Problem，RNDP)，該類問題將選址和車輛配送路徑一起考慮，使得整體費用最小。

(4)樞紐網(wǎng)絡設計(Hub Network Design Problem)。該類問題研究最早起源于航空網(wǎng)絡設計問題，現(xiàn)在廣泛應用于計算機網(wǎng)絡、通信網(wǎng)絡和運輸樞紐等問題研究。O’Kelly開創(chuàng)了Hub選址問題的研究工作。

(5)動態(tài)選址問題(Dynamic Location Problem)。在這方面，國內外學者的研究主要集中在倉庫或者企業(yè)物流中心的多階段動態(tài)選址研究上，主要的求解算法有動態(tài)規(guī)劃法、啟發(fā)式算法和分支定界法等［5－6］。

國內外研究大多集中在企業(yè)的倉庫、工廠、物流中心和配送中心單個設施的動態(tài)選址，且考慮物流中心、配送中心的處理成本和規(guī)模經(jīng)濟因素的研究文獻很少。而在物流網(wǎng)絡中心，不同的物流節(jié)點具有不同的技術經(jīng)濟特性，因此在物流節(jié)點布局時要考慮不同物流節(jié)點的協(xié)同配置問題［7］。

基于此，本文以一級物流節(jié)點(物流園區(qū))和二級物流節(jié)點(物流中心和配送中心)組成的物流節(jié)點系統(tǒng)為研究對象，并考慮不同物流節(jié)點運行的規(guī)模效益，構建多時期、多貨物類型的物流節(jié)點動態(tài)選址優(yōu)化模型，并給出了基于混合遺傳算法和啟發(fā)式規(guī)則相結合的求解算法。

1 數(shù)學模型

一個城市根據(jù)未來15年物流需求變化，規(guī)劃分3個階段(第一階段為1－5年，第二階段為6－10年，第三階段為11－20年)逐步完善該城市的物流節(jié)點系統(tǒng)，提高城市物流配送效率。規(guī)劃建設由一級物流節(jié)點(物流園區(qū))和二級物流節(jié)點(物流中心和配送中心)組成的物流節(jié)點系統(tǒng)，假設一級物流節(jié)點的候選地點共有n1個，二級物流節(jié)點的候選點共有n2個，該城市有m個物流需求點，各候選物流節(jié)點的建設成本，最大物流處理能力和其他相關參數(shù)已知，各物流需求點在各時期的物流需求量和物流需求點到各潛在的物流節(jié)點之間的距離已知，考慮物流節(jié)點關閉和重新開放的變遷費用。如何合理根據(jù)實際需要布局物流節(jié)點使得在整個規(guī)劃期內社會物流成本最低(包括物流配送費用、物流節(jié)點的建設費用、物流節(jié)點的處理費用及其物流節(jié)點變動的變遷費用)。

1.1 符號說明

I表示一級物流節(jié)點(物流園區(qū))候選點集合;J表示二級物流節(jié)點(物流中心、配送中心)候選點集合;N表示客戶需求點集合;M表示貨物類型集合;T表示物流規(guī)劃時間段集合;Fk表示物流節(jié)點k建設的固定成本，k∈I∪J;(t)表示t時期從一級物流節(jié)點i到二級物流節(jié)點j的單位運輸成本;(t)表示t時期從二級物流節(jié)點j到客戶需求點n的單位運輸成本;(t)表示t時期客戶需求點n對第m種貨物的需求量;U1i(t)表示t時期一級物流節(jié)點最初設計最大物流處理能力，i∈I;U2j(t)表示t時期二級物流節(jié)點j最初設計最大物流處理能力，j∈J;(t)表示t時期一級物流節(jié)點擴能后的最大物流處理能力，i∈I;(t)表示t時期二級物流節(jié)點j擴能后的最大物流處理能力，j∈J;)分別表示t時期一級物流節(jié)點i和二級物流節(jié)點j的單位處理成本;(t)，(t)分別表示t時期一級物流節(jié)點i和二級物流節(jié)點j的規(guī)模經(jīng)濟效應因子，一般而言，0≤(t)≤(t)≤1，且規(guī)模經(jīng)濟因子越小，規(guī)模經(jīng)濟效益越大;(t)，(t)分別表示t時期通過一級物流節(jié)點i和二級物流節(jié)點j的流量;表示t時期一級物流節(jié)點i進行擴能的擴建費用表示t時期二級物流節(jié)點j進行擴能的擴建費用;表示t時期關閉物流節(jié)點k的而剩下的殘值，有(將物流節(jié)點的殘值折算的關閉年的現(xiàn)值;表示物流節(jié)點k的投資回收期;r為資金的貼現(xiàn)率;Ak(t)為物流節(jié)點k一次性投資轉化為投資回收期內的每年的等價投資額，根據(jù)資金回收公式得:Ak(t)=Fk

Dec(f)為符號函數(shù)，當f＞0時其值為1，f＜0時其值為0。

決策變量:(t)表示t時期由一級物流節(jié)點i流向二級物流節(jié)點j的第m種貨物的物流量;Xmjn(t)表示t時期由二級物流節(jié)點j流向客戶需求點n的第m種貨物的物流量;Yk(t)表示t時期候選物流節(jié)點k是否運作的指示變量，當其值為1表示在t時期運作，為0表示不運作;Ek(t)表示t時期候選物流節(jié)點k是擴能的指示變量，當其值為1表示在t時期要擴能，為0表示不擴能;

1.2 數(shù)學模型(DMLNLP)

上述數(shù)學模型中，目標函數(shù)表示整個規(guī)劃期的總費用的凈現(xiàn)值最小，其總費由3部分構成:第一部分表示整個物流網(wǎng)絡的配送費用;第二部分表示物流節(jié)點的固定建設費用和運作費用之和，第三部分表示物流節(jié)點擴能和關閉的費用;式(2)表示進入一級物流節(jié)點的物流量不能超過其最大的物流處理能力;式(3)表示進入二級物流節(jié)點的物流量不能超過其最大的物流處理能力;式(4)表示每個客戶的需求要得到滿足;式(5)表示每個二級物流節(jié)點(物流中心、配送中心)輸入輸出流量達到平衡;式(6)～(7)分別表示流入各一級物流節(jié)點和二級物流節(jié)點的物流量;式(8)～(9)分別判斷各已經(jīng)運作的一級物流節(jié)點和二級物流節(jié)點是否要擴能;式(10)～(12)表示流入各物流節(jié)點的物流量為非負;式(13)表示各物流節(jié)點在t時期運作與否。

2 求解算法分析

上述模型是一個非線性的優(yōu)化問題，而且該優(yōu)化模型是靜態(tài)選址問題的擴展，其靜態(tài)選址已證明是一個NP問題，所以該問題也是一個NP問題。對于動態(tài)的非線性選址問題一般優(yōu)化算法很難得到其最優(yōu)解。本文給出一個基于啟發(fā)式算法和遺傳算法相結合的方法來搜尋其最優(yōu)解。

2.1 算法的基本思想

首先將候選物流節(jié)點的設計容量由小到大排序，并計算最大需要建設的物流節(jié)點數(shù)量。在各級物流節(jié)點建設數(shù)目確定的前提下，通過虛擬一個發(fā)點和收點，將原問題轉化為一個節(jié)點和弧都帶有容量限制的虛擬物流網(wǎng)絡，然后利用改進的最小費用最大算法和基本遺傳算法相結合的混合遺傳算法，可以得出第一個規(guī)劃階段物流節(jié)點最優(yōu)布局。

其次，根據(jù)第一個規(guī)劃階段的靜態(tài)最優(yōu)布局，運用下述相應啟發(fā)式規(guī)則來得到第二個階段的最優(yōu)布局;同理，可以得出第三階段的最優(yōu)布局。

2.2 啟發(fā)式規(guī)則描述

在詳細描述算法前，對相應的啟發(fā)式規(guī)則說明如下:

不妨假設，Ko(t)表示t時期進行建設或者重新運作的物流節(jié)點集;KC(t)表示t時期關閉的物流節(jié)點集，并且有，Ko(t)∪Kc(t)=I∪J。

記Z(Ko(t))為在t時期開放的物流節(jié)點集為Ko(t)所對應的目標函數(shù)中配送成本和運作成本之和(即目標函數(shù)中TC和OC值之和)。

記Z()，Z()分別表示在t時期開放的物流節(jié)點j擴能后和擴能前所對應的目標函數(shù)中配送成本和運作成本之和(即目標函數(shù)中TC和OC值之和)。

記DDj(t)為開放在t時期開放物流節(jié)點j帶來整個網(wǎng)絡配送成本和運作成本之和的變化值。

記DOj(t)為開放在t時期關閉物流節(jié)點j帶來整個網(wǎng)絡配送成本和運作成本之和的變化值。

記DEj(t)為開放在t時期物流節(jié)點j擴能帶來整個網(wǎng)絡配送成本和運作成本之和的變化值。

啟發(fā)式規(guī)則

(1)開放規(guī)則:若在t時期，開放一個物流節(jié)點帶來物流成本節(jié)約大于其最大投資增加額時，開放該物流節(jié)點是合理的，用數(shù)學表達式描述如下:

(2)關閉規(guī)則:若在t時期，關閉一個物流節(jié)點帶來物流成本增加小于其關閉回收投資額時，關閉該物流節(jié)點是合理的，用數(shù)學表達式描述如下:

(3)擴建規(guī)則:若在t時期，對一個物流節(jié)點擴能帶來物流成本節(jié)約大于其最大投資增加額時，擴建該物流節(jié)點是合理的，用數(shù)學表達式描述如下:

2.3 總體求解算法

Step 1:將物流節(jié)點按其設計容量從小到大排序，并計算最大需要建設的物流節(jié)點數(shù)量。

Step2:根據(jù)各級物流節(jié)點需要建設的數(shù)量，構建虛擬物流網(wǎng)絡。

Step3:利用基于擴展的最小費用最大流的混合遺傳算法得到T=1時期的最優(yōu)物流節(jié)點配置方案，其目標函數(shù)值記為Z1(，)，其中分別表示該階段最優(yōu)配置方案所對應的一級物流節(jié)點和二級物流節(jié)點數(shù)量。

Step4:將T=2時期的客戶點的物流需求加載在T=1時期的最優(yōu)配置的物流網(wǎng)絡上，若所有的流量加載完畢，轉Step9，否則轉Step 5。

Step 5:根據(jù)擴能啟發(fā)式規(guī)則，計算未加載的客戶需求點附近的物流節(jié)點是否滿足擴能條件，并計算完成流量加載的最小擴能費用，記為Z2(E)。

Step 6:根據(jù)開放啟發(fā)式規(guī)則，計算在未加載的客戶需求點附近的物流節(jié)點是否滿足開放要求，并計算滿足未分配流量的最小新建費用，記為Z2(O)。

Step 7:比較Z2(n)，Z2(O)值的大小，若Z2(n)＜Z2(O)，則進行擴建;否則進行新建。

由此，可得到能力緊張時T=2時期的最佳配置方案，轉Step 9。

Step 8:計算物流節(jié)點的利用率，并按照利用率值從小到大排序;依次計算排序較前的物流節(jié)點是否滿足關閉條件，若滿足則關閉。由此可以得出能力過剩T=2時的最佳物流配置方案。

Step 9:將T=3時的流量加載在T=2時的最優(yōu)配置網(wǎng)絡中，并類似Step4－Step 8操作，可以得出T=3時期的最佳網(wǎng)絡配置方案。

Step 10:輸出各時期的最優(yōu)配置方案。

2.4 虛擬物流網(wǎng)絡的構建方法

如圖1所示，假設有m個一級物流節(jié)點候選點(物流園區(qū))、n個二級物流節(jié)點(物流中心、配送中心)候選點和p個客戶需求點。虛擬一個發(fā)點s和收點t，發(fā)點s到各候選物流園區(qū)點i的距離記為dsi，發(fā)點s到各候選物流園區(qū)點i的流量限制記為capsi;收點t到各候選客戶需求k的距離記為dkt，收點t到各候選客戶需求k的流量限制記為capkt，并有:dsi=0，capsi=∞;dkt=0，capkt=∞。

圖1 虛擬物流網(wǎng)絡圖Fig.1 Virtural logistics netowork

2.5 編碼及相關遺傳操作說明

在遺傳算法進行優(yōu)化計算的過程中，染色體的編碼、適應度的計算及交叉和變異操作是幾個非常重要的環(huán)節(jié)。

染色體的編碼采用二進制編碼，編碼形式如下:［u1，u2，…um|v1，v2，…，vn］，若ui=1，表示在第i個候選的地修建一個一級物流節(jié)點，否則，不修建。若vj=1，表示在第j個候選的地修建一個二級物流節(jié)點，否則，不修建。

在一級物流節(jié)點和二級物流節(jié)點都確定的條件下，按照上述虛擬物流網(wǎng)絡構建的方法，可將原問題轉化為一個弧和節(jié)點都帶有容量限制的擴展的最小費用最大流問題，通過計算該擴展最小費用流，可得其總的最小費用和網(wǎng)絡中流量分配情況。將其最小總費用作為相應染色體的適應度值。

遺傳算子中的交叉運算采用雙斷點交叉。為了保證交叉后生產(chǎn)的后代染色體的可行性，對非可行解進行修復。修復策略詳細見文獻［8］，變異運算采用反轉變異運算。

3 結論

(1)物流節(jié)點的合理布局可以提升區(qū)域物流的運行效率，降低區(qū)域物流運作成本。

(2)區(qū)域物流節(jié)點需要根據(jù)區(qū)域產(chǎn)業(yè)布局和需求變化的實際情況，在不同的規(guī)劃周期內進行不斷動態(tài)調整與優(yōu)化，以提升整個區(qū)域物流運行效率。

(3)針對由物流園區(qū)、物流中心和配送中心組成的物流節(jié)點系統(tǒng)，構建了多規(guī)劃周期、多種物流類型的區(qū)域物流節(jié)點動態(tài)布局優(yōu)化模型，并提出基于擴展最小費用最大流的混合遺傳算法。

［1］王之泰.新編現(xiàn)代物流學［M］.北京:首都經(jīng)濟貿(mào)易大學出版社，2005.

WANG Zhi-tai.New editor for modern logistics［M］.Beijing:Capital Economic and Business University Press，2005.

［2］Klose A，Drexl A.Facility location models for distribution system design［J］.European Journal of Operational Research，2005，162(1):4 －29.

［3］Bas G.Towards collaborative，intermodal hub networks:a case study in the fast moving consumer goods market［J］.Transportation Research Part E，2005(41):567 －583.

［4］Canel C.An algorithm for the capacitated，multi－ commodity multi－ period facility location problem［J］.Computers＆ Operations Research，2001(28):411－427.

［5］Current J，Ratick S，Revelle C.Dynamic facility location when the total number of facilities is uncertain:A decision analysis approach［J］.European Journal of Operational Research，1997(110):597 －609.

［6］牟倫英.物流網(wǎng)絡節(jié)點的動態(tài)選址研究［J］.工業(yè)工程與管理，2005(2):102－105.

NIU Lun-ying.Research on dynamic location for logistics network nodes［J］.Industry Engineering and Management，2005(2):102 －105.

［7］張得志.物流節(jié)點系統(tǒng)演化機理研究［J］.鐵道科學與工程學院，2008，5(1):81 －86.

ZHANG De-zhi.Evolution mechanism of logistics nodes system［J］.Journal of Railway Science and Engineering，2008，5(1):81 －86.

［8］趙曉煜.供應鏈中二級分銷網(wǎng)絡優(yōu)化設計方法的研究［D］.沈陽:東北大學管理學院，2001.

ZHAO Xiao-yu.Research on optimization method of two classes distribution network of supply chain［D］.Shengyang:School of Management，North East University，2001.

Research on an optimization model for logistics nodes dynamic location and its solution algorithm

ZHANG De-zhi1，2，3，LI Shuang-yan3

(1.School of Management，Huazhong University of Science and Technology，Wuhan 430074，China;2.Logistics Center Department of Wasion Group，Changsha 410205，China;3.School of Transportation Engineering，Central South University，Changsha 410075，China)

Based on the analysis of the definition of logistics node and intension of Logistics node spatial layout，the model constructed in this paper presented the character of logistics nodes system，which is consist of the first－class logistics node(logistics park)and second－class logistics nodes(including logistics center and distribution center).According to the above analysis，a dynamic logistics nodes location model of multi－period，multi－type cargo flow and multiple logistics nodes was given.The optimization model considered the factors including fixed cost for logistics opening，handling cost and economic of scale of different type logistics nodes.An effective algorithm based on the heuristic rules and hybrid genetic algorithm was presented according to the characteristic of optimization problem.

logistics nodes;dynamic location;optimization model;heuristic rules;genetic algorithm

U294

A

1672－7029(2011)05－0096－05

2011－06－02

國家社會科學基金資助項目(11CGL032);中國博士后科學基金資助項目(20090460941);湖南省自然科學基金資助項目(09JJ3135);湖南省科技計劃項目(2010FJ3007);中央高校科研項目(201012200100)

張得志(1976－)，男，湖南祁東人，副教授，博士，博士后，從事物流系統(tǒng)優(yōu)化研究