Efficient Heuristic Based Methods for Two-Stage Transshipment Problem  

作　　者：Priyank Sinha Renduchintala Raghavendra Kumar Sharma 

机构地区：[1]Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India

出　　处：《American Journal of Operations Research》2018年第4期281-293,共13页美国运筹学期刊（英文）

摘　　要：In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by proposing a novel problem formulation for a two stage transshipment problem. Later, special structure of our problem formulation is utilized to devise two dual based heuristics solutions with computational complexity of O (n2), and O (n3) respectively. These methods are motivated by the methods developed by Sharma and Saxena [1], Sinha and Sharma [2]. Our methods differ in the initialization and the subsequent variation of the dual variables associated with the transshipment nodes along the shortest path. Lastly, a method is proposed to extract a very good primal solution from the given dual solutions with a computational complexity of O (n2). Efficacy of these methods is demonstrated by our numerical analysis on 200 random problems.In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by proposing a novel problem formulation for a two stage transshipment problem. Later, special structure of our problem formulation is utilized to devise two dual based heuristics solutions with computational complexity of O (n2), and O (n3) respectively. These methods are motivated by the methods developed by Sharma and Saxena [1], Sinha and Sharma [2]. Our methods differ in the initialization and the subsequent variation of the dual variables associated with the transshipment nodes along the shortest path. Lastly, a method is proposed to extract a very good primal solution from the given dual solutions with a computational complexity of O (n2). Efficacy of these methods is demonstrated by our numerical analysis on 200 random problems.

关 键 词：Two Stage TRANSSHIPMENT PROBLEM Min Cost Flow Transportation PROBLEM Dual Primal 

分 类 号：R73[医药卫生—肿瘤]