多目標規劃模型在城市零擔配裝成本優化管理中的應用

鐘　蘋，龍桂先

(1.南寧職業技術學院，廣西　南寧　530008；2.廣西財經學院，廣西　南寧　530003)

多目標規劃模型在城市零擔配裝成本優化管理中的應用

鐘蘋1，龍桂先2

(1.南寧職業技術學院，廣西南寧530008；2.廣西財經學院，廣西南寧530003)

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

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

關鍵詞：運輸經濟；成本優化；多目標規劃；零擔貨運；配裝優先級

0引言

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

本文以廣西城市貨的樣板——廣西宅配通有限公司為例，提出采用多目標規劃模型的方法對當地城市貨的貨運運營進行分析，為當地城市配送業務降低運輸配送成本提出優化方案。

1廣西宅配通零擔貨運現狀問題及分析

1.1　貨源組織力度不足

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

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

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

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

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

1.3　經營業務單一

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

2多目標規劃模型的建立

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

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

2.1　參數定義

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

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

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

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

2.2　目標函數

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

maxZw=∑mj=1∑ni=1wixij

(1)

maxZv=∑mj=1∑ni=1vixij

(2)

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

(3)

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

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

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

f2=maxZp=∑ni=1pixij

(4)

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

(5)

(6)

2.3　約束條件

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

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

2.4　多目標規劃模型

建立公路零擔貨運中轉裝車問題的多目標規劃模型如下：

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

?αi=0均有

或者

vi>Vj-∑ni=1xijvi

(14)

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

(15)

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

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

(SPT)maxU=f1，使得

(16)

?αi=0均有

或者

vi>Vj-∑ni=1xijvi

(17)

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

圖1　貨物的預處理示意圖

單目標規劃問題加入了f2≥β1、f3≤β2兩個新的約束條件，解空間變為多目標規劃解空間的子集，單目標規劃問題求得的解實際上比多目標規劃問題求得的解的數量和范圍縮小了。

2.5　解的編碼

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

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

(18)

其中，

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

2.6　隨機解的產生規則

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

2.7　計算結果與分析

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

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

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

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的條件，為無效解，所以不接受該方案，調整β2的取值為3.5，繼續求解。

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

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　貨物數據表

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

目標函數值f=f1=0.623

對應的單目標規劃模型中，f2=1 547，f3=3.41。

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

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

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

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

3結語

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

參考文獻

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

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

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

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

[5]李致中.零擔貨物配裝的數學模型[J].系統工程，1987，5(2)：34-39.

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

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

[8]張春梅，菅美英.用改進的遺傳算法求解危險貨物零擔運輸多目標配裝問題[J].數學的實踐與認識，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