Department of Mathematics

The single-sink fixed-charge transportation problem (SSFCTP) consists in finding a minimum cost flow from a number of supplier nodes to a single demand node. Shipping costs comprise costs proportional to the amount shipped as well as a fixed-charge. Although the SSFCTP is an important special case of the well-known fixed-charge transportation problem, just a few methods for solving this problem have been proposed in the literature. After summarising some applications of this problem arising in manufacturing and transportation, we give an overview on approximation algorithms and worst-case results. Finally, we briefly compare some exact solution algorithms for this problem.