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

1.湖南科技大學 計算機科學與工程學院，湖南 湘潭411201

2.知識處理與網絡化制造湖南省教育廳重點實驗室，湖南 湘潭411201

1 引言

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

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

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

2 問題描述及建模

2.1 問題描述

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

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

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

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

（3）每條配送線路的總長度不超過相應配送車輛的最大行駛里程。

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

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

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

2.2 建立模型

需要的符號和相關變量描述如下。

m：車輛數；

k：第k 輛車；

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

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

i：第i 個客戶；

qi：第i 個客戶的貨物需求量；

dij：客戶i 到j 的距離；

N ：區(qū)域數；

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

pI：第I 個區(qū)域內的客戶數量；

cI：第I 個區(qū)域內的車輛數；

則可以建立如下以總里程最短為目標函數的數學模型：

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

3 車輛配送線路的生成

3.1 線路規(guī)劃

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

圖2 線路區(qū)域節(jié)點結構圖

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

現進行如下定義說明。

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

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

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

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

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

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

3.2 生成協同配送網絡

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

步驟1 根據單元區(qū)域的鄰接關系，找到V(G)中每個區(qū)域節(jié)點的近鄰區(qū)域。

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

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

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

3.3 生成初始線路

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

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

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

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

3.4 線路間調整

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

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

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

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

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

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

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

4 配送方法

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

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

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

舉例說明如圖7，當進行配送線路l 上的區(qū)域A 的配送時，則需根據線路l 上相對于當前區(qū)域的下一個區(qū)域B來確定A的掃描方向。圖中區(qū)域A和B存在bc ＞ac&&bc ＞ad ，則區(qū)域A 的掃描方向為從b 到a，即從當前區(qū)域相對于下一個區(qū)域的最遠端開始掃描。

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

（2）掃描-遺傳算法

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

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

步驟2 從原點向起點做射線，并按掃描方向繞原點進行扇形掃描。

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

圖8 掃描分組方法

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

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

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

（1）跨線路配送

根據預先計算出來的當前線路中每輛車的裝載率，來判斷是否需要實施跨相鄰線路的配送。步驟如下：

步驟1 判斷當前線路是否有相鄰線路，若是，則轉到步驟2；若否，則轉到步驟4。

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

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

圖9 跨線路配送示意圖

步驟4 不進行跨線路配送，在當前線路中，相對于配送中心從遠到近，進行沿配送線路的單元區(qū)域內配送。

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

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

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

5 實驗與分析

5.1 實驗1

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

表1 實驗配送數據

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

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

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

表3 不同尺度下兩種配送模式結果對比分析

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

5.2 實驗2

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

表4 實驗結果對比分析

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

6 結束語

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