Set Partition Model and Algorithm for Crew Pairing Problem in Urban Rail Transit

Abstract:

A set partition model (R CP) for the crew pairing problem in urban rail transit was proposed based on practical considerations in rail transit operations. A hybrid algorithm of column generation and branch on follow ons (CGBF) was designed to solve R CP. The numerical results show that the proposed model and algorithm can meet requirements of crew pairing and yield better objective values than the existing manual methods.

Key words:urban rail transit; crew pairing problem; set partition problem; column generation; branch on follow ons