Surrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization
This addresses a specific combinatorial optimization problem for industries managing retail networks, but it is incremental as it builds on existing MCTS methods with a surrogate enhancement.
The paper tackles the facility location problem of minimizing sales loss from store closures by using Monte Carlo Tree Search (MCTS) with a surrogate model to speed up evaluations, resulting in faster solution generation while maintaining consistent quality compared to MCTS without the surrogate.
Industries frequently adjust their facilities network by opening new branches in promising areas and closing branches in areas where they expect low profits. In this paper, we examine a particular class of facility location problems. Our objective is to minimize the loss of sales resulting from the removal of several retail stores. However, estimating sales accurately is expensive and time-consuming. To overcome this challenge, we leverage Monte Carlo Tree Search (MCTS) assisted by a surrogate model that computes evaluations faster. Results suggest that MCTS supported by a fast surrogate function can generate solutions faster while maintaining a consistent solution compared to MCTS that does not benefit from the surrogate function.