基于改進(jìn)遺傳算法的連鎖便利店配送路徑優(yōu)化 *

李丹蓮，曹 倩，徐 菲

(北京工商大學(xué)電商與物流學(xué)院，北京 100048)

1 引言

便利店的興起緣于超市的大型化與郊外化，是一種能滿足人們需求的便利小超市[1]。學(xué)者將便利店描述為面積100平方左右，主要經(jīng)營非個性化商品，營業(yè)時間長，多為連鎖方式存在[2,3]的商店。連鎖便利店經(jīng)營食品、生活用具等，其中食品還包括了保質(zhì)期短的生鮮水果、便當(dāng)、酸奶等，此外，商店的規(guī)模很小，因此有必要實(shí)施有效且低成本的補(bǔ)貨策略[4]。在實(shí)地調(diào)查后發(fā)現(xiàn)，現(xiàn)北京市的大多數(shù)連鎖便利店(連鎖水果店和一般連鎖店)都為每日補(bǔ)貨一次[5,6]。學(xué)者們對7-11便利店的研究表明，連鎖便利店是基于市場支配戰(zhàn)略進(jìn)行擴(kuò)張，體現(xiàn)形式是在重點(diǎn)區(qū)域內(nèi)集中開店，利用快速密集的布局達(dá)到規(guī)模效益[7,8]。其配送特點(diǎn)為：(1)時間窗口較為集中且十分密集[9,10]；(2)具有一個配送中心[11]；(3)各便利店需求量不同[12]；(4)成本構(gòu)成多樣性[13]。以上幾點(diǎn)決定了這種情況下的連鎖便利店的物流供貨問題屬于單車場多車型帶密集半軟時間窗問題SHVRPDSTW(Single depot Heterogeneous fleet Vehicle Routing Problem with Dense Semi-soft Time Windows)。為了求解此問題， 本文提出了多染色體遺傳算法。

2 SHVRPDSTW數(shù)學(xué)模型構(gòu)建

傳統(tǒng)的連鎖便利店的物流配送是由單車型和單配送中心組成，但每個分店(客戶點(diǎn))的需求量是不同的，單車型在實(shí)際場景中并不靈活，多車型在物流配送中的應(yīng)用會越來越廣泛。因此，為了車輛調(diào)度的靈活性，SHVRPDSTW模型假設(shè)配送車隊由多種車型組成。并且，每個分店(客戶點(diǎn))都具有半軟時間窗，晚于時間窗口到達(dá)的車輛需支付晚到懲罰成本，早于時間窗口到達(dá)的車輛需等待至?xí)r間窗起始時間。SHVRPDSTW可視為VRP(Vehicle Routing Problem)問題的分支，假設(shè)已知各客戶點(diǎn)的需求量以及配送路徑序列和車輛序列，建立數(shù)學(xué)模型,其約束如下所示：

(1)只有一個配送中心，其具有多種車型的配送車輛。

(2)每種車型具有不同的額定載重量、固定成本和行駛成本。

(3)車輛駕駛員的工資將計入車輛的固定成本。

(4)所有車輛從配送中心出發(fā)并最終返回配送中心。

(5)待配送客戶點(diǎn)有各自的需求量、時間窗和卸貨服務(wù)時間。

(6)配送車輛應(yīng)在客戶規(guī)定的時間窗內(nèi)到達(dá)客戶點(diǎn)，若在時間窗后到達(dá)，需支付超時懲罰成本；若在時間窗前到達(dá)，需等待至客戶點(diǎn)的時間窗起始時間。

(7)所有車輛不可超載。

(8)一輛配送車輛可以服務(wù)多個客戶點(diǎn)，每個客戶點(diǎn)只能被一輛車服務(wù)一次。

(9)所有配送車輛均勻速行駛。

2.1 符號表示

設(shè)V為配送點(diǎn)集合，其中0為配送中心，V={0}∪D={0,1,2,…,n}；D為n個客戶點(diǎn)集合；設(shè)M為車型集合，M={0,1,…,h},共計h+1類。模型的相關(guān)變量和參數(shù)表示如下：

β：遲到懲罰成本；

Cm：車型m的額定載重量，m∈M；

Km：車型m可用數(shù)量，m∈M；

ρm：車型m固定成本,m∈M；

εm：車型m運(yùn)輸單位距離成本,m∈M；

ti,j：從點(diǎn)i行駛到點(diǎn)j的行駛時間，i∈V,j∈D；

di,j：從點(diǎn)i行駛到點(diǎn)j的行駛距離,i∈V,j∈D；

ci,j：從點(diǎn)i到點(diǎn)j的配送成本,i∈V,j∈D；

gi：客戶點(diǎn)i的需求量，i∈D；

ai：客戶點(diǎn)i的服務(wù)時間,i∈D；

wi：客戶點(diǎn)i開始服務(wù)時刻,i∈D；

[ei,li]：表示客戶點(diǎn)i的服務(wù)時間窗；

2.2 模型公式

本文優(yōu)化目標(biāo)為總配送成本Z最小化，包括配送距離成本、懲罰成本和固定成本，可描述為式(1)所示：

(1)

(2)

wj=wi+max(ei-wi,0)+ai+ti,j,

w0=0,i≠j,i,j∈V

(3)

(4)

(5)

(6)

(7)

(8)

式(2)代表了目標(biāo)函數(shù)中的配送成本計算方法；式(3)表示客戶點(diǎn)j的開始服務(wù)時間wj的更新方法；約束(4)表示配送中心每種類型的車輛的使用數(shù)量不應(yīng)超過此類型車輛的可用數(shù)量；約束式(5)表示所有車輛均從配送中心出發(fā)并且返回配送中心；約束式(6)表示每個客戶點(diǎn)只被服務(wù)一次；約束式(7)表示車輛在服務(wù)客戶點(diǎn)i后，到達(dá)下一客戶點(diǎn)或回到配送中心；約束式(8)表示每條路線的總需求量不高于此路線的配送車輛容量。

3 多染色體遺傳算法設(shè)計

傳統(tǒng)的遺傳算法求解單車場單車型車輛路徑問題效果較好，但是求解SHVRPDSTW時，由于同時考慮“多車型”和“時間窗”2個約束，解的質(zhì)量將受到影響，甚至存在無解的情況。以下設(shè)計參考陳呈頻等[14]對于多車場多染色體遺傳算法的研究，并在此基礎(chǔ)上加入“時間窗”約束，每個個體被設(shè)定包含2條染色體——配送路徑序列與車輛序列，表示所有可調(diào)用的車輛和其配送路線，有效避免無效解甚至非法解的產(chǎn)生[14]。

3.1 染色體的編碼與初始化

每輛車的配送路線只有一條，并且每個客戶點(diǎn)每次只能被一輛車服務(wù)。將客戶點(diǎn)和車輛進(jìn)行編碼：

(9)

式(9)表示各車型數(shù)量總和，車輛序列染色體順序編碼為：Seqv={1,2,3,…,Vehiclesum}。配送路徑序列染色體順序編碼為：Seqc={0,1,2,3,…,n}，共計n個客戶點(diǎn)，0代表配送中心。

編碼完成后，配送路徑序列染色體隨機(jī)初始化，然后與其對應(yīng)的車輛序列染色體隨機(jī)初始化，如圖1所示。車輛序列染色體代表可使用的車輛及其使用順序；配送路徑序列染色體代表待配送的客戶點(diǎn)的服務(wù)順序。

Figure 1 Chromosome initialization圖1 染色體初始化

3.2 任務(wù)分配與適應(yīng)度計算

個體的適應(yīng)度決定了個體的優(yōu)劣性，決定一個個體在迭代過程中是否可以被保留。根據(jù)個體的配送路徑序列染色體與車輛序列染色體，安排配送任務(wù)并求出適應(yīng)度，流程如下所示：

(1)對于種群中第i個個體，按照其車輛序列染色體選擇一輛可用的車輛，再在其配送路徑序列染色體中順序選擇盡可能多的待配送的客戶點(diǎn)，客戶點(diǎn)總需求量不應(yīng)超過該車輛的額定載重量。

(2)判斷配送路徑序列染色體中的所有客戶點(diǎn)是否已被配送，若存在待配送的客戶點(diǎn)，則返回(1)，若無則轉(zhuǎn)至(3)。

(3)完成任務(wù)分配后，生成種群中第i個個體的配送方案Ji，根據(jù)式(1)計算其總成本Zi。

(4)取第i個個體對應(yīng)的成本Zi，令fi=1/Zi，fi即為第i個個體的適應(yīng)度。

例：設(shè)種群中第t個個體的配送路徑序列染色體為[4,5,6,3,1,2]，其對應(yīng)的客戶點(diǎn)需求量為[300,200,200,400,100,300]；車輛序列染色體為[2,3,1,4,5]，其對應(yīng)的車型為[1,2,2,3,3]，車型對應(yīng)的額定載重量為[300,500,500,400,400]；根據(jù)上述任務(wù)分配方式則可知分配的任務(wù)為：

①安排序號為2車型為1的車輛，服務(wù)路線為：0-4-0；

②安排序號為3車型為2的車輛，服務(wù)路線為：0-5-6-0；

③安排序號為1車型為2的車輛，服務(wù)路線為：0-3-1-0；

④安排序號為4車型為3的車輛，服務(wù)路線為：0-2-0；

⑤其他車輛不分配配送任務(wù)。

之后根據(jù)此分配的任務(wù)結(jié)合式(1)求出總成本Zt和適應(yīng)度ft=1/Zt。

3.3 選擇、交叉、變異、逆轉(zhuǎn)操作

在本文算法中，種群內(nèi)每個個體包含2條染色體——配送路徑序列染色體和車輛序列染色體。染色體的交叉方法為部分映射交叉方法PMX(Partially Mapped Crossover)[15]，如圖2所示。

Figure 2 Chromosome crossing圖2 染色體交叉

根據(jù)變異概率分別變異配送路徑序列染色體和車輛序列染色體。方法是在個體的染色體中使用2-opt算法進(jìn)行變異操作[16]，如圖3所示。

Figure 3 Chromosome mutation圖3 染色體變異

逆轉(zhuǎn)操作是隨機(jī)選取染色體中的2個位點(diǎn)，顛倒兩位點(diǎn)間的基因序列前后順序，并且根據(jù)逆轉(zhuǎn)后的個體的適應(yīng)度決定是否保留逆轉(zhuǎn)結(jié)果。若其適應(yīng)度增大則保留逆轉(zhuǎn)結(jié)果，反之撤銷該操作。如圖4所示。

Figure 4 Chromosome reversion圖4 染色體逆轉(zhuǎn)操作

種群規(guī)模為S,選擇操作通過輪盤賭規(guī)則和代溝選擇參數(shù)PGap(0

3.4 算法的整體流程

步驟1設(shè)置本文算法的參數(shù)：交叉概率Pc、變異概率Pm、種群規(guī)模S和遺傳迭代輪數(shù)R。

步驟2初始化種群：種群中的個體包含的配送路徑序列染色體和車輛序列染色體。

步驟3選擇操作：根據(jù)適應(yīng)度和代溝選擇參數(shù)PGap，選擇S×PGap個個體繼續(xù)交叉、變異、逆轉(zhuǎn)操作后進(jìn)入子代種群，其余S×(1-PGap)個未被選擇的個體直接保留至子代種群。

步驟4交叉操作：根據(jù)交叉概率Pc對被選擇個體的配送路徑序列染色體和車輛序列染色體，分別通過PMX方法進(jìn)行交叉操作生成交叉后的新個體。

步驟5變異操作：根據(jù)變異概率Pm對步驟4生成的新個體，通過2-opt算法變異生成變異后的新個體。

步驟6逆轉(zhuǎn)操作：對每個個體的2條染色體分別進(jìn)行逆轉(zhuǎn)操作，并根據(jù)逆轉(zhuǎn)后適應(yīng)度大小決定是否保留逆轉(zhuǎn)結(jié)果。

步驟7子代種群的生成：經(jīng)過步驟4～步驟6操作后生成的S×PGap個個體，與選擇操作中的S×(1-PGap)個個體組成子代種群。

步驟8對種群重復(fù)步驟3～步驟7的操作，直到達(dá)到規(guī)定迭代輪數(shù)R,若達(dá)到規(guī)定的迭代輪數(shù)R，輸出最后一代種群中適應(yīng)度最高的個體、總成本和其對應(yīng)的配送任務(wù)作為最終結(jié)果。

4 實(shí)驗分析

4.1 算例設(shè)計

本文實(shí)驗中的連鎖便利店的配送中心和25個客戶點(diǎn)均位于北京市城區(qū)，間接模擬真實(shí)配送路徑業(yè)務(wù)場景，通過導(dǎo)航類程序測量客戶點(diǎn)與供貨中心間運(yùn)輸時間和距離,并在Matlab R2016a上與傳統(tǒng)遺傳算法進(jìn)行對比實(shí)驗，用于驗證所提出的多染色體遺傳算法對SHVRPDSTW的有效性和可行性。實(shí)驗的運(yùn)行環(huán)境為Intel Core i5-7200 HQ 2.5 GHz CPU,8 GB內(nèi)存,Windows 10操作系統(tǒng)。

4.2 實(shí)驗結(jié)果及分析

實(shí)驗中車輛分1,2,3類車型共計13輛車，分別對應(yīng)的可用輛數(shù)為5,4,4；容量(千克)為600,800,1 000；單位距離運(yùn)輸成本(元)為5,7,8；固定費(fèi)用(元)為30，40,60。車輛勻速行駛速度(km/h)為40，晚到懲罰(元/分鐘)為5。配送點(diǎn)詳細(xì)信息如表1所示。

Table 1 Distribution node set 表1 配送點(diǎn)集合

4.3 算法實(shí)現(xiàn)效果與可視化

本文算法使用多染色體進(jìn)行遺傳優(yōu)化，為了驗證其有效性，將其結(jié)果與傳統(tǒng)的單染色體(單序列)的遺傳算法的測試結(jié)果進(jìn)行對比。參考熊浩等[18]的算法設(shè)計，構(gòu)建了僅包含配送路徑序列染色體的并沒有逆轉(zhuǎn)操作的單染色體遺傳算法。在同樣實(shí)驗條件和算例中，各算法分別測試10次：迭代輪數(shù)R=1000,種群大小S=100,交叉概率Pc=0.8,變異概率Pm=0.2。

算法運(yùn)行結(jié)果如表2所示，在密集半軟時間窗約束下傳統(tǒng)遺傳算法的平均總成本為2 434.91元，而改進(jìn)遺傳算法求解得到的平均總成本為2 258.83元，改進(jìn)后平均總成本節(jié)約了7.25%。同時也明顯降低了最低和最高總成本約7.23%,9.35%。結(jié)果表明，多染色體遺傳算法能有效提高求解質(zhì)量。

Table 2 Comparison of the results of two algorithms

實(shí)驗的平均進(jìn)化曲線如圖5所示，改進(jìn)后的多染色體的遺傳算法與傳統(tǒng)的單染色體的遺傳算法相比，收斂速度快，且得到的最優(yōu)成本低，能夠有效地防止算法陷入局部最優(yōu)解。由此可得，將車輛序列作為第2條染色體參與遺傳的算法，在求解SHVRPDSTW時，具有更快的收斂速度和更強(qiáng)的全局搜索能力。

Figure 5 Average evolution curves of two algorithms圖5 2種算法平均進(jìn)化曲線

如圖6所示，客戶點(diǎn)配送總共使用7輛車，車型分別為2,2,2,3,2,1,1，與傳統(tǒng)遺傳算法相比，改進(jìn)遺傳算法節(jié)約了一輛車的購置成本。利用多染色體遺傳算法求解算例的最優(yōu)配送路徑為:0→4→13→14→0→22→20→23→19→15→10→0→24→25→0→16→11→18→12→0→17→9→0→2→3→1→8→0→6→7→5→21→0。例如序列為1型號為1的車輛，配送路徑為0→4→13→14→0，表示其從配送中心出發(fā)沿經(jīng)客戶點(diǎn)4,13,14配送貨物，完成任務(wù)后返回配送中心。

Figure 6 Delivery route optimization graph based on improved multi-chromosome genetic algorithm圖6 改進(jìn)多染色體遺傳算法下最優(yōu)路徑規(guī)劃圖

5 結(jié)束語

本文中建立的SHVRPDSTW數(shù)學(xué)模型，屬于具有單一配送中心、供貨時間較為密集、車型選擇多樣的物流供貨場景，可運(yùn)用于連鎖便利店、小型超市、農(nóng)產(chǎn)品超市、中央廚房等的車輛配送路徑規(guī)劃中。針對SHVRPDSTW的復(fù)雜性，提出了改進(jìn)多染色體遺傳算法——建立了車輛序列與配送路徑序列2條染色體。然后與傳統(tǒng)單染色體遺傳算法在Matlab R2016a上實(shí)驗比較，結(jié)果表明，多染色體遺傳算法的配送總成本明顯減少，可求出全局最優(yōu)解，明顯提升了解的質(zhì)量，驗證了改進(jìn)算法的有效性。最后利用改進(jìn)遺傳算法對SHVRPDSTW場景進(jìn)行算例求解，得到優(yōu)化后的配送路徑規(guī)劃，為類似問題提供了可行方案。因此，本文提出的多染色體遺傳算法，可填補(bǔ)在時間窗約束下單一車場多車型密集半軟時間窗車輛路徑規(guī)劃問題空缺，具有一定現(xiàn)實(shí)意義。