下料问题与运输问题联合优化建模

Cutting Stock Problem and Transportation Problem Collaboration Optimization Modeling

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。

In this paper,a standard one-dimensional cutting stock problem（S1-CSP） considering items transportation problem（ITP） is studied.It is assumed that the manufacturer undertakes products transportation.A coordination optimization model of standard one-dimensional cutting stock problem and items transportation is formulated.The model’s objective is to minimize total costs of the stock,items inventory and transportation.Lagrangian relaxation approach is employed to relax a certain type of constraint.A hybrid heuristic method called Lagrangian-based cutting and transportation heuristic based on the methods of column generation,sequential procedure,FFD and subgradient is developed.It consists of two sub-algorithms,one is for S1D-CSP,the other is for ITP.Finally,more than 1800 randomly generated instances have been solved by using the proposed method.The calculation results demonstrate the validity of the proposed model and the corresponding solving method.Compared with two-stage heuristic based on column generation,the hybrid heuristic algorithm reduces cost by 17.57% on average,which suggests that integrated algorithm is superior to two-stage algorithm.