The Key To Reducing Sales Losses: Optimizing Corporate Facility Networks With High-Speed Surrogate-Assisted MCTS
3 main points
✔️ focus on ways to minimize sales losses when companies open or close regional branches and adjust their facility networks. However, accurately estimating sales can be time-consuming and costly. To address this issue, we support a surrogate model that uses Monte Carlo Tree Search (MCTS) to expedite the evaluation.
✔️ Surrogate functions are fast but less accurate, and we have shown that they can efficiently solve optimization problems. Specifically, we approached the problem of closing a retail store to minimize sales losses.
✔️ Future work will investigate better surrogate function implementations and their application to other data sets and domains that take probability theory into account.
Surrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization
written by Saeid Amiri, Parisa Zehtabi, Danial Dervovic, Michael Cashmore
(Submitted on 14 Mar 2024)
Comments: Accepted to the ICAPS Planning and Scheduling for Financial Services (FINPLAN) 2023 workshop
Subjects: Artificial Intelligence (cs.AI)
code：
The images used in this article are from the paper, the introductory slides, or were created based on them.
Summary
This paper focuses on ways to minimize sales losses when firms adjust their facility networks by opening or closing regional branches. However, accurately estimating sales is time-consuming and costly. To address this issue, we support a surrogate model that uses Monte Carlo Tree Search (MCTS) to speed up the evaluation process. Results suggest that MCTS, supported by a fast surrogate function, may provide faster and more consistent solutions compared to regular MCTS.
Introduction
This paper focuses on a situation in which service and retail establishments need to decide where to locate their facilities in response to population changes and changing market trends. The problem is combinatorial optimization, which is generally computationally intractable. Therefore, a technique called Monte Carlo Tree Search (MCTS) is proposed, which is used in gaming and other domains to solve the problem by searching for possible actions and evaluating the value of each action.
We also apply MCTS to the facility location problem and propose a surrogate-assisted MCTS (SMCTS) that combines a fast surrogate evaluation function and a slow default evaluation function. The main evaluation function is a regression model that evaluates profitability, but due to its high computational cost, a surrogate function is introduced. This approach is applied to the problem of closing a network of liquor stores to minimize sales losses. Results show that combining MCTS with a surrogate function reduces computation time.
Related Research
Facility location problems have been framed using operations research methods such as set coverage, maximum coverage, and p-central. In most studies, integer programming and clustering techniques have been used to solve the problem. However, this paper proposes a way to quickly evaluate and optimize the facility location problem using data-driven evaluation functions and surrogate models. This can aid in decisions to modify existing facility networks. The study also presents prior work in surrogate-based optimization and is the first study to use surrogates in MCTS.
Proposed Method
This problem is a facility location problem to minimize sales loss due to retail store closures; there is a network of N stores in the city. Our goal is to minimize the final sales loss by closing M stores from that network. This is done by optimizing a vector X representing the opening and closing of each store. Specifically, we find X that minimizes the loss due to store closures by minimizing a certain evaluation function. This evaluation function depends not only on the loss due to store closings, but also on store sales and other store conditions.
The solution framework employs surrogate-assisted MCTS (SMCTS). Nodes are identified in a tree and the solution is found through the steps of selection, evaluation, expansion, backup, and reevaluation.
The following figure shows how node values are refined by occasional reevaluation steps in surrogate-assisted Monte Carlo tree search (SMCTS).
It is evaluated using a surrogate function and includes a re-evaluation step to adjust for errors. This ensures that node values are updated accurately and that the search to find the optimal solution is efficient.
Experiment
Through experimental evaluation, the performance of SMCTS (surrogate-assisted MCTS) was analyzed in a variety of problem settings.
First, we experimented with the Iowa Liquor dataset. This includes store sales and location information. The main evaluation function Fm is estimated using an XGBoost regression model to evaluate each store's sales. The surrogate function Fs, on the other hand, is a model that is faster to compute than Fm but less accurate.
Left: Shows how the occasional reevaluation step improves the value of a node in SMCTS (Surrogate Assisted Monte Carlo Tree Search). The horizontal axis represents the number of stores that need to be removed.
Central panel: shows SMCTS with various surrogate errors. The vertical axis shows the ratio of the surrogate function Fs evaluation to the total evaluation, and the horizontal axis shows the surrogate function with increasing normalized RMSE.
Right: the consistency of the stores selected by SMCTS and MCTS is evaluated. The vertical axis shows the number of stores selected by SMCTS as opposed to MCTS, and the result is the average of 10 randomly selected counties.
Specific results showed that the frequency of use of the surrogate function increased with the number of stores to be deleted, reducing the overall evaluation burden. The number of reevaluations also increased as the surrogate error increased, but this increase was acceptable as long as the SMCTS matched the MCTS.
Finally, we compared the consistency of the two approaches to deleting different stores. In most cases, the SMCTS output was consistent with the MCTS, indicating consistency. However, some outlier counties showed inconsistency due to weak surrogate function estimation.
These results indicate that SMCTS is effective in facility location problems and is especially useful for large problems or when the quality of the surrogate function is low.
Conclusion
In this study, surrogate functions were introduced to the MCTS search for combinatorial optimization. Surrogate functions are fast but less accurate, and we showed that they can efficiently solve optimization problems. Specifically, we approached the problem of closing a retail store to minimize sales losses. In future work, they plan to investigate implementing better surrogate functions and applying them to other data sets and domains that take probability theory into account.
Categories related to this article
