郭文強(qiáng)，杜正毅，李 嬪

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

1 引言

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

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

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

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

2 建立問題模型

2.1 模型假設(shè)條件

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

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

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

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

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

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

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

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

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

2.2 符號(hào)說明

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

表1 模型符號(hào)說明表

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

首先，將配送中心編號(hào)定為0，客戶點(diǎn)由英文字母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ī)院所進(jìn)入和離開的車輛數(shù)相等；約束條件式(7)的目的是消除子回路；約束條件式(8)，(9)表示決策變量的取值為0或1。

3 AACGA算法

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

圖1 算法流程圖

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

1)初始車輛的確定

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

(10)

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

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

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

(11)

3) 更新信息素

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

(12)

(13)

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

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

(14)

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

3.2 AACGA算法構(gòu)建

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

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

(15)

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

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

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

(16)

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

3)插入遺傳算子

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

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

Fk=1/Zk

(17)

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

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

圖2 染色體交叉示例圖

4 算例分析

4.1 背景介紹

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

表2 各學(xué)?；拘畔?/p>

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

表3 實(shí)驗(yàn)參數(shù)

4.3 結(jié)果與討論

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

圖5 各算法收斂情況