徐澤宇 蔣南云

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

[關(guān)鍵詞]凹多邊形布局;高校食堂;布局優(yōu)化;物料搬運;改進粒子群算法

[中圖分類號]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引言

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

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

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

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

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

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

1.1食堂概況及現(xiàn)狀分析

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

1.2數(shù)學(xué)模型的建立

1.2.1模型假設(shè)。為了便于求解含固定工作單位的凹多邊形食堂規(guī)劃布局模型的最優(yōu)布局，現(xiàn)做出如下合理假設(shè)：

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

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

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

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

（5）忽略食材加工過程中產(chǎn)生的食材質(zhì)量損失。

1.2.2模型構(gòu)建

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

另外，由于兩子目標函數(shù)在量綱上不一致，故將其歸一化;且未必能同時取到最優(yōu)解，故用線性加權(quán)和法轉(zhuǎn)化為單目標函數(shù)。

（2）約束條件

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

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

②間距約束。在進行布局規(guī)劃時，還要保證各工作區(qū)之間不重疊并存在一定間隔。數(shù)學(xué)表達如下：

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

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

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

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

（1）差分算法求解過程

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

③變異。變異是在群體的差異向量基礎(chǔ)上調(diào)整每個個體向量[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]的三個隨機數(shù)且r₁≠r₂≠r₃≠i，F(xiàn)為縮放因子，控制偏差向量的放大作用[14]。

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

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

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

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

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

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

②適應(yīng)度計算。根據(jù)適應(yīng)度公式，計算每個粒子的適應(yīng)度。具體計算公式如下：

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

其中，F(xiàn)_i（G）為第G代中第i個粒子的適應(yīng)度值，f表示適應(yīng)度函數(shù)，x_i，d（G）為第G代的第i個粒子的第d維分量。

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

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

⑥結(jié)束運算。當粒子最優(yōu)適應(yīng)度值收斂或達到最大迭代次數(shù)時，則停止運算，輸出最優(yōu)解。

2具體算例驗證

2.1參數(shù)確定

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

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

2.2DE-PSO算法求解

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

2.2.2粒子群算法求最優(yōu)解。初始種群個數(shù)N為500，維數(shù)d為13，最大迭代次數(shù)ger為500，慣性權(quán)重w設(shè)置為0.6，自我學(xué)習(xí)因子c₁設(shè)置為0.4，群體學(xué)習(xí)因子c₂設(shè)置為0.6。經(jīng)過多次求解得最優(yōu)解：{（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）}。對應(yīng)的物流搬運量為55 173kg·m。與改善前的物流搬運量79 127kg·m相比減少了23 954kg·m的物料搬運量，改善效果顯著，改善后的布局示意圖如圖5所示。

3結(jié)語

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

[參考文獻]

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

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

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

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

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

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

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

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

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

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

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

[11]閆群民，馬瑞卿，馬永翔，等.一種自適應(yīng)模擬退火粒子群優(yōu)化算法[J/OL].西安電子科技大學(xué)學(xué)報：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]張揚.改進群體智能優(yōu)化算法及其應(yīng)用[D].南京：南京郵電大學(xué)，2020.