單車多品種貨物配裝問(wèn)題的模型與算法研究

摘要：針對(duì)貨車裝載率低下的現(xiàn)狀，建立模型時(shí)考慮貨車的類型、體積、載重、客戶優(yōu)先級(jí)等約束，給出單車多貨配裝問(wèn)題進(jìn)行優(yōu)化的方法和步驟，并結(jié)合理論設(shè)計(jì)算法。

關(guān)鍵詞：配裝；多品種；需求緊急系數(shù)

中圖分類號(hào)：F224文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1002-3100(2007)08-0118-04

Abstract: Aiming at the low efficiency of truck loading， during making the model， the paper mainly considers such factors as model of vehicle， volume， load the urgent coefficient of customers' need and so on and gives the methods and processes to optimizing the loading of multi-category goods and single-vehicle. According to the combination theory， the algorithm is proposed.

Key words: loading; multi-category; urgent coefficient

配裝是指充分利用運(yùn)輸工具的載重量和容積，采用先進(jìn)的裝載方法，合理安排貨物配載的作業(yè)[1]。配送當(dāng)中的“配”和“送”是有機(jī)結(jié)合的形式，配是送的基礎(chǔ)起著決定性的作用。物流中心在選擇運(yùn)輸車輛完成配送業(yè)務(wù)時(shí)，應(yīng)充分考慮車輛的容積和載重量，實(shí)行合理的輕重配裝、容積大小不同的貨物搭配裝車，即按車輛的核定噸位滿載，做到滿載滿裝取得最優(yōu)效果。貨物配裝作為物流企業(yè)配送一個(gè)重要環(huán)節(jié)，是物流企業(yè)節(jié)約運(yùn)送成本的一個(gè)著眼點(diǎn)。合理的配裝有利于物流企業(yè)提高車輛裝載率，減少貨物損壞，減少車輛對(duì)道路的占有率。然而，到目前為止，大部分配送中心在實(shí)際操作中仍然憑借經(jīng)驗(yàn)進(jìn)行配裝。因此，為適應(yīng)配送需求的快速增長(zhǎng)，研究車輛的配裝利用率用以提高配送中心所能獲得的經(jīng)濟(jì)效益及社會(huì)效益是十分必要的。

根據(jù)待裝貨物和車輛的數(shù)目，配裝問(wèn)題可以分為多車單品種貨物配裝、單車多品種貨物配裝和多車多品種配裝等幾種類型。單車多品種貨物配裝指一輛配送車輛對(duì)一個(gè)客戶的多種貨物進(jìn)行組合配裝，使車輛達(dá)到較為滿意的空間和載重利用率。該種配裝方式往往是單個(gè)客戶對(duì)多種貨物有不同需求量，而貨物需求量之和小于單車容積和載重，此時(shí)用一輛車對(duì)多種貨物進(jìn)行配裝后再送給該客戶。

配裝問(wèn)題在學(xué)術(shù)上屬于相當(dāng)復(fù)雜約束條件的組合優(yōu)化問(wèn)題，屬于NP-hard問(wèn)題。國(guó)內(nèi)外許多學(xué)者對(duì)此進(jìn)行了研究，研究的內(nèi)容主要從車輛和貨物兩方面考慮，大致分為四種配裝情形，相同體積貨物與不同體積貨物的配裝、單車型和多車型的配裝。關(guān)注的焦點(diǎn)多為通常將整個(gè)貨物看成一個(gè)整體單純分析是否配送，優(yōu)先考慮體積或者重量方面的約束[2-4]，沒(méi)有提及每種貨物的具體配送數(shù)量，也不考慮顧客對(duì)貨物需求的緊急性。但在實(shí)際配送過(guò)程中，必須對(duì)不同貨物的具體配送數(shù)量進(jìn)行確定，也要考慮顧客對(duì)貨物的需求緊迫性，對(duì)優(yōu)先需求的產(chǎn)品優(yōu)先進(jìn)行配送。本文從配送中心實(shí)際出發(fā)，優(yōu)先考慮顧客需求優(yōu)先級(jí)確定各種貨物的配送數(shù)量，在此基礎(chǔ)上考慮使車輛的載重量和容積得到有效利用。

1配裝前提分析及模型

1.1顧客優(yōu)先級(jí)

由于客戶對(duì)多種貨物可能均有需求，貨物配送的先后順序由配裝優(yōu)先級(jí)來(lái)確定，優(yōu)先級(jí)大的貨物優(yōu)先配裝。貨物優(yōu)先級(jí)的制定與很多因素有關(guān)。這里所謂的顧客需求優(yōu)先系數(shù)即顧客需求緊急性系數(shù)，是指顧客對(duì)貨物需求緊急的大小[5]。一般來(lái)說(shuō)貨物的時(shí)間約束是決定貨物發(fā)送優(yōu)先級(jí)的最重要因素，貨物按照規(guī)定的時(shí)間運(yùn)輸?shù)竭_(dá)目的地，使貨物滿足顧客需要，可以減少時(shí)間延誤帶來(lái)的資金懲罰。貨物的優(yōu)先級(jí)和貨物的屬性也有關(guān)系，重點(diǎn)物資、軍用品、鮮活物資和一般的物資優(yōu)先級(jí)就不相同。另外，貨物的重量、集貨配送、直達(dá)中轉(zhuǎn)等因素也會(huì)影響到貨物的優(yōu)先級(jí)別[6]。

1.2前提條件及參數(shù)設(shè)置

單車多品種貨物配裝可描述為：現(xiàn)有一運(yùn)輸車輛對(duì)N種貨物配裝，在不超過(guò)該車額定載重和最大裝載容積的條件下，各貨物優(yōu)先級(jí)不完全相同，確定裝載貨物的品種和數(shù)量，使貨車滿足貨物優(yōu)先級(jí)的情況下裝載貨物的總價(jià)值最大。

該配裝問(wèn)題的前提條件：

（1）客戶對(duì)每種貨物的需求量確定，每種貨物單位價(jià)值系數(shù)已知；（2）待裝貨物滿足混裝問(wèn)題，不需對(duì)貨物進(jìn)行分類；（3）直送式配送不考慮貨物的裝卸貨順序和方向性因素；（4）單位貨物不可分割裝載，滿足整件裝載；（5）影響該配裝因素的主要是配送車輛的載重、體積和貨物的優(yōu)先級(jí)；（6）每種待運(yùn)貨物的配裝優(yōu)先級(jí)明確。

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

貨車的參數(shù)：額定載重W（噸）、最大裝載容積V（m3）；

4結(jié)論

利用該模型及算法求解單車多品種配裝問(wèn)題簡(jiǎn)單、通俗易懂，只需獲取待送貨物基本數(shù)據(jù)重量、體積、價(jià)值即可運(yùn)用運(yùn)籌學(xué)中的動(dòng)態(tài)規(guī)劃順序解法求出最優(yōu)配裝方案。計(jì)算方便簡(jiǎn)單，節(jié)約配裝時(shí)間進(jìn)而節(jié)省了整個(gè)配送流程的時(shí)間。該模型適用于現(xiàn)階段小型物流企業(yè)或?qū)I(yè)的配送中心，因?yàn)槠湄浽幢容^少、貨物品種單一或少量，其承擔(dān)的業(yè)務(wù)往往是一家或少數(shù)幾家企業(yè)的幾種商品配送。當(dāng)待運(yùn)貨物品種較多、且貨物外型不規(guī)則時(shí)，運(yùn)用該模型往往會(huì)在最后裝貨時(shí)發(fā)現(xiàn)并不能取得先前所預(yù)測(cè)的裝貨效果。另外，隨著貨物數(shù)量的增多，計(jì)算量會(huì)越來(lái)越大。當(dāng)配裝的貨物很多時(shí)，為充分利用運(yùn)輸車輛的容重（容積和載重），要求構(gòu)造有效的啟發(fā)式算法，在使計(jì)算復(fù)雜度迅速降低的同時(shí)，仍然能夠獲得比較滿意的配裝水平。

參考文獻(xiàn)：

[1] 吳清一. 物流管理[M]. 北京：中國(guó)物資出版社，2003.

[2] 劉小群，馬士華，徐天亮. 裝載能力有限下多品種貨物配裝的容重比平衡法[J]. 工業(yè)工程與管理，2004(3):62-66.

[3] 孫焰，李致中. 求雙目標(biāo)配裝的多項(xiàng)式近似算法[J]. 長(zhǎng)沙鐵道學(xué)院學(xué)報(bào)，1997，15(2):33-39.

[4] 高紅建，李韓娟，等. 貨物合理配裝的實(shí)用啟發(fā)式算法[J]. 交通科技與經(jīng)濟(jì)，2004(1):59-61.

[5] 曹明蘭，郎茂祥，等. 考慮客戶需求優(yōu)先級(jí)的貨物配裝問(wèn)題的模型與算法研究[J]. 物流科技，2006(7):69-72.

[6] 陳佳娟，王云鵬，紀(jì)壽文. 運(yùn)輸管理信息系統(tǒng)中車輛配載研究[J]. 公路交通科技，2004(12):137-140.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>