SISCOG has been investing on research and development (R&D) since its inception. However and since 2003, the company has a research lab fully devoted to R&D, the Innovation Department.
In this lab, a team of highly-skilled researchers, develop and improve optimisation models used to solve resource scheduling problems characteristic to transportation companies.
The research is done both internally and in partnership with other research labs, universities and even clients.
Some of SISCOG’s research projects have been supported by government incentives.
RESPLAN (for RESource PLANner) was a research project funded by “Quadro de Referência Estratégico Nacional – Sistema de Incentivos à Investigação e Desenvolvimento Tecnológico (QREN)” whose goal is the further development of an integrated product for planning and managing resources in transportation companies.
RESPLAN was carried out in partnership with the School of Engineering of the Oporto University (FEUP).
LUCIA III Project
Continuing its R&D partnership, SISCOG and Dutch Railways (NS), the main Dutch passenger railway operator, have further developed the LUCIA algorithm.
It is now capable of solving the NS crew scheduling problem for the whole week in a single run instead of solving it day by day in seven runs (as LUCIA I and LUCIA II, the older generations of this algorithm, did).
Today, LUCIA III is a much more powerful optimiser. Solving the problem on a weekly basis opens an opportunity for improving the efficiency of the solution, because the constraints that force the solution to be “rosterable” can be applied in a less conservative way without loss of compliance. However, in order to take advantage of this opportunity, the researchers had to face the challenge of solving a much larger problem (assigning crew to 30,000 trains instead of circa seven times less). This was overcome with the use of several state-of-the-art techniques.
The experiments made in the research with real data showed that solving the crew scheduling problem for the complete week lead to a significant improvement of about 1% efficiency gain, which reflects a cost reduction of 3 million euros in NS´s reality.
This algorithm combines Lagrangian heuristics, column generation and column fixing techniques, as well as intensive parallel computing.
The LUCIA III algorithm is being integrated in SISCOG’s CREWS optimizer and it is expected to be available in the next release.
These techniques and the results of this work are described in the paper “Solving Large Scale Crew Scheduling Problems in Practice”, which is an extended version of this Technical Report.
E. J. W. Abbink, L. Albino, T. Dollevoet, D. Huisman, J. Roussado, and R. L. Saldanha. Solving Large Scale Crew Scheduling Problems in Practice. Public Transport, 3(2): 149–164, 2011.
LUCIA II Project
This project was done in the context of a continued partnership between SISCOG and the Dutch Railways (NS) as a continuation of LUCIA I (see below).
It aimed at solving as fast as possible large-scale duty scheduling problems considering all real-world details.
The challenge was to efficiently solve in a single run for a single weekday the entire duty scheduling problem both for NS’ train drivers and guards with all real-world constraints (e.g. constraints limiting in each crew base the number of duties assigned, the average duration of the duties assigned, etc.).
This means handling problems that can go up to 11,380 train trips and 29 personnel bases.
The results were compared with previous solutions. All new solutions were feasible, which was not the case for all existing solutions, and they were between 0.12% and 2.84% more efficient than the previous ones, which were already optimised. Some of the solutions were obtained in less than 12 hours of running time.
Sophisticated Operational Research and parallel computing techniques were used to achieve these results.
LUCIA I Project
This project was the result of a partnership between SISCOG and the Dutch Railways (NS) and aimed at developing an optimisation model capable of solving from scratch large-scale duty scheduling problems.
The challenge was to solve in a single run for a single weekday the entire duty scheduling problem for NS’ train drivers with reduced number of constraints (i.e. only constraints limiting the number of duties and average duty length per personnel base).
This means handling problems that can go up to 9249 train trips and 29 personnel bases.
The results were compared with previous solutions for several test cases. Solutions that are up to 3% more efficient than highly optimised solutions were obtained, all of them in less than 33 hours of running time.
Sophisticated Operational Research techniques were used to achieve these results.