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

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.