Solving large scale crew scheduling problems by using iterative partitioning

Erwin Abbink

No EI 2008-03, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: This paper deals with large-scale crew scheduling problems arising at the Dutch railway operator, Netherlands Railways (NS). NS operates about 30,000 trains a week. All these trains need a driver and a certain number of conductors. No available crew scheduling algorithm can solve such huge instances at once. A common approach to deal with these huge weekly instances, is to split them into several daily instances and solve those separately. However, we found out that this can be rather inefficient. In this paper, we discuss several methods to partition huge instances into several smaller ones. These smaller instances are then solved with the commercially available crew scheduling algorithm TURNI. We compare these partitioning methods with each other, and we report several results where we applied different partitioning methods after each other. The results show that all methods significantly improve the solution. With the best approach, we were able to cut down crew costs with about 2\\% (about 6 million euro per year).

Keywords: crew scheduling; large-scale optimization; partitioning methods (search for similar items in EconPapers)
Date: 2008-03-18
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://repub.eur.nl/pub/11701/ei200803.pdf (application/pdf)

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:ems:eureir:11701

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).