羅蓉娟，戢守峰　

（東北大學(xué)　工商管理學(xué)院，遼寧　沈陽　110167，E-mail：sfji@mail.neu.edu.cn）

基于罰函數(shù)的設(shè)施定位布置問題模型與算法

羅蓉娟，戢守峰

（東北大學(xué)工商管理學(xué)院，遼寧沈陽110167，E-mail：sfji@mail.neu.edu.cn）

摘要：針對系統(tǒng)內(nèi)部設(shè)施布置決策，以定位布置問題為研究對象，提出了一種求解該問題的改進(jìn)分布估計算法（IEDA）。通過分析定位布置問題的基本特征，建立了帶容量約束的基本非線性整數(shù)規(guī)劃模型；引入了基于罰函數(shù)的約束處理方法建立了定位布置問題的改進(jìn)數(shù)學(xué)模型，進(jìn)而使用帶懲罰項的目標(biāo)函數(shù)引導(dǎo)IEDA的搜索方向；在IEDA中融入了一種概率矩陣變異機制和基于互換型鄰域結(jié)構(gòu)的局部搜索策略，用于平衡算法的全局和局部搜索能力；并通過仿真實驗比較和對某建筑工地實例求解驗證了模型的合理性與算法的有效性。

關(guān)鍵詞：定位布置問題；分布估計算法；罰函數(shù)；仿真實驗

設(shè)施布置問題（Facility Layout Problem，F(xiàn)LP）是對生產(chǎn)系統(tǒng)內(nèi)部各設(shè)施進(jìn)行優(yōu)化布局，以提高企業(yè)的長期經(jīng)濟效益。作為一類典型的組合優(yōu)化問題，設(shè)施布置問題需要考慮決策目標(biāo)、設(shè)施特征、物料搬運過程及場地物理空間等諸多因素，其決策過程十分復(fù)雜［1］。依據(jù)生產(chǎn)系統(tǒng)內(nèi)部的作業(yè)流程特征，基本設(shè)施布置形式可以分為按產(chǎn)品原則布置、按工藝過程原則布置、成組技術(shù)與定位布置等，選擇合理的設(shè)施布置形式已經(jīng)成為影響企業(yè)運營效率的關(guān)鍵因素。定位布置問題（Fixed-Positioning Layout Problem，F(xiàn)PLP）的研究對象為單個中心設(shè)施/位置（Hub Facility/Position，HF/P）和多個外圍設(shè)施/位置（Peripheral Facility/Position，PF/P）所構(gòu)成的系統(tǒng)。通常，中心設(shè)施體積較大或質(zhì)量較重且不易挪動，外圍設(shè)施需要按照一定的規(guī)則圍繞中心設(shè)施進(jìn)行布置，決策目標(biāo)為最小化總物流費用。定位布置問題廣泛存在于建筑施工、筑路、造船和飛機制造等實際生產(chǎn)制造系統(tǒng)中，已經(jīng)成為企業(yè)運營管理領(lǐng)域的技術(shù)熱點之一［2，3］。

理論上，如果將外圍設(shè)施圍繞中心設(shè)施作同心圓布置，則各外圍設(shè)施與中心設(shè)施之間的物流費用總和為固定值，此時定位布置問題可抽象為一類特殊（即目標(biāo)函數(shù)包含常數(shù)項，且?guī)Ц郊蛹s束條件）的二次分配問題（Quadratic Assignment Problem，QAP）［4］。實際上，由于受到作業(yè)場地面積和形狀的限制，使得可利用的位置到中心設(shè)施的距離不盡相同，無法保證外圍設(shè)施與中心設(shè)施間的同心圓布置。因此，定位布置問題不僅需要考率多個外圍設(shè)施間的物流費用總和，而且要考慮各個外圍設(shè)施與中心設(shè)施之間的物流費用總和，同時還需考慮位置容量約束的硬約束條件（即不允許松弛到目標(biāo)函數(shù)中）?？芍?，定位布置問題屬于典型的約束組合優(yōu)化問題，且二次分配問題可以歸約為定位布置問題，其求解難度比二次分配問題復(fù)雜得多，屬于組合優(yōu)化問題中的NP-難范疇，無法在多項式時間內(nèi)獲得大規(guī)模問題的最優(yōu)解［5］。目前，使用基于智能優(yōu)化的方法，求解特定指標(biāo)下的生產(chǎn)系統(tǒng)內(nèi)部設(shè)施布置問題已經(jīng)成為學(xué)術(shù)界的研究熱點。如Pourvaziri等［6］提出了一種混合多種群遺傳算法用于求解動態(tài)設(shè)施布置問題，并把解空間劃分成多個獨立的部分用于保持算法多樣性，融入了一種基于模擬退火的局部搜索以提高算法搜索能力。García-Hernández等［7］在處理不等面積設(shè)施布置問題時，把決策者的干預(yù)加入到了遺傳算法中，以此來調(diào)整算法的參數(shù)設(shè)置，進(jìn)而實現(xiàn)算法與專家決策的交互作用。Guan等［8］把一種基于變鄰域搜索的蟻群算法用于單列設(shè)施布置問題的優(yōu)化中，使用 60組標(biāo)準(zhǔn)測試算例對算法的性能進(jìn)行了驗證。根據(jù)文獻(xiàn)調(diào)研，使用智能優(yōu)化算法求解設(shè)施定位布置問題尚無文獻(xiàn)報道，因此設(shè)計和開發(fā)有效的智能優(yōu)化算法求解設(shè)施定位布置問題具有一定的意義。

1　定位布置問題的數(shù)學(xué)模型

1.1問題描述

定位布置問題即在中心設(shè)施位置固定的情況下，外圍設(shè)施圍繞中心設(shè)施進(jìn)行布置，通過對外圍設(shè)施布置方案進(jìn)行優(yōu)化調(diào)整實現(xiàn)目標(biāo)函數(shù)（總物流費用）的最小化。由于外圍與外圍設(shè)施、外圍與中心設(shè)施之間均存在著復(fù)雜的物料搬運關(guān)系，因此不僅需要考慮外圍設(shè)施間的物流費用和對總物流費用的影響，同時還需考慮各外圍設(shè)施與中心設(shè)施間的物流費用和對總物流費用的影響。此外，實際作業(yè)場地的可利用空間往往是有限的，必須考慮位置容量這一硬約束條件?？梢?，定位布置問題屬于典型的約束優(yōu)化問題，其求解難度受到問題規(guī)模與約束松緊的雙重影響，因此需要在基本數(shù)學(xué)模型的基礎(chǔ)上建立基于約束處理技術(shù)的改進(jìn)數(shù)學(xué)模型。

1.2基本數(shù)學(xué)模型

參數(shù)：cij為設(shè)施i與j之間的物流量；dkl為位置k與l之間的距離；hi為設(shè)施i到中心設(shè)施的物流量；gk為位置k到中心位置的距離；qi為設(shè)施i的空間占用量；Qk為位置k的容量；

基于上述參數(shù)和決策變量，定位布置問題的目標(biāo)函數(shù)和約束條件如下：

其中，式（1）為目標(biāo)函數(shù)（即總物流費用），前項表示外圍設(shè)施之間的物流費用和，后項表示各個外圍設(shè)施到中心設(shè)施的物流費用和；式（2）和（3）為指派類約束，其中式（2）表示每個設(shè)施只能放置在一個位置上，式（3）表示每個位置上只能放置一個設(shè)施；式（4）為容量約束，表示所放置設(shè)施的空間占用量總和不能超過相應(yīng)位置的容量。

1.3基于罰函數(shù)的改進(jìn)數(shù)學(xué)模型

由于上述基本數(shù)學(xué)模型中容量約束的存在，要求智能優(yōu)化算法在搜索過程中必須兼顧解的可行性和質(zhì)量，因此需要引入恰當(dāng)?shù)募s束處理技術(shù)。目前，主流的智能約束處理技術(shù)主要包括罰函數(shù)［9］，基于排序的方法［10］、基于多目標(biāo)的方法［11］等。其中，罰函數(shù)法是最簡單有效的約束處理技術(shù)，對問題結(jié)構(gòu)沒有硬性要求且簡單易于實現(xiàn)［12］，本文采用基于罰函數(shù)的方法把容量約束（式（4））附加懲罰權(quán)重后追加到原目標(biāo)函數(shù)中，定位布置問題的改進(jìn)數(shù)學(xué)模型如下：

其中，式（5）為引入懲罰項后的新目標(biāo)函數(shù)，最后一項為懲罰項，P表示罰因子。

2　改進(jìn)分布估計算法設(shè)計

分布估計算法（Estimation o f D istribution A lgorithm，EDA）是一種基于概率模型的隨機優(yōu)化方法，在求解規(guī)模較大和復(fù)雜度較高的組合優(yōu)化問題中效果顯著［13］。EDA通過對概率模型進(jìn)行更新和采樣形成新的個體，與遺傳算法相比，能較好地把握宏觀搜索方向，具有較強的全局搜索能力，但局部搜索能力較差［14］。針對這一特點，所提出的改進(jìn)分部估計算法（Improved Estimation of Distribution A lgorithm，IEDA）加入了一種基于鄰域互換型的局部搜索機制，用于提高算法的搜索深度，同時采用了一種概率矩陣擾動機制來拓展算法的搜索寬度。

2.1編碼策略

根據(jù)定位布置問題的特征，采用基于設(shè)施編號的方法進(jìn)行編碼，由于中心設(shè)施位置已知，故只需使用外圍設(shè)施字符排列來表示可行的布置方案。如，π=［4，3，2，5，1］表示設(shè)施4放在位置1，設(shè)施3放在位置2，設(shè)施2放在位置3，設(shè)施5放在位置4，設(shè)施1放在位置5。

2.2隨機種群初始化

為了防止算法在迭代尋優(yōu)過程中陷入局部最優(yōu)，需要保持初始解在解空間中的均勻分布。因此，IEDA采用隨機初始化種群的方法，即隨機生成的popsize個體組成初始種群，作為算法搜索的起點。

2.3概率矩陣初始化

EDA使用概率矩陣來記錄進(jìn)化過程中優(yōu)質(zhì)解的歷史信息，從而有效指導(dǎo)算法的搜索方向。概率模型的選擇需要結(jié)合問題的結(jié)構(gòu)特征。由于定位布置屬于離散型組合優(yōu)化問題，故IEDA使用概率矩陣作為概率模型。則算法在第gen代的概率矩陣定義為：

其中，該概率矩陣滿足列歸一性，即：

2.4概率矩陣更新機制

為了使算法獲得較快的收斂速度并提高搜索效率，IEDA采用歷史最優(yōu)個體對概率矩陣進(jìn)行更新。設(shè)表示第gen代的歷史最優(yōu)個體（best so far），LR表示學(xué)習(xí)速率，則概率矩陣的更新步驟如下：

步驟1：令j=1；

步驟4：令j=j+1，如果j≤n，轉(zhuǎn)向步驟2；

步驟5：輸出PM（gen+1）。

2.5概率矩陣采樣機制

IEDA通過概率矩陣采樣生成新一代種群。本文采用基于輪盤賭的采樣操作既利用了概率矩陣的信息，有利于保證較好的位置以較大的概率被選中。在采樣的過程中，按照從左到右的順序進(jìn)行采樣，當(dāng)位置j選中設(shè)施F后，設(shè)置n）以保證解的可行性。

設(shè) πi,gen+1表示種群 πg(shù)en+1中的第 i個個體，SelectFaclity（πi,gen+1（j））=F表示個體 πi,gen+1中的第 j個位置選中設(shè)施F的函數(shù)，則SelectFaclity（πi,gen+1（j））的步驟如下：

步驟1：構(gòu)造輪盤賭；

步驟2：選擇設(shè)施F；

產(chǎn)生隨機小數(shù)R∈［0，1）；

步驟3：輸出F。

根據(jù)上述步驟，IEDA的采樣操作步驟如下：

步驟1：令i=1；

步驟2：令j=1；

步驟4：j=j+1，若j≤n，轉(zhuǎn)向步驟3；

步驟5：令i=i+1，若i≤popsize，轉(zhuǎn)向步驟2；

步驟6：輸出πg(shù)en+1。

2.6概率矩陣變異機制

為了保持種群的多樣性，提高算法的搜索寬度，IEDA引入了概率矩陣變異機制。設(shè) Pmu為變異概率，MR為變異速率。變異步驟如下：

步驟1：令j=1；

步驟3：如果R＞Pmu，則并轉(zhuǎn)向步驟6；

步驟6：令j=j+1，如果j≤n，轉(zhuǎn)向步驟2；

步驟7：輸出PM（gen）。

2.7基于互換型鄰域結(jié)構(gòu)的局部搜索

組合優(yōu)化問題的近鄰假設(shè)理論認(rèn)為，在較好解的附近一般也存在較好的解，為了利于算法在相對狹窄的局部解空間周圍發(fā)現(xiàn)更優(yōu)良的解，引入了基于互換型（Interchange）鄰域結(jié)構(gòu)的局部搜索策略。同時，為了防止算法因過度的局部搜索而陷入局部最優(yōu)，EDA采用了首次改進(jìn)跳出原則。

2.8IEDA的算法流程

設(shè)genMax為 IEDA的最大迭代次數(shù)，結(jié)合上述相關(guān)操作，IEDA的算法流程如圖1所示。

圖1　　IEDA的算法流程圖　

3　仿真實驗比較和實例求解

3.1實驗設(shè)置

由于目前尚不存在針對定位布置問題的benchmark算例，隨機生成了20組不同規(guī)模的算例為測試對象，算例規(guī)模（即外圍設(shè)施/位置數(shù)目）分別為：5，8，9，10，13，15，18，20，23，25，28，30，33，35，38，40，43，45，48，50。模型中參數(shù)的生成規(guī)則如下：cij∈U［1，100］，dkl∈U［1，100］，h1∈U［1，100］，gk∈U［50，100］，qi∈U［1，50］，其中，

所有算法使用 M icrosoft Visual Studio2008 （C++語言）編程實現(xiàn)，實驗硬件環(huán)境為Core i53.3GHz，RAM3.46GB；軟件環(huán)境為，Windows7。所有的算法都獨立重復(fù)運行 21次，采用目標(biāo)函數(shù)平均值（AOV），約束違反量平均值（ACV）及可行率（FR）［15］作為評價指標(biāo)來衡量算法的性能。顯然，AOV可以作為算法尋優(yōu)能力的衡量尺度，ACV和FR可以用于衡量算法的約束處理能力。IEDA的參數(shù)配置為：popsize=50，LR=0.02，Pmu=0.05，MR=0.005，P=1000000。

3.2算法性能比較分析

為了所提出的IEDA的有效性，考慮將IEDA與下列算法進(jìn)行比較：①PEDA：標(biāo)準(zhǔn)分布估計算法（Pure Estimation of Distribution A lgorithm，PEDA），即其操作中不包含概率矩陣變異操作和局部搜索操作，其余操作及參數(shù)配置與IEDA相同；②PEDA_LS：在PEDA中加入局部搜索操作，其余操作及參數(shù)配置與PEDA相同；③GA：標(biāo)準(zhǔn)遺傳算法（Genetic A lgorithm，GA），采用基于輪盤賭的選擇方法，變異概率和交叉概率分別取0.3和0.7，種群規(guī)模為50；④GA_LS：在GA中融入局部搜索操作，其余操作及參數(shù)配置與GA相同。

為了保證算法性能比較實驗的公平性，設(shè)置所有EDA類算法均運行1000代，而GA和GA_LS均運行15000代，按照實驗設(shè)置規(guī)則運行所有算法所得到的實驗結(jié)果如表1所示。同時，對IEDA，GA和GA_LS3種算法的平均運行時間進(jìn)行了統(tǒng)計，其結(jié)果如圖2所示。

由表1可知，IEDA和PEDA_LS明顯占優(yōu)于其他3種對比算法，表明EDA類算法在求解定位布置問題時具有明顯優(yōu)勢，同時也驗證了所設(shè)計的基于互換型鄰域的局部搜索策略是有效的。雖然IEDA與PEDA_LS在AOV指標(biāo)上沒有顯著差異，但I(xiàn)EDA解的FR高于PEDA_LS，這表明所設(shè)計的概率矩陣變異策略有利于提高IEDA的約束處理能力。值得注意的是，IEDA的FR平均水平幾乎達(dá)到了100%，表明IEDA在求解帶容量約束的定位布置問題時具有較高的可靠性。

表1　　算法性能比較結(jié)果　

圖2　　算法運行時間趨勢圖　

由圖2可知，雖然IEDA的運行代數(shù)要遠(yuǎn)小于GA和GA_LS，但對所有的算例，IEDA都能在較短的時間內(nèi)獲得優(yōu)質(zhì)的解，說明IEDA具有較高的搜索效率。

3.3實例求解

以沈陽市某建筑物施工現(xiàn)場為例，驗證模型的合理性與算法的有效性。該建筑工地內(nèi)的主要外圍功能設(shè)施有：螺紋鋼庫、線材庫、鋼管庫、石子庫、木枋庫、沙場、砌磚塊庫、水泥庫、鋼筋加工區(qū)、鋼筋成品庫（I）、鋼筋成品庫（II）、石粉碎區(qū)、混凝土加工區(qū)、砌磚加工區(qū)和模板加工區(qū)等 15個可利用位置。

根據(jù)實際施工過程中的工藝需求，測算出各個外圍設(shè)施之間的距離及物流量矩陣、中心物流量、中心距離、設(shè)施的空間占有量和位置容量，統(tǒng)計結(jié)果如表2和表3所示。

表2　　物流量矩陣、中心物流量及空間占用量　

根據(jù)以上數(shù)據(jù)信息，使用IEDA算法獨立重復(fù)運行21次，所得結(jié)果如表4所示。

由上述求解結(jié)果可知，IEDA能夠在0.1s的時間內(nèi)獲得最優(yōu)解，而且在算法獨立重復(fù)運行 21次時，可行率為100%，再次驗證了IEDA的有效性以及在實際工程中的可用性。

表3　　物流量矩陣、中心距離及位置容量　

表4　　IEDA優(yōu)化性能分析　

4　結(jié)語

本文針對最小化總物流費用指標(biāo)下的定位布置問題，提出了一種改進(jìn)分布估計算法（IEDA）進(jìn)行求解。根據(jù)定位布置問題的特征，構(gòu)建了該問題的基本非線性整數(shù)規(guī)劃模型；使用基于罰函數(shù)的方法對容量約束進(jìn)行處理，并提出了該問題的改進(jìn)數(shù)學(xué)模型；在IEDA中融入了一種概率矩陣變異機制和基于互換型鄰域結(jié)構(gòu)的局部搜索策略，用于平衡算法的全局和局部搜索能力；并通過仿真實驗比較和基于建筑工地的實例求解對IEDA的性能及工程價值進(jìn)行了驗證。進(jìn)一步將針對多目標(biāo)的設(shè)施布置問題進(jìn)行研究，使用基于 EDA的混合算法求解更復(fù)雜情況下的設(shè)施布置問題。

參考文獻(xiàn)：

［1］周志文.生產(chǎn)與運作管理［M］（第1版）［M］.北京：石油工業(yè)出版社，2001.

［2］戢守峰.現(xiàn)代設(shè)施規(guī)劃與物流分析（第一版）［M］.北京：機械工業(yè)出版社，2013.

［3］王晶.生產(chǎn)與運作管理（第一版）［M］.北京：清華大學(xué)出版社，2011.

［4］Lee H Y，Kang S，Chae J.Mutation effects in a genetic algorithm for a facility layout problem in QAP form［J］.International Journal of Advanced Logistics，2015，4 （3）：170-179.

［5］張鴻賓.組合優(yōu)化問題的啟發(fā)式搜索［J］.計算機科學(xué)，1998，25（2）：13-16.

［6］Pourvaziri H，Naderi B，Pourvaziri H，et al.A hybrid multi-population genetic algorithm for the dynamic facility layout problem［J］.Applied Soft Computing，2014，24 （24）：457-469.

［7］García-Hernández L，Palomo-Romero J M，Salas-M orera L，et al.A novel hybrid evolutionary approach for capturing decision maker know ledge into the unequal area facility layout problem［J］.Expert Systems with Applications，2015，42（10）：4697-4708.

［8］Guan J，Lin G.Hybridizing variable neighborhood search w ith ant colony optim ization for solving the single row facility layout problem［J］.European Journal of Operational Research，2016，248（3）：899-909.

［9］Liu J，Teo K L，Wang X，et al.An exact penalty function-based differential search algorithm for constrained global optim ization［J］.Soft Computing，2015：1-9.

［10］Ho P Y，Shimizu K.Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme［J］.Information Sciences（S0020-0255），2007，177（14）：2985-3004.

［11］Wang Y，Caiz X，Guo G Q.Multi objective optimization and hybrid evolutionary algorithm to solve constrained optim ization problem s［J］.IEEE Trans on Systems，Man and Cybernetics-Part B：Cybernetics（S1083-4419），2007，37（3）：560-575.

［12］王凌，何鍥，金以慧.智能約束處理技術(shù)綜述［J］.化工自動化及儀表，2008，35（1）：1-7.

［13］Hauschild M，Pelikan M.An introduction and survey of estimation of distribution algorithms［J］.Sw arm&Evolutionary Computation，2011，1（3）：111-128.

［14］王圣堯，王凌，方晨，等.分布估計算法研究進(jìn)展［J］.控制與決策，2012，27（7）：961-966.

［15］Mallipeddi R，Suganthan P N.Problem definitions and evaluation criteria for the CEC2010Competition on Constrained Real-Parameter Optimization［R］.Singapore：Nanyang Technological University，2010.

遼寧省教育廳人文社科基地項目（ZJ2013014）.

中圖分類號：TU731

文獻(xiàn)標(biāo)識碼：A

文章編號：1674-8859（2016）03-116-06

DOI：10.13991/j.cnki.jem.2016.03.020

作者簡介：

羅蓉娟（1992-），女，碩士研究生，研究方向：設(shè)施布置理論與智能優(yōu)化；

戢守峰（1958-），男，教授，博士生導(dǎo)師，研究方向：物流系統(tǒng)建模與優(yōu)化，物流與供應(yīng)鏈管理。

收稿日期：2016-04-02.

基金項目：國家自然科學(xué)基金項目（71572031）；

M odel and A lgorithm for Fixed-positioning Layout Based on Penalty Function

LUO Rong-juan，JI Shou-feng
（School of Business Administration，Northeastern University，Shenyang110167，China，E-mail：sfji@mail.neu.edu.cn）

Abstract：Considering the decision of interior facility layout in the production systems and aiming at facility layout problem，an improved estimation of distribution algorithm（IEDA）is given to solve this problem.Firstly，based on its essential characteristics，a nonlinear integer programm ing model w ith capacity constraints is established to formulate associated basic properties.Secondly，a modified mathematical model combining w ith the penalty function based constraint handling method is constructed，w hich indicates that if the capacity constraint of any position is not satisfied，the related penalty term w ill be set to a high punishment，otherw ise set to zero.And thereafter，the objective function with penalty terms is used to guide the search direction of our proposed IEDA.Thirdly，a mutation mechanism for probability matrix and an interchange-based local search w ith first move strategy are embedded into IEDA to balance the global and local search ability.Finally，the results of simulation experiments and case study from a construction site demonstrate the rationality of the model and the effectiveness of the presented IEDA.

Keywords：fixed-positioning layout problem；estimation of distribution algorithm；penalty function；simulation experiments