基于改進(jìn)蟻群算法的不定長原管一維下料廢料率優(yōu)化

徐平平,郭蘊(yùn)華

(武漢理工大學(xué)a.能源與動力工程學(xué)院； b.船舶動力工程技術(shù)交通行業(yè)重點(diǎn)實(shí)驗(yàn)室，武漢 430063)

?

基于改進(jìn)蟻群算法的不定長原管一維下料廢料率優(yōu)化

徐平平,郭蘊(yùn)華

(武漢理工大學(xué)a.能源與動力工程學(xué)院； b.船舶動力工程技術(shù)交通行業(yè)重點(diǎn)實(shí)驗(yàn)室，武漢 430063)

針對船廠不定長原管一維下料廢料率問題，提出一種改進(jìn)的蟻群算法，按盡量利用余料和較短管材的原則選取原管，以螞蟻轉(zhuǎn)移路徑和信息素矩陣表示原管和胚料管之間的關(guān)聯(lián)關(guān)系，并據(jù)此選取胚料管。仿真實(shí)驗(yàn)表明，改進(jìn)蟻群算法比已有算法可以得到更佳的最優(yōu)解，且能明顯降低管材的廢料率。

改進(jìn)蟻群算法; 一維下料; 不定長管材；廢料率

管材加工是除船體結(jié)構(gòu)外工作量最大的工種，一艘船有幾十個系統(tǒng)，約萬根管材，提高管材利用率成為降低成本的關(guān)鍵因素之一。管材加工過程中存在余料和廢料，二者以某個閾值劃分。如果余料長期不進(jìn)行利用，不但增加管材的浪費(fèi)，也給船廠庫存也帶來較大的壓力。在下料時，盡量利用余料是控制成本的有效手段。管材下料屬于一維下料問題，該問題是NP難題[1]。求解該問題的方法包括：①經(jīng)典方法，如線性規(guī)劃[2]，分支定界法[3]等；②啟發(fā)式算法，如混合順序啟發(fā)式算法文獻(xiàn)[4]，蟻群算法[5]。經(jīng)典方法只能求解中小規(guī)模的下料問題，當(dāng)管材下料的數(shù)量較大時，問題的規(guī)模會指數(shù)增加，難以獲得較優(yōu)解。相比較而言，各種啟發(fā)式算法更適合求解大規(guī)模組合優(yōu)化問題，可以在有限時間內(nèi)獲得滿意解。不過，已有的各種啟發(fā)式算法都是針對原材料管為定長的情形而設(shè)計(jì)的，但實(shí)際生產(chǎn)過程中極有可能遇到不定長原管的下料問題。這是因?yàn)椋孩俅嬖谟嗔?，而余料不可能是定長的；②為節(jié)約成本，船廠采購了價(jià)格相對低廉不定長原管。為此，針對不定長原管一維下料問題，提出改進(jìn)的蟻群算法。該算法按盡量利用余料和較短管材的原則選取原管；以螞蟻轉(zhuǎn)移路徑和信息素矩陣表示原管和胚料管之間的關(guān)聯(lián)關(guān)系，并據(jù)此選取胚料管。

1　數(shù)學(xué)模型

大部分一維下料問題，都是針對原材料為定長情況來建立數(shù)學(xué)優(yōu)化模型，而船廠為了節(jié)約成本，大都購買不定長管，且余料也需用掉，因此在使用原材料管時，以不定長來建立模型，對每一根原材料管按長度升序單獨(dú)編號。而船廠所需的胚料管，相同管徑、管厚和長度的管材很少，對每一根胚料管也按長度升序單獨(dú)編號。文獻(xiàn)[6]研究了不定長的優(yōu)化模型，文獻(xiàn)[7]研究了可用余料問題，參考二者，根據(jù)船廠管材下料的實(shí)際情況，定義原材料管的集合為M管，定義胚料管的集合為C管，建立使原管的剩余長度最少的數(shù)學(xué)模型。

(1)

式中：m——已選用原材料管的根數(shù)；

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

n——胚料管的根數(shù)；

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

yi——每根已選中M管的剩余長度，若yi≤lmin(lmin為閾值)，則記為廢料，否則為余料；

xij——決策變量，若第i根M管上切割第j根C管，則xij=1，否則xij=0；

δ——切割刀縫寬度。

2　改進(jìn)的蟻群算法求解

2.1蟻群算法的基本原理

蟻群算法是一種基于種群的啟發(fā)式仿生進(jìn)化算法，實(shí)現(xiàn)過程主要體現(xiàn)在螞蟻路徑節(jié)點(diǎn)轉(zhuǎn)移，和信息素更新兩方面[8]。具體公式如下：

1)路徑節(jié)點(diǎn)轉(zhuǎn)移公式。

(2)

式中：q——[0,1]之間均勻分布的隨機(jī)數(shù);

1)積極引進(jìn)國內(nèi)外知名MOOCs課程體系，并重點(diǎn)建設(shè)本專業(yè)自己的MOOCs課程和翻轉(zhuǎn)課堂教學(xué)模式，并應(yīng)用于課程教學(xué)中，目前已完成3門專業(yè)課程的MOOCS建設(shè)和3門專業(yè)課程的“翻轉(zhuǎn)課堂”教學(xué)模式的建設(shè)，并都應(yīng)用于相關(guān)課程教學(xué)改革的實(shí)施中。

q0一般取0.25～0.85。

2)信息素更新公式。

(3)

(4)

式中：Q——常數(shù)；

Lbest——每代螞蟻?zhàn)顑?yōu)路徑的值，并限定τij(t+1)∈[τmin,τmax][8]。

2.2改進(jìn)的蟻群算法

船廠管材一維下料問題求解過程可以描述為：在M管選取一根管，從C管選取若干根管，使選出的M管用盡；然后再選取下一根M管，繼續(xù)上述過程，直至所有C管都完成下料。求解該問題有兩個關(guān)鍵：①M(fèi)管的選擇問題，M管的選擇不僅影響最優(yōu)解的求解，同時也影響余料的利用；②C管的選擇問題，即正反饋機(jī)制如何發(fā)揮作用。針對以上兩點(diǎn)，提出相應(yīng)的改進(jìn)策略。

2.2.1策略1

M管的選擇：余料管能夠盡量利用，關(guān)鍵在于較短的M管能夠優(yōu)先被選中，可按如下步驟實(shí)現(xiàn)。

步驟1求出C管中未被選用的最長一根管的長度，記為cmax。

步驟2為了選中較短的M管，根據(jù)下面公式來選定第k根M管。

(5)

步驟3通過分析仿真結(jié)果可知，若能將很短的C管擠到M管中被切割，這樣可能放棄選中較短的M管，但是降低了M管的總管數(shù)，有可能獲得更好的最優(yōu)解，因此在步驟2的基礎(chǔ)上給cmax加上一個正的隨機(jī)數(shù)r，按式(6)重新選取M管。

(6)

2.2.2策略2

C管的選擇：文獻(xiàn)[9-11]設(shè)計(jì)的螞蟻轉(zhuǎn)移路徑和信息素矩陣，表示C管與C管之間的關(guān)聯(lián)關(guān)系，但這種方法有待商榷：①針對同一根M管，C管和C管可以有關(guān)聯(lián)關(guān)系，但在不同的M管上，兩者并沒有關(guān)聯(lián)關(guān)系，造成啟發(fā)因子的關(guān)系式不明確；②給定M管選取第一根C管時，存在著隨機(jī)選取，若未能選取合適的第一根C管，將大大增加尋優(yōu)難度。因此，本文算法中螞蟻轉(zhuǎn)移路徑和信息素矩陣表示M管和C管之間的關(guān)聯(lián)關(guān)系，具體選管步驟如下。

步驟1將M管和C管統(tǒng)一編入節(jié)點(diǎn)集合，則城市數(shù)為Zcity=m+n(m為M管的數(shù)量，n為C管的數(shù)量)，每只螞蟻所走過的路線對應(yīng)著一個切割方案，將節(jié)點(diǎn)分為M管節(jié)點(diǎn)和C管節(jié)點(diǎn)。

步驟2根據(jù)策略一，選取M管，計(jì)算C管的可選集，M管到C管的節(jié)點(diǎn)選擇依據(jù)公式(2)，以選定的M管的剩余長度的倒數(shù)作為啟發(fā)因子。

式中：ml——選定M管的長度；

cl——選定C管的長度。

步驟3C管到M管的節(jié)點(diǎn)：若選定的M管還可以供C管繼續(xù)用，M管節(jié)點(diǎn)不變，否則依據(jù)策略1，重新選取M管，作為新的節(jié)點(diǎn)。

3　仿真及實(shí)驗(yàn)結(jié)果分析

本算法在48根M管的基礎(chǔ)上切割98根C管，數(shù)據(jù)如表1、2所示。

C管的總長為193.446 m，每個切縫的寬為0.005 m。在Java編程環(huán)境下對船廠管材一維下料問題進(jìn)行的仿真，參數(shù)選擇為α=2，β=8，ρ=0.3，Q=1 000，τmin=10，τmax=1 000，q0=0.25，螞蟻數(shù)為30，迭代次數(shù)為100代，策略1的隨機(jī)數(shù)為0～1.5，將M管中剩余長度大于0.05 m的管作為余料管。

表1　M管的數(shù)據(jù)　m

表2　C管的數(shù)據(jù)　m

文獻(xiàn)[9]研究的是原材料為定長的問題，在其基礎(chǔ)上考慮策略1，使其適應(yīng)不定長問題(以下簡稱“文獻(xiàn)算法”)。對文獻(xiàn)算法和本文算法進(jìn)行對比試驗(yàn)，每種算法各仿真計(jì)算100次。仿真實(shí)驗(yàn)結(jié)果見表3和圖1。

表3　仿真數(shù)據(jù)對比　m

圖1　平均最優(yōu)解的進(jìn)化

從仿真結(jié)果中可以看出：

1)本文算法全局最優(yōu)解為0.665 m，經(jīng)計(jì)算下次可利用的余料管總長共0.225 m，管材的廢料率為0.48%，實(shí)際船廠的管材下料廢料率大概在3%～5%左右。這表明針對M管選擇的改進(jìn)策略1，不僅使管材利用率提高，同時也使余料被盡量使用。

2)本文算法的全局尋優(yōu)能力和收斂速度都好于文獻(xiàn)算法。這表明針對C管選擇的改進(jìn)策略2，對提高算法的性能有顯著的影響。

4　結(jié)論

所提出的基于改進(jìn)蟻群算法的船廠不定長原管一維下料方法，使管材廢料率降低到0.48%，且能利用余料，在同文獻(xiàn)算法進(jìn)行對比實(shí)驗(yàn)，不僅提高了算法的全局尋優(yōu)能力，也加快了算法的收斂速度，表明本文算法在優(yōu)化船廠管材下料廢料率問題是可行的。將本文算法應(yīng)用到船廠管材下料中，不僅降低船廠管材下料的廢料率，也降低管材余料的庫存，可以產(chǎn)生很好的經(jīng)濟(jì)性。在下一步研究中，將嘗試根據(jù)本文算法開發(fā)成管材下料軟件，使其產(chǎn)生工程價(jià)值。

[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] 程浩,劉心報(bào),方昶.基于混合順序啟發(fā)式算法的一維下料問題[J].中國機(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] 吳正佳,張利平,王魁.蟻群算法在一維下料優(yōu)化問題中的應(yīng)用[J].機(jī)械科學(xué)與技術(shù),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

國家自然基金項(xiàng)目(51579201)

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

U664.84

A

1671-7953(2016)01-0113-04

研究方向:信息融合與工程優(yōu)化

E-mail:1404247066@qq.com