Metaheuristics for the bus-driver scheduling problem
AbstractWe present new metaheuristics for solving real crew scheduling problems in a public transportation bus company. Since the crews of these companies are drivers, we will designate the problem by the bus-driver scheduling problem. Crew scheduling problems are well known and several mathematical programming based techniques have been proposed to solve them, in particular using the set-covering formulation. However, in practice, there exists the need for improvement in terms of computational efficiency and capacity of solving large-scale instances. Moreover, the real bus-driver scheduling problems that we consider can present variant aspects of the set covering, as for example a different objective function, implying that alternative solutions methods have to be developed. We propose metaheuristics based on the following approaches: GRASP (greedy randomized adaptive search procedure), tabu search and genetic algorithms. These metaheuristics also present some innovation features based on and genetic algorithms. These metaheuristics also present some innovation features based on the structure of the crew scheduling problem, that guide the search efficiently and able them to find good solutions. Some of these new features can also be applied in the development of heuristics to other combinatorial optimization problems. A summary of computational results with real-data problems is presented.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Department of Economics and Business, Universitat Pompeu Fabra in its series Economics Working Papers with number 304.
Date of creation: Jul 1998
Date of revision:
Contact details of provider:
Web page: http://www.econ.upf.edu/
Metaheuristics; bus-driver; crew-scheduling; tabu-search; GRASP; genetic algorithms;
Find related papers by JEL classification:
- C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
- C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
- L80 - Industrial Organization - - Industry Studies: Services - - - General
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Paias, Ana & Paixao, J., 1993. "State space relaxation for set covering problems related to bus driver scheduling," European Journal of Operational Research, Elsevier, vol. 71(2), pages 303-316, December.
- Beasley, J. E. & Chu, P. C., 1996. "A genetic algorithm for the set covering problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 392-404, October.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ().
If references are entirely missing, you can add them using this form.