| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 300.75 KB | Adobe PDF |
Advisor(s)
Abstract(s)
The Bus Driver Rostering Problem (DRP) consists of assigning bus drivers to daily duties during a planning period. The problem considers hard constraints imposed by institutional and legal requirements. Solutions should as much as possible satisfy soft constraints that qualify rosters according to either the company's or the drivers' interests. A bi-objective version of the DRP is considered and two models are presented. Due to the high computational complexity of DRP, this paper proposes the Strength Pareto Utopic Memetic Algorithm (SPUMA) a new heuristic algorithm specially devised to tackle the problem. SPUMA genetic component combines utopic elitism with a strength Pareto fitness evaluation and includes an improvement procedure. Computational results show that SPUMA outperforms an adaptation of one of the state-of-the-art most competitive multi-objective evolutionary algorithms, SPEA2.
Description
Keywords
urban transit planning bus rostering multi-objective evolutionary algorithm memetic algorithm
Pedagogical Context
Citation
Respício, Ana, Margarida Moz e Margarida Vaz Pato. 2007. "A Memetic Algorithm for a Bi-objective Bus Driver Rostering Problem". Universidade de Lisboa – Centro de Investigação Operacional - CIO Working paper nº 13/2007
Publisher
Centro de Investigação Operacional - Universidade de Lisboa