王登清

(1. 福州大學(xué)經(jīng)濟(jì)與管理學(xué)院, 福建 福州 350108； 2. 福建船政交通職業(yè)學(xué)院管理工程系， 福建 福州 350007)

0 引言

新零售的概念是馬云率先于2016年10月在阿里云棲大會上提出的. 自誕生以來， 線上線下和物流緊密結(jié)合， 創(chuàng)造了真正的新零售. 目前新零售已發(fā)展為商品流通的新業(yè)態(tài)， 2017年網(wǎng)絡(luò)零售額7.18萬億， 占社會消費品零售總額的19.59%[1]. 新零售物流業(yè)務(wù)更新和迭代進(jìn)一步支撐新零售模式的發(fā)展. 新零售模式下物流配送業(yè)務(wù)對傳統(tǒng)的配送路徑規(guī)劃與優(yōu)化方法提出了新的挑戰(zhàn)， 主要呈現(xiàn)出如下特點： 配送的個性化需求更加強(qiáng)烈, 隨著前置倉數(shù)量的增加物流配送路徑問題更加復(fù)雜, 物流配送目標(biāo)更加多元化等. 研究新零售模式下的物流配送路徑優(yōu)化問題， 以降低國內(nèi)居高不下的物流成本， 具有重要的理論和現(xiàn)實意義.

近年來， 國內(nèi)外學(xué)者對電商物流配送線路優(yōu)化進(jìn)行了大量的研究， 文獻(xiàn)[2-4]對配送中心的線路進(jìn)行研究， 取得了一定的成果， 主要集中在物流成本優(yōu)化上. 國內(nèi)的學(xué)者關(guān)注的是在電子商務(wù)時代網(wǎng)絡(luò)購物者如何實現(xiàn)下訂單后貨物安全快速地送達(dá)， 具體詳見文獻(xiàn)[5-6]. 新零售物流路徑優(yōu)化理論明顯滯后于迅猛發(fā)展的新零售實踐， 僅有文獻(xiàn)[7-8]對其進(jìn)行分析. 在相關(guān)理論基礎(chǔ)上， 本研究針對現(xiàn)有車輛路徑規(guī)劃模型在解決新零售物流線路優(yōu)化問題時存在著靜態(tài)性、 未考慮交通擁堵及忽視個性化配送的局限性情況， 以車輛承載量為約束條件， 綜合考慮物流成本與服務(wù)時效性構(gòu)建新零售物流線路優(yōu)化模型， 并通過改進(jìn)遺傳算法求解該模型， 探索新零售物流線路優(yōu)化問題的新途徑.

1 問題描述與模型構(gòu)建

1.1 問題描述

某電子商務(wù)超市擁有12家門店， 門店不對外營業(yè)， 由總倉的配送中心對旗下門店進(jìn)行配送. 顧客通過APP從網(wǎng)上直接下單， 門店收到顧客訂單后， 門店工作人員直接分揀并盡量在顧客要求的時段內(nèi)配送到指定地址. 貨物先由總倉配送中心配送至門店， 再由門店按照顧客訂單需求數(shù)量、 時間和地點配送給顧客， 本研究需要解決的問題是物流企業(yè)如何在節(jié)省配送費用的同時盡量在指定的時段將貨物送達(dá)門店.

該配送中心車輛有限， 且最大載重量為Qk， 門店對貨物配送時間有一定的要求， 每條線路上的配送車輛早于或晚于顧客要求的配送時間窗將產(chǎn)生時間成本. 本研究根據(jù)道路擁擠狀況合理安排車輛配送路線， 目標(biāo)是達(dá)到配送中心配送費用最小且車輛到達(dá)門店的時間符合要求. 為簡化目標(biāo)問題， 提出如下假設(shè)條件：

1) 配送中心總倉擁有固定的車輛， 并且車型一致， 車輛最大載重量Qk.

2) 每輛車從總倉出發(fā)， 最后回到總倉.

3) 每個門店的需求量不超過車輛載重量Qk.

4) 每個門店客戶需求得到滿足， 并且只被一輛車服務(wù).

5) 配送任務(wù)在門店要求的時間窗內(nèi)完成， 否則產(chǎn)生懲罰成本.

6) 因交通擁堵造成配送時間增加， 考慮擁堵因素導(dǎo)致配送成本的增加.

7) 每條配送路徑的長度不超過車輛一次配送的最大行駛的距離.

1.2 模型構(gòu)建

模型構(gòu)建的參數(shù)與變量說明如下：

N表示配送的門店數(shù)；k表示配送中心車輛數(shù)；Qk表示配送車輛最大載重量；gi表示門店配送量；dij表示i到j(luò)的距離；c0表示車輛每公里運(yùn)輸成本；D表示車輛最遠(yuǎn)行駛距離；qi表示門店i的需求量；c1表示Ei之前到達(dá)門店i等待的單位成本；c2表示li之后到達(dá)門店i的單位時間懲罰成本；ti表示到達(dá)門店i的時間；cijk表示k輛車經(jīng)過ij路線的擁堵系數(shù)；xijk表示第k輛車從第i點行駛至j點， 取值為1， 未經(jīng)過取值為0；yik表示第i個門店由第k輛車配送， 取值為1， 否則為0.

根據(jù)問題的描述和變量說明， 建立新零售多門店模式的下單中心物流配送路徑優(yōu)化模型[9-10]：

(1)

s.t.yik=0或1 (i=1， 2， …,n；k=1, 2, …,m)

(2)

xijk=0或1 (i,j=1， 2， …，n；i≠j, ?k)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

模型中目標(biāo)函數(shù)(1)表示總費用最小， 包含運(yùn)輸費用(含線路擁堵成本)、 等待成本和懲罰成本； 式子(2)～(3)表示變量的定義； 約束(4)表示每個客戶只由一輛車配送； 約束(5)配送任務(wù)覆蓋所有客戶； 約束(6)～(7)表示送貨點車輛唯一性； 約束(8)表示每條配送線路上門店的需求量之和不超過車輛最大載重量； 約束(9)表示每條配送線路長度不超過最大行駛距離D.

2 算法設(shè)計

遺傳算法是一種基于模擬自然進(jìn)化過程搜索最優(yōu)解的方法， 具有使用方便、 魯棒性強(qiáng)、 便于并行處理等優(yōu)點， 但算法的主要遺傳算子是在隨機(jī)狀態(tài)下進(jìn)行迭代搜索， 種群不可避免陷入退化狀態(tài)， 產(chǎn)生局部最優(yōu)狀態(tài). 為避免算子過早進(jìn)入退化狀態(tài)， 本研究擬采用精英選擇策略， 對遺傳算子實施改進(jìn)求解， 以下是詳細(xì)的算法設(shè)計.

2.1 染色體編碼

本研究采用自然編碼方式進(jìn)行編碼， 總倉編碼為0， 使用M輛車向門店進(jìn)行配送， 然后返回總倉.K+M+1的染色體, 其中一條染色體“0987065403210”表示3輛車給9個客戶配送， 第一輛車從總倉出發(fā)， 經(jīng)過9、 8、 7節(jié)點后回到總倉； 第二輛車從總倉出發(fā)， 經(jīng)過6、 5、 4節(jié)點后回到起點； 第三輛車從總倉出發(fā)， 經(jīng)過3、 2、 1節(jié)點后回到起點. 第m輛車從總倉出發(fā)， 經(jīng)過若干節(jié)點后回到總倉， 構(gòu)成第m條路徑.

2.2 初始化種群

根據(jù)遺傳算法原理， 初始化種群需要一定的量使得算法收斂全局最優(yōu). 但種群過大， 會增加計算時間. 為保證群體的多樣性， 防止算法收斂于局部最優(yōu)解， 群體規(guī)模應(yīng)在合理的范圍內(nèi)選擇, 約80個左右. 本研究設(shè)計了最大載重量限制的初始化染色體方法.

步驟1： 從總倉開始， 染色體編碼為0， 然后給1～N的客戶進(jìn)行隨機(jī)編號.

步驟2： 從染色體0的客戶點開始， 隨機(jī)抽取遍歷， 形成一條客戶需求量小于最大載重量Q的線路， 插入其他客戶則大于最大載重量， 在這條線路的最后客戶點插入總倉基因0.

圖1 初始染色體生成示例Fig.1 Sample of the initial chromosomes generated

步驟3： 遍歷染色體新插入基因0后面的客戶點重新進(jìn)行遍歷， 重復(fù)步驟2， 形成第二條線路. 如此反復(fù)， 覆蓋所有客戶點.

步驟4： 在步驟3中的最后一條線路， 當(dāng)客戶總需求小于最大載重量Q時， 直接插入總倉0， 得到一條初始的染色體， 如圖1所示.

2.3 計算適應(yīng)度函數(shù)

適應(yīng)度函數(shù)可以用來評價配送路徑的優(yōu)劣程度， 是獲得最優(yōu)染色體的依據(jù), 對個體進(jìn)行優(yōu)勝劣汰. 配送路徑適應(yīng)度公式表達(dá)為：

(10)

其中:a是常數(shù);Zj是j條配送路徑的運(yùn)輸成本;Z′是種群中最優(yōu)配送路徑的運(yùn)輸成本.

(11)

式中：Pj表示染色體遺傳到下一代的概率， 其中fj表示第j條配送路徑的適應(yīng)度.

2.4 交叉與變異算法

1) 交叉算法. 遺傳算法中最具特色的機(jī)制是交叉和變異算子， 通過基因的交叉與變異， 實現(xiàn)對生物的進(jìn)化. 本研究采用類雙點交叉方法， 現(xiàn)舉例說明, 在父代個體中隨機(jī)選擇交配區(qū)域， 如兩個父代個體及交配區(qū)域選擇如下： 1)A=45|3 216|987，B=93|8 542|716. 2)將AB的交配區(qū)域互放置至前面， 得到A′=8 542|453 216 987，B′=3 216|938 542 716. 3)將A′與B′中與交配區(qū)相同的自然數(shù)刪除， 獲得A″=854 231 697,B″=321 698 547.

2) 變異算法. 由于在選擇機(jī)制中保留了最佳個體的方式， 為保持群體內(nèi)個體的多樣性和有效性， 采取精英選擇策略. 具體策略為： 在父代種群Q(t)中， 計算個體的適應(yīng)度函數(shù)并進(jìn)行優(yōu)劣排序， 將優(yōu)秀的個體進(jìn)行集合R(t)， 再在父代種群中隨機(jī)選取個體進(jìn)行量子變異產(chǎn)生子代種群P(t)， 其中量子變異以量子旋轉(zhuǎn)門更新的方式進(jìn)行[11]. 最后計算集合U(t)=P(t)∪R(t)中個體的適應(yīng)度函數(shù)并進(jìn)行排序， 選擇適應(yīng)度最大的前80個個體組成下一代父代種群. 如果集合U(t)種群的規(guī)模小于80， 則將適應(yīng)度最大的個體添加至新種群， 使其規(guī)模達(dá)到80個后， 進(jìn)行循環(huán). 該策略的優(yōu)點是刪除了相同的種群， 避免陷入局部最優(yōu)， 同時可以提高收斂速度.

3 算例驗證與優(yōu)化分析

某線上超市配送中心擁有最大載重量4 t的車輛6輛， 單車最大行駛距離100 km， 平均車速40 km·h-1， 主要面向12個前置倉配送商品. 車輛單位運(yùn)輸成本c0為8元·km-1，c1=100 元·h-1，c2=150 元·h-1. 擁堵系數(shù)為: 8： 00～9： 00系數(shù)1.3; 9： 00～10： 00系數(shù)1.2; 下午17： 00～19： 00系數(shù)1.4; 其他時間段系數(shù)為1.0. 配送中心標(biāo)號為0， 配送總倉位置坐標(biāo)(85， 60)， 各前置倉的位置坐標(biāo)、 需求量、 服務(wù)時間、 時間窗如表1所示.

表1 各前置倉位置、 需求量、 服務(wù)時間及時間窗

配送總倉每天6點統(tǒng)一發(fā)貨， 從發(fā)貨時間開始計算， 車輛從配送總倉出發(fā)， 經(jīng)過各前置倉后回到總倉， 選擇總成本最小的配送方案.

采用改進(jìn)的遺傳算法求解， 算法參數(shù)如下： 種群規(guī)模N=80， 交叉概率Pc=0.8， 變異概率0.2， 迭代次數(shù)200. 算法運(yùn)行200次發(fā)現(xiàn)目標(biāo)函數(shù)最優(yōu)值5 212.22, 最優(yōu)適應(yīng)度值為0.000 191 86. 與此對應(yīng)的最優(yōu)化路線0-1-5-0-2-7-8-0-6-3-0-4-9-0-10-12-11， 最優(yōu)路線的過程見圖2， 虛線表示最優(yōu)化的配送路徑圖， 實線表示路徑優(yōu)化結(jié)果的過程.

圖3是將改進(jìn)GA和標(biāo)準(zhǔn)GA最優(yōu)適應(yīng)值收斂過程進(jìn)行比較， 在該圖中改進(jìn)GA收斂速度明顯優(yōu)于標(biāo)準(zhǔn)GA. 改進(jìn)GA在迭代次數(shù)超過56次后， 目標(biāo)函數(shù)曲線趨于平緩， 逐步收斂于最優(yōu)適應(yīng)度值， 而標(biāo)準(zhǔn)GA在迭代次數(shù)超過156次后， 曲線趨于平緩. 表2是改進(jìn)GA和標(biāo)準(zhǔn)GA各指標(biāo)比較， 數(shù)據(jù)顯示改進(jìn)GA在車輛數(shù)使用、 總距離、 總成本等指標(biāo)方面要優(yōu)于標(biāo)準(zhǔn)GA.

圖2 車輛配送路徑優(yōu)化路線

Fig.2 Optimized distribution routes for vehicles

圖3 改進(jìn)GA與標(biāo)準(zhǔn)GA最優(yōu)化適應(yīng)值比較

Fig.3 Comparison between the optimal adaptive values of standard GA and improved GA

表2 改進(jìn)GA與標(biāo)準(zhǔn)GA比較

為進(jìn)一步驗證算法的有效性及穩(wěn)定性， 對算法參數(shù)取不同的值， 表3列出參數(shù)的不同取值及對應(yīng)的測算結(jié)果. 不同種群規(guī)模測算表明： 本研究設(shè)計的算法不完全依賴于參數(shù)的取值， 算法有效及穩(wěn)定性較強(qiáng).

表3 不同種群規(guī)模比較

4 結(jié)論

以新零售網(wǎng)上超市的總倉配送中心向前置倉物流配送路徑優(yōu)化為研究對象， 聚焦貨物配送的時效性和成本兩大目標(biāo). 建立新零售模式的下單中心物流配送路線整體優(yōu)化模型, 綜合考慮了運(yùn)輸成本、 道路擁堵程度以及配送業(yè)務(wù)的時效性， 突出解決新零售模式下單中心帶時間窗、 個性化配送的物流路徑優(yōu)化問題， 更加貼近物流行業(yè)的現(xiàn)實需求.

通過算例研究結(jié)果表明， 本研究基于配送時間窗和成本考慮的目標(biāo)優(yōu)化模型及其算法是有效的， 改進(jìn)的遺傳算法運(yùn)行效率更高， 求解結(jié)果對參數(shù)值的變化不敏感， 算法穩(wěn)定可靠. 后續(xù)的研究工作將進(jìn)一步完善模型， 兼顧考慮顧客滿意度、 交通路況復(fù)雜性、 車輛資源增加導(dǎo)致成本提高等因素， 以及適用于多物流配送中心的場合.