A Lagrangian relaxation-based heuristic for the bus driver scheduling problem: a case study of Beijing

The bus driver scheduling problem is the problem of generating and selecting a set of legal duties to cover all vehicle blocks and minimize transit agency's total operational costs. In this paper, a set partitioning/covering problem (SPP/SCP) based mathematical model for this problem in Beijing is presented. A tree enumeration algorithm is firstly used to enumerate all potential duties, which can reduce the SCP to a manageable size. Then, a Lagrangian relaxation-based heuristic algorithm is designed to solve the SCP. Computational results with real-life instances taken from the Beijing Public Transport Holdings, Ltd. show that the proposed Lagrangian relaxation-based heuristic can obtain good quality solutions in reasonable computation time.