Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems
Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems
复制标题
固定电荷传输问题：基于拉格朗日松弛的新启发式方法和核心问题的解决
DOI：
10.1007/s10479-008-0483-2
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jesús Sáez Aguado
中科院分区：
文献类型：
--
作者：
Jesús Sáez Aguado
本文研究固定费用运输问题。提出了一种新的启发式方法，密集使用拉格朗日松弛技术的基础上。这种方法的更新颖的方面是新的拉格朗日松弛和分解方法，考虑几个核心问题，从以前计算的拉格朗日降低成本，启发式选择最有前途的核心问题，并最终诉诸枚举通过应用一个分支和切割算法选择的核心问题。对于平均固定成本与平均可变成本之比较小（小于或等于25）的问题，该方法可以获得与禁忌搜索算法和参数化鬼像算法相似或更好的解.对于较大的比率（在50和180之间），所获得的解的质量可以被认为是两种方法之间的一半。
In this paper the Fixed Charge Transportation Problem is considered. A new heuristic approach is proposed, based on the intensive use of Lagrangean relaxation techniques. The more novel aspects of this approach are new Lagrangean relaxation and decomposition methods, the consideration of several core problems, defined from the previously computed Lagrangean reduced costs, the heuristic selection of the most promising core problem and the final resort to enumeration by applying a branch and cut algorithm to the selected core problem. For problems with a small ratio of the average fixed cost to the average variable cost (lower than or equal to 25), the proposed method can obtain similar or better solutions than the state-of-art algorithms, such as the tabu search procedure and the parametric ghost image processes. For larger ratios (between 50 and 180), the quality of the obtained solutions could be considered to be halfway between both methods.