| We propose several extensions to the existing methodologies for solving large-scale network routing problems like those often found in the distribution, transportation, and telecommunications industries. Our work is centered on the path flow formulation and the ensuing combinatorial explosion in the number columns. Our methods are aimed at pushing the boundaries of cases whose columns can be enumerated up front, as well as, those capable of efficiently using delayed column generation.; The primal-dual subproblem simplex method is the foundation upon which our research is based. We introduce the notion of strings and their use in an enhanced compact storage scheme for the enumeration of columns. For larger instances, we offer a significantly new approach that incorporates delayed column generation within the primal-dual subproblem framework. While our primary focus is on solving linear models, we do include some specific techniques for obtaining good integer solutions within a reasonable amount of time.; Airline crew scheduling is the area we chose for our implementation. Cockpit and cabin crew scheduling and daily and weekly problems are addressed. For the weekly case, we introduce a frequency-based enumeration method that provides an additional level of compacting and allows us to consider pairing regularity. We propose a new network specifically designed for airline crew scheduling, the extended duty network, and the resulting hybrid column generation method.; Our computational results demonstrate that our methods are capable of pushing well beyond the boundaries of current methodologies for the crew scheduling scenarios we tested. In one case, we were able to solve the LP relaxation of an 860 billion column problem with over 2500 rows in just 21 minutes. Moreover, we were able to obtain an integer solution within .12% of the LP solution. The total runtime from schedule to IP solution was just over 2 hours. |
