Christensen, Tue4; Andersen, Kim Allan4; Klose, Andreas5
1 Department of Economics and Business - Business Studies, Department of Economics and Business Economics, Aarhus BSS, Aarhus University2 Department of Mathematics, Science and Technology, Aarhus University3 Department of Economics and Business Economics, Aarhus BSS, Aarhus University4 Department of Economics and Business Economics, Aarhus BSS, Aarhus University5 Department of Mathematics, Science and Technology, Aarhus University
This paper considers a minimum-cost network flow problem in a bipartite graph with a single sink. The transportation costs exhibit a staircase cost structure because such types of transportation cost functions are often found in practice. We present a dynamic programming algorithm for solving this so-called single-sink, fixed-charge, multiple-choice transportation problem exactly. The method exploits heuristics and lower bounds to peg binary variables, improve bounds on flow variables, and reduce the state-space variable. In this way, the dynamic programming method is able to solve large instances with up to 10,000 nodes and 10 different transportation modes in a few seconds, much less time than required by a widely used mixed-integer programming solver and other methods proposed in the literature for this problem.
Transportation Science, 2013, Vol 47, Issue 3, p. 428-438