运输能力受限与费用时变批量问题的拉格朗日松弛启发式算法  

A Lagrangian-based heuristic algorithm for multi-product capacitated lot sizing with time-varying transportation costs

作　　者：鲁奎[1] 杨昌辉[2] 戴道明[2] 

机构地区：[1]中国科学技术大学管理学院,合肥230026 [2]合肥工业大学管理学院,合肥230009

出　　处：《系统工程理论与实践》2008年第10期47-52,共6页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70631003);合肥工业大学科学研究发展基金(051102F)

摘　　要：在多产品、多周期动态批量问题中引入产品的运输成本,每个周期采购的产品通过同一类型的运输工具运输.单位运输工具运载能力受限,每个周期可以使用的运输工具数量有限且单位使用费用时变.根据初始假定建立混合整数规划模型,运用拉格朗日松弛理论,通过约束松弛与模型分解,设计一个启发式算法进行模型求解.通过随机产生的大量实例从计算效果与效率两方面来评价启发式算法.This paper addresses multi-product, multi-period, dynamic lot sizing problem with time-varying transportation costs, in which the order size of multiple products and a single container type are simultaneously considered. In the problem, each order placed in a period is immediately shipped by some containers in the period and the total freight cost is proportional to the number of containers used. The carrying capacity of single container and number of containers available for use in each period is limited. The objective of this study is to simultaneously determine the lot sizes and the transportation policy that minimizes the total costs, which consist of ordering cost, inventory cost, and freight cost. Because this problem is NP-hard, a tagrangian-based heuristic algorithm is proposed to compute lower and upper bounds, of which comprehensive computational experiments show the compelling performance in terms of quality and speed.

关 键 词：批量 拉格朗日松弛 运输成本 启发式算法 

分 类 号：O224[理学—运筹学与控制论] F224.3[理学—数学]