1 Department of Mathematical Sciences, Faculty of Science, Aarhus University, Aarhus University2 University of Wuppertal3 Department of Mathematics, Science and Technology, Aarhus University4 Department of Mathematics, Science and Technology, Aarhus University
The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.
Journal of Heuristics, 2009, Vol 15, Issue 4, p. 331-349
Fixed-charge transportation problem · Min-knapsack problem · Greedy Fixed-charge transportation problem, min-knapsack problem, greedy algorithms, worst-case analysis, approximation algorithms