飛機制造物流問題的約束多目標(biāo)優(yōu)化算法研究

王鵬，譚杭波

無錫雪浪數(shù)制科技有限公司，江蘇無錫，214131

0 引言

航空工業(yè)是反映一個國家綜合國力和軍事實力的戰(zhàn)略性高科技產(chǎn)業(yè)。它是國防建設(shè)和航空運輸?shù)奈镔|(zhì)基礎(chǔ)，對國家經(jīng)濟、社會發(fā)展和技術(shù)創(chuàng)新具有重要意義[1]。航空工業(yè)的快速發(fā)展加速了技術(shù)進步和產(chǎn)業(yè)升級，促進了國民經(jīng)濟和就業(yè)增長，并為國家安全和國防能力建設(shè)提供了堅實的支撐。航空工業(yè)是一個高端技術(shù)聚集的領(lǐng)域，具有技術(shù)密集、高度綜合和廣泛協(xié)同的特點，并是多品種、小批量和離散制造的典型代表[2]。

近年來，航空制造業(yè)面臨著越來越短的開發(fā)周期、越來越高的交付質(zhì)量要求以及不斷增長的新產(chǎn)品需求的巨大壓力[3]。目前的協(xié)同制造模式，主機和配套廠商信息相對滯后，缺乏科學(xué)、系統(tǒng)、集中化的倉儲和物流管理系統(tǒng)。首先，由于統(tǒng)計和賬戶信息不清晰，倉庫無法及時獲取準(zhǔn)確的物料庫存信息，從而無法很好地組織生產(chǎn)。其次，缺乏科學(xué)有效的存儲設(shè)施和運輸設(shè)備，使物流時效性的預(yù)測成難題，結(jié)果造成大量資源浪費和成本上漲。更為嚴(yán)重的是，它阻礙了生產(chǎn)效率提高，并導(dǎo)致無法按時交貨，使協(xié)同制造模式難以滿足生產(chǎn)需求或成功完成開發(fā)任務(wù)[4]。

信息技術(shù)的不斷發(fā)展為信息網(wǎng)絡(luò)化和智能技術(shù)帶來了新的視角，并出現(xiàn)了各種自動化倉儲和運輸設(shè)備[5]?？湛秃筒ㄒ魧⑽锫?lián)網(wǎng)射頻識別技術(shù)應(yīng)用在供應(yīng)鏈、飛機制造、倉儲和售后管理等方面，以更好地識別、跟蹤和監(jiān)控實際情況[6]。

盡管當(dāng)前的解決方案僅僅通過信息技術(shù)手段實現(xiàn)了航空制造企業(yè)內(nèi)部所有環(huán)節(jié)的數(shù)據(jù)循環(huán)，但企業(yè)間的信息仍處于封閉孤立狀態(tài)，不同設(shè)備、不同站點和不同車間之間仍存在許多信息孤島。目前，由于航空企業(yè)信息技術(shù)水平不高造成的壁壘已成為供應(yīng)鏈和生產(chǎn)流程中的一個巨大障礙。由于信息基礎(chǔ)薄弱，生產(chǎn)過程中的信息傳遞和流通經(jīng)常會中斷，從而導(dǎo)致信息無法持續(xù)且及時傳遞。另外，信息流和物流之間的不同步引入了物料等待、倉庫積壓等問題，嚴(yán)重影響物流效率。因此，如何有效地預(yù)測物流是亟待解決的問題[7]。

為了更好地解決上述問題，研究發(fā)現(xiàn)基于PLC控制立體倉庫[8]、煙葉復(fù)烤生產(chǎn)流程[9]等均引入自動導(dǎo)引車（AGV）技術(shù)，故對航空航天制造廠、倉庫、配送中心和傳輸終端引入了基于AGV的內(nèi)部車輛運輸系統(tǒng)，以提高物流效率和精度，即AGV系統(tǒng)。AGV系統(tǒng)的設(shè)計和控制過程涉及導(dǎo)引路徑設(shè)計、所需車輛數(shù)量的估計、車輛調(diào)度、空閑車輛定位、電池管理、車輛路由和鎖死解決等多方面。特別是，指導(dǎo)路徑設(shè)計是一個戰(zhàn)略級問題，此級別的決策對其他級別的影響很大[10]。飛機制造是一個復(fù)雜的工程問題，涉及裝配前[11]的許多工藝、材料和半成品，本文重點關(guān)注使用AGV系統(tǒng)運輸作業(yè)車間使用的材料和半成品的物流問題。

相關(guān)物流問題在文獻(xiàn)[12]中被建立為一個單目標(biāo)優(yōu)化模型，該模型考慮了一些特殊因素，將各種相關(guān)的關(guān)注點包含在一個單一的目標(biāo)函數(shù)中。此外，為了提高飛機制造的能源效率，還考慮了AGV的最優(yōu)速度，驗證了該優(yōu)化模型比許多其他優(yōu)化模型更為有效。盡管如此，在多因素和約束條件之間很難達(dá)到平衡，只能得到單一的解決方案，沒有任何替代方案。因此，本文建立了一個有約束的多目標(biāo)優(yōu)化模型用于航空制造物流問題，旨在同時優(yōu)化多個目標(biāo)并滿足多個約束條件。為了建立優(yōu)化模型，采用了許多先進的約束多目標(biāo)元啟發(fā)式算法，以獲得滿足所有約束條件并在目標(biāo)之間進行多樣化權(quán)衡的多種解決方案。實驗結(jié)果表明，該方法比現(xiàn)有方法表現(xiàn)更好。

1 問題模型

飛機制造車間通常位于巨大的空間內(nèi)，需要將大量材料和半成品從倉庫運輸至生產(chǎn)線上的組裝點。借助自動化技術(shù)和信息技術(shù)，飛機制造車間正變得越來越智能化，常使用配備物聯(lián)網(wǎng)設(shè)備的自由導(dǎo)航AGV[11]來處理運輸任務(wù)。盡管如此，這樣的物流問題并不簡單，因為需要考慮到許多限制和成本，例如倉庫的最大容量約束、在倉庫存放材料和半成品的成本、AGV處理運輸任務(wù)的運輸成本、能源消耗成本、運輸時間成本等。這些考慮高度依賴于倉庫的位置、AGV運輸時的速度以及倉庫服務(wù)的組裝點，需要充分優(yōu)化以提高效率。

在文獻(xiàn)[12]中，已經(jīng)提出了一種使用AGV來解決飛機制造物流問題的優(yōu)化模型，但在實際應(yīng)用中存在一定的局限性。首先，該模型考慮到了倉庫位置和AGV速度的優(yōu)化，但忽略了哪些倉庫需要由哪些組裝點服務(wù)的問題。其次，該模型涉及四個按用戶定義的權(quán)重系數(shù)合并的優(yōu)化目標(biāo)，從而將其轉(zhuǎn)化為單一目標(biāo)優(yōu)化問題。然而，在實際場景中，不同的生產(chǎn)車間可能隨時間變化而有不同的需求，多個目標(biāo)的聚合無法滿足不同場景中的不同需求。此外，通過經(jīng)驗很難確定最優(yōu)權(quán)重系數(shù)。因此，在本文中，我們構(gòu)建了一個更為精細(xì)的優(yōu)化模型，將各個目標(biāo)分別處理，并對更多的變量進行優(yōu)化。

1.1 編碼方案

鑒于不同情境下裝配點的倉庫數(shù)量和位置存在差異，本文提出的模型中，第一部分決策變量是為m個裝配點選擇n個倉庫的位置。此外，考慮到每個倉庫的服務(wù)能力有限，需要將每個倉庫服務(wù)的裝配點指標(biāo)作為第二部分決策變量。另外，由于AGV的速度與交付時間和能量損耗有關(guān)，模型的第三部分決策變量包括每個用于交付過程的AGV的速度。值得注意的是，我們在此方面做出了一些假設(shè)：AGV從倉庫出發(fā)，在倉庫和裝配點之間往返運送材料；AGV在倉庫和裝配點之間的速度保持恒定。因此，本文所提出的優(yōu)化模型的完整決策向量如圖1所示。具體而言，每個解向量都由一個混合向量表示，其中，表示第個倉庫的位置，，表示屬于第個倉庫的AGV的速度，，表示第個裝配點由第個倉庫服務(wù)。

圖1 優(yōu)化模型的編碼方案

1.2 目標(biāo)函數(shù)

基于提出的編碼方案，我們在優(yōu)化模型中定義了四個最小化目標(biāo)，其中涉及的符號見表1。為了降低AGV從倉庫到裝配點運輸物料和半成品的成本，第一個目標(biāo)基于不同需求的倉庫和裝配點間的距離評估運輸成本，表示為：

表1 所提出的優(yōu)化模型中使用的形式化符號

第二個目標(biāo)與每個倉庫的存儲能力有關(guān)?？紤]到儲存能力越大，可能帶來的成本越高，因此第二個目標(biāo)基于每個倉庫服務(wù)的所有裝配點的總需求評估倉儲成本，表示為：

考慮到AGV在運輸物料和半成品時消耗能量，為了提高效率并降低對環(huán)境的能量消耗影響，第三個目標(biāo)基于運輸物料的重量和每個AGV的運輸路徑長度評估能量消耗，表示為：

考慮到物料運輸時間將會影響生產(chǎn)線操作時間和員工資源的安排，第四個目標(biāo)是基于倉庫和裝配點之間的距離和AGV的速度計算AGV運輸物料和半成品的時間，表示為：

最后，考慮到一個倉庫的存儲容量是有限的，我們加入一個約束來確保所有由第個倉庫服務(wù)的裝配點的總需求不超過其最大容量，表示為：

綜上所述，我們建立了以下帶約束的多目標(biāo)優(yōu)化模型來解決飛機制造中的物流問題：

這四個目標(biāo)之間存在一定程度的沖突，特別是表示能量消耗的第三個目標(biāo)和表示運輸時間的第四個目標(biāo)。通常情況下，運輸時間越短，能源消耗就越大，反之亦然。因此，很難通過定義權(quán)重系數(shù)來平衡這些目標(biāo)。更重要的是，在最小化目標(biāo)之前需要強制滿足約束條件，這也可能會破壞目標(biāo)的優(yōu)化性能。因此，此模型相對較為復(fù)雜，給通用優(yōu)化算法帶來了困難。

2 優(yōu)化算法

基于問題，我們使用多目標(biāo)進化算法（MO EAs），直接處理混合變量和非凸函數(shù)，并且在不聚合任何目標(biāo)的情況下，在多個目標(biāo)之間取得良好的平衡。

2.1 約束多目標(biāo)優(yōu)化

航空航天和工作室物流問題涉及多個目標(biāo)的優(yōu)化和同時滿足多個約束[13-15]，這些問題被稱為受限多目標(biāo)優(yōu)化問題（CMOPs）。CMOP在數(shù)學(xué)上的定義如下：

受到進化論和自然的群體行為的啟發(fā)，進化算法在優(yōu)化過程中演化出一個種群而不是一個單個解，并可以在單次運行中近似一組Pareto最優(yōu)解，提供多種選擇作為最終的輸出[17]。在過去幾十年中，進化算法的研究發(fā)展迅速，多目標(biāo)進化算法（MOEAs）提出了各種后代生成方案（例如，遺傳算子[18]、差分進化[19]、粒子群優(yōu)化[20]和分布估計算法[21]）和環(huán)境選擇策略（例如，非支配排序[22]、目標(biāo)分解[23]和基于指標(biāo)的選擇[24]）。MOEAs從一個隨機初始化的種群開始，通過后代生成方案迭代產(chǎn)生新的后代解，并通過環(huán)境選擇策略保留更好的解。經(jīng)過多代的重復(fù)操作后，種群可以逐漸逼近Pareto最優(yōu)解[25]，且具有良好收斂性和多樣性。

2.2 多目標(biāo)優(yōu)化算法

相較于傳統(tǒng)的優(yōu)化算法，多目標(biāo)進化算法（MOEAs）可以直接處理混合變量和非凸函數(shù)，并且在不聚合任何目標(biāo)的情況下，在多個目標(biāo)之間取得良好的平衡。盡管約束多目標(biāo)優(yōu)化問題（CMOPs）引入了在優(yōu)化目標(biāo)之前需要滿足的額外約束條件，但近年來MOEAs的研究集中在解決CMOPs上，在此期間提出了許多有效的MOEAs，能夠在不懲罰任何約束的情況下[26]，在目標(biāo)和約束之間取得良好的平衡。

由于本文所定義的優(yōu)化模型是一個典型的混合變量CMOP，因此在本文中采用以下五種代表性的MOEAs來解決CMOPs。

NSGA-Ⅱ[18]將可行性優(yōu)勢原則嵌入Pareto優(yōu)勢中以解決CMOPs。在該算法中，滿足所有約束的解優(yōu)先于不滿足約束的解，剩余的滿足約束的解則按照其違反約束的程度進行支配。由于NSGA-Ⅱ總是對約束的優(yōu)先級高于目標(biāo)，因此由于需要滿足約束，它的解可能會陷入局部最優(yōu)。

CCMO[27]通過解決一個簡單的輔助問題，為CMOPs提出了一個協(xié)同進化的約束多目標(biāo)優(yōu)化框架。CCMO分別演化出具有相同優(yōu)化模式的兩個種群，其中第一個種群用于解決原始CMOP，第二個種群用于解決從原始CMOP衍生出的幫助問題。CCMO中的協(xié)作相比已有的MOEAs較弱，但在解決CMOPs方面證實更加有效。

BiCo[28]嘗試通過雙向協(xié)同進化搜索范式來解決CMOPs。BiCo協(xié)同進化兩個種群（即樣本種群和歸檔種群），能夠有效地將解從可行和不可行的搜索空間中推向Pareto前沿，這對于約束多目標(biāo)優(yōu)化至關(guān)重要。BiCo設(shè)計了一種有效的基于角度的選擇策略來更新歸檔種群，不僅可以維持種群多樣性，還能找到更優(yōu)質(zhì)的解。

DCNSGA-Ⅲ[29]提出了一種處理CMOPs的問題轉(zhuǎn)化技術(shù)。具體地，它將高度約束問題轉(zhuǎn)換為一個約束條件很容易滿足的動態(tài)CMOP。利用問題轉(zhuǎn)化技術(shù)，隨著搜索的進行，約束的難度逐漸增加。對于給定的時刻，轉(zhuǎn)換后的問題可以被解決。通過一般MOEAs解決一個無約束問題。此外，動態(tài)約束可以幫助MOEAs在多樣性和收斂性之間進行平衡，而不必過多考慮約束滿足度。

CMOEA-MS[30]設(shè)計了一個解決具有復(fù)雜可行域的CMOPs的兩階段框架。該算法將進化過程分為兩個階段，并使用不同的適應(yīng)度計算方法調(diào)整目標(biāo)和約束的優(yōu)先級。第一階段顯示得到的解大多無法使用，并且為了覆蓋可行區(qū)域，各個目標(biāo)給予同等的優(yōu)先級。相反，第二階段顯示得到的解大多可行，目標(biāo)的優(yōu)先級低于約束。

3 實驗結(jié)果與分析

為了驗證所提出的優(yōu)化模型和使用的算法的有效性，本文在所構(gòu)造的數(shù)據(jù)集上進行了各個方法效果的對比。

3.1 實驗設(shè)置

為了驗證所提出的優(yōu)化模型和使用的算法的有效性，本文構(gòu)建了一個合成數(shù)據(jù)集，并在實驗中使用，其中包括n=3個倉庫和m=50個裝配點。裝配點的坐標(biāo)在二維歐幾里得空間中隨機設(shè)置在(0,0)和(100,100)之間，并且每個裝配點的需求也在[10,100]內(nèi)隨機設(shè)置。對于所有使用的MOEAs，人口規(guī)模設(shè)置為30，函數(shù)評估次數(shù)設(shè)置為60000。為了充分探索MOEAs在提出的優(yōu)化模型上的性能，每個MOEA都配備兩種類型的后代生成方案，即遺傳算子（GA）和差分進化算子（DE）。遺傳算子包括模擬二進制交叉[31]和多項式變異[32]，而差分進化算子包括DE/rand/1[33]和多項式變異。交叉概率設(shè)置為1，變異概率設(shè)置為1/D，交叉和變異的分布指數(shù)設(shè)置為20，DE/rand/1中的參數(shù)為CR=0.9和F=0.5。

另一方面，為了驗證所提出的多目標(biāo)優(yōu)化模型的優(yōu)越性，將其與文獻(xiàn)[11]中的異構(gòu)粒子群優(yōu)化算法HPSO進行比較，該算法解決了用于航空航天物流問題的單目標(biāo)優(yōu)化模型。該算法的參數(shù)為k=1.86/m，。此外，它解決以下單目標(biāo)優(yōu)化模型：

3.2 實驗結(jié)果

表2比較了六種算法HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA_MS在30次獨立運行中獲得的標(biāo)準(zhǔn)化超體積（HV）的均值和標(biāo)準(zhǔn)差[34]。較高的HV值表示所得種群的收斂和多樣性更好。結(jié)果表明，五個多目標(biāo)優(yōu)化算法的HV值明顯高于單目標(biāo)優(yōu)化算法HPSO。此外，圖2和圖3繪制了HV的收斂過程，這個過程由HPSO和分別使用遺傳算子和差分進化算子的5個MOEAs獲得。

表2 HPSO、NSGA-Ⅱ、CCMO、BICO、DCNSGA-Ⅲ和CMOEA MS 的HV 值

圖2 使用遺傳算子獲取的HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的HV 值的收斂過程

圖3 使用差分進化獲取的HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的HV 值的收斂過程

從圖中可以看出，五個多目標(biāo)優(yōu)化算法比HPSO收斂更快，并且最終得到的HV值也更高。因此，多目標(biāo)優(yōu)化算法的優(yōu)越性已得證。此外，使用遺傳算子的多目標(biāo)優(yōu)化算法表現(xiàn)更好，因為它可以更好地從所提出的優(yōu)化模型的景觀中逃脫局部最優(yōu)值。

為了進行直觀比較，圖4列出了六種算法所獲得的非支配解，依據(jù)不同目標(biāo)進行排序?？梢园l(fā)現(xiàn)，對于所提出的優(yōu)化模型而言，多目標(biāo)優(yōu)化算法特別是CMOEA_MS可以得到許多非主導(dǎo)解，而單目標(biāo)優(yōu)化算法HPSO所得到的解被許多其他解所支配。事實上，HPSO通過預(yù)定義的權(quán)重系數(shù)對四個目標(biāo)進行加權(quán)求和以得到單目標(biāo)優(yōu)化，因此，得到的解傾向于節(jié)約能量，而對于運輸成本、倉儲成本和運輸時間的目標(biāo)優(yōu)化較差。因此，證明了對于航空航天物流問題，多目標(biāo)優(yōu)化技術(shù)優(yōu)于單目標(biāo)優(yōu)化技術(shù)。為了清晰地比較各種算法所獲得的解，圖5描述了每個倉庫解碼后覆蓋的裝配點，選擇每個算法所獲得的最靠近目標(biāo)空間原點的解進行繪制。顯然，多目標(biāo)優(yōu)化算法獲得的解與HPSO獲得的解相比有更少的交叉路徑，因此在實踐中更有效率。此外，表3列出了比較算法所獲得的三個倉庫的速度，多目標(biāo)優(yōu)化算法獲得的解具有比HPSO更高的速度，因此在交付時間方面更短。最后，為了比較算法的優(yōu)化效率，表4顯示了它們所消耗的運行時間，其中多目標(biāo)優(yōu)化算法的計算復(fù)雜度與單目標(biāo)優(yōu)化算法 HPSO相似。因此，所提出的多目標(biāo)優(yōu)化模型以及先進的多目標(biāo)優(yōu)化算法對于航空制造物流問題是有效的和高效的。

表3 HPSO、NSGA-Ⅱ、CCMO、BICO、DCNSGA-Ⅲ和CMOEA MS 的速度

表4 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 的運行時間

圖4 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 獲得的非支配解

圖5 HPSO、NSGA-Ⅱ、CCMO、BiCo、DCNSGA-Ⅲ和CMOEA MS 獲得的解碼后的倉庫覆蓋的裝配點

4 結(jié)論與展望

為了解決飛機制造中的物流問題，本文建立了一個受約束的多目標(biāo)優(yōu)化模型，其中包含了一個混合決策向量、四個相互沖突的目標(biāo)和若干約束條件。為了解決這個復(fù)雜的優(yōu)化模型，本文選擇了五種最先進的受約束多目標(biāo)優(yōu)化算法。通過實驗結(jié)果的分析，本文驗證了受約束多目標(biāo)優(yōu)化技術(shù)在現(xiàn)有研究中明顯優(yōu)于使用的單目標(biāo)優(yōu)化技術(shù)。

未來可以開發(fā)更有效的元啟發(fā)式算法以獲得更好的優(yōu)化性能。此外，本文僅驗證了通用多目標(biāo)優(yōu)化算法在黑盒優(yōu)化中的優(yōu)越性，對于解決物流問題，可以定制更多的啟發(fā)式搜索策略，并滿足不同場景中的額外考慮因素。