雙層過道布置問題的混合整數(shù)非線性規(guī)劃模型及兩階段改進(jìn)模擬退火算法

管 超 張則強(qiáng) 朱立夏 毛麗麗

西南交通大學(xué)機(jī)械工程學(xué)院，成都，610031

0 引言

設(shè) 施 布 局 問 題 （facility layout problem，F(xiàn)LP）通常以最小化總物流成本為目標(biāo)，對空間中的設(shè)施或設(shè)備進(jìn)行組合優(yōu)化。據(jù)估計，合理的布局優(yōu)化可以降低生產(chǎn)過程中10%～30%的物料搬運(yùn)成本［1］，正因?yàn)樵搯栴}所具有的重要研究意義和實(shí)際應(yīng)用價值，近幾十年來一直受工業(yè)界和學(xué)術(shù)界的關(guān)注。

過道布置問題（corridor allocation problem，CAP）作為一種特殊的布局問題，由AMARAL［2］提出。該問題將一定數(shù)目的設(shè)施布置在過道兩邊，以最小化總物流成本為目標(biāo)，尋求設(shè)施序列的最優(yōu)布置。CAP問題與雙行布局問題［3］相似，但兩者區(qū)別主要在于CAP中相鄰設(shè)施之間沒有間隙，且上下兩行設(shè)施序列均從過道的最左邊同一點(diǎn)開始布局。在工業(yè)制造領(lǐng)域，CAP應(yīng)用于微芯片在集成電路板中的布局設(shè)計、半導(dǎo)體生產(chǎn)線的布局設(shè)計［4］等，具有重要的潛在應(yīng)用價值，因此，該問題自提出以來便快速成為設(shè)施布局領(lǐng)域一個新的研究熱點(diǎn)。

AMARAL［2］建立了CAP的混合整數(shù)規(guī)劃（mixed－integer programming，MIP）數(shù)學(xué)模型，提出3種啟發(fā)式算法，通過大量算例運(yùn)算驗(yàn)證了所提算法的有效性。GHOSH等［5］應(yīng)用混合遺傳算法和結(jié)合路徑再連接的分散搜索算法，對過道布置問題進(jìn)行了求解，進(jìn)一步提高了求解效率。ANJOS等［6］提出了一種針對無間隙多行布局問題的半正定規(guī)劃方法，該方法對小規(guī)模測試問題具有良好的求解效果，針對難度更大的問題也可求得高質(zhì)量的函數(shù)值下限。KALITA等［7］以最小化總物流成本和過道長度為目標(biāo)，通過大量運(yùn)算驗(yàn)證了遺傳算法求解雙目標(biāo)過道布置問題的有效性。

上述文獻(xiàn)均是對單層過道布置問題的研究，然而在實(shí)際生產(chǎn)或服務(wù)部門中，設(shè)施在多層空間中的布局設(shè)計越來越多地被采用。當(dāng)布局場地面積受限時，無法對數(shù)量龐大的設(shè)施進(jìn)行單層過道布置，設(shè)施被迫布局到多層空間；另一方面，設(shè)施的多層布置也可以實(shí)現(xiàn)土地的集約利用并減少占地成本。由此可知，設(shè)施在多層空間中的布局研究越來越有必要。

模擬退火 （simulated annealing，SA）算法在求解組合優(yōu)化問題中表現(xiàn)出良好的求解性能。AHONEN等［8］采用禁忌搜索算法和模擬退火算法分別對不同規(guī)模測試算例進(jìn)行了驗(yàn)算和對比，在求解質(zhì)量和求解效率方面，模擬退火算法性能更加優(yōu)異。韓偉等［9］將模擬退火思想引入溫度參數(shù)以控制權(quán)重的變化率，通過對ESICUP標(biāo)準(zhǔn)運(yùn)算數(shù)據(jù)測試，證明了所提溫控散列函數(shù)能有效提高排樣效率與排樣產(chǎn)出率。祝恒云等［10］將粒子群算法和模擬退火算法有機(jī)結(jié)合，通過實(shí)例仿真驗(yàn)證了所提算法的有效性和實(shí)用性。

本文考慮生產(chǎn)實(shí)際中布局用地成本以及布置場地受限等情況對過道布置的影響，提出了雙層過道布置問題，建立了該問題的混合整數(shù)非線性規(guī) 劃 （mixed-integer nonlinear programming，MINLP）模型。應(yīng)用GUROBI軟件首先對所選24個測試問題進(jìn)行精確求解，驗(yàn)證了模型的正確性；隨后提出一種改進(jìn)的模擬退火 （improved simulated annealing，ISA）算法求解該問題；最后，通過與精確算法和基本模擬退火算法運(yùn)算結(jié)果作對比，驗(yàn)證了所提算法的求解有效性。

1 雙層過道布置問題

1.1 問題描述

單層過道布置問題以最小化物流成本為目標(biāo)，將n個不同形狀的矩形設(shè)施布置到通道兩側(cè)，并確定分配到每一行的設(shè)施數(shù)目、設(shè)施序列以及每個設(shè)施的精確位置。在此基礎(chǔ)上，本文考慮用地成本等因素、布置場地受限等情況對設(shè)施布局的影響，提出了雙層過道布置問題。圖1為該問題示意圖。

圖1 雙層過道布置問題示意圖Fig.1 Schematic diagram of a double layer corridor allocation problem

與傳統(tǒng)過道布置問題相比，雙層過道布置問題考慮設(shè)施在兩層空間中的布置，分配到各層中的設(shè)施沿過道兩邊線進(jìn)行布局。雙層過道布置問題不是單層過道布置問題的簡單疊加，不同層各設(shè)施之間也存在物流交互，且交互通道為放置在過道最左邊的貨梯。結(jié)合該問題特點(diǎn)，需要對各層空間中的設(shè)施進(jìn)行組合排序，期望找到最優(yōu)布置序列，并確定此時各層設(shè)施布置排列順序，從而最小化總物流成本。

1.2 基本假設(shè)條件

為簡化問題作如下假設(shè)：①設(shè)施間物流量和每個矩形設(shè)施靠近過道邊線的寬度為已知量；②各設(shè)施的流量交互中心位于設(shè)施靠近過道邊線的中點(diǎn)；③相鄰兩設(shè)施之間沒有間隙；④上下兩層設(shè)施均從最左邊同一點(diǎn)開始并沿過道兩邊布置，即不同層起始點(diǎn)的橫坐標(biāo)均為0；⑤假設(shè)上下兩層過道的寬度為0；⑥不同層設(shè)施之間通過貨梯進(jìn)行物流交互，且搬運(yùn)距離為貨梯的運(yùn)輸路程；⑦貨梯布置在過道最左邊，即貨梯口與每層過道0橫坐標(biāo)零點(diǎn)重合。

1.3 數(shù)學(xué)模型

為方便描述，模型中出現(xiàn)的數(shù)學(xué)符號的意義如下：n為問題規(guī)模，即需要布置的設(shè)施數(shù)目；設(shè)施編號集合N＝｛1，2，…，n｝；L 為所有設(shè)施長度之和；h為貨梯運(yùn)輸路程；i、j為設(shè)施標(biāo)號，i，j∈N；xi為設(shè)施i在布置中的位置；k為行標(biāo)號，k∈K ＝｛U1，D1，U2，D2｝，其中，U1、D1分別表示第一層中布置設(shè)施的上行和下行標(biāo)號，U2、D2分別表示第二層中布置設(shè)施的上行和下行標(biāo)號；cij為設(shè)施i、j之間的流量成本，i∈I1，j∈I2，I1＝｛1，2，…，n－1｝，I2＝｛i＋1，i＋2，…，n｝；li為設(shè)施i的長度；dij為設(shè)施i和設(shè)施j中心點(diǎn)間的橫坐標(biāo)距離；Lk為布置在k行的設(shè)施總長度。

其中，3種決策變量描述如下：

所建MINLP數(shù)學(xué)模型為

引入三個決策變量：yik表示設(shè)施i是否布置在第k行，若在第k行，則yik＝1，否則yik＝0；zkij表示設(shè)施i、j是否均布置在第k行且設(shè)施i布置在設(shè)施j的左邊，若成立則zkij＝1，否則zkij＝0；Fij表示設(shè)施i、j是否在同一層，若成立則Fij＝1，否則Fij＝0，該變量由yik確定。已知設(shè)施總數(shù)目N、設(shè)施靠過道邊線長度li、設(shè)施間物流成本cij，以最小化總流量成本為目標(biāo)，如式（1）所示。

約束條件說明：式（2）～式（4）為設(shè)施距離約束，其中，式（2）、式（3）用于確定布置在相同層各設(shè)施之間的距離，式（4）確定不同層各設(shè)施之間的距離；式（5）確保每個設(shè)施僅分配至一行；式（6）保證各行均有設(shè)施布置；式（7）防止各層中同行設(shè)施位置發(fā)生重疊放置；式（8）用于計算每行設(shè)施布置的總長度；式（9）、式（10）用于確定xi的取值范圍，其中，式（9）保證第i個設(shè)施絕對位置坐標(biāo)值不小于li／2，式（10）則確定xi的上界為li／2，即設(shè)施i所在行的設(shè)施總長度減去設(shè)施i長度的一半，以此保證不同行設(shè)施布置始點(diǎn)為絕對位置0點(diǎn)；式（11）用于確定決策變量Fij；式（12）與式（13）保證設(shè)施i和j同時位于k行，此時，二進(jìn)制變量zkij或zkji為1。此外，該約束限制zkij和zkji同時為1的情況。如果設(shè)施i和j同時位于k行，則zkij或zkji為1；式（14）～式（16）限定變量取值。

本文將傳統(tǒng)CAP問題擴(kuò)展到雙層過道布置問題，使之更加滿足設(shè)施多層布局的實(shí)際要求。針對雙層過道布置問題的特點(diǎn)，本文考慮了設(shè)施在兩條過道上的布置，并構(gòu)建了相應(yīng)約束以表達(dá)所提問題。雙層過道布置問題是多層布局中的一個特例，其問題復(fù)雜度較單層過道布置問題更大，從模型中可以看出，雙層過道布置問題模型較單層過道布置問題模型約束更多，組合情況由原來的（n－1）n?。?增加為（n－1）（n－2）n?。?，求解難度更大。

2 求解雙層CAP的ISA算法

2.1 解序列的編碼和解碼

根據(jù)所提問題特點(diǎn)，本文采用一種基于設(shè)施序列的表達(dá)方式。雙層過道布置問題作為典型的組合優(yōu)化問題，其可行解序列可由一個有序排列的設(shè)施集合來表達(dá)。以設(shè)施數(shù)目n＝9的問題為例，一個可行解s＝［5 3 1 7 9 6 2 8 4］，其中，u＝5，nu1＝2，nu2＝3，即布置在第一層、第一行的設(shè)施序列為［5 3］，第一層、第二行的設(shè)施序列為［1 7 9］；布置在第二層、第一行的設(shè)施序列為［6 2 8］，第二層、第二行設(shè)施序列為［4］。上述可行解的編碼和解碼如圖2所示。

圖2 解的編碼與編碼Fig.2 Encoding and decoding of solutions

2.2 改進(jìn)模擬退火算法

2.2.1 記憶功能

為避免搜索過程中因執(zhí)行Metropolis接受準(zhǔn)則而遺失當(dāng)前最優(yōu)解，在模擬退火過程中內(nèi)嵌記憶解sbest用于保存搜索過程中所得最優(yōu)解。算法開始時，以初始解s0初始化sbest，即sbest＝s0。算法隨機(jī)搜索過程中，當(dāng)產(chǎn)生新解s1時，則比較f（sbest）與f（s1），其中，f（s）為解序列的圖標(biāo)函數(shù)值。若f（sbest）＞f（s1），則令sbest＝s1，f（sbest）＝f（s1）；否則sbest、f（sbest）不變。通過對f（sbest）和f（s1）的比較，不斷更新sbest，算法終止時輸出的解sbest即為整個搜索過程中的最優(yōu)解。

2.2.2 改進(jìn)抽樣過程

為提高算法求解質(zhì)量，對局部搜索過程進(jìn)行改進(jìn)。本文采用一種自適應(yīng)搜索策略代替原模擬退火算法中固定的馬氏鏈長度，將問題規(guī)模作為算法的抽樣次數(shù)。改進(jìn)的抽樣過程如下：

（1）確定最小抽樣次數(shù)Mstep，初始化累記抽樣次數(shù)q＝0，初始解s0，并將該初始解作為當(dāng)前最優(yōu)解s′best，即s′best＝s0；

（2）狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新解s1，計算目標(biāo)增量 ΔC＝f（s1）－f（s0）；

（3）若ΔC＜0，則s1＝s0，f（s0）＝f（s1），q＝0；否則以概率exp（－ΔC／Tc）接受新解，若s1被接受，則s0＝s1，f（s0）＝f（s1），q＝0，否則保持s0、f（s0）不變，q←q＋1；

（4）比較f（s1）與f（s′best）的大小，若f（s′best）＞f（s1），則令s′best＝s1，f（s′best）＝f（s1）；否則保持s′best與f（s′best）不變；

（5）若q≥Mstep，則執(zhí)行步驟（6）；否則執(zhí)行步驟（2）；

（6）輸出當(dāng)前最優(yōu)解s′best與f（s′best）。

2.2.3 回火操作

由式（17）可知，隨著溫度的降低，算法接受劣解的概率逐漸減小，此時容易陷入局部最優(yōu)。為對解空間進(jìn)行充分搜索，本文加入回火操作，在迭代過程中，若當(dāng)前最優(yōu)解sbest連續(xù)若干次沒有進(jìn)行更新時增大溫度值，并以當(dāng)前最優(yōu)解sbest作為初始解s0重新進(jìn)行搜索，提高獲得全局最優(yōu)解的概率。

2.2.4 設(shè)置雙閥值的改進(jìn)退火過程

為提高算法求解效率，在保證求解質(zhì)量前提下，設(shè)置雙閾值，消除多余迭代次數(shù)。在抽樣過程中，以Metropolis抽樣穩(wěn)定為終止準(zhǔn)則，即在各溫度下當(dāng)前最優(yōu)解s′best連續(xù)Rin（抽樣閾值）次保持不變，則結(jié)束此次抽樣過程；若連續(xù)Rout（退火閾值）次降溫過程中所得的最優(yōu)解sbest保持不變，則認(rèn)為退火過程收斂，繼而進(jìn)行回火操作或跳出降溫過程。改進(jìn)退火過程如圖3所示。

圖3 改進(jìn)退火流程圖Fig.3 Flow chart of improved annealing process

圖3中，參數(shù)cin、cout分別表示抽樣過程中s′best與降溫過程中sbest連續(xù)保持不變的次數(shù)；參數(shù)switch為布爾變量，當(dāng)退火過程收斂，即滿足閾值條件時，若switch＝false，則令當(dāng)前溫度Tc為初始溫度（即Tc＝T），Rout←2Rout／3，升高溫度并降低閾值條件，進(jìn)行下一次的退火操作，否則終止此次退火操作，返回sbest。

2.3 算法步驟

本文所提改進(jìn)模擬退火算法主要對退火過程及抽樣過程進(jìn)行改進(jìn)，具體步驟如圖4所示。圖4中，nu1、nu2分別為布置在第一層第一行和第二層第一行的設(shè)施數(shù)目，Tend為模擬退火算法的終止溫度。

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證雙層過道布置問題模型的正確性，針對設(shè)施數(shù)目從9～49不同規(guī)模的24個基準(zhǔn)算例，首先應(yīng)用數(shù)學(xué)規(guī)劃軟件進(jìn)行精確求解，測試數(shù)據(jù)來源于文獻(xiàn)［2，11-15］。計算試驗(yàn)采用的計算機(jī)硬件配置：CPU 為 E6700＠3.2GHz，內(nèi)存為4GB，在 Windows 7 操作系統(tǒng)下運(yùn)行GUROBI 7.0.1優(yōu)化器求出精確解。

圖4 改進(jìn)模擬退火算法流程圖Fig.4 The flow chart of improved simulated annealing algorithm

對于所選24個基準(zhǔn)算例，假設(shè)貨梯運(yùn)輸路程h＝10，運(yùn)用GUROBI軟件，依據(jù)2.4節(jié)給出的MINLP模型，采用數(shù)學(xué)規(guī)劃法進(jìn)行求解。經(jīng)測試，對于設(shè)施數(shù)目小于13的6個小規(guī)模測試問題，GUROBI優(yōu)化器可在合理時間內(nèi)找到問題最優(yōu)解，驗(yàn)證了所提數(shù)學(xué)模型的正確性。測試問題S9、S9H、S10、S11、Am12a、Am12b的求解時間分別為191.10s、2 263.97s、600.32s、4 749.20s、21 876.65s、26 032.73s，對于測試問題 Am13a，GUROBI軟件求解了48 726.00s之后仍未找到全局最優(yōu)解，程序終止時所得局部最優(yōu)解為3 032.5。由此可知，隨著問題規(guī)模的增大，數(shù)學(xué)規(guī)劃方法的計算時間大幅度增加，且難以在合理時間內(nèi)求解大規(guī)模問題。為給所提智能算法求解結(jié)果提供參考依據(jù)，兼顧求解效率，針對設(shè)施數(shù)目大于13的測試問題，GUROBI軟件中設(shè)置的運(yùn)行時間為1 200s。將所得結(jié)果列于表1，其中，第2列為測試問題名稱，第3、4列表示精確方法求得的目標(biāo)函數(shù)值f0及其CPU運(yùn)算時間。

為驗(yàn)證所提算法求解雙層過道布置問題的有效性，在同一運(yùn)行環(huán)境下使用 MATLAB R2012a軟件開發(fā)了ISA算法和SA算法的試驗(yàn)程序，并應(yīng)用兩算法分別求解24個基準(zhǔn)算例，通過對比運(yùn)算結(jié)果，證明了ISA算法的求解優(yōu)勢。算法參數(shù)設(shè)置方面，為兼顧求解質(zhì)量和求解效率，經(jīng)大量試驗(yàn)測試得相關(guān)參數(shù)，如表2和表3所示，表中“—”表示相關(guān)參數(shù)在算法中沒有設(shè)置。其中，參數(shù)即布置在第一層的設(shè)施數(shù)目u的上限U2＝5、下限U1＝2。通過對傳統(tǒng)過道布置問題的研究可知，當(dāng)過道兩邊設(shè)施數(shù)目相差不大時，總物流成本最小，由此確定nu1與nu2的相關(guān)參數(shù)：T1＝max（1， u／2 －3），T2＝u／2；T1＊＝max（1， （n－u）／2－3），T2＊＝ （n－u）／2，其中， · 表示向下取整。

為準(zhǔn)確對比ISA算法與SA算法的求解性能，針對每個測試問題，兩種算法均運(yùn)行10次，共獲得48 0個計算結(jié)果。為更加簡潔、直觀地表示兩種算法的運(yùn)算特點(diǎn)，對所得數(shù)據(jù)進(jìn)行整理、歸納，并列于表1的第5～16列，各基準(zhǔn)算例的最優(yōu)解及最優(yōu)解序列見表4。其中包含了目標(biāo)函數(shù)f的最小值、最大值、平均值、標(biāo)準(zhǔn)差、解偏差以及平均CPU運(yùn)算時間。平均目標(biāo)函數(shù)值f與f0的偏差定義為（fi－f0）／f0，i＝1，2。

表1 SA算法和ISA算法的計算結(jié)果Tab.1 The calculation results of SA algorithm and ISA algorithm

表2 算法參數(shù)設(shè)置1Tab.2 The parameter setting1of algorithms

表3 算法參數(shù)設(shè)置2Tab.3 The parameter setting2of algorithms

對表1所得結(jié)果分析可知，對于GUROBI所能求得的6個小規(guī)模測試問題，ISA算法均可求得，且求解時間遠(yuǎn)短于GUROBI軟件的求解時間；對于其他規(guī)模的測試問題，ISA算法也可在短于GUROBI的求解時間內(nèi)求得更優(yōu)解，表明了所提算法求解雙層過道布置問題的有效性；針對所選24個測試問題，ISA算法所得目標(biāo)函數(shù)值的最小值、最大值、平均值均不大于SA算法所得結(jié)果，表明ISA算法較SA算法具有更優(yōu)的求解質(zhì)量；ISA算法所得目標(biāo)函數(shù)值f的標(biāo)準(zhǔn)差均小于SA算法所得標(biāo)準(zhǔn)差，且對于測試問題S9、S9H、S10、S11、Am12a、Am12b、Am13a、Am15、Am17，ISA計算結(jié)果的標(biāo)準(zhǔn)差均為0，表明該算法具有更好的求解穩(wěn)定性。

由于本文設(shè)置了回火操作，ISA算法在退火過程收斂時需從初溫開始重啟一次退火操作，因此，所提算法的CPU運(yùn)算時間長于SA算法的求解時間。另一方面，為提高運(yùn)算效率，在ISA算法中設(shè)置了雙閾值，從而減少不必要的迭代運(yùn)算，故對于測試問題S11、Am18、H20、N25＿02、N25＿03、N25＿04、N25＿05，ISA 算法的 CPU 運(yùn)算時間短于SA算法的求解時間。

為更直觀地說明所提ISA算法的求解性能，針對GUROBI軟件所能求得的6個不同規(guī)模測試算例，應(yīng)用本文所提兩種算法重新運(yùn)算60次，并計算兩種算法與精確求解結(jié)果的偏差，繪制偏差箱形圖（圖5），其中，箱線圖的上下框線、中間線，點(diǎn)畫線分別表示該組計算結(jié)果的上下四分位數(shù)、中位值、平均偏差，上下框線之外的延伸線表示最大值（最小值）到上（下）四分位數(shù)的取值區(qū)間，符號“＋”表示不在正常值分布區(qū)間的異常值。由圖5可以看出，ISA算法的平均偏差為0，遠(yuǎn)小于SA算法的平均偏差，說明ISA算法具有良好的求解性能；ISA算法方盒長度為0，而SA算法方盒長度較大，尤其是測試問題Am12b，其偏差取值范圍為0～1.65%，且對于測試問題S9、S10、S11、Am12a，SA算法所得異常值較多，表明ISA算法較SA算法具有更好地求解穩(wěn)定性。

表4 改進(jìn)模擬退火算法求得的最優(yōu)設(shè)施序列Tab.4 Optimal facility sequence of ISA

隨后，為更加詳細(xì)地說明ISA算法的求解特點(diǎn)，選取H20規(guī)模問題，對比ISA算法和SA算法求解該基準(zhǔn)算例的運(yùn)算過程，并繪制了相應(yīng)的算法收斂圖見圖6。此時，部分參數(shù)設(shè)置為u＝2，nu1＝1，nu2＝8，其他參數(shù)如表2、表3設(shè)置。

圖5 ISA算法和SA算法的求解質(zhì)量Fig.5 Quality of solution between ISA algorithm and SA algorithm

圖6 ISA算法與SA算法收斂曲線Fig.6 The convergence curve for ISA algorithm and SA algorithm

從圖6中可以看出，與SA算法相比，ISA算法具有更高的收斂速度和收斂精度。SA算法在執(zhí)行176次退火操作后陷入局部最優(yōu)，此時局部最優(yōu)值為8 591.0。ISA算法降溫130次之后，求得局部最優(yōu)解為8 567.0，隨后算法重啟退火過程，進(jìn)行回火操作，在降溫262次時求得最優(yōu)解8 505.0。由此可知，ISA算法具有跳出局部最優(yōu)進(jìn)行全局搜索的能力。本文在ISA算法中設(shè)置了雙閾值，提前結(jié)束不必要的局部搜索，因此，ISA算法只需迭代51 506次，少于SA算法的55 080次，且取得了更高質(zhì)量的解。

為更加直觀地表現(xiàn)回火操作在ISA算法中的作用，圖7繪制了該算法的迭代過程曲線。算法迭代到26 686次時進(jìn)行回火操作，并將此時搜索到的局部最優(yōu)解作為下一次退火過程的初始解，最終求得全局最優(yōu)解8 505.0，且優(yōu)于回火之前的8 567.0。

圖7 ISA算法迭代曲線Fig.7 The iterative curve of ISA algorithm

4 結(jié)論

（1）針對實(shí)際布局活動中對多層過道布置的需求，本文提出了考慮設(shè)施空間布局的雙層過道布置問題，并建立了該問題的混合整數(shù)非線性規(guī)劃模型。應(yīng)用GUROBI優(yōu)化器對所選24個測試問題進(jìn)行精確求解，驗(yàn)證了所提模型的正確性。

（2）結(jié)合問題特征，提出一種改進(jìn)模擬退火算法，該算法由改進(jìn)退火過程與改進(jìn)抽樣過程構(gòu)成。通過引入記憶功能以避免遺失搜索過程中遇到的最優(yōu)設(shè)施序列；為進(jìn)一步提高算法全局搜索能力，在退火過程收斂穩(wěn)定時引入回火操作，并以此時搜索到的最優(yōu)解作為初始解進(jìn)行下一次的降溫過程，試驗(yàn)證明，該操作增強(qiáng)了算法跳出局部最優(yōu)的能力；在保證求解質(zhì)量的前提下，通過設(shè)置雙閾值，進(jìn)一步提高算法求解效率。應(yīng)用該算法對所選24個不同規(guī)模基準(zhǔn)算例進(jìn)行測試，將所得結(jié)果與基本模擬退火算法和GUROBI精確方法運(yùn)算結(jié)果作對比，驗(yàn)證了所提算法在求解穩(wěn)定性和求解質(zhì)量方面具有明顯優(yōu)勢。

在未來的研究中，將在目標(biāo)函數(shù)中考慮占地成本因素或進(jìn)行多個目標(biāo)的優(yōu)化，進(jìn)一步完善雙層過道布置問題；在求解方法層面，尋求更加優(yōu)異的智能算法，進(jìn)一步提高搜索效率與求解質(zhì)量。