基于車公里成本的多車型車輛規(guī)劃方法

劍，張俊麗，官靜萍

（1.湖南科技大學(xué) 資源環(huán)境與安全工程學(xué)院，湖南 湘潭 411201；2.湖南科技大學(xué) 知識處理與網(wǎng)絡(luò)化制造湖南省實驗室，湖南 湘潭 411201）

1 引言

作為一類經(jīng)典的NP-hard問題，車輛路徑問題（VRP）一直是現(xiàn)代物流領(lǐng)域的研究熱點。隨著研究的不斷深入，VRP問題更趨向于具體化和實用性，譬如增加倉庫約束、車型裝載量約束、裝卸順序約束、時間窗約束等。目前VRP的方法主要分為兩類：精確算法和啟發(fā)式算法。啟發(fā)式算法的求解精度雖不如精確算法那么高，但是因其時間效率表現(xiàn)更為明顯而受到青睞，或者將兩種算法相結(jié)合改進(jìn)求解質(zhì)量。

實際上，車輛路徑問題主要包括車輛規(guī)劃和路徑規(guī)劃。車輛規(guī)劃問題和路徑規(guī)劃問題相互制約，相關(guān)學(xué)者一般分為兩種，一是先車輛規(guī)劃后路徑規(guī)劃，二是車輛規(guī)劃和路徑規(guī)劃同時進(jìn)行。從先車輛規(guī)劃后路徑規(guī)劃的角度而言，當(dāng)前的研究主要集中在單車型VRP問題上，并對此提出一系列的啟發(fā)式算法及改進(jìn)方式，計算步驟一般為依據(jù)最高裝載率原則，得到貨物配送所需的最少車輛數(shù)，如Barrie M[1-6]等運(yùn)用遺傳算法求解單倉庫單車型VRP問題；梁承姬[7-9]等利用蟻群算法并加以改進(jìn)優(yōu)化求解單車型VRP問題；劉春苗等[10]運(yùn)用禁忌搜索算法求解帶時間窗的單車型VRP問題；馬華偉等[11]運(yùn)用禁忌搜索算法求解帶時間窗的單車型VRP問題；胡云清等[12-13]采用改進(jìn)螢火蟲算法求解單車型VRP問題。從車輛規(guī)劃和路徑規(guī)劃同時進(jìn)行求解的角度而言，Petrica C[14]通過結(jié)合局部-全局算法對遺傳算法進(jìn)行改進(jìn)，車輛問題和路徑問題同時考慮求解單車型VRP問題。在單車型VRP問題中，所需車輛數(shù)可以依據(jù)總貨物量進(jìn)行約束，以最高裝載率優(yōu)先得到高質(zhì)量解。

而在現(xiàn)實物流配送中，為了滿足不同客戶需求，往往是多種車型進(jìn)行同時配送。在多車型VRP問題中，因為車型裝載的限制不同，其車型的可用組合數(shù)增加，VRP問題的求解更為多樣。針對多車型VRP問題的相關(guān)研究較少，盧冰原等[15]基于混合粒子群算法求解多車型調(diào)度問題；熊浩等[16]以最小油耗為目標(biāo)利用改進(jìn)遺傳算法求解多車型動態(tài)車輛調(diào)度問題；Wenbin Zhu[17]認(rèn)為在多車型VRP問題中，難點在于車型組合的不確定性。相關(guān)學(xué)者往往將全部可能的組合進(jìn)行考慮，雖然可以提高全局的最優(yōu)解，但也同時增加了問題的復(fù)雜性。

在單車型VRP問題的求解中，需要在VRP的路徑規(guī)劃之前，先進(jìn)行貨物量或者總流量與當(dāng)前車型的裝載率要求，選出本次派送需要的最少車輛數(shù)，然后在此基礎(chǔ)上，運(yùn)用各自的搜索策略逐步求解，但也暴露了一些問題。VRP問題求解不單單是指車型裝載的約束，與途中的各個運(yùn)輸路徑均有關(guān)系，整個路徑規(guī)劃應(yīng)該是總體最優(yōu)的結(jié)果；其二是對于多種車型而言，這種車型的簡單約束并不能反映出問題，在路徑規(guī)劃中，大小不等的車型相互配合，路徑的不同也會對車型組合產(chǎn)生影響。所以在多車型VRP問題的求解中，目前的文獻(xiàn)研究多是通過將路徑與車型結(jié)合動態(tài)規(guī)劃最終結(jié)果，運(yùn)用車型組合與路徑規(guī)劃動態(tài)規(guī)劃，最優(yōu)近似解的質(zhì)量相較于單車型VRP問題更為合理，更加符合實際需求。不足之處在于動態(tài)規(guī)劃過程中，車型組合數(shù)量的不確定增加了搜索的更多可能性，增加了求解的時間復(fù)雜度。

本文的出發(fā)點在于依據(jù)實際物流配送中的多車型問題，借鑒相關(guān)學(xué)者的經(jīng)驗，以行政區(qū)域作為分區(qū)標(biāo)準(zhǔn)，加以車公里成本約束條件和距離估算模型，基于分枝定界思想構(gòu)造多車輛規(guī)劃整數(shù)模型，為路徑規(guī)劃前的車輛調(diào)度提供更為精確的理論支撐和數(shù)據(jù)對比，從而得到VRP問題的更高質(zhì)量解。

2 貨物配送距離分析

2.1 距離成本

在當(dāng)前的各種VRP求解中，關(guān)鍵在于如何在裝完所有貨物的前提下，使得貨物的總配送成本最低。假設(shè)在實際配送中，如果對較遠(yuǎn)的區(qū)域配送，盡量一次性用大車型裝載區(qū)域較遠(yuǎn)的貨物，把不必要的途中配送成本降低，而非利用多輛小車型進(jìn)行多次往返配送，顯然前者的成本會更低。

貨物配送是一個非常復(fù)雜的過程，區(qū)域大小和客戶點分布程度都影響著運(yùn)輸方案的復(fù)雜程度。實際配送中一般選用分區(qū)配送的方法提高配送的效率，分區(qū)配送就是把大型區(qū)域劃分成較小區(qū)域來配送貨物，在研究過程中，配送距離劃分為兩部分，即倉庫點至配送區(qū)域外圍的車輛外部單向行駛距離L1和配送區(qū)域內(nèi)部車輛行駛總距離L2，在圖1中，倉庫點A為配送中心，配送區(qū)域R，區(qū)域內(nèi)部包含客戶點和單車輛配送路線。在一次貨物配送過程中，配送總成本Costall包括區(qū)域外部配送總成本CostL1和區(qū)域內(nèi)部配送總成本CostL2：

在上述公式中，總貨物量為W，倉庫有n種車型{0,1,2,...,n},其中wi表示車型i的額定裝載量，Ci表示車型i的車公里成本，xi表示車型i在本次配送中所需的車輛數(shù)，q為本次配送的平均裝載率，一般取值為0.85-0.90。式（1）表示總配送成本包括區(qū)域外部配送總成本CostL1和區(qū)域內(nèi)部配送總成本CostL2；式（2）表示按照車型i所需車輛數(shù)xi在外部的往返配送成本為xi*2L1*Ci，可得到區(qū)域外部配送總成本CostL1；式（3）表示xiTi為本次配送過程中車型i在區(qū)域內(nèi)部的行駛距離，車型i在區(qū)域內(nèi)部的配送成本即為xiTiCi，可得到區(qū)域內(nèi)部配送總成本CostL2；式（4）表示由配送區(qū)域內(nèi)部行駛的總距離依據(jù)每輛車的平均裝載量占總貨物量的比重來計算在本次配送中每輛車在區(qū)域內(nèi)部的行駛距離Ti。

圖1 區(qū)域配送圖

2.2 分區(qū)配送距離估算

在分區(qū)配送過程中，區(qū)域外部配送總成本CostL1由已知的車公里成本數(shù)據(jù)和L1可計算得到，主要在于計算區(qū)域內(nèi)部配送總成本CostL2，由公式（3）可知，CostL2可依據(jù)Ti得到，而車型在區(qū)域內(nèi)部的行駛距離Ti是動態(tài)的，而Ti依賴于L2。在按照行政區(qū)域規(guī)劃的分區(qū)標(biāo)準(zhǔn)，區(qū)域分布離散度表示區(qū)域內(nèi)各客戶點的地理分布程度。對于每一個待配送區(qū)域，區(qū)域分布離散度各不相同，待配送區(qū)域內(nèi)部的客戶在地理位置上隨機(jī)分布，客戶點的各貨物需求量也不同，L2也隨之不確定。即使同樣的客戶數(shù)和配載貨物量，由于區(qū)域分布離散度的不同，區(qū)域內(nèi)部的配送距離L2也會有所變化。

在L2的計算過程中，Bahar Cavdara[18]提出了一個基于隨機(jī)分布點的TSP距離估算模型：

式（5）中L2即本配送區(qū)域內(nèi)部估算車輛行駛總距離，n為本次待配送區(qū)域內(nèi)客戶點數(shù)量，A為配送區(qū)域面積，首先從百度API接口獲取客戶點的經(jīng)緯度坐標(biāo)，可以計算出配送區(qū)域中心點C的坐標(biāo)，為各客戶點到區(qū)域中心點C的平均距離，距離的衡量標(biāo)準(zhǔn)采用百度距離，符合實際需求；stdevx,stdevy為客戶點經(jīng)緯度坐標(biāo)的標(biāo)準(zhǔn)差，衡量客戶點的總體分散程度，整體區(qū)域客戶越分散，值越大；cstdevx,cstdevy為各客戶點與中心點的絕對距離的標(biāo)準(zhǔn)差，表示各客戶距離區(qū)域中心的分布程度。

由式（5）計算出區(qū)域內(nèi)部配送估算總距離L2，此時得到客戶點之間的平均距離D為(L2/n)，區(qū)域分布離散度R為(stdevx2+stdevy2)/n。

由表1得到平均距離D與區(qū)域分布離散度R之間的線性回歸方程：

圖2為部分區(qū)域的區(qū)域分布離散度R與平均距離D及其線性回歸方程趨勢線。

表1 區(qū)域分布離散度R與平均距離D

圖2 平均距離與區(qū)域分布離散度的線性方程

3 車公里成本車輛規(guī)劃模型

3.1 模型確定

本文的問題描述：在實際派車過程中，以某物流中心作為貨物配送中心，配送中心已選取好待配載車型及其數(shù)量進(jìn)行集中配送。在項目的實施過程中，配送步驟為：統(tǒng)計當(dāng)天的波次訂單，然后依據(jù)貨物總量和已有車型選出裝載組合，然后進(jìn)行路徑規(guī)劃。

模型中所需變量描述：假設(shè)某物流倉庫點有W體積待配載貨物，有n種車型可供選擇：{m1,m2,...,mn}，各車型數(shù)量上限：{n1,n2,...,nn}輛，各車型額定裝載量：{w1,w2,...,wn}體積，各車型的每公里油耗：{C1,C2,...,Cn}，各車型的最高裝載率：{q1,q2,...,qn}，假設(shè)本次配送各車型需要{x1,x2,...,xn}輛，車輛外部單向行駛距離為L1，車輛內(nèi)部行駛總距離為L2。

目標(biāo)函數(shù)：

約束條件：

3.2 算法步驟

本文模型基于分枝定界法[19-20]的思想進(jìn)行構(gòu)建，分枝定界法作為一種在問題的解空間樹上搜索問題界的算法，在滿足約束條件的解中找出使目標(biāo)函數(shù)值達(dá)到極大或極小的解，即最優(yōu)解。其策略是，在擴(kuò)展結(jié)點處，先生成其所有的兒子結(jié)點，以加速搜索進(jìn)程，在每一活結(jié)點處，計算一個函數(shù)值，并根據(jù)這些已經(jīng)計算出的函數(shù)值，從當(dāng)前活結(jié)點表中選擇一個最有利的結(jié)點作為擴(kuò)展結(jié)點，使搜索向著解空間樹上最優(yōu)解的分支推進(jìn)，以便盡快找出一個最優(yōu)解。

本文的整數(shù)規(guī)劃模型應(yīng)用分支定界思想的計算步驟如下：

定義最大油耗成本為Costmax，最小油耗成本Costmin；

（1）先將上述模型中目標(biāo)函數(shù)問題P轉(zhuǎn)換為相應(yīng)的線性規(guī)劃問題P'求解，若P'無解則無解；若P'有解，且xi均滿足整數(shù)條件，則{x1',x2',...,xn'}即為最優(yōu)解，最優(yōu)運(yùn)輸成本為Cost'；若P'有解，但不符合整數(shù)條件，Costmax即Cost'。

（2）分枝：尋找此時解空間的非整數(shù)車型解，例如車型解的第一個非整數(shù)為x1'，構(gòu)造兩個約束條件x1≤floor(x1')和x1≥floor(x1'+1)；將這兩個條件重新加入到約束條件模型中，進(jìn)行計算。

（3）定界：以每個后繼問題為一分枝標(biāo)明求解的結(jié)果，在其它問題解的結(jié)果中找出最大配送成本作為新的Costmax，從已符合整數(shù)車型解的各分枝中找出最大配送成本作為Costmin。

（4）比較與剪枝：各分枝的最優(yōu)車型解的運(yùn)輸油耗成本若小于最大配送成本Costmin，則剪掉這枝，以后不再考率；若大于最小配送成本，且不符合整數(shù)條件，則重復(fù)（1）步驟，直到Costmax-Costmin在誤差范圍內(nèi)，保存此時的車型解，即為最優(yōu)車型組合{x1,x2,...,xn}，最優(yōu)配送成本為Costmin。

4 實例數(shù)據(jù)對比分析

實際案例描述，倉庫中心分布于湖南省湘潭市岳塘區(qū)內(nèi)，分區(qū)配送區(qū)域見表2，包括近距離區(qū)域（湘潭市雨湖區(qū)）、中距離區(qū)域（婁底市婁星區(qū)）以及遠(yuǎn)距離區(qū)域（常德市鼎城區(qū)），選定每個區(qū)域的一個波次訂單開始配送。車型為倉庫中心已有可用車輛，車型按照體積大小排序為{a,b,c,d,e,f,g,h,i,j}，車公里成本數(shù)據(jù)見表3，L1因為中心倉庫點和各配送區(qū)域虛擬倉庫點均為固定而固定，由于波次訂單的不同，依據(jù)式（5）動態(tài)計算L2，下面各實例A1-YH-14979（實例編號-區(qū)域編號-貨物總量）將考慮距離成本的分支定界算法與只考慮裝載率不考慮距離成本的一般精確算法進(jìn)行最終配送成本的對比，見表4。實驗數(shù)據(jù)對比包括同一區(qū)域不同貨物量的配送成本比較和不同區(qū)域間的配送成本對比，在當(dāng)前實例中車型組合的構(gòu)成對比如圖3所示，同一實例左側(cè)為本文模型計算得到的車型組合構(gòu)成，右邊為只考慮裝載率的一般精確算法結(jié)果。

表2 倉庫點、各分區(qū)坐標(biāo)和L1

表3 車型體積及車公里成本

從實驗結(jié)果可以看出：（1）在表3中，對于不同區(qū)域，在添加車公里成本約束條件之后，基于車公里成本的車輛規(guī)劃模型計算的配送總成本均得到不同程度的優(yōu)化，尤其在較遠(yuǎn)區(qū)域（鼎城區(qū)），成本優(yōu)化比高達(dá)80%；（2）對于同一區(qū)域，選用不同的初始車型組合，較大車型組合的配送成本更低；（3）圖3中，在同一實例數(shù)據(jù)的對比中，左側(cè)基于車公里成本模型的車型組合結(jié)果相較于右側(cè)只基于裝載率模型的車型組合結(jié)果，大車型選擇占比更高，配送總成本更優(yōu)。

表4 配送成本對比

圖3 車型組合對比

5 結(jié)束語

在物流配送中，裝載率最優(yōu)并非總成本最優(yōu)，車公里成本約束使得總成本最低更切合實際。單考慮裝載率約束的組合裝載成本并非最優(yōu)，這表現(xiàn)在當(dāng)一些小車型可以滿足最高裝載率的同時，組合裝載所用到的車型數(shù)量也會有所增長，而車型總數(shù)量的增加在較遠(yuǎn)距離運(yùn)輸中，導(dǎo)致物流運(yùn)輸總成本也隨之大幅提高。在遠(yuǎn)距離運(yùn)輸選用大車型時，一輛大車的運(yùn)輸成本往往低于兩輛甚至多輛小車型組合運(yùn)輸?shù)某杀?。由實驗?shù)據(jù)分析，加入車公里成本的考量，可以使得在路徑規(guī)劃前的車輛裝載調(diào)度表現(xiàn)更為合理。在進(jìn)行啟發(fā)式算法的路徑規(guī)劃前，合理的進(jìn)行車輛控制尤為必要。