多路徑交互環形過道布置問題建模及改進蟻獅算法優化

王沙沙，張則強，劉俊琦，陳 鳳

(西南交通大學 機械工程學院軌道交通運維技術與裝備四川省重點實驗室，四川 成都 610031)

1 問題的提出

系統的規劃和布局對提高工業生產率和服務效率具有重要意義，同時科學合理的設施布局結構有助于提高物料搬運效率并降低物流成本。設施布局問題(Facility Layout Problem, FLP)為系統規劃和布局的關鍵環節，其重要性日益凸顯，作為FLP的一種，過道布置問題[1](Corridor Allocation Problem, CAP)因具有較高的搬運效率而被廣泛應用在實際生產生活中，如行政辦公樓的辦公室[2]、醫院走廊兩側診室[3]和車間等布局問題。因此，CAP研究具有一定的實際應用價值和意義。

AMARAL[1]在2012年首次提出CAP，并建立以最小化加權物流成本為目標的混合整數規劃模型，引起了學者們的廣泛關注，CAP也被更加深入地研究，包括計算方法的改進和問題的進一步拓展。在計算方法方面，AHONEN等[4]、毛麗麗等[5]通過不同智能算法對該問題進行求解，均得到比較理想的計算結果；在問題拓展方面，KALITA等[6]將最小化過道長度加入CAP，不考慮相鄰設施之間的間隙，提出無約束優化雙目標CAP；KALITA等[7]加入新約束，即相鄰設施之間不能有間隙，改進了其所提出的雙目標CAP，并改進遺傳算法(Genetic Algorithm，GA)對新的雙目標CAP進行求解；管超等[8]將CAP擴展到雙層設施布局規劃，提出雙層CAP，兩層之間通過貨梯連接，并對該問題建立了混合整數規劃模型；管超等[9]在2019年又提出雙層過道布置混合整數非線性規劃模型；劉思璐等[10]提出考慮設施深度的CAP，并采用煙花算法進行求解；ZHANG等[11]將過道寬度的約束加入傳統CAP中，利用改進分散式搜索算法進行仿真求解。上述文獻求解問題時均假設過道為直線型，但許多建筑設計并非如此，首尾連通的環形布局同樣廣泛應用，其在大型醫院和商場中最為常見。環形生產線也是常見的生產線布局類型之一[12]，生產線的環形布置適合于物流方向與工序方向相同、總物料進出口設置在一起的生產線(圖1為環形生產線示意圖)；另外，掘進機超寬帶位姿檢測基站、機動車檢機構[13]也會采用環形布局。賈林等[14]在2019年首次提出環形過道布置問題(Annular Corridor Allocation Problem, ACAP)，將面積成本和物流總成本進行無量綱化處理，為環形設施布局的研究奠定了基礎，但其將所有物流交互路徑均設置在環形過道中線，并未考慮設施布置在過道同側與不同側時進行交互的區別，與實際生產情況存在一定差異。

蟻獅優化(Ant-Lion Optimizer, ALO)算法是Seyedali Mirjalili[15]于2015年提出的一種啟發式算法，該算法模擬自然界中蟻獅的捕食機制，通過輪盤賭法構建陷阱、螞蟻隨機游走、螞蟻掉進陷阱、螞蟻滑向陷阱底部、捕獲獵物和重建陷阱5個主要的捕食步驟來實現全局尋優，在改進搜索、避免局部最優和收斂性等方面具有良好的性能。該算法自提出以來，在熱液與風力發電調度問題[16-17]、經濟負荷分配[18]、無人機航跡規劃[19]、配電網優化調度[20-21]等方面均有應用，而且計算結果較好。例如，黃長強等[19]針對基本ALO算法在解決三維航跡規劃時能力不足的問題，引入混沌調節因子和反調節因子，提高了算法的探索能力和開發能力。

綜上所述，為探究多路徑交互對ACAP的影響，本文提出劃分3條不同物流交互路徑的多路徑交互ACAP，從而進一步優化物流成本，減輕物流沖突。其次，鑒于改進蟻獅優化(Improved Ant-Lion Optimizer, IALO)算法在求解類似問題中顯示出的優勢，本文提出一種將隨機行走機制與迭代機制融合，根據迭代次數增大動態化處理隨機行走機制的IALO算法，對所提問題進行求解。

2 多路徑交互環形過道布置問題的數學模型

2.1 問題描述

文獻[14]在提出ACAP時，假設其交互路徑唯一?？紤]到環形過道布置在優化過程中，多路徑交互方式和環形過道寬度的動態性特點對物流總成本的影響，采用多路徑交互來緩解單一路徑擁堵的問題，可以使該問題的研究更符合實際生產情況。多路徑交互ACAP可以描述為兩個主要過程：①將n個設施分為兩組，分別計算兩組設施的長度，以設施長度較長的序列作為外圈，較短序列作為內圈；②將內外兩圈設施序列從同一映射半徑進行布置并首尾相連，組成同心圓環，完成對環形過道的布置。

由于環形過道布置過程中設施位置和長度的不確定性，其環形過道寬度隨設施布置位置的變化而變化，即內外兩圈設施長度變化時，過道寬度也隨之變化；另外，由于ACAP的特點，過道寬度對物流成本有一定影響，在動態優化ACAP的基礎上，根據同圈異圈劃分兩種不同的交互方式，如圖2所示，設施序列為[1 2 3 4 5 6 7]，將其從位置4分為[1 2 3 4]和[5 6 7]兩組設施序列，計算兩組設施的長度，假設[1 2 3 4]序列較長，將兩組設施以加粗虛線為環形過道設施布置起點，兩組設施沿順時針布置，最后在外圈增設外部交互出入口X。當兩個設施處于同圈時，其設施之間的交互路徑為過道邊線，如圖2中設施1和設施2之間的距離為d12，設施5和設施6之間的距離為d56；當兩個設施位于異圈時，其設施之間的交互路徑為過道中線，交互距離近似為兩個設施投影到過道中線長度d15和過道寬度e之和，例如圖2中設施1和設施5之間的距離為d15+e。

2.2 主要假設條件

(1)設施的長度和設施之間的單位加權物流交互成本為已知量。

(2)以環形過道中心加粗虛線所在位置為設施布置的起點位置。

(3)每個設施的物流交互點均處于過道邊線中點，設施寬度暫不考慮。

(4)由于增設外部交互出入口X，將其設為布置起點，為便于對比計算，將其長度簡化為0，而且所有物流交互不穿越布置起點。

(5)設施布置不受場地約束和限制。

2.3 數學模型

為了便于表達，給出數學模型中各個數學符號的定義，如表1所示。

表1 數學模型中參數的定義

對比CAP和ACAP，多路徑交互ACAP要考慮物流交互路徑的不同以及過道寬度的變化，在此基礎上，以最小化物流成本為目標，建立基于動態過道的多路徑交互ACAP的數學模型：

(1)

s.t.

-Xij+Xik+Xjk-Xji+Xki+Xkj≤1,

i,j,k∈N，i

(2)

-Xij+Xik-Xjk+Xji-Xki+Xkj≤1,

i,j,k∈N，i

(3)

Xij+Xik+Xjk+Xji+Xki+Xkj≥1,

1≤i

(4)

Yij=Xij+Xji,1≤i,j≤n，i≠j；

(5)

1≤i

(6)

1≤i

(7)

1≤i

(8)

(9)

(10)

Xij,Yij∈{0,1},1≤i,j≤n,i≠j。

(11)

其中：式(1)為目標函數，表示所有設施間的單位距離物流成本與實際運輸距離乘積的最小值，位于不同圈設施間的實際運輸距離包括過道寬度e，用1-Yij判斷設施i和設施j是否在不同同圈，dij+e(1-Yij)表示設施間的實際運輸距離；約束條件(2)～約束條件(5)用于確定決策變量Xij和Yij，Xij確保設施在排列時分成兩圈，并確定排列時各個設施的相對位置；約束條件(6)～約束條件(8)計算各設施直線排列時的交互距離，用于近似表示設施間的弧線距離；約束條件(9)表示外圈設施的總長度，即設施交互距離矩陣中的最大值與其對應的兩個設施長度一半之和；約束條件(10)計算過道寬度，與直線型過道布置問題不同，ACAP中的過道寬度會隨布局變化而變化，因此需要計算過道寬度e，即外圈對應半徑與內圈對應半徑的差值，并限制其大于0，以保證兩圈設施不會出現重疊；約束條件(11)為決策變量Xij和Yij的取值范圍。

3 求解多路徑交互環形過道布置問題的改進蟻獅算法

3.1 蟻獅算法介紹

ALO算法是一種用于分布式優化問題的新算法，其靈感來源于自然界中蟻獅捕食螞蟻的行為。蟻獅在沙子里挖一個圓錐形的洞并躲在圓錐的底部，等待螞蟻掉進洞里。當螞蟻不幸掉到蟻獅洞里時，蟻獅向上噴沙子使螞蟻掉到圓錐底部，然后將其吃掉。一次捕食行為結束后對坑進行修補，等待下一只獵物出現。陷阱和蟻獅的質量通過這樣的過程不斷提高。

蟻獅算法模型主要分為5步：

(1)通過輪盤賭法構建陷阱

輪盤操作根據蟻獅的適應度值選擇一只蟻獅。蟻獅的適應度值越高，其健康狀況越好，所構建的陷阱也越好，因此有更高的幾率捕捉到螞蟻。蟻獅的位置和適應度值分別用矩陣表示如下：

(12)

(13)

式中：ALi,j表示第i只蟻獅在第j維上的位置；f表示適應度函數。

(2)螞蟻隨機游走

螞蟻位置

(14)

式中Ai,j表示第i只螞蟻在第j維上的位置。

用如下公式表示螞蟻的隨機行走：

Xt=[0,cumsum(2r(t1)-1),0,cumsum

(2r(t2)-1),…,0,cumsum(2r(tn)-1)]。

(15)

式中：cumsum表示累積和；t為迭代次數；n為螞蟻數量；r(t)表示隨機函數，當產生的隨機數大于0.5時，r(t)=1，否則r(t)=0。

螞蟻位置的優劣由適應度函數表示。螞蟻的適應度值保存在矩陣MOA中。

(16)

(3)螞蟻掉進陷阱

螞蟻隨機行走受蟻獅陷阱的影響，用式(17)和式(18)對此進行數學解釋，表明螞蟻被要求在一個由向量c和d定義的超球體內圍繞選定的蟻獅移動。

(17)

(18)

(4)螞蟻滑向陷阱底部

蟻獅一旦意識到陷阱里有螞蟻，就會從陷阱中心向外噴射沙子，使螞蟻滑向陷阱底部。

(5)捕捉螞蟻并重建陷阱

(19)

表示第t次迭代中，第i只螞蟻被第j只蟻獅捕食，即蟻獅種群更新。

ALO算法將每次迭代的精英蟻獅保存下來，若迭代未完成，則回到初始位置重新構建陷阱，重復進行捕捉操作，直到迭代結束。

3.2 改進蟻獅算法

原始ALO算法主要求解連續性問題，對離散問題的求解相對較少，為了將ALO算法應用到多路徑ACAP中，在原始ALO算法的基礎上對其結構進行調整，以求解所提問題，主要進行兩部分結構改進，具體如下：

(1)蟻獅衍生螞蟻種群

原始ALO算法隨機產生初始ALO種群和初始螞蟻種群，局部尋優能力相對較差。為了改善算法的局部尋優能力，IALO算法只生成初始蟻獅，不再同時生成螞蟻。改進算法采用輪盤賭法選擇一個較優蟻獅后，對其進行蟻獅衍生螞蟻變異操作，產生局部螞蟻種群，并更新蟻獅，進行蟻獅種群更新迭代。蟻獅衍生螞蟻變異操作方式如圖3所示，圖中隨機在(1，n)開區間內生成兩個整數對應蟻獅位置MAL，將兩個MAL的中間序列進行逆向排序來衍生螞蟻，然后根據問題規模的不同設置螞蟻種群Q組。

(2)動態化隨機游走

根據迭代次數的取值范圍選定隨機游走操作次數。在進行初始求解時，為了提高算法的全局尋優能力，將隨機游走次數和初始蟻獅種群設置為較大值，隨著迭代次數的增大，得到的精英蟻獅越來越接近最優解，在該過程中，隨著迭代次數的增加，逐漸減小螞蟻隨機游走的操作次數，以減少后期操作的計算量，提高計算速度與計算效率。在求解時，調整螞蟻種群Q，以減少螞蟻隨機游走操作，實現動態化的隨機游走過程。具體過程如下：將迭代次數分為(0,0.2Nmax]，(0.2Nmax,0.4Nmax]，(0.4Nmax,0.6Nmax]，(0.6Nmax,0.8Nmax]，(0.8Nmax,Nmax]5個階段，在不同迭代階段選擇不同的衍生螞蟻種群規模，隨著迭代次數的增加，隨機游走次數減小，將5個階段分別對應的隨機游走次數設置為Q，?0.8Q?，?0.6Q?，?0.4Q?，?0.2Q?。具體操作如圖4所示。

3.3 改進蟻獅算法偽代碼及步驟

IALO算法的偽代碼如下：

Initialize the first population of ants and antlions randomly

Calculate the fitness of antlions for MOAL

Find the best antlions and assume it as the elite(determined optimum)

While i

for every ant

Select an antlion using Roulette wheel

Create a random walk around the selected antlion

Update the position of ant

End for

if(ant is fitter than antlion)then

Replace antlion with its corresponding ant

end

Update elite if an antlion becomes fitter than the elite

end while

Return elite and its fitness

IALO算法的具體操作步驟如下：

步驟1初始化參數。設置問題規模n、最大迭代次數Nmax、蟻獅初始種群規模M、動態游走步長最大值Q。

步驟2判斷當前迭代次數i

步驟3對蟻獅種群進行輪盤賭操作，選擇較優蟻獅，保留蟻獅位置和適應度值。

步驟4根據輪盤賭選擇蟻獅位置、當前迭代次數、最大迭代次數，然后根據當前迭代次數i選擇游走步長，螞蟻在輪盤賭產生的蟻獅周圍進行動態隨機游走操作，產生螞蟻種群。

步驟5更新當前螞蟻位置MA和適應度值MOA。

步驟6蟻獅捕食螞蟻，更新蟻獅種群的位置MAL和適應度值MOAL，以及精英蟻獅位置和適應度值。

步驟7轉步驟2。

步驟8達到設置的最大迭代次數，停止循環并輸出結果。

IALO算法流程圖如圖5所示。

4 計算結果與分析

本文所做的所有算例測試試驗均在Window 10操作系統下進行，計算機硬件配置為：Intel(R)Core(TM)i5-8265U，主頻1.8 GHz，內存8 GB。計算軟件所用版本為Lingo 11和MATLAB R2016b。

為了驗證混合整數規劃模型的正確性，本文采用精確求解軟件Lingo 11求解小規模多路徑交互ACAP，結果對測試算例S5～S8均求得最優解，驗證了模型的正確性。然后將精確求解結果與IALO算法計算結果進行對比，對于測試算例S5～S8，IALO算法均可求到與Lingo 11相同的解，證明了IALO算法的正確性。IALO算法的部分參數設置為：問題規模為n時，最大迭代次數Nmax隨問題求解難度和最優解的穩定性而定，設置初始蟻獅個數為M，螞蟻隨機游走為(0, 0.2Nmax]，(0.2Nmax,0.4Nmax]，(0.4Nmax,0.6Nmax]，(0.6Nmax,0.8Nmax]，(0.8Nmax,Nmax]5個階段，對應的游走向上取整次數分別為Q，?0.8Q?，?0.6Q?，?0.4Q?，?0.2Q?。對于不同規模問題，經過20次測試算例試驗，IALO算法的具體參數設置如表2所示。

表2 IALO算法參數設置

采用Lingo 11和IALO算法求解中、大規模算例的比較如表3所示，可見對于8規模算例，IALO算法的求解時間為1.14 s，Lingo的求解時間為3 057 s，證明IALO算法具有明顯的優越性；對于9～15規模算例，由于自身局限性以及問題的復雜程度，Lingo不能在較短時間內求得全局最優解，將其計算時間設置為3 600 s，求得局部最優解，與IALO的計算結果進行對比，11規模算例的Lingo局部最優解為4 169.296，IALO算法求解結果為3 570.105，求解時間為23.91 s，解偏差gap=14.37，說明采用精確軟件Lingo求解較大規模問題時的精確求解質量和效率均已不能滿足要求；對于25～49之間的大規模測試算例，Lingo軟件在3 600 s內不能給出計算結果，IALO算法在合理的時間內均求得最優值或近似最優值。

表3 Lingo 11與IALO算法的求解結果比較

為了驗證算法對ACAP的求解性能，采用IALO算法對文獻[14]考慮面積成本的雙目標ACAP 13組算例的不同規模問題進行10次求解，結果顯示IALO算法均可求得最優值或近似最優值，而且對于30規模以內的10組算例，IALO算法的求解時間為0.04 s，0.22 s，0.64 s，1.67 s，6.39 s，7.07 s，11.47 s，22.67 s，235.67 s，446.73 s，均優于改進禁忌搜索(Improved Tabu Search, ITS)算法；對于40規模以上的3組算例，IALO算法的求解時間為989.25 s，903.24 s，2 108.36 s，其中在42規模算例，IALO算法的計算時間較短，在40規模和49規模算例，ITS算法的計算時間較短，即IALO算法和ITS算法對40規模以上算例的求解效率互不占優?？偠灾?，在兼顧求解質量和求解時間的前提下，采用IALO算法求解文獻[14]中的問題具有一定優勢，如表4所示。

表4 求解結果對比

文獻[14]采用單一路徑交互方式計算物流成本，考慮到交互過程中可能出現擁堵，本文采用多路徑交方式進行計算。為了驗證多路徑交互求解該問題的效果，編寫文獻[14]的單一路徑物流交互程序，在相同參數設置下，采用IALO算法分別對單一路徑交互方式和多路徑交互方式進行計算，結果顯示多路徑交互比單一路徑有明顯的改善，其中對于30規模，單一路徑的最優值為66 592.147，多路徑交互的最優值為63 734.217，改善率為4.29%，如表5所示。

表5 環形單一路徑交互與多路徑交互對比

通過分析表3～表5可知，IALO算法對單一路徑和多路徑ACAP有良好的求解效率和質量，將其與GA和禁忌搜索(Tabu Search，TS)算法進行對比，進一步驗證IALO算法的有效性和優越性，結果如表6所示?？梢?，在兼顧求解質量和時間的前提下：

表6 GA、TS算法和IALO算法的計算結果對比

(1)對比算法最優值偏差gapGA算法只有1組算例未出現最優值偏差，其求解S10算例的最優值偏差最大為5.04，TS算法和IALO算法均有3組未出現最優值偏差，TS算法在求解30規模算例時的最優值偏差最大為2.90，IALO算法在求解25規模算例時的最優值偏差最大為3.67，說明相對于GA，TS算法和IALO算法的求解穩定性相對較好。

(2)對比算法均值Avg14組對比算例中，GA中有13組算例的均值均大于TS算法和IALO算法。對比TS算法和IALO算法，14組算例中，IALO算法有9組算例的均值比TS算法優，有3組算例的均值和TS算法相同，有2組算例(S8和S9H)的均值比TS算法差。通過以上數據可以看出，GA的求解質量相對較差，TS算法的求解質量相對較好，IALO算法的求解質量最優。

(3)對比算法求解最優值或近似最優值Min針對14組對比算例，將3種算法求得的最小值作為最優值或近似最優值，GA有6組算例求得最優值或近似最優值，TS算法有8組算例求得最優值或近似最優值，IALO算法在14組算例均求得最優值或近似最優值，說明IALO算法相比GA和TS算法具有良好的尋優能力。

(4)對比算法求解時間t14組算例中，GA的求解時間均大于TS算法和IALO算法。對比TS算法和IALO算法，14組算例中，IALO算法有10組算例的求解時間比TS算法少，有4組算例的求解時間比TS算法長。在兼顧求解質量的情況下，GA對該問題的求解效率相對較差，TS算法的求解效率一般，IALO算法的求解效率良好。

綜上所述，在求解多路徑ACAP時，相比GA和TS算法，在求解效率和求解質量等方面，IALO算法均表現出良好的求解能力。

由表6的計算結果繪制GA、TS算法和IALO算法14組測試算例均值對比圖，如圖6所示。由表6和圖6可見，IALO算法14組算例的求解結果均屬最優值或近似最優值，其對應的14組均值為128.481，287.051，409.280，669.801，1 225.040，2 319.039，1 437.134，3 578.092，3 573.255，8 964.207，65 034.132，64 081.489，14 920.095，23 558.016，以上數據表明IALO算法在多路徑交互ACAP上具有良好的求解性能。

根據表6的計算結果比較3種算法，由于GA的求解質量和時間相對較差，繪制TS算法和IALO算法箱型圖，如圖7所示。從圖7和表6可見，IALO算法求解各種規模算例的平均偏差為0，0，0，1.18，0.79，0.19，1.75，0.95，1.15，3.67，2.03，1.59，1.33，0.93，而TS算法的平均偏差為0，0，0，0.54，1.40，0，1.97，1.35，1.62，2.42，2.90，2.04，0.68，0.72，說明TS算法和IALO算法均表現出良好的求解能力，但在兼顧求解時間的情況下，IALO算法具有更好的求解效率和質量。

5 結束語

針對現有ACAP中物流交互路徑設置在過道中線，忽略設施位于環形過道同圈與異圈物流交互區別的不足，本文結合實際生產，研究了以最小化總物流成本為目標的多路徑交互ACAP。

針對這一新問題建立混合整數規劃數學模型，通過精確求解小規模算例驗證了模型的正確性。然后設計了一種利用蟻獅衍生螞蟻種群，并將隨機行走機制和迭代次數進行關聯和動態化處理的IALO算法，改進了原始算法的搜索能力。將該算法應用于不同規模實例，分別與精確方法和3種啟發式方法進行比較，結果表明該方法具有良好的求解質量和效率。

本文并未考慮設施布置方向不同對布局的影響，未來研究可根據實際情況對ACAP進行進一步拓展，如設施方向可變的ACAP、多層ACAP、多約束ACAP等。