Bi-objective Evolutionary Heuristics for Bus Drivers

• Author(s): Moz, Margarida ; Respício, Ana ; Pato, Margarida Vaz
• Date: 2007
• Persistent ID: http://hdl.handle.net/10400.5/1423
• Origin: Repositório da UTL
• Subject(s): bus drivers rostering; bi-objective problems; genetic algorithms
• Document Type: Working paper
• Language: English
• Contributor(s): Repositório da Universidade de Lisboa

Description

The Bus Driver Rostering Problem refers to the assignment of drivers to the daily schedules of the company's buses, during a planning period of a given duration. The drivers' schedules must comply with legal and institutional rules, namely the Labour Law, labour agreements and the company's specific regulations. This paper presents a bi-objective model for the problem and two evolutionary heuristics differing as to the strategies adopted to approach the Pareto frontier. The first one, the utopian strategy, extends elitism to include an unfeasible solution in the population, and the second one is an adapted version of the well known SPEA2 (Strength Pareto Evolutionary Algorithm). The heuristics' empirical performance is studied with computational tests on a set of instances generated from vehicle and crew schedules. This research shows that both methodologies are adequate to tackle the instances of the Bus Driver Rostering Problem. In fact, in short computing times, they provide the planning department, with several feasible solutions, rosters that are very difficult to obtain manually and, in addition, identify among them the efficient solutions of the bi-objective model.