多目標(biāo)件選擇性拆卸序列規(guī)劃數(shù)學(xué)模型

王菊梅　楊建新

摘 要：廢舊汽車總體存量大、資源價值高，對其進行零部件回收拆卸，可以有效地減少環(huán)境污染以及資源浪費。選擇性拆卸作為滿足產(chǎn)品再制造，再利用的實用性環(huán)節(jié)，可實現(xiàn)廢舊資源利用最大化。拆卸序列規(guī)劃研究可以有效降低拆卸成本、提高效率，為拆卸過程提供具體科學(xué)有效的序列規(guī)劃方案，避免拆卸的盲目性，因而逐漸受到愈加廣泛的關(guān)注。由此，以合理、高效地拆卸廢舊汽車中的零部件為目標(biāo)件，研究面向多目標(biāo)件的選擇性拆卸序列規(guī)劃問題。為滿足序列的可行性，在保證各約束的前提下，提出了拆卸成本最小化的整數(shù)規(guī)劃模型。最后基于GAMS平臺進行了實例分析，驗證了其可行性和實用性。

關(guān)鍵詞：拆卸序列規(guī)劃 選擇性拆卸 多目標(biāo)件

1 引言

隨著制造業(yè)的快速發(fā)展，廢舊汽車產(chǎn)品所帶來的環(huán)境問題和其蘊含的經(jīng)濟價值，凸顯了拆卸在理論研究和實踐中的重要性。同時，復(fù)雜汽車產(chǎn)品的零部件數(shù)量呈指數(shù)形式增長，復(fù)雜度增加，如何以較低代價實現(xiàn)拆卸序列規(guī)劃（Disassembly Sequence Planning，DSP）問題的快速求解已經(jīng)成為了近年來的研究熱點。

選擇性拆卸（Selective DSP，SDSP）是指基于產(chǎn)品結(jié)構(gòu)、裝配關(guān)系、裝配過程等信息，從產(chǎn)品上拆卸下一個或多個指定的零部件。在制造業(yè)中面向再制造和再利用的目標(biāo)拆卸是一種選擇性拆卸，其快速高效地獲取拆卸序列是現(xiàn)今大多數(shù)學(xué)者的研究重點[1]。薛俊芳等[2]基于拆卸有向圖，使用時間乘以拆卸復(fù)雜度作為有向圖權(quán)重，并通過優(yōu)化有向圖模型的路徑得到了目標(biāo)件的最優(yōu)拆卸序列;張秀芬等[3]針對局部破壞情況，重建拆卸加權(quán)混合圖模型，結(jié)合圖模型和幾何推理得到了拆卸序列;趙樹恩等[4]基于Petri網(wǎng)建立了拆卸模型，通過求解Petri網(wǎng)獲得拆卸序列;王昊等[5]基于層次關(guān)系和關(guān)聯(lián)關(guān)系建模，并且引入跳躍拆卸路徑的概念進行了完善和優(yōu)化。Ziqiang Zhang等[6]定義了重構(gòu)混合EOL產(chǎn)品圖規(guī)則來獲取選擇性拆卸序列;郭希旺等[7]考慮了零部件之間的相互依賴關(guān)系約束，建立了以最小拆卸時間和最大拆卸收益為目標(biāo)的多目標(biāo)優(yōu)化模型;邢宇飛等[8]提出利用拆卸鄰接矩陣推導(dǎo)拆卸的可行條件，實現(xiàn)了拆卸序列的優(yōu)化;崔永等[9]通過了CAD設(shè)計信息建立了節(jié)點間的鄰接矩陣來獲得拆卸序列。

綜合以上的研究現(xiàn)狀，學(xué)者們各自雖然都取得了階段性的成果，但在廢舊汽車零部件產(chǎn)品DSP問題的求解中仍存在著一些不足之處：大多數(shù)的研究還是處在完全拆卸（Complete DSP，CDSP）和部分拆卸（Partial DSP，PDSP）上，針對SDSP的數(shù)學(xué)建模求解準(zhǔn)確度不盡人意。

本文深入挖掘目標(biāo)零部件相關(guān)信息，優(yōu)化拆卸效率，旨在合理、高效地拆卸回收零部件，最大限度地降低回收成本，最大化資源的可持續(xù)利用。

2 拆卸信息模型構(gòu)建

在建立產(chǎn)品CAD模型之后，可通過人機交互的方式由模型中的裝配關(guān)系得出零件和約束關(guān)系。連接關(guān)系是指零件間的拆卸鄰接關(guān)系，如兩零件之間通過螺紋、螺釘、焊接等等連接;拆卸優(yōu)先關(guān)系是指零件間拆卸的先后順序（包括接觸約束和非接觸約束）。本文主要結(jié)合人工推導(dǎo)，從產(chǎn)品和零部件的三維模型中直接提取零部件配合約束等裝配相關(guān)的信息。

混合圖是圖論中具有最基本表現(xiàn)形式的信息模型，主要由非空節(jié)點集合P、無向邊集合E和有向邊PE這個三元組構(gòu)成，本文對于拆卸關(guān)系混合圖表示為：EG={P，E，PE}。其中，P={p1，p2，…，pn}是零件集合，n表示產(chǎn)品中零件的個數(shù);E={e1，e2，…，em}是無向邊集合，m表示產(chǎn)品零件間連接關(guān)系的總個數(shù);PE={pe1， pe2，…，pez}是有向邊集合，z表示零件間空間約束的總個數(shù)。由于給邊賦予了方向，那么對于有向邊pez將與兩個相關(guān)聯(lián)的節(jié)點產(chǎn)生有序偶peij。

本文考慮了各零部件間的接觸和非接觸幾何空間約束，從中讀取零件和連接關(guān)系，生成節(jié)點與約束信息，據(jù)此構(gòu)建混合圖EG。基于混合圖，EG可分解為連接關(guān)系圖Ge={P，E}和優(yōu)先關(guān)系圖Gpe={P， PE}，可以直觀地觀察出待零件間的連接關(guān)系和拆卸優(yōu)先關(guān)系。

如果有向邊peij存在，采用gij（PE）（i=1，2，…，n;j=1，2，…，n）表示元素的拆卸約束，gij（PE）=1，即零件i優(yōu)先于零件j拆卸;如果有向邊peij不存在，則gij（PE）=0，即零件i、j之間不存在優(yōu)先關(guān)系。即

（1）

如果無向邊eij存在，采用gij（E）（i=1，2，…，n;j=1，2，…，n）表示元素的連接關(guān)系，gij（E）=1，即零件i與零件j連接;如果無向邊eij不存在，則gij（E）=0，即零件i和零件j之間不存在連接關(guān)系。即

（2）

3 數(shù)學(xué)模型的構(gòu)建

SDSP問題是根據(jù)建立的信息模型，生成滿足拆卸約束的最優(yōu)目標(biāo)拆卸的離散組合優(yōu)化問題。本節(jié)作為以往CDSP研究的延伸，考慮獲取多個目標(biāo)零件的情況。同時，為滿足拆卸實際的生產(chǎn)需求，本文以最小拆卸成本作為優(yōu)化拆卸序列的評價指標(biāo)，建立了多目標(biāo)件選擇性拆卸序列規(guī)劃模型，

3.1 模型假設(shè)

為便于求解，需要對問題進行一定的簡化處理，考慮了如下假設(shè)：

1）拆卸順序表示為拆卸任務(wù)（零件）的順序，當(dāng)進行一次拆卸操作，要保證從產(chǎn)品中拆除一個零件或組件，一次移除多個零部件視為非法操作。

2）待拆卸零部件均作為剛體，整個拆卸過程中不會產(chǎn)生受損或變形;緊固件等認(rèn)為是拆卸約束和消耗品，忽略其剩余價值。

3）當(dāng)某一零件拆卸操作完成，不會引起裝配體結(jié)構(gòu)的不穩(wěn)定，其它相關(guān)聯(lián)零件位置也不會發(fā)生變化。

4）任務(wù)的基本操作時間、基本操作成本已知。在拆卸的過程中采取非破壞性的拆卸方式，盡可能地保證零部件的完整性，以期拆卸后得到零部件的質(zhì)量和效益。

3.2 符號說明

根據(jù)上節(jié)對拆卸信息模型的構(gòu)建，分析了拆卸過程的相關(guān)信息和考慮了連接關(guān)系和優(yōu)先關(guān)系的拆卸約束信息。其符號說明如下：

集合：

N：產(chǎn)品拆卸零件（操作）數(shù)集合，其中N={i=1，2，…，n}，n為零件數(shù);

O：目標(biāo)零件集合，其中O={o1，o2，…}。

參數(shù)：

i，j，k：零件號;

dij：零件i和零件j的優(yōu)先關(guān)系;

ti：零件i的基本拆卸時間;

Tij：零件i和零件j的拆卸工具轉(zhuǎn)換時間;

Dij：零件i和零件j的拆卸方向轉(zhuǎn)換時間;

ci：零件i的基本拆卸成本;

rij：零件i和零件j的輔助拆卸成本;

max：一個極大數(shù)。

0-1變量：

xij：如果i和j都拆卸且i在j前拆卸，則xij為1，否則為0;

yi：如果零件i被拆卸，則yi為1，否則為0;

hij：如果i和j都被拆卸，則hij為1，否則為0。

連續(xù)變量：

Si：零件i拆卸的開始時間。

3.3 模型建立

拆卸成本是拆卸序列規(guī)劃問題中的重要指標(biāo)，也是企業(yè)在拆卸實踐中的重要需求，其目標(biāo)函數(shù)如下。

（3）

式（3）表示了拆卸成本主要包含了基本拆卸成本和輔助拆卸成本。

（4）

式（4）表示了拆卸目標(biāo)為最小化最大拆卸成本。拆卸成本越低，拆卸回收效益越好。為保證拆卸序列的可行性，還需要滿足下面的約束條件：

1） 拆卸優(yōu)先關(guān)系約束

（5）

式（5）表示拆卸零件（操作）的優(yōu)先關(guān)系，零件i是j的前序，當(dāng)前序進行了拆卸操作，后續(xù)才可能進行拆卸。

（6）

（7）

式（6）和（7）表示拆卸零件（操作）的優(yōu)先關(guān)系，當(dāng)零件i是零件j的操作前序，零件j不能在零件i前面進行拆卸。當(dāng)零件i和零件j都拆卸且i在j前拆卸，則xij、yi和yj都為1，xji為0，等號成立;反之，不等號成立。

（8）

式（8）保證了序列中所有拆卸操作必須滿足優(yōu)先關(guān)系約束，且不能形成“閉環(huán)”關(guān)系。

（9）

式（9）表示拆卸零件（操作）的優(yōu)先關(guān)系，當(dāng)零件i和零件j都進行拆卸且i在j前拆卸，xij、yi、yj和dij都為1，等號成立;反之，不等號成立。

2）拆卸操作分配約束：

（10）

（11）

式（10）和（11）表示了當(dāng)零件i或j有一個未被分配進行拆卸操作，則不能滿足hij為1，即零件i或j都被拆。

（12）

式（12）表示了當(dāng)零件i和j都被分配進行拆卸操作，則滿足hij為1，即零件i或j都被拆。

（13）

式（13）確保了所有的目標(biāo)零件都必須進行拆卸操作。

（14）

（15）

式（14）和（15）表示對兩個決策變量進行線性化處理，當(dāng)零件i和j都被分配進行拆卸，xij或xji才能成立。

3） 時間關(guān)系約束：

（16）

式（16）表示了只有在前序零件已經(jīng)被拆卸完成才能開始下一個零件的拆卸操作。

公式（3）-（16）共同構(gòu)成了多目標(biāo)件選擇性拆卸序列規(guī)劃的數(shù)學(xué)模型。

4 實例研究

為了驗證所提出方法的可行性及有效性，本文實例分析主要選自于文獻[10]所示案例，如圖1所示。同時針對該裝配體搜集了拆卸相關(guān)信息，其中優(yōu)先關(guān)系、拆卸成本等基本拆卸相關(guān)信息如表1所示。該裝配體主要包含了21個零件，2號和11號零件是目標(biāo)零件。

1.泵蓋分部件2.主動軸分部件3.螺栓M8（s） 4.墊圈中Φ8（s） 5.調(diào)整墊片6.半圓鍵（s） 7.銷Φ3.2（s） 8.螺母M14（s） 9.墊圈Φ14（s） 10.齒輪11.泵體分部件12.銷A5（s） 13.中間泵殼14.固定軸15.調(diào)整墊片（同5） 16.銷A5（s） 17.從動齒輪分部件18.蓋板19.墊圈中Φ6（s） 20.螺栓M6（s） 21.墊片，其中標(biāo)有s的是標(biāo)準(zhǔn)件。

根據(jù)前面拆卸信息模型的構(gòu)建方法，其混合圖EG如圖2所示。

通常，拆卸時間與拆卸成本成正相關(guān)，本文假定其拆卸輔助成本是拆卸工具變換時間的0.1倍。其拆卸工具轉(zhuǎn)換時間如表2所示。

在GAMS平臺上通過開發(fā)模型求解程序。根據(jù)拆卸信息，拆卸序列結(jié)果如表3所示。從展示的結(jié)果可以看出最佳解決方案不止一個，這是因為復(fù)雜產(chǎn)品，存在很多同等拆卸優(yōu)先關(guān)系和拆卸成本的零件，在拆卸過程中選擇有多個，只要拆卸條件滿足即可。

5 結(jié)論

針對回收再制造、再利用領(lǐng)域的拆卸序列規(guī)劃問題，本文通過分析國內(nèi)外現(xiàn)有的研究成果，考慮實際生產(chǎn)過程中的需求，建立了最小化拆卸成本下的多目標(biāo)件拆卸序列規(guī)劃數(shù)學(xué)模型，同時基于GAMS平臺求解得出可行性方案，求解效率高。實踐證明，該方法能夠快速地得到具有工程實踐意義的最優(yōu)拆卸序列。

基金項目：廣安職業(yè)技術(shù)學(xué)院2021年度校級科研項目（GAZYKY-2021B06）

廣安職業(yè)技術(shù)學(xué)院2020年度校級科研項目（GAZYKY-2020A06）。

參考文獻：

[1]賴霞虹. 產(chǎn)品再制造拆卸規(guī)劃方法與零件再制造性評估方法的研究[D]. 浙江大學(xué)， 2012.

[2]薛俊芳， 張新建， 張英利. 基于Floyd 算法的目標(biāo)拆卸序列優(yōu)化[J]. 現(xiàn)代制造工程， 2014（2）：83-87.

[3]張秀芬， 張樹有. 基于粒子群算法的產(chǎn)品拆卸序列規(guī)劃方法[J]. 計算機集成制造系統(tǒng)， 2009， 15（3）：508-514.

[4]趙樹恩， 李玉玲. 模糊推理Petri網(wǎng)及其在產(chǎn)品拆卸序列決策中的應(yīng)用[J]. 控制與決策， 2005， 20（10）：1181-1184.

[5]王昊， 曾鴻， 張均東，等. 基于目標(biāo)拆卸的虛擬拆裝過程建模[J]. 圖學(xué)學(xué)報， 2015， 36（6）：903-908.

[6]Ziqiang Z， Guohong D， Xiangyan Z， et al. Research of Partial Destructive based Selective Disassembly Sequence Planning[J]. The Open Mechanical Engineering Journal， 2015， 9： 605-612.

[7]郭希旺， 劉士新， 王大志. 多目標(biāo)選擇性拆卸序列優(yōu)化問題的分散搜索算法[J]. 系統(tǒng)工程學(xué)報， 2016， 31（3）：307-316.

[8]邢宇飛， 王成恩， 柳強. 基于Pareto解集蟻群算法的拆卸序列規(guī)劃[J]. 機械工程學(xué)報， 2012， 48（9）：186-192.

[9]崔永， 趙良才. 基于相似線索二叉樹的汽車零部件拆卸序列生成及其回收模糊評價[J]. 現(xiàn)代制造工程， 2007（2）：66-70.

[10]周開俊， 李東波. 基于遺傳模擬退火算法的產(chǎn)品裝配序列規(guī)劃方法[J]. 計算機集成制造系統(tǒng)， 2006， 12（7）：1037-1041.