基于聚类-约束满足算法的钢管入库优化决策模型

第36卷第1期 北京科技大学学报 Vol.36 No.1 2014年1月 Journal of University of Science and Technology Beijing Jan.2014 基于聚类一约束满足算法的钢管入库优化决策模型 董广静2区，施灿涛12)，李铁克12，王柏琳12 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 ☒通信作者，Emai:dongguangjing_2011@126.com 摘要针对钢管入库优化决策问题，建立了问题的约束满足优化模型，并通过对垛高和钢管堆放规则的分析，提出了基于 聚类和约束满足技术的两阶段求解算法.算法在第一阶段采用聚类的方式对待入库的钢管按照多重属性进行分组：在第二阶 段利用约束满足技术对于每组钢管分别指派垛位及其在垛位上的具体位置，并通过约束传播动态缩减问题的搜索空间.最后 将算法与经典的BFD(best fit deceasing)算法进行实验结果对比.实验结果表明，算法能够在保证倒垛次数最小的前提下，有 效减少垛位数并具有良好的垛位利用率，模型及算法可行、有效 关键词钢管：堆垛：聚类算法：约束满足问题：决策 分类号TP29 Optimization model of steel tube location decision based on clustering and constraint satisfaction algorithm DONG Guang jing,SHI Can-tao LI Tie-ke),WANG Bai-lin 1)Dongling School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron Steel Production,Ministry of Education,Beijing 100083,China Corresponding author,E-mail:dongguangjing_2011@126.com ABSTRACT A constraint satisfaction optimization model was presented to deal with the optimization decision problem about the steel tube location.Through the analysis of stack height and the piling rules of steel tubes,a two-stage algorithm was given based on cluste- ring and constraint satisfaction technology.In the first stage,steel tubes to be put into storage are grouped by clustering-based approach according to their multiple attributes.In the second stage,by using constraint satisfaction technology,the specific location of steel tubes in each group is assigned,and the search space of the problem is dynamically shrunk through constraint propagation.Finally, this algorithm was compared with the classical BFD (best fit deceasing)algorithm through experiments.Experimental results demon- strate that,in the premise of minimizing stacking operations,the algorithm can effectively reduce the quantity of stacks and achieve a well-performed utilization rate of stacks.And thus the results verify the feasibility and effectiveness of the model and algorithm. KEY WORDS steel tubes:stacking:clustering algorithms:constraint satisfaction problems:decision making 随着钢铁企业计算机集成制造理论与技术的发 用，对钢管库作业优化问题的研究具有重要的理论 展，炼钢一连铸一热轧一体化生产计划与调度问题得 意义和实用价值. 到了广泛的关注和研究习.钢管库在生产流程中 目前国内外钢管生产企业大都是按照订单组织 起着承前启后的作用：一方面要接收热轧阶段送来 生产的，但是依照钢管的品种和规格为原则进行入 的钢管，另一方面要为客户配送发运产品.因此，钢 库堆垛的，而钢管出入库时存在着大量复杂约束，导 管库在热轧工序和成品发运出库作业的能力协调以 致堆放无序而产生大量倒垛，严重影响了钢管库作 及对整个生产过程的物流平衡方面均具有重要作 业效率，造成库存和倒运成本的大幅上升.钢管库 收稿日期：2012-12-22 基金项目：教有部博士学科点专项科研基金资助项目(201000061100O6):中央高校基本科研业务费专项资金资助项目(FRF-SD-12011B) DOI:10.13374/j.issn1001-053x.2014.01.019;http://jourals.ustb.edu.cn

第 36 卷 第 1 期 2014 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 1 Jan． 2014 基于聚类--约束满足算法的钢管入库优化决策模型 董广静1，2) ，施灿涛1，2) ，李铁克1，2) ，王柏琳1，2) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083  通信作者，E-mail: dongguangjing_2011@ 126． com 摘 要 针对钢管入库优化决策问题，建立了问题的约束满足优化模型，并通过对垛高和钢管堆放规则的分析，提出了基于 聚类和约束满足技术的两阶段求解算法． 算法在第一阶段采用聚类的方式对待入库的钢管按照多重属性进行分组; 在第二阶 段利用约束满足技术对于每组钢管分别指派垛位及其在垛位上的具体位置，并通过约束传播动态缩减问题的搜索空间． 最后 将算法与经典的 BFD ( best fit deceasing) 算法进行实验结果对比． 实验结果表明，算法能够在保证倒垛次数最小的前提下，有 效减少垛位数并具有良好的垛位利用率，模型及算法可行、有效． 关键词 钢管; 堆垛; 聚类算法; 约束满足问题; 决策 分类号 TP29 Optimization model of steel tube location decision based on clustering and constraint satisfaction algorithm DONG Guang-jing1，2)  ，SHI Can-tao 1，2) ，LI Tie-ke 1，2) ，WANG Bai-lin1，2) 1) Dongling School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Ｒesearch Center of MES Technology for Iron ＆ Steel Production，Ministry of Education，Beijing 100083，China  Corresponding author，E-mail: dongguangjing_2011@ 126． com ABSTＲACT A constraint satisfaction optimization model was presented to deal with the optimization decision problem about the steel tube location． Through the analysis of stack height and the piling rules of steel tubes，a two-stage algorithm was given based on cluste￾ring and constraint satisfaction technology． In the first stage，steel tubes to be put into storage are grouped by clustering-based approach according to their multiple attributes． In the second stage，by using constraint satisfaction technology，the specific location of steel tubes in each group is assigned，and the search space of the problem is dynamically shrunk through constraint propagation． Finally， this algorithm was compared with the classical BFD ( best fit deceasing) algorithm through experiments． Experimental results demon￾strate that，in the premise of minimizing stacking operations，the algorithm can effectively reduce the quantity of stacks and achieve a well-performed utilization rate of stacks． And thus the results verify the feasibility and effectiveness of the model and algorithm． KEY WOＲDS steel tubes; stacking; clustering algorithms; constraint satisfaction problems; decision making 收稿日期: 2012--12--22 基金项目: 教育部博士学科点专项科研基金资助项目( 20100006110006) ; 中央高校基本科研业务费专项资金资助项目( FＲF--SD--12--011B) DOI: 10． 13374 /j． issn1001--053x． 2014． 01． 019; http: / /journals． ustb． edu． cn 随着钢铁企业计算机集成制造理论与技术的发 展，炼钢--连铸--热轧一体化生产计划与调度问题得 到了广泛的关注和研究［1--2］． 钢管库在生产流程中 起着承前启后的作用: 一方面要接收热轧阶段送来 的钢管，另一方面要为客户配送发运产品． 因此，钢 管库在热轧工序和成品发运出库作业的能力协调以 及对整个生产过程的物流平衡方面均具有重要作 用，对钢管库作业优化问题的研究具有重要的理论 意义和实用价值． 目前国内外钢管生产企业大都是按照订单组织 生产的，但是依照钢管的品种和规格为原则进行入 库堆垛的，而钢管出入库时存在着大量复杂约束，导 致堆放无序而产生大量倒垛，严重影响了钢管库作 业效率，造成库存和倒运成本的大幅上升． 钢管库

·124 北京科技大学学报 第36卷 的入库优化决策问题就是为即将入库的每一根钢管 实践中为了在合理的时间内找到近优解都采用启发 选择合适的垛位，以便于钢管库的管理，同时减少钢 式方法进行求解，因为传统的搜索技术求解此类问 管库的倒垛作业；其中，存在这样一类入库问题：在 题，会产生“组合爆炸现象”，很难在有效的时间内 钢管库入库管理及钢管的装载运输过程中，为了避 获得最优解.当前对钢铁企业产品入库问题的研究 免滚落和摆放不协调，往往是将半径较大的钢管置 中大部分是针对板坯入库问题的约束满足模型，而 于半径较小的下方，将较长的钢管置于较短钢管的 针对钢管入库决策问题的约束满足模型还尚未见， 下方)，且同一层的半径和长度不能相差太大：同 因此本文针对钢管入库优化决策问题建立了约束满 时为了优化后续的出库作业，要求钢管入库时考虑 足模型在求解算法上，针对入库钢管具有多种规格 交货期的松紧，即具有较紧交货期的钢管应尽可能 的特征，提出一种基于聚类的约束满足算法，并通过 的置于垛位上方，以便于出库.文献4]针对大规模 数据实验验证了算法的有效性 板坯倒垛问题建立了一种基于启发式的阶段动态规 1问题建模 划模型，并设计了对应启发式算法，该算法在实际生 产中可减少10.76%的倒垛量；文献5]提出一种箱 1.1问题描述 子高度可变的三维装箱问题，并设计了针对此类问 一般钢铁企业钢管的存放方式与钢管的半径有 题的一种改进的遗传算法，算法结果明显优于传统 很大关系，半径比较小的多以捆的形式存放，随着钢 装箱算法；文献6]将一种带交货期约束的板坯堆 铁企业的飞速发展，钢铁企业订单多以小批量、多客 垛问题归结为约束满足问题，并设计了一种混合约 户进行生产，钢管的存放方式也发生了一些改变 束满足算法，算法结果优于经典的BFD(best fit de-- 目前有很多钢铁企业钢管的存放多以“A”字型、多 ceasing)算法：文献7]针对板坯入库优化决策问 层多列堆放，这种堆放方式一般适应于半径较大、客 题，采用模糊数学的研究方法将板坯各规格属性模 户交货期松紧度相近的钢管产品，所以对于钢管的 糊化，设计了一种混合离散粒子群算法，相比传统的 入库堆放问题即垛位优化问题的研究对钢管库的管 遗传算法减少了16%的倒垛量；文献8]针对钢铁 理起着至关重要的作用. 企业供应链上的线圈作业调度优化问题设计了一种 对于钢管入库优化决策问题，由于入库钢管的 基于启发式规则的算法，并在实际生产中有了很好 订单交期已经确定，因此钢管在堆垛时主要参照订 的应用；文献⑨]针对库区吊机能力实际限制下的 单交货期执行，将钢管交货期靠前的尽可能摆在上 板坯倒垛问题建立了非线性规划模型，并对问题特 方，以减少出库时的倒垛次数.钢管库中通常存在 征进行分析，针对轧制项目间是否存在共同可选板 若干垛位，为节省空间需要多层多列叠放，因而为了 坯的两种情况，将模型转化为线性整数规划模型，利 保证垛位的稳定性，在进行钢管堆垛时考虑以下几 用问题的性质降低了模型的求解复杂性.以上研究 方面要求：(1)上层钢管的长度与下层相邻钢管的 成果对本文的研究具有一定的参考价值. 长度差的绝对值不超过某一给定上限值；(2)上层 以往研究中多以板坯特性的货物作为研究对 钢管的半径与下层相邻钢管的半径差的绝对值不超 象，一般是多层堆放，一层只允许堆放一个货物，在 过某一给定上限值：(3)同层任意两根钢管的半径 堆放时主要综合考虑货物的厚度、宽度、重量和交货 差值的绝对值不能超过某一给定上限值：(4)同层 期等因素，而对具有钢管特性的货物的研究较少，仅 任意两根钢管的长度差值的绝对值不能超过某一给 有几篇研究的是钢卷的入库优化问题，也是类似于 定上限值：(5)受地面承重能力、安全原因和起重设 板坯的存放方式.对于钢管多层多列的堆放方式研 备所能达到的高度所限，每个垛位上钢管的总高度 究还尚未见.本文以钢管成品库优化管理中的入库 不超过某一给定上限值 优化决策问题作为研究对象，因钢管入库时存在交 根据钢管成批生产且同批钢管钢种相同或相近 货期的松紧约束，故将其归结为带顺序约束的三维 的特征，本文假设每一批的待入库钢管具有相同的 ASBP(a-shape bin packing)问题，并映射为约束满 钢种，则钢管入库优化决策问题即是根据待入库的 足问题o(constraint satisfaction problem,CSP).三 钢管半径、长度等属性的不同，在不违背垛高限制的 维ASBP问题是一个具有复杂约束条件的组合优化 情况下为其指派垛位，使得在满足出库零倒垛的前 问题，具有典型的NP难特性，它在实际中有许多约 提下，占用的垛位数最少 束条件需要考虑，如空间约束、载重约束、货物摆向 1.2符号定义 约束、稳定性约束和货物装卸顺序约束四，一般在 为了便于建立问题的模型，定义以下符号

北 京 科 技 大 学 学 报 第 36 卷 的入库优化决策问题就是为即将入库的每一根钢管 选择合适的垛位，以便于钢管库的管理，同时减少钢 管库的倒垛作业; 其中，存在这样一类入库问题: 在 钢管库入库管理及钢管的装载运输过程中，为了避 免滚落和摆放不协调，往往是将半径较大的钢管置 于半径较小的下方，将较长的钢管置于较短钢管的 下方［3］，且同一层的半径和长度不能相差太大; 同 时为了优化后续的出库作业，要求钢管入库时考虑 交货期的松紧，即具有较紧交货期的钢管应尽可能 的置于垛位上方，以便于出库． 文献［4］针对大规模 板坯倒垛问题建立了一种基于启发式的阶段动态规 划模型，并设计了对应启发式算法，该算法在实际生 产中可减少 10. 76% 的倒垛量; 文献［5］提出一种箱 子高度可变的三维装箱问题，并设计了针对此类问 题的一种改进的遗传算法，算法结果明显优于传统 装箱算法; 文献［6］将一种带交货期约束的板坯堆 垛问题归结为约束满足问题，并设计了一种混合约 束满足算法，算法结果优于经典的 BFD ( best fit de￾ceasing) 算法; 文献［7］针对板坯入库优化决策问 题，采用模糊数学的研究方法将板坯各规格属性模 糊化，设计了一种混合离散粒子群算法，相比传统的 遗传算法减少了 16% 的倒垛量; 文献［8］针对钢铁 企业供应链上的线圈作业调度优化问题设计了一种 基于启发式规则的算法，并在实际生产中有了很好 的应用; 文献［9］针对库区吊机能力实际限制下的 板坯倒垛问题建立了非线性规划模型，并对问题特 征进行分析，针对轧制项目间是否存在共同可选板 坯的两种情况，将模型转化为线性整数规划模型，利 用问题的性质降低了模型的求解复杂性． 以上研究 成果对本文的研究具有一定的参考价值． 以往研究中多以板坯特性的货物作为研究对 象，一般是多层堆放，一层只允许堆放一个货物，在 堆放时主要综合考虑货物的厚度、宽度、重量和交货 期等因素，而对具有钢管特性的货物的研究较少，仅 有几篇研究的是钢卷的入库优化问题，也是类似于 板坯的存放方式． 对于钢管多层多列的堆放方式研 究还尚未见． 本文以钢管成品库优化管理中的入库 优化决策问题作为研究对象，因钢管入库时存在交 货期的松紧约束，故将其归结为带顺序约束的三维 ASBP ( a-shape bin packing) 问题，并映射为约束满 足问题［10］( constraint satisfaction problem，CSP) ． 三 维 ASBP 问题是一个具有复杂约束条件的组合优化 问题，具有典型的 NP 难特性，它在实际中有许多约 束条件需要考虑，如空间约束、载重约束、货物摆向 约束、稳定性约束和货物装卸顺序约束［11］，一般在 实践中为了在合理的时间内找到近优解都采用启发 式方法进行求解，因为传统的搜索技术求解此类问 题，会产生“组合爆炸现象”，很难在有效的时间内 获得最优解． 当前对钢铁企业产品入库问题的研究 中大部分是针对板坯入库问题的约束满足模型，而 针对钢管入库决策问题的约束满足模型还尚未见， 因此本文针对钢管入库优化决策问题建立了约束满 足模型; 在求解算法上，针对入库钢管具有多种规格 的特征，提出一种基于聚类的约束满足算法，并通过 数据实验验证了算法的有效性． 1 问题建模 1. 1 问题描述 一般钢铁企业钢管的存放方式与钢管的半径有 很大关系，半径比较小的多以捆的形式存放，随着钢 铁企业的飞速发展，钢铁企业订单多以小批量、多客 户进行生产，钢管的存放方式也发生了一些改变． 目前有很多钢铁企业钢管的存放多以“A”字型、多 层多列堆放，这种堆放方式一般适应于半径较大、客 户交货期松紧度相近的钢管产品，所以对于钢管的 入库堆放问题即垛位优化问题的研究对钢管库的管 理起着至关重要的作用． 对于钢管入库优化决策问题，由于入库钢管的 订单交期已经确定，因此钢管在堆垛时主要参照订 单交货期执行，将钢管交货期靠前的尽可能摆在上 方，以减少出库时的倒垛次数． 钢管库中通常存在 若干垛位，为节省空间需要多层多列叠放，因而为了 保证垛位的稳定性，在进行钢管堆垛时考虑以下几 方面要求: ( 1) 上层钢管的长度与下层相邻钢管的 长度差的绝对值不超过某一给定上限值; ( 2) 上层 钢管的半径与下层相邻钢管的半径差的绝对值不超 过某一给定上限值; ( 3) 同层任意两根钢管的半径 差值的绝对值不能超过某一给定上限值; ( 4) 同层 任意两根钢管的长度差值的绝对值不能超过某一给 定上限值; ( 5) 受地面承重能力、安全原因和起重设 备所能达到的高度所限，每个垛位上钢管的总高度 不超过某一给定上限值． 根据钢管成批生产且同批钢管钢种相同或相近 的特征，本文假设每一批的待入库钢管具有相同的 钢种，则钢管入库优化决策问题即是根据待入库的 钢管半径、长度等属性的不同，在不违背垛高限制的 情况下为其指派垛位，使得在满足出库零倒垛的前 提下，占用的垛位数最少． 1. 2 符号定义 为了便于建立问题的模型，定义以下符号． ·124·

第1期 董广静等：基于聚类一约束满足算法的钢管入库优化决策模型 ·125· (1)集合和索引. Cn+r为+ i:钢管编号； :垛位编号： :钢管集合，1={1,2，…，i,…,n}: hi: (2) J:垛位集合，J={1,2,…j,…,m}. C2:h≤H,jeJ: (3) (2)参数. Cmax{lr-T,lr1-r}≤D, L(2):初始垛位中空垛位集合； VaeZi (4) H:垛位允许的最大高度，只考虑初始状态为空 C4:lr,-r,≤a,Ha,a2∈Zt; (5) 垛的情况： Csimax D:任一钢管与上层相邻两钢管的半径差额上 Hz1∈Zt; (6) 限值： α：相邻两层半径的差额上限值： C6:l-l≤B,z∈Z: (7) L:任一钢管与上层相邻两钢管的长度差额上 C,:mio04n}≥0ua,a1∈乙：(8） (9) 限值； Cslo%-0≤Y,Ha1eZ: B:同层长度的差额上限值： Cim-ma YjeJ: (10) y:同层交货期的差额上限值； T:钢管i的半径： Comt+)+1≤m,j∈J: (11) l:钢管i的长度； C:0Q0{x}=0: (12) 0:钢管i的交货期. Cn:0)=1; (13) (3)变量. C13:m≥0，mt≥0，x法≥0. (14) h,:垛位j的高度： 目标函数式(1)表示最小化钢管占用垛位数； G:垛位j上的层数： 式(2)表示层数与垛位高度及各层钢管半径的直接 Z:垛位j上第k层的位置编号集合； 关系；式(3)表示垛位的高度不能超过一定限制；式 m:垛位j上的钢管总数： (4)表示第i+1层钢管与第i层相邻两钢管的半径 m:垛位j上第k层上的钢管总数： 差值不超过某一给定值：式(5)表示同一层钢管的 x:为第j个垛位上第k层自左起第z个钢管 半径差值不超过某一给定值：式(6)表示第i+1层 的编号，x1表示垛位j上最底层最左边的钢管编号， 钢管与第i层相邻两钢管的长度差值不超过某一给 随着同一层钢管逐次自左向右堆放，z值逐渐增大： 定值，主要是为了垛位稳定协调作的限制；式(7)表 随钢管的逐层堆放，k值逐渐增大 示同一层钢管的长度值不超过某一给定值：式(8) 1.3约束满足模型 表示第i+1层钢管不大于第i层相邻两钢管的交货 上述钢管入库优化决策问题实质上是一类多层 期，主要考虑到出库时的优化：式(9)表示同层钢管 多列带顺序的三维装箱问题，可以将此问题映射成 的交货期不能超过某一给定值，主要是为了保证出 约束满足问题.约束满足问题(constraint satisfaction 库的协调：式(10)表示垛位j上钢管总数与各层上 problem,CSP)是人工智能的一个重要研究领域，在 钢管的数量之间的关系；式(11)表示相邻两层之间钢 工业工程中的很多实际问题都有着广泛的应用，比 管的数量关系：式(12)要求每根钢管必须只能匹配一 如批量计划☒、作业调度圆、资源分配和产品配 个垛位：式(13)和式(14)定义了变量的取值范围. 置，其建模方法能够以更加接近于现实世界的方式 2钢管入库垛位优化决策问题的定性分析 描述问题及其复杂的约束的.对于钢管入库堆垛 问题，可用一个四元组<V,D,C,F>所表示的约束 2.1垛高的计算策略 满足问题来描述.其中，V={V,V2,,Vn}为变量 一般情况下，在钢管堆放时会出现如下堆放情 集；D={D1,D2,,Dn}为值域集，D:为V:的值域： 况，如下图1. C={C,C2,…,C}为约束关系集；F为优化目标数 对于图1的垛高计算公式如下：设11和r2分别 集.模型如下 为当前层半径及其上一层两相邻钢管的平均半径 min m; (1) 如图1，由三圆圆心组成的等腰三角形的高为h,= Subject to: √(m+r2)2-=√+2r1T2:截止到现在层的垛

第 1 期 董广静等: 基于聚类--约束满足算法的钢管入库优化决策模型 ( 1) 集合和索引． i: 钢管编号; j: 垛位编号; I: 钢管集合，I = { 1，2，…，i，…，n} ; J: 垛位集合，J = { 1，2，…，j，…，m} ． ( 2) 参数． L( Ω) : 初始垛位中空垛位集合; H: 垛位允许的最大高度，只考虑初始状态为空 垛的情况; D: 任一钢管与上层相邻两钢管的半径差额上 限值; α: 相邻两层半径的差额上限值; L: 任一钢管与上层相邻两钢管的长度差额上 限值; β: 同层长度的差额上限值; γ: 同层交货期的差额上限值; ri : 钢管 i 的半径; li : 钢管 i 的长度; oi : 钢管 i 的交货期． ( 3) 变量． hj : 垛位 j 的高度; cj : 垛位 j 上的层数; Zjk : 垛位 j 上第 k 层的位置编号集合; mj : 垛位 j 上的钢管总数; mjk : 垛位 j 上第 k 层上的钢管总数; xjkz: 为第 j 个垛位上第 k 层自左起第 z 个钢管 的编号，xj11表示垛位 j 上最底层最左边的钢管编号， 随着同一层钢管逐次自左向右堆放，z 值逐渐增大; 随钢管的逐层堆放，k 值逐渐增大． 1. 3 约束满足模型 上述钢管入库优化决策问题实质上是一类多层 多列带顺序的三维装箱问题，可以将此问题映射成 约束满足问题． 约束满足问题( constraint satisfaction problem，CSP) 是人工智能的一个重要研究领域，在 工业工程中的很多实际问题都有着广泛的应用，比 如批量计划［12］、作业调度［13］、资源分配和产品配 置，其建模方法能够以更加接近于现实世界的方式 描述问题及其复杂的约束［14］． 对于钢管入库堆垛 问题，可用一个四元组 ＜ V，D，C，F ＞ 所表示的约束 满足问题来描述． 其中，V = { V1，V2，…，Vn } 为变量 集; D = { D1，D2，…，Dn } 为值域集，Di 为 Vi 的值域; C = { C1，C2，…，Cn } 为约束关系集; F 为优化目标数 集． 模型如下． min m; ( 1) Subject to: C1 : rxj1 + rxjcj ( + 2∑ cj k =1 rxjk － cj rxj1 － rxjc ) ( j 2∑ cj k =2 rxjk + cj rxj1 － rx 槡 jc )j = hj ; ( 2) C2 : hj≤H，j∈J; ( 3) C3 : max{ |rxjkz1 － rxj( k + 1) z1 |，|rxjk( z1 + 1) － rxj( k + 1) z1 |} ≤D， z1∈Zjk ; ( 4) C4 : |rjkz1 － rjkz2 |≤α，z1，z2∈Zjk ; ( 5) C5 : max{ | lxjkz1 － lxj( k + 1) z1 |，| lxjk( z1 + 1) － lxj( k + 1) z1 |} ≤L， z1∈Zjk ; ( 6) C6 : | lxjkz1 － lxjkz2 |≤β，z1，z2∈Zjk ; ( 7) C7 : min{ oxjkz1 ，oxjk( z1 + 1) } ≥oxj( k + 1) z1 ，z1∈Zjk ; ( 8) C8 : | oxjkz1 － oxjkz2 |≤γ，z1，z2∈Z; ( 9) C9 : mj = ∑ cj k = 1 mjk，j∈J; ( 10) C10 : mj( k + 1) + 1≤mjk，j∈J; ( 11) C11 : ∩ j ∩k ∩z { xjkz} = ; ( 12) C12 : ∪ j ∪k ∪z { xjkz} = I; ( 13) C13 : mj≥0，mjk≥0，xjkz≥0． ( 14) 目标函数式( 1) 表示最小化钢管占用垛位数; 式( 2) 表示层数与垛位高度及各层钢管半径的直接 关系; 式( 3) 表示垛位的高度不能超过一定限制; 式 ( 4) 表示第 i + 1 层钢管与第 i 层相邻两钢管的半径 差值不超过某一给定值; 式( 5) 表示同一层钢管的 半径差值不超过某一给定值; 式( 6) 表示第 i + 1 层 钢管与第 i 层相邻两钢管的长度差值不超过某一给 定值，主要是为了垛位稳定协调作的限制; 式( 7) 表 示同一层钢管的长度值不超过某一给定值; 式( 8) 表示第 i + 1 层钢管不大于第 i 层相邻两钢管的交货 期，主要考虑到出库时的优化; 式( 9) 表示同层钢管 的交货期不能超过某一给定值，主要是为了保证出 库的协调; 式( 10) 表示垛位 j 上钢管总数与各层上 钢管的数量之间的关系; 式( 11) 表示相邻两层之间钢 管的数量关系; 式( 12) 要求每根钢管必须只能匹配一 个垛位; 式( 13) 和式( 14) 定义了变量的取值范围． 2 钢管入库垛位优化决策问题的定性分析 2. 1 垛高的计算策略 一般情况下，在钢管堆放时会出现如下堆放情 况，如下图 1． 对于图 1 的垛高计算公式如下: 设 r1 和 r2 分别 为当前层半径及其上一层两相邻钢管的平均半径． 如图 1，由三圆圆心组成的等腰三角形的高为 h1 = ( r1 + r2 ) 2 槡 － r 2 2 = r 2 1 + 2r 槡 1 ·r2 ． 截止到现在层的垛 ·125·

·126· 北京科技大学学报 第36卷 类的约束满足算法(constraint satisfaction algorithm based on clustering,CSC).算法由两阶段构成：第一 阶段将入库钢管按照半径、交货期和长度三个属性 进行加权聚类，并将各组按照平均半径非增排序，组 作前垛位高度私 内部按照交货期非增排序：第二阶段对于形成的每 一组采用约束满足算法为各类中钢管指派垛位.算 图1垛高分析示意图 Fig.1 Schematic diagram of analysis for stack high 法的主要流程如图2所示 高为h2=h+△h=h+r1-r2+h,:为了保证垛高增 算法开始 量△h>0,需要满足的半径约束为r1>r2/4. 初始化 显然，这种计算方法得到的堆垛高度必定不小 于实际垛高，换言之，只要此垛高不超过垛高的上限 聚类算法 要求，那么实际的垛高一定不会超过设定的上限值 初始约束 2.2钢管堆放规则 搜常算法 亨 约束传播 钢管的堆放对长度、半径和交货期等属性具有 局部解 严格要求，比一般的板坯堆垛问题要复杂。本文在 新约束 新约束 1.1节给出的五条堆垛要求的基础上定义了以下三 (传插) (决策值) 种规则，以指导钢管的堆放： 最终行效解 规则1]若垛位为空垛，则从垛位的第一层 (即最底层)自左向右依次按交货期非增堆放，交货 图2基于聚类的约束满足算法流程图 Fig.2 Flow chart of the clustering-based CSC algorithm 期相同的，则按长度非增堆放； 规则2]堆放钢管时按照“A”字型堆放，即 为了便于问题的进一步讨论，给出下列定义 第i层的钢管数必须严格大于第i+1层的钢管数， 定义1（适应值）设和”为垛位j上第k层 堆放高度一般不能超过最大高度H,且只有堆满上 两个相邻钢管的编号，i为该垛位上第k+1层与i、 一层才能继续堆放下一层； ”相邻的钢管编号，则定义钢管i与i'、”之间的适应 规则3]同层任意两个钢管的交货期的差值 值Pie为： 不大于给定值，且相邻两层钢管的交货期需满足第 t01+2 i+1层任一钢管的交货期不大于第i层相邻两钢管 √0(0+0-20，)2+w2(0,+l2-2,)2+01+2 的交货期的要求. (15) 其中，01和U2分别为钢管的交货期和长度的权重. 3求解算法 定义2（可排位置）若垛位j的第k个位置为 钢管入库优化决策问题实质上是对经典BP 空，且钢管放置在该位置不违背长度和交货期的 (bin packing)问题在三维上的一种扩展，通常考虑 约束，则称位置(，k)为钢管i的可排位置 将经典的BP启发式算法修改后直接推广使用.就 定义3（能排位置）在不考虑长度和交货期约 钢管入库垛位优化决策问题而言，考虑到降低同垛 束的情况下，若将钢管i堆放在垛位j的第k个位置 内不同层数上钢管之间半径、长度等属性的堆放要 上不会违背其他约束，则称位置(，k)为钢管i的能 求，降序最佳适应算法(best fit decreasing,BFD)具 排位置. 有相对良好的效果.然而考虑交货期的入库垛位优 3.1基于K-Means聚类算法的分组策略 化决策问题更为复杂，约束众多且彼此关联，因而不 将每个钢管的各个属性看作g维向量，记作 能直接采用.约束满足技术—作为求解大规模组 x:=(x1i,x2x,…,x）,（i=1,2,…,n),x表示钢管编 合优化问题的一种有效智能方法，能够针对约束满 号为i的第k个属性量.本文采用欧式加权距离来 足模型，在已知变量和约束的前提下，通过寻求变量 定义钢管之间的距离。则对多属性多约束的钢管进 的合理取值，以满足问题的所有约束，同时优化某个 行分组的K-Means聚类算法(K-Means clustering al-- 性能属性. gorithm of steel tube,KCAST)的具体步骤如下. 针对钢管的多维属性特征，本文设计了基于聚 Step1设钢管集为Q=(x1,x2,…,xn-1xn）

北 京 科 技 大 学 学 报 第 36 卷 图 1 垛高分析示意图 Fig． 1 Schematic diagram of analysis for stack high 高为 h2 = h + Δh = h + r1 － r2 + h1 ; 为了保证垛高增 量 Δh ＞ 0，需要满足的半径约束为 r1 ＞ r2 /4． 显然，这种计算方法得到的堆垛高度必定不小 于实际垛高，换言之，只要此垛高不超过垛高的上限 要求，那么实际的垛高一定不会超过设定的上限值． 2. 2 钢管堆放规则 钢管的堆放对长度、半径和交货期等属性具有 严格要求，比一般的板坯堆垛问题要复杂． 本文在 1. 1 节给出的五条堆垛要求的基础上定义了以下三 种规则，以指导钢管的堆放: ［规则 1］ 若垛位为空垛，则从垛位的第一层 ( 即最底层) 自左向右依次按交货期非增堆放，交货 期相同的，则按长度非增堆放; ［规则 2］ 堆放钢管时按照“A”字型堆放，即 第 i 层的钢管数必须严格大于第 i + 1 层的钢管数， 堆放高度一般不能超过最大高度 H，且只有堆满上 一层才能继续堆放下一层; ［规则 3］ 同层任意两个钢管的交货期的差值 不大于给定值，且相邻两层钢管的交货期需满足第 i + 1 层任一钢管的交货期不大于第 i 层相邻两钢管 的交货期的要求． 3 求解算法 钢管入库优化决策问题实质上是对经典 BP ( bin packing) 问题在三维上的一种扩展，通常考虑 将经典的 BP 启发式算法修改后直接推广使用． 就 钢管入库垛位优化决策问题而言，考虑到降低同垛 内不同层数上钢管之间半径、长度等属性的堆放要 求，降序最佳适应算法( best fit decreasing，BFD) 具 有相对良好的效果． 然而考虑交货期的入库垛位优 化决策问题更为复杂，约束众多且彼此关联，因而不 能直接采用． 约束满足技术———作为求解大规模组 合优化问题的一种有效智能方法，能够针对约束满 足模型，在已知变量和约束的前提下，通过寻求变量 的合理取值，以满足问题的所有约束，同时优化某个 性能属性． 针对钢管的多维属性特征，本文设计了基于聚 类的约束满足算法( constraint satisfaction algorithm based on clustering，CSC) ． 算法由两阶段构成: 第一 阶段将入库钢管按照半径、交货期和长度三个属性 进行加权聚类，并将各组按照平均半径非增排序，组 内部按照交货期非增排序; 第二阶段对于形成的每 一组采用约束满足算法为各类中钢管指派垛位． 算 法的主要流程如图 2 所示． 图 2 基于聚类的约束满足算法流程图 Fig． 2 Flow chart of the clustering-based CSC algorithm 为了便于问题的进一步讨论，给出下列定义． 定义 1( 适应值) 设 i'和 i″为垛位 j 上第 k 层 两个相邻钢管的编号，i 为该垛位上第 k + 1 层与 i'、 i″相邻的钢管编号，则定义钢管 i 与 i'、i″之间的适应 值 Pii'i″为: Pii'i″ = w1 + w2 w1 ( oi' + oi″ － 2oi ) 2 + w2 ( li' + li″ － 2li 槡 ) 2 + w1 + w2 ． ( 15) 其中，w1 和 w2 分别为钢管的交货期和长度的权重． 定义 2( 可排位置) 若垛位 j 的第 k 个位置为 空，且钢管 i 放置在该位置不违背长度和交货期的 约束，则称位置( j，k) 为钢管 i 的可排位置． 定义 3( 能排位置) 在不考虑长度和交货期约 束的情况下，若将钢管 i 堆放在垛位 j 的第 k 个位置 上不会违背其他约束，则称位置( j，k) 为钢管 i 的能 排位置． 3. 1 基于 K-Means 聚类算法的分组策略 将每个钢管的各个属性看作 q 维向量，记作 xi = ( x1i，x2i，…，xqi ) ，( i = 1，2，…，n) ，xki表示钢管编 号为 i 的第 k 个属性量． 本文采用欧式加权距离来 定义钢管之间的距离． 则对多属性多约束的钢管进 行分组的 K-Means 聚类算法( K-Means clustering al￾gorithm of steel tube，KCAST) 的具体步骤如下． Step 1 设钢管集为 Q = ( x1，x2，…，xn － 1，xn ) ， ·126·

第1期 董广静等：基于聚类一约束满足算法的钢管入库优化决策模型 ·127· x:=(x,x2,,x）,标准半径的种类数记为p,其 间实现减少计算量的目的.通过对入库堆垛问题使 中，与标准半径相差（给定值）可视为标准半径，因 用约束传播技术，能够约减部分变量（即钢管）的值 此将聚类组数设为p; 域，去掉一些无效的垛位取值，具体方法为：在完成 Step2随机选取每个类里的一个粒子作为初 对当前钢管i垛位匹配的同时，通过约束C3~C4可 始聚类中心c1,c2,…,Cp: 以过滤掉变量中有上下两层相邻钢管半径和同层半 Step3根据下式将钢管集Q中的对象x:(i= 径都有冲突的变量：通过约束C5~C。可以过滤掉变 1,2,…,n)依次按欧式平均距离分配给距离最近的 量中有上下两层相邻长度和同层长度都有冲突的变 中心c=1,2,…,p), 量；通过约束C,~Cg可以过滤掉变量中有上下两层 相邻交货期和同层交货期都有冲突的变量：通过约 lx:-c‖=min ,(1≤≤p), 束C,可以减少值域的搜索范围，加快搜索速度. (16) 通过上述操作，可以有效地降低问题的规模，降 式中，q为粒子的属性组成的维数，4为各属性的 低搜索空间，提高求解效率，从而简化了问题使其易 权值； 于求解. Step 4 按下式计算p个聚类的中心c)=1, 3.3算法步骤 2,…,p）, CSC算法的具体步骤如下. Step1(初始化) S=∑j=1,2,…p (17) 初始化入库钢管编号i,半径r、长度l:和订单 其中，N为第j个聚类S中所包含的粒子个数； 交货期·：及垛位信息及对应垛位上钢管信息 Step5如果各个聚类中心c,(=1,2,…,p)不 Step2(入库钢管的聚类分组) 再变化，转至Step6,否则返回Step3; 执行KCAST算法，将一批入库的钢管按照半 Step6分别对p个聚类结果中的钢管按照钢 径、长度和交货期的一定权重聚类，并在各类内按交 管的交货期非增，交货期相同的按长度非增排序 货期非增排序，类与类之间按平均半径非增排序 算法结束] Step3(变量选择) 3.2约束满足算法 遍历每个类里面的钢管，选定订单的交货期对 (1)变量选择.首先选择安排起来比较困难的 变量进行降序排序.令min(topLength())、min(to- 变量，即半径较大的钢管i,以尽可能避免形成不可 pOrder())和totalHeigtht()分别表示垛位j中能堆 行的部分解.结合BP的特点，对求解装箱问题的降 放钢管的位置上同层相邻钢管的最小长度、订单的 序最佳适应规则进行推广，得到以下两种变量排序 最小交货期以及该垛位钢管的水平高度 规则： Step4(值选择) 规则4]变量按交货期非增顺序排序； (a)依次为变量赋值，即对当前变量值域进行 规则5]变量按长度非增顺序排序，若存在 值排序，选取值域中的第一个垛位作为当前变量的 长度相同的多个变量，则按交货期降序排列. 当前取值： (2)值选择.首先依据所选变量的交货期约束 (b)设当前变量为i,当前取值为j,则通过搜索 对值域（可排位置）进行约简，即去除不满足当前钢 钢管所能堆放的位置确定是否将j赋值给变量： 管交货期约束的垛位然后采用值选择规则从值 若可堆放位置同层己有其他钢管，且满足！，≤ 域中选择垛位指派给当前钢管.为了使堆垛问题的 min(topLength())、o:≤min(topOrder()),则将垛 目标值尽可能最小化，采用BFD作为值选择规则： 位j赋值给钢管i,同时更新该垛位的min(topLength 规则6]值域按照垛位的剩余能排位置数的 ())、min(topOrder(i))取值； 非增排序，若能排位置数相同，则选择可排层数较高 若可堆放位置的同层没有其他钢管，且满足 的垛位； l,≤min(topLength(i)）、o,≤min(topOrder())和to- 规则7]若所有非空垛位都不能放置该钢管 talHeight()+V3r,≤H,则将垛位j赋值给钢管i,同 时，则为其申请一个新垛位 时更新该垛位的min(topLength(j))、min(topOrder 由于变量值域的大小在搜索过程中是动态变化 (i))和totalHeight()取值： 的，所以上述变量选择和值选择的顺序也是动态的 若取值j均不满足上述情况，则从值域中选取 (3)约束传播.约束传播技术通过缩小搜索空 下一个取值作为变量i的当前取值，重复Step4

第 1 期 董广静等: 基于聚类--约束满足算法的钢管入库优化决策模型 xi = ( x1i，x2i，…，xpi ) ，标准半径的种类数记为 p，其 中，与标准半径相差 θ( 给定值) 可视为标准半径，因 此将聚类组数设为 p; Step 2 随机选取每个类里的一个粒子作为初 始聚类中心 c1，c2，…，cp ; Step 3 根据下式将钢管集 Q 中的对象 xi ( i = 1，2，…，n) 依次按欧式平均距离分配给距离最近的 中心 cj ( j = 1，2，…，p) ， ‖xi － cj‖ = m ( in ∑ q k =1 ωk ( xki － ckj ) 槡 ) 2 ，( 1≤j≤p) ， ( 16) 式中，q 为粒子的属性组成的维数，ωk 为各属性的 权值; Step 4 按下式计算 p 个聚类的中心 cj ( j = 1， 2，…，p) ， cj = 1 Nj ∑i∈Sj xi，j = 1，2，…，p， ( 17) 其中，Nj 为第 j 个聚类 Sj 中所包含的粒子个数; Step 5 如果各个聚类中心 cj ( j = 1，2，…，p) 不 再变化，转至 Step 6，否则返回 Step 3; Step 6 分别对 p 个聚类结果中的钢管按照钢 管的交货期非增，交货期相同的按长度非增排序． ［算法结束］ 3. 2 约束满足算法 ( 1) 变量选择． 首先选择安排起来比较困难的 变量，即半径较大的钢管 i，以尽可能避免形成不可 行的部分解． 结合 BP 的特点，对求解装箱问题的降 序最佳适应规则进行推广，得到以下两种变量排序 规则: ［规则 4］ 变量按交货期非增顺序排序; ［规则 5］ 变量按长度非增顺序排序，若存在 长度相同的多个变量，则按交货期降序排列． ( 2) 值选择． 首先依据所选变量的交货期约束 对值域( 可排位置) 进行约简，即去除不满足当前钢 管交货期约束的垛位 j． 然后采用值选择规则从值 域中选择垛位指派给当前钢管． 为了使堆垛问题的 目标值尽可能最小化，采用 BFD 作为值选择规则: ［规则 6］ 值域按照垛位的剩余能排位置数的 非增排序，若能排位置数相同，则选择可排层数较高 的垛位; ［规则 7］ 若所有非空垛位都不能放置该钢管 时，则为其申请一个新垛位． 由于变量值域的大小在搜索过程中是动态变化 的，所以上述变量选择和值选择的顺序也是动态的． ( 3) 约束传播． 约束传播技术通过缩小搜索空 间实现减少计算量的目的． 通过对入库堆垛问题使 用约束传播技术，能够约减部分变量( 即钢管) 的值 域，去掉一些无效的垛位取值，具体方法为: 在完成 对当前钢管 i 垛位匹配的同时，通过约束 C3 ～ C4 可 以过滤掉变量中有上下两层相邻钢管半径和同层半 径都有冲突的变量; 通过约束 C5 ～ C6 可以过滤掉变 量中有上下两层相邻长度和同层长度都有冲突的变 量; 通过约束 C7 ～ C8 可以过滤掉变量中有上下两层 相邻交货期和同层交货期都有冲突的变量; 通过约 束 C2 可以减少值域的搜索范围，加快搜索速度． 通过上述操作，可以有效地降低问题的规模，降 低搜索空间，提高求解效率，从而简化了问题使其易 于求解． 3. 3 算法步骤 CSC 算法的具体步骤如下． Step 1 ( 初始化) 初始化入库钢管编号 i，半径 ri、长度 li 和订单 交货期 oi 及垛位信息及对应垛位上钢管信息． Step 2 ( 入库钢管的聚类分组) 执行 KCAST 算法，将一批入库的钢管按照半 径、长度和交货期的一定权重聚类，并在各类内按交 货期非增排序，类与类之间按平均半径非增排序． Step 3 ( 变量选择) 遍历每个类里面的钢管，选定订单的交货期对 变量进行降序排序． 令 min( topLength( j) ) 、min( to￾pOrder( j) ) 和 totalHeigtht( j) 分别表示垛位 j 中能堆 放钢管的位置上同层相邻钢管的最小长度、订单的 最小交货期以及该垛位钢管的水平高度． Step 4 ( 值选择) ( a) 依次为变量赋值，即对当前变量值域进行 值排序，选取值域中的第一个垛位作为当前变量的 当前取值; ( b) 设当前变量为 i，当前取值为 j，则通过搜索 钢管所能堆放的位置确定是否将 j 赋值给变量 i; 若可堆放位置同层已有其他钢管，且满足 li≤ min( topLength( j) ) 、oi≤min( topOrder( j) ) ，则将垛 位 j 赋值给钢管 i，同时更新该垛位的 min( topLength ( j) ) 、min( topOrder( j) ) 取值; 若可堆放位置的同层没有其他钢管，且满足 li≤min( topLength( j) ) 、oi≤min( topOrder( j) ) 和 to￾talHeight( j) + 槡3ri≤H，则将垛位 j 赋值给钢管 i，同 时更新该垛位的 min( topLength( j) ) 、min( topOrder ( j) ) 和 totalHeight( j) 取值; 若取值 j 均不满足上述情况，则从值域中选取 下一个取值作为变量 i 的 当 前 取 值，重 复 Step 4 ·127·