Browse Prior Art Database

SOLVING THE TRANSPORTATION PROBLEM

IP.com Disclosure Number: IPCOM000128847D
Original Publication Date: 1956-Jun-20
Included in the Prior Art Database: 2005-Sep-19
Document File: 8 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

Ford, Jr., L.R.,: AUTHOR [+4]

Abstract

A simplified description of a new computing procedure for the Hitchcock-Koopmans transportation problem is given, together with a step-by step solution of an illustrative example. The procedure is based on Kuhn's combinatorial algorithm for the assignment problem and a simple ";labeling process"; for solving maximal-flow problems in networks. The proposed computation appears to be considerably more efficient than the specialized form of the simplex method which is in common use.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SOLVING THE TRANSPORTATION PROBLEM

L. R. Ford, Jr., and D. R. Fulkerson

P-895

June 20, 1956

The RAND Corporation 1700 MAIN ST. SANTA MONICA CALIFORNIA

SUMMARY

A simplified description of a new computing procedure for the Hitchcock-Koopmans transportation problem is given, together with a step-by step solution of an illustrative example. The procedure is based on Kuhn's combinatorial algorithm for the assignment problem and a simple "labeling process" for solving maximal-flow problems in networks. The proposed computation appears to be considerably more efficient than the specialized form of the simplex method which is in common use.

CONTENTS

SUMMARY.....ii
Section

1. INTRODUCTION.....1
2. STATEMENT OF PROBLEM.....3
3. GETTING STARTED.....4
Determination of Starting Weights and Starting Zero Matrix.....4
Determination of Initial Allocations.....6
Remark.....6
4. THE ITERATIVE PROCEDURE.....7
The Labeling Process.....7
Breakthrough.....9
Nonbreakthrough.....11
5. TERMINATION OF SOLUTION.....14
REFERENCES.....15

SOLVING THE TRANSPORTATION PROBLEM

Rand Corporation Page 1 Jun 20, 1956

Page 2 of 8

SOLVING THE TRANSPORTATION PROBLEM

1. INTRODUCTION

A class of linear programming problems having important applications is that commonly known as the transportation problem. The problem was formulated by F. L. Hitchcock1 in 1941; he also sketched a constructive procedure for solving it that is similar to the simplex method2

Independently, during the Second World War, T. C. Koopmans3 considered this problem; thus it is often referred to as the Hitchcock-Koopmans transportation problem. In 1951, G. B. Dantzig4

developed a special form of the simplex method for transportation problems; this method has since been widely used. Large systems involving hundreds of equations in thousands of unknowns have been successfully solved by hand using the simplex computation. The procedure of this paper has been compared with the simplex method on a number of randomly chosen problems and has been found to take roughly half the effort for small5 problems. We believe that, as the size of the problem increases, the advantages of the present method become even more marked.

The proposed method is based on a new combinatorial procedure recently developed by H. Kuhn6 for solving the optimal assignment problem (a special type of transportation problem). In this method (which Kuhn has named the "Hungarian Method") an essential feature of a proof given by the Hungarian mathematician Egervary7 for a theorem of Konig concerning linear graphs is combined with a very efficient algorithm for solving a specialized assignment problem (Routine I of [ 6 ] .8

The present writers9 subsequently discovered a simple algorithm for solving maximal flow problems in networks. This algorithm, when applied to the special network of the Hitchcock problem, serves as a substitute for routine I of [ 6 ] 10 and enables one to solve...