Faster Ways to Solve Complex Planning Issues | MIT News

When some commuter trains arrive at the end of the line, they have to go to the switch platform to turn so that they can leave the station later, usually from a different platform than the one they arrive.

Engineers use software programs called algorithm solvers to plan these actions, but in thousands of arrival and departure stations a week, the problem becomes too complicated and can be solved at once for traditional solvers.

Using machine learning, MIT researchers have developed an improved planning system that reduces the solution by 50% and produces a solution that better meets user goals, such as on-time train departures. The new approach can also be used to effectively solve other complex logistical problems such as scheduling hospital staff, assigning crew members, or assigning tasks to factory machines.

Engineers often break these problems down into a series of overlapping sub-problems, each of which can be solved within a feasible time. But overlapping causes many decisions to be recalculated unnecessarily, so it takes longer for the solver to achieve the optimal solution.

New, AI-enhanced approaches to understand which part of each subproblem should remain unchanged, freezing these variables to avoid redundant calculations. Then, traditional algorithm solvers can solve the remaining variables.

“Often, a dedicated team could spend months or even years designing an algorithm to solve just one of these combined problems. Modern deep learning gives us an opportunity to use new advances to help streamline the design of these algorithms. We can take what we know works well, and use AI to accelerate it,” says Cathy Wu, the Thomas D. and Virginia W. Cabot Career Development Associate Professor in Civil and Environmental Engineering (CEE) and the MIT Institute of Data, Systems and Society (IDS) and the Laboratory of Information and Decision Systems (LIDS).

Sirui Li, the IDSS graduate student’s lead writer, joined the paper; Wenbin Ouyang, CEE graduate student; and MA, the cover. The study will be presented at the International Conference on Learning Performance.

Eliminate redundancy

One motivation for this study was a practical problem that Devin Camille Wilkins found in Wu’s entry-level transportation course. The student hopes to apply reinforcement learning to the real train at the North Boston station – having problems. Transport organizations need to allocate many trains to a limited number of platforms where they can turn well before they arrive at the station.

It turns out that this is a very complex combinatorial scheduling problem – Wu’s lab’s exact type of type over the past few years.

When faced with a long-term problem involving allocating limited resources (such as factory tasks) to a group of machines, planners often use the problem as a flexible workshop arrangement framework.

In flexible workshop arrangements, each task takes a different time to complete, but tasks can be assigned to any machine. At the same time, each task consists of operations that must be performed in the correct order.

For traditional solvers, such problems quickly become too big and clumsy, so users can use rolling field of view optimization (RHO) to break the problem down into manageable blocks that can be solved faster.

With Rho, users assign initial tasks to machines with fixed scheduled scopes, perhaps a four-hour time window. They then perform the first task in that sequence and move the four-hour scheduled vision forward to add the next task, repeating the process until the entire problem is solved and a final timetable for task assignment is created.

The planned range should last longer than any task, because the solution would be better if the algorithm also considers the task that will appear.

However, as the scope of the plan advances, this overlaps with the operations in the previous plan perspective. This algorithm has proposed a preliminary solution to these overlapping operations.

“Maybe these preliminary solutions are good and don’t need to be computed again, but maybe they are not good. This is where machine learning comes in,” Wu explained.

For what they call learning-guided rolling range optimization (L-RHO), researchers teach machine learning models to predict which operations or variables should be recalculated as the planned field of view rolls forward.

L-RHO requires data to train the model, so the researchers solved a set of subproblems using classical algorithm solvers. They took the best solutions – the ones that didn’t require recalculation – and used them as training data.

Once trained, machine learning models receive new sub-questions that have never been seen before and predict which operations should not be recalculated. The remaining operations are fed back to the algorithm solver, which performs tasks, recalculates these operations and moves the planned field of view forward. Then the loop starts again.

She added: “In hindsight, we don’t need to readjust them, then we can remove these variables from the question. Because the size of these problems grows exponentially, it would be very beneficial if we can give up some of these variables.”

Adaptable, scalable approach

To test their method, the researchers compared L-RHO with several basic algorithm solvers, professional solvers, and methods that use only machine learning. It outperformed everyone, reducing the solution by 54% and improving the quality of the solution by 21%.

Furthermore, their approach continues to outperform all benchmarks when they test on more complex variants of the problem, such as when factory machines crash or extra train congestion. It even surpasses other baselines that researchers have created to challenge their solvers.

“Our method can be applied without modifying all of these different variants, and that’s really something we’re related to this study,” she said.

If the target changes, you can adapt to L-RHO and automatically generate a new algorithm to solve the problem – all it needs is a new training dataset.

In the future, researchers hope to better understand the logic of the model’s decision to freeze some variables, rather than others. They also want to integrate the method into other types of complex optimization problems, such as inventory management or vehicle routes.

This work is supported by the National Science Foundation, the MIT Research Support Committee, Amazon Robot PhD Scholarships, and Mathematics Engineering.