A Hybrid Solution Approach for Railway Crew Scheduling Problems with Attendance Rates
This paper presents a model for railway crew scheduling problems dealing with attendance rates for conductors. Afterwards we discuss a hybrid solution approach for these kind of problems. This approach consists of a column generation framework using genet
- PDF / 137,870 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 242 Views
Abstract This paper presents a model for railway crew scheduling problems dealing with attendance rates for conductors. Afterwards we discuss a hybrid solution approach for these kind of problems. This approach consists of a column generation framework using genetic algorithm to solve the pricing problem. Based on a real-world instance, we compare our hybrid solution approach with the enumeration approach with respect to resulting total costs and computation time.
1 Introduction Apart from energy costs (fuel, electricity), crew costs are the largest cost factor in rail passenger transport. Therefore, the efficient assignment of crews is becoming increasingly more important. Previous crew scheduling models and solution approaches mostly deal with covering all trips of the given train timetable. The diminishing importance of operational tasks and increasing cost pressure, however, force responsible authorities in Germany to reduce the deployment of conductors. Therefore, transportation contracts defining all frame conditions for different transportation networks determine one or more percentage rates of trains or kilometres that have to be attended by conductors. In regional rail transport, crew members are train drivers (operator of a train) and conductors (tasks: ticket collection and other customer services). We focus on the latter, as variable attendance rates cannot be applied to train drivers, obviously. Nevertheless, train drivers could be included with attendance rates of 100 %. There is a wide range of models and algorithms concerning transport crew scheduling and rostering, respectively. For a recent review on passenger railway optimization, see [1]. Due to the size of crew scheduling problems (up to several millions of possible duties), metaheuristics are increasingly gaining in importance. Reference [8] introduce a tabu search algorithm for bus and train drivers. Reference [3] present a mathematical model for railway crew scheduling solved by simulated annealing. K. Hoffmann (B) Faculty of Business and Economics, TU Dresden, 01062 Dresden, Germany e-mail: [email protected] © Springer International Publishing Switzerland 2017 K.F. Dœrner et al. (eds.), Operations Research Proceedings 2015, Operations Research Proceedings, DOI 10.1007/978-3-319-42902-1_33
243
244
K. Hoffmann
Genetic algorithms can be applied in two different ways: After generating feasible duties, genetic algorithms are used to find the optimal shift schedule. On the other hand, the pricing problem (generation of new duties) can be solved with genetic algorithms [5, 7]. To the best of our knowledge, there are no appropriate models or algorithms dealing with attendance rates. Therefore, we define a new model with attendance rates in Sect. 2. Section 3 presents the hybrid solution approach, containing a column generation framework with a genetic algorithm to solve the pricing problem. Section 4 reports the results of our computational experiments.
2 Crew Scheduling Problem with Attendance Rates In public transport, especia
Data Loading...
