Desaulniers, Guy; Desrosiers, Jacques; Solomon, Marius M. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. (English) Zbl 1017.90045 Ribeiro, Celso C. et al., Essays and surveys in metaheuristics. Boston: Kluwer Academic Publishers. Oper. Res./Comput. Sci. Interfaces Ser. 15, 309-324 (2002). Summary: This paper focuses on accelerating strategies used in conjunction with column generation to solve vehicle routing and crew scheduling problems. We describe techniques directed at speeding up each of the five phases of the solution process: pre-processor, subproblem, master problem, branch-and-bound, and post-optimizer. In practical applications, these methods often were key elements for the viability of this optimization approach. The research cited here shows their use led to computational gains, and notably to solutions that could not have been obtained otherwise due to practical problem complexity and size. In particular, we present recent methods directed at the integer programming aspect of the approach that were instrumental in substantially reducing the integrality gap found in certain applications, thereby helping to efficiently produce excellent quality solutions.For the entire collection see [Zbl 0976.00017]. Cited in 1 ReviewCited in 23 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90C59 Approximation methods and heuristics in mathematical programming Keywords:vehicle routing; scheduling problems PDFBibTeX XMLCite \textit{G. Desaulniers} et al., in: Essays and surveys in metaheuristics. Selected papers of the Third Metaheuristics International Conference held in Angra dos Reis, Brazil, July 1999. Boston: Kluwer Academic Publishers. 309--324 (2002; Zbl 1017.90045)