Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959394 | European Journal of Operational Research | 2017 | 15 Pages |
Abstract
Dynamic resource allocation (DRA) problems constitute an important class of dynamic stochastic optimization problems that arise in many real-world applications. DRA problems are notoriously difficult to solve since they combine stochastic dynamics with intractably large state and action spaces. Although the artificial intelligence and operations research communities have independently proposed two successful frameworks for solving such problems-Monte Carlo tree search (MCTS) and rolling horizon optimization (RHO), respectively-the relative merits of these two approaches are not well understood. In this paper, we adapt MCTS and RHO to two problems - a problem inspired by tactical wildfire management and a classical problem involving the control of queueing networks - and undertake an extensive computational study comparing the two methods on large scale instances of both problems in terms of both the state and the action spaces. Both methods are able to greatly improve on a baseline, problem-specific heuristic. On smaller instances, the MCTS and RHO approaches perform comparably, but RHO outperforms MCTS as the size of the problem increases for a fixed computational budget.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Dimitris Bertsimas, J. Daniel Griffith, Vishal Gupta, Mykel J. Kochenderfer, Velibor V. MiÅ¡iÄ,