分析人：杜彥煒 吳 照

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

分析人：杜彥煒 吳 照

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

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

多品種貨物配裝問題

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

配裝優(yōu)化模型

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

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

前提條件：

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

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

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

優(yōu)化模型為：

約束條件：

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

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

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

算法思想

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

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

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

實(shí)例

某第三方物流企業(yè)接到某機(jī)床制造車間一項(xiàng)準(zhǔn)時(shí)物流配送任務(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)先級(jí)判斷條件，體積越大，優(yōu)先級(jí)越高，經(jīng)過優(yōu)先級(jí)排序得到集合

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

新的體積集合

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

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

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

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

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

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

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

（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可計(jì)算出裝載貨物的總體積為5.62m3，裝載貨物的總重量為293.5kg，載重利用率為98.57％，體積利用率為80.81％。

小結(jié)

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

10.3969/j.issn.1001-8972.2015.09.041