企业简介

作为中国自动化领域的权威旗舰网络媒体，控制网创立于1999年7月，是中国举行的第十四届IFAC （International Federation of Automatic Control）大会的中国官方组织机构的唯一指定网站。控制网是中国自动化学会专家咨询工作 委员会（ECC）的秘书处常设之地。是北京自控在线文化传播有限公司开设的网站。

  • 公司类型：其他

联系方式
  • 控制网
  • 地址：北京市海淀区上地十街辉煌国际2号楼1504室
  • 邮编：100085
  • 电话：010-57116291 / 59813326
  • 传真：010-59813329
  • 网址：http://www.kongzhi.net
  • Email：mahongliang@kongzhi.net
  • 联系人：市场部
案例详细
标题遗传算法在供应链优化问题中的应用
技术领域工控机
行业
简介本文以新疆某番茄酱厂番茄酱生产过程信息化项目为背景，主要针对生产计划中的供应链出现的问题，提出了一个新型供应链优化模型，并且采用遗传算法对其求解。
内容









刘金凤 （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).