Universität zu Köln

Juette, Silke and Thonemann, Ulrich ORCID: 0000-0002-3507-9498 (2015). A graph partitioning strategy for solving large-scale crew scheduling problems. OR Spectrum, 37 (1). S. 137 - 171. NEW YORK: SPRINGER. ISSN 1436-6304

Full text not available from this repository.

Abstract

Railway crew scheduling deals with generating driver duties for a given train timetable such that all work regulations are met and the resulting schedule has minimal cost. Typical problem instances in the freight railway industry require the generation of duties for thousands of drivers operating tens of thousands of trains per week. Due to short runtime requirements, common solution approaches decompose the optimization problem into smaller subproblems that are solved separately. Several studies have shown that the way of decomposing the problem significantly affects the solution quality. An overall best decomposition strategy for a freight railway crew scheduling problem, though, is not known. In this paper, we present general considerations on when to assign two scheduled train movements to separate subproblems (and when to rather assign them to the same subproblem) and deduct a graph partitioning based decomposition algorithm with several variations. Using a set of real-world problem instances from a major European railway freight carrier, we evaluate our strategy and benchmark the performance of the decomposition algorithm both against a common non-decomposition algorithm and a lower bound on the optimal solution schedule. The test runs show that our decomposition algorithm is capable of producing high-quality solution schedules while significantly cutting runtimes compared to the non-decomposition solution algorithm. We are following a greenfield approach, where no information on previous schedules is needed. Hence, our approach is applicable to any railway crew scheduling setting, including network enlargement, integration of new customers, etc.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Juette, Silke UNSPECIFIED UNSPECIFIED UNSPECIFIED Thonemann, Ulrich UNSPECIFIED orcid.org/0000-0002-3507-9498 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-417869
DOI:	10.1007/s00291-014-0381-8
Journal or Publication Title:	OR Spectrum
Volume:	37
Number:	1
Page Range:	S. 137 - 171
Date:	2015
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1436-6304
Language:	English
Faculty:	Faculty of Management, Economy and Social Sciences
Divisions:	Center of Excellence C-SEB
Subjects:	Economics
Uncontrolled Keywords:	Keywords Language BRANCH-AND-PRICE; COLUMN GENERATION; DECOMPOSITION; VEHICLE; SCHEME Multiple languages Operations Research & Management Science Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/41786