劉金鳳 （1984-）
女，重慶潼南人，碩士研究生，主要研究方向為計算機(jī)控制與自動化網(wǎng)絡(luò)?，F(xiàn)就讀于新疆大學(xué)電氣工程學(xué)院控制理論與控制工程專業(yè)。

基金項目：新疆制造業(yè)信息化科技示范工程 ——番茄醬廠生產(chǎn)過程信息集成及控制優(yōu)化項目，自治區(qū)“十一五”規(guī)劃重點科技攻關(guān)項目（項目編號：200732142）

摘要：本文以新疆某番茄醬廠番茄醬生產(chǎn)過程信息化項目為背景，主要針對生產(chǎn)計劃中的供應(yīng)鏈出現(xiàn)的問題，提出了一個新型供應(yīng)鏈優(yōu)化模型，并且采用遺傳算法對其求解。

關(guān)鍵詞：供應(yīng)鏈優(yōu)化；遺傳算法；供應(yīng)鏈優(yōu)化模型

Abstract: By analyzing the tomato paste production process in the tomato paste factory in 
Xinjiang , this paper proposes a new supply chain optimization model mainly for production
 planning in supply chain problems, and gives its solution by using genetic algorithms.

Key words: Supply chain optimization; Genetic Algorithm; supply chain optimization mode

1 引言

    目前中國已成為世界第三大番茄生產(chǎn)國和全球最大番茄醬出口國，到2006年新疆番茄的種植面積達(dá)100萬畝，年產(chǎn)達(dá)500萬噸。但是番茄種植戶的積極性并不高，主要原因是番茄醬生產(chǎn)受季節(jié)性限制。由于番茄的成熟季節(jié)比較集中，醬廠的生產(chǎn)能力有限，而儲存又很有難度，所以番茄種植戶在交售時也冒有很大風(fēng)險。為確保在榨季中醬廠的設(shè)備能夠滿負(fù)荷運(yùn)行，同時番茄供給時不會出現(xiàn)原料積壓或短缺，種植戶交售番茄長期排隊等情況，本文采用遺傳算法解決供應(yīng)鏈優(yōu)化問題。

2 供應(yīng)鏈優(yōu)化模型

    供應(yīng)鏈優(yōu)化問題的數(shù)學(xué)模型簡單地歸結(jié)為一個含約束條件的最小化問題，其目標(biāo)函數(shù)即庫存成本、制造成本、運(yùn)輸成本和短缺成本之和，如式(1)所示:
                                     （1）

    其中：
   
                                                                                （2）
   
                                                                                （3）
   
                                                                                 （4）
   
                                                                                 （5）
   
                                                                                 （6）
   
                                                                                 （7）
   
                                                                                 （8）
   
                                                                                 （9）
   
                                                                                 （10）
   
                                                                                 （11）

   

                                                                                 （12）
    其中：表示第p類單位產(chǎn)品在制造商處的處理時間（通常為固定常量）；表示第t階段制造商所允許的時間（通常為固定常量）；表示第p類單位產(chǎn)品從制造商運(yùn)送到第r個零售商的成本；表示每單位m類產(chǎn)品原材料從供應(yīng)商到制造商的運(yùn)送成本；表示每單位p類產(chǎn)品的制造成本；表示每單位p類產(chǎn)品從制造商到第r個零售商的短缺成本；表示第t階段從供應(yīng)商到第r個銷售商的第p類產(chǎn)品的需求；表示第m類單位原材料保存在制造商輸入倉庫的存儲成本；表示保存在制造商輸出倉庫的第p類產(chǎn)品的存儲單位成本；表示第p類產(chǎn)品保存在第r個分銷商的單位存儲成本；表示在開始第t個階段第m類原材料保存在制造商輸入處的數(shù)量；表示在第t個階段第p類產(chǎn)品存儲在制造商處的數(shù)量；表示在第t個階段第p類產(chǎn)品存儲在第r個銷售商處的數(shù)量；表示第m類原材料的單位重量；表示第p類產(chǎn)品的單位重量；表示在t時候從供應(yīng)商運(yùn)送到制造商的載重限制；表示在t時候從制造商運(yùn)送到分銷商的載重限制；表示第p類產(chǎn)品從制造商到第r個分銷商的數(shù)量；表示對于第p類產(chǎn)品每單位需求第m類原材料的必要數(shù)量。

    等式（2）、（3）、（4）和（5）是存儲、制造、運(yùn)輸和短缺成本的相關(guān)定義，等式（6）和（8）是說明銷售和制造成本必須為正，不等式（11）表示從供應(yīng)商到制造商的原材料數(shù)量必需為正，等式（7）限制了銷售規(guī)模，等式（9）限制了產(chǎn)品的容量，等式（10）和（12）限制了運(yùn)輸產(chǎn)品和原材料的總重量。

3 遺傳算法在供應(yīng)鏈優(yōu)化中的應(yīng)用

3.1 遺傳算法

    遺傳算法是基于自然選擇和遺傳學(xué)機(jī)理的迭代自適應(yīng)概率性搜索方法。GA實質(zhì)上是一個迭代過程，首先隨機(jī)形成初始種群，種群規(guī)模固定為N，接著進(jìn)行迭代，每次迭代都保留一組候選解，形成一個新種群，按照解的優(yōu)劣進(jìn)行排序，并按某種指標(biāo)從中選出一些解，進(jìn)行繁殖，交叉和變異等操作，產(chǎn)生新一代的候選解，重復(fù)此過程，直到滿足某種收斂指標(biāo)，求出最優(yōu)解或準(zhǔn)最優(yōu)解為止。傳統(tǒng)的遺傳算法的步驟為：

    （1） 隨機(jī)產(chǎn)生一組初始個體構(gòu)成初始種群，并評價每一個個體的適配。

    （2）判斷適配值收斂性是否滿足。若滿足則輸出搜索結(jié)果，否則執(zhí)行下步。

    （3）根據(jù)適配值大小以一定的方式進(jìn)行選擇操作。

    （4）按照交叉概率Pc執(zhí)行交叉操作。

    （5）按照變異概率Pm執(zhí)行變異操作。

    （6）返回步驟（2）。

    此算法中，適配值是對染色體（個體）進(jìn)行評價的一種指標(biāo)，是遺傳算法進(jìn)行優(yōu)化的主要信息，它與個體的目標(biāo)值存在一種對應(yīng)關(guān)系；選擇操作通常采用比例選擇，即選擇概率正比于個體的適配值，這就意味著適配值高的個體在下一代中復(fù)制自身的概率大，從而提高了種群的平均適配值；交叉操作通過交換兩父代個體的有效模式，從而有助于產(chǎn)生優(yōu)良個體；變異操作通過隨機(jī)改變個體中某些基因而產(chǎn)生新個體，有助于增加種群的多樣性，避免早熟收斂。傳統(tǒng)遺傳算法的流程圖描述如圖1所示。

3.2 基于遺傳算法的供應(yīng)鏈優(yōu)化求解

3.2.1遺傳編碼

    對于目標(biāo)函數(shù)（1）的優(yōu)化求解包含下列四類決策變量參數(shù)（它們都是整數(shù)變量）：

                                     圖1   遺傳算法的流程圖
   

    所以求該問題遺傳算法的染色體編碼為：X=((I) (J)，(K)，(Z))，其中(I) (J) (K)和(Z)是行向量，染色體首先的M(T-1)位代表Im，接下來的P(T-1)位代表Jpt，接下來的RP(T-1)位代表Krpt，最后的RTP位代表Zrpt。

3.2.2 面向供應(yīng)鏈優(yōu)化的遺傳算法

    步驟1：遺傳編碼。

    步驟2：初始化相關(guān)參數(shù)。

    步驟3：執(zhí)行遺傳算法。

    步驟4：輸出結(jié)果。

4 算例

    設(shè)供應(yīng)鏈優(yōu)化模型中的函數(shù)都設(shè)為常量，則與Mak和Wang模型完全一樣，并且假設(shè)所有的（原材料和產(chǎn)品）庫存是空的。由于醬廠只生產(chǎn)番茄醬，沒有其他產(chǎn)品，并且根據(jù)番茄的成熟期可分為2個階段，所以設(shè)M=1種原材料，P=2種產(chǎn)品，R=5個零售商，T=2個階段，產(chǎn)品在每一個階段的產(chǎn)品需求 Drpt預(yù)見如下：
   

    本文實驗采用傳統(tǒng)的遺傳算法，設(shè)定種群大小為50，交叉概率為0.25，變異概率0.01，采用二進(jìn)制編碼，輪盤賭選擇方法，交叉概率為0.25，變異概率0.01，按照上述的基本遺傳算法，在運(yùn)行到89代時獲得最佳個體。

5 結(jié)論

    本文對供應(yīng)鏈的優(yōu)化問題，建立新型供應(yīng)鏈模型，并采用遺傳算法對其求解，這種算法比較有效。但也存在不足，遺傳算法無法從根本上克服算法的“早熟”現(xiàn)象—局部最優(yōu)問題，以及收斂速度慢的缺點，這正是筆者今后研究的重點。

    其他作者：梁蘭珍（1957-），女，碩士，教授，碩士生導(dǎo)師，主要研究方向為自動化儀表與過程控制、計算機(jī)控制應(yīng)用技術(shù)等?，F(xiàn)就職于北京聯(lián)合大學(xué)自動化學(xué)院。



參考文獻(xiàn)

[1] Mak K L，Wong Y S.Design of integrated production-inventory-distribution systems using
 genetic algorithm[C] //Proceedings of the first International Conference on Genetic 
Algorithms in Engineering Systems: Innovations and Applications，Glasgow，UK，1995: 454-460. 

[2]胡桂武.求解供應(yīng)鏈優(yōu)化問題的廣義遺傳算法[J]. 計算機(jī)工程與應(yīng)用，2008.

[3]汪傳旭. 不同情形下供應(yīng)鏈優(yōu)化決策模型的比較分析[C]. 第三屆全國決策科學(xué)/多目標(biāo)決策研討會論文集. 2005.

[4] 張麗霞，鄒明能，唐萬生. 基于遺傳算法的Multi-agent技術(shù)在供應(yīng)鏈中的應(yīng)用[C]. 第五屆中國青年運(yùn)籌與管理學(xué)者大會論文集，2003.

[5] 聶蘭順，徐曉飛，戰(zhàn)德臣. 基于拉格朗日松弛和遺傳算法的供應(yīng)鏈協(xié)同計劃[J]. 計算機(jī)集成制造系統(tǒng)，2006，12(11).