第15卷第5期 智能系统学报 Vol.15 No.5 2020年9月 CAAI Transactions on Intelligent Systems Sep.2020 D0:10.11992/tis.201906041 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20200323.1704.010.html 响应动态约束条件的多目标货位优化算法研究 项前，周亚云，陆枳屹，余玉风 （东华大学机械工程学院，上海201620) 摘要：针对自动化立库货位决策与优化问题，考虑到优化目标多样、托盘使用状态及可分配货位动态变化等 因素，提出了一种响应动态约束条件的多目标货位优化算法。以巷道作业均衡、货架重心稳定及作业路径最短 建立多目标优化模型，基于变异系数自适应差分进化算法，使用货位随机数编码，根据实时货位可行域进行个 体解码，以响应动态货位约束条件。提出了基于层次分析的Pareto解评价方法，从而获得多批作业货位持续优 化的目标权重，为仓储货位决策提供合理方案。多批作业算法实验结果表明：所提算法效果显著优于多目标简 单加权算法，能够有效应用于动态货位决策与优化。 关键词：自动化立体仓库：货位优化：动态约束：持续优化：差分进化：变异系数自适应：层次分析法；多目标： Pareto解 中图分类号：TP18:F274文献标志码：A文章编号：1673-4785(202005-0925-09 中文引用格式：项前，周亚云，陆枳屹，等.响应动态约束条件的多目标货位优化算法研究J川.智能系统学报，2020,15(5)： 925-933. 英文引用格式：XIANG Qian,ZHOU Yayun,,LU Zhiyi,etal.MIuIti--objective location optimization algorithm in response to dynam- ic constraints[JI.CAAI transactions on intelligent systems,2020,15(5):925-933. Multi-objective location optimization algorithm in response to dynamic constraints XIANG Qian,ZHOU Yayun,LU Zhiyi,YU Yufeng (College of Mechanical Engineering,Donghua University,Shanghai 201620,China) Abstract:Considering the storage location decision and optimization problems in automated storage and retrieval sys- tem,we propose a multi-objective logistics optimization algorithm,which considers various optimization objectives, such as the usage status of the pallet and dynamic changes in the allocable storage location.A multi-objective optimiza- tion model is established based on the equilibrium of roadway operations,the stability of the gravity center of shelves, and the shortest operation path.Based on the adaptive variation coefficients'differential evolution algorithm,a random number encoding of the storage location is used to perform individual decoding according to the real-time feasible do- main in response to the dynamic constraint condition.A Pareto optimal solution evaluation method based on the analyt- ic hierarchy process is proposed to obtain the target weight related to the continuous optimization of a multi-batch opera- tion,and a reasonable plan for the storage location decision is provided.The experimental results of the multi-batch op- eration show that the proposed algorithm is significantly better than the simple weighting algorithm,which can be ef- fectively applied to dynamic location decision and optimization. Keywords:automated storage and retrieval system;location optimization;dynamic constraints,continuous optimiza- tion;differential evolution;adaptive variation coefficient,analytic hierarchy process;multi-objective;Pareto solution 收稿日期：2019-06-21.网络出版日期：2020-03-24 货位优化是对仓储货品储存位置的优化分 基金项目：国家重点研发计划项目(2017YFB1304000):上海市 科学技术委员会科研计划项目(I7DZ2283800):松 配，以合理利用存储空间，实现最佳货位布局与 江区产业转型升级发展专项资金重点领域示范应用 项目(2018-01). 降低仓库运营成本。现代仓储管理系统的需求复 通信作者：周亚云.E-mail:zhouyayun(@mail.dhu.edu.cn. 杂，考虑动态资源约束及多样目标的货位决策优
DOI: 10.11992/tis.201906041 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20200323.1704.010.html 响应动态约束条件的多目标货位优化算法研究 项前，周亚云，陆枳屹，余玉风 （东华大学 机械工程学院，上海 201620） 摘 要：针对自动化立库货位决策与优化问题，考虑到优化目标多样、托盘使用状态及可分配货位动态变化等 因素，提出了一种响应动态约束条件的多目标货位优化算法。以巷道作业均衡、货架重心稳定及作业路径最短 建立多目标优化模型，基于变异系数自适应差分进化算法，使用货位随机数编码，根据实时货位可行域进行个 体解码，以响应动态货位约束条件。提出了基于层次分析的 Pareto 解评价方法，从而获得多批作业货位持续优 化的目标权重，为仓储货位决策提供合理方案。多批作业算法实验结果表明：所提算法效果显著优于多目标简 单加权算法，能够有效应用于动态货位决策与优化。 关键词：自动化立体仓库；货位优化；动态约束；持续优化；差分进化；变异系数自适应；层次分析法；多目标； Pareto 解 中图分类号：TP18；F274 文献标志码：A 文章编号：1673−4785(2020)05−0925−09 中文引用格式：项前, 周亚云, 陆枳屹, 等. 响应动态约束条件的多目标货位优化算法研究 [J]. 智能系统学报, 2020, 15(5): 925–933. 英文引用格式：XIANG Qian, ZHOU Yayun, LU Zhiyi, et al. Multi-objective location optimization algorithm in response to dynamic constraints[J]. CAAI transactions on intelligent systems, 2020, 15(5): 925–933. Multi-objective location optimization algorithm in response to dynamic constraints XIANG Qian，ZHOU Yayun，LU Zhiyi，YU Yufeng (College of Mechanical Engineering, Donghua University, Shanghai 201620, China) Abstract: Considering the storage location decision and optimization problems in automated storage and retrieval system, we propose a multi-objective logistics optimization algorithm, which considers various optimization objectives, such as the usage status of the pallet and dynamic changes in the allocable storage location. A multi-objective optimization model is established based on the equilibrium of roadway operations, the stability of the gravity center of shelves, and the shortest operation path. Based on the adaptive variation coefficients' differential evolution algorithm, a random number encoding of the storage location is used to perform individual decoding according to the real-time feasible domain in response to the dynamic constraint condition. A Pareto optimal solution evaluation method based on the analytic hierarchy process is proposed to obtain the target weight related to the continuous optimization of a multi-batch operation, and a reasonable plan for the storage location decision is provided. The experimental results of the multi-batch operation show that the proposed algorithm is significantly better than the simple weighting algorithm, which can be effectively applied to dynamic location decision and optimization. Keywords: automated storage and retrieval system; location optimization; dynamic constraints; continuous optimization; differential evolution; adaptive variation coefficient; analytic hierarchy process; multi-objective; Pareto solution 货位优化是对仓储货品储存位置的优化分 配，以合理利用存储空间，实现最佳货位布局与 降低仓库运营成本。现代仓储管理系统的需求复 杂，考虑动态资源约束及多样目标的货位决策优 收稿日期：2019−06−21. 网络出版日期：2020−03−24. 基金项目：国家重点研发计划项目（2017YFB1304000）；上海市 科学技术委员会科研计划项目（17DZ2283800）；松 江区产业转型升级发展专项资金重点领域示范应用 项目（2018-01）. 通信作者：周亚云. E-mail：zhouyayun@mail.dhu.edu.cn.. 第 15 卷第 5 期 智 能 系 统 学 报 Vol.15 No.5 2020 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2020
·926· 智能系统学报 第15卷 化问题网，更具实际应用价值。 多巷道立体库作业货位优化分配，需考虑货 现有研究中，Dijkstra等)以作业路径最短为 架稳定性、巷道作业均衡及作业路径最短等因 单目标，Ning等以仓储作业时间、货架重心及 素，并满足动态变化库存、货位占用状态及托盘 产品关联性为多目标，分别开展货位决策优化研 使用情况等复杂约束条件，以实现高稳定性、高 究。研究表明，多目标优化模型更符合仓储管理 效率、高准确率的精益仓储目标。 系统的实际需求。Yan等采用层次分析法(ana- 由于托盘使用状态复杂，货位优化的同时还 lytic hierarchy process,AHP)获得权重，并通过简 需进行托盘决策。如图2所示为货位分配流程， 单加权将多目标转化为单目标。但上述研究只解 若是未与货位绑定的库外托盘入库，则需为该作 决了单批次作业下货位决策优化，对多批次作业 业分配空货位：若是与货位绑定的库内托盘入 优化目标值变化规律、货位持续优化能力是否稳 库，则应优先考虑包含该作业所需物料、且承载 定没有作进一步探讨。在构建约束时，Augustyn等 能力足够的库内托盘，使同种物料尽量聚集，若 考虑了仓库规模等环境因素对货位决策优化的影 无满足条件的托盘，则任选一个库外托盘；在执 响，但没有考虑库存及可分配货位等因素的动态 行出库作业时，应为作业分配包含该作业下所有 性。在模型算法实现方面，近年来采用遗传算 物料、且数量足够的库内托盘，否则应提示库存 法、机器学习⑧的货位优化研究不断涌现，差分 不足，无法分配货位。多批作业过程中，作业的 进化算法(differential evolution,.DE)因其卓越的优 货位可行域会动态变化。 化性能而备受关注例，在仓储优化中也有一定的 开始 应用uo。基于差分进化与Pareto最优的货位决 策优化研究还相对较少。 选择无货位 信息的作业 综上，以提高货架稳定性、均衡巷道作业及 N 提高仓储效率为目标，考虑动态库存与可分配货 、库内托盘 人库作业 。出库作业 位等约束条件，基于变异参数自适应差分进化， Y 提出响应动态约束条件的多目标货位优化算法。 库外托盘 已设托盘 进一步基于层次分析法对Pareto解集进行评价， 研究多目标权重对多批作业货位持续优化的影响 Y N 筛选可行的 筛选可行的 规律。 有空货位 库内托盘 库内托盘 任选 一个 1问题描述 库外 N N 托盘 存在 存在 1.1立库货位分配问题 Y Y 获得仓库内所 获得托盘对应 获得托盘对应 如图1所示自动化立体仓库(automated stor- 有可行空货位 的货位 的货位 age and retrieval system,AS/RS)有N个巷道，每个 巷道被一台堆垛机占用，在执行出、入库作业时， 货位优化分配 各巷道的堆垛机可同时工作。假定沿货架垂直方 查询绑定货位 综合评价 向为y方向，沿货架水平方向为x方向，沿货架排 显示无货位 显示无货位 列方向为：方向。 未登记托盘 不支持的作业 报错 类型报错 4 结束 图2自动化立体库货位分配流程 Fig.2 Flow of location assignment in AS/RS 目前大多数仓储管理系统中，出入库作业不 会在同批次内混杂，且人库作业对应的货位可行 域比出库作业大、货位可行域筛选规则复杂，由 于出库作业流程相对简单，简化起见，将重点研 图1自动化立体仓库布局 究入库作业多目标货位优化与评价，以及多批作 Fig.1 Layout of AS/RS 业货位持续优化规律等问题
化问题[1-2] ，更具实际应用价值。 现有研究中，Dijkstra 等 [3] 以作业路径最短为 单目标，Ning 等 [4] 以仓储作业时间、货架重心及 产品关联性为多目标，分别开展货位决策优化研 究。研究表明，多目标优化模型更符合仓储管理 系统的实际需求。Yan[5] 等采用层次分析法（analytic hierarchy process，AHP）获得权重，并通过简 单加权将多目标转化为单目标。但上述研究只解 决了单批次作业下货位决策优化，对多批次作业 优化目标值变化规律、货位持续优化能力是否稳 定没有作进一步探讨。在构建约束时，Augustyn 等 [6] 考虑了仓库规模等环境因素对货位决策优化的影 响，但没有考虑库存及可分配货位等因素的动态 性。在模型算法实现方面，近年来采用遗传算 法 [7] 、机器学习[8] 的货位优化研究不断涌现，差分 进化算法（differential evolution，DE）因其卓越的优 化性能而备受关注[9] ，在仓储优化中也有一定的 应用[10]。基于差分进化与 Pareto[11] 最优的货位决 策优化研究还相对较少。 综上，以提高货架稳定性、均衡巷道作业及 提高仓储效率为目标，考虑动态库存与可分配货 位等约束条件，基于变异参数自适应差分进化， 提出响应动态约束条件的多目标货位优化算法。 进一步基于层次分析法对 Pareto 解集进行评价， 研究多目标权重对多批作业货位持续优化的影响 规律。 1 问题描述 1.1 立库货位分配问题 如图 1 所示自动化立体仓库（automated storage and retrieval system, AS/RS）有 N 个巷道，每个 巷道被一台堆垛机占用，在执行出、入库作业时， 各巷道的堆垛机可同时工作。假定沿货架垂直方 向为 y 方向，沿货架水平方向为 x 方向，沿货架排 列方向为 z 方向。 y x z 图 1 自动化立体仓库布局 Fig. 1 Layout of AS/RS 多巷道立体库作业货位优化分配，需考虑货 架稳定性、巷道作业均衡及作业路径最短等因 素，并满足动态变化库存、货位占用状态及托盘 使用情况等复杂约束条件，以实现高稳定性、高 效率、高准确率的精益仓储目标。 由于托盘使用状态复杂，货位优化的同时还 需进行托盘决策。如图 2 所示为货位分配流程， 若是未与货位绑定的库外托盘入库，则需为该作 业分配空货位；若是与货位绑定的库内托盘入 库，则应优先考虑包含该作业所需物料、且承载 能力足够的库内托盘，使同种物料尽量聚集，若 无满足条件的托盘，则任选一个库外托盘；在执 行出库作业时，应为作业分配包含该作业下所有 物料、且数量足够的库内托盘，否则应提示库存 不足，无法分配货位。多批作业过程中，作业的 货位可行域会动态变化。 开始 已设托盘 选择无货位 信息的作业 筛选可行的 库内托盘 存在 获得托盘对应 的货位 获得仓库内所 有可行空货位 结束 N Y N Y 筛选可行的 库内托盘 存在 Y 获得托盘对应 的货位 Y 有空货位 Y Y N 显示无货位 显示无货位 N N 货位优化分配 综合评价 入库作业 出库作业 库外托盘 Y 库内托盘 N Y 未登记托盘 报错 N N 不支持的作业 类型报错 查询绑定货位 任选 一个 库外 托盘 图 2 自动化立体库货位分配流程 Fig. 2 Flow of location assignment in AS/RS 目前大多数仓储管理系统中，出入库作业不 会在同批次内混杂，且入库作业对应的货位可行 域比出库作业大、货位可行域筛选规则复杂，由 于出库作业流程相对简单，简化起见，将重点研 究入库作业多目标货位优化与评价，以及多批作 业货位持续优化规律等问题。 ·926· 智 能 系 统 学 报 第 15 卷
第5期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·927· 1.2假设条件 料m的数量，m=1,2,,M:wmt为该托盘上物料 1)同种物料可存放在多个托盘上，一个托盘 m的单位质量；M为该托盘存放物料的种类数； 可存放多种物料，一个货位只能放置一个托盘： xgm为决策变量。 2)同一批作业为单纯的出库或者入库； 2.2巷道作业均衡 3)一个作业对应一个货位，一个货位可被不 为了避免托盘在一个巷道内堆积、堆垛机超 同批次的作业重复使用： 负荷工作，影响作业效率及堆垛机寿命，以货架 4)只考虑物料重量，不考虑货架、托盘重量， 中占用货位的标准差方来反映作业的均衡程度， 且各巷道的出入库口在同一侧。 其值越小作业越均衡： 2多目标货位优化模型 f5(A)= 2R-时 T=(T,T2,…,Tn)表示单批作业，n表示该批作 式中：P表示分配货位后第k排货架被占货位数 业总数；Tg={tmlm=1,2,…,M为第q个作业，tm 量，P∈N;P表示优化分配后平均每货架占用货 表示作业q中物料m的总质量，M表示该物料种 位数量。 类数。A={(rg,Cg,kg)q=1,2…,n川为货位集合，通 2.3仓储作业路径最短 过作业g对应货位的排、列、层(，cg,kg),可从仓 若不考虑堆垛机存取货物的时间，则堆垛机 储管理系统中获得该货位上的库存信息。考虑自 在巷道作业路径越短，仓储运行效率越高。假设 动化立体仓库货架重心稳定、巷道作业均衡及就 出入库口S。的坐标为(0,0,0)，巷道的宽度忽略不 近存放等原则，建立以下多目标优化模型。 计，f表示堆垛机的工作总路径： 2.1货架重心稳定 货架质量偏心、重心较高等会影响货架的力 f(A)= nV,2+c2+k 学性能及稳定性，考虑托盘存放“均匀分布”、“上 4=1 轻下重”等原则，一方面使货架x方向重心接近其 式中：n为作业总数；(g,cg,kg)为作业q对应的目 几何中心，避免出现货物“一边倒”、货架倾覆等 标货位坐标。 现象，另一方面使y方向重心低。 2.4货位优化数学模型 fi(A)=1G.-0.5CU 由于目标函数的数值范围大小存在差异，为 f五(4)=G, 了后期更好地评价Pareto解，如式(1)所示，将多 C=22会cc-o5I 目标函数归一化处理为后： fi-minf max fi -min fi 22 5= f-min f max f2-min f 2克o6-5 =c= 公=合 G= 222c. f°=、方-minf max f-min f =1C=1k=1 maxfi =(0.5C-0.5)L,minfi =0.5L (1) Gn=∑QeWe+nkg=l2n maxf =(R-0.5)H,minf=0.5H maxfa VK2+R2+C2,minfa=0 1, 入库作业q分配到货位（口，c,)上 F=[f,ff Xgm= 0, 作业q未分配到货位(，c,k)上 (ra co,ka)E Da,q=1.2.....n -1,出库作业q分配到货位(，c,k)上 s.tGd≤Gma 式中：K、C、R分别为货架的排、列、层总数；L、 式中：max方与min后分别为f的上下限；多排货 W、H分别为货架的长、宽、高：Gx为货架x方向 架中占用货位的离散程度分，用来反映各巷道作 的重心；无表示x方向重心偏离其几何中心的程 业均衡；F为优化目标矢量；(~g,cg,kg)表示作业 度；f方、G,为货架在y方向的重心；Gt表示在第 q所分配的货位；D,表示作业q的动态货位可行 k排r层c列货位上的物料总质量(1≤c≤C,1≤ 域；每个托盘存放的物料总重量应小于托盘的最 r≤R,1≤k≤K,且c、r、k∈Z);qmt为该托盘上物 大承载重量Gmax o
1.2 假设条件 1）同种物料可存放在多个托盘上，一个托盘 可存放多种物料，一个货位只能放置一个托盘； 2）同一批作业为单纯的出库或者入库； 3）一个作业对应一个货位，一个货位可被不 同批次的作业重复使用； 4）只考虑物料重量，不考虑货架、托盘重量， 且各巷道的出入库口在同一侧。 2 多目标货位优化模型 T=(T1,T2, · · · ,Tn) Tq = { tqm|m = 1,2,· · ·, M } tqm A = {(rq, cq, kq ) |q = 1,2,· · ·,n } ( rq, cq, kq ) 表示单批作业，n 表示该批作 业总数； 为第 q 个作业， 表示作业 q 中物料 m 的总质量，M 表示该物料种 类数。 为货位集合，通 过作业 q 对应货位的排、列、层 ，可从仓 储管理系统中获得该货位上的库存信息。考虑自 动化立体仓库货架重心稳定、巷道作业均衡及就 近存放等原则，建立以下多目标优化模型。 2.1 货架重心稳定 货架质量偏心、重心较高等会影响货架的力 学性能及稳定性，考虑托盘存放“均匀分布”、“上 轻下重”等原则，一方面使货架 x 方向重心接近其 几何中心，避免出现货物“一边倒”、货架倾覆等 现象，另一方面使 y 方向重心低。 f1 (A) = |Gx −0.5CL| f2 (A) = Gy Gx = ∑R r=1 ∑C c=1 ∑K k=1 [Grck (c−0.5)L] ∑R r=1 ∑C c=1 ∑K k=1 Grck Gy = ∑R r=1 ∑C c=1 ∑K k=1 [Grck (r −0.5)H] ∑R r=1 ∑C c=1 ∑K k=1 Grck Grck = ∑M m=1 (qmrckwmrck + xqmtqm), q = 1,2,· · ·,n xqm = 1, 入库作业q分配到货位(r, c, k)上 0, 作业q未分配到货位(r, c, k)上 −1, 出库作业q分配到货位(r, c, k)上 Gx f1 f2 Gy Grck 1 ⩽ c ⩽ C 1 ⩽ r ⩽ R 1 ⩽ k ⩽ K qmrck 式中：K、C、R 分别为货架的排、列、层总数；L、 W、H 分别为货架的长、宽、高； 为货架 x 方向 的重心； 表示 x 方向重心偏离其几何中心的程 度； 、 为货架在 y 方向的重心； 表示在第 k 排 r 层 c 列货位上的物料总质量（ ， ， ，且 c、r、k∈Z）； 为该托盘上物 m = 1,2,· · ·, M;wmrck xqm 料 m 的数量， 为该托盘上物料 m 的单位质量；M 为该托盘存放物料的种类数； 为决策变量。 2.2 巷道作业均衡 f3 为了避免托盘在一个巷道内堆积、堆垛机超 负荷工作，影响作业效率及堆垛机寿命，以货架 中占用货位的标准差 来反映作业的均衡程度， 其值越小作业越均衡： f3 (A) = vt 1 K −1 ∑K k=1 ( Pk − P¯ )2 Pk Pk ∈ N ∗ P¯ 式中： 表示分配货位后第 k 排货架被占货位数 量， ； 表示优化分配后平均每货架占用货 位数量。 2.3 仓储作业路径最短 S 0 f4 若不考虑堆垛机存取货物的时间，则堆垛机 在巷道作业路径越短，仓储运行效率越高。假设 出入库口 的坐标为（0,0,0），巷道的宽度忽略不 计， 表示堆垛机的工作总路径： f4 (A) = 1 n ∑n q=1 √ rq 2 +cq 2 +kq 2 ( rq, cq, kq ) 式中：n 为作业总数； 为作业 q 对应的目 标货位坐标。 2.4 货位优化数学模型 fi f ∗ i 由于目标函数的数值范围大小存在差异，为 了后期更好地评价 Pareto 解，如式（1）所示，将多 目标函数 归一化处理为 ： f1 ∗ = f1 −min f1 max f1 −min f1 f2 ∗ = f2 −min f2 max f2 −min f2 f3 ∗ = f3 P¯ f4 ∗ = f4 −min f4 max f4 −min f4 max f1 = (0.5C −0.5)L,min f1 = 0.5L (1) max f2 = (R−0.5)H,min f2 = 0.5H max f4 = √ K2 +R2 +C2 ,min f4 = 0 F = [ f1 ∗ , f2 ∗ , f3 ∗ , f4 ∗ ]T s.t. { ( rq , cq , kq ) ∈ Dq , q = 1,2,· · ·,n Grck ⩽ Gmax max fi min fi fi f ∗ 3 F ( rq, cq, kq ) Dq Gmax 式中： 与 分别为 的上下限；多排货 架中占用货位的离散程度 ，用来反映各巷道作 业均衡； 为优化目标矢量； 表示作业 q 所分配的货位； 表示作业 q 的动态货位可行 域；每个托盘存放的物料总重量应小于托盘的最 大承载重量 。 第 5 期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·927·
·928· 智能系统学报 第15卷 3响应动态约束的多目标优化算法 3)变异操作 式(2)为个体变异公式，变异缩放因子F按 3.1基于自适应差分进化的货位优化算法 式(3)~(5)自适应产生，由F和Fa2部分组 自适应差分进化算法是通过自适应调整进 成。其中F,按时间呈非线性自适应衰减，使算 化参数与进化操作算子，以提高算法的收敛性 法在进化前期有较好的全局搜索能力，进化后期 能。本文采用的多目标差分进化算法(multi-. 有较好的局部勘探能力；F,按每个体自身与种 objective adaptive differential evolution algorithm, 群最优个体目标函数值差异来自适应调整； MOA-DEA),通过变异参数自适应调整，个体解 r、2、3为从1,2，，NP)集合中随机选择的两两 码时根据货位实时可行域响应动态约束条件，以 互不相同且不等于i的整数；F,为F:的下限；F 及多目标Pareto解集综合评价，获得最优作业货 为F:的上限；T为最大迭代次数；teO,T-1) 位。算法原理如下： 为当前迭代次数；为个体目标函数值；fm为种 1)初始化及编码 群内最小目标函数值；f为种群内最大目标函 个体采用0~1的浮点编码，长度等于作业个 数值。 数D,个体基因索引号为作业编号。初始化Pareto =X+F(X-X,) (2) 解集X为空集，随机生成NP个维度为D的初始 (In(F/F) 个体，对应于每个基因的(，cg,k)是货位排、 Fn =F,exp T-1 (3) 列、层。 2)响应动态约束条件的个体解码 F4 f-Jmin faax一fma (4) 通过作业q对应的基因值，、货位实时可行 F=FutFs (5) 域D,{1,C1,k1),(2,c2,k),…,(Cck,),可获得对应 2 4)交叉操作 的目标货位(~g,cg,k,)。通过货位集合A:计算目标 为增加种群的多样性，采用二项式交叉操作 函数值，具体解码过程如算法1所示。 获得实验向量U=G,吃，…， o,如式(6) 算法1响应动态约束条件的个体解码算法 输入个体编码X={,q=1,2…,n,n个 所示，Rad∈(1,2，…，D),可保证ta至少有一个参 数来自；交叉算子CR∈[O,1]。 作业。 rand(0,1)≤CR或j=Rrad 输出货位集合A={(gcg,k)lq=1,2,,m川。 其他 (6) 1)已分配的货位集合C初始化为中 5)选择操作 2)for作业q=1 to n do 基于多目标算法中的占优关系，选择算子如 3)设作业q的可行域D。=中 式(7)所示，LC(U,X)表示U与X中拥挤嫡较 4)if作业q为库外托盘入库 小的个体。 5)库内所有的未占用的空货位为D。 X,X占优或强占优U 6)else if作业q为库内托盘入库 U,U占优或强占优X (7) 7)库内所有包含作业9所需物料，且承载能 LC(U,X),U+1与X互不占优 力足够的货位为D。 6)获取Pareto解集 8)else if作业q为出库 xe2是Pareto最优解，是指xe2使得 9)库内所有包含作业q所需物料，且数量 f)<fx),2为变量x的可行域，Pareto最优解 足够的货位为D 集Xp是指所有Pareto最优解的集合。将第t代 10)D,←-D。-C∥从D,中去除前q-1个作 的Pareto解集与第t什l代的种群合并，用于求解 业已分配的货位 第t+l代的Pareto解集，以获得足够多样性且分 11)ifDg≠ 布在整个Pareto前沿的最优解集。 12)index=card(Dg)x,-1获得货位索引号 3.2基于层次分析法的Pareto最优解评价与选择 13)(Cg,cg,k)←D[index/获得目标货位 从仓储实际应用出发，需从Pareto解集中遴 14) 将(rcg,kg)添加到C中 选出合理的单个解。因此，通过常用的层次分析 15)clse(rgcg,k)=(-1,-1,-l1)/未分配货位 法161计算权重，利用该权重将多目标加权求解， 16)end for 获得综合目标函数值最小的个体，观察多目标权 17）return A; 重与货位持续优化能力间的关系。根据重要性标
3 响应动态约束的多目标优化算法 3.1 基于自适应差分进化的货位优化算法 自适应差分进化算法[12] 是通过自适应调整进 化参数与进化操作算子，以提高算法的收敛性 能。本文采用的多目标差分进化算法[13] （multiobjective adaptive differential evolution algorithm, MOA-DEA），通过变异参数自适应调整，个体解 码时根据货位实时可行域响应动态约束条件，以 及多目标 Pareto 解集综合评价，获得最优作业货 位。算法原理如下： 1）初始化及编码 XP ( rq, cq, kq ) 个体采用 0~1 的浮点编码，长度等于作业个 数 D，个体基因索引号为作业编号。初始化 Pareto 解集 为空集，随机生成 NP 个维度为 D 的初始 个体，对应于每个基因的 是货位排、 列、层。 2）响应动态约束条件的个体解码 xiq Dq { (r1, c1, k1),(r2, c2, k2),· · ·, ( rj , cj , kj )} ( rq, cq, kq ) Ai 通过作业 q 对应的基因值 、货位实时可行 域 ，可获得对应 的目标货位 。通过货位集合 计算目标 函数值，具体解码过程如算法 1 所示。 算法 1 响应动态约束条件的个体解码算法 Xi = { xi q |q = 1,2,· · ·,n } 输 入 个体编码 ， n 个 作业。 Ai = {(rq, cq, kq ) |q = 1,2,· · ·,n } 输出 货位集合 。 1）已分配的货位集合 C 初始化为 ϕ 2） for 作业 q=1 to n do 3） 设作业 q 的可行域 Dq = ϕ 4） if 作业 q 为库外托盘入库 5） 库内所有的未占用的空货位为 Dq 6） else if 作业 q 为库内托盘入库 Dq 7）库内所有包含作业 q 所需物料，且承载能 力足够的货位为 8） else if 作业 q 为出库 Dq 9） 库内所有包含作业 q 所需物料，且数量 足够的货位为 10） Dq ← Dq −C //从 Dq 中去除前 q-1 个作 业已分配的货位 11） if Dq , ϕ indexq = ⌈ card( Dq ) xi q ⌉ 12） −1 //获得货位索引号 ( rq, cq, kq ) ← D [ indexq ] 13） //获得目标货位 ( rq, cq, kq ) 14） 将 添加到 C 中 ( rq, cq, kq ) 15） else = (−1,−1,−1) //未分配货位 16） end for 17） return Ai 3）变异操作 F Fi1 Fi2 Fi1 Fi2 {1,2,· · ·,NP} Fl Fi Fu Fi t ∈ [0,T −1] fi fmin fmax 式（2）为个体变异公式，变异缩放因子 按 式 （ 3） ~（ 5）自适应产生，由 和 2 部分组 成。其中 按时间呈非线性自适应衰减，使算 法在进化前期有较好的全局搜索能力，进化后期 有较好的局部勘探能力； 按每个体自身与种 群最优个体目标函数值差异来自适应调整[14] ； r1、r2、r3 为从 集合中随机选择的两两 互不相同且不等于 i 的整数； 为 的下限； 为 的上限； T 为最大迭代次数； 为当前迭代次数； 为个体目标函数值； 为种 群内最小目标函数值； 为种群内最大目标函 数值。 V t i = X t r1 + F ( X t r2 − X t r3 ) (2) Fi1 = Fu exp( ln(Fl/Fu) T−1 t ) (3) Fi2= fi − fmin fmax − fmin (4) F = Fi1 + Fi2 2 (5) 4）交叉操作 U t i = [ u t 1,i , u t 2,i , ··· , u t D,i ] Ri,rand ∈ (1,2, · ··,D) u t j,i V t i CR ∈ [0,1] 为增加种群的多样性，采用二项式交叉操作 获得实验向量 ，如式（6） 所示， ，可保证 至少有一个参 数来自 ；交叉算子 。 u t j,i = { v t j,i , rand(0,1) ⩽ CR或j = Ri,rand x t j,i , 其他 (6) 5）选择操作 LC(U t+1 i ,X t i ) U t+1 i X t i 基于多目标算法中的占优关系，选择算子如 式（7）所示， 表示 与 中拥挤熵较 小的个体[15]。 X t+1 i = X t i , X t i占优或强占优U t+1 i U t+1 i , U t+1 i 占优或强占优X t i LC(U t+1 i ,X t i ), U t+1 i 与X t i互不占优 (7) 6）获取 Pareto 解集 x ∗ ∈ Ω ∄x ∈ Ω f(x) < f(x ∗ ) Ω XP 是 Pareto 最优解，是指 使 得 ， 为变量 x 的可行域，Pareto 最优解 集 是指所有 Pareto 最优解的集合。将第 t 代 的 Pareto 解集与第 t+1 代的种群合并，用于求解 第 t+1 代的 Pareto 解集，以获得足够多样性且分 布在整个 Pareto 前沿的最优解集。 3.2 基于层次分析法的 Pareto 最优解评价与选择 从仓储实际应用出发，需从 Pareto 解集中遴 选出合理的单个解。因此，通过常用的层次分析 法 [16] 计算权重，利用该权重将多目标加权求解， 获得综合目标函数值最小的个体，观察多目标权 重与货位持续优化能力间的关系。根据重要性标 ·928· 智 能 系 统 学 报 第 15 卷
第5期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·929· 度构建判断矩阵B=(b)am,按列归一化得到矩阵 1)设置种群规模NP,最大迭代次数T,终止 C=(c)xm,C矩阵的行元素之和除以元素总和可求 条件，交叉算子CR;初始化种群，个体向量维度 得各目标的权重。 D等于作业数量n,对个体进行随机数编码，初始 化Pareto解集为空集。 Ci= 2)判断是否达到最大迭代次数T,若是，则从 Pareto解中遴选出综合目标函数值最小的个体： 若不是，则进行下一步。 k=1 3)进行变异交叉操作，并计算目标函 = 数值。 11 4)判断U1与X的占优关系，并选择个 通过层次分析法确定x方向重心的权重、 体X。 y方向重心的权重2、多排货架中占用货位的离 5)比较目标向量X与Pareto解集Xp中所有 散程度权重及作业距离的权重4。MOADEA 向量，更新Pareto解集。 求解获得Pareto解集后，根据式(8)计算Pareto解 6)迭代次数仁什1，种群中合并第1代获取的 集中所有个体的综合目标函数值F,选择F最小 Pareto解，转到2)。 的个体为最优个体：若以式(8)为单目标进行优 化求解，则称之为简单加权差分进化算法(simple 4实验与分析 weighted adaptive differential evolution algorithms, 以图1所示的仓储环境为例进行实验，仓库 SWADEA),后续实验中将对2种方法优化结果 共有6排货架、3条巷道，每排货架4层4列，共 进行对比。 96个货位。相邻2货位之间间隔为1个距离单 F=min(+f+s+sfa) (8) 位，相邻2巷道之间间隔为2个距离单位。实验 3.3算法的流程 计算机配置为Intel(R)Core(TM)/i7CPU/1.8GHZ/8GB 所提算法基本流程如图3所示，具体步骤 内存，操作系统为Windows10,使用C#、MAT- 如下： LAB作为编程及分析工具。 4.1多批次作业货位持续优化实验与分析 开始 库内托盘入库、出库作业对货位占有率影响 设置DE参数 不大，且出入库混合比例等影响因素难以控制， 章” 为了观察多批次作业下，随着货位占有率的增 编码、初始化种群 加，多目标权重对货位持续优化的影响规律。随 机生成96个库外托盘入库作业，每8个作业为一 初始化Pareto解集 批共12批，每个作业随机包含115种物料，每种 物料存储数量随机。每个方案采用简单加权单目 1>7 根据权重从Pareto 解集中遴选最优个体 标SWADEA及多目标自适应MOADEA,分别单 N 独实验10次，通过多批作业的综合目标函数值分 变异操作 结束 析货位持续优化能力。 选取算法最大迭代次数T=500,种群规模 交叉操作 NP=50,变异参数F为自适应变化，范围是 个体解码 0.10.5交叉概率CR为0.5。如表1所示，基于层 次分析法仅选择同样重要、略重要2个重要性标 目标函数计算 度，设置了所有可能的权重方案。 实验结果如图4所示，每个子图的横坐标为 选择操作 作业批次，纵坐标为10次测试下，综合目标函数 下 值F的平均值。方案2、4、8、9、10、14的综合目 更新Pareto解集 标函数值F随作业批次增加不断增加，其波动范 图3多目标自适应差分进化算法流程 围大、不稳定，货位持续优化能力差；方案1、3、 Fig.3 Flowchart of MOADEA 7,综合目标函数值F随作业批次增加而趋于平
B= ( bi j) n×n C= ( ci j) n×n 度构建判断矩阵 ，按列归一化得到矩阵 ，C 矩阵的行元素之和除以元素总和可求 得各目标的权重。 ci j = bi j ∑n k=1 ak j ωi = ∑n k=1 cik ∑n j=1 ∑n i=1 ci j ω1 ω2 ω3 ω4 通过层次分析法确定 x 方向重心的权重 、 y 方向重心的权重 、多排货架中占用货位的离 散程度权重 及作业距离的权重 。MOADEA 求解获得 Pareto 解集后，根据式（8）计算 Pareto 解 集中所有个体的综合目标函数值 F，选择 F 最小 的个体为最优个体；若以式（8）为单目标进行优 化求解，则称之为简单加权差分进化算法（simple weighted adaptive differential evolution algorithms， SWADEA），后续实验中将对 2 种方法优化结果 进行对比。 F = min(ω1 f1 +ω2 f2 +ω3 f3 +ω4 f4) (8) 3.3 算法的流程 所提算法基本流程如图 3 所示，具体步骤 如下： 开始 设置 DE 参数 编码、初始化种群 初始化 Pareto 解集 t >T 变异操作 交叉操作 目标函数计算 更新 Pareto 解集 N t=t+1 根据权重从 Pareto 解集中遴选最优个体 Y 结束 选择操作 个体解码 图 3 多目标自适应差分进化算法流程 Fig. 3 Flowchart of MOADEA 1) 设置种群规模 NP，最大迭代次数 T，终止 条件，交叉算子 CR；初始化种群，个体向量维度 D 等于作业数量 n，对个体进行随机数编码，初始 化 Pareto 解集为空集。 2) 判断是否达到最大迭代次数 T，若是，则从 Pareto 解中遴选出综合目标函数值最小的个体； 若不是，则进行下一步。 3) 进行变异交叉操作，并计算目标函 数值。 U t+1 i X t i X t+1 i 4) 判 断 与 的占优关系，并选择个 体 。 X t 5) 比较目标向量 i 与 Pareto 解集 XP 中所有 向量，更新 Pareto 解集。 6) 迭代次数 t=t+1，种群中合并第 t 代获取的 Pareto 解，转到 2)。 4 实验与分析 以图 1 所示的仓储环境为例进行实验，仓库 共有 6 排货架、3 条巷道，每排货架 4 层 4 列，共 96 个货位。相邻 2 货位之间间隔为 1 个距离单 位，相邻 2 巷道之间间隔为 2 个距离单位。实验 计算机配置为 Intel(R)Core(TM)/i7CPU/1.8GHZ/8GB 内存，操作系统为 Windows10，使用 C#、MATLAB 作为编程及分析工具。 4.1 多批次作业货位持续优化实验与分析 库内托盘入库、出库作业对货位占有率影响 不大，且出入库混合比例等影响因素难以控制， 为了观察多批次作业下，随着货位占有率的增 加，多目标权重对货位持续优化的影响规律。随 机生成 96 个库外托盘入库作业，每 8 个作业为一 批共 12 批，每个作业随机包含 1~15 种物料，每种 物料存储数量随机。每个方案采用简单加权单目 标 SWADEA 及多目标自适应 MOADEA，分别单 独实验 10 次，通过多批作业的综合目标函数值分 析货位持续优化能力。 选取算法最大迭代次数 T=500，种群规模 NP=50 ，变异参 数 F 为自适应变化，范围 是 0.1~0.5 交叉概率 CR 为 0.5。如表 1 所示，基于层 次分析法仅选择同样重要、略重要 2 个重要性标 度，设置了所有可能的权重方案。 实验结果如图 4 所示，每个子图的横坐标为 作业批次，纵坐标为 10 次测试下，综合目标函数 值 F 的平均值。方案 2、4、8、9、10、14 的综合目 标函数值 F 随作业批次增加不断增加，其波动范 围大、不稳定，货位持续优化能力差；方案 1、3、 7，综合目标函数值 F 随作业批次增加而趋于平 第 5 期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·929·