雙層過道布置問題的混合整數非線性規劃模型及兩階段改進模擬退火算法

管 超 張則強 朱立夏 毛麗麗

西南交通大學機械工程學院，成都，610031

0 引言

設 施 布 局 問 題 （facility layout problem，FLP）通常以最小化總物流成本為目標，對空間中的設施或設備進行組合優化。據估計，合理的布局優化可以降低生產過程中10%～30%的物料搬運成本［1］，正因為該問題所具有的重要研究意義和實際應用價值，近幾十年來一直受工業界和學術界的關注。

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

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

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

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

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

1 雙層過道布置問題

1.1 問題描述

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

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

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

1.2 基本假設條件

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

1.3 數學模型

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

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

所建MINLP數學模型為

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

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

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

2 求解雙層CAP的ISA算法

2.1 解序列的編碼和解碼

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

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

2.2 改進模擬退火算法

2.2.1 記憶功能

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

2.2.2 改進抽樣過程

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

（1）確定最小抽樣次數Mstep，初始化累記抽樣次數q＝0，初始解s0，并將該初始解作為當前最優解s′best，即s′best＝s0；

（2）狀態產生函數產生新解s1，計算目標增量 Δ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，則執行步驟（6）；否則執行步驟（2）；

（6）輸出當前最優解s′best與f（s′best）。

2.2.3 回火操作

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

2.2.4 設置雙閥值的改進退火過程

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

圖3 改進退火流程圖Fig.3 Flow chart of improved annealing process

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

2.3 算法步驟

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

3 實驗結果與分析

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

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

對于所選24個基準算例，假設貨梯運輸路程h＝10，運用GUROBI軟件，依據2.4節給出的MINLP模型，采用數學規劃法進行求解。經測試，對于設施數目小于13的6個小規模測試問題，GUROBI優化器可在合理時間內找到問題最優解，驗證了所提數學模型的正確性。測試問題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之后仍未找到全局最優解，程序終止時所得局部最優解為3 032.5。由此可知，隨著問題規模的增大，數學規劃方法的計算時間大幅度增加，且難以在合理時間內求解大規模問題。為給所提智能算法求解結果提供參考依據，兼顧求解效率，針對設施數目大于13的測試問題，GUROBI軟件中設置的運行時間為1 200s。將所得結果列于表1，其中，第2列為測試問題名稱，第3、4列表示精確方法求得的目標函數值f0及其CPU運算時間。

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

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

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

表2 算法參數設置1Tab.2 The parameter setting1of algorithms

表3 算法參數設置2Tab.3 The parameter setting2of algorithms

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

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

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

表4 改進模擬退火算法求得的最優設施序列Tab.4 Optimal facility sequence of ISA

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

圖5 ISA算法和SA算法的求解質量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算法在執行176次退火操作后陷入局部最優，此時局部最優值為8 591.0。ISA算法降溫130次之后，求得局部最優解為8 567.0，隨后算法重啟退火過程，進行回火操作，在降溫262次時求得最優解8 505.0。由此可知，ISA算法具有跳出局部最優進行全局搜索的能力。本文在ISA算法中設置了雙閾值，提前結束不必要的局部搜索，因此，ISA算法只需迭代51 506次，少于SA算法的55 080次，且取得了更高質量的解。

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

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

4 結論

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

（2）結合問題特征，提出一種改進模擬退火算法，該算法由改進退火過程與改進抽樣過程構成。通過引入記憶功能以避免遺失搜索過程中遇到的最優設施序列；為進一步提高算法全局搜索能力，在退火過程收斂穩定時引入回火操作，并以此時搜索到的最優解作為初始解進行下一次的降溫過程，試驗證明，該操作增強了算法跳出局部最優的能力；在保證求解質量的前提下，通過設置雙閾值，進一步提高算法求解效率。應用該算法對所選24個不同規?；鶞仕憷M行測試，將所得結果與基本模擬退火算法和GUROBI精確方法運算結果作對比，驗證了所提算法在求解穩定性和求解質量方面具有明顯優勢。

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