An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems (Q792216)

To improve an algorithm by \textit{B. Gavish} and \textit{E. Shlifer} [ibid. 3, 122-134 (1979; Zbl 0392.90055)] for a class of transportation scheduling problems, \textit{G. P. White} [ibid. 9, 190-193 (1982; Zbl 0473.90054)] proposes the use of an alternative subproblem as a relaxation within a branch and bound framework. White's subproblem replaces an assignment problem relaxation used in Gavish and Shlifer's paper [loc. cit.] with a bipartite weighted matching problem, observing that the latter is susceptible to a 'Hungarian-type' of algorithm due to \textit{E. Lawler} [''Combinatorial optimization: Networks and matroids'' (1976; Zbl 0413.90040)]. The purpose of this note is to show that the bipartite weighted matching problem, applying a special case of a result of \textit{A. Charnes, F. Glover} and \textit{D. Klingman} [Nav. Res. Logist. Q. 18, 277-281 (1971; Zbl 0226.90025)], is equivalent to a 'quasi-transportation' problem - i.e., a transportation problem in which exactly one origin and one destination have a non-unit supply and demand. Empirical studies of \textit{F. Glover} and \textit{D. Klingman} [Techn. Rep. 212, Army Office Res., Research Triangle, Durham, NC, USA (1980)] have shown that the quasi- transportation problem can be solved very efficiently by a primal simplex type of code that exploits an alternating path basis structure due to \textit{R. S. Barr, F. Glover} and \textit{D. Klingman} [Eur. J. Oper. Res. 2, 137-144 (1978; Zbl 0376.90068)].