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

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

作　　者：朱向[1] 雷定猷[1] 游伟[1] 

机构地区：[1]中南大学交通运输工程学院,长沙410075

出　　处：《交通运输系统工程与信息》2013年第4期157-163,共7页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家自然科学基金资助项目(70971140)

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

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

分 类 号：U294.6[交通运输工程—交通运输规划与管理]