Search

A transshipment problem (G , d , λ) is modeled by a directed graph G = (V , E) with weighted vertices (nodes) d = (d v ∣ v ∈ V) and weighted directed edges (arcs) λ = (λ e ∣ e ∈ E) interpreted as follows: G is a communication or transportation network, for example, a pipeline; each arc e ∈ E is a one-way communication line, road or pipe of capacity λ e , while every vertex v ∈ V is a node of production d v > 0 , consumption d v < 0 , or just transition d v = 0. A non-negative flow x = (x e ∣ e ∈ E) is called weakly feasible if for each v ∈ V the algebraic sum of flows, over all directed edges incident to v , equals d v , or shorter, if A G x = d , where A G is the vertex-edge incidence matrix of G. A weakly feasible flow x is called feasible if x e ≤ λ e for all e ∈ E. We consider weakly feasible but not necessarily feasible flows, that is, inequalities x e > λ e are allowed. However, such an excess is viewed as unwanted (dangerous) and so we minimize the excess ratio vector r = (r e = x e / λ e ∣ e ∈ E) lexicographically. More precisely, first, we look for weakly feasible flows minimizing the maximum of r e over all e ∈ E ; among all such flows we look for those that minimize the second largest coordinate of r , etc. Clearly, in | E | such steps we obtain a unique lexmin vector r. We show that the corresponding balanced flow is also unique and represents the lexmin solution for problem (G , d , λ). Using the Gale–Hoffman inequalities, we construct it in polynomial time, provided vectors d and λ are rational. For symmetric digraphs the problem was solved by Gurvich and Gvishiani in 1984. Here we extend this result to arbitrary directed graphs. Furthermore, we simplify the algorithm and proofs applying the classic criterion of existence of a feasible flow for (G , d , λ) obtained by Gale and Hoffman in late 1950s. [ABSTRACT FROM AUTHOR]