Fast Algorithms for Single-Sink Fixed Charge Transportation Problems with Applications to Manufacturing and Transportation

The single-sink fixed-charge transportation problem has many applications in the area of Manufacturing and Transportation—These include the supplier selection problem, the product distribution/fleet selection problem and the process selection problem. In this paper we investigate the single-sink fixed-charge transportation problem. We develop implicit enumeration procedures to solve this problem. These procedures include both domination rules and lower bounds. We also show how the domination rules can be integrated into the lower bounds so as to get even better lower bounds. We test our procedures against the best pre-existing procedure and thereby demonstrate that problems which were previously computationally intractable can now be easily solved.