TITLE:
Efficient Heuristic Based Methods for Two-Stage Transshipment Problem
AUTHORS:
Priyank Sinha, Renduchintala Raghavendra Kumar Sharma
KEYWORDS:
Two Stage Transshipment Problem, Min Cost Flow, Transportation Problem, Dual, Primal
JOURNAL NAME:
American Journal of Operations Research,
Vol.8 No.4,
July
3,
2018
ABSTRACT: 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.