交通运输系统工程与信息

交通运输系统工程与信息 ›› 2013, Vol. 13 ›› Issue (4): 157-163.

• 系统工程理论与方法 • 上一篇    下一篇

多阶段带时间约束的变尺寸装箱问题优化研究

朱向*，雷定猷，游伟   

  1. 中南大学 交通运输工程学院，长沙 410075
  • 收稿日期:2013-03-04 修回日期:2013-04-14 出版日期:2013-08-26 发布日期:2013-09-05
  • 作者简介:朱向（1976-），男，湖南长沙人，博士生，讲师.
  • 基金资助:

    国家自然科学基金资助项目（70971140）.

Optimization of Multiphase Variable Size Bin Packing Problem with Time Constraints

ZHU Xiang, LEI Ding-you， YOU Wei   

  1. School of Traffic & Transport Engineering, Central South University, Changsha 410075, China
  • Received:2013-03-04 Revised:2013-04-14 Online:2013-08-26 Published:2013-09-05

PDF

被引次数

8

摘要：

多阶段带时间约束的变尺寸装箱问题，是将一般的变尺寸装箱问题（VSBPP）置于动态环境下并加入时间约束而形成的.通过合理的计划对多阶段、有交付时间要求的物品选择箱子进行装入，达到包括箱子使用成本及与物品相关时间成本在内的总成本最小化的目的.问题具有复杂、动态的特点，其在现实中的应用很多.本文将一般的带时间约束的VSBPP置于多阶段研究框架内，建立了基于确定信息的静态模型和基于滚动更新信息的动态模型，根据问题的特点设计了基于最佳适应规则与迭代松弛定界法相结合的启发式构造算法进行求解.经过实例的运算和分析，证明了方法在求解该问题时具有有效性.

关键词: 物流工程, 动态优化, 构造算法, 变尺寸装箱, 带时间约束

Abstract:

The multiphase variable size bin packing problem with time constraints originates from the variable size bin packing problem (VSBPP) after being placed in dynamical environment. It requires formulating a proper schedule which can minimize the total bin and time cost through selecting the different bins to form a combination to packing items involving multiphase and with tardiness date. It has complex and dynamical natures, and there have been a plenty of applications in reality. This paper investigates the VSBPP with time constraints under the multiphase framework. Then it develops a static model based on exacted information and a dynamic model with rolling updating. According to the characteristics of the problem, a heuristic constructive algorithm is presented integrating the best first decreasing rule and lower bounds technique. The numerical example demonstrates that the models and the algorithm perform well when solving the special bin packing problems.

Key words: logistics engineering, dynamic optimization, constructive algorithm, VSBPP, time constraints

中图分类号: