钢铁企业全流程物流优化问题的建模及分支——定价算法

研究了钢铁企业的全流程物流优化问题, 该问题在确保全流程各个工序机组产能和库存能力限制以及满足客户需求的前提下, 决策炼钢、连铸、热轧及冷轧工序间的物料流向和流量, 最小化物流成本、产能损失及库存费用. 为该问题建立了混合整数规划(Mixed integer programming, MIP)模型. 在问题求解中, 首先对MIP模型进行了Dantzig-Wolfe分解, 得到一个结构相对简单但列变量数目非常多的主问题和四个描述列向量空间的子问题. 然后, 从一个包含部分列变量的限制主问题出发, 通过子问题和主问题之间的迭代来获取主问题线性松弛的最优解. 最后, 将列生成同分支—定界相结合, 即分支—定价算法, 以获取原问题的整数最优解. 对某钢铁企业的实际生产数据扩展的随机算例进行仿真实验, 结果显示所提出的算法能够在合理计算时间内获得最优解或次优解.

Modeling and Branch-and-price Algorithm for Logistics Optimization Problem of Plant-wide Production Processes in Steel Industry

In this paper, we investigate the logistics optimization problem of plant-wide production processes in steel industry, which is to decide the amount of material flow between steelmaking, continuous-casting, hot rolling and cold rolling processes such that the constraints on unit's capacity, the storage capacity and the customer's demands are satisfied and the logistics cost, penalty of production capacity loss and stock cost are minimized. A mixed integer programming (MIP) model is formulated, then a column generation based optimization solution method is developed according to the model's characters. In the solution method, we first use the Dantzig-Wolfe decomposition method to split the MIP model into a master problem which has a simple structure but contains numerous columns and 4 types of subproblems which describe the vector space of the columns. Then, the column generation algorithm starts from a restricted version of master problem which contains only a subset of columns, and executes iterative operations between the restricted master problem and subproblems to obtain the optimal solution of the linear relaxation of the master problem. Finally, a branch-and-price algorithm, which is a branch and bound framework by embodying column generation as a bounding estimation mechanism, is designed to obtain the integral optimal solution for the original problem. Computational experiments are carried on a set of instances which are randomly generated based on the practical production data collected from a large steel company in China. The results demonstrate that the proposed algorithm can obtain the optimal or sub-optimal solution within a reasonable CPU time.