Column generation algorithm for the timetable-based crew scheduling problem in a bus rapid transit system

Abstract

El artículo presenta un algoritmo de minimización de turnos de trabajo para el sector de transporte masivo. Se estudia el caso de Integra S.A.S. en la ciudad de pereira y es probado con instancias de literatura. Adicionalmente se presentan variaciones en una estrategia de formación de bloques de trabajo, experimentando con el rendimiento de un algoritmo de generación de columnas cuando se ingresan entradas diversificadas. El algoritmo responde efectivamente para minimizar el objetivo propuesto con tiempos computacionales razonables y brinda capacidad de fácil adaptación para otros casos y sectores industriales.

This article presents an algorithm to solve a minimization problem in the work shifts creation to operate a massive transportation system. This algorithm is used to solve ten years of real-world application cases of a Colombian bus rapid system operator with several time restrictions for shift quality. In the literature, this problem is known as a Crew Scheduling Problem (CSP), and it has applications in many industries like airlines, trains, or subway operations. The optimization algorithm is based on a Column Generation (CG) with a critical adaptation for the timetables provided as input and requirement; it consists of a first phase with a feasible cutting heuristic of the timetables and a second phase with the principal approach of CG to create the minimum work shifts for the proper operation required. Computational experiments are made to prove the different variants of the first phase algorithm between making an only timetable cut and all cutting options for the CG performance in effort execution time and objective function value. The principal approach of CG is also proved in sets of instances published in the literature about CSP, adapting the CG algorithm to minimize the shifts generated using two different performance measures: the same shifts amount and the costs of the original problem. The results prove a better performance of the principal approach when there is a poorly variety of the blocks formed by the cutting strategy of the timetables. The proposed algorithm is effective to decrease the crew shifts with schedule considerations that have not been covered in previous works.