基于改进蚁群算法的实物效率型供应链网络生产决策毕业论文.docx

基于改进蚁群算法和面向订单的实物效率型供应链生产决策
摘要：针对面向订单生产的多规格多产线实物效率型供应链生产作业，以生产成本和销售利润为目标，构建有限产能下带有限延迟交货惩罚的生产模型。利用蚁群算法在求解复杂优化问题方面的优越性，设计改进的蚁群优化算法。对传统蚁群算法的概率选择函数进行改进，将选择概率分为产线选择概率和订单选择概率，在选取状态转移规则确定下一个订单时，采取随机比例规则与贪婪规则相结合的策略。在保留最适应个体时将精英蚂蚁策略与四种邻域搜索结合。将改进的蚁群算法应用到实际企业生产算例中，结果表明，无论是计算结果还是计算效率，改进蚁群算法在解决多订单多规格的实物效率型供应链生产作业问题上均优于传统蚁群算法。实证研究证明了模型、算法的可靠性及适用性，将算法和模型应用于生产决策，增加了订单处理数量，提高了销售利润。
关键词：改进蚁群算法，实物效率型供应链，面向订单，生产决策
中图分类号：F272.2文献标识码：A　文章编号：
Efficient supply chain planning based on Improved Ant Colony Algorithm and Make-to-order strategy
Abstract: A make to order problem with multi type and multi production line into consideration in efficient supply chain planning is investigated. Limit production capacity and back order punishment are taken into account in maximize profit objective model. Considering thesuperiority of ant colony algorithm in solving the complex problem， an improved ACO algorithm is proposed. The improved ACO algorithm processes selective probabilityof both production line and order. Strategy combined with random select rule and greedy select rule are chosen to select next orders. When keeping best generation, elite antstrategy with four different local search methods are used. Computational results indicate that the improved ACO algorithm performance better in calculating efficiency and planning outcomes. The implement of model and algorithm in real-life case also demonstrates that the gross profit and order acceptance respectively enhanced.
Key words:Improved ant colony algorithm;Efficient supply chain;Make to order; Planning

生产制造是供应链中必不可少的环节。为进行科学有效的生产决策，M.L.Fisher[1]对企业产品进行分类，将生产制造型的供应链分为实物效率型和市场反应型，并指出对于前者，降低成本，提高设备利用率是关键。不少学者从节约成本满足需求，提高设备利用率和库存周转率方面做了大量深入的研究[2-5]。
近年来，由于信息化管理程度的提高，以及面向订单生产方式研究的深入[6-11]，一部分实物效率型生产企业已经从面向库存生产转为面向订单生产。在这种生产模式下，由于生产能力的限制，企业需要从众多订单中选择合适的订单安排生产。若订单选择不合理，在实际生产中必然或造成诸如产能过剩或不足的情况。同时，产品的交付期限也对企业的订单生产的合理安排提出了更高的要求。文献[12]提出了面向订单的钢铁企业生产管理一体化系统，为钢铁企业面向订单的生产决策提供了框架。文献[13]研究了合同生产批量调度方法并用蚁群算法进行求解，不过模型考虑的是多品种小批量的生产计划编制。文献[14]研究了ERW钢管多阶段生产计划的编制与优化，提出带提前交货惩罚与延期惩罚的订单生产计划模型，却没有考虑多产线的生产。文献[15]研究了带非等效并行机的作业计划问题，并基于两阶段蚁群算法对计划模型求解，但是只把惩罚成本最小作为目标。同时这两篇文献提出的模型中没有考虑多产线的情况，生产原料和延期惩罚也是没有限制的。这不符合实际的实物效率供应链生产情况。针对以上问题及难点，本文以某钢铁企业为项目背景，提出了多规格多产线有限产能有限物料下带有限延迟交货惩罚的订单生产决策模型。模型建立时，考虑多产线生产能力和订单延迟对生产的影响，以生产利润最大化为目标建立最优生产决策模型。模型求解时，考虑传统蚁群算法易陷于局部最优，收敛速度慢的缺点，提出了改进的蚁群算法对模型进行求解。针对性地将订单综合优先级加入概率选择中，将概率选择分为产线和订单两种概率选择。采用随机比例规则与贪婪规则相结合的策略，并将蚁群算法与邻域操作相结合，使得算法能以更快的速度探索全局最优解。基于文本的模型和算法，企业可以在生产能力范围内有针对性地安排订单，实现公司生产能力合理利用和利润最大化。最后针对某钢铁集团进行实证研究，证明模型、算法的可靠性及适用性，为企业决策提供量化依据。
1问题定义及模型假设
本文的研究对象是拥有单产品多规格多产线的实物效率型供应链，讨论的重点在于适合生产能力前提下，确定最优的订单选择策略。本文建立在下列假设基础之上：
1) 任意一个产品只能在某唯一产线上生产，各产线的生产能力可以也可以不同。
2) 每项生产操作相互独立，没有完成的作业不可以中断，生产作业也无法拆解为更小的子作业。
3) 订单数量和产线的数量是有限的，分别表示为和。
4) 对于每一个订单，都对应唯一的订单编号，，每一条生产订单的产线，也对应唯一的编号，。订单若被安排生产，则该订单拥有唯一的生产序列标识；
5) 每生产一个订单，都需要消耗锌、铝合金和铅3种不同的材料。材料的消耗系数和可用总量分别为，。
6) 生产订单的耗时是确定的；
7) 产线的生产能力有限，产线的总生产能力表示为
8) 产线对订单的单位生产的能力为；
9) 每一笔订单的订货量，单位销售价格和生产成本都是大于零的实数；
10) 每一笔订单都有确定的交货期，允许交货延迟；
11) 订单交货延迟时，订单的单位延迟惩罚系数；
12) 订单必须在最迟交货期内完成，否则就算完成也不能获得任何收入。
13) 生产过程中会产生废品，废品不能进入生产序列再加工。订单在产线上的成品率为
2生产决策模型
每生产一笔订单，企业都会获得相应的收益。若该订单出现交付延期，则会造成相应的损失，同时考虑到企业的生产能力有限，本节将目标函数设为公式（1）。企业在满足生产能力和资源能力约束限制下，选择匹配的订单，实现生产利润最大化。
(1)
约束条件（2）表示企业所接收的订单需要被排在产线订单序列的某一具体位置，但未被接受的订单不能出现在订单序列之内。其中，表示能否接收订单，接收则，否则；表示若订单被接收且处于产线订单顺序的位置，则，否则
(2)
约束条件(3)规定产线订单序列的任一位置最多只能放入一个订单。
(3)
约束条件(4)限定订单必须在最迟交货期内完成，否则就算完成也不能获得任何收入。
(4)
约束条件(5)表示各产线的实际消耗的材料不能超过其最大生产能力。
(5)
约束条件(6)、(7)、(8)表示所接受订单的所需要消耗的锌、铝合金和铅总量不能超过已有的生产资源。
(6)
（7）
（8）
3模型求解及算法设计
考虑到模型的复杂性 ，本文采用蚁群算法求解。蚁群算法是一种结合了分布式计算和正反馈机制的算法，具有较强的搜索较优解的能力和稳健性，易于其他算法相结合，具有很强的并行性特点。但蚁群算法也有其缺点：易陷于局部最优，收敛速度慢。蚁群算法中先行蚂蚁的行为会影响后来蚂蚁的选择，这种引导行为可能会导致算法陷入局部最优，容易早熟。本文从以下三个方面对传统的蚁群算法进行改进。
3.1 选择策略
定义初始化订单在产线的位置上的信息素浓度为三维矩阵。表示各订单在产线上的执行概率。初始状态时蚂蚁在各路径的信息素均为常数。
（9）
其中，为订单在产线上的平均生产时间
本节对传统蚁群算法的概率选择函数进行改进，将选择概率分为产线选择概率和订单选择概率。产线选择概率表示订单在各产线上执行的概率；订单选择概率表示订单在各产线加工位置上执行的概率。此外，本文把订单综合优先级加入到概率计算公式之中，这样蚂蚁可以全面地根据自身信息寻找最优路径。和的计算方法如公式（10），（11）所示。
（10）
（11）
公式（11）中，，为信息素和启发函数重要程度因子；为启发函数，。各指标的含义如表1所示。
表1 启发函数计算指标
Tab.1 Heuristic function parameters
指标
转换公式（无量纲化）
加权系数
订单耗时利润

订单紧急度

其中，为订单的在各产线上的平均加工时间；为生产计划期终止日期。
在选取状态转移规则确定下一个订单时，传统蚁群算法主要依靠单一的概率选取最佳路线，但容易很快失去解的多样性。为改善这一问题，本节随机比例规则与贪婪规则相结合的策略。随机比例规则中的轮盘赌法的随机倾向性加大了蚁群选取较优路径边的机率，而贪婪规则中的贪心算法的针对性则提高了算法搜索全局最佳路线的集中性，可以增加蚁群算法的搜寻效率。引入参数（），在选择下个订单时，如果随机参数，那么按照贪婪规则选取最优的订单，不然根据随机比例规则进行轮盘赌选取。计算方法如公式（12）所示。
（12）
3.2 信息素更新机制
最优路径更新策略表示只有最佳的蚂蚁才能够放出信息激素。信息素按照如公式（13）进行更新。
（13）
其中，是信息激素浓度，是最佳路径的结果值，是挥发系数
3.3 精英蚂蚁策略
精英蚂蚁策略是保留住一代中的最适应个体。为了让本轮的最优解在下一次迭代中对蚁群更具吸引性，本文在每次迭代之后选择排名前10的精英蚂蚁，结合以下4种邻域操作进行局部搜索。
交换变异：随机取出2个订单，交换二者，如图1所示。

图1 交换变异
Fig.1 Mutation exchange
前移变换：随机取出一个订单，把它随机排在原有序列的前面，如图2所示。

图2前移变换
Fig.2 Forwardexchange
后移变换：随机取出一个订单，把它随机排在原有序列的后面，如图3所示。

图3后移变换
Fig.4 Backward exchange
订单插入变换：第一步随机挑选未被选择的订单，将其随机加入到已有的生产序列内生成新的生产序列。新订单的插入可能会使个别插入点之后的订单交付延期，利润变为负而被放弃。如图4所示，随机加入为被选择的订单5后，订单9由于拖期罚款高于所得而被放弃。

图4订单插入变换
Fig.4 New orderinsertion
3.4 算法整体流程
图5改进蚁群算法流程图
Fig.5 Flow chart for improved ant colony algorithm
图5为改进蚁群算法的流程图，算法过程如下：
1) 初始化参数。在计算之初，需要根据实际问题设置参数，设蚂蚁规模为Ant，最大迭代次数为MaxT，迭代次数初值Iter=1；
2) 产线选择。按信息素矩阵，采用随机比例规则的贪婪算法和轮盘选择进行产线选择。
3) 构建所有蚂蚁的解空间集合，将时刻可在产线位置上执行的订单放入可选订单集合中；
4) 订单的选择。根据随机比例公式运算出所有蚂蚁可选取的订单概率，然后再利用随机比例规则选取后一订单；
5) 修改可允许操作集合，当蚂蚁移动到目标位置时将该订单从集合中删除，计算所选目标订单是否满足利润和产能约束，若不满足那么跳到步骤4，否则转向步骤6；
6) 如果蚂蚁没有经过全部的位置，中仍留有未完成的订单，则转向步骤2，否则转向步骤7；
7) 选择排位前10的精英蚂蚁随机实行邻域操作；
8) 重新计算最优解和最佳路线中的信息激素浓度；
9) 判断进程目前是否符合IterMaxT结束条件。如果符合则结束算法，否则更新所有参数和排序并跳转执行步骤2。
4实证研究及结果分析
为验证本文所提出算法的有效性，采用某钢铁企业的实际生产数据进行研究。
生产规模：该企业共可生产45种规格的镀锌管产品，产线生产能力和物料总量限制见表2和表3。每种规格产品的生产成本、加工能力、耗锌系数、耗铝合金系数和耗铅系数、成材率统计结果如表4所示。
计划期：计划期为30天。
订单规模：选择该企业3月份实际订单，总量为150个。
表2产线能力
Tab.2 Production capacity for each line
生产线
规格范围
生产能力(吨/小时)
1
20.5-48.5
600
2
20.5-60.5
600
3
20.5-60.5
600
4
32.5-114.0
600
5
32.5-114.0
600
表3 物料总量
Tab.3 Total amount of materials
耗材
重量（吨）
锌
1450
铝合金
1210
铅
850

表4各规格镀锌管工艺参数
Tab.4 Process parameters for each type of galvanized pipe
产品规格
生产成本
加工能力
（吨/小时）
生产时间
耗锌系数
耗铝合金系数
耗铅系数
平均成材率
26.3X2.5X6.0
1012.02
4.13
145.28
0.083
0.073
0.03
0.9589
42.0X2.75X6.0
1121.21
4.08
147.06
0.091
0.081
0.036
0.9628
25.8X2.5X6.0
1012.02
4.1
146.34
0.081
0.067
0.028
0.9589
48.0X3.5X6.0
939.98
4.425
13559
0.076
0.062
0.023
0.9523
25.5X1.8X6.0
1365.08
3.67
163.49
0.106
0.084
0.043
0.9589
32.5X2.2X6.0
1119.99
4.08
147.06
0.086
0.079
0.038
0.9746
75.0X3.25X6.0
713.58
4.67
128.48
0.058
0.037
0.015
0.9631
41.5X2.5X6.0
1220.08
3.96
151.52
0.091
0.08
0.037
0.9628
20.5X1.8X6.0
1415.9
2.92
205.48
0.106
0.087
0.048
0.9561
33.0X2.75X6.0
918.76
4.17
143.88
0.069
0.049
0.018
0.9746
42.0X3.0X6.0
994.44
4.17
143.88
0.079
0.069
0.027
0.9628
21.3X2.75X6.0
966.02
4.08
147.06
0.072
0.061
0.023
0.9561
47.0X3.0X6.0
1148.37
4.375
137.14
0.086
0.075
0.035
0.9523
60.3X3.5X6.0
876.86
4.67
128.48
0.068
0.047
0.021
0.9837
32.5X2.5X6.0
992.84
4.15
144.58
0.082
0.061
0.024
0.9746
88.5X3.25X6.0
825.29
4.67
128.48
0.065
0.042
0.015
0.9852
48.3X3.5X6.0
876.86
4.425
135.59
0.068
0.047
0.021
0.9523
26.5X2.75X6.0
928.76
4.15
144.58
0.071
0.060
0.022
0.9589
59.5X3.25X6.0
939.98
4.76
126.05
0.072
0.061
0.023
0.9837
20.5X2.0X6.0
1284.95
3.25
184.62
0.097
0.084
0.043
0.9561
59.0X2.75X6.0
1148.37
4.58
131.00
0.087
0.073
0.035
0.9837
75.0X3.0X6.0
764.74
4.67
128.48
0.060
0.039
0.017
0.9785
20.8X2.5X6.0
1041.26
3.83
156.66
0.085
0.072
0.035
0.9561
47.0X2.5X6.0
1376.83
4.375
137.14
0.098
0.086
0.045
0.9523
60.3X2.75X6.0
976.86
4.67
128.48
0.081
0.053
0.028
0.9837
26.0X2.2X6.0
1114.8
3.86
155.44
0.084
0.073
0.032
0.9589
75.0X3.5X6.0
718.42
4.67
128.48
0.058
0.037
0.015
0.9824
41.5X1.8X6.0
1343.34
3.75
160.00
0.100
0.088
0.046
0.9628
60.3X3.75X6.0
780.17
4.67
128.48
0.061
0.040
0.018
0.9828
33.5X3.25X6.0
804.91
4.17
143.88
0.065
0.055
0.018
0.9746
114.0X3.25X6.0
660.65
4.835
124.10
0.055
0.035
0.014
0.9655
25.5X2.0X6.0
1230.58
4.08
147.06
0.093
0.081
0.04
0.9589
47.5X3.25X6.0
1018.18
4.425
135.59
0.085
0.072
0.035
0.9523
48.5X3.5X6.0
876.86
4.425
135.59
0.067
0.057
0.021
0.9523
60.3X3.0 X6.0
918.34
4.67
128.48
0.070
0.059
0.021
0.9793
33.0X3.0X6.0
857.15
4.17
143.88
0.066
0.056
0.019
0.9746
59.0X3.0X6.0
1018.18
4.58
131.00
0.084
0.056
0.033
0.9837
88.5X3.5X6.0
649.42
4.67
128.48
0.052
0.032
0.011
0.9741
59.0X2.5X6.0
1249.89
4.58
131.00
0.095
0.083
0.042
0.9837
47.5X3.0X6.0
1130.37
4.425
135.59
0.086
0.076
0.037

0.9523
88.5X3.0X6.0
699.94
4.67
128.48
0.055
0.035
0.014
0.9741
42.3X3.25X6.0
918.34
4.375
137.14
0.07
0.060
0.02
0.9628
75.0X2.75X6.0
823，55
4.67
128.48
0.065
0.042
0.015
0.9852
47.0X2.75X6.0
1249.89
4.375
137.14
0.095
0.083
0.042
0.9523
20.8X2.2X6.0
1172.08
3.75
160.00
0.087
0.076
0.038
0.9561
（1）选择策略比较。本文选择轮盘赌+贪心的选择策略，与传统蚁群算法相比，用实际数据运算，每组数据运行20次，结果比较见表5。
表5 不同选择策略对计算结果的影响
Tab.5 Computational performance under different choose strategies
选择策略
订单规模
平均目标值
最好目标值
最差目标值
平均偏差
轮盘赌
150
42871224
42888538
42857224
0.45%
轮盘赌+贪心
150
42881155
42890511
42868284
0.41%
从表5可以看出，总体来讲选择贪心准则和轮盘选择准则相结合的选择策略要比单一轮盘赌策略效果好，平均目标值和平均偏差均有改善。因此，本论文应用轮盘赌和贪心准则的结合选择策略是可行且较优的。
（2）信息素更新机制比较。本课题选用更新最佳路径的策略以更新信息素。对另外两种传统信息素更新机制，每组数据运行20次，运行结果如表6所示。
表6不同信息素更新机制对计算结果的影响
Tab.6 Computational performance under different pheromone laying mechanisms
算法
更新方法
平均目标值
最好目标值
最差目标值
平均偏差
改进算法
最优路径更新
42881155
42890511
42868284
0.41%
传统算法
最优—最差蚂蚁
42870370
42887719
42853951
0.47%
最大—最小蚂蚁
42861053
42876729
42846170
0.51%
总体来说，改进的信息素更新机制获得的结果好于其余两种传统方法。横向对比来看，最大—最小蚂蚁结果最不理想，最优路径方法三个目标值都达到了良好的结果。
（3）有无邻域搜索比较。本文将蚁群算法与邻域操作相结合，将每次循环的前10名精英蚂蚁进行多种邻域搜索变换，来增加寻优能力及效率。每组数据运行20次，结果见表7。
表7 局部搜索对计算结果的影响
Tab.7 Computational performance under different search strategies
算法设计
平均目标值
最好目标值
最差目标值
平均偏差
无邻域搜索
42881155
42890511
42868284
0.41%
有邻域搜索
42892656
42894827
42869293
0.39%
从表7可以看出，相比传统蚁群算法，增加局部搜索的算法计算的结果其三个目标值都有提升，平均偏差降低，这就意味着该算法能搜寻到更好的解，解的效果得到提升。
（4）各产线订单接受情况如表8所示：
表8 基于改进蚁群算法优化的生产策略
Tab.8 Production plan based on improved ACO
产线
接受订单个数
放弃订单个数
惩罚成本
1
26
6
541125
2
26
5
577100
3
23
9
438972
4
23
3
41772
5
24
5
705357

各产线产能利用率及利润情况如图6所示。

图6产能利用率及总利润
Fig.6 Capacity utilization and profit of each production line
从图中可以看出，进行订单选择后，各时段的产能利用率均在88%以上，平均产能利用率达到93.24%，订单接受率为81.33%，可以满足企业生产的需要。对于没有被接受的订单，企业可以根据实际情况与客户商讨后，将订单转下月生产或取消订单。

图7两种算法计算结果对比
Fig.7 Comparison of computational results using ordinary ACO and improved ACO
图7为三种订单规模下传统蚁群算法与改进蚁群算法的实验结果对比。从图中可以看出，与传统的蚁群算法计算结果相比，本文提出的改进遗传算法在平均产能利用率上提高了5.18%，订单接受率提高了3.17%，总利润相比提高了11.2%。
5结论
针对实物效率型供应链生产的特点，本文考虑多产线生产能力和订单延迟对生产的影响，以生产利润最大化为目标建立最优生产决策模型。模型求解时，提出了改进的蚁群算法，采用轮盘赌+贪心的选择策略，利用最优路径更新信息素，结合四种不同的邻域搜索方法对模型进行求解。
企业实际案例的算例表明，采取订单选择的生产决策策略，不仅可以最大程度的实现销售利润，还可以平衡产能负荷，满足企业的产能需求。采用改进的蚁群算法求解模型，不仅可以获得较传统蚁群算法更好的计算结果。实证研究证明了本文提出的模型及算法优越性，能够生产多订单为多规格的实物效率型企业在激烈的市场竞争环境下提供实际、有效的生产决策支持。

参考文献：
[1] M.L. Fisher, “What is the right supply chain for your product?”, Harvard Business Review,1997, pp. 105-16.
[2] Yan Hongsen, Zhang Xiaodong, Jiang Min.Hierarchical production planning with demand constraints[J] .Computers &IndustrialEngineering , 2004 , 46(3):533-551.
[3] Jain A,Palekar U S.Aggregate production planning for a continuous reconfigurable manufacturing process [J] .Computers &Operations Research, 2005 , 32(5):1213-1236.
[4] PradenasL.Penailillo F.Aggregate production planning problem:A new algorithm [J] .Electronic Notesin Discrete Mathematics,2004, 18(1):193-199
[5]陈淮莉,张洁,马登哲. 基于成本和时间平衡优化的供应链协同计划研究[J]. 计算机集成制造系统,2004,12:1518-1522.
[6] Carr S,Duenyas I. Optimal admission control and sequencing in a make-to-stock/make-to-order production system [J]. Operations research, 2000, 48(5): 709-720.
[7] Aouam T, Brahimi N. Integrated production planning and order acceptanceunder uncertainty: A robust optimization approach[J].European Journal ofOperational Research,2013, 288(3): 504-515
[8] Su N, Zhang M, Mark J, et al. Learning Reusable Initial Solutions forMulti-objective Order Acceptance and Scheduling Problems with GeneticProgramming [J].Letter Notes in Computer Science,2013,7831, 157-168.
[9] Gunasekaran A, Ngai E W T.Build-To-Order supply chain management:A literature review and framework for development[ J] .Journal of Operations Management , 2005 , 23(5):423-451.
[10]V.P.E. A. Tamilarasl. Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems. Int J AdvManufTechnol， 2009,40:1004- 1015.
[11] Youssef K H, Van Delft C,Dallery Y. Efficient scheduling rules in a combined make-to-stock and make-to-order manufacturing system [J]. Annals of Operations Research, 2004, 126(1-4): 103-134.
[12]蔡洋,李铁克. 面向订单的钢铁企业生产管理一体化系统[J]. 北京科技大学学报,2008,03:302-306.
[13]王利,高宪文,王伟,王琦. 基于模型的子空间聚类与时间段蚁群算法的合同生产批量调度方法[J]. 自动化学报,2014,09:1991-1997.
[14]陈超武,董绍华,丁文英. ERW钢管多阶段生产计划的编制及优化[J]. 北京科技大学学报,2006,07:691-695.
[15]张洁,张朋,刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度[J]. 机械工程学报,2013,06:136-144