Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming

Tue R. L. Christensen (), Kim Allan Andersen () and Andreas Klose ()
Additional contact information
Tue R. L. Christensen: Department of Economics and Business, Aarhus University, 8210 Aarhus V, Denmark
Kim Allan Andersen: Department of Economics and Business, Aarhus University, 8210 Aarhus V, Denmark
Andreas Klose: Department of Mathematics, Aarhus University, 8000 Aarhus C, Denmark

Transportation Science, 2013, vol. 47, issue 3, 428-438

Abstract: 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.

Keywords: supplier selection; network flow; piecewise linear cost; dynamic programming; mixed-integer programming (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0431 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:47:y:2013:i:3:p:428-438

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().