基于遺傳算法的分銷配送網絡模型及求解

摘要：從供應鏈的集成和協調的角度出發，提出了在單工廠、多產品、多分銷中心、多客戶環境下，考慮需求分配的分銷網絡優化設計模型。模型體現了在設計分銷網絡時，根據各客戶區對不同產品各種費用情況，合理地選擇分銷中心并將各客戶區對不同產品的需求分配到各個分銷中心，以降低分銷環節的總費用。針對該模型，通過遺傳算法，選擇恰當的編碼方法，快速求解模型，并通過實例驗證了優化模型的正確性和算法的有效性。

關鍵詞：分銷網絡；選址；需求分配；遺傳算法；整數規劃

中圖分類號：F224文獻標識碼：A

文章編號：1002-3100(2008)02-0031-03

Abstract: In this paper， based on the coordination and integration of the supply chain， an optimization model for distribution network design in which single manufacturer， multi-products， multi-distributors， multi-customers and demand allocation is considered is put forward. Product demands of different customers are allocated to distribution centers by their relative cost to reduce the total cost of distribution system. For that model， the genetic algorithm is adopted， a particular concise gene representation is presented， which improves the speed of solution. A simulation is given to confirm the correctness of the optimization model and the effectiveness of the algorithm.

Key words: distribution network; location; demand allocation; genetic algorithm; integer program

0引言

由于科學技術的不斷進步和經濟的全球化，以顧客為中心的供應鏈管理面臨更為復雜的競爭環境和更為強勁的競爭對手。企業之間由單純產品質量、性能方面的競爭轉向企業所在的供應鏈之間的競爭。供應鏈主要包括三個階段，即采購、制造和分銷。在傳統制造環境下的供應鏈管理中，重點考慮的是對采購和制造環節的管理，而在面向客戶的制造業環境中，企業的驅動力已由生產轉向通過分銷和服務提供的附加值。因此，合理的建立分銷網絡，加強對分銷環節的管理，是在當前客戶驅動的競爭環境下，提高客戶的滿意度，增強企業競爭力的重要途徑[1]。本文提出了在單工廠、多產品、多分銷中心、多客戶環境下，考慮需求分配的分銷網絡優化設計模型，模型體現了在設計分銷網絡時，根據各客戶區對不同產品的需求和各種費用情況，合理地選擇分銷中心并將各客戶區對不同產品的需求分配到各個分銷中心，以降低分銷環節的總費用。

1問題的提出及模型建立

某企業生產S種產品，在N個需求地擁有直銷店鋪，各直銷店鋪都擁有租賃的倉庫，為了加強對分銷環節的管理，考慮在這些需求地的直銷店鋪租賃倉庫中選擇一些建立分銷中心，每個直銷店鋪對同種產品的需求只能由一個分銷中心供貨，對不同產品的需求可由不同分銷中心供貨，分銷中心可隨時向各直銷店鋪供貨，分銷中心采取r，Q補貨策略，且分銷中心為其供應的直銷店鋪儲備安全庫存。根據調研已知：各直銷店鋪的平均月需求、各直銷店鋪之間的運價、由產地向各直銷店鋪的運價和各直銷店鋪倉庫的單位存儲費用。現須確定：（1）選擇哪些直銷店鋪地建立分銷中心；（2）每個分銷中心負責為哪些直銷店鋪供貨供應哪些產品，使得總費用最少。對此組合優化問題，本文采用一層規劃的方法建立簡化模型，建立的模型如下：

模型中符號的意義如下：

C0：分銷中心至店鋪的運輸成本

C1：分銷中心的安全庫存持有成本

C2：工廠至分銷中心的運輸成本

C3：分銷中心的循環庫存持有成本和訂貨成本

常量：

i，j=1，2…N直銷店鋪

k=1，2…S種產品

2模型求解

傳統的分枝定界求解方法難以適用于較為大型的規劃問題。遺傳算法能勝任任意函數，高維空間的組合優化問題，能求解空間從多點搜索問題的最優解或次優解，是一類可用于復雜系統優化計算的魯棒搜索算法[2]。因此本文采用遺傳算法求解上述分銷配送網絡問題，具體設計如下：

（1）編碼策略

例：2種產品，3個店鋪，供給狀況如下：

店鋪1對產品1需求由店鋪1的倉庫供給

店鋪1對產品2需求由店鋪2的倉庫供給

店鋪2對產品1需求由店鋪1的倉庫供給

店鋪2對產品2需求由店鋪2的倉庫供給

店鋪3對產品1需求由店鋪1的倉庫供給

店鋪3對產品2需求由店鋪2的倉庫供給

編碼如下：

基因位編號：Z11Z12Z21Z22Z31Z32

基因位值：121２12

解碼如下：

X111=X121=X131=X212=X222=X232=1

X112=X122=X132=X211=X221=X231=X332=X311=X312=X321=X322=X331=0

店鋪1、2的倉庫作為分銷中心

（2）適應函數

由于適應值是群體中個體生存機會選擇的唯一確定性指標，所以適應函數的形式直接決定著群體的進化行為。為了直接將適應函數與群體中的個體優劣度量相聯系，在遺傳算法中適應值規定為非負，并且在任何情況下總是越大越好。本文中針對該式建立如下適應函數：

FX=2C-fX，C常數為當代個體中目標函數最大值

（3）遺傳算子

A. 選擇：首先保證父代種群中適應值最大的染色體在子代中至少出現一次，然后按照標準的輪盤賭方式進行選擇操作。這樣可以保證最優秀的染色體被保留到下一代。

B. 交叉：遺傳算法的交又算子是模仿自然界有性繁殖的基因重組過程，其作用在于將原有的優良基因遺傳給下一代個體，并生成包含更復雜基因結構的新個體。本文中采用單點交叉算子，按交叉率Pc選擇兩個個體是否進行交叉。實行交叉時，在染色體中隨機設定一個交叉點，將該點之后的兩個個體部分結構進行互換，從而產生兩個新個體。

C. 變異：本文中采用單點變異。隨機選擇染色體中的基因值，按變異率Pm做變異。

（4）終止條件。判斷條件為最大終止代maxG。

3應用實例

（1）算例說明

假設1個工廠，3個產品，4個需求地（備選分銷中心）的問題，常數如表。

（2）算例結果

該供應鏈分銷系統模型應用前述遺傳算法計算。初始條件是群體規模popsize=40，終止代數maxG=500，交叉概率Pc=0.8，變異概率Pm=0.02。用Matlab6.5編程，最佳個體出現在第80代，系統最低成本為428 440。所得結果如下：

選擇第1，2，3店鋪的倉庫建立分銷中心，分銷中心與店鋪供給狀況：

a. 分銷中心1（店鋪1倉庫）：對店鋪1供應第1，2，3種產品，對店鋪4供應第1，3種產品；

b. 分銷中心2（店鋪2倉庫）：對店鋪2供應第2，3種產品，對店鋪3供應第1，3種產品，對店鋪4供應第2種產品；

c. 分銷中心3（店鋪3倉庫）：對店鋪2供應第1種產品，對店鋪3供應第2種產品。

4結論

本文提出在單工廠、多產品、多分銷中心、多客戶環境下，考慮需求分配的分銷網絡優化設計模型。針對該模型，提出通過遺傳算法，選擇恰當的編碼方法和遺傳算子快速求解，并可以進行大規模的優化運算。通過實例驗證了優化模型的正確性和算法的有效性。

參考文獻：

[1] 孫會君，高自友. 基于分布式工廠的供應鏈二級分銷網絡生產計劃優化模型[J]. 中國管理科學，2002，10(6):40-43.

[2] 金海和，陳劍，趙純均. 分銷配送網絡優化模型及其求解算法[J]. 清華大學學報：自然科學版，2002，42(6):739-742.

[3] 王小平，曹立明. 遺傳箅法：理論、應用及軟件實現[M]. 西安：西安變通大學出版社，2002:1-55.

[4] 刑文訓，謝金星. 現代優化計算方法[M]. 北京：清華大學出版社，1999:248-282.

[5] 黃海新，武利勇，汪定偉，等. 基于遺傳算法的二級分銷網模型及其求解[J]. 計算機集成制造系統，2004，10(8):915-917.

[6] 馬士華，林勇，陳志祥. 供應鏈管理[M]. 北京：機械工業出版社，2000:237-243.

[7] 茆劍. 基于遺傳算法的供應鏈分銷網絡模型及其求解[J]. 價值工程，2006(2):27-29.

[8] 宓燕，陳偉達. 供應鏈中二級分銷網絡優化設計的隨機規劃模型[J]. 系統工程，2003，5(21):29-33.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。