求解二級分銷網(wǎng)絡(luò)模型的混合微粒群算法

周鮮成，趙志學(xué)，賀彩虹，徐戈

(1. 湖南商學(xué)院 計(jì)算機(jī)與電子工程學(xué)院，湖南 長沙，410205；2. 湖南商學(xué)院 會計(jì)學(xué)院，湖南 長沙，410205)

在目前面向客戶的制造環(huán)境中，企業(yè)的驅(qū)動力已由生產(chǎn)轉(zhuǎn)向分銷和服務(wù)。合理地建立分銷網(wǎng)絡(luò)(Distribution network)，加強(qiáng)分銷環(huán)節(jié)管理，是當(dāng)前需求驅(qū)動競爭環(huán)境下，提高客戶滿意度、增強(qiáng)企業(yè)競爭力的重要途徑；因此，分銷網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)以及求解在需求驅(qū)動的供應(yīng)鏈(Supply chain)中顯得尤為重要。人們對于分銷網(wǎng)絡(luò)的建模和求解進(jìn)行了較多研究，提出了多種模型和求解方法，如：趙曉煜等[1]針對各需求地對產(chǎn)品的需求和工廠的生產(chǎn)具有模糊性的特點(diǎn)，提出了模糊機(jī)會規(guī)劃約束模型；Pikul等[2]提出了結(jié)合設(shè)施選址和需求分配的多產(chǎn)品、單個(gè)制造中心的雙層規(guī)劃分銷系統(tǒng)網(wǎng)絡(luò)模型；宓燕等[3]針對需求變化的情況，提出了基于需求變化狀態(tài)下的隨機(jī)模型；Mistsuo等[4]建立了多周期分銷系統(tǒng)的網(wǎng)絡(luò)模型；Ali[5]建立了各個(gè)分銷中心容量限制不同的分銷系統(tǒng)網(wǎng)絡(luò)模型；Yang等[6]提出了定單生產(chǎn)環(huán)境下企業(yè)分銷系統(tǒng)網(wǎng)絡(luò)模型；Wee等[7]提出了產(chǎn)銷一體化網(wǎng)絡(luò)模型；Daniela等[8]提出了融入庫存決策的分銷系統(tǒng)網(wǎng)絡(luò)模型；Mokashi等[9]提出了多周期和生產(chǎn)時(shí)間最小的分銷系統(tǒng)網(wǎng)絡(luò)模型；Schneeweiss等[10]提出了同時(shí)考慮生產(chǎn)條件與供應(yīng)條件的影響，目標(biāo)函數(shù)為總成本最小、總利潤最大的分銷系統(tǒng)網(wǎng)絡(luò)模型。求解上述分銷系統(tǒng)網(wǎng)絡(luò)模型有多種方法，主要有窮舉法、分枝定界法和遺傳算法等。窮舉法存在計(jì)算量大的不足；分枝定界法難以適用于求解大型的規(guī)劃問題；而遺傳算法雖能求解大型問題，但易陷入局部最優(yōu)，并且運(yùn)算效率不高[11-12]。在此，本文作者將遺傳操作引入微粒群算法(Particle swarm optimization, PSO)[13]，提出求解二級分銷網(wǎng)絡(luò)模型的混合微粒群算法。

1 問題的提出及數(shù)學(xué)描述

某制造企業(yè)計(jì)劃將某產(chǎn)品打入某地區(qū)市場，設(shè)置了多個(gè)較分散的零售商(需求地)，并建有多個(gè)生產(chǎn)工廠，同時(shí)建立一些分銷中心以降低分銷網(wǎng)絡(luò)成本和管理復(fù)雜性。本模型中，考慮在這些需求地中選擇一些點(diǎn)建立大型分銷中心，在分銷中心建立倉庫，而在沒被選為分銷中心的需求地建立分銷點(diǎn)，且每個(gè)分銷點(diǎn)只由1個(gè)分銷中心供貨，在不同需求地建立或租用倉庫的月費(fèi)用是不同的。根據(jù)調(diào)研，已知各需求點(diǎn)月需求量、各需求點(diǎn)運(yùn)價(jià)、產(chǎn)地到需求地運(yùn)價(jià)以及各需求地建立或租用倉庫的月費(fèi)用。需要解決的問題是如何設(shè)置分銷中心，確定分銷中心供貨點(diǎn)，使總費(fèi)用最少[12]。建立的模型如下：

其中：n和m為需求地號，m=1, 2, …, N, n=1, 2, …, N；l為產(chǎn)地號；an為需求地n的月需求；bnm為需求地n到需求地m的運(yùn)價(jià)；cln為產(chǎn)地l到需求地n的運(yùn)價(jià)；dk為需求地建立第k個(gè)倉庫的費(fèi)用；L為最大產(chǎn)地號；N為最大需求地號；K為最大倉庫號；xn為分銷中心的決策變量，xn=0表示需求地n不建立分銷中心，xn=1表示需求地n要建立分銷中心；ynm表示需求地n(分銷中心)向需求地m供貨的決策變量，ynm=0表示需求地n不負(fù)責(zé)需求地m的供貨，ynm=1表示需求地n負(fù)責(zé)需求地m的供貨；zln表示第l個(gè)產(chǎn)地負(fù)責(zé)向需求地n(分銷中心)供貨的決策變量，zln=0表示第l個(gè)產(chǎn)地不負(fù)責(zé)向需求地n(分銷中心)供貨，zln=1表示第l個(gè)產(chǎn)地負(fù)責(zé)向需求地n(分銷中心)供貨。

式(1)為目標(biāo)函數(shù)，其中：第1項(xiàng)為產(chǎn)地至分銷中心的總運(yùn)費(fèi)；第2項(xiàng)為分銷中心至分銷點(diǎn)的總運(yùn)費(fèi)；第3項(xiàng)為倉庫建立或租用的總費(fèi)用。約束條件式(2)～(5)中，式(2)表示分銷點(diǎn)只由 1個(gè)分銷中心供貨；式(3)表示只有分銷中心才供貨；式(4)表示每個(gè)分銷中心只由1個(gè)產(chǎn)地供貨，并且產(chǎn)地只向分銷中心供貨[12]。

2 求解二級分銷網(wǎng)絡(luò)模型的混合微粒群算法

2.1 標(biāo)準(zhǔn)微粒群算法

PSO算法是一種實(shí)數(shù)域內(nèi)的進(jìn)化算法。設(shè)微粒群的搜索區(qū)域?yàn)镹維空間，則第i個(gè)微粒的位置可表示為Pi(Pi1, Pi2, …, PiN)，其飛行速度表示為vi(vi1, vi2, …,viN)；每一個(gè)微粒所經(jīng)歷的具有最大適應(yīng)值的位置稱為個(gè)體最優(yōu)，記為Pbi(Pbi1, Pbi2, …, PbiN)，種群中所有微粒所經(jīng)歷的最大適應(yīng)值位置稱為全局最優(yōu)，記為 Gb(Gb1, Gb2, …, GbN)。對PSO算法的每一次迭代，微粒通過動態(tài)跟蹤Pbi和Gb來更新自身的速度和位置。對于最小化問題，目標(biāo)函數(shù)值越小，對應(yīng)的適應(yīng)度便越高。其速度和位置的進(jìn)化公式為：

其中：下標(biāo)“i” 表示第i個(gè)微粒；“j” 表示微粒的第 j維；“t”表示第 t代；ω稱為慣性權(quán)重；c1和 c2為加速常數(shù)，通常在0～2間取值；r1(t)和r2(t)為在(0, 1)之間取值的2個(gè)相互獨(dú)立的隨機(jī)序列[13]。

2.2 混合微粒群算法設(shè)計(jì)的基本思想

標(biāo)準(zhǔn)微粒群算法主要適用于連續(xù)空間函數(shù)的優(yōu)化問題，而二級分銷網(wǎng)絡(luò)模型的優(yōu)化目標(biāo)是要確定分銷中心的設(shè)置地點(diǎn)、設(shè)置數(shù)量以及各分銷中心負(fù)責(zé)供貨的需求地，是一個(gè)典型的離散優(yōu)化問題；因此，標(biāo)準(zhǔn)微粒群算法不能直接應(yīng)用于二級分銷網(wǎng)絡(luò)模型的優(yōu)化。為此，本文將遺傳算法中的變異和交叉操作引入微粒群算法，對標(biāo)準(zhǔn)微粒群算法進(jìn)行改造，使其能應(yīng)用于離散問題的求解。在此基礎(chǔ)上，提出一種求解二級分銷網(wǎng)絡(luò)模型的混合微粒群算法。

2.2.1 編碼

(1) 種群編碼。應(yīng)用微粒群算法求解二級分銷網(wǎng)絡(luò)模型的關(guān)鍵是如何編碼。對于該問題，微粒群算法的編碼采用如下設(shè)計(jì)：設(shè)種群中的個(gè)體為N維，個(gè)體的每一維 Pj(j=1, 2, …, N)為非零整數(shù)，其范圍為[-L, S]，Pj有S個(gè)負(fù)數(shù)，表示建立S個(gè)分銷中心；L為產(chǎn)地?cái)?shù)量。Pj＜0表示在第j個(gè)需求地建立分銷中心，且由第|Pj|產(chǎn)地供貨；Pj＞0表示在第j個(gè)需求地建立分銷點(diǎn)，且由第Pj分銷中心供貨[12]。

(2) 編碼說明。為了解釋編碼的含義，舉例進(jìn)行編碼說明。設(shè)有3個(gè)產(chǎn)地、10個(gè)需求地，編碼如下：

需求地：1 2 3 4 5 6 7 8 9 10

Pj： 2 2 -2 1 2 -3 2 2 3 -1

解碼如下：

① 當(dāng)j為3, 6, 10時(shí)，對應(yīng)的Pj＜0，因此，x=[0 0 1 0 0 1 0 0 0 1]。表示在第3，6和10個(gè)需求地建立分銷中心，在其他需求地建立分銷點(diǎn)。

② 對應(yīng) P3=-2，z23=1，P6=-3，z36=1，P10=-1，z110=1，由此可以得出z矩陣：

③ 由第1個(gè)分銷中心(需求地3)供貨的有P3和P4，得出y33=y34=1；由第2個(gè)分銷中心(需求地6)供貨的有P1, P2, P5, P6, P7和P8，得出y61= y62= y65= y66= y67=y68=1；由第 3個(gè)分銷中心(需求地 10)供貨的有 P9和P10，得出y99= y910=1。由此可以得出：

2.2.2 適應(yīng)度函數(shù)

為評價(jià)種群中個(gè)體的優(yōu)劣，以式(1)作為算法的適應(yīng)度函數(shù)，即

適應(yīng)度最小的微粒為最優(yōu)微粒。

2.2.3 種群更新策略

在混合微粒群算法中，遺傳算法的變異和交叉操作被引入微粒群算法。將式(6)中的)(tvω看作遺傳算法中的變異操作，將式(6)中的第2項(xiàng)和第3項(xiàng)看作是遺傳算法的交叉操作，讓當(dāng)前解首先與個(gè)體最優(yōu)位置進(jìn)行交叉操作，然后，與全局最優(yōu)位置進(jìn)行交叉操作，從而產(chǎn)生新的微粒。

(1) 檢測修補(bǔ)策略，主要是零檢測和范圍檢測。零檢測是為了保證任一需求地必須是分銷中心或者是分銷點(diǎn)之一；而范圍檢測是為了保證微粒在交叉和變異更新之后應(yīng)滿足取值范圍。修補(bǔ)策略主要是對檢測不滿足取值范圍的微粒重新賦值，使其符合取值范圍。

(2) 變異操作策略。

Step 1 在解空間(P1, P2, …, P10)中隨機(jī)選擇1到N的整數(shù)j；

Step 2 隨機(jī)對Pj進(jìn)行變異，變異范圍為[-L，S]。

(3) 交叉操作策略。

Step 1 2個(gè)串old1和old2交叉，在第2個(gè)串old2中隨機(jī)選擇1個(gè)交叉區(qū)域；

Step 2 old1相應(yīng)的交叉區(qū)域由old2交叉區(qū)域代替。

2.3 算法步驟

根據(jù)混合微粒群算法設(shè)計(jì)的基本思想，設(shè)計(jì)算法的具體操作步驟如下。

(1) 種群初始化。設(shè)定種群規(guī)模和最大迭代次數(shù)，在規(guī)定范圍內(nèi)對微粒的位置和速度進(jìn)行初始化。

(2) 檢測和解碼。檢測主要是范圍檢測。對符合條件的進(jìn)行解碼，否則進(jìn)行修補(bǔ)。解碼的目的是由Pi生成x，y和z。

(6) 對微粒進(jìn)行交叉和變異操作，更新微粒的速度和位置。

(7) 如未達(dá)到最大迭代次數(shù)，則返回第(2)步。

(8) 輸出全局最好位置Gb。

3 算例仿真及分析

3.1 算例仿真

采用文獻(xiàn)[12]中的算例，對3個(gè)產(chǎn)地、10個(gè)需求地的問題進(jìn)行求解，表1～4所示為算例提供的參數(shù)。微粒群算法的參數(shù)設(shè)定如下：種群規(guī)模為20，最大進(jìn)化代數(shù)為100。算法采用Matlab7.0編程，在CPU為2 G、內(nèi)存為4 G的PC機(jī)上運(yùn)行。算法平均在第40代左右收斂，產(chǎn)生的最優(yōu)解為[-1 1 -3 1 1 3 1 3 -2 3]，在第1，3和9點(diǎn)處建立分銷中心，總費(fèi)用為6 274 300元。

3.2 分析對比

為了驗(yàn)證算法的有效性，將提出的算法與窮舉法、基于遺傳算法的求解方法進(jìn)行對比分析，其運(yùn)算結(jié)果如表5所示。從表5可以看出：尋優(yōu)結(jié)果優(yōu)于遺傳算法結(jié)果；在收斂性方面，遺傳算法要到90代才會收斂，而提出的混合微粒群算法在40代左右即可收斂，收斂性更好；在運(yùn)算速度方面，遺傳算法達(dá)到收斂平均需要30 s，而采用提出的混合微粒群算法只需21 s，運(yùn)算速度更快，特別是在求解大型規(guī)劃問題時(shí)具有較大優(yōu)勢。

表1 各需求地之間的運(yùn)價(jià)Table 1 Demand node to demand node transportation cost 運(yùn)價(jià)/元

表2 產(chǎn)地到各需求地間的運(yùn)價(jià)Table 2 Plant to demand node transportation cost 運(yùn)價(jià)/元

表3 各需求地的月需求量Table 3 Demand details month at demand node

表4 在各需求地建立/租用各類倉庫的平均月費(fèi)用Table 4 Establishing or hire storehouse at demand node cost in a month 費(fèi)用/元

表5 S=3，n=10時(shí)算法運(yùn)算結(jié)果比較Table 5 Comparison of computing results using different methods when S=3 and n=10

4 結(jié)論

(1) 將微粒群算法應(yīng)用于二級分銷網(wǎng)絡(luò)模型的求解，為求解二級分銷網(wǎng)絡(luò)模型提供了一種新的思路和方法。

(2) 將遺傳算法的交叉和變異操作引入微粒群算法，使微粒群算法能應(yīng)用于離散問題的求解。

(3) 提出的混合微粒群算法應(yīng)用于二級分銷網(wǎng)絡(luò)模型的求解時(shí)，能獲得全局最優(yōu)解，且收斂性好，運(yùn)算速度快，穩(wěn)定性好，不容易陷入局部最優(yōu)。

[1] 趙曉煜, 汪定偉. 供應(yīng)鏈中二級分銷系統(tǒng)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的模糊機(jī)會約束規(guī)劃模型[J]. 控制理論與應(yīng)用, 2002, 19(2):249-253.ZHAO Xiao-yu, WANG Ding-wei. Fuzzy chance constrained programming model for bi-level distribution network design in the supply chain[J]. Control Theory and Applications, 2002,19(2): 249-253.

[2] Pikul H, Jayaraman V. A multi-commodity, multi-plant,capacitated facility location problem: formulation and efficient heuristic solution[J]. Computer Operations Research, 2003,25(1): 869-878.

[3] 宓燕, 陳偉達(dá). 供應(yīng)鏈中二級分銷系統(tǒng)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的隨機(jī)規(guī)劃模型[J]. 系統(tǒng)工程, 2003, 21(5): 29-32.MI Yan, CHEN Wei-da. A randomized programming model for bi-level distribution network designing in the supply chain[J].Systems Engineering, 2003, 21(5): 29-32.

[4] Mitsuo G, Admi S. Hybid genetic algorithm for multi-time perio production/distribution planning[J]. Computer and Industrial Engineering, 2005, 48(4): 799-809.

[5] Ali A. Designing a distribution network in a supply chain system formulation and efficient solution procedure[J]. European Journal of Operation Research, 2006, 171(2): 567-576.

[6] Yang P C, Wee H M. A single-vendor and multi-buyers production-inventory policy for a deteriorating item[J]. European Journal of Operational Research, 2002, 143(3): 570-581.

[7] Wee H M, Yang P C. The optimal and heuristic solution of a distribution network[J]. European Journal of Operational Research, 2004, 158(3): 626-632.

[8] Daniela A, Maria G S. Distibution network design: New problems and related models[J]. European Journal of Operational Research, 2005, 165(3): 610-624.

[9] Mokashi S D, Kokssis A C. Application of dispersion algorithms to supply chain optimization[J]. Computers and Chemical Engineering, 2003, 27(7): 924-949.

[10] Schneeweiss C, Zimmer K. Hierarchical coordination mechanisms within the supply chain[J]. European Journal of Operational Research, 2004, 153(3): 687-703.

[11] 孫會君, 高自友. 基于分布式工廠的供應(yīng)鏈二級分銷網(wǎng)絡(luò)生產(chǎn)計(jì)劃優(yōu)化模型[J]. 中國管理科學(xué), 2002, 10(6): 40-43.SUN Hui-jun, GAO Zi-you. Production planning models of two-echelon distribution network in supply chain based on distributed plants[J]. Chinese Journal of Management Science,2002, 10(6): 40-43.

[12] 黃海新, 武利勇, 汪定偉, 等. 基于遺傳算法的二級分銷網(wǎng)模型及其求解[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2004, 10(8): 914-918.HUANG Hai-xin, WU Li-yong, WANG Ding-wei, et al.Optimization model for a two-level distribution network and its genetic algorithm-based solution[J]. Computer Integrated Manufacturing Systems, 2004, 10(8): 914-918.

[13] 張?jiān)鲚x, 胡衛(wèi)東, 郁文賢. 遺傳二進(jìn)制多粒子群優(yōu)化算法及其在子陣STAP中的應(yīng)用[J]. 信號處理, 2009, 25(1): 52-56.ZHANG Zeng-hui, HU Wei-dong, YU Wen-xian. Genetic binary multiple particle swarm optimization algorithm and application in subarray STAP[J]. Signal Processing, 2009, 25(1): 52-56.