Multigrid approach to solving the long transportation problem on a regular grid in cost space
Cornett, Annette P.
Henson, Van E.
Rasmussen, Craig W.
MetadataShow full item record
Multigrid methods were developed to solve partial differential equations. Research has shown that these methods are applicable to a broader range of problems. This thesis investigates the application of multigrid techniques to minimal cost flow problems, specifically the long transportation problem. This research shows that multigrid techniques can be successfully applied to large-scale long transportation problems posed on a three- dimensional, regular grid in cost space. A V-cycle algorithm is developed for the long transportation problem. Analogies to the multigrid components of restriction, interpolation and relaxation are detailed. Performance of the algorithm is discussed, and computational cost is analyzed. Future research is likely to include the development of more sophisticated restriction and interpolation schemes to provide integer-valued flows, and the development of a method to map an irregularly spaced problem to a regular grid, and to map the regular grid solution back to the original problem domain.
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Cavanaugh, Kevin J. (Monterey, California. Naval Postgraduate School, 1992-09);This thesis presents an exploration of the application of multigrid/multilevel techniques to a non-geometric long transportation problem. An introduction to multigrid is given, and specifics of how it is applied to this ...
Nieto, Javier (Monterey, California. Naval Postgraduate School, 1994-03);Multigrid methods have been traditionally applied to the solution of certain Partial Differential Equations. However, applications in control theory, optimization, pattern recognition, computational tomography and particle ...
Volk, John S. (Monterey, California. Naval Postgraduate School, 1994-09);An empirical analysis on the applicability of multigrid techniques to system modeling using system identification techniques is presented. Multigrid with the Toeplitz approximation algorithm is used to model an infinite ...