MIT Researchers Develop AI-Enhanced System for Faster Complex Planning

Researchers at MIT have developed a new artificial intelligence-enhanced planning system that dramatically reduces the time it takes to solve complex logistical problems. The system, leveraging machine learning, cuts solve times by up to 50% while simultaneously improving the quality of solutions, particularly concerning objectives like on-time departures.

The innovative approach addresses challenges faced by traditional algorithmic solvers when dealing with intricate scheduling scenarios. One such scenario involves commuter trains arriving at terminal stations and needing to be efficiently routed to switching platforms for turnaround and subsequent departure. According to MIT, at stations handling thousands of weekly arrivals and departures, traditional solvers often struggle due to the overwhelming complexity.

Cathy Wu, the Thomas D. and Virginia W. Cabot Career Development Associate Professor in Civil and Environmental Engineering (CEE) and the Institute for Data, Systems, and Society (IDSS) at MIT, explains that engineers often break down these complex problems into smaller, overlapping subproblems. While this approach makes the problem more manageable, the overlaps lead to redundant computations, significantly slowing down the process of finding optimal solutions.

The MIT team’s AI-enhanced system overcomes this limitation by learning which parts of each subproblem should remain unchanged, effectively “freezing” those variables to avoid redundant computations. A traditional algorithmic solver then focuses on the remaining variables, leading to faster and more efficient problem-solving.

Wu emphasizes the potential impact of this research: “Often, a dedicated team could spend months or even years designing an algorithm to solve just one of these combinatorial 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.”

The research was led by Sirui Li, an IDSS graduate student, alongside Wenbin Ouyang, a CEE graduate student, and Yining Ma, a LIDS postdoc. The findings will be formally presented at the International Conference on Learning Representations.

The inspiration for this project stemmed from a real-world problem identified by Devin Camille Wilkins, a master’s student in Wu’s transportation course. Wilkins sought to apply reinforcement learning to optimize train dispatch at Boston’s North Station, where efficiently assigning trains to a limited number of platforms is crucial for timely turnarounds.

The researchers framed the problem as Flexible Job Shop Scheduling, where tasks (train routing, factory tasks) require varying completion times and can be assigned to different machines (platforms, factory machines). To tackle the complexity, they employed rolling horizon optimization (RHO) to break the problem into manageable segments.

Their technique, learning-guided rolling horizon optimization (L-RHO), uses machine learning to predict which operations should be recomputed as the planning horizon advances, further streamlining the optimization process.

In tests, L-RHO outperformed existing solvers, reducing solve time by 54% and improving solution quality by up to 21%. The system is also adaptable to changing conditions, such as machine breakdowns or congestion, demonstrating its robustness and scalability.

Wu notes, “Our approach can be applied without modification to all these different variants, which is really what we set out to do with this line of research.”

The researchers plan to further investigate the reasoning behind the model’s variable-freezing decisions and extend the approach to other optimization problems, such as inventory management and vehicle routing.