Bi-objective evolutionary heuristics for bus driver rostering

Margarida Moz (), Ana Respício () and Margarida Vaz Pato ()
Additional contact information
Margarida Moz: Technical University of Lisbon
Ana Respício: University of Lisbon
Margarida Vaz Pato: Technical University of Lisbon

Public Transport, 2009, vol. 1, issue 3, No 2, 189-210

Abstract: Abstract The Bus Driver Rostering Problem (BRP) refers to the assignment of drivers to the daily crew duties that cover a set of schedules for buses of a company during a planning period of a given duration, e.g., a month. An assignment such as this, denoted as roster, must comply with legal and institutional rules, namely Labour Law, labour agreements and the company’s regulations. This paper presents a new bi-objective model for the BRP, assuming a non-cyclic rostering context. One such model is appropriate to deal with the specific and diverse requirements of individual drivers, e.g. absences. Two evolutionary heuristics, differing as to the strategies adopted to approach the Pareto frontier, are described for the BRP. The first one, following a utopian strategy, extends elitism to include an infeasible (utopic) and two potential lexicographic individuals in the population, and the second one is an adapted version of the well known SPEA2 (Strength Pareto Evolutionary Algorithm). The heuristics’ empirical performance was studied through computational tests on BRP instances generated from the solution of integrated vehicle-crew scheduling problems, along with the rules of a public transit company operating in Portugal. This research shows that both methodologies are adequate to tackle these instances. However, the second one is, in general, the more favourable. In reasonable computation times they provide the company’s planning department with several rosters that satisfy all the constraints, an achievement which is very difficult to obtain manually. In addition, among these rosters they identify the potentially efficient ones with respect to the BRP model’s two objectives, one concerning the interests of administration, the other the interests of the workers. Both heuristics have advantages and drawbacks. This suggests that they should be used complementarily. On the other hand, the heuristics can, with little effort, be adapted to a wide variety of rostering rules.

Keywords: Bus driver rostering; Bi-objective problems; Evolutionary algorithms (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s12469-009-0013-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:pubtra:v:1:y:2009:i:3:d:10.1007_s12469-009-0013-x

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12469

DOI: 10.1007/s12469-009-0013-x

Access Statistics for this article

Public Transport is currently edited by Stefan Voß

More articles in Public Transport from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().