一種大批量多品種后向反饋容重比平衡貨物配裝法

謝貽文, 廖秀英, 林 劍, 曾祥飛

(1.湖南科技大學資源環(huán)境與安全工程學院， 湘潭 411201； 2.湖南科技大學計算機科學與工程學院， 湘潭 411201)

車輛配裝問題(vehicle fitting problem, VFP)是如何使車輛的裝載效率最高，從而降低物流企業(yè)運輸成本的問題。配裝涉及的貨物要素有幾何尺寸、容重比、防壓性能、成本及配送單價等，由于單一要素的配裝便屬于組合優(yōu)化領域的非確定性多項式(non-deterministic polynomial, NP)難題(NP-hard)，因此，車輛配裝研究主要是圍繞某一種要素展開。在眾多要素中，最為普遍存在、也是研究最為廣泛的兩種要素為幾何尺寸[1-4]和容重比[5]。不同容重比的貨物配裝能充分利用車輛的容積和載重，提高車輛裝載率。

貨物配裝問題是指一批不同類型的貨物如何用最少數量的車輛使貨物盡可能地裝完，貨物配裝是車輛配裝的目的，車輛配裝是貨物配裝的基礎。基于貨物容重比的VFP，按研究目標的側重面不同，可分為車輛配裝和貨物配裝。車輛配裝假設有遠大于車輛裝載量的不同容重比的貨物，其目標是使車輛的容積和載重得到最大限度的利用，即，選擇不同類型的貨物裝車，使所裝貨物的容重比趨向于車輛的容重比；貨物配裝假設有足夠的車輛，其目標是用最少的車輛把貨物盡可能地裝完，要使車輛數最少，就必須考慮充分利用車輛的容積和載重，即，使每臺車所裝貨物的容重比與車輛容重比的差值或比值均衡。

求解基于容重比的VFP的方法可分為精確算法、構造啟發(fā)式算法和元啟發(fā)式算法。精確算法把問題求解作為整數規(guī)劃問題處理，常用的方法有分切算法[6]、分支定界算法[7]等；構造啟發(fā)式算法主要有容重比平衡法、動態(tài)容重比平衡法，容重比平衡法啟發(fā)式規(guī)則有貨物容重比與車輛容重比(隨著貨物的載入車輛容重比動態(tài)調整)差值最小的規(guī)則[8]、通過聚類使待裝貨物單元容重比平衡的規(guī)則[9]、按貨物容重比大小交叉排序的容重比平衡規(guī)則[10]、載入貨物容重比均值與車輛容重比最小的容重比平衡規(guī)則[11]；元啟發(fā)式算法是在構造啟發(fā)式算法的基礎上增加隨機選擇的機制，以避免局部最優(yōu)，主要方法有遺傳算法和螞蟻群算法，在目標函數選擇方面，有采用車輛裝載率最大和車輛容積率最大的雙目標函數的[12-13]，也有二者歸一化的單目標函數的[14-16]；在隨機選擇策略方面，有利用模擬退火方法的遺傳算法[17]，有構造車輛容積比和貨物容積比為參數能見度函數的螞蟻群算法[18]。上述方法適用于小批量多品種零散貨物車輛配裝，對大批量多品種貨物配裝存在以下問題：①配裝單元都是以貨物類型為最小配裝單元，只考慮貨物類型配裝。大批量貨物中，一種貨物類型由多件包裝組成，其總量有時遠大于一輛車的裝載量，除了考慮貨物類型配裝，同時還需考慮貨物數量配裝。在已有的構造啟發(fā)式算法中，沒有設計貨物數量配裝規(guī)則，不能實現貨物數量配裝；元啟發(fā)式算法和精確算法雖無需設計專門的數量配裝規(guī)則，但貨物的數量會使算法的計算時間成指數增長。②均未事先規(guī)劃所需車型及其數量組合。對于車輛配裝不需考慮所有的貨物是否裝完，只需使已知車輛的裝載率最大，所以無需進行車輛規(guī)劃。對于貨物配裝需要盡可能地把所有貨物裝完，在構造啟發(fā)式算法中，車輛與車輛之間容積比平衡規(guī)則的設定與所有待裝貨物的量及容積比有關，要建立該規(guī)則需要先進行車輛規(guī)劃；在元啟發(fā)式算法中，如果未事先進行車輛規(guī)劃，那么在優(yōu)化計算時需要同時進行車輛組合優(yōu)化。如果貨物類型配裝和貨物數量配裝為2重NP-hard，那么，增加車輛組合優(yōu)化則為3重NP-Hard，其優(yōu)化效率進一步降低。

針對大批量多品種貨物配裝需要進行貨物數量配裝的問題，提出一種容重比平衡貨物配裝構造啟發(fā)式算法，首先，根據所有待裝貨物進行所需車輛組合規(guī)劃，然后，構造同時顧及貨物類型配裝及貨物數量配裝啟發(fā)式規(guī)則，并用物流企業(yè)實際配送貨物數據進行方法實驗驗證。

1 問題描述

在選擇大批量多品種貨物作為研究對象時，問題的研究基于以下前提條件。

(1)不考慮貨物的送達時間和路徑問題，以公路運輸為背景，有j類車型可供選擇，從配送中心將待配送貨物用多輛車送往同一個地方。

(2)所有待配送貨物可以相互混裝，不考慮貨物在車內的擺放情況，但需考慮貨物在車內質量、體積以及容重比的約束。

(3)訂單是指一種貨物類型的需求總量，是由相同體積規(guī)格的單元組成，單元單位為件，同種貨物允許載入不同的車輛，即允許拆單。

綜合以上因素，針對多車型、大批量和多品種的貨物配送問題可用數學方式描述為：設配送中心有n種貨物向同一個門店進行配送，貨物總質量為G，總體積為M，總容重比為C，同種貨物對應的件數為{t1,t2,t3,…,tn}，單件貨物對應的體積為{v1,v2,v3,…,vn}，單件貨物對應的質量為{g1,g2,g3,…,gn}，定義Ci=gi/vi為第i種貨物的容重比，所有貨物類型的容重比為{C1,C2,C3,…,Cn}，用于裝載貨物的車型有j類，每種車型對應的數量為{s1,s2,s3,…,sj}，單個車輛對應的載重為{W1,W2,W3,…,Wj}，單個車輛對應的容積為{V1,V2,V3,…,Vj}，定義Rj=Wj/Vj為第j類車型的容重比，所有車輛類型的容重比為{R1,R2,R3,…,Rj}。要求最終實現的目標是：在給定約束條件下，合理規(guī)劃所需車型及其數量的組合，同時顧及貨物類型配裝和貨物數量配裝，使貨車的使用數量最少，載重利用率和容積利用率達到最高。

2 車輛規(guī)劃模型

在貨物配裝之前，需進行車輛規(guī)劃，求解出所需車型及數量的組合。車輛規(guī)劃模型建立的目標函數為

(1)

(2)

(3)

約束條件為

xj≤sj

(4)

(5)

(6)

多車型車輛流程如圖1所示。

圖1 車輛規(guī)劃流程Fig.1 Vehicle planning process

3 后向反饋容重比平衡法

后向反饋法是指根據后續(xù)待裝貨物容重比，確定當前載入貨物的數量。后向反饋容重比平衡法的基本思想是：當貨物滿足容重比平衡約束時，盡可能地避免同種貨物載入不同的車輛，當貨物不滿足容重比平衡約束時，載入不同貨物使容重比平衡，所載入的貨物量由后向反饋法確定。其基本原則是：在貨物配裝的過程中應用“先裝大件再裝小件”的思想，從件數最多的貨物開始，并盡可能將同種貨物裝載在同一輛車上。

3.1 容重比平衡規(guī)則及總體流程

考慮到貨物類型配裝、貨物數量配裝及車輛組合優(yōu)化為3重NP-hard，針對貨物多品種、大批量的特點，構造后向反饋容重比平衡法的容重比平衡規(guī)則為

C≤Ckj≤Rj或Rj≤Ckj≤C

(7)

約束條件為

kj∈{1,2,…,m}

(8)

kj∈{1,2,…,m}

(9)

式中：tikj表示有t件i類的貨物裝載在車型為j的第k輛車上；Ckj為貨物i加入車輛kj后所載貨物的容重比。式(7)表示Ckj應在貨物總容重比C和第j類車型的容重比Rj之間。

算法的求解過程是根據構造的容重比平衡規(guī)則選擇解元素的過程，總體流程如圖2所示。

在算法中，當貨物超載時，先執(zhí)行超載拆單，再判斷拆分后的貨物是否滿足容重比平衡規(guī)則。超載拆單是當貨物質量或體積超過車輛的載重或容積時，拆除超出車輛容量的貨物件數后再進行配載的流程，拆除的貨物件數則生成新單，歸入未配載的貨物中。

圖2 算法總體流程Fig.2 Algorithm overall process

3.2 后向反饋法流程

貨物不滿足容重比平衡規(guī)則時，需采用后向反饋法確定貨物的載入量，搜索滿足容重比規(guī)則的未配載貨物并組合一起裝載，若搜索的未配載貨物小于車輛剩余空間時，需對貨物i配載拆單，重新搜索滿足容重比規(guī)則的未配載貨物，具體過程如圖3所示。

圖3 后向反饋法流程Fig.3 Backward feedback process

圖3中：W′為車輛kj裝載貨物i后的剩余載重；V′為車輛kj裝載貨物i后的剩余容積；g′為滿足式(7)所有未配載貨物的質量；v′為滿足式(7)所有未配載貨物的體積。

在后向反饋法中，配載拆單是當搜索出所有滿足容重比平衡規(guī)則的未配載貨物超出車輛剩余容量時，對已加入車輛貨物i進行折中拆分的流程，具體流程如圖4所示。

圖4 配載拆單流程Fig.4 Loading and splitting process

圖4中，ti為貨物i的件數。當加入車輛貨物i的件數小于2件時，則停止拆單，從車輛組合中選擇下一輛車，進行裝載。

4 實驗分析

4.1 容重比平衡法與其他算法對比分析

實驗在Intel(R) Core(TM) i5-3210 CPU @ 2.5 GHz處理器，8 GB內存，Windows10 64位操作系統(tǒng)下，用C++語言編制后向反饋容重比平衡貨物配裝法的程序。為客觀評價算法的有效性，使研究結果具有對比性，選取文獻[19]中的數據進行實驗，采用TBJ10(W=10 t，V=16.81 m3)型集裝箱配裝，并將解得的最優(yōu)結果與文獻[18]、文獻[19]的實驗最優(yōu)結果進行對比，如表1所示。

表1 3種算法結果比較Table 1 Comparison of 3 algorithm results

由表1可知，本文算法比文獻[18]、文獻[19]的載重利用率分別提高了18.7%、16.09%，容積利用率分別提高了0.95%、8.57%。由此看出，考慮多品種貨物的配裝問題，通過本文所提出的后向反饋容重比平衡貨物配裝法，能充分并均衡利用裝載工具的載重和容積，求解結果更好。

4.2 大批量多品種貨物配裝分析

為驗證本文算法求解大批量多品種貨物配裝問題的可行性，采用商業(yè)物流管理系統(tǒng)提供的實際配送數據進行研究，有432種待配送貨物類型，貨物件數共計56 701件，貨物的總質量為21.15 t，總體積為47.54 m3，配送車輛類型及規(guī)格如表2所示。

商業(yè)物流管理系統(tǒng)提供的432種貨物的實際配送結果如表3所示。表3中展示了部分貨物配裝的信息。

表2 配送車輛的類型及規(guī)格Table 2 Type and specifications of the delivery vehicle

表3 貨物配裝信息Table 3 Cargo fitting information

表3中，A1× 400表示001號貨物由第1輛車型為A的車裝載400件；A1× 131，B2× 61表示002號貨物由第1輛車型為A的車裝載131件和第2輛車型為B的車裝載61件。

表4所示為每輛車的配裝結果統(tǒng)計。結合表3和表4可知，實驗根據貨物的總量，采用車輛規(guī)劃模型，規(guī)劃車輛的車型組合為A1B1B2C1，即一輛A型車，兩輛B型車和一輛C型車。依據容重比平衡規(guī)則及后向反饋法，002號的貨物拆分后由A1車和B2車進行裝載，006號的貨物拆分后由B2車和C1車進行裝載，規(guī)劃的車輛組合共計裝載了56 439件貨物，余下的006號的208件貨物，則滯留在配送中心。一般商業(yè)物流車輛的裝載率為70%～85%，實驗中，車輛組合中的每輛車載重利用率和容積利用率都達到87%以上。

表4 配裝結果Table 4 Result of goods arrangement

綜上所述，由車輛規(guī)劃和后向反饋容重比平衡法確定的配送方案，利用可拆分的配載方式，盡可能裝載更多貨物，使滯留的貨物較少，減少車輛的使用數量，使車輛資源使用更加合理，可以有效解決大批量多品種的貨物配裝問題。

5 結論

針對大批量貨物配裝中貨物類型及數量問題，提出一種大批量多品種后向反饋容重比平衡貨物配裝法。該算法在貨物配裝前進行車輛規(guī)劃，有利于節(jié)約車輛資源，同時顧及貨物類型配裝和貨物數量配裝，構造了容重比平衡規(guī)則，在貨物不滿足容重比平衡規(guī)則時，采用后向反饋法，提高了貨物配裝的求解效率。通過選取類似文獻中的算例進行驗證，與其他2種算法相比，后向反饋容重比平衡貨物配裝法能同時均衡優(yōu)化車輛的載重和容積。最后結合商業(yè)物流實例數據進行研究，從而驗證了算法的實用性和有效性，提高了車輛在容積和載重兩方面的裝載量，節(jié)省運力，能夠為企業(yè)決策提供科學依據，提高配載工作的自動化水平。