基于改進(jìn)粒子群算法的凹多邊形食堂布局優(yōu)化

徐澤宇 蔣南云

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

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

[中圖分類(lèi)號(hào)]F224.0;F273[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]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ù)全校師生，每天飯菜制作的種類(lèi)和數(shù)量眾多。目前許多高校食堂的布局存在一定問(wèn)題。例如，某高校食堂只是仿照其他小型食堂再結(jié)合設(shè)計(jì)者自身的經(jīng)驗(yàn)設(shè)計(jì)而成，而隨后學(xué)生數(shù)量逐漸增加，備餐量也隨之增加，由此產(chǎn)生了較大的食材和菜品搬運(yùn)量。食材入庫(kù)和菜品搬運(yùn)的過(guò)程消耗了較多時(shí)間，降低了食堂的運(yùn)營(yíng)效率。因此，對(duì)于部分高校食堂，有必要對(duì)其食堂后廚的布局進(jìn)行重新規(guī)劃設(shè)計(jì)，以減少后廚工人的搬運(yùn)量，降低搬運(yùn)強(qiáng)度，提高運(yùn)營(yíng)效率。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.2模型構(gòu)建

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

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

（2）約束條件

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

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

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

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

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

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

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

（1）差分算法求解過(guò)程

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

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

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

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

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

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

（2）粒子群算法求解過(guò)程

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

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

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

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

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

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

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

2具體算例驗(yàn)證

2.1參數(shù)確定

現(xiàn)對(duì)某高校食堂進(jìn)行實(shí)地考察測(cè)量，獲得各工作單位的長(zhǎng)度、寬度，中心坐標(biāo)。具體劃分見(jiàn)表2，食堂各頂點(diǎn)坐標(biāo)如圖4所示，通過(guò)詢(xún)問(wèn)食堂工作人員得知，該食堂各工作單位之間的物流量矩陣P和非物流量矩陣M如下：

由于在搬運(yùn)過(guò)程均為人力搬運(yùn)，所以令搬運(yùn)費(fèi)用e_ij簡(jiǎn)化為1。

2.2DE-PSO算法求解

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

2.2.2粒子群算法求最優(yōu)解。初始種群個(gè)數(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)過(guò)多次求解得最優(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）}。對(duì)應(yīng)的物流搬運(yùn)量為55 173kg·m。與改善前的物流搬運(yùn)量79 127kg·m相比減少了23 954kg·m的物料搬運(yùn)量，改善效果顯著，改善后的布局示意圖如圖5所示。

3結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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

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

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

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

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

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

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

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