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

Van Emden Henson

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

Abstract

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:

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.

References

[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.