基于入侵雜草算法的城市生鮮配送優(yōu)化研究

金峰 董寶力

摘? 要：針對實(shí)際道路阻抗下的城市“最后一公里”生鮮配送路徑優(yōu)化問題，在保證騎手安全情況下，又能夠以最快速度將貨物送到客戶手上，降低配送成本，從配送過程中電動車遇到的實(shí)際道路阻抗因素出發(fā)，建立了以最大化顧客滿意度，最小化配送成本的多目標(biāo)優(yōu)化模型，并利用入侵雜草算法和遺傳算法對模型進(jìn)行分別求解。實(shí)驗(yàn)結(jié)果驗(yàn)證了模型和入侵雜草算法的有效性。

關(guān)鍵詞：生鮮配送;路徑優(yōu)化;入侵雜草算法

中圖分類號：F252.14? ? 文獻(xiàn)標(biāo)識碼：A

Abstract： In order to optimize the“l(fā)ast-mile”urban fresh food distribution route under actual road impedance， we set up a system that maximizes customer satisfaction and minimizes distribution costs， based on the actual road impedance factors encountered by electric vehicles in the distribution process， in order to ensure rider safety， deliver goods to customers as quickly as possible， and reduce distribution costs. A multi-objective optimization model was used to optimize the model and the invasive weed algorithm and genetic algorithm were used to solve the model separately. The experimental results validate the effectiveness of the model and the invasive weed algorithm.

Key words： fresh food distribution; path optimization; invasive weed algorithms

0? 引? 言

在“最后一公里”的生鮮產(chǎn)品配送過程中，安全、準(zhǔn)時是最重要的兩點(diǎn)因素，而配送時通往同一個地點(diǎn)有多種道路可以選擇，不同的道路有不同的路況，有明確將機(jī)動車道與非機(jī)動車道分開的道路更利于配送人員安全、準(zhǔn)時地配送。因此合理規(guī)劃和選擇配送路徑對于提高顧客滿意度、降低配送成本具有重要意義。因此，在配送過程中，應(yīng)在保證準(zhǔn)時配送的基礎(chǔ)上，盡量選擇利用非機(jī)動車道的道路，將貨物安全的送到客戶手上。

本文所描述的城市配送問題其本質(zhì)上就是一個VRP（Vehicle Routing Problem）問題。現(xiàn)有的文獻(xiàn)對VRP問題的研究已經(jīng)比較成熟。李桃迎等采用“商家—客戶”配對策略，對動態(tài)需求的外賣配送問題進(jìn)行了研究，但沒考慮到道路狀況問題;賈現(xiàn)召等采用灰色關(guān)聯(lián)度矩陣，應(yīng)用改進(jìn)的Floyd算法對實(shí)時路況下的生鮮農(nóng)產(chǎn)品配送問題進(jìn)行了優(yōu)化;王恒等在時間窗的約束下，考慮到道路路況的條件下提出改進(jìn)的自適應(yīng)遺傳算法對生鮮農(nóng)產(chǎn)品配送路徑進(jìn)行了求解;仝自強(qiáng)等在考慮實(shí)時路況的約束下解決了成品油二次配送的路徑優(yōu)化問題;徐肇元利用兩階段啟發(fā)式算法對外賣配送問題進(jìn)行了研究，但沒考慮到配送過程中的道路阻抗因素。上述文獻(xiàn)中對于實(shí)際道路狀況的研究都是針對于機(jī)動車的，對于電動車在行進(jìn)過程中的道路阻抗因素研究還有所欠缺。綜上所述，本文在考慮了時間窗約束以及電動車道路阻抗因素的條件下，建立了滿足顧客需求并且總配送時間最短的配送路徑模型。

1? 問題描述以及模型建立

1.1? 問題描述

本文描述的問題實(shí)際上是“一對多”的VRP問題，從一個配送中心出發(fā)，送到各個客戶點(diǎn)。在配送中心有M位騎手可供使用調(diào)度，每位騎手各自有一輛最大載貨量為Q的電動車可供使用。在某一時刻T，有N個客戶點(diǎn)需要配送貨物，每個客戶點(diǎn)各有一個時間滿意度T——即在T時刻內(nèi)訂單到達(dá)會滿意配送服務(wù)，超過這個時間點(diǎn)則會有時間窗懲罰成本。第i個客戶點(diǎn)需求的數(shù)量為q，最大q應(yīng)不超過載貨量Q。在配送過程中，不同的道路有各自不同的實(shí)際情況，有的道路是屬于機(jī)非混合道路，有的道路屬于非機(jī)動車道路，為了保障騎手安全行駛，在機(jī)非混合道路的行駛速度應(yīng)不超過15km/h，非機(jī)動車道路應(yīng)不超過25km/h。因此在其他條件相同的情況下，選擇擁有非機(jī)動車道的道路收益更大。如圖1所示，騎手從原點(diǎn)出發(fā)，在道路網(wǎng)絡(luò)中有不少機(jī)非混合道路，如何選擇道路會影響騎手的配送效率。對于騎手而言，在其他條件相同的情況下，走粗線的非機(jī)動車道明顯比細(xì)線的機(jī)非混合車道效率更高。

在這些約束下，要求合理安排配送路線，使顧客滿意度最大化，配送成本最小化。為了有效說明上述問題，做出以下幾點(diǎn)假設(shè)：

（1）每輛車的貨物容積一樣;

（2）每輛車在一次訂單的配送過程中只能被調(diào)用一次;

（3）為了保證安全準(zhǔn)時，本文使用允許使用的最高速度來表示行駛速度（啟動的時間忽略不計）。

1.2? 阻礙電動車行駛的因素

一般的BPR（道路阻抗）函數(shù)都是針對機(jī)動車而建立，主要是通過對道路交通流量的研究來得出道路通行的效率，從而得到不同交通流量道路上的通行時間。它的前提條件是因?yàn)闄C(jī)動車經(jīng)常有排隊(duì)和等候行為，而電動車相對而言在道路上行駛時更為暢通，不能簡單地將針對機(jī)動車的BPR函數(shù)套用到電動車身上。影響電動車實(shí)際通行效率主要是以下因素。在我國的道路系統(tǒng)中，并非所有的道路都設(shè)置了非機(jī)動車專用車道，有一定數(shù)量是機(jī)非混合的車道。機(jī)非混合車道對于非機(jī)動車而言需要更加注意騎行安全，降低騎行速度，國家規(guī)定，最高不能超過速度v=15公里/小時，正常電動車的騎行速度不能超過25km/h。

1.3? 模型建立

本文以最大化顧客滿意度和配送總成本最小化為目標(biāo)，建立了城市配送路徑的多目標(biāo)優(yōu)化模型：

MinZ=C+∑c*y+∑∑∑ctx? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

s.t. ∑y=1? ? i=1，2，3，…，N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

∑q*y≤Q? ? k=1，2，3，…，M? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）

∑x=1? ? k=1，2，3，…，M? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

∑x=1? ? k=1，2，3，…，M? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

t=∑∑t+tx? ? j=1，2，3，…，N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

x=? ? i，j=1，2，3，…，N; ？坌k? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

y=? ? i=1，2，3，…，N; k=1，2，3，…，M? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（8）

t=d/v? ? i，j=1，2，3，…，N? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（9）

其中：N是客戶點(diǎn)的數(shù)量;M是配送車輛的數(shù)量;Q是每輛車的最大載貨量;c是每輛車使用一次的固定成本費(fèi)和人工費(fèi)用;c是單位時間內(nèi)所花費(fèi)的成本;t是配送車輛從i到j(luò)客戶點(diǎn)的行駛時間;q是客戶點(diǎn)i的需求量;t表示到達(dá)客戶點(diǎn)j的時間;x是0-1變量，當(dāng)?shù)趉輛車通過客戶點(diǎn)i，j時為1，否則為0;y也是0-1變量，表示第k輛車被使用來服務(wù)第i位顧客;d表示i點(diǎn)與j點(diǎn)之間的距離;v表示i點(diǎn)與j點(diǎn)之間的速度，若i與j點(diǎn)之間有機(jī)非混合車道和非機(jī)動車道，則d和v分別按照兩種計算，所花費(fèi)的時間t則加起來得到。目標(biāo)函數(shù)（1）中的第一項(xiàng)C是時間窗的懲罰成本，時間窗的作用是限制配送時間，為了讓貨物能準(zhǔn)時送到顧客手上，顧客滿意度可以用配送時間長短來表示。根據(jù)調(diào)查結(jié)果本文設(shè)立軟時間窗，具體的懲罰函數(shù)如式（10）所示。

C=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（10）

根據(jù)客戶的要求，只要配送車輛在0，T時間范圍內(nèi)送達(dá)就不需要支付懲罰費(fèi)用，而超過了這個時間點(diǎn)則需要根據(jù)超時的長短來支付相應(yīng)的費(fèi)用，并且由于超時會對產(chǎn)品的質(zhì)量產(chǎn)生影響，懲罰費(fèi)用隨時間呈指數(shù)增長，如圖2所示。

第二項(xiàng)表示每次使用車輛的固定成本和人工費(fèi)用;第三項(xiàng)表示配送成本;式（2）表示客戶i只能被一輛車服務(wù);式（3）表示一輛配送車的容量限制;式（4）和式（5）表示確保從配送中心出發(fā)返回配送中心;式（6）表示從客戶點(diǎn)i到達(dá)客戶點(diǎn)j需要車輛的行駛時間;式（7）、式（8）是0-1變量;式（9）表示從客戶點(diǎn)i到客戶點(diǎn)j所花的時間是ij點(diǎn)之間的距離除以ij點(diǎn)之間的速度。上述問題是一個已經(jīng)被證明為NP難問題。

2? 入侵雜草優(yōu)化算法

IWO是2006年由A. R. Mehrabian等提出的一種從自然界雜草進(jìn)化原理演化而來的隨機(jī)搜索算法，模仿雜草入侵的種子空間擴(kuò)散、生長、繁殖和競爭性消亡的基本過程，具有很強(qiáng)的魯棒性和自適應(yīng)性。IWO算法是一種高效的隨機(jī)智能優(yōu)化算法，以群體中優(yōu)秀個體來指導(dǎo)種群的進(jìn)化，以正態(tài)分布動態(tài)改變標(biāo)準(zhǔn)差的方式將由優(yōu)秀個體產(chǎn)生的子代個體疊加在父代個體周圍，再經(jīng)過個體之間的競爭，得到最優(yōu)個體。算法兼顧了群體的多樣性和選擇力度。入侵雜草算法可以由以下幾個步驟實(shí)現(xiàn)：

（1）初始化種群

在D維空間隨機(jī)產(chǎn)生N個可行解（雜草）。

（2）種群繁殖

種群的繁殖是根據(jù)雜草的適應(yīng)度高低來進(jìn)行的，適應(yīng)度高的雜草所繁殖產(chǎn)生的后代多一點(diǎn);反之，適應(yīng)度低的雜草所繁殖的后代少一些。具體產(chǎn)生的種子數(shù)目由公式（11）決定：

Weed=s-s+s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （11）

其中：f代表當(dāng)前雜草對應(yīng)的適應(yīng)度值;f和f分別代表當(dāng)前雜草種群中雜草適應(yīng)度的最大和最小值;s和s代表當(dāng)前雜草種群中雜草產(chǎn)生種子的最大和最小數(shù)量。

（3）空間擴(kuò)散

種群產(chǎn)生的種子符合標(biāo)準(zhǔn)正態(tài)分布，設(shè)定步長為 -σ≤H≤σ。σ變化的公式為：

σ=σ-σ+σ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12）

其中：n表示非線性因子，iter表示最大進(jìn)化代數(shù)，iter表示當(dāng)前進(jìn)化代數(shù)，σ表示標(biāo)準(zhǔn)差的最終值，σ則是標(biāo)準(zhǔn)差的初始值。

（4）競爭擇優(yōu)

算法經(jīng)過若干代進(jìn)化以后，野草和種子的數(shù)目會達(dá)到預(yù)設(shè)的最大種群規(guī)模Q_max，種群中野草和種子按照適應(yīng)度大小進(jìn)行排序，選取適應(yīng)度較好的前Q_fmax個個體，淘汰其余的個體。

3? 仿真實(shí)驗(yàn)分析

案例計算：

本文以某生鮮超市的“最后一公里”配送實(shí)例為仿真對象進(jìn)行分析。在某塊區(qū)域范圍內(nèi)，某個時間點(diǎn)需要為17位顧客進(jìn)行配送，每輛車可容納的體積約為0.6立方米，每位騎手的成本約4.5元，單位時間所需要的成本為0.1元/min，車輛固定調(diào)度成本為10元/輛。表1表示各個顧客的坐標(biāo)和能夠接受的配送時間，圖3表示配送中心以及各個顧客之間的路況，坐標(biāo)原點(diǎn)為某生鮮超市所在地，為方便坐標(biāo)圖中將各點(diǎn)表示出來，所有的點(diǎn)坐標(biāo)在圖中縮小100倍，不影響實(shí)際的計算。

運(yùn)用Python編寫代碼對該模型進(jìn)行求解，模型的具體參數(shù)如下所示：初始種群規(guī)模N=3，非線性因子n=3，種群的最大種子數(shù)和最小種子數(shù)為s=20，s=1， 種群的最大和最小雜草數(shù)為N=20，N=5，最大迭代次數(shù)為500次。同時也用遺傳算法對該問題進(jìn)行模擬仿真，以此來對比兩種算法的優(yōu)越性。遺傳算法（GA）的選擇算子使用輪盤賭的方式獲取，交叉概率選擇P=0.7，變異算子選擇P=0.04。對兩種算法進(jìn)行分別計算得到結(jié)果如圖4所示。

從圖4中可以發(fā)現(xiàn)：遺傳（GA）算法在大約300代開始收斂趨于穩(wěn)定，此時的目標(biāo)函數(shù)值（總成本）為84.6元;入侵雜草（IWO）算法在大約200代就開始收斂趨于穩(wěn)定，此時的目標(biāo)函數(shù)值（總成本）大約為65.2元。由此可以說明，入侵雜草算法比遺傳算法擁有更快的收斂速度和更優(yōu)的優(yōu)化結(jié)果。

經(jīng)過仿真模擬得到的最優(yōu)配送路徑如圖5、表2所示。

4? 結(jié)? 論

本文針對城市“最后一公里”的配送問題上，由實(shí)際配送中遇到的道路狀況出發(fā)，為保證騎手安全，提出以最大化顧客滿意度，最小化配送成本的多目標(biāo)優(yōu)化模型。并且利用雜草入侵算法和遺傳算法對該模型進(jìn)行了求解，結(jié)果表明入侵雜草算法比遺傳算法擁有更快的收斂速度和更優(yōu)的結(jié)果。本文在計算點(diǎn)與點(diǎn)之間的距離時，雖然是使用的實(shí)際道路中需要行進(jìn)的距離，但是本文中的道路已被簡化，現(xiàn)實(shí)中的斜路彎路都被簡化成了直路且只保留了大路，城市中的各種羊腸小道不在考慮范圍之內(nèi)，如何將這些彎路斜路以及小路一起考慮進(jìn)去將會是下一步需要研究的點(diǎn)。

參考文獻(xiàn)：

[1] 李桃迎，呂曉寧，李峰，等. 考慮動態(tài)需求的外賣配送路徑優(yōu)化模型及算法[J]. 控制與決策，2019，34（2）：406-413.

[2] 賈現(xiàn)召，戚恒亮，賈其蘇，等. 實(shí)時路況下同城生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化[J]. 江蘇農(nóng)業(yè)科學(xué)，2017，45（17）：292-295.

[3] 王恒，徐亞星，王振鋒，等. 基于道路狀況的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化[J]. 系統(tǒng)仿真學(xué)報，2019，31（1）：126-135.

[4] 仝自強(qiáng)，李鵬翔. 考慮實(shí)時路況和車輛周轉(zhuǎn)率的成品油配送路徑優(yōu)化研究[J]. 工業(yè)工程與管理，2019，24（2）：109-115.

[5] 田源. 機(jī)非混合道路交通流模型校正以及道路阻抗函數(shù)的研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2012.

[6]? Alireza Goli， Erfan Babaee Tirkolaee， Behnam Malmir， et al. A multi-objective invasive weed optimization algorithm for robust aggregate production planning under uncertain seasonal demand[J]. Computing， 2019，101（6）：499-529.

[7] 何南，趙勝川. 城市道路阻抗函數(shù)模型研究——以大連市為例[J]. 公路交通科技，2014，31（2）：104-108.

[8] 張新，李珂，嚴(yán)大虎，等. 改進(jìn)入侵雜草算法求解柔性作業(yè)車間調(diào)度問題[J]. 系統(tǒng)仿真學(xué)報，2018，30（11）：4469-4476.

[9] 陳旭，陸麗麗，曹祖平，等. 道路阻抗函數(shù)研究綜述[J]. 交通運(yùn)輸研究，2020，6（2）：30-39.

[10] 余建軍，程文琪，吳永忠. 考慮顧客滿意度的生鮮外賣路徑規(guī)劃[J/OL]. 工業(yè)工程與管理，1-10[2020-10-25].