集裝箱裝箱輔助決策系統(tǒng)

王朝霞

(上海海事大學(xué)物流工程學(xué)院，上海 201306)

0 引言

在集裝箱運(yùn)輸業(yè)務(wù)中，集裝箱貨運(yùn)站是物流作業(yè)的重要環(huán)節(jié)之一，主要工作包括備箱、配箱、裝箱等作業(yè)流程.一些小型貿(mào)易公司出口的貨物為小批量，不足以裝滿一個(gè)集裝箱，因此當(dāng)目的地相同的貨物集中到一定數(shù)量時(shí)，貨運(yùn)站將這些貨物拼裝入箱.在拼裝過(guò)程中，如何將一定數(shù)量的貨物裝入最少數(shù)量的集裝箱內(nèi)是貨運(yùn)站工作的最終目標(biāo)，此即集裝箱裝箱問(wèn)題.

傳統(tǒng)的裝箱作業(yè)是由作業(yè)人員根據(jù)工作經(jīng)驗(yàn)，通過(guò)反復(fù)試驗(yàn)來(lái)實(shí)現(xiàn)的，集裝箱空間利用率相對(duì)不理想，造成一定的運(yùn)輸成本.一直以來(lái)，有很多學(xué)者對(duì)裝箱問(wèn)題進(jìn)行研究，但多數(shù)以理論為主，忽略裝箱算法的實(shí)用性.本研究旨在考慮實(shí)際裝箱過(guò)程中的諸多約束，設(shè)計(jì)合乎邏輯的裝箱算法并開發(fā)出集裝箱裝箱系統(tǒng)軟件，為工作人員提供輔助決策，從而提高貨運(yùn)站裝箱效率.

1 集裝箱裝箱問(wèn)題模型的建立

裝箱問(wèn)題是具有復(fù)雜約束條件的組合優(yōu)化問(wèn)題.若忽略約束條件，在理想狀態(tài)下研究裝箱問(wèn)題，會(huì)取得較好的計(jì)算效果，但脫離實(shí)際.因此，在建模過(guò)程中，分析其目標(biāo)和多種約束條件至關(guān)重要.

1.1 模型的目標(biāo)與約束條件分析

裝箱問(wèn)題是“尺寸協(xié)調(diào)”問(wèn)題，涉及到空間利用問(wèn)題.如何提高集裝箱的空間利用率正是裝箱的目標(biāo).

通過(guò)對(duì)集裝箱裝載過(guò)程的分析，總結(jié)出如下幾種常見且必要的約束條件:(1)集裝箱總?cè)莘e約束.(2)集裝箱載重量約束.(3)貨物箱單邊長(zhǎng)度約束.(4)貨物箱空間坐標(biāo)約束.(5)貨物箱擺放方向約束.有些貨物包裝上標(biāo)有向上的箭頭(即只能在水平方向上旋轉(zhuǎn))，本研究中用可旋轉(zhuǎn)度表示其擺放方向的約束.(6)貨物箱承載能力約束.貨物所能承受的最大壓力是有限的，當(dāng)上面貨物重量大于下面貨物的承受能力時(shí)，下面的貨物可能被損壞.本研究中用貨物的重量、貨物堆碼層數(shù)表示貨物承載能力的約束.(7)貨物箱特殊位置約束.有些特殊貨物需要擺放在指定位置，例如需接受海關(guān)查驗(yàn)的貨物需放在集裝箱門邊;或者某些貨物不能混裝.(8)貨物重心約束.貨物裝載結(jié)束后，集裝箱的重心應(yīng)該在限定范圍之內(nèi)，這樣才能保證碼放穩(wěn)定且容易搬運(yùn).

1.2 模型的建立

根據(jù)以上分析，建立裝箱問(wèn)題模型.

式中:P表示同一目的港貨物裝箱后的總運(yùn)費(fèi);m表示可用來(lái)裝貨的集裝箱數(shù)量;k表示集裝箱的種類，k=0表示20英尺箱，k=1表示40英尺箱;tjk表示第j個(gè)集裝箱是否裝入貨物，若裝入則tjk=1，若不裝入則tjk=0;Pk表示不同型號(hào)集裝箱的運(yùn)費(fèi).

式中:Fjk表示第j個(gè)集裝箱的空間利用率;n表示同一目的港所有貨物的數(shù)量;cij表示第i個(gè)貨物是否裝入第j個(gè)集裝箱，若裝入則 cij=1，若不裝入則cij=0;vi表示第i個(gè)貨物的體積;Vjk表示k種集裝箱的容積.

約束條件(3)為裝載貨物的總體積約束;約束條件(4)為裝載貨物的總重量約束.式(4)中:gi表示第i個(gè)貨物的重量;Gjk表示k種集裝箱的承載重量.

約束條件(5)～(7)為貨物在空間坐標(biāo)系中x，y，z坐標(biāo)軸上不超出集裝箱壁的長(zhǎng)度約束，其中:xi，yi，zi表示貨物裝入集裝箱左后下角的坐標(biāo)值;li，wi，hi表示貨物在坐標(biāo)軸上的長(zhǎng)度;Ljk，Wjk，Hjk表示k種集裝箱的長(zhǎng)、寬、高;nj表示裝入第j個(gè)集裝箱的所有貨物的數(shù)量.

約束條件(8)～(10)為重心約束條件，其中:xa，xb，ya，yb，za，zb為重心區(qū)間值.

約束條件(11)為每?jī)蓚€(gè)貨物在空間位置上不出現(xiàn)重疊、交叉現(xiàn)象的約束，其中 qxij，qyij，qzij分別表示每?jī)蓚€(gè)貨物在空間坐標(biāo)系3個(gè)坐標(biāo)軸上不能重疊的因數(shù)，其值可通過(guò)以下表達(dá)式確定:

貨物擺放方向的約束通過(guò)在貨物基礎(chǔ)信息中設(shè)置方向約束參數(shù)實(shí)現(xiàn)，在進(jìn)行貨物預(yù)處理時(shí)根據(jù)該約束參數(shù)確定貨物的初始長(zhǎng)、寬、高;貨物承重能力的約束通過(guò)將貨物的重量信息按降序排列后貨物的可堆碼層數(shù)實(shí)現(xiàn).

2 集裝箱裝箱算法設(shè)計(jì)

裝箱問(wèn)題有以下解法:(1)數(shù)學(xué)規(guī)劃法.用組合最優(yōu)化中廣泛應(yīng)用的線性規(guī)劃法、整數(shù)規(guī)劃法、分支定界法［1-2]和動(dòng)態(tài)規(guī)劃法等進(jìn)行求解.(2)數(shù)值優(yōu)化法.在各種布局算法中，數(shù)值優(yōu)化法［3-4]具有較為成熟的理論和相應(yīng)算法.(3)遺傳算法.通過(guò)模擬生物進(jìn)化的過(guò)程求解復(fù)雜的優(yōu)化問(wèn)題［5-6].(4)模擬退火算法.其來(lái)源于固體退火原理［7]，因其有可能求得布局問(wèn)題的全局最優(yōu)解而受到人們?cè)絹?lái)越多的重視［8-10].(5)啟發(fā)式算法.其基本思想是依靠人的先驗(yàn)知識(shí)確定每一步的排放策略，從而得到目標(biāo)的解.早期國(guó)外一些學(xué)者提出基于貪心策略的近似算法［11]，不少學(xué)者提到物體組合的方法［12-13].目前雖然有一些智能化的裝箱軟件，但并沒有得到廣泛應(yīng)用.綜合起來(lái)，啟發(fā)式算法較適用于實(shí)用軟件，這在集裝箱裝箱問(wèn)題中尤為重要，因此本研究采用啟發(fā)式算法求解模型.

2.1 裝箱問(wèn)題中的規(guī)則

針對(duì)集裝箱單側(cè)開門的封閉型結(jié)構(gòu)，本研究中貨物裝入的空間順序?yàn)?由內(nèi)到外，從左到右，自下往上.這種裝入順序符合集裝箱的結(jié)構(gòu)特點(diǎn)和實(shí)際裝箱業(yè)務(wù)中的操作要求.

(1)貨物放置規(guī)則.本研究要解決的是空間尺寸問(wèn)題，所以必須建立空間坐標(biāo)系.如圖1所示，集裝箱的左后下角作為坐標(biāo)原點(diǎn)，集裝箱的長(zhǎng)、寬、高方向分別作為 x，y，z軸.

圖1 空間坐標(biāo)系

(2)貨物定向規(guī)則.貨物擺放方向約束:不能旋轉(zhuǎn)、水平旋轉(zhuǎn)、任意旋轉(zhuǎn).從貨物擺放方向可以確定貨物在空間坐標(biāo)系中x，y，z方向的長(zhǎng)度.

(3)貨物定位、定序規(guī)則.當(dāng)進(jìn)行貨物填充時(shí)，考慮到貨物裝入順序?qū)λ惴ǖ挠绊懀岢龆ㄎ弧⒍ㄐ蛞?guī)則:占角策略、順?lè)挪呗浴⑵胶獠呗浴⑵戒亙?yōu)先策略.

2.2 裝箱算法總流程

在整個(gè)裝箱過(guò)程中，貨物的相關(guān)信息以及初始空間(集裝箱)的信息已知，算法的實(shí)質(zhì)就是以提高空間利用率為目標(biāo)，對(duì)已知的貨物信息和空間信息進(jìn)行整合計(jì)算，最終得出貨物在空間的具體位置.

2.2.1 區(qū)的劃分規(guī)則

(1)調(diào)用“貨物與空間寬度吻合算法”.若存在滿足條件的貨物，且其高度也吻合，則三邊一一對(duì)應(yīng)放置，否則將貨物的一邊作為寬度，另外兩邊中較長(zhǎng)者作為長(zhǎng)度，較短者作為高度來(lái)放置;若不存在則轉(zhuǎn)規(guī)則(2).

(2)調(diào)用“貨物與空間高度吻合算法”.若存在滿足條件的貨物，且存在等高等長(zhǎng)的貨物，則按照寬度組合最優(yōu)條件放置，否則將貨物的一邊作為高度，另外兩邊中較長(zhǎng)者作為長(zhǎng)度，較短者作為寬度放置;若不存在則轉(zhuǎn)規(guī)則(3).

(3)調(diào)用“貨物與空間長(zhǎng)度吻合算法”.若存在滿足條件的貨物，則按照寬度組合最優(yōu)條件放置貨物，并劃分空間;若不存在則轉(zhuǎn)規(guī)則(4).

(4)選擇最大貨物，按照寬度組合最優(yōu)條件將貨物或組合體放入空間.

2.2.2 等長(zhǎng)組合填充

在裝箱過(guò)程中，空間的劃分是隨著貨物的放入實(shí)時(shí)產(chǎn)生的，這樣可以保證貨物在空間位置上不出現(xiàn)交叉.將等高等長(zhǎng)(等寬)的貨物單獨(dú)放入后，在z軸方向上生成的剩余空間是等高等長(zhǎng)的，可以進(jìn)行結(jié)合.若是每放一個(gè)貨物，即劃分空間，然后再進(jìn)行空間結(jié)合，這樣使得空間劃分與結(jié)合的計(jì)算量很大.將等高等長(zhǎng)(等寬)的貨物組合后，以整體的形式放入空間，再進(jìn)行空間劃分，可以減少頻繁的空間劃分與結(jié)合的過(guò)程.

2.2.3 不等長(zhǎng)組合填充

在進(jìn)行上層空間填充時(shí)，無(wú)須考慮提供完整底面，單純追求最大填充即可.如果放入一個(gè)最大貨物后，剩余空間不能再放入任何貨物，就造成空間浪費(fèi)，而兩個(gè)較小的貨物組合后能實(shí)現(xiàn)較大的填充率，因此在進(jìn)行最上層空間填充時(shí)，需要進(jìn)行不等長(zhǎng)貨物組合填充.對(duì)通過(guò)調(diào)用“貨物與空間高度吻合算法”所找到的滿足高度吻合條件的所有貨物進(jìn)行不等長(zhǎng)組合填充，即以待填充空間的長(zhǎng)度為約束條件，在寬度上進(jìn)行最大填充.

2.3 貨物一維組合算法

在等長(zhǎng)(等寬)組合填充和不等長(zhǎng)組合填充中，要針對(duì)不同待裝貨物序列調(diào)用貨物一維組合算法.

2.3.1 一維組合模型的建立

貨物一維組合的實(shí)質(zhì)是對(duì)貨物的寬度或長(zhǎng)度進(jìn)行最優(yōu)組合，使集裝箱寬度或長(zhǎng)度方向上的剩余尺寸趨近于無(wú)窮小.通過(guò)分析發(fā)現(xiàn)，可將貨物一維組合看作是0-1背包問(wèn)題，模型為

式中:i表示貨物編號(hào);W表示空間寬度;wi表示貨物寬度.n 元向量 X=(x1，x2，…，xi，…，xn)為模型的解集.xi=1表示將第i件貨物放入該空間，xi=0表示第i件貨物不被放入該空間.

2.3.2 動(dòng)態(tài)規(guī)劃求解模型

背包問(wèn)題解法有很多，典型的有:回溯法、貪心算法、動(dòng)態(tài)規(guī)劃方法等.本文采用動(dòng)態(tài)規(guī)劃方法進(jìn)行一維組合.在運(yùn)籌學(xué)領(lǐng)域中，動(dòng)態(tài)規(guī)劃方法是解決背包問(wèn)題的一個(gè)較好方法，將每個(gè)物品放入背包的過(guò)程可以看作一個(gè)新的階段.根據(jù)動(dòng)態(tài)規(guī)劃的算法思想，可以得到如下遞歸方程:

式中:i表示決策第i件貨物是否被放入;W－wi表示裝入第i件貨物后，空間寬度的剩余量;f(i－1，W)表示沒有放入第i件貨物時(shí)的寬度;f(i－1，W－wi)+wi表示裝入第i件貨物后的寬度;f(i，W)表示決策是否放入第i件貨物階段的最優(yōu)解.

2.4 剩余空間的劃分

剩余空間是算法中的一個(gè)重要變量，需要用計(jì)算機(jī)語(yǔ)言實(shí)時(shí)、準(zhǔn)確地描述.本文研究的貨物都是規(guī)則的長(zhǎng)方體，初始剩余空間為集裝箱.當(dāng)放入貨物后，剩余空間不再是規(guī)則的長(zhǎng)方體，而且隨著裝入貨物數(shù)量的增加，剩余空間越來(lái)越不規(guī)則，對(duì)其進(jìn)行定性描述也就越來(lái)越困難，因此本文提出將不規(guī)則的剩余空間拆分成多個(gè)規(guī)則的長(zhǎng)方體，形成一個(gè)由多個(gè)長(zhǎng)方體空間組成的剩余空間序列.這樣，在裝入貨物時(shí)，只需在剩余空間序列中選擇滿足一定條件的長(zhǎng)方體空間進(jìn)行填充即可，既可簡(jiǎn)化剩余空間的描述，又可減小問(wèn)題的規(guī)模，而且能解決貨物在空間位置上重疊的約束.本文提出兩種空間劃分方式:x軸劃分和y軸劃分(其中A，B分別表示兩種空間劃分方法所產(chǎn)生的剩余空間區(qū)域)，見圖2.

圖2 剩余空間劃分俯視圖

2.5 剩余空間的結(jié)合

隨著裝入貨物的增加，產(chǎn)生的小空間塊越來(lái)越多，體積越來(lái)越小，很可能成為廢棄空間.將相鄰的小塊空間結(jié)合起來(lái)，會(huì)生成新的大塊空間，可以裝入大的貨物，減少?gòu)U棄空間數(shù)量，從而提高空間利用率.因此，本文提出剩余空間結(jié)合的概念——將相鄰的剩余空間按一定的規(guī)則結(jié)合，形成尺寸較大的剩余空間塊.結(jié)合之后形成的剩余空間塊的底面積比結(jié)合之前剩余空間的底面積大.在相鄰剩余空間塊的結(jié)合中，實(shí)現(xiàn)等高和不同高度剩余空間的結(jié)合，見圖3～5(其中Si表示不同的剩余空間塊).

圖3 剩余空間等高等長(zhǎng)(等寬)結(jié)合示意圖

圖4 等高不等長(zhǎng)空間結(jié)合示意圖

圖5 不等高空間結(jié)合示意圖

3 集裝箱裝箱系統(tǒng)軟件設(shè)計(jì)與實(shí)現(xiàn)

3.1 系統(tǒng)功能

(1)參數(shù)設(shè)置:輸入貨物信息和容器信息.

(2)環(huán)境設(shè)置:貨物堆棧的最小支撐面積比率、靠箱壁貨物允許擠壓量、是否允許不同貨物混裝在一個(gè)容器內(nèi)等.

(3)計(jì)劃制訂:選擇貨物及數(shù)量，選擇計(jì)劃用容器及計(jì)劃數(shù)量.

(4)裝載計(jì)算:計(jì)算貨物在集裝箱內(nèi)的具體裝載位置及所用集裝箱數(shù)量、輸出結(jié)果清單(包括貨物編號(hào)、貨物名稱、貨物裝載位置等)、輸出3D視圖.

3.2 系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì)

根據(jù)上述功能分析，本裝箱系統(tǒng)由4個(gè)模塊組成:參數(shù)設(shè)置、環(huán)境設(shè)置、計(jì)劃制訂、裝載計(jì)算.系統(tǒng)總體結(jié)構(gòu)見圖6.

圖6 系統(tǒng)總體結(jié)構(gòu)

3.3 系統(tǒng)功能實(shí)現(xiàn)

此裝箱系統(tǒng)包括如下功能:環(huán)境設(shè)置、容器信息管理、貨物信息管理、計(jì)劃制訂、裝載計(jì)算、裝箱明細(xì)、視圖顯示等.其核心為裝載執(zhí)行:在完成貨物信息輸入及計(jì)劃制訂后，只需打開裝載執(zhí)行界面，選中想要進(jìn)行計(jì)算的計(jì)劃計(jì)算，便可得出結(jié)果.裝箱明細(xì)中清楚地說(shuō)明每種貨物在集裝箱內(nèi)的位置，便于叉車人員按順序進(jìn)行裝箱作業(yè);視圖顯示則顯示三維視圖，通過(guò)鍵盤上下鍵查看貨物的裝、卸情況.

3.4 裝箱案例分析

(1)實(shí)例分析一.表1中的數(shù)據(jù)為考慮實(shí)際約束條件的一組數(shù)據(jù)，其中體現(xiàn)質(zhì)量、載質(zhì)量和旋轉(zhuǎn)度的約束條件.此類貨物的特點(diǎn)為少批多量.通過(guò)使用本裝箱軟件，可以較快得出裝箱方案.對(duì)于此類現(xiàn)實(shí)中的數(shù)據(jù)，在數(shù)據(jù)導(dǎo)入系統(tǒng)之后，經(jīng)過(guò)系統(tǒng)計(jì)算，空間利用率達(dá)到91.459 6%，3D視圖見圖7.對(duì)于此實(shí)例，江寶釧等［14]得到88.561 5%的空間利用率.

表1 貨物尺寸及屬性

圖7 裝箱視圖顯示

(2)實(shí)例分析二.表2中的數(shù)據(jù)是文獻(xiàn)［15]中使用的測(cè)試數(shù)據(jù)，30種貨物的尺寸，其中貨物信息包括編號(hào)、最大邊長(zhǎng)、居中邊長(zhǎng)、最小邊長(zhǎng).

表2 貨物尺寸及屬性

該組數(shù)據(jù)并沒有貨物的質(zhì)量、旋轉(zhuǎn)度等實(shí)際約束條件，數(shù)量基本為1.對(duì)于這類多種少量的貨物，姜義東等［15]得到82.8%的空間利用率，G and R算法得到 80%的空間利用率，樊建華等［16]得到80.59%的空間利用率，采用本文算法可得到83.90%的空間利用率，取得較為滿意的結(jié)果.

4 結(jié)束語(yǔ)

通過(guò)對(duì)集裝箱裝箱問(wèn)題的深入研究分析，結(jié)合裝箱實(shí)際操作的具體要求，考慮實(shí)際操作中的約束條件提出裝箱方案，并將該方案運(yùn)用于集裝箱裝箱系統(tǒng)，為工作人員提供輔助性決策，使工作人員可以結(jié)合經(jīng)驗(yàn)進(jìn)行裝箱作業(yè).

在未來(lái)的研究中，可以從以下方面繼續(xù)深入:

(1)貨物箱的尺寸因內(nèi)裝貨物的屬性而大小各一，有些貨物長(zhǎng)度遠(yuǎn)遠(yuǎn)大于寬和高，對(duì)其處理將是日后研究的重點(diǎn)之一;

(2)進(jìn)行裝箱問(wèn)題的反向研究，設(shè)計(jì)出幾種標(biāo)準(zhǔn)紙箱，使裝箱作業(yè)更加標(biāo)準(zhǔn)化;

(3)從提高3D界面的人機(jī)交互性方面著手，讓操作人員可以自行在界面上拖拉貨物箱，對(duì)裝箱方案進(jìn)行修改等.

［1]CHRISTOFIDES N，WHITILOCK C.An algorithm for two-dimensional cutting problems［J].Operations Res，1997，25(1):30-44.

［2]CHEN C S，LEE S M.An analytical model for the container loading problem［J].Eur J Operational Res，1996(88):78-84.

［3]KIM C.A large scale，multiple constraint network system for testability for printed wiring boards［J].Artificial Intelligence in Des，1992:119-137.

［4]MANNCHEN K.Solution methods for two and three-dimensional packing problems［D].Kar Lsruhe，Germany:Kar Lsruhe Univ，1989.

［5]胡瑞，丁香乾，張峰，等.基于混合遺傳算法的多約束集裝箱裝載問(wèn)題研究［J].電子技術(shù)應(yīng)用，2006(2):24-26.

［6]方平，李娟.求解裝箱問(wèn)題的遺傳算法［J].南昌航空工業(yè)學(xué)院學(xué)報(bào)，1998，12(2):21-24.

［7]KIRKPATRICK S.Optimization by simulated annealing［J].Science，1983，220(4598):671-680.

［8]FAINA L.Application of simulated annealing to the cutting stock problem［J].Eur J Operational Res，1999，114(3):542-556.

［9]李素萍.求解裝箱問(wèn)題的一種模擬退火算法［J].襄樊職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2007，6(4):15-16.

［10]ABANO A.A method to improve two-dimensional layout［J].Comput Aided Des，1977，9(1):48-52.

［11]VLIET A V.On the asymptotic worst-case behavior of harmonic fit［J].J Algorithms，1996，20(1):113-136.

［12]PISINGER D.Heuristics for the container loading problem［J].Eur J Operational Res，2002，141(2):382-392.

［13]GEHRING H.A computer-based heuristic for packing pooled shipment containers［J].Eur J Operational Res，1990，44(2):277-288.

［14]江寶釧，熊偉清.一種求解三維集裝箱裝箱問(wèn)題的混合遺傳算法［J].計(jì)算機(jī)工程與應(yīng)用，2007，43(26):200-202.

［15]姜義東，查建中，何大勇.集裝箱裝載矩形貨物的布局研究［J].鐵道學(xué)報(bào)，2002，22(6):13-18.

［16]樊建華，黃有群，劉嘉敏.集裝箱裝入算法的研究［J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2002，24(4):306-308.