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

章雪巖，桂 欣，鄭巧然

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

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

章雪巖，桂 欣，鄭巧然

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

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

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

1 引言

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

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

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

2 最后一公里配送VRP模型

2.1 問(wèn)題描述

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

（1）快遞員駕駛以配送點(diǎn)作為起點(diǎn)和終點(diǎn)；

（2）每個(gè)配送點(diǎn)的需求必須得到滿足，一般來(lái)說(shuō)配送點(diǎn)的需求不超過(guò)運(yùn)載工具的容量Q；

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

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

2.2 模型建立

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

目標(biāo)函數(shù)：

約束條件：

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

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

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

目標(biāo)函數(shù)：

約束條件：

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

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

3.1 遺傳算法原理

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

圖1CVRPGA算法流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

③計(jì)算每個(gè)配送路徑染色體編碼的個(gè)體累計(jì)概率Ti。

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

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

圖3 交叉算子示意圖

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

圖4 變異算子示意圖

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

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

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

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

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

4 實(shí)例應(yīng)用

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

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

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

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

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

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

表3CVRPGA算法的滿意解

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

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

5 結(jié)語(yǔ)

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

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

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

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

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

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

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

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

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

[9]劉英.遺傳算法中適應(yīng)度函數(shù)的研究[J].蘭州工業(yè)高等專(zhuān)科學(xué)校學(xué)報(bào),2006,(3)：1-4.

[10]李欣.自適應(yīng)遺傳算法的改進(jìn)與研究[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é)物流工程專(zhuān)業(yè)研究生；鄭巧然，女，西南交通大學(xué)物流工程專(zhuān)業(yè)研究生。