A hybrid constructive heuristic and simulated annealing for railway crew scheduling


Autoria(s): Hanafi, Rosmalina; Kozan, Erhan
Data(s)

01/01/2014

Resumo

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.

Formato

application/pdf

Identificador

http://eprints.qut.edu.au/66685/

Publicador

Elsevier

Relação

http://eprints.qut.edu.au/66685/1/Paper_A_Hybrid_Constructive_Heuristic_with_Simulated_Annealing_%28final_draft%29.pdf

DOI:10.1016/j.cie.2014.01.002

Hanafi, Rosmalina & Kozan, Erhan (2014) A hybrid constructive heuristic and simulated annealing for railway crew scheduling. Computers & Industrial Engineering, 70, pp. 11-19.

Direitos

Copyright 2014 Elsevier

This is the author’s version of a work that was accepted for publication in Computers & Industrial Engineering. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Computers & Industrial Engineering, [VOL 70, (2014)] DOI: 10.1016/j.cie.2014.01.002

Fonte

School of Mathematical Sciences; Science & Engineering Faculty

Palavras-Chave #090000 ENGINEERING #railway crew scheduling #mathematical programming #constructive heuristics #simulated annealing #combinatorial optimisation
Tipo

Journal Article