劉金鳳 （1984-）
女，重慶潼南人，碩士研究生，主要研究方向為計算機控制與自動化網絡。現就讀于新疆大學電氣工程學院控制理論與控制工程專業。

基金項目：新疆制造業信息化科技示范工程 ——番茄醬廠生產過程信息集成及控制優化項目，自治區“十一五”規劃重點科技攻關項目（項目編號：200732142）

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

關鍵詞：供應鏈優化；遺傳算法；供應鏈優化模型

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 引言

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

2 供應鏈優化模型

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

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

   

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

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

3 遺傳算法在供應鏈優化中的應用

3.1 遺傳算法

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

    （1） 隨機產生一組初始個體構成初始種群，并評價每一個個體的適配。

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

    （3）根據適配值大小以一定的方式進行選擇操作。

    （4）按照交叉概率Pc執行交叉操作。

    （5）按照變異概率Pm執行變異操作。

    （6）返回步驟（2）。

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

3.2 基于遺傳算法的供應鏈優化求解

3.2.1遺傳編碼

    對于目標函數（1）的優化求解包含下列四類決策變量參數（它們都是整數變量）：

                                     圖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 面向供應鏈優化的遺傳算法

    步驟1：遺傳編碼。

    步驟2：初始化相關參數。

    步驟3：執行遺傳算法。

    步驟4：輸出結果。

4 算例

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

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

5 結論

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

    其他作者：梁蘭珍（1957-），女，碩士，教授，碩士生導師，主要研究方向為自動化儀表與過程控制、計算機控制應用技術等。現就職于北京聯合大學自動化學院。



參考文獻

[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]胡桂武.求解供應鏈優化問題的廣義遺傳算法[J]. 計算機工程與應用，2008.

[3]汪傳旭. 不同情形下供應鏈優化決策模型的比較分析[C]. 第三屆全國決策科學/多目標決策研討會論文集. 2005.

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

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