Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications

The objective of the classical minimum cost flow problem is to send units of a good that reside at one or more points in a network (sources or supply nodes) with arc capacities to one or more other points in the network (sinks or demand nodes), incurring minimum cost. We develop fast algorithms for previously unstudied specially structured minimum cost flow problems that have applications in many areas, such as locomotive and airline scheduling, repositioning of empty rail freight cars, highway and river transportation, congestion pricing, shop loading, and production planning. First, we consider the case where the n 1 supply and n 2 demand nodes lie on a circle (or line) ( n = n 1 + n 2 ) and flow is allowed only in one direction; our algorithm solves this problem in O ( n ) time. Next, we consider a constrained version of this problem and show that it can be solved in O ( n log n 2 ) time. Finally, we consider the version where the nodes lie on a circle (or line), flow is allowed in both directions, and the costs of flow between two nodes in the clockwise and the counterclockwise direction are different; our algorithm solves this problem in O ( n log n ) time. Our algorithms are based on the successive shortest-path algorithm for the minimum cost flow problem. We exploit the special structure of the problem and use advanced data structures, when required, to achieve short run times.