林永昊 姚明山 趙 磊，3 朱道立，3

（1.上海交通大學(xué) 中美物流研究院，上海 200030；2.同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092；3.上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院，上海 200030）

1　問題描述

汽車零部件三維裝載問題是指對給定一輛待配載貨車以及一批待裝貨物，確定一個(gè)可行的裝載方案使得在滿足約束條件（貨物不與車廂相嵌約束；貨物互不相嵌約束；貨物承重約束等）下，車輛裝載率（裝入貨車的所有貨物體積之和／貨車車廂體積*100%）最大。

該問題滿足如下假設(shè)條件：

（1）車廂及待裝貨物均為長方體；

（2）放入的貨物完全被包含在車廂內(nèi)；

（3）貨物只能以棱平行（或垂直）于車廂的棱的方向放置；

（4）貨物只能繞高度棱旋轉(zhuǎn)，不可傾倒放置。

如圖1所示，以面向車頭方向車廂左前角作為坐標(biāo)原點(diǎn)建立笛卡爾坐標(biāo)系，待裝貨物的裝載位置由其最靠近坐標(biāo)原點(diǎn)的角點(diǎn)坐標(biāo)值表示，則可行裝載方案中各已裝入貨物的裝載位置可用貨物的角點(diǎn)坐標(biāo)值表示。

圖1　坐標(biāo)系示意圖

在圖1所示建立坐標(biāo)系下，汽車零部件三維裝載問題的數(shù)學(xué)模型可表示如下：

1.1　集合

I=｛1，…，N｝：待裝載貨物的集合。

1.2　參數(shù)

Li：貨物i的長度，i∈I；

Wi：貨物i的寬度，i∈I；

Hi：貨物i的高度，i∈I；

Qi：貨物i的重量，i∈I；

Vi：貨物i的體積，i∈I，Vi=Li×Wi×Hi；

Si：貨物i的承重重量，i∈I；

CL：車廂的長度；

CW：車廂的寬度；

CH：車廂的高度；

CV：車廂的體積，CV=CL×CW×CH。

1.3　變量

連續(xù)決策變量：用于刻畫裝載方案的連續(xù)變量。

xi：貨物i的放置位置的x軸坐標(biāo)，i∈I；

yi：貨物i的放置位置的y軸坐標(biāo)，i∈I；

zi：貨物i的放置位置的z軸坐標(biāo)，i∈I；

0-1決策變量：用于刻畫裝載方案的0-1變量。

αi：貨物i的裝載在車上則αi=1，否則，αi=0，i∈I；

βi：貨物i需要旋轉(zhuǎn)90°，如果貨物i長邊平行Y軸，寬邊平行X軸則βi=1，反之則βi=0；

0-1輔助決策變量：用于保證決策變量所刻畫的裝載方案為可行方案的變量。

lpij：貨物j在貨物i的X軸正方向上，則lpij=1，否則lpij=0；

wpij：貨物j在貨物i的Y軸正方向上，則wpij=1，否則wpij=0；

hpij：貨物j在貨物i的Z軸正方向上，則hpij=1，否則hpij=0。

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

該問題的求解目標(biāo)為車輛裝載率（裝入貨車的所有貨物體積之和／貨車車廂體積*100%）最大，即如式（1）所示：

（2）貨物互不嵌入約束。

（3）貨物與車廂不相嵌約束，即如式（12-14）所示：

1.5　約束條件

一般三維裝載問題約束。一般三維裝載問題的約束主要有體積約束、裝入貨物互不嵌入約束和貨物與車廂不相嵌約束，具體約束的數(shù)學(xué)表達(dá)如下：

（1）體積約束：裝入所有貨物的體積總和不超過車廂最大容積，即如式（2）所示：

（3）堆疊約束：零部件包裝箱有多種類型，存在不同堆疊限制：①不允許堆疊；②僅允許同類型、同尺寸堆疊；③允許同類型，同尺寸／底面尺寸小的堆疊；④允許不同類型、同尺寸按既定順序堆疊；⑤允許不同類型，同尺寸／底面尺寸小的堆疊（本條約束過于繁瑣，本文中省略其數(shù)學(xué)模型表述）。

汽車零部件裝載中特殊約束。汽車零部件裝載問題中的特殊約束主要有完全支撐約束、單箱承重約束和貨物堆疊約束，具體數(shù)學(xué)表達(dá)如下：

（1）完全支撐約束：貨物必須得到車廂底部或其他一件貨物的完全支撐，不允許懸空。

（2）單箱承重約束：貨物疊放時(shí)，貨物重量不得大于支撐其擺放的貨物的承重能力。

2　基于裝載塊序列的混合模擬退火算法

由于汽車零部件三維裝載問題較經(jīng)典三維裝箱問題在貨物堆疊方面更為復(fù)雜，現(xiàn)存的求解經(jīng)典三維裝箱問題的算法很難直接應(yīng)用到汽車零部件三維裝載問題上。因此，本文設(shè)計(jì)了一種基于裝載塊裝入順序的模擬退火算法。首先，將單箱貨物構(gòu)造成為裝載塊（裝載塊不能在高度上堆疊），將三維裝載問題降為二維裝載問題。然后，利用模擬退火過程，將各裝載塊裝入車廂。該算法以裝載塊的裝載順序作為編碼方式，通過模擬退火過程隨機(jī)調(diào)整裝載序列以優(yōu)化裝載序列對應(yīng)的裝載方案，最后輸出算法結(jié)束時(shí)產(chǎn)生的裝載序列對應(yīng)的裝載方案。以下算法流程中的集合、參數(shù)和變量的定義沿用上一小節(jié)中定義。

2.1　整體算法框架

基于裝載塊序列的混合模擬退火算法流程如下：

基于裝載塊序列的混合模擬退火算法

輸入：2.1中的待裝貨物集合；2.2中所有參數(shù)；降溫速度η，0＜η＜1；最大迭代次數(shù)n；降溫目

息βi，裝載率

否則，回到Step 4。

2.2　裝載塊生成子算法

裝載塊生成子算法輸入：2.1中的待裝貨物集合；2.2中所有參數(shù)。輸出：裝載塊序列B_list；貨物與裝載塊的對應(yīng)關(guān)系。

Step 1：輸入2.1中的待裝貨物集合；2.2中所有參數(shù)。

Step 2：按照底面積從大到小順序?qū)⒋b貨物排序，生成待裝貨物列表I_list；初始化iI=1，iB=1。

Step 3：將I_list中第iI個(gè)貨物放置于裝載塊iB，并I_list=I_list＼｛iI｝。

Step 4：選擇I_list中滿足堆疊、承重等約束條件可堆疊于裝載塊iB的貨物中，底面積最大的貨物jI。

Step 1：輸入2.1中的待裝貨物集合和2.2中的所有參數(shù)；設(shè)置降溫速度η，0＜η＜1；最大迭代次數(shù)n；降溫目標(biāo)tgoal。

Step 2：調(diào)用裝載塊生成子算法，生成裝載塊集合B。

Step 3：根據(jù)B隨機(jī)生成裝載塊的一個(gè)排序B_list（裝載序列）；設(shè)置初始溫度t＞tgoal。

Step 4：設(shè)置k=1。

Step 5：調(diào)用裝載方案生成子算法，計(jì)算適應(yīng)度值F=f（B_list）。

Step 6：調(diào)用隨機(jī)擾動(dòng)產(chǎn)生新的裝載序列B′_list；調(diào)用裝載方案生成子算法，計(jì)算適應(yīng)度值F′=f（B′_list）。

Step 7：判斷適應(yīng)度值是否改進(jìn)，若F′＞F，則接受新的裝載序列B_list=B′_list；否則按照Metropolis概率準(zhǔn)則接受新的裝載序列；令k=k+1。

Step 8：判斷是否k＞n，若是則執(zhí)行Step 9；否則回到Step 5。

Step 9：冷卻退火，令t=t·η。

Step 10：判斷是否t＜tgoal，若是則調(diào)用裝載方案生成子算法，由B_list生成并輸出裝載方案，即對任意i∈I，放置位置的x軸坐標(biāo)xi，y軸坐標(biāo)yi，z軸坐標(biāo)zi，是否裝載在車上αi，是否需要旋轉(zhuǎn)90°信標(biāo)tgoal。

輸出：裝載方案，即對任意i∈I，放置位置的x軸坐標(biāo)xi；y軸坐標(biāo)yi；z軸坐標(biāo)zi；是否裝載在車上αi；是否需要旋轉(zhuǎn)90°信息βi。裝載率f（B_list）

Step 5：若存在jI，則將jI放置于裝載塊iB目前已存在貨物的上一層，并I_list=I_list＼｛jI｝，回到Step 4。若不存在jI，則進(jìn)入Step 6。

Step 6：判斷I_list是否為空，若是，則輸出結(jié)果；若不是，iB=iB+1，回到Step 3。

由此生成的裝載塊，塊與塊之間在高度方向（z軸方向）上不能相互疊放。

2.3　裝載方案生成子算法

為方便表達(dá)，這里做如下定義：

定義1（格局）設(shè)某一時(shí)刻，車廂內(nèi)已放入若干裝載塊，還有若干個(gè)裝載塊待放，這稱為一個(gè)格局。車廂內(nèi)尚未放入任何裝載塊時(shí)，稱為初始格局。所有裝載塊已放入車廂，或車廂外剩余的裝載塊無法再放入時(shí)，稱為終止格局。

定義2（可裝載點(diǎn)）可裝載點(diǎn)定義參考文獻(xiàn)［3］，可裝載點(diǎn)是在當(dāng)前裝載格局下車廂中裝載塊的可行放置點(diǎn)。如圖2-（a）所示，初始可裝載點(diǎn)即為原點(diǎn)，坐標(biāo)為（0，0），當(dāng)裝入長為l寬為w的裝載塊后，可裝載點(diǎn)更新為（1，0）、（0，w）。如圖2-（b）所示，在某個(gè)裝載格局下，裝入3個(gè)裝載塊，當(dāng)4號裝載塊裝入時(shí)，新增兩個(gè)可裝載點(diǎn)。

定義3（可裝載度）：可裝載度表示待裝載塊與可裝載點(diǎn)的匹配程度，用于指導(dǎo)每個(gè)裝載動(dòng)作中可裝載點(diǎn)的選擇對任意裝載塊i在給定方向下和可裝載點(diǎn)j之間的可裝載度定義為一個(gè)向量當(dāng)按給定方向可裝載點(diǎn)j裝不下目標(biāo)待裝載塊i時(shí)，令Wkij=-1＜0，k∈｛1，2，3，4｝。反之，向量中各元素計(jì)算方法如下：

圖2　可裝載點(diǎn)示意圖

W1ij：新生成可裝載點(diǎn)指標(biāo)。表示放入車廂后新生成的可裝載點(diǎn)數(shù)量，NE∈｛0，1，2｝，NE越小，表示箱子與當(dāng)前空間的緊密度越高，因此，定義：

W2ij：穴度。具體定義參考文獻(xiàn)［4］，Bl，Bw表示裝入裝載塊的長和寬，Bd表示裝入裝載塊與車廂邊界或相鄰裝載塊最小距離，定義：

W3ij：封閉空間面積指標(biāo)。封閉空間是指裝箱過程中，由裝載塊間或裝載塊與車廂四個(gè)邊界圍成的空白區(qū)域，面積為BA。封閉空間面積越大，說明裝載空間浪費(fèi)越嚴(yán)重，因此定義封閉空間面積指標(biāo)W3ij：

貼邊數(shù)。表示新裝入裝載塊與已裝入裝載塊或車廂邊界相貼的邊數(shù)

對任意裝載塊i和可裝載點(diǎn)我們記Wij大于裝載度如果；或和和或和裝載方案生成子算法的流程如下：

裝載方案生成子算法

輸入：裝載塊序列B_list；貨物與裝載塊的對應(yīng)關(guān)系。

輸出：裝載方案，即對任意貨物i∈I，放置位置的x軸坐標(biāo)xi；y軸坐標(biāo)yi；z軸坐標(biāo)zi；是否裝載在車上αi；是否需要旋轉(zhuǎn)90°信息βi。適應(yīng)度值，即裝載率f（B_list）。

Step 1：輸入裝載塊序列B_list；貨物與裝載塊的對應(yīng)關(guān)系，設(shè)置iB=1。

Step 2：選擇B_list中第iB個(gè)裝載塊；獲得當(dāng)前格局下的可裝載點(diǎn)列表EP；計(jì)算B_list中第iB個(gè)裝載塊對EP中各可裝載點(diǎn)橫放／豎放的可裝載度值；第iB個(gè)裝載塊對EP中各可裝載點(diǎn)橫放／豎放的可裝載度值均小于0，則進(jìn)入Step 4；否則，選擇可裝載點(diǎn)列表EP中可裝載度值最大的可裝載點(diǎn)和其對應(yīng)的裝載方向作為第iB個(gè)裝載塊的裝載位置和裝載方向，進(jìn)入Step 3。

Step 3：按照當(dāng)前裝入裝載塊，得到一個(gè)新的格局。

Step 4：iB=iB+1。

Step 5：如果iB＞length（B_list），則算法終止，輸出裝載方案，即對任意貨物i∈I，放置位置的x軸坐標(biāo)xi；y軸坐標(biāo)yi；z軸坐標(biāo)zi；是否裝載在車上αi；是否需要旋轉(zhuǎn)90°信息βi。裝載率f（B_list）=否則，回到Step 2。

2.4　隨機(jī)擾動(dòng)

采用隨機(jī)置換的方式對裝載序列進(jìn)行調(diào)整，即在裝載序列中隨機(jī)選擇兩個(gè)裝載塊位置進(jìn)行交換，其他裝載塊排序不變。如初始裝載序列為［A，B，C，D，E，F(xiàn)，G］，隨機(jī)選擇到第1位和第5位進(jìn)行交換，則新的裝載序列為［E，B，C，D，A，F(xiàn)，G］。

2.5　Metropolis準(zhǔn)則

本文求解目標(biāo)為裝載率最大，設(shè)置評價(jià)函數(shù)為裝載率F，若ΔF=F′-F≥0，則接受新的裝載序列，若ΔF＜0，則采用Metropolis準(zhǔn)則，生成一個(gè)（0，1）之間的隨機(jī)數(shù)θ，若θ小于接受概率exp（10*ΔF／t），則同樣接受新的裝載序列，否則保留當(dāng)前裝載序列。

3　算例分析

本文選取上海某汽車物流企業(yè)的零部件入廠物流三維裝載的實(shí)際運(yùn)營數(shù)據(jù)，將算法優(yōu)化裝載方案與實(shí)際運(yùn)作中人工編排裝載方案進(jìn)行比較，驗(yàn)證算法能否有效處理零部件三維裝載問題，提高作業(yè)效率。

3.1　單箱裝載

（1）算例數(shù)據(jù)

如表1所示，共有8類159箱待裝零部件，數(shù)據(jù)包含貨物編號、長、寬、高、需求箱數(shù)等，采用9.6M貨車裝載，車廂長寬高分別為9400cm，2300cm，2300cm。

表1　單箱裝載數(shù)據(jù)

（2）算例結(jié)果

如表2所示，待裝零部件全部裝入車廂，裝載率達(dá)93.9%，裝載方案給出了零部件裝入順序、擺放方向及對應(yīng)的坐標(biāo)值，裝載效果如圖3表示。

表2　單箱裝載結(jié)果

圖3　單箱裝載結(jié)果（單位：cm）

3.2　多箱裝載-單日數(shù)據(jù)對比

為了進(jìn)一步驗(yàn)證算法的有效性，選取該汽車物流企業(yè)一條取貨路線某天的全部裝箱需求數(shù)據(jù)，采用串行裝箱方式即裝滿一車廂再裝下一車廂，直至裝完全部待裝貨物，比較裝載率及車輛使用數(shù)等指標(biāo)。

（1）算例數(shù)據(jù)：

共有31類1942箱待裝零部件，限于篇幅未列出具體數(shù)據(jù)。采用12M貨車裝載，車廂長寬高分別為11800cm，2300cm和2300cm。

（2）算例結(jié)果：

如表3所示，算法平均裝載率76.2%，需要使用10輛車；而實(shí)際運(yùn)營中人工作業(yè)結(jié)果為安排了12輛車，平均裝載率為63.5%。

表3　20170503裝載算例結(jié)果

3.3　多箱裝載——10日數(shù)據(jù)對比

選取該路線連續(xù)10日裝箱數(shù)據(jù)，共有16950箱待裝零部件，限于篇幅未列出具體數(shù)據(jù)，僅列出每天待裝零部件類型、需求箱數(shù)、算法結(jié)果、人工結(jié)果以及優(yōu)化效果，如表4所示。

圖4　裝載率對比

圖5　車輛使用數(shù)對比

表4　連續(xù)10日裝載結(jié)果比較

圖6　運(yùn)輸成本對比

結(jié)果表明，本文算法能有效解決汽車零部件三維裝載問題，在車輛裝載率、車輛使用數(shù)等方面均優(yōu)于人工編排結(jié)果。算法優(yōu)化后平均使用車輛數(shù)為6.7輛，平均裝載率75.5%，實(shí)際運(yùn)營使用車輛數(shù)8.2輛，平均裝載率62.9%。相比于人工結(jié)果，算法優(yōu)化后平均車輛使用數(shù)減少1.5輛，平均裝載率提升12.6%。

從成本角度而言，優(yōu)化后車輛使用數(shù)減少，直接降低了運(yùn)輸成本、裝卸成本及人力成本等。以運(yùn)輸成本為例，該取貨路線平均運(yùn)輸距離為140公里，運(yùn)輸費(fèi)用為3.4元／公里，優(yōu)化后10日運(yùn)輸成本減少了7140元，較人工結(jié)果降低18%。

4　總結(jié)

本文針對汽車零部件入廠物流實(shí)踐中的零部件三維裝載問題，考慮汽車零部件堆疊規(guī)則、單箱承重等現(xiàn)實(shí)約束，設(shè)計(jì)了基于裝載塊裝載序列的混合模擬退火算法。通過使用上海某汽車物流企業(yè)的實(shí)際數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，并與人工操作方案進(jìn)行對比，驗(yàn)證了本文提出的算法能有效解決汽車零部件三維裝載問題。未來的研究方向?yàn)槿∝浡窂脚c裝載的協(xié)同優(yōu)化問題。

參考文獻(xiàn)：

［1］ BOYSEN N，EMDE S，HOECK M，et al.Part logistics in the automotive industry：decision problems，literature review and research agenda［J］.European Journal of Operational Research，2015，242（1）：107-120.

［2］ 何明珂，張屹然.國內(nèi)汽車零件入廠物流研究綜述［J］.中國流通經(jīng)濟(jì)，2011，25（7）：31-36.

［3］ CRAINIC T G，PERBOLI G，TADEI R.Extreme point-based heuristics for three-dimensional bin packing［J］.Informs Journal on Computing，2008，20（3）：368-384.

［4］ 何琨，黃文奇，金燕.基于動(dòng)作空間求解二維矩形Packing問題的高效算法［J］.軟件學(xué)報(bào)，2012，34（5）：1037-1044.

［5］ 何琨，黃文奇.基于動(dòng)作空間的三維裝箱問題的確定性高效率求解算法［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（8）：1786-1793.

［6］ PARRENO F，ALVAREZ-VALDES R，OLIVEIRA J F，et al.Neighborhood structures for the container loading problem：a VNS implementation［J］.Journal of Heuristics，2010，16（1）：1-22.

［7］ FANSLAU T，BORTFELDT A.A tree search algorithm for solving the container loading problem［J］.Informs Journal on Computing，2010，22 （2）：222-235.

［8］ 張德富，彭煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（11）：2147-2156.

［9］ 張德富，彭煜，張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2553-2561.

［10］ 劉勝，朱鳳華，呂宜生，等.求解三維裝箱問題的啟發(fā)式正交二叉樹搜索算法［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（8）：1530-1543.

［11］ 靳志宏，蘭輝，郭貝貝.基于現(xiàn)實(shí)約束的集裝箱裝箱優(yōu)化及可視化［J］.系統(tǒng)工程理論與實(shí)踐，2010，30（9）：1722-1728.

［12］ 張瑩，劉二超，戚銘堯.考慮支撐面約束的三維裝箱問題快速求解方法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2014，14（2）：192-198.

［13］ 那日薩，崔雪蓮，韓琪瑋，等.有角件約束的集裝箱裝箱問題優(yōu)化算法［J］.工業(yè)工程與管理，2016，21（1）：1-7.