考慮轉(zhuǎn)移策略的物料配送和空箱回收集成優(yōu)化

陸志強(qiáng)， 王韻熹

（同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804）

飛機(jī)總裝周期約占整個飛機(jī)制造周期的 25%～40%［1］。為了縮短總裝周期，近年來逐漸引入更加穩(wěn)定和高效的移動裝配技術(shù)［2］。但這種裝配方式對精準(zhǔn)配送提出了更高的要求，亟需建立一個有效而可靠的配套物料供給系統(tǒng)。

飛機(jī)裝配過程中所需的物料可以分為4 類：通用標(biāo)準(zhǔn)件、大型結(jié)構(gòu)件、裝配件和自制件。通用標(biāo)準(zhǔn)件（如螺栓等）一般在線邊存儲，采用定期補(bǔ)貨的方式供給；大型結(jié)構(gòu)件（如發(fā)動機(jī)、機(jī)翼等）通常使用叉車和機(jī)械臂等其他方式直接配送。本文研究問題中的物料主要指體積中等、種類復(fù)雜的裝配件，由于零部件組裝的相關(guān)性，通過齊套的方式使用標(biāo)準(zhǔn)料箱以準(zhǔn)時化的方式進(jìn)行配送，并在作業(yè)完成后對空箱進(jìn)行回收。

目前以飛機(jī)移動裝配線為背景研究物料供給問題的文獻(xiàn)較少，而以汽車裝配線為背景的研究相對成熟且物料供給過程與飛機(jī)類似，因此可以借鑒汽車裝配線中物料供給問題的模型與算法作為參考。Sali等［3］對庫存、齊套和順序配送這三種常用的物料配送策略進(jìn)行了描述并總結(jié)了各種配送方式的適用環(huán)境。Souza等［4］研究裝配線準(zhǔn)時化物料配送問題，以最小化搬運(yùn)費(fèi)用和庫存費(fèi)用為目標(biāo)建立數(shù)學(xué)模型，提出了具有貪婪隨機(jī)自適應(yīng)搜索的啟發(fā)式算法。Boysen等［5］以最小化最大庫存水平為目標(biāo)函數(shù)建立了汽車裝配線叉車配送模型，并設(shè)計了動態(tài)規(guī)劃算法進(jìn)行求解。但文獻(xiàn)［5］假定每個料箱的物料量為定值，在實際應(yīng)用中可能出現(xiàn)缺料的情形，因此Zhou 等［6］對假設(shè)進(jìn)行了改進(jìn)，在決策變量中引入了每次配送物料量的選擇，同時設(shè)計了反向動態(tài)規(guī)劃算法對該問題進(jìn)行求解。上述問題均考慮的是點(diǎn)對點(diǎn)的配送問題，每次只配送一個工位。Fathi 等［7］提出了milk-run 配送方式下多載量小車裝載和調(diào)度問題，即小車每次可以裝載多個工位所需物料。Emde等［8］在此基礎(chǔ)上對小車發(fā)車時間與配送工位進(jìn)行了集成決策。Golz 等［9］研究了多輛小車的組批和調(diào)度問題，設(shè)計了兩階段分解算法最小化配送人員數(shù)量。Zhou 等［10］考慮了以電動機(jī)器人作為送料工具的情況，提出了一種二次搬運(yùn)的策略，通過物料在不同機(jī)器人之間的轉(zhuǎn)運(yùn)降低了物料供給過程的能耗以及機(jī)器人的數(shù)量。

上述文獻(xiàn)對汽車裝配線的物料供給問題進(jìn)行了充分的研究，但汽車裝配線模型與飛機(jī)裝配線模型存在區(qū)別，將其直接應(yīng)用到飛機(jī)移動裝配線中存在局限性。汽車裝配線每個工位裝配作業(yè)單一，一般采用固定料箱，研究的重點(diǎn)集中于小車的裝載和調(diào)度問題；而飛機(jī)移動裝配線裝配周期長且并行作業(yè)多，不對線邊空間進(jìn)行合理的分配會造成物料存儲空間不足等問題。胡鑫銘等［11］建立了飛機(jī)移動裝配線物料配送與線邊存儲集成優(yōu)化模型，在物料組批和小車調(diào)度的基礎(chǔ)上，引入了物料在線邊空間的存儲決策。但文獻(xiàn)［11］假設(shè)空箱在裝配完成后統(tǒng)一回收，忽略了空箱對線邊空間的占用以及回收所需要的物流成本。陸志強(qiáng)等［12］建立了飛機(jī)移動裝配線物料配送與空箱回收集成決策模型，考慮讓小車在單次出行中同時執(zhí)行配送和回收任務(wù)，相比獨(dú)立回收策略減少了出行次數(shù)。但是由于小車在線邊只能按位置順序執(zhí)行各線邊單元上的任務(wù)，因此需要在小車從中心倉庫出發(fā)時就預(yù)留好空箱的存放空間，提高了小車返回倉庫時的裝載率卻降低了配送物料時的裝載率，相比獨(dú)立回收策略成本優(yōu)化有限。

事實上，對飛機(jī)移動裝配線的物料配送和空箱回收進(jìn)行集成決策存在如下權(quán)衡：在時間上，對物料分批和發(fā)車時間進(jìn)行決策時需要協(xié)調(diào)配送和回收任務(wù)的時間約束；在線邊空間上，料箱和空箱共享線邊存放空間，不對料箱到達(dá)線邊的時間以及空箱離開線邊的時間進(jìn)行科學(xué)的決策就會導(dǎo)致存放空間不足；在小車的裝載能力上，小車裝載率受到空箱和料箱存放位置前后關(guān)系的影響，不對線邊存儲進(jìn)行合理的規(guī)劃會降低兩類任務(wù)調(diào)度的集成度，增加出行成本。因此，對物料配送和空箱回收任務(wù)的集成決策展開研究對于保障飛機(jī)移動裝配線物料供給系統(tǒng)的穩(wěn)定性和效率具有重要意義。

基于對上述文獻(xiàn)研究成果的分析，本文在文獻(xiàn)［12］提出的物料供給問題中引入轉(zhuǎn)移策略和線邊存放位置的決策，提出了考慮轉(zhuǎn)移策略的物料配送和空箱回收集成優(yōu)化問題（Integrated optimization of material delivery and container pickup problem considering transfer strategy，IOMDCP-TS）。以飛機(jī)的一個裝配節(jié)拍為決策周期，綜合考慮小車裝載能力與線邊空間重復(fù)共享等因素，對料箱和空箱的組批方式與其在線邊存放的位置與時間進(jìn)行決策，建立了以最小化小車出行成本為目標(biāo)函數(shù)的數(shù)學(xué)模型并設(shè)計了以混沌差分進(jìn)化算法為框架的啟發(fā)式算法對該模型進(jìn)行求解。其中結(jié)合了發(fā)車時間動態(tài)調(diào)度算法、存放位置決策算法和轉(zhuǎn)移調(diào)度算法。最后通過數(shù)值實驗驗證了該算法的可行性和有效性。

1 問題描述和數(shù)學(xué)模型

飛機(jī)移動裝配線物料供給問題，是通過優(yōu)化各作業(yè)所需物料的配送、回收時間及其在線邊空間的存放位置，以達(dá)到最小化小車出行成本的目標(biāo)。圖1為飛機(jī)移動裝配線的物料供應(yīng)模式，整條裝配線被劃分為多個“虛擬大工位”，每個大工位內(nèi)存在大量的并行裝配作業(yè)，在工位旁劃定相關(guān)的區(qū)域用于存放各作業(yè)裝配所需的物料，并由多載量小車將物料按照裝配計劃從中心倉庫配送至對應(yīng)的線邊單元，同時將各線邊單元上的空箱運(yùn)回中心倉庫。

圖1 考慮轉(zhuǎn)移策略的物料配送及空箱回收模型示意圖Fig.1 Material delivery and container pickup model considering transfer strategy

小車裝載率受到空箱和料箱在線邊存放位置的相互關(guān)系的影響，因此。為了提高小車的裝載率，減少小車出行成本，本文提出了轉(zhuǎn)移策略，即允許小車將空箱放至線邊末尾的空箱暫存區(qū)后直接返回裝配線前端，由其他小車將暫存區(qū)的空箱運(yùn)回中心倉庫。通過該策略可以調(diào)整空箱的存放位置以及在線邊的存放時間，減少小車從中心倉庫到線邊的往返次數(shù)并優(yōu)化線邊物料的存放狀態(tài)。稱執(zhí)行料箱配送任務(wù)和空箱回收任務(wù)的小車為配送小車，執(zhí)行空箱轉(zhuǎn)移任務(wù)的小車為轉(zhuǎn)移小車。

該問題的假設(shè)與符號說明如下：

（1）以飛機(jī)移動裝配線的一個裝配節(jié)拍時間為決策周期。假定該周期內(nèi)某大工位包含n項裝配作業(yè)，J={1，2，…，n}，任意作業(yè)j∈J的執(zhí)行工期為tj，開始時間為TS，j，完成時間TF，j=TS，j+tj。

（2）將時間離散化 ，時間集合為D={1，2，…，Z}，Z表示所有作業(yè)操作時間總和，任意d∈D表示時間節(jié)點(diǎn)。tw，j={t|t=TDS，j…TDF，j}表示 作 業(yè)j在 線 邊 存 放 的 時 間 窗 。Jl表示線邊單元l的作業(yè)集合，表示線邊單元l第i個時間窗交集不為空集的作業(yè)集合。

（3）Ka表 示 配 送 小 車 集 合k∈Ka={1，2，…，h}；Kb表示轉(zhuǎn)移小車集合k∈Kb={1，2，…，h}。小車從倉庫到線邊的運(yùn)輸時間為tl，從裝配線前端到末端的移動時間為tb，飛機(jī)移動速度為v，表示單位時間內(nèi)經(jīng)過的線邊單元數(shù)量。任意配送行程r不得超過裝載能力上限Cmr∈Rk= {1，2，…， π}，Rk表示小車出行趟數(shù)集合。

（4）同一個作業(yè)的料箱由一輛小車一次性配送和回收，一輛小車一次可配送或回收多項作業(yè)所需的物料，作業(yè)j對物料的需求量為mj。作業(yè)j的物料抵達(dá)線邊的時間為TDS，j，離開線邊的時間為TF，j，配送提前期tp，j=TS，j-TDS，j，回收滯后期tI，j=TF，j-Tf，j。

（5）將線邊空間和作業(yè)空間離散化。如圖2 所示，作業(yè)空間描述了各作業(yè)在飛機(jī)上的裝配位置，用集合Γ={1，2，…，φ}表示，φ表示飛機(jī)的長度，任意lj∈Γ表示作業(yè)j在飛機(jī)上的裝配位置；線邊空間描述了物料在線邊的存儲位置，用l∈L={1，2，…，ξ}表示線邊單元的集合，ξ表示最大線邊單元的編號；用cl= {1，2，…，ψ}表示各線邊單元內(nèi)存儲位置的集合，ψ表示線邊單元的容量。對于任意一架飛機(jī)，狀態(tài)A 表示飛機(jī)開始進(jìn)入裝配線，移動到狀態(tài)B 的位置開始執(zhí)行作業(yè)j，移動到狀態(tài)D 的位置作業(yè)j執(zhí)行結(jié)束。狀態(tài)C 表示該作業(yè)執(zhí)行過程飛機(jī)的中間位置，定義該狀態(tài)下作業(yè)j裝配位置所對應(yīng)的線邊單元為該作業(yè)物料的中心存儲位置，即表示向上取整。

圖2 飛機(jī)作業(yè)裝配點(diǎn)及物料存放位置Fig.2 Assembly positions and material storage on aircraft moving assembly line

（6）為減少取料距離，作業(yè)j的物料只能存放在lm，j及其左右兩側(cè)各1個單位的線邊空間內(nèi)。為使線邊物料存放整齊有序，要求任一作業(yè)的全部物料應(yīng)連續(xù)存放于同一線邊單元內(nèi)。

（7）為了避免同一工段內(nèi)前后兩架飛機(jī)所需物料在線邊發(fā)生重疊，在每個大工位之前設(shè)置生產(chǎn)緩沖帶，該區(qū)間內(nèi)不進(jìn)行裝配作業(yè)。配送小車發(fā)車時刻晚于最大提前量約束tmin。

（8） 在裝配線末端設(shè)置空箱暫存區(qū)，轉(zhuǎn)移小車將空箱從線邊單元取下暫存在該區(qū)域內(nèi)，由配送小車運(yùn)回中心倉庫。

定義決策變量如下：

xjrk∈{0，1}，作業(yè)j的料箱在配送小車k第r趟出行配送時則xjrk等于1，否則取0。

yjrk∈{0，1}，作業(yè)j的空箱在配送小車k第r趟出行時回收則yjrk等于1，否則取0。

zjrk={0，1}，作業(yè)j的空箱在轉(zhuǎn)移小車k第r趟出行時轉(zhuǎn)移則zjrk等于1，否則取0。

(ta，rk，tb，rk，lj)，ta，rk表示配送小車k第r次出行的時間，tb，rk表示轉(zhuǎn)移小車k第r次出行的時間，lj為作業(yè)j的存放單元。

定義輔助變量如下：

根據(jù)上述模型假設(shè)和符號定義，對該問題建模如下：

式（1）為目標(biāo)函數(shù)，最小化小車出行成本，包括配送小車和轉(zhuǎn)移小車的出行次數(shù)以及車輛的固定成本。其中，ca，cb，cc分別是三者的單位成本系數(shù)；式（2）表示每個作業(yè)的料箱要在作業(yè)開始時間之前送達(dá)；式（3）～（5）表示每個作業(yè)的物料只能在作業(yè)完成之后回收或轉(zhuǎn)移，同時轉(zhuǎn)移時間要早于回收時間；式（6）表示作業(yè)配送時間要滿足最大提前量約束。式（7）～（9）表示單個作業(yè)物料的運(yùn)輸任務(wù)均只能由同一輛小車執(zhí)行；式（10）～（11）表示小車在整個行駛過程中都不能超過其載量上限；式（12）表示任意時刻線邊單元物料暫存量均不應(yīng)超過其最高限度；式（13）表示物料中心存放位置為其裝配過程中的中心位置。

2 算法設(shè)計

Boysen 等［13］研究了IOMDCP-TS 問題的一個子問題（從倉庫向單工位組批配送物料，目標(biāo)為優(yōu)化小車配送次數(shù)），并證明了該問題為強(qiáng) NP-hard 問題。而IOMDCP-TS 問題除了小車的配送調(diào)度外，還要考慮物料的存放以及小車的轉(zhuǎn)移調(diào)度，具有較高的復(fù)雜度。精確算法在求解這類大規(guī)模問題時效率較低。差分進(jìn)化算法具有速度快、魯棒性好等優(yōu)點(diǎn)，被廣泛應(yīng)用于生產(chǎn)調(diào)度等問題［14-15］。因此本文針對IOMDCP-TS問題的特點(diǎn)設(shè)計了以混沌差分進(jìn)化算法為框架的啟發(fā)式算法（HBCDE）。該算法上層對物料的組批方式進(jìn)行搜索，下層對每個包含物料組批方案的個體依次采用發(fā)車時間動態(tài)調(diào)度算法、存放位置決策算法和轉(zhuǎn)移調(diào)度算法進(jìn)行解碼；最后使用兩種修復(fù)算子對不可行解進(jìn)行修復(fù)。算法迭代過程中適應(yīng)度較高的個體所對應(yīng)的物料組批方案較優(yōu)，將作為優(yōu)質(zhì)解保留在記憶池中；低適應(yīng)度的個體將被淘汰或通過變異更新。設(shè)定Nm為最大迭代次數(shù)，g為當(dāng)前迭代次數(shù)。算法框架如圖3所示。

圖3 算法結(jié)構(gòu)Fig.3 algorithm structure

2.1 差分進(jìn)化算法框架

本文采用離散型差分進(jìn)化算法，使用雙層整數(shù)編碼。編碼的列數(shù)為作業(yè)的數(shù)量n，編碼數(shù)字為不大于作業(yè)數(shù)量的整數(shù)。上層數(shù)字代表該作業(yè)物料配送的批次序號，下層數(shù)字代表該作業(yè)物料回收的批次序號。如圖4所示作業(yè)1的物料在第二批配送，在第三批回收。為了提高算法搜索的效率，在初始種群中加入了兩條分別基于作業(yè)開始時間（FCFS）和作業(yè)結(jié)束時間（LFT）進(jìn)行排序的個體。

圖4 編解碼及修復(fù)示意圖Fig.4 Encoding, decoding and repairing representation

對于違反載量或時間約束的作業(yè)，從編號最小的開始執(zhí)行就近轉(zhuǎn)移規(guī)則，將該作業(yè)移入離當(dāng)前批次最近的批次，直到該作業(yè)滿足約束。如果所有批次都無法存放該作業(yè)則為該個體添加懲罰值。

混沌序列具有隨機(jī)性 、遍歷性等特點(diǎn)［16］。為了防止算法早熟收斂，本文在差分變異算子中引入混沌序列對比例因子進(jìn)行動態(tài)調(diào)整，根據(jù)logistic 方程yn+1，d=μyn，d(1—yn，d)產(chǎn)生混沌序列，然后通過載波方式將混沌變量映射到比例因子的取值范圍［0，2］。式中：n∈[1，Nmax]，Nmax取 100 ，d為變量的維度， μ 是混沌狀態(tài)的控制參數(shù)，本文取4，該參數(shù)下logistic方程完全進(jìn)入混沌狀態(tài)。在離散差分進(jìn)化算法中縮放比例因子根據(jù)Fch=yn，dexp (—t/tmax）動態(tài)產(chǎn)生，差分進(jìn)化中的變異算子如式（14）所示，其中r1，r2，r3為與i不同的互不相同的3 個隨機(jī)個體。關(guān)于差分進(jìn)化算法的通用部分不再贅述。

2.2 發(fā)車時間動態(tài)調(diào)度算法

在物料分批確定的情況下，對批次發(fā)車時間進(jìn)行優(yōu)化可以減少物料在線邊的占用時間。各批次的發(fā)車時間會受到最早作業(yè)開始時間和最晚空箱回收時間的約束。在該范圍內(nèi)，若料箱較多而發(fā)車時間偏早會導(dǎo)致配送提前期過長；若空箱較多而發(fā)車時間偏晚則會導(dǎo)致回收滯后期長。二者均會使料箱在線邊的占用時間延長，導(dǎo)致線邊存放空間不足。在參考文獻(xiàn)［13］提出的反向動態(tài)調(diào)度技術(shù)的基礎(chǔ)上，基于以下定理提出了發(fā)車時間動態(tài)調(diào)度算法，該算法能保證每個批次物料在線邊的總占用時間最短。應(yīng)用該算法得到的物料占用時間作為中間解，為后續(xù)存放位置決策算法的應(yīng)用奠定基礎(chǔ)。

定理：對于包含配送作業(yè)集合Jx和回收作業(yè)集合Jy的作業(yè)批次Bi，若滿足那么使得該批次物料在線邊占用最小的發(fā)車時間為

證明如下：

發(fā)車時間規(guī)劃這一子問題的目標(biāo)函數(shù)是在使得物料在線邊的占用在時間和空間兩個維度上最小，也就是使得非必需存放時間和物料量的乘積最小。

設(shè)，則該函數(shù)可以表示為

該函數(shù)為ti的單調(diào)函數(shù)，取值由ti的系數(shù)決定。

（4）更新該車的最早可用時刻為tea，(r+1)k=trk+2t0。

（5）如果i=|Ω|，轉(zhuǎn)（6），否則i=i+1，轉(zhuǎn)（3）。

發(fā)車時間的動態(tài)規(guī)劃算法步驟如下：

（2）令i=1，選擇首個批次的物料集合Bi，安排其發(fā)車時間

2.3 存放位置決策算法

在確定了物料在線邊的占用時間之后，可以將帶時間維度的線邊存放區(qū)看作一個長、寬、高分別對應(yīng)于裝配節(jié)拍、線邊長度和單位線邊單元容量的三維容器。胡鑫銘等［15］將物料在線邊的存放過程抽象為了一類帶單邊時間窗的三維裝箱問題。但該模型僅考慮了物料提前配送對于線邊的非必需占用，而在實際情況中回收的滯后也會導(dǎo)致空箱對于線邊空間的占用，因此本文考慮了一個帶雙邊時間窗的三維裝箱問題并為該問題設(shè)計了物料初始存儲位置生成算法并為無法存放的物料設(shè)計了修復(fù)算法。

物料的初始存儲位置生成算法如下：首先將線邊單元li的作業(yè)集合Jli中的所有作業(yè)按照mj(TDF，j—TDS，j)降序排列，按照該順序依次挑選作業(yè)放入其對應(yīng)線邊單元，判斷是否滿足三個維度上的約束，滿足則輸出該作業(yè)存放位置；若其存放范圍內(nèi)的線邊單元均不滿足則將其放入無法存放作業(yè)集合。

由于在配送小車發(fā)車時間的調(diào)度的過程中松弛了線邊容量的約束，因此可能會出現(xiàn)作業(yè)無法存放的情況。對于無法存放的作業(yè)集合Νp，采取局部替換和削峰算法兩種算子對不可行解進(jìn)行修復(fù)。首先使用不會增加額外成本的局部替換算子，若不能修復(fù)則采用存在額外成本的削峰算子進(jìn)行修復(fù)。

（1）局部替換：通過在局部范圍內(nèi)對作業(yè)存放位置進(jìn)行互換調(diào)整使線邊存量滿足約束。主要步驟為：對于無法存放的作業(yè)jun，從其可存放范圍中按照剩余空間降序選擇線邊單元，按物料量升序選擇作業(yè)直到可以替換jun。對新的jun首先判斷能否直接放入，若沒有則重復(fù)相同操作直到不存在無法存放的作業(yè)。

（2）削峰算法：參考文獻(xiàn)［17］提出的削峰操作，利用轉(zhuǎn)移策略將空箱離開線邊的時間提前，等同于削減物料占用立方體的長，解決因作業(yè)存放時間重合導(dǎo)致空間不足的問題。

削峰算法步驟如下：

（1）獲取無法存放的作業(yè)集合Νp，令未被選擇的作業(yè)集合Νo=Νp。

（2）從Νo中隨機(jī)取出一個作業(yè)的物料j，令jun=j，ltp=lm—1，j。

（3）將線邊單元ltp的作業(yè)集合的子集Jli按照升序排列。

（4）按順序遍歷各子集，判斷將能否通過將該子集中作業(yè)的離開線邊時間提前至作業(yè)結(jié)束時間的方式來將該作業(yè)放入。若，加入作業(yè)j后仍然滿足對于?t，mli，t＜φ，對于?j∈Jli*，令TF，j=TDF，j，Jli=Jli∪jun，Νp=Νp—jun，轉(zhuǎn)Step5；若且ltp≠ltp+1，令ltp=ltp+1，轉(zhuǎn)（3）；否則轉(zhuǎn)（5）。

（5）若Ν0≠Φ，轉(zhuǎn)（2），否則轉(zhuǎn)（6）。

（6）若Νp≠Φ，添加懲罰值到目標(biāo)函數(shù)中；否則輸出存放位置集合L={l1，l2，…ln}和需要削減存放時間的作業(yè)集合Jp。

如圖5 所示，有7 個作業(yè)的物料被存放在線邊，立方體的長代表該作業(yè)的物料在線邊存放的時間窗［TDS，j，TDF，j］，高代表該作業(yè)的物料量。矩形中深色的部分代表作業(yè)的在線邊存放的硬時間窗［TS，j，TF，j]，此時間窗無法調(diào)整；帶斜線的淺色部分代表作業(yè)的物料的配送提前期tp，j以及存放滯后期tI，j，可以通過更改發(fā)車時間來對其進(jìn)行調(diào)整。如圖5所示，按照初始存儲位置，作業(yè)5的物料會超出線邊單元的容量。使用削峰算法將作業(yè)7在線邊的時間窗從［TDS，7，TDF，7］縮短為［TDS，7，TF，7］，避免了作業(yè)5和作業(yè)7 的物料在時間上的重合，修復(fù)后使該線邊單元滿足了最大容量約束。

圖5 削峰算法Fig.5 Peak clipping algorithm

2.4 轉(zhuǎn)移調(diào)度算法

通過2.2 節(jié)和2.3 節(jié)中的算法解碼可以得到需要轉(zhuǎn)移的作業(yè)集合為超出線邊容量約束需要減少回收滯后期的作業(yè)集合，由2.4 節(jié)中的削峰算法計算得到。Ju表示無法即時裝載的作業(yè)集合。計算Ju的算法步驟如下：

（2）選中第一個還未被選擇的批次Bi，初始化批次Bi的載量

（3）遍歷各線邊單元，若該線邊單元存在配送作業(yè)，mBi=mBi—mj；若存在回收作業(yè)且mBi+mj≤Cm，則mBi=mBi+mj；若mBi+mj＞Cm，將該作業(yè)加入轉(zhuǎn)移作業(yè)集合。

（4）若所有批次都已被選擇，輸出無法即時裝載的作業(yè)集合Ju；否則轉(zhuǎn)（2）。

將Jt按完成時間進(jìn)行升序排列，使用最小批量法生成轉(zhuǎn)移批次的初始解，以出行次數(shù)最少為目標(biāo)對最優(yōu)轉(zhuǎn)移批次進(jìn)行搜索。轉(zhuǎn)移小車出發(fā)時間的決策問題是配送小車出發(fā)時間決策問題的一個特例，即各轉(zhuǎn)移批次中只包含回收作業(yè)，不包含配送作業(yè)，因此最優(yōu)發(fā)車時間依然適用于2.2 節(jié)中所證明的定理。

3 數(shù)值實驗

本文使用文獻(xiàn)［11］所構(gòu)建的算例集進(jìn)行數(shù)值實驗，參考了文獻(xiàn)［18］關(guān)于出行成本的參數(shù)設(shè)置，設(shè)定單次配送小車行駛成本45$，單次轉(zhuǎn)移小車行駛成本9$，單輛小車固定成本45$。小車容量Cm=20，線邊單元容量ξ=20，中心倉庫到線邊裝卸貨的時間tl=4，線邊運(yùn)行時間tb=1，飛機(jī)移動速度v=0.5。構(gòu)建了30、60、120等3個規(guī)模的算例來進(jìn)行實驗，每個規(guī)模的算例集包括3組，每組10個算例。本文在Pycharm 2021.2.1（community edition）平臺上使用Python 語言進(jìn)行編程測試，計算機(jī)配置為Ryzen 74 800H處理器，2.9GHz主頻，16G內(nèi)存。

3.1 策略對比

將本文提出的轉(zhuǎn)移策略TS 和文獻(xiàn)［12］所提出的集成調(diào)度策略CHBG以及傳統(tǒng)的兩階段調(diào)度策略CAS 進(jìn)行對比。CAS 策略是指將物料配送和空箱回收作為兩個獨(dú)立的問題，分別進(jìn)行調(diào)度，最后將總出行成本相加；CHBG 策略是指對物料配送和空箱回收進(jìn)行集成調(diào)度，一個批次可以同時執(zhí)行這兩種任務(wù)；TS 策略是在CHBG 策略的基礎(chǔ)上，允許空箱在線邊進(jìn)行轉(zhuǎn)移以優(yōu)化料箱和空箱的存放次序。對三種策略采用相同的解碼算法。對比的結(jié)果如表 1所示，表格中Ci代表策略i物料配送的總成本，Gi代表策略i的成本和三種策略中的最低成本之間的差距，計算如下：

對表1 的數(shù)據(jù)進(jìn)行分析可以得到如下實驗結(jié)論：

（1）在成本上，在3種規(guī)模的算例下， TS策略都擁有最低的總成本，而且隨著算例規(guī)模的上升，相比另外兩種策略的優(yōu)化幅度也進(jìn)一步提升。在120的算例規(guī)模下，TS 策略相比CHBG 策略和CAS 策略優(yōu)化比例分別達(dá)到了19.40%和29.70%。

（2）在可行解比例上，TS 策略也擁有最高的求解成功率。如圖6所示，在30規(guī)模的算例下，3種策略都能對所有算例成功求解；在60 規(guī)模的算例下，TS策略依然能夠成功求解所有算例，而CHBG策略和CAS 策略都下降到了93.33%；在120 的規(guī)模下，TS 策略求解成功率達(dá)到了86.67%，而CHBG 策略和CAS策略分別下降到了76.67%和73.33%。

圖6 不同策略成本及可行解比例對比Fig.6 Comparison of cost and proportion of feasible solution between different strategies

綜上所述，轉(zhuǎn)移策略的引入能夠有效降低物料配送和空箱回收集成模型的小車出行成本和不可行解比例，說明該策略在物料批次的劃分和存放位置的決策上都具有優(yōu)越性。

3.2 算法對比

為了驗證HBCDE 算法的性能，將該算法與去除修復(fù)算法的HBCDE-RA，標(biāo)準(zhǔn)DE 算法和CMAES 算法進(jìn)行了對比。在30、60、120 等3 個規(guī)模的算例下進(jìn)行了實驗，每個算例集包括30 個算例。用可行解比例和總成本兩個指標(biāo)作為衡量標(biāo)準(zhǔn)，分別用P和C進(jìn)行表示。分析表2中的實驗結(jié)果可以得到如下結(jié)論：

表2 不同算法結(jié)果對比Tab.2 Comparison of experimental results between different models

表3 錯位度與優(yōu)化幅度的回歸分析Tab.3 Regression analysis of misalignment and optimization amplitude

（1）在算法框架的對比中，HBCDE 算法在3 種規(guī)模的算例下，都擁有更低的成本和更高的求解成功率，隨著作業(yè)規(guī)模的增大，優(yōu)勢更加明顯。在規(guī)模為120 的算例下，相比HBCDE 算法和CMAES 算法，該算法在成本上分別優(yōu)化了6.65%和4.49%，在求解成功率上與CMAES算法持平，比DE算法高出6.67%。說明本文使用的混沌差分進(jìn)化算法在求解物料組批配送這一類組合優(yōu)化問題上具有優(yōu)越性，可以得到更高的的求解質(zhì)量和可行解比例。

（2）在修復(fù)算法的效果驗證實驗中，加入修復(fù)算法的HBCDE-RA 算法比HBCDE 算法成本降低了4.33%，求解成功率提高了20%，說明該修復(fù)算法在三維裝箱這類問題的不可行解修復(fù)上具有良好的效果。

3.3 算例錯位度對轉(zhuǎn)移策略效果的影響

為了探究算例中影響轉(zhuǎn)移策略有效性的因素，本文綜合考慮小車運(yùn)輸機(jī)制和作業(yè)信息提出了一項以錯位度（Dislocation degree，dld）為核心的評價指標(biāo)，該指標(biāo)表征了算例中空箱的回收任務(wù)與配送任務(wù)相互沖突的可能性。定義輔助變量Dl，ij，代表兩個算例之間的錯位關(guān)系，如果作業(yè)j完成時間和中心存放位置都小于作業(yè)i則Dl，ij=1，否則Dl，ij=0，如式（19）所示。對于任意作業(yè)j，錯位度計算方式如式（20）所示，|J|表示作業(yè)數(shù)量。

分別繪制81 個成功求解的算例的錯位度和轉(zhuǎn)移策略的優(yōu)化幅度的折線圖，如圖7 所示可以看出兩條曲線的形狀高度吻合。計算兩個指標(biāo)的回歸方程為G= —0.0901 + 1.809dld。方差分析表如3所示，P值表示樣本間的差異由抽樣誤差所致的可能性，其值小于0.001 說明錯位度對于轉(zhuǎn)移策略的優(yōu)化幅度有顯著的影響，而Pearson 相關(guān)性系數(shù)為0.735，說明二者的關(guān)系為正相關(guān)。對于錯位度高的算例采用轉(zhuǎn)移策略可以降低更多的成本。該評估方法也可以應(yīng)用到其他采用循環(huán)配送方式的料箱配送和回收集成調(diào)度問題中。

圖7 錯位度和優(yōu)化幅度曲線的對比Fig.7 Curve comparison of misalignment and optimization amplitude

3.4 成本系數(shù)對轉(zhuǎn)移策略有效性的影響

成本系數(shù)之間的大小關(guān)系可能會影響該策略的有效性。為了探究二者比值處于什么范圍內(nèi)該策略有效，對三種規(guī)模的算例進(jìn)行實驗，繪制臨界點(diǎn)的箱線圖如圖8 所示。比值在臨界點(diǎn)以下則該策略有效。臨界點(diǎn)的計算方法為：以0.01為間隔生成總成本關(guān)于轉(zhuǎn)移與配送成本系數(shù)比值的變化曲線，觀察與CHBG 策略成本的交叉點(diǎn)，以交叉點(diǎn)左側(cè)的值為臨界點(diǎn)?？梢钥闯? 組規(guī)模算例的臨界值分布在［0.61，0.84］的區(qū)間內(nèi)，規(guī)模越大，臨界值越高。在具體裝配線的決策過程中，可以通過計算這兩者的比值是否達(dá)到臨界值來判斷采用轉(zhuǎn)移策略是否有效。

圖8 不同規(guī)模算例下的臨界值Fig.8 Critical value of examples with different scales

4 結(jié)論與展望

（1）在飛機(jī)移動裝配線中引入轉(zhuǎn)移策略對物料供給模型進(jìn)行優(yōu)化。將料箱的配送、回收以及線邊存儲這三類互相影響的問題的決策整合到一個集成模型當(dāng)中，并設(shè)計了元啟發(fā)式算法對該模型進(jìn)行求解。通過數(shù)值實驗驗證了該模型和算法的有效性，為飛機(jī)移動裝配線物料供給問題的研究提供了參考和借鑒。

（2）對影響轉(zhuǎn)移策略有效性的兩種因素進(jìn)行了研究。首先提出了基于作業(yè)信息計算的預(yù)測指標(biāo)“錯位度”。使用回歸方程對轉(zhuǎn)移策略所能帶來的優(yōu)化幅度進(jìn)行預(yù)測，通過方差分析驗證了該指標(biāo)的可靠性；其次研究了成本系數(shù)對調(diào)度性能的影響，通過數(shù)值實驗界定了該策略的有效范圍，為該策略的使用提供了參考。

（3）后續(xù)可以考慮使用機(jī)器學(xué)習(xí)對不同運(yùn)行策略在不同算例下的效果進(jìn)行預(yù)測，實現(xiàn)不同裝配線情況下的動態(tài)調(diào)度，以應(yīng)對具有高不確定性的作業(yè)環(huán)境。

作者貢獻(xiàn)聲明：

陸志強(qiáng)：提出研究選題，設(shè)計研究思路和論文框架；

王韻熹：設(shè)計研究思路，完成實驗設(shè)計并實施，分析數(shù)據(jù)，撰寫論文。