A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem
A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem
复制标题
多集装箱装载成本最小化问题的目标驱动原型柱生成策略
DOI：
10.1016/j.ejor.2014.08.015
复制
发表时间：
2015-02
影响因子：
6.4
通讯作者：
Lim Andrew
中科院分区：
文献类型：
--
作者：
Wei Lijun;Zhu Wenbin;Lim Andrew
在多集装箱装载成本最小化问题中，为了使总运输成本最小，将不同尺寸的矩形箱子装载到不同尺寸的矩形集装箱中。MCLCMP可以自然地建模为集合覆盖问题。我们通过引入一个新的参数来对溶液中容器的总体积利用率进行建模，从而推广了集合覆盖公式。最先进的算法使用原型列生成(PCG)技术来处理MCLCP。对于极其困难的优化问题，PCG是一种有效的加速列生成技术，其中相应的定价子问题是NP-难的。我们提出了一种将PCG技术与目标驱动搜索相结合的MCLCMP新方法。本文提出的目标驱动原型列生成算法(GD-PCG)在三个方面对原有的原型列生成算法进行了改进。计算实验表明，这三种改进都是有效的。与文献中的所有其他方法相比，我们的GD-PCG算法使用更少的计算时间为350个现有的基准实例产生了明显更好的解决方案。我们还基于工业数据生成了两个新的集合实例和经典的单箱装载实例。
In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.
登录
查看更多内容
DOI：
10.1016/j.ejor.2012.04.036
发表时间：
2012-11
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Wenbin Zhu;A. Lim
通讯作者：
Wenbin Zhu;A. Lim
影响因子：
3.1
作者：
H. Gehring;Andreas Bortfeldt
通讯作者：
H. Gehring;Andreas Bortfeldt
影响因子：
12
作者：
Ning Wang;A. Lim;Wenbin Zhu
通讯作者：
Ning Wang;A. Lim;Wenbin Zhu
影响因子：
1.4
作者：
Bortfeldt, A;Gehring, H;Mack, D
通讯作者：
Mack, D
DOI：
10.1016/j.cor.2012.03.016
发表时间：
2013-12
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit
通讯作者：
R. Alvarez-Valdés;F. Parreño;J. M. Tamarit