基于蟻群算法的應(yīng)急救援資源調(diào)度

呂昊彥 張傳虎 王坤 高為超 郭建雄

摘 要：在傳染病疫情突發(fā)的情況下，許多地區(qū)同時(shí)出現(xiàn)需要多種應(yīng)急救援物資的情況。鑒于災(zāi)后應(yīng)急資源配置的特點(diǎn)，以及疫情的特殊性的基礎(chǔ)，建立了單一資源供應(yīng)點(diǎn)兼顧調(diào)度路線可靠性的考慮，能為多個(gè)資源需求點(diǎn)協(xié)調(diào)配送的多目標(biāo)優(yōu)化調(diào)度模型，提出運(yùn)用蟻群算法用于求解突發(fā)疫情的應(yīng)急資源調(diào)度問題。最終通過算例與仿真，證明蟻群算法可以用于解決該問題。

1.問題描述

應(yīng)急救援資源的運(yùn)送問題可以被看做旅行商問題（TSP問題），可以用同樣的方法解決此類問題。

旅行商問題又被叫作為“旅行推銷員問題”，一名旅行商要到達(dá)n座城市，這n座城市分布在不同的位置，旅行商要轉(zhuǎn)遍其中的每一座城市，最終回到出發(fā)點(diǎn)的位置。這就是最直觀簡(jiǎn)單的求最短路徑的問題，因此選擇蟻群算法來解決這一問題。

2.模型建立

2.1模型參數(shù)

2.2算法模型

本篇文章在研究蟻群算法基本模型的過程中，假設(shè)在 n個(gè)不一樣位置的地方有m只螞蟻在尋找它們的食物，螞蟻在這個(gè)過程之間會(huì)尋找確定下一個(gè)未去過的食物地點(diǎn)。同時(shí)，當(dāng)螞蟻把所在區(qū)域食物尋找完成之后，螞蟻會(huì)及時(shí)將行進(jìn)的各個(gè)路徑上的分泌獲得的信息素濃度記錄下來，即。 在覓食過程 t ，覓食路徑節(jié)點(diǎn)的集合C中，不同地點(diǎn)之間的濃度，可用式（2）去表示， 開始時(shí)，非相同

路徑和過程的各個(gè)個(gè)體初始的信息分泌量相同，即為常數(shù)，螞蟻在尋找食物過程中，會(huì)根據(jù)之前結(jié)果來確定種群尋找路線，規(guī)則為“隨機(jī)比概率”規(guī)則，因此可得，外出尋找食物的螞蟻個(gè)體從出發(fā)點(diǎn)到目標(biāo)地點(diǎn)的隨機(jī)概率為：

β表示個(gè)體k在 t 時(shí)由尋找食物出發(fā)位i到下一點(diǎn)j的轉(zhuǎn)移可行性;α 表示個(gè)體在尋找食物過程遇到同類交流的信息物質(zhì)剩余量的誘發(fā)因子;β個(gè)體偶然前進(jìn)的誘發(fā)因素;表示為螞蟻k在下一次尋找食物的目標(biāo)地，tabk 為 tab 表，意義為記錄螞蟻k行動(dòng)路線的觀察表。螞蟻在接下的移動(dòng)路線，不能夠再次去往 tab 表中已經(jīng)存在記錄 的目標(biāo)點(diǎn)。個(gè)體走完所有節(jié)點(diǎn)，并可以形成閉合狀態(tài)。等待所有個(gè)體路線完成，即本次覓食過程迭代完成。下一次螞蟻重復(fù)以上過程進(jìn)行下一次迭代，最后發(fā)現(xiàn)最優(yōu)的路線過程。同時(shí)，螞蟻在行徑過程中，移動(dòng)遵守規(guī)律公式：

q表示為范圍0到1的變量， q0為已經(jīng)在[0，1]范圍內(nèi)的一個(gè)常數(shù)，當(dāng)q的取值大于 q0 時(shí)，尋找下一個(gè)新的路徑點(diǎn)。在螞蟻轉(zhuǎn)移過程中，防止多余信息取代啟發(fā)信息。當(dāng)螞蟻在n個(gè)地點(diǎn)就緒完成，將所有信息更新迭代，螞蟻移動(dòng)行為具有記憶特征，當(dāng)新的記憶涌入會(huì)取代舊的記憶，因此，所有螞蟻個(gè)體在完成每一次循環(huán)以后，所有食物目的地之間的路徑中的信息素濃度會(huì)按照下面公式進(jìn)行更新替換：

式中：為信息揮發(fā)量，同時(shí)1-為揮發(fā)后剩余量ρ 的確定范圍為[0，1];用來表示在t時(shí)間范圍內(nèi)信息素改變的大小;用以表示螞蟻k從出發(fā)點(diǎn)i到目標(biāo)j路徑之間的信息素濃度增量。 終上所述研究得，蟻群算法提出學(xué)者Dorigo.M結(jié)合蟻群行進(jìn)過程中信息素濃度的變化規(guī)律，總結(jié)研究分別獲得了蟻群數(shù)量（Ant-Quantity）、蟻群周期（Ant-Cycle）和蟻群密度（Ant-Density）三種蟻群算法模型，其中，蟻群算法模型，從開始到結(jié)束保證了信息素一直在增量，比其他有較明顯優(yōu)勢(shì)，其具體求解過程如下所示： Ant-Cycle 蟻群算法研究模型：

3.算例分析

現(xiàn)在假設(shè)某一旅行商要遍歷12座城市（從任意一座城市出發(fā)最后返回該城市），12座城市從1至12座的具體坐標(biāo)如表1所示，中心坐標(biāo)為（0，0）;初始化將m=24（實(shí)驗(yàn)證明螞蟻數(shù)是城市數(shù)量2倍左右最好）只螞蟻隨機(jī)的放在12個(gè)城市上，取迭代次Nc=100。

4結(jié)論

本篇文章建立的模型解決的是一個(gè)資源供應(yīng)點(diǎn)，向分布在不同地區(qū)的多個(gè)資源需求點(diǎn)供應(yīng)一種或者多種所需資源的問題。算例中包含12個(gè)城市，網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、計(jì)算規(guī)模較大，算例分析表明本算法能夠很好地處理大型復(fù)雜網(wǎng)絡(luò)。

參考文獻(xiàn)

[1]殷玲玲.淺析蟻群算法及其應(yīng)用[J].價(jià)值工程，2019：156-157.

[2]胡夏云.基于蟻群算法的動(dòng)態(tài)車輛調(diào)度問題的研究[D].廣東：廣東工業(yè)大學(xué)，2013.

[3]樂群星.螞蟻算法基本原理及其研究發(fā)展現(xiàn)狀[J].社會(huì)科學(xué)，2005，18（04）：5-6.