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

Cutting Stock Problem and Transportation Problem Collaboration Optimization Modeling

作　　者：靳鹏[1,2] 左春荣[1,2] 杨善林[1,2] 马华伟[1,2] 

机构地区：[1]合肥工业大学管理学院,安徽合肥230009 [2]过程优化与智能决策教育部重点实验室,安徽合肥230009

出　　处：《中国管理科学》2013年第2期91-97,共7页Chinese Journal of Management Science

基　　金：国家自然科学基金重点资助项目(71131002);国家自然科学基金资助项目(70801024;71171072;71001032)

摘　　要：本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和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.

关 键 词：下料 运输 排序 拉格朗日松弛 模式 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]