劉　星

(鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院，河南 鄭州 450046)

?

和聲搜索算法優(yōu)化快速消費(fèi)品生產(chǎn)配送協(xié)調(diào)調(diào)度

劉星

(鄭州航空工業(yè)管理學(xué)院 管理工程學(xué)院，河南 鄭州 450046)

摘要：研究具有生產(chǎn)準(zhǔn)備環(huán)節(jié)的快速消費(fèi)品生產(chǎn)配送問題，考慮工廠和配送中心的庫存限制，工廠產(chǎn)能限制和勞動(dòng)力限制，建立一個(gè)多周期、多工廠、多產(chǎn)品、多配送中心、多客戶的混合整數(shù)線性規(guī)劃模型，旨在最小化準(zhǔn)備成本、生產(chǎn)成本、庫存成本和配送成本。通過設(shè)計(jì)一種遺傳和聲搜索算法對(duì)模型進(jìn)行求解。最后給出一個(gè)算例說明所提模型和算法的可行性和有效性。

關(guān)鍵詞：生產(chǎn)配送； 快速消費(fèi)品； 協(xié)調(diào)調(diào)度； 遺傳和聲搜索算法

生產(chǎn)與配送計(jì)劃是供應(yīng)鏈中兩個(gè)核心優(yōu)化問題。其中，生產(chǎn)計(jì)劃通常決定在一定計(jì)劃周期內(nèi)，常規(guī)/加班生產(chǎn)時(shí)間、轉(zhuǎn)包量、生產(chǎn)力水平等，配送計(jì)劃通常決定配送量、配送方式和配送路徑[1]。在傳統(tǒng)供應(yīng)鏈中，盡管制造商、批發(fā)商和零售商都清楚要追求共同的利益，但是由于其追求利益最大化的動(dòng)機(jī)，使得制造商、批發(fā)商和零售商還是作為獨(dú)立實(shí)體來進(jìn)行生產(chǎn)、配送[2]。目前已經(jīng)證明，在供應(yīng)鏈背景下的生產(chǎn)配送計(jì)劃是相互聯(lián)系且需要在整體上同時(shí)優(yōu)化的兩個(gè)環(huán)節(jié)，也出現(xiàn)了不少關(guān)于生產(chǎn)配送協(xié)調(diào)調(diào)度的綜述性文章[1,3-5]。鑒于快速消費(fèi)品單位價(jià)值低、品種種類多、更新速度快等特點(diǎn)，為了尋求更快的補(bǔ)給和更短的生產(chǎn)周期，就需要緊密協(xié)調(diào)生產(chǎn)與配送環(huán)節(jié)，避免庫存過剩帶來成本、資源浪費(fèi)[6-7]。

啟發(fā)式算法可以幫助求解大規(guī)模的生產(chǎn)配送協(xié)調(diào)調(diào)度問題，可以彌補(bǔ)傳統(tǒng)優(yōu)化方法的不足，快速找到接近最優(yōu)解的有效解。目前用于求解生產(chǎn)配送協(xié)調(diào)調(diào)度問題常用算法有模擬退火[8]、粒子群算法[9]、禁忌搜索[10]、文化基因算法[11]和遺傳算法[12]等。和聲搜索算法[13-15]是一種新的啟發(fā)式搜索算法。該算法的新和聲生成方式及微調(diào)方式非常適合離散優(yōu)化問題，但是目前較少用于生產(chǎn)配送協(xié)調(diào)調(diào)度問題。本文嘗試采用遺傳和聲搜索算法對(duì)快速消費(fèi)品生產(chǎn)配送協(xié)調(diào)調(diào)度方案進(jìn)行優(yōu)化，并通過算例驗(yàn)證該算法的可行性。

1問題描述及模型建立

為建模方便，假設(shè)在某種快速消費(fèi)品生產(chǎn)配送網(wǎng)絡(luò)中存在多個(gè)工廠、多個(gè)配送中心和多個(gè)客戶。工廠和配送中心均有庫存。每個(gè)工廠只能生產(chǎn)一種產(chǎn)品，且能夠滿足所有客戶的需求，在切換產(chǎn)品品種時(shí)需要考慮生產(chǎn)準(zhǔn)備成本。工廠和配送中心庫存有限制。工廠和配送中心的配送能力無限。

參數(shù)與決策變量如下。

n為工廠編號(hào)，n=1,2,…,N；

i為產(chǎn)品編號(hào)，i=1,2,…,I；

j為配送中心編號(hào)，j=1,2,…,J；

m為客戶編號(hào)，m=1,2,…,M；

t為周期編號(hào)，t=1,2,…,T；

anit為周期t工廠n產(chǎn)品i的單位常規(guī)生產(chǎn)成本；

bnit為周期t工廠n產(chǎn)品i的單位加班生產(chǎn)成本；

hnit為周期t工廠n產(chǎn)品i的單位庫存成本；

dnit為周期t工廠n產(chǎn)品i的生產(chǎn)準(zhǔn)備成本；

enit為周期t工廠n產(chǎn)品i的單位產(chǎn)能；

fnit為周期t工廠n產(chǎn)品i的單位勞動(dòng)力水平；

gnijt為周期t工廠n到配送中心j產(chǎn)品i的單位配送成本；

gjimt為周期t配送中心j到客戶m產(chǎn)品i的單位配送成本；

hijt為周期t配送中心j產(chǎn)品i的單位庫存成本；

Vjit為周期t配送中心j產(chǎn)品i的庫存量；

Vnit為周期t工廠n產(chǎn)品i的庫存量；

Dimt為周期t客戶m對(duì)產(chǎn)品i的需求；

vi為產(chǎn)品i的體積；

M為一個(gè)大正數(shù)；

Pnit為周期t工廠n產(chǎn)品i的常規(guī)生產(chǎn)量；

Onit為周期t工廠n產(chǎn)品i的加班生產(chǎn)量；

Rnijt為周期t工廠n到配送中心j產(chǎn)品i的配送量；

Rjimt為周期t配送中心j到客戶m產(chǎn)品i的配送量；

Ynit為周期t工廠n產(chǎn)品i的生產(chǎn)決策變量。

目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Pnit+Onit≤MYnit，

(9)

Pnit，Onit，Rnijt，Rjimt≥0，

(10)

(11)

其中，式(1)表示總成本目標(biāo)函數(shù)，包括生產(chǎn)成本、加班成本、庫存成本、配送成本；式(2) 表示從配送中心到客戶的配送量應(yīng)大于客戶需求量；式(3)和式(4)分別表示工廠和配送中心的庫存平衡約束；式(5)和式(6)表示工廠和配送中心的庫存空間限制；式(7)和式(8)分別表示工廠的產(chǎn)能限制和勞動(dòng)力水平限制；式(9)表示生產(chǎn)決策變量與常規(guī)生產(chǎn)量和加班生產(chǎn)量的相關(guān)關(guān)系；式(10)為非負(fù)約束；式(11)為生產(chǎn)決策變量。

2本文提出的遺傳和聲搜索算法

和聲搜索算法是由Geem等[13]提出的模仿音樂演奏過程的一種新的智能優(yōu)化算法，具有時(shí)間復(fù)雜度小，適用范圍廣等優(yōu)點(diǎn)。但是和聲搜索算法非常依賴于和聲記憶庫和新解產(chǎn)生方式。為了克服這一缺點(diǎn)，本文提出通過遺傳算法來產(chǎn)生初始解，并且調(diào)整新解的產(chǎn)生方式，使和聲算法具有更好的收斂性和最優(yōu)性。具體步驟如下。

步驟1初始化遺傳和聲搜索算法參數(shù)。包括和聲搜索算法參數(shù)和聲記憶庫大小HMS、和聲記憶庫考慮概率HMCR、和聲微調(diào)概率PAR、迭代次數(shù)NI。

由仿真實(shí)驗(yàn)和文獻(xiàn)[16]，本文中和聲記憶庫選擇概率HMCR在[0.63,0.99]范圍內(nèi)取0.95，和聲微調(diào)概率PAR在[0.01,0.73]范圍內(nèi)取0.1，距離帶寬BW在[0.01,0.50]范圍內(nèi)取0.5，迭代次數(shù)NI在[50,150]范圍內(nèi)取100。

遺傳算法參數(shù)有種群規(guī)模GS、變異概率PM、交叉概率PC、迭代次數(shù)NI。本文中種群規(guī)模GS在[10,200]范圍內(nèi)取200，交叉概率PC在[0.1,0.9]范圍內(nèi)取0.7，變異概率PM在[0.05,0.35]范圍內(nèi)取0.2，迭代次數(shù)NG在[50,150]范圍內(nèi)取100。

步驟2初始化和聲記憶庫。利用遺傳算法產(chǎn)生初始種群，從種群中選擇最好的HMS個(gè)體作為初始和聲記憶庫的解。其過程如下。

a) 初始化種群。參數(shù)優(yōu)化后會(huì)以自然數(shù)進(jìn)行編碼。

b) 選擇操作。采用錦標(biāo)賽方法，隨機(jī)選擇2個(gè)適應(yīng)度高的個(gè)體x1和x2，如果x1優(yōu)于x2，則保留x1。同樣，選擇兩個(gè)目標(biāo)函數(shù)值高的個(gè)體x3和x4，如果x3優(yōu)于x4，則保留x3。

d) 變異操作。b1和b2通常用來取代相應(yīng)的個(gè)體。

e) 計(jì)算新個(gè)體的目標(biāo)函數(shù)值f(x)，不斷循環(huán)選擇、交叉和變異操作，直到達(dá)到迭代次數(shù)。

f) 新種群中的HMS個(gè)體將作為初始和聲記憶庫的解向量被保存起來。

步驟3產(chǎn)生新和聲。通過HMCR與PAR產(chǎn)生一個(gè)新解Xnew。根據(jù)Xnew=Xnew+2w·rand-w。其中,w代表微調(diào)幅度；rand代表0-1之間的隨機(jī)數(shù)。

步驟4更新和聲記憶庫。若上述產(chǎn)生的新解優(yōu)于和聲記憶庫中的最差解，那么就用新解替換最差解；否則，保持不變。

步驟5判斷是否達(dá)到迭代次數(shù)。若沒有，則重新進(jìn)行步驟3。

3數(shù)值算例

2種按單生產(chǎn)產(chǎn)品分別由2個(gè)工廠生產(chǎn)，產(chǎn)成品經(jīng)過3個(gè)配送中心，最后配送至4個(gè)客戶。已知工廠1中產(chǎn)品1、2的初始庫存為400和200單位；工廠2中產(chǎn)品1、2的初始庫存為300和200單位。產(chǎn)品1、2的庫存空間分別是2和3單位，2個(gè)工廠的最大庫存容量是20 000和15 000，3個(gè)配送中心的最大庫存空容量分別是20 000、18 000、20 000單位。工廠1、2的最大生產(chǎn)能力分別為17 100和20 500。工廠1、2的最大可用勞動(dòng)力水平分別為10 400和9 200。表1～3分別為其他相關(guān)數(shù)據(jù)。

表1　各產(chǎn)品的相關(guān)成本

表2　各配送中心到客戶的配送成本和客戶需求

4求解結(jié)果

使用Matlab R2014a編制程序求解，目標(biāo)值為1 418 046。最優(yōu)值如圖1所示。

圖1　最優(yōu)值圖

5結(jié)論與展望

上述遺傳和聲搜索算法對(duì)求解具有生產(chǎn)準(zhǔn)備環(huán)節(jié)的且?guī)齑?、產(chǎn)能、勞動(dòng)力水平均有限制的快速消費(fèi)品生產(chǎn)配送協(xié)調(diào)調(diào)度問題具有良好的求解效率，隨著迭代次數(shù)增加，目標(biāo)值趨于最優(yōu)。但是現(xiàn)實(shí)生產(chǎn)配送過程中還可能存在不確定性參數(shù)，因此，在此基礎(chǔ)上在模型中添加不確定參數(shù)，進(jìn)一步模仿現(xiàn)實(shí)環(huán)境，才能得到更加有效合理的模型和解法。

參考文獻(xiàn)：

[1]BEHNAM Fahimnia, REZA Zanjirani Farahani, ROMEO Marian, et al. A review and critique on integrated production-distribution planning models and techniques[J]. Journal of Manufacturing Systems，2013,32(1): 1-19.

[2]GULAY Barbarosoglu, DEMET Ozgur. Hierarchical design of an integrated production and 2-echelon distribution system[J]. European Journal of Operational Research， 1999, 118 (3):464-484.

[3]CHEN Zhilong. Integrated production and outbound distribution scheduling: review and extensions[J]. Operations Research, 2010,58(1):130-148.

[4]GOETSCHALCKX M, VIDAL C J, DOGAN K. Modeling and design of global logistics systems: A review of integrated strategic and tactical models and design algorithms[J]. European Journal of Operational Research， 2002,143(1): 1-18.

[5]BILGEN B, OZKARAHAN I. Strategic tactical and operational production-distribution models: a review[J]. International Journal of Technology Management， 2004, 28(2): 151-171.

[6]BILGEN Bilge, GUNTHER Hans-Otto. Integrated production and distribution planning in the fast moving consumer goods industry: a block planning application[J]. OR Spectrum， 2010,32(4):927-955.

[7]SEL C, BILGEN B. Hybrid simulation and MIP based heuristic algorithm for the production and distribution planning in the soft drink industry[J]. Journal of Manufacturing Systems， 2014,33(3):385-399.

[8]SARRAFHA K, RAHMATI S H A, NIAKI S T A, et al. A bi-objective integrated procurement, production, and distribution problem of a multi-echelon supply chain network design: a new tuned MOEA[J]. Computer & Operations Research， 2015,54:35-51.

[9]VARTHANAN P A, MURUGAN N, KUMAR G M. A simulation based heuristic discrete particle swarm algorithm for generating integrated prodution-distribution plan[J]. Applied Soft Computing，2012,12(9):3034-3050.

[10]ARMENTANO V A, SHIGUEMOTO A L, LOKKETANGEN A. Tabu search with path relinking for an integrated production-distribution problem[J]. Computers & Operations Research， 2011,38(8):1199-1209.

[11]BOUDIA M, PRINS C. A memetic algorithm with dynamic population management for an integrated production-distribution problem[J]. European Journal of Operational Research， 2009,195(3):703-715.

[12]ALIEV R A, FAZLOLLAHI B, GUIRIMOV B G, et al. Fuzzy-genetic approach to aggregate production-distribution planning in supply chain management[J]. Information Sciences， 2007,177(20):4241-4255.

[13]GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm: harmony search[J]. Simulation,2001,76(2):60-68.

[14]DAS S, MUKHOPADHYAY A, ROY A, et al. Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics， 2011, 41(1): 89-106.

[15]MANJARRES D, LANDA-TORRES I, GIL-LOPEZ S, et al. A survey on application of the harmony search algorithm[J]. Engineering Applications of Artificial Intelligence，2013,26(8):1818-1831.

[16]賴志柱.和聲搜索算法優(yōu)化多時(shí)間窗多式聯(lián)運(yùn)運(yùn)輸方案[J].計(jì)算機(jī)應(yīng)用，2013,33(9):2640-2642,2693.

LAI Zhizhu. Harmony search algorithm for solving selection of multimodal transportation scheme with several time windows[J]. Journal of Computer Applications，2013,33(9):2640-2642,2693.

Harmony Search Algorithm for Coordinated Scheduling in Production and Distribution of Fast Moving Consumer Goods

LIU Xing

(School of Management Engineering, Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450046, China)

Abstract：Considering the production setup decisions and limited inventory in plant and distribution center, capacity of plant and labor level, a mixed integer linear program model is presented to solve multi-period, multi-product, multi-plant, multi-distribution-center and multi-customer of fast moving consumer goods production and distribution coordinated scheduling plan which aims to minimize the production setup cost, production cost, inventory cost and distribution cost. A genetic harmony search algorithm is set up to solve the model. At last, an illustrative example is provided to show the applicability and usefulness of the proposed model and solution method.

Key words：production and distribution; fast moving consumer goods; coordinated scheduling; genetic harmony search algorithm

收稿日期：2015- 01- 27

基金項(xiàng)目：高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20100032110034)

作者簡(jiǎn)介：劉星(1983-)，女，貴州省人，講師，博士，主要研究方向?yàn)槲锪髋c供應(yīng)鏈管理.

doi:10.3969/j.issn.1007- 7375.2016.03.003

中圖分類號(hào)：F253.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-7375(2016)03- 0014- 04