| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 214.38 KB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
Description
Keywords
bus drivers rostering bi-objective problems genetic algorithms
Pedagogical Context
Citation
Moz, Margarida, Ana Respício e Margarida Vaz Pato. 2007. "Bi-objective Evolutionary Heuristics for Bus Drivers". Universidade de Lisboa – Centro de Investigação Operacional CIO - Working paper nº 1/2007
Publisher
Centro de Investigação Operacional - Universidade de Lisboa