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

金峰 董寶力

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

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

中圖分類(lèi)號(hào)：F252.14? ? 文獻(xiàn)標(biāo)識(shí)碼：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)品配送過(guò)程中，安全、準(zhǔn)時(shí)是最重要的兩點(diǎn)因素，而配送時(shí)通往同一個(gè)地點(diǎn)有多種道路可以選擇，不同的道路有不同的路況，有明確將機(jī)動(dòng)車(chē)道與非機(jī)動(dòng)車(chē)道分開(kāi)的道路更利于配送人員安全、準(zhǔn)時(shí)地配送。因此合理規(guī)劃和選擇配送路徑對(duì)于提高顧客滿意度、降低配送成本具有重要意義。因此，在配送過(guò)程中，應(yīng)在保證準(zhǔn)時(shí)配送的基礎(chǔ)上，盡量選擇利用非機(jī)動(dòng)車(chē)道的道路，將貨物安全的送到客戶手上。

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

1? 問(wèn)題描述以及模型建立

1.1? 問(wèn)題描述

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

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

（1）每輛車(chē)的貨物容積一樣;

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

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

1.2? 阻礙電動(dòng)車(chē)行駛的因素

一般的BPR（道路阻抗）函數(shù)都是針對(duì)機(jī)動(dòng)車(chē)而建立，主要是通過(guò)對(duì)道路交通流量的研究來(lái)得出道路通行的效率，從而得到不同交通流量道路上的通行時(shí)間。它的前提條件是因?yàn)闄C(jī)動(dòng)車(chē)經(jīng)常有排隊(duì)和等候行為，而電動(dòng)車(chē)相對(duì)而言在道路上行駛時(shí)更為暢通，不能簡(jiǎn)單地將針對(duì)機(jī)動(dòng)車(chē)的BPR函數(shù)套用到電動(dòng)車(chē)身上。影響電動(dòng)車(chē)實(shí)際通行效率主要是以下因素。在我國(guó)的道路系統(tǒng)中，并非所有的道路都設(shè)置了非機(jī)動(dòng)車(chē)專(zhuān)用車(chē)道，有一定數(shù)量是機(jī)非混合的車(chē)道。機(jī)非混合車(chē)道對(duì)于非機(jī)動(dòng)車(chē)而言需要更加注意騎行安全，降低騎行速度，國(guó)家規(guī)定，最高不能超過(guò)速度v=15公里/小時(shí)，正常電動(dòng)車(chē)的騎行速度不能超過(guò)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是配送車(chē)輛的數(shù)量;Q是每輛車(chē)的最大載貨量;c是每輛車(chē)使用一次的固定成本費(fèi)和人工費(fèi)用;c是單位時(shí)間內(nèi)所花費(fèi)的成本;t是配送車(chē)輛從i到j(luò)客戶點(diǎn)的行駛時(shí)間;q是客戶點(diǎn)i的需求量;t表示到達(dá)客戶點(diǎn)j的時(shí)間;x是0-1變量，當(dāng)?shù)趉輛車(chē)通過(guò)客戶點(diǎn)i，j時(shí)為1，否則為0;y也是0-1變量，表示第k輛車(chē)被使用來(lái)服務(wù)第i位顧客;d表示i點(diǎn)與j點(diǎn)之間的距離;v表示i點(diǎn)與j點(diǎn)之間的速度，若i與j點(diǎn)之間有機(jī)非混合車(chē)道和非機(jī)動(dòng)車(chē)道，則d和v分別按照兩種計(jì)算，所花費(fèi)的時(shí)間t則加起來(lái)得到。目標(biāo)函數(shù)（1）中的第一項(xiàng)C是時(shí)間窗的懲罰成本，時(shí)間窗的作用是限制配送時(shí)間，為了讓貨物能準(zhǔn)時(shí)送到顧客手上，顧客滿意度可以用配送時(shí)間長(zhǎng)短來(lái)表示。根據(jù)調(diào)查結(jié)果本文設(shè)立軟時(shí)間窗，具體的懲罰函數(shù)如式（10）所示。

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

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

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

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

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

（1）初始化種群

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

（2）種群繁殖

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

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

其中：f代表當(dāng)前雜草對(duì)應(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è)定步長(zhǎng)為 -σ≤H≤σ。σ變化的公式為：

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

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

（4）競(jìng)爭(zhēng)擇優(yōu)

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

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

案例計(jì)算：

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 賈現(xiàn)召，戚恒亮，賈其蘇，等. 實(shí)時(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é)報(bào)，2019，31（1）：126-135.

[4] 仝自強(qiáng)，李鵬翔. 考慮實(shí)時(shí)路況和車(chē)輛周轉(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è)車(chē)間調(diào)度問(wèn)題[J]. 系統(tǒng)仿真學(xué)報(bào)，2018，30（11）：4469-4476.

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

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