徐平平,郭蕴华

(武汉理工大学a.能源与动力工程学院； b.船舶动力工程技术交通行业重点实验室，武汉 430063)



基于改进蚁群算法的不定长原管一维下料废料率优化

徐平平,郭蕴华

(武汉理工大学a.能源与动力工程学院； b.船舶动力工程技术交通行业重点实验室，武汉 430063)

针对船厂不定长原管一维下料废料率问题，提出一种改进的蚁群算法，按尽量利用余料和较短管材的原则选取原管，以蚂蚁转移路径和信息素矩阵表示原管和胚料管之间的关联关系，并据此选取胚料管。仿真实验表明，改进蚁群算法比已有算法可以得到更佳的最优解，且能明显降低管材的废料率。

改进蚁群算法; 一维下料; 不定长管材；废料率

管材加工是除船体结构外工作量最大的工种，一艘船有几十个系统，约万根管材，提高管材利用率成为降低成本的关键因素之一。管材加工过程中存在余料和废料，二者以某个阈值划分。如果余料长期不进行利用，不但增加管材的浪费，也给船厂库存也带来较大的压力。在下料时，尽量利用余料是控制成本的有效手段。管材下料属于一维下料问题，该问题是NP难题[1]。求解该问题的方法包括：①经典方法，如线性规划[2]，分支定界法[3]等；②启发式算法，如混合顺序启发式算法文献[4]，蚁群算法[5]。经典方法只能求解中小规模的下料问题，当管材下料的数量较大时，问题的规模会指数增加，难以获得较优解。相比较而言，各种启发式算法更适合求解大规模组合优化问题，可以在有限时间内获得满意解。不过，已有的各种启发式算法都是针对原材料管为定长的情形而设计的，但实际生产过程中极有可能遇到不定长原管的下料问题。这是因为：①存在余料，而余料不可能是定长的；②为节约成本，船厂采购了价格相对低廉不定长原管。为此，针对不定长原管一维下料问题，提出改进的蚁群算法。该算法按尽量利用余料和较短管材的原则选取原管；以蚂蚁转移路径和信息素矩阵表示原管和胚料管之间的关联关系，并据此选取胚料管。

1　数学模型

大部分一维下料问题，都是针对原材料为定长情况来建立数学优化模型，而船厂为了节约成本，大都购买不定长管，且余料也需用掉，因此在使用原材料管时，以不定长来建立模型，对每一根原材料管按长度升序单独编号。而船厂所需的胚料管，相同管径、管厚和长度的管材很少，对每一根胚料管也按长度升序单独编号。文献[6]研究了不定长的优化模型，文献[7]研究了可用余料问题，参考二者，根据船厂管材下料的实际情况，定义原材料管的集合为M管，定义胚料管的集合为C管，建立使原管的剩余长度最少的数学模型。

(1)

式中：m——已选用原材料管的根数；

Li——原材料管的长度，i=1,2,…,m；

n——胚料管的根数；

lj——胚料管的长度，j=1,2,…,n；

yi——每根已选中M管的剩余长度，若yi≤lmin(lmin为阈值)，则记为废料，否则为余料；

xij——决策变量，若第i根M管上切割第j根C管，则xij=1，否则xij=0；

δ——切割刀缝宽度。

2　改进的蚁群算法求解

2.1蚁群算法的基本原理

蚁群算法是一种基于种群的启发式仿生进化算法，实现过程主要体现在蚂蚁路径节点转移，和信息素更新两方面[8]。具体公式如下：

1)路径节点转移公式。

(2)

式中：q——[0,1]之间均匀分布的随机数;

1)积极引进国内外知名MOOCs课程体系，并重点建设本专业自己的MOOCs课程和翻转课堂教学模式，并应用于课程教学中，目前已完成3门专业课程的MOOCS建设和3门专业课程的“翻转课堂”教学模式的建设，并都应用于相关课程教学改革的实施中。

q0一般取0.25～0.85。

2)信息素更新公式。

(3)

(4)

式中：Q——常数；

Lbest——每代蚂蚁最优路径的值，并限定τij(t+1)∈[τmin,τmax][8]。

2.2改进的蚁群算法

船厂管材一维下料问题求解过程可以描述为：在M管选取一根管，从C管选取若干根管，使选出的M管用尽；然后再选取下一根M管，继续上述过程，直至所有C管都完成下料。求解该问题有两个关键：①M管的选择问题，M管的选择不仅影响最优解的求解，同时也影响余料的利用；②C管的选择问题，即正反馈机制如何发挥作用。针对以上两点，提出相应的改进策略。

2.2.1策略1

M管的选择：余料管能够尽量利用，关键在于较短的M管能够优先被选中，可按如下步骤实现。

步骤1求出C管中未被选用的最长一根管的长度，记为cmax。

步骤2为了选中较短的M管，根据下面公式来选定第k根M管。

(5)

步骤3通过分析仿真结果可知，若能将很短的C管挤到M管中被切割，这样可能放弃选中较短的M管，但是降低了M管的总管数，有可能获得更好的最优解，因此在步骤2的基础上给cmax加上一个正的随机数r，按式(6)重新选取M管。

(6)

2.2.2策略2

C管的选择：文献[9-11]设计的蚂蚁转移路径和信息素矩阵，表示C管与C管之间的关联关系，但这种方法有待商榷：①针对同一根M管，C管和C管可以有关联关系，但在不同的M管上，两者并没有关联关系，造成启发因子的关系式不明确；②给定M管选取第一根C管时，存在着随机选取，若未能选取合适的第一根C管，将大大增加寻优难度。因此，本文算法中蚂蚁转移路径和信息素矩阵表示M管和C管之间的关联关系，具体选管步骤如下。

步骤1将M管和C管统一编入节点集合，则城市数为Zcity=m+n(m为M管的数量，n为C管的数量)，每只蚂蚁所走过的路线对应着一个切割方案，将节点分为M管节点和C管节点。

步骤2根据策略一，选取M管，计算C管的可选集，M管到C管的节点选择依据公式(2)，以选定的M管的剩余长度的倒数作为启发因子。

式中：ml——选定M管的长度；

cl——选定C管的长度。

步骤3C管到M管的节点：若选定的M管还可以供C管继续用，M管节点不变，否则依据策略1，重新选取M管，作为新的节点。

3　仿真及实验结果分析

本算法在48根M管的基础上切割98根C管，数据如表1、2所示。

C管的总长为193.446 m，每个切缝的宽为0.005 m。在Java编程环境下对船厂管材一维下料问题进行的仿真，参数选择为α=2，β=8，ρ=0.3，Q=1 000，τmin=10，τmax=1 000，q0=0.25，蚂蚁数为30，迭代次数为100代，策略1的随机数为0～1.5，将M管中剩余长度大于0.05 m的管作为余料管。

表1　M管的数据　m

表2　C管的数据　m

文献[9]研究的是原材料为定长的问题，在其基础上考虑策略1，使其适应不定长问题(以下简称“文献算法”)。对文献算法和本文算法进行对比试验，每种算法各仿真计算100次。仿真实验结果见表3和图1。

表3　仿真数据对比　m

图1　平均最优解的进化

从仿真结果中可以看出：

1)本文算法全局最优解为0.665 m，经计算下次可利用的余料管总长共0.225 m，管材的废料率为0.48%，实际船厂的管材下料废料率大概在3%～5%左右。这表明针对M管选择的改进策略1，不仅使管材利用率提高，同时也使余料被尽量使用。

2)本文算法的全局寻优能力和收敛速度都好于文献算法。这表明针对C管选择的改进策略2，对提高算法的性能有显著的影响。

4　结论

所提出的基于改进蚁群算法的船厂不定长原管一维下料方法，使管材废料率降低到0.48%，且能利用余料，在同文献算法进行对比实验，不仅提高了算法的全局寻优能力，也加快了算法的收敛速度，表明本文算法在优化船厂管材下料废料率问题是可行的。将本文算法应用到船厂管材下料中，不仅降低船厂管材下料的废料率，也降低管材余料的库存，可以产生很好的经济性。在下一步研究中，将尝试根据本文算法开发成管材下料软件，使其产生工程价值。

[1] PARMAR K B, PRAJAPATI H B, DABHI V K. Cutting stock problem: A survey of evolutionary computing based solution [C]∥Green Computing Communication and Electrical Engineering (ICGCCEE), 2014 International Conference on IEEE, 2014:1-6.

[2] CUI Y, YANG Y. A heuristic for the one-dimensional cutting stock problem with usable leftover [J]. European Journal of Operational Research, 2010,204(2):245-250.

[3] ALVES C, CARVALHO J M V D. A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem [J]. Computers & Operations Research, 2008,35(4):1315-1328.

[4] 程浩,刘心报,方昶.基于混合顺序启发式算法的一维下料问题[J].中国机械工程,2014,25(16):2191-2195,2203.

[5] JIN Peng, ZHANG Shu， Chu. A hybird ant colony algorithm for the Cutting Stock Problem[C]∥Future Information Technology and Management Engineering(FITME), 2010 International Conference,2010(2):32-35.

[6] GRADISAR M, TRKMAN P. A combined approach to the solution to the general one-dimensional cutting stock problem [J]. Computers & Operations Research, 2005,32(7):1793-1807.

[7] CHERRI A C. The one-dimensional cutting stock problem with usable leftover-A heuristic approach [J]. European Journal of Operational Research, 2009,196(3):897-908.

[8] STüTZLE T, HOOS H H．Max-min ant system [J]. Future Generation Computer System, 2000,16(8):889-914.

[9] 吴正佳,张利平,王魁.蚁群算法在一维下料优化问题中的应用[J].机械科学与技术,2008,7(12):1681-1684.

[10] LU Q, WANG Z, CHEN M. An ant colony optimization algorithm for the one-dimensional cutting stock problem with multiple stock lengths [C]∥ Fourth International Conference on Natural Computation IEEE Computer Society, 2008:475-479.

[11] YANG B, LI C, HUANG L, et al. Solving one-dimensional cutting-stock problem based on ant colony optimization [C]∥Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDCIEEE Computer Society, 2009:1188-1191.

An Improved Ant Colony Algorithm for the Optimization to Scrap Rate of One-dimensional Cutting Stock with Multiple Stock Lengths

XU Ping-ping, GUO Yun-hua

(a.School of Energy and Power Engineering, Wuhan University of Technology; b.Key Laboratory of Marine Power Engineering and Technology of Ministry of Communications, Wuhan University of Technology, Wuhan 430063, China)

An improved ant colony algorithm is proposed for the scrap rate of one-dimensional cutting stock with multiple stock lengths in ship building. In that algorithm, the stocks is selected according to the principle of utilizing the remnant stocks and the shorter stocks as much as possible, while the ant path and pheromone matrix represent the relations between the stocks and the items by which the items is selected. The simulation results show that the proposed algorithm can get the superior optimal solution, and its pipe scrap rate is lower.

improved ant colony algorithm; one-dimensional cutting stock; multiple stock lengths; scrap rate

10.3963/j.issn.1671-7953.2016.01.022

2015-09-23

2015-11-03

国家自然基金项目(51579201)

徐平平(1988-)，男，硕士生

U664.84

A

1671-7953(2016)01-0113-04

研究方向:信息融合与工程优化

E-mail:1404247066@qq.com