當一些通勤火車到達線路的盡頭時，他們必須前往開關平台要轉動，以便以後可以離開車站，通常是從與到達的平台不同的平台上。
工程師使用稱為算法求解器的軟件程序來計劃這些動作，但是在每週數千個到達和出發的電台中，問題變得太複雜了，對於傳統的求解器即可一次解開。
使用機器學習，麻省理工學院的研究人員開發了一種改進的計劃系統，該系統將解決方案降低了50％，並產生了一種更好地滿足用戶目標的解決方案，例如準時的火車出發。新方法還可以用於有效地解決其他復雜的後勤問題，例如安排醫院工作人員，分配機組人員或將任務分配給工廠機器。
工程師經常將這些問題分解為一系列重疊的子問題，每個問題都可以在可行的時間內解決。但是重疊會導致許多決策被不必要地重新計算，因此求解器需要更長的時間才能達到最佳解決方案。
新的，人工智能增強的方法了解每個子問題的哪一部分應保持不變，從而凍結這些變量以避免冗餘計算。然後，傳統的算法求解器可以解決其餘變量。
“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,” says Cathy Wu, the Thomas D. and Virginia W. Cabot Career Development Associate Professor in Civil and Environmental Engineering (CEE) and the麻省理工學院數據，系統和社會研究所（IDS）和信息和決策系統實驗室成員（LIDS）。
IDSS研究生的首席作家Sirui Li加入了紙上； Wenbin Ouyang，CEE研究生；和MA，蓋上的蓋子。該研究將在國際學習表現會議上介紹。
消除冗餘
這項研究的一個動機是吳·卡米爾·威爾金斯（Devin Camille Wilkins）在吳的入門級運輸課程中發現的實用問題。該學生希望將強化學習應用於波士頓北部車站的真正火車 – 遇到問題。運輸組織需要將許多火車分配給有限數量的平台，在那裡它們在到達車站之前就可以很好地轉過。
事實證明，這是一個非常複雜的組合調度問題 – Wu的實驗室過去幾年的確切類型的類型。
當面對一個長期問題，涉及將有限的資源（例如工廠任務）分配給一組機器時，規劃人員通常將問題作為靈活的車間安排框架。
在靈活的車間安排中，每個任務都需要不同的時間來完成，但是可以將任務分配給任何機器。同時，每個任務都由必須按正確順序執行的操作組成。
對於傳統求解器而言，此類問題很快變得太大且笨拙，因此用戶可以採用滾動視野優化（RHO）將問題分解為可以更快地解決的可管理塊。
使用Rho，用戶將初始任務分配給固定計劃範圍的機器，也許是四個小時的時間窗口。然後，他們在該順序中執行第一個任務，並將四個小時的計劃視野向前移動以添加下一個任務，重複該過程，直到解決整個問題並創建任務分配的最終時間表。
計劃範圍的時間應比任何一個任務的持續時間更長，因為如果算法還考慮將要出現的任務，則該解決方案會更好。
但是，當計劃範圍的進步時，這會與以前的計劃視野中的操作重疊。該算法已經提出了這些重疊操作的初步解決方案。
Wu解釋說：“也許這些初步解決方案是好的，不需要再次計算，但也許它們不好。這是機器學習進來的地方。”
對於他們稱之為學習指導的滾動範圍優化（L-RHO）的技術，研究人員教授機器學習模型，以預測計劃視野向前滾動時應重新計算哪些操作或變量。
L-RHO需要數據來訓練模型，因此研究人員使用經典算法求解器解決了一組子問題。他們採用了最好的解決方案 – 那些不需要重新計算的操作最多的解決方案 – 並將其用作培訓數據。
一旦受過培訓，機器學習模型就會收到以前從未見過的新子問題，並預測不應重新計算哪些操作。其餘操作被饋回算法求解器，該算法求解器執行任務，重新計算這些操作並將計劃視野向前移動。然後循環重新開始。
她補充說：“在事後看來，我們不需要重新調整它們，那麼我們可以從問題中刪除這些變量。因為這些問題的大小成倍增長，如果我們可以放棄其中一些變量，那將是非常有利的。”
適應性，可擴展的方法
為了測試他們的方法，研究人員將L-RHO與僅使用機器學習的幾種基本算法求解器，專業求解器和方法進行了比較。它的表現優於所有人，將解決方案減少了54％，將解決方案質量提高了21％。
此外，當他們在問題的更複雜變體上測試時，例如當工廠機器崩潰或額外的火車擁塞時，他們的方法繼續勝過所有基準。它甚至超過了研究人員為挑戰其求解器而創建的其他基線。
她說：“我們的方法可以在沒有修改所有這些不同變體的情況下應用，這確實是我們與這一研究有關的事情。”
如果目標發生變化，則可以適應L-RHO，自動生成一種新算法來解決問題 – 它所需的只是一個新的培訓數據集。
將來，研究人員希望更好地了解模型決定凍結某些變量的邏輯，而不是其他變量。他們還希望將方法整合到其他類型的複雜優化問題中，例如庫存管理或車輛路線。
這項工作得到了國家科學基金會，麻省理工學院研究支持委員會，亞馬遜機器人博士獎學金和數學工程的支持。
