潘 曉 ,鹿冬娜 ,王書(shū)海

（1.石家莊鐵道大學(xué) 管理學(xué)院,石家莊 050043;2.石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,石家莊 050043）

0 引 言

2020 年的中國(guó)社會(huì)消費(fèi)品零售總額中涉及商超類(lèi)型產(chǎn)品的零售額為193 323 億元,占比達(dá)到了商品零售總額的54.85%.因此,商超配送是社會(huì)消費(fèi)需求的重要組成部分,且其需求占比較大.商超配送主要是指在經(jīng)濟(jì)合理區(qū)域范圍內(nèi),根據(jù)各商超和賣(mài)場(chǎng)的要求,對(duì)貨物進(jìn)行分揀、加工、分割、組配等作業(yè),最后將貨物由配送中心送達(dá)指定的商超門(mén)店的物流活動(dòng)[1].

與其他配送問(wèn)題相比,商超配送目前主要面臨的問(wèn)題有: 商超門(mén)店位置不一,分布較散;配送資源利用不足,車(chē)輛配載和路徑規(guī)劃難;配送場(chǎng)景復(fù)雜,商超門(mén)店需求差異大;貨物品類(lèi)繁雜,對(duì)運(yùn)輸和存儲(chǔ)方式要求嚴(yán)格等.

為了解決上述問(wèn)題,各大商超企業(yè)分別采取了不同的配送方式,例如,家樂(lè)福采取供應(yīng)商直送的方式,由供應(yīng)商實(shí)現(xiàn)配送資源的整合;沃爾瑪采取自營(yíng)配送的方式,適應(yīng)了門(mén)店間的需求差異;一般中小型商超采取第三方物流的配送方式,滿足了不同貨物品類(lèi)對(duì)運(yùn)輸和存儲(chǔ)的需求[2].但無(wú)論哪種配送方式,都面臨相同的且重要的問(wèn)題: 車(chē)輛配載和路徑規(guī)劃.訂單拆分可以充分利用車(chē)輛容量,合理安排貨物裝載.2006 年,Archetti 等[3]證明了訂單拆分的可行性.

鑒于此,本文設(shè)計(jì)了基于訂單拆分的容量限制商超配送路徑規(guī)劃方案,可在一定程度上解決商超配送的車(chē)輛配載和路徑規(guī)劃問(wèn)題.首先,采用“20/10/5 規(guī)則”的訂單拆分策略對(duì)每個(gè)商超客戶的需求量進(jìn)行拆分;然后,在該訂單拆分策略的基礎(chǔ)上,建立商超配送路徑規(guī)劃模型;最后,采用改進(jìn)灰狼優(yōu)化算法進(jìn)行模型求解,得到具體的商超配送路徑規(guī)劃方案.通過(guò)實(shí)例分析,與求解該模型的代表性方法—遺傳算法進(jìn)行對(duì)比,驗(yàn)證了本文的改進(jìn)灰狼優(yōu)化算法的有效性.

1 相關(guān)工作

基于訂單拆分的容量限制商超配送路徑規(guī)劃問(wèn)題是一般帶容量限制車(chē)輛路徑規(guī)劃問(wèn)題(Capacitated Vehicle Routing Problem,CVRP) 中的一種.CVRP 最早由Dantzig 和Ramser[4]提出,其作為車(chē)輛路徑問(wèn)題 (Vehicle Routing Problem,VRP) 的一種常見(jiàn)形式,已被證明是典型的NP-難(Non-deterministic Polynomial Hard)組合優(yōu)化問(wèn)題[5].目前,針對(duì)CVRP 的研究主要集中在模型建立和算法求解這兩個(gè)方面.

1.1 模型建立

在模型建立的目標(biāo)方面,學(xué)者們大多傾向于以1 個(gè)或多個(gè)目標(biāo)最優(yōu),如成本最低、路徑長(zhǎng)度最小、耗時(shí)最短、能耗和污染最低等,同時(shí)考慮現(xiàn)實(shí)場(chǎng)景中的約束條件建立模型.范厚明等[6]考慮生鮮品配送的時(shí)效性要求,以配送車(chē)輛運(yùn)輸成本、派遣成本、時(shí)間懲罰成本及貨損成本最小為目標(biāo),建立了配送路徑規(guī)劃問(wèn)題模型;曾正洋等[7]以應(yīng)急配送中受災(zāi)點(diǎn)的累計(jì)等待時(shí)間最短為目標(biāo),建立了多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題模型;周鮮成等[8]考慮物流配送領(lǐng)域的節(jié)能減排需求,以車(chē)輛油耗和碳排放成本、車(chē)輛使用成本之和最小為目標(biāo),建立了綠色配送車(chē)輛路徑問(wèn)題模型.

分析上述模型建立方式可發(fā)現(xiàn),在建模時(shí),應(yīng)根據(jù)配送過(guò)程中需求的不同設(shè)置合理的目標(biāo)及約束條件.本文所研究的商超配送路徑規(guī)劃問(wèn)題,意在滿足客戶需求的同時(shí),也能夠充分利用配送資源,減少成本支出.因此,結(jié)合實(shí)際商超配送過(guò)程中的成本組成,本文以車(chē)輛行駛成本、車(chē)輛派遣成本之和為目標(biāo),建立基于訂單拆分策略的容量限制商超配送路徑規(guī)劃模型.

訂單拆分策略在CVRP 上實(shí)現(xiàn)的方式主要有2 種: 一種是在建立模型的約束中添加訂單拆分;另一種是在模型求解過(guò)程中實(shí)現(xiàn)訂單拆分.這兩種方式都可以降低配送成本,但后者計(jì)算時(shí)間較長(zhǎng)[9].而商超配送貨物品類(lèi)繁雜,裝載過(guò)程耗時(shí)較長(zhǎng).為了保證在時(shí)間窗內(nèi)完成配送任務(wù),本文采用在模型建立中進(jìn)行訂單拆分策略,即按照“20/10/5 規(guī)則”的訂單拆分策略,依據(jù)車(chē)輛容量限制,將商超門(mén)店的訂單需求進(jìn)行拆分.

1.2 算法求解

在算法求解方面,當(dāng)前解決CVRP 的方法主要分為精確算法、啟發(fā)式算法和混合算法這3 類(lèi).

(1) 精確算法

精確算法適用于小規(guī)模的CVRP 求解,往往能夠獲得問(wèn)題的最優(yōu)解,其代表性方法主要是分支-切割-定價(jià)算法.Yang 等[10]利用分支-切割-定價(jià)算法,為農(nóng)村最后1 km 的配送提供了合理的方案;揭婉晨等[11]針對(duì)需求可拆分的容量約束車(chē)輛路徑問(wèn)題模型,提出了一種改進(jìn)的分支定價(jià)算法.

(2) 啟發(fā)式算法

啟發(fā)式算法在求解大規(guī)模的CVRP 時(shí)效果較好,能夠在合理時(shí)間內(nèi)獲得相對(duì)最優(yōu)解.具有代表性的啟發(fā)式算法主要有遺傳算法、蟻群算法、禁忌搜索算法等.張亞明等[12]設(shè)計(jì)了局部精英單親遺傳算法來(lái)求解滿意度約束多車(chē)型冷鏈車(chē)輛的路徑問(wèn)題;Xu 等[13]針對(duì)實(shí)時(shí)變化的新客戶需求下大規(guī)模車(chē)輛路徑問(wèn)題,設(shè)計(jì)改進(jìn)了蟻群算法求解;符卓等[14]在綜合考慮客戶的訂單拆分需求和服務(wù)時(shí)間需求后建立模型,并設(shè)計(jì)了禁忌搜索算法求解.

(3) 混合算法

混合算法是將各類(lèi)精確算法、啟發(fā)式算法進(jìn)行混合,以加快算法收斂速度,跳出局部最優(yōu)解.目前,混合算法主要有: Sitek 等[15]為解決帶取送貨車(chē)輛路徑問(wèn)題,提出的約束邏輯規(guī)劃與啟發(fā)式算法相結(jié)合的混合算法;李陽(yáng)等[16]為求解CVRP 設(shè)計(jì)的混合變鄰域生物共棲搜索算法;Gokalp 等[17]提出的用于解決CVRP 的基于迭代局部搜索和隨機(jī)變量鄰域下降元啟發(fā)式的混合算法等.

綜上所述,在設(shè)計(jì)大規(guī)模CVRP 模型的求解算法時(shí),大多數(shù)學(xué)者選擇對(duì)已有的解決CVRP的啟發(fā)式算法進(jìn)行改進(jìn),但仍存在容易而陷入局部最優(yōu)解的弊端;也有不少學(xué)者將不同的算法進(jìn)行結(jié)合,采用混合算法求解,但也會(huì)出現(xiàn)求得的最優(yōu)解不理想的問(wèn)題.

灰狼優(yōu)化(Grey Wolf Optimization,GWO) 算法作為一種新興的群體智能啟發(fā)式算法,具有依賴參數(shù)少、尋優(yōu)性能好的特點(diǎn)[18],適用于求解大規(guī)模的NP-難問(wèn)題.GWO 算法利用系數(shù)向量和收斂因子,能夠合理平衡問(wèn)題求解時(shí)的全局搜索和局部開(kāi)發(fā)能力,從而擴(kuò)大最優(yōu)解的搜索空間,有效避免了陷入局部最優(yōu)解[18].但GWO 算法所得的最優(yōu)解效果仍不夠理想.因此,本文在GWO 算法的基礎(chǔ)上添加遺傳變異操作,提出了改進(jìn)灰狼優(yōu)化算法,增加了其在局部開(kāi)發(fā)最優(yōu)解過(guò)程的隨機(jī)性.研究結(jié)果表明,與GWO 算法、遺傳算法相比,在配送總成本方面,本文的改進(jìn)灰狼優(yōu)化算法結(jié)果更優(yōu).

2 問(wèn)題描述與數(shù)學(xué)模型

2.1 問(wèn)題描述

本文所研究的基于訂單拆分的容量限制商超配送路徑規(guī)劃問(wèn)題: 在經(jīng)濟(jì)合理區(qū)域范圍內(nèi),已知商超類(lèi)型的客戶數(shù)量、位置以及訂單需求,由單配送中心統(tǒng)一派出若干輛車(chē),依據(jù)車(chē)輛容量將客戶訂單進(jìn)行拆分,并在不超過(guò)車(chē)輛最大容量限制的前提下進(jìn)行配載,為相應(yīng)客戶提供配送服務(wù);設(shè)計(jì)配送總成本最小的路線規(guī)劃方案,將貨物按時(shí)送到各大商超和賣(mài)場(chǎng),滿足所有客戶的訂單需求.這里的配送總成本由依賴于行駛距離的車(chē)輛行駛成本和派遣成本構(gòu)成.

如果1 個(gè)訂單的需求量本身已超過(guò)配送車(chē)輛的最大容量限制,則必須對(duì)訂單進(jìn)行拆分,由1 輛以上的車(chē)輛進(jìn)行配送.這種必須拆分的情況,不在本文研究范圍內(nèi).本文只針對(duì)每個(gè)客戶訂單需求量未超過(guò)配送車(chē)輛最大容量限制的情形.對(duì)于某個(gè)客戶需求量超過(guò)車(chē)輛最大容量限制的情況,本文默認(rèn)對(duì)該客戶訂單先進(jìn)行整車(chē)裝載,剩余部分再采取訂單拆分策略.

為了研究方便,提出以下假設(shè).

(1) 已知各商超類(lèi)型的客戶數(shù)量、客戶位置、訂單需求,所有訂單任務(wù)均由單配送中心完成.

(2) 配送中心有若干配送車(chē)輛,車(chē)型相同,車(chē)輛容量已知,且裝載量不可超過(guò)車(chē)輛最大容量.

(3) 配送車(chē)輛總是由配送中心出發(fā),完成各個(gè)客戶的配送任務(wù)后,再返回配送中心.

(4) 每個(gè)配送車(chē)輛只允許被派遣1 次.

(5) 保證所有客戶均被服務(wù),允許每個(gè)客戶被服務(wù)多次,即不要求一次性滿足客戶需求.

(6) 送貨和收貨的時(shí)間皆在規(guī)定范圍內(nèi),即不考慮客戶對(duì)時(shí)間的要求.

為避免過(guò)細(xì)拆分造成的計(jì)算負(fù)擔(dān)過(guò)重問(wèn)題,本文修正了Chen 等[9]提出的“20/10/5/1 規(guī)則”的先驗(yàn)拆分策略,結(jié)合商超配送的特殊性,采用“20/10/5 規(guī)則”的訂單拆分策略,在算法求解前先對(duì)訂單進(jìn)行拆分.具體的拆分規(guī)則: 將每個(gè)商超客戶的訂單需求按20%、10%和5%的車(chē)輛最大容量分別拆分為不同的份數(shù),且每個(gè)訂單在拆分時(shí),最多允許有1 份少于5%的車(chē)輛最大容量,例如,當(dāng)某商超客戶需求量為649,車(chē)輛最大容量為2050 時(shí),根據(jù)“20/10/5 規(guī)則”,該訂單將被拆分為3 份,即410、205、34.

2.2 模型構(gòu)建

基于訂單拆分的帶容量限制商超配送路徑規(guī)劃問(wèn)題可以用1 個(gè)有向圖G=(N,E) 來(lái)表示,其中,點(diǎn)集N={i|i=0,1,2,···,n},{0}表示配送中心節(jié)點(diǎn),{1,2,···,n}表示各商超客戶節(jié)點(diǎn);弧集E={〈i,j〉|i,j ∈N},弧〈i,j〉表示車(chē)輛從商超客戶i向商超客戶j行駛的路徑.問(wèn)題示意圖如圖1 所示.

圖1 商超配送路徑規(guī)劃問(wèn)題示意圖Fig.1 Schematic diagram of the distribution routes planning problem in supermarkets

圖1(a)表示無(wú)訂單拆分的配送路徑方案,配送過(guò)程中每個(gè)客戶只允許被服務(wù)1 次;圖1(b)表示有訂單拆分的路徑規(guī)劃方案,每個(gè)客戶允許被多次服務(wù),其中紅色圈圈出的商超客戶被進(jìn)行了多次配送服務(wù).

根據(jù)提出的假設(shè)和訂單拆分策略,以最小化配送總成本為目標(biāo),構(gòu)建車(chē)輛路徑配送模型.

設(shè)置的各參數(shù)及含義如下.

K—車(chē)輛集合,K={k|k=1,2,···,m},k表示配送中心派出的車(chē)輛.

n—商超客戶數(shù)量.

qi—商超客戶i的訂單需求量,i∈{1,2,···,n}.

Qk—車(chē)輛k的最大容量.

dij—從商超客戶i到商超客戶j的距離.

ce—單位距離的車(chē)輛行駛成本.

ck—車(chē)輛的派遣成本.

xijk—若車(chē)輛k從商超客戶i直接到達(dá)商超客戶j,則xijk=1,否則為0.

—若車(chē)輛k服務(wù)于商超客戶i,則,否則為0.

構(gòu)建基于訂單拆分的容量限制商超配送路徑模型

表示配送總成本,由車(chē)輛行駛成本和派遣成本構(gòu)成: 車(chē)輛行駛成本主要取決于車(chē)輛的行駛距離,由每輛車(chē)的行駛距離之和乘以單位距離的車(chē)輛行駛成本計(jì)算得出;車(chē)輛派遣成本主要取決于使用車(chē)輛數(shù),由配送方案使用的總車(chē)輛數(shù)乘以每輛車(chē)的固定成本計(jì)算得出.

約束條件是

公式 (1) 為目標(biāo)函數(shù),表示配送的總成本最小.公式 (2)—公式 (4) 為“20/10/5 規(guī)則”的訂單拆分策略：公式 (2) 表示商超客戶i的訂單需求量中所拆分出的20%車(chē)輛最大容量的數(shù)量;公式 (3) 表示經(jīng)過(guò)公式 (2) 的拆分后,剩余商超客戶i的訂單需求量中所拆分出的10%車(chē)輛最大容量的數(shù)量;公式 (4)表示經(jīng)過(guò)公式 (2) 和 公式(3) 的拆分后,商超客戶i的訂單需求量中所拆分出的5%車(chē)輛最大容量的數(shù)量.公式 (5) 和公式 (6) 表示車(chē)輛的容量限制: 公式 (5) 表示沒(méi)有訂單拆分時(shí),根據(jù)客戶需求安排的車(chē)輛裝載量不能超過(guò)配送車(chē)輛的最大容量;公式 (6) 表示基于訂單拆分所安排的車(chē)輛裝載量不能超過(guò)配送車(chē)輛的最大容量.公式 (7) 表示車(chē)輛從配送中心出發(fā),并最終回到配送中心.公式 (8) 和公式 (9)表示每個(gè)客戶都將至少被服務(wù)1 次,即車(chē)輛k到達(dá)和離開(kāi)商超客戶j的次數(shù)分別至少為1 次.公式 (10)表示車(chē)輛的進(jìn)出平衡關(guān)系,即若車(chē)輛k為商超客戶j服務(wù),則需要在商超客戶j處完成進(jìn)和出,且進(jìn)出次數(shù)保持平衡.

3 算法設(shè)計(jì)

灰狼優(yōu)化(GWO)算法是由Mirjalili 等[18]于2014 年提出的,是模擬自然界中灰狼群體的社會(huì)等級(jí)制度和狩獵行為而衍生出的一種群體智能啟發(fā)式算法.啟發(fā)式算法中的代表性算法是遺傳算法[12].與遺傳算法一樣,GWO 算法也適用于求解CVRP[18],但通過(guò)其所得的最優(yōu)解效果仍不夠理想.因此,本文通過(guò)對(duì)GWO 算法添加遺傳變異操作,設(shè)計(jì)改進(jìn)GWO 算法,來(lái)求解基于訂單拆分的容量限制商超配送車(chē)輛路徑問(wèn)題.為便于理解,表1 給出了本文改進(jìn)灰狼優(yōu)化算法中的常用術(shù)語(yǔ)以及其與車(chē)輛路徑規(guī)劃問(wèn)題的必要對(duì)應(yīng)關(guān)系.

表1 灰狼優(yōu)化算法的術(shù)語(yǔ)說(shuō)明Tab.1 Glossary of grey wolf optimization algorithm

基于改進(jìn)灰狼優(yōu)化算法的路徑規(guī)劃流程見(jiàn)算法1 所示.算法1 中,行1—行9,對(duì)9 對(duì)灰狼種群進(jìn)行初始化,即根據(jù)商超配送問(wèn)題規(guī)模的大小,為每個(gè)灰狼個(gè)體確定其所有車(chē)輛的初始經(jīng)過(guò)商超客戶序列.本文采用隨機(jī)初始化的方式產(chǎn)生灰狼種群,具體的步驟將在3.1 節(jié)詳細(xì)介紹.

行10—行16,利用適應(yīng)度函數(shù)計(jì)算種群中每個(gè)灰狼個(gè)體的適應(yīng)度值,并保留種群中適應(yīng)度值最佳的前3 只狼α、β、δ(配送總成本最低的3 個(gè)方案) .適應(yīng)度函數(shù)計(jì)算將在3.2 節(jié)的算法2 中詳細(xì)介紹.

行17—行24,在最大迭代次數(shù)范圍內(nèi),以3 只狼α、β、δ為依據(jù),對(duì)灰狼種群進(jìn)行位置更新.具體的灰狼位置更新方式將在3.3 節(jié)詳細(xì)介紹.對(duì)更新后的灰狼個(gè)體,重新計(jì)算其適應(yīng)度值,可以在每次迭代中都獲得新的3 只狼α、β、δ.

行25—行33,在設(shè)定的變異次數(shù)上限內(nèi),借鑒遺傳算法中的變異操作,采用部分單點(diǎn)移動(dòng)的方式,對(duì)最后一次迭代中狼α(第一最佳配送方案) 所對(duì)應(yīng)的配送路徑規(guī)劃方案進(jìn)行改進(jìn).具體的變異操作方法將在3.4 節(jié)詳細(xì)介紹.判斷改進(jìn)后的方案適應(yīng)度值是否優(yōu)于狼α,輸出適應(yīng)度值最佳的灰狼個(gè)體所對(duì)應(yīng)的車(chē)輛行駛路線及配送總成本.

3.1 初始化灰狼種群步驟

初始化灰狼種群是改進(jìn)灰狼優(yōu)化算法的基礎(chǔ)步驟.在商超配送路徑規(guī)劃問(wèn)題中,初始化灰狼種群是指產(chǎn)生多種可能配送方案的所有車(chē)輛,初始經(jīng)過(guò)的商超客戶序列.具體分為以下3 個(gè)步驟.

步驟1: 確定配送方案所需車(chē)輛數(shù)k.為了滿足所有商超客戶的服務(wù)需求,本文通過(guò)公式

計(jì)算完成配送任務(wù)所需最少的配送車(chē)輛數(shù)k,即計(jì)算所有商超客戶總需求量qi與配送車(chē)輛最大容量Qk的比值,并向上取整,得到所需車(chē)輛數(shù).若無(wú)法在最少車(chē)輛數(shù)基礎(chǔ)上得到可行的配送方案,則依次增加1 輛配送車(chē)輛,直至能夠得到可行方案,確定所需車(chē)輛數(shù).

步驟2: 隨機(jī)產(chǎn)生灰狼個(gè)體.采用隨機(jī)初始化的方式產(chǎn)生灰狼個(gè)體,即為步驟1 中的k輛車(chē)隨機(jī)確定初始經(jīng)過(guò)的商超客戶坐標(biāo),k輛車(chē)的全部初始經(jīng)過(guò)的商超客戶坐標(biāo)共同組成灰狼個(gè)體.本文設(shè)置配送車(chē)輛的初始經(jīng)過(guò)的商超客戶坐標(biāo)須在規(guī)定的配送范圍內(nèi)產(chǎn)生.

步驟3: 根據(jù)問(wèn)題規(guī)模,產(chǎn)生灰狼種群.重復(fù)執(zhí)行步驟2,產(chǎn)生多個(gè)灰狼個(gè)體,形成灰狼種群,即產(chǎn)生多種可能的k輛車(chē)的初始經(jīng)過(guò)的商超客戶坐標(biāo).

3.2 適應(yīng)度值計(jì)算過(guò)程

在改進(jìn)灰狼優(yōu)化算法中,通過(guò)適應(yīng)度函數(shù)計(jì)算適應(yīng)度值,用適應(yīng)度值來(lái)度量種群中每個(gè)灰狼個(gè)體的優(yōu)劣程度,即依據(jù)全部配送車(chē)輛的初始經(jīng)過(guò)商超客戶坐標(biāo),利用適應(yīng)度函數(shù)得出完整的商超配送路徑規(guī)劃方案,并計(jì)算該方案的配送總成本作為灰狼個(gè)體的適應(yīng)度值.適應(yīng)度函數(shù)的流程如算法2所示.

算法2 中,行1,初始化參數(shù);行2—行13,對(duì)商超客戶i與配送車(chē)輛k進(jìn)行匹配,其中,行3—行6是商超客戶i與配送車(chē)輛k的初步匹配,即為配送車(chē)輛k分配與其距離最近且需求量最大的商超客戶i,且優(yōu)先配送.本文通過(guò)公式

為每個(gè)商超客戶i計(jì)算其與所有配送車(chē)輛之間的距離以及其需求量的比值,選擇需求量比值最小的配送車(chē)輛k與商超客戶i進(jìn)行匹配,以保證所有商超客戶均得到服務(wù).公式 (12) 中:fik表示商超客戶i與配送車(chē)輛k的初步匹配標(biāo)準(zhǔn);dik表示商超客戶i與配送車(chē)輛k之間的距離;qi表示商超客戶i的需求量.

行7—行12,初步匹配方案的調(diào)整.由于初步匹配沒(méi)有考慮到配送車(chē)輛k的容量限制,因此,需要進(jìn)一步判斷商超客戶i的需求量是否超過(guò)配送車(chē)輛k的剩余車(chē)輛容量: 若未超過(guò),則不改變初始匹配方案;若超過(guò),則調(diào)整商超客戶i由其他配送車(chē)輛服務(wù).最終,得出符合車(chē)輛容量限制的完整商超配送規(guī)劃方案.

行14—行16,計(jì)算種群中每個(gè)灰狼個(gè)體的適應(yīng)度值.利用目標(biāo)函數(shù)計(jì)算灰狼個(gè)體的適應(yīng)度值,即計(jì)算方案所需配送總成本.適應(yīng)度值計(jì)算的表達(dá)式為

公式 (13) 中:ffit表示灰狼個(gè)體的適應(yīng)度值;z表示方案的配送總成本 (車(chē)輛行駛成本與車(chē)輛派遣成本的和).

行17,返回每個(gè)灰狼個(gè)體所對(duì)應(yīng)的車(chē)輛行駛路線和適應(yīng)度值.

3.3 灰狼位置更新方式

灰狼位置更新的目的是實(shí)現(xiàn)狩獵行為.在狩獵期間,灰狼群體主要進(jìn)行包圍獵物、追捕獵物、攻擊獵物和搜索獵物4 項(xiàng)活動(dòng).在改進(jìn)灰狼優(yōu)化算法中,灰狼位置的更新方式與灰狼社會(huì)等級(jí)制度有關(guān).灰狼的社會(huì)等級(jí)制度是指,依據(jù)適應(yīng)度值從小到大將灰狼種群中的個(gè)體劃分為α、β、δ、ω這4 個(gè)等級(jí),如圖2 所示.圖2 中,狼ω以狼α、狼β、狼δ的位置為依據(jù)進(jìn)行狩獵行為,即種群中的全部配送方案均以適應(yīng)度值最佳的前3 個(gè)方案 (狼α、狼β、狼δ) 為依據(jù)進(jìn)行調(diào)整.

圖2 灰狼社會(huì)等級(jí)劃分[18]Fig.2 Hierarchy of grey wolf[18]

(1) 包圍

包圍本質(zhì)上是一種灰狼位置更新的法則,是指當(dāng)假定的獵物位置已知時(shí),灰狼種群如何實(shí)現(xiàn)逐漸接近獵物.因此,在商超配送路徑規(guī)劃過(guò)程中,包圍表示,在有多個(gè)配送方案的集合中,選定某一方案并將其視為獵物,此時(shí)集合中其他方案將以該方案為依據(jù)進(jìn)行調(diào)整,這種做出調(diào)整的法則即為包圍獵物的過(guò)程.具體的調(diào)整方式為[18]

(2) 追捕

由于在實(shí)際情況下,求解之前無(wú)法得知適應(yīng)度值的最佳配送方案,改進(jìn)灰狼優(yōu)化算法假.設(shè)狼α、狼β、狼δ(適應(yīng)度值最佳的前3 個(gè)配送方案所對(duì)應(yīng)的所有車(chē)輛經(jīng)過(guò)的商超客戶序列) 更了解獵物 (全局最佳配送方案所對(duì)應(yīng)的所有車(chē)輛經(jīng)過(guò)的商超客戶序列) 的潛在位置,有能力帶領(lǐng)狼ω(其余配送方案所對(duì)應(yīng)的所有車(chē)輛經(jīng)過(guò)的商超客戶序列) 識(shí)別并包圍獵物.

因此,追捕是在包圍的基礎(chǔ)上,分別將狼α、狼β、狼δ視為獵物,綜合考慮這3 只灰狼的位置進(jìn)行狼ω的位置更新.在商超配送車(chē)輛路徑規(guī)劃過(guò)程中,追捕表示,利用包圍中的配送方案調(diào)整法則,將適應(yīng)度值最佳的前3 個(gè)方案作為獵物,分別得到3 種配送方案調(diào)整方式,再利用公式[18]

綜合3 種調(diào)整方式,得出每輛車(chē)初始經(jīng)過(guò)的商超客戶,作為最終調(diào)整方案.

(3) 攻擊和搜索

在完成包圍、追捕的活動(dòng)后,灰狼種群可以做出2 種選擇: 攻擊或搜索.攻擊是指確定輸出當(dāng)前最優(yōu)解;搜索是指放棄當(dāng)前最優(yōu)解,探索其他可行解.因此,在商超配送車(chē)輛路徑規(guī)劃過(guò)程中,攻擊表示,在追捕活動(dòng)后,將得到的最終配送方案輸出,作為全局最佳配送方案;搜索表示,放棄追捕活動(dòng)得到的最佳方案,以跳出局部最優(yōu)解,去探索其他更佳的配送方案.

如何在攻擊和搜索中做出選擇,取決于系數(shù)向量.改進(jìn)灰狼優(yōu)化算法設(shè)置:時(shí),攻擊獵物,即確定最佳配送方案;時(shí),搜索獵物,即探索其他更佳配送方案.

3.4 變異操作方法

與遺傳算法的目的一致,變異操作是為了產(chǎn)生新的商超配送路徑方案.對(duì)狼α所對(duì)應(yīng)的配送路徑規(guī)劃方案進(jìn)行部分單點(diǎn)移動(dòng)的變異操作.變異操作的過(guò)程如圖3 所示,具體可以分為以下2 個(gè)步驟.

圖3 變異算子示意圖Fig.3 Schematic diagram of the mutation operator

步驟1: 在狼α對(duì)應(yīng)的配送路徑規(guī)劃方案中,隨機(jī)選擇某輛車(chē)所服務(wù)的2 個(gè)商超客戶.

步驟2: 將服務(wù)順序靠后的商超客戶向前移,移至服務(wù)順序靠前的下一個(gè),并進(jìn)行配送服務(wù).同時(shí),2 個(gè)客戶之間的其他商超客戶的服務(wù)順序依次后移,產(chǎn)生新的配送方案.

4 實(shí)例分析

4.1 實(shí)例數(shù)據(jù)

本文選用中國(guó)外運(yùn)公司商超項(xiàng)目中2020 年6 月6 日北京配送中心的需求訂單數(shù)據(jù)來(lái)驗(yàn)證本文方法的有效性.該數(shù)據(jù)包含1 個(gè)配送中心的位置信息、20 個(gè)商超類(lèi)型客戶的位置信息和訂單需求量.配送中心的所有客戶總需求量為6 035 個(gè)貨物,車(chē)輛派遣成本為850 元/輛,平均的車(chē)輛行駛成本為0.5 元/km.

已知該配送中心所服務(wù)的商超類(lèi)型客戶均位于北京市內(nèi).為了便于研究,利用地學(xué)大數(shù)據(jù)平臺(tái)①http://www.giscalculator.com/將數(shù)據(jù)中的文本位置信息轉(zhuǎn)換為位置經(jīng)緯度,并應(yīng)用大地坐標(biāo)系與空間直角坐標(biāo)的關(guān)系轉(zhuǎn)換公式[19]將經(jīng)緯度投影到空間直角坐標(biāo)系下.其位置分布和訂單需求如圖4 所示.圖4 中,商超客戶和配送中心旁邊括號(hào)內(nèi)的數(shù)字分別表示商超客戶結(jié)點(diǎn)的編號(hào)及其訂單需求量.

圖4 北京配送中心商超配送信息Fig.4 Beijing distribution center supermarket delivery information

圖5 為訂單需求分布箱線圖.從圖5 中可以看出,商超客戶的需求量差異較大,取值范圍為[10,1 600],呈長(zhǎng)右尾分布,平均需求量為300.圖6 采用熱力氣泡式數(shù)據(jù)圖展示了北京配送中心的所有商超客戶需求分布情況.其中,氣泡的位置表示每個(gè)客戶的坐標(biāo),氣泡的大小和顏色均表示每個(gè)客戶的需求量大小(需求貨物的個(gè)數(shù)).根據(jù)圖6,結(jié)合北京市的實(shí)際情況來(lái)看,各客戶的訂單需求量大致呈環(huán)狀分布: 內(nèi)環(huán)靠近北京市中心,訂單大多來(lái)自人流量較大的賣(mài)場(chǎng),而此類(lèi)賣(mài)場(chǎng)倉(cāng)儲(chǔ)面積較小,訂單需求量較小;外環(huán)靠近郊區(qū),大多是商超的自建倉(cāng)儲(chǔ)物流中心或倉(cāng)儲(chǔ)型超市,訂單需求量較大.

圖5 訂單需求分布箱線圖Fig.5 Boxplot of order demand distribution

圖6 訂單需求分布熱力圖Fig.6 Heat map of order demand distribution

根據(jù)“20/10/5 規(guī)則”的訂單拆分策略,將北京配送中心的20 條需求訂單數(shù)據(jù)進(jìn)行拆分.以配送車(chē)輛容量限制為2050 (總需求量∶車(chē)輛容量=2.9) 為例,得39 個(gè)新訂單.訂單需求信息展示在了表2 中,其中最后一列即為拆分后的新訂單.

表2 訂單拆分后的商超配送信息Tab.2 Supermarket delivery information after order split

4.2 算法分析

采用改進(jìn)灰狼優(yōu)化算法求解,設(shè)置算法的參數(shù)取值如表3 所示.使用Python3.8 語(yǔ)言編程運(yùn)行,實(shí)現(xiàn)改進(jìn)灰狼優(yōu)化算法.經(jīng)過(guò)多次實(shí)驗(yàn)并觀察算法的收斂趨勢(shì).本文發(fā)現(xiàn)將迭代次數(shù)設(shè)置為300 次最為合理.

表3 灰狼優(yōu)化算法參數(shù)取值Tab.3 Grey wolf optimization algorithm parameter values

(1) 與標(biāo)準(zhǔn)灰狼優(yōu)化算法對(duì)比分析

改進(jìn)灰狼優(yōu)化算法是在標(biāo)準(zhǔn)灰狼優(yōu)化算法的基礎(chǔ)上添加遺傳變異操作而設(shè)計(jì)的.為驗(yàn)證改進(jìn)后算法的求解效果,將改進(jìn)灰狼優(yōu)化算法與標(biāo)準(zhǔn)灰狼優(yōu)化算法進(jìn)行實(shí)例對(duì)比分析.

由于設(shè)置的種群規(guī)模和迭代次數(shù)的不同,所得方案的配送總成本也會(huì)有所不同.因此,本文分別在不同的種群規(guī)模和迭代次數(shù)下進(jìn)行了實(shí)驗(yàn).表4 給出了不同迭代次數(shù)下的對(duì)比結(jié)果;表5 給出了不同種群規(guī)模下的對(duì)比結(jié)果.

表4 不同迭代次數(shù)下算法求解效果對(duì)比Tab.4 Comparison of algorithm solution effects under different iterations

表5 不同種群規(guī)模下算法求解效果對(duì)比Tab.5 Comparison of algorithm solution effects under different population sizes

為方便分析,表4 和表5 中均顯示出了改進(jìn)灰狼優(yōu)化算法與標(biāo)準(zhǔn)灰狼優(yōu)化算法的配送成本優(yōu)化水平 (Δz) . Δz的計(jì)算公式為

公式(21)中:z表示標(biāo)準(zhǔn)灰狼優(yōu)化算法的所得方案配送總成本;z′表示改進(jìn)灰狼優(yōu)化算法的所得方案配送總成本.通過(guò)計(jì)算配送總成本的 Δz,可以反映改進(jìn)灰狼優(yōu)化算法的優(yōu)化水平.

從表4 和表5 中可以看出,隨著種群規(guī)模和迭代次數(shù)的增加,2 種算法的運(yùn)行時(shí)間也都在增長(zhǎng).因此,需要設(shè)置合理的種群規(guī)模和迭代次數(shù),以便在時(shí)間允許范圍內(nèi)獲得相對(duì)最佳的配送路徑規(guī)劃方案.此外,根據(jù)表4、表5 中的結(jié)果還可以發(fā)現(xiàn),與標(biāo)準(zhǔn)灰狼優(yōu)化算法相比,改進(jìn)灰狼優(yōu)化算法所得方案的配送總成本的降低比率為14%～ 20%.

可見(jiàn),改進(jìn)灰狼優(yōu)化算法能夠明顯降低配送方案總成本.雖然運(yùn)行時(shí)間比標(biāo)準(zhǔn)灰狼算法慢,但是在可接受的運(yùn)行時(shí)間范圍內(nèi) (大概500 s).

(2) 與遺傳算法對(duì)比分析

通過(guò)與遺傳算法的實(shí)例結(jié)果進(jìn)行對(duì)比,驗(yàn)證改進(jìn)灰狼優(yōu)化算法求解基于訂單拆分策略的容量限制商超配送路徑問(wèn)題的有效性.設(shè)置遺傳算法的交叉概率和變異概率分別為0.65 和0.20,種群進(jìn)化代數(shù) (迭代次數(shù)) 為300,得到問(wèn)題求解過(guò)程的目標(biāo)函數(shù)適應(yīng)度曲線對(duì)比圖如圖7 所示.為了更好地反映兩種算法之間的差距,圖7 中的目標(biāo)函數(shù)值為真實(shí)值擴(kuò)大10 倍后的可視化結(jié)果: 圖7(a)顯示了無(wú)訂單拆分的2 種算法配送總成本變化趨勢(shì)對(duì)比;圖7(b)顯示了有訂單拆分的2 種算法配送總成本變化趨勢(shì)對(duì)比.

圖7 適應(yīng)度變化曲線圖Fig.7 Fitness change curve

從圖7(a)、圖7(b)中可以看出,無(wú)論是否進(jìn)行訂單拆分,改進(jìn)灰狼優(yōu)化算法都比遺傳算法所得配送方案的配送總成本低.這是由于遺傳算法都是直接在迭代過(guò)程中收斂至算法所能得到的最優(yōu)解;而改進(jìn)灰狼優(yōu)化算法則能夠突破局部最優(yōu)解,在更廣的范圍內(nèi)搜索其他更佳的配送方案,最終達(dá)到收斂.

將圖7(a)、圖7(b)進(jìn)行對(duì)比,可以發(fā)現(xiàn),有訂單拆分的適應(yīng)度曲線較沒(méi)有訂單拆分的收斂速度更慢.這是因?yàn)椴鸱謺?huì)使訂單數(shù)量增加,改進(jìn)灰狼優(yōu)化算法的計(jì)算量也會(huì)隨之加大,適應(yīng)度曲線的收斂速度就會(huì)相應(yīng)減慢.所以,過(guò)細(xì)的訂單拆分策略可能導(dǎo)致曲線無(wú)法收斂.但是,合理的訂單拆分能夠更充分地利用車(chē)輛容量,減少使用車(chē)輛數(shù),降低配送總成本,這一點(diǎn)將在4.3 節(jié)詳細(xì)介紹.

4.3 結(jié)果分析

為驗(yàn)證“20/10/5 規(guī)則”的訂單拆分策略的適用性,本文在商超客戶訂單需求量確定的情況下,以總需求量為車(chē)輛容量的1.1 倍～ 3.5 倍,步長(zhǎng)為0.2,設(shè)定車(chē)輛容量限制,分別做了13 組“有”“無(wú)”訂單拆分的對(duì)比實(shí)驗(yàn),分析不同的車(chē)輛容量限制和“有”“無(wú)”訂單拆分對(duì)配送路徑方案總成本的影響.圖8 顯示了在不同的“總需求量∶車(chē)輛容量”下配送總成本在有訂單拆分 (藍(lán)色虛線) 和無(wú)訂單拆分(紅色實(shí)線) 情況下的變化趨勢(shì).

圖8 實(shí)驗(yàn)結(jié)果對(duì)比Fig.8 Comparison of experimental results

從圖8 可以看出,無(wú)論有訂單拆分還是無(wú)訂單拆分,隨著“總需求量∶車(chē)輛容量”的增加,配送總成本呈梯度上升趨勢(shì).此外,當(dāng)總需求量為車(chē)輛容量的1.9 倍和2.9 倍時(shí),有訂單拆分的配送總成本明顯低于無(wú)訂單拆分的情況,即當(dāng)商超客戶總需求量接近車(chē)輛容量的整數(shù)倍時(shí),使用“20/10/5 規(guī)則”,訂單拆分策略效果更好.這是因?yàn)椤翱傂枨罅俊密?chē)輛容量”直接影響車(chē)輛的行駛距離和使用車(chē)輛數(shù),進(jìn)而影響車(chē)輛的行駛成本和派遣成本,造成配送總成本的變化.當(dāng)總需求量接近車(chē)輛容量的整數(shù)倍時(shí),采用訂單拆分策略能夠更充分地利用車(chē)輛容量,提高車(chē)輛容量利用率,減少使用車(chē)輛數(shù),降低車(chē)輛派遣成本,進(jìn)而節(jié)省配送總成本.

為驗(yàn)證訂單拆分策略對(duì)總需求量接近車(chē)輛容量的整數(shù)倍的適用性,以總需求量∶車(chē)輛容量=2.9為例,表6 列出了其具體的商超配送路徑規(guī)劃方案,并在圖9 中對(duì)有訂單拆分和無(wú)訂單拆分的配送路線進(jìn)行了可視化.根據(jù)圖9(a)、圖9(b)的結(jié)果對(duì)比,可以看出,進(jìn)行訂單拆分后有2 個(gè)商超客戶 (?、?) 被服務(wù)了多次,同時(shí)使用車(chē)輛數(shù)也減少了1 輛.

圖9 配送路線圖Fig.9 Delivery route map

表6 商超配送路徑規(guī)劃方案Tab.6 Supermarket distribution routes planning scheme

表7 從總成本、使用車(chē)輛數(shù)和平均車(chē)輛容量利用率這3 個(gè)方面,對(duì)上述商超有無(wú)訂單拆分的配送方案的優(yōu)劣進(jìn)行了對(duì)比分析.從表7 可以看出,當(dāng)總需求量為車(chē)輛容量的2.9 倍時(shí),有訂單拆分的方案比無(wú)訂單拆分的方案配送總成本低了845.42 元,使用車(chē)輛數(shù)少了1 輛,平均車(chē)輛容量利用率高了24.53%;當(dāng)商超客戶總需求量接近車(chē)輛容量的整數(shù)倍時(shí),“20/10/5 規(guī)則”訂單拆分策略能夠充分地利用車(chē)輛容量,減少使用車(chē)輛數(shù),降低配送總成本.

表7 配送方案對(duì)比結(jié)果Tab.7 Delivery plan comparison results

5 結(jié)束語(yǔ)

本文針對(duì)商超配送中所存在的車(chē)輛配載和路徑規(guī)劃問(wèn)題,構(gòu)建了基于訂單拆分的帶容量限制的商超配送路徑規(guī)劃模型;結(jié)合遺傳算法中的變異操作,設(shè)計(jì)改進(jìn)了灰狼優(yōu)化算法并進(jìn)行了求解.通過(guò)實(shí)例分析,與求解CVRP 的代表性啟發(fā)式算法—遺傳算法進(jìn)行了對(duì)比.結(jié)果顯示,本文所提的基于訂單拆分的模型和算法,在解決帶容量限制商超配送路徑規(guī)劃問(wèn)題時(shí)能夠取得良好的效果;特別是通過(guò)選擇合適的車(chē)型使商超客戶總需求量接近車(chē)輛容量的整數(shù)倍時(shí),更能夠充分地利用車(chē)輛容量,降低車(chē)輛的空駛率,減少配送總成本.

通過(guò)真實(shí)案例的驗(yàn)證,本文有以下總結(jié).

(1) 對(duì)于配送中心擁有多種可選車(chē)型的企業(yè),建議其根據(jù)所有商超客戶的全部需求量之和選擇合適的車(chē)型,使商超客戶總需求量接近配送中心車(chē)輛容量的整數(shù)倍.此時(shí),企業(yè)可以采用訂單拆分策略進(jìn)行車(chē)輛配載和路徑規(guī)劃.

(2) 對(duì)于訂單拆分方式,建議企業(yè)按照每個(gè)商超客戶需求量相對(duì)于配送車(chē)輛容量的比例進(jìn)行拆分.由案例分析結(jié)果中各項(xiàng)指標(biāo)的對(duì)比可知,“20/10/5 規(guī)則”的訂單拆分策略可作為企業(yè)進(jìn)行訂單拆分時(shí)的一種良好選擇,企業(yè)也可以根據(jù)實(shí)際情況使用更合適的訂單拆分方式.

(3) 對(duì)于求解算法,本文所提的改進(jìn)灰狼優(yōu)化算法,在可接受的運(yùn)行時(shí)間范圍內(nèi),能明顯降低配送方案總成本,獲得成本更低的商超配送路徑規(guī)劃方案.

本文在設(shè)計(jì)配送方案時(shí),僅考慮了客戶需求量和車(chē)輛容量限制.未來(lái)將會(huì)擴(kuò)展到時(shí)間窗約束、車(chē)型限制、客戶滿意度、客戶需求量變動(dòng)等因素,進(jìn)一步修訂模型;同時(shí),對(duì)于更大規(guī)模的配送路徑問(wèn)題,探究如何提高算法的工作效率,以增強(qiáng)其實(shí)際應(yīng)用效果.