Article ID: | iaor2002437 |
Country: | Netherlands |
Volume: | 99 |
Issue: | 1 |
Start Page Number: | 141 |
End Page Number: | 166 |
Publication Date: | Dec 2000 |
Journal: | Annals of Operations Research |
Authors: | Wedelin Dag, Alefragis Panayiotis, Sanders Peter, Takkula Tuomo |
Keywords: | vehicle routing & scheduling, personnel & manpower planning |
Performance aspects of a Lagrangian relaxation based heuristic for solving large 0–1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, Göteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.