肖正中，譚建，周玉峰，曾俊

1 貴州省煙草公司黔東南州公司，貴州凱里，556000；

2 貴州財經(jīng)大學，貴州貴陽，550003

跨區(qū)域多配送中心車輛調度智能優(yōu)化研究

肖正中1，譚建2，周玉峰1，曾俊1

1 貴州省煙草公司黔東南州公司，貴州凱里，556000；

2 貴州財經(jīng)大學，貴州貴陽，550003

跨區(qū)域多配送中心車輛調度是一個典型的NP難題，是當前運籌學領域的一個研究熱點。本文采用邊界分配法將該問題轉化為單配送中心車輛調度問題，并結合遺傳算法與蟻群算法求解跨區(qū)域配送最優(yōu)調度方案。以貴州省黔東南州煙草公司物流中心卷煙配送為背景進行了仿真分析，結果表明了算法的有效性。

車輛調度；邊界分配法；遺傳算法；啟發(fā)式算法

21世紀電子商務的蓬勃發(fā)展為物流行業(yè)帶來了新的機遇和挑戰(zhàn)[1]。由于客戶數(shù)量巨大，貨物需求量和配送時間要求的多樣性，在車輛載重、車輛最大行駛距離等方面的約束，使得當前物流問題變得非常復雜，亟需對物流問題建模并研究準確高效的求解算法。

現(xiàn)代物流體系建設主要涉及配送中心選址與配送車輛調度[2]。配送車輛調度是物流系統(tǒng)的關鍵環(huán)節(jié)，在配送時間、貨物需求量、配送中心車輛數(shù)目、車輛載重和車輛最長運載里程等限制下，采用某種算法得到最優(yōu)配送路線[3]。依據(jù)配送中心數(shù)目的多少，可將配送車輛調度問題劃分為單配送和多配送中心車輛調度問題。在一個物流體系中往往存在多個配送中心共同協(xié)作配送特定區(qū)域內客戶。

跨區(qū)域多配送中心車輛調度是針對各配送中心所劃定的配送區(qū)域進行綜合車輛調度，是一個NP難題[4]，隨著配送中心數(shù)目及客戶數(shù)目的增加，候選的配送方案數(shù)量以指數(shù)形式增加。因此，尋找合適的算法快速準確找到配送方案問題的全局最優(yōu)解是該問題的研究重點。目前很多文獻對多配送中心車輛調度問題進行了研究[5-6]，研究集中在兩個方面，一是采用一定的客戶分配方法將多配送中心問題轉換為單配送中心問題，二是設計算法解決單配送中心車輛調度問題。王征等（2013）以顧客時間窗偏離程度最小化和配送成本最小化為目標,在Solomon提出的標準算例上建立了問題的數(shù)學模型及其求解算法[7]。馬宇紅等（2013）針對大規(guī)模的多配送中心多車型車輛調度問題提出了一種新的多片段染色體混合編碼算法[8]。殷脂和葉春明（2014）提出了采用聚類分析最短距離分配法將多配送中心車輛調度問題動態(tài)地分解為多個單配送中心車輛調度問題進行求解的策略[9]。孫壯志等（2014）采用中心聚類、禁忌搜索、局部搜索等多種專業(yè)算法研究了卷煙配送調度問題[10]。楊珍花等（2015）采用混合模擬退火算法分析了冷藏車多車型混合配送調度優(yōu)化[11]。

本文針對多配送中心車輛調度問題，首先采用邊界分配法將多配送中心車輛調度問題轉化為單配送中心車輛調度問題，其次將單配送中心車輛調度問題分解為車輛分配與單車輛路線優(yōu)劃兩個互相關聯(lián)的子問題，并結合遺傳算法和蟻群算法求解。邊界分配法是將客戶分為邊界點位置客戶和非邊界點位置客戶，非邊界點位置客戶根據(jù)最近分配原則分配，邊界點位置客戶的分配由最大節(jié)約距離確定。遺傳算法是模擬群體的個體按照它們對環(huán)境適應度實現(xiàn)優(yōu)勝劣汰的進化過程。蟻群算法是模擬螞蟻覓食行為的優(yōu)化算法，采用分布式正反饋并行計算機制尋找最優(yōu)路徑，易與其他方法結合，且具有較強的魯棒性。

本文創(chuàng)新點體現(xiàn)在兩個方面：（1）提出了配送中心-客戶距離關系矩陣，研究了該矩陣的對稱性等基本性質，并將路線長度、載重量計算等轉換為矩陣運算，使得優(yōu)化目標和約束條件的表述更加清晰嚴格；（2）采用邊界分配法結合遺傳算法、蟻群算法對多配送中心車輛調度問題進行求解，并根據(jù)黔東南州煙草公司物流配送中心調動數(shù)據(jù)進行仿真驗證，仿真結果說明了算法的有效性。

1 多配送中心車輛調度問題數(shù)學模型

多配送中心車輛調度模型中，配送中心表示為集合P={p1，p2，…，pm}，客戶表示為集合Q={q1，q2，…，qn}，且m＞1，n＞1。客戶的貨物需求量表示為集合R={r1，r2，…，rn}，其中ri表示客戶qi的需求量。車輛調度問題中一個重要輸入?yún)?shù)是配送中心與客戶相對距離，該參數(shù)直接影響到最佳調度路線的分配。為準確描述配送中心與客戶的相對距離，本文提出距離關系矩陣：

其中，dx,y表示位置x到位置y的實際最短貨運距離，dx,y會隨道路維修等實際情況變動，因此具有時間相關性，但考慮到這種變動情況很緩慢且離散，單次配送路線規(guī)劃中假定dx,y是常量。當兩地之間最短貨運距離不確定時，dx,y也可用球面距離代替。關于距離關系矩陣有如下兩個結論：

（1）dx,x=0，即同一位置之間的距離為0；

（2）D=DT，即地點x與地點y的距離等于地點y與地點x之間的距離。單向道路可能會導致dx,y≠dy,x，考慮到這種影響很小，本文假定dx,y=dy,x。

利用矩陣D可計算配送路徑的行駛距離。例如某一運輸車從配送中心p1出發(fā)，先送貨到客戶q1，再送貨到客戶q2，然后回到配送中心p1。將其配送路線簡記為L=p1→q1→q2→p1，則該路線的總距離為d（L）=dp1,q1+dq1,q2+dq2,p1。由于每輛運輸車均是從某一配送中心出發(fā)，經(jīng)過若干客戶后回到原配送中心，所以配送路線L在拓撲學上是一個簡單環(huán)。記QL為路線L上的客戶集合，例如Qp1→q1→q2→p1={q1,q2}。在每個客戶的貨物僅由一個車輛配送的前提下，任兩個配送路線QL的交集應為空集。每條配送路線上運輸車總載重量G(L)為該路線途徑的客戶的需求量總和，例如G(p1→q1→q2→p1)=r1+r2。實際問題中，存在車輛載重量和單次最大行駛距離的限制，即d(L)≤dup，G(L)≤Gup，其中，dup表示一次配送最大行駛距離，Gup表示車輛最大載重量。由于配送產(chǎn)品均為卷煙，其體積與重量基本呈正比，因此，本文只考慮車輛最大載重量。

總配送成本包含很多方面，如車輛油耗、車輛損耗、人工成本，時間成本等等?？偝杀敬笾屡c車輛總行駛里程成正比，可假設比例系數(shù)為常數(shù)k，此時多配送中心車輛調度問題的優(yōu)化目標即為總配送成本最小。綜上得到車輛調度問題的數(shù)學模型為：

其中，四個約束條件分別為：（1）最大行駛距離約束；（2）載重約束；（3）每個客戶僅由一臺車輛送貨；（4）所有客戶需求全部滿足。該優(yōu)化問題可分為兩步求解。步驟一：為每位客戶分配一個配送中心負責為其運貨；步驟二：每個配送中心選擇最優(yōu)的車輛數(shù)以及配貨路線完成配貨。若采用窮舉法則第一步的問題復雜度為O(mn)，第二步是m個相互獨立的單配送中心車輛調度問題，該問題具有NP復雜度。鑒于問題的復雜度，每個步驟均需采用一定的算法快速求解。下文分別用邊界分配法和遺傳算法解決步驟一與步驟二。

2 客戶分配方法

2.1 最近距離分配法

步驟一可看做一個聚類問題，聚類中心為配送中心，聚類目的是將每個客戶按一定標準分配給某一配送中心。最簡單的標準將客戶歸類到與其距離最近的配送中心，該方法已經(jīng)在部分文獻中使用[6-7]。但該聚類方式在某些情形下不合理，例如某一地區(qū)包含兩個配送中心和兩個客戶，坐標分別為p1∶(2，2)，p2∶(6，2)，q1∶(3，5)，q2∶(5，5)，如圖1 所示。

圖1配送路線比較Fig.1 Distribution route comparison

配送路線一的總運輸距離為：dis1=Dp1→q1→p1+Dp2→q2→p2=dp1,q1+dq1,p1+dp2,q2+dq2,p2=12.64

配送路線二的總運輸距離為：dis2=Dp1→q2→p1=dp1,q1+dq1,q2+dq2,p1=9.4

當采用最近距離分配法時，得到配送路線一，這種配送方案顯然不如配送方案二。最近距離分配法僅考慮了配送中心與客戶之間的距離，而未考慮客戶之間的距離。

2.2 邊界分配法

采用邊界分配法分配客戶時包含兩個過程：首先確定邊界點，其次是計算最大節(jié)約距離，并將邊界點分配給最大節(jié)約距離對應的配送中心。取矩陣D的左下子塊并記為M，即

將矩陣M的第i行記為Mi，則Mi表示客戶qi到各配送中心之間的距離。記min（Mi）為Mi中最小的元素值；記submin（Mi）為Mi中次小的元素值。取一個臨界值σ，σ∈[0，1]。當min（Mi）/submin（Mi）＜σ時，將客戶i分配給min（Mi）相應的分配中心；當 min（Mi）/submin（Mi）＞=σ時，將客戶i標記為邊界點。按照下述步驟為邊界點分配配送中心，記

則Spi（qk）表示當邊界點qk分配給配送中心pi時所能節(jié)約的配送距離。則表示分配邊界點qk后所能節(jié)約的最大配送距離。將邊界點qk分配給對應的pi。

臨界值σ取值會影響到邊界點的分配。當σ=1時，任何客戶均按照最近距離分配，邊界分配法退化為最近距離分配法；當σ=0時，任何客戶均是臨界點。邊界分配法既考慮到了配送中心與客戶之間的距離，又考慮到了客戶與客戶之間的距離，因此更加合理。

3 車輛選擇與線路優(yōu)化算法

3.1 基于遺傳算法的車輛分配方案

邊界分配法分配客戶之后，多配送中心車輛調度問題轉換為單配送中心車輛調度問題。單配送中心車輛調度問題可拆分為車輛選擇和路線優(yōu)化兩個相互關聯(lián)的子問題。車輛選擇是單配送中心車輛調度問題的核心，可采用遺傳算法解決[12-13]，其流程如圖2所示。

圖2 遺傳算法流程圖Fig.2 Flow chart of genetic algorithm

該矩陣表示將五個客戶分配給三臺車輛的一個方案，其中第一和第三個客戶分配給第一輛車；第二和第五個客戶分配給第二臺車；第四個客戶分配給第三臺車。

適應度函數(shù)定義。適應度函數(shù)用于評價遺傳算法中每個個體編碼的好壞，適應度較高的個體優(yōu)先遺傳到下一代。車輛配送方案的總行駛里程越低，其相應染色體的適應度越高。因此將總行駛里程的倒數(shù)作為適應度函數(shù)。

生成初始種群。根據(jù)車輛數(shù)和客戶數(shù)隨機生成N個矩陣C作為初始種群G0={C1,C2,…,CN}，種群中的每個個體必須滿足最大行駛距離限制和最大載重量限制，否則將該個體淘汰并隨機產(chǎn)生新的個體直到滿足限制條件為止。

種群選擇與復制。種群中的個體以一定概率進行選擇與復制，每個個體的選擇概率與其適應度成正比。概率選擇機制確保了優(yōu)秀個體有更大機會遺傳到下一代。

交叉操作。種群的選擇復制本質上不產(chǎn)生新的個體，即新的車輛分配方案。因此，經(jīng)種群選擇與復制操作后，雖然種群的平均適應度上升了，但其適應度的上限并沒有升高。交叉操作以一定概率隨機交換種群中兩個個體的某些片段，由此產(chǎn)生一些新的個體。交叉操作有利于提升種群適應度上限，從而得到更合理的配送方案。

變異。變異操作隨機對個體中的某些基因座的值作變動，即對矩陣C的某些列中1的位置進行變換。遺傳算法中，交叉算子具有全局搜索能力，而變異算子具有局部搜索能力，兩者相輔相成促進遺傳算法得到全局最優(yōu)解。

終止規(guī)則。當兩次迭代過程得到的群體適應度上限相差很小或達到迭代次數(shù)上限時停止迭代，選擇最大適應度對應的分配方案作為最終車輛分配方案。

3.2 基于蟻群算法的車輛路線優(yōu)化

車輛路線安排問題實質上是一個旅行商問題（TSP），當車輛分配方案確定時，車輛路線優(yōu)化可用蟻群算法解決[14]。假設車輛所屬配送中心的坐標為（0，0），隨機生成20個客戶。采用的蟻群算法基本參數(shù)如表1所示。

蟻群算法是一種進化算法，螞蟻個數(shù)越多，算法搜索的路徑越多，得到的解越精確，但是蟻群越大計算復雜度也越大。信息素重要程度體現(xiàn)了已知信息對螞蟻路徑選擇的重要程度，該值越大蟻群運動軌跡的隨機性也就越弱。啟發(fā)式因子的重要程度則會影響蟻群尋找路徑時的先驗性，該值越大螞蟻越容易選擇局部最優(yōu)路徑。信息素蒸發(fā)系數(shù)對算法收斂速度有很大影響。信息素增加強度系數(shù)表示螞蟻釋放信息量的大小，該系數(shù)越大算法收斂性越強，同時也更容易陷入局部最優(yōu)解。

表1 蟻群算法基本參數(shù)Tab.1 basic parameters of ant colony algorithm

利用蟻群算法得最短路徑為：2-16-9-17-7-1-15-20-10-13-8-14-3-19-12-6-5-11-18-4，最短路徑距離為95.0333，路線圖以及收斂曲線如圖3所示。

圖3 基于蟻群算法的路線圖及收斂曲線Fig.3 route map and convergence curve based on ant colony algorithm

4 仿真分析

4.1 參數(shù)設置

本節(jié)以黔東南州煙草公司物流配送為例做仿真分析。該公司共有六個配送站，以東經(jīng)107度北緯25度為原點，在橫坐標[50,250]縱坐標[50,250]的矩形區(qū)域內隨機產(chǎn)生50個點代表相應客戶位置。每個點與最近鄰的配送站的距離小于60km。配送中心以及客戶位置如圖4所示，中小矩形代表配送中心，小圓形代表客戶。不同的配送中心以不同顏色區(qū)分。模型參數(shù)設置如下：每個配送中心的車輛數(shù)目為4，每輛車最大載重量dup=8噸，每輛車的最大行駛距離Gup=120km，每個客戶的貨物需求量在1噸至2噸之間隨機生成。

圖4 配送中心以及隨機產(chǎn)生的客戶位置圖Fig.4 Distribution center and the random generation of customer location map

4.2 分配客戶

分別用最近距離法和邊界分配法分配客戶，分配結果如圖5和圖6所示。為清晰地表示分配結果，客戶的顏色用分配中心所屬的顏色標記。

圖5 最近距離法分配客戶Fig.5 Nearest distance distribution method

圖6 邊界分配法Fig.6 Boundary distribution method

對比圖5和圖6可知，不同的客戶分配方法會產(chǎn)生不同的分配結果。最近距離分配法將客戶分配給距離最近的配送中心，這種配送方法可能將大量不同方位的客戶分配到同一配送中心，而邊界分配法傾向于將“成簇”的客戶分配到同一配送中心。

4.3 計算最佳配送方案

本文采用遺傳算法和蟻群算法對六個配送中心計算其最佳配送方案，限于篇幅僅展示黎平配送中心的配送方案和從江配送中心的配送方案，分別如圖6和圖7所示。圖6中黎平配送中心負責6個客戶的貨物配送，由兩輛車完成，其中一輛車負責西北方向的三個客戶，另一輛車負責東南方向的三個客戶；圖7中從江配送中心負責七個客戶的貨物配送，同樣由兩輛車完成，其中一輛車負責西面的4個客戶，另外一輛車負責東面的三個客戶。

圖7 黎平車輛調度路線圖Fig.7 Liping vehicle routing map

圖8 從江車輛調度路線圖Fig.8 Congjiang vehicle routing map

作為對比，本文采用窮舉法求解黎平和從江配送中心的配送路線。含有m輛車，n個客戶的配送中心，其客戶分配方案總共有mn種，每輛車的行駛路線數(shù)為k!，其中k為該車輛負責的客戶數(shù)目。窮取法可以評價所有可能的配送方案從而得到最優(yōu)解。但當m和n數(shù)值較大時，窮舉法計算上難以實現(xiàn)。而結合遺傳算法及蟻群算法求解黎平和從江配送中心的配送方案，得到與窮舉法同樣的解（正向與反向的路線配送長度相同，可看作相同方案），但同等計算機配置下耗時僅為窮舉法的百分之一。該對比說明結合遺傳算法及蟻群算法應用于求解配送方案是一種準確高效的方法。

為研究算法的收斂性與有效性，論文模擬了包含3輛車、12個客戶的運輸調度問題，結合遺傳算法及蟻群算法中隨機選取初始種群重復100次實驗，在其中85次實驗中該算法均得到與窮舉法相同的配送方案，即收斂到全局最優(yōu)解，而在其余15次實驗中收斂到局部最優(yōu)解。這說明遺傳算法及蟻群算法的結合有很大概率得到全局最優(yōu)解，是一種有效的方法。

5 總結與展望

本文采用邊界分配法將多分配中心車輛調度問題轉化為單分配中心車輛調度問題，并將單分配中心車輛調度問題分解為車輛選擇與單車輛路線規(guī)劃兩個互相關聯(lián)的子問題，分別用遺傳算法和蟻群算法求解。問題的轉化和分解提高了求解速度，有利于解決大規(guī)模跨區(qū)域倉儲配送問題。客戶分配方法對后續(xù)的車輛路線規(guī)劃結果有很大影響，邊界分配法相比于最近距離分配法更加合理，然而更有效的客戶分配法有待后續(xù)研究。

[1]郇青.電子商務物流發(fā)展模式研究[D].山東大學, 2012.HUAN Qing.E-commerce logistics development model [D].Shandong University, 2012.

[2]張培林, 魏巧云.物流配送中心選址模型及其啟發(fā)式算法[J].交通運輸工程學報, 2003, 3(02):65-68.ZHANG Peilin, WEI Qiaoyun.Model of logistics distribution center location model and its heuristic algorithm [J].Journal of Traf fi c and Transportation Engineering, 2003, 3 (02): 65-68.

[3]劉云忠, 宣慧玉.車輛路徑問題的模型及算法研究綜述[J].管理工程學報, 2005, 19(01):124-130.LIU Yunzhong, XUAN Huiyu.Research on model and algorithm of vehicle routing problem [J].Journal of Management Engineering,2005, 19 (01): 124-130.

[4]Bogdanovi? M.Overview of some solved NP-complete problems in graph theory[J].Advances and Applications in Mathematical Science, 2011, 9(1):35-45.

[5]施朝春, 王旭, 葛顯龍.帶有時間窗的多配送中心車輛調度問題研究[J].計算機工程與應用, 2009, 45(34):21-24.SHI Zhaochun, WANG Xu, GE Xianlong.Vehicle routing problem with time windows in multiple distribution centers [J].Computer Engineering and Applications, 2009, 45 (34): 21-24.

[6]邢鵬.基于云平臺的多配送中心車輛調度問題研究[D].北京交通大學, 2013.XING Peng.Study on vehicle scheduling problem of multi distribution center based on cloud platform [D].Beijing Jiaotong University, 2013.

[7]王征,胡祥培,王旭坪.行駛時間延遲下配送車輛調度的干擾管理模型與算法[J].系統(tǒng)工程理論與實踐,2013,33(2):378-387.WANG Zheng, HU Xiangpei, WANG Xuping.Disturbance management model and algorithm for distribution vehicle scheduling with time delay [J].System Engineering Theory and Practice, 2013,33(2):378-387.

[8]馬宇紅,姚婷婷,張浩慶.基于分區(qū)的多配送中心多車型車輛調度問題與遺傳算法設計[J].科技導報,2013,(2):61-67.MA Yuhong, YAO Tingting, ZHANG Haoqing.Multi vehicle scheduling problem and genetic algorithm design based on partition of multi distribution centers [J].Technology review, 2013,(2):61-67.

[9]殷脂,葉春明.多配送中心物流配送車輛調度問題的分層算法模型[J].系統(tǒng)管理學報,2014,(4):602-606.YIN Zhi, YE Chunming.Hierarchical algorithm model of logistics distribution vehicle scheduling problem of multi distribution center[J].Journal of Systems Management, 2014,(4):602-606.

[10]孫壯志,鄢烈虎,要學瑋.基于線路優(yōu)化算法的卷煙配送調度系統(tǒng)[J].中國煙草學報,2014,(5):128-133.SUN Zhuangzhi, YAN Liehu, YAO Xuewei.Cigarette distribution scheduling system based on line optimization algorithm[J].Chinese Journal of Tobacco, 2014,(5):128-133.

[11]楊珍花,賴平仲,湯洋等.冷藏車多車型混合配送調度優(yōu)化[J].系統(tǒng)工程,2015,(10):28-36.Yang Zhenhua, Lai Pingzhong, Tang Yang, et al.Multi vehicle type mixed refrigerated vehicle distribution scheduling optimization [J].System Engineering, 2015,(10):28-36.

[12]Bayley D J, Hart fi eld R J, Burkhalter J E, et al.Design Optimization of a Space Launch Vehicle Using a Genetic Algorithm[J].Journal of Spacecraft & Rockets, 2015, 45(4):733-740.

[13]Gage P J, Kroo I M, Sobieski I P.Variable-complexity genetic algorithm for topological design[J].Aiaa Journal, 2015,33(11):2212-2217.

[14]許爭爭, 唐加福.基于協(xié)作的三階段啟發(fā)式算法求解多行程車輛行程問題[J].南開大學學報(自然科學版), 2015,(5):51-59.XU Zhengzheng, TANG Jafu.Three stage heuristic algorithm for solving multi stroke vehicle routing problem [J].Journal of Nankai University (NATURAL SCIENCE EDITION), 2015, (5): 51-59.

Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers

XIAO Zhengzhong1, TAN Jian2*, ZHOU Yufeng1, ZENG Jun1
1 Guizhou Provincial Tobacco Company Qiandongnan Branch, Kaili, Guizhou 556000, China
2 Guizhou University of Finance and Economics, Guiyang 550003, China

Trans-regional vehicle scheduling among multiple distribution centers is a typical NP issue.Boundary distribution method was applied to transform this issue into the issue of vehicle scheduling in single distribution center.An optimal scheduling scheme was then obtained through genetic algorithm combined with ant colony optimization.Simulation analysis was carried out using logistics data of Qiandongnan Tobacco Company in Guizhou province.Results of the analysis proved that the method is valid and ef fi cient.

vehicle scheduling; boundary distribution; genetic algorithm; ant colony optimization

肖正中，譚建，周玉峰，等.跨區(qū)域多配送中心車輛調度智能優(yōu)化研究[J].中國煙草學報，2017, 23（4）

肖正中(1977—)，碩士，經(jīng)濟師，煙草供應鏈管理，Email：gzxiaozz@163.com

譚 建(1982—)，博士，副教授，煙草供應鏈管理，Email：tanjian123@126.com

2016-08-23；< class="emphasis_bold">網(wǎng)絡出版日期：

日期：2017-03-06

：XIAO Zhengzhong, TAN Jian, ZHOU Yufeng,et al.Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers [J].Acta Tabacaria Sinica, 2017, 23(4)

*Corresponding author.Email：tanjian123@126.com