□ 唐 穎,高倩蕓,張文婷,陳曉健,陳 偉

(上海煙草集團有限責任公司上海煙草儲運公司，上海 200439)

1 引言

隨著物流設(shè)施和設(shè)備的革新，信息技術(shù)在物流中的廣泛應(yīng)用，煙草行業(yè)需要通過物流策略來提高工作效率，降低企業(yè)經(jīng)營成本，優(yōu)化核心業(yè)務(wù)流程，提升企業(yè)市場競爭力。從煙葉制成到卷煙，再從卷煙倉庫銷售到終端，其物流環(huán)節(jié)之多、控制之嚴是煙草行業(yè)物流的特點。國家專賣的管控、原料產(chǎn)地的限制使得煙草行業(yè)的物流研究具有獨特的研究意義。車輛的配載和裝車是物流的重要環(huán)節(jié)，直接影響物流成本，而上海煙草集團產(chǎn)銷規(guī)模的擴大，客戶對卷煙的需求朝著多樣化、小批量、多頻次和個性化方向發(fā)展，同時煙草物流業(yè)務(wù)的運營體量和復雜程度與日俱增，如何依據(jù)全國各地客戶點訂單情況，并結(jié)合物流線路、運輸工具、貨物(煙件)規(guī)格等若干因素，進行快速、有效的車輛配載及貨物裝車成了上煙物流業(yè)務(wù)中一個迫切需要解決的問題。

目前，上海煙草集團有限責任公司上海煙草儲運公司(以下簡稱“儲運公司”)的卷煙裝車業(yè)務(wù)在單車配載優(yōu)化環(huán)節(jié)，長期以來都是憑經(jīng)驗來給運輸工具進行配載的，是否已經(jīng)達到運輸工具使用率的最大化、配載效益的最大化卻無從評估，同時這種配載方式強烈依賴員工的個人能力和經(jīng)驗，不利于大規(guī)模推廣。此外，在利用裝卸工人的經(jīng)驗進行裝車操作時，只考慮車輛空間利用率及載重利用率，不僅無法保障車輛行駛路程，還導致了人力、物力和財力等方面成本的增加。

綜上，有必要對煙草物流的智慧配載與裝車方法進行深入研究，根據(jù)實際業(yè)務(wù)需求，提出一種適用于煙草行業(yè)的配載與裝車優(yōu)化解決方案，從而提高車輛滿載率和裝車一次成功率。

國內(nèi)對貨運配載的相關(guān)研究大致分為兩個方向，一個是考慮車輛數(shù)目的多少與載重、容積及往返距離的約束等建模的方法，模型的運算與設(shè)計以啟發(fā)式算法為主，例如：FFF(Finite First-fit)、FBS(Finite Best-fit)、基于禁忌搜索的元啟發(fā)式算法、自適應(yīng)遺傳算法等；另一個則是對傳統(tǒng)貨運配載路徑的研究，主要是解決一維裝箱問題，結(jié)合遺傳算法的混合啟發(fā)式算法的二維裝箱問題，采用遺傳算法解決不同包裝類型的三維裝箱問題等。關(guān)于煙草行業(yè)的研究大多集中在物流成本控制和配送路徑優(yōu)化方面，而針對煙草智慧配載與裝車方法的相關(guān)研究較少。

2 問題描述與模型構(gòu)建

卷煙的配載與裝車實際上是一個三維裝箱問題。三維裝箱問題(Three-dimensional Bin Packing Problem,3D-BPP)即物體在三維空間的擺放優(yōu)化問題，可以描述為具有長、寬、高的n個物體在一個車箱中擺放，在滿足一定的約束條件下，使裝箱利用率最高。通過模型來刻畫裝箱問題，解決 “如何用車”和“怎么裝車”的優(yōu)化問題，有效提高煙草運力、節(jié)約配載和裝車時間、降低物流成本。

本研究通過對實際業(yè)務(wù)需求的調(diào)研，例如：統(tǒng)計花式煙種類、件煙規(guī)格及包裝尺寸、車廂尺寸等基本數(shù)據(jù)以及訂單物流信息等，準確界定研究問題，充分考慮各種煙草配載裝車場景，建立符合實際業(yè)務(wù)需求的配載運輸模型。確定優(yōu)化目標與約束條件，建立車貨匹配及裝車運輸模型。

2.1 模型假設(shè)

多尺寸貨物(煙草)的運輸車輛裝箱優(yōu)化問題是將待裝貨物為不同種規(guī)格的若干個矩形物體，按照一定的規(guī)律裝入運輸車廂中，使得車箱利用率最大。要求滿足以下假設(shè)：

①所有車廂和貨品形狀為大小不同的長方體；

②所有貨品質(zhì)量分布均勻；

③所有貨品的外包裝具有足夠的承重能力，不會由于堆積而變形；

④每個訂單包括多種貨品，訂單信息包括貨品種類、需求數(shù)量；

⑤每個訂單不可拆分裝車。

2.2 參數(shù)和變量

假設(shè)煙草裝載配送中心有N輛不同型號的箱式貨車，每輛貨車的最大容積為V。貨車車廂可抽象成一個長L、寬W、高H的三維長方體?？蛻鬷需要多種類貨物p，設(shè)每個貨物j的長寬高為(lj,wj,hj)。不妨設(shè)車廂和貨物的長、寬、高在整數(shù)范圍內(nèi)取值。主要參數(shù)和變量定義如表1和表2所示。

2.3 目標函數(shù)及約束性條件

(1)

(2)

ujn=ukn,?j,k∈Oip,?n∈N,i∈I,p∈P

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

模型解釋如下：目標函數(shù)(1)是裝箱率最大即累加所有裝到車箱里的貨品的體積最大；約束(2)表示每個貨品只能被裝到一輛貨車中；約束(3)限制訂單中每個種類的貨品需求只能由一輛貨車完成，即訂單中同一種類的貨品不能被拆分運輸；約束(4)確保每輛貨車的每個車廂裝載的所有貨品的體積不超過該車廂的容量限制；約束(5)-(7)確保裝入車廂的貨品不能違反該車廂的長、寬、高限制；約束(8)-(10)表示貨品的前左下角頂點與后右上角頂點之間的坐標關(guān)系；約束(11)-(14)確保同一車廂中的兩個貨品至少存在一種位置關(guān)系(左右、前后、上下)；約束(15)-(17)確保同一個車廂中的任意兩個貨品不重疊；約束(18)-(19)限制決策變量的取值范圍。

3 啟發(fā)式算法設(shè)計

圖1 不同貨物的裝箱示意圖

多種不同尺寸的物品裝箱問題是個NP-Hard 問題，通常采用啟發(fā)式算法進行求解。本文根據(jù)煙草公司裝箱的特殊需求和笛卡爾坐標的特點設(shè)計一種啟發(fā)式求解算法，啟發(fā)式算法遵循了貨物一定是存在上下、前后、左右中的一種關(guān)系且貨物不允許空放?；舅悸啡缦拢孩俑鶕?jù)煙草訂單的目的地，設(shè)計每輛車的裝箱方案；②確保訂單不拆分的情況下所有種類的貨物裝箱并滿足所有裝箱約束；③訂單里的所有貨物都裝箱完成后，判斷裝箱率，一般原則大于90%，則產(chǎn)生最優(yōu)裝箱方案，否則，重新安排裝箱，如此循環(huán)。

算法1 啟發(fā)式三維裝箱步驟1從貨物集合B和放置點集合items中取出需要的數(shù)據(jù)。步驟2 針對每一個貨物,進行以下步驟:2.1 根據(jù)取出的貨物bi(i∈1,…,n)的規(guī)格以及放置點的位置判斷其在方向1的情況下能否裝入車內(nèi)。2.1.1若可以裝入,則判斷貨物bi與其他貨物是否發(fā)生重疊,2.1.1.1若發(fā)生重疊但是因為行間長度不一致導致的重疊則會根據(jù)行間約束規(guī)則生成新的放置點并存入集合,否則不對該放置點進行放置。2.1.1.2若沒有發(fā)生重疊則判斷貨物bi是否懸空。2.1.2若不懸空并且bi的長度小于其底部貨物的長度則在此放置點進行放置并生成新的放置點,再去除下一個放置點和貨物,判斷貨物集合是否裝完。否則按照相應(yīng)的約束規(guī)則進行放置。2.2若方向1無法放置貨物則判斷方向2是否可以裝入,若可以則判斷相關(guān)的約束條件是否成立執(zhí)行操作,否則判斷方向3是否可以裝入。步驟3 若三個方向都無法裝入貨物則該放置點不進行貨物放置,取出下一個放置點。步驟4 當貨物集合全部裝完返回貨物在車廂內(nèi)的坐標和貨物種類并存入output中。步驟5 配載驗證系統(tǒng)根據(jù)output來繪制所需的裝車圖。

圖2 算法流程圖

4 數(shù)值實驗與實證分析

本文采用上煙公司裝箱的實際數(shù)值來驗證模型。采用運行系統(tǒng)為Windows 10 X64，處理器為Intel(R) Core(TM) i7-10510U CPU@1.80GHz，內(nèi)存為2.30 GHz。在運行環(huán)境中默認參數(shù)設(shè)置下，采用python 語言實現(xiàn)三維裝箱問題的啟發(fā)式算法。

4.1 參數(shù)設(shè)置

在實例中，運輸車隊選擇經(jīng)常使用的兩款車型，貨車車廂的規(guī)格數(shù)據(jù)如表3所示。根據(jù)訂貨的實際情況選取相關(guān)貨品規(guī)格，如表4所示。

表3 車輛規(guī)格

表4 裝載貨物的基本信息

4.2 結(jié)果分析

算法以凈裝箱率為評價指標，實驗結(jié)果如表5所示。

數(shù)據(jù)結(jié)果顯示，每輛車根據(jù)訂單的量進行組合，盡量滿足90%以上的裝箱率，如果要提高裝箱率，可以對某些訂單進行拆分處理。根據(jù)訂單的要求，如果同一訂單的貨物不允許多個車廂運輸?shù)脑挘瑫霈F(xiàn)降低裝箱率的問題。因此，如果貨物較多，可以選擇車隊的方式進行煙草貨品運輸。

車廂內(nèi)可以放置的方式不一定按照訂單的順序，可以根據(jù)貨物的尺寸決定哪單貨物最先放置，前提是該車的貨物卸貨沒有先后順序。這與上煙的實際情況一致，一般同一輛車或者一個車隊會去相同的目的地同時卸貨。由于每類貨物的需求量不同，不一定總能碼垛成一個立方體，有些地方可能會空幾箱貨物。如果全碼齊，則裝箱率最高。如果訂單可以拆分的話，不一定一個訂單必須裝在一輛車里，則可以全部碼垛成立方體，提高裝箱率。

現(xiàn)有的數(shù)據(jù)模擬結(jié)果顯示，12.5米半掛巴士車至少可以容納1050-1110箱貨物，從而保證較高的裝箱率。

5 結(jié)論

本文研究訂單不拆分的多尺寸煙草三維裝箱問題，充分考慮了多種類多貨品的混裝特點，構(gòu)建了混合整數(shù)線性規(guī)劃模型。同時提出了一種啟發(fā)式算法，該算法考慮了多種實際約束，可以用最簡單的方法，在最短的時間內(nèi)得出近似最優(yōu)解。實驗結(jié)果表明，算法優(yōu)化效果顯著。

本文基于多尺寸煙草貨品的裝箱問題展開研究，未來可進一步結(jié)合運輸路徑及配送順序等研究車輛路徑問題。結(jié)合訂單客戶點的順序，進一步深化研究考慮煙草在車場三維裝箱的裝箱順序。

表5 車廂長寬高為11800*2300*2450的實驗結(jié)果