最后一公里配送路徑優化研究

章雪巖，桂 欣，鄭巧然

（西南交通大學 交通運輸與物流學院，四川 成都 610031）

最后一公里配送路徑優化研究

章雪巖，桂 欣，鄭巧然

（西南交通大學 交通運輸與物流學院，四川 成都 610031）

根據最后一公里配送的業務特點，對最后一公里配送路徑優化問題進行了研究，建立了適合啟發式算法求解的配送優化模型，并結合遺傳算法的思想設計了算法。從模擬仿真的角度證明該方法對求解最后一公里配送的優化問題具有簡單可行、計算效率高、并行能力強、自動學習的特點。

最后一公里；配送路徑；路徑優化；遺傳算法；線上到線下

1 引言

近年來，由于電子商務O2O等模式的興起，使得最后一公里配送的研究變得熱門。O2O最難解決的就是“最后一公里問題”，也就是物流配送或者針對用戶在線下送貨上門服務。最后一公里配送從定義上來說，是指供應鏈中到最終顧客手中的最后一段短距離配送，并不是真正意義上的“最后一公里”，屬于電商平臺的線下部分[1]。由于在這一段配送過程中，處于供應鏈過程的末端，屬于零擔運輸，需求點多，貨物種類多，同時直接與客戶交互，提供給顧客服務，是供應鏈中最為復雜且最為重要的一環[2]。

結合電商平臺快遞配送、外賣配送等實際業務的考慮，客戶關注配送的等待時間，而配送員關注配送的成本[3]。在實際操作中，無論外賣還是電商快遞都是兩階段優化的。第一階段，根據客戶平均等待時間和訂單下達時間劃分不同快遞員配送的訂單；第二階段，不同的快遞員根據訂單的分布規劃自己的配送路線。在這兩階段中，其中第一階段一般由配送平臺根據數據挖掘結果結合平均服務時間進行安排。而第二階段目前還是依靠人工經驗。這兩階段都是服務質量和成本之間的均衡，但在第二階段往往因為人為因素導致不合理情況的出現，例如快遞員不合理配送導致顧客等待太長時間、運程增加等。因此，本文結合遺傳算法從車輛路徑問題（VRP，Vehicle Routing Problem）的角度對最后一公里配送的第二階段進行優化研究。

VRP是一個NP-hard問題，求解算法有精確算法和人工智能算法，在規模小且可求解情況下，精確算法優于人工智能算法[4]，但要在有限時間內找到大規模問題的滿意解、可行解，啟發式算法具有無與倫比的優勢[5]。我國目前使用最廣泛的電子商務物流配送模式是送貨上門模式，隨著碳排放研究、生鮮配送等O2O模式的開展，單純的對服務質量的研究開始轉為對配送效率和配送成本節約的研究。雖然最后一公里配送還有自助收發箱模式、顧客自提模式等，但其本質還是快遞員追求配送效率和顧客追求服務質量之間的矛盾。最后一公里在抽象為VRP問題時，通常有帶時間窗的車輛路徑問題（VRPTW）、容量限制的車輛路徑問題（CVRP）、需求可拆分的車輛路徑問題（SDVRP）等，但在實際中，最后一公里問題中諸如時間、服務對象等約束不是那么苛刻，更多是希望在提升效率的同時獲取顧客認同和快速求解的能力。因此本文從快遞員和客戶這兩個角度出發，結合容量限制提出了快速求解的CVRPGA算法。

2 最后一公里配送VRP模型

2.1 問題描述

一般來說，快遞員運載工具的貨物容量是有限的，且在最后一公里配送過程中，貨物種類繁多，其快遞包裝不統一，同時客戶簽收對快遞包裝有一定的要求，導致有限的運載容量難以充分利用；矛盾在于快遞員想盡量的縮短配送路徑，同時避免在某一地點停留太久，以縮短工作時間和提高服務效率。因此如何規劃自己的配送路線是快遞員最該考慮的問題。從線性規劃的角度來說，該問題的求解目標是快遞員行走的路徑最短，存在的約束條件有：

（1）快遞員駕駛以配送點作為起點和終點；

（2）每個配送點的需求必須得到滿足，一般來說配送點的需求不超過運載工具的容量Q；

（3）在每次快遞員接單過程中，其行程不超過L，以降低單次快遞配送中快遞平臺通知客戶收取包裹信息的牛鞭效應，使得客戶等待時間較少，維持一定的服務質量。

從上述分析可以看出，該規劃問題是一個典型的車輛能力約束的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）。最后一公里配送的CVRP問題可以描述如下：存在圖G=(V,E)，其中節點集合V={0,1,2,...,n}代表1個配送中心和n個需求點，邊的集合E={(i,j)|0≤i≠j≤n}代表任意兩節點形成的邊，邊長用dij表示。設快遞員駕駛容量為Q的車從配送中心出發回到配送中心，n個節點的需求量分別是q1,q2,...,qn，邊長dij和需求qi已知，且max(qi)≤Q。現在目標是快遞員可以多次往返配送中心，往返次數為m，滿足配送點的需求，但希望總路徑長度最短。

2.2 模型建立

通過上述分析可以得出，最后一公里配送的CVRP問題的數學規劃模型如下：

目標函數：

約束條件：

其中xijk為0,1變量，表示快遞員第k次服務的快遞點集合Vk，具體的：

式（1）為目標函數，表示快遞員一共m次所配送的總路徑長度；式（2）為每輛車單次配送的容量約束；式（3）為快遞員單次配送的距離約束（為保證服務質量）；式（4）、（5）表示快遞員只經過服務點一次；式（6）約束了所有車輛起始終點都在配送中心。

上述模型精確描述了最后一公里的CVRP問題,但不利于對遺傳算法執行細節的理解,從集合的角度將上述問題等價轉換如下[6]：

目標函數：

約束條件：

其中Vi、ni分別是第i次的路徑集合和路徑集合中經過配送點的數量。從式（8）-（12）可以看出，啟發式算法下CVRP模型的關鍵在于如何在既定條件下劃分快遞員的配送次數和配送順序，使得總路徑最短。

3 最后一公里配送的遺傳算法

3.1 遺傳算法原理

遺傳算法是基于生物進化提出的一種啟發式算法，通過模擬自然進化過程來進行最優解的搜索。遺傳算法認為最優解是最滿足適應度的種群中的最優個體，為了得到這個個體，一個種群的基因通過不斷的復制、組合交叉、變異適應新的環境，產生新的解。一般為了效率考慮，設定一個迭代上界，把末代種群中的最優個體經過解碼，作為求解問題的滿意解。其實現步驟如圖1所示。

圖1CVRPGA算法流程圖

遺傳算法從種群的角度考慮解的搜索，這種策略相比傳統優化算法而言，它從多個初始值開始迭代，覆蓋面廣，不易陷入局部最優解；同時對解的評價是通過適應度函數，面對搜索空間中的多個解進行評估，利于計算的并行化；從算法的思路來說，其本身是自組織、自適應和自學習性的，對復雜問題的求解具有很強的應變能力。為了促進遺傳算法的收斂，避免種群的早熟，就一般而言，遺傳算法的參數選取存在一定的經驗值[7]：

（1）種群規模。當種群規模太小時，會出現明顯的近親交配，產生病態基因，雖然可以采用較大概率的變異算子，但一般效果不明顯，且對已有模式的破壞作用極大。同時如果種群規模太大，結果難以收斂會浪費資源，穩健性下降，結合現有的研究，一般種群規模建議在100以內。

（2）變異概率。變異是遺傳算法中增加種群多樣性的一種方式。如果變異概率太小，種群多樣性下降會特別快，導致有效基因迅速丟失；如果變異概率太大，容易破壞高階模式。變異概率一般取0.000 1-0.2。

（3）交配概率。交配是生成新種群最重要的手段，與變異概率類似，交配概率太大容易破壞已有的有利模式，隨機性增大，易錯失最優個體；交配概率太小不能有效更新種群。交配概率一般取0.4-0.99。

（4）進化代數。遺傳算法是一個逐步優化的算法，需要一定的進化時間。進化代數太小，算法不容易收斂，種群沒有成熟；代數太大，會額外的浪費時間，一般進化代數取100-500。

（5）種群初始化。初始種群的生成是隨機的，但可以考慮在開始時對實際問題進行簡單分析，進行一個大概的區間估計，將解盡量靠近最優解的解集空間。

3.2 最后一公里配送優化算法設計

遺傳算法的關鍵在于初始種群的生成、基因編碼、適應度函數的設計、選擇算子、交叉算子的選擇和處理等。本文結合最后一公里配送的業務特點進行如下的選擇。

（1）基因編碼。基因編碼是在遺傳算法求解過程中，選擇合適的方法表示該問題的可行解。常用的編碼有二進制編碼、實數編碼、矩陣編碼和量子編碼等[8]。其編碼方式、優缺點和適用范圍存在不同的特點。最后一公里配送過程中，其配送點規模較大，實數編碼直接采用解空間的形式，無需特別解碼，且編碼意義直觀清楚。例如對于存在9個配送點的最后一公里配送的一個基因，其染色體（0,4,5,3,0,2,8,6,0,7,1,9,0）表示快遞員分三次完成9個配送點的配送任務，配送路線如圖2所示。

圖2 實數編碼的染色體（0表示配送中心）

（2）初始種群的生成。初始種群的生成一般采用隨機策略，本文利用matlab生成隨機的實數序列，根據容量約束確定配送員需要配送的次數，從最低次數開始調整，插入實數序列的0值，進行初始種群的生成。一般而言，可以運行多次，將上一次的結果作為輸入，提高效率。

（3）適應度函數設計。遺傳算法依據適應度函數的值來區分種群個體的優劣，適應度值大的個體有更多的機會繁衍后代。適應度函數在設計時要滿足單值、連續、非負、最大化的函數特性；在適應度函數曲線上，各點的優劣性成反比例，保證合理性、一致性；同時其計算量不能太大；且在一致問題上具有廣泛的通用性[8]。在上述準則下，設計最后一公里配送優化問題的適應度函數如下：

式（13）中的M為懲罰因子，一般取一個較大的實數。

（4）選擇算子。選擇算子是遺傳算法中根據個體的適應度對種群中的個體進行優勝劣汰操作的過程，使得適應度大的個體有較大的概率遺傳到下一代群體中。輪盤賭選擇方法是經典且成熟的選擇算子，采用回放式隨機抽樣的方式進行選擇，保證個體選中的概率與適應度成正比，采用輪盤賭選擇算子的最后一公里配送的基因選擇大致如下：

①計算配送路徑每個染色體xi的適應度值 f(xi)，i=1,2,...,N。

②計算每個配送路徑染色體編碼遺傳到下一代種群中的概率P(xi)。

③計算每個配送路徑染色體編碼的個體累計概率Ti。

④隨機產生一個（0,1]之間的隨機數r，根據q[k-1]＜r≤q[k]選擇路徑染色體編碼k。

（5）交叉算子。交叉是指把兩個父代個體部分結構進行重組形成新的個體，在最后一公里配送問題上，是指在兩個配送方案中，進行部分配送節點的調整，完成對方案的改進（如圖3所示）。

圖3 交叉算子示意圖

（6）變異算子。同交叉算子一樣，變異算子也是一種隨機進化后代的策略，在配送路徑上表現為單個配送方案的內部調整（如圖4所示）。

圖4 變異算子示意圖

（7）自適應過程。交叉概率Pc和變異概率Pm的選擇對遺傳算法的行為和性能都有一定的影響。結合對自適應遺傳算法AGA和改進的自適應遺傳算法IAGA的研究[10]，為了加快算法效率，提出以下據適應度對變異概率做出調整的方法。

式（16）、（17）的改進使得交叉概率和變異概率根據個體的適應度在平均適應度與最大適應度之間線性變換，采用精英保留策略，保證了每一代的優良個體不被破壞。

（8）迭代停止條件。在最后一公里配送問題的求解上，往往不在意取得算術上的最優解，而是快速的獲取相對經濟的配送方案。從這個思想出發，最后一公里配送優化的迭代停止條件考慮如下：

①從種群進化穩定性出發，設置一個ε，當種群進化出現max(f(xi))-averg(f(xi))≤ε就停止迭代。

②設置一個最大迭代次數，一般根據問題求解的經驗取得，在不滿足種群穩定性的條件下，為了算法效率，迭代到最大迭代次數時取其為滿意解。

4 實例應用

在某個電子商務平臺的運營過程中，一快遞員一共接到12個收貨點的訂單，快遞員單次可攜帶的最大重量為20個單位，其中配送中心在快遞員取包裹時短信通知客戶，為了保證較少的客戶等待時間和對快遞員效率的監控，一般每次給快遞員的包裹配送總行程不超過35個單位，以配送中心為（0,0）建立坐標，各配送點的坐標和配送量見表1。

表1 各節點數據

利用式（1）-（7）的線性規劃模型，結合lingo軟件精確求解得最優的配送總路程為78.52，一共配送4次，迭代4 249次，平均耗時2.12s，子路徑見表2。

表2 lingo精確求解結果

結合式（8）-（12）的CVRPGA問題，利用matlab實現算法，其相關參數設置為：種群規模N=100，懲罰因子M=100 000，最大遺傳代數G=200,初始交叉概率Pc=0.9，初始變異概率Pm=0.1，ε為10-5。隨機求解100次，平均耗時3.34s，求解結果的懲罰因子值如圖5所示；隨機抽取100次結果的10個解，見表3；改變點的規模，求解平均耗時如圖6所示。

圖5 隨機求解100次結果

表3CVRPGA算法的滿意解

從圖5和表2可以看出，在隨機100次求解情況下，有效解為92個，滿意解個體也足夠優秀，能夠找到問題的解；結合圖6的耗時比較，可以看出CVRPGA算法耗時經濟。因此在求解最后一公里配送路徑優化問題時，CVRPGA能夠有效得到滿意解，滿足O2O條件下的急速配送需求。

圖6 不同規模下的求解耗時

5 結語

從上述分析可以看出，在求解最后一公里配送優化問題上，CVRPGA算法具有適應度強，并行化程度高，收斂速度快的特點。在快速求解滿意解的角度上，該算法為解決最后一公里配送問題提供了新的思路，是解決O2O難題的一種新方法。

[1]詹斌,谷孜琪,李陽.“互聯網+”背景下電商物流“最后一公里”配送模式優化研究[J].物流技術,2016,(1)：1-4.

[2]楊巖.我國電商物流最后一公里配送問題研究[J].物流工程與管理,2014,(10)：90-91.

[3]黃驗然,吳光先.電子商務最后一公里配送的收貨模式研究[J].嘉應學院學報,2014,(4)：37-41.

[4]賈楠,呂永波,付蓬勃,等.物流配送問題中VRP的數學模型及其求解算法[J].物流技術,2007,(4)：54-56.

[5]史玉敏.物流配送環節中車輛路徑問題（VRP）的研究[D].濟南：山東師范大學,2007.

[6]饒衛振,金淳.求解大規模CVRP問題的快速貪婪算法[J].管理工程學報,2014,(2)：45-54.

[7]卓金武.MATLAB在數據建模中的應用[M].北京：北京航空航天出版社,2011.

[8]張超群,鄭建國,錢潔.遺傳算法編碼方案比較[J].計算機應用研究,2011,(3)：819-822.

[9]劉英.遺傳算法中適應度函數的研究[J].蘭州工業高等專科學校學報,2006,(3)：1-4.

[10]李欣.自適應遺傳算法的改進與研究[D].南京：南京信息工程大學,2008.

Study on Route Optimization in Last-mile Distribution

Zhang Xueyan,Gui Xin,Zheng Qiaoran
(School of Transportation&Logistics,Southwest Jiaotong University,Chengdu 610031,China)

In this paper,according to the operational characteristics of the last-mile distribution,we studied the route optimization in the last-mile distribution process,built the distribution optimization model that can be solved using the heuristic algorithm and then based on the genetic algorithm,designed an effective solution to the model.From the angle of simulation,we proved the convenience,feasibility,high efficiency and other superiorities of the method in solving the optimization issues in the last-mile distribution.

last mile;distribution route;route optimization;genetic algorithm;online to offline

F224.0；F252.14

A

1005-152X(2017)06-0116-06

10.3969/j.issn.1005-152X.2017.06.027

2017-05-06

章雪巖（1957-），男，西南交通大學教授，研究生導師，管理學博士，研究方向：物流信息化、供應鏈管理；桂欣，男，西南交通大學物流工程專業研究生；鄭巧然，女，西南交通大學物流工程專業研究生。