Aarhus University Seal / Aarhus Universitets segl

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

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

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.
TidsskriftTransportation Science
Sider (fra-til)428-438
Antal sider11
StatusUdgivet - 2013

Bibliografisk note

Campus adgang til artiklen / Campus access to the article


  • Supplier selection, Network flow, Piecewise linear cost, Dynamic programming, Mixed-integer programming

Se relationer på Aarhus Universitet Citationsformater

ID: 47975963