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

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

1　問(wèn)題描述

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

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

（1）車(chē)廂及待裝貨物均為長(zhǎng)方體；

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

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

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

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

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

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

1.1　集合

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

1.2　參數(shù)

Li：貨物i的長(zhǎng)度，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：車(chē)廂的長(zhǎng)度；

CW：車(chē)廂的寬度；

CH：車(chē)廂的高度；

CV：車(chē)廂的體積，CV=CL×CW×CH。

1.3　變量

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

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

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

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

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

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

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

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

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ù)

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

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

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

1.5　約束條件

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

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

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

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

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

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

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

由于汽車(chē)零部件三維裝載問(wèn)題較經(jīng)典三維裝箱問(wèn)題在貨物堆疊方面更為復(fù)雜，現(xiàn)存的求解經(jīng)典三維裝箱問(wèn)題的算法很難直接應(yīng)用到汽車(chē)零部件三維裝載問(wèn)題上。因此，本文設(shè)計(jì)了一種基于裝載塊裝入順序的模擬退火算法。首先，將單箱貨物構(gòu)造成為裝載塊（裝載塊不能在高度上堆疊），將三維裝載問(wèn)題降為二維裝載問(wèn)題。然后，利用模擬退火過(guò)程，將各裝載塊裝入車(chē)廂。該算法以裝載塊的裝載順序作為編碼方式，通過(guò)模擬退火過(guò)程隨機(jī)調(diào)整裝載序列以?xún)?yōu)化裝載序列對(duì)應(yīng)的裝載方案，最后輸出算法結(jié)束時(shí)產(chǎn)生的裝載序列對(duì)應(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；貨物與裝載塊的對(duì)應(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生成并輸出裝載方案，即對(duì)任意i∈I，放置位置的x軸坐標(biāo)xi，y軸坐標(biāo)yi，z軸坐標(biāo)zi，是否裝載在車(chē)上αi，是否需要旋轉(zhuǎn)90°信標(biāo)tgoal。

輸出：裝載方案，即對(duì)任意i∈I，放置位置的x軸坐標(biāo)xi；y軸坐標(biāo)yi；z軸坐標(biāo)zi；是否裝載在車(chē)上α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í)刻，車(chē)廂內(nèi)已放入若干裝載塊，還有若干個(gè)裝載塊待放，這稱(chēng)為一個(gè)格局。車(chē)廂內(nèi)尚未放入任何裝載塊時(shí)，稱(chēng)為初始格局。所有裝載塊已放入車(chē)廂，或車(chē)廂外剩余的裝載塊無(wú)法再放入時(shí)，稱(chēng)為終止格局。

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

定義3（可裝載度）：可裝載度表示待裝載塊與可裝載點(diǎn)的匹配程度，用于指導(dǎo)每個(gè)裝載動(dòng)作中可裝載點(diǎn)的選擇對(duì)任意裝載塊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)。表示放入車(chē)廂后新生成的可裝載點(diǎn)數(shù)量，NE∈｛0，1，2｝，NE越小，表示箱子與當(dāng)前空間的緊密度越高，因此，定義：

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

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

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

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

裝載方案生成子算法

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

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

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

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

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

Step 4：iB=iB+1。

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

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

采用隨機(jī)置換的方式對(duì)裝載序列進(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è)置評(píng)價(jià)函數(shù)為裝載率F，若ΔF=F′-F≥0，則接受新的裝載序列，若ΔF＜0，則采用Metropolis準(zhǔn)則，生成一個(gè)（0，1）之間的隨機(jī)數(shù)θ，若θ小于接受概率exp（10*ΔF／t），則同樣接受新的裝載序列，否則保留當(dāng)前裝載序列。

3　算例分析

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

3.1　單箱裝載

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

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

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

（2）算例結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

圖4　裝載率對(duì)比

圖5　車(chē)輛使用數(shù)對(duì)比

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

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

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

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

4　總結(jié)

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

參考文獻(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］ 何明珂，張屹然.國(guó)內(nèi)汽車(chē)零件入廠物流研究綜述［J］.中國(guó)流通經(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問(wèn)題的高效算法［J］.軟件學(xué)報(bào)，2012，34（5）：1037-1044.

［5］ 何琨，黃文奇.基于動(dòng)作空間的三維裝箱問(wèn)題的確定性高效率求解算法［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］ 張德富，彭煜，朱文興，等.求解三維裝箱問(wèn)題的混合模擬退火算法［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（11）：2147-2156.

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

［10］ 劉勝，朱鳳華，呂宜生，等.求解三維裝箱問(wèn)題的啟發(fā)式正交二叉樹(shù)搜索算法［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］ 張瑩，劉二超，戚銘堯.考慮支撐面約束的三維裝箱問(wèn)題快速求解方法［J］.交通運(yùn)輸系統(tǒng)工程與信息，2014，14（2）：192-198.

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