基于AACGA算法的校園防疫配送路徑優(yōu)化

郭文強，杜正毅，李 嬪

(新疆財經(jīng)大學(xué)，新疆 烏魯木齊 830012)

1 引言

新冠疫情的出現(xiàn)，各省市需要采取相應(yīng)措施來應(yīng)對重大公共衛(wèi)生突發(fā)事件。在應(yīng)對的過程中，各學(xué)校所需大量防疫用品成為需要解決的問題。在此特殊環(huán)境下，如何實現(xiàn)疫情物資合理有效的配送，滿足各高校的需求的同時節(jié)省運輸成本，是本文要研究的內(nèi)容。

車輛路徑問題(Vehi￣cle Routing Problem，VRP)于1959年由Dantzig等[1]提出。該問題同旅行商問題相似，都是組合優(yōu)化領(lǐng)域中典型的NP難問題，各國學(xué)者研究至今，解決這類問題的方法主要有兩類：精確算法和啟發(fā)式算法。精確算法有分支定界法[2]，動態(tài)規(guī)劃算法等方法。精確算法能夠有效的求出問題的最優(yōu)解，但是隨著訪問客戶點數(shù)量的上升，其算法復(fù)雜度會大量增加，要想解決對應(yīng)問題需要花費大量的時間和費用，故逐漸被淘汰。啟發(fā)式算法有人工蜂群算法[3-4]，禁忌搜索算法[5]，模擬退火法等[6]，這類算法往往通過對過去經(jīng)驗的歸納推理及實驗分析來解決問題，往往能夠較快的得到滿意解，比起精確算法更加實用，從實際決策需求的角度出發(fā)，啟發(fā)式算法更加具有合理性。

蟻群算法[7-9](ant colony optimization，ACO)和遺傳算法[10-12](Genetic Algorithm，GA)在解決VRP問題時使用較為廣泛。蟻群算法的靈感來自于自然界中真實螞蟻的行為，它已被證明是一種對于許多NP難問題完全可接受的啟發(fā)式算法。遺傳算法是一種遵循適者生存原則的進化算法，通過模擬染色體的交叉、變異等操作尋找更好的可行解來解決相應(yīng)的問題。

近年來，為了彌補蟻群算法自身的缺點，提高算法的有效性，國內(nèi)外學(xué)者在蟻群算法和其它算法的融合方面開展了大量的研究。例如文獻(xiàn)[13]基于蟻群算法和遺傳算法的各自特點，提出了把蟻群算法和單種群遺傳算法相結(jié)合的混合算法，文獻(xiàn)[14]提出了A*算法與蟻群算法相結(jié)合的算法，解決了冷鏈物流配送問題等。本文針對這種靜態(tài)融合算法的局限性上，提出一種自適應(yīng)蟻群遺傳算法(adaptive ant colony-genetic algorithms，AACGA)，以烏魯木齊市22所學(xué)校為例，進行VRP問題的仿真模擬，最終實驗結(jié)果證明，該算法在解決這類問題時能夠得到更好的可行解。

2 建立問題模型

2.1 模型假設(shè)條件

根據(jù)本次研究，對疫情配送路徑優(yōu)化模型做出如下假設(shè)：

1)配送車輛為同一種類型的車輛；

2)配送中心(醫(yī)院)只有一個，由該醫(yī)院擔(dān)任對所有(客戶點)學(xué)校的配送任務(wù)。

3)學(xué)校和醫(yī)院所在的地點和對疫情物資的需求量已知。

4)車輛在完成自己的配送任務(wù)后，由當(dāng)前的配送地點駛回醫(yī)院。

5)不考慮城市內(nèi)出現(xiàn)意外突發(fā)事件。

6)車輛行駛的路程和時間成正比，即每輛車所行駛的距離決定了其配送成本。

7)一所學(xué)校不接受多臺車輛的服務(wù)，車輛到達(dá)學(xué)校時要保證滿足該校的需求。

8)一輛車服務(wù)的所有需求點的需求量之和不能超過車輛的額定荷載量。

2.2 符號說明

基于以上描述，本研究構(gòu)建疫情期間物資配送路徑優(yōu)化的數(shù)學(xué)模型，首先對模型中的基本符號進行說明，表1表達(dá)了模型中基本符號的含義。

表1 模型符號說明表

2.3 優(yōu)化函數(shù)的建立

首先，將配送中心編號定為0，客戶點由英文字母i，j表示，決策變量的取值Xijk，yijk分別表示如下

疫情配送優(yōu)化調(diào)度模型如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

xijk=0 或 1 ?i，j，k

(8)

yik=0 或 1 ?i，k

(9)

式中：目標(biāo)函數(shù)式(1)表示使目標(biāo)函數(shù)配送成本最少；約束條件式(2)表示車載配送容量限制，約束條件式(3)表示配送車輛最大距離限制；約束條件式(4)表示每所學(xué)校保證有且只有1輛車為其服務(wù)，約束條件式(5)，(6)為流量平衡約束，即每所學(xué)校及醫(yī)院所進入和離開的車輛數(shù)相等；約束條件式(7)的目的是消除子回路；約束條件式(8)，(9)表示決策變量的取值為0或1。

3 AACGA算法

蟻群算法最開始用于解決旅行商問題(TSP)，現(xiàn)在也廣泛用于路徑優(yōu)化。為了縮短蟻群算法的搜索時間，加快收斂速度，同時達(dá)到全局搜索的效果，本研究采用遺傳算法與其結(jié)合的方式。自適應(yīng)蟻群遺傳算法是在基本蟻群算法的基礎(chǔ)上，對其進行一定的改進，對其中的某些參數(shù)進行自適應(yīng)調(diào)整后，通過在蟻群算法內(nèi)部插入遺傳算子，對蟻群遍歷結(jié)果進行交叉變異等局部搜索操作，最后根據(jù)結(jié)果更新每條路徑中的信息素濃度，從而更好的發(fā)揮蟻群算法中的信息素反饋機制；同時，蟻群算法的正反饋機制同樣作用于遺傳算法的初始種群，也提高了遺傳算法的搜索效率。兩種算法相互融合，提高了算法的尋優(yōu)性能，其算法的流程圖如圖1所示。

圖1 算法流程圖

3.1 基本蟻群算法模型構(gòu)建

1)初始車輛的確定

求解前，需要先確定初始車輛的使用數(shù)目，為了避免車輛不足的情況出現(xiàn)，加入?yún)?shù)θ(0<θ<1)使其具有一定的彈性。初始車輛數(shù)m可由式(10)求得：

(10)

其中，[ ]表示不大于括號內(nèi)數(shù)值的整數(shù)，一般來講，條件越復(fù)雜，則約束越多，θ越小，表示一輛車能容納的貨物越少，本文中取θ=0.85。

2)狀態(tài)轉(zhuǎn)移概率

螞蟻從起始點出發(fā)時，每一步都要選擇要訪問的對象，螞蟻通過路徑上已有的信息素濃度，以及當(dāng)前位置與要訪問地點的距離，來決定其下一步要訪問的每個地點的概率。初始狀態(tài)，各條路徑上的信息素相等，即τij(0)=p(p為常數(shù))，之后螞蟻在訪問各個客戶點的過程中，優(yōu)秀的螞蟻個體不斷更新路徑上的信息素，使得后來的螞蟻更趨向于選擇這些路徑。螞蟻的概率轉(zhuǎn)移公式如式(11)所示

(11)

3) 更新信息素

螞蟻在遍歷過程中通過不斷釋放信息素，使得自己經(jīng)過的路徑信息素的含量增多，同時，路徑上的信息素隨著時間的推移不斷揮發(fā)，從而形成信息素的不斷更新。本文使用antcyclesystem模型進行更新，即螞蟻釋放的信息素含量由其經(jīng)過路徑的整體信息來決定，這種方法更具有全局性。更新規(guī)則為

(12)

(13)

在該式中，Lbest為當(dāng)次迭代中尋找到的最優(yōu)路徑的長度。Q為事前設(shè)定的常數(shù)，其值越大，螞蟻所遺留的信息素濃度越高。式(14)是對當(dāng)前所有路徑所包含的邊(i，j)的信息素更新公式如式(14)

τij(t+n)=(1-ρ)τij(t)+Δτij

(14)

ρ表示信息素?fù)]發(fā)程度，ρ越大，信息素?fù)]發(fā)越快。

3.2 AACGA算法構(gòu)建

1)改進轉(zhuǎn)移概率

為了防止算法收斂緩慢，無法尋找的合適的解。本文引入概率轉(zhuǎn)移參數(shù)r0，0

(15)

當(dāng)r>r0，螞蟻選擇的方式同基本蟻群算法，利用“輪盤對賭”的方式?jīng)Q定下一個前往的地點；當(dāng)r≤r0時，螞蟻直接選擇啟發(fā)函數(shù)與信息素函數(shù)乘積最大的路徑。通過這種方式使得螞蟻能夠更快的尋找到最優(yōu)解。

2)自適應(yīng)概率轉(zhuǎn)移參數(shù)選擇

如果將r0設(shè)為一個固定的值，那r0的取值如果過大或過小，都會對最后的結(jié)果產(chǎn)生較大影響。為了尋找到一個較為合適的r0值，本文對該值進行自適應(yīng)調(diào)整，使r0隨著算法的運行不斷向更合適的方向變化，當(dāng)算法執(zhí)行過一次循環(huán)后，如果找到了更好的解，則表明在局部范圍內(nèi)存在著更優(yōu)解，故增大r0使尋優(yōu)效率增強；如果長時間所尋找到的最優(yōu)解沒有變化，表明算法可能陷入了局部最優(yōu)解，這時需要減小r0的值，使其隨機性變大，促使算法在其它區(qū)域?qū)ふ业礁鼉?yōu)秀的解，具體設(shè)置如式(16)所示

(16)

Zbest為當(dāng)代求得的最優(yōu)解，Nmax為最優(yōu)解保持不變的情況下迭代次數(shù)的上限，λ為一個[0，1]之間的參數(shù)，p為解連續(xù)停滯的代數(shù)。

3)插入遺傳算子

自適應(yīng)蟻群遺傳算法是在蟻群算法的基礎(chǔ)上，將遺傳算子插入到算法內(nèi)部，每當(dāng)所有螞蟻進行完一次周游后，運用遺傳算法中的交叉，變異，局部搜索等操作再次進行優(yōu)化，擴大搜索范圍，最后根據(jù)產(chǎn)生的最優(yōu)個體來更新信息素分布，從而實現(xiàn)全局尋優(yōu)；同時，利用蟻群算法的反饋機制，反作用于遺傳算法上，加強算法的搜索效率。

在所有螞蟻對所在客戶點完成一次周游后，將所有產(chǎn)生的解以染色體的形式表示，并對當(dāng)前產(chǎn)生的染色體進行選擇操作，首先按式(17)計算每條染色體的適應(yīng)度：

Fk=1/Zk

(17)

由該式可知每條染色體適應(yīng)度的值為其對應(yīng)解的倒數(shù)，即成本越低其對應(yīng)的函數(shù)值越高，之后使用輪盤對賭法選擇染色體時更容易被選中。本文中采用精英保留策略，即在父代染色體中適應(yīng)度排在前1/10的染色體直接遺傳到子代，該策略可有效保證好的個體不會通過交叉變異等操作而丟失。

染色體的交叉過程如圖2所示。對于兩個染色體P1，P2隨機產(chǎn)生兩個交叉點X，Y。將各自截取的染色體片段提取出來，連接到對方染色體的頭部形成新的染色體P11，P12。然后去掉原染色體中對應(yīng)序號相同的染色體片段，形成最終染色體PC1， PC2。通過這種方式生成新的解，增加了解的多樣性，有利于尋找到更優(yōu)解。之后通過變異算子，對局部系統(tǒng)中少量的染色體進行變異， 通過隨機交換一條染色體中的片段，使得染色體能夠跳出局部最優(yōu)解，從而在其它范圍進行搜索，有利于解的多樣性。

圖2 染色體交叉示例圖

4 算例分析

4.1 背景介紹

以新冠肺炎疫情為例，疫情期間，新疆省醫(yī)院面對各高校進行防疫物資配送服務(wù)，面向師生供應(yīng)以藥品，口罩等防疫為主的物資。本文選取新疆烏魯木齊市的22所高校為例，根據(jù)防控規(guī)定，各學(xué)校所需的疫情防控物資需要統(tǒng)一進行配送。依據(jù)百度地圖整理每個配送點的經(jīng)緯度，并將這些數(shù)據(jù)通過ARCGIS轉(zhuǎn)化為平面坐標(biāo)。設(shè)定醫(yī)院坐標(biāo)為(0，0)，各個高校的相對坐標(biāo)及對應(yīng)的每日需求補給量與該校的學(xué)生及其教職工人數(shù)有關(guān)，具體數(shù)據(jù)見表2。

表2 各學(xué)校基本信息

4.2 實驗參數(shù)設(shè)置

在AACGA算法中，含有大量參數(shù)，這些參數(shù)的取值往往會影響到最后的結(jié)果，本文經(jīng)過反復(fù)實驗，最終確定使用的參數(shù)如表3所示。

表3 實驗參數(shù)

4.3 結(jié)果與討論

運用MATLABR2018b編程對該算例進行求解運算，在求解目標(biāo)函數(shù)時，對4種算法分別進行測試，并將結(jié)果以圖表的形式呈現(xiàn)出來進行比對。其中，對前文改進的前兩處分別進行測試，得到改進的蟻群算法(IACO)以及自適應(yīng)蟻群算法(AACO)，另外兩種算法為基本蟻群算法(ACO)算法和本文所研究的AACGA算法。

本次仿真中，將這四種算法分別運行10次，并記錄這10次所得出的成本以及收斂代數(shù)，表4展示了這10次實驗所得出的數(shù)據(jù)。通過對比分析，ACO算法所得出的配送成本最大值為219.24，最小值為204.18，平均值為212.76，比較其它算法明顯看出其成本最高；IACO算法所求得的配送成本比起ACO算法有了明顯的提升，最優(yōu)值僅有196.12；AACO算法所得的最優(yōu)解為189.63，相比較前兩種算法而言更為優(yōu)秀，但每次實驗所求得的解相差較大，并不穩(wěn)定。同時，這三種算法的收斂代數(shù)都呈現(xiàn)一個不穩(wěn)定的狀態(tài)，起伏較大。最后，對比前三者可知，AACGA算法所求得的配送成本明顯降低，平均值僅有168.24，而且最佳的收斂代數(shù)明顯提前，且浮動較小，并且結(jié)果穩(wěn)定。圖3對四種算法所得的最優(yōu)解，最差解和均值以圖表的形式展示，能直觀的看出AACGA算法求解結(jié)果明顯優(yōu)于其它三種算法。

表4 運行結(jié)果比較

對照前表的相關(guān)數(shù)據(jù)，取每種算法實驗中所得的最佳結(jié)果放于圖4-圖5中，圖4中的四幅圖分別對應(yīng)了四種算法求得的配送方案路線圖，通過對比不難看出，前三種算法求得的方案，都有著圈內(nèi)交叉的現(xiàn)象，即車輛在行駛過程中產(chǎn)生了不同程度的路徑交叉，耗費了多余的成本，而第四幅圖中的每輛車所行駛的路徑都形成了一個完整無交叉的閉環(huán)，這種方式明顯更為高效，圖5中也展示了這四種方案對應(yīng)的收斂圖，不難看出AACGA算法能夠?qū)崿F(xiàn)更為快速的收斂，也證實該算法的有效性。

圖3 各算法結(jié)果對比圖

5 結(jié)束語

針對原有算法求解車輛路徑問題時的不足，本文融合了遺傳算法和蟻群算法的優(yōu)點，并在算法中引入了參數(shù)的自適應(yīng)調(diào)整，使得種群能夠更好的尋找最優(yōu)解，通過選取實際問題進行多次優(yōu)化仿真模擬，證明該算法能夠有效降低疫情物資配送的運輸成本，加快算法的收斂速度。本文算法適用于在疫情等緊急突發(fā)事件中的物資配送等業(yè)務(wù)，文章本身還有可以延伸思考的地方，為了能夠更符合實際，以后將嘗試更大規(guī)模的，或含有模糊限定條件的例子進行仿真。

圖4 各算法配送方案最優(yōu)解

圖5 各算法收斂情況