A multilevel cost-space approach to solving the balanced long transportation problem

Kevin Cavanaugh

U.S. Coast Guard Research and Development Center, Groton, CT.

Van Emden Henson

Department of Mathematics, Naval Postgraduate School, Monterey, CA 93943


A transportation problem is to minimize the cost of shipping a commodity from a set of supply points to a set of demand points. The problem is balanced if the total supply exactly equals the total demand. A long transportation problem is one where the number of demand points is many times greater than the number of supply points. Such a problem may be stated as:

Minimize c^{T}x subject to the constraint Ax=b.
Here c is vector containing shipping costs, x is the vector of commodity flow, while A and b ensure that the problem is balanced. Although efficient solution methods for the transportation problem have long since been established, it nevertheless remains a useful test problem for the development of new methods that are intended, eventually, to be developed for more intractible problems.

We develop multilevel schemes for solving the long, balanced transportation problem. Little previous work has been done on this problem ([ronachi], [kaminsky], [ron] ). The most successful effort to date is that of [kaminsky], who developed methods for the problem that required a geometric relation between cost of shipping and distance shipped.

Our schemes remove this geometric requirement, instead transferring the problem to a space in which cost of shipping is the metric for measuring distance between points. Thus we are able to develop coarsening schemes that group together demand nodes having similar shipping costs. Much of the difficulty in formulating multilevel methods for this problem, however, arises because there are no clear analogs of relaxation, interpolation, and coarse-grid correction. Indeed, the problem has no analog to a residual equation, necessitating an FAS-like approach. We discuss several approaches to interpolation, coarsening, and relaxation, giving the merits and drawbacks to several.


[ronachi] Dorit Ron, D. Amit, and Achi Brandt. Multi-level approaches to discrete-state and stochastic problems, in W. Hackbusch and U. Trottenberg (eds.), Multigrid Methods II (Proceedings, Cologne), Lecture notes in mathematics no. 1228. Springer-Verlag, 1985.

[kaminsky] Ron Kaminsky. Multilevel solution of the long transportation problem, MS thesis. Weizmann Institute of Science, 1986.

[ron] Dorit Ron. Development of fast numerical solvers for problems in optimization and statistical mechanics, PhD thesis. Weizmann Institute of Science, 1987.