Premium
On some techniques useful for solution of transportation network problems
Author(s) -
Tomizawa N.
Publication year - 1971
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230010206
Subject(s) - dijkstra's algorithm , transportation theory , mathematical optimization , computer science , reduction (mathematics) , dual (grammatical number) , process (computing) , flow network , algorithm , mathematics , shortest path problem , graph , theoretical computer science , art , geometry , literature , operating system
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.