On some techniques useful for solution of transportation network problems

Abstract

Abstract This paper presents an efficient algorithm for solving transportation problems. The improvement over the existing algorithms of the “primal‐dual” type [3], [5] consists in modifying the “potential‐raising” stages of the solution process in such a way that negative‐cost arcs are removed so that the Dijkstra's algorithm may be applied. Especially, the algorithm requires at most n 3 additions and comparisons when applied to an n‐by‐n assignment problem, as compared with the theoretical upper bound proportional to n 4 for the number of such operations required by currently available methods. Furthermore, auxiliary techniques of simplifying the original network by means of “reduction” and “induction” are also introduced as useful tools to treat large‐scale problems and specially‐structured problems with.