基于改進粒子群算法的凹多邊形食堂布局優化

徐澤宇 蔣南云

[摘要]針對凹多邊形的食堂布局，采用基于DE-PSO算法的改進SLP法，對食堂內部的物流因素和非物流因素進行定量分析。確定食堂布局規劃的數學模型，設置間距約束、邊界約束和固定工作單位約束。運用DE算法，求解出滿足間距約束的粒子，然后傳遞給PSO進行進一步的尋優。最后用算例驗證該方法的可行性。

[關鍵詞]凹多邊形布局;高校食堂;布局優化;物料搬運;改進粒子群算法

[中圖分類號]F224.0;F273[文獻標識碼]A[文章編號]1005-152X（2021）12-0059-06

Layout Optimization of Concave Polygon Canteen Based on Improved Particle Swarm Optimization Algorithm

XUZeyu，JIANG Nanyun

（School of Economics & Management，Nanjing Technology University，Nanjing 211816，China）

Abstract：In view of the layout of a concave polygon shaped canteen，we adopt the improved SLP method based on DE-PSO algorithm to quantitatively analyze the logistics and non-logistics factors inside the canteen. Then，we determined the mathematical model of canteen layout planning，and set the spacing constraint，boundary constraint and fixed work unit constraint. Using the DE algorithm，we solved the particles meeting the spacing constraint，and then passed them to PSO for further optimization. Finally，an example was given to verify the feasibility of this method.

Keywords：concave polygon layout;college canteen;layout optimization;materials handling;improved particle swarm optimization

0引言

高校食堂需要服務全校師生，每天飯菜制作的種類和數量眾多。目前許多高校食堂的布局存在一定問題。例如，某高校食堂只是仿照其他小型食堂再結合設計者自身的經驗設計而成，而隨后學生數量逐漸增加，備餐量也隨之增加，由此產生了較大的食材和菜品搬運量。食材入庫和菜品搬運的過程消耗了較多時間，降低了食堂的運營效率。因此，對于部分高校食堂，有必要對其食堂后廚的布局進行重新規劃設計，以減少后廚工人的搬運量，降低搬運強度，提高運營效率。

首先，傳統的系統布置分析（Systemitic Layout Planning）由理查德·繆瑟于1961年提出。我國在1983年引入SLP法后，在較多的情景和領域的設施和布局規劃中都有應用。如潘麗穎[1]應用傳統SLP法對生產車間的布局進行分析，根據物料搬運量從至表等數據，設計改善方案。董舒豪，等[2]對車間布局應用SLP法進行分析，布局優化的依據也是工作單位之間的物流和非物流相關關系。根據工作單位之間的物流和非物流密切程度設計改善方案，可以看出傳統SLP法在優化布局時有兩大缺點：一是量化程度不夠，即在將物料搬運量劃分等級時，擴大或縮小了工作單位對之間的真實物料搬運量，由此設計的改善方案也就未必是最優解了。二是受限于精力和能力，學者只能制定出有限個改善方案，而且也無法證明是否存在比當前改善方案更優的改善方案。所以傳統SLP法在布局優化上的改善效果是有限的。而采用智能算法搜索改善方案，一是免去將物料搬運量劃分五個等級的步驟，從而以實際物料搬運量代入運算，量化程度更精確;二是可以找出更多的改善方案從而加以比較，使改善方案更接近最優解。

其次，已有不少學者考慮到將傳統的系統布置分析和智能算法相結合。郭源源，等[3]在優化車間布局時，將SLP法分別與慣性系數遞減的粒子群算法和遺傳算法相結合，都獲得了滿意解。王玖河，等[4]采用粒子群算法和模擬退火算法結合SLP法，求解出帶鐵路分割線的物流園區功能區的最優布局。徐曉鳴，等[5]運用粒子群算法，考慮物流因素和非物流因素，將多目標函數轉化為單目標函數，最后求解出優化布局方案。高嘉成[6]在優化車間布局時不僅用遺傳算法對其求解，還運用Flexsim軟件對求解結果進行模擬，以驗證結果的可行性和有效性。然而，在他們的研究中，其研究對象均為規則的矩形或正方形，而本文的研究對象是凹多邊形。這增加了工作單位排布的復雜度，需要對工作單位的中心坐標做出不同情況的討論。

再者，以往研究對于間隔約束的處理是引入懲罰函數，對不滿足間隔約束個體的適應度值進行懲罰。如蔡鑒明，等[7]對不滿足邊界約束的個體均添加固定的大數懲罰值。馮芬玲，等[8]在目標函數中添加指數型罰函數，對不滿足邊界約束的個體添加不同的懲罰值，根據超出邊界約束的程度進行不同大小的懲罰。但這一方法適用于原始布局中存在較多閑置區域的情況。而如果工作單位排布密集，那么隨機產生的初始個體往往難以滿足間距約束，即造成種群中極個別甚至沒有個體滿足約束條件，在此基礎上也就無法進行尋優。本文在解決這一問題時，先采用差分進化算法（Differential Evolution）搜索相當數量的滿足約束的可行解，然后再對可行解運用粒子群算法（Particle Swarm Optimization）進行尋優，最終找到最優解。

最后，以往的改進型SLP的應用對象多為物流園區或倉庫，其特點是由于園區或倉庫面積較大，工作單位排布相對稀疏，因此工作單位的長寬比有條件在滿足面積不變的情況下發生適當變化，或者有條件將工作單位按行或列整齊排布。如蔣璐[9]應用SLP 和遺傳算法對物流功能區的布局進行優化，允許工作單位的形狀在面積不變的條件下產生適當變化。候智，等[10]應用SLP和遺傳算法對倉庫布局進行優化，將工作單位按行規則排布。但食堂與上述對象在這一方面有所不同。食堂因處在建筑內部，所以工作單位排布密集，少有閑置區域供工作單位的面積或形狀發生變化。此外，食堂的工作單位中往往布置大量的烹飪設備，這對其工作單位的形狀和面積提出了更嚴格的約束。所以，在食堂中應用改進SLP法時，考慮到實際生產的要求，在優化過程中應嚴格保持各工作單位的形狀和面積固定，不得隨意更改變換。

1凹多邊形的食堂布局規劃模型建立

1.1食堂概況及現狀分析

通過對某高校食堂實地考察和測量得知其占地面積約1 506m²，食堂后廚可分為倉庫區、辦公區、米面粗加工間、面食精加工間、面食蒸煮間、米類精加工間、米類烹調間、肉菜粗加工間、肉菜精加工間、菜品烹調間、菜品蒸煮間、留樣處、備餐間共13個工作單位，對其用1-13數字來表示，當前的布局如圖1所示。由于食堂設計之初未考慮到物品的搬運，從而導致過道狹窄冗長，不利于菜品搬運;倉庫離米面粗加工間約31m，距離較遠。食材從倉庫取出經加工后送至備餐間的過程中，需要經過較多的迂回路徑。綜上所述，當前的食堂布局所產生的物流強度較大，造成了人力的浪費。后續將對食堂的物流因素進行分析，以確定最佳的布局方案。

1.2數學模型的建立

1.2.1模型假設。為了便于求解含固定工作單位的凹多邊形食堂規劃布局模型的最優布局，現做出如下合理假設：

（1）各工作單位形狀為矩形且長寬已知，工作單位的邊界與食堂邊界相互平行，工作單位的面積、數量已知且固定。

（2）各工作單位的幾何中心為物流量產生的起點或終點。

（3）各工作單位之間存在一定間隔，且間隔固定。

（4）受功能約束，備餐間必須靠近就餐區域。

（5）忽略食材加工過程中產生的食材質量損失。

1.2.2模型構建

（1）目標函數。目標函數由兩子函數組成，一是總物流量（G）最低，二是非物流相互關系（G2）最大。具體如下：

另外，由于兩子目標函數在量綱上不一致，故將其歸一化;且未必能同時取到最優解，故用線性加權和法轉化為單目標函數。

（2）約束條件

①中心坐標約束。所有作業單位均不能超出食堂邊界，由于食堂形狀為一種凹六邊形，所以對定義域分段定義如下：

其中，x_i，y_i為i工作區中心的橫、縱坐標。x_k，y_k分別為兩條內凹邊的橫坐標和縱坐標。

②間距約束。在進行布局規劃時，還要保證各工作區之間不重疊并存在一定間隔。數學表達如下：

其中，a_i，a_j為工作單位i、j的長（沿橫向坐標軸方向）;b_i，b_j為工作單位i、j的寬（縱向坐標軸方向）;Δs為工作單位i、j之間的最小間距。

③固定工作區約束。由于食堂的就餐區域固定，所以備餐間位置也需緊鄰就餐區域。故備餐間的橫縱坐標表達如下：

1.2.3模型求解。粒子群算法（Particle Swarm Optimization，PSO）是Russell.C Eberhart 教授和心理學家James Kennedy 博士通過對生物學家Frank Heppner 的鳥群覓食模型進行改進所提出的[11]。而差分進化算法（Differential Evolution，DE）是由Storn等人于1997年提出的，其主要包含變異、交叉、選擇三大部分[12]。

經典粒子群算法在生成初始種群時是隨機產生的。所以當間距約束較為嚴格時，其產生的大部分個體是不滿足間距約束的。也即隨機生成個體的方法產生可行個體的效率較低。所以需要先采用全局尋優能力較強的DE算法找出可行個體，然后再運用PSO算法對可行個體進一步計算尋優。本文算法求解流程如圖2所示。

（1）差分算法求解過程

①參數初始化。設置個體維數d，初始種群個數N，最大迭代次數ger，縮放因子F，交叉概率CR等。

③變異。變異是在群體的差異向量基礎上調整每個個體向量[13]。常用的變異策略為DE/rand/1，具體變異方法如下：

V_i，j（G）=x_r1，j（G）+F×（x_r2，j（G）-x_r3，j（G））（8）

其中，V_i，j（G）為變異種群中第G代的第i個個體的第j維向量，r₁、r₂、r₃為[1，N]的三個隨機數且r₁≠r₂≠r₃≠i，F為縮放因子，控制偏差向量的放大作用[14]。

④交叉。交叉是指按照某種規則從當前種群中每個個體的部分分量與對應變異個體的部分分量組合形成交叉種群。具體規則如下：

其中，U_i，j（G）表示交叉種群中第G代的第i個個體的第j維向量，r為隨機數，CR為交叉概率。j=randr表示變異種群中的每個個體存在一個隨機選中的第randr個分量必然產生交叉。具體示意圖如圖3所示。

⑤選擇。選擇是指從當前種群個體X_i（G）和交叉種群個體U_i（G）中，選擇適應度較優的個體作為下一代種群個體。具體操作如下：

⑥結束運算。當粒子最優適應度值收斂或達到最大迭代次數時，則停止運算，輸出最優解。在本文中，只要滿足間距約束，即視為達到最優解，結束運算并輸出結果X_i。

（2）粒子群算法求解過程

①參數初始化。設置種群規模N，最大迭代次數ger，空間維數d，慣性權重w，速度上界V_u，速度下界V_L，學習因子c₁，c₂等。生成隨機速度v_i（0）（i=1，2，…，N），在本文中，粒子的初始位置由DE算法計算產生。

②適應度計算。根據適應度公式，計算每個粒子的適應度。具體計算公式如下：

F_i（G）=f（x_i，l（G），…，x_i，d（G））（11）

其中，F_i（G）為第G代中第i個粒子的適應度值，f表示適應度函數，x_i，d（G）為第G代的第i個粒子的第d維分量。

④群體歷史最優更新。將每一代種群中的最優適應度值g^best（G+1）與前一代種群的最優適應度值g^best（G）作比較，如果優于前一代種群適應度值，則用當代最優適應度值將其代替，否則保留原值。具體數學表達如下：

其中max（p^best（G+1））為第G+1代中所有粒子歷史最優值中的最優值。

⑥結束運算。當粒子最優適應度值收斂或達到最大迭代次數時，則停止運算，輸出最優解。

2具體算例驗證

2.1參數確定

現對某高校食堂進行實地考察測量，獲得各工作單位的長度、寬度，中心坐標。具體劃分見表2，食堂各頂點坐標如圖4所示，通過詢問食堂工作人員得知，該食堂各工作單位之間的物流量矩陣P和非物流量矩陣M如下：

由于在搬運過程均為人力搬運，所以令搬運費用e_ij簡化為1。

2.2DE-PSO算法求解

2.2.1DE算法求初始可行解。由于有13個工作單位，所以維數d為13;設置初始種群N為250，縮放因子F為0.5，交叉概率CR為0.3。只要滿足式間距約束的個體就將其保存，否則對其進一步尋優。經過DE算法求解得到2 000個初始可行解。受限于篇幅，此處僅展示部分可行解，見表3。

2.2.2粒子群算法求最優解。初始種群個數N為500，維數d為13，最大迭代次數ger為500，慣性權重w設置為0.6，自我學習因子c₁設置為0.4，群體學習因子c₂設置為0.6。經過多次求解得最優解：{（19.649，33.875），（9.594，4.084），（20.273，24.408），（19.375，14.855），（5.210，12.619），（35.796，26.656），（13.739，14.580），（4.142，25.039），（6.799，33.130），（37.489，33.375），（52.625，31.509），（9.926，19.605），（42.033，21.625）}。對應的物流搬運量為55 173kg·m。與改善前的物流搬運量79 127kg·m相比減少了23 954kg·m的物料搬運量，改善效果顯著，改善后的布局示意圖如圖5所示。

3結語

本文研究了凹多邊形的最優布局設計，由于建筑內部工作單位排布密集，從而導致隨機生成的粒子難以滿足間距約束，大大降低了算法的尋優效率。于是引入DE算法先求出大量可行解，然后再用PSO算法迭代求解，最終求出可行解，并用具體示例驗證了該求解流程的可行性，為食堂布局優化提供了一些借鑒。改善后的布局與原布局相比減少了23 954kg·m的物料搬運量，改善效果顯著。

[參考文獻]

[1]潘麗穎.基于SLP方法的A公司生產車間布局設計[J].管理科學與工程，2019，8（1）：14-21.

[2]董舒豪，徐志剛，秦開仲.基于SLP與SHA的農機車間布置優化及仿真研究[J].現代制造工程，2020（1）：50-57.

[3]郭源源，王謙，梁峰.基于粒子群優化算法的車間布局設計[J].計算機集成制造系統，2012，18（11）：2 476-2 484.

[4]王玖河，韓希卓，時國強.考慮鐵路分割線的物流園區功能區布局規劃研究[J].工業工程，2019，22（5）：102-108.

[5]徐曉鳴，鄧裕琪，吳綺萍.基于SLP和粒子群算法的車間布局優化研究[J].機電工程技術，2020，49（2）：17-20，98.

[6]高嘉成.基于改進SLP的生產車間設施布局優化及仿真研究[J].內燃機與配件，2019（1）：189-191.

[7]蔡鑒明，肖世斌.生鮮冷鏈物流中心功能區布局研究[J].物

流科技，2019，42（1）：20-26.

[8]馮芬玲，景莉，楊柳文.基于改進SLP的鐵路物流中心功能區布局方法[J].中國鐵道科學，2012，33（2）：121-128.

[9]蔣璐.基于改進SLP和遺傳算法的配送中心功能區的布局設計[J].物流工程與管理，2021，43（1）：87-90.

[10]侯智，孟祥超.基于SLP與遺傳算法的倉儲布局優化[J].組合機床與自動化加工技術，2020（5）：159-163.

[11]閆群民，馬瑞卿，馬永翔，等.一種自適應模擬退火粒子群優化算法[J/OL].西安電子科技大學學報：1-9[2021-03- 12].doi：10.19665/j.issn 1001-2400.2021.04.016.

[12] DIXIT A，MANI A，BANSAL R.An adaptive mutation strategy for differential evolution algorithm based on particleswarm optimization[J].Evolutionary Intelligence，2021（Feb- ruary）：1-15.

[13] QIN A K，HUANG V L，SUGANTHAN P N .Differential evolution algorithm with strategy adaptation for global numerical optimization[C]//IEEE Transactions on Evolutionary Computation，2009.

[14]張揚.改進群體智能優化算法及其應用[D].南京：南京郵電大學，2020.