基于車輛配送線路的區(qū)域協(xié)同配送方法

吳亮然，林 劍，劉毅志，劉 敏

1.湖南科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 湘潭411201

2.知識(shí)處理與網(wǎng)絡(luò)化制造湖南省教育廳重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭411201

1 引言

物流配送所要解決的核心問題是車輛路徑問題（Vehicle Routing Problem，VRP）[1]，傳統(tǒng)的解決此類問題的方法多以動(dòng)態(tài)規(guī)劃方法和啟發(fā)式算法兩種，如掃描算法[2-3]、動(dòng)態(tài)搜索算法[4-5]、遺傳算法以及它的改進(jìn)算法[6-7]等。

隨著城市化進(jìn)程的不斷加快，城市輻射面積相應(yīng)擴(kuò)大。在城市商業(yè)連鎖加盟店的物流配送中，存在客戶數(shù)量大、分布范圍廣以及客戶訂單不穩(wěn)定[8]等特點(diǎn)，傳統(tǒng)方法難以滿足實(shí)際的需求。針對(duì)以上問題，國(guó)內(nèi)外的學(xué)者也已經(jīng)做了較多的研究。其中，一些研究?jī)?nèi)容通過分階段求解的方式來縮小求解問題的規(guī)模，從而來優(yōu)化配送路徑。Liu 等人[9]提出了一種數(shù)學(xué)規(guī)劃模型及其相應(yīng)的圖論模型，并設(shè)計(jì)了一種兩階段貪婪算法來求解實(shí)際的大規(guī)模物流配送問題，從而最大限度的減少車輛空載運(yùn)行。?zdamar 等人[10]設(shè)計(jì)了一種多級(jí)聚類算法，將需求點(diǎn)分組為較小的集群，并在集群內(nèi)部進(jìn)行具體路徑的規(guī)劃，集群間互相獨(dú)立，從而得到較優(yōu)的路由方案。葛顯龍等人[11-12]提出網(wǎng)絡(luò)化跨區(qū)域分段聯(lián)運(yùn)的方法，設(shè)計(jì)了不同區(qū)域間的“多對(duì)多”網(wǎng)絡(luò)化聯(lián)合配送機(jī)制，打破了傳統(tǒng)的分級(jí)分區(qū)配送方式。黃鈺[13]結(jié)合客戶的需求和時(shí)間窗進(jìn)行客戶的區(qū)域劃分，設(shè)計(jì)了以油耗成本和車輛固定成本為優(yōu)化目標(biāo)的跨區(qū)域聯(lián)合配送模型，并利用改進(jìn)的遺傳算法進(jìn)行求解。另外，還有一些研究是通過優(yōu)化配送模型，設(shè)計(jì)更智能的優(yōu)化算法，以此進(jìn)行配送路徑的優(yōu)化。文獻(xiàn)[14-15]提出一種雙染色體的遺傳算法，通過爬山（HC）和模擬退火（SA）來提高解的表現(xiàn)，但相比于一條染色體編碼大大增加了解的空間，導(dǎo)致進(jìn)化速度緩慢。張慶華等人[16]通過改進(jìn)交叉算子，采用大變異操作來提高遺傳算法的搜索速度，但算法的復(fù)雜性隨之增加。郎茂祥等人[17]提出將爬山算法和遺傳算法相結(jié)合的方法來求解大規(guī)模物流配送問題，有效地避免了算法“早熟”和容易陷入局部最優(yōu)解的問題。

本文針對(duì)單物流中心多區(qū)域物流配送中存在的車輛路徑規(guī)劃不合理、裝載率不高的問題，提出了一種基于車輛配送線路的區(qū)域間協(xié)同配送方法。該方法通過配送區(qū)域間的空間關(guān)系，生成車輛途徑配送區(qū)域的配送線路。在此基礎(chǔ)上，依據(jù)配送區(qū)域內(nèi)訂單的分布情況和單一區(qū)域基于掃描-遺傳算法的配送方法，設(shè)計(jì)了沿配送線路的區(qū)域協(xié)同配送方法。最后，通過對(duì)比實(shí)驗(yàn)分析得出，本文所提出的方法，不僅可以減少總配送里程，同時(shí)減少了車輛的使用數(shù)量，提升了車輛的裝載率。

2 問題描述及建模

2.1 問題描述

一般的解決大規(guī)模物流配送問題，多是將一個(gè)范圍較大的服務(wù)區(qū)域劃分成若干個(gè)較小的子區(qū)域，然后分別在各子區(qū)域內(nèi)求最優(yōu)解。當(dāng)區(qū)域數(shù)量較少、區(qū)域內(nèi)的客戶訂單較穩(wěn)定時(shí)，這種方法能夠較好的滿足需求。但是，商業(yè)連鎖加盟店多區(qū)域配送是一個(gè)復(fù)雜的配送系統(tǒng)，其中區(qū)域的分布無規(guī)律、區(qū)域內(nèi)訂單客戶不穩(wěn)定。因此傳統(tǒng)的方法難以對(duì)其進(jìn)行有效的求解。

針對(duì)商業(yè)連鎖加盟店多區(qū)域的配送問題，本文提出了沿配送線路的區(qū)域協(xié)同配送方法，并構(gòu)建相應(yīng)的模型。模型需要滿足的具體內(nèi)容如下：

（1）僅有一個(gè)配送中心，是每條線路的起點(diǎn)和終點(diǎn)，車輛需從配送中心出發(fā)完成配送任務(wù)后最終返回配送中心。

（2）每條配送線路上的客戶的需求量之和不超過相應(yīng)配送車輛的最大裝載量。

（3）每條配送線路的總長(zhǎng)度不超過相應(yīng)配送車輛的最大行駛里程。

（4）每個(gè)客戶的貨物訂單只能被一輛車服務(wù)，且僅能被服務(wù)一次。

（5）區(qū)域內(nèi)的車輛不僅限于對(duì)本區(qū)域內(nèi)的客戶進(jìn)行服務(wù)，也可對(duì)其他區(qū)域內(nèi)的客戶進(jìn)行服務(wù)（區(qū)域協(xié)同配送）如圖1所示。

圖1 區(qū)域協(xié)同配送模型

2.2 建立模型

需要的符號(hào)和相關(guān)變量描述如下。

m：車輛數(shù)；

k：第k 輛車；

Qk：第k 輛車的最大裝載量；

Lk：第k 輛車的最大行駛里程；

i：第i 個(gè)客戶；

qi：第i 個(gè)客戶的貨物需求量；

dij：客戶i 到j(luò) 的距離；

N ：區(qū)域數(shù)；

I ：第I 個(gè)區(qū)域；

pI：第I 個(gè)區(qū)域內(nèi)的客戶數(shù)量；

cI：第I 個(gè)區(qū)域內(nèi)的車輛數(shù)；

則可以建立如下以總里程最短為目標(biāo)函數(shù)的數(shù)學(xué)模型：

其中，式（1）為以總里程最短的目標(biāo)函數(shù)，表示配送完成后所有車輛的行駛里程之和；式（2）為車輛的最大載重約束；式（3）為車輛的最大行駛里程約束；式（4）表示所有區(qū)域客戶總和；式（5）表示所有區(qū)域車輛總和；式（6）表示每個(gè)客戶只能被一輛車所服務(wù)，且所有的車輛都從配送中心出發(fā)完成配送任務(wù)后返回配送中心；式（7）和式（8）表示模型中變量xijk和yik之間的關(guān)系。

3 車輛配送線路的生成

3.1 線路規(guī)劃

本文將配送區(qū)域（單元區(qū)域）抽象成配送線路上的區(qū)域節(jié)點(diǎn)，用全連通圖G 來表示區(qū)域的連通情況如圖2所示。則令G={ }V,E ，其中V(G)={v0,v1,…,vN}為節(jié)點(diǎn)集，v0表示配送中心，vi(i ∈[1,N]) 表示區(qū)域節(jié)點(diǎn)，E(G)={e1,e2,…,eM}表示各線路節(jié)點(diǎn)間邊的集合，其中M 表示邊的條數(shù)。用空間區(qū)域拓?fù)溧徑有訹18]來反映單元區(qū)域間的4種鄰接關(guān)系如圖3。借鑒數(shù)據(jù)結(jié)構(gòu)中單鏈表（Single Linked List）的概念來表示配送線路。

圖2 線路區(qū)域節(jié)點(diǎn)結(jié)構(gòu)圖

圖3 單元區(qū)域鄰接關(guān)系圖

現(xiàn)進(jìn)行如下定義說明。

定義1 線路節(jié)點(diǎn)間距離：

其中，wvivj表示節(jié)點(diǎn)vi、vj的可達(dá)距離。

定義2 區(qū)域鄰接關(guān)系：遠(yuǎn)鄰區(qū)域、近鄰區(qū)域、左鄰區(qū)域和右鄰區(qū)域，分別為在不同方位上距離單元區(qū)域最近的區(qū)域。且每個(gè)單元區(qū)域的近鄰區(qū)域、左鄰區(qū)域和右鄰區(qū)域的個(gè)數(shù)均為0個(gè)或1個(gè)。

定義3 線路鏈表l ：以單元區(qū)域a1為線路的首節(jié)點(diǎn)，將其next 指針域指向a1的近鄰區(qū)域并以近鄰區(qū)域形成新的節(jié)點(diǎn)，繼續(xù)尋找新節(jié)點(diǎn)的近鄰區(qū)域，直到配送中心v0為止。表示為l={a1,a2,…,an,v0} ，其中ai∈V(i ∈[1,n])如圖4所示。

圖4 線路鏈表l 的表示方法

定義4 線路相鄰：若兩條線路中的某兩個(gè)區(qū)域節(jié)點(diǎn)互為左右相鄰的關(guān)系，則稱這兩條線路為相鄰線路。

3.2 生成協(xié)同配送網(wǎng)絡(luò)

協(xié)同配送網(wǎng)絡(luò)是由V(G)中的每個(gè)區(qū)域節(jié)點(diǎn)到配送中心的線路所鉤織出來的網(wǎng)絡(luò)。由線路鏈表的定義可知，生成從單元區(qū)域到配送中心的線路，關(guān)鍵在于找到每個(gè)單元區(qū)域的近鄰。步驟如下：

步驟1 根據(jù)單元區(qū)域的鄰接關(guān)系，找到V(G)中每個(gè)區(qū)域節(jié)點(diǎn)的近鄰區(qū)域。

步驟2 判斷當(dāng)前區(qū)域節(jié)點(diǎn)否是為V(G)中的最后一個(gè)，若是，則結(jié)束；若否，則轉(zhuǎn)向步驟3。

步驟3 根據(jù)線路鏈表的定義，以當(dāng)前區(qū)域節(jié)點(diǎn)vi為線路首節(jié)點(diǎn)，生成從vi到v0的線路l，并將生成的線路添加到配送網(wǎng)絡(luò)Γ 中，轉(zhuǎn)向步驟2。

由定義2可知，每個(gè)單元區(qū)域近鄰的個(gè)數(shù)至多只有一個(gè)，則對(duì)于生成的配送網(wǎng)絡(luò)Γ={l1,l2,…,lQ} ，有Q=N 。

3.3 生成初始線路

由于在每次的實(shí)際配送任務(wù)中，有貨區(qū)域的數(shù)量以及區(qū)域內(nèi)訂單的分布情況都不相同，所以在每次的任務(wù)中需要根據(jù)實(shí)際的配送需求，生成此次配送中的初始配送線路。步驟如下：

步驟1 找到此次配送任務(wù)中遠(yuǎn)鄰為空的單元區(qū)域，并將其設(shè)為邊緣區(qū)域。

步驟2 依據(jù)3.2 節(jié)生成的配送網(wǎng)絡(luò)，以及此次配送任務(wù)中的區(qū)域信息，生成從邊緣區(qū)域到配送中心的線路集合L={l1,l2,…,lm} ，此時(shí)線路中的區(qū)域節(jié)點(diǎn)均為此次配送中的有貨區(qū)域。

步驟3 將集合L 中的線路，按邊緣區(qū)域所在的位置順時(shí)針從左到右進(jìn)行排序，形成車輛的初始配送線路集合。

3.4 線路間調(diào)整

借鑒文獻(xiàn)[19]中“節(jié)約里程”的思想對(duì)具有相鄰關(guān)系的線路進(jìn)行如下調(diào)整，生成最優(yōu)的車輛途徑配送區(qū)域的線路集合。

（1）相鄰線路邊緣區(qū)域調(diào)整

舉例說明如圖5A，線路l1：a1,a2,…,an,v0和線路l2：b1,b2,…,bn,v0中的a1和b1互為左右相鄰關(guān)系并且存在Da1b1＜Da1a2||Da1b1＜Db1b2。若Da1a2＞Db1b2則調(diào)整后的線路為：a2,…,an,v0、a1,b1,…, bn,v0，如圖5B；若Da1a2＜Db1b2則調(diào)整后的線路為：b1,a1,…,an,v0、b2,…,bn,v0，如圖5C所示。

圖5 相鄰線路邊緣區(qū)域調(diào)整示意圖

（2）相鄰線路邊緣區(qū)域和途徑區(qū)域調(diào)整

舉例說明如圖6A，線路l1：a1,a2,…,an,v0和線路l2：b1,b2,…,bn,v0中的ai和b1互為左右相鄰關(guān)系并且存在Daib1＜Daiai-1||Daib1＜Db1b2。若Daiai-1＞Db1b2則調(diào)整后的線路為：ai-1,…,an,v0、a1,…,ai,b1,…,bn,v0，如圖6B；若Daiai-1＜Db1b2則調(diào)整后的線路為：a1,…,ai,b1,ai-1,…,an,v0、b2,…,bn,v0，如圖6C所示。

圖6 相鄰線路邊緣區(qū)域和途徑區(qū)域調(diào)整示意圖

4 配送方法

4.1 掃描-遺傳算法的配送方法

這里，選用掃描算法（Sweep Method）和遺傳算法（Genetic Algorithm）相結(jié)合的方法進(jìn)行單一區(qū)域內(nèi)的配送。

（1）確定區(qū)域掃描方向

舉例說明如圖7，當(dāng)進(jìn)行配送線路l 上的區(qū)域A 的配送時(shí)，則需根據(jù)線路l 上相對(duì)于當(dāng)前區(qū)域的下一個(gè)區(qū)域B來確定A的掃描方向。圖中區(qū)域A和B存在bc ＞ac&&bc ＞ad ，則區(qū)域A 的掃描方向?yàn)閺腷 到a，即從當(dāng)前區(qū)域相對(duì)于下一個(gè)區(qū)域的最遠(yuǎn)端開始掃描。

圖7 確定區(qū)域掃描方向示意圖

（2）掃描-遺傳算法

掃描算法是一種求解物流配送的啟發(fā)式算法，其基本原理為“先分組后線路”。其中，分組是指為每輛車分配送滿足其容量的客戶點(diǎn)。線路是指對(duì)每輛車所分配到的客戶點(diǎn)，采用插入算法、節(jié)約算法（Clarke-Wright）等方法進(jìn)行路徑規(guī)劃，本文采用的是文獻(xiàn)[17]中的遺傳算法，在此不再贅述。一種簡(jiǎn)單的分組設(shè)計(jì)步驟如下：

步驟1 以配送中心為原點(diǎn)，以區(qū)域邊緣客戶點(diǎn)為掃描起點(diǎn)。

步驟2 從原點(diǎn)向起點(diǎn)做射線，并按掃描方向繞原點(diǎn)進(jìn)行扇形掃描。

步驟3 記錄當(dāng)前掃描到的客戶需求qi，并把此次掃描過的客戶需求之和S 與當(dāng)前車輛可裝載容量V 進(jìn)行比較，若S ≤V ≤S+qi則終止此次掃描，把掃描過的需求量之和為S 的客戶分為一組，如圖8所示。

圖8 掃描分組方法

步驟4 重復(fù)上述步驟2 和3，直到所有的客戶都已分組。

4.2 區(qū)域協(xié)同配送方法

沿線區(qū)域協(xié)同配送是指，在每個(gè)單元區(qū)域內(nèi)，配送資源共享的前提下，從整體出發(fā)進(jìn)行區(qū)域間聯(lián)合配送，從而達(dá)到提高車輛裝載率、減少配送里程。具體有如下兩種情況。

（1）跨線路配送

根據(jù)預(yù)先計(jì)算出來的當(dāng)前線路中每輛車的裝載率，來判斷是否需要實(shí)施跨相鄰線路的配送。步驟如下：

步驟1 判斷當(dāng)前線路是否有相鄰線路，若是，則轉(zhuǎn)到步驟2；若否，則轉(zhuǎn)到步驟4。

步驟2 計(jì)算當(dāng)前線路上車輛的裝載率，判斷是否有車輛裝載率不滿足要求（一條線路中最多只可能有一輛車不滿足要求），若是，則轉(zhuǎn)到步驟3；若否，則轉(zhuǎn)到步驟4。

步驟3 跨線路配送，計(jì)算沒有裝滿的車輛上的已裝載量S1和空余量S2，找到當(dāng)前線路l1和相鄰線路l2上距離最近的兩個(gè)區(qū)域節(jié)點(diǎn)A和B。在區(qū)域A、B中，按掃描法將距離彼此最近的客戶分配到跨線路的車上，其中區(qū)域A和B裝載在跨線路車上的貨物量分別為S1、S2，如圖9所示。

圖9 跨線路配送示意圖

步驟4 不進(jìn)行跨線路配送，在當(dāng)前線路中，相對(duì)于配送中心從遠(yuǎn)到近，進(jìn)行沿配送線路的單元區(qū)域內(nèi)配送。

（2）沿線跨區(qū)域配送

在進(jìn)行沿配送線路單元區(qū)域內(nèi)的配送時(shí)，當(dāng)區(qū)域內(nèi)出現(xiàn)沒有達(dá)到裝載率要求的車輛，則讓該車輛沿線裝載下一個(gè)區(qū)域內(nèi)的客戶，如圖10 所示。為了保證下一個(gè)區(qū)域內(nèi)的客戶分布的完整性不被破壞，則將該區(qū)域內(nèi)的距離沒裝滿車輛最近一端的客戶，通過掃描法分配到該車輛上。

圖10 沿線跨區(qū)域配送示意圖

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)1

為驗(yàn)證模型和算法的有效性，利用“步步高”商業(yè)物流管理系統(tǒng)提供的實(shí)際配送數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。其中，配送車輛的額定體積為7.3 m3，裝載率的范圍為75%～85%，最大行駛里程為600 km。不同尺度下的具體配送數(shù)據(jù)如表1所示，其中，z 表示有貨區(qū)域的數(shù)量，n 表示區(qū)域客戶數(shù)量之和，w 表示所有客戶的貨物之和（單位m3）。仿真實(shí)驗(yàn)在Intel?Core?i5-6500 CPU@3.20 GHz處理器，8 GB內(nèi)存，Windows10 64位操作系統(tǒng)下采用jdk1.8.0的編程環(huán)境實(shí)現(xiàn)。

表1 實(shí)驗(yàn)配送數(shù)據(jù)

表2為在不同尺度下，生成的車輛途徑配送區(qū)域的線路（數(shù)字代表區(qū)域編號(hào)，如：340124）。

表2 車輛途徑區(qū)域的配送線路

在單一區(qū)域內(nèi)掃描-遺傳算法的基礎(chǔ)上，分別通過獨(dú)立配送模式（IS-G）與區(qū)域協(xié)同配送模式（CS-G）對(duì)實(shí)例進(jìn)行10 次求解，實(shí)驗(yàn)結(jié)果如表3，其中Best、Worst、Avg、Num和Load F分別代表10次求解中的最優(yōu)解、最差解、平均解、車輛的平均使用數(shù)量以及車輛的平均裝載率。

表3 不同尺度下兩種配送模式結(jié)果對(duì)比分析

表3中，在尺度S、M和L下的10次求解中，CS-G相比于IS-G，平均里程的公里數(shù)分別降低12.98%、17.32%和13.19%，車輛使用量分別減少2 輛、7 輛和6 輛，車輛的平均裝載率分別提升11.49%、18.93%和9.89%。從以上指標(biāo)的分析中可以看出，相比于獨(dú)立配送模式，區(qū)域協(xié)同配送模式在各方面都得到了優(yōu)化，不僅減少了車輛行駛的總里程，同時(shí)提升了車輛的裝載率，減少了車輛的使用數(shù)量，使得車輛資源使用的更加合理，并有效地減少了交通擁堵和環(huán)境污染。實(shí)驗(yàn)結(jié)果驗(yàn)證了基于車輛配送線路的區(qū)域協(xié)同配送方法，對(duì)于求解多區(qū)域物流配送的有效性和現(xiàn)實(shí)意義。

5.2 實(shí)驗(yàn)2

為進(jìn)一步驗(yàn)證本文所提出的掃描-遺傳算法在單一區(qū)域內(nèi)求解VRP 問題的有效性，選用標(biāo)準(zhǔn)遺傳算法（SGA）、禁忌搜索算法（TS）、蟻群算法（ACO）和掃描-遺傳算法（S-G），分別對(duì)同一區(qū)域內(nèi)的76個(gè)客戶進(jìn)行10次配送路徑的求解，實(shí)驗(yàn)結(jié)果如表4，其中Time為10次求解的平均耗時(shí)。

表4 實(shí)驗(yàn)結(jié)果對(duì)比分析

從表4可以看出，S-G在最優(yōu)解、最劣解和平均解這三個(gè)指標(biāo)上要遠(yuǎn)遠(yuǎn)優(yōu)于SGA和TS，在平均求解時(shí)間上，相比于這兩種算法雖然S-G的耗時(shí)最多，但也只是毫秒級(jí)的差別，是人們能夠接受的范圍。同算法ACO 的計(jì)算結(jié)果相比，S-G 在最優(yōu)解、最劣解和平均解的計(jì)算結(jié)果上，雖然只略優(yōu)于ACO 算法，但在平均耗時(shí)的指標(biāo)上，ACO 的耗時(shí)是S-G 的20 倍，且由于ACO 并行算法的本質(zhì)，在求解配送路徑時(shí)所消耗的資源遠(yuǎn)比其他算法要多。從實(shí)驗(yàn)結(jié)果可以看出本文所提的掃描-遺傳算法，對(duì)于求解VRP問題的有效性。

6 結(jié)束語

本文關(guān)注單物流中心大規(guī)模多區(qū)域的物流配送問題，有針對(duì)性地提出了一種基于車輛配送線路的區(qū)域協(xié)同配送方法。該方法利用配送區(qū)域間的空間關(guān)系生成區(qū)域協(xié)同配送網(wǎng)絡(luò)，進(jìn)而得到車輛配送線路。在此基礎(chǔ)上，依據(jù)配送區(qū)域內(nèi)訂單的分布情況和單一區(qū)域基于掃描-遺傳算法的配送方法，設(shè)計(jì)了沿配送線路的區(qū)域協(xié)同配送方法。最后，通過對(duì)比實(shí)驗(yàn)對(duì)算法和模型的有效性進(jìn)行了分析，在不同指標(biāo)上的計(jì)算結(jié)果顯示，本文方法取得了較滿意的效果。