劍，張俊麗，官靜萍

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

1 引言

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

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

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

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

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

2 貨物配送距離分析

2.1 距離成本

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

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

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

圖1 區(qū)域配送圖

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

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

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

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

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

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

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

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

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

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

3.1 模型確定

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

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

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

約束條件：

3.2 算法步驟

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

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

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

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

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

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

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

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

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

表2 倉(cāng)庫(kù)點(diǎn)、各分區(qū)坐標(biāo)和L1

表3 車(chē)型體積及車(chē)公里成本

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

表4 配送成本對(duì)比

圖3 車(chē)型組合對(duì)比

5 結(jié)束語(yǔ)

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