多目標規(guī)劃模型在城市零擔(dān)配裝成本優(yōu)化管理中的應(yīng)用

鐘　蘋，龍桂先

(1.南寧職業(yè)技術(shù)學(xué)院，廣西　南寧　530008；2.廣西財經(jīng)學(xué)院，廣西　南寧　530003)

多目標規(guī)劃模型在城市零擔(dān)配裝成本優(yōu)化管理中的應(yīng)用

鐘蘋1，龍桂先2

(1.南寧職業(yè)技術(shù)學(xué)院，廣西南寧530008；2.廣西財經(jīng)學(xué)院，廣西南寧530003)

南寧職業(yè)技術(shù)學(xué)院2014年度科研立項項目“南寧專線物流聯(lián)盟標準化體系研究”(編號：2014YB12)

摘要：文章以車輛標記最大載重、最大載貨容積限制以及貨物不可分裝作為約束條件，建立研究“城市貨的”貨運中轉(zhuǎn)配載的多目標規(guī)劃模型，并以廣西宅配通有限公司為例進行了模型應(yīng)用分析。結(jié)果表明，該方法簡單可行，給公路零擔(dān)貨運企業(yè)提供了理論參考，對于解決現(xiàn)實問題中的中轉(zhuǎn)裝車問題具有重要的價值和現(xiàn)實意義。

關(guān)鍵詞：運輸經(jīng)濟；成本優(yōu)化；多目標規(guī)劃；零擔(dān)貨運；配裝優(yōu)先級

0引言

“城市貨的”是城市運營日常生活工作中物流配送小型搬運的一種貨物運輸車輛、或貨運出租車的簡稱。在公路運輸中，居于城市區(qū)域范圍內(nèi)的城市貨的——“宅配通”這一新興業(yè)務(wù)在傳統(tǒng)的公路零擔(dān)貨運上，管理和服務(wù)有所創(chuàng)新，但是在資源的消耗量上依舊居高不下，如何快速高效的對各種貨物進行配裝，降低資源的使用量，就成了城市貨的當(dāng)前亟待解決的一個問題。

本文以廣西城市貨的樣板——廣西宅配通有限公司為例，提出采用多目標規(guī)劃模型的方法對當(dāng)?shù)爻鞘胸浀呢涍\運營進行分析，為當(dāng)?shù)爻鞘信渌蜆I(yè)務(wù)降低運輸配送成本提出優(yōu)化方案。

1廣西宅配通零擔(dān)貨運現(xiàn)狀問題及分析

1.1　貨源組織力度不足

廣西宅配通有限公司的配送范圍主要是以高新區(qū)科園大道的規(guī)劃總部為出發(fā)點的內(nèi)環(huán)以內(nèi)的青秀區(qū)、西鄉(xiāng)塘區(qū)、興寧區(qū)和江南區(qū)，配送范圍有限，攬貨量也相對有限，每天出庫的快件量大概為3 000件，每月的出庫量約有10萬件。由于區(qū)域覆蓋面低，導(dǎo)致花費大部分的時間在貨物的組織過程中，貨車運營效率低，運輸組織程度低。

1.2　配載的計劃性差，配送效率低

宅配通零擔(dān)貨物運輸信息不暢，從攬貨到高新區(qū)總部入庫貨品信息以手工錄入為主，所有待配送貨物在進入倉庫后，不能及時根據(jù)貨物的信息對貨物進行編排和預(yù)處理，因此在車輛的選擇和貨物的配裝上，難以達到預(yù)期的目標，車輛的容積利用率<70%。

在出庫時，僅僅滿足“先進先出，后進后出”，在車輛的選擇以及貨物的配載上，無法立刻做出響應(yīng)，完成積載計劃，再加上宅配通沒有采用貨物追蹤系統(tǒng)以及先進的通訊技術(shù)裝備，無法實現(xiàn)“貨物交接清楚之后能在3 h之內(nèi)將貨物安全送達客戶手上”的要求。

此外，宅配通的兩種車型都是中小型的普通貨車，針對特殊貨物時只能另外選擇車輛或者租賃車輛，配送效率低且成本高。

1.3　經(jīng)營業(yè)務(wù)單一

宅配通目前只停留在為商家和企業(yè)提供城市貨配送的階段，且對象非常固定，還不具備為客戶提供全面的物流網(wǎng)絡(luò)設(shè)計的能力，一旦這些商家或者企業(yè)尋找到更加優(yōu)質(zhì)的合作對象，而企業(yè)一時又難以滿足大眾客戶的貨物配送需求，企業(yè)將面臨前所未有的運營困境。

2多目標規(guī)劃模型的建立

考慮到企業(yè)的實際情況，單一目標規(guī)劃模型不能夠針對性地解決以上三個問題，因此本文考慮建立多目標規(guī)劃模型，設(shè)置目標函數(shù)：(1)配載貨物的優(yōu)先級最大化。優(yōu)先配載加急貨物，在限時內(nèi)送達客戶。(2)車輛有效載重利用率和總體積利用率最大化。對貨物進行預(yù)處理，充分利用車輛的運載空間，在盡可能提高每一配送車輛滿載率的基礎(chǔ)上降低車輛的平均使用頻率，減少車輛的油耗和車輛的損耗，降低企業(yè)的物流運輸成本。(3)相對于運達期限的運送富裕時間的數(shù)學(xué)期望值最小。通過已知的運到期限和已在途時間，計算出貨物的運送富余時間，按照富余時間，在配載時對貨物進行調(diào)整，做到貨物在交接清楚之后的3 h之內(nèi)將能夠安全地送至客戶手上，減少客戶投訴，體現(xiàn)客戶需求至上。

通過主要目標法，將函數(shù)的主要目標，實現(xiàn)車輛的滿載率作為唯一目標，將次要目標轉(zhuǎn)化為約束條件，實現(xiàn)多目標規(guī)劃模型向單目標規(guī)劃模型的轉(zhuǎn)變，從而簡化計算，提高計算效率，并通過隨機解的產(chǎn)生規(guī)則得到單目標規(guī)劃問題的有效解，即可作為多目標規(guī)劃模型的最優(yōu)解。具體解法如下：

2.1　參數(shù)定義

定義如下符號：n為待配裝貨物的總數(shù)量，中轉(zhuǎn)站待配送貨物集i={1，2，…，n}，其對應(yīng)的各批貨物的重量和體積分別為Wn={w1，w2，…wn}和Vn={v1，v2，…vn}，m為零擔(dān)貨物作業(yè)車的總數(shù)量，車輛j(j=1，2，…m)剩余載重量和載貨容積分別為Wm={w1，w2，…wm}和Vm={v1，v2，…vm}，Wj表示車輛標記的最大載重量，Vj表示車輛最大載貨容積，Ti為貨物已知在途時間(包涵前程運輸時間和落地入庫保管時間)，Tei為中轉(zhuǎn)裝車之后的后程運輸時間(以零擔(dān)貨物出庫配裝的時間點為計算節(jié)點)。

定義xij為0-1決策變量，且

定義α為貨物裝載情況的判斷決策變量，且

αi=∑mj=1xij，即ai的實際含義為

2.2　目標函數(shù)

第一個目標函數(shù)：受車輛類型的限制，配裝問題所要考慮的兩個必要因素是使得車輛裝載貨物的總重量和總體積達到最大，分別表示為：

maxZw=∑mj=1∑ni=1wixij

(1)

maxZv=∑mj=1∑ni=1vixij

(2)

在沒有特別要求重量或體積目標時，可用“載貨的平均容重盡量接近車輛的容重”來替代(1)和(2)兩個目標，即：

(3)

式中：r′j——j輛車載貨的平均容重；

rj——表示第j輛車的容重。

第二個目標函數(shù)：在滿足貨物的數(shù)量最大化要求的基礎(chǔ)上，確保重點物資，急需物資及核心貨物優(yōu)先配裝。因此，待裝貨物賦予優(yōu)先級pi=(pi≥0,i=1，2，…，n)，其中，pi值越大，則裝車順序越靠前，pi值越小，則裝車順序越靠后，那么，配裝貨物的優(yōu)先級最大化可以表示為：

f2=maxZp=∑ni=1pixij

(4)

第3個目標函數(shù)：相對于運達期限的運送剩余時間(Di-Ti-Tei)要最小。即：

(5)

(6)

2.3　約束條件

約束條件是指在公路零擔(dān)貨運場站車輛配裝過程中已知的并必須遵守的前提條件。在這里，貨運中轉(zhuǎn)裝車配送問題的約束條件有3個：

約束條件1：貨車核定載重限制，即任何一輛車中轉(zhuǎn)配載的貨物的重量不得超過車輛出廠規(guī)定的標定值。

∑ni=1wi·xij≤Wj，j=1，2，…，m

(7)

約束條件2：貨車載貨容積限制，即配載的貨物總體積不得超過托運車輛的最大載貨容積。

∑ni=1vixij≤Vj，j=1，2，…，m

(8)

在實際中轉(zhuǎn)裝車配送問題中，上述兩個約束條件所對應(yīng)的解空間RC是寬松的，會產(chǎn)生許多滿足條件的劣質(zhì)解，因此，為了過濾掉劣質(zhì)解，加入以下兩個約束條件。

(1)載重量使用約束。任意一輛車配載貨物達到一定數(shù)量時，其剩余載重量都無法再裝載任意一批尚未被配裝的貨物，即：

?αi=0均有wi>Wj-∑ni=1wixij

(9)

(2)車輛容積使用約束。任意一輛車配載貨物達到一定數(shù)量時，其剩余載貨空間都無法再裝載任意一批尚未被配裝的貨物，即：

?αi=0均有vi>Vj-∑ni=1vixij

(10)

因為載重量使用約束和車輛容積使用約束不能割裂開來單獨考慮，因此，將2個約束條件合并為一個，稱為滿載約束。即

?αi=0均有wi>Wj-∑ni=1wixijor vi>Vj-∑ni=1vixij

(11)

約束條件3：一批貨物不可分裝的限制。即每批貨物最多只能裝入一輛車內(nèi)。

∑mj=1xij≤1，i=1，2，…，n

(12)

2.4　多目標規(guī)劃模型

建立公路零擔(dān)貨運中轉(zhuǎn)裝車問題的多目標規(guī)劃模型如下：

min(f1，f2，f3)ω，使得

?αi=0均有

或者

vi>Vj-∑ni=1xijvi

(14)

若記f=(f1，f2，f3)C，RC為解空間，那么模型可以簡記為

(15)

(VP)表示該問題為多目標規(guī)劃問題，能夠滿足目標向量f=(f1，f2，f3)C的解稱為多目標問題的絕對最優(yōu)解。但是由于目標向量的不對稱性和約束函數(shù)的存在，所以絕對最優(yōu)解一般不存在于解空間RC。多目標規(guī)劃問題(VP)一般只能得出有效解或者是弱有效解，用來替代最優(yōu)解。因此，在這里將多目標規(guī)劃問題轉(zhuǎn)化為單目標問題進行求解，采用主要目標法，將第一目標函數(shù)確定為首要目標，將第二、第三目標作為次要目標，同時，為每個次要目標確定一個適宜的范圍值后，將其轉(zhuǎn)化為約束條件。此時多目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題，通過解決單目標規(guī)劃問題，找到最優(yōu)解，作為原來多目標問題的有效解或弱有效解。

首先考慮到車輛的標記載重量和載貨容積最大化，并能夠確保貨物配裝的優(yōu)先級得到滿足，同時確保相對于運達期限的運送富裕時間的數(shù)學(xué)期望值不高于一個給定的數(shù)值，進行單目標規(guī)劃模型及其轉(zhuǎn)化。以多目標規(guī)劃問題(VP)中的f1為主要目標，根據(jù)f2，f3的最低界限即理想點，給定f2，f3的適宜界限值β1，β2，并將其轉(zhuǎn)變?yōu)閮蓚€約束條件。這樣多目標規(guī)劃問題(VP)就轉(zhuǎn)化為如下的單目標規(guī)劃問題(SP)，即

(SPT)maxU=f1，使得

(16)

?αi=0均有

或者

vi>Vj-∑ni=1xijvi

(17)

為了減少貨物預(yù)處理的復(fù)雜程度，在這里，主要以能否和其他貨物混裝作為對貨物預(yù)處理的主要依據(jù)。首先，將有混載限制的貨物從所有等待裝車配送的貨物分離出來，再將剩下的，可以與其他貨物無條件配裝的普通貨物劃分為q1，q2…，qn等若干個配裝集(如圖1所示)。

圖1　貨物的預(yù)處理示意圖

單目標規(guī)劃問題加入了f2≥β1、f3≤β2兩個新的約束條件，解空間變?yōu)槎嗄繕艘?guī)劃解空間的子集，單目標規(guī)劃問題求得的解實際上比多目標規(guī)劃問題求得的解的數(shù)量和范圍縮小了。

2.5　解的編碼

為了提高計算的效率，將解的矩陣即0-1稀疏矩陣壓縮為一個向量，向量的元素序列對應(yīng)貨物的序列，這樣，向量元素的取值就不再是0-1，而是采用0-k的取值，即：

Vn={α1，α2，…αn}

(18)

其中，

單目標規(guī)劃問題的適應(yīng)函數(shù)與目標函數(shù)的表達方式一致，因為其目標函數(shù)也為取得最大值。所以，單目標規(guī)劃問題的適應(yīng)函數(shù)又可以表示為f=U=f1。

2.6　隨機解的產(chǎn)生規(guī)則

隨機解產(chǎn)生的過程：首先貨物的配載裝車是一個隨機的過程，即從不受混裝限制的貨物集或者受混裝限制的貨物集Q中隨機選取1批貨物，隨機裝載到m輛車中的任意1輛，并保證滿足約束條件不超過車輛剩余的載重量和載貨容積。當(dāng)配載車輛的剩余載重量和剩余載貨容積接近邊緣狀態(tài)時隨機裝載暫時結(jié)束。對所有未裝載貨物進行統(tǒng)計，如果未被配載的貨物其重量或體積相對于已經(jīng)裝車的貨物，更能夠滿足或者接近滿載的條件約束，則對產(chǎn)生的隨機解進行取舍，如果隨機解滿足f1≥β1且f2≤β2，那么接受該方案，若隨機解的f1<β1或者f2>β2時，那么不接受該方案，此時，該問題解空間為無效解，終止計算，調(diào)節(jié)β1和β2取值大小之后再進行求解過程。

2.7　計算結(jié)果與分析

以廣西宅配通有限公司為例，對相同去向的一批貨物進行預(yù)處理，按照貨物的性質(zhì)，以及混裝與不可混裝等要求，分成53批貨物，經(jīng)預(yù)處理的貨物信息如表1所示，分別裝入2輛標記的載重輛為3.5t、2t，載貨容積為8m3和4m3，剩余載重量為1 200kg、500kg，載貨容積為1.8m3和0.8m3小貨車中。

為了便于計算，在求解單目標規(guī)劃問題的過程中，隨即抽取的貨物的運送富余時間，其數(shù)值都大于或等于β2，這樣，無論如何隨機組合裝車的貨物批次，均能滿足運送平均富余時間大于或等于給定的β1的取值，滿足由目標函數(shù)三轉(zhuǎn)化而成的約束條件。同樣，配裝優(yōu)先級也采用上述方式。

單目標規(guī)劃模型中的β1和β2的首次取值分別設(shè)置為1 500和3，則計算得到的多目標規(guī)劃問題的有效解或單目標規(guī)劃問題的最優(yōu)解的編碼為：

S0=(1，1，1，1，1，1，1，0，1，0，1，1，1，1，1，1，0，0，1，1，0，1，1，1，1，1，1，1，2，2，2，1，1，2，1，2，2，1，2，2，1，1，2，1，1，1，2，2，2，1，1，2，1)

此時f1=1 872>β1=1 500，f2≈3.34>β2=3，不符合隨機解滿足f1≥β1且f2≤β2的條件，為無效解，所以不接受該方案，調(diào)整β2的取值為3.5，繼續(xù)求解。

此時β1=1 500，β2=3.5，計算得到的多目標規(guī)劃問題的有效解或單目標規(guī)劃問題的最優(yōu)解的編碼為：

S0=(1，1，1，1，1，0，1，0，1，0，0，1，1，1，0，0，0，0，1，1，0，1，1，1，1，1，2，2，1，2，1，1，1，2，1，1，2，2，1，1，1，1，1，2，1，1，1，1，1，1，1，1，1)

表1　貨物數(shù)據(jù)表

此時f1=1 547>β1=1 500，f2≈3.41>β2=3.5，滿足f1≥β1且f2≤β2的條件，為有效解，接受該方案，則：

目標函數(shù)值f=f1=0.623

對應(yīng)的單目標規(guī)劃模型中，f2=1 547，f3=3.41。

該結(jié)果表示配裝方案中，等待裝貨的車輛的剩余容重利用率為0.623，貨物裝車的優(yōu)先級為1 547，所有待裝貨物的平均后程運送時間為3.412 h。裝載貨物與車輛的使用情況如表2所示。

表2　貨物裝載以及車輛使用具體情況表

從表2的配送方案可以看出，車輛的平均空間利用率超過90%，而之前宅配通配送車輛的空間利用率一般在80%~85%之間。即使取最高值85%作為平均利用率，也就意味著原來車輛出勤18次配送的貨物量，現(xiàn)在只需17次就能完成，大大提高了車輛的利用率，減少了企業(yè)的物流成本，而且配載過程中充分考慮了貨物的優(yōu)先級以及后程的送達時間，有利于保證貨物在時限內(nèi)送到客戶手中，提高客戶的滿意度。

不足的是，簡化的計算方案雖然能求解出多種裝車方案，但是裝車過程中由于在貨物批次的隨機組合上限定了范圍，因此，求得的只能是多目標規(guī)劃問題的有效解，而不是最優(yōu)解。但是，也可以看出，表2的配載方案并不是最優(yōu)方案，在車輛的利用上，企業(yè)還有很大的改進余地，在節(jié)省企業(yè)成本以及為客戶提供優(yōu)質(zhì)的服務(wù)的問題上，還能夠更高效。

3結(jié)語

本文將車輛載重標記、載貨容積標記以及一批貨物不可分裝作為約束條件，建立了公路零擔(dān)貨物中轉(zhuǎn)配裝的多目標模型，并對模型進行了求解。計算結(jié)果表明：配裝方案在滿足車輛載重與載貨容積約束的基礎(chǔ)上，最大化滿足了車輛的滿載率，提高了企業(yè)車輛的運輸效率，降低了企業(yè)的物流成本。本文的方法簡單可行，給公路零擔(dān)貨運企業(yè)提供了理論參考，對于解決現(xiàn)實問題中的中轉(zhuǎn)裝車問題具有重要的價值和現(xiàn)實意義。

參考文獻

[1]姜桂寶，劉文峰.公路貨運配載問題的研究[J].甘肅科技，2005，21(11)：158-160.

[2]趙峰.物流中心貨物配裝問題研究(碩士學(xué)位論文)[D].長春：吉林大學(xué)，2005.

[3]馬艷玲.物流中心貨運配載系統(tǒng)優(yōu)化研究：(碩士學(xué)位論文)[D].上海：上海海事大學(xué)，2006.

[4]徐大亮，劉小群.多品種貨物配裝的優(yōu)化方法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版)，2003，31(9)：15-17.

[5]李致中.零擔(dān)貨物配裝的數(shù)學(xué)模型[J].系統(tǒng)工程，1987，5(2)：34-39.

[6]曹明蘭.配送中心貨物優(yōu)化配裝問題的模型與算法研究：(碩士學(xué)位論文)[D].北京：北京交通大學(xué)，2007.

[7]史亞貝，楊筍，楊荷.零擔(dān)貨物配裝問題的算法和系統(tǒng)設(shè)計[J].組合機床與自動化加工技術(shù)，2008(3)：86-88，95.

[8]張春梅，菅美英.用改進的遺傳算法求解危險貨物零擔(dān)運輸多目標配裝問題[J].數(shù)學(xué)的實踐與認識，2010，5(9)：121-127.

Application of Multi-objective Programming Model in Urban LTL Loading Cost Optimization Management

ZHONG Ping1，LONG Gui-xian2

(1，Nanning College for Vocational Technology，Nanning，Guangxi，530008；2.Guangxi University of Fi-nance and Economics，Nanning，Guangxi，530003)

Abstract：With the vehicle’s marked maximum load and maximum cargo volume as well as its unsplitta-ble cargo loading as constraints，this article established the multi-objective programming model to study the cargo loading and stowage during “urban goods”transit，and conducted the model application anal-ysis with Guangxi City Express Services Co.，Ltd.，as the example.The results showed that this method is simple and feasible，providing the theoretical reference for highway LTL freight enterprises，with the important value and practical significance for solving the transit loading problem in the practices.

Keywords：Transport economy；Cost optimization；Multi-objective programming；LTL freight；Loading priority

文章編號：1673-4874(2015)12-0068-06

中圖分類號：U492

文獻標識碼：A

DOI：10.13282/j.cnki.wccst.2015.12.016

基金項目

作者簡介
鐘蘋(1977—)，副教授，研究方向：物流管理；
龍桂先(1975—)，講師，碩士，研究方向：物流管理。

收稿日期：2015-11-05