What is the most complex algorithm you used in your work – experts say

At the dawn of my career, I was tasked with developing an algorithm for automatically scheduling the work of metro drivers.

The essence of the task is to draw up a work schedule for train crews, taking into account the obligatory rest break. If the shift lasted more than 4 hours, then the drivers were entitled to a 30-minute lunch in the interval from 2.5 hours to 4 hours from the moment they entered the line. If the shift exceeded 7 hours, then the drivers had an additional 15-minute rest in the interval from 6 to 7 hours of work.

In all previous attempts to develop an appropriate algorithm, it was possible to distribute only half of the working time. The remaining “tails” had to be handled manually, since the algorithm “gave” extra crews or made the “wrong” shift, which was impossible to work on.

It would seem that the task was simple: after 30 minutes from the beginning of lunch, the driver had to be returned to the line. However, a peculiarity of the metro was revealed: the driver could only be returned to the same train from which he began his shift. And here the problem appeared.

Due to the train schedule, the duration of the lunch break “floated” from 25 to 33 minutes, depending on the time and day of the week (rush hour, weekdays, days off), as well as on individual metro lines. In addition, drivers could only dine at certain stations on the line. At the same time, the number of brigades having lunch at the same time was also limited, since while the main brigade was on a break, the so-called replacement brigade controlled the composition. And there were few of them.

Technically, everything was implemented using T-SQL within stored procedures and functions in MS SQL Server. It was necessary to take the train schedule data from the corresponding table, calculate the number of routes, and, based on the length of the route and shifts, calculate the number of required crews.

The first iteration of the algorithm consisted of 300 lines of code, with many nested subqueries to determine the “bounds” of the sample. Based on the results of the first iteration, it turned out that it was impossible to work on such a schedule, since the teams were people, not robots.

Further optimization led to an increase in the number of lines of code to 900. There was a triple nesting of queries, nested loops, double cursors, temporary tables and self-written SQL functions.

As a result, it turned out to optimize the automatic scheduling of work by 80%. The remaining 20% ​​were “tailings” of shifts, which did not allow creating a full-fledged shift for the brigade, and they had to be distributed manually.

Towards the end of this work, I was additionally entrusted with the task of automatically scheduling the work of shunting brigades (these are the brigades that land at the final or penultimate metro station, lead the train to a dead end and drive it back). The problem of these brigades, in addition to the lunch break, was also in the duration of their work: only 2-3 minutes. Because of this, overlays appeared in a matter of seconds, which, if incorrectly configured, gave an extra 3-5 minute shift in the morning or evening rush hour.

The result of the work was a “monstrous” SQL script, which was split into a main procedure of 1200 lines of code and in which three additional self-written functions of 50-150 lines of code were repeatedly called, as well as a script of shunting brigades for 700 lines.

After the end of development, it turned out that this script does not fit into the current processes of the depot. As a result, the developments in this script formed the basis for other software, which made it possible to compose shifts in an automated mode, and not in an automatic one. Subsequently, the main algorithm was reworked into an algorithm for the automated compilation of shifts for driver assistants, which became my diploma project.

The software for automated scheduling of work has reduced the number of hours required to create a new schedule from 20-30 to 5-6, since earlier this work was done manually using a pencil and eraser on A1 sheets. The software was fully implemented in three depots and began to be implemented in three more. In 2011, the director of the metro was changed, and the project was closed.