章雪巖，桂 欣，鄭巧然

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

最后一公里配送路徑優(yōu)化研究

章雪巖，桂 欣，鄭巧然

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

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

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

1 引言

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

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

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

2 最后一公里配送VRP模型

2.1 問題描述

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

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

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

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

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

2.2 模型建立

通過上述分析可以得出，最后一公里配送的CVRP問題的數(shù)學(xué)規(guī)劃模型如下：

目標函數(shù)：

約束條件：

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

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

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

目標函數(shù)：

約束條件：

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

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

3.1 遺傳算法原理

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

圖1CVRPGA算法流程圖

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

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

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

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

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

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

3.2 最后一公里配送優(yōu)化算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

圖3 交叉算子示意圖

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

圖4 變異算子示意圖

（7）自適應(yīng)過程。交叉概率Pc和變異概率Pm的選擇對遺傳算法的行為和性能都有一定的影響。結(jié)合對自適應(yīng)遺傳算法AGA和改進的自適應(yīng)遺傳算法IAGA的研究[10]，為了加快算法效率，提出以下?lián)m應(yīng)度對變異概率做出調(diào)整的方法。

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

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

①從種群進化穩(wěn)定性出發(fā)，設(shè)置一個ε，當(dāng)種群進化出現(xiàn)max(f(xi))-averg(f(xi))≤ε就停止迭代。

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

4 實例應(yīng)用

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

表1 各節(jié)點數(shù)據(jù)

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

表2 lingo精確求解結(jié)果

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

圖5 隨機求解100次結(jié)果

表3CVRPGA算法的滿意解

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

圖6 不同規(guī)模下的求解耗時

5 結(jié)語

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

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

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

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

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

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

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

[7]卓金武.MATLAB在數(shù)據(jù)建模中的應(yīng)用[M].北京：北京航空航天出版社,2011.

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

[9]劉英.遺傳算法中適應(yīng)度函數(shù)的研究[J].蘭州工業(yè)高等?？茖W(xué)校學(xué)報,2006,(3)：1-4.

[10]李欣.自適應(yīng)遺傳算法的改進與研究[D].南京：南京信息工程大學(xué),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-），男，西南交通大學(xué)教授，研究生導(dǎo)師，管理學(xué)博士，研究方向：物流信息化、供應(yīng)鏈管理；桂欣，男，西南交通大學(xué)物流工程專業(yè)研究生；鄭巧然，女，西南交通大學(xué)物流工程專業(yè)研究生。