第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·
·930· 智能系统学报 第15卷 稳，其波动范围小，货位持续优化能力强；且 差σ=0.036均较小，解的质量好且稳定，即货位持 MOADEA的综合目标函数值F明显优于 续优化能力好，适用于ASRS中对货位持续优化 SWADEA,而不同权重会影响货位的持续优化能 要求较高的作业场景，以减少盘点周期、降低仓 力。方案7中12批作业F的均值=0.188，标准 储成本、提高作业效率。 米—SWADEA -MOADEA 0.350 0.43 0.280 0.560 0.340 0.296 0.37 0.257 0.483 0.297 0.243 0.233 -0.407 0259 0.190 0.25 0.210 0.330 0.210 24681012 24681012 24681012 24681012 24681012 作业批次 作业批次 作业批次 作业批次 作业批次 (a)方案1 (b)方案2 (c)方案3 (d)方案4 (e)方案5 0.38 0.30 0.43 0.320 0.550 0.34 0.25 0.38 028 0.467 三0.30 三0.20 0.33 m0253 盖038 0.26 0.15 0.28L 0.220 0.300 24681012 24681012 24681012 24681012 24681012 作业批次 作业批次 作业批次 作业批次 作业批次 (①方案6 (g)方案7 (h)方案8 (①)方案9 G方案10 0.31 0.42 0.350 0.45 0.360 0.27 0.38 女0.310 0.39 0.323 0.23 0.33 0.276 0.33 0.286 0.19 0.28 0.240 0.27 24681012 24681012 24681012 24681012 0.250 24681012 作业批次 作业批次 作业批次 作业批次 作业批次 k)方案11 0)方案12 (m)方案13 (n)方案14 (o)方案15 图4不同权重下SWADEA及MOADEA优化结果对比 Fig.4 Comparison of SWADEA and MOADEA optimization results under different weight 当选择y方向重心的权重2、作业路径的权 果的差异，选择持续优化能力较好的4组权重方 重ω，较大的方案时，综合优化目标函数值F不断 案（方案1、3、7、11），分析SWADEA与MOADEA 增加，优化结果越来越差，货位的持续优化能力 各子目标函数值。如图5所示，随着作业批次的 差。相反，选择x方向重心与货架中心偏离程度 增加，x方向重心偏离货架中心程度片越小，y方 的权重ω、多排货架中占用货位的离散程度的权 向重心方越高，占用货位离散程度在达到较 重较大时，货位的持续优化能力较强，更符合 优后趋于平稳，作业路径分越长。对比2种方 仓储持续、动态作业的需求。 法，MOADEA求解结果显著优于SWADEA,且 为了进一步分析影响货位持续优化能力的因 MOADEA综合目标函数值F的均值更加平稳。 素，并更好地观察SWADEA与MOADEA优化结 可见，相比SWADEA,MOADEA更易获得最优解。 +—SWADEA ◆—MOADEA 货架稳定(x方向) 货架稳定y方向) 占用货位离散程度 作业路径 0.160 0.550 0.400 0.82 0.116 0.457 0.266 0.68 ● 0.073 0.363 0.133 0.5 0.030L 0.270 0.40 24681012 24681012 468101 2 4681012 作业批次 作业批次 作业批次 作业批次 (a)方案1各目标函数值对比
µ 稳，其波动范围小，货位持续优化能力强； 且 MOADE A 的综合目标函数 值 F 明显优 于 SWADEA，而不同权重会影响货位的持续优化能 力。方案 7 中 12 批作业 F 的均值 =0.188，标准 差 σ=0.036 均较小，解的质量好且稳定，即货位持 续优化能力好，适用于 AS/RS 中对货位持续优化 要求较高的作业场景，以减少盘点周期、降低仓 储成本、提高作业效率。 SWADEA MOADEA 0.350 目标 F0.296 0.243 0.190 2 4 6 8 10 12 作业批次 (a) 方案1 0.43 目标 F0.37 0.31 0.25 2 4 6 8 10 12 作业批次 (b) 方案2 0.280 目标 F0.257 0.233 0.210 2 4 6 8 10 12 作业批次 (c) 方案3 0.560 目标 F 0.483 0.407 0.330 2 4 6 8 10 12 作业批次 (d) 方案4 0.340 目标 F 0.297 0.253 0.210 2 4 6 8 10 12 作业批次 (e) 方案5 0.38 目标 F 0.34 0.30 0.26 2 4 6 8 10 12 作业批次 (f) 方案6 0.30 目标 F0.25 0.20 0.15 2 4 6 8 10 12 作业批次 (g) 方案7 0.43 目标 F 0.38 0.33 0.28 2 4 6 8 10 12 作业批次 (h) 方案8 0.320 目标 F 0.286 0.253 0.220 2 4 6 8 10 12 作业批次 (i) 方案9 0.550 目标 F 0.467 0.383 0.300 2 4 6 8 10 12 作业批次 (j) 方案10 0.31 目标 F 0.27 0.23 0.19 2 4 6 8 10 12 作业批次 0.42 目标 F0.38 0.33 0.28 2 4 6 8 10 12 作业批次 0.350 目标 F0.310 0.276 0.240 2 4 6 8 10 12 作业批次 0.45 目标 F 0.39 0.33 0.27 2 4 6 8 10 12 作业批次 0.360 目标 F 0.323 0.286 0.250 2 4 6 8 10 12 作业批次 (k) 方案11 (l) 方案12 (m) 方案13 (n) 方案14 (o) 方案15 图 4 不同权重下 SWADEA 及 MOADEA 优化结果对比 Fig. 4 Comparison of SWADEA and MOADEA optimization results under different weight ω2 ω4 ω1 ω3 当选择 y 方向重心的权重 、作业路径的权 重 较大的方案时，综合优化目标函数值 F 不断 增加，优化结果越来越差，货位的持续优化能力 差。相反，选择 x 方向重心与货架中心偏离程度 的权重 、多排货架中占用货位的离散程度的权 重 较大时，货位的持续优化能力较强，更符合 仓储持续、动态作业的需求。 为了进一步分析影响货位持续优化能力的因 素，并更好地观察 SWADEA 与 MOADEA 优化结 f ∗ 1 f ∗ 2 f ∗ 3 f ∗ 4 果的差异，选择持续优化能力较好的 4 组权重方 案（方案 1、3、7、11），分析 SWADEA 与 MOADEA 各子目标函数值。如图 5 所示，随着作业批次的 增加，x 方向重心偏离货架中心程度 越小，y 方 向重心 越高，占用货位离散程度 在达到较 优后趋于平稳，作业路径 越长。对比 2 种方 法，MOADEA 求解结果显著优于 SWADEA，且 MOADEA 综合目标函数值 F 的均值更加平稳。 可见，相比 SWADEA，MOADEA 更易获得最优解。 (a) 方案1各目标函数值对比 0.160 0.116 0.073 0.030 f1 * SWADEA MOADEA 货架稳定 (x 方向) 作业批次 2 4 6 8 10 12 货架稳定 (y 方向) 0.550 0.457 0.363 0.270 作业批次 2 4 6 8 f2 * 10 12 占用货位离散程度 0.400 0.266 0.133 0 2 4 6 8 f3 * 10 12 作业路径 0.82 0.68 0.54 0.40 作业批次 作业批次 2 4 6 8 f4 * 10 12 ·930· 智 能 系 统 学 报 第 15 卷
第5期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·931· +—SWADEA ◆—MOADEA 货架稳定(x方向) 货架稳定(y方向) 占用货位离散程度 作业路径 0.200 0.54 0.400 0.800 0.143 0.44 0.267 0.633 0.087 0.34 0.133 0.467 0.030 24681012 0.24 24681012 2468102 0.300 24681012 作业批次 作业批次 作业批次 作业批次 (b)方案3各目标函数值对比 +—SWADEA ◆—MOADEA 0.15 货架稳定(x方向) 货架稳定y方向) 占用货位离散程度 作业路径 0.530 0.400E 0.800 0.453 0.267 0.633 0.07 0.377 0.133 0.4671 0.03L 0.300 o 24681012 2 4681012 2 46810 0.030 2 4681012 作业批次 作业批次 作业批次 作业批次 (©)方案7各目标函数值对比 +一SWADEA ◆MOADEA 货架稳定x方向) 货架稳定方向) 占用货位离散程度 作业路径 0.200 0.55 0.400 0.800 0.143 0.45 0.267 0.683 0.087 0.35 0.133 0.567 0.030 0.25 0.470 24681012 24681012 246810 2 4681012 作业批次 作业批次 作业批次 作业批次 (@)方案11各目标函数值对比 图5方案1、3、7及11下SWADEA与MOADEA优化结果对比 Fig.5 Comparison of optimization results between SWADEA and MOADEA by schemes 1.3,7 and 11 为了观察变异系数自适应DE算法的改进效 表1基于层次分析法的不同权重方案 果，与基于标准DE的多目标算法MODEA相比， Table 1 Different weight schemes based on AHP MODEA的固定参数F=0.5,CR=0.5,采用方案 方案 1 W2 w Ws 7的权重，在同样初始库存、单批作业下，对2种 1 0.167 0.167 0.500 0.167 算法分别进行10次独立试验。如图6所示，采用 2 0.167 0.500 0.167 0.167 式(2)~(5)中的变异参数自适应方法，综合目标 3 0.500 0.167 0.167 0.167 4 0.167 函数值F显著优于标准DE算法。 0.167 0.167 0.500 5 0.125 0.375 0.375 0.125 0.220 ■MOADEA口MODEA 6 0.125 0.125 0.375 0.375 0.215 7 0.375 0.125 0.375 0.125 8 0.375 0.125 0.125 0.375 0.205 9 0.375 0.375 0.125 0.125 0.200 10 0.125 0.375 0.125 0.375 0.195 11 0.300 0.300 0.300 0.100 0.190 0.100 0.300 0.300 0.300 45678910 实验次数 13 0.300 0.100 0.300 0.300 14 0.300 0.300 0.100 0.300 图6 MOADEA与MODEA算法效果对比 15 0.250 0.250 0.250 0.250 Fig.6 Comparison of effects between MOADEA and MODEA
SWADEA MOADEA 0.200 0.143 0.087 0.030 f1 * (b) 方案3各目标函数值对比 货架稳定 (x 方向) 作业批次 2 4 6 8 10 12 货架稳定 (y 方向) 0.54 0.44 0.34 0.24 作业批次 2 4 6 8 f2 * 10 12 占用货位离散程度 0.400 0.267 0.133 0 2 4 6 8 f3 * 10 12 作业路径 0.800 0.633 0.467 0.300 作业批次 作业批次 2 4 6 8 f4 * 10 12 货架稳定 (y 方向) 0.530 0.453 0.377 0.300 作业批次 2 4 6 8 f2 * 10 12 货架稳定 (x 方向) 0.15 0.11 0.07 0.03 作业批次 2 4 6 8 f1 * 10 12 (c) 方案7各目标函数值对比 占用货位离散程度 0.400 0.267 0.133 0 作业批次 2 4 6 8 f3 * 10 12 作业路径 0.800 0.633 0.467 0.030 作业批次 2 4 6 8 f4 * 10 12 SWADEA MOADEA 货架稳定 (y 方向) 0.55 0.45 0.35 0.25 作业批次 2 4 6 8 f2 * 10 12 货架稳定 (x 方向) 0.200 0.143 0.087 0.030 作业批次 2 4 6 8 f1 * 10 12 (d) 方案11各目标函数值对比 占用货位离散程度 0.400 0.267 0.133 0 作业批次 2 4 6 8 f3 * 10 12 作业路径 0.800 0.683 0.567 0.470 作业批次 2 4 6 8 f4 * 10 12 SWADEA MOADEA 图 5 方案 1、3、7 及 11 下 SWADEA 与 MOADEA 优化结果对比 Fig. 5 Comparison of optimization results between SWADEA and MOADEA by schemes 1、3、7 and 11 为了观察变异系数自适应 DE 算法的改进效 果，与基于标准 DE 的多目标算法 MODEA 相比， MODEA 的固定参数 F=0.5，CR=0.5，采用方案 7 的权重，在同样初始库存、单批作业下，对 2 种 算法分别进行 10 次独立试验。如图 6 所示，采用 式（2）~（5）中的变异参数自适应方法，综合目标 函数值 F 显著优于标准 DE 算法。 0.190 0.195 0.200 0.205 0.210 0.215 0.220 1 2 3 4 5 6 7 8 9 10 综合目标值 F MOADEA 实验次数 MODEA 图 6 MOADEA 与 MODEA 算法效果对比 Fig. 6 Comparison of effects between MOADEA and MODEA 表 1 基于层次分析法的不同权重方案 Table 1 Different weight schemes based on AHP 方案 ω1 ω2 ω3 ω4 1 0.167 0.167 0.500 0.167 2 0.167 0.500 0.167 0.167 3 0.500 0.167 0.167 0.167 4 0.167 0.167 0.167 0.500 5 0.125 0.375 0.375 0.125 6 0.125 0.125 0.375 0.375 7 0.375 0.125 0.375 0.125 8 0.375 0.125 0.125 0.375 9 0.375 0.375 0.125 0.125 10 0.125 0.375 0.125 0.375 11 0.300 0.300 0.300 0.100 12 0.100 0.300 0.300 0.300 13 0.300 0.100 0.300 0.300 14 0.300 0.300 0.100 0.300 15 0.250 0.250 0.250 0.250 第 5 期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·931·
·932· 智能系统学报 第15卷 4.2算法结果 表2 MOADEA与SWADEA入库作业优化结果对比 为验证所提模型及算法在实际仓储作业中的 Table 2 Comparison of the results by MOADEA and SWADEA 有效性，在仓库单元设置初始库存的情况下，随 机生成库内托盘入库、库外托盘入库共20个作 目标项 SWADEA MOADEA优化比率/% 业，而出库作业优化求解过程与库内托盘入库基 重心稳定(x方向)f片 0.102 0.096 6 本类似，在此不再赘述。如图7所示，气泡表示 重心稳定(y方向)f分 0.480 0.426 11 经MOADEA求解后获得的Pareto解集，横坐标为 占用货位离散系数后 0.106 0.106 0 疗，纵坐标为，气泡越小表示方值越小，气泡颜 作业路径f: 0.593 0.552 7 色越浅表示分值越小，虚线圈出的气泡表示采用 方案7权重选择出的最优个体。 综合目标F 0.212 0.202 4.7 0.7 日0.50 注：优化比率=(SWADEA的指标-MOADEA的指标)/SWADEA 0.6 的指标×100% 0.48 0.5 0.46 5结束语 0.4 0.44 考虑仓储作业中资源约束的动态性，采用多 目标差分进化算法求解动态货位决策优化问题， 0.2 0.42 进而基于层次分析法从Pareto解中遴择最符合需 0.1 0.40 求的个体，并分析目标权重与货位持续优化能力 0.45 间的关系。实验结果表明： 0.50 0.55 0.60 0.65 1)所提优化算法能够响应货位可行域等动态 约束条件，符合实际仓储作业需求； 图7多目标差分进化Pareto解集及最优个体结果 Fig.7 Results of pareto solutions and optimal individual 2)相比于简单加权差分进化算法，所提算法 by MOADEA 的解更优，分配货位后货架重心稳定，作业均衡 从图8及表2可看出，MOADEA优化后的库 且路径短； 位布局达到了理想的结果，分配的作业货位均匀 3)优化目标的权重将影响货位持续优化能 分布在各巷道，货位更接近于货架底层，离出人 力，当货架x方向稳定性与货位占有离散程度权 库口更近，更靠近货架中心。相比于SWADEA,经 重取较大时，货位优化持续稳定。 MOADEA优化后，货架垂直方向重心降低了11%， 综上所述，所提算法可有效解决动态货位决 水平方向重心改善了6%，作业路径缩短了7%， 策优化问题，但未考虑出入库混批等复杂情形， 综合目标函数值优化了4.7%。实验中单批作业 出入库混批作业货位决策优化有待进一步研究， 平均优化时间约为3~4s。MOADEA在企业中已 算法性能也有待进一步提高。 得到初步应用，能够有效解决动态货位优化问题。 R01 R02 R03 R04 R05 参考文献： [1]JIAO Yuling,XING Xiaocui,ZHANG Peng,et al.Multi- (a)仓库初始库存布局 objective storage location allocation optimization and sim- R02 R03 R04 R05 ulation analysis of automated warehouse based on multi- R06 population genetic algorithm[J].Concurrent engineering. 2018.26(4):367-377 (b)SWDEA货位优化结果 [2]REYES JJR,SOLANO-CHARRIS E L,MONTOYA- R02 TORRES J R.The storage location assignment problem:a R03 R04 R05 R06 literature review[J].International journal of industrial en gineering computations,2019,10(2):199-224. ☐空货位☐有托盘的货位☒库外托盘人库回库内托盘人库 [3]DIJKSTRA A S,ROODBERGEN K J.Exact route-length (c)MODEA货位优化结果 formulas and a storage location assignment heuristic for 图8不同方案下货位优化结果对比 picker-to-parts warehouses.Transportation research part Fig.8 Comparison of the results of the optimization of the E:logistics and transportation review,2017,102:38-59. storage location by different schemes [4]NING Ding,LI Wang,WEI Teng,et al.Research on op-
4.2 算法结果 f ∗ 4 f ∗ 1 f ∗ 3 f ∗ 2 为验证所提模型及算法在实际仓储作业中的 有效性，在仓库单元设置初始库存的情况下，随 机生成库内托盘入库、库外托盘入库共 20 个作 业，而出库作业优化求解过程与库内托盘入库基 本类似，在此不再赘述。如图 7 所示，气泡表示 经 MOADEA 求解后获得的 Pareto 解集，横坐标为 ，纵坐标为 ，气泡越小表示 值越小，气泡颜 色越浅表示 值越小，虚线圈出的气泡表示采用 方案 7 权重选择出的最优个体。 f * 1 f 4 * 0.45 0.50 0.55 0.60 0.65 0.50 0.48 0.46 0.44 0.42 0.40 0.6 0.7 0.5 0.4 0.3 0.2 0.1 图 7 多目标差分进化 Pareto 解集及最优个体结果 Fig. 7 Results of pareto solutions and optimal individual by MOADEA 从图 8 及表 2 可看出，MOADEA 优化后的库 位布局达到了理想的结果，分配的作业货位均匀 分布在各巷道，货位更接近于货架底层，离出入 库口更近，更靠近货架中心。相比于 SWADEA，经 MOADEA 优化后，货架垂直方向重心降低了 11%， 水平方向重心改善了 6%，作业路径缩短了 7%， 综合目标函数值优化了 4.7%。实验中单批作业 平均优化时间约为 3~4 s。MOADEA 在企业中已 得到初步应用，能够有效解决动态货位优化问题。 R01 R02 R03 R04 R06 R05 (a) 仓库初始库存布局 R01 R02 R03 R04 R06 R05 R02 R03 R04 R06 R05 (b) SWDEA 货位优化结果 R01 空货位 有托盘的货位 库外托盘入库 库内托盘入库 (c) MODEA 货位优化结果 图 8 不同方案下货位优化结果对比 Fig. 8 Comparison of the results of the optimization of the storage location by different schemes 表 2 MOADEA 与 SWADEA 入库作业优化结果对比 Table 2 Comparison of the results by MOADEA and SWADEA 目标项 SWADEA MOADEA 优化比率/% f ∗ 重心稳定（ 1 x方向） 0.102 0.096 6 f ∗ 重心稳定（ 2 y方向） 0.480 0.426 11 f ∗ 占用货位离散系数 3 0.106 0.106 0 f ∗ 作业路径 4 0.593 0.552 7 综合目标 F 0.212 0.202 4.7 注：优化比率=（SWADEA的指标-MOADEA的指标）/SWADEA 的指标×100% 5 结束语 考虑仓储作业中资源约束的动态性，采用多 目标差分进化算法求解动态货位决策优化问题， 进而基于层次分析法从 Pareto 解中遴择最符合需 求的个体，并分析目标权重与货位持续优化能力 间的关系。实验结果表明： 1）所提优化算法能够响应货位可行域等动态 约束条件，符合实际仓储作业需求； 2）相比于简单加权差分进化算法，所提算法 的解更优，分配货位后货架重心稳定，作业均衡 且路径短； 3）优化目标的权重将影响货位持续优化能 力，当货架 x 方向稳定性与货位占有离散程度权 重取较大时，货位优化持续稳定。 综上所述，所提算法可有效解决动态货位决 策优化问题，但未考虑出入库混批等复杂情形， 出入库混批作业货位决策优化有待进一步研究， 算法性能也有待进一步提高。 参考文献： JIAO Yuling, XING Xiaocui, ZHANG Peng, et al. Multiobjective storage location allocation optimization and simulation analysis of automated warehouse based on multipopulation genetic algorithm[J]. Concurrent engineering, 2018, 26(4): 367–377. [1] REYES J J R, SOLANO-CHARRIS E L, MONTOYATORRES J R. The storage location assignment problem: a literature review[J]. International journal of industrial engineering computations, 2019, 10(2): 199–224. [2] DIJKSTRA A S, ROODBERGEN K J. Exact route-length formulas and a storage location assignment heuristic for picker-to-parts warehouses[J]. Transportation research part E: logistics and transportation review, 2017, 102: 38–59. [3] [4] NING Ding, LI Wang, WEI Teng, et al. Research on op- ·932· 智 能 系 统 学 报 第 15 卷
第5期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·933· timization of warehouse allocation problem based on im- constrained multi-objective optimization problems with proved genetic algorithm[C]//Proceedings of the 13th In- low feasible ratio[J].Applied soft computing,2019,80: ternational Conference on Bio-Inspired Computing:Theor- 42-56. ies and Applications.Beijing,China,2018:252-263. [14]项前，周亚云，吕志军.资源约束项目的改进差分进化 [5]YAN Bo,YAN Chang,LONG Feng,et al.Multi-objective 参数控制及双向调度算法.自动化学报，2020.46(2)： optimization of electronic product goods location assign- 283-293. ment in stereoscopic warehouse based on adaptive genetic XIANG Qian,ZHOU Yayun,LV Zhijun.Improved dif- algorithm[J].Journal of intelligent manufacturing,2018, ferential evolution parameter control and bidirectional 29(6):1273-1285. scheduling algorithm for the resource-constrained [6]AUGUSTYN L,TONE L.Effectiveness of product stor- project[J].Acta automatica sinica,2020,46(2):283-293 age policy according to classification criteria and ware- [15]吴亮红，王耀南.动态差分进化算法及其应用M).北 house size[J].FME transactions,2019,47(1):142-150. 京：科学出版社，2014：113 [7]CHENG Chibin,WENG Yuchi.Warehouse storage assign- WU Lianghong,WANG Yaonan.Dynamic differential ment by genetic algorithm with multi-objectives[C]//Pro- evolution algorithm and application[M].Beijing:Science ceedings of the 2nd International Conference on Intelli- Press..2014:113. gent Human Systems Integration.San Diego,USA,2019: [16]WANG Kun,ZHAO Wei,CUI Junjie,et al.A K-anonym- 300-305 ous clustering algorithm based on the analytic hierarchy [8]LEI Bin,JIANG Zhaoyuan,MU Haibo.Integrated optim- process[J].Journal of visual communication and image ization of mixed cargo packing and cargo location assign- representation,2019,59:76-83. ment in automated storage and retrieval systems[J].Dis- 作者简介： crete dynamics in nature and society,2019,2019:9072847. 项前，副教授，博士，主要研究方 [9]DAS S,MULLICK SS,SUGANTHAN P N.Recent ad- 向为数字化制造、智慧物流、计算智能 vances in differential evolution-an updated survey[J]. 及应用。主持和参加国家、省部级及 Swarm and evolutionary computation,2016,27:1-30. 企业科研项目20余项，获上海市科学 技术进步奖二等奖1项。发表学术论 [10]YU Yadong,MA Haiping,YU Mei,et al.Multipopula- 文40余篇。 tion management in evolutionary algorithms and applica- tion to complex warehouse scheduling problems[J].Com- plexity,.2018.2018:4730957. 周亚云，硕士研究生，主要研究方 [11]WISITTIPANICH W.HENGMEECHAI P.A multi-ob- 向为智能仓储。 jective differential evolution for just-in-time door assign- ment and truck scheduling in multi-door cross docking problems[J].Industrial engineering and management sys- tems.2015,14(3):299-311. [12]肖鹏，邹德旋，张强.一种高效动态自适应差分进化算 法[.计算机科学，2019,46(S1):124-132 陆枳屹，硕士研究生，主要研究方 XIAO Peng,ZOU Dexuan,ZHANG Qiang.Efficient dy- 向为智能仓储。 namic self-adaptive differential evolution algorithm[J]. Computer science,2019,46(S1):124-132 [13]YANG Yongkuan,LIU Jianchang,TAN Shubin,et al.A multi-objective differential evolutionary algorithm for
timization of warehouse allocation problem based on improved genetic algorithm[C]//Proceedings of the 13th International Conference on Bio-Inspired Computing: Theories and Applications. Beijing, China, 2018: 252-263. YAN Bo, YAN Chang, LONG Feng, et al. Multi-objective optimization of electronic product goods location assignment in stereoscopic warehouse based on adaptive genetic algorithm[J]. Journal of intelligent manufacturing, 2018, 29(6): 1273–1285. [5] AUGUSTYN L, TONE L. Effectiveness of product storage policy according to classification criteria and warehouse size[J]. FME transactions, 2019, 47(1): 142–150. [6] CHENG Chibin, WENG Yuchi. Warehouse storage assignment by genetic algorithm with multi-objectives[C]//Proceedings of the 2nd International Conference on Intelligent Human Systems Integration. San Diego, USA, 2019: 300-305. [7] LEI Bin, JIANG Zhaoyuan, MU Haibo. Integrated optimization of mixed cargo packing and cargo location assignment in automated storage and retrieval systems[J]. Discrete dynamics in nature and society, 2019, 2019: 9072847. [8] DAS S, MULLICK S S, SUGANTHAN P N. Recent advances in differential evolution-an updated survey[J]. Swarm and evolutionary computation, 2016, 27: 1–30. [9] YU Yadong, MA Haiping, YU Mei, et al. Multipopulation management in evolutionary algorithms and application to complex warehouse scheduling problems[J]. Complexity, 2018, 2018: 4730957. [10] WISITTIPANICH W, HENGMEECHAI P. A multi-objective differential evolution for just-in-time door assignment and truck scheduling in multi-door cross docking problems[J]. Industrial engineering and management systems, 2015, 14(3): 299–311. [11] 肖鹏, 邹德旋, 张强. 一种高效动态自适应差分进化算 法 [J]. 计算机科学, 2019, 46(S1): 124–132. XIAO Peng, ZOU Dexuan, ZHANG Qiang. Efficient dynamic self-adaptive differential evolution algorithm[J]. Computer science, 2019, 46(S1): 124–132. [12] YANG Yongkuan, LIU Jianchang, TAN Shubin, et al. A multi-objective differential evolutionary algorithm for [13] constrained multi-objective optimization problems with low feasible ratio[J]. Applied soft computing, 2019, 80: 42–56. 项前, 周亚云, 吕志军. 资源约束项目的改进差分进化 参数控制及双向调度算法 [J]. 自动化学报, 2020, 46(2): 283–293. XIANG Qian, ZHOU Yayun, LV Zhijun. Improved differential evolution parameter control and bidirectional scheduling algorithm for the resource-constrained project[J]. Acta automatica sinica, 2020, 46(2): 283–293. [14] 吴亮红, 王耀南. 动态差分进化算法及其应用 [M]. 北 京: 科学出版社, 2014: 113. WU Lianghong, WANG Yaonan. Dynamic differential evolution algorithm and application[M]. Beijing: Science Press, 2014: 113. [15] WANG Kun, ZHAO Wei, CUI Junjie, et al. A K-anonymous clustering algorithm based on the analytic hierarchy process[J]. Journal of visual communication and image representation, 2019, 59: 76–83. [16] 作者简介： 项前，副教授，博士，主要研究方 向为数字化制造、智慧物流、计算智能 及应用。主持和参加国家、省部级及 企业科研项目 20 余项，获上海市科学 技术进步奖二等奖 1 项。发表学术论 文 40 余篇。 周亚云，硕士研究生，主要研究方 向为智能仓储。 陆枳屹，硕士研究生，主要研究方 向为智能仓储。 第 5 期 项前，等：响应动态约束条件的多目标货位优化算法研究 ·933·