主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2013, Vol. ›› Issue (2): 91-97.

• 论文 • 上一篇    下一篇

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

靳鹏1,2, 左春荣1,2, 杨善林1,2, 马华伟1,2   

  1. 1. 合肥工业大学管理学院, 安徽 合肥 230009;
    2. 过程优化与智能决策教育部重点实验室, 安徽 合肥 230009
  • 收稿日期:2011-03-27 修回日期:2012-05-21 出版日期:2013-04-30 发布日期:2013-04-25
  • 基金资助:
    国家自然科学基金重点资助项目 (71131002); 国家自然科学基金资助项目(70801024,71171072,71001032)

Cutting Stock Problem and Transportation Problem Collaboration Optimization Modeling

JIN Peng1,2, ZUO Chun-rong1,2, YANG Shan-lin1,2, MA Hua-wei1,2   

  1. 1. School of Management, Hefei University of Technology, Hefei 230009, China;
    2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China
  • Received:2011-03-27 Revised:2012-05-21 Online:2013-04-30 Published:2013-04-25

PDF (PC)

2607

被引次数

5

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

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

Abstract: 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.

Key words: cutting stock, transportation, sequencing, Lagrangian relaxation, patterns

中图分类号: