Allocation of Transportation Units to Alternative Trips—A Column Generation Scheme with Out-of-Kilter Subproblems

M. R. Rao and S. Zionts
Additional contact information
M. R. Rao: United States Steel Corporation, Monroeville, Pennsylvania
S. Zionts: United States Steel Corporation, Monroeville, Pennsylvania

Operations Research, 1968, vol. 16, issue 1, 52-63

Abstract: The problem of allocating transportation units to alternative trips can be solved by linear programming. However, the linear programming formulation has three shortcomings: (1) the optimal solution obtained does not have an integer number of trips; (2) the optimal solution may have sets of disconnected cycles; and (3) problems of considerable size will be intractable because of the vast number of variables and constraints. In some applications, it has been found that shortcomings 1 and 2 are not serious, but the third one—the size of the problem—presents considerable difficulty. This paper describes an approach—a column generation scheme with out-of-kilter subproblems—that reduces the size of the problem considerably. An algorithm for the method is given, and it is proved that the algorithm solves the problem in a finite number of steps. Computational experience thus far with this method has been limited, but encouraging.

Date: 1968
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.16.1.52 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:16:y:1968:i:1:p:52-63

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().