劍，張俊麗，官靜萍

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

1 引言

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

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

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

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

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

2 貨物配送距離分析

2.1 距離成本

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

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

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

圖1 區(qū)域配送圖

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

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

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

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

由式（5）計算出區(qū)域內部配送估算總距離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 模型確定

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

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

目標函數：

約束條件：

3.2 算法步驟

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

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

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

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

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

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

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

4 實例數據對比分析

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

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

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

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

表4 配送成本對比

圖3 車型組合對比

5 結束語

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