Schedule planning in the transport sector can be a real headache. With thousands of employees and hundreds of trips to coordinate, the number of possibilities is so vast that it is difficult, if not impossible, to list them explicitly. The challenge is always to find the schedule with the lowest cost. Issmail El Hallaoui, a professor in the Department of Mathematics and Industrial Engineering at Polytechnique Montréal, has developed a faster, more efficient way of doing this.
Combining several tasks can greatly reduce the size of the problem and the number of possible combinations.
In public transport and aviation, task distribution is often carried out using set partitioning models, which have their limits: among other things, they can generate billions of combinations from which the most cost-effective schedule must be extracted within a reasonable amount of time.
The researcher and his team developed a new model based on a very simple observation: a bus driver often stays in the same vehicle throughout his working day and can make several consecutive trips without leaving his seat. Why not group these segments into a single task? Indeed, combining several tasks can greatly reduce the size of the problem and the number of possible combinations.
Issmail El Hallaoui’s team managed to find the optimal solution to a problem involving 2,000 tasks in just one minute using this new scheduling tool, whereas commercial solvers struggle to achieve the same result in…10 hours! The aviation industry is already using this new program to manage airline crews and solve problems involving 50,000 flights. The research team is now hoping to take advantage of scheduling history to improve the solver’s results and its computing time.
When sulfur leads to minerals
Inclusion begins with children
