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

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

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

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

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

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

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

基于對(duì)上述文獻(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ī)的一個(gè)裝配節(jié)拍為決策周期，綜合考慮小車裝載能力與線邊空間重復(fù)共享等因素，對(duì)料箱和空箱的組批方式與其在線邊存放的位置與時(shí)間進(jìn)行決策，建立了以最小化小車出行成本為目標(biāo)函數(shù)的數(shù)學(xué)模型并設(shè)計(jì)了以混沌差分進(jìn)化算法為框架的啟發(fā)式算法對(duì)該模型進(jìn)行求解。其中結(jié)合了發(fā)車時(shí)間動(dòng)態(tài)調(diào)度算法、存放位置決策算法和轉(zhuǎn)移調(diào)度算法。最后通過數(shù)值實(shí)驗(yàn)驗(yàn)證了該算法的可行性和有效性。

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

飛機(jī)移動(dòng)裝配線物料供給問題，是通過優(yōu)化各作業(yè)所需物料的配送、回收時(shí)間及其在線邊空間的存放位置，以達(dá)到最小化小車出行成本的目標(biāo)。圖1為飛機(jī)移動(dòng)裝配線的物料供應(yīng)模式，整條裝配線被劃分為多個(gè)“虛擬大工位”，每個(gè)大工位內(nèi)存在大量的并行裝配作業(yè)，在工位旁劃定相關(guān)的區(qū)域用于存放各作業(yè)裝配所需的物料，并由多載量小車將物料按照裝配計(jì)劃從中心倉庫配送至對(duì)應(yīng)的線邊單元，同時(shí)將各線邊單元上的空箱運(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í)間，減少小車從中心倉庫到線邊的往返次數(shù)并優(yōu)化線邊物料的存放狀態(tài)。稱執(zhí)行料箱配送任務(wù)和空箱回收任務(wù)的小車為配送小車，執(zhí)行空箱轉(zhuǎn)移任務(wù)的小車為轉(zhuǎn)移小車。

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

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

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

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

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

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

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

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

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

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

定義決策變量如下：

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

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

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

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

定義輔助變量如下：

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

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

2 算法設(shè)計(jì)

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

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

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

混沌序列具有隨機(jī)性 、遍歷性等特點(diǎn)［16］。為了防止算法早熟收斂，本文在差分變異算子中引入混沌序列對(duì)比例因子進(jìn)行動(dòng)態(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）動(dòng)態(tài)產(chǎn)生，差分進(jìn)化中的變異算子如式（14）所示，其中r1，r2，r3為與i不同的互不相同的3 個(gè)隨機(jī)個(gè)體。關(guān)于差分進(jìn)化算法的通用部分不再贅述。

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

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

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

證明如下：

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

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

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

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

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

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

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

2.3 存放位置決策算法

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

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

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

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

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

削峰算法步驟如下：

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

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

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

（4）按順序遍歷各子集，判斷將能否通過將該子集中作業(yè)的離開線邊時(shí)間提前至作業(yè)結(jié)束時(shí)間的方式來將該作業(yè)放入。若，加入作業(yè)j后仍然滿足對(duì)于?t，mli，t＜φ，對(duì)于?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}和需要削減存放時(shí)間的作業(yè)集合Jp。

如圖5 所示，有7 個(gè)作業(yè)的物料被存放在線邊，立方體的長(zhǎng)代表該作業(yè)的物料在線邊存放的時(shí)間窗［TDS，j，TDF，j］，高代表該作業(yè)的物料量。矩形中深色的部分代表作業(yè)的在線邊存放的硬時(shí)間窗［TS，j，TF，j]，此時(shí)間窗無法調(diào)整；帶斜線的淺色部分代表作業(yè)的物料的配送提前期tp，j以及存放滯后期tI，j，可以通過更改發(fā)車時(shí)間來對(duì)其進(jìn)行調(diào)整。如圖5所示，按照初始存儲(chǔ)位置，作業(yè)5的物料會(huì)超出線邊單元的容量。使用削峰算法將作業(yè)7在線邊的時(shí)間窗從［TDS，7，TDF，7］縮短為［TDS，7，TF，7］，避免了作業(yè)5和作業(yè)7 的物料在時(shí)間上的重合，修復(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é)中的削峰算法計(jì)算得到。Ju表示無法即時(shí)裝載的作業(yè)集合。計(jì)算Ju的算法步驟如下：

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

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

3.1 策略對(duì)比

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

對(duì)表1 的數(shù)據(jù)進(jìn)行分析可以得到如下實(shí)驗(yà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種策略都能對(duì)所有算例成功求解；在60 規(guī)模的算例下，TS策略依然能夠成功求解所有算例，而CHBG策略和CAS 策略都下降到了93.33%；在120 的規(guī)模下，TS 策略求解成功率達(dá)到了86.67%，而CHBG 策略和CAS策略分別下降到了76.67%和73.33%。

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

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

3.2 算法對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論與展望

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

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

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

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

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

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