徐泽宇 蒋南云

[摘要]针对凹多边形的食堂布局，采用基于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.