基于蟻群算法的應急救援資源調度

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

摘 要：在傳染病疫情突發的情況下，許多地區同時出現需要多種應急救援物資的情況。鑒于災后應急資源配置的特點，以及疫情的特殊性的基礎，建立了單一資源供應點兼顧調度路線可靠性的考慮，能為多個資源需求點協調配送的多目標優化調度模型，提出運用蟻群算法用于求解突發疫情的應急資源調度問題。最終通過算例與仿真，證明蟻群算法可以用于解決該問題。

1.問題描述

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

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

2.模型建立

2.1模型參數

2.2算法模型

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

路徑和過程的各個個體初始的信息分泌量相同，即為常數，螞蟻在尋找食物過程中，會根據之前結果來確定種群尋找路線，規則為“隨機比概率”規則，因此可得，外出尋找食物的螞蟻個體從出發點到目標地點的隨機概率為：

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

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

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

3.算例分析

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

4結論

本篇文章建立的模型解決的是一個資源供應點，向分布在不同地區的多個資源需求點供應一種或者多種所需資源的問題。算例中包含12個城市，網絡結構復雜、計算規模較大，算例分析表明本算法能夠很好地處理大型復雜網絡。

參考文獻

[1]殷玲玲.淺析蟻群算法及其應用[J].價值工程，2019：156-157.

[2]胡夏云.基于蟻群算法的動態車輛調度問題的研究[D].廣東：廣東工業大學，2013.

[3]樂群星.螞蟻算法基本原理及其研究發展現狀[J].社會科學，2005，18（04）：5-6.