圓形件卷材排樣問題的一種定序定位算法

陸 濤，潘衛(wèi)平

?

圓形件卷材排樣問題的一種定序定位算法

陸 濤1，潘衛(wèi)平2

(1. 南寧學(xué)院信息工程學(xué)院，廣西 南寧 530200；2. 廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

圓形件卷材排樣問題是指將一組不同半徑的圓形件互不重疊的排放在寬度指定的卷材上，使得占據(jù)的卷材長度最小。針對(duì)該問題提出一種定序定位啟發(fā)式優(yōu)化算法。設(shè)計(jì)基于最大穴度的定位算法，對(duì)于每個(gè)特定排樣序列，計(jì)算待排樣圓形件在當(dāng)前布局的所有可行放置位置的穴度，選擇穴度最高的一個(gè)位置放置圓形件；更新當(dāng)前布局，繼續(xù)排放剩余圓形件，直到所有圓形件均排放進(jìn)卷材為止。采用遺傳算法對(duì)排樣序列進(jìn)行遺傳進(jìn)化得到多種不同的排樣方案，選擇耗費(fèi)卷材長度最小的一種排樣方案作為最終解。實(shí)驗(yàn)結(jié)果表明，本文算法排樣方案耗費(fèi)卷材長度較小，且算法計(jì)算時(shí)間相對(duì)合理。

卷材排樣問題；圓形件；優(yōu)化排樣；排樣算法；定序定位算法

在機(jī)械制造領(lǐng)域，經(jīng)常需要將金屬卷材切割成圓形件用來生產(chǎn)各種家用商品，譬如水桶，盤子，杯子等。對(duì)圓形件在卷材中的排樣方式進(jìn)行優(yōu)化，可以減少卷材資源消耗，降低企業(yè)生產(chǎn)成本[1-2]。本文研究圓形件卷材排樣(circular parts coiled sheet packing，CCSP)問題，該問題在文獻(xiàn)[3]的切割與裝填布局分類中屬于二維開放維度布局問題，在計(jì)算理論上屬于NP難范疇，具有很高的計(jì)算復(fù)雜度[4]。

本文針對(duì)CCSP問題，提出一種耗時(shí)較少的定序定位求解算法。首先構(gòu)造圓形件的定位算法，計(jì)算圓形件在當(dāng)前布局中各個(gè)可行放置位置的穴度，按照穴度最大原則確定圓形件的放置位置；然后采用遺傳算法構(gòu)造多個(gè)圓形件排樣序列，對(duì)于每個(gè)排樣序列調(diào)用上述定位算法確定排樣方案，選擇卷材使用長度最小的排樣方案作為最終解。編程實(shí)現(xiàn)本文算法，采用數(shù)值實(shí)驗(yàn)驗(yàn)證本文算法的有效性。

1 CCSP問題的相關(guān)概念

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

1.2 圓形件放置位置的穴度

如圖1所示，在卷材中排入了圓形件1和圓形件2之后，圖中虛線給出了圓形件3可能的排放位置。

圖1 第3個(gè)圓形件在卷材中可能的排放位置示意圖

(1)c+1至少與集合S中的2個(gè)圓形件相切。

(2)c+1至少與集合S中的1個(gè)圓形件相切并且至少與卷材的3條邊(左邊、上邊和下邊)中的1條邊相切。

(3)c+1至少與卷材的3條邊中的2條邊相切。

2 排樣算法

2.1 定位算法

2.2 定序算法

2.2.1 初始種群

初始種群對(duì)遺傳算法的收斂速度和優(yōu)化效率具有重要影響。從實(shí)際生產(chǎn)經(jīng)驗(yàn)可知，大小不同的圓形件均勻搭配排放能使布局緊湊，從而提高材料利用率。本節(jié)在構(gòu)造初始種群時(shí)借鑒此經(jīng)驗(yàn)。

2.2.2 遺傳算子

2.2.3 終止條件

重復(fù)執(zhí)行第2.2.2節(jié)，直到滿足預(yù)定的進(jìn)化代數(shù)，或計(jì)算時(shí)間超過規(guī)定的最大時(shí)間，停止計(jì)算，輸出適應(yīng)度最大的個(gè)體，得到最優(yōu)排樣方案。

3 數(shù)值實(shí)驗(yàn)計(jì)算

在主頻3.2 GHz，內(nèi)存4 GB的計(jì)算機(jī)上進(jìn)行下面兩組實(shí)驗(yàn)，本文算法進(jìn)化代數(shù)設(shè)置為500代，最大計(jì)算時(shí)間設(shè)置為3 600 s。算法排樣方案取500代中的最優(yōu)排樣方案；如果算法計(jì)算時(shí)間超過3 600 s，則取3 600 s內(nèi)獲得的最優(yōu)排樣 方案。

實(shí)驗(yàn)1.采用文獻(xiàn)[8]的18道例題，將本文算法與文獻(xiàn)[8]的3種算法進(jìn)行比較，分別為開放條帶生成算法(open strip generation solution procedure，OSGSP)、改進(jìn)版的開放條帶生成算法(open strip generation solution procedure with a diversification strategy，OSGSPa)和二劃分束搜索算法(Beam-Seach and the Binary Interval Search，BSBIS)。求解上述18道例題，本文算法總共耗時(shí)10 147.63 s，平均每道例題計(jì)算時(shí)間為563.76 s，OSGSP算法、OSGSPa算法和BSBIS算法每道例題平均計(jì)算時(shí)間分別為0.14 s、23.06 s和19 782.58 s。對(duì)于18道例題，本文算法排樣方案使用卷材平均長度為35.754 8，OSGSP算法、OSGSPa算法和BSBIS算法分別為37.727 3、37.091 9和36.180 8，實(shí)驗(yàn)對(duì)比結(jié)果見表1；本文算法比上述3種算法分別節(jié)省5.23%、3.60%和1.78%的卷材長度。因?yàn)樵诙ㄎ凰惴ㄅc文獻(xiàn)[8]定位算法類似的前提下：①本文定序算法基于遺傳算法原理比OSGSP和OSGSPa算法考察了更多個(gè)數(shù)的圓形件排樣序列；②BSBIS算法基于束搜索原理，實(shí)質(zhì)是一種不完全枚舉算法，考慮到計(jì)算時(shí)間和內(nèi)存空間上的限制，BSBIS算法尋優(yōu)能力可能劣于本文的定序算法。圖2為本文算法求得的例題SY12的排樣方案，其卷材寬度為9.5 dm，圓形件的尺寸數(shù)據(jù)見圖3。

表1 SY類例題本文算法與文獻(xiàn)算法的計(jì)算結(jié)果比較

圖2 例題SY12的排樣方案

圖3 例題SY12的50個(gè)圓形件的半徑數(shù)據(jù)(dm)

實(shí)驗(yàn)2.采用文獻(xiàn)[9]的30道例題，將本文算法與文獻(xiàn)[9]算法和文獻(xiàn)[10]算法進(jìn)行比較。本文算法求解上述例題，平均每道例題耗時(shí)35.62 s，文獻(xiàn)[9]和文獻(xiàn)[10]未報(bào)道例題的具體計(jì)算時(shí)間，其中文獻(xiàn)[10]設(shè)置每道例題最大計(jì)算時(shí)間為30 h。3種算法的實(shí)驗(yàn)對(duì)比結(jié)果見表2，從表中可以看出本文算法比文獻(xiàn)[9]和文獻(xiàn)[10]分別節(jié)省1.58%和0.68%的卷材長度。文獻(xiàn)[9]算法是一種貪婪算法，雖然并行化提高了其計(jì)算效率，但是未能改變其貪婪性；文獻(xiàn)[10]算法基于非線性規(guī)劃模型，在有限的時(shí)間內(nèi)，算法無法找到最優(yōu)解。圖4為本文算法求得的例題KBG_SPP3的排樣方案。

表2 KBG_SPP類例題本文算法與文獻(xiàn)算法計(jì)算結(jié)果比較

圖4 例題KBG_SPP3的排樣方案

4 結(jié)束語

針對(duì)圓形件卷材排樣問題，構(gòu)造了一種基于定序定位思想的排樣算法。該算法將排樣過程分為定序和定位2個(gè)階段，在定序階段確定圓形件的排放順序，在定位階段確定圓形件的具體排放位置。對(duì)于一個(gè)特定的排樣序列，定位算法按照放置位置穴度最大原則確定當(dāng)前待排圓形件的排放位置。為了擴(kuò)大解空間的搜索范圍，定序階段采用遺傳算法構(gòu)造了大量不同的排樣序列，選擇其中最優(yōu)的一個(gè)排樣序列作為最終解。從2組實(shí)驗(yàn)計(jì)算結(jié)果，可以看出本文算法具有較高的節(jié)材能力和合理的計(jì)算時(shí)間。

[1] 胡鋼, 楊瑞, 潘立武. 基于價(jià)值修正的圓片下料順序啟發(fā)式算法[J]. 圖學(xué)學(xué)報(bào), 2016, 37(3): 337-341.

[2] 陳燕, 劉詠, 謝琪琦, 等. 基于梯形和平行四邊形的圓片剪沖下料算法設(shè)計(jì)與實(shí)現(xiàn)[J]. 圖學(xué)學(xué)報(bào), 2016, 37(5): 661-667.

[3] W?SCHER G, HAU?NER H, SCHUMANN H. An improved typology of cutting and packing problems [J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[4] HUANG W Q, LI Y, AKEB H, et al. Greedy algorithms for packing unequal circles into a rectangular container [J]. Journal of the Operational Research Society, 2005, 56(5): 539-548.

[5] C?Té J F, DELL′AMICO M, LORI M. Combinatorial benders’ cuts for the strip packing problem [J]. Operations Research, 2014, 62(3): 643-661.

[6] 姚怡, 吳金春, 賴朝安. 采用分層搜索填充策略的啟發(fā)式帶排樣算法[J]. 武漢大學(xué)學(xué)報(bào): 工學(xué)版, 2014, 47(6): 854-858.

[7] CUI Y P, ZHOU Y W, CUI Y D. Triple-solution approach for the strip packing problem with two-staged patterns [J]. Journal of Combinatorial Optimization, 2017, 34(2): 588-604.

[8] AKEB H, HIFI M. Algorithms for the circular two-dimensional open dimension problem [J]. International Transactions in Operational Research, 2008, 15(6): 685-704.

[9] KUBACH T, BORTFELDT A, GEHRING H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle [J]. Central European Journal of Operations Research, 2009, 17(4): 461-477.

[10] STOYAN Y, YASKOV G. Packing unequal circles into a strip of minimal length with a jump algorithm [J]. Optimization Letters, 2014, 8(3): 949-970.

[11] 周杰, 周靜, 蔡世清, 等. 基于遺傳算法的參與式感知激勵(lì)機(jī)制的優(yōu)化[J]. 科學(xué)技術(shù)與工程, 2016, 16(17): 230-234.

[12] 劉二輝, 姚錫凡. 基于改進(jìn)遺傳算法的自動(dòng)導(dǎo)引小車路徑規(guī)劃及其實(shí)現(xiàn)平臺(tái)[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2017, 23(3): 465-472.

A Sequential Positioning Algorithm for Problem of Circular Parts Coiled Sheet Packing

LU Tao1, PAN Weiping2

(1. Information Engineering College, Nanning University, Nanning Guangxi 530200, China; 2. Computer and Electronic Information College, Guangxi University, Nanning Guangxi 530004, China)

The problem of circular parts coiled sheet packing means that a set of different radius circular parts are non-overlappingly packed on the coiled sheet with specified width, so that the occupied length of the coiled sheet is minimized. To solve this problem, a sequential positioning heuristic optimization algorithm is proposed. A positioning algorithm is designed based on maximum caving degree. For each particular packing sequence, caving degrees of all feasible placement location of circular parts are calculated, and the location which has the highest caving degree is selected to pack the circular part. The current layout is updated, and the packing of the residual circular parts is continued, according to the above rule until all of circular parts are packed into the coiled sheet. Genetic algorithm is employed to evolve the packing sequence, in order to obtain a great number of different packing schemes, and the packing scheme with the minimum coiled sheet length is chosen as the final solution. The experimental results show that the algorithm scheduling scheme of this paper consumes less coil length, and the calculation time of the algorithm is relatively reasonable.

coiled sheet packing problem; circular parts; packing optimization; packing algorithm; sequential positioning algorithm

TP 391

10.11996/JG.j.2095-302X.2018030562

A

2095-302X(2018)03-0562-05

2017-10-12；

2017-11-15

國家自然科學(xué)基金項(xiàng)目(61363026)；廣西高校科學(xué)技術(shù)研究項(xiàng)目(KY2015YB533)

陸 濤(1982-)，男，廣西環(huán)江人，講師，碩士。主要研究方向?yàn)檐浖こ獭⑷斯ぶ悄芎痛髷?shù)據(jù)。E-mail：ltgx82@163.com

潘衛(wèi)平(1989-)，男，湖北黃岡人，工程師，碩士，主要研究方向?yàn)閮?yōu)化計(jì)算。E-mail：gxwp08@163.com