Reshipments and overshipments in transportation problems with minimax objective (Q1182137)

Three versions of minimax flow transportation problems (MFTP) are considered (the standard, reshipment and overshipment minimax flow transportation problem). These problems are special cases of so-called sharing problems as introduced by \textit{J. R. Brown} [Oper. Res. 27, 341- 355 (1979; Zbl 0394.90065); Math. Program. 25, 199-227 (1983; Zbl 0507.90026)]. Explicit formulas for the optimal objective function values of all three versions of minimax flow transportation problems are obtained by means of network flow theory. It is shown that these formulas can be evaluated in linear time. Efficient algorithms for the transportation problems under consideration are developed. Three extensions of the MFTP's are discussed.