0 引言

新零售是指企業(yè)以互聯(lián)網(wǎng)為依托，通過(guò)運(yùn)用大數(shù)據(jù)、人工智能、區(qū)塊鏈、云計(jì)算、物聯(lián)網(wǎng)等新興技術(shù)，升級(jí)改造商品的生產(chǎn)、流通和銷(xiāo)售過(guò)程以重塑業(yè)態(tài)結(jié)構(gòu)和生態(tài)圈的深度融合線上服務(wù)、線下體驗(yàn)和現(xiàn)代物流的零售新模式。盒馬鮮生是國(guó)內(nèi)首家新零售商超，對(duì)于新零售的發(fā)展具有重要意義。盒馬鮮生的物流配送最大特征在于為線下門(mén)店附近3公里范圍內(nèi)的線上平臺(tái)訂單顧客提供30分鐘內(nèi)的送貨上門(mén)服務(wù)，顧客通過(guò)線上平臺(tái)挑選商品下單購(gòu)買(mǎi)，線下門(mén)店接收到線上平臺(tái)訂單后根據(jù)區(qū)塊鏈中儲(chǔ)存的訂單信息，安排工作人員在10分鐘內(nèi)完成訂單商品的分揀打包，隨后安排配送車(chē)輛在20分鐘內(nèi)完成訂單商品的上門(mén)送貨。盒馬鮮生的物流配送整體環(huán)節(jié)復(fù)雜多變，尤其是在銷(xiāo)售旺季、節(jié)假日等特殊時(shí)期，顧客的需求量增加，容易造成企業(yè)的物流配送效率降低，進(jìn)而使得顧客的滿意度下降。在新零售背景下，企業(yè)的物流配送路徑是物流配送的重要組成部分，因此為了提高企業(yè)的物流配送效率，增強(qiáng)顧客的滿意度，本文基于新零售運(yùn)用的區(qū)塊鏈技術(shù)，選取盒馬鮮生為研究對(duì)象，針對(duì)盒馬鮮生的物流配送特征，通過(guò)分析盒馬鮮生的物流配送路徑優(yōu)化，研究企業(yè)的物流配送路徑優(yōu)化問(wèn)題，具有一定的理論參考價(jià)值和實(shí)際應(yīng)用價(jià)值。

物流配送路徑優(yōu)化問(wèn)題本質(zhì)上是車(chē)輛路徑問(wèn)題。該問(wèn)題最早由Dantzig和Ramser于1959年提出，一經(jīng)提出便吸引了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，目前已經(jīng)產(chǎn)生了大量的研究成果。龐燕等[1]闡述了車(chē)輛路徑問(wèn)題的研究現(xiàn)狀、應(yīng)用場(chǎng)景、求解方法和研究方向。劉爍佳等[2]改進(jìn)了多個(gè)常見(jiàn)的啟發(fā)式算法，分析了基于改進(jìn)啟發(fā)式算法的帶時(shí)間窗的車(chē)輛路徑問(wèn)題。孫滬增等[3]構(gòu)建了帶時(shí)間窗的車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)了基于蟻群系統(tǒng)和局部增強(qiáng)搜索策略的蟻群算法求解該模型。蘇欣欣等[4]構(gòu)建了考慮時(shí)間窗和多配送人員的車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)了禁忌搜索算法求解該模型。李國(guó)明等[5]考慮實(shí)際配送過(guò)程中需求和服務(wù)時(shí)間隨機(jī)可變的特性，構(gòu)建了帶軟時(shí)間窗的隨機(jī)需求和隨機(jī)服務(wù)時(shí)間車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)了混合禁忌搜索算法求解該模型。江雨燕等[6]考慮時(shí)間窗、需求點(diǎn)、需求量、交通等因素，構(gòu)建了考慮多配送中心的動(dòng)態(tài)車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)了改進(jìn)的自適應(yīng)非支配排序遺傳算法求解該模型。因此，本文在分析盒馬鮮生的物流配送路徑優(yōu)化問(wèn)題時(shí)，以允許配送車(chē)輛違反顧客時(shí)間窗約束和最大載重量約束為前提，考慮顧客的時(shí)間窗、配送車(chē)輛的最大載重量等因素，以物流配送成本最小為目標(biāo)，構(gòu)建物流配送路徑優(yōu)化模型，設(shè)計(jì)禁忌搜索算法求解該模型，并通過(guò)實(shí)例分析驗(yàn)證模型的可行性和求解算法的有效性。

1 模型構(gòu)建

1.1 問(wèn)題描述

盒馬鮮生的物流配送路徑優(yōu)化問(wèn)題描述為：盒馬鮮生的某一線下門(mén)店從某一時(shí)刻開(kāi)始每間隔10分鐘接收一次線上平臺(tái)訂單，每一時(shí)間間隔結(jié)束后配送中心根據(jù)區(qū)塊鏈中儲(chǔ)存的訂單信息，安排配送車(chē)輛前往配送中心獲取訂單商品，并于10分鐘后從配送中心出發(fā)前往各自負(fù)責(zé)的顧客位置為其配送訂單商品，完成各自的配送任務(wù)，最終在規(guī)定時(shí)間內(nèi)返回配送中心。

1.2 基本假設(shè)

(1）顧客的需求量不超過(guò)配送車(chē)輛的最大載重量。

(2）一個(gè)顧客由一個(gè)配送車(chē)輛負(fù)責(zé)；一個(gè)配送車(chē)輛負(fù)責(zé)一個(gè)顧客或者負(fù)責(zé)多個(gè)顧客。

(3）配送車(chē)輛的最大載重量、配送車(chē)輛的單次運(yùn)行固定成本、配送車(chē)輛的單位距離行駛成本、配送車(chē)輛違反顧客時(shí)間窗約束的單位延誤時(shí)間懲罰成本和配送車(chē)輛違反最大載重量約束的單位超出重量懲罰成本已知。

(4）配送車(chē)輛保持勻速狀態(tài)行駛，行駛道路交通順暢，不存在擁擠、堵塞等情況。

(5）配送車(chē)輛的數(shù)量充足。

1.3 參數(shù)說(shuō)明

N'：配送中心和顧客的編號(hào)集合，N'={0,1,2,…,N}，N表示顧客的數(shù)量。a,b∈N',a,b=0表示配送中心的編號(hào)；a,b=1,2,…,N表示顧客的編號(hào)。

V'：配送車(chē)輛的編號(hào)集合，V'={1,2,…,V}，V表示配送車(chē)輛的數(shù)量。v∈V',v=1,2,…,V表示配送車(chē)輛的編號(hào)。

Q：配送車(chē)輛的最大載重量。

CF：配送車(chē)輛的單次運(yùn)行固定成本。

CD：配送車(chē)輛的單位距離行駛成本。

CW：配送車(chē)輛違反顧客時(shí)間窗約束的單位延誤時(shí)間懲罰成本。

CQ：配送車(chē)輛違反最大載重量約束的單位超出重量懲罰成本。

Xvab：配送車(chē)輛v是否從a前往b,v∈V',a,b∈N',a≠b。0～1型變量，Xvab=1表示配送車(chē)輛v從a前往b;Xvab=0表示配送車(chē)輛v不從a前往b。

Yva：配送車(chē)輛v是否負(fù)責(zé)顧客a,v∈V',a∈{1,2,…,N}。0～1型變量，Yva=1表示配送車(chē)輛v負(fù)責(zé)顧客a;Xvab=0表示配送車(chē)輛v不負(fù)責(zé)顧客a。

Qa：顧客a的需求量，a∈{1,2,…,N}。

La：顧客a的左時(shí)間窗，a∈{1,2,…,N}。

Ra：顧客a的右時(shí)間窗，a∈{1,2,…,N}。

Dvab：配送車(chē)輛v從a前往b的行駛距離，v∈V',a,b∈N',a≠b。

Tvab：配送車(chē)輛v從a前往b的行駛時(shí)間，v∈V',a,b∈N',a≠b。

Tva,Tvb：配送車(chē)輛v到達(dá)配送中心或者顧客a,b的時(shí)間，v∈V',a∈N',b∈{1,2,…,N}。Tv0也表示配送車(chē)輛v從配送中心出發(fā)的時(shí)間。

T'va：配送車(chē)輛v在配送中心或者顧客a的停留時(shí)間，v∈V',a∈N',T'v0=0。

Tv：配送車(chē)輛v返回配送中心的規(guī)定時(shí)間，v∈V'。

1.4 建立模型

物流配送成本主要由配送車(chē)輛的固定成本、配送車(chē)輛的行駛成本、配送車(chē)輛違反顧客時(shí)間窗約束的懲罰成本和配送車(chē)輛違反最大載重量約束的懲罰成本四個(gè)部分組成，建立以物流配送成本最小為目標(biāo)的物流配送路徑優(yōu)化模型，如式（1）至式（10）所示。

式（1）為目標(biāo)函數(shù)，表示物流配送成本最小。式（2）至式（10）為約束條件，式（2）表示Xvab為0～1型變量；式（3）表示Yva為0～1型變量；式（4）表示顧客的需求量不超過(guò)配送車(chē)輛的最大載重量；式（5）至式（6）表示一個(gè)顧客由一個(gè)配送車(chē)輛負(fù)責(zé)；式（7）至式（10）表示配送車(chē)輛前往配送中心獲取訂單商品，并從配送中心出發(fā)前往各自負(fù)責(zé)的顧客位置為其配送訂單商品，完成各自的配送任務(wù)后最終在規(guī)定時(shí)間內(nèi)返回配送中心。

2 模型求解

禁忌搜索（Tabu Search或者Taboo Search,TS）算法是一種元啟發(fā)式隨機(jī)搜索算法，是一種全局逐步尋優(yōu)搜索算法。該算法利用人類(lèi)的記憶功能誘導(dǎo)跳出局部最優(yōu)解，得到全局最優(yōu)解。本文設(shè)計(jì)禁忌搜索算法求解物流配送路徑優(yōu)化模型，算法設(shè)計(jì)主要包含五個(gè)部分：

(1）生成初始可行解。本文設(shè)計(jì)節(jié)約算法生成初始可行解。

(2）構(gòu)造鄰域結(jié)構(gòu)。鄰域結(jié)構(gòu)是禁忌搜索算法的重要組成部分，主要作用是通過(guò)一個(gè)解產(chǎn)生一個(gè)新的解。本文設(shè)計(jì)鄰域結(jié)構(gòu)為將當(dāng)前最優(yōu)解中的某一條配送路徑中的某一個(gè)顧客插入到另一條配送路徑中，要求只能將一條配送路徑中的一個(gè)顧客插入到另一條配送路徑中，不能將該顧客再插回到原來(lái)的配送路徑中。

(3）禁忌表。禁忌表是禁忌搜索算法的核心，主要作用是記錄在算法的整體搜索過(guò)程中被禁忌的局部最優(yōu)解，即禁忌對(duì)象。禁忌長(zhǎng)度是禁忌表的重要指標(biāo)，主要作用是控制禁忌對(duì)象的數(shù)量。本文設(shè)計(jì)禁忌表為先進(jìn)先出的形式，如果禁忌對(duì)象的數(shù)量超過(guò)禁忌長(zhǎng)度，則先記錄的禁忌對(duì)象先被引退，后記錄的禁忌對(duì)象后被引退。

(4）特赦準(zhǔn)則。本文設(shè)計(jì)特赦準(zhǔn)則為如果候選集中的所有可行解均為禁忌解，則為候選集中的禁忌最好解解除禁忌。

(5）終止準(zhǔn)則。本文設(shè)計(jì)終止準(zhǔn)則為限定算法的最大迭代次數(shù)，以此控制算法的運(yùn)行時(shí)間，如果算法的當(dāng)前迭代次數(shù)超過(guò)最大迭代次數(shù)，則結(jié)束算法。

3 實(shí)例分析

本文選取盒馬鮮生在西安市設(shè)立的太白店為研究實(shí)例，通過(guò)實(shí)例分析驗(yàn)證物流配送路徑優(yōu)化模型的可行性和禁忌搜索算法的有效性。假設(shè)該門(mén)店從第0分鐘開(kāi)始接收線上平臺(tái)訂單，在第一個(gè)10分鐘結(jié)束后共接收到20個(gè)訂單。通過(guò)百度地圖開(kāi)放平臺(tái)中的拾取坐標(biāo)系統(tǒng)獲取配送中心和顧客的經(jīng)緯度坐標(biāo)，并將經(jīng)緯度坐標(biāo)轉(zhuǎn)換為實(shí)際距離（km）坐標(biāo)，使用MATLAB R2020b編寫(xiě)程序，在Intel Core i5 6200U CPU 2.3GHz的筆記本電腦上運(yùn)行，其中配送中心的經(jīng)緯度坐標(biāo)為（108.928 370,34.240 810），實(shí)際距離坐標(biāo)為（32 163.359,7 310.314）。顧客的地址、坐標(biāo)、需求量（kg）和時(shí)間窗（min）如表1所示。

配送中心根據(jù)區(qū)塊鏈中儲(chǔ)存的訂單信息，安排配送車(chē)輛前往配送中心獲取訂單商品，并于第20分鐘從配送中心出發(fā)前往各自負(fù)責(zé)的顧客位置停留3分鐘為其配送訂單商品，完成各自的配送任務(wù)后最終在規(guī)定的60分鐘內(nèi)返回配送中心。通過(guò)實(shí)踐調(diào)研獲取物流配送的相關(guān)信息，假設(shè)配送車(chē)輛可以直線行駛于任意兩點(diǎn)之間，為貼近現(xiàn)實(shí)情況，設(shè)定配送車(chē)輛的行駛距離為兩點(diǎn)之間直線距離的1.5倍；設(shè)定配送車(chē)輛的最大載重量為10kg，配送車(chē)輛的單次運(yùn)行固定成本為5元/次，配送車(chē)輛的單位距離行駛成本為0.5元/km，配送車(chē)輛違反顧客時(shí)間窗約束的單位延誤時(shí)間懲罰成本為1元/min，配送車(chē)輛違反最大載重量約束的單位超出重量懲罰成本為1元/kg，配送車(chē)輛的行駛速度為20km/h。使用MATLAB編寫(xiě)程序，在筆記本電腦上運(yùn)行，設(shè)定算法的最大迭代次數(shù)為100，禁忌表的禁忌長(zhǎng)度為20。運(yùn)行程序得到的物流配送路徑優(yōu)化結(jié)果如圖1和圖2所示，共有七條配送路徑，物流配送成本為52.8元，算法的收斂迭代次數(shù)為36。配送路徑分別為：（1）配送中心—西關(guān)新苑—解家村小區(qū)—配送中心；（2）配送中心—東泰城市之光—西北大學(xué)太白校區(qū)—配送中心；（3）配送中心—廣電小區(qū)—紫薇花園—西安美術(shù)學(xué)院雁塔校區(qū)—配送中心；（4）配送中心—西安醫(yī)學(xué)院高新校區(qū)—糜家橋小區(qū)—太白花園—配送中心；（5）配送中心—西安醫(yī)學(xué)院含光校區(qū)—九錦臺(tái)—唐苑小區(qū)—配送中心；（6）配送中心—西安電子科技大學(xué)北校區(qū)—西北工業(yè)大學(xué)友誼校區(qū)—白廟小區(qū)—配送中心；（7）配送中心—西荷花園—含光小區(qū)—機(jī)關(guān)小區(qū)—金花苑—配送中心。

4 結(jié)論

本文在新零售背景下，通過(guò)分析盒馬鮮生的物流配送路徑優(yōu)化問(wèn)題，研究企業(yè)的物流配送路徑優(yōu)化問(wèn)題?；谛铝闶圻\(yùn)用的區(qū)塊鏈技術(shù)，選取盒馬鮮生為研究對(duì)象，針對(duì)盒馬鮮生的物流配送特征，以物流配送成本最小為目標(biāo)，構(gòu)建了物流配送路徑優(yōu)化模型，設(shè)計(jì)了禁忌搜索算法求解該模型，并通過(guò)實(shí)例分析驗(yàn)證了模型的可行性和求解算法的有效性。結(jié)果表明，本文構(gòu)建的物流配送路徑優(yōu)化模型和設(shè)計(jì)的禁忌搜索算法能夠有效的優(yōu)化盒馬鮮生的物流配送路徑，從而提高盒馬鮮生的物流配送效率，增強(qiáng)顧客的滿意度，對(duì)于優(yōu)化企業(yè)的物流配送路徑具有一定的參考借鑒作用。