基于兩階段法的車輛配載優(yōu)化分析

王鶴+曾寧波+劉婧雯

摘要：本文從降低物流配送成本，提高車輛利用率的角度出發(fā)，綜合考慮車輛的額定容積與載重、訂單價(jià)值等多重因素，建立了相應(yīng)的決策模型，并設(shè)計(jì)了改進(jìn)的兩階段法和0-1型整數(shù)規(guī)劃進(jìn)行決策方案的求解，將此模型實(shí)際運(yùn)用到某小家電制造商的車輛配載過(guò)程中，對(duì)比結(jié)果分析表明，該優(yōu)化模型不僅能提高車輛利用率，更能大幅提升物流配送利潤(rùn)。該模型結(jié)果對(duì)車輛配載的優(yōu)化研究具有一定借鑒意義。

關(guān)鍵詞：車輛配載；訂單分析；兩階段法；0-1型整數(shù)規(guī)劃

中圖分類號(hào)：F252 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1005-913X（2017）06-0036-03

一、引言

隨著物流行業(yè)的蓬勃發(fā)展，物流配送領(lǐng)域的不斷擴(kuò)大，車輛資源的利用率問(wèn)題逐漸成為物流管理人員一大關(guān)注點(diǎn)。據(jù)中國(guó)物流信息中心物流統(tǒng)計(jì)數(shù)據(jù)表明，發(fā)達(dá)國(guó)家的物流費(fèi)用占國(guó)民生產(chǎn)總值（GDP）的比重遠(yuǎn)低于10%，而我國(guó)這一項(xiàng)數(shù)據(jù)已攀升至17.8%，約為發(fā)達(dá)國(guó)家的兩倍，物流費(fèi)用的持續(xù)攀高使得企業(yè)的資金運(yùn)轉(zhuǎn)壓力增大。同時(shí)，我國(guó)市場(chǎng)上一般物流企業(yè)的車輛平均載重率為75.67%，車輛平均容積率僅65.37%，大量車輛資源的浪費(fèi)導(dǎo)致企業(yè)管理成本增加。顯然，配送成本和管理成本作為物流成本中占比最大的一項(xiàng)，降低這兩類成本將引起物流成本增速的放緩，直接提高物流配送利潤(rùn)，為企業(yè)帶來(lái)更大的運(yùn)營(yíng)效益。此前，有不少關(guān)于優(yōu)化車輛配載模型的研究。如劉鐵男（2014）通過(guò)對(duì)車輛的判斷和對(duì)貨物的特性分類，運(yùn)用貪婪算法建立物流車輛配載模型進(jìn)行有效的拼裝組合，實(shí)現(xiàn)車輛的載重和容積利用程度達(dá)到最大，結(jié)果顯示，可以大力的節(jié)省運(yùn)力，節(jié)省物流企業(yè)的配送成本。[1]謝天保（2010）等將染色體的進(jìn)化過(guò)程運(yùn)用到遺傳算法求解中，在任務(wù)時(shí)間窗和車輛實(shí)際容量的約束條件下建立車輛配載調(diào)度模型，最后通過(guò)實(shí)驗(yàn)分析證明運(yùn)用該模型快速求解最優(yōu)解，且結(jié)果具有一定的借鑒意義。[2]曹明蘭（2009）等為保證配貨中的穩(wěn)定客源，通過(guò)設(shè)立顧客緊急系數(shù)，運(yùn)用二階段法，分別在不同階段實(shí)現(xiàn)不同的目標(biāo)，最后建立能夠?qū)崿F(xiàn)滿足客戶需求目標(biāo)的能使車輛得到充分利用的車輛配載模型。[3]胡貴彥等通過(guò)對(duì)傳統(tǒng)型配載模型的優(yōu)化，將配載車輛分成平面的分別有約束條件的四個(gè)放置區(qū)，利用計(jì)算機(jī)編程技術(shù)，開(kāi)發(fā)了能使空間利用率達(dá)到最優(yōu)的視窗軟件，傳統(tǒng)模型與優(yōu)化模型對(duì)比可知，優(yōu)化模型可大幅提高車輛的空間利用率。[4]楊錦冬（2004）等從車輛駕駛員和物流企業(yè)的雙角度出發(fā)，在約束條件下，利用0-1整數(shù)規(guī)劃建立了一個(gè)配送配載雙目標(biāo)優(yōu)化模型，實(shí)現(xiàn)了配送路徑最短，拼裝方案最優(yōu)的目標(biāo)，仿真實(shí)驗(yàn)證實(shí)了該模型的可行性。[5]Liu（2016）等考慮在帶時(shí)間窗和裝載車輛的約束條件下，運(yùn)用改進(jìn)的分支定界方法和貪婪算法建立車輛配載的優(yōu)化模型，結(jié)果表明，其模型能夠提高整車物流的配載效率。[6]

上述文獻(xiàn)是假設(shè)在車輛的承載能力的約束下，以滿足客戶要求和配送成本最小為目標(biāo)建立模型，沒(méi)有考慮到交貨期、配送時(shí)間及利潤(rùn)等方面的影響，雖然這樣的模型能夠最大限度的利用車輛的容積和載重，滿足客戶淺層次的要求級(jí)按時(shí)交貨，這樣不僅忽視了所要配送的訂單優(yōu)先級(jí)別，不能夠在提高車輛利用率的同時(shí)做到重要的訂單優(yōu)先配送，并且未將所配送的訂單價(jià)值作為影響因素考慮進(jìn)去，這樣所帶來(lái)的問(wèn)題是提高了利用率的同時(shí)降低了客戶滿意度，并沒(méi)有達(dá)到最佳效果。因此，本文運(yùn)用兩階段法以及0-1型整數(shù)規(guī)劃，分階段合理設(shè)置目標(biāo)函數(shù)及變量、參數(shù)，第一階段考慮了訂單優(yōu)先度大小問(wèn)題，確定必須優(yōu)先配送的訂單，做好客戶管理，維系好客戶關(guān)系；第二階段考慮了車輛容積、載重的利用率和訂單價(jià)值問(wèn)題，將訂單價(jià)值作為主要因素，在其排序結(jié)果及車輛的核定容積與載重的約束下，確定最終的車輛配載方案，使車輛利用率得到提高，配送成本下降，不同程度的提升配送利潤(rùn)。

二、基于車輛配載優(yōu)化問(wèn)題的建模

（一）建模前提

可以將車輛的配載優(yōu)化問(wèn)題描述為：針對(duì)制造商所接到的訂單，選擇最佳的車輛配載方案，在一定的約束條件下，諸如所要配送的訂單交貨期一定，均能滿足客戶的按時(shí)交貨要求，且一個(gè)訂單至少包括一種貨物，同一訂單的貨物由同一次車輛進(jìn)行配送，每件貨物的實(shí)際容積和重量在車輛的承受范圍之內(nèi)，不存在超載現(xiàn)象，同時(shí)，所有待配載的訂單為原始訂單，未經(jīng)后期的加工處理，無(wú)插單、割單等，使物流企業(yè)在高度滿足客戶要求，配送的訂單價(jià)值達(dá)最大，車輛利用率提高，提升配送利潤(rùn)。

（二）符號(hào)說(shuō)明

決策參數(shù)：

i為訂單編號(hào)，i=1，2，3......n；Hi為訂單優(yōu)先度，i=1，2，3......n；Ai為單個(gè)訂單的訂單價(jià)值量，i=1，2，3......n；Bi為制造商對(duì)客戶的預(yù)測(cè)訂單月交易量，i=1，2，3......n；Ci為訂單的客戶重要程度，i=1，2，3......n；根據(jù)唐麗春，蔡曉毅（2009）在供應(yīng)鏈環(huán)境下對(duì)影響訂單優(yōu)先權(quán)的因素所采用的線性歸一化的處理結(jié)果將Ai，Bi，Ci的系數(shù)分別設(shè)為0.6，0.3，0.1；W2，V2為第一階段配載貨物后車輛的剩余容積和載重，W2=W-wk，V2=V-vk，是第二階段配載的限制變量；j表示將第二階段訂單的計(jì)算看作不同的計(jì)算步驟j=1，2，3......n-1；Wj，Vj分別為第二階段進(jìn)行到第j步時(shí)，所裝載的容積和載重；x，y為第二階段車輛中裝入貨物總重量和總?cè)莘e；αwj，βvj取決于下面的決策變量。

決策變量：

α1累加訂單容積及載重≤W

0 否則，

β1累加訂單容積及載重≤V

0 否則，

（三）車輛配載優(yōu)化模型

建立的車輛配載優(yōu)化模型如下：

式（1）為第一階段的目標(biāo)函數(shù)，式（2）式（3）為第二階段目標(biāo)函數(shù)，表示在已知訂單優(yōu)先度的前提下，滿足約束條件的車輛利用最優(yōu)化，訂單價(jià)值最大化。式（4）至式（9）為模型的約束條件，式（4）表示第一階段選出來(lái)的訂單，其訂單優(yōu)先度必須為最高，式（5）式（6）表示第二階段的容積載重不得超過(guò)車輛的核定容積載重，式（7）表示第二階段初始必須對(duì)訂單價(jià)值進(jìn)行排序處理，式（8）式（9）表示第二階段累加計(jì)算的訂單容積和載重不得超過(guò)第二階段剩余容積和載重。

三、算法描述

為了更好的實(shí)現(xiàn)車輛配載優(yōu)化，提高物流企業(yè)單次配送利潤(rùn)，本文采用兩階段法和0-1型整數(shù)規(guī)劃相結(jié)合的算法構(gòu)建優(yōu)化模型。

第一階段：當(dāng)制造商接收到一批需要配送的訂單集合1，2，3，...，n時(shí)，整理其所有的訂單數(shù)據(jù)，確定每個(gè)訂單的訂單價(jià)值A(chǔ)i，月交易量Bi和客戶重要程度Ci，據(jù)式（1），對(duì)這三個(gè)指標(biāo)分別給予不同的權(quán)重，可得每個(gè)訂單的訂單優(yōu)先度數(shù)值。根據(jù)數(shù)值結(jié)果，將數(shù)值最大的訂單確定為第一階段必須配載的貨物訂單k。

第二階段：在求出訂單的基礎(chǔ)上，可知車輛剩余容積和載重W2，V2。同時(shí)，對(duì)剔除后的訂單集合1，2，...，k-1，k+1，...n進(jìn)行以訂單價(jià)值為關(guān)鍵詞的排序處理，第二階段的計(jì)算在此排序結(jié)果的前提下進(jìn)行。將剩余的n-1個(gè)訂單看成不同的n-1個(gè)計(jì)算步驟，根據(jù)式（8）式（9），對(duì)0-1型變?chǔ)粒铝糠謩e進(jìn)行取值計(jì)算，即可求得從訂單k開(kāi)始累加的車輛容積與載重wi，vi直至累加達(dá)到maxf（x，y）即式（2）時(shí)，計(jì)算停止，可以得到最佳的配載方案P=1，...，k，...，n使得車輛利用率最大化，配送利潤(rùn)得到不同程度的提升。

四、算例分析

在本算例中，由于制造產(chǎn)品均為小家電，因此，假設(shè)使用一輛額定載重為1.5t，容積為12m3的輕型配送車輛進(jìn)行配載。以某家電制造企業(yè)2016年6月份其中兩天的訂單數(shù)據(jù)為例，訂單產(chǎn)品的基礎(chǔ)數(shù)據(jù)如表1所示，分別統(tǒng)計(jì)來(lái)自十家門店訂單的貨物容積、重量以及訂單價(jià)值。

第一階段，由式（1）Hi=0.6Ai+0.3Bi+0.1Ci計(jì)算可得十個(gè)訂單的訂單優(yōu)先度，計(jì)算結(jié)果如表2所示。對(duì)此結(jié)果進(jìn)行排序，由式（3）很明顯的可以看出，必須優(yōu)先配送的訂單1，來(lái)自寶山店，其訂單優(yōu)先度為11563.50。

第二階段，確定好第一階段必須配送的訂單的容積為2.316m3，重量為204kg后，可以求得車輛的剩余載重W2=1296kg，剩余容積V2=9.684m3。據(jù)式（6），對(duì)其他訂單進(jìn)行以訂單價(jià)值為關(guān)鍵詞的排序，如表4所示。由第二階段目標(biāo)函數(shù)式（2）可得，當(dāng)j=1時(shí)，α=1，β=1即

顯可以看出，經(jīng)過(guò)6個(gè)步驟后，可以求得此規(guī)劃問(wèn)題的最優(yōu)解即最佳車輛配載方案為1、4、5、6、8、9，該方案的訂單容積量為11.718m3，重量為878.1kg，車輛的容積利用率和載重利用率分別為98%和59%，配送的訂單價(jià)值達(dá)高達(dá)77753.5元。

同時(shí)，為了更顯著的比對(duì)出模型的優(yōu)化效果，通過(guò)計(jì)算機(jī)程序語(yǔ)言，以車輛核定容積為主要的約束條件，對(duì)所有訂單進(jìn)行隨機(jī)組合，共有141120種組合結(jié)果，選取到其中結(jié)果最佳的隨機(jī)組合方案為訂單1、2、3、5、7、8，計(jì)算可得此隨機(jī)方案的車輛容積載重利用率，可知其配送的訂單價(jià)值大小，具體的比對(duì)結(jié)果如表4所示。

由表4可以看出，雖然隨機(jī)方案的容積利用率為99%，比優(yōu)化方案高1%，但在車輛的載重率以及單次配送的訂單價(jià)值上，優(yōu)化方案都略勝一籌，配送的訂單價(jià)值更是比隨機(jī)方案要多1746元。在物流公司的實(shí)際運(yùn)營(yíng)過(guò)程中，提高現(xiàn)有車輛資源的利用率固然重要，但流動(dòng)資金對(duì)一個(gè)公司生產(chǎn)經(jīng)營(yíng)起著決定性力量，如何使配送利潤(rùn)得到提升，配送成本不斷降低同樣受到關(guān)注。因此，在對(duì)比結(jié)果的時(shí)候不能單獨(dú)比較車輛利用率的浮動(dòng)，應(yīng)該更加關(guān)注訂單價(jià)值即單次配送利潤(rùn)的大小。顯然，從結(jié)果分析可知，優(yōu)化模型的結(jié)果是可行的，具有一定借鑒意義。

五、結(jié)語(yǔ)

本文通過(guò)研究分析物流企業(yè)的車輛配載過(guò)程車輛的利用率過(guò)低以及配送成本偏高的問(wèn)題，建立了兩階段法和0-1型整數(shù)規(guī)劃的相結(jié)合雙算法優(yōu)化模型。該模型綜合考慮到了影響訂單和物流服務(wù)的多個(gè)因素，如訂單優(yōu)先度，訂單價(jià)值，車輛有效容積、重量等。在加強(qiáng)客戶合作關(guān)系的同時(shí)，提高物流企業(yè)車輛利用率，實(shí)現(xiàn)了車與貨的高效匹配，大幅提升了企業(yè)配送利潤(rùn)，降低了配送成本。在實(shí)證研究中，以某家電制造企業(yè)為例，計(jì)算了訂單的增量訂單價(jià)值以及車輛容積重量利用率，并通過(guò)計(jì)算機(jī)程序，科學(xué)選取了隨機(jī)方案進(jìn)行對(duì)比，研究結(jié)論對(duì)優(yōu)化車輛配載有一定的指導(dǎo)意義。

參考文獻(xiàn)：

[1] 劉鐵男.貪婪式算法在在物流配送車輛配載模型中的應(yīng)用[J].物流技術(shù)，2014，33（10）.

[2] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（36）.

[3] 曹明蘭，郎茂祥，曹明琴，喬曉東.考慮客戶需求優(yōu)先級(jí)的貨物配裝問(wèn)題的模型與算法研究[J].物流科技，2006（29）.

[4] 胡貴彥，杜志平，孫衛(wèi)華，鐘芙蓉.貨物配載方法最優(yōu)化的研究[J].物流技術(shù)，2009，28（8）： 86-107.

[5] 楊錦冬，徐麗群.城市物流中心車輛配送配載調(diào)度指派模型研究[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)報(bào)， 2004（11）.

[6] Liu J S，Alice E S，Dan Q. The vehicle loading problem with a heterogeneous transport fleet[J]. Computers & Industrial Engineering.2016，97： 137-145.

[7] 靳志宏，于 波，侯麗曉.基于配載約束的配送優(yōu)化問(wèn)題及其求解算法[J].系統(tǒng)工程學(xué)報(bào)，2012（3）.

[8] 孫國(guó)華.帶時(shí)間窗的開(kāi)放式滿載車輛路徑問(wèn)題建模及其求解算法[J].系統(tǒng)工程理論與實(shí)踐，2012，32（8）.

[9] 朱 偉，徐克林，佀占華，周 娜.單車輛物流配送決策模型及其遺傳算法[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（6）.

[10] 包得海，管會(huì)生.一種求解貨物配送問(wèn)題的改進(jìn)算法[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2011（5）：12-16.

[責(zé)任編輯：譚志遠(yuǎn)]