The Factored Transportation Problem

The factored transportation problem is one having cost coefficients of the form c_ij = u_iv_j. The main result proven in this paper is that if rows are arranged according to nonincreasing u_i and columns by nondecreasing v_j, then the northwest corner rule provides an optimal solution. Applications to stock location in a warehouse and information storage and retrieval policies are presented. For the stock location problem, this verifies that a previously advocated heuristic is optimal.