劉 娜，張 璽，石超峰

(1.重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074；2.重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074)

2020年春節(jié)伊始，新型冠狀病毒疫情首先在武漢出現(xiàn)，隨后迅速籠罩到全國。疫情防控當(dāng)前，確保社區(qū)居民生活物資的供應(yīng)與配送成為政府工作的重中之重。無接觸式配送響應(yīng)疫情態(tài)勢，各地社區(qū)推廣生活物資統(tǒng)一購辦方式，創(chuàng)新“商超+社區(qū)”配送模式確保居民基本生活用品配送，具體的物資配送流程見圖1。商超到各個(gè)社區(qū)的配送路徑優(yōu)化是物資供應(yīng)保障高效化、及時(shí)化的核心環(huán)節(jié)，是打贏疫情防控攻堅(jiān)戰(zhàn)的關(guān)鍵所在。因此，對社區(qū)商超物資配送路徑進(jìn)行優(yōu)化研究刻不容緩。

圖1 物資配送流程

在快遞、大型超市商場物流配送等行業(yè)車輛路徑規(guī)劃有廣泛的應(yīng)用前景。文獻(xiàn)[1]建立總距離最短的混合整數(shù)規(guī)劃模型，使用Lingo11.0對其求解，得到合理的生活垃圾收運(yùn)路徑。文獻(xiàn)[2]考慮配送路徑、載重、時(shí)間窗限制并以配送費(fèi)用最低、配送時(shí)間最小建立模型，結(jié)合遺傳算法并運(yùn)用大數(shù)據(jù)平臺對其求解。文獻(xiàn)[3]以總配送時(shí)間最低為目標(biāo)函數(shù)，應(yīng)用Beam-PSO優(yōu)化算法對模型進(jìn)行處理。文獻(xiàn)[4]研究帶有越庫策略的生鮮農(nóng)產(chǎn)品配送問題，提出以總成本為目標(biāo)的模型。文獻(xiàn)[5]提出一種兩階段的禁忌搜索算法,研究開放式的第三方物流家具配送問題。

旅行商問題(Traveling Salesman Problem，TSP)屬于車輛路徑規(guī)劃的特例，是經(jīng)典的組合優(yōu)化問題。目前，對解算TSP問題方法的研究已成為熱點(diǎn)。近年來，啟發(fā)式算法作為有效求解TSP問題的現(xiàn)代智能算法被普遍使用，較為熱門的有遺傳算法、螞蟻算法、離散蝴蝶算法、神經(jīng)網(wǎng)絡(luò)等。其中，文獻(xiàn)[6]對混合遺傳模擬算法做出改進(jìn)且應(yīng)用于TSP優(yōu)化中，該算法對中小規(guī)模的算例求解精度較高。文獻(xiàn)[7]使用2-opt改進(jìn)遺傳算法中的變異與交叉算子，并應(yīng)用到某灑水配送實(shí)際案例中來減少行程。文獻(xiàn)[8]考慮分工合作的思想，結(jié)合改進(jìn)的聚類蟻群算法，提出1種顯著減少運(yùn)行時(shí)間的分層遞進(jìn)算法來求解大規(guī)模TSP問題。文獻(xiàn)[9]針對TSP的松弛問題，通過進(jìn)行一系列線性整數(shù)規(guī)劃求解，提出有效生成子回路消除約束的方法來極大地提高算法的求解效率。文獻(xiàn)[10]為提高算法的搜尋能力，在煙花算法中引入混沌優(yōu)化思想來解決TSP問題。文獻(xiàn)[11]利用貪婪機(jī)制，利用模擬退火算法與優(yōu)化的2-opt算子，設(shè)計(jì)1種改進(jìn)離散蝴蝶優(yōu)化算法。本文將疫情期間社區(qū)商超生活物資配送路徑問題轉(zhuǎn)化為TSP問題，以湖北省黃石港區(qū)為研究對象，將SOM神經(jīng)網(wǎng)絡(luò)算法、遺傳算法求解的結(jié)果進(jìn)行對比分析，遺傳算法優(yōu)化能力更加突出，使用遺傳算法的物資配送路徑優(yōu)化既能減少人員流動，又能使商超在疫情期間快速得到配送方案，提高配送效率，為社區(qū)居民提供堅(jiān)實(shí)的物資保障。

1 疫情下社區(qū)物資配送路徑規(guī)劃問題

1.1 問題描述

疫情影響下某區(qū)域內(nèi)各社區(qū)居民在網(wǎng)上挑選物資下單后，商超匯總需求后分派車輛對不同區(qū)段進(jìn)行物資配送，每個(gè)區(qū)段均由1輛卡車負(fù)責(zé)配送，對n個(gè)社區(qū)逐一配送且每個(gè)社區(qū)只經(jīng)過1次，最后卡車返回配送中心，求1條配送行程最短的路徑。該問題即TSP問題，可以用1個(gè)圖(Graph)來描述：V={c1,c2,…,ci,…,cn}，i=1,2,…,n是所有社區(qū)的集合；ci表示第i個(gè)社區(qū)，n為社區(qū)數(shù)目；E={(r,s):r,s∈V}是所有社區(qū)間連接的集合；C={cr,s:r,s∈V}是所有社區(qū)之間的距離，即求解只能訪問1次圖G=(V,E,C)中所有社區(qū)并返回原出發(fā)社區(qū)，使訪問行程最短。

1.2 數(shù)學(xué)模型

模型符號定義如下：

dij：社區(qū)i與社區(qū)j間的距離；

n：所要配送的社區(qū)數(shù)目；

V：所有配送的社區(qū)集；

U：所有配送的社區(qū)集的真子集，U?V；

TSP數(shù)學(xué)模型如下：

(1)

(2)

(3)

(4)

xij∈{0,1}，i,j∈V，i≠j.

(5)

其中，式(1)為以最小化社區(qū)配送路徑總距離的目標(biāo)函數(shù)；約束(2)(3)表示保證每個(gè)社區(qū)有且僅有1次被配送；約束(4)表示保證配送路徑中不會產(chǎn)生子回路解；約束(5)表示決策變量的取值，如果已經(jīng)對該社區(qū)配送，則xij=1；如果未對該社區(qū)配送，則xij=0。

2 求解算法

2.1 SOM算法

自組織映射網(wǎng)絡(luò)(Self-Organizing Maps，SOM)[12]是1981年由芬蘭專家Kohonen提出。它具有自組織、自適應(yīng)功能，類似于人腦特性，可自動學(xué)習(xí)到樣本的基本屬性與內(nèi)部規(guī)則，改變網(wǎng)絡(luò)結(jié)構(gòu)。目標(biāo)是將高維空間里的所有點(diǎn)用低維空間中的點(diǎn)來表示，盡量維持點(diǎn)間距離與拓?fù)潢P(guān)系。

SOM為層次型結(jié)構(gòu)。典型結(jié)構(gòu)是輸入層加輸出層。其中，輸入層通過接受外圍信息獲得輸入模式，傳給輸出層；輸出層從輸入模式的分析比較中總結(jié)獲得規(guī)律并分類。TSP問題屬于典型的NP難問題[13]，無法應(yīng)對線性的復(fù)雜度問題，SOM網(wǎng)絡(luò)尋優(yōu)能力強(qiáng)，無需監(jiān)督可自動學(xué)習(xí)到樣本數(shù)據(jù)的輸入模式，最終得到1條優(yōu)化后的最短路徑。

SOM算法解決TSP問題的具體步驟如下[14]：

1)神經(jīng)元位置隨機(jī)初始化，分布于城市坐標(biāo)四周。

2)隨機(jī)挑選1座城市，找到獲勝神經(jīng)元，即距離該城市最近的神經(jīng)元。采用歐式距離作為距離度量。

3)周圍的神經(jīng)元按高斯分布向獲勝神經(jīng)元移動。具體調(diào)整規(guī)則如式(6)所示。

Wt+1=Wt+α(t)g(t,N)d(c,Wt).

(6)

式中：Wt+1為當(dāng)前的神經(jīng)元；Wt為先前迭代的神經(jīng)元值；α(t)為學(xué)習(xí)率；g(t,N)為獲勝神經(jīng)元的鄰域函數(shù)；d(c,Wt)為神經(jīng)元與獲勝神經(jīng)元間的距離。

4)若學(xué)習(xí)率達(dá)到設(shè)定閾值或迭代次數(shù)，則繼續(xù)步驟5)，否則再重新執(zhí)行步驟2)。

5)以神經(jīng)元順序輸出最短配送路徑及長度。

2.2 遺傳算法

遺傳算法(Genetic Algorithm，GA)[15]是把問題模擬為1個(gè)生物進(jìn)化過程來隨機(jī)搜尋最優(yōu)解的方法，充分展現(xiàn)了自然界優(yōu)勝劣汰、適者生存的規(guī)律。1975年由美國教授J.Holland首先提出[16]。由于GA算法有很多優(yōu)良的特性，干擾因素少，直接對個(gè)體進(jìn)行操作，對解決TSP問題有很大的優(yōu)勢。

遺傳算法求解TSP問題的具體步驟如下[17]：

1)編碼并進(jìn)行種群初始化。這里采用整數(shù)編碼的方法。

2)選擇適應(yīng)度函數(shù)。適應(yīng)度值直接反映對應(yīng)回路的優(yōu)劣，適應(yīng)度值定義為目標(biāo)函數(shù)值的倒數(shù)，即

(7)

目標(biāo)函數(shù)值越小，適應(yīng)度值越大，對應(yīng)產(chǎn)生的回路解越好。

3)計(jì)算個(gè)體的適應(yīng)度值，進(jìn)行選擇操作。從舊群體中挑選個(gè)體到新群體，被選中的概率與個(gè)體的適應(yīng)度值成正比，取值越大，選中的概率就越大。

4)交叉、變異操作。操作的父代交叉算子選用部分映射交叉，隨機(jī)選擇兩個(gè)個(gè)體完成交叉操作；變異算子選用交換變異算子，隨機(jī)選擇兩個(gè)變異點(diǎn)并對換位置。

5)進(jìn)化逆轉(zhuǎn)操作。這里的逆轉(zhuǎn)操作是單方向性的。逆轉(zhuǎn)后認(rèn)可適應(yīng)度值有提高的個(gè)體，不然無效。

6)判斷是否完成進(jìn)化次數(shù)，若未達(dá)到要求則執(zhí)行操作3)，否則繼續(xù)下一步。

7)輸出路徑圖。根據(jù)以上步驟取得結(jié)果并輸出最短配送路徑軌跡。

3 案例比較與分析

3.1 案例說明

本文以疫情期間湖北省黃石港區(qū)為實(shí)例對該區(qū)商超物資配送路徑優(yōu)化問題進(jìn)行研究。該區(qū)共有32個(gè)社區(qū)需要提供生活物資供給服務(wù)，商超考慮到配送效率與各社區(qū)的配送距離有關(guān)，要合理地規(guī)劃物資配送車輛路徑。根據(jù)位置地圖得到各個(gè)社區(qū)位置坐標(biāo)如表1所示。

表1 社區(qū)位置坐標(biāo)

3.2 算法比較

本文采用MATLABR2016b編程，分別對SOM和GA兩種求解算法進(jìn)行實(shí)現(xiàn)。不同算法下，將程序獨(dú)立重復(fù)運(yùn)行30次，求出該區(qū)商超物資配送路徑優(yōu)化解，并對算法結(jié)果比較分析。為保證算法的有效性及準(zhǔn)確性，經(jīng)過多次參數(shù)實(shí)驗(yàn)測試，在SOM算法中，設(shè)定學(xué)習(xí)率為0.8，學(xué)習(xí)率衰減率為0.999 97，領(lǐng)域值衰減率為0.999 7，最大迭代次數(shù)為10 000；在GA算法中，設(shè)定N=100，Pc=0.9，Pm=0.06，MAXGEN=200。通過運(yùn)行算法記錄得到的兩種算法平均數(shù)據(jù)對比如表2所示。

首先，從表2分析得知，GA算法的平均運(yùn)行時(shí)間相對較小，同時(shí)得到的平均路徑距離也相對較短；兩種算法的優(yōu)化迭代次數(shù)相差巨大，GA算法迭代僅160次左右就可搜索到距離為23.5 km的最優(yōu)路徑，而SOM算法要迭代8 000次即GA算法迭代次數(shù)的50倍才可搜索出最優(yōu)配送路徑。明顯看出，GA算法的收斂速度快，搜尋最優(yōu)路徑的能力較

表2 2種算法運(yùn)行結(jié)果比較

強(qiáng)，擁有更高的收斂性能及尋優(yōu)精度。其次，在實(shí)驗(yàn)過程中發(fā)現(xiàn)，SOM算法收斂性密切依賴于求解問題的拓?fù)浞植迹?dāng)分布無規(guī)律時(shí)很難得到理想結(jié)果，GA算法則與其無關(guān)，在可接受時(shí)間內(nèi)一定能尋到一個(gè)優(yōu)化路徑，雖然非最優(yōu)，但基本可滿足需求。綜上分析，GA算法對路徑配送優(yōu)化問題求解的性能更優(yōu)，效果更佳。

3.3 結(jié)果分析

在疫情攻堅(jiān)戰(zhàn)中，綜合考慮求解精度與收斂速度，為保障居民生活物資生命線，及時(shí)生成配送路徑，應(yīng)用GA算法對該區(qū)物資配送方案進(jìn)行詳細(xì)地分析。由最近鄰點(diǎn)算法得到初始配送路徑距離為63.2 km，初始配送路線見表3，初始路徑見圖2。通過GA算法優(yōu)化后的路徑距離為23.5 km，比初始路徑減少39.7 km，優(yōu)化后的路徑距離為初始路徑距離的37.2%?？梢姡珿A算法優(yōu)化后配送距離極大降低，配送成本明顯減少。最終優(yōu)化后的配送路線見表4，軌跡圖及進(jìn)化過程分別見圖3、圖4。

表3 初始配送路線

圖2 初始路線

圖3 優(yōu)化后的軌跡

圖4 進(jìn)化過程

同時(shí)，針對GA算法中參數(shù)種群規(guī)模N及最大迭代次數(shù)MAXGEN的變化進(jìn)一步驗(yàn)證分析。對不同取值的N和MAXGEN重復(fù)做20次運(yùn)算，計(jì)算平均最優(yōu)值。不同N與MAXGEN取值下平均最優(yōu)解見圖5、圖6。

圖5 不同N下平均最優(yōu)值的變化

圖6 不同MAXGEN下平均最優(yōu)值的變化

觀察圖5、圖6可知，隨著種群規(guī)模與迭代次數(shù)的增加，平均最優(yōu)值減小，解的平均最優(yōu)性增大，算法收斂到最優(yōu)解的概率會增大。由于算法具有隨機(jī)性，平均最優(yōu)值的變化并不是單調(diào)的，會出現(xiàn)相鄰規(guī)模反復(fù)的現(xiàn)象。在實(shí)驗(yàn)過程中發(fā)現(xiàn)參數(shù)值的設(shè)置與最終求解結(jié)果聯(lián)系緊密，參數(shù)設(shè)置的不合理可能會導(dǎo)致所求的解不一定是最優(yōu)解，增加種群數(shù)目及迭代次數(shù)有利于最優(yōu)解的獲得，商超可減少物資配送時(shí)間，提高物資供給效率。

4 結(jié)束語

本文在考慮新型冠狀病毒肺炎疫情影響下，對社區(qū)商超物資配送路徑優(yōu)化問題進(jìn)行了研究。運(yùn)用SOM和GA兩種算法到湖北省黃石港區(qū)社區(qū)物資配送案例中，由案例結(jié)果比較發(fā)現(xiàn)：GA算法擁有更高的求解精度及收斂速度，優(yōu)化后的路徑距離為初始路徑距離的37.2%，能夠迅速而精確地獲得最優(yōu)配送方案。而后又展開分析種群規(guī)模、迭代次數(shù)等重要參數(shù)對配送方案的影響，優(yōu)化后的結(jié)果可顯著加快商超配送速度，節(jié)約配送成本，及時(shí)快速地完成社區(qū)配送任務(wù)，紓解因疫情為居民生活帶來的眾多不便，保障社區(qū)居民基本生活需求，推動疫情態(tài)勢不斷朝著好的方向發(fā)展。未來可考慮社區(qū)對物資配送車輛有時(shí)間條件要求的前提下，引入時(shí)間窗的限制，研究含有時(shí)間約束的社區(qū)商超物資配送路徑優(yōu)化問題，使得居民需求得到進(jìn)一步的滿足。