基于改進遺傳算法的連鎖便利店配送路徑優化 *

李丹蓮，曹 倩，徐 菲

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

1 引言

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

2 SHVRPDSTW數學模型構建

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

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

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

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

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

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

(6)配送車輛應在客戶規定的時間窗內到達客戶點，若在時間窗后到達，需支付超時懲罰成本；若在時間窗前到達，需等待至客戶點的時間窗起始時間。

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

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

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

2.1 符號表示

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

β：遲到懲罰成本；

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

Km：車型m可用數量，m∈M；

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

εm：車型m運輸單位距離成本,m∈M；

ti,j：從點i行駛到點j的行駛時間，i∈V,j∈D；

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

ci,j：從點i到點j的配送成本,i∈V,j∈D；

gi：客戶點i的需求量，i∈D；

ai：客戶點i的服務時間,i∈D；

wi：客戶點i開始服務時刻,i∈D；

[ei,li]：表示客戶點i的服務時間窗；

2.2 模型公式

本文優化目標為總配送成本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)代表了目標函數中的配送成本計算方法；式(3)表示客戶點j的開始服務時間wj的更新方法；約束(4)表示配送中心每種類型的車輛的使用數量不應超過此類型車輛的可用數量；約束式(5)表示所有車輛均從配送中心出發并且返回配送中心；約束式(6)表示每個客戶點只被服務一次；約束式(7)表示車輛在服務客戶點i后，到達下一客戶點或回到配送中心；約束式(8)表示每條路線的總需求量不高于此路線的配送車輛容量。

3 多染色體遺傳算法設計

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

3.1 染色體的編碼與初始化

每輛車的配送路線只有一條，并且每個客戶點每次只能被一輛車服務。將客戶點和車輛進行編碼：

(9)

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

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

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

3.2 任務分配與適應度計算

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

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

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

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

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

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

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

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

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

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

⑤其他車輛不分配配送任務。

之后根據此分配的任務結合式(1)求出總成本Zt和適應度ft=1/Zt。

3.3 選擇、交叉、變異、逆轉操作

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

Figure 2 Chromosome crossing圖2 染色體交叉

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

Figure 3 Chromosome mutation圖3 染色體變異

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

Figure 4 Chromosome reversion圖4 染色體逆轉操作

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

3.4 算法的整體流程

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

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

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

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

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

步驟6逆轉操作：對每個個體的2條染色體分別進行逆轉操作，并根據逆轉后適應度大小決定是否保留逆轉結果。

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

步驟8對種群重復步驟3～步驟7的操作，直到達到規定迭代輪數R,若達到規定的迭代輪數R，輸出最后一代種群中適應度最高的個體、總成本和其對應的配送任務作為最終結果。

4 實驗分析

4.1 算例設計

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

4.2 實驗結果及分析

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

Table 1 Distribution node set 表1 配送點集合

4.3 算法實現效果與可視化

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

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

Table 2 Comparison of the results of two algorithms

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

Figure 5 Average evolution curves of two algorithms圖5 2種算法平均進化曲線

如圖6所示，客戶點配送總共使用7輛車，車型分別為2,2,2,3,2,1,1，與傳統遺傳算法相比，改進遺傳算法節約了一輛車的購置成本。利用多染色體遺傳算法求解算例的最優配送路徑為: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，表示其從配送中心出發沿經客戶點4,13,14配送貨物，完成任務后返回配送中心。

Figure 6 Delivery route optimization graph based on improved multi-chromosome genetic algorithm圖6 改進多染色體遺傳算法下最優路徑規劃圖

5 結束語

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