Primal transportation and transshipment algorithms

Summary Capacitated transshipment problems constitute the most general class of single commodity network flow problems. During the last ten years the emphasis has shifted away from the primal-dual solution methods back to specializations of the primal simplex algorithm as the more efficient approach. In this survey numerous variations in data structures, selection rules and implementations of individual steps are extracted from the relevant literature. The exposition is centered around one basic algorithm which is explained in complete detail with particular attention to the intricacies of the basis exchange part. Specialized solution methods for transportation and assignment problems are taken into account.

---

Zusammenfassung Die kapazitierten Transshipmentprobleme bilden die allgemeinste Klasse von Flußproblemen in Netzwerken, die sich mit der Verteilung einer einzigen Ware beschäftigen. Während der letzten zehn Jahre hat sich die Betonung von den primal-dualen Lösungsmethoden zurückverlagert zu den Spezialisierungen des primalen Simplexalgorithmus als der effizienteren Prozedur. Für diesen Übersichtsartikel werden die zahlreichen Variationen in den Datenstrukturen, in den Auswahlregeln und in den Verwirklichungen der einzelnen Schritte aus der entsprechenden Literatur ausgewählt. Die Ausführungen haben als Mittelpunkt einen Algorithmus, der in allen Einzelheiten erklärt wird, wobei den Schwierigkeiten des Basiswechsels besondere Aufmerksamkeit gewidmet wird. Spezielle Lösungsmethoden für Transport- und Zuordnungsprobleme werden mitberücksichtigt.

---

---

An invited survey.