×

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].

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite