面向準(zhǔn)時生產(chǎn)的第三方物流貨物配裝優(yōu)化

分析人：杜彥煒 吳 照

面向準(zhǔn)時生產(chǎn)的第三方物流貨物配裝優(yōu)化

分析人：杜彥煒 吳 照

為了適應(yīng)制造企業(yè)準(zhǔn)時化生產(chǎn)方式，第三方物流企業(yè)在配送貨物時，要及時響應(yīng)訂單，提高供貨頻次，準(zhǔn)時為生產(chǎn)供貨。本文應(yīng)用容重比啟發(fā)式算法進行配裝優(yōu)化實施，綜合考慮車廂容積、載重量約束條件來確定所裝貨物的種類和數(shù)量。實例證明，應(yīng)用該算法使車廂的容積和載重量均能得到很好的利用。

隨著客戶個性化需求不斷增加和所要求交貨期的縮短，制造企業(yè)傳統(tǒng)的批量生產(chǎn)方式已經(jīng)不能適應(yīng)多品種變批量的生產(chǎn)訂單。而基本思想為“在所需要的時刻，按所需要的數(shù)量生產(chǎn)所需要的配件”的準(zhǔn)時化生產(chǎn)方式成為制造企業(yè)盛行的生產(chǎn)模式。為了適應(yīng)制造企業(yè)準(zhǔn)時化生產(chǎn)方式，第三方物流企業(yè)在配送貨物時，要對訂單進行快速識別和分類，充分利用車輛的載重量和容積，合理安排貨物裝載作業(yè)，短時間內(nèi)制定出與客戶要求相適應(yīng)的配裝方案。本文針對單車多品種貨物配裝優(yōu)化問題，采用容重比啟發(fā)式算法確定所裝貨物的種類和數(shù)量，從而克服了以往依靠經(jīng)驗制定配裝方案的缺點。

多品種貨物配裝問題

多品種貨物配載優(yōu)化是指給定了一批待裝長方體貨箱和長方體容器，按一定的要求將待裝貨物互不干涉地擺放在這一容器內(nèi)，使某一項或幾項性能達到最優(yōu)。該問題的優(yōu)化可歸結(jié)為一類離散組合優(yōu)化問題。如何制定出一個合理的裝載方案，以在保證裝運的順序、重量限制、裝箱效率等條件約束下，使該容器的空間利用率最大，是這類問題的主要目標(biāo)。對多種物資配載優(yōu)化問題的研究方法有啟發(fā)式算法、智能搜索方法（如模擬退火算法、禁忌搜索算法、螞蟻算法、遺傳算法）、窮舉法、動態(tài)規(guī)劃法以及圖論法等。智能搜索方法比較適合于解大規(guī)模組合優(yōu)化問題。啟發(fā)式算法在目前處理多種物資配裝問題時被廣泛應(yīng)用，它憑借有效的優(yōu)化策略來減小搜索空間的規(guī)模，從而縮小搜索范圍，盡可能在很短的時間內(nèi)找出問題的最優(yōu)解，具有很強的實用價值。

配裝優(yōu)化模型

將單車多品種貨物配裝描述為：某車輛對N種貨物配裝，最大程度利用單輛貨車的容積及載重量，確定所裝貨物的品種和數(shù)量，在盡可能滿載的條件下獲得最大經(jīng)濟收益。

有n個具有不同尺寸和重量的貨物，1個容積為V、載重量為W的運輸車，要求利用車輛的容積及載重量。

前提條件：

（1）每件貨物的體積和重量比車廂的容、載重量小；

（2）貨物為直送即送往同一地方；

（3）假設(shè)所有貨物都不相同（實際情況同種貨物可歸為一種）；

優(yōu)化模型為：

約束條件：

式中xi?｛0，1｝，xi=0時表示不裝貨物，xi=l時表示裝入貨物i ，wi代表貨箱i的重量，vi代表貨箱i 的體積；λ?（0，l），λ=l時，目標(biāo)為載重量最大，λ+μ=l； μ=1時，目標(biāo)為容積利用率最大。

若求得的最優(yōu)解形式為（l，0，1，0，l，l，0，0），則表示所要裝載的貨箱編號為l，3，5，6，其余不裝在本車上。

容重比啟發(fā)式算法求解

算法思想

容重比算法是指如果已裝載的貨箱的容重比與車廂的容重比接近時，則已裝載貨箱的重量與車廂的載重量接近，已裝載貨物的體積和車廂的容積接近，說明充分地利用了車廂的載重及容積。

設(shè)某貨箱的重量為W，貨箱的體積為V，稱VW為該貨箱的容重比。

設(shè)貨箱集合為N=（1，2，3…n），貨箱對應(yīng)的重量集合G=（w1，w2，w3…wn） ，貨物對應(yīng)的體積集合V =（v1，v2，v3…vn），ci=viwi為第i個貨物的容重比，所有貨物的容重比集合為R=（c1，c2，c3…cn），S0=V/W為車廂的容重比。

實例

某第三方物流企業(yè)接到某機床制造車間一項準(zhǔn)時物流配送任務(wù)，訂單中包含下列14種配件，分別采用矩形貨箱包裝，重量和體積信息如表1所示，貨箱尺寸分別為：A配件（520×900×1130），B配件（8 0 0×8 0 0×1 7 7 0），C配件（923×871×885），D配件（1000×1000×1000），E配件（812×820×815），F(xiàn)配件（1312 ×932×1175），G配件（1107×869×1254），H配件（632×420×571），I配件（1320×583×720），J配件（1207×190×1096），K配件（512×512×1.54），L配件（870×420×837），M配件（1410 ×832×875），N配件（912×733×1321）。輕卡貨車的載重量為300kg，車廂（2818×1394×1806）/㎜，容積為7m3，要求制定出合理的配裝結(jié)果。

表1　訂單中各配件貨箱重量和體積

算法求解：

（1）第i 種貨物的容重比：ci=viwi得到14種貨箱的容重比分別為：

（2）依據(jù)貨物體積為優(yōu)先級判斷條件，體積越大，優(yōu)先級越高，經(jīng)過優(yōu)先級排序得到集合

對應(yīng)新的重量集合

新的體積集合

（3）規(guī)定貨物B為必須要裝入的貨物，此時R0=3， T=（6，7，2），Rj+1〈3，得到， N=T ∪N1；

（4）N1中的待裝貨物容重比ci=viwi貨物集合N1中貨物的容重比ci=viwi為第i個貨物的容重比。

得到剩余貨物的容重比集合并按遞增順序排列C1=（cj，cj+1…cj+n）按增序排序的到集合

（5）則已裝貨物的容重比為：

（6）由于S1＞S0，則從待裝貨物中選取第一個滿足下列條件的貨物：得到

（8）由（7）得已裝貨物的容重比：

（9）滿足第六步的xi不存在，尋找?guī)аb貨物中可以得到只有x8滿足條件，此時已裝貨物的體積和重量分別為：

（10）因此求得剩余空間和重量為：V剩=V-V1=7-5.62=1.38。W剩=W-W1=300-293.5=6.5；

（11）現(xiàn)在空間已經(jīng)無法再裝入其他貨物。則優(yōu)化后的要裝載的貨箱見表2

表2　配裝優(yōu)化結(jié)果

由表2可計算出裝載貨物的總體積為5.62m3，裝載貨物的總重量為293.5kg，載重利用率為98.57％，體積利用率為80.81％。

小結(jié)

容重比啟發(fā)式算法適用于第三方物流企業(yè)提供的準(zhǔn)時化物流配送，能夠方便快速獲得比較滿意的配裝效果，提高了車輛的空間利用率，降低了企業(yè)的配送成本，節(jié)省了整個配送流程的時間，保證了及時供貨，提高了客戶的滿意度，增強了企業(yè)的競爭力。

10.3969/j.issn.1001-8972.2015.09.041