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

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.