| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 1.24 MB | Adobe PDF |
Advisor(s)
Abstract(s)
In this work, the bus driver rostering problem is considered in the context of a noncyclic rostering, with two objectives representing either the company or the drivers’ interests. A network model and a proof of the NP-hardness of the problem are presented, along with a bi-objective memetic algorithm that combines a specific decoder with a utopian/lexicographic elitism, a strength Pareto fitness evaluation, and a local search procedure. By taking real and benchmark instances the computational behavior of the memetic algorithm is compared with simpler versions to assess the effects of the embedded components. The developed algorithm is a valuable tool for bus companies’ planning departments insofar as it yields at low computing times a pool of good quality rosters that reconcile contradictory objectives. This study shows that simple enhancements in standard bi-objective genetic algorithms may improve the results for this difficult combinatorial problem.
Description
Keywords
Bus Driver Rostering Personnel Scheduling Evolutionary Algorithms Multi-Objective Heuristics
Pedagogical Context
Citation
Respício, Ana; Margarida Moz and Margarida Vaz Pato .(2013). "Enhanced genetic algorithms for a bi-objective bus driver rostering problem: a computational study". International Transations in Operational Research, vol. 20: pp. 443-470. 2013
Publisher
John Wiley & Sons Ltd.