Paper Info
Title
A hybrid constructive heuristic and simulated annealing for railway crew scheduling
Abstract
Railway crew scheduling problem is the process of allocating train services to the crew duties based on the published train timetable while satisfying operational and contractual requirements. The problem is restricted by many constraints and it belongs to the class of NP-hard. In this paper, we develop a mathematical model for railway crew scheduling with the aim of minimising the number of crew duties by reducing idle transition times. Duties are generated by arranging scheduled trips over a set of duties and sequentially ordering the set of trips within each of duties. The optimisation model includes the time period of relief opportunities within which a train crew can be relieved at any relief point. Existing models and algorithms usually only consider relieving a crew at the beginning of the interval of relief opportunities which may be impractical. This model involves a large number of decision variables and constraints, and therefore a hybrid constructive heuristic with the simulated annealing search algorithm is applied to yield an optimal or near-optimal schedule. The performance of the proposed algorithms is evaluated by applying computational experiments on randomly generated test instances. The results show that the proposed approaches obtain near-optimal solutions in a reasonable computational time for large-sized problems.
Year
DOI
Venue
2014
10.1016/j.cie.2014.01.002
Computers & Industrial Engineering
Keywords
Field
DocType
published train timetable,railway crew scheduling,simulated annealing,mathematical model,train crew,railway crew scheduling problem,crew duty,hybrid constructive heuristic,optimisation model,relief opportunity,train service,relief point,mathematical programming
Simulated annealing,Decision variables,Search algorithm,Crew,Crew scheduling,Operations research,Schedule,Engineering,Constructive heuristic,TRIPS architecture
Journal
Volume
ISSN
Citations 
70,
0360-8352
0
PageRank 
References 
Authors
0.34
12
2
Name
Order
Citations
PageRank
Rosmalina Hanafi100.34
Erhan Kozan231532.28