Premium
Enhanced genetic algorithms for a bi‐objective bus driver rostering problem: a computational study
Author(s) -
Respício Ana,
Moz Margarida,
Vaz Pato Margarida
Publication year - 2013
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12013
Subject(s) - memetic algorithm , computer science , benchmark (surveying) , genetic algorithm , mathematical optimization , context (archaeology) , pareto principle , lexicographical order , combinatorial optimization , local search (optimization) , algorithm , machine learning , mathematics , paleontology , geodesy , combinatorics , biology , geography
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.