When some commuter trains arrive at the tip of the road, they need to travel to a switching platform to be turned around in order that they can depart the station later, often from a special platform than the one at which they arrived.
Engineers use software programs called algorithmic solvers to plan these movements, but at a station with hundreds of weekly arrivals and departures, the issue becomes too complex for a standard solver to unravel .
Using machine learning, MIT researchers have developed an improved planning system that reduces the solve time by as much as 50 percent and produces an answer that higher meets a user’s objective, akin to on-time train departures. The brand new method is also used for efficiently solving other complex logistical problems, akin to scheduling hospital staff, assigning airline crews, or allotting tasks to factory machines.
Engineers often break these sorts of problems down right into a sequence of overlapping subproblems that may each be solved in a feasible period of time. However the overlaps cause many choices to be needlessly recomputed, so it takes the solver for much longer to succeed in an optimal solution.
The brand new, artificial intelligence-enhanced approach learns which parts of every subproblem should remain unchanged, freezing those variables to avoid redundant computations. Then a standard algorithmic solver tackles the remaining variables.
“Often, a dedicated team could spend months and even years designing an algorithm to unravel just one in every of these combinatorial problems. Modern deep learning gives us a chance to make use of latest advances to assist streamline the design of those algorithms. We are able to take what we all know works well, and use AI to speed up it,” says Cathy Wu, the Thomas D. and Virginia W. Cabot Profession Development Associate Professor in Civil and Environmental Engineering (CEE) and the Institute for Data, Systems, and Society (IDSS) at MIT, and a member of the Laboratory for Information and Decision Systems (LIDS).
She is joined on the paper by lead writer Sirui Li, an IDSS graduate student; Wenbin Ouyang, a CEE graduate student; and Yining Ma, a LIDS postdoc. The research might be presented on the International Conference on Learning Representations.
Eliminating redundance
One motivation for this research is a practical problem identified by a master’s student Devin Camille Wilkins in Wu’s entry-level transportation course. The coed desired to apply reinforcement learning to an actual train-dispatch problem at Boston’s North Station. The transit organization must assign many trains to a limited variety of platforms where they might be turned around well upfront of their arrival on the station.
This seems to be a really complex combinatorial scheduling problem — the precise sort of problem Wu’s lab has spent the past few years working on.
When faced with a long-term problem that involves assigning a limited set of resources, like factory tasks, to a gaggle of machines, planners often frame the issue as Flexible Job Shop Scheduling.
In Flexible Job Shop Scheduling, each task needs a special period of time to finish, but tasks might be assigned to any machine. At the identical time, each task consists of operations that have to be performed in the right order.
Such problems quickly turn out to be too large and unwieldy for traditional solvers, so users can employ rolling horizon optimization (RHO) to interrupt the issue into manageable chunks that might be solved faster.
With RHO, a user assigns an initial few tasks to machines in a set planning horizon, perhaps a four-hour time window. Then, they execute the primary task in that sequence and shift the four-hour planning horizon forward so as to add the subsequent task, repeating the method until your entire problem is solved and the ultimate schedule of task-machine assignments is created.
A planning horizon ought to be longer than anyone task’s duration, for the reason that solution might be higher if the algorithm also considers tasks that might be coming up.
But when the planning horizon advances, this creates some overlap with operations within the previous planning horizon. The algorithm already got here up with preliminary solutions to those overlapping operations.
“Perhaps these preliminary solutions are good and don’t should be computed again, but possibly they aren’t good. That is where machine learning is available in,” Wu explains.
For his or her technique, which they call learning-guided rolling horizon optimization (L-RHO), the researchers teach a machine-learning model to predict which operations, or variables, ought to be recomputed when the planning horizon rolls forward.
L-RHO requires data to coach the model, so the researchers solve a set of subproblems using a classical algorithmic solver. They took one of the best solutions — those with probably the most operations that don’t should be recomputed — and used these as training data.
Once trained, the machine-learning model receives a brand new subproblem it hasn’t seen before and predicts which operations shouldn’t be recomputed. The remaining operations are fed back into the algorithmic solver, which executes the duty, recomputes these operations, and moves the planning horizon forward. Then the loop starts all yet again.
“If, in hindsight, we didn’t must reoptimize them, then we are able to remove those variables from the issue. Because these problems grow exponentially in size, it may well be quite advantageous if we are able to drop a few of those variables,” she adds.
An adaptable, scalable approach
To check their approach, the researchers compared L-RHO to several base algorithmic solvers, specialized solvers, and approaches that only use machine learning. It outperformed all of them, reducing solve time by 54 percent and improving solution quality by as much as 21 percent.
As well as, their method continued to outperform all baselines after they tested it on more complex variants of the issue, akin to when factory machines break down or when there’s extra train congestion. It even outperformed additional baselines the researchers created to challenge their solver.
“Our approach might be applied without modification to all these different variants, which is basically what we got down to do with this line of research,” she says.
L-RHO can even adapt if the objectives change, mechanically generating a brand new algorithm to unravel the issue — all it needs is a brand new training dataset.
In the long run, the researchers want to higher understand the logic behind their model’s decision to freeze some variables, but not others. Additionally they wish to integrate their approach into other varieties of complex optimization problems like inventory management or vehicle routing.
This work was supported, partially, by the National Science Foundation, MIT’s Research Support Committee, an Amazon Robotics PhD Fellowship, and MathWorks.
