基于SEGA算法的区段式车间系统协同布局优化

张艳伟，程沙沙，张新艳

(1.武汉理工大学 物流工程学院，湖北 武汉 430063；2.同济大学 机械与能源工程学院，上海 201804)

车间设备布局和物料搬运路径规划不合理是导致制造系统物流成本居高不下的重要原因。牛占文等[1]针对现有布局下车间生产效率低等问题，提出了多目标车间布局改善方法。KUMAR等[2]采用仿真技术对单回路、区域式及区域式环形3种AGV系统进行分析，发现不同的AGV路径布置方式各有所长。近几年，设备布局与AGV路径集成优化方法逐步引起人们的关注。葛华辉等[3]针对SFT系统建立了设备布局与AGV路径规划集成优化模型，但未考虑需求不确定性和空载成本。REZAPOUR等[4]针对区域式AGV系统，提出一种将设备分配、区域内设备布局、车间区域布局和转运中心设计进行串联求解的方法。SEDEHI等[5]综合考虑分块布局、AGV单回路物流路径和装卸点位置，对设备布局和物料搬运系统进行并行设计。王闯等[6]综合考虑车间实际搬运路径和物流效率，研究智能车间布局规划的建模与求解方法。李爱平等[7]建立了鲁棒性布局与物料搬运系统协同优化模型。刘庄成[8]将区域式AGV系统的设备布局与路径规划进行集成设计，提出一种协同求解框架。

空载运行成本是车间完成物料搬运任务过程中产生的额外成本，在计算物流成本时，鲜少有研究将其考虑在内。李玉兰等[9]以重载和空载搬运成本之和最小为目标，采用曼哈顿距离计算公式建立数学模型，但忽略了车辆行驶过程中需绕过障碍物和设备等情况。董舒豪等[10]建立了以物料搬运成本、车辆空载运行成本及作业单元相互关系为优化目标的多行设备布局模型，但未考虑设备布局对搬运车辆路径规划的影响。针对空载成本的研究，目前均以多行线性布局车间系统为对象，未考虑区段划分和中转缓存区布置等问题，模型中的决策变量较少。车间布局规划是企业的一个战略性决策过程，在布局时考虑需求不确定性有助于实现可持续发展[11]。为了解决不确定性需求下的设备布局难题，部分研究假设加工产品种类固定，引入随机变量[11-13]或采用模糊理论[14-16]等方式描述产品需求水平的不确定性，但均存在相关参数难以确定等问题。

综上所述，目前已有学者将车间设备布局与AGV路径规划进行综合考虑，大部分研究将二者进行串联处理，忽略了设备布局与搬运路径规划的耦合性。为了避免曼哈顿距离和欧氏距离公式导致的计算误差，分析区段式AGV系统特征、物料搬运工艺和车间物流动线，研究车辆重载和空载搬运距离的实际计算方法。在考虑需求不确定性和车间设备布局与AGV路径规划耦合性的基础上，以AGV重载和空载搬运成本最小为优化目标，建立SFT系统设备布局与AGV路径协同优化模型，提出一种双链染色体编码的增强精英保留遗传算法，通过实例分析与求解，验证模型和算法的有效性。

1 问题描述与假设

区段式AGV系统通过“分区控制”避免了复杂的AGV调度和路径冲突问题，以简单、易控、柔性好的特点逐渐引起学者关注。其设计难点在于如何合理地进行区段划分和设备布局，即在满足AGV最大负载能力和各区段负载均衡的前提下，将车间设备分配至车间内不同区段，同时基于设备之间的物流量对区段内设备进行布局规划。

1.1 问题描述

车间采用SFT系统布局形式，AGV轨道被划分成几个互不交叉的区段，将一定数量的设备组和中转缓存区分区段布置在固定尺寸的车间，每个区段由一台AGV负责物料搬运，AGV可在本区段内双向行驶，缓存区为区段间的物料中转设施，优化目标为所有AGV重载和空载总搬运成本最小。已知产品种类、每种产品被加工概率及加工顺序。r∈{1,2,…,R}近似表示产品低、中、高的需求水平，其中R为产品最高需求水平。同一类别的设备成组放置形成设备组，2个及多个设备组划分为一个区段，如图1所示。每个设备组在区段内主通道一侧中间设置1个装卸点，中转缓存区根据需求在上、下边界中点设置装卸点。在任意时刻，AGV执行完某个任务后，从当前任务的终点行驶至新任务的起点，期间产生空载行驶距离。

图1 区段式AGV系统示意图

平面直角坐标系原点位于矩形车间的左上角，L和W分别为车间总长度和总宽度；Mi表示第i个设备组，i∈{1,2,…,n}；Sz表示第z个中转缓存区，z∈{1,2,…,v-1}；qz表示第z个区段，z∈{1,2,…,v}。当有一批物料需要跨区段搬运时，每个区段的 AGV只负责本区段的搬运任务。如接到M2→M6的搬运任务后，区段q1中的AGV将物料从设备组M2搬运到中转缓存区S1，再通过区段q2中的AGV将物料从中转缓存区S1搬运到设备组M6。在执行当前任务的过程中，若AGV接到新的搬运任务M5→M8，则区段q2中的AGV先将物料从中转缓存区S1搬运到设备组M6处，再从设备组M6行驶至设备组M5，即可执行M5→M8的搬运任务。其中，从设备组M6至设备组M5的距离称为空载搬运距离。

1.2 相关假设

实际生产中，功能不同的设备组所占区域可能存在边缘不规则的情况，在建立数学模型时，需对一些车间布局参数进行标准化处理，作出如下假设：

(1)车间产品、工艺过程已知，设备配备满足生产工艺要求。

(2)设备组所占区域为形状规则、尺寸已知的矩形；中转缓存区所占区域为形状规则、尺寸已知、容量不限的正方形。其中，所有设备组和中转缓存区的装卸点同时具有上料和下料功能。

(3)AGV为单一负载，沿水平和垂直方向移动，空载与重载单位距离运行成本均为1。

2 数学模型

区段式车间系统作为一种柔性较好的布局形式，其规划过程需综合考虑AGV搬运路径规划、中转缓存区布置、设备布局等问题。现有研究中，大多采用设备组几何中心之间的欧氏距离或曼哈顿距离作为距离的计算方法，忽略了AGV在物料搬运途中需避开设备组或中转缓存区等障碍物，且车辆进行物料装卸的位置往往不在设备组几何中心处，造成距离成本的计算会有较大误差。将设备组之间的距离定义为对应装卸点之间的实际距离，使距离成本更接近实际车间情况；考虑到车间物流量随需求而变化，采用离散概率分布近似表示产品需求的不确定性；在综合考虑车间尺寸、设备组尺寸、中转缓存区尺寸、最小安全距离等几何约束的条件下，建立车间设备布局和AGV物料搬运路径规划协同优化模型。

2.1 优化目标

目标为计划期内总物料搬运成本最小，包含AGV重载和空载搬运成本。

(1)

(2)

2.2 距离计算公式

2.2.1 基本距离计算公式

设备组之间的距离定义为对应装卸点之间的实际距离。假设设备组Mi属于区段qz，则设备组Mi与Mj之间距离为：

(3)

式中：(xi,yi)和(xj,yj)分别表示设备组Mi和Mj的坐标；DiSz为设备组Mi与中转缓存区Sz之间的距离；DSz+m-1j为设备组Mj与中转缓存区Sz+m-1之间的距离；DSlSl+1为中转缓存区Sl与Sl+1之间的距离;跨m个区段，即设备组Mi与Mj之间有m个中转缓存区。

2.2.2 空载距离计算公式

当AGV即将执行下一项搬运任务时，其所处位置具有不确定性，即AGV可能处于该区段任一设备组或邻近中转缓存区的装卸点处。AGV处于区段qz中任一设备组Mo处的概率为：

(4)

由式(4)可知，PMo越大，表示其他设备组到Mo的物流量越大，则AGV在接到新任务时处于设备组Mo处的概率越大。由此可得，任意时刻为完成下一搬运任务(Mi→Mj)，AGV所需空载搬运距离的计算公式如式(5)和式(6)所示。

(1)若设备组Mi与Mj之间不跨区段，则：

(5)

(2)若设备组Mi与Mj之间跨m个区段，则：

(6)

2.3 约束条件

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

3 增强精英保留的遗传算法

车间设备布局与AGV路径协同优化是一个复杂的离散优化问题，同时受设备组之间相对位置、AGV数量、中转缓存区位置、车间几何约束等影响，算法求解关键在于设备组之间的距离。为求解该问题，提出一种增强精英保留的遗传算法(strengthen elitist genetic algorithm，SEGA)。采用双链染色体编码表示车间综合布局方案，设备组布局的染色体采用排列编码方式，0-1整数编码表示中转缓存区的染色体，有效提高了进化过程解的质量；对适应度函数进行线性尺度变换，增加了种群的多样性，提高了算法的全局搜索能力；结合精英锦标赛选择算子和父子合并竞争选择等进化策略，提高了算法的进化效率和全局收敛性。

3.1 适应度函数

为了保证最终解的质量和进化过程的搜索效率，对目标函数进行线性尺度变换, 得到适应度函数，如式(18)所示。变换后，少数适应度高的个体，其适应度等比例缩小；适应度较差的个体，其适应度等比例扩大。在种群进化过程中，一部分超常个体的竞争力可能远远超过其他个体，而部分适应度较差的个体可能携带一些优良基因。因此，适当保留一些适应度较差的个体，同时降低适应度较高个体被选择的概率，有利于种群跳出局部最优解，增加种群的多样性，提高算法的全局搜索能力。

f=αC+Cmax+ξ

(18)

式中：Cmax为目标函数最大值；α=-1，保证适应度增大方向与总物料搬运成本减小方向一致；ξ是一个较小的正数，保证种群中最差的个体也可获得繁衍机会。

3.2 染色体编码与解码

3.2.1 编码方式

设备布局与AGV路径协同优化模型相当于资源分配问题，即将有限的车间资源分配给数量有限的设备组，由于不同设备组具有不同尺寸和功能特性，采用排列编码方式可表示不同设备组位置；不同中转缓存区的尺寸和功能相同，排列编码方式无法有效表示不同中转缓存区在车间的空间位置。因此，单一的染色体编码方式难以同时表达设备组和中转缓存区位置。将表达不同元素的基因在同一条染色体上进行分段编码可以满足模型求解要求，但经过交叉、变异等进化操作后容易出现非可行解。

设备组和中转缓存区分别采用不同的编码方式，可大大降低编码和进化难度。表示设备组布局的染色体采用排列编码方式，序号0,1,2,…,n-1表示设备组的编号，染色体的长度为n；0-1整数编码表示中转缓存区的染色体，1表示该位置对应设备组后面有中转缓存区，0表示其对应设备组后面没有中转缓存区。由于每个区段设备组数量不少于2，因此排布在开头和末尾两个位置的设备组后不可能设置中转缓存区，对应数字必须为0。在算法进化过程中，染色体通过交叉、变异等操作后，种群个体的染色体在这几个位置容易出现非0元素，引起后代种群中非可行解占比增加。为了降低非可行解的出现频率，提高进化过程中解的质量并加快种群的进化效率，缩减中转缓存区的染色体长度至n-3。染色体编码示意图如图2所示。

图2 染色体编码示意图

3.2.2 解码方式

在求设备组和中转缓存区中心位置坐标前，首先对染色体进行初次解码，采用一个不同于所有设备组序号的整数表示中转缓存区，得到一条包含设备组和中转缓存区综合位置信息的序列表。将图2中的染色体进行初次解码得到：[0,5,7,10,9,4,10,1,8,2,10,3,6]，其中序号10表示中转缓存区。将初次解码得到的序列表按从左至右，从上往下依次排列，当车间宽度不足时采取自动换行策略，最终解码求得每个设备组和中转缓存区的中心坐标值。若已知设备组Mi的中心坐标为(xi,yi)，则与设备组Mi位于同一行的下一个设备组Mo的中心位置坐标为：

(19)

3.3 选择操作

算法进化过程包含2个阶段的选择。第1阶段是选择参与进化过程的种群个体，该阶段采用精英锦标赛选择算子，确保最优个体一定会被选中参加锦标赛，从而保留了精英个体所携带的优良基因。第2阶段为“环境选择”过程，经过交叉、变异等操作，从进化后的种群中选择一定数量的个体形成新一代种群。在这个阶段采用父子两代合并的竞争选择方式，即将进化后的个体与父代个体合并形成规模为2N的种群，再按照适应度值排序,从中选择前N个个体保留到下一代。

3.4 交叉操作

针对设备布局编码的染色体，采用部分匹配交叉算子。针对中转缓存区编码的染色体，采用两点交叉算子。对于两条设备布局编码的父代染色体，先随机产生两个随机数k1和k2作为截取染色体片段的起始和终止位置，0≤k1≤k2≤n；将截取到的两个片段进行位置互换；若交叉后出现重复编码，则根据映射关系进行染色体修复，得到最终的两条子代染色体。对于两条父代染色体，取k1=3，k2=6，其交叉操作如图3所示。

图3 染色体交叉操作示意图

3.5 变异操作

针对设备布局编码的染色体，采用染色体片段逆转变异算子，为了防止进化过程陷入局部最优解，往往选取较大的变异概率。针对中转缓存区编码的染色体，采用遗传算法育种变异算子。

4 实例对比分析

为了验证所提出的协同优化模型和算法的有效性，分别从算法和模型两个方面进行对比分析。首先，随机生成一组算例，采用SEGA算法和标准遗传算法(standard genetic algorithm，SGA)进行求解，通过对比分析验证SEGA算法的有效性；其次，采用SEGA算法对文献[3]中的算例进行求解，将求得的最小搬运成本与文献[3]中最优布局的物料搬运成本进行对比，进一步检验模型和算法的合理性。算法均采用Python语言编写，并在配置为 Intel Core i5 8th Gen，2.30 GHz CPU，8.0GB内存的电脑上运行。

4.1 算法对比

4.1.1 实例描述

车间长为80 m，宽为60 m，通道宽度为3 m，最小安全距离为2 m。车间需放置10组设备和3个中转缓存区，AGV处于中转缓存区的概率PS=0.5。产品需求水平r∈{1,2,3}，分别表示产品低、中、高的需求水平。设备组尺寸如表1所示，产品需求信息如表2所示。

表1 设备组尺寸

表2 产品需求信息

4.1.2 算法参数设计与问题求解

算法参数设置为：随机生成初始种群，种群规模为100，最大迭代次数为100；对于表示设备布局的染色体，交叉概率Pc=0.7，变异概率Pm=0.5；对于表示中转缓存区的染色体，交叉概率Pc=0.7，变异概率Pm=1/Dim，其中Dim为决策变量的维度，此时取值为17。针对上述算例，分别采用SGA和SEGA算法求解30次并取平均值，结果如表3所示。由表3可知，两种算法求解时间相近，SEGA算法求解得到的总物料搬运成本的最差解、最优解及平均解均优于SGA算法，表明SEGA算法在求解协同优化模型时具有更强的寻优能力。SEGA算法与SGA算法取最优解时的算法收敛图分别如图4和图5所示，可知SEGA算法的全局收敛性较好，SGA算法无法获得收敛。

表3 SEGA算法与SGA算法结果对比

图4 SEGA算法收敛图

图5 SGA算法收敛图

SEGA算法求得最优解时，设备组和中转缓存区位置坐标如表4所示，最优方案如图6所示。综合分析设备组之间的相对位置和物流量大小可知，该最优布局方案符合“物流量大的距离近、物流量小的距离远”布局原则。

表4 设备组和中转缓存区位置坐标

图6 最优方案示意图

4.2 模型对比

4.2.1 算例数据

文献[3]中的算例数据为：车间长100 m，宽90 m，通道宽度和最小安全距离均为5 m，车间需放置8组设备，设备组长和宽均为20 m，不考虑中转缓存区的尺寸。设备组之间的物料搬运量如表5所示，表中数据单位为批次。

表5 设备组之间的物料搬运量

4.2.2 模型结果对比

表6 物料搬运成本对比

笔者提出的协同优化模型考虑了AGV空载搬运成本，求解出的最优解使得车间总物料搬运成本降低了约2%。对比结果也表明，在AGV执行物料搬运任务的过程中，产生的空载运行成本不可轻易忽略，若搬运路线设置不合理，可能导致较高的车辆空载成本。

5 结论

(1)考虑到产品需求不确定性及车间设备布局与搬运路径规划之间的耦合性，研究不确定需求环境下区段式AGV系统路径规划与设备布局协同优化建模及求解方法，并通过算例对比分析验证模型和算法的有效性。

(2)考虑到欧氏距离和曼哈顿距离计算公式会造成距离误差偏大，提出考虑装卸点位置的车辆重载和空载搬运距离计算方法，使得模型与实际生产车间更相近。

(3)以AGV重载和空载运行成本总和最小为目标，建立不确定需求下车间设备布局与AGV路径规划协同优化模型，实例分析表明，所提出的优化模型能求解出合理的布局方案。

(4)设计一种双链染色体编码的增强精英保留遗传算法，与SGA算法对比发现，提出的 SEGA算法有效提升了遗传算法的全局寻优能力和稳定性，并克服了遗传算法无法收敛的问题。

(5)在后续研究中，可综合考虑AGV数量、物料搬运成本、车间面积利用率等优化目标，建立多目标协同优化模型；为实现不确定需求环境下的经济可持续发展，可进一步研究动态设备布局与搬运路径协同优化问题的建模与求解方法；设计算法时，可将多种智能算法进行融合，改善求解算法的稳定性和计算效率，并结合仿真技术验证方案的合理性。